| | Krill
Registered: Apr 2002
Posts: 3065 |
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 |
|
... 12 posts hidden. Click here to view all posts....
|
| | Bitbreaker
Registered: Oct 2002
Posts: 510 |
his is really cool and funny to see how few mappings fit in the end, but they do. A part of this adding can be done for the 566666xx part on teh original gcr-mapping, but with those mappings it can be done across all bits.
The 16! scared me first when i tried about those mappings when you gave me the hint that i don't need to stick to the original mapping. Sorting helped to find one of those mappings by hand after some tries and fiddling. Thing is that the checksum of a sector does not represent the checksum build from the data in a new mapping, as far as i see. What needs to be done to have a checksum that can be compared?
The costs for the tables can be reduced when masking (clipping of bits of the next byte to be decoded) or shifting is applied at some points. This of course costs extra cycles. |
| | Krill
Registered: Apr 2002
Posts: 3065 |
Quoting Bitbreakerhis is really cool and funny to see how few mappings fit in the end, but they do. For quite a long time i suspected only my one hand-crafted mapping works, until i came up with a tool that would find the others with a lot less than fac(16) tries in an exhaustive search on the day i started this thread. =D (I'm still not 100% certain that those 16 mappings are all of them.)
Quoting BitbreakerA part of this adding can be done for the 566666xx part on teh original gcr-mapping, but with those mappings it can be done across all bits. Indeed, i found out that partial GCR decoding works on the 4:1 partition of the original mapping, when working on Krill's Loader, Repository Version 164 decode4: lda $00 ; 112 117 122 127 ; ----4444 -> $x0, partial %11: cycle 118 is -11 in [104..129], %10: cycle 123 is +11 in [112..139]
adc DECODETAB5,x ; 116 121 126 131 ; 455555-- -> $xx, clears v - %01: cycle 128 is +8 in [120..149], %00: cycle 133 is +5 in [128..159]
pha ; 119 124 129 134 ; ; checksummed with eor STACK + 3,x aboveThen i played around with the concept a bit more to generalise it and find more mappings which support partial decoding on all partitions and down to bitwise.
Quoting BitbreakerThing is that the checksum of a sector does not represent the checksum build from the data in a new mapping, as far as i see. What needs to be done to have a checksum that can be compared? Apart from the obvious sacrifice of one payload byte for a custom checksum, there might be a mapping whose decoded values can be transformed to the original Commodore GCR decoded values via EOR #const. There may be some viable mappings when restricting to certain partitions, which is hinted at by the fact that the 4:1 partition works with the original mapping, but other partitions do not.
Quoting BitbreakerThe costs for the tables can be reduced when masking (clipping of bits of the next byte to be decoded) or shifting is applied at some points. This of course costs extra cycles. With shifting and masking, we're quickly losing the benefits of this approach. But then, this is just another tool in the toolbox to squeeze more stuff into a loader's cycle-constrained low-level disk-reading loop. =)
There might be ways to combine different mappings for different nibbles in less table space, however. |
| | Bitbreaker
Registered: Oct 2002
Posts: 510 |
Quoting KrillApart from the obvious sacrifice of one payload byte for a custom checksum, there might be a mapping whose decoded values can be transformed to the original Commodore GCR decoded values via EOR #const. There may be some viable mappings when restricting to certain partitions, which is hinted at by the fact that the 4:1 partition works with the original mapping, but other partitions do not.
First i will do is a tool that searches for mappings that meet my needs i guess, thankfully i have access to quite some computing power :-D Certain partitions that meet the criterias would suffice for my case. Sacrificing payload for checksum would not be an option for me, as i spoil my sectorsize of $100 by that :-( I don't want to go beyond the yet resident code size, when having smaller sectors. |
| | Krill
Registered: Apr 2002
Posts: 3065 |
Quoting BitbreakerFirst i will do is a tool that searches for mappings that meet my needs i guess, thankfully i have access to quite some computing power :-D Pretty sure you can find all mappings for all four partitions with modest home-computing power.
Keep in mind that a viable partition mapping will form a positional number system as well, but with just 2 digits (instead of 5): one digit on the left-hand side (GCR byte) and the other on the right-hand side (GCR byte). A digit can then have more than just 2 possible values, of course. =) |
| | Quiss
Registered: Nov 2016
Posts: 52 |
Quote:
there might be a mapping whose decoded values can be transformed to the original Commodore GCR decoded values via EOR #const
I wasn't able to find such a mapping for the 1:4 or the 2:3 partition, with only EOR.
However, it does exist if you also reshuffle the bits of the nibble.
In fact, there are even four GCR mappings, listed below, that
(a) are separable for any partition
(b) allow later deriving the sector checksum through EOR #const and bit reshuffle in the nibble.
[23, 19, 22, 18, 15, 11, 14, 10, 21, 27, 30, 26, 29, 25, 13, 9] # xor: $07, bit order: 1203
[23, 22, 19, 18, 21, 30, 27, 26, 15, 14, 11, 10, 29, 13, 25, 9] # xor: $0b, bit order: 0312
[23, 19, 22, 18, 21, 27, 30, 26, 15, 11, 14, 10, 29, 25, 13, 9] # xor: $0b, bit order: 1302
[23, 22, 19, 18, 15, 14, 11, 10, 21, 30, 27, 26, 29, 13, 25, 9] # xor: $07, bit order: 0213
This is unexpected and delightful. It needs verification, and possibly a proof-of-concept implementation. |
| | Quiss
Registered: Nov 2016
Posts: 52 |
Those four solutions are wrong though, unfortunately. (I knew it sounded too good to be true)
I think I found working ones, though. Will double-check and then post here. |
| | Krill
Registered: Apr 2002
Posts: 3065 |
Quoting QuissThose four solutions are wrong though, unfortunately. (I knew it sounded too good to be true)
I think I found working ones, though. Will double-check and then post here. Ah, i see. =)
Wanted to post here, but was wondering whether i understood things correctly, because i couldn't get the first mapping to work without contradictions.
Good luck! |
| | Krill
Registered: Apr 2002
Posts: 3065 |
Quoting Quiss(a) are separable for any partition Would this be a less strong restriction than allowing for bitwise decoding in any order of input bits?
In other words, would the set with the "separable for any partition" constraint contain the 16 mappings of the OP... AND contain more than 16 mappings in total?
Because separable for any partition is all we need, really, to boil it down to two lookups and an add.
More mappings to choose from would be quite something in (my, at least) quest for the somewhat holy grail of requiring only those two lookups plus add with no more than say 2 pages worth of tables. =) |
| | Quiss
Registered: Nov 2016
Posts: 52 |
Quote:
I think I found working ones, though. Will double-check and then post here.
The second set was wrong as well. Which is sad.
But at least the universe makes sense again now. There are 20922789888000 ways to order the GCR values. Only 16 of which can be decoded bit-by-bit, see OP.
It would have very improbable that the (more or less) random choice of the default GCR order and its 5160960 checksum-compatible reshufflings would have happened to contain one of those 16.
Quote:
Would this be a less strong restriction than allowing for bitwise decoding in any order of input bits?
It's the same restriction, actually!
Quote:
More mappings to choose from would be quite something in (my, at least) quest for the somewhat holy grail of requiring only those two lookups plus add with no more than say 2 pages worth of tables. =)
You can give each partition (i.e., each nibble) its own mapping?
Only the 4:1 partition can be made "checksum-compatible", though. |
| | Krill
Registered: Apr 2002
Posts: 3065 |
Quoting QuissIt's the same restriction, actually! That's what i thought, but then your post made me question that assumption. =)
Quoting QuissYou can give each partition (i.e., each nibble) its own mapping? Of course, but then more mappings would still come in handy! And yeah, all by-partition mappings are a few more than just the 16. But how to cleverly combine them to squeeze the lookup tables while still avoiding shifts and masking... =)
Quoting QuissOnly the 4:1 partition can be made "checksum-compatible", though. Oh well, the original checksum is really weak anyways. Wouldn't have any problems to sacrifice a payload byte for a stronger checksum, like i did with Transwarp.
But it would be cool still to be able to transform the original checksum. |
| Previous - 1 | 2 | 3 - Next | |
