| | Krill
Registered: Apr 2002
Posts: 2825 |
Bitwise GCR decoding
This is some kind of ongoing basic research pet project of mine, possibly re-inventing the wheel, and so far with fewer opportunities for practical application than i've hoped.
Posting this here because it might be of interest to some and may lead to more insights than i've had so far. =)
Consider the traditional Commodore GCR to raw nibble mapping:$09 %01001 -> %1000 $08
$0a %01010 -> %0000 $00
$0b %01011 -> %0001 $01
$0d %01101 -> %1100 $0c
$0e %01110 -> %0100 $04
$0f %01111 -> %0101 $05
$12 %10010 -> %0010 $02
$13 %10011 -> %0011 $03
$15 %10101 -> %1111 $0f
$16 %10110 -> %0110 $06
$17 %10111 -> %0111 $07
$19 %11001 -> %1001 $09
$1a %11010 -> %1010 $0a
$1b %11011 -> %1011 $0b
$1d %11101 -> %1101 $0d
$1e %11110 -> %1110 $0e A decoder must know all 5 GCR bits in order to decode a raw nibble.
Consider an alternative GCR to raw nibble mapping:$09 %01001 -> %1111 $0f
$0a %01010 -> %1110 $0e
$0b %01011 -> %1101 $0d
$0d %01101 -> %1100 $0c
$0e %01110 -> %1011 $0b
$0f %01111 -> %1010 $0a
$12 %10010 -> %0100 $04
$13 %10011 -> %0011 $03
$15 %10101 -> %0010 $02
$16 %10110 -> %0001 $01
$17 %10111 -> %0000 $00
$19 %11001 -> %1001 $09
$1a %11010 -> %1000 $08
$1b %11011 -> %0111 $07
$1d %11101 -> %0110 $06
$1e %11110 -> %0101 $05 This mapping has some interesting properties, which become apparent with different representations: [0] 6
/ \
/ \ [0] f
/ \ / \ +0
/ \ / [1] f 1111
/ \ / +2
/ \ +4 [0] d
/ \ / \ +0
/ \ / \ [0] e 1110
/ \ / \ / +1
/ \ / +3 [1] d
/ \ / \ +0
/ +6 [1] a [1] d 1101
/ \
/ \ +0 [0] c
/ \ / \ +0
/ \ / [1] c 1100
/ \ / +2
/ [1] a
/ \ +0
/ \ [0] b 1011
GCR|+16 +8 +4 +2 +1 \ / +1
0| +6 +0 +3 +2 +1 decode [1] a
1| +0 +4 +0 +0 +0 to raw \ +0
\ [1] a 1010
\
\ [0] 3
\ / \ +0
\ / \ [0] 4 0100
\ / \ / +1
\ / +3 [1] 3
\ / \ +0
\ +0 [0] 0 [1] 3 0011
\ / \
\ / \ +0 [0] 2
\ / \ / \ +0
\ / \ / [1] 2 0010
\ / \ / +2
\ / +0 [1] 0
\ / \ +0
\ / \ [0] 1 0001
\ / \ / +1
\ / [1] 0
\ / \ +0
[1] 0 [1] 0 0000
\
\ [0] 9
\ / \ +0
\ / [1] 9 1001
\ / +2
\ +4 [0] 7
\ / \ +0
\ / \ [0] 8 1000
\ / \ / +1
\ / +3 [1] 7
\ / \ +0
[1] 4 [1] 7 0111
\
\ +0 [0] 6
\ / \ +0
\ / [1] 6 0110
\ / +2
[1] 4
\ +0
\ [0] 5 0101
\ / +1
[1] 4The GCR values form some kind of positional number system.
Each GCR bit position/value pair maps to a decoded value.
The individual decoded values of all 5 GCR nibble bits can be added to decode a raw nibble.
As the add operation is commutative and associative, a decoder can consume GCR nibbles piece-wise in any order of the input bits.
This can be used to decode a GCR stream like so:ldx $1c01 ; 00000111
lda decode01,x; 00001... - nibble 0 complete, nibble 1 partial
[...]
ldx $1c01 ; 11222223
adc decode1,x ; 00001111 - byte 0 complete
[...]
lda decode23,x; 22223... - nibble 2 complete, nibble 3 partial
ldx $1c01 ; 33334444
adc decode3,x ; 22223333 - byte 1 complete
[...] This concept can also be used to decode a GCR stream on-the-fly while it is sent over the serial bus in bitpairs.
Note that an additional look-up would be required to map the custom-GCR decoded bytes to original standard Commodore GCR decoded bytes.
As the individual decoding tables take the better part of 256 indices each, memory required for them quickly becomes quite big.
This is problematic with the 2 KB of RAM of a 1541.
There may be opportunities to squeeze the tables together or apply other optimisations, considering these 16 mappings which satisfy the bitwise GCR decoding constraints.GCR: 4 3 2 1 0
1. 0: 2, 4, 1, 6, 0
1: 0, 0, 0, 0, 5
2. 0: 1, 2, 3, 6, 0
1: 0, 0, 0, 0, 5
3. 0: 3, 0, 0, 2, 1
1: 0, 2, 8, 0, 0
4. 0: 3, 6, 0, 2, 1
1: 0, 0, 7, 0, 0
5. 0: 6, 0, 3, 2, 1
1: 0, 4, 0, 0, 0
6. 0: 0, 6, 3, 2, 1
1: 5, 0, 0, 0, 0
7. 0: 3, 0, 8, 2, 1
1: 0, 2, 0, 0, 0
8. 0: 6, 0, 0, 4, 2
1: 0, 4, 1, 0, 0
9. 0: 6, 0, 1, 4, 2
1: 0, 4, 0, 0, 0
10. 0: 0, 6, 1, 4, 2
1: 5, 0, 0, 0, 0
11. 0: 1, 2, 0, 0, 3
1: 0, 0, 8, 2, 0
12. 0: 1, 2, 8, 0, 3
1: 0, 0, 0, 2, 0
13. 0: 1, 2, 0, 6, 3
1: 0, 0, 7, 0, 0
14. 0: 2, 4, 0, 0, 6
1: 0, 0, 1, 4, 0
15. 0: 2, 4, 1, 0, 6
1: 0, 0, 0, 4, 0
16. 0: 1, 2, 3, 0, 6
1: 0, 0, 0, 4, 0 |
|
| | Oswald
Registered: Apr 2002
Posts: 5017 |
I dont understand, but why not huffmann gcr then :D that tree just looks like it. |
| | Krill
Registered: Apr 2002
Posts: 2825 |
Quoting Oswaldwhy not huffmann gcr All 16 encoded symbols have the same size and probability. |
| | Oswald
Registered: Apr 2002
Posts: 5017 |
why does the add operation work, why doesnt it matter if ther is overflow on nibble boundaries ? why doesnt it matter if you add a nibble to a byte that's not even present in it? |
| | Krill
Registered: Apr 2002
Posts: 2825 |
Quoting Oswaldwhy does the add operation work See OP.
Quoting Oswaldwhy doesnt it matter if ther is overflow on nibble boundaries ? There is no overflow of bit 7 to carry (or from one decoded nibble to the left-hand neighbour), and the carry flag being clear initially is implied.
Quoting Oswaldwhy doesnt it matter if you add a nibble to a byte that's not even present in it? I don't understand the question. |
| | Oswald
Registered: Apr 2002
Posts: 5017 |
ldx $1c01 ; 11222223
adc decode1,x ; 00001111 - byte 0 complete
2222233 gcr bits are not present in the resulting byte, how does it still work?
if there is no overflow then you could just OR ?
"See OP."
I'm asking coz I didnt understand.You could just answer that to each of my Q.
lot of things are unknown tho most of us here imho, like at 1c01 you get a full gcr nibble, or a byte with partial nibbles, how exactly the gcr data comes in ?
why there is 2 ldx for the first byte and 1 for the 2nd ? |
| | Krill
Registered: Apr 2002
Posts: 2825 |
Quoting Oswaldldx $1c01 ; 11222223
adc decode1,x ; 00001111 - byte 0 complete
2222233 gcr bits are not present in the resulting byte, how does it still work? Nibbles 2 and 3 are decoded to the next byte in just the following snippet you have casually omitted:
Quoting Krilllda decode23,x; 22223... - nibble 2 complete, nibble 3 partial
ldx $1c01 ; 33334444
adc decode3,x ; 22223333 - byte 1 complete Quoting Oswaldif there is no overflow then you could just OR ? There is no overflow from one decoded nibble/byte to the next, but there is "overflow" from bits within a (partially) decoded nibble. The partially decoded values generally aren't powers of 2, so you must use some arithmetical operation (add/sub) to "smear" them across a decoded nibble, not a logical/bitwise operation (and/or/eor).
Quoting Oswald"See OP."
I'm asking coz I didnt understand.You could just answer that to each of my Q. That was in response to "why does add work". The entire OP is about using add for partial GCR decoding, and why this works. Please ask more precise questions.
Quoting Oswaldlot of things are unknown tho most of us here imho, like at 1c01 you get a full gcr nibble, or a byte with partial nibbles, how exactly the gcr data comes in ? $1c01 gives a byte-wise stream of GCR nibbles rolling in from disk. 5 bytes (10 nibbles) of GCR data encode 4 raw bytes (8 nibbles):00000111 11222223 33334444 45555566 66677777 The problem is that 4 of the encoded GCR nibbles within such a 5-byte GCR stream-chunk are spread across 2 bytes.
Quoting Oswaldwhy there is 2 ldx for the first byte and 1 for the 2nd ? The second incoming encoded GCR byte (11222223) which was used to complete decoding the first byte (00001111) is still in the X register when partially decoding it to "22223..." via "lda decode23,x". |
| | ChristopherJam
Registered: Aug 2004
Posts: 1370 |
Ooh, that's rather clever. I wouldn't have expected interpreting GCR bits as digits in a positional number system to work. It will indeed be interesting to see if this is useful in practice. |
| | Krill
Registered: Apr 2002
Posts: 2825 |
Quoting ChristopherJamOoh, that's rather clever. I wouldn't have expected interpreting GCR bits as digits in a positional number system to work. It will indeed be interesting to see if this is useful in practice. I see at least some application for single-revolution loading of standard format files with a parallel cable.
Maybe also for double-revolution loading over plain serial. =) |
| | ΛΛdZ
Registered: Jul 2005
Posts: 153 |
Hi Krill,
You state:
"This is problematic with the 2 KB of RAM of a 1541."
What about for 1570 and 1571 drives ? |
| | Krill
Registered: Apr 2002
Posts: 2825 |
Quoting ΛΛdZWhat about for 1570 and 1571 drives ? Ah, sorry. Correction:
This is problematic with the 2 KB of RAM of a 1541, 1570 or 1571. =]
But then, 1570 and 1571 can run at 2 MHz and have some okay-ish GCR decoding tables in ROM. |
... 6 posts hidden. Click here to view all posts....
|
| Previous - 1 | 2 - Next | |
