From 87f1670834e09523f4fba2499aeadee253853709 Mon Sep 17 00:00:00 2001
From: "R. Steve McKown" <rsmckown@gmail.com>
Date: Thu, 29 Dec 2011 11:30:39 -0700
Subject: [PATCH] Replace rand() with LFSR implementation

---
 lfsr.c | 38 ++++++++++++++++++++++++++++++++++++++
 lfsr.h | 17 +++++++++++++++++
 main.c | 11 ++++++-----
 3 files changed, 61 insertions(+), 5 deletions(-)
 create mode 100644 lfsr.c
 create mode 100644 lfsr.h

diff --git a/lfsr.c b/lfsr.c
new file mode 100644
index 0000000..e2539d8
--- /dev/null
+++ b/lfsr.c
@@ -0,0 +1,38 @@
+/*
+ * File:   lfsr.c
+ *
+ * Linear Feedback Shift Register (random number generator)
+ */
+
+/**
+ * This is a small, fast and efficient software implementation of a 16-bit
+ * Linear Feedback Shift Register (LFSR).  It uses the Galois method to perform
+ * the exclusive OR operations in parallel for improved performance over the
+ * standard, or Fibonacci, method.  The algorithm also skips the exlusive or
+ * operations if it doesn't need to do them, though on this uC the branch may
+ * not generate a net performance increase over doing the exclusive or
+ * operations every time.
+ *
+ * After rng returns, RNGLO and RNGHI contain the updated 16-bit random number.
+ * RNGLO will contain a value $01-$FF, RNGHI will contain $00-$FF.
+ *
+ * @author R. Steve McKown <rsmckown@gmail.com>
+ */
+
+
+#include "lfsr.h"
+
+static unsigned lfsr_val = 0x1aa1;
+
+void lfsr_init(unsigned seed)
+{
+  /* The seed cannot be zero */
+  if (seed)
+    lfsr_val = seed;
+}
+
+unsigned lfsr_get()
+{
+  lfsr_val = (lfsr_val >> 1) ^ (-(lfsr_val & 1) & 0xd008);
+  return lfsr_val;
+}
diff --git a/lfsr.h b/lfsr.h
new file mode 100644
index 0000000..64af84e
--- /dev/null
+++ b/lfsr.h
@@ -0,0 +1,17 @@
+/*
+ * File:   lfsr.h
+ *
+ * Linear Feedback Shift Register (random number generator)
+ */
+
+
+#ifndef _LFSR_H
+#define _LFSR_H
+
+/* Initialize the LFSR generator */
+void lfsr_init(unsigned seed);
+
+/* Read the next LFSR value */
+unsigned lfsr_get();
+
+#endif
diff --git a/main.c b/main.c
index 627c94a..dc14185 100644
--- a/main.c
+++ b/main.c
@@ -38,6 +38,7 @@
 #include <stdlib.h>
 #include "picinit.h"
 #include "unused.h"
+#include "lfsr.h"
 #include "btn.h"
 #include "rgb.h"
 #include "tmr.h"
@@ -104,7 +105,7 @@ enum {
   STD_FADE = 16,         /* Fade time in 32.768 ms units */
   STD_INCOLOR = 29491,   /* Time in color when MODE_CYCLE, in 32.768 ms units */
   PARTY_MIN = 8,         /* Min party fade and incolor units */
-  PARTY_RANGE = 8,       /* Party fade/incolor range mask for rand() */
+  PARTY_RANGE = 8,       /* Party fade/incolor range mask for lfsr_get() */
                          /* ... see start_fade() */
   CFG_MODE_ADDR = 0,     /* EEPROM address of mode variable */
   CFG_COLOR_ADDR,        /* EEPROM address of color variable */
@@ -181,8 +182,8 @@ void start_fade()
   /* Select the destination color and fade-to time depending upon mode. */
   fade_steps = STD_FADE;
   if (mode == MODE_PARTY) {
-    color = rand() % COLOR_COUNT;
-    fade_steps = PARTY_MIN + (rand() % PARTY_RANGE);
+    color = lfsr_get() % COLOR_COUNT;
+    fade_steps = PARTY_MIN + (lfsr_get() % PARTY_RANGE);
   } else if (mode == MODE_CYCLE) {
     if (++color == COLOR_COUNT)
       color = 0;
@@ -337,7 +338,7 @@ void fade_task()
     if (mode == MODE_CYCLE)
       tmr_start(TMR_INCOLOR, STD_INCOLOR);
     else if (mode == MODE_PARTY)
-      tmr_start(TMR_INCOLOR, PARTY_MIN + (rand() % PARTY_RANGE));
+      tmr_start(TMR_INCOLOR, PARTY_MIN + (lfsr_get() % PARTY_RANGE));
   }
   leds_set();
 }
@@ -358,7 +359,7 @@ void auto_offon_task()
 void user_boot()
 {
   dbgpin_high();
-  srand((adc_random() << 8) + adc_random());
+  lfsr_init((adc_random() << 8) + adc_random());
   cfg_read(mode, color);
   rs_task();
 }
-- 
2.39.2