flat assembler
Message board for the users of flat assembler.

Index > Main > A bunch of binary to decimal conversion routines

Goto page Previous  1, 2
Author
Thread Post new topic Reply to topic
wht36



Joined: 18 Sep 2005
Posts: 106
wht36
Hmmmm, hope I am substituting correctly

Let N=15, B=1

A= 0 = 15 mod 5^1
C = (15-0)/5^1 mod 2^1 = 1
15 mod 10^1 = 5^1 * 1 + 0

Sorry, by overflow I thought that since one is dividing a 64 bit number (EDX:EAX) by 5^B and the remainder needs to go into a 32 bit number (EDX), so if the 64 bit number is very big, and if B is very low, the initial remainder will overflow. But if B is very big, then I'm worried that the remainder + (the bits shift left * 5^B) will also overflow. But now that I think again, it shouldn't, since we are clearing the high dword initially, and later filling the high dword with the remainder (which will never be greater than 5^B, and therefore will never cause an overflow).

However, I am struggling to do a long binary to decimal conversion using a div5/shl 1 operation. So to make things easier for my brain to comprehend, let me reduce 32 bits to 8 bits, and say one is trying to convert FF FF FF FFh into decimal using 8 bit division, where the dividend is 16 bits, the remainder goes into an 8 bit number and the quotient the other 8 bit number.

N=FFFFFFFFh = 4294967295
Maximum 5^B to go into 8 bits is 5^3 = 125
Maximum 10^C to go into 8 bits is 10^2 = 100

1) Clear high byte of dividend and load most significant byte into dividend
1) 255 / 100 = quotient 2, remainder 55
2) 14335 / 100 = quotient 143 (8F), remainder 35
3) 9215 / 100 = quotient 92 (5C), remainder 15
4) 4095 / 100 = quotient 40 (28h), remainder 95

final remainder = 95 is the least significant term in the final result
current quotient = 02 8F 5C 28h...

1) 255 / 125 = quotient 2, remainder 5
2) 5FFh / 125 = quotient 12, remainder 35
3) 23FFh / 125 = quotient 73, remainder 90
4) 5AFFh / 125 = quotient 186, remainder 45

final quotient = 02 0C 49 BAh
remainder = 45
Okay, now to get the least significant term in the final decimal result...

A = N mod 5^3
C = (N-A)/5^B mod 2^B
N mod 10^B = 5^B * C + A

A = FF FF FF FFh mod 125 = 45
C = (FF FF FF FFh - 45)/125 mod 2^3 = 2
FF FF FF FFh mod 10^3 = 125 * 2 + 45 = 295

That works very nicely! 3 digits instead of 2 digits!

So now extrapolate back...
largest 10^B to go into 32 bits = 10^9 = 9 digits
largest 5^B to go into 32 bits = 5^13 = 13 digits

4 more digits per dword divide (8 more digits for 64bit divide / 16 more digits per 128 bit divide)!
bitRake, you are a star Smile!
Post 19 Dec 2008, 05:48
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2914
Location: [RSP+8*5]
bitRAKE
Did some very minor testing - appears to work...
Code:
BIGINT.itoa:
      ; rsi = BIGINT pointer
      ; rcx = qword limbs in big integer
  ; rdi = string buffer

   mov rbp,5*5*5*5*5*5*5*5*5 * 5*5*5*5*5*5*5*5*5 * 5*5*5*5*5*5*5*5*5
   jmp .3
  .1:     xor edx,edx
 xor ebx,ebx
 push rcx
  .0:
       mov rax,[rsi+rcx*8]
 div rbp
     shrd rbx,rax,27+10
  shrd rax,rbx,27
     mov [rsi+rcx*8],rax
 dec ecx
     jns .0
      shl rbx,10
  shr rbx,27+10

   ; N mod 10^27 = RBP * RBX + RDX
     mov rax,rbx
 mov rbx,rdx
 mul rbp
     add rax,rbx
 adc rdx,0

       ; extract the 27 digits...

      pop rcx
  .2:    cmp qword [rsi+rcx*8],0
     jne .1
  .3:     dec ecx
     jns .2

  retn    
...the trick is eliminating the shift - it isn't needed.
Post 19 Dec 2008, 06:25
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
finally, when i look deeper to my code, i see it is not so bad.
and is it very frequent to display more than 32bits values in decimal?
Code:
topofbuffer rd 1
.buffer rb 32
endofbuffer db 0
num:
.dec:
; eax = number to convert
        mov esi,endofbuffer
        dec esi
        mov ebx,10  ; decimal base
        mov ch,' '
        test eax,80000000h
        jne .positif
        neg eax    ;eax = |eax|
        mov ch,'-' ;set the minus sign
.positif:
.next:
        cdq         ; expand eax for the division ( xor edx,edx is ok)
        idiv ebx   ; divide by 10
        mov cl,dl   ;extract one digit from the remainder,
        add cl,'0'   
        mov [esi],cl  ;store digit, high digit first 
        dec esi         ;increment digit rank
        cmp eax,0    ; do it until eax = 0
        jne .next
        cmp ch,'-'     ;is it a negative number?
        je @f
        mov ch,cl
        inc esi
@@:
        mov [esi],ch
        mov [topofbuffer],esi
        ret
    

decimal to ascii conversion of a 32 bits value.

start the convertion with the least significant digit.
the lsd is putted the char before the end of buffer (0)
the buffer start should be returned for a printing ressource.
the buffer size is 12 bytes (s)(1234567890)(,0)

the value -123456 is equivalent of this after conversion:
Code:
topofbuffer dd xxxxxxxxxx>>>> v
buffer      db 0,0,0,0,0,0,0,'-','1','2','3','4','5','6'
endofbuffer db 0
    
Post 20 Dec 2008, 01:17
View user's profile Send private message Visit poster's website Reply with quote
kempis



Joined: 12 Jun 2008
Posts: 49
kempis
my code: convert to BCD with fbstp (Is it slow or fast?)

Code:
dword_to_string:
  ;eax    dword value
 ;edi    pointer to string buffer

        push    ebp
 mov     ebp,esp
     sub     esp,12
      and     esp,not 0xF
 mov     dword[esp],eax
      mov     dword[esp+4],0
      fild    qword[esp]
  mov     ecx,5
       fbstp   [esp]   ;store packed-BCD
     .loop1:
       sub     ecx,1
       mov     al,[esp+ecx]
        test    al,al
       jnz     .br_loop1
   test    ecx,ecx
     jnz     .loop1
      mov     byte[edi],'0'
     mov     byte[edi+1],0
       mov     esp,ebp
     pop     ebp
 ret
     .br_loop1:
  test    al,0xF0
     jnz     .loop2
      add     al,'0'
    stosb
       test    ecx,ecx
     jz      .end_loop
   sub     ecx,1
       mov     al,[esp+ecx]
     .loop2:
    mov     ah,al
       shr     al,4
        and     ah,0x0F
     add     al,'0'
    add     ah,'0'
    mov     byte[edi],al
        mov     byte[edi+1],ah
      add     edi,2
       test    ecx,ecx
     jz      .end_loop
   sub     ecx,1
       mov     al,[esp+ecx]
        jmp     .loop2
     .end_loop:
       mov     byte[edi],0
 mov     esp,ebp
     pop     ebp
 ret    
Post 20 Dec 2008, 13:23
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17278
Location: In your JS exploiting you and your system
revolution
Slow. FBSTP is a very un-optimal way to do it if your goal is speed.
Post 20 Dec 2008, 13:32
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17278
Location: In your JS exploiting you and your system
revolution
I think I've posted this elsewhere but I can't find it just now so I'll post again.

Prints and unsigned dword in eax:
Code:
   push    -1
  mov     ebx,0cccccccdh
    .a:   mov     ecx,eax
     mul     ebx
 and     edx,-8
      mov     eax,edx
     sub     ecx,edx
     shr     edx,2
       sub     ecx,edx
     push    ecx
 shr     eax,3
       jnz     .a
  pop     eax
    .b:      add     al,'0'
    ;;;put your print/store function here. Example only shown in next line
              stosb ;example only!
        pop     eax
 test    al,10h
      jz      .b    
Feel free to wrap whatever headers and returns are required for your situation.
Post 20 Dec 2008, 13:42
View user's profile Send private message Visit poster's website Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
r22
Funny how this type of stuff is so overly complex on an x86. Even the divide by '10' method.

I used to program at an insurance company and their IBM mainframe (I think zOS s/370) had built in numeric formatting. In ASM it was the ED opcode and you'd use EPDIC character mask like "$,$$$,ZZZ.ZZ".

An old school strictly business oriented processor would have that type of thing as part of the architecture and the x87 FPU only went as far as BCD. I guess the 'strictly business oriented' part answers my own non-question.

[If you read this far you won't be getting any return on your time Very Happy]
Post 21 Dec 2008, 03:54
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17278
Location: In your JS exploiting you and your system
revolution
r22 wrote:
Funny how this type of stuff is so overly complex on an x86. Even the divide by '10' method.

I used to program at an insurance company and their IBM mainframe (I think zOS s/370) had built in numeric formatting. In ASM it was the ED opcode and you'd use EPDIC character mask like "$,$$$,ZZZ.ZZ".
Now that is what I call a real CISC instruction set.
r22 wrote:
An old school strictly business oriented processor would have that type of thing as part of the architecture and the x87 FPU only went as far as BCD. I guess the 'strictly business oriented' part answers my own non-question.
But the main problem is that is offers no flexibility. If you have a requirement that is even slightly different then you have go and code up the whole thing using other instructions. It is a waste of space in the microcode of the CPU unless you can be sure that it is used often.
r22 wrote:
[If you read this far you won't be getting any return on your time Very Happy]
?
Post 21 Dec 2008, 04:03
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2914
Location: [RSP+8*5]
bitRAKE
It would be nice to have a couple custom opcodes. Very Happy I assume the reconfiguration time would be immense. Yet, I wonder how low the latency could be? Given the microcode update facility, why shouldn't it be possible?

[I don't get a return on any of my time and the expiration date is too fuzzy to bother me either, lol.]
Post 21 Dec 2008, 05:57
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17278
Location: In your JS exploiting you and your system
revolution
But all x86 CPUs already have one custom opcode. All you need to do is set up a memory area with your required set of actions that you need the CPU to follow and then you execute the special custom opcode to do it. BTW The custom opcode is called CALL.
Post 21 Dec 2008, 06:05
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2914
Location: [RSP+8*5]
bitRAKE
My special opcode is int3, lol.
Post 21 Dec 2008, 07:16
View user's profile Send private message Visit poster's website Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 724
tthsqe
Here is a very short program that displays a 64-bit register in any base.

Code:
format PE64 GUI
entry start

include 'win64a.inc'

section '.text' code readable executable

start:

base=11
hexnumber=0xffffffffffffffff


        lea     rdi,[answer]
        mov     rcx,base
        mov     r10,hexnumber
        call    ConvertFromHex
        invoke MessageBox,NULL,answer,caption,MB_OK
        invoke ExitProcess,0



ConvertFromHex:
; rcx: base
; r10: number to convert
; rdi: address to write string to

        cld
        mov     rbp,rsp
        mov     rax,1
        xor     rdx,rdx
loop_push:
        mov     rbx,rax
        push    rbx
        mul     rcx
        jo      loop_pop
        cmp     rax,r10
        jb      loop_push
loop_pop:       
        xor     rdx,rdx
        pop     rcx
        mov     rax,r10
        div     rcx
        mov     al,[digit_table+rax]
        stosb
        mov     r10,rdx
        cmp     rbp,rsp
        jne     loop_pop
        mov     al,0
        stosb
        ret

section '.data' data readable writeable
  answer rb 65
  caption db 'Result:',0
  digit_table   db '0123456789abcdefghijklmnopqrstuvwxyz',0

section '.idata' import data readable writeable
  library kernel32,'KERNEL32.DLL',\
          user32,'USER32.DLL'

  include 'api\kernel32.inc'
  include 'api\user32.inc'         
Post 06 Jul 2009, 10:01
View user's profile Send private message Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1160
Azu
revolution wrote:
r22 wrote:
An old school strictly business oriented processor would have that type of thing as part of the architecture and the x87 FPU only went as far as BCD. I guess the 'strictly business oriented' part answers my own non-question.
But the main problem is that is offers no flexibility. If you have a requirement that is even slightly different then you have go and code up the whole thing using other instructions. It is a waste of space in the microcode of the CPU unless you can be sure that it is used often.
If they made it easy to customize the microcode this kind of thing wouldn't be a problem though..
Post 07 Jul 2009, 18:41
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.