111395686SJesper Dangaard Brouer /* SPDX-License-Identifier: LGPL-2.1 211395686SJesper Dangaard Brouer * 311395686SJesper Dangaard Brouer * Based on Paul Hsieh's (LGPG 2.1) hash function 411395686SJesper Dangaard Brouer * From: http://www.azillionmonkeys.com/qed/hash.html 511395686SJesper Dangaard Brouer */ 611395686SJesper Dangaard Brouer 711395686SJesper Dangaard Brouer #define get16bits(d) (*((const __u16 *) (d))) 811395686SJesper Dangaard Brouer 911395686SJesper Dangaard Brouer static __always_inline SuperFastHash(const char * data,int len,__u32 initval)1011395686SJesper Dangaard Brouer__u32 SuperFastHash (const char *data, int len, __u32 initval) { 1111395686SJesper Dangaard Brouer __u32 hash = initval; 1211395686SJesper Dangaard Brouer __u32 tmp; 1311395686SJesper Dangaard Brouer int rem; 1411395686SJesper Dangaard Brouer 1511395686SJesper Dangaard Brouer if (len <= 0 || data == NULL) return 0; 1611395686SJesper Dangaard Brouer 1711395686SJesper Dangaard Brouer rem = len & 3; 1811395686SJesper Dangaard Brouer len >>= 2; 1911395686SJesper Dangaard Brouer 2011395686SJesper Dangaard Brouer /* Main loop */ 2111395686SJesper Dangaard Brouer #pragma clang loop unroll(full) 2211395686SJesper Dangaard Brouer for (;len > 0; len--) { 2311395686SJesper Dangaard Brouer hash += get16bits (data); 2411395686SJesper Dangaard Brouer tmp = (get16bits (data+2) << 11) ^ hash; 2511395686SJesper Dangaard Brouer hash = (hash << 16) ^ tmp; 2611395686SJesper Dangaard Brouer data += 2*sizeof (__u16); 2711395686SJesper Dangaard Brouer hash += hash >> 11; 2811395686SJesper Dangaard Brouer } 2911395686SJesper Dangaard Brouer 3011395686SJesper Dangaard Brouer /* Handle end cases */ 3111395686SJesper Dangaard Brouer switch (rem) { 3211395686SJesper Dangaard Brouer case 3: hash += get16bits (data); 3311395686SJesper Dangaard Brouer hash ^= hash << 16; 3411395686SJesper Dangaard Brouer hash ^= ((signed char)data[sizeof (__u16)]) << 18; 3511395686SJesper Dangaard Brouer hash += hash >> 11; 3611395686SJesper Dangaard Brouer break; 3711395686SJesper Dangaard Brouer case 2: hash += get16bits (data); 3811395686SJesper Dangaard Brouer hash ^= hash << 11; 3911395686SJesper Dangaard Brouer hash += hash >> 17; 4011395686SJesper Dangaard Brouer break; 4111395686SJesper Dangaard Brouer case 1: hash += (signed char)*data; 4211395686SJesper Dangaard Brouer hash ^= hash << 10; 4311395686SJesper Dangaard Brouer hash += hash >> 1; 4411395686SJesper Dangaard Brouer } 4511395686SJesper Dangaard Brouer 4611395686SJesper Dangaard Brouer /* Force "avalanching" of final 127 bits */ 4711395686SJesper Dangaard Brouer hash ^= hash << 3; 4811395686SJesper Dangaard Brouer hash += hash >> 5; 4911395686SJesper Dangaard Brouer hash ^= hash << 4; 5011395686SJesper Dangaard Brouer hash += hash >> 17; 5111395686SJesper Dangaard Brouer hash ^= hash << 25; 5211395686SJesper Dangaard Brouer hash += hash >> 6; 5311395686SJesper Dangaard Brouer 5411395686SJesper Dangaard Brouer return hash; 5511395686SJesper Dangaard Brouer } 56