[src/trunk]: src comment from niels provos;

[itojun <itojun%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/dbd95e7ea7a2
branches:  trunk
changeset: 556228:dbd95e7ea7a2
user:      itojun <itojun%NetBSD.org@localhost>
date:      Wed Dec 10 05:22:18 2003 +0000

description:
comment from niels provos;
- seed2 is necessary, but use it as "seed2 + x" not "seed2 ^ x".
- skipping number is not needed, so disable it for 16bit generator (makes
  the repetition period to 30000)

diffstat:

 lib/libc/gen/randomid.3            |   8 ++++----
 lib/libc/gen/randomid.c            |  26 ++++++++++++++++----------
 regress/lib/libc/randomid/idtest.c |   4 ++--
 sys/netinet/ip_id.c                |  13 +++++++++----
 sys/netinet6/ip6_id.c              |  14 ++++++--------
 5 files changed, 37 insertions(+), 28 deletions(-)

diffs (273 lines):

diff -r 48fd5d0c786d -r dbd95e7ea7a2 lib/libc/gen/randomid.3
--- a/lib/libc/gen/randomid.3   Wed Dec 10 05:19:41 2003 +0000
+++ b/lib/libc/gen/randomid.3   Wed Dec 10 05:22:18 2003 +0000
@@ -1,4 +1,4 @@
-.\"    $NetBSD: randomid.3,v 1.4 2003/11/25 23:28:31 wiz Exp $
+.\"    $NetBSD: randomid.3,v 1.5 2003/12/10 05:22:18 itojun Exp $
 .\"
 .\" Copyright (C) 2003 WIDE Project.
 .\" All rights reserved.
@@ -84,17 +84,17 @@
 For instance,
 .Fa ctx
 configured to generate 16 bit data stream will reinitialize its internal state
-every 6000 calls to
+every 30000 calls to
 .Fn randomid
 .Po
 or after
 .Fa timeo
 seconds
 .Pc ,
-therefore the same data will not appear until after 12000 calls to
+therefore the same data will not appear until after 30000 calls to
 .Fn randomid
 .Po
-or after 2 times
+or after
 .Fa timeo
 seconds
 .Pc .
diff -r 48fd5d0c786d -r dbd95e7ea7a2 lib/libc/gen/randomid.c
--- a/lib/libc/gen/randomid.c   Wed Dec 10 05:19:41 2003 +0000
+++ b/lib/libc/gen/randomid.c   Wed Dec 10 05:22:18 2003 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: randomid.c,v 1.9 2003/11/25 18:13:06 itojun Exp $      */
+/*     $NetBSD: randomid.c,v 1.10 2003/12/10 05:22:18 itojun Exp $     */
 /*     $KAME: ip6_id.c,v 1.8 2003/09/06 13:41:06 itojun Exp $  */
 /*     $OpenBSD: ip_id.c,v 1.6 2002/03/15 18:19:52 millert Exp $       */
 
@@ -88,7 +88,7 @@
 
 #include <sys/cdefs.h>
 #if defined(LIBC_SCCS) && !defined(lint)
-__RCSID("$NetBSD: randomid.c,v 1.9 2003/11/25 18:13:06 itojun Exp $");
+__RCSID("$NetBSD: randomid.c,v 1.10 2003/12/10 05:22:18 itojun Exp $");
 #endif
 
 #include "namespace.h"
@@ -114,6 +114,7 @@
        const u_int32_t rc_agen; /* determine ru_a as ru_agen^(2*rand) */
        const u_int32_t rc_m;   /* ru_m = 2^x*3^y */
        const u_int32_t rc_pfacts[4];   /* factors of ru_n */
+       const int       rc_skip;        /* skip values */
 };
 
 struct randomid_ctx {
@@ -125,12 +126,13 @@
 #define ru_agen                ru_conf->rc_agen
 #define ru_m           ru_conf->rc_m
 #define ru_pfacts      ru_conf->rc_pfacts
+#define ru_skip                ru_conf->rc_skip
        long ru_out;            /* Time after wich will be reseeded */
        u_int32_t ru_counter;
        u_int32_t ru_msb;
 
        u_int32_t ru_x;
-       u_int32_t ru_seed;
+       u_int32_t ru_seed, ru_seed2;
        u_int32_t ru_a, ru_b;
        u_int32_t ru_g;
        long ru_reseed;
@@ -145,6 +147,7 @@
        7,                      /* determine ru_a as RU_AGEN^(2*rand) */
        1836660096,             /* RU_M = 2^7*3^15 - don't change */
        { 2, 3, 59652323, 0 },  /* factors of ru_n */
+       3,                      /* skip values */
   },
   {
        20,                     /* resulting bits */
@@ -154,6 +157,7 @@
        7,                      /* determine ru_a as RU_AGEN^(2*rand) */
        279936,                 /* RU_M = 2^7*3^7 - don't change */
        { 2, 3, 14563, 0 },     /* factors of ru_n */
+       3,                      /* skip values */
   },
   {
        16,                     /* resulting bits */
@@ -163,6 +167,7 @@
        7,                      /* determine ru_a as RU_AGEN^(2*rand) */
        31104,                  /* RU_M = 2^7*3^5 - don't change */
        { 2, 3, 2729, 0 },      /* factors of ru_n */
+       0,                      /* skip values */
   },
   {
        -1,                     /* termination */
@@ -218,6 +223,7 @@
 
        /* (bits - 1) bits of random seed */
        p->ru_seed = arc4random() & (~0U >> (32 - p->ru_bits + 1));
+       p->ru_seed2 = arc4random() & (~0U >> (32 - p->ru_bits + 1));
 
        /* Determine the LCG we use */
        p->ru_b = (arc4random() & (~0U >> (32 - p->ru_bits))) | 1;
@@ -297,19 +303,19 @@
 randomid(struct randomid_ctx *p)
 {
        int i, n;
-       u_int32_t tmp;
        struct timeval tv;
 
        gettimeofday(&tv, NULL);
        if (p->ru_counter >= p->ru_max || tv.tv_sec > p->ru_reseed)
                initid(p);
 
-       tmp = arc4random();
-
        /* Skip a random number of ids */
-       n = tmp & 0x3; tmp = tmp >> 2;
-       if (p->ru_counter + n >= p->ru_max)
-               initid(p);
+       if (p->ru_skip) {
+               n = arc4random() & p->ru_skip;
+               if (p->ru_counter + n >= p->ru_max)
+                       initid(p);
+       } else
+               n = 0;
 
        for (i = 0; i <= n; i++) {
                /* Linear Congruential Generator */
@@ -318,6 +324,6 @@
 
        p->ru_counter += i;
 
-       return (p->ru_seed ^ pmod(p->ru_g, p->ru_x, p->ru_n)) |
+       return (p->ru_seed ^ pmod(p->ru_g, p->ru_seed2 + p->ru_x, p->ru_n)) |
            p->ru_msb;
 }
diff -r 48fd5d0c786d -r dbd95e7ea7a2 regress/lib/libc/randomid/idtest.c
--- a/regress/lib/libc/randomid/idtest.c        Wed Dec 10 05:19:41 2003 +0000
+++ b/regress/lib/libc/randomid/idtest.c        Wed Dec 10 05:22:18 2003 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: idtest.c,v 1.3 2003/11/29 00:11:18 simonb Exp $ */
+/* $NetBSD: idtest.c,v 1.4 2003/12/10 05:22:18 itojun Exp $ */
 
 /* If defined, abort at first short period and only test REGRESS times. */
 #define        REGRESS         10000000                /* should be enough... */
@@ -11,7 +11,7 @@
 #include <stdio.h>
 #include <string.h>
 
-#define        PERIOD          12000
+#define        PERIOD          30000
 
 uint64_t last[65536];
 
diff -r 48fd5d0c786d -r dbd95e7ea7a2 sys/netinet/ip_id.c
--- a/sys/netinet/ip_id.c       Wed Dec 10 05:19:41 2003 +0000
+++ b/sys/netinet/ip_id.c       Wed Dec 10 05:22:18 2003 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: ip_id.c,v 1.4 2003/11/25 18:13:55 itojun Exp $ */
+/*     $NetBSD: ip_id.c,v 1.5 2003/12/10 05:22:18 itojun Exp $ */
 /*     $OpenBSD: ip_id.c,v 1.6 2002/03/15 18:19:52 millert Exp $       */
 
 /*
@@ -57,7 +57,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: ip_id.c,v 1.4 2003/11/25 18:13:55 itojun Exp $");
+__KERNEL_RCSID(0, "$NetBSD: ip_id.c,v 1.5 2003/12/10 05:22:18 itojun Exp $");
 
 #include "opt_inet.h"
 
@@ -85,7 +85,7 @@
 };
 
 static u_int16_t ru_x;
-static u_int16_t ru_seed;
+static u_int16_t ru_seed, ru_seed2;
 static u_int16_t ru_a, ru_b;
 static u_int16_t ru_g;
 static u_int16_t ru_counter = 0;
@@ -137,6 +137,7 @@
 
        /* 15 bits of random seed */
        ru_seed = (tmp >> 16) & 0x7FFF;
+       ru_seed2 = arc4random() & 0x7FFF;
 
        /* Determine the LCG we use */
        ru_b = ((tmp = arc4random()) & 0xfffe) | 1;
@@ -182,10 +183,14 @@
        if (!tmp)
                tmp = arc4random();
 
+#if 0
        /* Skip a random number of ids */
        n = tmp & 0x3; tmp = tmp >> 2;
        if (ru_counter + n >= RU_MAX)
                ip_initid();
+#else
+       n = 0;
+#endif
 
        for (i = 0; i <= n; i++)
                /* Linear Congruential Generator */
@@ -193,5 +198,5 @@
 
        ru_counter += i;
 
-       return (ru_seed ^ pmod(ru_g, ru_x, RU_N)) | ru_msb;
+       return (ru_seed ^ pmod(ru_g, ru_seed2 + ru_x, RU_N)) | ru_msb;
 }
diff -r 48fd5d0c786d -r dbd95e7ea7a2 sys/netinet6/ip6_id.c
--- a/sys/netinet6/ip6_id.c     Wed Dec 10 05:19:41 2003 +0000
+++ b/sys/netinet6/ip6_id.c     Wed Dec 10 05:22:18 2003 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: ip6_id.c,v 1.10 2003/11/25 18:13:55 itojun Exp $       */
+/*     $NetBSD: ip6_id.c,v 1.11 2003/12/10 05:22:18 itojun Exp $       */
 /*     $KAME: ip6_id.c,v 1.8 2003/09/06 13:41:06 itojun Exp $  */
 /*     $OpenBSD: ip_id.c,v 1.6 2002/03/15 18:19:52 millert Exp $       */
 
@@ -87,7 +87,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: ip6_id.c,v 1.10 2003/11/25 18:13:55 itojun Exp $");
+__KERNEL_RCSID(0, "$NetBSD: ip6_id.c,v 1.11 2003/12/10 05:22:18 itojun Exp $");
 
 #include <sys/types.h>
 #include <sys/param.h>
@@ -113,7 +113,7 @@
        u_int32_t ru_msb;
 
        u_int32_t ru_x;
-       u_int32_t ru_seed;
+       u_int32_t ru_seed, ru_seed2;
        u_int32_t ru_a, ru_b;
        u_int32_t ru_g;
        long ru_reseed;
@@ -186,6 +186,7 @@
 
        /* (bits - 1) bits of random seed */
        p->ru_seed = arc4random() & (~0U >> (32 - p->ru_bits + 1));
+       p->ru_seed2 = arc4random() & (~0U >> (32 - p->ru_bits + 1));
 
        /* Determine the LCG we use */
        p->ru_b = (arc4random() & (~0U >> (32 - p->ru_bits))) | 1;
@@ -223,15 +224,12 @@
 randomid(struct randomtab *p)
 {
        int i, n;
-       u_int32_t tmp;
 
        if (p->ru_counter >= p->ru_max || time.tv_sec > p->ru_reseed)
                initid(p);
 
-       tmp = arc4random();
-
        /* Skip a random number of ids */
-       n = tmp & 0x3; tmp = tmp >> 2;
+       n = arc4random() & 0x3;
        if (p->ru_counter + n >= p->ru_max)
                initid(p);
 
@@ -242,7 +240,7 @@
 
        p->ru_counter += i;
 
-       return (p->ru_seed ^ pmod(p->ru_g, p->ru_x, p->ru_n)) |
+       return (p->ru_seed ^ pmod(p->ru_g, p->ru_seed2 + p->ru_x, p->ru_n)) |
            p->ru_msb;
 }