Hi,
Earlier on someone on IRC mentioned that ext/hash had no support for the
FNV-1 hash function
(http://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function), so I
decided to have a go at adding it. The result of this is the attached
patch. Currently it only supports 32-bit and 64-bit versions. I've
written it against PHP 5.3 SVN, I presume it'll apply to HEAD but I
haven't checked yet. Any comments?
Cheers,
Michael
diff -x run-tests.php -x 'Make*' -x ltmain.sh -x '*.svn*' -x '*config*' -x
'*.m4' -x '*auto*' -x 'build*' -N -u -r php-src-5.3/ext/hash/hash.c hash/hash.c
--- php-src-5.3/ext/hash/hash.c 2009-09-04 14:22:19.000000000 +0100
+++ hash/hash.c 2009-09-04 11:59:53.000000000 +0100
@@ -74,7 +74,11 @@
{"RIPEMD320", "ripemd320", 25},
{NULL, NULL, 26}, /* support needs to be added for snefru 128 */
{"SNEFRU256", "snefru256", 27},
- {"MD2", "md2", 28}
+ {"MD2", "md2", 28},
+ {"FNV132", "fnv132", 29},
+ {"FNV1a32", "fnv1a32", 30},
+ {"FNV164", "fnv164", 31},
+ {"FNV1a64", "fnv1a64", 32},
};
#endif
@@ -841,6 +845,8 @@
php_hash_register_algo("crc32b", &php_hash_crc32b_ops);
php_hash_register_algo("salsa10", &php_hash_salsa10_ops);
php_hash_register_algo("salsa20", &php_hash_salsa20_ops);
+ php_hash_register_algo("fnv132", &php_hash_fnv132_ops);
+ php_hash_register_algo("fnv164", &php_hash_fnv164_ops);
PHP_HASH_HAVAL_REGISTER(3,128);
PHP_HASH_HAVAL_REGISTER(3,160);
diff -x run-tests.php -x 'Make*' -x ltmain.sh -x '*.svn*' -x '*config*' -x
'*.m4' -x '*auto*' -x 'build*' -N -u -r php-src-5.3/ext/hash/hash_fnv.c
hash/hash_fnv.c
--- php-src-5.3/ext/hash/hash_fnv.c 1970-01-01 01:00:00.000000000 +0100
+++ hash/hash_fnv.c 2009-09-04 15:14:33.000000000 +0100
@@ -0,0 +1,221 @@
+/*
+ +----------------------------------------------------------------------+
+ | PHP Version 5 |
+ +----------------------------------------------------------------------+
+ | Copyright (c) 1997-2009 The PHP Group |
+ +----------------------------------------------------------------------+
+ | This source file is subject to version 3.01 of the PHP license, |
+ | that is bundled with this package in the file LICENSE, and is |
+ | available through the world-wide-web at the following url: |
+ | http://www.php.net/license/3_01.txt |
+ | If you did not receive a copy of the PHP license and are unable to |
+ | obtain it through the world-wide-web, please send a note to |
+ | lice...@php.net so we can mail you a copy immediately. |
+ +----------------------------------------------------------------------+
+ | Authors: Michael Wallner <m...@php.net> |
+ | Sara Golemon <poll...@php.net> |
+ | Michael Maclean <m...@php.net> |
+ +----------------------------------------------------------------------+
+*/
+
+/* $Id: hash_salsa.c 272370 2008-12-31 11:15:49Z sebastian $ */
+
+#include "php_hash.h"
+#include "php_hash_fnv.h"
+
+const php_hash_ops php_hash_fnv132_ops = {
+ (php_hash_init_func_t) PHP_FNV132Init,
+ (php_hash_update_func_t) PHP_FNV132Update,
+ (php_hash_final_func_t) PHP_FNV132Final,
+ (php_hash_copy_func_t) php_hash_copy,
+ 4,
+ 4,
+ sizeof(PHP_FNV132_CTX)
+};
+
+ const php_hash_ops php_hash_fnv1a32_ops = {
+ (php_hash_init_func_t) PHP_FNV132Init,
+ (php_hash_update_func_t) PHP_FNV1a32Update,
+ (php_hash_final_func_t) PHP_FNV132Final,
+ (php_hash_copy_func_t) php_hash_copy,
+ 4,
+ 4,
+ sizeof(PHP_FNV132_CTX)
+};
+
+const php_hash_ops php_hash_fnv164_ops = {
+ (php_hash_init_func_t) PHP_FNV164Init,
+ (php_hash_update_func_t) PHP_FNV164Update,
+ (php_hash_final_func_t) PHP_FNV164Final,
+ (php_hash_copy_func_t) php_hash_copy,
+ 8,
+ 4,
+ sizeof(PHP_FNV164_CTX)
+};
+
+const php_hash_ops php_hash_fnv1a64_ops = {
+ (php_hash_init_func_t) PHP_FNV164Init,
+ (php_hash_update_func_t) PHP_FNV1a64Update,
+ (php_hash_final_func_t) PHP_FNV164Final,
+ (php_hash_copy_func_t) php_hash_copy,
+ 8,
+ 4,
+ sizeof(PHP_FNV164_CTX)
+};
+
+/* {{{ PHP_FNV132Init
+ * 32-bit FNV-1 hash initialisation
+ */
+PHP_HASH_API void PHP_FNV132Init(PHP_FNV132_CTX *context)
+{
+ context->state = PHP_FNV1_32_INIT;
+}
+/* }}} */
+
+PHP_HASH_API void PHP_FNV132Update(PHP_FNV132_CTX *context, const unsigned
char *input,
+ unsigned int inputLen)
+{
+ context->state = fnv_32_buf((void *)input, inputLen, context->state, 0);
+}
+
+PHP_HASH_API void PHP_FNV1a32Update(PHP_FNV132_CTX *context, const unsigned
char *input,
+ unsigned int inputLen)
+{
+ context->state = fnv_32_buf((void *)input, inputLen, context->state, 1);
+}
+
+PHP_HASH_API void PHP_FNV132Final(unsigned char digest[4], PHP_FNV132_CTX *
context)
+{
+#ifdef WORDS_BIGENDIAN
+ memcpy(digest, &context->state, 4);
+#else
+ int i = 0;
+ unsigned char *c = (unsigned char *) &context->state;
+
+ for(i = 0; i < 4; i++) {
+ digest[i] = c[3 - i];
+ }
+#endif
+}
+
+/* {{{ PHP_FNV164Init
+ * 64-bit FNV-1 hash initialisation
+ */
+PHP_HASH_API void PHP_FNV164Init(PHP_FNV164_CTX *context)
+{
+ context->state = PHP_FNV1_64_INIT;
+}
+/* }}} */
+
+PHP_HASH_API void PHP_FNV164Update(PHP_FNV164_CTX *context, const unsigned
char *input,
+ unsigned int inputLen)
+{
+ context->state = fnv_64_buf((void *)input, inputLen, context->state, 0);
+}
+
+PHP_HASH_API void PHP_FNV1a64Update(PHP_FNV164_CTX *context, const unsigned
char *input,
+ unsigned int inputLen)
+{
+ context->state = fnv_64_buf((void *)input, inputLen, context->state, 1);
+}
+
+PHP_HASH_API void PHP_FNV164Final(unsigned char digest[8], PHP_FNV164_CTX *
context)
+{
+#ifdef WORDS_BIGENDIAN
+ memcpy(digest, &context->state, 8);
+#else
+ int i = 0;
+ unsigned char *c = (unsigned char *) &context->state;
+
+ for(i = 0; i < 8; i++) {
+ digest[i] = c[7 - i];
+ }
+#endif
+}
+
+
+/*
+ * fnv_32_buf - perform a 32 bit Fowler/Noll/Vo hash on a buffer
+ *
+ * input:
+ * buf - start of buffer to hash
+ * len - length of buffer in octets
+ * hval - previous hash value or 0 if first call
+ * alternate - if > 0 use the alternate version
+ *
+ * returns:
+ * 32 bit hash as a static hash type
+ */
+static php_hash_uint32
+fnv_32_buf(void *buf, size_t len, php_hash_uint32 hval, int alternate)
+{
+ unsigned char *bp = (unsigned char *)buf; /* start of buffer */
+ unsigned char *be = bp + len; /* beyond end of buffer */
+
+ /*
+ * FNV-1 hash each octet in the buffer
+ */
+ while (bp < be) {
+
+ if(alternate == 0) {
+ /* multiply by the 32 bit FNV magic prime mod 2^32 */
+ hval *= PHP_FNV_32_PRIME;
+
+ /* xor the bottom with the current octet */
+ hval ^= (php_hash_uint32)*bp++;
+ } else {
+ /* xor the bottom with the current octet */
+ hval ^= (php_hash_uint32)*bp++;
+
+ /* multiply by the 32 bit FNV magic prime mod 2^32 */
+ hval *= PHP_FNV_32_PRIME;
+ }
+ }
+
+ /* return our new hash value */
+ return hval;
+}
+
+/*
+ * fnv_64_buf - perform a 64 bit Fowler/Noll/Vo hash on a buffer
+ *
+ * input:
+ * buf - start of buffer to hash
+ * len - length of buffer in octets
+ * hval - previous hash value or 0 if first call
+ * alternate - if > 0 use the alternate version
+ *
+ * returns:
+ * 64 bit hash as a static hash type
+ */
+static php_hash_uint64
+fnv_64_buf(void *buf, size_t len, php_hash_uint64 hval, int alternate)
+{
+ unsigned char *bp = (unsigned char *)buf; /* start of buffer */
+ unsigned char *be = bp + len; /* beyond end of buffer */
+
+ /*
+ * FNV-1 hash each octet of the buffer
+ */
+ while (bp < be) {
+
+ if(alternate == 0) {
+ /* multiply by the 64 bit FNV magic prime mod 2^64 */
+ hval *= PHP_FNV_64_PRIME;
+
+ /* xor the bottom with the current octet */
+ hval ^= (php_hash_uint64)*bp++;
+ } else {
+ /* xor the bottom with the current octet */
+ hval ^= (php_hash_uint64)*bp++;
+
+ /* multiply by the 64 bit FNV magic prime mod 2^64 */
+ hval *= PHP_FNV_64_PRIME;
+ }
+ }
+
+ /* return our new hash value */
+ return hval;
+}
+
+
diff -x run-tests.php -x 'Make*' -x ltmain.sh -x '*.svn*' -x '*config*' -x
'*.m4' -x '*auto*' -x 'build*' -N -u -r php-src-5.3/ext/hash/php_hash_fnv.h
hash/php_hash_fnv.h
--- php-src-5.3/ext/hash/php_hash_fnv.h 1970-01-01 01:00:00.000000000 +0100
+++ hash/php_hash_fnv.h 2009-09-04 15:08:43.000000000 +0100
@@ -0,0 +1,72 @@
+/*
+ +----------------------------------------------------------------------+
+ | PHP Version 5 |
+ +----------------------------------------------------------------------+
+ | Copyright (c) 1997-2009 The PHP Group |
+ +----------------------------------------------------------------------+
+ | This source file is subject to version 3.01 of the PHP license, |
+ | that is bundled with this package in the file LICENSE, and is |
+ | available through the world-wide-web at the following url: |
+ | http://www.php.net/license/3_01.txt |
+ | If you did not receive a copy of the PHP license and are unable to |
+ | obtain it through the world-wide-web, please send a note to |
+ | lice...@php.net so we can mail you a copy immediately. |
+ +----------------------------------------------------------------------+
+ | Authors: Michael Wallner <m...@php.net> |
+ | Sara Golemon <poll...@php.net> |
+ | Michael Maclean <m...@php.net> |
+ +----------------------------------------------------------------------+
+*/
+
+/* $Id: hash_salsa.c 272370 2008-12-31 11:15:49Z sebastian $ */
+
+#ifndef PHP_HASH_FNV_H
+#define PHP_HASH_FNV_H
+
+#define PHP_FNV1_32_INIT ((php_hash_uint32)0x811c9dc5)
+#define PHP_FNV1_32A_INIT PHP_FNV1_32_INIT
+
+#define PHP_FNV_32_PRIME ((php_hash_uint32)0x01000193)
+
+#define PHP_FNV1_64_INIT ((php_hash_uint64)0xcbf29ce484222325ULL)
+#define PHP_FNV1A_64_INIT FNV1_64_INIT
+
+#define PHP_FNV_64_PRIME ((php_hash_uint64)0x100000001b3ULL)
+
+
+/*
+ * hash types
+ */
+enum php_fnv_type {
+ PHP_FNV_NONE = 0, /* invalid FNV hash type */
+ PHP_FNV0_32 = 1, /* FNV-0 32 bit hash */
+ PHP_FNV1_32 = 2, /* FNV-1 32 bit hash */
+ PHP_FNV1a_32 = 3, /* FNV-1a 32 bit hash */
+ PHP_FNV0_64 = 4, /* FNV-0 64 bit hash */
+ PHP_FNV1_64 = 5, /* FNV-1 64 bit hash */
+ PHP_FNV1a_64 = 6, /* FNV-1a 64 bit hash */
+};
+
+typedef struct {
+ php_hash_uint32 state;
+} PHP_FNV132_CTX;
+
+typedef struct {
+ php_hash_uint64 state;
+} PHP_FNV164_CTX;
+
+
+PHP_HASH_API void PHP_FNV132Init(PHP_FNV132_CTX *context);
+PHP_HASH_API void PHP_FNV132Update(PHP_FNV132_CTX *context, const unsigned
char *input, unsigned int inputLen);
+PHP_HASH_API void PHP_FNV1a32Update(PHP_FNV132_CTX *context, const unsigned
char *input, unsigned int inputLen);
+PHP_HASH_API void PHP_FNV132Final(unsigned char digest[16], PHP_FNV132_CTX *
context);
+
+PHP_HASH_API void PHP_FNV164Init(PHP_FNV164_CTX *context);
+PHP_HASH_API void PHP_FNV164Update(PHP_FNV164_CTX *context, const unsigned
char *input, unsigned int inputLen);
+PHP_HASH_API void PHP_FNV1a64Update(PHP_FNV164_CTX *context, const unsigned
char *input, unsigned int inputLen);
+PHP_HASH_API void PHP_FNV164Final(unsigned char digest[16], PHP_FNV164_CTX *
context);
+
+static php_hash_uint32 fnv_32_buf(void *buf, size_t len, php_hash_uint32 hval,
int alternate);
+static php_hash_uint64 fnv_64_buf(void *buf, size_t len, php_hash_uint64 hval,
int alternate);
+
+#endif
diff -x run-tests.php -x 'Make*' -x ltmain.sh -x '*.svn*' -x '*config*' -x
'*.m4' -x '*auto*' -x 'build*' -N -u -r php-src-5.3/ext/hash/php_hash.h
hash/php_hash.h
--- php-src-5.3/ext/hash/php_hash.h 2009-09-04 14:22:19.000000000 +0100
+++ hash/php_hash.h 2009-09-04 11:26:55.000000000 +0100
@@ -80,6 +80,10 @@
extern const php_hash_ops php_hash_crc32b_ops;
extern const php_hash_ops php_hash_salsa10_ops;
extern const php_hash_ops php_hash_salsa20_ops;
+extern const php_hash_ops php_hash_fnv132_ops;
+extern const php_hash_ops php_hash_fnv1a32_ops;
+extern const php_hash_ops php_hash_fnv164_ops;
+extern const php_hash_ops php_hash_fnv1a64_ops;
#define PHP_HASH_HAVAL_OPS(p,b) extern const php_hash_ops
php_hash_##p##haval##b##_ops;
--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php
