Хозяйке на заметку: повидло
Для варки яблочного повидла подойдут те фрукты, которые не пригодны для еды – переспевшие,
поврежденные и т.д. – короче говоря, все мягкие или жёсткие, какими вы располагаете.
chudo-povar.com

Категорическая вам конничива, товарищи!
Как и было обещано, принесли вам многабуквенный отчёт про тонкости приготовления повидла из плохих яблок в условиях крайнего юга.

DISCLAIMER: За сочинения у меня в школе была стабильная тройка, поэтому пристегните ремни.
Будет много воды и лабуды. Возможны полный бред, попирание принципов, нарушение законов физики и розовые пони.

Преамбула

Всё началось с того, что одним хмурым октябрьским вечером в беседе с n1k-o речь зашла о нашумевшем несколько лет назад анимационном shadow-art видео «Bad Apple!!».
Если вы в своё время благополучно пропустили вспышку (как, собственно, это сделал я), то узнать, в чём суть, можно здесь.
Вот, чтобы далеко не ходить, то самое видео:



Так вот: n1k-o совершенно справедливо заметил, что конверсии этого видео есть чуть более, чем на всех известных платформах, но вот беда — исключая нашу с вами любимую. Обидно, не так ли? Я тогда отшутился, дескать, раз надо, то я прямо сейчас готов исполнить всё вот это, правда, в спектрумовских атрибутах 32x20.

Шутки шутками, но яблочное зёрнышко засело в голове и потихоньку пускало корни.
Как стало понятно позже, и у Олега тоже.

<nq> но вселенская справедливость должна быть восстановлена
— nq торжественно скрывается на пару часов

Я осознал и проникся.
Не менее хмурой и не менее октябрьской ночью, удостоверившись, что домочадцы мирно пускают пузыри в кроватках, я вколотил первые строки в Makefile. Пути назад не было.

Ограбление по-питоновски

Итак, исходное видео скачано. Посмотрим-ка на то, что мы тут имеем:

VIDEO:  [H264]  960x720  24bpp  30.000 fps  901.3 kbps (110.0 kbyte/s)

Прикидываем наши скромные возможности и решаем ограничиться десятью кадрами в секунду.
Это снизит размер, позволит выводить чётко кадр через четыре и всё ещё будет выглядеть вполне смотрибельно.
Отсюда получаем порядка 2200 кадров, что в спектрумовских монохромных скринах составляет около 13 метров.
Время расчехлять Python, чесать лысину и притаптывать это безобразие!

Раскладывать на диске адовый пасьянс, выдёргивая и сохраняя кадры по одному, не хочется, да и не нужно.
Делаем так:

import subprocess

WIDTH,HEIGHT,FPS = 256,192,10
command = [
    FFMPEG_BIN,
    '-i', SRC_VIDEO,
    '-f', 'image2pipe',
    '-vf', 'scale=%d:%d' % (WIDTH,HEIGHT),
    '-r', '%0.1f' % FPS,
    '-an',
    '-pix_fmt', 'rgb24',
    '-vcodec', 'rawvideo',
    '-v', '0',
    '-'
]

pipe = subprocess.Popen(command, stdout=subprocess.PIPE, bufsize=10**8)

После этого мы легко можем брать следующий кадр в формате RGB24 прямо из видео таким образом:

def get_next_frame(pipe):
    raw_frame = pipe.stdout.read(WIDTH*HEIGHT*3) # RGB24
    return raw_frame

Итак, у нас есть RGB24-кадр из видео, взятый с нужным FPS, любезно отмасштабированный ffmpeg'ом до наших 256x192 и преобразованный нехитрым питоновским кодом в 6144 байта монохромного битмапа. Что дальше?

Притаптываем

Первое, что приходит в голову при виде чёрно-белой картинки — это, конечно же, применить всем известное RLE.
Но априори в чистом виде этим тут совершенно не прославиться. Поэтому пока откладываем в сторону и следом берём второе, что приходит в голову: работать не с кадрами, а с дельтой — разницей между двумя последовательными кадрами. С этим уже можно что-то делать.
Дальше, памятуя о том, что всё это ещё надо будет как-то успевать распаковывать, отказываемся от мысли оперировать отдельными битами изображения и переходим к полным байтам, а вернее — к блокам по 8 пикселей в ширину и 1 в высоту.
Набрасываем некоторое количество кода и видим вот что:



Это исходный кадр RGB24, его конверсия в 1bpp, разница этого кадра с предыдущим и, собственно, кучка блоков 8x1, которую надо наложить на предыдущий кадр для получения текущего.

Если немного помедитировать, можно заметить, что наши блоки из-за их размера и содержания видео (все вот эти вот силуэты) чаще всего образуют цепочки по вертикали. Исходя из этого делаем предположение, что оптимальнее RLE будет работать именно со столбцами (идём по битмапу сверху вниз), нежели построчно (слева направо).

Прикидываем на пальцах формат хранения одного кадра. Если опустить ненужные подробности, получается примерно так:

(skip), N,
(literals), %bbbbbbbb, %cccccccc,
(rle), M, %dddddddd,
...,
(end-of-frame)

В общем, всё очевидно, ничего нового. В скобках — условные команды распаковщику:
skip — пропустить N строк экрана, literals — отрисовать следующие за командой блоки, rle — отрисовать следующий блок M раз, и, наконец, end-of-frame — закончили упражнение.

Спустя некоторое количество хмурых октябрьских ночей и манипуляций с форматом на выходе получаем что-то около мегабайта и сжатие в дюжину раз. Всё ещё никуда не годится. Про производительность распаковщика даже думать не хочется.
Понимаем, что сжатие без потерь в таком наивном исполнениии себя исчерпало, и переходим к самому весёлому: начинаем соображать, как эти самые потери потерять.

Таджу Каге Буншин но Дзюцу!

Понятное дело, что из-за невеликой производительности нашего Z80 нам недоступны алгоритмы сжатия с хитрой математикой, которые в хвост и в гриву гоняют на PC. Однако есть ниндзюцу со сложным и страшным названием и простой, как полено, сутью: VQ, то бишь векторное квантование.



Оставим рассказы про понижение размерности многомерного векторного пространства путём отображения на конечный набор значений из дискретного подпространства меньшей размерности математикам и Википедии, опишем принцип просто и грубо.

Хозяйке на заметку: алгоритмы Алгоритма (sic!)
Будет преступлением не сказать о том, что где-то в этом месте индеец Зоркий Глаз таки узрел на Поуете совершенно замечательный Bad Apple C64 от algorithm'а. Так вот, алгоритмы Алгоритма строятся примерно на той же базе, но куда более изощрённы технически.
За счёт этого видео ужато до ничтожных размеров флопика C64, однако на результат без боли в глазах смотреть трудновато.
Даже с учётом преимуществ Коммодора — возможности стримить с флопа и быстро рисовать.

• Разбиваем наш кадр сеткой на блоки 8xN пикселей.
• Каждому уникальному блоку ставим в соответствие свой индекс.
• Содержимое блока 8xN (N байт) записываем в некую структуру (условно говоря, массив), из которой его можно будет потом получить по индексу (условно говоря, указателю).

Здесь должен был быть рисунок, наглядно демонстрирующий всё это безобразие, но мне очень не хочется его рисовать. Поэтому просто давайте условимся, что он здесь есть. Мы же с вами взрослые люди, да?

Такую структуру хитрые компрессологи называют поваренной кодовой книгой, codebook.
Не правда ли, сразу видна аналогия c картами тайлов и с палитровыми картинками, к примеру, 256c? Там точно таким же образом 8-битному индексу цвета сопоставляется его 24-битное RGB-значение из палитры (по сути, той же кодовой книги).
Дальше, наверное, можно уже и не продолжать, но… терпите уж :)

Исходный кадр теперь можно сохранить в виде набора индексов-указателей на блоки в кодовой книге и собственно самой кодовой книги. При этом 8xN бит блока заменяется M битами его индекса.
При условии, что блоки изображения не всегда уникальны и M << 8xN, мы уже можем заметить некоторую выгоду от этой затеи. Вспомните пример с картинкой 256c, где M=8, 8*N=24: 24 бита заменяется на восемь, и за вычетом размера палитры наша картинка сдувается втрое.
Понятно, что если мы попробуем таким образом перекрутить наше видео целиком, то всё быстро превратится в тыкву: из-за разнообразия блоков книжка распухнет до непотребных размеров, а вместе с ней, соответственно, вырастет и битовая длина M указателя, сводя на нет все преимущества. Вы ещё здесь?

А теперь финт ушами.

Что нам мешает жёстко зафиксировать размер кодовой книги, СРАЗУ забить её наиболее часто встречающимися в видео блоками и при упаковке подбирать для каждого блока индекс НАИБОЛЕЕ ПОХОЖЕГО на него из имеющихся в книге?

Да, собственно, ничегошеньки. Берём и делаем!

Потери потерь

В качестве меры похожести, не мудрствуя лукаво, выбираем что-то типа так называемой дистанции Хэмминга:



С негодованием отвергая буржуазную математическую символику, говорим, что мы ксорим наши блоки побитово и считаем количество единичек. Нормируя по размеру блока в битах, получаем клёвое число в диапазоне от 0.0 (полное совпадение) до 1.0 (вообще нифига не похоже). Профит!

Хозяйке на заметку: Вороной-Делоне и прочие K-средние центроиды
Да, есть куда более красивые и продвинутые варианты всего этого дела, но нам хватит и этого, спасибочки.

Повидло будем делать за два прохода.
На первом мы определяем наиболее часто встречающиеся блоки, формируем из них нашу кодокнигу и сохраняем её. Вторым проходом мы получаем готовые кадры, подставив вместо каждого блока индекс наиболее похожего из книги.
Крутим размер книжки и блока, по соотношению качества и степени сжатия выбираем блок 8x4 и размер книги в… 128 блоков, то есть 128x8x4 = 4096 бит, или 512 байт. То есть, мы заменяем 32 бита на 7, сдувая кадр минимум в четыре раза.
(Напомню, мы к тому же шерстим не кадры целиком, а только разницу между ними.)
Вооружённые всем вышесказанным, переписываем упаковщик, перебираемся с питона на асм и начинаем пробовать всю эту богадельню распаковать. Распаковщик описывать особого смысла нет, всё тривиально.
В сущности, выходит некое подобие какого-то странного текстового режима. Однако сжатие радует: около 200 байт на кадр!

Хозяйке на заметку: ла***ны

В столь полюбившейся почтенной публике работе мы тихонько спойлернули и сделали именно это: общая для 52 картинок кодовая книга со 128 блоками размером 8x2, zx7 с чуток докрученным депакером сверху — и, на минуточку, овер 350К запихиваются в стандартные 128!
На фоне всеобщего разгула страстей это замечено не было.
Как, впрочем, и ожидалось.

Make it sing

Тем временем хмурые октябрьские ночи внезапно перетекли в декабрьские, а потом, уж совсем неожиданно, и в январские. Дела, работа, семья… repeat. Но у нас уже есть собранная TRD-шка. Пока что без звука и только для Pentagon 512K+. Видео занимает около 400К. Меньше можно, но нельзя: либо качество падает, либо начинает страдать несварением ЦПУ бедный распаковщик.
Великолепный Олег тактично интересуется, не пора ли уже и ему взорвать тишину, в конце-то концов? Уточняет, насколько у него связаны руки в плане памяти и наворотов. Я, как поклонник турбосаунда, думаю не особо долго. Очень хочу Bad Apple в два чипа! Под такое дело и двух банок в нижней памяти не жалко, чёрт возьми!

Хозяйке на заметку: TurboSound
Не понимаю, как эта чудесная, простая и эффектная доработка до сих пор не стала стандартом де факто. Не понимаю. Нет. Ой, всё.

Расшариваем папочку в дропбоксе, и Олежа начинает священнодействие.
Я получаю двойное удовольствие: Олег сохраняет последовательные шаги в музыке так, как это обычно делают в графике. У меня есть редкая возможность слышать и наблюдать, как трек изменяется, крепнет, «обрастая» звуковым «мясом». Бесценно!
Кресло, на котором я подпрыгиваю в наушниках, близко к терминальной стадии разрушения.
Всплывает маленькая проблемка, о которой мы и до того подозревали: скорость TS-трека немного расходится со скоростью оригинальной звуковой дорожки, он несколько быстрее. Без танцев с бубном и дёрганьем трек не вытянуть, да и не нужно — прикинув разницу и поменяв одну строчку в упаковщике, чуть ускоряю видео — до 103.5% от оригинала. make trd, enter, готово. make run. Есть синхра! :)
Следующая проблемка — потребление тактов плеером TS. Как это ни смешно, видео приходится даже немножечко разжать :) Итоговый размер — около 430К.
И вот звучат фанфары: трек полностью закончен! Лихой задор! Кресло доломано бесповоротно.

frames: ~2100
raw zx screens size: ~13M
avg bytes per frame: ~200
compression ratio: ~29.2:1
packed size: ~430K

Кушать подано!

Трек торчит на repeat-е энные сутки. NES-версия изменившимся лицом бежит нервно курить пруду, а соседи, семья и домашние животные от безысходности начинают разучивать слова. Думаем, как лучше зарелизить вот это вот всё.
Идея выпуститься под старым добрым лейблом Techno Lab пришла ещё во время просмотра отличной новогодней интры by Placebo, автор которой, к тому же, любезно соглашается помочь с оформлением релиза и рисует отпадный ASCII-art. Спасибо, dman_pcb !



Изначально собираемся выложить просто так, для исправления исторической несправедливости.
Тут проходит инфа о предстоящем ZX Enhanced компо. Кажется, трудно придумать вариант лучше!
Опять же, были некоторые сомнения: не зарелизить ли out of compo? Как-никак, у нас не вполне дема! Но, учитывая активность сцены, всё-таки кладу наше яблоко в корзинку с демами. Пусть будет :)
Перед этим нахожу хороший менеджер верхней памяти под всё на свете (затрудняюсь точно указать авторство, там человека три минимум), немного правлю под свои нужды и приделываю вместо своей пентагон-only листалки страниц.
Всё, можно расслабиться. Что было дальше, вы и так знаете.
Большое спасибо организаторам пати и всем, кто помогал нам словом и делом.
Надеемся, плохое яблоко всё же вышло не таким уж и плохим :)



До скорого, друзья! Жмите демосцены!

nagareteku toki no naka de demo
kedarusa ga hora guruguru mawatte
и немедленно выпил
(И. Бродский)

(end-of-frame)