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