Saving ~2kb by Encoding Into 12 bits

A project log for Nyan Cat Badge Demo (2018 Supercon)

An adaptation of YouTube star Nyan Cat for the 2018 Hackaday Superconference Badge

RogerRoger 11/09/2018 at 20:210 Comments

I built my Nyan Cat project on the Hackaday Belgrade 2018 badge. Now there’s a slim opening for it to be part of the Hackaday Superconference 2018 badge. The key is to get Nyan Cat skinny enough to fit through that door. Most of the 512 kilobytes of program storage on the badge’s PIC32MX370F512H chip have already been spoken for, leaving only about 16 kilobytes available. I set out to take up less than half of that space. I’m now just over 10 kilobytes, I need to trim another 2+ kilobytes.

The first task is to port the code from a fork of the Belgrade repo over to a fork of the Supercon repo. During this move, Nyan Cat code also migrated from being a customized user_program.c to its own nyancat.c source file in order to leave the default user program alone for badge hackers to play with. First I verified it still worked in the new repo – overweight and all – then I got to work trimming more data.

The key insight for more savings is realizing that we now store a quarter-scale image of 80×60 pixels and scale up at rendering time. Since they are encoded (and decoded) one scanline at a time, this means no single run length of pixels can be longer than 80. Previously, 12 bits were used to store length because a 320×240 image may have a run of 320 – longer than the maximum 8-bit value of 256. Now I only need 8 bits for run length. (The color palette always had only 14 colors, so it still needed only 4 bits.)

This trims every run in the image, color index + run length, from 16 bits down to 12. This did indeed trim data down to a little over 8.5 kilobytes. But code readability took a hit as a result: the smallest convenient unit in C is in multiple of 8 bits, so working with 12 bit values involve a lot of bit manipulation to pack and unpack that data.

(Cross-posted to