Jump to content

Photo

DAN2 Lossless Data Compression

dan2 dan1 lz77 lzss compression z80 vram lossless pletter zx7

5 replies to this topic

#1 newcoleco OFFLINE  

newcoleco

    Stargunner

  • 1,328 posts
  • Always Tired
  • Location:Quebec

Posted Sun Jan 1, 2017 12:29 PM

DAN2 Lossless Compression

by Daniel Bienvenu aka NewColeco

 

A variant of DAN1 Compression Format

Based on LZ77 data compression, multiple offset sizes, unary code and elias gamma.

 

The project started after Alekmaul remarks and test data during December 2016.

 

 

Technical information

 

Three (3) differences compared to DAN1:

  1. The set of 4 different sizes to encode offset values becomes { 1, 4, 8, max } where max value is set by the user.
  2. The capability to store sequences of literal bytes is removed.
  3. The END OF DATA code is 17 bits long instead of 18.

The data format changed a little, making it incompatible with the original DAN1 format.

The first bits is an unary code to set the maximum of bits for offset values ( 0 = 10 bits, 10 = 11 bits, 110 = 12 bits, etc.)

The second byte is the first raw byte to copy as literal.

The rest of the data format follows similar to DAN1 specifications, except there is no sequences of literals (RLE) and also the END code is shorter by 1 bit.

 

 

Comparing DAN1 and DAN2

 

In term of speed, the compression and decompression are virtually the same speed as DAN1.

In term of size, the decompression routine is slightly bigger than DAN1, +7 bytes according to my z80 data compression library.

The expected improvement in compression ratio is only due to the possibility to adjust the maximum number of bits to encode offsets. 

 
 
Test samples from Exomizer
 
test1.bin (audio wave file) 
  • Original: 202762
  • ZX7: 223933
  • DAN1: 204208 (sequences of raw bytes help to not blow up in size)
  • DAN2 -m 16: 216898
  • Pletter: 221245
  • MegaLZ: 221136
  • Aplib aka APPACK: 219793
  • PUCrunch: N/A
test2.bin (text file filled only with the letter q)
  • Original: 196608
  • ZX7: 19
  • DAN1: 18
  • DAN2 -f -m 10: 18
  • Pletter:  N/A *error during compression*
  • MegaLZ: 2510
  • Aplib aka APPACK: 19
  • PUCrunch: N/A
test3.bin (formatted text file with fields such as name and date)
  • Original: 111261
  • ZX7: 52035
  • DAN1: 48103
  • DAN2 -m 16: 37048
  • Pletter: 44563
  • MegaLZ: 47052
  • Aplib aka APPACK: 37094
  • PUCrunch: N/A

 

Test samples from Alekmaul

 

Robee Blaster Title (Pattern, Color, and Name version)

  • Original: 2024, 2024 and 768. Total 4816
  • ZX7: 970, 790 and 383. Total 2143
  • DAN1: 965, 793 and 385. Total 2143
  • DAN2 m -10: 947, 784 and 385. Total 2116
  • Pletter: 957, 787 and 385. Total 2129
  • MegaLZ: 972, 806 and 384. Total 2162
  • Aplib aka APPACK: 986, 806 and 384. Total 2176
  • PUCrunch -d -c0 -s: 940, 772 and 373. Total 2085

Robee Blaster Title (Pattern and Color only version)

  • Original: 6144 and 6144. Total 12288
  • ZX7: 1257 and 793. Total 2049
  • DAN1: 1248 and 799. Total 2047
  • DAN2 -m 11: 1233 and 791. Total 2024
  • Pletter: 1259 and 795. Total 2054
  • MegaLZ: 1269 and 832. Total 2101
  • Aplib ka APPACK: 1273 and 825. Total 2098
  • PUCrunch -d -c0 -s: 1235 and 770. Total 2005

 

Test Sample Bitmap Graphic II

 

 

Download

 

DAN2 (EXE, SRC, ASM) version BETA-20170106 : Attached File  dan2-beta-20170106.zip   14.43KB   133 downloads

 

Change Log for version BETA-20170106:

  • increased up to 16 bits max offset size value
  • fixed bug with default max bits
  • fixed bug occurring with test2.bin sample

 

DAN2 (EXE, SRC, ASM) version BETA-20170101 : Attached File  dan2-beta-20170101.zip   14.39KB   155 downloads * BUG FOUND , PLEASE DOWNLOAD NEWER VERSION *


Edited by newcoleco, Fri Jan 6, 2017 10:59 PM.


#2 alekmaul OFFLINE  

alekmaul

    Chopper Commander

  • 207 posts
  • Location:Blois (France)

Posted Mon Jan 2, 2017 1:12 AM

Really nice Daniel, will try it soon :)



#3 PeteE OFFLINE  

PeteE

    Chopper Commander

  • 222 posts
  • Location:Beaverton, OR

Posted Wed Aug 30, 2017 4:33 PM

This is great!  Thank you for such a good tool with a simple encoding and great compression ratio.  I have written a decoder for the Texas Instruments TMS9900 CPU in assembly language that comes to about 220 bytes in size.



#4 Dr. D. OFFLINE  

Dr. D.

    Space Invader

  • 45 posts
  • Healer of Appliances
  • Location:Cleveland, Ohio

Posted Thu Aug 31, 2017 10:13 AM

Daniel is awesome, no doubt about it.

 

*Dr. D.*



#5 nanochess OFFLINE  

nanochess

    Processorus Polyglotus

  • 5,875 posts
  • Coding something good
  • Location:Mexico City

Posted Wed Mar 28, 2018 9:38 PM

I was testing your utility and found a bug running it in Windows XP, for some reason it crashed immediately.

I found that file_exits did a fclose over a NULL file causing the crash.

Also removed the need for getopt as my Microsoft Visual C++ 2008 compiler doesn't have it.

A few iterations later also made it Mac OS X compatible ;)

Attached Files



#6 newcoleco OFFLINE  

newcoleco

    Stargunner

  • Topic Starter
  • 1,328 posts
  • Always Tired
  • Location:Quebec

Posted Thu Mar 29, 2018 7:44 PM

I was testing your utility and found a bug running it in Windows XP, for some reason it crashed immediately.

I found that file_exits did a fclose over a NULL file causing the crash.

Also removed the need for getopt as my Microsoft Visual C++ 2008 compiler doesn't have it.

A few iterations later also made it Mac OS X compatible icon_wink.gif

 

Oops, thanks for the bug report.  This bug is also present in DAN1 and DAN3 tools since the main structure is the same. I will have to check it out.

 

Windows and Mac versions, that's very nice!

 

The next step could be to make a DAN2-to-RAM routine, derived from the DAN2-to-VRAM version... or someone already did one?

 

And, it seems DAN2 works better for my projects than DAN1 or DAN3 anyway. DAN3 would be great if only I use more elaborated pixel-art graphics which I don't. DAN2 is the winner for me by a few bytes.







Also tagged with one or more of these keywords: dan2, dan1, lz77, lzss, compression, z80, vram, lossless, pletter, zx7

0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users