#+title: 9 -- Conversão de strings numéricas para inteiros
#+author: Blau Araujo
#+email: cursos@blauaraujo.com

#+options: toc:3

* Objetivos

- Diferenciar as expressões numéricas em texto dos números que representam.
- Conhecer a relação entre tipos numéricos e tamanhos de dados.
- Criar sub-rotinas reaproveitáveis para conversões de caracteres para números.

* Todos os dados externos são recebidos como caracteres

Se consideramos como /dados externos/:

- Argumentos de linha de comando;
- Variáveis exportadas para o ambiente do processo;
- Dados digitados pelo usuário;
- Dados lidos por redirecionamentos e pipes;
- Dados lidos de arquivos em geral...

Todos eles têm em comum o fato de serem recebidos nos nossos programas
como cadeias de caracteres, mesmo que representem números. Consequentemente,
para utilizá-los em operações numéricas, será necessário convertê-los nos
valores que representam.

** Entendendo o problema

Para entendermos melhor o problema, vamos analisar o que acontece no programa
abaixo (=exemplo.c=) com o GDB.

Arquivo: [[exemplos/09/exemplo.c][exemplo.c]]

#+begin_src c :tangle exemplos/09/exemplo.c
#include <stdio.h>

int main(void) {

    int a = 123;
    char *b = "123";
    int *c = (int *)b; // Casting do valor no endereço 'b' para inteiro
        
    printf("Inteiro a: %d\n", a);
    printf("String  b: %s\n", b);
    printf("Inteiro c: %d\n", *c); // Imprime o valor no endereço 'c'
    
    return 0;
}
#+end_src

*Compilação e execução:*

#+begin_example
:~$ gcc -g exemplo.c
:~$ ./a.out
Inteiro a: 123
String  b: 123
Inteiro c: 3355185
#+end_example

Note que o ponteiro =c=, que recebeu endereço dos bytes da string no ponteiro
=b= (="123"=), aponta para um valor inteiro totalmente diferente do que está
representado pelos dígitos da string (o inteiro =3355185=).

*Abertura e execução com o GDB:*

Para examinar os conteúdo da memória em hexadecimal, nós vamos marcar a
unção =main= como ponto de parada, executar o programa e avançar a execução
em 3 linhas, para que as variáveis sejam inciadas, o nos levará ao ponto
anterior à chamada da função =printf=:

#+begin_example
:~$ gdb a.out
Reading symbols from a.out...
(gdb) break main
Breakpoint 1 at 0x1141: file exemplo.c, line 5.
(gdb) run
Starting program: /home/blau/git/pbn/curso/exemplos/09/a.out
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Breakpoint 1, main () at exemplo.c:5
warning: Source file is more recent than executable.
5	    int a = 123;
(gdb) next 3
9	    printf("Inteiro a: %d\n", a);
(gdb)
#+end_example

O que queremos observar é a diferença entre os valores numéricos dos três
dados na memória, como se todos eles fossem inteiros (formato =w= no GDB):

#+begin_example
(gdb) x /1wx &a
0x7fffffffdecc:	0x0000007b
(gdb) x /1wx b
0x555555556004:	0x00333231
(gdb) x /1wx c
0x555555556004:	0x00333231
#+end_example

Veja que os bytes da string apontada por 'b' são, como esperado, os mesmos
do inteiro apontado por 'c', mas ambos são totalmente diferentes do valor
em hexadecimal do inteiro em =a= (=123=).

** A ordem dos bytes

Nós também podemos examinar o conteúdo byte a byte desses dados a partir de
seus endereços iniciais:

#+begin_example
(gdb) x /4bx &a
0x7fffffffdecc:	0x7b	0x00	0x00	0x00
(gdb) x /4bx b
0x555555556004:	0x31	0x32	0x33	0x00
(gdb) x /4bx c
0x555555556004:	0x31	0x32	0x33	0x00
#+end_example

Isso ajuda a demonstrar que os bytes de inteiros, como os de qualquer outro
tipo diferente de =char=, são escritos em ordem inversa (/little endian/) na
memória. Portanto, quando os bytes da string foram interpretados como os
4 bytes de um inteiro, eles também foram invertidos:

#+begin_example
(gdb) x /4bx c
0x555555556004:	0x31	0x32	0x33	0x00
(gdb) x /1wx c
0x555555556004:	0x00333231
#+end_example

O tipo =char= é composto por apenas um byte e a ordem /little endian/ só afeta
a disposição de bytes: é por isso que somente os dados de tipos com dois ou
mais bytes são invertidos. Além disso, na montagem dos dados na memória,
o que importa é o tamanho de cada dado, não o que eles formam. Então, como
strings são formadas por cadeias de caracteres terminadas com o caractere
nulo (='\0'=), a ordem de seus bytes não é invertida.

** Dígitos na tabela ASCII

Os valores dos bytes da string ="123"= (além do terminador nulo ='\0'=, de valor
=0x00=) foram determinados pela convenção de representação de caracteres da
tabela ASCII:

| Caractere | Hexadecimal | Octal | Decimal |
|-----------+-------------+-------+---------|
| =\0=        |        0x00 |     0 |       0 |
| =0=         |        0x30 |   060 |      48 |
| =1=         |        0x31 |   061 |      49 |
| =2=         |        0x32 |   062 |      50 |
| =3=         |        0x33 |   063 |      51 |
| =4=         |        0x34 |   064 |      52 |
| =5=         |        0x35 |   065 |      53 |
| =6=         |        0x36 |   066 |      54 |
| =7=         |        0x37 |   067 |      55 |
| =8=         |        0x38 |   070 |      56 |
| =9=         |        0x39 |   071 |      57 |

Em comparação aos valores dos caracteres em outras bases, a representação em
hexadecimal é bastante conveniente, pois basta subtrair =0x30= para saber qual
é o dígito correspondente.

** Considerações sobre os tipos numéricos

Em baixo nível, nós trabalhamos diretamente com tamanhos de dados. Os tipos
das linguagens de alto nível, como a linguagem C, são apenas abstrações para
ajudar a definir o tamanho dos dados e as regras de seus usos. Sendo assim,
existe uma equivalência entre as formas de representar tamanhos de dados em
Assembly com os tipos, por exemplo, da linguagem C.

Considerando a arquitetura x86_64:

| Tipo em C | Tamanho | Tamanho em Assembly |
|-----------+---------+---------------------|
| =char=      | 1 byte  | /byte/                |
| =short=     | 2 bytes | /word/                |
| =int=     | 4 bytes | /double-word/         |
| =long=      | 8 bytes | /quad-word/           |
| =float=     | 4 bytes | /double-word/         |
| =double=    | 8 bytes | /quad-word/           |

#+begin_quote
Esses tamanhos são especificados na ABI do System V AM64, usada pelo Linux
em arquitetura x86_64 e garantidos, na prática, pelo GCC e em sistemas
baseados na =glibc=.
#+end_quote

Em Assembly, portanto, definir uma lista de /double-words/ (=dd=) tem o mesmo
efeito de definir um vetor de inteiros na linguagem C, inclusive na ordem
em que os bytes são dispostos na memória. Ou então, o dado em um registrador
de 64 bits, se tomado como um todo, terá o tamanho de uma /quad-word/ e será
equivalente ao tipo =long= da linguagem C.

** Pesos posicionais

Falando apenas de inteiros sem sinal por enquanto, cada byte de uma string
numérica decimal representa um algarismo do número multiplicado pelo seu
/peso posicional/, por exemplo:

#+begin_example
0x31 0x32 0x33  => '1' '2' '3'

0x31 - 0x30 * 100 = 100 (centenas)
0x32 - 0x30 * 10  =  20 (dezenas)
0x33 - 0x30 * 1   =   3 (unidades)

100 + 20 + 3 = 123
#+end_example

Manualmente, este é um procedimento de conversão bastante simples, mas a sua
implementação em uma rotina de baixo nível não é tão intuitiva, embora também
não seja nada muito complicado. O /"pulo do gato"/ está em alcançar os pesos
posicionais de cada algarismo progressivamente:

#+begin_example
031 0x32 033 => '1' '2' '3'

val = 0x31 - 0x30 = 1
val = (val * 10) + (0x32 - 0x30) = 10 + 2 = 12 
val = (val * 10) + (0x33 - 0x30) = 120 + 3 = 123
#+end_example

Ou, de uma forma mais regular:

#+begin_example
val = 0
val = (val * 10) + (0x31 - 0x30) =   0 + 1 = 1
val = (val * 10) + (0x32 - 0x30) =  10 + 2 = 12 
val = (val * 10) + (0x33 - 0x30) = 120 + 3 = 123
#+end_example

Esse procedimento, facilmente implementável em Assembly, contempla tudo que
vimos sobre o problema:

- Percorre os bytes da string na ordem em que estão na memória;
- Converte os dígitos ASCII para os valores que representam;
- Aplica os pesos posicionais corretos a cada algarismo encontrado.

Com isso, nós já podemos escrever uma rotina de conversão para strings que
representam números decimais sem sinal de todos os tipos compatíveis com
=int= (=char=, =short= e =long=, por exemplo).

* Conversão para inteiros sem sinal em alto nível

Em linguagem C, sem utilizar as funções especializadas da biblioteca padrão
e com base no procedimento que elaboramos, nós poderíamos implementar uma
função de conversão para inteiros sem sinal deste modo:

#+begin_src c
unsigned int str_to_uint(char *str) {
    int dig;               // Recebe o dígito convertido
    unsigned int conv = 0; // Recebe a parcial da conversão
    
    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] < '0' || str[i] > '9') break;
        dig = str[i] - '0'; 
        conv = (conv * 10) + dig;
    }
    return conv;
}
#+end_src

Embora funcional para a maioria dos casos, essa abordagem tem alguns problemas:

- Não verifica se o valor convertido excede o limite máximo para inteiros sem
  sinal da plataforma;
- Não verifica se o ponteiro para a string é nulo (=NULL=);
- Retorna =0= tanto para a conversão da string ="0"= quanto para uma string sem
  dígitos nos primeiros caracteres.

Todos esses problemas poderiam ser solucionados com verificações e o retorno
de um valor de erro: mas que valor seria esse? Tipicamente, utilizaríamos =-1=,
mas o retorno da função tem que ser =unsigned=. Também poderíamos sacrificar um
número válido, como o valor do próprio limite máximo de inteiros sem sinal,
definido na =glibc= em =UINT_MAX=, no cabeçalho =limits.h=, mas isso requereria
uma nota sobre essa limitação.

Uma terceira opção, que me parece bem mais razoável, seria incluir um segundo
parâmetro para receber o estado de término da função:

#+begin_src c
unsigned int str_to_uint(char *str, int *err);
#+end_src

Deste modo, a função poderia ser utilizada assim:

#+begin_src c
char *str_num = "123";   // String a ser convertida.
int status;              // Recebe o estado de término da função.

unsigned int num = str_to_uint(str_num, &status);
if (!status) ...;        // Consequências do erro...
#+end_src

Para os casos de uso onde o tratamento de erros não for importante, nós
podemos dar a opção de passar =NULL= como argumento de =*err= e trabalhar a
implementação para definir um estado padrão =0= (erro), condicionado ao
ponteiro recebido, e alterá-lo para =1= somente antes de terminar com
sucesso:

#+begin_src c
unsigned int str_to_uint(char *str, int *err /* nullable */) {
    // Inicia a função com estado de erro, mas só se '*err' não for NULL...
    if (err) *err = 0;

    // Outras verificações e rotina de conversão...

    // Altera o estado antes de terminar com sucesso (1)...
    if (err) *err = 1;
    return conv;
}
#+end_src

Assim, caso =*err= seja =NULL=, nenhum estado de término será definido.

** Erro de ponteiro nulo

Caso o endereço da string (=*str=) seja passada como um ponteiro nulo, nós
simplesmente terminaremos a função com retorno =0= sem alterar o valor de
=*err=, que também é =0= (erro):

#+begin_src c
// Inicia a função com estado de erro, mas só se '*err' não for NULL...
if (err) *err = 0;

// Termina com erro (0) e valor 0 se str==NULL...
if (str == NULL) return 0;
#+end_src

** Erro de byte inicial fora faixa de dígitos

Apesar de ser uma verificação redundante, por ser repetida mais adiante no
código, ela é necessária para determinar quando a função retorna =0= por ter
convertido apenas uma string ="0"= ou devido a não haver dígitos para converter
no início da string, ou seja:

#+begin_example
String: "abc123" --> Converte para 0 com estado 1
String: ""       --> Converte para 0 com estado 1
String: "0"      --> Converte para 0 com estado 1
Erros            --> Retornam conversão para 0, mas com estado 0
#+end_example

A ideia é que os dois primeiros casos (="abc123"= e =""=) retornem =0= om estado
de término =0= (erro), portanto...

#+begin_src c
// Inicia a função com estado de erro, mas só se '*err' não for NULL...
if (err) *err = 0;

// Termina com erro (0) e valor 0 se str==NULL...
if (str == NULL) return 0;

// Termina com erro (0) e valor 0 se primeiro byte não for um dígito...
if (str[0] < '0' || str[0] > '9') return 0;
#+end_src

Nós podemos, inclusive, combinar as duas verificações numa só:

#+begin_src c
// Inicia a função com estado de erro, mas só se '*err' não for NULL...
if (err) *err = 0;

// Termina com erro (0) e valor 0 se str==NULL
// ou se o primeiro byte não for um dígito...
if (str == NULL || str[0] < '0' || str[0] > '9') return 0;
#+end_src

** Erro de estouro do limite do tipo

Nós podemos utilizar o valor de =UINT_MAX= como referência para determinar se
o próximo valor parcial do ciclo de conversões excederá ou não o limite
máximo para números inteiros sem sinal. A cada ciclo, a conversão é feita
com:

#+begin_example
valor = (valor * 10) + dígito;
#+end_example

Para determinar se isso excederá o valor de =UNIT_MAX=, basta calcular qual
seria o valor corrente máximo para que a próxima conversão resulte em algo
dentro do limite:

#+begin_example
valor * 10 + dígito < UINT_MAX
valor * 10 < UINT_MAX - dígito
valor < (UINT_MAX - dígito) / 10
#+end_example

No código, isso pode ser escrito no loop de conversão como:

#+begin_src c
// Converte o dígito corrente...
dig = str[i] - '0';
    
// Termina com erro e valor 0 se a próxima conversão exceder UINT_MAX...
if (conv > (UINT_MAX - dig) / 10) return 0;

// Processa a parcial da conversão...
conv = (conv * 10) + dig;
#+end_src

** Implementação final em C

Aqui está a implementação final, com as verificações e os procedimentos
atualizados:

#+begin_src c
#include <limits.h> // Requerido para obter UINT_MAX da plataforma

unsigned int str_to_uint(char *str, int *err /* nullable */) {

    if (err) *err = 0;  // Estado padrão é de erro (0 = falso)!
    
    // Termina com erro e valor 0 se str==NULL ou se '0'>str[0]>'9'...
    if (str == NULL || str[0] < '0' || str[0] > '9') return 0;
   
    int dig;               // Recebe o dígito convertido
    unsigned int conv = 0; // Recebe a parcial da conversão
    
    for (int i = 0; str[i] != '\0'; i++) {
        // Se o caractere não for um dígito, termina a conversão...
        if (str[i] < '0' || str[i] > '9') break;
        
        // Converte o dígito corrente...
        dig = str[i] - '0';
        
        // Termina com erro e valor 0 se a próxima conversão exceder UINT_MAX...
        if (conv > (UINT_MAX - dig) / 10) return 0;

        // Processa a parcial da conversão...
        conv = (conv * 10) + dig;
    }
    
    if (err) *err = 1;  // Altera estado para sucesso (1 = verdadeiro)
    return conv;
}
#+end_src

** Exemplo de uso

Arquivo: [[exemplos/09/uint.c][uint.c]]

#+begin_src c :tangle exemplos/09/uint.c
/*
 * Arquivo   : uint.c
 * Compilação: gcc -Wall uint.c -o uintc
 */
#include <stdio.h>
#include <limits.h> // Requerido para obter UINT_MAX da plataforma

unsigned int str_to_uint(char *str, int *err /* nullable */);

int main(int argc, char **argv) {
    if (argc == 1) {
        fprintf(stderr, "Uso: %s NÚMERO\n", argv[0]);
        return 1;
    }

    int status;
    unsigned int num = str_to_uint(argv[1], &status);

    if (status) {
        printf("String: %s\nNúmero: %u\n", argv[1], num);
    } else {
        fprintf(stderr, "Erro de conversão!\n");
        return 1;
    }

    return 0;
}

unsigned int str_to_uint(char *str, int *err /* nullable */) {
    if (err) *err = 0;  // Estado padrão é de erro (0 = falso)!
    
    // Termina com erro e valor 0 se str==NULL ou se '0'>str[0]>'9'...
    if (str == NULL || str[0] < '0' || str[0] > '9') return 0;
   
    int dig;               // Recebe o dígito convertido
    unsigned int conv = 0; // Recebe a parcial da conversão
    
    for (int i = 0; str[i] != '\0'; i++) {
        // Se o caractere não for um dígito, termina a conversão...
        if (str[i] < '0' || str[i] > '9') break;
        // Converte o dígito corrente...
        dig = str[i] - '0';
        // Termina com erro e valor 0 se a próxima conversão exceder UINT_MAX...
        if (conv > (UINT_MAX - dig) / 10) return 0;
        // Processa a parcial da conversão...
        conv = (conv * 10) + dig;
    }
    
    if (err) *err = 1;  // Altera estado para sucesso (1 = verdadeiro)
    return conv;
}
#+end_src

Compilação e testes:

#+begin_example
:~$ gcc -Wall uint.c -o uintc
$ ./uintc
Uso: ./uintc NÚMERO
:~$ ./uintc 123
String: 123
Número: 123
:~$ ./uintc 123abc
String: 123abc
Número: 123
:~$ ./uintc $((2**32))
Erro de conversão!
:~$ ./uintc $((2**32 - 1))
String: 4294967295
Número: 4294967295
:~$ ./uintc ''
Erro de conversão!
:~$ ./uintc abc
Erro de conversão!
#+end_example

* Conversão para inteiros sem sinal em baixo nível

Em Assembly, o procedimento de conversão ainda é o mesmo:

#+begin_example
val = 0
val = (val * 10) + (0x31 - 0x30) =   0 + 1 = 1
val = (val * 10) + (0x32 - 0x30) =  10 + 2 = 12 
val = (val * 10) + (0x33 - 0x30) = 120 + 3 = 123
#+end_example

Que pode ser implementado, de forma genérica, com uma sub-rotina assim:

#+begin_src asm
_str_to_uitn:
    ; ------------------------------------------------------
    ; Entrada: RSI = Endereço da string (char * str)
    ; Saída  : RAX = Valor convertido (unsigned int)
    ; ------------------------------------------------------
    ; Preparação...
    ; ------------------------------------------------------
    push rbx              ; Salva conteúdo de rbx
    xor rax, rax          ; rax = 0 (acumula a conversão)
    xor rbx, rbx          ; rbx = 0 (recebe os caracteres no loop)
    ; ------------------------------------------------------
.conv_loop:
    ; ------------------------------------------------------
    ; Condições de término do loop...
    ; ------------------------------------------------------
    mov bl, [rsi]         ; Lê o primeiro byte
    test bl, bl           ; Compara primeiro byte com o terminador '\0'
    je .done              ; Se 0x00, termina o loop
    cmp bl, 0x30          ; Compara primeiro byte com '0'
    jl .done              ; Se menor, termina o loop
    cmp bl, 0x39          ; Compara primeiro byte com '9'
    jg .done              ; Se maior, termina o loop
    ; ------------------------------------------------------
    ; Conversão...
    ; ------------------------------------------------------
    sub rbx, 0x30         ; Subtrai '0' do byte (dígito convertido)
    imul rax, rax, 10     ; rax *= 10 (deslocamento do peso posicional)
    add rax, rbx          ; rax += dígito convertido
    inc rsi               ; Avança rdi para o próximo byte
    jmp .conv_loop        ; Volta ao início do loop de conversão
    ; ------------------------------------------------------
.done:
    ; ------------------------------------------------------
    pop rbx               ; Restaura rbx
    ret
#+end_src

Isso equivale à primeira versão da função em C e traz os mesmos problemas:

- Não verifica se o valor convertido excede o limite máximo para inteiros sem
  sinal da plataforma;
- Não verifica se o ponteiro para a string é nulo (=NULL=);
- Retorna =0= tanto para a conversão da string ="0"= quanto para uma string sem
  dígitos nos primeiros caracteres.

Além disso, se quisermos adaptar a sub-rotina para uso em um programa em C
(em um objeto compartilhado, por exemplo) ela precisa seguir as convenções
da ABI. Do jeito que está, ela já poderia ser utilizada, porque recebe o
primeiro argumento em =rdi= e retorna o valor convertido em =rax=, mas ainda
precisamos decidir como implementar a sinalização de erros. Na função em C,
isso é feito com um ponteiro opcional (/nullable/) para a variável que receberá
o estado de erro:

#+begin_src c
unsigned int str_to_uint(char *str, int *err /* nullable */);
#+end_src

A ABI determina que o segundo argumento deve ser recebido em =rdx=, então a
assinatura da sub-rotina passaria a ser:

#+begin_src asm
_str_to_uitn:
    ; ------------------------------------------------------
    ; Entrada:
    ;     RSI = Endereço da string (char * str)
    ;     RDX = Endereço da variável de erro (int *err)
    ; Saída  :
    ;     RAX = Valor convertido (unsigned int)
    ;     Se sucesso: *err = 1 (verdadeiro)
    ;     Se erro   : *err = 0 (falso)
    ; ------------------------------------------------------
#+end_src

Ainda na função em C, nós decidimos definir o estado de =*err= logo no início
e só alterá-lo antes do retorno com sucesso. Como o argumento pode receber
um ponteiro nulo (=NULL=), o estado de término foi definido condicionalmente:

#+begin_src c
if (err) *err = 0;  // Estado padrão é de erro (0 = falso)!
// ...
if (err) *err = 1;  // Altera estado para sucesso (1 = verdadeiro)
return conv;
#+end_src

Além disso, sempre que a função terminava com erro, o valor retornado era
definido com =0=, e isso também deve ser implementado na sub-rotina:

#+begin_src asm
_str_to_uitn:
    ; ------------------------------------------------------
    ; Entrada:
    ;     RSI = Endereço da string (char * str)
    ;     RDX = Endereço da variável de erro (int *err /* nullable */)
    ; Saída  :
    ;     RAX = Valor convertido (unsigned int)
    ;     Se sucesso: *err = 1 (verdadeiro)
    ;     Se erro   : *err = 0 (falso)
    ; ------------------------------------------------------
    ; Definição condicional do estado inicial de erro...
    ; ------------------------------------------------------
    test rdx, rdx         ; Se *err = NULL, rdx = 0
    jz .skip_error        ; Se for 0, pula a definição do erro
    mov dword [rdx], 0    ; *err = 0 => estado inicial é de erro (falso)
    ; ------------------------------------------------------
.skip_error:
    ; ------------------------------------------------------

    ; ...

    ; ------------------------------------------------------
.error:
    ; ------------------------------------------------------
    xor rax, rax          ; Retorna 0 em caso de erro
    jmp .done
    ; ------------------------------------------------------
.success:
    ; ------------------------------------------------------
    ; Redefinição condicional do estado final de sucesso...
    ; ------------------------------------------------------
    test rdx, rdx         ; Se *err = NULL, rdx = 0
    jz .done              ; Se for 0, pula a definição de sucesso
    mov dword [rdx], 1    ; *err = 1 => estado final é de sucesso (verdadeiro)
    ; ------------------------------------------------------
.done:
    ; ------------------------------------------------------
    pop rbx               ; Restaura rbx
    ret
#+end_src

Com o procedimento de tratamento de erros definido, nós podemos prosseguir
com a implementação das validações necessárias.

** Erro de ponteiro nulo

A primeira verificação que faremos é para o caso de =rsi= ter recebido um
ponteiro nulo na chamada:

#+begin_src asm
    ; ------------------------------------------------------
    ; Teste de ponteiro nulo...
    ; ------------------------------------------------------
    test rsi, rsi      ; verifica se enderçeo é nulo (0)
    jz .error          ; se for, termina retornando -1 (erro)
#+end_src

Deste modo, se =rsi= receber =0= (=NULL=, numa chamada em C), a sub-rotina salta
para o rótulo local =.error= e termina retornando =0= em =rax= e =1= no endereço
em =rdx=, se =*err= estiver definido.

** Erro de byte inicial fora da faixa de dígitos

Para que o primeiro byte seja verificado, ele precisa ser lido. Portanto,
a verificação da faixa de dígitos deve ser feita logo após a preparação
dos registradores utilizados, antes do /loop/ de conversão:

#+begin_src asm
    ; ------------------------------------------------------
    ; Preparação...
    ; ------------------------------------------------------
    push rbx           ; salva rbx na pilha
    xor rax, rax       ; rax = 0 (acumula o resultado)
    xor rbx, rbx       ; rbx = 0 (recebe os caracteres no loop)
    mov bl, [rsi]      ; lê o primeiro byte
    ; ------------------------------------------------------
    ; Validação do primeiro byte...
    ; ------------------------------------------------------
    cmp bl, 0x30       ; compara com menor byte válido
    jl .error          ; se menor, termina retornando -1
    cmp bl, 0x39       ; compara com maior byte válido
    jg .error          ; se maior, termina retornando -1
#+end_src

Assim, a sub-rotina salta para =.error= se o byte for menor que =0x30= (caractere
='0'=) ou maior que =0x39= (caractere ='9'=). 

** Erro de estouro do limite do tipo

Como vimos, o cálculo do maior valor que pode ser multiplicado por 10 na
conversão é feito com:

#+begin_example
(UINT_MAX - dígito) / 10
#+end_example

Contudo, essa verificação é um pouco mais complicada em Assembly, por alguns
motivos:

- Nós não temos um limite definido para a plataforma, como a constante
  simbólica =UINT_MAX=, da =glibc=.
- É possível definir =UINT_MAX= com uma macro no Assembly, mas não podemos
  contar com isso no caso de reutilização da sub-rotina, a menos que ela
  esteja em uma biblioteca que também contenha definições de macros.
- Também teremos que utilizar registradores auxiliares adicionais, porque,
  numa divisão, =rax= recebe o quociente e =rdx= o resto, e ambos estão em
  uso.

Mas /"complicada"/ não é /"impossível"/, e nós podemos assumir alguns critérios:

- A ABI define que inteiros terão 4 bytes (32 bits) em arquiteturas x86_64
  e as implementações da linguagem C no GCC e na Glibc garantem isso.
- O valor de =UINT_MAX= pode ser armazenado em =rcx= como =0xffffffff=, o maior
  número sem sinal que pode ser escrito com 4 bytes.
- Os registradores =r8= e =r10= podem ser usados para salvar e restaurar os
  dados em =rax= e =rdx=.
- O registrador =r9= pode ser usado para auxiliar nos cálculos.

Portanto, esta é uma implementação possível:

#+begin_src asm
; ------------------------------------------------------
; Limite válido: conv < (UINT_MAX - dígito) / 10
; ------------------------------------------------------
mov r8, rax           ; Salva parcial da conversão em r8
mov r10, rdx          ; Salva ponteiro de erro em r10

mov eax, -1           ; rax = 0x00000000ffffffff (UINT_MAX)
sub eax, ebx          ; rax = UINT_MAX - dígito (dividendo)

xor rdx, rdx          ; prepara rdx para receber o resto da divisão
mov r9, 10            ; divisor
div r9                ; limite(rax) = (UINT_MAX - dígito) / 10

cmp r8, rax           ; se parcial > limite, teremos um estouro
jg .error             ; se maior, termina com erro
	
mov rdx, r10          ; restaura rdx (pontiero para erros)
mov rax, r8           ; restaura rax (parcial da conversão)
#+end_src

** Implementação final em Assembly

Com alguns ajustes estéticos e na documentação, aqui está a implementação
completa...

Arquivo: [[exemplos/09/uint.asm][uint.asm]]

#+begin_src asm :tangle exemplos/09/uint.asm
; ----------------------------------------------------------
; Arquivo : uint.asm
; Montagem: nasm -g -f elf64 uint.asm
; Ligação : ls uint.o -o uint
; ----------------------------------------------------------
section .data
; ----------------------------------------------------------
    num_str db "123", 0   ; string numérica
; ----------------------------------------------------------
section .bss
; ----------------------------------------------------------
    num resd 1            ; 4 bytes para o valor UINT32
    status resd 1         ; 4 bytes para o estado de término
; ----------------------------------------------------------
section .text
global _start
; ----------------------------------------------------------
_start:
; ----------------------------------------------------------
; Teste de chamada (verificar com o GDB)...
; ----------------------------------------------------------
    mov rsi, num_str      ; copia endereço da string em rsi
    mov rdx, status       ; copia o endereço do estado de erro em rdx
    call _str_to_uint     ; chama a sub-rotina de conversão
    mov dword [num], eax  ; copia o resultado como int para [num]
; ----------------------------------------------------------
_exit:
; ----------------------------------------------------------
    mov rax, 60
    mov rdi, 0
    syscall
; ----------------------------------------------------------
; Sub-rotinas...
; ----------------------------------------------------------
_str_to_uint:
; ----------------------------------------------------------
; Converte string numérica em inteiro sem sinal (uint32_t).
; Entradas:
;   RSI = Endereço da string (char *str)
;   RDX = Endereço para estado de erro (int *err /* nullable */)
; Saída:
;   RAX = valor convertido (uint32_t) ou 0, no caso de erro
;   Sucesso: *rdx = 1
;   Erro:    *rdx = 0
; ----------------------------------------------------------
    ; Definição condicional do estado inicial de erro...
    ; ------------------------------------------------------
    test rdx, rdx         ; Se *err = NULL, rdx = 0
    jz .skip_error        ; Se for 0, pula a definição do erro
    mov dword [rdx], 0    ; *err = 0 => estado inicial é de erro (falso)
    ; ------------------------------------------------------
.skip_error:
    ; ------------------------------------------------------
    ; Teste de ponteiro nulo...
    ; ------------------------------------------------------
    test rsi, rsi         ; verifica se enderçeo é nulo (0)
    jz .error             ; se for, termina retornando -1 (erro)
    ; ------------------------------------------------------
    ; Preparação...
    ; ------------------------------------------------------
    push rbx              ; salva rbx na pilha
    xor rax, rax          ; rax = 0 (acumula o resultado)
    xor rbx, rbx          ; rbx = 0 (recebe os caracteres no loop)
    mov bl, [rsi]         ; lê o primeiro byte
    ; ------------------------------------------------------
    ; Validação do primeiro byte...
    ; ------------------------------------------------------
    cmp bl, 0x30          ; compara com menor byte válido
    jl .error             ; se menor, termina retornando -1
    cmp bl, 0x39          ; compara com maior byte válido
    jg .error             ; se maior, termina retornando -1
.conv_loop:
    ; ------------------------------------------------------
    ; Condições de término da conversão ...
    ; ------------------------------------------------------
    test bl, bl           ; verifica se o byte é o terminador 0x00
    je .success           ; se for, termina com sucesso
    cmp bl, 0x30          ; compara o byte em rbx com o menor dígito
    jl .success           ; se for menor, termina com sucesso
    cmp bl, 0x39          ; compara o byte em rbx com o maior dígito
    jg .success           ; se for maior, termina com sucesso
    ; ------------------------------------------------------
    ; Conversão do dígito corrente...
    ; ------------------------------------------------------
    sub rbx, 0x30         ; converte o dígito para seu valor numérico
    ; ------------------------------------------------------
    ; Limite válido: conv < (UINT_MAX - dígito) / 10
    ; ------------------------------------------------------
    mov r8, rax           ; Salva parcial da conversão em r8
    mov r10, rdx          ; Salva ponteiro de erro em r10
    
    mov eax, -1           ; eax = 0xffffffff (UINT_MAX - 32 bits)
    sub eax, ebx          ; rax = UINT_MAX - dígito (dividendo)
    
    xor rdx, rdx          ; prepara rdx para receber o resto da divisão
    mov r9, 10            ; divisor
    div r9                ; limite(rax) = (UINT_MAX - dígito) / 10
    
    cmp r8, rax           ; se parcial > limite, teremos um estouro
    jg .error             ; se maior, termina com erro
    	
    mov rdx, r10          ; restaura rdx (pontiero para erros)
    mov rax, r8           ; restaura rax (parcial da conversão)
    ; ------------------------------------------------------
    ; Processa a parcial da conversão...
    ; ------------------------------------------------------
    imul rax, rax, 10     ; rax *= 10 (deslocamento do peso posicional)
    add rax, rbx          ; rax += novo algarismo
    inc rsi               ; avança para o próximo byte
    mov bl, [rsi]         ; carrega o dígito corrente em rbx
    jmp .conv_loop
    ; ------------------------------------------------------
.error:
    ; ------------------------------------------------------
    xor rax, rax          ; Retorna 0 em caso de erro
    jmp .done
    ; ------------------------------------------------------
.success:
    ; ------------------------------------------------------
    ; Redefinição condicional do estado final de sucesso...
    ; ------------------------------------------------------
    test rdx, rdx         ; Se *err = NULL, rdx = 0
    jz .done              ; Se for 0, pula a definição de sucesso
    mov dword [rdx], 1    ; *err = 1 => estado final é de sucesso (verdadeiro)
    ; ------------------------------------------------------
.done:
    ; ------------------------------------------------------
    pop rbx               ; Restaura rbx
    ret
#+end_src

** Teste com o GDB

Nosso objetivo é testar se a string em =num_str= é convertida corretamente
pela análise dos valores em =rax= e =rdx= (=status=) após a chamada da sub-rotina
neste trecho do programa:

#+begin_src asm
; ----------------------------------------------------------
section .data
; ----------------------------------------------------------
    num_str db "123", 0   ; string numérica
; ----------------------------------------------------------
section .bss
; ----------------------------------------------------------
    num resd 1            ; 4 bytes para o valor UINT32
    status resd 1         ; 4 bytes para o estado de término
; ----------------------------------------------------------
section .text
global _start
; ----------------------------------------------------------
_start:
; ----------------------------------------------------------
; Teste de chamada (verificar com o GDB)...
; ----------------------------------------------------------
    mov rsi, num_str      ; copia endereço da string em rsi
    mov rdx, status       ; copia o endereço do estado de erro em rdx
    call _str_to_uint     ; chama a sub-rotina de conversão
    mov dword [num], eax  ; copia o resultado como int para [num]
#+end_src

*Montagem e execução no GDB:*

#+begin_example
:~$ nasm -g -f elf64 uint.asm
:~$ ld uint.o -o uint
:~$ gdb ./uint
Reading symbols from ./uint...
(gdb) break _start
Breakpoint 1 at 0x401000: file uint.asm, line 22.
(gdb) run
Starting program: /home/blau/git/pbn/curso/exemplos/09/uint

Breakpoint 1, _start () at uint.asm:22
22	    mov rsi, num_str      ; copia endereço da string em rsi
(gdb)
#+end_example

*Execução e verificações antes da chamada:*

#+begin_example
(gdb) n 2
24	    call _str_to_uint     ; chama a sub-rotina de conversão
(gdb) info registers rax rdx rsi
rax            0x0                 0
rdx            0x402008            4202504
rsi            0x402000            4202496
(gdb) x /1wx &num_str
0x402000 <num_str>:	0x00333231
(gdb) x /1s &num_str
0x402000 <num_str>:	"123"
(gdb) x /1wx &num_
No symbol "num_" in current context.
(gdb) x /1wx &num
0x402004 <num>:	0x00000000
(gdb) x /1wx &status
0x402008 <status>:	0x00000000
#+end_example

*Execução e verificações após a chamada:*

#+begin_example
(gdb) n
25	    mov dword [num], eax  ; copia o resultado para [num]
(gdb) n
_exit () at uint.asm:29
29	    mov rax, 60
(gdb) info registers rax rdx rsi
rax            0x7b                123
rdx            0x402008            4202504
rsi            0x402003            4202499
(gdb) x /1wx &num
0x402004 <num>:	0x0000007b
(gdb) print (int)num
$1 = 123
(gdb) x /1wx &status
0x402008 <status>:	0x00000001
#+end_example

* Conversão para inteiros com sinal

No Assembly x86_64, números com sinal são representados usando o método do
/complemento de dois/. Tomando um inteiro de 32 bits como exemplo, se o bit
mais significativo (MSB, o bit mais a esquerda) for =0=, o número é interpretado
como positivo ou zero; se for =1=, o número é negativo. Em outras palavras, o
bit mais a esquerda de um número é o seu sinal.

O complemento de dois de um número binário é obtido pela inversão de todos
os seus bits (com uma operação =NOT= bit a bit) seguida da soma de 1:

#+begin_example
       00000000 00000000 00000000 00000101 =  5  (0x0005)
NOT -> 11111111 11111111 11111111 11111010 = -6  (0xFFFA)
 +1 -> 11111111 11111111 11111111 11111011 = -5  (0xFFFB)
#+end_example

** Interpretação do sinal

Se o MSB de um número for =1=, o que acontecerá sempre que o byte (não bit)
mais significativo de seu valor em hexadecimal iniciar com =8= ou mais, o
número poderá ser interpretado como negativo ou positivo -- tudo depende
do contexto. Por exemplo, o número 2.147.483.648, se escrito com 4 bytes
em hexa, será =0x80000000= e seu equivalente binário será:

#+begin_example
10000000 00000000 00000000 00000000 = 0x80 00 00 00 = 2.147.483.648
#+end_example

Digamos que esse número seja escrito em =edx= (32 bits) e seja utilizado em
uma chamada de função que espera um argumento inteiro sem sinal. Neste caso,
o valor será tomado como positivo, mesmo que o binário inicie com =1=. Porém,
considere esta situação:

#+begin_src asm
mov eax, 0x80000000
cmp eax, 0
#+end_src

A instrução =cmp= calcula =eax - 0= e configura as flags de acordo com o valor
em =eax= e o resultado da operação:

- Flag =SF=: foi definida com =1= porque o MSB do resultado é =1= (negativo).
- Flag =OF=: como não houve /overflow/ na operação, seu valor foi definido como =0=.
- Flag =CF=: como a operação não provocou um "vai um" ou um empréstimo fora
  do limite representável em 32 bits (capacidade de =eax=), seu valor foi
  definido como =0=.

Neste ponto, a interpretação do sinal do valor em =eax= vai depender do que
faremos com o resultado da comparação. Observe esta possibilidade:

#+begin_src asm
	mov eax, 0x80000000
	cmp eax, 0  ; resulta 0x80000000 -> SF=1 e OF=0
	jl .menor   ; Se SF != OF, o salto acontece
	; ...
.menor:
	; ...
#+end_src

A instrução =jl= (/jump if less/) avalia se as flags =SF= e =OF= são diferentes: se
forem, o salto é feito. Portanto, =jl= levaria em conta o sinal do resultado
da subtração e salto aconteceria porque =eax < 0=. Mas, e neste caso?

#+begin_src asm
	mov eax, 0x80000000
	cmp eax, 0  ; resulta 0x80000000 -> SF=1 e OF=0
	jb .menor   ; Se CF = 1, o salto acontece
	; ...
.menor:
	; ...
#+end_src

Já a instrução =jb= (/jump if below/) só salta se =CF=1=, mas o resultado da
subtração (=eax-0=) não provocou um "vai um" ou um empréstimo fora do limite
do registrador: portanto, seu valor será =0= e o salto não acontecerá. Isso
significa que, como =jb= não leva em conta o sinal, =0x80000000= foi interpretado
como um valor acima de zero.

Por outro lado, se utilizássemos =rax= em vez de =eax=...

#+begin_src asm
	mov rax, 0x80000000 ; 0x0000000080000000
	cmp rax, 0          ; CF=0 SF=0 e OF=0
	jb .menor           ; CF=0, não salta
	jl .menor           ; SF=OF, não salta
	; ...
.menor:
	; ...
#+end_src

Desta forma, não há ambiguidades quanto à interpretação do sinal.

** Uma nota sobre as flags

É importante entender corretamente o conceito por detrás da /carry flag/,
porque, em operações sem sinal, é ela que indica se um número é menor do
que outro.

Então, vejamos: =10= é menor do que =14=?

#+begin_src asm
mov al, 10  ; 10 = 1010 = 0x0A
cmp al, 14  ; 14 = 1110 = 0xFE
#+end_src

A instrução =cmp= fará a subtração...

#+begin_example
   Aqui, temos que fazer um empréstimo e o MSB de 10 será 0...
   ↓
  1010
- 1110
------
    00

  Agora é o MSB que requer um empréstimo!
  ↓
  0110
- 1110
------
  ?100
#+end_example

Numa situação desas, onde não há mais de onde emprestar um bit =1= mais a
esquerda, o processador efetua a subtração, como se houvesse de onde tirar
o bit 1 de que precisa, sobe a flag =CF= (indicando que houve um empréstimo
fora do limite dos operandos) e a flag =SF= (indicando que o resultado é
negativo). Ao mesmo tempo, =OF= e =ZF= receberiam =0=, porque não houve estouro
do limite do valor representável com sinal e o resultado não foi zero.

Na operação acima, nós teríamos:

#+begin_example
  CF=1
  ↓
 (1)0110
  - 1110
  ------
    1100 = -4 ← ZF=0 (não é zero)
    ↑
    SF=1
    OF=0 (é possível escrever em 4 bits)
#+end_example

#+begin_quote
O processador não possui circuitos capazes de efetuar subtrações e, por isso,
não executaria a operação desta forma, e sim calculando o complemento de dois
de =-14= (=0010=) para, em seguida, somar com =10=: ~1010+0010 = 1100 (-4)~.
#+end_quote

** Limites de inteiros com sinal

Assumindo que inteiros são escritos com 4 bytes, o maior valor absoluto
que podemos representar ainda é =0xFFFFFFFF=, mas ele teria que ser visto
como um número negativo. Calculando seu complemento de dois...

#+begin_example
       11111111 11111111 11111111 11111111 (0xFFFFFFFF)
NOT -> 00000000 00000000 00000000 00000000
 +1 -> 00000000 00000000 00000000 00000001 => (1)
#+end_example

Portanto, levando em conta o sinal, =0xFFFFFFFF= é =-1=.

Como o bit mais significativo representa o sinal, o primeiro dígito do byte
mais significativo do maior número positivo que pode ser escrito em hexa tem
que ser =7=:

#+begin_example
Maior byte positivo: 0x7f = 0111 1111 = 127
#+end_example

Se somarmos =1= a =0x7F=, nós chegaremos a =0x80= (128), que será interpretado como
um número negativo: 

#+begin_example
0x7F -> 0111 1111
  +1 -> 1000 0000 = 0x80 = -128
        ↑                  ↑
        SF=1 -------------´
#+end_example

Então, se o inteiro com sinal tiver 1 byte, seus limites serão:

#+begin_example
0x7F = 0111 1111 = +127
0x7E = 0111 1110 = +126
...
0x01 = 0000 0001 =   +1
0x00 = 0000 0000 =    0
0xFF = 1111 1111 =   -1
...
0x81 = 1000 0001 = -127
0x80 = 1000 0000 = -128
#+end_example

Transpondo o princípio para o tamanho de um inteiro na arquitetura x86_64,
os limites são:

#+begin_example
0x7FFFFFFF ->  2.147.483.647
0x80000000 -> -2.147.483.648
#+end_example

** Procedimento de conversão para inteiros com sinal

As diferenças em relação à conversão de strings para inteiros sem sinal são:

- Antes da conversão, nós precisamos detectar a presença dos caracteres
  de sinal (=+= e =-=);
- Depois do valor absoluto encontrado, nós teremos que verificar se ele está
  na faixa de valores inteiros com sinal (entre =0x7FFFFFFF= e =0x80000000=);
- No final, se o número passar na verificação, nós teremos que calcular seu
  complemento de dois, o que pode ser feito multiplicando o valor por =-1= ou,
  de forma ainda mais compacta e eficiente, utilizando a instrução =neg=.

Todo o restante do procedimento é idêntico, tanto que podemos reutilizar
as mesmas funções de antes para a etapa de conversão.

** Conversão em alto nível

Com base no procedimento geral, esta seria uma forma de implementar a
conversão de inteiros com sinal em linguagem C reutilizando a função que
criamos para converter inteiros sem sinal:

#+begin_src c
#include <limits.h> // Requerido para obter INT_MAX e INT_MIN da plataforma

int str_to_sint(char *str, int *err) {
    if (err) *err = 0;          // Flag de estado de término: 0 = erro
    if (str == NULL) return 0;  // Teste do ponteiro para a string

    // Verificação e atrubuição do sinal da string...
    char sig = '+';             // Sinal padrão
    if (str[0] == '+' || str[0] == '-') {
        sig = str[0];
        str++;                  // Avança o ponteiro da string
    }

    // Chama a função de conversão de inteiros sem sinal...
    unsigned conv = str_to_uint(str, err);
    if (!*err) return 0;

    // Verificação da faixa de inteiros com sinal...
    if (sig == '-') {
        // INT_MIN=-2147483648, que em unsigned é 2147483648
        if (conv > (unsigned)INT_MAX + 1) return 0;    
        if (err) *err = 1;    // Flag de estado de término: 1 = sucesso
        return -(int)conv;
    } else {
       if (conv > INT_MAX) return 0;
       if (err) *err = 1;    // Flag de estado de término: 1 = sucesso
       return (int)conv; 
    }
}
#+end_src

#+begin_quote
Agora cabe a você, como parte dos exercícios propostos, elaborar e executar
os testes e os ajustes, se forem necessários.
#+end_quote

** Conversão em baixo nível

Esta seria uma solução equivalente implementada como uma sub-rotina que
depende de =_str_to_uint=, criada e testada anteriormente:

#+begin_src asm
; ----------------------------------------------------------
_str_to_sint:
; ----------------------------------------------------------
; Converte string numérica com sinal em inteiro (int32_t).
; Entradas:
;   RSI = Endereço da string (char *str)
;   RDX = Endereço para estado de erro (int *err /* nullable */)
; Saída:
;   RAX = valor convertido (int32_t)
;   Sucesso: *rdx = 1
;   Erro:    *rdx = 0
; ----------------------------------------------------------
    push rbx             ; salva rbx
    push rcx             ; salva rcx
    xor rcx, rcx         ; rcx = 0 (sinal: 0 = positivo, 1 = negativo)
    ; ------------------------------------------------------
    ; Testa ponteiro nulo
    ; ------------------------------------------------------
    test rsi, rsi
    jz .error
    ; ------------------------------------------------------
    ; Verifica o sinal na string
    ; ------------------------------------------------------
    mov bl, [rsi]
    cmp bl, '-'          ; caractere de sinal negativo?
    jne .check_plus
    inc rcx              ; rcx = 1 => negativo
    inc rsi              ; avança o ponteiro
    jmp .convert
.check_plus:
    cmp bl, '+'          ; caractere de sinal positivo?
    jne .convert
    inc rsi              ; ignora '+'
.convert:
    ; ------------------------------------------------------
    ; Chama _str_to_uint
    ; ------------------------------------------------------
    call _str_to_uint    ; RSI = str, RDX = err, RAX = resultado (uint32_t)
    ; ------------------------------------------------------
    ; Verifica se _str_to_uint retornou erro
    ; ------------------------------------------------------
    test rdx, rdx
    jz .check_sign
    cmp dword [rdx], 0
    je .error
.check_sign:
    test rcx, rcx        ; se rcx = 1, é número negativo
    jz .check_range_pos
    ; ------------------------------------------------------
    ; Verifica se valor cabe em int32_t negativo
    ; ------------------------------------------------------
    cmp eax, 0x80000000
    ja .error            ; se maior que INT_MAX + 1 -> erro

    neg eax              ; aplica o sinal negativo
    jmp .success
.check_range_pos:
    ; ------------------------------------------------------
    ; Verifica se valor cabe em int32_t positivo
    ; ------------------------------------------------------
    cmp eax, 0x7fffffff
    ja .error            ; maior que INT_MAX -> erro
.success:
    test rdx, rdx
    jz .done
    mov dword [rdx], 1   ; *err = 1
    jmp .done
.error:
    xor eax, eax         ; valor de erro = 0
    test rdx, rdx
    jz .done
    mov dword [rdx], 0   ; *err = 0
.done:
    pop rcx
    pop rbx
    ret
#+end_src

#+begin_quote
Também faz parte dos exercícios propostos, elaborar e executar os testes
e os ajustes, se forem necessários.
#+end_quote

* Exercícios propostos

1. Altere o valor em =num_str=, nos testes da sub-rotina =_str_to_uint=, e
   analise os resultados com o GDB.
2. Em C, crie as funções =str_to_ulong= (string para inteiros longos sem sinal)
   e =str_to_slong= (string para inteiros longos com sinal).
3. Em Assembly, crie as sub-rotinas =_str_to_ulong= e =_str_to_slong=.

