Hash always use all characters in a long string
Hashes for long strings are computed only when they are used as keys
in a table, not a too common case. And, in that case, it is to easy to
force collisions changing only the characters which are not part of the
hash.
diff --git a/lstate.c b/lstate.c
index 76df6a2..4227429 100644
--- a/lstate.c
+++ b/lstate.c
@@ -76,7 +76,7 @@
addbuff(buff, p, &h); /* local variable */
addbuff(buff, p, &lua_newstate); /* public function */
lua_assert(p == sizeof(buff));
- return luaS_hash(buff, p, h, 1);
+ return luaS_hash(buff, p, h);
}
#endif
diff --git a/lstring.c b/lstring.c
index 6f15747..138871c 100644
--- a/lstring.c
+++ b/lstring.c
@@ -23,16 +23,6 @@
/*
-** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a long string to
-** compute its hash
-*/
-#if !defined(LUAI_HASHLIMIT)
-#define LUAI_HASHLIMIT 5
-#endif
-
-
-
-/*
** Maximum size for string table.
*/
#define MAXSTRTB cast_int(luaM_limitN(MAX_INT, TString*))
@@ -50,10 +40,9 @@
}
-unsigned int luaS_hash (const char *str, size_t l, unsigned int seed,
- size_t step) {
+unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) {
unsigned int h = seed ^ cast_uint(l);
- for (; l >= step; l -= step)
+ for (; l > 0; l--)
h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1]));
return h;
}
@@ -63,8 +52,7 @@
lua_assert(ts->tt == LUA_VLNGSTR);
if (ts->extra == 0) { /* no hash? */
size_t len = ts->u.lnglen;
- size_t step = (len >> LUAI_HASHLIMIT) + 1;
- ts->hash = luaS_hash(getstr(ts), len, ts->hash, step);
+ ts->hash = luaS_hash(getstr(ts), len, ts->hash);
ts->extra = 1; /* now it has its hash */
}
return ts->hash;
@@ -201,7 +189,7 @@
TString *ts;
global_State *g = G(L);
stringtable *tb = &g->strt;
- unsigned int h = luaS_hash(str, l, g->seed, 1);
+ unsigned int h = luaS_hash(str, l, g->seed);
TString **list = &tb->hash[lmod(h, tb->size)];
lua_assert(str != NULL); /* otherwise 'memcmp'/'memcpy' are undefined */
for (ts = *list; ts != NULL; ts = ts->u.hnext) {
diff --git a/lstring.h b/lstring.h
index a413a9d..450c239 100644
--- a/lstring.h
+++ b/lstring.h
@@ -41,8 +41,7 @@
#define eqshrstr(a,b) check_exp((a)->tt == LUA_VSHRSTR, (a) == (b))
-LUAI_FUNC unsigned int luaS_hash (const char *str, size_t l,
- unsigned int seed, size_t step);
+LUAI_FUNC unsigned int luaS_hash (const char *str, size_t l, unsigned int seed);
LUAI_FUNC unsigned int luaS_hashlongstr (TString *ts);
LUAI_FUNC int luaS_eqlngstr (TString *a, TString *b);
LUAI_FUNC void luaS_resize (lua_State *L, int newsize);
diff --git a/ltests.c b/ltests.c
index 9945615..7e3a389 100644
--- a/ltests.c
+++ b/ltests.c
@@ -523,7 +523,6 @@
((void)g); /* better to keep it available if we need to print an object */
while (o) {
lua_assert(!!isgray(o) ^ (getage(o) == G_TOUCHED2));
- //lua_assert(isgray(o) || getage(o) == G_TOUCHED2);
lua_assert(!testbit(o->marked, TESTBIT));
if (keepinvariant(g))
l_setbit(o->marked, TESTBIT); /* mark that object is in a gray list */