Page 2 of 2
Re: binary to ascii
Posted: Sat Sep 07, 2013 1:34 am
by teamtempest
Oh how I spend my Friday nights
In order to help me understand what's going on in that one-byte original version, I decided it would be helpful to write a version that didn't loop at all:
Code: Select all
; first char: A = 0..255
; 2xx -> %10
; 1xx -> %01
; 0xx -> %00
cmp #200
bcc @1 ; A = 0..199
sbc #200 ; A = 0..55
@1 rol outchar ; %1,%0
; A = 0..199 or 0..55
cmp #100
bcc @2 ; A = 0..99
sbc #100 ; A = 0..99
@2 rol outchar ; %10,%01,%00
tax
lda outchar
and #$03
ora #$30
jsr output
txa
; second char: A = 0..99
; 9x -> %1001
; 8x -> %1000
; 7x -> %0111
; 6x -> %0110
; 5x -> %0101
; 4x -> %0100
; 3x -> %0011
; 2x -> %0010
; 1x -> %0001
; 0x -> %0000
cmp #80
bcc @3 ; A = 0..79
sbc #80 ; A = 0..19
@3 rol outchar ; %1,%0
; A = 0..79 or 0..19
cmp #40
bcc @4 ; A = 0..39
sbc #40 ; A = 0..39
@4 rol outchar ; %10,%01,%00
; A = 0..39
cmp #20
bcc @5 ; A = 0..19
sbc #20 ; A = 0..19
@5 rol outchar ; %100,%011,%010,%000
; A = 0..19
cmp #10
bcc @6 ; A = 0..9
sbc #10 ; A = 0..9
@6 rol outchar ; %1001,%1000,%0111,%0110
; %0101,%0100,%0011,%0010,%0000
tax
lda outchar
and #$0F
ora #$30
jsr output
txa
; third char: A = 0..9
; 9 -> %1001
; 8 -> %1000
; 7 -> %0111
; 6 -> %0110
; 5 -> %0101
; 4 -> %0100
; 3 -> %0011
; 2 -> %0010
; 1 -> %0001
; 0 -> %0000
cmp #8
bcc @7 ; A = 0..7
sbc #8 ; A = 0..1
@7 rol outchar ; %1,%0
; A = 0..7 or 0..1
cmp #4
bcc @8 ; A = 0..3
sbc #4 ; A = 0..3
@8 rol outchar ; %10,%01,%00
; A = 0..3
cmp #2
bcc @9 ; A = 0..1
sbc #2 ; A = 0..1
@9 rol outchar ; %100,%011,%010,%000
; A = 0..1
cmp #1
bcc @10 ; A = 0
sbc #1 ; A = 0
@10 rol outchar ; %1001,%1000,%0111,%0110
; %0101,%0100,%0011,%0010,%0000
lda outchar
and #$0F
ora #$30
jsr output
rts
; alternatively:
; A = 0..1
; cmp #1 (or) lsr
; rol outchar
So that was helpful. A looping version pretty easily follows:
Code: Select all
ldy #$00
sty outchar
ldy #2
ldx #10-1
@1 cmp table,x
bcc @2
sbc table,x
@2 rol outchar
dex
dey
bne @1
tay
lda outchar
and #$0F
ora #$30
jsr output
tya
ldy #4
cpx #-1
bne @1
rts
table: byte 1,2,4,8,10,20,40,80,100,200
... or something like that...
Re: binary to ascii
Posted: Sat Sep 07, 2013 10:27 am
by wwl
You are mixing the compare and subtract constant table .A with the preset for .B ...
No! I started with the assumption that all values in .A have to be of the form 2^A*10^B and (may be that was wrong?) that they have to be maximal but lower than 2^16. With this I get the .A values:
2^02*10^4
2^06*10^3
2^09*10^2
2^12*10^1
2^14*10^0
the difference betwenn the exponents to the base 2 factores + 1 would then be the number of shifts.
But as I wrote: maybe my above assumption was wrong.
Re: binary to ascii
Posted: Sat Sep 07, 2013 11:04 am
by wwl
So that was helpful. A looping version pretty easily follows:
Code: Select all
ldy #$00
sty outchar
ldy #2
ldx #10-1
@1 cmp table,x
bcc @2
sbc table,x
@2 rol outchar
dex
dey
bne @1
tay
lda outchar
and #$0F
ora #$30
jsr output
tya
ldy #4
cpx #-1
bne @1
rts
table: byte 1,2,4,8,10,20,40,80,100,200
... or something like that...
You can use the $4C/$13 trick too:
Code: Select all
LDX #9
ldy #$4c
A1 sty outchar
A2 cmp table,x
bcc A3
sbc table,x
A3 ROL outchar
DEX
BCC A2
TAY
lda outchar
JSR OUTPUT
TXA
bmi A4
TYA
ldy #$13
bne A1
A4 rts
table .DB 1,2,4,8,10,20,40,80,100,200
Re: binary to ascii
Posted: Sat Sep 07, 2013 1:20 pm
by Klaus2m5
You are mixing the compare and subtract constant table .A with the preset for .B ...
No! I started with the assumption that all values in .A have to be of the form 2^A*10^B and (may be that was wrong?) that they have to be maximal but lower than 2^16. With this I get the .A values:
2^02*10^4
2^06*10^3
2^09*10^2
2^12*10^1
2^14*10^0
the difference betwenn the exponents to the base 2 factores + 1 would then be the number of shifts.
But as I wrote: maybe my above assumption was wrong.
The assumption itself is not wrong but the assumption of what A is going to be in 2^A*10^B.
It hopefully gets clearer if one writes:
2^2*10^4
2^3*10^3*2^2
2^3*10^2*2^5
2^3*10^1*2^8
2^3*10^0*2^11
The first part (2^A) describes the number of bits necessary to decode 1 digit, the last part (2^C) compensates the number of shifts done on the accumulator on the previous digits.
@RichTW: So converting to 16-bit is not as bad as I thought.
I have done a bit of cycle and space counting, teamtempest modified by wwl versus outdec8z.
outdec8z wins at space: 39 Bytes of code and table + 1 Byte ZP-RAM
teamtempest/wwl: 44 Bytes c&d (mainly due to the larger table) + 1zp
Teamptempest/wwl wins cycle count worst case (all CMP/SBC must be done): 296 cycles
outdec8z under same condition: 345 cycles
edit: corrected byte count 44 due to miscounted table size
edit2: corrected cycle count for 10 iterations instead of erroneously counted 8
Re: binary to ascii
Posted: Sat Sep 07, 2013 8:28 pm
by teamtempest
Code: Select all
You can use the $4C/$13 trick too:
Code:
LDX #9
ldy #$4c
A1 sty outchar
A2 cmp table,x
bcc A3
sbc table,x
A3 ROL outchar
DEX
BCC A2
TAY
lda outchar
JSR OUTPUT
TXA
bmi A4
TYA
ldy #$13
bne A1
A4 rts
table .DB 1,2,4,8,10,20,40,80,100,200
I like it! I think it can be made one byte shorter and three cycles faster, though:
Code: Select all
Code:
LDX #10-1
ldy #$13 << 2 ; $13 * 4 if shifts not supported
A1 sty outchar
A2 cmp table,x
bcc A3
sbc table,x
A3 ROL outchar
DEX
BCC A2
TAY
lda outchar
JSR OUTPUT
TYA
ldy #$13
cpx #0
bne A1
A4 rts
table .DB 1*1,1*2,1*4,1*8
.DB 10*1,10*2,10*4,10*8
.DB 100*1,100*2
Still, I count 43 bytes - I don't believe the table would be in zero page, so that adds a couple.
Re: binary to ascii
Posted: Sat Sep 07, 2013 9:37 pm
by Klaus2m5
Still, I count 43 bytes - I don't believe the table would be in zero page, so that adds a couple.
I counted 8 for the table size but it is actually 10. However, it must be CPX #$FF.
edit: Oh dear, my previous post was really wrong as I counted the number of iterations on both codes as 8 but they are really 10. The ratio however was sort of correct. I update the numbers in the original post.
Re: binary to ascii
Posted: Sun Sep 08, 2013 9:21 am
by wwl
The assumption itself is not wrong but the assumption of what A is going to be in 2^A*10^B.
It hopefully gets clearer if one writes:
2^2*10^4
2^3*10^3*2^2
2^3*10^2*2^5
2^3*10^1*2^8
2^3*10^0*2^11
If my assumption would be right, then the second value for example should be:
2^6*10^3 or 2^3*10^3*2^3
and then you need one shift more. The output initialisation should then be not $13 but $89 (10001001) in which bit 3 is the shift stopper bit. And if we had an ROL that immediately rotates the most significant bit in (without carry) it would be ok because the last remainder is lower than 2^6*10^3. Thats why 2^5*10^3 is working.
Wolfgang
Re: binary to ascii
Posted: Sun Sep 08, 2013 2:43 pm
by Klaus2m5
Wolfgang,
are you trying to tell us, that it works even while we don't know what we are doing?
What's wrong with:
The first part (2^A) describes the number of bits necessary to decode 1 digit, the last part (2^C) compensates the number of shifts done on the accumulator on the previous digits.
and previously posted
One decimal digit in the output is made of four bit values (1,2,4,8). So you always need four shifts to decode one digit, except the topmost digit for 16-bit is 3 shifts as it can only represent 0-6.
that you choose to ignore?
On a 16-bit value the most significant digit has only 3 bits (max value of 6, 3 shifts of B., B. precharged with $26). The binary operand in the accumulator is only shifted twice (not shifted on the highest value bit 2^2). You need to compensate only for 2 shifts. That is simply 2^5*10^3 or 2^3*10^3*2^2 on the second digit. All other digits have 4 bits (max value of 9, 4 shifts of B., B. precharged with $13). The binary operand in the accumulator is shifted 3 times (not shifted on the highest value bit 2^3). For the remaining digits after the second digit you need to compensate for 3 more shifts each time.
Look at RichTW´s 16-bit Version here:
viewtopic.php?f=2&t=2656#p28310
Do you see 5 shifts anywhere?
If someone has a better explanation go ahead. I am out of ideas how to make it clear.
Re: binary to ascii
Posted: Sun Sep 08, 2013 4:07 pm
by wwl
Wolfgang,
are you trying to tell us, that it works even while we don't know what we are doing?
What's wrong with:
The first part (2^A) describes the number of bits necessary to decode 1 digit, the last part (2^C) compensates the number of shifts done on the accumulator on the previous digits.
and previously posted
One decimal digit in the output is made of four bit values (1,2,4,8). So you always need four shifts to decode one digit, except the topmost digit for 16-bit is 3 shifts as it can only represent 0-6.
that you choose to ignore?
On a 16-bit value the most significant digit has only 3 bits (max value of 6, 3 shifts of B., B. precharged with $26). The binary operand in the accumulator is only shifted twice (not shifted on the highest value bit 2^2). You need to compensate only for 2 shifts. That is simply 2^5*10^3 or 2^3*10^3*2^2 on the second digit. All other digits have 4 bits (max value of 9, 4 shifts of B., B. precharged with $13). The binary operand in the accumulator is shifted 3 times (not shifted on the highest value bit 2^3). For the remaining digits after the second digit you need to compensate for 3 more shifts each time.
Look at RichTW´s 16-bit Version here:
viewtopic.php?f=2&t=2656#p28310
Do you see 5 shifts anywhere?
If someone has a better explanation go ahead. I am out of ideas how to make it clear.
Nothing is wrong with the above!
I only thought about my assumption, that the used constants have to be the max values of the form 2^A*10^B. This assumption is wrong because there is no 'has to'. But it is not entirely wrong. That's what I tried to explain in my last post. It's ok if nobody is further interested in this. The original question is more than solved.
Thank you all, Wolfgang
Re: binary to ascii
Posted: Sun Sep 08, 2013 11:29 pm
by dclxvi
You can click on history at the bottom of a wiki page and see who made what additions and edits.
I wrote a how it works section and added it to the wiki, but I see you people have been busy posting to this thread in the meantime, so the how it works section is pretty much all overlap.
I don't know of any name for this algorithm.
OUTDEC8 and OUTDEC8S do not require a 65C02.
Re: binary to ascii
Posted: Mon Sep 09, 2013 4:10 am
by White Flame
Wolfgang: The interesting thing about the original algorithm is that it does 10 shifts across the accumulator in total. For each digit, a zero is "unshifted" into the top of the accumulator via LSR, so the acc only gets truly shifted by 1 less than the number of bits outputted. That is why the cumulative effects of shifting need to be tracked.
100s digit, acc is unshifted, 2 bits are outputted, net effect on acc is <<1.
10s digit, acc is unshifted, 4 bits outputted, net effect on acc is <<3, or a total of <<4.
1s digit, acc is unshifted, 4 bits outputted, net effect on acc is <<3, or a total of <<7.
The constants in .A are built by looking at the history of shifts before that operation. We want to compare every digit against {8,4,2,1}, except the top digit will just be against {2,1}:
200 << 0 = 200
80 << 1 = 160
8 << 4 = 128