Adding a license text to a set of files using sed

The problem: I needed to add (prepend) a license text to a set of source files.

I thought sed might be a good tool for this task. Having not done anything but trivial sed scripts in the past, I took a look in the web for advice.

I was faced with the following script (I already lost the original URL, I'm sorry):

1{h; r [file]
D;}
2{x; G; }

It needs some explaining. Sed works by maintaining two data buffers: the pattern space and the hold space. A sed execution cycle is performed for each input line. First the input line is placed in the pattern space. Then the commands are (conditionally) executed. Finally, the contents of the pattern space are printed to stdout (if not explicitly prevented). The hold space maintains its contents between two cycles. The pattern space on the other hand is cleared between two cycles.

The GNU sed manual explains the used commands as follows.

h - "Replace the contents of the hold space with the contents of the pattern space."

r [file] - "Queue the contents of filename to be read and inserted into the output stream at the end of the current cycle, or when the next input line is read. Note that if filename cannot be read, it is treated as if it were an empty file, without any error indication."

D - "Delete text in the pattern space up to the first newline. If any text is left, restart cycle with the resultant pattern space (without reading a new line of input), otherwise start a normal new cycle."

x - "Exchange the contents of the hold and pattern spaces."

G - "Append a newline to the contents of the pattern space, and then append the contents of the hold space to that of the pattern space. "

So the program is performing the job as follows. The first set of commands is executed only for the first line of the input. The first line is copied to the hold buffer. After that, the file [file] is queued to be printed to stderr in the end of the current cycle. Finally, the contents of the pattern space is deleted (so that the first line won't be printed just yet).

Now the file [file] (containing the license text) has been printed. Nothing else has been printed. Also, the first line has been saved to the hold space. Looks good. The second set of commands do the rest. These commands are executed for the second line of the input only. First the contents of the hold space and the pattern space are switched. Now the hold space contains the second line of the input and the pattern space contains the first line of the input. Now a newline and the contents of the hold space are appended to the pattern space. The pattern space now contains the first two lines of the input in correct order. Next, the cycle ends and the contents of the pattern space are printed.

No commands are executed for the remaining lines of the input. They are just printed by default. We have printed the license text, the first line of the input, the second line of the input and the rest of the input in correct order - effectively prepending the license text on the input files.

Now considering the license text is located at /tmp/license, the following code is exactly what is needed to do the job for each *.c and *.h files in the current directory.

sed -i '1{h; r /tmp/license
D;}
2{x; G; }' *.[ch]

Google's 3D view over Vallila/Helsinki

And so Google Earth got 3D view of Helsinki [digitoday.fi]. Here's a picture depicting Vallila, that is, my current home.

LLVM assembly and integer signedness

LLVM assembly does not encode integer signedness which can be a nuisance when reading the assembly code. On the other hand the policy simplifies the representation, as the sign does not make a difference in most of the operations (such as integer addition). In some operations (such as boolean comparisons on integers <, <=, >, >=) signedness is significant, however. For completeness, let's remember that the (dis)equality operator does not care about the sign.

Let's have a look on the following C program block:

if (x < UINT_MAX-1)
    puts("foo");
else
    puts("bar")

Piping clangs's output to llvm-dis gives us the following LLVM assembly representation:

%1 = load i32* %x, align 4
%2 = icmp ult i32 %1, -2
br i1 %2, label %bb, label %bb1

bb:
%3 = call i32 @puts(i8* getelementptr ([4 x i8]* @.str, i32 0, i32 0)) nounwind
br label %bb2

bb1:
%4 = call i32 @puts(i8* getelementptr ([4 x i8]* @.str1, i32 0, i32 0)) nounwind
br label %bb2

bb2:

Now, in the assembly code, it can be read that the %1 register is compared with -2, and the operands are to be interpreted as unsigned 32-bit integers. On the bit level, that is of course correct. However, a human needs to make a conversion in her head to understand on what concrete values of %1 the first branch is taken.

In the two's complement, the first bit represents the sign. For negative numbers, the sign bit is set, for positive, it is unset. The number zero is represented as a value where all bits are unset. The smallest negative value of an n-bit integer is represented as one followed by n-1 zeros. Semantically it can be thought as if the rightmost n-1 bits represent a positive value that is summed with the smallest negative value available (-2^(n-1)), and the result is something between -2^(n-1)..-1.

Assuming 4-bit integers, -2 is represented as 1110 (-2^3 + 6). When 1110 is interpreted as an unsigned integer, that is 14 (2^3 + 2^2 + 2^1). However, in our example, we have 32-bit integers (the i32 type in LLVM), where the min value for int is -2147483648. In the 32-bit world, -2 is represented by a number where there are 31 ones followed by a zero. Interpreted as unsigned, that is 2^31 + 2^30 ... 2^2 + 2^1 = 4294967294.

So we came to the conclusion, for values of %1 < 4294967294, the first branch is taken. Otherwise the second branch is taken. That was not obvious directly from the assembly code. We had to consider the integer width to deduce the concrete unsigned value.

It should be noted that one can decide whether to write integer literals as the llvm tools do or not. Since the bit representation is identical for signed i32 -2 and unsigned i32 4294967294, it does not matter which way it is written. I would still stick to the signed interpretation for consistency's sake. Otherwise it becomes a hopeless mess.

Sex differences

I wanted to see what kind of questions we are asking about the opposite sex. Google. Let us assume that questions asked about men are usually asked by women and vice versa.

Top suggestions for 'how do women...':
1. get pregnant
2. think
3. get yeast infections
4. flirt
5. come

Top suggestions for 'how do men...':
1. think
2. fall in love
3. flirt
4. get hpv(*)
5. get yeast infections

(*) human papillomavirus

Comparing the first matches makes me sad.

Emil finds its first defect!

I earlier described the nature of my work at TKK tcslab. My job is to write a tool for automatically testing C programs using a technique called dynamic symbolic execution basing the implementation on LLVM. I call my tool Emil (that is ucfirst(reverse(lower(Lime))) after a similar tool called Lime for testing Java programs, developed here as well).

Emil is currently at 2.9 KLOC, and for the first time, I wrote a test case that should fail, and it failed on the first attempt! This is somewhat a milestone so I now celebrate it by showing the test case and the failing inputs found by Emil. This is of course all trivial and useless, but I believe Emil is going to the right direction.

==divzero.c==

int input(void);
int main() {
    int i = input();
    int j = input();
    if (i > j) {
        i = i / (0*j); // ouch
    } else {
        i = j;
    }
    return i;
}

==Values for i, j by Emil that will lead to division by zero==
{i: 892648572, j: -1285173836}

I hope this is just the beginning for Emil. The future of Emil will be out of my hands, though, because I will (in my current knowledge) leave Emil in the hands of others before next year and be searching for new challenges in the software industry.

Back to work

Ah, my week-long summer vacation is now over. I mostly spent the time in a friend's summer cottage in Sysmä and in the beautiful archipelago of Sipoo. Last two days I was in Porvoo. Vacation reading included works from Hesse and Solzhenitsyn, but I especially want to raise Erlend Loe's Naive, Super that I fell in love with when sitting in a bus.

As for work, I'm now familiar with LLVM optimization pass architecture and implementation. It all feels intuitive. On the negative side, C++ frequently demonstrates its clumsiness in basic tasks. Also, the LLVM API is poorly documented, so I constantly find myself grepping (actually, ack'ing) around the LLVM tree and reading code rather than the doxygen (huh) generated API. However, all in all I'm definitely thankful for LLVM.org/docs.

C++ name mangling

Ever wondered what the 'extern "C" { ... }' block stands for in C++? In C and C++ the 'extern' keyword is used to declare external variables that are instantiated in other translation units. Using 'extern' tells the compiler not to allocate space for the variable as space is being allocated elsewhere. The keyword is also used within variable instantiation. In that case its semantics are to denote that the variable may be referenced from other translation units.

The 'extern "C" { ... }' block, however, has additional semantics. Let's first explain what name mangling is and why it is required.

In C functions cannot be overloaded by type. Thus we cannot declare, for example, functions with prototypes 'int foo(void)' and 'int foo(int)' in the same program. In C++, however, such overloading is possible. Due to the tight coupling of C and C++, particularly in the past (C++ was first implemented by compiling C++ code to C code and then using a regular C compiler to produce machine code), C++ compilers must use distinct symbols for overloaded functions to be compatible with the linker. Name mangling is the act of adding type information in the function names to separate overloaded functions from each other.

For example, the GNU C compiler mangles the first 'foo' function [int foo(void)] to '_Z3foov' and the second 'foo' function [int foo(int)] to '_Z3fooi'. The '_Z' is just a prefix that is a unique identifier in C/C++ that prevents conflicts with user defined identifiers. The number is the length of the original name, three in case of 'foo', and the following letters encode argument types (here 'i' for int and 'v' for void, respectively).

Now, suppose there is a C++ function 'bar' that we would want to use in our C module. We would declare a prototype for 'bar' in the C module that references the function and link the C module with the C++ module, that provides the definition for 'bar'. Let's try just that:

-------module.c--------
int bar(void);
int hooray() {
    return bar() + 42;
}
-----------------------

-------bar.cpp--------
int bar(void) {
    return 7;
}
-----------------------

Let's first compile our modules:

$ g++ -c -O0 -o bar.o bar.cpp
$ gcc -c -O0 -o module.o module.c


Then link them together to produce an executable

$ gcc -O0 bar.o module.o


 module.o: In function `hooray':
 module.c:(.text+0x7): undefined reference to `bar'
 collect2: ld returned 1 exit status

The linker could not find 'bar' from the symbol table. And that is precisely due to C++ name mangling. Let's have a look inside bar.o:

$ objdump -D bar.o

 -- [clip] --
00000000 <_Z3barv>:
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   b8 07 00 00 00          mov    $0x7,%eax
   8:   5d                      pop    %ebp
   9:   c3                      ret
 -- [/clip] --

There it is again, the function is called '_Z3barv' instead of 'bar'. This is the point where the extern "C" block comes to the rescue. It declares that the symbols declared inside the block are to be referenced from C context, and thus the compiler cannot mangle the names.

If the code in bar.cpp is wrapped inside the extern "C" block, everything will work:

-------bar.cpp--------
extern "C" {

int bar(void) {
    return 7;
}

}
-----------------------

Recompiling bar.cpp:

$ g++ -c -O0 -o bar.o bar.cpp

.. and relinking the modules:

$ gcc -O0 bar.o module.o


No errors. If you now disassemble bar.o you will see that the name of the bar function is now 'bar' instead of '_Z3barv', and thus the C module is able to reference the C++ function.