9999 to ASCII

[FORTRANS]

Hi,

   Just for fun, a four multiply version.  The individual ADDS could
be made into one ADD with the buffer.

Regards,

Steve

Code Select Expand


; - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
; BINary to DECimal conversion with multiplies.  Assume unsigned numbers.
; The number in AX is stored to a four digit number buffer.

; September 2008, start double word version.
; September 2009, rework for four digits.

;   INPUT:  EAX contains the four digit number ( 0 ... 9999 ) to be
;           converted to decimal ASCII.
;           EDI points to buffer start.
;    Uses:  EAX, ECX, EDX

Bin2DecM:
        MOV     EDX,00418938H   ; Multiplier to get leading digit of four digit
                                ; number into low byte of EDX (DL).
        MUL     EDX     ; Do a fixed point multiply to get result. 

        ADD     DL,'0'  ; Convert binary to ASCII.
        MOV     [EDI],DL

        MOV     ECX,10  ; Multiplier to get remaining digits.

        MUL     ECX     ; Second digit.

        ADD     DL,'0'
        MOV     [EDI+1],DL

        MUL     ECX

        ADD     DL,'0'
        MOV     [EDI+2],DL

        MUL     ECX

        ADD     DL,'0'
        MOV     [EDI+3],DL

        RET


[dedndave]

we have one like that
this one converts all four bytes at once

;----------------------------------------------------------------
;       code by Drizz
;
;this snippet converts a value in eax from base 10,000
;(0 to 9999) into 4 ASCII numeric characters
;----------------------------------------------------------------
        mov     edx,4294968          ;2^32/1000
        mov     ebx,10               ;per digit
        mul     edx                  ;extend first digit
        mov     ecx,edx              ;digit 1 in CL
        mul     ebx                  ;second digit
        mov     ch,dl                ;digit 2 in CH
        mul     ebx                  ;third digit
;----------------------------------------------------------------
;this section of Drizz's snippet was replaced below
;----------------------------------------------------------------
;;;;    push    edx                  ;save digit 3
;;;;    mul     ebx                  ;forth digit
;;;;    pop     eax                  ;digit 3 in AL
;;;;    mov     ah,dl                ;digit 4 in AH
;;;;    shl     eax,16               ;relocate digits 3 & 4
;;;;    lea     ecx,[eax+ecx+'0000'] ;combine and make ASCII
;----------------------------------------------------------------
;replacement section by DednDave - saves 2 clock cycles ;)
;----------------------------------------------------------------
        bswap   ecx                  ;digits 1 & 2 up high
        mov     ch,dl                ;digit 3 in CH
        mul     ebx                  ;digit 4 in DL
        lea     ecx,[edx+ecx+'0000'] ;combine and make ASCII
        bswap   ecx                  ;re-order bytes
;----------------------------------------------------------------

[dedndave]

Drizz also made this one
i think this is now my all-time second favorite snippet of code
it will handle any value from 0 to 4294967295

;----------------------------------------------------------------
;       code by Drizz
;
;this snippet divides the value in eax by 10000 with remainder
;very cool, Drizz - i really like this piece of code ;)
;----------------------------------------------------------------
;eax = dividend
        mov     ebx,eax              ;original in ebx
        mov     edx,3518437209       ;2^45/10000
        mul     edx                  ;extend quotient
        shr     edx,13               ;quotient
        imul    eax,edx,10000        ;reconstruct for remainder
        sub     ebx,eax              ;remainder=orig-10000*quot
;edx = quotient
;ebx = remainder
;----------------------------------------------------------------

by combining the two "Drizz snippets", we have one that will do 8 digits at a time
(base 100,000,000 to ASCII)

        mov     ebx,eax              ;original in ebx
        mov     edx,3518437209       ;2^45/10000
        mul     edx                  ;extend quotient
        shr     edx,13               ;quotient
        imul    eax,edx,10000        ;reconstruct for remainder
        neg     eax
        push    edx
        add     eax,ebx              ;remainder=orig-10000*quot
        mov     edx,4294968          ;2^32/1000
        mov     ebx,10               ;per digit
        mul     edx                  ;extend first digit
        mov     ecx,edx              ;digit 1 in CL
        mul     ebx                  ;second digit
        mov     ch,dl                ;digit 2 in CH
        mul     ebx                  ;third digit
        bswap   ecx                  ;digits 1 & 2 up high
        mov     ch,dl                ;digit 3 in CH
        mul     ebx                  ;digit 4 in DL
        lea     ecx,[edx+ecx+'0000'] ;combine and make ASCII
        bswap   ecx                  ;re-order bytes
        pop     eax
        mov     [edi+4],ecx
        mov     edx,4294968          ;2^32/1000
        mov     ebx,10               ;per digit
        mul     edx                  ;extend first digit
        mov     ecx,edx              ;digit 1 in CL
        mul     ebx                  ;second digit
        mov     ch,dl                ;digit 2 in CH
        mul     ebx                  ;third digit
        bswap   ecx                  ;digits 1 & 2 up high
        mov     ch,dl                ;digit 3 in CH
        mul     ebx                  ;digit 4 in DL
        lea     ecx,[edx+ecx+'0000'] ;combine and make ASCII
        bswap   ecx                  ;re-order bytes
        mov     [edi],ecx

all we need now is a Drizz snippet to divide 64-bits by 100,000,000   :bg
let me see if i can "do what Drizz would do" - lol
i guess the answer is to use the first snippet 4 times to divide 64 bits

[drizz]

I'm sure i mentioned this tool  by qWord already.

This thread started with 9999 to ascii, now you are talking 64bits; there are plenty of threads discussing dword2ascii/qword2ascii already ... use the search button :P

[drizz]

here it is anyway ...  :8)

Code Select Expand

;; edi::esi == 18446744073709551615
or edi,-1
or esi,-1

mov ebx,esi
_mul_64x64_top64_2 esi, edi, 8461CEFDh, 0ABCC7711h; /100000000
shrd esi,edi,26
shr edi,26
mov eax,100000000
mul esi
sub ebx,eax
; ebx == first 8 digits ("09551615")
; edi::esi == top 12 digits ("184467440737")
mov ebx,esi
_mul_64x64_top64_2 esi, edi, 8461CEFDh, 0ABCC7711h; /100000000
shrd esi,edi,26
imul eax,esi,100000000
sub ebx,eax
; ebx == second 8 digits ("67440737")
; esi == top 4 digits ("1844")

Code Select Expand

; A1::A0 = (A1::A0 * B1::B0) >> 64
_mul_64x64_top64_2 macro A0:req,A1:req, B0:req,B1:req
mov eax,dword ptr B0
mul A0
mov ecx,edx; d1
mov eax,dword ptr B1
mul A0
add ecx,eax;e0
mov A0,0
adc A0,edx;e1
mov eax,dword ptr B0
mul A1
add ecx,eax;f0
mov eax,dword ptr B1
adc A0,edx;f1
mov ecx,0
mov edx,A1
adc ecx,ecx
mul edx
mov A1,ecx
add A0,eax
adc A1,edx
endm

[dedndave]

many thanks, Drizz
none of the previous threads discuss using ling long kai fang - lol - or horners rule, either
at least not for this (it is used all the time for decimal to binary, of course)
what i want to do is compare divide and conquer (which, i am sure has a better name, someplace) with ling long kai fang
i am working on bignum to ascii routines, not just 64-bit
recently, you (Drizz), Jochen, and I all wrote a few 64-bit to ascii routines
i have a few versions of yours around here someplace
i think yours were fastest if i remember

at any rate, i am trying to apply things i have learned along the way
the mul-to-div stuff is great help, of course
my original ling long kai fang code loaded bytes from the input value and output words (base 256 to base 10,000)
the routine i have been working on (when i have time) is an attempt to reading and writing dwords only (a tip from Hutch)
in essence, i am converting base 4,294,967,296 to base 100,000,000
this generates some pretty big "carry" values - lol - but i am working through it
i wish i knew how to write code for sse/sse2 - but that can come later

[drizz]

Use magic divider method.
Magic = CCCCCCCD for 32bit
Magic = CCCCCCCC CCCCCCCD for 64bit
Magic = CCCCCCCC CCCCCCCC CCCCCCCD for 96bit
Magic = (n-1) dup(CCCCCCCC) CCCCCCCD for 32*n-bit

same method as for 32bit unsigned integers.
But the question is: Is using div instruction faster than the overhead of using magic divider?

[dedndave]

i can use mul by constants

in one place, i need to divide a 57 bit value (105_F5DF_FF00_0000h max) by 390,625 with remainder
the resulting quotient can be 38 bits (2B_F31D_9943h max)

i am not sure which one is worse - lol

another one - i need to divide a 59 bit value (5F5_E12A_F31D_9943h max) by 100,000,000 with remainder
the resulting quotient can be 33 bits (1_0000_0734h max)

and the easy one.....

divide a 33 bit value (1_05F5_E0FFh max) by 10,000 with remainder
the resulting quotient can be 19 bits (6_B4C8h max)

i can probably use your previous examples to help
i know how to multiple-precision divide and multiply
at this point, i am writing the routine with DIV's
i have even outlined a fast way to handle signed values
once i get it up and running, i will go back and replace these three critical operations

using the mul-to-div 2 or even 4 times is ok
i like that, because i can split the code off and test all the values
there is no way to test a piece of code that does such large divisions in one step
there are just to many input values to test for

it looks like i might get to spend some time on it, today   :U
i will post the code (DIV version) when i get it tested

[dedndave]

i have started a different thread and posted LLKF version 1...
http://www.masm32.com/board/index.php?topic=12363.new#new