| 1 |
|
| 2 |
#include "protoLFSR.h" |
| 3 |
#include "protoDebug.h" |
| 4 |
#include <stdlib.h> // for abs() |
| 5 |
|
| 6 |
ProtoLFSR::ProtoLFSR(Polynomial polynomial, |
| 7 |
UINT32 initialState, |
| 8 |
bool reverse) |
| 9 |
: lfsr_poly((UINT32)polynomial), |
| 10 |
lfsr_state(initialState), |
| 11 |
lfsr_bits(GetPolySize(polynomial)), |
| 12 |
is_mirrored(false), byte_mode(false) |
| 13 |
{ |
| 14 |
lfsr_mask = ((UINT32)0xffffffff) >> (32 - lfsr_bits); |
| 15 |
//TRACE("lfsr_mask = 0x%04x\n", lfsr_mask); |
| 16 |
lfsr_state &= lfsr_mask; |
| 17 |
if (reverse) |
| 18 |
{ |
| 19 |
Mirror(); |
| 20 |
is_mirrored = false; |
| 21 |
} |
| 22 |
} |
| 23 |
|
| 24 |
unsigned int ProtoLFSR::GetPolySize(Polynomial poly) |
| 25 |
{ |
| 26 |
unsigned int numBits = 0; |
| 27 |
UINT32 p = (UINT32)poly; |
| 28 |
while (0 != p) |
| 29 |
{ |
| 30 |
p >>= 1; |
| 31 |
numBits++; |
| 32 |
} |
| 33 |
return numBits; |
| 34 |
} // end ProtoLFSR::GetPolySize() |
| 35 |
|
| 36 |
|
| 37 |
const ProtoLFSR::Polynomial ProtoLFSR::POLYNOMIAL_LIST[33] = |
| 38 |
{ |
| 39 |
PN_NONE, // 0 bits (invalid) |
| 40 |
PN_NONE, // 1 bit (TBD) |
| 41 |
PN3, // 2 bits |
| 42 |
PN7, // 3 bits |
| 43 |
PN15, // 4 bits |
| 44 |
PN31, // 5 bits |
| 45 |
PN63, // 5 bits |
| 46 |
PN127, // 7 bits |
| 47 |
PN255, // 8 bits |
| 48 |
PN511, // 9 bits |
| 49 |
PN1023, // 10 bits |
| 50 |
PN2047, // 11 bits |
| 51 |
PN4095, // 12 bits |
| 52 |
PN8191, // 13 bits |
| 53 |
PN_NONE, // 14 bits (TBD) |
| 54 |
PN_NONE, // 15 bits (TBD) |
| 55 |
PN65535, // 16 bits |
| 56 |
PN_NONE, // 17 bits (TBD) |
| 57 |
PN_NONE, // 18 bits (TBD) |
| 58 |
PN_NONE, // 19 bits (TBD) |
| 59 |
PN_NONE, // 20 bits (TBD) |
| 60 |
PN_NONE, // 21 bits (TBD) |
| 61 |
PN_NONE, // 22 bits (TBD) |
| 62 |
PN_NONE, // 23 bits (TBD) |
| 63 |
PN24BIT, // 24 bits |
| 64 |
PN_NONE, // 25 bits (TBD) |
| 65 |
PN_NONE, // 26 bits (TBD) |
| 66 |
PN_NONE, // 27 bits (TBD) |
| 67 |
PN_NONE, // 28 bits (TBD) |
| 68 |
PN_NONE, // 29 bits (TBD) |
| 69 |
PN_NONE, // 30 bits (TBD) |
| 70 |
PN_NONE, // 31 bits (TBD) |
| 71 |
PN32BIT // 32 bits |
| 72 |
}; |
| 73 |
|
| 74 |
void ProtoLFSR::Seek(int offsetBits) |
| 75 |
{ |
| 76 |
if (offsetBits < 0) |
| 77 |
{ |
| 78 |
if (!IsMirrored()) |
| 79 |
{ |
| 80 |
Mirror(); // reverse here does a -1 offset on its own, so adjust |
| 81 |
//offsetBits++; |
| 82 |
} |
| 83 |
} |
| 84 |
else if (IsMirrored()) |
| 85 |
{ |
| 86 |
Mirror(); // reverse here does a +1 offset on its own, so adjust |
| 87 |
//offsetBits--; |
| 88 |
} |
| 89 |
Shift(abs(offsetBits)); |
| 90 |
byte_mode = false; |
| 91 |
} // end ProtoLFSR::Seek() |
| 92 |
|
| 93 |
void ProtoLFSR::Shift(unsigned int count) |
| 94 |
{ |
| 95 |
for (unsigned int i = 0; i < count; i++) |
| 96 |
{ |
| 97 |
bool bit = (0 != (lfsr_state & 0x00000001)); |
| 98 |
lfsr_state >>= 1; |
| 99 |
//TRACE("shifted lfsr_state = 0x%04x (bit:%d) (poly: 0x%04x\n", lfsr_state, bit, lfsr_poly); |
| 100 |
if (bit) lfsr_state ^= lfsr_poly; |
| 101 |
} |
| 102 |
} // end ProtoLFSR::Shift() |
| 103 |
|
| 104 |
// This is used to "reverse load" the shift |
| 105 |
// register towards the state it would be |
| 106 |
// in to generate the sequence of bits |
| 107 |
// (used by the ProtoLFSR::Sync() method) |
| 108 |
void ProtoLFSR::LoadBit(bool bit) |
| 109 |
{ |
| 110 |
if (bit) lfsr_state ^= lfsr_poly; |
| 111 |
lfsr_state <<= 1; |
| 112 |
lfsr_state &= lfsr_mask; |
| 113 |
if (bit) lfsr_state |= 1; |
| 114 |
} // end ProtoLFSR::LoadBit() |
| 115 |
|
| 116 |
// This sets the LFSR to the state it would be in _before_ |
| 117 |
// generating the first "lfsr_bits" (register length) of bits |
| 118 |
// provided in the "buffer". This can be used to "sync" the |
| 119 |
// LFSR to a received sequence of bits. |
| 120 |
bool ProtoLFSR::Sync(const char* buffer, unsigned int buflen, unsigned int bitOffset) |
| 121 |
{ |
| 122 |
if ((buflen << 3) < (lfsr_bits + bitOffset)) return false; |
| 123 |
Reset(0); |
| 124 |
for (int i = bitOffset+lfsr_bits-1; i >= (int)bitOffset; i--) |
| 125 |
LoadBit(GetBit(buffer, i)); |
| 126 |
return true; |
| 127 |
} // end ProtoLFSR::Sync() |
| 128 |
|
| 129 |
UINT32 ProtoLFSR::MirrorBits(UINT32 word, unsigned int numBits) |
| 130 |
{ |
| 131 |
UINT32 bit = 0x00000001 << (numBits - 1); |
| 132 |
UINT32 mbit = 1; |
| 133 |
UINT32 mirrorWord = 0; |
| 134 |
while (0 != bit) |
| 135 |
{ |
| 136 |
if (0 != (bit & word)) |
| 137 |
mirrorWord |= mbit; |
| 138 |
mbit <<= 1; |
| 139 |
bit >>= 1; |
| 140 |
} |
| 141 |
return mirrorWord; |
| 142 |
} // end ProtoLFSR::MirrorBits() |
| 143 |
|
| 144 |
// Mirror the generator polynomial and state to generate |
| 145 |
// the time-reversed version of the sequence |
| 146 |
void ProtoLFSR::Mirror() |
| 147 |
{ |
| 148 |
// 1) "Mirror" the polynomial |
| 149 |
// Starting at most significant bit, mirror |
| 150 |
// all except most significant bit |
| 151 |
// (which is always set) |
| 152 |
UINT32 mirrorPoly = MirrorBits(lfsr_poly, lfsr_bits - 1); |
| 153 |
// Set the most significant bit |
| 154 |
mirrorPoly |= 0x00000001 << (lfsr_bits - 1); |
| 155 |
lfsr_poly = mirrorPoly; |
| 156 |
// 2) "Mirror" the shift register state |
| 157 |
lfsr_state = MirrorBits(lfsr_state, lfsr_bits); |
| 158 |
is_mirrored = is_mirrored ? false : true; |
| 159 |
} // end ProtoLFSR::Mirror() |
| 160 |
|
| 161 |
bool ProtoLFSR::GetNextBit() |
| 162 |
{ |
| 163 |
//TRACE("lfsr_state = 0x%04x\n", lfsr_state); |
| 164 |
byte_mode = false; |
| 165 |
if (IsMirrored()) |
| 166 |
{ |
| 167 |
Mirror(); |
| 168 |
Shift(); |
| 169 |
} |
| 170 |
bool bit = (0 != (lfsr_state & 0x00000001)); |
| 171 |
Shift(); |
| 172 |
return bit; |
| 173 |
} // end ProtoLFSR:::GetNextBit() |
| 174 |
|
| 175 |
UINT8 ProtoLFSR::GetNextByte() |
| 176 |
{ |
| 177 |
if (IsMirrored()) |
| 178 |
{ |
| 179 |
Shift(); |
| 180 |
if (byte_mode) |
| 181 |
{ |
| 182 |
GetNextBit(); |
| 183 |
Shift(7); |
| 184 |
} |
| 185 |
} |
| 186 |
UINT8 nextByte = GetNextBit() ? 0x01 : 0x00; |
| 187 |
for (int i = 1; i < 8; i++) |
| 188 |
{ |
| 189 |
nextByte <<= 1; |
| 190 |
if (GetNextBit()) nextByte |= 0x01; |
| 191 |
} |
| 192 |
byte_mode = true; |
| 193 |
return nextByte; |
| 194 |
} // end ProtoLFSR:::GetNextByte() |
| 195 |
|
| 196 |
|
| 197 |
bool ProtoLFSR::GetPrevBit() |
| 198 |
{ |
| 199 |
byte_mode = false; |
| 200 |
if (!IsMirrored()) |
| 201 |
{ |
| 202 |
Mirror(); |
| 203 |
Shift(); |
| 204 |
} |
| 205 |
bool bit = (0 != (lfsr_state & 0x000000001)); |
| 206 |
Shift(); |
| 207 |
return bit; |
| 208 |
} // end ProtoLFSR::GetPrevBit() |
| 209 |
|
| 210 |
UINT8 ProtoLFSR::GetPrevByte() |
| 211 |
{ |
| 212 |
if (!IsMirrored()) |
| 213 |
{ |
| 214 |
Shift(); |
| 215 |
if (byte_mode) |
| 216 |
{ |
| 217 |
GetPrevBit(); |
| 218 |
Shift(7); |
| 219 |
} |
| 220 |
} |
| 221 |
UINT8 prevByte = GetPrevBit() ? 0x80 : 0x00; |
| 222 |
for (int i = 1; i < 8; i++) |
| 223 |
{ |
| 224 |
prevByte >>= 1; |
| 225 |
if (GetPrevBit()) prevByte |= 0x80; |
| 226 |
} |
| 227 |
byte_mode = true; |
| 228 |
return prevByte; |
| 229 |
} // end ProtoLFSR::GetPrevByte() |
| 230 |
|
| 231 |
void ProtoLFSR::FillBuffer(char* buffer, unsigned int buflen) |
| 232 |
{ |
| 233 |
for (unsigned int i = 0; i < buflen; i++) |
| 234 |
buffer[i] = GetNextByte(); |
| 235 |
} // end ProtoLFSR::FillBuffer() |
| 236 |
|
| 237 |
|
| 238 |
// This function searches for an m-sequence generator polynomial |
| 239 |
// for a given shift register size of "m" bits |
| 240 |
UINT32 ProtoLFSR::PolynomialSearch(unsigned int m) |
| 241 |
{ |
| 242 |
const UINT32 LEN = 0x00000001 << m; |
| 243 |
|
| 244 |
char** seq = new char*[LEN]; |
| 245 |
if (NULL == seq) |
| 246 |
{ |
| 247 |
PLOG(PL_ERROR, "ProtoLFSR::PolynomialSearch() new 'seq' error: %s", GetErrorString()); |
| 248 |
return 0; |
| 249 |
} |
| 250 |
for (UINT32 i = 0; i < LEN; i++) |
| 251 |
{ |
| 252 |
seq[i] = new char[LEN >> 3]; |
| 253 |
if (NULL == seq[i]) |
| 254 |
{ |
| 255 |
PLOG(PL_ERROR, "ProtoLFSR::PolynomialSearch() new 'seq[%lu] error: %s", |
| 256 |
(unsigned long)i, GetErrorString()); |
| 257 |
for (UINT32 j = 0; j < i; j++) |
| 258 |
delete[] seq[j]; |
| 259 |
delete[] seq; |
| 260 |
return 0; |
| 261 |
} |
| 262 |
} |
| 263 |
|
| 264 |
UINT32 maxPoly = 0; |
| 265 |
unsigned int maxMin = 0; |
| 266 |
|
| 267 |
// min possible poly has bit "m-1" set |
| 268 |
UINT32 polyMin = LEN >> 1; |
| 269 |
// max possible poly has all "m" bits set |
| 270 |
UINT32 polyMax = 0xffffffff; |
| 271 |
polyMax >>= (32 - m); |
| 272 |
|
| 273 |
for (UINT32 poly = polyMin; poly <= polyMax; poly++) |
| 274 |
{ |
| 275 |
for (unsigned int i = 0; i < LEN; i++) |
| 276 |
{ |
| 277 |
ProtoLFSR lfsr((ProtoLFSR::Polynomial)poly); |
| 278 |
lfsr.Seek(i); |
| 279 |
lfsr.FillBuffer(seq[i], LEN >> 3); |
| 280 |
} |
| 281 |
|
| 282 |
unsigned int wtMin = 0xffffffff; |
| 283 |
//unsigned int offset = 0; |
| 284 |
for (unsigned int i = 1; i < LEN-1; i++) |
| 285 |
{ |
| 286 |
unsigned int wt = 0; |
| 287 |
for (unsigned int j = 0; j < (LEN >> 3); j++) |
| 288 |
{ |
| 289 |
unsigned char delta = (unsigned char)(seq[0][j] ^ seq[i][j]); |
| 290 |
wt += ProtoBitmask::GetWeight(delta); |
| 291 |
} |
| 292 |
if (wt < wtMin) |
| 293 |
{ |
| 294 |
wtMin = wt; |
| 295 |
//offset = i; |
| 296 |
} |
| 297 |
} |
| 298 |
if (wtMin > maxMin) |
| 299 |
{ |
| 300 |
maxMin = wtMin; |
| 301 |
maxPoly = poly; |
| 302 |
} |
| 303 |
} |
| 304 |
for (UINT32 j = 0; j < LEN; j++) |
| 305 |
delete[] seq[j]; |
| 306 |
delete[] seq; |
| 307 |
|
| 308 |
return maxPoly; |
| 309 |
} // end ProtoLFSR::PolynomialSearch() |
| 310 |
|
| 311 |
|
| 312 |
ProtoLFSRX::ProtoLFSRX() |
| 313 |
: lfsrx_poly(NULL), lfsrx_state(NULL), |
| 314 |
lfsrx_bits(0), lfsrx_words(0), lfsrx_mask(0), |
| 315 |
is_mirrored(false), byte_mode(false) |
| 316 |
{ |
| 317 |
} |
| 318 |
|
| 319 |
ProtoLFSRX::~ProtoLFSRX() |
| 320 |
{ |
| 321 |
if (NULL != lfsrx_poly) |
| 322 |
{ |
| 323 |
delete[] lfsrx_poly; |
| 324 |
delete[] lfsrx_state; |
| 325 |
lfsrx_poly = NULL; |
| 326 |
} |
| 327 |
} |
| 328 |
|
| 329 |
bool ProtoLFSRX::SetPolynomial(const UINT32* polynomial, |
| 330 |
unsigned int numBits, |
| 331 |
const UINT32* initialState, |
| 332 |
bool reverse) |
| 333 |
{ |
| 334 |
if (NULL != lfsrx_poly) |
| 335 |
{ |
| 336 |
delete[] lfsrx_poly; |
| 337 |
delete[] lfsrx_state; |
| 338 |
} |
| 339 |
lfsrx_state = NULL; |
| 340 |
lfsrx_bits = lfsrx_words = 0; |
| 341 |
lfsrx_mask = 0; |
| 342 |
is_mirrored = byte_mode = false; |
| 343 |
// Determine how many UINT32 "words" to allocate? |
| 344 |
unsigned int numWords = numBits >> 5; |
| 345 |
if (0 != (numBits & 0x01f)) numWords++; |
| 346 |
|
| 347 |
if ((NULL == polynomial) || (0 == numWords)) |
| 348 |
{ |
| 349 |
lfsrx_poly = NULL; // LFSR is being cleared |
| 350 |
return true; |
| 351 |
} |
| 352 |
|
| 353 |
if (NULL == (lfsrx_poly = new UINT32[numWords])) |
| 354 |
{ |
| 355 |
PLOG(PL_ERROR, "ProtoLFSRX::SetPolynomial() new lfsrx_poly error: %s\n", GetErrorString()); |
| 356 |
return false; |
| 357 |
} |
| 358 |
if (NULL == (lfsrx_state = new UINT32[numWords])) |
| 359 |
{ |
| 360 |
PLOG(PL_ERROR, "ProtoLFSRX::SetPolynomial() new lfsrx_poly error: %s\n", GetErrorString()); |
| 361 |
delete[] lfsrx_poly; |
| 362 |
lfsrx_poly = NULL; |
| 363 |
return false; |
| 364 |
} |
| 365 |
lfsrx_bits = numBits; |
| 366 |
lfsrx_words = numWords; |
| 367 |
lfsrx_mask = (UINT32)0xffffffff; |
| 368 |
lfsrx_mask >>= (32 - (numBits & 0x1f)); // bitmask for most significant word |
| 369 |
|
| 370 |
//TRACE("lfsrx_mask = 0x%04x\n", lfsrx_mask); |
| 371 |
|
| 372 |
// Copy polynomial and set initial state |
| 373 |
memcpy(lfsrx_poly, polynomial, numWords*sizeof(UINT32)); |
| 374 |
|
| 375 |
if (NULL != initialState) |
| 376 |
memcpy(lfsrx_state, initialState, numWords*sizeof(UINT32)); |
| 377 |
else |
| 378 |
memset(lfsrx_state, 0xff, numWords*sizeof(UINT32)); |
| 379 |
lfsrx_state[lfsrx_words-1] &= lfsrx_mask; |
| 380 |
|
| 381 |
//TRACE("initial lfsrx_state = 0x%04x\n", lfsrx_state[0]); |
| 382 |
|
| 383 |
if (reverse) |
| 384 |
{ |
| 385 |
Mirror(); |
| 386 |
is_mirrored = false; |
| 387 |
} |
| 388 |
|
| 389 |
return true; |
| 390 |
} // end ProtoLFSRX::SetPolynomial() |
| 391 |
|
| 392 |
void ProtoLFSRX::Reset(UINT32* initialState) |
| 393 |
{ |
| 394 |
byte_mode = false; |
| 395 |
if (IsMirrored()) Mirror(); |
| 396 |
|
| 397 |
if (NULL != initialState) |
| 398 |
memcpy(lfsrx_state, initialState, lfsrx_words*sizeof(UINT32)); |
| 399 |
else |
| 400 |
memset(lfsrx_state, 0xff, lfsrx_words*sizeof(UINT32)); |
| 401 |
lfsrx_state[lfsrx_words-1] &= lfsrx_mask; |
| 402 |
|
| 403 |
} // end ProtoLFSRX::Reset() |
| 404 |
|
| 405 |
// This uses the Berlekamp-Massey algorithm to compute a polynomial |
| 406 |
// from the input bit sequence in the "buffer" |
| 407 |
bool ProtoLFSRX::ComputePolynomial(const char* buffer, int numBits) |
| 408 |
{ |
| 409 |
// Destroy existing polynomial and state if applicable |
| 410 |
if (NULL != lfsrx_poly) |
| 411 |
{ |
| 412 |
delete[] lfsrx_poly; |
| 413 |
delete[] lfsrx_state; |
| 414 |
} |
| 415 |
lfsrx_state = NULL; |
| 416 |
lfsrx_bits = lfsrx_words = 0; |
| 417 |
lfsrx_mask = 0; |
| 418 |
is_mirrored = byte_mode = false; |
| 419 |
|
| 420 |
// We use "UINT32" words for our registers |
| 421 |
// TBD - Is allocating these temp arrays off the stack OK? (i.e. if "numBits" is large?) |
| 422 |
unsigned int numWords = numBits >> 5; |
| 423 |
if (0 != (numBits & 0x1f)) numWords++; // round up as needed |
| 424 |
UINT32* c = new UINT32[numWords]; |
| 425 |
UINT32* b = new UINT32[numWords]; |
| 426 |
UINT32* t = new UINT32[numWords]; |
| 427 |
if ((NULL == c) || (NULL == b) || (NULL == t)) |
| 428 |
{ |
| 429 |
PLOG(PL_ERROR, "ProtoLFSRX::ComputePolynomial() new UINT32[%u] error(s)\n", |
| 430 |
numWords, GetErrorString()); |
| 431 |
if (NULL != c) delete[] c; |
| 432 |
if (NULL != b) delete[] b; |
| 433 |
if (NULL != t) delete[] t; |
| 434 |
return false; |
| 435 |
} |
| 436 |
|
| 437 |
memset(c, 0, numWords*sizeof(UINT32)); |
| 438 |
memset(b, 0, numWords*sizeof(UINT32)); |
| 439 |
|
| 440 |
SetBit32(c, 0, true); |
| 441 |
SetBit32(b, 0, true); |
| 442 |
|
| 443 |
int length = 0; |
| 444 |
int m = -1; |
| 445 |
bool linearityWarning = false; |
| 446 |
|
| 447 |
// Process input sequence, bit by bit |
| 448 |
for (int index = 0; index < numBits; index++) |
| 449 |
{ |
| 450 |
// compute discrepancy 'd ' |
| 451 |
bool d = ProtoLFSR::GetBit(buffer, index); |
| 452 |
for (int i = 1; i <= length; ++i) |
| 453 |
d ^= GetBit32(c, i) && ProtoLFSR::GetBit(buffer, index-i); |
| 454 |
// recompute sequence if necessary |
| 455 |
if (d) |
| 456 |
{ |
| 457 |
// Copy c[] to t[] |
| 458 |
for (int i = 0; i <= index; i++) |
| 459 |
SetBit32(t, i, GetBit32(c, i)); |
| 460 |
|
| 461 |
int deltaM = index - m; |
| 462 |
for (int j = 0; j <= (m+1); j++) |
| 463 |
{ |
| 464 |
int i = deltaM + j; |
| 465 |
SetBit32(c, i, GetBit32(c, i) ^ GetBit32(b, j)); |
| 466 |
} |
| 467 |
if (length <= index/2) |
| 468 |
{ |
| 469 |
// we have a jump in linear complexity -- check if unusual |
| 470 |
if (!linearityWarning && ((index/2 - length) > 6) && (length > 2)) |
| 471 |
linearityWarning = true; |
| 472 |
length = index + 1 - length; |
| 473 |
m = index; |
| 474 |
// Copy t[] to b[] |
| 475 |
for (int i = 0; i <= index; i++) |
| 476 |
SetBit32(b, i, GetBit32(t, i)); |
| 477 |
} |
| 478 |
} |
| 479 |
} // end while (index < numBits) |
| 480 |
|
| 481 |
// At this point the c[] array has our polynomial bits and |
| 482 |
// 'length' is the rough register length. Just need to |
| 483 |
// tweak things a little bit for our ProtoLFSR register conventions |
| 484 |
// Do a bit by bit check to determine actual register length |
| 485 |
// (Note that bit zero isn't included (always one) |
| 486 |
int polyBits = 0; |
| 487 |
for (int i = 1; i <= length; i++) |
| 488 |
if (GetBit32(c, i)) polyBits = i; |
| 489 |
int polyWords = polyBits >> 5; |
| 490 |
if (0 != (polyBits & 0x1f)) polyWords++; |
| 491 |
// Allocate lfsr_poly array for shift register taps |
| 492 |
if (NULL == (lfsrx_poly = new UINT32[polyWords])) |
| 493 |
{ |
| 494 |
PLOG(PL_ERROR, "ProtoLFSRX::ComputePolynomial() new lfsrx_poly[%d] error: %s\n", |
| 495 |
polyWords, GetErrorString()); |
| 496 |
delete[] c; |
| 497 |
delete[] b; |
| 498 |
delete[] t; |
| 499 |
return false; |
| 500 |
} |
| 501 |
// Allocate corresponding lfsr_state for shift register contents |
| 502 |
if (NULL == (lfsrx_state = new UINT32[polyWords])) |
| 503 |
{ |
| 504 |
PLOG(PL_ERROR, "ProtoLFSRX::ComputePolynomial() new lfsrx_state[%d] error: %s\n", |
| 505 |
polyWords, GetErrorString()); |
| 506 |
delete[] lfsrx_poly; |
| 507 |
lfsrx_poly = NULL; |
| 508 |
delete[] c; |
| 509 |
delete[] b; |
| 510 |
delete[] t; |
| 511 |
return false; |
| 512 |
} |
| 513 |
|
| 514 |
// We copy c[] shifted by one bit (skipping alwast set bit zero) |
| 515 |
for (int i = 1; i <= length; i++) |
| 516 |
SetBit32(lfsrx_poly, i-1, GetBit32(c, i)); |
| 517 |
lfsrx_bits = polyBits; |
| 518 |
lfsrx_words = polyWords; |
| 519 |
lfsrx_mask = (UINT32)0xffffffff; |
| 520 |
lfsrx_mask >>= (32 - (polyBits & 0x1f)); // bitmask for most significant word |
| 521 |
|
| 522 |
// Set a valid lfsr_state (all ones) |
| 523 |
memset(lfsrx_state, 0xff, lfsrx_words*sizeof(UINT32)); |
| 524 |
lfsrx_state[lfsrx_words-1] &= lfsrx_mask; |
| 525 |
|
| 526 |
// Now we "Sync()" to the input "buffer" bit stream by using "polyBits" of it |
| 527 |
// to set the initial state so it will regenerate the input "buffer" bits |
| 528 |
// and the "Seek()" backwards so |
| 529 |
unsigned int syncBytes = polyBits >> 3; |
| 530 |
if (0 != (polyBits & 0x07)) syncBytes++; |
| 531 |
Sync(buffer, syncBytes); |
| 532 |
|
| 533 |
// TBD - put a test here to make sure the resultant LFSR actually regenerates the |
| 534 |
// input "buffer" sequence. If not, the input was not linear! |
| 535 |
// A) temporarily save our "lfsrx_state" in 'c' |
| 536 |
bool result = true; |
| 537 |
memcpy(c, lfsrx_state, lfsrx_words*sizeof(UINT32)); |
| 538 |
// B) Check input sequence match to lfsr output |
| 539 |
for (int i = 0; i < numBits; i++) |
| 540 |
{ |
| 541 |
if (ProtoLFSR::GetBit(buffer, i) != GetNextBit()) |
| 542 |
{ |
| 543 |
PLOG(PL_ERROR, "ProtoLFSRX::ComputePolynomial() error: non-linear input sequence\n"); |
| 544 |
linearityWarning = false; |
| 545 |
result = false; |
| 546 |
break; |
| 547 |
} |
| 548 |
} |
| 549 |
// C) set state back to sync point |
| 550 |
memcpy(lfsrx_state, c, lfsrx_words*sizeof(UINT32)); |
| 551 |
|
| 552 |
if (linearityWarning) |
| 553 |
PLOG(PL_WARN, "ProtoLFSRX::ComputePolynomial() warning: possible non-linear input sequence!\n"); |
| 554 |
delete[] c; |
| 555 |
delete[] b; |
| 556 |
delete[] t; |
| 557 |
return result; |
| 558 |
} // end ProtoLFSRX::ComputePolynomial() |
| 559 |
|
| 560 |
|
| 561 |
void ProtoLFSRX::Seek(int offsetBits) |
| 562 |
{ |
| 563 |
if (offsetBits < 0) |
| 564 |
{ |
| 565 |
if (!IsMirrored()) |
| 566 |
{ |
| 567 |
Mirror(); // reverse here does a -1 offset on its own, so adjust |
| 568 |
//offsetBits++; |
| 569 |
} |
| 570 |
} |
| 571 |
else if (IsMirrored()) |
| 572 |
{ |
| 573 |
Mirror(); // reverse here does a +1 offset on its own, so adjust |
| 574 |
//offsetBits--; |
| 575 |
} |
| 576 |
Shift(abs(offsetBits)); |
| 577 |
byte_mode = false; |
| 578 |
} // end ProtoLFSRX::Seek() |
| 579 |
|
| 580 |
bool ProtoLFSRX::GetNextBit() |
| 581 |
{ |
| 582 |
//TRACE("lfsrx_state = 0x%04x\n", lfsrx_state[0]); |
| 583 |
byte_mode = false; |
| 584 |
if (IsMirrored()) |
| 585 |
{ |
| 586 |
Mirror(); |
| 587 |
Shift(); |
| 588 |
} |
| 589 |
bool bit = (0 != (lfsrx_state[0] & 0x00000001)); |
| 590 |
Shift(); |
| 591 |
return bit; |
| 592 |
} // end ProtoLFSRX:::GetNextBit() |
| 593 |
|
| 594 |
UINT8 ProtoLFSRX::GetNextByte() |
| 595 |
{ |
| 596 |
if (IsMirrored()) |
| 597 |
{ |
| 598 |
Shift(); |
| 599 |
if (byte_mode) |
| 600 |
{ |
| 601 |
GetNextBit(); |
| 602 |
Shift(7); |
| 603 |
} |
| 604 |
} |
| 605 |
UINT8 nextByte = GetNextBit() ? 0x01 : 0x00; |
| 606 |
for (int i = 1; i < 8; i++) |
| 607 |
{ |
| 608 |
nextByte <<= 1; |
| 609 |
if (GetNextBit()) nextByte |= 0x01; |
| 610 |
} |
| 611 |
byte_mode = true; |
| 612 |
return nextByte; |
| 613 |
} // end ProtoLFSRX:::GetNextByte() |
| 614 |
|
| 615 |
|
| 616 |
bool ProtoLFSRX::GetPrevBit() |
| 617 |
{ |
| 618 |
byte_mode = false; |
| 619 |
if (!IsMirrored()) |
| 620 |
{ |
| 621 |
Mirror(); |
| 622 |
Shift(); |
| 623 |
} |
| 624 |
bool bit = (0 != (lfsrx_state[0] & 0x000000001)); |
| 625 |
Shift(); |
| 626 |
return bit; |
| 627 |
} // end ProtoLFSRX::GetPrevBit() |
| 628 |
|
| 629 |
UINT8 ProtoLFSRX::GetPrevByte() |
| 630 |
{ |
| 631 |
if (!IsMirrored()) |
| 632 |
{ |
| 633 |
Shift(); |
| 634 |
if (byte_mode) |
| 635 |
{ |
| 636 |
GetPrevBit(); |
| 637 |
Shift(7); |
| 638 |
} |
| 639 |
} |
| 640 |
UINT8 prevByte = GetPrevBit() ? 0x80 : 0x00; |
| 641 |
for (int i = 1; i < 8; i++) |
| 642 |
{ |
| 643 |
prevByte >>= 1; |
| 644 |
if (GetPrevBit()) prevByte |= 0x80; |
| 645 |
} |
| 646 |
byte_mode = true; |
| 647 |
return prevByte; |
| 648 |
} // end ProtoLFSRX::GetPrevByte() |
| 649 |
|
| 650 |
void ProtoLFSRX::FillBuffer(char* buffer, unsigned int buflen) |
| 651 |
{ |
| 652 |
for (unsigned int i = 0; i < buflen; i++) |
| 653 |
buffer[i] = GetNextByte(); |
| 654 |
} // end ProtoLFSRX::FillBuffer() |
| 655 |
|
| 656 |
// This sets the LFSR to the state it would be in _before_ |
| 657 |
// generating the first "lfsr_bits" (register length) of bits |
| 658 |
// provided in the "buffer". This can be used to "sync" the |
| 659 |
// LFSR to a received sequence of bits. |
| 660 |
bool ProtoLFSRX::Sync(const char* buffer, unsigned int buflen, unsigned int bitOffset) |
| 661 |
{ |
| 662 |
if ((buflen << 3) < (lfsrx_bits + bitOffset)) return false; |
| 663 |
|
| 664 |
// These 3 lines do a Reset() with an all 0's initial state |
| 665 |
byte_mode = false; |
| 666 |
if (IsMirrored()) Mirror(); |
| 667 |
memset(lfsrx_state, 0, lfsrx_words*sizeof(UINT32)); |
| 668 |
|
| 669 |
for (int i = bitOffset+lfsrx_bits-1; i >= (int)bitOffset; i--) |
| 670 |
LoadBit(ProtoLFSR::GetBit(buffer, i)); |
| 671 |
return true; |
| 672 |
} // end ProtoLFSRX::Sync() |
| 673 |
|
| 674 |
// This is used to "reverse load" the shift |
| 675 |
// register towards the state it would be |
| 676 |
// in to generate the sequence of bits |
| 677 |
// (used by the ProtoLFSR::Sync() method) |
| 678 |
void ProtoLFSRX::LoadBit(bool bit) |
| 679 |
{ |
| 680 |
if (bit) // the bit shifted in is set |
| 681 |
{ for (unsigned int i = 0; i < lfsrx_words; i++) |
| 682 |
lfsrx_state[i] ^= lfsrx_poly[i]; |
| 683 |
} |
| 684 |
|
| 685 |
// This loop shifts the lfsrx_state register to the "left" |
| 686 |
UINT32* statePtr = lfsrx_state; |
| 687 |
for (unsigned int i = 0; i < lfsrx_words; i++) |
| 688 |
{ |
| 689 |
bool saveBit = (0 != (*statePtr & 0x80000000)); |
| 690 |
*statePtr <<= 1; |
| 691 |
if (bit) *statePtr |= 0x00000001; |
| 692 |
bit = saveBit; |
| 693 |
statePtr++; |
| 694 |
} |
| 695 |
// Mask the most significant word |
| 696 |
lfsrx_state[lfsrx_words - 1] &= lfsrx_mask; |
| 697 |
} // end ProtoLFSRX::LoadBit() |
| 698 |
|
| 699 |
void ProtoLFSRX::Shift(unsigned int count) |
| 700 |
{ |
| 701 |
for (unsigned int i = 0; i < count; i++) |
| 702 |
{ |
| 703 |
// This loop shifts the lfsrx_state register to the "right" |
| 704 |
bool bit = false; |
| 705 |
UINT32* statePtr = lfsrx_state + lfsrx_words - 1; |
| 706 |
for (unsigned int i = 0; i < lfsrx_words; i++) |
| 707 |
{ |
| 708 |
bool saveBit = (0 != (*statePtr & 0x00000001)); |
| 709 |
*statePtr >>= 1; |
| 710 |
if (bit) *statePtr |= 0x80000000; |
| 711 |
bit = saveBit; |
| 712 |
statePtr--; |
| 713 |
} |
| 714 |
//TRACE("shifted lfsrx_state = 0x%04x (bit:%d poly: 0x%04x)\n", lfsrx_state[0], bit, lfsrx_poly[0]); |
| 715 |
if (bit) // the bit shifted out of the register was set |
| 716 |
{ for (unsigned int i = 0; i < lfsrx_words; i++) |
| 717 |
lfsrx_state[i] ^= lfsrx_poly[i]; |
| 718 |
} |
| 719 |
} |
| 720 |
} // end ProtoLFSRX::Shift() |
| 721 |
|
| 722 |
// Mirror the generator polynomial and state to generate |
| 723 |
// the time-reversed version of the sequence |
| 724 |
void ProtoLFSRX::Mirror() |
| 725 |
{ |
| 726 |
// Note this could be implemented more efficiently for the |
| 727 |
// case of 0 == (lfsrx_bits % 32) (TBD - do this) |
| 728 |
// 1) "Mirror" the polynomial |
| 729 |
// Starting at 2nd most significant bit, mirror the bits |
| 730 |
// (most significant bit is always set) |
| 731 |
unsigned int i = 0; // least significant bit |
| 732 |
unsigned int j = lfsrx_bits - 2; // 2nd most significant bit |
| 733 |
while (i < j) |
| 734 |
{ |
| 735 |
// Swap bit[i] and bit[j] |
| 736 |
bool jbit = GetBit32(lfsrx_poly, j); |
| 737 |
SetBit32(lfsrx_poly, j, GetBit32(lfsrx_poly, i)); |
| 738 |
SetBit32(lfsrx_poly, i, jbit); |
| 739 |
i++; |
| 740 |
j--; |
| 741 |
} |
| 742 |
// Note the most significant bit was left set. |
| 743 |
|
| 744 |
// 2) "Mirror" the entire shift register state |
| 745 |
i = 0; // least significant bit |
| 746 |
j = lfsrx_bits - 1; // most significant bit |
| 747 |
while (i < j) |
| 748 |
{ |
| 749 |
// Swap bit[i] and bit[j] |
| 750 |
bool jbit = GetBit32(lfsrx_state, j); |
| 751 |
SetBit32(lfsrx_state, j, GetBit32(lfsrx_state, i)); |
| 752 |
SetBit32(lfsrx_state, i, jbit); |
| 753 |
i++; |
| 754 |
j--; |
| 755 |
} |
| 756 |
is_mirrored = is_mirrored ? false : true; |
| 757 |
} // end ProtoLFSRX::Mirror() |