ascii adder

[zedd151]

Just for fun, I once made a procedure that adds two unsigned ascii decimal numbers.

I couldn't find the original version, so I rewrote it today. I wanted to find a better way
but still using only registers (no external calls, SSE, MMX, etc)

I'm sure the coding gurus here can find a better method.

bugfix

This is the only version that works 100% regardless of input string size. one string could be 1 byte and the other 1,000's of bytes and will work properly. (The console input version also works AFAIK 100% also.)

During the optimizations however that accuracy was lost, and the new 'optimised' algo would
only work on input strings of the same length.

Code Select Expand




        include \masm32\include\masm32rt.inc

        asciiadder PROTO :DWORD, :DWORD, :DWORD

    .data
       align 4
       asciinumber1 db 1024 dup (39h)
       dd 0
       align 4
       asciinumber2 db 1024 dup (39h)
       db 3 dup (0)
       align 4
       asciidest    db 1024 dup (0)
       db 4 dup (0)

    .code

    start:

        print offset asciinumber1, 13, 10, 13, 10
        print chr$("plus"), 13, 10, 13, 10
        print offset asciinumber2, 13, 10, 13, 10
        print chr$("equals"), 13, 10, 13, 10

        invoke asciiadder, addr asciinumber1, addr asciinumber2, addr asciidest
        print offset asciidest, 13, 10

        inkey
        exit

    OPTION PROLOGUE:NONE
    OPTION EPILOGUE:NONE
    align 16
    nops 13
    asciiadder proc src1:dword, src2:dword, dst:dword
        push ebp
        push ebx
        push esi
        push edi
        mov esi, [esp+14h]
        mov ebp, [esp+18h]
        mov edi, [esp+1Ch]
       
        invoke StrLen, ebp
        mov ebx, eax
       
        invoke StrLen, esi
        mov ecx, eax
       
        cmp ecx, ebx ;  effectively right aligning all strings - then work our way left
        jl ebxgr
        mov edx, ecx
        jmp setdst
        ebxgr:
        mov edx, ebx

        setdst:
        inc edx                         ; add an extra byte for potential carry

    calc:
        mov al, 0
        cmp ecx, -1
        js @f
        mov al, byte ptr [esi+ecx]
        @@:
        cmp ebx, -1
        js @f
        add al, byte ptr [ebp+ebx]
        @@:
        sub al, 30h
        cmp al, 0Fh
        jl @f
        sub al, 30h
        @@:
        cmp al, 0Ah
        jl @f
        sub al, 0Ah
        inc byte ptr [edi+edx-1]
        @@:

        add al, 30h
        add al, byte ptr [edi+edx]

        cmp al, 39h
        jng @f
        sub al, 0Ah
        inc byte ptr [edi+edx-1]
        @@:
        mov byte ptr [edi+edx], al

        dec ebx
        dec ecx
        dec edx
    jnz calc
        cmp byte ptr [edi+edx], 30h     ; test to see if first byte in dest is the carry byte
        jg @f
        add byte ptr [edi], 30h         ; if so, convert to ascii
        @@:
        pop edi
        pop esi
        pop ebx
        pop ebp
        ret 12
    asciiadder endp
    OPTION PROLOGUE:PrologueDef
    OPTION EPILOGUE:EpilogueDef


    end start
   


final version attached

[dedndave]

did you consider using the AAA instruction ?

[zedd151]

did you consider using the AAA instruction ?

:P

Code Select Expand



        add al, byte ptr [ebp+ebx]
        @@:
        aaa
        add al, 30h
        mov byte ptr [edi+edx], al
        mov byte ptr [edi+edx-1], ah
        @@:





something like that?

Nope that's not right.
The first result looked ok (using AAA), but tried other input values.....
And the result wasn't right, my implementation was somehow wrong.
thinking....

[zedd151]

Okay, thats ok, but I know there has to be a fool-proof way to do it 4 bytes at a time.
But the endian-ness also gets in the way. (don't want to use bswap for obvious reasons)

lemme think on it...

trouble is the way I'm doing it, I'm using up all the registers.
I don't really want to use local variables.

and eax, 30303030h ?

thinking....

[zedd151]

Okay, I tried different things using all of eax, to try to add 4 bytes at a time.
The results were less than good.

Hmmm.....

[dedndave]

i'm sure there is - lol

if you want a faster byte-oriented routine, though...
you could use a look-up-table
any 2 numeric ascii bytes can only have 1 of 20 possible results (if you include previous carry)
so table with 20 values - some way to set carry or something
maybe double the result values and set the low bit to carry a one
you pick up the result, and shift right - sets the carry flag for the next operation

[zedd151]

hmmm, lookup table. Thats a possibility.

My implementation of AAA was wrong somehow. It looked good in olly, even carried in the right
place but.....  ;)

The results were not correct

I'm still looking for another way

The original version is the best (accurate) I have so far.

[zedd151]

Adding a very large pair of numbers. They don't have to be equal length, btw. I just did it here as an example. Using the original version, with a 256 byte destinatination buffer.

Code Select Expand


123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789

plus

123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890

equals

0246913578135802468024691357013580245912469134802358023691346912580245801469135690358024679246913578135802468024691357013580245912469134802358023691346912580245801469135690358024679


It may not be the fastest method, but it gets the job done.  8)

Now to get a pencil and paper to verify the results. I don't have a calculator that will work with such large numbers.   

If this is good, I will do one for subtraction, the if that turns out well,
I will *attempt* to make one for multiplication and division.  :shock:

[zedd151]

Full console input and output added:

Code Select Expand




    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    ;;                                                                            ;;
    ;;  asciiadder :: takes two unsigned ascii decimal strings and adds them      ;;
    ;;  designed to add very long numbers. Surely an easier way, but it was fun.  ;;
    ;;                                                                            ;;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    ;;                                        ;;
    ;;  build with console assemble and link  ;;
    ;;                                        ;;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


    include \masm32\include\masm32rt.inc

    asciiadder PROTO :DWORD, :DWORD, :DWORD
   
    zinput MACRO prompt:VARARG
      LOCAL txt
      LOCAL buffer
      IFNB <prompt>
        .data
          txt db prompt, 0
          align 4
        .data?
          buffer db 2052 dup (?)
          align 4
        .code
        invoke StdOut,ADDR txt
        invoke StdIn,ADDR buffer,2048
        mov BYTE PTR [buffer+eax], 0
        invoke StripLF,ADDR buffer
        EXITM <OFFSET buffer>
      ELSE
        .data?
          buffer db 2052 dup (?)
          align 4
        .code
        invoke StdIn,ADDR buffer,2048
        mov BYTE PTR [buffer+eax], 0
        invoke StripLF,ADDR buffer
        EXITM <OFFSET buffer>
      ENDIF
    ENDM


    .data
       align 4
;        asciinumber1 db 2048 dup (0)
       lpstring1 dd 0
       
       align 4
;        asciinumber2 db 2048 dup (0)
       lpstring2 dd 0
       
       align 4
       asciidest    db 2048 dup (0)
       db 4 dup (0)

    .code

    start:

        ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
        ;;                                    ;;
        ;;  get first number from user input  ;;
        ;;                                    ;;
        ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
       
        print "enter first number - 2048 digits max", 13, 10
        mov lpstring1, zinput()
        invoke locate,0,4
       
        ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
        ;;                                      ;;
        ;;   get second number from user input  ;;
        ;;                                      ;;
        ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
       
        print "enter second number - 2048 digits max", 13, 10
        mov lpstring2, zinput()
        invoke locate,0,8

        cls     ;   clear the screen to get the inputting outta the way

        ;;;;;;;;;;;;;;;;;;;;;;;;;;;
        ;;                       ;;
        ;;  print full equation  ;;
        ;;                       ;;
        ;;;;;;;;;;;;;;;;;;;;;;;;;;;
       
        print lpstring1, 13, 10, 13, 10
        print chr$("plus"), 13, 10, 13, 10
        print lpstring2, 13, 10, 13, 10


        ;;;;;;;;;;;;;;;;;;;;;;;;;;;;
        ;;                        ;;
        ;;  perform the addition  ;;
        ;;                        ;;
        ;;;;;;;;;;;;;;;;;;;;;;;;;;;;
       
        invoke asciiadder, lpstring1, lpstring2, addr asciidest

        ;;;;;;;;;;;;;;;;;;;;;;;;;
        ;;                     ;;
        ;;  print the results  ;;
        ;;                     ;;
        ;;;;;;;;;;;;;;;;;;;;;;;;;
       
        print chr$("equals"), 13, 10, 13, 10
        print offset asciidest, 13, 10

        inkey
        exit

    OPTION PROLOGUE:NONE
    OPTION EPILOGUE:NONE
    align 16
    nops 13
    asciiadder proc src1:dword, src2:dword, dst:dword
        push ebp
        push ebx
        push esi
        push edi
        mov esi, [esp+14h]
        mov ebp, [esp+18h]
        mov edi, [esp+1Ch]
        xor ecx, ecx
        @@:
        cmp byte ptr [esi+ecx+1], 0     ; get the last ascii byte
        jz @f
        inc ecx
        jmp @b
        @@:

        xor ebx, ebx
        @@:
        cmp byte ptr [ebp+ebx+1], 0     ; get the last ascii byte
        jz @f
        inc ebx
        jmp @b
        @@:

        cmp ecx, ebx ;  effectively right aligning all strings - then work our way left
        jl ebxgr
        mov edx, ecx
        jmp setdst
        ebxgr:
        mov edx, ebx

        setdst:
        inc edx                         ; add an extra byte for potential carry

    calc:
        mov al, 0
        cmp ecx, -1
        js @f
        mov al, byte ptr [esi+ecx]
        @@:
        cmp ebx, -1
        js @f
        add al, byte ptr [ebp+ebx]
        @@:
        sub al, 30h
        cmp al, 0Fh
        jl @f
        sub al, 30h
        @@:
        cmp al, 0Ah
        jl @f
        sub al, 0Ah
        inc byte ptr [edi+edx-1]
        @@:

        add al, 30h
        add al, byte ptr [edi+edx]

        cmp al, 39h
        jng @f
        sub al, 0Ah
        inc byte ptr [edi+edx-1]
        @@:
        mov byte ptr [edi+edx], al

        dec ebx
        dec ecx
        dec edx
    jnz calc
        cmp byte ptr [edi+edx], 30h     ; test to see if first byte in dest is the carry byte
        jg @f
        add byte ptr [edi], 30h         ; if so, convert to ascii
        @@:
        pop edi
        pop esi
        pop ebx
        pop ebp
        ret 12
    asciiadder endp
    OPTION PROLOGUE:PrologueDef
    OPTION EPILOGUE:EpilogueDef


    end start



Still trying to make the routine a bit faster....
But for demonstration purposes, it is fine as is, I suppose.

Using modified 'input()' macro, allowing up to 2048 digit input

Code Select Expand


72687256878728728578278273764572634567527634762347624623645268275497274697367264
59726597629769726979767654976479567269726957629764592769247629767629347697676576
876587872876575764578568745687564758756

plus

10101010101010101010101010101010101010101010101010101010101010101010101010101010
10101010101100110101010101010010100101001010101001010010100100101010010100101001
010100101001010010100101001010010100101001010010010100100101

equals

01010101010101010101017369735788882973867928837477467364466853773577244863472465
53692855982856984682746982760763986982798077775597748957736982705863977469287024
8639867730348707686676977588882886675865579578755697664858857


[zedd151]

cycle counts using one of dedndaves templates  adding two, 256 digit ascii strings

Code Select Expand


5498
5499
5497
5500
5499
5501
5495
5498
5501
5498


still working, trying to make it faster, but so far no luck
I can make it faster, but accuracy is questionable.

[dedndave]

i would take one of two approaches
and, you'd have to test them to see which is fastest

one approach, seeing as you know the length of the longest input string,
you can estimate the length of the output string
and from that, you can calculate the size of a binary integer that would contain it

zero the required dwords on the stack
you can keep a running binary total in a register
when it overflows 32 bits, you will get a carry flag
at that time, you add the dword (with required carries) to the large integer on the stack
zero the accumulator register and start over until the input values are done

after all that, use a routine to convert the large integer to an ascii decimal string
the thinking behind this method is to eliminate un-aligned (probably byte) writes while processing the strings
my Ling Long Kai Fang routines can crank out the big ascii string - pretty fast, too
seems like a lot of code to write though - lol

the other way is the look-up table i mentioned earlier
when you add two ascii decimal digits together (plus a possible previous carry bit),
the end results will be values from 60h to 73h, inclusive
so, make a table with 20 byte values in it
access the table for the result rather than all that add/subtract stuff

this will give you an idea what the loop might look like

Code Select Expand

TopOfLoop:
    movzx   edx,byte ptr [esi]
    adc     dl,byte ptr [ebx]         ;with carry flag from previous loop pass
    mov     al,MyTable[edx-60h]
    shr     eax,1                     ;the carry flag is used on the next loop pass
    mov     MyDest[edi-1],al
    dec     esi
    dec     ebx
    dec     edi
    jnz     TopOfLoop

[zedd151]

It's true, you never pass up the chance to say "Ling Long Kai Fang". 

Yeah, I've been kicking around some ideas here myself. Even experimented using a lookup table
as you had suggested earlier.

I'll come up with something...

Can't be that hard, but at the moment my mind brain isn't yet connecting the dots.






Eventually.

[dedndave]

i guess that loop needs a little work, as you would loop on the length of the shortest input value, not the output string
at the end, you'll have a carry bit to ripple through the remaining bytes of the longer value

[zedd151]

I did a quick search to find this ling long kai fang that I've heard you mention several times, and I'm looking at it at the moment......

Code Select Expand


;bignum integer to string - by DednDave
;ling long kai fang......

2009, is that the only version (LLKF9_1a)?

[dedndave]

there were previous versions, LLKF8_1 and LLKF9_1
inside the LLKF9_1a package, you will find 3 versions of the routine:

one is for signed values
one is for unsigned values
one will handle either type (an extra argument to tell it which mode)