Скопировано с сайта zxvideo.fatal.ru по просьбе его автора Статья написана по заказу Александра Шушкова (Alex Xor) для книги по программированию на спектруме. Сжатие графической информации и что из этого можно получить. (C) Vitamin/CAIG/2001 Любая игра, даже самая маленькая содержит в себе графику. Ее количество зависит от многих факторов- жанр игры, стиль исполне- ния, возможности штатного художника :) Возникает естественное стремление "впихнуть" в эту игрушку как можно больше картинок, дабы сделать ее красивее, играбельнее и чтобы она навсегда оста- лась в памяти потомков. Только вот стремление это одно, а аппа- ратные возможности зачастую совсем не соответствуют вашим запро- сам ("ну почему эти 10 картинок нельзя вместить в 48 килобайт?!?!"). И приходится кодерам ругаться с художниками, вы- кидывая результат их труда чтобы освободить еще несколько байт памяти под музыку или что другое. С появлением упаковщиков ситу- ация несколько изменилась. Теперь графика (и не только) занимает ГОРАЗДО меньше места. На диске. В памяти после декомпрессии она весит столько же сколько и была раньше. И тут наступает второй этап чесания реп и других частей тела в поисках оригинальных идей. И они приходят. Взять, к примеру, идею хранения через- строчной маски- выигрыш до 25%. А вот создатели "CSC: Deja Vu" пошли еще дальше- они вообще умудрились хранить спрайты без мас- ки, что в два раза сэкономило объем графики (по крайней мере той, что использует маски). Но у это медали, как и у любой дру- гой, есть обратная сторона. А не будут ли затраты на процессор- ное время (и ту же память) вследствие такой экономии настолько велики, что лучше будет обойтись старым способом? Необходимо прийти к компромиссу, оптимальному соотношению качество упаков- ки/время обработки. В данной статье я собираюсь вам рассказать об одной идее, ко- торая мне так же однажды очень крепко стукнула в голову. Эта идея как раз насчет сжатия графики без потерь и с минимальными расходами на декомпрессию. Она была успешно опробована и реали- зована под козырным названием BitPack. Идея этого метода вот в чем. Пусть у нас изображение разбито на квадратные блоки 8х8 пиксе- лов, тогда каждый такой блок будет занимать 8 байт. Если картина осмысленная, а не абстрактный шум, то между байтами данного зна- коместа должна быть связь. В качестве примера можно взять текс- туры. Последовательно опишем операции при упаковке одного знако- места. Вот оно: +--------+ | # # | | # | | # # # #| |# # # # | | # # # #| |# # # # | | # # | |## # | +--------+ Что мы с ним будем делать? А перегоним его в своеобразный дель- та-код, т.е. вместо байта будет выступать его разница с предыду- щим. Для первого байта предыдущий будет пустым. Для графики в качестве разницы удобно брать не вычитание, а операцию "сключаю- щее или" (xor). Вот что мы получим в итоге +--------+ | # # | | # # # | | # # ###| |########| |########| |########| |# ### | |## # ## | +--------+ Тут видно, что у нас один байт повторяется три раза. Мы можем (а может и нет) на этом выиграть место. Пусть у нас будет введен сигнальный байт, в котором будет храниться информация о том, в каких случаях разница остается постоянной. Каждый бит данного байта будет отвечать за каждый байт итоговой разницы. Вот что мы получим: +--------+ |#### ##| +--------+ |||||||| +--------+ |||||||| | # # | <----+||||||| | # # # | <-----+|||||| | # # ###| <------+||||| |########| <-------+|||| |########| <--------+||| |########| <---------+|| |# ### | <----------+| |## # ## | <-----------+ +--------+ Два бита мы установили в ноль т.к. разница, за которую они отве- чают равна предыдущей, т.е. разнице 4 бита. Таким образом, из исходной разницы мы можем выкинуть два байта. Но при этом мы должны добавить один байт- маску, в которой будет храниться информация о байтах выходного потока. Значит, в данном примере мы сэкономим один байт. Стоило ли городить огород из-за одного байта? Тем более, как многие могли заметить, возможен даже проигрыш в один байт, если повторов не будет. Приведу некоторые факты, которые вы можете сами проверить: 1 пустое знакоместо кодируется в 1 байт 1 полное знакоместо кодируется в 3 байта любую текстуру из чередующихся двух байт можно сжать в 3 байта а некоторые даже в 2 (в том случае, если каждый второй байт ну- левой). И для практической реализации приведу исходник упаковщика и рас- паковщика для одного знакоместа. При желании его нетрудно будет переделать на большее число знакомест. ;упаковка одного знакоместа ;HL- адрес верхней строки знакоместа ;DE- адрес в памяти, куда будем передавать данный PACKPLC ;HL->DE PUSH DE LD B,8 LD DE,BUFF ;временный буфер LD C,0 MXOR LD A,(HL) ;составляем разницу знакоместа XOR C LD (DE),A LD C,(HL) INC H INC DE DJNZ MXOR POP DE LD HL,BUFF LD (ADRA+1),DE ;запоминаем адрес, куда поместим маску INC DE ;знакоместа XOR A LD BC,#800 PCKA CP (HL) ;сравниваем разницы JR Z,OLBY LD A,(HL) ;если такой не было, то заносим LD (DE),A INC DE SCF ;и документируем OLBY RR C INC HL DJNZ PCKA ;и так по всем байтам LD A,C ;получили маску ADRA LD (0),A RET ;распаковка одного знакоместа ;HL- адрес в памяти ;DE- адрес первой строки знакоместа DEPACKPLC ;HL->DE LD C,(HL) ;взяли маску знакоместа INC HL LD A,8 ;цикл на 8 байт EX AF,AF' XOR A ;начальный байт LD B,A ;начальная разница EX AF,AF' MCO EX AF,AF' RR C ;выделяем очередной бит JR NC,OLBB LD B,(HL) ;новая разница- обновляем INC HL OLBB ;выводим данные XOR B LD (DE),A INC D EX AF,AF' DEC A JR NZ,MCO RET BUFF DS 8 ;временный буфер Подсчитаем время, затрачиваемое на распаковку одного знакоместа (время упаковки не так критично). Примечание: все нечетнотактовые команды на самом деле выполняют- ся на полтакта дольше. Это вы можете легко проверить, подсчитав, сколько байт успеет LDIR перебросить за одно прерывание, а за- тем, разделив число тактов у вашей машины на этот объем, получи- те приблизительно 21.5, вместо 21 такта, как пишут в справочни- ке. LD C,(HL) ;7.5 INC HL ;6 LD A,8 ;7.5 EX AF,AF' ;4 XOR A ;4 LD B,A ;4 EX AF,AF' ;4 E=37 tics MCO EX AF,AF' ;4 RR C ;8 JR NC,OLBB ;12/7.5 LD B,(HL) ;7.5 INC HL ;6 E1=12/21 tics OLBB XOR B ;4 LD (DE),A ;7.5 INC D ;4 EX AF,AF' ;4 DEC A ;4 JR NZ,MCO ;12/7.5 Итого выходит: T=37+8*(47.5+12/21)-4.5=37+380-4.5+8*(12/21)= =412.5+8*(12/21) tics Max: 580.5 tics Min: 508.5 tics В среднем это будет 544.5 такта на одно знакоместо. Сравним с обычным методом: LD B,8 ;7.5 LOOP LD A,(HL) ;7.5 LD (DE),A ;7.5 INC HL ;6 INC D ;4 DJNZ LOOP ;13.5/8 E=7.5+8*38.5-5.5=310 tics Разница в скорости составляет 1.76 раза. Таким образом, данный метод можно рекомендовать в тех случаях, когда не требуется особое быстродействие. К тому же у данного метода есть одна особенность: упакованные данные также хорошо сжимаются разными архиваторами.