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

[Shuah Khan <shuahkh@osg.samsung.com>]

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