степень MBA - master of business administration ?Shaos wrote:Ну степень MBA от NYU я в 2018 таки получилLavr wrote:Ты случаем не заканчивал каких либо курсов по экономике и "Управлению проектами"?Shaos wrote:...на представленной выше диаграмме Парето ...
Недоархиватор SHAFF
Moderator: Shaos
-
Lavr
- Supreme God
- Posts: 16676
- Joined: 21 Oct 2009 08:08
- Location: Россия
Re: Недоархиватор SHAFF
iLavr
-
Shaos
- Admin
- Posts: 23989
- Joined: 08 Jan 2003 23:22
- Location: Silicon Valley
Re: Недоархиватор SHAFF
он самыйLavr wrote:степень MBA - master of business administration ?
viewtopic.php?p=148959#p148959
Я тут за главного - если что шлите мыло на me собака shaos точка net
-
Shaos
- Admin
- Posts: 23989
- Joined: 08 Jan 2003 23:22
- Location: Silicon Valley
Re: Недоархиватор SHAFF
Надо начинать думать над реализацией Z80 депакера бит-ориентированного формата SHAFF1:
Предположим у нас есть подпрограмма shabit, которая вытаскивает один бит из входного потока в виде флага C
Для разминки попробуем высчитать длину ссылки - для этого надо считать входящие единички и накапливать базовое значение (при 0 единичек оно будет 2, при 1 единичке - 4, при 2 единичках - 8 и т.д.):После этого в HL будет содержаться базовое смещение, из входного потока уже будет вычитан нолик, который надо пропустить, а далее надо читать столько битиков, сколько было единичек плюс 1 (количество уже лежит в регистре B) и прибавить их к базовому значению:
После этого в регистровой паре BC будет длина ссылки...
P.S. 4 мая 2021 года поправил код выше
Code: Select all
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)
Для разминки попробуем высчитать длину ссылки - для этого надо считать входящие единички и накапливать базовое значение (при 0 единичек оно будет 2, при 1 единичке - 4, при 2 единичках - 8 и т.д.):
Code: Select all
ld b,0
ld hl,1
shacnt1:
inc b
add hl,hl
call shabit
jr c,shacnt1
Code: Select all
ld de,0
shalen1:
call shabit
rl e
rl d
djnz shalen1
add hl,de
ld b,h
ld c,l
P.S. 4 мая 2021 года поправил код выше
Я тут за главного - если что шлите мыло на me собака shaos точка net
-
Shaos
- Admin
- Posts: 23989
- Joined: 08 Jan 2003 23:22
- Location: Silicon Valley
Re: Недоархиватор SHAFF
Попробуем набросать основной цикл чтения управляющих битиков - нам надо определить какое действие выполнять:
Если мы вычитаем 4 бита, то по их значению можно развести управление:
0000.0001,0010,0011,0100,0101,0110,0111 - дочитать к ним 4 бита и записать в выходной поток 1 байт с таким значением
1000 - дочитать 5 битов и записать 100xxxxx
1001 - дочитать 5 битов и записать 101xxxxx
1010 - дочитать 5 битов и записать 110xxxxx
1011 - дочитать 5 битов и записать 111xxxxx
1100 - дочитать ещё 2 бита и выполнить одну из 4 команд (см.выше)
1101 - вычитать 6 бит кодирующих дистанцию, вычесть их из -2 для получения смещения и затем пойти на вычитку длины (см.выше)
1110 - вычитать 1 бит и выполнить одну из 2 команд (см.выше)
1111 - вычитать 14 бит дистанции, использовать их как смещение (установив два старших бита в 11) и пойти на вычитку длины (см.выше)
P.S. На самом деле проще сначала вычитать 1 бит, и если он 0 - сразу уйти на вычитку байта
P.P.S. 4 мая 2021 года поправил код выше
Code: Select all
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)
0000.0001,0010,0011,0100,0101,0110,0111 - дочитать к ним 4 бита и записать в выходной поток 1 байт с таким значением
1000 - дочитать 5 битов и записать 100xxxxx
1001 - дочитать 5 битов и записать 101xxxxx
1010 - дочитать 5 битов и записать 110xxxxx
1011 - дочитать 5 битов и записать 111xxxxx
1100 - дочитать ещё 2 бита и выполнить одну из 4 команд (см.выше)
1101 - вычитать 6 бит кодирующих дистанцию, вычесть их из -2 для получения смещения и затем пойти на вычитку длины (см.выше)
1110 - вычитать 1 бит и выполнить одну из 2 команд (см.выше)
1111 - вычитать 14 бит дистанции, использовать их как смещение (установив два старших бита в 11) и пойти на вычитку длины (см.выше)
P.S. На самом деле проще сначала вычитать 1 бит, и если он 0 - сразу уйти на вычитку байта
Code: Select all
xor a
call shabit
jr nc,shabyte0
call shabit
rla
call shabit
rla
call shabit
rla
ld c,a
ld b,0
ld hl,jumps
add hl,bc
add hl,bc
ld e,(hl)
inc hl
ld d,(hl)
ex de,hl
jp (hl)
jumps dw sha1000,sha1001,sha1010,sha1011,sha1100,sha1101,sha1110,sha1111
sha1000:
ld a,4
jr shabyte1
sha1001:
ld a,5
jr shabyte1
sha1010:
ld a,6
jr shabyte1
sha1011:
ld a,7
jr shabyte1
shabyte0:
call shabit
rla
call shabit
rla
shabyte1:
call shabit
rla
call shabit
rla
call shabit
rla
call shabit
rla
call shabit
rla
; write literal A to output
Я тут за главного - если что шлите мыло на me собака shaos точка net
-
Shaos
- Admin
- Posts: 23989
- Joined: 08 Jan 2003 23:22
- Location: Silicon Valley
Re: Недоархиватор SHAFF
А вот подпрограмма вычитки бита из потока байтов и возвращение его в виде состояния флага C:
Подпрограмма сохраняет все регистры, которые потрогала (но не флаги)
Code: Select all
shabit:
push hl
push af
ld hl,curcount
dec (hl)
jr nz,shabit1
ld (hl),8
ld hl,(srcptr)
inc hl
ld a,(hl)
ld (curbyte),a
ld (srcptr),hl
shabit1:
ld hl,curbyte
rl (hl)
pop hl
ld a,h
pop hl
ret
srcptr dw curbyte
curcount db 9
curbyte db 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
Я тут за главного - если что шлите мыло на me собака shaos точка net
-
Shaos
- Admin
- Posts: 23989
- Joined: 08 Jan 2003 23:22
- Location: Silicon Valley
Re: Недоархиватор SHAFF
Сегодня поправил подпрограмму shabit в предыдущем сообщении - двигаюсь дальше...
Я тут за главного - если что шлите мыло на me собака shaos точка net
-
Shaos
- Admin
- Posts: 23989
- Joined: 08 Jan 2003 23:22
- Location: Silicon Valley
Re: Недоархиватор SHAFF
А вот и с депакером SHAFF1 проверилShaos wrote:Проверил на сжатой основной части солидовского линкера LD, размер которого в развёрнутом виде составляет 12422 байта...
Контрольная сумма совпадает
Исходник (поправленный 5 мая 2021 года занимает 334 байта в собранном виде):
https://gitlab.com/shaos/shaff/-/blob/master/depackers/z80/deshaff1.asm
(теперь на LD-примере оно даёт 470.5 тактов на байт или 22.4*LDIR)
P.S. Полученные результаты ставят SHAFF1 примерно вот в такое место (тем не менее надо всё перемерять с ZXCORPUS чтобы поставить правильные звёздочки т.к. например на LD степень сжатия у меня лучше, чем в ZX7 и близка к Hrum (см. ниже), но по графику это не так т.к. все остальные пакеры представлены по итогам работы с ZXCORPUS - все кроме меня):
Место прямо скажем не очень красивое. Как я уже написал выше, надо всё перемерять с данными из ZXCORPUS, чтобы не сравнивать яблоки с апельсинами (хотя автор графика пишет, что в 2017 году скорость он мерял только по наборам "graphics" и "music", что странно, т.к. там ведь из спектрумовского есть ещё "mixedzx"). Также можно поработать по оптимизации депакера (как я поработал в случае SHAFF0), что сдвинет квадрат вправо. А в перспективе можно поработать над по настоящему оптимальным пакером, что может сдвинуть квадрат немного вверх (но большой выгоды от этого вряд ли можно получить). Ну и полноценно закончив SHAFF2, я могу сильно улучшить сжатие (т.к. добавится Хаффман), но скорость и размер депакера будут ещё хуже...
P.P.S. В случае LD кода разница между разными пакерами по степени сжатия следующая:
Code: Select all
-rw-r--r-- 1 shaos shaos 12422 Mar 11 23:16 ld_.bin
-rw-r--r-- 1 shaos shaos 8418 Mar 11 23:40 ld_.SHAFF0
-rw-r--r-- 1 shaos shaos 8402 Mar 11 23:41 ld_.SHAFF0-xCF
-rw-r--r-- 1 shaos shaos 8261 Mar 11 23:16 ld_.bin.lz4
-rw-r--r-- 1 shaos shaos 7067 Mar 11 23:46 ld_.bin.zx7
-rw-r--r-- 1 shaos shaos 7036 Mar 11 23:43 ld_.SHAFF1
-rw-r--r-- 1 shaos shaos 7023 Mar 11 23:57 ld_1.lzh
-rw-r--r-- 1 shaos shaos 7002 Mar 11 23:38 ld_.bin.hrm
-rw-r--r-- 1 shaos shaos 6994 Mar 11 23:36 ld_.zip
-rw-r--r-- 1 shaos shaos 6982 Mar 11 23:38 ld_.bin.mlz
-rw-r--r-- 1 shaos shaos 6897 Mar 11 23:57 ld_5.lzh
-rw-r--r-- 1 shaos shaos 6877 May 4 03:11 ld_q.zx0
-rw-r--r-- 1 shaos shaos 6774 Mar 11 23:38 ld_.bin.hst
-rw-r--r-- 1 shaos shaos 6759 May 4 03:15 ld_.bin.EX2
-rw-r--r-- 1 shaos shaos 6703 Mar 11 23:46 ld_.bin.zx0
-rw-r--r-- 1 shaos shaos 6620 Mar 11 23:16 ld_.bin.xz
P.P.P.S. Всё таки коэффициент сжатия для графика автор брал из всего набора, а не только mus+gfx, как он писал в статье (возможно скорость бралась только по mus+gfx) - по идее SHAFF-ы на этом тестовом наборе показывают несколько лучшие результаты, приближенные к другим пакерам:
You do not have the required permissions to view the files attached to this post.
Я тут за главного - если что шлите мыло на me собака shaos точка net
-
Shaos
- Admin
- Posts: 23989
- Joined: 08 Jan 2003 23:22
- Location: Silicon Valley
Re: Недоархиватор SHAFF
Расставил такты у инструкций - получилось 114 в 7/8 случаях и 191 в 1/8 случаях или в среднем 126.25 тактов на бит.Shaos wrote:А вот подпрограмма вычитки бита из потока байтов и возвращение его в виде состояния флага C:Подпрограмма сохраняет все регистры, которые потрогала (но не флаги)Code: Select all
shabit: push hl ; +11=11 push af ; +11=22 ld hl,curcount ; +10=32 dec (hl) ; +11=43 jr nz,shabit1 ; +12/7=55 if jump, 50 if no jump ld (hl),8 ; +10=60 ld hl,(srcptr) ; +20=80 inc hl ; +6=86 ld a,(hl) ; +7=93 ld (curbyte),a ; +13=106 ld (srcptr),hl ; +16=132 shabit1: ld hl,curbyte ; +10=65 for 7 out of 8 cases, 142 for 1 out 8 cases rl (hl) ; +15=80 or 157 pop hl ; +10=90 or 167 ld a,h ; +4=94 or 171 pop hl ; +10=104 or 181 ret ; +10=114 or 191 srcptr dw curbyte curcount db 9 curbyte db 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
Можно попробовать текущий указатель источника посадить в IX, а текущий счётчик битов в A' - удастся поди выциганить несколько тактов на чтении каждого бита?
Например:
Code: Select all
shabit:
; push hl ненужен т.к. мы больше не используем HL
ex af,af' ; +4=4 заменяет push af и обращение к curcount
dec a ; +4=8
jr z,shabit0 ; +12/7=20/15 (надо сделать так, чтобы самый частый путь шёл по быстрому маршруту - без джампа
shabit1:
ex af,af' ; +4=19 для 7/8 случаев и 51 для 1/8 случаев
rl (ix+0) ; +23=42 или 74
ret ; +10=52 или 84 <<<<<<<<<<<<< (52*7+84)/8=56 больше чем в 2 раза быстрее получилось :)
shabit0:
ld a,8 ; +7=27
inc ix ; +10=37
jp shabit1 ; +10=47 (JP быстрее, чем JR)
Code: Select all
shabit:
ex af,af' ; +4=4 заменяет push af и обращение к curcount
dec a ; +4=8
jr nz,shabit1 ; +12/7=20/15
ld a,8 ; +7=22
inc ix ; +10=32
shabit1:
ex af,af' ; +4=24 для 7/8 случаев и 36 для 1/8 случаев
rl (ix+0) ; +23=47 или 59
ret ; +10=57 или 69
Замена JR NZ на JP NZ также будет хуже:
Code: Select all
shabit:
ex af,af' ; +4=4 заменяет push af и обращение к curcount
dec a ; +4=8
jp nz,shabit1 ; +10=18
ld a,8 ; +7=25
inc ix ; +10=35
shabit1:
ex af,af' ; +4=22 для 7/8 случаев и 39 для 1/8 случаев
rl (ix+0) ; +23=45 или 62
ret ; +10=55 или 72
Можно убрать джамп в конце первого варианта:
Code: Select all
shabit:
ex af,af' ; +4=4 заменяет push af и обращение к curcount
dec a ; +4=8
jr z,shabit0 ; +12/7=20/15 (надо сделать так, чтобы самый частый путь шёл по быстрому маршруту - без джампа
ex af,af' ; +4=19
rl (ix+0) ; +23=42
ret ; +10=52 в 7 из 8 случаев
shabit0:
ld a,8 ; +7=27
inc ix ; +10=37
ex af,af' ; +4=41
rl (ix+0) ; +23=64
ret ; +10=74 в 1 из 8 случаев
Если частично разворачивать вызов shabit и каждый call shabit (56+17=73) заменять на:
Code: Select all
ex af,af' ; +4=4
dec a ; +4=8
call z,shabit0 ; +17/10=> 18 для 7/8 или 25+27=52 для 1/8
ex af,af' ; +4=22 для 7/8 или 56 для 1/8
rl (ix+0) ; +23=55 для 7/8 или 79 для 1/8
....
shabit0:
ld a,8 ; +7=7
inc ix ; +10=17
ret ; +10=27
Я тут за главного - если что шлите мыло на me собака shaos точка net
-
Shaos
- Admin
- Posts: 23989
- Joined: 08 Jan 2003 23:22
- Location: Silicon Valley
Re: Недоархиватор SHAFF
Вот ускоренная версия - теперь на LD примере получается 470.5 тактов на байт, что есть 22.4*LDIR
P.S. Картинку выше поправил
P.P.S. Увеличив размер депакера удалось его ещё чуток ускорить:
https://gitlab.com/shaos/shaff/-/blob/master/depackers/z80/deshaff1.asm
Теперь оно распаковывает LD.SHAFF1 со скоростью 465 тактов на байт или 22*LDIR (размер после выкидывания лишнего - 337 байт)
(для сравнения - по набору данных zxmus+zxgfx MegaLZ и Hrust1 примерно в 3 раза быстрее, а ZX0 - почти в 10)
P.S. Картинку выше поправил
P.P.S. Увеличив размер депакера удалось его ещё чуток ускорить:
https://gitlab.com/shaos/shaff/-/blob/master/depackers/z80/deshaff1.asm
Теперь оно распаковывает LD.SHAFF1 со скоростью 465 тактов на байт или 22*LDIR (размер после выкидывания лишнего - 337 байт)
(для сравнения - по набору данных zxmus+zxgfx MegaLZ и Hrust1 примерно в 3 раза быстрее, а ZX0 - почти в 10)
Я тут за главного - если что шлите мыло на me собака shaos точка net
-
Shaos
- Admin
- Posts: 23989
- Joined: 08 Jan 2003 23:22
- Location: Silicon Valley
Re: Недоархиватор SHAFF
Я прям так и планировал таблицу кодов Хаффмана хранить в файле, однако это похоже не сильно оптимально - например перейдя с побайтного представления в побитное можно легко сэкономить 42 байта, сделав эту таблицу 7-битных символов с кодами от 4 до 13 битов длиной размером 235 байтов вместо 277 (минус 15%)!Shaos wrote:Сделал предопределённую таблицу Хаффмана для английского текста (за основу брал оригинал "Алисы в стране чудес"), добавив несколько спец-кодов, чтобы досовские текстовые файлы тоже обрабатывались - в результате получился массив 277 байт (под спойлером):Alice Huffman
А так-то люди ещё сильнее извращаются - не сохраняют коды вовсе
Вместо этого они сохраняют дерево Хаффмана прямо как дерево и коды строятся программно по мере вычитывания этого дерева из файла - вроде бы именно так устроен JPEG
P.S. Это я реанимировал свой класс кодирования-декодированя по Хаффману, написанный мной (но недописанный) на C++ в 1996 году - начал прикручивать его к своему недожпегу WHI и призадумался - там у меня совсем плохо таблица сохраняется - надо переделывать...
P.P.S. А не - там всё более менее было. Просто сортировку лишнюю потребовалось выкинуть и всё
Теперь там каждая запись в таблице Хаффмана тратит 4 бита на длину кода (это потеря от 10 до 80 байт в зависимости от длины таблицы) в дополнение к символу и его коду, а в варианте представления в SHAFF2 длина кода указывается для группы символов (т.е. каждая запись содержит только символ и его код с заранее известной длиной) и видимо пока пусть так и остаётся ибо как я писал в 2017 году:
Вот в SHAFF3 и сделаю супер-компактное представление таблицы...Shaos wrote:Планы на будущее:
SHAFF2 - формат с общей таблицей Хаффмана для литералов всего файла (формат ссылок остаётся таким же как в SHAFF1)
SHAFF3 - формат где у каждого 16КБ блока имеется своя таблица Хаффмана, включающая 1,2 и 3-символьные литералы, а также ссылки (этот формат должен побить всех самодельщиков : )
Кроме этого последний формат может стать полноценным архиватором, когда в один архив могут быть добавлены несколько файлов...
Я тут за главного - если что шлите мыло на me собака shaos точка net
-
Shaos
- Admin
- Posts: 23989
- Joined: 08 Jan 2003 23:22
- Location: Silicon Valley
Re: Недоархиватор SHAFF
Попробовал сохранить дерево Хаффмана для Алисы без кодов и получил 114 байт вместо 277Shaos wrote:Я прям так и планировал таблицу кодов Хаффмана хранить в файле, однако это похоже не сильно оптимально - например перейдя с побайтного представления в побитное можно легко сэкономить 42 байта, сделав эту таблицу 7-битных символов с кодами от 4 до 13 битов длиной размером 235 байтов вместо 277 (минус 15%)!
А так-то люди ещё сильнее извращаются - не сохраняют коды вовсе
Вместо этого они сохраняют дерево Хаффмана прямо как дерево и коды строятся программно по мере вычитывания этого дерева из файла - вроде бы именно так устроен JPEG
т.е. выигрышь уже 163 байта или минус 59% (более чем в 2 раза даже по сравнению с вышеописанной побитной версией)
Суть нового супер-компактного алгоритма такая - дерево Хаффмана рекурсивно расположено в последовательности битов где каждый блок:
- начинается с 1, если это разветвление - далее идут 2 блока: ветка для 1 и ветка для 0 на этом уровне;
- начинается с 0, если это литерал - далее идут N бит символа (в случае Алисы все символы имеют длину 7 бит).
Код символа вычисляется как путь к нему - на каждом разветвлении запоминается каким путём мы пошли (нулевым или единичным) и в момент выхода на символ это и будет его кодом.
P.S. Можно этот алгоритм в побайтовой плоскости тоже реализовать (для хранения в хедере SHAFF2 архивов):
- если вычитывается 0xFF, то далее идут 2 блока - для 1 и для 0;
- если вычитывается 0xFE, то это терминатор (в таблицах Хаффмана предназначенных для SHAFF2 будет один такой);
- если вычитывается что-то другое, то это литерал - символ у которого код вычисляется из пройденного к нему пути.
При таком подходе таблица ALICE умещается в 201 байт, что лучше вышеописанной побитной версии с сохранением кодов, но хуже побитной версии с сохранением дерева. Минусом такого подхода является необходимость задействовать 2 символа из алфавита под специальные нужды (либо мы должны знать заранее, что префикс 11 является недопустимым, чтобы явно не ставить терминатор - хотя с другой стороны неизвестно могут ли быть терминаторы при других раскладах) ну или считать, что за 0xFE надо вычитать следующий байт - если он 0xFE то это таки терминатор (если вдруг 0xFF, то это начало следующего блока и туда идти ненадо), а если любое другое значение M от 0x00 до 0xFD, то это литерал 0xFE+M (чтобы можно было представить 0xFE и 0xFF если они таки будут в алфавите ну и для расширения вплоть до 0xFE+0xFD=507).
P.P.S. Или даже ещё глубже - значения M от 0x00 до 0xF6 это коды 0xFE+M (вплоть до 500), а далее:
0xF7 означает вычитку третьего байта M2 для представления литералов с кодами 501+M2 (вплоть до 756),
0xF8 означает вычитку третьего байта M2 для представления литералов с кодами 757+M2 (вплоть до 1012),
0xF9 означает вычитку третьего байта M2 для представления литералов с кодами 1013+M2 (вплоть до 1268),
0xFA означает вычитку третьего байта M2 для представления литералов с кодами 1269+M2 (вплоть до 1524),
0xFB означает вычитку третьего байта M2 для представления литералов с кодами 1525+M2 (вплоть до 1780),
0xFC означает вычитку третьего байта M2 для представления литералов с кодами 1781+M2 (вплоть до 2036),
0xFD означает вычитку третьего байта M2 для представления литералов с кодами 2037+M2 (вплоть до 2292),
0xFE означает вычитку третьего байта M2 для представления литералов с кодами 2293+M2 (вплоть до 2548) либо мы тут оставляем место для будущих расширений,
а 0xFF в этой позиции будет означать начало нового блока (и если до этого был байт 0xFE, то это терминатор).
P.P.P.S. Ну ещё для пущего уплотнения первые несколько FF-ов можно заменить на один байт содержащий их количество - например в случае представления в таком виде таблицы ALICE вначале будет идти 5 FF-ов подряд и их можно заменить на один байт, содержащий 5, т.е. длина таблицы ещё уменьшится с 201 до 197 байт (минус 80 байт от первоначального варианта или -29% т.е. уменьшение почти на треть)...
Я тут за главного - если что шлите мыло на me собака shaos точка net
-
Shaos
- Admin
- Posts: 23989
- Joined: 08 Jan 2003 23:22
- Location: Silicon Valley
Re: Недоархиватор SHAFF
Добавил на гитлаб депакер SHAFF0 для 8080/8085:
https://gitlab.com/shaos/shaff/-/tree/master/depackers
В скомпилированном виде депакер весит 137 байт и он раскодирует непакуемые данные со скоростью 48 тактов на 1 байт (на 1 такт быстрее, чем для Z80), что равносильно простому копированию:
Пакуемые данные расжимаются чуть медленнее...
https://gitlab.com/shaos/shaff/-/tree/master/depackers
Code: Select all
; SHAFF0 block depacker for 8080/8085 written by Shaos on 27-JAN-2024
; See http://nedoPC.org/forum/ for more info about SHAFF packer
; This code is PUBLIC DOMAIN - use it on your own RISK!
; This depacker is doing decoding of a single data block with size <=16KB
; No SHAFF header is expected - it's already known that it's SHAFF0 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
; #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
; Size of assembled code is 137 bytes
; HL - address of packed data (data starts with a key byte)
; DE - pointer to the buffer where depacked data should appear (16KB max)
; Subroutine uses 2 bytes of memory as variable (DSH0D)
DESHAFF0:
mov b,m ; B is a Key byte (#FF in normal case)
inx h
DSH0L: mov a,m ; +7=7 ; main loop
inx h ; +5=12
cmp b ; +4=16 ; compare with a Key
jz DSH0FF ; +10=26
DSH0LL: stax d ; +7=33 ; it was not a Key so decode byte as is
inx d ; +5=38
jmp DSH0L ; +10=48 ; 1 byte of unpackable data takes 48 clock cycles
DSH0FF: mov a,m ; read byte after Key
inx h
ora a ; check for 0
jnz DSH0F1
mov a,b ; it was 0 after a Key so decode it as Key value
jmp DSH0LL ; go back to the loop
DSH0F1: mov c,a ; it was not 0 after a Key so store it and
ani 0C0H ; check if it's 1-byte distance
cpi 0C0H ; by comparing 2 most significant bits with 11
jz DSH0F2 ; go to handle 2-byte case
; 1-byte distance
mov a,c ; now check if distance is 191 (special case)
cpi 0BFH
jz DSH0F3 ; go to special case handler
push b ; temporarily push Key to stack
xra a ; clear A and flagC
; mov b,a ; here BC is a distance back (1..190)
; mov a,b ; invert B
cma
mov b,a
mov a,c ; invert C
cma
mov c,a
inx b ; make it two's complement negative number
jmp DSH0LN ; go to read length
; 2-byte distance
DSH0F2: push b ; temporary push Key to stack
mov b,c ; it should be 2-byte distance, so this is higher byte
mov c,m ; read lower byte of the distance
inx h
; now BC is a negative distance for 2-byte case - save it
mov a,c
sta DSH0D
mov a,b
sta DSH0DH
; check for end of the block
mov a,b
cpi 0C0H ; compare higher byte with #C0
jnz DSH0LN ; go to read length
mov a,c
ori 0 ; compare lower byte with #00
jnz DSH0LN ; go to read length
pop b ; balance the stack before return
ret
DSH0F3: push b ; temporary push Key to stack
; retrieve stored distance
lda DSH0D
mov c,a
lda DSH0DH
mov b,a
; now BC is a negative distance for special case
DSH0LN: mov a,m ; read length code from stream
add a ; check if bit 7 of length code was 1
jnc DSH0L1 ; if not go to next step
; 1xxxxxxx - Length 4..131 (0x80->4, 0x81->5 ... 0xFF->131)
mov a,m ; read length code from stream again
sui 7CH ; convert code to actual length
DSH0L0: inx h
push d ; temporarily push DE to stack
mvi d,0 ; higher byte of the length is 0
mov e,a ; lower byte of the length is taken from A
jmp DSH0L3
DSH0L1: add a ; check if bit 6 of length code was 1
jnc DSH0L2 ; if not go to next step
; 01xxxxxx - Length 132..195 (0x40->132, 0x41->133 ... 0x7F->195)
mov a,m ; read length code from stream again
adi 44H ; convert code to actual length
jmp DSH0L0
DSH0L2: push d ; temporarily push DE to stack
; 00xxxxxx xxxxxxxx - Length up to 16383
mov d,m ; read higher byte of the length from stream again
inx h
mov e,m ; read lower byte of the length from stream
inx h
DSH0L3: xthl ; exchange top of the stack (stored DE) with HL
push d ; push length of the data to stack
mov d,h
mov e,l ; now DE is current destination address
dad b ; now HL is address of the reference
pop b ; now BC is length of the data to copy
; perform copying of the data (as if it's LDIR)
DSH0L4: mov a,m
stax d
inx h
inx d
dcx b
mov a,c
ora b
jnz DSH0L4
pop h ; restore old source
pop b ; restore a Key
jmp DSH0L ; go back to main loop
DSH0D: db 0 ; lower byte of last used long distance
DSH0DH: db 0 ; higher byte of last used long distance
Code: Select all
loop:
mov a,m ; +7=7
stax d ; +7=14
inx h ; +5=19
inx d ; +5=24
dcx b ; +5=29
mov a,c ; +5=34
ora b ; +4=38
jnz loop ; +10=48
Я тут за главного - если что шлите мыло на me собака shaos точка net
