lib/libpuffs/hash.h

   1 /*      $NetBSD: hash.h,v 1.6 2008/04/28 20:24:10 martin Exp $  */
   2
   3 /*-
   4  * Copyright (c) 2001 The NetBSD Foundation, Inc.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to The NetBSD Foundation
   8  * by Luke Mewburn.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29  * POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 #ifndef _SYS_HASH_H_
  33 #define _SYS_HASH_H_
  34
  35 #include <sys/types.h>
  36 #ifdef __HAVE_MACHINE_HASH_H
  37 #include <machine/hash.h>
  38 #endif
  39
  40
  41 #ifndef __HAVE_HASH32_BUF                       /* not overridden by MD hash */
  42
  43 #define HASH32_BUF_INIT 5381
  44
  45 /*
  46  * uint32_t
  47  * hash32_buf(const void *bf, size_t len, uint32_t hash)
  48  *      return a 32 bit hash of the binary buffer buf (size len),
  49  *      seeded with an initial hash value of hash (usually HASH32_BUF_INIT).
  50  */
  51 static __inline uint32_t
  52 hash32_buf(const void *bf, size_t len, uint32_t hash)
  53 {
  54         const uint8_t *s = bf;
  55
  56         while (len-- != 0)                      /* "nemesi": k=257, r=r*257 */
  57                 hash = hash * 257 + *s++;
  58         return (hash * 257);
  59 }
  60 #endif  /* __HAVE_HASH32_BUF */
  61
  62
  63 #ifndef __HAVE_HASH32_STR                       /* not overridden by MD hash */
  64
  65 #define HASH32_STR_INIT 5381
  66 /*
  67  * uint32_t
  68  * hash32_str(const void *bf, uint32_t hash)
  69  *      return a 32 bit hash of NUL terminated ASCII string buf,
  70  *      seeded with an initial hash value of hash (usually HASH32_STR_INIT).
  71  */
  72 static __inline uint32_t
  73 hash32_str(const void *bf, uint32_t hash)
  74 {
  75         const uint8_t *s = bf;
  76         uint8_t c;
  77
  78         while ((c = *s++) != 0)
  79                 hash = hash * 33 + c;           /* "perl": k=33, r=r+r/32 */
  80         return (hash + (hash >> 5));
  81 }
  82
  83 /*
  84  * uint32_t
  85  * hash32_strn(const void *bf, size_t len, uint32_t hash)
  86  *      return a 32 bit hash of NUL terminated ASCII string buf up to
  87  *      a maximum of len bytes,
  88  *      seeded with an initial hash value of hash (usually HASH32_STR_INIT).
  89  */
  90 static __inline uint32_t
  91 hash32_strn(const void *bf, size_t len, uint32_t hash)
  92 {
  93         const uint8_t   *s = bf;
  94         uint8_t c;
  95
  96         while ((c = *s++) != 0 && len-- != 0)
  97                 hash = hash * 33 + c;           /* "perl": k=33, r=r+r/32 */
  98         return (hash + (hash >> 5));
  99 }
 100 #endif  /* __HAVE_HASH32_STR */
 101
 102
 103 #endif  /* !_SYS_HASH_H_ */