Vikram and Neha

Project Euler in R: Problem 25

2012-01-24T19:19:00.000-08:00

Solutions in R to Project Euler problems are generally hard to find, so I've recently started posting R solutions on this site. Here are the previous problems: problem 22, problem 23 and problem 24

Now let's look at Problem 25 from Project Euler. Here is the problem statement:

The Fibonacci sequence is defined by the recurrence relation: Fn = Fn1 + Fn2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:
F1 = 1
F2 = 1
...
F11 = 89
F12 = 144
The 12th term, F12, is the first term to contain three digits. What is the first term in the Fibonacci sequence to contain 1000 digits?

This is an easy problem to solve for a small number of digits. It gets interesting once we increase the required number of digits to 1000. The R integer type can hold 10 digits at most, and the type double can hold 309 digits. There is no Big Integer class in R that can hold larger numbers, so to compute the 1000 digit Fibonacci number we will have to be creative.

Computing Fibonacci numbers iteratively

Here is a basic iterative Fibonacci function, that works for Fibonacci numbers with 309 or fewer digits.

fib <- function(n) {
  a = 0
  b = 1
  for (i in 1:n) {
    tmp = b
    b = a
    a = a + tmp
  }
  return (a)
}

The version that works with larger numbers is similar, with the following changes

Integer vectors are used to store each Fibonacci number.
Each element of the vector is at most nine digits long.
Once all the nine digits are used, a new element is added to the vector and the Fibonacci number computation is carried over to the new element.
The variable numberDigits counts the number of digits in the latest Fibonacci number. When numberDigits exceeds 999, the function exits, returning the Fibonacci number index.

fib.bigint <- function(lim) {
  a = c(0)
  b = c(1)
  n = 0           # Fibonacci number index
  integerSize <- 1000000000  ## How big is each integer
  while (1) {
    n = n + 1     # Compute next Fibonacci number
    tmp = c(rep(0,length(a)-length(b)), b)  # Pad beginning with zero
    b = a
 
    # Add a and tmp
    carry = 0
    for (i in length(a):1) {
      sum.i = tmp[i] + a[i] + carry
      a[i] = sum.i %% integerSize
      carry = floor (sum.i / integerSize)
    }
    if (carry > 0) {a <- c(carry, a)}
    numberDigits <- (length(a) - 1) * 9 + countDigits(a[1])
    if (numberDigits > (lim - 1)) { return (n) }
  }
}

countDigits <- function(n) {
  count <- 1
  for (i in 1:9){
    if ((n/10) > 1) {
      count <- count + 1
      n = n / 10
    } else {
      return (count)
    }
  }
}

On my Intel Core 2 Duo 1.6Ghz laptop running Linux, this function less than 4 seconds to find the Fibonacci number with 1000 digits.

The analytical solution
Fibonacci numbers have a closed form solution, which leads to a simpler approximation by rounding (from Wikipedia),

F_n = the closest integer to (golden ratio)^n / sqrt(5)

We need the first Fibonacci number with 1000 digits. This number will be greater than or equal to 10^999.

F_n = the closest integer to (golden ratio)^n / sqrt(5) >= 10^999

We can drop the closest integer function because if F_n rounds off to the floor of the ratio, the resulting Fibonacci number will have less than the required digits. So we need smallest n satisfying

(golden ratio)^n / sqrt(5) >= 10^999

Or, n >= (999 log(10) + log(sqrt(5)))/log(golden ratio)

Or, n >= 4781.86

So we need the 4782nd Fibonacci number to get the required 1000 digits.

This problem was particularly interesting to R users because it runs into an R-specific limitation. Many other languages don't have this problem and can just use a simple Fibonacci generator to get the answer. For example, in Scheme (or other Lisp variants), a naive Fibonacci implementation produces all the digits.

Aside: Having started writing about R, I have found an excellent online resource, R-bloggers - an aggregator of content from various blogs about R. You can search for other R Project Euler solutions here. Be sure to check out the top articles box on R-bloggers landing page if you're looking for new and interesting applications of R.

Project Euler in R: Problem 24

2012-01-19T19:52:00.000-08:00

I had previously posted solutions in R to Project Euler problem 23 and problem 22. This is the next problem from Project Euler. The statement of problem 24 is as follows.

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are: 012 021 102 120 201 210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

This is a very interesting problem and it can be solved analytically. The key insight is that n distinct digits can be arranged in n! permutations.

Here's the logic you could use. If the permutations of the numbers 0 through 9 are arranged in lexicographic order,

The first 9! permutations, #1 to #362,880 are numbers starting with 0, in order from 0123456789 to 0987654321
The next 9! permutations, #362,881 to #725,760, are numbers from 1023456789 to 1987654320
The next 9! permutations, #725,761 to #1,088,640 are numbers from 2013456789 to 2987654310. The millionth permutation is contained in this set. Thus we know that the millionth number must start with a 2. In fact, it is the 274,240th = (1000000 - 725760) number contained in this set.
Our problem has now reduced to finding the 274,240th lexicographic permutation of the numbers 0, 1, 3, 4, 5, 6, 7, 8 and 9 - the nine digits excluding 2. We can repeat the above process to get each successive digit.

Essentially we're writing one million as the following sum

1000000 = (a1 x 9!) + (a2 x 8!) + ... + (a10 x 1)

As shown above, the index a1 is 2. That is, only two times 9! numbers fit perfectly within 1,000,000. So the first digit of the millionth number is the third digit in 0123456789. The index a2 is 6, so the second digit of the millionth number is the seventh digit of the remaining numbers 013456789, which is 7. The remaining digits can be found similarly. While finding the digits you have to be careful to ignore the digits that have been previously used. This is a permutation, so each digit appears exactly once.

The process is tedious, so here is some R code that will make it easier. This generalizes the solution to find the nth permutation of the numbers 0 to 9.

findperm <- function (n) {
  # Find the indices a1 - a10
  indices = c()
  for (i in 9:0) {
    index = 0
    while (factorial (i) < n) {
      n = n - factorial (i)
      index = index + 1
    }
    indices = c(indices, index)
  }
 
  # Use the indices to find the nth permutation
  input = 0:9                         # The list of numbers to permute
  output = c()
  for (j in 1:10) {
    output[j] = input[indices[j] + 1] # Move digit to output
    input = input[-(indices[j] + 1)]  # Remove the assigned digits from input
  }
  return (output)
}

That was straight-forward and a fun illustration of R's capabilities.

But you can do better. The strength of R lies in the wealth of user defined libraries and functions that can ease the implementation of tricky computation. For a simpler solution, try the lexicographicPermutation function in the library R.basic. Here is the entire solution.

library(R.basic)
lexicographicPermutation(c(0,1,2,3,4,5,6,7,8,9),999999)

The first solution illustrates that even tricky computation can be coded easily in R and the code is pretty readable. The second solution suggests that before writing your own code, it is a good idea to look for existing libraries that can help. Statistical computations can get complex and tricky. You can write your own k-means clustering algorithm but it is difficult getting all the edge cases correct. Rather than writing your own routine, look around and see if it has been written already. An expert does a better job writing such routines. And you can leverage their code and their expertise.

Project Euler in R: Problem 23

2012-01-15T15:56:00.000-08:00

I was just looking through the programming language statistics on Project Euler. It shows that only 7% of the problems have been solved in R, whereas 8% have been solved on any kind of spreadsheet. This is outrageous!

Let's look at the solution of problem 23 in R. Here is the statement of Project Euler's problem 23:

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.
A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.
As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Find proper divisors
First we write a function to find the proper divisors (that is divisors less than the number itself) of a number n.

divisor <- function (n) {
    divs <- c(1)
    i = 2
    lim = floor (sqrt(n))
 
    while (i <= lim) {
        if (n %% i == 0) {
          divs <- c(divs, i)
          if (n/i != i) { divs <- c(divs, n/i) }
        }
        i = i + 1
      }
    return (divs)
  }

Check if number is abundant
Next we create a simple function which checks whether a number n is abundant.

abundant <- function (n) {
    if (sum (divisor(n)) > n) return (TRUE) else return (FALSE)
  }

The solution
With the above two functions we have the tools we need to solve the main problem: finding the sum of all positive integers which can not be written as the sum of two abundant numbers.

All the numbers greater than 28,123 can be written as sum of two abundant numbers, so we only need to check numbers smaller than 28,123 for this property. The vector abunlist in the code below holds all abundant numbers starting from 12 to 28,123. With every new abundant number than we find, we create all possible two abundant number sums and store them in the vector sumno. The answer we're looking for is the sum of all numbers 1 to 28,123 except the ones in the vector sumno.

abunlist <- c(12)            # The smallest abundant number = 12
sumno <- c(24)               # The smallest abundant number sum = 12 + 12 = 24
 
for (i in 13:28123) {
  if (abundant(i)) {
    abunlist <- c(abunlist, i)                   # Latest abundant number = i
    tmp <- abunlist[(abunlist + i) <= 28123] + i   # New abundant sums <= 28123 using i
    sumno <-unique(c(sumno, tmp))                # Add to existing list
  }
}

This is certainly not the most efficient solution, but runs in approximately 25 seconds - well within the stated 1 minute goal.

Note: The code for this post was formatted in Pretty R at inside-R.org.

Generate UML Diagrams From Java Source

2012-01-11T20:31:00.000-08:00

I was navigating through a large Java project today, and I needed some source tools to help me visualize the massive class hierarchy. Looking on Google didn't produce anything obvious: people pointed to eUML2, which was difficult to install, and some tools didn't generate UML from existing code.

After a while of searching, I remembered the Doxygen utility which writes documentation from source code. It works on C,C++, and Java, among many other languages. While its diagrams might not be perfect, they were very helpful for C++ projects in the past.

So I decided to give it a shot. It worked out beautifully.

Here are the steps involved in generating UML diagrams.
First, you install doxygen (to parse the files) and graphviz (to write out PNG of graphs)

$ sudo apt-get install doxygen graphviz

Then, run doxygen to generate a config file.

$ cd <path-to-source>
$ doxygen -g

Now you have a config file called Doxyfile. Edit this to allow recursive searching, to look for java source, to generate call graphs and to generate pictures, and to generate UML style diagrams. Here are all the changes I made to this file.

FILE_PATTERNS     = *.java
RECURSIVE       = YES
HAVE_DOT        = YES
CALL_GRAPH       = YES
CALLER_GRAPH      = YES
DOT_GRAPH_MAX_NODES  = 500
UML_LOOK            = YES

Now, generate documentation with this command:

$ doxygen Doxyfile

To test this out for a blog post, I downloaded the source code to Azureus, a large Java-based project. Here is a graph from one of the files. The top right shows a close-up view of a tiny section of the picture. Even in this simple example, you can see how a zoomed-out view allows you to understand the complex structure.

Doxygen reads code written in C, C++, Java, and many other languages. So if you are in need of UML style diagrams to better understand a class hierarchy, give it a try. It is freely available, easy to install, and easy to use. In addition to class graphs, it can also make call graphs and caller graphs.

Entertainment comes from many activities

2012-01-09T00:00:00.000-08:00

I came across an interesting post by Roger Ebert about why movie revenue is dropping. He raises important points about high ticket prices and the poor theater experience. I agree with most of the post. Many years ago, I had written about the abysmal theater experience and it is nice to see that my concern is shared.

Movies are losing revenue because they are chasing ghosts. The days of mass theater watching is history. Even in India, people are comfortable renting or buying DVDs and watching the movie at home. The theater experience deserves much blame. Theaters function in a world of limited supply. Their glory days were when few movies were released and there was little alternate entertainment. Both assumptions are false today. Thanks to streaming video and increased access to foreign movies, I can watch Korean movies from 2011 if Hollywood produced poor movies. And I don't need to watch movies. I can play video games, watch short videos online, or spend my evening looking at cute kittens online.

Our definition of entertainment is changing. Movies are just a way of spending time having fun. We have many more ways of having fun. Traditional media likes their definition of "entertainment", which is "consuming content". This is a very narrow definition. It has never held true. Children's idea of enjoyment ranges from drawing to making a mess out of newspaper. Adults are similar.

Computers on the Internet are the ultimate tool. I write articles (like this one) and it entertains me. Others use Facebook or Google Plus to keep in touch with their friends and family. Still others contribute to Wikipedia or online forums. Each of these activities provides enjoyment for the person. Each of these are entertainment.

Some of the terminology from the movie industry indicates this bias. "Entertainment Online" and "Entertainment Weekly" are focused entirely on the movie and television industry. Entertainment on MSN is all about movie stars.

Even in the absence of online streaming videos and DVDs, the number of people watching movies would drop. There is a lot more stuff you can do on a computer. And sitting in an uncomfortable chair for ninety minutes staring at a screen is not always entertainment.

Learning Languages as a puzzle game

2012-01-08T00:00:00.000-08:00

I am interested in languages. I tried learning some Japanese when I was young. I gave up rather quickly. It might have been due to the lack of good books, or the lack of teachers. It might have been the lack of native Japanese speakers with whom I could practice my skills. My experience with Japanese instilled a love for learning new languages, and understanding a culture from their perspective, through their language.

A few months ago I started learning Mandarin Chinese. We found ourselves in Beijing, and we came across some great Chinese books lesson books for English speakers. These were useful in teaching characters and sentence construction in a very academic setting. Learning a language in this way is difficult. For one: your pronunciation is all wrong. For another, it is difficult to apply such academic learning to everyday speech.

Next, I tried using audio lessons only. These were a bit more helpful. They had correct pronunciation and useful everyday phrases. I did find that the lessons were geared more towards scoring women rather than real everyday phrases. Early lessons started with, "Where do you want to go to drink?", "Would you like to come to my place?" Useful stuff I'm sure, but not for a boring family man like me. A person like me needs directions to the hospital and the rest room. Further, the audio lessons made it difficult to distinguish between close syllables like 'ga' and 'ka'. You could easily mispronounce words and not realize it. Finally, you have no idea of written Chinese. This is a real limitation. Chinese is written in a strange and confusing way. Starting out with characters is much better than trying to learn them later. Building an initial comfort level helps if you travel.

Finally, we settled on Rosetta Stone (RS for short). RS teaches language in an interesting way. You don't see any of your native language written down. Concepts are introduced entirely through pictures, and you see Chinese to go along with the concepts. It is a strange feeling. You see a big ball and a small ball, and there are strange words. With time, you form the connection between the word and the concept. All without relying on the equivalent word in your native language. I was skeptical of this idea when a friend explained it to me. And RS costs an arm and a leg, which made me even more skeptical.

Luckily for me, I seem to learn Chinese with RS. I use RS as a puzzle game rather than language learning. It is fun to try to understand the game and get better. Now I'm on the final unit in Level One, I am surprised at how much Chinese I can understand. We have a few Chinese friends and I can understand bits of their conversation with their children. It is a great feeling.

Chinese is a devilishly hard language to learn. Right at the beginning, you start out learning pictographs (characters), tones in pronunciation, vocabulary, and grammar. If RS works for Chinese, I suspect it will work for Japanese too. Once I go through RS Mandarin lessons, I might just look at the RS Japanese lessons.

Fun fact for the day: The original rosetta stone was a stone which had three languages inscribed on it. The three languages had the same message. The discovery of this stone led to a breakthrough in deciphering Ancient Egyptian. It is ironic that the Rosetta Stone software teaches you a language by only showing you the language you wish to learn. Rosetta Stone never shows you a rosetta stone.

Project Euler in R: Problem 22

2012-01-07T15:55:00.000-08:00

I solve Project Euler problems for recreation. I am using the Statistical Language R to solve these. R is free for use and download, so I would recommend downloading it if you are interested in Statistical computation.
This is problem 22 from Project Euler:

Using names.txt, a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.
For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 x 53 = 49714.
What is the total of all the name scores in the file?

While this is an easy problem, its solution involves some nice R concepts. Let's go through solving this in R.

Reading free form text using scan()
The first order of business is to read the text file. The file names.txt is a single line of text, separated by commas:

"MARY","PATRICIA","LINDA","BARBARA", ...

The scan function reads free form text and stores each element in a vector. We specify that the input is character data separated by commas. That should do the trick, right?

nlist <- scan("names.txt", what= "", sep=",",)

Unfortunately, this does not work. After many minutes of scratching your head you'll find that one of the names in the file is 'NA'. This confuses the scan function since it is interpreted as the constant NA, or "Not Available" in R. This can be fixed by setting an na.strings argument in the scan function.

nlist <- scan("names.txt", what= "", sep=",", na.strings="")

Dictionaries / hashtables in R
Getting the alphabetical value of each character is easiest if it is stored in a hashtable somewhere. In R, named vectors can be used as hashtables. The traditional definition would go as follows:
dict = c("A" = 1, "B" = 2, ...)
While you can sit and write the entire dictionary by hand, you should avoid such repeated work. Here's a niftier definition using the names() function:

dict = 1:26
names(dict) = unlist(strsplit("ABCDEFGHIJKLMNOPQRSTUVWXYZ", ""))

This should be a trivial method to write in a C-style language where you can turn a character into an integer. R, however, has no internal ASCII table that I could find. If there is a simpler solution, please let me know.

Name scoring function
The scoring function gets the name as an input, pulls the score for each letter in the name and then adds up the letter scores.

score <- function (name) {
    return (sum(dict[unlist(strsplit(name, ""))]))
}

Calculating weighted scores
The vector of name scores is obtained by applying the score function defined above to each name in nlist. We use the sapply function, which gives a simplified vector output by default. The vector of weights is a sequence of numbers from 1 to the length of nlist. Multiply the two vectors to get the vector of weighted scores.

weighted.score = (1:length(nlist))*(sapply(nlist, score))

The full solution

nlist <- scan("names.txt", what= "", sep=",", na.strings="")
dict = 1:26
names(dict) = unlist(strsplit("ABCDEFGHIJKLMNOPQRSTUVWXYZ", ""))

score <- function (name) {
    return (sum(dict[unlist(strsplit(name, ""))]))
}

nlist <- sort(nlist)
weighted.score = (1:length(nlist))*(sapply(nlist, score)) 
sum(weighted.score)

This was an interesting problem to solve in R. It demonstrates the flexibility of R in reading and processing free form text. Trying to do a similar task in SAS would be hard.

Book Review: Foundation Trilogy by Asimov

2012-01-06T00:00:00.000-08:00

Want to start reading some good science fiction? Pick up the Foundation series by Isaac Asimov.

Asimov was a prolific writer. The foundation series comprises many books. The first three are called "Foundation", "Foundation and Empire" and "Second Foundation".

The books have an interesting premise: the behavior of individual humans is unpredictable, but the behavior of a large number of people can be collectively predicted. This is similar to the behavior of molecules of a gas, or movements of electrons. It is an interesting idea, and Asimov takes this concept and writes a kind of history for the Galactic Empire. In the introduction, Asimov says that he wanted to write a science fiction book, modeled on Gibbon's History of the Roman Empire.

The first three books are very interesting, though I did find my interest flagging in the third book. As expected, the first is the strongest. It talks of how the first Foundation was established, and how they made it through their turbulent years. The second book talks of how the Foundation faced very determined opposition, and how it escaped through it. The third talks of the second Foundation, whether it was indeed established, and what happened to it.

I don't read too much science fiction, and I am impatient when reading fiction. The foundation series were a great introduction to the genre. They are old now, but they are short and punchy. After reading the first book you'll have a pretty good idea whether you like the genre.

Science fiction is a popular genre among computer engineers and programmers. Imagining the future gives the author a lot of room to imagine a better future. The first Foundation books were published in 1952. Fifty years in the future, I was wondering how much of the world has changed. Looking back at old science fiction gives you an idea of what the older generations were hoping for.

The first three books are a great trilogy to start reading science fiction.

Book Review: The Elements of Computing Systems

2012-01-05T00:00:00.000-08:00

Want to really, truly understand how computers work? Read "The Elements of Computing Systems", by Noam Nisan and Shimon Schocken.

I studied Computer Science through graduate school. I love the field, and I own the texts that make this field fun. So I was surprised when this book came from nowhere. It promised to teach Computer Science completely through building an entire computer from the most basic pieces. After reading through it, and doing most of the exercises, I am convinced. This is the way to teach Computer Science. This way doesn't come easy, a high school student could go through it, but he would need a lot of exposure to Computing concepts in advance: flip-flops, how a VHDL-like language works, and programming. An undergraduate student could start on this book in this third year. It forms the textbook for a course at MIT. Lucky students.

The most important concept in Computer Science is abstraction: how a layer of abstraction can hide the underlying complexity. This is a difficult concept to grasp in practice, though you see it everywhere. A CPU is an abstraction layer: you program it in Assembly, and assume that it is a magical box that "understands" assembly. The CPU itself is built using transistors and logic gates. Computer Science is built on many abstractions: a memory, a processing unit, a lower-level language, a compiler, an operating system.

The Elements of Computing Systems is written in a very interesting way. It starts out with logic gates and a flip-flop as the basic unit. Using these, you create all the complexity of an adder, a register, a simple arithmetic unit. Using your creation, you create a full CPU. Using your CPU, you use an assembly language to program it. For your assembly language, you write a compiler, and then an operating system. This shows you the entire stack for a make-believe computer. The computer made is a simpler version of your laptop or desktop. Knowing one allows you to understand the more complex version.

This method of learning by doing is very powerful. This is the only way this understanding sticks in the minds of students. I've seen many of these topics covered in separate Computer Science coursework. But a single book tying the topics together has more impact.

This book isn't for everyone. You will need some experience with a C or Java like programming language, and perseverance. A smart high school student could tackle this with some help from his parents. I cannot think of a better way to learn computing.

Book Review: Three Cups of Deceit

2012-01-04T00:00:00.000-08:00

Want to know the true story behind Greg Mortenson? Read Jon Krakauer's short book, "Three Cups of Deceit", to find how Greg was able to fool millions of people.

Greg Mortenson is a person who runs the Central Asia Institute (CAI), where they collect charity money to construct schools in Afghanistan and Pakistan. His book, "Three Cups of Tea", has sold many copies, and is popular in the West. Greg claims that he stumbled into the town of Korphe, and was so moved by the poverty that he made a solemn vow to return and construct a school there. In his books, he recounts this journey, and the difficulty in building a school in such a remote place. He claims to have been apprehended by Taliban, and describes how he was released on the promise of building a school. His story is a miraculous tale of transforming hotbeds of fundamentalist religion by building schools.

It would be fantastic, if it were true. Jon Krakauer shows how much of Greg's story is a fabrication. Jon supports his claims with real proof. The most damning evidence is Greg's photograph alongside people whom Greg claimed were Taliban. In reality, they were his bodyguards through dangerous territory. Greg is shown holding an AK-47, and happily posing for the photograph with his tormentors. Jon also shows how other claims of success are completely hollow. Not only is the CAI building far fewer schools than it claims, but also the schools are mere buildings. There are no students because there are no teachers.

Jon Krakauer writes beautifully. From his book about Everest, "Into Thin Air", to the insightful account of Mormons, "Under the Banner of Heaven". Get this book now. It is a quick and captivating read.

We're done with the review. But there is a lingering feeling in my mind that something has been left unsaid.

A passage in Jon's book made me think deeply. On Page 68, Jon says how Greg was able to fool his audience.

It soothed the national conscience. Greg may have used smoke and mirrors to generate the hope he offered, but the illusion made people feel good about themselves, so nobody was in a hurry to look behind the curtain. Although it doesn't excuse his dishonesty, Mortenson was merely selling what the public was eager to buy.

This brilliant passage made me think of more than just Greg Morentson's fraud. People have an inherent need to believe in a feel-good story. We want to believe happy stories from hopeless areas because we are so eager for hope. This is as true in yogi-infested India as it is in the West. Many babas and yogis originate in rural India. We are eager for stories that show India in a good light. We want to believe the lies that India has a stronger spiritual connection with God than the rest of the world. We want to believe that India has all the mystic and spiritual men, the land that gave birth to five religions. In the absence of good news about the economy, or education, or political progress, we'll believe in far-fetched stories about how God favors Indians. In our eagerness to believe such stories, we are fooled by crooks posing as saints.

I am glad that Jon wrote a book exposing Greg Mortenson. But the real people I applaud are his audience. People realized that they were fooled, and they admitted this. Jon himself was a supporter of Greg's work, and had donated more than $77,000 of his own money to support the effort. It takes a lot of courage to investigate someone's fraud. But it takes a log more courage to admit that you have been fooled. I applaud the people for realizing their deceit, and having the strength to end the charade.

Indie Gaming

2012-01-03T00:00:00.001-08:00

I was going to bemoan the loss of innovative ideas in gaming. I had seen too many first person shooters, too many car racing games, and the same old Japanese Role Playing Games.

And then I met Indie Gaming, and I was blown away.

If you're new to the concept, as I was, Indie Gaming are games made by independent studios. Sometimes, these are very small teams of developers producing a single game. The large game studios want to chase millions of installs and the big blockbuster game. They do not deviate much from formulaic games, massive story-lines, insanely detailed graphics and big budgets. Independent games are made by smaller teams, so they have a limited story, small budgets. This limits what they can do: they cannot put millions of dollars into graphics. And as a result, they need something to attract audience away from well established games. They need to be innovative.

My introduction to Indie gaming was through the Humble Indie Bundle. The concept of an Indie bundle is as innovative as the games. Independent developers cannot get their games stocked in Walmart, and they don't have the traffic that can sustain Internet-only sales. As a result, they suffer from poor visibility and lackluster sales. So some independent game developers tried to offer a bundle of independent games at a price that the customer sets. Everyone chooses their own price. If you pay more than the mean donation amount, you also get some freebie games. The games are available for Windows, Mac, and Linux. The games have no Digital Rights Management, so you can confidently run the game on your computers in the future. They have no copy protection, so you can install the games on all your home computers. The independent games bundle concept has taken off. The sales are bigger and more prominent each year. The Humble Indie Bundle was the first bundle, and now there are many different types of bundles offered on the Internet.

This year, I purchased the Humble Indie Bundle #4, and it included the Indie Bundle #3, since my donation amount was larger than the average. I paid $10. I get eleven games with no DRM, and they all work on Linux: it is a bargain.

The games are refreshingly innovative. Night Sky is a 2D physics platformer, where you have to roll a ball around to progress through levels. Hammerfight is a game in which you battle with a floating hammer. Hammerfight uses only a mouse, and no buttons. Bit Trip Runner is a rhythm-based platformer, where your character has to jump and navigate through a level and your moves have to be synchronized to the background music.

Independent gaming are bringing fun back into gaming with their innovative games.

Book Review: Binary, by Michael Crichton

2012-01-02T00:00:00.000-08:00

Want to read good fiction? Read "Binary", by Michael Crichton, one of his best works that you've never heard of. Yes, that Michael Crichton.

The first book I read by Michael Crichton was an unknown book called "Binary" that none of my friends had heard about. I was in high school, and my father's friend had dropped this short book at our place. The author was John Lange, whom nobody had heard of. Inside, the book mentioned that the author was now revealed to be the great Michael Crichton, but I hadn't heard of Crichton either, so I wasn't expecting much.

The book starts with a gripping description of a heist. It grabs you, and pulls you in. The book is a thriller, of a plot involving dangerous weapons, and one man's race to stop it all. It is a short book, written very well.

I had harbored fond memories of this book. I had recommended it to many friends, knowing full well how difficult it was to obtain a copy. Recently, I received a copy of this book, and I sat down to read it. A short evening passed, and I was done. Despite having read it over a decade ago, I remembered most of the plot and many of the scenes. It was a thrilling book made punchier by the fact that I knew the story. I marveled at the plot and the excellent writing.

A fantastic novel, a thrilling plot. The ending isn't blockbuster by today's standards, and that is part of the lure. No superfluous nonsense, and no extra pages. A snappy story beautifully told.

Book Review: The Argumentative Indian

2012-01-01T00:00:00.000-08:00

Suffering from insomnia? Read "The Argumentative Indian", by Amartya Sen.

"The Argumentative Indian" is supposed to be observations about Indian culture and society. It might be that, but the language was so convoluted that any beauty or meaning was lost in the maze of words. Here is a sample passage, after which I decided to drop the book.

Yet, as is discussed in Essays 7, 8 and 15, general statements about India and Indians can be found throughout history, from the ancient days of Alexander the Great, of Megasthenes (author of the Indika, in the third century BCE), and of Apollonius of Tyana (an India-expert in the first century CE) to the 'medieval' days of Arab and Iranian visitors (who, like Alberuni, wrote so much about the land and the people of India), all the way to the Enlightenment and post-Enlightenment Europe (with heroic generalizations about India presented by Herder, Schelling, Schlegel and Schopenhauer, among many others).

Say what? If you were counting, that contained one sentence.

I'm sure the book contains some useful insight but the unconnected ideas and the lack of flow made the book unreadable. I would recommend V.S. Naipaul instead. Not only does he have insight into Indian culture and society, but the language is beautifully readable.

Book Review: "Secrets" by Daniel Ellsberg

2011-12-31T00:00:00.000-08:00

Do you always do the "right" thing, or do you take the path of least resistance? "Secrets", by Daniel Ellsberg reveals the life of a person who did the right thing.

Daniel Ellsberg is the person who leaked The Pentagon Papers, a secret study about the lessons learned during the Vietnam war. Leaking the study required a lot of personal courage. He was tried for acts of treason, though he was later acquitted. I find the lives of people like Daniel fascinating. They knew the path of least resistance, and yet they actively worked against it because of their conviction about the "right" thing to do. I wonder if I will have the strength that people like Daniel did.

Secrets starts of with the Gulf of Tonkin incident, and Daniel talks about his observations when he was posted in Vietnam. This section of the book was very riveting: Daniel has incisive observations about the war that he saw. Later, Daniel was a scholar for the RAND corporation, studying the Vietnam war. The Pentagon Papers are the result of this study. Daniel talks about his experience with the secrecy in RAND and the Department of Defense.

I found Daniel's observation about the effect of access to secret clearance beautifully insightful. He warned Kissinger what the access to secret information will do. (Page 237 in the paperback version). I'll paraphrase Daniel's commentary:

At first, you'll feel exhilarated by the volume and extent of information. Then, you'll feel like a fool for having analyzed these topics without even knowing that these secret documents existed. Then, you'll be aware of others who don't have this information, and you'll think that these people are fools. Finally, you'll become incapable of learning from people, because most people don't have access to these secret documents. No matter how great their experience compared to yours, you'll be incapable of learning from them.

This passage should be read in the original. It is a beautifully crisp understanding of the impact of secret clearances, and power in general.

Daniel talks about his thought-process, and why he decided to release the confidential study. He talks about the impact of the study, and the impact to his freedom. It makes a very interesting read.

It reads like a war thriller, but it carries deep lessons about how difficult it is to do the right thing.

Book Review: Autobiography of a Yogi

2011-12-30T00:00:00.001-08:00

Why not read some third-grade fiction this weekend? Pick up a copy of "Autobiography of a Yoga" by Paramhansa Yogananda.

The book is about a "yogi", a person who has attained enlightenment of some sort. However, the book reads like a supernatural fairy tale. The very first chapter started off with this hoot of a passage.

The helpless humiliations of infancy are not banished from my mind. I was resentfully conscious of not being able to walk or express myself freely.... Psychological ferment and my unresponsive body brought me to many obstinate crying-spells.

The author claims that he was fully conscious of his infancy, and that he cried because he couldn't express himself. This is pretty damn hard to believe. Of course, the author is gone now, and no supporting evidence can be obtained. From what we know about brain development, it is difficult to believe that any child could have such capability. A few sentences before that, he claims that in his previous birth he was a Himalayan yogi. You would think such a highly perceptive creature would wait for the infancy days to get over before trying to talk.

A few pages later, we get another passage tailor-made for the gullible audience:

An immense flash of light at once manifested to my inward gaze. Diving shapes of saints, sitting in meditating posture in mountain caves, formed like miniature cinema pictures on the large screen of radiance within my forehead.
"Who are you", I spoke aloud
"We are the Himalayan yogis." The celestial response is difficult to describe; my heart was thrilled.
"Ah, I long to go to the Himalayas and become like you!" The vision vanished, but silvery beams expanded in ever-widening circles to infinity.
"What is this wondrous glow"
"I am Iswara, I am Light." The voice was as murmuring clouds.
"I want to be one with Thee!"

It is as poorly written as it is imagined. In the first chapter, he had recognized himself as a Himalayan yogi from a previous birth, and now that he sees a few people more, he needs them to positively identify themselves. The book is filled with extravagant recounting of supernatural events. Looks like the author lived in a charmed world, only dimly aware of laws of Physics. The miracles themselves are difficult to take seriously. Extraordinary claims require extraordinary proof, none of which is provided by the book. And they aren't even written in a funny or engaging manner. They're stated with a nonchalance that suggests that this is commonplace. Even if this were a work of fiction I'd pass it by.

The lesson from the book is that you are a yogi if unnatural stuff happens to you. If it doesn't, tough luck. Maybe next birth pal. Wait this life out. Even as a spiritual text the book is abysmal. It has no lesson about how to live a good life, or how to achieve peace. A much more concise and beautiful lesson is the one-liner from Mae West, "You only live once, but if you do it right, once is enough."

I am amused by "Autobiography of a Yogi". It comes highly recommended from seemingly sane people. People swear by it, and say that it changed their life. You have to be very desperate for meaning if this book gives you any. It is like finding deep meaning in "Baa Baa Black Sheep".

Due to the poorly imagined plot, and the haphazard story-line, I didn't read too far. If someone could point out passages that they thought were spiritually enlightening, I'd be happy to revise my opinion.

(In case you are offended by this: Calm down. If this guy is half as divine as he claims, he won't mind it.)

Book Review: The Golden Gate by Vikram Seth

2011-12-29T00:00:00.000-08:00

Want to read a moving novel in sonnets? Grab a copy of "The Golden Gate", by Vikram Seth.

I am prejudiced against "popular" Indian authors. Past experiences have made me critical towards them, especially if their fiction is popular in the West. I don't know what I was thinking when I picked up "The Golden Gate" by Vikram Seth. I had heard of Vikram Seth, but I had not read anything by him.

The Golden Gate is a story about a few friends, and a few years of their life. The book is written entirely in verse, which took me by surprise. It has been a few years since I read verse. I need not have worried, the Golden Gate is a great way to start reading verse again. It is easy to read, and many passages in it are moving, and thought provoking. The book starts out with a person who should be happy at his success, but he feels lonely. It follows his journey, and tells you about his friends, and their lives. Written during the turbulent period of the Vietnam era, it raises interesting questions about life, ambition, following one's dreams, and what it takes to be happy and at peace.

The locations are all from the San Francisco Bay Area: San Francisco, San Jose, Marin county, and introduce the reader to the joy of living in this wonderful part of the world. It makes the reader appreciate the world we live in, and our friends.

I started out skeptical, and ended up enjoying the book immensely. I was sad when it ended, Vikram had done such a fine job of introducing the characters that they felt like friends.

Get the book, and enter the charming world of Vikram Seth's verse.

Image courtesy Wikipedia.

Book Review: Spice Route

2011-12-28T00:00:00.000-08:00

Want to know why bay leaves were once more expensive than saffron? Read "The Spice Route", by John Keay.

The book is a history of the Spice Route, and the general quest of Europeans to find exotic aromas and flavors. It goes through time, showing how the trade route was a long chain of sea and overland routes through the Middle Ages. Various spices were harvested in South East Asia: India, Indonesia, and other countries. These were traded by Arabian traders, who brought them to the Middle East. Here, they were traded to others who took them to the Mediterranean.

The history of this route is fascinating: spices were a big motivation for the European powers to expand East and West. Many campaigns were waged: trying all the routes, trying all ways to gain more access. The merchants from Holland successfully bypassed the Mediterranean, and the Spanish and Portuguese managed to go in different directions: the Spanish went towards the New World, while the Portuguese went East towards Goa and Japan. It is difficult to transport a person to that time, where travel was wretched and dangerous, but John does a fine job in giving the reader a flavor of that world.

The spice route led to a colonization of the world, as the European powers carved up the commercial world among themselves. It is instructive to read this history, and learn about how a new improvement fundamentally changes the field.

This book will shed a light into the colonial era, and will take the reader back through time. It made me look at my spice cabinet very differently, and treat my bay leaves with a lot more respect.

Book Review: H20 A Biography

2011-12-27T00:00:00.000-08:00

Looking for some good science writing about a common topic? Pick up Philip Ball's, "H20, A Biography".

Philip writes about water from a few different angles. It talks about how water originated in the Universe. The book talks about the origin of the Universe (Big Bang, not 6000 years), and how planets were formed. Then it goes into how Earth might have got its water. We take water for granted, but many planets have little or no water at all. If we believe that intelligent life requires water, we need to understand how water could have come around in the first place. It is a very strange set of circumstances that caused Earth to get water and retain it. Many planets might have had water, but they lost it over time. Astronomers and Physicists have looked at Venus and Mars and tried to reason about how Earth might have had water. The Science behind this is quite beautiful and involved, and it helps that Philip explains it so well.

Next, Philip explains how humans discovered water. This is the most interesting part of the book, the history of Science. Ancients thought that water was an element, and they did not know that ice, water and steam are the same compound. This led to a long set of mistakes and it shaped the thinking of early chemists, leading them astray. I found this section remarkable. How does one realize what water contains? Philip lists all the major Physics and Chemistry milestones that allowed humans to recognize that water is a compound of hydrogen and oxygen. The book also talks of how humans realized that ice, water and steam are the same compound. The mis-steps are very instructive. They lead to a better understanding of how science proceeds and how mistakes are corrected. Early chemists thought that when something is burned, it gives up phlogiston (rather than taking up oxygen). This was an easy mistake, given the instruments of the time. Early chemistry made quick advances when people showed that burning was a process of oxidation, combining chemically with oxygen. (Similar mistakes were made in early experiments with electricity. Electricity was through to flow from the positive lead to the negative lead, when the actual flow is in the opposite direction. Thus, electrons now have a negative charge by convention.)

In the third section, the book talks about the behavior of water in cells, and the anomalous behavior of water under various circumstances: low temperature, high pressure, low pressure, presence of solid bodies. I didn't know much of it, though I confess that I wasn't able to retain much of this information. It was just too dense for me in parts, and I had to skim through. The book ends with drinking water, and explains why the lack of drinking water is one of the biggest problems facing humanity.

The book is a beautiful history of early chemistry and various aspects of water. It does get technical at times explaining in quite some detail how certain things work. It is best to skim such sections and return to them later. A majority of the book is an easy and insightful read.

Book Review: Seeing Voices

2011-12-26T08:05:00.000-08:00

Oliver Sacks is a neurologist of some renown. He has written some fascinating books on the working of the mind: the most famous are "The Man Who Mistook His Wife for a Hat", and "Musicophilia". "Seeing Voices" is a short book about the deaf.

When I first picked up the book, I wondered if brain development for deaf people is very different from that of hearing people. Oliver's book lists the various ways in which language development suffers if a deaf person isn't allowed to sign naturally, or if he doesn't have access to other people who sign. I didn't know much about sign language before reading the book. Sign language isn't a simple translation of English or Hindi into gestures. Rather, it has its own idioms, its own grammar. So sign has a notion of poetry and of puns.

Oliver lists various cases of deaf people whose parents did not sign. When these children grew up and finally encountered signing, a world of language opened up to them. This process is beautifully described, and provides valuable insights into the working of the language part of the brain. For example, without language, there was no way to describe time: today versus tomorrow blend in if there is no way to describe them.

There are also examples of a few hearing individuals whose language development has been artificially suppressed. These examples showed how both hearing and non-hearing individuals pick up language in similar manner.

"Seeing Voices" is a great book to read if you have a small child in the house. Children learn sign language faster than spoken language. Spoken language requires a complicated co-ordination of the vocal chords, and these develop rather late in children. Sign language requires arm motion which children acquire rather early. Based on this, many hearing parents teach their children sign language. From an early age, the child learns how to express himself: pain, hunger, boredom, and a need for mommy, daddy, or sibling. This allows for a limited communication between parent and child, removing frustrations on both ends.

After reading this book, I could think of many friends who would love to read this. You don't need to be interested in neuroscience, language development, child development, or the world of the deaf to love this book. This short book makes you aware of language, and gives you much to consider about.

Book Review: The Man Who Knew Infinity

2011-12-25T18:21:00.000-08:00

Srinivas Ramanujan was a brilliant Indian mathematician who made seminal contributions to Number Theory and the theory of continued fractions. Robert Kanigel's book, "The Man Who Knew Infinity" is a biography of Ramanujan.

The book talks about Ramanujan's life in quite some detail. Robert has provided a lot of color by traveling to the places involved, and deeply researching Ramanujan's life. The book has photographs of the places and maps of areas, making it easy to identify with the story. The biography is well balanced and impartial. If this was all the book contained, it would already be a worthy read.

What I found most interesting was the associated commentary on Indian society, values and the education system. Ramanujan was ignored by the Indian education system, largely because he refused to conform to its requirements. Ramanujan showed an early brilliance in Mathematics. But the system didn't care for exceptional performance in one field. Due to the inflexibility of the system, the talent of a brilliant mathematician was wasted. Having suffered through the Indian education system, I found the passages revealing. Even back in Ramanujan's day, the system was inflexible and idiotic. Many people recognized the inflexibility of the system, its arbitrary outcome, and the ill effect on genuine talent.

How much part did Indian society and customs play in Ramanujan's downfall? Ramanujan refused to alter his diet in cold, cloudy England. As a result, he got very little vitamin D, and suffered poor health. This is a problem that persists to this day: Indians who firmly adhere to a restricted diet suffer from problems in countries where an Indian diet is unsuitable. Ramanujan's wife was poorly treated by his mother, and this poor treatment led to misunderstanding and stress in Ramanujan's life. Would the outcome have been different if the Indian arranged marriage was not as stifling?

Ramanujan's life is full of questions. It makes me sad at the outcome. But more importantly, it makes me wonder.

Would a Ramanujan be possible today? Could a lower middle class boy with no talent for anything other than Mathematics be recognized as a genius? Could he even reach a point where he could seek collaboration or patronage from Western mathematicians?

It is a very sad tale, though one I think every Indian student should know. Indian students yearn for exposure to foreign education and worldwide recognition. This is one example of a person who got both, and yet he had a sad and lonely life. The outcome could have been so much different. Ramanujan was as good as Euler or a Gauss, according to people who worked with him. And yet his talent was squandered away. An early death, a lonely life full of struggle. And Ramanujan was lucky. Today, he probably would have no hope of success.

Image courtesy Wikipedia.

Book Review: The Male Brain & The Female Brain

2011-12-19T00:00:00.000-08:00

Rather than waste your time with pop-culture books about men and women, how about read books with real science and insight this holiday season?

This is a review of two delightful books called "The Female Brain" and "The Male Brain" written by Louann Brizendine. Dr. Brizendine is a professor at UC San Francisco. Both books talk about the peculiarities of each brain from a scientific viewpoint. The books are scientifically accurate, and are accessible to a layperson with no background in neurology.

The books contain a lot of insight about the behavior of both men and women. For example, The Female Brain talks about how women's brain is highly geared towards social connections. It provides many examples to demonstrate this, and talks about the development of a female brain from a newborn to adult and to a mature brain. Along the way, you see the various changes in the brain. A lot of behavior changes accompany the development of the brain. This book made me understand the motivation behind the baffling behavior of friends and relatives.

The Female Brain was the earlier book. Recently, Dr. Brizendine wrote The Male Brain. The second book is as interesting and as revealing as the first. It talks of the development of the male brain through the years. There are many ways in which the adult male brain is different from the teenage male brain. Reading about the male brain allowed me to better understand how I will change as I grow older. It also allowed me to understand male toddlers behavior.

Both books are a quick read, they make cutting-edge scientific research accessible to everyone. This is scientific writing at its best.

Book Review: Kashmir, The Wounded Valley

2011-10-12T09:02:00.000-07:00

Many years ago, Neha and I were walking around Santa Rosa in Northern California. We came across a used bookstore where the owner was listening to some good blues, and improvising with a harmonica. It was a perfect setting. We entered the store and found some very interesting books. Some of these books have been impossible to find elsewhere.

Today's review is about one book from that store. The book is "Kashmir, The Wounded Valley", by Ajit Bhattacharjea.

The book is a condensed history of the Kashmir valley. It starts around 700AD, when authoritative written record begins, and continues on till 1992. It is an insightful read. Written in an easy style, Ajit takes the reader through time in Kashmir's history. Entirely factual, and entirely gripping, the book has the pull of a crime thriller rather than the yawn of history books. It is even more chilling when you realize that all the events occurred. And when you turn to the evening news, you realize that we are still living with the repercussions.

Two things struck me when reading the book.

The valley has had mismanagement and cruel monarchs. Few rulers have cared for the well-being of their people. Dynasties follow a predictable pattern. The first monarch in a dynasty is an aggressive conqueror, or a cunning statesman. The second is a benevolent and able leader. Successive leaders are selfish, greedy, and insensitive to the needs of the people. Few monarchs have focused on improving education or living conditions. As a result, the people have suffered greatly and their lot has worsened over the years. Even before the British Raj, the condition of the people was miserable.
The people are surprisingly resilient, and a little gullible. Kashmiris have a liberal outlook towards life. Most Kashmiris converted from Hinduism and Buddhism to Islam willingly. The benevolent influence of liberal sufis struck a chord among the liberal Kashmiris. Culture played a bigger role than religion in their life. All through the turmoil of Mughal India, Kashmir had peaceful co-existence among Hindus and Muslims. The gullibility of the people leads to their willingness to be ruled and oppressed. And it shows in the lack of popular uprising to demand better rights and better living conditions. They supported outsiders to overthrow the existing monarch, only to find the new boss was same as the old boss. Even when democracy was at hand, they did not demand their rights aggressively. As a result, leaders turned into tyrants, ignoring the needs of the people and holding Kashmir back from fully awakening.

The book also explains how Kashmir became a contentious issue between India and Pakistan, and the mistakes that led us there. The book is impartial: it points out mistakes on all sides. The ruler of Kashmir, Hari Singh, refused to make a concrete decision on joining either side. He had hopes of staying independent despite the impossibility of such an arrangement for Kashmir. Rulers of India and Pakistan refused to give the Kashmir issue the importance it deserved. And as we have seen countless times before, administrative incompetence and widespread corruption made a bad situation worse. Heavy-handed actions by the central government, corruption by well-known people, and a lack of respect for the people's needs alienated an entire state. The people started out amicable to India, eager to strengthen ties with the land of Nehru and Gandhi. Over years, all good will was squandered, culminating in the excesses of the armed forces. Warm friends turned into bitter enemies.

A small bruise festered into an open sore, leading to much pain and hardship for both countries for over fifty years. Over time, that pain has spread through both countries. It has led to war and terrorism.

This book should be a required reading for every Indian and Pakistani student. It has valuable lessons for future statesmen. Due to mortal follies, a place with heavenly beauty has been turned into a dark hell. Having deteriorated so far, it is debatable if the situation will ever improve. If a workable remedy exists, knowing how we got into this mess is the first step towards it.

The State of Free Software Today: What We Need to Do

2011-10-10T22:37:00.000-07:00

Richard Stallman (popularly called RMS) wrote an eulogy to Steve Jobs recently. It was widely reported due to its angry tone. In summary, RMS was happy that Steve Jobs is dead because Jobs personifies the "walled garden" approach to computing. In the Free Software camp, nothing is more abhorrent than the walled garden approach. Free software is all about giving people a lot of freedom: including the full source code of the software, and the freedom to modify it and copy it. The walled garden approach is all about tight control: not just of the source code but also the development and the overall experience.

It is easy for me to pick sides: I have been a free software enthusiast since 1995, when my friend and I chanced upon something called Linux. I spent many hours playing with Linux, and have used it as my primary system for well over a decade. In addition to Linux, I spend all my time in free application software: Firefox, Chrome, Blender, GIMP, R, Eclipse, Emacs, Arduino, ... The list goes on.

I abhor the walled garden approach. It is damaging to my livelihood as a software engineer if I cannot learn from a system or modify it. I enjoy programming and have tinkered with most systems I own. My tinkering was lousy and inconsequential, but I enjoyed it. And I learned a lot by poking inside them.

It is easy to identify with RMS' criticism of Steve Jobs. It is easy to rally people when you demonize someone. But free software doesn't need this kind of rallying.

I think RMS is wrong.

The Lure of Free Software
Free software is compelling. Many programs like Blender, Eclipse, Emacs are the best in their class. They are exceptional tools. I write better in Emacs than any other editor. Emacs is an extension of my mind: it is a supremely capable editor. My other editor, vim, is equally good. It is beautiful to watch an expert use emacs or vi: the software makes them insanely productive. Free software has done exceptionally well in technical areas like Statistics (R), 3D modelling (Blender), web serving (Apache), microcontroller hackery (Arduino), development tools (Eclipse, GCC, emacs/vi, ..) In these areas, non-free tools are at a significant disadvantage. Who would bother using some souped-up microcontroller tool when Arduino works so beautifully? Who would bother with a strange new Statistical language, now that you can download, install and use R right away? And if you have a newbie question with R, the wizard Peter Dalgaard himself replies to questions! That is how awesome the community is. The software is great, the community is knowledgeable and helpful, and you can read the source code to learn more. It doesn't get better than that.

With software like that, you don't need to yell about the virtues of free software and the evils of the walled garden. The software stands on its own merit. And it continues to attract people like me who care about the freedom.

The free software world has produced some exceptional non-technical software: Firefox and Chrome as browsers, VLC as a media player. But in the non-technical area, free software has lagged behind. Ubuntu is making a gorgeous operating system that my mother can use. But companies like Canonical are the exception rather than the norm.

The Lure of the Walled Garden
In recent past, Apple has gained a large following. Their products like the iPhone and the iPad are phenomenally popular. People are buying these products because of the superior user interface, and the ease of use. The user interface really is the killer feature. Free software advocates might dislike the walled garden approach, but we cannot deny that Apple devotes extraordinary resources to getting an excellent user interface. The first bite of the Apple is bewitchingly delicious. The interface sells.

For a long time, the free software world has been blind to the needs of the "common" user. We have aimed at the technical audience, and have ignored the needs of the vast majority of computer users: our parents, our grandparents, our friends. We justified this stance because there were limited developers, and we needed to get our own house in order. We needed development tools, drivers for technical products, technical software. Developers were more interested in scratching their own itches, writing programs that satisfied their needs. Nobody can be blamed for the situation we are in. Every free software developer has been working hard, quite often without pay. Asking a Statistics programmer to write a cute game would be a disaster.

In the meanwhile, a walled garden has appeared with exceptional usability, even if it has a limited set of features.

It is a testimony to good usability that people are willing to enter the walled garden. Many people don't care about the freedom. People who do care continue to enter the walled garden despite their loss of freedom. It is a question of convenience, and people choose their battles carefully.

The way forward
We have many glimmers of hope. Look at Firefox or Chrome. Both are free software, and both wrested browser market share from Internet Explorer (IE). IE was never an explicit walled garden, but it did curtail freedoms: it ran on specific platforms, it fragmented the web with its own extensions. For a long time, the lack of a good browser was the chief hurdle for free software users. We couldn't use IE, and nothing else was good enough. Navigator was barely usable.

Then came Firefox: it was a compelling browser. Firefox was fast, it ran on every system, it was more secure. Most importantly, it was beautiful. Compared to Netscape Navigator and IE: man, was it gorgeous! Put the navigation buttons and URL bar along the menu bar, and you had one pretty interface. Chrome went one step ahead: it is an exceptional browser. It is fast, it is pretty, it is secure. Oh, and the source is available. People who don't care about freedom of software use it because it is good. And people who care about freedom can download its source code.

Something similar is happening with Android now. Android's source code is available. But that's not why millions flock to buy the Nexus-S or the Droid. They want the system because it is excellent. With Gingerbread, the Android system looks beautiful. With the next release, I'm sure it will look even better. Now that it is comparable on features, it is polishing its usability.

That is the way forward: to make exceptional software. Make the best damn system in the world. Make it gorgeous, fast, cheap, reliable, rugged, stable. And then release the source code. Find opportunities like the Mozilla Foundation did with Firefox. Like Canonical did with Ubuntu. Or like Google did with Chrome, Chrome OS and Android.

Users are being charmed by the the usability of the software that Steve Jobs provided. Provide the same usability with the freedom. The walled garden will disappear by itself.

Indian Universities are no longer world class

2011-10-09T16:28:00.000-07:00

A recent survey carried out by the Times Higher Education magazine ranked all the universities in the world. Sadly, Indian universities don't figure too highly. The best Indian university in that list is IIT Bombay. Its ranking is 301-350: no specific rank is given. One thing is for sure, IIT Bombay is worse than many small universities few people have heard about, like places in Turkey and Brazil.

Many years ago, I had written about how the IITs are not world class. When you venture out of India, you realize how bad they are. That article got a lot of pageviews, and lots of comments. Many IIT students wrote to say how deluded I was, in their own special way. Eat humble pie, my friends.

The Times Higher Education survey is quite comprehensive. You can look at the methodology details here. In short, they asked industry and education leaders for their views of universities. Universities were graded along a variety of factors: the number of citations for their papers, the amount of research funding, the impact of its research on industry, the teaching environment. The study looks solid: all income has been adjusted for purchasing power parity, so poor countries are not penalized for their lower cost of living. Also, there is a normalization across disciplines, so sciences where overall publication frequency is lower are not penalized for having lesser research output. The weight for research output is 30%, which is perhaps too low. They have an iPhone application which allows you to change the weights and see the impact on the ranking.

I don't have access to their raw data, but from reading about the study, their method looks sound. Ranking an institution is a difficult task, and this study is probably the most precise answer we have right now. A better study could look at the impact of graduates from the universities, or the difference between the capability of students with and without the education: thereby measuring the impact of the institution itself. Alas, such controlled studies are difficult to come by.

So where does this leave us? This leaves us in the sorry state of admitting that Indian educational institutions are really not that good. The Chinese are far ahead of us. The prestigious Tsinghua University in China is at position 71, ranking near well known universities Rice and Vanderbilt, both in the US. Among Asian countries, Japan, Hong Kong, and Singapore all fare very well. In fact, the top Asian universities are dominated by Japan, Hong Kong, China, Singapore, and Korea, and now the reasons are somewhat clearer. . These countries have made investments in education, and the results speak for themselves. Even between Brazil, Russia, and China, India spends the least amount of money on education, per student.

Admitting that our educational institutions have fallen behind is the first step. Only after we admit the problem can we find ways to rectify the situation.

Learning a new software: Blender

2011-10-08T13:00:00.000-07:00

Blender is a 3D design software. It is a complete tool, allowing you to create entire worlds in 3D, modelling, meshing, applying texture, and animating the world.

Here is an example of what Blender can do. This movie was created completely in Blender.

Isn't that impressive? What is more impressive is that Blender is available for free, you can download it and install it right now (Windows/Mac/Linux). And if you want to make your own movie based on the characters behind Sintel, you can download all the art and characters at the Sintel website. This level of sharing is refreshing: it allows new graphics designers to learn a complex tool, and be able to look behind the scenes of a very complex project.

Blender has a beautiful UI, though it looks very complicated initially. When you load it up the first time, the number of buttons and controls is overwhelming. This is what the default Blender 2.5 UI looks like. There is a small cube placed at the center of the viewport, and many properties and control widgets are open. Once you learn a few Blender principles, you find that the UI is clearly arranged, and every control is in the perfect place. As with any good tool, the tool itself vanishes pretty quickly. Within hours of learning Blender, you focus on the 3D modeling activity rather than the Blender tool.

Learning Blender
I tried learning how to use Blender using a book. It is hard to explain the various UI elements using written words. It is even harder to describe the 3D world you are creating using just words. The best book I have found till now is called Blender for Dummies. It requires no previous knowledge, and is an excellent resource to begin modelling simple meshes in Blender. It covers Blender 2.5.

In case you want to start while your book is on its way, here are a list of online resources. I list Blender 2.5 resources only. The Blender interface changed a lot between 2.4 and 2.5. If you are starting out, it is best to start with 2.5 directly.

Getting Started with Blender: This is a set of seven video tutorials. They are short and cover the very basics of using Blender. You can watch all seven within an hour and you will have a great idea of the Blender UI and basic features.
Neal Hirsig's blender learning course: More than a collection of isolated tutorials, Neal has created a comprehensive learning course. You can download all videos to your machine and follow along with Neal as he patiently explains every feature of Blender. Neal's explanatory style is impeccable: it is a pleasure to follow along and learn. You can downloads all these videos from sagefans.net.
A collection of tutorials at Blenderlinks: Finally, when you have mastered the UI, you can focus on a specific topic by looking through the links at Blenderlinks. The videos are created by many contributors, so the videos differ in sound quality and expository style. But if you want to learn a single topic, the videos at cgcookie linked from Blenderlinks often provide the perfect recipe.

Blender is a powerful software, and it compares well against software which costs thousands of dollars. With a little bit of effort, you can learn how to create an entire 3D world inside your computer. It is scriptable in Python, which allows you to use Blender 3D models from an automated system. Give Blender a try, and see what you think!

Book Review: A Contract With God

2011-10-07T15:02:00.000-07:00

I came across a copy of Will Eisner's, "A Contract With God" Trilogy at my library. This includes three books, "A Contract With God", "A Life Force", and "Dropsie Avenue". I had heard vaguely of this book, so I picked it up. I was expecting a good graphic novel.

I wasn't expecting a book of this lyrical depth and insight into human behavior.

These graphic novels are about life in a poor New York neighborhood starting near the Depression and going to more recent times. It describes the life of poor migrants to America; their dreams, their lives, and how they escape the squalor of their world.

I am struck by the depth and force of some of the stories. A few stories in the first book were very hard-hitting and thought provoking. I stopped reading after a few stories because there was so much to mull about. It is a rare book which has this level of insight coupled with such beautiful art.

These books are not for children, though they may be okay for teenagers. They have plentiful sex and nudity, putting the "graphic" back in "graphic novel". Use your own discretion if you have children or teenagers around or are squeamish about sex.

The book can be ordered from online stores. Amazon has a hardbound copy for $20 which is a steal.

When Boston Brahmins were hoping that American classical would improve upon European Continental music, Jazz took the world by surprise. In much the same way, Will Eisner's graphic novel is the epitome of American graphic art. Completely out of the blue, it defined the graphic novel genre and gave readers and future novelists something original and beautiful.

Google Plus versus online news sites (like Reddit)

2011-10-06T07:44:00.000-07:00

Google Plus is a new social networking site. If you haven't heard about it, it is similar to other social networking sites like Orkut or Facebook.

There has been a lot of discussion about how Google Plus resembles Facebook. Indeed, you can search the Internet for the two names and there are countless comparisons. I think this misses a broader point.

Once I started using Google Plus, I haven't checked Reddit.

In case you don't know, reddit is a popular news website. Reddit started out as a small startup with mostly programming topics. The stories were interesting and it had an impressive signal to noise ratio due to the self-selected audience. For a while, reddit was even better than Slashdot, another popular geek news website.

Over time, reddit descended into cheeky cuteness, pictures, and pointless articles. At some point, I stopped reading the reddit main page, and started reading the programming subreddit. Even that is becoming irrelevant. At around this time, Google Plus came in.

Social Networking connects me to virtual cows
I'm very skeptical about social networking. Very, very skeptical. Social networking puts me in touch with a wide number of acquaintances, where the level of interaction is shallow at best. I dislike shallow interactions, and so I avoid checking social networking sites. I check these sites roughly once every quarter. The quality of posts is between pointless and annoying. Things really went down the toilet when Facebook allowed games to post updates. Suddenly, you could see how some long-forgotten acquaintance of yours had just obtained a virtual cow in some online farm simulation. Do you want to make a farm next to his? No thanks. If I had hours to waste and wanted to simulate reality, I would duel in the sky.

So the previous social networking stuff was a total chore. I would check it infrequently, and post self-promotional content: links to my articles when I was happy with one.

It took a lot of prodding from my friends to try out Google Plus. You know who you are: thanks!

Google Plus connects me to Peter Norvig
When Google Plus came in, it allowed me to subscribe to people who weren't friends: Tim O'Reilly, or Peter Norvig. These people have insightful articles to post or reshare. They are interesting to me, and are relevant to my area of work. Suddenly, Google Plus had much higher value content than Reddit. It was the Reddit front page, all over again. Except this time, it wasn't fluffykitten13, but Peter Norvig himself. Woohoo! The articles were interesting, topical, timely.

I doubt Google Plus would descend into the cutesy pointlessness of Reddit anytime soon. I doubt Peter Norvig would switch completely to posting lolcats. Actually, knowing Peter, he probably would post lolcats to prove someone wrong.

And that's the beauty of Google Plus, the articles are linked to the poster's reputation. I wouldn't post lolcat pictures: partly because I have better things to do, and partly because my friends would think me crazy if I did. People are free to engage in their interest of choice: it is like giving everyone their own reddit-like site. Unlike blogs, the content is usually smaller. You can subscribe to many people, and find related content very easily. Like blogs, it is personally generated content. The content is frequently updated, topical, personal, and recent. The site layout is great and no page is missing.

Google Plus isn't perfect. I still read Slashdot due to reasonable editorial filter and good comment moderation. Google Plus comments on highly visible posts are quite useless and spammy. But overall, Google Plus has given me a high signal news source.

The complicated Indian negotiation ritual: why decisions take much longer

2011-10-05T16:39:00.000-07:00

In traditional Indian conversation, you are never supposed to express willingness or displeasure in a straightforward manner. So when you are having lunch with extended family, you are not supposed to clearly express that the daal was excellent and you would like some more. A similar dance is played out when arriving at agreement of any sort. The standard Indian conversation hovers on generalities with no preference clearly outlined. Most conversations are elaborate dances: both sides express a little more of their preference without clearly saying what they would like. Here is an example of a couple called Harry and Sally at a restaurant:

Harry: What would you like to eat?
Sally: Anything is good.
(At this point, you would think that they're in agreement. Well, you are wrong. Listen to the remaining conversation.)

Harry: Would fish curry be good?
Sally: Yeah, that's ok. Does this restaurant make good lamb curry, I wonder?

Harry: I guess, I haven't tried it. But I hear everything here is good. Would you like lamb?
Sally: Lamb is good too, I haven't had it for a while now.

Harry: Would you like to try their lamb curry?
Sally: That sounds good. What else is on their menu?

Harry: They have a lot of things. Their vegetable selection is also great. The pav bhaji looks enticing.
Sally: Yeah, pav bhaji sounds interesting. What other vegetables do they have?

Harry: Their cauliflower curry gets good reviews. I tried it once. It is much like the fish curry, but the fish curry is clearly better. Weren't you craving fish yesterday?
Sally: Yeah, but I wonder if their preparation of fish is good. You can get that if it is their best dish.

Harry: No, fish isn't their best dish, they make everything well. The cauliflower is also cooked perfectly.
Sally: I see. Both sound great. You know, just the other day I was telling my mom that it is difficult to make good okra, unless it is fresh. Did you know that?

Harry: No, I didn't know that. But that makes sense. Okra goes limp when it is old.
Sally: I wonder how this restaurant makes okra.

Harry: I wonder too, I haven't tried it. Would you like to try it?
Sally: Oh no, I didn't mean to imply that. Fish curry sounds great.

Harry: But now I'm interested in the okra, let's order some this time.
Sally: Ok.

All along, Sally didn't make her preference known, and neither did Harry. This elaborate ritual is even worse as the number of people increases. Going for lunch with one person is hard, lunch in a group of ten means that deciding the order can take a long time. I hope you had a snack before starting.

There's no guarantee that this ritual produces the correct outcome. Among young people and close friends, this ritual has given way to specifying direct preference. And I feel a sense of relief when I can clearly list my preferences without having the song and dance. In cases when the song and dance is involved, the outcome is usually unfortunate. And when you cannot express your preference, you certainly cannot express your displeasure at the outcome.

As the number of people increases, the outcome becomes more and more incorrect. Perhaps this is good, because it gives plentiful fodder for the gossip mill later on. "Jason was telling me that dining with Sally was such a chore, and how she was completely insensitive to Mark's needs."

This ritual is carried out not just for meals, but for many other decisions: what people want to do, where they want to go, whom they want to marry...

You notice some things only when you stop doing them. The complicated Indian negotiation ritual is one of these. Among friends and close family, I love the ability to say clearly what I want. Decisions happen quicker, and we can discuss things of consequence in the time saved.

(Fun fact: If Neo and Morpheus were Indian, the red pill, blue pill decision would have lasted the entire movie.)

What to do when friends are expecting: A guide for friends of new parents

2011-10-01T19:58:00.000-07:00

Your friends are having babies, and you haven't got any yourself. There are lots of guides for new parents, but few guides explaining what the friends of new parents can do. This guide will help you learn about the process, and help you deal with the change.

Fundamentals

Your friends still love you the same. You would take care of a throbbing headache rather than being with friends. Having a child is similar. They need to take care of the child before being with you.
Your friends' priorities will change. It might have been you, now it will be the baby. Don't be hurt by this. You will feel the same when you have children.
Your friends will have zero time initially. Bringing up a baby takes a lot of time and effort from both parents.
Your friends still need social contact. They enjoy social visits, but the flavor changes considerably. Mothers might have less time to meet, but they continue enjoying telephone conversations and short visits.

During Pregnancy

Mom will be tired constantly. Pregnant mothers go through many physical changes. They feel tired constantly from carrying the extra weight. Be mindful of this. Moms also have to use the restroom very frequently. Don't engage your friend for any long activity. Even long conversations are enough to tire mothers. If the mother looks or sounds uncomfortable, be prepared to give her some time off. If you are on a telephone, ask her if she needs to hang up.
Moms go through psychological changes. Many women go through mood swings. All this means that women's behavior changes considerably. Their behavior towards you will change too. Don't take it personally.
Less time. Your friends don't have a child yet. But preparing for a child is also time consuming. There are things to buy, doctors to visit, and a house to prepare. Limit your demands on their time.
Less patience. During pregnancy, your friends are going through a lot of mental and physical strain. Their levels of patience are very low. Pranks and tomfoolery are a terrible idea.
Positive conversations. Pregnancy is a scary time for parents already. Do your part by keeping all conversations positive. If you have heard of a scary pregnancy or delivery: keep the story to yourself! If there is a cautionary tale, give the moral precisely while keep gory details to yourself. Try to make all emotional stories positive. Negative emotional stories trouble the mother and make her very nervous. Dads can handle emotional stories better during this time. If you need to tell an un-nerving story, tell it to the dad, out of earshot of the mom.
Steer clear of stomach size conversations. Moms are worried about their health, their appearance, their progress. Our friends suggest the phrase, "You are carrying very well" rather than the variants that raise questions about the size or the rate of development of the baby. Definitely stay away from comments like "Are you sure you're not carrying twins?", or "Are you sure you're in your seventh month, you look small". There's nothing to be gained from comparing the size of one mother's belly with other mothers. If you are concerned about the baby's development, tell the father the specific concern and your suggestions. Let the dad discuss it with the OB or the mom.
You might want to ask the parents before gifting them anything for the baby. Or give them something that can be returned or exchanged. New parents get too many gifts. Make your gift an asset, not a burden.
How you can help: try to visit your friends at their place. Call before starting to confirm it is a good time and don't be upset by a last-minute change of plans. Carry some home-prepared meal that the mother enjoys. Be prepared to leave quickly.

During Labor

The steps in labor are: contractions or water breaking (either can happen first), active labor (pushing) and delivery.
Labor takes time. Mothers may spend twelve to fourteen hours in labor, but it could easily be twice as much. First-time mothers usually take more time during delivery.
Active labor itself can take a few hours and is the most strenuous activity the mother will ever do in her life. Active labor is like doing twice your capacity of push-ups every five minutes.
Labor takes effort. A lot of effort. Don't expect parents to do anything during this time, even take your phone calls. In addition, don't expect them to do anything for at least four days after (for the father) and two weeks after (for the mother) as the fatigue of delivery takes time to wear off.
If the child was delivered through a C-section, double all recovery times. C-sections take a long time to heal, and the dad is fatigued from his supporting role during this time.
The only priority is the child. Parents are completely focused on delivering the baby. They have no time, let alone patience, for anything else. This is no time for telephone conversations, or status updates. Be patient. You'll know when labor is done.
How you can help: spread the word, and ask others to hold off their calls to the parents.

After Delivery

Most hospitals keep mom and baby in a different room for a day or two. This is a critical time for mom to recover and learn about baby care from the nurses. Visiting mom and dad in the hospital room is usually a bad idea. There is no space in the hospital room, and mom and dad are constantly busy. In addition, the mom is weak and worn.
Mom has never been this tired. Labor drains the mother completely. Let her rest! You can speak with her later.
There's a lot to do. Post delivery, the child and mother have to be taken care of. There's food, bowel movements, health checks, doctor visits, ...
Limit infections. Just after delivery, both mom and baby are susceptible to infections. They will limit the number of people they meet. Give them a few weeks before visiting. if you have had a contagious disease like the flu, wait for many weeks of good health before visiting them. Be honest if you have any illness that can be spread.
Zero time. Mom and dad are focused on the child. They sleep when the child sleeps, and when the child is awake, they are completely busy with the child. If you do want to visit, be ready to help with the house during the visit. Your friend might ask you to help with the laundry or with the cooking or cleaning.
Prepare to hang up the phone anytime. When baby needs parents, they need to go right away. While talking with a new parent, I was once in the middle of a sentence, and my friend blurted, "Baby crying, got to go" and hung up. At the moment I thought it strange. Later I realized that it was an excellent idea rather than squirming on the phone.
Zero patience. New parents have absolutely no patience. Be as frank and honest about things. Luckily both mom and dad are happy with brutal honesty at this time. (Just not about mom's appearance.)
How you can help: congratulate the parents on email, and plan social visits at their convenience, not yours. If you stay close, consider helping them with laundry, grocery shopping, dishes, cleaning and cooking.

Hopefully these steps have enlightened you on the new world of your friends. Your friends might seem self-centered, and eager for your help. But this is the time they need to focus on themselves, and they need your support.

Rest assured that they will allow you to prioritize correctly, and provide the same care for you when you have children.

Linux udev: two-factor USB token turned into a car ignition key

2011-09-16T20:04:00.000-07:00

We use two-factor authentication at work. The one-time token generator looks a lot like an automobile key. It is easy to modify Linux to make a silly car noise when the token generator is plugged in. It turns your lame one-time token into a cool ignition key for your laptop.

Here is a video that shows what it looks like:

To do this for your device, create a shell script to make the sound of a car. I have created an audio file called car.mp3 containing the car sound. The shell script plays this file with mplayer. Record the sound of your car, or grab a file from the internet.

$ cat /root/car.sh
#!/bin/bash
# Play a silly car starting sound
mplayer /root/car.mp3 &

Now you need obtain the vendor ID. Disconnect your token generator and run this command:

$ udevadm monitor

Now insert your device. You will see an output like this:

KERNEL[] add  /devices/pci0000:00/0000:00:1a.0/usb3/3-1 (usb)
KERNEL[] add  /devices/pci0000:00/0000:00:1a.0/usb3/3-1/3-1:1.0 (usb)
KERNEL[] add  /devices/pci0000:00/0000:00:1a.0/usb3/3-1/3-1:1.0/0003:1050:0010.0015 (hid)
UDEV  [] add  /devices/pci0000:00/0000:00:1a.0/usb3/3-1 (usb)
UDEV  [] add  /devices/pci0000:00/0000:00:1a.0/usb3/3-1/3-1:1.0 (usb)
UDEV  [] add  /devices/pci0000:00/0000:00:1a.0/usb3/3-1/3-1:1.0/0003:1050:0010.0015 (hid)
KERNEL[] add  /devices/pci0000:00/0000:00:1a.0/usb3/3-1/3-1:1.0/input/input33 (input)
UDEV  [] add  /devices/pci0000:00/0000:00:1a.0/usb3/3-1/3-1:1.0/0003:1050:0010.0015/hidraw/hidraw0 (hidraw)
KERNEL[] add  /devices/pci0000:00/0000:00:1a.0/usb3/3-1/3-1:1.0/input/input33/event13 (input)
KERNEL[] add  /devices/pci0000:00/0000:00:1a.0/usb3/3-1/3-1:1.0/0003:1050:0010.0015/hidraw/hidraw0 (hidraw)
UDEV  [] add  /devices/pci0000:00/0000:00:1a.0/usb3/3-1/3-1:1.0/input/input33 (input)
UDEV  [] add  /devices/pci0000:00/0000:00:1a.0/usb3/3-1/3-1:1.0/input/input33/event13 (input)

The part after the 0003: is your vendor ID. Of course, it will be different for you. Now create a udev rule to specify the action. This is what my rule looks like:

$ cat /etc/udev/rules.d/90-token.rules
# Make a silly sound like the starting of a car
SUBSYSTEM=="usb", ATTR{idVendor}=="1050", MODE="0664", GROUP="plugdev", RUN+="/root/car.sh"

That's it, you don't need to restart anything. If you have done it correctly, then the car sound will play every time you insert your key.

Android ARM Assembly: Calling Assembly from Android (Part 8)

2011-09-13T02:00:00.000-07:00

This is part eight in a series on learning ARM assembly on Android. This part covers calling Assembly code from Android applications.

Part 1: Motivation and device set up
Part 2: A walk-through of a simple ARM assembly program
Part 3: Registers, memory, and addressing modes
Part 4: Gnu tools for assembly; GCC and GDB
Part 5: Stack and Functions
Part 6: Arithmetic and Logical Expressions
Part 7: Conditional Execution
=> Part 8: Assembly in Android code

The articles follow in series, each article builds on the previous.

Native Development Kit
You've written some assembly code, made it run real fast, and now you want to include it in an Android application. What's the advantage of running little assembly programs that can't use the full feature set available to Android? You need the Android Native Development Kit.

Download the Native Development Kit from the Android development page. Follow the instructions on that page to install it. Installation is little more than unzipping the file in the correct directory.

Sample Application
My sample application has three parts. The first is the most familiar part: this is the assembly source. This is in an assembly source file called jni/multiple.s. This code computes 10y for a given value y.

	@ This file is jni/multiple.s
	.text
	.align	2
	.global	armFunction
	.type	armFunction, %function
armFunction:
	@ Multiply by 10. Input value and return value in r0
	stmfd	sp!, {fp,ip,lr}
	mov	r3, r0, asl #3
	add	r0, r3, r0, asl #1
	ldmfd	sp!, {fp,ip,lr}
	bx	lr
	.size	armFunction, .-armFunction

The assembly code is called from a C stub. The C stub must have a very fixed name: Java_name_of_package_Class_function. This looks downright ugly but is required for Java to look up the correct function. I create a C stub to hold the strange name, and to accept the weird JNI arguments. You don't need to have a C stub, but it makes life easy.

The type jint is a java int that you can treat as a 32 bit int value. Other types are jboolean, jbyte, jchar, jshort, jlong, jfloat, jdouble, and jobject. Notice the signature of the JNI function: it accepts the environment, which is a JNIEnv pointer, and an arbitrary object. Finally, we have the input value, which is an integer. In its implementation, we call our ARM assembly function on the input. The return value is a jint, which indicates that we are returning an integer.

/* This file is jni/hello-jni.c */

#include <jni.h>

/* This stub calls the function. It helps to have a stub like this to
 * save yourself the hassle of defining the function call in
 * Assembly. */
jint Java_com_eggwall_android_assembly_AssemblyActivity_factorialJNI(
	JNIEnv* env, jobject object, jint input) {
	/* Try calling some local code */
	return armFunction(input);
}

Finally, there is a file that defines the sources in a Makefile. This is the jni/Android.mk file. It puts together the stub and the assembly code into a library called "hello-jni".

# This file is jni/Android.mk

LOCAL_PATH := $(call my-dir)
include $(CLEAR_VARS)

# I want ARM, not thumb.
LOCAL_ARM_MODE := arm

# Name of the local module
LOCAL_MODULE    := hello-jni
# The files that make up the source code
LOCAL_SRC_FILES := hello-jni.c multiple.s

include $(BUILD_SHARED_LIBRARY)

The stub and the assembly input are compiled by calling the following command from the root directory of your project. This is the directory that contains jni/, src/, res/, ..etc. I am assuming the ndk is installed in /usr/local/android-sdk-linux_x86/android-ndk-r6b.

$ ls
AndroidManifest.xml  assets/  bin/  build.properties  build.xml  default.properties
gen/  jni/  libs/  local.properties  obj/  proguard.cfg  res/  src/
$ /usr/local/android-sdk-linux_x86/android-ndk-r6b/ndk-build
Compile arm    : hello-jni <= multiple.s
SharedLibrary  : libhello-jni.so
Install        : libhello-jni.so => libs/armeabi/libhello-jni.so

Finally, there is a Java source code to create the Activity in Android. This code creates an Android application. It extends Activity, and overrides the onCreate method. In this, it creates a TextView, which is a label, and then sets the contents of the label to the return value of the function. It defines a function called factorialJNI which accepts an integer input and returns an integer. It is marked as native, indicating that its implementation is not in Java.

Finally, a static initialisation loads the jni library that was defined in the XML file.

package com.eggwall.android.assembly; 
 
import android.app.Activity; 
import android.widget.TextView; 
import android.os.Bundle; 
 
public class AssemblyActivity extends Activity { 
	@Override 
	public void onCreate(Bundle savedInstanceState) { 
		super.onCreate(savedInstanceState); 
		// Create a new Textview 
		TextView  tv = new TextView(this); 
		// Print the multiple of 13 through assembly. 
		tv.setText("The multiple was: " + factorialJNI(13)); 
		setContentView(tv); 
	} 
	/**
	 * Multiply the number by 10.
	 * @param input, the number to be multiplied
	 * @return the multiple of the number
	 */ 
	public native int factorialJNI(int input); 
	/* This is used to load the 'hello-jni' library on application
	 * startup. The library has already been unpacked into
	 * /data/data/com.eggwall.android.AssemblyActivity/lib/libhello-jni.so at
	 * installation time by the package manager.
	 */ 
	static { 
		System.loadLibrary("hello-jni"); 
	} 

}

That is a lot of code to run a single assembly function! But now that you've seen the overall structure, you can begin modifying it to run your own assembly code. This is not a good way to experiment with assembly programming, though. Assembly programs can be hard to debug and it helps to have good tools during development. I would recommend developing using emacs, gcc, gdb, and other GNU tools, just as before. When the code is working correctly, hook it into Android Java source. The Android NDK has some useful debugging facilities, but I would consider them options of last resort.
You can download the entire ARM Android assembly example as an Eclipse project here.

Speed versus Complexity
Just because you are calling assembly code does not automatically make your program faster. The Dalvik virtual machine runs most code fairly fast, and the effort to develop assembly code is not worth the minor improvement in code execution speed. Here are some reasons why you might want to use native code.

Legacy code. You have a lot of existing code that you want to plug into Android.
Optimised code. You have CPU-intensive code that has been carefully optimised.

Assembly code takes a longer to develop, more effort to maintain, and is difficult to port. There are few people who can read assembly code, so your code will be out of reach of many programmers.

A careful consideration of implementation speed and code complexity will lead you to the correct balance.

Things to try out

Create a new function called factorial(int a) and its corresponding stub. Call it from Java.
Create a new source file called factorial.s, and put the function in there. Modify jni/Android.mk to run it correctly.
Try adding an input area, where a number is entered. Pass this number to the assembly source code, and print out its factorial.

My example builds upon the hello-jni example that ships with the NDK. You can read the other NDK samples for inspiration. You can learn more by reading the JNI reference. It covers the data types, and the various functions available from native code.

Android ARM Assembly: Conditional execution (Part 7)

2011-09-12T02:00:00.000-07:00

This is part seven in a series on learning ARM assembly on Android. This part covers conditional execution.

Part 1: Motivation and device set up
Part 2: A walk-through of a simple ARM assembly program
Part 3: Registers, memory, and addressing modes
Part 4: Gnu tools for assembly; GCC and GDB
Part 5: Stack and Functions
Part 6: Arithmetic and Logical Expressions
=> Part 7: Conditional Execution
Part 8: Assembly in Android code

The articles follow in series, each article builds on the previous.

Compare and Jump
The previous lessons touched on a variety of microprocessor instructions. Let's move to conditional execution. These are the basis of all the if, while, for loops in programming languages.

Conditions are implemented in microprocessors using the Status Register CPSR. The various bits on the status register are set using instructions. Then, you can jump to a different position in the code if the specific bit is set or unset. While this scheme looks primitive, it forms the basis of all conditional execution in every language on computers. Let's see the status register again.

The conditions in the status register are:

Negative: the result was negative (bit 31 of the result was set)
Zero: the result was zero (all bits of the result were unset)
Carry: integer addition, subtraction or shifts produce a carry or borrow (result bits could be anything)
oVerflow: there was carry or borrow during signed addition or subtraction (result bits could be anything)

The status register has other bits relating to the different processor modes, but we can ignore them for now. The bits in the CPSR are set on four instructions: CMP, CMN, TEQ, TST. Let's see these instructions.

CMP Rn, shifter_operand

This performs Rn - shifter_operand, throws away the result and updates the status register. So doing a CMP R2, R2 would produce a zero output, and the Zero condition would be set. It is important to note that the result is never stored anywhere. From your perspective, you are asking the processor what the result would be like.

This is a full list of the comparison instructions.

Instruction	Rough Intention	The condition flags are set based on this value
CMP Rn, shifter_operand	(Addition)	Rn - shifter_operand
CMN Rn, shifter_operand	(Negation)	Rn + shifter_operand
TST Rn, shifter_operand	(Test)	Rn & shifter_operand
TEQ Rn, shifter_operand	(Test Equivalence)	Rn ^ shifter_operand

Once the condition is set, you can use that condition to jump to a specific label. The easiest jump instruction doesn't care for flags. We saw it in part 5, where it was used to return execution back from our function.

        bx      lr

This instruction branched execution to the address contained in the Link Register. This could be done with any register, though you better be sure that the register contains a valid address. It also needs to be a 32-bit aligned address. All ARM instructions are 32-bit (word) aligned. This isn't Intel, every instruction is exactly 32 bits long. BX is a Branch, while BL is a Branch and Link.

Branch just jumps to the address specified in the register.

Branch and Link stores the address of the existing Program Counter in the Link Register, in case you want to jump back. This is something you do all the time, so there is one instruction to handle it.

ARM and Thumb Instructions
Most new ARM processors support two different instruction sets: ARM and Thumb. Thumb instructions are a subset of ARM instructions and are 16 bits each. Going back and forth between ARM and Thumb is possible, though it should be done correctly. The branch instructions ending in "X" do this. A "BX" instruction allows you to switch between ARM and Thumb while the "B" instruction doesn't. In general, you should use "BX" and "BLX" when you are unsure of the resulting code. If you are certain, you can use "B" for branch, and "BL" for branch and link.

Condition Codes
How about adding the actual condition? The condition goes as a suffix to the instruction. Say you only want to check if the Zero condition was true. Then, the condition is called EQual, with mnemonic EQ. So this operation only branches when the zero condition is set:
BLEQ lr

The full list of conditions is:

Suffix	Meaning	Condition tested
EQ	Equal	Z == 1
NE	Not Equal	Z == 0
CS or HS	Unsigned Higher or Same (Carry Set)	C == 1
CC or LO	Unsigned Lower (Carry Clear)	C == 0
MI	MInus	N == 1
PL	PLus or Zero	N == 0
VS	Overflow (V Set)	V == 1
VC	No Overflow (V Clear)	V == 0
HI	Unsigned Higher	C == 1 and Z == 0
LS	Unsigned Lower or Same	C == 0 or Z == 1
GE	Signed Greater Than or Equal	N == V
LT	Signed Lesser Than	N != V
GT	Signed Greater Than	Z == 0 and N == V
LE	Signed Less Than or Equal To	Z==1 or N != V
AL	Always

So you could have an instruction BXNE r3, which will branch to r3, only if the previous comparison did not set the Zero condition code.

Conditional Execution
Let's look at a single if-then loop to see how to run a simple conditional in Assembly.

 1         .section        .data
 2         .align 2
 3 higher:
 4         .asciz "Yes, r2 is higher than or equal to r1\n"
 5 lower:
 6         .asciz "No, r2 is lower than r1\n"
 7 
 8         .text
 9         .align  2
10         .global main
11         .type   main, %function
12 main:
13         stmfd   sp!, {fp, lr}
14 
15         @ Load some values
16         mov     r1, #32
17         mov     r2, #33
18 
19         @ Check if r2 is lower than r1
20         cmp     r2, r1
21 
22         @ If it is greater or equal, jump ahead
23         bge     greaterOrEqual
24 
25         @ Otherwise it was lower
26         ldr     r0, =lower
27         @ Now skip past to the common point again
28         b       common
29 
30 greaterOrEqual:
31         ldr     r0, =higher
32 
33 common:
34         @ Print the message
35         bl      puts
36 
37         @ Return 0
38         mov     r0, #0
39         ldmfd   sp!, {fp, lr}
40         bx      lr

This program loads values in r2 and r3 and then compares the two. If (r2-r1) is greater than or equal to 0, then we skip to the greaterOrEqual label. Since there are only one kind of instructions (ARM instructions), we don't bother with the "X" variant of the branch. At the greaterOrEqual label, we move the string corresponding to the higher message. Otherwise, we move the string corresponding to the lower message into r0. Either case, we want to get to the common code, which prints the message, and returns 0. If we didn't return to the common case, it would continue running instructions linearly, and load r0 with the higher message. Then, we return 0, like every well behaved main() function should.

The Program Counter holds the address that will be executed next. Since it is also r15, you can directly modify it. This is a terrible idea in most cases, so you should have a good reason to do this. In theory, you could implement logic by conditionally moving values into the Program Counter. For example, you could add 8 to the current value in the PC to skip an instruction. In practice, you will not do this because it is prone to errors. Such logic fails when the program is modified, and the address of instructions changes.

Every Instruction is Conditional
Now that you know what conditional execution looks like, you are ready for a real twist. In ARM architectures, every instruction is conditional. So the ADD, SUB, LDR, STR instructions can all have these condition codes appended to them. We could write instructions containing very few BX or BLX calls.

In practice, however, you should use conditional operations only for a single instruction or two. If you find that a lot of operations act on the same condition, you should branch and skip all these operations. This is much more efficient, since ARM processors fetch more than one instruction and act upon parts of it in parallel. If you can start to execute the next few instructions, your code is considerably faster. So as a rule, use conditional operations only for two instructions or fewer. If you have a longer list of conditional operations that depend on the same condition, pull them out in a separate routine.

In addition to every instruction being conditional, every instruction can set the CPSR flags. For this, you need to append the "S" flag (for Status) to every instruction. Here is what a MOV instruction really looks like:
MOV{condition_code}{S} Rd, shifter_operand
This allows you to set the status flag without performing a CMP, saving another instruction. The status flag can be set on most operations you have seen till now. So you can automatically set the condition codes when performing arithmetic operations.

Exercises
Try your hand at these to see if you understand branches.

What does the MOVGE r0, r2 instruction do?
Rewrite the program to use just one branch rather than two.
Rewrite the program using conditional move to avoid a branch. In this case, a conditional move is perhaps cleaner since the condition only changes one instruction.
Write a function isZero(n) to accept an unsigned number n and to return 1 if n is equal to 0 and n otherwise.
Improve on isZero() to write almostFactorial(n) which returns n*(n-1) if n is not zero, and 1 otherwise.
Try your hand at turning almostFactorial(n) to factorial(n) which returns n! for small values of n. As n gets large, you run out of bits, so you will need to test your function with small inputs.
Write a simple while { .. } loop in C and let GCC compile it to assembly. See if you can make sense of the code. GCC can compile code with optimisations turned on with the "-O2" flag. Try to read the assembly output with and without optimisations. See if you can figure out the optimisation logic.

This marks the end of all the functional pieces of ARM architecture. You should be able to read the disassembly of nearly any ARM program now. Isn't that impressive? Look up unknown instructions in the reference manual. As always, the ARM Reference Manual has more information on all condition codes, conditional execution and instructions that accept conditions and can set the flags.

The final piece will be to integrate this with Android. We will see how to call assembly code from Android to be able to run fast processing directly in assembly.

Book Review: The Big Necessity by Rose George

2011-09-11T15:11:00.000-07:00

Would you be worried if a Boeing 747 worth of people died? What if it were all children. How about 10 Boeing 747s of children dying, everyday?

Diarrhea causes 1.5 million deaths in children every year. That's roughly ten 747s worth every single day. And diarrhea is simple to cure. Good sanitation removes the occurrence of the disease. The reason why so many children still die of diarrhea is because of poor sanitation. Most deaths are in third-world countries, and the West is largely unaware of the problem because it is embarrassing to talk about poop.

Rose George's book, "The Big Necessity" talks about various aspects of poop in her book: from the science of waste water treatment, to the design of eco-friendly toilets and the problems of third-world sanitation. It is a delightful read which brings our awareness to many poop-related issues.

We don't really talk about poop, even though many of our swear-words include fecal matter. And that's largely the problem. We can solve problems of nutrition because we can casually talk about African children only eating 400 calories a day. What we cannot do is talk about the fecal matter that is contaminating their food. So we can talk about to 400 calories they are eating, but not about the crap they are eating with it.

Sanitation brings immense benefits. Children living in areas with good sanitation fall ill less, and are more likely to go to school. Girls' education is directly related to good sanitation. Yet, we're too civilised to talk about improving sanitation.

The book is an insightful read. I would highly recommend it to anyone who has witnessed poverty and wondered what can be done to improve health of the poor. It talks about open defecation in India, the general lack of sanitation in India, and glimmers of hope from rural China. Each chapter deals with a single aspect of sanitation. You will learn about how waste water is treated in the West, and why it is a poor design. You will learn about the difficulties in marketing toilets to the poor. It should be an easy sell, but there are reasons why it is hard, and the book talks about creative solutions.

Android ARM Assembly: Arithmetic and Logical Operations (Part 6)

2011-09-10T08:03:00.000-07:00

This is part six in a series on learning ARM assembly on Android. This part covers arithmetic and logic expressions.

Part 1: Motivation and device set up
Part 2: A walk-through of a simple ARM assembly program
Part 3: Registers, memory, and addressing modes
Part 4: Gnu tools for assembly; GCC and GDB
Part 5: Stack and Functions
=> Part 6: Arithmetic and Logical Expressions
Part 7: Conditional Execution
Part 8: Assembly in Android code

The articles follow in series, each article builds on the previous.

We covered a lot of data moving in the previous articles. Let's see what processing we can do.

Arithmetic
The ARM processors are packed with the usual arithmetic operators. If you have experience with some other processor, you might find the possible operations somewhat limited. This follows the Reduced Instruction Set principles: there are a few basic primitives and you are required to produce everything using these. So you lack complex instructions, but make up for it with faster code. More importantly, you make up for it with code that runs quiet, cool, and uses minimal battery life.

All arithmetic instructions look identical. Remember the MOV instructions?

An immediate value. Ex.
```
mov	r0, #3
```
A register. Ex:
```
mov	r0, r1
```
A register with an offset. Ex:
```
mov	r0, r1, #4
```
A register with a shift. Ex:
```
mov	r0, r1, lsr #3
```
A register with a register specifying the shift. Ex:
```
mov	r0, r1, lsr r2
```

The first part is called the destination register, since that's where the value is placed. The second part is called the shifter_operand, as a short-hand for one of many possibilities. In other words, MOV instructions have this structure:
MOV Rd, shifter_operand. This causes: Rd = shifter_operand

Arithmetic instructions follow the same structure. Instead of having one register, they have two registers. This is the general structure of arithmetic instructions:
OPERATION Rd, Rn, shifter_operand

OPERATION can be one of:

ADD	(Addition)	Rd = Rn + shifter_operand
SUB:	(Subtraction)	Rd = Rn - shifter_operand
RSB:	(Reverse Subtraction)	Rd = shifter_operand - Rn
ADC:	(Add with Carry)	Rd = Rn + shifter_operand + Carry
SBC:	(Subtract with Carry)	Rd = Rn - shifter_operand - Carry
RSC:	(Reverse Subtract with Carry)	Rd = shifter_operand - Rn - Carry
AND:	(Logical And)	Rd = Rn & shifter_operand
BIC:	(Logical Bit Clear)	Rd = Rn & ! shifter_operand
ORR:	(Logical Or)	Rd = Rn \| shifter_operand
EOR:	(Logical Exclusive Or)	Rd = Rn ^ shifter_operand

The instructions are regular and follow the same pattern. The only unexplained thing is the Carry.

Carry is a bit in the status register CPSR that is set when an addition overflows past 32 bits. This could happen when adding 1 to 0xff ff ff ff. The resulting number is 1 << 32, which cannot be represented in 32 bits. It needs 33 bits. In such a case, the carry bit will be set. Addition with carry allows you to automatically add the carry bit.

The carry bit is also set when subtraction produces underflow: If you subtract INT_MAX from 0, the resulting number cannot be expressed in 2's complement because it needs to borrow a bit. In such a case, the carry is set again.

Multiply
Multiplications only take a register argument. They don't take a shifter_operand.

MLA Rd, Rm, Rs, Rn	Multiply with Accummulate	Rd = Rm * Rs + Rn
MUL Rd, Rm, Rs	Multiply	Rd = Rm * Rs
SMLAL Rd32, Rd64, Rm, Rs	Signed Multiply with Accummulate Long	Rd64,Rd32 += Rm * Rs
SMULL Rd32, Rd64, Rm, Rs	Signed Multiply Long	Rd64,Rd32 = Rm * Rs
UMLAL Rd32, Rd64, Rm, Rs	Unsigned Multiply with Accummulate Long	Rd64,Rd32 += Rm * Rs
UMULL Rd32, Rd64, Rm, Rs	Unsigned Multiply Long	Rd64,Rd32 = Rm * Rs

MLA and MUL are easy to understand. The difference between Signed and Unsigned instructions is that signed instructions use bit 31 as a sign bit, and 2's complement arithmetic. If you know you have unsigned numbers, using the unsigned variants allows you to express higher numbers.

The Long version of the instructions stores the lower 32 bits of the result in Rd32 and the higher bits in Rd64. MLA and MUL store only the lower 32 bits of the result, so if you multiply two very large numbers, you will get incorrect results.

A multiply is slower than using the barrel shifter. If you need to multiply by 4, you are much better off supplying "lsl #2".

Links
Arithmetic and logical instructions are very easy in ARM processors. I have covered the instructions available in v5 of ARM processors. These instructions are guaranteed to be available nearly everywhere. v6 adds a few instructions, but the regular structure means that once you understand the v5 set, you can immediately learn the v6 additions.

You can try the following to test your knowledge till now:

Write a function to input an integer y and return y * (y-1). Check by calling it inside main() and using the program from Part 5 to print the value.
Test out the behaviour of BIC using a program and different inputs. Why is it called Bit Clear?

As before, the ARM Reference Manual has more information on all operations.

Android ARM Assembly: Stack and Functions (Part 5)

2011-09-09T04:00:00.000-07:00

This is part five in a series on learning ARM assembly on Android. This part covers the stack and function calling.

Part 1: Motivation and device set up
Part 2: A walk-through of a simple ARM assembly program
Part 3: Registers, memory, and addressing modes
Part 4: Gnu tools for assembly; GCC and GDB
=> Part 5: Stack and Functions
Part 6: Arithmetic and Logical Expressions
Part 7: Conditional Execution
Part 8: Assembly in Android code

The articles follow in series, each article builds on the previous.

Stack
The stack is a linear data structure in memory that holds function-specific information. When a function call is made, the stack is grown, and we place local variables on the stack. When a function returns, we shrink the stack, and the local variables are lost. The stack is a temporary structure. For permanent non-constant variables, we need to allocate space on the heap. The heap is an operating system (OS) concept that we'll cover later. It is an OS concept because the processor is unaware of its presence. It is a programming paradigm rather than a facility provided by the silicon on the chip. The stack, on the other hand, is a processor-level concept. Life is a lot simpler if the processor supports stack primitives.

The stack grows up: to allocate space on the stack, you subtract multiples of 4 from the Stack Pointer. If you need 5 variables, you need to subtract 20 from the Stack Pointer. (In many documents, the memory is laid out from highest address to the lowest address. In such documents, the stack is said to grow downwards. Unfortunately, this is a standard convention even though humans think of stacks growing upward, so I explain everything with the stack growing upward.)

If you write memory as a linear list of addresses, you can see why this makes sense. Here is the memory laid out from top to bottom as a linear list going from the lowest address to the highest address. All addresses and data are in hexadecimal.

Data	Location
ab	0000
cd	0004
de	0008
xx	...
f0	0080
f0	0084
f2	0088
f3	008c
f4	0090 <- SP
xx	...
ff	ffff

The Stack Pointer is pointing at location 90, which means that it contains the value 0x90. The value at the top of the stack is f4, and this is the contents of memory location 0x90.

If we want to allocate two variables, we need to subtract 4 * 2 = 8 from the stack pointer. Say we store values 99 and AA at these locations, then the stack looks like this:

Data	Location
ab	0000
cd	0004
de	0008
xx	...
f0	0080
f0	0084
99	0088 <- SP
AA	008c
f4	0090
xx	...
ff	ffff

We ended up clobbering the existing values at those locations. To deallocate space from the stack, you add to the SP. Every allocation on the stack should be matched by a de-allocation. Otherwise you get out of sync, and read the wrong value. Functions start out by storing all the local registers on the stack. Then, on top of the stack, they allocate function-specific data.

Data	Location
ab	0000
cd	0004
de	0008
xx	...
current function's stack	0080 <- SP
SP	0084
LR	0088
PC	008c
previous function's stack	0090
xx	...
ff	ffff

As a result, the new function has space to grow, and when it returns, the previous variable values are moved from the stack to the registers. From the perspective of the calling function, nothing has changed.

Writing Functions
Let's look at a program to see how variables are stored on the stack. I'll use a long program, because we need a main function and another function that we can change to our liking. The main() function has a fixed signature, so we need something different.

 1         .text
 2         .align  2
 3         .global multiplyByTen
 4         .type   multiplyByTen, %function
 5 multiplyByTen:
 6         stmfd   sp!, {fp, ip, lr}
 7         mov     r3, r0, asl #3
 8         add     r0, r3, r0, asl #1
 9         ldmfd   sp!, {fp, ip, lr}
10         bx      lr
11         .size   multiplyByTen, .-multiplyByTen
12 
13         .section        .rodata
14         .align  2
15 .LC0:
16         .ascii  "The number is %d\012\000"
17 
18         .text
19         .align  2
20         .global main
21         .type   main, %function
22 main:
23         stmfd   sp!, {fp, lr}
24 
25         mov     r0, #32
26         bl      multiplyByTen
27 
28         mov     r1, r0
29         ldr     r0, .L3
30         bl      printf
31 
32         mov     r0, #0
33         ldmfd   sp!, {fp, lr}
34         bx      lr
35 
36         .align  2
37 .L3:
38         .word   .LC0
39         .size   main, .-main

The program is long, but you should be able to understand most of it by now.
This is the function we made:

 5 multiplyByTen:
 6         stmfd   sp!, {fp, ip, lr}
 7         mov     r3, r0, asl #3
 8         add     r0, r3, r0, asl #1
 9         ldmfd   sp!, {fp, ip, lr}
10         bx      lr

This function returns the input multiplied by 10 through its creative uses of shifts. Multiplying y by 10 is the same as (y << 3 + y << 1) = (8y + 2y). The function is made to illustrate how function calling works. The first four inputs to a function are kept in r0-r3. Here we have just one input, so it is in r0. Line 7 moves 8*r0 to r3, and line 8 adds 2*r0 to this, and stores it back in r0. The return value of the function is kept in r0. However, we also have line 6 and line 9. What are they doing?

 6         stmfd   sp!, {fp, ip, lr}

This is a multi-register move operation. This moves the registers FP,IP,LR into the area specified by the register SP. Since SP is the stack pointer, this is the same as pushing registers FP,IP,LR to the top of the stack in a single operation. FP is another name for r11. Once this is done, the stack pointer is updated since it has an exclamation mark. The order of specifying the registers doesn't matter. ARM processors have a bitmask to specify which registers are written, and they are always written in the same order, irrespective of the order you specify them in. GCC might complain if you specify them in the wrong order, though. STM is the base operation, there are variants depending on how you want the stack to grow. STM is STore Multiple, and it comes in variants like IA: Increment After, IB: Increment Before, DA: Decrement After, DB: Decrement Before. These describe when the stack pointer is updated (before writing to memory, or after), and whether it is incremented or decremented. These operations also have handy mnemonics describing their use for operating with stacks. Linux uses a Full Descending type of a stack. Full because the stack pointer points to the last used location, and Descending because the stack grows downward, when memory listed from highest address to lowest address. If you use the FD versions of these operations, your code will interoperate well with other libraries.

 9         ldmfd   sp!, {fp, ip, lr}

This is another multi-register move that undoes the action on line 6. This reads back the values that were written earlier, popping them from the stack. The combined effect of lines 6 and 9 is to store the important register values on the stack and then restore them. This allows the function to modify them in the main body. As with STMFD, the values are specified in a bitmask, so they are always read in the same order.

The function semantics require that r0-r3 are the only registers that can be clobbered during a function call. If you need more than four registers in a function, you need to include them in the STMFD and LDMFD lines to ensure they are restored before exit. If you need a lot of local variables in a function, you need to keep the rest in memory using load and store commands. You can safely keep variables past the stack, in locations like SP-4, SP-8. When your function returns, the stack pointer is restored and the next function can reuse this storage. You can either grow the stack by subtracting multiples of 4 from it, or you can refer to offsets from the stack. The ARM Procedure call Standard mentions that r4-r8, r10, r11, and the SP need to be preserved in a subroutine. So if you are modifying these registers, ensure that you store them at the start and load them back before the end of your routine.

If you need to pass more than four input values to a function, you need to store them on the stack. The function needs to read the exact number of values from the stack. Finally, if you need to return more than one value, you need to modify values in the stack, or return them in r0-r3, and hope your code is never called by anyone else's code.

Exercises
Try experimenting with the following:

Break the function at various points with GDB and examine the memory starting at the Stack Pointer. Does the stack pointer point to the last variable on the stack, or past the last variable on the stack?
Try removing the STMFD and LDMFD in the multiplyByTen function. Does the function still work?
Change multiplyByTen to return the value of SP. Print it using '%p' in the printf. Does it match what GDB says?
Change the multiplyByTen to modify IP, LR and FP in the function and assert that they are indeed restored. Verify the modification and the restoring through GDB.
Rewrite the function to use LDR and STR rather than multi-register moves. You will need to modify the stack pointer with each load and store.

The ARM Reference Manual has more information on mutiple loads and stores, including information about the IA,IB,DA,DB, and FD versions, and what they mean.

Android ARM Assembly: GCC and GDB (Part 4)

2011-09-08T08:11:00.000-07:00

This is part four of a multi-part series. This part covers the Gnu C Compiler and the Gnu Debugger. Both are essential development tools.

Part 1: Motivation and device set up
Part 2: A walk-through of a simple ARM assembly program
Part 3: Registers, memory, and addressing modes
=> Part 4: Gnu tools for assembly; GCC and GDB
Part 5: Stack and Functions
Part 6: Arithmetic and Logical Expressions
Part 7: Conditional Execution
Part 8: Assembly in Android code

The articles follow in series, each article builds on the previous.

In case you already know how to use Gnu tools in the Intel world, they work in the same way for ARM machines.

GCC
GCC is the default compiler on Linux systems. It is a versatile compiler. We need very few options for our ARM assembly development.

$ gcc -S source.c

This is perhaps the most useful way in which we can use gcc. It creates an assembly source.s file which corresponds to the C source code. This is great for learning how gcc translates specific C constructs to assembly.

$ gcc -o hello source.c

Compile C file source.c into an executable called hello.

$ gcc -o hello source.s

Compile assembly file source.s into an executable called hello. This is probably what you will be using all along.
The full GCC manual can be downloaded online.

GAS
Gas is the GNU assembler, and is the default assembler on Linux systems. My tutorials don't call gas directly. If you invoke gas yourself, you get an object file that you need to link against glibc using the linker. Invoking gcc on assembly source code calls gas and the linker, so I prefer to do that.

Knowledge of the assembler helps when you want to use specific assembler directives. The gas manual is available online.

GDB
While programming assembly, you often need something to show you what the state of the machine is. You need to see every register and every memory location. This is where GDB comes in. It is free, it is easy to use. Here is a gentle introduction to gdb to cover most assembly needs.

$ gdb hello

Start gdb with the executable called hello. It prints a helpful message, and drops you to the (gdb) prompt. This prompt is where you type all commands.

(gdb) disassemble main
Dump of assembler code for function main:
   0x000083d0 <+0>:	push	{r11, lr}
   0x000083d4 <+4>:	add	r11, sp, #4
   0x000083d8 <+8>:	sub	sp, sp, #8
   0x000083dc <+12>:	str	r0, [r11, #-8]
   0x000083e0 <+16>:	str	r1, [r11, #-12]
   0x000083e4 <+20>:	ldr	r0, [pc, #20]	; 0x8400 
   0x000083e8 <+24>:	bl	0x82e8 
   0x000083ec <+28>:	mov	r3, #0
   0x000083f0 <+32>:	mov	r0, r3
   0x000083f4 <+36>:	sub	sp, r11, #4
   0x000083f8 <+40>:	pop	{r11, lr}
   0x000083fc <+44>:	bx	lr
   0x00008400 <+48>:	andeq	r8, r0, r8, lsl #9
End of assembler dump.

Look at the assembly source of any function. In this case, we looked through the assembly output of main, the entry point to our hello word function. There are some familiar instructions here already. Disassembly can be done for any executable. You don't need the source code for the program.

(gdb) break *0x000083e4
Breakpoint 1 at 0x83e4

This sets a breakpoint at the specified memory address. When you run the program, the execution will break at that location, and you will be dropped back on the gdb shell to inspect the state.

(gdb) run
Starting program: /home/user/ARM/hello 

Breakpoint 1, 0x000083e4 in main ()

Alright, we started the program and it broke exactly where we asked it to. This is a great time to examine the registers and the memory.

(gdb) info registers
r0             0x1	1
r1             0xbed9a924	3201935652
r2             0xbed9a92c	3201935660
r3             0x83d0	33744
r4             0x0	0
r5             0x0	0
r6             0x0	0
r7             0x0	0
r8             0x0	0
r9             0x0	0
r10            0x40025000	1073893376
r11            0xbed9a7d4	0xbed9a7d4
r12            0xbed9a840	3201935424
sp             0xbed9a7c8	0xbed9a7c8
lr             0x4003b508	1073984776
pc             0x83e4	0x83e4 
cpsr           0x60000010	1610612752

This command shows you the register state. As you can see, there are the standard registers r0-r12, and SP, LR, and PC. You can also see the status register CPSR printed in full. The function calling convention on ARM is that the first four arguments to a function are stored in r0-r3. Let's verify that this is the case.
The function we are looking at is main(int argc, char* argv[]). It has two arguments argc and argv, which should be in r0 and r1 respectively. r0 should contain argc, or the number of commandline arguments given. We invoked the program with no arguments, so the commandline arguments consist of only the program name. argc should be 1, which is what r0 contains
argv is trickier. It is a pointer to pointers containing strings. This is partly confirmed by r2, which is a large hex number: 0xbed9a924. It could be a memory location. Let's find out.

(gdb) x/w 0xbed9a924
0xbed9a924:	0xbed9aa0d

The "x/w" stands for eXamine memory/ parse as Word. Memory locations could contain anything, so we want to parse it as a 32 bit word to start out. The contents look a lot like the address itself. Let's see what the next few contents hold.

(gdb) x/12w 0xbed9a924
0xbed9a924:	0xbed9aa0d	0x00000000	0xbed9aa22	0xbed9aa32
0xbed9a934:	0xbed9aa3d	0xbed9aa47	0xbed9af37	0xbed9af43
0xbed9a944:	0xbed9af80	0xbed9af8f	0xbed9afa2	0xbed9afab

x/12w stand for eXamine memory/show me 12 Words. As you can see, all the contents of memory look like they are addresses. Let's see what is at the first address: at 0xbed9aa0d

(gdb) x/w 0xbed9aa0d
0xbed9aa0d:	0x6d6f682f

Hmm, that doesn't look like an address. This should be a string, and rather than converting the 0x6d 0x6f 0x68 ... to ascii myself, I'll let gdb help me out.

(gdb) x/s 0xbed9aa0d
0xbed9aa0d:	 "/home/user/ARM/hello"

We are asking gdb to "eXamine memory / as String". gdb knows that C strings are null terminated, so it helpfully walks over the successive memory locations, interpreting each byte as ASCII, till it comes to a null terminator. So we have verified that argv[1] is a pointer to a string, containing the program name. Let's see what the next few memory addresses hold.

(gdb) x/10s 0xbed9aa0d
0xbed9aa0d:	 "/home/user/ARM/hello"
0xbed9aa22:	 "SHELL=/bin/bash"
0xbed9aa32:	 "TERM=xterm"
0xbed9aa3d:	 "USER=user"
0xbed9aa47:	 "LS_COLORS=rs=0:di=01;34:ln=01;36:mh=00:pi=40;33:so=01;35:...
0xbed9ab0f:	 ":*.taz=01;31:*.lzh=01;31:*.lzma=01;31:*.tl...
0xbed9abd7:	 "eb=01;31:*.rpm=01;31:*.jar=01;31:*.rar=0"...
0xbed9ac9f:	 ":*.xbm=01;35:*.xpm=01;35:*.tif=01;35:*.ti...
0xbed9ad67:	 "v=01;35:*.mp4v=01;35:*.vob=01;35:*.qt=0...
0xbed9ae2f:	 "yuv=01;35:*.cgm=01;35:*.emf=01;35:*.axv...

We "eXamine 10 memory locations as String", and we find that we have run past the end of argv. We are seeing the environment variables that are specified by the Bash shell, including the name of the shell, the username, and the colors for the different file types. I forgot, where were we?

(gdb) where
#0  0x000083e4 in main ()

We can find out our state in the execution by asking 'where'. Though we could just as easily have looked up the Program Counter register for this simple program.

(gdb) disassemble main
Dump of assembler code for function main:
   0x000083d0 <+0>:	push	{r11, lr}
   0x000083d4 <+4>:	add	r11, sp, #4
   0x000083d8 <+8>:	sub	sp, sp, #8
   0x000083dc <+12>:	str	r0, [r11, #-8]
   0x000083e0 <+16>:	str	r1, [r11, #-12]
=> 0x000083e4 <+20>:	ldr	r0, [pc, #20]	; 0x8400 
   0x000083e8 <+24>:	bl	0x82e8 
   0x000083ec <+28>:	mov	r3, #0
   0x000083f0 <+32>:	mov	r0, r3
   0x000083f4 <+36>:	sub	sp, r11, #4
   0x000083f8 <+40>:	pop	{r11, lr}
   0x000083fc <+44>:	bx	lr
   0x00008400 <+48>:	andeq	r8, r0, r8, lsl #9
End of assembler dump.

gdb shows a helpful arrow showing where we are. We can set another breakpoint if we like. After a long debugging session, you might forget which breakpoints you have set.

(gdb) info breakpoints 
Num     Type           Disp Enb Address    What
1       breakpoint     keep y   0x000083e4 
	breakpoint already hit 1 time
        info registers
3       breakpoint     keep y   0x000083f0 
        info registers

You can see all breakpoints with 'info breakpoints' and you can delete breakpoints with 'delete x', where x is the number of the breakpoint. When deleting breakpoints, gdb doesn't produce any output if it is successful.

(gdb) delete 3

A very helpful technique when debugging for loops is to run some commands automatically when a breakpoint is hit. This is done with the 'commands' directive as folows.

(gdb) break *0x000083ec
Breakpoint 4 at 0x83ec
(gdb) commands 4
Type commands for breakpoint(s) 4, one per line.
End with a line saying just "end".
>info registers
>end
(gdb)

Now, when the breakpoint is hit, gdb will automatically run the 'info registers' command. Let's continue running this program so it can hit the next breakpoint.

(gdb) continue
Continuing.
Hello World

Breakpoint 4, 0x000083ec in main ()
r0             0xc	12
r1             0x0	0
r2             0x40153228	1075130920
r3             0x83d0	33744
r4             0x0	0
r5             0x0	0
r6             0x0	0
r7             0x0	0
r8             0x0	0
r9             0x0	0
r10            0x40025000	1073893376
r11            0xbed9a7d4	0xbed9a7d4
r12            0x0	0
sp             0xbed9a7c8	0xbed9a7c8
lr             0x83ec	33772
pc             0x83ec	0x83ec 
cpsr           0x60000010	1610612752

gdb ran past the puts(), and printed "Hello World" on the screen. It hit the breakpoint, and automatically showed us the registers. Great. Let's finish up by continuing.

(gdb) continue 
Continuing.
[Inferior 1 (process 17307) exited normally]
(gdb) info registers 
The program has no registers now.

The program is done. We can't examine registers or memory because it isn't running anymore.
The full GDB documentation is available online.

Links
Now that you know how to examine registers and memory, you can write ARM programs and verify that they do the right thing. You can break at various locations and verify that your load store and move instructions are working as expected.

The Gnu tools are ubiquitous and mature. Once you learn how to use gdb and gcc on ARM, you can easily use the same tricks on another platform like Intel. Here are all the manual links again:

Android ARM Assembly: Registers, Memory and Addressing Modes (Part 3)

2011-09-07T20:31:00.000-07:00

This is part three of a series on learning ARM assembly on Android. This part covers registers, memory and addressing modes.

Part 1: Motivation and device set up
Part 2: A walk-through of a simple ARM assembly program
=> Part 3: Registers, memory, and addressing modes
Part 4: Gnu tools for assembly; GCC and GDB
Part 5: Stack and Functions
Part 6: Arithmetic and Logical Expressions
Part 7: Conditional Execution
Part 8: Assembly in Android code

The articles follow in series, each article builds on the previous.

Registers

On ARM processors you have 16 registers. Actually, that is not entirely true. ARM processors have 32 registers, each 32 bits wide. ARM processors have different programming modes to distinguish user-level and system-level access. Only some registers are visible in each mode. In the user-level mode you can access 16 registers. This is the mode you will use most frequently, so you can ignore the entire mode stuff for now. By the time you need to write Linux device drivers, you will be well past this introduction.

The registers are called r0-r15, and the last four are special.
r12: IP, or Intra-Procedure call stack register. This register is used by the linker as a scratch register between procedure calls. A procedure must not modify its value on return. This register isn't used by Linux gcc or glibc, but another system might.
r13: SP, or Stack Pointer. This register points to the top of the stack. The stack is area of memory used for local function-specific storage. This storage is reclaimed when the function returns. To allocate space on the stack, we subtract from the stack register. To allocate one 32-bit value, we subtract 4 from the stack pointer.
r14: LR, or Link Register. This register holds the return value of a subroutine. When a subroutine is called, the LR is filled with the program counter.
r15: PC, or Program Counter. This register holds the address of memory that is currently being executed.
There is one more register, the Current Program Status Register (CPSR) that contains values indicating some flags like Negative, Zero, Carry, etc. We'll visit it later, you can't read and write it like a normal register anyway.

In assembly language, these are all the variables you have access to. If you need to perform any computation, they need to operate upon these registers. Since there are a small number of registers, you need to be judicious in their use. A lot of optimisation boils down to being miserly with register allocation.

Here are all the data move instructions:

	mov	r0, r1

This moves the value from r1 to r0. This achieves r0 = r1

 	mov	r0, r1, lsl #2

Logical Shift Left (lsl) variable r1 by 2 bits, and then move to r0. This achieves r0 = r1 << 2. There is a limitation on how much rotation is allowed: rotation is specified using five bits, so any value of rotation between 0-31 is allowed. The effect of a single left-shift is multiplication by 2.

 	mov	r0, r1, lsr #3

Logical Shift Right (lsr) variable r1 by 3, and then move to r0. This achieves r0 = (int) (r1 >> 3) The effect of a single left-shift is (the integer part of) division by 2.

 	mov	r0, r1, lsl r2

Logical Shift Left (lsl) variable r1 by the amount given in r2, and then move to r0. The value in register r2 should be between 0 and 31. This achieves r0 = (int) (r1 << r2)
LSL and LSR are not the only shifts. There are also Arithmetic Shifts: ASL and ASR that maintain signed-ness. ASR is different from LSR for negative numbers. Negative numbers have leading bits set 1, and ASR right shifting propagates the 1 bits. In case you don't remember how negative numbers are represented, you might want to read a One's Complement review. ASL is the same as LSL because the sign extension doesn't happen when shifting left. Finally there is ROtate Right, or ROR. Rotation preserves all information, the bits are cycled like the barrel of a six-shooter. You can rotate by five bits, which means from 0-31 positions. There is no rotate left, since to rotate left by 3 bits, you can rotate right by 32-3 = 29 bits. Every shift can take either a five bit value or a register that contains a value between 0 and 31.

 	mov	r0,#10

Move the literal value 10 r0. This achieves r0 = 10. This is an example of Immediate addressing, the literal value of the constant is given in the instruction. There is a limit to what can be listed in immediate values. Any number that can be expressed in 8 bits constant, plus 5 bits in rotation is allowed. Anything other that that must be declared as a constant, and loaded from memory. Examples of valid values are 0x10, 0x100 (both using the constant alone), and 0x40000 (using rotate to left)

Loading from and Storing to Memory

The memory on the ARM architecture is laid out as a flat array. No more segment register nonsense of the Intel world. Addressing modes are equally straight forward and easy to remember.

 	ldr	r0, .L3

Move the contents of address label .L3 to r0. This achieves r0 = *(.L3)

 	ldr	r0, [r1]

Move the contents of data pointed to by r1 to r0. This achieves r0 = *(r1). This addressing mode is using a register for a base address.

 	ldr	r0, [r1, #4]

Move the contents of data pointed to by (r1 + 4) to r0. This achieves r0 = *(r1 + 1) since 32 bits are moved at a time. Byte alignment might enforce this, so you might not be able to do "ldr r0, [r1, #1]". This addressing mode is using an immediate offset value.

 	ldr	r0, [r1, r2]

Move the contents of data pointed to by (r1 + r2) to r0. This achieves r0 = *(r1 + (r2/4)). This addressing mode is using a register as an offset, in addition to a register as a bass address.

 	ldr	r0, [r1, -r2]

It is possible to specify the offsets as negative.

 	ldr	r0, [r1, r2, lsl #4]

Move the contents of data pointed to by (r1 + (r2 logical shift left by four bits)) to r0. This achieves r0 = *(r1 + ((r2 << 4)/4)). This addressing mode is using a register for base address, and a shifted register for offset.
You get the picture. The load instructions take the same barrel shift arguments as the move instructions, so LSL, LSR, ASL, ASR, and ROR are all valid.The interesting stuff happens when you have the ability to use a register as a pointer while modifying the pointer and the destination. There are two ways of doing this, post-index addressing, and pre-index addressing. These correspond roughly to the postincrement (a++) and preincrement (++a) operators in C. Here is a post-increment operator

 	ldr	r0, [r1], #4

Move the contents of data pointed to by r1 to r0, and stores the value r1+4 in r1. This achieves r0 = *(r1), r1 = r1 + 1. As before, variants where registers are used as offsets and shifted registers as offsets are valid.

 	ldr	r0, [r1], r2

 	ldr	r0, [r1], r2, asl #4

In pre-indexed addressing, we modify the base address register before loading the address from the memory to the register. This is indicated by an exclamation mark at the end of the address, indicating that it is written first.

 	ldr	r0, [r1, #4]!

Increase the content of r1 by 4, and then move the contents of data pointed to by (r1) to r0. This achieves r1 = r1 + 4, r0 = *(r1)

 	ldr	r0, [r1, r2]!

Increase the content of r1 by the contents of r2, and then move the contents of data pointed to by (r1) to r0. This achieves r1 = r1 + r2, r0 = *(r1)

 	ldr	r0, [r1, r2,  #4 ]!

You get the idea. Any registers r0-r15 can be used where r0, r1, and r2 are used in examples above.
All those examples dealt with loading contents from memory to registers. For storing to memory, we use the STR opcode instead of the LDR opcode. The same addressing modes can be used to store values from registers into memory. Here are a few examples.

 	str	r0, [r1], #4

Move the contents of r0 into memory pointed to by r1, and stores the value r1+4 in r1. This achieves *(r1) = r0, r1 = r1 + 1. As before, variants where registers are used as offsets and shifted registers as offsets are valid.

 	str	r0, [r1]

Move contents of r0 into address pointed to by register r1 *(r1) = r0

 	str	r0, [r1], r2

Move contents of r0 into address pointed to by r1, and increment r1 by contents of r2. *r1 = r0, r1 = r1 + r2

References
Register move instructions and indexing modes is perhaps the hardest part of ARM assembly. You should take solace in the fact that the addressing modes are considerably less complicated than the madness of segment registers on Intel processors.

This is a basic introduction to the registers and addressing modes in ARM processors. In case you want more depth, Jasper Vijn's excellent introduction to ARM assembly covers these topics.

The authoritative technical reference for the ARM architecture is the ARM Application Reference Manual. It contains valuable technical information on all instructions in the ARM instruction set.

Android ARM Assembly: A trivial program (Part 2)

2011-09-05T16:03:00.000-07:00

This is part two of a series on learning ARM assembly on Android. This part covers a walkthrough of a ARM assembly program.

Part 1: Motivation and device set up
=> Part 2: A walk-through of a simple ARM assembly program
Part 3: Registers, memory, and addressing modes
Part 4: Gnu tools for assembly; GCC and GDB
Part 5: Stack and Functions
Part 6: Arithmetic and Logical Expressions
Part 7: Conditional Execution
Part 8: Assembly in Android code

The articles follow in series, each article builds on the previous.

Hello world assembly program

The easiest program that most languages introduce is the Hello World program. If you had followed with Part one, you typed the Hello World program in C. Now generate the assembly language for that example using the command given at the end of part one.

Here is the assembly language program in full:

 1 	.cpu arm9tdmi
 2 	.fpu softvfp
 3 	.eabi_attribute 20, 1
 4 	.eabi_attribute 21, 1
 5 	.eabi_attribute 23, 3
 6 	.eabi_attribute 24, 1
 7 	.eabi_attribute 25, 1
 8 	.eabi_attribute 26, 2
 9 	.eabi_attribute 30, 6
10 	.eabi_attribute 18, 4
11 	.file	"hello.c"
12 	.section	.rodata
13 	.align	2
14 .LC0:
15 	.ascii	"Hello World\000"
16 	.text
17 	.align	2
18 	.global	main
19 	.type	main, %function
20 main:
21 	@ Function supports interworking.
22 	@ args = 0, pretend = 0, frame = 8
23 	@ frame_needed = 1, uses_anonymous_args = 0
24 	mov	ip, sp
25 	stmfd	sp!, {fp, ip, lr, pc}
26 	sub	fp, ip, #4
27 	sub	sp, sp, #8
28 	str	r0, [fp, #-16]
29 	str	r1, [fp, #-20]
30 	ldr	r0, .L3
31 	bl	puts
32 	mov	r3, #0
33 	mov	r0, r3
34 	sub	sp, fp, #12
35 	ldmfd	sp, {fp, sp, lr}
36 	bx	lr
37 .L4:
38 	.align	2
39 .L3:
40 	.word	.LC0
41 	.size	main, .-main
42 	.ident	"GCC: (Debian 4.3.2-1.1) 4.3.2"
43 	.section	.note.GNU-stack,"",%progbits

As you can see, it is quite a lot of code for a simple program. Luckily, most of it is boilerplate. Let's break it down piece by piece.

Declaration and options

 1 	.cpu arm9tdmi
 2 	.fpu softvfp
 3 	.eabi_attribute 20, 1
 4 	.eabi_attribute 21, 1
 5 	.eabi_attribute 23, 3
 6 	.eabi_attribute 24, 1
 7 	.eabi_attribute 25, 1
 8 	.eabi_attribute 26, 2
 9 	.eabi_attribute 30, 6
10 	.eabi_attribute 18, 4
11 	.file	"hello.c"

The first eleven lines are declarations of various options in the ARM cpu. You can ignore them for now. In case you are curious, we specify the CPU type, the way we want the Floating Point Unit (FPU) to operate, and then specify options for the ARM Embedded Application Binary Interface (EABI). The filename is specified on line 11.

Declaring constants

12 	.section	.rodata
13 	.align	2
14 .LC0:
15 	.ascii	"Hello World\000"

The string "Hello World" is specified as a constant in assembly on lines 12-15. It is in the Read Only DATA section (.section .rodata), it needs to be aligned on two-byte boundaries, and the string is specified as an ASCII string. Byte alignment is very important in assembly language programming. You must pay careful attention to data that needs to be word aligned (2-byte), quad aligned (4-byte) or byte aligned (1-byte). In general, you can't go wrong with word alignment, so if you are uncertain, add a .align 2 at the top of data and functions.
The data is specified as a string in assembly, though the assembler writes it out as bytes behind the scenes.

Declaring functions

16 	.text
17 	.align	2
18 	.global	main
19 	.type	main, %function
20 main:

The program consists of a single function called main. Program code is always in the text section, thus the declaration on line 16. It is word aligned (line 17). main is a global variable, and line 18 allows it to be visible elsewhere in the program. Finally, it is listed as a function, and line 20 is a label containing the name 'main'.

Registers and data
Before we look at the function contents, it might be useful to know what the ARM architecture is like. ARM processors are an example of Reduced Instruction Set Computing (RISC). This means that there are few instructions, and most instructions operate on registers. For user programs, there are 16 registers, called r0, r1, r2, .., r15. Each register is 32 bits long. Registers correspond roughly to variables, though they don't have a data type. Most arithmetical and logical operations are performed on registers. The processor can also access the entire memory using load and store instructions.

The registers r12-r15 are special:
r12: IP, or Intra-Procedure call stack register. This register is used by the linker as a scratch register between procedure calls. A procedure must not modify its value on return. This register isn't used by Linux gcc or glibc, but another system might.
r13: SP, or Stack Pointer. This register points to the top of the stack. The stack is area of memory used for local function-specific storage. This storage is reclaimed when the function returns. To allocate space on the stack, we subtract from the stack register. To allocate one 32-bit value, we subtract 4 from the stack pointer.
r14: LR, or Link Register. This register holds the return value of a subroutine. When a subroutine is called, the LR is filled with the program counter.
r15: PC, or Program Counter. This register holds the address of memory that is currently being executed.

Here are some data move instructions:

24 	mov	ip, sp

This moves the value from sp (r13) to ip (r12). This achieves ip = sp.

32 	mov	r3, #0

This moves the value 0 into r3. This achieves r3 = 0
In addition to moving values within registers, you can load values from memory into registers, and store registers into memory. Here are instructions that achieve this:

28 	str	r0, [fp, #-16]

This stores the contents of r0 into the memory location pointed to by (fp -16). Since memory is addressed by bytes, and registers are 4 bytes each, memory offsets are often multiples of 4. This is the same as the C statement *(fp - 4) = r0

30 	ldr	r0, [fp]

This loads the data from memory pointed to by register fp into register r0. This is the same as the C statement r0 = *(fp)

25 	stmfd	sp!, {fp, ip, lr, pc}

This is a multi-register move operation. This moves the registers FP,IP,LR,PCinto the area specified by the register SP. Since SP is the stack pointer, this is the same as pushing registers FP,IP,LR,PC to the top of the stack in a single operation. Once this is done, the stack pointer is updated since it has an exclamation mark.

35 	ldmfd	sp, {fp, sp, lr}

This is another multi-register move that undoes the action on line 25. This reads back the values that were written earlier, popping them from the stack. The combined effect of lines 25 and 35 is to store the important register values on the stack and then restore them. This allows the function to modify them in the main body. We don't restore IP

Manipulating data
Assembly instructions to manipulate data are very basic: you can do basic arithmetic operations: ADD, SUB, and basic logical operations: AND, OR. ARM Assembly language operations are of the type:OPERATION ARG1, ARG2, ARG3 This performs the operation ARG1 = ARG2 OPERATION ARG3. In the above program, you see some basic arithmetic.

26 	sub	fp, ip, #4

This performs the action fp = ip - 4.

Function calls and returns
Assembly language is written as a flat set of instructions: there is very little structure once the instructions are written to memory in the computer. In order to make code modular, functions can be written. Without the protection of the C compiler, assembly programs must manage their own function calling.
The basic function call involves the following structure:

 	.text
 	.align	2
 	.global	functionName
 	.type	functionName, %function
 functionName:
 	mov	ip, sp
 	stmfd	sp!, {fp, ip, lr, pc}
 	sub	fp, ip, #4  @ Space for local variables
 	sub	sp, sp, #8

 
 	sub	sp, fp, #12
 	ldmfd	sp, {fp, sp, lr}
 	bx	lr

Subroutines are required to preserve every register except for r0-r3. So if you need to use the other registers (r4 onwards), you should save them on the stack before over-writing them. The exact function call convention is listed in the ARM procedure call standard.
In order to call a function, you Branch and Link using the BL instruction. The return address is placed in the LR register. To return from a function, you call a branch on the LR register. This is a BX rather than a B to correctly move between ARM and Thumb instructions. (Ignore ARM and Thumb differences for now, they will be made clear later).

Hello World functionality
Put together, the lines 30-33 lines print out the message Hello ARM world. Let's break this down instruction-by-instruction to see how this is achieved.

30 	ldr	r0, .L3
31 	bl	puts
32 	mov	r3, #0
33 	mov	r0, r3

Line 30 loads the address of label .L3 into register r0. The function calling convention is that the first four arguments are stored in r0-r3, and subsequent arguments are stored on the stack. The function to put a value on the screen is called puts, and it accepts just one argument: the string to be printed. The address of this string is stored in the first register: r0.
Line 31 calls the puts function, which consumes r0 and prints the value on the screen. After calling the function, we can expect the registers r0-r3 to be trashed. The return value of the puts is in r0, but we don't care for it.

Line 32 and 33 put together achieve r0 = 0. This is the return value that the main method returns.

Final word
You are now capable of reading ARM assembly and understanding the main elements in the program. As an exercise, you could try reducing the size of the code while keeping the functionality intact.

In the next article, we can examine each piece in some detail.

Android ARM assembly: Device set up (Part 1)

2011-09-05T12:34:00.000-07:00

This is part one of a multipart series about learning ARM assembly programming with Android. This covers motivation and device set up.

=> Part 1: Motivation and device set up
Part 2: A walk-through of a simple ARM assembly program
Part 3: Registers, memory, and addressing modes
Part 4: Gnu tools for assembly; GCC and GDB
Part 5: Stack and Functions
Part 6: Arithmetic and Logical Expressions
Part 7: Conditional Execution
Part 8: Assembly in Android code

The articles follow in series, each article builds on the previous.

Motivation

You might not realise it, but ARM processors are ubiquitous. When I look around my house, I can count eight ARM processors in routers, phones, eBook readers and web servers. There are more ARM processors in my house than Intel processors.

ARM assembly language is perhaps the easiest assembly language in widespread use. The Intel instruction set was developed over years of CPU revisions, which made the Complex Instruction Set (CISC) even more complex. In case you want to learn assembly, the ARM instruction set is simple to learn. Once you know how to write ARM assembly, it is easier to learn Intel assembly.

Finally, ARM processors are being used everywhere. Whether you like the iPhone or Android, they both use ARM processors. ARM processors excel at low-power computing, which makes them valuable for mobile computing, and consumer electronic devices like routers, NAS storage, eBook readers, game consoles and cell phones. Unlike desktop computers, resources are very limited on mobile devices. On such devices optimisation makes the difference between a slow and unusable application and a fast and responsive one.

Thanks to the profusion of Android devices, you can start programming ARM assembly within minutes and at low cost. You don't need to sign an NDA or pay for development tools. If you have an Android phone and a computer, you already have everything you need. Assembly language programming will not require the buttons or the touch-screen. Any device with a working USB port and with root access will do.

Setting up an ARM device with Linux was a monumental effort: you had to buy a dev-kit which easily ran in the hundreds of dollars. Then you struggled to shoe-horn Linux onto the tiny device. With Android, you already get an ARM device running Linux. All the device drivers are in place. All you need is a Linux distribution that allows you to get the native development tools. This is considerably easier. It should take around an hour of effort.

At this point, you have a choice. You can either go with setting up your own device, which lets you develop on a real ARM computer. Or you can download a prebuilt QEMU image.

Choice A: Emulation
This is the easy choice. For this, you need a computer: Windows, Mac, Linux, all are good.

QEMU is a full CPU emulator that can emulate an ARM computer. It is capable of running the full Android stack, and is shipped with the Android SDK. QEMU is much easier than setting up Linux on Android. To start, download and install QEMU on your system and a utility to extract RAR files. I have prepared QEMU images with the full software development environment.

Download all three files [part 1], [part 2], [part 3], and then run this command:

$  unrar x arm-qemu.part1.rar

This will create a directory called ARM. You can enter that directory and run the command runme.sh. It will start up the virtual machine. The virtual machine is slow, so be patient. The administrator has username "root" and password "root".

Choice B: Using a real device
In this case you install Linux on your Android phone.

You need:

Android phone with 2GB free space on the SD card
Any computer with USB

Obtain an Android phone on which you can get root access. If you have a working Android phone, you can use that. Otherwise you can buy a used Android phone. Install Debian on it using Jay Freeman's instructions on getting Debian on an Android phone.

Another option is to buy an ARM device like this Zipit. This is a harder option. Many devices have poor support, and installing Linux can be a herculean task. I would recommend sticking to an Android phone unless you have easy access to an ARM device and you know that you can install Linux on it easily.

Once you have Debian working, you need to create a user and install ssh to allow easy access to the device from your laptop or desktop:

phone$ sudo adduser # Create a normal user for dev purposes.
phone$ sudo apt-get install openssh-server
phone$ sudo /etc/init.d/ssh start

You now have a working Debian installation that you can access using SSH. To ssh into your device, you can use port forwarding with the Android Debug Bridge (adb) to forward the desktop's port 2222 to port 22 on the phone as follows:

desktop$ adb forward tcp:2222 tcp:22

Finally, you can login to your phone from your desktop as follows:

desktop$ ssh user@localhost -p 2222

Once the port forwarding is working correctly, you can also login from any computer on your network as follows:

desktop$ ssh user@mydesktop -p 2222

This allows you to connect to your ARM device from any computer in your house. You can punch holes in your firewall by forwarding ports from the firewall to port 2222 on your desktop's IP address, and be able to access your ARM device from anywhere in the world. Even if the screen has turned off, you will be able to ssh into it, edit, compile and debug programs.

Congratulations. You now have a completely silent ARM device which you can connect to from anywhere.

Once you have Debian installed on your device, you can get the development system using apt-get:

phone$ sudo apt-get install gcc gdb make vi emacs

Install the editor you prefer: vi or emacs. Now, your phone is a fully capable ARM dev environment.

Test the development tools
You can try a simple C program to verify the setup.

/* hello.c: Hello World program */
#include <stdio.h>

int main(int argc, char* argv[]){
  printf("Hello ARM World\n");
  return 0;
}

You can compile this and run this as follows:

phone$ gcc hello.c -o hello && ./hello

If you have got this far, you can get a sneak peak at ARM assembly with the following command:

phone$ gcc hello.c -S && cat ./hello.s

This shows you the intermediate Assembly language from the Hello world program.

Congratulations, you have turned your Android phone into a full-featured ARM dev kit. The next article will cover programming your device in Assembly language.

The Linux Programming Interface: a beautifully written technical book

2011-08-29T20:52:00.000-07:00

I have been reading, "The Linux Programming Interface" recently. It covers everything about the Linux programming environment: the layout of process space in memory, threads, signals, sockets. Nearly everything you can think of while programming Linux is covered here. Go get it. Now.

It is a beautifully written book. The author, Michael Kerrisk, combines technical knowledge about Linux internals with a clear, precise writing style. This book is fun to read. I have used Linux for many years now, and I found the chapters both illuminating and delightful. At first, I picked it up to learn about memory layout in Linux. I found the writing style so good that I read on, finishing not just that chapter, but many others. I have been reading a chapter at a time at random since. Each chapter deals with a single topic (e.g. Threads) and consists of roughly 25 pages. This is an excellent organisation: it lets you completely understand one area at a time in manageable chunks. Its 64 chapters are spread across 1500 pages, giving it unprecedented breadth and depth.

Technical books are difficult to write. The subject matter can be dry and the terminology makes sentences verbose and difficult to parse. In addition, there is a problem of target audience. You can assume the reader knows too much, making the book inaccessible. Or you could assume too little, and require the reader to go through trivial material that they already know. In addition, technical books are often read with a purpose in mind. They need to answer the question, "How do I do X in Linux" in minimum time. Remarkably, this book does well along all these dimensions. It is a case study in pleasant, lucid writing.

If you do anything with Linux, and have ever programmed in Linux, get a copy now. Keep it on your shelf, and leaf through it when you are bored. You will enjoy the book, and learn more about Linux while doing so.

Be more productive at work

2011-08-28T20:55:00.000-07:00

I have learned a few things about enhancing my productivity over the past few years, by observing my own productivity at work. These rules should work for anyone whose work requires concentration, creativity and thought.

Here goes:

Get a quiet room. If your job requires thinking of any kind, it needs to happen in a quiet place. In case you cannot get a quiet room, invest in a pair of good earplugs. I recommend the Howard Leight Laser Light earplugs. At $20 for 200 pairs, it is a steal. If you do get a box, hand them out to your co-workers to improve the entire team's productivity. Even if you think that a noisy room works for you, try out a pair of earplugs first. Chances are that you, like most of humanity, will prefer a quiet room. If you work in an enclosed office: you are lucky! Consider submitting my resume to your recruiters.
No distractions. This is essential to keep you in flow. What works for me is to wear my earplugs and display a sheet of paper that says, "Do not disturb". Yes, you look like a douche-bag and you feel anti-social, but the feeling quickly passes. Additionally, you can indicate that if people drop you an email, you will go by their desk when they are free. This reduces the chances of people mistaking you for a self-important jerk. Apologise in advance, and mention what you are working on. I use an IM status like this "Do not Disturb. Need to finish Project Wallaby. Please email. Apologies :(" I also block off time on my calendar to focus on a single activity. This reduces the chance of someone scheduling you for a meeting when you're in the middle of a task.
Respect people's time. Meeting with people is essential. I choose to meet people in their office at a scheduled time. When I do meet someone, I avoid checking email, and I avoid looking at my phone. If someone is spending time with you, respect their time in addition to yours. Ditto for meetings. If you are checking mail in a meeting: you should consider avoiding the meeting entirely.
Stop when done. I usually set a goal and try to finish the activity as soon as possible. When I am done, I stop and take a break. This is essential to getting a feeling of accomplishment. Plodding through the day is much easier if you get regular shots of satisfaction. Break up work into 2-3 hour chunks, and try to finish a task before allowing yourself to be distracted. Over time, you'll find that your productivity improves, so adjust your expectations. Once you are done, go for a short walk, or look outside. Give yourself some time to relax before tackling the next objective.
Beat inertia with a trivial task. I find it much easier to get back into work if I have something trivial that I can hammer out early. This could be a simple bug or a trivial feature. This allows you to get in the mode of work with minimal hassle and beats inertia.
Hardest job first. Once you have beaten inertia, go for the hardest task of the day. Concentration, focus, and decision-making are their best in the morning after a full night of rest. Once you've done the hardest task, you have the added benefit of knowing that the remaining day is easy.
Full night's sleep. Research suggests that a full night's sleep is critical to improving your concentration. If you are constantly tired at work, napping might help. Many managers frown upon napping, so exercise caution if you need to go down this route.
Love your work. It is easy to work hard at something when work is fun. It might be too late to change jobs, but try to find interesting projects and interesting people to work with. My productivity is high when I work with peers whom I respect and from whom I can learn.

This wisdom is from personal experience, good books like "Peopleware" and "The Mythical Man Month", Randy Pausch's talk, and many online resources.

Many activities at home require concentration and focus, and work is no different. At home, I love reading a book or playing with computers. I think of the atmosphere that allows me to enjoy my home activities and I try to recreate the same atmosphere at work. You might consider trying something similar. Find an activity you love, and identify what atmosphere allows you to enjoy that activity completely. A similar atomsphere at work might help improve your productivity.

Why software patents lead to poor usability

2011-08-19T18:23:00.000-07:00

I'm a big fan of usability. I think that usability is the next goal, not features. Products are being distinguished based on how usable they are, rather than how many features they have.

In the physical world, usability is improved by

Making the underlying process visible. An example is a small light that glows when a device is turned on. Glowing lights indicate that electricity is flowing through the device, which suggests that now the device is on.
Improving the mapping between the action and the object that causes the action. Switches have only two positions: on and off, corresponding to the two states of a lamp. Volume controls are dials that you rotate indicating a range of possibilities. Doors have handles that indicate which direction they can be pulled.

Good interfaces in the physical world rely on making the system clear to the user. When interfaces don't follow any logic, they have been standardised: all cars have driving controls in very similar locations.

Computer usability is somewhat arbitrary, though. There is no real-world analogue for a menu-bar, or a right click, or a context menu. There is no real-world analogue for task-switching. The pioneers in computer design could adapt some real-world objects as metaphors for computing actions. Thus the pervasive 'desktop' metaphor for objects on the computer, even though it now has nothing to do with a real desktop. But metaphors are rare and much of the interface was incidental and arbitrary. Like the use of the QWERTY keyboard for all English-language computers, and the arbitrary position of the menu bar (top of the window) and the status bar (bottom of the window).

When usability cannot follow any logic, the easiest solution is to standardise. In his book, "The Design of Everyday Things", Donald Norman shows how the design of a wall clock is arbitrary and illogical. But around the world, every wall clock looks identical, which allows you to read a clock. The placement of the accelerator and brake pedals, and the control sticks on the car is similarly illogical. There is no good reason for the wiper control to lie to the right, and the light control to lie to the left of the steering wheel. But every car seems to follow this. The result is a breathtaking advance in usability. You can rent a Toyota Sienna or step into a Ford Focus and drive it without any instruction. Once you know one car, you can drive nearly every car.

Computers aren't like that, here are the trash bins from Windows and Mac OS:

They both look pretty similar, but not exactly. A user who has been seeing a clear glass recycle bin will look for something similar on OS X. It takes some time to identify these similar features and their related mappings: 'Recycle bin' versus 'Trash can'. Trash cans are just the start of it. Computer systems differ along all these characteristics: the placement and position of the menu, the types of icons, the keyboard behaviours. Even turning off a computer has no agreement. Some computers have a physical off button on the keyboard, some have an icon on the top right, some have menu items. Software to perform the same action looks very different on different systems.

Where computers have standardised, it has been a success. Computers all use the same keyboard and mouse, thankfully. And some keystrokes (Ctrl-C, Ctrl-V) are common across platforms and programs.

The reason why software cannot look identical across products is due to software look-and-feel patents. Look-and-feel patents allow the patent holder to maintain exclusive right to how a user interface looks. A good example is the recent patent litigation on a phone's look and feel. These patents have been around for a while now. So has the resulting litigation. Patents of this nature disallow someone from providing a similar look-and-feel of an established product, which makes it impossible to standardise on an interface.

As a result, consumers have to deal with the explosion of interfaces. Using a new phone is much harder than using a new car!

I don't want to highlight just one company: many companies are involved in this. Such litigation has existed for quite some time now. One of the early lawsuits between Apple and Microsoft about the look-and-feel of the Windows system was filed in 1988. As a result, Windows could not look similar to Mac OS. Windows developed its features in isolation, which Mac users had to painfully adapt to when they switched to Windows. Many years later, Apple developed the popular OS X operating system and many users switched from Windows to Mac OS, they had to painfully learn the new interface.

Innovation is key to generating new products, though radical innovation in the interface is harmful rather than helpful. Cars have had the same control mechanism for many years now. Yet they have had some innovation within the confines of the interface. Cars are more comfortable, safer, and consume less fuel than those in 1960. Yet, you could probably step into a car from 1960 and drive it.

While computers have become faster and more capable, they have not made much advance in standardising interfaces. New systems have their own bewildering interface that require learning. People dislike upgrading because they will have to learn the new interface to perform the same actions that they used to perform earlier.

It is our responsibility as users to demand consistent interfaces. We can buy a new car and can safely transfer all our driving knowledge to it. We should be able to buy a new computer and be productive with it right away.

1 Watt webserver

2011-08-16T20:26:00.000-07:00

I recently bought a Zipit 2 from an online store. It is a tiny device with an ARM CPU (XScale-PXA270) with 32MB of RAM, an SD card slot, and 802.11 networking. The device cost me $30 including shipping, which is a cheap price for the computing potential. My goal was to run Linux on it, and learn the ARM instruction set. There are many Linux distributions for the Z2, and I found Debian on the Z2 to be perfect. The device is small, light and fits in the pocket of my jeans. Its battery lasts four hours when the screen is on.

Installing Linux on it was trivial: you flash a custom bootloader using FlashStock. This loads a new kernel on the small flash partition on the device, and it gives you the ability to boot from an SD card. Then, you download a Linux distribution for the z2 (I chose z2sid), copy the image to the SD card (using a raw copy tool like dd) and boot from it. I have an 8GB SD card in the Zipit. This Z2 is better than my first Pentium computer along every single dimension except screen size.

Once Debian is installed on the Zipit, you have access to the 'apt-get' package management tool. After installing vim, gcc, make, it turned into a fully functioning ARM development system. I did not want to type using the tiny keyboard, which is uncomfortable and lacks important keys. So I installed an ssh server called dropbear. Now I can remotely log in to the device, copy files back and forth, and use it for development.

Once it was set up, I wondered if I can serve web pages from it. After installing a webserver called nginx, the zipit holds up very well. I'm serving three virtual hosts externally from it, and two hosts internally. For a small amount of traffic, this is the perfect device.

Power consumption

With the screen turned on, the Zipit consumes less than 2 watts of power. When the lid is shut, the screen turns off and power consumption drops to 1 watt. By comparison, a typical laptop consumes 30 Watts and a typical desktop consumes 100 watts. The device is dead silent and cold to the touch. Due to the low power consumption, it generates no perceptible heat. You can leave it in the corner of a cramped closet, and it will chug away. Silently.

There is a lot of potential in these low-power devices called plug computers. Plug computers and mobile devices have caused a resurgence of ARM processors due to their low power consumption. With improvements in processor technology, an entry-level ARM CPU can handle tasks reserved for a "real" computer. Web serving, file serving and ssh-login don't require a beefy processor. Rather than maintain a full computer, you can purchase a small, silent, and low-footprint computer to handle these tasks for you. Once it is set up, you can store it in a closet somewhere, completely out of sight. Low power consumption allows the device to run exclusively on solar power.

You could use it as an entry point to a home network. Once the SD card is copied to a desktop, you can recover from a malicious attack by copying a known-good image back onto the card.

Low-power computing holds a lot of promise. In the developed world, it can be used instead of power-hungry computers for routine tasks. In the developing world, it can be the first computer for a family.

The importance of staying mentally agile

2011-08-10T21:00:00.000-07:00

I am a software engineer, and I get paid to write software and design software systems. In my spare time I write other code: Arduino and microcontroller code and Android code for my phone. Over the past few days, I have been modifying my site's CSS and HTML to ensure it looks just right. Forget just right, I wanted it to look darn near perfect, even if it meant knowing everything about CSS layout.

After a few days of not writing software or constructing anything, I get itchy. At the very least, I find reading technical documentation and learning about the innards of systems very liberating.

I didn't understand why this is so until I was discussing mental agility with a friend. He mentioned that, in his job, he felt his skills were wasting away. He felt that he was getting slower. He thought he was taking longer to learn new systems. After this discussion, I realised that I am scared of losing mental agility. A lot of my home-hacking is done for fun: I love playing with an Arduino and electronics. But I suspect that deep down, I am also motivated by a fear of slowing down. I don't want to reach a point when I cannot learn something new, because my livelihood depends on learning new things quickly and in sufficient detail.

Intelligence is more than just mental agility. Intelligence includes quick learning, and also requires good communication and abstract thought. But the ability to quickly learn a new area is critical. Even if I wasn't an engineer, I would be working in a profession that required quick mental thinking. Learning an arcane instruction set won't make me smarter (more intelligent). However, I will get the mental rush of learning something new. And I'll know that I have the mental agility to learn something new to sufficient depth. In the future when I'm required to learn something completely new, I will be prepared for it.

In the case of my friend, his fears are unfounded. The guy is a talented engineer and a quick learner. He is certainly faster than I am at learning new things.

Ironically, the people who are worried about slowing down are the ones that never slow down. They drive harder, keep picking up new skills and keep sharpening their powers of learning.

The people slowing down are the ones that aren't worried about slowing down. If you're worried about slowing down: you're probably doing fine.

Beautiful, professional resumes with LaTeX

2011-08-07T16:18:00.000-07:00

I love LaTeX, but when it comes to resume writing, my skills at LaTeX fall short. This means that I have to load up OpenOffice, and spend hours tuning every single spacing and pagination problem.

Enter Moderncv, a class file for professional looking resumes. If you use LaTeX, it is the perfect document class for writing a resume.

This is what my resume looks like:

You can download the resume in PDF. This resume was generated from this LaTeX source file.

The moderncv class is straightforward: you fill in the details and it generates a beautiful, professional resume for you. Once you fill in the critical details, the page layout is handled for you. So if one section is too big it is automatically shifted to the next page. You fill in the contents, LaTeX handles the rest.

Itching to give it a try? To get started, download the moderncv class from CTAN. Either use my resume as an example, or look through the examples directory for a file called 'template.tex'. On Ubuntu, you need the texlive and texlive-latex-extra packages.

On Ubuntu or Debian machines, you can download all the packages with:

$ sudo apt-get install texlive texlive-latex-extra

Lego NXT Mindstorm with Linux

2011-08-07T07:37:00.000-07:00

There is a lot of documentation on the NXT and Linux on the Internet. A lot of it is very good, like this page showing Linux setup with NXT. Unfortunately it is scattered all over the place, making it difficult for a complete newbie to make headway with the Lego Mindstorms on Linux. This page links to the major steps and will enable you to set up Linux-Mindstorms communication and the programming environment.

Why Linux?

Linux is better suited for Lego programming. It is essential if you have a Linux machine, and don't want to install Windows (or MacOS) just for using the Mindstorm. But the advantages of Linux go beyond that. Linux is a great programming environment, and interfacing it with Mindstorms allows you to connect it to other devices. Linux machines have a good programming interface for Bluetooth, GPS, networking through the Internet, sound, display, and large-scale processing. Connecting the NXT to a Linux device opens up a lot of possibilities.

Also, many netbook computers are ideal robot building blocks: they are small, light and lack fragile spinning disks. Linux is space efficient, and runs well on these devices.

Journey

These are the steps you need to be completely up and running with Linux and the NXT. These pages are listed in order, and each page builds upon the previous work.

With a little bit of setup, you can combine the flexibility and design of the Mindstorms with the power of Linux.

Alternate ways of viewing this site

2011-08-06T22:23:00.000-07:00

This site is hosted on Blogger, which allows alternate views on the same content. Here are some views you can try:

Sidebar view: the content takes the entire screen. The list of posts is in a left bar which is good for small laptop screens. This is my favorite alternate view.
Flipcard view: all posts appear as two-sided cards. Clicking on the card takes you to the post. The top navigation allows different sorting methods.
Snapshot view: all posts appear as instant-camera snapshots.
Timeslide view: for seeing the entire site arranged by time with recent posts on the top.

These views allow you to explore the blog in a more flexible way than traditional page views.

What to look for in a manager

2011-08-05T23:09:00.000-07:00

After having worked with a few people, I have narrowed down the skills needed by a technical manager down to two qualities. While these are observations from software engineering and business analysis, the lessons hold for other technical professions. Here are the two qualities.

Provide creative space. This is essential for technical areas like software development where creativity and risk-taking are essential. After confirming a general direction, the manager should be willing to let the employee explore and learn from mistakes. An excessive amount of top-down direction is frustrating and demeaning to a capable employee. This requires technical skill in the manager, so he can set general direction and realize the amount of work involved. Providing creative space also means ensuring that the employee has a distraction-free atmosphere, and meetings are kept to a minimum.

Without the freedom to make mistakes, a technical employee feels bored, demotivated, and does all his creative work elsewhere (at home, or with friends).
Reward technical achievement. Many projects look deceptively simple from the outside, but require significant work to be successful. A person who ensures that technical work gets rewarded makes an excellent manager. This is critical when the employee's achievement might not yield immediate benefit: large-scale re-factoring of code leads to immense long-term gains and short-term discomfort. Therefore, strong managers understand the benefit of code hygiene and reward engineers for improving the quality of the system.

Without recognition for hard work, employees settle for low-risk high-visibility projects. Over time, challenging technical work dries up, since nobody is willing to solve real problems. Once this happens, the team loses the ability to hire fresh talent, because they have no interesting projects. Also, a manager who either cannot recognize technical achievement or does not spend time rewarding achievement is seen as spineless. Such a manager quickly loses respect among skilled engineers.

In the best teams, recognition flows downward and blame flows upward. A good manager shields a well-functioning team from missed deadlines and temporary failure. And when things work, he highlights individual engineers for their contributions and ensures recognition for them. Sounds too good to be true? Managers like this do exist.

Truly exceptional managers inspire confidence and motivate their employees. Work is fun because employees are interested in the problems they are solving.

You can judge a team's technical manager approximately by assessing two things.

Quality of technical work: quality of code, and challenge in existing projects. Excellent technical work speaks for itself. It shows that the team values technical achievement and rewards it.
Amount of time employees spend dealing with fluff: number of hours spent in non-technical meetings is a great estimate. Any manager who frees his employees' time values their time and their contribution.

The age of technology? The age of the interface

2011-07-31T10:35:00.000-07:00

When computers were new, they were capable of doing things that were labor intensive: calculating payroll, accounting and billing. People who were able to buy computers were also the people who could spend hours learning them. Early hackers were also engineers, or at least bored students with lots of free time who were happy to learn the minutiae of the system. They were happy to go through large volumes of programming manuals, datasheets. The rewards were rich: you got to be the master of a computing machine that did exactly what was told. Products at this time competed on features alone: new features might have been cumbersome to learn, but the customers didn't mind.

That was the age of technology, and we aren't in it any more.

Now, we're in the age of the interface. In the past few years, we have seen the rise of great products which aren't competing on feature-set alone. The iPhone is a perfect example of this: in functionality alone it was comparable to other devices in the market. What made it appealing was its ease-of-use, it's computer interface. The daily interaction with the device were much better than other cell-phones, and that convinced users to switch. I see this trend in many areas.

Arduino is a microcontroller board and development software that allows you to attach physical objects to computers. The underlying microprocessor is made by Atmel, and it has been around for a lot of years. Arduino's contribution is to package the hardware and software in an easy-to-use, accessible package. You buy the microcontroller board, download their free development software, and can have a programming running within minutes. Arduino makes it trivial to try out microcontroller hacking, and it has led to an explosion in creative hardware hacking. Arduino programs are called 'sketches' and the software makes it easy to share your sketches with others.
Processing is a programming environment that makes it easy to visualize data. Processing is built on Java, and is much easier to learn than Java. Arduino and Processing are very similar. With Processing too, you download free software which runs on all platforms. It allows for fast programming: a child can start programming graphics routines within minutes. Processing makes easy tasks trivial and hard tasks possible, all without having to teach a person the nuances of programming. Processing code compiles into four different programs: one each for Windows, Mac, Linux, and a Java applet. Processing also has an Android mode that allows you to run your processing code directly on an Android device.
Fritzing is a development tool for electronic circuits. You can design the circuit as an physical layout (with bread-board, wires and components), or as a schematic diagram (big boxes rather than pictures). It does a splendid job of making hardware traces that can then be used to fabricate Printed Circuit Boards. Also, you can share your projects with other people by giving them a copy of your .fzz file. Fritizing makes it easy for a student to design a circuit board and have it mass-produced.

All these projects make it easy for a newbie to get started. They all provide software for Linux, Mac, and Windows, and they all make it easy to share your creation with the world. This has resulted in many more people getting involved with electronics and software hacking. It has opened this world up to people who were unwilling to read through thick programming manuals.

People are no longer interested in feature-sets. The feature world has been saturated: people who care for spreadsheet features already have all the features in their spreadsheet. Now, the goal is to make a spreadsheet that is accessible to the rest of the population.

Fewer features, ease of use, and excellent design. Software engineers are learning that good products are easy to use and well designed rather than a random collection of good features.

Image courtesy Jeff Atwood.

GPS datalogger with Arduino and SD card

2011-07-30T11:37:00.000-07:00

I recently finished making a GPS datalogger with an Arduino, a micro-SD card, and an old USB GPS unit. It continuously logs the position from a GPS unit to an SD card.

The connections are trivial with a 3.3V Arduino, since the micro-SD card has an SPI interface which the ATmega328 supports natively. I used a SiRF GPS unit, which outputs NMEA sentences at 4800bps. This was connected directly to the serial pins on the Arduino. With a 2GB SD card, we can log everything that the GPS outputs for well over a year, so I didn't bother filtering the GPS output.

The bill of materials is:

3.3V Arduino, or appropriate level shifters for the SD card
GPS unit with a serial interface
SD card or micro-SD card slot and memory card
Some power source: car 12V plug, or USB, 9V battery

You can download the entire GPS datalogger Fritzing project. The connections and the schematic are shown below:

The associated Arduino program is trivial:

#include "FileLogger.h"

#define HEADER "Starting GPS logging.\r\n"
unsigned long header_length = sizeof(HEADER)-1;
byte header[] = HEADER;
unsigned long data_length;
byte gpsdata[128];

void setup(void) {
  Serial.begin(4800);
  FileLogger::append("data.log", header, header_length);
  data_length = 0;
}

void loop(void) {
  if (Serial.available() > 0) {
    gpsdata[data_length] = Serial.read();
    ++data_length;
    if(data_length > 127) { 
      FileLogger::append("data.log", gpsdata, data_length);
      data_length = 0;
    }
  }
}

The Seeduino Stalker is an excellent Arduino-SD card combination that can be used for this project.

This GPS datalogger can be powered from a 12V car plug for continuous logging of a car's position. This is useful to monitor the driving habits of your teenage child, or to log the route of a long cross-country drive. Another use is for logging bicycle trips automatically (powered from solar energy and a 9V battery for backup).

This device requires no user interaction. It starts logging when the device is powered on. If the Arduino has an LED connected to pin 13, it will blink when new data is being written to the card. At the end of a month, you can copy the contents of the SD card to a computer for analysis.

Most of the Arduino pins are unused, so there is hacking potential.

Whose advice do you trust?

2011-07-23T17:30:00.000-07:00

One of the most difficult things about parenting (and pre-parenting) is knowing whose advice to trust. As a parent, many things are completely new and it is difficult to know the right way to do something. Many people offer to give advice, and while people are well-intentioned, their method might not work for you. The central problem is: whose advice do you trust?

After listening to conflicting advice from many people, I have a reliable method of determining whose advice to trust:

Trust the advice of people with many friends from diverse backgrounds.

I arrived at this idea after looking at the people who have given us good advice in different scenarios. It seemed that the people with the best advice also had many diverse friends.

Why? When a person has many diverse friends, it displays two qualities:

Access to a wider variety of human experience.
An ability to handle criticism and a difference of opinion. Being able to hear someone out is good, but being able to patiently hear why you are wrong is a true skill. Being thin-skinned about a topic usually cuts short the conversation before you can see an alternative solution to a problem.

My friend calls this the "Pagerank" of human advice. While I had not thought of it in those terms, it makes complete sense. People are knowledgeable because of whom they know, not just what they know. When people have a lot of diverse friends, the increase in knowledge is not just linear. It is exponential, as they can relate to how Mary had a similar problem that Bob is talking about, even though Mary and Bob have completely different backgrounds. This allows them to identify patterns of problems and patterns of solutions, which is more valuable than knowing a single solution for a single problem. Also, having a wider set of friends allows you to learn from others' mistakes before you face the same situation.

Low sensitivity to criticism helps in accepting alternate methods of solving the same problem. Being receptive to new ideas allows us to identify new methods rather than being stuck in a rigidly defined solution. You can measure the receptivity of a person when you decline their suggestion. A person who takes offence when you decline their suggestion has low levels of receptivity. Such people also have the poorest suggestions. The best advice is given by people whose interest is piqued when you say you are going to do things differently. They don't feel offended when someone declines their advice. Indeed, they want to know the alternatives because they actively seek other ways of solving the problem.

My friend also pointed out that the two qualities listed above might be present in a person lacking diversity among their friends. This could happen when a person has lived in a homogeneous society and does not have access to people of diverse backgrounds. I suspect that in such cases, the people will form lasting friendships with diverse people if they get a chance. I know some people who have grown up in homogeneous societies, and they still have a diverse group of friends for their limited surroundings. Their group might be homogeneous by some respects (ethnic background, religion, etc) but will be completely diverse in others (education, parenting, occupation, age...)

Microcontroller driven LCD panel with voltage measurement, time, EEPROM for computers

2011-07-17T11:34:00.000-07:00

I just finished making a circuit to drive a four line LCD panel from an Arduino. The project started out as a way to drive the LCD to display arbitrary information, but then evolved into a way to tell the time, read and write the EEPROM from the Atmel 328p, and measure voltage. I'm using many existing libraries: the Time library, and the two Controller LCD library.

The final functionality is:

Commands are sent over USB using vi-line syntax. All commands start with ':' character.
Segments the 40x4 display into 8 segments of 20 chars each. Segment 0 is column 0, line 0. Segment 1 is column 20 line 0. This allows an easy way to display up to eight different status updates. To write "hello world" in segment 3, you write ":s3helloworld\n" to the serial port.
Read and write from EEPROM. The 1028 bytes of EEPROM is chunked into 8 segments of 128 bytes each. Segment 0 cannot be written to, which allows for 128 bytes of ROM. To write a segment 3, you index (:i3), then write (:wMySecretMessage\n). To read from EEPROM, you index first (:i3), then read the full segment (:r).
Time can be read from the device (:t) and the time can be set using Unix time (:T1310349445).
Voltage monitoring at analog pins can be toggled (:a). Voltages are displayed on the LCD (display shows all six pins in decivolts: 5.0v is written 50) and written in raw form on serial (relative to 1023. 1023 = 5V, 0=0V)

The entire Arduino source code is available as FourLinePanel.pde. It still has some debugging information left in, it prints the value of every new command it receives. This debugging could be removed. It supports a few commands:

:t Displays the time
:T<unix time> sets the time
:l<message>\n Writes message to current position
:sN<message>\n Writes message starting at segment N
:a Turns on analog voltage monitoring on LCD and serial
:r Reads 128 bytes from EEPROM at current location
:iN Index into segment N of the EEPROM
:w<data>\n Write data into EEPROM starting at current location

This requires one Atmega microcontroller, an LCD panel, two 22pF ceramic capacitors, and one 16Mhz crystal. To interface it with USB, a USB to serial cable might be required. In my design, I'm driving the entire project using power from the USB port. This minimises the need for voltage regulation and additional components: power over USB is usually clean. You can download the schematic for the FourLinePanel here.

To interface with a computer, you read and write to the serial port with 38400 bits per second, no flow control, and no parity bits. An example program to interface this with Python is given below.

import serial, time
# Set the time on the FourLinePanel for GMT+5hrs
# offset from GMT: Add 5hrs
offset = 5*3600
port = "/dev/ttyUSB0"
fourLine = serial.Serial(port, 38400);
fourLine.write(":T" + 
               str((int)(time.time() + offset)))

There are five spare digital pins that could be used to drive a Real Time Clock or LEDs. These are marked as "Spare Digital (unused)" in the circuit diagram [png], and circuit diagram [ps]. The analog voltage testers can be used as handy ways to measure voltage at the desk when a multimeter isn't handy, or to constantly monitor the voltage drop across a device (like a photovoltaic cell).

Who is Secret Labs, and why the Netduino project makes me nervous

2011-07-15T06:53:00.000-07:00

I'm a big fan of the Arduino project. It is a micro-controller board that makes hardware programming fun. It is supported on all platforms, Windows, Mac and Linux, and works equally well on all of them. Arduino has fired off creativity in micro-controller hacking, and one product that caught my attention was the Netduino project. The board looks like the Arduino, but it uses the .NET framework by Microsoft.

A lot of what I found about Netduino was suspicious, so I thought I'd share this in the hope that someone could clarify the situation.

For an electronic project, Netduino is too good to be true.

The Netduino contact page is very sparse: it contains a physical address (Secret Labs LLC, 315 Bleecker St #308, New York, NY 10014), an email address (webmaster@netduino.com), and a link to the online forums. The Secret Labs LLC website contains exactly this information. Almost nothing is known about them.
The only name associated with Secret Labs is a person called Chris Walker. He is the only moderator of the Netduino forums. This is strange: I would expect Secret Labs to have a lot more than one technical contributor and a lot more people involved.
I couldn't tell any source of funding. Is Secret Labs making money from the Netduino product? Hardware margins are probably too small for this to work. How does Chris Walker pay his rent? Do they have Venture Capital funding? I wasn't aware of open source hardware being a VC magnet.
They have designed and developed the entire product, and it is available for purchase at major electronics stores like Sparkfun. The design is polished and crisp, too crisp for a version 1 product by an unknown company.
The Netduino plus contains an ethernet port, for which they have 5C:86:4A MAC address prefix. Applying for MAC addresses takes some effort, so it is impressive that Secret Labs LLC has done so much groundwork.
All their source code is available from files hosted at netduino.com. There is no public source code repository: no tracking of who made changes, and when. They claim to be an open source project, but if I want to submit improvements, there is no email address or contact in the source code. All source code is copyright Secret Labs LLC. A real hacker would love to get improvements from the community. The source code is not professional: comments are missing, and stale code is commented out when it didn't work. From the look and feel of the source code, I would guess a very small team, and a very hurried release. It was most probably developed in September 2010, which is very close to the release of the .NET Micro framework.
From a cursory look through Google Maps, 315 Bleecker St. looks like a residential address. What's worse, the Better Business Bureau lists 318 Bleecker St #308 as a Payment Processing Service called SimplePayClix, with the listing opened in March 18, 2010.
The domain netduino.com was first created on 16 January, 2009, while Netcraft first saw it in March 2009. This is very surprising. The netduino.com domain was registered before the Secret Labs LLC was created. Microsoft announced that they would open source the .NET Micro Framework on 16 November, 2009. Did Secret Labs LLC work on a product even before they knew that the framework was going to be open sourced, or were they working on a different design that wasn't released? The owner on secretlabs.com is Chris Walker again, with address cwalker@secretlabs.com.

The Netduino project looks very impressive, and if it is the work of a few people, they are very smart and very capable indeed. But it doesn't look anything like a community-driven project. Only one person is visible, and I find it hard to believe that he has developed the hardware, the software, the book, the documentation, the video tutorials, the forums. All in isolation from the hacker community.

It is entirely possible that Chris Walker is independently wealthy, is an expert electronics and software hacker, is amazing at website design, and has good relations with electronics manufacturers. But I smell a rat.

Update (23 July 2011): Read the first comment for all the answers.

More about Chris Walker of Secret Labs: he has a Channel 9 account 'cwalker_secretlabs', created this year. He gave a podcast interview about the Netduino. OReilly is about to publish a book called "Getting Started with Netduino" by Chris Walker, which will be released soon. Chis Walker is listed as the CTO of Secret Labs in one article. There is what he looks like. Later this year, he is giving a talk titled "Connecting Devices to the Cloud on Open Source Hardware and Software", at Oreilly's OSCON on July 27, 2011. His co-speaker is Colin Miller, who is a Product Manager for the .NET Micro Framework.

Why is Bombay a target of bomb blasts?

2011-07-13T19:50:00.000-07:00

There were another set of bomb blasts in Bombay. My heart is with the families of the affected people.

Security in India is pretty bad. There is a culture of lax security.

In my experience, the police have been unhelpful and unable to enforce laws. The airport police are slightly more diligent than the regular force inside the city, but both are relatively incompetent. At the International airport, I have seen passengers walk away without their bags being scanned through the machines. On one occasion my bag was run through the scanner but there was nobody looking at the scanner to see what I was bringing in. It is easy to see how dangerous, explosive material could have been brought in.

Inside the city, the police are equally lax. I do not remember approaching the police when there was any problem. The police were a nuisance rather than a service and a convenience. The police were happy to assert their authority and harass students and poor people, while avoiding their responsibility to enforce laws. The porous border with other countries combined with the lax enforcement of laws make it easy for criminals to cause mischief with little consequence.

A symptom of this is the high number of accidents and traffic fatalities in India. Traffic police are probably the least competent, but the indifference and incompetence of the traffic police points to a systemic problem in law enforcement everywhere: tax evasion, violations of human rights, and a lack of security. Citizens that pay taxes are paying the state to keep them safe, and to guarantee some basic dignity. The police are unable to provide this in Bombay.

This incident is truly unfortunate, and I share the sense of vulnerability such incidents cause. Unless we can address the core problem: the failure of enforcement of laws, we can never achieve the security that Bombay deserves.

Image courtesy: blog on Indian police

Dual HD 44780 Controller Liquid Crystal Library for Arduino

2011-07-10T15:32:00.000-07:00

I came across a four row LCD panel while browsing at an electronics store: the model name was WM-C4004A. I wasn't sure if I could drive it through an Arduino but decided to try. It was easy to drive once I hunted down the datasheet for the WM C4004A, a dual HD44780 controller, and understood the controller.

There is a good Arduino library for driving HD 44780 compatible controllers and I modified the LiquidCrystal library to drive two separate controllers. The usage is identical to the LiquidCrystal library. You specify the Register Select (RS) and enable bits for both controllers, the data pins, and the rows and column per controller. Then you can seek() and write() through Arduino.

My modifications are available as the LiquidCrystalDual library. Download the library: LiquidCrystalDual.tar.gz or LiquidCrystalDual.zip. Unzip and place the contents in the libraries/ directory in the arduino installation.

Here is a small example program (there is a detailed program in the examples/ menu in the Arduino IDE).

#include <LiquidCrystalDual.h>

// 2 controllers: RS, RW, EN1, EN2, D4, D5, D6, D7
// We have the RS (RS=12) line, *no* RW line (RW=-1),
// two enable lines (EN1=6, EN2=7),
// four data lines (D4=11, D5=10, D6=9, D7=8)
LiquidCrystalDual lcd(12, -1, 6, 7, 11, 10, 9, 8);

void setup()
{
  // I have 40 characters and two lines per controller.
  lcd.begin(40,2);

  // Move to the first column of second row.
  lcd.setCursor(0,0);
  lcd.print("Line 1: Hello");
  lcd.setCursor(0, 1);
  lcd.print("Line 2: World");
  // Move to the second controller
  lcd.setCursor(0, 2);
  lcd.print("Line 3: Four...");
  lcd.setCursor(0, 3);
  lcd.print("Line 4! Lines!");
}

void loop()
{
  // Do nothing.
}

What determines the success of a country: Nurturing creators

2011-07-08T20:16:00.000-07:00

Why does a single area dominate one industry? Detroit with cars in the 1960s, Silicon companies in California in the 1980s, .... Before the computer revolution, there was no centre of electronics. A lot of work was done in the UK, Japan, the US, and other countries. And yet, most of the computer design is now centred in the US.

I am beginning to think that the core reason why the US forged ahead with computers was that it had a large number of initial hobbyists and tinkerers. Many individuals tried different ideas. Most of the ideas made no commercial sense, but there were enough ideas that reached commercial success. The initial tinkering group found themselves employed at companies that were successful. Apple started out as a tinkering collection, with Steve Woz designing motherboards for sale for $666.66. He had worked previously at Hewlett Packard, and brought his impressive tinkering skills to bear on the Apple I and the Apple II. Dell, Compaq, Intel, they all had a core group of tinkering engineers who had a commercially viable idea. Everyone was producing things, and most were of dubious value. But for every hundred bad ideas, there was one Apple or one Microsoft. And that hit-rate was enough to sustain entire generations of engineers. The UK had some tinkerers but their total number was small compared to those in the US, so while they had some success, they couldn't sustain a lead.

Something similar happened with the Web 2.0 boom. For a while, every college student in the US was making a Web 2.0 mashup, armed with an Apache server and a passing knowledge of Javascript. Not everything worked, but enough ideas were bounced around to give rise to a Twitter, a Facebook, a LinkedIn, a Youtube. All these sites were possible elsewhere.

This is happening in the mobile world, all over again. College students in the US are making apps for their iPhone and Android devices. Most of them are failures, but enough are succeeding in the San Francisco area to create a virtuous cycle. Many college students are getting together to form two-person startups around their iPhone app.

I think this tinkering and production of ideas is the reason for phenomenal American success in computer hardware, Web 2.0, and mobile applications. One of reasons for this is cultural: American individuality recognises the lone wolf who is trying something new, even if the idea isn't mainstream. The other is the large payoff to a successful venture. The third is the general risk-loving attitude: students willingly take a year off from University to try out a startup, working families try a startup even if they know it might cause some hardship if the venture fails. College students are happy working on some idea they love.

All these factors contribute to an environment where tinkering and idea creation is nurtured and idea creators are rewarded. Even if most projects fail, enough of them succeed that the job market is always looking for engineers and other tinkerers. Many people working at Apple or Google today have a varied history of trying out different ideas and learning from their mistakes.

I see this trend most clearly in hobbyist hacking involving the Arduino or other micro controllers. Again, a lot of tinkering is being done in the West. The difference is that there are a significant numbers of Chinese hobbyists involved. At first, this was because the manufacturing had moved off to China, and the Chinese engineers were exposed to a lot of Western products and ideas. Now, we see many Chinese engineers tinkering and experimenting. Unlike the Web or mobile applications, electronics hacking doesn't require an excellent command of English, and some Chinese electronic designs are approaching the best in their class.

It seems to me that countries should focus on nurturing creators. It pays off in the long run.

Fun with Assembly Language

2011-07-05T12:02:00.000-07:00

This is a quick page about my adventures with Linux assembly language, with links to resources, and some source code.

Why?

I won't fool you into thinking that assembly language is a useful tool: it isn't. By and large, if you want to get stuff done, you're much better off learning Python, C or Java. Assembly language is great if you're a tinkerer, and want to know what is going on inside your computer. Many people have written interesting tiny programs using assembly, which might be handy on embedded environments. Finally, there are some features that you can only get through assembly: low-level architecture features, getting around compiler limitations and understanding languages themselves. For me, assembly is just for fun!

Resources

I do all my programming on Linux, and it is one of the best environments to learn assembly. The tools are quite good, and there is some lovely documentation. If you don't already have Linux, get a copy of Knoppix, which is a live CD that lets you try out Linux without modifying your computer setup. Here is a list of books that I highly recommend.

[PGU] - Programming From the Ground Up, by Jonathan Bartlett: an excellent introduction to x86 assembly language on Linux. The entire book is free for download. This one book is all you need, initially.
[PAL] - Professional Assembly Language: another excellent introduction.
[IPM] - Intel Programming Manuals: complete, in-depth information on architecture and assembly language. You're probably interested in Vol 1, 2A, 2B, 3A and 3B. It is meant as a reference: not a cover-to-cover read.
[APM] - AMD x86-64 Programming Manuals: complete, in-depth information from AMD. Get all the volumes.

Fun with Assembly

So you got yourself a copy of [PGU], and want a challenge?

We try to rewrite the first program from [PGU] as 01_exitValue.s. The expected return value is 999, but you get something else.
1. Can you guess what the return value is without running the program?
2. Can you explain why the return value is not 999?
3. Can you write the program so that this problem can be caught by the assembler?
4. 01_exitValue_Solution.s.
We try to rewrite the second program from [PGU], using our understanding from the earlier problem, as 02_maximumValue.s. The expected return value is 214, but you get something else.
1. Can you guess what the return value is without running the program?
2. Can you explain why the return value is not 214?
3. Can you write the program so that this problem can be caught by the assembler?
4. 02_maximumValue_Solution.s.
Here's an example for why you might need assembly language. Your mission is breaking into a program to steal a secret key. Some experienced hackers have isolated where the secret key is being passed to a secret function.
1. secretFunction(char *useless, char *secret_key) calls validate() immediately upon starting. You job is to print secret_key inside validate. As an example, the file 03_keyIsHere.o contains the secret function that has the second argument as a key. You are only allowed to write a validate() method in a separate .s or .c file. Try not to modify the original object file. You are assured that the key is exactly 13 characters long. Try writing an assembly solution, and compile and run with gcc 03_keyIsHere_Solution.s 03_keyIsHere.o -o 03_keyIsHere; ./03_keyIsHere
2. If the validate was called in the end, how does it change your solution?
3. Can you use this trick to guess the local variables of secretFunction?
4. In case the object file doesn't work for you, 03_keyIsHere.c contains the C source. The solution must not modify it.
5. 03_keyIsHere_Solution.s Compile and run with gcc 03_keyIsHere_Solution.s 03_keyIsHere.c -o 03_keyIsHere; ./03_keyIsHere
This is a more sophisticated example compared to the previous one. Having moved on in your career, you are faced with a new program that calls printf, and you have to inject code without a recompilation. The program 04_crackMe executes happily on its own. You know that printf is being called in it, and that on the first invocation, the calling function has a secret-key as its second parameter.
1. secretFunction(char *useless, char *secret_key) calls printf() immediately upon starting. You job is to print secret_key. Most probably, you'll want to inject code into printf. The solution does not require modifying the original binary. You are assured that the key is exactly 13 characters long.
2. Can you do this while continuing to print the original messages?
3. In case the object file doesn't work for you, 04_crackMe.c contains the C source. Compile and run with gcc 04_crackMe.c -o 04_crackMe; ./04_crackMe . Remember that the solution does not require modifying the 04_crackMe binary or the C source code.
4. 04_crackMe_Solution.s. Instructions on how to run it are inside the solution.
5. Sufficiently pleased? Good, now carry it over to the next level by visiting this awesome page on making 13 equal to 17.

Cost effective (cheap!) USB Serial cable for any project

2011-07-05T11:51:00.000-07:00

If you've been playing with microcontrollers, or hacking any sort of hardware, you know that it is great to be able to communicate with a computer. A usb cable is often the best option, since usb serial drivers are ubiquitous and easy to work with. However, cheap usb cables are difficult to come by. On this page, you will find instructions to build a very low cost USB serial cable, which can also supply +5V to a board. This is ideal for breadboard arduinos, but will also work great for any microcontroller or TTL circuit.

All instructions here are provided solely as a guide. If you miswire the cable, you might end up burning your computer, your electronic gadgets, or your house. I do not take personal responsibility for your actions.

Cost, parts, and capability

You need a Nokia CA-42 cable, a soldering iron and some method of determining continuity. A multimeter would be handy, but is not required. Assuming you have the tools, the CA-42 cable sells for $3 including free shipping from many sellers on eBay and Amazon. Since the cost of the cable is so low, online fraud is unlikely. The total cost of the project is $3, and you don't need any extra parts.
The final cable works on Linux, without requiring any extra drivers. Most cheap CA-42 cables are made using a PL-2303 chip, which is a cheap RS232 convertor. For data transmission, you only get two lines: RX and TX, but this is usually sufficient. You get +3V and +5V, which are very well regulated and clean sources of power. These could be directly attached to microcontroller boards. I have seen drivers for PL-2303 on Windows and Mac, and you should search for these over the Internet. You might need to mask the device ID, since the cable might announce itself as a Nokia phone cable. You don't need any drivers if you only want to use the cable as a power source.

Make it

The construction is trivial. This is what the cable looks like (image courtesy Timothy Small):

The pinout, from left to right is:

This is body of the cable, and is not connected
The missing pin, no connection
No connection
+3.3V, might be as low as +3V
No connection
RX
TX
GND

It might help to view the pin out diagram (hosted at nas-central.org).

To create the cable, cut the head near the top of the cable, as shown. When you cut the cable, try to match the color of the wire with the pinout given above. I've found the following colors, though you should check your own cable:

Black: Ground
Red: 3V
White: RX data
Blue: TX data
Green: no connection

Now, the cable has five wires: two are used for data (TX, RX), two are for power (+3.3, GND). There is an extra wire in there, which is useless for our purposes. So we repurpose this wire to carry the +5V connection from the USB port. In my cables, this wire has always been green, though you should check which wire, if any, is unused in your cable. The head of the cable comes off quite easily if you hold it and twist the metal USB connector as though it were a key. Connect the far right metal lead from the USB connector to the green wire. The green wire should be disconnected from the body, but the +5V connect should not be disconnected from the body: the PL-2303 requires +5V power to work.

Here is the final soldered assembly. In this image, the usb connector is the correct side up. For your reference, here is pin-out for the USB A connector. The soldering is done to the +5V wire.

Uses

The +5V and ground can be used to power an arduino or most Atmel Atmega AVR microprocessors. The TX wire (colored blue in my cable) goes into the TXD pin of microcontrollers (Arduino: digital 1), and the RX wire (colored white in my cable) goes into the RXD pin of microcontrollers (Arduino: digital 0). I've tested the power using an oscilloscope: the power in my cables is very clean. This means that you can avoid using a 7805 and other circuitry that would provide a clean +5V signal.

Credit: The idea for this cable is due to the the ARM9 Linkstation hackers.

Making your Linux computer silent

2011-07-05T11:33:00.000-07:00

These are some notes I made back before Solid State Disks were popular. If I were doing this today, I'd get an Intel Atom processor with SSD disks, and no fans. These tips might still be relevant for desktop computers.

While you may not realize it, your computer is capable of being silent, or at least quieter. I collect some tips here which might help in reaching this goal.

Buy a good power supply. A lot of the noise comes from power supply fans and other fans in the system. While the CPU fan is usually rather silent, some power supply fans are very noisy. If you want to make your existing fan quieter, a good way is to blow the dust out. Dust stuck in the fans makes noise. You could use a bicycle pump to force air through the fan after switching off the computer. Your mileage may vary. CPU heatsink fans have the tendancy to get very dirty, and dirt gets accumulated in the heatsink fins. I've found cleaning these fins to make quite a dramatic change in the amount of noise from the heatsink fan.
Use noflushd: It is a user level daemon that prevents disk writes from spinning disks back up.
Don't use journaling filesystems. Ext3, reiserfs, xfs, jfs are all journaling filesystems and commit data to disk without going through any cache. While journaling filesystems are cooler and have much better recovery and consistency: if you have a noisy disk: they will make it spin almost continuously. Turn off journaling with ext3, or change the filesystem if you can. Here is a quick way to convert an ext3 partition to ext2. This will work even if it is the / filesystem, though nothing is guaranteed. First, turn off all the services possible, and try to get almost no processes running. Then edit /etc/fstab so that the ext3 filesystems are changed to ext2. Next, run the command
```
vi /etc/fstab  # <- change /dev/sdaXX from ext3 to ext2
mount -o remount,ro /dev/sdaXX
tune2fs -O ^has_journal /dev/sdaXX
mount -t ext2 -o remount,rw /dev/sdaXX
```
After these commands, you might want to reboot, and see if the filesystem is now ext2. It worked for my iMac, where I could not reboot to another Linux distribution. Again, your mileage may vary.
Turn off as many services as you can. If you don't need mysql running all the time, switch it off. A lot of services want to write logs, and you can either change their configuration to disable log writing, or look at the next step.
If you have directories in which frequent writes are required, consider mounting them as a tmpfs. This is a new filesystem in Linux which keeps data on RAM, and not on disk. This means that if the machine goes down, your data is lost. To avoid losing data, you might want to copy the data out to real disk when switching off the machine. This is a great way to write log files, or put images from the webcam that you take every second or so. After all, when you have the most recent image, you might not be so interested in the older photos. If your kernel is too old, you might want to use the ramdisk module, but tmpfs is a better choice if you have it.

Programming the NXT to communicate with Linux

2011-07-05T11:26:00.000-07:00

This is Part 3 of a three-part series on programming the Lego NXT through Linux.

If you have followed along, you are now ready to program in NXC.
Let's write a simple C program for Linux, and an NXC program for the NXT that communicate through Bluetooth. The interface of this program is totally dopey and unprofessional, but it demonstrates how to send information to the NXT and get information from it. The ideas are borrowed by notes from the CPSC 3720 Software Engineering course at the University of Lethbridge, in particular this handout. Here are the steps you need to follow.

Install Bluetooth libraries and GTK libraries on Linux. On Ubuntu, the command is:

$ sudo apt-get install libbluetooth-dev \
       libgtk2.0-dev libc6-dev make gcc

Make the Tribot from the Mindstorms quickstart. This is the first project, the quick start.
Ensure that B is connected to the right motor, and C to the left motor. Leave A unconnected.
Now download my nxtBluetooth.tar.gz package to demonstrate Linux Bluetooth communication. Unpack it, and go through the files.
There are two programs: nx_soldier, which is the NX's program. It listens on Bluetooth and obeys the commands of the commander. The pc_commander is a GTK application that allows you to specify commands that the soldier will faithfully carry out.
There is a single place you have to edit to specify your NXT's address. Remember the times you changed 11:22:33:44:55:66 address above? Well, you need to open the pc_commander.c file and change this address to that of your NXT again.

Attach your NXT using the USB cable. Compile the programs with

$ grep ADDRESS pc_commander.c       
$ # Make sure you have the right address
$ make nx_soldier.rxe
$ make pc_commander && ./pc_commander

Run the nx_soldier program on the NXT.
Run the pc_commander on the Linux machine. Press the buttons to make the soldier move according to your wishes.
When you ask the soldier for his status, he always replies he is fine.
This program makes a good starting point: the code is reasonably well documented, and easy to adapt. You could try putting the bumper sensor on the TriBot, and modifying the nx_soldier so that he replies with "I am stuck" when it has hit a wall.

Setting up the Lego programming environment in Linux

2011-07-05T11:25:00.000-07:00

This is Part 2 of programming the Lego NXT using Linux. Part 1 covers the Lego-Linux bluetooth connection.

If you're like me, you've used the graphical NXT programming environment for about twenty minutes before wrist pain and frustration sets in. I did not enjoy the graphical programming at all, and the fact that it did not work on Linux was another factor. Well, there is a very nice alternative, which is John Hansen's NXC language. It is a C-like language which you can program the NXT in. You'll hear a lot of references to BrixCC, which is an IDE for NBC and NXC. It doesn't exist for Linux, but any text editor works quite well. All features are supported, and you can write code that is more compact and faster than the graphical tool. Also, you can use NXC to allow your robot to communicate with your Linux computer over bluetooth! This is what you need to do to start using NXC.

Visit the excellent NXC beta release page . There is no stable release as of March 2009, but the beta is pretty rock solid. Forget the source code, it is made in Delphi and there is little documentation on how to compile it under Linux. Get the binary distribution. It consists of some very spare documentation and the nbc executable. Despite its name, it is also the NXC compiler. This will only work on x86 Linux.
Run nbc -help to learn the options. Really, this program needs a man page!
Visit the NXC documentation page and get the lovely NXC_Guide.pdf, a guide on how to program using NXC. Download it but don't look at it yet. It is a reference, not an introduction.
The real document you're looking for is Danny Benedettelli's NXC tutorial, which is far more useful than the guide. Download it, print it out, read it through and through.
To set up the USB communication, download setupNxtUSB.sh: shell script to perform USB settings for Linux communication with NXT.
Run it by itself as follows
```
$ chmod +x ./setupNxtUSB.sh;
$ ./setupNxtUSB.sh
```
This will prompt you for the root password when required. The file follows instructions from the page about Linux USB setup with NXT, so all credit to them. Feel free to edit the file if you suspect something went wrong. The script will prompt you with any errors that it encountered.
In case you aren't certain if the setup worked, plug in your NXT. You should see the word "USB" in the top left of the NXT display, and the output of the command ls -l /dev/lego* should show at least one device. My output is given as a reference
```
$ ls -l /dev/lego*
lrwxrwxrwx 1 root root 15 2009-04-19 17:45 /dev/legonxt-2-1 -> bus/usb/002/042
```
Write a sample program using Danny's guide.
Compile your program with nbc your_program.nxc -d -S=usb, where your_program.nxc is the name of your program.
Now the program has been compiled and loaded on to the NXT. It should appear in the "My Files" -> "Software Files" area of the NXT, from where you can run it!
There, that wasn't so hard! As you learn NXC, you'll realize that it is feature complete, and is a much more elegant way of programming the NXT.

Setting up NXT-Bluetooth support on Linux

2011-07-05T10:25:00.000-07:00

So you want your NXT device to talk back to your Linux machine? Perhaps you want to control your robot through your computer. As a first step, you have to set up the Linux - NXT bluetooth connection. My setup is explained below.

Ubuntu Gutsy (7.10) Linux, though these instructions are not version dependant. The only instructions that depend on the distribution are the ones related to package installation (apt-get). If you know your distribution's package manager, you should have no trouble.
An x86 computer. Typically, you'll want a laptop with bluetooth support, so you can walk around with your NXT construction. A desktop will do just fine too. You need an x86 because the nbc binary only works on an x86.
A Lego Mindstorm NXT.
Bluetooth hardware on your linux machine.
The Linux packages: bluez-utils, python-bluez, bluez-hcidump, bluez-gnome, bluetooth

Make sure you have all the packages installed. On Ubuntu, you can run this command.

sudo apt-get install bluez-utils \
     python-bluez bluez-hcidump bluez-gnome bluetooth

Now, once all the packages are installed, make sure that your bluetooth hardware is supported and is running fine. One way to do this is to check for the bluetooth icon in the taskbar of Gnome.

You should be able to click on that icon and get a list of preferences. In case you are not sure if you device is getting recognized and used, check for lines similar to the ones below in the output of dmesg

[243203.060226] Bluetooth: HCI USB driver ver 2.9
[243203.063512] usbcore: registered new interface driver hci_usb

Now that you have a working bluetooth setup, you need to pair it with the NXT brick. First, you need to ensure that the serial service is started by selecting it in the preferences dialog from the bluetooth icon.

Now turn on your NXT Brick, and enter bluetooth settings, and turn bluetooth on. You can verify that bluetooth is turned on by looking in the top left of the NXT display. It should have a bluetooth icon. Now run the command sudo hcitool scan from a console. The output should contain a line for your NXT device. My device is called Snow, and I get the following output.

Scanning ...
 11:22:33:44:55:66 Snow

Great!. This is definite proof that your bluetooth device works, and that it can see your NXT. Time to set them up for pairing. Edit the file /etc/bluetooth/rfcomm.conf to contain the following block:

rfcomm0 {
        # Automatically bind the device at startup
        bind yes;

        # Bluetooth address of the device
        device 11:22:33:44:55:66;

        # RFCOMM channel for the connection
        channel 1;

        # Description of the connection
        comment "Snow Mindstorm";
}

Change the address 11:22:33:44:55:66 to match the output of your hcitool scan command that you made in the previous step. Now run the command sudo /etc/init.d/bluetooth restart, and then rfcomm. The output should contain your device's address. A sample session is shown here:

$ sudo /etc/init.d/bluetooth restart
   * Restarting bluetooth            [ OK ]
$ rfcomm
rfcomm0: 11:22:33:44:55:66 channel 1 clean

Now, you need to pair your device. This is done with the following command

$ sudo l2ping 11:22:33:44:55:66

This will prompt the NXT to beep happily, asking for a passphrase. The number "1234" is already entered, so just accept it by pressing the orange button. Now your computer will want to know this passphrase. Click on the button in the notification that pops up (example shown below), and enter the same number as shown. This is a one-time procedure for each computer-NXT combination.

If you have a multi-seat (or multi-terminal) setup, this notification might be going to another seat, so check all notification areas on every terminal. If you don't know what multi-seat or multi-terminal setup is, ignore the previous statement. If all went well, your ping command should be able to send packets back and forth to the NXT. A happy sample output is shown below.

Ping: 11:22:33:44:55:66 from 00:09:DD:50:67:CE (data size 44) ...
4 bytes from 11:22:33:44:55:66 id 0 time 49.95ms
4 bytes from 11:22:33:44:55:66 id 1 time 85.71ms
4 bytes from 11:22:33:44:55:66 id 2 time 27.80ms
4 bytes from 11:22:33:44:55:66 id 3 time 54.80ms
4 bytes from 11:22:33:44:55:66 id 4 time 65.81ms
4 bytes from 11:22:33:44:55:66 id 5 time 47.80ms
4 bytes from 11:22:33:44:55:66 id 6 time 84.79ms
4 bytes from 11:22:33:44:55:66 id 7 time 45.81ms

Great! So now your NXT is paired with the computer. In order to communicate with the desktop, you need to download the NXT Python library. Once you have downloaded and installed it, enter the sample program, and you should be able to get the NXT's name and ID. If you have any problems at this stage, try rebooting the NXT brick, it sometimes helps. After running the sample program, you should see your hostname in the "My Contacts" in the NXT's bluetooth menu. This verifies that you can connect with the NXT, and have the NXT talk back to the desktop computer.

(This is the stable home of the page that was earlier at vikram.eggwall.com)

Hiking: Portola Redwoods State Park, July 4, 2010

2011-07-03T00:00:00.000-07:00

This was our first time camping and hiking at the Portola Redwood State Park. The drive to Portola from San Jose is almost as long as the drive to Big Basin - about 1 hour. The park is nice, but we like Big Basin and Henry Cowell better.
There's a short trail starting behind the camp office, the Sequoia Nature trail I think, that takes you to a small stream with a bridge running across it. This is a great place to come by for a late evening walk from the campground.
The main hike marked in the map was on the Slate Creek trail. Took us a while to get to the trailhead, as you can see. We walked over 9 miles, spanning an elevation gain of 1000 - 1200 feet. A large map of the hike can be found here.

Hiking: Henry Coe State Park, Jun 26, 2010

2011-07-01T00:00:00.000-07:00

The campgrounds at Henry Coe are very nice. There are just a few campgrounds, so it's a lot quieter, and the view is great. On a nearly-full-moon Friday night in late June, it was spectacular. The facilities are primitive, but well maintained.
We started hiking early, expecting most of the trails to be exposed to the sun, but our path was reasonably well shaded by trees and large shrubs. Okay - here's the 6.6 mile loop we did: started up the Monument Trail, made a left on Hobbs road, right on the Frog Lake Trail (there were many tiny, camouflaged frogs jumping all over!), right on the Middle Ridge trail, right on the Fish Trail, and then back to the Camp Headquarters via the Corral trail. The route was pretty well-marked all along.
Oh, and apart from being on the lookout for poison oak, also be on the lookout for ticks. Light colored clothing is probably a good idea - makes them easier to spot and de-tick.
A large map of the hike can be found here. The route covered roughly 1800 feet of elevation gain over a 6.6 mile stretch, but the uphill stretches are interspersed with easier stretches. Walking the same route in an anti-clockwise direction would probably be a lot more strenous.