1156592Sandre/*- 2156592Sandre * Copyright (c) 2001 Tobias Weingartner 3156592Sandre * All rights reserved. 4156592Sandre * 5156592Sandre * Redistribution and use in source and binary forms, with or without 6156592Sandre * modification, are permitted provided that the following conditions 7156592Sandre * are met: 8156592Sandre * 1. Redistributions of source code must retain the above copyright 9156592Sandre * notice, this list of conditions and the following disclaimer. 10156592Sandre * 2. Redistributions in binary form must reproduce the above copyright 11156592Sandre * notice, this list of conditions and the following disclaimer in the 12156592Sandre * documentation and/or other materials provided with the distribution. 13156592Sandre * 14156592Sandre * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 15156592Sandre * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 16156592Sandre * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 17156592Sandre * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 18156592Sandre * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 19156592Sandre * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 20156592Sandre * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 21156592Sandre * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22156592Sandre * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 23156592Sandre * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24156592Sandre * 25156592Sandre * $OpenBSD: hash.h,v 1.4 2004/05/25 18:37:23 jmc Exp $ 26156592Sandre * $FreeBSD$ 27156592Sandre */ 28156592Sandre 29156592Sandre#ifndef _SYS_HASH_H_ 30156592Sandre#define _SYS_HASH_H_ 31156592Sandre#include <sys/types.h> 32156592Sandre 33156592Sandre/* Convenience */ 34156592Sandre#ifndef HASHINIT 35156592Sandre#define HASHINIT 5381 36156592Sandre#define HASHSTEP(x,c) (((x << 5) + x) + (c)) 37156592Sandre#endif 38156592Sandre 39156592Sandre/* 40156592Sandre * Return a 32-bit hash of the given buffer. The init 41156592Sandre * value should be 0, or the previous hash value to extend 42156592Sandre * the previous hash. 43156592Sandre */ 44156592Sandrestatic __inline uint32_t 45156592Sandrehash32_buf(const void *buf, size_t len, uint32_t hash) 46156592Sandre{ 47156592Sandre const unsigned char *p = buf; 48156592Sandre 49156592Sandre while (len--) 50156592Sandre hash = HASHSTEP(hash, *p++); 51156592Sandre 52156592Sandre return hash; 53156592Sandre} 54156592Sandre 55156592Sandre/* 56156592Sandre * Return a 32-bit hash of the given string. 57156592Sandre */ 58156592Sandrestatic __inline uint32_t 59156592Sandrehash32_str(const void *buf, uint32_t hash) 60156592Sandre{ 61156592Sandre const unsigned char *p = buf; 62156592Sandre 63156592Sandre while (*p) 64156592Sandre hash = HASHSTEP(hash, *p++); 65156592Sandre 66156592Sandre return hash; 67156592Sandre} 68156592Sandre 69156592Sandre/* 70156592Sandre * Return a 32-bit hash of the given string, limited by N. 71156592Sandre */ 72156592Sandrestatic __inline uint32_t 73156592Sandrehash32_strn(const void *buf, size_t len, uint32_t hash) 74156592Sandre{ 75156592Sandre const unsigned char *p = buf; 76156592Sandre 77156592Sandre while (*p && len--) 78156592Sandre hash = HASHSTEP(hash, *p++); 79156592Sandre 80156592Sandre return hash; 81156592Sandre} 82156592Sandre 83156592Sandre/* 84156592Sandre * Return a 32-bit hash of the given string terminated by C, 85156592Sandre * (as well as 0). This is mainly here as a helper for the 86156592Sandre * namei() hashing of path name parts. 87156592Sandre */ 88156592Sandrestatic __inline uint32_t 89168557Sthompsahash32_stre(const void *buf, int end, const char **ep, uint32_t hash) 90156592Sandre{ 91156592Sandre const unsigned char *p = buf; 92156592Sandre 93156592Sandre while (*p && (*p != end)) 94156592Sandre hash = HASHSTEP(hash, *p++); 95156592Sandre 96156592Sandre if (ep) 97168557Sthompsa *ep = p; 98156592Sandre 99156592Sandre return hash; 100156592Sandre} 101156592Sandre 102156592Sandre/* 103156592Sandre * Return a 32-bit hash of the given string, limited by N, 104156592Sandre * and terminated by C (as well as 0). This is mainly here 105156592Sandre * as a helper for the namei() hashing of path name parts. 106156592Sandre */ 107156592Sandrestatic __inline uint32_t 108168557Sthompsahash32_strne(const void *buf, size_t len, int end, const char **ep, 109168557Sthompsa uint32_t hash) 110156592Sandre{ 111156592Sandre const unsigned char *p = buf; 112156592Sandre 113156592Sandre while (*p && (*p != end) && len--) 114156592Sandre hash = HASHSTEP(hash, *p++); 115156592Sandre 116156592Sandre if (ep) 117168557Sthompsa *ep = p; 118156592Sandre 119156592Sandre return hash; 120156592Sandre} 121240086Sglebius 122240086Sglebius#ifdef _KERNEL 123240086Sglebius/* 124240086Sglebius * Hashing function from Bob Jenkins. Implementation in libkern/jenkins_hash.c. 125240086Sglebius */ 126240086Sglebiusuint32_t jenkins_hash(const void *, size_t, uint32_t); 127240086Sglebiusuint32_t jenkins_hash32(const uint32_t *, size_t, uint32_t); 128274486Sgnn 129274486Sgnnuint32_t murmur3_aligned_32(const void *data, size_t len, uint32_t seed); 130274486Sgnn 131240086Sglebius#endif /* _KERNEL */ 132240086Sglebius 133156592Sandre#endif /* !_SYS_HASH_H_ */ 134