Сжатие данных

[ivagor]

Извините за оффтоп, но раз сказал A, то и следующую букву надо проговорить. Убрал тупизну из варианта 8086 (давно не брал я в руки шашки), стало на 23 байта короче и сильно быстрее. Критерием того, что этот вариант уже приемлемый считаю то, что он стал меньше компактного варианта для z80.

[ivagor]

Может возникнуть вопрос - зачем сделал свой вариант распаковщика upkr для 8088, если есть штатные?
1. Штатные используют команды 286 и 386, у меня только 8088/86.
2. Пресеты --x86 и --x86b на тех файлах, которые я попробовал, обеспечивают несколько худшее сжатие, чем --z80, но тут обобщать не берусь.
3. Мой вариант поддерживает и прямую и обратную распаковку.
У штатных есть и плюс - там можно без дополнительных телодвижений распаковать готовый .com, а не только абстрактные данные из одной области памяти в другую. Ну и признаюсь, что когда качал репозиторий upkr, там еще не было распаковщиков для x86 (когда выкладывал свой вариант они уже были, но я их не смотрел). Возможно если вовремя скачал бы образцовые распаковщики, то ограничился бы их адаптацией для 8088/86, зато теперь есть разнообразие вариантов.

[ivagor]

После появления zx0 я среди прочих "отменил" и exomizer, но должен признать, что был излишне категоричен. Пусть в среднем по больнице zx0 пожалуй все же выигрывает (особенно для sfx с учетом более компактного распаковщика), но нашлась ниша для exomizera - сжатие "мультимедийных" данных, графики и музыки, особенно при использовании для распаковки циклического буфера 256 байт. У zx0 быстрее падает эффективность при уменьшении размера буфера. Еще лучше подошел бы rip, но для него нет упаковщика с возможностью ограничения длины смещений. Ну а upkr несомненно лучше всех, но очень уж медленный. В порядке оффтопа - выложил на гитхаб deupkr для R800. Вот там он работает на приемлемой скорости, остается только позавидовать продвинутым msxникам.

[ivagor]

Удалось сократить deupkr для 8080 на 1-2 байта и чуть разогнать. И даже получилось сделать один микроскопический момент лучше чем в прототипе для z80.
Еще попробовал сделать небитстримные варианты - чуда не произошло, как и прогнозировал (или он просто попробовал) автор распаковщика для z80 они уступают битстримному. У меня создалось впечатление, что для их эффективной реализации нужны регистры по 24-32 бита и быстрое умножение 8x16 (или хотя бы 8x12), т.е. это не z80 и не 8080/88/86.

[ivagor]

Еще немного про upkr (потихоньку закругляюсь с этой темой, по крайней мере для 8080).
1. Сообразил, как оптимизировать версию с развернутым циклом умножения, стало на 3 байта короче и на 2% быстрее. Более того, оптимизация этого момента позволила ускорить и сократить на 2 байта оригинальную версию для z80, поэтому добавил на гитхаб и оптимизированный вариант для z80.
2. Единицы процентов - это хорошо, но мало, хотелось прорывов, поэтому попробовал умножение с большими таблицами. Оказалось, что в голый вектор влезает самый быстрый вариант с таблицей 6x8. Дальнейшее увеличение таблицы не ускоряет умножение, т.к. выигрыш съедают накладные расходы на работу с квазидиском. По 5 вариантам построил зависимость общего времени распаковки upkr8080 от времени умножения. Оказалось, что она (зависимость) очень хорошо аппроксимируется (MATLAB, polyfit, polyval) прямой линией. И по этой аппроксимации получается, что при сокращении времени умножения до 4-8 тактов общее время распаковки уменьшится примерно в 2 раза относительно самой медленной версии с умножением в цикле, вот такие пределы роста.

[ivagor]

Небольшое дополнение.
1. Если обозначить общее время распаковки y и время умножения x, то зависимость между ними y=x+const, т.к. const зависит только от содержания потока бит, который постоянен для одного файла и не зависит от времени умножения.
2. Хорошо, линейность зависимости очевидна, зачем нужна ползучая эмпирика с аппроксимацией, почему бы не посчитать x и const по тактам? Собственно x я и посчитал по тактам, для процедур умножения это возможно. Хотя внимательность нужна, т.к. большинство процедур умножения (в моей выборке все кроме одной) содержат условные переходы и нужно посчитать пути по всем веткам и усреднить, если нет заметных перекосов вероятностей сомножителей (судя по линейности полученной аппроксимации, я посчитал правильно, по крайней мере без серьезных ошибок). А вот const включает в себя слишком много условных переходов и циклов. За одним умножением, т.е. за одним декодированным битом может следовать запись одного литерала или накопление части литерала или копирование ссылки или декодирование длины ссылки или смещения, вариантов слишком много чтобы их все аккуратно и правильно посчитать. Проще и точнее определить y (общее время распаковки).

[ivagor]

Подбираю крошки за буржуинами. В оригинальной версии upkr для z80 есть такая штука

 archived: possible LUT variant of updating probs value, requires 512-aligned 512B table (not tested)
 ...
 table generator is not obvious and probably not short either, 20+ bytes almost for sure, maybe even 30-40

У меня генератор получился 30 байт. Это почти первая прикидочная версия, наверняка можно немного оптимизировать. Выигрыш от LUT для вектора примерно 2%. Малину портят две LUTые команды mov r,r по 8 тактов, для z80 и 8085 (да и для 8080 без торможения) эффект от LUT будет чуть больше.

[ivagor]

Итоговые распаковщики и небольшие комментарии будут потом, а пока демонстрация использования deupkr (самый компактный и медленный вариант) для распаковки картинок.
Две картинки 208x256 (16 цветов), на реале и в Emu80 такой размер выглядит как квадрат (оригинальные картинки квадратные). При конверсии использовал палитру наиболее близкую к Emu80, для VV тоже хорошо подходит, для Emu похуже. С палитрой v06x пока не разбирался, похоже она отличается и от Emu80/VV и от Emu. После старта распаковывается первая картинка и ждет нажатия РУС/ЛАТ. Потом вторая картинка (и тоже ждет РУС/ЛАТ). И так по кругу. Только upkr позволил уместить одновременно 2 картинки такого разрешения и цветности в памяти.
РУС/ЛАТ в эмуляторах:
Emu и VV - RCtrl
Emu80 - Insert
v06x - F6

[ivagor]

И небольшие комментарии.
В базовой версии удалось чуть ускорить вариант с развернутым умножением. Версию с таблицей квадратов разогнал на 3% и сократил на байт. Думаю примерно такие варианты и останутся. При желании можно наплодить промежуточных версий, которые по размеру и скорости будут между существующими, но не вижу в этом особого смысла.
Про обновление вероятностей с LUT (как раз пример одной из опций, которую можно реализовать). Несколько раз полностью переписал генератор таблицы, удалось его сократить до 23 байт и сильно ускорить (что неважно на фоне времени распаковки). А для z80 получается 21 байт, т.е. практически на нижней границе оценки автора распаковщика для z80 ("20+ bytes almost for sure"). Исходя из границ возможного это весьма хороший результат, но по критерию {ускорение/добавочный размер} не очень, разгон умножения более эффективен. Другое дело, что когда умножение уже разогнано до упора и хочется еще быстрее, тогда да. Если будут соревнования спортивных распаковщиков upkr, то можно туда добавить.
В целом повторю очевидную вещь: upkr - очень крутой упаковщик с очень медленной распаковкой. По сравнению со шринклером несомненный шаг в правильную сторону и по степени сжатия и по скорости и по размеру распаковщика, плюс еще и с полезными опциями упаковщика. Надеюсь все же в будущем появится что-то между rip и upkr.

[nzeemin]

ivagor, скажите, а вот эти новые алгоритмы если расположить на вот этом общем графе, где они примерно встанут?

https://github.com/emmanuel-marty/lz...reto_graph.png