Author Topic: LZD Image Compression/Decompression  (Read 4196 times)

0 Members and 1 Guest are viewing this topic.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
LZD Image Compression/Decompression
« on: June 27, 2018, 08:41:18 pm »
Hey all, I have been playing with compression. I made a Python program that compresses data, such as a TI Image, as well as a calculator program that can decompress such data to the graph screen.

While the Python program is general-purpose, the Z80 program assumes that the input is a compressed image, so you can mess things up! The neat thing is that in my example, the calc program (LZD) and the compressed data, along with their file headers, all came out to less than the size of the original image!

Offline Eeems

  • Mr. Dictator
  • Administrator
  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 6266
  • Rating: +318/-36
  • little oof
    • View Profile
    • Eeems
Re: LZD Image Compression/Decompression
« Reply #1 on: June 27, 2018, 09:17:42 pm »
Have you done any performance testing around the length of time it takes to decompress?
How much memory is used to decompress?
/e

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: LZD Image Compression/Decompression
« Reply #2 on: June 28, 2018, 09:39:04 am »
Decompression uses 4 bytes of additional RAM. I haven't analyzed average case performance, but best and worst case performance were pretty easy. Note that using LDIR to copy 768 bytes, along with an RET is 16138cc

Best case (speed): Uncompressible data => 16477cc which is 2.1% slower
Worst case: A run of 4 bytes, followed by 153 of [match of 4 bytes, run of 1 byte] =>93336cc which takes about 5.78 times as long as an LDIR.

If I had to guess, average case might be somewhere closer to taking 4 times as long as a direct copy.

Edit: I analysed the example image and that took 46482cc for decompression (2.88 times as long as an LDIR) Attached is a copy of the compression program that returns how long it should take in clock cycles to decompress.

Offline Eeems

  • Mr. Dictator
  • Administrator
  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 6266
  • Rating: +318/-36
  • little oof
    • View Profile
    • Eeems
Re: LZD Image Compression/Decompression
« Reply #3 on: June 29, 2018, 11:32:34 am »
It still seems performant enough that you could use it to compress data in your program and decompress them into a buffer at runtime. Assuming you need the space that is.
/e

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: LZD Image Compression/Decompression
« Reply #4 on: July 03, 2018, 10:11:24 pm »
Oh, absolutely. And for programs that have hard-coded splash screens, this can reduce size of the overall program (since the decompression routine is so light-weight, the gains in compression are not exceeded by the size of the decompression code).