Debian Codegraph @

protolib/include/protoLFSR.h

raw
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