1

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

  • can you share all of the data, not just the first n bytes of file x – julian May 11 '17 at 15:06
  • hey i have something pretty similar just with 16 bits and not 8. can you tell us how did solve it? ian cock can you give me your skype or something to chat? – rertiyulte Jun 27 '17 at 0:37
  • If you have a new question, please ask it by clicking the Ask Question button. Include a link to this question if it helps provide context. - From Review – perror Jun 27 '17 at 8:42
2

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:   ...          
  • I was so sure it is the right solution, but sadly after decompressing it - the image isnt readable :( this is my decompression script: pastebin.com/N94jrkpu I'm so hoping you will find an error in my decompression script... – user20145 May 11 '17 at 21:28
  • 1
    The problem is that there are various ways of encoding the dictionary entities and it's not possible to tell how it's done from the exceedingly small data sample you've provided. Having more of the compressed image would help. – Ian Cook May 11 '17 at 21:39
  • the 4 bits definitely represent the amount, because the size of the decompressed file is right (I know that by the IDAT length) but the content isnt, any other ideas? – user20145 May 12 '17 at 8:00
0

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.  */
  • Can you please give an example on the data I provided – user20145 May 12 '17 at 7:20
  • @Matan The algorithm refuses to compress because of no savings (as you said, the original is 33 bytes, the "compressed" form is 35). The LZRW1 format is similar but not exact; for example, it uses 2 bytes of flags at a time, but otherwise the idea is the same. You may want to consult the decompression part of the LZRW code by my link to see if your decompression script has a bug (sorry, I cannot access pastebin now from behind a corporate firewall). – Leo B. May 12 '17 at 21:02
  • One thing to notice is that the compressed references use the absolute buffer position of the string to copy (offset 8) rather than the relative (how many bytes to step back to find the copy source). This is different from most LZ77 implementations. – Leo B. May 12 '17 at 21:18
  • I implemented a decompressor and it outputed a file in right side - but the CRC32 of the IDAT chunk doesnt fit the data itself, the CRC is right, the data isnt. – user20145 May 13 '17 at 6:26
  • What it means is that the 4 LSB bits are definitely the amount but the 12 MSB bits aren't just the offset, there is something more over there. – user20145 May 13 '17 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy