Introducing Arachnid Labs and the Loki

As many of you will have guessed from the predominance of electronics related posting recently, I've been working a lot with digital electronics of late. I recently made the decision to get serious about it, pick a trading name, and start working on projects that others can enjoy. The end result? Meet Arachnid Labs:

Arachnid Labs is the name I'll be releasing future projects under, including some that will be available to buy on Tindie. The first of these is a very ambitious project I'm calling Loki.

Loki is a microcontroller development board designed around Cypress's PSoC processor. It's extremely flexible and powerful - a big step beyond a typical Arduino style board. I'm really excited about it, and I'm working really hard to get it - and an initial set of expansion boards - ready and tested.

I'll be blogging about my progress with Loki and other projects regularly on the Arachnid Labs blog, so please check it out and subscribe if hearing about that appeals.

I've also set up accounts for Arachnid Labs on Twitter and Google+, which you can follow for news and updates.

7400 Competition Winners Announced

The winners are out! See the blog post for details.

My own entry, the Discrete FPGA is one of the 15(!) first-place winners!

7400 Competition Reader's Choice

The 7400 competition has put up a Reader's Choice post, soliciting votes for readers' favorite submissions. It's also a great summary of all the excellent submissions this year.

Go check it out! Of course, if you wanted to leave a comment voting for my DFPGA project, I certainly wouldn't complain...

Build your own FPGA

The Open 7400 Logic Competition is a crowd-sourced contest with a simple but broad criteria for entry: build something interesting out of discrete logic chips. It's now in its second year, and this time around I was inspired to enter it.

Discrete logic, for anyone who isn't familiar, are any of a number of families of ICs who each perform a single, usually fairly straightforward, function. Typical discrete logic ICs include basic logic gates like AND, OR and NAND, Flip-Flops, shift registers, and multiplexers. For smaller components like gates and flipflops, a single IC will usually contain several independent ones. As you can imagine, building anything complex out of discrete logic involves using a lot of parts; these days they're typically used as 'glue' logic rather than as first-class components, having been largely supplanted by a combination of specialised devices, microcontrollers, and FPGAs.

Building a microcontroller or CPU out of discrete logic is a popular hobbyist pursuit, and it serves a useful purpose: building a CPU from scratch teaches you a lot about CPU architecture and tradeoffs; it's an interesting and instructive exercise. So, I wondered, wouldn't building an FPGA out of discrete logic be ...

Penny for your thoughts?

I've been using my spare time lately to build something that's even more trivial and silly than usual. Behold, the advice machine!

Operation is pretty straightforward. You insert whatever quantity of coins you see fit, then request some advice from the machine. The quality of the advice you get reflects the value of the coins you put in - more or less. More money typically results in more in-depth fortunes, and more interesting ones such as quotations, while a small amount gets you platitudes or terrible jokes.

Here's a video of it in action:

More photos can be found here.

All in all, the project was relatively straightforward, after a couple of false starts. The coin acceptor is a standard item commonly found on ebay - this one has model number CH-926 - for around about $20-$30. The device has a moderately complex setup procedure whereby you 'train' it on a set of sample coins, and tell it how many pulses to output for each coin. After that, it will recognize coins similar to the ones it was trained on, outputting the appropriate number of pulses on one of its pins when each is detected.

The LCD is a ...

Damn Cool Algorithms: Cardinality Estimation

Suppose you have a very large dataset - far too large to hold in memory - with duplicate entries. You want to know how many duplicate entries, but your data isn't sorted, and it's big enough that sorting and counting is impractical. How do you estimate how many unique entries the dataset contains? It's easy to see how this could be useful in many applications, such as query planning in a database: the best query plan can depend greatly on not just how many values there are in total, but also on how many unique values there are.

I'd encourage you to give this a bit of thought before reading onwards, because the algorithms we'll discuss today are quite innovative - and while simple, they're far from obvious.

A simple and intuitive cardinality estimator

Let's launch straight in with a simple example. Suppose someone generate a dataset with the following procedure:

  1. Generate n evenly distributed random numbers
  2. Arbitrarily replicate some of those numbers an unspecified number of times
  3. Shuffle the resulting set of numbers arbitrarily

How can we estimate how many unique ...

Damn Cool Algorithms: Homomorphic Hashing

In the last Damn Cool Algorithms post, we learned about Fountain Codes, a clever probabilistic algorithm that allows you break a large file up into a virtually infinite number of small chunks, such that you can collect any subset of those chunks - as long as you collect a few more than the volume of the original file - and be able to reconstruct the original file. This is a very cool construction, but as we observed last time, it has one major flaw when it comes to use in situations with untrusted users, such as peer to peer networks: there doesn't seem to be a practical way to verify if a peer is sending you valid blocks until you decode the file, which happens very near the end - far too late to detect and punish abuse.

It's here that Homomorphic Hashes come to our rescue. A homomorphic hash is a construction that's simple in principle: a hash function such that you can compute the hash of a composite block from the hashes of the individual blocks. With a construction like this, we could distribute ...

An interesting gotcha in Java unittesting

Those of you who have more than a passing familiarity with Java will be aware of Java's semantics for object equality using '==': it returns true iff the two arguments are the same object. There's no operator overloading for the equals operator, even by built in classes; classes that want to do value equality tests are expected to override the built in 'equals()' method.

This leads to a common pitfall with Strings. The following compiles fine, with no warnings:

public static void isFoo(String s) {
  return s == "foo";

This won't work as intended, of course, because it will only return true if the passed in string is the very same object as our string literal "foo". Let's write a unittest to make sure everything works as expected:

public void testIsFoo() {

But wait! This test passes just fine! Something is very wrong here.

What's happening is that the Java compiler is interning string literals, so that multiple uses of the same string constant point to the same actual string object at runtime. This saves memory, but it's making it tough for us to test properly. You might ...

Endings and beginnings

As of July 8th, I will no longer be working at Google.

The last four-and-a-half years at Google have been an incredible experience. First working as an SRE - Google's oncall / infrastructure role - and then as a Developer Programs Engineer, I've learned an incredible amount, worked with some amazing people, and done some exciting things. I've been with the Google App Engine team - first in a 20% capacity, and then full time - since before the product launched, and I think I've had a significant impact on the product and the community that's formed around it. I've greatly enjoyed interacting with everyone in the community and lending a hand where I can.

Ultimately, though, I've decided it's time for me to move on and seek out new challenges. With that in mind, I'm going to be working at Smart Sparrow, an exciting Sydney startup who are making waves in the education area. They're doing some really impressive stuff with E-Learning, and I'm excited to be joining them and helping shape things. Although I've worked at small companies before, this will be my first time at a for-real startup, and I ...

Shameless plug

Just a quick reminder that I've started my tour of NZ, and I'll be blogging about it at - so check it out and subscribe, if you're so inclined.

This is the last time I plug the blog here, I promise*.

* I reserve the right to renege on this promise. It _is_ my blog, after all.