nss/nss_hash.c

   1 /* Copyright (c) 1997-2022 Free Software Foundation, Inc.
   2    This file is part of the GNU C Library.
   3
   4    The GNU C Library is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU Lesser General Public
   6    License as published by the Free Software Foundation; either
   7    version 2.1 of the License, or (at your option) any later version.
   8
   9    The GNU C Library is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    Lesser General Public License for more details.
  13
  14    You should have received a copy of the GNU Lesser General Public
  15    License along with the GNU C Library; if not, see
  16    <https://www.gnu.org/licenses/>.  */
  17
  18 #include <nss.h>
  19
  20 /* This is from libc/db/hash/hash_func.c, hash3 is static there */
  21 /*
  22  * This is INCREDIBLY ugly, but fast.  We break the string up into 4 byte
  23  * units.  On the first time through the loop we get the "leftover bytes"
  24  * (len % 4).  On every other iteration, we perform a 4x unrolled version
  25  * HASHC. Further unrolling does not appear to help.
  26  *
  27  * OZ's original sdbm hash
  28  */
  29 uint32_t
  30 __nss_hash (const void *keyarg, size_t len)
  31 {
  32   enum
  33   {
  34     HASH_CONST_P0 = 1,         /* (uint32_t)(65599 ^ 0).  */
  35     HASH_CONST_P1 = 65599,     /* (uint32_t)(65599 ^ 1).  */
  36     HASH_CONST_P2 = 8261505,   /* (uint32_t)(65599 ^ 2).  */
  37     HASH_CONST_P3 = 780587199, /* (uint32_t)(65599 ^ 3).  */
  38     HASH_CONST_P4 = 1139564289 /* (uint32_t)(65599 ^ 4).  */
  39   };
  40
  41   const unsigned char *key;
  42   uint32_t h;
  43
  44 #define HASHC   h = *key++ + HASH_CONST_P1 * h
  45
  46   h = 0;
  47   key = keyarg;
  48   if (len > 0)
  49     {
  50       switch ((len & (4 - 1)))
  51         {
  52         case 0:
  53           /* h starts out as zero so no need to include the multiply. */
  54           h = *key++;
  55           /* FALLTHROUGH */
  56         case 3:
  57           HASHC;
  58           /* FALLTHROUGH */
  59         case 2:
  60           HASHC;
  61           /* FALLTHROUGH */
  62         case 1:
  63           HASHC;
  64           /* FALLTHROUGH */
  65         }
  66
  67       uint32_t c0, c1, c2, c3;
  68       for (--len; len >= 4; len -= 4)
  69         {
  70           c0 = (unsigned char) *(key + 0);
  71           c1 = (unsigned char) *(key + 1);
  72           c2 = (unsigned char) *(key + 2);
  73           c3 = (unsigned char) *(key + 3);
  74           h = HASH_CONST_P4 * h + HASH_CONST_P3 * c0 + HASH_CONST_P2 * c1
  75               + HASH_CONST_P1 * c2 + HASH_CONST_P0 * c3;
  76
  77           key += 4;
  78         }
  79     }
  80   return h;
  81 }
  82
  83
  84 libc_hidden_def (__nss_hash)