V¡®u§ 849 Posted January 7, 2012 Aritmética Inteira de 128 bits (1) Introdução ========== Com 32 bits podemos representar 2^32 números diferentes, isto é, 4294967296 (~4 bilhões) números diferentes, tais como inteiros com sinal de -2147483648 até +2147483647 ou inteiros sem sinal de 0 até 4294967295 (Longint e Longword respectivamente). Isso é suficiente para muitas finalidades como, por exemplo, guardar a posição de um byte em um arquivo de 4GB. Mas às vezes precisamos representar inteiros maiores e então podemos usar TLargeInteger (Windows.pas) e Int64 (a partir do Delphi 4) para representar inteiros de 64-bits (2^64 valores diferentes): 18446744073709551616 (~18 sestilhões) de valores, de -9223372036854775808 até +9223372036854775807 (~9 sestilhões, 17-18 dígitos). Essa quantidade de dígitos é muito mais do que eu preciso e não consigo imaginar qualquer uso prático para mais do que isso- a não ser Bill Gates que conta seu dinheiro em sestilhões! ;) Mas de tempos em tempos eu vejo alguém no fórum perguntar por mais dígitos que o Int64 oferece... De qualquer maneira, se válido ou completamente inútil numa proposta prática, veremos a implementação de várias procedures e functions desenvolvidas para trabalhar com inteiros de 128-bits, que nos servirão para mostrar exemplos de instruções básicas de assembler. Este "inteiros longos", "inteiros grandes" ou "inteiros enormes" podem manter 2^128 diferentes valores (38-39 dígitos). Representação dos inteiros de 128-bits ====================================== Eu chamo o novo tipo Hugeint mas, por exemplo, Bigint (big integer) ou Int128 podem ser nomes igualmente bons. Largeint pode ser confundido com o tipo da unit Windows.pas que refere-se ao inteiro de 64-bits. Quando precisamos representar o novo tipo, também existem várias formas de fazê-lo. Eu optei pela representação mais simples- um array de 4 inteiros de 32 bits: type Hugeint: packed array [0..3] of longword; Também decidi pelo formato little-endian já que é o padrão na arquitetura Intel e isto significa que o primeiro elemento do array (endereço mais baixo) guardará os 32 bits de ordem mais baixa (menos significativos) e o último elemento do array (endereço mais alto) guardará os 32 bits de mais alta ordem (mais significativos). Abaixo é a forma que os números 5 e 5000000000 ($12A05F200) serão representados: +---- 32 bits de baixa ordem | v +-------------+-------------+-------------+-------------+ | $00000005 | $00000000 | $00000000 | $00000000 | = 5 +-------------+-------------+-------------+-------------+ 0 1 2 3 +-------------+-------------+-------------+-------------+ | $2A05F200 | $00000001 | $00000000 | $00000000 | = 5000000000 +-------------+-------------+-------------+-------------+ $12A05F200 ^ | 32 bits de alta ordem ----+ Os próprios inteiros são armazenados no formato little-endian (primeiro o byte de mais baixa ordem). Se você verificar a representação em bytes de um número na memória, ela se pareceria com isso (valores em bytes representados na notação hexadecimal): $00000005 +-------------+-------------+-------------+-------------+ | 05 00 00 00 | 00 00 00 00 | 00 00 00 00 | 00 00 00 00 | = 5 +-------------+-------------+-------------+-------------+ 0 1 2 3 +-------------+-------------+-------------+-------------+ | 00 F2 05 2A | 01 00 00 00 | 00 00 00 00 | 00 00 00 00 | = 5000000000 +-------------+-------------+-------------+-------------+ $12A05F200 $2A05F200 $00000001 Entretanto, para quase todas as operações, podemos abstrair a ordem do byte e considerar que os inteiros de 32-bits são unidades atômicas, desde que a ordem do byte seja mantida transparentemente. Algumas instruções úteis ======================== Antes de começarmos, vejamos algumas instruções úteis que usaremos neste artigo (principalmente na continuação desta parte); antes, porém, é preciso enfatizar que a proposta deste artigo não é ensiná-lo assembler. Tudo que eu posso fazer neste espaço limitado é simplesmente mostrar exemplos de algumas instruções. Como material de referência, recomendo estes links: * Intel 80386 Reference Programmer's Manual Um versão HTML deste manual da Intel. O pseudocódigo ajuda a entender as instruções e seus efeitos sobre os flags. Excelente. http://people.freebsd.org/~jhb/386htm/toc.htm Existem alguns links quebrados, mas as páginas estão lá. Tente encontrá-los no diretório: http://people.freebsd.org/~jhb/386htm/ * iAPx86 - Norton Guide Não é tão didático quanto o documento acima, mas contém todas as instruções do 8086 do Pentium e Pentium Pro, com informações de tamanho e tempo não inclusas no link acima. http://www.clipx.net/ng/iapx86/index.php * The IA-32 Intel Architecture Software Developer's Manual, Volume 2: Instruction Set Reference Manual em PDF descrevendo as instruções dos processadores IA-32 (Pentium, Pentium Pro, Pentium II, Pentium III, Pentium 4 e Xeon). Inclui pseudocódigo que explica as instruções e como elas afetam os flags dos registradores. http://www.intel.com/design/pentium4/manuals/245471.htm * Otimização - How to optimize for the Pentium family of microprocessors Excelente guia de otimização escrito por Agner Fog http://fatphil.org/x86/pentopt/index.html - Optimizations for Intel's 32-Bit Processors Outro excelente guia de otimização. http://x86.ddj.com/ftp/manuals/686/optimgd.pdf OK, agora vamos ver as instruções. Referência: Z/ZF: Flag Zero S/SF: Flag de Sinal C/CF: Flag de Transporte (Carry) P/PF: Flag de Paridade A/AF: Flag Auxiliar s: bit de sinal (bit de ordem mais alta) o: bit ímpar (bit de ordem mais baixa) x: valor do bit 0: o valor 0 1: o valor 1 r: bit invertido em relação ao valor anterior u: bit não alterado desde o valor anterior XX: valor desconhecido Nos exemplos presumimos que o valor de AL antes de cada operação é sxxxxxxo (bit de sinal, 6 bits desconhecidos e bit ímpar). Aqui temos algumas instruções para começar: SHL al,1 AL := xxxxxxo0 CF := s Deslocamento à esquerda SAL al,1 AL := xxxxxxo0 CF := s Mesmo que SHL SHR al,1 AL := 0sxxxxxx CF := o Deslocamento à direita SAR al,1 AL := ssxxxxxx CF := o Deslocamento aritmético à direita SAR al,7 AL := ssssssss CF := x Reprodução do bit de sinal ROL al,1 AL := xxxxxxos CF := s Rotação à esquerda ROR al,1 AL := osxxxxxx CF := o Rotação à direita RCL al,1 AL := xxxxxxoC CF := s Rotação completa com transporte à esquerda RCR al,1 AL := Csxxxxxx CF := o Rotação completa com transporte à direita AND al,al AL := uuuuuuuu CF := 0 Define flags (veja abaixo) AND al,-1 AL := uuuuuuuu CF := 0 -1 = $FF = 1111111 Define flags (veja abaixo) AND al,$01 AL := 0000000u CF := 0 $01 = 00000001 AND al,$80 AL := u0000000 CF := 0 $80 = 10000000 AND al,$5A AL := 0u0uu0u0 CF := 0 $5A = 01011010 AND al,0 AL := 00000000 CF := 0 XOR AL,AL ou MOV AL,0 são melhores TEST AL,XX AL := uuuuuuuu TEST é como AND mas o resultado não é armazenado no destino. O resultado é usado para definir as flags (veja abaixo) TEST AL,-1 é melhor que AND AL,-1 e OR AL,AL porque não escreve em AL, o que permite certas otimizações em alguns casos. OR al,al AL := uuuuuuuu CF := 0 Define as flags (veja abaixo) OR al,$01 AL := uuuuuuu1 CF := 0 $01 = 00000001 OR al,$80 AL := 1uuuuuuu CF := 0 $80 = 10000000 OR al,$5A AL := u1u11u1u CF := 0 $5A = 01011010 OR al,-1 AL := 11111111 CF := 0 Mesmo que MOV AL,1 XOR al,al AL := 0 CF := 0 Utilize MOV AL,0 para preservar as flags XOR al,$5A AL := ururruru CF := 0 $5A = 01011010 XOR al,-1 AL := rrrrrrrr CF := 0 Mesmo que NOT AL Exceto pelas instruções de rotação (ROL, RCL, ROR e RCR), todas acima definem SF, ZF e PF baseados no resultado das operações: SF = valor do bit de mais alta ordem do resultado ZF = 1 ("definido") se o resultado for zero, 0 ("limpo") nos demais casos PF = 1 ("definido") se o o byte de mais baixa ordem do resultado contém um número par de bits 1, senão 0 ("limpo") Veja mais algumas instruções: STC CF := 1 Define o flag de Transporte CLC CF := 0 Limpa o flag de Transporte CMC CF := r Complementa o flag de Transporte LAHF AH := SZxAxPxC SAHF Presumindo que AH é SZxAxPxC: ZF := S; ZF := Z; AF := A; PF := P; CF := C SETc AL AL := CF Define se carry SETs AL AL := SF Define se sign SETz AL AL := ZF Define se zero SETe AL AL := ZF Define se equal (sinônimo de SETZ) SETp AL AL := PF Define se paridade SETpe AL AL := PF Define se a paridade é par (sinônimo de SETP) SETo AL AL := OF Define se overflow SETnc AL AL := NOT CF Define se não carry SETns AL AL := NOT SF Define se não sign SETnz AL AL := NOT ZF Define se não zero SETne AL AL := NOT ZF Define se não equal (sinônimo de SETNZ) SETnp AL AL := NOT PF Define se não paridade SETpo AL AL := NOT PF Define se a paridade é ímpar (sinônimo de SETNP) SETno AL AL := NOT OF Define se não overflow SETa (ou SETNbe), SETae (ou SETnb), SETb (ou SETnae), SETbe (SETna), SETg (ou SETNle), SETge (ou SETnl), SETl (ou SETnge) e SETle (SETng) definem o byte de destino para 1 ou 0 dependendo da condição específica ser satisfeita ou não. ADD AL,XX AL := AL+XX CF := 1 se a operação gera transporte; 0 outros casos SUB AL,XX AL := AL-XX CF := 1 se a operação precisa de um empréstimo; 0 outros casos SUB AL,0 AL := uuuuuuuu Define os flags baseados no AL SUB AL,AL AL := 0 Mesmo que XOR AL,AL ou MOV AL,0 CMP AL,XX CMP é como SUB mas o resultado não é armazenado no destino. A operação simplesmente define os flags. ADC AL,XX AL := AL+XX+C CF := 1 se a operação gera um transporte; 0 outros casos SBB AL,XX AL := AL-C-XX CF := 1 se a operação necessitade um empréstimo; 0 outros casos NEG AL AL := -AL CF := 1 se previamente AL <> 0 NOT AL; INC AL é o mesmo NOT AL AL := rrrrrrrr CF := u Mesmo que XOR AL,-1 Funções de Conversão ==================== Estas funções nos ajudarão a entender a representação dos inteiros 128-bits. Longword para Hugeint --------------------- Vamos começar convertendo de Longword para HugeInt. Os 32 bits de mais baixa ordem do resultado serão os 32 bits do parâmetro e os 96 bits de mais alta ordem serão zerados. function UToHugeint(const x: Longword): Hugeint; overload; // Result := Hugeint(x); // Parâmetros: EAX = x; EDX = @Result; asm xor ecx, ecx // ECX := 0; mov [edx+_0_], eax // Result[0] := x; mov [edx+_1_], ecx // Result[1] := 0; mov [edx+_2_], ecx // Result[2] := 0; mov [edx+_3_], ecx // Result[3] := 0; end; Comentários: * "_0_", "_1_", "_2_", e "_3_"? O que são? São constantes que representam os deslocamentos dos quatro elementos do vetor, permitindo-nos escrever um código mais limpo. const _0_ = 0; _1_ = 4; _2_ = 8; _3_ = 12; Longint para Hugeint -------------------- Os 32 bits inferiores do resultado serão os 32 bits do parâmetro. Se o número for positivo ou zero, então os 96 bits superiores serão 0, senão os 96 bits superiores serão 1. Isso nos força a fazer uma comparação ou teste do sinal e então executar um jump condicional baseado no resultado: function ToHugeint(const x: Longint): Hugeint; overload; // Result := Hugeint(x); // Parâmetros: EAX = x; EDX = @Result; asm or eax, eax // EAX := EAX or EAX; // EAX não é alterado // Efeito colateral: // SF (Flag de Sinal) := EAX < 0; mov ecx, 0 // ECX := 0; jns @@not_negative // if not SF then goto @@not_negative; dec ecx // ECX := ECX - 1; // 0 - 1 = -1 = $FFFFFFFF @@not_negative: mov [edx+_0_], eax // Result[0] := x; mov [edx+_1_], ecx // Result[1] := ECX; // 0 or $FFFFFFFF mov [edx+_2_], ecx // Result[2] := ECX; // 0 or $FFFFFFFF mov [edx+_3_], ecx // Result[3] := ECX; // 0 or $FFFFFFFF end; Comentários: * Observe o uso do "MOV ECX, 0" no lugar de "XOR ECX, ECX" para evitar alterar o estado do Flag de Sinal (SF) definido na instrução anterior (OR) e então usado no jump condicional que aparece na instrução seguinte (JNS). é claro que era desnecessário trocar a ordem das operações para isto. * Em vez de: or eax, eax jns @@not_negative os pares de instruções abaixo realizariam o mesmo: * and eax, eax // EAX mantém o valor, mas SF recebe o sinal jns @@not_negative // se SF = 0 então goto @@not_negative * test eax, $80000000 // somente zero se o bit de sinal (bit 31) é 0 jz @@not_negative // se ZF então goto @@not_negative * test eax, $87654321 // qualquer valor com o bit 31 definido jns @@not_negative // se SF = 0 então goto @@not_negative * cmp eax, 0 // compara eax com 0 jge @@not_negative // se maior ou igual então goto @@not_negative * Observe o uso de "DEC ECX" para alterar o valor de ECX de $00000000 para $FFFFFFFF (decrementando o valor do registro). "NOT ECX" faz a mesma coisa invertendo os bits, na mesma velocidade, e com o mesmo número de bytes para codificar a instrução, mas não é uma instrução par como o DEC. Por esta razão NOT é normalmente evitado e substituido por: - Se você sabe de antemão que o valor é zero, utilize DEC Dest - Se você sabe de antemão que o valor é 1, use INC Dest - Se você não conhece o valor, use XOR Dest, -1 * Também preste atenção na ordem das instruções para jamais utilizar um registro que foi definido por um instrução imediatamente anterior. Essa é uma das condições para que ocorra o pareamento. Você encontrará mais informações sobre instruções de pareamento nos documentos sobre otimização recomendados anteriormente. Podemos simplificar a função obrigando a instrução CDQ que estende o sinal de EAX para EDX. Veja o funcionamento (simplificado) de CDQ: if EAX >= 0 then EDX := $0 else EDX := $FFFFFFFF; Aqui é uma pequena e simples implementação usando CDQ: function ToHugeint(const x: Longint): Hugeint; overload; // Result := Hugeint(x); // Parâmetros: EAX = x; EDX = @Result; asm mov ecx, edx // ECX := @Result; cdq // EDX := IIF(x>=0, 0, $FFFFFFFF); mov [ecx+_0_], eax // Result[0] := x; mov [ecx+_1_], edx // Result[1] := EDX; // 0 or $FFFFFFFF mov [ecx+_2_], edx // Result[2] := EDX; // 0 or $FFFFFFFF mov [ecx+_3_], edx // Result[3] := EDX; // 0 or $FFFFFFFF end; CDQ é usualmente substituído usando MOV e SAR, que oferecem a vantagem de que a origem não precisa ser EAX e o destino não precisa ser EDX (mas são instruções pareadas). Vejamos um exemplo: function ToHugeint(const x: Longint): Hugeint; overload; // Result := Hugeint(x); // Parâmetros: EAX = x; EDX = @Result; asm mov ecx, eax // ECX := x; sar ecx, 31 // ECX := IIF(x>=0, 0, $FFFFFFFF); mov [edx+_0_], eax // Result[0] := x; mov [edx+_1_], ecx // Result[1] := EDX; // 0 or $FFFFFFFF mov [edx+_2_], ecx // Result[2] := EDX; // 0 or $FFFFFFFF mov [edx+_3_], ecx // Result[3] := EDX; // 0 or $FFFFFFFF end; Hugeint para Longint -------------------- Um Hugeint pode ser convertido para Longint simplesmente pegando os 32 bits de mais baixa ordem. Os 96 bits altos do Hugeint podem ser todos definidos para 0 ou 1 igualando o bit de sinal para que o resultado (bit 31) do Hugeint esteja dentro dos limites do Longint, mas a função não checa isto e executa a conversão cegamente (da mesma forma que um Longint é convertido para um Shortint, por exemplo). function ToLongint(const x: Hugeint): Longint; overload; // Result := Longint(x); // Nenhuma exceção é gerada se o valor não estiver dentro dos limites // (os 96 bits de mais alta ordem são descartados). // Parâmetros: EAX = @x; asm mov eax, [eax+_0_] // Result := x[0]; end; Int64 para Hugeint ------------------ Parâmetros Int64 são passados para a pilha; assim, funções com parâmetros Int64 automaticamente criam um quadro de pilha (stack frame). Os 64 bits mais baixos do resultado serão os 64 bits do parâmetro enquanto os 64 bits mais altos serão obtidos a partir do bit de sinal do inteiro (32 bits) de mais alta ordem do Int64. {$IFDEF DELPHI4} function ToHugeint(const x: Int64): Hugeint; overload; // Result := Hugeint(x); // Parâmetros: x na pilha; EAX = @Result; asm mov edx, dword[x+_0_] // EDX := x[0]; mov ecx, dword[x+_1_] // ECX := x[1]; mov [eax+_0_], edx // Result[0] := x[0]; mov [eax+_1_], ecx // Result[1] := x[1]; sar ecx, 31 // ECX := IIF(x[1]>=0, 0, $FFFFFFFF); mov [eax+_2_], ecx // Result[2] := ECX; // 0 or $FFFFFFFF mov [eax+_3_], ecx // Result[3] := ECX; // 0 or $FFFFFFFF end; {$ENDIF} Valores Int64 são armazenados no formato little-endian; assim, o inteiro inferior é o primeiro, com um deslocamento 0 do endereço base da variável e o inteiro superior é o segundo, com um deslocamento 4 do endereço base da variável. Nesse caso, o endereço base da variável é EBP+8 (veja o primeiro capítulo desta série de artigos) e, assim, o primeiro elemento está em EBP+8 (EBP+8+0) e o segundo elemento está em EBP+12 (EBP+8+4). Eu poderia usar EBP+8 e EBP+12 para endereçar estes elementos mas "x+_0_" e "x+_1_" referem-se aos endereços de forma mais transparente. O especificador de tamanho (DWORD) é já que o assembler recebe "x+_0_" e "x+_1_" como ponteiros para dados de 64 bits ("x" é considerado um ponteiro de dados de 64-bits) e não permite mover o valor referenciado para um registrador de 32-bits. Hugeint para Int64 ------------------ Um Hugeint pode ser convertido para um Int64 simplesmente pegando os 64 bits inferiores. Os 64 bits superiores do HugeInt podem ser definidos como 0 ou 1 para igualar o bit de sinal para que o resultado (bit 32) do valor Hugeint fique dentro dos limites de um Int64, mas a função não checa isto e executa a conversão cegamente: {$IFDEF DELPHI4} function ToInt64(const x: Hugeint): Int64; overload; // Result := Int64(x) // Nenhuma exceção é gerada se o valor não estiver dentro dos limites // (os 64 bits de mais alta ordem são descartados). // Parâmetros: EAX = @x; asm mov edx, [eax+_1_] // EDX := x[1]; mov eax, [eax+_0_] // EAX := x[0]; // Result = EDX:EAX = x[1]:x[0] end; {$ENDIF} Commentários: * Int64 retorna valores colocados em EDX (32 bits de alta ordem) e EAX (32 bits de baixa ordem). Por enquanto é isso. Nas próximas edições veremos funções que executam funções lógicas e matemáticas com inteiros gigantes. Share this post Link to post Share on other sites