Return to lfsr.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / ntp / lib / isc

Annotation of embedaddon/ntp/lib/isc/lfsr.c, revision 1.1.1.1

1.1       misho       1: /*
                      2:  * Copyright (C) 2004, 2005, 2007  Internet Systems Consortium, Inc. ("ISC")
                      3:  * Copyright (C) 1999-2002  Internet Software Consortium.
                      4:  *
                      5:  * Permission to use, copy, modify, and/or distribute this software for any
                      6:  * purpose with or without fee is hereby granted, provided that the above
                      7:  * copyright notice and this permission notice appear in all copies.
                      8:  *
                      9:  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
                     10:  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
                     11:  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
                     12:  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
                     13:  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
                     14:  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
                     15:  * PERFORMANCE OF THIS SOFTWARE.
                     16:  */
                     17: 
                     18: /* $Id: lfsr.c,v 1.20 2007/06/19 23:47:17 tbox Exp $ */
                     19: 
                     20: /*! \file */
                     21: 
                     22: #include <config.h>
                     23: 
                     24: #include <stddef.h>
                     25: #include <stdlib.h>
                     26: 
                     27: #include <isc/assertions.h>
                     28: #include <isc/lfsr.h>
                     29: #include <isc/util.h>
                     30: 
                     31: #define VALID_LFSR(x)  (x != NULL)
                     32: 
                     33: void
                     34: isc_lfsr_init(isc_lfsr_t *lfsr, isc_uint32_t state, unsigned int bits,
                     35:              isc_uint32_t tap, unsigned int count,
                     36:              isc_lfsrreseed_t reseed, void *arg)
                     37: {
                     38:        REQUIRE(VALID_LFSR(lfsr));
                     39:        REQUIRE(8 <= bits && bits <= 32);
                     40:        REQUIRE(tap != 0);
                     41: 
                     42:        lfsr->state = state;
                     43:        lfsr->bits = bits;
                     44:        lfsr->tap = tap;
                     45:        lfsr->count = count;
                     46:        lfsr->reseed = reseed;
                     47:        lfsr->arg = arg;
                     48: 
                     49:        if (count == 0 && reseed != NULL)
                     50:                reseed(lfsr, arg);
                     51:        if (lfsr->state == 0)
                     52:                lfsr->state = 0xffffffffU >> (32 - lfsr->bits);
                     53: }
                     54: 
                     55: /*!
                     56:  * Return the next state of the lfsr.
                     57:  */
                     58: static inline isc_uint32_t
                     59: lfsr_generate(isc_lfsr_t *lfsr)
                     60: {
                     61: 
                     62:        /*
                     63:         * If the previous state is zero, we must fill it with something
                     64:         * here, or we will begin to generate an extremely predictable output.
                     65:         *
                     66:         * First, give the reseed function a crack at it.  If the state is
                     67:         * still 0, set it to all ones.
                     68:         */
                     69:        if (lfsr->state == 0) {
                     70:                if (lfsr->reseed != NULL)
                     71:                        lfsr->reseed(lfsr, lfsr->arg);
                     72:                if (lfsr->state == 0)
                     73:                        lfsr->state = 0xffffffffU >> (32 - lfsr->bits);
                     74:        }
                     75: 
                     76:        if (lfsr->state & 0x01) {
                     77:                lfsr->state = (lfsr->state >> 1) ^ lfsr->tap;
                     78:                return (1);
                     79:        } else {
                     80:                lfsr->state >>= 1;
                     81:                return (0);
                     82:        }
                     83: }
                     84: 
                     85: void
                     86: isc_lfsr_generate(isc_lfsr_t *lfsr, void *data, unsigned int count)
                     87: {
                     88:        unsigned char *p;
                     89:        unsigned int bit;
                     90:        unsigned int byte;
                     91: 
                     92:        REQUIRE(VALID_LFSR(lfsr));
                     93:        REQUIRE(data != NULL);
                     94:        REQUIRE(count > 0);
                     95: 
                     96:        p = data;
                     97:        byte = count;
                     98: 
                     99:        while (byte--) {
                    100:                *p = 0;
                    101:                for (bit = 0; bit < 7; bit++) {
                    102:                        *p |= lfsr_generate(lfsr);
                    103:                        *p <<= 1;
                    104:                }
                    105:                *p |= lfsr_generate(lfsr);
                    106:                p++;
                    107:        }
                    108: 
                    109:        if (lfsr->count != 0 && lfsr->reseed != NULL) {
                    110:                if (lfsr->count <= count * 8)
                    111:                        lfsr->reseed(lfsr, lfsr->arg);
                    112:                else
                    113:                        lfsr->count -= (count * 8);
                    114:        }
                    115: }
                    116: 
                    117: static inline isc_uint32_t
                    118: lfsr_skipgenerate(isc_lfsr_t *lfsr, unsigned int skip)
                    119: {
                    120:        while (skip--)
                    121:                (void)lfsr_generate(lfsr);
                    122: 
                    123:        (void)lfsr_generate(lfsr);
                    124: 
                    125:        return (lfsr->state);
                    126: }
                    127: 
                    128: /*
                    129:  * Skip "skip" states in "lfsr".
                    130:  */
                    131: void
                    132: isc_lfsr_skip(isc_lfsr_t *lfsr, unsigned int skip)
                    133: {
                    134:        REQUIRE(VALID_LFSR(lfsr));
                    135: 
                    136:        while (skip--)
                    137:                (void)lfsr_generate(lfsr);
                    138: }
                    139: 
                    140: /*
                    141:  * Skip states in lfsr1 and lfsr2 using the other's current state.
                    142:  * Return the final state of lfsr1 ^ lfsr2.
                    143:  */
                    144: isc_uint32_t
                    145: isc_lfsr_generate32(isc_lfsr_t *lfsr1, isc_lfsr_t *lfsr2)
                    146: {
                    147:        isc_uint32_t state1, state2;
                    148:        isc_uint32_t skip1, skip2;
                    149: 
                    150:        REQUIRE(VALID_LFSR(lfsr1));
                    151:        REQUIRE(VALID_LFSR(lfsr2));
                    152: 
                    153:        skip1 = lfsr1->state & 0x01;
                    154:        skip2 = lfsr2->state & 0x01;
                    155: 
                    156:        /* cross-skip. */
                    157:        state1 = lfsr_skipgenerate(lfsr1, skip2);
                    158:        state2 = lfsr_skipgenerate(lfsr2, skip1);
                    159: 
                    160:        return (state1 ^ state2);
                    161: }