PDA

View Full Version : [INFO] Space Marine custom 64bit-hash algorithm



Copernicus
13th Sep 11, 8:31 AM
This post won't be of any use to anyone besides those writing tools for Space Marine.
Space Marine uses a custom (at least I believe it is) 64-bit hashing algorithm to hash certain things, e.g. type names in OPPC files or strings in BOD files. Hopefully this hashing algorithm will allow us to load custom BOD files at some point in the future.
Here's a C# implementation of the 64-bit hashing algorithm used by Space Marine (reversed from the demo):

Note: Convert strings to lower case before hashing to get correct results. In the grim dark future of the 41st millennium, there is only lower-case.



// 512 entries
private static readonly uint[] s_hashData = {
0x0, 0x0, 0x5800C, 0x1A1561E, 0x0B0018, 0x342AC3C, 0x0E8014, 0x2E3FA22,
0x160030, 0x6855878, 0x13803C, 0x7240E66, 0x1D0028, 0x5C7F444, 0x188024,
0x466A25A, 0x2C0060, 0x0D0AB0F0, 0x29806C, 0x0CABE6EE, 0x270078,
0x0E481CCC, 0x228074, 0x0FE94AD2, 0x3A0050, 0x0B8FE888, 0x3F805C,
0x0A2EBE96, 0x310048, 0x8CD44B4, 0x348044, 0x96C12AA, 0x5800C0,
0x1A1561E0, 0x5D80CC, 0x1BB437FE, 0x5300D8, 0x1957CDDC, 0x5680D4,
0x18F69BC2, 0x4E00F0, 0x1C903998, 0x4B80FC, 0x1D316F86, 0x4500E8,
0x1FD295A4, 0x4080E4, 0x1E73C3BA, 0x7400A0, 0x171FD110, 0x7180AC,
0x16BE870E, 0x7F00B8, 0x145D7D2C, 0x7A80B4, 0x15FC2B32, 0x620090,
0x119A8968, 0x67809C, 0x103BDF76, 0x690088, 0x12D82554, 0x6C8084,
0x1379734A, 0x0B00180, 0x342AC3C0, 0x0B5818C, 0x358B95DE, 0x0BB0198,
0x37686FFC, 0x0BE8194, 0x36C939E2, 0x0A601B0, 0x32AF9BB8, 0x0A381BC,
0x330ECDA6, 0x0AD01A8, 0x31ED3784, 0x0A881A4, 0x304C619A, 0x9C01E0,
0x39207330, 0x9981EC, 0x3881252E, 0x9701F8, 0x3A62DF0C, 0x9281F4,
0x3BC38912, 0x8A01D0, 0x3FA52B48, 0x8F81DC, 0x3E047D56, 0x8101C8,
0x3CE78774, 0x8481C4, 0x3D46D16A, 0x0E80140, 0x2E3FA220, 0x0ED814C,
0x2F9EF43E, 0x0E30158, 0x2D7D0E1C, 0x0E68154, 0x2CDC5802, 0x0FE0170,
0x28BAFA58, 0x0FB817C, 0x291BAC46, 0x0F50168, 0x2BF85664, 0x0F08164,
0x2A59007A, 0x0C40120, 0x233512D0, 0x0C1812C, 0x229444CE, 0x0CF0138,
0x2077BEEC, 0x0CA8134, 0x21D6E8F2, 0x0D20110, 0x25B04AA8, 0x0D7811C,
0x24111CB6, 0x0D90108, 0x26F2E694, 0x0DC8104, 0x2753B08A, 0x1600300,
0x68558780, 0x165830C, 0x69F4D19E, 0x16B0318, 0x6B172BBC, 0x16E8314,
0x6AB67DA2, 0x1760330, 0x6ED0DFF8, 0x173833C, 0x6F7189E6, 0x17D0328,
0x6D9273C4, 0x1788324, 0x6C3325DA, 0x14C0360, 0x655F3770, 0x149836C,
0x64FE616E, 0x1470378, 0x661D9B4C, 0x1428374, 0x67BCCD52, 0x15A0350,
0x63DA6F08, 0x15F835C, 0x627B3916, 0x1510348, 0x6098C334, 0x1548344,
0x6139952A, 0x13803C0, 0x7240E660, 0x13D83CC, 0x73E1B07E, 0x13303D8,
0x71024A5C, 0x13683D4, 0x70A31C42, 0x12E03F0, 0x74C5BE18, 0x12B83FC,
0x7564E806, 0x12503E8, 0x77871224, 0x12083E4, 0x7626443A, 0x11403A0,
0x7F4A5690, 0x11183AC, 0x7EEB008E, 0x11F03B8, 0x7C08FAAC, 0x11A83B4,
0x7DA9ACB2, 0x1020390, 0x79CF0EE8, 0x107839C, 0x786E58F6, 0x1090388,
0x7A8DA2D4, 0x10C8384, 0x7B2CF4CA, 0x1D00280, 0x5C7F4440, 0x1D5828C,
0x5DDE125E, 0x1DB0298, 0x5F3DE87C, 0x1DE8294, 0x5E9CBE62, 0x1C602B0,
0x5AFA1C38, 0x1C382BC, 0x5B5B4A26, 0x1CD02A8, 0x59B8B004, 0x1C882A4,
0x5819E61A, 0x1FC02E0, 0x5175F4B0, 0x1F982EC, 0x50D4A2AE, 0x1F702F8,
0x5237588C, 0x1F282F4, 0x53960E92, 0x1EA02D0, 0x57F0ACC8, 0x1EF82DC,
0x5651FAD6, 0x1E102C8, 0x54B200F4, 0x1E482C4, 0x551356EA, 0x1880240,
0x466A25A0, 0x18D824C, 0x47CB73BE, 0x1830258, 0x4528899C, 0x1868254,
0x4489DF82, 0x19E0270, 0x40EF7DD8, 0x19B827C, 0x414E2BC6, 0x1950268,
0x43ADD1E4, 0x1908264, 0x420C87FA, 0x1A40220, 0x4B609550, 0x1A1822C,
0x4AC1C34E, 0x1AF0238, 0x4822396C, 0x1AA8234, 0x49836F72, 0x1B20210,
0x4DE5CD28, 0x1B7821C, 0x4C449B36, 0x1B90208, 0x4EA76114, 0x1BC8204,
0x4F06370A, 0x2C00600, 0x0D0AB0F00, 0x2C5860C, 0x0D10A591E, 0x2CB0618,
0x0D3E9A33C, 0x2CE8614, 0x0D248F522, 0x2D60630, 0x0D62E5778, 0x2D3863C,
0x0D78F0166, 0x2DD0628, 0x0D56CFB44, 0x2D88624, 0x0D4CDAD5A, 0x2EC0660,
0x0DDA1BFF0, 0x2E9866C, 0x0DC00E9EE, 0x2E70678, 0x0DEE313CC, 0x2E28674,
0x0DF4245D2, 0x2FA0650, 0x0DB24E788, 0x2FF865C, 0x0DA85B196, 0x2F10648,
0x0D8664BB4, 0x2F48644, 0x0D9C71DAA, 0x29806C0, 0x0CABE6EE0, 0x29D86CC,
0x0CB1F38FE, 0x29306D8, 0x0C9FCC2DC, 0x29686D4, 0x0C85D94C2, 0x28E06F0,
0x0CC3B3698, 0x28B86FC, 0x0CD9A6086, 0x28506E8, 0x0CF799AA4, 0x28086E4,
0x0CED8CCBA, 0x2B406A0, 0x0C7B4DE10, 0x2B186AC, 0x0C615880E, 0x2BF06B8,
0x0C4F6722C, 0x2BA86B4, 0x0C5572432, 0x2A20690, 0x0C1318668, 0x2A7869C,
0x0C090D076, 0x2A90688, 0x0C2732A54, 0x2AC8684, 0x0C3D27C4A, 0x2700780,
0x0E481CCC0, 0x275878C, 0x0E5209ADE, 0x27B0798, 0x0E7C360FC, 0x27E8794,
0x0E66236E2, 0x26607B0, 0x0E20494B8, 0x26387BC, 0x0E3A5C2A6, 0x26D07A8,
0x0E1463884, 0x26887A4, 0x0E0E76E9A, 0x25C07E0, 0x0E98B7C30, 0x25987EC,
0x0E82A2A2E, 0x25707F8, 0x0EAC9D00C, 0x25287F4, 0x0EB688612, 0x24A07D0,
0x0EF0E2448, 0x24F87DC, 0x0EEAF7256, 0x24107C8, 0x0EC4C8874, 0x24487C4,
0x0EDEDDE6A, 0x2280740, 0x0FE94AD20, 0x22D874C, 0x0FF35FB3E, 0x2230758,
0x0FDD6011C, 0x2268754, 0x0FC775702, 0x23E0770, 0x0F811F558, 0x23B877C,
0x0F9B0A346, 0x2350768, 0x0FB535964, 0x2308764, 0x0FAF20F7A, 0x2040720,
0x0F39E1DD0, 0x201872C, 0x0F23F4BCE, 0x20F0738, 0x0F0DCB1EC, 0x20A8734,
0x0F17DE7F2, 0x2120710, 0x0F51B45A8, 0x217871C, 0x0F4BA13B6, 0x2190708,
0x0F659E994, 0x21C8704, 0x0F7F8BF8A, 0x3A00500, 0x0B8FE8880, 0x3A5850C,
0x0B95FDE9E, 0x3AB0518, 0x0BBBC24BC, 0x3AE8514, 0x0BA1D72A2, 0x3B60530,
0x0BE7BD0F8, 0x3B3853C, 0x0BFDA86E6, 0x3BD0528, 0x0BD397CC4, 0x3B88524,
0x0BC982ADA, 0x38C0560, 0x0B5F43870, 0x389856C, 0x0B4556E6E, 0x3870578,
0x0B6B6944C, 0x3828574, 0x0B717C252, 0x39A0550, 0x0B3716008, 0x39F855C,
0x0B2D03616, 0x3910548, 0x0B033CC34, 0x3948544, 0x0B1929A2A, 0x3F805C0,
0x0A2EBE960, 0x3FD85CC, 0x0A34ABF7E, 0x3F305D8, 0x0A1A9455C, 0x3F685D4,
0x0A0081342, 0x3EE05F0, 0x0A46EB118, 0x3EB85FC, 0x0A5CFE706, 0x3E505E8,
0x0A72C1D24, 0x3E085E4, 0x0A68D4B3A, 0x3D405A0, 0x0AFE15990, 0x3D185AC,
0x0AE400F8E, 0x3DF05B8, 0x0ACA3F5AC, 0x3DA85B4, 0x0AD02A3B2, 0x3C20590,
0x0A96401E8, 0x3C7859C, 0x0A8C557F6, 0x3C90588, 0x0AA26ADD4, 0x3CC8584,
0x0AB87FBCA, 0x3100480, 0x8CD44B40, 0x315848C, 0x8D751D5E, 0x31B0498,
0x8F96E77C, 0x31E8494, 0x8E37B162, 0x30604B0, 0x8A511338, 0x30384BC,
0x8BF04526, 0x30D04A8, 0x8913BF04, 0x30884A4, 0x88B2E91A, 0x33C04E0,
0x81DEFBB0, 0x33984EC, 0x807FADAE, 0x33704F8, 0x829C578C, 0x33284F4,
0x833D0192, 0x32A04D0, 0x875BA3C8, 0x32F84DC, 0x86FAF5D6, 0x32104C8,
0x84190FF4, 0x32484C4, 0x85B859EA, 0x3480440, 0x96C12AA0, 0x34D844C,
0x97607CBE, 0x3430458, 0x9583869C, 0x3468454, 0x9422D082, 0x35E0470,
0x904472D8, 0x35B847C, 0x91E524C6, 0x3550468, 0x9306DEE4, 0x3508464,
0x92A788FA, 0x3640420, 0x9BCB9A50, 0x361842C, 0x9A6ACC4E, 0x36F0438,
0x9889366C, 0x36A8434, 0x99286072, 0x3720410, 0x9D4EC228, 0x377841C,
0x9CEF9436, 0x3790408, 0x9E0C6E14, 0x37C8404, 0x9FAD380A
};

/// <summary>
/// Returns a 64bit hash value.
/// </summary>
public static byte[] CalculateHash(byte[] toHash)
{
uint firstPart = 0xFFFFFFFF;
uint secondPart = 0xFFFFFFFF;

for (int idx = 0; idx < toHash.Length; idx++)
{
byte current = toHash[idx];
int offset = (int) ((current ^ firstPart) & 0xFF); // XOR

firstPart = firstPart >> 8;
uint secondPartLastByte = (secondPart & 0x000000FF) << 24;
firstPart = firstPart | secondPartLastByte; // SHRD 8

secondPart = secondPart >> 8; // SHR 8

firstPart = firstPart ^ s_hashData[offset * 2];
secondPart = secondPart ^ s_hashData[(offset * 2) + 1];
}
int first32Bits = (int) (-firstPart - 1); // NOT
int second32Bits = (int) (-secondPart - 1);

// put the values into a byte-array and return it
return BitConverter.GetBytes(first32Bits).Append(BitConverter.GetBytes(second32Bits));
}


-cope.

Santos
13th Sep 11, 9:04 AM
OMG! :Hail: That's fantastic! :jump:


Hopefully this hashing algorithm will allow us to load custom BOD files at some point in the future.That might be like today. I have export code in place and working, except for hash generation.

Santos
13th Sep 11, 11:34 AM
Works flawlessly. :awesome: Now I can convert from BOD to XML and back with no loss (files are exactly the same byte to byte). Here's an updated smbod tool:

http://hotfile.com/dl/129721565/33d3a46/smbod.exe.html

Try something simple, like changing some texture names in materials.

I figured out some more things about BOD format BTW. Turns out type 0xFF is objectlink and allows to reference elements (0x07) from within the same file (that's what the global index is used for). 0xFE is objectnull and is like objectlink but points to void. 0x0D should be read as Int64 (signed). So the only unknown left is type 0x05.

Here's the full format:



================
BOD File Format
================
Version: 0.2.0
Author: Santos
================


Types
-----


GUID unique id (8 bytes)
HSTRING hashed string (with GUID being a key into string table)


------
HEADER
------


CHAR[3] signature (BOD)
UINT8 ? (0xFD)
UINT8 ? (2)
UINT8 compressed (0, 1)
UINT32 ? (1)
IF (compressed == 1) THEN
UINT32 uncompressed data size
DATA[N} zlib compressed data (N - to file's end)
ELSE IF (compressed == 0) THEN
UINT32 num strings
UINT32 max string length
FOR (num strings) DO
GUID id
STRING string
OBJECT root object


------
OBJECT
------


UINT8 type? (1)
HSTRING class
UINT32 num properties
FOR (num properties) DO
HSTRING property name
PROPERTY property


--------
PROPERTY
--------


UINT8 type
CASE (type) OF
0x02: INT32 value
0x03: FLOAT value
0x04: BOOL value
0x05: HSTRING value
0x07: UINT32 index
PROPERTY property
0x09: UINT32 count
UINT8 flag (0, 1)
FOR (count) DO
IF (flag == 1) THEN
UINT8 type? (5)
HSTRING name
PROPERTY property
0x0B: UINT32 count
FOR (count) DO
PROPERTY value
0x0D: INT64 value
0x0F: HSTRING value
0xFE: // No value
0xFF: UINT32 value


--------------
Property Types
--------------


0x02 - int
0x03 - float
0x04 - bool
0x05 - ?
0x07 - object
0x09 - struct
0x0B - array
0x0D - int64
0x0F - hstring
0xFE - objectnull
0xFF - objectlink


-----
Notes
-----


- if compression is equal to 1, entire data block is compressed with zlib (best compression level)
- four out of eight BOD file types are compressed - Layer, O3d, region, world
- int property (0x02) is signed integer (can be negative)
- properties 0x05 and 0x0F are both hashed strings, difference between the two is unknown
- object property (0x07) is indexed globally, index can be referenced by objectlink properties (0xFF)
- objectnull property (0xFE) has no value

Copernicus
13th Sep 11, 11:59 AM
Changed a texture name, renamed the texture and the game loads it all up fine. So that's fixed now :).

Santos
13th Sep 11, 12:18 PM
Woot! :jig: We just killed not 2 but 8 birds with one stone. :D

Copernicus
13th Sep 11, 12:22 PM
Indeed! It is just nice to see how simple teamwork can solve such problems :).

Croaxleigh
13th Sep 11, 5:40 PM
Santos and Cope: Like a shotgun of modding. ;)