Identifying a very weak hash algorithm

Question

I'm reverse-engineering a string translation file format for a particular game. It's ultimately just an ID-to-string map, where the IDs are four-byte integers. There are 1935 IDs in total; you can see them all here.

The first thing that I notice is that when written in base 16, 115 of them have the first digit set to 0, roughly what you'd expect from a list of 1935 random numbers. But unlike 1935 random numbers, 19 IDs have the entire upper byte as 0, 8 have the upper three digits as 0, 6 have the upper four digits as 0, 5 have the upper five digits as 0, and one is less than 256!

Furthermore, the strings with the dozen or so smallest IDs are mostly very short strings (although not all short strings have small IDs).

This leads me to conclude that these numerical IDs were produced by some very weak & simple hash function operating on strings (like "text1" or something), where the IDs for short strings were often just the string itself.

Additionally, strings that occur in sequence in the game (consecutive lines of dialogue) very often have consecutive IDs in ascending order (but not always). This makes sense if the IDs are hashes of string keys; the original strings for a given situation would presumably have looked something like "situation_text_1", "situation_text_2", and so on. A weak hash algorithm could easily have this effect.

This is where I'm stuck. From what I can tell, the other files in the game refer to these strings by numerical ID, not by string IDs. I'm unsure if original string keys or the hash function itself exist anywhere in the game. As such, I don't have any way to test controlled input values -- I just have to go on those 1935 examples (plus a few more that can be found in a leftover debug file).

Here are the corresponding strings for the smallest IDs. I'm skipping ones with text very specific to this particular game.

• 20: [Game copyright notice. I think this is the hash of the empty string.]
• 576: "5"
• 614: "10"
• 2681: "25"
• 2684: "OK"
• 53444: "On"
• 87305: [Skipped; two words]
• 88410: "NEW"
• 2444912: "Off"
• 2553265: "ɓ Back" (This is allowed because strings are UTF-16.)
• 2661022: "Normal"
• 2736539: "Expert"
• 2963284: [Skipped; a sentence with markup]
• 3020267: "POCS" (I have no idea what this means.)
• 7314642: "Rank:"

Do you have any ideas about what the hash algorithm could be?

Answer 1

From your description, I suspect these are not hashes but just randomly-generated numerical IDs, incremented as new strings were added around the same place to the program (possibly because programmer was too lazy to regenerate a completely new ID). There is a small possibility that the ID depends on the string contents but I doubt it.

In any case, if you have recovered the ID->String mapping, I don't see why you need to know how exactly they were generated. Just translate the strings and you should be done.

Answer 2

I actually found the hash function today by reverse-engineering the game's code. Here it is, translated to Python:

def hashFunction(data):
    h = -1

    for c in data:
        if (c - 65) & 0xFFFFFFFF <= 0x19:
            c |= 0x20

        h = (h * 33 + c) & 0xFFFFFFFF

    return h

When run with b'5', b'10', b'25', etc., this function returns hash values seen in the table I posted. They don't match the corresponding keys in that table due to a bug in my text extraction script (oops).