Author Topic: qword to ascii conversion  (Read 20911 times)

allynm

  • Guest
qword to ascii conversion
« on: June 06, 2012, 02:36:32 AM »
Hello all,

I have hunted around for a qword integer to ascii converter in vain.  I know that once upon a time Raymond created something he called qwta, but I've been unable to find it.  No doubt someone else has taken the trouble to do this too, but I've come up empty handed.

Thanks,
Mark Allyn

dedndave

  • Member
  • *****
  • Posts: 8734
  • Still using Abacus 2.0
    • DednDave
Re: qword to ascii conversion
« Reply #1 on: June 06, 2012, 02:50:04 AM »
that's probably my favorite algo to work on - and see the code of others   :P
a lot of time is spent on it because it is fun and interesting

here is one for unsigned integers by Drizz that is pretty fast...

dedndave

  • Member
  • *****
  • Posts: 8734
  • Still using Abacus 2.0
    • DednDave
Re: qword to ascii conversion
« Reply #2 on: June 06, 2012, 02:52:22 AM »
here is an update by Drizz..
Code: [Select]
comment #
- fixed point arithmetic conversion of Unsigned 64 integer to string -
- Multiply 64bit unsigned integer by 2^127/10^19
- make correction to prevent precision loss
- first digit will be at bit offset 127 (0 or 1)
- [1]8446744073709551615, first digit can only be 0 or 1
- after handling the first digit, we get subsequent digits multiplying by 10
- the "point" is moved to end so all other digits are constructed from shifted "out" bits (multiplying by 10)
#

OPTION PROLOGUE:NONE
OPTION EPILOGUE:NONE
_U64ToStrNLZ proc val:QWORD, pbuff:PTR BYTE

__locals equ 4*4+4*4+4;;//4*4=regs + 4*4=128bit temp
__saveregs equ <dword ptr [esp]>
__128bittmp equ <dword ptr [esp+4*4]>
__NLZmask equ <dword ptr [esp+4*4+4*4]>
__val_hi equ <dword ptr [esp+__locals+2*4]>
__val_lo equ <dword ptr [esp+__locals+1*4]>
__pbuff equ <dword ptr [esp+__locals+3*4]>
__cnst_hi equ 0EC1E4A7Dh
__cnst_lo equ 0B69561A5h
__correction_lo equ 0E30437FBh
__correction_hi equ 0AD7B4F1Bh

sub esp,__locals
mov __saveregs[0*4],ebp
mov __saveregs[1*4],esi
mov __saveregs[2*4],edi
mov __saveregs[3*4],ebx

;;// 64bit x 64bit = 128bit result
mov eax,__cnst_lo;//__y_lo; = b0
mul __val_lo;;// get a0*b0 = d1:d0
mov esi,eax ;mov __128bittmp[0*4],eax;;//d0
mov ecx,edx;;//d1
mov eax,__cnst_lo;//__y_lo; = b0
xor ebx,ebx
mul __val_hi;;// get a1*b0 = e1:e0
add ecx,eax;;//e0
adc ebx,edx;;//e1
mov eax,__cnst_hi;//__y_hi; =b1
mul __val_lo;;// get a0*b1 = f1:f0
add ecx,eax;;//f0
adc ebx,edx;;//f1
mov edi,ecx;mov __128bittmp[1*4],ecx
mov ecx,0
mov eax,__cnst_hi;//__y_hi; =b1
adc ecx,ecx
mul __val_hi;;// get a1*b1 = g1:g0
add eax,ebx;;//g0
adc edx,ecx;;//g1
mov ebp,__pbuff
;// -------------------------------
;// -------------------------------
xor ebx,ebx
add esi,__correction_lo
adc edi,__correction_hi
adc eax,ebx
adc edx,ebx

;// first digit 0 or 1, zero not written

mov ebx,edx
sar ebx,31
lea ecx,[ebx+'2']
mov byte ptr [ebp],cl
sub ebp,ebx
mov __NLZmask,ebx

;// second digit, 128 bits needed
;// shift 2:
;// - account for the first digit
;// - multiply by 2

shld ebx,edx,2
shld edx,eax,2
shld eax,edi,2
shld edi,esi,2
shl esi,2
and ebx,1; only bit 0
;// mul by 5
mov __128bittmp[0*4],esi
mov __128bittmp[1*4],edi
mov __128bittmp[2*4],eax
mov __128bittmp[3*4],edx
mov ecx,ebx
shld ebx,edx,2
shld edx,eax,2
shld eax,edi,2
shld edi,esi,2
shl esi,2
add esi,__128bittmp[0*4]
adc edi,__128bittmp[1*4]
adc eax,__128bittmp[2*4]
adc edx,__128bittmp[3*4]
adc ecx,ebx; X*2 + X*5
cmp ecx,1
sbb ebx,ebx
xor ebx,-1
add ecx,'0'
or __NLZmask,ebx
mov byte ptr [ebp],cl
sub ebp,__NLZmask

;// third digit, 128 bits needed
xor ebx,ebx
add esi,esi
adc edi,edi
adc eax,eax
adc edx,edx
adc ebx,ebx
mov __128bittmp[0*4],esi
mov __128bittmp[1*4],edi
mov __128bittmp[2*4],eax
mov __128bittmp[3*4],edx
mov ecx,ebx
shld ebx,edx,2
shld edx,eax,2
shld eax,edi,2
shld edi,esi,2
shl esi,2
add esi,__128bittmp[0*4]
adc edi,__128bittmp[1*4]
adc eax,__128bittmp[2*4]
adc edx,__128bittmp[3*4]
adc ecx,ebx
cmp ecx,1
sbb ebx,ebx
xor ebx,-1
add ecx,'0'
or __NLZmask,ebx
mov byte ptr [ebp],cl
sub ebp,__NLZmask

;// mul by 10 the rest not using lower qword anymore
;184
;   46744073709551615

REPT 16
xor ecx,ecx
add eax,eax;
adc edx,edx;
adc ecx,ecx
mov esi,eax;
mov edi,edx;
mov ebx,ecx
shld ecx,edx,2;
shld edx,eax,2;
shl eax,2;
add eax,esi;
adc edx,edi;
adc ecx,ebx
cmp ecx,1
sbb ebx,ebx
xor ebx,-1
add ecx,'0'
or __NLZmask,ebx
mov byte ptr [ebp],cl
sub ebp,__NLZmask
ENDM

xor ecx,ecx
add eax,eax;
adc edx,edx;
adc ecx,ecx
mov esi,eax;
mov edi,edx;
mov ebx,ecx
shld ecx,edx,2;
shld edx,eax,2;
shl eax,2;
add eax,esi;
adc edx,edi;
adc ecx,ebx
cmp ecx,1
sbb ebx,ebx
xor ebx,-1
add ecx,'0'
mov edx,__pbuff
or __NLZmask,ebx
mov word ptr [ebp],cx
sub ebp,__NLZmask
mov eax,ebp
;// -------------------------------
mov ebp,__saveregs[0*4]
mov esi,__saveregs[1*4]
mov edi,__saveregs[2*4]
mov ebx,__saveregs[3*4]
add esp,__locals
sub eax,edx
ret 8+4
_U64ToStrNLZ endp

dedndave

  • Member
  • *****
  • Posts: 8734
  • Still using Abacus 2.0
    • DednDave
Re: qword to ascii conversion
« Reply #3 on: June 06, 2012, 02:56:02 AM »
and another update by Drizz...
Code: [Select]
;*****************************************************************
;
; uint64-to-string:
;
; split the uint64 value to two 10-digit numbers by magic divider method
; if possible use uint32-to-string nested subroutine, upper 10-digits will
; always fit to 32bit, but lower 10-digit must be adjusted dividing by 10
; (again with magic divider method), then the remainder can be passed to
; uint32-to-string.
;
; uint32-to-string:
;
; split the uint32 value to two 5-digit numbers by magic divider method,
; then scale the 5-digit part by 2^32/10000 (68DB9h) to get decimal
; digit in edx (upper dword) after multiplication, subsequent digits
; are got multiplying by 10
;
;*****************************************************************

New_U64ToStr proc Value:QWORD, lpszBuffer:DWORD
OPTION PROLOGUE:NONE
OPTION EPILOGUE:NONE
locals = 4*4

sub esp,locals
mov [esp+0*4],ebp
mov [esp+1*4],esi
mov [esp+2*4],edi
mov [esp+3*4],ebx
mov esi,[esp+1*4][locals]; a0
mov edi,[esp+2*4][locals]; a1
mov ebp,[esp+3*4][locals]; lpszBuffer
test edi,edi
jnz @F
call DOFULL32NLZ
mov eax,ebp; lpszBuffer
mov ebp,[esp+0*4]
mov esi,[esp+1*4]
mov edi,[esp+2*4]
mov ebx,[esp+3*4]
add esp,locals
sub eax,[esp+3*4]
ret 3*4
@@:
_mul_64x64_top64 0BDEDD5BFh, 0DBE6FECEh; /10000000000

shr edi,1
mov esi,edi
jz TOP10ZERO

call DOFULL32NLZ
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; *1000000000000 == 02_540BE400h
;_mul_32x64_no_overflow
mov eax,0540BE400h; = b0
mul edi
lea edx,[2*edi+edx]; hidword is 2
;endm

mov esi,[esp+1*4][locals]; a0
mov edi,[esp+2*4][locals]; a1
sub esi,eax
sbb edi,edx
mov [esp+1*4][locals],esi; a0
mov [esp+2*4][locals],edi; a1
mov ebx,esi; a0
jnz @F
; the rest also fits to 32bit **
call DOFULL32LZ
mov eax,ebp; lpszBuffer
mov ebp,[esp+0*4]
mov esi,[esp+1*4]
mov edi,[esp+2*4]
mov ebx,[esp+3*4]
add esp,locals
sub eax,[esp+3*4]
ret 3*4

; ** If it does not there will be no leading zero
; so below code also works in this case
TOP10ZERO:
mov esi,[esp+1*4][locals]; a0
mov edi,[esp+2*4][locals]; a1
mov ebx,esi
@@:
add esi,1
adc edi,0
_mul_64x64_top64 01B478423h, 0A7C5AC47h; /100000
shrd esi,edi,16
mov eax,100000
mov ecx,esi
mov esi,ebx
mul ecx
sub esi,eax
mov eax,68DB9h;2^32/10000
mul ecx
mov ebx,ecx
mov ecx,10
call DOFULL32NLZSTART

shrd esi,edi,16
mov eax,100000
mul esi
sub ebx,eax
mov ecx,10
mov eax,68DB9h;2^32/10000
mul esi
mov esi,ebx
call DOFULL32NLZSTART

mov eax,ebp; lpszBuffer
mov ebp,[esp+0*4]
mov esi,[esp+1*4]
mov edi,[esp+2*4]
mov ebx,[esp+3*4]
add esp,locals
sub eax,[esp+3*4]
ret 3*4

;; esi == value
;; ebp == buffer
DOFULL32NLZ::
mov eax,0A7C5AC47h; magic div /100000
mul esi
add eax,0A7C5AC47h; correction for 0FFFFFFFFh
adc edx,0
mov ecx,10
shr edx,16
imul eax,edx,100000
sub esi,eax;/100000 remainder
mov ebx,edx
mov eax,68DB9h;2^32/10000
mul edx
DOFULL32NLZSTART:
test ebx,ebx
jz NEXT5
cmp ebx,9999
ja DIGIT0
cmp ebx,999
ja DIGIT1
add eax,eax
cmp ebx,99
lea eax,[eax*4+eax]
ja DIGIT2
add eax,eax
cmp ebx,9
lea eax,[eax*4+eax]
ja DIGIT3
add eax,eax
test ebx,ebx
lea eax,[eax*4+eax]
jnz DIGIT4
NEXT5:
mov eax,68DB9h;2^32/10000
mul esi
cmp esi,9999
ja DIGIT5
cmp esi,999
ja DIGIT6
add eax,eax
cmp esi,99
lea eax,[eax*4+eax]
ja DIGIT7
add eax,eax
cmp esi,9
lea eax,[eax*4+eax]
ja DIGIT8
lea edx,[esi+'0']
jmp DIGIT9

DOFULL32LZ:
mov eax,0A7C5AC47h; magic div /100000
mul esi
add eax,0A7C5AC47h; correction for 0FFFFFFFFh
adc edx,0
mov ecx,10
shr edx,16
imul eax,edx,100000
sub esi,eax;/100000 remainder
mov ebx,edx
mov eax,68DB9h;2^32/10000
mul edx

DIGIT0:
add dl,'0'
mov [ebp],dl
inc ebp
i = 1
rept 7
@CatStr(<DIGIT>,%(i)):
if i eq 0; first five
elseif i eq 5; next five
mov eax,68DB9h;2^32/10000
mul esi
elseif i gt 0
mul ecx
endif
add dl,'0'
mov [ebp],dl
inc ebp
i = i + 1
endm
DIGIT8:
mul ecx
add dl,'0'
mov [ebp],dl
inc ebp
mul ecx
add dl,'0'
DIGIT9:
mov [ebp],dx
inc ebp
retn
OPTION PROLOGUE:PROLOGUEDEF
OPTION EPILOGUE:EPILOGUEDEF
New_U64ToStr endp
%echo New_U64ToStr: @CatStr(%($-New_U64ToStr)) bytes

; edi::esi *= x
_mul_64x64_top64 macro __x_lo:req, __x_hi:req
mov eax,dword ptr __x_lo; = b0
mul esi;__y_lo; get a0*b0 = d1:d0
mov ecx,edx; d1
mov eax,dword ptr __x_hi; = b0
mul esi;__y_lo; get a1*b0 = e1:e0
add ecx,eax;e0
mov esi,0
adc esi,edx;e1
mov eax,dword ptr __x_lo; =b1
mul edi;__y_hi; get a0*b1 = f1:f0
add ecx,eax;f0
mov eax,dword ptr __x_hi; =b1
adc esi,edx;f1
mov edx,edi
mov edi,0
adc edi,edi
mul edx;__y_hi; get a1*b1 = g1:g0
add esi,eax
adc edi,edx
endm

New_Int64ToStr proc QwValue:QWORD,pBuffer:DWORD
mov eax,[esp+1*4];U64.Lo
mov edx,[esp+2*4];U64.Hi
mov ecx,[esp+3*4];buff
test edx,edx
jns New_U64ToStr
mov byte ptr [ecx],'-'
xor eax,-1
xor edx,-1
inc ecx
add eax,1
adc edx,0
invoke New_U64ToStr,edx::eax,ecx
inc eax
ret 3*4
New_Int64ToStr endp

New_Int32ToStr proc dwValue,pBuffer
mov eax,[esp+4];dwValue
mov edx,[esp+8];pBuffer
test eax,eax
jns New_U32ToStr
mov byte ptr [edx],'-'
neg eax
push ebp
push ebx
push esi
mov esi,eax
lea ebp,[edx+1]
call DOFULL32NLZ
mov eax,ebp;lpszBuffer
pop esi
pop ebx
pop ebp
sub eax,[esp+2*4]; strlen
ret 2*4
New_Int32ToStr endp

New_U32ToStr proc dwValue,pBuffer
push ebp
push ebx
push esi
mov esi,[esp+1*4][3*4]; a0
mov ebp,[esp+2*4][3*4]; lpszBuffer
call DOFULL32NLZ
mov eax,ebp;lpszBuffer
pop esi
pop ebx
pop ebp
sub eax,[esp+2*4]; strlen
ret 2*4
New_U32ToStr endp

dedndave

  • Member
  • *****
  • Posts: 8734
  • Still using Abacus 2.0
    • DednDave
Re: qword to ascii conversion
« Reply #4 on: June 06, 2012, 02:57:56 AM »
and here is one by Paul Dixon, with some speed-ups by lingo...
supposedly, slightly faster that Drizz's - but i like Drizz's methods a little better

dedndave

  • Member
  • *****
  • Posts: 8734
  • Still using Abacus 2.0
    • DednDave
Re: qword to ascii conversion
« Reply #5 on: June 06, 2012, 03:45:03 AM »
here are some routines that i wrote that will handle integers of variable sizes

http://masm32.com/board/index.php?topic=222.0

jj2007

  • Member
  • *****
  • Posts: 7549
  • Assembler is fun ;-)
    • MasmBasic
Re: qword to ascii conversion
« Reply #6 on: June 06, 2012, 04:41:02 AM »
I have hunted around for a qword integer to ascii converter in vain.

Which kind of qword?

Code: [Select]
include \masm32\MasmBasic\MasmBasic.inc
.data
MyQw QWORD 1234567890123456789
Init
Print Str$("Plain mem:\t%i\n", MyQw)
mov eax, dword ptr MyQw
mov edx, dword ptr MyQw[4]
Print Str$("Reg pair:\t%i\n", edx::eax)
movlps xmm0,  MyQw
Print Str$("Xmm reg:\t%i\n", xmm0)
fild MyQw
Inkey Str$("Fpu reg:\t%i\n", ST(0))
Exit
end start

allynm

  • Guest
Re: qword to ascii conversion
« Reply #7 on: June 06, 2012, 07:33:35 AM »
Hi Dedndave and JJ,

As always, you guys are extraordinarily helpful.  Plenty to chew on in what you kindly sent.  Not entirely sure what JJ's question about "what kind of qword" I had in mind quite meant.  I was thinking specifically of a positive or negative integer or unsigned integer, not a REAL8. 

Regards,
Mark

dedndave

  • Member
  • *****
  • Posts: 8734
  • Still using Abacus 2.0
    • DednDave
Re: qword to ascii conversion
« Reply #8 on: June 06, 2012, 08:51:45 AM »
i think he meant signed or unsigned
normally, you can make an unsigned routine do signed integers with a little modification

if the value is negative, you can either:
1) remove the sign bit, evaluate as unsigned, then place the minus sign in front, if negative
or
2) invert the value and add 1 if it is negative - then do the sign thing as in (1)

raymond

  • Member
  • **
  • Posts: 172
    • Raymond's page
Re: qword to ascii conversion
« Reply #9 on: June 06, 2012, 10:02:55 AM »
If you have access to the latest version of the Fpulib, it contains umqtoa (for unsigned qword to ascii) and smqtoa (for signed qword to ascii). Both are described in the latest Fpulib help file. The source code of the modules is also included in the latest library package v2_341 downloadable from:
http://www.ray.masmcode.com/fpu.html#fpulib

Before you ask, the "m" stands for "multiply-instead-of-divide".
Whenever you assume something, you risk being wrong half the time.
http://www.ray.masmcode.com/

allynm

  • Guest
Re: qword to ascii conversion
« Reply #10 on: June 06, 2012, 10:44:50 AM »
Hi Dave, Raymond, and indirectly, Drizz.

Thanks.  Looking over Drizz's code it is clear that this problem is even tougher to solve than I originally thought.  Incidentally, I did not have the latest copy of Fpulib so I was unaware of umqtoa or smqtoa.  Thanks, Raymond.

Regards,
Mark

dedndave

  • Member
  • *****
  • Posts: 8734
  • Still using Abacus 2.0
    • DednDave
Re: qword to ascii conversion
« Reply #11 on: June 06, 2012, 11:06:32 AM »
it really isn't as complex as it may seem
the guys that wrote these routines went to great lengths to make them as fast as is practical
that means that they use multiply-to-divide code and/or look-up-tables

here is some simple code that isn't nearly as fast as the others
Code: [Select]
        .DATA

AscBuf  DB      '01234567890123456789',0  ;20 ASCII digits

        .CODE

Asc64   PROC

;Convert 64-bit unsigned integer to ASCII decimal string
;
;Call With: EDX:EAX= QWORD value to convert
;
;  Returns: EDI= Offset into AscBuf of first numchar

        std
        mov     edi,offset AscBuf+18
        mov     ecx,edx
        xchg    eax,esi
        mov     ebx,100

Asc64a: xor     edx,edx
        xchg    eax,ecx
        div     ebx
        xchg    eax,ecx
        xchg    eax,esi
        div     ebx
        xchg    eax,esi
        xchg    eax,edx
        aam
        xchg    al,ah
        or      ax,3030h
        stosw
        mov     eax,ecx
        or      eax,esi
        jnz     Asc64a

        inc     edi
        inc     edi
        cld
        cmp byte ptr [edi],30h       ;leading 0 ?
        jz      Asc64b               ;yes - supress it

        ret                          ;no - done

Asc64b: inc     edi
        ret

Asc64   ENDP

dedndave

  • Member
  • *****
  • Posts: 8734
  • Still using Abacus 2.0
    • DednDave
Re: qword to ascii conversion
« Reply #12 on: June 06, 2012, 11:11:49 AM »
what makes the 64-bit case interesting on 32-bit machines is the magnitude of the quotient
that is - if you choose to divide
it is really easy to run into a divide overflow problem   :P
notice that, in that last one i posted, i used multiple precision division to avoid this

another thing that makes it fun...
there is no way to perform a 100% functional test
there are just too many values to run through
i think i calculated something like 400 years to run through them all on my machine   :biggrin:

you have to use a certain amount of infered logic in verification
make sure all the pieces work - then make sure they are put together correctly
when you're done - test some known problematic values and move on

jj2007

  • Member
  • *****
  • Posts: 7549
  • Assembler is fun ;-)
    • MasmBasic
Re: qword to ascii conversion
« Reply #13 on: June 06, 2012, 02:59:19 PM »
Not entirely sure what JJ's question about "what kind of qword" I had in mind quite meant.  I was thinking specifically of a positive or negative integer or unsigned integer, not a REAL8.

Hi Mark,
My snippet is just a demo of the various representations of a QWORD integer: in memory, in a reg32:reg32 pair, in the lower half of an XMM register, in the FPU. If you want the Str$() macro to treat them as unsigned, replace the %i below with %u.

Under the hood is (inter alia, the routine is relatively big) a qword to ascii algo by drizz (old link).
Str$ supports even simple algebra:
Code: [Select]
MyQw QWORD -1234567890123456789
..
mov eax, 1000000000
Print Str$("MyQw/eax=\t%If\n", MyQw/eax)

MyQw/eax = -1234567890.12345679

Speed is rarely a problem. Str$() is an allrounder and as such not the fastest algo around but still much faster than the C equivalents. If you need to output a Million strings in an innermost loop, drizz' original algo is a good candidate :t

Code: [Select]
include \masm32\MasmBasic\MasmBasic.inc  ; http://masmforum.com/~masm32/board/index.php?topic=94
.data
MyQw QWORD -1234567890123456789
Init
Print Str$("Plain mem:\t%i\n", MyQw)
mov eax, dword ptr MyQw
mov edx, dword ptr MyQw[4]
Print Str$("Reg pair:\t%i\n", edx::eax)
movlps xmm0,  MyQw
Print Str$("Xmm reg:\t%i\n", xmm0)
fild MyQw
Inkey Str$("Fpu reg:\t%i\n", ST(0))
Exit
end start

allynm

  • Guest
Re: qword to ascii conversion
« Reply #14 on: June 06, 2012, 11:08:41 PM »
Hi Dave, JJ,

I tried Dave's code and it runs very nicely.  I'm not a speed person so this dimension doesn't matter as much to me as ease of understanding.  Dave's code fits nicely inside a OLLY window and so its relatively easy to follow.  This is just a practical concern for a novice like me. 

JJ:  I have to download MasmBasic--something I should have done some time ago.  I will do so and give yours a try.

I also still have to do Raymond's. 

Thanks all.

Mark