Avian’s Blog

One simple reason: it got really hard to do anything useful on my PowerBook after I upgraded to OS X 10.5 Leopard.

My office suite of choice is OpenOffice. Granted it wasn't very responsive even before the upgrade, but at least it responded fast enough to be usable. Now, it either doesn't start at all (version 2.2) or randomly crashes (version 2.3) after a couple of minutes of work. Now I'm using NeoOffice. That works, but has other quirks (like every once in a while it doesn't let me change the font). Did I mention how slow it is? It uses up practically all of computer's 1.25 GB of RAM and still takes around 5 seconds to show up a font selection dialog.

Other applications like Firefox and Thunderbird also got less stable. I often get first the spinning beach ball cursor and then after some minutes of unresponsiveness a crash dialog.

X11 applications are another pain with Leopard. GIMP and Inkscape will crash X11 or X11 will crash them once every 15 minutes. And they are also slow - much slower in my opinion than on OS X 10.3.

I also had to disable practically all of Leopard's fancy new features (at least those I could turn off). Spaces for example. After a couple of weeks of using it I found out that Spaces is a terribly broken implementation of virtual desktops. For example if I have several terminal windows scattered across desktops, and I switch with alt - tab to the Terminal application, Spaces will take me to a random desktop that has a Terminal window on it. Unusable and nerve breaking since most of the windows I used are terminals. It also plays terribly with X11.

There's also a problem with reboots - for some reason the system won't shutdown properly. It closes all applications but then hangs, showing just the desktop (something that painfully reminds me of similar problems I once had with Windows 95). Only a long press of the power button will help. The worst thing about that is that it does the same thing when restarting after installing software updates. I'm just waiting for some broken update to do some more serious damage.

Finally there are also some minor things that make the entire system feel unpolished. Like clipping errors on icon titles in Finder and some weird cases where I get random noise instead of transparent background in terminal windows.

Oh, and did you know that Finder now represents all non-Apple computers on the network with icons showing monitors that are displaying Blue Screen of Death? Now that's just childish. No Linux desktop I've ever seen did this and the average Linux user probably hates Windows more than an average Apple user.

Two years ago when I bought this PowerBook I bought it because it was a computer that really just worked. It seamlessly synchronized with my mobile phone and my other hardware, all applications worked out of the box and most free software I used on Linux also ran on OS X. I could really concentrate on my work instead of having to continuously tweak the operating system - something I don't want to do when I'm traveling with my laptop. Looking back this computer gave me the least problems and best experience of all systems I used.

With Leopard, all these benefits are gone... And if I can't have a system that works, then I rather have a PC with Linux where at least I can fix things myself when they aren't working.

They say that every hacker once in his life founds a bug in Perl. It seems I just found mine.

It started when I was hacking on Wikiprep, the Perl script we're using to parse Wikipedia. After I made some trivial change and ran it on a sample of Wikipedia pages I was greeted with a Segmentation fault message on the console. Since this was the first time I saw Perl do that, I quickly ran the same thing on another machine (I still don't trust Leopard on my laptop), this time a trusted Debian GNU/Linux development server. When I got the same result I knew I'm up to something.

After a couple of hours of testing I came up with this short script that consistently crashed Perl on every machine I tried:

sub a {
	my ($ref) = @_;

  	$$ref =~ s/\[\[[^\[]*\]\]/&b(pos($$ref))/eg;
}

sub b {
	my ($a) = @_;
	return "";
}

$a = "";
open(FILE, "<sf.dat");
binmode(FILE,  ':utf8');
while(<FILE>) {
	$a .= $_;
}
close(FILE);

&a(\$a);

sf.dat in this case is a UTF-8 encoded file with some links in MediaWiki markup (you can see it here).

After some consulting with people on #perl IRC channel we found a work around and my work on Wikipedia could continue. The crash seems to be caused by the pos() function, which can be replaced with lookups to @+ and @- arrays.

I haven't yet reported this issue since I was told Perl 5.10 is just around the corner, which might have this issue already fixed.

Our development server sometimes shows weird things in top (it also tends to crash quite a bit):

It's not limited to 9999% CPU - I've seen all sorts of strange readings, larger than 100%.

Maybe we had a quantum computer in our living room all this time without knowing it.

A lot my work at Zemanta has to do with storing large amounts of data (like titles of lots and lots of Wikipedia pages) in memory. Since the main problem here is running out of swap space I've done a couple of simple experiments with different data structures in Python and measured how much memory each of them used versus number of stored objects.

How I got these results: I used Python 2.4.4 (as packaged for current Debian Testing). The test machine is running Linux kernel 2.6.21 (again from Debian Testing) and has 1 GB of RAM. The metric is virtual memory size, as reported by the kernel in /proc/*/status (I used this piece of code)

First I tested dictionaries (or hashes in Perl-speak). The test code simply adds entries to the dictionary one by one and writes out virtual memory size every 1000 iterations. I've made three different tests here: simple integer to integer mapping, string to integer, string to tuple and string to list.

bighash={}
count=0
step=1000

while True:

	for n in xrange(step):
		# bighash[count]=1		#1
		# bighash[str(count)]=1		#2
		# bighash[str(count)]=[1]	#3
		# bighash[str(count)]=(1)	#4

		count+=1


	if count>=10000000:
		sys.exit(0)

	sys.stdout.write("%d\t%f\n"%(count, memory()/1024.0/1024.0))

Results:

The most interesting point here is how inefficient lists are compared to tuples - there is no significant difference when storing an integer in the dictionary or a tuple containing a single integer.

In the second part I compared tuples and lists. For the first test I used append method to add elements to the list on each iteration. For the second test I repeated that with tuples. However because they are immutable I created a new tuple on each iteration with one additional element. The third test is identical to the second except this time it was done with lists (i.e. I treated lists as if they were immutable like tuples).

# biglist=[]	#1 and #3
# bigtuple=()	#2
count=0
step=1000

while True:

	for n in xrange(step):
		# biglist.append(1)		#1
		# bigtuple=bigtuple+(1,)	#2
		# biglist=biglist+[1]		#3

		count+=1


	if count>=100000:
		sys.exit(0)

	sys.stdout.write("%d\t%f\n"%(count, memory()/1024.0/1024.0))

The second and third tests ran so slowly that I only tested sizes from 1 to 100000.

Interesting result here is that tuples do not seem to be significantly more efficient than lists when storing a lot of items (see the right end of the lower graph). However adding another element by creating a new tuple is very inefficient and takes a lot of memory and CPU time (as expected for an immutable data structure).

When the World Wide Web and HTML were designed, a decision was made to try to make web page authoring as easy as possible. That meant that web browsers gracefully accepted all documents, even those that did not strictly conform to the HTML syntax, and tried their best to present them on the screen in the way document authors intended. This was probably one of the key factors of why WWW became so popular - everyone with a text editor and some patience could come up with some tag soup document that would be silently rendered by his web browser without displaying a single error message. However this also became a major problem of the web, because no one wrote standards-compliant HTML and browsers were forced to become more and more complex to cope with all the mistyped garbage that was floating around.

Wikipedia was founded good 10 years after the World Wide Web and it's current engine MediaWiki a year later. At that time the tag soup problem of the web was already well-known. You would think that the founders of Wikipedia would learn from history and would know that giving your users too much freedom in regard to markup syntax will only lead to problems. In reality it seems that exactly the opposite is true.

The syntax behind Wikipedia pages today is so diverse, filled with hacks and workarounds for errors and typos page editors made that the only thing capable of properly rendering a page from Wikipedia is MediaWiki itself. It's wonderfully difficult to use Wikipedia dumps from any other software and for any other purpose than displaying them in the browser. It takes for example a 2000 line Perl script Wikipedia Preprocessor to make sense of the most of the garbage and make information even remotely machine-readable.

Consider for example this comment from Wikiprep:

# The correct form to create a redirect is #REDIRECT [[ link ]],
# and function 'Parse::MediaWikiDump::page->redirect' only supports this form.
# However, it seems that Wikipedia can also tolerate a variety of other forms, such as
# REDIRECT|REDIRECTS|REDIRECTED|REDIRECTION, then an optional ":", optional "to" or optional "=".
# Therefore, we use our own function to handle these cases as well.

What possible reason could there be to allow this kind of flexibility in the markup syntax? The only one I can think of is that some administrator noticed a broken page that for example had a "REDIRECTS" keyword instead instead of "REDIRECT" and instead of fixing that page fixed MediaWiki to support this typo. There are a lot of other cases like this. For example disambiguation pages can be marked with {{disambiguation}}, {{disambig}} or {{dab}} because of those who can't remember the name. Then there is this strange policy of ignoring the case of the first letter in a page title and distinguishing the case of subsequent letters. I can't imagine a good reason for that.

In the end I have a feeling the syntax itself is starting to bite back. With time it got more and more complex. Take for example the source of this Wikipedia template:

<div class="notice metadata" id="disambig">
{|style="background:none"
|style="vertical-align:middle;"|[[Image:Disambig gray.svg|30px]]
|style="vertical-align:middle;"|''This
[[Wikipedia:Disambiguation|disambiguation]] page lists articles about distinct
geographical locations with the same name. If <!-- you are viewing this
online as opposed to as a [[hard copy]] and -->an
[[Special:Whatlinkshere/{{FULLPAGENAME}}|internal link]] led you here, you may
wish to change the link to point directly to the intended article.''
|}</div>
</div><includeonly>[[Category:Ambiguous place
names]]</includeonly><noinclude>[[Category:Disambiguation and
redirection templates|Geodis]]</noinclude>

This neither human nor machine readable and the only thing that can make sense out of it is the MediaWiki with its 100000 lines of PHP code dedicated to interpreting mess like this. Just figuring out what gets included from a template page is complex, full of special cases and exceptions:

# We're storing template text for future inclusion, therefore,
# remove all <noinclude> text and keep all <includeonly> text
# (but eliminate <includeonly> tags per se).
# However, if <onlyinclude> ... </onlyinclude> parts are present,
# then only keep them and discard the rest of the template body.
# This is because using <onlyinclude> on a text fragment is
# equivalent to enclosing it in <includeonly> tags **AND**
# enclosing all the rest of the template body in <noinclude> tags.
# These definitions can easily span several lines, hence the "/s" modifiers.

The very Wiki markup that made Wikipedia accessible to many is now making hard for common people to contribute. If I want to make a new page on Wikipedia today and mess up the markup there is a good chance it will get deleted. It isn't realistic to expect people will read through long, boring pages describing the markup.

How exactly would one solve this problem? I don't know, but I'm sure it won't be easy - most of the pages on the Web still aren't standards-compliant. The difference with Wikipedia is that it is all under the control of WikiMedia Foundation, so in theory it would be possible to try to automatically convert all pages to some saner, more strict markup and manually fix those that failed to convert. However it would require some enormous effort and it would probably turn away a lot of current editors so I don't think it will happen any time soon.

I've put online an incomplete Galaksija ROM disassembly in HTML format (with links to functions and all).

Oh, and z80dasm 1.1.0 is in Debian Unstable now.

There's a lot of Galaksija emulators out there. First there's one for DOS and Windows. Then you have one for ZX Spectrum and now also for SAM Coupé.

So how can you, as a simple user, be sure that you're getting the real 1980s Galaksija experience instead of some emulator of a questionable origin? Well, fear no more: Galaksija genuine advantage software will tell you exactly what kind of machine is behind the display you are looking at:

On a more serious note. It's amazing that Galaksija can be emulated so well on another machine of its class (same CPU with similar clock frequency), but it isn't that hard tell apart emulator from the real thing.

This diagnostic program just looks at properties of different sections of Z80 address space. CNST means that you get consistent values from it, suggesting there is something attached to the bus at that address and MMRY means that it can remember a value that was previously written to it (like RAM for example). Emulators also patch some bytes in ROM, so a check sum is calculated and compared to a known value.

Update: Here's how it looks when it runs on an emulator:

I have a feeling I had this problem at least once before, found the solution and forgot about it. So, here's the whole story hoping I won't forget about this the third time.

The twoside option to the article document class in Latex makes the document suitable for duplex printing (for example by making margins slightly different on odd and even pages, etc.). It's just one of those little things that make Latex documents look really nice when printed. However Latex documentation doesn't mention that it also has one nasty side effect...

It changes page layout from this:

to this:

Why is this you ask? Some grepping through the Latex configuration brings up this little gem (in article.cls):

\if@twoside
\else
\raggedbottom
\fi

Which means that the raggedbottom option is not enabled if the twoside option is enabled. I'm sure a perfectly reasonable explanation exists for this (as it seems to for every other thing in Latex), however to me this kind of layout just looks plain ugly.

The solution is obviously to include a \raggedbottom command at the beginning of the document. This way the page layout you've painstakingly fine tuned doesn't break when you switch from single side to duplex printing.

A few days ago I uploaded version 1.1.0 of z80dasm. Here are a few bits from the changelog:

Rewritten symbol table routines. Replaced old symbol table from dz80 that used statically allocated strings with some more modern code. Better comments in the symbol file regarding where and how a particular symbol is used is a nice side effect of this.

Support for input symbol files. You can now give the disassembler knowledge about known symbol values (constants, function locations, etc.) in the form of a standard Z80 assembler symbol file.

Support for splitting binary file into data and code blocks. Along with the symbol file you can also now give z80dasm a description of data and code sections in the binary file you're working on. It will then write data sections with "defb" or "defw" directives in the assembly file instead of disassembling them.

Here's a short video of all of new demos that are included in the 0.2.0 release of Galaksija development tools:

Chariots of Fire is a short (260 bytes) program for Galaksija that plays a part of "Chariots of Fire" track by Vangelis.

The music it produces resembles some of the more advanced beeper music from Sinclair Spectrum. I was always curious how people were able to reproduce anything else than simple tones on a 1-bit D/A converter and this small program was nice a opportunity to learn about it.

It turns out that the code implements two independently running loops with a slightly different frequency. Each one of them changes the state of the audio output on each iteration (from 1 to 0 or 0 to 1). Result is an oscillator that slowly changes its duty cycle from 0% to 100% and back again. Here's the waveform of one note:

(listen)

The changing duty cycle periodically shifts the signal's energy from lower to higher frequencies and back again. Since the beeper (or whatever is between the audio output and your brain, including your ear) has a limited bandwidth, a lot of the higher frequencies get cut off. This means that the sound gets periodically stronger and weaker, which can be used to produce the illusion that the square wave signal has an envelope added to it.

Compare this with a simple square wave of the same frequency:

(listen)

And here is the same square wave with an added envelope, roughly matching the changing duty cycle:

(listen)

z80dasm was accepted to Debian unstable yesterday.

Dancing Demon was a famous game for Tandy TRS-80 model I written by Leo Christopherson. I found out about it when I was researching the origins of Galaksija's operating system.

It turns out TRS-80 and Galaksija not only have very similar BASIC interpreters but also very similar graphics capabilities (which led me to believe Galaksija's ROM was based on Tandy's ROM, not Microsoft BASIC, but that is another story). To prove that, I ported Dancing Demon to Galaksija:

Of course, the whole program didn't fit into Galaksija's 6 kB of RAM (I believe the TRS-80 model on which the original Dancing Demon ran had 16 kB). I had to strip away the editor and basically everything else except the dancing animation (however you can still edit the dancing routine with BASIC editor in Galaksija's ROM). Melody playback also didn't make it (besides, Galaksija's software video would make that tricky), but I did manage to preserve the clicking sound (played back through Galaksija's cassette port, of course).

Source will be included in the next release of Galaksija development tools.

Here'a a short assembly program (around 180 bytes of code) that demonstrates a small part of Galaksija's considerable graphics abilities :).

Some screenshots (it actually looks quite nice in motion if you're looking from far enough):

Manic Miner was one of the first computer games I played. It was also the first game I tried on my newly repaired Spectrum. Out of curiosity I did some googling around for technical information about this game. It turns out there's plenty floating around the Internet.

I was quite amazed that besides being one of the most popular games on the Spectrum it was also very well designed. The author (Matthew Smith) pushed a lot game's complexity from code into data: there's a pretty simple game engine taking the bottom 12 kB of Spectrum's 48kB RAM. The rest is available for data describing maps, sprites, etc. Within engine's limits you can make your own monster-infested levels simply by manipulating the data structures with no need to modify (or even understand) the engine's machine code. This made it possible for other people to make completely new games (I guess people would call them mods today) using his engine: there are several tens of them listed at World of Spectrum. This was made even simpler by the fact that the original Manic Miner release didn't employ any copy protection schemes or fancy loaders - you could push BREAK after the first part of the game's code loaded and do some simple modifications directly from Spectrum's BASIC, without needing some extra software.

It's also interesting how the engine development progressed over time: With Manic Miner's engine you could load at most 20 levels into Spectrum's memory (in addition to the engine) with each level taking 1024 bytes. It supported conveyor belts, crumbling floors and two types of monsters per level. The next version of the engine (used in the sequel Jet Set Willy) on the other hand supported 60 levels (256 bytes each) and added swinging ropes, stairways, more monsters per level and ability to connect different levels so that the player can freely walk between them instead of just passing from the first to the last level like in Manic Miner.

All this reminds me of for example more recent ID software's games like Doom and Quake. They are also written in much the same way: a compact, simple engine and a larger WAD file, containing data about the levels. Not surprisingly these game engines were also used in a large number of other games.

Here some further technical reading: Jet Set Willy and Manic Miner internals.

If you think C supports some funny syntax, how about this:

HAI
CAN HAS STDIO?
PLZ OPEN FILE "LOLCATS.TXT"?
	AWSUM THX
		VISIBLE FILE
	O NOES
		INVISIBLE "ERROR!"
KTHXBYE

Lolcode is a new Turing-complete language that will probably end up along such legends as Whitespace and Brainfuck. They even have a book cover ready:

Here's the first release of z80dasm, my fork of the dz80 disassembler.

Some basic information about it can be found here. More details in the README file and the included man page.

Enjoy.

I'm getting tired of hunting Z80 assembler and disassembler bugs each time I want to focus on researching Galaksija's operating system.

Today I wanted to squash all those bugs once and for all, so I turned z80asm (a nice Z80 macro assembler) against its bitter rival z80dasm (my soon-to-be-released fork of dz80 Z80 disassembler).

After a long debugging session of z80dasm, I finally got the desired result (interestingly I found no new bugs in z80asm):

$ stress
Final results of stress testing
===============================

Tested: 2000
Failed: 0
$

(In each iteration this script copies 16kB of data from /dev/urandom, disassembles and assembles it and compares the result with the original)

Hruške wrote about how to get IPv6 connectivity in Debian.

A few days ago I found out by accident that there is a simpler way: just install the tspc package (Some web site said to me "you are using IPv6" and I said "Wow. When did I configure that?" then remembered I installed some IPv6-related package a while ago to read its documentation). No configuration necessary and it works from behind a NAT.

It is a different kind of connectivity though (point-to-point tunnel versus 6to4), but it's good enough for just poking around the 128 bit address space and trying out a few pings.

PVM was designed to connect different machines into a cluster over low-latency high-speed LANs. Some applications however do not need good connectivity between cluster nodes in order to work efficiently.

Now imagine you have a four-way Opteron machine at your disposal and the only thing that prevents you from adding it to your virtual machine is the fact that it is 30 km away and the only route to it leads through two firewalls and a block of public Internet.

PVM uses a combination of TCP and UDP connections for communication between nodes so you can't use SSH port forwarding. However there is a way to tunnel any kind of traffic over SSH and make a simple virtual private network using a combination of SSH and PPP daemons (see VPN HOWTO) which will also support PVM traffic.

The complete installation described in the HOW-TO is too complicated for one time use. So here are simple step-by-step instructions:

1. Make sure you can make an SSH connection from master to opteron with a single command and without entering a password (e.g. by using RSA or DSA authentication). To traverse firewalls you can use SSH port forwarding for this connection (since you only need one standard TCP connection from master to opteron to achieve this - in my case it was SSH-over-SSH-over-SSH)
2. Download and install pty-redir on master. It's only 100 lines of code, so it's easy to audit if you're worried about security.
3. Install pppd on both master (the local host that runs the pvm console and controls the cluster) and opteron (the remote host you want to add to the cluster). Pray that both machines have ppp support enabled in kernel.
4. Put the following into /etc/ppp/options on master:

noauth

5. Put the following into /etc/ppp/options on opteron:

ipcp-accept-local
ipcp-accept-remote
proxyarp
noauth

6. Run ./pty-redir /usr/bin/ssh -C -c blowfish -t -e none -o 'Batchmode yes' -i path-to-your-rsa-key opteron-host-name /usr/sbin/pppd on master.
7. Run pppd /dev/ttyp0 192.168.X.1:192.168.X.2 on master (replace /dev/ttyp0 with the device name that is printed by the previous command) Choose X so that these two IPs do not conflict with any other networks master and opteron are connected to. 192.168.X.1 becomes master's IP and 192.168.X.2 becomes opteron's IP in this little VPN.
8. Write a PVM hostfile like this:

192.168.X.1 sp=1000
192.168.X.2 sp=10000
...and any other local machines in your cluster

9. Start PVM on master: pvm -n192.168.X.1 hostfile
10. Enjoy :)

From the README file:

This is a loose collection of tools for use with Galaksija home
microcomputer:

 gtp2wav     - Convert a binary Galaksija tape file to an audio file for
               loading to a Galaksija computer through the sound card.

 bin2gtp     - Encapsulate a Z80 machine code block into a Galaksija tape
               file together with a simple BASIC loader.

 pgm2scr     - Convert a bitmap to a Galaksija video framebuffer.

 chargendump - Inspect and dump characters from a Galaksija character
               generator ROM image.

 include/    - Header files for use with a Z80 assembler that contain useful
               macro definitions for writing assembly programs for
	       Galaksija.

 examples/   - Example assembly programs for Galaksija

Get the tarball here.