LINUX.ORG.RU

Что это такое?

 , ,


0

1

Наткнулся на странный алгоритм распаковки. Похоже, перевод с ассемблера на С++ https://github.com/vvendigo/Darklands/blob/master/file_formats/quadko/PicReaderC.cpp Вкратце:

void CPicReaderC::SetupDecodeTable(TDecodeTableC *DecodeTable, unsigned short &BitMask, unsigned short &DecodeTableIndex, unsigned char &BitMaskCount)
{
	int cnt;
	BitMaskCount=9; // Max valid bit position
	BitMask=0x1ff; // Max valid BitMasks
	DecodeTableIndex=0x100;
	for (cnt=0;cnt<0x800;cnt++)
	{
		DecodeTable[cnt].Next=0xffff;
		DecodeTable[cnt].PixelData=cnt&0xff;
	}
}

// turn file bits into pixel bits
unsigned char CPicReaderC::GetNextPixel(int &StackTop, unsigned short &CurWordValue, unsigned char &BitMaskCount, unsigned short &BitMask,unsigned short *Stack, TDecodeTableC *DecodeTable, unsigned short *Data,unsigned char &DataBitCount,unsigned short &PrevIndex,unsigned char &PrevPixel,unsigned short &CurIndex,unsigned short &DecodeTableIndex, unsigned char &FormatFlag)
{
	unsigned char RetVal=0;
	int TempIndex;
	int Index;
	int CurBits;

	if (StackTop==0) 
	{
		CurBits=CurWordValue>>(16-DataBitCount);
		while (DataBitCount<BitMaskCount)
		{
			CurWordValue=Data[CurIndex++]; // Get next word (Image data:next word)
			CurBits|=(CurWordValue<<DataBitCount)&0xffff;
			DataBitCount+=0x10;
		}
		DataBitCount=DataBitCount-BitMaskCount; 
		Index=CurBits & BitMask;
		TempIndex=Index;
		if (Index>=DecodeTableIndex)
		{
			TempIndex=DecodeTableIndex;
			Index=PrevIndex; 
			Stack[StackTop++]=PrevPixel;
		}
		while (DecodeTable[Index].Next!=0xFFFF)
		{
			Stack[StackTop++]=(Index&0xff00)+DecodeTable[Index].PixelData;
			Index=DecodeTable[Index].Next;
		}
		PrevPixel=DecodeTable[Index].PixelData;
		Stack[StackTop++]=PrevPixel; 
		DecodeTable[DecodeTableIndex].Next=PrevIndex;
		DecodeTable[DecodeTableIndex].PixelData=PrevPixel;
		PrevIndex=TempIndex;
		DecodeTableIndex++;
		if (DecodeTableIndex>BitMask)
		{
			BitMaskCount++;
			BitMask<<=1;
			BitMask|=1;
		}
		if (BitMaskCount>FormatFlag)
		{		SetupDecodeTable(DecodeTable,BitMask,DecodeTableIndex,BitMaskCount);
		}
	}
	RetVal=(unsigned char)(Stack[--StackTop]);
	return RetVal;
}

void CPicReaderC::DecodeImage(void *FileData,int Len)
{
	unsigned short	*Data=(unsigned short*)FileData;
	unsigned char	RepeatCount=0; // Repeat count for RLE pixels
	unsigned char	CurPixelValue=0; // Cur/Next Pixel value
	unsigned char	TempPixelValue;	// Temp pixel holding var 
	unsigned char	FormatFlag=0; // First byte of file (some max bit value, I think)
	unsigned short	DecodeTableIndex=0; // Base DecodeTableIndex (default= 0x100) incremented for each successful data chunk
	unsigned short	CurWordValue=0; // Cur Word (Last file pointer position/size sometimes?)
	unsigned char	DataBitCount=0; // Cur 'active' bits in
	unsigned short	PrevIndex=0; // Previous Index found
	unsigned char	PrevPixel=0; // Previous Pixel value fetched 
	unsigned char	BitMaskCount=0; // Decode Table count of bits in BitMask (default=9)
	unsigned short	BitMask=0; // Decode Table bitmask maximum (default=0x1FF)
	TDecodeTableC	DecodeTable[0x800];
	unsigned short	CurIndex=0;
	unsigned short	Stack[500];
	int StackTop=0;
	int CurX;
	int CurY;
	Width=Data[CurIndex++]; // Get next word (Width)
	Height=Data[CurIndex++]; // Get next word (Height)
	if (Width==0 || Height==0) 
	{
		return;
	}
	if (ImageData!=NULL)
	{
		delete [] ImageData;
		ImageData=NULL;
	}
	ImageDataLen=Width*Height;
	ImageData=new unsigned char[ImageDataLen];
	RepeatCount=0; // Pixel Repeat count=0
	CurPixelValue=0; // Cur Pixel value; none at first!
	CurWordValue=Data[CurIndex++]; // Get next word (Image data:first word)
	FormatFlag=CurWordValue&0xff; // First byte of Cur word	
	if (FormatFlag>0xb) // Command is > 0xb Fix it
	{
		CurWordValue=(CurWordValue&0xff00)+0xb;
		FormatFlag=0xb;
	}
	DataBitCount=8;
	SetupDecodeTable(DecodeTable, BitMask, DecodeTableIndex, BitMaskCount);
	for (CurY=0; CurY<Height; CurY++)
	{
		for (CurX=0;CurX<Width;CurX++)
		{
			if (RepeatCount>0) // "RLE" Repeat count
			{
				RepeatCount--;
			}
			else
			{
				TempPixelValue = GetNextPixel( StackTop, CurWordValue, BitMaskCount, BitMask, Stack, DecodeTable, Data, DataBitCount, PrevIndex, PrevPixel, CurIndex, DecodeTableIndex, FormatFlag);
				if (TempPixelValue!=0x90)
				{
					CurPixelValue = TempPixelValue; // Set Pixel Value
				}
				else
				{
					TempPixelValue = GetNextPixel( StackTop, CurWordValue, BitMaskCount, BitMask, Stack, DecodeTable, Data, DataBitCount, PrevIndex, PrevPixel, CurIndex, DecodeTableIndex, FormatFlag);
					if (TempPixelValue==0)
					{
						CurPixelValue = 0x90;
					}
					else
					{
						RepeatCount = TempPixelValue-2; 
					}
				}
			}
			ImageData[CurY*Width+CurX]=(unsigned char)CurPixelValue;

		}
	}
}

То есть DecodeImage в цикле вызывает GetNextPixel и применяет к полученному потоку байтов RLE-распаковку (по коду 0x90 0xNN повторяет предыдущий байт NN раз, по 0x90 0x00 ставит 0x90), и так пока не заполнит массив Width x Height байт.
GetNextPixel сбрасывает по байту из накопившихся в стеке, а когда стек пуст, прогоняет очередную расшифровку: читает из массива сжатых данных 9-11 бит, использует их как индекс в словаре, движется по цепочке ссылок внутри словаря, меняя их и сбрасывая данные в стек; при переполнении словаря все элементы сбрасываются в -1 и словарь начинает заполняться по новой.

Вопросы: как это называется? Можно ли его оптимизировать? Можно ли разделить расшифровку и RLE, не теряя последние байты?

★★★★★

Ответ на: комментарий от LamerOk

И заглядывал, и переписал на питоне 3, и в отладчике гонял с разными файлами.

Это не просто RLE, а в комбинации с хитровывернутым алгоритмом. RLE декодируется в DecodeImage, второй алгоритм — в GetNextPixel. Да, на выходе получается 8-битный битмап. Палитра отдельно.

question4 ★★★★★ ()
Ответ на: комментарий от LamerOk

https://en.wikipedia.org/wiki/LZ77_and_LZ78

Словарик строится по частотности.

Именно. Специально написал реализацию LZW, чтобы сравнить. Совсем непохоже на имеющееся здесь. В LZW словарь понемногу пополняется по мере необходимости, а по коду 2**(начальная длина) сбрасывается и составляется заново. Здесь словарь корректируется для каждой очередной последовательности. Общего вижу только чтение из массива последовательностей битов некратных 8 и сброс при достижении предельного размера словаря.

question4 ★★★★★ ()

на странный алгоритм распаковки.

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

Похоже, перевод с ассемблера на С++

это вроде как типишный реверс инжиниринг.

Можно ли его оптимизировать?

Он что ли тормозит? в 92 году не тормозил, а сейчас начал? :D Или оптимизация для оптимизации?

vtVitus ★★★★★ ()
Ответ на: комментарий от vtVitus

Афтор чего то слышал про сжатие со словарём, вот и реализовал какое-то своё виденье.

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

Тут скорее реверсеры нахуевертели, потому как с байтами работать биологически не умеют:

	// Bitmasks for data bits
	BitMaskCount=9; // Max valid bit position
	BitMask=0x1ff; // Max valid BitMasks

	// DecodeTable base index
	DecodeTableIndex=0x100; // why 100, top bit in BitMask? - Coincedence, plan?
LamerOk ★★★★★ ()
Ответ на: комментарий от vtVitus

Афтор чего то слышал про сжатие со словарём, вот и реализовал какое-то своё виденье.

Настолько плохо? А если этот алгоритм был не столько для сжатия, сколько для шифрования?

типишный реверс инжиниринг

Именно.

в 92 году не тормозил, а сейчас начал?

Питон. На большую сложную картинку GetNextPixel вызывается до ~25 тысяч раз. Можно, конечно, вызывать класс на C++, можно просто подождать по 2 секунды на большую картинку. Поэтому интересно, какой будет выигрыш, если вызывать распаковку со словарём всего 1 раз.

question4 ★★★★★ ()
Ответ на: комментарий от LamerOk

пчел

Кто?

Для автора кода загадка, почему в байте восемь бит.

В процитированном фрагменте счётчик бит инициализируется 9, битовая маска инициализируется 9 битами в нижних разрядах, а указатель в словаре ставится на 2^9 байт от начала. Причину последнего автор и пытается понять.

question4 ★★★★★ ()
Ответ на: комментарий от question4

А если этот алгоритм был не столько для сжатия, сколько для шифрования?

в 92 году? Тогда проблема была малый объём всего, а не злобные хакиры. Но микропрайс тогда пытался прыгнуть выше головы, так что, возможно, там и была функция запутывания (шифрования тогда особо не было - не те жел. ресурсы) игровых ресурсов. Как я понимаю, там даже своя файловая иерархия для всех ресурсов да и вообще бедлам https://wendigo.online-siesta.com/darklands/file_formats/bay12forums.com/imc.txt .

Настолько плохо?

ну игра работала на допотопном железе и была достаточно известна, так что результат для того времени хороший +). А так сложно сегодня оценивать работу тогдашних программеров. Инета не было, реализаций в открытом доступе там более, доступ до всякой техно литературы с описанием алгоритмов и т.п. был только через технические библиотеки вузов, доступ в которые в сша стояли не малых денег и не факт что микропрайз жаждал это оплачивать. Железо просто не сравнить, зоопарк видюх и видеорежимов, экономия байтов и тактов и программинг на асме. Сегодня нам в принципе тяжело понять, как тогда жилось и программiлось.

Питон. На большую сложную картинку GetNextPixel вызывается до ~25 тысяч раз.

Не совсем понятно зачем игру 92 года передирать один в один сейчас. Чес слово, думаю что проникнуться идеологией игры, картой, технологией боёв, но сделать на новых технологиях - займёт пару тройку месяцев.

vtVitus ★★★★★ ()
Последнее исправление: vtVitus (всего исправлений: 4)
Ответ на: комментарий от vtVitus

Не совсем понятно зачем игру 92 года передирать один в один сейчас.

Просто интересно посмотреть на ресурсы. Вылазят вещи, которые не смогли доделать, но не стали удалять. Например, вырезанный сюжет с восстанием по объёму тянет на роман — более 200 килобайт текстов.

question4 ★★★★★ ()

Это обычный gif lzw декодер с длиной кода от 9 до 11 бит.

lzw энкодер добавляет в словарь строчку, как только ее находит. Строчка состоит из головы и хвоста. Голова это уже имеющаяся в словаре строчка, хвост это один октет. Начальное состояние словаря – 256 однооктетных строчек. Когда строка найдена, энкодер эмитит код головы и код хвоста.

Например текст октетов ABABCABCD (8x9=72 bit) будет закодирован как последовательность 9-битных кодов A B 256 C 257 D (9x6=54 bit), словарь после этого будет 256=A+B, 257=256+C, 258=257+D. Если словарь заполнен, длина кода увеличивается на один бит. Если словарь заполнен, а длина кода уже максимальная, длина кода и словарь сбрасываются в начальное состояние.

Декодер читает коды парами голова + хвост. Считав пару кодов добавляет в словарь строчку, декодирует код головы в строку октетов по словарю и эмитит эту строку и хвост.

iliyap ★★★★★ ()
Ответ на: комментарий от iliyap

Это обычный gif lzw декодер

Тогда какой смысл несёт данный фрагмент?

PrevPixel=DecodeTable[Index].PixelData;
Stack[StackTop++]=PrevPixel; 
DecodeTable[DecodeTableIndex].Next=PrevIndex;
DecodeTable[DecodeTableIndex].PixelData=PrevPixel;
PrevIndex=TempIndex;
DecodeTableIndex++;

Начальное состояние словаря – 256 однооктетных строчек.

Как реализован словарь? В массиве DecodeTable хранятся только 1-байтные PixelData (инициализируются в 0-255 внутри каждого 256-байтного блока) и 2-байтные Next (инициализирутся в -1). Строк нет. Явных ссылок на строки в раскодированном изображении нет.

Строки как-то строятся через цепочку Next и модифицируются при каждом обращении.

Также я не вижу специальной обработки кодов 256 и 257 для 9 бит. Если это и LZ, то всё же не LZW.

Декодер читает коды парами голова + хвост.

Где это в коде?

CurBits=CurWordValue>>(16-DataBitCount);
while (DataBitCount<BitMaskCount)
{
	CurWordValue=Data[CurIndex++]; // Get next word (Image data:next word)
	CurBits|=(CurWordValue<<DataBitCount)&0xffff;
	DataBitCount+=0x10;
}
DataBitCount=DataBitCount-BitMaskCount; 
Index=CurBits & BitMask;
TempIndex=Index;

Я вижу, как из сжатого массива Data берутся очередые BitMaskCount бит (из CurWordValue оставшиеся с прошлого раза помещаются в CurBits, читаются новые 16 бит в CurWordValue, сдвигаются, OR-ятся с CurBits, накладывается маска в BitMaskCount младших бит) и помещается в TempIndex и Index. Где хвост и голова?

question4 ★★★★★ ()
Последнее исправление: question4 (всего исправлений: 1)
Ответ на: комментарий от question4

Про чтение декодером пар сказал чушь. Обновил в памяти LZW и написал комменты к коду.

// LZW энкодер работает так:
// - начинает со словаря из однооктетных строк
// - читает октеты, пока они составляют строку, которая есть в словаре
// - записывает код строки X
// - добавляет в словать строку X+C
// А это LZW декодер:
unsigned char CPicReaderC::GetNextPixel(
  int &StackTop, // количество октетов в декодированной на предыдущем вызове строке
  unsigned short &CurWordValue, // последнее считанное из Data 16-битное слово
  unsigned char &BitMaskCount, // текущий размер кода, в битах
  unsigned short &BitMask, // текущая маска кода 0xffff >> (16-BitMaskCount)
  unsigned short *Stack, // декодированная на предыдущем вызове строка
                         // в обратном порядке октетов (голова в конце)
  TDecodeTableC *DecodeTable, // словарь, индексирован кодами строк,
                              // каждая строка хранится как код головы Next
                              // и октет хвоста PixelData
  unsigned short *Data, // входные (сжалые) данные, 16-битные слова
  unsigned char &DataBitCount, // кол-во старших битов CurWordValue,
                               // не потреблённых на предыдущем вызове
  unsigned short &PrevIndex, // предыдущий код
  unsigned char &PrevPixel, // первый октет строки, соответствующей предыдущему коду
  unsigned short &CurIndex, // позиция чтения входного массива Data
  unsigned short &DecodeTableIndex, // текущий незанятый код в словаре
  unsigned char &FormatFlag) // максимальный размер кода, в битах
{
	unsigned char RetVal=0;
	int TempIndex;
	int Index;
	int CurBits;

        // Если стек пуст, надо читать из входного массива Data
	if (StackTop==0) 
	{
                // Кладём не потреблённые ранее DataBitCount старших бит из CurWordValue в младшие биты CurBits
		CurBits=CurWordValue>>(16-DataBitCount);

                // Если нужно, считываем очередное 16-битной слово из Data в CurWordValue.
                // Младшие биты CurWordValue кладём в старшие биты CurBits.
                // В DataBitCount кладём количество старших непотреблённых бит.
		while (DataBitCount<BitMaskCount)
		{
			CurWordValue=Data[CurIndex++];
			CurBits|=(CurWordValue<<DataBitCount)&0xffff;
			DataBitCount+=0x10;
		}
		DataBitCount=DataBitCount-BitMaskCount;

                // Наконец-то, Index -- это BitMaskCount-битный код из Data
		Index=CurBits & BitMask;
		TempIndex=Index;

                // Такого кода в словаре ещё нет (этот кейс мне непонятен)
		if (Index>=DecodeTableIndex)
		{
			TempIndex=DecodeTableIndex;
			Index=PrevIndex; 
			Stack[StackTop++]=PrevPixel;
		}

                // Декодируем строку по словарю в стек.
                // Зачем к PixelData добавляется какой-то мусор, непонятно.
                // Всё равно каст к unsigned char этот мусор выбросит.
		while (DecodeTable[Index].Next!=0xFFFF)
		{
			Stack[StackTop++]=(Index&0xff00)+DecodeTable[Index].PixelData;
			Index=DecodeTable[Index].Next;
		}

                // Сохраняем первый октет строки, соответствующей коду
		PrevPixel=DecodeTable[Index].PixelData;
		Stack[StackTop++]=PrevPixel;

                // Добавляем новую строку (предыдущий код + первый октет) в словарь
		DecodeTable[DecodeTableIndex].Next=PrevIndex;
		DecodeTable[DecodeTableIndex].PixelData=PrevPixel;
		DecodeTableIndex++;

                // Сохраняем предыдущий код для следующего вызова
		PrevIndex=TempIndex;

                // Если словарь заполнен, увеличиваем разрядность кодов строк
		if (DecodeTableIndex>BitMask)
		{
			BitMaskCount++;
			BitMask<<=1;
			BitMask|=1;
		}

                // Если масимальный размер кода превышен,
                // сбрасываем словарь и размер кода в начальной состояние
		if (BitMaskCount>FormatFlag)
		{
			SetupDecodeTable(DecodeTable,BitMask,DecodeTableIndex,BitMaskCount);
		}
	}

        // В стеке есть декодированная строка: возвращаем очередной октет
	RetVal=(unsigned char)(Stack[--StackTop]);
	return RetVal;
}
iliyap ★★★★★ ()