Checksums (part I)

I once worked in a company specializing in embedded electronics for industrial applications. In one particular project, the device communicated through a RS-422 cable to the computer and seemed to return weird data once in a while, causing unwanted behavior in the control computer whose programming did not provide for this unexpected data. So I took upon myself to test the communication channel as it seemed that the on-board software was operating properly and did not contain serious bugs. I added a check-sum to the data packet and it turned out that some packets came in indeed corrupted despite the supposedly superior electrical characteristics of the RS-422 link.

After a few days’ work, I implemented the communication protocol that could detect and repair certain errors while reverting to a request to retransmit if the data was too damaged. I then started gathering statistics on error rate, number of retransmit, etc, and the spurious behavior on the controller’s side went away. My (metaphorically) pointy-haired boss opposed the modification because “we didn’t have any of these damn transmission errors until you put your fancy code in there“. Of course, this was an epic facepalm moment. I tried to explain that the errors have always been there, except that now they’re caught and repaired. Needless to say, it ended badly.

Notwithstanding this absurd episode, I kept using check-sum to validate data whenever no other layer of the protocol took care of transmission errors. So, this week, let us discuss check-sums and other error detection algorithms.

Linux Symposium 2009: Finalization

The Linux Symposium ended on Friday (yesterday, that is) and I now post our paper. I’ve added it to my publication page but you can get the pdf of the paper as well as the slides in Open Office 3.0 format. The slides are really nothing fancy, but they’re to the point, I think.

I suppose the complete proceedings will appear sometimes soon on the Symposium’s Archive page. I think some of the links are broken.

*
* *

The Symposium is really not what I expected, and it’s all for the better. I thought I would get more “OpenSource or Die!!!1!” talks, but most of the talks were down-to-earth in a very sane way; some were technically deep, other left the real goodies out, but all were interesting in their own way—not all topics interested me, of course. I think I will also attend next year.

Linux Symposium 2009: Day 4

I wanted to attend to Load Balancing Using Free Software, by Mathieu Trudel, a special, last-minute added talk, but I couldn’t. Unfortunately his paper did not make it into the proceedings, so I’ll have to ask him if he got one or not.

I also got the proceedings and I must say that I am generally pleased with the breadth of subjects as well as the quality of the papers. Makes for good reading. It took me about an hour to read the abstracts and skim over to decide which I will be reading in depth.

*
* *

While we were discussing the symposium over coffee this morning, my friend Christopher ended up calling it the Linux synopsium for some reason known only to himself.

Linux Symposium 2009: Day 3

Did not attend yesterday (Day 2) either. However, this morning François-Denis delivered a most cromulent speech despite being quite nervous. There was a couple of very interesting talks, like the current state of kernel development, but I must say that the talk about GStreamer ported to the DaVinci DSP series was a bit disappointing as all the tasty technical details of using SIMD on the DSP for video processing were left out as proprietary—so much for Open Source!

Another thing that quite surprised me is that they had no coffee! How can hackers do anything without coffee? But to do justice to the organisators, they have been otherwise very concerned with their guests’ comfort: wireless access was very good, there were water pitchers in every room, and they were quite quick to intervene should some technical difficulty arise.

Linux Symposium 2009: Day 1

Today opened in Montréal the Linux Symposium 2009. Not much excitement so far as today was a day filled with tutorials and unfortunately I could not attend. Still got my OLS’09 burgundy T-shirt, though. I am also quite looking forward to wednesday morning where my co-author and good friend François-Denis (blog) will be presenting our paper on non-privileged user package management. I’ll be putting the paper on my publication page (with the presentation’s slides) sometime next week.

Powers of Ten (so to speak)

I am not sure if you are old enough to remember the 1977 IBM movie Powers of Ten (trippy version, without narration) [also at the IMDB and wikipedia], but that’s a movie that sure put things in perspective. Thinking in terms of powers of ten helps me sort things out when I am considering a design problem. Thinking of the scale of a problem in terms of physical scale is a good way to assess its true importance for a project. Sometimes the problem is the one to solve, sometimes, it is not. It’s not because a problem is fun, enticing, or challenging, that it has to be solved optimally right away because, in the correct context, considering its true scale, it may not be as important as first thought.

Maybe comparing problems’ scales to powers of ten in the physical realm helps understanding where to put your efforts. So here are the different scales and what I think they should contain:

Sorting Lists (part II)

Last week I showed you the radix sort on simple linked lists. This week, I will present a version of QuickSort modified to sort simply linked lists.

Recycling Random Bits

It is not uncommon that for large-scale simulations you need a large volume of high-quality (pseudo)random numbers. The relatively short period of the C standard library’s rand function may make it impractical for your purpose; and you might need to resort to stronger generators such as the Linux-provided /dev/random and /dev/urandom pseudo-devices. But calling those is a relatively expensive process as /dev/random may stall until its “entropy pool” is repleted.

The /dev/urandom is the unblocked version of /dev/random, but it is also demonstrably less random. Moreover, one has to access either pseudo-devices through the file system, which in certain case introduces a noticeable impact on performance. Using other sources of randomness such as a hardware random number generator may also incur significant delays.

To avoid being stalled, I propose a simple method that will allow you to recycle bits from an expensive pseudo-random source without polling it too often.

Safer Integer Types (part III)

A few days ago (again at the time of writing, but since I accumulate and schedule posts for a weekly release, that may already mean a few months ago) a friend was a bit nonplussed by the fact that an expression such as:

int x;
unsigned int y;

if (x+y<0)
 {
  ...
 }

was simply never true. At first, you’re thinking “how can this be?” because you’re trying to find values of x and y that, summed together, are obviously negative. That is, without counting on the surprising integer promotion/integral conversion system of C and C++.

Let us see what’s going on exactly.

Cutting Corners

Cutting corners is generally thought of as a bad thing. It generally is, I agree. But in some occasions, optimally cutting corners is the right thing to do. I can show you what I mean. Using the Logo programming language (precisely the KTurtle implementation), I devised the following experiment. Consider the following image:

Two circles drawn with KTurtle