Некоторое время назад встал вопрос о необходимости библиотеки для сжатия assert`ов в движке. На тот момент для этих целей использовалась библиотека LZO (к слову, единственная используемая мной сторонняя библиотека), однако из-за её GPL-лицензии надо было или покупать её pro-версию, или менять на что-то другое (возможно даже своё). Кроме того, давно назревал вопрос о целесообразности использования для поставленной задачи именно алгоритма семейства LZ77. С целью сбора и анализа данных о различных алгоритмах сжатия в контексте указанной задачи и был начал этот R&D проект.
Учитывая задачу, для которой планировалось применять сжатие, были выработаны следующие требования к реализуемому алгоритму сжатия:
- Возможность работать с независимыми блоками размером от 1КБ до 1ГБ
- Отсутствие требований к быстрой компрессии
- Высокая скорость декомпрессии (~256 МБ/с) на блоках в 256КБ-1МБ
- Необходимость вычислять CRC32 хеш результатов декомпрессии (либо в процессе декомпрессии, либо дополнительным шагом)
Столь высокие требования к скорости декомпрессии сразу же исключали любые сложные алгоритмы, вроде PPM, да и вообще любые адаптивные алгоритмы.
Дальнейшие изыскания показали также нецелесообразность использования статического арифметического кодирования, т.к. оно лишь незначительно выигрывает в сжатии у кодов Хаффмана, но при этом значительно проигрывает ему в производительности. Простые реализации алгоритмов семейства LZ78 также не дали желаемых результатов – отсутствие сколько-нибудь существенного преимущества над LZ77 при значительно меньшей скорости работы.
Таким образом с алгоритмической стороны остались только Хаффман, LZ77 и их комбинация (широко известная реализация такой комбинации – формат deflate, используемый в zip). Кроме того, компрессор LZ77 обычно ещё разделяют на 2 варианта – быстро/качественно. Со стороны библиотек в тестировании участвовали LZO, LZ4 (как возможная замена LZO) и ZIP (как классическая вещь, которую очень часто советуют для этой задачи). Кроме них естественно участвовали и собственные реализации всех 3-х вариантов.
Так уж сложилось, что изначально для сравнения алгоритмов был выбран отнюдь не лучший, с точки зрения планируемого применения, набор файлов:
- Английский текст – 186 223 байта
- Исполняемая программа – 123 808 байт
- Малоцветная монохромная картинка – 65 580 байт
- Полноцветная монохромная картинка – 65 580 байт
- 3D-модель – 1 030 256 байт
На данном наборе были получены следующие результаты:
| Алгоритм | Файл 1 | Файл 2 | Файл 3 | Файл 4 | Файл 5 |
| Huffman | 56,5%|214,47|293,42 | 70,1%|205,26|252,29 | 35,2%|221,43|312,28 | 95,7%|195,94|279,50 | 73,6%|209,70|269,63 |
| LZ77_3S | 53,4%|197,39|398,66 | 44,4%|221,83|530,26 | 39,3%|271,87|436,07 | 95,4%|141,03|690,15 | 52,7%|203,71|649,44 |
| LZ77_4S | 48,6%|238,98|453,17 | 42,0%|285,51|626,14 | 33,5%|349,19|535,10 | 95,9%|316,32|1267,6 | 51,7%|261,60|816,50 |
| LZ77_3L | 54,2%|198,50|403,75 | 45,3%|228,23|523,12 | 40,3%|272,32|441,99 | 94,6%|140,64|683,96 | 51,8%|207,99|601,65 |
| LZ77_4L | 49,0%|238,64|454,76 | 42,7%|301,02|626,37 | 34,4%|344,37|528,38 | 95,5%|313,70|1231,5 | 51,5%|291,08|738,51 |
| LZO_1x_15 | 55,6%|174,93|385,35 | 42,2%|183,68|553,26 | 37,2%|337,89|525,10 | 97,0%|81,06|1117,5 | 50,8%|170,28|679,16 |
| LZ4 | 60,6%|331,1|1598,6 | 45,3%|444,5|1924,0 | 45,2%|553,9|1135,9 | 97,6%|490,1|3809,6 | 55,0%|491,9|1858,8 |
| LZ77_3S+ | 40,0%|13,51|510,63 | 37,8%|13,24|604,22 | 23,0%|2,80|826,08 | 93,5%|52,80|652,13 | 47,7%|5,03|761,20 |
| LZ77_4S+ | 41,0%|26,28|517,27 | 38,1%|22,52|668,74 | 23,0%|4,15|802,75 | 95,2%|68,79|1145,2 | 47,6%|6,64|932,57 |
| LZ77_3L+ | 40,7%|5,70|519,77 | 38,7%|8,87|595,49 | 23,9%|2,77|835,34 | 92,9%|43,87|654,18 | 40,4%|2,07|895,64 |
| LZ77_4L+ | 41,2%|11,81|531,00 | 38,8%|14,20|674,83 | 23,8%|4,09|820,50 | 94,8%|50,92|1118,6 | 40,2%|2,97|1082,0 |
| LZO_1x_999 | 41,2%|6,74|423,14 | 33,8%|5,87|599,35 | 24,6%|1,86|659,60 | 92,6%|12,22|553,69 | 43,0%|6,09|781,05 |
| LZ4HC | 42,0%|23,6|1598,6 | 36,3%|38,6|1924,0 | 26,6%|7,6|1135,9 | 94,4%|50,1|3809,6 | 47,0%|30,9|1858,8 |
| LZHuffS | 49,3%|138,65|258,24 | 39,5%|156,79|310,92 | 28,7%|177,06|275,92 | 94,1%|90,85|241,94 | 45,1%|143,78|310,36 |
| LZHuffL | 50,1%|138,71|255,47 | 40,3%|158,74|306,64 | 29,1%|176,82|278,19 | 93,5%|91,11|243,81 | 44,6%|145,82|300,46 |
| ZIP1 | 43,5%|40,10|116,62 | 35,7%|45,34|131,51 | 25,7%|54,29|152,83 | 87,0%|25,54|90,45 | 41,9%|37,48|125,12 |
| LZHuffS+ | 38,2%|13,15|306,70 | 34,6%|12,92|352,01 | 21,9%|2,79|460,89 | 92,5%|42,11|239,20 | 42,4%|5,00|350,57 |
| LZHuffL+ | 38,5%|5,64|311,69 | 35,3%|8,74|351,26 | 22,1%|2,77|466,74 | 92,1%|36,53|243,23 | 36,4%|2,07|406,02 |
| ZIP9 | 36,1%|10,83|133,71 | 31,6%|3,48|148,20 | 19,5%|1,42|196,60 | 87,6%|19,34|93,34 | 38,3%|4,62|139,42 |
Исходя из полученых данных, можно было сделать следующие выводы:
- Использование кодов Хаффмана в чистом виде нецелесообразно
- LZ4 обеспечивает просто огромные скорости декомпрессии, однако ценой худшего сжатия по сравнению с другими LZ-собратьями
- Использование связки LZ4+Huffman попросту глупо, т.к. декомпрессия всё равно упрётся в скорость именно декодера Хаффмана
- Библиотека LZO очень удачно спроектирована и, если нужно только LZ77-сжатие, то она довольно неплохой вариант
- LZ4 демонстрирует очень высокую скорость сжатия в режиме HighCompression, и причина тому – использование поискового алгоритма Morphing Match Chain (который я, к сожалению, так и не понял)
- Deflate демонстрирует наилучшие результаты почти всегда (проигрывая только на больших файлах из-за наличия у моей реализации режима с окном в 1МБ), однако его скорость декомпрессии непозволительно низкая для поставленной задачи
Как я уже писал выше, набор тестовых данных был слегка неудачным, потому были добавлены ещё 4 файла:
- 3D-стека – 11 526 376 байт
- Текстура 1024х1024, сжатая BC1 – 524 416 байт
- Текстура 1024х1024, сжатая BC7 – 1 048 576 байт
- 16-ти битная карта высот – 134 250 498 байт
Результаты новых тестов (без чистого Хаффмана и LZ4):
| Алгоритм | Файл 6 | Файл 7 | Файл 8 | Файл 9 |
| LZ77_3S | 47,1%|284,84|970,1 | 81,9%|128,42|413,60 | 96,9%|117,56|806,91 | 25,6%|331,22|1040,3 |
| LZ77_4S | 44,0%|348,31|1296,3 | 82,0%|193,18|597,13 | 96,9%|221,24|1204,0 | 24,7%|360,20|1184,2 |
| LZ77_3L | 47,2%|275,23|937,9 | 82,1%|136,18|398,41 | 96,0%|127,63|824,39 | 23,5%|315,52|1022,9 |
| LZ77_4L | 43,9%|382,33|1196,7 | 81,9%|222,58|563,46 | 96,2%|281,17|1163,2 | 23,0%|346,25|1056,9 |
| LZO_1x_15 | 43,6%|292,86|1221,0 | 84,1%|94,75|533,81 | 98,5%|75,98|1075,1 | 30,1%|263,97|984,17 |
| LZ77_3S+ | 42,1%|16,51|1117,0 | 76,9%|24,40|413,97 | 95,3%|33,51|745,36 | 19,7%|84,11|1340,5 |
| LZ77_4S+ | 42,0%|26,23|1342,6 | 79,0%|36,05|528,28 | 95,9%|44,92|1021,3 | 19,8%|113,22|1586,0 |
| LZ77_3L+ | 42,0%|1,04|1101,1 | 75,8%|6,54|374,37 | 92,4%|4,26|612,75 | 15,2%|11,45|1462,6 |
| LZ77_4L+ | 40,4%|1,11|1206,4 | 77,4%|10,61|436,90 | 92,8%|4,99|699,73 | 15,2%|15,08|1518,1 |
| LZO_1x_999 | 36,1%|4,68|1198,8 | 73,2%|8,44|348,51 | 95,8%|10,40|656,89 | 19,3%|24,35|1098,3 |
| LZHuffS | 35,6%|191,10|437,29 | 73,1%|92,81|211,28 | 94,6%|82,73|264,27 | 22,5%|253,61|590,40 |
| LZHuffL | 36,2%|186,35|414,21 | 73,9%|96,28|206,38 | 94,2%|88,29|270,32 | 21,0%|247,71|599,26 |
| ZIP1 | 29,0%|47,35|147,81 | 68,6%|22,78|85,67 | 90,8%|20,06|92,24 | 25,6%|62,90|169,15 |
| LZHuffS+ | 33,9%|16,00|484,70 | 69,1%|22,41|212,20 | 93,0%|29,35|258,18 | 17,1%|78,13|738,25 |
| LZHuffL+ | 33,3%|1,04|466,05 | 69,1%|6,39|203,87 | 90,3%|4,20|248,97 | 13,8%|11,34|841,39 |
| ZIP9 | 27,5%|4,44|162,48 | 65,9%|10,55|92,00 | 90,4%|15,39|96,25 | 19,1%|34,22|200,83 |
По результатам напрашивается еще один вывод: если текстуры в BC1 есть смысл сжимать, то для BC7 особого смысла делать это нет.
LZHuffS+ и LZHuffL+ демонстрируют неплохие показатели: средняя скорость декодирования ~432МБ/с, минимальная – 204МБ/с. И при этом выигрывают у LZO как в степени сжатия, так и в скорости сжатия (относится только к LZHuffS+, т.к. плата за 1МБ окно у LZHuffL+ весьма высока).
Таким образом у нас остаётся последний вопрос – CRC32 хеш результата декомпрессии. Алгоритмы LZHuffS и LZHuffL вполне позволяют встроить его рассчёт прямо в декомпрессор, остаётся только проверить эффективность такого шага.
| Алгоритм сжатия | С внешним расчётом хеша | С внутренним расчётом хеша |
| LZHuffS | 96,96% | 98,72% |
| LZHuffL | 96,91% | 98,80% |
| LZHuffS+ | 96,33% | 99,17% |
| LZHuffL+ | 96,13% | 99,53% |
Итог тут один – встроенному рассчёту хеша быть!