Анализ недокументированных растровых форматов с алгоритмами RLE сжатия.

До такого я еще не дорос. Lempel & Zeewe они же вроде с дваухбайтовыми массивами работают. Меня интересуют игровые растры с однобайтовым представлением цвта.

 

WERTA, LZ - это битовый поток, сколько захочешь, столько и будет.

 

Как не пытался читать вот это Ватолин, Ратушняк - Сжатие..., ничего кроме RLE так и не понимаю толком. А если битовый, то я пас. Я битовое сжатие только понимаю в растровых шрифтах. Вот там все просто.

 

WERTA, в сжатии я нифига не понимаю (хотя я вообще мало что понимаю ), но LZ несильно отличается от RLE. Например, есть строка "я шел и пришел о". Пронумеруем символы (по сути, смещения от начала строки):

Код:

я шел и пришел о
0123456789ABCDEF

Закодируем так:

Код:

я шел и при24о

Здесь 24 означает, что при распаковке на место этого кода мы подставляем 4 символа, начиная со смещения 2 (то есть как раз "шел ").
Чтобы отличать данные, которые нужно будет расшифровывать, от тех, которые не нужно будет расшифровывать, обычно вводят байт масок. Это значит, что на каждые 8 байт данных мы включаем еще один байт, в котором каждый бит будет говорить, является ли соответствующий байт из 8-байтного блока зашифрованными данными. Например, наше "я шел и при24о" будет в результате выглядеть так:

Код:

(0000 0000)я шел и (0001 10)при24о

В нашем случае 0 - данные не зашифрованы, 1 - данные зашифрованы.

Хоть это и словоблудие, но реальное описание формата очень разнится от модификации к модификации. Байт масок может быть двумя байтами, может быть до или после блока данных. Само представление кодирования (код "24" в нашем случае) может быть тоже разным.

Вот, например, формат из реальной жизни (игры Z и Z: Expansion Kit):
Исходная последовательность байт (от балды):

Код:

00 00 01 [B]02 AB 56 90[/B] 90 34 [B]02 AB 56 90[/B] 00 01 05 60 87 65

Жирным выделены одинаковые последовательности. Кодируется так:

Код:

[U]FF[/U] 00 00 01 02 AB 56 90 90 [U]BF[/U] 34 [B]42 00[/B] 00 01 05 60 87 65

Жирным выделен код (в данном алгоритме он всегда двухбайтовый), представляющий собой следующее (читаем справа налево):
0042:
004 - смещение (первый байт имеет смещение 1)
2 - кол-во упакованных байт за вычетом двойки (то есть, реальное количество байт равно 4)

Подчеркнутым выделены байты масок:
FF = 1111 1111 - все последующие байты являются незашифрованными
BF = 1011 1111 - все последующие байты, кроме одного двухбайтного кода, являются незашифрованными.
Здесь важно отметить, что на двухбайтный код зашифровки в байте масок выделяется только 1 бит, а не 2. То есть, в нашем случае, соответствие байта маски и идущей за ним последовательности таково:

Код:

[U]BF[/U] 34 [B]42 00[/B] 00 01 05 60 87 65
BF= 1    0   1  1  1  1  1  1

Прошу прощения за такой огромный непонятный пост ни о чем)

 

Очень даже понятный. Нет лучше объяснения, чем объяснение в простом разговоре. Спасибо.

 

WERTA, вот ещё один формат:
http://www.shikadi.net/moddingwiki/RLEW_compression
Используется в Dangerous Dave 2.

 

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