Задумал я тут недоархиватор, чтобы декодер был поменьше чем MegaLZ, степень сжатия не хуже, ну и само-собой опенсорц

Идея такая - сжатие на байтовом уровне (хаффмана могу попозже приделать) - байт #FF является ключевым (поэтому SHAFF ; ), после него идёт смещение до копии и длина повторяющегося блока. Если смещение/длина в диапазоне от 1 до 254, то ставим один байт, если больше - то #00 и далее два байта (т.е. всего будет три). Получается команда, начинающаяся с #FF, может занимать от 3 до 7 байт. Если встречается отдельно стоящий байт #FF, то он раздваивается - #FF #FF, чтобы декодер не принял его за начало команды. Некоторые последовательности можно объявить командами, например: #FF #00 #00 #00 #01 (смещение в виде #00 #00 #00 никогда не попадётся) может обозначать маркер конца блока. Повторяющиеся байты описываются последовательностью, которая ссылается сама на себя - например 16 нулей могут быть закодированы так: #00 #FF #01 #0F (сначала отдельный байт #00 далее команда копирования по смещению -1 блока длиной 15 байт).
Архиватор работает с блоками 16К - чтобы охватить все возможные варианты повторений строим в памяти буфер 32Мб, в котором располагаем автокорреляционную матрицу с шагом от 1 до 16383. И далее "жадным" алгоритмом откусываем самые большие куски, пока не останутся только маленькие (3 и менее повторяющихся байт). Жмёт долго, но зато оптимально
P.S. Обновление от 7 октября 2013:Заголовок файла SHAFF может выглядеть примерно так:
0...5 "SHAFF1" - первые 6 байт сигнатура и версия
6,7 - смещение от начала файла до данных первого блока в сетевом формате (big-endian)
8,9 - количество блоков (тоже в сетевом формате)
10,11 - длина последнего блока (она может быть меньше 16K)
P.P.S. Обновление от 11 октября 2013:Например можно смещение после #FF представлять иначе:
- если смещение равно нулю (#00), то это команда, заменяющая один символ #FF;
- если старший бит 0, то смещение занимает 1 байт и может принимать значения от -1 до -127 (представляемые величинами от #01 до #7F);
- если старшие два бита 1 и 0, то смещение занимает 1 байт и может принимать значения от -128 до -191 (представляемые величинами от #80 до #BF);
- если старшие два бита 1 и 1, то смещение занимает 2 байта и может принимать значения от -192/#FF40 до -16383/#C001 (величины #C000 и #FF41...#FFFF не используются).
Далее идёт размер блока - на нём также можно сэкономить, т.к. размеров больше 16383 (#3FFF) быть не может:
- если старший бит 1, то размер занимает один байт и задаёт значения от 4 до 131 ( представляемые величинами от #80 до #FF или S+124 );
- если старшие два бита 0 и 1, то размер занимает 1 байт и задаёт значения от 132 до 195 ( представляемые величинами от #40 до #7F или S-68 );
- если старшие два бита 0 и 0, то размер занимает 2 байта и может принимать значения от 196/#00С4 до 16383/#3FFF (величины #0000...#00С3 не используются).
В результате без особых усилий мы уменьшили максимальную длину FF-команды до 5 байтов (1+2+2).
Последовательность вида #FF #С0 #00 может являться маркером конца блока, а в будущем ещё и #FF #FF [#41...#FF] можно будет задействовать для задания спец-команд...
P.P.P.S. Обновление от 23 октября 2013 - окончательный формат для первой версии архиватора (добавил комментариев в январе 2017):P.P.P.P.S. Исходники тут: https://github.com/shaos/shaff (к 8 февраля 2017 реализовал оба метода SHAFF0 и SHAFF1, а 12 февраля 2017 добавил экспериментальную поддержку SHAFF2)