Dillo: a eulogy

Posted by HEx 2013-11-26 at 09:44

Dillo has been my web browser of choice for a decade now. This tends to provoke either blank stares or sniggers depending on whether I've previously told whoever I'm talking to about it.1

Dillo is not a browser you would give to Mum and Dad.2 Dillo does not sing and dance and run arbitrary code. Dillo is not Web 2.0. Dillo does not have gradients and rounded corners. Dillo has never heard of HTML5. (Dillo has heard of CSS, but will feign amnesia when asked nicely. Site authors do not know my colour and font preferences better than I do.)

Dillo renders HTML 4.01, and will happily quote the sections of the spec your page is violating. Dillo does not send cookies or Referer headers. Dillo does not claim to be Mozilla only to admit later, in the small print, that that's a lie. Dillo identifies itself as “Dillo”.

Dillo has never once shown me a banner ad. Dillo laughs in the face of pages that plead “refresh me every 30 seconds!”. Dillo never hits the network without permission. Dillo keeps every document ever fetched in memory. (Disk cache? That's what swap is for! And other programs get to use it too!)

Dillo does not run on Microsoft Windows. Dillo requires you to edit configuration files using an actual text editor (remember those?). Dillo is, in short, a browser for purists. It does one thing and does it well. Using Dillo as your sole browser would be pure masochism. But it's lean, it's mean, and it keeps going long after bigger browsers would have keeled over under the weight of all the crap the modern web demands of them.

Sadly, your choice of sites is increasingly limited.3 But a fine test of whether a site is worth visiting is whether it is usable in Dillo. As for me, I rarely browse Wikipedia or search Google or read Hacker News using anything else.

And long may it remain that way.

[1] Of course, nobody has ever heard of Dillo before I tell them about it.

[2] That is, unless you're trying to keep them off the internet.

[3] As a proportion of the sites you might want to visit, that is. I doubt the absolute number of dillo-friendly sites is dwindling. Nonetheless, the day I discovered that Google Groups—an interface to an entirely text-based medium, let's not forget—now required javascript for even minimal functionality is the day I knew the web was doomed.

Ranting: in abeyance

Posted by HEx 2013-11-05 at 00:55

I had a rant planned, but just as I was getting nicely worked up and frothy I happened to read this. And, well, I know when I'm beat.

That is all.

Music reverse-engineering, or, how to pretend that SIDs are mods

Posted by HEx 2013-10-03 at 13:00

One of the goals of the Fooble project is to make music more hacker-friendly; in particular, to expose the internal workings of music whose construction was previously opaque.

The most common way for music to be distributed is as recordings. But reverse-engineering music from a recording is hard. (It's hard for humans. Getting machines to do it is even harder.) Luckily, there are many music formats intermediate in structure between a raw waveform (which is non-trivial to extract information from) and human-editable formats such as Protracker and MIDI (which already have all the information present in a usable form).

One obvious example is the Commodore 64's SID format. As a file format, SID long postdates the C64 itself. It consists of a header followed by 6502 machine code: when executed in the correct environment, this code writes to the memory-mapped I/O registers that control the SID chip itself. Can we turn this into something resembling readable pattern data? Presumably the patterns are stored in the code somehow. But many different playroutines have been written over the years, and given the activity of the C64 demoscene it seems likely that new ones will continue to be written.1 The only reliable way to recover the information we seek is to treat the code as a black box: execute it, watch what it does, and reconstruct what we can.2

So essentially we are faced with a compression problem. We have a large (indeed, potentially infinite) stream of data, of very low entropy, which we would like to turn into a smaller amount of high-entropy data (patterns, instruments, maybe samples). The problems we face are many. There is no indication where pattern boundaries should lie, or how long the tune is. But happily, the SID offers hardware ADSR volume envelopes: if a tune takes advantage of this we can at least identify where notes begin.

Enough waffling. Demo time!

(Enterprising readers with a copy of HVSC should have little problem figuring out how to try their favourite tunes.)

The current code lacks many niceties. No cycle counting is done. The CPU is assumed to be infinitely fast, thus events occur precisely at interrupts. Tunes are assumed to set the interrupt frequency only at initialization time: this sets the tempo for whole tune. Only PSIDs are loaded. A trivial environment is provided that doesn't resemble the C64 much at all. (Many of these problems can be solved at a stroke by using a real C64 emulator. Happily, a javascript port of VICE already exists.)

Also, because modplayjs is currently completely sample-based, much of the SID chip is unemulated. In particular, no filters or ringmod. Variable pulse width is done ickily, by switching between samples. There may be envelope bugs. The problem of finding pattern boundaries has yet to be tackled.

Still, there is good news. Most SIDs play recognizably. Many play reasonably well, modulo the lack of filters. And some simple SIDs have extracted pattern data that resembles what a human would produce. To the best of my knowledge, this is not an approach that anyone has tried before. But as far as I'm concerned, it's certainly a step in the right direction.

[1] It also seems likely that demosceners' playroutines will continue to tend towards the completely undecipherable. Yes, that is 373 bytes of code. (And no, it doesn't render well in modplayjs. Yet.)

[2] That's not to say we can't peek at the code. But it won't necessarily yield good results. In particular, one not-quite-black-box technique I've had only limited success with is to detect looping of the tune by checksumming the state of the emulated machine at each frame. Since the state completely determines future states, matching checksums means a guaranteed loop. This can even be done in constant space.

Fifteen dissection part one: Audio in a browser

Posted by HEx 2013-09-27 at 21:44

[Part zero is here].

Phase 1 of making a music demo in javascript is to work out how to play js-generated PCM audio in a browser. There are two widely available APIs for synthesizing audio in real time, namely the Firefox-specific MozAudio and the much more heavyweight Web Audio (Chrome, Safari). Opera supports neither. Even neglecting Opera, supporting both would require separate code for each, which is a Really Bad Idea when the space constraints are this tight.1

So real time is out. It's possible to put a base64-encoded WAV in a data: URI and pass that to an audio element. This has been fairly widely exploited by this point, and works just about everywhere. http://js1k.com/2013-spring/demo/1388 is a good example of this at work. Neglecting the quantization noise that comes from using 8-bit samples, the main problem here is that notes are triggered using setInterval, which is not a precise timing method, and at least on my setup it sounds very juddery.

Which leaves the final option: generating the entire tune as a single WAV. This has its own problems: there's a delay at startup while megabytes of data are precalculated, the tune can't loop indefinitely (unless you use setInterval again, and that won't be seamless), and memory usage for storing the data: URI is quite high. (Some browsers (*cough* IE) place restrictions on the size of data: URIs too.) Still, it's the best we can do.

I settled on mono 16-bit 32kHz audio for a data rate of 64KiB/sec. (8-bit audio sounds terrible; see above.) Delightfully, browsers offer the ancient and arcane btoa() method for base64 encoding, which at 6 bytes can't be beat. Then new Audio('data:audio/wav;base64,"+btoa(header+pcmdata)).play(); will make noises. The data chunk is built up by iterating the following a few million times (z is a number in the range -32768..32767; the bitwise ops force integer conversion): pcmdata += String.fromCharCode(z&255,(z>>8)&255);2

Here is the WAV header:

00000000  52 49 46 46 24 00 00 01  57 41 56 45 66 6d 74 20  |RIFF$...WAVEfmt |
00000010  10 00 00 00 01 00 01 00  00 7d 00 00 00 00 00 00  |.........}......|
00000020  02 00 10 00 64 61 74 61  3a 61 75 64              |....data:aud    |

To save space the header is stored as a raw string rather than base64-encoded, so we can't use any byte values greater than 0x7f as UTF-8 bloat would more than offset any gains from avoiding base64. Hence 32kHz (0x7d00), which is the highest common rate that is less than 32768. The lengths 0x01000024 and 0x01000000 are simply "sufficiently large" and wildly inaccurate. Similarly the four bytes after "data" are the data length, but since browsers don't check this, we reuse part of the "data:audio/wav" string to increase compression. (It's just as well there's no space to include an <audio> element as the seek bar would get very confused.)

Finally, I discovered at the last minute that submitting entries containing null bytes doesn't work. Sadly there was no time to do anything other than replace them with \0.

Next up: the calculation of those few million z values.

[1] Good news! In the six months since the contest ended, both Firefox and Opera are now shipping with Web Audio. So things will be different next year.

[2] String.fromCharCode? That's 19 bytes. Nineteen! For shame, javascript, for shame. Perl manages with three, and the parens are optional.

SSL (mis)adventures

Posted by HEx 2013-09-27 at 15:11

So I've been meaning to set up SSL on here for a while now—the web being unencrypted by default these days is just silly—and reading this gave me the impetus to give it a try. ($0, you say? Under an hour, you say? Sounds good to me!) My experiences were... frustrating.

Step 1: Register with StartSSL. After I grudgingly gave them all my personal information, I was provided with a client certificate, which my browser (Chromium) promptly rejected. "The server returned an invalid client certificate. Error 502 (net::ERR_NO_PRIVATE_KEY_FOR_CERT)". The end.

Since the auth token they emailed me only worked once, I couldn't try using another browser. So, unsure what to do (and thinking they might appreciate knowing about problems people have using their site, so they can fix them or work around them or even just document them), I fired off an email.

The response I got was less than helpful: "I suggest to simply register again with a Firefox. Make sure that there are no extensions in Firefox that might interfere with the client certificate generation." Gee thanks, I would never have thought of that. And nope, I can't register in Firefox, my email address already has an account associated with it. Perhaps naïvely, I thought StartSSL might frown on people creating multiple accounts (or might like to take the opportunity to purge accounts that will never be used because their owners can't access them), which was why I didn't just create a second account using a different address in the first place. Still, lesson learned, second account created, no problems this time round. Bug fixed for the next person to come along? Not so much.

Step 2: Validate my domain. Going into this I was thinking "Hmm, will I need to set up a mail server and MX record so I can prove I can receive mail at my domain? Will the email address WHOIS has suffice? What address does WHOIS have, anyway?"

This was premature. Apparently the domain chronosempire.org.uk is blacklisted. Sadness. Not having any clue why, I fired off another email. Turns out it's Google. Google blacklisted me, claiming "Part of this site was listed for suspicious activity 9 time(s) over the past 90 days."

Nine times? WTF, Google?

The reply continued: "Unfortunately we can't take the risks if such a listing appears in the Class 1 level which is mostly automated. We could however validate your domain manually in the Class 2 level if you wish to do so.". I am confused as to what risks there are to StartSSL (I thought they were only verifying my ownership of the domain, which I'm pretty sure is not in doubt), and how those risks would go away if I paid them more than $0 for a Class 2 cert.1

Still, StartSSL is just the messenger here. Google recommends I use Webmaster Tools to find out more, so I dig out my rarely-used Google account, get given an HTML file to put in my wwwroot, let Google verify I've done so, and finally I find out what this is about.

I have a copy of Kazaa Lite in my (publicly-indexed) tmp directory. Apparently some time around June 2004 I needed to send it to someone, and it's been there ever since.2 This should not come as any surprise to anyone who knows of my involvement in giFT-FastTrack, but more to the point, Kazaa Lite is not malware. Not only is it not malware, it not being malware is the entire reason for Kazaa Lite's existence.

Sadly, whether it is or is not malware is irrelevant. "Google has detected harmful code on your site and will display a warning to users when they attempt to visit your pages from Google search results." Nice. So now I have to refrain from putting random executables in my tmp dir in case they make Google hate me? (Total hits for the file in question over the past few months: 14. Hits that weren't Googlebot: zero. In fact, I'm pretty sure not a single actual human has fetched it in the past, say, five years.)

Anyway. A quick dose of pragmatism and chmod later and my site is squeaky-clean! Now I guess I have to wait 90 days for Google to concur. Which is perhaps just as well, as I've already spent substantially more than an hour on this, I've not even started configuring my web server or making a CSR, and my enthusiasm is as low as the number of people desperate for my copy of Kazaa Lite.

[1] Maybe I'm being overly cynical here and they would actually use the money to check... something? What? I have no idea.

[2] I firmly believe in not breaking URLs unnecessarily. That's my story and I'm sticking to it. It has nothing whatsoever to do with me never cleaning up my filesystem.

Fifteen dissection part zero: History

Posted by HEx 2013-04-14 at 15:58

This is part zero of a dissection of my recent JS1K submission Fifteen, a 1K javascript audio demo. In this part: history of the tune.

In August 2004 I wrote an unnamed tune using soundtracker. It got the temporary name "f", because it's in 15/8 time and 15 is 0xf in hex. As was my custom, snapshots got an incrementing version number stuck on the end, and the "final" version was called f4.xm. I never got round to properly naming or distributing it, but it seemed well received by the few friends I showed it to.

Here's the original xm (or rendered in-browser for your convenience).

Fast forward four years to July 2008. My friend Kinetic had just started serious hacking on a project he'd had in mind for a long while, namely modding the Amiga game Lemmings with new levels, graphics and music. Since he liked my tune, I set myself the challenge of squeezing it into the constraints that would allow playback within the game.

Lemmings has a particularly unsophisticated playroutine. Its capabilities are a tiny subset of those of Protracker: the only supported effect is "set volume", although an initial speed can be set. Only three channels are available as the fourth is reserved for sound effects; maximum 15 samples per tune, and no finetunes. In addition, the entire tune had to fit into 47000 bytes―the game ran on a 512K Amiga so memory was tight. Nonetheless, to my (and Kinetic's!) surprise and delight, I succeeded in making something that sounded very much like the original 8-channel tune.

Here's the 3-channel version (browser).1

And here's a video of it playing in Lemmings.

Fast forward another four years. So JS1K came round and I'd been musing over the idea of submitting something audio-related. Since rule number one of optimization is to have a stable starting point, I needed a tune already written. After my previous success, f4.xm seemed worth trying, although I was under no illusions that it would survive such a drastic excision unscathed.

Next up: so how do you squeeze something like this into 1K?

[1] Alert readers might spot that this file is larger than 47000 bytes. The game's internal file format stored a stream of three-byte (note, sample, volume) tuples with RLE of empty events, making the pattern data smaller than Protracker's encoding. Samples were of course uncompressed to allow Paula to suck them directly out of RAM.

WebDAV and the HTTP PATCH nightmare

Posted by HEx 2012-11-21 at 22:04

HTTP 1.1 defines a way of retrieving part of a file1, namely the Content-Range header (plus Accept-Ranges and the 206 status code). This was widely implemented by web servers and is now ubiquitous, meaning that clients can resume partial downloads and/or seek in remote files (think video) with impunity. HTTP 1.1 also introduced the PUT method to create and update files, which was later used in WebDAV.

Clients might want to do partial updates for much the same reasons they want to perform partial retrieval: because network connections might die part way through big requests.2 The obvious way to perform partial updates is to send a PUT request with a Content-Range header, and indeed Apache supports such requests and behaves as expected.3

This seemed so clear and straightforward a solution to me that, when implementing a WebDAV client, I tried this idea before even reading the spec, was gratified that it worked on my test Apache server, and called it “done”.

Sadly, there's a snag.4 HTTP 1.1 defined PUT as being “idempotent”, which is allegedly incompatible with partial updates. RFC 5789, thirteen years after HTTP 1.1, decided to address this with the HTTP PATCH method.  It says:

“The PUT method is already defined to overwrite a resource with a complete new body, and cannot be reused to do partial changes. Otherwise, proxies and caches, and even clients and servers, may get confused as to the result of the operation.”

OK, let's assume for the minute that this is true, and this RFC is an earnest attempt to solve the problem.

RFC 5789 documents a way of sending “patch” requests to existing files. It allows multiple patch formats, and documents how to enumerate the list of formats, but—and this boggles my mind—does not document, or even hint at, any examples of such formats.5 Indeed, nowhere does such a list exist. Again from the RFC:

“Further, it is expected that different patch document formats will be appropriate for different types of resources and that no single format will be appropriate for all types of resources.  Therefore, there is no single default patch document format that implementations are required to support.”

Why, why would they do this?  It's HTML5 <video> all over again.

Unsurprisingly, given such an underspecified standard (yes, RFC 5789 is Standards Track!), no WebDAV servers have bothered to implement it.

Actually, that's not quite true. SabreDAV is making a valiant attempt. Since there's not enough information in the standard to actually implement,  PartialUpdate defines a SabreDAV-specific patch format with the same functionality that Apache has supported for PUT with Content-Range for the past twelve years, namely updating a simple byte range.

How many clients support this SabreDAV-specific behaviour?  To the best of my (and google's) knowledge: none.

But is PATCH even solving a real problem? RFC 2616 has the following to say about PUT requests:

“The recipient of the entity MUST NOT ignore any Content-* (e.g. Content-Range) headers that it does not understand or implement and MUST return a 501 (Not Implemented) response in such cases.”

To me, this reads as “Content-Range is just fine for PUT requests, but if you don't implement it, make sure you throw an error instead of silently ignoring it”.  For this to actually mean “you MUST return 501 if the request contains a Content-Range that is not the entire file” seems perverse. The possibility exists that the authors of RFC 2616 overlooked something in their implicit approval of Content-Range for PUT requests, but I have my doubts.

As for idempotence: it is true that PUT requests are defined as being idempotent, and thus proxies, caches, clients and servers are allowed to optimize accordingly. But partial PUT requests are idempotent! Writing part of a file more than once has precisely the same effect as writing it once.

Multiple partial PUT requests for different parts of a file may of course not be idempotent (depending on whether the ranges overlap), but this isn't a problem! Multiple differing complete PUT requests are not idempotent either, indeed, HTTP 1.1 explicitly states that “it is possible that a sequence of several requests is non-idempotent, even if all of the methods executed in that sequence are idempotent”.

Where I think the confusion lies is the notion that the state of a file after a (successful) PUT request is completely specified by the request, and does not rely on the previous file contents. Nowhere that I have found has this been claimed, so presumably any software that assumes it to be true can expect nasal demons.

I do not know whether such broken software exists. It might do. Nonetheless, I cannot think of a single case where, given the assumptions in HTTP 1.1, partial PUT requests might cause a problem. Clearly the authors of Apache considered it sufficiently non-problematic to support them. lighttpd supports them too. Whether other WebDAV servers that declined to did so because of fear of misbehaviour or because they considered resumable uploads a corner case too obscure to be worthwhile implementing is anyone's guess (though if it's the latter I will happily denounce them for skimping).

That I can't think of any possibilities for badness doesn't mean they don't exist, but examples would go a long way to making me a believer. Meanwhile I can't help but wonder what the authors of RFC 5789 (which, as a standard, “represents the consensus of the IETF community”) considered so worrying, and why they proposed such a baroque non-solution to a seeming non-problem.

So where do things stand if you want resumable uploads over WebDAV?

  • If your WebDAV server is Apache (or lighttpd!): use PUT with Content-Range, and ignore what RFC 5789 says about this being forbidden.
  • If your WebDAV server is a recent SabreDAV: use PATCH with a SabreDAV-specific Content-Type.
  • If your WebDAV server is anything else (nginx, IIS, ...) you're probably out of luck.

And this is why we still don't have a sane standards-based network filesystem.

[1] For the pedants: yes, the things that an HTTP server serves up needn't be files, and indeed the official terminology is “entity” or “resource”.  But I'm going to call them “files” for simplicity, in deference to the 99% of the time that this is the case.

[2] There are other reasons, of course.  But this is the biggie.

[3] WebDAV code first appeared in Apache's repository in June 2000, with this functionality already present. See here, around line 1120.

[4] You saw that one coming, right?

[5] Well. “The determination of what constitutes a successful PATCH can vary depending on the patch document and the type of resource(s) being modified.  For example, the common 'diff' utility can generate a patch document that applies to multiple files in a directory hierarchy.”—wait, so web servers are supposed to understand diffs? Diffs that apply to multiple files? Talk about scope creep!