antiblock
Rodnia | Alpha & Omega
  • Chatbox

    You don't have permission to chat.
    Load More
Sign in to follow this  
V¡®u§

Delphi com assembly (Parte 4)

1 post in this topic

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
antiblock
Rodnia | Alpha & Omega

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this