1 /*
2 * aprsc
3 *
4 * (c) Matti Aarnio, OH2MQK, <oh2mqk@sral.fi>
5 *
6 * This program is licensed under the BSD license, which can be found
7 * in the file LICENSE.
8 *
9 */
10
11 /*
12 * Keyhash routines for the system.
13 *
14 * What is needed is _fast_ hash function. Preferrably arithmethic one,
15 * which does not need table lookups, and can work with aligned 32 bit
16 * data -- but also on unaligned, and on any byte counts...
17 *
18 * Contenders:
19 * http://burtleburtle.net/bob/c/lookup3.c
20 * http://www.ibiblio.org/pub/Linux/devel/lang/c/mph-1.2.tar.gz
21 * http://www.concentric.net/~Ttwang/tech/inthash.htm
22 * http://isthe.com/chongo/tech/comp/fnv/
23 *
24 * Currently using FNV-1a
25 *
26 */
27
28 /*
29 // FNV-1a hash from http://isthe.com/chongo/tech/comp/fnv/
30 //
31 // It is algorithmic hash without memory lookups.
32 // Compiler seems to prefer actual multiplication over a bunch of
33 // fixed shifts and additions.
34 */
35
36
37 /*
38 * ON A HIGHLY OPTIMIZED CRC32 HASH CALCULATION PROCESSING ALONE
39 * THE SYSTEM IS PUSHING AROUND 8-12 % OF CPU TIME!
40 *
41 * ... but the previous top waster, the aprsc output filters, are optimized
42 * to the hilt...
43 *
44 * There exists alternate implementations of CRC32 which are 1.7 - 2.3 times
45 * faster than this one with an expense of using 4kB / 8 kB / 16 kB of tables,
46 * which of course fill caches...
47 *
48 */
49
50 #include <stdint.h>
51 #include <sys/types.h>
52
53 #include "keyhash.h"
54
55 #ifdef __GNUC__ // compiling with GCC ?
56
57 #define likely(x) __builtin_expect(!!(x), 1)
58 #define unlikely(x) __builtin_expect(!!(x), 0)
59
60 #else
61
62 #define likely(x) (x)
63 #define unlikely(x) (x)
64
65 #define __attribute__(x)
66
67 #endif
68
keyhash_init(void)69 void keyhash_init(void) { }
70
keyhash(const void * p,int len,uint32_t hash)71 uint32_t __attribute__((pure)) keyhash(const void *p, int len, uint32_t hash)
72 {
73 const uint8_t *u = p;
74 int i;
75 #define FNV_32_PRIME 16777619U
76 #define FVN_32_OFFSET 2166136261U
77
78 if (hash == 0)
79 hash = (uint32_t)FVN_32_OFFSET;
80
81 for (i = 0; i < len; ++i, ++u) {
82 #if defined(NO_FNV_GCC_OPTIMIZATION)
83 hash *= FNV_32_PRIME;
84 #else
85 hash += (hash<<1) + (hash<<4) + (hash<<7) +
86 (hash<<8) + (hash<<24);
87 #endif
88 hash ^= (uint32_t) *u;
89 }
90 return hash;
91 }
92
93 /* The data material is known to contain ASCII, and if any value in there
94 * is a lower case letter, it is first converted to upper case one.
95 */
keyhashuc(const void * p,int len,uint32_t hash)96 uint32_t __attribute__((pure)) keyhashuc(const void *p, int len, uint32_t hash)
97 {
98 const uint8_t *u = p;
99 int i;
100
101 if (hash == 0)
102 hash = (uint32_t)FVN_32_OFFSET;
103
104 for (i = 0; i < len; ++i, ++u) {
105 #if defined(NO_FNV_GCC_OPTIMIZATION)
106 hash *= FNV_32_PRIME;
107 #else
108 hash += (hash<<1) + (hash<<4) + (hash<<7) +
109 (hash<<8) + (hash<<24);
110 #endif
111 uint32_t c = *u;
112 // Is it lower case ASCII letter ?
113 if ('a' <= c && c <= 'z') {
114 // convert to upper case.
115 c -= ('a' - 'A');
116 }
117 hash ^= c;
118 }
119 return hash;
120 }
121