[PATCH] lfsr: a simple binary Galois linear feedback shift register
From: Waiman Long
Date: Tue Mar 31 2015 - 13:29:19 EST
This patch is based on the code sent out by Peter Zijstra as part
of his queue spinlock patch to provide a hashing function with open
addressing. The lfsr() function can be used to return a sequence of
numbers that cycle through all the bit patterns (2^n -1) of a given
bit width n except the value 0 in a somewhat random fashion depending
on the LFSR tap that is being used.
This code should be a standalone patch and not part of a larger
patch series. I have also modified and extended it and added some
testing code to verify the correctness of the taps that are being used.
Signed-off-by: Waiman Long <Waiman.Long@xxxxxx>
---
include/linux/lfsr.h | 84 ++++++++++++++++++++++++++++++
tools/testing/selftests/lfsr/Makefile | 11 ++++
tools/testing/selftests/lfsr/test-lfsr.c | 70 +++++++++++++++++++++++++
3 files changed, 165 insertions(+), 0 deletions(-)
create mode 100644 include/linux/lfsr.h
create mode 100644 tools/testing/selftests/lfsr/Makefile
create mode 100644 tools/testing/selftests/lfsr/test-lfsr.c
diff --git a/include/linux/lfsr.h b/include/linux/lfsr.h
new file mode 100644
index 0000000..3e2a168
--- /dev/null
+++ b/include/linux/lfsr.h
@@ -0,0 +1,84 @@
+#ifndef _LINUX_LFSR_H
+#define _LINUX_LFSR_H
+
+/*
+ * Simple Binary Galois Linear Feedback Shift Register
+ *
+ * http://en.wikipedia.org/wiki/Linear_feedback_shift_register
+ *
+ * This function only currently supports only bits values of 4-30. Callers
+ * that doesn't pass in a constant bits value can optionally define
+ * LFSR_MIN_BITS and LFSR_MAX_BITS before including the lfsr.h header file
+ * to reduce the size of the jump table in the compiled code, if desired.
+ */
+#ifndef LFSR_MIN_BITS
+#define LFSR_MIN_BITS 4
+#endif
+
+#ifndef LFSR_MAX_BITS
+#define LFSR_MAX_BITS 30
+#endif
+
+static __always_inline u32 lfsr_taps(int bits)
+{
+ BUG_ON((bits < LFSR_MIN_BITS) || (bits > LFSR_MAX_BITS));
+ BUILD_BUG_ON((LFSR_MIN_BITS < 4) || (LFSR_MAX_BITS > 30));
+
+#define _IF_BITS_EQ(x) \
+ if (((x) >= LFSR_MIN_BITS) && ((x) <= LFSR_MAX_BITS) && ((x) == bits))
+
+ /*
+ * Feedback terms copied from
+ * http://users.ece.cmu.edu/~koopman/lfsr/index.html
+ */
+ _IF_BITS_EQ(4) return 0x0009;
+ _IF_BITS_EQ(5) return 0x0012;
+ _IF_BITS_EQ(6) return 0x0021;
+ _IF_BITS_EQ(7) return 0x0041;
+ _IF_BITS_EQ(8) return 0x008E;
+ _IF_BITS_EQ(9) return 0x0108;
+ _IF_BITS_EQ(10) return 0x0204;
+ _IF_BITS_EQ(11) return 0x0402;
+ _IF_BITS_EQ(12) return 0x0829;
+ _IF_BITS_EQ(13) return 0x100D;
+ _IF_BITS_EQ(14) return 0x2015;
+ _IF_BITS_EQ(15) return 0x4122;
+ _IF_BITS_EQ(16) return 0x8112;
+ _IF_BITS_EQ(17) return 0x102C9;
+ _IF_BITS_EQ(18) return 0x20195;
+ _IF_BITS_EQ(19) return 0x403FE;
+ _IF_BITS_EQ(20) return 0x80637;
+ _IF_BITS_EQ(21) return 0x100478;
+ _IF_BITS_EQ(22) return 0x20069E;
+ _IF_BITS_EQ(23) return 0x4004B2;
+ _IF_BITS_EQ(24) return 0x800B87;
+ _IF_BITS_EQ(25) return 0x10004F3;
+ _IF_BITS_EQ(26) return 0x200072D;
+ _IF_BITS_EQ(27) return 0x40006AE;
+ _IF_BITS_EQ(28) return 0x80009E3;
+ _IF_BITS_EQ(29) return 0x10000583;
+ _IF_BITS_EQ(30) return 0x20000C92;
+#undef _IF_BITS_EQ
+
+ /* Unreachable */
+ return 0;
+}
+
+static inline u32 lfsr(u32 val, int bits)
+{
+ u32 bit = val & 1;
+
+ /*
+ * LFSR doesn't work with a start state of 0, so force it to a
+ * non-zero value (bits) as the next state.
+ */
+ if (val == 0)
+ return bits;
+
+ val >>= 1;
+ if (bit)
+ val ^= lfsr_taps(bits);
+ return val;
+}
+
+#endif /* _LINUX_LFSR_H */
diff --git a/tools/testing/selftests/lfsr/Makefile b/tools/testing/selftests/lfsr/Makefile
new file mode 100644
index 0000000..62a4ae4
--- /dev/null
+++ b/tools/testing/selftests/lfsr/Makefile
@@ -0,0 +1,11 @@
+# Makefile for lfsr self test
+
+CFLAGS += -O -I../../../../include/
+
+all: run-test
+
+run-test: test-lfsr
+ @./test-lfsr -v
+
+clean:
+ @rm -f test-lfsr test-lfsr.[so]
diff --git a/tools/testing/selftests/lfsr/test-lfsr.c b/tools/testing/selftests/lfsr/test-lfsr.c
new file mode 100644
index 0000000..156c643
--- /dev/null
+++ b/tools/testing/selftests/lfsr/test-lfsr.c
@@ -0,0 +1,70 @@
+/*
+ * Test the correctness of the lfsr.h header file.
+ * Usage: test-lfsr [-v]
+ */
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/types.h>
+
+typedef unsigned int u32;
+#define BUG_ON(x)
+#define BUILD_BUG_ON(x)
+#include <linux/lfsr.h>
+
+int verbose;
+
+int main(int argc, char **argv)
+{
+ int bit, value, initvalue, count, limit;
+ char errbuf[256];
+
+ if ((argc > 1) && (strncmp(argv[1], "-v", 2) == 0))
+ verbose++;
+ for (bit = LFSR_MIN_BITS; bit <= LFSR_MAX_BITS; bit++) {
+ if (verbose)
+ printf("Checking %2d-bit value cycling ...", bit);
+ /*
+ * Test 1: an input value of 0 should give an non-zero output
+ */
+ initvalue = lfsr(0, bit);
+ if (initvalue == 0) {
+ snprintf(errbuf, sizeof(errbuf),
+ "lfsr(0, %d) returns 0!", bit);
+ goto err_exit;
+ }
+ /*
+ * Test 2: successive calls to lfsr() should cycle through
+ * (2^bit - 1) different values before going back
+ * to the initial value.
+ */
+ count = 0;
+ value = initvalue;
+ limit = (1U << bit) - 1;
+ do {
+ value = lfsr(value, bit);
+ if (++count > limit) {
+ snprintf(errbuf, sizeof(errbuf),
+ "lfsr(*,%d) doesn't return to initial "
+ "value %d", bit, initvalue);
+ goto err_exit;
+ }
+ } while (value != initvalue);
+
+ if (count != limit) {
+ snprintf(errbuf, sizeof(errbuf),
+ "lfsr(*, %d) cycles through only 0x%x "
+ "different values!", bit, count);
+ goto err_exit;
+ }
+ if (verbose)
+ printf(" done.\n");
+ }
+ if (verbose)
+ printf("lfsr check completed successfully.\n");
+ return 0;
+
+err_exit:
+ fflush(stdout);
+ fprintf(stderr, "\nError: %s\n", errbuf);
+ exit(1);
+}
--
1.7.1
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/