nedoPC.org

Electronics hobbyists community established in 2002
Atom Feed | View unanswered posts | View active topics It is currently 19 Mar 2024 02:31



Reply to topic  [ 117 posts ]  Go to page Previous  1 ... 4, 5, 6, 7, 8
Недоархиватор SHAFF 
Author Message
Supreme God
User avatar

Joined: 21 Oct 2009 08:08
Posts: 7777
Location: Россия
Reply with quote
Shaos wrote:
Lavr wrote:
Shaos wrote:
...на представленной выше диаграмме Парето ...
Ты случаем не заканчивал каких либо курсов по экономике и "Управлению проектами"? :wink:
Ну степень MBA от NYU я в 2018 таки получил :roll:

степень MBA - master of business administration ?

_________________
iLavr


31 Mar 2021 10:53
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Lavr wrote:
степень MBA - master of business administration ?

он самый :)

http://www.nedopc.org/forum/viewtopic.php?p=148959#p148959

_________________
:dj: https://mastodon.social/@Shaos


31 Mar 2021 11:24
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Надо начинать думать над реализацией Z80 депакера бит-ориентированного формата SHAFF1:
Code:
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)

Предположим у нас есть подпрограмма shabit, которая вытаскивает один бит из входного потока в виде флага C

Для разминки попробуем высчитать длину ссылки - для этого надо считать входящие единички и накапливать базовое значение (при 0 единичек оно будет 2, при 1 единичке - 4, при 2 единичках - 8 и т.д.):
Code:
  ld b,0
  ld hl,1
shacnt1:
  inc b
  add hl,hl
  call shabit
  jr c,shacnt1
После этого в HL будет содержаться базовое смещение, из входного потока уже будет вычитан нолик, который надо пропустить, а далее надо читать столько битиков, сколько было единичек плюс 1 (количество уже лежит в регистре B) и прибавить их к базовому значению:
Code:
   ld de,0
shalen1:
   call shabit
   rl e
   rl d
   djnz shalen1
   add hl,de
   ld b,h
   ld c,l
После этого в регистровой паре BC будет длина ссылки...

P.S. 4 мая 2021 года поправил код выше

_________________
:dj: https://mastodon.social/@Shaos


11 Apr 2021 02:05
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Попробуем набросать основной цикл чтения управляющих битиков - нам надо определить какое действие выполнять:
Code:
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)
Если мы вычитаем 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 - сразу уйти на вычитку байта
Code:
  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


P.P.S. 4 мая 2021 года поправил код выше

_________________
:dj: https://mastodon.social/@Shaos


11 Apr 2021 02:22
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
А вот подпрограмма вычитки бита из потока байтов и возвращение его в виде состояния флага C:
Code:
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
Подпрограмма сохраняет все регистры, которые потрогала (но не флаги)

_________________
:dj: https://mastodon.social/@Shaos


18 Apr 2021 21:47
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Сегодня поправил подпрограмму shabit в предыдущем сообщении - двигаюсь дальше...

_________________
:dj: https://mastodon.social/@Shaos


03 May 2021 22:12
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Shaos wrote:
Проверил на сжатой основной части солидовского линкера LD, размер которого в развёрнутом виде составляет 12422 байта...

Image

А вот и с депакером SHAFF1 проверил ;)

Attachment:
ld_Zpring1.gif
ld_Zpring1.gif [ 19.26 KiB | Viewed 8228 times ]

Контрольная сумма совпадает :)

Исходник (поправленный 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 - все кроме меня):

Attachment:
zxcorpus2017-Pareto-Sh0Sh1.gif
zxcorpus2017-Pareto-Sh0Sh1.gif [ 63.45 KiB | Viewed 8228 times ]

Место прямо скажем не очень красивое. Как я уже написал выше, надо всё перемерять с данными из ZXCORPUS, чтобы не сравнивать яблоки с апельсинами (хотя автор графика пишет, что в 2017 году скорость он мерял только по наборам "graphics" и "music", что странно, т.к. там ведь из спектрумовского есть ещё "mixedzx"). Также можно поработать по оптимизации депакера (как я поработал в случае SHAFF0), что сдвинет квадрат вправо. А в перспективе можно поработать над по настоящему оптимальным пакером, что может сдвинуть квадрат немного вверх (но большой выгоды от этого вряд ли можно получить). Ну и полноценно закончив SHAFF2, я могу сильно улучшить сжатие (т.к. добавится Хаффман), но скорость и размер депакера будут ещё хуже...

P.P.S. В случае LD кода разница между разными пакерами по степени сжатия следующая:
Code:
    -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-ы на этом тестовом наборе показывают несколько лучшие результаты, приближенные к другим пакерам:

Attachment:
zxcorpus2017new.jpg
zxcorpus2017new.jpg [ 171.07 KiB | Viewed 8241 times ]


Attachments:
zxcorpus2017.xls [16.5 KiB]
Downloaded 290 times

_________________
:dj: https://mastodon.social/@Shaos
04 May 2021 05:12
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Shaos wrote:
А вот подпрограмма вычитки бита из потока байтов и возвращение его в виде состояния флага C:
Code:
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
Подпрограмма сохраняет все регистры, которые потрогала (но не флаги)

Расставил такты у инструкций - получилось 114 в 7/8 случаях и 191 в 1/8 случаях или в среднем 126.25 тактов на бит.
Можно попробовать текущий указатель источника посадить в IX, а текущий счётчик битов в A' - удастся поди выциганить несколько тактов на чтении каждого бита?
Например:
Code:
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:
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
(57*7+69)/8=63 - дольше, чем в предыдущем случае.

Замена JR NZ на JP NZ также будет хуже:
Code:
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
(55*7+72)/8=57.125

Можно убрать джамп в конце первого варианта:
Code:
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 случаев
(52*7+74)/8=54.75 - выгадали 1.25 такта на бит - наверное не стоит за такими мелочами гнаться...

Если частично разворачивать вызов shabit и каждый call shabit (56+17=73) заменять на:
Code:
 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
то получится (55*7+79)/8=58 vs 73 - на 15 тактов быстрее (на 20%), хотя наверное это надо оставить для TURBO версии, т.к. размер кода вырастет существенно...

_________________
:dj: https://mastodon.social/@Shaos


04 May 2021 23:36
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Вот ускоренная версия - теперь на 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)

_________________
:dj: https://mastodon.social/@Shaos


05 May 2021 02:11
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Shaos wrote:
Сделал предопределённую таблицу Хаффмана для английского текста (за основу брал оригинал "Алисы в стране чудес"), добавив несколько спец-кодов, чтобы досовские текстовые файлы тоже обрабатывались - в результате получился массив 277 байт (под спойлером):
 Alice Huffman
Code:
unsigned char enghuf[] = {
/* === 4 bits === */ 0xFF,4,
/* 0x65 e 0001 */
   0x65,0x10,
/* === 5 bits === */ 0xFF,5,
/* 0x20   00000 */
   0x20,0x00,
/* 0x61 a 10111 */
   0x61,0xB8,
/* 0x73 s 10110 */
   0x73,0xB0,
/* 0x6F o 10100 */
   0x6F,0xA0,
/* 0x69 i 01111 */
   0x69,0x78,
/* 0x72 r 01110 */
   0x72,0x70,
/* 0x6E n 01011 */
   0x6E,0x58,
/* 0x74 t 01010 */
   0x74,0x50,
/* 0x6C l 01000 */
   0x6C,0x40,
/* 0x64 d 01100 */
   0x64,0x60,
/* === 6 bits === */ 0xFF,6,
/* 0x6D m 101010 */
   0x6D,0xA8,
/* 0x75 u 100111 */
   0x75,0x9C,
/* 0x70 p 100110 */
   0x70,0x98,
/* 0x2C , 100100 */
   0x2C,0x90,
/* 0x63 c 100010 */
   0x63,0x88,
/* 0x79 y 100001 */
   0x79,0x84,
/* 0x66 f 011011 */
   0x66,0x6C,
/* 0x77 w 011010 */
   0x77,0x68,
/* 0x67 g 010010 */
   0x67,0x48,
/* 0x68 h 001110 */
   0x68,0x38,
/* 0x22 " 001101 */
   0x22,0x34,
/* 0x62 b 001100 */
   0x62,0x30,
/* 0x2D - 001011 */
   0x2D,0x2C,
/* 0x0D   001001 */
   0x0D,0x24,
/* 0x0A   001000 */
   0x0A,0x20,
/* === 7 bits === */ 0xFF,7,
/* 0x6B k 1010110 */
   0x6B,0xAC,
/* 0x27 ' 1001010 */
   0x27,0x94,
/* 0x5F _ 1000111 */
   0x5F,0x8E,
/* 0x2E . 1000110 */
   0x2E,0x8C,
/* 0x49 I 1000001 */
   0x49,0x82,
/* 0x21 ! 0011110 */
   0x21,0x3C,
/* 0x76 v 0010100 */
   0x76,0x28,
/* 0x41 A 0000110 */
   0x41,0x0C,
/* 0x54 T 0000100 */
   0x54,0x08,
/* === 8 bits === */ 0xFF,8,
/* 0x3B ; 10101110 */
   0x3B,0xAE,
/* 0x3F ? 10010110 */
   0x3F,0x96,
/* 0x45 E 01001111 */
   0x45,0x4F,
/* 0x53 S 01001110 */
   0x53,0x4E,
/* 0x57 W 00111111 */
   0x57,0x3F,
/* 0x4E N 00101011 */
   0x4E,0x2B,
/* 0x44 D 00001111 */
   0x44,0x0F,
/* 0x4F O 00001110 */
   0x4F,0x0E,
/* 0x43 C 00001011 */
   0x43,0x0B,
/* 0x78 x 00001010 */
   0x78,0x0A,
/* === 9 bits === */ 0xFF,9,
/* 0x48 H 100101111 */
   0x48,0x97,0x80,
/* 0x52 R 100101110 */
   0x52,0x97,0x00,
/* 0x50 P 100000011 */
   0x50,0x81,0x80,
/* 0x46 F 100000010 */
   0x46,0x81,0x00,
/* 0x4D M 100000000 */
   0x4D,0x80,0x00,
/* 0x4C L 010011011 */
   0x4C,0x4D,0x80,
/* 0x3A : 010011010 */
   0x3A,0x4D,0x00,
/* 0x6A j 001111100 */
   0x6A,0x3E,0x00,
/* === 10 bits === */ 0xFF,10,
/* 0x7A z 1010111111 */
   0x7A,0xAF,0xC0,
/* 0x29 ) 1010111110 */
   0x29,0xAF,0x80,
/* 0x28 ( 1010111101 */
   0x28,0xAF,0x40,
/* 0x59 Y 1000000011 */
   0x59,0x80,0xC0,
/* 0x4B K 1000000010 */
   0x4B,0x80,0x80,
/* 0x56 V 0011111011 */
   0x56,0x3E,0xC0,
/* 0x42 B 0011111010 */
   0x42,0x3E,0x80,
/* 0x47 G 0010101011 */
   0x47,0x2A,0xC0,
/* 0x71 q 0010101001 */
   0x71,0x2A,0x40,
/* 0x55 U 0010101000 */
   0x55,0x2A,0x00,
/* === 11 bits === */ 0xFF,11,
/* 0x5D ] 10101111000 */
   0x5D,0xAF,0x00,
/* 0x5B [ 01001100101 */
   0x5B,0x4C,0xA0,
/* 0x51 Q 01001100100 */
   0x51,0x4C,0x80,
/* === 12 bits === */ 0xFF,12,
/* 0x4A J 101011110010 */
   0x4A,0xAF,0x20,
/* 0x09   101011110011 */
   0x09,0xAF,0x30,
/* === 13 bits === */ 0xFF,13,
/* 0x1A   0010101010110 */
   0x1A,0x2A,0xB0,
/* 0x1B   0010101010111 */
   0x1B,0x2A,0xB8,
/* 0x58 X 0010101010001 */
   0x58,0x2A,0x88,
/* 0x7E ~ 0010101010000 */
   0x7E,0x2A,0x80,
/* 0x24 $ 0010101010101 */
   0x24,0x2A,0xA8,
/* 0x23 # 0010101010100 */
   0x23,0x2A,0xA0,
/* 0x7D } 0010101010011 */
   0x7D,0x2A,0x98,
/* 0x7C | 0010101010010 */
   0x7C,0x2A,0x90,
/* 0x5E ^ 0100110011111 */
   0x5E,0x4C,0xF8,
/* 0x5C \ 0100110011110 */
   0x5C,0x4C,0xF0,
/* 0x7B { 0100110011101 */
   0x7B,0x4C,0xE8,
/* 0x60 ` 0100110011100 */
   0x60,0x4C,0xE0,
/* 0x3E > 0100110011011 */
   0x3E,0x4C,0xD8,
/* 0x3D = 0100110011010 */
   0x3D,0x4C,0xD0,
/* 0x5A Z 0100110011001 */
   0x5A,0x4C,0xC8,
/* 0x40 @ 0100110011000 */
   0x40,0x4C,0xC0,
/* 0x3C < 0100110001111 */
   0x3C,0x4C,0x78,
/* 0x2F / 0100110001110 */
   0x2F,0x4C,0x70,
/* 0x2B + 0100110001101 */
   0x2B,0x4C,0x68,
/* 0x2A * 0100110001100 */
   0x2A,0x4C,0x60,
/* 0x26 & 0100110001011 */
   0x26,0x4C,0x58,
/* 0x25 % 0100110001010 */
   0x25,0x4C,0x50,
/* 0x39 9 0100110001001 */
   0x39,0x4C,0x48,
/* 0x38 8 0100110001000 */
   0x38,0x4C,0x40,
/* 0x37 7 0100110000111 */
   0x37,0x4C,0x38,
/* 0x36 6 0100110000110 */
   0x36,0x4C,0x30,
/* 0x35 5 0100110000101 */
   0x35,0x4C,0x28,
/* 0x34 4 0100110000100 */
   0x34,0x4C,0x20,
/* 0x33 3 0100110000011 */
   0x33,0x4C,0x18,
/* 0x32 2 0100110000010 */
   0x32,0x4C,0x10,
/* 0x31 1 0100110000001 */
   0x31,0x4C,0x08,
/* 0x30 0 0100110000000 */
   0x30,0x4C,0x00,
/* === end of table === */ 0xFF,0xFF
};
Я прям так и планировал таблицу кодов Хаффмана хранить в файле, однако это похоже не сильно оптимально - например перейдя с побайтного представления в побитное можно легко сэкономить 42 байта, сделав эту таблицу 7-битных символов с кодами от 4 до 13 битов длиной размером 235 байтов вместо 277 (минус 15%)!

А так-то люди ещё сильнее извращаются - не сохраняют коды вовсе :o

Вместо этого они сохраняют дерево Хаффмана прямо как дерево и коды строятся программно по мере вычитывания этого дерева из файла - вроде бы именно так устроен JPEG

P.S. Это я реанимировал свой класс кодирования-декодированя по Хаффману, написанный мной (но недописанный) на C++ в 1996 году - начал прикручивать его к своему недожпегу WHI и призадумался - там у меня совсем плохо таблица сохраняется - надо переделывать...

P.P.S. А не - там всё более менее было. Просто сортировку лишнюю потребовалось выкинуть и всё :rotate:
Теперь там каждая запись в таблице Хаффмана тратит 4 бита на длину кода (это потеря от 10 до 80 байт в зависимости от длины таблицы) в дополнение к символу и его коду, а в варианте представления в SHAFF2 длина кода указывается для группы символов (т.е. каждая запись содержит только символ и его код с заранее известной длиной) и видимо пока пусть так и остаётся ибо как я писал в 2017 году:
Shaos wrote:
Планы на будущее:

SHAFF2 - формат с общей таблицей Хаффмана для литералов всего файла (формат ссылок остаётся таким же как в SHAFF1)

SHAFF3 - формат где у каждого 16КБ блока имеется своя таблица Хаффмана, включающая 1,2 и 3-символьные литералы, а также ссылки (этот формат должен побить всех самодельщиков : )

Кроме этого последний формат может стать полноценным архиватором, когда в один архив могут быть добавлены несколько файлов...
Вот в SHAFF3 и сделаю супер-компактное представление таблицы...

_________________
:dj: https://mastodon.social/@Shaos


05 Nov 2023 23:19
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Shaos wrote:
Я прям так и планировал таблицу кодов Хаффмана хранить в файле, однако это похоже не сильно оптимально - например перейдя с побайтного представления в побитное можно легко сэкономить 42 байта, сделав эту таблицу 7-битных символов с кодами от 4 до 13 битов длиной размером 235 байтов вместо 277 (минус 15%)!

А так-то люди ещё сильнее извращаются - не сохраняют коды вовсе :o

Вместо этого они сохраняют дерево Хаффмана прямо как дерево и коды строятся программно по мере вычитывания этого дерева из файла - вроде бы именно так устроен JPEG
Попробовал сохранить дерево Хаффмана для Алисы без кодов и получил 114 байт вместо 277 :o
т.е. выигрышь уже 163 байта или минус 59% (более чем в 2 раза даже по сравнению с вышеописанной побитной версией) :rotate:

Суть нового супер-компактного алгоритма такая - дерево Хаффмана рекурсивно расположено в последовательности битов где каждый блок:
- начинается с 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% т.е. уменьшение почти на треть)...

_________________
:dj: https://mastodon.social/@Shaos


06 Nov 2023 23:17
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22383
Location: Silicon Valley
Reply with quote
Добавил на гитлаб депакер SHAFF0 для 8080/8085:

https://gitlab.com/shaos/shaff/-/tree/master/depackers

Code:
; 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

В скомпилированном виде депакер весит 137 байт и он раскодирует непакуемые данные со скоростью 48 тактов на 1 байт (на 1 такт быстрее, чем для Z80), что равносильно простому копированию:

Code:
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

Пакуемые данные расжимаются чуть медленнее...

_________________
:dj: https://mastodon.social/@Shaos


28 Jan 2024 05:54
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 117 posts ]  Go to page Previous  1 ... 4, 5, 6, 7, 8

Who is online

Users browsing this forum: No registered users and 6 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.