CE Checksum Algorithm

[Btcc22]

Needed the map checksum algorithm but couldn't find any information on it so I had to reverse it. Posting an example implementation should anybody else find themselves wanting it for any of their projects (hint: map editors that update the checksum). Shouldn't be a problem to port it to other languages.


Error checks removed for brevity.
Make sure invalid data isn't going to make your code do something stupid.
Longs and pointers are 32 bits here.
You'll also be better off using a memory mapped file for this rather than all of the seeks and reads but I wanted the example to be easy to follow.



//typedef unsigned int DWORD;
//typedef unsigned char BYTE;

struct TagEntry {
DWORD Class0;
DWORD Class1;
DWORD Class2;
long TagID;
char* TagNameAddress;
long TagStruct;
char Unknown[8];
};

struct TagTableHeader {
long TagTableEntryPointer;
long FirstTagID;
long MapID;
long TagCount;
long VerticesCount;
long VerticesOffset;
long IndicesCount;
long IndicesOffset;
long ModelDataSize;
long Signature;
};

struct BSPChunkMeta {
DWORD offset;
DWORD size;
};

//Just made this up
struct SceneryTag {
DWORD sections;
DWORD address;
};

struct MapHeader {
long Signature0; // head = "daeh"
short Game; // Xbox = 5 / Trial = 6 / PC = 7 / CE = 0x261
short Unknown0;
long MapSize;
char Unknown1[4];
long IndexOffset;
long MetaSize;
char Unknown3[8];
char MapName[14];
char Unknown4[18];
char Build[12]; // PC = 01.00.00.0564 / CE = 01.00.00.0609
char Unknown5[20];
char MapType; // SP = 0 / MP = 1 / UI = 2
char Unknown6;
short Unknown7;
int checksum;
char Unknown8[1940];
long Signature1; // foot = "toof"
};

DWORD xorChunk(DWORD checksum, BYTE* data, DWORD length, DWORD* xorBuff) {
for(DWORD i = 0; i < length; i++) {
int byte = data[i];
byte ^= checksum;
byte &= 255;
byte = xorBuff[byte];
checksum /= 256;
checksum ^= byte;
}
return checksum;
}

void generateXorBuff(DWORD* buffer) {
for(DWORD i = 0, val = 0; i < 256; i++, val = i) {
for(int j = 0; j < 8; j++) {
if(val % 2 == 1) {
val /= 2;
val ^= 0xEDB88320;
} else {
val /= 2;
}
}
buffer[i] = val;
}
}

DWORD checksum(FILE* handle) {
MapHeader header;
TagEntry tag;
SceneryTag scenery;
BSPChunkMeta bspMeta;
DWORD checksum = -1;
BYTE* chunk;
DWORD* xorBuffer = new DWORD[256];

generateXorBuff(xorBuffer);

//Read the map header
rewind(handle);
fread(&header, sizeof(MapHeader), 1, handle);

//Read the index
TagTableHeader index;
fseek(handle, header.IndexOffset, SEEK_SET);
fread(&index, sizeof(TagTableHeader), 1, handle);

//Calculate 'rebase' value
DWORD magic = (index.TagTableEntryPointer - header.IndexOffset) - 40;

//Checksum SBSPs - bless this mess
DWORD scenario = index.TagTableEntryPointer - magic;
fseek(handle, scenario, SEEK_SET);
fread(&tag, sizeof(TagEntry), 1, handle);
DWORD scnrMetaOffset = (tag.TagStruct - magic) + 0x5A4;

fseek(handle, scnrMetaOffset, SEEK_SET);
fread(&scenery, sizeof(SceneryTag), 1, handle);

for(DWORD i = 0; i < scenery.sections; i++) {
DWORD bspMetaOffset = ((scenery.address - magic) + (i * 32));
fseek(handle, bspMetaOffset, SEEK_SET);
fread(&bspMeta, sizeof(bspMeta), 1, handle);

//Read BSP
fseek(handle, bspMeta.offset, SEEK_SET);
chunk = new BYTE[bspMeta.size];
fread(chunk, bspMeta.size, 1, handle);

//Checksum BSP
checksum = xorChunk(checksum, chunk, bspMeta.size, xorBuffer);
delete[] chunk;
}

//Load model data
fseek(handle, index.VerticesOffset, SEEK_SET);
chunk = new BYTE[index.ModelDataSize];
fread(chunk, index.ModelDataSize, 1, handle);

//Checksum model data
checksum = xorChunk(checksum, chunk, index.ModelDataSize, xorBuffer);
delete[] chunk;

//Load tag index
DWORD tagOffset = header.IndexOffset;
chunk = new BYTE[header.MetaSize];
fseek(handle, tagOffset, SEEK_SET);
fread(chunk, 1, header.MetaSize, handle);

//Checksum tag index
checksum = xorChunk(checksum, chunk, header.MetaSize, xorBuffer);
delete[] chunk;

delete[] xorBuffer;

return checksum;
}

[Kornman00]

Bungie has been using the same CRC32 algorithm since before Halo http://code.google.com/p/open-sauce/source/browse/OpenSauce/shared/Include/YeloLib/memory/memory_interface_base.cpp#195

[Btcc22]

I figured OS would have it somewhere in that vast codebase but I couldn't find any actual usage of it for checksumming the maps, although it doesn't help that Google Code's search feature is borderline useless.

This implementation is higher level anyway and it doesn't hurt to have more. :)

[Kornman00]

Yeah, we've had the actual checksum logic documented for a few months now: http://code.google.com/p/open-sauce/source/browse/OpenSauce/Halo1/Halo1_CE/TagGroups/CacheFiles.CRC.inl

[Btcc22]

Ah. Too bad Google Code's search feature doesn't seem to return that file when searching with relevant keywords.