File: keyhash.c

package info (click to toggle)
aprx 2.9.0+dfsg-2
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 2,352 kB
  • sloc: ansic: 15,809; sh: 598; makefile: 160
file content (91 lines) | stat: -rw-r--r-- 2,554 bytes parent folder | download | duplicates (2)
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;
}