Дикий ум - Компрессия: Фичи с эвристикой, Потоковая декомпрессия, Сжатие музыки (часть 2).

<b>Дикий ум</b> - Компрессия: Фичи с эвристикой, Потоковая декомпрессия, Сжатие музыки (часть 2).
  Компрессия - продолжение
Alone Coder

           8. Фичи с эвристикой
   В архиваторе  PAQ используются нейросе─
ти,причём он пакует не байты,а биты.Но всё
это  очень медленно и памяти требует под2
ГБ. Насколько я понимаю,нейросеть строится
и при  распаковке. Но  можно  использовать
нейросети  и эволюционные алгоритмы  и для
компрессоров  с  простыми  распаковщиками,
имеющими  дополнительные фичи. Например, в
Hrust1 расширение ссылки и вставка байта,в 
Laser Compact 4 копирование с переворотом. 

alone> архиватор durilca порвали! теперь 
лидер cmix (http://mattmahoney.net/dc/
text.html ). автор ссылается на книжку
http://mattmahoney.net/dc/dce.html
оказывается, сейчас в архиваторах делают
специальные методы для пережатия жпегов.
кто хочет написать архиватор и получить
приз?http://prize.hutter1.net/
рекорд держится уже 5 лет.
cmix uses a total of 1,723 independent
models. There are a variety of different
types of models,some specialized for cert─
ain types of data such as text, execut─
ables, or images. For each bit of input
data,each model outputs a single floating
point number, representing the probability
that the next bit of data will be a 1.cmix
uses a neural network to combine the model
predictions into a single probability.

hrumer> есть тема - при упаковке лаз. ком─ 
пактом можно выявлять непакованные байты, 
и если на них нет опоры, то заменять их 
при случае недавно встретившимися. 
Есть вероятность, что ЛК без перекодировки 
и с olzh может немного лучше жать игры с 
большим количеством графики. 
lvd>из-за каких фич? 
hrumer> Из-за перевернутости последовате─ 
льностей, возможно, более оптимально коди─ 
рованных. Эта тема с 2000 года в голове. 
alone> Не понял насчёт заменять. 
hrumer> Вот встретили АБ. Они не пакуются. 
На Б позже никто не ссылается.Поэтому мож─ 
но АБ заменять на АС,которое ранее недавно 
встретилось,и Б не сильно отличается от С. 
alone> Т.е. сжатие с потерями? 
hrumer> Ага. С потерями. Но с возможной 
корректировкой художником. 
alone> Помню, я в Gunfright вручную испра─ 
влял байты на картинке, чтобы лучше пако─
валась моим RLE )
hrumer> Ну вот, опыт одного человека есть) 
lvd>чото мне кажекцо, что переписывание 
игры с нуля, например, даст куда большую
экономию, чем смена пацкера )
hrumer> Я когда делал пакеры - одна из тем 
была в том, что берёшь, голову грузишь, 
чего надо придумать. А потом у меня есть 
минут 40 простой ходьбы, чтобы подумать и 
размышлять. Вот я бы хреновое что-нибуть 
придумал, если бы ранее машина была. 

hrumer> а ты чего отказался в одной из 
версий, если не ошибаюсь, рипа, от repeat 
distance? мало выгоды, а депакер пухнет? 
alone> да, я вообще выгоды не заметил. 
hrumer> может,пакер не оптимизил это дело? 
alone> можно оптимизить только с дополни─ 
тельным проходом.ZXRar 128K only.упакован─
ные данные налезают на пакуемые.и скользя─
щий словарь поэтому не делал. и окно 64К.

alone> смотрел про апроксимацию картинки 
кружочками? :)http://www.youtube.com/
watch?v=dOO5XcXLxGs
hrumer> Придумал совершенно новый редактор 
графики для спектрума! Картинка пакуется, 
потом показывается, где плохо пакуется. 
Художнику дается выбор, где подправить и 
на что, чтобы хорошо паковалось :) 

        9. Потоковая декомпрессия
   Сделать компрессор, рассчитанный на по─
токовое считывание упакованных данных. Та─
кой удобно применять при загрузке MOD-фай─
лов в General Sound и при проигрывании по─
токового видео.Сейчас для этих целей испо─
льзуется  обычно сжатие по одной страничке
или голый Хаффман ( ZXRar с окном0K и без
заголовка), распаковываемый вручную.
   Интерфейс  потокового распаковщика дол─
жен  позволять  распаковать  за один вызов
кусок  размером  порядка килобайта. Другой
вариант - сам  распаковщик  будет вызывать
программу пользователя с каждым полученным
байтом, это медленнее.

lvd>в пентеве прошивка фпга (в нгс, кста─ 
ти,тоже) распаковывается в кольцевой буфер
и кусочками грузится потом в фпга. в
пентеве - 100 кило распакованного размера.
hrumer> В хруст2.1 в хедере ещё CRC ) 
lvd>сколько бит? 
hrumer> 16. 
lvd>ccitt поди?http://srecord. 
sourceforge.net/crc16-ccitt.html
hrumer> Надо поверить. Может, и она. 
Может, нет. Исходники подсчёта есть. 
lvd>а как считается, табличкой 2х256 или 
побитно? или хитро побайтно без таблицы?
hrumer> 2 варианта было. Сначала табличка 
считается 512, а потом сумма. Или очень 
медленно без. Я тут глянул на хрум и 
мегалз. Братья-близнецы почти. Мегалз, 
похоже, чуток лучше жмёт из-за окна на 256 
большего.А я в своё время из-за кольцевого 
массива не стал заморачиваться. 
lvd>кольцевой массив можно из любого 
такого пакера сделать. по-моему, в мегалзе
лучше ссылки кодируются.
в мхмт можно окно задать в 4 кило ровно, и
сравнить. всё равно хрум проиграет )))
ну да, можно и таблицу считать.
но, по-моему, проще её заинкбинить сразу )
hrumer> Она не пакуется,сука такая ) В те─ 
кущей версии можно задать окно для мегалз? 
lvd>да, окно для всего можно задать. 
не токо для мегалза.например,для распаков─
щика в аврке окно 2к,потому что там памяти
ОЗУ всего 4к. да, я буквально недавно
заморачивался по работе генерацией црц в
разных позах. в т.ч.генерацией той таблицы
из полинома. ЧСХ один из элементов таблицы
и есть сам полином.
hrumer> Кольцевой массив - это для скорос─ 
ти упаковки на zx применялся. 8к+512. 
lvd>а, упаковки. а в чём скорость? 
hrumer> Ссылки на предыдущие вхождения си─ 
мвола. Если степень двойки, то красиво. А 
если чуток больше - то ясен пень, сразу 
надо больше в 2 раза. Правда, последняя 
ссылка может как раз указать за пределы 
окна, и это можно было использовать для 
увеличения окна на 256. 

hrumer> интересно бы взглянуть на демегалз 
с кольцевым буфером. Есть идейка одна,надо 
проверить. 
lvd>http://svn.zxevo.ru/filedetails.php? 
repname=ngs&path=%2Fz80%2FbootFPGAOO
%2FbootFPGA.asm- раз (DECЧObuf)
http://svn.zxevo.ru/filedetails.php?
repname=pentevo&path=%2Favr%2Fcurrent%2Fde
packer_dirty.cдва (ещё такой же файл .h)
http://svn.zxevo.ru/filedetails.php?
repname=pentevo&path=%2Favrboot%2Ftrunk%2F
avr%2Fboot_evo.asmтри
(примерно с метки PUTB1, писал DDp)
hrumer> по кольцевому буферу подумалось, 
что если пакер не будет делать кодирования 
строки на краях кольцевого буфера,то можно 
не заморачиваясь делать LDIR. 
lvd>эффективность пакинга упадёт же. 
hrumer> на 1-2 байта всего (для длины 
буфера), в худшем случае. 
lvd>1-2 байта на каждый край кольцевого 
буфера.
hrumer> вероятность ~1%. можно тестануть, 
поставив цену = бесконечность при переходе 
фразы по месту n*window. Хотя, нафиг надо, 
если скорости депакера достаточно ) 

alone> надо выход распаковщика стравить 
другой процедуре, а памяти чтобы юзало
только 4к.мультики про кота видел?например
https://zxaaa.net/view_demo.php?id=8593
lvd>официально заявляю, что впервые 
демегалз с буфером-окном изобрёл я.
в далёком 2005 году (+-1), написав депакер
прошивки для фпга в нгсе.http://
svn.zxevo.ru/filedetails.php?repname=ngs&
path=%2Fz80%2FbootFPGAOO%2FbootFPGA.asm
по-моему, принцип и так очевиден. если не
очевиден, см. сорец на цэ.
alone> он целиком окно прожёвывает? 
lvd>да. депакует 8 кило потом, идёт эти 8 
кило жрать.
alone> надо, значит, фиксить. 
lvd>фиксь, принцип от этого не изменится. 
там всего 2 места,где фиксить: LDI и LDIR.
alone> благодарствую.у меня в видевах тупо 
Хаффманом пожато. ZXRar с окном 0.
lvd>вот оно, преимущество тупоокных 
пакеров по сравнению с умными словарными
рарами и зюпами.
alone> это смотря что паковать. 
lvd>если буфер сделаешь в F000..FFFF, то 
фиксить можно прощё.OR H,#F0.даже set 4,h.
alone> я когда паковал году в 2002 нарезки 
из фильма,у меня были ссылки назад на рас─
пакованные знакоместа.но когда сделал ста─
ндартные знакоместа, выигрыш был огромный.

DDp> 
   Атрибутная агрессия (v2)http://dlcorp.
nedopc.com/viewtopic.php?p=30304#p30304
  2970 кадров, 25 FPS.
   Все кадры в виде дампа спектрумовских
атрибутов(768 байт) друг за другом в виде
одного потока упакованы алгоритмом MegaLZ.
   Проигрывание: в основном цикле распако─
вываются в циклический буфер8 КБ (с небо─
льшим запасом,вроде бы,4 кадра).В прерыва─
нии очередной кадр LDIR-ится на экран.

   ASCII-мультик   "Звёздные   войны"  для
"Апогея"http://zx-pk.ru/showpost.php? 
p=714968&postcount=3
   Размер кадра67x13=871 символ (экранный
буфер "Апогея" 78x30).Плавающий фреймрейт,
индивидуальная  продолжительность для каж─
дого  кадра. В исходном  мультике замещены
символы, отсутствующие  в  "Апогее". Итого
используются64 символа (0x20...Ox5f).
   1 уровень:
00...3f - символ (+0x20)
40...7b - повтор предыдущего (1...60 раз)
7c      - scroll up (сдвинуть весь кадр)
7d      - scroll left
7e      - scroll right
7f      - очистить весь кадр
80...ff - пропуск (1...128 знакомест)
   Номера  кадров  со  скроллами  забиты в
упаковщик как  константы (нет определятора
движения).
   2  уровень: полученный  поток  упакован
алгоритмом MegaLZ с размером окна4 КБ.
   Проигрывание: распаковщик  MegaLZ испо─
льзует циклический буфер4 КБ. Распакован─
ные байты передаются на 1 уровень, который
обновляет экранный буфер.

   Серия мультиков "Simon's Cat"
  256x192  точек, 12.5  FPS (в  некоторых
снижено до10 или ниже)
   1 уровень: экран  делится на знакоместа
8x8 точек. Сохраняются только изменившиеся
знакоместа.
00      - очистить весь кадр
01...1f - далее идут данные для знакомест
          (1...31 шт.)
20      - кадр без изменений
21...ff - пропуск знакомест (1...223 шт.)
   2  уровень: полученный  поток  упакован
алгоритмом MegaLZ с размером окна4 КБ.
   Проигрывание: распаковщик  MegaLZ испо─
льзует циклический буфер4 КБ. Распакован─
ные байты передаются на 1 уровень, который
обновляет экранный буфер.

      10. Ускорение нативного пакера
   LZ  при  обычном  хэшировании даёт ско─
рость упаковки от силы1 КБ/с  на 3.5 MHz.
Можно  ускорить  улучшением хэша, чтобы он
распределился более равномерно (причём хэ─
шировать  только по3 символам, по 2 особо
не  улучшить - для таких ссылок нужен дру─
гой хэш). А можно ускорить главный цикл.

alone> Как не перебирать все совпадения по 
2, когда ищу большие совпадения? В ZXRar
хэшируются тройки, а двойки ищутся простым
поиском не дальше 256 байт смещения. Но не
спасает. Впрочем, статистику не собирал,
сколько адресов перебирается в среднем на
один поиск.Можно было бы сделать отдельные
хэш-таблицы для других длин ссылок, но не
факт,что это ускорит поиск в сумме. Скорее
наоборот,и чем больше хэш-таблиц,тем хуже.
И хэшировать символы 1,2,3,потом 3,4,5
тоже ни к чему не приведёт. Гулять по двум
цепочкам со сравнением расстояний
не выгоднее, чем по одной длинной цепочке.
Может, построить LZ77 на куче из LZ78?
Большинство популярных алгоритмов основаны
на  LZ77, потому  что  производный от LZ78
алгоритм  LZW  был  запатентован компанией
Unisys  в 1984 году, после чего они начали
троллить всех и каждого, включая даже слу─
чаи  использования  изображений  в формате
GIF.

alone> Интересная идея двойного хэширова─ 
ния:An improvement on hash-based
algorithms for searching the longest-match
string used in LZ77-type data compression
(1997) by Kunihiko Sadakane. Интересно,что
по статистике в текстах ссылки длиной 4
встречаются чаще, чем ссылки длиной 3.
lvd>в общем, 3-байтовые хэши примерять к 
концу совпадения,а не к началу.если совпа─
ло - гоу сравнивать побайтно.а ещё у мну в
мхмт все 2-байтовые совпадения в отдельной
таблице лежат.65536 входов.и в каждый вход
список, где раньше такое встречалось.
alone> А какая разница, к концу или к 
началу?
lvd>такая, шо если 2 байта вначале совпа─ 
дают и 3 в конце, то есть смысл сравнивать
всю строчку. Я ищу совпадения на каждом
байте, в отличие от.
была мысль совпадения длины эн от прошлого
байта передавать в текущий с длиной n-1.
но ничего не делал пока.
alone> Вообще-то сравнивать строчку 
гораздо быстрее, чем по списку гулять.
lvd>да ну? у мну список всех мест, где 
такие 2 байта уже были.
alone> А ты иннер луп посмотри. 
lvd>берёшь ближайшее и работаешь. 
взять первыё элемент списка - O(1).
alone> 2 байта могли быть в 1000 мест. 
lvd>найти, где такие два байта раньше 
было - O(n). где n - размер файла.
alone> Из них ближайшие 888 неправильные. 
lvd>и чо. взял из списка, примерил хеш к 
концу - облом. взял следующий из списка,
примерил хэш - и так до усрачки.
alone> И фейл. Статью почитай. 
Усрачки нет даже в zlib и lha.
lvd>и чо там говорят, если кратко? 
alone> Что надо по хэшу переходить не 
сразу на список, а на хэш младших битов
следующих символов в этом контексте.
И типа на 40% быстрее у них получилось.
lvd>у меня список и хэш отдельно. 
alone> А что у тебя по хэшу? 
lvd>3 байта. 
alone> 3 байта у тебя на входе, а что на 
выходе?
lvd>1 байт хеша. 
alone> В хрусте там адрес цепочки лежит. 
А потом по цепочке идём. В ZXRar'е тоже.
lvd>какой цепочки? 
alone> Цепочки всех адресов, где такие 3 
байта или похожие.
lvd>у мну такая цепочка на 2 байта. 
alone> Фишка в том, что надо исключить 
такие омегадлинные цепочки. Для повторяю─
щихся байтов hrumer придумал как (см. Info
Guide #7, не реализовано).
lvd>они исключаются по макс. длине ссылки 
назад замечательно.
alone> Фигово исключаются, если всякие 
японцы делают на 40% быстрее на текстах.
lvd>быстрее, чем что? 
alone> Чем zlib. 
lvd>может, mhmt на 20% быстрее японцев? 
alone> Хоца на Спектруме. 

hrumer> 
aaaaakedfhvbsdghaaaaaaadeferaaaaaaaaaaa - 
быстрое решение вопроса последовательности 
аааааа. 
вот кусок: "Я для Laser Compact думал обо─ 
йти  проблему  следующим  образом: по-осо─ 
бому относиться к последовательностям байт 
AAAAAA... и ABABABAB..., длиной  L, больше 
определенной,подбираемой на тестах (думаю, 
от 3..5 байт). Они очень часто встречаются 
в картинках. При заполнении таблицы - той, 
где лежат адреса предыдущих вхождений сим─ 
вола (или символов, если  хэширование идёт 
не по одному байту):" 
там на самом деле поиск от 2 байт. 
alone> жалко, та статья никому не помогла. 
вернуться бы в те годы и писать сразу под
256К. у нас не было ни одной 128К машины
тогда! а сейчас смотрю прессу и воспомина─
ния челов - похоже, они вообще были редко─
стью.что характерно,самый старый архиватор
на ZX - ZXZIP - поддерживает 256K...

alone> Читал статью про двойное 
хэширование?
hrumer> памяти в 2 раза больше ест, или 
прыгает по той же таблице, и нужна только 
таблица "головы" хешей? я уж когда начал 
читать, подумал, что это именно тот алг., 
про который я тебе говорил. А оказался всё 
же другой алг. 
alone> Памяти не представляю,сколько ест ) 
hrumer> насколько понял, памяти в 2 раза 
больше ест. и хэши вычисляются через 0, 
+1, +2, +5, +7 +9 типа байты. 
кстати, рукомпресс за 95..98 годы здорово 
было читать, я, правда, в более поздние 
года читал...http://compression.ru/
но я смотрел - жутко неудобно читать. 
95-98 - как раз самая тема по сжатию была. 
много всего напридумано именно в те годы.а 
сейчас естьhttp://encode.ru/.домен в ру, 
но всё по-английски. ощущение, что рукомп─ 
ресс из фидо перебрался на енкоде.ру. 
alone> У меня была идея ускорения главного 
цикла поиска таким дубовым методом: вместо
хранения файла в одной странице, а списков
в других четырёх хранить в каждой странице
кусок списка (8К) и кусок файла (4К).
Нужно 8 страниц (Для 32К файла). Можно и
на 128К сделать, если загадить экран.
А вот сейчас в голову пришла ещё более
экзотическая мысль - хранить в списке не
адреса,а адреса+страницы,чтобы не пересчи─
тывать. Тогда 12К список+4К файл. Но уже
нельзя будет перейти от файла к списку по
add hl,hl. Зато можно а) их чередовать
через 4 байта, б) чередовать через сегмент
256 байт, в) номер страницы спарить с бай─
том файла, а адрес будет по +#2000, напри─
мер. г) д) - вариации на тему в).

    11. Предварительная обработка файла
   При  упаковке6912 экранов можно попро─
бовать наксорить0, 1 биты одного байта на
7, 6 биты следующего.

hrumer> идея, которую надо проверить на 
реальных данных. а там видно будет, эффек─ 
тивна она или нет. мне тут lvd подкинул 
статистику по вставному байту в хруст1. то 
ли много вхождений, то ли мало... от файла 
к файлу скачет. но, похоже, вряд ли XOR в 
нем можно применить. проверять надо. 

hrumer> Alone, видал Lethargeek Kompakt 
0.(0)4 - компрессор  картинок, пока чёрно─ 
белый? от Lethargeek на форуме. 
alone> Нет пока, а что там? 
hrumer> да там замудрёно что-то в плане 
именно графики. Вот что пишет Lethargeek: 
xored получается так: каждую клетку-знако─
место  можно  инвертировать или ксорить на
соседние со сдвигом  1-2 пикселя (вычищает
сплошные  заливки и типичные текстуры) или
на любую прошлую (мб инвертированную) кле─
тку.Сдвиги не учитываются сейчас,всё равно
для фоновых объектов один обычно,так что и
со  сдвигом будет много одинаковых клеток.
Совпадения  точные  не  требуются, лишь бы
разница поменьше была,в любом случае выбор
в пользу ксорки, занимающей меньше места в
префиксном коде (код простой фиксированный
оставил, потому что подгоняется под него и
разница с оптимальным хаффманом незначите─
льна;в общем лучше,если больше нулей полу─
чится). Так  что нужно будет ещё запомнить
инфу  о выборе (вот она кодируется по Хаф─
фману,потому что непредсказуема) плюс,воз─
можно,расстояние для ксорки с далёкой кле─
ткой (кроме совпадения с прошлой ссылкой в
случае  крупных фоновых объектов или везе─
ния). По уму надо бы после обработки всего
экрана ещё раз сравнить размеры и скоррек─
тировать,но пока я этим не занимался. Цель
была определиться сперва с форматом. Моно─
хромный пакер новый улучшенный выложу, на─
верно, в понедельник, потом буду атрибута─
ми заниматься, а потом депакером на z80.

alx_bw> по столбцам графика лучше пакует─ 
ся, кстати. 
все заставки всегда хранил столбиками. 
alone> Паковать графику можно с перестано─ 
вкой данных. А во время исполнения надо
оптимизить по скорости.

alone> Есть картинка 48х96. Каждый пиксель 
своим цветом.Цвет состоит из оттенка(8 шт)
и яркости (5 шт). Яркость,наверно,меняется
плавно, цвет нет. Но между ними наверняка
есть связь.Как паковать картинку?Либо при─
думать, как обработать данные, чтобы пако─
вать хрустами.Самый тупой способ:разделить
цвета и яркости, паковать по вертикали.

alone> hrumer, а есть какие-нибудь алгори─ 
тмы фрактального сжатия видео? я раньше
пытался что-то придумывать для чистого ч/б
(без полутонов). но надо с полутонами.
hrumer> Книжка есть Ватолина, там, видимо, 
изложено, но как бы это применить, я даже 
и не знаю. 
alone> походу Ватолин только про статичные 
пишет...

alone> На Sega CD 16ц видео разбивают 
на 16 чанков, а чанки где-то там описаны.
Но это только в 2 раза сжимает знакоместо.
Ещё интересно бы паковать не знакоместа, а
весь экран, чтобы адски всё двигалось и
можно было менять поллитру на ходу (на
Sega CD можно, емнип). Можно фиксировать
одни цвета и позволить менять другие.
Тогда можно обновлять по частям.
lvd>может, как в 6912 паковать - подбирая 
чанки, скажем, 4х4.
alone> 4х4 будет видно. 
lvd>если фпс ок, то не будет. к тому же, 
они разноцветные. один и тот же 4х4 может
быть разных цветов.
alone> Имхо надо что-то поумнее тупо 
чанков. Надо хранить какую-то модель,
которую уже потом превращать в пиксели.
Типа вейвлетов. Причём области разной
раскраски тоже должны жить отдельно.
lvd>там тоже есть ключевые кадры, а есть 
диффы. в диффах можно области предыдущих
кадров двигать и зумить.и прочая херотень,
про которую я не знаю.
alone> Двигать и зумить - это слишком 
адско для АТМ. Точнее, двигать можно по
целым парам пикселей.
lvd>а чего бы не придумать jpeg чанками 
4х4 и его распаковывать?
alone> Есть вариант делать видео чисто за─ 
литое,без цветопереходов. Плюс 50% штрихо─
вка. Но совсем залитых знакомест явно на
пол-экрана не наберётся. А если залитые
рисунки, то паковку надо без потерь.
hrumer> Alone: "Мультсистема2.0". жмёт по─ 
следовательности экранов. если послед.бай─ 
тов от картинки к картинке не менялась, то 
вместо этих байт в сжатый поток записывае─ 
тся инфа о его длине.с онлайн перекодиров─ 
кой экрана по столбцам внутри третей экра─ 
на. с LZ77. но тормозно. и с RLE. 
alone> У меня для 6912 был метод с разбие─ 
нием на знакоместа, раздельными потоками
стандартных и нестандартных знакомест и
упавляющим. Нестандартные знакоместа коди─
ровались 4 байтами(из 1 байта делается 2).
В Time Gal(16ц) знакоместа шли целиком,там
сжатие только за счёт пропуска знакомест.
В цвете на точку ещё нужна очень быстрая
распаковка, т.к. экран в 4 раза больше.
В 6912 сначала вместо стандартных знако─
мест были ссылки назад в пул использован─
ных знакомест,но со стандартными оказалось
выгоднее. Даже несколько залитых разным
уровнем яркости уже сильно улучшают упако─
вку.Типичное полутоновое видео сжимается в
200-500 байт на кадр.Хотелось бы для цвета
на точку порядка килобайта на кадр.
В большинстве случаев достаточно 4 цветов
на знакоместо.Но их перечислить - 2 байта.
Надо обыграть тот факт,что знакоместа с
общей палитрой соседние по вертикали и го─
ризонтали.И чтобы знакоместа учитывали со─
седние по рисунку,но это матан.Думаю,пали─
тру от кадра к кадру менять бессмысленно.
hrumer> эдак ты к jpeg придешь. и к сжатию 
видео mpeg. 

lvd>пцвидео не столько пакуют картинки, 
сколько предыдущий кадр модифают в новый.
alone> для этого надо многа-многа тактов. 
lvd>если кадер в виде чанков 88 или 44, 
то не особо. и вообще, чанки в 16ц могут
быть любого размера по вертикали и чётного
по горизонтали.
alone> для затравки идея - 4 цвета на зна─ 
коместо. это для реального кино.
а линии совсем по-другому пакуются.

alone> 16ц видео жать методом DDp,наверно, 
не самый эффективный способ.А для залитого
метод Screw не учитывает соседние столбцы.
lvd>а чарсетом жать можно? 
alone> Думаю, будет фигово. Я делал в 2002 
году пакер со ссылкой на старые
знакоместа,было некрасиво. Вылезали фигуры
узнаваемые, но не из тех мест.
lvd>нет - сгенерить под кадыр чарсет и 
напечатать им кадыр. можно чарсет на всю
видиу, печать с точностью 1 пиксель,разных
размеров.или динамически упдейтить чарсет.
alone> Сколько символов в чарсете? 
lvd>больше 256 и много. сколько памяти не 
жалко.
alone> Тогда в чём вин? 
lvd>в реюзе. 
alone> Надо меньше килобайта на кадр,иначе 
нет смысла возиться.
В Dimon128 примерно 200 байт на кадр.
lvd>ты хочешь из головы без экспериментов 
придумать меньше килобайта на кадр?
alone> Наверно,всё-таки надо скроллы.Нужно 
от чего-то танцевать. Иначе любимых диги─
талреалитями и тхесуперами анимированных
человечков на АТМ не получится, или
получится, но неоправданно жирно.
lvd>что такое скроллы? 
alone> Это для зоны указываем, что графику 
брать со старого экрана с такого-то места.
lvd>скроллами весь кадр не вытянешь. 
alone> Треть кадра идёт пропуском знако─ 
мест,треть стандартными знакоместами,а вот
в остальной части можно часть скроллами,
часть новой графикой.

            12. Сжатие музыки
alone> Hrumer: а ты не размышлял насчёт 
упаковки AY музыки?
hrumer> в 97 году размышлял. свёл к тому, 
что в конечном итоге получится плеер,подо─ 
бный существующим, и забросил это дело :) 
а сейчас как дело обстоит? сколько КБ идёт 
на музыку? 
alone> Всё ещё плеер от саундтрекера 
юзаем. Есть ещё WYZ tracker,но туда ничего
не сконвертить. Испанский. Его юзают Mojon
Twins. В фидо кто-то говорил, что он в 2К
музыку может засунуть от Чёрного Ворона,
но результатов не видели.
  (Самый короткий плейер PTЗ (меньше 1 КБ)
см. в Info Guide #11 .)

jtn> нельзя *LZ переделать под ROM? 
lvd>ну смотри: пакед это RND. а депакед - 
нет. если ты для депакед в пакеде искать
будешь, х чего ты найдёшь.
jtn> во-первых, битовый поток отделить. 
lvd>ну и? больше 1 байта тогда ты не 
найдёшь. если битовый поток отделить и
инфу о длинах и смещениях от байтов.
jtn> не факт, но можно попробовать. 

hrumer> Я вот, кстати, не тестировал такую 
штуку: в LZ кодировать не ссылки на распа─ 
кованную область,а на "запакованную".Доба─ 
вить RLE, непакованные байты класть в один 
поток, а битовый поток пускать отдельно. 
alone> Особенно выиграет,если потоки физи─ 
чески разделены в памяти (ссылки короче).
Я делал пакер регистров для AY с LZ в упа─
кованную область (но без рекурсии). Но не
доделал (плейерTFMCOM12.$H вhttp://
alonecoder.nedopc.com/zx/books/TFM.rar ).
Вообще если разделить потоки, то сразу
можно LZ78. Для него что-то там доказано:)

             13. Самоконтроль
alone> Чего не хватает в спекопакерах:сра─ 
зу тестировать блок на распаковываемость.
lvd>если нет ошибок в коде, то блок 
распакуется железно, ты о чём?
alone> что он поверх себя распаковывается. 
lvd>а ты не распаковывай поверх. юзай по─ 
токовую модель с буфером.правда,для хруста
буфер получится на всю память, но всё же.
можно в mhmt уменьшить макс смещение взад.
hrumer> была поздняя мысль у меня. Через 
CRC делать проверку сразу после упаковки+ 
на этом же этапе сообщать, на сколько надо 
делать зазор для распаковки, чтобы не было 
накрытия областей. вот чего не хватает - 
пакера, чтобы голову не греть насчет нало─ 
жения распакованного на нераспакованное. 
а сделать-то можно. 
lvd>Alone: так возьми распаковщик на сях 
и напиши обёртку, чтобы палила позицию
депака и исходных данных, и вычисли зазор.
hrumer> так однозначно тормозно будет. или 
пофиг на скорость? 
lvd>в деме алонера целый мод в полмегаба─ 
йта распаковывается через буфер.
hrumer> да не, типа просто кусок памяти 
распаковать, без буфера. если плохо жмётся 
- то в определенный момент съезжаем с 
паковки, кидаем с особым кодом завершения 
оставшийся кусок. 
lvd>так в хрусте же так и есть, по сути. 
есть коды - скопировать длинный кусок
просто так.
hrumer> ага, надо было просто развить на 
кусок не в 42 байта, а в 30 КБ. Не так и 
сложно, только чуток сложнее в пакере 
организовать. типа в полтора прохода. 
в хрусте пакер зазря иногда срывается, и 
вместо 42 таких байт кодирует непакованную 
последовательность, потом пару-тройку байт 
пакует,потом снова непакующиеся кодирует:( 
lvd>а есть смысл до 30 кил увеличивать? 
если в блоке 30 кил рандома, зачем вообще
паковать?
hrumer> есть, особенно чтобы в конце 
использовать, но надо вовремя понять это. 
Хотя, если оптимальное кодирование юзать, 
то это понимается попроще. 
lvd>а в mhmt всегда лепит оптимальное 
кодирование! :) правда, для хруста оно не
совсем оптимальное. ибо увеличивающиеся
ссылки он не знает, как оптималить.
hrumer> если 30 кил рандома - то надо всё 
равно обрабатывать, т.к. народ желает 
просто сжать кусок и разжать. но если 
чистые 30 кил рандома и ничего больше - то 
хрен распакуешь без доп. буфера :) 

         14. Finite state entropy
   Вместо Хаффмана и арифметического коди─
рования можно использовать компромисс: це─
лобитное кодирование с конечным автоматом.
  FSE  is  a new kind of Entropy encoder,
based  on ANS /asymmetric numeral systems/
theory, from Jarek Duda. It is designed to
compete  with  Huffman  encoder and Arith─
metic  ones. While huffman is fast but can
only represent probabilities in power of 2
(50%,  25%, etc.)  arithmetic  coding  can
represent  probabilities  with much better
accuracy, but requires multiplications and
divisions.
  FSE  solves  this  dilemna by providing
precise   probabilities,  like  arithmetic
does, but  using only additions, masks and
shifts. This makes FSE faster, on par with
Huffman  speed, and suitable for low-power
CPU environment.
https://
github.com/CyanЧ973/FiniteStateEntropy
   Про  asymmetric binary system есть тут:
https://groups.google.com/forum/#!topic/
comp.compression/_cYQFMijqXE
   Хорошо разжёвано на русском языке:
https://m.habrahabr.ru/company/playrix/
blog/324116/ Но нужна большая таблица,если
не придумать хитрую структуру данных.
   Ещё попадались такие публикации:
http://citeseerx.ist.psu.edu/viewdoc/
summary?doi=10.1.1.168.6702
https://www.vde-verlag.de/proceedings-en/
45369047.html