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

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.

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.