Недоархиватор SHAFF

Shaos · Post by **Shaos** » 07 Feb 2017 22:59

Shaos wrote:Сделал запаковку-распаковку SHAFF1

Подбиваю статистику - как подобъю, выложу сырцы

P.S. Статистику см. выше - на более рандомных файлах чуть-чуть не догоняю MegaLZ и ZX7, но хрум часто обхожу, не говоря уже об LZ4

Перезалил сырцы - косячок небольшой пофиксил - с вероятностью 1/8 между блоками SHAFF1 записывался лишний байт из-за которого всё съезжало на больших файлах, теперь всё ок

Code: Select all

    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

Shaos · Post by **Shaos** » 11 Feb 2017 14:56

Чото у меня задор почти на нет сошёл - надо побыстрее доделать SHAFF2 с Хаффманом пока маниакальная фаза совсем не разрядилась и не перешла в депрессивную

P.S. А мне ведь ещё "бублик-доменные" декодеры писать для всяких ретро-процыков надо будет...

Shaos · Post by **Shaos** » 12 Feb 2017 00:16

Сделал предопределённую таблицу Хаффмана для английского текста (за основу брал оригинал "Алисы в стране чудес"), добавив несколько спец-кодов, чтобы досовские текстовые файлы тоже обрабатывались - в результате получился массив 277 байт (под спойлером):

Alice Huffman

Code: Select all

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
};

А вот обновлённые опции:

Code: Select all

SHAFF v1.1 (C) 2013,2017 A.A.Shabarshin <me@shaos.net>


Usage:
	shaff [options] filename

Encoding options:
	-0 to use SHAFF0 file format (by default)
	-1 to use SHAFF1 file format
	-2 to use SHAFF2 file format (experimental)
	-b to save blocks as separate files
	-lN to limit length of matches (default value is 4 for SHAFF0 and 2 for SHAFF1/2)
	-xHH to set prefix byte other than FF (applicable only to SHAFF0 file format)
	-e to set default table for English text (applicable only to SHAFF2 file format)

Decoding options:
	-d to decode compressed SHAFF file to file
	-c to decode compressed SHAFF file to screen

Пока опция -2 (SHAFF2) без опции -e (английский текст) не работает...

P.S. с "Алисой в стране чудес" и построенным под неё Хаффманом получилось вот так:

Code: Select all

 54342 alice.txt - оригинал
 36263 alice.SHAFF0 <<< shaff alice.txt (байтовый поток)
 27255 alice.SHAFF1 <<< shaff -1 alice.txt (битовый поток)
 26295 alice.ZX7
 25989 alice.PP2 (RNC Pro Pack method 2)
 25664 alice.LZ4
 24962 alice.txt.hrm
 24585 alice.txt.mlz
 24465 alice.SHAFF2 <<< shaff -2 -e alice.txt (битовый поток с Хаффманом для литералов по предопределённой таблице ENG)
 22947 alice.txt.hst
 22730 alice.ZX0 (добавлено 15 февраля 2021 года)
 21892 alice.PP1 (RNC Pro Pack method 1)
 21856 alice.lzh (LHA 2.13)
 20788 alice.zip
 20706 alice.txt.gz
 20385 alice.rar
 20213 alice.ha (HA 0.98)
 19352 alice.txt.xz
 17953 alice.EX2 (Exomizer 2.0.9)
 17514 alice.txt.bz2

P.P.S. Обновил сырцы на гитхабе - размер файла shaff.c теперь стал 1906 строк...

P.P.P.S. Сишный исходник это не совсем английский текст, т.к. там часто встречаются символы, которых в обычном английском тексте крайне мало (как фигурные скобки, арифметические и логические операторы и т.д.), но тем не менее SHAFF2 таки его сильнее сжимает, чем SHAFF1, даже пользуясь Хаффманом для английского текста (опция -e), ожидаемо отставая от зипа

Code: Select all

-rw-r--r-- 1 shaos shaos 46335 Feb 12 03:27 shaff.c - оригинальный файл (исходник shaff v1.1)
-rw-r--r-- 1 shaos shaos 16208 Feb 12 04:08 shaff.SHAFF0 <<< сжатие без опций
-rw-r--r-- 1 shaos shaos 12666 Feb 12 13:36 shaff.c.hrm
-rw-r--r-- 1 shaos shaos 12450 Feb 12 04:26 shaff.SHAFF1 <<< сжатие с опцией -1
-rw-r--r-- 1 shaos shaos 12373 Feb 12 13:36 shaff.c.mlz
-rw-r--r-- 1 shaos shaos 12262 Feb 12 13:56 shaff.SHAFF2 <<< сжатие с опциями -2 -e
-rw-r--r-- 1 shaos shaos 11541 Feb 12 13:36 shaff.c.hst
-rw-r--r-- 1 shaos shaos 10444 Feb 12 13:23 shaff.zip
-rw-r--r-- 1 shaos shaos 10434 Feb 12 03:27 shaff.c.gz
-rw-r--r-- 1 shaos shaos  9627 Feb 12 03:27 shaff.c.bz2
-rw-r--r-- 1 shaos shaos  9380 Feb 12 03:27 shaff.c.xz

P.P.P.P.S. Нашёл косячок в табличке - неправильно были указаны коды для символов > и = теперь всё ок
[/b]

Shaos · Post by **Shaos** » 12 Feb 2017 11:03

В следующей версии 1.2 можно окончательно допилить формат SHAFF2 (чтобы генерил своего Хаффмана для каждого файла если не задана опция -e) ну и многопоточность присобачить ибо у меня 16КБ блоки сжимаются независимо друг от друга

Возможные ассемблерные декодеры для трёх форматов:
- Z80 (перемещаемый)
- 8080
- 8086
- 6502
- PIC17
- NEDONAND

Ну и на разных языках можно тоже для разнообразия - там бейсик ZX-спектрума, жаба, RW1 и т.д.

Shaos · Post by **Shaos** » 13 Feb 2017 21:14

Shaos wrote:P.P.P.P.S. Нашёл косячок в табличке - неправильно были указаны коды для символов > и = теперь всё ок

Опция -b сломана оказалось - исправил и заодно расширил:

Code: Select all

SHAFF v1.2 (C) 2013,2017 A.A.Shabarshin <me@shaos.net>


Usage:
	shaff [options] filename

Encoding options:
	-0 to use SHAFF0 file format (by default)
	-1 to use SHAFF1 file format
	-2 to use SHAFF2 file format (experimental)
	-b to compress blocks into separate files
	-bN to compress only block N
	-bN-M to compress blocks N..M
	-lN to limit length of matches (default value is 4 for SHAFF0 and 2 for SHAFF1/2)
	-xHH to set prefix byte other than FF (applicable only to SHAFF0 file format)
	-e to set default table for English text (applicable only to SHAFF2 file format)

Decoding options:
	-d to decode compressed SHAFF file to file
	-c to decode compressed SHAFF file to screen

Теперь на очереди параллельная компрессия блоков на всех доступных корах

Shaos · Post by **Shaos** » 13 Feb 2021 23:33

Автор пакера ZX7 Einar Saukas в начале 2021 года выпустил под BSD-лицензией суперпакер ZX0, который сделал всех

https://github.com/einar-saukas/ZX0

pareto_20210128.png

график изначально нарисован introspec/spke:

introspec wrote:Исходя из этих соображений, я обработал данные выше, и объединил их с измерениями скорости распаковки, которые я привёл описывая распаковщики (хочу отметить, что скорость была измерена только на наборах данных «graphics» и «music»).

но потом похоже дополнен автором LZSA - см. https://github.com/emmanuel-marty/lzsa, а потом снова дополнен introspec данными по ZX0

P.S. Кстати теперь у меня есть с чем сравнивать по скорости, когда буду писать свои депакеры под Z80

https://hype.retroscene.org/blog/dev/740.html

P.P.S. Вот содержимое тестового набора файлов от introspec/spke под названием zxcorpus2017.7z:

Code: Select all

  Length      Date    Time    Name
---------  ---------- -----   ----
        0  2017-09-01 03:38   calgary/
    11954  1991-07-15 05:56   calgary/paper5
    49379  1991-07-15 05:57   calgary/progp
    13286  1991-07-15 05:56   calgary/paper4
    53161  1991-07-15 05:56   calgary/paper1
    38105  1991-07-15 05:56   calgary/paper6
    21504  1991-07-15 05:56   calgary/obj1
    39611  1991-07-15 05:57   calgary/progc
    46526  1991-07-15 05:56   calgary/paper3
        0  2017-09-01 03:38   mixedzx/
    53778  2009-09-04 11:47   mixedzx/prelimonty.tap
    33356  2012-11-09 11:56   mixedzx/pariboro.tap
    39000  2013-05-06 09:11   mixedzx/avalon.bin
    49152  2013-05-04 09:08   mixedzx/chronos.bin
    38948  2011-05-20 04:24   mixedzx/alterego.tzx
    33205  2000-02-21 11:21   mixedzx/manicminer.tzx
    61264  2007-09-07 19:26   mixedzx/bomb.tap
    47449  2012-01-29 11:24   mixedzx/glooptroop.tap
    41839  2006-09-13 13:20   mixedzx/rage.scl
    38953  2006-01-07 11:39   mixedzx/eyeache.scl
        0  2017-09-01 03:38   canterbury/
    24603  1996-06-12 08:44   canterbury/cp.html
     4227  1996-11-06 04:15   canterbury/xargs.1
    38240  1996-11-12 08:12   canterbury/sum
     3721  1996-09-26 09:16   canterbury/grammar.lsp
    11150  1996-09-26 07:02   canterbury/fields.c
        0  2021-02-14 03:44   graphics/
     6912  2017-08-23 08:24   graphics/vassa_gnezdo_(2016).scr
    19456  2017-08-23 07:27   graphics/bfox-dont_go_away_(2010).mg1
     6912  2017-08-23 08:15   graphics/diver_mercenary_4_(2014).scr
     6912  2017-08-23 07:27   graphics/slayer_stars_die_(2011).scr
     6912  2017-08-23 06:51   graphics/oleg_origin_saboteur_ii_(2015).scr
     6912  2017-08-23 07:26   graphics/prof4d_4th_dimension_(2002).scr
     6912  2017-08-23 07:27   graphics/darklight_when_i_sleep_i_see_demons_(2016).scr
    13824  2017-08-23 06:58   graphics/prof4d_fructus_(2015).img
     6912  2017-08-23 08:24   graphics/moroz1999_vyplivaya_(2017).scr
     6912  2017-08-23 08:27   graphics/r0bat_kotodrocherstvo_(2012).scr
     6912  2017-08-23 06:59   graphics/rion_unreal_(2003).scr
    12288  2017-08-23 07:28   graphics/agyagos_graphics-robin_(2000).mc
    13824  2017-08-23 08:27   graphics/riskej_sceners_gallery_(2008).img
    11136  2017-08-23 08:15   graphics/diver_mercenary_3_(2013).bsc
    18688  2017-08-23 07:07   graphics/r0m_dark_apprehensions_(2010).mg2
     6912  2017-08-23 08:41   graphics/mixer_strelka_(1997).scr
     6912  2017-08-23 07:28   graphics/karen_davies_firefly_(1988).scr
     6912  2017-08-23 08:35   graphics/m_stawicki_exolon_(1987).scr
     6912  2017-08-23 08:15   graphics/mac_phantis_(2014).scr
     6912  2017-08-23 08:38   graphics/jose_a_casarrubios_humphrey_bogart_(1989).scr
     6912  2017-08-23 06:58   graphics/dimidrol_bear_(2014).scr
    15616  2017-08-23 06:55   graphics/prof4d_fairy_(2011).mg4
     6912  2017-08-23 07:31   graphics/samanasuke_na_yug_poleteli_(2011).scr
     6912  2017-08-23 08:19   graphics/diver_underwood_(2002).scr
    13824  2017-08-23 06:53   graphics/pheel_stellar_contour_(2001).img
     6912  2017-08-23 06:53   graphics/mac_cauldron_ii_(2016).scr
    13831  2017-08-23 06:57   graphics/craig_stevenson-rewind_to_side_a_(2015).ch$
     6912  2017-08-23 07:28   graphics/dimidrol_good_morning_(2014).scr
    13824  2017-08-23 06:59   graphics/diver_tbk_logo_(2001).img
    12288  2017-08-23 08:24   graphics/piesiu_yoyo_bear_(2014).scr
        0  2017-09-01 03:38   music/
     3022  2017-08-23 07:10   music/imp_vibrations_outro_(1996).stc
     6344  2017-08-23 07:16   music/tdm_electric_city_(2002).sqt
     5755  2017-08-23 07:16   music/scratcher_trashe2_(1997).psc
     4710  2017-08-23 07:22   music/ksa_19_mng.w_(1996).stp
     4270  2017-08-23 07:11   music/d-juice_sentimental_motives_(1999).pt3
    10928  2017-08-23 07:15   music/frankt_carlos_michelis_theme_(2012).ay
     2368  2017-08-23 07:14   music/ziutek_shock7_(1992).stc
     7942  2017-08-23 07:16   music/4mat_bomb_(2007).pt3
     4453  2017-08-23 07:12   music/evolver_krytexho_(1996).stc
     7027  2017-08-23 07:14   music/special_erase_firefly_title_1_(1988).ay
    11147  2017-08-23 07:10   music/nq_synchronization_(2015).pt3
    10848  2017-08-23 07:24   music/keyjee_der_flaum_(2004).pt3
     2822  2017-08-23 07:11   music/mmcm_assured_(2000).pt3
     8333  2017-08-23 07:11   music/factor6_tailwind_(2016).pt3
     6186  2017-08-23 07:11   music/tim_follin_chronos_(1987).ay
    10048  2017-08-23 07:16   music/sairoos_inbetween_(2002).psc
     6430  2017-08-23 07:11   music/kenotron_voodoo_soundtrack_(2000).pt3
     4073  2017-08-23 07:11   music/karbofos_wat_is_luv_(2016).pt3
     3678  2017-08-23 07:16   music/siril_olia_iz_lukoila_(2001).pt3
     7892  2017-08-23 07:14   music/nq_recycler_(2012).pt3
     5339  2017-08-23 07:16   music/fatal_snipe_machined.pt2
     2811  2017-08-23 07:11   music/ben_daglish_dark_fusion_(1988).ay
     8425  2017-08-23 07:11   music/david_whittaker_savage_part_3_(1988).ay
     6806  2017-08-23 07:22   music/c-jeff_fatal_snipe-my_lalka_is_back_(2005).pt3
---------                     -------
  1233995                     82 files

Теперь мне стало интересно, где на этой карте скоростей распаковки и степеней сжатия находится мой SHAFF

introspec wrote:В четвёртой группе у меня снова только один распаковщик, LZ4. Это единственный байтовый пакер в обзоре. С учётом совершенно нереальной скорости распаковки — в среднем, около 34 тактов на распакованный байт, т.е. примерно 1.5*LDIR, видимо и нам на спектруме тоже есть смысл начать задумываться о компрессии, как способе повышения пропускной способности доступного нам железа. Только задумайтесь, LZ4 может распаковывать больше 2Кб данных за фрейм!

P.P.P.S. Вот результат:

zxcorpus2017.jpg

Понятно, что SHAFF0 проигрывает всем, однако SHAFF1/2 обгоняет LZ4 и ZX7, но при этом видно, что по текстовым файлам (из которых по большей части состоят Calgary и Canterbury) SHAFF2 обгоняет Hrum, MegaLZ и даже частично ZX0 -q (ускоренный вариант ZX0 со сжатием похуже) - это потому что сейчас SHAFF2 содержит в себе таблицу Хаффмана для английского текста "Алиса в стране чудес" и в целом оно должно неплохо работать для любых англоязычных текстов, а вот бинари в SHAFF2 смогут подтянуться только когда я в SHAFF2 сделаю адаптивного Хаффмана (пока я цифры для бинарей скопировал из колонки SHAFF1, поэтому пометил серым). Теперь надо писать депакеры под Z80 и можно наносить свои звёздочки на вышеизложенную диаграмму Парето

[/b]

P.P.P.P.S. Нашёл тут случайно кладезь Z80 депакеров с замерами https://github.com/uniabis/z80depacker

Shaos · Post by **Shaos** » 15 Feb 2021 23:36

Думаю добавить ещё предопределённую таблицу Хаффмана в формате SHAFF2 для русского текста в досовской кодировке (взяв за основу скажем документацию со Спринтера) - в этом случае нужна будет ещё одна опция по типу -e которая задаёт такую таблицу пакеру. Кроме того надо бы ещё в заголовке указывать какая таблица выбрана - вот у меня мысль возникла зареюзать ту же самую опцию -x которая пока используется как дополнительный (extra) параметр для формата SHAFF0 - скажем вместо -e указывать -xENG для английского текста в 7-битном формате ASCII и -xRUS для альтернативной кодировки русского языка с псевдографикой для доса. Для C/C++ без русских комментариев можно тоже рассчитать таблицу -xCPP и возможно надо будет ещё рассчитать таблицу для русского текста в UTF-8 и назвать её скажем -xRU2

Shaos wrote:А теперь по поводу добавления Хаффмана в SHAFF2 - думаю сделать общую таблицу на весь файл (все блоки) и записывать ее в заголовок (причем по умолчанию можно использовать встроенную заранее нагенеренную таблицу для английского технического текста). Например начало таблицы будет указывать трехбуквенный идентификатор HUF и далее:
#FF nn - где nn количество бит кода для символов следующих после такой команды (#FF #FF будет означать конец таблицы, т.е. таким способом можно задавать коды длиной до 254 битов)
после этого идут описатели кодов символов с указанной длиной:
cc hh...hh - где cc это байт символа (в случае #FF после него будет вставлен #00 чтобы отличить его от команды #FF nn) и далее необходимое количество байтов, кодирующих код Хаффмана для этого символа (код выдвинут влево до упора, т.е. например код 01 будет представлен байтом 01000000, а например код 111111111 будет представлен двумя байтами 11111111 10000000)
Думаю это будет самым компактным представлением кодов Хаффмана в виде байтов...

Добавление в заголовок архива информации про предопределённую таблицу Хаффмана потребует пережатия всего что я успел экспериментально сжать в формате 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

Shaos · Post by **Shaos** » 16 Feb 2021 22:05

Ещё из потенциальных будущих расширений - возможность перепаковки из одного SHAFF-формата в другой SHAFF-формат - информация о закономерностях всё-равно уже собрана (правда с разной степенью детализации) - т.е. надо научить код эту информацию вытягивать из старого архива и переиспользовать при создании нового без поиска совпадений заново. А вообще в первую очередь надо доделать то, на чём я застрял в 2017 году - параллельное сжатие блоков одновременно на разных ядрах компьютера (такое правда будет возможно только в сборке под линукс, ну и может быть ещё под макось). Ещё можно добавить печать в человеческом виде таблиц Хаффмана (их ведь будет несколько встроенных). Можно также сделать внешнюю тулзу для подсчёта таблицы Хаффмана для экспериментов. А также добавить внешний отрезатель заголовка, который также будет делить файл на блоки для слабопроцессорных депакеров. Ешё размер окошка можно попробовать указывать, чтобы побыстрее паковало, а то щас окошком считается всё распакованное пространство в блоке вплоть до начала, т.е. 16 килобайт максимум. Ещё можно опицю -v добавить, которая после сжатия будет разжимать и сверять с оригинальным файлом, чтобы удостовериться, что всё сжалось и расжалось правильно.

P.S. Пока выложил EXE-шник последней версии 1.2 от 2017 года под винды, кому интересно: https://gitlab.com/shaos/shaff/-/tree/master/binaries/win32

Shaos · Post by **Shaos** » 28 Mar 2021 21:07

Shaos wrote:Теперь мне стало интересно, где на этой карте скоростей распаковки и степеней сжатия находится мой SHAFF
introspec wrote:В четвёртой группе у меня снова только один распаковщик, LZ4. Это единственный байтовый пакер в обзоре. С учётом совершенно нереальной скорости распаковки — в среднем, около 34 тактов на распакованный байт, т.е. примерно 1.5*LDIR, видимо и нам на спектруме тоже есть смысл начать задумываться о компрессии, как способе повышения пропускной способности доступного нам железа. Только задумайтесь, LZ4 может распаковывать больше 2Кб данных за фрейм!

Написал прямо на Спринтере перемещаемый депакер на ассемблере Z80 для SHAFF0 (недокументированные команды не использовал, т.е. он и под Z180 должен собраться) - скорость декодирования последовательности непакуемых байтов будет 49 тактов на байт (это 2.33*LDIR) - если забить на перемещаемость, то можно ускорить до 47 тактов на байт (это 2.24*LDIR). Возможно когда начну тестить реальные данные, средняя скорость может получиться и получше (т.к. там LDIR используется при копировании повторяемых областей). Размер скомпилированного депакера вышел 104 байта (см. текст программы ниже). Сейчас надо написать какую-то тестилку, чтобы прогнать через этот депакер все zxcorpus2017 файлы и померять с точностью до такта сколько занимает распаковка, чтобы можно было свою жирную точку поставить на ту диаграмму Парето, что выше приведена...

Code: Select all

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

Shaos · Post by **Shaos** » 29 Mar 2021 21:20

Сделал версию, которую можно собрать zmac-ом как неперемещаемую (надо установить RELO в 0) - кое что побыстрее там будет работать:

Code: Select all

; 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)

Shaos · Post by **Shaos** » 29 Mar 2021 23:42

Я похоже знаю как сделать 1.62*LDIR в пределе

Путём разворачивания главного цикла!...

Shaos · Post by **Shaos** » 30 Mar 2021 03:01

Вот - главный цикл развёрнут в 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: Select all

; 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)

Shaos · Post by **Shaos** » 30 Mar 2021 20:19

Пока линейка скоростей для 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):

zxcorpus2017-Pareto-Sh0.gif

Более точно расположенные звёздочки для трёх депакеров SHAFF0 поставлю тогда, когда прогоню все файлы из zxcorpus2017.7z на эмуле и посчитаю такты

P.S. А потом подойдёт черёд SHAFF1 - там должно быть всё несколько получше...

Lavr · Post by **Lavr** » 31 Mar 2021 05:26

Shaos wrote:...на представленной выше диаграмме Парето ...

Ты случаем не заканчивал каких либо курсов по экономике и "Управлению проектами"?

Shaos · Post by **Shaos** » 31 Mar 2021 10:28

Lavr wrote:
Shaos wrote:...на представленной выше диаграмме Парето ...
Ты случаем не заканчивал каких либо курсов по экономике и "Управлению проектами"?

Ну степень MBA от NYU я в 2018 таки получил

Недоархиватор SHAFF

Re: Недоархиватор SHAFF

Re: Недоархиватор SHAFF

Re: Недоархиватор SHAFF

Re: Недоархиватор SHAFF

Re: Недоархиватор SHAFF

Re: Недоархиватор SHAFF

Re: Недоархиватор SHAFF

Re: Недоархиватор SHAFF

Re: Недоархиватор SHAFF

Re: Недоархиватор SHAFF

Re: Недоархиватор SHAFF

Re: Недоархиватор SHAFF

Re: Недоархиватор SHAFF

Re: Недоархиватор SHAFF

Re: Недоархиватор SHAFF