She turned me into a Gnewt! I got better…

EDIT: Yes, the linked list solution is not the most efficient one (and in fact could be dangerous if used with much more memory than this when malloc’d on a small chip like the Arduino). The “right” way is using a circular buffer. A sketch utilizing a circular buffer has been added to the github project.

Around two years ago, a fellow by the name of darco posted an article called “Hacking Christmas Lights” on his blog. He was nice enough to reverse engineer the LED data bus protocol of the GE Color Effects christmas lights, as well as release some code for an ATMel microcontroller. This was of course turned into an Arduino library soon after.

I had an idea for something to do with these lights: I wanted a network service I could connect to which would pick a random color from a pre-defined list, tell me which color it picked, and then “push” that color onto the string of lights. Each time the service was hit, a new color would enter the string of lights. Each other color would move to the next light until it was at the end of the string, where it would “fall off.”

I decided to do all the networking and color choosing in a Python script on my laptop, leaving the Arduino with just the task of controlling the lights and storing their colors. The GEColorEffects library would handle the control, so all I needed to do on that end was find a data structure to store the colors in. Usually I would just use an array, but this approach gets ugly when you want to “move” each color to the next light. It would involve copying every single color value in the array to the next location before adding the new color.

// colors are 12 bits, so can be stored in a 16-bit type easily
uint16_t lights[NUMLIGHTS]; // populated somewhere else in code
int i;

--snip--

for (i = NUMLIGHTS; i > 1; i--) {
    lights[i-1] = lights[i-2];
}

lights[0] = newcolor;

The previous code would have to be called every time I wanted to add a new color to the string of lights. It would probably work just fine (meaning sufficiently fast) considering that it’s only copying 72 bytes, but it feels clunky. I wanted an approach which felt elegant. The thing that came to mind after some shower-aided thinking (all good programming ideas happen in the shower) was a circular linked list. A linked list is a collection of structures, 0r collections of data, with the unique characteristic that each structure contains a pointer to the next one. In a doubly-linked list, each structure contains a pointer to the previous and the next one. In a circular linked list, the last structure points to the first, effectively making it act like a circle. If you were to follow the path forever, you’d never reach an end.

The nice part of using circular linked lists is that you can just choose where the “beginning” is dynamically.

struct RGB
{
    // each color is only 4 bits but stored as an 8-bit type
    uint8_t r;
    uint8_t g;
    uint8_t b;
    struct RGB *next; // pointer to the next RGB structure
};
typedef struct RGB rgb;

rgb *head;

void populate_linked_list()
{
  int i;
  rgb *curr;
  curr = head = (rgb*)malloc(sizeof(rgb)); // allocate first struct as head

  for (i = 0; i < lightCount-1; i++) { // allocate 35 more (36 lights total)
      curr->r = 15; // they all start out red
      curr->g = curr->b = 0;
      curr->next = (rgb*)malloc(sizeof(rgb));
      curr = curr->next;
  }
  // and finally, the last struct
  curr->r = 15;
  curr->g = curr->b = 0;
  curr->next = head; // the "next" after the last, is the first
  curr = head;
}

The lights are set by iterating through the list and using the GEColorEffects library to set each light to the color represented by each structure. Here comes the fun part. To “push” a color onto the set of lights (and move each other color to the next light), all you have to do is write the color values to the current head of the list, and then move the head to point to the next structure. Keep in mind that we’re pushing colors onto the end of the list, and each color at the very beginning of the list falls off when we do that.

void add_color(uint8_t r, uint8_t g, uint8_t b)
{
  head->r = r;
  head->g = g;
  head->b = b;
  head = head->next;
}

We’ve just moved the beginning/head of the list one light forward (meaning the 2nd color on the string of lights moves to the 1st, 3rd moves to 2nd etc.) and put the data for the new color in the previous location of the head, which is now the very end of the list. The colors of the lights appear to move accordingly.

I put the code on github here. It comes with the Arduino sketch which implements the linked list setup as well as a simple serial interface. Read the README for more info about that.