Ted YapoI had to do it.
The logo plus decoding code takes up 2519 14-bit instructions (4409 bytes). I used a simple RLE compression and stored the compressed data in a header file. I only compressed the left half image, then decompressed the runs in reverse for the right half. The whole code is uploaded here, but the decompression part looks like:
void GenerateFrame()
{
GenerateLine( VSYNC , RGB(0, 0, 0), 33); // V back porch
const uint8_t *data_ptr = rle_wrencher;
uint16_t row = 480;
do {
write_SRAM_bytes( VSYNC | HSYNC | 0 , 16); // H front porch
write_SRAM_bytes( VSYNC | HSYNC&0 | 0 , 96); // H sync pulse
write_SRAM_bytes( VSYNC | HSYNC | 0 , 48); // H back porch
const uint8_t *row_ptr = data_ptr;
// left half image
uint8_t color = 0;
uint8_t num_runs = *data_ptr++;
if (num_runs){
do {
uint8_t run_length = *data_ptr++;
write_SRAM_bytes( VSYNC | HSYNC | color, run_length);
color ^= 0x3f;
} while (--num_runs);
} else {
write_SRAM_bytes( VSYNC | HSYNC | 0, 160);
write_SRAM_bytes( VSYNC | HSYNC | 0, 160);
}
// right half image (runs processed in reverse)
color ^= 0x3f;
num_runs = *row_ptr;
if (num_runs){
do {
uint8_t run_length = *--data_ptr;
write_SRAM_bytes( VSYNC | HSYNC | color, run_length);
color ^= 0x3f;
} while (--num_runs);
} else {
write_SRAM_bytes( VSYNC | HSYNC | 0, 160);
write_SRAM_bytes( VSYNC | HSYNC | 0, 160);
}
data_ptr += *row_ptr;
} while (--row);
GenerateLine( VSYNC , RGB(0, 0, 0), 10); // V front porch
GenerateLine( VSYNC&0 , RGB(0, 0, 0), 2); // V sync pulse
write_SRAM_bytes( VSYNC | HSYNC | 0, 2); // end of vsync; resets counter
}I really wanted to fit this into 1kB, but ran out of time.Quadtrees?
I also experimented with quadtree compression, which should take better advantage of the solid 2D areas (not just 1D runs). The best strategy I found was to compress the top and bottom halves as 256x256 blocks (bottom visualized here):
Again, symmetry would be used to create the right side. I got the data down to 1047 bytes this way, but didn't think I could add the decompression code *and* find a way to make it all fit in 1kB, so I abandoned the effort.
I think you probably could get this image into 1kB, though, if you really worked at it.
Now, back to other projects...
For those that want to try compressing this 640x480 rendering of the wrencher, here is the one I used as a png. I do not know anything about the intellectual property status of this image, so, you know...don't sue me or anything. I make no representations whatsoever about rights to use this logo or this specific rendering of it. I hear it's a touchy subject - but then again, there are a number of instances of people using the logo, then not being sued for trademark infringement, so that sounds like failure-to-enforce. But failing to enforce copyright doesn't weaken the copyright, so ... whatever. Then again, this is their site, so if they have an issue with this, they should send themselves a takedown notice.
Discussions
Become a Hackaday.io Member
Create an account to leave a comment. Already have an account? Log In.
Damnit, I just had an idea... again :-(
Are you sure? yes | no
I hate when that happens. It almost always costs time and money that I don't really have :-)
Are you sure? yes | no
the story of my life...
Are you sure? yes | no
Remark about your RLE-encoded header : you could have saved the last run of 0s :-)
Similarly, the first run of 0s as well.
Are you sure? yes | no
Yep, I was going to encode those separately, but once I realized it wasn't going to make it into the 1kB contest, I got even more lazy...
Are you sure? yes | no
You can also hard-code the black margins around the image and only RLE the stuff inside the bounding box of the figure to save some more bits.
Are you sure? yes | no
What was your original picture/source ? maybe others can work on it ? Or make a "compress this image" challenge ?
Are you sure? yes | no
Posted above. Read the disclaimers :-)
Are you sure? yes | no
thanks !
Are you sure? yes | no
You can also "compile" the picture in advance, collect the histogram of the RLE and use a precompiled dictionary, using the Huffman algo. Don't bother too much about the color : each new run lenght is for the opposite color. You can optimise a bit with 2 dictionaries, one for each color...
Are you sure? yes | no
Yes, in the above code I just invert the color (with an XOR of the rgb bits) after each run.
I computed the entropy of the run lengths; it's about 6.7 bits per run length, so with Huffman coding you could save about 20% of the space for some extra code complexity - but then you have to store the Huffman tree/table, too. I didn't look at alternating tables, but again, you have to store the tree.
Are you sure? yes | no
Did you look at https://hackaday.io/project/18688-1kb-6502-image-compression/log/50314-first-crack-lzw/discussion-71813 ?
His LZW might be useful :-)
And if you are into quadtrees, my 3R Algorithm might be useful, though you first need to apply an edge detection algorithm (XOR the north, west and north-west neighbours)
Are you sure? yes | no
Yes, it's an interesting discussion. I bet if you really thought about this image, you could come up with code to generate it in very few instructions - like rendering it with primitives and just storing a few bitmaps to clean it up. Not a general-purpose image compression algorithm, but specific to this image: my guess is that the Kolmogorov complexity is very low.
I did my Master's thesis on a form of quadtree compression many years ago - it was fun to think about it again :-)
Are you sure? yes | no
Quadtrees map to my #Recursive Range Reduction (3R) HW&SW CODEC ;-)
Are you sure? yes | no
Oh the other thing about this is that writing to the framebuffer must be in-order (or, you have to reset the address counter and count up again to the next pixel). This puts limits on which decompression algorithms can work efficiently. For the quadtree, I would have to do a quadtree search on each pixel to find the color - you can't just traverse the tree and render the leaf blocks as you find them, which would require random access to the SRAM.
Are you sure? yes | no
Random Access Memory is RAM...
RAM is life !
Are you sure? yes | no
Serial-Access-Memory?
Are you sure? yes | no
@esot.eric According to wikipedia, one of the first framebuffers (1972) used shift registers for a 640x480 display with 8 bit color depth (sounds familiar, right?)
https://en.wikipedia.org/wiki/Framebuffer
So, what if I use my "new discovery," every maker's favorite part, the 74HC595? I'll only need 420,000 of them. I should probably design a PCB instead of wiring them by hand.
Are you sure? yes | no
Hah! A purely-shift-registered frame-buffer!
I think it's fair, these days, to use an SRAM *as* a big-ol'-shift-register, rather than 420,000 chips ;)
Though, it's been somewhat interesting to me that LCD displays function via shift-registers for every row and every column; I thought 640+480 shift-registers is a lot!
Are you sure? yes | no