0

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?

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.

  • 1
    I just extracted the text from another game that uses the same format. It displays all of the same trends, but with different values even for strings that are the same in both games. Based on that, you're probably right. – RoadrunnerWMC Nov 3 '16 at 9:15
  • Also, you're right that I don't need to know how the IDs were generated in order to make changes. I was just trying to figure it out for curiosity's sake. At any rate, I'll mark this as accepted. Thanks. :) – RoadrunnerWMC Nov 3 '16 at 9:19
1

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).

  • I knew it was a hash function's output, I just couldn't get anything valuable with the data you posted. Thanks for reporting back! – NirIzr Nov 11 '16 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.