git.gag.com Git - debian/gnuradio/blob - gnuradio-core/src/lib/general/gri_lfsr.h

   1 /* -*- c++ -*- */
   2 /*
   3  * Copyright 2008,2010 Free Software Foundation, Inc.
   4  *
   5  * This file is part of GNU Radio
   6  *
   7  * GNU Radio is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 3, or (at your option)
  10  * any later version.
  11  *
  12  * GNU Radio is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with GNU Radio; see the file COPYING.  If not, write to
  19  * the Free Software Foundation, Inc., 51 Franklin Street,
  20  * Boston, MA 02110-1301, USA.
  21  */
  22
  23 #ifndef INCLUDED_GRI_LFSR_H
  24 #define INCLUDED_GRI_LFSR_H
  25
  26 #include <stdexcept>
  27 #include <stdint.h>
  28
  29 /*!
  30  * \brief Fibonacci Linear Feedback Shift Register using specified polynomial mask
  31  * \ingroup misc
  32  *
  33  * Generates a maximal length pseudo-random sequence of length 2^degree-1
  34  *
  35  * Constructor: gri_lfsr(int mask, int seed, int reg_len);
  36  *
  37  *      mask - polynomial coefficients representing the locations
  38  *             of feedback taps from a shift register which are xor'ed
  39  *             together to form the new high order bit.
  40  *
  41  *             Some common masks might be:
  42  *              x^4 + x^3 + x^0 = 0x19
  43  *              x^5 + x^3 + x^0 = 0x29
  44  *              x^6 + x^5 + x^0 = 0x61
  45  *
  46  *      seed - the initialization vector placed into the register
  47  *             durring initialization.   Low order bit corresponds
  48  *             to x^0 coefficient -- the first to be shifted as output.
  49  *
  50  *   reg_len - specifies the length of the feedback shift register
  51  *             to be used.   Durring each iteration, the register
  52  *             is rightshifted one and the new bit is placed in bit reg_len.
  53  *             reg_len should generally be at least order(mask) + 1
  54  *
  55  *
  56  * see http://en.wikipedia.org/wiki/Linear_feedback_shift_register
  57  * for more explanation.
  58  *
  59  *
  60  *
  61  *  next_bit() - Standard LFSR operation
  62  *
  63  *      Perform one cycle of the LFSR.  The output bit is taken from
  64  *      the shift register LSB.  The shift register MSB is assigned from
  65  *      the modulo 2 sum of the masked shift register.
  66  *
  67  *  next_bit_scramble(unsigned char input) - Scramble an input stream
  68  *
  69  *      Perform one cycle of the LFSR.  The output bit is taken from
  70  *      the shift register LSB.  The shift register MSB is assigned from
  71  *      the modulo 2 sum of the masked shift register and the input LSB.
  72  *
  73  *  next_bit_descramble(unsigned char input) - Descramble an input stream
  74  *
  75  *      Perform one cycle of the LFSR.  The output bit is taken from
  76  *      the modulo 2 sum of the masked shift register and the input LSB.
  77  *      The shift register MSB is assigned from the LSB of the input.
  78  *
  79  * See http://en.wikipedia.org/wiki/Scrambler for operation of these
  80  * last two functions (see multiplicative scrambler.)
  81  *
  82  */
  83
  84 class gri_lfsr
  85 {
  86  private:
  87   uint32_t d_shift_register;
  88   uint32_t d_mask;
  89   uint32_t d_seed;
  90   uint32_t d_shift_register_length;     // less than 32
  91
  92   static uint32_t
  93   popCount(uint32_t x)
  94   {
  95     uint32_t r = x - ((x >> 1) & 033333333333)
  96                    - ((x >> 2) & 011111111111);
  97     return ((r + (r >> 3)) & 030707070707) % 63;
  98   }
  99
 100  public:
 101
 102   gri_lfsr(uint32_t mask, uint32_t seed, uint32_t reg_len)
 103     : d_shift_register(seed),
 104       d_mask(mask),
 105       d_seed(seed),
 106       d_shift_register_length(reg_len)
 107   {
 108     if (reg_len > 31)
 109       throw std::invalid_argument("reg_len must be <= 31");
 110   }
 111
 112   unsigned char next_bit() {
 113     unsigned char output = d_shift_register & 1;
 114     unsigned char newbit = popCount( d_shift_register & d_mask )%2;
 115     d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
 116     return output;
 117   }
 118
 119   unsigned char next_bit_scramble(unsigned char input) {
 120     unsigned char output = d_shift_register & 1;
 121     unsigned char newbit = (popCount( d_shift_register & d_mask )%2)^(input & 1);
 122     d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
 123     return output;
 124   }
 125
 126   unsigned char next_bit_descramble(unsigned char input) {
 127     unsigned char output = (popCount( d_shift_register & d_mask )%2)^(input & 1);
 128     unsigned char newbit = input & 1;
 129     d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
 130     return output;
 131   }
 132
 133   /*!
 134    * Reset shift register to initial seed value
 135    */
 136   void reset() { d_shift_register = d_seed; }
 137
 138   /*!
 139    * Rotate the register through x number of bits
 140    * where we are just throwing away the results to get queued up correctly
 141    */
 142   void pre_shift(int num){
 143     for(int i=0; i<num; i++){
 144       next_bit();
 145     }
 146   }
 147
 148   int mask() const { return d_mask; }
 149 };
 150
 151 #endif /* INCLUDED_GRI_LFSR_H */