2

I have been trying to figure out how this compression algorithm works, so I can write a decompression tool for it.

The compressed data consists of the following layout:

0x00 →  0x03 : uncompressed data size (4 bytes, e.g. 0x80)
0x04 →  0x83 : multibyte table (named `_ptrArray`)
0x84 → 0x103 : 0x80 first bytes of the uncompressed data
the rest is the actual compressed data that I'm trying to figure out

I'm having no luck understanding how the data is actually being compressed, and so far I'm unable to recover the original data from the compression output.

I'm not sure what I should do next, the attempts I made thus far have been failed. I would deeply appreciate any help or advice I can get in order to understand this compression mechanism, and write a decompression tool for it.

Here's the reference implementation to compress the data, and the sample I've been working on:

Uncompressed data

https://pastebin.com/6sQyFY30

Compressed data

80 00 00 00 01 00 02 00 03 00 04 00 05 00 06 00 07 00 08 00 09 00 0A 00 0B 00 0C 00 0D 00 0E 00 0F 00 10 00 11 00 12 00 13 00 14 00 15 00 16 00 17 00 18 00 19 00 1A 00 1B 00 1C 00 1D 00 1E 00 1F 00 20 00 21 00 22 00 23 00 24 00 25 00 26 00 27 00 28 00 29 00 2A 00 2B 00 2C 00 75 00 76 00 77 00 78 00 79 00 7A 00 7B 00 7C 00 7D 00 7E 00 7F 00 80 00 81 00 82 00 83 00 84 00 85 00 86 00 87 00 88 00 FF FF FF FF FF FF FF FF FF FF FF FF FF FF 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF 93 37 A1 2B 8E 00 C0 37 00 0F 84 37 01 E0 FE AE 35 01 FE E0 84 36 00 0F B8 37 03 FF 7F 0F 03 83 39 05 80 E0 F0 F8 FC FE A1 3E 06 FE FE FC F8 F0 E0 80 83 34 02 03 0F 7F B9 36 82 00 06 3F 1F 0F 07 03 01 01 83 3F 02 00 00 80 80 00 00 C0 91 00 81 18 85 24 06 01 01 03 07 0F 1F 3F BE 33 8A 00 04 7F 7F 3F 3F 1F 80 00 00 0F 83 00 00 07 87 00 84 11 81 1C 04 3F 3F 7F 7F 7F CB 2F F7 00 00 E0 C1 00 B8 37 00 00 84 00 00 07 94 00 9D 1F 82 00 C0 37 B5 1F BD 00 00 03 84 37 01 F0 FE 92 1E 00 F0 85 37 02 C0 F8 FC 93 21 BD 00 02 3F 07 01 83 39 06 80 C0 E0 F0 F0 F0 F8 85 00 04 F0 F0 E0 C0 80 81 17 03 01 07 7F 0F 84 23 00 80 80 23 80 24 05 F8 F8 FC FC FE FE C9 3B 06 1F 0F 0F 07 03 03 01 81 00 00 00 82 00 81 09 06 03 03 07 0F 1F 3F 7F 84 23 03 7F 7F 3F 1F 81 26 00 07 80 26 83 23 09 00 80 80 C0 C0 E0 E0 F0 F0 F8 C5 3F A7 00 0D 7F 7F 3F 3F 1F 1F 0F 07 07 03 03 01 01 00 C3 2C 00 FE 81 00 00 FC 82 00 81 09 9B 38 81 21 83 00 BD 2E 07 FC F8 F0 E0 C0 80 80 00 8F 00 04 80 C0 E0 F0 F8 95 3F 02 3F 0F 01 84 25 00 F0 B8 3A 01 F0 C0 83 2C 06 01 07 1F 3F 3F 7F 7F 85 16 04 7F 7F 3F 0F 07 85 3D 01 E0 FC 95 3A 00 03 84 22 00 F8 B5 36 83 34 02 00 00 3F 92 1D 00 1F 85 1E 00 C0 95 39 85 20 B5 37 00 0F 84 37 00 F0 95 1F 00 01 85 39 01 F8 FE 8E 1C 02 FC F0 80 83 1C 01 01 1F B5 37 03 FF 7F 0F 01 83 39 02 C0 F0 FC 92 20 02 3F 0F 07 85 3B 03 80 C0 C0 E0 85 00 01 C0 80 85 33 02 03 0F 3F B6 35 83 3A 86 00 98 22 03 3F 1F 1F 0F 81 00 00 07 83 00 81 0A 04 1F 1F 3F 3F 7F BB 32 FF C0 FE C0 00 FC C1 00 B8 37 00 00 C1 00 C0 37 A1 2B 8E 00 C0 37 00 0F 84 37 01 E0 FE AE 35 01 FE E0 84 36 00 0F B8 37 03 FF 7F 0F 03 83 39 05 80 E0 F0 F8 FC FE A1 3E 06 FE FE FC F8 F0 E0 80 83 34 02 03 0F 7F B9 36 82 00 06 3F 1F 0F 07 03 01 01 83 3F 02 00 00 80 80 00 00 C0 91 00 81 18 85 24 06 01 01 03 07 0F 1F 3F BE 33 8A 00 04 7F 7F 3F 3F 1F 80 00 00 0F 83 00 00 07 87 00 84 11 81 1C 04 3F 3F 7F 7F 7F CB 2F 8B 40 00 FE 84 00 8C 15 04 FC F8 F8 F0 E0 80 00 00 C0 82 00 80 08 04 F0 F0 F8 F8 FC 8C 25 BE 00 02 FC E0 00 81 00 02 01 0F 3F 89 33 01 F0 C0 83 15 03 07 07 0F 1F 84 00 03 0F 07 03 01 82 14 01 C0 F0 C8 36 83 35 01 00 0F 91 14 01 07 7F 8B 2B 02 FF FF 3F 83 18 00 00 C7 37 00 01 83 37 00 FC 8A 14 83 13 00 00 8D 2B 02 FF FC E0 82 17 01 03 1F C7 37 02 FF 1F 03 82 3A 06 C0 E0 F0 F8 FC FC FE 83 00 84 37 84 0D 11 FE FC FC F8 F8 F0 F0 E0 C0 00 00 02 02 06 0E 3E 7E FE C8 36 81 00 08 7F 3F 1F 0F 07 07 03 03 01 82 00 84 34 99 00 CC 37 FB 00 05 F8 FC FC FE FE FE F7 37 03 01 01 01 00 82 00 11 80 80 C0 C0 C0 E0 E0 E0 F0 F0 F8 F8 F8 FC FC FC FE FE E8 3D 13 7F 7F 3F 3F 3F 1F 1F 1F 0F 0F 0F 07 07 03 03 03 01 01 01 00 81 00 12 80 80 80 C0 C0 E0 E0 E0 F0 F0 F0 F8 F8 FC FC FC FE FE FE DA 3F 8B 00 0E 7F 7F 3F 3F 3F 1F 1F 1F 0F 0F 0F 06 06 02 00 85 00 DB 2C 12 FE FE FE FC FC F8 F8 F8 F0 F0 F0 E0 E0 E0 C0 C0 80 80 80 82 2D 09 01 01 01 03 03 07 07 07 0F 0F CA 2C 0E FC F8 F8 F0 F0 F0 E0 E0 E0 C0 C0 80 80 80 00 82 00 11 01 01 03 03 03 07 07 07 0F 0F 1F 1F 1F 3F 3F 3F 7F 7F 83 2B D1 00 10 01 03 03 03 07 07 0F 0F 0F 1F 1F 1F 3F 3F 7F 7F 7F 98 2B FD 40 00 F0 83 00 CA 2C 00 80 83 00 A2 2B 00 00 83 00 B6 2C 00 FC 87 00 86 13 00 00 83 00 88 1A 97 00 BD 37 00 01 87 00 91 13 9E 00 BD 37 BD 00 FD 77 00 7F 83 00 D9 2C 00 FE 82 00 00 FC 84 00 83 0D 95 2B C4 00 0A FE FC F8 F0 E0 E0 C0 80 80 80 00 96 00 09 80 80 C0 C0 E0 E0 F0 F8 FC FE CC 34 01 F0 C0 82 2C 0A 01 03 07 0F 1F 1F 3F 3F 7F 7F 7F 8D 21 80 12 07 3F 3F 3F 1F 0F 07 03 01 82 2A 01 C0 F0 C8 36 82 34 02 00 00 3F A1 2B 02 FF FF 3F 82 38 01 00 00 C7 37 02 3F 07 01 81 37 03 C0 F8 FC FE 9D 2A 03 FE FC F8 C0 81 2B 02 01 07 3F B5 2C 00 F0 91 00 02 70 30 10 81 3A 08 00 00 80 C0 C0 C0 E0 E0 E0 8D 1F 80 12 80 18 00 80 83 23 04 10 30 70 F0 F0 B5 36 01 FF 07 C3 00 B6 37 FF C0 FF C0 86 00 00 FE 81 00 00 FC 82 00 81 09 9B 2C 81 21 83 00 BD 2E 07 FC F8 F0 E0 C0 80 80 00 8F 00 04 80 C0 E0 F0 F8 95 3F 02 3F 0F 01 84 25 00 F0 B8 3A 01 F0 C0 83 2C 06 01 07 1F 3F 3F 7F 7F 85 16 04 7F 7F 3F 0F 07 85 3D 01 E0 FC 95 3A 00 03 84 22 00 F8 B5 36 83 34 02 00 00 3F 92 1D 00 1F 85 1E 00 C0 95 39 85 20 B5 37 00 0F 84 37 00 F0 95 1F 00 01 85 39 01 F8 FE 8E 1C 02 FC F0 80 83 1C 01 01 1F B5 37 03 FF 7F 0F 01 83 39 02 C0 F0 FC 92 20 02 3F 0F 07 85 3B 03 80 C0 C0 E0 85 00 01 C0 80 85 33 02 03 0F 3F B6 35 83 3A 86 00 98 22 03 3F 1F 1F 0F 81 00 00 07 83 00 81 0A 04 1F 1F 3F 3F 7F BB 32 98 40 08 FE FC FC F8 F8 F0 F0 F0 E0 83 00 00 C0 84 00 84 0E 80 18 04 F8 F8 FC FC FE D1 31 05 FC F0 E0 C0 80 00 81 00 07 01 03 03 03 07 07 07 0F 8C 00 80 12 80 18 00 01 82 22 04 80 C0 E0 F0 FC C9 35 00 F0 82 31 04 00 03 1F 3F 7F 9D 2A 03 7F 3F 1F 03 82 3C 01 00 F0 C7 37 00 01 83 37 00 F8 A1 2B 02 FF FF F8 83 37 00 01 C7 37 02 FF 1F 07 83 3A 06 80 C0 E0 F0 F8 F8 FC 80 00 00 FE 8C 00 81 13 05 F8 F8 F0 E0 E0 80 83 34 01 07 1F C8 36 82 00 0B 7F 3F 1F 0F 07 07 03 03 01 01 01 00 92 00 80 18 07 03 03 07 07 0F 1F 3F 7F CD 33 92 00 00 7F 86 00 9F 2B BD 40 00 C0 83 00 F6 37 00 00 83 00 E4 2C 06 FC F8 F0 E0 C0 C0 80 81 00 84 30 B0 00 B6 35 01 E0 00 82 00 04 07 1F 3F 3F 7F 85 00 84 2C 86 0F A0 00 B6 37 83 36 00 00 9E 13 D5 00 00 0F 83 00 9E 13 E9 40 00 C0 83 00 F6 37 00 00 83 00 E7 2C 00 80 8B 00 84 37 8C 15 8F 00 08 C0 C0 C0 E0 E0 F0 F0 F8 FE BD 37 00 3F 8B 00 84 37 8C 15 8F 00 03 1F 1F 07 01 82 29 01 80 F8 BD 39 8A 00 84 37 CE 2B A5 00 00 03 83 00 CE 2B FF C0 FF C0 A3 40 00 FE 84 00 8C 15 04 FC F8 F8 F0 E0 80 00 00 C0 82 00 80 08 04 F0 F0 F8 F8 FC 8C 25 BE 00 02 FC E0 00 81 00 02 01 0F 3F 89 33 01 F0 C0 83 15 03 07 07 0F 1F 84 00 03 0F 07 03 01 82 14 01 C0 F0 C8 36 83 35 01 00 0F 91 14 01 07 7F 8B 2B 02 FF FF 3F 83 18 00 00 C7 37 00 01 83 37 00 FC 8A 14 83 13 00 00 8D 2B 02 FF FC E0 82 17 01 03 1F C7 37 02 FF 1F 03 82 3A 06 C0 E0 F0 F8 FC FC FE 83 00 84 37 84 0D 11 FE FC FC F8 F8 F0 F0 E0 C0 00 00 02 02 06 0E 3E 7E FE C8 36 81 00 08 7F 3F 1F 0F 07 07 03 03 01 82 00 84 34 99 00 CC 37 FB 00 00 FC 83 00 F6 37 00 00 83 00 E7 2C 00 F8 8B 00 84 37 8C 15 8F 00 04 FC FC FC FE FE C1 37 00 03 8B 00 84 37 8C 15 8F 00 01 01 01 82 27 02 80 E0 F8 C1 3C 87 00 84 37 A0 29 01 7F 1F 83 2A 00 80 F4 37 AB 2B A5 00 00 3F 83 00 CE 2B FF C0 FF C0 C3 00 09 FE FE FE FC FC FC F8 F8 F8 F0 80 00 03 E0 E0 E0 C0 D3 2C 09 FE FE FE FC FC FC F8 F8 F8 F0 80 00 09 E0 E0 E0 C0 C0 C0 80 80 80 00 85 00 00 01 80 00 06 03 03 03 07 07 07 0F BA 2C 09 FE FE FE FC FC FC F8 F8 F8 F0 80 00 09 E0 E0 E0 C0 C0 C0 80 80 80 00 83 00 00 01 80 00 03 03 03 03 07 80 00 01 0F 0F 85 31 03 7F 7F 7F FF C5 00 00 00 86 00 07 06 06 06 07 0F 0F 0F 1F 80 00 03 3F 3F 3F 7F 80 00 95 2B C6 34 80 00 0A 0F 0F 07 07 07 03 03 03 01 01 01 83 3E 03 80 80 80 C0 80 00 03 E0 E0 E0 F0 80 00 03 F8 F8 F8 FC 80 00 02 FE FE FE D4 37 8B 00 06 7F 7F 7F 3F 3F 3F 1F 80 00 0B 0F 0F 0F 07 07 07 03 03 03 01 01 01 85 2F 85 00 0C E0 E0 E0 F0 F0 F0 F8 F8 F8 FC FC FC FE 80 00 CF 3F 8E 00 06 7F 7F 7F 3F 3F 3F 1F 80 00 0C 0F 0F 0F 07 07 07 03 03 03 01 01 01 00 84 00 E0 38 95 00 04 7F 7F 7F 3F 3F BD 2C 06 FE FC F8 F8 F0 F0 E0 81 00 00 C0 82 00 81 09 04 F0 F0 F8 FC FE 96 2F 01 EF E3 81 23 81 00 00 F8 BA 32 04 FC F0 C0 80 00 81 00 05 01 03 03 07 07 0F 84 00 02 07 07 03 82 14 04 00 00 80 E0 F8 95 3C 00 1F 85 23 00 E0 B6 35 00 F0 82 32 04 00 00 03 1F 7F 8E 1B 02 7F 0F 01 84 1D 01 C0 FC 94 39 00 3F 84 20 00 80 B5 37 84 36 00 00 94 1E 00 0F 85 1F 94 39 00 F8 84 1E 00 01 B5 37 01 FF 07 84 38 01 F0 FC 93 1F 01 1F 03 84 20 06 80 E0 F0 F8 FC FC FE 85 00 04 FC F8 F8 F0 C0 84 1A 01 03 1F B6 36 80 00 01 1F 07 84 00 01 C7 F7 93 20 07 7F 1F 0F 07 07 03 01 01 83 3F 87 00 07 01 01 03 03 07 0F 1F 3F B9 34 AE 00 00 7F 83 00 A2 2B D6 00 09 FE FE FE FC FC FC F8 F8 F8 F0 80 00 03 E0 E0 E0 C0 D3 2C 09 FE FE FE FC FC FC F8 F8 F8 F0 80 00 09 E0 E0 E0 C0 C0 C0 80 80 80 00 85 00 00 01 80 00 06 03 03 03 07 07 07 0F BA 2C 09 FE FE FE FC FC FC F8 F8 F8 F0 80 00 09 E0 E0 E0 C0 C0 C0 80 80 80 00 83 00 00 01 80 00 03 03 03 03 07 80 00 01 0F 0F 85 31 03 7F 7F 7F FF C5 00 00 00 86 00 07 06 06 06 07 0F 0F 0F 1F 80 00 03 3F 3F 3F 7F 80 00 95 2B C6 34 80 00 0A 0F 0F 07 07 07 03 03 03 01 01 01 83 3E 03 80 80 80 C0 80 00 03 E0 E0 E0 F0 80 00 03 F8 F8 F8 FC 80 00 02 FE FE FE D4 37 8B 00 06 7F 7F 7F 3F 3F 3F 1F 80 00 0B 0F 0F 0F 07 07 07 03 03 03 01 01 01 85 2F 85 00 0C E0 E0 E0 F0 F0 F0 F8 F8 F8 FC FC FC FE 80 00 CF 3F 8E 00 06 7F 7F 7F 3F 3F 3F 1F 80 00 0C 0F 0F 0F 07 07 07 03 03 03 01 01 01 00 84 00 E0 38 95 00 04 7F 7F 7F 3F 3F F8 37 FF C0 D1 80 00 FE 83 00 00 FC 86 00 84 10 D5 2C 0C FE FC F8 F8 F0 E0 E0 C0 C0 80 80 80 00 9C 00 80 22 08 C0 C0 E0 E0 F0 F0 F8 FC FE C0 31 04 F8 F0 C0 80 00 82 00 09 01 03 07 07 0F 0F 1F 1F 1F 3F 81 00 00 7F 8E 00 82 16 80 1E 06 0F 0F 07 07 03 01 00 82 00 03 80 C0 E0 F8 B8 3D 01 FC C0 84 32 02 0F 3F 7F 9D 2B 8D 00 02 7F 3F 0F 84 3C 01 C0 FC B5 37 83 35 01 00 00 AD 33 85 00 83 37 01 00 00 B5 37 02 7F 07 01 83 38 02 E0 F8 FE AD 33 02 FE FC E0 83 34 02 01 07 7F B5 37 81 3A 01 1F 0F 83 00 02 8F CF EF A7 34 03 EF CF 8F 0F 83 00 00 1F B9 34 97 40 08 FE FC FC F8 F8 F0 F0 F0 E0 83 00 00 C0 84 00 84 0E 80 18 04 F8 F8 FC FC FE D1 31 05 FC F0 E0 C0 80 00 81 00 07 01 03 03 03 07 07 07 0F 8C 00 80 12 80 18 00 01 82 22 04 80 C0 E0 F0 FC C9 35 00 F0 82 31 04 00 03 1F 3F 7F 9D 2A 03 7F 3F 1F 03 82 3C 01 00 F0 C7 37 00 01 83 37 00 F8 A1 2B 02 FF FF F8 83 37 00 01 C7 37 02 FF 1F 07 83 3A 06 80 C0 E0 F0 F8 F8 FC 80 00 00 FE 8C 00 81 13 05 F8 F8 F0 E0 E0 80 83 34 01 07 1F C8 36 82 00 0B 7F 3F 1F 0F 07 07 03 03 01 01 01 00 92 00 80 18 07 03 03 07 07 0F 1F 3F 7F CD 33 92 00 00 7F 86 00 9F 2B BD 00 00 F8 AF 00 CA 37 03 03 02 02 00 80 00 03 01 01 01 03 A5 00 C8 35 01 F0 C0 81 34 01 00 3E A1 2B D1 00 02 1F 07 01 82 38 03 00 80 80 C0 A6 00 C9 38 0B FC F0 E0 E0 40 00 01 07 0F 0F 0F 1F A5 00 C8 36 00 00 83 00 04 F0 F8 FC FC FE A6 00 C8 37 08 FF 3F 1F 0F 07 03 03 03 01 82 00 00 00 A3 00 C9 37 FE 00 00 FC C3 00 B6 37 00 03 80 00 01 02 00 85 00 00 01 80 00 81 11 87 00 81 11 86 1E 01 02 02 8B 1C 87 00 B5 36 03 F8 E0 C0 80 80 2F 05 03 0F 1F 3F 7F 7F 97 26 05 7F 7F 3F 1F 0F 03 81 3A 02 C0 E0 F8 97 26 AE 00 81 33 80 00 A2 2B 80 00 81 2B 80 00 C7 37 01 1F 03 83 38 04 E0 F0 FC FC FE 99 28 04 FE FC FC F0 E0 83 2B 01 03 1F C7 37 80 00 05 3F 1F 0F 07 03 01 83 3E 03 80 80 80 C0 8E 00 80 14 83 1D 05 01 03 07 0F 1F 3F CA 34 88 00 05 7F 7F 3F 3F 3F 1F 81 00 00 0F 88 00 82 10 80 18 01 7F 7F D5 2F 99 00 00 FE 80 00 00 FC 82 00 80 08 D3 2C 02 FE F0 E0 82 00 01 E3 EF 89 15 06 FC F0 E0 C0 80 80 00 80 00 00 01 84 00 81 0B 05 80 80 C0 E0 F0 FC CA 35 01 C0 00 82 00 00 1F 8A 14 00 E0 83 14 03 07 1F 7F 7F 87 15 03 7F 3F 1F 03 83 17 00 F0 C7 37 83 35 00 00 92 14 88 33 84 00 00 FE 83 18 00 01 C7 37 01 1F 01 82 37 02 C0 FC FE 8F 37 8C 33 02 FC F0 C0 81 15 02 03 07 3F C7 36 80 00 03 3F 1F 07 03 82 3C 03 80 C0 C0 E0 83 00 84 37 84 0D 04 E0 C0 C0 80 80 83 11 02 20 20 60 81 10 CA 37 83 00 04 7F 7F 3F 3F 1F 82 00 00 0F 9F 00 D0 37 F7 00 00 FC AF 00 CA 37 00 03 80 00 02 02 02 00 82 00 00 01 80 00 81 0F 9C 00 C9 36 03 FC F0 C0 80 80 30 04 07 1F 3F 7F 7F 9D 2B D0 00 80 33 81 00 00 FE F0 32 82 00 01 1F 03 83 38 06 80 E0 F0 F0 F8 F8 FC A3 00 CB 3A 08 7F 3F 1F 1F 0F 0F 07 07 03 82 00 00 01 A0 00 CB 37 FC 00 04 F8 FC FC FE FE F8 37 01 01 00 83 00 10 80 80 C0 C0 C0 E0 E0 F0 F0 F8 F8 F8 FC FC FE FE FE A4 2C 00 80 83 00 BA 3B 11 7F 7F 3F 3F 3F 1F 1F 0F 0F 0F 07 07 03 03 03 01 01 00 82 00 10 80 80 C0 C0 C0 E0 E0 F0 F0 F0 F8 F8 FC FC FE FE FE 8B 31 05 FE FC FC F8 F0 C0 83 2A 00 07 BA 37 91 00 0F 7F 7F 3F 3F 3F 1F 1F 0F 0F 0F 07 07 03 03 02 00 83 00 03 80 80 80 C0 80 00 01 80 80 82 0D 08 01 01 01 03 07 07 0F 1F 7F CA 31 11 FE FE FE FC FC F8 F8 F8 F0 F0 E0 E0 E0 C0 C0 80 80 80 82 32 0F 01 01 03 03 03 07 07 0F 0F 0F 1F 1F 3F 3F 3F 7F C4 2C 0F FC FC FC F8 F8 F0 F0 F0 E0 E0 C0 C0 C0 80 80 00 82 00 10 01 01 03 03 03 07 07 0F 0F 0F 1F 1F 3F 3F 3F 7F 7F 83 2B D1 00 11 00 01 01 01 03 03 07 07 07 0F 0F 1F 1F 3F 3F 3F 7F 7F 97 2B FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 FF C0 DF 80

Compression routine (code below)

const COMPRESS_SAMPLE_RATE =   0x800,
      TABLE_PTR_SIZE =         0x40,
      MAX_UNCOMPRESSED_BYTES = 0x80,
      MAX_COMPRESSED_BYTES =   0x202,
      MIN_COMPRESSED_BYTES =   0x2,

      COMPRESSION_FLAG =       0x80;

_ptrArray = [];

function lookupBestOccurs(data, size)
{
    // var occurs[COMPRESS_SAMPLE_RATE][2];
    var occurs = Array(COMPRESS_SAMPLE_RATE).fill(0).map(x => Array(2).fill(0));

    var oneIsPresent = false;
    var b;
    var i;

    // Initialize the table
    // occurs[i][0] = number of occurrences of the offset
    // occurs[i][1] = offset
    for (i=0; i < COMPRESS_SAMPLE_RATE; i++) {
        occurs[i][0] = 0;
        occurs[i][1] = i;
    }

    // Calculate the byte occurrence
    for (i=COMPRESS_SAMPLE_RATE; i < size; i += COMPRESS_SAMPLE_RATE) {
        b = data[i];
        for (let j=1; j < COMPRESS_SAMPLE_RATE; j++)
            if (data[i - j] == b)
                occurs[(j - 1)][0]++;
    }

    // Order the array
    // qsort(occurs, COMPRESS_SAMPLE_RATE, sizeof(uint32_t)*2, __compare);
    occurs.sort( function(n1, n2) { return n2[0] - n1[0]; } );

    // Set the pointer table to use for compression
    for (i=0; i < TABLE_PTR_SIZE; i++) {
        _ptrArray[i] = occurs[i][1] + 1;
        if (_ptrArray[i] == 1)
            oneIsPresent = true;
    }
    // Append the value 1 which improves the compression of multiple same bytes
    if (!oneIsPresent)
        _ptrArray[TABLE_PTR_SIZE-1] = 1;

    return true;
}

function compress(data, size)
{

    /* unsigned long */
    var r, w=4, uncompSize=0, maxCompSize, bestCompCounter, bestPtr;
    var rawDataCounter = 0, rawDataCounterPtr=0, maxOutputSize;

    var out = []; /* size: maxOutputSize */

    // Create the output buffer
    maxOutputSize = size;

    // Print the table
    for (let i = 0; i < TABLE_PTR_SIZE; i++, w += 2) {
        out[w] = _ptrArray[i];
        out[w+1] = _ptrArray[i] >> 8;
        if (_ptrArray[i] > uncompSize)
            uncompSize = _ptrArray[i];
    }

    // Print the first uncompressed bytes
    if (uncompSize > MAX_UNCOMPRESSED_BYTES)
        uncompSize = MAX_UNCOMPRESSED_BYTES;

    out[0] = uncompSize;
    out[1] = uncompSize>>8;
    out[2] = uncompSize>>16;
    out[3] = uncompSize>>24;

    for (r=0; r < uncompSize; r++, w++)
        out[w] = data[r];

    //
    // Compress the data
    //
    do {
        maxCompSize = size - r > MAX_COMPRESSED_BYTES ? MAX_COMPRESSED_BYTES :
            size - r;

        // End of the compression
        if (!maxCompSize) {
            if (rawDataCounter)
                out[rawDataCounterPtr] = rawDataCounter - 1;
            break;

        // Try to compress the next piece of data
        } else if (maxCompSize >= 2) {
            bestCompCounter = 0;
            bestPtr = 0;

            // Check if there is enough space
            if (w + 2 >= maxOutputSize) {
                w += 2;
                break;
            }

            // Check the best similar piece of data
            for (let i = 0; i < TABLE_PTR_SIZE; i++) {
                let counter;

                if (_ptrArray[i] > r)
                    continue;

                for (counter = 0; counter < maxCompSize; counter++)
                    if (data[r + counter] != data[r + counter - _ptrArray[i]])
                        break;

                if (counter > bestCompCounter) {
                    bestCompCounter = counter;
                    bestPtr = i;
                }
            }

            // If the reproduced piece is large enough, use it!
            if (bestCompCounter > MIN_COMPRESSED_BYTES) {
                r += bestCompCounter;
                bestCompCounter -= 3;
                
                out[w] = COMPRESSION_FLAG | (bestCompCounter & 0x7F);
                out[w+1] = ((bestCompCounter >> 1) & 0xC0) | (bestPtr & 0x3F);

                // _bestCompCounter = (out[w] & ~COMPRESSION_FLAG) + ((out[w+1] & 0xC0) << 1);
                // _bestPtr = out[w+1] & 0x3F;

                w += 2;
                if (rawDataCounter) {
                    out[rawDataCounterPtr] = rawDataCounter - 1;
                    rawDataCounter = 0;
                }
                continue;
            }
        }

        // Else write the uncompressed data
        rawDataCounter++;
        if (rawDataCounter == 1) {
            // Check if there is enough space
            if (w + 2 >= maxOutputSize) {
                w += 2;
                break;
            }
            rawDataCounterPtr = w;
            w++;
        } else if (rawDataCounter == MAX_UNCOMPRESSED_BYTES) {
            out[rawDataCounterPtr] = 0x7F;
            rawDataCounter = 0;
        }
        out[w] = data[r];
        w++;
        r++;
    } while (w < maxOutputSize);

    // Does the compression finished without any error?
    if (w >= maxOutputSize) {
        alert("No more space available in the output buffer for compression");
        return false;
    }

    // Copy the buffer in a best buffer
    outputSize = w;

    return out;
}

function initApp(t) {
    hexData = [];

    for (let i = 0; i < t.length; i++)
        hexData.push( t.charCodeAt(i) );

    const result = lookupBestOccurs(hexData, hexData.length) ?
                           compress(hexData, hexData.length) : [];

    return result;
}

Using the provided uncompressed data, compressed data, and the compression algorithm, how can I write a decompression mechanism?

Improve this question
0

1 Answer 1

Reset to default
3

The question is a bit odd. If you have the code that generates the compressed data, you simply read it, understand it, then write a decompressor because you know how the compressed data was produced.

In your case it seems like Google Fu is easier.

I googled for javascript "MAX_UNCOMPRESSED_BYTES", which led me to a file diff for a Gentoo package (called net-print splix or something I don't know what it is) that looked promising.

So I checked the source code and it seems like I found the original C++ source for your code, which was apparently transliterated to JavaScript from that (even the comments match):

https://sourceforge.net/projects/splix/

The C++ code for what you posted can be found in splix-2.0.0\src\algo0x11.cpp. There is also a decompressor in a different file splix-2.0.0\tools\algo0x11.cpp

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.