Archive for November, 2007

« Older posts

That 80′s feeling

2007-11-23

There should be a name for that feeling you get when moving house and you discover yet another forgotten microcomputer from the 1980′s. ZX81… BBC B… Commodore 64… BBC Master… Hey a SPARCstation 2! Isn’t that from the 90′s?

Oh look, another Model B.

Posted in computing | 1 Comment »

A use for uncompressed PNGs

2007-11-20

A new feature of Curly Logo is the SETTBG command to Set Text BackGround colour. settbg "#850c sets the background to be a nearly fully opaque brown. Note that you can set the alpha (opacity) channel. As I mention in an earlier article the background for this (XHTML) div element is a 1×1 PNG. In order to implement SETTBG I have to create a 1×1 PNG containing an arbitrary 4-channel colour value, in JavaScript.

Gareth Rees wrote a very useful post on making very small PNGs that does most of the work of showing which bits should go where in a PNG file. Unfortunately the IDAT chunk in a PNG file is required to be compressed with zlib/deflate. That means I have to take my 32-bits of data (RGBA), prepend a 0 octet (for PNG’s scanline filter) then compress those 5 octets into zlib format.

I haven’t written a fully general zlib encoder in JavaScript, so what I do is use the feature of the deflate format that allows uncompressed blocks.

Let’s say my pixel has colour value #c5005c6d (that’s in RGBA order). My PNG scanline requires a 00 to be prepended, so I need to zlib encode the 5 octets 00 c5 00 5c 6d. Here’s what the encoded zlib data looks like:

78 9c 01 05 00 fa ff 00 c5 00 5c 6d 04 3e 01 8f

Which breaks down like this:

78 9c
zlib header.
01
the little endian bit string 1 00 00000. 1 indicating the final block, 00 indicating a non-compressed block, and 00000 are 5 bits of padding to align the start of a block to on octet (which is required for non-compressed blocks, and very convenient for me).
05 00 fa ff
The number of octets of data in the uncompressed block (5). Stored as a little-endian 16-bit integer followed by its 1′s complement (!).
00 c5 00 5c 6d
The scanline data stored as plain octets.
04 3e 01 8f
The zlib Adler checksum. Observe that 1 + 0×00+0xc5+0×00+0x5c+0x6d = 0x18f and 5 + 5*0×00 + 4*0xc5 + 3*0×00 + 2*0x5c + 1*0x6d = 0x43e.

In the same style as Gareth’s Python here’s some JavaScript:

  // Create a PNG chunk.  Supply type and data, length and CRC are
  // computed.
  chunk: function(type, data) {
    return be32(data.length) + type + data +
        be32(this.crc(type + data))
  },

  // Create binary data for a 1x1 4-channel PNG.  The colour is specified
  // by the number n: 0xRRGGBBAA
  unit: function(n) {
    var d = '\x00' + be32(n) // PNG scanline data.
    return '\x89PNG\r\n\x1A\n' +
      this.chunk('IHDR', be32(1) + be32(1) + '\x08\x06\x00\x00\x00') +
      this.chunk('IDAT',
          '\x78\x9c\x01\x05\x00\xfa\xff' + d + be32(this.adler32(d))) +
      this.chunk('IEND', '')
  }

These fragments are embedded inside an object, hence the object literal syntax to declare the functions and the use of this to refer to other functions defined alongside. be32 is a function to encode an integer in 4 octet (32-bit) big-endian format.

JavaScript bit twiddling

Getting all this data correctly inside a PNG requires two checksum algorithms: Zlib format uses a simple Adler checksum (at the end, see above); PNG uses a conventional 32-bit polynomial residue checksum for each of its chunks. I had to implement both of those in JavaScript.

JavaScript is actually a pretty nice language for bit-twiddling. Sure the performance is bound to suck but that’s a feature of the implementations not the language itself. Not that I actually measured the performance, but I Just Know. In any case performance is not an issue for encoding this trivial amount of data. JavaScript has all of C’s bit-twiddling operators, and it has a bonus feature that C doesn’t have: 32-bit operation guaranteed. Generally the way that an operator like «x ^ y» works in JavaScript is that both x and y are converted to 32-bit signed integers then the operation is performed as if on 32-bit signed integers and the result is converted to a JavaScript number (which is an IEEE double). In C you might have to worry about those 36-bit or 64-bit architectures that have “funny” widths for their types. Not in JavaScript.

Here’s the CRC code in C from the PNG Spec Annex D:

unsigned long update_crc(unsigned long crc, unsigned char *buf,
                             int len)
{
  unsigned long c = crc;
  int n;

  for (n = 0; n < len; n++) {
    c = crc_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);
  }
  return c;
}

Here’s my JavaScript version:

  crc32: function(buf, crc) {
    if(crc === undefined) {
      crc = 0xffffffff
    }
    var i
    for(i=0; i<buf.length; ++i) {
      crc = this.crctable[(crc^buf.charCodeAt(i)) & 0xff] ^ (crc >>> 8)
    }
    return crc
  },

The core code inside the “for” loop has hardly changed. Instead of «buf[i]» I have to write «buf.charCodeAt(i)»; JavaScript doesn’t have a character type so conversions from characters to their internal representation are more explicit. Note that in JavaScript the shift is «crc >>> 8». JavaScript doesn’t distinguish signed and unsigned integers (or indeed integers and floats) so it can’t tell which sort of shift is required by inspecting crc. Like Java JavaScript has two right shift operators, «>>» for preserving the sign bit, and «>>>» for clearing the sign bit. Using the wrong one was a bug in an earlier implementation of mine.

Posted in ecmascript, graphics, javascript, PNG, programming | 11 Comments »

The trouble with matrix multiplication

2007-11-19

is that it’s not commutative. That means that when the SVG spec says in the documentation for the multiply method in the SVGMatrix DOM “this matrix is post-multiplied by another matrix” it really does matter which way round you do the multiplication of the two matrices.

In the call «A.multiply(B)», A is this and should be post-multiplied by B. In the usual mathematical convention the result should be AB.

Safari computes BA, Firefox computes AB. Oopsy.

This is a confusing area; when I was first getting the turtle motion in Curly Logo going (on Firefox initially) I remember a bit where the turtle’s motion was wrong, and I realised that I had some matrix multiplication the wrong way round. Happens all the time regardless of how much thinking I do beforehand about which way round matrices ought to be multiplied, so I thought nothing of it and simply swopped my arguments. As I was writing the first draft of this article I thought Firefox had it wrong and Safari had it right, turns out that’s not right, it’s the other way round.

Regardless of who is right, anyone wanting to use the routine has to do something to work around it.

So here’s what I do. I perform a trial matrix multiplication using SVGMatrix.multiply and determine whether the multiplication was performed the correct way round or the wrong way round.

Consider the matrices L, a flip, and R, a projection:

L = \begin{pmatrix}0&1&0\cr 1&0&0\cr 0&0&1\end{pmatrix}, R = \begin{pmatrix}0&0&1\cr 0&0&0\cr 0&0&1\end{pmatrix}

LR, that is «L.multiply(R)» as it should be:

LR = \begin{pmatrix}0&0&0\cr 0&0&1\cr 0&0&1\end{pmatrix}

What happens if the implementation swops its arguments:

RL = \begin{pmatrix}0&0&1\cr 0&0&0\cr 0&0&1\end{pmatrix}

In JavaScript (well, SVG DOM really) the entries of a matrix are assigned to properties like this:

\begin{pmatrix}a&c&e\cr b&d&f\cr 0&0&1\end{pmatrix}

Note that the two result matrices (above) only differ in their e and f entries. Specifically when «L.multiply(R)» is computed correctly (following the specification) the result’s e property is 0; when computed with the matrices swopped (incorrectly) the result’s e property is 1. How convenient.

Here is some JavaScript to detect if SVGMatrix.multiply is wrong:

matmulwrong = function() {
  var g = document.createElementNS('http://www.w3.org/2000/svg', 'g')
  g.setAttribute('transform',
    'matrix(0 1 1 0 0 0) translate(1 0)')
  var l = g.transform.baseVal.getItem(0).matrix
  var r = g.transform.baseVal.getItem(1).matrix
  return l.multiply(r).e
}

There is a lot of faffing around creating a pointless g element just so I can attach two matrices to it. That really was the most convenient way I found to create two matrices.

We can use matmulwrong to select one of two definitions for our own matmul function to multiply two matrices:

// matmul(A, B) computes AB
matmul = matmulwrong() ?
    function(a, b) { return b.multiply(a) } :
    function(a, b) { return a.multiply(b) }

Now we should only use matmul and avoid using SVGMatrix.multiply. Defining it like this means we decide once, when the JavaScript is loaded, and not every time that we call matmul. Notice how this simply tests whether SVGMatrix.multiply is swopped or not and acts accordingly; it doesn’t care whether you’re using Safari or Firefox, it’s more in the spirit of object detection, not browser sniffing. As soon as bug 16062 gets fixed in FirefoxSafari the code will detect it as being fixed. Life is good again and Curly Logo works on both browsers.

PS: Opera agrees with Firefox.
PPS: Guess which WordPress feature I used today that I thought I’d never find a genuine use for.

Posted in ecmascript, javascript, maths, programming | 13 Comments »

JavaScript: Bitmap Editing

2007-11-16

Following on from my discovery of RFC 2397 I realised that we would be able to manipulate the “src” property of the “img” element in JavaScript and thereby change the image being displayed. The Base64 encoding is conveniently handled by JavaScript’s (non-standard but ubiquitous in the browser) btoa function (2008-05-10: ubiquitous apart from Opera, that is). I chose OS/2′s BMP image file format as being suitably simple to manipulate.

The result is BME (BitMap Editor). Note that all the work is done by client-side JavaScript, there’s no server side programming or communication at all (that would be madness!).

Bi-level any-colour-you-like-as-long-as-it’s-grey-and-blue at the moment. I suggest you right-click to save.

This use of RFC 2397 shows up some bugs and misfeatures of the OS X user interface. For example, dragging the image onto Mail.app opens a new mail message containing the contents of the URL as text rather than an image.

Posted in ecmascript, graphics, javascript, programming, web | 5 Comments »

Using the RFC 2397 “data” URL scheme to micro-optimise small images

2007-11-14

Curly Logo has a text area with a transparent background (maybe you haven’t noticed, but you can move the turtle “underneath” the purple text area and it is still visible, try «bk 333»). Support for colours with alpha channels (a CSS3 feature) was limited when I tried, so I ended up implementing this using a transparent 1×1 PNG which is repeated across the background.

That PNG file is 95 octets big. That’s no big deal, but the HTTP 1.1 headers that are transmitted before the file are about 400 octets. I’m paying to transmit the headers to you, and it takes time. Receiving the header takes 4 times as long as transmitting the file. Time is Money. [edit: 2007-11-16 I do pay to transmit headers, I was wrong when I said I didn't.]

If I could somehow bundle the PNG file inside the only file that uses it (it’s used in a CSS background-image property in an XHTML file) then you could avoid downloading the extra header. Win! This would be a win even if the bundled PNG was slightly larger. Even if the overall transmitted octet count was a bit higher it would probably be a win in elapsed time because we avoid having to do another HTTP round trip for the extra file (and on some browsers that might mean another TCP/IP connexion, so we save all that too). It turns out we can bundle the PNG file inside the CSS.

We use the apparently obscure “data” URL scheme from RFC 2397. It works by having URLs like this:

data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAGAAAABgAQMAAADYVuV7AAAABlBMVEUAAAD///+l2Z/dAAAAIUlEQVQ4jWP4DwMMQDDKIZHDAAGjnFEO7TkMcDDKIZYDAAVlPd9Ahj+EAAAAAElFTkSuQmCC

(this example is actually a graphic from my earlier article on anti-aliasing, paste it into the location field of a browser to try it out)

“image/png” is optional but defaults to “text/plain” so you probably need to specify it for almost any practical application.

“;base64″ is also optional but if you don’t use it then you need to use the standard %xx URL encoding for non-ASCII octets. For binary data it’s probably saner to use “;base64″. Conceivably there might be binary files for which it was shorter to not use “;base64″.

The comma, “,”, is not optional.

So my CSS changes from:

background-image: url(ts.png);

to

background-image: url(data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEXFAFxSw3SuAAAAAXRSTlNu6uyUOQAAAApJREFUCJljYAAAAAIAAfRxZKYAAAAASUVORK5CYII=);

Once I’ve gzip’d everything (which I used to not do, but is a big win for XML and JavaScript) I end up with an extra 19 octets. Which I pay for to store and transmit. So I’m 19 octets worse off, but you guys lose an entire header so you’re well over 300 octets better off plus an entire round-trip. How good is that?

Naturally RFC 2397 is implemented in Safari (3.0.3), Firefox, and Opera.

Now looking at the Base64 encoded version of the 1×1 PNG I can see that the PNG file is mostly overhead. Maybe I can get rid of some of those obviously unused header fields or chunks? Maybe there is some other image file format that would have less overhead for very tiny images (must be able to store at least 1 pixel to 8-bit precision for each of 4 channels). It’s 1-pixel GIFs all over again. Sorry.

Appendix – The Script

Happily uuencode turns out to support Base64 (on OS X and Single Unix Specification).

(includes bugfix!)

#!/bin/sh
# $Id: //depot/prj/logoscript/master/code/dataurl#1 $
# Convert anything to a data URL.
# See http://www.ietf.org/rfc/rfc2397.txt
# Base64 is always used.
# dataurl [filename [mimetype]]

m="$2"
if test "$1" != "" && test "$2" == ""
then
  case "x$1" in
  *.png) m=image/png;;
  *.gif) m=image/gif;;
  esac
fi

if test "$1" = ""
then
  uuencode -m foo
else
  uuencode -m "$1" foo
fi |
   { echo data:"${m};base64," ; sed '1d;$d;' ; } | tr -d '
'

Posted in /bin/sh, web | 15 Comments »

« Older posts
Follow

Get every new post delivered to your Inbox.