home *** CD-ROM | disk | FTP | other *** search
/ Hacker Chronicles 2 / HACKER2.BIN / 1212.LFSR.C < prev    next >
Text File  |  1991-01-06  |  3KB  |  100 lines
  1. /*
  2. **    lfsr.c - Linear Feedback Shift Register (LFSR) routines.
  3. **    (c) 1988 Philip Zimmermann.  All rights reserved.
  4. **    10 Sep 88 -- revised 20 Jun 89
  5. */
  6.  
  7. #include "lfsr.h"    /* Linear Feedback Shift Register headers */
  8.  
  9. /* Calling routines must declare lfsr buffer and byte index into it.: */
  10. /* byte lfsr[256] = {0}; */
  11. /* byte rtail = 0;    /* points to 256, which is same as 0 */
  12.  
  13.  
  14. /*
  15. **    steplfsr256 - Step big linear feedback shift register (LFSR)
  16. **    256 cycles.  Use primitive polynomial:  X^255 + X^82 + X^0
  17. **    Actually runs 8 LFSR's in parallel, outputting a whole byte
  18. **    with each step.
  19. */
  20. void steplfsr256(register byteptr lfsr)
  21. {    register byte ltail;
  22.     register byte ltap0;
  23.     register byte ltap82;
  24.     register byte ltap255;
  25.     ltail = 0; ltap0 = 0; ltap82 = 82; ltap255 = 255;
  26.     do
  27.         lfsr[--ltail] = lfsr[ltap0--]^lfsr[ltap82--]^lfsr[ltap255--];
  28.     while (ltail);
  29. } /* steplfsr256 */
  30.  
  31.  
  32. /*
  33. **    getlfsr - get 1 byte from lfsr buffer.
  34. **    Calls steplfsr256() if necessary to replenish lfsr buffer.
  35. **
  36. **    getlfsr() is a #define in the header file "lfsr.h"
  37. */
  38.  
  39.  
  40. /*
  41. **    initlfsr - initialize linear feedback shift register
  42. **
  43. **    Since each of the 8 bits of the bytes in the LFSR array represents
  44. **    a separate independant LFSR, we must be sure the every one of the
  45. **    8 LFSRs have some 1's and 0's in it.  Therefore, an unmodified
  46. **    7-bit ASCII string is not an acceptable seed for the LFSR byte
  47. **    array, because the high bits are all zeros.  That's why we do a
  48. **    cumulative add on the seed bits, to mix the seed bits up between
  49. **    the 8 LFSRs.
  50. */
  51. void initlfsr(byteptr seed, short size, byteptr lfsr, byte *rtail)
  52. /*    seed is random number seed.
  53.     size is number of bytes in seed.
  54.     lfsr is pointer to 256-byte LFSR buffer.
  55.     *rtail is rtail index byte.
  56. */
  57. {    short i;
  58.     unsigned int c;
  59. #ifdef CHECKLFSR
  60.     byte check1,check0;    /* to ensure 1s and 0s mixed in each LFSR */
  61.     check0 = 0x00;        /* should end up as 0xff after ORing */
  62.     check1 = 0xff;        /* should end up as 0x00 after ANDing */
  63. #endif    /* CHECKLFSR */
  64.     *rtail = 0;        /* points to 256, which is same as 0 */
  65.     c = size;        /* makes seed "AAA" distinct from seed "AAAAAA" */
  66.     for (i=0; i<=255; i++)    /* make several seed copies across the LFSR */
  67.     {    c += seed[i % size];    /* cumulatively add the seed data */
  68.         lfsr[i] = c + (c>>8);    /* wraparound carry bits */
  69. #ifdef CHECKLFSR
  70.         check0 |= lfsr[i];    /* scan for all zeros in any LFSR row */
  71.         check1 &= lfsr[i];    /* scan for all ones in any LFSR row */
  72. #endif    /* CHECKLFSR */
  73.     }
  74. #ifdef CHECKLFSR
  75.     /* if any LFSR row contained all zeros, check0 will not be 0xff */
  76.     /* if any LFSR row contained all ones, check1 will not be 0x00 */
  77.     c = 0xFF & (check1 | ~check0);    /* should be 0x00 if all went OK. */
  78.     /* Now guarantee that all 8 LFSRs contain a mix of 1s and 0s... */
  79.     if (c) printf("\nLFSR check0=%2X check1=%2X. ",check0,check1);
  80.     lfsr[0] ^= c;        /* flip some faulty bits if we have to */
  81. #endif    /* CHECKLFSR */
  82. } /* initlfsr */
  83.  
  84.  
  85. /*
  86. **    stomplfsr - inverts about half the bits in an LFSR.
  87. **
  88. **    If the LFSR has a "rail" of almost all 0's or almost all 1's in
  89. **    the same bit position, it will perform poorly as a random number
  90. **    generator.  This function will probably fix this condition.
  91. */
  92. void stomplfsr(byteptr lfsr)
  93. /*    lfsr is pointer to 256-byte LFSR buffer. */
  94. {    byte i;
  95.     i=255;
  96.     while (i) *lfsr++ ^= i--;
  97. } /* stomplfsr */
  98.  
  99.  
  100.