I'm Nicholas FitzRoy-Dale, a software developer from Sydney, Australia. I'm interested in embedded systems and operating system research, code optimisation, 8-bit music, rock climbing, shiny things...
I've had to do this twice now, and if I understand my computer science mythology correctly that means I will need to do it an infinite number of times, so:
split_bootimg.pl from here, or use my mirror. boot.img to get the kernel and ramdisk files.Lots of information on Android's (simple) boot.img format is here. Thanks to William Enck for split_bootimg.pl.
Arduino-maple is a program for 16MHz Atmega-based devices (such as the Arduino) which enables them to impersonate a Sega Dreamcast for the purpose of communicating with devices attached to Sega's proprietary Maple bus. The practical upshot of this is that you can use an Arduino or similar cheap board connected to a PC to communicate with Dreamcast controllers and Visual Memory Units.
The code requires avr-gcc, and has been tested on Debian Linux, Mac OS X, and Windows (use winavr for Windows). It is still quite rough code, so proceed at your own risk. It is known to be able to read from and write to controllers and the Dreamcast Visual Memory Unit.
The code has very specific timing requirements and will almost certainly only run on an ATmega part clocked at a 16MHz using a crystal oscillator.
Download arduino-maple from bitbucket (or download a snapshot: arduino-maple-tip.tar.gz)
To set it up you'll need to compile the code and get it onto the Arduino (or other ATmega part). Make sure avr-gcc and friends are in your path, then type ''make''. If that works, ensure the port is correct for your computer in the Makefile (it's the line starting PORT=), and type ''make upload'' to run avrdude and upload the code.
After that, connect one end of a Maple bus to your Arduino. I did this by buying a Dreamcast controller on EBay for £4 and cutting the connector off. Attach the wires as follows:
Once you have that set up, you can run a Python program, ''maple.py'', to test. If you have a VMU, ensure it is connected to the controller's upper port first. The program will print out information about the controller and VMU, display a picture of Astro Boy on the VMU, and sit in a loop reading the controller. Press some buttons on the controller, and you'll see the changes to the controller state displayed by the test code. Press ctrl-c to exit the test program.
Other test programs:
I owe a huge debt of thanks to Marcus Comstedt for his very helpful Dreamcast information pages, and to Ikalogic for their low-cost logic analyser.
Changes:
22/Oct/2010: Reading from the VMU is now stable thanks to several code tweaks. Also, no extra hardware is required (the previous version needed some external pull-up resistors).
24/Oct/2010: Reading from the VMU's flash is now supported.
Time to blog about some older projects...
I made a silly Safari extension to rewrite Google News in an 8-bit style.
Despite being a bit silly, this project had a real purpose, which was to make the Google News page less cluttered. Most of the extension is about removing things. Google News adds a lot of unnecessary information to the news page -- the only non-news part preserved by 8bitnews is the link to other articles, because this ability to see multiple interpretations of the same story is the best part about Google News.
There are two other parts to the extension.
The first other part adds a custom font. This wasn't hard at all -- extensions can bundle resources and reference them -- but many C64 fonts didn't actually display in Safari for some reason, even though I could preview them with Font Book. I eventually managed to find a reasonably-licensed font that worked.
The final part of the project is the image manipulation. 8bitnews redisplays each image at 4x scale using a Commodore 64 palette. To convert to the C64 palette, I copied the image to a Canvas object, then accessed the image data from there to choose to most appropriate colour. To choose the best colour, each pixel is converted to the HSL colour space. This is important because variations in saturation and luminance are far less visually annoying than variations in hue.
The pictures mostly look pretty bad, but sometimes there are some gems.
An interesting security consideration: the extension JavaScript is injected into the Google News page and thus behaves as if it were served by the Google News web server. This means that the extension script is prohibited from accessing the image data of images that were served by other Web sites, due to the same-origin policy. Happily, Google News seems to encode about 90% of their images as base64 and include them directly in the HTML page, so this wasn't a problem in practise.
(Incidentally, this is a bit of a weird policy... if the browser makers are worried about malicious (XSS-injected, say) JavaScript modifying an image, well, the JS can easily hide that image and substitute its own without violating the policy. If they are worried about information leakage, well, the JS has access to a whole lot of metadata about the image, such as its width and height -- these may have been supplied by a third party as well. So the policy seems rather inconsistent.)
I wanted to do some performance monitoring on an HTC Desire phone -- nothing complex, just to be able to read the CPU cycle counter. Unfortunately this is more complicated than one might expect, because
To cut a long story short, it turns out the reason for the second bullet point above is that the kernel doesn't include support for the perf_events framework for the QSD 8250, which is the SOC present in the HTC Desire. Fortunately, adding the support is easy to do, because the QST 8250 is similar to the already-supported Cortex M8.
So, to do it:
I'm going to focus on step 3. Get the kernel -- currently you can do that this way: (source):
git clone git://github.com/teamdesire/cm-kernel.git
cd cm-kernel
make cyanogen_bravo_defconfig
make
Apply the patch I made: qst_8250_perf_events.patch.
Rebuild the kernel according the above instructions and generate a boot.img. If you're going to do this via mkbootimg, the command-line to use is this:
mkbootimg --cmdline 'no_console_suspend=1 msmsdcc_sdioirq=1
wire.search_count=5' --kernel zImage --ramdisk boot.img-ramdisk.gz
--base 0x20000000 -o new.boot.img
Flash it from the clockwordmod recovery console by mounting the sdcard, pushing the new image using adb and then using the flash_image command:
adb shell flash_image boot /sdcard/new.boot.img
To test it you'll need perf. I was not in the mood to compile perf, so I wrote a small tool. This tool is named miniperf, but that's a rather ostentatious name because all it does is print the cycle count, sleep for five seconds, print the cycle count again, and exit.
Download it here: miniperf.tar.gz
It compiles with agcc. You will have to change the obvious in the Makefile. Note that the cycle counter is reset when you start miniperf. I have tested it for all of five minutes, so give no guarantees that this works or does anything at all. :)
Happy cycle counting!
Python exceptions are really helpful but they're also rather ugly. Here's a mean one I encountered today. Don't try to interpret it -- it's only here to show off its ugliness:
I wanted it to look more like this:
So I wrote some code to do that. Specifically, the exception formatter I wrote does the following:
All of the above is, of course, configurable.
Here's the code:
Usage:
import bettertb
bettertb.run(your_main_function, arg1, arg2, ...)
This is a pretty quick and dirty work in progress, so email me (nicholas at lardcave) if you have suggestions, fixes, etc. The first major problem is that getting tracebacks is now more rewarding than having the code finish successfully.
Like all students, I hate LaTeX. It's old and outdated and it looks funny and it smells and... aww, I can't go on. I love LaTeX. I love the way it's a standard, and I love the way Leslie Lamport's book about LaTeX is illustrated with anthropomorphic animals. Most of all I love the look of the PDFs it generates.
Despite being awesome, LaTeX shares a couple of annoying characteristics with HTML:
Like HTML, it's hard to syntax highlight. LaTeX is really a very flexible programming language, and that means that doing syntax highlight "right" means you have to do something pretty-much equivalent to actually running LaTeX. Here's an example of Vim doing it wrong:
This is from Vim. Emacs is a bit better, but not perfect -- I'll get to that below. The point here is that Vim has dutifully syntax highlighted all the LaTeX commands. But is that really what you want? For me, the answer is usually "no". The trouble with syntax highlighting in markup languages is that usually the syntax is much less important than the semantics but, because the markup commands are all mixed up in the text, highlighting the markup just makes the text even harder to read. I want "semantics highlighting".
Like HTML, it's really verbose. Have a look at that picture above. When I read that my actual thought process goes something like: "Syntax highlighting LaTeX is textit -- oh, wait, italics -- hard." Inline markup is distracting, so the less of it the better.
In the land of HTML, where every problem has been solved, these problems have been solved with specialised markup languages like Markdown, reStructuredText, and a million subtly-different Wiki formats. All these little languages work the same way: someone made a list of the top 15 or 20 things that you would want to do with text, and then created a language which lets you do those things really easily. So in Markdown, for example, you do "emphasis" (almost certainly rendered as italics) *like this*. This is an improvement over standard HTML <em>italics</em>, and a vast improvement over LaTeX \textit{italics}.
The other cool thing about these little languages is that they are easy to make meaningful highlight modes for. In Markdown, * means "use emphasis", and it's the only thing that could possibly mean "use emphasis" in that document (unless you drop down to HTML). So you can quite easily add a highlight mode for Markdown emphasis in your text editor, and it will be right 100% of the time.
So I took this idea, ran with it, and wrote Texdown. Texdown has nothing to do with Markdown except sharing a name and the idea of replacing a complex language with a miniature one. There is syntax for common LaTeX things -- cite, ref, textit, textbf, texttt, and so on. It comes with a Vim highlight mode.
There is also a very simple extension system, written in Python, which lets you define custom "block extensions". This is best described by example. I frequently want to insert small code snippets into my writing. I normally do this using a LaTeX verbatim environment. But for various reasons (pagination, ease of reference) I tend to end up wanting the code inside a labelled figure. Then, of course, you can't really have a figure without a caption. So I end up writing quite a lot of mark-up every time I want to talk about some code. In Texdown, any contiguous collection of indented lines is called a "block". If you annotate the first line of the block by ending it with "!!macroname", then your custom function, macro_macroname, will be called during parsing with the contents of the block. Here's how it looks for code descriptions:
This calls the macro named "floatcode". You will see that the macro name in the above is coloured rather faintly, making it difficult to notice. This is because you usually will need to write this once and not change it. Here is the LaTeX code produced:
There are a couple of other ways to extend Texdown. Full details are on the Texdown main page.
Preemptively-answered questions:
Q. Where is the source code again?
A. lardcave.net/texdown for the information page, code.nyloncactus.com/hg/texdown for the source.
Q. I use Emacs, which has an actually decent LaTeX mode. So I don't need this, right?
A. Maybe you do, and maybe you don't. Emacs is much better at this than Vim, but you still get an awful lot of clutter -- it makes guesses about what stuff inside LaTeX formatting commands should look like, but it doesn't remove the commands themselves. If you're happy with that, great.
Q. I use LyX / some other WYSIWYG editor. So I don't need this, right?
A. Right. If you like LyX. I couldn't bear it when I tried it, but that was ages ago and it has (surely) improved.
Q. Why didn't you use Restructured Text?
A. I don't like the syntax.
Q. So this is a markup language on top of a markup language on top of a markup language?
A. Yes, but PostScript is also a (programmable, extensible) markup language. It's turtles all the way down.
Q. I like the concept, but I don't like Texdown very much.
A. In that case I have you half-brainwashed already, and if you are a more-than-casual LaTeX user you should definitely try out a couple of other macro languages for LaTeX, or write your own. It's worth it. Texdown solves a very personal set of problems, so it's definitely not for everybody, but the minilanguages-for-LaTeX concept is much bigger than Texdown.
As far as other markup languages go, you may be interested in looking at reStructuredText or asciidoc.
Q. You only did this because you don't know LaTeX well enough to make it look nice!
A. Yes.
Q. All of this stuff could be done using LaTeX macros and it would be just as easy to edit!
A. Maybe. I doubt it.
Q. Script language programmer!
A. LaTeX nerd!
This caused me no end of trouble, and Google wasn't much help:
The example consists of two files. socketmaster.c opens a file you pass it and starts listening on a Unix-domain datagram socket. socketslave.c sends a single-character request to socketmaster's datagram socket. Upon receipt of the request, socketmaster sends the file descriptor of the open file to socketslave's datagram socket. Socketslave reads a small amount of data from the file, displays it, and exits. Run socketslave again and you get the next portion of the file, proving that the file pointer is being shared between the (persistent) socketmaster and the (transient) socketslave.
Thanks to the following three links which contain code to do almost, but not quite, what I want: kragen-hacks; blackhats; docs.hp.com.
This post is about device drivers and owes a lot to papers written by Leonid Ryzhyk.
Most devices are asynchronous. You tell the device to do something, then some time later it lets you know that it's finished. The typical programming model for asynchronous devices uses callbacks, something like this:
read_bytes():
write_to_device_register(READ_DATA)
device_irq_handler():
if(read_from_device_register(STATUS) & DATA_READY)
...
The problem with this model is that it's kind of hard to read. It's particularly annoying if you are doing something which involves lots of interaction with the device, such as initialisation:
void init(int state)
{
register_callback(init, state);
static int counter;
try_again:
switch(state) {
case 1:
write_to_device_register(SETUP1, ...);
break;
case 2:
if(there was an error) {
counter += 1;
if (counter < 10) {
goto try_again;
} else {
die();
}
}
write_to_device_register(SETUP2, ...);
break;
case 4:
handle possible errors;
default:
panic();
}
}
void device_irq_handler(void)
{
if(callback registered) {
callback();
}
}
It would be much easier to read the code if the device behaved synchronously. Then you could just write this:
void init(void)
{
int counter;
for(counter = 0; counter < 10; counter++) {
write_to_device_register(SETUP1, ...);
if(no error encountered);
break;
}
if(error_encountered) {
die();
}
write_to_device_register(SETUP2, ...);
handle possible errors;
}
So how do you make an asynchronous device behave synchronously? There are lots of ways. The most obvious way is simply to poll the device. This may even be feasible for some devices in some situations (for example, when initialising the device), but, in general it's not a feasible option, because the cycles consumed by polling the device could be better spent doing something (anything!) else.
The second way is to use threads. Under this approach, write_to_device_register() would go to sleep on some synchronisation primitive. The IRQ handler would wake up any thread sleeping on the synch primitive. This approach is pretty much what the Linux kernel does.
Threads have their problems: they really require a lot of thinking to make sure you get both correctness and performance out of the device driver you're writing. For example, Linux allows multiple threads to execute device driver code simultaneously. Multi-threaded drivers are signficant source of device driver bugs.
But I wasn't at the stage of writing concurrency bugs. I just didn't want to manage more than one thread. So instead I abused the pre-processor to create the illusion of synchronous device operation while secretly using callbacks.
Here's how that device init function looks using this approach:
EC_FUNCTION(init)
static int counter;
EC_START
for(counter = 0; counter < 10; counter++) {
EC_WRITE(SETUP1, ...);
if(no_error)
break;
}
if(error) {
die();
}
EC_WRITE(SETUP2, ...);
handle_possible_errors();
EC_END
EC_FUNCTION_END
This has the same block structure as the threading version, and is pretty easy to read (once you get over the yucky pre-processor macros). But what is that tell-tale "static" doing in front of "int counter"?
That's right, this is just syntactic sugar over a callback-based model. After preprocessing, it looks something like this:
void init(struct device_info *info)
{
static int counter;
static void *__label = &&label0;
goto *__label;
label0:
for(counter = 0; counter < 10; counter++) {
__label = &&label1;
device_write(SETUP1, ..., init, info);
goto end;
label1:
if(no_error)
break;
}
if(error) {
die();
}
__label = &&label2;
device_write(SETUP2, ..., init, info);
goto end;
label2:
handle_possible_errors();
__label = &&label0;
end:
;
}
Hideous, huh? The good thing is, you only need to get this sort of thing right once, and then you don't need to see it again.
This approach has some really good points: firstly, you get complete control over where you could be pre-empted in a very intuitive way: when you interact with the device. Any internal state manipulation has no chance of being corrupted. It's not perfect, though: as you can see, you can't use local variables. If you do want to make use of local variables, you need to add some code to save and restore the stack -- essentially continuations.
You can download my preprocessor macros here: event_chain.h.
If you find this sort of thing interesting you should look at Leonid Ryzhyk's publications, particularly "Dingo: taming device drivers".
EDIT: This page gives another summary of the same technique (thanks to Benno for the link)
For benchmarking, I wanted to be able to replay an event sequence. For example, I wanted a test to open the browser, browse to a Web page, scroll around on the page, and then return to the application launcher. Android offers lots of ways to do this, but because I like systems programming (and haven't touched Java in years) I picked quite a low-level one: capturing and injecting Linux input device events.
Android uses the Linux input system in the standard way, which means events from the keyboard, touchpad, and so forth are available at /dev/input/eventX, where X is some number starting from 0. It is quite straightforward to record these events to a file -- each event arrives as a struct input_event, which is (on Android) a 128-byte structure containing a timestamp, an event type, and a payload.
Recording events is easy. What about playing them back? I started dreaming up something that would rename the /dev/input/eventX files and create PTYs for each, but then I discovered that there is a far easier way: thanks to a feature added early in the 2.6 kernel series, you can just inject events by writing struct input_events back to the relevant files!
This ease of debugging really is an advantage of using a fully-fledged kernel rather than a custom or cut-down operating system.
Anyway, the end result is two programs, "record" and "replay". The "record" program reads events from /dev/input/eventX and writes them to a file named /sdcard/events. The "replay" program reads this file and replays the events in real time.
The programs read from and write to /dev/input/eventX, even though /dev/uinput should in theory work -- it doesn't appear to on the ADP1.
Both programs are quite "proof of concept", and probably only work on the HTC Dream for now, but they are very simple and easy to adapt.
Update 30/Dec/2009: Aaron made some changes to "replay" which should give much smoother results on OpenMoko phones.
injectevents.tar.gz (6k)
Update 1/Jul/2012: there have been a few questions about this recently. Nice to see it's still being used! Here is some extra information.
To build the code:
Install the Android NDK and set it up so that ndk-build is in your path.
Then create a directory called jni/ and put Android.mk into it.
Then move the src/ directory inside the jni/ directory.
Then you can run ndk-build to build the binaries.
To install:
You need root access to your phone, then run
adb shell
to get a shell
Put record and replay somewhere you can execute them. /data/local/tmp is a good place -- you can use adb push for this, eg
adb push record /data/local/tmp/record
You might then need to "chmod 555 /data/local/tmp/record" to make it executable.
Some people have emailed me asking for help on running the code from within a Java test framework. I can't help you there I'm sorry. You would run replay, and then you would have to check the expected result somehow. Robotium for example can tell you about the state of the GUI, so if you wanted to check that, e.g., a particular GUI change had occurred, you could run replay and then investigate the GUI with Robotium.
When I used the replay code, it was for benchmarking, not testing. So I wrote my own Android apps to call "replay" and then check the state of the GUI directly.
This blog post is about some of the terrible ways you can abuse Python byte code: specifically, by using it to implement lightweight function calls ("GOSUB") directly in byte code. Doing this is obviously stupid and disgusting, and (spoiler) regular Python function calls are fast enough to make this hack not worth the effort. But trying it was quite interesting.
We don't need a new namespace, or exception handling, or any of the other nice features that Python functions provide. In fact the only thing we need is support for 1) jumping to an arbitrary location and then 2) returning to wherever we came from later. That is, we need GOSUB.
Jumping to arbitrary locations is very easy, since Python bytecode has a JUMP_ABSOLUTE opcode. Unfortunately the argument to this opcode must be an offset calculated at compilation time -- there is no way to change the address of a JUMP_ABSOLUTE statement from within the bytecode itself. This makes returning to wherever we came from later impossible with JUMP_ABSOLUTE -- unless we only ever call the subroutine from one location, which isn't true in general.
Fortunately, more devious people than I think about these problems: Phillip J. Eby has discovered that a certain opcode, END_FINALLY, normally used at the end of Python finally blocks, does its work by taking the address to return to from the stack. If we put the location we want to jump to on the stack and call END_FINALLY, we can jump wherever we want. Effectively, it's a computed GOTO. Sadly, END_FINALLY was designed as part of the exception handling machinery and not as part of the dodgy-hack-supporting machinery. As a result, the code is a little more complicated than you might think -- but not much.
This hack can be nicely abused to implement GOSUB, like so:
0 LOAD_CONST 4 (12)
3 LOAD_CONST 1 (37)
6 SETUP_LOOP 3 (to 12)
>> 9 JUMP_ABSOLUTE 14
12 POP_BLOCK
13 RETURN_VALUE
>> 14 LOAD_CONST 2 (2)
17 INPLACE_ADD
18 ROT_TWO
19 LOAD_CONST 3 (32)
22 END_FINALLY
Here we are calling a subroutine that adds 2 to the value on the top of the stack. First we push a value to return to after the subroutine finishes onto the stack -- in this case we return to byte 12. Then we push an argument to the subroutine, in this case 37. SETUP_LOOP creates a block for looping or exception handling, and is required to make the END_FINALLY hack work. We then jump directly to the subroutine at byte 14.
In the subroutine we add 2 to whatever is at the top of the stack. Our stack then contains the return address, followed by the result of our calculation. We're about to jump to the return address, so we want that at the top of the stack. ROT_TWO does that for us by swapping the top items at the top of the stack. We then LOAD_CONST a magic value that is part of the END_FINALLY hack -- it is WHY_CONTINUE, a number that has special meaning to the CPython interpreter. It pops WHY_CONTINUE off the stack, which instructs it to continue execution at the value at the top of the stack -- which is now our return value.
Execution then resumes at byte 12, which removes the block we created with SETUP_LOOP, and then returns the value at the top of the stack, which is the return code from our subroutine. In this case the function returns the value 39.
There are some problems with this approach:
POP_BLOCK, in addition to removing a block from the block stack, also returns the stack level to the level that it was when SETUP_LOOP was called. So if the subroutine returns any values on the stack you have to be careful. One simple way to deal with this is to have subroutines that take as many arguments as they return (i.e. 1).BREAK_LOOP now has useless (but well-defined) behaviour: it acts as if the subroutine has immediately returned, but doesn't provide any way of letting the caller know what happened. BREAK_LOOP still works if the subroutine sets up an actual (real) loop by pushing another block to the block stack. It should actually be possible to "fix" this by having SETUP_LOOP target an exception-handling block, essentially giving the subroutine a choice of two different locations to return to -- taking the nastiness to the next level!END_FINALLY that is only guaranteed to work in the canonical C implementations of Python, and even then only versions 2.3 and upward.Adding an extra opcode would make this much nicer. There was some talk back in 2006 about implementing a JUMP_TOP opcode, which would simply jump to the bytecode position at the top of the stack. Unfortunately, the motivation for adding it was to add a "switch" statement to Python, and nowadays that doesn't seem very likely.
Fortunately, there is no real motivation to use this hack. Running a simple test (10000000 iterations, on a 2.2Ghz MacBook) gives the following results:
| Method | Time in seconds |
| GOSUB | 2.78 |
| CALL_FUNCTION, hand-written | 3.00 |
| CALL_FUNCTION, Python | 3.67 |
In these results, "GOSUB" is the hand-written GOSUB hack discussed above, and the other two use the regular Python function call mechanism: one with hand-written bytecode, and the other written in regular Python and compiled in the normal way. Even with ten million calls there isn't that huge a speed improvement to make GOSUB worthwhile.