DOOM64-RE

Doom 64 Reverse Engineering
Log | Files | Refs | README | LICENSE

commit f7f9d9a10e067dd89b36f1ff20349fdc881c3ddb
parent f3792388b43d6fcef087b953f117f4df1bfd261e
Author: Erick Vasquez Garcia <erickv5394@gmail.com>
Date:   Tue, 12 Sep 2023 20:59:27 -0600

Update decodes.c

The code is updated to a cleaner and more understandable format, in addition it was possible to identify the possible encoding functions, and the code is added to encode data with 100% accuracy. Since I found no differences with the WAD recompressed with the original WAD.

Diffstat:
Mdoom64/decodes.c | 804++++++++++++++++++++++++++++++++++++++++++++++++++-----------------------------
Mdoom64/doomdef.h | 5+++++
2 files changed, 514 insertions(+), 295 deletions(-)

diff --git a/doom64/decodes.c b/doom64/decodes.c @@ -9,39 +9,44 @@ /*=======*/ typedef struct { - int var0; - int var1; - int var2; - int var3; - byte *write; - byte *writePos; - byte *read; - byte *readPos; -} decoder_t; + int dec_bit_count; + int dec_bit_buffer; + int enc_bit_count; + int enc_bit_buffer; + byte* ostart; + byte* output; + byte* istart; + byte* input; +} buffers_t; + +typedef struct { + int offset; + int incrBit; + int unk1; + int type; +} encodeArgs_t; /*=========*/ /* GLOBALS */ /*=========*/ -static short ShiftTable[6] = {4, 6, 8, 10, 12, 14}; // 8005D8A0 - -static int tableVar01[18]; // 800B2250 +static short ShiftTable[6] = { 4, 6, 8, 10, 12, 14 }; // 8005D8A0 -static short *PtrEvenTbl; // 800B2298 -static short *PtrOddTbl; // 800B229C -static short *PtrNumTbl1; // 800B22A0 -static short *PtrNumTbl2; // 800B22A4 +static int offsetTable[12]; // 800B2250 +static int offsetMaxSize, windowSize; // 800b2280 , 800b2284 +static encodeArgs_t encArgs; // 800b2288 -//static short EvenTable[0x275]; // DecodeTable[0] -//static short OddTable[0x275]; // DecodeTable[0x278] -//static short NumTable1[0x4EA]; // DecodeTable[0x4F0] -//static short NumTable2[0x4EA]; // array01[0] +#define HASH_SIZE (1 << 14) +static short* hashtable; // 800B2298 +static short* hashtarget; // 800B229C +static short* hashNext; // 800B22A0 +static short* hashPrev; // 800B22A4 -static short DecodeTable[2524]; // 800B22A8 +static short DecodeTable[2516]; // 800B22A8 static short array01[1258]; // 800B3660 -static decoder_t decoder; // 800B4034 -static byte *allocPtr; // 800B4054 +static buffers_t buffers; // 800B4034 +static byte* window; // 800B4054 static int OVERFLOW_READ; // 800B4058 static int OVERFLOW_WRITE; // 800B405C @@ -57,33 +62,59 @@ DECODE BASED ROUTINES /* ======================== = -= GetDecodeByte += GetOutputSize += +======================== +*/ +int GetOutputSize(void) // [GEC] New +{ + return (int)((int)buffers.output - (int)buffers.ostart); +} + +/* +======================== += += GetReadSize += +======================== +*/ + +int GetReadSize(void) // [GEC] New +{ + return (int)((int)buffers.input - (int)buffers.istart); +} + +/* +======================== += += ReadByte -> Old GetDecodeByte = ======================== */ -static byte GetDecodeByte(void) // 8002D1D0 +static int ReadByte(void) // 8002D1D0 { - if ((int)(decoder.readPos - decoder.read) >= OVERFLOW_READ) + if ((int)(buffers.input - buffers.istart) >= OVERFLOW_READ) return -1; - return *decoder.readPos++; + return *buffers.input++; } /* ======================== = -= WriteOutput += WriteByte -> Old WriteOutput = ======================== */ -static void WriteOutput(byte outByte) // 8002D214 +static void WriteByte(byte outByte) // 8002D214 { - if ((int)(decoder.writePos - decoder.write) >= OVERFLOW_WRITE) + if ((int)(buffers.output - buffers.ostart) >= OVERFLOW_WRITE) { I_Error("Overflowed output buffer"); + } - *decoder.writePos++ = outByte; + *buffers.output++ = outByte; } /* @@ -97,44 +128,44 @@ static void WriteOutput(byte outByte) // 8002D214 static void WriteBinary(int binary) // 8002D288 { - decoder.var3 = (decoder.var3 << 1); + buffers.enc_bit_buffer = (buffers.enc_bit_buffer << 1); if (binary != 0) - decoder.var3 = (decoder.var3 | 1); + buffers.enc_bit_buffer = (buffers.enc_bit_buffer | 1); - decoder.var2 = (decoder.var2 + 1); - if (decoder.var2 == 8) + buffers.enc_bit_count = (buffers.enc_bit_count + 1); + if (buffers.enc_bit_count == 8) { - WriteOutput((byte)decoder.var3); - decoder.var2 = 0; + WriteByte((byte)buffers.enc_bit_buffer); + buffers.enc_bit_count = 0; } } /* ======================== = -= DecodeScan += ReadBinary -> old DecodeScan = ======================== */ -static int DecodeScan(void) // 8002D2F4 +static int ReadBinary(void) // 8002D2F4 { int resultbyte; - resultbyte = decoder.var0; + resultbyte = buffers.dec_bit_count; - decoder.var0 = (resultbyte - 1); + buffers.dec_bit_count = (resultbyte - 1); if ((resultbyte < 1)) { - resultbyte = GetDecodeByte(); + resultbyte = ReadByte(); - decoder.var1 = resultbyte; - decoder.var0 = 7; + buffers.dec_bit_buffer = resultbyte; + buffers.dec_bit_count = 7; } - resultbyte = (0 < (decoder.var1 & 0x80)); - decoder.var1 = (decoder.var1 << 1); + resultbyte = (0 < (buffers.dec_bit_buffer & 0x80)); + buffers.dec_bit_buffer = (buffers.dec_bit_buffer << 1); return resultbyte; } @@ -142,13 +173,13 @@ static int DecodeScan(void) // 8002D2F4 /* ======================== = -= MakeExtraBinary += WriteCodeBinary = routine required for encoding = ======================== */ -static void MakeExtraBinary(int binary, int shift) // 8002D364 +static void WriteCodeBinary(int binary, int shift) // 8002D364 { int i; @@ -166,12 +197,12 @@ static void MakeExtraBinary(int binary, int shift) // 8002D364 /* ======================== = -= RescanByte += ReadCodeBinary -> old RescanByte = ======================== */ -static int RescanByte(int byte) // 8002D3B8 +static int ReadCodeBinary(int byte) // 8002D3B8 { int shift; int i; @@ -181,12 +212,12 @@ static int RescanByte(int byte) // 8002D3B8 i = 0; shift = 1; - if(byte <= 0) + if (byte <= 0) return resultbyte; do { - if (DecodeScan() != 0) + if (ReadBinary() != 0) resultbyte |= shift; i++; @@ -199,67 +230,61 @@ static int RescanByte(int byte) // 8002D3B8 /* ======================== = -= WriteEndCode += FlushBitBuffer = routine required for encoding = ======================== */ -static void WriteEndCode(void) // 8002D424 +static void FlushBitBuffer(void) // 8002D424 { - if (decoder.var2 > 0) { - WriteOutput((byte)(decoder.var3 << (8 - decoder.var2)) & 0xff); + if (buffers.enc_bit_count > 0) { + WriteByte((byte)(buffers.enc_bit_buffer << (8 - buffers.enc_bit_count)) & 0xff); } } /* ======================== = -= InitDecodeTable += InitTables -> old InitDecodeTable = ======================== */ -static void InitDecodeTable(void) // 8002D468 +static void InitTables(void) // 8002D468 { - int evenVal, oddVal, incrVal; + int evenVal, oddVal, incrVal, i; - short *curArray; - short *incrTbl; - short *evenTbl; - short *oddTbl; + short* curArray; + short* incrTbl; + short* evenTbl; + short* oddTbl; - tableVar01[15] = 3; - tableVar01[16] = 0; - tableVar01[17] = 0; + int* Tbl1, * Tbl2; - decoder.var0 = 0; - decoder.var1 = 0; - decoder.var2 = 0; - decoder.var3 = 0; + encArgs.incrBit = 3; + encArgs.unk1 = 0; + encArgs.type = 0; - curArray = &array01[2]; - incrTbl = &DecodeTable[0x4F2]; + buffers.dec_bit_count = 0; + buffers.dec_bit_buffer = 0; + buffers.enc_bit_count = 0; + buffers.enc_bit_buffer = 0; - incrVal = 2; + curArray = &array01[(0 + 2)]; + incrTbl = &DecodeTable[(1258 + 2)]; - do - { - if(incrVal < 0) { - *incrTbl = (short)((incrVal + 1) >> 1); - } - else { - *incrTbl = (short)(incrVal >> 1); - } + incrVal = 2; + do { + *incrTbl++ = (short)(incrVal / 2); *curArray++ = 1; - incrTbl++; - } while(++incrVal < 1258); + } while (++incrVal < 1258); - oddTbl = &DecodeTable[0x279]; - evenTbl = &DecodeTable[1]; + oddTbl = &DecodeTable[(629 + 1)]; + evenTbl = &DecodeTable[(0 + 1)]; - evenVal = 2; + evenVal = 1; oddVal = 3; do @@ -267,38 +292,22 @@ static void InitDecodeTable(void) // 8002D468 *oddTbl++ = (short)oddVal; oddVal += 2; - *evenTbl++ = (short)evenVal; - evenVal += 2; - - } while(oddVal < 1259); + *evenTbl++ = (short)(evenVal * 2); + evenVal++; + } while (evenVal < 629); - tableVar01[0] = 0; - - incrVal = (1 << ShiftTable[0]); - tableVar01[6] = (incrVal - 1); - tableVar01[1] = incrVal; - - incrVal += (1 << ShiftTable[1]); - tableVar01[7] = (incrVal - 1); - tableVar01[2] = incrVal; - - incrVal += (1 << ShiftTable[2]); - tableVar01[8] = (incrVal - 1); - tableVar01[3] = incrVal; - - incrVal += (1 << ShiftTable[3]); - tableVar01[9] = (incrVal - 1); - tableVar01[4] = incrVal; - - incrVal += (1 << ShiftTable[4]); - tableVar01[10] = (incrVal - 1); - tableVar01[5] = incrVal; - - incrVal += (1 << ShiftTable[5]); - tableVar01[11] = (incrVal - 1); - tableVar01[12] = (incrVal - 1); + incrVal = 0; + i = 0; + Tbl2 = &offsetTable[6]; + Tbl1 = &offsetTable[0]; + do { + *Tbl1++ = incrVal; + incrVal += (1 << (ShiftTable[i] & 0x1f)); + *Tbl2++ = incrVal - 1; + } while (++i <= 5); - tableVar01[13] = tableVar01[12] + 64; + offsetMaxSize = incrVal - 1; + windowSize = offsetMaxSize + (64 - 1); } /* @@ -309,20 +318,20 @@ static void InitDecodeTable(void) // 8002D468 ======================== */ -static void CheckTable(int a0,int a1,int a2) // 8002D624 +static void CheckTable(int a0, int a1, int a2) // 8002D624 { int i; int idByte1; int idByte2; - short *curArray; - short *evenTbl; - short *oddTbl; - short *incrTbl; + short* curArray; + short* evenTbl; + short* oddTbl; + short* incrTbl; i = 0; evenTbl = &DecodeTable[0]; - oddTbl = &DecodeTable[0x278]; - incrTbl = &DecodeTable[0x4F0]; + oddTbl = &DecodeTable[629]; + incrTbl = &DecodeTable[1258]; idByte1 = a0; @@ -333,21 +342,21 @@ static void CheckTable(int a0,int a1,int a2) // 8002D624 a0 = idByte2; - if(idByte2 != 1) { + if (idByte2 != 1) { idByte1 = incrTbl[idByte2]; idByte2 = evenTbl[idByte1]; a1 = idByte2; - if(a0 == idByte2) { + if (a0 == idByte2) { a1 = oddTbl[idByte1]; } } idByte1 = a0; - }while(a0 != 1); + } while (a0 != 1); - if(array01[1] != 0x7D0) { + if (array01[1] != 0x7D0) { return; } @@ -362,18 +371,18 @@ static void CheckTable(int a0,int a1,int a2) // 8002D624 curArray[0] >>= 1; curArray += 4; i += 4; - } while(i != 1256); + } while (i != 1256); } /* ======================== = -= DecodeByte += UpdateTables -> old DecodeByte = ======================== */ -static void DecodeByte(int tblpos) // 8002D72C +static void UpdateTables(int tblpos) // 8002D72C { int incrIdx; int evenVal; @@ -382,14 +391,14 @@ static void DecodeByte(int tblpos) // 8002D72C int idByte3; int idByte4; - short *evenTbl; - short *oddTbl; - short *incrTbl; - short *tmpIncrTbl; + short* evenTbl; + short* oddTbl; + short* incrTbl; + short* tmpIncrTbl; evenTbl = &DecodeTable[0]; - oddTbl = &DecodeTable[0x278]; - incrTbl = &DecodeTable[0x4F0]; + oddTbl = &DecodeTable[629]; + incrTbl = &DecodeTable[1258]; idByte1 = (tblpos + 0x275); array01[idByte1] += 1; @@ -465,17 +474,16 @@ static void DecodeByte(int tblpos) // 8002D72C static int StartDecodeByte(void) // 8002D904 { int lookup; - short *evenTbl; - short *oddTbl; + short* evenTbl; + short* oddTbl; lookup = 1; evenTbl = &DecodeTable[0]; - oddTbl = &DecodeTable[0x278]; + oddTbl = &DecodeTable[629]; - while(lookup < 0x275) - { - if(DecodeScan() == 0) { + while (lookup < 0x275) { + if (ReadBinary() == 0) { lookup = evenTbl[lookup]; } else { @@ -484,7 +492,7 @@ static int StartDecodeByte(void) // 8002D904 } lookup = (lookup + -0x275); - DecodeByte(lookup); + UpdateTables(lookup); return lookup; } @@ -492,161 +500,134 @@ static int StartDecodeByte(void) // 8002D904 /* ======================== = -= L8002d990 -= unknown Function += InsertNodeDirectory += routine required for encoding = ======================== */ -void L8002d990(int arg0) // 8002D990 +void InsertNodeDirectory(int start) // 8002D990 { - int val; - - val = ((allocPtr[(arg0 + 2) % tableVar01[13]] << 8) ^ (allocPtr[arg0] ^ (allocPtr[(arg0+1) % tableVar01[13]] << 4))) & 0x3fff; + int hashKey = ((window[start % windowSize] ^ (window[(start + 1) % windowSize] << 4)) ^ (window[(start + 2) % windowSize] << 8)) & (HASH_SIZE - 1); - if (PtrEvenTbl[val] == -1) - { - PtrOddTbl[val] = arg0; - PtrNumTbl1[arg0] = -1; - } - else - { - PtrNumTbl1[arg0] = PtrEvenTbl[val]; - PtrNumTbl2[PtrEvenTbl[val]] = arg0; - } + if (hashtable[hashKey] == -1) { + hashtarget[hashKey] = start; + hashNext[start] = -1; + } + else { + hashNext[start] = hashtable[hashKey]; + hashPrev[hashtable[hashKey]] = start; + } - PtrEvenTbl[val] = arg0; - PtrNumTbl2[arg0] = -1; + hashtable[hashKey] = start; + hashPrev[start] = -1; } /* ======================== = -= FUN_8002dad0 -= unknown Function += DeleteNodeDirectory += routine required for encoding = ======================== */ -void FUN_8002dad0(int arg0) // 8002DAD0 +void DeleteNodeDirectory(int start) // 8002DAD0 { - int val; - - val = ((allocPtr[(arg0 + 2) % tableVar01[13]] << 8) ^ (allocPtr[arg0] ^ (allocPtr[(arg0+1) % tableVar01[13]] << 4))) & 0x3fff; + int hashKey = ((window[start % windowSize] ^ (window[(start + 1) % windowSize] << 4)) ^ (window[(start + 2) % windowSize] << 8)) & (HASH_SIZE - 1); - if (PtrEvenTbl[val] == PtrOddTbl[val]) - { - PtrEvenTbl[val] = -1; - } - else - { - PtrNumTbl1[PtrNumTbl2[PtrOddTbl[val]]] = -1; - PtrOddTbl[val] = PtrNumTbl2[PtrOddTbl[val]]; - } + if (hashtable[hashKey] == hashtarget[hashKey]) { + hashtable[hashKey] = -1; + } + else { + hashNext[hashPrev[hashtarget[hashKey]]] = -1; + hashtarget[hashKey] = hashPrev[hashtarget[hashKey]]; + } } /* ======================== = -= FUN_8002dc0c -= unknown Function += FindMatch += routine required for encoding = ======================== */ -int FUN_8002dc0c(int start, int count) // 8002DC0C -{ - short sVar1; - int iVar2; - int iVar4; - int iVar5; - int iVar6; - int cnt; - int curr, next; - - iVar4 = 0; - if (start == tableVar01[13]) { +int FindMatch(int start, int count) // 8002DC0C +{ + int encodedlen; + int offset; + int i; + int samelen; + int next; + int curr; + int encodedpos; + int hashKey; + + encodedlen = 0; + if (start == windowSize) { start = 0; } - sVar1 = PtrEvenTbl[(allocPtr[(start + 2) % tableVar01[13]] << 8 ^ allocPtr[start] ^ allocPtr[(start + 1) % tableVar01[13]] << 4) & 0x3fff]; + hashKey = ((window[start % windowSize] ^ (window[(start + 1) % windowSize] << 4)) ^ (window[(start + 2) % windowSize] << 8)) & (HASH_SIZE - 1); - iVar5 = 1; - do + offset = hashtable[hashKey]; + + i = 0; + while (offset != -1) { - iVar2 = (int)sVar1; - if ((iVar2 == -1) || (count < iVar5)) { - return iVar4; + if (++i > count) { + break; } - if ((allocPtr[(start + iVar4) % tableVar01[13]]) == - (allocPtr[(iVar2 + iVar4) % tableVar01[13]])) + if ((window[(start + encodedlen) % windowSize]) == (window[(offset + encodedlen) % windowSize])) { - cnt = 0; - if (allocPtr[start] == allocPtr[iVar2]) - { - curr = start; - next = iVar2; - - if(next != start) - { - while (curr != tableVar01[15]) - { - curr++; - if (curr == tableVar01[13]) { - curr = 0; - } - - next++; - if (next == tableVar01[13]) { - next = 0; - } - - cnt++; - - if (allocPtr[curr] != allocPtr[next]) - break; + samelen = 0; + curr = start; + next = offset; - if (cnt >= 64) - break; - - if (next == start) - break; - } + while (window[curr] == window[next]) { + if (samelen >= 64) { + break; + } + if (next == start) { + break; + } + if (curr == encArgs.incrBit) { + break; + } + ++samelen; + if (++curr == windowSize) { + curr = 0; + } + if (++next == windowSize) { + next = 0; } } - iVar6 = start - iVar2; - if (iVar6 < 0) { - iVar6 += tableVar01[13]; + encodedpos = start - offset; + if (encodedpos < 0) { + encodedpos += windowSize; } - - iVar6 -= cnt; - if (tableVar01[16] && (tableVar01[6]/*15*/ < iVar6)) { - return iVar4; + encodedpos -= samelen; + if ((encArgs.unk1) && (encodedpos > offsetTable[6])) { + break; } - //if (((iVar4 < cnt) && (iVar6 <= tableVar01[12])) && - //((3 < cnt || (iVar6 <= tableVar01[tableVar01[17] + 9])))) - if(iVar4 < cnt) - { - if(iVar6 <= tableVar01[12]) - { - if((cnt > 3) || (iVar6 <= tableVar01[tableVar01[17] + 9])) - { - iVar4 = cnt; - tableVar01[14] = iVar6; - } - } + if (encodedlen < samelen && encodedpos <= offsetMaxSize && (samelen > 3 || offsetTable[6 + (encArgs.type + 3)] >= encodedpos)) { + encodedlen = samelen; + encArgs.offset = encodedpos; } } - sVar1 = PtrNumTbl1[iVar2]; - iVar5++; - } while( true ); + offset = hashNext[offset]; // try next in list + } + return encodedlen; } + /* ======================== = @@ -661,24 +642,24 @@ void FUN_8002df14(void) // 8002DF14 byte byte_val; int i, j, k; - byte *curPtr; - byte *nextPtr; - byte *next2Ptr; + byte* curPtr; + byte* nextPtr; + byte* next2Ptr; - curPtr = &allocPtr[0]; + curPtr = &window[0]; k = 0; j = 0; i = 1; do { - nextPtr = &allocPtr[j]; + nextPtr = &window[j]; if (curPtr[0] == 10) { j = i; - if(nextPtr[0] == curPtr[1]) + if (nextPtr[0] == curPtr[1]) { - next2Ptr = &allocPtr[i+1]; + next2Ptr = &window[i + 1]; do { nextPtr++; @@ -691,10 +672,12 @@ void FUN_8002df14(void) // 8002DF14 i++; } while (i != 67); - if (k >= 16) - tableVar01[16] = 1; + if (k >= 16) { + encArgs.unk1 = 1; + } } + /* ======================== = @@ -705,49 +688,47 @@ void FUN_8002df14(void) // 8002DF14 ======================== */ -void DecodeD64(unsigned char *input, unsigned char *output) // 8002DFA0 +void DecodeD64(unsigned char* input, unsigned char* output) // 8002DFA0 { int copyPos, storePos; - int dec_byte, resc_byte; - int incrBit, copyCnt, shiftPos, j; + int dec_byte, resc_byte; + int incrBit, copyCnt, shiftPos, j; - //PRINTF_D2(WHITE, 0, 15, "DecodeD64"); + //PRINTF_D2(WHITE, 0, 15, "DecodeD64"); - InitDecodeTable(); + InitTables(); - OVERFLOW_READ = MAXINT; + OVERFLOW_READ = MAXINT; OVERFLOW_WRITE = MAXINT; - incrBit = 0; + incrBit = 0; - decoder.read = input; - decoder.readPos = input; - decoder.write = output; - decoder.writePos = output; + buffers.input = buffers.istart = input; + buffers.output = buffers.ostart = output; - allocPtr = (byte *)Z_Alloc(tableVar01[13], PU_STATIC, NULL); + window = (byte *)Z_Alloc(windowSize, PU_STATIC, NULL); dec_byte = StartDecodeByte(); - while(dec_byte != 256) + while (dec_byte != 256) { - if(dec_byte < 256) + if (dec_byte < 256) { - /* Decode the data directly using binary data code */ + /* Decode the data directly using binary data code */ - WriteOutput((byte)(dec_byte & 0xff)); - allocPtr[incrBit] = (byte)dec_byte; + WriteByte((byte)(dec_byte & 0xff)); + window[incrBit] = (byte)dec_byte; - /* Resets the count once the memory limit is exceeded in allocPtr, + /* Resets the count once the memory limit is exceeded in allocPtr, so to speak resets it at startup for reuse */ incrBit += 1; - if(incrBit == tableVar01[13]) { + if (incrBit == windowSize) { incrBit = 0; } } else { - /* Decode the data using binary data code, + /* Decode the data using binary data code, a count is obtained for the repeated data, positioning itself in the root that is being stored in allocPtr previously. */ @@ -755,59 +736,292 @@ void DecodeD64(unsigned char *input, unsigned char *output) // 8002DFA0 necessary to obtain a shift value in the ShiftTable*/ shiftPos = (dec_byte + -257) / 62; - /* get a count number for data to copy */ - copyCnt = (dec_byte - (shiftPos * 62)) + -254; + /* Get a count number for data to copy */ + copyCnt = (dec_byte - (shiftPos * 62)) + -254; /* To start copying data, you receive a position number that you must sum with the position of table tableVar01 */ - resc_byte = RescanByte(ShiftTable[shiftPos]); + resc_byte = ReadCodeBinary(ShiftTable[shiftPos]); /* with this formula the exact position is obtained to start copying previously stored data */ - copyPos = incrBit - ((tableVar01[shiftPos] + resc_byte) + copyCnt); + copyPos = incrBit - ((offsetTable[shiftPos] + resc_byte) + copyCnt); - if(copyPos < 0) { - copyPos += tableVar01[13]; + if (copyPos < 0) { + copyPos += windowSize; } storePos = incrBit; - for(j = 0; j < copyCnt; j++) + for (j = 0; j < copyCnt; j++) { /* write the copied data */ - WriteOutput(allocPtr[copyPos]); + WriteByte(window[copyPos]); /* save copied data at current position in memory allocPtr */ - allocPtr[storePos] = allocPtr[copyPos]; + window[storePos] = window[copyPos]; storePos++; /* advance to next allocPtr memory block to store */ copyPos++; /* advance to next allocPtr memory block to copy */ /* reset the position of storePos once the memory limit is exceeded */ - if(storePos == tableVar01[13]) { + if (storePos == windowSize) { storePos = 0; } /* reset the position of copyPos once the memory limit is exceeded */ - if(copyPos == tableVar01[13]) { + if (copyPos == windowSize) { copyPos = 0; } } - /* Resets the count once the memory limit is exceeded in allocPtr, + /* Resets the count once the memory limit is exceeded in allocPtr, so to speak resets it at startup for reuse */ incrBit += copyCnt; - if (incrBit >= tableVar01[13]) { - incrBit -= tableVar01[13]; + if (incrBit >= windowSize) { + incrBit -= windowSize; } } dec_byte = StartDecodeByte(); } - Z_Free(allocPtr); + Z_Free(window); + + //PRINTF_D2(WHITE, 0, 21, "DecodeD64:End"); +} + +// ENCODE MODE BY GEC Erick Vasquez Garcia (ERICK194) +// Updated version, compresses too fast and exact. + +void StartEncodeCode(int lookup) +{ + // Encodes data from a table + int lookupCode, lookupCheck; + short* oddTbl; + short* incrTbl; + int binCnt = 0; + byte binary[64]; + //static std::vector<byte> binary; + + //binary.clear(); + oddTbl = &DecodeTable[629]; + incrTbl = &DecodeTable[1258]; + + lookupCode = lookup + 0x275; + while (1) { + + if (lookupCode <= 1) { break; } + + lookupCheck = oddTbl[incrTbl[lookupCode]]; + + //binary.push_back((lookupCheck == lookupCode) ? 1 : 0); + binary[binCnt++] = (lookupCheck == lookupCode) ? 1 : 0; + + lookupCode = incrTbl[lookupCode]; + }; + + // Write bits in bytes + while (binCnt) { + WriteBinary(binary[--binCnt]); + } + + /*auto it = binary.rbegin(); + for (int k = 0; k < (int)binary.size(); k++) { + WriteBinary(*it++); + }*/ + + // Update table + UpdateTables(lookup); +} + +unsigned char* EncodeD64(unsigned char* input, int inputlen, int* size) { + int i, readPos, nodePos, looKupCode, byteData; + int cpyCountNext, cpyCount, cntMin, cntMax; + boolean deleteNode, skipCopy; + + unsigned char* output = (unsigned char*)malloc(inputlen * 2); + + InitTables(); + + OVERFLOW_READ = inputlen; + OVERFLOW_WRITE = inputlen * 2; + + deleteNode = false; + skipCopy = false; + readPos = encArgs.incrBit; + nodePos = 0; + + buffers.input = buffers.istart = input; + buffers.output = buffers.ostart = output; + + hashtable = (short*)Z_Alloc(HASH_SIZE * sizeof(short), PU_STATIC, NULL); + hashtarget = (short*)Z_Alloc(HASH_SIZE * sizeof(short), PU_STATIC, NULL); + hashNext = (short*)Z_Alloc(windowSize * sizeof(short), PU_STATIC, NULL); + hashPrev = (short*)Z_Alloc(windowSize * sizeof(short), PU_STATIC, NULL); + D_memset(hashNext, 0, windowSize * sizeof(short)); + D_memset(hashPrev, 0, windowSize * sizeof(short)); + + window = (byte*)malloc(windowSize * sizeof(byte)); + D_memset(window, 0, windowSize * sizeof(byte)); + + // Initializes hash encoding tables + for (i = 0; i < HASH_SIZE; i++) { + hashtable[i] = -1; + hashtarget[i] = -1; + } + + // Copy the first 3 bytes in the data window + for (i = 0; i < encArgs.incrBit; i++) { + byteData = ReadByte(); + if (byteData != -1) { + // Encode a simple byte data. + StartEncodeCode(byteData); + window[i] = byteData; + } + } + + if (GetReadSize() < OVERFLOW_READ) { // Does not copy any data if the input data reached the limit + // Copy the first 64 bytes in the data window + for (i = 0; i < 64; i++) { + byteData = ReadByte(); + + // For some unknown reason if a byte is greater than or equal to 128 the form of the encoding changes + // This happens depending on the file an example the BLANK and SPACEO texture results in 0 + // Textures such as C101, result in 1 + // MAP01, result in 1 + if (byteData >= 128) { + encArgs.type = 1; + } + + if (byteData != -1) { + window[encArgs.incrBit++] = byteData; + } + } + } + + // Determines the number of bytes to compare + cntMin = (encArgs.type == 1) ? 20 : 50; + cntMax = (encArgs.type == 1) ? 200 : 1000; + + if (GetReadSize() < OVERFLOW_READ) { // Does not encode any data if the input data reached the limit + + while (readPos != encArgs.incrBit) { + // Add the data in the node directory table + // update the hash table + InsertNodeDirectory(nodePos); + + if (!skipCopy) { + + cpyCountNext = FindMatch(readPos + 1, cntMin); + cpyCount = FindMatch(readPos, cntMax); + + //printf("cpyCount %d\n", cpyCount); + //printf("cpyCountNext %d\n", cpyCountNext); + + // Check if there is a possibility to copy the data by routes + if (cpyCount >= 3 && cpyCount >= cpyCountNext) { + + int count = cpyCount; + int ValExtra = encArgs.offset; + int Shift = 0x04; + + if ((ValExtra >= offsetTable[1]) && (ValExtra < offsetTable[2])) + { + Shift = 0x06; + ValExtra -= offsetTable[1]; + } + if ((ValExtra >= offsetTable[2]) && (ValExtra < offsetTable[3])) + { + Shift = 0x08; + ValExtra -= offsetTable[2]; + } + if ((ValExtra >= offsetTable[3]) && (ValExtra < offsetTable[4])) + { + Shift = 0x0A; + ValExtra -= offsetTable[3]; + } + if ((ValExtra >= offsetTable[4]) && (ValExtra < offsetTable[5])) + { + Shift = 0x0C; + ValExtra -= offsetTable[4]; + } + if ((ValExtra >= offsetTable[5])) + { + Shift = 0x0E; + ValExtra -= offsetTable[5]; + } + + if (Shift == 0x04) { looKupCode = (0x0101 + (count - 3)); } + else if (Shift == 0x06) { looKupCode = (0x013F + (count - 3)); } + else if (Shift == 0x08) { looKupCode = (0x017D + (count - 3)); } + else if (Shift == 0x0A) { looKupCode = (0x01BB + (count - 3)); } + else if (Shift == 0x0C) { looKupCode = (0x01F9 + (count - 3)); } + else if (Shift == 0x0E) { looKupCode = (0x0237 + (count - 3)); } + + //printf("Code 0x%04X ValExtra 0x%04X\n", LooKupCode2, ValExtra); + + // Writes the startup code and address to copy data from the data window. + StartEncodeCode(looKupCode); + // Writes the amount of data to copy from the data window. + WriteCodeBinary(ValExtra, Shift); + + skipCopy = true; + } + else { // Encode a simple byte data. + StartEncodeCode(window[readPos]); + } + } + + // Skip copy data + if (--cpyCount == 0) { + skipCopy = false; + } + + // Advance to the next position to check in matching + if (++readPos == windowSize) { + readPos = 0; + } + + // Advance to the next position to add to the nodes of the directory + if (++nodePos == windowSize) { + nodePos = 0; + } + + // Copy input data to the data window + if (GetReadSize() < OVERFLOW_READ) { // Does not copy any data if the input data reached the limit + byteData = ReadByte(); + if (byteData != -1) { + window[encArgs.incrBit++] = byteData; + } + + // Enables the deletion of nodes in the directory once the first block of the data window is reached + if (encArgs.incrBit == windowSize) { + encArgs.incrBit = 0; + deleteNode = true; + } + } + + // Delete the data in the node directory table + if (deleteNode && GetReadSize() < OVERFLOW_READ) { + DeleteNodeDirectory(encArgs.incrBit); + } + } + } + + // Write the code to finish the encoding + StartEncodeCode(0x100); + FlushBitBuffer(); + + *size = GetOutputSize(); + + Z_Free(hashtable); + Z_Free(hashtarget); + Z_Free(hashNext); + Z_Free(hashPrev); + Z_Free(window); - //PRINTF_D2(WHITE, 0, 21, "DecodeD64:End"); + return output; } /* diff --git a/doom64/doomdef.h b/doom64/doomdef.h @@ -698,6 +698,11 @@ void *W_GetMapLump(int lump); void DecodeD64(unsigned char *input, unsigned char *output); void DecodeJaguar(unsigned char *input, unsigned char *output); +/*---------*/ +/* ENCODES */ +/*---------*/ +unsigned char* EncodeD64(unsigned char* input, int inputlen, int* size); + /*------------*/ /* BASE LEVEL */ /*------------*/