Branch data     Line data    Source code

       1                 :            : /*
       2                 :            :  * libdpkg - Debian packaging suite library routines
       3                 :            :  * strhash.c - FNV string hashing support
       4                 :            :  *
       5                 :            :  * Copyright © 2003 Daniel Silverstone <dsilvers@digital-scurf.org>
       6                 :            :  *
       7                 :            :  * This is free software; you can redistribute it and/or modify
       8                 :            :  * it under the terms of the GNU General Public License as published by
       9                 :            :  * the Free Software Foundation; either version 2 of the License, or
      10                 :            :  * (at your option) any later version.
      11                 :            :  *
      12                 :            :  * This is distributed in the hope that it will be useful,
      13                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      14                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15                 :            :  * GNU General Public License for more details.
      16                 :            :  *
      17                 :            :  * You should have received a copy of the GNU General Public License
      18                 :            :  * along with this program.  If not, see <https://www.gnu.org/licenses/>.
      19                 :            :  */
      20                 :            : 
      21                 :            : #include <config.h>
      22                 :            : #include <compat.h>
      23                 :            : 
      24                 :            : #include <dpkg/string.h>
      25                 :            : 
      26                 :            : #define FNV_OFFSET_BASIS 2166136261UL
      27                 :            : #define FNV_MIXING_PRIME 16777619UL
      28                 :            : 
      29                 :            : /**
      30                 :            :  * Fowler/Noll/Vo -- FNV-1a simple string hash.
      31                 :            :  *
      32                 :            :  * For more info, @see <http://www.isthe.com/chongo/tech/comp/fnv/index.html>.
      33                 :            :  *
      34                 :            :  * @param str The string to hash.
      35                 :            :  *
      36                 :            :  * @return The hashed value.
      37                 :            :  */
      38                 :            : unsigned int
      39                 :        409 : str_fnv_hash(const char *str)
      40                 :            : {
      41                 :        409 :         register unsigned int h = FNV_OFFSET_BASIS;
      42                 :        409 :         register unsigned int p = FNV_MIXING_PRIME;
      43                 :            : 
      44         [ +  + ]:       6005 :         while (*str) {
      45                 :       5596 :                 h ^= *str++;
      46                 :       5596 :                 h *= p;
      47                 :            :         }
      48                 :            : 
      49                 :        409 :         return h;
      50                 :            : }