Help with adding Big Numbers

[peter_asm]

Hey folks,

This isn't a homework question and I have tried to do this myself but ..just can't get it to work and need some feedback.
I want to perform addition and subtraction on big numbers but I don't get the same results as those in big numbers calculator.

Having looked around the internet, I thought you would add big numbers on x86 cpu using ADD/ADC, like the following function for 256-bit numbers.

Code Select Expand


; edi = esi + edi
bn_add proc uses esi edi
  mov ecx, 8
  clc
add_cycle:
  mov eax, [esi]
  adc eax, [edi]
  mov [edi], eax
  lea esi, [esi+4]
  lea edi, [edi+4]
  loop add_cycle
  ret
bn_add endp

This looked fine to me until i compared the output of addition with big calculator.
It is related to the carry but i'm not entirely sure what.

Does anyone know why this wouldn't be compatible with most big number libraries that perform addition?

By the way, i realize this routine isn't optimized for speed but I really just want to understand the arithmetic...how it can be done, so simple as possible explanation would be welcome.

[qWord]

your are not updating the pointers in ESI and EDI:

Code Select Expand

add edi,4
add esi,4
inc ecx
jnz ...
an other problem is that you are changing the carry flag at end of each loop iteration sorry, INC/DEC does not affect the carry flag. The best is to unroll the loop:

Code Select Expand

mov eax,[esi]
add [edi],eax
mov eax,[esi+4]
adc [edi+4],eax
...

EDIT

[peter_asm]

I updated the code.

When I try adding 2 big numbers from calculator

esi = EABC39EBD635C26C
edi = AA469F19BA22C209

The output is

9502D904 90588475 1

The big calculator gives me:

1 9502D905 90588475

the numbers are mostly correct except for 2nd and order of course.

[qWord]

TEST does set the carry flag to zero. Use DEC instead.

[dedndave]

Code Select Expand

esi = EABC39EBD635C26C
edi = AA469F19BA22C209
i think you mean [esi] and [edi]   :P

intel processors use "little-endian" format
that is, the lower-order bytes are at lower addresses

the code in your original post is almost correct, assuming ESI and EDI are pre-loaded with addresses

Code Select Expand

bn_add proc uses esi edi
  mov ecx, 8
  clc
add_cycle:
  mov eax, [esi]
  adc eax, [edi]
  dec ecx             ;sets the ZERO FLAG
  mov [edi], eax
  lea esi, [esi+4]
  lea edi, [edi+4]
  jnz add_cycle
  ret
bn_add endp

you have another free register, EDX, so you could sort of unroll once, as qWord suggested...

Code Select Expand

bn_add proc uses esi edi
  mov ecx, 4
  clc
add_cycle:
  mov eax, [esi]
  mov edx, [esi+4]
  adc eax, [edi]
  adc edx, [edi+4]
  dec ecx             ;sets the ZERO FLAG
  mov [edi], eax
  mov [edi+4], edx
  lea esi, [esi+8]
  lea edi, [edi+8]
  jnz add_cycle
  ret
bn_add endp
with 4 passes, you could even get rid of the loop, altogether   

[dedndave]

Code Select Expand

bn_add proc
  mov eax, [esi]
  mov ecx, [esi+4]
  mov edx, [esi+8]
  add eax, [edi]
  adc ecx, [edi+4]
  adc edx, [edi+8]
  mov [edi], eax
  mov [edi+4], ecx
  mov [edi+8], edx

  mov eax, [esi+12]
  mov edx, [esi+16]
  adc eax, [edi+12]
  adc edx, [edi+16]
  mov [edi+12], eax
  mov [edi+16], edx

  mov eax, [esi+20]
  mov ecx, [esi+24]
  mov edx, [esi+28]
  adc eax, [edi+20]
  adc ecx, [edi+24]
  adc edx, [edi+28]
  mov [edi+20], eax
  mov [edi+24], ecx
  mov [edi+28], edx

  ret
bn_add endp

[dedndave]

maybe faster....

Code Select Expand

bn_add proc
  mov eax, [esi]
  mov ecx, [esi+4]
  mov edx, [esi+8]
  add [edi], eax
  adc [edi+4], ecx
  adc [edi+8], dx

  mov eax, [esi+12]
  mov edx, [esi+16]
  adc [edi+12], eax
  adc [edi+16], edx

  mov eax, [esi+20]
  mov ecx, [esi+24]
  mov edx, [esi+28]
  adc [edi+20], eax
  adc [edi+24], ecx
  adc [edi+28], edx

  ret
bn_add endp

[dedndave]

i modified the last 2 posts - there is no need to preserve ESI and EDI, because they aren't altered

[peter_asm]

Hey,

Thanks for all responses!

However, the problem appears to be with the actual numbers I'm using in addition.
They are big endian format or at least should be added to be compatible with big endian machine.

The carry is the problem really, different for big/little endian.
I'll figure it out eventually.

[dedndave]

what big-endian machine ???   :redface:

The Intel x86 and x86-64 series of processors use the little-endian format, and for this reason, the little-endian format is also known as the Intel convention. Other well-known little-endian processor architectures are the 6502 (including 65802, 65C816), Z80 (including Z180, eZ80 etc.), MCS-48, 8051, DEC Alpha, Altera Nios II, Atmel AVR, VAX, and, largely, PDP-11.

so, unless you are writing code for a motorola 6800/68000 processor.....

here is a simple little test piece
i took the last code i posted and made a macro out of it   :P

Code Select Expand

;###############################################################################################

        .XCREF
        .NoList
        INCLUDE    \Masm32\Include\Masm32rt.inc
        .List

;###############################################################################################

AddOword MACRO
    mov     eax,[esi]
    mov     ecx,[esi+4]
    mov     edx,[esi+8]
    add     [edi],eax
    adc     [edi+4],ecx
    adc     [edi+8],dx

    mov     eax,[esi+12]
    mov     edx,[esi+16]
    adc     [edi+12],eax
    adc     [edi+16],edx

    mov     eax,[esi+20]
    mov     ecx,[esi+24]
    mov     edx,[esi+28]
    adc     [edi+20],eax
    adc     [edi+24],ecx
    adc     [edi+28],edx
ENDM

;###############################################################################################

        .DATA
        ALIGN   4

owVal1  dd 9ABCDEF0h,12345678h
owVal2  dd 11111011h,11111111h

;###############################################################################################

        .CODE

;***********************************************************************************************

_main   PROC

    mov     esi,offset owVal1
    mov     edi,offset owVal2

    print   chr$(' Val1: ')
    print   uhex$([esi+4])
    print   uhex$([esi]),13,10

    print   chr$(' Val2: ')
    print   uhex$([edi+4])
    print   uhex$([edi]),13,10

    AddOword

    print   chr$('Total: ')
    print   uhex$([edi+4])
    print   uhex$([edi]),13,10

    print   chr$(13,10)
    inkey
    exit

_main   ENDP

;###############################################################################################

        END     _main

[peter_asm]

When I try adding 2 big numbers from calculator

esi = EABC39EBD635C26C
edi = AA469F19BA22C209

The output is

9502D904 90588475 1

The big calculator gives me:

9502D905 90588475 1 

you'll notice the first number has extra one added to it.
It's something to do with endianness from what i'm reading

http://stackoverflow.com/questions/13926760/the-reason-behind-endianness

Another interesting explanation that I found concerns addition and subtraction. When adding or subtracting multi-byte numbers, the least significant byte must be fetched first to see if there is a carryover to more significant bytes. Because the least-significant byte is read first in little-endian numbers, the system can parallelize and begin calculation on this byte while fetching the following byte(s).

[dedndave]

first, re-design your program for little-endian values
it will make life much simpler when you add other things   :t

when you use

Code Select Expand

    dword 12345678h
the bytes are stored as

Code Select Expand

78 56 34 12

second, start with 2 values whose sum does not exceed the range of an unsigned OWORD
you have chosen 2 values that, when added together, cause a 128-bit overflow

[peter_asm]

I've got the correct values now but I had to add backwards.

  mov ecx, 8
  clc
add_cycle:
  mov eax, [esi+4*ecx-4]
  adc [edi+4*ecx-4], eax 
  loop add_cycle

Tried to reverse the bytes but it gave same problems.

[peter_asm]

i reversed the order first and then use bswap in loop which works too.

  mov ecx, 8
  clc
add_cycle:
  lodsd
  mov ebx, [edi]
  bswap eax
  bswap ebx
  adc eax, ebx
  stosd
  loop add_cycle

thanks for your help :)

[dedndave]

perhaps you mis-understand what i meant
if you are using BSWAP for all your data, you haven't grasped what i tried to explain
probably my fault, as i haven't talked about this much

intel processors store and manipulate numbers in low-order-byte-first fashion

if you define a DWORD value, then load it into a register, you will see the effect

Code Select Expand

    .DATA

Val01  dd 11223344h

;in memory, Val01 looks like this:
; 44 33 22 11
;(hexadecimal format)
;the low-order bytes are at lower addresses

    .CODE

    mov     eax,Val01         ;AL = 44h, AH = 33h, and so on

it simply must be that way for many instructions to work properly
INC is a good example, because if we use the instruction on Val01...

Code Select Expand

    inc     Val01
the low-order byte of Val01 will be incremented
if it rolls over from 0FFh to 0, the second byte will be incremented
if the second byte rolls over from 0FFh to 0, the third byte will be incremented
if the third byte rolls over from 0FFh to 0, the forth byte will be incremented

in order for the instruction to work correctly on a DWORD in memory, the bytes MUST be in little-endian order

to extend from a single DWORD to a longer "string" of DWORD's, we would place the high-order DWORD's at higher addresses

Code Select Expand

Val01  dd 33221100h,77665544h

;Val01 looks like this in memory
; 00 11 22 33 44 55 66 77

if you like, you may post a complete example of your code,
and i (or we) can show you how to do it using little-endian values, without the use of BSWAP