From 01ecf332ff9f0c8f61e493cdca116f58d80bb5fb Mon Sep 17 00:00:00 2001 From: Nick Brassel Date: Mon, 27 Jun 2022 07:18:21 +1000 Subject: Generic wear-leveling algorithm (#16996) * Initial import of wear-leveling algorithm. * Alignment. * Docs tweaks. * Lock/unlock. * Update quantum/wear_leveling/wear_leveling_internal.h Co-authored-by: Stefan Kerkmann * More tests, fix issue with consolidation when unlocked. * More tests. * Review comments. * Add plumbing for FNV1a. * Another test checking that checksum mismatch clears the cache. * Check that the write log still gets played back. Co-authored-by: Stefan Kerkmann --- lib/fnv/Makefile | 304 +++++ lib/fnv/README | 158 +++ lib/fnv/fnv.h | 249 +++++ lib/fnv/fnv32.c | 467 ++++++++ lib/fnv/fnv64.c | 591 ++++++++++ lib/fnv/hash_32.c | 156 +++ lib/fnv/hash_32a.c | 144 +++ lib/fnv/hash_64.c | 312 ++++++ lib/fnv/hash_64a.c | 291 +++++ lib/fnv/have_ulong64.c | 58 + lib/fnv/longlong.h | 18 + lib/fnv/qmk_fnv_type_validation.c | 14 + lib/fnv/test_fnv.c | 2237 +++++++++++++++++++++++++++++++++++++ 13 files changed, 4999 insertions(+) create mode 100644 lib/fnv/Makefile create mode 100644 lib/fnv/README create mode 100644 lib/fnv/fnv.h create mode 100644 lib/fnv/fnv32.c create mode 100644 lib/fnv/fnv64.c create mode 100644 lib/fnv/hash_32.c create mode 100644 lib/fnv/hash_32a.c create mode 100644 lib/fnv/hash_64.c create mode 100644 lib/fnv/hash_64a.c create mode 100644 lib/fnv/have_ulong64.c create mode 100644 lib/fnv/longlong.h create mode 100644 lib/fnv/qmk_fnv_type_validation.c create mode 100644 lib/fnv/test_fnv.c (limited to 'lib/fnv') diff --git a/lib/fnv/Makefile b/lib/fnv/Makefile new file mode 100644 index 0000000000..c0673ded40 --- /dev/null +++ b/lib/fnv/Makefile @@ -0,0 +1,304 @@ +#!/bin/make +# +# hash - makefile for FNV hash tools +# +# @(#) $Revision: 5.2 $ +# @(#) $Id: Makefile,v 5.2 2012/03/21 01:42:15 chongo Exp $ +# @(#) $Source: /usr/local/src/cmd/fnv/RCS/Makefile,v $ +# +# See: +# http://www.isthe.com/chongo/tech/comp/fnv/index.html +# +# for the most up to date copy of this code and the FNV hash home page. +# +# Please do not copyright this code. This code is in the public domain. +# +# LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, +# INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO +# EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR +# CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF +# USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR +# OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +# PERFORMANCE OF THIS SOFTWARE. +# +# By: +# chongo /\oo/\ +# http://www.isthe.com/chongo/ +# +# Share and Enjoy! :-) + +# make tools +# +SHELL= /bin/sh +CFLAGS= -O3 -g3 +#CFLAGS= -O2 -g3 +#CC= cc +AR= ar +TAR= tar +EGREP= egrep +GZIP_BIN= gzip +INSTALL= install + +# If your system needs ranlib use: +# RANLIB= ranlib +# otherwise use: +# RANLIB= : +# +#RANLIB= ranlib +RANLIB= : + +# where to install things +# +DESTBIN= /usr/local/bin +DESTLIB= /usr/local/lib +DESTINC= /usr/local/include + +# what to build +# +SRC= hash_32.c hash_32a.c hash_64.c hash_64a.c \ + fnv32.c fnv64.c \ + have_ulong64.c test_fnv.c +NO64BIT_SRC= no64bit_fnv64.c no64bit_hash_64.c \ + no64bit_hash_64a.c no64bit_test_fnv.c +HSRC= fnv.h \ + longlong.h +ALL= ${SRC} ${HSRC} \ + README Makefile +PROGS= fnv032 fnv064 fnv132 fnv164 fnv1a32 fnv1a64 +OBSOLETE_PROGS= fnv0_32 fnv0_64 fnv1_32 fnv1_64 fnv1a_32 fnv1a_64 +NO64BIT_PROGS= no64bit_fnv064 no64bit_fnv164 no64bit_fnv1a64 +LIBS= libfnv.a +LIBOBJ= hash_32.o hash_64.o hash_32a.o hash_64a.o test_fnv.o +NO64BIT_OBJ= no64bit_fnv64.o no64bit_hash_64.o \ + no64bit_hash_64a.o no64bit_test_fnv.o +OTHEROBJ= fnv32.o fnv64.o +TARGETS= ${LIBOBJ} ${LIBS} ${PROGS} + +# default rule +# +all: ${TARGETS} + +# things to build +# +hash_32.o: hash_32.c longlong.h fnv.h + ${CC} ${CFLAGS} hash_32.c -c + +hash_64.o: hash_64.c longlong.h fnv.h + ${CC} ${CFLAGS} hash_64.c -c + +hash_32a.o: hash_32a.c longlong.h fnv.h + ${CC} ${CFLAGS} hash_32a.c -c + +hash_64a.o: hash_64a.c longlong.h fnv.h + ${CC} ${CFLAGS} hash_64a.c -c + +test_fnv.o: test_fnv.c longlong.h fnv.h + ${CC} ${CFLAGS} test_fnv.c -c + +fnv32.o: fnv32.c longlong.h fnv.h + ${CC} ${CFLAGS} fnv32.c -c + +fnv032: fnv32.o libfnv.a + ${CC} fnv32.o libfnv.a -o fnv032 + +fnv64.o: fnv64.c longlong.h fnv.h + ${CC} ${CFLAGS} fnv64.c -c + +fnv064: fnv64.o libfnv.a + ${CC} fnv64.o libfnv.a -o fnv064 + +libfnv.a: ${LIBOBJ} + rm -f $@ + ${AR} rv $@ ${LIBOBJ} + ${RANLIB} $@ + +fnv132: fnv032 + -rm -f $@ + -cp -f $? $@ + +fnv1a32: fnv032 + -rm -f $@ + -cp -f $? $@ + +fnv164: fnv064 + -rm -f $@ + -cp -f $? $@ + +fnv1a64: fnv064 + -rm -f $@ + -cp -f $? $@ + +longlong.h: have_ulong64.c Makefile + -@rm -f have_ulong64 have_ulong64.o ll_tmp longlong.h + @echo 'forming longlong.h' + @echo '/*' > longlong.h + @echo ' * DO NOT EDIT -- generated by the Makefile' >> longlong.h + @echo ' */' >> longlong.h + @echo '' >> longlong.h + @echo '#if !defined(__LONGLONG_H__)' >> longlong.h + @echo '#define __LONGLONG_H__' >> longlong.h + @echo '' >> longlong.h + @echo '/* do we have/want to use a long long type? */' >> longlong.h + -@rm -f have_ulong64.o have_ulong64 + -@${CC} ${CFLAGS} have_ulong64.c -c 2>/dev/null; true + -@${CC} ${CFLAGS} have_ulong64.o -o have_ulong64 2>/dev/null; true + -@${SHELL} -c "./have_ulong64 > ll_tmp 2>/dev/null" \ + >/dev/null 2>&1; true + -@if [ -s ll_tmp ]; then \ + cat ll_tmp >> longlong.h; \ + else \ + echo '#undef HAVE_64BIT_LONG_LONG /* no */' >> longlong.h; \ + fi + @echo '' >> longlong.h + @echo '/*' >> longlong.h + @echo ' * NO64BIT_LONG_LONG undef HAVE_64BIT_LONG_LONG' >> longlong.h + @echo ' */' >> longlong.h + @echo '#if defined(NO64BIT_LONG_LONG)' >> longlong.h + @echo '#undef HAVE_64BIT_LONG_LONG' >> longlong.h + @echo '#endif /* NO64BIT_LONG_LONG */' >> longlong.h + @echo '' >> longlong.h + @echo '#endif /* !__LONGLONG_H__ */' >> longlong.h + -@rm -f have_ulong64 have_ulong64.o ll_tmp + @echo 'longlong.h formed' + +# utilities +# +install: all + -@if [ -d "${DESTBIN}" ]; then \ + echo " mkdir -p ${DESTBIN}"; \ + mkdir -p ${DESTBIN}; \ + fi + -@if [ -d "${DESTLIB}" ]; then \ + echo " mkdir -p ${DESTLIB}"; \ + mkdir -p ${DESTLIB}; \ + fi + -@if [ -d "${DESTINC}" ]; then \ + echo " mkdir -p ${DESTINC}"; \ + mkdir -p ${DESTINC}; \ + fi + ${INSTALL} -m 0755 ${PROGS} ${DESTBIN} + ${INSTALL} -m 0644 ${LIBS} ${DESTLIB} + ${RANLIB} ${DESTLIB}/libfnv.a + ${INSTALL} -m 0644 ${HSRC} ${DESTINC} + @# remove osolete programs + for i in ${OBSOLETE_PROGS}; do \ + if [ -f "${DESTBIN}/$$i" ]; then \ + echo "rm -f ${DESTBIN}/$$i"; \ + rm -f "${DESTBIN}/$$i"; \ + fi; \ + done + +clean: + -rm -f have_ulong64 have_ulong64.o ll_tmp ll_tmp2 longlong.h + -rm -f ${LIBOBJ} + -rm -f ${OTHEROBJ} + +clobber: clean + -rm -f ${TARGETS} + -rm -f ${OBSOLETE_PROGS} lltmp lltmp2 ll_tmp + -rm -f ${NO64BIT_SRC} + -rm -f ${NO64BIT_OBJ} + -rm -f ${NO64BIT_PROGS} + -rm -f vector.c + +check: ${PROGS} + @echo -n "FNV-0 32 bit tests: " + @./fnv032 -t 1 -v + @echo -n "FNV-1 32 bit tests: " + @./fnv132 -t 1 -v + @echo -n "FNV-1a 32 bit tests: " + @./fnv1a32 -t 1 -v + @echo -n "FNV-0 64 bit tests: " + @./fnv064 -t 1 -v + @echo -n "FNV-1 64 bit tests: " + @./fnv164 -t 1 -v + @echo -n "FNV-1a 64 bit tests: " + @./fnv1a64 -t 1 -v + +############################### +# generate test vector source # +############################### + +no64bit_fnv64.c: fnv64.c + -rm -f $@ + -cp -f $? $@ + +no64bit_hash_64.c: hash_64.c + -rm -f $@ + -cp -f $? $@ + +no64bit_hash_64a.c: hash_64a.c + -rm -f $@ + -cp -f $? $@ + +no64bit_test_fnv.c: test_fnv.c + -rm -f $@ + -cp -f $? $@ + +no64bit_fnv64.o: no64bit_fnv64.c longlong.h fnv.h + ${CC} ${CFLAGS} -DNO64BIT_LONG_LONG no64bit_fnv64.c -c + +no64bit_hash_64.o: no64bit_hash_64.c longlong.h fnv.h + ${CC} ${CFLAGS} -DNO64BIT_LONG_LONG no64bit_hash_64.c -c + +no64bit_hash_64a.o: no64bit_hash_64a.c longlong.h fnv.h + ${CC} ${CFLAGS} -DNO64BIT_LONG_LONG no64bit_hash_64a.c -c + +no64bit_test_fnv.o: no64bit_test_fnv.c longlong.h fnv.h + ${CC} ${CFLAGS} -DNO64BIT_LONG_LONG no64bit_test_fnv.c -c + +no64bit_fnv064: no64bit_fnv64.o no64bit_hash_64.o \ + no64bit_hash_64a.o no64bit_test_fnv.o + ${CC} ${CFLAGS} no64bit_fnv64.o no64bit_hash_64.o \ + no64bit_hash_64a.o no64bit_test_fnv.o -o $@ + +no64bit_fnv164: no64bit_fnv064 + -rm -f $@ + -cp -f $? $@ + +no64bit_fnv1a64: no64bit_fnv064 + -rm -f $@ + -cp -f $? $@ + +vector.c: ${PROGS} ${NO64BIT_PROGS} + -rm -f $@ + echo '/* start of output generated by make $@ */' >> $@ + echo '' >> $@ + #@ + echo '/* FNV-0 32 bit test vectors */' >> $@ + ./fnv032 -t 0 >> $@ + echo '' >> $@ + #@ + echo '/* FNV-1 32 bit test vectors */' >> $@ + ./fnv132 -t 0 >> $@ + echo '' >> $@ + #@ + echo '/* FNV-1a 32 bit test vectors */' >> $@ + ./fnv1a32 -t 0 >> $@ + echo '' >> $@ + #@ + echo '/* FNV-0 64 bit test vectors */' >> $@ + echo '#if defined(HAVE_64BIT_LONG_LONG)' >> $@ + ./fnv064 -t 0 >> $@ + echo '#else /* HAVE_64BIT_LONG_LONG */' >> $@ + ./no64bit_fnv064 -t 0 >> $@ + echo '#endif /* HAVE_64BIT_LONG_LONG */' >> $@ + echo '' >> $@ + #@ + echo '/* FNV-1 64 bit test vectors */' >> $@ + echo '#if defined(HAVE_64BIT_LONG_LONG)' >> $@ + ./fnv164 -t 0 >> $@ + echo '#else /* HAVE_64BIT_LONG_LONG */' >> $@ + ./no64bit_fnv164 -t 0 >> $@ + echo '#endif /* HAVE_64BIT_LONG_LONG */' >> $@ + echo '' >> $@ + #@ + echo '/* FNV-1a 64 bit test vectors */' >> $@ + echo '#if defined(HAVE_64BIT_LONG_LONG)' >> $@ + ./fnv1a64 -t 0 >> $@ + echo '#else /* HAVE_64BIT_LONG_LONG */' >> $@ + ./no64bit_fnv1a64 -t 0 >> $@ + echo '#endif /* HAVE_64BIT_LONG_LONG */' >> $@ + echo '' >> $@ + #@ + echo '/* end of output generated by make $@ */' >> $@ diff --git a/lib/fnv/README b/lib/fnv/README new file mode 100644 index 0000000000..60aa9aaf61 --- /dev/null +++ b/lib/fnv/README @@ -0,0 +1,158 @@ +#=====================# +# Fowler/Noll/Vo hash # +#=====================# + +The basis of this hash algorithm was taken from an idea sent +as reviewer comments to the IEEE POSIX P1003.2 committee by: + + Phong Vo (http://www.research.att.com/info/kpv) + Glenn Fowler (http://www.research.att.com/~gsf/) + +In a subsequent ballot round: + + Landon Curt Noll (http://www.isthe.com/chongo) + +improved on their algorithm. Some people tried this hash +and found that it worked rather well. In an EMail message +to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash. + +FNV hashes are designed to be fast while maintaining a low +collision rate. The FNV speed allows one to quickly hash lots +of data while maintaining a reasonable collision rate. See: + + http://www.isthe.com/chongo/tech/comp/fnv/index.html + +for more details as well as other forms of the FNV hash. +Comments, questions, bug fixes and suggestions welcome at +the address given in the above URL. + + +#==================# +# FNV hash utility # +#==================# + +Two hash utilities (32 bit and 64 bit) are provided: + + fnv032 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...] + fnv132 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...] + fnv1a32 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...] + + fnv064 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...] + fnv164 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...] + fnv1a64 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...] + + -b bcnt mask off all but the lower bcnt bits (default: 32) + -m multiple hashes, one per line for each arg + -s hash arg as a string (ignoring terminating NUL bytes) + -t code 0 ==> generate test vectors, 1 ==> test FNV hash + -v verbose mode, print arg after hash (implies -m) + arg string (if -s was given) or filename (default stdin) + +The fnv032, fnv064 implement the historic FNV-0 hash. +The fnv132, fnv164 implement the recommended FNV-1 hash. +The fnv1a32, fnv1a64 implement the recommended FNV-1a hash. + +This is the original historic FNV algorithm with a 0 offset basis. +It is recommended that FNV-1, with a non-0 offset basis be used instead. + +To test FNV hashes, try: + + fnv032 -t 1 -v + fnv132 -t 1 -v + fnv1a32 -t 1 -v + + fnv064 -t 1 -v + fnv164 -t 1 -v + fnv1a64 -t 1 -v + +If you are compiling, try: + + make check + + +#==================# +# FNV hash library # +#==================# + +The libfnv.a library implements both a 32 bit and a 64 bit FNV hash +on collections of bytes, a NUL terminated strings or on an open file +descriptor. + +Here is the 32 bit FNV 1 hash: + + Fnv32_t fnv_32_buf(void *buf, int len, Fnv32_t hval); /* byte buf */ + Fnv32_t fnv_32_str(char *string, Fnv32_t hval); /* string */ + +Here is the 32 bit FNV 1a hash: + + Fnv32_t fnv_32a_buf(void *buf, int len, Fnv32_t hval); /* byte buf */ + Fnv32_t fnv_32a_str(char *string, Fnv32_t hval); /* string */ + +Here is the 64 bit FNV 1 hash: + + Fnv64_t fnv_64_buf(void *buf, int len, Fnv64_t hval); /* byte buf */ + Fnv64_t fnv_64_str(char *string, Fnv64_t hval); /* string */ + +Here is the 64 bit FNV 1a hash: + + Fnv64_t fnv_64a_buf(void *buf, int len, Fnv64_t hval); /* byte buf */ + Fnv64_t fnv_64a_str(char *string, Fnv64_t hval); /* string */ + +On the first call to a hash function, one must supply the initial basis +that is appropriate for the hash in question: + + FNV-0: (not recommended) + + FNV0_32_INIT /* 32 bit FNV-0 initial basis */ + FNV0_64_INIT /* 64 bit FNV-0 initial basis */ + + FNV-1: + + FNV1_32_INIT /* 32 bit FNV-1 initial basis */ + FNV1_64_INIT /* 64 bit FNV-1 initial basis */ + + FNV-1a: + + FNV1A_32_INIT /* 32 bit FNV-1a initial basis */ + FNV1A_64_INIT /* 64 bit FNV-1a initial basis */ + +For example to perform a 64 bit FNV-1 hash: + + #include "fnv.h" + + Fnv64_t hash_val; + + hash_val = fnv_64_str("a string", FNV1_64_INIT); + hash_val = fnv_64_str("more string", hash_val); + +produces the same final hash value as: + + hash_val = fnv_64_str("a stringmore string", FNV1_64_INIT); + +NOTE: If one used 'FNV0_64_INIT' instead of 'FNV1_64_INIT' one would get the + historic FNV-0 hash instead recommended FNV-1 hash. + +To perform a 32 bit FNV-1 hash: + + #include "fnv.h" + + Fnv32_t hash_val; + + hash_val = fnv_32_buf(buf, length_of_buf, FNV1_32_INIT); + hash_val = fnv_32_str("more data", hash_val); + +To perform a 64 bit FNV-1a hash: + + #include "fnv.h" + + Fnv64_t hash_val; + + hash_val = fnv_64a_buf(buf, length_of_buf, FNV1_64_INIT); + hash_val = fnv_64a_str("more data", hash_val); + +=-= + +chongo /\oo/\ +http://www.isthe.com/chongo + +Share and Enjoy! diff --git a/lib/fnv/fnv.h b/lib/fnv/fnv.h new file mode 100644 index 0000000000..2083a4aa23 --- /dev/null +++ b/lib/fnv/fnv.h @@ -0,0 +1,249 @@ +/* + * fnv - Fowler/Noll/Vo- hash code + * + * @(#) $Revision: 5.4 $ + * @(#) $Id: fnv.h,v 5.4 2009/07/30 22:49:13 chongo Exp $ + * @(#) $Source: /usr/local/src/cmd/fnv/RCS/fnv.h,v $ + * + *** + * + * Fowler/Noll/Vo- hash + * + * The basis of this hash algorithm was taken from an idea sent + * as reviewer comments to the IEEE POSIX P1003.2 committee by: + * + * Phong Vo (http://www.research.att.com/info/kpv/) + * Glenn Fowler (http://www.research.att.com/~gsf/) + * + * In a subsequent ballot round: + * + * Landon Curt Noll (http://www.isthe.com/chongo/) + * + * improved on their algorithm. Some people tried this hash + * and found that it worked rather well. In an EMail message + * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash. + * + * FNV hashes are designed to be fast while maintaining a low + * collision rate. The FNV speed allows one to quickly hash lots + * of data while maintaining a reasonable collision rate. See: + * + * http://www.isthe.com/chongo/tech/comp/fnv/index.html + * + * for more details as well as other forms of the FNV hash. + * + *** + * + * NOTE: The FNV-0 historic hash is not recommended. One should use + * the FNV-1 hash instead. + * + * To use the 32 bit FNV-0 historic hash, pass FNV0_32_INIT as the + * Fnv32_t hashval argument to fnv_32_buf() or fnv_32_str(). + * + * To use the 64 bit FNV-0 historic hash, pass FNV0_64_INIT as the + * Fnv64_t hashval argument to fnv_64_buf() or fnv_64_str(). + * + * To use the recommended 32 bit FNV-1 hash, pass FNV1_32_INIT as the + * Fnv32_t hashval argument to fnv_32_buf() or fnv_32_str(). + * + * To use the recommended 64 bit FNV-1 hash, pass FNV1_64_INIT as the + * Fnv64_t hashval argument to fnv_64_buf() or fnv_64_str(). + * + * To use the recommended 32 bit FNV-1a hash, pass FNV1_32A_INIT as the + * Fnv32_t hashval argument to fnv_32a_buf() or fnv_32a_str(). + * + * To use the recommended 64 bit FNV-1a hash, pass FNV1A_64_INIT as the + * Fnv64_t hashval argument to fnv_64a_buf() or fnv_64a_str(). + * + *** + * + * Please do not copyright this code. This code is in the public domain. + * + * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO + * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR + * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF + * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR + * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR + * PERFORMANCE OF THIS SOFTWARE. + * + * By: + * chongo /\oo/\ + * http://www.isthe.com/chongo/ + * + * Share and Enjoy! :-) + */ + +#if !defined(__FNV_H__) +#define __FNV_H__ + +#include + +#define FNV_VERSION "5.0.2" /* @(#) FNV Version */ + + +/* + * 32 bit FNV-0 hash type + */ +typedef u_int32_t Fnv32_t; + + +/* + * 32 bit FNV-0 zero initial basis + * + * This historic hash is not recommended. One should use + * the FNV-1 hash and initial basis instead. + */ +#define FNV0_32_INIT ((Fnv32_t)0) + + +/* + * 32 bit FNV-1 and FNV-1a non-zero initial basis + * + * The FNV-1 initial basis is the FNV-0 hash of the following 32 octets: + * + * chongo /\../\ + * + * NOTE: The \'s above are not back-slashing escape characters. + * They are literal ASCII backslash 0x5c characters. + * + * NOTE: The FNV-1a initial basis is the same value as FNV-1 by definition. + */ +#define FNV1_32_INIT ((Fnv32_t)0x811c9dc5) +#define FNV1_32A_INIT FNV1_32_INIT + + +/* + * determine how 64 bit unsigned values are represented + */ +#include "longlong.h" + + +/* + * 64 bit FNV-0 hash + */ +#if defined(HAVE_64BIT_LONG_LONG) +typedef u_int64_t Fnv64_t; +#else /* HAVE_64BIT_LONG_LONG */ +typedef struct { + u_int32_t w32[2]; /* w32[0] is low order, w32[1] is high order word */ +} Fnv64_t; +#endif /* HAVE_64BIT_LONG_LONG */ + + +/* + * 64 bit FNV-0 zero initial basis + * + * This historic hash is not recommended. One should use + * the FNV-1 hash and initial basis instead. + */ +#if defined(HAVE_64BIT_LONG_LONG) +#define FNV0_64_INIT ((Fnv64_t)0) +#else /* HAVE_64BIT_LONG_LONG */ +extern const Fnv64_t fnv0_64_init; +#define FNV0_64_INIT (fnv0_64_init) +#endif /* HAVE_64BIT_LONG_LONG */ + + +/* + * 64 bit FNV-1 non-zero initial basis + * + * The FNV-1 initial basis is the FNV-0 hash of the following 32 octets: + * + * chongo /\../\ + * + * NOTE: The \'s above are not back-slashing escape characters. + * They are literal ASCII backslash 0x5c characters. + * + * NOTE: The FNV-1a initial basis is the same value as FNV-1 by definition. + */ +#if defined(HAVE_64BIT_LONG_LONG) +#define FNV1_64_INIT ((Fnv64_t)0xcbf29ce484222325ULL) +#define FNV1A_64_INIT FNV1_64_INIT +#else /* HAVE_64BIT_LONG_LONG */ +extern const fnv1_64_init; +extern const Fnv64_t fnv1a_64_init; +#define FNV1_64_INIT (fnv1_64_init) +#define FNV1A_64_INIT (fnv1a_64_init) +#endif /* HAVE_64BIT_LONG_LONG */ + + +/* + * hash types + */ +enum fnv_type { + FNV_NONE = 0, /* invalid FNV hash type */ + FNV0_32 = 1, /* FNV-0 32 bit hash */ + FNV1_32 = 2, /* FNV-1 32 bit hash */ + FNV1a_32 = 3, /* FNV-1a 32 bit hash */ + FNV0_64 = 4, /* FNV-0 64 bit hash */ + FNV1_64 = 5, /* FNV-1 64 bit hash */ + FNV1a_64 = 6, /* FNV-1a 64 bit hash */ +}; + + +/* + * these test vectors are used as part o the FNV test suite + */ +struct test_vector { + void *buf; /* start of test vector buffer */ + int len; /* length of test vector */ +}; +struct fnv0_32_test_vector { + struct test_vector *test; /* test vector buffer to hash */ + Fnv32_t fnv0_32; /* expected FNV-0 32 bit hash value */ +}; +struct fnv1_32_test_vector { + struct test_vector *test; /* test vector buffer to hash */ + Fnv32_t fnv1_32; /* expected FNV-1 32 bit hash value */ +}; +struct fnv1a_32_test_vector { + struct test_vector *test; /* test vector buffer to hash */ + Fnv32_t fnv1a_32; /* expected FNV-1a 32 bit hash value */ +}; +struct fnv0_64_test_vector { + struct test_vector *test; /* test vector buffer to hash */ + Fnv64_t fnv0_64; /* expected FNV-0 64 bit hash value */ +}; +struct fnv1_64_test_vector { + struct test_vector *test; /* test vector buffer to hash */ + Fnv64_t fnv1_64; /* expected FNV-1 64 bit hash value */ +}; +struct fnv1a_64_test_vector { + struct test_vector *test; /* test vector buffer to hash */ + Fnv64_t fnv1a_64; /* expected FNV-1a 64 bit hash value */ +}; + + +/* + * external functions + */ +/* hash_32.c */ +extern Fnv32_t fnv_32_buf(void *buf, size_t len, Fnv32_t hashval); +extern Fnv32_t fnv_32_str(char *buf, Fnv32_t hashval); + +/* hash_32a.c */ +extern Fnv32_t fnv_32a_buf(void *buf, size_t len, Fnv32_t hashval); +extern Fnv32_t fnv_32a_str(char *buf, Fnv32_t hashval); + +/* hash_64.c */ +extern Fnv64_t fnv_64_buf(void *buf, size_t len, Fnv64_t hashval); +extern Fnv64_t fnv_64_str(char *buf, Fnv64_t hashval); + +/* hash_64a.c */ +extern Fnv64_t fnv_64a_buf(void *buf, size_t len, Fnv64_t hashval); +extern Fnv64_t fnv_64a_str(char *buf, Fnv64_t hashval); + +/* test_fnv.c */ +extern struct test_vector fnv_test_str[]; +extern struct fnv0_32_test_vector fnv0_32_vector[]; +extern struct fnv1_32_test_vector fnv1_32_vector[]; +extern struct fnv1a_32_test_vector fnv1a_32_vector[]; +extern struct fnv0_64_test_vector fnv0_64_vector[]; +extern struct fnv1_64_test_vector fnv1_64_vector[]; +extern struct fnv1a_64_test_vector fnv1a_64_vector[]; +extern void unknown_hash_type(char *prog, enum fnv_type type, int code); +extern void print_fnv32(Fnv32_t hval, Fnv32_t mask, int verbose, char *arg); +extern void print_fnv64(Fnv64_t hval, Fnv64_t mask, int verbose, char *arg); + + +#endif /* __FNV_H__ */ diff --git a/lib/fnv/fnv32.c b/lib/fnv/fnv32.c new file mode 100644 index 0000000000..58c61f03fc --- /dev/null +++ b/lib/fnv/fnv32.c @@ -0,0 +1,467 @@ +/* + * fnv32 - 32 bit Fowler/Noll/Vo hash of a buffer or string + * + * @(#) $Revision: 5.5 $ + * @(#) $Id: fnv32.c,v 5.5 2012/03/21 01:38:12 chongo Exp $ + * @(#) $Source: /usr/local/src/cmd/fnv/RCS/fnv32.c,v $ + * + *** + * + * Fowler/Noll/Vo hash + * + * The basis of this hash algorithm was taken from an idea sent + * as reviewer comments to the IEEE POSIX P1003.2 committee by: + * + * Phong Vo (http://www.research.att.com/info/kpv/) + * Glenn Fowler (http://www.research.att.com/~gsf/) + * + * In a subsequent ballot round: + * + * Landon Curt Noll (http://www.isthe.com/chongo/) + * + * improved on their algorithm. Some people tried this hash + * and found that it worked rather well. In an EMail message + * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash. + * + * FNV hashes are designed to be fast while maintaining a low + * collision rate. The FNV speed allows one to quickly hash lots + * of data while maintaining a reasonable collision rate. See: + * + * http://www.isthe.com/chongo/tech/comp/fnv/index.html + * + * for more details as well as other forms of the FNV hash. + * + *** + * + * Please do not copyright this code. This code is in the public domain. + * + * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO + * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR + * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF + * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR + * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR + * PERFORMANCE OF THIS SOFTWARE. + * + * By: + * chongo /\oo/\ + * http://www.isthe.com/chongo/ + * + * Share and Enjoy! :-) + */ + +#include +#include +#include +#include +#include +#include +#include +#include "longlong.h" +#include "fnv.h" + +#define WIDTH 32 /* bit width of hash */ + +#define BUF_SIZE (32*1024) /* number of bytes to hash at a time */ + +static char *usage = +"usage: %s [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]\n" +"\n" +"\t-b bcnt\tmask off all but the lower bcnt bits (default 32)\n" +"\t-m\tmultiple hashes, one per line for each arg\n" +"\t-s\thash arg as a string (ignoring terminating NUL bytes)\n" +"\t-t code\t test hash code: (0 ==> generate test vectors\n" +"\t\t\t\t 1 ==> validate against FNV test vectors)\n" +"\t-v\tverbose mode, print arg after hash (implies -m)\n" +"\targ\tstring (if -s was given) or filename (default stdin)\n" +"\n" +"\tNOTE: Programs that begin with fnv0 implement the FNV-0 hash.\n" +"\t The FNV-0 hash is historic FNV algorithm that is now deprecated.\n" +"\n" +"\tSee http://www.isthe.com/chongo/tech/comp/fnv/index.html for more info.\n" +"\n" +"\t@(#) FNV Version: %s\n"; +static char *program; /* our name */ + + +/* + * test_fnv32 - test the FNV32 hash + * + * given: + * hash_type type of FNV hash to test + * init_hval initial hash value + * mask lower bit mask + * v_flag 1 => print test failure info on stderr + * code 0 ==> generate FNV test vectors + * 1 ==> validate against FNV test vectors + * + * returns: 0 ==> OK, else test vector failure number + */ +static int +test_fnv32(enum fnv_type hash_type, Fnv32_t init_hval, + Fnv32_t mask, int v_flag, int code) +{ + struct test_vector *t; /* FNV test vestor */ + Fnv32_t hval; /* current hash value */ + int tstnum; /* test vector that failed, starting at 1 */ + + /* + * print preamble if generating test vectors + */ + if (code == 0) { + switch (hash_type) { + case FNV0_32: + printf("struct fnv0_32_test_vector fnv0_32_vector[] = {\n"); + break; + case FNV1_32: + printf("struct fnv1_32_test_vector fnv1_32_vector[] = {\n"); + break; + case FNV1a_32: + printf("struct fnv1a_32_test_vector fnv1a_32_vector[] = {\n"); + break; + default: + unknown_hash_type(program, hash_type, 12); /* exit(12) */ + /*NOTREACHED*/ + } + } + + /* + * loop thru all test vectors + */ + for (t = fnv_test_str, tstnum = 1; t->buf != NULL; ++t, ++tstnum) { + + /* + * compute the FNV hash + */ + hval = init_hval; + switch (hash_type) { + case FNV0_32: + case FNV1_32: + hval = fnv_32_buf(t->buf, t->len, hval); + break; + case FNV1a_32: + hval = fnv_32a_buf(t->buf, t->len, hval); + break; + default: + unknown_hash_type(program, hash_type, 13); /* exit(13) */ + /*NOTREACHED*/ + } + + /* + * print the vector + */ + switch (code) { + case 0: /* generate the test vector */ + printf(" { &fnv_test_str[%d], (Fnv32_t) 0x%08lxUL },\n", + tstnum-1, hval & mask); + break; + case 1: /* validate against test vector */ + switch (hash_type) { + case FNV0_32: + if ((hval&mask) != (fnv0_32_vector[tstnum-1].fnv0_32 & mask)) { + if (v_flag) { + fprintf(stderr, "%s: failed fnv0_32 test # %d\n", + program, tstnum); + fprintf(stderr, "%s: test # 1 is 1st test\n", program); + fprintf(stderr, + "%s: expected 0x%08lx != generated: 0x%08lx\n", + program, (hval&mask), + (fnv0_32_vector[tstnum-1].fnv0_32 & mask)); + } + return tstnum; + } + break; + case FNV1_32: + if ((hval&mask) != (fnv1_32_vector[tstnum-1].fnv1_32 & mask)) { + if (v_flag) { + fprintf(stderr, "%s: failed fnv1_32 test # %d\n", + program, tstnum); + fprintf(stderr, "%s: test # 1 is 1st test\n", program); + fprintf(stderr, + "%s: expected 0x%08lx != generated: 0x%08lx\n", + program, (hval&mask), + (fnv1_32_vector[tstnum-1].fnv1_32 & mask)); + } + return tstnum; + } + break; + case FNV1a_32: + if ((hval&mask) != (fnv1a_32_vector[tstnum-1].fnv1a_32 &mask)) { + if (v_flag) { + fprintf(stderr, "%s: failed fnv1a_32 test # %d\n", + program, tstnum); + fprintf(stderr, "%s: test # 1 is 1st test\n", program); + fprintf(stderr, + "%s: expected 0x%08lx != generated: 0x%08lx\n", + program, (hval&mask), + (fnv1a_32_vector[tstnum-1].fnv1a_32 & mask)); + } + return tstnum; + } + break; + } + break; + default: + fprintf(stderr, "%s: -m %d not implemented yet\n", program, code); + exit(14); + } + } + + /* + * print completion if generating test vectors + */ + if (code == 0) { + printf(" { NULL, 0 }\n"); + printf("};\n"); + } + + /* + * no failures, return code 0 ==> all OK + */ + return 0; +} + + +/* + * main - the main function + * + * See the above usage for details. + */ +int +main(int argc, char *argv[]) +{ + char buf[BUF_SIZE+1]; /* read buffer */ + int readcnt; /* number of characters written */ + Fnv32_t hval; /* current hash value */ + int s_flag = 0; /* 1 => -s was given, hash args as strings */ + int m_flag = 0; /* 1 => print multiple hashes, one per arg */ + int v_flag = 0; /* 1 => verbose hash print */ + int b_flag = WIDTH; /* -b flag value */ + int t_flag = -1; /* FNV test vector code (0=>print, 1=>test) */ + enum fnv_type hash_type = FNV_NONE; /* type of FNV hash to perform */ + Fnv32_t bmask; /* mask to apply to output */ + extern char *optarg; /* option argument */ + extern int optind; /* argv index of the next arg */ + int fd; /* open file to process */ + char *p; + int i; + + /* + * parse args + */ + program = argv[0]; + while ((i = getopt(argc, argv, "b:mst:v")) != -1) { + switch (i) { + case 'b': /* bcnt bit mask count */ + b_flag = atoi(optarg); + break; + case 'm': /* print multiple hashes, one per arg */ + m_flag = 1; + break; + case 's': /* hash args as strings */ + s_flag = 1; + break; + case 't': /* FNV test vector code */ + t_flag = atoi(optarg); + if (t_flag < 0 || t_flag > 1) { + fprintf(stderr, "%s: -t code must be 0 or 1\n", program); + fprintf(stderr, usage, program, FNV_VERSION); + exit(1); + } + m_flag = 1; + break; + case 'v': /* verbose hash print */ + m_flag = 1; + v_flag = 1; + break; + default: + fprintf(stderr, usage, program, FNV_VERSION); + exit(1); + } + } + /* -t code incompatible with -b, -m and args */ + if (t_flag >= 0) { + if (b_flag != WIDTH) { + fprintf(stderr, "%s: -t code incompatible with -b\n", program); + exit(2); + } + if (s_flag != 0) { + fprintf(stderr, "%s: -t code incompatible with -s\n", program); + exit(3); + } + if (optind < argc) { + fprintf(stderr, "%s: -t code incompatible args\n", program); + exit(4); + } + } + /* -s requires at least 1 arg */ + if (s_flag && optind >= argc) { + fprintf(stderr, usage, program, FNV_VERSION); + exit(5); + } + /* limit -b values */ + if (b_flag < 0 || b_flag > WIDTH) { + fprintf(stderr, "%s: -b bcnt: %d must be >= 0 and < %d\n", + program, b_flag, WIDTH); + exit(6); + } + if (b_flag == WIDTH) { + bmask = (Fnv32_t)0xffffffff; + } else { + bmask = (Fnv32_t)((1 << b_flag) - 1); + } + + /* + * start with the initial basis depending on the hash type + */ + p = strrchr(program, '/'); + if (p == NULL) { + p = program; + } else { + ++p; + } + if (strcmp(p, "fnv032") == 0) { + /* using non-recommended FNV-0 and zero initial basis */ + hval = FNV0_32_INIT; + hash_type = FNV0_32; + } else if (strcmp(p, "fnv132") == 0) { + /* using FNV-1 and non-zero initial basis */ + hval = FNV1_32_INIT; + hash_type = FNV1_32; + } else if (strcmp(p, "fnv1a32") == 0) { + /* start with the FNV-1a initial basis */ + hval = FNV1_32A_INIT; + hash_type = FNV1a_32; + } else { + fprintf(stderr, "%s: unknown program name, unknown hash type\n", + program); + exit(7); + } + + /* + * FNV test vector processing, if needed + */ + if (t_flag >= 0) { + int code; /* test vector that failed, starting at 1 */ + + /* + * perform all tests + */ + code = test_fnv32(hash_type, hval, bmask, v_flag, t_flag); + + /* + * evaluate the tests + */ + if (code == 0) { + if (v_flag) { + printf("passed\n"); + } + exit(0); + } else { + printf("failed vector (1 is 1st test): %d\n", code); + exit(8); + } + } + + /* + * string hashing + */ + if (s_flag) { + + /* hash any other strings */ + for (i=optind; i < argc; ++i) { + switch (hash_type) { + case FNV0_32: + case FNV1_32: + hval = fnv_32_str(argv[i], hval); + break; + case FNV1a_32: + hval = fnv_32a_str(argv[i], hval); + break; + default: + unknown_hash_type(program, hash_type, 9); /* exit(9) */ + /*NOTREACHED*/ + } + if (m_flag) { + print_fnv32(hval, bmask, v_flag, argv[i]); + } + } + + + /* + * file hashing + */ + } else { + + /* + * case: process only stdin + */ + if (optind >= argc) { + + /* case: process only stdin */ + while ((readcnt = read(0, buf, BUF_SIZE)) > 0) { + switch (hash_type) { + case FNV0_32: + case FNV1_32: + hval = fnv_32_buf(buf, readcnt, hval); + break; + case FNV1a_32: + hval = fnv_32a_buf(buf, readcnt, hval); + break; + default: + unknown_hash_type(program, hash_type, 10); /* exit(10) */ + /*NOTREACHED*/ + } + } + if (m_flag) { + print_fnv32(hval, bmask, v_flag, "(stdin)"); + } + + } else { + + /* + * process any other files + */ + for (i=optind; i < argc; ++i) { + + /* open the file */ + fd = open(argv[i], O_RDONLY); + if (fd < 0) { + fprintf(stderr, "%s: unable to open file: %s\n", + program, argv[i]); + exit(4); + } + + /* hash the file */ + while ((readcnt = read(fd, buf, BUF_SIZE)) > 0) { + switch (hash_type) { + case FNV0_32: + case FNV1_32: + hval = fnv_32_buf(buf, readcnt, hval); + break; + case FNV1a_32: + hval = fnv_32a_buf(buf, readcnt, hval); + break; + default: + unknown_hash_type(program, hash_type, 11);/* exit(11) */ + /*NOTREACHED*/ + } + } + + /* finish processing the file */ + if (m_flag) { + print_fnv32(hval, bmask, v_flag, argv[i]); + } + close(fd); + } + } + } + + /* + * report hash and exit + */ + if (!m_flag) { + print_fnv32(hval, bmask, v_flag, ""); + } + return 0; /* exit(0); */ +} diff --git a/lib/fnv/fnv64.c b/lib/fnv/fnv64.c new file mode 100644 index 0000000000..0662d4d657 --- /dev/null +++ b/lib/fnv/fnv64.c @@ -0,0 +1,591 @@ +/* + * fnv_64 - 64 bit Fowler/Noll/Vo hash of a buffer or string + * + * @(#) $Revision: 5.5 $ + * @(#) $Id: fnv64.c,v 5.5 2012/03/21 01:38:12 chongo Exp $ + * @(#) $Source: /usr/local/src/cmd/fnv/RCS/fnv64.c,v $ + * + *** + * + * Fowler/Noll/Vo hash + * + * The basis of this hash algorithm was taken from an idea sent + * as reviewer comments to the IEEE POSIX P1003.2 committee by: + * + * Phong Vo (http://www.research.att.com/info/kpv/) + * Glenn Fowler (http://www.research.att.com/~gsf/) + * + * In a subsequent ballot round: + * + * Landon Curt Noll (http://www.isthe.com/chongo/) + * + * improved on their algorithm. Some people tried this hash + * and found that it worked rather well. In an EMail message + * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash. + * + * FNV hashes are designed to be fast while maintaining a low + * collision rate. The FNV speed allows one to quickly hash lots + * of data while maintaining a reasonable collision rate. See: + * + * http://www.isthe.com/chongo/tech/comp/fnv/index.html + * + * for more details as well as other forms of the FNV hash. + * + *** + * + * Please do not copyright this code. This code is in the public domain. + * + * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO + * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR + * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF + * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR + * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR + * PERFORMANCE OF THIS SOFTWARE. + * + * By: + * chongo /\oo/\ + * http://www.isthe.com/chongo/ + * + * Share and Enjoy! :-) + */ + +#include +#include +#include +#include +#include +#include +#include +#include "longlong.h" +#include "fnv.h" + +#define WIDTH 64 /* bit width of hash */ + +#define BUF_SIZE (32*1024) /* number of bytes to hash at a time */ + +static char *usage = +"usage: %s [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]\n" +"\n" +"\t-b bcnt\tmask off all but the lower bcnt bits (default 64)\n" +"\t-m\tmultiple hashes, one per line for each arg\n" +"\t-s\thash arg as a string (ignoring terminating NUL bytes)\n" +"\t-t code\t test hash code: (0 ==> generate test vectors\n" +"\t\t\t\t 1 ==> validate against FNV test vectors)\n" +"\t-v\tverbose mode, print arg after hash (implies -m)\n" +"\targ\tstring (if -s was given) or filename (default stdin)\n" +"\n" +"\tNOTE: Programs that begin with fnv0 implement the FNV-0 hash.\n" +"\t The FNV-0 hash is historic FNV algorithm that is now deprecated.\n" +"\n" +"\tSee http://www.isthe.com/chongo/tech/comp/fnv/index.html for more info.\n" +"\n" +"\t@(#) FNV Version: %s\n"; +static char *program; /* our name */ + + +/* + * test_fnv64 - test the FNV64 hash + * + * given: + * hash_type type of FNV hash to test + * init_hval initial hash value + * mask lower bit mask + * v_flag 1 => print test failure info on stderr + * code 0 ==> generate FNV test vectors + * 1 ==> validate against FNV test vectors + * + * returns: 0 ==> OK, else test vector failure number + */ +static int +test_fnv64(enum fnv_type hash_type, Fnv64_t init_hval, + Fnv64_t mask, int v_flag, int code) +{ + struct test_vector *t; /* FNV test vestor */ + Fnv64_t hval; /* current hash value */ + int tstnum; /* test vector that failed, starting at 1 */ + + /* + * print preamble if generating test vectors + */ + if (code == 0) { + switch (hash_type) { + case FNV0_64: + printf("struct fnv0_64_test_vector fnv0_64_vector[] = {\n"); + break; + case FNV1_64: + printf("struct fnv1_64_test_vector fnv1_64_vector[] = {\n"); + break; + case FNV1a_64: + printf("struct fnv1a_64_test_vector fnv1a_64_vector[] = {\n"); + break; + default: + unknown_hash_type(program, hash_type, 12); /* exit(12) */ + /*NOTREACHED*/ + } + } + + /* + * loop thru all test vectors + */ + for (t = fnv_test_str, tstnum = 1; t->buf != NULL; ++t, ++tstnum) { + + /* + * compute the FNV hash + */ + hval = init_hval; + switch (hash_type) { + case FNV0_64: + case FNV1_64: + hval = fnv_64_buf(t->buf, t->len, hval); + break; + case FNV1a_64: + hval = fnv_64a_buf(t->buf, t->len, hval); + break; + default: + unknown_hash_type(program, hash_type, 13); /* exit(13) */ + /*NOTREACHED*/ + } + + /* + * print the vector + */ +#if defined(HAVE_64BIT_LONG_LONG) + /* + * HAVE_64BIT_LONG_LONG testing + */ + switch (code) { + case 0: /* generate the test vector */ + printf(" { &fnv_test_str[%d], (Fnv64_t) 0x%016llxULL },\n", + tstnum-1, hval & mask); + break; + + case 1: /* validate against test vector */ + switch (hash_type) { + case FNV0_64: + if ((hval&mask) != (fnv0_64_vector[tstnum-1].fnv0_64 & mask)) { + if (v_flag) { + fprintf(stderr, "%s: failed fnv0_64 test # %d\n", + program, tstnum); + fprintf(stderr, "%s: test # 1 is 1st test\n", program); + fprintf(stderr, + "%s: expected 0x%016llx != generated: 0x%016llx\n", + program, + (hval&mask), + (fnv0_64_vector[tstnum-1].fnv0_64 & mask)); + } + return tstnum; + } + break; + case FNV1_64: + if ((hval&mask) != (fnv1_64_vector[tstnum-1].fnv1_64 & mask)) { + if (v_flag) { + fprintf(stderr, "%s: failed fnv1_64 test # %d\n", + program, tstnum); + fprintf(stderr, "%s: test # 1 is 1st test\n", program); + fprintf(stderr, + "%s: expected 0x%016llx != generated: 0x%016llx\n", + program, + (hval&mask), + (fnv1_64_vector[tstnum-1].fnv1_64 & mask)); + } + return tstnum; + } + break; + case FNV1a_64: + if ((hval&mask) != (fnv1a_64_vector[tstnum-1].fnv1a_64 &mask)) { + if (v_flag) { + fprintf(stderr, "%s: failed fnv1a_64 test # %d\n", + program, tstnum); + fprintf(stderr, "%s: test # 1 is 1st test\n", program); + fprintf(stderr, + "%s: expected 0x%016llx != generated: 0x%016llx\n", + program, + (hval&mask), + (fnv1a_64_vector[tstnum-1].fnv1a_64 & mask)); + } + return tstnum; + } + break; + } + break; + + default: + fprintf(stderr, "%s: -m %d not implemented yet\n", program, code); + exit(14); + } +#else /* HAVE_64BIT_LONG_LONG */ + /* + * non HAVE_64BIT_LONG_LONG testing + */ + switch (code) { + case 0: /* generate the test vector */ + printf(" { &fnv_test_str[%d], " + "(Fnv64_t) {0x%08lxUL, 0x%08lxUL} },\n", + tstnum-1, + (hval.w32[0] & mask.w32[0]), + (hval.w32[1] & mask.w32[1])); + break; + + case 1: /* validate against test vector */ + switch (hash_type) { + case FNV0_64: + if (((hval.w32[0] & mask.w32[0]) != + (fnv0_64_vector[tstnum-1].fnv0_64.w32[0] & + mask.w32[0])) && + ((hval.w32[1] & mask.w32[1]) != + (fnv0_64_vector[tstnum-1].fnv0_64.w32[1] & + mask.w32[1]))) { + if (v_flag) { + fprintf(stderr, "%s: failed fnv0_64 test # %d\n", + program, tstnum); + fprintf(stderr, "%s: test # 1 is 1st test\n", program); + fprintf(stderr, + "%s: expected 0x%08llx%08llx != " + "generated: 0x%08llx%08llx\n", + program, + (hval.w32[0] & mask.w32[0]), + (hval.w32[1] & mask.w32[1]), + ((fnv0_64_vector[tstnum-1].fnv0_64.w32[0] & + mask.w32[0])), + ((fnv0_64_vector[tstnum-1].fnv0_64.w32[1] & + mask.w32[1]))); + } + return tstnum; + } + break; + case FNV1_64: + if (((hval.w32[0] & mask.w32[0]) != + (fnv1_64_vector[tstnum-1].fnv1_64.w32[0] & + mask.w32[0])) && + ((hval.w32[1] & mask.w32[1]) != + (fnv1_64_vector[tstnum-1].fnv1_64.w32[1] & + mask.w32[1]))) { + if (v_flag) { + fprintf(stderr, "%s: failed fnv1_64 test # %d\n", + program, tstnum); + fprintf(stderr, "%s: test # 1 is 1st test\n", program); + fprintf(stderr, + "%s: expected 0x%08llx%08llx != " + "generated: 0x%08llx%08llx\n", + program, + (hval.w32[0] & mask.w32[0]), + (hval.w32[1] & mask.w32[1]), + ((fnv1_64_vector[tstnum-1].fnv1_64.w32[0] & + mask.w32[0])), + ((fnv1_64_vector[tstnum-1].fnv1_64.w32[1] & + mask.w32[1]))); + } + return tstnum; + } + break; + case FNV1a_64: + if (((hval.w32[0] & mask.w32[0]) != + (fnv1a_64_vector[tstnum-1].fnv1a_64.w32[0] & + mask.w32[0])) && + ((hval.w32[1] & mask.w32[1]) != + (fnv1a_64_vector[tstnum-1].fnv1a_64.w32[1] & + mask.w32[1]))) { + if (v_flag) { + fprintf(stderr, "%s: failed fnv1a_64 test # %d\n", + program, tstnum); + fprintf(stderr, "%s: test # 1 is 1st test\n", program); + fprintf(stderr, + "%s: expected 0x%08llx%08llx != " + "generated: 0x%08llx%08llx\n", + program, + (hval.w32[0] & mask.w32[0]), + (hval.w32[1] & mask.w32[1]), + ((fnv1a_64_vector[tstnum-1].fnv1a_64.w32[0] & + mask.w32[0])), + ((fnv1a_64_vector[tstnum-1].fnv1a_64.w32[1] & + mask.w32[1]))); + } + return tstnum; + } + break; + } + break; + + default: + fprintf(stderr, "%s: -m %d not implemented yet\n", program, code); + exit(15); + } +#endif /* HAVE_64BIT_LONG_LONG */ + } + + /* + * print completion if generating test vectors + */ + if (code == 0) { +#if defined(HAVE_64BIT_LONG_LONG) + printf(" { NULL, (Fnv64_t) 0 }\n"); +#else /* HAVE_64BIT_LONG_LONG */ + printf(" { NULL, (Fnv64_t) {0,0} }\n"); +#endif /* HAVE_64BIT_LONG_LONG */ + printf("};\n"); + } + + /* + * no failures, return code 0 ==> all OK + */ + return 0; +} + + +/* + * main - the main function + * + * See the above usage for details. + */ +int +main(int argc, char *argv[]) +{ + char buf[BUF_SIZE+1]; /* read buffer */ + int readcnt; /* number of characters written */ + Fnv64_t hval; /* current hash value */ + int s_flag = 0; /* 1 => -s was given, hash args as strings */ + int m_flag = 0; /* 1 => print multiple hashes, one per arg */ + int v_flag = 0; /* 1 => verbose hash print */ + int b_flag = WIDTH; /* -b flag value */ + int t_flag = -1; /* FNV test vector code (0=>print, 1=>test) */ + enum fnv_type hash_type = FNV_NONE; /* type of FNV hash to perform */ + Fnv64_t bmask; /* mask to apply to output */ + extern char *optarg; /* option argument */ + extern int optind; /* argv index of the next arg */ + int fd; /* open file to process */ + char *p; + int i; + + /* + * parse args + */ + program = argv[0]; + while ((i = getopt(argc, argv, "b:mst:v")) != -1) { + switch (i) { + case 'b': /* bcnt bit mask count */ + b_flag = atoi(optarg); + break; + case 'm': /* print multiple hashes, one per arg */ + m_flag = 1; + break; + case 's': /* hash args as strings */ + s_flag = 1; + break; + case 't': /* FNV test vector code */ + t_flag = atoi(optarg); + if (t_flag < 0 || t_flag > 1) { + fprintf(stderr, "%s: -t code must be 0 or 1\n", program); + fprintf(stderr, usage, program, FNV_VERSION); + exit(1); + } + m_flag = 1; + break; + case 'v': /* verbose hash print */ + m_flag = 1; + v_flag = 1; + break; + default: + fprintf(stderr, usage, program, FNV_VERSION); + exit(1); + } + } + /* -t code incompatible with -b, -m and args */ + if (t_flag >= 0) { + if (b_flag != WIDTH) { + fprintf(stderr, "%s: -t code incompatible with -b\n", program); + exit(2); + } + if (s_flag != 0) { + fprintf(stderr, "%s: -t code incompatible with -s\n", program); + exit(3); + } + if (optind < argc) { + fprintf(stderr, "%s: -t code incompatible args\n", program); + exit(4); + } + } + /* -s requires at least 1 arg */ + if (s_flag && optind >= argc) { + fprintf(stderr, usage, program, FNV_VERSION); + exit(5); + } + /* limit -b values */ + if (b_flag < 0 || b_flag > WIDTH) { + fprintf(stderr, "%s: -b bcnt: %d must be >= 0 and < %d\n", + program, b_flag, WIDTH); + exit(6); + } +#if defined(HAVE_64BIT_LONG_LONG) + if (b_flag == WIDTH) { + bmask = (Fnv64_t)0xffffffffffffffffULL; + } else { + bmask = (Fnv64_t)((1ULL << b_flag) - 1ULL); + } +#else /* HAVE_64BIT_LONG_LONG */ + if (b_flag == WIDTH) { + bmask.w32[0] = 0xffffffffUL; + bmask.w32[1] = 0xffffffffUL; + } else if (b_flag >= WIDTH/2) { + bmask.w32[0] = 0xffffffffUL; + bmask.w32[1] = ((1UL << (b_flag-(WIDTH/2))) - 1UL); + } else { + bmask.w32[0] = ((1UL << b_flag) - 1UL); + bmask.w32[1] = 0UL; + } +#endif /* HAVE_64BIT_LONG_LONG */ + + /* + * start with the initial basis depending on the hash type + */ + p = strrchr(program, '/'); + if (p == NULL) { + p = program; + } else { + ++p; + } + if (strcmp(p, "fnv064") == 0 || strcmp(p, "no64bit_fnv064") == 0) { + /* using non-recommended FNV-0 and zero initial basis */ + hval = FNV0_64_INIT; + hash_type = FNV0_64; + } else if (strcmp(p, "fnv164") == 0 || strcmp(p, "no64bit_fnv164") == 0) { + /* using FNV-1 and non-zero initial basis */ + hval = FNV1_64_INIT; + hash_type = FNV1_64; + } else if (strcmp(p, "fnv1a64") == 0 || strcmp(p, "no64bit_fnv1a64") == 0) { + /* start with the FNV-1a initial basis */ + hval = FNV1A_64_INIT; + hash_type = FNV1a_64; + } else { + fprintf(stderr, "%s: unknown program name, unknown hash type\n", + program); + exit(7); + } + + /* + * FNV test vector processing, if needed + */ + if (t_flag >= 0) { + int code; /* test vector that failed, starting at 1 */ + + /* + * perform all tests + */ + code = test_fnv64(hash_type, hval, bmask, v_flag, t_flag); + + /* + * evaluate the tests + */ + if (code == 0) { + if (v_flag) { + printf("passed\n"); + } + exit(0); + } else { + printf("failed vector (1 is 1st test): %d\n", code); + exit(8); + } + } + + /* + * string hashing + */ + if (s_flag) { + + /* hash any other strings */ + for (i=optind; i < argc; ++i) { + switch (hash_type) { + case FNV0_64: + case FNV1_64: + hval = fnv_64_str(argv[i], hval); + break; + case FNV1a_64: + hval = fnv_64a_str(argv[i], hval); + break; + default: + unknown_hash_type(program, hash_type, 9); /* exit(9) */ + /*NOTREACHED*/ + } + if (m_flag) { + print_fnv64(hval, bmask, v_flag, argv[i]); + } + } + + + /* + * file hashing + */ + } else { + + /* + * case: process only stdin + */ + if (optind >= argc) { + + /* case: process only stdin */ + while ((readcnt = read(0, buf, BUF_SIZE)) > 0) { + switch (hash_type) { + case FNV0_64: + case FNV1_64: + hval = fnv_64_buf(buf, readcnt, hval); + break; + case FNV1a_64: + hval = fnv_64a_buf(buf, readcnt, hval); + break; + default: + unknown_hash_type(program, hash_type, 10); /* exit(10) */ + /*NOTREACHED*/ + } + } + if (m_flag) { + print_fnv64(hval, bmask, v_flag, "(stdin)"); + } + + } else { + + /* + * process any other files + */ + for (i=optind; i < argc; ++i) { + + /* open the file */ + fd = open(argv[i], O_RDONLY); + if (fd < 0) { + fprintf(stderr, "%s: unable to open file: %s\n", + program, argv[i]); + exit(4); + } + + /* hash the file */ + while ((readcnt = read(fd, buf, BUF_SIZE)) > 0) { + switch (hash_type) { + case FNV0_64: + case FNV1_64: + hval = fnv_64_buf(buf, readcnt, hval); + break; + case FNV1a_64: + hval = fnv_64a_buf(buf, readcnt, hval); + break; + default: + unknown_hash_type(program, hash_type, 11);/* exit(11) */ + /*NOTREACHED*/ + } + } + + /* finish processing the file */ + if (m_flag) { + print_fnv64(hval, bmask, v_flag, argv[i]); + } + close(fd); + } + } + } + + /* + * report hash and exit + */ + if (!m_flag) { + print_fnv64(hval, bmask, v_flag, ""); + } + return 0; /* exit(0); */ +} diff --git a/lib/fnv/hash_32.c b/lib/fnv/hash_32.c new file mode 100644 index 0000000000..077170ff6d --- /dev/null +++ b/lib/fnv/hash_32.c @@ -0,0 +1,156 @@ +/* + * hash_32 - 32 bit Fowler/Noll/Vo hash code + * + * @(#) $Revision: 5.1 $ + * @(#) $Id: hash_32.c,v 5.1 2009/06/30 09:13:32 chongo Exp $ + * @(#) $Source: /usr/local/src/cmd/fnv/RCS/hash_32.c,v $ + * + *** + * + * Fowler/Noll/Vo hash + * + * The basis of this hash algorithm was taken from an idea sent + * as reviewer comments to the IEEE POSIX P1003.2 committee by: + * + * Phong Vo (http://www.research.att.com/info/kpv/) + * Glenn Fowler (http://www.research.att.com/~gsf/) + * + * In a subsequent ballot round: + * + * Landon Curt Noll (http://www.isthe.com/chongo/) + * + * improved on their algorithm. Some people tried this hash + * and found that it worked rather well. In an EMail message + * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash. + * + * FNV hashes are designed to be fast while maintaining a low + * collision rate. The FNV speed allows one to quickly hash lots + * of data while maintaining a reasonable collision rate. See: + * + * http://www.isthe.com/chongo/tech/comp/fnv/index.html + * + * for more details as well as other forms of the FNV hash. + *** + * + * NOTE: The FNV-0 historic hash is not recommended. One should use + * the FNV-1 hash instead. + * + * To use the 32 bit FNV-0 historic hash, pass FNV0_32_INIT as the + * Fnv32_t hashval argument to fnv_32_buf() or fnv_32_str(). + * + * To use the recommended 32 bit FNV-1 hash, pass FNV1_32_INIT as the + * Fnv32_t hashval argument to fnv_32_buf() or fnv_32_str(). + * + *** + * + * Please do not copyright this code. This code is in the public domain. + * + * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO + * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR + * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF + * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR + * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR + * PERFORMANCE OF THIS SOFTWARE. + * + * By: + * chongo /\oo/\ + * http://www.isthe.com/chongo/ + * + * Share and Enjoy! :-) + */ + +#include +#include "fnv.h" + + +/* + * 32 bit magic FNV-0 and FNV-1 prime + */ +#define FNV_32_PRIME ((Fnv32_t)0x01000193) + + +/* + * 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 + * + * returns: + * 32 bit hash as a static hash type + * + * NOTE: To use the 32 bit FNV-0 historic hash, use FNV0_32_INIT as the hval + * argument on the first call to either fnv_32_buf() or fnv_32_str(). + * + * NOTE: To use the recommended 32 bit FNV-1 hash, use FNV1_32_INIT as the hval + * argument on the first call to either fnv_32_buf() or fnv_32_str(). + */ +Fnv32_t +fnv_32_buf(void *buf, size_t len, Fnv32_t hval) +{ + 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) { + + /* multiply by the 32 bit FNV magic prime mod 2^32 */ +#if defined(NO_FNV_GCC_OPTIMIZATION) + hval *= FNV_32_PRIME; +#else + hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24); +#endif + + /* xor the bottom with the current octet */ + hval ^= (Fnv32_t)*bp++; + } + + /* return our new hash value */ + return hval; +} + + +/* + * fnv_32_str - perform a 32 bit Fowler/Noll/Vo hash on a string + * + * input: + * str - string to hash + * hval - previous hash value or 0 if first call + * + * returns: + * 32 bit hash as a static hash type + * + * NOTE: To use the 32 bit FNV-0 historic hash, use FNV0_32_INIT as the hval + * argument on the first call to either fnv_32_buf() or fnv_32_str(). + * + * NOTE: To use the recommended 32 bit FNV-1 hash, use FNV1_32_INIT as the hval + * argument on the first call to either fnv_32_buf() or fnv_32_str(). + */ +Fnv32_t +fnv_32_str(char *str, Fnv32_t hval) +{ + unsigned char *s = (unsigned char *)str; /* unsigned string */ + + /* + * FNV-1 hash each octet in the buffer + */ + while (*s) { + + /* multiply by the 32 bit FNV magic prime mod 2^32 */ +#if defined(NO_FNV_GCC_OPTIMIZATION) + hval *= FNV_32_PRIME; +#else + hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24); +#endif + + /* xor the bottom with the current octet */ + hval ^= (Fnv32_t)*s++; + } + + /* return our new hash value */ + return hval; +} diff --git a/lib/fnv/hash_32a.c b/lib/fnv/hash_32a.c new file mode 100644 index 0000000000..8b10acf3e2 --- /dev/null +++ b/lib/fnv/hash_32a.c @@ -0,0 +1,144 @@ +/* + * hash_32 - 32 bit Fowler/Noll/Vo FNV-1a hash code + * + * @(#) $Revision: 5.1 $ + * @(#) $Id: hash_32a.c,v 5.1 2009/06/30 09:13:32 chongo Exp $ + * @(#) $Source: /usr/local/src/cmd/fnv/RCS/hash_32a.c,v $ + * + *** + * + * Fowler/Noll/Vo hash + * + * The basis of this hash algorithm was taken from an idea sent + * as reviewer comments to the IEEE POSIX P1003.2 committee by: + * + * Phong Vo (http://www.research.att.com/info/kpv/) + * Glenn Fowler (http://www.research.att.com/~gsf/) + * + * In a subsequent ballot round: + * + * Landon Curt Noll (http://www.isthe.com/chongo/) + * + * improved on their algorithm. Some people tried this hash + * and found that it worked rather well. In an EMail message + * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash. + * + * FNV hashes are designed to be fast while maintaining a low + * collision rate. The FNV speed allows one to quickly hash lots + * of data while maintaining a reasonable collision rate. See: + * + * http://www.isthe.com/chongo/tech/comp/fnv/index.html + * + * for more details as well as other forms of the FNV hash. + *** + * + * To use the recommended 32 bit FNV-1a hash, pass FNV1_32A_INIT as the + * Fnv32_t hashval argument to fnv_32a_buf() or fnv_32a_str(). + * + *** + * + * Please do not copyright this code. This code is in the public domain. + * + * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO + * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR + * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF + * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR + * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR + * PERFORMANCE OF THIS SOFTWARE. + * + * By: + * chongo /\oo/\ + * http://www.isthe.com/chongo/ + * + * Share and Enjoy! :-) + */ + +#include +#include "fnv.h" + + +/* + * 32 bit magic FNV-1a prime + */ +#define FNV_32_PRIME ((Fnv32_t)0x01000193) + + +/* + * fnv_32a_buf - perform a 32 bit Fowler/Noll/Vo FNV-1a 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 + * + * returns: + * 32 bit hash as a static hash type + * + * NOTE: To use the recommended 32 bit FNV-1a hash, use FNV1_32A_INIT as the + * hval arg on the first call to either fnv_32a_buf() or fnv_32a_str(). + */ +Fnv32_t +fnv_32a_buf(void *buf, size_t len, Fnv32_t hval) +{ + unsigned char *bp = (unsigned char *)buf; /* start of buffer */ + unsigned char *be = bp + len; /* beyond end of buffer */ + + /* + * FNV-1a hash each octet in the buffer + */ + while (bp < be) { + + /* xor the bottom with the current octet */ + hval ^= (Fnv32_t)*bp++; + + /* multiply by the 32 bit FNV magic prime mod 2^32 */ +#if defined(NO_FNV_GCC_OPTIMIZATION) + hval *= FNV_32_PRIME; +#else + hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24); +#endif + } + + /* return our new hash value */ + return hval; +} + + +/* + * fnv_32a_str - perform a 32 bit Fowler/Noll/Vo FNV-1a hash on a string + * + * input: + * str - string to hash + * hval - previous hash value or 0 if first call + * + * returns: + * 32 bit hash as a static hash type + * + * NOTE: To use the recommended 32 bit FNV-1a hash, use FNV1_32A_INIT as the + * hval arg on the first call to either fnv_32a_buf() or fnv_32a_str(). + */ +Fnv32_t +fnv_32a_str(char *str, Fnv32_t hval) +{ + unsigned char *s = (unsigned char *)str; /* unsigned string */ + + /* + * FNV-1a hash each octet in the buffer + */ + while (*s) { + + /* xor the bottom with the current octet */ + hval ^= (Fnv32_t)*s++; + + /* multiply by the 32 bit FNV magic prime mod 2^32 */ +#if defined(NO_FNV_GCC_OPTIMIZATION) + hval *= FNV_32_PRIME; +#else + hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24); +#endif + } + + /* return our new hash value */ + return hval; +} diff --git a/lib/fnv/hash_64.c b/lib/fnv/hash_64.c new file mode 100644 index 0000000000..4338605dca --- /dev/null +++ b/lib/fnv/hash_64.c @@ -0,0 +1,312 @@ +/* + * hash_64 - 64 bit Fowler/Noll/Vo-0 hash code + * + * @(#) $Revision: 5.1 $ + * @(#) $Id: hash_64.c,v 5.1 2009/06/30 09:01:38 chongo Exp $ + * @(#) $Source: /usr/local/src/cmd/fnv/RCS/hash_64.c,v $ + * + *** + * + * Fowler/Noll/Vo hash + * + * The basis of this hash algorithm was taken from an idea sent + * as reviewer comments to the IEEE POSIX P1003.2 committee by: + * + * Phong Vo (http://www.research.att.com/info/kpv/) + * Glenn Fowler (http://www.research.att.com/~gsf/) + * + * In a subsequent ballot round: + * + * Landon Curt Noll (http://www.isthe.com/chongo/) + * + * improved on their algorithm. Some people tried this hash + * and found that it worked rather well. In an EMail message + * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash. + * + * FNV hashes are designed to be fast while maintaining a low + * collision rate. The FNV speed allows one to quickly hash lots + * of data while maintaining a reasonable collision rate. See: + * + * http://www.isthe.com/chongo/tech/comp/fnv/index.html + * + * for more details as well as other forms of the FNV hash. + * + *** + * + * NOTE: The FNV-0 historic hash is not recommended. One should use + * the FNV-1 hash instead. + * + * To use the 64 bit FNV-0 historic hash, pass FNV0_64_INIT as the + * Fnv64_t hashval argument to fnv_64_buf() or fnv_64_str(). + * + * To use the recommended 64 bit FNV-1 hash, pass FNV1_64_INIT as the + * Fnv64_t hashval argument to fnv_64_buf() or fnv_64_str(). + * + *** + * + * Please do not copyright this code. This code is in the public domain. + * + * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO + * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR + * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF + * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR + * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR + * PERFORMANCE OF THIS SOFTWARE. + * + * By: + * chongo /\oo/\ + * http://www.isthe.com/chongo/ + * + * Share and Enjoy! :-) + */ + +#include +#include "fnv.h" + + +/* + * FNV-0 defines the initial basis to be zero + */ +#if !defined(HAVE_64BIT_LONG_LONG) +const Fnv64_t fnv0_64_init = { 0UL, 0UL }; +#endif /* ! HAVE_64BIT_LONG_LONG */ + + +/* + * FNV-1 defines the initial basis to be non-zero + */ +#if !defined(HAVE_64BIT_LONG_LONG) +const Fnv64_t fnv1_64_init = { 0x84222325UL, 0xcbf29ce4UL }; +#endif /* ! HAVE_64BIT_LONG_LONG */ + + +/* + * 64 bit magic FNV-0 and FNV-1 prime + */ +#if defined(HAVE_64BIT_LONG_LONG) +#define FNV_64_PRIME ((Fnv64_t)0x100000001b3ULL) +#else /* HAVE_64BIT_LONG_LONG */ +#define FNV_64_PRIME_LOW ((unsigned long)0x1b3) /* lower bits of FNV prime */ +#define FNV_64_PRIME_SHIFT (8) /* top FNV prime shift above 2^32 */ +#endif /* HAVE_64BIT_LONG_LONG */ + + +/* + * 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 + * + * returns: + * 64 bit hash as a static hash type + * + * NOTE: To use the 64 bit FNV-0 historic hash, use FNV0_64_INIT as the hval + * argument on the first call to either fnv_64_buf() or fnv_64_str(). + * + * NOTE: To use the recommended 64 bit FNV-1 hash, use FNV1_64_INIT as the hval + * argument on the first call to either fnv_64_buf() or fnv_64_str(). + */ +Fnv64_t +fnv_64_buf(void *buf, size_t len, Fnv64_t hval) +{ + unsigned char *bp = (unsigned char *)buf; /* start of buffer */ + unsigned char *be = bp + len; /* beyond end of buffer */ + +#if defined(HAVE_64BIT_LONG_LONG) + + /* + * FNV-1 hash each octet of the buffer + */ + while (bp < be) { + + /* multiply by the 64 bit FNV magic prime mod 2^64 */ +#if defined(NO_FNV_GCC_OPTIMIZATION) + hval *= FNV_64_PRIME; +#else /* NO_FNV_GCC_OPTIMIZATION */ + hval += (hval << 1) + (hval << 4) + (hval << 5) + + (hval << 7) + (hval << 8) + (hval << 40); +#endif /* NO_FNV_GCC_OPTIMIZATION */ + + /* xor the bottom with