| 1 |
#ifndef _PROTO_LFSR |
| 2 |
#define _PROTO_LFSR |
| 3 |
|
| 4 |
#include "protoDefs.h" // for UINT32 and UINT8 types |
| 5 |
#include "protoBitmask.h" // for ProtoBitmask::GetWeight() |
| 6 |
|
| 7 |
// This class implements Galois construction of |
| 8 |
// of m-sequences that would be generated by a |
| 9 |
// linear feedback shift register (LFSR) |
| 10 |
// The ProtoLFSR class has a maximum 32-bit register size |
| 11 |
// (The ProtoLFSRX class below can work with arbitrary register sizes) |
| 12 |
class ProtoLFSR |
| 13 |
{ |
| 14 |
public: |
| 15 |
|
| 16 |
// These m-sequence generator polynomials are from |
| 17 |
// Forney[1970] via Proakis[1989], Table 5.2.5 |
| 18 |
// Note the first set bit is "stage 1" of the |
| 19 |
// shift register. In this Galois construction, |
| 20 |
// the output is collected from "stage m" |
| 21 |
enum Polynomial |
| 22 |
{ // Connected shift register stages |
| 23 |
PN_NONE = 0x00000000, // invalid polynomial |
| 24 |
PN3 = 0x00000003, // 2 bits, stages 1,2 |
| 25 |
PN7 = 0x00000005, // 3 bits, stages 1,3 |
| 26 |
PN15 = 0x00000009, // 4 bits, stages 1,4 |
| 27 |
PN31 = 0x00000012, // 5 bits, stages 1,4 |
| 28 |
PN63 = 0x00000021, // 6 bits, stages 1,6 |
| 29 |
PN127 = 0x00000041, // 7 bits, stages 1,7 |
| 30 |
PN255 = 0x0000008e, // 8 bits, stages 1,5,6,7 |
| 31 |
PN511 = 0x00000108, // 9 bits, stages 1,6 |
| 32 |
PN1023 = 0x00000204, // 10 bits, stages 1,8 |
| 33 |
PN2047 = 0x00000402, // 11 bits, stages 1,10 |
| 34 |
PN4095 = 0x00000829, // 12 bits, stages 1,7,9,12 |
| 35 |
PN8191 = 0x00001070, // 13 bits, stages 1,7,8,9 |
| 36 |
PN65535 = 0x00008805, // 16 bits, stages 1,5,14,16 |
| 37 |
PN24BIT = 0x00800043, // 24 bits, stages 1,18,23,24 |
| 38 |
PN32BIT = 0x80200003, // 32 bits, stages 1,11,31,32 |
| 39 |
PNTEST = 0x00000025 |
| 40 |
}; |
| 41 |
|
| 42 |
// The "reverse" parameter when set to "true" generates |
| 43 |
// the time-reversed version of the given PN sequence |
| 44 |
ProtoLFSR(Polynomial polynomial = PN2047, |
| 45 |
UINT32 initialState = 0xffffffff, |
| 46 |
bool reverse = false); |
| 47 |
|
| 48 |
Polynomial GetPolynomial() const |
| 49 |
{return (Polynomial)lfsr_poly;} |
| 50 |
|
| 51 |
UINT32 GetState() const |
| 52 |
{return (lfsr_state);} |
| 53 |
|
| 54 |
// Get lfsr size in bits |
| 55 |
unsigned int GetNumBits() const |
| 56 |
{return lfsr_bits;} |
| 57 |
|
| 58 |
// Get lfsr size in bytes (rounding up) |
| 59 |
unsigned int GetNumBytes() const |
| 60 |
{ |
| 61 |
unsigned int n = lfsr_bits >> 3; |
| 62 |
return (0 != (lfsr_bits & 0x07)) ? n+1 : n; |
| 63 |
} |
| 64 |
|
| 65 |
// Get bitmask to apply to state or polynomial if desired |
| 66 |
UINT32 GetMask() const |
| 67 |
{return lfsr_mask;} |
| 68 |
|
| 69 |
void Reset(UINT32 initialState = 0xffffffff) |
| 70 |
{ |
| 71 |
byte_mode = false; |
| 72 |
if (IsMirrored()) Mirror(); |
| 73 |
lfsr_state = (initialState & lfsr_mask); |
| 74 |
} |
| 75 |
|
| 76 |
|
| 77 |
// This adjusts the "cursor" (i.e. position) |
| 78 |
// of the sequence. I.e., GetNextBit() returns |
| 79 |
// the bit following the "cursor" and GetPrevBit() |
| 80 |
// returns the bit preceding the "cursor" |
| 81 |
void Seek(int offset); |
| 82 |
|
| 83 |
// These methods can be used to "jog/shuttle" back and |
| 84 |
// forth through the generated sequence. |
| 85 |
// These return the next bit (or byte) of the sequence |
| 86 |
bool GetNextBit(); |
| 87 |
UINT8 GetNextByte(); |
| 88 |
|
| 89 |
// These return the bit (or byte) prior in the sequence |
| 90 |
// _before_ the last bit/byte produced by GetNextBit() |
| 91 |
// or GetNextByte(), respectively. |
| 92 |
bool GetPrevBit(); |
| 93 |
UINT8 GetPrevByte(); |
| 94 |
|
| 95 |
void FillBuffer(char* buffer, unsigned int buflen); |
| 96 |
|
| 97 |
// Here, buflen MUST be >= ((GetNumBits() + bitOffset) / 8) |
| 98 |
bool Sync(const char* buffer, unsigned int buflen, unsigned int bitOffset = 0); |
| 99 |
|
| 100 |
// Some static "helper" methods |
| 101 |
static unsigned int GetPolySize(Polynomial poly); |
| 102 |
static Polynomial GetPolynomial(unsigned int registerSize) |
| 103 |
{return POLYNOMIAL_LIST[registerSize &= 31];} |
| 104 |
|
| 105 |
static UINT32 PolynomialSearch(unsigned int registerSize); |
| 106 |
|
| 107 |
static unsigned char GetWeight(unsigned char c) |
| 108 |
{return ProtoBitmask::GetWeight(c);} |
| 109 |
|
| 110 |
static bool GetBit(const char* buffer, unsigned int index) |
| 111 |
{return (0 != (buffer[index >> 3] & (0x80 >> (index & 0x07))));} |
| 112 |
|
| 113 |
static UINT32 MirrorBits(UINT32 word, unsigned int numBits); |
| 114 |
|
| 115 |
private: |
| 116 |
static const ProtoLFSR::Polynomial POLYNOMIAL_LIST[33]; |
| 117 |
void Shift(unsigned int count = 1); |
| 118 |
void LoadBit(bool bit); |
| 119 |
void Mirror(); |
| 120 |
bool IsMirrored() const |
| 121 |
{return is_mirrored;} |
| 122 |
|
| 123 |
|
| 124 |
|
| 125 |
UINT32 lfsr_poly; |
| 126 |
UINT32 lfsr_state; |
| 127 |
unsigned int lfsr_bits; |
| 128 |
UINT32 lfsr_mask; |
| 129 |
bool is_mirrored; |
| 130 |
bool byte_mode; |
| 131 |
|
| 132 |
}; // end class ProtoLFSR |
| 133 |
|
| 134 |
// "Extended" version of ProtoLFSR that can have arbitrarily large register sizes |
| 135 |
// (ProtoLFSR is limited to a 32-bit maximum register size, but with quicker performance) |
| 136 |
class ProtoLFSRX |
| 137 |
{ |
| 138 |
public: |
| 139 |
|
| 140 |
ProtoLFSRX(); |
| 141 |
~ProtoLFSRX(); |
| 142 |
|
| 143 |
// Bit zero of "polynomial" and "initialState" is the |
| 144 |
// least significant bit of polynomial[0] and initialState[0], |
| 145 |
// respectively. If "numBits" is not a multiple of 32 bits, |
| 146 |
// then only the least significant bits of the the last |
| 147 |
// word in the "polynomial" and "initialState" arrays are used. |
| 148 |
// (If "numBits" <= 32, then it's the same as ProtoLFSR above) |
| 149 |
// The "reverse" parameter when set to "true" generates |
| 150 |
// the time-reversed version of the given PN sequence |
| 151 |
bool SetPolynomial(const UINT32* polynomial, |
| 152 |
unsigned int numBits, |
| 153 |
const UINT32* initialState = NULL, // all 1's by default |
| 154 |
bool reverse = false); |
| 155 |
|
| 156 |
// Use the Berlekamp-Massey algorithm to compute a polynomial |
| 157 |
// from the input bit sequence in the "buffer" |
| 158 |
// (Will return "false" if input is non-linear (i.e. non-reproducible) |
| 159 |
bool ComputePolynomial(const char* buffer, int numBits); |
| 160 |
|
| 161 |
const UINT32* GetPolynomial() const |
| 162 |
{return lfsrx_poly;} |
| 163 |
|
| 164 |
const UINT32* GetState() const |
| 165 |
{return lfsrx_state;} |
| 166 |
|
| 167 |
// Get lfsr size in bits |
| 168 |
unsigned int GetNumBits() const |
| 169 |
{return lfsrx_bits;} |
| 170 |
|
| 171 |
// Get lfsr size in bytes (rounded up) |
| 172 |
unsigned int GetNumBytes() const |
| 173 |
{ |
| 174 |
unsigned int n = lfsrx_bits >> 3; |
| 175 |
return (0 != (lfsrx_bits & 0x07)) ? n+1 : n; |
| 176 |
} |
| 177 |
|
| 178 |
// Get lfsr size in 32-bit words (rounded up) |
| 179 |
unsigned int GetNumWords() const |
| 180 |
{return lfsrx_words;} |
| 181 |
|
| 182 |
// Get bitmask to use for most significant word |
| 183 |
UINT32 GetMask() const |
| 184 |
{return lfsrx_mask;} |
| 185 |
|
| 186 |
void Reset(UINT32* initialState = NULL); // all 1's by default |
| 187 |
|
| 188 |
// This adjusts the "cursor" (i.e. position) |
| 189 |
// of the sequence. I.e., GetNextBit() returns |
| 190 |
// the bit following the "cursor" and GetPrevBit() |
| 191 |
// returns the bit preceding the "cursor" |
| 192 |
void Seek(int offset); |
| 193 |
|
| 194 |
// These methods can be used to "jog/shuttle" back and |
| 195 |
// forth through the generated sequence. |
| 196 |
// These return the next bit (or byte) of the sequence |
| 197 |
bool GetNextBit(); |
| 198 |
UINT8 GetNextByte(); |
| 199 |
|
| 200 |
// These return the bit (or byte) prior in the sequence |
| 201 |
// _before_ the last bit/byte produced by GetNextBit() |
| 202 |
// or GetNextByte(), respectively. |
| 203 |
bool GetPrevBit(); |
| 204 |
UINT8 GetPrevByte(); |
| 205 |
|
| 206 |
void FillBuffer(char* buffer, unsigned int buflen); |
| 207 |
|
| 208 |
// Here, buflen MUST be >= ((GetNumBits() + bitOffset) / 8) |
| 209 |
bool Sync(const char* buffer, unsigned int buflen, unsigned int bitOffset = 0); |
| 210 |
|
| 211 |
// Some static "helper" methods |
| 212 |
static unsigned char GetWeight(unsigned char c) |
| 213 |
{return ProtoBitmask::GetWeight(c);} |
| 214 |
|
| 215 |
private: |
| 216 |
void Shift(unsigned int count = 1); // right shift |
| 217 |
void LoadBit(bool bit); |
| 218 |
void Mirror(); |
| 219 |
bool IsMirrored() const |
| 220 |
{return is_mirrored;} |
| 221 |
|
| 222 |
static bool GetBit32(UINT32* buffer, unsigned int index) |
| 223 |
{return (0 != (buffer[index >> 5] & (0x00000001 << (index & 0x01f))));} |
| 224 |
|
| 225 |
static void SetBit32(UINT32* buffer, unsigned int index, bool bit) |
| 226 |
{ |
| 227 |
if (bit) |
| 228 |
buffer[(index >> 5)] |= (0x00000001 << (index & 0x01f)); |
| 229 |
else |
| 230 |
buffer[(index >> 5)] &= ~(0x00000001 << (index & 0x01f)); |
| 231 |
} |
| 232 |
|
| 233 |
UINT32* lfsrx_poly; |
| 234 |
UINT32* lfsrx_state; |
| 235 |
unsigned int lfsrx_bits; |
| 236 |
unsigned int lfsrx_words; // lfsrx_bits >> 3 (rounded down) |
| 237 |
UINT32 lfsrx_mask; // mask for most significant word (i.e. lfsrx_poly[lfsrx_words] |
| 238 |
bool is_mirrored; |
| 239 |
bool byte_mode; |
| 240 |
|
| 241 |
}; // end class ProtoLFSRX |
| 242 |
|
| 243 |
|
| 244 |
#endif // _PROTO_LFSR |