Skip to content

Number Ninja – Fast and Flexible Binary to Ascii Conversion With Sharp Edges!

May 3, 2015

Double Dabble is way too gentle a tag for this bad boy. On my 4mhz processor this converts binary numbers to ascii strings at well over 1000 digits per second. It can handle numbers of arbitrary length up to buffer limits, and it punishes inattention with memory overruns – what more could you ask for!

Unlike the traditional itoa(int, char *) which takes an integer and a pointer to a buffer as parameters and returns a pointer to the ascii string, numberNinja takes three parameters: a POINTER to the first byte of the binary number which can be any length, a pointer to the TAIL of the buffer – not the 1st position, and the number of bytes in the binary number. The buffer, of course, has to be long enough for the result: e.g. 10 digits plus a terminating 0 for a long int.

The code is based on double dabble with some refinements: most notably the idea of storing the binary number in memory rather than a register and the use of an “add 120” hack in the pre-correction loop. The general form of “double dabble” is to shift the bits from the top of the binary number into the bottom of the BCD number adjusting during each shift not to let the BCD digits get over 10. The previous versions used a pre-correction loop which are simplified dramatically with the 120 hack.

adding120

In the BCD digit sequence area, this code stores *one* BCD digit in
the low-order 4 bits of each byte. The high-order 4 bits are all
zeros. The rule for pre-correction is: if the BCD digit has the
value 4 or less, do *no* pre-correction at all! If the BCD digit has
the value 5 or more, add 3 for the pre-correction.

Note that if *no* pre-correction is done… the BCD digit has the
form “0xxx”; the high-order bit of the BCD digit will always be zero
if *no* precorrection is done. If a pre-correction *is* done, the
BCD digit will have the form “1xxx”. The BCD digit must have the
value 5 or greater to receive a pre-correction. 5 + 3 is 8, so the
smallest pre-corrected value for a BCD digit will be “1000” or 8.

RULE: BCD digits *not* needing correction will *always* have a “0”
high-order fourth bit; BCD digits that *are* corrected will *always*
have a “1” as the high-order fourth bit.

So if a pre-correction is done, the entire *byte* (containing the BCD
digit in the lower four bits)… will have the form “00001xxx”, where
“xxx” is some combination of three bits. The idea is to change the
pre-correction so the form of the byte will be “10000xxx”… or to
“move” that 1 bit at the high end of the BCD digit… to the high-
order bit in the byte. The “xxx” in the bottom will remain the
same. This is done *only* to BCD digits that are being pre-
corrected. The following chart shows how this works:

The above figure shows adding an additional 120 *after* the 3 pre-
correction has been done *and* the 5 has already been added back.
All these additions can be done at once by “adi 128”. Adding this
“block of ones” forces the 1 in the high-order bit of the BCD
digit… to become the high-order bit of the entire *byte*, so it
will shift into the carry (DF register) in the BCD digit shift loop.

Now the BCD digit shift loop can just do the left shift only and
*not* worry about the high-order 4 bits. BCD digits that were *not*
pre-corrected (4 or less in value) will have the form “00000xxx”
where “xxx” is 4 or less. The pre-corrected BCD digits will now have
the form “10000xxx”… and when this is shifted left, the high-order
1 goes into carry (DF register) and the high-order 4 bits will be
zero. So we are covered in both cases.

Number Ninja is, of course, coded in 1802 assembly but to be useful without being totally scary, it can be wrapped as for example:

char * numberninja(void * binary, char * buffertail, int sizeofbinarynumber);
char * itoa(int s, char *buffer){ //convert an integer to printable ascii in a buffer supplied by the caller
char * bptr;
if (s<0){
s=-s;
bptr=numberninja(&s,buffer+6,2)-1;
*bptr='-';
} else{
bptr=numberninja(&s,buffer+6,2);
}
return bptr;
}
_numberninja:
;fierce and flexible - be careful with the inputs!
;binay-ascii conversion originally based the double-dabble algorithm
;handles variable length input and output
;thanks to Charles Richmond for the suggestion and code
;15-05-02 initial version
;POINTER to integer is passed in r12
;pointer to LAST BYTE of buffer is passed in r13
;number of bytes to convert is passed as the 3rd parameter
;a pointer to the 1st non-zero byte in the buffer is passed back in r15
;r8-11 are used as temps
;r13 is the working pointer to the BCD number
;r12 is the pointer to the input
;r15.0 is bit count in the current byte and the return value register
;r11.0 is the number of bytes to convert
;r10.0 is the count of digits as the bcd number is developed
;r9.0 is digit count for the current pass
ld2 r11,'O',sp,(2+4); pick up the number of bytes to convert

ldi 0	;source a 0
str r13	;terminate the buffer
dec r13	;back to units position
str r13	;initialize bcd number to 0
ldi 1	; initialize the bcd digit count at 1
plo r10 ;

$$nxtbyte:
ldi 8		;bits in byte
plo r15
$$nxtbit:
ldn r12		;pick up current byte
shl		;check top bit
bdf $$bitloop	;move on for a 1 bit
str r12		;put the byte back

dec r15		;decrement and test bits in byte
glo r15
bnz $$nxtbit

dec r11		;decrement and test bytes in number
glo 11
bz $$done	;the whole number was 0! no need for further processing

inc r12		;point to the next byte
br $$nxtbyte	;go back for it
$$bitloop:
glo r10	;digit count
plo r9
$$dcklp:
ldn r13 	;pick up a bcd digit
smi 5	;see if it's greater than 4
bnf $$dnoadd ;if not, bypass add
adi 128	;add the 5 black and 3 more and 120 per charles
str r13	;put it back
$$dnoadd:
inc r13
dec r9	;decrement digit count
glo r9
bnz $$dcklp ;and back for next digit

ldn r12 ;shift the current byte of the input number
shl
str r12

glo r10	;load the digit count again
plo r9
;r13 is now just past the units location and ready to walk back
$$dshlp:
dec r13	;walk back from 0's position
ldn r13	;get the digit back
shlc	;continue the shift
str r13	;put the digit back
dec r9	;decrement the digit count
glo r9
bnz $$dshlp ;back for more if needed
;we are now out of digit positions but if DF is 1 we need another digit
bnf $$nextbit	;no need to increase digits
inc r10	;increase BCD digit count
dec r13	;back up pointer to new digit position
ldi 1	;source a 1
str r13	;initialize the position

$$nextbit:
dec r15		;see if bits left in byte
glo r15
bnz $$bitloop

dec r11		;see if bytes left in number
glo r11
bz $$done
inc r12		;point to next byte of number
ldi 8		;prep for 8 more bits
plo r15
br $$bitloop

$$done: ;this is also used for for an early exit.  R13 and R10 must be correct
cpy2 r15,r13	;save the starting location of the digits to return
glo r10		;digit count again
plo r9
$$upnxt:
ldn r13		;get digit
ori 0x30	;make ascii
str r13		;put it back
inc r13		;next digit
dec r9		;counter
glo r9
bnz $$upnxt	;upgrade all spots
cretn		;return with pointer to 1st digit in r15

I did a little test of printing ip addresses which is what got me started on this. Using the number ninja, printf takes about 15ms to print an ip address as opposed to about 50 using itoa(). It will be a little bit of work to revise the compiler version of printf but that really needs an overhaul anyway: I did it a while ago and my understanding of c strings and pointers has improved a lot in the meantime.

Advertisements

From → Uncategorized

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: