Skip to contentSkip to conversation

lfsr: a simple binary Galois linear feedback shift register

PATCH In review Waiman Long 3 participants 11 messages Mar 31, 2015 – Apr 1, 2015 Kselftest

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 lfsr: a simple binary Galois linear feedback shift register

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.

---
 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
include/linux/lfsr.h new file +84 -0
new file mode 100644
index 0000000..3e2a168
@@ -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 */
tools/testing/selftests/lfsr/Makefile new file +11 -0
new file mode 100644
index 0000000..62a4ae4
@@ -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]
tools/testing/selftests/lfsr/test-lfsr.c new file +70 -0

70 lines not on this page · raw message

Signature · 1 line
1.7.1
#1 lore raw
Quoted 6 lines · Waiman Long

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.

Does this new test intended to test a new kernel feature? If so could you please include what it tests in the commit log. It isn't very clear to me what this test does?

Quoted 4 lines

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.

The above can be left out of the commit log.

Quoted 10 lines
---
 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

I don't see the test added to selftests/Makefile? Is it the intent to leave it out of default test run and install? If this test is intended to be part of selftests run and install, please add it to selftests Makefile and also add install target support. You can find good examples in linux-kselftest next branch. Please add a .gitignore for git to ignore the binaries built.

thanks,
-- Shuah

Quoted 22 lines
include/linux/lfsr.h new file +15 -0
new file mode 100644
index 0000000..3e2a168
@@ -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

include/linux/lfsr.h line 25

Quoted 10 lines
include/linux/lfsr.h new file +10 -0
+#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));

Aren't these kernel defines?

Quoted 153 lines
include/linux/lfsr.h new file +59 -0
+
+#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 */
tools/testing/selftests/lfsr/Makefile new file +11 -0
new file mode 100644
index 0000000..62a4ae4
@@ -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]
tools/testing/selftests/lfsr/test-lfsr.c new file +70 -0
new file mode 100644
index 0000000..156c643
@@ -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);
+}
Signature · 5 lines
Shuah Khan
Sr. Linux Kernel Developer
Open Source Innovation Group
Samsung Research America (Silicon Valley)
[email protected] | (970) 217-8978
#2 lore raw
Quoted 11 lines · Shuah Khan
Quoted 6 lines · Waiman Long

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.

Does this new test intended to test a new kernel feature? If so could you please include what it tests in the commit log. It isn't very clear to me what this test does?

This test is for checking the correctness of the lfsr.h header file. I will clarify that in the commit log.

Quoted 5 lines
Quoted 3 lines

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.

The above can be left out of the commit log.

Sure.

Quoted 16 lines
Quoted 9 lines
---
  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

I don't see the test added to selftests/Makefile? Is it the intent to leave it out of default test run and install? If this test is intended to be part of selftests run and install, please add it to selftests Makefile and also add install target support. You can find good examples in linux-kselftest next branch. Please add a .gitignore for git to ignore the binaries built.

Quoted 4 lines

thanks,
-- Shuah

Yes, it is intended to be left out of the default selftest run and install because the lfsr.h header is for kernel internal use and is not accessible from any of the kernel syscall APIs.

Thanks,
Longman

#3 lore raw
Quoted 42 lines · Waiman Long
Quoted 11 lines · Shuah Khan
Quoted 6 lines · Waiman Long

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.

Does this new test intended to test a new kernel feature? If so could you please include what it tests in the commit log. It isn't very clear to me what this test does?

This test is for checking the correctness of the lfsr.h header file. I will clarify that in the commit log.

Quoted 5 lines
Quoted 3 lines

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.

The above can be left out of the commit log.

Sure.

Quoted 18 lines
Quoted 11 lines
---
  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

I don't see the test added to selftests/Makefile? Is it the intent to leave it out of default test run and install? If this test is intended to be part of selftests run and install, please add it to selftests Makefile and also add install target support. You can find good examples in linux-kselftest next branch. Please add a .gitignore for git to ignore the binaries built.

Quoted 9 lines
Quoted 4 lines

thanks,
-- Shuah

Yes, it is intended to be left out of the default selftest run and install because the lfsr.h header is for kernel internal use and is not accessible from any of the kernel syscall APIs.

Please add this to the commit log as well that it shouldn't be included in the default run and install. Also BUG_ON and BUILD_BUG_ON are used in this test. These are kernel defines, hope these are included somehow.

-- Shuah

Signature · 5 lines
Shuah Khan
Sr. Linux Kernel Developer
Open Source Innovation Group
Samsung Research America (Silicon Valley)
[email protected] | (970) 217-8978
#4 lore raw
Quoted 49 lines · Shuah Khan
Quoted 40 lines · Waiman Long
Quoted 11 lines · Shuah Khan
Quoted 6 lines · Waiman Long

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.

Does this new test intended to test a new kernel feature? If so could you please include what it tests in the commit log. It isn't very clear to me what this test does?

This test is for checking the correctness of the lfsr.h header file. I will clarify that in the commit log.

Quoted 5 lines
Quoted 3 lines

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.

The above can be left out of the commit log.

Sure.

Quoted 18 lines
Quoted 11 lines
---
   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

I don't see the test added to selftests/Makefile? Is it the intent to leave it out of default test run and install? If this test is intended to be part of selftests run and install, please add it to selftests Makefile and also add install target support. You can find good examples in linux-kselftest next branch. Please add a .gitignore for git to ignore the binaries built.

Quoted 8 lines
Quoted 4 lines

thanks,
-- Shuah

Yes, it is intended to be left out of the default selftest run and install because the lfsr.h header is for kernel internal use and is not accessible from any of the kernel syscall APIs.

Quoted 6 lines

Please add this to the commit log as well that it shouldn't be included in the default run and install. Also BUG_ON and BUILD_BUG_ON are used in this test. These are kernel defines, hope these are included somehow.

-- Shuah

I will update the patch once I receive feedbacks from others. The lfsr.h header does use BUG_ON and BUILD_BUG_ON, but they are disabled in the self-test.

-Longman

#5 lore raw
In reply to Waiman Long
Quoted 9 lines · Waiman Long

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.

Yeah, except we don't merge code without users, which is why such stuff typically gets a lift on the larger series you mention.

#6 lore raw
Quoted 8 lines · Peter Zijlstra
Quoted 7 lines · Waiman Long

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.

Quoted 4 lines
Quoted 2 lines

This code should be a standalone patch and not part of a larger patch series.

Yeah, except we don't merge code without users, which is why such stuff typically gets a lift on the larger series you mention.

OK, if that is the case, I will embedded it in the qspinlock series.

-Longman

#7 lore raw
In reply to Waiman Long

include/linux/lfsr.h line 76

Quoted 12 lines · Waiman Long
include/linux/lfsr.h new file +11 -0
+static __always_inline u32 lfsr_taps(int bits)
 
+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;

Arguably this should be a debug/warn instead of a silent modification.

include/linux/lfsr.h line 82

Quoted 5 lines
include/linux/lfsr.h new file +5 -0
+	val >>= 1;
+	if (bit)
+		val ^= lfsr_taps(bits);
+	return val;
+}

I was also thinking that if we modify the hash to be dynamically signed we cannot use the compile time tap selection and need to change the interface slightly.

#8 lore raw
Quoted 13 lines · Peter Zijlstra

include/linux/lfsr.h line 76

Quoted 11 lines · Waiman Long
include/linux/lfsr.h new file +11 -0
+static __always_inline u32 lfsr_taps(int bits)
+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;

Arguably this should be a debug/warn instead of a silent modification.

Since it is used in conjunction with hashing, it is possible that hashing can produce a value of 0. Do we really want to have a warning for that? Alternatively, we can pass in some flag to decide if a warning should be issued.

Quoted 8 lines

include/linux/lfsr.h line 82

Quoted 5 lines
include/linux/lfsr.h new file +5 -0
+	val>>= 1;
+	if (bit)
+		val ^= lfsr_taps(bits);
+	return val;
+}

I was also thinking that if we modify the hash to be dynamically signed we cannot use the compile time tap selection and need to change the interface slightly.

So you mean having another argument for the caller to pass in the tap value instead of using the default. Right?

-Longman

#9 lore raw
Quoted 15 lines · Waiman Long
Quoted 13 lines · Peter Zijlstra

include/linux/lfsr.h line 76

Quoted 11 lines · Waiman Long
include/linux/lfsr.h new file +11 -0
+static __always_inline u32 lfsr_taps(int bits)
+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;

Arguably this should be a debug/warn instead of a silent modification.

Quoted 4 lines

Since it is used in conjunction with hashing, it is possible that hashing can produce a value of 0. Do we really want to have a warning for that? Alternatively, we can pass in some flag to decide if a warning should be issued.

So if we present it as generic code we cannot assume what it'll be used for. The only thing we know is that it should never be 0, so warn for it and let the user deal with it.

Quoted 11 lines
Quoted 8 lines

include/linux/lfsr.h line 82

Quoted 5 lines
include/linux/lfsr.h new file +5 -0
+	val>>= 1;
+	if (bit)
+		val ^= lfsr_taps(bits);
+	return val;
+}

I was also thinking that if we modify the hash to be dynamically signed we cannot use the compile time tap selection and need to change the interface slightly.

So you mean having another argument for the caller to pass in the tap value instead of using the default. Right?

Yah, and we can still construct this version by doing:

  lfsr(val, lfsr_taps(bits));
#10 lore raw
Quoted 9 lines · Peter Zijlstra
Quoted 5 lines

Since it is used in conjunction with hashing, it is possible that hashing can produce a value of 0. Do we really want to have a warning for that? Alternatively, we can pass in some flag to decide if a warning should be issued.

So if we present it as generic code we cannot assume what it'll be used for. The only thing we know is that it should never be 0, so warn for it and let the user deal with it.

Also while i like the lfsr probe i feel we should listen to my wiser self and go with a simpler linear probe first. Only of we find prpblems with that should we look into different things.