Сжатие и упаковка. hrum3.5, hrust1, hrust2, laser compact x.x.

[jerri]

Hrumer, не не Хруст это другое... А именно официальная версия. Чтобы с бесстековым форматом как в Hrust 2 и компактным распаковщиком меньше чем в MegaLZ

[Hrumer]

Hrumer, не не Хруст это другое... А именно официальная версия. Чтобы с бесстековым форматом как в Hrust 2 и компактным распаковщиком меньше чем в MegaLZ

Jerri, я тут взглянул на кодирование hrum и megalz. Последний более универсальный вроде бы. А у hrum формат как бы должен жать лучше плохопакуемые данные, а на включениях текста, графики он начинает проигрывать, так, не? Я протестил на mhmt несколько файлов, вроде megalz лучше сжимает, причем байтов на 100(Несколько байт-десятков байт можно отвести на то, что в hrum окно могло бы быть на 256 больше, всего то вставить надо команду типа DEC H). Или мне попались не те тестовые файлы?

[jerri]

Hrumer, Хрум лучше жмет код. Да. графику лучше жмет Хруст.
МегаЛЗ хз. я еще статистику не накопил.

[Hrumer]

jerri, Всё, до меня дошло. Посмотрел внимательно, как устроены депакеры у других. EXX нету. Как будто не для z80 писали. Формат hrum'а+увеличение dist на 256 (т.к. это ограничение фактически придуманное для скорости паковки)+депакер типа hrust2+пакер OLZH и своя ниша есть. Последние X байт явно ведь не надо хранить где нибудь, это же не модно сейчас.

[jerri]

Hrumer, ну последние байты это нужно только если чужой снапшот кусками сжимаешь.
А если свое что-то то тут до бита известно что где лежит

[Hrumer]

Если кому интересно, (типа похвалюсь!) почему сжатие было быстрым, и почему на некоторых файлах в режиме best тормозилось. Без заумных слов, одни схемы:

Файл:      |   Таблица зацикленная,
           |   Указывает на предыдущее
           |   вхождение символа:

#8000   A<----+   #0000
#8001   B     |   #0000
#8002   C     |   #0000
#8003   D     |   #0000
...           |
              |
#8010   A<--+ +-- #8000
#8011   E   | 
#8012   C   | 
...         |
            |
#8030   A   +---- #8010
#8031   F
#8032   D
... 

#8070   A   <--- Мы тут.
#8071   B
#8072   C


Таблица последних вхождений символов:

A	#8030
B       #8001
...
--------------------------

Всё ОК, но есть фейл на таких вот данных:

#8000   A<------+ #0000
#8001   A<----+ +-#8000
#8002   A<--+ +---#8001
#8003   A<+ +-----#8002
....      +---+
              |
#8010   A<-   +---#8003
#8011   A<-     <-#8010
#8012   A<--+   <-#8011
....        |
            |
#8030   A   +---- #8012
#8031   A         #8030
#8032   A         #8031
....

#8070   A   <--- Мы тут. Впереди печаль.
#8071   A
#8072   A

В пакере в режимах fast и good эти таблицы заполнялись частично, чтобы скорость не падала. В 95 году это типа было крута. Сейчас все проще - в свободном доступе много инфы, в т.ч. на русском. Например, кандидатская Кадача. Там много всего написано, читать в общем, интересно.

В хрусте2 поиск идет не по одному символу, а по символу и нескольким битам следующего символа.

Позже выложу схему, алгоритм, который без потери коэффициента сжатия решает вопрос по скорости с такими "рыхлыми" файлами.

[alone]

Почитал про нибблы Титуса, и пришла в голову новая идея.

Что если у нас есть ветка, которая вставляет L байтов (i=0..L-1) следующим образом:
mem[pointer+i] = mem[pointer+i-disp] xor <data[i]>
Где <data[i]> - только младшие N битов, причём N вычисляется так (вариация на тему DAKX):

N=curN[L]
Читаем из потока биты и считаем число единиц M - до первого нуля или пока N+M-1 < 8
N=N+M-1
curN[pointer mod disp]=N

Такое кодирование может оптимизировать много вызовов типа:
ld hl,nn
ld a,n
call nn

или развёрнутых лупов типа
add hl,bc
ld a,h
ld e,n
ld (de),a

В последнем случае L=disp.

[Titus]

mem[pointer+i] = mem[pointer+i-disp] xor <data[i]>
Где <data[i]> - только младшие N битов, причём N вычисляется так (вариация на тему DAKX):

Почему XOR, а не ADD?

[alone]

Потому что, например, между значениями 2 и 7 нужно ксорить всего 3 бита, а для сложения надо 3 бита и знак, т.е. 4 бита.

---------- Post added at 14:01 ---------- Previous post was at 14:00 ----------

Вообще интересно было бы послушать идеи, как в рамках этой концепции кодировать ксоры типа #80 (1 сдвинутый бит).

[Hrumer]

Я б тоже предпочел XOR. С одно стороны. С другой - бывают таблицы с увеличивающимися значениями. С третьей - надо же тестировать! И тут возникает вопрос на чем. Предлагаю в соседней ветке обсудить набор тестовых файлов, в т.ч. подброку игр, дем, текстов, графики, смешанных данных.

Но эта ветка о другом. А вы читали http://cbloomrants.blogspot.ru/2010/...ing-lzma.html? Вот этот кусок интересен:

ADDENDUM : here's an illustration of how the special LZMA modes help on structured data. Say you have a file of structs; the structs are 72 bytes long. Within each struct are a bunch of uint32, floats, stuff like that. Within something like a float, you will have a byte which is often very correlated, and some bytes that are near random. So we might have something like :


[00,00,40,00] [7F 00 3F 71] ... 72-8 bytes ... [00,00,40,00] [7E 00 4C 2F]
... history ... * start here

we will encode :

00,00,40,00 :
4 byte match at offset 72
(offset 72 is probably offset0 so this is a rep0 match)

7E :
delta literal
encode 7E ^ 7F = 1

00 :
one byte match to offset 72 (rep0)

4C :
delta literal
encode 4C ^ 3F = 0x73

2F :
regular literal

Also because of the position and state-based coding, if certain literals occur often in the same spot in the pattern, that will be captured very well.

Note that this is not really the "holy grail" of compression which is a compressor that figures out the state-structure of the data and uses that, but it is much closer than anything in the past. (eg. it doesn't actually figure out that the first dword of the structure is a float, and you could easily confuse it, if your struct was 73 bytes long for example, the positions would no longer work in simple bottom-bits cycles).

В хруст1, особенно в реализации mhmt подобного рода структурность сжимается кодом вида AxC(вставной байт). Надо бы просчитать закономерность, как изменяется вставной байт, если всего на 1-2бита, то можно выиграть.

А, формат hrum4 расписал. Ннадо сюда?
Это улучшенный hrum3.5:
Нет неиспользованных кодов.
Две переменных, передающихся от кодера к декодеру, для оптимизации дистанций и длин.