Skip to content

Proposed LFSR implementation

Alex Pyrgiotis fio 1 version New

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest2 patches 0 repliesNew

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/2Improve LFSR implementationfilesetup.c lib/lfsr.c lib/lfsr.h +1 more+198 -2390 replies
2/2Add a simple test for LFSR generatorMakefile t/lfsr-test.c+136 -00 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [PATCH 0/2] Proposed LFSR implementation

Hi Jens and list,

Due to the open-source nature of fio, I figured I'd share with you something I've created while working on Archipelago[1], a storage backend for synnefo[2] VMs.

We wanted to have an entity that can do random permutations fast, so we've created an XNOR Galois LFSR (more details about the implementation in the following patches) that should perform "better" than the generic one for I/O related tasks.

By "better", I don't mean only in terms of speed - since by definition LFSRs are insanely fast - but also in terms of their properties as PRNGs. The main issue with LFSRs that can't make them a serious candidate for I/O tasks is that due to their shifting nature, they cannot produce a sequence of numbers that differs widely from one to the next. This implementation should tackle this problem and should make LFSRs promising candidates at least for randrepeat jobs.

I actually went one step further and tested this implementation against the TESTU01 suite. A generic LFSR fails all the tests as expected, but this LFSR passes 3 to 5 out the 10 entry level tests of the suite. This shows that they are far from suitable as stand-alone PRNGs for cryptography, but should be pretty decent for I/O tasks.

Anyways, hopefully you will find this patch set interesting for inclusion in your code. If you have any questions, feel free to ask.

Thanks,
Alex

[1] http://synnefo-software.blogspot.gr/2013/02/we-are-happy-to-announce-that-synnefo_11.html
[2] http://www.synnefo.org/
[3] http://www.iro.umontreal.ca/~simardr/testu01/tu01.html

Alex Pyrgiotis (2):
Improve LFSR implementation
Add a simple test for LFSR generator

 Makefile      |   9 ++
 filesetup.c   |   2 +-
 lib/lfsr.c    | 421 ++++++++++++++++++++++++++--------------------------------
 lib/lfsr.h    |  12 +-
 t/axmap.c     |   2 +-
 t/lfsr-test.c | 127 ++++++++++++++++++
 6 files changed, 334 insertions(+), 239 deletions(-)
 create mode 100644 t/lfsr-test.c
Signature · 1 line
1.8.1.4