1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
/********************************************************************
* APRX -- 2nd generation APRS iGate and digi with *
* minimal requirement of esoteric facilities or *
* libraries of any kind beyond UNIX system libc. *
* *
* (c) Matti Aarnio - OH2MQK, 2007-2014 *
* *
********************************************************************/
/*
* Keyhash routines for the system.
*
* What is needed is _fast_ hash function. Preferrably arithmethic one,
* which does not need table lookups, and can work with aligned 32 bit
* data -- but also on unaligned, and on any byte counts...
*
* Contenders:
* http://burtleburtle.net/bob/c/lookup3.c
* http://www.ibiblio.org/pub/Linux/devel/lang/c/mph-1.2.tar.gz
* http://www.concentric.net/~Ttwang/tech/inthash.htm
* http://isthe.com/chongo/tech/comp/fnv/
*
* Currently using FNV-1a
*
*/
/*
// FNV-1a hash from http://isthe.com/chongo/tech/comp/fnv/
//
// It is algorithmic hash without memory lookups.
// Compiler seems to prefer actual multiplication over a bunch of
// fixed shifts and additions.
*/
#include <stdint.h>
#include <sys/types.h>
#include "keyhash.h"
void keyhash_init(void) { }
uint32_t __attribute__((pure)) keyhash(const void const *p, int len, uint32_t hash)
{
const uint8_t *u = p;
int i;
#define FNV_32_PRIME 16777619U
#define FNV_32_OFFSET 2166136261U
if (hash == 0)
hash = (uint32_t)FNV_32_OFFSET;
for (i = 0; i < len; ++i, ++u) {
#if defined(NO_FNV_GCC_OPTIMIZATION)
hash *= FNV_32_PRIME;
#else
hash += (hash<<1) + (hash<<4) + (hash<<7) +
(hash<<8) + (hash<<24);
#endif
hash ^= (uint32_t) *u;
}
return hash;
}
/* The data material is known to contain ASCII, and if any value in there
* is a lower case letter, it is first converted to upper case one.
*/
uint32_t __attribute__((pure)) keyhashuc(const void const *p, int len, uint32_t hash)
{
const uint8_t *u = p;
int i;
if (hash == 0)
hash = (uint32_t)FNV_32_OFFSET;
for (i = 0; i < len; ++i, ++u) {
#if defined(NO_FNV_GCC_OPTIMIZATION)
hash *= FNV_32_PRIME;
#else
hash += (hash<<1) + (hash<<4) + (hash<<7) +
(hash<<8) + (hash<<24);
#endif
uint32_t c = *u;
// Is it lower case ASCII letter ?
if ('a' <= c && c <= 'z') {
// convert to upper case.
c -= ('a' - 'A');
}
hash ^= c;
}
return hash;
}
|
