Hi, all

I was looking for a conversion routine for a 64 bit integer. Having searched the board for useful pieces of code I finally put together the following routine which seems to work.

Two questions remain for me:
- Is the fpu control word 067Fh the correct one?
- According to several manuals the fprem instruction is outdated and should be replaced by fprem1. But when I do that, I get a wrong result. Is there a solution for that?

wolf




.486
.model flat,stdcall
option casemap:none

include \masm32\include\windows.inc
include \masm32\include\kernel32.inc
include \masm32\include\user32.inc

includelib \masm32\lib\kernel32.lib
includelib \masm32\lib\user32.lib

i64toa proto :DWORD,:DWORD

.data?
testbuff db 128
.data
onebillion dq 1000000000
testint dq 7FFFFFFFFFFFFFFFh
caption db "64 bit integer conversion",0
.code

start:
invoke i64toa,ADDR testint,ADDR testbuff
invoke MessageBox,0,ADDR testbuff,ADDR caption,0
invoke ExitProcess,0


i64toa proc uses ebx ecx edx edi esi lpLarge:DWORD,lpBuffer:DWORD
LOCAL dqLarge:QWORD
LOCAL dqRemainder:QWORD
LOCAL fpucontrol:WORD
LOCAL myfpucontrol:WORD

mov edi,[lpLarge] ; copy integer into dqLarge and eax:edx
lea esi,[dqLarge]
mov ebx,[lpBuffer]
mov eax,[edi]
mov edx,[edi+4]
bt edx,31
jnc positive

mov byte ptr [ebx],'-' ; integer is negative
inc ebx
not eax
not edx
add edx,1
adc edx,0

positive:
push ebx
mov [esi],eax
mov [esi+4],edx
cmp edx,0
jne bignum ; it is a 64 bit integer
cmp eax,0
jne convert ; it is a 32 bit integer

pop ebx ; it is zero
mov word ptr [ebx],0030h
jmp exit

bignum:
lea edi,[onebillion]
lea ecx,[dqRemainder]

split64: divide the number by 1 billion until the result is a 32 bit value
finit
fstcw [fpucontrol]
mov [myfpucontrol],067Fh ; initialize our control word with 067Fh or 0C7Fh or 0A7h?
fldcw [myfpucontrol]

fild qword ptr [edi] ; load divisor
fild qword ptr [esi] ; load dividend
fst st(2) ; copy dividend into fp register st2
fdiv st(0),st(1)
fistp qword ptr [esi]
fxch st(1)
fprem
fistp qword ptr [ecx]
fstp st(0)

mov eax,[ecx] ; get the 32 bit remainder and convert it
push ecx
push edi
mov ecx,10
mov edi,9

remainderloop:
cmp eax,0
je numberfinished
xor edx,edx
div ecx
add dl,'0'
mov [ebx],dl
inc ebx
dec edi
jmp remainderloop
numberfinished:
dec edi
js digitsfinished
mov byte ptr [ebx],"0"
inc ebx
jmp numberfinished

digitsfinished:
pop edi ; restore the pointers
pop ecx

mov eax,[esi]
mov edx,[esi+4]
cmp edx,0
jne split64 ; it is still a 64 bit number
fldcw [fpucontrol]

convert:
mov ecx,10
conversionloop:
cmp eax,0
je conversionfinished
xor edx,edx
div ecx
add dl,'0'
mov [ebx],dl
inc ebx
jmp conversionloop

conversionfinished:
mov byte ptr [ebx],0
pop esi
rotate:
cmp esi,ebx
jge exit
dec ebx
mov al,[esi]
mov ah,[ebx]
mov [ebx],al
mov [esi],ah
inc esi
jmp rotate

exit:
ret
i64toa endp

end start
Posted on 2002-05-05 14:12:52 by wolf
The FPREM instruction does not compute the remainder specified in IEEE Std 754. The IEEE specified remainder can be computed with the FPREM1 instruction. The FPREM instruction is
provided for compatibility with the Intel 8087 and Intel287 math coprocessors.
Posted on 2002-05-05 14:31:01 by bitRAKE
WOLF

I didn't try to follow all your code.
I think you got too complicated using the FPU instructions.
Do you NEED to use FPU for this?

I modified your code using the normal integer instructions and then displaying 2 message boxes with a big positive and negative number.
If you had checked the code in my post "64 bit primes" in this same algo section, you would have found that i am using exactly the same code to convert the 64 bit number to ascii.
Posted on 2002-05-06 11:54:00 by towers
I'd recommend test speed of both.
Logic choosen in both methods leads to very slow performence.
I submitted 3 difference routines to convert qword to ascii.
You can look for them here in the board or in Thomas snippet lybrary.

To All:
People, why all contests and testing stopped here?
The section is close to dead again.
I was sure that there were a lot of coders to make algo creaters
eat a humble pie.

Is your fighting spirit dead already?
Posted on 2002-05-06 15:52:49 by The Svin

To All:
People, why all contests and testing stopped here?
The section is close to dead again.
I was sure that there were a lot of coders to make algo creaters
eat a humble pie.

Is your fighting spirit dead already?
Haven't you seen RSA threads? We're going to make big discovery! ;)
Posted on 2002-05-06 17:11:12 by bitRAKE

Haven't you seen RSA threads? We're going to make big discovery! ;)


I feel excited already...

On a side note:
I've just proved that god really does exist and figured it out with the use of a pencil, paper and a stick of chewing gum... Should I publish?

:) :) :)

All in good fun,
Sliver

ps. j/k I didn't use a pencil :)
Posted on 2002-05-06 18:54:18 by Sliver
Haven't you seen RSA threads? We're going to make big discovery

Don't make me laugh.
I wouldn't surpise that the guy is from FBI making
another stupid provokation.
Rickey, frankly it's absolutly immpossible to carry
discussion on cryptography here.
At least until you make decision in the States what is
good and what is bad in it.
Government wants a kind of cryptography that SEEMS
secure for ordinary people, but easy to crack for
government intellegence. And act from this logic.
It's stupidity that leads only for unsecurity for both
ordinary Americans and government itself.
It would work (let say it in math logic way)
IF and ONLY IF
1. The USA has the best education over the world.
2. All most talanted Americans are willing to work for the Government.

Both conditions are FALSE.
About education:
Read about Manhettan project (S.M.Ulam Adventure of a Mathematician)
to were the best heads are coming from to the States.

From recent evens 200 000 russian math and theory physics men left to USA
(50% in math and 30% in physics are Russians in the States now)
they were requsted from the States to work there in their fields.

About working for Government you know better than me.

Now couple facts from my experience.
1. Our Russian M$ department proved to chif M$ department that currenlty used in M$
products DSA algorithm was weak.
Under request they offered new DSA.
It was refused.
And know why?
FBI found it hard to crack, so that was afraid that some illigal people can
do their job unvisible to FBI.

2. Our programmer for long time worked under security issues of Acrobat.
FBI was among his CLIENTS!
But when he openly showed that cripting is too weak, to say people for
free that it is unsecure to rely on Acrobat protection, he was put in prison
in the States.
We all were in shock. Guy tried to help the Americans for free and got prison
for it. Well you are strange people indeed.

Now you are got absolutly insecure with the policy.
Best hackers and crackers are not those bully guys as media try to say.
They are talanted Mathematicians and they never reveal themself.
They don't need popularity, and working in dark, and they are not
worse at all of those who work for Government.
They hacked air net communication system in the tradigy day in America.
And you'll never know their names.

So from the above following very simple thing:
FBI paying by insecurity for ability to crack any crypting.
But did they seceed?
NO!
For those who want to be secure in their illigal activity
and have money for it - don't use DSA of M$.
So all FBI got was just insecurity for them and ordinary
people they have to protect.
Along with it persecuting those honest altruists who
try to bring protection.
Making low against using other protection than they
can crack.
It's all bring so complexity in discussing protection, so
that even most honest men trying to protect people
can be blame in illigal activities if their level better in crypting
than those that have people working for Intellegence.

In open key cryptography only those who don't want
that protection algo protect anything from them would
hide results of protection weakness from people.

There are 2 group of such people
1. Pro Hackers and Crackers
2. Security services of Government.

Other people are suffering in those two's buttles
Posted on 2002-05-06 19:00:12 by The Svin
Is your fighting spirit dead already?
I'm busy playing Arcanum, FFX and Yugioh: Dungeondice Monsters 5(even though I don't understand japanese, I still manage to kick some butts on my opponents). When I'm bored playing I'll join in the algo fun ;)

Currently, I'm bored programming any type of code...I even had nightmares that the mov instruction resurrected from the grave and nearly killed me. :grin:
Posted on 2002-05-06 19:49:57 by stryker
Svin,

This is also quite humorous :)

1. The USA has the best education over the world.
2. All most talanted Americans are willing to work for the Government.

1. not in Math, here, they don't even teach Classical Math anymore.....they only teach modern logic and such (training for employment)....I'll bet there's less than 5% Math Dept. Heads that can prove Eulers Equation!!!!

2. "willing to work"??? no-one here in the Gov does any work!!!!

:grin:
B
Posted on 2002-05-06 19:56:26 by Brad

2. "willing to work"? no-one here in the Gov does any work!
Don't give away my secret - it is the only job I could find where I could continue other work and still get paid for something totally unrelated to that work. As an added bonus, I don't feel so bad about all the federal taxes I'm paying. ;)
Posted on 2002-05-06 20:51:06 by bitRAKE
Someday, I'm going to actually LEARN Assembly, and then be able to post something with a little more substance, (In an Algorithmn Thread), than just a opinionated comment!!! :)
sorry, B
Posted on 2002-05-06 21:18:31 by Brad
Thanks very much - especially towers for the 64a.asm!!
It looks so easy. My problem was that I didn't know how to handle the two divisions (hi/low) one after the other and so I involved the fpu instead. Seems I delivered an excellent example for making a really slow routine with a lot of superfluous code.
But I learned a bit at least.

wolf
Posted on 2002-05-07 00:20:43 by wolf
towers logic is slow too.
If lazy to search for already submitted code, I did it for you.
test this(I have also cople MMX versions):


uqw2a proc uses ebx esi edi lBuffer,lQword

LOCAL num18:QWORD
mov esi,lQword
mov edi,lBuffer
mov edx,[esi]
mov eax,[esi+4]

N19H equ 0DE0B6B3h
N19L equ 0A7640000h
N20H equ 8AC72304h
N20L equ 89E80000h
cmp eax,N19H
jc C18
jne C20
cmp edx,N19L
jc C18
C20: cmp eax,N20H
jc DO19
jne DO20
cmp edx,N20L
jc DO19
DO20: mov byte ptr [edi],'1'
sub edx,N20L
lea edi,[edi+1]
sbb eax,N20H
DO19: mov byte ptr [edi],'0'-1
@@: inc byte ptr [edi]
sub edx,N19L
sbb eax,N19H
jnc @B
add edx,N19L
adc eax,N19H
inc edi
C18: mov dword ptr num18,edx
mov dword ptr num18+4,eax

sub esp,10
fild num18
fbstp [esp]
xor esi,esi
@@:
pop eax
bswap eax
mov ebx,eax

mov ecx,eax
mov bl,bh

shr ecx,16
mov ah,al

shr bl,4
shr al,4

and bh,0fh
and ah,0fh

shl ebx,16
and eax,0FFFFh

mov edx,ecx
mov cl,ch

mov dh,dl
shr cl,4

shr dl,4
and ch,0fh

and dh,0fh
shl ecx,16

lea eax,[eax][ebx]+30303030h
lea edx,[edx][ecx]+30303030h

mov [edi+10],eax
mov [edi+14],edx
xor esi,1
lea edi,[edi-8]
jne @B

mov ah,byte ptr [esp]
add edi,16
mov al,ah
add esp,2
shr al,4
mov esi,lBuffer
and eax,0f0fh
or eax,3030h
mov word ptr [edi],ax
cmp edi,esi
mov byte ptr [edi+18],0
jne @P
mov ecx,-20
add edi,19
@@:
inc ecx
cmp byte ptr [edi][ecx],30h
je @B
mov eax,ecx
js @Zero
neg eax
add esi,eax
@@: mov al,byte ptr [edi][ecx]
mov byte ptr [esi][ecx],al
inc ecx
jne @B

@P: ret
@Zero:
mov byte ptr [esi+1],0
jmp @P
uqw2a endp
Posted on 2002-05-07 00:36:55 by The Svin
Hi Svin,

your code is about five times faster - unbelievable.
It will take me some time to have a closer look at it and try to understand it.

wolf
Posted on 2002-05-07 01:42:31 by wolf
a really slow routine with a lot of superfluous code.

It is sign of corrage that you submit the code.
When you don't have already examples of how to deal some algo,
it's 99 % chance that you do code that slower then somewere existing. Most of so to called gurus didn't create any ideas - they just pick them from others.
So coward in the case would pretend that he knows something but don't have time to show it. Or at least simply ask for code.
Brave man just try what he can and show :)
Posted on 2002-05-07 02:00:22 by The Svin
Talking of criptography, I've just finish wathing wanderfool american movie (documentary) "CodeBreakers"
About British and American men who work as military codebeakers
in the 2nd World War.
Authors stated that it was almost impossible to win the war without the codebreakers work.
It was nice to here one more time that brain is more powerfool weapon then bombs.

I'm glad to congradulate our alies with the Victory Day.
Posted on 2002-05-07 02:41:59 by The Svin
I saw some MMX solution in FIDONet earlier


= TALKS.ASM (2:5056/##.###) ==========================
Msg : 3460 of 3692 Snt Loc Scn
From : Stepan Polovnikov 2:5056/16.47 14 Sep 01 17:38:44
To : Sashka Yackubtchick
Subj : ??????????????? 64? ???. ?????????????? ??????
==================================================
Hello, Sashka!

SY> ?? ?????? ???? ?? ?????????? ??????? - ??? ????? ????????? ?? ???? ???
SY> ??????? ??? ???????? ?? ?????? ?? ?? ???? ???? ;)
????? ?????? ?????? ???? ??????, ????????, ??? ?????????? ????? ???? ?
?????. ??????? ? ??? - ?????? ???????????????. ??????? - ???? ;)
??? ?????? 32 ?????? ????? ??????????? ???????????? ???????? (~4??), ???
????????? ????????? ?????????????? ?? 20 ?? 60 ??????.

Const
mmxb0F dq 0F0F0F0F0F0F0F0Fh
mmxb30 dq '00000000'

CodeSeg
...
; edx:eax-number
; edi-string buffer
N19H equ 00DE0B6B3h
N19L equ 0A7640000h
N20H equ 08AC72304h
N20L equ 089E80000h
sub esp,12
xor ecx,ecx
cmp edx,N19H
jb @@nm18
jne @@cp20
cmp eax,N19L
jb @@nm18
@@cp20: cmp edx,N20H
jb @@do19
jne @@do20
cmp eax,N20L
jb @@do19
@@do20: mov cl,10h-1
sub eax,N20L
sbb edx,N20H
@@lp19: inc ecx
@@do19: sub eax,N19L
sbb edx,N19H
jae @@lp19
add eax,N19L
adc edx,N19H
@@nm18: push edx eax
fild [qword esp]
fbstp [esp]
mov [esp+9],ecx
; ?????????? ????? BCD-??????
mov edx,2
cmp [dword esp+4*2],0
jne @@dg16
cmp [dword esp+4*1],1
sbb edx,1
@@dg16: bsr ecx,[esp+4*edx]
je @@zero
shr ecx,3
lea eax,[ecx+4*edx]
lea edx,[eax+eax]
cmp [byte esp+eax],10h
sbb edx,-1
; ?????????????? ?? BCD ? ASCII
movq mm7,[mmxb0F]
movq mm6,[mmxb30]
movq mm0,[esp+0]
movd mm4,[esp+8]
movq mm1,mm0
psrlq mm1,4
pand mm0,mm7
por mm0,mm6
pand mm1,mm7
por mm1,mm6
movq mm2,mm0
punpcklbw mm0,mm1
movq [esp+0],mm0
punpckhbw mm2,mm1
movq [esp+8],mm2
movq mm5,mm4
psrlq mm5,4
pand mm4,mm7
por mm4,mm6
pand mm5,mm7
por mm5,mm6
punpcklbw mm4,mm5
movd [esp+16],mm4
emms
; ??????????? ?????? ? ???????? ???????
@@lpS: mov eax,[esp+edx-3]
bswap eax
mov [edi],eax
add edi,4
sub edx,4
jns @@lpS
mov [byte edi+edx+1],0
add esp,20
ret
@@zero: mov [dword edi],'0'
add esp,20
ret

Bye!
Stepan
--- GoldED+/W32 1.1.5-20010807
* Origin: NETMAIL (2:5056/##.###)


BTW, Stepan leave FIDO Net :(
Posted on 2002-05-07 13:50:41 by Nexo
BTW, Stepan leave FIDO Net

It's too sad.
I'm leaving inet in near future too.
But I think you always can find me in FIDO net.
As I previously said numerous time, Stepan and I worked very closely on many algos, exchanging ideas through echoes and fidomail. Some time I start algo and he follows sometime he.
In the case of hex to ascii MMX he started and then we both add some ideas, In the case of 64 bit to dec string I started and then we both add some ideas.
You SRC 32 algo, we discussed also a half a year ago.


Nexo, I'm sure you can add some ideas. Let's concentrate on it.
Posted on 2002-05-07 18:59:22 by The Svin
This is my first post here, and I'm wondering why you use MMX and other weird instructions to write these routines.
They are basic routines which don't need tremendous optimisation.
Personally, if I had to put the code into a real program, I'll put tower's code to avoid crash on weird systems. Of course, I'll replace the horrible bt ecx, 31 by or ecx, ecx !
Also, there is a subtle bug in his routine, when ecx reached 0 but not ebx.

My modified routine (untested):

mov edi,lpBuffer
or ecx, ecx
jns positive
mov byte ptr ,'-' ; integer is negative
inc edi
not ebx
not ecx
add ebx,1
adc ecx,0
positive:
xor eax, eax
push eax
mov esi,10 ; decoding the 64 bit binary to ASCII
@@:
sub edx,edx
mov eax,ecx
div esi ; divide numhi by 10...
mov ecx,eax
mov eax,ebx
div esi ; .... then numlo by 10, using
mov ebx,eax ; first remainder in edx
add dl,30h ; new remainder plus 30h is the digit
push edx
or eax,ecx
jne @B ; keep looping until no digits left
move:
pop eax
mov ,al ; move......
inc edi
or eax, eax
jnz move
ret

2 other indications:
1) I vaguely remember a trick based on neg to invert 64 bits.
It was something like:
not ecx
neg ebx
adc ecx,0
(not sure if it works)

2) there is another way to avoid ALL floating point operations AND divisions.
The trick is based on the Microsoft Basic conversion routine.
First, we substract 10^19, until we reach a negative result (the iteration counter gives us the first digit !)
Then, we add 10^18, until we reach a positive result (the iteration counter gives us the second digit !)
Then we sub 10^17, etc...
This makes 18 loops, with only add/sub !

To conclude, I have to admit that Svin's code is beautiful, but I really hate floating point operations (what is this fbstp instruction ?)

JCM
Posted on 2002-05-14 18:20:35 by MCoder