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