#ifndef _PROTO_LFSR #define _PROTO_LFSR #include "protoDefs.h" // for UINT32 and UINT8 types #include "protoBitmask.h" // for ProtoBitmask::GetWeight() // This class implements Galois construction of // of m-sequences that would be generated by a // linear feedback shift register (LFSR) // The ProtoLFSR class has a maximum 32-bit register size // (The ProtoLFSRX class below can work with arbitrary register sizes) class ProtoLFSR { public: // These m-sequence generator polynomials are from // Forney[1970] via Proakis[1989], Table 5.2.5 // Note the first set bit is "stage 1" of the // shift register. In this Galois construction, // the output is collected from "stage m" enum Polynomial { // Connected shift register stages PN_NONE = 0x00000000, // invalid polynomial PN3 = 0x00000003, // 2 bits, stages 1,2 PN7 = 0x00000005, // 3 bits, stages 1,3 PN15 = 0x00000009, // 4 bits, stages 1,4 PN31 = 0x00000012, // 5 bits, stages 1,4 PN63 = 0x00000021, // 6 bits, stages 1,6 PN127 = 0x00000041, // 7 bits, stages 1,7 PN255 = 0x0000008e, // 8 bits, stages 1,5,6,7 PN511 = 0x00000108, // 9 bits, stages 1,6 PN1023 = 0x00000204, // 10 bits, stages 1,8 PN2047 = 0x00000402, // 11 bits, stages 1,10 PN4095 = 0x00000829, // 12 bits, stages 1,7,9,12 PN8191 = 0x00001070, // 13 bits, stages 1,7,8,9 PN65535 = 0x00008805, // 16 bits, stages 1,5,14,16 PN24BIT = 0x00800043, // 24 bits, stages 1,18,23,24 PN32BIT = 0x80200003, // 32 bits, stages 1,11,31,32 PNTEST = 0x00000025 }; // The "reverse" parameter when set to "true" generates // the time-reversed version of the given PN sequence ProtoLFSR(Polynomial polynomial = PN2047, UINT32 initialState = 0xffffffff, bool reverse = false); Polynomial GetPolynomial() const {return (Polynomial)lfsr_poly;} UINT32 GetState() const {return (lfsr_state);} // Get lfsr size in bits unsigned int GetNumBits() const {return lfsr_bits;} // Get lfsr size in bytes (rounding up) unsigned int GetNumBytes() const { unsigned int n = lfsr_bits >> 3; return (0 != (lfsr_bits & 0x07)) ? n+1 : n; } // Get bitmask to apply to state or polynomial if desired UINT32 GetMask() const {return lfsr_mask;} void Reset(UINT32 initialState = 0xffffffff) { byte_mode = false; if (IsMirrored()) Mirror(); lfsr_state = (initialState & lfsr_mask); } // This adjusts the "cursor" (i.e. position) // of the sequence. I.e., GetNextBit() returns // the bit following the "cursor" and GetPrevBit() // returns the bit preceding the "cursor" void Seek(int offset); // These methods can be used to "jog/shuttle" back and // forth through the generated sequence. // These return the next bit (or byte) of the sequence bool GetNextBit(); UINT8 GetNextByte(); // These return the bit (or byte) prior in the sequence // _before_ the last bit/byte produced by GetNextBit() // or GetNextByte(), respectively. bool GetPrevBit(); UINT8 GetPrevByte(); void FillBuffer(char* buffer, unsigned int buflen); // Here, buflen MUST be >= ((GetNumBits() + bitOffset) / 8) bool Sync(const char* buffer, unsigned int buflen, unsigned int bitOffset = 0); // Some static "helper" methods static unsigned int GetPolySize(Polynomial poly); static Polynomial GetPolynomial(unsigned int registerSize) {return POLYNOMIAL_LIST[registerSize &= 31];} static UINT32 PolynomialSearch(unsigned int registerSize); static unsigned char GetWeight(unsigned char c) {return ProtoBitmask::GetWeight(c);} static bool GetBit(const char* buffer, unsigned int index) {return (0 != (buffer[index >> 3] & (0x80 >> (index & 0x07))));} static UINT32 MirrorBits(UINT32 word, unsigned int numBits); private: static const ProtoLFSR::Polynomial POLYNOMIAL_LIST[33]; void Shift(unsigned int count = 1); void LoadBit(bool bit); void Mirror(); bool IsMirrored() const {return is_mirrored;} UINT32 lfsr_poly; UINT32 lfsr_state; unsigned int lfsr_bits; UINT32 lfsr_mask; bool is_mirrored; bool byte_mode; }; // end class ProtoLFSR // "Extended" version of ProtoLFSR that can have arbitrarily large register sizes // (ProtoLFSR is limited to a 32-bit maximum register size, but with quicker performance) class ProtoLFSRX { public: ProtoLFSRX(); ~ProtoLFSRX(); // Bit zero of "polynomial" and "initialState" is the // least significant bit of polynomial[0] and initialState[0], // respectively. If "numBits" is not a multiple of 32 bits, // then only the least significant bits of the the last // word in the "polynomial" and "initialState" arrays are used. // (If "numBits" <= 32, then it's the same as ProtoLFSR above) // The "reverse" parameter when set to "true" generates // the time-reversed version of the given PN sequence bool SetPolynomial(const UINT32* polynomial, unsigned int numBits, const UINT32* initialState = NULL, // all 1's by default bool reverse = false); // Use the Berlekamp-Massey algorithm to compute a polynomial // from the input bit sequence in the "buffer" // (Will return "false" if input is non-linear (i.e. non-reproducible) bool ComputePolynomial(const char* buffer, int numBits); const UINT32* GetPolynomial() const {return lfsrx_poly;} const UINT32* GetState() const {return lfsrx_state;} // Get lfsr size in bits unsigned int GetNumBits() const {return lfsrx_bits;} // Get lfsr size in bytes (rounded up) unsigned int GetNumBytes() const { unsigned int n = lfsrx_bits >> 3; return (0 != (lfsrx_bits & 0x07)) ? n+1 : n; } // Get lfsr size in 32-bit words (rounded up) unsigned int GetNumWords() const {return lfsrx_words;} // Get bitmask to use for most significant word UINT32 GetMask() const {return lfsrx_mask;} void Reset(UINT32* initialState = NULL); // all 1's by default // This adjusts the "cursor" (i.e. position) // of the sequence. I.e., GetNextBit() returns // the bit following the "cursor" and GetPrevBit() // returns the bit preceding the "cursor" void Seek(int offset); // These methods can be used to "jog/shuttle" back and // forth through the generated sequence. // These return the next bit (or byte) of the sequence bool GetNextBit(); UINT8 GetNextByte(); // These return the bit (or byte) prior in the sequence // _before_ the last bit/byte produced by GetNextBit() // or GetNextByte(), respectively. bool GetPrevBit(); UINT8 GetPrevByte(); void FillBuffer(char* buffer, unsigned int buflen); // Here, buflen MUST be >= ((GetNumBits() + bitOffset) / 8) bool Sync(const char* buffer, unsigned int buflen, unsigned int bitOffset = 0); // Some static "helper" methods static unsigned char GetWeight(unsigned char c) {return ProtoBitmask::GetWeight(c);} private: void Shift(unsigned int count = 1); // right shift void LoadBit(bool bit); void Mirror(); bool IsMirrored() const {return is_mirrored;} static bool GetBit32(UINT32* buffer, unsigned int index) {return (0 != (buffer[index >> 5] & (0x00000001 << (index & 0x01f))));} static void SetBit32(UINT32* buffer, unsigned int index, bool bit) { if (bit) buffer[(index >> 5)] |= (0x00000001 << (index & 0x01f)); else buffer[(index >> 5)] &= ~(0x00000001 << (index & 0x01f)); } UINT32* lfsrx_poly; UINT32* lfsrx_state; unsigned int lfsrx_bits; unsigned int lfsrx_words; // lfsrx_bits >> 3 (rounded down) UINT32 lfsrx_mask; // mask for most significant word (i.e. lfsrx_poly[lfsrx_words] bool is_mirrored; bool byte_mode; }; // end class ProtoLFSRX #endif // _PROTO_LFSR