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.


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.


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()

    * 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(c ? "TRUE" : "FALSE");
     * 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]);

void loop() { }

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


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 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)

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

See here for my review of the M001.

Eken M001

This teardown shows the V006 revision of the board, a quick serial port install, and includes some console/dmesg output. The main difference between V005 and V006/V007 board revisions seems to be relocating the USB WiFi dongle to a better position.

EDIT: It took me a while to post this article, and Slatedroid is down this past week. So links to there will be broken (hopefully not for good.)

This isn’t the first teardown of the Eken M001, the first one was the “Aimless Teardown” and there is also a disassembly howto video by another community member.


I’ve had lots of hardware problems with my Eken since I took it apart. They may have been there before, but maybe not. YMMV, but be careful and remember you may not still have a warranty after the device has been opened, and especially after it’s been modified.

Specifically, I have two problems. There is a cold solder joint in one corner of the board (I’m currently warming it up before it will boot at all.) Also I get occasional failure of the LCD (totally black) on reassembly, which requires me to press on the front of the unit until it clicks back on.

Getting In

  1. Remove the two phillips screws on each side of the base:
    Base of Eken
  2. The only other thing holding the back on is a series of plastic clips around the outside of the unit. Working from the base (the first clip is half-way between the two screws), carefully insert a plastic spudger or a knife (worse, but what I used) and jiggle it around until each clip snaps open. Some clips may break, they’re not very strong.

    Then work your way along towards the top of the unit:
    Eken part open

    Eken more open

  3. Once all the clips have popped, remove the plastic back. Take care not to disturb the small speaker
    Small speaker in the plastic back
    Plastic back

Main Board

Main board as installed
(Click through for a high-res version.)

You can see:

  • Battery and backlight connectors bottom-left
  • Internal USB soldered to pads bottom-right (leading up to the USB WiFi module, installed top left.)
  • LCD and touchscreen ribbon connectors on the left side.
  • Main CPU daughterboard in DIMM socket.
  • CPU Board

    Here’s some shots of the CPU daughterboard:
    CPU daughterboard front
    CPU daughterboard back
    The board is hosting a VIA/Wondermedia WM8505 SoC. Datasheet shared here (courtesy Slatedroid, again.

    Serial Connector

    J17 on the back of the board is a RvTTL (3.3v) serial port. 115200 8N1. Pinout, left to right, is Vcc Tx Rx Gnd.

    I didn’t take any photos of it before I soldered on my serial port, but here it is after:
    Eken M001 serial port

    The only other interesting thing I saw on the back of the board was the 2Gb NAND flash:
    2Gb NAND flash

    Boot logs

    Once you have the serial port connected, you can grab some log data easily (and you also get a root shell once startup completes.)

    EDIT: As of firmware release 1.7.4, no more automatic root shell on serial console. It’s still a boot console, but for root you need to log in… Poor show, Eken.

    Standard kernel boot log, plus some /proc entries
    Log of a factory upgrade via SD card

    I meant to capture and post some of the ‘logcat’ Android log output as well, from standard startup, but it doesn’t look like I kept any.

IMPORTANT EDIT: There is now an Alpha release of Froyo hacked onto the Eken M001. This isn’t the same as full support, but it’s a step in the right direction!

Over the past couple of evenings I’ve been looking into porting Android 2.x (eclair or froyo) to the Eken M001. These are my notes from unsuccessful binary-only reverse engineering.

Short version

Although Android 2.1, and possibly 2.2, will run against Eken’s supplied 2.6.29 kernel, Eken have patched several of the ‘base’ userspace binaries against the proprietary Wondermedia SDK. Without accessing the SDK, or reverse engineering the SDK’s workings, it may not be possible to port Android 2.x to the Eken.

I worked this out trying to install the iPhone Android 2.2 port by munging it into the existing Eken binary firmware. I initially had a lot of success, because the link I followed was completely wrong, and I had the Android 1.6 iPhone build. After I got that booting to the home screen, someone on the slatedroid forums let me know it was the wrong version. Oops! I then found a genuine binary release of Froyo for iPhone and tried the same tricks, without success.

In this post I’ll explain what I learned. I hope it’s of use to someone.

Differences in firmware format

One of the first things that you’ll notice is that Eken firmware looks different to “normal” Android disk images. Instead of a group of disk images, the main Android userspace data is contained in two tarballs – android_fs.tgz and data.tgz. android_fs.tgz contains the parts of the filesystem would normally be mounted from ramdisk.img and system.img, data.tgz contains the parts from userdata.img.

A u-boot script (scriptcmd) in the firmware package performs an initial flash of the bootloader and then directs the Eken to boot from a small ramdisk image on the SD card. Ramdisk init then runs update.sh to reflash the firmware onto the internal flash.

Other than the different firmware image layout, the firmware layout of a running Eken is similar to any other Android system.

Using the Eken kernel

There are no kernel sources, so the Eken-provided 2.6.29 kernel is the only one we have. Slatedroid user bushing has started working on an alternative kernel, here, but it is very early days (doesn’t boot, let alone support any of the Eken’s WM8505 hardware.)

I don’t this is the big problem for Android 2.x, though. 2.1 officially supports kernel 2.6.29, and it looks like the 2.2 userspace components might even run against the 2.6.29 kernel without any serious problems (although probably with reduced performance.)

Getting info

The serial port on the board gives you a linux kernel console, and then a root shell with busybox. Running ‘logcat’ gives you the Android log as it runs. Run ‘logcat -d’ if you don’t want to lose your root shell forever. Strace is also available.

Munging the firmwares

My dodgy technique for munging the firmwares together was, roughly:

  • Copy the iPhone system.img contents over system/ in android_fs
  • Copy init and init.rc from iPhone ramdisk.img to the root of android_fs
  • Merge differences between the new init.rc and the old Eken one.
  • Flash & Boot!

Dodgy framebuffer driver

This method eventually leaves you with a flashing LCD display, showing 4 distorted copies of the screen you’re expecting. That’s what I got with 1.6 & 2.2, and I think that’s where Slatedroid modder ECOTOX got to as well.

If the Eken kernel provided a properly supported framebuffer device, this wouldn’t happen. The framebuffer device looks correct (although unaccelerated):

/ # fbset -s -fb /dev/graphics/fb0

mode "800x480-0"
# D: 0.033 MHz, H: 0.035 kHz, V: 0.066 Hz
geometry 800 480 800 480 32
timings 30000000 40 24 32 11 96 2
accel false
rgba 8/16,8/8,8/0,0/0

… but that’s not enough. There’s some userspace magic required to make the display work properly. Normally this would be implemented in the driver itself, and standard ioctl calls would make the changes. In this case, Android’s /system/lib/libui.so has been patched and now links against libwmtapi.so, a proprietary Wondermedia WM8505 SDK library:

:lib gus$ strings libui.so | grep wmt

… I have no idea what it’s doing, but when I copied the patched libui.so (and dependencies) onto my Android 1.6 iPhone system, the display immediately started working.

On Android 2.2, copying the library causes system_server to segfault because the library is no longer ABI compatible. There have been big changes, just look at the 1.6 ui headers compared to the 2.1 ui headers. So there’s no way the patched libui will work without the source patches being merged and recompiled, at the minimum.

That’s not all either, there are actually quite a few Android libraries linked against WMT libraries, presumably with other patches:

$ grep libwmt *
Binary file libcamera.so matches
Binary file libmediaplayerservice.so matches
Binary file libopencore_player.so matches
Binary file libui.so matches

Where to from here?

Speaking for myself, I’m done, unless Eken release their Android & kernel sources. There’s no sense in working to improve a product when the company itself is blatantly abusing OSS and refusing to honour its obligations.

On the other hand, even if an Eken source release left out the Wondermedia SDK, it would be a great start.

In the absense of the source, it seems there would be two options for the intrepid coder. The first would be to reverse-engineer the WM8505 hardware and write an OSS version of the platform drivers. This would be a massive job, although there is a datasheet we don’t even have JTAG available for debugging.

Alternatively, some judicious use of objdump would probably show what calls are being made to libwmt. With that knowledge, it is possible to reverse engineer function declarations and create patches for the relevant sources in Android 1.6, then port those source patches to Android 2.x. (I posted steps that I would try to follow, here.)

This is just a quick note on some experiences using an external USB drive with OpenWRT 8.09 on an Asus WL-500gP.

Mount options not honoured

It seems that mount options set in /etc/fstab aren’t honoured properly. I’ve filed a bug report here with a fix. If you have a running OpenWRT installation, you can grab the /sbin/usb-storage replacement from there and copy it onto your router.

A particular badness of this bug is if you’re relying noatime/nodiratime to stop your disk spinning up, or your USB stick wearing out(!)

USB startup timing

This isn’t a bug in OpenWRT, just an annoyance.

On the Asus WL-500gP (at least), USB devices don’t come online until 10-20 seconds after startup. This means that USB disks don’t mount until some time during the boot process.

This causes a problem if you have any init scripts that rely on an external disk (for example, if you’ve added Optware packages and symlinked in some Optware init scripts.)

The (half-assed) solution I have come up with is to put in an init script that waits for usb-storage to come online, and then sleeps while the disks are mounted. Make sure this script runs before any other init scripts that require the external disk.

  1. Download the script from here
  2. Copy the script to /etc/init.d on the router.
  3. Enable it with /etc/init.d/usb-storage enable
  4. You will now have /etc/rc.d/S50usb-storage. Make sure any other init scripts that rely on external disks come after ’50’

There are a variety of other hacks to get all this stuff working, this is just my take on it. It looks like external storage has been dramatically overhauled in the upcoming OpenWRT release, so hopefully it will no longer be an issue.

EDIT: The setup described below worked fine for me for six months, with only the annoyances described below (mostly not being able to traverse DHCP requests across the bridge.) However, I recently upgraded to OpenWRT Backfire and took the opportunity to replace my proprietary ADSL router with a Fonera. This allowed me to switch over to WDS as described in this post. So this setup is no longer in use at my house.

Renting sucks when you’re a nerd. When you move, you have to re-network all your bits and pieces, without the benefits of laying cable. Wireless is great, but not every network device has it. I have a VoIP phone and an XBMC XBox, each without wireless and each in a separate room.

I need a way to connect the phone and the Xbox to my existing wireless access point.

Here’s a rough diagram of my network:

Wired & Unwired Diagram
Rough diagram of my network


I want a flat network, single broadcast domain, for all of the (wired and unwired) devices in the diagram above.

I already have two Linux-compatible wireless routers, an Asus WL-500G and a Fonera. Both running OpenWRT.

If my routers had Broadcom wireless chipsets then this task would be easy. Thanks to driver support, OpenWRT can automatically bridge network segments through a wireless client (at least on 2.4 kernels, not sure about 2.6.) Neither of my routers have Broadcom. The Asus used to have it, but I swapped in an Atheros card. Oops.

WDS is a possibility, using each router as a repeater station. However, each repeater costs half the available bandwidth. I also can’t get WDS+WPA to work with my access point. YMMV.

You can set up separate networks, one for each segment, and the routers can route(!) between them using iptables. I’ve tried this and I don’t like it. It’s much easier when you have one single network with a single broadcast domain: simple DHCP, simple NetBIOS lookups, no routing tables to maintain, etc.

The final option, and the one I settled on, is using ARP-NAT.

What is ARPNAT?

ARPNAT is a clever hack. It’s the same idea as NAT for IP networks, except it works one layer deeper. Instead of translating IP network addresses, the router translates between the MAC hardware addresses on each side of it.

If something on the wired side of the router makes an ARP request for the MAC address of an IP on the wireless side, then the router forwards the request as if it came from the router. When the response comes back, it mangles that too. Instead of passing back the real MAC (which lives on the wireless network), the router gives its own wired MAC address. Then, when it receives frames for IP addresses on the wireless network, it forwards them through. It does this to both sides of the bridge.

Here’s an example, taken from my network:

  1. XBMC Xbox asks “What is the MAC address of Tell me:” This is a broadcast ARP request over the wired ethernet.
  2. Asus router sees the ARP request, and forwards the broadcast onto the wireless network, as “What is the MAC address of Tell me:”
  3. Access point (at gets the ARP request from the wireless, and replies with its MAC address: AA:AA:AA:AA:AA:AA.
  4. Asus router gets the ARP response, sent to It mangles it and forwards it back to the Xbox as “ is at BB:BB:BB:BB:BB:BB”, where BB:BB:BB:BB:BB:BB is the wired address of the Asus itself.
  5. Now, any time the Xbox wants to talk to, it will talk to BB:BB:BB:BB:BB:BB, and the Asus will forward that frame onto the wireless network, to the real destination AA:AA:AA:AA:AA:AA.

On Linux, this is done using a patched version of the ethernet filtering program ebtables.

How to do it?

Out of the box, OpenWRT does not support either ebtables or ARPNAT. The developers have expressed opinions that ARPNAT is a hack, and ebtables is too slow (see here & here.) We’ll get to that issue, later.

However, there are some forum posts that show how to do it. In this post, a developer of the OpenWRT fork Gargoyle links to their patch for ARPNAT. So, one option is to just use Gargoyle. Gargoyle apparently has a very nice web interface, and is good for intermediate users. I prefer flat config files, so I’m going to stick with OpenWRT.

Building OpenWRT with ARPNAT Support

If you’ve never compiled OpenWRT before, start here. Alternatively, I have some prebuilt 8.09.2 images for Atheros devices (like the Fonera), here.

To build, you’ll need two patches. One is from Gargoyle. The other is a small bugfix to allow a DHCP client to run on the router. The patches can be found here. These patches are against the 8.09 branch of OpenWRT SVN, I don’t think either will apply to the trunk.

EDIT: I’ve just posted a slightly different patch, 04-arpnat-brcm47xx.patch, for brcm47xxx devices like the Asus WL-500g. It’s different because these devices have an older kernel version in 8.09, and also because the arpnat kernel module doesn’t seem to load the first time around. Also, on this architecture DHCP responses don’t seem to pass back correctly to devices on the other side of the bridge (while on my Atheros-based Fonera they are passed back.) I’m just using a static IP on those devices, for now. Things will also work fine if the DHCP server is on the bridge router, itself.

You’ll need to enable ‘ebtables’ in your configuration (ie when you make menuconfig.) You’ll probably want wpa-supplicant as well. The .config that I used for the Fonera can be found at the link above, as well.

Once up and running, /etc/config/wireless only needs one tweak. Here’s mine:

config wifi-device  wifi0
	option type     atheros
	option channel  auto

config wifi-iface
	option device	wifi0
	option network	lan
	option mode	sta
	option client_bridge 1
	option ssid	<your ssid here>
	option encryption psk
	option key <your key here>

The only difference is “option client_bridge 1“, which indicates that you want ARPNAT enabled.

/etc/config/network is simple, too. Here’s the bridge section of mine:

config interface lan
	option ifname	eth0
	option type 	bridge
	option macaddr  CC:CC:CC:CC:CC:CC
	option proto	dhcp

The only difference here is option macaddr. You will need this only if you want to assign the router’s IP address dynamically via DHCP. If you do this, “option macaddr” must be set to the MAC address of the interface where the DHCP server lives (ie wired side or wireless side.) The DHCP request will only go out on a single interface, so you need to make sure it is the correct one.

If you don’t need DHCP then you don’t need to manually assign any MAC address. “option macaddr” can be totally removed.

That’s it! When the router boots up, it will connect to the wireless network, and any devices on the wired side will automatically be bridged onto the wireless (and vice-versa.) To them, it just looks like one big seamless network.

Bear in mind that not all routers support failsafe mode (Fonera for one), so if these values are wrong then you may end up locked out of your router, especially if you run the router with a DHCP-assigned address. If you’re not certain, I recommend running with a static IP first, so you can always plug in a network cable and still connect to the router.

Thanks again to Eric Bishop and the Gargoyle project, because it’s really his patch (building on other people’s work for ARPNAT) that makes all this possible.

Problems with ARPNAT

The OpenWRT developers will not consider ARPNAT, or even include ebtables, in the default package set of OpenWRT. They say this is because of performance impact. Every ethernet frame that hits the router needs to be inspected in software, so it’s understandable that there will be a cost.

Some cost is OK by me, in exchange for convenience. So I did some tests:

The test methodology was to ping flood the Fonera from a PC:

Performance of ebtables & ARPNAT (longer is better)
  • “Ethernet, no ebtables” is a vanilla Openwrt 8.09.2 install
  • “Ethernet, ebtables installed” is with patches and ebtables installed, but no ARPNAT enabled.
  • “Ethernet, ARPNAT enabled” is with ARPNAT turned on, but no traversal (the pings still go just to the router.)
  • “Direct WiFi” is pinging the router directly over the wireless network. It’s slower, but only because WiFi is slower than ethernet.
  • “WiFi via ARPNAT” is pinging a client on the wireless side, from a client on the wired side. So the ping is going through ARPNAT translation on the router.

Under all of these tests the CPU on the router was pegged at >95%.

The results seem to show that ebtables & ARPNAT do not drastically affect the performance of the Fonera. Turning on ARPNAT causes direct traffic to the router to be about 17% more costly. Actually bridging packets through ARPNET on the router is only 32% more costly than directly accessing the router itself.

I’m surprised these figures aren’t worse, given the doom & gloom spouted by the OpenWRT devs. It’s possible there’s another circumstance under which ARPNAT falls over, or possibly it performs worse on certain architectures. I’ll post back if I learn anything interesting.

EDIT: One more discovery, obvious in retrospect, is that IPv6 won’t get ARPNATted by this config. If you have any devices that use IPv6 (like iTunes talking to an Apple Airport Express), you’ll either need to disable IPv6 or tweak the ebtables scripts somehow to translate IPv6 as well. I opted for disabling IPv6.

If you upgrade OS X to Snow Leopard, and Word 2004 starts locking up, freezing, not responding when you try to open a document, forcing you to force quit, then it’s probably a font cache issue.

The easy way to clear the cache is to reboot with the “Shift” key held down. This does a “safe mode” boot. Then log in, and verify you can open your document. If it works, restart into normal mode and it should just keep working.

This probably also works: Open a terminal, run sudo atsutil databases -remove, and then reboot.

If this doesn’t work, you might need to open the Font Book application and do Edit -> Resolve Duplicates. But I don’t think that step was actually necessary.

Hth. It’s alluded to around the internet, but I thought I’d put our experience out clearly.

I had some automatically code generated files that I wanted to mark as read-only. I knew it was possible to flag a file as read-only in both emacs and vim. However, I found it really hard to Google for the exact syntax.

In Vim, the flags go in the file’s “modelines“, which by default can go anywhere in the first or last five lines of the file:

// vim:set ro:

In emacs, there is the “local variable list“. Sometimes known as the “magic first line” or the “file mode line”. This is a list of variables to set when the file is opened. So for a read only file, set the buffer-read-only variable:

// -*- buffer-read-only:t -*- 

This only works on the first line of the file. There’s a different form for the end of the file, follow the link to see details.

Here is a first line that flags the file as read only in both emacs and vim:

// vim:set ro: -*- buffer-read-only:t -*- 

The code generator now automatically adds this line to generated C++, Erlang and Java files, in order to prevent accidental edits.

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.

I recently bought a couple of cheap MG996R high-torque servos on ebay, and I want to use them with my Arduino.

Arduino + MG996 + Dusty Breadboard

These have the “JR” servo pinout, so orange = signal, red = V+, brown = V-.

You control these servos by sending a 50Hz pulse width modulated signal. The pulse width determines the position of the servo. Arduino wraps this in a nice Servo library. So you can just use servo.write(<angle>) to set the servo to a certain angle. Cool!

The servo library defaults to pulsing 544ms to 2400ms for angles zero to 180. This is too wide for the MG996R, the servo only moves when you write angles through 20-150 or so. Setting the value outside this range stresses the servo and can wear it out!

I wrote a quick sketch to interactively find the real minimum and maximum values: . You just watch the serial port and follow simple prompts:

Download the sketch here.

Servo Range Sketch (running)

Using that sketch, I found my MG996R servos to have minimum pulse width around 771 and maximum around 2193 when running off 5v1. The full sweep is approximately 0-130 degrees.

So, to use the servo library with correct angles the sweep will be 771 to 27402. So I can call:

servo.attach(servopin, 771, 2740);
servo.write(0); // Min
servo.write(65); // Midpoint
servo.write(130); // Max

Note: If setting up the Servo range like this, it’s important not to drive the servo past 130 degrees – which corresponds to pulse width 2193 and the maximum position of the servo.

EDIT 2018: Fixed a nine year old bug in the formula above, thanks Dillon and Stavros for pointing it out.

Yay Arduino!

  1. While the servo is unloaded I’m powering it from the Arduino via USB, but this won’t supply enough current for a loaded servo. []
  2. The adjusted max of 2740 is calculated as ( (MaxPW – MinPW) * (180 / MaxAngle) ) + MinPW, ie ( (2193 – 771) * (180 / 130) ) + 771 []