Peter Siebel - Practical Common Lisp

Some binary file formats are in-memory data structures—on many operating systems it's possible to map a file into memory, and low-level languages such as C can then treat the region of memory containing the contents of the file just like any other memory; data written to that area of memory is saved to the underlying file when it's unmapped. However, these formats are platform-dependent since the in-memory representation of even such simple data types as integers depends on the hardware on which the program is running. Thus, any file format that's intended to be portable must define a canonical representation for all the data types it uses that can be mapped to the actual in-memory data representation on a particular kind of machine or in a particular language.

The term big-endian and its opposite, little-endian , borrowed from Jonathan Swift's Gulliver's Travels , refer to the way a multibyte number is represented in an ordered sequence of bytes such as in memory or in a file. For instance, the number 43981, or abcdin hex, represented as a 16-bit quantity, consists of two bytes, aband cd. It doesn't matter to a computer in what order these two bytes are stored as long as everybody agrees. Of course, whenever there's an arbitrary choice to be made between two equally good options, the one thing you can be sure of is that everybody is not going to agree. For more than you ever wanted to know about it, and to see where the terms big-endian and little-endian were first applied in this fashion, read "On Holy Wars and a Plea for Peace" by Danny Cohen, available at http://khavrinen.lcs.mit.edu/wollman/ien-137.txt.

LDB and DPB , a related function, were named after the DEC PDP-10 assembly functions that did essentially the same thing. Both functions operate on integers as if they were represented using twos-complement format, regardless of the internal representation used by a particular Common Lisp implementation.

Common Lisp also provides functions for shifting and masking the bits of integers in a way that may be more familiar to C and Java programmers. For instance, you could write read-u2yet a third way, using those functions, like this:

(defun read-u2 (in)

(logior (ash (read-byte in) 8) (read-byte in)))

which would be roughly equivalent to this Java method:

public int readU2 (InputStream in) throws IOException {

return (in.read() << 8) | (in.read());

}

The names LOGIOR and ASH are short for LOGical Inclusive OR and Arithmetic SHift . ASH shifts an integer a given number of bits to the left when its second argument is positive or to the right if the second argument is negative. LOGIOR combines integers by logically or ing each bit. Another function, LOGAND , performs a bitwise and , which can be used to mask off certain bits. However, for the kinds of bit twiddling you'll need to do in this chapter and the next, LDB and BYTE will be both more convenient and more idiomatic Common Lisp style.

Originally, UTF-8 was designed to represent a 31-bit character code and used up to six bytes per code point. However, the maximum Unicode code point is #x10ffff, so a UTF-8 encoding of Unicode requires at most four bytes per code point.

If you need to parse a file format that uses other character codes, or if you need to parse files containing arbitrary Unicode strings using a non-Unicode-Common-Lisp implementation, you can always represent such strings in memory as vectors of integer code points. They won't be Lisp strings, so you won't be able to manipulate or compare them with the string functions, but you'll still be able to do anything with them that you can with arbitrary vectors.

Unfortunately, the language itself doesn't always provide a good model in this respect: the macro DEFSTRUCT , which I don't discuss since it has largely been superseded by DEFCLASS , generates functions with names that it generates based on the name of the structure it's given. DEFSTRUCT 's bad example leads many new macro writers astray.

Technically there's no possibility of typeor objectconflicting with slot names—at worst they'd be shadowed within the WITH-SLOTS form. But it doesn't hurt anything to simply GENSYM all local variable names used within a macro template.

Using ASSOC to extract the :readerand :writerelements of specallows users of define-binary-typeto include the elements in either order; if you required the :readerelement to be always be first, you could then have used (rest (first spec))to extract the reader and (rest (second spec))to extract the writer. However, as long as you require the :readerand :writerkeywords to improve the readability of define-binary-typeforms, you might as well use them to extract the correct data.

The ID3 format doesn't require the parent-of-typefunction since it's a relatively flat structure. This function comes into its own when you need to parse a format made up of many deeply nested structures whose parsing depends on information stored in higher-level structures. For example, in the Java class file format, the top-level class file structure contains a constant pool that maps numeric values used in other substructures within the class file to constant values that are needed while parsing those substructures. If you were writing a class file parser, you could use parent-of-typein the code that reads and writes those substructures to get at the top-level class file object and from there to the constant pool.

Ripping is the process by which a song on an audio CD is converted to an MP3 file on your hard drive. These days most ripping software also automatically retrieves information about the songs being ripped from online databases such as Gracenote (née the Compact Disc Database [CDDB]) or FreeDB, which it then embeds in the MP3 files as ID3 tags.

Almost all file systems provide the ability to overwrite existing bytes of a file, but few, if any, provide a way to add or remove data at the beginning or middle of a file without having to rewrite the rest of the file. Since ID3 tags are typically stored at the beginning of a file, to rewrite an ID3 tag without disturbing the rest of the file you must replace the old tag with a new tag of exactly the same length. By writing ID3 tags with a certain amount of padding, you have a better chance of being able to do so—if the new tag has more data than the original tag, you use less padding, and if it's shorter, you use more.

The frame data following the ID3 header could also potentially contain the illegal sequence. That's prevented using a different scheme that's turned on via one of the flags in the tag header. The code in this chapter doesn't account for the possibility that this flag might be set; in practice it's rarely used.