Live Video Color Gamut

The other day—well, a year ago or so—I was invited to visit CBC’s digital TV studios in Montréal by the SMPTE Montréal. We were shown around, even in the somewhat small control rooms. Amongst all the displays, dials, monitors, and misc. blinkenlights, I noticed a small LCD display showing an hexagonal projection of the current show’s color gamut in (or maybe ?), probably for quality assessment purposes. I thought it was pretty cool, actually.

Let’s see how we can realize this projection with as little CPU time as possible.

#defines are EVIL

The C (and C++) preprocessor is a powerful but dangerous tool. For sure, it helps with a number of problems, from conditional code inclusion to explicit code generation, but it has a few problems. In fact, more than a few. It is evil.

The C preprocessor (hereafter CPP) should be used with extreme care. For one thing, the CPP doesn’t know about the language it is applied on, it merely proceeds to the translation of the input using very simple rules, and this can leads to tons of hard to detect—and to fix—problems.

Is Python Slow?

Python is a programming language that I learnt somewhat recently (something like 2, 3 years ago) and that I like very much. It is simple, to the point, and has several functional-like constructs that I am already familiar with. But Python is slow compared to other programming languages. But it was unclear to me just how slow Python was compared to other languages. It just felt slow.

So I have decided to investigate by comparing the implementation of a simple, compute-bound problem, the eight queens puzzle generalized to any board dimensions. This puzzle is most easily solved using, as Dijkstra did, a depth-first backtracking program, using bitmaps to test rapidly whether or not a square is free of attack¹. I implemented the same program in C++, Python, and Bash, and got help from friends for the C# and Java versions². I then compared the resulting speeds.

Generating Random Sequences (part I)

Every once in a while, we need a random sequence. Whether to test a data structure’s performance or to run probabilistic unit tests, the provided rand primitive from your favorite programming language has several limitations. First, it’s been known for a while that if most implementations of the C standard library rand() function are not very random, despite being “good enough” in great many cases. Second, and more importantly, it does not allow you to easily control the period nor to generate a permutation on , for example.

There are many methods of generating pseudo-random number sequences. Not all exhibit the same properties and, accordingly, a method may be more useful in one case and perfectly useless in another. High quality pseudo-random number generation is a notoriously hard endeavor, but there is a number of very simple algorithms that will get you out of trouble for certain specific tasks. Let us consider, for example, the example where the pseudo-random generator must generate the numbers in exactly once, in a random order, of course, in exactly draws.

The Zune Freezes: More on Unit Testing

Do you remember the epic fail that bricked the Zune a whole day on the last day of last year, a bisextile year? I described here and here how this error could have been entirely avoided using basic unit testing.

You probably remember (if you read the original post) that I first claimed that it’d take a few seconds to check all possible dates but in fact it ended up taking something like 90 minutes. This week, I come back on unit testing of a very large domain under a time constraint.

Faster than Bresenham’s Algorithm?

There’s always a number of graphics primitives you will be using in all kinds of projects. If you’re lucky, you’re working on a “real” platform that comes with a large number of graphics libraries that offer abstractions to the graphics primitives of the OS and, ultimately, to its hardware. However, it’s always good to know what’s involved in a particular graphics primitives and how to recode it yourself should you be in need to do so, either because you do not have a library to help you, or because it would contaminate your project badly to include a library only to draw, say, a line, within an image buffer.

Lines are something we do a lot. Perfectly horizontal or vertical lines have very simple algorithms. Arbitrary lines are a bit more complicated, that is, to get just right. This week, let us take a look at a few algorithms to draw lines. First, we’ll discuss a naïve algorithm using floating point. We’ll also have a look at Bresenham’s algorithm that uses only integer arithmetic. Finally, we’ll show that we can do better than Bresenham if we used fixed point arithmetic.

_S for Sneaky

Ensuring that one’s costumer base remains loyal, also known as lock-in, is an important part of many software and hardware manufacturers’ business plan. Recently, I came across an especially displeasing example of sneaky and subtle customer lock-in strategy from our friends at Microsoft.

Sneaky Cat is Sneaky

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.

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.

Your Automatisms Betray You

Yesterday someone dropped on the IRC channel where my fellow programmers, computer enthusiasts, and I hang out to get help to find a bug. He uses one of the paste sites (like pastebin.ca, pastebin.com, or rafb.net), pastes his piece of offending code, and so we get a look at the code. Of course, I go over the short program, notice a mistake in the scanf but it took me a full two minutes to notice the loop:

for (c=0; c++; cwe don’t read what’s actually written, but what we think is written, unless we pay the utmost attention to the code—what we should be doing anyway, but do not always. Usually, you zero in on that kind of bug rapidly, as you guide your search from the bug’s symptoms which leads you to defect’s approximate location. If you’re like me—write a little, test a lot—you find those bugs right away most of the times. However, even if you zero in rapidly, you still get a coarse-grained location: module, class, function.