as i mentioned in a previous post, yahoo is shutting down geocities free webhosting (scheduled for Oct 26th, 2009)
as such, i have been rifling through all my geocities bookmarks and trying to extract any "goodies" i may want later on
some of my bookmarks are for code tricks and tips
while following some of the links, i found this little jewel
compressed, it is small enough to share on a forum link
of course, there has been a recent trend of multiplying to divide
this is not a new technique, at all
but it has seen some recent popularity
this PDF shows some extensions on the idea
[attachment deleted by admin]
Thanks, I actually was looking recently for div_by_10 substitution.
But .. I doubt that it would be faster :lol w/o div instruction.
Anyway this kind of brain-food taste good :}
i am working on a division by 10 also
or division by 100, actually (i will use AAM to convert 2 digits at once)
the problem with multiplying to divide is that the remainder is not typically sought
the remainder information is there, it just has to be re-multiplied
i am working on a solution
i am trying to make a fast 64-bit unsigned integer to decimal ascii routine without using the FPU
i have a good working routine, now, but i am trying to improve on it
hope you'll share it soon with some comparison results :U
i'd be happy to send you my current routine - lol
i intend to write a little paper on it, as well, before sharing it with the masm32 community
Quote from: dedndave on June 28, 2009, 07:22:28 PM
i'd be happy to send you my current routine - lol
i intend to write a little paper on it, as well, before sharing it with the masm32 community
You know drizz' version (http://www.masm32.com/board/index.php?topic=9857.msg72422#msg72422), I suppose... I am eager to see some timings :bg
well, yes, but his uses mmx
i would be interested to see how fast my current virgin is
i think it will be surprising
also, mine is written to pass the qword in edx:eax and saves no registers
adding push's/pop's is easy enough
i need someone who is familiar with the current set of timing macros - lol
Was that a typo or a Freudian slip? :bg
And drizz's routine isn't mmx.
lol
so it isn't
that thing sure is fast - gonna be hard to improve on it
Quote from: dedndave on June 29, 2009, 01:57:51 AMthat thing sure is fast - gonna be hard to improve on it
well, i can try... ::)
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
Hi drizz-
What's the license on your routine? Every good one I've found so far (e.g.. jj's float$, Raymond's fbulib) prohibits commercial usage, something I just can't understand.
i have one you may use freely - it uses the standard multiple precision division method
not even close to being as fast as the one Drizz wrote, though - lol
(mine is smaller - lol - big deal)
.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
Quote from: Jimg on June 29, 2009, 04:32:36 PMWhat's the license on your routine? Every good one I've found so far (e.g.. jj's float$, Raymond's fbulib) prohibits commercial usage, something I just can't understand.
All source code posted on this forum under alias "drizz" is in the public domain.
here is some comparison timing
although, there seems to be a flaw someplace
still, Drizz's routine will be about 7 times faster than mine
i think i can convert my method a bit
i may not beat Drizz, but i can get somewhere in the same galaxy - lol
[attachment deleted by admin]
Quote from: Jimg on June 29, 2009, 04:32:36 PM
Hi drizz-
What's the license on your routine? Every good one I've found so far (e.g.. jj's float$, Raymond's fbulib) prohibits commercial usage, something I just can't understand.
It's not that complicated: Once code is posted here as "public domain", the original authors will not accept to see it copyrighted by somebody who asks money for it...
dedndave,
my proc is only optimal, there is even faster routine by lingo but you'll have to search the board for it...
Copyrighted, and used in a copyrighted program, are two entirely different things.
A copyrighted work may include any number of other copyrighted segments without affecting the original copyrights.
However, prohibiting use of a routine in a commercial program simply because it is commercial, is somewhat disingenuous.
For what it's worth, I'm with Drizz. Any code posted by me on this forum is hereby released to the public domain and may be freely used for any purpose without restrictions or requiring reference as to origin.
Quote from: Jimg on June 29, 2009, 07:49:04 PM
Copyrighted, and used in a copyrighted program, are two entirely different things.
A copyrighted work may include any number of other copyrighted segments without affecting the original copyrights.
However, prohibiting use of a routine in a commercial program simply because it is commercial, is somewhat disingenuous.
For what it's worth, I'm with Drizz. Any code posted by me on this forum is hereby released to the public domain and may be freely used for any purpose without restrictions or requiring reference as to origin.
Jim, I am not an expert on these things. All I say is use my code but don't restrict its usage by others. I don't want to pay royalties for my own code. It is free - for everybody.
Quote from: drizz on June 29, 2009, 07:32:26 PM
dedndave,
my proc is only optimal, there is even faster routine by lingo but you'll have to search the board for it...
You mean b2a3264 (http://www.masm32.com/board/index.php?topic=8974.msg65436#msg65436)?
i found a flaw in Drizz's latest - lol
these 2 lines are missing...
OPTION PROLOGUE:PrologueDef
OPTION EPILOGUE:EpilogueDef
i am going to put Drizz1, Drizz2, Dixon, and Lingo in a program to test them for correct values
while i am at it, i may as well get average timing results over the range of values
depends on how long it takes to run - lol
Quote from: dedndave on June 29, 2009, 07:00:22 PM
here is some comparison timing
although, there seems to be a flaw someplace
still, Drizz's routine will be about 7 times faster than mine
i think i can convert my method a bit
i may not beat Drizz, but i can get somewhere in the same galaxy - lol
Congrats, you
are in the same galaxy!
Sherlock Holmes found a missing counter_end after the call to drizz' algo :(
[attachment deleted by admin]
well, i know i can make mine faster, but i doubt it is worth the effort - lol
although, i am confident it returns the correct string for all input values
still, it is nice to know what i am working with
i think we need to update our timer macros, Jochen - lol
Drizz's latest has no branch's - lol
i like it
Quotei am going to put Drizz1, Drizz2, Dixon, and Lingo in a program to test them for correct values
while i am at it, i may as well get average timing results over the range of values
depends on how long it takes to run - lol
well, so much for that idea - lol
just going through an empty loop for all 18,446,744,073,709,551,616 values would take about 408 years on my machine
(if i did my calculations right)
if i test every 65536th value, i can run an empty loop in a couple days
how do we verify our routines ?
ideas ? suggestions ?
even some tiny fraction of reliability testing is better than 0 - lol
Testing for border values is always a good idea.
0,
1,10,100,...,10^19,
9,99,999,...,10^19-1,
0Fh,0FFh,0FFFh,...,2^64-1
btw, here's my latest code, fast non lut routine
;*****************************************************************
;
; 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
edit: code updated to slightly improved verison + added suplemental procs
cool Drizz - is it faster ?
(lol - magic diver)
:bg, it's not faster than the LUT routine (pdixon, lingo) but it is very close.
it is 2-3 times faster than my previous functions.
close is great - the Dixon method is a little clumsy with the table and all
1 kb to convert to decimal - lol
i see this one has branches - i was a fan of the last one :(