Line data    Source code

       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       89107 : _dl_elf_hash (const char *name_arg)
      29             : {
      30       89107 :   const unsigned char *name = (const unsigned char *) name_arg;
      31       89107 :   unsigned long int hash = *name;
      32       89107 :   if (hash != 0 && name[1] != '\0')
      33             :     {
      34       89085 :       hash = (hash << 4) + name[1];
      35       89085 :       if (name[2] != '\0')
      36             :         {
      37       88904 :           hash = (hash << 4) + name[2];
      38       88904 :           if (name[3] != '\0')
      39             :             {
      40       87087 :               hash = (hash << 4) + name[3];
      41       87087 :               if (name[4] != '\0')
      42             :                 {
      43       69069 :                   hash = (hash << 4) + name[4];
      44       69069 :                   name += 5;
      45      150284 :                   while (*name != '\0')
      46             :                     {
      47             :                       unsigned long int hi;
      48       12146 :                       hash = (hash << 4) + *name++;
      49       12146 :                       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       12146 :                       hash ^= hi >> 24;
      63             :                     }
      64             : 
      65             :                   /* Second part of the modified formula.  This
      66             :                      operation can be lifted outside the loop.  */
      67       69069 :                   hash &= 0x0fffffff;
      68             :                 }
      69             :             }
      70             :         }
      71             :     }
      72       89107 :   return hash;
      73             : }
      74             : 
      75             : #endif /* dl-hash.h */