The Boston Diaries

The ongoing saga of a programmer who doesn't live in Boston, nor does he even like Boston, but yet named his weblog/journal “The Boston Diaries.”

Go figure.

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.


Discussions about this entry

Obligatory Picture

An abstract representation of where you're coming from]

Obligatory Contact Info

Obligatory Feeds

Obligatory Links

Obligatory Miscellaneous

Obligatory AI Disclaimer

No AI was used in the making of this site, unless otherwise noted.

You have my permission to link freely to any entry here. Go ahead, I won't bite. I promise.

The dates are the permanent links to that day's entries (or entry, if there is only one entry). The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site: https://boston.conman.org/, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

https://boston.conman.org/2000/08/01

You can also specify the entire month by leaving off the day portion. You can even select an arbitrary portion of time.

You may also note subtle shading of the links and that's intentional: the “closer” the link is (relative to the page) the “brighter” it appears. It's an experiment in using color shading to denote the distance a link is from here. If you don't notice it, don't worry; it's not all that important.

It is assumed that every brand name, slogan, corporate name, symbol, design element, et cetera mentioned in these pages is a protected and/or trademarked entity, the sole property of its owner(s), and acknowledgement of this status is implied.

Copyright © 1999-2024 by Sean Conner. All Rights Reserved.