1
/* This file implements a 64-bit FNV-1a hash UDF (user-defined function) for
2
* MySQL. The function accepts any number of arguments and returns a 64-bit
3
* unsigned integer. MySQL actually interprets the result as a signed integer,
4
* but you should ignore that. I chose not to return the number as a
5
* hexadecimal string because using an integer makes it possible to use it
6
* efficiently with BIT_XOR().
8
* The function never returns NULL, even when you give it NULL arguments.
10
* To compile and install, execute the following commands. The function name
11
* fnv1a_64 in the mysql command is case-sensitive! (Of course, when you
12
* actually call the function, it is case-insensitive just like any other SQL
15
* gcc -fPIC -Wall -I/usr/include/mysql -shared -o fnv1a_udf.so fnv1a_udf.cc
16
* cp fnv1a_udf.so /lib * OR: * cp fnv1a_udf.so /usr/lib
17
* mysql mysql -e "CREATE FUNCTION fnv1a_64 RETURNS INTEGER SONAME 'fnv1a_udf.so'"
19
* For MySQL version 4.1 or older you must add the following flag to the gcc
20
* command above: -DNO_DECIMAL_RESULT
21
* Otherwise you will get an error like:
22
* fnv1a_udf.cc:167: `DECIMAL_RESULT' undeclared (first use this function)
23
* (See http://code.google.com/p/maatkit/issues/detail?id=89)
25
* If you get the error "ERROR 1126 (HY000): Can't open shared library
26
* 'fnv1a_udf.so' (errno: 22 fnv1a_udf.so: cannot open shared object file: No
27
* such file or directory)" then you may need to copy the .so file to another
28
* location in your system. Look at your environment's $LD_LIBRARY_PATH
29
* variable for clues. If none is set, you may need to set this variable to
30
* something like /lib.
32
* If you get the error "ERROR 1126 (HY000): Can't open shared library
33
* 'libfnv1a_udf.so' (errno: 22 /lib/libfnv1a_udf.so: undefined symbol:
34
* __gxx_personality_v0)" then you may need to use g++ instead of gcc.
36
* Try both /lib and /usr/lib before changing LD_LIBRARY_PATH.
38
* On Mac OSX, use -dynamiclib instead of -shared and add -lstdc++ to the
41
* Once installed successfully, you should be able to call the function. Here's
42
* a faster alternative to MD5 hashing, with the added ability to hash multiple
43
* arguments in a single call:
45
* mysql> SELECT FNV1A_64('hello', 'world');
47
* Here's a way to reduce an entire table to a single order-independent hash:
49
* mysql> SELECT BIT_XOR(CAST(FNV1A_64(col1, col2, col3) AS UNSIGNED)) FROM tbl;
53
/* The following header is from hash_64a.c:
55
* hash_64 - 64 bit Fowler/Noll/Vo-0 FNV-1a hash code
57
* @(#) $Revision: 5.1 $
58
* @(#) $Id: hash_64a.c,v 5.1 2009/06/30 09:01:38 chongo Exp $
59
* @(#) $Source: /usr/local/src/cmd/fnv/RCS/hash_64a.c,v $
65
* The basis of this hash algorithm was taken from an idea sent
66
* as reviewer comments to the IEEE POSIX P1003.2 committee by:
68
* Phong Vo (http://www.research.att.com/info/kpv/)
69
* Glenn Fowler (http://www.research.att.com/~gsf/)
71
* In a subsequent ballot round:
73
* Landon Curt Noll (http://www.isthe.com/chongo/)
75
* improved on their algorithm. Some people tried this hash
76
* and found that it worked rather well. In an EMail message
77
* to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
79
* FNV hashes are designed to be fast while maintaining a low
80
* collision rate. The FNV speed allows one to quickly hash lots
81
* of data while maintaining a reasonable collision rate. See:
83
* http://www.isthe.com/chongo/tech/comp/fnv/index.html
85
* for more details as well as other forms of the FNV hash.
89
* To use the recommended 64 bit FNV-1a hash, pass FNV1A_64_INIT as the
90
* Fnv64_t hashval argument to fnv_64a_buf() or fnv_64a_str().
94
* Please do not copyright this code. This code is in the public domain.
96
* LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
97
* INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
98
* EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
99
* CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
100
* USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
101
* OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
102
* PERFORMANCE OF THIS SOFTWARE.
105
* chongo <Landon Curt Noll> /\oo/\
106
* http://www.isthe.com/chongo/
108
* Share and Enjoy! :-)
111
#include <my_global.h>
117
/* On the first call, use this as the initial_value. */
118
#define FNV1A_64_INIT 0xcbf29ce484222325ULL
119
/* Default for NULLs, just so the result is never NULL. */
120
#define HASH_NULL_DEFAULT 0x0a0b0c0d
121
/* Magic number for the hashing. */
122
#define FNV_64_PRIME 0x100000001b3ULL
127
ulonglong hash64a(const void *buf, size_t len, ulonglong hval);
128
my_bool fnv1a_64_init(UDF_INIT* initid, UDF_ARGS* args, char* message);
129
ulonglong fnv1a_64(UDF_INIT *initid, UDF_ARGS *args, char *is_null, char *error );
132
/* Implementations */
134
ulonglong hash64a(const void *buf, size_t len, ulonglong hval) {
135
const unsigned char *bp = (const unsigned char*)buf;
136
const unsigned char *be = bp + len;
138
/* FNV-1a hash each octet of the buffer */
139
for (; bp != be; ++bp) {
140
/* xor the bottom with the current octet */
141
hval ^= (ulonglong)*bp;
142
/* multiply by the 64 bit FNV magic prime mod 2^64 */
143
hval *= FNV_64_PRIME;
150
fnv1a_64_init(UDF_INIT* initid, UDF_ARGS* args, char* message) {
151
if (args->arg_count == 0 ) {
152
strcpy(message,"FNV1A_64 requires at least one argument");
155
initid->maybe_null = 0; /* The result will never be NULL */
160
fnv1a_64(UDF_INIT *initid, UDF_ARGS *args, char *is_null, char *error) {
162
uint null_default = HASH_NULL_DEFAULT;
163
ulonglong result = FNV1A_64_INIT;
166
for (i = 0 ; i < args->arg_count; ++i ) {
167
if ( args->args[i] != NULL ) {
168
switch ( args->arg_type[i] ) {
170
#ifdef NO_DECIMAL_RESULT
175
= hash64a((const void*) args->args[i], args->lengths[i], result);
180
real_val = *((double*) args->args[i]);
182
= hash64a((const void*)&real_val, sizeof(double), result);
188
int_val = *((long long*) args->args[i]);
189
result = hash64a((const void*)&int_val, sizeof(ulonglong), result);
198
= hash64a((const void*)&null_default, sizeof(null_default), result);