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.

bf-cs-3Rather 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.

1kb-thumb

 

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!

 

34 thoughts on “Character Generation in 144 Bytes

      1. It took me 3 months of searching and asking on Facebook and Craigslist before a friend found a Dimension 3000 in her attic that still had a working floppy drive. After all that, the disk I was looking to read was corrupt

  1. Nice solution!

    He should use bit 0 of each byte pattern as an invert mask – giving him 32 possible 7-bit patterns instead of 16 8-bit patterns where bit 0 is always clear. But that might make the text rendering code a lot larger.

    1. Err, that doesn’t make sense at all thinking about it… I meant for the invert bit to be in the char definitions, but that would be slightly less flexible even as that’s a whole bit out of 4 which would reduce the patterns to 8.

      1. Only 94 are non-whitespace printables. So that’s 376 bytes. Some of those could probably be trimmed further as illegible at that size. Given he’s only got 64 we’ll say 30 so 256 bytes.

    1. The image in the page you link to, containing the visual representation of those ascii characters, is 2.5 million bytes.
      It’s over 27 thousand bytes using PNG compression.

      You sir have far far exceeded the 1024 byte limit of data storage in your solution.

  2. Can you arrange those stings of pixel patterns by size and then assume that the bit length diminishes as a given rate. i.e. Can you shuffle the data so that the 1’s are mostly toward the bottom left corner of the array? See what I mean? Perhaps you can but the code to handle it would be larger than the data saved. I don’t know.

    1. Thanks for suggestion.
      Yep, the vectors usage frequency is very different,like 50 for the most commonly used and 3 for least used. The variable bit length would make sense here, in theory. Though, given the fact I have approximately 180B of code free, the decoder will probably take more space than the encoding can save. In my case, decoder is just one data pointer and nibble shifting from fixed length patterns.
      This is very small data set and every byte/instruction counts, if it would be one order of magnitude bigger, I’d definitely go this way, though it could be interesting experiment anyway.

  3. Reminds me of having to write an algorithm to create the draw calls for the VNC FPS on the ESP. Having to write a program that figured out how to use squares to represent text. some of it compressed very well, others were bigger than if I just represented the raw bits :(

  4. The 3×5 font mentioned above is little hard to read, so another solution is to reduce the font to 4×6 or 4×5, that reduces the number of combination needed in the vector table and it may be easier to make the characters more readable.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s