Hypomnemata

The Volksduino is our high-power Arduino clone.  The first (short) run is nearly sold out, and has been integrated into everything from a prototype laser display to a bacon-y alarm clock.  Over the next week or two, we’ll have a series of blog posts talking about these Volksduino projects, with links as needed.

First up: the laser drive circuit, as a teaser.  This is a part of a Noisebridge project that’s still a bit nascent, but it’s handy to know how to drive a higher current device from the Volksduino board.  Miloh is hooking up his Volksduino to a laser diode, adding some repurposed hard drive platters, and building a raster scanning laser display.  Note that this is a Volksduino v1.0, which was used in the Greenwire (PCB Repair) workshop.

The laser pulls more current than the Atmega328 can provide, so he added a transistor and a couple of resistors to drive it.  The transistor is a 2N2222 or 2N3904, and the resistors look to be 510 ohms between digital 8 and the base of the transistor, and 22K into the collector, with the laser diode going from the emitter to ground.

With that, he can pulse the laser, and has full PWM control of it.  Along with an optical encoder on the mirror platters, this can form a full-fledged raster scanner.  I can’t wait to see the finished result here; perhaps it’ll be done soon enough to be featured in this parade of Volksduino projects!

Coming up next time: monitoring web server utilization with a Volksduino and a surprising choice of output devices.

I recently built a new fileserver for home. It’s pretty nice, with 3.7TB of RAID5 storage. I’ll never have to worry about losing data again (mostly).

Unfortunately, in the process of transferring data, I found that, well, I had already lost data.  My old backup drive (an external, FAT32 disk)  contained a directory that pointed off into gobbledygook, containing garbage as “files” and “directories.”  I noticed this when my rsync went off the deep end.  This “broken copy problem” is a simple problem to fix: rsync has a –exclude option.  To get the copy to finish, I just –exclude the broken directory and recopy.  Thankfully, the directory was junk (eclipse metadata), so I could ignore it, and all was well.

But.  Once I finish the copy, I’d like to continue using this drive for moving data around, etc.  With this corrupt directory, though, I can’t quite trust it.  When you realize what causes this corrupt, it becomes clear that no off-the-shelf tools will repair this without potentially mangling other data.  So, there’s no way to fix it short of formatting it.  But, understanding the corruption pretty intimately, I saw that it might be possible to fix this, if I hand-edit the disk.

So I did.  Knowing what the underlying problem was, I wrote some tools to inspect the filesystem manually, then went in and excised this directory.  Once that was done, the FS came up “clean enough,” and worked.  It might be fun to go through the process of building these tools, so here’s a quick overview.

First off, let’s identify the problem more precisely.  The big symptom is that ‘find’ returns tons of the following:

./density_home/jbm/workspace/.metadata/.plugins/org.eclipse.core.resources/.history/8f/ ?<A2>md`<B5>?.?<EE>?

./density_home/jbm/workspace/.metadata/.plugins/org.eclipse.core.resources/.history/8f/<F4><B0>q<EA>^\@??.?s<FC>

./density_home/jbm/workspace/.metadata/.plugins/org.eclipse.core.resources/.history/8f/<E6>q^]^\^K^G^N%.<E6>?0

./density_home/jbm/workspace/.metadata/.plugins/org.eclipse.core.resources/.history/8f/??^]v<B2>?<ED>?.?b^\

./density_home/jbm/workspace/.metadata/.plugins/org.eclipse.core.resources/.history/8f/?<E2>^^8<A5>^?<F4>?.u<F2>`

./density_home/jbm/workspace/.metadata/.plugins/org.eclipse.core.resources/.history/8f/<E8>???^X<DF>?<EE>.<F6>8^T

./density_home/jbm/workspace/.metadata/.plugins/org.eclipse.core.resources/.history/8f/ ?<A2>md`<B5>?.?<EE>?./density_home/jbm/workspace/.metadata/.plugins/org.eclipse.core.resources/.history/8f/<F4><B0>q<EA>^\@??.?s<FC>./density_home/jbm/workspace/.metadata/.plugins/org.eclipse.core.resources/.history/8f/<E6>q^]^\^K^G^N%.<E6>?0./density_home/jbm/workspace/.metadata/.plugins/org.eclipse.core.resources/.history/8f/??^]v<B2>?<ED>?.?b^\./density_home/jbm/workspace/.metadata/.plugins/org.eclipse.core.resources/.history/8f/?<E2>^^8<A5>^?<F4>?.u<F2>`./density_home/jbm/workspace/.metadata/.plugins/org.eclipse.core.resources/.history/8f/<E8>???^X<DF>?<EE>.<F6>8^T

It’s clearly “corrupt,” but what does that mean?  First, we’ll need to learn a little bit about how FAT works.  To do that, you can read any of a myriad of difficult-to-follow documents, all of which talk a lot about things that are only relevant on floppy disks (no, really).  Examples: Microsoft’s Description of the FAT File System (which is incomplete: it doesn’t cover FAT32), Wikipedia’s File Allocation Table (good, but tl;dr), Andries Brouwer’s The FAT filesystem (great, a little incomplete), and Paul Stoffregen’s Understanding FAT32 Filesystems (aha, finally helpful!  But lots of disk-ish stuff, and a few missing bits).

Once you’ve digested all of those, you’ve got a good idea of how FAT works.  Or you can sit down and listen to Josh talk story.

First and foremost: FAT was designed for floppies.  There’s lots of cruft in there, and a bit of weirdness, from that heritage.  A lot of things we think of as constants are variables in the land of 3.5″ vs 5.25″, DS vs SS, DD or not… all that great floppy crap.  Just be prepared for this.

So, without further ado, the structure of a FAT filesystem.  I’m going to assume you’re working with a partition on a hard disk, or a ‘dd’ copy of one.  The first chunk of the disk is the Boot Sector.  This is where the CPU boots from, so it’s got some actual code in it.  This is important for floppies.  We don’t care.  What we do care about are the following fields stored in the Boot Sector:

• bytes per sector (0x0b-0x0c)
• sectors per cluster (0x0d)
• number of FAT copies (0×10)
• number of sectors per FAT (0×24-0×27)
• first cluster of FS (0x3C~0x3F)
• FS type (0×52-0×59)

If you’re playing the home game, begin by checking the FS Type.  It should be “FAT32 “.  If it’s not, you’re in trouble, because I’m only explaining FAT32.

This is just the header structure, which lets us determine the geometry of the drive, and calculate where data goes.  After this, there’s the eponymous File Allocation Table, then a second copy of the FAT, and then we get to the actual data.  Let’s talk a little about how the data is organized, then come back to the FAT.

The actual directories and files in FAT32 are stored in “clusters.” A cluster is a contiguous block of sectors; a sector is a contiguous block of bytes (corresponding to a floppy disk sector, once upon a time).  All of these things are variables, though it’s really typical that sectors are 512 bytes, and clusters are 32Kbytes.  You should read in the appropriate variables above, and compute them for your disk, though.  The cluster is the base unit of allocation of your filesystem.  When you store a file, its content gets put into a set of clusters.  If the file is under 32K long, it goes into a single cluster; if it’s more than 32K, it goes into multiple clusters.  Similarly, directories are stored in clusters.  Most directories fit within one cluster, but sometimes they, too, span multiple clusters.

The content of files are stored “raw”: a file cluster is just a 32K chunk of that file.  All the metadata about the file is stored in a directory cluster.  Directory clusters, on the other hand, are nothing but metadata.  They’re a list of entries with names, types (directory or file), and cluster numbers.  So, you start out at the root cluster (“first cluster of FS”), and read it as a directory.  Walking through this, you find the name of all files and directories in the root of the FS, and pointers to the clusters containing those files and directories.  From there, you can go to those clusters and read their contents.

But what if a file (or directory) spans more than one cluster?  Normally, you’d assume the OS would allocate a contiguous range of clusters to any file, and just write the file there.  However, let’s assume you’re the OS, and you’re working on a disk that’s been in use for a while.  What if the user wants to write a file that’s bigger than any contiguous range of clusters, but fits into the free space fo the disk?  You could shuffle things around to make that work, but, haven’t I heard this before?  Oh, yeah, the bin packing problem.  It’s hard.  So, instead, we fragment the file into multiple clusters, and spread them to the four corners of the disk.  This lets us use all the free space on the disk, without having to solve NP problems every time the user writes a new WordPerfect document. (Yay floppies!)

So, now we need a way to keep track of all these clusters.  Putting them into the directory entry itself is tricky: we’d really prefer it if our directory tables were made of constant-length entries.  We could use some space at the end of each cluster to point at its next entry, but there must be some good reason not to do it that way, which probably involves floppies (it smells like a DMA/alignment thing to me, but I dunno.  If you do, please comment).  Why must there be a good reason not to do it that way?  Because MS chose to solve it in a way that makes absolutely no sense otherwise.

They created the File Allocation Table.  If you looked at the Boot Sector of your disk, you might’ve noticed that the “number of sectors per FAT” is a kinda big number.  On my 320GB drive, it comes out to 37MB.  If all the file contents are in clusters, and the directories and filesystem metadata are in other clusters, what the heck is in the FAT?

Naturally, it’s the linked list of what cluster comes after the current one.  Every cluster on the disk gets a 32 bit number entry in the FAT (hence FAT32), which is the index of the next cluster after it in the current file. These are coindexed, so cluster 2 gets the 2′th FAT entry: whatever number is in there is the next cluster in this entry.  There’s a few special values: anything over 0x0ffffff7 is an “END” marker.  So, let’s assume we have a directory that points to “NIBBLE.BAS” of length 35K at cluster 13, and that FAT[13] = 37, and FAT[37] = 0x0ffffff.  Then NIBBLE.BAS is made up of all 32K of cluster 13, and then the first 3K of cluster 37.  The remainder of 37 gets wasted, which is a real shame on a 720K floppy.

So, to recap: file metadata is stored in directory tables, which are stuck in clusters.  File contents are also stuck in clusters.  If any one entity spans more than one cluster, you start at the first cluster in its chain, then go to the FAT entry for that cluster to find out the next one.  If the next one is greater than 0x0fffff7, you’ve hit the end of the chain.

How is that metadata stored?  Well, it’s not too bad until we get to long file names.  It’s just a packed struct, of a fixed length.  Every directory table entry is 0×20 bytes long.  The fields you care about:

• FilenameExt: (0×00-0x0b): 8.3, minus the dot
• Attributes: directory/readonly/system/etc.  (0x0f is a wacky VFAT entry, if 0×20 is set, it’s a directory, see Andries for a complete bitmask)
• Cluster high: 0×14-0×15
• Cluster low: 0x1a-0x1b
• Filesize: 0x1c-0x1f

Notice that the cluster is split up?  The “high” part is in a previously reserved part of the directory entry structure.  They used to only have the low part.  Floppies.

So, you read in those bits, multiple high by 256 and add it to low, and bob’s your uncle.  The filenames are probably awful (BOBSY~12TXT), but, for the purposes of “Find the place to excise a tumor from my FS,” I can deal with ugly path components.

At this point, we can see what went wrong above: the directory entry for …/8f/ got mangled somehow, and its clusterhi+clusterlo now points off into the middle of file.  The contents of that file are being dutifully interpreted as a directory.  Better still, the file goes on for a reasonable number of clusters, and, best of all: since those clusters contain random stuff, some of it is being interpreted as pointers to subdirectories, which point off to random clusters.  Which are probably other files, and so on, and so forth.

This explains the behavior I was seeing quite nicely.  So, what do I do to fix it?  If I tried to delete it recursively (rm -rf and/or deltree), it could be Very Bad: it’s going to go through and crap all over the clusters randomly pointed to, breaking the chains they’re in, and potentially mangling the whole FS.  That would be pretty tragic.

Knowing what we know above, though, there’s a pretty obvious entry: let’s just remove the bogus directory entry by hand!  Since the contents of 8f are a lost cause anyway, I could just go in and nuke its directory entries.  But, honestly, I kinda hate eclipse.  I only care about that workspace directory for the code in it; the eclipse metadata can go to hell for all I care.  So, I’m going to cut the tree of there.  Now I just need to find the 32 bytes on the disk to overwrite to make this happen.

To do that, we need to find the cluster on disk.  We know the first cluster comes right after the FAT, so that’s easy: len(boot sector) + len(FAT) + N * sizeof(cluster), right?  No, that would make sense, and this is FAT32.  Remember the variable “first cluster of FS” in the boot sector?  Didn’t it seem like that should be zero?  Yeah, it’s two.  It’s always two.  Not sure why, it just is, but, remember, it’s stored in a variable.  So, that’s the cluster you go to read the root filesystem, but it’s actually the first cluster immediately after the FATs.  Yes, FATs, because there’s probably two of them.  So, in the end, you wind up with:

offset_of_cluster(N) = 512 + 2*sectors_per_fat*bytes_per_sector + (N – first_cluster) * (sectors_per_cluster * bytes_per_sector)

Ain’t FAT grand?  This is the most widely-deployed FS in the world, folks.

With all that in hand, we can finally write code to walk down these things and find out where they live on disk.  Once you’ve done that, you can find the offending entry in the directory table and pluck it out by writing zeros over it.  Well, assuming it’s after anything else you might want in that directory.  If the zeroth byte of a filename is 0×00, it’s assumed to be the end of the directory listing.  Supposedly.  So, if you want to access stuff beyond the excised directory, you might be in trouble.  Good luck with that.  Happily (and oddly), Linux’s implementation of vfat skips over zeroed out entries, probably assuming that they’re problematic in this kind of a way.  Actually, it only does that when I mount the disk I modified; the disk image treats this as a directory terminator.  There’s an awkward question I don’t want to ask there, so I won’t.

Also note that the FAT is probably wonky at this point.  We pruned the directory entry, but it might still have clusters allocated to it.  Since we didn’t (and can’t) clean those up, there are probably a bunch of clusters marked as used which aren’t actually connected to the current FS tree.  There’s not any good way to identify these, short of walking the whole FS and keeping track of which clusters are part of something.  At that point, we’ve written our own baby fsck (the stock fsck.vfat totally fails on drives this size for me, and I’m definitely not hooking this thing up to a windows machine at this point).

After all was said and done, I got my drive back.  It’s probably got a bunch of wasted clusters, but, you know what?  I don’t care.  There’s a lot of stuff in this process that, when it comes down to it, I don’t care.  All that matters is that, at the end of the day, I got my drive back.

Actually, since we don’t currently have a public blog or wiki, I thought it’d be nice to collect a bunch of Project Bacchus stuff in one place.

We started Project Bacchus in late October, 2009.  My friend Shannon approached me with a question: “What do you think about sending a camera to the edge of space?”  My answer was quick: “That’s why I got my ham radio license!”  We pulled in a few more people, and a plan emerged through weekly meetings, at which we always have beer. Always.

Our project was kept quiet for a while, in part to give ourselves room to fail (which we did), and in part to keep it coherent. The more people you have, the more ideas/goals you have, the less you can focus. By keeping it to just five guys, we stayed on track, though we did probably bite off too much for our first few launches.

The biggest challenge has actually been scheduling flights, with weather a close second. Everyone wanted to have the whole team present at our first big launch, which we did. Getting there was a challenge, especially in December: between the holidays and the rain, we didn’t have a single launch window. We’ve since moved to a much nimbler group, able and willing to fly with only three guys in the field. That’s worked out really well for us, as you’ll see.

Without further ado, a quick recap of most of Project Bacchus up to the present:

Bacchus I: 2009, November 21; abject failure.

My apartment, the night before Bacchus I

Adam has a flickr set of our attempt here, 20091121 Project Bacchus I.  Note that all these pictures were taken on November 21.  The ones in my apartment were just after midnight, the rest were at about 7am, an hour and a half drive from San Francisco.  This is on top of an all-nighter on Thursday by Michael and myself, which resulted in a nice, solid payload, but slightly frazzled nerves.

Bacchus I's Flight Computer: Spaghetti (Ted Scharff)

That’s a great shot of the flight computer’s (totally spaghetti) guts by Ted; he’s got more electronics porn in his Bacchus I Gallery.  There’s other documentary evidence of this trip, but it’s mostly depressing, so I’ll pretend it doesn’t exist.  On the positive side, I got an inadvertently free margarita at brunch after our failure.

Bacchus I, which never left the ground (Ted Scharff)

In summary, we learned a lot from our first failure.

Bacchus II: 2010, January 10; payload lost at launch. RECOVERED! 2010, May 29

The balloon, tethered between our cars (Adam Fritzler)

Adam’s the most photo-happy member of the group (but Michael and Ted are both pretty photo-happy themselves), so I’ll link to his set first again: 20100111 Bacchus II Launch.  This launch was in a valley that’s socked in with fog, underneath otherwise crystal-clear skies.  Launching through the fog was technically against FAA regulations, but there was no behavioral difference between us launching in clear skys and through the fog: pilots couldn’t have seen our balloon until the same altitude either way.

(L to R) Ted, myself, Michael, and Shannon (hidden) rig Bacchus II (Adam)

But maybe the FAA regs aren’t there for the pilots, because we immediately lost visual contact with the payload, and the ham radio rig only got three check-ins (up to 9,000′!) before it went silent.  We had a backup cell phone in the payload as well, but it never checked in.  The assumption is a catastrophic failure shortly after launch, but we’ll never know.  For now, the official story is pterodactyls.

Update, 2010, May 31 Bacchus II was found! A rancher moving cattle down to summer grazing land came across Bacchus II dangling from a tree. It was in a remote valley with no cell phone coverage, but the phone seemed to be in okay shape. The current theory is that the radio failed shortly after launch. We’ll know more in the next week or two–the call came in two days before Bacchus VI, which was retrieved from the top of a peak in the foothills (technically a mountain), which was yesterday. Needless to say, we’re a little overwhelmed between the post-processing of mission data from VI, post-processing of the data from II, and making time to post-mortem the failure of II’s hardware. Regardless, welcome home, prodigal probe!

Bacchus II: It's About Quality™ (Ted Scharff)

Again, we learned a lot from our failure here. For instance, our new fill method is nice and elegant; the fill method used in Bacchus II… less than elegant. There’s a lot of good photos in Ted’s Bacchus II Picasa Gallery.

Bacchus III: 2010, February 14; payload retrieved.

A camera, dangling from a balloon, took this.

After throwing away several hundreds of dollars of electronics on Bacchus II, we went back to basics for Bacchus III.  One tortilla warmer, one cell phone, and one camera.  We didn’t put on a chute, since we had a very light payload and a giant streamer, which worked out really well.  A couple hours after launch, we came upon Bacchus III lying, undignified, in a fallow field, nary a scratch on it.  The telemetry from the phone’s GPS shows it coming down at about 40mph, which is a little zippy, but not dangerous with as much foam as we had.

Bacchus III Away Team: Shannon, Adam, myself, Michael (Michael Toren)

As part of our “lean and nimble” goal for this launch, we went with just four of the five team members.  Ted had other plans that weekend, so we ran off without him.  We did have his hiking GPS, though, which, once we figured out the UI, was invaluable.

Bacchus III, on the ground (Michael Toren)

We retrieved the payload and got a bunch of photos off of it.  Adam went through and edited them down to the best ones: 20100214 Bacchus III (payload camera).  We thank him greatly for that, as it’s kind of a huge pain, and he’s really good at it.

Based on the data we collected here, we’ve been able to understand the dynamics of the system, predict future behavior, and better plan future flights.  We’re working towards a payload for Bacchus IV in a couple weeks, which is part of why I was reviewing battery holders in the last post.

Bacchus Kite Tests: 2010, February 20; way fun.

Myself, Ted, and Michael rig a "test" payload (Adam Fritzler)

To test some of our descent gear, we decided to use a kite as a flying platform.  We had a few things to test this way, but only really got to one of them this time.  Mostly, this was a good excuse to go out into the park and drop stuff from kites.  It’s really, really fun, try it sometime.  Also, it gave me an excuse to buy a 200′ measuring tape, which is probably one of the more specialized pieces of equipment I own.

Mission accomplished! (Ted Scharff)

After we finished our actual goals (breaking the hell out of some styrofoam), we went ahead and did something silly: dropped the camera, recording video, from 100′ with a Wal-Mart bag as a parachute.  It’s really, incredibly disorienting, but damned fun. Video as soon as wordpress stops being stupid about it.

And that’s it. You’re now caught up on Project Bacchus!

A lot of my free time has gone into Project Bacchus lately.  Some friends and I decided to try and get a picture of the edge of space in late November, and we’ve been working at it ever since.  A few weeks ago, we had our first successful flight, Bacchus III.

Bacchus III's view of the horizon near apogee (Courtesy Adam Fritzler)

We’re now getting a little more ambitious, and working on engineering things a little better.  We captured a bunch of pictures, but our camera stopped right after this one:

A nice shot of Bacchus III's impact point (Courtesy Adam Fritzler)

This is the field Bacchus III landed in.  Taken on the way down, literally seconds before impact: talk about good timing!  It landed surprisingly gently, and all the equipment survived intact.  In fact, our styrofoam cooler doesn’t even have a dent from the impact.  It was, quite frankly, a perfect landing.  Despite this, the camera suddenly stopped after the above photo.  Our conclusion is that the batteries came “loose”: the springs that hold the AAs in place inside the camera were compressed by touchdown.  This disconnected power for an instant, resetting the camera.

So, we’re now very interested in battery holders.  So interested, in fact, that I spent an hour the other evening playing “Consumer Reports for Near-Space Hackers.”  Andy (of the eSATA help) purchased some candidate holders from Jameco, our neighborhood electronics warehouse.

Here’s my notes, if you’re in the market for battery holders.

Jameco 216152: 4-AA, 1×4, no case, $1.15/unit

This is a boring 4-AA holder, like you had in the bottom of R/C cars as a kid, yadda yadda. Except that it doesn’t have a door, like your cars always did.

The springs feel good, pretty firm. A longitudinal landing will probably cause disconnect, similar to that seen in the camera on Bacchus III.

There is no case, so it’s really easy for me to imagine bouncing the batteries out unless they’re retained somehow. Given that it costs us $2.50 for two of them, and we’re already spending $20 on the batteries, we could consider these consumables and just replace them every flight. The real challenge there is that we’re resoldering the most important solder junction in the system every flight, which is going to be bad for the PCB eventually.

Another alternative is to construct a little sleeve to go around the batteries, which could be as simple as cardstock (read: cereal box) and fiberglass tape (read: duct tape).

Jameco 216216: 6-AA, 2×3, no case, $0.75/unit

This a little 2 by 3 battery pack.  In layout, it’s the same as the 216152, except that it’s only got three batteries in a row, and there are two of them back-to-back. It feels reasonably constructed, same as the last, but still not the totally solid feeling I’d like. The springs are less solid than the 216152, by a noticeable amount.

Most significantly, the middle battery in each row has the exact same “could get jostled out” problem as the middle two batteries had in the 216152.

We could resort to the same “consider it consumable” strategy here. This is cheaper than the previous solution, and I’m much more okay with burning $0.75 per battery load if it means we don’t have to worry about our power supply.

A sleeve is also an option here.

Jameco 2095453: 4-AA, 1×4, case, $0.99.unit

You know the battery cases Mitch uses for his kits? This is one of those, without the switch. It has the little hole for the switch, just no switch.

It’s 1×4, with a case around it. It snaps closed, and then is retained by a screw. It generally feels really solid, which is nice.

The one big concern I have here is the quality of the springs. They’re significantly weaker than the ones in the 216-series cases.

Conclusion:

I’d go for the 2095453 vs the 216152. They’re both 4-AA, which is not ideal for our current payload, but they both feel really solid in their own ways. With a bit of testing, I’d feel confident that the 2065453 can handle the impact of landing, and then I’d be totally sold. Barring that, I’d prefer to make a dapper little sleeve for the 216152 and work with that a bit.

Short version: the Roku Channel SDK License includes language that prohibits GPL-bearing applications.  Given that their device runs a GPL’d OS with a bunch of other OSS infrastructure, this is disappointing, and F/OSS authors should be careful in accepting the Roku SDK’s terms of service.

If you read my old blog, you may remember that I found a way to  Download the Roku Firmware a while ago. It was clear that one could load custom firmware via a man-in-the-middle technique. In my case, I wanted to place my ripped movies into the Netflix Play-it-Now queue. It was technically feasible, but sort of a pain (it required reversing the Netflix protocol, which required adding custom CA certs to the image, and and and…), so I dropped it.

Fast forward to now-ish, with the introduction of the Channel Store on Roku.  I just noticed Roku’s Channel Developer SDK in an email announcement they sent out.  Exciting!  With a little elbow grease, I could watch my ripped DVDs, use YouTube on my TV (Google TechTalks and MIT OpenCourseWare!), or maybe even have a nice weather channel.  I was so stoked, I got out of bed an hour earlier than usual to look into it.  No, really.

Part of my excitement was knowing it would be familiar.  Having seen their firmware, I know the Roku is a Linux box, running X windows, and using QT for its UI.  All of this is Open Source Software, and I’ve used it all before: this is great!  I can bring my former experience to bear, and a lot of the Open Source stuff I’ve been using in the past should integrate pretty flawlessly.

I went and started signing up for the process.  Before downloading the SDK, though, you have to agree to The Roku Channel Developer Agreement. Instead of blindly clicking, I decided to read it.

5.A.iii:   Subject to the Grace Period, Your Channel Application must at all times: … not contain any open source code or other restricted code that could require Roku to publicly post or display any third party notices or any modifications to such code.

Recently @edrabbit had a great idea: “I want to install a cache of balloons and confetti over my desk for when I achieve inbox zero.”

It was brilliant, so I kludged together the first step: a ruby script that takes an action when you hit inbox zero.  Here’s the code, if you want to play along at home.  You’ll need to edit your username and password; if you’re on Linux, “gnome-open” is probably the right thing to have there.  On OS X, you’ll want “open.”  If you’re on Windows, you have your own little set of special problems.

(Note that this program exits 0 when you’ve got inbox zero, and 1 otherwise, so you can easily put it into a shell script.  In addition to the exec() command in the script, this could be used to trigger a program that pings an arduino to unlatch a box of balloons and confetti.  For my sake, I’ll be thrilled to have “Peanut Butter Jelly Time” pop up when I hit inbox zero.)

#!/usr/bin/env ruby
# You need to add your username and password below!
require 'net/imap'

config = {
  'server' => "imap.gmail.com",
  'port' => 993,
  'username' => "josh.myer@gmail.com",
  'password' => "",
  'action' => "gnome-open http://bit.ly/pbj_time",
}

imap = Net::IMAP.new(config['server'], config['port'], true)
imap.login(config['username'], config['password'])
imap.select('INBOX')
n = 0
imap.search(["NOT", "DELETED"]).each do |message_id|
  n += 1
end

imap.logout()
imap.disconnect()

puts "Your inbox contains #{n} not-deleted messages."

if n == 0
  puts "SUCCESS!  INBOX ZERO ACHIEVED!"
  exec(config['action'])
  exit 0 # superfluous, I know
else
  exit 1
end

I’ve recently been working my way through Write Yourself a Scheme in 48 Hours. This is a guided tutorial through implementing a Scheme interpreter in Haskell. It’s been really fun, and a nice change from my current contract (which involves a lot of screwdriver turning and other sysadmin duties).

That said, there is one big change that I’d like to see made in the text: build it with unit tests! I’m not a total test-driven disciple, but I do believe they’re a fantastic tool, and this is a great place to use them.

Parsing is incredibly test-friendly: you have an input string, and an expected output parse tree. It’s totally deterministic, with no random numbers, no ambiguities, and no pesky humans. There are a lot of interacting components, especially in terms of nesting, which are hard to keep in mind when manually “testing” things.

In addition, the “here’s code, extend it to do X” pattern used in the text benefits from having comprehensive tests. In working the homework exercises, you’re going to refactor big chunks of code. As you do so, you should be worried about breaking the hell out of your existing code (if you’re not worried, you’re either brilliant, inexperienced, or inattentive). There’s no better way to assuage those worries than unit tests, and, as you find broken things, adding regression tests. It gets even better if you add code coverage, guaranteeing that you’re exercising all codepaths via your tests.

Another wrinkle that makes you want tests: as you work through the book, you merge your existing code into the next snippet of example code. This is often an error-prone process, and having tests to catch mistakes is great. This is the reason I broke down and refactored the code for testing. I started getting into the interesting stuff at the end of chapter two, and suddenly my strings weren’t parsing properly. Upon examination, I found I’d merged my code into the next sample code incorrectly, and left my parseString implementation behind.

So, with all that in mind, let’s make Write Yourself a Scheme more test-friendly. The first step is to factor the parser implementation out into its own module. This is really easy: we create WYAS.hs, containing everything but main, and change the module line to:

module WYAS where

We’ll also need to extend LispVal a little bit, too. We want to be able to compare them, so we’ll add deriving(Show, Eq) immediately after the definition:

data LispVal = Atom String
             | List [LispVal]
             | DottedList [LispVal] LispVal
             | Number Integer
             | Float Float
             | String String
             | Char Char
             | Bool Bool
             deriving (Show, Eq)

Don’t worry about what “deriving()” means here; it’s just some Haskell typeclass voodoo that lets us now show (Char 'x') and have it do something useful, as well as allowing us to compare two LispVals for equality. After adding deriving(Show), you can also make readExpr‘s Right case return the actual parse tree as a string:

    Right val -> "Found value: " ++ show val

Handy, no?

Then, we add main.hs, containing:

module Main where
import WYAS
import System.Environment

main :: IO ()
main = do args <- getArgs
    putStrLn (readExpr (args !! 0))

Next, let’s compile this, and make sure we get something that acts like our old parser:

ghc --make -o main main.hs
./main 42
./main "#t"

Once we’re convinced that’s all working, save it and commit it to your version control. (You are using version control, right? svn, git, cvs, hg… they’re all great, and totally worth using here!)

Now, we add a test framework. First and foremost: make sure you have HUnit installed (on ubuntu and debian, it should be ‘apt-get install libghc6-hunit-dev libghc6-hunit-doc‘).

Then, we’ll get to using HUnit to write unit tests. I don’t really want to explain HUnit in too much detail, in part because I still don’t fully grok it. Suffice it to say, the following works, and gets good results. If you have better options, please leave them in the comments, as this is one of those things that could always use refinement.

For my purposes, I’m only really interested in running tests on each parse type. That is: I want to put together a bunch of strings representing possible Number inputs, along with their parses, and run them one after the other. I’d like to have a string to tell me the name of the grouping, but, beyond that, I’m not too picky on how much debug output I get. When an input string fails (and it will), I can use the ./main binary to examine the output parse. So, I’m going to write a small templating facility in my test setup. I’ll define a ParseTestSuite, which is a String identifying the group with a list of (String, LispVal) pairs. The String is the input, and the LispVal is the expected parse. Once I have that, add some code around it to turn them into HUnit’s internal Test representation. At the very end, we collect all these Tests, and run them. Here’s the resultant test.hs:

module Main where
import WYAS
import Test.HUnit
import Text.ParserCombinators.Parsec hiding (spaces)

-- A ParseTestSuite is a name, then a list of strings, and their expected parses
-- For instance:
--   ParseTestSuite "testNumbers" [("32", Number 32), ("3.4", Float 3.4), ..]
--
data ParseTestSuite = ParseTestSuite String [(String, LispVal)] deriving (Show)

doParse :: String -> LispVal

doParse input = case parse parseExpr "lisp" input of
    Left err -> Atom ("No Match " ++ show err)
    Right val -> val

-- Convert a ParseTestSuite into an HUnit test suite.
-- This requires extracting the boolean assert, then turning
-- it into a test case.
suiteEntryToAssert :: String -> LispVal -> Assertion
suiteEntryToAssert s p =
assertBool s (p == doParse s)

parseTestSuiteToTest :: ParseTestSuite -> Test
parseTestSuiteToTest (ParseTestSuite name tests) =
    TestLabel name bodies_t where
    bodies_t = TestList $ map (\(s,p) -> TestLabel s (TestCase (suiteEntryToAssert s p))) tests

tests_Number :: ParseTestSuite
tests_Number = ParseTestSuite "tests_Number"
    [
    ("32", Number 32),
    ("3.2", Float 3.2),
    ("0", Number 0),
    ("#d1", Number 1),
    ("#b10", Number 2),
    ("#x10", Number 16),
    ("#o10", Number      ]

tests_Bool :: ParseTestSuite
tests_Bool = ParseTestSuite "tests_Bool"
    [
    ("#t", Bool True),
    ("#f", Bool False)
    ]

-- lots of other tests elided

all_tests :: [ParseTestSuite]
all_tests = [tests_Number, tests_Bool, tests_Atom, tests_String, tests_Char, tests_List, tests_DottedList, tests_Quoted]

main :: IO ()
main = do
    runTestTT $ TestList (map parseTestSuiteToTest all_tests)
    return ()

Then, we compile this:

ghc --make -o test test.hs
./test

and its output:

0] jbm@density:~/src/wyas/ch2 $ ./test
Cases: 22  Tried: 22  Errors: 0  Failures: 0
0] jbm@density:~/src/wyas/ch2 $

From here, it’s just a matter of adding more of these ParseTestSuite entries and inserting it into all_tests. As we do this, we gain more confidence in the parser we’re building in this process.

There’s one more key consideration in confidence, though: code coverage. Unit tests are great, but they might not test all your code, leaving bugs lurking for some poor soul to find later. The best way to ensure this is to run your unit tests under a coverage tool. GHC comes with one of these, handily enough: hpc.

As with all coverage tools, we need to recompile the program with some new options. And, like many of them, we need to clean up the project a bit first. So, in the name of being lazy, I wrote a Makefile:

# NB: you're going to get this mangled.
# The things under the target names MUST be tabs, not spaces.
# The joys of ancient Unix programs.
#
all: test main

coverage: clean WYAS.hs test.hs
        ghc --make -fhpc -o test test.hs
        ./test
        hpc markup --include=WYAS ./test

test: WYAS.hs test.hs
        ghc --make -o test test.hs
        ./test

main: WYAS.hs main.hs
        ghc --make -o main main.hs

clean:
        rm -f *.tix *.hi *.o main test

distclean: clean
        rm -f *.html

This lets us run ‘make coverage‘ and get an HTML file showing the coverage of WYAS.hs:

0] jbm@density:~/src/wyas/ch2 $ make coverage
rm -f *.tix *.hi *.o main test
ghc --make -fhpc -o test test.hs
[1 of 2] Compiling WYAS             ( WYAS.hs, WYAS.o )
[2 of 2] Compiling Main             ( test.hs, test.o )
Linking test ...
./test
Cases: 22  Tried: 22  Errors: 0  Failures: 0
hpc markup --include=WYAS ./test
Writing: WYAS.hs.html
Writing: hpc_index.html
Writing: hpc_index_fun.html
Writing: hpc_index_alt.html
Writing: hpc_index_exp.html

To get a quick view of how we’re doing, we can use ‘hpc report‘:

0] jbm@density:~/src/wyas/ch2 $ hpc report test.tix
91% expressions used (416/457)
100% boolean coverage (1/1)
100% guards (0/0)
100% 'if' conditions (1/1)
100% qualifiers (0/0)
62% alternatives used (22/35)
100% local declarations used (6/6)
96% top-level declarations used (32/33)
0] jbm@density:~/src/wyas/ch2 $ hpc report test.tix  WYAS
91% expressions used (233/256)
100% boolean coverage (1/1)
100% guards (0/0)
100% 'if' conditions (1/1)
100% qualifiers (0/0)
63% alternatives used (21/33)
100% local declarations used (5/5)
95% top-level declarations used (19/20)
0] jbm@density:~/src/wyas/ch2 $

As you can see, my “alternatives used” is rather low. Looking at the highlighted output, I need to finish up the tests around my R5RS character decoding implementation. Time to go in and add more cases to my unit tests!

I hope this post helps explain the benefits of testing for this project, and helps you convert your copy of Write Yourself a Scheme into something more test-driven. If it saves you time, or you have any other ways to help the rest of us save some time, leave a comment. WYAS is a great resource, and I’d love to collect all the time-savings we can and fold them into the original text.

Here’s a quick hack I keep meaning to release in a meaningful way: a morse code decoder in arduino.  Hook up a button to pin 2 (like you would for the button examples), and then watch the serial monitor.  If you key in SOS (…/—/…), it will light up the LED on pin 13.  My intention here was to use this to buzzy myself into my apartment building’s door, but I still haven’t gotten around to actually putting it inside the box yet(!).

Give it a go, and see what you think of it.  I’d also like to hook it up to an LCD panel and make a proper morse training device out of it, but that’s for another day, I think.

Leave comments here if you make any use of this, I’m keen on seeing what happens with it!

73 de KJ6ANM

Here’s the file: arduino_morse_decoder.pde(.txt to make things happier).

When doing creative things, there are challenges at three basic stages: intimidation in starting, getting stuck in ruts while implementing, and chasing my tail while wrapping up.  In this post, I want to share three “techniques” to help get over the intimidation up front, get out of ruts as you’re building, and keep from chasing your tail as you wrap up.

First, a few examples of each problem.  When designing a system, I get intimidated by the openness of the blank page, and don’t want to write down anything until I’m confident that it’s Right (free fourth tip: this is why I always start out in tiny notebooks or on notecards).  It’s also nice to use whiteboards; something about the ephemerality of them is really helpful.  That said, there’s still a lot of ground to cover in getting over that initial hurdle, and Merlin Mann has some great quotes and reassurance to share.

Next up is getting stuck in a rut.  For instance, when designing an architecture, I sometimes can’t decide which component should own a particular piece of functionality.  If I’m not careful, I wind up getting stuck in little mental loops, recapitulating my own ideas over and over.  Once I recognize this, I break out a deck of cards with totally insane advice (think Tarot, but for the creative process), and give it a go.  This usually helps reset my state and reinstate some clarity.

But, sometimes I’m stuck in that rut because I’m simply overwhelmed.  This is most common when debugging a program crash that takes a certain sequence of operations to recreate, it’s hard to keep track of which operations I’ve tried.  In that case, I start taking notes of what I’ve tried, and then look for patterns, especially where I’ve missed some alternative way to go through things.

With those kinds of problem in mind, here’s some techniques (err, process hacks) for getting over each of them.

First up, getting over intimidation: Merlin Mann on Doing Creative Work.  Mr Mann talks at length about the mental hurdles you face in the creative process, and how to overcome/ignore them.  Here are the quotes that really resonated for me; I hope you find them helpful, or at least they help motivate you to spend half an hour listening to someone giving great, free advice.

@17:24  — “Anybody you know who does great work, sit and sweat it: I am a fraud,  I am never going to do anythign good again, and I’m going to die alone, with shit in my pants, watching cable”

@19:00 — “Develop an insane amount of tolerance for having no idea what something is turning into.”

@20:15 –  “If you let your brain give you ideas, you can execute them. You can’t force them out, you can’t think them out.  You think you can.  You think if you buy a  better mind-mapping app, you think if you get a new project management app, you think if you get a really cool pen, it’s gonna get easier, and it’s not.  You’ve got everything on your body right now, with your nerd phone or your space pen… you literally have everything you need right now to get started on that.”

@21:15 — “You’re going to have forgive yourself when it doesn’t work out on the very first day”

If, after all that, you’re not convinced that your fears of abject failure are normal, well, you need to go catch up on who that dude is, and maybe read more about how authors view themselves.  Just sayin’.

As for getting stuck in ruts, I really like Brian Eno’s Oblique Strategies cards.  I like them so much that, if I weren’t a starving entrepreneur at the moment, I might even buy them.  Until then, I’ll use the iPhone or JavaScript versions (search the App Store for the iPhone, JavaScript Oblique Strategies).  They’re a great way to knock yourself out of mental ruts you might get stuck in.  Sure, they’re totally inappropriate for the kind of work we do, but that’s half the benefit: try to make the bizarro-in-context advice (“Change instrument roles”) fit what you’re doing.  If nothing else, the mental exercise clears your mind of the patterns you keep following.  In the same vein, I have a tarot program on my iPhone.  Sure, it was $3, but that’s such a low price for a lifetime of bad advice and creative jostling.

Sometimes, though, that jostling just isn’t enough.  Especially when debugging, I sometimes keep track of which steps I’ve taken, which combinations of techniques I’ve tried, or what order of operations, etc.  In doing this, I can find new patterns to try, and keep from repeating the same steps to no avail.  This is one of those cases where the logbook idea I posted about last time really pays off: when you find a similar crash in the future, you can look back to your repro steps for this time.

All in all, I find myself relying on these more as I’m my own boss.  It’s key to keep myself productive, engaged, and not-frustrated.  A lot of that comes from being able to focus, recognize when I’m stuck in one of the above loops, and grab the right tool to pry myself out.  I hope this helps you, too.

If you have any further ideas or feedback, I’d love to hear about it in the comments.

My iPhone is gradually becoming a universal remote control, and I love it.  This is the first part of that: how to hook a generic GUI-creation tool on the iPhone up to run arbitrary commands on my Linux box.

One of the peacetime dividends of Perceptron is an awareness of OSC.  OSC is Open Sound Control, a standard for sending, well, sound controls over the network.  If you’re familiar with MIDI, it’s basically MIDI over the network, but with twice the resolution.  Technically, they seem to have made lots of really good design decisions, and it’s been around long enough to have mature tools around it.

Basically, OSC allows you to have volume sliders, arbitrary buttons (play, pause, turn on lights, etc), knobs: just about anything you could use to control music can be put into OSC.  This is great, because it allows a designer to abstract out the interface from their application, and just plug in different physical widgets to implement “volume slider 1″ or “play drum B.”  Or, just as easily, hook those up to software, so they can have a GUI to interface to humans, or pure software control, with a software robot hitting virtual buttons.

While poking around one day, I thought to myself, “Wait, someone has to have done an OSC GUI for the iPhone!”  And, sure enough, they had: OSCRemote.  It’s great fun to play with: you can add little sliders, move buttons around, and even use the accelerometers.  It’s a delight, especially if you’re used to creating GUIs in code.

However, at the end of the day, I’m still a command-line Unix guy.  How do I bridge that gap?  With a control daemon, of course!  There’s a nice C library that implements OSC (liblo) using callbacks; add a trivial config file parser and an exec() implementation, and voila: I can now run set unix commands by hitting buttons on my iPhone.  It’s incredibly configurable and general, while staying pretty straightforward.  Now I can start and stop music, jump tracks, and nudge volume up and down from anywhere in my apartment, using just my phone.

You can get the code for this at oscremoted (creative name, eh?).  It needs to get a proper homepage on my domain; until then, it’s just a tarball with a freshmeat page.  I’m curious if anyone has ideas for refinements or improvements; comment if you do!