Hey fellows Debian lovers, and old friends reading this, after more than a decade serving Debian, our greatest and beloved OS, I've finally decided to start blogging. Please, bear with me, I'm still very new at blogging. Thus, constructive comments and mails are welcome So here we actually go with the usual 'quick introduction post': I'm Arnaud Quette, 36 years old, and Debian developer since 2001. I'm leading the upstream project called 'NUT' (Network UPS Tools project) since 2005, and I'm a Free Software hacker since 1997 (incomplete list of contribs and linkedIn profile). I'm working at Eaton, a Debian partner participating in the power protection of our Debian infrastructure (FTP masters and Alioth). If you're a Debian admin, and feel Eaton can help, drop me a mail. My main Opensource contribution, for some years, is to lead 'NUT', and the related power management developments and distribution. As such, I also ensure that all this work lands finely in Debian, and is useful and reliable to users. In the past, I've also been working on some Media Center packages (Coherence UPnP, moovida, LIRC, ...), Synaptics touchpads app and some more. Here is the current list of maintained and co-maintained packages, though not up to date. It's not always that easy to balance between upstream lead and the numerous developments on one hand, and Debian packaging and support on the other hand... Not counting real life and the many others responsibilities I have. Just forgive me for the time it has taken (and is still taking, sometimes) to update my various packages. Just remember that I'm always doing my best So dear Planet Debian readers, I'll be bothering you with some news on power management and GreenIT in Debian. There will be both upstream and Debian developments and releases info, so that you all can react. There may probably be some diversion, on other Debian related topics, one way or another... All this will depend on your feedback, and the balance with my available time and pleasure to share with you these few tech bits. cheers,
Arnaud

For once, I went north. Which means going *into* the city but I also need to explore that part of Managua, right? Therefore, I went down north heading to the lake and Old Cathedral. Surroundings of the Old Cathedral and Presidential House are strange. There is nearly nobody around, few activity. Doesn't look like a city's "heart". I also reached the lakeshore. I already read that managua is more or less "turning its back" to its lake. It's really true. There's nearly no place where one can actually freely reach the lakeshore, at least where I was. Seems that, here also, the nasty habit of bars and restaurants to "privatize" the shores, as one can see in Italy, sometimes Mexico....is also happening. I'm happy we have laws against this in France, indeed. Fun to also see a small recreation park...just like Coney Island, in some way..:) Anyway, I could still reach the lakeshore at some point and take a picture of the Chiltepe Peninsula (guess what on it? A volcano, of course...). I finally went back up through a different neighbourhood than the one I went down. Often "not so nice" streets, in some poor neighbourhood but, again, I always felt very safe....and people are still saying "bon dia" when you meet them. GPS trace is here, as usual.

A year ago, I bought a Logitech Wireless Solar Keyboard K750. I'm particularly picky on keyboards, but this one is good. It has an incredible useful feature: while being wireless, it has no need for disposable or rechargeable batteries, it uses solar power! My problem is that there's obviously no way to know the battery status from Linux, the provided application only working on Windows. And one dark night, while fragging on QuakeLive, my keyboard stopped working: it had no battery left. This activity being quite energy consuming, it emptied the whole battery. Someone should write code to get the battery status and light meter from Linux: challenge accepted! How the keyboard works This keyboard, like many of the new wireless devices from Logitech, uses the Unifying interface. It's an USB receiver that can be attached up to 6 differents devices (mouse, keyboards ). On old Linux kernel, the Unifying receiver is recognized as only one keyboard and/or one mouse device. Recently, a driver called hid-logitech-dj has been added to the Linux kernel. With this driver, each device attached to the receiver is recognized as one different device. What the Logitech application does The Logitech application under Windows works that way: you launch it, and it displays the battery charge level. On the keyboard, there's a special "light" button (up right). When pressed, a LED will light up on the keyboard: green if the keyboard is receiving enough light and is charging, red if the keyboard does not receive enough light and is therefore discharging. Pushing this same button while the application is running will makes the light meter activated: the application will tell you how much lux your keyboard is receiving. Let's reverse engineer this As far as I know, there's nothing in the USB HID protocol that handles this kind of functionality (battery status, light meter ) in a standard way. So the first task to accomplish is, unfortunately, to reverse engineer the program. I discovered a bit too late that Drew Fisher did a good presentation on USB reverse engineering at 28c3. You might want to take a look at it if you want to reverse engineer on USB. I did not need it, but I learned a few things. Anyway, my plan was the following: run the Logitech application inside a virtual machine running Windows, give it direct access to the USB keyboard, and sniff what happens on the USB wire. To achieve that, you need a virtual machine emulator that can do USB pass-through. Both KVM and VirtualBox can do that, but VirtualBox works much better with USB and allow hot(un)plugging of devices, so I used it. To sniff what happens on the USB, you need to load the usbmon Linux kernel module. Simply doing modprobe usbmon will work. You can then use Wireshark which know how to use usbmon devices and understand the USB protocol. USB stuff you need to know You don't need to know much about USB to understand what I'll write about below, but for the sake of comprehensibility I'll write a couple of things here before jumping in. To communicate with an USB device, we communicate with one of its endpoints. Endpoints are regrouped into an interface. Interfaces are regrouped into a configuration. A device might contains one or several configurations. There's also several types of packets in the USB wire protocol, and at least two of them interest us there, they are:

• Interrupt packets, a packet send spontaneously;
• Controls packets, used for command and status operations.

All of this and more is well (and better) explained in the chapter 13 of Linux Device Drivers, Third Edition. Sniffed data Once everything was set-up, I ran my beloved Wireshark. There's a an URB of type interrupt sent each time you press any key with some data in it. Therefore I advise you to plug another keyboard (or use the laptop keyboard if you're doing this on a laptop), otherwise you'll get crazy trying to sniff the keyboard you're typing on. At this point, just launching the application does a bunch of USB traffic. Pressing the "light" button on the keyboard makes even more USB packets coming in and out. Here's the interesting packets that I noticed once I excluded the noise:

• When pressing the "light" button, an URB of type interrupt is sent by the keyboard to the computer;
• An URB control packet is sent by the computer to the keyboard in response;
• Regularly URB interrupt packets are sent just after.

With all this, the next step was clear: understand the packets and reproduce that exchange under Linux. What the packets mean The "go for the light meter" packet The packet sent from the computer to the keyboard is the following. <figure>

Frame 17: 71 bytes on wire (568 bits), 71 bytes captured (568 bits)
    Frame Length: 71 bytes (568 bits)
    Capture Length: 71 bytes (568 bits)
USB URB
    URB id: 0xffff880161997240
    URB type: URB_SUBMIT ('S')
    URB transfer type: URB_CONTROL (0x02)
    Endpoint: 0x00, Direction: OUT
        0... .... = Direction: OUT (0)
        .000 0000 = Endpoint value: 0
    Device: 6
    URB bus id: 1
    Device setup request: relevant (0)
    Data: present (0)
    URB sec: 1340124450
    URB usec: 495643
    URB status: Operation now in progress (-EINPROGRESS) (-115)
    URB length [bytes]: 7
    Data length [bytes]: 7
    [Response in: 18]
    [bInterfaceClass: HID (0x03)]
    URB setup
        bmRequestType: 0x21
            0... .... = Direction: Host-to-device
            .01. .... = Type: Class (0x01)
            ...0 0001 = Recipient: Interface (0x01)
    bRequest: SET_REPORT (0x09)
    wValue: 0x0210
        ReportID: 16
        ReportType: Output (2)
    wIndex: 2
    wLength: 7
0000  40 72 99 61 01 88 ff ff 53 02 00 06 01 00 00 00   @r.a....S.......
0010  22 ad e0 4f 00 00 00 00 1b 90 07 00 8d ff ff ff   "..O............
0020  07 00 00 00 07 00 00 00 21 09 10 02 02 00 07 00   ........!.......
0030  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00   ................
0040  10 01 09 03 78 01 00                              ....x..

</figure> What's here interesting is the last part representing the data. wLength says that the length of the data is 7 bytes, so let's take a look at those 7 bytes: 10 01 09 03 78 01 00. Well, actually, you can't decode them like that, unless you're a freak or a Logitech engineer. And I have actually no idea what they mean. But sending this to the keyboard will trigger an interesting thing: the keyboard will start sending URB interrupt with some data without you pressing any more key. The "light meter and battery values" packet This is most interesting packet. This is the one sent by the keyboard to the host and that contains the data we want to retrieve. <figure>

Frame 1467: 84 bytes on wire (672 bits), 84 bytes captured (672 bits)
    Frame Length: 84 bytes (672 bits)
    Capture Length: 84 bytes (672 bits)
USB URB
    URB id: 0xffff88010c43c380
    URB type: URB_COMPLETE ('C')
    URB transfer type: URB_INTERRUPT (0x01)
    Endpoint: 0x83, Direction: IN
        1... .... = Direction: IN (1)
        .000 0011 = Endpoint value: 3
    Device: 2
    URB bus id: 6
    Device setup request: not relevant ('-')
    Data: present (0)
    URB sec: 1334953309
    URB usec: 728740
    URB status: Success (0)
    URB length [bytes]: 20
    Data length [bytes]: 20
    [Request in: 1466]
    [Time from request: 0.992374000 seconds]
    [bInterfaceClass: Unknown (0xffff)]
Leftover Capture Data: 1102091039000c061d474f4f4400000000000000
0000  80 c3 43 0c 01 88 ff ff 43 01 83 02 06 00 2d 00   ..C.....C.....-.
0010  5d c5 91 4f 00 00 00 00 a4 1e 0b 00 00 00 00 00   ]..O............
0020  14 00 00 00 14 00 00 00 00 00 00 00 00 00 00 00   ................
0030  02 00 00 00 00 00 00 00 00 02 00 00 00 00 00 00   ................
0040  11 02 09 10 39 00 0c 06 1d 47 4f 4f 44 00 00 00   ....9....GOOD...
0050  00 00 00 00                                       ....

</figure> This packets come in regularly (1 per second) on the wire for some time once you sent the "go for the light meter" packet. At one point they are emitted less often and do not contain the value for the light meter anymore, suggesting that the control packet sent earlier triggers the activation of the light meter for a defined period. Now you probably wonder where the data are in this. They're in the 20 bytes leftover in the capture data part, indicated by Wireshark, at the end of the packet: 11 02 09 10 39 00 0c 06 1d 47 4f 4f 44 00 00 00 00 00 00 00. Fortunately, it was easy to decode. Knowing we're looking for 2 values (battery charge and light meter), we just need to observe and compare the packet emitted on the wire with the values displayed by the Logitech Solar App. To achieve this, I looked both at the Logitech Solar App and Wireshark while bringing more and more light near the keyboard, increasing the lux value received by the meter on the Solar App, and saw that the fields represented in blue (see below) where changing in Wireshark. Since 2 bytes were changing, I guessed that it was coded on 16 bits, and therefore it was easy to correlate the value with the Solar App. <figure>

[ ....9....GOOD....... ]
11 02 09 10 39 00 0c 06 1d 47 4f 4f 44 00 00 00 00 00 00 00
4 bytes - 1 byte for battery charge - 2 bytes for light meter - 2 bytes - 4 bytes for GOOD - 7 bytes

</figure> In this example, the battery has a charge of 0x39 = 57 % and the light meter receives 0x0c = 12 lux of light. It's basically dark, and that makes sense: it was night and the light was off in my office, the only light being the one coming from my screen. I've no idea what the GOOD part of the packet is about, but it's present in every packet and it's actually very handy to recognize such a packet. Therefore I'm considering this as some sort of useful mark for now. For the other bytes, they were always the same (0x11 0x2 0x9 0x10 at the beginning, 7 times 0x00 at the end). The 2 bytes between the light meter and GOOD probably mean something, but I've no idea what for now. Building our solar app Now we've enough information to build our own very basic solar application. We know how to triggers the light meter, and we know how to decode the packets. We're going to write a small application using libusb. Here's a quick example. It's not perfect and does not check for error codes, be careful. <figure>

/* Written by Julien Danjou <julien> in 2012 */
#include <linux/hid.h>
#include <libusb.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
 
    libusb_context *ctx;
    libusb_init(&ctx);
    libusb_set_debug(ctx, 3);
    /* Look at the keyboard based on vendor and device id */
    libusb_device_handle *device_handle = libusb_open_device_with_vid_pid(ctx, 0x046d, 0xc52b);
    fprintf(stderr, "Found keyboard 0x%p\n", device_handle);
    libusb_device *device = libusb_get_device(device_handle);
    struct libusb_device_descriptor desc;
    libusb_get_device_descriptor(device, &desc);
    for(uint8_t config_index = 0; config_index < desc.bNumConfigurations; config_index++)
     
        struct libusb_config_descriptor *config;
        libusb_get_config_descriptor(device, config_index, &config);
        /* We know we want interface 2 */
        int iface_index = 2;
        const struct libusb_interface *iface = &config->interface[iface_index];
        for (int altsetting_index = 0; altsetting_index < iface->num_altsetting; altsetting_index++)
         
            const struct libusb_interface_descriptor *iface_desc = &iface->altsetting[al>tsetting_index];
            if (iface_desc->bInterfaceClass == LIBUSB_CLASS_HID)
             
                libusb_detach_kernel_driver(device_handle, iface_index);
                libusb_claim_interface(device_handle, iface_index);
                unsigned char ret[65535];
                unsigned char payload[] = "\x10\x02\x09\x03\x78\x01\x00";
                if(libusb_control_transfer(device_handle,
                                           LIBUSB_REQUEST_TYPE_CLASS   LIBUSB_RECIPIENT_INTERFACE,
                                           HID_REQ_SET_REPORT,
                                           0x0210, iface_index, payload, sizeof(payload) - 1, 10000))
                 
                    int actual_length = 0;
                    while(actual_length != 20   strncmp((const char *) &ret[9], "GOOD", 4))
                        libusb_interrupt_transfer(device_handle,
                                                  iface_desc->endpoint[0].bEndpointAddress,
                                                  ret, sizeof(ret), &actual_length, 100000);
                    uint16_t lux = ret[5] << 8   ret[6];
                    fprintf(stderr, "Charge: %d %%\nLight: %d lux\n", ret[4], lux);
                 
                libusb_release_interface(device_handle, iface_index);
                libusb_attach_kernel_driver(device_handle, iface_index);
             
         
     
    libusb_close(device_handle);
    libusb_exit(ctx);
 

</figure> What the program is doing is the following:

• Request for the Unifying Receiver device based on vendor and product ID
• Get the HID interface
• Detach the HID interface from the kernel driver
• Claim the interface
• Send a control packets, were parameters are defined using the same data we captured earlier
• Read interrupt packets coming in until we receive one we recognize (length 20 containing the "GOOD" string)
• Decode the content (battery charge & light meter)
• Release the interface
• Reattach the kernel driver to the interface

This gives the following:

Found keyboard 0x0x24ec8e0
Charge: 64 %
Light: 21 lux

Challenge accomplished! To be continued Unfortunately, this approach has at least one major drawback. We have to disconnect the Logitech Unifying Receiver from the kernel. That means that while we're waiting for the packet, we're dropping packets corresponding to other events from every connected device (key presses, pointer motions ). In order to solve that, I sent a request for help on the linux-input mailing list. That way, I learned that Logitech is actually using the HID++ protocol to communicate with the devices using the Unifying Receiver. Lars-Dominik Braun managed to get the HID++ specifications from Logitech and published them with their authorization. This opens a whole new world. With that document, I may be able to understand the part I reverse engineered and convert this to a more useful and generic library using the hidraw interface (so we don't have to disconnect the devices from the kernel driver).

Over a year ago when I was considering my first Android phone purchase I setup a test account on my mail server so that I could test email clients on phones and tablets. I used a short password because I didn t want to type a lot on small screens and because typing a password into a random system owned by someone else isn t particularly secure anyway. Then I forgot about the account until I noticed that my mail server was sending out spam. Next time I setup such a test account I ll put rules similar to the following in my Postfwd [1] configuration to stop Postfix from sending such messages. That will prevent the test account from receiving mail from outside or sending mail out of the server. The former is optional (getting a few thousand spam messages in an unused test account is no big deal) but the latter is needed to prevent getting my server blacklisted. id=R_test_recipient ; recipient==test@coker.com.au ; sender!~.*@coker.com.au ; action=REJECT
id=R_test_sender ; sender==test@coker.com.au ; recipient!~.*@coker.com.au ; action=REJECT

• [1] http://postfwd.org/

Related posts:

1. email disclaimers Andre Pang blogs about the annoyance of email disclaimers. For...
2. Email Passwords I was doing some routine sysadmin work for a client...
3. Some Postfix Scripts for dealing with Outbound Spamming I ve just written some small scripts to help me manage...

I've been lazy today: I just went to the same place than yesterday..:-) I actually waslate and missed the meeting with No l who indeed went running in about the same neighbourhood, as well as Martin Bagge who went running on the road to the "Intermezzo" restaurant I described earlier..:-) So, no real fancy description today. And, as usual, the full GPS trace is here. The interesting challenge is to see if I can manage to achieve a run every day..:-). We'll see!

The Debian Edu / Skolelinux project have users all over the globe, but until recently we have not known about any users in Norway's neighbour country Sweden. This changed when George Bredberg showed up in March this year on the mailing list, asking interesting questions about how to adjust and scale the just released Debian Edu Wheezy setup to his liking. He granted me an interview, and I am happy to share his answers with you here. Who are you, and how do you spend your days? I'm a 44 year old country guy that have been working 12 years at the same school as 50% IT-manager and 50% Teacher. My educational background is fil.kand in history and religious beliefs, an exam as a "folkhighschool" teacher, that is, for teaching grownups. In Norwegian I believe it's called "Vuxenupplaring". I also have a master in "Technology and social change". So I'm not really a tech guy, I just like to study how humans and technology interact and that is my perspective when working with IT. How did you get in contact with the Skolelinux/Debian Edu project? I have followed the Skolelinux project for quite some time by now. Earlier I tested out the K12-LTSP project, which we used for some time, but I really like the idea of having a distribution aimed to be a complete solution for schools with necessary tools integrated. When K12-LTSP abandoned that idea some years ago, I started to look more seriously into Skolelinux instead. What do you see as the advantages of Skolelinux/Debian Edu? The big point of Skolelinux to me is that it is a complete distribution, ready to install. It has LDAP-support, MS Windows integration tools and so forth already configured, saving an administrator a lot of time and headache. We were using another Linux based thin-client system called Thinlinc, that has served us very well. But that Skolelinux is based on VNC and LTSP, to me, is better when it comes to the kind of multimedia used in schools. That is showing videos from Youtube or educational TV. It is also easier to mix thin clients with workstations, since the user settings will be the same. In our VNC-based solution you had to "beat around the bush" by setting up a second, hidden, home-directory for user settings for the workstations, because they will be different from the ones used on the thin clients. Skolelinux support for diskless workstations are very convenient since a school today often need to use a class room projector showing videos in full screen. That is easily done with a small integrated media computer running as a diskless workstation. You have only two installs to update and configure. One for the thin clients and one for the workstations. Also saving a lot of time. Our old system was also based on Redhat and CentOS. They are both very nice distributions, but they are sometimes painfully slow when it comes to updating multimedia support and multimedia programs (even such as Gimp), leaving us with a bit "oldish" applications. Debian is quicker to update. What do you see as the disadvantages of Skolelinux/Debian Edu? Debian is a bit too quick when it comes to updating. As an example we use old HP terminals as thinclients, and two times already this year (2012) the updates you get from the repositories has stopped sound from working with them. It's a kernel/ALSA issue. So you have to be more careful properly testing the updates before you run them in a production environment. This has never happened with CentOS. I also would like to be able to set my own domain-settings at install time. In Skolelinux they are kind of hard coded into the distribution, when it comes to LDAP and at least samba integration. That is more a cosmetic/translation issue, and not a real problem. Running MS Windows applications within the Skolelinux environment needs to be better supported. That is, running them seamlessly via RDP, and support for single-sign on. That will make the transition to free software easier, because you can keep the applications you really need. No support will make it impossible if you work in a school where some applications can't be open source. As for us we really need to run Adobe InDesign in our journalist classes. We run a journalist education, and is one of the very few non university ones that is ok:d by Svenska journalistf rbundet (Swedish journalist association). Our education gives the pupils the right of membership there, once they are done. This is important if you want to get a job. Adobe InDesign is the program most commonly used in newspapers and magazines. We used Quark Express before, but they seem to loose there market to Adobe. The only "equivalent" to InDesign in the opensource world is Scribus, and its not advanced enough. At least not according to the teacher. I think it would be possible to use it, because they are not supposed to learn a program, they are supposed to learn how to edit and compile a newspaper. But politically at our school we are not there yet. And Scribus lacks a lot of things you find i InDesign. We used even a windows program for sound editing when it comes to the radio-journalist part. The year to come we are going to try Audacity. That software has the same kind of limitations compared to Adobe Audition, but that teacher is a bit more open minded. We have tried Ardour also, but that instead is more like a music studio program, not intended for the kind of editing taking place in a radio studio. Its way to complex and the GUI is to scattered when you only want to cut, make pass-overs, add extra channels and normalise. Those things you can do in Audacity, but its not as easy as in Audition. You have to do more things manually with envelopes, and that is a bit old fashion and timewasting. Its also harder to cut and move sound from one channel to another, which is a thing that you do frequently because you often find yourself needing to rearrange parts of the sound file. So, I am not sure we will succeed in replacing even Audition, but we will try. The problem is the students have certain expectations when they start an education towards a profession. So the programs has to look and feel professional. Good thing with radio, there are many programs out there, that radio studios use, so its not as standardised as Newspaper editing. That means, it does not really matter what program they learn, because once they start working they still have to learn the program the studio uses, so instead focus has to be to learn the editing part without to much focus on a specific software. Which free software do you use daily? Myself I'm running Linux Mint, or Ubuntu these days. I use almost only open source software, and preferably Linux based. When it comes to most used applications its OpenOffice, and Firefox (of course ;) ) Which strategy do you believe is the right one to use to get schools to use free software? To get schools to use free software there has to be good open source software that are windows based, to ease the transition. But it's also very important that the multimedia support is working flawlessly. The problems with Youtube, Twitter, Facebook and whatever will create problems when it comes to both teachers and students. Economy are also important for schools, so using thin clients, as long as they have good multimedia support, is a very good idea. It's also important that the open source software works even for the administration. It's hard to convince the teachers to stick with open source, if the principal has to run Windows. It also creates a problem if some classes has to use Windows for there tasks, since that will create a difference in "status" between classes, so a good support for running windows applications via the thin client (Linux) desktop is essential. At least at our school, where we have mixed level of educations, from high-school to journalist-school. Update 2012-07-09 08:30: Paul Wise tipped me on IRC about three useful sources related to Free Software for radio stations: the LWN article Radio station management with Airtime, Airtime which claim to be a Free open source radio automation software and Rivendell which claim to be complete radio broadcast automation solution. All of them seem useful to the aspiring radio producer.

I keep using a Neo Freerunner with Qtmoko in a Debian Squeeze (+ some Wheezy) chroot as my daily phone. It also works well for SMS, GPS, MUA, IM, IRC and some Web browsing with Aurora (using both Wifi and GPRS). Last weekend I managed to play a little with VoIP possibilities in Qtmoko and ended with a functional SIP client in my hands. I want to share some points which may be useful for other brave freerunners:

• Qtmoko has a native VoIP client but it seems to be broken. Its sipagent uses port 5060. I couldn't find a way to disable it at qpe startup, so I had to setup my client to use another port.
• Choosing the application: Ekiga takes 93.4MB of additional disk space. Qutecom takes 212MB. Too much for a 256MB rootfs. Twinkle is ok on this point, it uses about 40MB of additional space, but it fails in the capture (mic) quality. I've tried many setups in my voip-handset state file with no success. Perhaps it's something related to the codecs and/or default parameters. I didn't go deeper on this and gave Linphone a try. This package also uses about 40MB of additional space and finally made my day.
• Linphone gui is called by linphone-3, which has a character not supported by /opt/qtmoko/etc/qx/profiles.conf and /opt/qtmoko/etc/qx/favourites.conf. So if you want to have some setup here you need to create a link/wrapper/whatever without this dash.
• You can edit your preferences directly in your ~/.linphonerc . Remember to change the sip_port entry to any other than 5060.
• I use a basic VoIP service from diamondcard.us. It's cheap and works properly. This company gives financial support to Ekiga and Twinkle projects.
• I was not able to have default Freerunner headset working on an acceptable quality. Help will be very welcome.
• Here is my current config:
• /opt/qtmoko/etc/qx/profiles.conf
• /opt/qtmoko/etc/qx/favourites.conf
• .linphonerc
• /usr/share/openmoko/scenarios/voip-handset.state (please share your improvements!)

UPDATE: I didn't make clear that I get a very nice audio quality using internal mic/speaker with the above voip-handset state file. The issue is only when using the headset, which demands understanding and setting up a proper state file. Enjoy some shots:

The challenge is now more and more to find good places to run without too much cars and noises....and not too far away. Today, I think I made it well..:-) After a look on the map, and some wild guess from what I now know of the way the city is organized, I decided to go south-west of Managa, from the hotel Seminole. This is again a hilly run because, anyway, wherever you go south in Managua, you're going up. Ralf, who arrived just yesterday, joined me and, I guess, enjoyed the run. After going through an obviously quite rich neighbourhood with nice villas, gardeners, huge US truck-style cars, we went close to the Mormonschurch...and a mosque, then headed westward close to "Colegio Americano", with fences, walls, guards in the corner, etc. Seems that any tiny bit of USA in the world needs an army to protect it. Crossing la Pista Suburbana, we then went on a very quiet roads towards the hill, in a very green and peaceful area. House there were really not as fancy as in other places, even seeming quite "poor" in some way. However, we never felt any problem and people we meet on the way are always friendly and smiling : "Hola", "Buenos Dias", etc. At the end of the road, after about half an hour, we decided to head back. However, as going back the same way is boring, I suggested we head up west as my phone's map (it is very helpful to have a smartphone with GPS and Google Maps for wandering through unknwon places) was mentioning another road going north-west a little bit westward. So we entered a small trail between house farms...with dogs! These were a bit "scary" as they were barking at us and of course running entirely freely. On the other hand, none was really aggressive and we had no problem. I however saw a few people really staring at us as I guess there are not so many runners in this place..:-). But still, we never felt unsafe: just in a quite uncommon place. After abotu 500m we found the "road" that was on my map: indeed a path going down slowly along the hill. And there was the marvel. An incredible panoramic view going going the volcanoes that are East and North of Leon : San Cristobal, Telica Rota, Pilas elHoj and last but definitely not least: EL MOMOTOMBO. A nearly perfect pyramid-style volcano that lies about 50km north-west of Managua, on the eastern shore of Managua Lake. The view there is...just fantastic with also a 180 panorama to West and North-West of the lake and the volcanoes area. After this, all we had to do was heading back to the hotel and share this with you...:-) As usual, the full GPS trace is here.

Forward Error Correction with the TI CC1120 Sub-GHz transceiver We re building a new, fancier flight computer and decided to give the new, fancier TI CC1120 chip a try. It has significantly more transmit power (+16dBm) and receive sensitivity (-109dBm) than the transciever built in to the TI CC1111 RF SoC that we ve built our other boards with. Given that we d already decided to use a fancier STM32L processor, using the nicest stand-alone radio chip we could find seemed to make good sense. One of the nice features found in the CC1111 is support for FEC using a 1/2 rate constraint length 4 convolutional code. Both the encoder and the soft-decision Viterbi decoder are built right into the chip; all we had to do was flip a couple of bits and we got error correction, interleaving, data whitening and CRC checking all for free. We assumed that, as the CC1120 was advertised as a better replacement for our CC1111 radio, that it would also include all of these fine features. After we got the chip all soldered down to our first prototype boards, we read through the reference manual looking for the right register values to flip for forward error correction. We found support for CRC computation and data whitening, but no mention of interleaving or forward error correction at all. Thanks, TI. Of course, without the FEC pieces, the other packet handling hardware is worthless you can t exactly do a CRC on the encoded data and expect it to be useful on the other end of the link, and data whitening happens after the CRC. Basic CC1120 driver I assumed I d eventually figure out something to do about the FEC pieces and started writing a basic CC1120 driver AltOS, the operating system used in all of our projects. I started with the transmit side, as that seemed easier as I could use the existing packet hardware by uploading the desired bit sequence using whatever fancy encoding desired and the hardware would happily transmit it. I first tested that using low data-rate bits (2kbps), transmitting an alternating sequence of zeros and ones to generate a 1kHz tone on a regular 70cm receiver. That seemed to work just fine, demonstrating that I had some grasp of the basic operation of the chip. Convolutional Encoding in Software Not to be daunted by a small challenge in software, I set out to replicate the encoding scheme used in the CC1111 chips for use in our CC1120-based design. We obviously want our CC1120 boards to interoperate with the CC1111 boards. Fortunately, TI fully documents the CRC, data whitening, convolutional encoding and interleaving done in the hardware. I created my own implementation of the encoder (licensed, as usual, under the GPLv2) which you can see in the file ao_fec_tx.c It s not quite as flexible as the hardware, it always whitens the data and always appends the CRC bytes to the end of the packet, along with the necessary trellis termination bytes. The core of that code is surprisingly simple:

static const uint8_t ao_fec_encode_table[16] =  
/* next 0  1      state */
    0, 3,   /* 000 */
    1, 2,   /* 001 */
    3, 0,   /* 010 */
    2, 1,   /* 011 */
    3, 0,   /* 100 */
    2, 1,   /* 101 */
    0, 3,   /* 110 */
    1, 2    /* 111 */
 ;
uint8_t
ao_fec_encode(const uint8_t *in, uint8_t len, uint8_t *out)
 
    uint8_t     extra[AO_FEC_PREPARE_EXTRA];
    uint8_t     extra_len;
    uint32_t    encode, interleave;
    uint8_t     pair, byte, bit;
    uint16_t    fec = 0;
    const uint8_t   *whiten = ao_fec_whiten_table;
    extra_len = ao_fec_prepare(in, len, extra);
    for (pair = 0; pair < len + extra_len; pair += 2)  
        encode = 0;
        for (byte = 0; byte < 2; byte++)  
            if (pair + byte == len)
                in = extra;
            fec  = *in++ ^ *whiten++;
            for (bit = 0; bit < 8; bit++)  
                encode = encode << 2   ao_fec_encode_table[fec >> 7];
                fec = (fec << 1) & 0x7ff;
             
         
        interleave = 0;
        for (bit = 0; bit < 4 * 4; bit++)  
            uint8_t byte_shift = (bit & 0x3) << 3;
            uint8_t bit_shift = (bit & 0xc) >> 1;
            interleave = (interleave << 2)   ((encode >> (byte_shift + bit_shift)) & 0x3);
         
        *out++ = interleave >> 24;
        *out++ = interleave >> 16;
        *out++ = interleave >> 8;
        *out++ = interleave >> 0;
     
    return (len + extra_len) * 2;
 

ao_fec_encode_table takes care of the convolutional piece, ao_fec_whiten_table (not shown) contains the data whitening codes while the little loop at the bottom does the interleaving. I didn t spend a lot of time optimizing this as it seemed to run plenty fast on the 32MHz processor. With the bits all nicely encoded, I passed them to my simple CC1120 driver and let it send them along to our CC1111 receiver. Much to my delight, with only a few bugs fixed, it worked just fine! I d managed to get one direction working, validating the hardware and making it clear that we d at least be able to use the board in flight for telemetry. Getting Soft-decision data out of the CC1120 In packet mode, the CC1120 receiver converts the incoming GFSK stream directly into bits, making its best guess as to whether the detected value was a one or zero. Of course, like any FM modulation, the receiver will be producing intermediate values, especially when the signal is weak or masked by interference. A Viterbi decoder can make good use of this information;these noisy intermediate values are less influential in the final resulting path cost which allows the strong 0/1 values to pull the solution to the right one. Soft decision decoding yields a theoretical 2dB gain over hard decision decoders, and given our desire for maximum packet reception over long distances, it seemed important to make this work. The CC1120 has a way to recover the soft decision values, but only one 8-bit value at a time. It does, however, helpfully provide a GPIO wire which can be programmed to interrupt the CPU when the soft decision data has arrived. So, I hooked up a GPIO line on the processor to the GPIO line on the CC1120 and let it interrupt once per bit time, or 38400 times per second, to read this valuable soft decision data out of the radio part. According to TI support, this is the only way to make this work, and that they generally recommend that developers use the packet mode stuff and throw away this valueable source of data. I was happily surprised to learn that the STM32L can in fact survive this interrupt rate, and by setting interrupt priorities appropriately, I manage to reliably capture an entire packets worth of data without dropping a single bit. I set up a simple packet dumping function to run on the prototype board and captured raw encoded bytes from our CC1111-based flight computer so that I d have some real data to work from. Soft-decision Viterbi Decoding The sample encoding implementation from TI made that piece fairly straightforward. Lacking a similar sample for the decoding piece meant that I d be starting from scratch. And, implementing something that seemed like magic to me when I started. I started by reading a few articles on Viterbi decoding: I found Chip Fleming s tutorial very useful as it included a bunch of worked examples using a convolutional encoders with constraint length (k) of 3 instead of 4; this makes all of the trellis diagrams half the size. I also sent my friend, Phil Karn, a query about this process, and he responded with a bunch of helpful suggestions, while also recommending that I just steal his DSP and FEC library implementation. Of course, I don t like using code that I can t understand, and his code only implements much longer codes than I needed, so I d have to understand it anyways to make it work for me. Phil s code is a marvel, but it s not exactly comprehensible to someone who doesn t even know what a Viterbi decoder is supposed to do. So, with Chip s tutorial on my screen, I wrote a primitive Viterbi decoder. This did only the Viterbi step, and split that into two phases. The first computed the cost for each state in the system for every received pair of symbols received. It also tracked the chain of states through the entire decode process:

    for (state = 0; state < 8; state++)  
        struct ao_soft_sym zero = ao_soft_sym(ao_fec_encode_table[state * 2 + 0]);
        struct ao_soft_sym one = ao_soft_sym(ao_fec_encode_table[state * 2 + 1]);
        uint8_t zero_state = ao_next_state(state, 0);
        uint8_t one_state = ao_next_state(state, 1);
        int zero_cost = ao_cost(s, zero);
        int one_cost = ao_cost(s, one);
        zero_cost += cost[b][state];
        one_cost += cost[b][state];
        if (zero_cost < cost[b+1][zero_state])  
            prev[b+1][zero_state] = state;
            cost[b+1][zero_state] = zero_cost;
         
        if (one_cost < cost[b+1][one_state])  
            prev[b+1][one_state] = state;
            cost[b+1][one_state] = one_cost;
         
     

At the end of the packet, it found the least costly path and walked that from back to front, generating output bits (yes, one bit per element of the bits array):

for (state = 1; state < 8; state++)  
    if (cost[b][state] < c)  
        c = cost[b][state];
        min_state = state;
     
 
for (b = len/2; b > 0; b--)  
    bits[b-1] = min_state & 1;
    min_state = prev[b][min_state];
 

Completely separate from this code were the interleaving and data whitening stages. Keeping those separate allowed them to be tested independently, which made debugging them far easier. None of this code ever ran on the STM32L processor, it was instead run in a test framework on my laptop. I first got this working with data generated by the software convolutional encoder, then I managed to get it to decode the raw packets that I had recorded directly from the receiver it self. This marked a significant milestone in my mind I d managed to replace, in software, the CC1111 FEC encoder and decoder. However, the decoder performance was not fast enough to manage back-to-back packets yet. Having something in hand that worked meant that further development would be directly comparable to something that did work, making optimization much easier. Yet another lesson in making it work, and then making it work fast. Optimizing the Viterbi Decoder The first step was to reduce memory usage within the decoder. While it s best to defer computing the path until the very last bit has been received, it s also true that the chances of a bit affecting old data reduces as the distance between the new and old data increases. With the rule of thumb being a distance of k 6 or k 7, I saved 32 output bits for each state and wrote the oldest of 8 each time the buffer filled up, making a distance of 24 bits between the newest saved data and the current decoding position. That meant a fixed amount of storage was needed for an arbitrarily long packet. I tested a variety of different history sizes from 8 to 56 bits (cooresponding to 16, 32 and 64 bits of saved data for each state). With 100000 random packets generated that had gaussian noise added to each bit, here are the error rates for the different history lengths:

History Length	Total Packets	Correct	Incorrect
8 bits	100000	90520 (90.52%)	9480 (9.48%)
24 bits	100000	93614 (93.61%)	6386 (6.39%)
56 bits	100000	93620 (93.62%)	6380 (6.38%)

The performance of the 8-bit history and 16-bit history versions turned out to be essentially identical (given the 32-bit nature of the STM32L, that shouldn t be too surprising). The performance of the 56-bit version, which manipulated uint64_t data types was sigificantly slower, and given the very modest benefit, deemed not worth it. If we move to a larger constraint length (k > 4), or started using a punctured convolutional encoding, we would want to re-measure this. The next step was to combine the de-interleaving, decoding, de-whitening and CRC computation into a single loop. This would eliminate a pile of data copying and extra memory usage. Nothing fancy here, but it made enough of a difference that I could decode most of the incoming packets now, dropping only about 25% of them. To get to being able to decode every packet, I needed to start decoding the packet while it was being received. Because of interleaving, I had to have 32 bits of data to be able to decode anything, so it was a simple matter of having my per-soft-value interrupt handler start the decoder going after each interleave block of data was received. With this in place, I was able to decode a 76-byte payload (160 transmitted bits) in 14.7 ms, or just about 50% of the time it took to transmit the packet. Unrolling one of the inner decoding loops eliminated a bunch of computation and sped this up even more, decoding packets in 9.5ms. Success at last, a solid 100% of packets received were being decoded, as long as the CPU was otherwise idle. Finally, I went and re-read Phil Karn s code and pondered over how it works. It was opaque until I wrote a message back to Phil asking how it worked and pointing out sections that were confusing. Fortunately, simply phrasing my confusion in words made me understand how the code works. Here s my original code for computing the per-state cost metric:

/* Metric for a zero bit */
uint32_t    bitcost = ((uint32_t) (s0 ^ ao_fec_decode_table[(state<<1)]) +
               (uint32_t) (s1 ^ ao_fec_decode_table[(state<<1)+1]));
 
    /* Total path metric and state for a zero bit */
    uint32_t    cost0 = cost[p][state] + bitcost;
    uint8_t     state0 = ao_next_state(state, 0);
    /* Compare the total path metric against all existing
     * metrics heading into the same new state, choosing
     * the least expensive and killing the others.  Record
     * the new lowest cost and output bit.
     */
    if (cost0 < cost[n][state0])  
        cost[n][state0] = cost0;
        bits[n][state0] = (bits[p][state] << 1)   (state & 1);
     
 
 
    /* Total path metric and state for a one bit.  Because
     * encoding a one is always exactly the opposite of
     * encoding a zero from any state, this cost is
     * 255*2 - bitcost
     */
    uint32_t    cost1 = cost[p][state] + 510 - bitcost;
    uint8_t     state1 = ao_next_state(state, 1);
    if (cost1 < cost[n][state1])  
        cost[n][state1] = cost1;
        bits[n][state1] = (bits[p][state] << 1)   (state & 1);
     
 

Before this loop is run, I have to initialize cost[n] to a large value so that the comparisons will be true for the first case to reach each state. Phil s code, in contrast, doesn t have to initialize cost[n] as we know which two states can reach any possible new state. His code looks like this:

/* Metric for a zero bit */
bitcost = ((uint32_t) (s0 ^ ao_fec_decode_table[(state<<1)]) +
       (uint32_t) (s1 ^ ao_fec_decode_table[(state<<1) 1]));
/* Only state and state+4 reach state<<1 with a zero bit */
/* Cost from state to state<<1 for a zero bit*/
m0 = cost[p][state] + bitcost;
/* Cost from state+4 to state<<1 for a zero bit */
m1 = cost[p][state+4] + (510 - bitcost);
/* Which source state is cheaper? */
bit = m0 > m1;
/* Record the cheaper cost and the add to the path of bits */
cost[n][state<<1] = bit ? m1 : m0;
bits[n][state<<1] = (bits[p][state + (bit<<2)] << 1)   (state&1);
/* State and state+4 reach (state<<1)+1 with a one bit */
/* Cost from state to (state<<1)+1 for a one bit */
m0 -= (bitcost+bitcost-510);
/* Cost from state+4 to (state<<1)+1 for a one bit */
m1 += (bitcost+bitcost-510);
/* Which source state is cheaper? */
bit = m0 > m1;
/* Record cheaper cost and add to the path of bits */
cost[n][(state<<1)+1] = bit ? m1 : m0;
bits[n][(state<<1)+1] = (bits[p][state + (bit<<2)] << 1)   (state&1);

This code does two states at a time, and so while it s slightly longer than the above, it only needs to run half as many times. The resulting code now decodes packets in 5.7ms. The final version of the code can be see in ao_fec_rx.c The whole AltOS operating system, with many drivers and support for CC1111, AVR and STM32L processirs is available, under the GPLv2 from git://git.gag.com/scm/git/fw/altos

I'm here in managua since sunday evening, & by now DebCamp is slowly getting to its end. So here are some of my impressions so far:

• as each year, it's great to have time to work on Debian stuff for longer times undisturbed;
• it helps to have other people around, & be able to ask them something just across the table;
• I'm spending a good chunk of my time with the other guys from the Debian perl Group, both in my "work time" & in my "free time" it's just a pleasure;
• most of my work was on the Open Tasks of the Debian Perl Group preparing our meeting next week, working on bugs, preparing changes to our policy, cleaning up never-uploaded packages in our repos, updating our documentation, doing mass-changes across hundreds of packages, ...;
• hotel, university, food, etc. are all fine & the people are all friendly & helpful;
• yesterday evening we even had "una noche de la poesia" in a nearby bar.

thanks to all organizers & sponsors who make this experience happen!

Yet another Grand Plan today: run in Masaya Volcan National Park. Masaya Volcano is one of the most active volcanoes in Nicaragua. It is located only 20km south-east of Managua, so going there is as easy as renting a taxi. The original plan was to drive to the entrance of the National park (on the road to Masaya city), then run up to the volcan, so from 250m altitude up to about 600m. I therefore rented a taxi with the kind help of Norman, and we agreed to meet up at 08:30 at the hotel, along with No l and Daniel (who was planning to walk up, not running). After discussing here or there, Kurt and Gaudenz joined, both with the intent of running up. Others would also have liked to join, but I wasn't in the mood of organizing a full bus of Debconfers..:-). My plan was to enjoy pyself the hike...not to manage several taxis, etc. We thus packed in Denis blue taxi...a fancy and very visible customized blue car that looked like it had been the topic of on episode of the "Pimp My Ride" TV show..:-) Sitting 4 people at the back of a regular car without hitting some blue neon lights, or 7" TV screens is kinda tricky, but we made it. When arriving at the park's entrance, we however learned that it is forbidden to walk or hike up the road by foot, because of potential high concentrations of Carbon Dioxide. Sadly, we then had to pack again in the car and go up with it. After reaching the parking close to the volcano's active crater (that is said to have a small lava lake at its bottom, one of the very few in the world), we decided to head up for going round the Nindira crater, an inactive crater located slightly above. Unfortunately, again, the path around the Masaya crater is forbidden to walk on, because of landslides. We indeed still had great fun by running around this crater (which is about a 2.5 kilometers round trip, very very hilly and sometimes hard to run on such as a mountain path. After about 50 minutes and two laps (after all, we had a giant stadium!), we headed back to the parking, packed 5 sweating geeks in the car and went back to the hotel. Full GPS trace is here. I also put a few pictures on Facebook, supposedly visible by anybody : Masaya crater and Nindiri crater.

Most x86 devices export various bits of system information via SMBIOS, including the system manufacturer, model and firmware version. This makes it possible for the kernel to alter its behaviour depending on the machine it's running on, usually referred to as "DMI quirking". This is a very attractive approach to handling machine-specific bugs - unfortunately it also means that we often end up working around symptoms with no understanding of the underlying issue.

Almost all x86 hardware is tested with Windows. For the most part vendors don't ship devices that don't work - if you install a stock copy of Windows on a system, you expect it to boot successfully and reboot properly. Basic ACPI functionality should be present and correct, including processor power-saving states. Time should pass at something approximating the real rate. And since stock Windows isn't updated with large numbers of DMI quirk entries, the hardware needs to do this with an operating system that's already shipped.

Which means that if Linux doesn't provide the same level of functionality, it means we're doing something different to Windows. Sometimes this is because we're doing something fundamentally different with the hardware - the HP NX6125, for example, resets its thermal trip points if the timer is set up in a different way to Windows. In this case we've decided that the additional functionality of doing things the Linux way is worth it, and we'll just blacklist the small set of machines that are broken by it.

But other times there's no need for the difference. For years we were triggering system reboots in a different way to Windows and then adding DMI workarounds for any systems that didn't work. The problem with this approach is that it's basically impossible to guarantee that you've found the full set of broken hardware. It's very easy to add another DMI quirk, but it doesn't solve the problem for anyone who bought a machine, tried Linux and gave up when they found reboot didn't work. More recently we've added a pile of quirks for Dells - turns out that in all cases we're working around a bug in their firmware that hangs if we're using VT-d.

We typically don't merge code that fixes a specific example of a problem without at least considering whether there's a wider class of similar problems that could all be solved at once. We should take the same attitude to DMI quirks. Sometimes they're the least harmful way of handling an issue, but most of the time they're just fixing one person's itch and leaving a larger number of people to continue cursing at Linux. There should at least be a demonstration of an attempt to understand the underlying problem before just adding another quirk, and every patch that permits the removal of some DMI checks should be greeted with great cheer.

comments

This seems like a simple question: how do you listen to music? But in a way, I think I ve fallen behind the times. I ve enjoyed listening to digital music for years, since well before MP3 even existed (MIDI files could be comfortably downloaded over dialup; some of you may even remember MOD files). Anyhow, a few years ago, I digitized my entire CD collection, ripping it to FLAC and encoding to high-bitrate MP3 for storage on my 160GB iPod. Since, I ve purchased some music from DRM-free MP3 retailers, and even FLAC files from Magnatune, but at this point I basically say that I have enough music. I have only rarely bought anything new in the last couple of years. I have used Musicbrainz Picard to enforce consistent tagging across almost my entire collection. I am usually in front of a Linux machine. I run mt-daapd on my fileserver, so I can stream music from it to any other machine in the house. However, this has a lot of drawbacks. It is generally impossible to create or modify persistent playlists with this protocol. I can t modify metadata. I can t assign ratings. Though perhaps I don t need to. There are a lot of online services I could think of: Pandora, Spotify, Rdio, Slacker. Plus, of course, the upload your music to the cloud services such as Google and Amazon. Have people tried these? I m hesitant to use a service where I pay a monthly fee, unless I wind up owning the music in a DRM-free fashion. And I m a little nervous about the privacy implications of uploading a vast amount of music to the cloud. There are some items in my collection that I am certain are not available on any of those others, but for the most part I m willing to take what is out there if it meets my tastes. My tastes, by the way, typically run to classical and opera but also can go towards middle eastern or certain new age music (though I m very picky about that, since I don t care for most new age stuff I hear.) But these are huge categories; sometimes I d like to hear some load and noisy classical (say, Beethoven s Ninth conclusion, some Wagner, Verdi arias, etc.) And other times, something more contemplative (a Mozert concerto) or even quiet (a nice sonata) meet my mood. I have playlists for these on my iPod Classic a bit of a problem, since I don t use that device much anymore except in the car, and it takes a LOT of time to categorize things into these playlists. (An opera or a symphony could have parts in various styles and various levels of energy, for instance.) I keep a small manually-managed subset on my Android phone, which works fine. A recommendation engine for things like this could be useful, if it works well. My requirements, basically: I want something that will play the same music on my Linux machines. I want to be able to have playlists kept in sync across my machines. And I don t want a monthly fee. Ideally, the software will work on Android as well, and provide similar features there. Anything that requires Windows is a non-starter. I ve considered NFS mounts, but that s a bit annoying when the laptop disconnects from the network or when it s not at home. What are your thoughts? Ideas?

It's still good to be at Debcamp before DebConf and I'm not running all day long, contrary to what you might think by reading my posts. Of course, I'm always busy with "social-like" activities such as doing my best for us to have a good Cheese and Wine Party as, now that I'm trapped into it, people expect it to be better and better each year. Or to revive the traditional Assassins game. But Debian is not only about killing cheese with socks and I try to also achieve a few things while being here. As of now, I can already count a few things:

• completing dpkg translation and dpkg manpages translations (I blessed Guillem Jover a lot for being so picky and changing so many details in dpkg messages....and I blessed Rapha l a lot for writing so detailed manpages). To be honest, that part was not achieved during Debcamp but during.....the flight from Paris to Atlanta and partly during the Atlanta-Managua flight. Being upgraded to Premium helped as there are power sockets in seats there..:-)
• completing APT translation and APT manpages translations. Here, a big work had been done by Justin Rye to bring more English in a big pile of Germish and I had to fight hard to check significative changes out of the typo and grammar fixes
• preparing a backport of samba for squeeze. We'll have samba 3.6.6 in wheezy and our squeeze users deserve it also
• go through a few leftovers from the Paris i18n sprint that created i18n.debian.org, such as creating a page for the I18n team.
• discuss (briefly) with David Pr votto have the Debian website l10n pages point to material from i18n.debian.org and no longeri18n.debian.net

The only thing I nearly haven't worked on yet is....the talk I have on Sunday and that is supposed to explain newcomers how to join the crowd of localization fanatics. Oh, and I'm still jetlagged and go to bed daily at 10pm...:-)

Yay, got to Nicaragua OK last night. It's the first time I've managed to get to DebCamp in quite a while, and I'm making the most of it. I've got slides ready for two of my BoF sessions next week (both ARM-related), and I'm preparing for the other four now. Why did I sign up to run six sessions? Maybe because I'm a bit silly, or maybe because they needed doing and other people hadn't registered them. Maybe both. :-) BTW: these are all BoF (Birds of a Feather) sessions, not lectures. While I have an interest in each topic, I'm neither wanting nor expecting to just talk at a room full of people - I'm wanting to provoke discussions in each case. If you're interested, please join in those discussions, either physically in Managua or virtually using the live video streaming and IRC back-channels:

• ARM port(s) update
• AArch64 planning
• EFI in Debian
• Debian-CD
• Hijacking packages for fun and profit
• wiki.debian.org

See you there...!

Many community driven projects have a problem with overgrown bureaucratic processes reducing the desire and ability of casual contributors to contribute. Debian has struggled with this problem, with efforts like Debian Maintainers and sponsorship to address it, but it's insidious and difficult to completely overcome. I recently ran into this problem again with Wikipedia, where I'm a casual contributor (I probably average an edit a month). Sometime in 2006, I uploaded an image of a Boojum tree I took in 2004 to Wikipedia to provide an image for the Boojum tree article. It wasn't a particularly awe inspiring image, as I took it while I was teaching second quarter freshmen biology on campus, and showing the students the awesome Botanical Gardens at UCR. In 2011, a Wikipedia user asked for deletion of the image because of some confusion about the copyright on the image, as Apache::Gallery's default template footer contains Apache::Gallery's copyright. I didn't notice that during the 7 day deletion review period because I rarely log into Wikipedia. A few days ago, I noticed the deletion and asked for a Deletion Review. I assumed that my explanation that the copyright notice was for Apache::Gallery would be understood (or at least believed), and that at least the original reason for the deletion would be seen to be invalid. Instead, during the process I was questioned as to whether I actually took the picture, why I used GPLv2+ for the pictures, whether I was claiming other people's images, and whether the image was actually good enough to be in Wikipedia in the first place. Hundreds of lines of text, an edit to the template in A::G, hours wasted, people still unsatisfied, and the potential contributor (myself) feeling so annoyed with the entire process that I bothered to write this blog entry. While I'm not sure what to do about Wikipedia, I've been forcibly reminded of how important enabling easy contributions are, and how alienated one can feel when one is stymied by them to the point that your (admittedly insignificant) contribution to a project no longer seems worth the effort.

The Grand Plan today was reaching the end of the road I already explored on Tuesday. Named "Camino Las Viudas", it's climbing in the southern hills up to a place named "Intermzeeo del Bosque", apparently a very fancy (and expensive) restaurant. The road climbs in the apparently "rich" neighbourhood of Managua, with very fancy villas as guarded by private security, as well as private condominiums, guarded as well. What's funny to see is that, at the bottom of the road, when it crosses a large avenue (Pista Suburbana Espana), you can find several auto-rickshaws, just like those you find everywhere in India. Those autos apparently drive people who happen to work in these villas (like maids, gardeners, security guards, etc.) up to the place they work. We even met two cows wandering on the road and I hesitated waiting for a rickshaw to show up and take a pic of the road (with holes), the auto and the cows, then pretending that I'm no longer in Nicaragua but back in Karnataka. I did the run along with No l K the, who I was very happy to find again, restoring our now famous Debconf Runners Duet. We even found the German Embassy! Though climb, even if we took care to start at 6 a.m. to avoid the heat (and also the traffic and noise). No l unfortunately had to give up at 1km from the top of the road, when a 15% climb suddenly "killed" his legs. I need to train him more for ups and downs..:-) I could continue the road and finally reached the restaurant....which was guarded by private security (as apparently everything in this country) who unfortunately didn't let me in despite my desperate attempts to convince him, in broken Spanish, that I just wanted to take a few pictures and not place a bomb or rob someone... So, I gota little bit disappointed and the only option was then....to run down for another 8.5 kilometers, accelerating all the way, to finish nearly at 14 km/h on Managua's sidewalks...Fun. Great run (nearly 400m positive slope in less than 17km). Next challenge : find another such nice run in the neighbourhood! Maybe Volcan Masaya tomorrow. GPS trace is here.

Second day in managua, second day running. Today, after breakfast, so at about 7h45, I went out running with Gaudenz Steinlin. The goal was to go to laguna de Tiscapa, a lagoon of volcanic origin, in the middle of the city of Managua. The laguna is not really far away from the place we're staying at (about 2.5km). However, as usual here, the only way to get there is along the streets. Noisy streets. Often smelly streets. But that's the only way. For instance, it took Gaudenz several minutes before he could manage to cross the "Pista Beljamin Zelodon", a quite busy highway. The lagoon per se is really nice, particularly the view from the Sandino monument where you can see the Peninsula de Chiltepe. However, apart from that, it was sometimes a quite boring run because of the traffic, noise, etc. But I enjoyed again having a good run with Gaudenz. We'll do this again, but in another place..:-) GPS trace for that run is here.

For my GSoC project this year I need to be able to enumerate all elementary circuits of a directed graph. My code is written in Ocaml but neither the ocamlgraph library nor graph libraries for other languages seem to implement a well tested algorithm for this task. In lack of such a well tested solution to the problem, I decided to implement a couple of different algorithms. Since it is unlikely that different algorithms yield the same wrong result, I can be certain enough that each individual algorithm is working correctly in case they all agree on a single solution. As a result I wrote a testsuite, containing an unholy mixture of Python, Ocaml, D and Java code which implements algorithms by D. B. Johnson, R. Tarjan, K. A. Hawick and H. A. James.

Algorithm by R. Tarjan The earliest algorithm that I included was published by R. Tarjan in 1973.

Enumeration of the elementary circuits of a directed graph
R. Tarjan, SIAM Journal on Computing, 2 (1973), pp. 211-216
http://dx.doi.org/10.1137/0202017

I implemented the pseudocode given in the paper using Python. The git repository can be found here: https://github.com/josch/cycles_tarjan

Algorithm by D. B. Johnson The algorithm by D. B. Johnson from 1975 improves on Tarjan's algorithm by its complexity.

Finding all the elementary circuits of a directed graph.
D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
http://dx.doi.org/10.1137/0204007

In the worst case, Tarjan's algorithm has a time complexity of O(n e(c+1)) whereas Johnson's algorithm supposedly manages to stay in O((n+e)(c+1)) where n is the number of vertices, e is the number of edges and c is the number of cycles in the graph. I found two implementations of Johnson's algorithm. One was done by Frank Meyer and can be downloaded as a zip archive. The other was done by Pietro Abate and the code can be found in a blog entry which also points to a git repository. The implementation by Frank Meyer seemed to work flawlessly. I only had to add code so that a graph could be given via commandline. The git repository of my additions can be found here: https://github.com/josch/cycles_johnson_meyer Pietro Abate implemented an iterative and a functional version of Johnson's algorithm. It turned out that both yielded incorrect results as some cycles were missing from the output. A fixed version can be found in this git repository: https://github.com/josch/cycles_johnson_abate

Algorithm by K. A. Hawick and H. A. James The algorithm by K. A. Hawick and H. A. James from 2008 improves further on Johnson's algorithm and does away with its limitations.

Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs.
Hawick and H.A. James, In Proceedings of FCS. 2008, 14-20
www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf

In contrast to Johnson's algorithm, the algorithm by K. A. Hawick and H. A. James is able to handle graphs containing edges that start and end at the same vertex as well as multiple edges connecting the same two vertices. I do not need this functionality but add the code as additional verification. The paper posts extensive code snippets written in the D programming language. A full, working version with all pieces connected together can be found here: https://github.com/josch/cycles_hawick_james The algorithm was verified using example output given in the paper. The project README states how to reproduce it.

Input format All four codebases have been modified to produce executables that take the same commandline arguments which describes the graphs to investigate. The first argument is the number of vertices of the graph. Subsequent arguments are ordered pairs of comma separated vertices that make up the directed edges of the graph. Lets look at the following graph as an example: The DOT source for this graph is:

digraph G  
  0;
  1;
  2;
  0 -> 1;
  0 -> 2;
  1 -> 0;
  2 -> 0;
  2 -> 1;
   

To generate the list of elementary circuits using Tarjan's algorithm for the graph above, use:

$ python cycles.py 3 0,1 0,2 1,0 2,0 2,1
0 1
0 2
0 2 1

The commandline arguments are the exact same for the other three methods and yield the same result in the same order. If the DOT graph is in a format as simple as above, the following sed construct can be used to generate the commandline argument that represents the graph:

$ echo  sed -n -e '/^\s*[0-9]\+;$/p' graph.dot   wc -l   sed -n -e 's/^\s*\([0-9]\) -> \([0-9]\);$/\1,\2/p' graph.dot 

Testsuite As all four codebases take the same input format and have the same output format, it is now trivial to write a testsuite that compares the individual output of each algorithm for the same input and checks for differences. The code of the testsuite is available via this git repository: https://github.com/josch/cycle_test The other four repositories exist as submodules of the testsuite repository.

$ git clone git://github.com/josch/cycle_test.git
$ cd cycle_test
$ git submodule update --init

A testrun is done via calling:

$ ./test.sh 11

The argument to the shell script is an integer denoting the maximum number N of vertices for which graphs will be generated. The script will compile the Ocaml, Java and D sourcecode of the submodules as well as an ocaml script called rand_graph.ml which generates random graphs from v = 1..N vertices where N is given as a commandline argument. For each number of vertices n, e = 1..M number of edges are chosen where M is maximum number of edges given the number of vertices. For every combination of number of vertices v and number of edges e, a graph is randomly generated using Pack.Digraph.Rand.graph from the ocamlgraph library. Each of those generated graphs is checked for cycles and written to a file graph-v-e.dot if the graph contains a cycle. test.sh then loops over all generated dot files. It uses the above sed expression to convert each dot file to a commandline argument for each of the algorithms. The outputs of each algorithm are then compared with each other and only if they do not differ, does the loop continue. Otherwise the script returns with an exit code. The tested algorithms are the Python implementation of Tarjan's algorithm, the iterative and functional Ocaml implementation as well as the Java implementation of Johnson's algorithm and the D implementation of the algorithm by Hawick and James.

Future developments Running the testsuite with a maximum of 12 vertices takes about 33 minutes on a 2.53GHz Core2Duo and produces graphs with as much as 1.1 million cycles. It seems that all five implementations agree on the output for all 504 generated graphs that were used as input. If there should be another implementation of an algorithm that enumerates all elementary circuits of a directed graph, I would like to add it. There are some more papers that I would like to read but I lack access to epubs.siam.org and ieeexplore.ieee.org and would have to buy them. Benchmarks seem a bit pointless as not only the algorithms are very different from each other (and there are many ways to tweak each of them) but also the programming languages differ. Though for the curious kind, it follows the time each algorithm takes to enumerate all cycles for all generated graphs up to 11 vertices.

algorithm	time (s)
Johnson, Abate, Ocaml, iterative	137
Johnson, Abate, Ocaml, functional	139
Tarjan, Python	153
Hawick, D	175
Johnson, Meyer, Java	357

The iterative Ocaml code performs as well as the functional one. In practice, the iterative code should probably be preferred as the functional code is not tail recursive. On the other hand it is also unlikely that cycles ever grow big enough to make a difference in the used stack space. The Python implementation executes surprisingly fast, given that Tarjan's algorithm is supposedly inferior to Johnson's and given that Python is interpreted but the Python implementation is also the most simple one with the least amount of required datastructures. The D code potentially suffers from the bigger datastructures and other bookkeeping that is required to support multi and self arcs. The java code implements a whole graph library which might explain some of its slowness.

Update on computational chemistry packages in Debian

For many years, me and the Debichem team maintained two computational chemistry packages, first MPQC and later PSI3. In recent years however, two respected quantum chemistry codes have been open sourced and are now available in Debian: ACESIII and NWChem. Make no mistake, those are not recently started codes or some Ph.D.'s pet-project but state-of-the-art projects targeted at massively parallel supercomputers and developed at the University of Florida's Quantum Chemistry Project (QTP) in the case of ACESIII and at Pacific Northwest National Laboratory (PNNL) for NWChem.

While ACESIII has a somewhat narrow focus on Coupled-Cluster (unfortunately, the current version does not yet implement analytic gradients for the "golden standard" CCSD(T) method) and Multi-Body Perturbation Theory methods, NWChem is a very versatile package supporting a variety of molecular quantum chemistry methods (including Density Functional Theory (DFT)), as well as periodic plane-wave electronic structure and (ab-initio and classical) molecular dynamics. At this point, NWChem probably covers 90% of all use cases for routine computational chemistry compared to the popular non-free codes Gaussian and GAMESS, while likely exhibiting superior parallel scaling at least compared to Gaussian.

Over the last year, I have packaged and integrated NWChem and ACESIII for Debian, and they are now both in testing. Furthermore, I have recently overhauled the packaging of MPQC and enabled parallel execution via MPI. Further, both MPQC and PSI will see updated versions (MPQC3 and PSI4) in the near future with significant increased functionality, including some unique (at least among open source codes) features like Symmetry-Adapted Perturbation Theory (SAPT) for PSI4 and general explicitly correlated corrections ([2]_f12) for MPQC3. Unfortunately, they both did not get released in time for the wheezy freeze.

On the periodic/plane-wave front, I have also packaged and uploaded Quantum ESPRESSO (formerly PwSCF), a set of plane-wave programs, and I have been working with lafur Jens Sigur sson to get the latest Abinit release packaged. The nanoscale-physics team is also targeting further periodic ab-initio packages like BigDFT and Octopus, but those as well did not land in time for the freeze.

Finally, I also packaged and uploaded CP2K, a well-engineered and versatile periodic plane-wave/pseudo-potential code which focuses on state-of-the-art ab-initio Molecular Dynamics (AIMD) using Density Functional Theory. Some of the authors have recently published a paper reporting linear scaling benchmark calculations on a system with a million atoms using almost 50,000 CPU cores.

All of the above mentioned packages are included either in the molecular ab-initio or the periodic ab-initio Debichem tasks.