1 files changed, 101 insertions, 0 deletions
diff --git a/tests/_fastrand.c b/tests/_fastrand.c
new file mode 100644
index 0000000..d1f85ea
--- /dev/null
+++ b/tests/_fastrand.c
@@ -0,0 +1,101 @@
+/*
+Copyright 2014 Google Inc. All rights reserved.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+*/
+
+/*
+ * _fastrand.c -- Python extension module to generate random bit vectors
+ * quickly.
+ *
+ * IMPORTANT: This module does not use crytographically strong randomness.  It
+ * should be used ONLY be used to speed up the simulation.  Don't use it in
+ * production.
+ *
+ * If an adversary can predict which random bits are flipped, then RAPPOR's
+ * privacy is compromised.
+ *
+ */
+
+#include <stdint.h>  // uint64_t
+#include <stdio.h>  // printf
+#include <stdlib.h>  // srand
+#include <time.h>  // time
+
+#include <Python.h>
+
+uint64_t randbits(float p1, int num_bits) {
+  uint64_t result = 0;
+  // RAND_MAX is the maximum int returned by rand().
+  //
+  // When p1 == 1.0, we want to guarantee that all bits are 1.  The threshold
+  // will be RAND_MAX + 1.  In the rare case that rand() returns RAND_MAX, the
+  // "<" test succeeds, so we get 1.
+  //
+  // When p1 == 0.0, we want to guarantee that all bits are 0.  The threshold
+  // will be 0.  In the rare case that rand() returns 0, the "<" test fails, so
+  // we get 0.
+
+  // NOTE: cast is necessary to do unsigned arithmetic rather than signed.
+  // RAND_MAX is an int so adding 1 won't overflow a uint64_t.
+  uint64_t max = (uint64_t)RAND_MAX + 1u;
+  uint64_t threshold = p1 * max;
+  int i;
+  for (i = 0; i < num_bits; ++i) {
+    // NOTE: The comparison is <= so that p1 = 1.0 implies that the bit is
+    // ALWAYS set.  RAND_MAX is the maximum value returned by rand().
+    uint64_t bit = (rand() < threshold);
+    result |= (bit << i);
+  }
+  return result;
+}
+
+static PyObject *
+func_randbits(PyObject *self, PyObject *args) {
+  float p1;
+  int num_bits;
+
+  if (!PyArg_ParseTuple(args, "fi", &p1, &num_bits)) {
+    return NULL;
+  }
+  if (p1 < 0.0 || p1 > 1.0) {
+    printf("p1 must be between 0.0 and 1.0\n");
+    // return None for now; easier than raising ValueError
+    Py_INCREF(Py_None);
+    return Py_None;
+  }
+  if (num_bits < 0 || num_bits > 64) {
+    printf("num_bits must be 64 or less\n");
+    // return None for now; easier than raising ValueError
+    Py_INCREF(Py_None);
+    return Py_None;
+  }
+
+  //printf("p: %f\n", p);
+  uint64_t r = randbits(p1, num_bits);
+  return PyLong_FromUnsignedLongLong(r);
+}
+
+PyMethodDef methods[] = {
+  {"randbits", func_randbits, METH_VARARGS,
+   "Return a number with N bits, where each bit is 1 with probability p."},
+  {NULL, NULL},
+};
+
+void init_fastrand(void) {
+  Py_InitModule("_fastrand", methods);
+
+  // Just seed it here; we don't give the application any control.
+  int seed = time(NULL);
+  srand(seed);
+}