"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.

Preparing for Academic Career

Today I read a very interesting article (in Chinese) which is about the guidance to students who are pursuing their Master's degree, telling them how to read papers, how to get the state-of-the-art information in their fields, and how to face the difficulties that one may run into during research activities. Though I am not able to find the source of the article, it should be written by a student who studied artificial intelligence at MIT. Despite the fact that I have just graduated from university, I still think I should read it carefully since I have the long-term plan to get a PhD degree and to pursue an academic career.

Several books mentioned in the article are also worth reading. Alan Lakein's How to Get Control of Your Time and Your Life talking about time management. I have started reading it, and hope to find some tips that can help me manage my time better. In the very start of the book, it reminds us not to become a time nut, who makes himself and everyone else nervous with his concern about never wasting a minute. I feel I should keep this advice in mind, because in a very busy situation like now, it is very easy for me to become that kind of person. Another book, Notebooks of the Mind by Vera John-Steiner,  is about the ideas and creativity.

Writing is a very important skill for anyone who wants to work in university. That is why I bought three books about writing today, The Elements of Style (William Strunk and E. B. White), Simple & Direct (Jacques Barzun) and Line by Line: How to Edit Your Own Writing (Claire Kehrwald Cook), all of which are recommended by the article. And most important, to improve writing proficiency, one needs years of consistent practices. Therefore I shall write the blog more frequently. Even though I am maybe never going to study for my PhD or to become a professor, I will surely still need these writing skills since they are useful almost everywhere.

Last but not least, the article mentioned the lecture about lecturing (pardon my bad wording) given by Patrick Winston. Lecturing is a very important and useful way to present your ideas and yourself. The video of the lecture helped me a lot not only in the lecturing skill which I will need in the far future, but also in other forms of oral communication such as job interview which I probably need very soon.

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.

Input Redirection in GDB (MinGW)

When using GDB to debug my program, I ran into a problem that GDB cannot accept my input redirection, because the GDB provided with MinGW passes on verbatim all arguments including redirects to the debugee.

I have found several solutions to solve this problem on the Internet, which I decide to write down here in case that I forget them.

1. Parsing a -i ifile argument using argc and argv to get input from ifile instead of stdin and parsing a -o ofile to write output to ofile instead of stdout.
2. Setting symbols for the debugee while compiling (gcc -g), and proceeding in the following manner:
   (gdb) b main
   (gdb) r non-redirect-arguments-if-any
   (gdb) p dup2(open("input.txt", 0), 0)
   (gdb) c

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.