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
lutil_HASHInit(lutil_HASH_CTX * ctx)40 lutil_HASHInit( lutil_HASH_CTX *ctx )
41 {
42 ctx->hash = HASH_OFFSET;
43 }
44
45 /*
46 * Update hash
47 */
48 void
lutil_HASHUpdate(lutil_HASH_CTX * ctx,const unsigned char * buf,ber_len_t len)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
lutil_HASHFinal(unsigned char * digest,lutil_HASH_CTX * ctx)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
lutil_HASH64Init(lutil_HASH_CTX * ctx)94 lutil_HASH64Init( lutil_HASH_CTX *ctx )
95 {
96 ctx->hash64 = HASH64_OFFSET;
97 }
98
99 /*
100 * Update hash
101 */
102 void
lutil_HASH64Update(lutil_HASH_CTX * ctx,const unsigned char * buf,ber_len_t len)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
lutil_HASH64Final(unsigned char * digest,lutil_HASH_CTX * ctx)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