summaryrefslogtreecommitdiffstats
path: root/lib/fnv
diff options
context:
space:
mode:
authorNick Brassel <nick@tzarc.org>2022-06-27 07:18:21 +1000
committerGitHub <noreply@github.com>2022-06-27 07:18:21 +1000
commit01ecf332ff9f0c8f61e493cdca116f58d80bb5fb (patch)
tree92fc03cbdeb2bf963574bfeed29276e164ca7561 /lib/fnv
parent0d013a21e1347fc38e742b2bd876329e86c153a9 (diff)
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 <karlk90@pm.me> * 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 <karlk90@pm.me>
Diffstat (limited to 'lib/fnv')
-rw-r--r--lib/fnv/Makefile304
-rw-r--r--lib/fnv/README158
-rw-r--r--lib/fnv/fnv.h249
-rw-r--r--lib/fnv/fnv32.c467
-rw-r--r--lib/fnv/fnv64.c591
-rw-r--r--lib/fnv/hash_32.c156
-rw-r--r--lib/fnv/hash_32a.c144
-rw-r--r--lib/fnv/hash_64.c312
-rw-r--r--lib/fnv/hash_64a.c291
-rw-r--r--lib/fnv/have_ulong64.c58
-rw-r--r--lib/fnv/longlong.h18
-rw-r--r--lib/fnv/qmk_fnv_type_validation.c14
-rw-r--r--lib/fnv/test_fnv.c2237
13 files changed, 4999 insertions, 0 deletions
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) {
+
+ /*
+ * 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, '/');