common/lib/libc/stdlib/mi_vector_hash.c

   1 /*      $NetBSD: mi_vector_hash.c,v 1.1 2013/12/11 01:24:08 joerg Exp $ */
   2 /*-
   3  * Copyright (c) 2009 The NetBSD Foundation, Inc.
   4  * All rights reserved.
   5  *
   6  * This code is derived from software contributed to The NetBSD Foundation
   7  * by Joerg Sonnenberger.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  *
  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
  17  *    the documentation and/or other materials provided with the
  18  *    distribution.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  24  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  25  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  28  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  29  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  30  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  */
  33
  34 /*
  35  * See http://burtleburtle.net/bob/hash/doobs.html for the full description
  36  * and the original version of the code.  This version differs by exposing
  37  * the full internal state and avoiding byte operations in the inner loop
  38  * if the key is aligned correctly.
  39  */
  40
  41 #if HAVE_NBTOOL_CONFIG_H
  42 #include "nbtool_config.h"
  43 #endif
  44
  45 #include <sys/cdefs.h>
  46 __RCSID("$NetBSD: mi_vector_hash.c,v 1.1 2013/12/11 01:24:08 joerg Exp $");
  47
  48 #if !HAVE_NBTOOL_CONFIG_H || HAVE_SYS_ENDIAN_H
  49 #include <sys/endian.h>
  50 #endif
  51
  52 #if defined(_KERNEL) || defined(_STANDALONE)
  53 #include <sys/types.h>
  54 #include <sys/systm.h>
  55 #include <lib/libkern/libkern.h>
  56 #else
  57 #include "namespace.h"
  58
  59 #include <stdint.h>
  60 #include <stdlib.h>
  61 #endif
  62
  63 #define mix(a, b, c) do {               \
  64         a -= b; a -= c; a ^= (c >> 13); \
  65         b -= c; b -= a; b ^= (a << 8);  \
  66         c -= a; c -= b; c ^= (b >> 13); \
  67         a -= b; a -= c; a ^= (c >> 12); \
  68         b -= c; b -= a; b ^= (a << 16); \
  69         c -= a; c -= b; c ^= (b >> 5);  \
  70         a -= b; a -= c; a ^= (c >> 3);  \
  71         b -= c; b -= a; b ^= (a << 10); \
  72         c -= a; c -= b; c ^= (b >> 15); \
  73 } while (/* CONSTCOND */0)
  74
  75 #define FIXED_SEED      0x9e3779b9      /* Golden ratio, arbitrary constant */
  76
  77 #if !defined(_KERNEL) && !defined(_STANDALONE)
  78 #ifdef __weak_alias
  79 __weak_alias(mi_vector_hash, _mi_vector_hash)
  80 #endif
  81 #endif
  82
  83 void
  84 mi_vector_hash(const void * __restrict key, size_t len, uint32_t seed,
  85     uint32_t hashes[3])
  86 {
  87         static const uint32_t mask[4] = {
  88                 0x000000ff, 0x0000ffff, 0x00ffffff, 0xffffffff
  89         };
  90         uint32_t orig_len, a, b, c;
  91         const uint8_t *k;
  92
  93         orig_len = (uint32_t)len;
  94
  95         a = b = FIXED_SEED;
  96         c = seed;
  97
  98         if ((uintptr_t)key & 3) {
  99                 k = key;
 100                 while (len >= 12) {
 101                         a += le32dec(k);
 102                         b += le32dec(k + 4);
 103                         c += le32dec(k + 8);
 104                         mix(a, b, c);
 105                         k += 12;
 106                         len -= 12;
 107                 }
 108                 c += orig_len;
 109
 110                 if (len > 8) {
 111                         switch (len) {
 112                         case 11:
 113                                 c += (uint32_t)k[10] << 24;
 114                                 /* FALLTHROUGH */
 115                         case 10:
 116                                 c += (uint32_t)k[9] << 16;
 117                                 /* FALLTHROUGH */
 118                         case 9:
 119                                 c += (uint32_t)k[8] << 8;
 120                                 /* FALLTHROUGH */
 121                         }
 122                         b += le32dec(k + 4);
 123                         a += le32dec(k);
 124                 } else if (len > 4) {
 125                         switch (len) {
 126                         case 8:
 127                                 b += (uint32_t)k[7] << 24;
 128                                 /* FALLTHROUGH */
 129                         case 7:
 130                                 b += (uint32_t)k[6] << 16;
 131                                 /* FALLTHROUGH */
 132                         case 6:
 133                                 b += (uint32_t)k[5] << 8;
 134                                 /* FALLTHROUGH */
 135                         case 5:
 136                                 b += k[4];
 137                                 /* FALLTHROUGH */
 138                         }
 139                         a += le32dec(k);
 140                 } else if (len) {
 141                         switch (len) {
 142                         case 4:
 143                                 a += (uint32_t)k[3] << 24;
 144                                 /* FALLTHROUGH */
 145                         case 3:
 146                                 a += (uint32_t)k[2] << 16;
 147                                 /* FALLTHROUGH */
 148                         case 2:
 149                                 a += (uint32_t)k[1] << 8;
 150                                 /* FALLTHROUGH */
 151                         case 1:
 152                                 a += k[0];
 153                                 /* FALLTHROUGH */
 154                         }
 155                 }
 156         } else {
 157                 const uint32_t *key32 = key;
 158                 while (len >= 12) {
 159                         a += le32toh(key32[0]);
 160                         b += le32toh(key32[1]);
 161                         c += le32toh(key32[2]);
 162                         mix(a, b, c);
 163                         key32 += 3;
 164                         len -= 12;
 165                 }
 166                 c += orig_len;
 167
 168                 if (len > 8) {
 169                         c += (le32toh(key32[2]) & mask[len - 9]) << 8;
 170                         b += le32toh(key32[1]);
 171                         a += le32toh(key32[0]);
 172                 } else if (len > 4) {
 173                         b += le32toh(key32[1]) & mask[len - 5];
 174                         a += le32toh(key32[0]);
 175                 } else if (len)
 176                         a += le32toh(key32[0]) & mask[len - 1];
 177         }
 178         mix(a, b, c);
 179         hashes[0] = a;
 180         hashes[1] = b;
 181         hashes[2] = c;
 182 }