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                 :         425 : str_fnv_hash(const char *str)
      40                 :             : {
      41                 :         425 :         unsigned int h = FNV_OFFSET_BASIS;
      42                 :         425 :         unsigned int p = FNV_MIXING_PRIME;
      43                 :             : 
      44         [ +  + ]:        6245 :         while (*str) {
      45                 :        5820 :                 h ^= *str++;
      46                 :        5820 :                 h *= p;
      47                 :             :         }
      48                 :             : 
      49                 :         425 :         return h;
      50                 :             : }