git.sur5r.net Git - openldap/blob - libraries/liblutil/hash.c

   1 /* $OpenLDAP$ */
   2 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   3  *
   4  * Copyright 2000-2018 The OpenLDAP Foundation.
   5  * Portions Copyright 2000-2003 Kurt D. Zeilenga.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted only as authorized by the OpenLDAP
  10  * Public License.
  11  *
  12  * A copy of this license is available in the file LICENSE in the
  13  * top-level directory of the distribution or, alternatively, at
  14  * <http://www.OpenLDAP.org/license.html>.
  15  */
  16
  17 /* This implements the Fowler / Noll / Vo (FNV-1) hash algorithm.
  18  * A summary of the algorithm can be found at:
  19  *   http://www.isthe.com/chongo/tech/comp/fnv/index.html
  20  */
  21
  22 #include "portable.h"
  23
  24 #include <lutil_hash.h>
  25
  26 /* offset and prime for 32-bit FNV-1 */
  27 #define HASH_OFFSET     0x811c9dc5U
  28 #define HASH_PRIME      16777619
  29
  30
  31 /*
  32  * Initialize context
  33  */
  34 void
  35 lutil_HASHInit( lutil_HASH_CTX *ctx )
  36 {
  37         ctx->hash = HASH_OFFSET;
  38 }
  39
  40 /*
  41  * Update hash
  42  */
  43 void
  44 lutil_HASHUpdate(
  45     lutil_HASH_CTX      *ctx,
  46     const unsigned char         *buf,
  47     ber_len_t           len )
  48 {
  49         const unsigned char *p, *e;
  50         ber_uint_t h;
  51
  52         p = buf;
  53         e = &buf[len];
  54
  55         h = ctx->hash;
  56
  57         while( p < e ) {
  58                 h *= HASH_PRIME;
  59                 h ^= *p++;
  60         }
  61
  62         ctx->hash = h;
  63 }
  64
  65 /*
  66  * Save hash
  67  */
  68 void
  69 lutil_HASHFinal( unsigned char *digest, lutil_HASH_CTX *ctx )
  70 {
  71         ber_uint_t h = ctx->hash;
  72
  73         digest[0] = h & 0xffU;
  74         digest[1] = (h>>8) & 0xffU;
  75         digest[2] = (h>>16) & 0xffU;
  76         digest[3] = (h>>24) & 0xffU;
  77 }
  78
  79 #ifdef HAVE_LONG_LONG
  80
  81 /* 64 bit Fowler/Noll/Vo-O FNV-1a hash code */
  82
  83 #define HASH64_OFFSET   0xcbf29ce484222325ULL
  84
  85 /*
  86  * Initialize context
  87  */
  88 void
  89 lutil_HASH64Init( lutil_HASH_CTX *ctx )
  90 {
  91         ctx->hash64 = HASH64_OFFSET;
  92 }
  93
  94 /*
  95  * Update hash
  96  */
  97 void
  98 lutil_HASH64Update(
  99     lutil_HASH_CTX      *ctx,
 100     const unsigned char         *buf,
 101     ber_len_t           len )
 102 {
 103         const unsigned char *p, *e;
 104         unsigned long long h;
 105
 106         p = buf;
 107         e = &buf[len];
 108
 109         h = ctx->hash64;
 110
 111         while( p < e ) {
 112                 /* xor the bottom with the current octet */
 113                 h ^= *p++;
 114
 115                 /* multiply by the 64 bit FNV magic prime mod 2^64 */
 116                 h += (h << 1) + (h << 4) + (h << 5) +
 117                         (h << 7) + (h << 8) + (h << 40);
 118
 119         }
 120
 121         ctx->hash64 = h;
 122 }
 123
 124 /*
 125  * Save hash
 126  */
 127 void
 128 lutil_HASH64Final( unsigned char *digest, lutil_HASH_CTX *ctx )
 129 {
 130         unsigned long long h = ctx->hash64;
 131
 132         digest[0] = h & 0xffU;
 133         digest[1] = (h>>8) & 0xffU;
 134         digest[2] = (h>>16) & 0xffU;
 135         digest[3] = (h>>24) & 0xffU;
 136         digest[4] = (h>>32) & 0xffU;
 137         digest[5] = (h>>40) & 0xffU;
 138         digest[6] = (h>>48) & 0xffU;
 139         digest[7] = (h>>56) & 0xffU;
 140 }
 141 #endif /* HAVE_LONG_LONG */