### Author Topic: qword to ascii conversion  (Read 25227 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: 8767
• Still using Abacus 2.0
##### 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
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: 8767
• Still using Abacus 2.0
##### 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:NONEOPTION 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 0AD7B4F1Bhsub esp,__localsmov __saveregs[0*4],ebpmov __saveregs[1*4],esimov __saveregs[2*4],edimov __saveregs[3*4],ebx;;// 64bit x 64bit = 128bit resultmov eax,__cnst_lo;//__y_lo; = b0mul __val_lo;;// get a0*b0 = d1:d0mov esi,eax ;mov __128bittmp[0*4],eax;;//d0mov ecx,edx;;//d1mov eax,__cnst_lo;//__y_lo; = b0xor ebx,ebxmul __val_hi;;// get a1*b0 = e1:e0add ecx,eax;;//e0adc ebx,edx;;//e1mov eax,__cnst_hi;//__y_hi; =b1mul __val_lo;;// get a0*b1 = f1:f0add ecx,eax;;//f0adc ebx,edx;;//f1mov edi,ecx;mov __128bittmp[1*4],ecxmov ecx,0mov eax,__cnst_hi;//__y_hi; =b1adc ecx,ecxmul __val_hi;;// get a1*b1 = g1:g0add eax,ebx;;//g0adc edx,ecx;;//g1mov ebp,__pbuff;// -------------------------------;// -------------------------------xor ebx,ebxadd esi,__correction_loadc edi,__correction_hiadc eax,ebxadc edx,ebx;// first digit 0 or 1, zero not writtenmov ebx,edxsar ebx,31lea ecx,[ebx+'2']mov byte ptr [ebp],clsub ebp,ebxmov __NLZmask,ebx;// second digit, 128 bits needed;// shift 2:;// - account for the first digit;// - multiply by 2shld ebx,edx,2shld edx,eax,2shld eax,edi,2shld edi,esi,2shl esi,2and ebx,1; only bit 0;// mul by 5mov __128bittmp[0*4],esimov __128bittmp[1*4],edimov __128bittmp[2*4],eaxmov __128bittmp[3*4],edxmov ecx,ebxshld ebx,edx,2shld edx,eax,2shld eax,edi,2shld edi,esi,2shl esi,2add 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*5cmp ecx,1sbb ebx,ebxxor ebx,-1add ecx,'0'or __NLZmask,ebxmov byte ptr [ebp],clsub ebp,__NLZmask;// third digit, 128 bits neededxor ebx,ebxadd esi,esiadc edi,ediadc eax,eaxadc edx,edxadc ebx,ebxmov __128bittmp[0*4],esimov __128bittmp[1*4],edimov __128bittmp[2*4],eaxmov __128bittmp[3*4],edxmov ecx,ebxshld ebx,edx,2shld edx,eax,2shld eax,edi,2shld edi,esi,2shl esi,2add esi,__128bittmp[0*4]adc edi,__128bittmp[1*4]adc eax,__128bittmp[2*4]adc edx,__128bittmp[3*4]adc ecx,ebxcmp ecx,1sbb ebx,ebxxor ebx,-1add ecx,'0'or __NLZmask,ebxmov byte ptr [ebp],clsub ebp,__NLZmask;// mul by 10 the rest not using lower qword anymore;184;   46744073709551615REPT 16xor ecx,ecxadd eax,eax;adc edx,edx;adc ecx,ecxmov esi,eax;mov edi,edx;mov ebx,ecxshld ecx,edx,2;shld edx,eax,2;shl eax,2;add eax,esi;adc edx,edi;adc ecx,ebxcmp ecx,1sbb ebx,ebxxor ebx,-1add ecx,'0'or __NLZmask,ebxmov byte ptr [ebp],clsub ebp,__NLZmaskENDMxor ecx,ecxadd eax,eax;adc edx,edx;adc ecx,ecxmov esi,eax;mov edi,edx;mov ebx,ecxshld ecx,edx,2;shld edx,eax,2;shl eax,2;add eax,esi;adc edx,edi;adc ecx,ebxcmp ecx,1sbb ebx,ebxxor ebx,-1add ecx,'0'mov edx,__pbuffor __NLZmask,ebxmov word ptr [ebp],cxsub ebp,__NLZmaskmov eax,ebp;// -------------------------------mov ebp,__saveregs[0*4]mov esi,__saveregs[1*4]mov edi,__saveregs[2*4]mov ebx,__saveregs[3*4]add esp,__localssub eax,edxret 8+4_U64ToStrNLZ endp`

#### dedndave

• Member
• Posts: 8767
• Still using Abacus 2.0
##### 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:DWORDOPTION PROLOGUE:NONEOPTION EPILOGUE:NONElocals = 4*4sub esp,localsmov [esp+0*4],ebpmov [esp+1*4],esimov [esp+2*4],edimov [esp+3*4],ebxmov esi,[esp+1*4][locals]; a0mov edi,[esp+2*4][locals]; a1mov ebp,[esp+3*4][locals]; lpszBuffertest edi,edijnz @Fcall DOFULL32NLZmov eax,ebp; lpszBuffermov ebp,[esp+0*4]mov esi,[esp+1*4]mov edi,[esp+2*4]mov ebx,[esp+3*4]add esp,localssub eax,[esp+3*4]ret 3*4@@:_mul_64x64_top64 0BDEDD5BFh, 0DBE6FECEh; /10000000000shr edi,1mov esi,edijz TOP10ZEROcall DOFULL32NLZ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; *1000000000000 == 02_540BE400h;_mul_32x64_no_overflowmov eax,0540BE400h; = b0mul edilea edx,[2*edi+edx]; hidword is 2;endmmov esi,[esp+1*4][locals]; a0mov edi,[esp+2*4][locals]; a1sub esi,eaxsbb edi,edxmov [esp+1*4][locals],esi; a0mov [esp+2*4][locals],edi; a1mov ebx,esi; a0jnz @F; the rest also fits to 32bit **call DOFULL32LZmov eax,ebp; lpszBuffermov ebp,[esp+0*4]mov esi,[esp+1*4]mov edi,[esp+2*4]mov ebx,[esp+3*4]add esp,localssub eax,[esp+3*4]ret 3*4; ** If it does not there will be no leading zero; so below code also works in this caseTOP10ZERO:mov esi,[esp+1*4][locals]; a0mov edi,[esp+2*4][locals]; a1mov ebx,esi@@:add esi,1adc edi,0_mul_64x64_top64 01B478423h, 0A7C5AC47h; /100000shrd esi,edi,16mov eax,100000mov ecx,esimov esi,ebxmul ecxsub esi,eaxmov eax,68DB9h;2^32/10000mul ecxmov ebx,ecxmov ecx,10call DOFULL32NLZSTARTshrd esi,edi,16mov eax,100000mul esisub ebx,eaxmov ecx,10mov eax,68DB9h;2^32/10000mul esimov esi,ebxcall DOFULL32NLZSTARTmov eax,ebp; lpszBuffermov ebp,[esp+0*4]mov esi,[esp+1*4]mov edi,[esp+2*4]mov ebx,[esp+3*4]add esp,localssub eax,[esp+3*4]ret 3*4;; esi == value;; ebp == bufferDOFULL32NLZ::mov eax,0A7C5AC47h; magic div /100000mul esiadd eax,0A7C5AC47h; correction for 0FFFFFFFFhadc edx,0mov ecx,10shr edx,16imul eax,edx,100000sub esi,eax;/100000 remaindermov ebx,edxmov eax,68DB9h;2^32/10000mul edxDOFULL32NLZSTART:test ebx,ebxjz NEXT5cmp ebx,9999ja DIGIT0cmp ebx,999ja DIGIT1add eax,eaxcmp ebx,99lea eax,[eax*4+eax]ja DIGIT2add eax,eaxcmp ebx,9lea eax,[eax*4+eax]ja DIGIT3add eax,eaxtest ebx,ebxlea eax,[eax*4+eax]jnz DIGIT4NEXT5:mov eax,68DB9h;2^32/10000mul esicmp esi,9999ja DIGIT5cmp esi,999ja DIGIT6add eax,eaxcmp esi,99lea eax,[eax*4+eax]ja DIGIT7add eax,eaxcmp esi,9lea eax,[eax*4+eax]ja DIGIT8lea edx,[esi+'0']jmp DIGIT9DOFULL32LZ:mov eax,0A7C5AC47h; magic div /100000mul esiadd eax,0A7C5AC47h; correction for 0FFFFFFFFhadc edx,0mov ecx,10shr edx,16imul eax,edx,100000sub esi,eax;/100000 remaindermov ebx,edxmov eax,68DB9h;2^32/10000mul edxDIGIT0:add dl,'0'mov [ebp],dlinc ebpi = 1rept 7@CatStr(<DIGIT>,%(i)):if i eq 0; first fiveelseif i eq 5; next fivemov eax,68DB9h;2^32/10000mul esielseif i gt 0mul ecxendifadd dl,'0'mov [ebp],dlinc ebpi = i + 1endmDIGIT8:mul ecxadd dl,'0'mov [ebp],dlinc ebpmul ecxadd dl,'0'DIGIT9:mov [ebp],dxinc ebpretnOPTION PROLOGUE:PROLOGUEDEFOPTION EPILOGUE:EPILOGUEDEFNew_U64ToStr endp%echo New_U64ToStr: @CatStr(%(\$-New_U64ToStr)) bytes; edi::esi *= x_mul_64x64_top64 macro __x_lo:req, __x_hi:reqmov eax,dword ptr __x_lo; = b0mul esi;__y_lo; get a0*b0 = d1:d0mov ecx,edx; d1mov eax,dword ptr __x_hi; = b0mul esi;__y_lo; get a1*b0 = e1:e0add ecx,eax;e0mov esi,0adc esi,edx;e1mov eax,dword ptr __x_lo; =b1mul edi;__y_hi; get a0*b1 = f1:f0add ecx,eax;f0mov eax,dword ptr __x_hi; =b1adc esi,edx;f1mov edx,edimov edi,0adc edi,edimul edx;__y_hi; get a1*b1 = g1:g0add esi,eaxadc edi,edxendmNew_Int64ToStr proc QwValue:QWORD,pBuffer:DWORDmov eax,[esp+1*4];U64.Lomov edx,[esp+2*4];U64.Himov ecx,[esp+3*4];bufftest edx,edxjns New_U64ToStrmov byte ptr [ecx],'-'xor eax,-1xor edx,-1inc ecxadd eax,1adc edx,0invoke New_U64ToStr,edx::eax,ecxinc eaxret 3*4New_Int64ToStr endpNew_Int32ToStr proc dwValue,pBuffermov eax,[esp+4];dwValuemov edx,[esp+8];pBuffertest eax,eaxjns New_U32ToStrmov byte ptr [edx],'-'neg eaxpush ebppush ebxpush esimov esi,eaxlea ebp,[edx+1]call DOFULL32NLZmov eax,ebp;lpszBufferpop esipop ebxpop ebpsub eax,[esp+2*4]; strlenret 2*4New_Int32ToStr endpNew_U32ToStr proc dwValue,pBufferpush ebppush ebxpush esimov esi,[esp+1*4][3*4]; a0mov ebp,[esp+2*4][3*4]; lpszBuffercall DOFULL32NLZmov eax,ebp;lpszBufferpop esipop ebxpop ebpsub eax,[esp+2*4]; strlenret 2*4New_U32ToStr endp`

#### dedndave

• Member
• Posts: 8767
• Still using Abacus 2.0
##### 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: 8767
• Still using Abacus 2.0
##### 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: 8071
• Assembler is fun ;-)
##### 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.dataMyQw 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)) Exitend 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: 8767
• Still using Abacus 2.0
##### 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: 183
##### 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: 8767
• Still using Abacus 2.0
##### 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]
`        .DATAAscBuf  DB      '01234567890123456789',0  ;20 ASCII digits        .CODEAsc64   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,100Asc64a: 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 - doneAsc64b: inc     edi        retAsc64   ENDP`

#### dedndave

• Member
• Posts: 8767
• Still using Abacus 2.0
##### 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
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

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: 8071
• Assembler is fun ;-)
##### 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

Code: [Select]
`include \masm32\MasmBasic\MasmBasic.inc  ; http://masmforum.com/~masm32/board/index.php?topic=94.dataMyQw 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)) Exitend 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