Số lớn hơn 2^32 được xử lý bởi máy 32 bit như thế nào?

Question

Tôi đang cố gắng hiểu cách tính toán liên quan đến các số lớn hơn 2 xảy ra trên máy 32 bit.

mã 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)); 
} 
$ 

đầu ra gcc

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

mã lắp ráp tương ứng

$ 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 
$ 

gì chính xác xảy ra trên đường 1-4?

Đây có phải là loại nối chuỗi ở cấp độ lắp ráp không?

Answer 1

__printf_chk là một wrapper quanh printf mà kiểm tra cho stack overflow, và mất một tham số đầu tiên bổ sung, một lá cờ (ví dụ: xem here.)

pow(2, 64) - 1 đã được tối ưu hóa để 0xffffffffffffffff như các đối số là hằng số.

Theo các công ước gọi thông thường, đối số đầu tiên để __printf_chk() (int flag) là một giá trị 32-bit trên stack (tại %esp tại thời điểm hướng dẫn call). Đối số tiếp theo, const char * format, là con trỏ 32 bit (từ 32 bit tiếp theo trên ngăn xếp, tức là tại %esp+4). Và số lượng 64-bit đang được in chiếm những lời tiếp theo hai 32-bit (tại %esp+8 và %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 

Trình biên dịch đã hiệu quả viết lại này:

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

... vào điều này:

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

... và khi chạy, bố cục ngăn xếp cho cuộc gọi trông như thế này (hiển thị ngăn xếp dưới dạng từ 32 bit, với địa chỉ tăng từ dưới cùng của biểu đồ trở lên):

 :     : 
     :  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

Trình biên dịch thực sự đã tối ưu hóa tĩnh mã của bạn. dòng # 1 # 2 # 3 là các tham số cho printf()

Answer 3

Như @Pafy đề cập, trình biên dịch đã đánh giá đây là hằng số.

2 đến dấu trừ thứ 64 là 0xffffffffffffffff.

Như 2 số nguyên 32-bit này là: 0xffffffff và 0xffffffff,
mà nếu bạn coi đó là một cặp của các loại ký 32-bit, kết thúc như: -1, và -1.

Như vậy cho trình biên dịch của bạn mã được tạo sẽ xảy ra là tương đương với:

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

Trong lắp ráp nó được viết như thế này:

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 

Bằng cách này, một cách tốt hơn để tính toán, quyền hạn của 2 là để chuyển 1 sang trái. Ví dụ. (1ULL << 64) - 1.

Answer 4

Trong trường hợp của bạn, trình biên dịch biết rằng 2^64-1 chỉ là 0xffffffffffffffff, vì vậy nó đã đẩy -1 (dword thấp) và -1 (dword cao) lên ngăn xếp làm đối số của bạn để printf. Nó chỉ là một tối ưu hóa.

Nói chung, số 64 bit (và thậm chí giá trị lớn hơn) có thể được lưu trữ với nhiều từ, ví dụ: an unsigned long long sử dụng hai số dword s. Để thêm hai số 64-bit, hai bổ sung được thực hiện - một trên 32 bit thấp, và một trên 32 bit cao, cộng với carry:

; 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. 

Bạn có thể lặp lại chuỗi này add và adc s như nhiều như bạn muốn thêm số lượng lớn tùy ý. Điều tương tự có thể được thực hiện với phép trừ - chỉ cần sử dụng sub và sbb (trừ đi vay).

Phép nhân và phân chia phức tạp hơn nhiều, và trình biên dịch thường tạo ra một số hàm trợ giúp nhỏ để xử lý những khi bạn nhân các số 64 bit với nhau. Các gói như GMP hỗ trợ các số nguyên rất lớn, rất lớn sử dụng SSE/SSE2 để tăng tốc độ. Hãy xem this Wikipedia article để biết thêm thông tin về thuật toán nhân.

Answer 5

tương tự như cách như chúng ta xử lý số lượng lớn hơn 9, chỉ với chữ số 0 - 9. (sử dụng chữ số theo vị trí). giả sử câu hỏi là một câu hỏi khái niệm.

Answer 6

Không ai trong chủ đề này nhận thấy rằng OP đã yêu cầu giải thích 4 dòng đầu tiên, chứ không phải dòng 11-14.

4 dòng đầu tiên là:

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

Đây là những gì xảy ra trong 4 dòng đầu tiên:

.file "size.c" 

Đây là một chỉ thị lắp ráp mà nói rằng chúng ta sắp bắt đầu một tập tin hợp lý mới có tên gọi "size.c".

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

Đây cũng là chỉ thị cho các chuỗi chỉ đọc trong chương trình.

.align 4 

chỉ thị này đặt vị trí ngược lại luôn là một bội số của 4.

.LC0: 

Đây là một nhãn LC0 có thể được tăng lên, ví dụ.

Tôi hy vọng tôi đã cung cấp câu trả lời đúng cho câu hỏi khi tôi trả lời chính xác những gì OP đã hỏi.

Answer 7

Khi những người khác đã chỉ ra tất cả số học 64 bit trong ví dụ của bạn đã được tối ưu hóa. Câu trả lời này tập trung vào câu hỏi trong tiêu đề.

Về cơ bản, chúng tôi xử lý từng số 32 bit dưới dạng chữ số và làm việc trong cơ sở 4294967296.Theo cách này, chúng ta có thể làm việc với số lượng lớn.

Phép cộng và trừ dễ dàng nhất. Chúng tôi làm việc thông qua các chữ số một tại một thời điểm bắt đầu từ ít nhất có ý nghĩa và di chuyển đến quan trọng nhất. Nói chung chữ số đầu tiên được thực hiện với một lệnh thêm/trừ thông thường và các chữ số sau được thực hiện bằng cách sử dụng hướng dẫn cụ thể "thêm mang theo" hoặc "trừ đi vay". Cờ mang trong thanh ghi trạng thái được sử dụng để lấy bit mang/mượn từ một chữ số sang chữ số kế tiếp. Nhờ twos bổ sung có chữ ký và unsigned cộng và trừ là như nhau.

Phép nhân phức tạp hơn một chút, nhân hai số 32 bit có thể tạo ra kết quả 64 bit. Hầu hết các bộ xử lý 32 bit sẽ có hướng dẫn nhân hai số 32 bit và tạo kết quả 64 bit trong hai thanh ghi. Bổ sung sau đó sẽ là cần thiết để kết hợp các kết quả vào một câu trả lời cuối cùng. Nhờ twos bổ sung cho phép nhân đã ký và unsigned giống nhau, kích thước kết quả mong muốn giống như kích thước đối số. Nếu kết quả lớn hơn các đối số thì cần phải chăm sóc đặc biệt.

Để so sánh, chúng tôi bắt đầu từ chữ số quan trọng nhất. Nếu nó bằng nhau, chúng tôi chuyển xuống chữ số tiếp theo cho đến khi kết quả bằng nhau.

Phân vùng quá phức tạp để tôi mô tả trong bài đăng này, nhưng có rất nhiều ví dụ ngoài thuật toán. ví dụ. http://www.hackersdelight.org/hdcodetxt/divDouble.c.txt

---

Một số ví dụ thực tế từ gcc https://godbolt.org/g/NclqXC, lắp ráp là trong cú pháp intel.

Đầu tiên là sự bổ sung. thêm hai số 64 bit và tạo ra kết quả 64 bit. Asm là giống nhau cho cả hai phiên bản đã ký và chưa ký.

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 

Điều này khá đơn giản, tải một đối số vào eax và edx, sau đó thêm đối số vào eax và edx, sau đó thêm đối số khác bằng dấu cộng theo sau là dấu cộng. Kết quả còn lại trong eax và edx để trở về người gọi.

Bây giờ nhân số hai số 64 bit để tạo kết quả 64 bit. Một lần nữa mã không thay đổi từ đã ký thành unsigned. Tôi đã thêm một số nhận xét để giúp bạn dễ dàng theo dõi hơn.

Trước khi chúng tôi xem xét mã, hãy xem xét toán học. a và b là các số 64 bit, tôi sẽ sử dụng lo() để biểu thị các bit 32 bit thấp hơn của số 64 bit và hi() đại diện cho 32 bit trên của số 64 bit.

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

(a * b) mod 2^64 = (lo (a) * lo (b)) + (lo (hi) 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 

Cuối cùng khi chúng ta thử một bộ phận chúng ta thấy.

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 

Trình biên dịch đã quyết định phân chia quá phức tạp để thực hiện nội tuyến và thay vào đó gọi một thói quen thư viện.