[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!
that’s the kind of OCD that could get us Windows 10 on a floppy disc. :)
FORTH OS in embedded space.
The NSA are working hard at windows 11
I doubt the win10 drivers for floppy drives fit on a CD-ROM thene days.
Challenge issued: make W10 driver for floppy drive as small as 1k.
Barney Stinson, is that you?
https://github.com/Microsoft/Windows-driver-samples/blob/master/storage/sfloppy/src/floppy.c
93k source of the Super floppy driver alone. Not including the lower level bus drivers and frameworks it depends on.
Mind you that’s the official, “proper”, windows driver design. The antithesis of the 1k challenge.
At the time this has been done, it is probably even harder to find a working floppy disc and drive. :-)
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
I predict a nice career in politics for that disk.
Harder part will be finding an MB with IDE and a floppy connection.
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.
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.
Try ASCII for 127 bytes Character set
https://en.wikipedia.org/wiki/ASCII
A 4×8 pixel 127-character set uses 508 bytes to define the patterns.
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.
ASCII only represents characters in a set… ASCII is not a bitmap. This handles the actual bitmap.
There’s a big difference
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.
This is pure poetry.
Agreed.
Very impressive bit of coding there.
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.
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.
Have you got a demo anywhere? Javascript perhaps?
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 :(
Though this is just beautiful.
This is exactly what I would enjoy seeing in the 1kB (1KiB in SI) challenge.
Why didn’t he use this font?
http://fontstruct.com/fontstructions/show/716744/3_by_5_pixel_font
It would be about the same size, and he wouldn’t had to have come up with that crazy compression scheme.
Can you tell us how much space this would use?
If you can tell us this, then that is why.
It will take 15 bits. That is two bytes per character, no vector table and probably a smaller decoder.
Thats what I used for OKOS, even stuffed descender support in the 16th bit (if you can spare the 10 bytes to support it). I used 40 printable characters in 80 bytes. Another 50 bytes to decode and send over i2c. 3×5 is readable, but not as nice as a 4×8.
https://hackaday.io/project/18774-one-kilobyte-operating-system-okos
Excellent idea, excellent execution.
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.
Today there is horrible bloatware everywhere, it’s really nice to see somebody talking about 180B (bytes!) left and trying to optimize his code really well!