diff options
28 files changed, 7519 insertions, 0 deletions
diff --git a/builddefs/build_test.mk b/builddefs/build_test.mk index 834184f221..bd9b372c33 100644 --- a/builddefs/build_test.mk +++ b/builddefs/build_test.mk @@ -63,6 +63,7 @@ include $(TMK_PATH)/protocol.mk include $(QUANTUM_PATH)/debounce/tests/rules.mk include $(QUANTUM_PATH)/encoder/tests/rules.mk include $(QUANTUM_PATH)/sequencer/tests/rules.mk +include $(QUANTUM_PATH)/wear_leveling/tests/rules.mk include $(PLATFORM_PATH)/test/rules.mk ifneq ($(filter $(FULL_TESTS),$(TEST)),) include $(BUILDDEFS_PATH)/build_full_test.mk diff --git a/builddefs/common_features.mk b/builddefs/common_features.mk index b9ee0a30a7..552171fe68 100644 --- a/builddefs/common_features.mk +++ b/builddefs/common_features.mk @@ -650,6 +650,12 @@ ifeq ($(strip $(CRC_ENABLE)), yes) SRC += crc.c endif +ifeq ($(strip $(FNV_ENABLE)), yes) + OPT_DEFS += -DFNV_ENABLE + VPATH += $(LIB_PATH)/fnv + SRC += qmk_fnv_type_validation.c hash_32a.c hash_64a.c +endif + ifeq ($(strip $(HAPTIC_ENABLE)),yes) COMMON_VPATH += $(DRIVER_PATH)/haptic diff --git a/builddefs/testlist.mk b/builddefs/testlist.mk index b8d22bce80..8a30a44972 100644 --- a/builddefs/testlist.mk +++ b/builddefs/testlist.mk @@ -4,6 +4,7 @@ FULL_TESTS := $(notdir $(TEST_LIST)) include $(QUANTUM_PATH)/debounce/tests/testlist.mk include $(QUANTUM_PATH)/encoder/tests/testlist.mk include $(QUANTUM_PATH)/sequencer/tests/testlist.mk +include $(QUANTUM_PATH)/wear_leveling/tests/testlist.mk include $(PLATFORM_PATH)/test/testlist.mk define VALIDATE_TEST_LIST 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 <Landon Curt Noll> /\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 <Landon Curt Noll> /\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 <Landon Curt Noll> /\oo/\ + * http://www.isthe.com/chongo/ + * + * Share and Enjoy! :-) + */ + +#if !defined(__FNV_H__) +#define __FNV_H__ + +#include <sys/types.h> + +#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 <Landon Curt Noll> /\../\ + * + * 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 <Landon Curt Noll> /\../\ + * + * 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 <Landon Curt Noll> /\oo/\ + * http://www.isthe.com/chongo/ + * + * Share and Enjoy! :-) + */ + +#include <stdio.h> +#include <unistd.h> +#include <stdlib.h> +#include <sys/types.h> +#include <sys/stat.h> +#include <fcntl.h> +#include <string.h> +#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) { + |