OberonCore

понадобилось мне тут быстропожать всякое, а zlib расчехлять неохота: жирный, страшный, лаяй. вспомнил про один свой старенький компрессор на си, портанул. благо, там кода-то…

чистейший LZ, выдаёт битовый поток, сжимает и разжимает строго из памяти в память. компрессору надо source_size*16 байт хипа и чуть более 4 кб стека, декомпрессору ничего кроме выходного буфера. размер распакованых данных для декомпрессора надо знать заранее, и буфер передавать соответствующего размера (это элементарно чинится, просто мне не надо).

чтобы вы понимали прелесть: размер компрессора около двухсот строчек (~6 кб исходника), декомпрессора около ста строчек (~3 кб исходника). они независимы, можно просто копипастить по месту. жмёт получше всяких lz4. параметры в компрессоре лучше не трогать: они методом ненаучной магии подобраны под более-менее производительность и compression ratio на разных наборах данных.

чисто по приколу: на level=normal тарбол "sqlite-autoconf-3360000.tar" у меня жмёт вот так:
packing 11,724,800 bytes...
packed: 3,383,942 in 6.505 seconds

а если вам очень хочется один раз пожать, но хорошо, то жмите с уровнем ultra, будет вот так:
packing 11,724,800 bytes...
packed: 2,800,464 in 397.077 seconds
это, кстати, лучше, чем gzip (ну ещё бы, со словарём в десять мегабайт-то, лол).

декомпрессору, натурально, плевать на уровни сжатия, он ничего дополнительно не требует.

p.s.: считайте, что код под WTFPL, как обычно.

Спасибо, штука полезная.

может и tiny inflate тогда оформить под mainline и выложить отдельно, а не в составе LC? 20 кб, распаковщик deflate-потоков, обычных и raw. у меня вон трудится, распаковывая пинги.

чисто ради интереса сделал эксперимент: уменьшил словарь до 64 кб, но впилил энтропийный кодек и пол-дюжины битовых моделей 9+ порядка. тарбол пожало за три секунды, гзип обошло на 100 кб.

публиковать не буду, потому что грязный эксперимент, код больше, и лень под mainline адаптировать. кому интересно — в личке попросите, но адаптировать сами будете. ;-)

краткое описание: битовый range coder (для алфавита из одного бита, внутренней разрядностью 32), 17-битовый предиктор (там механика чуть сложнее, ну да неважно), модель 256*256 предикторов для байта. по две байтовых модели на счётчик литералов, смещения и длины. памяти жрёт дополнительно несколько мегов, но энтропийный кодек того стоит. плюс в такой конфигурации это буквально десять строк кода для предиктора, и по десятку для encode и decode. делений не использует, только одно умножение (правда, LONGINT'а), и сдвиги.

недостаток в том, что декомпрессор тоже жрёт эти мегабайты, потому что ему, натурально, те же самые модели нужны. и медленней, само собой.

глубокого смысла эксперимент не имеет, но удержаться было сложно.

а если радикально уменьшить количество предсказателей, то дополнительной памяти надо 8 кб (плюс депакеру 128 кб на словарь), пакует не хуже, и депакер можно сделать потоковым. упс.