Generating de Bruijn sequences and Lyndon words

Generating de Bruijn sequences and Lyndon words

Not so long ago I encountered something called the de Bruijn sequence. For now I’ll only use this for an alphabet of (0,1), binary. But everything said here could also be applied to other alphabets. In this post I’ll describe what this sequence is, and how you can generate them, using Lyndon words.

What is a de Bruijn sequence?

Well, it is a sequence (again, in this case binary) which contains all combinations/permutations of a specific length. And it does this only once.
For example: B(2,4)

  • 000100110101111 (000)

This sequence contains all possible permutations you can make in binary of length 4. The last part (000) is optional, and needed it you do not want the sequence looped. As you can see, the length of this sequence is 16. All sequences will have length 2^N.

How do you construct these sequences?

The next thing I wanted to know is how to construct these sequences. The first hit I got was from the MathWorld website. It states:
Surprisingly, it turns out that the lexicographic sequence of Lyndon words of lengths divisible by N gives the lexicographically smallest de Bruijn sequence (Ruskey).

Lyndon word..?

It seems that the next step is generating Lyndon words. Lyndon words are the lexographically smallest rotation of a word. I haven’t yet found a proper way to do this (I know there are) so here is what I do:

Pseudo:

lastLyndon = -1
for all possible N's {
    currentSmallestLyndon = smallestLyndonRotation(N)
    if( currentSmallestLyndon > lastLyndon ) {
        lastLyndon = currentSmallestLyndon
        print currentSmallestLyndon
    }
}

And here is what I used to generate the smallestLyndonRotation (Java):

private BigInteger smallestLyndonRotation(BigInteger input, int size) {
	BigInteger lowestForm = input;
	BigInteger mask = BigInteger.ONE;
	for(int i = 1;i<size;i++) {
		BigInteger possibleLowerForm = (input.and(mask).shiftLeft(size-i)).or(input.and(mask.negate()).shiftRight(i));
		mask = mask.or(mask.shiftLeft(1));
		if(possibleLowerForm.compareTo(lowestForm) == -1) {
			lowestForm = possibleLowerForm;
		}
	}
	return lowestForm;
}

How does it work? Well, for example the input is: 0010.
It loops over all rotations (using some bit-masking):

  • 0010
  • 0100
  • 1000
  • 0001

And finds the smallest lexographically (0001) and returns this.

The above pseudo code will spit out the following numbers:

  • 0000
  • 0001
  • 0011
  • 0101
  • 0111
  • 1111

These are all the Lyndon words for N=4.

Splitting, reducing the Lyndon words

Now if we put the Lyndon words together we get:

  • 000000010011010101111111 (our sequence)
  • 0000100110101111 (de Bruijn sequence)

We aren’t quite there yet… but there is some resemblance. There is one more step left, we have to reduce/split the Lyndon words into its smallest unique part.

Lets take the Lyndon words again:

  • 0000 -> 0 (4x)
  • 0001 -> 0001
  • 0011 -> 0011
  • 0101 -> 01 (2x)
  • 0111 -> 0111
  • 1111 -> 1 (4x)

Results in: 0000100110101111, the sequence!

And that is it! If we’ve created the smallest possible de Bruijn sequence for B(2,4).

Here are some more sequences:

  1. 01
  2. 0011
  3. 00010111
  4. 0000100110101111
  5. 00000100011001010011101011011111
  6. 0000001000011000101000111001001011001101001111010101110110111111
  7. 00000001000001100001010000111000100100010110001101000111100100110010101001011100110110011101001111101010110101111011011101111111
  8. 00000000100000011000001010000011100001001000010110000110100001111000100010011000101010001011100011001000110110001110100011111001
    00101001001110010101100101101001011110011001101010011011100111011001111010011111101010101110101101101011111011011110111011111111
  9. 00000000010000000110000001010000001110000010010000010110000011010000011110000100010000100110000101010000101110000110010000110110
    00011101000011111000100011000100101000100111000101001000101011000101101000101111000110011000110101000110111000111001000111011000111
    10100011111100100100101100100110100100111100101001100101010100101011100101101100101110100101111100110011100110101100110110100110111
    10011101010011101110011110110011111010011111110101010110101011110101101110101110110101111110110110111110111011110111111111

Testing a chess engine

Testing a chess engine

About a week ago I decided to try and write a chess engine. I’ve encountered bitboards before, and I really liked working with them. Most references I found had to do with chess engines, so I decided to have a go.

The single most important and time consuming aspect of building a chess engine is legal move generation. In all situations, be able to generate all legal moves that can be made on the board. At first this seems pretty straight forward, all pieces can move and attack in certain ways. But when you get to specific rules like castling and en-passant things get really tricky.

But how do you know for sure your engine works and gets the right results? The many chess engine developers around the world found a great solution for this problem. Something I can only describe as universal integration-tests! They call it “perft” (from performance test). The first thing they do it create a particulair situation on the chess board. This can be described like in FEN notation.
For example:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
    (initial chess starting position)

All chess engines use this small language and understand how to set up their internal board. The next step is to generate all possible moves. From the example FEN above all possible moves are just 20 moves. But why stop here? From these 20 moves calculate all legal moves the opponent can make (also 20) which results in 400 moves. Continue doing this and you’ll end up with a table like this:

Depth
Nodes
Captures
E.p.
Castles
Promotions
Checks
Checkmates
1
20
0
0
0
0
0
0
2
400
0
0
0
0
0
0
3
8902
34
0
0
0
12
0
4
197281
1576
0
0
0
469
8
5
4865609
82719
258
0
0
27351
347
6
119060324
2812008
5248
0
0
809099
10828

As you can see, the numbers in these tables quickly become huge. This will ensure that a lot of situations are tested. Using these tables you can check if your program outputs the same values, and thus complies to all the rules. There are a lot of these tables online, using a FEN for starting position, and a table with all nodes that can be generated.

The next problem is, when your numbers don’t add up, how do you find the move 6 levels deep that goes wrong? Well, some engines can help you with that. Personally I used ROCE (Roman’s Own Chess Engine). His engine has a “divide” function. First you set the board in a certain position using the FEN, and then you call the divide function, for example “divide 6”. Now it shows a table like this:

move : nodes
    e2e4 1249
    e2e3 2356
    f2f3 5356
    f2f4 6436
    (etc)

This lists each node at level 1, and after that each number of nodes it results in at depth 6. If you also have this function in your own chess engine you can compare the numbers. Now you can pinpoint which of the first nodes contains the error. Do this move and try divide 5. This will guide you all the way to the specific move that is (or isn’t) created! This was a huge help, and I love the way chess engine developers devised a way to have a kind of universal integration-tests which will point out the most commonly made bugs. You can take these tables, load them in a automatic test and keep running them every nights to see if things are still working like it should.

How did my engine end up? Well, it worked perfect in the sense that it could generate all the good legal moves. Then I added a simple evaluation function and it could play chess. After that I implemented a simple search algorithm (alpha-beta using negamax) and it could beat two simple other chess engines and myself. And of course, after a week, I lost interest again and writing a blogpost about it is usually the nail to the coffin of most of my projects.

So, what should I tackle next? I’m looking forward to having a new AZsPCs competition, but I think this might take a while…

Update: A couple of readers have pointed out that these tests are obviously not unit tests, but rather integration or acceptance tests. You are completely right. I’ve called them Unit tests because I used JUnit and they run in the automatic build. But they do test integration..!


Exception mailing

Exception mailing

A couple of weeks ago our Scrum team was thinking about exception handling. We don’t use checked exceptions, since they are the embodiment of evil. So everything is translated into runtime exceptions whenever possible. But this is where the problems start: What do you do with the uncatched runtime exceptions?

Taking it one step further

Most projects will decide to just write the exceptions to the console, maybe to a log file. In some cases there is specialized software which will analyze log files, detect stacktraces and act on them. We decided to create a fast specialized solution. We want to have a mailbox where all the runtime exceptions end up, including stacktrace, system properties, program properties and even a screenshot.

Catching the uncaught exception

In Java you can set a exception handlers on Threads. You can set a handler on a Thread, but it is also possible to set a default exception handler. It is very easy:

public class CustomUncaughtExceptionHandler implements UncaughtExceptionHandler {

    public CustomUncaughtExceptionHandler() {
        Thread.setDefaultUncaughtExceptionHandler(this);
    }

    @Override
    public void uncaughtException(final Thread t, final Throwable throwable) {
        //do something here!    

    }
}

If an exception occurs, the uncaughtException method will be called. Then you can do anything you want with the throwable. As said before, we decided it is best for us that the application phones home and sends us an email with as much information as we can get.

What to send?

Our application is launched by JNLP and will run on several clients. We don’t have complete contol over these clients, so we want to include as much information as possible to solve possible bugs in the application. The more information we have about the runtime, the easier it might be to find the problem. We grab all (relevant) system properties and program properties we can get. Including usernames, machine details.

Creating a screenshot

In Java there are actually two methods of creating a screenshot. The first method is the easiest, using the Java Robot:

Robot robot = new Robot();
 
BufferedImage screenShot = robot.createScreenCapture(new Rectangle(Toolkit.getDefaultToolkit().getScreenSize()));

Very easy, but this can contain a LOT of information about the moment the exception occurs. It may provide valuable information. But we encountered a major security problem with the above method. Java will create an actual screenshot, the size of your application. But it doesn’t know if your application is currently the active window..! When we did tests we saw screenshots with Skype messages in screen and browsers being active… We can’t invade the lives of our users and send this information over the mail!

So I decided to search for something less invasive. The main frame of our application has a paint method, and most of the time this method can still be called if we have an exception. It is possible to create our own Graphics object and let the main frame paint itself into memory. So eventually I settled on the code below:

private BufferedImage createScreenshot() {
    try {
        // Try to repaint the main frame of our application:

        int w = this.screenshotComponent.getWidth();
        int h = this.screenshotComponent.getHeight();
        BufferedImage image = new BufferedImage(w, h, BufferedImage.TYPE_INT_RGB);
        this.screenshotComponent.paintAll(image.getGraphics());
        // We can't use Robot, it might capture a bit too much information

        return image;
    } catch (Exception e) {
        // Screen can't be captured, don't throw exception, else we'll end up in a loop :-)

        return null;
    }
}

Mailing the exception

The next step in our solution is sending an email with all the information. This is done using Java Mail, an API to send emails. More about sending emails from Java here. In our case we create a pretty HTML email with all relevant information and three attachements:

  • Text file with all system properties
  • Text file with the complete exception
  • The image/screenshot

To create the email it is easy to create MimeBodyParts which contain the text, the only part a bit more complicated it to add the screenshot inside the email, this can be done using:

public MimeBodyPart createImagePart(final BufferedImage screenshot)
		throws MessagingException {
    
	if (screenshot == null) {
		return null;
	}
    
	MimeBodyPart imagePart = new MimeBodyPart();
	ByteArrayOutputStream outputStream = new ByteArrayOutputStream();
	try {
		ImageIO.write(screenshot, "jpg", outputStream);
	} catch (IOException ioException) {
		// Impossible to get the screenshot, return null and continue without it

		return null;
	}
    
	DataSource source = new ByteArrayDataSource(outputStream.toByteArray(), "image/jpeg");
	imagePart.setDataHandler(new DataHandler(source));
	imagePart.setFileName("screenshot.jpg");
	imagePart.setContentID("<screenshot>");
	return imagePart;
}

The only non-obvious line in the code above is setting the ContentID, this can be used to refer to the image-data in case of an HTML email. In the main email content I added the following line:

Screenshot: <img src="/images/cid:screenshot" alt="Screenshot of the moment the exception occured." />

The src=”cid:screenshot” will cause the email to show the screenshot embedded inside the email. This makes the exception-email look very pretty.

Even more in the future…?

With our current implementation we’ll be able to detect exceptions instantly (on every new email). Also we’ll have more information then just a stacktrace, we have a screenshot and some parameters/system properties which can help us re-create the situation.

To improve this even more I’m planning on adding a simple bounded FIFO queue. This queue will contain a list of actions performed by the user. These user-actions can be added automatically by using aspect oriented programming. For example annotating all the service methods. Everytime a service method is called we can add it to the bounded queue, which has a maximum of N elements, for example 20. If an exception occurs we print our the current queue, we can read the last N actions leading up to the exception. This too can be very helpful in re-creating the situation.

What more information could be useful in an debug email like this? How do you guys solve exception handling?


Rainbow tables, reverse hash lookup

Rainbow tables, reverse hash lookup

Today I’ve been looking into rainbow tables. These are tables used to do a reverse lookup for a hash function. For example MD5, or Windows LAN Manager. Usually these tables are used to find passwords if the hash is known. Now I’m not looking for a method to crack somebodies computer, but the technology and algorithms involved are very advanced and might be usefull in other fields as well!

Hashing

First off, lets talk about ‘hashing’, what is hashing? Well, a hash-function is a one-way function which turns some data (usually text) into a hashcode. For example… passwords:

"test"     -> "098f6bcd4621d373cade4e832627b4f6"
"password" -> "5f4dcc3b5aa765d61d8327deb882cf99"

Every good website which takes security seriously will only store these MD5 hashes in their databases, not the real passwords. So even if their database is compromised the attackers don’t have anything, because the hash-function is only one-way.

Attacking a hash

Where there is security there will be crackers trying to break it. How would you go about attacking, reversing, a hash? The earliest form was just to create huge tables of:

PLAIN_TEXT -> HASH

And then check if the hash is your hash. If you have a match, you’ll get into the system!

The problem is that these tables take a very long time to compute and you’ll end up with so much data you won’t be able to store it. This made hashing pretty safe.

Rainbow tables

A couple of generations further down the line, crackers now use rainbow tables. It takes the best of both worlds having a small(-ish) table on disk, and doing minimal computations. So how do they work..?

The reduce function

Lets assume we start with a random piece of text. For example we want to crack all passwords of length 5 and consisting of [ABC…XYZ0123456789]. We can now calculate the hash value. Instead of storing this single pair, we do a little trick. We use something that is called a ‘reduce function’. This is a selfmade one-way function that turns a hash back into a password! But not the original password (it isn’t a reverse hash-function) but just into some other password.

Why would we do that? Lets continue, we take our first random password, generate a hash, and then we reduce it back to another password. This is then again hashed, reduced, hashed, reduced for lets say 1000 times. We’ll end up with:

Hash:   "random"                           -> "7ddf32e17a6ac5ce04a8ecbf782ca509"
Reduce: "7ddf32e17a6ac5ce04a8ecbf782ca509" -> "ienw3"
Hash:   "ienw3"                            -> "b9322e367ad002d5adf7ca60b8b61e86"
        ... (1000 times) ...
Hash:   "o1gti"                            -> "27aa4cbd3653a4617e0aec76ba3af9a4"

The trick is, we throw away everything except the first input “random” and the final hash “27aa4cbd3653a4617e0aec76ba3af9a4”! This is the only part we need to store.

Using a rainbow table

How can we use the data above to reverse hashes you might ask? To use this table we need the input hash. For example “b9322e367ad002d5adf7ca60b8b61e86”. First we check if this hash is in the database. If it is, we are very lucky, we can just re-generate that particulair chain and we know the plain text input!

If we don’t find anything (which is very likely) we apply our reduce function to the input-hash and then hash that result. Now we check the hashes again, regenerate the chain and find out the answer. This can be repeated until we hit our set limit (1000) in that case, if no match has been found, we can’t reverse it.

False alarms

There is one problem in this algorithm. If you take a input-hash and then do a couple of reduce/hashes, and then you find a match… it might be a false alarm! The problem is that there might be input strings that result in the same hash. If this happens two chains will end up into one chain.

If we would have done a couple of reduce/hashes from our input and find a match for endpoint “52cafa6b5e4a6509e6ed2b8e6976d780”, the original chain might not have contained our input value. When we construct the complete chain it is possible that our input-hash isn’t in the chain…!

The ‘rainbow’ of the rainbow table

The reason they call it a rainbow table has something to do with reducing the amount of false alarms. Until now we’ve talked about having one reduce-function. What if we would have multiple reduce functions? Then we could create multiple small tables, which would help reduce a little bit.

Philippe Oechslin had a great idea. He used a different reduce algorithm for each step in the chain. So his tables are build using:

input chain 1 -> hash -> reduce1 -> hash -> reduce2 -> .... -> reduceN -> hash
input chain 2 -> hash -> reduce1 -> hash -> reduce2 -> .... -> reduceN -> hash
input chain 3 -> hash -> reduce1 -> hash -> reduce2 -> .... -> reduceN -> hash

(If you color the reduce functions you’ll end up with a pretty rainbow pattern).

How would you reverse a hash using this method? Well, the first step is the same, check if your input-hash is present in the stored hashes.
Next we apply:

reduce1000 -> hash -> check
reduce999 -> hash -> reduce1000 -> hash -> check
reduce998 -> hash -> reduce999 -> hash -> reduce1000 -> hash -> check

(etc)

The big advantage is that similair hashes (collisions) will most likely use different reduce algorithms so they won’t end up in the same chain.

Conclusion

Using rainbow tables you greatly decrease the amount of stored values. It isn’t log(O), there is a bit of computation needed to do the lookups, but that as well is kept to a minimum. This results in a very fast method to crack passwords. But I think it can be used in other fields of computer science as well. There are a lot of situations where you’d like to have a very big hash-lookup table, and when it becomes too big, this can be used to reduce storage but maintain fairly good lookup times.

Salting

Almost every article about hashing and rainbow tables end with a short alinea about salting. You can do salting in a couple of different ways, but the idea is usually the same. The easiest form of salting is having on ‘salt’ for a complete database.

One salt per database

How does this work? Well, lets just generate a completely random piece of text: “thisisoursaltanditisverylarge”. Now every time we store a new user we do “MD5(password + salt)”. Because the password itself may be weak, we apply our large “database-salt” to it, and then we calculate the hash.

Now if you want to crack a hash in this system it is almost impossible. Unless you find out the salt, then you could re-create a complete rainbow table and crack all the passwords.

Using a user value as salt

An even better solution is to use a user-value as salt, for example their username or date of birth, or maybe their registration date/time. Now if somebody cracks the database and finds all the data they’ll have to create a new rainbow table for each seperate user (!!!). This is even more secure and preferred over the database-salt.

Just generate a random sequence…

But the single best way of salting your database is to generate a large random salt for each user. You can just store this salt in the database next to the hash of the password. This is better then, for example, the username, because there are just less collisions. For example usernames like “root” or “admin” aren’t very uncommon aren’t they? So creating a rainbow table with “root” as salt might be worth the trouble. But creating one with a large random number just for a single user? That is hard and they’ll probably quickly give up.

Other uses for this algorithm

I haven’t been able to come up with a good other use for this algorithm yet, but I have the feeling tons of problems could potentially benefit from it! Can you come up with one?


Finding performance problems

Finding performance problems

Many projects I’ve worked on, especially the projects using micro-optimization, had memory leaks and surprising performance hits. Most coders who work on for example Al Zimmermann’s programming contests use C/C++ and maybe even CUDA to get the most out of their system.

I’m usually using Java, just because I’m most at home in this language. It allows me to quickly get some working code and test some algorithms. But when I reach the final phase of the project it is time to micro-optimize everything.

The first tool I’ve tried it Java Visual VM. This tool is available in all the new Sun Oracle JVM’s. Just go to the bin-directory and type jvisualvm. This program will attach to your running code and tries to extract all the information. The good part of this tool is the price, it is free!

But if you really need to know what it going on inside your project, you should try YourKit. YourKit is kindly supporting open source projects with its full-featured Java Profiler. YourKit, LLC is the creator of innovative and intelligent tools for profiling Java and .NET applications. Take a look at YourKit’s leading software products: YourKit Java Profiler and YourKit .NET Profiler.

If you readers are interested I’ll write a blog with some simple examples on how to fix performance issues in your program, and how to detect these issues using Visual VM and YourKit.

Or I can do a comparison between the leading profilers (YourKit/JProfiler/Visual VM/etc)..?

Let me know!


XOR doubly linked list

XOR doubly linked list

Since a couple of days I’ve been working hard on the new Al Zimmermann’s Programming Contest: Cards (also called Topswops).

The challenge

The idea is very easy, you take a series of numbers, from 1 to N. You shuffle the numbers around, for example:

  • 5,3,1,2,4

Now we reverse the amount of numbers as stated by the first entry in the list. So in this case we reverse 5, and we get:

  • 4,2,1,3,5

We keep doing this, now reversing 4:

  • 3,1,2,4,5
  • 2,1,3,4,5
  • 1,2,3,4,5

At this point, 1 is in front, we are done! No more reversals are possible.

The problems

When implementing this the first thing I did was to create an array and reverse parts of the array by swapping the items around. The problem is that the amount of swaps is pretty big!

So I started thinking about other ways to save the numbers in this challenge.. how about a linked list? This won’t work because when updating the linked list you’ll have to reverse all the pointers in the part you are reversing.

So how about using a doubly linked list? This won’t work because we have to swap the next/previous pointers for all the nodes we reverse.

XOR doubly linked list

Then I learned about the XOR doubly linked list. Let me explain how it works. The idea is that you don’t have next and previous pointers, but you just have one pointer. This pointer is both the next AND the previous pointer! How is this possible you might ask?

Well, this is where the XOR comes into play. Lets do a tiny bit of math:
A ^ B = C
Now:
C ^ A = B
C ^ B = A

A property of the XOR is, if we have one value, we can calculate what the other value is!

When we create the list we XOR the next and previous together, and we save the pointer to the first element in a seperate pointer. Lets say A = previous, B = next, C = stored value:

  • previous ^ next = stored value
  • stored value ^ previous = next
  • stored value ^ next = previous

If we traverse our XOR doubly linked list we know the current element and the one before that (previous), so we can always calculate the pointer to the next element!

The advantages

So why would we do this? It involves a bit more processing power and will obviously save you half of the pointer-memory compared to a normal doubly linked list. We now keep one XOR-ed value instead of two pointers.

But there is another great advantage which might be usefull in the competition I mentioned above, reversability! As stated above using a doubly linked list wasn’t helpfull because when we reverse a part all the previous and next pointers have to be swapped. But we don’t have these pointers anymore, they are XOR-ed into one value! That means that we don’t have to change anything!

Lets assume we have a list of 80 items, and we want to reverse the first 40, what do we need to do now?

  1. Traverse to the 40th element
  2. Adjust the value of the 40th pointer, now the first element:
    TERMINATOR ^ (PTR TO 39)
  3. Adjust the value of the 1st pointer, it must have
    (PTR TO 2) ^ (PTR TO 41)
  4. Adjust the value of the 41th pointer, it must have
    (PTR TO 1) ^ (PTR TO 42)
  5. Pointer to the first element is now 40 (this has become our first element)

Done! We have adjusted three pointers and nothing in the middle. B.t.w. TERMINATOR is a value which indicates the boundaries of the first and last elements, I’ve used -1 for this. When traversing we use this to check if we are done.

Lets traverse the above reversed list, first we go to the first element (40) and perform the following XOR:

  • stored_value (40) ^ TERMINATOR = next (39)

This will result in 39, now we continue:

  • stored_value (39) ^ previous (40) = next (38)
  • stored_value (38) ^ previous (39) = next (37)
  • stored_value (2) ^ previous (3) = next (1)
  • stored_value (1) ^ previous (2) = next (41) !!
  • stored_value (41) ^ previous (1) = next (42) !!
  • stored_value (42) ^ previous (41) = next (43) etc etc

It works!

A bit of dissapointment

After implementing this it doesn’t seem to be faster then using swaps to reverse everything in the whole array. This is probably due to a couple of things:

  • The locality of a normal array is faster in memory
  • You’ll have to traverse N-nodes to reach the target to reverse
  • The competition has max 97 elements, this might be too small to see the advantage

My algorithm until now only used a single pointer to keep track of the first element, but it might be usefull to also keep a pointer to the last element. For example if we need to reverse everything up to N-1, I need to traverse from 1 to N-1. But if you have a last-element pointer, using the doubly in the XOR doubly linked list, we can just go backwards from N.

Ah well, it might not have been usefull (yet?) but it is a beautiful algorithm!


Patent infringement (part 2)

Patent infringement (part 2)

After a lot of comments on my blog asking about the code I decided to try getting it released one more time. Thus I mailed Digital Landmark Services again, telling them this is just a hobby project, and will (in its current form) never be a replacement for Shazam. Also, I explained a lot of people hated Shazam and deleted the application after reading this blog… the only thing they got out of it is bad marketing.

So I asked them for a peaceful solution, I’ll release the code, tell everybody Landmark Digital Services is a good company after all, and that’s it, both will benefit.

This is the reply I got:

Dear Mr. Van Rijn,

I am an attorney for Landmark Digital Services. Thank you for your response and attention to this important matter. As we have stated in detail in previous communications, we would like you to refrain from releasing the code and to remove the blogpost explaining the algorithm. While we appreciate your thoughtful comments and questions, we have already made our position clear and hope you will respect our interest in our IP.

Sincerely,
XXX
Attorney
Woodcock Washburn

WHAT!? They tell me again to remove the blogpost, this is crazy! A blogpost describing an algorithm can never be infrigement of intellectual property. The whole idea of a patent is to preserve an idea, to write down what it does and how it works for future generations. A patent has to be publicly available for this sole reason. This isn’t protecting their intellectual property, this is plain censorship.

My reply to the email was short an concise:

I’m sorry, but I can’t comply.

Good luck.

This was a week ago, lets see what they come up with this time…


Handling 'Frame switching'

Handling 'Frame switching'

A couple of days ago I noticed this tweet:

berenguel: What is your view on ‘frame switching’?How do you manage (forced) interruptions of your workflow?How do you get the interruptor to give up?

This is something I’m currently not experiencing, but I have been fighting this in the past. And I’ve come up with a quite effective way to eliminate this.

Post-it

Priority todo-list

I’m just a regular guy, and just like all men I can only focus on a single thing. Context swithing/frame of reference switching is hard. If I’m working on a programming problem and people interrupt me, ask other technical questions, I lose my train of thought.

So, how do you counter this? Well, first I made a list of things to do. This is always good to have, it directs your focus. My list is priorized. For example:

  • Implement “General overview” page
  • Fix bug with disappearing “Solve” button
  • Refactor OfflineAvailableController
  • Fix table layout bug

Yay!

Coffee time!

The top post-it is the one I’m working on, that one has my complete focus. When the project lead comes and asks me questions, I ask him to prioritize it. He can add post-its to the list and/or shuffle the list. But there is one catch: Every time he changes or I finish the top priority I need a coffee break. This is my frame-switching moment, to clear my head.

If you do this, and keep doing this (no exceptions!) the project lead will start putting his ‘requests’ (interruptions) beneath your current piece of work, without distracting you. Because else you go for a cup of coffee first…. This is what we want. When we finish what we are currently doing we get a little coffee break. When we’ve fully cleared our head we look at the next item in the todo-queue.

Don’t worry, it may sound a bit rude, they’ll understand it if you explain the problem with frame-switching…! This just makes it visible.

p.s. Berengual will probably write a blog post about his own experiences with frame-switching, I’ll post a link when he does!


Bug Fix Day!

Bug Fix Day!

After a couple of iterations our software started to show some wear and tear. With all fat-GUI clients you always have some behaviour that isn’t exacly what you want, there are always glitches. More and more (Scrum) iterations followed and more and more glitches started accumulating in the application. These glitches are sometimes hard to fix and/or hard to reproduce, and they never made their way to our backlog.
computer-bug

How do you solve this?

“Bug Fix Day” concept

To improve the quirkiness and general impression of our application, as well as the teamspirit, I decided to hold a competition! This is how we did it:

The teams

  1. Take everybody, testers, project managers and of course the developers. Mix and create small groups of three (maybe four) people with a mixed skillset.
  2. Create a jury, in our case the two product-owners and a GUI-expert.
  3. One day the teams compete against eachother.

The boards:

You’ll also need two board:

  1. Create a BugBoard with (on Post-its) all known existing glitches and bugs which need fixing.
  2. Create a TeamsBoard with a list of all the teamnames (make them come up with cool names!)

Jury:

The jury (product owners) must assign points to all the known bugs on the BugBoard, ranging from 1 point to 10 points.

  • 1 point: minor importance
  • 10 points: important! fix asap

Scoring points

Now the teams can do two things:

Fix a bug

Take a Post-it from the BugBoard and paste it behind your teamname on the TeamsBoard. There is a maximum of 1 (!!) Post-it. Your team can only claim and work on one bug at the time. While you are doing this, nobody can work on that same bug.

When you have implemented a fix for the bug, commit it, let the jury check the result. Once the jury has verified the fix, you’ll get the assigned points!

Find a bug

If you want you can also scan the application for new glitches and bugs. If you have found a (repeatable) bug, document it on a Post-it and give it to the jury. If they can reproduce the glitch/bug, they’ll assign points to the bug. For finding the bug you’ll receive half the bug’s points.

Extra rules

There are a couple of extra rules:

  1. The teams can only work on one workstation. You’ll have to pair up and work together. This will enforce the teams to look at each others code and learn.

  2. If you break the (continuous) build, you’ll lose points. For every minute the build is not green, a point is deducted from your team’s score.

  3. At the end of the day all the teams have to present their fixes.
    This will show everybody a couple of things:

  • How was the bug fixed?
  • What was wrong?
  • How could it have been prevented?
  1. Bonus points! To make it even more exiting we’ve introduced bonus points. Try to come up with original ideas! This is our list:
  • Most impressive presentation: 2 points
  • Hardest bug to fix: 2 points
  • Best team name: 1 point
  • Most original found bug: 1 point

Possible problems

Of course there are possible problems you want to avoid:
- People saving up bug-fixes
- People introducing bugs, solve on bug fix day.
- People not telling about glitches, report them on bug fix day.

We haven’t seen this behaviour yet, but you’ll have to trust the developers. Our team has enough professionalism to not have this problem (yet?).

Results

When I suggested this idea to our product owners they were very enthusiastic. About a week later we had our first Bug Fix Day and the results are very impressive.

  1. All of the 10-point (most important) bugs had been solved
  2. Most other bugs/glitches had been resolved
  3. Despite people actively abusing the system, not a lot of new glitches could be found (in contrary to our impression).
  4. Developers loved it, teamspirit was very high. It was fun to see the competitive instinct during that day.
  5. Our team won, and got a very good lunch as surprise first prize (yay!).

Other idea’s this concept could work for:
- Performance Fix Day (improve performance)
- Funny Features Day (build new features into the application)
- Other ideas…?

If you decide to hold a Bug Fix Day at your company, I’d love to hear about the results!


(Annotated) Field injection vs Constructor injection

(Annotated) Field injection vs Constructor injection

A couple of people replied to my last article about constructor vs setter injection that they prefer a third option, field injection. This is a slight variant of setter injection in which we magically let the setter dissapear.

So, another blogpost here!

Let me first show what field injection looks like:

public class Apple {  
    @Inject  
    private Orange orange;  
}

This is an example from the PicoContainer website, but Spring and Google Guice can do this too. So, you ask, what is wrong with this?

Testability

I want the classes I write to be testable. Every class needs a test, and every class needs to be tested without the help of any other dependency. For every dependency in my class I want to be able to use a stub/mock implementation.

With constructor injection this is easy, just do new SomeClass(…). But this just can’t be done with field injection..! How do you test these classes? You have no way to construct the objects without bytecode-magic. You cannot create an instance of the above Apple class with its dependencies without using the DI-framework. And the last thing I want is the DI-framework in my unit tests. It makes the test slow, and as we all know, tests need to run as fast as possible to be effective.

Final is still tricky

When using field injection your fields can be made private, but you can’t make them final (!!). This is a common mistake, but look at the Google Guice wiki: http://code.google.com/p/google-guice/wiki/Injections.

Note the warning: “Avoid using field injection with final fields, which has weak semantics.”

Code smell is wanted

And the final thing I don’t like about field injection… it looks good. This is a bad thing! I tried to explain this in the previous blogpost, but failed I guess. When using constructor injection you’ll notice when it gets ugly, you’ll see that long ugly constructor… and you’ll refactor the class. When using field injection this warning is forgotten.

Large constructor equals bad design. Don’t fix this by changing to setter or field injection, fix the underlying problem and improve your class granularity. The fact that is looks bad with more then 2 or 3 arguments is actually a big plus!

Annotations

Yes, annotations bind you to the framework, and they are evil. But so is XML. I have to agree on one thing, annotations (javax.inject) are a good thing. But still use constructor injection with these annotations please!


Setter vs Constructor injection

Setter vs Constructor injection

Recently I’ve had a discussion with a collegue about Setter vs Constructor injection. For those who don’t know what I’m talking about a quick example:

Setter injection:

public class SomeClass {
	
	private SomeDependency someDependency;
	
	public SomeClass() {
		//Empty constructor

	}

	public void setSomeDependency(SomeDependency someDependency) {
		this.someDependency = someDependency;
	}
}

Constructor injection:

public class SomeClass {
	
	private final SomeDependency someDependency;
	
	public SomeClass(final SomeDependency someDependency) {
		this.someDependency = someDependency;
	}
}

Ever since I’ve used constructor injection, I’ve never wanted to go back. For a good reason I might add. Constructor injection is just better, no discussion. Please allow me to explain.

Safe construction

First of all there is safety. In the case of setter injection it is perfectly possible to create the object without calling the setter(s). This would leave SomeClass in an uninitialized state. With constructor injection this could never happen, you just can’t create the object without at least deliberately ignoring (null-ing) the arguments.

Also, if you add a new dependency and forget to add the dependency in the XML… you’ll end up with weird behaviour and NPE’s while running your code. If you use constructor injection is would fail on startup because the correct constructor couldn’t be found. Failing early.

Finalization

In the case of constructor injection you can make the dependencies final, this is something you just can’t do with setter injection. This will further ensure the atomicity of SomeClass, it just can’t exist without its dependency. And there are many many more reasons using ‘final’ is a good idea (google it).

But… isn’t constructor injection less readable?

The only argument I’ve heard made against constructor injection is the fact that it becomes unreadable if you have too much incoming dependencies. But that argument is completely invalid!

The problem isn’t the constructor injection, it is a code smell. If your class has too much incoming dependencies you should reconsider this class. There is a good chance it is doing too much or having too much responsibilities.

So, it is actualy a good thing that constructor injection becomes aweful with too much dependencies, it is a code-smell! If the list of incoming dependencies grows too large you need to refactor, not blame constructor injection.

With setter injection it wouldn’t be almost invisible, a bad thing.

Conclusion…

In every single way constructor injection beats setter injection, so please only use constructor injection from now, k? bye!


Dinosaurize your street

Dinosaurize your street

After looking at The Wilderness Downtown, a fantastic Chrome Experiment, I felt like I had to do something similair! Three hours later (first time experimenting with Google Maps and Street View) the result is below.

It is nothing like The Wilderness Downtown, but still I’d like to share it ;-)

Enter streetname, town and country:

Image 1
Image 1
Image 1

walking

Yes, there are a LOT of bugs… And no, I’m not going to fix them, so there is no need to notify me.
Some known bugs:

  • Sometimes the dinosaur moonwalks (images go backwards)
  • Locations aren’t always found, it depends on Google Street View
  • It can only walk from the startingpoint to the next junction, no complete routes.

Patent, publicity

Patent, publicity

Wow, just wow…

Thanks a lot for all your support people, it’s great to see and read I’m not the only one to think this situation isn’t normal.

Social networking:

First it became huge on social network sites:
- #1 on yCombinator Hacker News: here
- #1 on Reddit: here
- Frontpage on Slashdot: here
- DZone Top Link: here
- Digg: here

Blogs and news sites:

And it was featured on some major blogs/news sites:

- BoingBoing: here
- OpenDotDotDot: here
- Webwereld (Dutch): here
- TechDirt: here
- The Command Line: here
(and many more)

Twitter

Also, it is a hit on Twitter too, with hunderds of retweets and people taking aim at Shazam:

(which might be a bit unfair since Landmark Digital Services LLC is the complaining patent holder, not Shazam, but I’m not sure how they relate)

``

``

springify: RT @StefanRoock: RT @mittie RT @merbist: wow the Shazam guys are real jerks: http://sites.google.com/site/redcodenl/ #wtf   asgerhallas: RT @tomasekeli: Hey #shazam, you suck :) Software patents, seriously uncool. Being a dick, even more so. #shazamfail http://bit.ly/cm4Y5f (via @blakefate)   gerharbo: Patent issues ivm Shazam. Een developer uit nl heeft code in java, shazam niet blij http://sites.google.com/site/redcodenl/   unimatrixZxero: RT @ralph: Now that I've found SoundHound, I can safely delete the app from the jerks that made Shazam: http://sites.google.com/site/redcodenl/   LuisBenavides: RT @stilkov: Software patents just suck RT @merbist: wow the Shazam guys are real jerks: http://sites.google.com/site/redcodenl/

...etc etc etc...  

Thanks again!

So thanks again for the support and the emails en tweets and blogs… I’m going to wait and see now what the next reply from Landmark Digital Services LLC will be. In the mean time, with the article available you should be able to create something similair for yourself.

Or just take the describing scientific paper and/or the patent itself, that should be sufficient (and it isn’t too mathematical, nor hard).


Patent infringement

Patent infringement

Some time ago I received the following email about this project.

-–
Mr. van Rijn,

I am Darren Briggs, the Chief Technical Officer of Landmark Digital Services, LLC. Landmark Digital Services owns the patents that cover the algorithm used as the basis for your recently posted “Creating Shazam In Java”. While it is not Landmark’s intention to alienate those in the Open Source and Music Information Retrieval community, Landmark must request that you do not ship, deploy or post the code presented in your post. Landmark also requests that in the future you do not ship, deploy or post any portions or versions of this code in its current state or in any modified state.

We hope you understand our position and that we would be legally remiss not to make this request. We appreciate your immediate attention and response.

Best regards,

Darren P. Briggs
Vice President &
Chief Technical Officer
Landmark Digital Services, LLC
-–

This scared me a bit, why are they emailing me? I’ve written some code (100% my own) and implemented my own methods for matching music. There are some key differences with the algorithm Shazam uses.

The code isn’t published yet, but I was planning on releasing it under Apache License to the open source community soon.

It was never my intention to release this commercially, I’m just a programmer who likes to work on technical, mathematical algorithms in his spare time. And if enough people ask for the source code, I’d be happy to give it to them. Who would have thought that creating something at home in a weekend could result in a possible patent infringement!?

Just to be sure I asked them confirmation that the email was indeed sent from their company. And second, I’d like to know which patents are in play. Because I just couldn’t think that something this easy (music-fingerprint is a hash, and we do a lookup) can be patented.. Maybe in the States, but in Europe?

I got the following reply from Landmark Digital Services LLC:

-–
Mr. van Rijn,

I can confirm that the email you received came from me on behalf of Landmark Digital Services, LLC. If you require a more formal notification, the Landmark legal department can provide you with a legal notification. Please let me know if that would be preferable.

The Landmark patents have been granted around the world, including the US, the EU, individual EU-member countries.

Examples of some of the Landmark patents include:
- System and Methods for Recognizing Sound and Music Signals in High Noise and Distortion
- Robust and Invariant Audio Pattern Matching

We appreciate your compliance with our request.

Best regards,

Darren P. Briggs
Vice President &
Chief Technical Officer
Landmark Digital Services, LLC
-–

They are really serious about this. But there is a problem, I still don’t have patent numbers of European patents, so there is no way for me to check the validity of their claims. Once again I asked them for specific patent numbers. And got the following reply:

-–
Mr. van Rijn,

The US patent numbers for the two examples I provided you are 6,990,453 and 7,627,477. Note that there are additional issued patents and pending patent applications in the US and Eu that cover these concepts as well.

Best regards,

Darren
P. Briggs
Vice President &
Chief Technical Officer
Landmark Digital Services, LLC
-–

Sigh, again two U.S. patent numbers. But well, lets take a step back. Why does Landmark Digital Services think they hold a patent for the concepts used in my code? Even if my code works pretty different from the Shazam code (from which the patents came).

What they describe in the patent is a system which:

  1. Make a series of fingerprints of a media file and/or media sample
         (such as audio, but could also be text, video, multimedia, etc)
  2. Have a database/hashtable of fingerprints as lookup
  3. Compare the set of hashtable hits using their moment in time it happened

This is very vague, basically the only innovative idea is matching the found fingerprints linearly in time. Because the first two steps describe how a hashtable works and creating a hash works. These concepts are not new nor innovative.

But, with a bit of imagination one could (possibly) argue that my code (again, written completely by myself in a weekend with some spare time) does the same thing as the patent describes.

Just to be sure I asked around for advice, including help from the FSF (Free Software Foundation) and the EFF (Electronic Frontier Foundation). They forwarded my questions to Bits of Freedom a Dutch organisation for digital rights.

After a good conversation with Ot van Daalen (from Bits Of Freedom) he suggested I contact Arnoud Engelfriet, a Dutch ICT lawyer and patent attorney with a lot of knowledge about software patents.

In the last couple of days I’ve had quite a few conversations with Arnoud, and he helped me with a lot of my questions.

Here are some of the conclusions:

  • Software companies can make your life very miserable if you don’t comply;
  • Using the Java-Music Match code commercially will likely result in a lawsuit for patent infringement;
  • Releasing the code under an Open Source license on a non-profit website (no ads) is a grey area;
  • Writing/using this code privately can’t be patent infringement in the Netherlands;

And even the Arnoud even mailed me:

-–
Als je de software laat staan, loop je de kans dat Landmark Digital Services je een proces aandoet. En zoals gezegd kan dat een fiks bedrag worden.

Translation:
If you leave the software on your website, you run the risk that Landmark Digital Services files a patent infringement lawsuit. And like I told you, this could result in a substantial amount of money.
-–

Since I don’t want to end up like Dmitry Sklyarov, with the possibility of a lawsuit, I’m not going to publish the code anymore… Grey area’s with lawsuits roaming around are better to be avoided. Especially if you think about the average cost of a patent lawsuit being 1 to 3 million dollars.

In the latest email I received from Landmark Digital Services they are even asking for more:

-–
Mr. Van Rijn,

The two example patent numbers that I sent you are U.S. patents, but each of these patents has also been filed as patent applications in the Netherlands. Also, as I’m sure you are aware, your blogpost may be viewed internationally. As a result, you may contribute to someone infringing our patents in any part of the world.

While we trust your good intentions, yes, we would like you to refrain from releasing the code at all and to remove the blogpost explaining the algorithm.

Thank you for your understanding.

Best regards,

Darren
P. Briggs
Vice President &
Chief Technical Officer
Landmark Digital Services, LLC
-–

They are still unable to direct me to the correct Dutch patent numbers. But more shocking, they are now telling me that my blogpost may contribute internationally to patent infringement. But… doesn’t the patent itself describe their algorithm in much more detail? The idea of patents are that the world knows about technology and how it can be used, but they can’t legally commercially exploit it? Now next to asking me not to release the code, they are also asking me to remove the previous blogpost!

This seems like a very unjust threat to me, and for now I’m going to ignore that request. If they decide to file a formal legal complaint I might reconsider taking down the blogpost. The only action I’ll take right now is not releasing the source code.

Other implementations

I’ve also had contact with other people who have implemented this kind of algorithms. Most notible is Dan Ellis. His implementation can be found here: http://labrosa.ee.columbia.edu/~dpwe/resources/matlab/fingerprint/

He hasn’t been contacted (yet?), but he isn’t planning on taking his MatLab implementation down anyway and has agreed for me to place the link here. This raises another interesting question, why are they targetting me, somebody who hasn’t even published the code yet, and not the already published implementation of Dan?!

And if they think its illegal to explain the algorithm, why aren’t they going after this guy? http://laplacian.wordpress.com/2009/01/10/how-shazam-works/

This is where I got the idea to implement the algorithm and it is mentioned in my own first post about the Java Shazam.

Any advice?

So, has anybody else had these kind of experiences? What would you do in this situation?

Maybe I’m going to need it, maybe I’ll just buy a beer, every penny is welcome:
btn_donateCC_LG.gif

Next:

The patent infrigement story continues here…

ps. I’m sorry John Metcalf: You can stop printing “Free Roy van Rijn” t-shirts…


Music Matching (part deux)

Music Matching (part deux)

After a comment on my previous blog entry (about creating a shazam clone) I started tinkering again.

Somebody asked: Could this be used to detect duplicate songs in my mp3 collection!?

That is exacly what I just tried!

The results

Here are some examples:

Duplicate found: 01 - everything in its right place.mp3.song matches with D:\data\v2\01-radiohead-everything_in_it’s_wrong_place-h8me.mp3.song and score: 134
(note: This is a remix of the original, with some rap mixed in)

Duplicate found: 01 - Joy Division - Exercise One.mp3.song matches with D:\data\v2\114 - Joy Division - Exercise One (From Still).mp3.song and score: 255
(note: Yes, duplicate!)

Duplicate found: 01 The District Sleeps Alone Tonight.mp3.song matches with D:\data\v2\The Postal Service - The District Sleeps Alone Tonight.mp3.song and score: 636
(note: Yes, duplicate!)

Duplicate found: 01-AudioTrack 01.mp3.song matches with D:\data\v2\06.Richard cheese -Id like a virgin- Butterfly.mp3.song and score: 144
(note: Yes, duplicate, the second was a radio snippet with jingle in the song)

Duplicate found: 01-editors-papillon_edit.mp3.song matches with D:\data\v2\02-editors-papillon_instrumental_edit.mp3.song and score: 382
(note: Almost a duplicate, the second is an instrumental version of the first)

Duplicate found: 01-the_strokes-you_only_live_once-ser.mp3.song matches with D:\data\v2\01-the_strokes-you_only_live_once.mp3.song and score: 450
(note: Yes, duplicate!)

Duplicate found: 01-the_wombats-backfire_at_the_disco.mp3.song matches with D:\data\v2\Backfire @ The Disco [Promo Version].mp3.song and score: 493
(note: Yes, almost duplicate, the second is a radio-promo announcement with jingle in it)

Conclusion

With a bit of tinkering this algorithm could be used to make a tool to detect duplicate songs, even if the mp3’s aren’t similair. Even live versions and instrumental versions are detected if you lower the threshold.