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>

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, '/');