Идея такая - сжатие на байтовом уровне (хаффмана могу попозже приделать) - байт #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- окончательный формат для первой версии архиватора (в марте 2021 сделал описание более понятным):
Code: Select all
SHAFF header:
Bytes 0...5 - signature and version ("SHAFF0", "SHAFF1" or "SHAFF2")
Bytes 6,7 - offset to the 1st block of encoded data (big-endian)
Bytes 8,9 - number of 16K blocks (big-endian)
Bytes 10,11 - size of the last block (less or equal to 16384, also big-endian)
Then optional uncompressed auxilary data, for example in case of SNA-file:
Bytes 12...14 "SNA" - signature to identify SNA header
Bytes 15...41 - SNA 27-byte header itself
(for optional Huffman data in header after "HUF" signature see SHAFF2 description below)
Then sequence of encoded 16KB blocks in chosen format:
SHAFF0 data format:
1st byte sets a Key to use further instead of #FF (but usually it's #FF)
then any byte other than Key goes directly to output, but for Key see below
#FF 00000000 - single byte #FF, otherwise
#FF 0xxxxxxx LENGTH - distance 1..127 and LENGTH (see below)
#FF 10xxxxxx LENGTH - distance 128..190 and LENGTH (see below), but
#FF 10111111 LENGTH - reuses previous long distance -191 or longer
#FF 11xxxxxx xxxxxxxx LENGTH - directly encoded long negative distance, but
#FF 11000000 00000000 - end of block (with no length after)
where LENGTH encoded by 1 or 2 bytes:
1xxxxxxx - for 4..131
01xxxxxx - for 132..195
00xxxxxx xxxxxxxx - direcly encoded length for up to 16383
SHAFF1 data format:
0xxxxxxx - single byte #00...#7F
10xxxxxxx - single byte #80...#FF
110000 - repeat last single byte (no LENGTH after that)
110001 LENGTH - repeat last distance longer than -1 and not equal to previous
110010 LENGTH - repeat previous last distance longer than -1
110011 LENGTH - distance -1 (that basically means copy of the last byte LENGTH times)
1101xxxxxx LENGTH - distance from -2 (000000) to -65 (111111)
11100xxxxxxxx LENGTH - distance from -66 (00000000) to -321 (11111111)
11101xxxxxxxxxx LENGTH - distance from -322 (0000000000) to -1345 (1111111111)
1111xxxxxxxxxxxxxx LENGTH - distance up to -16383 (directly encoded with prefix 11)
special case without LENGTH:
111100000000000000 - end of block (after that last byte padded by zero bits)
and anything above 111111101010111110 is reserved!
LENGTH is a sequence of 2...26 bits that encode length of the copy:
0x - for 2 (encoded by 0) and 3 (encoded by 1)
10xx - for 4 (00), 5 (01), 6 (10), 7 (11)
110xxx - for 8...15 (000...111)
1110xxxx - for 16...31 (0000...1111)
11110xxxxx - for 32...63 (00000...11111)
111110xxxxxx - for 64...127 (000000...111111)
1111110xxxxxxx - for 128...255 (0000000...1111111)
11111110xxxxxxxx - for 256...511 (00000000...11111111)
111111110xxxxxxxxx - for 512...1023 (000000000...111111111)
1111111110xxxxxxxxxx - for 1024...2047 (0000000000...1111111111)
11111111110xxxxxxxxxxx - for 2048...4095 (00000000000...11111111111)
111111111110xxxxxxxxxxxx - for 4096...8191 (000000000000...111111111111)
1111111111110xxxxxxxxxxxxx - for 8192...16383 (0000000000000...1111111111111)
SHAFF2 data format:
00... \
01... - Huffman codes for literals
10... /
11... - Reference that encoded the same way as in SHAFF1 above
Optional Huffman table after "HUF" signature in header:
#FF N - start section with codes that have length N (1...254)
XX ... - code for byte XX (Huffman code starts with most significant bit)
#FF #00 ... - code for byte #FF
#FF #FF - end of HUF table
If "HUF" signature is not found in the header then it means depacker must use internal
Huffman table for English text in ASCII format. Other internal tables will also be
supported as HUF1 for Russian text in alternative DOS codepage, HUF2 for Russian text
in UTF-8 format with UNIX line ending and HUF3 for C/C++ source code also with UNIX line
ending.
https://gitlab.com/shaos/shaff
Code: Select all
SHAFF v1.2 (C) 2013,2017 A.A.Shabarshin <me@shaos.net>
Usage:
shaff [options] filename
Encoding options:
-0 to use SHAFF0 file format (by default)
-1 to use SHAFF1 file format
-2 to use SHAFF2 file format (experimental)
-b to compress blocks into separate files
-bN to compress only block N
-bN-M to compress blocks N..M
-lN to limit length of matches (default value is 4 for SHAFF0 and 2 for SHAFF1/2)
-xHH to set prefix byte other than FF (applicable only to SHAFF0 file format)
-e to set default table for English text (applicable only to SHAFF2 file format)
Decoding options:
-d to decode compressed SHAFF file to file
-c to decode compressed SHAFF file to screen
https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Storer%E2%80%93Szymanski
https://ru.wikipedia.org/wiki/LZSS (по русски)
P.P.P.P.P.P.S. Пока выложил EXE-шник последней версии 1.2 от 2017 года под винды, кому интересно: https://gitlab.com/shaos/shaff/-/tree/master/binaries/win32
