flat assembler
Message board for the users of flat assembler.

Index > Main > smallest AX hex code to AL binary byte conversion?

Author
Thread Post new topic Reply to topic
wht36



Joined: 18 Sep 2005
Posts: 106
wht36
Hi all,

Here is another challenge. There are many ways to convert a hex string to binary and to convert an AL hex code to binary. I would like to see the smallest routine to convert an AX hex code to AL binary. The routine should handle invalid hex codes correctly. Here is my contribution
Code:
hex2bin:   ;33 bytes (28 bytes if 16 bit); converts AX hex code to AL, AH zero if valid conversion
     call    .hex            ;convert high nibble
        xchg    al,ah
       call    .hex            ;convert low nibble
 rol     al,4            ;move low nibble next to high nibble
        ror     ax,4            ;bring both nibbles into AL and move everything else into AH
        ;add    ah,255          ;convert AH > 0 into CF (adds 3 bytes to size)
   ret
.hex:        sub     al,'9'+1      ;Is it a number
     jb      .num
        or      al,'a'-'A'  ;Coerce to lowercase
        sub     al,'a'-('9'+1)      ;Is it a letter
     jb      .ret
.num:       add     al,10           ;Convert to binary
.ret: ret    
Post 28 Jun 2011, 07:29
View user's profile Send private message Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
r22
*edit*
Use a lookup table....
5 bytes
Code:
MOVZX eax, ax
MOV al, byte[LUT_HEX2BIN + eax] 
    

But if you count the data size... I guess I lose by a few orders of magnitude.

Look-up tables... when math is hard and memory's cheap.
Look-up tables... when you want speed but have to get to sleep.
Look-up tables... when a one-to-one transform is all you need.
Look-up tables... when you want your code to be easy to read.
Post 28 Jun 2011, 11:56
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
Code:
;40 bytes (44 bytes if 16 bit)
movzx ebx,al
shr   eax,8
mov   bl,[LUT_HEX2BIN+ebx-30h]
mov   al,[LUT_HEX2BIN+eax-30h]
shl   al,4
add   al,bl

LUT_HEX2BIN db 0,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0,0,10,11,12,13,14,15
    

Can come up with LUT-filling routine that takes less than 15 bytes?
Post 28 Jun 2011, 14:06
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
r22
@Madis
I initially posted something very similar to yours, but then I noticed that wht36 was correcting for UPPER and LOWER case. So the LUT would need to be at least 256 bytes. Or more logic would need to be added before the look-up for correction.
Post 28 Jun 2011, 17:13
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
Oh... I missed that.
I think we need some magic number multiplication trick: http://www.azillionmonkeys.com/qed/asmexample.html (9. 64bit BCD add)

My partial solution for bit wizardry is:
UPDATE:
Code:
use16
; Now packing 0-9 & A-F together to map to continuous space
; if(X > "A") X-=7
; sub X 30h
; X in {0,1,..,E,F}
;       ax = "9A"
mov     bx,ax           ;"9A"
sub     bx,0101h        ;4038h
and     bx,4040h        ;4000h
shr     bx,6            ;0100h
imul    bx,7            ;0700h
sub     ax,bx           ;3A39h
sub     ax,3030h        ;0A09h
shl     ah,4            ;A009h
rol     ax,4            ;009Ah ;27 bytes

use32
;       eax = "19AF"
mov     ebx,eax         ;"19AF"
and     ebx,0F0F0F0Fh   ;06010901h
mov     ecx,eax         ;"19AF"
and     ecx,40404040h   ;40400000h
shr     ecx,6           ;01010000h
lea     ecx,[ecx*9]     ;09090000h
add     ebx,ecx         ;0F0A0901h
imul    ebx,11h         ;FFAA9911h
bswap   ebx             ;1199AAFFh
shr     ebx,4           ;01199AAFh
mov     al,bl           ;??????AFh
bswap   ebx             ;AF9A1901h
mov     ah,bh           ;????19AFh ;38 bytes
    


Last edited by Madis731 on 30 Jun 2011, 13:42; edited 1 time in total
Post 29 Jun 2011, 05:42
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Picnic



Joined: 05 May 2007
Posts: 1288
Location: behind the arc
Picnic
Routine converts 1 to 4 hex digits although no error control. 21/24 bytes

Code:
;mov ebx, "FFFF"
;mov ecx, 4
;call hex2bin

;edx = 65535

hex2bin:
            xor edx, edx
                @@:
            mov al, bl
            and al, 0CFh
            aam 41h
            aad 10
            ror ebx, 8
            shl edx, 4
            or dl, al
            loop @B
            ret
    
Post 29 Jun 2011, 22:55
View user's profile Send private message Reply with quote
wht36



Joined: 18 Sep 2005
Posts: 106
wht36
Hmm, very interesting submissions. I've written a short program to display the output of the conversions. At a quick glance both Madis and Picnic's submission give correct results (if input is valid...). Feel free to put your routine in and see what comes out! e.g.
Code:
;........
;;;;;; remove the 3 lines below to see what happens with invalid input
   call    hex2bin_wht36
       test    ah,ah
       jnz     .next
;;;;;;;;;; put your routine here
        mov     eax,ebx    ;restore EAX
        
    mov     bx,ax           ;"9A"
     and     bx,0F0Fh        ;0109h
      mov     cx,ax           ;"9A"
     and     cx,4040h        ;4000h
      shr     cx,6            ;0100h
      lea     cx,[ecx*9]      ;0900h
      add     bx,cx           ;0A09h
      imul    bx,11h          ;AA99h
      rol     bx,4            ;A99Ah
      mov     al,bl           ;??9Ah ;29 bytes 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  mov     [output],al
;.....
    


Description:
Download
Filename: test_h2b.zip
Filesize: 1.73 KB
Downloaded: 118 Time(s)

Post 30 Jun 2011, 08:14
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
I declare "branchless ax ascii hex2bin under 28 bytes" impossible (by my understanding of bits and bytes and hex) Sad

I can almost beat your code (but not in 16-bit world) by optimizing this:
Code:
hex2bin:        ;[b]29[/b] bytes (28 bytes if 16 bit); converts AX hex code to AL, AH zero if valid conversion
        mov     cl,1
.hex:   sub     al,'9'+1        ;Is it a number
        jb      .num
        or      al,'a'-'A'      ;Coerce to lowercase
        sub     al,'a'-('9'+1)  ;Is it a letter
        jb      .ret
.num:   add     al,10           ;Convert to binary
.ret:   xchg    al,ah
        sub     cl,1
        jnc     .hex
        rol     al,4            ;move low nibble next to high nibble
        ror     ax,4            ;bring both nibbles into AL and move everything else into AH
        ;add    ah,255          ;convert AH > 0 into CF (adds 3 bytes to size)
        ret
    
Post 07 Jul 2011, 11:47
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Picnic



Joined: 05 May 2007
Posts: 1288
Location: behind the arc
Picnic
I'm aware of another method to convert a hex char to binary

Code:
; Convert ascii hex char ('0'..'9', 'A'..'F', 'a'..'f') to binary
; DL = character

        and dl, 0CFh
        cmp dl, 0Ah
        jl @F
        sub dl, 37h
        @@:    
    
Post 08 Jul 2011, 06:21
View user's profile Send private message Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
r22
I extended Picnics version to cover the question AX hex->AL bin
I made the algorithm branch-less with CMOVcc (31bytes)
Code:
        xor     edx,edx
        xor     ecx,ecx
        and     ax,0CFCFh ;; 1100'1111x2
        mov     ch,37h
        cmp     ah,09h
        cmova   edx,ecx
        lea     ecx,[edx+37h]
        cmp     al,09h
        cmova   edx,ecx
        sub     eax,edx
        shl     al,4
        or      al,ah  
    
Post 08 Jul 2011, 13:02
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
mindcooler



Joined: 01 Dec 2009
Posts: 423
Location: Västerås, Sweden
mindcooler
Unfortunately cmov is probably slower than branching :/
Post 08 Jul 2011, 15:52
View user's profile Send private message Visit poster's website MSN Messenger ICQ Number Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17250
Location: In your JS exploiting you and your system
revolution
mindcooler wrote:
Unfortunately cmov is probably slower than branching :/
And fortunately this thread is about size, not speed. Wink
Post 08 Jul 2011, 16:13
View user's profile Send private message Visit poster's website Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
r22
mindcooler wrote:
Unfortunately cmov is probably slower than branching :/

In testing I've done in the past CMOV outperforms unpredictable branches.
If you were referring to CMOV + all of the extra setup op-codes, then perhaps it is slower.
Post 08 Jul 2011, 17:24
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
Fanael



Joined: 03 Jul 2009
Posts: 168
Fanael
Hehe, this topic reminded me of my own challenge that was pretty much the reverse of this one. Very Happy
Post 09 Jul 2011, 01:16
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< 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.