Source-Changes-HG archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

[src/trunk]: src/sys/lib/libkern Remove never-used Mersenne twister from libk...



details:   https://anonhg.NetBSD.org/src/rev/a7aedf6e77f8
branches:  trunk
changeset: 967567:a7aedf6e77f8
user:      riastradh <riastradh%NetBSD.org@localhost>
date:      Sat Dec 14 17:23:47 2019 +0000

description:
Remove never-used Mersenne twister from libkern.

diffstat:

 sys/lib/libkern/Makefile.libkern |    4 +-
 sys/lib/libkern/libkern.h        |   14 +--
 sys/lib/libkern/mertwist.c       |  222 ---------------------------------------
 3 files changed, 3 insertions(+), 237 deletions(-)

diffs (279 lines):

diff -r c9fb651ba27d -r a7aedf6e77f8 sys/lib/libkern/Makefile.libkern
--- a/sys/lib/libkern/Makefile.libkern  Sat Dec 14 17:23:31 2019 +0000
+++ b/sys/lib/libkern/Makefile.libkern  Sat Dec 14 17:23:47 2019 +0000
@@ -1,4 +1,4 @@
-#      $NetBSD: Makefile.libkern,v 1.45 2019/12/14 17:23:31 riastradh Exp $
+#      $NetBSD: Makefile.libkern,v 1.46 2019/12/14 17:23:47 riastradh Exp $
 
 # 
 # Variable definitions for libkern.  
@@ -54,7 +54,7 @@
 SRCS+= bswap64.c
 .endif
 SRCS+= md4c.c md5c.c rmd160.c sha1.c sha2.c sha3.c keccak.c murmurhash.c
-SRCS+= pmatch.c mcount.c mertwist.c crc32.c
+SRCS+= pmatch.c mcount.c crc32.c
 
 SRCS+= ppath_kmem_alloc.c
 
diff -r c9fb651ba27d -r a7aedf6e77f8 sys/lib/libkern/libkern.h
--- a/sys/lib/libkern/libkern.h Sat Dec 14 17:23:31 2019 +0000
+++ b/sys/lib/libkern/libkern.h Sat Dec 14 17:23:47 2019 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: libkern.h,v 1.136 2019/12/05 04:17:13 riastradh Exp $  */
+/*     $NetBSD: libkern.h,v 1.137 2019/12/14 17:23:47 riastradh Exp $  */
 
 /*-
  * Copyright (c) 1992, 1993
@@ -356,14 +356,6 @@
     ((const TYPE *)(((const char *)(PTR)) - offsetof(TYPE, FIELD))     \
        + __validate_const_container_of(PTR, TYPE, FIELD))
 
-#define        MTPRNG_RLEN             624
-struct mtprng_state {
-       unsigned int mt_idx;
-       uint32_t mt_elem[MTPRNG_RLEN];
-       uint32_t mt_count;
-       uint32_t mt_sparse[3];
-};
-
 /* Prototypes for which GCC built-ins exist. */
 void   *memcpy(void *, const void *, size_t);
 int     memcmp(const void *, const void *, size_t);
@@ -497,10 +489,6 @@
 long    random(void);
 void    mi_vector_hash(const void * __restrict, size_t, uint32_t,
            uint32_t[3]);
-void    mtprng_init32(struct mtprng_state *, uint32_t);
-void    mtprng_initarray(struct mtprng_state *, const uint32_t *, size_t);
-uint32_t mtprng_rawrandom(struct mtprng_state *);
-uint32_t mtprng_random(struct mtprng_state *);
 int     scanc(u_int, const u_char *, const u_char *, int);
 int     skpc(int, size_t, u_char *);
 int     strcasecmp(const char *, const char *);
diff -r c9fb651ba27d -r a7aedf6e77f8 sys/lib/libkern/mertwist.c
--- a/sys/lib/libkern/mertwist.c        Sat Dec 14 17:23:31 2019 +0000
+++ /dev/null   Thu Jan 01 00:00:00 1970 +0000
@@ -1,222 +0,0 @@
-/*     $NetBSD: mertwist.c,v 1.8 2008/04/28 20:24:06 martin Exp $      */
-/*-
- * Copyright (c) 2008 The NetBSD Foundation, Inc.
- * All rights reserved.
- *
- * This code is derived from software contributed to The NetBSD Foundation
- * by Matt Thomas <matt%3am-software.com@localhost>.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
- * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
- * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
- * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- * POSSIBILITY OF SUCH DAMAGE.
- */
-
-#if defined(_KERNEL) || defined(_STANDALONE)
-#include <sys/param.h>
-#include <sys/types.h>
-#include <sys/systm.h>
-
-#include <lib/libkern/libkern.h>
-#else
-#include <stdlib.h>
-#include <string.h>
-#include <inttypes.h>
-#include <assert.h>
-#define        KASSERT(x)      assert(x)
-#endif
-
-/*
- * Mersenne Twister.  Produces identical output compared to mt19937ar.c
- * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
- */
-
-#define        MATRIX_A(a)             (((a) & 1) ? 0x9908b0df : 0)
-#define        TEMPERING_MASK_B        0x9d2c5680
-#define        TEMPERING_MASK_C        0xefc60000
-#define        UPPER_MASK              0x80000000
-#define        LOWER_MASK              0x7fffffff
-#define        MIX(u,l)                (((u) & UPPER_MASK) | ((l) & LOWER_MASK))
-
-#define        KNUTH_MULTIPLIER        0x6c078965
-
-#ifndef MTPRNG_RLEN
-#define        MTPRNG_RLEN             624
-#endif
-#define        MTPRNG_POS1             397
-
-static void mtprng_refresh(struct mtprng_state *);
-
-/*
- * Initialize the generator from a seed
- */
-void
-mtprng_init32(struct mtprng_state *mt, uint32_t seed)
-{
-       size_t i;
-
-       /*
-        * Use Knuth's algorithm for expanding this seed over its
-        * portion of the key space.
-        */
-       mt->mt_elem[0] = seed;
-       for (i = 1; i < MTPRNG_RLEN; i++) {
-               mt->mt_elem[i] = KNUTH_MULTIPLIER
-                   * (mt->mt_elem[i-1] ^ (mt->mt_elem[i-1] >> 30)) + i;
-       }
-
-       mtprng_refresh(mt);
-}
-
-void
-mtprng_initarray(struct mtprng_state *mt, const uint32_t *key, size_t keylen)
-{
-       uint32_t *mp;
-       size_t i, j, k;
-
-       /*
-        * Use Knuth's algorithm for expanding this seed over its
-        * portion of the key space.
-        */
-       mt->mt_elem[0] = 19650218UL;
-       for (i = 1; i < MTPRNG_RLEN; i++) {
-               mt->mt_elem[i] = KNUTH_MULTIPLIER
-                   * (mt->mt_elem[i-1] ^ (mt->mt_elem[i-1] >> 30)) + i;
-       }
-
-       KASSERT(keylen > 0);
-
-       i = 1;
-       j = 0;
-       k = (keylen < MTPRNG_RLEN ? MTPRNG_RLEN : keylen);
-
-       mp = &mt->mt_elem[1];
-       for (; k-- > 0; mp++) {
-               mp[0] ^= (mp[-1] ^ (mp[-1] >> 30)) * 1664525UL;
-               mp[0] += key[j] + j;
-               if (++i == MTPRNG_RLEN) {
-                       KASSERT(mp == mt->mt_elem + MTPRNG_RLEN - 1);
-                       mt->mt_elem[0] = mp[0];
-                       i = 1;
-                       mp = mt->mt_elem;
-               }
-               if (++j == keylen)
-                       j = 0;
-       }
-       for (j = MTPRNG_RLEN; --j > 0; mp++) {
-               mp[0] ^= (mp[-1] ^ (mp[-1] >> 30)) * 1566083941UL;
-               mp[0] -= i;
-               if (++i == MTPRNG_RLEN) {
-                       KASSERT(mp == mt->mt_elem + MTPRNG_RLEN - 1);
-                       mt->mt_elem[0] = mp[0];
-                       i = 1;
-                       mp = mt->mt_elem;
-               }
-       }
-       mt->mt_elem[0] = 0x80000000;
-       mtprng_refresh(mt);
-}
-
-/*
- * Generate an array of 624 untempered numbers
- */
-void
-mtprng_refresh(struct mtprng_state *mt)
-{
-       uint32_t y;
-       size_t i, j;
-       /*
-        * The following has been refactored to avoid the need for 'mod 624'
-       */
-       for (i = 0, j = MTPRNG_POS1; j < MTPRNG_RLEN; i++, j++) {
-               y = MIX(mt->mt_elem[i], mt->mt_elem[i+1]);
-               mt->mt_elem[i] = mt->mt_elem[j] ^ (y >> 1) ^ MATRIX_A(y);
-       }
-       for (j = 0; i < MTPRNG_RLEN - 1; i++, j++) {
-               y = MIX(mt->mt_elem[i], mt->mt_elem[i+1]);
-               mt->mt_elem[i] = mt->mt_elem[j] ^ (y >> 1) ^ MATRIX_A(y);
-       }
-       y = MIX(mt->mt_elem[MTPRNG_RLEN - 1], mt->mt_elem[0]);
-       mt->mt_elem[MTPRNG_RLEN - 1] =
-           mt->mt_elem[MTPRNG_POS1 - 1] ^ (y >> 1) ^ MATRIX_A(y);
-}
- 
-/*
- * Extract a tempered PRN based on the current index.  Then recompute a
- * new value for the index.  This avoids having to regenerate the array
- * every 624 iterations. We can do this since recomputing only the next
- * element and the [(i + 397) % 624] one.
- */
-uint32_t
-mtprng_rawrandom(struct mtprng_state *mt)
-{
-       uint32_t x, y;
-       const size_t i = mt->mt_idx;
-       size_t j;
-
-       /*
-        * First generate the random value for the current position.
-        */
-       x = mt->mt_elem[i];
-       x ^= x >> 11;
-       x ^= (x << 7) & TEMPERING_MASK_B;
-       x ^= (x << 15) & TEMPERING_MASK_C;
-       x ^= x >> 18;
-
-       /*
-        * Next recalculate the next sequence for the current position.
-        */
-       y = mt->mt_elem[i];
-       if (__predict_true(i < MTPRNG_RLEN - 1)) {
-               /*
-                * Avoid doing % since it can be expensive.
-                * j = (i + MTPRNG_POS1) % MTPRNG_RLEN;
-                */
-               j = i + MTPRNG_POS1;
-               if (j >= MTPRNG_RLEN)
-                       j -= MTPRNG_RLEN;
-               mt->mt_idx++;
-       } else {
-               j = MTPRNG_POS1 - 1;
-               mt->mt_idx = 0;
-       }
-       y = MIX(y, mt->mt_elem[mt->mt_idx]);
-       mt->mt_elem[i] = mt->mt_elem[j] ^ (y >> 1) ^ MATRIX_A(y);
-
-       /*
-        * Return the value calculated in the first step.
-        */
-       return x;
-}
-
-/*
- * This is a non-standard routine which attempts to return a cryptographically
- * strong random number by collapsing 2 32bit values outputed by the twister
- * into one 32bit value.  
- */
-uint32_t
-mtprng_random(struct mtprng_state *mt)
-{
-       uint32_t a;
-
-       mt->mt_count = (mt->mt_count + 13) & 31;
-       a = mtprng_rawrandom(mt);
-       a = (a << mt->mt_count) | (a >> (32 - mt->mt_count));
-       return a + mtprng_rawrandom(mt);
-}



Home | Main Index | Thread Index | Old Index