"Congratulations! You've defused the bomb!"

Guess what? The famous Bomb Lab of Computer Systems: A Programmer's Perspective! I have done this before in the university, three years ago. After three years, I do it again. However, the lab has changed so much that I can not believe I have ever seen this . . . or maybe just because I am forgetful.

Fortunately time did not rust my skills. There is no substantial difficulty for me to do reverse engineering on this binary bomb. Identifying the transfer of control, determining the control flow, identifying the function calls, finding out the function prototypes, identifying the names of global variables, analyzing the data structures, and so on, everything can be done in a certain routine. Nevertheless, seeing the success message appearing on the screen still excited me a lot.

What is worth mentioning is the secret phase, which I did not ever find three years ago. Its entry is in the phase_defused function. The function decides whether to enter the secret phase by checking the string buffer of a certain phase. The read_line function read the user input into the string buffers. Actually it can take more than needed into the buffers, which we can exploit. To solve the secret phase, you just need to be aware that it operates recursively on a binary tree.

From the lab you can learn many things about GDB. Like me, I found that GDB can print the variable names associated with the memory addresses when I use x to check them, which helped me a lot. Another discovery is that Python is a really good command line calculator. Now I shall continue to the other lab of this chapter—the Buffer Lab.

Bit-Level Operation Tricks

These days I am reading Computer Systems: A Programmer’s Perspective by R. Bryant and D. O’Hallaron, which is an extremely interesting and useful book. The first edition of this book was the textbook of one of my courses in the university, though I did not have the chance to read it carefully due to the lack of time (there were so many courses). Now I finally get the chance to read this wonderful book cover to cover.

While doing the Data Lab, I encountered several problems whose solutions are quite tricky. There are three of them: bitCount, bang and ilog2.

bitCount requires us to write a function returning count of number of 1's in a word using almost only bit-level operations !, ~, &, ^, |, +, << and >>. The answer is a classical application of parallel computation, computing the sums of every 2, 4, 8, 16 and finally 32 bits in the word.

bang is the most tricky one among these problems in my opinion. It asks us to compute !x without using !. The point of the solution is to use sign bit as the indicator: converting negative values to positive ones, then subtracting one from the number, giving a negative value for input 0 and non-negative number for any other inputs.

ilog2 requires us to implement floor(log₂x) using the same operations as we are allowed to use in bitCount. This problem is equivalent to find the position of the most significant bit of 1. A clever way to do it is using binary search, but we are forbidden to use any control constructs. In order to create branch, notice that the following code

x = ((~c + 1) & A) + (~(~c + 1) & B);

is equivalent to

if (c == 1) x = A;
else if (c == 0) x = B;
else /* I don't care */

Based on this we can use the binary search to find the answer.

By now I have just read the first two chapters of the book. I will upload the solutions (written by myself, certainly) when I finish all the labs (which might never come).

A 3D Mesh Model Viewer Based on OpenGL

The idea about this program comes from the work I am doing in my Master's degree thesis. In my thesis project, I have to use some mesh files and programs that were left by some former student. He did not leave any document about the file format he used, so I have to figure it out by myself. The file extension is ylp, about which I could not find any information on Internet. Fortunately, things became easier when I opened the file with some text editor. The structure of the file is very easy to understand, which permits me to write a program to render these 3D mesh models. Whew!

I name the program Mesh Viewer, a quite straightforward name, and people who are interested can download it from here. In readme.txt I write the usage of the program and something about the structure of .ylp file, so you can create your own mesh files to render.

Here are some screenshots of the program.

Sudoku Solving Program

Although very busy with my master thesis, learning French and final exam (and the exams of my girlfriend's), I thought I should set some time apart to do something interesting. That is why this blog has been started. The first thing I do is to write some code to solve Sudoku. The codes (written in C) and the executive file can be found here.

Basically it is not a hard problem, though it has token me a lot of time to find a bug due to a wrong subscript of an array. Things like that always happen, sadly. The basic idea is depth-first search for each empty cell we list all the possibilities, guessing one of them, and then eliminate the possibilities of the relative cells (namely the cells in the same row, same column and the same 3 by 3 block).

Usage of the executive is very simple. You input the numbers given in the puzzle, and use 0 to represent empty cell. You can type in the numbers one by one after running the program without any arguments if you want, or you can put the numbers in a file and redirect the input stream to it. For the output you can do the same thing, viewing it directly on the screen or saving it to a file using the output redirection.

Here is an example to explain how it works. Suppose you have a file named input.txt, which contains the following numbers in a Sudoku puzzle, where 0 means empty cell:

0 0 0 0 2 0 0 7 4
0 0 1 0 0 0 0 0 0
6 0 8 3 0 5 0 0 0
0 0 0 8 0 0 0 0 9
0 1 4 0 9 0 7 3 0
3 0 0 0 0 1 0 0 0
0 0 0 7 0 6 5 0 2
0 0 0 0 0 0 1 0 0
2 6 0 0 1 0 0 0 0

To use them as the input of our program, we can type the following command in the system console:

sudoku <input.txt

Then you will see the output as:

5 3 9 1 2 8 6 7 4
4 2 1 9 6 7 8 5 3
6 7 8 3 4 5 9 2 1
7 5 6 8 3 4 2 1 9
8 1 4 6 9 2 7 3 5
3 9 2 5 7 1 4 6 8
1 4 3 7 8 6 5 9 2
9 8 7 2 5 3 1 4 6
2 6 5 4 1 9 3 8 7

That is the solution of the puzzle.