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 + 0x00+0xc5+0x00+0x5c+0x6d = 0x18f and 5 + 5*0x00 + 4*0xc5 + 3*0x00 + 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.

About these ads

13 Responses to “A use for uncompressed PNGs”

  1. Tony Finch Says:

    Um, 05 00 is 5 in little-endian order.

  2. drj11 Says:

    Durr… of course, yes. Fixed now, ta.

  3. Gareth Rees Says:

    You’re missing a </dl>.

  4. drj11 Says:

    I refer you to my previous statement.

  5. Gareth Rees Says:

    It would be nice if there were some easier way to pass image data from JavaScript to the browser. Perhaps an image format like TGA, which needs neither compression nor checksums? Safari supports TGA, but I’m not sure about other browsers.

  6. drj11 Says:

    Targa looks quite promising in terms of simplicity, good suggestion. Sadly, whilst Safari supports it, the other browser does not (it offers to save to disk a .tga file I wrote with Preview).

    OS/2 BMP is tolerable for 24-bit RGB images, and I have most of the code to provide a sane interface to that. This “uncompressed PNG” format isn’t too bad now that I’ve done the checksum code, and using one uncompressed deflate block per scanline will give me the (k*y + x) computation for going from pixel co-ordinate to address. The checksums only need to check-out when I transfer the image to the browser so a series of edits can delay computing the checksum until the end. That doesn’t help BME which (when editing bitmaps with an alpha channel) will need an O(n) pass over the entire image data for every visible user edit.

  7. drj11 Says:

    APS14 suggests a way to incrementally compute the checksum which I intend to write about in another post.

  8. drj11 Says:

    On Targas, the pamtotga documentation has the following amusing thing to say: “It is unclear that anything except pamtotga knows about TGAs with transparency”

  9. Gareth Rees Says:

    What a libel on the entire video game industry!

  10. drj11 Says:

    You mean you use TGAs with alpha in video games production? What tools and specs do you typically use? When I looked a few weeks ago I couldn’t find a Targa spec that mentioned alpha, although it was reasonably clear what the file format would be if you wanted to add that channel.

    OS X Preview knows what to do with TGAs with transparency too.

    • Gareth Rees Says:

      Sorry, I didn’t see your question at the time. (I always forget to tick the “Notify me of follow-up comments” box.)

      Anyway, we create and edit TGA images with alpha channels using Photoshop and Paintshop Pro. We have our own tools that can write TGAs and read (a subset of) them. There are also proprietary tools that read TGAs that form parts of toolchains distributed by the console vendors.

      Basically you set the pixel size to 32 bits and write your texture data as bytes in the order BGRA. The TGA 1.0 spec calls the fourth byte the “attribute” byte, so maybe storing alpha in there is, strictly speaking, an abuse of the format. Nonetheless, it works.

  11. Johnny Rocco Says:

    You talk about “the little endian bit string 1 00 00000″. The endianness doesn’t matter here because all modern memory is going to be byte addressable.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: