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

   1 /* -*- c++ -*- */
   2 /*
   3  * Copyright 2008 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_shift_register_length;     // less than 32
  90
  91   static uint32_t
  92   popCount(uint32_t x)
  93   {
  94     uint32_t r = x - ((x >> 1) & 033333333333)
  95                    - ((x >> 2) & 011111111111);
  96     return ((r + (r >> 3)) & 030707070707) % 63;
  97   }
  98
  99  public:
 100
 101   gri_lfsr(uint32_t mask, uint32_t seed, uint32_t reg_len)
 102     : d_shift_register(seed), d_mask(mask), d_shift_register_length(reg_len)
 103   {
 104     if (reg_len > 31)
 105       throw std::invalid_argument("reg_len must be <= 31");
 106   }
 107
 108   unsigned char next_bit() {
 109     unsigned char output = d_shift_register & 1;
 110     unsigned char newbit = popCount( d_shift_register & d_mask )%2;
 111     d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
 112     return output;
 113   }
 114
 115   unsigned char next_bit_scramble(unsigned char input) {
 116     unsigned char output = d_shift_register & 1;
 117     unsigned char newbit = (popCount( d_shift_register & d_mask )%2)^(input & 1);
 118     d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
 119     return output;
 120   }
 121
 122   unsigned char next_bit_descramble(unsigned char input) {
 123     unsigned char output = (popCount( d_shift_register & d_mask )%2)^(input & 1);
 124     unsigned char newbit = input & 1;
 125     d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
 126     return output;
 127   }
 128
 129
 130   /*!
 131    * Rotate the register through x number of bits
 132    * where we are just throwing away the results to get queued up correctly
 133    */
 134   void pre_shift(int num){
 135     for(int i=0; i<num; i++){
 136       next_bit();
 137     }
 138   }
 139
 140   int mask() const { return d_mask; }
 141 };
 142
 143 #endif /* INCLUDED_GRI_LFSR_H */