6502.org Forum Projects Code Documents Tools Forum
It is currently Thu Sep 19, 2024 11:00 pm

View unanswered posts | View active topics


Board index » 6502.org Users Forum » Programming

All times are UTC




Post new topic Reply to topic  Page 2 of 2
  [ 26 posts ]  Go to page Previous  1, 2
  Previous topic | Next topic 
Author Message
teamtempest
 Post subject: Re: binary to ascii
PostPosted: Sat Sep 07, 2013 1:34 am 
Offline

Joined: Sun Nov 08, 2009 1:56 am
Posts: 395
Location: Minnesota
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:

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

    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...
Top
 Profile  
Reply with quote  
wwl
 Post subject: Re: binary to ascii
PostPosted: Sat Sep 07, 2013 10:27 am 
Offline

Joined: Thu Sep 05, 2013 2:28 pm
Posts: 8
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.
Top
 Profile  
Reply with quote  
wwl
 Post subject: Re: binary to ascii
PostPosted: Sat Sep 07, 2013 11:04 am 
Offline

Joined: Thu Sep 05, 2013 2:28 pm
Posts: 8
teamtempest wrote:
So that was helpful. A looping version pretty easily follows:

Code:
    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:
    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
Top
 Profile  
Reply with quote  
Klaus2m5
 Post subject: Re: binary to ascii
PostPosted: Sat Sep 07, 2013 1:20 pm 
Offline

Joined: Sat Jul 28, 2012 11:41 am
Posts: 442
Location: Wiesbaden, Germany
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. 8)

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

_________________
6502 sources on GitHub: https://github.com/Klaus2m5


Last edited by Klaus2m5 on Sun Sep 08, 2013 5:22 am, edited 2 times in total.

Top
 Profile  
Reply with quote  
teamtempest
 Post subject: Re: binary to ascii
PostPosted: Sat Sep 07, 2013 8:28 pm 
Offline

Joined: Sun Nov 08, 2009 1:56 am
Posts: 395
Location: Minnesota
Code:
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:

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.
Top
 Profile  
Reply with quote  
Klaus2m5
 Post subject: Re: binary to ascii
PostPosted: Sat Sep 07, 2013 9:37 pm 
Offline

Joined: Sat Jul 28, 2012 11:41 am
Posts: 442
Location: Wiesbaden, Germany
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.

_________________
6502 sources on GitHub: https://github.com/Klaus2m5
Top
 Profile  
Reply with quote  
wwl
 Post subject: Re: binary to ascii
PostPosted: Sun Sep 08, 2013 9:21 am 
Offline

Joined: Thu Sep 05, 2013 2:28 pm
Posts: 8
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
Top
 Profile  
Reply with quote  
Klaus2m5
 Post subject: Re: binary to ascii
PostPosted: Sun Sep 08, 2013 2:43 pm 
Offline

Joined: Sat Jul 28, 2012 11:41 am
Posts: 442
Location: Wiesbaden, Germany
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.

_________________
6502 sources on GitHub: https://github.com/Klaus2m5
Top
 Profile  
Reply with quote  
wwl
 Post subject: Re: binary to ascii
PostPosted: Sun Sep 08, 2013 4:07 pm 
Offline

Joined: Thu Sep 05, 2013 2:28 pm
Posts: 8
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
Top
 Profile  
Reply with quote  
dclxvi
 Post subject: Re: binary to ascii
PostPosted: Sun Sep 08, 2013 11:29 pm 
Offline
User avatar

Joined: Thu Mar 11, 2004 7:42 am
Posts: 362
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.
Top
 Profile  
Reply with quote  
White Flame
 Post subject: Re: binary to ascii
PostPosted: Mon Sep 09, 2013 4:10 am 
Offline

Joined: Tue Jul 24, 2012 2:27 am
Posts: 674
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

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 2 of 2
  [ 26 posts ]  Go to page Previous  1, 2

Board index » 6502.org Users Forum » Programming

All times are UTC


Who is online

Users browsing this forum: Google [Bot] and 6 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
6502.org is an ongoing project by Mike Naberezny and contributors.