Ir para conteúdo
  • Cadastre-se

fredericopissarra

Membros
  • Total de itens

    128
  • Registro em

  • Última visita

Reputação

118 Excellent

10 Seguidores

Últimos Visitantes

O bloco dos últimos visitantes está desativado e não está sendo visualizado por outros usuários.

  1. Eis um texto meu explicando o AES. Espero que gostem: https://bitismyth.wordpress.com/2017/05/19/wanna-laugh-ou-criptografia-no-refugio-dos-elfos/
  2. Em linguagens com tipagem, como é o caso de C, existem inteiros sinalizados (possuem valores negativos) e não sinalizados (apenas valores positivos). É intuitivo, para o estudante, pensar que valores negativos como sendo aqueles que tem um sinal '-' na frente do número, no entanto, não é assim que as coisas são feitas pelo processador. Não há como colocar um '-' na frente de um valores binários, nos circuitos do processador ou do computador. Acredito que eu já tenha digo, por aqui ou em meu blog, que valores inteiros sinalizados são meras representações e que, na realidade, eles não tenham sinal algum. Ou seja, a maneira como são interpretados é que dá sinal ao valor, na hora de ser convertido de e para a base decimal... É também comum que essa representaçao use a técnica do "complemento 2", onde o bit mais significativo do valor indica ao programa que esse valor pode ser interpretado como sendo negativo. Mas, o que diabos significa "complemento 2"? Que "complemento" é esse? Daqui por diante farei de conta que nosso processador hipotético tenha registradores de apenas 4 bits só para não ficar escrevendo um montão de bits, mas os raciocínios aplicam-se a 8, 16, 32, 64 e a 128 bits facilmente. Comecemos com os inteiros não sinalizados... Com 4 bits, todos os valores possíveis são de 0b0000 até 0b1111, ou, em decimal, de 0 a 15. Não há qualquer mistério ai. As operações aritméticas funcionam perfeitamente bem, desde que não tenhamos condições de overflow (exemplo: 0b0000 - 0b0001 = 0b1111, ou 0 - 1 = 15?). Se quisermos trabalhar com esses valores como se existissem valores negativos, um macete é encarar o bit mais significativo (msb) como se fosse um indicador de sinal (como se fosse o '-'). Se o msb for 0 temos um valor positivo, na faixa de 0 a 7 (0b0000 até 0b0111), se o msb for 1, temos valores negativos (discussão sobre a faixa segue abaixo). Poderíamos simplesmente parar ai, ou seja, -1 poderia ser representado como 0b1_001 (msb='-' e 1), mas isso causa problemas nas operações aritméticas fundamentais... Como vimos, 0b0000 - 0b0001 = 0b1111, ou seja, nessa representação teríamos como resposta -7 (que poderia ser encarada como uma condição de overflow, mas não é, como veremos). Outra técnica é a inversão de todos os bits de um valor positivo para obter o negativo e usarmos apenas o bit 1 como sinalização. Com o mesmo exemplo, -1 seria ~0b0001 = 0b1110, ou seja, o "inverso" de 1 (operação NOT) seria -6, o que ainda está errado. Mas essa representação é usada em computadores antigos, com alguns ajustes. Por exemplo, sempre que toparmos com o msb=1 devemos inverter o valor para obter seu absoluto... assim, ~0b1110 volta a ser 1, interpretado como negativo, e estaria tudo certo. Mas temos um problema: E quanto ao valor 0b1111? Seu inverso, obviamente, é 0b0000, o que significaria que temos +0 e -0 e, usando aritmética binária elementar 0b0000 - 0b0001 = 0b1111, ou seja, nessa representação temos +0 - +1 = -0 (menos zero?). A solução para isso foi o uso do conceito de complementação da faixa dos positivos. Se temos 8 valores positivos de 0b0000 até 0b0111, na sequência ascendente, podemos copiar a sequência, mudando apenas o msb para 1 e colocando-a "antes" da faixa dos positivos (de 0b1000 até 0b1111). Assim: 0b1000, 0b1001, 0b1010, ..., 0b000, 0b0001, ... Assim, temos 8 valores negativos antes do zero, na sequência {-8, -7, -6, ... 0, +1, ..., 7}. Ou, de outra maneira, um valor sinalizado pode ser calculado de acordo com a seguinte equação: Eis o "complemento 2", trata-se apenas da "complementação" da faixa dos inteiros positivos (quando s=0), na sequência, ascendente que mostrei, pela mesma sequência, mas com s=1. Onde: s é o msb e P é a precisão, em bits, do valor (lembrando que "precisão" é a quantidade de bits que expressa o valor absoluto - isso vale tanto para inteiros quanto para ponto flutuante). No nosso caso, P=3 e s é o bit 3. Vejamos como fica -1: Se 0b1111 é -1, então, pela equação acima temos (-1*2³)+(4+2+1) = -8+7 = -1. Isso faz com que as operações aritméticas fiquem corretas, exceto no caso de overflows, e não temos mais dois zeros: 0b1000 = -8. Existe, é claro, uma aparente assimetria de valores. No lado negativo o menor valor é -8 e no lado positivo o maior é +7. Isso é inevitável, já que temos uma quantidade par de valores possíveis, dividindo toda a faixa em dois blocos de 8 valores, onde um deles é 0 (que ficará do lado positivo). O único problema aqui é que -8 será sempre -8, se interpretado com sinal. Não é difíil perceber, embora eu gastaria muitas palavras aqui para descrever, que a fórmula acima pode ser substituída, lógicamente, por uma simples operação NOT seguida de um incremento de uma unidade para realizar a transformação de um valor positivo para negativo e vice-versa, ou seja, a operação de negação (o '-' unário de C e a instrução NEG do x86) só fazem y=~x+1. E essa é outra interpretação do significado do "complemento 2": Se o "complemento 1" for definido como a simples inversão, ao somar 1 temos um "complemento 2". Quanto aos overflows, eles acontecem, como sempre, na passagem dos extremos da faixa. -8 - 1 resultará em +7, assim como 7+1 resultatá em -8. Resumindo: inteiros sinalizados são uma representação, o seu processador sempre lida com valores sem sinal, mas mantém flags interpretando os valores com e sem sinal (CF para não sinalizados e SF e OF para sinalizados - e ZF para ambos -- em outros processadores, como ARM, por exemplo, os flags são nomeados, respectivamente, C, N, V e Z, de carry, "negativo", "oVerflow" e Zero). Agora dá para entender porque, em C, ao fazer,: unsigned int x = -1; Obtemos 0xffffffff?
  3. Outro follow-up: A geração de código ineficiente foi aceita como bug a ser corrigido (até o momento) no bugzilla do GCC.
  4. Um follow-up no que concerne esse bug: Não é um bug! Recebi uma explicação convincente do Bugzilla do GCC, onde me foi dito que a segunda chamada é feita apenas para ajustar o errno (errno = EDOM, quando x < 0). Mas, de qualquer modo, o código é ineficiente (comentário meu)... Em essência, o GCC está fazendo o que deveria mesmo fazer. Só mais um aviso: Não é necessário o uso de assembly inline para obter uma única instrução SQRTSS, SQRTSD ou FSQRT. Basta adicionar a opção -ffast-math (que não é habilitada com -O2 ou -O3 -- mas é habilitada com a opção -Ofast)...
  5. Entendo... mas acho que as sentenças acima, com algumas pequenas alterações para caberem no texto, explica melhor do que dizer que um computador binário não é binário... 🙂
  6. Recentemente divulguei uma descoberta minha, que, acho, ninguém prestou atenção antes, sobre a geração esquisita de código do GCC em relação à função built in sqrt()... Anunciei isso em outros foruns e tentei reporta para o bugzilla do GCC (não consegui!). Eis algumas reações: Nunca disse que não segue, mas que o GCC está criando código inútil. Ao apontar isso o sujeito usa aquele ar de profundo conhecedor do padrão (e o total desconhecimento de Assembly) para me dizer, num forum sobre 😄 Além disso, nosso "profundo conhecedor" não sabe de coisa alguma dos bugs que ainda existem em compiladores C/C++ (tanto o GCC quanto o CLANG, VC++ e Intel C++, pra citar alguns)... A característica de alguém que busca minúcias para desqualificar os argumentos de outra pessoa e/ou mudar de assunto completamente para o mesmo fim é, na minha opinião, coisa de idiota...
  7. Algumas críticas, se é que você quer vê-las: Essa ideia de que "código de máquina não é binário" é bizarra, em minha opinião... A linguagem de programação é ASSEMBLY, não "código de máquina"... Há uma correspondência direta, ok, mas não são a mesma coisa... Acredito que para o novato (se é que os textos se destinam a eles) a coisa está num ritmo muito rápido... Por exemplo, na parte 2 você cita "flags", mas não os conceitua... []s Fred
  8. O nome, agora, é contraditório (ARM=Advanced Risc Machine). O conjunto de instruções é tudo, menos restrito: https://is.gd/D2YIXu
  9. Um detalhe: O código do CLANG não só é mais elegante, quanto mais rápido (se ambos chamarem sqrtf()). Saltos condicionais para frente são assumidos, pelo algoritmo do branch predictor, do processador, como não tomados. Como a função builtin sqrt() geralmente será chamada com valores válidos, o processador não perde tempo corrigindo o salto, que, na maioria das vezes, não será feito. Mas, como eu disse, isso ai é um exagero dos compiladores... Um simples "SQRTSS XMM0,XMM0" resolve todo o problema... Anyway... por favor, notem que não estou dizendo que clang tende a gerar sempre código melhor que o GCC. Pelos meus testes ele costuma criar código próximo da performance do gerado pelo GCC, mas, neste caso, ele ganhou a parada (embora pudesse ser melhor!).
  10. Testei, agorinha, com o GCC 8.2 e o bug ainda está lá... Testei com o CLANG 6 e o bug não está lá. Ele gera até um código mais elegante: f: xorps xmm1,xmm1 ucomiss xmm0,xmm1 jb .lessthan0 sqrtss xmm0,xmm0 ret .lessthan0: jmp sqrtf Mas, essa chamada a sqrtf() é inútil, já que sqrtss retorna os mesmos valores para x < 0 e até valores inválidos como NAN e INFINITY.
  11. Confirmado! Isso é um BUG do GCC, pelo menos até a versão 7.3 (do Debian/Ubuntu, pelo menos) para o x86 e ARM AArch64 e versão 6.3 para ARM AArch32... Embora a versão 7.3 do MinGW-64 (do linux) não tenha esse BUG... Não sei se foi resolvida na versão 8. Felizmente é um bug inofensivo, já que o resultado será o da instrução SQRTSS (ou SQRTSD, se for double) e a chamda à função da libm sqrtf() (ou sqrt()) será feita, mas ignorada... Se for lidar com raiz quadrada no x86 e usa o GCC, prefira a função inline em asm, como mostrei acima. ou modifique-a para não ignorar o returno de sqrtf() se x < 0...
  12. O código fonte é público e a licença é GPL. Conserte-o, se acha que tem problema...
  13. Para os puristas, testar por overflow de inteiros sinalizados, em C, é um "undefined behavior", como dito no artigo 6.5.6:8 da especificação ISO 9989:1999 (por exemplo). Mas, considerando que estive falando da plataforma Intel e em representações de complemento 2, os "macetes" que mostrei anteriormente funcionam muito bem. Mas, se, mesmo assim, o purista exigir uma solução "correta", o GCC oferece funções built in para testes de overflow: _Bool __builtin_add_overflow(a, b, [type] *res); _Bool __builtin_sub_overflow(a, b, [type] *res); _Bool __builtin_mul_overflow(a, b, [type] *res); Esses são MACROS e existem funções equivalentes para cada "tipo", basta mudar o nome da operação para sadd, ssub ou smul (int), saddl, ssubl ou smull (long) ou saddll, ssubll ou smulll (long long). Troque o s por u para operações 'unsigned'... Nos macros, "[type]" é apenas uma indicação que o ponteiro, que não pode ser NULL, deve apontar para os tipos de a e b... As funções retornam 1 se houver overflow e colocam o resultado no local apontado por res. Existem ainda as funções built in de mesmos nomes, mas terminadas em _p. Elas não armazenam o resultado, mas usam o tipo do terceiro argumento (portanto não são funções, mas macros) para determinar se houve ou não overflow... A documentação diz que as operações são feitas com "precisão infinita" e só depois reduzida para a precisão do tipo do terceiro argumento. Mas, ao que parece, o compilador não usa aritmética de múltipla precisão, no sentido de bibliotecas como libgmp ou libmp. Eis um exemplo de código: #include <stdio.h> int main( void ) { int o, r, a, b; // a + b, com certeza, vai dar overflow. a = (unsigned)-1 >> 1; b = 1; // Faz a adição e retorna o flag de overflow. o = __builtin_add_overflow(a, b, &r); printf( "%d + %d = %d (%sOVERFLOW)\n", a, b, r, o ? "" : "not " ); } Sem otimizações a chamada ao built in fica assim, em assembly: xor ecx,ecx add eax,edx seto cl ; EAX sai com a soma e ECX com o booleano. A vantagem de usar os built ins é que todo GCC suporta, para qualquer arquitetura...
  14. Aliás, para o x86-64, esse último código é o usado pela rotina __ieee_sqrtf(), na glibc, exceto que o contraint de entrada é diferente ("xm"). Isso torna o código original ainda mais estranho... testa-se se x < 0 para chamar a mesma rotina (instrução)?! Muito estranho... []s Fred
  15. Eis uma simples função: float f( float x ) { return sqrtf( x ); } Já que os processadores desde o 486 têm o co-processador matemático incorporado, é de se supor que a rotina acima "use" apenas algumas instruções, não é? Mas não é isso o que acontece, mesmo na otimização máxima, obtemos algo assim: f: pxor xmm2, xmm2 sqrtss xmm1, xmm0 ucomiss xmm2, xmm0 ja .L8 movaps xmm0, xmm1 ret .L8: sub rsp, 24 movss dword [rsp+12], xmm1 call sqrtf movss xmm1, dword [rsp+12] add rsp, 24 movaps xmm0, xmm1 ret Essencialmente isso ai em cima faz chama a função sqrtf() se sqrtss retornar algo menor que zero (note que a lógica está invertida, UCOMISS compara zero [em xmm2] com o valor retornado por sqrtss), ou seja se CF=0 e ZF=0. Ainda não entendi porque o GCC prefere fazer algo assim, já que sqrtss retorna os mesmos valores que sqrtf() para valores inválidos: #include <stdio.h> #include <x86intrin.h> #include <math.h> int main ( void ) { float a[] = { -0.0, -1.0, NAN, -NAN, INFINITY, -INFINITY }; int i; __m128 f; for ( i = 0; i < sizeof a / sizeof a[0]; i++ ) { f = _mm_set_ss ( &a[i] ); printf ( "sqrtss(%1$f) = %2$f, sqrtf(%1$f) = %3$f\n", a[i], _mm_cvtss_f32 ( _mm_sqrt_ss( f ) ), sqrtf ( a[i] ) ); } } Compilando e executando, temos: $ cc -O2 -o test test.c -lm $ ./test sqrtss(-0.000000) = -0.000000, sqrtf(-0.000000) = -0.000000 sqrtss(-1.000000) = -nan, sqrtf(-1.000000) = -nan sqrtss(nan) = nan, sqrtf(nan) = nan sqrtss(-nan) = -nan, sqrtf(-nan) = -nan sqrtss(inf) = inf, sqrtf(inf) = inf sqrtss(-inf) = -nan, sqrtf(-inf) = -nan Até que eu descubra porquê o GCC faz esse teste, prefiro lidar com SSE diretamente para ter apenas uma instrução sendo executada. Só que temos um problema: Na função abaixo, _mm_set_ss() não deveria fazer coisa alguma, já que o argumento x é um float e estará em XMM0 ela está ali apenas para compatibilizar os tipos float e __m128. No entanto, MOVSS zera os bits superiores do registrador quando o operando fonte é memória. Logo depois _mm_sqrt_ss() extrairá a raiz quadrada e a colocará de volta em XMM0. A função _mm_cvtss_f32() garantidamente não faz nada aqui: float f( float x ) { return _mm_cvtss_f32( _mm_sqrt_ss( _mm_set_ss( x ) ) ); } Isso fica: f: movss dword [rsp-12], xmm0 ; movss xmm0, dword [rsp-12] ; ZERA os bits superiores. sqrtss xmm0, xmm0 ret Não estranhe a escrita na pilha sem o devido deslocamento de RSP. Provavelmente o compilador está usando a red zone e escritas até 128 bytes abaixo de RSP são permitidas sem alocação. Em essência, as duas primeiras instruções MOVSS são desnecessárias, mas usar algum macete do tipo abaixo não ajuda também: __m128 f; *(float *)&f = x; // copia x para XMM0[0-31]. Isso acaba criando os mesmos dois MOVSS. E essa "zeração" dos bits superiores não estão ai porque o tipo de retorno é um escalar float simples. Mesmo mudando o retorno para __m128, os MOVSS continuam lá. Assim, a única forma de garantir uma única instrução é usando assembly inline. Embora o "constraint" de entrada fique estranho: inline float mysqrtf( float x ) { __m128 r; __asm__ __volatile__ ( "sqrtss %0,%1" : "=x" (r) : "x" (x) // estranho, mas válido! ); return _mm_cvtss_f32( r ); } Agora sim, quando chamarmos mysqrtf() apenas a instrução SQRTSS será usada. Ahhh... os mesmos testes são feitas, em sqrtf(), se -mfpmath=387 for usado...
×
×
  • Criar Novo...