Rockbox.org home
release
dev builds
extras
themes manual
wiki
device status forums
mailing lists
IRC bugs
patches
dev guide



Rockbox mail archive

Subject: Re: clever algorithm string ->int id wanted
From: brendan hack (bendy_at_bendys.com)
Date: 2002-10-04


I've needed a hash function for strings in the past and eventually settled on the hash function used by perl. It works on generic data and might fit your needs. Here's my c code if you want to use it:

DWORD
HashKey(void *pData, int nBytes)
{
        // use: 65599 nice
        // 65587 even better.
        #define HASHC n = *str++ + 65599 * n

        register char *str;
        register DWORD n = 0;

        // hash on the key;
        str = (char*)pData;
                
        if (nBytes > 0) {
                register int loop = (nBytes + 8 - 1) >> 3;

                switch(nBytes & (8 - 1)) {
                case 0: do {
                        HASHC; case 7: HASHC;
                case 6: HASHC; case 5: HASHC;
                case 4: HASHC; case 3: HASHC;
                case 2: HASHC; case 1: HASHC;
                        } while (--loop);
                }
        }
        return n;
}

NB: I just copied and pasted this from other code and didn't test it directly.

hope this helps

brendan

phil_at_x-phobie.de wrote:
> On Thu, 3 Oct 2002 16:40:55 -0400, "M. OReilly"
> <moreilly_at_moreilly.com> wrote:
>
>
>>Would a simple checksum work? A two digit hex checksum would be enough for
>>256 unique entries.
>
>
> Maybe a checksum is not sufficiant to really distinguish two different
> strings. BTW I wouldn't be surprised if we exceed a limit of 256
> different commands. Well. Somewhen, maybe.
>
> I read in
> http://java.sun.com/j2se/1.4.1/docs/api/java/lang/String.html#hashCode()
> that they make a hash key for strings with
>
> s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
>
> Because I'm not that much interested in speed while loading a key
> scheme I'll take that (in spite of all those multiplications) unless I
> accidently stumble across something better.
>
> Phil
>
>

-- 
Brendan Hack                                     
Bendy's 3D Systems               Plugins for trueSpace 3 and above
w:http://www.bendys.com                         e:bendy_at_bendys.com

If you're not part of the solution, you're part of the precipitate



Page was last modified "Jan 10 2012" The Rockbox Crew
aaa