01ecf332ff9f0c8f61e493cdca116f58d80bb5fb
- Author
- Nick Brassel <nick@tzarc.org>
- Committer
- GitHub <noreply@github.com>
- Date
Message
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>
Diff
This diff is truncated to protect this page.
1diff --git a/builddefs/build_test.mk b/builddefs/build_test.mk
2index 834184f22167fbf2730121cbcf89cb508a642ec4..bd9b372c3321321c37a6dbcee224020335decb8c 100644
3--- a/builddefs/build_test.mk
4+++ b/builddefs/build_test.mk
5@@ -63,6 +63,7 @@ include $(TMK_PATH)/protocol.mk
6 include $(QUANTUM_PATH)/debounce/tests/rules.mk
7 include $(QUANTUM_PATH)/encoder/tests/rules.mk
8 include $(QUANTUM_PATH)/sequencer/tests/rules.mk
9+include $(QUANTUM_PATH)/wear_leveling/tests/rules.mk
10 include $(PLATFORM_PATH)/test/rules.mk
11 ifneq ($(filter $(FULL_TESTS),$(TEST)),)
12 include $(BUILDDEFS_PATH)/build_full_test.mk
13diff --git a/builddefs/common_features.mk b/builddefs/common_features.mk
14index b9ee0a30a75b8e9ee5cd5aaaea1c54882ebf6deb..552171fe689eb322d1e24cc34dc1ded3215d680b 100644
15--- a/builddefs/common_features.mk
16+++ b/builddefs/common_features.mk
17@@ -650,6 +650,12 @@ ifeq ($(strip $(CRC_ENABLE)), yes)
18 SRC += crc.c
19 endif
20
21+ifeq ($(strip $(FNV_ENABLE)), yes)
22+ OPT_DEFS += -DFNV_ENABLE
23+ VPATH += $(LIB_PATH)/fnv
24+ SRC += qmk_fnv_type_validation.c hash_32a.c hash_64a.c
25+endif
26+
27 ifeq ($(strip $(HAPTIC_ENABLE)),yes)
28 COMMON_VPATH += $(DRIVER_PATH)/haptic
29
30diff --git a/builddefs/testlist.mk b/builddefs/testlist.mk
31index b8d22bce805d055b307a0d79a715a0649b343df4..8a30a44972425e923ea5acaa4661010cc979cda6 100644
32--- a/builddefs/testlist.mk
33+++ b/builddefs/testlist.mk
34@@ -4,6 +4,7 @@ FULL_TESTS := $(notdir $(TEST_LIST))
35 include $(QUANTUM_PATH)/debounce/tests/testlist.mk
36 include $(QUANTUM_PATH)/encoder/tests/testlist.mk
37 include $(QUANTUM_PATH)/sequencer/tests/testlist.mk
38+include $(QUANTUM_PATH)/wear_leveling/tests/testlist.mk
39 include $(PLATFORM_PATH)/test/testlist.mk
40
41 define VALIDATE_TEST_LIST
42diff --git a/lib/fnv/Makefile b/lib/fnv/Makefile
43new file mode 100644
44index 0000000000000000000000000000000000000000..c0673ded402fbe4e5f12e7e2eeebb6945bc88bb4
45--- /dev/null
46+++ b/lib/fnv/Makefile
47@@ -0,0 +1,304 @@
48+#!/bin/make
49+#
50+# hash - makefile for FNV hash tools
51+#
52+# @(#) $Revision: 5.2 $
53+# @(#) $Id: Makefile,v 5.2 2012/03/21 01:42:15 chongo Exp $
54+# @(#) $Source: /usr/local/src/cmd/fnv/RCS/Makefile,v $
55+#
56+# See:
57+# http://www.isthe.com/chongo/tech/comp/fnv/index.html
58+#
59+# for the most up to date copy of this code and the FNV hash home page.
60+#
61+# Please do not copyright this code. This code is in the public domain.
62+#
63+# LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
64+# INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
65+# EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
66+# CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
67+# USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
68+# OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
69+# PERFORMANCE OF THIS SOFTWARE.
70+#
71+# By:
72+# chongo <Landon Curt Noll> /\oo/\
73+# http://www.isthe.com/chongo/
74+#
75+# Share and Enjoy! :-)
76+
77+# make tools
78+#
79+SHELL= /bin/sh
80+CFLAGS= -O3 -g3
81+#CFLAGS= -O2 -g3
82+#CC= cc
83+AR= ar
84+TAR= tar
85+EGREP= egrep
86+GZIP_BIN= gzip
87+INSTALL= install
88+
89+# If your system needs ranlib use:
90+# RANLIB= ranlib
91+# otherwise use:
92+# RANLIB= :
93+#
94+#RANLIB= ranlib
95+RANLIB= :
96+
97+# where to install things
98+#
99+DESTBIN= /usr/local/bin
100+DESTLIB= /usr/local/lib
101+DESTINC= /usr/local/include
102+
103+# what to build
104+#
105+SRC= hash_32.c hash_32a.c hash_64.c hash_64a.c \
106+ fnv32.c fnv64.c \
107+ have_ulong64.c test_fnv.c
108+NO64BIT_SRC= no64bit_fnv64.c no64bit_hash_64.c \
109+ no64bit_hash_64a.c no64bit_test_fnv.c
110+HSRC= fnv.h \
111+ longlong.h
112+ALL= ${SRC} ${HSRC} \
113+ README Makefile
114+PROGS= fnv032 fnv064 fnv132 fnv164 fnv1a32 fnv1a64
115+OBSOLETE_PROGS= fnv0_32 fnv0_64 fnv1_32 fnv1_64 fnv1a_32 fnv1a_64
116+NO64BIT_PROGS= no64bit_fnv064 no64bit_fnv164 no64bit_fnv1a64
117+LIBS= libfnv.a
118+LIBOBJ= hash_32.o hash_64.o hash_32a.o hash_64a.o test_fnv.o
119+NO64BIT_OBJ= no64bit_fnv64.o no64bit_hash_64.o \
120+ no64bit_hash_64a.o no64bit_test_fnv.o
121+OTHEROBJ= fnv32.o fnv64.o
122+TARGETS= ${LIBOBJ} ${LIBS} ${PROGS}
123+
124+# default rule
125+#
126+all: ${TARGETS}
127+
128+# things to build
129+#
130+hash_32.o: hash_32.c longlong.h fnv.h
131+ ${CC} ${CFLAGS} hash_32.c -c
132+
133+hash_64.o: hash_64.c longlong.h fnv.h
134+ ${CC} ${CFLAGS} hash_64.c -c
135+
136+hash_32a.o: hash_32a.c longlong.h fnv.h
137+ ${CC} ${CFLAGS} hash_32a.c -c
138+
139+hash_64a.o: hash_64a.c longlong.h fnv.h
140+ ${CC} ${CFLAGS} hash_64a.c -c
141+
142+test_fnv.o: test_fnv.c longlong.h fnv.h
143+ ${CC} ${CFLAGS} test_fnv.c -c
144+
145+fnv32.o: fnv32.c longlong.h fnv.h
146+ ${CC} ${CFLAGS} fnv32.c -c
147diff --git a/lib/fnv/README b/lib/fnv/README
148new file mode 100644
149index 0000000000000000000000000000000000000000..60aa9aaf610ff9b7ff682b94cbdce1fb60f68c60
150--- /dev/null
151+++ b/lib/fnv/README
152@@ -0,0 +1,158 @@
153+#=====================#
154+# Fowler/Noll/Vo hash #
155+#=====================#
156+
157+The basis of this hash algorithm was taken from an idea sent
158+as reviewer comments to the IEEE POSIX P1003.2 committee by:
159+
160+ Phong Vo (http://www.research.att.com/info/kpv)
161+ Glenn Fowler (http://www.research.att.com/~gsf/)
162+
163+In a subsequent ballot round:
164+
165+ Landon Curt Noll (http://www.isthe.com/chongo)
166+
167+improved on their algorithm. Some people tried this hash
168+and found that it worked rather well. In an EMail message
169+to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
170+
171+FNV hashes are designed to be fast while maintaining a low
172+collision rate. The FNV speed allows one to quickly hash lots
173+of data while maintaining a reasonable collision rate. See:
174+
175+ http://www.isthe.com/chongo/tech/comp/fnv/index.html
176+
177+for more details as well as other forms of the FNV hash.
178+Comments, questions, bug fixes and suggestions welcome at
179+the address given in the above URL.
180+
181+
182+#==================#
183+# FNV hash utility #
184+#==================#
185+
186+Two hash utilities (32 bit and 64 bit) are provided:
187+
188+ fnv032 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]
189+ fnv132 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]
190+ fnv1a32 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]
191+
192+ fnv064 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]
193+ fnv164 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]
194+ fnv1a64 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]
195+
196+ -b bcnt mask off all but the lower bcnt bits (default: 32)
197+ -m multiple hashes, one per line for each arg
198+ -s hash arg as a string (ignoring terminating NUL bytes)
199+ -t code 0 ==> generate test vectors, 1 ==> test FNV hash
200+ -v verbose mode, print arg after hash (implies -m)
201+ arg string (if -s was given) or filename (default stdin)
202+
203+The fnv032, fnv064 implement the historic FNV-0 hash.
204+The fnv132, fnv164 implement the recommended FNV-1 hash.
205+The fnv1a32, fnv1a64 implement the recommended FNV-1a hash.
206+
207+This is the original historic FNV algorithm with a 0 offset basis.
208+It is recommended that FNV-1, with a non-0 offset basis be used instead.
209+
210+To test FNV hashes, try:
211+
212+ fnv032 -t 1 -v
213+ fnv132 -t 1 -v
214+ fnv1a32 -t 1 -v
215+
216+ fnv064 -t 1 -v
217+ fnv164 -t 1 -v
218+ fnv1a64 -t 1 -v
219+
220+If you are compiling, try:
221+
222+ make check
223+
224+
225+#==================#
226+# FNV hash library #
227+#==================#
228+
229+The libfnv.a library implements both a 32 bit and a 64 bit FNV hash
230+on collections of bytes, a NUL terminated strings or on an open file
231+descriptor.
232+
233+Here is the 32 bit FNV 1 hash:
234+
235+ Fnv32_t fnv_32_buf(void *buf, int len, Fnv32_t hval); /* byte buf */
236+ Fnv32_t fnv_32_str(char *string, Fnv32_t hval); /* string */
237+
238+Here is the 32 bit FNV 1a hash:
239+
240+ Fnv32_t fnv_32a_buf(void *buf, int len, Fnv32_t hval); /* byte buf */
241+ Fnv32_t fnv_32a_str(char *string, Fnv32_t hval); /* string */
242+
243+Here is the 64 bit FNV 1 hash:
244+
245+ Fnv64_t fnv_64_buf(void *buf, int len, Fnv64_t hval); /* byte buf */
246+ Fnv64_t fnv_64_str(char *string, Fnv64_t hval); /* string */
247+
248+Here is the 64 bit FNV 1a hash:
249+
250+ Fnv64_t fnv_64a_buf(void *buf, int len, Fnv64_t hval); /* byte buf */
251+ Fnv64_t fnv_64a_str(char *string, Fnv64_t hval); /* string */
252diff --git a/lib/fnv/fnv.h b/lib/fnv/fnv.h
253new file mode 100644
254index 0000000000000000000000000000000000000000..2083a4aa23f99244111032732061093b374ada2f
255--- /dev/null
256+++ b/lib/fnv/fnv.h
257@@ -0,0 +1,249 @@
258+/*
259+ * fnv - Fowler/Noll/Vo- hash code
260+ *
261+ * @(#) $Revision: 5.4 $
262+ * @(#) $Id: fnv.h,v 5.4 2009/07/30 22:49:13 chongo Exp $
263+ * @(#) $Source: /usr/local/src/cmd/fnv/RCS/fnv.h,v $
264+ *
265+ ***
266+ *
267+ * Fowler/Noll/Vo- hash
268+ *
269+ * The basis of this hash algorithm was taken from an idea sent
270+ * as reviewer comments to the IEEE POSIX P1003.2 committee by:
271+ *
272+ * Phong Vo (http://www.research.att.com/info/kpv/)
273+ * Glenn Fowler (http://www.research.att.com/~gsf/)
274+ *
275+ * In a subsequent ballot round:
276+ *
277+ * Landon Curt Noll (http://www.isthe.com/chongo/)
278+ *
279+ * improved on their algorithm. Some people tried this hash
280+ * and found that it worked rather well. In an EMail message
281+ * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
282+ *
283+ * FNV hashes are designed to be fast while maintaining a low
284+ * collision rate. The FNV speed allows one to quickly hash lots
285+ * of data while maintaining a reasonable collision rate. See:
286+ *
287+ * http://www.isthe.com/chongo/tech/comp/fnv/index.html
288+ *
289+ * for more details as well as other forms of the FNV hash.
290+ *
291+ ***
292+ *
293+ * NOTE: The FNV-0 historic hash is not recommended. One should use
294+ * the FNV-1 hash instead.
295+ *
296+ * To use the 32 bit FNV-0 historic hash, pass FNV0_32_INIT as the
297+ * Fnv32_t hashval argument to fnv_32_buf() or fnv_32_str().
298+ *
299+ * To use the 64 bit FNV-0 historic hash, pass FNV0_64_INIT as the
300+ * Fnv64_t hashval argument to fnv_64_buf() or fnv_64_str().
301+ *
302+ * To use the recommended 32 bit FNV-1 hash, pass FNV1_32_INIT as the
303+ * Fnv32_t hashval argument to fnv_32_buf() or fnv_32_str().
304+ *
305+ * To use the recommended 64 bit FNV-1 hash, pass FNV1_64_INIT as the
306+ * Fnv64_t hashval argument to fnv_64_buf() or fnv_64_str().
307+ *
308+ * To use the recommended 32 bit FNV-1a hash, pass FNV1_32A_INIT as the
309+ * Fnv32_t hashval argument to fnv_32a_buf() or fnv_32a_str().
310+ *
311+ * To use the recommended 64 bit FNV-1a hash, pass FNV1A_64_INIT as the
312+ * Fnv64_t hashval argument to fnv_64a_buf() or fnv_64a_str().
313+ *
314+ ***
315+ *
316+ * Please do not copyright this code. This code is in the public domain.
317+ *
318+ * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
319+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
320+ * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
321+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
322+ * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
323+ * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
324+ * PERFORMANCE OF THIS SOFTWARE.
325+ *
326+ * By:
327+ * chongo <Landon Curt Noll> /\oo/\
328+ * http://www.isthe.com/chongo/
329+ *
330+ * Share and Enjoy! :-)
331+ */
332+
333+#if !defined(__FNV_H__)
334+#define __FNV_H__
335+
336+#include <sys/types.h>
337+
338+#define FNV_VERSION "5.0.2" /* @(#) FNV Version */
339+
340+
341+/*
342+ * 32 bit FNV-0 hash type
343+ */
344+typedef u_int32_t Fnv32_t;
345+
346+
347+/*
348+ * 32 bit FNV-0 zero initial basis
349+ *
350+ * This historic hash is not recommended. One should use
351+ * the FNV-1 hash and initial basis instead.
352+ */
353+#define FNV0_32_INIT ((Fnv32_t)0)
354+
355+
356+/*
357diff --git a/lib/fnv/fnv32.c b/lib/fnv/fnv32.c
358new file mode 100644
359index 0000000000000000000000000000000000000000..58c61f03fcb2bd179b411e4141f4a1e28f55f4c7
360--- /dev/null
361+++ b/lib/fnv/fnv32.c
362@@ -0,0 +1,467 @@
363+/*
364+ * fnv32 - 32 bit Fowler/Noll/Vo hash of a buffer or string
365+ *
366+ * @(#) $Revision: 5.5 $
367+ * @(#) $Id: fnv32.c,v 5.5 2012/03/21 01:38:12 chongo Exp $
368+ * @(#) $Source: /usr/local/src/cmd/fnv/RCS/fnv32.c,v $
369+ *
370+ ***
371+ *
372+ * Fowler/Noll/Vo hash
373+ *
374+ * The basis of this hash algorithm was taken from an idea sent
375+ * as reviewer comments to the IEEE POSIX P1003.2 committee by:
376+ *
377+ * Phong Vo (http://www.research.att.com/info/kpv/)
378+ * Glenn Fowler (http://www.research.att.com/~gsf/)
379+ *
380+ * In a subsequent ballot round:
381+ *
382+ * Landon Curt Noll (http://www.isthe.com/chongo/)
383+ *
384+ * improved on their algorithm. Some people tried this hash
385+ * and found that it worked rather well. In an EMail message
386+ * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
387+ *
388+ * FNV hashes are designed to be fast while maintaining a low
389+ * collision rate. The FNV speed allows one to quickly hash lots
390+ * of data while maintaining a reasonable collision rate. See:
391+ *
392+ * http://www.isthe.com/chongo/tech/comp/fnv/index.html
393+ *
394+ * for more details as well as other forms of the FNV hash.
395+ *
396+ ***
397+ *
398+ * Please do not copyright this code. This code is in the public domain.
399+ *
400+ * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
401+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
402+ * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
403+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
404+ * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
405+ * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
406+ * PERFORMANCE OF THIS SOFTWARE.
407+ *
408+ * By:
409+ * chongo <Landon Curt Noll> /\oo/\
410+ * http://www.isthe.com/chongo/
411+ *
412+ * Share and Enjoy! :-)
413+ */
414+
415+#include <stdio.h>
416+#include <unistd.h>
417+#include <stdlib.h>
418+#include <sys/types.h>
419+#include <sys/stat.h>
420+#include <fcntl.h>
421+#include <string.h>
422+#include "longlong.h"
423+#include "fnv.h"
424+
425+#define WIDTH 32 /* bit width of hash */
426+
427+#define BUF_SIZE (32*1024) /* number of bytes to hash at a time */
428+
429+static char *usage =
430+"usage: %s [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]\n"
431+"\n"
432+"\t-b bcnt\tmask off all but the lower bcnt bits (default 32)\n"
433+"\t-m\tmultiple hashes, one per line for each arg\n"
434+"\t-s\thash arg as a string (ignoring terminating NUL bytes)\n"
435+"\t-t code\t test hash code: (0 ==> generate test vectors\n"
436+"\t\t\t\t 1 ==> validate against FNV test vectors)\n"
437+"\t-v\tverbose mode, print arg after hash (implies -m)\n"
438+"\targ\tstring (if -s was given) or filename (default stdin)\n"
439+"\n"
440+"\tNOTE: Programs that begin with fnv0 implement the FNV-0 hash.\n"
441+"\t The FNV-0 hash is historic FNV algorithm that is now deprecated.\n"
442+"\n"
443+"\tSee http://www.isthe.com/chongo/tech/comp/fnv/index.html for more info.\n"
444+"\n"
445+"\t@(#) FNV Version: %s\n";
446+static char *program; /* our name */
447+
448+
449+/*
450+ * test_fnv32 - test the FNV32 hash
451+ *
452+ * given:
453+ * hash_type type of FNV hash to test
454+ * init_hval initial hash value
455+ * mask lower bit mask
456+ * v_flag 1 => print test failure info on stderr
457+ * code 0 ==> generate FNV test vectors
458+ * 1 ==> validate against FNV test vectors
459+ *
460+ * returns: 0 ==> OK, else test vector failure number
461+ */
462diff --git a/lib/fnv/fnv64.c b/lib/fnv/fnv64.c
463new file mode 100644
464index 0000000000000000000000000000000000000000..0662d4d65726978f6b87d0dc71a4f66243987f61
465--- /dev/null
466+++ b/lib/fnv/fnv64.c
467@@ -0,0 +1,591 @@
468+/*
469+ * fnv_64 - 64 bit Fowler/Noll/Vo hash of a buffer or string
470+ *
471+ * @(#) $Revision: 5.5 $
472+ * @(#) $Id: fnv64.c,v 5.5 2012/03/21 01:38:12 chongo Exp $
473+ * @(#) $Source: /usr/local/src/cmd/fnv/RCS/fnv64.c,v $
474+ *
475+ ***
476+ *
477+ * Fowler/Noll/Vo hash
478+ *
479+ * The basis of this hash algorithm was taken from an idea sent
480+ * as reviewer comments to the IEEE POSIX P1003.2 committee by:
481+ *
482+ * Phong Vo (http://www.research.att.com/info/kpv/)
483+ * Glenn Fowler (http://www.research.att.com/~gsf/)
484+ *
485+ * In a subsequent ballot round:
486+ *
487+ * Landon Curt Noll (http://www.isthe.com/chongo/)
488+ *
489+ * improved on their algorithm. Some people tried this hash
490+ * and found that it worked rather well. In an EMail message
491+ * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
492+ *
493+ * FNV hashes are designed to be fast while maintaining a low
494+ * collision rate. The FNV speed allows one to quickly hash lots
495+ * of data while maintaining a reasonable collision rate. See:
496+ *
497+ * http://www.isthe.com/chongo/tech/comp/fnv/index.html
498+ *
499+ * for more details as well as other forms of the FNV hash.
500+ *
501+ ***
502+ *
503+ * Please do not copyright this code. This code is in the public domain.
504+ *
505+ * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
506+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
507+ * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
508+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
509+ * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
510+ * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
511+ * PERFORMANCE OF THIS SOFTWARE.
512+ *
513+ * By:
514+ * chongo <Landon Curt Noll> /\oo/\
515+ * http://www.isthe.com/chongo/
516+ *
517+ * Share and Enjoy! :-)
518+ */
519+
520+#include <stdio.h>
521+#include <unistd.h>
522+#include <stdlib.h>
523+#include <sys/types.h>
524+#include <sys/stat.h>
525+#include <fcntl.h>
526+#include <string.h>
527+#include "longlong.h"
528+#include "fnv.h"
529+
530+#define WIDTH 64 /* bit width of hash */
531+
532+#define BUF_SIZE (32*1024) /* number of bytes to hash at a time */
533+
534+static char *usage =
535+"usage: %s [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]\n"
536+"\n"
537+"\t-b bcnt\tmask off all but the lower bcnt bits (default 64)\n"
538+"\t-m\tmultiple hashes, one per line for each arg\n"
539+"\t-s\thash arg as a string (ignoring terminating NUL bytes)\n"
540+"\t-t code\t test hash code: (0 ==> generate test vectors\n"
541+"\t\t\t\t 1 ==> validate against FNV test vectors)\n"
542+"\t-v\tverbose mode, print arg after hash (implies -m)\n"
543+"\targ\tstring (if -s was given) or filename (default stdin)\n"
544+"\n"
545+"\tNOTE: Programs that begin with fnv0 implement the FNV-0 hash.\n"
546+"\t The FNV-0 hash is historic FNV algorithm that is now deprecated.\n"
547+"\n"
548+"\tSee http://www.isthe.com/chongo/tech/comp/fnv/index.html for more info.\n"
549+"\n"
550+"\t@(#) FNV Version: %s\n";
551+static char *program; /* our name */
552+
553+
554+/*
555+ * test_fnv64 - test the FNV64 hash
556+ *
557+ * given:
558+ * hash_type type of FNV hash to test
559+ * init_hval initial hash value
560+ * mask lower bit mask
561+ * v_flag 1 => print test failure info on stderr
562+ * code 0 ==> generate FNV test vectors
563+ * 1 ==> validate against FNV test vectors
564+ *
565+ * returns: 0 ==> OK, else test vector failure number
566+ */
567diff --git a/lib/fnv/hash_32.c b/lib/fnv/hash_32.c
568new file mode 100644
569index 0000000000000000000000000000000000000000..077170ff6d930010d6ceb77037057fb910de4f8e
570--- /dev/null
571+++ b/lib/fnv/hash_32.c
572@@ -0,0 +1,156 @@
573+/*
574+ * hash_32 - 32 bit Fowler/Noll/Vo hash code
575+ *
576+ * @(#) $Revision: 5.1 $
577+ * @(#) $Id: hash_32.c,v 5.1 2009/06/30 09:13:32 chongo Exp $
578+ * @(#) $Source: /usr/local/src/cmd/fnv/RCS/hash_32.c,v $
579+ *
580+ ***
581+ *
582+ * Fowler/Noll/Vo hash
583+ *
584+ * The basis of this hash algorithm was taken from an idea sent
585+ * as reviewer comments to the IEEE POSIX P1003.2 committee by:
586+ *
587+ * Phong Vo (http://www.research.att.com/info/kpv/)
588+ * Glenn Fowler (http://www.research.att.com/~gsf/)
589+ *
590+ * In a subsequent ballot round:
591+ *
592+ * Landon Curt Noll (http://www.isthe.com/chongo/)
593+ *
594+ * improved on their algorithm. Some people tried this hash
595+ * and found that it worked rather well. In an EMail message
596+ * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
597+ *
598+ * FNV hashes are designed to be fast while maintaining a low
599+ * collision rate. The FNV speed allows one to quickly hash lots
600+ * of data while maintaining a reasonable collision rate. See:
601+ *
602+ * http://www.isthe.com/chongo/tech/comp/fnv/index.html
603+ *
604+ * for more details as well as other forms of the FNV hash.
605+ ***
606+ *
607+ * NOTE: The FNV-0 historic hash is not recommended. One should use
608+ * the FNV-1 hash instead.
609+ *
610+ * To use the 32 bit FNV-0 historic hash, pass FNV0_32_INIT as the
611+ * Fnv32_t hashval argument to fnv_32_buf() or fnv_32_str().
612+ *
613+ * To use the recommended 32 bit FNV-1 hash, pass FNV1_32_INIT as the
614+ * Fnv32_t hashval argument to fnv_32_buf() or fnv_32_str().
615+ *
616+ ***
617+ *
618+ * Please do not copyright this code. This code is in the public domain.
619+ *
620+ * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
621+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
622+ * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
623+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
624+ * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
625+ * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
626+ * PERFORMANCE OF THIS SOFTWARE.
627+ *
628+ * By:
629+ * chongo <Landon Curt Noll> /\oo/\
630+ * http://www.isthe.com/chongo/
631+ *
632+ * Share and Enjoy! :-)
633+ */
634+
635+#include <stdlib.h>
636+#include "fnv.h"
637+
638+
639+/*
640+ * 32 bit magic FNV-0 and FNV-1 prime
641+ */
642+#define FNV_32_PRIME ((Fnv32_t)0x01000193)
643+
644+
645+/*
646+ * fnv_32_buf - perform a 32 bit Fowler/Noll/Vo hash on a buffer
647+ *
648+ * input:
649+ * buf - start of buffer to hash
650+ * len - length of buffer in octets
651+ * hval - previous hash value or 0 if first call
652+ *
653+ * returns:
654+ * 32 bit hash as a static hash type
655+ *
656+ * NOTE: To use the 32 bit FNV-0 historic hash, use FNV0_32_INIT as the hval
657+ * argument on the first call to either fnv_32_buf() or fnv_32_str().
658+ *
659+ * NOTE: To use the recommended 32 bit FNV-1 hash, use FNV1_32_INIT as the hval
660+ * argument on the first call to either fnv_32_buf() or fnv_32_str().
661+ */
662+Fnv32_t
663+fnv_32_buf(void *buf, size_t len, Fnv32_t hval)
664+{
665+ unsigned char *bp = (unsigned char *)buf; /* start of buffer */
666+ unsigned char *be = bp + len; /* beyond end of buffer */
667+
668+ /*
669+ * FNV-1 hash each octet in the buffer
670+ */
671+ while (bp < be) {
672diff --git a/lib/fnv/hash_32a.c b/lib/fnv/hash_32a.c
673new file mode 100644
674index 0000000000000000000000000000000000000000..8b10acf3e2f57e54cac5d045826ff41ab0471283
675--- /dev/null
676+++ b/lib/fnv/hash_32a.c
677@@ -0,0 +1,144 @@
678+/*
679+ * hash_32 - 32 bit Fowler/Noll/Vo FNV-1a hash code
680+ *
681+ * @(#) $Revision: 5.1 $
682+ * @(#) $Id: hash_32a.c,v 5.1 2009/06/30 09:13:32 chongo Exp $
683+ * @(#) $Source: /usr/local/src/cmd/fnv/RCS/hash_32a.c,v $
684+ *
685+ ***
686+ *
687+ * Fowler/Noll/Vo hash
688+ *
689+ * The basis of this hash algorithm was taken from an idea sent
690+ * as reviewer comments to the IEEE POSIX P1003.2 committee by:
691+ *
692+ * Phong Vo (http://www.research.att.com/info/kpv/)
693+ * Glenn Fowler (http://www.research.att.com/~gsf/)
694+ *
695+ * In a subsequent ballot round:
696+ *
697+ * Landon Curt Noll (http://www.isthe.com/chongo/)
698+ *
699+ * improved on their algorithm. Some people tried this hash
700+ * and found that it worked rather well. In an EMail message
701+ * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
702+ *
703+ * FNV hashes are designed to be fast while maintaining a low
704+ * collision rate. The FNV speed allows one to quickly hash lots
705+ * of data while maintaining a reasonable collision rate. See:
706+ *
707+ * http://www.isthe.com/chongo/tech/comp/fnv/index.html
708+ *
709+ * for more details as well as other forms of the FNV hash.
710+ ***
711+ *
712+ * To use the recommended 32 bit FNV-1a hash, pass FNV1_32A_INIT as the
713+ * Fnv32_t hashval argument to fnv_32a_buf() or fnv_32a_str().
714+ *
715+ ***
716+ *
717+ * Please do not copyright this code. This code is in the public domain.
718+ *
719+ * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
720+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
721+ * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
722+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
723+ * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
724+ * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
725+ * PERFORMANCE OF THIS SOFTWARE.
726+ *
727+ * By:
728+ * chongo <Landon Curt Noll> /\oo/\
729+ * http://www.isthe.com/chongo/
730+ *
731+ * Share and Enjoy! :-)
732+ */
733+
734+#include <stdlib.h>
735+#include "fnv.h"
736+
737+
738+/*
739+ * 32 bit magic FNV-1a prime
740+ */
741+#define FNV_32_PRIME ((Fnv32_t)0x01000193)
742+
743+
744+/*
745+ * fnv_32a_buf - perform a 32 bit Fowler/Noll/Vo FNV-1a hash on a buffer
746+ *
747+ * input:
748+ * buf - start of buffer to hash
749+ * len - length of buffer in octets
750+ * hval - previous hash value or 0 if first call
751+ *
752+ * returns:
753+ * 32 bit hash as a static hash type
754+ *
755+ * NOTE: To use the recommended 32 bit FNV-1a hash, use FNV1_32A_INIT as the
756+ * hval arg on the first call to either fnv_32a_buf() or fnv_32a_str().
757+ */
758+Fnv32_t
759+fnv_32a_buf(void *buf, size_t len, Fnv32_t hval)
760+{
761+ unsigned char *bp = (unsigned char *)buf; /* start of buffer */
762+ unsigned char *be = bp + len; /* beyond end of buffer */
763+
764+ /*
765+ * FNV-1a hash each octet in the buffer
766+ */
767+ while (bp < be) {
768+
769+ /* xor the bottom with the current octet */
770+ hval ^= (Fnv32_t)*bp++;
771+
772+ /* multiply by the 32 bit FNV magic prime mod 2^32 */
773+#if defined(NO_FNV_GCC_OPTIMIZATION)
774+ hval *= FNV_32_PRIME;
775+#else
776+ hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);
777diff --git a/lib/fnv/hash_64.c b/lib/fnv/hash_64.c
778new file mode 100644
779index 0000000000000000000000000000000000000000..4338605dcaf269dfe80e6d858f3646e330e75faf
780--- /dev/null
781+++ b/lib/fnv/hash_64.c
782@@ -0,0 +1,312 @@
783+/*
784+ * hash_64 - 64 bit Fowler/Noll/Vo-0 hash code
785+ *
786+ * @(#) $Revision: 5.1 $
787+ * @(#) $Id: hash_64.c,v 5.1 2009/06/30 09:01:38 chongo Exp $
788+ * @(#) $Source: /usr/local/src/cmd/fnv/RCS/hash_64.c,v $
789+ *
790+ ***
791+ *
792+ * Fowler/Noll/Vo hash
793+ *
794+ * The basis of this hash algorithm was taken from an idea sent
795+ * as reviewer comments to the IEEE POSIX P1003.2 committee by:
796+ *
797+ * Phong Vo (http://www.research.att.com/info/kpv/)
798+ * Glenn Fowler (http://www.research.att.com/~gsf/)
799+ *
800+ * In a subsequent ballot round:
801+ *
802+ * Landon Curt Noll (http://www.isthe.com/chongo/)
803+ *
804+ * improved on their algorithm. Some people tried this hash
805+ * and found that it worked rather well. In an EMail message
806+ * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
807+ *
808+ * FNV hashes are designed to be fast while maintaining a low
809+ * collision rate. The FNV speed allows one to quickly hash lots
810+ * of data while maintaining a reasonable collision rate. See:
811+ *
812+ * http://www.isthe.com/chongo/tech/comp/fnv/index.html
813+ *
814+ * for more details as well as other forms of the FNV hash.
815+ *
816+ ***
817+ *
818+ * NOTE: The FNV-0 historic hash is not recommended. One should use
819+ * the FNV-1 hash instead.
820+ *
821+ * To use the 64 bit FNV-0 historic hash, pass FNV0_64_INIT as the
822+ * Fnv64_t hashval argument to fnv_64_buf() or fnv_64_str().
823+ *
824+ * To use the recommended 64 bit FNV-1 hash, pass FNV1_64_INIT as the
825+ * Fnv64_t hashval argument to fnv_64_buf() or fnv_64_str().
826+ *
827+ ***
828+ *
829+ * Please do not copyright this code. This code is in the public domain.
830+ *
831+ * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
832+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
833+ * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
834+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
835+ * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
836+ * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
837+ * PERFORMANCE OF THIS SOFTWARE.
838+ *
839+ * By:
840+ * chongo <Landon Curt Noll> /\oo/\
841+ * http://www.isthe.com/chongo/
842+ *
843+ * Share and Enjoy! :-)
844+ */
845+
846+#include <stdlib.h>
847+#include "fnv.h"
848+
849+
850+/*
851+ * FNV-0 defines the initial basis to be zero
852+ */
853+#if !defined(HAVE_64BIT_LONG_LONG)
854+const Fnv64_t fnv0_64_init = { 0UL, 0UL };
855+#endif /* ! HAVE_64BIT_LONG_LONG */
856+
857+
858+/*
859+ * FNV-1 defines the initial basis to be non-zero
860+ */
861+#if !defined(HAVE_64BIT_LONG_LONG)
862+const Fnv64_t fnv1_64_init = { 0x84222325UL, 0xcbf29ce4UL };
863+#endif /* ! HAVE_64BIT_LONG_LONG */
864+
865+
866+/*
867+ * 64 bit magic FNV-0 and FNV-1 prime
868+ */
869+#if defined(HAVE_64BIT_LONG_LONG)
870+#define FNV_64_PRIME ((Fnv64_t)0x100000001b3ULL)
871+#else /* HAVE_64BIT_LONG_LONG */
872+#define FNV_64_PRIME_LOW ((unsigned long)0x1b3) /* lower bits of FNV prime */
873+#define FNV_64_PRIME_SHIFT (8) /* top FNV prime shift above 2^32 */
874+#endif /* HAVE_64BIT_LONG_LONG */
875+
876+
877+/*
878+ * fnv_64_buf - perform a 64 bit Fowler/Noll/Vo hash on a buffer
879+ *
880+ * input:
881+ * buf - start of buffer to hash
882diff --git a/lib/fnv/hash_64a.c b/lib/fnv/hash_64a.c
883new file mode 100644
884index 0000000000000000000000000000000000000000..6660f92ddf0f2ec768f61d7bb63c042856e7e7cf
885--- /dev/null
886+++ b/lib/fnv/hash_64a.c
887@@ -0,0 +1,291 @@
888+/*
889+ * hash_64 - 64 bit Fowler/Noll/Vo-0 FNV-1a hash code
890+ *
891+ * @(#) $Revision: 5.1 $
892+ * @(#) $Id: hash_64a.c,v 5.1 2009/06/30 09:01:38 chongo Exp $
893+ * @(#) $Source: /usr/local/src/cmd/fnv/RCS/hash_64a.c,v $
894+ *
895+ ***
896+ *
897+ * Fowler/Noll/Vo hash
898+ *
899+ * The basis of this hash algorithm was taken from an idea sent
900+ * as reviewer comments to the IEEE POSIX P1003.2 committee by:
901+ *
902+ * Phong Vo (http://www.research.att.com/info/kpv/)
903+ * Glenn Fowler (http://www.research.att.com/~gsf/)
904+ *
905+ * In a subsequent ballot round:
906+ *
907+ * Landon Curt Noll (http://www.isthe.com/chongo/)
908+ *
909+ * improved on their algorithm. Some people tried this hash
910+ * and found that it worked rather well. In an EMail message
911+ * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
912+ *
913+ * FNV hashes are designed to be fast while maintaining a low
914+ * collision rate. The FNV speed allows one to quickly hash lots
915+ * of data while maintaining a reasonable collision rate. See:
916+ *
917+ * http://www.isthe.com/chongo/tech/comp/fnv/index.html
918+ *
919+ * for more details as well as other forms of the FNV hash.
920+ *
921+ ***
922+ *
923+ * To use the recommended 64 bit FNV-1a hash, pass FNV1A_64_INIT as the
924+ * Fnv64_t hashval argument to fnv_64a_buf() or fnv_64a_str().
925+ *
926+ ***
927+ *
928+ * Please do not copyright this code. This code is in the public domain.
929+ *
930+ * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
931+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
932+ * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
933+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
934+ * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
935+ * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
936+ * PERFORMANCE OF THIS SOFTWARE.
937+ *
938+ * By:
939+ * chongo <Landon Curt Noll> /\oo/\
940+ * http://www.isthe.com/chongo/
941+ *
942+ * Share and Enjoy! :-)
943+ */
944+
945+#include <stdlib.h>
946+#include "fnv.h"
947+
948+
949+/*
950+ * FNV-1a defines the initial basis to be non-zero
951+ */
952+#if !defined(HAVE_64BIT_LONG_LONG)
953+const Fnv64_t fnv1a_64_init = { 0x84222325, 0xcbf29ce4 };
954+#endif /* ! HAVE_64BIT_LONG_LONG */
955+
956+
957+/*
958+ * 64 bit magic FNV-1a prime
959+ */
960+#if defined(HAVE_64BIT_LONG_LONG)
961+#define FNV_64_PRIME ((Fnv64_t)0x100000001b3ULL)
962+#else /* HAVE_64BIT_LONG_LONG */
963+#define FNV_64_PRIME_LOW ((unsigned long)0x1b3) /* lower bits of FNV prime */
964+#define FNV_64_PRIME_SHIFT (8) /* top FNV prime shift above 2^32 */
965+#endif /* HAVE_64BIT_LONG_LONG */
966+
967+
968+/*
969+ * fnv_64a_buf - perform a 64 bit Fowler/Noll/Vo FNV-1a hash on a buffer
970+ *
971+ * input:
972+ * buf - start of buffer to hash
973+ * len - length of buffer in octets
974+ * hval - previous hash value or 0 if first call
975+ *
976+ * returns:
977+ * 64 bit hash as a static hash type
978+ *
979+ * NOTE: To use the recommended 64 bit FNV-1a hash, use FNV1A_64_INIT as the
980+ * hval arg on the first call to either fnv_64a_buf() or fnv_64a_str().
981+ */
982+Fnv64_t
983+fnv_64a_buf(void *buf, size_t len, Fnv64_t hval)
984+{
985+ unsigned char *bp = (unsigned char *)buf; /* start of buffer */
986+ unsigned char *be = bp + len; /* beyond end of buffer */
987diff --git a/lib/fnv/have_ulong64.c b/lib/fnv/have_ulong64.c
988new file mode 100644
989index 0000000000000000000000000000000000000000..5c06262388a7afc0e62c3c61dac9e2dfcf9a13a6
990--- /dev/null
991+++ b/lib/fnv/have_ulong64.c
992@@ -0,0 +1,58 @@
993+/*
994+ * have_ulong64 - Determine if we have a 64 bit unsigned long long
995+ *
996+ * usage:
997+ * have_ulong64 > longlong.h
998+ *
999+ * Not all systems have a 'long long type' so this may not compile on
1000+ * your system.
1001+ *
1002+ * This prog outputs the define:
1003+ *
1004+ * HAVE_64BIT_LONG_LONG
1005+ * defined ==> we have a 64 bit unsigned long long
1006+ * undefined ==> we must simulate a 64 bit unsigned long long
1007+ */
1008+/*
1009+ *
1010+ * Please do not copyright this code. This code is in the public domain.
1011+ *
1012+ * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
1013+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
1014+ * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
1015+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
1016+ * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
1017+ * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
1018+ * PERFORMANCE OF THIS SOFTWARE.
1019+ *
1020+ * By:
1021+ * chongo <Landon Curt Noll> /\oo/\
1022+ * http://www.isthe.com/chongo/
1023+ *
1024+ * Share and Enjoy! :-)
1025+ */
1026+
1027+/*
1028+ * have the compiler try its hand with unsigned and signed long longs
1029+ */
1030+#if ! defined(NO64BIT_LONG_LONG)
1031+unsigned long long val = 1099511628211ULL;
1032+#endif /* NO64BIT_LONG_LONG */
1033+
1034+int
1035+main(void)
1036+{
1037+ /*
1038+ * ensure that the length of long long val is what we expect
1039+ */
1040+#if defined(NO64BIT_LONG_LONG)
1041+ printf("#undef HAVE_64BIT_LONG_LONG\t/* no */\n");
1042+#else /* NO64BIT_LONG_LONG */
1043+ if (val == 1099511628211ULL && sizeof(val) == 8) {
1044+ printf("#define HAVE_64BIT_LONG_LONG\t/* yes */\n");
1045+ }
1046+#endif /* NO64BIT_LONG_LONG */
1047+
1048+ /* exit(0); */
1049+ return 0;
1050+}
1051diff --git a/lib/fnv/longlong.h b/lib/fnv/longlong.h
1052new file mode 100644
1053index 0000000000000000000000000000000000000000..c8cfe48f29f50c9620b5f222ad445ae1004941e0
1054--- /dev/null
1055+++ b/lib/fnv/longlong.h
1056@@ -0,0 +1,18 @@
1057+/*
1058+ * DO NOT EDIT -- generated by the Makefile
1059+ */
1060+
1061+#if !defined(__LONGLONG_H__)
1062+#define __LONGLONG_H__
1063+
1064+/* do we have/want to use a long long type? */
1065+#define HAVE_64BIT_LONG_LONG /* yes */
1066+
1067+/*
1068+ * NO64BIT_LONG_LONG undef HAVE_64BIT_LONG_LONG
1069+ */
1070+#if defined(NO64BIT_LONG_LONG)
1071+#undef HAVE_64BIT_LONG_LONG
1072+#endif /* NO64BIT_LONG_LONG */
1073+
1074+#endif /* !__LONGLONG_H__ */
1075diff --git a/lib/fnv/qmk_fnv_type_validation.c b/lib/fnv/qmk_fnv_type_validation.c
1076new file mode 100644
1077index 0000000000000000000000000000000000000000..e8576617ba8b4e14bfb10833fb29bed0e7fa7aee
1078--- /dev/null
1079+++ b/lib/fnv/qmk_fnv_type_validation.c
1080@@ -0,0 +1,14 @@
1081+// Copyright 2022 Nick Brassel (@tzarc)
1082+// SPDX-License-Identifier: GPL-2.0-or-later
1083+#include "fnv.h"
1084+
1085+// This library was originally sourced from:
1086+// http://www.isthe.com/chongo/tech/comp/fnv/index.html
1087+//
1088+// Version at the time of retrieval on 2022-06-26: v5.0.3
1089+
1090+_Static_assert(sizeof(long long) == 8, "long long should be 64 bits");
1091+_Static_assert(sizeof(unsigned long long) == 8, "unsigned long long should be 64 bits");
1092+
1093+_Static_assert(sizeof(Fnv32_t) == 4, "Fnv32_t should be 32 bits");
1094+_Static_assert(sizeof(Fnv64_t) == 8, "Fnv64_t should be 64 bits");
1095diff --git a/lib/fnv/test_fnv.c b/lib/fnv/test_fnv.c
1096new file mode 100644
1097index 0000000000000000000000000000000000000000..efec3dec1da4b688ea959ac7cbd65d5550586882
1098--- /dev/null
1099+++ b/lib/fnv/test_fnv.c
1100@@ -0,0 +1,2237 @@
1101+/*
1102+ * test_fnv - FNV test suite
1103+ *
1104+ * @(#) $Revision: 5.3 $
1105+ * @(#) $Id: test_fnv.c,v 5.3 2009/06/30 11:50:41 chongo Exp $
1106+ * @(#) $Source: /usr/local/src/cmd/fnv/RCS/test_fnv.c,v $
1107+ *
1108+ ***
1109+ *
1110+ * Fowler/Noll/Vo hash
1111+ *
1112+ * The basis of this hash algorithm was taken from an idea sent
1113+ * as reviewer comments to the IEEE POSIX P1003.2 committee by:
1114+ *
1115+ * Phong Vo (http://www.research.att.com/info/kpv/)
1116+ * Glenn Fowler (http://www.research.att.com/~gsf/)
1117+ *
1118+ * In a subsequent ballot round:
1119+ *
1120+ * Landon Curt Noll (http://www.isthe.com/chongo/)
1121+ *
1122+ * improved on their algorithm. Some people tried this hash
1123+ * and found that it worked rather well. In an EMail message
1124+ * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
1125+ *
1126+ * FNV hashes are designed to be fast while maintaining a low
1127+ * collision rate. The FNV speed allows one to quickly hash lots
1128+ * of data while maintaining a reasonable collision rate. See:
1129+ *
1130+ * http://www.isthe.com/chongo/tech/comp/fnv/index.html
1131+ *
1132+ * for more details as well as other forms of the FNV hash.
1133+ *
1134+ ***
1135+ *
1136+ * Please do not copyright this code. This code is in the public domain.
1137+ *
1138+ * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
1139+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
1140+ * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
1141+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
1142+ * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
1143+ * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
1144+ * PERFORMANCE OF THIS SOFTWARE.
1145+ *
1146+ * By:
1147+ * chongo <Landon Curt Noll> /\oo/\
1148+ * http://www.isthe.com/chongo/
1149+ *
1150+ * Share and Enjoy! :-)
1151+ */
1152+
1153+#include <stdio.h>
1154+#include "longlong.h"
1155+#include "fnv.h"
1156+
1157+#define LEN(x) (sizeof(x)-1)
1158+/* TEST macro does not include trailing NUL byte in the test vector */
1159+#define TEST(x) {x, LEN(x)}
1160+/* TEST0 macro includes the trailing NUL byte in the test vector */
1161+#define TEST0(x) {x, sizeof(x)}
1162+/* REPEAT500 - repeat a string 500 times */
1163+#define R500(x) R100(x)R100(x)R100(x)R100(x)R100(x)
1164+#define R100(x) R10(x)R10(x)R10(x)R10(x)R10(x)R10(x)R10(x)R10(x)R10(x)R10(x)
1165+#define R10(x) x x x x x x x x x x
1166+
1167+/*
1168+ * FNV test vectors
1169+ *
1170+ * NOTE: A NULL pointer marks beyond the end of the test vectors.
1171+ *
1172+ * NOTE: The order of the fnv_test_str[] test vectors is 1-to-1 with:
1173+ *
1174+ * struct fnv0_32_test_vector fnv0_32_vector[];
1175+ * struct fnv1_32_test_vector fnv1_32_vector[];
1176+ * struct fnv1a_32_test_vector fnv1a_32_vector[];
1177+ * struct fnv0_64_test_vector fnv0_64_vector[];
1178+ * struct fnv1_64_test_vector fnv1_64_vector[];
1179+ * struct fnv1a_64_test_vector fnv1a_64_vector[];
1180+ *
1181+ * IMPORTANT NOTE:
1182+ *
1183+ * If you change the fnv_test_str[] array, you need
1184+ * to also change ALL of the above fnv*_vector arrays!!!
1185+ *
1186+ * To rebuild, try:
1187+ *
1188+ * make vector.c
1189+ *
1190+ * and then fold the results into the source file.
1191+ * Of course, you better make sure that the vaules
1192+ * produced by the above command are valid, otherwise
1193+ * you will be testing against invalid vectors!
1194+ */
1195+struct test_vector fnv_test_str[] = {
1196+ TEST(""),
1197+ TEST("a"),
1198+ TEST("b"),
1199+ TEST("c"),
1200diff --git a/quantum/wear_leveling/tests/backing_mocks.cpp b/quantum/wear_leveling/tests/backing_mocks.cpp
1201new file mode 100644
1202index 0000000000000000000000000000000000000000..1dbb26f8e7dd727d62bb6162cb9cbfbb27fe41e2
1203--- /dev/null
1204+++ b/quantum/wear_leveling/tests/backing_mocks.cpp
1205@@ -0,0 +1,154 @@
1206+// Copyright 2022 Nick Brassel (@tzarc)
1207+// SPDX-License-Identifier: GPL-2.0-or-later
1208+#include "gtest/gtest.h"
1209+#include "gmock/gmock.h"
1210+#include "backing_mocks.hpp"
1211+
1212+////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
1213+// Backing Store Mock implementation
1214+////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
1215+
1216+void MockBackingStore::reset_instance() {
1217+ for (auto&& e : backing_storage)
1218+ e.reset();
1219+
1220+ locked = true;
1221+
1222+ backing_erasure_count = 0;
1223+ backing_max_write_count = 0;
1224+ backing_total_write_count = 0;
1225+
1226+ backing_init_invoke_count = 0;
1227+ backing_unlock_invoke_count = 0;
1228+ backing_erase_invoke_count = 0;
1229+ backing_write_invoke_count = 0;
1230+ backing_lock_invoke_count = 0;
1231+
1232+ init_success_callback = [](std::uint64_t) { return true; };
1233+ erase_success_callback = [](std::uint64_t) { return true; };
1234+ unlock_success_callback = [](std::uint64_t) { return true; };
1235+ write_success_callback = [](std::uint64_t, std::uint32_t) { return true; };
1236+ lock_success_callback = [](std::uint64_t) { return true; };
1237+
1238+ write_log.clear();
1239+}
1240+
1241+bool MockBackingStore::init(void) {
1242+ ++backing_init_invoke_count;
1243+
1244+ if (init_success_callback) {
1245+ return init_success_callback(backing_init_invoke_count);
1246+ }
1247+ return true;
1248+}
1249+
1250+bool MockBackingStore::unlock(void) {
1251+ ++backing_unlock_invoke_count;
1252+
1253+ EXPECT_TRUE(is_locked()) << "Attempted to unlock but was not locked";
1254+ locked = false;
1255+
1256+ if (unlock_success_callback) {
1257+ return unlock_success_callback(backing_unlock_invoke_count);
1258+ }
1259+ return true;
1260+}
1261+
1262+bool MockBackingStore::erase(void) {
1263+ ++backing_erase_invoke_count;
1264+
1265+ // Erase each slot
1266+ for (std::size_t i = 0; i < backing_storage.size(); ++i) {
1267+ // Drop out of erase early with failure if we need to
1268+ if (erase_success_callback && !erase_success_callback(backing_erase_invoke_count)) {
1269+ append_log(true);
1270+ return false;
1271+ }
1272+
1273+ backing_storage[i].erase();
1274+ }
1275+
1276+ // Keep track of the erase in the write log so that we can verify during tests
1277+ append_log(true);
1278+
1279+ ++backing_erasure_count;
1280+ return true;
1281+}
1282+
1283+bool MockBackingStore::write(uint32_t address, backing_store_int_t value) {
1284+ ++backing_write_invoke_count;
1285+
1286+ // precondition: value's buffer size already matches BACKING_STORE_WRITE_SIZE
1287+ EXPECT_TRUE(address % BACKING_STORE_WRITE_SIZE == 0) << "Supplied address was not aligned with the backing store integral size";
1288+ EXPECT_TRUE(address + BACKING_STORE_WRITE_SIZE <= WEAR_LEVELING_BACKING_SIZE) << "Address would result of out-of-bounds access";
1289+ EXPECT_FALSE(is_locked()) << "Write was attempted without being unlocked first";
1290+
1291+ // Drop out of write early with failure if we need to
1292+ if (write_success_callback && !write_success_callback(backing_write_invoke_count, address)) {
1293+ return false;
1294+ }
1295+
1296+ // Write the complement as we're simulating flash memory -- 0xFF means 0x00
1297+ std::size_t index = address / BACKING_STORE_WRITE_SIZE;
1298+ backing_storage[index].set(~value);
1299+
1300+ // Keep track of the write log so that we can verify during tests
1301+ append_log(address, value);
1302+
1303+ // Keep track of the total number of writes into the backing store
1304+ ++backing_total_write_count;
1305diff --git a/quantum/wear_leveling/tests/backing_mocks.hpp b/quantum/wear_leveling/tests/backing_mocks.hpp
1306new file mode 100644
1307index 0000000000000000000000000000000000000000..e7af7895f3c8a4bc35c1464760eb378b2517a1d3
1308--- /dev/null
1309+++ b/quantum/wear_leveling/tests/backing_mocks.hpp
1310@@ -0,0 +1,210 @@
1311+// Copyright 2022 Nick Brassel (@tzarc)
1312+// SPDX-License-Identifier: GPL-2.0-or-later
1313+#pragma once
1314+#include <algorithm>
1315+#include <array>
1316+#include <cstdint>
1317+#include <cstdlib>
1318+#include <functional>
1319+#include <type_traits>
1320+#include <vector>
1321+
1322+extern "C" {
1323+#include "fnv.h"
1324+#include "wear_leveling.h"
1325+#include "wear_leveling_internal.h"
1326+};
1327+
1328+// Maximum number of mock write log entries to keep
1329+using MOCK_WRITE_LOG_MAX_ENTRIES = std::integral_constant<std::size_t, 1024>;
1330+// Complement to the backing store integral, for emulating flash erases of all bytes=0xFF
1331+using BACKING_STORE_INTEGRAL_COMPLEMENT = std::integral_constant<backing_store_int_t, ((backing_store_int_t)(~(backing_store_int_t)0))>;
1332+// Total number of elements stored in the backing arrays
1333+using BACKING_STORE_ELEMENT_COUNT = std::integral_constant<std::size_t, (WEAR_LEVELING_BACKING_SIZE / sizeof(backing_store_int_t))>;
1334+
1335+class MockBackingStoreElement {
1336+ private:
1337+ backing_store_int_t value;
1338+ std::size_t writes;
1339+ std::size_t erases;
1340+
1341+ public:
1342+ MockBackingStoreElement() : value(BACKING_STORE_INTEGRAL_COMPLEMENT::value), writes(0), erases(0) {}
1343+ void reset() {
1344+ erase();
1345+ writes = 0;
1346+ erases = 0;
1347+ }
1348+ void erase() {
1349+ if (!is_erased()) {
1350+ ++erases;
1351+ }
1352+ value = BACKING_STORE_INTEGRAL_COMPLEMENT::value;
1353+ }
1354+ backing_store_int_t get() const {
1355+ return value;
1356+ }
1357+ void set(const backing_store_int_t& v) {
1358+ EXPECT_TRUE(is_erased()) << "Attempted write at index which isn't empty.";
1359+ value = v;
1360+ ++writes;
1361+ }
1362+ std::size_t num_writes() const {
1363+ return writes;
1364+ }
1365+ std::size_t num_erases() const {
1366+ return erases;
1367+ }
1368+ bool is_erased() const {
1369+ return value == BACKING_STORE_INTEGRAL_COMPLEMENT::value;
1370+ }
1371+};
1372+
1373+struct MockBackingStoreLogEntry {
1374+ MockBackingStoreLogEntry(uint32_t address, backing_store_int_t value) : address(address), value(value), erased(false) {}
1375+ MockBackingStoreLogEntry(bool erased) : address(0), value(0), erased(erased) {}
1376+ uint32_t address = 0; // The address of the operation
1377+ backing_store_int_t value = 0; // The value of the operation
1378+ bool erased = false; // Whether the entire backing store was erased
1379+};
1380+
1381+class MockBackingStore {
1382+ private:
1383+ MockBackingStore() {
1384+ reset_instance();
1385+ }
1386+
1387+ // Type containing each of the entries and the write counts
1388+ using storage_t = std::array<MockBackingStoreElement, BACKING_STORE_ELEMENT_COUNT::value>;
1389+
1390+ // Whether the backing store is locked
1391+ bool locked;
1392+ // The actual data stored in the emulated flash
1393+ storage_t backing_storage;
1394+ // The number of erase cycles that have occurred
1395+ std::uint64_t backing_erasure_count;
1396+ // The max number of writes to an element of the backing store
1397+ std::uint64_t backing_max_write_count;
1398+ // The total number of writes to all elements of the backing store
1399+ std::uint64_t backing_total_write_count;
1400+ // The write log for the backing store
1401+ std::vector<MockBackingStoreLogEntry> write_log;
1402+
1403+ // The number of times each API was invoked
1404+ std::uint64_t backing_init_invoke_count;
1405+ std::uint64_t backing_unlock_invoke_count;
1406+ std::uint64_t backing_erase_invoke_count;
1407+ std::uint64_t backing_write_invoke_count;
1408+ std::uint64_t backing_lock_invoke_count;
1409+
1410diff --git a/quantum/wear_leveling/tests/rules.mk b/quantum/wear_leveling/tests/rules.mk
1411new file mode 100644
1412index 0000000000000000000000000000000000000000..4d7a964049653c72b78ef9e69168c349b0f74959
1413--- /dev/null
1414+++ b/quantum/wear_leveling/tests/rules.mk
1415@@ -0,0 +1,66 @@
1416+wear_leveling_common_DEFS := \
1417+ -DWEAR_LEVELING_TESTS
1418+wear_leveling_common_SRC := \
1419+ $(LIB_PATH)/fnv/qmk_fnv_type_validation.c \
1420+ $(LIB_PATH)/fnv/hash_32a.c \
1421+ $(LIB_PATH)/fnv/hash_64a.c \
1422+ $(QUANTUM_PATH)/wear_leveling/wear_leveling.c \
1423+ $(QUANTUM_PATH)/wear_leveling/tests/backing_mocks.cpp
1424+wear_leveling_common_INC := \
1425+ $(LIB_PATH)/fnv \
1426+ $(QUANTUM_PATH)/wear_leveling
1427+
1428+wear_leveling_general_DEFS := \
1429+ $(wear_leveling_common_DEFS) \
1430+ -DBACKING_STORE_WRITE_SIZE=2 \
1431+ -DWEAR_LEVELING_BACKING_SIZE=48 \
1432+ -DWEAR_LEVELING_LOGICAL_SIZE=16
1433+wear_leveling_general_SRC := \
1434+ $(wear_leveling_common_SRC) \
1435+ $(QUANTUM_PATH)/wear_leveling/tests/wear_leveling_general.cpp
1436+wear_leveling_general_INC := \
1437+ $(wear_leveling_common_INC)
1438+
1439+wear_leveling_2byte_optimized_writes_DEFS := \
1440+ $(wear_leveling_common_DEFS) \
1441+ -DBACKING_STORE_WRITE_SIZE=2 \
1442+ -DWEAR_LEVELING_BACKING_SIZE=65536 \
1443+ -DWEAR_LEVELING_LOGICAL_SIZE=32768
1444+wear_leveling_2byte_optimized_writes_SRC := \
1445+ $(wear_leveling_common_SRC) \
1446+ $(QUANTUM_PATH)/wear_leveling/tests/wear_leveling_2byte_optimized_writes.cpp
1447+wear_leveling_2byte_optimized_writes_INC := \
1448+ $(wear_leveling_common_INC)
1449+
1450+wear_leveling_2byte_DEFS := \
1451+ $(wear_leveling_common_DEFS) \
1452+ -DBACKING_STORE_WRITE_SIZE=2 \
1453+ -DWEAR_LEVELING_BACKING_SIZE=48 \
1454+ -DWEAR_LEVELING_LOGICAL_SIZE=16
1455+wear_leveling_2byte_SRC := \
1456+ $(wear_leveling_common_SRC) \
1457+ $(QUANTUM_PATH)/wear_leveling/tests/wear_leveling_2byte.cpp
1458+wear_leveling_2byte_INC := \
1459+ $(wear_leveling_common_INC)
1460+
1461+wear_leveling_4byte_DEFS := \
1462+ $(wear_leveling_common_DEFS) \
1463+ -DBACKING_STORE_WRITE_SIZE=4 \
1464+ -DWEAR_LEVELING_BACKING_SIZE=48 \
1465+ -DWEAR_LEVELING_LOGICAL_SIZE=16
1466+wear_leveling_4byte_SRC := \
1467+ $(wear_leveling_common_SRC) \
1468+ $(QUANTUM_PATH)/wear_leveling/tests/wear_leveling_4byte.cpp
1469+wear_leveling_4byte_INC := \
1470+ $(wear_leveling_common_INC)
1471+
1472+wear_leveling_8byte_DEFS := \
1473+ $(wear_leveling_common_DEFS) \
1474+ -DBACKING_STORE_WRITE_SIZE=8 \
1475+ -DWEAR_LEVELING_BACKING_SIZE=48 \
1476+ -DWEAR_LEVELING_LOGICAL_SIZE=16
1477+wear_leveling_8byte_SRC := \
1478+ $(wear_leveling_common_SRC) \
1479+ $(QUANTUM_PATH)/wear_leveling/tests/wear_leveling_8byte.cpp
1480+wear_leveling_8byte_INC := \
1481+ $(wear_leveling_common_INC)
1482diff --git a/quantum/wear_leveling/tests/testlist.mk b/quantum/wear_leveling/tests/testlist.mk
1483new file mode 100644
1484index 0000000000000000000000000000000000000000..32cfc178b4eef78554fcb4c30729a93156a225ae
1485--- /dev/null
1486+++ b/quantum/wear_leveling/tests/testlist.mk
1487@@ -0,0 +1,6 @@
1488+TEST_LIST += \
1489+ wear_leveling_general \
1490+ wear_leveling_2byte_optimized_writes \
1491+ wear_leveling_2byte \
1492+ wear_leveling_4byte \
1493+ wear_leveling_8byte
1494diff --git a/quantum/wear_leveling/tests/wear_leveling_2byte.cpp b/quantum/wear_leveling/tests/wear_leveling_2byte.cpp
1495new file mode 100644
1496index 0000000000000000000000000000000000000000..b749c32b04d4f2ca9b21dc53b18bb82c105091f5
1497--- /dev/null
1498+++ b/quantum/wear_leveling/tests/wear_leveling_2byte.cpp
1499@@ -0,0 +1,228 @@
1500+// Copyright 2022 Nick Brassel (@tzarc)
1501+// SPDX-License-Identifier: GPL-2.0-or-later
1502+#include <numeric>
1503+#include "gtest/gtest.h"
1504+#include "gmock/gmock.h"
1505+#include "backing_mocks.hpp"
1506+
1507+class WearLeveling2Byte : public ::testing::Test {
1508+ protected:
1509+ void SetUp() override {
1510+ MockBackingStore::Instance().reset_instance();
1511+ wear_leveling_init();
1512+ }
1513+};
1514+
1515+static std::array<std::uint8_t, WEAR_LEVELING_LOGICAL_SIZE> verify_data;
1516+
1517+static wear_leveling_status_t test_write(const uint32_t address, const void* value, size_t length) {
1518+ memcpy(&verify_data[address], value, length);
1519+ return wear_leveling_write(address, value, length);
1520+}
1521+
1522+/**
1523+ * This test verifies that the first write after initialisation occurs after the FNV1a_64 hash location.
1524+ */
1525+TEST_F(WearLeveling2Byte, FirstWriteOccursAfterHash) {
1526+ auto& inst = MockBackingStore::Instance();
1527+ uint8_t test_value = 0x15;
1528+ test_write(0x02, &test_value, sizeof(test_value));
1529+ EXPECT_EQ(inst.log_begin()->address, WEAR_LEVELING_LOGICAL_SIZE + 8) << "Invalid first write address.";
1530+}
1531+
1532+/**
1533+ * This test verifies that the first write after initialisation occurs after the FNV1a_64 hash location, after an erase has occurred.
1534+ */
1535+TEST_F(WearLeveling2Byte, FirstWriteOccursAfterHash_AfterErase) {
1536+ auto& inst = MockBackingStore::Instance();
1537+ uint8_t test_value = 0x15;
1538+ wear_leveling_erase();
1539+ test_write(0x02, &test_value, sizeof(test_value));
1540+ EXPECT_EQ((inst.log_begin() + 1)->address, WEAR_LEVELING_LOGICAL_SIZE + 8) << "Invalid first write address.";
1541+}
1542+
1543+/**
1544+ * This test forces consolidation by writing enough to the write log that it overflows, consolidating the data into the
1545+ * base logical area.
1546+ */
1547+TEST_F(WearLeveling2Byte, ConsolidationOverflow) {
1548+ auto& inst = MockBackingStore::Instance();
1549+
1550+ // Generate a test block of data which forces OPTIMIZED_64 writes
1551+ std::array<std::uint8_t, WEAR_LEVELING_LOGICAL_SIZE> testvalue;
1552+
1553+ // Write the data
1554+ std::iota(testvalue.begin(), testvalue.end(), 0x20);
1555+ EXPECT_EQ(test_write(0, testvalue.data(), testvalue.size()), WEAR_LEVELING_CONSOLIDATED) << "Write returned incorrect status";
1556+ uint8_t dummy = 0x40;
1557+ EXPECT_EQ(test_write(0x04, &dummy, sizeof(dummy)), WEAR_LEVELING_SUCCESS) << "Write returned incorrect status";
1558+
1559+ // All writes are at address<64, so each logical byte written will generate 1 write log entry, thus 1 backing store write.
1560+ // Expected log:
1561+ // [0..11]: optimised64, backing address 0x18, logical address 0x00
1562+ // [12]: erase
1563+ // [13..20]: consolidated data, backing address 0x00, logical address 0x00
1564+ // [21..24]: FNV1a_64 result, backing address 0x10
1565+ // [25]: optimised64, backing address 0x18, logical address 0x04
1566+ EXPECT_EQ(std::distance(inst.log_begin(), inst.log_end()), 26);
1567+
1568+ // Verify the backing store writes for the write log
1569+ std::size_t index;
1570+ write_log_entry_t e;
1571+ for (index = 0; index < 12; ++index) {
1572+ auto write_iter = inst.log_begin() + index;
1573+ EXPECT_EQ(write_iter->address, WEAR_LEVELING_LOGICAL_SIZE + 8 + (index * BACKING_STORE_WRITE_SIZE)) << "Invalid write log address";
1574+ e.raw16[0] = write_iter->value;
1575+ EXPECT_EQ(LOG_ENTRY_GET_TYPE(e), LOG_ENTRY_TYPE_OPTIMIZED_64) << "Invalid write log entry type";
1576+ }
1577+
1578+ // Verify the backing store erase
1579+ {
1580+ index = 12;
1581+ auto write_iter = inst.log_begin() + index;
1582+ e.raw16[0] = write_iter->value;
1583+ EXPECT_TRUE(write_iter->erased) << "Backing store erase did not occur as required";
1584+ }
1585+
1586+ // Verify the backing store writes for consolidation
1587+ for (index = 13; index < 21; ++index) {
1588+ auto write_iter = inst.log_begin() + index;
1589+ EXPECT_EQ(write_iter->address, (index - 13) * BACKING_STORE_WRITE_SIZE) << "Invalid write log entry address";
1590+ }
1591+
1592+ // Verify the FNV1a_64 write
1593+ {
1594+ EXPECT_EQ((inst.log_begin() + 21)->address, WEAR_LEVELING_LOGICAL_SIZE) << "Invalid write log address";
1595+ e.raw16[0] = (inst.log_begin() + 21)->value;
1596+ e.raw16[1] = (inst.log_begin() + 22)->value;
1597+ e.raw16[2] = (inst.log_begin() + 23)->value;
1598+ e.raw16[3] = (inst.log_begin() + 24)->value;
1599diff --git a/quantum/wear_leveling/tests/wear_leveling_2byte_optimized_writes.cpp b/quantum/wear_leveling/tests/wear_leveling_2byte_optimized_writes.cpp
1600new file mode 100644
1601index 0000000000000000000000000000000000000000..0b03113c89ff8ab69e29842ad03bd0a7238f026b
1602--- /dev/null
1603+++ b/quantum/wear_leveling/tests/wear_leveling_2byte_optimized_writes.cpp
1604@@ -0,0 +1,295 @@
1605+// Copyright 2022 Nick Brassel (@tzarc)
1606+// SPDX-License-Identifier: GPL-2.0-or-later
1607+#include <numeric>
1608+#include "gtest/gtest.h"
1609+#include "gmock/gmock.h"
1610+#include "backing_mocks.hpp"
1611+
1612+class WearLeveling2ByteOptimizedWrites : public ::testing::Test {
1613+ protected:
1614+ void SetUp() override {
1615+ MockBackingStore::Instance().reset_instance();
1616+ wear_leveling_init();
1617+ }
1618+};
1619+
1620+static std::array<std::uint8_t, WEAR_LEVELING_LOGICAL_SIZE> verify_data;
1621+
1622+static wear_leveling_status_t test_write(const uint32_t address, const void* value, size_t length) {
1623+ memcpy(&verify_data[address], value, length);
1624+ return wear_leveling_write(address, value, length);
1625+}
1626+
1627+/**
1628+ * This test ensures the correct number of backing store writes occurs with a multibyte write, given the input buffer size.
1629+ */
1630+TEST_F(WearLeveling2ByteOptimizedWrites, MultibyteBackingStoreWriteCounts) {
1631+ auto& inst = MockBackingStore::Instance();
1632+
1633+ for (std::size_t length = 1; length <= 5; ++length) {
1634+ // Clear things out
1635+ std::fill(verify_data.begin(), verify_data.end(), 0);
1636+ inst.reset_instance();
1637+ wear_leveling_init();
1638+
1639+ // Generate a test block of data
1640+ std::vector<std::uint8_t> testvalue(length);
1641+ std::iota(testvalue.begin(), testvalue.end(), 0x20);
1642+
1643+ // Write the data
1644+ EXPECT_EQ(test_write(2000, testvalue.data(), testvalue.size()), WEAR_LEVELING_SUCCESS) << "Write failed with incorrect status";
1645+
1646+ std::size_t expected;
1647+ if (length > 3) {
1648+ expected = 4;
1649+ } else if (length > 1) {
1650+ expected = 3;
1651+ } else {
1652+ expected = 2;
1653+ }
1654+
1655+ // Check that we got the expected number of write log entries
1656+ EXPECT_EQ(std::distance(inst.log_begin(), inst.log_end()), expected);
1657+ }
1658+}
1659+
1660+/**
1661+ * This test runs through writing U16 values of `0` or `1` over the entire logical address range, to even addresses only.
1662+ * - Addresses <16384 will result in a single optimised backing write
1663+ * - Higher addresses will result in a multibyte write of 3 backing writes
1664+ */
1665+TEST_F(WearLeveling2ByteOptimizedWrites, WriteOneThenZeroToEvenAddresses) {
1666+ auto& inst = MockBackingStore::Instance();
1667+
1668+ // Only attempt writes for each address up to a limit that would NOT force a consolidated data write.
1669+ std::size_t writes_per_loop = (MOCK_WRITE_LOG_MAX_ENTRIES::value / 6) - 1; // Worst case is 6 writes for each pair of writes of 0/1
1670+ std::size_t final_address;
1671+ for (uint32_t address = 0; address < WEAR_LEVELING_LOGICAL_SIZE; address += (writes_per_loop * 2)) {
1672+ // Clear things out
1673+ std::fill(verify_data.begin(), verify_data.end(), 0);
1674+ inst.reset_instance();
1675+ wear_leveling_init();
1676+
1677+ // Loop through all the addresses in this range
1678+ std::size_t expected = 0;
1679+ for (uint32_t offset = 0; offset < (writes_per_loop * 2); offset += 2) {
1680+ // If we're about to exceed the limit of the logical store, skip the writes
1681+ if (address + offset + 2 > WEAR_LEVELING_LOGICAL_SIZE) {
1682+ break;
1683+ }
1684+
1685+ // The default erased value of the wear-leveling cache is zero, so we write a one first, then a zero, to ensure a backing store write occurs.
1686+ uint16_t val = 1;
1687+ EXPECT_EQ(test_write(address + offset, &val, sizeof(val)), WEAR_LEVELING_SUCCESS) << "Write failed with incorrect status";
1688+ val = 0;
1689+ EXPECT_EQ(test_write(address + offset, &val, sizeof(val)), WEAR_LEVELING_SUCCESS) << "Write failed with incorrect status";
1690+
1691+ std::size_t backing_store_writes_expected = 0;
1692+ if (address + offset < 16384) {
1693+ // A U16 value of 0/1 at an even address <16384 will result in 1 backing write each, so we need 2 backing writes for 2 logical writes
1694+ backing_store_writes_expected = 2;
1695+ } else {
1696+ // All other addresses result in a multibyte write (3 backing store writes) to write two local bytes of data
1697+ backing_store_writes_expected = 6;
1698+ }
1699+
1700+ // Keep track of the total number of expected writes to the backing store
1701+ expected += backing_store_writes_expected;
1702+
1703+ // Verify we're at the correct number of writes
1704diff --git a/quantum/wear_leveling/tests/wear_leveling_4byte.cpp b/quantum/wear_leveling/tests/wear_leveling_4byte.cpp
1705new file mode 100644
1706index 0000000000000000000000000000000000000000..54482c5fe7c3a0f643486070f767ed663a76f1d5
1707--- /dev/null
1708+++ b/quantum/wear_leveling/tests/wear_leveling_4byte.cpp
1709@@ -0,0 +1,193 @@
1710+// Copyright 2022 Nick Brassel (@tzarc)
1711+// SPDX-License-Identifier: GPL-2.0-or-later
1712+#include <numeric>
1713+#include "gtest/gtest.h"
1714+#include "gmock/gmock.h"
1715+#include "backing_mocks.hpp"
1716+
1717+class WearLeveling4Byte : public ::testing::Test {
1718+ protected:
1719+ void SetUp() override {
1720+ MockBackingStore::Instance().reset_instance();
1721+ wear_leveling_init();
1722+ }
1723+};
1724+
1725+static std::array<std::uint8_t, WEAR_LEVELING_LOGICAL_SIZE> verify_data;
1726+
1727+static wear_leveling_status_t test_write(const uint32_t address, const void* value, size_t length) {
1728+ memcpy(&verify_data[address], value, length);
1729+ return wear_leveling_write(address, value, length);
1730+}
1731+
1732+/**
1733+ * This test verifies that the first write after initialisation occurs after the FNV1a_64 hash location.
1734+ */
1735+TEST_F(WearLeveling4Byte, FirstWriteOccursAfterHash) {
1736+ auto& inst = MockBackingStore::Instance();
1737+ uint8_t test_value = 0x15;
1738+ test_write(0x02, &test_value, sizeof(test_value));
1739+ EXPECT_EQ(inst.log_begin()->address, WEAR_LEVELING_LOGICAL_SIZE + 8) << "Invalid first write address.";
1740+}
1741+
1742+/**
1743+ * This test verifies that the first write after initialisation occurs after the FNV1a_64 hash location, after an erase has occurred.
1744+ */
1745+TEST_F(WearLeveling4Byte, FirstWriteOccursAfterHash_AfterErase) {
1746+ auto& inst = MockBackingStore::Instance();
1747+ uint8_t test_value = 0x15;
1748+ wear_leveling_erase();
1749+ test_write(0x02, &test_value, sizeof(test_value));
1750+ EXPECT_EQ((inst.log_begin() + 1)->address, WEAR_LEVELING_LOGICAL_SIZE + 8) << "Invalid first write address.";
1751+}
1752+
1753+/**
1754+ * This test ensures the correct number of backing store writes occurs with a multibyte write, given the input buffer size.
1755+ */
1756+TEST_F(WearLeveling4Byte, MultibyteBackingStoreWriteCounts) {
1757+ auto& inst = MockBackingStore::Instance();
1758+
1759+ for (std::size_t length = 1; length <= 5; ++length) {
1760+ // Clear things out
1761+ std::fill(verify_data.begin(), verify_data.end(), 0);
1762+ inst.reset_instance();
1763+ wear_leveling_init();
1764+
1765+ // Generate a test block of data
1766+ std::vector<std::uint8_t> testvalue(length);
1767+ std::iota(testvalue.begin(), testvalue.end(), 0x20);
1768+
1769+ // Write the data
1770+ EXPECT_EQ(test_write(0, testvalue.data(), testvalue.size()), WEAR_LEVELING_SUCCESS) << "Write failed with incorrect status";
1771+
1772+ std::size_t expected;
1773+ if (length > 1) {
1774+ expected = 2;
1775+ } else {
1776+ expected = 1;
1777+ }
1778+
1779+ // Check that we got the expected number of write log entries
1780+ EXPECT_EQ(std::distance(inst.log_begin(), inst.log_end()), expected);
1781+ }
1782+}
1783+
1784+/**
1785+ * This test forces consolidation by writing enough to the write log that it overflows, consolidating the data into the
1786+ * base logical area.
1787+ */
1788+TEST_F(WearLeveling4Byte, ConsolidationOverflow) {
1789+ auto& inst = MockBackingStore::Instance();
1790+
1791+ // Generate a test block of data
1792+ std::array<std::uint8_t, WEAR_LEVELING_LOGICAL_SIZE> testvalue;
1793+
1794+ // Write the data
1795+ std::iota(testvalue.begin(), testvalue.end(), 0x20);
1796+ EXPECT_EQ(test_write(0, testvalue.data(), testvalue.size()), WEAR_LEVELING_CONSOLIDATED) << "Write returned incorrect status";
1797+ uint8_t dummy = 0x40;
1798+ EXPECT_EQ(test_write(0x04, &dummy, sizeof(dummy)), WEAR_LEVELING_SUCCESS) << "Write returned incorrect status";
1799+
1800+ // Expected log:
1801+ // [0,1]: multibyte, 5 bytes, backing address 0x18, logical address 0x00
1802+ // [2,3]: multibyte, 5 bytes, backing address 0x20, logical address 0x05
1803+ // [4,5]: multibyte, 5 bytes, backing address 0x28, logical address 0x0A, triggers consolidation
1804+ // [6]: erase
1805+ // [7,8]: consolidated data, backing address 0x00, logical address 0x00
1806+ // [9,10]: consolidated data, backing address 0x08, logical address 0x08
1807+ // [11,12]: FNV1a_64 result, backing address 0x10
1808+ // [13]: multibyte, 1 byte, backing address 0x18, logical address 0x04
1809diff --git a/quantum/wear_leveling/tests/wear_leveling_8byte.cpp b/quantum/wear_leveling/tests/wear_leveling_8byte.cpp
1810new file mode 100644
1811index 0000000000000000000000000000000000000000..c27c21d034aae73784b845cd9d188ae569d2f099
1812--- /dev/null
1813+++ b/quantum/wear_leveling/tests/wear_leveling_8byte.cpp
1814@@ -0,0 +1,178 @@
1815+// Copyright 2022 Nick Brassel (@tzarc)
1816+// SPDX-License-Identifier: GPL-2.0-or-later
1817+#include <numeric>
1818+#include "gtest/gtest.h"
1819+#include "gmock/gmock.h"
1820+#include "backing_mocks.hpp"
1821+
1822+class WearLeveling8Byte : public ::testing::Test {
1823+ protected:
1824+ void SetUp() override {
1825+ MockBackingStore::Instance().reset_instance();
1826+ wear_leveling_init();
1827+ }
1828+};
1829+
1830+static std::array<std::uint8_t, WEAR_LEVELING_LOGICAL_SIZE> verify_data;
1831+
1832+static wear_leveling_status_t test_write(const uint32_t address, const void* value, size_t length) {
1833+ memcpy(&verify_data[address], value, length);
1834+ return wear_leveling_write(address, value, length);
1835+}
1836+
1837+/**
1838+ * This test verifies that the first write after initialisation occurs after the FNV1a_64 hash location.
1839+ */
1840+TEST_F(WearLeveling8Byte, FirstWriteOccursAfterHash) {
1841+ auto& inst = MockBackingStore::Instance();
1842+ uint8_t test_value = 0x15;
1843+ test_write(0x02, &test_value, sizeof(test_value));
1844+ EXPECT_EQ(inst.log_begin()->address, WEAR_LEVELING_LOGICAL_SIZE + 8) << "Invalid first write address.";
1845+}
1846+
1847+/**
1848+ * This test verifies that the first write after initialisation occurs after the FNV1a_64 hash location, after an erase has occurred.
1849+ */
1850+TEST_F(WearLeveling8Byte, FirstWriteOccursAfterHash_AfterErase) {
1851+ auto& inst = MockBackingStore::Instance();
1852+ uint8_t test_value = 0x15;
1853+ wear_leveling_erase();
1854+ test_write(0x02, &test_value, sizeof(test_value));
1855+ EXPECT_EQ((inst.log_begin() + 1)->address, WEAR_LEVELING_LOGICAL_SIZE + 8) << "Invalid first write address.";
1856+}
1857+
1858+/**
1859+ * This test ensures the correct number of backing store writes occurs with a multibyte write, given the input buffer size.
1860+ */
1861+TEST_F(WearLeveling8Byte, MultibyteBackingStoreWriteCounts) {
1862+ auto& inst = MockBackingStore::Instance();
1863+
1864+ for (std::size_t length = 1; length <= 5; ++length) {
1865+ // Clear things out
1866+ std::fill(verify_data.begin(), verify_data.end(), 0);
1867+ inst.reset_instance();
1868+ wear_leveling_init();
1869+
1870+ // Generate a test block of data
1871+ std::vector<std::uint8_t> testvalue(length);
1872+ std::iota(testvalue.begin(), testvalue.end(), 0x20);
1873+
1874+ // Write the data
1875+ EXPECT_EQ(test_write(0, testvalue.data(), testvalue.size()), WEAR_LEVELING_SUCCESS) << "Write failed with incorrect status";
1876+
1877+ // Check that we got the expected number of write log entries
1878+ EXPECT_EQ(std::distance(inst.log_begin(), inst.log_end()), 1);
1879+ }
1880+}
1881+
1882+/**
1883+ * This test forces consolidation by writing enough to the write log that it overflows, consolidating the data into the
1884+ * base logical area.
1885+ */
1886+TEST_F(WearLeveling8Byte, ConsolidationOverflow) {
1887+ auto& inst = MockBackingStore::Instance();
1888+
1889+ // Generate a test block of data
1890+ std::array<std::uint8_t, WEAR_LEVELING_LOGICAL_SIZE> testvalue;
1891+
1892+ // Write the data
1893+ std::iota(testvalue.begin(), testvalue.end(), 0x20);
1894+ EXPECT_EQ(test_write(0, testvalue.data(), testvalue.size()), WEAR_LEVELING_CONSOLIDATED) << "Write returned incorrect status";
1895+ uint8_t dummy = 0x40;
1896+ EXPECT_EQ(test_write(0x04, &dummy, sizeof(dummy)), WEAR_LEVELING_SUCCESS) << "Write returned incorrect status";
1897+
1898+ // Expected log:
1899+ // [0]: multibyte, 5 bytes, backing address 0x18, logical address 0x00
1900+ // [1]: multibyte, 5 bytes, backing address 0x20, logical address 0x05
1901+ // [2]: multibyte, 5 bytes, backing address 0x28, logical address 0x0A, triggers consolidation
1902+ // [3]: erase
1903+ // [4]: consolidated data, backing address 0x00, logical address 0x00
1904+ // [5]: consolidated data, backing address 0x08, logical address 0x08
1905+ // [6]: FNV1a_64 result, backing address 0x10
1906+ // [7]: multibyte, 1 byte, backing address 0x18, logical address 0x04
1907+ EXPECT_EQ(std::distance(inst.log_begin(), inst.log_end()), 8);
1908+
1909+ // Verify the backing store writes for the write log
1910+ std::size_t index;
1911+ write_log_entry_t e;
1912+ for (index = 0; index < 3; ++index) {
1913+ auto write_iter = inst.log_begin() + index;
1914diff --git a/quantum/wear_leveling/tests/wear_leveling_general.cpp b/quantum/wear_leveling/tests/wear_leveling_general.cpp
1915new file mode 100644
1916index 0000000000000000000000000000000000000000..76a4bf7bf3290395ca5fa1ca3950d53e10b8be0a
1917--- /dev/null
1918+++ b/quantum/wear_leveling/tests/wear_leveling_general.cpp
1919@@ -0,0 +1,204 @@
1920+// Copyright 2022 Nick Brassel (@tzarc)
1921+// SPDX-License-Identifier: GPL-2.0-or-later
1922+#include <numeric>
1923+#include "gtest/gtest.h"
1924+#include "gmock/gmock.h"
1925+#include "backing_mocks.hpp"
1926+
1927+class WearLevelingGeneral : public ::testing::Test {
1928+ protected:
1929+ void SetUp() override {
1930+ MockBackingStore::Instance().reset_instance();
1931+ wear_leveling_init();
1932+ }
1933+};
1934+
1935+/**
1936+ * This test verifies that even if there is consolidated data present, if the checksum doesn't match then the cache is zero'd after reading the consolidated area, but before write log is played back.
1937+ */
1938+TEST_F(WearLevelingGeneral, InvalidChecksum_ConsolidatedDataIgnored) {
1939+ auto& inst = MockBackingStore::Instance();
1940+ auto logstart = inst.storage_begin() + (WEAR_LEVELING_LOGICAL_SIZE / sizeof(backing_store_int_t));
1941+
1942+ // Generate a test block of data
1943+ std::array<std::uint8_t, WEAR_LEVELING_LOGICAL_SIZE> testvalue;
1944+ std::iota(testvalue.begin(), testvalue.end(), 0x20);
1945+
1946+ // Write the data
1947+ EXPECT_EQ(wear_leveling_write(0, testvalue.data(), testvalue.size()), WEAR_LEVELING_CONSOLIDATED) << "Write returned incorrect status";
1948+
1949+ // Invalidate the checksum
1950+ (logstart + 0)->erase();
1951+ (logstart + 1)->erase();
1952+ (logstart + 2)->erase();
1953+ (logstart + 3)->erase();
1954+
1955+ // Set up a 1-byte logical write of [0x11] at logical offset 0x01
1956+ auto entry0 = LOG_ENTRY_MAKE_OPTIMIZED_64(0x01, 0x11);
1957+ (logstart + 4)->set(~entry0.raw16[0]);
1958+
1959+ // Re-init
1960+ EXPECT_EQ(wear_leveling_init(), WEAR_LEVELING_SUCCESS) << "Init returned incorrect status";
1961+ EXPECT_EQ(wear_leveling_read(0, testvalue.data(), testvalue.size()), WEAR_LEVELING_SUCCESS) << "Failed to read";
1962+ for (int i = 0; i < WEAR_LEVELING_LOGICAL_SIZE; ++i) {
1963+ EXPECT_EQ(testvalue[i], i == 0x01 ? 0x11 : 0x00) << "Invalid readback";
1964+ }
1965+}
1966+
1967+/**
1968+ * This test verifies that writing the same data multiple times does not result in subsequent writes to the backing store.
1969+ */
1970+TEST_F(WearLevelingGeneral, SameValue_SingleBackingWrite) {
1971+ auto& inst = MockBackingStore::Instance();
1972+
1973+ uint8_t test_val = 0x14;
1974+ EXPECT_EQ(wear_leveling_write(0x02, &test_val, sizeof(test_val)), WEAR_LEVELING_SUCCESS) << "First overall write operation should have succeeded";
1975+
1976+ uint64_t invoke_count = inst.unlock_invoke_count();
1977+ uint64_t erase_count = inst.erase_invoke_count();
1978+ uint64_t write_count = inst.write_invoke_count();
1979+ uint64_t lock_count = inst.lock_invoke_count();
1980+
1981+ for (int i = 0; i < 10; ++i) {
1982+ EXPECT_EQ(wear_leveling_write(0x02, &test_val, sizeof(test_val)), WEAR_LEVELING_SUCCESS) << "Subsequent overall write operation should have succeeded";
1983+
1984+ EXPECT_EQ(inst.unlock_invoke_count(), invoke_count) << "Unlock count should match";
1985+ EXPECT_EQ(inst.erase_invoke_count(), erase_count) << "Erase count should match";
1986+ EXPECT_EQ(inst.write_invoke_count(), write_count) << "Write count should match";
1987+ EXPECT_EQ(inst.lock_invoke_count(), lock_count) << "Lock count should match";
1988+ }
1989+}
1990+
1991+/**
1992+ * This test verifies that no other invocations occur if `backing_store_init()` fails.
1993+ */
1994+TEST_F(WearLevelingGeneral, InitFailure) {
1995+ auto& inst = MockBackingStore::Instance();
1996+ inst.reset_instance(); // make sure the counters are all zero
1997+ inst.set_init_callback([](std::uint64_t count) { return false; });
1998+
1999+ EXPECT_EQ(inst.erasure_count(), 0) << "Invalid initial erase count";
2000+ EXPECT_EQ(wear_leveling_init(), WEAR_LEVELING_FAILED) << "Init should have failed";
2001+ EXPECT_EQ(inst.erasure_count(), 0) << "Invalid final erase count";
2002+
2003+ EXPECT_EQ(inst.init_invoke_count(), 1) << "Init should have been invoked once";
2004+ EXPECT_EQ(inst.unlock_invoke_count(), 0) << "Unlock should not have been invoked";
2005+ EXPECT_EQ(inst.erase_invoke_count(), 0) << "Erase should not have been invoked";
2006+ EXPECT_EQ(inst.write_invoke_count(), 0) << "Write should not have been invoked";
2007+ EXPECT_EQ(inst.lock_invoke_count(), 0) << "Lock should not have been invoked";
2008+}
2009+
2010+/**
2011+ * This test verifies that no invocations occur if the supplied address is out of range while writing.
2012+ */
2013+TEST_F(WearLevelingGeneral, WriteFailure_OOB) {
2014+ auto& inst = MockBackingStore::Instance();
2015+
2016+ uint8_t test_val = 0x14;
2017+ EXPECT_EQ(wear_leveling_write(0x21349830, &test_val, sizeof(test_val)), WEAR_LEVELING_FAILED) << "Overall write operation should have failed";
2018+
2019diff --git a/quantum/wear_leveling/wear_leveling.c b/quantum/wear_leveling/wear_leveling.c
2020new file mode 100644
2021index 0000000000000000000000000000000000000000..8418ae77bf51abc283b1a906b0628cf4962ff845
2022--- /dev/null
2023+++ b/quantum/wear_leveling/wear_leveling.c
2024@@ -0,0 +1,779 @@
2025+// Copyright 2022 Nick Brassel (@tzarc)
2026+// SPDX-License-Identifier: GPL-2.0-or-later
2027+#include <stdbool.h>
2028+#include "fnv.h"
2029+#include "wear_leveling.h"
2030+#include "wear_leveling_internal.h"
2031+
2032+/*
2033+ This wear leveling algorithm is adapted from algorithms from previous
2034+ implementations in QMK, namely:
2035+ - Artur F. (http://engsta.com/stm32-flash-memory-eeprom-emulator/)
2036+ - Yiancar -- QMK's base implementation for STM32F303
2037+ - Ilya Zhuravlev -- initial wear leveling algorithm
2038+ - Don Kjer -- increased flash density algorithm
2039+ - Nick Brassel (@tzarc) -- decoupled for use on other peripherals
2040+
2041+ At this layer, it is assumed that any reads/writes from the backing store
2042+ have a "reset state" after erasure of zero.
2043+ It is up to the backing store to perform translation of values, such as
2044+ taking the complement in order to deal with flash memory's reset value.
2045+
2046+ Terminology:
2047+
2048+ - Backing store: this is the storage area used by the wear leveling
2049+ algorithm.
2050+
2051+ - Backing size: this is the amount of storage provided by the backing
2052+ store for use by the wear leveling algorithm.
2053+
2054+ - Backing write size: this is the minimum number of bytes the backing
2055+ store can write in a single operation.
2056+
2057+ - Logical data: this is the externally-visible "emulated EEPROM" that
2058+ external subsystems "see" when performing reads/writes.
2059+
2060+ - Logical size: this is the amount of storage available for use
2061+ externally. Effectively, the "size of the EEPROM".
2062+
2063+ - Write log: this is a section of the backing store used to keep track
2064+ of modifications without overwriting existing data. This log is
2065+ "played back" on startup such that any subsequent reads are capable
2066+ of returning the latest data.
2067+
2068+ - Consolidated data: this is a section of the backing store reserved for
2069+ use for the latest copy of logical data. This is only ever written
2070+ when the write log is full -- the latest values for the logical data
2071+ are written here and the write log is cleared.
2072+
2073+ Configurables:
2074+
2075+ - BACKING_STORE_WRITE_SIZE: The number of bytes requires for a write
2076+ operation. This is defined by the capabilities of the backing store.
2077+
2078+ - WEAR_LEVELING_BACKING_SIZE: The number of bytes provided by the
2079+ backing store for use by the wear leveling algorithm. This is
2080+ defined by the capabilities of the backing store. This value must
2081+ also be at least twice the size of the logical size, as well as a
2082+ multiple of the logical size.
2083+
2084+ - WEAR_LEVELING_LOGICAL_SIZE: The number of bytes externally visible
2085+ to other subsystems performing reads/writes. This must be a multiple
2086+ of the write size.
2087+
2088+ General algorithm:
2089+
2090+ During initialization:
2091+ * The contents of the consolidated data section are read into cache.
2092+ * The contents of the write log are "played back" and update the
2093+ cache accordingly.
2094+
2095+ During reads:
2096+ * Logical data is served from the cache.
2097+
2098+ During writes:
2099+ * The cache is updated with the new data.
2100+ * A new write log entry is appended to the log.
2101+ * If the log's full, data is consolidated and the write log cleared.
2102+
2103+ Write log structure:
2104+
2105+ The first 8 bytes of the write log are a FNV1a_64 hash of the contents
2106+ of the consolidated data area, in an attempt to detect and guard against
2107+ any data corruption.
2108+
2109+ The write log follows the hash:
2110+
2111+ Given that the algorithm needs to cater for 2-, 4-, and 8-byte writes,
2112+ a variable-length write log entry is used such that the minimal amount
2113+ of storage is used based off the backing store write size.
2114+
2115+ Firstly, an empty log entry is expected to be all zeros. If the backing
2116+ store uses 0xFF for cleared bytes, it should return the complement, such
2117+ that this wear-leveling algorithm "receives" zeros.
2118+
2119+ For multi-byte writes, up to 8 bytes will be used for each log entry,
2120+ depending on the size of backing store writes:
2121+
2122+ ╔ Multi-byte Log Entry (2, 4-byte) ═╗
2123+ ║00XXXYYY║YYYYYYYY║YYYYYYYY║AAAAAAAA║
2124diff --git a/quantum/wear_leveling/wear_leveling.h b/quantum/wear_leveling/wear_leveling.h
2125new file mode 100644
2126index 0000000000000000000000000000000000000000..6641bc49b3c42c8cbd2c9542c935967079385720
2127--- /dev/null
2128+++ b/quantum/wear_leveling/wear_leveling.h
2129@@ -0,0 +1,54 @@
2130+// Copyright 2022 Nick Brassel (@tzarc)
2131+// SPDX-License-Identifier: GPL-2.0-or-later
2132+#pragma once
2133+#include <stdint.h>
2134+#include <stdlib.h>
2135+
2136+/**
2137+ * @typedef Status returned from any wear-leveling API.
2138+ */
2139+typedef enum wear_leveling_status_t {
2140+ WEAR_LEVELING_FAILED, //< Invocation failed
2141+ WEAR_LEVELING_SUCCESS, //< Invocation succeeded
2142+ WEAR_LEVELING_CONSOLIDATED //< Invocation succeeded, consolidation occurred
2143+} wear_leveling_status_t;
2144+
2145+/**
2146+ * Wear-leveling initialization
2147+ *
2148+ * @return Status of the request
2149+ */
2150+wear_leveling_status_t wear_leveling_init(void);
2151+
2152+/**
2153+ * Wear-leveling erasure.
2154+ *
2155+ * Clears the wear-leveling area, with the definition that the "reset state" of all data is zero.
2156+ *
2157+ * @return Status of the request
2158+ */
2159+wear_leveling_status_t wear_leveling_erase(void);
2160+
2161+/**
2162+ * Writes logical data into the backing store.
2163+ *
2164+ * Skips writes if there are no changes to written values. The entire written block is considered when attempting to
2165+ * determine if an overwrite should occur -- if there is any data mismatch the entire block will be written to the log,
2166+ * not just the changed bytes.
2167+ *
2168+ * @param address[in] the logical address to write data
2169+ * @param value[in] pointer to the source buffer
2170+ * @param length[in] length of the data
2171+ * @return Status of the request
2172+ */
2173+wear_leveling_status_t wear_leveling_write(uint32_t address, const void* value, size_t length);
2174+
2175+/**
2176+ * Reads logical data from the cache.
2177+ *
2178+ * @param address[in] the logical address to read data
2179+ * @param value[out] pointer to the destination buffer
2180+ * @param length[in] length of the data
2181+ * @return Status of the request
2182+ */
2183+wear_leveling_status_t wear_leveling_read(uint32_t address, void* value, size_t length);
2184diff --git a/quantum/wear_leveling/wear_leveling_internal.h b/quantum/wear_leveling/wear_leveling_internal.h
2185new file mode 100644
2186index 0000000000000000000000000000000000000000..74b43932dfde02e905b9a4dac6a155e635e74a22
2187--- /dev/null
2188+++ b/quantum/wear_leveling/wear_leveling_internal.h
2189@@ -0,0 +1,145 @@
2190+// Copyright 2022 Nick Brassel (@tzarc)
2191+// SPDX-License-Identifier: GPL-2.0-or-later
2192+#pragma once
2193+
2194+#ifdef __cplusplus
2195+# define _Static_assert static_assert
2196+#endif
2197+
2198+#include <stdint.h>
2199+#include <string.h>
2200+
2201+#if BACKING_STORE_WRITE_SIZE == 2
2202+typedef uint16_t backing_store_int_t;
2203+#elif BACKING_STORE_WRITE_SIZE == 4
2204+typedef uint32_t backing_store_int_t;
2205+#elif BACKING_STORE_WRITE_SIZE == 8
2206+typedef uint64_t backing_store_int_t;
2207+#else
2208+# error Invalid BACKING_STORE_WRITE_SIZE, needs to be 2/4/8.
2209+#endif
2210+
2211+#ifndef WEAR_LEVELING_BACKING_SIZE
2212+# error WEAR_LEVELING_BACKING_SIZE was not set.
2213+#endif
2214+
2215+#ifndef WEAR_LEVELING_LOGICAL_SIZE
2216+# error WEAR_LEVELING_LOGICAL_SIZE was not set.
2217+#endif
2218+
2219+#ifdef WEAR_LEVELING_DEBUG_OUTPUT
2220+# include <stdio.h>
2221+# define wl_dprintf(...) printf("Wear leveling: " __VA_ARGS__)
2222+# define wl_dump(address, value, length) \
2223+ do { \
2224+ printf("[0x%04X]: ", (int)(address)); \
2225+ const uint8_t* p = (const uint8_t*)(value); \
2226+ for (int i = 0; i < (length); ++i) { \
2227+ printf(" %02X", (int)p[i]); \
2228+ } \
2229+ printf("\n"); \
2230+ } while (0)
2231+#else
2232+# define wl_dprintf(...) \
2233+ do { \
2234+ } while (0)
2235+# define wl_dump(...) \
2236+ do { \
2237+ } while (0)
2238+#endif // WEAR_LEVELING_DEBUG_OUTPUT
2239+
2240+#ifdef WEAR_LEVELING_ASSERTS
2241+# include <assert.h>
2242+# define wl_assert(...) assert(__VA_ARGS__)
2243+#else
2244+# define wl_assert(...) \
2245+ do { \
2246+ } while (0)
2247+#endif // WEAR_LEVELING_ASSERTS
2248+
2249+// Compile-time validation of configurable options
2250+_Static_assert(WEAR_LEVELING_BACKING_SIZE >= (WEAR_LEVELING_LOGICAL_SIZE * 2), "Total backing size must be at least twice the size of the logical size");
2251+_Static_assert(WEAR_LEVELING_LOGICAL_SIZE % BACKING_STORE_WRITE_SIZE == 0, "Logical size must be a multiple of write size");
2252+_Static_assert(WEAR_LEVELING_BACKING_SIZE % WEAR_LEVELING_LOGICAL_SIZE == 0, "Backing size must be a multiple of logical size");
2253+
2254+// Backing Store API, to be implemented elsewhere by flash driver etc.
2255+bool backing_store_init(void);
2256+bool backing_store_unlock(void);
2257+bool backing_store_erase(void);
2258+bool backing_store_write(uint32_t address, backing_store_int_t value);
2259+bool backing_store_lock(void);
2260+bool backing_store_read(uint32_t address, backing_store_int_t* value);
2261+
2262+/**
2263+ * Helper type used to contain a write log entry.
2264+ */
2265+typedef union write_log_entry_t {
2266+ uint64_t raw64;
2267+ uint32_t raw32[2];
2268+ uint16_t raw16[4];
2269+ uint8_t raw8[8];
2270+} write_log_entry_t;
2271+
2272+_Static_assert(sizeof(write_log_entry_t) == 8, "Wear leveling write log entry size was not 8");
2273+
2274+/**
2275+ * Log entry type discriminator.
2276+ */
2277+enum {
2278+ // 0x00 -- Multi-byte storage type
2279+ LOG_ENTRY_TYPE_MULTIBYTE,
2280+
2281+ // 0x01 -- 2-byte backing store write optimization: address < 64
2282+ LOG_ENTRY_TYPE_OPTIMIZED_64,
2283+
2284+ // 0x02 -- 2-byte backing store write optimization: word-encoded 0/1 values
2285+ LOG_ENTRY_TYPE_WORD_01,
2286+
2287+ LOG_ENTRY_TYPES
2288+};