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


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/