Not Loosing the Perspective

My first true computer, a TI 99/4a (which I talk about also in a previous entry), had 16 or 48 KB of RAM, depending whether or not you had one of the memory expansion cartridges, and that limited quantity of memory severely curbed the complexity of the programs one could write on the machine. However, the limited complexity of the programs, the relative crudeness of the development environment (a BASIC shell) and the slow execution speeds weren’t very obvious to me back then. They were somewhat mitigated by the novelty of the computer itself as a machine, and by the perpetual intense excitement of discovery. The arduous design of programs to save memory, fit more graphics or more code, or even getting our programs to work at all was less about constraints than challenge.

The same kind of constraints—or challenge—followed me over the years as I moved on to different computers. Despite their being more powerful, both faster and sporting more memory, the challenge remained there because while the computers got better, so did I at programming. I kept asking more out of the machine, writing increasingly complex programs needing either more memory or more speed, often both. That meant better algorithms, better data structures, and better implementations¹.

Different problems aren’t always different

Magic Squares are much less frequent than latin squares in computer science (on which we may come back in the future), but they have a number of (fun) applications.

Historically, magic squares are tied to numerology, alchemy and other esoteric sytems. However, as you may already know, I’m not interested in pseudoscience except to debunk it, so this post isn’t about using magic squares turtles to predict the level of the river running behind your house.

Albrech Dürer's Melancholia I

Ad Hoc Compression Methods: RLE (part II)

Yestermorning I presented an ad hoc compression method known as RLE, or run-length encoding and I got quite more reactions than I thought I would. Many suggested doing plenty of other stuff despite the fact that the post was about RLE, not about <insert your favorite compression method>. But something very nice happened: people got interested and many suggestions came forth.

I decided to implement the median-based prediction method as suggested by Dark Shikari here. Let us see the results!

Ad Hoc Compression Methods: RLE

Suppose you have been sub-contracted by a video game company, say Nintendo, to come up with an low power, low-memory, implementation of a popular video game, say, an installment of the infamous Pokémon series. The envisaged device is very slow (it has a 2MHz processor) but has a 220×176 pixels color screen capable of displaying 32768 different colors. It also has a hardware sprite mode, but sprites are limited to 4 distinct colors. You have to encode the complete database of Pokémons, which are several hundreds, in as little space as possible. Each image vary somewhat in size, but can only have 4 distinct colors from the possible palette of 32768 colors.

A typical Pokémon would look like:

A typical Pokémon image, shown enlarged and in original size.

Since the artists put a lot of efforts into drawing the critters in 4 colors, and because of the hardware requirements, you cannot use a compression algorithm that modifies or creates more colors than the original image had, therefore excluding JPEG. Moreover, the JPEG codec would be too complex to port to the platform considered. You must therefore use a simple lossless codec.

We will be comparing 5 codecs for the Pokémon image database. We will be looking at a “block” codec, which will serve as a comparison for a non-RLE codec. We will be looking at 5 variations on the theme of run length encoding, or RLE, namely, the All Counts, the Bit Select, and Auto-Trigger RLE. The last variant will help Auto-Trigger RLE by using predictors, transforming the input image into one that is easier to compress using RLE.

Soft-Ignore: Filter buggers in XChat

If you, like me, hang out once in a while on IRC to chat with fellow programmers (or with fellow practitioner of your favorite hobby), you may find that some individuals are just not worth your full attention. One easy, and rather definitive way to deal with the problem is to use the /ignore command that allows your IRC client to filter incoming messages from those people, and you just never see them again… quite literally.

However, just /ignoring someone is rude, and may prevent you from keeping a eye on them. You know, the “keep your friends close, your enemies closer” kind of thing.

A long time ago, with a friend, I wrote a mIRC script that shaded the “ignored” people’s text so that it was hard to read (like dark gray on blue), but the text was still available. To view the text, you could either squint or select the text. This week, I present a python version of that script, for XChat, based on the work of Albert W. Hopkins, a.k.a. Marduk, released under the GPL.

What the Happy Hacking Keyboard should have been

The Quest for the Perfect Hacking Keyboard is indeed an eternal one. Over the years, I had great many keyboards and most of them went the way of the dodo. Recently, despite not having other Apple products, I tried the (wired) thin Apple aluminum keyboard. As I prefer very thin keyboard over thick ones, and laptop-style keys to the big M Type keys; it was a very good match. However, after a while, I got unnerved by the extra, useless keypad. In short, the keyboard is too long: as I am right handed, it’s always somehow in the way of the mouse so I started looking for a better keyboard. Again.

So I got the Apple aluminium keyboard, wireless version.

Suggested Reading: The Myths of Innovation

Scott Berkun — The Myths of Innovation — O’Reilly, 2007, 178 pp. ISBN 978-0-596-52705-1

(buy at Amazon.com)

In this book, Berkun debunks the myths surrounding the new, the innovation, the invention that will change the world, surrounding the inventor, lonely and strange, superman or genius. In ten chapters, he systematically demolishes a series of myths, starting by the myth of epiphany, that is, how an innovation is “revealed” to its inventor. He explains how and why such epiphanies do not exist, and, if they exist, how they cannot be anything but the final step of long, tedious work.

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.

Ad Hoc Compression Methods: Digram Coding

Ad hoc compression algorithms always sound somewhat flimsy, but they still have their usefulness whenever the data you have to compress exhibits very special properties or is extremely short. Universal compression algorithms need a somewhat lengthy input to adapt sufficiently to yield good compression. Moreover, you may not have the computing power (CPU speed, RAM and program space) to implement full-blown compressors. In this case also, an ad hoc algorithm may be useful.

Digram (bigram, digraph, bigraph) coding is one of those ad hoc algorithms. Digram coding will compress text (or any source, really) by finding pairs of symbols that appear often and assigning them codes corresponding to used symbols, if any.

Let us see in detail what digram compression is, and how effective it really is.

__MODULE_DEBUG_TOOLS__

Yesterday, at least at the time I am writing this entry, I spoke about the Zune and its time bug that caused so many of the devices to just freeze on boot. It its clear that this bug is the result of poor testing (in addition to a poor implementation of a conversion using loops rather than explicit divisions and moduli) and this week, I’d like to tell you about one of my tricks to debug code.