Close

640x480 RLE Wrencher (4409 Bytes)

A project log for PIC Graphics Demo

Generate 640x480 64-color VGA graphics with an 8-bit PIC and an SRAM framebuffer

Ted YapoTed Yapo 01/06/2017 at 23:5019 Comments

I 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

Yann Guidon / YGDES wrote 01/07/2017 at 03:57 point

Damnit, I just had an idea... again :-(

  Are you sure? yes | no

Ted Yapo wrote 01/07/2017 at 05:20 point

I hate when that happens.  It almost always costs time and money that I don't really have :-)

  Are you sure? yes | no

Yann Guidon / YGDES wrote 01/07/2017 at 06:06 point

the story of my life...

  Are you sure? yes | no

Yann Guidon / YGDES wrote 01/07/2017 at 02:36 point

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

Ted Yapo wrote 01/07/2017 at 02:45 point

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

Ted Yapo wrote 01/07/2017 at 02:47 point

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

Yann Guidon / YGDES wrote 01/07/2017 at 02:07 point

What was your original picture/source ? maybe others can work on it ? Or make a "compress this image" challenge ?

  Are you sure? yes | no

Ted Yapo wrote 01/07/2017 at 02:45 point

Posted above.  Read the disclaimers :-)

  Are you sure? yes | no

Yann Guidon / YGDES wrote 01/07/2017 at 02:55 point

thanks !

  Are you sure? yes | no

Yann Guidon / YGDES wrote 01/07/2017 at 01:24 point

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

Ted Yapo wrote 01/07/2017 at 02:24 point

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

Yann Guidon / YGDES wrote 01/07/2017 at 01:22 point

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

Ted Yapo wrote 01/07/2017 at 02:30 point

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

Yann Guidon / YGDES wrote 01/07/2017 at 02:40 point

  Are you sure? yes | no

Ted Yapo wrote 01/07/2017 at 02:52 point

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

Yann Guidon / YGDES wrote 01/07/2017 at 03:58 point

Random Access Memory is RAM...

RAM is life !

  Are you sure? yes | no

esot.eric wrote 01/07/2017 at 07:22 point

Serial-Access-Memory?

  Are you sure? yes | no

Ted Yapo wrote 01/07/2017 at 14:24 point

@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

esot.eric wrote 01/08/2017 at 00:01 point

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