From Nand to Tetris in 12 steps

This came across my desk earlier today. I’ve actually been interested in this kind of “from the ground” up view: basically compiling simulators for very simple machines, but then bootstrapping all of a simulated virtual machine from the ground up.

From Nand to Tetris in 12 steps.

Addendum: This was the story that set me on the road to finding the video above. Someone implemented the 16-bit ALU from the above in terms of the LEGO-like construction materials available in the videogame “Minecraft”. Very wacky.

Works of Shakespeare Copyrighted on Project Gutenberg?

As a followup to my earlier posting on the public domain, I noticed something rather curious. if you surf over to Project Gutenberg looking for The Complete Works of William Shakespeare, you can look at the Copyright Status field, and it says “Copyrighted. Read the copyright notice inside this book for details.”


Sure enough, it says inside:


Okay, that’s not the biggest deal in the world, but I do think that it’s pretty annoying that the works of someone whose been dead for 394 years could still be under copyright. All is not lost though. While some of the plays such as this version of King Lear are copyrighted, other versions are available which are properly in the public domain. One just has to be careful about these details when one seeks to modify or redistribute these works.

While digging around, I also discovered another interesting resource. Some free online references made reference to the Complete Moby Shakespeare, and with a little digging I found that the Moby Shakespeare was available online, and it claims to be in the public domain. It is a part of Grady Ward’s Moby Project, and in addition to Shakespeare, includes a bunch of other resources: a list of 185,000 word hypenations, parts of speach, a thesaurus, and pronunciations for many words. A very neat resource. Bookmarked for later consumption.

Teaching English, Ebooks, and the Public Domain

Forgive this slightly meandering diatribe, there are a few ideas that have been kicking around in my head, and today is the day I decided to try to give them form here on my blog. I’ve been thinking about three interwoven topics: the rather odd way we teach people “English” in high school, the oncoming electronic book revolution, and the public domain.

On the drive in to work, I was thinking what an odd subject “English” actually is. It is actually an amalgum of two separate disciplines which are only vaguely related. The first is mastery (or at least competence) in the basic mechanics of the English language: mastery of spelling, increasing your vocabulary, and constructing meaningful and precise sentences. The second is usually reading, analysis and criticism of some works which are viewed as “good” by some, well, teachers of the English language. For some reason, these works seem to be almost exclusively works of fiction or poetry, and are usually of considerable diversity. They also seem to have largely written by people who are now dead, people who lived not just before the birth of modern high school students, but often before the birth of their grandparents.

Leaving that for the moment, I recently was gifted an iPad by my lovely wife. I’ve discovered (somewhat to my amazement) that one of its primary uses for me has been as an ebook reader. I’ve been rather skeptical of the ebook reading experience, but without really making an effort, I’ve found that I have read five entire books on my iPad, and generally had a very positive experience. I’ve begun to actually buy books online. Yes, you don’t actually have the physical artifact anymore, but Amazon will nicely keep track of the books you have bought, and you can redownload them to your device (or new devices) whenever you please, so in some sense they are better than the physical artifact. They are also in general signficantly cheaper: the $9.99 pricepoint is gaining some traction in the market.

I’ve also found the iPad to be a convenient repository for the myriad of technical PDF files that I used to have to print to read. Suddenly, bankers’ boxes full of papers are obsolete: I’m just downloading them to my iPad and tossing them into the shredder. The paperless office might still be a myth, but the source of much of the clutter in my office is slowly evaporating. It’s a minor revolution for me and my reading habits.

And now, the public domain. As long time readers of this blog can assert, I’m a big fan of Project Gutenberg and other efforts to make books and materials which are in the public domain widely available. But even I was forced to admit that I didn’t read a lot of the freely available classics of literature that are available because reading on your computer just isn’t that pleasant. But I find reading on the iPad to be pretty pleasant, so I’m finding that I don’t have any excuse anymore. Many, many classics are available for free and I actually enjoy reading them using the iPad. The net result of this is that I’m reading more, and it is not like I didn’t read a lot before.

Okay, back to teaching English.

One of the reasons that I suspect that high school English curricula contain so many “old books” is that these old books are now in the public domain, and are therefore cheaper to buy. But in electronic format, these books aren’t just cheap, they are for all practical purposes free. I was scanning a few suggested reading lists for high school students such as this one. The page thoughtfully says that:

Students may find these titles at libraries and bookstores.

But somewhat tragically, the page doesn’t even acknowledge that online editions could exist. I conservatively estimate that at least half and likely three quarters of these books are available in electronic formats for free. Imagine what we could do for the literacy of young people if we made sure that all these titles were available to them.

And of course we can go further. Using the Kindle reader on the iPad, you can highlight and annotate your book, but you can also share your highlighting and see parts which are commonly highlighted. Imagine an ecosphere where we could archive the commentary of these classic works, and make them similarly available to all readers.

In my analysis thusfar, I’ve been unfairly ignoring the cost of the reader. After all, my iPad wasn’t cheap even by my standards, and putting one in the hands of high school students seems like a huge expense. To that, I would merely say that other good reader options are emerging at much more competitive price points, and it is likely to only get better over time. Currently the cheapest Kindle you can buy (and which I ordered this morning) is a mere $139, which still sounds like a lot when you compare it to a single paperback, but when you compare it to 20 cheap paperbacks, it’s about even, and when you compare it to 200 paperbacks, it’s pretty obviously a heck of a bargain. It’s also a lot smaller and lighter than carrying even a single book, you can adjust font sizes so even my presbyopic eyes can read comfortably, and you can even do a bit of web browsing and check your twitter and facebook feeds.

I read arguments that we are becoming an increasingly illiterate society. Too much TV, too many video games, too much consumption, not enough reflection. But I see glimmers of hope. The computer networks which bury us in spam also allow us to communicate as never before. The devices which seduce with cheap thrills can also be used to educate and inform.

I don’t think these devices are a panacea. Putting them in the hands of students is no guarantee of improved results, but I think they represent an interesting new opportunity. And even at age forty-six, I think they will reduce the cost of enhancing my mind by bringing some classic literature onto my virtual shelf, without cluttering my physical shelf.

Okay, that’s off my chest. I’m off to download Jack London’s The Sea Wolf.

Ambisonic Microphone Exp2 Construction

Here’s one for Tom, or anyone else interested in doing ambisonic sound recordings. It mounts four inexpensive Panasonic electret microphones into a tetrahedral array to record sound that can later be processed for surround or other spatialization effects. Seems pretty cool, and they even include the patterns for PCBs that can be cheaply manufactured by ExpressPCB. Nifty!

Ambisonic Microphone Exp2 Construction Documents page.

Direct use of the PostScript language

As I have mentioned before, I sometimes find it convenient to write raw PostScript. I’ve used it to generate business cards, to make templates for laying out parts for radios and telescopees, and generating score cards and labels. Today, I had an idea for creating a large poster to hang in my office. It turns out that Costco will print 20″x30″ posters for $8.99, which is actually very cheap (almost as cheap as simple throw-away posters). So, I found myself once again coding things up in raw postscript, and generating 300dpi output from that using GhostScript. But unlike previous projects, I also wanted to include a couple of paragraphs of formatted text. I remember reading about The Tinydict system promoted by the Capella Archive. He writes whole books in raw PostScript, which isn’t actually as painful as it sounds. Digging around though, I found that there are a couple of resources thoughtfully archived on

Direct use of the PostScript language.

Software for the SDR-IQ

Earlier this year, I blogged about my acquisition of an SDR-IQ receiver, made by RFSpace. I hadn’t had it hooked up for quite some time, so I dusted it off, fired up the Spectravue software that drives it, and did some scanning around the bands. Yep, it still works. I really like Spectravue for the most part. It isn’t that hard to get used to, and allows you to easily scan the ham bands looking for signals.

But the one thing it does seem to lack is some noise reduction. Listening to hours of white noise is a bit fatiguing, and I was hoping that I could find something that would make listening a tiny bit better.

Enter SDR-Radio. It’s a spiffy program that knows about the SDR-IQ, and among other things seems to include three different types of noise reduction, as well as some better (IMO) automatic gain controls. There are aspects of the interface that I find less intuitive, but overall it is a very pretty and well done program. If you have a supported radio, check it out. > Home.

Revisiting: Printing Holograms on a Laser Printer

A few years ago I spent a couple of hours tinkering with implementing Thad Walker’s scheme for printing computer generated holograms (see the link for the paper):

Printing Holograms on a Laser Printer

A recent comment has got me thinking that I should revisit the idea and the paper. For reasons which aren’t entirely clear to me now, it seems that I understand the underlying mathematics much better now (I have done a lot more tinkering with FFTs and the like) and I think that I could use FFTW to implement a much fancier and more robust version of the original program. I also have access to some equipment that might be capable of creating accurate 2400 dpi prints, which wouldn’t hurt. Stay tuned.

Homemade T.E.A. Lasers

Nyle Steiner gets a link from me again, this time for his construction of T.E.A. lasers. I remember reading about these kind of lasers in an issue of Scientific American (I just looked it up, Jun, 1974 in the Amateur Scientist column), but that was the extent of it. Nyle has done a lot of experimentation and written up his notes here.

Homemade T.E.A. Lasers.

These lasers in most respects don’t compare favorably to the ubiquitous laser diodes that we’ve become all-too familiar with, but they don’t require any ability to fabricate semiconductors, blow glass, or indeed, have any machining skills beyond the kind you might have if you can find your way around a Home Depot.

He’s got some YouTube videos about these, oddly enough, that don’t seem to be linked to the above page. Search for his name on YouTube if you want to get more of these:


Guess What, You Don’t Own That Software You Bought | Threat Level |

Sigh. The Ninth Circuit Court of Appeals handed down a decision on Friday that says that software makers can use use licenses (in particular, shrink-wrap and click-wrap licenses) to keep you from legally reselling the software that you bought.

In other words, they just gutted the first-sale doctrine.

Guess What, You Don’t Own That Software You Bought

The somewhat poorly thought-out aspect of this ruling is that there is absolutely nothing keeping people from preventing any copyrighted work from resale on the used market. If you merely ship your book in a wrapper which includes a license agreement, you could be charged with copyright infringement for selling that book.

The EFF had this write up on the principle.

More hackable hardware: Installing OpenWrt on Seagate DockStar HOWTO

I have a suprising fascination with devices that can be reflashed with custom firmware. I have an old NSLU2 from Linksys. I have more than a couple WRT54Gish routers that run DD-WRT and Tomato. I have a Canon SD1100 that runs CHDK. I have an ASUS router that runs OpenWRT. And here’s another possible hackable device:

Installing OpenWrt on Seagate DockStar HOWTO

The gadgets used to be $99, but they are now on sale directly from Seagate for an entirely reasonable $39.99.

Seagate’s Page

Sounds like too much fun.

Addendum: A bit of clicking reveals that the CPU is an ARM-compatible SOC running at 1.2Ghz (not shabby) and with 128 megabytes of DDR2 RAM and 256 MB of NAND flash. This is actually quite a bit beefier than any of the other OpenWRT compatible devices I have. Very interesting.

Addendum2: Apparently the Dockstar is essentially a version of the SheevaPlug, but at the $40 price point, quite a bit cheaper.

Translating HAKMEM 175 into C…

A couple of years back, I made note of HAKMEM 175, a nifty hack by Bill Gosper that finds the next higher value that has the same number of ‘1’ bits as the input.

brainwagon » Blog Archive » HAKMEM 175.

If I bothered to convert it to C, I didn’t scribble it down, so I thought I’d do it here.

#include <stdio.h>

/*  _  _   _   _  ____  __ ___ __  __ _ ____ ___ 
 * | || | /_\ | |/ /  \/  | __|  \/  / |__  | __|
 * | __ |/ _ \| ' <| |\/| | _|| |\/| | | / /|__ \
 * |_||_/_/ \_\_|\_\_|  |_|___|_|  |_|_|/_/ |___/
 * A straightforward implementation of Gosper's algorithm for
 * determining the next higher value which has the same number of 1
 * bits. This is useful for enumerating subsets.
 * Translated by Mark VandeWettering.

unsigned int hakmem175(unsigned int A) { unsigned int B, C, D ;

    B = A ;                     /* MOVE B, A */
    C = -B ;                    /* MOVN C, B */
    C &= B ;                    /* AND C, B */
    A += C ;                    /* ADD A, C */
    D = A ;                     /* MOVE D, A */
    D ^= B ;                    /* XOR D, B */
    D >>= 2 ;                   /* LSH D, -2 */
    D /= C ;                    /* IDIVM D, C */
    A |= D ;                    /* IOR A, C typo? */
    return A ;

    unsigned int x ;
    int i ;

    x = 3 ;

    do {
        printf("0x%x\n", x) ;
        x = hakmem175(x) ;
    } while (x != 0) ;

I was surprised to find that there is actually a bug in the published memo. The last instruction should obviously be an OR of A and D, not A and C as listed in the published memo. After discovering the error, I seeked to find mention of it onlne somewhere. This page lists the corrected PDP-10 assembly code without comment. It also suggests a couple of optimizations: you can save one register and one instruction by variable renaming, and with a bit of work, you can avoid the integer divide, which is probably a good thing on pretty much any architecture you are likely to use.

Addendum: I thought it might be fun to show an illustration of how this could be used. At one point, while writing my checkers program, I thought about enumerating all possible positions with given numbers of checkers on each side. Counting them is actually rather easy, but enumerating them is a bit trickier, but using the trick of HAKMEM175, it becomes somewhat easier.

#include <stdio.h>
#include <stdlib.h>

unsigned int
hakmem175 (unsigned int A)
    unsigned int B, C, D;

    B = A;                      /* MOVE B, A */
    C = -B;                     /* MOVN C, B */
    C &= B;                     /* AND C, B */
    A += C;                     /* ADD A, C */
    D = A;                      /* MOVE D, A */
    D ^= B;                     /* XOR D, B */
    D >>= 2;                    /* LSH D, -2 */
    D /= C;                     /* IDIVM D, C */
    A |= D;                     /* IOR A, C typo? */
    return A;

 * Here's an interesting use (okay, semi-interesting use) of the
 * above function.  Let's use it to enumerate all the potential
 * positions in checkers which have two checkers (not kings) for
 * each side.   

#define WHITEILLEGAL    (0x0000000F)
#define BLACKILLEGAL    (0xF0000000)

main (int argc, char *argv[])
    unsigned int B, W;

    int nb = atoi (argv[1]);

    int nw = atoi (argv[2]);

    if (nb < 1 || nb > 12 || nw < 1 || nw > 12) {
        fprintf (stderr, "usage: checkers nb nw\n");
        fprintf (stderr, "       1 <= nb, nw <= 12\n");
        exit (-1);

    B = (1 << nb) - 1;

    for (;;) {
        W = (1 << nw) - 1;
        for (;;) {
            while (W != 0 && (W & (B | WHITEILLEGAL)))
                W = hakmem175 (W);
            if (W == 0)
            /* output B, W, we could be prettier */
            printf ("%x %x\n", B, W);
            W = hakmem175 (W);
        B = hakmem175 (B);
        while (B != 0 && (B & BLACKILLEGAL))
            B = hakmem175 (B);
        if (B == 0)

    return 0;

Using this, you can easily enumerate the 125,664 positions with 2 checkers on each side, the 8,127,272 positions with 3 checkers on each side, and the 253,782,115 positions with 4 checkers on each side. By then, the code gets a little slow: it has to step over all the positions where there is a conflict in B and W placement, so it gets pretty slow. Still, it works reasonably well, and as such, might serve as part of the inner loop of a retrograde endgame analysis project.