## 1. Tiny introduction
- Trong quá trình mình học code C, một vấn đề mình rất ghét phải đối mặt đó là tràn số. Điều này xuất phát từ việc dữ liệu của C chỉ gói gọn trong 64 bit, tức là số lớn nhất lưu được dưới dạng long long có giá trị đâu đó tầm 9 tỉ tỉ (`9 * 10^18`). Khi vượt qua giá trị này, việc tính toán trở nên khó khăn và nảy sinh nhiều lỗi.
- Assembly cũng gặp vấn đề tương tự khi mặc định số lưu được trong thanh ghi EAX là 32 bit, RAX là 64 bit. Chính vì vậy, đối với những task khó như tìm số fibonacci (mà mình sẽ nói trong bài 105), chúng ta cần công cụ để handle các số lớn này (trong bài mình sẽ gọi là Big Num).
## 2. Algorithm
- Một cách giải quyết số lớn điển hình và cổ điển mà mình gặp trong code C đó là sử dụng string để lưu giá trị. Khi đó, các phép toán cộng, trừ, nhân, chia, modulo sẽ không dùng được, mà chúng ta phải viết hàm để xử lí. Trong bài này mình chỉ nói về việc cộng hai số lớn với nhau.
- Chúng ta sẽ lưu big num dưới dạng string, ví dụ số `3` sẽ được lưu thành `"3"` và `999` sẽ được lưu thành `"999"`. Sau đó mình sẽ thực hiện cộng từng chữ số từ phải sang trái, có lấy nhớ (thực hiện giống khi học tiểu học).
## 3. Code
- Chi tiết thuật toán có thể tham khảo [nguồn này](https://www.geeksforgeeks.org/how-to-handle-large-numbers-in-c/)
### Reverse String
- Với mình, việc `memmove` như trong code C khá sú, vì khi đó mình phải truy cập vào địa chỉ ngay trước big num của mình. Ví dụ như chuỗi `"3"` có địa chỉ 1, muốn `memmove` để nó trở thành `"03"` thì phải truy cập vào địa chỉ 0 để thêm `"0"`. Hoặc không cũng phải dịch các giá trị sang phải một đơn vị nhớ rồi mới thêm `"0"` được.
- Điều này có thể làm thay đổi dữ liệu của các biến trước đó trong vùng nhớ, bên cạnh đó mình cũng ngại việc shifting, vậy nên mình xử lí bằng cách đảo ngược chuỗi và thêm `"0"` vào cuối chứ không phải đầu. Khi đó phép cộng cũng được thực hiện từ trái qua phải, từ `i = 0` cho tới `i = strlen(num)`, mà các giá trị trong bộ nhớ cũng được lưu từ trái qua phải nên thuận tiện hơn
- Dưới đây là code để đảo ngược chuỗi mà mình đã code để quẳng vào file `functions.asm` (cần có hàm `sLen` của file vì mình custom hàm đó khác với của [asmtutor](https://asmtutor.com/)):
```assembly=
; void reverseStr(String message)
; Reverse a string
; Source: esi
; Destination: edi
reverseStr:
push eax
push ecx
push edi
push esi
push esi
call sLen
mov ecx, esi ; n
dec ecx
pop esi
next_reverseStr:
cmp ecx, -1
je finished_reverseStr
mov al, byte [esi + ecx]
mov [edi], al
inc edi
dec ecx
jmp next_reverseStr
finished_reverseStr:
mov [edi], byte 0 ; make null
pop esi
pop edi
pop ecx
pop eax
ret
```
- Hàm sẽ nhận vào `ESI` là địa chỉ của chuỗi ban đầu, `EDI` là địa chỉ của chuỗi đảo ngược, tức là `reverseStr(ESI) = EDI`. Test code:
```assembly=
global _start
%include "functions.asm"
section .bss
input: resb 100
output: resb 100
outoutput: resb 100
section .data
msg1: db ">> ", 0
msg2: db "Your reversed input is: ", 0
newline: db "", 0xa
msg3: db "Your reversed reversed input is: ", 0
section .text
_start:
; Print msg1
lea esi, [msg1]
call sPrint
lea esi, [input]
call sScan
; Print msg2
lea esi, [msg2]
call sPrint
; Output: reversed input
lea esi, [input]
lea edi, [output]
call reverseStr
lea esi, [output]
call sPrint
; Print newline
mov edx, 1
lea ecx, [newline]
mov ebx, 1
mov eax, 4
int 0x80
; Outoutput: reversed output
lea esi, [output]
lea edi, [outoutput]
call reverseStr
lea esi, [msg3]
call sPrint
lea esi, [outoutput]
call sPrint
call quit
```
- Chuỗi đảo ngược lại đúng và chuỗi đảo ngược hai lần giống hệt chuỗi ban đầu, điều đó chứng tỏ hàm của mình có hiệu quả, bảo toàn được dữ liệu. Điều này giúp mình tránh lỗi khi cộng. Lấy ví dụ cộng `"3"` vào `"999"` như thuật toán ra được `"2001"`, khi đó cần đảo ngược lại chuỗi để được kết quả đúng thì hàm cho kết quả đúng như mong đợi.
### Adding Big Num
- Code của mình khá ngắn, hàm nhận vào các tham số `num1, num2, reversedNum1, reversedNum2`, push theo đúng thứ tự. Tại đây mình thực hiện thuật toán giống như trong link trên, đảo ngược `num1` và `num2`, cộng hai số, lưu tổng (bị ngược) trong `reservedNum1` và kết quả cuối cùng nằm trong `num1`.
- Dưới đây là hàm `addBigNum` của mình, trông hơi kinh dị, mình cũng mất mấy tiếng để ngồi fix sao cho ngon nhất, mặc dù chưa ưng ý lắm vì phải truyền `reservedNum1` và `reservedNum2` chả liên quan mẹ gì đến hàm:
```assembly=
; void addBigNum()
; Calculate the sum of two big numbers
; First para: esi -> num1
; Second para: edi -> num2
; Third para: reversedNum1
; Fourth para: reversedNum2
; Store result in num1: [esp + 0x4] in the end
; Stack in the end before return will look like that
; [len] -> esp
; [edi]
; [esi]
; [edx]
; [ecx]
; [ebx]
; [eax]
; [old ebp]
; [return address]
; [reversedNum2]
; [reversedNum1]
; [num2]
; [num1] -> it stores the result in the end
addBigNum:
; Backup things
push ebp
mov ebp, esp
push eax
push ebx
push ecx
push edx
mov esi, [ebp+0x14] ; num1
mov edi, [ebp+0x10] ; num2
push esi ; store num1
push edi ; store num2
call sLen
mov eax, esi ; strlen(num1)
mov esi, edi
call sLen
mov edx, esi ; strlen(num2)
push eax ; Suppose it is the max length
cmp eax, edx ; Compare to find the max length
jg reverseStep_addBigNum
pop eax
push edx ; len = strlen(num2)
reverseStep_addBigNum:
mov esi, [esp+0x4] ; num2
mov edi, [ebp+0x8] ; reversedNum2
call reverseStr ; if num2 = 30, after that it would be 03
mov esi, [esp+0x8] ; num1
mov edi, [ebp+0xc] ; reversedNum1
call reverseStr
; appendZeros_addBigNum:
mov bl, byte "0"
cmp eax, edx
jl appendZeros_addBigNum_1
jmp appendZeros_addBigNum_2 ; if num2 is "03", append zeros to the right until it gets the max length
appendZeros_addBigNum_1:
mov [edi + eax], ebx ; edi is holding reversedNum1 so no need to change
inc eax
cmp eax, [esp]
jl appendZeros_addBigNum_1
jmp finished_appending_addBigNum
appendZeros_addBigNum_2:
mov edi, [ebp+0x8] ; change to reversedNum2
mov [edi + edx], ebx
inc edx
cmp edx, [esp]
jl appendZeros_addBigNum_2
jmp finished_appending_addBigNum
finished_appending_addBigNum:
mov esi, [ebp+0xc] ; make esi -> reversedNum1
mov edi, [ebp+0x8] ; make edi -> reversedNum2
; this is preparation for calculating and storing result in reversedNum1
xor eax, eax ; store digit
mov bl, 10 ; dividing
xor ecx, ecx ; counter: from 0 -> max length stored at [esp]
xor edx, edx ; the carry
addingLoop_addBigNum:
push edx ; backup carry
xor eax, eax ; cleanning up
xor edx, edx ; cleanning up
mov al, [esi + ecx]
mov dl, [edi + ecx]
sub al, "0" ; num1[i] - "0"
sub dl, "0" ; num2[i] - "0"
add al, dl ; num1[i] - "0" + num2[i] - "0"
pop edx ; restore carry
add al, dl ; digit = num1[i] - "0" + num2[i] - "0" + carry
div bl
; ah = ax % bl
; al = ax / bl -> carry
add ah, "0" ; (digit % 10) + "0"
mov [esi + ecx], byte ah; num1[i] = (digit % 10) + "0"
mov dl, al ; carry = digit / 10
inc ecx ; i++
cmp ecx, [esp] ; cmp i, max length
jne addingLoop_addBigNum
cmp edx, 1 ; if there is a carry after adding
jne finished_addBigNum
add dl, "0" ; append the carry to the end of reversed string
mov [esi + ecx], byte dl
finished_addBigNum:
add esp, 0x4 ; skip the max length value
mov esi, [esp + 0x4*9] ; point to reversedNum1
mov edi, [esp + 0x4*11] ; point to num1
call reverseStr
; Restore things
pop edi
pop esi
pop edx
pop ecx
pop ebx
pop eax
mov esp, ebp
pop ebp
ret
```
và code tính tổng hai số big num sẽ như sau:
```assembly=
global _start
%include "functions.asm"
section .bss
num1: resb 100
num2: resb 100
reversedNum1: resb 100
reversedNum2: resb 100
section .data
msg1: db "Input the first number: ", 0
msg2: db "Input the second number: ", 0
msg3: db "The sum of two numbers is: ", 0
section .text
_start:
lea esi, [msg1]
call sPrint ; Print msg1
lea esi, [num1]
call sScan ; Input num1
lea esi, [msg2]
call sPrint ; Print msg2
lea esi, [num2]
call sScan ; Input num2
push num1 ; ebp+0x14
push num2 ; ebp+0x10
push reversedNum1 ; ebp+0xc
push reversedNum2 ; ebp+0x8
call addBigNum
; addBigNum(reversedNum2, reversedNum1, num2, num1)
lea esi, [msg3]
call sPrint ; Print msg3
lea esi, [num1]
call sPrint ; Print result
call quit
```
- Note một chút lí do vì sao mình lại sử dụng `reversedNum1` và `reversedNum2` ở kia. Khác với các code handle Big Num khác (như [code của anh Sơn Doraemon](https://github.com/SonVH2511/trainingKCSC/blob/main/TASK1_FIB%2CSORT%2CBIGNUM/descript.md) sử dụng stack để lưu từng digit) thì mình sử dụng hẳn hai vùng nhớ để lưu chuỗi đảo ngược của `num1` và `num2`. Với mình điều này khá tối ưu, tránh được khả năng bị overflow với số quá lớn. Tuy nhiên điểm bất cập là phải cung cấp địa chỉ của hai vùng nhớ `reversedNum1` và `reversedNum2` không liên quan gì đến hàm tính tổng, gây khó hiểu cho người đọc.
- Sau khi done thì mình đã cố sử dụng stack để lưu chuỗi thay cho `reversedNum` nhưng quên mất một điều là stack chỉ có 4 byte, tức lưu được đến 4 chữ số là max, khi đó nếu tiếp tục chạy sẽ bị tràn, nói cách khác là buffer overflow. Mình đã khá ngu khi cố ngồi fix để không phải truyền `reveredNum` mà không nhận ra vấn đề. Trong tương lai nếu có thời gian mình sẽ quay lại và fix nó để tối ưu hơn, còn bây giờ tạm thời code như vậy.
- Mình để max là 100 chữ số nên chỉ dám test big num đâu đó tầm 9x chữ, nếu hơn thì khả năng xảy ra bug rất nhiều :crying_cat_face:
- Lỗi đây:
- 98 chữ số thì bình thường:
- Vậy nên muốn tăng max digits lên thì chỉ cần tăng size của .bss lên là được, ở đây mình set 100 cho đẹp :smile_cat:
> Bài viết sau là về tìm số fibonacci thứ n, mình sẽ viết sau khi ôn xong môn "Tư tưởng Hồ Chí Minh", còn giờ mình phải cấp tốc học. Hi vọng bài viết này hữu ích với các bạn. Dear!!!
## 4. Updating
- Mình đã upload file `functions.asm` mới ở [đây](https://github.com/Zupp30/Zupp_Learn_Reverse/blob/c76a93eb137602f9df46a38d0a2b790376eb60e2/functions.asm)
### New function
- Mình đã comeback sau khi thi, và tìm ra một phương án tối ưu, hợp tình hợp lí hơn. Ý tưởng của mình vẫn như trước, chỉ có điều hàm sum giờ nhận vào 3 tham số, lần lượt là `(sum, num2, num1)` với `sum` là nơi lưu tổng.
- Code:
```assembly=
; int sumBigNum()
; Calculate the sum of two big numbers
; First para: sum -> destination to store
; Next paras: num2, num1
; After finished label, num1 holds result reversed, sum holds the right one
sumBigNum:
; Backup things
push ebp
mov ebp, esp
push eax
push ebx
push ecx
push edx
; Code
; First to reverse the two string
; sum = reversedStr(num1)
; num1 = reversedStr(num2)
mov esi, [ebp+0x10] ; num1
mov edi, [ebp+0x8] ; sum
call reverseStr
mov esi, edi
call sLen
mov edx, esi
push edx ; suppose it is max_len
mov esi, [ebp+0xc] ; num2
mov edi, [ebp+0x10] ; num1
call reverseStr
mov esi, edi
call sLen
mov eax, esi
cmp eax, edx
jl pre_appendZeros
pop edx
push eax ; change max_len if eax > edx
pre_appendZeros:
mov esi, [ebp+0x10] ; point to num1
mov edi, [ebp+0x8] ; point to sum
mov bl, byte "0" ; prepare byte to append
cmp eax, [esp] ; compare to add "0"
jl appendZeros_num1
jmp appendZeros_sum
appendZeros_num1:
mov [esi + eax], ebx
inc eax
cmp eax, [esp]
jl appendZeros_num1
jmp pre_addLoop
appendZeros_sum:
mov [edi + edx], ebx
inc edx
cmp edx, [esp]
jl appendZeros_sum
jmp pre_addLoop
pre_addLoop:
; this is preparation for calculating and storing result in num1
xor eax, eax ; store digit
mov bl, 10 ; dividing
xor ecx, ecx ; counter: from 0 -> max length stored at [esp]
xor edx, edx ; the carry
addLoop:
push edx
xor eax, eax
xor edx, edx
mov al, [esi + ecx]
mov dl, [edi + ecx]
sub al, "0" ; num1[i] - "0"
sub dl, "0" ; sum[i] - "0"
add al, dl ; num1[i] - "0" + sum[i] - "0"
pop edx ; restore carry
add al, dl ; digit = num1[i] - "0" + sum[i] - "0" + carry
div bl
; ah = ax % bl
; al = ax / bl -> carry
add ah, "0" ; (digit % 10) + "0"
mov [esi + ecx], byte ah; num1[i] = (digit % 10) + "0"
mov dl, al ; carry = digit / 10
inc ecx ; i++
cmp ecx, [esp] ; cmp i, max_len
jne addLoop
cmp edx, 1 ; if there is a carry after adding
jne finished
add dl, "0" ; append the carry to the end of reversed string
mov [esi + ecx], byte dl
finished:
add esp, 0x4 ; skip the max_len
; mov esi, [ebp + 0x10] ; num1
; mov edi, [ebp + 0x8] ; sum
; but no need to do that
call reverseStr ; sum = reversed(num1)
pop edx
pop ecx
pop ebx
pop eax
mov esp, ebp
pop ebp
ret
```
- Với hàm mới này, mình không cần phải truyền vào `reversedNum` nữa. Thay vì lưu chuỗi đảo ngược của `num1` và `num2` trong `reversedNum1` và `reversedNum2`, mình thay đổi nó thành `sum` và `num1`. Khi đó, mình sẽ lưu chuỗi kết quả ngược vào `num1`, kết quả xuôi vào `sum`, cuối cùng đạt được hiệu quả tương tự hàm cũ nhưng tối ưu và đẹp hơn nhiều.
- Ví dụ sử dụng hàm:
```assembly=
push num1 ; ebp+0x10
push num2 ; ebp+0xc
push sum ; ebp+0x8
call sumBigNum
; sumBigNum(sum, num2, num1)
```
Sign in with Wallet
Connect another wallet