Mar 09

Beat Detection: A Raspberry Pi Hacking of Hallmark’s “Happy Tappers”

In graduate school, time series analysis was the topic I liked the most. The classic models (like AR(p), MA(q), ARMA(p,q), etc.) are used usually after time series have been sampled in some fashion. Of course, there’s more than one way to look at a time series and many of those perspectives come from the field of digital signal processing. Unfortunately, a lot of the text books on DSP are dry. One can spend hours reading a DSP book, understand the math, and still not really appreciate the material. I happen to think the appreciation for the topic comes more from trying to solve real-world problems. As problems are encountered, the motivation arises to go back and attack the mathematics in a meaningful sense. One of the more interesting problems, in my opinion, is real-time beat detection in music.  Therefore,  I decided to do some experimentation with beat detection.

After Christmas, I went through pharmacy after-Christmas sales and picked up a bunch of cheap Hallmark ornaments. When I discovered the ornaments had a port to interface to each other, I decided I’d look at the interfacing method and devise my own schemes for controlling them. After figuring out the communications protocol between ornaments, I experimented by building control systems using FPGAs, Arduinos, and the Raspberry Pi.  I ultimately settled on the Raspberry Pi.

With the Raspberry Pi, I was able to perform FFTs fast enough on the music samples to make a crude attempt at detecting beats while playing mp3 files. The project is still something I tinker with from time to time. I find entertainment in looking at various approaches for beat detection in research papers and documents on the internet.  Below is a sample of what I have been able to create so far, which is a hack of Hallmark’s Happy Tappers, set to a clip Capital Cities’ “Safe and Sound”:

As precious free time becomes available, I’d like to improve the system to work with onset detection and explore various filtering problems.

Finally, I’d like to thank the Dishoom Labs crew (MB) for letting me borrow some equipment during the project.

Jun 01

C++ Reading List

In the past, I’ve paid for various libraries (such as Anthony Williams’ excellent  just::thread library ) and C++11 documents to make an attempt to get ahead of the curve.  Now, however, C++11 information is becoming more easily accessible.  There is quite a bit of new content out there that is making things more digestible for programmers who aren’t so involved as to be following the evolution of C++ standard.

I think this particular Dr. Dobbs article/link is technical gold for people navigating the new C++11 standard and its feature set: C++ Reading List

A key item to note is that Bjarne Stroustrup’s book, “The C++ Programming Language”, has had its 4th edition released recently.  (It is also in the list.)

 

May 26

C++11 Idioms Slideshow from Silicon Valley Code Camp

I stumbled across this very nice presentation (see below) by Sumant Tambe on C++11 idioms on Google+ and figured I’d stash a link here.

I try to integrate as much C++11 as I can into my projects where I think there would be benefit. However, without reading the C++ programming community’s input on various programming techniques, it’s difficult to know the drawbacks of using a particular method until it’s too late (and costly). Whenever new idioms like this are presented in a clean format like in Sumant’s slideshow, I’m always eager to read about the general consensus/feedback/comments of others.  (Incidentally, Sumant’s blog is a gold mine of interesting C++ techniques; many [enjoyable] hours can be lost there.)

Have a look for yourself:

May 12

C++, WebSockets, and Mt.Gox

I’ve been reading quite a bit about websockets lately. To test my understanding of the concepts involved, I was trying to connect an application to Mt.Gox in order to collect bitcoin-related pricing information. I was having some difficulty getting all of the parameters aligned properly with all of the various websocket libraries, so I went through the process of reading other people’s code on github, sifting through stackoverflow-style-forums, and experimenting until things worked correctly. I thought I’d document some of the minor hurdles here, just to save some people out there in the wild some effort.

I tried a few approaches:

  • Python using autobahn
  • C++ using libwebsockets (a C library)

The Python implementation worked perfectly.  The only quirk was that I had to trick the application into inserting an “Origin:” field in the websocket handshake in order to get the application to connect.  (This had something to do with something called the Web Origin Concept.  It’s a safety mechanism for web browsers.)  After tweaking the code to force an ‘Origin’ using the autobahn library, the handshake with the server ended up looking something like this:

GET /mtgox HTTP/1.1
User-Agent: disease
Origin: websocket.mtgox.com:80
Host: websocket.mtgox.com:80
Upgrade: WebSocket
Connection: Upgrade
Pragma: no-cache
Cache-Control: no-cache
Sec-WebSocket-Key: JI2o83NARHJDps1XCN7eCQ==
Sec-WebSocket-Version: 13

After a handshake of this style, data starts streaming over the connection with no issue. With a working Python version, I had enough knowledge to craft an appropriate handshake in the C++ version of my bitcoin application.

With libwebsockets, it took some tinkering with the source code to get things to work right with Mt.Gox. The extensions field in the ‘lws_context_creation_info’ should not be filled in, and in the connection phase in libwebsocket_client_connect(), the specified protocol should be NULL. The origin and host strings fed into the libwebsocket_client_connect() function should mirror what you see above in the successful python handshake.

I didn’t bother to post code here, but the general idea to get things to start streaming correctly is to have a handshake that looks something like what I’ve copied above for the python implementation I used.

I hope this helps the random Googler out there searching for information.

Apr 16

Merkle Trees

The paper detailing the mechanics of Bitcoin is a fascinating read. However, the technology involved requires several re-readings of the paper to make sense of what is going on.  I’ve been attacking the concepts piece by piece as time permits. In particular, the Bitcoin paper’s comments regarding the use of the Merkle Tree caught my eye. I had never encountered the concept of a Merkle Tree before in any applications I’d worked with, so I figured some investigation would be worthwhile.

Within Bitcoin, the Merkle Tree is a disk-space saving mechanism.   From the Bitcoin paper:

” Once the latest transaction in a coin is buried under enough blocks, the spent transactions before it can be discarded to save disk space. To facilitate this without breaking the block’s hash, transactions are hashed in a Merkle Tree […], with only the root included in the block’s hash. Old blocks can then be compacted by stubbing off branches of the tree. The interior hashes do not need to be stored.

I did some digging into the Merkle Tree and read some of the implementation code to understand it. I found that the Wikipedia page does a pretty good job summarizing the data structure:

“In cryptography and computer science a hash tree or Merkle tree is a tree in which every non-leaf node is labelled with the hash of the labels of its children nodes. Hash trees are useful because they allow efficient and secure verification of the contents of larger data structures. Hash trees are a generalisation of hash lists and hash chains. To demonstrate that a leaf node is part of a given hash tree requires an amount of data proportional to the log of the number of nodes of the tree. (This contrasts with hash lists, where the amount is proportional to the number of nodes.) The concept is named after Ralph Merkle.”

The bitcoin source code helps make some of the concepts clearer.  Within the code, the CBlockHeader shows a member variable ‘uint256 hashMerkleRoot’ that refers to the concept mentioned in the paper:

class CBlockHeader
{
public:
    // header
    static const int CURRENT_VERSION=2;
    int nVersion;
    uint256 hashPrevBlock;
    uint256 hashMerkleRoot;
    unsigned int nTime;
    unsigned int nBits;
    unsigned int nNonce;
    ...

And, as far as the actual construction of the Merkle Tree:

uint256 BuildMerkleTree() const
{
    vMerkleTree.clear();
    BOOST_FOREACH(const CTransaction& tx, vtx)
        vMerkleTree.push_back(tx.GetHash());
    int j = 0;
    for (int nSize = vtx.size(); nSize > 1; 
         nSize = (nSize + 1) / 2)
    {
        for (int i = 0; i < nSize; i += 2)
        {
            int i2 = std::min(i+1, nSize-1);
            vMerkleTree.push_back(
                Hash( BEGIN(vMerkleTree[j+i]),
                      END(vMerkleTree[j+i]),
                      BEGIN(vMerkleTree[j+i2]), 
                      END(vMerkleTree[j+i2])));
        }
        j += nSize;
    }
    return (vMerkleTree.empty() ? 0 : vMerkleTree.back());
}

The first thing to note is that the Hash() function mentioned in this code is actually a SHA256 double hash. (You can look into the code for yourself to validate this.)

The code appears to iterate over a vector of transactions and pushes their hashes into a vector representing the nodes of the Merkle tree. It then loops in such a manner that it appears to hash adjacent transaction hashes together (if an adjacent node is available — if one isn’t, the node is concatenated with itself). So if there are 3 transactions (nSize=3), [1, 2, 3]. The first pass of the outer loop, nSize = 3, you get an inner loop where there’s a hash of the hash computed over the hashes of element 1 and element 2 (we’ll call it dhash[1,2]), then a hash of the hash of element 3 concatenated with itself (dhash[3,3]). The variable j increments forward, so that on the next loop iteration, the double hash of dhash[1,2] and dhash[3,3] (both from the previous iteration) is computed, etc., etc. and the process continues until the tree gets built within a vector. The last node (vMerkelTree.back()) ends up being the root hash.

When I queried some people on various forums as to the necessity of the double hash as opposed to a single hash, they claimed it was desirable as a means of increasing the cost of calculation within the bitcoin framework.

Interesting, right? I hope to look more into the transaction mechanisms as I dig further into the system. Nevertheless, the exercise of going through the code to construct the Merkle Tree was educational and enlightening.

 

Apr 09

Qt 5.1 Supports Android and iOS

I didn’t plan on writing marketing material for Digia here.  However, as an existing Qt user, I was excited to see this article.  The ability to target Android and iOS will make it easier to take pieces of functionality I am dependent on currently and take them to new platforms.  I’ve often wanted to collapse pieces of well-tested, already written code and just make them function in the mobile space without too much effort.  I like seeing that my original investment in Qt will continue to pay off and extend my reach.

Qt is, in some senses, not as elegant as some of the newer frameworks.  (Developing GUIs, for example, in Microsoft’s .NET with C# is almost relaxing.)  However, the appeal with Qt has always been the cross platform functionality.  It’s simply impractical for small organizations to maintain several different builds and variations for so many different platforms.  Qt enables that flexibility, at least once you get past the quirkiness of doing things the Qt way.

Adding iOS and Android will just make the development experience that much better.