Friday, February 24, 2023
A branchless segment of code to generate a printable hexadecimal value
I was an avid fan of assembly language back in my youth and I did a lot of it. And in that time, if I needed to convert a 4-bit quantity to a hexadecimal character, I would write the obvious code:
; x86 code add al,'0' cmp al,'9' ; if '0'-'9', no adjustment needed jbe skip ; otherwise, we need to adjust add al,7 ; the resulting character by 7 ; to get 'A'-'F' skip:
Eight bytes and a branch instruction, and not many ways I could see to improve on that, until the other day when I came across this bit of code:
; x86 code add al,90h daa adc al,40h daa
Not only does this convert a 4-bit value to a hexadecial character, but it's two bytes shorter and it's branchless!
Now,
some might say this abuses the DAA instruction,
but it works.
And how it works is pretty clever I think.
The DAA instruction exists to allow BCD
arithmetic
(back when it was a thing).
For each 4-bits in a byte,
the DAA instruction will check to see if it's in the range of 10 to 15 and if so,
add 6 to that 4-bit value to bring it back into the 0 to 9 range,
and propagate a carry bit
(well,
it's a bit more involved than that,
but that will suffice for this post—you can check my MC6809 emulator for the gory details of the DAA instruction).
By adding 0x90 (or 144 in decimal) to a 4-bit value then using DAA,
a carry bit will be propagated if the initial value was 10 to 15;
otherwise there's no carry to propagate.
The ADC of 0x40 (or 64 decimal) will then add any carry of the previous two instructions into the lower four bits of the result,
and the DAA will then adjust the upper 4-bits to be either 0x3 or 0x4 due to the previous addition of 0x90
(which causes the number to act like a negative number if the initial value was bewteen 0 and 9).
And because of the carry if the initial 4-bit value was between 10 to 15,
you get the required adjustment of 7 needed for values of 10 through 15.
This means the result is 0x30 to 0x39 (the ASCII values of “0” to “9”) of the 4-bit values of 0 through 9, or 0x41 to 0x46 (the ASCII values of “A” to “F”) for values 10 through 15.
Quite ingenious really.
I found reference to what may be the origin of this sequence: the article “A Design Philosophy for Microcomputer Architectures” from the February 1977 edition of Computer (the code appears on the third page of the article), but it's unclear if the author came up with this on his own, or it was a known sequence at the time.
I just wish I found out about it earlier.
