We're hiring!

We're actively seeking developers and designers for our Detroit & Ann Arbor locations.

Getting Started with MQTT

mqttorgAs more and more things around us become networked, the communication protocols tying them together need careful rethinking. This network of devices, sometimes called the “Internet of Things” or “Machine-to-Machine” network (though it could also just be called “the Internet”), includes many embedded devices with very limited resources.

Protocols designed for typical ethernet networks, such as HTTP, are based around assumptions that no longer fit: they expect more bandwidth, processing power, and network reliability than may be available, and that networked devices will be on most of the time.

There is a more appropriate alternative, however: MQTT. It’s much lower in overhead, with only a 2-byte header for many messages. Its design suits devices that are suspended most of the time, with only occasional network activity. It also has support for reliable delivery built into the protocol, so simple sensors can just flag an outgoing message as requiring confirmed delivery and let the message broker take care of delivery reattempts. Using a standard messaging protocol for all communication also greatly reduces the surface area for possible security vulnerabilities. Read more on Getting Started with MQTT…

Posted in Embedded Systems | Tagged | 1 Comment

Lightweight Indexing for Small Strings

Lately, I have been investigating performance improvements for heatshrink, my data compression library for embedded systems. Since it may be processing sensor data in real-time, or compressing data as it transfers over a network, compression can directly impact overall throughput. After experiments with string search and indexing algorithms, I’ve settled on a particularly effective method, which I’m calling a “flattened linked-list index”.

Where’s the Time Going?

Before trying to speed it up, I measured where it was spending most of its time. Profiling revealed two hotspots:

  1. Detecting repeated patterns in recent history.
  2. Managing bit-buffering for its I/O.

Read more on Lightweight Indexing for Small Strings…

Posted in Embedded Systems | Tagged , , | 1 Comment

Comparing the Cost of Different Multiple-return Techniques in C

C’s design limits functions to directly returning at most one value. Unfortunately, there are many cases where returning more than one makes sense — returning a data buffer and its size, returning either a success code and data requested or an error code, splitting a tree node into two, etc. Making returning multiple values awkward has likely led to many security problems over the years, when people forget to track (or check) sizes associated with buffers. There still isn’t an obviously correct way to return multiple values, just a couple of methods with different trade-offs.

Three Common Techniques

The most common method involves mutation: The function returns one value, and additional values are written into pointers that were passed in by the caller. (They may or may not be NULL-checked.) While there are conventions for this, such as returning a status code and writing the result(s) into parameters, the language standard has no opinion. Passing around pointers to return values through can be a source of subtle errors, and (along with pointer arithmetic) also complicates static analysis.

Read more on Comparing the Cost of Different Multiple-return Techniques in C…

Posted in Embedded Systems | Tagged , , | 9 Comments

Making Real-Time Real Tame

real-time1

One of my current personal projects is a home automation system, based around really cheap radio hardware. Unlike devices that provide a full wireless TCP/IP stack, such as Zigbee radios, these transmitters and receivers just give me control over the raw radio signal. (I’m intentionally using such barebones devices to learn more about radio.)

There are just four pins: power, ground, “data”, and antenna. The “data” line is just a GPIO pin — I need to create the radio signal myself. (In this case, I’m using on-off keying and Manchester coding, but more on that in another post.)

Read more on Making Real-Time Real Tame…

Posted in Embedded Systems | Tagged | Leave a comment

Completing the Circuit: From Arduino to AVR Microcontrollers for Hobbyist Projects

Breadboard Atmel ATtiny13

The Arduino platform has a lot of advantages. It’s designed so that artists and hobbyists can do lots of cool stuff. There are plenty of tutorials for beginners, and the standard hardware means that incompatibilities won’t add extra confusion when learning microcontroller programming. Getting started is inexpensive — for $25ish, one can get a relatively self-contained hardware prototyping platform. Also, Arduino was carefully designed to have a smooth transition to more specific hardware in production — the hardware is open, and there isn’t any vendor lock-in.

However, there are also many benefits to reaching beyond Arduino. Much useful hardware isn’t available in a “shield“ package (and what is tends to be expensive compared to just the components), and changing the hardware allows more flexibility in price, power, and size. Also, using C and its tools allows more options than the Arduino environment alone. (And it’s fun to learn how things work at a deeper level!)

Unfortunately, once you try to move a step or two outside of the Arduino ecosystem, beginner-friendly documentation gets thinner. The information is there if you know how to find it, but many questions have to be answered at once, upfront.

I have been using “raw” AVR microcontrollers for some personal projects, and I’m going to describe are some tools and resources I’ve found useful. (There are also non-AVR microcontrollers, like PICs, but I’m going to ignore those because they have less in common with Arduinos.) Read more on Completing the Circuit: From Arduino to AVR Microcontrollers for Hobbyist Projects…

Posted in Extracurricular Activities | Comments closed

Knocking Out Bugs with greatest

Let's plug you in and fire it up

I looked into various options for unit-testing C, but wasn’t satisfied with any of them. First, I looked at Unity. While its suite of tools work quite well, they depend on Ruby/rake/YAML, require creating a full project configuration, and take on many other responsibilities. I wanted a tool for testing embedded C, not a whole build and testing framework, and having to define a whole project adds too much overhead for testing small programs.

Then, I looked at minunit, which is only a few lines of code. But while it doesn’t impose any particular workflow or toolchain, it stops after the first test failure, and doesn’t provide any way to control which tests run. I appreciate its transparency, but wanted something that provided more infrastructure.

After ruling out a couple others because they required dynamic allocation, I decided to write greatest. It doesn’t depend on anything beyond ANSI C or do any allocation, and it keeps boilerplate to a minimum. Since it starts quickly and can run only an individual suite or test, it allows rapid iteration during development. (With one Emacs keybinding, I can re-compile and re-test the code I’m working on.) It also tracks pass/fail/skip counts, suite & test runtimes, and files & line numbers for failing assertions. Read more on Knocking Out Bugs with greatest…

Posted in Embedded Systems | Tagged , | Comments closed

A Field Guide to Lua Coroutines

carl-mallory-everywhere

Lua is a deceptively simple language. Its designers have done such a good job of keeping it downwardly scalable to simple uses that it’s easy to overlook the advanced parts. One of these is its polished implementation of coroutines.

Why Coroutines Matter

The combination of coroutines, tail-call optimization, and closures means that many sophisticated control structures can be implemented in Lua pretty easily. Rather than turning functions inside-out and nesting them inside an arbitrary primary function, untangling them and giving each its own main loop often simplifies things. Allowing individual closures to suspend and resume means that backtracking, lazy streams, constraint propagation networks, and so on can be expressed cleanly. Also, asynchronous IO can be coordinated with functions like luasocket.select scheduling coroutines; each can still be read linearly, and there’s no need to CPS-transform everything by hand with callbacks.

Read more on A Field Guide to Lua Coroutines…

Posted in Development Techniques | Tagged , | Comments closed

Checking Your Derivers’ License

Sharing by Toban Black on Flickr

Sharing by Toban Black on Flickr

Recently, an OEM contacted me about a problem with heatshrink. They said that it worked well for their needs, except there was a snag with the license. Huh? I had released it under the 3-clause BSD license, not the GPL or something. Isn’t the BSD license as commercially permissive as they get? It turns out that there’s a clause in the BSD License that is problematic for anything distributed solely as hardware:

“Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.”

I am not a lawyer, but their objection makes sense to me. As an OEM, they don’t usually provide documentation or other disclaimers for end-users with their hardware — it just gets installed in other vendors’ products. (Do you know, or necessarily care, who supplied the brakes in your car? The GPS in your smartphone? The controller in your thermostat?). That clause would put an extra burden on their customers, who would have to print and distribute an extra disclaimer just to indicate that an upstream vendor was using my library. Looks like I found another leaky abstraction.

Read more on Checking Your Derivers’ License…

Posted in Evolving the Industry | Tagged | Comments closed

Adventures in Undefined Behavior

Car crash

I recently had to write my own malloc. While replacing important bits of the C standard library would normally be serious over-engineering, it turned out to be the only option.

The Backstory

We had taken over an embedded project with known stability issues, and I quickly determined that thread race conditions were involved. After fixing some low-hanging fruit by switching to mailboxes and queues for cross-thread communication, there was still strange behavior — in particular, certain actions could cause infinite loops after a few tries or during heavy network activity.

Read more on Adventures in Undefined Behavior…

Posted in Embedded Systems | Comments closed

heatshrink: An Embedded Data Compression Library

DIY TiVo IR Blaster

In embedded systems, space is always tight. Adding pennies of extra storage can be enough to kill a budget (when multiplied by hundreds of thousands or even millions of units), so available space has to be used effectively.

For my current project, I need to fit a lot of data into 16 MB of flash: a backup of the firmware, 9 MB (!) of graphical assets (including bitmapped Chinese fonts with over 30,000 characters), and other configuration data for the unit. On top of this, I need space for a second version of everything during updates. There’s no way this could fit as-is. Read more on heatshrink: An Embedded Data Compression Library…

Posted in Embedded Systems | Tagged | Comments closed