Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
You are not logged in 
CSDb User Forums


Forums > C64 Coding > Bitwise GCR decoding
2021-01-05 10:34
Krill

Registered: Apr 2002
Posts: 1741
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] 4
The 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
2021-01-05 10:54
Oswald

Registered: Apr 2002
Posts: 4666
I dont understand, but why not huffmann gcr then :D that tree just looks like it.
2021-01-05 11:24
Krill

Registered: Apr 2002
Posts: 1741
Quoting Oswald
why not huffmann gcr
All 16 encoded symbols have the same size and probability.
2021-01-05 11:29
Oswald

Registered: Apr 2002
Posts: 4666
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?
2021-01-05 11:35
Krill

Registered: Apr 2002
Posts: 1741
Quoting Oswald
why does the add operation work
See OP.

Quoting Oswald
why 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 Oswald
why doesnt it matter if you add a nibble to a byte that's not even present in it?
I don't understand the question.
2021-01-05 14:30
Oswald

Registered: Apr 2002
Posts: 4666
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 ?
2021-01-05 15:06
Krill

Registered: Apr 2002
Posts: 1741
Quoting Oswald
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?
Nibbles 2 and 3 are decoded to the next byte in just the following snippet you have casually omitted:
Quoting Krill
lda decode23,x; 22223... - nibble 2 complete, nibble 3 partial
ldx $1c01 ; 33334444
adc decode3,x ; 22223333 - byte 1 complete
Quoting Oswald
if 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 Oswald
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 ?
$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 Oswald
why 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".
2021-01-05 16:38
ChristopherJam

Registered: Aug 2004
Posts: 1122
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.
2021-01-05 16:46
Krill

Registered: Apr 2002
Posts: 1741
Quoting ChristopherJam
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.
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. =)
2021-01-05 19:14
ΛΛdZ

Registered: Jul 2005
Posts: 148
Hi Krill,

You state:
"This is problematic with the 2 KB of RAM of a 1541."

What about for 1570 and 1571 drives ?
2021-01-05 19:18
Krill

Registered: Apr 2002
Posts: 1741
Quoting ΛΛdZ
What 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.
2021-01-06 10:46
Oswald

Registered: Apr 2002
Posts: 4666
only now do I realise you have a different decode table for each case of the GCR nibble position in $1c01, I still fail to understand how it all works. guess the key is your "huffman" drawing and the positional nr system, maybe you could make 1-2 examples with it that helps understanding whats going on?
2021-01-06 13:31
Krill

Registered: Apr 2002
Posts: 1741
Quoting Oswald
guess the key is your "huffman" drawing and the positional nr system, maybe you could make 1-2 examples with it that helps understanding whats going on?
The binary tree is just an alternative representation of mapping #5, picked as an example to show the 16* mappings' positional number system properties.

But let's walk the tree with an example GCR number, say %01010 = $0a. When going along the tree from left to right, you would traverse the edges from node to node like so: /\/\/ (01010). On the travelled edges, you see +<number>. Start with 0, then add the numbers on the edges you travel along: (0 +) 6 + 4 + 3 + 0 + 1 = 14.

Repeat with the other 15 possible GCR values, and you'll get the 15 other values from 0 to 15, too.

You'll notice that for every GCR bit, you'll add either of two values for that position. This boils down to this representation:
  GCR  4  3  2  1  0
    0: 6, 0, 3, 2, 1
    1: 0, 4, 0, 0, 0
* There are 16! = ~2.092278989 * 10^13 bijective mappings from 16 unique values to 16 unique values, but the vast majority of them do not have the properties exploited here.
2021-01-06 19:03
Bitbreaker

Registered: Oct 2002
Posts: 448
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.
2021-01-06 20:17
Krill

Registered: Apr 2002
Posts: 1741
Quoting Bitbreaker
his 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 Bitbreaker
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.
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 above
Then 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 Bitbreaker
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?
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 Bitbreaker
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.
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.
2021-01-11 08:29
Bitbreaker

Registered: Oct 2002
Posts: 448
Quoting Krill
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.


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.
2021-01-11 13:23
Krill

Registered: Apr 2002
Posts: 1741
Quoting Bitbreaker
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
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. =)
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
da Blondie/Resource
Karmic/HVSC
The MeatBall
mkarcz
nc513
Guests online: 72
Top Demos
1 Christmas Megademo  (9.7)
2 Uncensored  (9.6)
3 Edge of Disgrace  (9.6)
4 Unboxed  (9.6)
5 Coma Light 13  (9.6)
6 Memento Mori  (9.6)
7 Lunatico  (9.6)
8 Comaland 100%  (9.6)
9 Unboxed [6581 edition]  (9.5)
10 The Shores of Reflec..  (9.5)
Top onefile Demos
1 Copper Booze  (9.8)
2 To Norah  (9.8)
3 Lovecats  (9.6)
4 Berniemania  (9.6)
5 The Sprite Demo  (9.6)
6 Elite Code Mechanics  (9.6)
7 Square Booze  (9.5)
8 Daah, Those Acid Pil..  (9.5)
9 Dawnfall V1.1  (9.5)
10 Quadrants  (9.5)
Top Groups
1 Booze Design  (9.4)
2 Censor Design  (9.4)
3 Fossil  (9.4)
4 Oxyron  (9.3)
5 PriorArt  (9.3)
Top NTSC-Fixers
1 Pudwerx  (10)
2 Horizon  (9.9)
3 Stormbringer  (9.7)
4 Fungus  (9.5)
5 Grim Reaper  (9.3)

Home - Disclaimer
Copyright © No Name 2001-2021
Page generated in: 0.062 sec.