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.l...@hp.com> --- 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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
