Fixed Bit Length Encoding - Falmouth-Games-Academy/comp310-wiki GitHub Wiki

In computing, a byte is 8 bits and can have a value from 0-255. However, there are many occasions when you will not need to utilise all 8 bits. For example, if your data only requires the values 0-15 then you will only need to use 4 of the 8 available bits. However, if Fixed Bit Length Encoding is not used then all 8 bits will still be assigned to your data. On more modern machines this poses less of a problem as there are much larger amounts of memory available to developers, however, on older machines, there is often very limited memory available for use. This means developers must take more care to only use as much memory as is needed. Fixed Bit Length Encoding will compress your data by packing it into the minimum number of bits needed to represent all possible values for your data thus meaning there is far less wasted memory [1].

For example, if we have the values 0-15:

00000000, 00000001, 00000010, 00000011, 00000100, 00000101, 00000110, 00000111, 00001000, 00001001, 00001010, 00001011, 00001100, 00001101, 00001110, 00001111

As you can see the first 4 values are 0 for all the data. This means we can effectively 'chop-off' the first 4 values so 00001111 will become 1111 and 00000001 will become 0001. This is known as 4-bit encoding and it allows us to nicely squash two bytes together as only 4 bits are needed for each piece of data.

4 Bit Encoding Example Placeholder

left nibble
    lda data, y                read a byte from our data stream
    lsr
    lsr
    lsr
    lsr                        right shift four times to get the left nibble
    jsr do_stuff                

right nibble                                                                                                            
    lda data, y                read a byte from our data stream
    and #$0F                   ANDing with #$0F zeros out the left side, 
    jsr do_stuff

Source 1(https://wiki.nesdev.com/w/index.php/Fixed_Bit_Length_Encoding)

Other Bit Length Encoding (5-bit)

Other bit length encoding methods are possible such as 5-bit encoding. However, they are significantly more complex as you often find data will carry over from one byte to another. This means that you will have to read each byte a few bits at a time and keep track of where this crossover will occur.

Sources

[1] https://wiki.nesdev.com/w/index.php/Fixed_Bit_Length_Encoding