/ Low Level

Entropy on the cortex

A few people were complaining about the lack of random number generation in PROS and RobotC so i've made a simple RNG for the cortex in C++ on PROS:

// entropy.h
// Created by Andre "PixelToast" Lipke
// Released under CC0 (public domain).
// https://creativecommons.org/publicdomain/zero/1.0/

#include "main.h"

namespace entropy {
  void feed(uint32_t val);
  uint32_t getInt();
  uint32_t getInt(uint32_t min, uint32_t max);
  float getFloat();
  float getFloat(float min, float max);
}
// entropy.cpp
// Created by Andre "PixelToast" Lipke
// Released under CC0 (public domain).
// https://creativecommons.org/publicdomain/zero/1.0/

#include "include/entropy.h"
#include "include/util.h"

static uint32_t ring[16] = {0};
static int index = 0;

static uint32_t hash(uint32_t x) {
  x ^= x << 13;
  x ^= x >> 17;
  x ^= x << 5;
  return x;
}

void entropy::feed(uint32_t x) {
  ring[index] ^= x = hash(x);
  ring[(x >> 12) % 16] ^= hash(ring[index]);
  index = (index + 1) % 16;
}

uint32_t entropy::getInt() {
  uint32_t x = hash(ring[index]);
  ring[(ring[index] >> 9) % 16] ^= hash(x);
  index = (index + 1) % 16;
  return x;
}

uint32_t entropy::getInt(uint32_t min, uint32_t max) {
  uint32_t x;
  do {
    x = entropy::getInt() % exp(2, log2(max - min) + 1);
  } while (x > max - min); // ensure perfect distribution
  return x;
}

float entropy::getFloat() {
  return getInt() / 4294967295.0f;
}

float entropy::getFloat(float min, float max) {
  return (entropy::getFloat() * (max - min)) + min;
}

Entropy gathers in the ring array (total of 512 bits) which is fed by entropy::feed. The hash function is a simple xorshift to cut down on cpu time.

An important quality of random number generators is to make it hard to find the seed from the random outputs cough java.util.Random cough, since the output of entropy::getInt() is only one xorshift away from the input it's easy to determine the state of the ring with a large list of numbers which is bad. This is less relevant though because rather than using a single seed the RNG is going to be fed continuously making predicting the state of the ring nearly impossible.

We are spoiled on desktops and mobile devices with random numbers as there are a ton of sources of entropy for a psudorandom number generator because on the cortex we only have one constant source of entropy: the analog ports.

Analog ports on the cortex are pretty fuzzy, when an analog port is unplugged it normally floats between 252 and 258. This can be used quite effectively to generate random numbers so I put this in a background task:

for (int i = 1; i <= 8; i++) {
  entropy::feed(analogRead(i));
}

I estimate each analog port produces about 50 bits per second of entropy, 640 bits per second total (you only need 1 to randomize an autonomous mode)

This is completely unnecessary for competition, even the most advanced adaptive / randomized autonomous modes need less than 10 bits of entropy but I hope you learned something about crypto and RNGs while reading this.

Entropy on the cortex
Share this