flat assembler
Message board for the users of flat assembler.

 Index > Main > smallest AX hex code to AL binary byte conversion?
Author
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

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

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

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
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
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
imul    bx,11h          ;AA99h
rol     bx,4            ;A99Ah
mov     al,bl           ;??9Ah ;29 bytes
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
mov     [output],al
;.....
```

30 Jun 2011, 08:14

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)

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.
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.
09 Jul 2011, 01:16
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum