To follow up on yesterday’s post, here is some code to extract a bit field. First, a refresher:

The field marked in blue is the value we’d like to extract. One way to do this is to “manually” pick each of the pieces and assemble them into the desired form:

Here is a little CoffeeScript test version:

buf = new Buffer [23, 125, 22, 2]

for i in [0..3]
  console.log "buf[#{i}] = #{buf[i]} = #{buf[i].toString(2)} b"

x = buf.readUInt32LE 0
console.log "read as 32-bit LE = #{x.toString 2} b"

b1 = buf[1] >> 7
b2 = buf[2]
b3 = buf[3] & 0b111
w = b1 + (b2 << 1) + (b3 << 9)
console.log "extracted from buf: #{w} = #{w.toString 2} b"

v = (x >> 15) & 0b111111111111
console.log "extracted from int: #{v} = #{v.toString 2} b"

Or, if you prefer JavaScript, the same thing:

var buf = new Buffer([23, 125, 22, 2]);

for (var i = 0; i <= 3; ++i) {
  console.log("buf["+i+"] = "+buf[i]+" = "+buf[i].toString(2)+" b");
}

var x = buf.readUInt32LE(0);
console.log("read as 32-bit LE = "+x.toString(2)+" b");

var b1 = buf[1] >> 7;
var b2 = buf[2];
var b3 = buf[3] & 0x7;
var w = b1 + (b2 << 1) + (b3 << 9);
console.log("extracted from buf: "+w+" = "+w.toString(2)+" b");

var v = (x >> 15) & 0xfff;
console.log("extracted from int: "+v+" = "+v.toString(2)+" b");

The output is:

    buf[0] = 23 = 10111 b
    buf[1] = 125 = 1111101 b
    buf[2] = 22 = 10110 b
    buf[3] = 2 = 10 b
    read as 32-bit LE = 10000101100111110100010111 b
    extracted from buf: 1068 = 10000101100 b
    extracted from int: 1068 = 10000101100 b

This illustrates two ways to extract the data: “w” was extracted as described above, but “v” used a trick: first use built-in logic to extract an integer field which is too big (but with all the bits in the right order), then use bit shifting and masking to pull out the required field. The latter is much simpler, more concise, and usually also a little faster.

Here’s an example in Python, illustrating that second approach via “unpack”:

import struct

buf = struct.pack('BBBB', 23, 125, 22, 2)
(x,) = struct.unpack('<l', buf)

v = (x >> 15) & 0xFFF
print(v)

And lastly, the same in Lua, another popular language:

require 'struct'
require 'bit'

buf = struct.pack('BBBB', 23, 125, 22, 2)
x = struct.unpack('<I4', buf)

v = bit.band(bit.rshift(x, 15), 0xFFF)
print(v)

So there you go, lots of ways to extract useful data from the RF12demo sketch output!

Prompted by a recent discussion on the forum, and because it’s a recurring theme, I thought I’d go a bit (heh…) into how bit fields work.

One common use-case in Jee-land, is with packets coming in from a roomNode sketch, which are reported by the RF12demo sketch on USB serial as something like:

OK 3 23 125 22 2

The roomNode sketch tightly packs its results into a packet using this C structure:

struct {
    byte light;     // light sensor: 0..255
    byte moved :1;  // motion detector: 0..1
    byte humi  :7;  // humidity: 0..100
    int temp   :10; // temperature: -500..+500 (tenths)
    byte lobat :1;  // supply voltage dropped under 3.1V: 0..1
} payload;

So how do you get the values back out, given just those 4 bytes (plus a header byte)?

To illustrate, I’ll use a slightly more complicated example. But first, some diagrams:

That’s 4 consecutive bytes in memory, and two ways a 32-bit long int can be mapped to it:

• little-endian (LE) means that the first byte (at #00) points to the little end of the int
• big-endian (BE) means that the first byte (at #00) points to the big end of the int

Obvious, right? On x86 machines, and also the ATmega, everything is stored in LE format, so that’s what I’ll focus on from now on (PIC and ARM are also LE, but MIPS is BE).

Let’s use this example, which is a little more interesting (and harder) to figure out:

struct {
    unsigned long before :15;
    unsigned long value :12;  // the value we're interested in
    unsigned long after :3;
} payload;

That’s 30 bits of payload. On an ATmega the compiler will use the layout shown on the left:

But here’s where things start getting hairy. If you had used the definition below instead, then you’d have gotten a different packed structure, as shown above on the right:

struct {
    unsigned int before :15;
    unsigned int value :12;  // the value we're interested in
    unsigned int after :3;
} payload;

Subtle difference, eh? The reason for this is that the declared size (long vs int) determines the unit of memory in which the compiler tries to squeeze the bit field. Since an int is 16 bits, and 15 bits were already assigned to the “before” field, the next “value” field won’t fit so the compiler will restart on a fresh byte boundary! IOW, be sure to understand what the compiler does before trying to decode stuff. One way to figure out what’s going on, is to set the values to some distinctive bit patterns and see what comes out as bytes:

payload.before = 0b1;  // bit 0 set
payload.value = 0b11;  // bits 0 and 1 set
payload.after = 0b111; // bits 0, 1, and 2 set

Tomorrow, I’ll show a couple of ways to extract this bit field.

No, not the medical term, and not this carambolage either (though it’s related):

What I’m talking about is the software kind: back pressure is what you need in some cases to avoid running into resource limits. There are many scenario’s where this can be an issue:

• In the case of highway pile-ups, the solution is to add road signalling, so drivers can be warned to slow down ahead of time – before that decision is taken from them…
• Sending out more data than a receiver can handle – this is why traditional serial links had “handshake” mechanisms, either software (XON/XOFF) or hardware (CTS/RTS).
• On the I2C bus, hardware-based clock stretching is often supported as mechanism for a slave to slow down the master, i.e. an explicit form of back pressure.
• Sending out more packets than (some node in) a network can handle – which is why backpressure routing was invented.
• Writing out more data to the disk than the driver/controller can handle – in this case, the OS kernel will step in and suspend your process until things calm down again.
• Bringing a web server to its knees when it gets more requests than it can handle – crummy sites often suffer from this, unless the front end is clever enough to reject requests at some point, instead of trying to queue more and more work which it can’t possibly ever deal with.
• Filling up memory in some dynamic programming languages, where the garbage collector can’t keep up and fails to release unused memory fast enough (assuming there is any memory to release, that is).

That last one is the one that bit me recently, as I was trying to reprocess my 5 years of data from JeeMon and HouseMon, to feed it into the new LevelDB storage system. The problem arises, because so much in Node.js is asynchronous, i.e. you can send off a value to another part of the app, and the call will return immediately. In a heavy loop, it’s easy to send off so much data that the callee never gets a chance to process it all.

I knew that this sort of processing would be hard in HouseMon, even for a modern laptop with oodles of CPU power and gigabytes of RAM. And even though it should all run on a Raspberry Pi eventually, I didn’t mind if reprocessing one year of log files would take, say, an entire day. The idea being that you only need to do this once, and perhaps repeat it when there is a major change in the main code.

But it went much worse than I expected: after force-feeding about 4 months of logs (a few hundred thousand converted data readings), the Node.js process RAM consumption was about 1.5 GB, and Node.js was frantically running its garbage collector to try and deal with the situation. At that point, all processing stopped with a single CPU thread stuck at 100%, and things locked up so hard that Node.js didn’t even respond to a CTRL-C interrupt.

Now 1.5 GB is a known limit in the V8 engine used in Node.js, and to be honest it really is more than enough for the purposes and contexts for which I’m using it in HouseMon. The problem is not more memory, the problem is that it’s filling up. I haven’t solved this problem yet, but it’s clear that some sort of back pressure mechanism is needed here – well… either that, or there’s some nasty memory leak in my code (not unlikely, actually).

Note that there are elegant solutions to this problem. One of them is to stop having a producer push data and calls down a processing pipeline, and switch to a design where the consumer pulls data when it is ready for it. This was in fact one of the recent big changes in Node.js 0.10, with its streams2 redesign.

Even on an embedded system, back pressure may cause trouble in software. This is why there is an rf12_canSend() call in the RF12 driver: because of that, you cannot ever feed it more packets than the (relatively slow) wireless RFM12B module can handle.

Soooo… in theory, back pressure is always needed when you have some constraint further down the processing pipeline. In practice, this issue can be ignored most of the time due to the slack present in most systems: if we send out at most a few messages per minute, as is common with home monitoring and automation, then it is extremely unlikely that any part of the system will ever get into any sort of overload. Here, back pressure can be ignored.

After yesterday’s hardware hookup, the next step is to set up the proper software for this.

There are a number of design and implementation decisions involved:

• how to format the data as a wireless packet
• how to generate and send out that packet on a JeeNode
• how to pick up and decode the data in Node.js

Let’s start with the packet: there will be one every 10 seconds, and it’s best to keep the packets as small as possible. I do not want to send out differences, like I did with the otRelay setup, since there’s really not that much to send. But I also don’t want to put too many decisions into the JeeNode sketch, in case things change at some point in the future.

The packet format I came up with is one which I’d like to re-use for some of the future nodes here at JeeLabs, since it’s a fairly convenient and general-purpose format:

       (format) (longvalue-1) (longvalue-2) ...

Yes, that’s right: longs!

The reason for this is that the electricity meter counters are in Watt-hour, and will immediately exceed what can be stored as 16-bit ints. And I really do want to send out the full values, also for gas consumption, which is in 1000th of a m3, i.e. in liters.

But for these P1 data packets that would be a format code + 8 longs, i.e. at least 25 bytes of data, which seems a bit wasteful. Especially since not all values need longs.

The solution is to encode each value as a variable-length integer, using only as many bytes as necessary to represent each value. The way this is done is to stored 7 bits of the value in each byte, reserving the top-most bit for a flag which is only set on the last byte.

With this encoding, 0 is sent as 0x80, 127 is sent as 0xFF, whereas 128 is sent as two bytes 0x01 + 0x80, 129 is sent as 0x01 + 0x81, 1024 as 0x08 + 0x80, etc.

Ints up to 7 bits take 1 byte, up to 14 take 2, … up to 28 take 4, and 32 will take 5 bytes.

It’s relatively simple to implement this on an ATmega, using a bit of recursion:

The full code of this p1scanner.ino sketch is now in JeeLib on GitHub.

Tomorrow, I’ll finish off with the code used on the receiving end and some results.

Ok, now that I have serial data from the P1 port with electricity and gas consumption readings, I would like to do something with it – like sending it out over wireless. The plan is to extend the homePower code in the node which is already collecting pulse data. But let’s not move too fast here – I don’t want to disrupt a running setup before it’s necessary.

So the first task ahead is to scan / parse those incoming packets shown yesterday.

There are several sketches and examples floating around the web on how to do this, but I thought it might be interesting to add a “minimalistic sauce” to the mix. The point is that an ATmega (let alone an ATtiny) is very ill-suited to string parsing, due to its severely limited memory. These packets consist of several hundreds of bytes of text, and if you want to do anything else alongside this parsing, then it’s frighteningly easy to run out of RAM.

So let’s tackle this from a somewhat different angle: what is the minimal processing we could apply to the incoming characters to extract the interesting values from them? Do we really have to collect each line and then apply string processing to it, followed by some text-to-number conversion?

This is the sketch I came up with (“Look, ma! No string processing!”):

This is a complete sketch, with yesterday’s test data built right into it. You’re looking at a scanner implemented as a hand-made Finite State Machine. The first quirk is that the “state” is spread out over three global variables. The second twist is that the above logic ignores everything it doesn’t care about.

Here’s what comes out, see if you can unravel the logic (see yesterday’s post for the data):

Yep – that’s just about what I need. This scanner requires no intermediate buffer (just 7 bytes of variable storage) and also very little code. The numeric type codes correspond to different parameters, each with a certain numeric value (I don’t care at this point what they mean). Some values have 8 digits precision, so I’m using a 32-bit int for conversion.

This will easily fit, even in an ATtiny. The moral of this story is: when processing data – even textual data – you don’t always have to think in terms of strings and parsing. Although regular expressions are probably the easiest way to parse such data, most 8-bit microcontrollers simply don’t have the memory for such “elaborate” tools. So there’s room for getting a bit more creative. There’s always a time to ask: can it be done simpler?

PS. I had a lot of fun come up with this approach. Minimalism is an addictive game.

The “benstream.lua” decoder I mentioned yesterday is based on coroutines. Since probably not everyone is familiar with them (they do not exist in languages such as C and C++), it seems worthwhile to go over this topic briefly.

Let’s start with this completely self-contained example, written in Lua:

Here’s the output generated from the test code at the end:

  (string) abcde
  (string) 123
  (number) 12345
  (boolean) false
  (number) 987
  (boolean) false
  (number) 654
  (table) 
  (number) 321
  (table) 
  (number) 99999999
  (boolean) true
  (string) one
  (number) 11
  (string) two
  (number) 22
  (table) 
  (string) bye!

There is some weird stuff in here, notably how the list start, dict start, and list/dict end are returned as “false”, “true”, and the empty list ({} in Lua), respectively. The only reason for this is that these three values are distinguishable from all the other possible return values, i.e. strings and numbers.

But the main point of this demo is to show what coroutines are and what they do. If you’re not familiar with them, they do take getting used to… but as you’ll see, it’s no big deal.

First, think about the task: we’re feeding characters into a function, and expect it to track where it is and return complete “tokens” once enough data has been fed through it. If it’s not ready, the “cwrap” function will return nil.

The trouble is that such code cannot be in control: it can’t “pull” more characters from the input when it needs them. Instead, it has to wait until it gets called again, somehow figure out where it was the last time, and then deal with that next character. For an input sequence such as “5:abcde”, we need to track being in the leading count, then skip the colon, then track the actual data bytes as they come in. In the C code I added to the EmBencode library recently, I had to implement a Finite State Machine to keep track of things. It’s not that hard, but it feels backwards. It’s like constantly being called away during a meeting, and having to pick up the discussion again each time you come back :)

Now look at the above code. It performs the same task as the C code, but it’s written as if it was in control! – i.e. we’re calling nextChar() to get the next character, looping and waiting as needed, and yet the coroutine is not actually pulling any data. As you can see, the test code at the end is feeding characters one by one – the normal way to “push” data, not “pull” it from the parsing loop. How is this possible?

The magic happens in nextchar(), which calls coroutine.yield() with an argument.

Yield does two things:

• it saves the complete state of execution (i.e. call stack)
• it causes the coroutine to return the argument given to it

It’s like popping the call stack, with one essential difference: we’re not throwing the stack contents away, we’re just moving it aside.

Calling a coroutine does almost exactly the opposite:

• it restores the saved state of execution
• it causes coroutine.yield() to return with the argument of the call

These are not full-blown continuations, as in Lisp, but sort of halfway there. There is an asymmetry in that there is a point in the code which creates and starts a coroutine, but from then on, these almost act like they are calling each other!

And that’s exactly what turns a “pull” scanner into a “push” scanner: the code thinks it is calling nextChar() to immediately obtain the next input character, but the system sneakily puts the code to sleep, and resumes the original caller. When the original caller is ready to push another character, the system again sneakily changes the perspective, resuming the scanner with the new data, as if it had never stopped.

This is in fact a pretty efficient way to perform multiple tasks. It’s not exactly multi-tasking, because the caller and the coroutine need to alternate calls to each other in lock-step for all this trickery to work, but the effect is almost the same.

The only confusing bit perhaps, is that argument to nextChar() – what does it do?

Well, this is the way to communicate results back to the caller. Every time the scanner calls nextChar(), it supplies it with the last token it found (or nil). The conversation goes like this: “I’m done, I’ve got this result for you, now please give me the next character”. If you think of “coroutine.yield” as sort of a synonym for “return”, then it probably looks a lot more familiar already – the difference being that we’re not returning from the caller, but from the entire coroutine context.

The beauty of coroutines is that you can hide the magic so that most of the code never knows it is running as part of a coroutine. It just does its thing, and “asks” for more by calling a function such as nextChar(), expecting to get a result as soon as that returns.

Which it does, but only after having been put under narcosis for a while. Coroutines are a very neat trick, that can simplify the code in languages such a Lua, Python, and Tcl.

A brief excursion into the land of advanced C++ tricks…

Create an enumTrick sketch with the following contents:

  #include "header.h"

  static int fun (One x) {
      return 10 + x;
  }

  static int fun (Two x) {
      return 20 + x;
  }

  void setup () {
      Serial.begin(57600);
      Serial.println("\n[enumTrick]");
      Serial.println(fun(A));
      Serial.println(fun(B));
      Serial.println(fun(C));
      Serial.println(fun(D));
      Serial.println(fun(E));
      Serial.println(fun(F));
  }

  void loop () {}

Now create a “header.h” file with the following contents:

  typedef enum { A, B, C } One;
  typedef enum { D, E, F } Two;

The stupid Arduino IDE pre-processing logic makes it necessary to place these definitions in a separate header file, unfortunately.

You can see that there are two definitions of fun (heh).

This code compiles without errors, because C++ supports “function overloading”, a mechanism to disambiguate function calls through the number and type of the arguments. In this case the args differ in type, being different enumeration constants.

Here’s the output:

  [enumTrick]
  10
  11
  12
  20
  21
  22

Note that if you were to call fun with an integer value, you’d get an error:

  enumTrick.cpp: In function 'void setup()':
  enumTrick:17: error: call of overloaded 'fun(int)' is ambiguous
  enumTrick.cpp:12: note: candidates are: int fun(One) <near match>
  enumTrick.cpp:13: note:                 int fun(Two) <near match>

Ok, so what’s the point?

Well, this provides a way to create a simpler API for drivers. Say we have a device which can turn the lights on and off, and dim the lights to a certain level (a Dimmer Plug, perhaps, or an X10 interface). We could do this:

typedef enum { ON, OFF } CmdSet1;
typedef enum { DIM } CmdSet2;

void DeviceControl (CmdSet1 cmd) { ... }
void DeviceControl (CmdSet2 cmd, byte level) { ... }

Now the only valid calls are those where ON or OFF is specified and nothing else, or DIM is specified and a single byte value is required. Every other mix generates an error at compile time. And there’s a single “DeviceControl” function you need to deal with and remember.

It’s definitely a contrived example, but I’m currently digging into some stuff which could probably benefit from this. Basically, you get static typing to help simplify more cases at compile time, which I expect will lead to more compact code.

Which – on a low-end 8-bit MPU – can be a big deal!

After yesterday’s post about source code control systems, here are some notes about getting started with it.

I’ll focus on Subversion, because that’s what I’m using.

Update, 2013 – Subversion is no longer in use, everything is now on GitHub.

There are two sides to a version control system: the server, where the source code “repository” is kept, and the client, which is your own workstation / PC. In distributed systems (DVCS), for example Git, there is no such asymmetry – client and server can perform the same tasks. But Subversion uses a centralized model: one repository, any number of clients.

You’ll need at least the client software to be able to use Subversion:

• On Windows, you can use TortoiseSVN. It integrates deeply with the Windows Explorer, meaning that the current status of each file is always visible. See this page for some screen shots.

• On Mac OSX it’s built-in (starting with 10.5, Leopard, I think) – although you probably have to install the Xcode that came with your Mac. You can check by typing “svn” in the terminal. If you get “Type ‘svn help’ for usage.”, then it’s ready for business.

• On Linux, it’s a package called “subversion”. Install via your favorite package manager, depending on which flavor of Linux you’re using (e.g. Ubuntu).

Here’s the big picture:

Assuming you’re trying this out with existing source code (from JeeLabs, for example), then the server is somewhere on the internet, so you don’t have to deal with its setup. A little terminology and some conventions:

• the server has all the source code and all the changes in a “repository”
• you can get a local “working copy” by “checking it out” from the server
• you can do anything you like on your copy, but…
• don’t rename files or move anything around, without telling subversion
• you cand send changes back by “checking them in” (a.k.a. “commit”)
• you can adjust your copy to the latest version by “updating” your copy

So the basic idea is to check out a working copy (once), and then doing an update whenever you want to make sure you have the latest and the greatest. This update is totally safe: if you made changes on your working copy, and you do an update, subversion will tell you that there are changes, and occasionally maybe even a “conflict”, i.e. if your changes interfere with changes made by others.

Note that conflicts can occur in two ways: when updating your modified copy, or when committing your changes back to the server. The latter can lead to a conflict when someone made changes which you didn’t pick up yet.

If you don’t intend to make changes, or only minimally, then conflicts are a non-issue. In that case, subversion is simply a convenient (and very quick/efficient) way to keep up to date with all the latest changes.

There is another convenience, in that you can check to see what has changed, before updating. Perhaps you want to first examine the changes – and only the changes – to decide whether you want to adopt that latest version. This can be done with the subversion “status” and “diff” commands, but with the new Redmine setup at JeeLabs, it’s actually much simpler to use the web interface for this. Simply browse the repository from the web, starting here, and review the comments shown under the “Latest revisions” header (last ones are at the top). By zooming in as described yesterday, you can quickly see whether the changes are of interest to you. You could even decide to opdate only a single source file. Subversion will track all this, even with some parts updated and others not.

Let me give an example how to use subversion for getting the Ports library. I’ll use the command-line interface for this, assuming that it maps relatively simply to the GUI-based TortoiseSVN on Windows.

Step 1 – Initial check-out

You need to be in the proper place to check out. In this case, we want to get a “Ports” folder inside a “libraries” folder, which in turn needs to be placed inside the Arduino IDE’s “sketches” directory. On Mac OSX, this is “~/Documents/Arduino”. So the first thing to do, is make sure that the libraries folder exists:

    % mkdir -p ~/Documents/Arduino/libraries

Then go to that directory:

    % cd ~/Documents/Arduino/libraries

Now, we’ll check out the Ports library from JeeLabs:

    % svn checkout svn://svn.jeelabs.org/jeelabs/trunk/libraries/Ports

A new directory is created with the same name, i.e. “Ports”. It will contain all the source files. So we’re essentially done.

One thing to note, is that subversion needs to track a bit of information (such as where this Ports thing came from and when it was checked out). It does this in sub-folders called “.svn” – the leading dot is a convention to keep this area hidden. So it’s there all right, but you often won’t see it. That’s fine. Never go in there and make any changes, or you’ll completely mess up your working copy, as far as subversion is concerned.

Step 2 – Using the source code

Nothing much to say here. Just use it as if you had created the Ports folder yourself, perhaps by unpacking a ZIP archive. Apart from the “.svn” hidden areas, it’s the same thing. You should check out a copy of the RF12 library as well, since that’s always needed when using the Ports library:

    % cd ~/Documents/Arduino/libraries
    % svn checkout svn://svn.jeelabs.org/jeelabs/trunk/libraries/RF12

You can make changes to the source files if you want to. Subversion will know what you did, when asked, because it keeps an extra copy of the original files in the “.svn” folders, and besides, it could also use the server to check.

The one thing you can’t do with subversion (some other systems are more lenient), is to delete, rename, or move files and folders as you were used to. Don’t do things like these, or use other commands or programs to the same effect:

    % mv foo.c bar.c
    % rm foo.h

Instead, ask subversion to do it for you, and all will be well:

    % svn mv foo.c bar.c
    % svn rm foo.h

Step 3 – Tracking updates

Updating your copy to the latest version in the repository is trivial, and can be done at any time with:

    % svn update

You will get a concise summary of which files were changed. Changes may also include adding new files and removing obsolete ones. After the update, your working copy will be in sync with the repository again.

If you only want to find out what would be changed, without actually updating anything, use the status command:

    % svn status -u

But usually it’s simpler to use the web interface for this. For the Ports library, just go to https://jeelabs.net/projects/cafe/repository/show/Ports.

Step 4 – Submitting changes

If you have write access to the repository, then you can also submit the changes you made in your working copy. All you need is a reason… :)

Seriously, the only thing that needs some thought is what to put in the comment describing this change. Because Subversion insists on some comment. I usually check in after every little change and add a very brief note describing it, such as:

    % svn ci -m "fixed bug X so Y works again"

Note that with all these commands, you don’t have to mention the respository at all. Subversion knows which repository is being referenced by looking at the information in the “.svn” folder in the current directory you’re in.

I won’t go into conflict resolution or any of the numerous more advanced commands in subversion. Check the excellent manual online to find out more.

That’s it!

The only comment I’d like to add to conclude this weblog post, is that the above was written specifically for subversion. Many other systems exists, but once you are used to the terminology and conventions of one, using another version control system is usually no big deal. Lots of people seem to be using Git these days. No doubt due to the free GitHub source repository server, available to anyone who wants to maintain their source code in a public place. It comes with a nice and powerful set of features, see the help section for an overview.

Have fun with version control – and say goodbye to version mixups once and for all!

From the beginning, all Open Source Software at JeeLabs has been maintained in a system called Subversion. This is a version control system which makes it easy to manage changes in (large amounts of) source code over (large periods of) time.

There are many such systems, with names like CVS, Subversion, Bazaar, Git, Mercurial, and more. I used CVS in the past, and switched to Subversion many years ago. It suits me well.

If you think that version control is not much more than “making frequent backups in an organized manner”, then you may be in for a surprise. Please keep reading…

All of these systems deal with the same task: managing edits. And all of them have reached a level of functionality and maturity, that frankly, I couldn’t understand how anyone writing software these days could live without…

That’s quite a statement, so let me explain.

Software development is a process. You write code, you fix bugs, you add new features over time – sometimes over a period of years, in fact. Coding is an error-prone activity, from trivial typo’s, to syntax errors, to feature omissions, to design errors… it’s all part of the process.

Suppose someone finds a bug. Wouldn’t it be great if you could go back and see what changes you made, and in what order? Maybe the bug is a new one? Maybe it got introduced by a recent change? Maybe it’s part of a very specific feature?

Here’s an extract of a special “annotated” view of the RF12.h header file. This overview was generated by Redmine, as it is now used for the JeeLabs Café:

The color-coded areas are “change sets”. The numbers indicate in which “revision” this particular code was added or last changed. The numbers are clickable, so if I click on “5976” for example, to view the last change related to the rf12_sendStart() code, I get this:

This shows exactly which files were changed at the same time, and the comment I added when I made that change, i.e. “more rf12_sendStart() low power modes”. The value is not just this little overview, but the fact that all other files and changes have been omitted. All irrelevant info is gone.

Let’s say I want to find out what was changed in the “radioBlip.pde” sketch at that time. I can click on the “(diff)” link, to get this:

Aha, this is apparently where I added some extra low-power-mode options to the RF12 driver, as I was writing the radioBlip example (red = deleted code, green = added code).

Note how only a small part of the source code is shown. I’m only interested in what changed, so all I get is a “diff” with a few lines of context. I can always go back to my full copy of the source code to see the rest.

This particular change was made 4 months ago. It took me three clicks in the web browser to find out what happened. Not “sort of”, but precisely. I don’t know about you, but to me that is an incredible way to keep track of things. I never have to guess, I can go back in time and zoom in on any specific detail I’m interested in right now.

Let me drive the point home: this isn’t a feature, it’s a necessity. There is no way I could call myself a software developer without tools like these.

All version control systems do this, it doesn’t really matter which one you use. All I can say is: if you haven’t been using any of them, pick one and put your whole (software) life in it. Today. You will have to learn some new conventions and some new habits. You will feel constrained initially. But once that wears off and the new habits kick in, you will wonder how you ever did without.

This doesn’t just apply to “official” software development, btw. Anything that takes more than say a day to work on, will benefit from revision control, IMO. Some people put their entire websites in there. Some people even put their entire home directory in there!

The nice thing about modern revision control systems, is that they are networked. With proper care and authentication, source code can live in a public “repository” accessible to more people. Websites such as http://github.com/ specialize in providing a complete environment for anyone who wishes to manage their source code in public. Completely free. All you need is the proper “client software” for the version control system you’re using, and a server (such as Github) where you get source code and send changes back.

By now, I no longer consider the source code on my hard disk to be crucially important. It’s a copy, “checked out” from my main subversion repository, which lives on an internet-facing server. I can get an up to date copy anywhere, just by checking out a new copy (as long as I remember where the server is, and my personal username/password).

The second killer feature (no less) of a version control system, is that it lets people work together on a single project, no matter where they are. Everyone gets their own locally checked-out copy of the same project, and everyone can make whatever changes they like, and “check-in” the changes whenever they please.

This happens very efficiently, because version control systems are immensely clever about dealing with text changes. They don’t send around complete projects and source files all the time, they quickly send little changes around (called “diffs”). This makes the mechanism 100% scalable. You could be working on a project with millions of lines of source code. Yet when you send in a change, the process is almost as quick as with a tiny project.

When more than one person makes a change to a source file, and sends in that change, three things can happen:

• there is no one else who changed that file, so the change is accepted as is
• someone else changed that file, but not in the same place – again, the change is automatically accepted as is, and “merged” in
• someone else changed one or more of the same lines, in which case the change is flagged as a conflict

The last case is the only one which needs a bit of attention. The changes need to be compared, and someone has to decide what the final version should look like. Usually, the intent is easy to spot, and things can be resolved without any further discussion. In rare cases, the two people involved will have to discuss and resolve the issue between them.

This sounds like a lot of hassle. But it’s in fact one of my favorite features: I can check out someone else’s source code, and use it. But I can also make changes in any way I like, without ever sending them in. IOW, I can tweak any code I have in any way I like. Never will I risk losing those changes, even if I never send them in (often, they are not of general use anyway). And I’ll always be able to go back and see what my own changes were.

So with this guaranteed checking and comparing of source code, it becomes impossibe to lose changes. My own, or anyone else’s. The version control system will flag any potential problem before it actually becomes one.

More tomorrow, as I describe how to get version control going on your own machine, and how to hook up to the source code in the JeeLabs repository.

If you can’t wait and already know how to use Subversion, all the JeeLabs code can be found here:

    svn://svn.jeelabs.org/jeelabs/trunk/

If you just want to have a quick look around using the new Redmine web interface: the JeeLabs libraries can be browsed here, while JeeMon has its own repository area, which can be browsed here.

The Graphics Board is going to enable a bunch of fun projects around here.

Unfortunately, the ST7565 library is a bit slow in one specific way – display updates. Since everything is buffered in RAM, most other operations are actually quite fast, but to get that data onto the gLCD takes time.

I had to find out how much time, of course. Here’s my test sketch:

All the loop does is send the same RAM buffer contents to the display, over and over again. The time it takes in microseconds is sent to the serial port, and the result is quite bad, actually:

• 126 milliseconds, i.e. 8 refreshes per second, max!

The good news is that it’s a clear bottleneck, so chances are that it can be found and then hopefully also avoided. Sleuthing time!

The ST7565 core primitives, responsible for getting the data out to the display were coded as follows:

Guess what: the shiftOut() in the Arduino library is written with calls to digitalWrite(). That rings a bell.

Ah, yes, good OLD digitalWrite() again, eh? Of course …

So I rewrote this code using fixed pin numbers and direct port access:

And sure enough, it’s almost exactly TEN times faster:

• 12.3 milliseconds, i.e. 80 refreshes per second.

Needless to say, I’m going to leave these changes in my copy of the ST7565 library – even though that means it’s no longer general purpose since the pin assignments are now hard-coded. A 10-fold performance increase of something which really needs to be snappy and responsive is non-negotiable for me.

Here is a copy of the ST7565 code I use.

Could this bottleneck have been avoided?

The ST7565 library was clearly written as general purpose library, so making it usable with any set of pin assignments makes a lot of sense. The price paid in this case, was a 10-fold drop in performance, plus a few extra bytes of RAM used in the ST7565 class.

I’ll revisit this topic some other time, to discuss the trade-offs and implications of compile-time vs run-time logic, as well as tricks such as: putting the pin choices in a header file, using #include for source files, pre-processing and code generation, and C++ templates.

For now, I’m just happy with the 80 Hz refresh rate :)

Update – I had to slow down the SPI clock a bit, because the display was not 100% reliable with the code shown above. The fix is in the ZIP file.

For one of the infinite number of projects here at Jee Labs, I wanted to know how fast you can toggle a pin. This has been covered before in a previous weblog post, but this time I’m going to actually measure the results.

I’m going to focus on sending out 8 pulses in a row, because my goal is to transfer one byte in or out of the system (i.e. software-based SPI).

Here’s the simplest possible way to do it:

Measured result = 124.60 KHz, i.e. ≈ 8 µs per bit.

Some of that is loop overhead, and one trick to avoid that is to “unroll” the loop:

Measured result = 129.14 KHz – no big difference?

The reason is that the Arduino library’s “digitalWrite()” is very slow. So let’s go back to the loop and use a faster mechanism:

Measured result = 1.72 MHz – whoa, 0.58 µS per bit!

Now let’s unroll that loop again:

Measured result = 3.03 MHz – yep, now the loop overhad makes a big difference…

Can we do better? Yes, we can (heh) – using the PIND trick to toggle an output:

Measured result = 2.16 MHz – that’s ≈ 0.46 µs per bit.

And now, at these speeds, loop unrolling makes an even bigger difference:

Measured result = 4.71 MHz!

That’s a bit odd though. The JeeNode is running at 16 MHz, and 4.71 MHz is not a very clear multiple or divisor of anything. How can a regular sequence of statements generate such an irregular frequency? The puzzle is solved by looking at the bigger picture with a scope:

(as you can see, my scope can’t sample 8 MHz square waves with good fidelity)

The scope measurement says it all: these are short bursts, because now the calling overhead of “loop()” is taking almost as much time as the 8 pulses.

If I unroll the loop further to contain several hundred “PIND = bit(4);” statements, the frequency readout increases to 7.82 MHz. IOW, each C statement takes one processor cycle!

Quite an amazing feat, the AVR MPUs are clearly RISC-class processors. And the gcc compiler is generating optimal code in this case.

So there you have it. A lowly JeeNode (or Arduino) can generate multi-megahertz signals on an I/O pin, just by writing a few lines of C code!

Note that these are limiting values. As soon as you start adding more logic to these loops – whether unrolled or not – the maximum attainable frequency will quickly drop. But still: not too shabby for them little chips!

Update – measurements were slightly off, because not all loops were 8 long. Fixed now, same conclusions.

I often need some way to get a bit of data and a few commands into an Arduino-type sketch from the serial port. Trivial but tedious stuff if you need to write the code for it, each time again.

Trouble is, the ATmega has very limited RAM space and string processing capabilities, so writing a super duper fancy string input parser is too wasteful of resources to be practical, in most cases.

In the RF12demo sketch, I used a very simple postfix notation, which lets you enter some bytes of data and a one-letter command. The syntax is:

<arg1>,<arg2>,... <cmd-char>

It works fairly well, but arguments are limited to single bytes and have to be entered as decimal values.

Here’s another attempt to simplify this sort of task. I’ve added an “InputParser” class to the Ports library, which takes care of basic parsing, while remaining flexible enough to allow use in different sketches. It supports input of bytes, ints, and longs in decimal or hex format, as well as short strings. It’s not JeeNode specific, and should work with any Arduino.

Here is the InpurtParser class definition (minor details omitted):

Note that many choices were made to keep the code overhead low, while allowing enough flexibility to input data in different ways. As a consquence, the syntax is a bit strict and limited:

• args are separated by spaces or commas, with the command code typed last
• plain numbers are interpreted as bytes: 123
• negative values can be entered using a trailing minus sign: 123-
• append a decimal point to enter 2-byte ints: 12345.
• append a colon to enter as 4-byte longs: 123456789:
• prefix with a dollar sign to use hex mode: $1A / $1A2B. / $123456:
• enter strings between double quotes: “this is a string”

I’ve added a “parser_demo.pde” sketch to illustrate its use:

When initialized, the parser must be given a buffer it can use to collect all argument data and input strings in. In this simple example, a 50-byte buffer is allocated dynamically.

Each command is a separate function, which pulls its variables from the parser object when called. The parser is initialized with a table of these commands, listing the command code and minimum number of expected bytes, along with the function to call.

Here are some examples of input:

h
?
v
1234. v
"Hello, there!" s
123456789: "abc" $100. "defgh" 12345. c

Here is the output, corresponding to each of the above commands:

[parser_demo]
Hello!
Known commands: h v l s c
Not enough data, need 2 bytes
value = 1234
string = <Hello, there!>
complex = 123456789 <abc> 256 <defgh> 12345

Note that you get a list of known commands when entering a bad command (or “?”).

That last example illustrates how to pass a variety of input argument types to a command. The code for this is:

This demo requires about 5 Kb, including some 850 bytes for the command functions. 600 bytes for malloc (this is optional), and 600 bytes for the Serial class. The parser itself uses some 1.7 Kb.

By default, the parser object is attached to the “Serial” stream, but it can be hooked up to something else if necessary, such as an LCD or Ethernet.

Enjoy!

Since Room Nodes are going to become more sophisticated in terms of timing, I’m adding some support code to simplify my work later on. In most cases, I think it’s not a good idea to start generalizing too early, but this is a pretty common utility: scheduling multiple activities in parallel. No rocket science, and badly needed…

So here’s a little “Scheduler” class I’m going to add to the Ports library:

Nothing fancy. My main concern is to keep RAM usage low. So the idea is that you can have a fixed number of tasks, each one with (at most) one timer running. Timers can be started and cancelled at will. The term “task” is used very loosely here: anything that needs to have an independent timer mechanism can be treated as a separate task. This is not multi-tasking or threading – just a way to manage activities which need to be performed some time into the future.

Unlike the Millitimer class, which works for durations up to 60000 milliseconds, the Scheduler class works in tenths of seconds, and supports durations from 0 to 6000 seconds, i.e. over an hour and a half. A zero duration means: run the associated task as soon as possible.

Probably best to show this in action with an example:

The way to use the scheduler, is to define an enum with all the tasks there can be, plus a “TASK_LIMIT” value, which is in fact simply the number of tasks.

Then you declare a “Scheduler” instance, and give it that TASK_LIMIT value, so it can allocate the proper amount of memory (each task needs only 2 bytes).

The only remaining thing to do is call the “poll()” member and handle each task request in a big switch statement.

The demo will blink two LEDs at different rates, the classical (and simplest) example of doing two different things at the same time. Eh… almost the same time.

I’m still putting the finishing touches on this code and making sure that this will play nicely with low-power and power-down modes, so it hasn’t been checked in yet – it should all be ready in at most a day or two. At which time this will become part of the Ports library, along with the above “schedule.pde” example sketch.

Prompted by a question on the forum, I thought it’d be a good idea to write an extra “PacketBuffer” class which makes it easy to fill a buffer with string data to send out over wireless.

This new packetBuf.pde sketch in the RF12 library shows how to set up a packet buffer, fill it with some string data, and send it to other nodes in the same net group:

If you want to use the PacketBuffer class in your own code, just copy the dozen lines or so from the above example. The code is very small, because all the heavy lifting is done by the standard Arduino “Print” class.

The code includes logic to report incoming packets, which are also assumed to always contain text strings. To try this example, you’ll need at least two nodes, of course. Here’s output from the two I tried this with:

And the other side (not at the same time):

But having made this demo, I have to add that in general it’s not such a good idea to send out everything in string form. It takes (much) more code and RAM to deal with strings, and the receiver cannot easily convert everything back to numeric values. Then again, if you just want to send out strings to report or process on the PC, then the above may come in handy.

Enjoy!

No, not your time or mine… the topic I want to go into here is how to let a micro-controller deal with things that happen over time.

The way an Arduino sketch works is as follows:

The little slashes represent real code, where “stuff happens” so to speak. You can see that there is a clear flow of control, from the start of the code to the end, with delays and calls to other bits of code.

The trouble with this is that it can’t deal with multiple events. You can’t count pulses on an input pin and keep a LED blinking at the same time, for example.

In the old days, interactive computer interfaces were written in this same way. You’d enter a couple of values and then you got some results back. If you made a mistake halfway in the sequence, you had to restart and enter everything all over again.

Then “command menus” were invented: elaborate decision trees of the form “do you want to do X, Y, or Z?” – now at least it was possible to go back just one step. Today, user interfaces are event driven, responding to whatever interaction the user initiates instead of presenting choices. The user is in control, not the computer.

The traditional event-driven logic uses a dispatch / switchboard approach:

The more modern approach is to use callbacks and closures. Fancier still is to use coroutines or continuations.

Could we use something similar for micro-controllers? Sure.

Callbacks are not that convenient in C, since it does not support the closures concept which would make it convenient (nor coroutines or continuations). Also, callbacks would have to be represented by pointers to C functions (2 bytes), whereas dispatch codes can probably be represented as a single byte (as long as we don’t have more than 256 of them). Efficiency and memory space matters on small 8-bit chips such as the ATmega.

This requires a change in mindset when writing sketches. A good way to get into such an event-oriented style is to imagine that there is no delay() function. In event-oriented code, you’re not allowed to wait for time to pass.

So how can we blink a LED if we can’t wait to switch it on and off? Well, instead of delays, we have timers. We’re still not allowed to loop until the timer expires, but we can tell this new type of timer to generate an event when its time has come.

For a low-end implementation, an event can simply be a small integer dispatch code.

So instead of waiting until we can turn the LED on or off again, we tell the system to wake us up again at the right time. This approach is also a perfect match for low-power nodes, by the way: sleep and wake-up on events can be taken literally to enter power-down mode and start up again.

The code might look something like this:

Sure, it takes some more work than this delay-based code:

… but it has the huge benefit that it’s now fairly simple to deal with other activities at the same time. What you need to do is turn each of those activities into one ore more events as well. They can then be added right next to the blink event code, as additional case(s) in the above “switch” statement.

An event-based dispatch mechanism adds a lot of flexibility. Tasks such as counting pulses, blinking LEDs, serial communication, wireless packet reception and transmission – these can all be processed as they occur. With as nice bonus that low-power sleep modes can become fully automatic: when there are no events, go to sleep!

The trick is to ban all uses of “delay()” and “delayMicroseconds()” and to never use “busy loops” to wait for something to happen. This has far-reaching implications, because all libraries must also play by these rules.

I’m going to explore this approach further. Maybe one of the existing nanokernels could be used as foundation. To qualify, it must be truly minimal (and I’m picky!) – i.e. it has to fit into an ATmega328 without claiming too much flash or RAM memory space.

Update – here’s a web page by “inthebitz” which illustrates the problems described above. It’s an absolutely genuine attempt to help people get started, and it no doubt does a very fine job at that, but it also shows how everything gets serialized time-wise. For slow things, it’ll be just fine of course.