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