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

[jerri]

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

[Advertiser]

[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?

[Hrumer]

Что если у нас есть ветка, которая вставляет 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.

Ты прям как Алекс Юстасу, сразу зашифровал и закодил

Я так понимаю, на примере:

Ранее встречалось:

00 11 56 92 34 CD

встретилось:

01 10 56 93 36 CD

Кодируем длину, дистанцию, колво бит, от 1 до.. ну, наверное, 4, и далее биты. В результате наложения этих бит по XOR с ранее встреченной строкой получаем текущую строку.

Верно?

---------- Post added at 11:59 ---------- Previous post was at 11:50 ----------

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

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

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

Добавить маску для битов в виде 1 байта. %10000000. Можно вот так даже:
%10101010. Типа, есть данные, где четные биты не меняются.

upd: при таком подходе в 1 байте уже есть инфа как о месте изменяющихся бит, так и о длине бит.

[alone]

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

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

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