Компрессоры. Часть 1: Delta-компрессор анимации

КОМПРЕССОРЫ Часть 1: Дельта-компрессор анимации

Существует множество способов сжатия содержимого экрана, многие из них используются в различных компрессорах, призванных уменьшить титульные экраны игр до приемлемых размеров. Один из таких компрессоров постоянным читателям SCENE+ уже знаком — это Screen Compressor+D, выходивший в одном из прошлых номеров. Его плюсом было то, что он пробовал 4 разных метода и затем выбирал наиболее выгодный. Минусом было то, что работал он сравнительно медленно. С другой стороны, компрессор, представленный в YS, был способен плавно анимировать 1/3 экрана и использовался мной для вращающегося логотипа SCENE+.

Но как добиться плавной анимации на весь экран? Насколько мне известно, до меня никто не реализовывал Delta Compressor для Спектрума, а ведь именно с его помощью можно плавно анимировать полноэкранное изображение, если соблюдены некоторые условия.

Delta Compressor, который я для простоты в дальнейшем буду называть «Дельта», применялся в конце 80-х годов, чтобы заставить ультрасовременные тогда компьютеры вроде Amiga или Atari ST воспроизводить плавную анимацию. Одной из программ того времени у меня была Videoscape 3D — самая недружелюбная к пользователю программа на свете! Ее единственным плюсом было то, что она использовала Дельту для проигрывания очень длинных анимаций.

Что дозволено Амиге, то должно быть по плечу и Спектруму, подумал я и стал размышлять, как перенести эту процедуру на Speccy. Ассемблер 68000 я не знаю, я же не мазохист! Поэтому я стал собирать информацию из «Happy Computer» и других журналов о том, как работает этот компрессор. И ведь действительно: гениальная штука для тех времен, когда слово MPEG еще никому ни о чем не говорило.

Дельта работает очень просто: сохраняются только изменения относительно предыдущего кадра. Это означает, что не нужен ни байт-флаг, отсутствующий в данных экрана, ни большое количество процессорного времени, ведь на экран выводятся только изменившиеся байты. При небольших изменениях картинки можно достичь частоты 50 FPS и скромного размера файла анимации. При значительных изменениях у меня получался размер около 3-4 Кб на кадр и совершенно неприемлемый фреймрейт, но при мелких изменениях все шло как по маслу.

Имея в общей сложности 640 Кб памяти на моем MB02 (512 Кб) и Спектруме (128 Кб), я теоретически мог бы делать потрясающие, длинные и плавные анимации, даже в интерлейсе. Для сжатия я использовал небольшую BASIC-программу, в то время как декомпрессия благодаря крошечной MC-процедуре происходит очень быстро.

Вопрос, который передо мной встал: как сохранить изменения без необходимости городить буфер на 12 Кб, в котором перед каждым байтом хранилась бы информация о том, изменился он или нет? Довольно глупая идея, правда? Из кода 68000 я ничего понять не мог, поэтому начал всерьез ломать голову сам и в итоге пришел к окончательному решению:

Поскольку неизмененные байты всегда чередуются с измененными, достаточно использовать байт-маркер, чтобы сообщить компьютеру, с каких байтов начинается последовательность — с измененных или неизмененных. Затем идут цепочки по 2 байта:

• Байты остаются без изменений: (2-байтовая последовательность задает количество неизмененных байтов, то есть теоретически до 65535, поэтому метод сработает и на SAM Coupé. Счетчик DEstination просто увеличивается на это число байтов).
• Байты изменяются: (2-байтовая последовательность — теоретически хватило бы и 1 байта — задает количество последующих байтов, которые берутся без изменений, просто копируясь через LDIR).

Мало того, что такой способ работает невероятно быстро, он еще и гениально прост — даже я сам удивился полученному решению! Неужели все правда может быть настолько просто? Да! Мой депакер, конечно, не предел совершенства, но благодаря ему я снова смог узнать что-то новое о машинном коде, и понял следующее... Скорость огромна, но и шанс зависнуть не меньше!

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

По поводу Дельты могу добавить, что ей требуется так называемый ключевой кадр (Keyframe), который в идеале нужно сжать другим экранным компрессором. Если же различия между отдельными кадрами довольно велики, можно дополнительно использовать Shrinker-компрессор, а всю готовую анимацию затем «схлопнуть» (Implode).

BASIC-часть компрессора я затем доработал таким образом, чтобы одиночный неизмененный байт, оказавшийся среди нескольких изменившихся, тоже сохранялся как измененный. Благодаря этому декомпрессия не растягивается понапрасну.

Tiger's Claw.

Это была первая часть цикла о компрессорах. Если кто-то захочет продолжить его — без проблем! Пишите мне! В следующей части речь пойдет об обычном алгоритме сжатия (Shrinker). Буду также рад увидеть какие-нибудь ваши примеры анимаций.

Ассемблерная процедура декомпрессора Delta:

       LD HL,Comprscradr ; Адрес сжатого экрана
       LD DE,16384       ; Адрес экрана
       LD A,(HL)         ; Первый байт в A
       INC HL            ; Увеличиваем указатель адреса
       CP 1              ; Сравниваем A с 1
       JR Z,vers         ; Если да, то измененные байты! Переход к vers
Start: LD C,(HL)         ; Загружаем BC содержимым (HL)
       INC HL
       LD B,(HL)
       INC HL
       EX DE,HL          ; Меняем DE и HL местами, так как
       ADD HL,BC         ; сложение возможно только с HL
       EX DE,HL          ; Возвращаем значения обратно
vers:  LD C,(HL)         ; Количество изменившихся байтов
       INC HL            ; загружаем в BC
       LD B,(HL)
       INC HL
       LDIR              ; Копируем все изменившиеся байты
       LD A,D            ; Старший байт DEstination
       CP 88             ; сравниваем с 88 (22528)
       JR Z,Ende         ; Если значение достигнуто, выход
       JR Start          ; Иначе возвращаемся в начало
Ende:  LD BC,HL          ; Для LET X=USR adr, X=следующий свободный байт
       RET               ; Возврат в BASIC

Программа может работать и при включенных прерываниях (например, с музыкой) и компилироваться под любой адрес. Надеюсь, мои комментарии окажутся полезными! Мне пришлось переписывать программу с черновика, на котором было полно правок, так что надеюсь, что все без ошибок.

По поводу сопутствующей BASIC-программы могу дать такие советы:

• Экран после сжатия нужно сохранять где-то в памяти в несжатом виде, чтобы иметь опорный кадр для следующего изображения.
• Программу обязательно нужно скомпилировать, иначе придется очень долго ждать.

Впрочем, написать BASIC-программу каждый из вас должен суметь и сам. Если возникнут какие-либо проблемы или появятся предложения по улучшению от профи ассемблера — пишите в редакцию ASC.