binary to ascii

[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...

[wwl]

Klaus2m5 wrote:

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.

[wwl]

teamtempest wrote:

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

[Klaus2m5]

wwl wrote:

Klaus2m5 wrote:

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

[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.

[Klaus2m5]

teamtempest wrote:

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.

[wwl]

Klaus2m5 wrote:

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

[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:

Quote:

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

Quote:

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.

[wwl]

Klaus2m5 wrote:

Wolfgang,

are you trying to tell us, that it works even while we don't know what we are doing?

What's wrong with:

Quote:

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

Quote:

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

[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.

[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