- Revision
- 16063
- Author
- vajda
- Date
- 2007-12-06 12:26:50 -0800 (Thu, 06 Dec 2007)
Log Message
widened uuid hash
Modified Paths
Diff
Modified: trunk/internal/chandlerdb/chandlerdb/util/c.c (16062 => 16063)
--- trunk/internal/chandlerdb/chandlerdb/util/c.c 2007-12-06 19:44:35 UTC (rev 16062) +++ trunk/internal/chandlerdb/chandlerdb/util/c.c 2007-12-06 20:26:50 UTC (rev 16063) @@ -49,7 +49,10 @@ if (!PyArg_ParseTuple(args, "s#", &data, &len)) return 0; - + + /* int hash, these hashes are persisted and should be the same + * regardless of sizeof(long) + */ return PyInt_FromLong(hash_bytes(data, len)); } @@ -231,7 +234,7 @@ static PyMethodDef c_funcs[] = { { "isuuid", (PyCFunction) isuuid, METH_O, "isinstance(UUID)" }, { "_hash", (PyCFunction) hash, METH_VARARGS, "hash bytes" }, - { "_combine", (PyCFunction) combine, METH_VARARGS, "combine two hashes" }, + { "_combine", (PyCFunction) combine, METH_VARARGS, "combine two int hashes" }, { "loadUUIDs", (PyCFunction) loadUUIDs, METH_O, "use a list of pre-generated UUIDs, for debugging" }, { "saveUUIDs", (PyCFunction) saveUUIDs, METH_O,
Modified: trunk/internal/chandlerdb/chandlerdb/util/fns.h (16062 => 16063)
--- trunk/internal/chandlerdb/chandlerdb/util/fns.h 2007-12-06 19:44:35 UTC (rev 16062) +++ trunk/internal/chandlerdb/chandlerdb/util/fns.h 2007-12-06 20:26:50 UTC (rev 16063) @@ -20,5 +20,6 @@ void format16_uuid(unsigned char *uuid, char *buf); void format64_uuid(unsigned char *uuid, char *buf); int hash_bytes(unsigned char *uuid, int len); +long long_hash_bytes(unsigned char *uuid, int len); +long combine_longs(unsigned long h0, unsigned long h1); int combine_ints(unsigned int h0, unsigned int h1); -
Modified: trunk/internal/chandlerdb/chandlerdb/util/hashtuple.c (16062 => 16063)
--- trunk/internal/chandlerdb/chandlerdb/util/hashtuple.c 2007-12-06 19:44:35 UTC (rev 16062) +++ trunk/internal/chandlerdb/chandlerdb/util/hashtuple.c 2007-12-06 20:26:50 UTC (rev 16063) @@ -103,7 +103,10 @@ } else return 0; - + + /* these hashes are persisted and need to be the same on 32- and 64-bit + * architectures, using 32-bit int hash function + */ hash = hash_bytes((unsigned char *) data, len); Py_XDECREF(string);
Modified: trunk/internal/chandlerdb/chandlerdb/util/pyuuid.c (16062 => 16063)
--- trunk/internal/chandlerdb/chandlerdb/util/pyuuid.c 2007-12-06 19:44:35 UTC (rev 16062) +++ trunk/internal/chandlerdb/chandlerdb/util/pyuuid.c 2007-12-06 20:26:50 UTC (rev 16063) @@ -23,7 +23,7 @@ static void t_uuid_dealloc(t_uuid *self); static PyObject *t_uuid_new(PyTypeObject *type, PyObject *args, PyObject *kwds); static int t_uuid_init(t_uuid *self, PyObject *args, PyObject *kwds); -static int t_uuid_hash(t_uuid *self); +static long t_uuid_hash(t_uuid *self); static PyObject *t_uuid_str(t_uuid *self); static PyObject *t_uuid_repr(t_uuid *self); static int t_uuid_cmp(t_uuid *o1, t_uuid *o2); @@ -42,7 +42,11 @@ static PyMemberDef t_uuid_members[] = { { "_uuid", T_OBJECT, offsetof(t_uuid, uuid), READONLY, "UUID bytes" }, +#ifdef __LP64__ + { "_hash", T_LONG, offsetof(t_uuid, hash), READONLY, "UUID hash" }, +#else { "_hash", T_INT, offsetof(t_uuid, hash), READONLY, "UUID hash" }, +#endif { NULL, 0, 0, 0, NULL } }; @@ -192,12 +196,12 @@ return -1; } - self->hash = hash_bytes(uuid, 16); + self->hash = long_hash_bytes(uuid, 16); return 0; } -static int t_uuid_hash(t_uuid *self) +static long t_uuid_hash(t_uuid *self) { return self->hash; } @@ -309,7 +313,8 @@ /* steals reference */ uuid->uuid = str16; - uuid->hash = hash_bytes((unsigned char *) PyString_AS_STRING(str16), 16); + uuid->hash = long_hash_bytes((unsigned char *) PyString_AS_STRING(str16), + 16); return (PyObject *) uuid; }
Modified: trunk/internal/chandlerdb/chandlerdb/util/uuid.c (16062 => 16063)
--- trunk/internal/chandlerdb/chandlerdb/util/uuid.c 2007-12-06 19:44:35 UTC (rev 16062) +++ trunk/internal/chandlerdb/chandlerdb/util/uuid.c 2007-12-06 20:26:50 UTC (rev 16063) @@ -92,8 +92,58 @@ return hash; } -static unsigned char chew_int(unsigned int n) +long long_hash_bytes(unsigned char *uuid, int len) { +#ifdef __LP64__ + unsigned long hash = 0xb01dfacedeadbeef; +#else + unsigned long hash = 0xdeadbeef; +#endif + int i = -1; + + while (++i < len) { + unsigned char source = uuid[i]; + unsigned char byte = hTable[(unsigned char) ((hash & 0xff) ^ source)]; + unsigned int newHash = byte; + + hash >>= 8; + byte = hTable[(unsigned char) ((hash & 0xff) ^ (source + 1))]; + newHash = (newHash << 8) | byte; + + hash >>= 8; + byte = hTable[(unsigned char) ((hash & 0xff) ^ (source + 2))]; + newHash = (newHash << 8) | byte; + + hash >>= 8; + byte = hTable[(unsigned char) ((hash & 0xff) ^ (source + 3))]; + newHash = (newHash << 8) | byte; + +#ifdef __LP64__ + hash >>= 8; + byte = hTable[(unsigned char) ((hash & 0xff) ^ (source + 4))]; + newHash = (newHash << 8) | byte; + + hash >>= 8; + byte = hTable[(unsigned char) ((hash & 0xff) ^ (source + 5))]; + newHash = (newHash << 8) | byte; + + hash >>= 8; + byte = hTable[(unsigned char) ((hash & 0xff) ^ (source + 6))]; + newHash = (newHash << 8) | byte; + + hash >>= 8; + byte = hTable[(unsigned char) ((hash & 0xff) ^ (source + 7))]; + newHash = (newHash << 8) | byte; +#endif + + hash = newHash; + } + + return hash; +} + +static unsigned int chew_int(unsigned int n) +{ unsigned char hash = hTable[0 ^ (n & 0xff)]; n >>= 8; @@ -105,9 +155,39 @@ n >>= 8; hash = hTable[hash ^ (n & 0xff)]; - return hash; + return (unsigned int) hash; } +static unsigned long chew_long(unsigned long n) +{ + unsigned char hash = hTable[0 ^ (n & 0xff)]; + + n >>= 8; + hash = hTable[hash ^ (n & 0xff)]; + + n >>= 8; + hash = hTable[hash ^ (n & 0xff)]; + + n >>= 8; + hash = hTable[hash ^ (n & 0xff)]; + +#ifdef __LP64__ + n >>= 8; + hash = hTable[hash ^ (n & 0xff)]; + + n >>= 8; + hash = hTable[hash ^ (n & 0xff)]; + + n >>= 8; + hash = hTable[hash ^ (n & 0xff)]; + + n >>= 8; + hash = hTable[hash ^ (n & 0xff)]; +#endif + + return (unsigned long) hash; +} + static int hash_int(unsigned int n) { unsigned int hash; @@ -120,6 +200,25 @@ return hash ? hash : hash_int(++n); } +static long hash_long(unsigned long n) +{ + unsigned int hash; + + hash = chew_long(n); + hash |= chew_long(++n) << 8; + hash |= chew_long(++n) << 16; + hash |= chew_long(++n) << 24; + +#ifdef __LP64__ + hash |= chew_long(++n) << 32; + hash |= chew_long(++n) << 40; + hash |= chew_long(++n) << 48; + hash |= chew_long(++n) << 56; +#endif + + return hash ? hash : hash_long(++n); +} + int combine_ints(unsigned int h0, unsigned int h1) { unsigned int hash; @@ -130,7 +229,17 @@ return hash; } +long combine_longs(unsigned long h0, unsigned long h1) +{ + unsigned int hash; + while (!(hash = hash_long(h0 + h1))) + h0 = hash_long(h0); + + return hash; +} + + #if defined(__MACH__) #include <unistd.h>
Modified: trunk/internal/chandlerdb/chandlerdb/util/uuid.h (16062 => 16063)
--- trunk/internal/chandlerdb/chandlerdb/util/uuid.h 2007-12-06 19:44:35 UTC (rev 16062) +++ trunk/internal/chandlerdb/chandlerdb/util/uuid.h 2007-12-06 20:26:50 UTC (rev 16063) @@ -20,12 +20,13 @@ typedef struct { PyObject_HEAD PyObject *uuid; - int hash; + long hash; } t_uuid; typedef int (*PyUUID_Check_fn)(PyObject *obj); /* steals reference to obj */ typedef PyObject *(*PyUUID_Make16_fn)(PyObject *obj); typedef int (*_hash_bytes_fn)(char *obj, int len); +typedef long (*_long_hash_bytes_fn)(char *obj, int len); #endif /* _UUID_H */
_______________________________________________ Commits mailing list [email protected] http://lists.osafoundation.org/mailman/listinfo/commits
