Commits

Jason S committed 7f2c523

moved common items into LFSRBase, added stateFromOutputBits

  • Participants
  • Parent commits d761bca

Comments (0)

Files changed (1)

src/libgf2/lfsr.py

         i <<= 1
     return k & 1
 
-class LFSR(object):
+class LFSRBase(object):
+    def __init__(self, poly):
+        self.poly = poly;
+        self.n = _degree(poly)
+    @property
+    def degree(self):
+        return self.n
+    def _stateFromReverseIterator(self, it, atEnd=True):
+        '''returns the state of an LFSR with default mask that produces the given output.
+        if atEnd is True, the state in question is the state at the end of the output.
+        Otherwise it is the state at the beginning of the output.
+        '''
+        n = self.degree
+        s = 0
+        # run backwards until the state has no unknown bits
+        for bit in it:
+            if bit != 0:
+                s ^= self.poly
+            s >>= 1
+        # then run forwards again, if desired
+        if atEnd:
+            for i in xrange(n-1):
+                s <<= 1
+                if (s >> n) & 1 == 1:
+                    s ^= self.poly
+        return s
+    
+    def stateFromOutput(self, output, atEnd=True):
+        '''returns the state of an LFSR with default mask that produces the given output.
+        if atEnd is True, the state in question is the state at the end of the output.
+        Otherwise it is the state at the beginning of the output.
+        '''
+        n = self.degree
+        return self._stateFromReverseIterator(((output >> i & 1) for i in xrange(n)), atEnd)
+    def stateFromOutputBits(self, output, atEnd=True):
+        '''returns the state of an LFSR with default mask that produces the given output.
+        if atEnd is True, the state in question is the state at the end of the output.
+        Otherwise it is the state at the beginning of the output.
+        '''
+        n = self.degree
+        return self._stateFromReverseIterator(output[n-1::-1], atEnd)
+
+class LFSR(LFSRBase):
     '''
     Linear feedback shift register, with an output mask:
     at any given instant, the output is the parity of the state ANDed with the output mask.
     LFSR state s[k] = initstate * x^k 
     '''
     def __init__(self, poly, initstate=1, mask=None):
-        self.poly = poly;
-        self.n = _degree(poly)
+        LFSRBase.__init__(self, poly)
         self.testmask = 1 << self.n
         self.coefficientsMask = mask
         self.state = initstate
             b = parity(self.state & self.coefficientsMask)
         self.state = nextState            
         return b
-    @property
-    def degree(self):
-        return self.n
-    def stateFromOutput(self, output, atEnd=True):
-        '''returns the state of an LFSR with default mask that produces the given output.
-        if atEnd is True, the state in question is the state at the end of the output.
-        Otherwise it is the state at the beginning of the output.
-        '''
-        n = self.degree
-        s = 0
-        # run backwards until the state has no unknown bits
-        for i in xrange(n):
-            if ((output >> i) & 1) != 0:
-                s ^= self.poly
-            s >>= 1
-        # then run forwards again, if desired
-        if atEnd:
-            for i in xrange(n-1):
-                s <<= 1
-                if (s >> n) & 1 == 1:
-                    s ^= self.poly
-        return s
-
     def __repr__(self):
         return 'LFSR({0:x},{1:x})'.format(self.poly,self.state)
 
-class LFSRAnalyzer(object):
+class LFSRAnalyzer(LFSRBase):
     def __init__(self, poly, factors=None):
-        self.poly = poly;
+        LFSRBase.__init__(self, poly)
         self.dlog = GF2DiscreteLog(poly, factors)
-    def getDegree(self):
-        return _degree(self.poly)
     def lookaheadCoefficients(self, k):
         '''returns coefficients a_j such that the sum of a_j*state[j] = output[n+k],
         for an LFSR with default mask'''
         '''returns initial state of an LFSR with default mask, such that the output matches 
         the output of a masked LFSR with given coefficients and initial state of 1'''
          
-        n = self.getDegree()
+        n = self.degree
         e1 = GF2Element(1,self.poly)
         out = 0
         for i in xrange(n):
         return self.dlog.log(s)
     def timeshiftFromState(self, s):
         return self.dlog.log(s)
-    def stateFromOutput(self, output, atEnd=True):
-        '''returns the state of an LFSR with default mask that produces the given output.
-        if atEnd is True, the state in question is the state at the end of the output.
-        Otherwise it is the state at the beginning of the output.
-        '''
-        n = self.getDegree()
-        s = 0
-        # run backwards until the state has no unknown bits
-        for i in xrange(n):
-            if ((output >> i) & 1) != 0:
-                s ^= self.poly
-            s >>= 1
-        # then run forwards again, if desired
-        if atEnd:
-            for i in xrange(n-1):
-                s <<= 1
-                if (s >> n) & 1 == 1:
-                    s ^= self.poly
-        return s
     def coefficientsFromState(self, s):
         '''Inverse of stateFromCoefficients'''
-        n = self.getDegree()
+        n = self.degree
         c = 0
         for i in xrange(n):
             b = (s >> (n-1)) << i