Trying to figure what kind of compression was used

Question

I got the following raw data, which are the first 35 bytes of a compressed png image:

00 89 50 4e 47 0d 0a 1a 0a 00 00 00 00 0d 49 48
44 52 08 00 00 02 58 00 83 5a 08 06 80 00 83 64
31 28 fe

I also happened to have the 33 bytes the above 35 bytes were before they were compressed

89 50 4e 47 0d 0a 1a 0a 00 00 00 0d 49 48 44 52
00 00 02 58 00 00 00 5a 08 06 00 00 00 64 31 28
fe

I'm staring on those bytes for days now and can't figure our the compression algorithm... it looks like some kind of lz77 or Sliding Window Compression.

Any help would be much appreciated with this problem

Answer 1

It does indeed appear to be an LZ77 variant where 8 encoded/not-encoded flags are combined into a single flag byte.

The compressed data is then grouped into 8 data 'units' where each unit is represented either by a single uncompressed byte or by a 2 byte dictionary entry.

The data for a batch of 8 units is preceded by the flag byte where each of its 8 bits indicates whether each unit is an uncompressed byte or a dictionary entry.

There's not enough data here to be 100% sure about the encoding of the dictionary entries or what any window is because there are only 2 (identical) dictionary entries in your example data. However, it appears likely that the 2 byte entry is made up of a 12 bit offset and a 4 bit length referring back to previously decompressed data.

In the case of your compressed data, the decompression proceeds as follows -

compressed                  decompressed
flags         data          offset  data            
00                                                  
    0=>raw    89      ->    0000:   89              
    0=>raw    50      ->    0001:   50              
    0=>raw    4e      ->    0002:   4e              
    0=>raw    47      ->    0003:   47              
    0=>raw    0d      ->    0004:   0d              
    0=>raw    0a      ->    0005:   0a              
    0=>raw    1a      ->    0006:   1a              
    0=>raw    0a      ->    0007:   0a              
00                                                  
    0=>raw    00      ->    0008:   00              
    0=>raw    00      ->    0009:   00              
    0=>raw    00      ->    000A:   00              
    0=>raw    0d      ->    000B:   0d              
    0=>raw    49      ->    000C:   49              
    0=>raw    48      ->    000D:   48              
    0=>raw    44      ->    000E:   44              
    0=>raw    52      ->    000F:   52              
08                                                  
    0=>raw    00      ->    0010:   00              
    0=>raw    00      ->    0011:   00              
    0=>raw    02      ->    0012:   02              
    0=>raw    58      ->    0013:   58              
    1=>dict   00 83   ->    0014:   00 00 00    // copy of 3 bytes from offset 8    
    0=>raw    5A      ->    0017:   5A              
    0=>raw    08      ->    0018:   08              
    0=>raw    06      ->    0019:   06              
80                                                  
    1=>dict   00 83   ->    001A:   00 00 00    // copy of 3 bytes from offset 8        
    0=>raw    64      ->    001D:   64              
    0=>raw    31      ->    001E:   31              
    0=>raw    28      ->    001F:   28              
    0=>raw    fe      ->    0020:   fe              
    0=>raw    ...     ->    0021:   ...
    0=>raw    ...     ->    0022:   ...                 
    0=>raw    ...     ->    0023:   ...          

Answer 2

This looks like an format produced by a LZRW family algorithm.

The code referred there contains

#define FLAG_COMPRESS 0     /* Signals that compression occurred. */
#define FLAG_COPY     1     /* Signals that a copyover occurred.  */

(your variant may have those two swapped) and

#define ITEMMAX 16     /* Maximum number of bytes in an expanded item.  */