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().
7 *
8 * The function never returns NULL, even when you give it NULL arguments.
9 *
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
13 * function).
14 *
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'"
18 *
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)
24 *
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.
31 *
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.
35 *
36 * Try both /lib and /usr/lib before changing LD_LIBRARY_PATH.
37 *
38 * On Mac OSX, use -dynamiclib instead of -shared and add -lstdc++ to the
39 * compile flags.
40 *
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:
44 *
45 * mysql> SELECT FNV1A_64('hello', 'world');
46 *
47 * Here's a way to reduce an entire table to a single order-independent hash:
48 *
49 * mysql> SELECT BIT_XOR(CAST(FNV1A_64(col1, col2, col3) AS UNSIGNED)) FROM tbl;
50 *
51 */
52
53 /* The following header is from hash_64a.c:
54 *
55 * hash_64 - 64 bit Fowler/Noll/Vo-0 FNV-1a hash code
56 *
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 $
60 *
61 ***
62 *
63 * Fowler/Noll/Vo hash
64 *
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:
67 *
68 * Phong Vo (http://www.research.att.com/info/kpv/)
69 * Glenn Fowler (http://www.research.att.com/~gsf/)
70 *
71 * In a subsequent ballot round:
72 *
73 * Landon Curt Noll (http://www.isthe.com/chongo/)
74 *
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.
78 *
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:
82 *
83 * http://www.isthe.com/chongo/tech/comp/fnv/index.html
84 *
85 * for more details as well as other forms of the FNV hash.
86 *
87 ***
88 *
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().
91 *
92 ***
93 *
94 * Please do not copyright this code. This code is in the public domain.
95 *
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.
103 *
104 * By:
105 * chongo <Landon Curt Noll> /\oo/\
106 * http://www.isthe.com/chongo/
107 *
108 * Share and Enjoy! :-)
109 */
110
111 #include <my_global.h>
112 #include <my_sys.h>
113 #include <mysql.h>
114 #include <ctype.h>
115 #include <string.h>
116
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
123
124 /* Prototypes */
125
126 extern "C" {
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 );
130 }
131
132 /* Implementations */
133
hash64a(const void * buf,size_t len,ulonglong hval)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;
137
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;
144 }
145
146 return hval;
147 }
148
149 my_bool
fnv1a_64_init(UDF_INIT * initid,UDF_ARGS * args,char * message)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");
153 return 1;
154 }
155 initid->maybe_null = 0; /* The result will never be NULL */
156 return 0;
157 }
158
159 ulonglong
fnv1a_64(UDF_INIT * initid,UDF_ARGS * args,char * is_null,char * error)160 fnv1a_64(UDF_INIT *initid, UDF_ARGS *args, char *is_null, char *error) {
161
162 uint null_default = HASH_NULL_DEFAULT;
163 ulonglong result = FNV1A_64_INIT;
164 uint i;
165
166 for (i = 0 ; i < args->arg_count; ++i ) {
167 if ( args->args[i] != NULL ) {
168 switch ( args->arg_type[i] ) {
169 case STRING_RESULT:
170 #ifdef NO_DECIMAL_RESULT
171 #else
172 case DECIMAL_RESULT:
173 #endif
174 result
175 = hash64a((const void*) args->args[i], args->lengths[i], result);
176 break;
177 case REAL_RESULT:
178 {
179 double real_val;
180 real_val = *((double*) args->args[i]);
181 result
182 = hash64a((const void*)&real_val, sizeof(double), result);
183 }
184 break;
185 case INT_RESULT:
186 {
187 long long int_val;
188 int_val = *((long long*) args->args[i]);
189 result = hash64a((const void*)&int_val, sizeof(ulonglong), result);
190 }
191 break;
192 default:
193 break;
194 }
195 }
196 else {
197 result
198 = hash64a((const void*)&null_default, sizeof(null_default), result);
199 }
200 }
201 return result;
202 }
203