Character Generation in 144 Bytes

[Jaromir Sukuba]  has an awesome BrainF*ck interpreter project going. He’s handling the entire language in less than 1 kB of code. Sounds like a great entry in the 1 kB Challenge. The only problem is the user interface. The original design used a 4 line character based LCD. The HD44780 controller in these LCDs have their own character table ROM, which takes up more than 1 kB of space alone.

[Jaromir] could have submitted the BrainF*ck interpreter without the LCD, and probably would have done well in the contest. That wasn’t quite enough for him though. He knew he could get character based output going within the rules of the contest. The solution was a bit of creative compression.

Rather than a pixel-by-pixel representation of the characters, [Jaromir] created a palette of 16 single byte vectors of commonly used patterns. Characters are created by combining these vectors. Each character is 4 x 8 pixels, so 4 vectors are used per character. The hard part was picking commonly used bit patterns for the vectors.

The first iteration was quite promising – the text was generally readable, but a few characters were pretty bad. [Jaromir] kept at it, reducing and optimizing his vector pallet twice more. The final design is pretty darn good. Each character uses 16 bits of storage (four 4-bit vector lookup values). The vector pallet itself uses 16 bytes. That means 64 characters only eat up 144 Bytes of flash.
This is exactly the kind of hack we were hoping to see in the 1 kB challenge. A bit of creative thinking finds a way around a seemingly impossible barrier. The best part of all is that [Jaromir] has documented his work, so now anyone can use it in the 1 kB challenge and beyond.

If you have a cool project in mind, there is still plenty of time to enter the 1 kB Challenge! Deadline is January 5, so check it out and fire up your assemblers!