Add a fast non-cryptographic PRNG.

10 files changed, 107 insertions, 20 deletions

diff --git a/node/BloomFilter.hpp b/node/BloomFilter.hpp
index 60af61ab..ef48c9f0 100644
--- a/node/BloomFilter.hpp
+++ b/node/BloomFilter.hpp
@@ -115,11 +115,12 @@ public:
 
 	/**
 	 * Clear a random bit in this bloom filter
+	 *
+	 * @param rn Random number
 	 */
-	inline void decay()
+	inline void decay(unsigned int rn)
 		throw()
 	{
-		const unsigned int rn = Utils::randomInt<unsigned int>();
 		_field[(rn >> 3) % (B / 8)] &= ~((unsigned char)(1 << (rn & 7)));
 	}
 
diff --git a/node/CMWC4096.hpp b/node/CMWC4096.hpp
new file mode 100644
index 00000000..31ef2ca4
--- /dev/null
+++ b/node/CMWC4096.hpp
@@ -0,0 +1,81 @@
+/*
+ * ZeroTier One - Global Peer to Peer Ethernet
+ * Copyright (C) 2012-2013  ZeroTier Networks LLC
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * --
+ *
+ * ZeroTier may be used and distributed under the terms of the GPLv3, which
+ * are available at: http://www.gnu.org/licenses/gpl-3.0.html
+ *
+ * If you would like to embed ZeroTier into a commercial application or
+ * redistribute it in a modified binary form, please contact ZeroTier Networks
+ * LLC. Start here: http://www.zerotier.com/
+ */
+
+#ifndef _ZT_CMWC4096_HPP
+#define _ZT_CMWC4096_HPP
+
+#include <stdint.h>
+#include "Utils.hpp"
+
+/** 
+ * Complement Multiply With Carry random number generator
+ *
+ * Based on original code posted to Usenet in the public domain by
+ * George Marsaglia. Period is approximately 2^131086.
+ *
+ * This is not used for cryptographic purposes but for a very fast
+ * and high-quality PRNG elsewhere in the code.
+ */
+class CMWC4096
+{
+public:
+	/**
+	 * Construct and initialize from secure random source
+	 */
+	CMWC4096()
+		throw()
+	{
+		Utils::getSecureRandom(Q,sizeof(Q));
+		Utils::getSecureRandom(&c,sizeof(c));
+		c %= 809430660;
+		i = 4095;
+	}
+
+	inline uint32_t next32()
+		throw()
+	{
+		uint32_t __i = ++i & 4095;
+		const uint64_t t = (18782ULL * (uint64_t)Q[__i]) + (uint64_t)c;
+		c = (uint32_t)(t >> 32);
+		uint32_t x = c + (uint32_t)t;
+		const uint32_t p = (uint32_t)(x < c); x += p; c += p;
+		return (Q[__i] = 0xfffffffe - x);
+	}
+
+	inline uint64_t next64()
+		throw()
+	{
+		return ((((uint64_t)next32()) << 32) ^ (uint64_t)next32());
+	}
+
+private:
+	uint32_t Q[4096];
+	uint32_t c;
+	uint32_t i;
+};
+
+#endif
diff --git a/node/Demarc.cpp b/node/Demarc.cpp
index 4885c086..cf521707 100644
--- a/node/Demarc.cpp
+++ b/node/Demarc.cpp
@@ -143,7 +143,7 @@ Demarc::Port Demarc::pick(const InetAddress &to) const
 			}
 		}
 		if (possibilities.size())
-			return possibilities[Utils::randomInt<unsigned int>() % possibilities.size()]->first;
+			return possibilities[_r->prng.next32() % possibilities.size()]->first;
 		else return NULL_PORT;
 	} catch ( ... ) {
 		return NULL_PORT;
@@ -174,7 +174,7 @@ Demarc::Port Demarc::send(Demarc::Port fromPort,const InetAddress &to,const void
 				}
 			}
 			if (possibilities.size())
-				pe = possibilities[Utils::randomInt<unsigned int>() % possibilities.size()];
+				pe = possibilities[_r->prng.next32() % possibilities.size()];
 			else {
 				_ports_m.unlock();
 				return NULL_PORT;
diff --git a/node/Http.cpp b/node/Http.cpp
index 6a79a974..07ada6dc 100644
--- a/node/Http.cpp
+++ b/node/Http.cpp
@@ -173,7 +173,7 @@ void Http::Request::main()
 				addrList->sort();
 				addrList->unique();
 				unsigned int i = 0,k = 0;
-				k = Utils::randomInt<unsigned int>() % addrList->size();
+				k = _r->prng.next32() % addrList->size();
 				std::list<InetAddress>::iterator a(addrList->begin());
 				while (i++ != k) ++a;
 				addr = &(*a);
diff --git a/node/Multicaster.hpp b/node/Multicaster.hpp
index aa3bcb16..42c92aab 100644
--- a/node/Multicaster.hpp
+++ b/node/Multicaster.hpp
@@ -50,6 +50,7 @@
 #include "SharedPtr.hpp"
 #include "BloomFilter.hpp"
 #include "Identity.hpp"
+#include "CMWC4096.hpp"
 
 // Maximum sample size to pick during choice of multicast propagation peers
 #define ZT_MULTICAST_PICK_MAX_SAMPLE_SIZE (ZT_MULTICAST_PROPAGATION_BREADTH * 8)
@@ -211,6 +212,7 @@ public:
 	 */
 	template<typename T,typename P>
 	inline unsigned int pickNextPropagationPeers(
+		CMWC4096 &prng,
 		T &topology,
 		uint64_t nwid,
 		const MulticastGroup &mg,
diff --git a/node/Node.cpp b/node/Node.cpp
index 976de742..265b77e4 100644
--- a/node/Node.cpp
+++ b/node/Node.cpp
@@ -193,8 +193,11 @@ Node::ReasonForTermination Node::run()
 		std::string ovsPath(_r->homePath + ZT_PATH_SEPARATOR_S + "thisdeviceismine");
 		if (((Utils::now() - Utils::getLastModified(ovsPath.c_str())) >= ZT_OVS_GENERATE_NEW_IF_OLDER_THAN)||(!Utils::readFile(ovsPath.c_str(),_r->ownershipVerificationSecret))) {
 			_r->ownershipVerificationSecret = "";
-			for(unsigned int i=0;i<24;++i)
-				_r->ownershipVerificationSecret.push_back("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"[Utils::randomInt<unsigned int>() % 62]);
+			unsigned int securern = 0;
+			for(unsigned int i=0;i<24;++i) {
+				Utils::getSecureRandom(&securern,sizeof(securern));
+				_r->ownershipVerificationSecret.push_back("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"[securern % 62]);
+			}
 			_r->ownershipVerificationSecret.append(ZT_EOL_S);
 			if (!Utils::writeFile(ovsPath.c_str(),_r->ownershipVerificationSecret))
 				return impl->terminateBecause(Node::NODE_UNRECOVERABLE_ERROR,"could not write 'thisdeviceismine' (home path not writable?)");
diff --git a/node/RuntimeEnvironment.hpp b/node/RuntimeEnvironment.hpp
index 3b398e0c..b39a584f 100644
--- a/node/RuntimeEnvironment.hpp
+++ b/node/RuntimeEnvironment.hpp
@@ -31,6 +31,7 @@
 #include <string>
 #include "Identity.hpp"
 #include "Condition.hpp"
+#include "CMWC4096.hpp"
 
 namespace ZeroTier {
 
@@ -77,6 +78,9 @@ public:
 	// signal() to prematurely interrupt main loop wait
 	Condition mainLoopWaitCondition;
 
+	// non-cryptographic fast PRNG
+	CMWC4096 prng;
+
 	Identity configAuthority;
 	Identity identity;
 
diff --git a/node/SharedPtr.hpp b/node/SharedPtr.hpp
index 014e34fa..a31e135e 100644
--- a/node/SharedPtr.hpp
+++ b/node/SharedPtr.hpp
@@ -88,6 +88,14 @@ public:
 		return *this;
 	}
 
+	inline void swap(SharedPtr &with)
+		throw()
+	{
+		T *tmp = _ptr;
+		_ptr = with._ptr;
+		with._ptr = tmp;
+	}
+
 	inline operator bool() const throw() { return (_ptr); }
 	inline T &operator*() const throw() { return *_ptr; }
 	inline T *operator->() const throw() { return _ptr; }
diff --git a/node/Topology.cpp b/node/Topology.cpp
index de65de3b..a4ba1e04 100644
--- a/node/Topology.cpp
+++ b/node/Topology.cpp
@@ -201,7 +201,7 @@ skip_and_try_next_supernode:
 	if (bestSupernode)
 		return bestSupernode;
 
-	return _supernodePeers[Utils::randomInt<unsigned int>() % _supernodePeers.size()];
+	return _supernodePeers[_r->prng.next32() % _supernodePeers.size()];
 }
 
 void Topology::clean()
diff --git a/node/Utils.hpp b/node/Utils.hpp
index 4b7d6be8..e6bef5e5 100644
--- a/node/Utils.hpp
+++ b/node/Utils.hpp
@@ -87,18 +87,6 @@ public:
 	static void getSecureRandom(void *buf,unsigned int bytes);
 
 	/**
-	 * @tparam T Integer type to fill and return
-	 * @return Random int using secure random source
-	 */
-	template<typename T>
-	static inline T randomInt()
-	{
-		T foo = 0; // prevents valgrind warnings
-		getSecureRandom(&foo,sizeof(foo));
-		return foo;
-	}
-
-	/**
 	 * Set modes on a file to something secure
 	 * 
 	 * This locks a file so that only the owner can access it. What it actually