Skip to content

Double Dabble State of Play

April 13, 2015

I’m a bit awash in binary to ascii conversion routines so i’m just baselining things here. The production “Rhinestone” compiler uses a C language routine to convert 16 bit binary to ascii for printing. For 32 bit numbers it uses a double dabble routine i developed with a friend in 2013(call it original double dabble). I have several new versions of double dabble from that same friend. The one i have converted for use with the compiler he called onelp because it uses a single inner loop rather than two in the original.

Using an instruction counter in my emulator, and converting binary 0x3039 to 12345 bcd takes

  • 16 bit c-language itoa(): 2279 instructions
  • 32 bit original double dabble: 3153 instructions
  • 32 bit “one loop” double dabble: 1032 instructions

Noe of these comparisons are “fair” because the routines all have a bit different inputs and outputs. Notably the double dabble counts don’t include clearing the work area or converting the result to ascii (they end with 0x0102030405 rather than 0x3132333435); also, the new routines literally won’t work with 0 inputs – one part of them eschews a loop counter in favour of counting on eventually hitting a non-zero bit in the number.

Clearly the game is worth the prize though so i’ll benchmark the latest routine i got from charles then see about converting it for compiler use.

char * itoa(int s, char *buffer){ //convert an integer to printable ascii in a buffer supplied by the caller
unsigned int r,k,n;
unsigned int flag=0;
char * bptr; bptr=buffer;
if (s<0){
*bptr='-';bptr++;
n=-s;
} else{
n=s;
}
k=10000;
while(k>0){
for(r=0;k<=n;r++,n-=k); // was r=n/k
if (flag || r>0||k==1){
*bptr=('0'+r);bptr++;
flag='y';
}
//n=n-r*k;
k=k/10;
}

*bptr='\0';
return buffer;
}
dubdabx:
;experimental binay-ascii conversion using the double-dabble algorithm
;thanks to Charles Richmond for the suggestion and code
;long interger is passed in rp1p2
;buffer pointer is passed at sp+2+4
;a pointer to the 1st non-zero byte in the buffer is passed back in r15
;r8-11 are used as temps
;r8 is the working pointer
;r15.0 is bit count(32) and the return value register
;r9.0 is digit count
;r10 is the number of digits wanted in the result including leading 0's - 0 means no leading 0's
ld2 r8,'O',sp,(2+4); pick up the buffer pointer
ld2 r10,'O',sp,(2+4+2); pick up the number of digits wanted
cpy2 r15,r8 ;save address for now
ldi 11	;digit count+1 for trailing 0
plo r9
$$clrlp:	;clear the passed buffer
ldi 0
str r8	;clear a byte
inc r8
dec r9
glo r9	;check the count
bnz $$clrlp ;back for more
cpy2 r8,r15 ;get the address back

ldi 32	;bit count
plo r15
;now i'm going to spin off any leading 0's in the binary number
$$cktop:
ghi rp1p2-1	;get the top bit of the number
shl		;check for a 1
bdf $$bitloop	;move on if we have one
shl4 rp1p2	;shift the input number
dec r15		;reduce the number of times to shift
glo r15
bnz $$cktop	;
inc r15		;our whole number was 0 but force at least one pass
$$bitloop:
ldi 10	;digit count
plo r9
$$dcklp:
ldn r8 	;pick up a digit
smi 5	;see if it's greater than 4
bnf $$dnoadd ;if not, bypass add
adi 0x08	;add the 5 black and 3 more
str r8	;put it back
$$dnoadd:
inc r8
dec r9	;decrement digit count
glo r9
bnz $$dcklp ;and back for next digit

shl4 rp1p2 ;shift the input number

ldi 10	;load the digit count again
plo r9
;r8 is now just past the units location and ready to walk back
$$dshlp:
dec r8	;walk back from 0's position
ldn r8	;get the digit back
shlc	;continue the shift
phi r15 ;save it for the carry test
ani 0x0f ;clear the 10 bit
str r8	;put the digit back
ghi r15	;now test for carry
smi 0x10 ; this will make df 1 if the 10 bit is set
dec r9	;decrement the digit count
glo r9
bnz $$dshlp ;back for more if needed

dec r15
glo r15
bnz $$bitloop

cpy2 r15,r8	;save the starting location of the digits
ldi 10		;digit count again
plo r9
$$upnxt:
ldn r8		;get digit
ori 0x30	;make ascii
str r8		;put it back
inc r8		;next digit
dec r9		;counter
glo r9
bnz $$upnxt	;upgrade all 10 spots

ldaX memaddr,sp,(2+4+2+1)	;point to lsb of desired digit count
sex memaddr	;set up
ldi 10		;max number of 0's to skip
sm		;desired number of digits to skip
sex sp		;reset index register
plo r9		;number of leading 0's to skip
$$cknext:
ldn r15		;check digit
smi 0x30	;for '0'
bnz $$done
inc r15		;next digit
dec r9		;reduce count
glo r9
bnz $$cknext
$$done:
cretn
; **********************************
; R10  - BINARY BIT COUNT
; r12 & r13 - BINARY NUMBER
; R8 - INDEX REGISTER
; R9 - LOW db STORES LOCAL LOOP COUNTER
; R9 - HIGH db SAVES CURRENT BCD DIGIT
; R14 - LOW db STORES ACTIVE BCD DIGIT COUNT
; R14 - HIGH db SAVES CARRY VALUE (DF)
; **********************************
align 256
BGNDIG:         db    0,0,0,0,0,0,0,0,0
ENDDIG:         db    1

CONVRT:         db    $00,$CE,$ED,$BB         ; DECIMAL 847,291
_dd32cr1:
; -----------------
; *** SET UP INDEX REGISTER LOAD
ldad    R8,ENDDIG
sex			R8
ldad		R11,ENDDIG
; -----------------
; *** BINARY NUMBER TO CONVERT comes in r12 AND r13
; -----------------
; *** SET UPPER BYTE OF R10 TO 1
LDI     1
PHI     R10              ;STORE CONSTANT 1 INTO HIGH db OF R10
PLO     R14             ;ACTIVE BCD DIGIT COUNT -- STARTS AT 1
; -----------------
; *** SET BINARY BIT COUNT IN LOW db OF R10
LDI     32
PLO     R10
; -----------------
; SHIFT OUT HIGH ORDER ZERO BITS OF BINARY NUMBER

SHFOUT:     GLO     r13
SHLC
PLO     r13
;           -----------------
GHI     r13
SHLC
PHI     r13
;           -----------------
GLO     r12
SHLC
PLO     r12
;           -----------------
GHI     r12
SHLC
PHI     r12
;           -----------------
DEC     R10              ;DECREMENT BINARY BIT COUNT
BNF     SHFOUT
;********

; -----------------
; *** MAIN DOUBLE DABBLE LOOP
NLOOP:
; -----------------
; SHIFT OUT HIGH-ORDER BIT OF BINARY NUMBER
; -----------------
GLO     r13
SHLC
PLO     r13
;           -----------------
GHI     r13
SHLC
PHI     r13
;           -----------------
GLO     r12
SHLC
PLO     r12
;           -----------------
GHI     r12
SHLC
PHI     r12
; -----------------
; SET INDEX REGISTER (LOW db ONLY)
GLO     R11              ;GET INDEX LOW db
PLO     R8             ;STORE IN INDEX REG.
; -----------------
; CALCULATE LOOP COUNT
GLO     R14             ;GET ACTIVE BCD DIGIT COUNT
PLO     R9             ;STORE LOCAL LOOP COUNT
UNILP:
; -----------------
; *** SAVE DF (CARRY) IN UPPER db OF R14
SHLC                    ;GET CARRY TO LOW-ORDER BIT OF D
PHI     R14             ;SAVE D IN UPPER db OF R14
; ----------------
; *** TEST ONE db FOR PRE-CORRECTION
LDX                     ;LOAD D FROM INDEX ADDRESS
PHI     R9             ;SAVE BCD DIGIT IN UPPER db OF R9
SMI     5               ;IS D > 4
BNF     NOFIX           ;SKIP CORRECTION IF D < 0
; *** PRE-CORRECT BCD DIGIT
ADI     128             ;ADD 3 CORRECTION + 5 RESTORE + 120
PHI     R9             ;SAVE BCD DIGIT IN UPPER db OF R9
NOFIX:
; -----------------
; SHIFT ONE BCD DIGIT
; -----------------
GHI     R14             ;GET CARRY BACK TO D
SHR                     ;PUT CARRY VALUE INTO DF
GHI     R9             ;GET WORKING BCD DIGIT
SHLC                    ;ROTATE D THROUGH CARRY
STXD                    ;STORE D AND DECREMENT INDEX REGISTER
; -----------------
; *** UNILP COUNTER OVERHEAD
DEC     R9             ;DECREMENT CORRECT-SIFT LOOP COUNTER
GLO     R9             ;D = LOCAL LOOP COUNT
BNZ     UNILP           ;LOOP UNTIL DONE
; -----------------
; *** IF DF = 1, CREATE NEW BCD DIGIT = 1 -- INCREMENT ACTIVE BCD DIGIT COUNT
BNF     SKPDIG          ;IF CARRY IS ZERO, NO NEW BCD DIGIT
INC     R14             ;INCREMENT ACTIVE BCD DIGIT COUNT
GHI     R10              ;GET A db WITH VALUE OF 1
STXD                    ;STORE D IN NEW BCD DIGIT POSITION
; -----------------
; *** MAIN LOOP COUNTER OVERHEAD
SKPDIG:     DEC     R10              ;DECREMENT MASTER LOOP COUNTER
GLO     R10              ;D = BINARY BIT COUNT
BNZ     NLOOP           ;LOOP UNTIL DONE

bail:				ldad		R15,BGNDIG			;point to converted number
sex			R2
cretn										;return to caller

UPDATE: WOW. I tested the latest routine from Charles. It clocked in at 757 instructions to convert the same 12345 test number. Again, not a fair comparison but it indicates it’s worth pursuing. Code follows:


NUMBER		EQU	0

;
; Register Definitions:
;
R0		EQU	0
R1		EQU	1
R2		EQU	2
R3		EQU	3
R4		EQU	4
R5		EQU	5
R6		EQU	6
R7		EQU	7
R8		EQU	8
R9		EQU	9
R10		EQU	10
R11		EQU	11
R12		EQU	12
R13		EQU	13
R14		EQU	14
R15		EQU	15

; **********************************
; R5  - LOW BYTE = LOW BYTE OF INDEX REGISTER VALUE
; R6  - BINARY BIT COUNT
; R8  - POINTER TO BINARY NUMBER
; R9  - UPPER BYTE IS PART OF BINARY NUMBER
; R9  - LOWER BYTE IS BYTE SHIFT COUNT
; R12 - INDEX REGISTER
; R13 - LOW BYTE STORES LOCAL LOOP COUNTER
; R13 - HIGH BYTE SAVES CURRENT BCD DIGIT
; R14 - LOW BYTE STORES ACTIVE BCD DIGIT COUNT
; R14 - HIGH BYTE SAVES CARRY VALUE (DF)
; **********************************

LBR     start

BGNDIG:         DB      84,129,91,194,132,49,81,49,71
ENDDIG:         DB      191

CONVRT:         DB      00,00,48,057        ; DECIMAL 12,345

ORG	100H
START:
; -----------------
; *** LOAD BINARY NUMBER ADDRESS TO R8
LDI     CONVRT/256
PHI     R8
LDI     CONVRT
PLO     R8
; -----------------
; *** SET BINARY BIT COUNT IN LOW BYTE OF R6
LDI     32           ;LOWER R6 = TOTAL BIT COUNT
PLO     R6
; -----------------
; *** HIGH R9 = BYTE OF BINARY NUMBER
DOMORE:         LDA     R8
; -----------------
; *** IF ZERO BYTE, ADJUST R6 SHIFT COUNT AND TRY AGAIN
BNZ     NOMORE
GLO     R6           ;GET SHIFT COUNT
SMI     8            ;SUBTRACT ONE BYTE OF 8 BITS
PLO     R6           ;PUT BACK SHIFT COUNT
BR      DOMORE       ;GET ANOTHER BINARY BYTE
; -----------------
; *** RELOAD BINARY BYTE -- RESET COUNT TO 8
NOMORE:         PHI     R9
LDI     8
PLO     R9
; -----------------
; *** CURRENT BYTE HAS A ONE BIT
; -----------------
; *** SHIFT OUT HIGH ORDER ZERO BITS OF BINARY NUMBER
SHFOUT:         GHI     R9
SHL
PHI     R9
; -----------------
; *** CHECK FOR BYTE RELOAD
DEC     R9           ;DECREMENT BYTE BIT COUNT
CONTIN:         DEC     R6           ;DECREMENT TOTAL BIT COUNT
BNF     SHFOUT
; -----------------
; *** SET UP INDEX REGISTER LOAD
SEX     R12
LDI     ENDDIG/256
PHI     R12
LDI     ENDDIG
PLO     R5
PLO     R12
; -----------------
; *** SET UPPER BYTE OF R6 TO 1
LDI     1
PHI     R6              ;HIGH BYTE OF R6 IS CONSTANT 1
PLO     R14             ;ACTIVE BCD DIGIT COUNT -- STARTS AT 1
; -----------------
; SET LOW-ORDER BCD DIGIT TO 1
STXD
;
;
;
; -----------------
; *** MAIN DOUBLE DABBLE LOOP
NLOOP:
; -----------------
; SHIFT BIT OF BINARY NUMBER INTO DF (CARRY)
; -----------------
GHI     R9
SHL
PHI     R9
; -----------------
; *** CHECK FOR BYTE RELOAD
DEC     R9
GLO     R9
BNZ     SKLOAD
; -----------------
; *** RELOAD BINARY BYTE -- RESET COUNT TO 8
LDA     R8
PHI     R9
LDI     8
PLO     R9
; -----------------
; SET INDEX REGISTER (LOW BYTE ONLY)
SKLOAD:         GLO     R5              ;GET INDEX LOW BYTE
PLO     R12             ;STORE IN INDEX REG.
; -----------------
; GET ACTIVE BCD DIGIT COUNT TO LOOP COUNTER R13
GLO     R14             ;GET ACTIVE BCD DIGIT COUNT
PLO     R13             ;STORE LOCAL LOOP COUNT
UNILP:
; -----------------
; *** SAVE DF (CARRY) IN UPPER BYTE OF R14
SHLC                    ;GET CARRY TO LOW-ORDER BIT OF D
PHI     R14             ;SAVE D IN UPPER BYTE OF R14
; ----------------
; *** TEST ONE BYTE FOR PRE-CORRECTION
LDX                     ;LOAD D FROM INDEX ADDRESS
PHI     R13             ;SAVE BCD DIGIT IN UPPER BYTE OF R13
SMI     5               ;IS D > 4
BNF     NOFIX           ;SKIP CORRECTION IF D < 0
; *** PRE-CORRECT BCD DIGIT
ADI     128             ;ADD 3 CORRECTION + 5 RESTORE + 120
PHI     R13             ;SAVE BCD DIGIT IN UPPER BYTE OF R13
NOFIX:
; -----------------
; SHIFT ONE BCD DIGIT
; -----------------
GHI     R14             ;GET CARRY BACK TO D
SHR                     ;PUT CARRY VALUE INTO DF
GHI     R13             ;GET WORKING BCD DIGIT
SHLC                    ;ROTATE D THROUGH CARRY
STXD                    ;STORE D AND DECREMENT INDEX REGISTER
; -----------------
; *** UNILP COUNTER OVERHEAD
DEC     R13             ;DECREMENT CORRECT-SHIFT LOOP COUNTER
GLO     R13             ;D = LOCAL LOOP COUNT
BNZ     UNILP           ;LOOP UNTIL DONE
; -----------------
; *** IF DF = 1, CREATE NEW BCD DIGIT = 1 -- INCREMENT ACTIVE BCD DIGIT COUNT
BNF     SKPDIG          ;IF CARRY IS ZERO, NO NEW BCD DIGIT
INC     R14             ;INCREMENT ACTIVE BCD DIGIT COUNT
GHI     R6              ;GET A BYTE WITH VALUE OF 1
STXD                    ;STORE D IN NEW BCD DIGIT POSITION
; -----------------
; *** MAIN LOOP COUNTER OVERHEAD
SKPDIG:         DEC     R6              ;DECREMENT MASTER LOOP COUNTER
GLO     R6              ;D = BINARY BIT COUNT
BNZ     NLOOP           ;LOOP UNTIL DONE
; -----------------
; *** ZERO REMAINING HIGH ORDER BCD DIGITS
GLO     R14             ;GET LAST ACTIVE BCD DIGIT COUNT
SDI     10              ;COMPUTE REMAINING BCD DIGIT COUNT
PLO     R6              ;AND STORE IN LOOP COUNTER
CLEAR:          GLO     R13             ;GET ZERO FROM LOW BYTE OF R13
STXD                    ;STORE ZERO IN UNUSED BCD DIGITS
DEC     R6
GLO     R6
BNZ     CLEAR
; -----------------
IDL
END
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: