Here is a lesson that I have learned over the past 4 years: _TOOLS_. Humanity has reason and it can use tools. It is what separates us from the animal kingdom: the ability to do something better the second time, the third time, and so on. In fact, I can create a tool that has no purpose today, but saves a dozen hours tomorrow. I can build a tool that builds a tool that builds a tool. The Nth tool may be totally useless in the hunter-gatherer sense of the word, but the Mth tool may cause something wonderful to happen.

Take for example, the microprocessor. A person or animal with a microprocessor would hardly be able to use it as jewelry (some people do that). But put the microprocessor in a motherboard with a bunch of other ICs and you have a functional computer. It needs software, data, and all kinds of stuff. It is a tool.

It is easy to decide if an object is a tool. It is also easy to compare the attributes of tools. A CDROM is a tool because it has a function: store data. A floppy is also a tool to store data. A floppy stores 1.44 MB while a CDROM stores 650-700 MB. A person can compare these attributes to decide what they should use for their specific purpose. The CDROM and floppy both have other interesting attributes, like read-only vs read-write, failure rate, and access speed.

A person who uses a computer has a large array of digital electronic tools available to them. The computer is a tool which has the amazing property that it can be used to create and distribute tools. Imagine that: a tool that can make a practically limitless amount of tools. In fact, a computer programmer can create many tools everyday. I have created a few tools today. Looking at their attributes, I can decide their value.

---

You might have caught a glimpse of the image above. Look at it again, if you want. If you want to reproduce the picture, you can using the data available on this very page. The text says:

# vorbis floor1 packet
  floor1_Y 0 20
  floor1_Y 1 88
    floor1_Y 2 2
    floor1_Y 3 0
    floor1_Y 4 7
    floor1_Y 5 3
    floor1_Y 6 0
    floor1_Y 7 0
    floor1_Y 8 0
    floor1_Y 9 0
    floor1_Y 10 0
    floor1_Y 11 0
    floor1_Y 12 2
    floor1_Y 13 0
    floor1_Y 14 13
    floor1_Y 15 0
    floor1_Y 16 0
    floor1_Y 17 0
    floor1_Y 18 0
    floor1_Y 19 0
    floor1_Y 20 0

What does this cryptic data mean? Copy this data into a text file named 'ov53h51.dat'.

Here is one of the tools I wrote today:

set terminal png color
set output 'ov53h51.png'
plot 'ov53h51.dat' using ($2):($3) with line

If you put that input into gnuplot, you will get my image. What is cool about this is that I have 24994 of these packets (not data points, _packets_). Yeah...

I generated these 25k packets with yet another tool that I created over the past few weeks. That tool is the Ogg Vorbis R0xx0rer. It literally r0xx0rs¹ the data from an Ogg Vorbis audio file. The lastest output of this tool is the floor1_Y. The floor1_Y is what the actual data of the Ogg Vorbis audio file is. Besides ~2.5 kB of headers, it is mainly floor1_Ys. So I have successfully r0xx0red that data from the file. You can see in the graph that it looks like a spectrum. That's no mistake, it is supposed to be the spectrum of the audio at a certain short period of time. The X axis isn't frequency, I think it might be a constant multiplied by log of frequency or something like that.


Now I need to use it. I have a few ideas. The problem is the Huffman codec. I don't like it very well. It obscures the data with a layer that is pretty difficult to understand. It uses variable length codewords to explain data. For example:

00 = A
011 = B
010 = C
1001 = D
1010 = E
1011 = F
1100 = G
1101 = H
1110 = I
11110 = J
11111 = _ (underscore)

Decode:
11110 00 011 011 00 11111
J A B B A _
1001 00 11111 
D A _
011 00 1001 11111 
B A D _
010 00 011
C A B _

There are 11 values in the above Huffman tree. That would normally require 4 bits per character. The Huffman codec uses 2-5 bits. If the ones with less length are used more, there is a overall savings by using the Huffman codec. In my example, JABBA DA BAD CAB requires 54 bits to encode. The normal 4 bits per character would require 68 bits. Had I given J and underscore the positions of E and F, I would get even better compression. But there's a problem here. Do you know what it is? The header. The header takes space to setup the decoding of the Huffman data. It would take at least 3 * 11 = 33 bits to describe the header even if you made many assumptions. 54 + 33 = 87 bits to encode the Huffman data. Obviously, there are good ways to encode Huffman data so that the data will be smaller than the original.

Why does an audio codec use Huffman? There is a tradeoff between size and complexity that the Vorbis team decided to make. How much did Huffman coding save? I can calculate that with my Ogg Vorbis R0xx0rer. For each non-zero output on the floor1_Y, I have to give 6 bits. For each zero output on the floor, I have to give 1 bit. Let's calculate!

data count
-1   1296 = 400+896
0    465676 = 406737+58939
>0   371431 = 190601+122990+50826+2+7012

bits = 371431 * 6 + 465676 * 1 + 1296 * 1
     = 2695558 bits
     = 336945 Bytes.

Ogg Vorbis Huffman encoded 
floor1_Y size: 275727 Bytes.

Compression ratio: 275727 : 336945 = 81.8%

It's ironic that my system that is supposed to be easier than Huffman which gives one bit to zero and 6 bits to data is actually a Huffman tree itself:

0: 0
1: 100001
2: 100010
3: 100011
...

It just happens to set the least 5 bits to the binary value of the number:

1: 00001
2: 00010
3: 00011

That makes it a very easy Huffman tree to decode; five lines of code:

nonzero = read 1 bit;
if(nonzero == 1)
	data = read 5 bits;
else
	data = 0;

So Huffman compresses by 18.2%. They put quite a large amount of complexity into their codec for a savings of 652 kB per 3.4 MB. They would probably feel like they hadn't done their full duty if they didn't compress it as much as possible.

Looking at it, the floor1_Y is not as large a part of the Ogg Vorbis file as I thought it was. I thought it was ~3 MB, but it's only 269 kB. There is still the residue, ... Hmm... I guess I must continue the quest for the purpose of additional information. After 2 weeks of constant work on this project (~80 hours), I have found that while the Ogg Vorbis spec is pretty good, it's order is confusing (jumping to and fro a bit) and is missing a few minor parts. The source code comes in very handy.

This brings us back to the original point: _TOOLS_. In the past four years, I have worked on a number of _TOOLS_ and I have used a number of amazing tools. Four years ago was when I switched to Linux. It was a natural step in my computing evolution: I needed a set of tools that did more work than I could ever hope to accomplish with Windows. Those tools are available and easy to use for Linux. Those tools are working their way back to Windows developers, but it is not the same. Windows is a poor development environment. Linux Distributions like Slackware, Gentoo, and Red Hat Fedora (and most others) come with a set of amazing tools:

• the Linux Kernel (dependable, secure, fast, small core)
• GNU Operating System (a set of amazing, yet simple tools that make up a usable command-line/library interface to the computer)
• GNU C/C++ compiler (a magnificent tool to create programs and tools that can do anything)
• X11 (the base gui layer)
• KDE (a beautiful desktop environment)
• GIMP (a powerful image editor)
• Python (a powerful scripting language)
• Apache (the best web server)
• PHP (a powerful web scripting language)
• and much more.

The value of these tools are innumerable (priceless in both contexts). While the Open Source community works diligently to provide ports of many of these tools to Windows, but the bulk of the work is being done for the Linux platform because Linux is so well written.

Here is an important part about tools: the quality of tools increases productivity. Linux as a tool increases the productivity of all its users. Those users are able to work on more projects because they do not have to work as hard. This is the lesson: use the right tools and you will be able to do much more than with poor tools.

This is probably the point where you say: "Okay, I get it, can I get back to my math / physics / chemistry / comp sci homework?"

Permalink