1
\$\begingroup\$

The first "method" I have coded is _bigPow which can pow(x, y) on any number which is really big. And the _printBigInt prints a very big integer. Plus I have tried to comment most parts of my code to make it easier hopefully!

I just want criticism on what I can improve upon!

The _start you can edit the numbers to check that it works on giant numbers

I used this resource to guide me on how to work with big numbers in x86 - http://x86asm.net/articles/working-with-big-numbers-using-x86-instructions/

Code-

bits 64

%define STDIN  0
%define STDOUT 1
%define STDERR 2

%define SYSCALL_READ     0
%define SYSCALL_WRITE    1
%define SYSCALL_EXIT     60


section .bss
   bigNum resq 100000
   bigNumLen equ 100000

section .text
global _start

_start:

   push 1000      ;pow(1356, 1000) <- edit these two to check the program!
   push 1356      ;pow(1356, 1000) <- edit these two to check the program!

   push bigNumLen ;how many qwords is this storage
   push bigNum    ;pointer to storage
   call _bigPow   ;return pointer in rax if sucess or 0 if fail

   push bigNumLen ;push storage size again
   push rax       ;pus hpointer again
   call _printBigInt
   add rsp, 48    ;clean stack

   mov rax, 60    ;SYSCALL_EXIT
   mov rdi, 0
   syscall


;must reserve at leat 64 bits of space aka 1 qword.
;must increment space in 64 bits. (64, 128, 192) aka 1 qword, 2 qword, 3 qword
;(first)last thing pushed on the stack must be a pointer to where you want to store the number
;second argument must be how many qwords you have reserved (1, 2, 3) etc.
;third argument must be what number you want to pow e.g 2
;fourth argument must be thw power e.g 3 (2^3)
;if sucessful then it will return pointer in rax
;if failer returns 0 in rax
_bigPow:
   ;prolog
   push rbp
   mov rbp, rsp
   ;save registers
   push rbx

   mov rbx, [rbp + 32]             ;the number to be powed (the base)
   mov r8, qword[rbp + 16]         ;the pointer to where to store the result
   mov [r8], rbx                   ;derefrence pointer and store rbx
   mov rcx, [rbp + 40]             ;the actual power       (the exponent)
   test rcx, rcx
   jz ._expIsZero
   jmp ._BigPowLoopCond

   ._BigPowLoop:
      mov rax, [r8]                ;derefrence pointer and move value into rax
      mul rbx                      ;multiply by base
      mov [r8], rax                ;put the number back after derefrencing pointer
      mov r9, rdx                  ;save the carried part into r9 register

      push rcx                     ;pushing rcx (the exponent) into the stack for later use
      xor rcx, rcx
      jmp ._BigPowLoop2Cond
      ._BigPowLoop2:
         mov rax, [r8 + 8 * rcx]   ;moving xth bytes into rax (8, 16, 24...)
         mul rbx
         add rax, r9               ;adding previous carried part
         mov [r8 + 8 * rcx], rax   ;store number back into xth bytes
         mov r9, rdx
      ._BigPowLoop2Cond:
         inc rcx
         cmp rcx, [rbp + 24]       ;how many qwords were reserved
         jl ._BigPowLoop2

      pop rcx                      ;put the exponent back into rcx
      test rdx, rdx                ;if rdx is not zero we dont have enough space!
      jnz ._overflow               ;exit gracefuly

   ._BigPowLoopCond:
   loop ._BigPowLoop

   ._sucess:
   mov rax, r8
   jmp ._exitBigPow

   ._expIsZero:
   mov rax, r8
   mov qword[r8], 1
   jmp ._exitBigPow

   ._overflow:
   mov rax, 0

   ._exitBigPow:
   ;restore registers
   pop rbx
   ;epilog
   pop rbp
   ret



;prints only big positive numbers
;last value pushed onto stack must contain pointer to the value to be printed
;second value is how many qwords long is the number (1, 2, 3,...)
_printBigInt:
   ;prolog
   push rbp
   mov rbp, rsp
   ;save registers
   push rbx
   mov rdi, rsp                ;make a copy of rsp for later. plus now I dont need to clean stack!!!

   ;making space on the stack because
   ;I dont want to destroy the original number
   mov rcx, [rbp + 24]         ;getting the second param. how many qwords long
   lea r8,  [rcx * 8]
   sub rdi, r8                 ;make space on the stack

   mov r8, [rbp + 16]          ;getting the pointer
   jmp ._printBigIntStackLoopCond

   ._printBigIntStackLoop:
      mov rax, [r8 + 8 * rcx]  ;move the most significant byte into rax
      mov [rdi + 8 * rcx], rax ;mov that byte into the stack
   ._printBigIntStackLoopCond:
      dec rcx
      cmp rcx, -1
      jne ._printBigIntStackLoop

   ;now the bigInt has been moved into the stack so we dont mess it up

   mov rbx, 10                      ;divisor
   xor r8, r8                       ;will be used to keep track of how many char are in the stack
   mov r9, rdi                      ;needed to manually put char in stack
   ._printBigIntLoop:
      mov rcx, [rbp + 24]           ;get how many qwords big the number is
      dec rcx                       ;decrementing because 0 based index

      xor rdx, rdx                  ;clear rdx
      mov rax, [rdi + 8 * rcx]      ;move most sig 8 bytes into rax from the stack
      div rbx                       ;divide by 10
      mov [rdi + 8 * rcx], rax      ;mov the result into the stack again
      jmp ._printBigIntLoop2Cond

      ._printBigIntLoop2:
         mov rax, [rdi + 8 * rcx]
         div rbx
         mov [rdi + 8 * rcx], rax
      ._printBigIntLoop2Cond:
         dec rcx
         cmp rcx, -1
         jne ._printBigIntLoop2

      lea rax, [rdx + '0']         ;converting the one digit into ascii value
      dec r9
      mov [r9], al                 ;pushing the remainded onto the stack
      inc r8                       ;inc how many chars need to be printed
   ._printBigIntLoopCond:
      mov rcx, [rbp + 24]          ;move how many qwords big the number is
      dec rcx                      ;dec by 1 because 0 based index
      ._checkIfBigIntIsZero:
         mov rax, [rdi + 8 * rcx]  ;move most sig 8 bytes int rax
         test rax, rax             ;check if 0
         jnz ._printBigIntLoop     ;jump if not zero as there is more numbers to divide
      dec rcx
      cmp rcx, -1                  ;if rcx becomes -1 then there is noting less to divide
      jne ._checkIfBigIntIsZero

   ;print the number
   mov rax, SYSCALL_WRITE
   mov rdi, STDOUT
   mov rsi, r9                     ;the string
   mov rdx, r8                     ;length
   syscall

   ;restore registers
   pop rbx
   ;epilog
   pop rbp
   ret

```
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Multiplication bug

Putting aside the loop logic for a bit, the "meat" of the bignint-by-smallint multiplication is like this:

 mov rax, [r8 + 8 * rcx]   ;moving xth bytes into rax (8, 16, 24...)
 mul rbx
 add rax, r9               ;adding previous carried part
 mov [r8 + 8 * rcx], rax   ;store number back into xth bytes
 mov r9, rdx

Of course, you followed the resource, but it's not right. add rax, r9 can carry (though keeping the base low means it is unlikely to happen). When it does, the upper half would have to be incremented. That increment does not pose the same problem again: the maximum product of two 64bit numbers is 0xffffffffffffffff² = 0xfffffffffffffffe0000000000000001, the upper half is at most 0xfffffffffffffffe so it's safe to increment.

For example,

 mov rax, [r8 + 8 * rcx]   ;moving xth bytes into rax (8, 16, 24...)
 mul rbx
 add rax, r9               ;adding previous carried part
 mov [r8 + 8 * rcx], rax   ;store number back into xth bytes
 adc rdx, 0                ;increment upper half if the 'add' carried
 mov r9, rdx

Unnecessarily-64-bit instructions

Several instructions can be replaced with their 32bit counterparts, typically saving code size. For example, mov rax, 1 (7 bytes) can be mov eax, 1 (5 bytes). xor rdx, rdx can be xor edx, edx. _BigPowLoop2 does not need a 64bit loop count. Small changes in code size are not necessarily significant, so this is all low-priority, but it can help.

Perhaps you have heard that a processor "prefers" operations that match its "bitness", x86-64 does not work like that, if anything it has a small preference for 32bit operations (but 64bit memory addressing).

The loop instruction

loop is not as nice as it looks. See How exactly does the x86 LOOP instruction work? for the details. As an extra half-strike against it, your code needed push rcx / pop rcx in the loop because rcx was used as loop counter by both loops - but of course an other way to avoid that is choosing an other register for the inner loop.

Spelling

I rarely comment on this, but there are some spelling errors in your comments, so they could be improved. For example: dereference, successful, failure.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the advice tonight i will fix it! Especially the spelling that my bad! \$\endgroup\$
    – Dagar
    Oct 8, 2020 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.