[ English | Japanese ]

lfsr-generator

http://lfsr-generator.sourceforge.net/

Introduction
Download
Prerequisites
Installation
Usage
Generated Codes and Calculation Costs
Examples
Restrictions
Project page on SourceForge.net
Copyright and License
References

Introduction

lfsr-generator is a source code generator of programs, which handle state transitions of LFSRs: Linear Feedback Shift Registers.

A LFSR is a state machine, which consists of a shift register and a linear feedback function which provides an input bit from its previous state. For example, 4 bits length state variable shown as:

x[i] (x[i] = {0, 1}, i:1..4)

and a state transition function which provides a next state x'[i], defined as:

x'[i] = x[i - 1] (i: 2..4)
x'[i] = x[4] ^ x[1] (i: 1)
... `^' means XOR(exclusive-or)

They compose a LFSR, whose period (or cycle) is 2⁴ - 1. N bits length LFSR with a well-chosen feedback function can achieve 2ⁿ - 1 period. LFSRs are used as easy and fast implementations of pseudo random number generators, because the calculation cost of feedback functions of LFSRs is not relatively expensive.

lfsr-generator outputs a C source code which includes a function definition, takes a current state as an argument and returns a next state. In order to generate a source code of the LFSR described above, call as:

$ lfsr-generator --length=4 --taps=4,1 --shift-amounts=1 > shift_lfsr.c

See Usage for more details.

For more details of LFSRs, e.g. how to select well-chosen tap sequences to be used with feedback functions, a comparison between a Fibonacci LFSR and a Galois LFSR --- see References.

Prerequisites

lfsr-generator requires Perl (5.005 or later).

Source codes generated by lfsr-generator require a C compiler or a C++ compiler.

Installation

The basic way to install this package is:

$ ./configure
$ make
# make install  (as root, maybe)

Usage

The usage of the command lfsr-generator is:

usage: lfsr-generator [options]

Startup:
  -h, --help     show this help.
  -V, --version  show the version.

LFSR options:
  --config=STRING       set the configuration: `fibonacci' or `galois'.
  --length=NUMBER       set the length.
  --shift-amounts=LIST  comma-separated list of shift amounts.
  --shift-left          set the direction of shifting to left.
  --taps=LIST           comma-separated list of tap sequences.

Code options:
  --function-name=STRING       set the name of the function.
  --function-qualifier=STRING  set qualifier of the function.
  --function-template          generate a function template. (C++ only)
  --header                     equivalent to `--include-guard --prototype'.
  --include-guard              generate with an include guard.
  --includes=LIST              comma-separated list of pre-included files.
  --language=STRING            set language: `c' or `c++'.
  --namespace=STRING           set the namespace of the function. (C++ only)
  --no-extern-c-guard          remove an `extern "C"' guard.
  --prototype                  generate the prototype of the function.
  --variable-type=STRING       set variable type used in the function.

Other options:
  --no-auto      disable auto-correcting of settings.

For example, to generate the function of the LFSR whose length is 4, the tap sequences are (4, 1) and the shift amount is 1, call it like this:

$ lfsr-generator --length=4 --taps=4,1 --shift-amounts=1 > shift_lfsr.c

Then, lfsr-generator outputs a source code to the standard output.

An example of a source code of a program which calls the generated function is:

#include <stdio.h>
#include "shift_lfsr.h"

int main(void)
{
  const unsigned int init = 1;
  unsigned int v = init;
  do {
    v = shift_lfsr(v);
    putchar(((v & 1) == 0) ? '0' : '1');
  } while (v != init);
}

This program outputs a random bit sequence as a string consists of characters 0 and 1. The function shift_lfsr uses lower 4 bits of the variable v as the state of the LFSR. Initialization of the state variable must be done by the caller before calling the function: a random seed should be set to lower 4 bits of the state variable, and 0s should be set to other upper bits. In order to generate the header file shift_lfsr.h, call lfsr-generator with the option --header.

The option --config=<str> is used to select the configuration of the LFSR: Fibonacci or Galois. The default is Fibonacci.

In Fibonacci configuration, you can extend a shift amount without suffering any extra calculation cost. For example:

$ lfsr-generator --config=fibonacci \
    --length=23 --taps=23,14 --shift-amounts=8

The source code generated by this example translates a state of the LFSR forward by 8 bits each time. The calculation cost is not changed from shift-amount == 1. A caller may use lower 8 bits of a state variable as a random number, such as:

while (...) {
  v = shift_lfsr(v);
  random_bits = (v & 0xff);
  ...
}

Note that the period of the LFSR is reduced to: (2²³ - 1) / 8. In general, you can extend a shift amount up to the minimal distance of the taps.

You can also extend a shift amount without any restriction by the taps with suffering some extra calculation cost. For example:

$ lfsr-generator --config=fibonacci \
    --length=32 --taps=32,25,17,7 --shift-amounts=6,6,4

The total shift amount of this example per one function call is 16 bits. In the function, 6 bits shift, 6 bits shift and 4 bits shift will be processed. Each shift amount in the function is restricted by the taps. The calculation cost per one function call will become three times as much as the previous, but a compiler optimization may reduce the cost because the code is closed in the internal of the function.

A Galois LFSR can process without any extra calculation cost depend on the number of the taps. For example:

$ lfsr-generator --config=galois \
    --length=25 --taps=25,24,23,22,21,20,19,18,9,7,6,5,4,2 \
    --shift-amounts=1

Many taps are specified on this example but there is no extra cost: a Fibonacci form has the cost in proportion to the number of the taps. On the other hand, a Galois form cannot extend a shift amount per one function call without suffering extra cost, but a Fibonacci form can. In general, a Galois form is more efficient than a Fibonacci form if it handle a LFSR with many taps (a dense LFSR), a Fibonacci form is that if you want to get multiple random bits with a sparse LFSR oppositely.

In order to extend a shift amount per one function call with Galois LFSRs, specify the --shift-amounts option like this:

$ lfsr-generator --config=galois \
    --length=32 --taps=32,25,17,7 --shift-amounts=16

The total shift amount per one function call of this example is 16 bits: bit shift operations will be done 16 times repeatedly in the function.

See Generated Codes and Calculation Costs for more details.

The option --shift-left is used to change the direction of shifting in the function to left. The default is right. For example, values of the 8 bits width state variable, with the Fibonacci LFSR whose length is 4, the tap sequences are (4, 1), the shift amount is 1 and the direction of shifting is right are:

The values with shifting left are:

Lower 4 bits of the state variable are used as the state of the LFSR on both shifting right and shifting left. With shifting left, other upper bits are the history of older states of the LFSR, while upper bits are always 0 with shifting right. Bits larger than the length of the LFSR can be used as a random number. For example:

$ lfsr-generator --shift-left \
    --length=31 --taps=31,18 --shift-amounts=12,12,8

The length of the LFSR of this example is 31 and total shift amount per one function call of it is 32. A caller can use lower 32 bits of the state variable as a random number.

Generated Codes and Calculation Costs

Part of the generated code of the Fibonacci LFSR whose length is 4, the tap sequences are (4, 1) and the shift amount is 1 is:

unsigned int shift_lfsr(unsigned int v)
{
  enum {
    length         = 4,
    tap_0          = 4,
    tap_1          = 1,
    shift_amount_0 = 1
  };
  typedef unsigned int T;
  const T zero = (T)(0);
  v = (
    (
      v >> shift_amount_0
    ) | (
      (
        (v << (tap_0 - shift_amount_0)) ^
        (v << (tap_1 - shift_amount_0))
      ) & (
        ~(~zero << shift_amount_0) << (length - shift_amount_0)
      )
    )
  );
  return v;
}

The disassembled code of the compiled object of it for i686 architecture with Gcc is:

push   %ebp
mov    %esp,%ebp
mov    0x8(%ebp),%edx
pop    %ebp
lea    0x0(,%edx,8),%eax
xor    %edx,%eax
and    $0x8,%eax
shr    %edx
or     %edx,%eax
ret

The generated code and the disassembled code of the Galois LFSR whose settings are almost all the same as the above Fibonacci LFSR are:

unsigned int shift_lfsr(unsigned int v)
{
  enum {
    length = 4,
    tap_0  = 4,
    tap_1  = 1
  };
  typedef unsigned int T;
  const T zero = (T)(0);
  const T lsb = zero + (T)(1);
  const T feedback = (
    (lsb << (tap_0 - 1)) ^
    (lsb << (tap_1 - 1))
  );
  v = (v >> 1) ^ ((zero - (v & lsb)) & feedback);
  return v;
}

push   %ebp
mov    %esp,%ebp
mov    0x8(%ebp),%edx
pop    %ebp
mov    %edx,%eax
and    $0x1,%eax
neg    %eax
and    $0x9,%eax
shr    %edx
xor    %edx,%eax
ret

In general, required operations to the one shift calculation of the Fibonacci LFSR or the Galois LFSR are:

Fibonacci

immediate SHIFT to a variable x num-of-taps

XOR to 2 variables x (num-of-taps - 1)

immediate AND to a variable x 1

immediate SHIFT to a variable x 1

OR to 2 variables x 1
Galois

1-bit SHIFT to a variable x 1

immediate SHIFT to a variable x 1 (only for --shift-left)

UNARY-NEGATE to a variable x 1

immediate AND to a variable x 2

XOR to 2 variables x 1

Examples

An 8 bits width random number generator, (2³¹ - 1) / 8 period, fast:

$ lfsr-generator --config=fibonacci \
    --length=31 --taps=31,18 --shift-amounts=8 \
    --variable-type='unsigned int'

A 16 bits width random number generator, (2³¹ - 1) / 16 period, fast:

$ lfsr-generator --config=fibonacci \
    --length=31 --taps=31,18 --shift-amounts=8,8 \
    --variable-type='unsigned int'

A 32 bits width random number generator, (2³¹ - 1) / 32 period, fast:

$ lfsr-generator --config=fibonacci --shift-left \
    --length=31 --taps=31,18 --shift-amounts=12,12,8 \
    --variable-type='unsigned int'

An 8 bits width random number generator, (2³² - 1) / 8 period, dense taps:

$ lfsr-generator --config=galois \
    --length=32 --shift-amounts=8 \
    --taps=32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,4,3,2 \
    --variable-type='unsigned int'

An 8 bits width random number generator, using uint32_t:

$ lfsr-generator --config=fibonacci \
    --length=31 --taps=31,18 --shift-amounts=8 \
    --variable-type='uint32_t' --includes='<stdint.h>'

Generating a header file:

$ lfsr-generator --header --variable-type='unsigned int'

An 8 bits width random number generator, using inline-function, function-template and namespace:

$ lfsr-generator --config=fibonacci \
    --length=31 --taps=31,18 --shift-amounts=8 \
    --function-qualifier='inline' --function-template --namespace='lfsr'

"Applied Cryptography", Bruce Schneier
Linear feedback shift register - Wikipedia

immediate SHIFT to a variable	x	num-of-taps
XOR to 2 variables	x	(num-of-taps - 1)
immediate AND to a variable	x	1
immediate SHIFT to a variable	x	1
OR to 2 variables	x	1

1-bit SHIFT to a variable	x	1
immediate SHIFT to a variable	x	1 (only for --shift-left)
UNARY-NEGATE to a variable	x	1
immediate AND to a variable	x	2
XOR to 2 variables	x	1