|
nedoPC.orgElectronics hobbyists community established in 2002 |
|
Author |
Message |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22821 Location: Silicon Valley
|
Перезалил сырцы - косячок небольшой пофиксил - с вероятностью 1/8 между блоками SHAFF1 записывался лишний байт из-за которого всё съезжало на больших файлах, теперь всё ок | | | | Code: 147,456 JRCARTS7.IMG - original 135,765 JRCARTS7.IMG.0pak - sequence of zeros coded as 00-nn 130,281 JRCARTS8.IMG - my 00-00-00 compression 112,745 JRCARTS7.IMGFF - my byte-oriented LZ77-like compression (SHAFF0) <<<<<<<<<<<<<<<<<<<<<< 111,526 JRCARTS7.IMGFF - my byte-oriented LZ77-like compression (SHAFF0 with option -x92) <<<<< 103,307 JRCARTS7.PP2 - RNC Pro Pack (method 2) 101,009 JRCARTS7.ZX7 100,180 JRCARTS7.IMG.hrm - Russian Hrum 99,974 JRCARTS7.IMG.mlz - Russian MegaLZ 98,045 JRCARTS7.IMGFF - my bit-oriented LZ77-like compression (SHAFF1) <<<<<<<<<<<<<<<<<<<<<< 98,006 JRCARTS7.LZH - created by LHA v2.13 80,016 JRCARTS7.IMG.bz2 79,098 JRCARTS7.LZ4 72,959 JRCARTS7.PP1 - RNC Pro Pack (method 1) 71,950 JRCARTS7.zip - modern ZIP from Debian 71,925 JRCARTS7.ARJ - created by ARJ v2.41a 71,865 JRCARTS7.AIN - another Russian archiver from 90s 71,855 JRCARTS7.ZIP - old PKZIP v2.06 71,808 JRCARTS7.IMG.gz 70,041 JRCARTS7.HA - HA 0.98 (Harri Hirvola) 67,437 JRCARTS7.IMG.hst - Russian Hrust 66,970 JRCARTS7.RAR - old RAR v1 65,765 JRCARTS7.RAR - modern RAR v5 62,543 JRCARTS7.7z - modern 7-zip 62,508 JRCARTS7.IMG.xz - modern LZMA2
| | | | |
|
07 Feb 2017 22:59 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22821 Location: Silicon Valley
|
Чото у меня задор почти на нет сошёл - надо побыстрее доделать SHAFF2 с Хаффманом пока маниакальная фаза совсем не разрядилась и не перешла в депрессивную P.S. А мне ведь ещё "бублик-доменные" декодеры писать для всяких ретро-процыков надо будет...
|
11 Feb 2017 14:56 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22821 Location: Silicon Valley
|
Сделал предопределённую таблицу Хаффмана для английского текста (за основу брал оригинал "Алисы в стране чудес"), добавив несколько спец-кодов, чтобы досовские текстовые файлы тоже обрабатывались - в результате получился массив 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 };
| | | | |
А вот обновлённые опции: Пока опция -2 (SHAFF2) без опции -e (английский текст) не работает... P.S. с "Алисой в стране чудес" и построенным под неё Хаффманом получилось вот так: P.P.S. Обновил сырцы на гитхабе - размер файла shaff.c теперь стал 1906 строк... P.P.P.S. Сишный исходник это не совсем английский текст, т.к. там часто встречаются символы, которых в обычном английском тексте крайне мало (как фигурные скобки, арифметические и логические операторы и т.д.), но тем не менее SHAFF2 таки его сильнее сжимает, чем SHAFF1, даже пользуясь Хаффманом для английского текста (опция -e), ожидаемо отставая от зипа
P.P.P.P.S. Нашёл косячок в табличке - неправильно были указаны коды для символов > и = теперь всё ок
|
12 Feb 2017 00:16 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22821 Location: Silicon Valley
|
В следующей версии 1.2 можно окончательно допилить формат SHAFF2 (чтобы генерил своего Хаффмана для каждого файла если не задана опция -e) ну и многопоточность присобачить ибо у меня 16КБ блоки сжимаются независимо друг от друга Возможные ассемблерные декодеры для трёх форматов: - Z80 (перемещаемый) - 8080 - 8086 - 6502 - PIC17 - NEDONAND Ну и на разных языках можно тоже для разнообразия - там бейсик ZX-спектрума, жаба, RW1 и т.д.
|
12 Feb 2017 11:03 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22821 Location: Silicon Valley
|
Опция -b сломана оказалось - исправил и заодно расширил: Теперь на очереди параллельная компрессия блоков на всех доступных корах
|
13 Feb 2017 21:14 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22821 Location: Silicon Valley
|
Автор пакера ZX7 Einar Saukas в начале 2021 года выпустил под BSD-лицензией суперпакер ZX0, который сделал всех https://github.com/einar-saukas/ZX0график изначально нарисован introspec/spke: но потом похоже дополнен автором LZSA - см. https://github.com/emmanuel-marty/lzsa, а потом снова дополнен introspec данными по ZX0
P.S. Кстати теперь у меня есть с чем сравнивать по скорости, когда буду писать свои депакеры под Z80 https://hype.retroscene.org/blog/dev/740.htmlP.P.S. Вот содержимое тестового набора файлов от introspec/spke под названием zxcorpus2017.7z: Теперь мне стало интересно, где на этой карте скоростей распаковки и степеней сжатия находится мой SHAFF P.P.P.S. Вот результат: Понятно, что SHAFF0 проигрывает всем, однако SHAFF1/2 обгоняет LZ4 и ZX7, но при этом видно, что по текстовым файлам (из которых по большей части состоят Calgary и Canterbury) SHAFF2 обгоняет Hrum, MegaLZ и даже частично ZX0 -q (ускоренный вариант ZX0 со сжатием похуже) - это потому что сейчас SHAFF2 содержит в себе таблицу Хаффмана для английского текста "Алиса в стране чудес" и в целом оно должно неплохо работать для любых англоязычных текстов, а вот бинари в SHAFF2 смогут подтянуться только когда я в SHAFF2 сделаю адаптивного Хаффмана (пока я цифры для бинарей скопировал из колонки SHAFF1, поэтому пометил серым). Теперь надо писать депакеры под Z80 и можно наносить свои звёздочки на вышеизложенную диаграмму Парето P.P.P.P.S. Нашёл тут случайно кладезь Z80 депакеров с замерами https://github.com/uniabis/z80depacker
|
13 Feb 2021 23:33 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22821 Location: Silicon Valley
|
Думаю добавить ещё предопределённую таблицу Хаффмана в формате SHAFF2 для русского текста в досовской кодировке (взяв за основу скажем документацию со Спринтера) - в этом случае нужна будет ещё одна опция по типу -e которая задаёт такую таблицу пакеру. Кроме того надо бы ещё в заголовке указывать какая таблица выбрана - вот у меня мысль возникла зареюзать ту же самую опцию -x которая пока используется как дополнительный (extra) параметр для формата SHAFF0 - скажем вместо -e указывать -xENG для английского текста в 7-битном формате ASCII и -xRUS для альтернативной кодировки русского языка с псевдографикой для доса. Для C/C++ без русских комментариев можно тоже рассчитать таблицу -xCPP и возможно надо будет ещё рассчитать таблицу для русского текста в UTF-8 и назвать её скажем -xRU2 Добавление в заголовок архива информации про предопределённую таблицу Хаффмана потребует пережатия всего что я успел экспериментально сжать в формате SHAFF2 т.к. там в заголовок ничего не добавлялось (либо считать по умолчанию, что используется таблица для английского текста в ASCII) - теперь в заголовке для SHAFF2 либо конкретная таблица Хаффмана будет ('H','U','F',0xFF...0xFF,0xFF), либо будет указан идентификатор предопределённой таблицы, например HUF/ENG для ENG или HUF/RUS для RUS и т.д. (ну или цифрами - без HUFn будет значить -xENG и далее HUF1 это -xRUS, HUF2 это -xRU2, HUF3 это -xCPP и т.д.). Более того, можно понаделать специализированных депакеров, которые будут распаковывать данные с конкретными таблицами и это будет работать быстрее, нежели универсальный SHAFF2 депакер, работающий с произвольными таблицами. P.S. Для SHAFF1 формата тоже можно экстра опцию -x поддержать, скажем -xINV которая будет означать инверсию входного потока перед сжатием - это может помочь, если количество несжатых литералов с кодом >= 128 в исходных данных больше, нежели с кодом < 128 (т.к. литералы с кодами больше 128 кодируются 9 битами, в то время как литералы с кодами меньше 128 кодируются 8 битами) - в zxcorpus2017 было несколько таких файлов. Факт инверсии можно указать путём добавления в заголовок сигнатуры "INV". В таком случае у нас получаются следующие вариации дополнительных данных в заголовке: SNA и далее 27 байт заголовка SNA (всего 30 байт - может встречаться во всех трёх форматах SHAFF0/1/2); HUF,0xFF.....0xFF,0xFF (объём данных может быть произвольным - останавливаемся когда встречены два FF-а подряд - может встречаться только в формате SHAFF2); HUFn где n это символ цифры '1','2','3' и т.д. (всего 4 байта - может встречаться только в формате SHAFF2); INV (3 байта - может встречаться только в формате SHAFF1). P.P.S. Для SHAFF0 можно реализовать автоматический поиск самого редкого байта вместо FF путём указания пустой экстра опции -x что может дать выигрышь в сжатии до 3% (например на графике из набора zxcorpus2017), причём программа сможет найти самый редкий байт для каждого 16кб блока и они могут быть разными для разных блоков, что также может помочь со сжатием. P.P.P.S. Формат .Z80 тоже можно попробовать поддержать (версию 2/3, где 16кб блоки отдельно друг от друга идут): https://worldofspectrum.org/faq/reference/z80format.htm
|
15 Feb 2021 23:36 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22821 Location: Silicon Valley
|
Ещё из потенциальных будущих расширений - возможность перепаковки из одного SHAFF-формата в другой SHAFF-формат - информация о закономерностях всё-равно уже собрана (правда с разной степенью детализации) - т.е. надо научить код эту информацию вытягивать из старого архива и переиспользовать при создании нового без поиска совпадений заново. А вообще в первую очередь надо доделать то, на чём я застрял в 2017 году - параллельное сжатие блоков одновременно на разных ядрах компьютера (такое правда будет возможно только в сборке под линукс, ну и может быть ещё под макось). Ещё можно добавить печать в человеческом виде таблиц Хаффмана (их ведь будет несколько встроенных). Можно также сделать внешнюю тулзу для подсчёта таблицы Хаффмана для экспериментов. А также добавить внешний отрезатель заголовка, который также будет делить файл на блоки для слабопроцессорных депакеров. Ешё размер окошка можно попробовать указывать, чтобы побыстрее паковало, а то щас окошком считается всё распакованное пространство в блоке вплоть до начала, т.е. 16 килобайт максимум. Ещё можно опицю -v добавить, которая после сжатия будет разжимать и сверять с оригинальным файлом, чтобы удостовериться, что всё сжалось и расжалось правильно. P.S. Пока выложил EXE-шник последней версии 1.2 от 2017 года под винды, кому интересно: https://gitlab.com/shaos/shaff/-/tree/master/binaries/win32
|
16 Feb 2021 22:05 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22821 Location: Silicon Valley
|
Написал прямо на Спринтере перемещаемый депакер на ассемблере Z80 для SHAFF0 (недокументированные команды не использовал, т.е. он и под Z180 должен собраться) - скорость декодирования последовательности непакуемых байтов будет 49 тактов на байт (это 2.33*LDIR) - если забить на перемещаемость, то можно ускорить до 47 тактов на байт (это 2.24*LDIR). Возможно когда начну тестить реальные данные, средняя скорость может получиться и получше (т.к. там LDIR используется при копировании повторяемых областей). Размер скомпилированного депакера вышел 104 байта (см. текст программы ниже). Сейчас надо написать какую-то тестилку, чтобы прогнать через этот депакер все zxcorpus2017 файлы и померять с точностью до такта сколько занимает распаковка, чтобы можно было свою жирную точку поставить на ту диаграмму Парето, что выше приведена... | | | | Code: ; SHAFF0 block depacker for Z80/Z180 written by Shaos on 28-MAR-2021 ; 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 this relocatable code is 104 bytes ; HL - address of packed data (data starts with a key byte) ; DE - pointer to the buffer where depacked data should appear (up to 16KB)
DESHAFF0: ld b,(hl) ; B is a Key byte (#FF in normal case) inc hl DSH0L: ld a,(hl) ; +7=7 ; main loop inc hl ; +6=13 cp b ; +4=17 ; compare with a Key jr z,DSH0FF ; +7=24 (the best case goes through) DSH0LL: ld (de),a ; +7=31 ; it was not a Key so decode byte as is inc de ; +6=37 jr DSH0L ; +12=49 (copying of unpacked data 2.33*LDIR) DSH0FF: ld a,(hl) ; read byte after Key inc hl or a ; check for 0 jr nz,DSH0F1 ld a,b ; it was 0 after a Key so decode it as Key value jr DSH0LL ; go back to the loop DSH0F1: ld c,a ; it was not 0 after a Key so store it and and #C0 ; check if it's 1-byte distance cp #C0 ; by comparing 2 most significant bits with 11 jr z,DSH0F2 ld a,c ; now check if distance is 191 (special case) cp #BF jr z,DSH0F3 ; go to special case handler push bc ; temporarily push Key to stack xor a ; clear A and flagC ld b,a ; here BC is a distance back (1..190) push hl ld h,a ; clear H ld l,a ; clear L sbc hl,bc ; calculate negative distance HL = 0 - BC ld b,h ld c,l ; now BC is a negative distance for 1-byte case pop hl jr DSH0LN ; go to read length DSH0F2: push bc ; temporary push Key to stack ld b,c ; it should be 2-byte distance, so this is higher byte ld c,(hl) ; read lower byte of the distance inc hl push bc ; now BC is a negative distance for 2-byte case pop iy ; store negative long distance to IY for future use ; check for end of the block ld a,b cp #C0 ; compare higher byte with #C0 jr nz,DSH0LN ; go to read length ld a,c or a ; compare lower byte with #00 jr nz,DSH0LN ; go to read length pop bc ; balance the stack before return ret DSH0F3: push bc ; temporary push Key to stack push iy ; retrieve stored distance pop bc ; now BC is a negative distance for special case DSH0LN: ld a,(hl) ; read length inc hl bit 7,a jr z,DSH0L1 ; 1xxxxxxx - Length 4..131 (0x80->4, 0x81->5 ... 0xFF->131) sub #7C DSH0L0: push de ; push DE temporarily ld d,0 ; higher byte of the length is 0 ld e,a ; lower byte of the length is taken from A jr DSH0L3 DSH0L1: bit 6,a jr z,DSH0L2 ; 01xxxxxx - Length 132..195 (0x40->132, 0x41->133 ... 0x7F->195) add a,#44 jr DSH0L0 DSH0L2: push de ; push DE temporarily ; 00xxxxxx xxxxxxxx - Length up to 16383 ld d,a ; higher byte of the length ld e,(hl) ; read lower byte of the length inc hl DSH0L3: ex (sp),hl ; exchange top of the stack (stored DE) with HL push de ; push length of the data ld d,h ld e,l ; now DE is current destination address add hl,bc ; now HL is an address of the reference pop bc ; now BC is length of the data to copy ldir ; perform copying of the data pop hl ; restore old source pop bc ; restore a Key jr DSH0L ; go back to main loop
| | | | |
P.S. В неперемещаемой версии например можно все JR adr заменить на JP adr, что увеличит длину кода, но ускорит скорость его работы т.к. JP $NN 10 3 C3 XX XX JR $N+2 12 2 18 XX также неперемещаемую версию можно сделать самомодифицирующейся, например вместо хранения ключевого байта (#FF) в регистре можно модифицировать его прямо в коде в паре мест: CP #FF что сэкономит такты которые я трачу на сохранение этого регистра в стеке в нескольких местах (также убрание этих лишних пушей и попов уменьшит длину программы) P.P.S. Проверил на сжатой основной части солидовского линкера LD, размер которого в развёрнутом виде составляет 12422 байта - в эмуляторе он разворачивался 601097 тактов, что даёт 48.39 тактов на байт (2.3*LDIR):
|
28 Mar 2021 21:07 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22821 Location: Silicon Valley
|
Сделал версию, которую можно собрать zmac-ом как неперемещаемую (надо установить RELO в 0) - кое что побыстрее там будет работать: | | | | Code: ; SHAFF0 block depacker for Z80/Z180 written by Shaos on 28-MAR-2021 ; Conditional compilation with or without relocatability added on 29-MAR-2021 ; See http://nedoPC.org/forum/ for more info about SHAFF packer ; This code is PUBLIC DOMAIN - use it on your own RISK!
RELO equ 1 ; set it to 0 to make non-relocatable faster code
; Size of relocatable code is 104 bytes with speed <=49t/byte (2.33*LDIR) ; Size of non-relocatable code is 119 bytes with speed <=47t/byte (2.24*LDIR) ; On real data non-relocatable code is about 4% faster than relocatable
; 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
; HL - address of packed data (data starts with a key byte) ; DE - pointer to the buffer where depacked data should appear (up to 16KB)
DESHAFF0: if RELO ld b,(hl) ; B is a Key byte (#FF in normal case) else ld a,(hl) ; Store a Key to the code in 2 places ld (DSH0LF+1),a ld (DSH0LG+1),a endif inc hl DSH0L: if RELO ld a,(hl) ; RELO +7=7 ; main loop inc hl ; RELO +6=13 cp b ; RELO +4=17 ; compare with a Key else DSH0LF: ld a,#FF ; NON-RELO +7=7 cp (hl) ; NON-RELO +7=14 endif jr z,DSH0FF ; RELO +7=24 NON-RELO +7=21 (the best case no jump) if RELO DSH0LL: ld (de),a ; RELO +7=31 ; it was not a Key so decode byte as is inc de ; RELO +6=37 jr DSH0L ; RELO +12=49 (copying of unpacked data 2.33*LDIR) else ldi ; NON-RELO +16=37 (de++)=(he++) bc-- (unused) jp DSH0L ; NON-RELO +10=47 (copying of unpacked data 2.24*LDIR) endif DSH0FF: if !RELO inc hl ; NON-RELO code requires HL to be incremented here endif ld a,(hl) ; read byte after Key inc hl or a ; check for 0 jr nz,DSH0F1 if RELO ld a,b ; it was 0 after a Key so decode it as Key value jr DSH0LL ; go back to the loop else DSH0LG: ld a,#FF ; it was 0 after a Key so decode it as Key value ld (de),a ; store Key itself inc de ; and increment destination pointer jp DSH0L ; then go back to the beginning of the loop endif DSH0F1: ld c,a ; it was not 0 after a Key so store it and and #C0 ; check if it's 1-byte distance cp #C0 ; by comparing 2 most significant bits with 11 jr z,DSH0F2 ld a,c ; now check if distance is 191 (special case) cp #BF jr z,DSH0F3 ; go to special case handler if RELO push bc ; temporarily push Key to stack endif xor a ; clear A and flagC ld b,a ; here BC is a distance back (1..190) push hl ld h,a ; clear H ld l,a ; clear L sbc hl,bc ; calculate negative distance HL = 0 - BC ld b,h ld c,l ; now BC is a negative distance for 1-byte case pop hl if RELO jr DSH0LN ; go to read length else jp DSH0LN ; go to read length faster endif DSH0F2: if RELO push bc ; temporary push Key to stack endif ld b,c ; it should be 2-byte distance, so this is higher byte ld c,(hl) ; read lower byte of the distance inc hl push bc ; now BC is a negative distance for 2-byte case pop iy ; store negative long distance to IY for future use ; check for end of the block ld a,b cp #C0 ; compare higher byte with #C0 jr nz,DSH0LN ; go to read length ld a,c or a ; compare lower byte with #00 jr nz,DSH0LN ; go to read length if RELO pop bc ; balance the stack before return endif ret DSH0F3: if RELO push bc ; temporary push Key to stack endif push iy ; retrieve stored distance pop bc ; now BC is a negative distance for special case DSH0LN: ld a,(hl) ; read length inc hl bit 7,a jr z,DSH0L1 ; 1xxxxxxx - Length 4..131 (0x80->4, 0x81->5 ... 0xFF->131) sub #7C DSH0L0: push de ; push DE temporarily ld d,0 ; higher byte of the length is 0 ld e,a ; lower byte of the length is taken from A if RELO jr DSH0L3 else jp DSH0L3 endif DSH0L1: bit 6,a jr z,DSH0L2 ; 01xxxxxx - Length 132..195 (0x40->132, 0x41->133 ... 0x7F->195) add a,#44 if RELO jr DSH0L0 else push de ; push DE temporarily ld d,0 ; higher byte of the length is 0 ld e,a ; lower byte of the length is taken from A jp DSH0L3 endif DSH0L2: push de ; push DE temporarily ; 00xxxxxx xxxxxxxx - Length up to 16383 ld d,a ; higher byte of the length ld e,(hl) ; read lower byte of the length inc hl DSH0L3: ex (sp),hl ; exchange top of the stack (stored DE) with HL push de ; push length of the data ld d,h ld e,l ; now DE is current destination address add hl,bc ; now HL is an address of the reference pop bc ; now BC is length of the data to copy ldir ; perform copying of the data pop hl ; restore old source if RELO pop bc ; restore a Key jr DSH0L ; go back to main loop else jp DSH0L ; go back to main loop faster endif
| | | | |
Размер неперемещаемой версии 119 байт и работает она примерно на 4% быстрее перемещаемой - 47 тактов на байт в основном цикле (2.44*LDIR) и на живых данных (основная часть солидовского LD для Z80) оно дало 46.45 тактов на байт (2.21*LDIR)
|
29 Mar 2021 21:20 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22821 Location: Silicon Valley
|
Я похоже знаю как сделать 1.62*LDIR в пределе Путём разворачивания главного цикла!...
|
29 Mar 2021 23:42 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22821 Location: Silicon Valley
|
Вот - главный цикл развёрнут в 21 макрос плюс LDIR для последовательностей длиннее 12 заменён на быструю фигню с 64 инструкциями LDI (спасибо Sayman). Турбо версия компилируетя в 398 байт, но зато имеет скорость распаковки в пределе 34.95 тактов на байт (1.66*LDIR) для непакованных данных и 39.06 тактов на байт (1.86*LDIR) для реального примера Z80 кода (основная часть солидовского LD, которая сжимается с 12422 байт до 8402 байтов). Также делал возможным собирать промежуточную по объёмам версию размером 241 байт, которая по скорости примерно на 1.5% хуже полной турбо-версии: | | | | Code: ; SHAFF0 block depacker for Z80/Z180 written by Shaos in March 2021 ; See http://nedoPC.org/forum/ for more info about SHAFF packer ; This code is PUBLIC DOMAIN - use it on your own RISK! ; History: ; 28-MAR-2021 - initial version with relocatable depacker only ; 29-MAR-2021 - conditional compilation for non-relocatable depacker added ; 30-MAR-2021 - conditional compilation for non-relocatable turbo depacker
TURBO equ 1 ; to make non-relocatable faster code TURBO2 equ 1 ; to switch to sequence of LDI instead of LDIR for sizes > 12
; How to build: zmac -m deshaff0.asm (after setting appropriate values above) ; Relocatable code is 104 bytes long with speed <=49t/byte (2.33*LDIR) ; Non-relocatable full turbo code is 398 bytes long with speed varying ; from 34.95t/byte (1.66*LDIR) for uncompressable data ; to 39.06t/byte (1.86*LDIR) for real life Z80 code block ; so turbo depacker might be about 29% faster than relocatable one ; if you disable TURBO2 the size goes down to 241 bytes with ~2% worse speed
; 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, 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
; Input: ; HL - address of packed data thar starts with a key byte (usually #FF) ; DE - pointer to the buffer where depacked data should appear (up to 16KB) ; Output: ; HL - address of the next byte after packed data ; DE - address of the next byte after unpacked data ; flag C - indicates an error (in this version it's always 0)
DESHAFF0: if !TURBO ld b,(hl) ; B is a Key byte (#FF in normal case) else ld a,(hl) ; Store a Key to the code in 2 places ld (DSH0L+2),a ld (DSH0LG+1),a endif inc hl DSH0L: if !TURBO ld a,(hl) ; RELO +7=7 ; main loop inc hl ; RELO +6=13 cp b ; RELO +4=17 ; compare with a Key jr z,DSH0FF ; RELO +7=24 (12 if jump) DSH0LL: ld (de),a ; RELO +7=31 ; it was not a Key so decode byte as is inc de ; RELO +6=37 jr DSH0L ; RELO +12=49 (copying of unpacked data 2.33*LDIR) else ld bc,-1 ; TURBO 10 (before) MLDI macro ld a,b ;+4=4 cp (hl) ;+7=11 jr z,DSH0FF ;+7=18 ldi ;+16=34 endm ; end of macro MLDI MLDI ; 1 MLDI ; 2 MLDI ; 3 MLDI ; 4 MLDI ; 5 MLDI ; 6 MLDI ; 7 MLDI ; 8 MLDI ; 9 MLDI ; 10 MLDI ; 11 MLDI ; 12 MLDI ; 13 MLDI ; 14 MLDI ; 15 MLDI ; 16 MLDI ; 17 MLDI ; 18 MLDI ; 19 MLDI ; 20 MLDI ; 21 jp DSH0L ; TURBO 10 (after) ; so it's 10+21*34+10=734 and 734/21=34.95t/byte (1.66*LDIR) endif DSH0FF: if TURBO inc hl ; TURBO code requires HL to be incremented here endif ld a,(hl) ; read byte after Key inc hl or a ; check for 0 jr nz,DSH0F1 if !TURBO ld a,b ; it was 0 after a Key so decode it as Key value jr DSH0LL ; go back to the loop else DSH0LG: ld a,#FF ; it was 0 after a Key so decode it as Key value ld (de),a ; store Key itself inc de ; and increment destination pointer jp DSH0L ; then go back to the beginning of the loop endif DSH0F1: ld c,a ; it was not 0 after a Key so store it and and #C0 ; check if it's 1-byte distance cp #C0 ; by comparing 2 most significant bits with 11 jr z,DSH0F2 ld a,c ; now check if distance is 191 (special case) cp #BF jr z,DSH0F3 ; go to special case handler if !TURBO push bc ; temporarily push Key to stack endif xor a ; clear A and flagC ld b,a ; here BC is a distance back (1..190) push hl ld h,a ; clear H ld l,a ; clear L sbc hl,bc ; calculate negative distance HL = 0 - BC ld b,h ld c,l ; now BC is a negative distance for 1-byte case pop hl if !TURBO jr DSH0LN ; go to read length else jp DSH0LN ; go to read length faster endif DSH0F2: if !TURBO push bc ; temporary push Key to stack endif ld b,c ; it should be 2-byte distance, so this is higher byte ld c,(hl) ; read lower byte of the distance inc hl push bc ; now BC is a negative distance for 2-byte case pop iy ; store negative long distance to IY for future use ; check for end of the block ld a,b cp #C0 ; compare higher byte with #C0 jr nz,DSH0LN ; go to read length ld a,c or a ; compare lower byte with #00 jr nz,DSH0LN ; go to read length if !TURBO pop bc ; balance the stack before return endif ret DSH0F3: if !TURBO push bc ; temporary push Key to stack endif push iy ; retrieve stored distance pop bc ; now BC is a negative distance for special case DSH0LN: ld a,(hl) ; read length inc hl bit 7,a if !TURBO jr z,DSH0L1 else if TURBO2 jp z,DSH0L1 else jr z,DSH0L1 endif endif ; 1xxxxxxx - Length 4..131 (0x80->4, 0x81->5 ... 0xFF->131) sub #7C DSH0L0: push de ; push DE temporarily ld d,0 ; higher byte of the length is 0 ld e,a ; lower byte of the length is taken from A if !TURBO jr DSH0L3 else if TURBO2 cp 12 jp c,DSH0L3 DSH0L3N: ex (sp),hl ; exchange top of the stack (stored DE) with HL push de ; push length of the data ld d,h ld e,l ; now DE is current destination address add hl,bc ; now HL is an address of the reference pop bc ; now BC is length of the data to copy xor a ; turbo LDIR starts here sub c and #3F add a,a ld (DSH0L3N1+1),a DSH0L3N1: jr nz,DSH0L3N2 DSH0L3N2: LDI8 macro ldi ; +16 ldi ; +16 ldi ; +16 ldi ; +16 ldi ; +16 ldi ; +16 ldi ; +16 ldi ; +16 endm ; end of macro LDI8 LDI8 ; 1 LDI8 ; 2 LDI8 ; 3 LDI8 ; 4 LDI8 ; 5 LDI8 ; 6 LDI8 ; 7 LDI8 ; 8 jp pe,DSH0L3N2 ; turbo LDIR ends here pop hl ; restore old source jp DSH0L ; go back to main loop else jp DSH0L3 endif endif DSH0L1: bit 6,a jr z,DSH0L2 ; 01xxxxxx - Length 132..195 (0x40->132, 0x41->133 ... 0x7F->195) add a,#44 if !TURBO jr DSH0L0 else push de ; push DE temporarily ld d,0 ; higher byte of the length is 0 ld e,a ; lower byte of the length is taken from A if TURBO2 jp DSH0L3N else jp DSH0L3 endif endif DSH0L2: push de ; push DE temporarily ; 00xxxxxx xxxxxxxx - Length up to 16383 ld d,a ; higher byte of the length ld e,(hl) ; read lower byte of the length inc hl if TURBO if TURBO2 jp DSH0L3N ; go to faster version in case of non-relocatable code endif endif DSH0L3: ex (sp),hl ; exchange top of the stack (stored DE) with HL push de ; push length of the data ld d,h ld e,l ; now DE is current destination address add hl,bc ; now HL is an address of the reference pop bc ; now BC is length of the data to copy ldir ; perform copying of the data pop hl ; restore old source if !TURBO pop bc ; restore a Key jr DSH0L ; go back to main loop else jp DSH0L ; go back to main loop faster endif
| | | | |
На реальном коде (основная часть LD) промежуточный вариант показывает 39.7-39.9 тактов на байт (1.90*LDIR), что чуть хуже full turbo версии, где получается 39.06 тактов на байт (1.86*LDIR)
|
30 Mar 2021 03:01 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22821 Location: Silicon Valley
|
Пока линейка скоростей для SHAFF0 на Z80 такая получается: 49t/byte (2.33*LDIR) - распаковка непакуемых данных перемещаемым депакером (104 байта) 48t/byte (2.30*LDIR) - распаковка LD перемещаемым депакером (104 байта) 40t/byte (1.89*LDIR) - распаковка LD турбо депакером (241 байт) 39t/byte (1.86*LDIR) - распаковка LD полнотурбированным депакером (398 байт) 35t/byte (1.66*LDIR) - распаковка непакуемых данных турбо депакерами (241 и 398 байтов) Что на представленной выше диаграмме Парето помещает SHAFF0 в пределы вот такого жёлтого прямоугольника (степень сжатия фиговая, но скорость распаковки стремится к LZ4): Более точно расположенные звёздочки для трёх депакеров SHAFF0 поставлю тогда, когда прогоню все файлы из zxcorpus2017.7z на эмуле и посчитаю такты P.S. А потом подойдёт черёд SHAFF1 - там должно быть всё несколько получше...
|
30 Mar 2021 20:19 |
|
|
Lavr
Supreme God
Joined: 21 Oct 2009 08:08 Posts: 7777 Location: Россия
|
Ты случаем не заканчивал каких либо курсов по экономике и "Управлению проектами"?
_________________ iLavr
|
31 Mar 2021 05:26 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22821 Location: Silicon Valley
|
Ну степень MBA от NYU я в 2018 таки получил
|
31 Mar 2021 10:28 |
|
|
Who is online |
Users browsing this forum: No registered users and 3 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
|
|