25 Sep 2007

I wrote this thing back in September 2005 when I had to learn MATLAB for work. This writeup was done about year later.

Download the code (GPL licensed) at download/walk.tar.gz (33.72KB). There are both Perl an MATLAB versions.

This was a text-adventure engine I wrote when I was starting to learn MATLAB programming, which means the MATLAB code here is pretty horrendous. It may or may not work in GNU octave, I didn't bother checking. That's because I later wrote a Perl version that does the same thing (when I was still starting with learning Perl, so not much better). Included is a sample "world" to explore (in English and pig latin!). The format for the "world" is a really simple one, probably missing a lot of features of a real text adventure scripting language. Have fun!

This is what it looks like,

Welcome to Walk. Just type in plain English into the 'Action:' line what you
want to do.

Type 'inv' to display the inventory.
Type 'clc' to clear the screen
Type 'look' or 'ls' to get the current description of the room.
Type 'save' to quicksave the session.
Type 'load' to restore the quicksave session.
Type 'doc' or 'help' to see this message again.
Type 'quit' to quit.

 Action: look

 You appear to be in a small bedroom. There are no windows. Light is
provided by a small ceiling lamp. There is a brown wooden door, a small bed
with no sheets, a small box which is laying on the bed.

 Action: _

23 Sep 2007

Today I had a large document written in MediaWiki markup. The document was a simple one consisting only of paragraphs, all possible heading levels, and flat lists. There were no mathematical expressions or images -- nothing fancy whatsoever. I wanted this document available in LaTeX markup so that I could have a nice, professional looking printout.

After some brief searching I couldn't find a practical, simple script to convert the document to LaTeX markup (I didn't look very hard). Everything I found wanted to do the conversion the opposite way that was needed. It ended up that writing and debugging my own Perl script to do the job only took me about 30 minutes. You can see it here (BSD-style license),

wiki2latex.pl

Here are the main guts to give you the gist of it,

while (<>) {
    # Sections
    s/======([^=]+)======/\\subparagraph{$1}/g;
    s/=====([^=]+)=====/\\paragraph{$1}/g;
    s/====([^=]+)====/\\subsubsection{$1}/g;
    s/===([^=]+)===/\\subsection{$1}/g;
    s/==([^=]+)==/\\section{$1}/g;
    
    # Special characters
    s/([&#_])/\\$1/g;
    
    # Lists
    if (m/^\* / && !$listmode) {
	print "\\begin{itemize}\n";
	$listmode = 1;
    }
    if (!m/^\* / && $listmode) {
	print "\\end{itemize}\n";
	$listmode = 0;
    }
    s/^\* /\\item{} /;
    
    print;
}

Here is some sample input markup and output,

sample.wiki
sample.tex
sample.pdf

The script will write out all the header and footer markup (including title page and table of contents, which is what I needed) so that the output can go right into LaTeX for processing. The script is very far from being complete in terms of a "MediaWiki to LaTeX converter", and I have no intention on making it any more complete either. It does only what I needed it to do: handle a few special characters, convert headings, and create lists. I am providing it here in case someone finds it useful or interesting. Perhaps it may serve as a stepping stone for creating something more complete.

19 Sep 2007

An idea I had some time ago would be for a free (as in speech) musical (or play). It could be licensed under the GPL or something like it (the GNU Free Musical License, GFML, perhaps?). For example, think of the scripts and music scores as the "source code" for the musical, where these documents must be provided to ticket-holders upon request in digital form, such as on a CD, or printed. Just like free software, we are mostly concerned with preserving the freedom of the user/audience. These are free musicals.

Have you ever watched a great musical and your skin tingled at the orchestra's crescendo during the hero's solo? Or perhaps you choked up at a dramatic scene? These moments should not be locked up so that they cannot be shared. Free musicals would be another step towards a free culture where these scenes are not lost, where everyone is free to share his or her own culture. This freedom does not exist fully today. For instance, I can write a story about vampires but I can't write one about Jedi.

Just as free software developers don't have to starve, neither do free musical composers and writers. The word free refers to freedom, not price. A free musical author can distribute the musical to a producer for any price he or she wants.

You see, I was involved in my high school musicals growing up and I remember how they had to pay some steep royalties to put these shows on. One year, to help pay for the show we had collected spare change from students during lunch periods. Even for all this expense, we weren't even permitted to make copies of the music and scripts as needed for use in the production (these cost extra). We were being dominated by the musical's publisher.

This, of course, did not stop these extra copies from being made. It's just another bad law which should have been and was ignored. Remember, the act of breaking laws itself is not wrong. You get to decide right and wrong for yourself. No one, especially a politician, can do this for you. I would wager that, in the US at least, just about everyone breaks some law at least once a month. Okay, back to free musicals.

If there were free musicals from which to choose, once a high school (or anyone) obtained a copy of a musical's source code they would be free to put on a production without paying any special or additional per-seat or per-ticket royalties. They could make as many copies of scripts and scores as needed without having to break any laws. They could even send copies to other schools.

Let's say a choir teacher (or whoever is directing things) goes out and sees a free musical somewhere. She enjoys the show so much she wants to have her students perform it as the next year's production. As a ticket-holder, she requests and receives the source code for this show. That's it! She can put on this show for the cost of a single ticket. In other cases, someone might be feeling generous and make the source code available to anyone at no cost to anyone who asks.

Since I have had the idea, I have dreamed of writing a free musical. Unfortunately, my writing skills are poor and my music skills are even worse. I have arranged music for a marching band in the past, but have done no serious composition. Maybe some day I will be good enough to write one. I would like to learn GNU LilyPond sometime and writing a free musical would be good practice.

Of course, an existing musical could always be liberated (expensively, without doubt) and turned into a free musical.

17 Sep 2007

I have recently really gotten into clustering with excitement to write something that can really take advantage of one. The first thing I had to do was figure out how to cluster my computers. The second was to write something that could really use my personal cluster to its full potential. This post is about the first step.

A live CD was the obvious choice (and still is) to begin clustering: no installation and quick setup. I started with dyne:bolic, a GNU/Linux distribution geared for editing and creating multimedia while strictly using free software (already off to a great start!). I had read that dyne:bolic had clustering capabilities with openMosix, which was my reason for looking at it in the first place. I found out later (after digging deep into documentation a dyne:bolic mirror) that dyne:bolic doesn't include openMosix anymore. No good for me.

Next I found BCCD, a live CD distribution based on LNX-BBC, the same distribution used by the Free Software Foundation for its business-sized CD member cards. This one is fantastic! I think this is due to its goal as an educational tool, making it easy to learn about clusters while using it. It comes with several programming examples and full MPI development capabilities.

The only objection I have about BCCD is that the boot/setup process is too interactive and manual. When booting off a CD, you must create and confirm a password (good!), hit enter through several dialogs to detect network cards (annoying), plus a dialog about DHCP (not bad). Then you have to broadcast a heartbeat and enable the openMosix detection daemon. I also have a problem with it occasionally trashing the fat16 file system my USB thumb drives. Fortunately, this only causes trivial, and small data loss as the drive contains only data generated by the cluster.

I own two computers and have a access third one (a laptop) borrowed from my school for use in a robot design lab. I have not yet employed my roommate's computer in my cluster (only a matter of time!). Since my NETGEAR router has only 4 ports, 4 computers is the max for my cluster. Booting up 4 computers with BCCD can be annoying enough, but imagine booting 30 (in some computer lab) by yourself! I bet they pictured a lab full of students all handling their own boot/setup sequence when the BCCD team made these decisions.

As I said before, BCCD has great MPI facilities (which their example programs take advantage of), including support for synced directories. I have yet to employ the MPI, however, as I find fork() and pipe() to be much more convenient in terms of coding and execution (run and forget). If you can tell me why MPI is better than a regular POSIX pipe when it comes to clusters, send me an e-mail. I haven't figured why yet, if it is even true in the first place.

I have a working version of a program that can take advantage of a cluster. I will write about this later as a sort-of "part 2".

14 Sep 2007

I wrote this code and writeup some time ago and have used it in several projects for building parse trees quickly. Using the pool is faster than making a system call with malloc each time you add a new node. In fact, one of my programs ran 25% faster when I dropped in the this memory allocation pool. This code is very solid and reliable.

Download the code (GPL licensed) at download/alloc-pool.tar.gz (2.58KB).

I read about memory allocation pools in the Subversion manual and decided to write one for fun. So here it is. Included is a small driver I ran over night to test for memory leaks. lint will complain about memory leaks on this code, however. I also added thread safety, but I don't suggest you use it.

A memory allocation pool is good for speeding up a program that needs to make many small memory requests quickly (many system calls). Instead, one system call is made in place of many.

It is also useful for semi-automatic memory management. Let's say you build some large tree structure somewhere in your program. If you want to free all this memory used by the tree, you will need to traverse it to take it down. This takes time and code. If you use a memory pool, you can free all of the memory at once by freeing the entire memory pool.

The pool works by allocating a large chunk of memory and dishes it out as requested (a subpool). If a request is too large to take out of the current chunk, it allocates another chunk twice as large as the previous one (another subpool). This doubling allows the pool to quickly scale up to whatever size is needed. Memory will still be allocated from the old pool until that pool has too many misses in a row (hard coded to 10 in my sources). Once this happens, the subpool remains untouched and your pool will have some slight internal fragmentation.

08 Sep 2007

This is one of my projects. The original idea for this project came from Sean Howard's Gameplay Mechanic's #012. The basic idea here is that image files are the second easiest type of data to share on the Internet (the first being text). Sharing anything other than images may be difficult, so Why not store files within an image as the image data? This is not steganography as the data is not being hidden. In fact, the data is quite obvious because we are trying to make the data as compact as possible in the image.

My "PNG Archiver" is usable but should still be considered alpha quality software. I am adding support for different types of PNGs (currently it does 8-bit RGB only), but I have found that using the libpng library gives me headaches. The archiver can actually only store a single file (just as gzip doesn't know what a file is). This is because I do not want to duplicate the work of real file archivers like tar. To store multiple files, make a "png-tarball".

Here are a couple examples. Below is the US Constitution (gzipped),

And this is an audio recoding I made (encoded in Ogg Vorbis),

The PNG Archiver stores a checksum in the image that allows it to verify that the data was received correctly. This also allows it to automatically scan the image for data. When it reads in a piece that fulfills the checksum it assumes that it found the data you are looking for. You can decorate the image with text or a border and the archiver should still find the data as long as you didn't disturb it. (examples of this on the project page)

You can find the project page with detailed information (duplicating some of what I said here) under projects/pngarch.

05 Sep 2007

Update 2009-6-30: Thanks to HTML 5 and the video tag I will be self-hosting videos from now on. This is information is only historical.

As I have stated previously, I love free software and I try to use free software exclusively whenever I can (it is very difficult to find employment in computer engineering where no proprietary software is used). This can pose a problem when I want to watch YouTube videos because I do not use the proprietary, non-free Flash player. The free Flash players currently either handle YouTube poorly or not at all. I also find Flash annoying enough that I am not interested in using these free Flash players anyway (fewer ads automatically!).

Like everyone else with an e-mail address, I get links to videos on YouTube from my friends. I also post videos there myself under the name "throwaway0" as it is convenient not only for me, but also for anyone who wants to watch the videos. Now, if the only way to watch these videos was with proprietary software, I would not encourage this. In fact, not too long ago this was true of most online video, which was limited to a "choose your poison" type situation between the proprietary, worthless Windows Media and QuickTime formats. No poison for me, thanks.

I have discovered several solutions to watching YouTube with free software. There are two steps involved: getting the video and playing the video. For the first you have youtube-dl and Firefox Fast Video Download.

youtube-dl is a Python script that you can easily install on your system. You just give it a YouTube URL and it does all the work. It feels a bit like wget. The Firefox add-on will add a nice little icon like this,

Clicking this icon will download the video. With either tool, you will have this .flv file somewhere that you want to watch.

To watch the video file, you can use mplayer (without the w32 codecs) or VLC. As far as I know, these videos are handled with free software only when using these players. They play fine (except without seeking) on my system. I use Debian GNU/Linux so I am pretty confident that my system is strictly free software.

Now you can watch YouTube without having to fall victim to proprietary software.

02 Sep 2007

In preparation for another project idea I have (to be posted in the future), I wrote a Mandelbrot fractal generator in Octave. Octave is great for just trying things out and prototyping your algorithms. It is very slow, however. Here is the code,

function mandel_img = mandel ()
  ## Parameters
  w = [-2.5 1.5]; # Domain
  h = [-1.5 1.5]; # Range
  s = 0.005;      # Step size
  it = 64;        # Iteration depth
  
  ## Prepare the complex plane
  [wa ha] = meshgrid (w(1):s:w(2), h(1):s:h(2));
  complex_plane = wa + ha * i;
  
  ## Preallocate image
  mandel_img = zeros( length(h(1):s:h(2)), length(w(1):s:w(2)));
  
  ## Generate mandelbrot
  for wi = 1:size(mandel_img, 2)
    for hi = 1:size(mandel_img, 1)
      
      z = 0;
      k = 0;
      while k < it && abs(z) < 2
	z = z^2 + complex_plane (hi, wi);
	k = k + 1;
      end
      mandel_img (hi, wi) = k - 1;
      
    end
    ## Display progress
    waitbar (wi/size(mandel_img, 2));
  end
  
end

You may need to comment out the waitbar line if you do not have Octave-Forge installed properly (as is the case with Octave 2.9 on Debian as of this writing) or at all. You will also need Octave-Forge if you want to use the image functions described below.

You can find the same code all over the Internet for many different languages. The advantage with Octave is that it knows about complex numbers so that this can be expressed directly with z = z^2 + c and abs(z). For an introduction on how the Mandelbrot is generated, check out the Wikipedia article.

Now, this code just generates a matrix of the escape iteration numbers for each pixel. To visualize this, you will need to use the image functions. The simplest thing to do is view the data as a boring greyscale image.

octave> m = mandel(); # Generate the data
octave> imshow(m);

You should see something like this,

You can save this as an image with imwrite,

octave> imwrite("mandel.png", m*4)

The *4 part is because the iteration depth was set to 64. The image being written will have values between 0 and 255. This allows the data to use the full dynamic range of the image.

If you want more interesting images, you can apply a colormap. Octave-Forge has two handy color maps, hot and ocean (cool). To make the inside of the fractal black, which are the points that are part of the set and never escaped, stick black on the end of the colormap. This can be done like this (viewing and saving),

octave> cmap = [hot(63); 0 0 0];  # The colormap
octave> imshow(m + 1, cmap);
octave> imwrite("mandel.png", m + 1, cmap);

m is between 0 and 63. We add one to it to put it between 1 and 64. Then we take the colormap of length 63 and stick black on the end. If you substitute ocean for hot, you will get a nice blue version.

You can modify the code above to try to get different fractals. For example, try z = z^4 + c instead,

More on fractals another time.

01 Sep 2007

Welcome to null program. This is my new home as my student location will no longer exist in a few months. Here is where I will share my projects and ideas, even if no one is looking, reading, or caring.

The name for this website comes from a phrase spoken in several places in my favorite book, The Moon is a Harsh Mistress. If you have not read this book, you are missing out. I recommend you go to the nearest library immediately and read it. Amazon lets you read the first chapter online if you want to get a taste of it. When I started reading it, I was hooked right away. Why is it a great book? Because it is about an American Revolution style libertarian revolution on the moon, and the hero character is a computer engineer. What book can get better than that?

I would like to post something interesting here about once a week or so. I am taking classes right now, so getting ideas should be relatively easy. The first few posts will probably be repeating things I have already published at my old student location. This will include little intros to my old projects and a bunch of code snippets.

Also, separate from this blog thing are my projects, such as the PNG Archiver and binitools. These have a permanent home located under projects/.

I am a big free software fan and you will probably see the GNU project being mentioned a lot around here. I also use Emacs for just about everything I can. Here is more advice: learn to use Emacs. You will become much more productive. After using Emacs for awhile, you will begin loathing word processors and mice (the computer kind). More on this later.