[Top] [Prev] [Next]

image - external format for images


An image is a rectangular array of pixels.

There are two formats for storing Inferno images in files. The simpler but deprecated format is identical with the bitmap file format used in Plan 9. The other is a compressed format for more efficient storage and transmission.

The function Display.readimage will handle either format implicitly; however, the Display.writeimage function produces only the compressed form. See display - connection to draw device in Chapter 11.

Uncompressed Format

An uncompressed image file starts with 5 decimal strings: ldepth, r.min.x, r.min.y, r.max.x, and r.max.y. Each number is right-justified and blank padded in 11 characters, followed by a blank.

The number of bits in the image's pixels is 1<<ldepth.

The x coordinates of the rectangle range from r.min.x to r.max.x-1, left to right; y coordinates range from r.min.y to r.max.y-1, top to bottom.

The rest of the file contains the r.max.y-r.min.y rows of pixel data. A row consists of the byte containing pixel r.min.x and all the bytes up to and including the byte containing pixel r.max.x-1.

A pixel with x-coordinate = x in an image with ldepth = ld will appear as contiguous bits in a byte, with the pixel's high order bit starting at the byte's bit number , where bits within a byte are numbered 0 to 7 from the high order to the low order bit.

Compressed Format

A compressed image file begins with the 11 bytes 'compressed\n', immediately followed by 5 decimal strings giving the image's ldepth and rectangle, as above. The rest of the file is a string of compression blocks, each encoding a number of rows of the image's pixel data.

Compression blocks are at most 6024 bytes long, so that they fit comfortably in a single Styx message. Since a compression block must encode a whole number of rows, there is a limit (about 5825 bytes) to the width of images that may be encoded. Most wide images are in subfonts, which, at 1 bit per pixel (the usual case for fonts), can be 46600 pixels wide.

A compression block begins with two decimal strings of twelve bytes each. The first number is one more than the y coordinate of the last row in the block. The second is the number of bytes of compressed data in the block, not including the two decimal strings. This number must not be larger than 6000.

Pixels are encoded using a version of Lempel & Ziv's sliding window scheme LZ77.

The compression block is a string of variable-length code words encoding substrings of the pixel data. A code word either gives the substring directly or indicates that it is a copy of data occurring previously in the pixel stream.

In a code word where the first byte has the high-order bit set, the rest of the byte indicates the length of a substring encoded directly. Values from 0 to 127 encode lengths from 1 to 128 bytes. Subsequent bytes are the literal pixel data.

If the high-order bit is zero, the next 5 bits encode the length of a substring copied from previous pixels. Values from 0 to 31 encode lengths from 3 to 34 bytes. The bottom two bits of the first byte and the 8 bits of the next byte encode an offset backward from the current position in the pixel data at which the copy is to be found. Values from 0 to 1023 encode offsets from 1 to 1024. The encoding may be prescient, with the length larger than the offset. The new data is identical to the data at the given offset, even though the two strings overlap.

See Also

For the best description of Lempel & Ziv's sliding window scheme LZ77 see J. A. Storer & T. G. Szymanski Data Compression via Textual Substitution, JACM 29 #4, pp. 928-951.

[Top] [Prev] [Next]

Copyright © 1996,Lucent Technologies, Inc. All rights reserved.