In che modo i numeri sono superiori a 2^32 gestiti da una macchina a 32 bit?

Question

Sto cercando di capire come i calcoli che coinvolgono numeri superiori a 2 si verificano su una macchina a 32 bit.

codice C

$ cat size.c 
#include<stdio.h> 
#include<math.h> 

int main() { 

    printf ("max unsigned long long = %llu\n", 
    (unsigned long long)(pow(2, 64) - 1)); 
} 
$ 

uscita gcc

$ gcc size.c -o size 
$ ./size 
max unsigned long long = 18446744073709551615 
$ 

codice assembly corrispondente

$ gcc -S size.c -O3 
$ cat size.s 
    .file "size.c" 
    .section .rodata.str1.4,"aMS",@progbits,1 
    .align 4 
.LC0: 
    .string "max unsigned long long = %llu\n" 
    .text 
    .p2align 4,,15 
.globl main 
    .type main, @function 
main: 
    pushl %ebp 
    movl %esp, %ebp 
    andl $-16, %esp 
    subl $16, %esp 
    movl $-1, 8(%esp) #1 
    movl $-1, 12(%esp) #2 
    movl $.LC0, 4(%esp) #3 
    movl $1, (%esp)  #4 
    call __printf_chk 
    leave 
    ret 
    .size main, .-main 
    .ident "GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3" 
    .section .note.GNU-stack,"",@progbits 
$ 

Cosa accade esattamente sulle linee 1 - 4?

È una sorta di concatenazione di stringhe a livello di assembly?

Answer 1

__printf_chk è un involucro intorno printf che verifica stack overflow, e prende un ulteriore primo parametro, un flag (per esempio vedi here.)

pow(2, 64) - 1 è stato ottimizzato per 0xffffffffffffffff come argomenti sono costanti.

Secondo le usuali convenzioni di chiamata, il primo argomento di __printf_chk() (int flag) è un valore di 32 bit dello stack (a %esp al momento dell'istruzione call). L'argomento successivo, const char * format, è un puntatore a 32 bit (la successiva parola a 32 bit sullo stack, ad esempio %esp+4). E la quantità a 64 bit che viene stampato occupa entro due parole di 32 bit (a %esp+8 e %esp+12):

pushl %ebp     ; prologue 
movl %esp, %ebp   ; prologue 
andl $-16, %esp   ; align stack pointer 
subl $16, %esp   ; reserve bytes for stack frame 
movl $-1, 8(%esp) #1 ; store low half of 64-bit argument (a constant) to stack 
movl $-1, 12(%esp) #2 ; store high half of 64-bit argument (a constant) to stack 
movl $.LC0, 4(%esp) #3 ; store address of format string to stack 
movl $1, (%esp)  #4 ; store "flag" argument to __printf_chk to stack 
call __printf_chk   ; call routine 
leave      ; epilogue 
ret       ; epilogue 

Il compilatore ha efficacemente riscritto questo:

printf("max unsigned long long = %llu\n", (unsigned long long)(pow(2, 64) - 1)); 

... in questo:

__printf_chk(1, "max unsigned long long = %llu\n", 0xffffffffffffffffULL); 

... e, in fase di esecuzione, il layout stack per la chiamata simile a questo (che mostra la pila come parole di 32 bit, con gli indirizzi in aumento dal inferiore del diagramma verso l'alto):

 :     : 
     :  Stack  : 
     :     : 
     +-----------------+ 
%esp+12 |  0xffffffff | \ 
     +-----------------+ } <-------------------------------------. 
%esp+8 |  0xffffffff |/          | 
     +-----------------+           | 
%esp+4 |address of string| <---------------.      | 
     +-----------------+     |      | 
%esp |    1 | <--.   |      | 
     +-----------------+ |   |      | 
        __printf_chk(1, "max unsigned long long = %llu\n", | 
                0xffffffffffffffffULL); 

Answer 2

Il compilatore ha effettivamente effettuato un'ottimizzazione statica del codice. linee # 1 # 2 # 3 sono parametri per printf()

Answer 3

Come menziona @Pafy, il compilatore ha valutato questo come una costante.

dal 2 al 64 meno 1 è 0xffffffffffffffff.

Come 2 interi a 32 bit questo è: 0xffffffff e 0xffffffff,
che se si prende che, come un paio di tipi firmato a 32 bit, finisce come: -1 e -1.

Così per il compilatore genera il codice sembra essere equivalente a:

printf("max unsigned long long = %llu\n", -1, -1); 

Nell'assemblea è scritto così:

movl $-1, 8(%esp) #Second -1 parameter 
movl $-1, 12(%esp) #First -1 parameter 
movl $.LC0, 4(%esp) #Format string 
movl $1, (%esp)  #A one. Kind of odd, perhaps __printf_chk 
         #in your C library expects this. 
call __printf_chk 

Tra l'altro, un modo migliore per calcolare i poteri di 2 è quello di spostare 1 a sinistra. Per esempio. (1ULL << 64) - 1.

Answer 4

Nel tuo caso, il compilatore sa che 2^64-1 è solo 0xffffffffffffffff, quindi ha spinto -1 (bassa dword) e -1 (alta dword) nello stack come argomento per printf. È solo un'ottimizzazione.

In generale, i numeri a 64 bit (e anche i valori maggiori) possono essere memorizzati con più parole, ad es. un unsigned long long utilizza due dword s. Per aggiungere due numeri a 64 bit, due aggiunte vengono eseguite - uno sulle basse 32 bit, ed uno in alto 32 bit, più il riporto:

; Add 64-bit number from esi onto edi: 
mov  eax, [esi] ; get low 32 bits of source 
add  [edi], eax ; add to low 32 bits of destination 
; That add may have overflowed, and if it did, carry flag = 1. 
mov  eax, [esi+4] ; get high 32 bits of source 
adc  [edi+4], eax ; add to high 32 bits of destination, then add carry. 

È possibile ripetere questa sequenza di add e adc s come tanto quanto ti piace aggiungere numeri arbitrariamente grandi. La stessa cosa si può fare con la sottrazione: basta usare sub e sbb (sottrarre con un prestito).

La moltiplicazione e la divisione sono molto più complicate e il compilatore di solito produce alcune piccole funzioni di supporto per gestirle quando si moltiplicano i numeri a 64 bit. Pacchetti come GMP che supportano numeri interi molto grandi utilizzano SSE/SSE2 per velocizzare le cose. Dai un'occhiata a this Wikipedia article per ulteriori informazioni sugli algoritmi di moltiplicazione.

Answer 5

simile al modo in cui gestiamo numeri maggiori di 9, con soli cifre 0 - 9. (utilizzando le cifre posizionali). presumendo che la domanda sia concettuale.

Answer 6

Nessuno in questo thread ha notato che l'OP ha chiesto di spiegare le prime 4 righe, non le righe 11-14.

Le prime 4 linee sono:

.file "size.c" 
    .section .rodata.str1.4,"aMS",@progbits,1 
    .align 4 
.LC0: 

Ecco ciò che accade nelle prime 4 linee:

.file "size.c" 

Si tratta di una direttiva assembler che dice che stiamo per iniziare un nuovo file logico chiamato "size.c".

.section .rodata.str1.4,"aMS",@progbits,1 

Questa è anche una direttiva per le stringhe di sola lettura nel programma.

.align 4 

Questa direttiva imposta il contatore posizione di essere sempre un multiplo di 4.

.LC0: 

Questa è un'etichetta LC0 che può essere saltato, per esempio.

Spero di aver fornito la risposta giusta alla domanda poiché ho risposto esattamente che cosa ha chiesto OP.

Answer 7

Come altri hanno sottolineato, tutti gli aritmetici a 64 bit nell'esempio sono stati ottimizzati. Questa risposta si concentra sulla domanda nel titolo.

Fondamentalmente trattiamo ciascun numero a 32 bit come una cifra e lavoriamo nella base 4294967296.In questo modo possiamo lavorare su grandi numeri arbitrariamente.

L'addizione e la sottrazione sono più facili. Lavoriamo attraverso le cifre una alla volta partendo dal meno significativo e passando al più significativo. Generalmente la prima cifra viene eseguita con una normale istruzione di addizione/sottrazione e le cifre successive vengono eseguite utilizzando una specifica istruzione "aggiungi con trasporta" o "sottrai con un prestito". Il flag carry nel registro di stato viene usato per prendere il bit carry/borrow da una cifra alla successiva. Grazie a due complementi di addizione e sottrazione firmati e non firmati sono gli stessi.

La moltiplicazione è un po 'più complicata, moltiplicando due cifre a 32 bit è possibile ottenere un risultato a 64 bit. La maggior parte dei processori a 32 bit avrà istruzioni che moltiplicano due numeri a 32 bit e produce un risultato a 64 bit in due registri. Sarà quindi necessaria l'aggiunta per combinare i risultati in una risposta finale. Grazie a due complementi, la moltiplicazione con segno e senza segno è la stessa a condizione che la dimensione del risultato desiderata sia la stessa della dimensione dell'argomento. Se il risultato è maggiore degli argomenti, è necessario prestare particolare attenzione.

Per il confronto iniziamo dalla cifra più significativa. Se è uguale, passiamo alla cifra successiva finché i risultati non sono uguali.

La divisione è troppo complessa per essere descritta in questo post, ma ci sono molti esempi di algoritmi. per esempio. http://www.hackersdelight.org/hdcodetxt/divDouble.c.txt

---

Alcuni esempi reali da gcc https://godbolt.org/g/NclqXC, l'assemblatore è nella sintassi intel.

Prima un'aggiunta. aggiunta di due numeri a 64 bit e produzione di un risultato a 64 bit. Asm è lo stesso per entrambe le versioni firmate e non firmate.

int64_t add64(int64_t a, int64_t b) { return a + b; } 
add64: 
    mov  eax, DWORD PTR [esp+12] 
    mov  edx, DWORD PTR [esp+16] 
    add  eax, DWORD PTR [esp+4] 
    adc  edx, DWORD PTR [esp+8] 
    ret 

Questo è piuttosto semplice, caricare un argomento in eax e edx, quindi aggiungere l'altro utilizzando un componente aggiuntivo seguito da un aggiungere con riporto. Il risultato è lasciato in eax ed edx per tornare al chiamante.

Ora una moltiplicazione di due numeri a 64 bit per produrre un risultato a 64 bit. Di nuovo il codice non cambia da firmato a non firmato. Ho aggiunto alcuni commenti per renderlo più facile da seguire.

Prima di esaminare il codice, prendere in considerazione la matematica. a e b sono numeri a 64 bit Userò lo() per rappresentare i 32 bit inferiori di un numero a 64 bit e hi() per rappresentare i 32 bit superiori di un numero a 64 bit.

(a * b) = (lo (a) * lo (b)) + (ciao (a) * lo (b) * 2^32) + (ciao (b) * lo (a) * 2^32) + (ciao (b) * ciao (a) * 2^64)

(a * b) mod 2^64 = (lo (a) * lo (b)) + (lo (ciao (ciao a) * lo (b)) * 2^32) + (lo (hi (b) * lo (a)) * 2^32)

lo ((a * b) mod 2^64) = lo (lo (a) * lo (b))

hi ((a * b) mod 2^64) = hi (lo (a) * lo (b)) + lo (hi (a) * lo (b)) + lo (hi (b) * lo (a))

uint64_t mul64(uint64_t a, uint64_t b) { return a*b; } 
mul64: 
    push ebx      ;save ebx 
    mov  eax, DWORD PTR [esp+8] ;load lo(a) into eax 
    mov  ebx, DWORD PTR [esp+16] ;load lo(b) into ebx 
    mov  ecx, DWORD PTR [esp+12] ;load hi(a) into ecx 
    mov  edx, DWORD PTR [esp+20] ;load hi(b) into edx 
    imul ecx, ebx     ;ecx = lo(hi(a) * lo(b)) 
    imul edx, eax     ;edx = lo(hi(b) * lo(a)) 
    add  ecx, edx     ;ecx = lo(hi(a) * lo(b)) + lo(hi(b) * lo(a)) 
    mul  ebx      ;eax = lo(low(a) * lo(b)) 
            ;edx = hi(low(a) * lo(b)) 
    pop  ebx      ;restore ebx. 
    add  edx, ecx     ;edx = hi(low(a) * lo(b)) + lo(hi(a) * lo(b)) + lo(hi(b) * lo(a)) 
    ret 

Finalmente quando proviamo una divisione vediamo.

int64_t div64(int64_t a, int64_t b) { return a/b; } 
div64: 
    sub  esp, 12 
    push DWORD PTR [esp+28] 
    push DWORD PTR [esp+28] 
    push DWORD PTR [esp+28] 
    push DWORD PTR [esp+28] 
    call __divdi3 
    add  esp, 28 
    ret 

Il compilatore ha deciso che la divisione è troppo complessa da implementare in linea e chiama una routine di libreria, invece.