#!/usr/bin/env python #-*-coding:utf-8-*- # # A simple, high level, implementation of a LFSR. # # Fibonacci model # # __________+_______+________________ # | ^ ^ ^ # | ___ | ___ | ___ ___ | # | | | | | | | | | | | | # ---->| d |---| c |---| b |---| a |------> S = ..., s_1, s_0 # |___| |___| |___| |___| # 3 2 1 0 # # ______+___+_______ # | ^ ^ ^ # | _|_ _|_ ___ _|_ # | | | | | | # ---->| d | c | b | a |------> S = ..., s_1, s_0 # |___|___|___|___| # 3 2 1 0 # # $ python # Python 2.6.2 (release26-maint, Apr 19 2009, 01:56:41) # [GCC 4.3.3] on linux2 # Type "help", "copyright", "credits" or "license" for more information. # >>> import lfsr # >>> x = lfsr.LFSR([0,0,1,0,1], [1,0,0,1,1]) # >>> x.dump() # ([0, 0, 1, 0, 1], [1, 0, 0, 1, 1]) # >>> x.period() # 7 # >>> x.clock() # 0 # >>> x.clock() # 0 # >>> x.clock() # 1 # >>> x.clock() # 0 # >>> x.clock() # 1 # >>> x.clock() # 1 # >>> x.clock() # 0 # >>> x.clock() # 0 # >>> x.clock() # 0 # >>> x.clock() # 1 # # Copyright (c) Stefan Pettersson 2007, http://www.bigpointyteeth.se/ # # Permission to use, copy, modify, and distribute this software for any # purpose with or without fee is hereby granted, provided that the above # copyright notice and this permission notice appear in all copies. # # THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES # WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF # MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR # ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES # WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN # ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF # OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. # class LFSR(object): def __init__(self, seed, feedback): """Returns a linear feedback shift register with seed as the initial values and feedback as the feedback polynomial. >>> x = lfsr.LFSR([0,0,0,1], [1,0,1,0]) The feedback polynomial given above, 1 + x^2, is primitive and will generate the maximum possible sequence of length 2^4 - 1 = 15.""" self.length = len(seed) self.clocks = 1 self.seed = seed[:] self.register = seed self.feedback = feedback # at which indices do we have taps? self.taps = [] for i in range(len(feedback)): if feedback[i]: self.taps.append(i) def _xor(self, a, b): """Helper function that returns the sum mod 2 of a and b.""" return a ^ b def period(self): """Returns the period of the LFSR.""" tmp = self.register[:] clocks = 1 self.clock(False) # cheap one, i know, bit there are no do loops while self.register != tmp: self.clock(False) clocks += 1 return clocks def dump(self): """Print the LFSRs current register and its feedback polynomial.""" return self.register, self.feedback def clock(self, count=True): """Clock one step of the LFSR and return the popped value.""" # prevent from incrementing the counter when used internally, like period() if count: self.clocks += 1 add = reduce(self._xor, [self.register[i] for i in self.taps]) self.register.append(add) pop = self.register.pop(0) return pop # EOF