G2's Blog

In the previous post I stated that the packet size was 28 bytes. This is perfectly reasonable, and small enough for almost any situation... but what if we wanted to go even smaller? To start, I'll use an example of storing the time in the packet in as compact a way as possible.

Basic Implementation

The easiest and smallest way to store time normally (with a precision of microseconds) would be to store it in a struct similar to the following...

struct Time {
    hours: u8,
    minutes: u8,
    seconds: u8,
    microsec: u32,
}

...where the smallest regular unit capable of storing all the data for each field is used. This is both easy and fast. But if we look critically, we can see that a lot of space is being wasted! The hours field only needs 24 values, yet it's being stored in a field which can hold 256 different numbers (2^8). The same is the case for the rest of the values, minutes and seconds only need 60 values, and microseconds only needs 1 million values, but is being stored in a field which can store over 4 billion values[!] (2^32). This brings the total number of bits for the timestamp to 56 bits, or 7 bytes. One thing which jumped out at me to decrease the size was to store the number of hours, minutes, and seconds as just seconds in a u16, but unfortunately this doesn't work, as there are 86,400 seconds in one day, and an unsigned 16-bit integer can store 65,536 values. We need another solution.

Sub-byte Sizes

If we don't need 256 values for the hours, minutes, and seconds, why don't we decrease the number of bytes each field requires? Well, that can work! For example, in order to store 24 hours, we can use 5 bits (2^5), which can store 32 different values. For hours and minutes, 6 bits can work (2^6), which stores 64 different values. Finally, microseconds only require 1 million different values, which can fit nicely in 20 bits (2^20), which can store a little over 1 million values. With that, we come to a new total of 5 + 6 + 6 + 20 bits, or 37 bits. That saves 19 bits compared to the full-byte size! The problem now becomes how to store these values in a size less than one byte.

Bit Packing

In order to make use of the smaller bit size values, it is possible to "pack" the bits into a set of bytes, using the bytes simply as a carrier for the bits. For example, in order to store the time in u8 values, the bits would be arranged like this:

[ Hour ] [Minute] [Second] [           Microsecond           ]
00000000 00000000 00000000 00000000 00000000 00000000 00000000

If we then reduce the number of bits to the new smaller sizes and then arrange them into the bytes again, it would look like this:

H = Hour
M = Minute
S = Second
U = Microsecond

HHHHHMMM MMMSSSSS SUUUUUUU UUUUUUUU UUUUU
00000000 00000000 00000000 00000000 00000000

Amazing use of space in comparison to the previous method!

Application

In order to further reduce the size of the telemetry packets, I applied this same method to all the other fields, removing bits where precision was not needed. I actually ended up increasing the precision of some of the fields, while decreasing the overall size of the packet from 28 to 22 bytes!

Usually, in order to get the bits into the bytes in this way, you can do it with bit shifting and bitwise operations to move the bits where they're needed, however there is a nice Rust crate which can help out here called packed_struct. It allows you to specify sizes of individual parts of the struct, and then it will automatically pack and unpack the bits for you.