Return to lfsr.c CVS log

Up to [PGP] / pgp / src

Annotation of pgp/src/lfsr.c, revision 1.1

1.1     ! root        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: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.