I've been addicted to logical puzzles for a long time. Recently, I've become addicted to writing programs to solve addicting logic puzzles.
Years ago I whipped up a dancing links sudoku solver as popularized by Knuth, which converts sudoku instances into exact cover problems. So of course when I learned ZDDs were good at exact cover problems, again from Knuth, I immediately thought of sudokus.
I dreamt of building a ZDD representing all possible (standard) sudokus. I could then fill in some boxes, and from here, I could count the number of solutions, pick one at random uniformly, or weight the solutions with any given scheme and find the maximum or minimum solution, as well as the mean and standard deviation.
I eagerly wrote enough ZDD routines to encode the sudoku constraints. The preliminary results were encouraging: my ZDD enforcing exactly one per box and exactly one per row for each digit required only 20738 nodes. But the column constraints crushed my aspirations. No matter how I sliced it, the ZDD grew too rapidly as more constraints were added.
As a consolation prize, I hoped to at least convert my program into a solver that would rival my earlier program. Unfortunately, although the end result could solve a sudoku, it did so slowly.
Deflated, I sought reassurance by verifying Knuth's results on chessboard tilings. Thankfully my numbers agreed exactly, so I knew my implementation was sufficiently correct and efficient for basic experiments. On the other hand, it also probably means that sudokus are indeed beyond the reach of ZDDs.
I flailed around looking for another excuse to use ZDDs. It didn't take long: nonogram puzzles turn out to be no match for their power.
By the way, I obviously mean human-friendly nonograms, as the general problem is NP-complete; ZDDs aren't that revolutionary! The same applies to other NP-complete puzzles: rather than prove P = NP, my goal is to write an efficient solver for instances meant for humans, and maybe also instances that are just a bit tougher.
I didn't have much time to stress test the nonogram solver, as I rapidly moved on to a Light Up solver. Shortly after I threw together a dominosa solver, and yet more ZDD solvers for other logic puzzles are in the pipeline. I'll release the code soon.
As dominosa puzzles are easily disguised as exact cover problems, I also wrote a dancing links solver. Unsurprisingly, it is much faster; I'm sure specialized recursive search programs outperform ZDDs for the other puzzles too, but ZDDs have some advantages. Firstly, they are easy to write once the infrastructure is in place. Constraints for many logic puzzles are easily expressed in terms of ZDDs. Secondly, even if ZDDs are only practical for smaller instances, they can often answer more questions.
For example, how many dominosa problems are there if we go up to double-nine? How many are there if we then place a few particular dominoes in certain places? What does puzzle number 12345 look like? And so on.
Sunday, May 31, 2009
Sunday, May 24, 2009
A really fundamental data structure
There are many things I wish my textbooks had taught me. It's often not the fault of the authors: in any field, even the best ideas suffer a lag between discovery and dissemination. However, even accounting for this, it seems I'm always behind the times. Some glaring omissions I belatedly redressed:
Take a map of the USA, and consider the following problems:
Learning about BDDs reminded me of learning about Pólya theory, another simple yet powerful technique which transforms the seemingly impossible into child's play.
- Calculus can be taught rigorously with infinitesimals, following the path traveled by its original developers, unlike the approach using limits and deltas and epsilons.
- Cuckoo hashing gives hash tables with O(1) worst-case lookups and are also space-efficient.
- Bob Jenkin's hash functions for hash tables are better than those many commonly encountered in textbooks.
- Perfect hashes give optimal performance when the keys come from a small set that can be preprocessed beforehand.
- Crit-bit trees perform similarly to hash tables but have some advantages. My favourites: good worst-case running time and lexicographical operations. Apparently they can be used to sort strings faster than quicksort or radix sort.
- AA trees remove the pain from implementing balanced binary trees.
Take a map of the USA, and consider the following problems:
- Suppose you want to visit every state capitol exactly once, traveling on highways. Which route is shortest? Which route is longest? What is the mean and standard deviation of all the routes?
- Weight the states by any means, for example, by reading their two-letter code as a number in base 36. Then find a set of states such that no two members of the set are adjacent, and the total weight is maximized.
- There are several ways to colour the map with four colours such that no two adjacent states have the same colour. How do we pick one of these colourings at random (uniformly)?
- How many ways can you tile a chessboard using 1x1, 2x1 and 3x1 rectangles? What if we also have pieces that look like 2x2 boxes with one tile missing?
- List all 5-letter words that remain words after replacing a 'b' with 'o'.
Learning about BDDs reminded me of learning about Pólya theory, another simple yet powerful technique which transforms the seemingly impossible into child's play.
Sunday, May 17, 2009
Assorted sorts
Let void x(int *p, int *q) be function that swaps its arguments, namely, after execution, *p is equal to the original value of *q and vice versa.
What do the following functions do?
The title is a big hint, but if you're still not sure, experiment with a function by compiling it with the following code, and supply some integers on standard input.
Can you identify each algorithm? The answers are, in some order, bubble sort, gnome sort, insertion sort, selection sort, shell sort, heapsort and quicksort.
The real puzzle is why I bothered. All I can say is you don't have to be a chef to enjoy making spaghetti: see the International Obfuscated C Code Contest.
What do the following functions do?
void f(int *m, int *n) {
int *p;
for(p = m; p < n; p -= *p > p[1] ? x(p, p + 1), p != m : -1);
}
void f(int *m, int *n) {
int *p, *q;
for(p = m; p <= n; p++) for(q = p; q <= n; *p > *q ? x(p, q) : 0, q++);
}
void f(int *m, int *n) {
int i, j, k;
for(i = 1; (k = i) <= n - m; i++)
while(k && m[j = k - 1 >> 1] < m[k]) x(m + j, m + k), k = j;
for(k--; x(m, m + k--), k;) for(i = 0;
j = 2 * i + 1, k >= (j += k > j && m[j] <= m[j + 1]) && m[j] > m[i];
x(m + j, m + i), i = j);
}
void f(int *m, int *n) {
int *p, *q, i;
do
for (i = 0, p = q = m, ++q; q <= n; p = q++) *p > *q ? x(p, q), i = 1 : 0;
while(i);
}
void f(int *m, int *n) {
int *p, *q;
for(p = m + 1, q = n; p < q; *p > *m ? x(p, q--) : *p++);
m != n ? *m > *p ? x(m, p) : 0, f(m, --p), f(q, n) : 0;
}
void f(int *m, int *n) {
int *p, *q, i, j;
for(p = m + 1; p <= n; p++, *q = i)
for(i = *p, q = p; q > m && i < (j = *(q - 1)); *q-- = j);
}
void f(int *m, int *n) {
static short s[] = { 1, 4, 10, 23, 57, 132, 301, 701, 1750 };
int *p, *q, i, j, a, b;
for(a = sizeof(s)/sizeof(short) - 1; a && s[a] > n - m; a--);
while(a >= 0) for(p = m + (b = s[a--]); p <= n; p++, *q = i)
for(i = *p, q = p; q > m && i < (j = *(q - b)); *q = j, q -= b);
}
The title is a big hint, but if you're still not sure, experiment with a function by compiling it with the following code, and supply some integers on standard input.
#include <stdio.h>
void f(int *m, int *n);
void x(int *p, int *q) {
int i = *p;
*p = *q, *q = i;
}
int main() {
enum { limit = 8192 };
int a[limit], *n, *k;
for(n = a; 1 == scanf("%d", n) && n - a < limit; n++);
puts("in:");
for (k = a; k < n; k++) printf(" %d", *k);
puts("");
f(a, n - 1);
puts("out:");
for (k = a; k < n; k++) printf(" %d", *k);
puts("");
return 0;
}
Can you identify each algorithm? The answers are, in some order, bubble sort, gnome sort, insertion sort, selection sort, shell sort, heapsort and quicksort.
The real puzzle is why I bothered. All I can say is you don't have to be a chef to enjoy making spaghetti: see the International Obfuscated C Code Contest.
Thursday, May 14, 2009
Notable Notation
Pursuing a graduate degree in computer science at Stanford offered many perks. I benefited from at least one more than some of my colleagues, as I was assigned an office only a few doors away from Don Knuth's.
I'd occasionally catch a glimpse of the legendary computer scientist, for some reason usually donning a bicycle helmet. However, the proximity of his office alone seems to have had an effect: I switched to LaTeX for typesetting. As an undergraduate I loyally used Lout, whose author, Jeff Kingston, had an office near where I worked. In seriousness, it was probably more for practical reasons than out of respect: all my co-authors used LaTeX.
I still have a soft spot for Lout with its clean and comprehensible internals. Compare with the inscrutable black-magic LaTeX style sheets built on top of TeX, which itself is tricky to grasp. However, the TeX equation syntax certainly deserves its status as the lingua franca of mathematicians communicating via email and other plain text mediums.
My workplace is no longer near Knuth or Kingston. Perhaps not entirely coincidentally, I no longer use TeX or Lout. Wanting documentation sources to be as readable as much as possible, I devised a markup language inspired by venerable ASCII typesetting tricks of heavy email users and README authors, such as *asterisks*, _underscores_, and ==Headings==, and wrote a script to translate it to HTML. Luckily I didn't get far before discovering AsciiDoc.
Equation-heavy notes, books, HTML, PDF: AsciiDoc handles them all despite using source files that look like ordinary text documents. Easy to learn, easy to type, and easy on the eyes. Fine-tuning the final layout is difficult, a blessing in disguise as users have solid excuses for ignoring those typesetting nitpicks TeXperts are expected to correct.
But I digress: back to name-dropping Donald E. Knuth. Although he was warm and friendly, I only spoke to him a few times as he was also busy. However, I had many chances to listen to him. Sometimes he'd give a talk in the meeting area outside my door, where I always had a guaranteed seat: I could simply wheel my office chair a few meters.
Regrettably I recall almost nothing. There was a story about how noticing a pattern in table of numbers yielded a PhD thesis; he made it sound so easy. I also vaguely remember a fascinating introduction to coroutines along with an obscure but accessible application: generating certain Gray code sequences. This would describe all I have left from Knuth's talks, but happily, some of his Computer Musings were recorded and are freely available online.
The Notation episode is surprisingly interesting, especially the historical tidbits. The notation for floor and ceiling functions only became standard relatively recently, a brilliant idea that usurped many inferior schemes and rapidly took over the world. Another young fad is to use "lg" for the base 2 logarithm, though now it seems we should use "lb" instead.
The highlight was Iverson's bracket convention: one places an expression within square brackets, and the whole thing evaluates to 1 if the expression is true, and 0 otherwise. For example, [k is even] means 1 when k is even, and 0 otherwise. Other examples:
This should all sound familiar to C programmers, because many C operators evaluate to 1 when the result is true and 0 otherwise. It's simultaneously disheartening and amusing that while mathematicians and computer scientists are discovering the utility of this convention, some programming language designers actively oppose it by introducing a boolean data type that cannot be interchanged with integers.
The lecture was crammed with other ideas that deserve to be widespread. I discuss them somewhere I can use AsciiDoc and LaTeX equation notation.
I'd occasionally catch a glimpse of the legendary computer scientist, for some reason usually donning a bicycle helmet. However, the proximity of his office alone seems to have had an effect: I switched to LaTeX for typesetting. As an undergraduate I loyally used Lout, whose author, Jeff Kingston, had an office near where I worked. In seriousness, it was probably more for practical reasons than out of respect: all my co-authors used LaTeX.
I still have a soft spot for Lout with its clean and comprehensible internals. Compare with the inscrutable black-magic LaTeX style sheets built on top of TeX, which itself is tricky to grasp. However, the TeX equation syntax certainly deserves its status as the lingua franca of mathematicians communicating via email and other plain text mediums.
My workplace is no longer near Knuth or Kingston. Perhaps not entirely coincidentally, I no longer use TeX or Lout. Wanting documentation sources to be as readable as much as possible, I devised a markup language inspired by venerable ASCII typesetting tricks of heavy email users and README authors, such as *asterisks*, _underscores_, and ==Headings==, and wrote a script to translate it to HTML. Luckily I didn't get far before discovering AsciiDoc.
Equation-heavy notes, books, HTML, PDF: AsciiDoc handles them all despite using source files that look like ordinary text documents. Easy to learn, easy to type, and easy on the eyes. Fine-tuning the final layout is difficult, a blessing in disguise as users have solid excuses for ignoring those typesetting nitpicks TeXperts are expected to correct.
But I digress: back to name-dropping Donald E. Knuth. Although he was warm and friendly, I only spoke to him a few times as he was also busy. However, I had many chances to listen to him. Sometimes he'd give a talk in the meeting area outside my door, where I always had a guaranteed seat: I could simply wheel my office chair a few meters.
Regrettably I recall almost nothing. There was a story about how noticing a pattern in table of numbers yielded a PhD thesis; he made it sound so easy. I also vaguely remember a fascinating introduction to coroutines along with an obscure but accessible application: generating certain Gray code sequences. This would describe all I have left from Knuth's talks, but happily, some of his Computer Musings were recorded and are freely available online.
The Notation episode is surprisingly interesting, especially the historical tidbits. The notation for floor and ceiling functions only became standard relatively recently, a brilliant idea that usurped many inferior schemes and rapidly took over the world. Another young fad is to use "lg" for the base 2 logarithm, though now it seems we should use "lb" instead.
The highlight was Iverson's bracket convention: one places an expression within square brackets, and the whole thing evaluates to 1 if the expression is true, and 0 otherwise. For example, [k is even] means 1 when k is even, and 0 otherwise. Other examples:
- sign(x) = [x > 0] - [x < 0]
- [A and B] + [A or B] = [A] + [B]
This should all sound familiar to C programmers, because many C operators evaluate to 1 when the result is true and 0 otherwise. It's simultaneously disheartening and amusing that while mathematicians and computer scientists are discovering the utility of this convention, some programming language designers actively oppose it by introducing a boolean data type that cannot be interchanged with integers.
The lecture was crammed with other ideas that deserve to be widespread. I discuss them somewhere I can use AsciiDoc and LaTeX equation notation.
Wednesday, February 11, 2009
Compiler Compilers
Long ago I sat a set of exams designed to test the breadth of our computer science knowledge. I failed Compilers. Luckily, they had just changed the rules, and it was acceptable to fail Compilers provided you passed the Databases exam. Fortune smiled upon me, and I passed the Databases exam despite possessing even less knowledge in that field. Or perhaps fortune was actually laughing at me: I stayed away from compiler theory for the rest of my degree to my detriment. It's scandalous I still know so little.
I was especially dispirited by my failure since I had thought I knew compilers well. When I was a child, I felt moved after learning about recursive descent parsers. I had been mystified: how could a program could possibly read an expression like (1+2)*((3+4)/5)? All I could think of was to use a simple loop to iterate over the tokens in the expression and assigning them to local variables before processing them. This led nowhere, because the nesting of parentheses can be arbitrarily deep. Thus I was awestruck by the elegance of recursive descent; after the first reading the technique was indelibly etched in my mind.
Much later, in university, basic compiler theory (grammar, languages, automata, and so on) came easily to me. I implemented a compiler for a toy language which produced the smallest and fastest code in my class. I'd also written the odd recursive descent parser for pet projects.
So I thought I was a compiler expert. But I should have paid attention to my weaknesses. I found LR(1) parsers unintuitive. I leafed through their proofs of correctness and promptly forgot their details, especially since the textbook stated these parsers are rarely coded by hand and instead generated by programs such as yacc or bison. Instead of embracing these powerful tools, I stuck with trusty hand-coded parsers because I understood them completely.
Ultimately this caused me to fail my Compilers exam, which was peppered with yacc questions, and more seriously, to waste copious amounts of time coding and debugging parsers and lexical analyzers. I have at last invested energy in seriously learning flex and bison, and I urge anyone in a similar situation to do the same. All these years, instead of writing recursive descent parsers unless there was a compelling reason not to, my default attitude should have been to use flex and bison unless there was a compelling reason not to.
I wrote a compiler that converts a toy language (essentially a tiny subset of Limbo) to Dalvik bytecode. I also wrote a Dalvik assembler along the way. In both cases, flex and bison were invaluable: gone are the finicky routines I've written and rewritten a million times, like handling an unexpected end of input, and fine-tuning mutually recursive functions and logic to get the desired operator precedence and associativity.
I've put my efforts on hold. I was hoping for a relatively functional and less object-oriented input language, but it seems such a language would be tricky to shoehorn into Dalvik bytecode: function calls are abstracted, and with no control over stack frames I doubt I can implement trampolining.
Also, I greatly underestimated my ignorance of compiler theory. I know nothing about the static single assignment (SSA) form, which appears too new for the textbooks I had. Moreover, I need to refresh my memory on older optimization techniques.
On the other hand, I don't want to discard my code, particularly as it will forever remind me to consider flex/bison before coding yet another parser by hand. Below is the git repository containing my primitive compiler and assembler that turns this:
http://cs.stanford.edu/~blynn/bender.git
I was especially dispirited by my failure since I had thought I knew compilers well. When I was a child, I felt moved after learning about recursive descent parsers. I had been mystified: how could a program could possibly read an expression like (1+2)*((3+4)/5)? All I could think of was to use a simple loop to iterate over the tokens in the expression and assigning them to local variables before processing them. This led nowhere, because the nesting of parentheses can be arbitrarily deep. Thus I was awestruck by the elegance of recursive descent; after the first reading the technique was indelibly etched in my mind.
Much later, in university, basic compiler theory (grammar, languages, automata, and so on) came easily to me. I implemented a compiler for a toy language which produced the smallest and fastest code in my class. I'd also written the odd recursive descent parser for pet projects.
So I thought I was a compiler expert. But I should have paid attention to my weaknesses. I found LR(1) parsers unintuitive. I leafed through their proofs of correctness and promptly forgot their details, especially since the textbook stated these parsers are rarely coded by hand and instead generated by programs such as yacc or bison. Instead of embracing these powerful tools, I stuck with trusty hand-coded parsers because I understood them completely.
Ultimately this caused me to fail my Compilers exam, which was peppered with yacc questions, and more seriously, to waste copious amounts of time coding and debugging parsers and lexical analyzers. I have at last invested energy in seriously learning flex and bison, and I urge anyone in a similar situation to do the same. All these years, instead of writing recursive descent parsers unless there was a compelling reason not to, my default attitude should have been to use flex and bison unless there was a compelling reason not to.
I wrote a compiler that converts a toy language (essentially a tiny subset of Limbo) to Dalvik bytecode. I also wrote a Dalvik assembler along the way. In both cases, flex and bison were invaluable: gone are the finicky routines I've written and rewritten a million times, like handling an unexpected end of input, and fine-tuning mutually recursive functions and logic to get the desired operator precedence and associativity.
I've put my efforts on hold. I was hoping for a relatively functional and less object-oriented input language, but it seems such a language would be tricky to shoehorn into Dalvik bytecode: function calls are abstracted, and with no control over stack frames I doubt I can implement trampolining.
Also, I greatly underestimated my ignorance of compiler theory. I know nothing about the static single assignment (SSA) form, which appears too new for the textbooks I had. Moreover, I need to refresh my memory on older optimization techniques.
On the other hand, I don't want to discard my code, particularly as it will forever remind me to consider flex/bison before coding yet another parser by hand. Below is the git repository containing my primitive compiler and assembler that turns this:
init() {
print("Hello, World");
}
on_input(arg : string) {
a: int;
a:= parse_int(arg);
print("\n");
print(int_to_string(a * (a + 1) / 2));
}into an Android app.http://cs.stanford.edu/~blynn/bender.git
Friday, February 6, 2009
Minimal Dalvik Executables
When I was a kid, the Windows era had yet to arrive. Floor-model PCs in shops ran MS-DOS. They'd often take steps to stop little imps like me messing around with their systems. I recall one where they even deleted the standard DOS utilities. But they had left COMMAND.COM unmodified which is enough for plenty of mischief. One can create executables via:
I created a HELLO.COM program by typing the following, where the numbers are typed on the numberpad with the Alt key held:
Thus with 9 bytes plus the size of the message, plus a byte for the terminator, we get a valid DOS program. We can type raw machine code from the keyboard to produce a full program.
Linux on x86 systems is less straightforward. The machine code is similar, but there must also be an ELF header (not strictly true: in some circumstances, the entire machine code can be placed within a truncated ELF header!), making binaries more tedious to construct by hand. However, certain kernel configurations allow different header types, some of them brief enough to be easily memorized and hand-rolled.
Minimalist Android
How about Android? An APK file is a ZIP file containing, among other files, the Dalvik executable in a DEX file. We're interested in minimizing this DEX file, whose full specification is well-documented.
All Android code must lie in some class, and Android applications typically inherit from a library class such as Activity, so we must also record information such as the class name, access rights, and inheritance. This, in turn, requires a strings section so we can store the class names, as well as invoked library functions and function signatures. Other overheads include the header and the map section. We can cheat a little by defining the UI with XML, so it won't contribute to the size of the DEX file.
After compiling to Java class files, most or all the R*.class files can be removed before making a DEX file,since the constants they contain are hardcoded in other class files by javac. For some projects, R$styleable must be retained, though this class appears to have since been removed from the public API.
I chose to write a program that parsed the DEX file from the HelloAndroid example and output only the necessary sections rather than attempt to create a DEX file from scratch. I found I could safely elide the source filenames, debug information and annotations. The result consists of 632 bytes, though we could trivially shrink this further by using a shorter name for the class.
$ copy con: hello.comand then enter machine code by holding Alt while typing a number on the keypad. (It doesn't work on DOSBox by the way.) Some numbers, such as 0, must be avoided, but there are workarounds; the book from which I learned the trick, Ralph Burger's "Computer Viruses: a High-tech Disease", recommended first creating a program that read numbers in ASCII and output the corresponding binary, a sort of proto-assembler, which in turn could be used to create more complex executables.
I created a HELLO.COM program by typing the following, where the numbers are typed on the numberpad with the Alt key held:
180 9 190 9 1 205 33 205 32 hello$which is perhaps more recognizable to DOS programmers when converted to hex:
B409 BA0901 CD21 CD20 hello$It is the machine code for:
MOV AH, 09This instructs DOS to print the '$'-terminated string at address 0x109 and then exit. When .COM files are loaded, DOS places their contents at address 0x100 (locations 0 to 0x100 are populated with miscellaneous information such as the command-line), hence the 0x109.
MOV DX, 109h
INT 21h
INT 20h
Thus with 9 bytes plus the size of the message, plus a byte for the terminator, we get a valid DOS program. We can type raw machine code from the keyboard to produce a full program.
Linux on x86 systems is less straightforward. The machine code is similar, but there must also be an ELF header (not strictly true: in some circumstances, the entire machine code can be placed within a truncated ELF header!), making binaries more tedious to construct by hand. However, certain kernel configurations allow different header types, some of them brief enough to be easily memorized and hand-rolled.
Minimalist Android
How about Android? An APK file is a ZIP file containing, among other files, the Dalvik executable in a DEX file. We're interested in minimizing this DEX file, whose full specification is well-documented.
All Android code must lie in some class, and Android applications typically inherit from a library class such as Activity, so we must also record information such as the class name, access rights, and inheritance. This, in turn, requires a strings section so we can store the class names, as well as invoked library functions and function signatures. Other overheads include the header and the map section. We can cheat a little by defining the UI with XML, so it won't contribute to the size of the DEX file.
After compiling to Java class files, most or all the R*.class files can be removed before making a DEX file,since the constants they contain are hardcoded in other class files by javac. For some projects, R$styleable must be retained, though this class appears to have since been removed from the public API.
I chose to write a program that parsed the DEX file from the HelloAndroid example and output only the necessary sections rather than attempt to create a DEX file from scratch. I found I could safely elide the source filenames, debug information and annotations. The result consists of 632 bytes, though we could trivially shrink this further by using a shorter name for the class.
0000000: 6465 780a 3033 3500 2f4f 153b 3623 8747 dex.035./O.;6#.GOnly the 4 16-bit words at 0x128 and the 9 16-bit words at 0x140 are actual Dalvik bytecode. They belong to the constructor and the onCreate method respectively.
0000010: 6d02 4697 5b1e 959d a8b1 2f0f 9c3a a14f m.F.[...../..:.O
0000020: 7802 0000 7000 0000 7856 3412 0000 0000 x...p...xV4.....
0000030: 0000 0000 f001 0000 0a00 0000 7000 0000 ............p...
0000040: 0500 0000 9800 0000 0300 0000 ac00 0000 ................
0000050: 0000 0000 0000 0000 0500 0000 d000 0000 ................
0000060: 0100 0000 f800 0000 6001 0000 1801 0000 ........`.......
0000070: 6201 0000 6a01 0000 6d01 0000 8501 0000 b...j...m.......
0000080: 9a01 0000 bc01 0000 bf01 0000 c301 0000 ................
0000090: c701 0000 d101 0000 0100 0000 0200 0000 ................
00000a0: 0300 0000 0400 0000 0500 0000 0500 0000 ................
00000b0: 0400 0000 0000 0000 0600 0000 0400 0000 ................
00000c0: 5401 0000 0700 0000 0400 0000 5c01 0000 T...........\...
00000d0: 0100 0000 0000 0000 0100 0200 0800 0000 ................
00000e0: 0300 0000 0000 0000 0300 0200 0800 0000 ................
00000f0: 0300 0100 0900 0000 0300 0000 0100 0000 ................
0000100: 0100 0000 0000 0000 ffff ffff 0000 0000 ................
0000110: e101 0000 0000 0000 0100 0100 0100 0000 ................
0000120: 0000 0000 0400 0000 7010 0000 0000 0e00 ........p.......
0000130: 0300 0200 0200 0000 0000 0000 0900 0000 ................
0000140: 6f20 0100 2100 1500 037f 6e20 0400 0100 o ..!.....n ....
0000150: 0e00 0000 0100 0000 0000 0000 0100 0000 ................
0000160: 0200 063c 696e 6974 3e00 0149 0016 4c61 .....I..La
0000170: 6e64 726f 6964 2f61 7070 2f41 6374 6976 ndroid/app/Activ
0000180: 6974 793b 0013 4c61 6e64 726f 6964 2f6f ity;..Landroid/o
0000190: 732f 4275 6e64 6c65 3b00 204c 636f 6d2f s/Bundle;. Lcom/
00001a0: 616e 6472 6f69 642f 6865 6c6c 6f2f 4865 android/hello/He
00001b0: 6c6c 6f41 6e64 726f 6964 3b00 0156 0002 lloAndroid;..V..
00001c0: 5649 0002 564c 0008 6f6e 4372 6561 7465 VI..VL..onCreate
00001d0: 000e 7365 7443 6f6e 7465 6e74 5669 6577 ..setContentView
00001e0: 0000 0001 0102 8180 0498 0203 01b0 0200 ................
00001f0: 0b00 0000 0000 0000 0100 0000 0000 0000 ................
0000200: 0100 0000 0a00 0000 7000 0000 0200 0000 ........p.......
0000210: 0500 0000 9800 0000 0300 0000 0300 0000 ................
0000220: ac00 0000 0500 0000 0500 0000 d000 0000 ................
0000230: 0600 0000 0100 0000 f800 0000 0120 0000 ............. ..
0000240: 0200 0000 1801 0000 0110 0000 0200 0000 ................
0000250: 5401 0000 0220 0000 0a00 0000 6201 0000 T.... ......b...
0000260: 0020 0000 0100 0000 e101 0000 0010 0000 . ..............
0000270: 0100 0000 f001 0000 ........
Thursday, January 22, 2009
Developing Android without Eclipse or Ant
The Android documentation recommends using Eclipse for development, but this is sluggish on my laptop, and feels cluttered on compact screens. A stated alternative is to use Ant, but this is also unnecessary as the build commands it invokes can be easily extracted and executed manually. This suits my preference for a minimalistic or practically non-existent IDE, especially on laptops, as well as my distaste for editing XML. As a bonus, on Ubuntu, I install one package:
$ sudo apt-get install sun-java6-jdk
along with the Android SDK and I'm ready to develop for Android. In contrast, the Ant package has several dependencies, and the required version of Eclipse is newer than the currently available Ubuntu package.
Here are the details:
$ SDKDIR=~/android-sdk-linux_x86-1.0_r2 # Where I extracted the SDK.
$ PATH=$SDKDIR/tools:$PATH
$ activitycreator -o somepath some.project.name
$ cd somepath
At this point Ant can build the project, but masochists like me will prefer to shun Ant and run the underlying commands themselves. The following command generates R.java from the resources:
$ aapt p -m -J src -M AndroidManifest.xml -S res -I $SDKDIR/android.jar
Next, the source is compiled to .class files. This is why we need the JDK:
$ mkdir bin/classes
$ javac -encoding ascii -target 1.5 -d bin/classes \
-bootclasspath $SDKDIR/android.jar src/some/project/*
# When libs exist, append -classpath=libs/*.jar
These files contain instructions for the JVM. They are converted to Dalvik bytecode via:
$ dx --dex --output=bin/classes.dex bin/classes # If libs exist, append libs/*.jar
The resources and assets are packaged:
$ aapt p -f -M AndroidManifest.xml -S res -I $SDKDIR/android.jar -F bin/projectname.ap_
# When assets exist, add -A assets
This package is itself packaged with the Dalvik bytecode to make the final product:
$ apkbuilder bin/something.apk -z bin/projectname.ap_ -f bin/classes.dex -rf src -rj libs
# Use -u for unsigned builds.
Now if I could only roll my own Dalvik compiler for a language I like, I could avoid the Java SDK, as well as Java itself.
$ sudo apt-get install sun-java6-jdk
along with the Android SDK and I'm ready to develop for Android. In contrast, the Ant package has several dependencies, and the required version of Eclipse is newer than the currently available Ubuntu package.
Here are the details:
$ SDKDIR=~/android-sdk-linux_x86-1.0_r2 # Where I extracted the SDK.
$ PATH=$SDKDIR/tools:$PATH
$ activitycreator -o somepath some.project.name
$ cd somepath
At this point Ant can build the project, but masochists like me will prefer to shun Ant and run the underlying commands themselves. The following command generates R.java from the resources:
$ aapt p -m -J src -M AndroidManifest.xml -S res -I $SDKDIR/android.jar
Next, the source is compiled to .class files. This is why we need the JDK:
$ mkdir bin/classes
$ javac -encoding ascii -target 1.5 -d bin/classes \
-bootclasspath $SDKDIR/android.jar src/some/project/*
# When libs exist, append -classpath=libs/*.jar
These files contain instructions for the JVM. They are converted to Dalvik bytecode via:
$ dx --dex --output=bin/classes.dex bin/classes # If libs exist, append libs/*.jar
The resources and assets are packaged:
$ aapt p -f -M AndroidManifest.xml -S res -I $SDKDIR/android.jar -F bin/projectname.ap_
# When assets exist, add -A assets
This package is itself packaged with the Dalvik bytecode to make the final product:
$ apkbuilder bin/something.apk -z bin/projectname.ap_ -f bin/classes.dex -rf src -rj libs
# Use -u for unsigned builds.
Now if I could only roll my own Dalvik compiler for a language I like, I could avoid the Java SDK, as well as Java itself.
Subscribe to:
Posts (Atom)