lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 PHC  
Open Source and information security mailing list archives
 

Date: 29 Apr 2016 00:12:36 0400 From: "George Spelvin" <linux@...izon.com> To: linux@...izon.com, torvalds@...uxfoundation.org Cc: linuxkernel@...r.kernel.org, tglx@...utronix.de Subject: Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Linus wrote: > Having looked around at other hashes, I suspect we should look at the > ones that do five or six shifts, and a mix of add/sub and xor. And > because they shift the bits around more freely you don't have the > final shift (that ends up being dependent on the size of the target > set). I'm not sure that final shift is a problem. You need to mask the result to the desired final size somehow, and a shift is no more cycles than an AND. > It really would be lovely to hear that we can just replace > hash_int/long() with a better hash. And I wouldn't get too hung up on > the multiplication trick. I suspect it's not worth it. My main concern is that the scope of the search grows enormously if we include such things. I don't want to discourage someone from looking, but I volunteered to find a better multiplication constant with an efficient add/subtract chain, not start a thesis project on more general hash functions. Two places one could look for ideas, though: http://www.burtleburtle.net/bob/hash/integer.html https://gist.github.com/badboy/6267743 Here's Thomas Wang's 64bit hash, which is reputedly quite good, in case it helps: uint64_t hash(uint64_t key) { key = ~key + (key << 21); // key = (key << 21)  key  1; key ^= key >> 24; key += (key << 3)) + (key << 8); // key *= 265 key ^= key >> 14; key += (key << 2)) + (key << 4); // key *= 21 key ^= key >> 28; key += key << 31; return key; } And his slightly shorter 64to32bit function: unsigned hash(uint64_t key) { key = ~key + (key << 18); // key = (key << 18)  key  1; key ^= key >> 31; key *= 21; // key += (key << 2)) + (key << 4); key ^= key >> 11; key += key << 6; key ^= key >> 22; return (uint32_t)key; } Sticking to multiplication, using the heuristics in the current comments (prime near golden ratio = 9e3779b9 = 2654435769,) I can come up with this for multiplying by 2654435599 = 0x9e37790f: //  // This code was generated by Spiral Multiplier Block Generator, www.spiral.net // Copyright (c) 2006, Carnegie Mellon University // All rights reserved. // The generated code is distributed under a BSD style license // (see http://www.opensource.org/licenses/bsdlicense.php) //  // Cost: 6 adds/subtracts 6 shifts 0 negations // Depth: 5 // Input: // int t0 // Outputs: // int t1 = 2654435599 * t0 //  t3 = shl(t0, 11); /* 2048*/ t2 = sub(t3, t0); /* 2047*/ t5 = shl(t2, 8); /* 524032*/ t4 = sub(t5, t2); /* 521985*/ t7 = shl(t0, 25); /* 33554432*/ t6 = add(t4, t7); /* 34076417*/ t9 = shl(t0, 9); /* 512*/ t8 = sub(t9, t0); /* 511*/ t11 = shl(t6, 4); /* 545222672*/ t10 = sub(t11, t6); /* 511146255*/ t12 = shl(t8, 22); /* 2143289344*/ t1 = add(t10, t12); /* 2654435599*/ Which translates into C as uint32_t multiply(uint32_t x) { unsigned y = (x << 11)  x; y = y << 8; y = x << 25; x = x << 9; y = y << 4; y = x << 22; return y; } Unfortunately, that utility bogs like hell on 64bit constants.
Powered by blists  more mailing lists