Social Icons

^^

segunda-feira, 15 de agosto de 2011

Delphi com assembly (Parte 4)

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.

Nenhum comentário:

Postar um comentário

Popular Posts

 

Seguidores

Hora exata:

Total de visualizações de página