Huffman Coding

So far my Christmas vacation has been spent repairing computers. My mother had a truly awful hard drive crash. Every trick I had up my sleeve (e.g. mounting the drive under Linux) failed. Files were lost. It was a little time consuming rebuilding the OS, but it wasn’t a hard effort. Thanks to Microsoft’s security holes, I downloaded about 100 Mb of PATCHES after re-installing XP and Office. How does anyone without broadband stomach that?

The truly interesting repair job was a computer that belonged to my wife’s friend. The family had a six year old 333Mz Gateway that was very sluggish and frequently it would lock up. After logging in, the hard drive would thrash for about five minutes before the computer was responsive enough that you could click on an icon. If my daughters’ 300Mz machine ever gets this bad, I’ll just give it away. It is sometimes just not worth the hassle.

But for others, I’ll give it a shot. Without the original Windows98 CD, I attempted to excise its daemons without a fresh re-install. I examined the programs referenced by the registry, the startup menu, and those loaded into memory after logging in. For each program I had to search the web for whether it was a “friendly” or not. It was a mess. Some of those were stubborn suckers to remove.

Countless sarc searches and computer reboots later, all was better. It runs faster and doesn’t hang. Her computer had, not one, not two, but seventeen different spyware/trojans installed. I was amazed.

Chris finished her Christmas shopping sometime in October. I, however, have yet to start. But one thing did catch my eye and I have gotten it for the girls already.

The girls got a Game Boy Advance SP last year. The girls have a handful of game cartridges to go along with it. I read about the GBA Movie Player last month. It seemed too cool and cheap not to get. Regardless of whether the girls even wanted it. But I think they will.

Unlike typical game cartridges, the Movie Player cartridge itself has a slot. Into that slot goes a standard CompactFlash memory card. That CF card can be filled with pictures, music, and videos from your computer. (There are conversion programs for just about every file format.) Plug it into the Game Boy and it can play/view those files. Way cool.

After loading it up with a couple of picture and sound files, I showed this to Chris after the girls went to bed. Her eyes rolled and she asked whether giving the girls another cartridge was a good thing. When I insisted it was worthy simply because it was cool, she wasn’t impressed.

At least I passed the geek “gene” onto my oldest daughter.

My 5 year old DVD player died. Back then, DVD players were expensive. They were heavy and large and had lots of buttons. My recently deceased player had 15 connectors for cables and 18 buttons on the front. It was nice. You could operate it completely without a remote control because it had that scroll wheel on the unit.

The basement DVD player, purchased a few months ago, has been moved up to the living room. It has only seven really tiny non-ergonomic buttons in front and only 8 A/V connectors in back.

I went to Best Buy to gander at possible replacement DVD players. They are much less expensive now. According to reports the average manufacturing profit for them, now made in China, is down to one dollar. They are shorter, narrower, lighter and shallower. They look and feel cheaper. You can no longer buy a player with a scroll wheel on the front at ANY price. None of them impressed me. You can buy a changer that holds 5 DVDs, but I just can’t see myself watching 10 hours of movies without getting up for a bladder break.

Almost all play MP3 and picture CDs now. There was one DVD player that had flash memory slots on it so you could view digital camera pictures on your TV, but most of my pictures on my computer’s hard drive.

One of the neatest DVD players out there also connects to your computer so you enjoy movie, picture and music files from your computer on the family room TV/stereo. No slide projector! This coolness comes at a cost though. Turns out it is cheaper to buy a plain old DVD player plus a separate media adapter that does the other stuff.

But why stop there? If you are going to buy something the can handle computer music and pictures, for a few bucks more your can browse the web and chat on your TV too. The optional keyboard becomes necessary though if you want to surf or chat.

As it stands now, I only have two inputs to my TV and both of them are taken (a VCR and the cheapo DVD player). So I cannot use one of these new toys in my family room. Perhaps if the box had its own display I wouldn’t have to connect it to the TV. And maybe the display should have a higher resolution than my analog TV. And hard drive for storing stuff. And the ability to take it from room to room. And, and, and…

It appears I am rationalizing a laptop purchase.

So instead of buying a $80 DVD player, really should get a $1800 laptop for Christmas. Think that reasoning with fly with the spouse? Not a chance.

The week I got my WiFi PDA a co-worker, Dave, got one as well. Different brand and operating system though. And thus began the endless comparisons on which brand was superior. Being geeks one of the things he suggested we do is find a two person game that we could play over the Internet from the couches of our respective Wireless-enabled homes.

Well I searched high and low and there are only a few multi-player games and none of them were Internet based. All the games out there required the participants to be within a few feet of each other. Might as well break out a deck of cards and actually talk to one other. Well that won’t do. Since that is too low tech for my tastes, I felt the need to write my own. Coincidentally I had just learned a new card game that was perfect for taking online.

In a few days while on a business trip, I wrote the desktop (Windows/Mac/Linux) version. A no brainer. We test drove it and got hooked. Others are playing. So much so that it has become the most visited site on my web server, ahead of this blog.

But writing for handhelds was a learning opportunity for me. Because it is less capable than a desktop computer, code I had grown accustomed to wasn’t available on the PDA. I had to do more coding “by hand.” The difference between using a calculator and doing long division on paper. I was able to use yet another open source library, but only after fixing a fex bugs in it. The code had been abandoned, so there is no one to report the fixes to and others will encounter the same problems if they haven’t already. But the program is finally working and it is high on the cool/geek factor. Recently I played one game while I was giving my girls a bath and Dave was gaming at his own house.

I coded it in Java (specifically J2ME CLDC/MIDP 1.0, for you geeks out there) because that platform is theoretically available for both handhelds. The version of Java for my PDA, while free, is ancient. The version for his PDA was modern and a cheap download from handango.com. Or so we thought. After charging his VISA number, he received just a license agreement that stated he had the right to use the software, but they didn’t actually give him the software. He had to get ahold of the software himself elsewhere. And they never told him where he could find it.

After numerous Google searches, we discovered that we had to download and install a trial version of an expensive developer package, Websphere, to get access to the Micro Edition software he had paid the rights for. No where in this product did it explain which files were necessary for his PDA or how to install them. More fruitless Google searches followed. My only user gave up and went back to the PC version.

Eventually I posted a message to a few mailing lists (with thousands of members) looking for beta testers for the game. I was hoping for dozens of testers with at least one other user with the same software and hardware as my frustrated friend. After a week, I only had two replies, and the only guy who was willing to test it has a phone display that is too small for the program. Another dead end.

So, with no one with the hardware to run my handheld program, what do I do? Write a THIRD version that will run in a Java-less browser. Perhaps now I’ll have users.

But that’s it. I’m drawing the line there. Really. Well, maybe. We’ll see.

Got an e-mail today. Even though Huffman Coding is explained in about half the introductory computer algorithm textbooks out there, someone wants me to write their College thesis for them. Example code and all.

Respected sir

                        yours sincerely
                     [redacted]

I don’t know whether they want me to write it in broken English.

This is cool if you’ve ever studied music.

I always thought a certain portion of population had a repressed desire to write a book. Perhaps not to become fantastically wealthy but to be recognized for the ability to present compelling ideas to others and possibly influence them.

Is this why I [mo]blog? Maybe. Frankly only having 4 semi-regular readers makes this a futile path to fame. Sadly even my wife doesn’t bother to read this. But this quest for creative contribution is partially the reason I became a programmer. It is an occupation with different, relatively creative challenges every day. And someday if my software ever gets sold to someone, it’ll stroke my ego.

The stuff I do takes advantage of open source software like Linux. Developers, who usually go uncompensated for it, contribute source code for others to use free of charge. I have written open source software as well. Aside from code I wrote that was purposely
bad and college students wanting me to write their Huffman Algorithm homework for them, my open source code goes largely unnoticed.

Two of the (many)open source programs I use at work are XML-RPC and thttpd. I mention those particular two because I happen to find a bug in each of them. Minor corner cases most people wouldn’t encounter, but since I could look at the source I was able to fix them myself. Now as a good steward of open source software, I notified the original authors so others can take advantage of my fixes. I posted my changes on their mailing lists too. Since they don’t know me from Adam, the code owners would have to be willing to review and merge my changes into the authority copy. I was hoping to be able to say I was a open source contributor.

So I waited for my patches to be picked up and incorporated into the main source branches. And I waited some more.

After posting my thttpd fix, the merits of my fix were debated. Some thought the problem should never arise. One person even argued that the program SHOULD crash when the rare situation does occur. I mentioned that he should warn me if he ever writes software for the medical or airline industries.

My XML-RPC fix was ignored as well. It was more than a few line fix, so a person would have to spend a few minutes reading it to understand it. No one bothered. Months later someone reported on the mailing list the same problem I had had. He was kind enough to post a simpler fix which, unfortunately, had no chance of compiling let alone solving the problem. After I remind everyone that I had already solved the problem the code owner did take notice and incorporated my changes. Yippee! I’m famous in a very, very, very small way.

This domain name has a double meaning: this site contains my personal code and it also happens to be the name of my late Uncle’s relatively infamous algorithm. (Elsewhere on this site I have a description of it.) My uncle came up with the algorithm at a pretty young age (to get out of taking a test) and since had gone onto to less famous endeavors.

One of those passions was Computational origami (origami sekkei). While Huffman Coding is in web images, digital music, fax machines and VCRs, David Huffman’s foldings are only in my cousin’s den.

But out of the blue, an article appeared in last Tuesday’s New York Times (June 22, 2004, page D2) on his artful foldings. It included color photographs of three of his works. It is also on their (registration required) website.

He would graph complex equations on stiff plastic laminate then score along those curves. With a gentle bending at those scores, a 3 dimensional piece of art would snap into place. No cuts, no tape, no glue. With no stress on the paper/plastic. A perfect equation as it were.

He had developed a way of analyzing graphical equations to determine whether they would yield a perfect (“zero curvature”) surface. Mindbendingly detailed mathematical analysis, but it yielded mindbendingly beautiful art.

On the flight back from South Africa, the flight map, which normally shows a map, the altitude, air speed and distance to the destination, wouldn’t display on our little pop-up screens.

Instead of cycling through 5 pretty screens, what appeared was a Linux console full of errors from an endless script. To most of the passengers, I’m sure it was gibberish, but being Linux developers, it made sense to my co-worker and me. The in-flight entertainment computer (a small 486) was trying to download the current flight information from another computer (I’m guessing the main navigation system) and failing miserably. It was getting repeated “File not found” errors.

Linux boot screen

Even with the errors, I’m glad it was running Linux. Had it been running Windows, the message would have been the less flight-friendly: “Abort, Retry, Fail?”

I’m going to South Africa tomorrow. So I am packing today.

I’m taking my PDA and since I’m going to be gone for 8 days, I’m bringing along its AC adapter to charge it. I’m also taking a company laptop and its adapter. Since its battery lasts only about two hours, and the flight is 18 hours, I’ll bring my little MP3 player to listen to music. But that’s 18 hours each way so its adapter is coming too. All these adapters have bulky “bricks” in the middle of their cords.

I’m hoping to go on safari over the weekend so I’m taking my camera. It takes rechargeable batteries, so you know what that means.

I shave with a rechargeable electric razor and beard trimmer: they are coming too. After all, we are talking 8 days here.

The Republic of South Africa, is 220 volts and only some of these things cannot deal with that, so I have to bring my AC converter and plug adapters. They have a very unusual outlet over there.

But I will draw the line somewhere: I’m not taking my cell phone (it doesn’t work over there), electric toothbrush, and I’ll towel dry my hair.