# Weston frame buffer backend

Just over a week ago everyone’s favourite Xorg replacement, Weston, gained a frame buffer backend I put together as part of some university work. It was remarkably easy to write, since almost all of the code already existed in the DRM and RPI backends; I just needed to hook pixman up to /dev/fb0 and everything worked!

Weston’s code base was a pleasure to work on. Hopefully someone stuck on a frame buffer somewhere finds this work useful. Since I did this work, I also got the frame buffer backend working on FreeBSD (as part of the same university project), but haven’t had time to update, tidy up and submit my patches yet. They’re pretty hacky in (many) places.

Without further ado, a gratuitous flowery screenshot (taken using fbcat):

Weston running on a Linux frame buffer, taken on 2013-01-15.

# Adventures with an ATmega

As part of some university coursework, I’ve recently been playing around with an Atmel 8-bit microcontroller in a quest to build a data logger for home brewing. The aim is to log various sensor readings over the course of primary fermentation of a batch of beer to see how it’s progressing without having to disturb the brew.

While working with hardware is fun, it has the downside that you’re working with hardware. Things break as much as they do in software, but are harder to debug. A nice solution to this is to use a simulator to test the software, rather than using the hardware itself. I’ve been using the simavr simulator. It’s got all the right features, but more importantly its code is easy to understand and extend. In fact, most of the simulator is written as a library which one can build a simulated circuit board around.

I’ve built simulations of several of the components used in the brewing logger now, including an SD card and a flash memory. The code isn’t brilliant, but they’re working well enough to get my firmware booting. Hopefully they might be useful to other people too — hence the code is on gitorious. The SD card simulator is for a generic SDv2 card. The flash memory is for an ST M25P16 (but should support any of the M25P family, with a little work). The serial LCD is for a custom LCD daughter board provided by my university, so that’s probably not so useful. The RHT03 temperature/humidity sensor is general purpose; as is the DS3231 real-time clock.

Put together, and with a little extra work, these will allow closed loop testing of the microcontroller firmware — without ever having to go near the hardware itself. Bliss. (This is all under the misguided assumption that the simulations are sound and complete, but they’ll get there eventually.)

As an example of how easy simavr makes this, take a look at the code needed to instantiate and hook up the humidity sensor simulation:

/* Create the sensor. */
rht03_t rht03;
rht03_init (avr, &rht03);

/* Connect its bidirectional data pin to pin D3 on the microcontroller. */
avr_connect_irq (avr_io_getirq (avr, AVR_IOCTL_IOPORT_GETIRQ ('D'), 3), rht03.irq + IRQ_RHT03_DATA);
avr_connect_irq (rht03.irq + IRQ_RHT03_DATA, avr_io_getirq (avr, AVR_IOCTL_IOPORT_GETIRQ ('D'), 3));

# All aboard the Bendy Bus

Have you ever written a client for a D-Bus service, then had difficulty in testing it because you need to find a way to set up the state of the D-Bus service, run your test, then set up the service in a completely different manner, rinse and repeat…all while running a modified version of the service’s binary in parallel with your system installation of it, and without doing anything which might cause your personal data to be accidentally eaten?

Having done some hacking on Telepathy and EDS clients I can, unfortunately, say “yes” to all of the above. Since problems are problematic, I’ve been hacking on a tool called Bendy Bus, which will hopefully alleviate some of this pain.

Bendy Bus is a project I’ve been working on as my final year university project, but I intend for it to be most useful outside of (hopefully) getting me marks for my degree. The basic idea of Bendy Bus is that you fuel it up with a description of a nondeterministic finite state automaton which represents the D-Bus service you’re using, plus a D-Bus introspection XML file describing all the relevant D-Bus interfaces. Bendy Bus will use the FSM description to simulate the D-Bus service, and run as a wrapper around the client program you’re trying to test. It’ll set up a private dbus-daemon instance for your client program, and expose all the simulated D-Bus objects on this bus.

Bendy Bus will listen for D-Bus method calls and property changes made by your client program, and execute transitions within the FSM as coded in your FSM description file. These transitions may, for example, change the FSM’s state, change data stored in the FSM (technically making it a nondeterministic DFSM, but that’s immaterial), emit D-Bus signals, throw D-Bus errors, etc. Why do I say it’s a nondeterministic FSM? Because you may specify several transitions between the same pair of states which are triggered by the same (for example) D-Bus method call. Bendy Bus will randomly choose one of the transitions to take. For example, if your client program calls a frobnicate : string → string D-Bus method, you could code one transition which successfully replies to the method call with a string return value, and another transition which simulates a failure in the D-Bus service by throwing a D-Bus error instead.

It’s in this fashion that Bendy Bus is actually designed as a fuzzing tool. You can code up a full description of every possible state and transition in your D-Bus service, then set your client program running in the Bendy Bus wrapper, and it’ll randomly explore the service’s state space until a termination condition is met. For example, the client program could crash (in which case a bug’s been found!), a D-Bus activity timeout could be reached (if your client program hasn’t made any D-Bus calls for a few seconds, for example), or a global timeout could be reached. At this point, the test harness can restart your client program and start the whole thing all over again with a different random seed value, causing different execution paths to be explored, and more of your client’s code to be covered.

Of course, Bendy Bus is still young, so features are missing, there are plenty of bugs, and documentation is basically non-existent. A couple of the big features on the list are to implement support for unit testing (which would tone down the fuzz testing aspect of Bendy Bus, and allow deterministic unit tests to be written for D-Bus client programs), implement better error reporting in the machine description parser and better logging during simulation, write a language specification and GtkSourceView highlighter, and write documentation. Help on any of these (except the unit testing stuff, which I have to keep for myself for my university project) would be greatly appreciated.

More than anything, it would be great if people could play with Bendy Bus and see if it’s useful for them (and if not, what could be done to improve it). In the repository at the moment are a couple of example machine description files for Telepathy. They can be used to get a randomly-generated contact list to appear in Empathy, using the following command:

bendy-bus machines/telepathy-cm.machine machines/telepathy-cm.xml \ --test-program-log-file=test-program.log \ --dbus-daemon-log-file=dbus-daemon.log \ --simulator-log-file=simulator.log \ -E FOLKS_DEBUG=telepathy -E EMPATHY_DEBUG=all -E G_MESSAGES_DEBUG=all \ -- empathy

# End of the summer

It's come to the end of the summer, and the end of my internship with Collabora. They've enabled me to spend three months helping work on adding meta-contacts support to Empathy in the form of libfolks; something which I've thoroughly enjoyed. Thank you to all my friends and colleagues at Collabora for letting me do this!

Term starts at university for me again in the next few weeks, so I expect to disappear back into the world of degree-enabling work, but I hope to be able to poke my head up from my little hole every so often, and possibly even submit a patch or two.

# Introspectable libgdata

Now that full term at university has finished, I have a little free time (inbetween sleeping, doing all the holiday work, and that celebration thing that people seem to do) to spend on projects. Today, I got round to adding GObject introspection support to libgdata. I think some of the Makefile changes I made were a little hacky, but they seem to work. If anyone wants to use libgdata from an interpreted language which has GIR support, it should now be possible.

In university news, things have gone well this term, and I managed to (precariously) stay on top of the rolling mountain of work. I've now got two weeks' stay in Cambridge to help shepherd interviewees around for their application interviews before I go home and do Christmassy things.

It took me until about half way through the term to notice that I was actually walking past Collabora's UK office every morning (opposite King's College). It was quite a shock when I noticed. It was also a shock to see they weren't at the computer lab's recent careers fair. Perhaps missing a trick there?

# End of the beginning

It's been a week now since I had my last ever lessons and left school for good. I've been at that school for seven years now, and it's a little weird knowing I'm never again going to have to go back there (apart from exams). I'm now on exam leave, leading up to A-level exams throughout June. After that, I'm free!

The last seven years have been fairly good, on the whole. I made some good friends, learnt a fair bit, and amassed a collection of award ties which is almost into double figures. The school does seem to have a fetish for giving out ties.

What's next? A summer of partyingwork, leading up to university next year, assuming I get the grades in the coming exams. For that reason I might be out of contact quite a bit for the next month, partyingstudying.

In other news, I released libgdata 0.3.0 a few days ago, which features a lot of cleanup work, plus an access control list framework contributed by Thibault Saunier as part of his GSoC work on Nautilus.

# String swap algorithms

When I went for interview at Imperial College, my interviewer (Dr. P. Kelly) asked me quite a nice question, which (for some unearthly reason) I decided to follow up on afterwards.

The question was a simple one: given a string (e.g.) "examplesgnome" consisting of two substrings (in this case, "examples" and "gnome"), how can we swap the two substrings in-place? In the interview, we covered the third method in more detail, but touched upon the other two. Afterwards, I calculated their computational efficiency, and determined while they all have the same upper bound, one has a lower average running time.

### Method one: reversal

This is one Dr. Kelly suggested, which is really rather neat. It consists of two steps: reversing the entire string, then reversing both substrings. For example:

1. examplesgnome
2. emongselpmaxe
3. gnomeexamples

If we take

n

to equal the total number of characters,

a

to equal the number of characters in the smaller substring, and

b

to equal the number of characters in the larger substring, this has:

\left\lfloor \frac{n}{2} \right\rfloor + \left\lfloor \frac{a}{2} \right\rfloor + \left\lfloor \frac{b}{2} \right\rfloor

swaps, so we may as well say it's of linear complexity

O(n)

.

### Method two: cycles

This one was also suggested by Dr. Kelly, and involves taking the first character of the larger substring out to a temporary location, then cyclically moving characters

b

places along into the generated space. Once the strings have been swapped (

n

swaps have taken place), we put the stored character back in the final space. For example:

1. examplesgnome
2. _xamplesgnome
3. gxamples_nome
4. gxa_plesmnome
5. gxamplesmno_e
6. gxampl_smnoee
7. g_amplxsmnoee
8. gnamplxsm_oee
9. gnam_lxsmpoee
10. gnamelxsmpoe_
11. gnamelx_mpoes
12. gn_melxampoes
13. gnomelxamp_es
14. gnome_xamples
15. gnomeexamples

Since each character moves to its final position in one move, the algorithm is intuitively of complexity

O(n)

— but we can go further and say it's of absolute complexity

\sim (n + 2)

, taking the steps to remove the first character and fill the last space into account.

### Method three: reduction

This is the method I came up with during the interview and, with some help, made work. It basically involves swapping the first smaller substring into its final position, then applying the same algorithm to the resulting subsubstrings of the second substring. For example:

1. examplesgnome
2. gnomelesexamp
3. gnomeampexles
4. gnomeexpamles
5. gnomeexmaples
6. gnomeexamples

This is quite a neat one to implement, and will perform

O(n)

swaps in the worst case (when the smaller substring is only one character long, as one character moves to its final position with each swap).

However, what if we consider the case "foobar", where the substrings are "foo" and "bar"? In this case, method three only takes 3 swaps. Obviously, this method is limited in the upper bound to

O(n)

swaps, but it seems it can do the operation in far fewer — as few as

\Omega (a)

.

I haven't got a concrete proof for this, but I believe this is actually of complexity:

\sim (a \left\lfloor \frac{b}{a} \right\rfloor + (b \bmod{a}) \left\lfloor \frac{a}{b \bmod{a}} \right\rfloor)

as the lengths of the substring for each iteration

i

depend on the remainder of

\frac{b}{a}

for the

i - 1

th iteration. This complexity can be manipulated to prove that it's also of complexity

O(n)

:

All-in-all, I'm quite pleased with the interview: even if I'm not successful, it's given me an interesting problem to consider. Corrections and further thoughts on the problem are welcomed.