Project Gus

First Steps

I’m a very recent (3 days) user of scratchbox2 for cross-compiling. My initial response was “this is crazy magic” awe, followed shortly by “this is a crazy mountain of hacks” skepticism. However, after some use & success now, it seems to be a really neat tool.

The best introductions to scratchbox2 that I’ve found are this wiki page from the plugcomputing people, and this nice succinct set of presentation slides from Riku Voipi.

One of the big annoyances has been seeking information, Google likes to replace sb2 (the main scratchbox2 command) with db2 and scratchbox2 with scratchbox.

Multiarch

I have found that scratchbox2 (as of 2.3.3) is a bit fiddly when targeting Debian wheezy or sid (testing or unstable.) This is due to the new Debian Multiarch support.

In a nutshell, multiarch means libraries and tools are moving from locations like /usr/lib to arch-specific locations like /usr/lib/[triplet] where triplet identifies the architecture, ie arm-linux-gnueabi for ARM systems.

The symptoms I saw were linking errors (or configuration failures) due to missing libraries, when you know they are installed on the target. The crucial test is whether “sb2 [some-simple-command]” fails while “sb2 -e [same-simple-command]” passes – this implies that the problem is in the host translation, not in the target (otherwise it would fail in the -e qemu’d environment, as well.)

Here’s what worked for me. In the file ~/.scratchbox2/[TARGETNAME]/gcc.config.lua, I sought out and changed the following two config items as follows, to add linker search paths:

extra_cross_compiler_args="   -L@SBOX_TARGET_ROOT@/usr/lib -L@SBOX_TARGET_ROOT@/usr/lib/arm-linux-gnueabi -L@SBOX_TARGET_ROOT@/lib  -L@SBOX_TARGET_ROOT@/lib/arm-linux-gnueabi",

extra_cross_ld_args="-rpath-link @SBOX_TARGET_ROOT@/usr/lib/arm-linux-gnueabi:@SBOX_TARGET_ROOT@/usr/lib:@SBOX_TARGET_ROOT@/lib:@SBOX_TARGET_ROOT@/lib/arm-linux-gnueabi",

I also ran the command

sb2-config setenv PKG_CONFIG_PATH /usr/lib/pkgconfig/:/usr/lib/arm-linux-gnueabi/pkgconfig/

(In all the above, replace arm-linux-gnueabi with your target architecture’s “triplet” of choice.)

As always, the solutions are simple and easy to follow once you know what they are. :) Please bear in mind also that this may not be the best solution, I’m still a scratchbox2 newbie.

Distro Versions

The other major gotcha, hinted at in the presentation I linked to, is that the host and the target distros must match exactly. If you have different library versions on each then you are headed for problems.

This can be tricky even when the distros match. At time of writing debian wheezy uses libc6-dev 2.13 on amd64 but emdebian wheezy uses libc6-dev-armel-cross 2.11 for the cross-compiler. The header files are different enough to cause builds to fail. To get matching headers I had to change to emdebian sid, which currently has libc6-dev-armel-cross 2.13.

An alternative, also hinted at in the presentation, is to set up a “tools” distro. This is a directory with a complete host-arch distribution, matching perfectly the target’s distro except for the architecture. It seems the idea there is to create a controlled single-purpose environment, instead of just sharing the host’s tools. Maybe that’s a cleaner path, especially if it lets you sandbox a stable distro release with predictable versions.

(Extended Rant, Feel Free to Ignore)

The header-mismatch problem seems to be caused because programs compiled under sb2 can search for headers in both the host directory /usr/include/, and also in the cross-compiler directory (ie /usr/arm-linux-gnueabi/include/), -and- in the target rootfs directory.

Exactly which header file gets chosen for which purpose seems to be somewhat haphazard – in the example I saw, a #include <fcntl.h> was pulling in /usr/include/fcntl.h which was then pulling /usr/arm-linux-gnueabi/include/bits/stat.h.

I haven’t dug deep enough into sb2 to see what’s really going on here with gcc include paths, but it seems like it should be possible to workaround this and ignore the host’s headers entirely – in favour of the cross-compiler headers & those installed in the target rootfs.

However, passing these paths explicitly is exactly the kind of drudgery that sb2 tries to avoid with its “magic”, so at this stage I’m leaving it – my program compiles & links, so that’s good enough for now. If I end up having to explicitly set everything then I may as well create a conventional cross-compiler environment.

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.