cannam@86: % -*- mode: latex; TeX-master: "Vorbis_I_spec"; -*-
cannam@86: %!TEX root = Vorbis_I_spec.tex
cannam@86: % $Id$
cannam@86: \section{Bitpacking Convention} \label{vorbis:spec:bitpacking}
cannam@86: 
cannam@86: \subsection{Overview}
cannam@86: 
cannam@86: The Vorbis codec uses relatively unstructured raw packets containing
cannam@86: arbitrary-width binary integer fields.  Logically, these packets are a
cannam@86: bitstream in which bits are coded one-by-one by the encoder and then
cannam@86: read one-by-one in the same monotonically increasing order by the
cannam@86: decoder.  Most current binary storage arrangements group bits into a
cannam@86: native word size of eight bits (octets), sixteen bits, thirty-two bits
cannam@86: or, less commonly other fixed word sizes.  The Vorbis bitpacking
cannam@86: convention specifies the correct mapping of the logical packet
cannam@86: bitstream into an actual representation in fixed-width words.
cannam@86: 
cannam@86: 
cannam@86: \subsubsection{octets, bytes and words}
cannam@86: 
cannam@86: In most contemporary architectures, a 'byte' is synonymous with an
cannam@86: 'octet', that is, eight bits.  This has not always been the case;
cannam@86: seven, ten, eleven and sixteen bit 'bytes' have been used.  For
cannam@86: purposes of the bitpacking convention, a byte implies the native,
cannam@86: smallest integer storage representation offered by a platform.  On
cannam@86: modern platforms, this is generally assumed to be eight bits (not
cannam@86: necessarily because of the processor but because of the
cannam@86: filesystem/memory architecture.  Modern filesystems invariably offer
cannam@86: bytes as the fundamental atom of storage).  A 'word' is an integer
cannam@86: size that is a grouped multiple of this smallest size.
cannam@86: 
cannam@86: The most ubiquitous architectures today consider a 'byte' to be an
cannam@86: octet (eight bits) and a word to be a group of two, four or eight
cannam@86: bytes (16, 32 or 64 bits).  Note however that the Vorbis bitpacking
cannam@86: convention is still well defined for any native byte size; Vorbis uses
cannam@86: the native bit-width of a given storage system. This document assumes
cannam@86: that a byte is one octet for purposes of example.
cannam@86: 
cannam@86: \subsubsection{bit order}
cannam@86: 
cannam@86: A byte has a well-defined 'least significant' bit (LSb), which is the
cannam@86: only bit set when the byte is storing the two's complement integer
cannam@86: value +1.  A byte's 'most significant' bit (MSb) is at the opposite
cannam@86: end of the byte. Bits in a byte are numbered from zero at the LSb to
cannam@86: $n$ ($n=7$ in an octet) for the
cannam@86: MSb.
cannam@86: 
cannam@86: 
cannam@86: 
cannam@86: \subsubsection{byte order}
cannam@86: 
cannam@86: Words are native groupings of multiple bytes.  Several byte orderings
cannam@86: are possible in a word; the common ones are 3-2-1-0 ('big endian' or
cannam@86: 'most significant byte first' in which the highest-valued byte comes
cannam@86: first), 0-1-2-3 ('little endian' or 'least significant byte first' in
cannam@86: which the lowest value byte comes first) and less commonly 3-1-2-0 and
cannam@86: 0-2-1-3 ('mixed endian').
cannam@86: 
cannam@86: The Vorbis bitpacking convention specifies storage and bitstream
cannam@86: manipulation at the byte, not word, level, thus host word ordering is
cannam@86: of a concern only during optimization when writing high performance
cannam@86: code that operates on a word of storage at a time rather than by byte.
cannam@86: Logically, bytes are always coded and decoded in order from byte zero
cannam@86: through byte $n$.
cannam@86: 
cannam@86: 
cannam@86: 
cannam@86: \subsubsection{coding bits into byte sequences}
cannam@86: 
cannam@86: The Vorbis codec has need to code arbitrary bit-width integers, from
cannam@86: zero to 32 bits wide, into packets.  These integer fields are not
cannam@86: aligned to the boundaries of the byte representation; the next field
cannam@86: is written at the bit position at which the previous field ends.
cannam@86: 
cannam@86: The encoder logically packs integers by writing the LSb of a binary
cannam@86: integer to the logical bitstream first, followed by next least
cannam@86: significant bit, etc, until the requested number of bits have been
cannam@86: coded.  When packing the bits into bytes, the encoder begins by
cannam@86: placing the LSb of the integer to be written into the least
cannam@86: significant unused bit position of the destination byte, followed by
cannam@86: the next-least significant bit of the source integer and so on up to
cannam@86: the requested number of bits.  When all bits of the destination byte
cannam@86: have been filled, encoding continues by zeroing all bits of the next
cannam@86: byte and writing the next bit into the bit position 0 of that byte.
cannam@86: Decoding follows the same process as encoding, but by reading bits
cannam@86: from the byte stream and reassembling them into integers.
cannam@86: 
cannam@86: 
cannam@86: 
cannam@86: \subsubsection{signedness}
cannam@86: 
cannam@86: The signedness of a specific number resulting from decode is to be
cannam@86: interpreted by the decoder given decode context.  That is, the three
cannam@86: bit binary pattern 'b111' can be taken to represent either 'seven' as
cannam@86: an unsigned integer, or '-1' as a signed, two's complement integer.
cannam@86: The encoder and decoder are responsible for knowing if fields are to
cannam@86: be treated as signed or unsigned.
cannam@86: 
cannam@86: 
cannam@86: 
cannam@86: \subsubsection{coding example}
cannam@86: 
cannam@86: Code the 4 bit integer value '12' [b1100] into an empty bytestream.
cannam@86: Bytestream result:
cannam@86: 
cannam@86: \begin{Verbatim}[commandchars=\\\{\}]
cannam@86:               |
cannam@86:               V
cannam@86: 
cannam@86:         7 6 5 4 3 2 1 0
cannam@86: byte 0 [0 0 0 0 1 1 0 0]  <-
cannam@86: byte 1 [               ]
cannam@86: byte 2 [               ]
cannam@86: byte 3 [               ]
cannam@86:              ...
cannam@86: byte n [               ]  bytestream length == 1 byte
cannam@86: 
cannam@86: \end{Verbatim}
cannam@86: 
cannam@86: 
cannam@86: Continue by coding the 3 bit integer value '-1' [b111]:
cannam@86: 
cannam@86: \begin{Verbatim}[commandchars=\\\{\}]
cannam@86:         |
cannam@86:         V
cannam@86: 
cannam@86:         7 6 5 4 3 2 1 0
cannam@86: byte 0 [0 1 1 1 1 1 0 0]  <-
cannam@86: byte 1 [               ]
cannam@86: byte 2 [               ]
cannam@86: byte 3 [               ]
cannam@86:              ...
cannam@86: byte n [               ]  bytestream length == 1 byte
cannam@86: \end{Verbatim}
cannam@86: 
cannam@86: 
cannam@86: Continue by coding the 7 bit integer value '17' [b0010001]:
cannam@86: 
cannam@86: \begin{Verbatim}[commandchars=\\\{\}]
cannam@86:           |
cannam@86:           V
cannam@86: 
cannam@86:         7 6 5 4 3 2 1 0
cannam@86: byte 0 [1 1 1 1 1 1 0 0]
cannam@86: byte 1 [0 0 0 0 1 0 0 0]  <-
cannam@86: byte 2 [               ]
cannam@86: byte 3 [               ]
cannam@86:              ...
cannam@86: byte n [               ]  bytestream length == 2 bytes
cannam@86:                           bit cursor == 6
cannam@86: \end{Verbatim}
cannam@86: 
cannam@86: 
cannam@86: Continue by coding the 13 bit integer value '6969' [b110 11001110 01]:
cannam@86: 
cannam@86: \begin{Verbatim}[commandchars=\\\{\}]
cannam@86:                 |
cannam@86:                 V
cannam@86: 
cannam@86:         7 6 5 4 3 2 1 0
cannam@86: byte 0 [1 1 1 1 1 1 0 0]
cannam@86: byte 1 [0 1 0 0 1 0 0 0]
cannam@86: byte 2 [1 1 0 0 1 1 1 0]
cannam@86: byte 3 [0 0 0 0 0 1 1 0]  <-
cannam@86:              ...
cannam@86: byte n [               ]  bytestream length == 4 bytes
cannam@86: 
cannam@86: \end{Verbatim}
cannam@86: 
cannam@86: 
cannam@86: 
cannam@86: 
cannam@86: \subsubsection{decoding example}
cannam@86: 
cannam@86: Reading from the beginning of the bytestream encoded in the above example:
cannam@86: 
cannam@86: \begin{Verbatim}[commandchars=\\\{\}]
cannam@86:                       |
cannam@86:                       V
cannam@86: 
cannam@86:         7 6 5 4 3 2 1 0
cannam@86: byte 0 [1 1 1 1 1 1 0 0]  <-
cannam@86: byte 1 [0 1 0 0 1 0 0 0]
cannam@86: byte 2 [1 1 0 0 1 1 1 0]
cannam@86: byte 3 [0 0 0 0 0 1 1 0]  bytestream length == 4 bytes
cannam@86: 
cannam@86: \end{Verbatim}
cannam@86: 
cannam@86: 
cannam@86: We read two, two-bit integer fields, resulting in the returned numbers
cannam@86: 'b00' and 'b11'.  Two things are worth noting here:
cannam@86: 
cannam@86: \begin{itemize}
cannam@86: \item Although these four bits were originally written as a single
cannam@86: four-bit integer, reading some other combination of bit-widths from the
cannam@86: bitstream is well defined.  There are no artificial alignment
cannam@86: boundaries maintained in the bitstream.
cannam@86: 
cannam@86: \item The second value is the
cannam@86: two-bit-wide integer 'b11'.  This value may be interpreted either as
cannam@86: the unsigned value '3', or the signed value '-1'.  Signedness is
cannam@86: dependent on decode context.
cannam@86: \end{itemize}
cannam@86: 
cannam@86: 
cannam@86: 
cannam@86: 
cannam@86: \subsubsection{end-of-packet alignment}
cannam@86: 
cannam@86: The typical use of bitpacking is to produce many independent
cannam@86: byte-aligned packets which are embedded into a larger byte-aligned
cannam@86: container structure, such as an Ogg transport bitstream.  Externally,
cannam@86: each bytestream (encoded bitstream) must begin and end on a byte
cannam@86: boundary.  Often, the encoded bitstream is not an integer number of
cannam@86: bytes, and so there is unused (uncoded) space in the last byte of a
cannam@86: packet.
cannam@86: 
cannam@86: Unused space in the last byte of a bytestream is always zeroed during
cannam@86: the coding process.  Thus, should this unused space be read, it will
cannam@86: return binary zeroes.
cannam@86: 
cannam@86: Attempting to read past the end of an encoded packet results in an
cannam@86: 'end-of-packet' condition.  End-of-packet is not to be considered an
cannam@86: error; it is merely a state indicating that there is insufficient
cannam@86: remaining data to fulfill the desired read size.  Vorbis uses truncated
cannam@86: packets as a normal mode of operation, and as such, decoders must
cannam@86: handle reading past the end of a packet as a typical mode of
cannam@86: operation. Any further read operations after an 'end-of-packet'
cannam@86: condition shall also return 'end-of-packet'.
cannam@86: 
cannam@86: 
cannam@86: 
cannam@86: \subsubsection{reading zero bits}
cannam@86: 
cannam@86: Reading a zero-bit-wide integer returns the value '0' and does not
cannam@86: increment the stream cursor.  Reading to the end of the packet (but
cannam@86: not past, such that an 'end-of-packet' condition has not triggered)
cannam@86: and then reading a zero bit integer shall succeed, returning 0, and
cannam@86: not trigger an end-of-packet condition.  Reading a zero-bit-wide
cannam@86: integer after a previous read sets 'end-of-packet' shall also fail
cannam@86: with 'end-of-packet'.
cannam@86: 
cannam@86: 
cannam@86: 
cannam@86: 
cannam@86: 
cannam@86: