From 65d7be410bf3558bc5d61745e3203753b1f37673 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Sat, 16 Nov 2019 11:37:11 +0100 Subject: fast log2 --- internal/hash/log2.go | 18 ++++++++++++------ 1 file changed, 12 insertions(+), 6 deletions(-) (limited to 'internal/hash/log2.go') diff --git a/internal/hash/log2.go b/internal/hash/log2.go index 5e30f17..8ba79df 100644 --- a/internal/hash/log2.go +++ b/internal/hash/log2.go @@ -1,9 +1,15 @@ package hash -func log2(num uint32) uint32 { - var i uint32 - for limit := uint32(1); limit < num; limit <<= 1 { - i++ - } - return i +var tab32 = [32]uint32{ + 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, + 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31, +} + +func log2(value uint32) uint32 { + value |= value >> 1 + value |= value >> 2 + value |= value >> 4 + value |= value >> 8 + value |= value >> 16 + return tab32[(value*0x07c4acdd)>>27] } -- cgit v1.2.3