Getting a unique number per string?

Its quite easy to generate a unique number for any given string using Cyclic Redundancy Checking (CRC)

Heres a link to an article on GameDev:
http://www.gamedev.net/reference/programming/features/crc32/

However it is impossible to generate the string from the CRC value. To do this, you would have to create a string lookup table, and just search for the unique value, and its corresponding string.

Hope that helps
Spree

Cool thanks.

Being able to get the string from the number is not required.

Why not just use the bitpattern of the nullterminated C-style string? That is, mov = {'m','o','v','\0'} = 109+111*256+118*256^2. Of course, then, you could only use strings of length at most 4. If you're only going to use letters of the alphabet, you could do the same thing but fit more chars into it.

If you're only going to use a predefined set of strings, like mov, push, etc, then just assign a unique number to each string.

Yes keywords would be given a value.

Using only the first 8 characters might give enough combinations that it should take alot of symbols to actually have a problem.

I wonder just how many combinations using just the first 4 would give me?

You need hash.



OK, more accurately, you need a hashing algorithm. This is a pretty decent introduction to hashing and collision management via chaining.

By the way, for any string longer than 4 bytes, it is impossible to create a unique 32-bit integer representing that string. Why? Each byte has 256 possible values, for a total of 256^4 = 4,294,967,296 possible strings. A 32-bit (unsigned) integer can store values up to but not including 2^32 = 4,294,967,296 - meaning a 32-bit integer can have up to 4,294,967,296 unique values. Adding another byte gives us a total of 256^5 = 1,099,511,627,776 unique strings, which cannot be stored in 32 bits.

Since any hash algorithm will produce collisions if the hash code is shorter than the original data (which is what we want, after all) you have to handle collisions. The easiest way to do this is chaining, which is described in the article linked above.

The article's algorithm is very simplistic, and produces collisions fairly fast on strings of any significant size. However, it is fairly easy to adapt that general concept to work well in various scenarios. For example, you can hash 128-byte blocks of a large string to produce a series of hash codes. This is still far faster than doing a byte-for-byte comparison, but reduces the risk of collision problems; if any of the hash blocks mismatch, the overall text block is not a match. On the other hand, if all your blocks are short (say, less than 10 bytes), this isn't too important.

Hashes sound good.

Collision sounds like a feature. If a symbol is already defined the hash values should collide. Then I know I do not need to add a new symbol to the symbol table.

A unique 32-bit number for any string is not possible, since there are only 2^32 possible 32-bit numbers, and infinite strings. A hash function converts a string to a seemingly random value, so collissions (two different string with the same number) are very unlikely.
It is possible to convert a string to a number if you have no restriction of size, simply interpret the string data as a very large (binary) number.

I understand for any length of sting is not possible. So I was thinking of making the first 8 character significant. Now that I think of it hases is the way to go. There maybe some APIs that the first 8 characters are the same. I planning to limit the symbol name length to something reasonable, say 64 bytes.

So I guess I should learn about hashes.

Would STL hash be good for this?

Thanks.

Well, if you use hashes, it doesn't matter how long the strings are (as long as there's enough memory for the string in the first place). There may always be collisions, no matter whether you limit the lengths or not. Because of this, there's also no way to reconstruct the original string from its hash.

If you want one-to-one mapping and the first 8 chars are enough, the string fits nicely into two 32-bit ints (or one 64-bit int (long long) if your compiler supports it).

There's no good reason to limit the length to 64 characters.

The STL doesn't have a hash. hash_map is a non-portable extension. On different implementations of the STL, hash_map may not be present, may be in a different namespace, and/or may be in a different header.

I'd suggest using std::map. It might be more efficient than a hash map anyway. And if it isn't, it's better to have something that works that you can optimise later than to delay things spending time misoptimising something that might not even be a performance bottleneck.

Just FYI, I once made a 'hash string' type that held a string and kept its hash as well, and using that as a key in std::map and doing tons of searching was slower than just using std::string for some reason. I'm guessing that since std::map is a ballanced tree, searching the few levels with a string was faster than computing the CRC32 and searching the few levels with an int.

Quote:

Original post by Extrarius Just FYI, I once made a 'hash string' type that held a string and kept its hash as well, and using that as a key in std::map and doing tons of searching was slower than just using std::string for some reason. I'm guessing that since std::map is a ballanced tree, searching the few levels with a string was faster than computing the CRC32 and searching the few levels with an int.

I suspect that std::map is optimised for searching for string elements, and std::map is optimised for searching for int elements. std::map doesn't (or at least shouldn't) generate a hash for the string and look it up in an integer map. So it's going to be slower if you do that.

This is unfortunately a case of premature optimisation (the root of all evil).
strcmp is actually not that bad for speed.
When it compares the first character of each string there is a high probability that they are different and the function stops and emits an answer. Assuming you hit the case where they are the same you then proceed to compare the second characters which also have a high chance of being different etc...
Unless you have really long strings with a lot of common characters at the start then strcmp should be not too bad for speed. It is unlikely to be a bottleneck.

These days there is more speedup from storing the length of the string, such as is done by BSTR's etc, and strings in many other languages. This saves calculating the string length reducing an O(n) to an O(1). It also speeds up other operations like concatenation, turning O(m+n) into O(n) etc...
You can then compare the length first too which will be as fast as your unique key compare, and will often be enough on it's own. And if they are the same and are greater than four then a cast to (int) of the first four chars, and then compare is going to be very fast also (since you know that there are at least four chars).

If you truly are trying to increase speed, or simply use the fastest design "straight out of the box" then storing the length is where there is much speed to be gained (I read this recently in some book, but can't remember which one sorry).
It is also a more generic approach. i.e. It will work if you want case-insensitive compares for example. Your idea will not. Your proposal also has on top of it, conversion to these unique IDs as well which takes away much of any speed advantage of having them in the first place, since the precalcalcution time is still part of the parsing time. But with the length you already have that as you read each literal in.

[Edit]
Actually I was thinking later that your strings may be very short for an assembler, so the length advantage will be unusually small in that case. I don't think your idea would be worth it either though. Assemblers are generally considerably faster than C++ compilers for example as they have almost no optimisation to perform etc. I don't think you will have speed problems.