I’ve been a bit lax with the blog updating. In Part 1 of this post I promised Part 2 “soon” and here it is, eight weeks later. Oops.

This two-post series, aimed at embedded device beginners, explains some differences between Arduino and Raspberry Pi. In this second part we’re going to focus on one particular issue – “real-time” constraints. We’ll also quickly look over some of the alternative devices available.

Continue reading

On an Arduino or other AVR, EEPROM access is a bit fiddly if you want to store different types of data. In this blog post, I’ll show you a quick trick to use when you have lots of structured data to store in EEPROM.

Alternatives

First, the existing alternatives:

  • Arduino has EEPROM, which is simple but it only reads/writes single bytes.
  • Arduino Playground has two templated functions that let you read/write anything. However, you need to know the offset of whatever you are accessing. Also, I find C++ templates a bit icky for this use case.
  • One level deeper, avr-libc has a more complex API for other kinds of integers, and buffers. However, you still need to remember offsets & sizes.
  • The EEMEM keyword works like PROGMEM to let you flag things as stored in the EEPROM. Which is nice, but you still need to pass size and offset whenever you read a value.

Technique

This technique uses a single ‘struct’ to represent the entire contents of your EEPROM, so you can then use macros to read and write fields.

You define a struct called __eeprom_data that describes your EEPROM:

struct __eeprom_data {
  int first;
  int second[64]; 
  boolean third;
  char fourth[buf_len];
}

Then use macros eeprom_read & eeprom_write to read and write each field:

int x;
eeprom_write(-7, first);
eeprom_read(x, first);

Full Example


/*
 * Copy and paste this block of #include & #defines into your code to use
 * this technique.
 *
 * (Don't worry too much about reading the macros, read through the
 * examples below instead.)
 */

#include <avr/eeprom.h>
#define eeprom_read_to(dst_p, eeprom_field, dst_size) eeprom_read_block(dst_p, (void *)offsetof(__eeprom_data, eeprom_field), MIN(dst_size, sizeof((__eeprom_data*)0)->eeprom_field))
#define eeprom_read(dst, eeprom_field) eeprom_read_to(&dst, eeprom_field, sizeof(dst))
#define eeprom_write_from(src_p, eeprom_field, src_size) eeprom_write_block(src_p, (void *)offsetof(__eeprom_data, eeprom_field), MIN(src_size, sizeof((__eeprom_data*)0)->eeprom_field))
#define eeprom_write(src, eeprom_field) { typeof(src) x = src; eeprom_write_from(&x, eeprom_field, sizeof(x)); }
#define MIN(x,y) ( x > y ? y : x )

const int buflen = 32;

/*
 * __eeprom_data is the magic name that maps all of the data we are 
 * storing in our EEPROM
 */
struct __eeprom_data {
  int first;
  int second; 
  boolean third;
  char fourth[buflen];
  char fifth[buflen];
};


void setup()
{
   Serial.begin(57600);

   /*
    * Writing simple variables to the EEPROM becomes simple
    *
    * First argument is the value to write, second argument is which field
    * (in __eeprom_data) to write to.
    */
   int q = 132;
   eeprom_write(q, first);
   eeprom_write(5958, second);
   eeprom_write(false, third);
   eeprom_write("Hello from EEPROM!", fourth);

   /*
    * You can even write from a pointer address if need be
    *
    * First argument is the pointer to write from.
    * Second argument is the field (in __eeprom_data) 
    * to write to.
    * Third argument is the buffer length
    */
    const char * buf = "Another hello looks like this";
    eeprom_write_from(buf, fifth, strlen(buf)+1);


    int a, b;
    boolean c;
    char d[buflen], e[buflen];
    char *e_p = e;
    
    /*
     * Reading back is just as simple. First argument is the variable to read
     * back to, the second argument is the field (in __eeprom_data) to read
     * from.
     */
    eeprom_read(a, first);
    eeprom_read(b, second);
    eeprom_read(c, third);
    eeprom_read(d, fourth);
    
    /*
     * You can read back to a pointer address, if you need to.
     */
    eeprom_read_to(e_p, fifth, buflen);
    

    Serial.println(a);
    Serial.println(b);
    Serial.println(c ? "TRUE" : "FALSE");
    Serial.println(d);
    Serial.println(e_p);
    
    /*
     * The eeprom_write macros do bounds checking, 
     * so you can't overrun a buffer.
     *
     * In __eeprom_data, 'third' is a one-byte boolean, but 
     * eeprom_write knows this so only the first char 'T' is written
     * to EEPROM
     */
    eeprom_write("This is a buffer overflow", third);
    
    /*
     * If you have an array, like char[], you can write & read a single
     * array entry from a particular constant index
     *
     * Unfortunately, it only works for constant indexes not variables.
     * eeprom_write('X', fourth[x]) does not work with these macros.
     */
    eeprom_write('X', fourth[3]);
    eeprom_read(d, fourth);
    char x;
    eeprom_read(x, fourth[3]);
    Serial.println(d);
    Serial.println(x);
}

void loop() { }

(This is Arduino code, obviously if you’re using avr-libc directly then you can rewrite it for that.)

Downsides

The downsides of this technique (as I see them) are:

  • Uses macro magic (so a bit icky.)
  • Overkill if you only need to store one type of data in EEPROM, but useful if you have lots of different types.

Initial Values

When you start up, you need to know if the data in EEPROM is data that your program saved, or something else. There are a few different ways to deal with this.

EEMEM

EEMEM provides a way for you to set default values easily in your code:

EEMEM struct __eeprom_data initial_data EEMEM = { 
  1, // first
  2, // second
  false, // third
  "Initial fourth", // fourth
   "Initial fifth" // fifth
};

Via avr-objcopy & avrdude you can generate a .eep file and flash it to the AVR. This is nice, but it won’t work if you’re using the Arduino IDE because (as of version 0018) it doesn’t generate .eep files properly, and it also doesn’t support flashing them.

It’s a good option if you’re using your own Makefile, though.

“Magic” number

The other way is to check for and expect a “magic” value somewhere in the EEPROM data. Something like:

// Change this any time the EEPROM content changes
const long magic_number = 0x5432;

struct __eeprom_data {
  long magic; // should be set to magic_number
  int first;
  int second; 
}

void setup() {
  long magic;
  eeprom_read(magic, magic);
  if(magic != magic_number)
    initialise_eeprom();
}

void initialise_eeprom() {
  eeprom_write(0, first);
  eeprom_write(0, second);
  eeprom_write(magic_number, magic);
}

I first read about the Engineyard Programming Contest yesterday and I thought it was a silly contest, winnable only through the application of raw brute force.

For some reason, I woke up this morning obsessed with it. This is despite the fact that this “competition” is basically a lottery, in which you buy tickets with basic programming skills and large amounts of computing time.

In the spirit of sharing, I have a few (fairly obvious) things I’ve noticed in an evening of messing around.

I’m not any kind of cryptographer, but from what I know about the known weaknesses in SHA-1, none of them will apply significantly to this contest. Maybe I’m wrong though.

The Avalanche effect means you don’t have to change much in the input to see a big change in the output. So making large changes (whole word permutations) is a waste of cycles.

Permutating the word list at all is almost unnecessary. One core on my 2.2Ghz Macbook pro takes 45 minutes to check all 7.7 billion combinations of printable five-character strings for a single word list combination. Once you add the possibilities for varying capitalisation in a single sentence (at least 2^40), you have more permutations in a single word list string than a single core can run in many times the 30 hours of test time. So distributing word list permutations is, at most, the “top level” job to distribute work to each cpu.

SHA-1 uses 64-byte blocks so if your total string is more than 64 bytes and the first 64 bytes don’t change, you can calculate that hash separately just once. Testing on an 85-character test string (the one from the competition blog posting), this got me from 1.6 million hash checks per second per core to 2.5 million/second/core.

Using gcc’s __builtin_popcount() and/or the x86 popcntl instruction lets you compute hamming distance in a handful of instructons.

None of this matters at all, although it’s fun to think about. Even with all these optimisations, I still have at most 16 cores (work and home) to run this on. The winner will have hundreds or thousands of parallel cores at their disposal.

Programming skills seem to only play a minor part. Several hours of optimisation only yielded me a 60% improvement compared to my original naive C program. Although, one of the posters on HN suggested he was only getting a tenth of that performance, which suggests a combination of language choice and savvy performance design may be statistically significant in the long run.

I will laugh if the winner is a shady programmer with a medium sized botnet as his or her disposal.

Does anyone have any more optimisations to share? Despite it being kinda pointless, I find this kind of thing really interesting. I honestly don’t plan to enter, except for maybe out of curiosity to see how close a single consumer computer can get to the winning results.