An XML Compression Scheme

There are different ways of compressing XML but I like the idea of doing it with a schema. Using a schema you always have the advantage of validation but you can also produce very efficient encoding of the XML data. I have been working on an XML layer for packedobjects to allow compression of XML data. Currently it takes XML data with a schema written in packedobjects and produces binary data. This is very similar to XER but everything happens at runtime. This means I could support a subset of XML Schema and dynamically map to the packedobjects schema. Doing this the end user will only see an XML world.  Everything is handled by embedding Scheme to take care of the mapping between XML and s-expressions. From C you will not see this but you still have the advantage of working directly within a REPL to design your schema if you want. The Scheme layer could also be extended to handle other data formats.

Running the example will show that the packedobjects compression is about 3 times smaller than gzip based compression. In similar tests I have seen similar gains over encoding with Protocol Buffers.

TCR update

Building The Clashing Rocks prototype was fun. It really identified some brick wall challenges surrounding the quantity of data we had to process in real-time. Even encoding to bit-level was not going to cut it. As a result a new direction for the project will be to focus solely on recording the seismic events. This will provide more opportunity to implement techniques to work with the bandwidth constraints in place and will eliminate the hard real-time processing constraints. There will still be the challenge of synchronising, logging and presenting the data but we will focus more on providing high-level APIs and/or a DSL to help realise this. The project will still be OpenWrt based and run on different architectures.

The Clashing Rocks

This project is about using embedded Linux devices to detect, record and react to seismic events. The idea is to use accelerometers to detect shaking and then communicate this event to all other devices connected to the same broadcast group. We are developing the technology using OpenWrt which allows us to use a range of hardware including routers and pocket computing devices. We really like the idea of exploring emerging low-powered, low-bandwidth mesh networks in developing countries. In this video you can see some early work using a network of Ben NanoNote computers fitted with WPAN hardware. Three devices are connected to a Spread daemon running on a co-ordinating device. Because our current hardware lacks accelerometers we run a program on one device to send fake accelerometer data onto the network. Each device should then pick up this data across our wireless network. We are currently able to get some basic support for IP networking using a hack by Werner Almesberger who also developed the WPAN hardware.  In the video you can see the devices display a bar graph indicating it received data. Only one bar is registered as only one device is transmitting. This bar graph could act as a finger print for deciding the scale of seismic activity in a larger network. We intend to add some more intelligence to this part by building a some kind of knowledge system. Currently the project is at a very early stage with some basic infrastructure developed in C. The aim is to extend this infrastructure by embedding GNU Guile. This will allow us to dynamically control how we communicate, store and process the structured data shared amongst devices. Part of this system will involve trying to minimise the quantity of structured data exchanged on the network by serialising to bit-level using Packedobjects.

Further details of the project can be found at The Clashing Rocks wiki.

Searchable USB flash drives

Recently I was revisiting a powerful open source search engine technology on a Ben NanoNote to see how well it performed. Bearing in mind the NanoNote is only equipped with 32MB of RAM and a 336MHz MIPS processor it performed admirably. As a proof of concept I took the PDF lecture slides from three MIT OpenCoureWare undergraduate modules and indexed them on the device. This part of the process is time consuming but only needs to take place once. As you can see from the following video (OGG format), searching the PDFs is rapid and there should be no problem scaling to thousands of documents.

One nice feature of connecting the NanoNote to your PC is that you are able to access the search engine through your PC’s web browser. This becomes close to something I have thought about for a while – a copyleft designed USB flash drive with embedded web server and search engine. This would allow you to take your documents with you and view them using a familiar g**gle style search on any PC you get access to (in theory) without relying on the host OS to do the work.

btlogger updated to support OAuth

Twitter pulling the plug on basic authentication meant I had to make changes to btlogger to support OAuth. Fortunately, librest made the code changes trivial. However, I ran into some problems. The clock was out of sync on the PC where btlogger runs. This caused the authenticate process to fail at the token request stage and was not easy to debug. The other issue which has been heavily documented is how to support authentication keys in FOSS. Currently configure.ac requires an edit to supply the key information. In theory I could supply the keys to somebody who wants to build the software from source until I figure out another way to handle this. I think they call this “best effort security”.

btlogger is now running from its own twitter account at: http://twitter.com/bluetoothlogger

SlowFi protocols on copyleft hardware

Recently I have been working on Packedobjects which included redesigning the API and replacing a lot of C code in Scheme. I will try and formalize the whole encoding process which I have called Integer Encoding Rules. I also began work on a manual which includes some examples. My aim is to support the tool on OpenWrt which also involves maintaining the GNU Guile build.

I built and tested the software on my Ben Nanonote. The ipk is available: http://zedstar.org/ipk/packedobjects_0.4_xburst.ipk

After improving the documentation I intend to use the tool in a networking course at work. I think it is important for students to gain some experience of designing and structuring binary network protocols.  We will be getting a bunch of Nanonotes to compliment the Openmoko Freerunners we have. This will provide some nice hands on experience packing some data and communicating it across different kinds of hardware.

Long term, I am interested in designing some funky SlowFi protocols on copyleft hardware.

GNU Guile on a Ben NanoNote with command line history (readline support)

I have been hacking at the OpenWrt Makefile and now have command line history working within the REPL.

opkg install http://zedstar.org/guile/libgmp_4.3.1-2_xburst.ipk
opkg install http://zedstar.org/guile/libltdl_1.5.26-1_xburst.ipk
opkg install http://zedstar.org/guile/guile_1.8.7_xburst.ipk

Once installed setup a .guile file:

root@BenNanoNote:~# cat /root/.guile
(use-modules (ice-9 readline))
(activate-readline)

When you run guile now you should be able to use the up and down cursor keys to go through your command history etc.

A minimal OpenWrt image for the Openmoko Freerunner containing GNU Guile

To experiment some more with OpenWrt I dusted out a Freerunner and built a minimal image containing GNU Guile. The image is built with glibc and an IP 192.168.254.101 to match my Nanonote settings.

** UPDATE: GNU Guile now has readline support and root image now contains GLib **

Flash the following:

http://zedstar.org/freerunner/openwrt-s3c24xx-2.6-uImage

http://zedstar.org/freerunner/openwrt-s3c24xx-root.jffs2-128k

Boot the device then:
john@thinkpad:~$ telnet 192.168.254.101
Trying 192.168.254.101…
Connected to 192.168.254.101.
Escape character is ‘^]’.

=== IMPORTANT ============================
Use ‘passwd’ to set your login password
this will disable telnet and enable SSH
——————————————

BusyBox v1.16.1 (2010-05-02 14:45:14 BST) built-in shell (ash)
Enter ‘help’ for a list of built-in commands.

_______ ________ __
| |.—–.—–.—–.| | | |.—-.| |_
| – || _ | -__| || | | || _|| _|
|_______|| __|_____|__|__||________||__| |____|
|__| W I R E L E S S F R E E D O M
KAMIKAZE (bleeding edge, r21293) ——————
* 10 oz Vodka Shake well with ice and strain
* 10 oz Triple sec mixture into 10 shot glasses.
* 10 oz lime juice Salute!
—————————————————
root@OpenWrt:/# uname -a
Linux OpenWrt 2.6.30.10 #1 PREEMPT Sun May 2 14:59:31 BST 2010 armv4tl GNU/Linux
root@OpenWrt:/# guile
guile> (string-tokenize “hello world”)
(“hello” “world”)
guile>

A dynamic data encoder for embedded systems

I personally view Scheme as a good extension language. Something that can be embedded into C code to ease the pain of doing everything in C. I am interested in exploiting this concept on embedded systems where there is a lot of fooling about to make a binary. I still intend to produce binaries and reuse the large amount of existing C code out there. However, I want to script the network communication and in particular the structure of the network packets. I have periodically been working on a tool that attempts to support this. This summer I intend to get rid of the old C code in this project and rewrite it entirely in Scheme apart from the low-level encoder/decoder which will remain in C. In this white paper I attempt to describe the work.

**update**

This white paper has now be superseded by the paper “Everything counts in small amounts“.

Guile on a Ben NanoNote

Received a Ben NanoNote today. It is a really natty little device with a lot of potential.

My standard test on how hackable a device is involves getting Guile running. Anyway, it was pretty easy to accomplish this despite not using openWrt before.


root@BenNanoNote:~#
root@BenNanoNote:~# guile
guile> (map (lambda (x) (+ x 1)) '(1 2 3 4 5))
(2 3 4 5 6)
guile>


To install get the 3 xburst packages from here.

Happy Scheming!