Наткнулся на странный алгоритм распаковки. Похоже, перевод с ассемблера на С++ 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, не теряя последние байты?
