Home | History | Annotate | Line # | Download | only in isc 
      1 /*	$NetBSD: lfsr.c,v 1.1 2024/02/18 20:57:49 christos Exp $	*/
      2 
      3 /*
      4  * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
      5  *
      6  * SPDX-License-Identifier: MPL-2.0
      7  *
      8  * This Source Code Form is subject to the terms of the Mozilla Public
      9  * License, v. 2.0.  If a copy of the MPL was not distributed with this
     10  * file, you can obtain one at https://mozilla.org/MPL/2.0/.
     11  *
     12  * See the COPYRIGHT file distributed with this work for additional
     13  * information regarding copyright ownership.
     14  */
     15 
     16 /*! \file */
     17 
     18 #include <inttypes.h>
     19 #include <stddef.h>
     20 #include <stdlib.h>
     21 
     22 #include <isc/assertions.h>
     23 #include <isc/lfsr.h>
     24 #include <isc/util.h>
     25 
     26 #define VALID_LFSR(x) (x != NULL)
     27 
     28 void
     29 isc_lfsr_init(isc_lfsr_t *lfsr, uint32_t state, unsigned int bits, uint32_t tap,
     30 	      unsigned int count, isc_lfsrreseed_t reseed, void *arg) {
     31 	REQUIRE(VALID_LFSR(lfsr));
     32 	REQUIRE(8 <= bits && bits <= 32);
     33 	REQUIRE(tap != 0);
     34 
     35 	lfsr->state = state;
     36 	lfsr->bits = bits;
     37 	lfsr->tap = tap;
     38 	lfsr->count = count;
     39 	lfsr->reseed = reseed;
     40 	lfsr->arg = arg;
     41 
     42 	if (count == 0 && reseed != NULL) {
     43 		reseed(lfsr, arg);
     44 	}
     45 	if (lfsr->state == 0) {
     46 		lfsr->state = 0xffffffffU >> (32 - lfsr->bits);
     47 	}
     48 }
     49 
     50 /*!
     51  * Return the next state of the lfsr.
     52  */
     53 static uint32_t
     54 lfsr_generate(isc_lfsr_t *lfsr) {
     55 	/*
     56 	 * If the previous state is zero, we must fill it with something
     57 	 * here, or we will begin to generate an extremely predictable output.
     58 	 *
     59 	 * First, give the reseed function a crack at it.  If the state is
     60 	 * still 0, set it to all ones.
     61 	 */
     62 	if (lfsr->state == 0) {
     63 		if (lfsr->reseed != NULL) {
     64 			lfsr->reseed(lfsr, lfsr->arg);
     65 		}
     66 		if (lfsr->state == 0) {
     67 			lfsr->state = 0xffffffffU >> (32 - lfsr->bits);
     68 		}
     69 	}
     70 
     71 	if (lfsr->state & 0x01) {
     72 		lfsr->state = (lfsr->state >> 1) ^ lfsr->tap;
     73 		return (1);
     74 	} else {
     75 		lfsr->state >>= 1;
     76 		return (0);
     77 	}
     78 }
     79 
     80 void
     81 isc_lfsr_generate(isc_lfsr_t *lfsr, void *data, unsigned int count) {
     82 	unsigned char *p;
     83 	unsigned int bit;
     84 	unsigned int byte;
     85 
     86 	REQUIRE(VALID_LFSR(lfsr));
     87 	REQUIRE(data != NULL);
     88 	REQUIRE(count > 0);
     89 
     90 	p = data;
     91 	byte = count;
     92 
     93 	while (byte--) {
     94 		*p = 0;
     95 		for (bit = 0; bit < 7; bit++) {
     96 			*p |= lfsr_generate(lfsr);
     97 			*p <<= 1;
     98 		}
     99 		*p |= lfsr_generate(lfsr);
    100 		p++;
    101 	}
    102 
    103 	if (lfsr->count != 0 && lfsr->reseed != NULL) {
    104 		if (lfsr->count <= count * 8) {
    105 			lfsr->reseed(lfsr, lfsr->arg);
    106 		} else {
    107 			lfsr->count -= (count * 8);
    108 		}
    109 	}
    110 }
    111 
    112 static uint32_t
    113 lfsr_skipgenerate(isc_lfsr_t *lfsr, unsigned int skip) {
    114 	while (skip--) {
    115 		(void)lfsr_generate(lfsr);
    116 	}
    117 
    118 	(void)lfsr_generate(lfsr);
    119 
    120 	return (lfsr->state);
    121 }
    122 
    123 /*
    124  * Skip "skip" states in "lfsr".
    125  */
    126 void
    127 isc_lfsr_skip(isc_lfsr_t *lfsr, unsigned int skip) {
    128 	REQUIRE(VALID_LFSR(lfsr));
    129 
    130 	while (skip--) {
    131 		(void)lfsr_generate(lfsr);
    132 	}
    133 }
    134 
    135 /*
    136  * Skip states in lfsr1 and lfsr2 using the other's current state.
    137  * Return the final state of lfsr1 ^ lfsr2.
    138  */
    139 uint32_t
    140 isc_lfsr_generate32(isc_lfsr_t *lfsr1, isc_lfsr_t *lfsr2) {
    141 	uint32_t state1, state2;
    142 	uint32_t skip1, skip2;
    143 
    144 	REQUIRE(VALID_LFSR(lfsr1));
    145 	REQUIRE(VALID_LFSR(lfsr2));
    146 
    147 	skip1 = lfsr1->state & 0x01;
    148 	skip2 = lfsr2->state & 0x01;
    149 
    150 	/* cross-skip. */
    151 	state1 = lfsr_skipgenerate(lfsr1, skip2);
    152 	state2 = lfsr_skipgenerate(lfsr2, skip1);
    153 
    154 	return (state1 ^ state2);
    155 }
    156