blob: a6afa47b5697f18d5398db6b867a977da0d3a45e [file]
/-
Copyright (c) 2024 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Markus Himmel
-/
prelude
import Init.Data.UInt.Lemmas
import Init.Data.UInt.Bitwise
/-!
This is an internal implementation file of the hash map. Users of the hash map should not rely on
the contents of this file.
File contents: mapping a hash to a hash map bucket
-/
set_option linter.missingDocs true
set_option autoImplicit false
namespace Std.DHashMap.Internal
/--
Scramble the hash code in order to protect against bad hash functions.
Example: if `Hashable Float` was implemented using the "identity" reinterpreting the bit pattern as
a `UInt64`, then the hash codes of all small positive or negative integers would end in around 50
zeroes, meaning that they all land in bucket 0 in reasonably-sized hash maps.
To counteract this, we xor the hash code with some shifted-down versions of itself, to make sure
that all of the entropy of the hash code appears in the lower 16 bits at least.
The scrambling operation is very fast. It does not have a measurable impact on performance in the
insert benchmark.
-/
@[inline]
def scrambleHash (hash : UInt64) : UInt64 :=
let fold := hash ^^^ (hash >>> 32)
fold ^^^ (fold >>> 16)
-- Note that this indexing scheme always produces a valid index, but it only has a chance of
-- returning every index if sz is a power of two.
/--
`sz` is an explicit parameter because having it inferred from `h` can lead to suboptimal IR,
cf. https://github.com/leanprover/lean4/issues/4157
-/
@[irreducible, inline] def mkIdx (sz : Nat) (h : 0 < sz) (hash : UInt64) :
{ u : USize // u.toNat < sz } :=
⟨(scrambleHash hash).toUSize &&& (sz.toUSize - 1), by
-- Making this proof significantly less painful will be a good test for our USize API
by_cases h' : sz < USize.size
· rw [USize.and_toNat, ← USize.ofNat_one, USize.toNat_sub_of_le, USize.toNat_ofNat_of_lt]
· refine Nat.lt_of_le_of_lt Nat.and_le_right (Nat.sub_lt h ?_)
rw [USize.toNat_ofNat_of_lt]
· exact Nat.one_pos
· exact Nat.lt_of_le_of_lt h h'
· exact h'
· rw [USize.le_def, Fin.le_def]
change _ ≤ (_ % _)
rw [Nat.mod_eq_of_lt h', USize.ofNat, Fin.val_ofNat', Nat.mod_eq_of_lt]
· exact h
· exact Nat.lt_of_le_of_lt h h'
· exact Nat.lt_of_lt_of_le (USize.toNat_lt_size _) (Nat.le_of_not_lt h')⟩
end Std.DHashMap.Internal