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     ! 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: }