[PATCH] lfsr: a simple binary Galois linear feedback shift register

[PATCH] lfsr: a simple binary Galois linear feedback shift register

[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.  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@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

Re: [PATCH] lfsr: a simple binary Galois linear feedback shift register

[Shuah Khan]

On 03/31/2015 11:28 AM, Waiman Long wrote:
> 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 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.

> 
> Signed-off-by: Waiman Long <Waiman.Long@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

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

> 
> 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));

Aren't these kernel defines?

> +
> +#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);
> +}
> 


-- 
Shuah Khan
Sr. Linux Kernel Developer
Open Source Innovation Group
Samsung Research America (Silicon Valley)
shuahkh@osg.samsung.com | (970) 217-8978

Re: [PATCH] lfsr: a simple binary Galois linear feedback shift register

[Waiman Long]

On 03/31/2015 03:21 PM, Shuah Khan wrote:
> On 03/31/2015 11:28 AM, Waiman Long wrote:
>> 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.

>> 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.

>> Signed-off-by: Waiman Long<Waiman.Long@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
> 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
>
>

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

Re: [PATCH] lfsr: a simple binary Galois linear feedback shift register

[Shuah Khan]

On 03/31/2015 03:53 PM, Waiman Long wrote:
> On 03/31/2015 03:21 PM, Shuah Khan wrote:
>> On 03/31/2015 11:28 AM, Waiman Long wrote:
>>> 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.
> 
>>> 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.
> 
>>> Signed-off-by: Waiman Long<Waiman.Long@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
>> 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
>>
>>
> 
> 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

-- 
Shuah Khan
Sr. Linux Kernel Developer
Open Source Innovation Group
Samsung Research America (Silicon Valley)
shuahkh@osg.samsung.com | (970) 217-8978

Re: [PATCH] lfsr: a simple binary Galois linear feedback shift register

[Waiman Long]

On 03/31/2015 05:58 PM, Shuah Khan wrote:
> On 03/31/2015 03:53 PM, Waiman Long wrote:
>> On 03/31/2015 03:21 PM, Shuah Khan wrote:
>>> On 03/31/2015 11:28 AM, Waiman Long wrote:
>>>> 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.
>>
>>>> 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.
>>
>>>> Signed-off-by: Waiman Long<Waiman.Long@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
>>> 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
>>>
>>>
>> 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
>

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

Re: [PATCH] lfsr: a simple binary Galois linear feedback shift register

[Peter Zijlstra]

On Tue, Mar 31, 2015 at 01:28:09PM -0400, Waiman Long wrote:
> 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.

Re: [PATCH] lfsr: a simple binary Galois linear feedback shift register

[Peter Zijlstra]

On Tue, Mar 31, 2015 at 01:28:09PM -0400, Waiman Long wrote:
> +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.

> +	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.

Re: [PATCH] lfsr: a simple binary Galois linear feedback shift register

[Waiman Long]

On 04/01/2015 03:45 AM, Peter Zijlstra wrote:
> On Tue, Mar 31, 2015 at 01:28:09PM -0400, Waiman Long wrote:
>> 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.

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

-Longman

Re: [PATCH] lfsr: a simple binary Galois linear feedback shift register

[Waiman Long]

On 04/01/2015 03:53 AM, Peter Zijlstra wrote:
> On Tue, Mar 31, 2015 at 01:28:09PM -0400, Waiman Long wrote:
>> +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.

>> +	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

Re: [PATCH] lfsr: a simple binary Galois linear feedback shift register

[Peter Zijlstra]

On Wed, Apr 01, 2015 at 10:15:59AM -0400, Waiman Long wrote:
> On 04/01/2015 03:53 AM, Peter Zijlstra wrote:
> >On Tue, Mar 31, 2015 at 01:28:09PM -0400, Waiman Long wrote:
> >>+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.

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.

> >>+	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));

Re: [PATCH] lfsr: a simple binary Galois linear feedback shift register

[Peter Zijlstra]

On Wed, Apr 01, 2015 at 06:46:32PM +0200, Peter Zijlstra wrote:
> > 
> > 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.