sysdeps/generic/dl-hash.h

   1 /* Compute hash value for given string according to ELF standard.
   2    Copyright (C) 1995-2015 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    The GNU C Library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, see
  17    <http://www.gnu.org/licenses/>.  */
  18
  19 #ifndef _DL_HASH_H
  20 #define _DL_HASH_H      1
  21
  22
  23 /* This is the hashing function specified by the ELF ABI.  In the
  24    first five operations no overflow is possible so we optimized it a
  25    bit.  */
  26 static unsigned int
  27 __attribute__ ((unused))
  28 _dl_elf_hash (const char *name_arg)
  29 {
  30   const unsigned char *name = (const unsigned char *) name_arg;
  31   unsigned long int hash = *name;
  32   if (hash != 0 && name[1] != '\0')
  33     {
  34       hash = (hash << 4) + name[1];
  35       if (name[2] != '\0')
  36         {
  37           hash = (hash << 4) + name[2];
  38           if (name[3] != '\0')
  39             {
  40               hash = (hash << 4) + name[3];
  41               if (name[4] != '\0')
  42                 {
  43                   hash = (hash << 4) + name[4];
  44                   name += 5;
  45                   while (*name != '\0')
  46                     {
  47                       unsigned long int hi;
  48                       hash = (hash << 4) + *name++;
  49                       hi = hash & 0xf0000000;
  50
  51                       /* The algorithm specified in the ELF ABI is as
  52                          follows:
  53
  54                          if (hi != 0)
  55                            hash ^= hi >> 24;
  56
  57                          hash &= ~hi;
  58
  59                          But the following is equivalent and a lot
  60                          faster, especially on modern processors.  */
  61
  62                       hash ^= hi >> 24;
  63                     }
  64
  65                   /* Second part of the modified formula.  This
  66                      operation can be lifted outside the loop.  */
  67                   hash &= 0x0fffffff;
  68                 }
  69             }
  70         }
  71     }
  72   return hash;
  73 }
  74
  75 #endif /* dl-hash.h */