diff options
author | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2016-10-07 15:10:20 +0200 |
---|---|---|
committer | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2017-01-10 09:53:31 +0100 |
commit | c40e45b75eb76d79a05c7fa85c1fa9b5c728a12f (patch) | |
tree | ad4f2519067709f00ab98b3c591186c26dc3a21f /freebsd/sys/libkern | |
parent | userspace-header-gen.py: Simplify program ports (diff) | |
download | rtems-libbsd-c40e45b75eb76d79a05c7fa85c1fa9b5c728a12f.tar.bz2 |
Update to FreeBSD head 2016-08-23
Git mirror commit 9fe7c416e6abb28b1398fd3e5687099846800cfd.
Diffstat (limited to 'freebsd/sys/libkern')
-rw-r--r-- | freebsd/sys/libkern/arc4random.c | 158 | ||||
-rw-r--r-- | freebsd/sys/libkern/fls.c | 50 | ||||
-rw-r--r-- | freebsd/sys/libkern/jenkins_hash.c | 465 | ||||
-rw-r--r-- | freebsd/sys/libkern/murmur3_32.c | 134 | ||||
-rw-r--r-- | freebsd/sys/libkern/random.c | 2 |
5 files changed, 600 insertions, 209 deletions
diff --git a/freebsd/sys/libkern/arc4random.c b/freebsd/sys/libkern/arc4random.c deleted file mode 100644 index 89c89eea..00000000 --- a/freebsd/sys/libkern/arc4random.c +++ /dev/null @@ -1,158 +0,0 @@ -#include <machine/rtems-bsd-kernel-space.h> - -/*- - * THE BEER-WARE LICENSE - * - * <dan@FreeBSD.ORG> wrote this file. As long as you retain this notice you - * can do whatever you want with this stuff. If we meet some day, and you - * think this stuff is worth it, you can buy me a beer in return. - * - * Dan Moschuk - */ - -#include <sys/cdefs.h> -__FBSDID("$FreeBSD$"); - -#include <sys/types.h> -#include <rtems/bsd/sys/param.h> -#include <sys/kernel.h> -#include <sys/random.h> -#include <sys/libkern.h> -#include <rtems/bsd/sys/lock.h> -#include <sys/mutex.h> -#include <sys/time.h> - -#define ARC4_RESEED_BYTES 65536 -#define ARC4_RESEED_SECONDS 300 -#define ARC4_KEYBYTES (256 / 8) - -int arc4rand_iniseed_state = ARC4_ENTR_NONE; - -static u_int8_t arc4_i, arc4_j; -static int arc4_numruns = 0; -static u_int8_t arc4_sbox[256]; -static time_t arc4_t_reseed; -static struct mtx arc4_mtx; - -static u_int8_t arc4_randbyte(void); - -static __inline void -arc4_swap(u_int8_t *a, u_int8_t *b) -{ - u_int8_t c; - - c = *a; - *a = *b; - *b = c; -} - -/* - * Stir our S-box. - */ -static void -arc4_randomstir (void) -{ - u_int8_t key[256]; - int r, n; - struct timeval tv_now; - - /* - * XXX read_random() returns unsafe numbers if the entropy - * device is not loaded -- MarkM. - */ - r = read_random(key, ARC4_KEYBYTES); - getmicrouptime(&tv_now); - mtx_lock(&arc4_mtx); - /* If r == 0 || -1, just use what was on the stack. */ - if (r > 0) { - for (n = r; n < sizeof(key); n++) - key[n] = key[n % r]; - } - - for (n = 0; n < 256; n++) { - arc4_j = (arc4_j + arc4_sbox[n] + key[n]) % 256; - arc4_swap(&arc4_sbox[n], &arc4_sbox[arc4_j]); - } - arc4_i = arc4_j = 0; - - /* Reset for next reseed cycle. */ - arc4_t_reseed = tv_now.tv_sec + ARC4_RESEED_SECONDS; - arc4_numruns = 0; - - /* - * Throw away the first N words of output, as suggested in the - * paper "Weaknesses in the Key Scheduling Algorithm of RC4" - * by Fluher, Mantin, and Shamir. (N = 256 in our case.) - */ - for (n = 0; n < 256*4; n++) - arc4_randbyte(); - mtx_unlock(&arc4_mtx); -} - -/* - * Initialize our S-box to its beginning defaults. - */ -static void -arc4_init(void) -{ - int n; - - mtx_init(&arc4_mtx, "arc4_mtx", NULL, MTX_DEF); - arc4_i = arc4_j = 0; - for (n = 0; n < 256; n++) - arc4_sbox[n] = (u_int8_t) n; - - arc4_t_reseed = 0; -} - -SYSINIT(arc4_init, SI_SUB_LOCK, SI_ORDER_ANY, arc4_init, NULL); - -/* - * Generate a random byte. - */ -static u_int8_t -arc4_randbyte(void) -{ - u_int8_t arc4_t; - - arc4_i = (arc4_i + 1) % 256; - arc4_j = (arc4_j + arc4_sbox[arc4_i]) % 256; - - arc4_swap(&arc4_sbox[arc4_i], &arc4_sbox[arc4_j]); - - arc4_t = (arc4_sbox[arc4_i] + arc4_sbox[arc4_j]) % 256; - return arc4_sbox[arc4_t]; -} - -/* - * MPSAFE - */ -void -arc4rand(void *ptr, u_int len, int reseed) -{ - u_char *p; - struct timeval tv; - - getmicrouptime(&tv); - if (atomic_cmpset_int(&arc4rand_iniseed_state, ARC4_ENTR_HAVE, - ARC4_ENTR_SEED) || reseed || - (arc4_numruns > ARC4_RESEED_BYTES) || - (tv.tv_sec > arc4_t_reseed)) - arc4_randomstir(); - - mtx_lock(&arc4_mtx); - arc4_numruns += len; - p = ptr; - while (len--) - *p++ = arc4_randbyte(); - mtx_unlock(&arc4_mtx); -} - -uint32_t -arc4random(void) -{ - uint32_t ret; - - arc4rand(&ret, sizeof ret, 0); - return ret; -} diff --git a/freebsd/sys/libkern/fls.c b/freebsd/sys/libkern/fls.c deleted file mode 100644 index c6766815..00000000 --- a/freebsd/sys/libkern/fls.c +++ /dev/null @@ -1,50 +0,0 @@ -#include <machine/rtems-bsd-kernel-space.h> - -/*- - * Copyright (c) 1990, 1993 - * The Regents of the University of California. All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - */ - -#include <sys/cdefs.h> -__FBSDID("$FreeBSD$"); - -#include <sys/libkern.h> - -/* - * Find Last Set bit - */ -int -fls(int mask) -{ - int bit; - - if (mask == 0) - return (0); - for (bit = 1; mask != 1; bit++) - mask = (unsigned int)mask >> 1; - return (bit); -} diff --git a/freebsd/sys/libkern/jenkins_hash.c b/freebsd/sys/libkern/jenkins_hash.c new file mode 100644 index 00000000..9ecdb82b --- /dev/null +++ b/freebsd/sys/libkern/jenkins_hash.c @@ -0,0 +1,465 @@ +#include <machine/rtems-bsd-kernel-space.h> + +/* + * Taken from http://burtleburtle.net/bob/c/lookup3.c + * $FreeBSD$ + */ + +#include <sys/hash.h> +#include <machine/endian.h> + +/* +------------------------------------------------------------------------------- +lookup3.c, by Bob Jenkins, May 2006, Public Domain. + +These are functions for producing 32-bit hashes for hash table lookup. +hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() +are externally useful functions. Routines to test the hash are included +if SELF_TEST is defined. You can use this free for any purpose. It's in +the public domain. It has no warranty. + +You probably want to use hashlittle(). hashlittle() and hashbig() +hash byte arrays. hashlittle() is faster than hashbig() on +little-endian machines. Intel and AMD are little-endian machines. +On second thought, you probably want hashlittle2(), which is identical to +hashlittle() except it returns two 32-bit hashes for the price of one. +You could implement hashbig2() if you wanted but I haven't bothered here. + +If you want to find a hash of, say, exactly 7 integers, do + a = i1; b = i2; c = i3; + mix(a,b,c); + a += i4; b += i5; c += i6; + mix(a,b,c); + a += i7; + final(a,b,c); +then use c as the hash value. If you have a variable length array of +4-byte integers to hash, use hashword(). If you have a byte array (like +a character string), use hashlittle(). If you have several byte arrays, or +a mix of things, see the comments above hashlittle(). + +Why is this so big? I read 12 bytes at a time into 3 4-byte integers, +then mix those integers. This is fast (you can do a lot more thorough +mixing with 12*3 instructions on 3 integers than you can with 3 instructions +on 1 byte), but shoehorning those bytes into integers efficiently is messy. +------------------------------------------------------------------------------- +*/ + +#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) + +/* +------------------------------------------------------------------------------- +mix -- mix 3 32-bit values reversibly. + +This is reversible, so any information in (a,b,c) before mix() is +still in (a,b,c) after mix(). + +If four pairs of (a,b,c) inputs are run through mix(), or through +mix() in reverse, there are at least 32 bits of the output that +are sometimes the same for one pair and different for another pair. +This was tested for: +* pairs that differed by one bit, by two bits, in any combination + of top bits of (a,b,c), or in any combination of bottom bits of + (a,b,c). +* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed + the output delta to a Gray code (a^(a>>1)) so a string of 1's (as + is commonly produced by subtraction) look like a single 1-bit + difference. +* the base values were pseudorandom, all zero but one bit set, or + all zero plus a counter that starts at zero. + +Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that +satisfy this are + 4 6 8 16 19 4 + 9 15 3 18 27 15 + 14 9 3 7 17 3 +Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing +for "differ" defined as + with a one-bit base and a two-bit delta. I +used http://burtleburtle.net/bob/hash/avalanche.html to choose +the operations, constants, and arrangements of the variables. + +This does not achieve avalanche. There are input bits of (a,b,c) +that fail to affect some output bits of (a,b,c), especially of a. The +most thoroughly mixed value is c, but it doesn't really even achieve +avalanche in c. + +This allows some parallelism. Read-after-writes are good at doubling +the number of bits affected, so the goal of mixing pulls in the opposite +direction as the goal of parallelism. I did what I could. Rotates +seem to cost as much as shifts on every machine I could lay my hands +on, and rotates are much kinder to the top and bottom bits, so I used +rotates. +------------------------------------------------------------------------------- +*/ +#define mix(a,b,c) \ +{ \ + a -= c; a ^= rot(c, 4); c += b; \ + b -= a; b ^= rot(a, 6); a += c; \ + c -= b; c ^= rot(b, 8); b += a; \ + a -= c; a ^= rot(c,16); c += b; \ + b -= a; b ^= rot(a,19); a += c; \ + c -= b; c ^= rot(b, 4); b += a; \ +} + +/* +------------------------------------------------------------------------------- +final -- final mixing of 3 32-bit values (a,b,c) into c + +Pairs of (a,b,c) values differing in only a few bits will usually +produce values of c that look totally different. This was tested for +* pairs that differed by one bit, by two bits, in any combination + of top bits of (a,b,c), or in any combination of bottom bits of + (a,b,c). +* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed + the output delta to a Gray code (a^(a>>1)) so a string of 1's (as + is commonly produced by subtraction) look like a single 1-bit + difference. +* the base values were pseudorandom, all zero but one bit set, or + all zero plus a counter that starts at zero. + +These constants passed: + 14 11 25 16 4 14 24 + 12 14 25 16 4 14 24 +and these came close: + 4 8 15 26 3 22 24 + 10 8 15 26 3 22 24 + 11 8 15 26 3 22 24 +------------------------------------------------------------------------------- +*/ +#define final(a,b,c) \ +{ \ + c ^= b; c -= rot(b,14); \ + a ^= c; a -= rot(c,11); \ + b ^= a; b -= rot(a,25); \ + c ^= b; c -= rot(b,16); \ + a ^= c; a -= rot(c,4); \ + b ^= a; b -= rot(a,14); \ + c ^= b; c -= rot(b,24); \ +} + +/* +-------------------------------------------------------------------- + This works on all machines. To be useful, it requires + -- that the key be an array of uint32_t's, and + -- that the length be the number of uint32_t's in the key + + The function hashword() is identical to hashlittle() on little-endian + machines, and identical to hashbig() on big-endian machines, + except that the length has to be measured in uint32_ts rather than in + bytes. hashlittle() is more complicated than hashword() only because + hashlittle() has to dance around fitting the key bytes into registers. +-------------------------------------------------------------------- +*/ +uint32_t jenkins_hash32( +const uint32_t *k, /* the key, an array of uint32_t values */ +size_t length, /* the length of the key, in uint32_ts */ +uint32_t initval) /* the previous hash, or an arbitrary value */ +{ + uint32_t a,b,c; + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval; + + /*------------------------------------------------- handle most of the key */ + while (length > 3) + { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a,b,c); + length -= 3; + k += 3; + } + + /*------------------------------------------- handle the last 3 uint32_t's */ + switch(length) /* all the case statements fall through */ + { + case 3 : c+=k[2]; + case 2 : b+=k[1]; + case 1 : a+=k[0]; + final(a,b,c); + case 0: /* case 0: nothing left to add */ + break; + } + /*------------------------------------------------------ report the result */ + return c; +} + +#if BYTE_ORDER == LITTLE_ENDIAN +/* +------------------------------------------------------------------------------- +hashlittle() -- hash a variable-length key into a 32-bit value + k : the key (the unaligned variable-length array of bytes) + length : the length of the key, counting by bytes + initval : can be any 4-byte value +Returns a 32-bit value. Every bit of the key affects every bit of +the return value. Two keys differing by one or two bits will have +totally different hash values. + +The best hash table sizes are powers of 2. There is no need to do +mod a prime (mod is sooo slow!). If you need less than 32 bits, +use a bitmask. For example, if you need only 10 bits, do + h = (h & hashmask(10)); +In which case, the hash table should have hashsize(10) elements. + +If you are hashing n strings (uint8_t **)k, do it like this: + for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h); + +By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this +code any way you wish, private, educational, or commercial. It's free. + +Use for hash table lookup, or anything where one collision in 2^^32 is +acceptable. Do NOT use for cryptographic purposes. +------------------------------------------------------------------------------- +*/ + +uint32_t jenkins_hash( const void *key, size_t length, uint32_t initval) +{ + uint32_t a,b,c; /* internal state */ + union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; + + u.ptr = key; + if ((u.i & 0x3) == 0) { + const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ + + /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ + while (length > 12) + { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a,b,c); + length -= 12; + k += 3; + } + + /*----------------------------- handle the last (probably partial) block */ + /* + * "k[2]&0xffffff" actually reads beyond the end of the string, but + * then masks off the part it's not allowed to read. Because the + * string is aligned, the masked-off tail is in the same word as the + * rest of the string. Every machine with memory protection I've seen + * does it on word boundaries, so is OK with this. But VALGRIND will + * still catch it and complain. The masking trick does make the hash + * noticably faster for short strings (like English words). + */ + + switch(length) + { + case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; + case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; + case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; + case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; + case 8 : b+=k[1]; a+=k[0]; break; + case 7 : b+=k[1]&0xffffff; a+=k[0]; break; + case 6 : b+=k[1]&0xffff; a+=k[0]; break; + case 5 : b+=k[1]&0xff; a+=k[0]; break; + case 4 : a+=k[0]; break; + case 3 : a+=k[0]&0xffffff; break; + case 2 : a+=k[0]&0xffff; break; + case 1 : a+=k[0]&0xff; break; + case 0 : return c; /* zero length strings require no mixing */ + } + + } else if ((u.i & 0x1) == 0) { + const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ + const uint8_t *k8; + + /*--------------- all but last block: aligned reads and different mixing */ + while (length > 12) + { + a += k[0] + (((uint32_t)k[1])<<16); + b += k[2] + (((uint32_t)k[3])<<16); + c += k[4] + (((uint32_t)k[5])<<16); + mix(a,b,c); + length -= 12; + k += 6; + } + + /*----------------------------- handle the last (probably partial) block */ + k8 = (const uint8_t *)k; + switch(length) + { + case 12: c+=k[4]+(((uint32_t)k[5])<<16); + b+=k[2]+(((uint32_t)k[3])<<16); + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ + case 10: c+=k[4]; + b+=k[2]+(((uint32_t)k[3])<<16); + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 9 : c+=k8[8]; /* fall through */ + case 8 : b+=k[2]+(((uint32_t)k[3])<<16); + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ + case 6 : b+=k[2]; + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 5 : b+=k8[4]; /* fall through */ + case 4 : a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ + case 2 : a+=k[0]; + break; + case 1 : a+=k8[0]; + break; + case 0 : return c; /* zero length requires no mixing */ + } + + } else { /* need to read the key one byte at a time */ + const uint8_t *k = (const uint8_t *)key; + + /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ + while (length > 12) + { + a += k[0]; + a += ((uint32_t)k[1])<<8; + a += ((uint32_t)k[2])<<16; + a += ((uint32_t)k[3])<<24; + b += k[4]; + b += ((uint32_t)k[5])<<8; + b += ((uint32_t)k[6])<<16; + b += ((uint32_t)k[7])<<24; + c += k[8]; + c += ((uint32_t)k[9])<<8; + c += ((uint32_t)k[10])<<16; + c += ((uint32_t)k[11])<<24; + mix(a,b,c); + length -= 12; + k += 12; + } + + /*-------------------------------- last block: affect all 32 bits of (c) */ + switch(length) /* all the case statements fall through */ + { + case 12: c+=((uint32_t)k[11])<<24; + case 11: c+=((uint32_t)k[10])<<16; + case 10: c+=((uint32_t)k[9])<<8; + case 9 : c+=k[8]; + case 8 : b+=((uint32_t)k[7])<<24; + case 7 : b+=((uint32_t)k[6])<<16; + case 6 : b+=((uint32_t)k[5])<<8; + case 5 : b+=k[4]; + case 4 : a+=((uint32_t)k[3])<<24; + case 3 : a+=((uint32_t)k[2])<<16; + case 2 : a+=((uint32_t)k[1])<<8; + case 1 : a+=k[0]; + break; + case 0 : return c; + } + } + + final(a,b,c); + return c; +} + +#else /* !(BYTE_ORDER == LITTLE_ENDIAN) */ + +/* + * hashbig(): + * This is the same as hashword() on big-endian machines. It is different + * from hashlittle() on all machines. hashbig() takes advantage of + * big-endian byte ordering. + */ +uint32_t jenkins_hash( const void *key, size_t length, uint32_t initval) +{ + uint32_t a,b,c; + union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */ + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; + + u.ptr = key; + if ((u.i & 0x3) == 0) { + const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ + + /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ + while (length > 12) + { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a,b,c); + length -= 12; + k += 3; + } + + /*----------------------------- handle the last (probably partial) block */ + /* + * "k[2]<<8" actually reads beyond the end of the string, but + * then shifts out the part it's not allowed to read. Because the + * string is aligned, the illegal read is in the same word as the + * rest of the string. Every machine with memory protection I've seen + * does it on word boundaries, so is OK with this. But VALGRIND will + * still catch it and complain. The masking trick does make the hash + * noticably faster for short strings (like English words). + */ + + switch(length) + { + case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; + case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break; + case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break; + case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break; + case 8 : b+=k[1]; a+=k[0]; break; + case 7 : b+=k[1]&0xffffff00; a+=k[0]; break; + case 6 : b+=k[1]&0xffff0000; a+=k[0]; break; + case 5 : b+=k[1]&0xff000000; a+=k[0]; break; + case 4 : a+=k[0]; break; + case 3 : a+=k[0]&0xffffff00; break; + case 2 : a+=k[0]&0xffff0000; break; + case 1 : a+=k[0]&0xff000000; break; + case 0 : return c; /* zero length strings require no mixing */ + } + + } else { /* need to read the key one byte at a time */ + const uint8_t *k = (const uint8_t *)key; + + /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ + while (length > 12) + { + a += ((uint32_t)k[0])<<24; + a += ((uint32_t)k[1])<<16; + a += ((uint32_t)k[2])<<8; + a += ((uint32_t)k[3]); + b += ((uint32_t)k[4])<<24; + b += ((uint32_t)k[5])<<16; + b += ((uint32_t)k[6])<<8; + b += ((uint32_t)k[7]); + c += ((uint32_t)k[8])<<24; + c += ((uint32_t)k[9])<<16; + c += ((uint32_t)k[10])<<8; + c += ((uint32_t)k[11]); + mix(a,b,c); + length -= 12; + k += 12; + } + + /*-------------------------------- last block: affect all 32 bits of (c) */ + switch(length) /* all the case statements fall through */ + { + case 12: c+=k[11]; + case 11: c+=((uint32_t)k[10])<<8; + case 10: c+=((uint32_t)k[9])<<16; + case 9 : c+=((uint32_t)k[8])<<24; + case 8 : b+=k[7]; + case 7 : b+=((uint32_t)k[6])<<8; + case 6 : b+=((uint32_t)k[5])<<16; + case 5 : b+=((uint32_t)k[4])<<24; + case 4 : a+=k[3]; + case 3 : a+=((uint32_t)k[2])<<8; + case 2 : a+=((uint32_t)k[1])<<16; + case 1 : a+=((uint32_t)k[0])<<24; + break; + case 0 : return c; + } + } + + final(a,b,c); + return c; +} +#endif diff --git a/freebsd/sys/libkern/murmur3_32.c b/freebsd/sys/libkern/murmur3_32.c new file mode 100644 index 00000000..63ed07a8 --- /dev/null +++ b/freebsd/sys/libkern/murmur3_32.c @@ -0,0 +1,134 @@ +#include <machine/rtems-bsd-kernel-space.h> + +/*- + * Copyright (c) 2014 Dag-Erling Smørgrav + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * $FreeBSD$ + */ + +#include <sys/hash.h> +#include <sys/endian.h> +#include <sys/stdint.h> +#include <sys/types.h> + +#define rol32(i32, n) ((i32) << (n) | (i32) >> (32 - (n))) + +/* + * Simple implementation of the Murmur3-32 hash function. + * + * This implementation is slow but safe. It can be made significantly + * faster if the caller guarantees that the input is correctly aligned for + * 32-bit reads, and slightly faster yet if the caller guarantees that the + * length of the input is always a multiple of 4 bytes. + */ +uint32_t +murmur3_32_hash(const void *data, size_t len, uint32_t seed) +{ + const uint8_t *bytes; + uint32_t hash, k; + size_t res; + + /* initialization */ + bytes = data; + res = len; + hash = seed; + + /* main loop */ + while (res >= 4) { + /* replace with le32toh() if input is aligned */ + k = le32dec(bytes); + bytes += 4; + res -= 4; + k *= 0xcc9e2d51; + k = rol32(k, 15); + k *= 0x1b873593; + hash ^= k; + hash = rol32(hash, 13); + hash *= 5; + hash += 0xe6546b64; + } + + /* remainder */ + /* remove if input length is a multiple of 4 */ + if (res > 0) { + k = 0; + switch (res) { + case 3: + k |= bytes[2] << 16; + case 2: + k |= bytes[1] << 8; + case 1: + k |= bytes[0]; + k *= 0xcc9e2d51; + k = rol32(k, 15); + k *= 0x1b873593; + hash ^= k; + break; + } + } + + /* finalize */ + hash ^= (uint32_t)len; + hash ^= hash >> 16; + hash *= 0x85ebca6b; + hash ^= hash >> 13; + hash *= 0xc2b2ae35; + hash ^= hash >> 16; + return (hash); +} + +/* + * Simplified version of the above optimized for aligned sequences of + * 32-bit words. The count argument is the number of words, not the + * length in bytes. + */ +uint32_t +murmur3_32_hash32(const uint32_t *data, size_t count, uint32_t seed) +{ + uint32_t hash, k; + size_t res; + + /* iterate */ + for (res = count, hash = seed; res > 0; res--, data++) { + k = le32toh(*data); + k *= 0xcc9e2d51; + k = rol32(k, 15); + k *= 0x1b873593; + hash ^= k; + hash = rol32(hash, 13); + hash *= 5; + hash += 0xe6546b64; + } + + /* finalize */ + hash ^= (uint32_t)count; + hash ^= hash >> 16; + hash *= 0x85ebca6b; + hash ^= hash >> 13; + hash *= 0xc2b2ae35; + hash ^= hash >> 16; + return (hash); +} + diff --git a/freebsd/sys/libkern/random.c b/freebsd/sys/libkern/random.c index 6d6755a3..5b780670 100644 --- a/freebsd/sys/libkern/random.c +++ b/freebsd/sys/libkern/random.c @@ -52,7 +52,7 @@ srandom(seed) } /* - * Pseudo-random number generator for randomizing the profiling clock, + * Pseudo-random number generator for perturbing the profiling clock, * and whatever else we might use it for. The result is uniform on * [0, 2^31 - 1]. */ |