Because the ip_id code initialisation is a specific case of shuffling

a set of incrementing integers (and not an arbitrary set of values) it
is possible to populate the array as we shuffle it in a single forward
pass. Clever optimisation from didickman AT gmail.com;
ok deraadt@ mcbride@

1 files changed, 10 insertions, 9 deletions

diff --git a/sys/netinet/ip_id.c b/sys/netinet/ip_id.c
index 07834dfcd25..1a4b8a1b740 100644
--- a/sys/netinet/ip_id.c
+++ b/sys/netinet/ip_id.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ip_id.c,v 1.18 2008/03/02 21:38:18 deraadt Exp $ */
+/*	$OpenBSD: ip_id.c,v 1.19 2008/03/15 04:36:31 djm Exp $ */
 
 /*
  * Copyright (c) 2008 Theo de Raadt, Ryan McBride
@@ -51,17 +51,18 @@ ip_randomid(void)
 		ipid_initialized = 1;
 
 		/*
-		 * Initialize using a Durstenfeld shuffle. Even if our PRNG
-		 * is imperfect at boot time, we have deferred doing this until
-		 * the first packet being sent and now must generate an ID.
+		 * Initialize with a random permutation. Do so using Knuth
+		 * which avoids the exchange in the Durstenfeld shuffle.
+		 * (See "The Art of Computer Programming, Vol 2" 3rd ed, pg. 145).
+		 *
+		 * Even if our PRNG is imperfect at boot time, we have deferred
+		 * doing this until the first packet being sent and now must
+		 * generate an ID.
 		 */
-		for (i = 0; i < sizeof(ip_shuffle)/sizeof(ip_shuffle[0]); ++i)
-			ip_shuffle[i] = i;
-		for (i = sizeof(ip_shuffle)/sizeof(ip_shuffle[0]); --i; ) {
+		for (i = 0; i < sizeof(ip_shuffle)/sizeof(ip_shuffle[0]); ++i) {
 			i2 = arc4random_uniform(i + 1);
-			r = ip_shuffle[i];
 			ip_shuffle[i] = ip_shuffle[i2];
-			ip_shuffle[i2] = r;
+			ip_shuffle[i2] = i;
 		}
 	}