smallest AX hex code to AL binary byte conversion?

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

Author

Thread

wht36

Joined: 18 Sep 2005
Posts: 106

wht36 28 Jun 2011, 07:29

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

28 Jun 2011, 07:29

r22

Joined: 27 Dec 2004
Posts: 805

r22 28 Jun 2011, 11:56

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

28 Jun 2011, 11:56

Madis731

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia

Madis731 28 Jun 2011, 14:06

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?

28 Jun 2011, 14:06

r22

Joined: 27 Dec 2004
Posts: 805

r22 28 Jun 2011, 17:13

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

28 Jun 2011, 17:13

Madis731

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia

Madis731 29 Jun 2011, 05:42

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

29 Jun 2011, 05:42

Picnic

Joined: 05 May 2007
Posts: 1389
Location: Piraeus, Greece

Picnic 29 Jun 2011, 22:55

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

29 Jun 2011, 22:55

wht36

Joined: 18 Sep 2005
Posts: 106

wht36 30 Jun 2011, 08:14

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:	266 Time(s)

30 Jun 2011, 08:14

Madis731

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia

Madis731 07 Jul 2011, 11:47

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

07 Jul 2011, 11:47

Picnic

Joined: 05 May 2007
Posts: 1389
Location: Piraeus, Greece

Picnic 08 Jul 2011, 06:21

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
        @@:

08 Jul 2011, 06:21

r22

Joined: 27 Dec 2004
Posts: 805

r22 08 Jul 2011, 13:02

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

08 Jul 2011, 13:02

mindcooler

Joined: 01 Dec 2009
Posts: 423
Location: Västerås, Sweden

mindcooler 08 Jul 2011, 15:52

Unfortunately cmov is probably slower than branching :/

08 Jul 2011, 15:52

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 08 Jul 2011, 16:13

mindcooler wrote:

Unfortunately cmov is probably slower than branching :/

And fortunately this thread is about size, not speed. Wink

08 Jul 2011, 16:13

r22

Joined: 27 Dec 2004
Posts: 805

r22 08 Jul 2011, 17:24

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.

08 Jul 2011, 17:24

Fanael

Joined: 03 Jul 2009
Posts: 168

Fanael 09 Jul 2011, 01:16

Hehe, this topic reminded me of my own challenge that was pretty much the reverse of this one. Very Happy

09 Jul 2011, 01:16

< 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