From 96f428d5e3f77c21ba625fdbe3ca1fd3afda1755 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Mon, 19 Jun 2023 20:02:12 -0700 Subject: hash: bug: initial hash mask miscalculation. Hash tables are supposed to start with a mask of 255, which is the 256 modulus less one. However, due to a coding mistake, they get a modulus of 252. Now this still works. It just has a few zero bits in it: 1111 1100 rather than 11111111. When this grows by doubling in size, we get 1 1111 1001, 11 1111 0011 and so on. Now this still all works, because hash values AND-ed with such a mask are no greater than that mask. The table isn't accessed out of bounds. It's just inefficiently used. * hash.c (do_make_hash, make_similar_hash, clearhash): When converting the power-of-two modulus, which is a Lisp word, to the integer mask, subtract 1 from the integer value, not the original Lisp word. --- hash.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/hash.c b/hash.c index cb8ec3b9..c803f845 100644 --- a/hash.c +++ b/hash.c @@ -924,7 +924,7 @@ static val do_make_hash(hash_weak_opt_t wkopt, hash_type_t type, val seed) h->seed = c_unum(default_arg(seed, if3(hash_seed_s, hash_seed, zero)), self); h->wkopt = wkopt; - h->mask = c_unum(mod - 1, self); + h->mask = c_unum(mod, self) - 1; h->count = 0; h->table = table; h->userdata = nil; @@ -996,7 +996,7 @@ val make_similar_hash(val existing) val table = vector(mod, nil); val hash = cobj(coerce(mem_t *, h), hash_cls, &hash_ops); - h->mask = c_unum(mod - 1, self); + h->mask = c_unum(mod, self) - 1; h->count = 0; h->table = table; h->userdata = ex->userdata; @@ -1147,7 +1147,7 @@ val clearhash(val hash) val mod = num_fast(256); val table = vector(mod, nil); ucnum oldcount = h->count; - h->mask = c_unum(mod - 1, self); + h->mask = c_unum(mod, self) - 1; h->count = 0; h->table = table; setcheck(hash, table); -- cgit v1.2.3