[Xen-devel] [PATCH v15 08/15] lfsr: a simple binary Galois linear feedback shift register

[Waiman Long <Waiman.Long@xxxxxx>]

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 taps that is being used. Callers can provide their own
taps value or use the default.

Signed-off-by: Waiman Long <Waiman.Long@xxxxxx>
---
 include/linux/lfsr.h |   80 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 80 insertions(+), 0 deletions(-)
 create mode 100644 include/linux/lfsr.h

diff --git a/include/linux/lfsr.h b/include/linux/lfsr.h
new file mode 100644
index 0000000..f570819
--- /dev/null
+++ b/include/linux/lfsr.h
@@ -0,0 +1,80 @@
+#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;
+}
+
+/*
+ * Please note that LFSR doesn't work with a start state of 0.
+ */
+static inline u32 lfsr(u32 val, int bits, u32 taps)
+{
+       u32 bit = val & 1;
+
+       val >>= 1;
+       if (bit)
+               val ^= taps ? taps : lfsr_taps(bits);
+       return val;
+}
+
+#endif /* _LINUX_LFSR_H */
-- 
1.7.1


_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel