Linear Feedback Shift Register in Clojure
Clojure C Ruby Shell
Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
examples
src/com/github/kyleburton/clj_lfsr
test/com/github/kyleburton/clj_lfsr
util
.gitignore
README.textile
project.clj
run-example.sh

README.textile

clj-lfsr

This branch is for Clojure 1.3 support. All clj-lfsr versions released from this branch shall have a 1.3.x version numbering scheme. Clojure 1.2 support will be on the clojure-1.2 branch.

Overview

Linear Feedback Shift Register library for Clojure.

Wikipedia describes LFSRs as:

A linear feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.

It describes their uses as:

Applications of LFSRs include generating pseudo-random numbers, pseudo-noise sequences, fast digital counters, and whitening sequences.

The article also goes on to explain that there is an interesting class of LFSRs that have maximal length, called m-sequences. The interesting property is that for a given width (number of bits), the set of taps produces all possible permutations of bits, once and only once. This means they will enumerate all the possible bit permutations (with the exception of all zeros), though not in a monotonically increasing sequence (eg: 1, 2, 3, …, n).

Thus they can be used for situations where you want what looks like a random sequence, but is in fact an enumeration. An example would be assigning ids for users on your website by enumerating identifiers using the LFSR.

Usage

You can find this script in examples/test.clj:

(ns test
  (:require
   [clj-lfsr.core :as lfsr]))

(def *lfsr*
     (atom
      (let [lfsr-cfg (clj-lfsr.taps/lfsr-for-bit-size 34 4)]
        (lfsr/lfsr
         1
         (:taps lfsr-cfg)))))

(defn next-id []
  (reset! *lfsr* (lfsr/next-lfsr @*lfsr*))
  (:state @*lfsr*))

(defn next-id-hex []
  (let [id (str (apply str (repeat 10 "0")) (.toString (next-id) 16))]
    (str "ID" (.substring id (- (count id) 10) (count id)))))

(dotimes [ii 10]
  (printf "next id=%s\n" (next-id-hex)))

It produces the following output

next id=ID00a3000000
next id=ID0051800000
next id=ID0028c00000
next id=ID0014600000
next id=ID000a300000
next id=ID0005180000
next id=ID00028c0000
next id=ID0001460000
next id=ID0000a30000
next id=ID0000518000

An LFSR’s next state is entirely dependent on only its current state, it is possible to create an LFSR (your ID generator), commit it to persistent storage until it’s needed, re-initialize your LFSR with the previous state and continue enumerating from it.

The only drawback from this perspective is that a single LFSR can not be used concurrently or in a distributed manner, then again it’s easy enough to add a prefix or use separate LFSRs.

Taps Database

clj-lfsr.taps contains a data set of bit sizes and taps for several known maximal sequence LFSRs. These were obtained from the Wikipedia article and provide a convenient starting point for your own LFSRs.

Installation

If you’re using Leiningen, add the following to your project.clj file’s :dependencies:

  [com.github.kyleburton/clj-lfsr "1.0.0"]

For maven:

  <dependencies>
    <dependency>
      <groupId>com.github.kyleburton</groupId>
      <artifactId>clj-lfsr</artifactId>
      <version>1.0.0</version>
    </dependency>
    ...
  </dependencies>

Building

To build using Leiningen:

  clj-lfsr$ lein test
  clj-lfsr$ lein jar
  clj-lfsr$ lein uberjar

References

License

Same as Clojure