Vorbis I specification

Vorbis is a general purpose perceptual audio CODEC intended to allow maximum encoder flexibility, thus allowing it to scale competitively over an exceptionally wide range of bitrates. At the high quality/bitrate end of the scale (CD or DAT rate stereo, 16/24 bits) it is in the same league as MPEG-2 and MPC. Similarly, the 1.0 encoder can encode high-quality CD and DAT rate stereo at below 48kbps without resampling to a lower rate. Vorbis is also intended for lower and higher sample rates (from 8kHz telephony to 192kHz digital masters) and a range of channel representations (monaural, polyphonic, stereo, quadraphonic, 5.1, ambisonic, or up to 255 discrete channels).

Vorbis I is a forward-adaptive monolithic transform CODEC based on the Modified Discrete Cosine Transform. The codec is structured to allow addition of a hybrid wavelet filterbank in Vorbis II to offer better transient response and reproduction using a transform better suited to localized time events.

The Vorbis CODEC design assumes a complex, psychoacoustically-aware encoder and simple, low-complexity decoder. Vorbis decode is computationally simpler than mp3, although it does require more working memory as Vorbis has no static probability model; the vector codebooks used in the first stage of decoding from the bitstream are packed in their entirety into the Vorbis bitstream headers. In packed form, these codebooks occupy only a few kilobytes; the extent to which they are pre-decoded into a cache is the dominant factor in decoder memory usage.

Vorbis provides none of its own framing, synchronization or protection against errors; it is solely a method of accepting input audio, dividing it into individual frames and compressing these frames into raw, unformatted 'packets'. The decoder then accepts these raw packets in sequence, decodes them, synthesizes audio frames from them, and reassembles the frames into a facsimile of the original audio stream. Vorbis is a free-form variable bit rate (VBR) codec and packets have no minimum size, maximum size, or fixed/expected size. Packets are designed that they may be truncated (or padded) and remain decodable; this is not to be considered an error condition and is used extensively in bitrate management in peeling. Both the transport mechanism and decoder must allow that a packet may be any size, or end before or after packet decode expects.

Vorbis packets are thus intended to be used with a transport mechanism that provides free-form framing, sync, positioning and error correction in accordance with these design assumptions, such as Ogg (for file transport) or RTP (for network multicast). For purposes of a few examples in this document, we will assume that Vorbis is to be embedded in an Ogg stream specifically, although this is by no means a requirement or fundamental assumption in the Vorbis design.

The specification for embedding Vorbis into an Ogg transport stream is in Appendix 1, Embedding Vorbis into an Ogg stream.

Vorbis' heritage is as a research CODEC and its current design reflects a desire to allow multiple decades of continuous encoder improvement before running out of room within the codec specification. For these reasons, configurable aspects of codec setup intentionally lean toward the extreme of forward adaptive.

The single most controversial design decision in Vorbis (and the most unusual for a Vorbis developer to keep in mind) is that the entire probability model of the codec, the Huffman and VQ codebooks, is packed into the bitstream header along with extensive CODEC setup parameters (often several hundred fields). This makes it impossible, as it would be with MPEG audio layers, to embed a simple frame type flag in each audio packet, or begin decode at any frame in the stream without having previously fetched the codec setup header.

Thus, Vorbis headers are both required for decode to begin and relatively large as bitstream headers go. The header size is unbounded, although for streaming a rule-of-thumb of 4kB or less is recommended (and Xiph.Org's Vorbis encoder follows this suggestion).

Our own design work indicates the primary liability of the required header is in mindshare; it is an unusual design and thus causes some amount of complaint among engineers as this runs against current design trends (and also points out limitations in some existing software/interface designs, such as Windows' ACM codec framework). However, we find that it does not fundamentally limit Vorbis' suitable application space.

The Vorbis format is well-defined by its decode specification; any encoder that produces packets that are correctly decoded by the reference Vorbis decoder described below may be considered a proper Vorbis encoder. A decoder must faithfully and completely implement the specification defined below (except where noted) to be considered a proper Vorbis decoder.

Although Vorbis decode is computationally simple, it may still run into specific limitations of an embedded design. For this reason, embedded designs are allowed to deviate in limited ways from the 'full' decode specification yet still be certified compliant. These optional omissions are labelled in the spec where relevant.

Global codec configuration consists of a few audio related fields (sample rate, channels), Vorbis version (always '0' in Vorbis I), bitrate hints, and the lists of component instances. All other configuration is in the context of specific components.

Each Vorbis frame is coded according to a master 'mode'. A bitstream may use one or many modes.

The mode mechanism is used to encode a frame according to one of multiple possible methods with the intention of choosing a method best suited to that frame. Different modes are, e.g. how frame size is changed from frame to frame. The mode number of a frame serves as a top level configuration switch for all other specific aspects of frame decode.

A 'mode' configuration consists of a frame size setting, window type (always 0, the Vorbis window, in Vorbis I), transform type (always type 0, the MDCT, in Vorbis I) and a mapping number. The mapping number specifies which mapping configuration instance to use for low-level packet decode and synthesis.

A mapping contains a channel coupling description and a list of 'submaps' that bundle sets of channel vectors together for grouped encoding and decoding. These submaps are not references to external components; the submap list is internal and specific to a mapping.

A 'submap' is a configuration/grouping that applies to a subset of floor and residue vectors within a mapping. The submap functions as a last layer of indirection such that specific special floor or residue settings can be applied not only to all the vectors in a given mode, but also specific vectors in a specific mode. Each submap specifies the proper floor and residue instance number to use for decoding that submap's spectral floor and spectral residue vectors.

As an example:

Assume a Vorbis stream that contains six channels in the standard 5.1 format. The sixth channel, as is normal in 5.1, is bass only. Therefore it would be wasteful to encode a full-spectrum version of it as with the other channels. The submapping mechanism can be used to apply a full range floor and residue encoding to channels 0 through 4, and a bass-only representation to the bass channel, thus saving space. In this example, channels 0-4 belong to submap 0 (which indicates use of a full-range floor) and channel 5 belongs to submap 1, which uses a bass-only representation.

Vorbis encodes a spectral 'floor' vector for each PCM channel. This vector is a low-resolution representation of the audio spectrum for the given channel in the current frame, generally used akin to a whitening filter. It is named a 'floor' because the Xiph.Org reference encoder has historically used it as a unit-baseline for spectral resolution.

A floor encoding may be of two types. Floor 0 uses a packed LSP representation on a dB amplitude scale and Bark frequency scale. Floor 1 represents the curve as a piecewise linear interpolated representation on a dB amplitude scale and linear frequency scale. The two floors are semantically interchangeable in encoding/decoding. However, floor type 1 provides more stable inter-frame behavior, and so is the preferred choice in all coupled-stereo and high bitrate modes. Floor 1 is also considerably less expensive to decode than floor 0.

Floor 0 is not to be considered deprecated, but it is of limited modern use. No known Vorbis encoder past Xiph.org's own beta 4 makes use of floor 0.

The values coded/decoded by a floor are both compactly formatted and make use of entropy coding to save space. For this reason, a floor configuration generally refers to multiple codebooks in the codebook component list. Entropy coding is thus provided as an abstraction, and each floor instance may choose from any and all available codebooks when coding/decoding.

The spectral residue is the fine structure of the audio spectrum once the floor curve has been subtracted out. In simplest terms, it is coded in the bitstream using cascaded (multi-pass) vector quantization according to one of three specific packing/coding algorithms numbered 0 through 2. The packing algorithm details are configured by residue instance. As with the floor components, the final VQ/entropy encoding is provided by external codebook instances and each residue instance may choose from any and all available codebooks.

Codebooks are a self-contained abstraction that perform entropy decoding and, optionally, use the entropy-decoded integer value as an offset into an index of output value vectors, returning the indicated vector of values.

The entropy coding in a Vorbis I codebook is provided by a standard Huffman binary tree representation. This tree is tightly packed using one of several methods, depending on whether codeword lengths are ordered or unordered, or the tree is sparse.

The codebook vector index is similarly packed according to index characteristic. Most commonly, the vector index is encoded as a single list of values of possible values that are then permuted into a list of n-dimensional rows (lattice VQ).

Before decoding can begin, a decoder must initialize using the bitstream headers matching the stream to be decoded. Vorbis uses three header packets; all are required, in-order, by this specification. Once set up, decode may begin at any audio packet belonging to the Vorbis stream. In Vorbis I, all packets after the three initial headers are audio packets.

The header packets are, in order, the identification header, the comments header, and the setup header.

Note that clever rearrangement of the synthesis arithmetic is possible; as an example, one can take advantage of symmetries in the MDCT to store the right-hand transform data of a partial MDCT for a 50% inter-frame buffer space savings, and then complete the transform later before overlap/add with the next frame. This optimization produces entirely equivalent output and is naturally perfectly legal. The decoder must be entirely mathematically equivalent to the specification, it need not be a literal semantic implementation.

1.3.2.3. Window shape decode (long windows only)

Vorbis frames may be one of two PCM sample sizes specified during codec setup. In Vorbis I, legal frame sizes are powers of two from 64 to 8192 samples. Aside from coupling, Vorbis handles channels as independent vectors and these frame sizes are in samples per channel.

Vorbis uses an overlapping transform, namely the MDCT, to blend one frame into the next, avoiding most inter-frame block boundary artifacts. The MDCT output of one frame is windowed according to MDCT requirements, overlapped 50% with the output of the previous frame and added. The window shape assures seamless reconstruction.

This is easy to visualize in the case of equal sized-windows:

And slightly more complex in the case of overlapping unequal sized windows:

In the unequal-sized window case, the window shape of the long window must be modified for seamless lapping as above. It is possible to correctly infer window shape to be applied to the current window from knowing the sizes of the current, previous and next window. It is legal for a decoder to use this method. However, in the case of a long window (short windows require no modification), Vorbis also codes two flag bits to specify pre- and post- window shape. Although not strictly necessary for function, this minor redundancy allows a packet to be fully decoded to the point of lapping entirely independently of any other packet, allowing easier abstraction of decode layers as well as allowing a greater level of easy parallelism in encode and decode.

A description of valid window functions for use with an inverse MDCT can be found in the paper “ The use of multirate filter banks for coding of high quality digital audio”, by T. Sporer, K. Brandenburg and B. Edler. Vorbis windows all use the slope function $y = \sin(.5*\pi \, \sin^2((x+.5)/n*\pi))$.

window_blocksize(previous_window)/4+window_blocksize(current_window)/4

In most contemporary architectures, a 'byte' is synonymous with an 'octet', that is, eight bits. This has not always been the case; seven, ten, eleven and sixteen bit 'bytes' have been used. For purposes of the bitpacking convention, a byte implies the native, smallest integer storage representation offered by a platform. On modern platforms, this is generally assumed to be eight bits (not necessarily because of the processor but because of the filesystem/memory architecture. Modern filesystems invariably offer bytes as the fundamental atom of storage). A 'word' is an integer size that is a grouped multiple of this smallest size.

The most ubiquitous architectures today consider a 'byte' to be an octet (eight bits) and a word to be a group of two, four or eight bytes (16, 32 or 64 bits). Note however that the Vorbis bitpacking convention is still well defined for any native byte size; Vorbis uses the native bit-width of a given storage system. This document assumes that a byte is one octet for purposes of example.

A byte has a well-defined 'least significant' bit (LSb), which is the only bit set when the byte is storing the two's complement integer value +1. A byte's 'most significant' bit (MSb) is at the opposite end of the byte. Bits in a byte are numbered from zero at the LSb to n (n=7 in an octet) for the MSb.

Words are native groupings of multiple bytes. Several byte orderings are possible in a word; the common ones are 3-2-1-0 ('big endian' or 'most significant byte first' in which the highest-valued byte comes first), 0-1-2-3 ('little endian' or 'least significant byte first' in which the lowest value byte comes first) and less commonly 3-1-2-0 and 0-2-1-3 ('mixed endian').

The Vorbis bitpacking convention specifies storage and bitstream manipulation at the byte, not word, level, thus host word ordering is of a concern only during optimization when writing high performance code that operates on a word of storage at a time rather than by byte. Logically, bytes are always coded and decoded in order from byte zero through byte n.

The Vorbis codec has need to code arbitrary bit-width integers, from zero to 32 bits wide, into packets. These integer fields are not aligned to the boundaries of the byte representation; the next field is written at the bit position at which the previous field ends.

The encoder logically packs integers by writing the LSb of a binary integer to the logical bitstream first, followed by next least significant bit, etc, until the requested number of bits have been coded. When packing the bits into bytes, the encoder begins by placing the LSb of the integer to be written into the least significant unused bit position of the destination byte, followed by the next-least significant bit of the source integer and so on up to the requested number of bits. When all bits of the destination byte have been filled, encoding continues by zeroing all bits of the next byte and writing the next bit into the bit position 0 of that byte. Decoding follows the same process as encoding, but by reading bits from the byte stream and reassembling them into integers.

The signedness of a specific number resulting from decode is to be interpreted by the decoder given decode context. That is, the three bit binary pattern 'b111' can be taken to represent either 'seven' as an unsigned integer, or '-1' as a signed, two's complement integer. The encoder and decoder are responsible for knowing if fields are to be treated as signed or unsigned.

Code the 4 bit integer value '12' [b1100] into an empty bytestream. Bytestream result:

  
              |
              V

        7 6 5 4 3 2 1 0
byte 0 [0 0 0 0 1 1 0 0]  <-
byte 1 [               ]
byte 2 [               ]
byte 3 [               ]
             ...
byte n [               ]  bytestream length == 1 byte

Continue by coding the 3 bit integer value '-1' [b111]:

        |
        V

        7 6 5 4 3 2 1 0
byte 0 [0 1 1 1 1 1 0 0]  <-
byte 1 [               ]
byte 2 [               ]
byte 3 [               ]
             ... 
byte n [               ]  bytestream length == 1 byte

Continue by coding the 7 bit integer value '17' [b0010001]:

          |
          V    

        7 6 5 4 3 2 1 0
byte 0 [1 1 1 1 1 1 0 0]
byte 1 [0 0 0 0 1 0 0 0]  <-
byte 2 [               ]
byte 3 [               ]
             ...
byte n [               ]  bytestream length == 2 bytes
                          bit cursor == 6

Continue by coding the 13 bit integer value '6969' [b110 11001110 01]:

                |
                V

        7 6 5 4 3 2 1 0
byte 0 [1 1 1 1 1 1 0 0]
byte 1 [0 1 0 0 1 0 0 0]
byte 2 [1 1 0 0 1 1 1 0]
byte 3 [0 0 0 0 0 1 1 0]  <-
             ...
byte n [               ]  bytestream length == 4 bytes

Reading from the beginning of the bytestream encoded in the above example:

                      |
                      V
                      
        7 6 5 4 3 2 1 0
byte 0 [1 1 1 1 1 1 0 0]  <-
byte 1 [0 1 0 0 1 0 0 0]
byte 2 [1 1 0 0 1 1 1 0]
byte 3 [0 0 0 0 0 1 1 0]  bytestream length == 4 bytes

We read two, two-bit integer fields, resulting in the returned numbers 'b00' and 'b11'. Two things are worth noting here:

The typical use of bitpacking is to produce many independent byte-aligned packets which are embedded into a larger byte-aligned container structure, such as an Ogg transport bitstream. Externally, each bytestream (encoded bitstream) must begin and end on a byte boundary. Often, the encoded bitstream is not an integer number of bytes, and so there is unused (uncoded) space in the last byte of a packet.

Unused space in the last byte of a bytestream is always zeroed during the coding process. Thus, should this unused space be read, it will return binary zeroes.

Attempting to read past the end of an encoded packet results in an 'end-of-packet' condition. End-of-packet is not to be considered an error; it is merely a state indicating that there is insufficient remaining data to fulfill the desired read size. Vorbis uses truncated packets as a normal mode of operation, and as such, decoders must handle reading past the end of a packet as a typical mode of operation. Any further read operations after an 'end-of-packet' condition shall also return 'end-of-packet'.

Reading a zero-bit-wide integer returns the value '0' and does not increment the stream cursor. Reading to the end of the packet (but not past, such that an 'end-of-packet' condition has not triggered) and then reading a zero bit integer shall succeed, returning 0, and not trigger an end-of-packet condition. Reading a zero-bit-wide integer after a previous read sets 'end-of-packet' shall also fail with 'end-of-packet'.

The codebook mechanism is built on top of the vorbis bitpacker. Both the codebooks themselves and the codewords they decode are unrolled from a packet as a series of arbitrary-width values read from the stream according to Section 2, “Bitpacking Convention”.

A codebook begins with a 24 bit sync pattern, 0x564342:

byte 0: [ 0 1 0 0 0 0 1 0 ] (0x42)
byte 1: [ 0 1 0 0 0 0 1 1 ] (0x43)
byte 2: [ 0 1 0 1 0 1 1 0 ] (0x56)

16 bit [codebook_dimensions] and 24 bit [codebook_entries] fields:

byte 3: [ X X X X X X X X ] 
byte 4: [ X X X X X X X X ] [codebook_dimensions] (16 bit unsigned)

byte 5: [ X X X X X X X X ] 
byte 6: [ X X X X X X X X ] 
byte 7: [ X X X X X X X X ] [codebook_entries] (24 bit unsigned)

Next is the [ordered] bit flag:

byte 8: [               X ] [ordered] (1 bit)

Each entry, numbering a total of [codebook_entries], is assigned a codeword length. We now read the list of codeword lengths and store these lengths in the array [codebook_codeword_lengths]. Decode of lengths is according to whether the [ordered] flag is set or unset.

After all codeword lengths have been decoded, the decoder reads the vector lookup table. Vorbis I supports three lookup types:

The lookup table type is read as a four bit unsigned integer:

  1) [codebook_lookup_type] = read four bits as an unsigned integer

Codebook decode precedes according to [codebook_lookup_type]:

An 'end of packet' during any read operation in the above steps is considered an error condition rendering the stream undecodable.

3.2.1.1. Huffman decision tree representation

The [codebook_codeword_lengths] array and [codebook_entries] value uniquely define the Huffman decision tree used for entropy decoding.

Briefly, each used codebook entry (recall that length-unordered codebooks support unused codeword entries) is assigned, in order, the lowest valued unused binary Huffman codeword possible. Assume the following codeword length list:

entry 0: length 2
entry 1: length 4
entry 2: length 4
entry 3: length 4
entry 4: length 4
entry 5: length 2
entry 6: length 3
entry 7: length 3

Assigning codewords in order (lowest possible value of the appropriate length to highest) results in the following codeword list:

entry 0: length 2 codeword 00
entry 1: length 4 codeword 0100
entry 2: length 4 codeword 0101
entry 3: length 4 codeword 0110
entry 4: length 4 codeword 0111
entry 5: length 2 codeword 10
entry 6: length 3 codeword 110
entry 7: length 3 codeword 111

Note

Unlike most binary numerical values in this document, we intend the above codewords to be read and used bit by bit from left to right, thus the codeword '001' is the bit string 'zero, zero, one'. When determining 'lowest possible value' in the assignment definition above, the leftmost bit is the MSb.

It is clear that the codeword length list represents a Huffman decision tree with the entry numbers equivalent to the leaves numbered left-to-right:

As we assign codewords in order, we see that each choice constructs a new leaf in the leftmost possible position.

Note that it's possible to underspecify or overspecify a Huffman tree via the length list. In the above example, if codeword seven were eliminated, it's clear that the tree is unfinished:

Similarly, in the original codebook, it's clear that the tree is fully populated and a ninth codeword is impossible. Both underspecified and overspecified trees are an error condition rendering the stream undecodable.

Codebook entries marked 'unused' are simply skipped in the assigning process. They have no codeword and do not appear in the decision tree, thus it's impossible for any bit pattern read from the stream to decode to that entry number.

the [codebook_multiplicands] array
[codebook_minimum_value]
[codebook_delta_value]
[codebook_sequence_p]
[codebook_lookup_type]
[codebook_entries]
[codebook_dimensions]
[codebook_lookup_values]

  1) [last] = 0;
  2) [index_divisor] = 1;
  3) iterate [i] over the range 0 ... [codebook_dimensions]-1 (once for each scalar value in the value vector) {
       
       4) [multiplicand_offset] = ( [lookup_offset] divided by [index_divisor] using integer 
          division ) integer modulo [codebook_lookup_values]

       5) vector [value_vector] element [i] = 
            ( [codebook_multiplicands] array element number [multiplicand_offset] ) *
            [codebook_delta_value] + [codebook_minimum_value] + [last];

       6) if ( [codebook_sequence_p] is set ) then set [last] = vector [value_vector] element [i]

       7) [index_divisor] = [index_divisor] * [codebook_lookup_values]

     }
 
  8) vector calculation completed.

  1) [last] = 0;
  2) [multiplicand_offset] = [lookup_offset] * [codebook_dimensions]
  3) iterate [i] over the range 0 ... [codebook_dimensions]-1 (once for each scalar value in the value vector) {

       4) vector [value_vector] element [i] = 
            ( [codebook_multiplicands] array element number [multiplicand_offset] ) *
            [codebook_delta_value] + [codebook_minimum_value] + [last];

       5) if ( [codebook_sequence_p] is set ) then set [last] = vector [value_vector] element [i] 

       6) increment [multiplicand_offset]

     }
 
  7) vector calculation completed.

Each header packet begins with the same header fields.

  1) [packet_type] : 8 bit value
  2) 0x76, 0x6f, 0x72, 0x62, 0x69, 0x73: the characters 'v','o','r','b','i','s' as six octets

Decode continues according to packet type; the identification header is type 1, the comment header type 3 and the setup header type 5 (these types are all odd as a packet with a leading single bit of '0' is an audio packet). The packets must occur in the order of identification, comment, setup.

The identification header is a short header of only a few fields used to declare the stream definitively as Vorbis, and provide a few externally relevant pieces of information about the audio stream. The identification header is coded as follows:

 1) [vorbis_version] = read 32 bits as unsigned integer
 2) [audio_channels] = read 8 bit integer as unsigned
 3) [audio_sample_rate] = read 32 bits as unsigned integer
 4) [bitrate_maximum] = read 32 bits as signed integer
 5) [bitrate_nominal] = read 32 bits as signed integer
 6) [bitrate_minimum] = read 32 bits as signed integer
 7) [blocksize_0] = 2 exponent (read 4 bits as unsigned integer)
 8) [blocksize_1] = 2 exponent (read 4 bits as unsigned integer)
 9) [framing_flag] = read one bit

[vorbis_version] is to read '0' in order to be compatible with this document. Both [audio_channels] and [audio_sample_rate] must read greater than zero. Allowed final blocksize values are 64, 128, 256, 512, 1024, 2048, 4096 and 8192 in Vorbis I. [blocksize_0] must be less than or equal to [blocksize_1]. The framing bit must be nonzero. Failure to meet any of these conditions renders a stream undecodable.

The bitrate fields above are used only as hints. The nominal bitrate field especially may be considerably off in purely VBR streams. The fields are meaningful only when greater than zero.

Comment header decode and data specification is covered in Section 5, “comment field and header specification”.

Vorbis codec setup is configurable to an extreme degree:

The setup header contains the bulk of the codec setup information needed for decode. The setup header contains, in order, the lists of codebook configurations, time-domain transform configurations (placeholders in Vorbis I), floor configurations, residue configurations, channel mapping configurations and mode configurations. It finishes with a framing bit of '1'. Header decode proceeds in the following order:

Vorbis windows all use the slope function y=sin(0.5 * π * sin^2((x+.5)/n * π)), where n is window size and x ranges 0...n-1, but dissimilar lapping requirements can affect overall shape. Window generation proceeds as follows:

An end-of-packet condition up to this point should be considered an error that discards this packet from the stream. An end of packet condition past this point is to be considered a possible nominal occurrence.

From this point on, we assume out decode context is using mode number [mode_number] from configuration array [vorbis_mode_configurations] and the map number [vorbis_mode_mapping] (specified by the current mode) taken from the mapping configuration array [vorbis_mapping_configurations].

Floor curves are decoded one-by-one in channel order.

For each floor [i] of [audio_channels]

An end-of-packet condition during floor decode shall result in packet decode zeroing all channel output vectors and skipping to the add/overlap output stage.

A possible result of floor decode is that a specific vector is marked 'unused' which indicates that that final output vector is all-zero values (and the floor is zero). The residue for that vector is not coded in the stream, save for one complication. If some vectors are used and some are not, channel coupling could result in mixing a zeroed and nonzeroed vector to produce two nonzeroed vectors.

for each [i] from 0 ... [vorbis_mapping_coupling_steps]-1

Unlike floors, which are decoded in channel order, the residue vectors are decoded in submap order.

for each submap [i] in order from 0 ... [vorbis_mapping_submaps]-1

for each [i] from [vorbis_mapping_coupling_steps]-1 descending to 0

For each channel, synthesize the floor curve from the decoded floor information, according to packet type. Note that the vector synthesis length for floor computation is [n]/2.

For each channel, multiply each element of the floor curve by each element of that channel's residue vector. The result is the dot product of the floor and residue vectors for each channel; the produced vectors are the length [n]/2 audio spectrum for each channel.

One point is worth mentioning about this dot product; a common mistake in a fixed point implementation might be to assume that a 32 bit fixed-point representation for floor and residue and direct multiplication of the vectors is sufficient for acceptable spectral depth in all cases because it happens to mostly work with the current Xiph.Org reference encoder.

However, floor vector values can span ~140dB (~24 bits unsigned), and the audio spectrum vector should represent a minimum of 120dB (~21 bits with sign), even when output is to a 16 bit PCM device. For the residue vector to represent full scale if the floor is nailed to -140dB, it must be able to span 0 to +140dB. For the residue vector to reach full scale if the floor is nailed at 0dB, it must be able to represent -140dB to +0dB. Thus, in order to handle full range dynamics, a residue vector may span -140dB to +140dB entirely within spec. A 280dB range is approximately 48 bits with sign; thus the residue vector must be able to represent a 48 bit range and the dot product must be able to handle an effective 48 bit times 24 bit multiplication. This range may be achieved using large (64 bit or larger) integers, or implementing a movable binary point representation.

Convert the audio spectrum vector of each channel back into time domain PCM audio via an inverse Modified Discrete Cosine Transform (MDCT). A detailed description of the MDCT is available in the paper “The use of multirate filter banks for coding of high quality digital audio”, by T. Sporer, K. Brandenburg and B. Edler. The window function used for the MDCT is the function described earlier.

Windowed MDCT output is overlapped and added with the right hand data of the previous window such that the 3/4 point of the previous window is aligned with the 1/4 point of the current window (as illustrated in Section 1.3.2.3, “Window shape decode (long windows only)”). The overlapped portion produced from overlapping the previous and current frame data is finished data to be returned by the decoder. This data spans from the center of the previous window to the center of the current window. In the case of same-sized windows, the amount of data to return is one-half block consisting of and only of the overlapped portions. When overlapping a short and long window, much of the returned range does not actually overlap. This does not damage transform orthogonality. Pay attention however to returning the correct data range; the amount of data to be returned is:

window_blocksize(previous_window)/4+window_blocksize(current_window)/4

from the center (element windowsize/2) of the previous window to the center (element windowsize/2-1, inclusive) of the current window.

Data is not returned from the first frame; it must be used to 'prime' the decode engine. The encoder accounts for this priming when calculating PCM offsets; after the first frame, the proper PCM output offset is '0' (as no data has been returned yet).

Vorbis I specifies only a channel mapping type 0. In mapping type 0, channel mapping is implicitly defined as follows for standard audio applications:

Applications using Vorbis for dedicated purposes may define channel mapping as seen fit. Future channel mappings (such as three and four channel Ambisonics) will make use of channel mappings other than mapping 0.

The comment header is logically a list of eight-bit-clean vectors; the number of vectors is bounded to 2^32-1 and the length of each vector is limited to 2^32-1 bytes. The vector length is encoded; the vector contents themselves are not null terminated. In addition to the vector list, there is a single vector for vendor name (also 8 bit clean, length encoded in 32 bits). For example, the 1.0 release of libvorbis set the vendor string to "Xiph.Org libVorbis I 20020717".

The comment header is decoded as follows:

  1) [vendor_length] = read an unsigned integer of 32 bits
  2) [vendor_string] = read a UTF-8 vector as [vendor_length] octets
  3) [user_comment_list_length] = read an unsigned integer of 32 bits
  4) iterate [user_comment_list_length] times {
       5) [length] = read an unsigned integer of 32 bits
       6) this iteration's user comment = read a UTF-8 vector as [length] octets
     }
  7) [framing_bit] = read a single bit as boolean
  8) if ( [framing_bit] unset or end-of-packet ) then ERROR
  9) done.

The comment vectors are structured similarly to a UNIX environment variable. That is, comment fields consist of a field name and a corresponding value and look like:

The field name is case-insensitive and may consist of ASCII 0x20 through 0x7D, 0x3D ('=') excluded. ASCII 0x41 through 0x5A inclusive (characters A-Z) is to be considered equivalent to ASCII 0x61 through 0x7A inclusive (characters a-z).

The field name is immediately followed by ASCII 0x3D ('='); this equals sign is used to terminate the field name.

0x3D is followed by 8 bit clean UTF-8 encoded value of the field contents to the end of the field.

The comment header comprises the entirety of the second bitstream header packet. Unlike the first bitstream header packet, it is not generally the only packet on the second page and may not be restricted to within the second bitstream page. The length of the comment header packet is (practically) unbounded. The comment header packet is not optional; it must be present in the bitstream even if it is effectively empty.

The comment header is encoded as follows (as per Ogg's standard bitstream mapping which renders least-significant-bit of the word to be coded into the least significant available bit of the current bitstream octet first):

This is actually somewhat easier to describe in code; implementation of the above can be found in vorbis/lib/info.c, _vorbis_pack_comment() and _vorbis_unpack_comment().

Configuration information for instances of floor zero decodes from the codec setup header (third packet). configuration decode proceeds as follows:

  1) [floor0_order] = read an unsigned integer of 8 bits
  2) [floor0_rate] = read an unsigned integer of 16 bits
  3) [floor0_bark_map_size] = read an unsigned integer of 16 bits
  4) [floor0_amplitude_bits] = read an unsigned integer of six bits
  5) [floor0_amplitude_offset] = read an unsigned integer of eight bits
  6) [floor0_number_of_books] = read an unsigned integer of four bits and add 1
  7) if any of [floor0_order], [floor0_rate], [floor0_bark_map_size], [floor0_amplitude_bits],
     [floor0_amplitude_offset] or [floor0_number_of_books] are less than zero, the stream is not decodable
  8) array [floor0_book_list] = read a list of [floor0_number_of_books] unsigned integers of eight bits each;

An end-of-packet condition during any of these bitstream reads renders this stream undecodable. In addition, any element of the array [floor0_book_list] that is greater than the maximum codebook number for this bitstream is an error condition that also renders the stream undecodable.

Extracting a floor0 curve from an audio packet consists of first decoding the curve amplitude and [floor0_order] LSP coefficient values from the bitstream, and then computing the floor curve, which is defined as the frequency response of the decoded LSP filter.

Packet decode proceeds as follows:

  1) [amplitude] = read an unsigned integer of [floor0_amplitude_bits] bits
  2) if ( [amplitude] is greater than zero ) {
       3) [coefficients] is an empty, zero length vector
       4) [booknumber] = read an unsigned integer of ilog( [floor0_number_of_books] ) bits
       5) if ( [booknumber] is greater than the highest number decode codebook ) then packet is undecodable
       6) [last] = zero;
       7) vector [temp_vector] = read vector from bitstream using codebook number [floor0_book_list] element [booknumber] in VQ context.
       8) add the scalar value [last] to each scalar in vector [temp_vector]
       9) [last] = the value of the last scalar in vector [temp_vector]
      10) concatenate [temp_vector] onto the end of the [coefficients] vector
      11) if (length of vector [coefficients] is less than [floor0_order], continue at step 6

     }

 12) done.
 

Take note of the following properties of decode:

Given an [amplitude] integer and [coefficients] vector from packet decode as well as the [floor0_order], [floor0_rate], [floor0_bark_map_size], [floor0_amplitude_bits] and [floor0_amplitude_offset] values from floor setup, and an output vector size [n] specified by the decode process, we compute a floor output vector.

If the value [amplitude] is zero, the return value is a length [n] vector with all-zero scalars. Otherwise, begin by assuming the following definitions for the given vector to be synthesized:

The above is used to synthesize the LSP curve on a Bark-scale frequency axis, then map the result to a linear-scale frequency axis. Similarly, the below calculation synthesizes the output LSP curve [output] on a log (dB) amplitude scale, mapping it to linear amplitude in the last step:

Floor type one represents a spectral curve as a series of line segments. Synthesis constructs a floor curve using iterative prediction in a process roughly equivalent to the following simplified description:

Consider the following example, with values chosen for ease of understanding rather than representing typical configuration:

For the below example, we assume a floor setup with an [n] of 128. The list of selected X values in increasing order is 0,16,32,48,64,80,96,112 and 128. In list order, the values interleave as 0, 128, 64, 32, 96, 16, 48, 80 and 112. The corresponding list-order Y values as decoded from an example packet are 110, 20, -5, -45, 0, -25, -10, 30 and -10. We compute the floor in the following way, beginning with the first line:

We now draw new logical lines to reflect the correction to new_Y, and iterate for X positions 32 and 96:

Although the new Y value at X position 96 is unchanged, it is still used later as an endpoint for further refinement. From here on, the pattern should be clear; we complete the floor computation as follows:

A more efficient algorithm with carefully defined integer rounding behavior is used for actual decode, as described later. The actual algorithm splits Y value computation and line plotting into two steps with modifications to the above algorithm to eliminate noise accumulation through integer roundoff/truncation.

A list of floor X values is stored in the packet header in interleaved format (used in list order during packet decode and synthesis). This list is split into partitions, and each partition is assigned to a partition class. X positions 0 and [n] are implicit and do not belong to an explicit partition or partition class.

A partition class consists of a representation vector width (the number of Y values which the partition class encodes at once), a 'subclass' value representing the number of alternate entropy books the partition class may use in representing Y values, the list of [subclass] books and a master book used to encode which alternate books were chosen for representation in a given packet. The master/subclass mechanism is meant to be used as a flexible representation cascade while still using codebooks only in a scalar context.

  1) [floor1_partitions] = read 5 bits as unsigned integer
  2) [maximum_class] = -1
  3) iterate [i] over the range 0 ... [floor1_partitions]-1 {
       
        4) vector [floor1_partition_class_list] element [i] = read 4 bits as unsigned integer

     }

  5) [maximum_class] = largest integer scalar value in vector [floor1_partition_class_list]
  6) iterate [i] over the range 0 ... [maximum_class] {

        7) vector [floor1_class_dimensions] element [i] = read 3 bits as unsigned integer and add 1
	8) vector [floor1_class_subclasses] element [i] = read 2 bits as unsigned integer
        9) if ( vector [floor1_class_subclasses] element [i] is nonzero ) {
            
             10) vector [floor1_class_masterbooks] element [i] = read 8 bits as unsigned integer
           
           }

       11) iterate [j] over the range 0 ... (2 exponent [floor1_class_subclasses] element [i]) - 1  {

             12) array [floor1_subclass_books] element [i],[j] = 
                 read 8 bits as unsigned integer and subtract one
           }
      }

 13) [floor1_multiplier] = read 2 bits as unsigned integer and add one
 14) [rangebits] = read 4 bits as unsigned integer
 15) vector [floor1_X_list] element [0] = 0
 16) vector [floor1_X_list] element [1] = 2 exponent [rangebits];
 17) [floor1_values] = 2
 18) iterate [i] over the range 0 ... [floor1_partitions]-1 {

       19) [current_class_number] = vector [floor1_partition_class_list] element [i]
       20) iterate [j] over the range 0 ... ([floor1_class_dimensions] element [current_class_number])-1 {
             21) vector [floor1_X_list] element ([floor1_values]) = 
                 read [rangebits] bits as unsigned integer
             22) increment [floor1_values] by one
           }
     }
 
 23) done

An end-of-packet condition while reading any aspect of a floor 1 configuration during setup renders a stream undecodable. In addition, a [floor1_class_masterbooks] or [floor1_subclass_books] scalar element greater than the highest numbered codebook configured in this stream is an error condition that renders the stream undecodable.

  1) [nonzero] = read 1 bit as boolean

  1) [range] = vector { 256, 128, 86, 64 } element ([floor1_multiplier]-1)
  2) vector [floor1_Y] element [0] = read ilog([range]-1) bits as unsigned integer
  3) vector [floor1_Y] element [1] = read ilog([range]-1) bits as unsigned integer
  4) [offset] = 2;
  5) iterate [i] over the range 0 ... [floor1_partitions]-1 {

       6) [class] = vector [floor1_partition_class]  element [i]
       7) [cdim]  = vector [floor1_class_dimensions] element [class]
       8) [cbits] = vector [floor1_class_subclasses] element [class]
       9) [csub]  = (2 exponent [cbits])-1
      10) [cval]  = 0
      11) if ( [cbits] is greater than zero ) {
 
             12) [cval] = read from packet using codebook number
                 (vector [floor1_class_masterbooks] element [class]) in scalar context
          }
      
      13) iterate [j] over the range 0 ... [cdim]-1 {
       
             14) [book] = array [floor1_subclass_books] element [class],([cval] bitwise AND [csub])
             15) [cval] = [cval] right shifted [cbits] bits
	     16) if ( [book] is not less than zero ) {
	     
	           17) vector [floor1_Y] element ([j]+[offset]) = read from packet using codebook 
                       [book] in scalar context

                 } else [book] is less than zero {

	           18) vector [floor1_Y] element ([j]+[offset]) = 0

                 }
          }
             
      19) [offset] = [offset] + [cdim]
         
     }
  
 20) done

  1) [range] = vector { 256, 128, 86, 64 } element ([floor1_multiplier]-1)
  2) vector [floor1_step2_flag] element [0] = set
  3) vector [floor1_step2_flag] element [1] = set
  4) vector [floor1_final_Y] element [0] = vector [floor1_Y] element [0]
  5) vector [floor1_final_Y] element [1] = vector [floor1_Y] element [1]
  6) iterate [i] over the range 2 ... [floor1_values]-1 {
    
       7) [low_neighbor_offset] = low_neighbor([floor1_X_list],[i])
       8) [high_neighbor_offset] = high_neighbor([floor1_X_list],[i])

       9) [predicted] = render_point( vector [floor1_X_list] element [low_neighbor_offset],
				      vector [floor1_final_Y] element [low_neighbor_offset],
                                      vector [floor1_X_list] element [high_neighbor_offset],
				      vector [floor1_final_Y] element [high_neighbor_offset],
                                      vector [floor1_X_list] element [i] )

      10) [val] = vector [floor1_Y] element [i]
      11) [highroom] = [range] - [predicted]
      12) [lowroom]  = [predicted]
      13) if ( [highroom] is less than [lowroom] ) {

            14) [room] = [highroom] * 2
         
          } else [highroom] is not less than [lowroom] {
		      
            15) [room] = [lowroom] * 2
        
          }

      16) if ( [val] is nonzero ) {

            17) vector [floor1_step2_flag] element [low_neighbor_offset] = set
            18) vector [floor1_step2_flag] element [high_neighbor_offset] = set
            19) vector [floor1_step2_flag] element [i] = set
            20) if ( [val] is greater than or equal to [room] ) {
 
                  21) if ( [highroom] is greater than [lowroom] ) {

                        22) vector [floor1_final_Y] element [i] = [val] - [lowroom] + [predicted]
		     
		      } else [highroom] is not greater than [lowroom] {
              
                        23) vector [floor1_final_Y] element [i] = [predicted] - [val] + [highroom] - 1
                   
                      }
               
                } else [val] is less than [room] {
		 
		  24) if ([val] is odd) {
                 
                        25) vector [floor1_final_Y] element [i] = 
                            [predicted] - (([val] + 1) divided by  2 using integer division)

                      } else [val] is even {

                        26) vector [floor1_final_Y] element [i] = 
                            [predicted] + ([val] / 2 using integer division)
                          
                      }

                }      

          } else [val] is zero {

            27) vector [floor1_step2_flag] element [i] = unset
            28) vector [floor1_final_Y] element [i] = [predicted]

          }

     }

 29) done

  1) [hx] = 0
  2) [lx] = 0
  3) [ly] = vector [floor1_final_Y]' element [0] * [floor1_multiplier]
  4) iterate [i] over the range 1 ... [floor1_values]-1 {

       5) if ( [floor1_step2_flag]' element [i] is set ) {

             6) [hy] = [floor1_final_Y]' element [i] * [floor1_multiplier]
 	     7) [hx] = [floor1_X_list]' element [i]
             8) render_line( [lx], [ly], [hx], [hy], [floor] )
             9) [lx] = [hx]
	    10) [ly] = [hy]
          }
     }
 
 11) if ( [hx] is less than [n] ) {

        12) render_line( [hx], [hy], [n], [hy], [floor] )

     }

 13) if ( [hx] is greater than [n] ) {

            14) truncate vector [floor] to [n] elements

     }
 
 15) for each scalar in vector [floor], perform a lookup substitution using 
     the scalar value from [floor] as an offset into the vector [floor1_inverse_dB_static_table]

 16) done

Header decode for all three residue types is identical.

  1) [residue_begin] = read 24 bits as unsigned integer
  2) [residue_end] = read 24 bits as unsigned integer
  3) [residue_partition_size] = read 24 bits as unsigned integer and add one
  4) [residue_classifications] = read 6 bits as unsigned integer and add one
  5) [residue_classbook] = read 8 bits as unsigned integer

[residue_begin] and [residue_end] select the specific sub-portion of each vector that is actually coded; it implements akin to a bandpass where, for coding purposes, the vector effectively begins at element [residue_begin] and ends at [residue_end]. Preceding and following values in the unpacked vectors are zeroed. Note that for residue type 2, these values as well as [residue_partition_size]apply to the interleaved vector, not the individual vectors before interleave. [residue_partition_size] is as explained above, [residue_classifications] is the number of possible classification to which a partition can belong and [residue_classbook] is the codebook number used to code classification codewords. The number of dimensions in book [residue_classbook] determines how many classification values are grouped into a single classification codeword.

Next we read a bitmap pattern that specifies which partition classes code values in which passes.

  1) iterate [i] over the range 0 ... [residue_classifications]-1 {
  
       2) [high_bits] = 0
       3) [low_bits] = read 3 bits as unsigned integer
       4) [bitflag] = read one bit as boolean
       5) if ( [bitflag] is set ) then [high_bits] = read five bits as unsigned integer
       6) vector [residue_cascade] element [i] = [high_bits] * 8 + [low_bits]
     }
  7) done

Finally, we read in a list of book numbers, each corresponding to specific bit set in the cascade bitmap. We loop over the possible codebook classifications and the maximum possible number of encoding stages (8 in Vorbis I, as constrained by the elements of the cascade bitmap being eight bits):

  1) iterate [i] over the range 0 ... [residue_classifications]-1 {
  
       2) iterate [j] over the range 0 ... 7 {
  
            3) if ( vector [residue_cascade] element [i] bit [j] is set ) {

                 4) array [residue_books] element [i][j] = read 8 bits as unsigned integer

               } else {

                 5) array [residue_books] element [i][j] = unused

               }
          }
      }

  6) done

An end-of-packet condition at any point in header decode renders the stream undecodable. In addition, any codebook number greater than the maximum numbered codebook set up in this stream also renders the stream undecodable.

Format 0 and 1 packet decode is identical except for specific partition interleave. Format 2 packet decode can be built out of the format 1 decode process. Thus we describe first the decode infrastructure identical to all three formats.

In addition to configuration information, the residue decode process is passed the number of vectors in the submap bundle and a vector of flags indicating if any of the vectors are not to be decoded. If the passed in number of vectors is 3 and vector number 1 is marked 'do not decode', decode skips vector 1 during the decode loop. However, even 'do not decode' vectors are allocated and zeroed.

Depending on the values of [residue_begin] and [residue_end], it is obvious that the encoded portion of a residue vector may be the entire possible residue vector or some other strict subset of the actual residue vector size with zero padding at either uncoded end. However, it is also possible to set [residue_begin] and [residue_end] to specify a range partially or wholly beyond the maximum vector size. Before beginning residue decode, limit [residue_begin] and [residue_end] to the maximum possible vector size as follows. We assume that the number of vectors being encoded, [ch] is provided by the higher level decoding process.

  1) [actual_size] = current blocksize/2;
  2) if residue encoding is format 2
       3) [actual_size] = [actual_size] * [ch];
  4) [limit_residue_begin] = maximum of ([residue_begin],[actual_size]);
  5) [limit_residue_end] = maximum of ([residue_end],[actual_size]);

The following convenience values are conceptually useful to clarifying the decode process:

  1) [classwords_per_codeword] = [codebook_dimensions] value of codebook [residue_classbook]
  2) [n_to_read] = [limit_residue_end] - [limit_residue_begin]
  3) [partitions_to_read] = [n_to_read] / [residue_partition_size]

Packet decode proceeds as follows, matching the description offered earlier in the document.

  1) allocate and zero all vectors that will be returned.
  2) if ([n_to_read] is zero), stop; there is no residue to decode.
  3) iterate [pass] over the range 0 ... 7 {

       4) [partition_count] = 0

       5) while [partition_count] is less than [partitions_to_read]

            6) if ([pass] is zero) {
     
                 7) iterate [j] over the range 0 .. [ch]-1 {

                      8) if vector [j] is not marked 'do not decode' {

                           9) [temp] = read from packet using codebook [residue_classbook] in scalar context
                          10) iterate [i] descending over the range [classwords_per_codeword]-1 ... 0 {

                               11) array [classifications] element [j],([i]+[partition_count]) =
                                   [temp] integer modulo [residue_classifications]
                               12) [temp] = [temp] / [residue_classifications] using integer division

                              }
      
                         }
            
                    }
          
               }

           13) iterate [i] over the range 0 .. ([classwords_per_codeword] - 1) while [partition_count] 
               is also less than [partitions_to_read] {

                 14) iterate [j] over the range 0 .. [ch]-1 {
   
                      15) if vector [j] is not marked 'do not decode' {
   
                           16) [vqclass] = array [classifications] element [j],[partition_count]
                           17) [vqbook] = array [residue_books] element [vqclass],[pass]
                           18) if ([vqbook] is not 'unused') {
   
                                19) decode partition into output vector number [j], starting at scalar 
                                    offset [limit_residue_begin]+[partition_count]*[residue_partition_size] using 
                                    codebook number [vqbook] in VQ context
                          }
                     }
   
                 20) increment [partition_count] by one

               }
          }
     }
 
 21) done

An end-of-packet condition during packet decode is to be considered a nominal occurrence. Decode returns the result of vector decode up to that point.

Format zero decodes partitions exactly as described earlier in the 'Residue Format: residue 0' section. The following pseudocode presents the same algorithm. Assume:

 1) [step] = [n] / [codebook_dimensions]
 2) iterate [i] over the range 0 ... [step]-1 {

      3) vector [entry_temp] = read vector from packet using current codebook in VQ context
      4) iterate [j] over the range 0 ... [codebook_dimensions]-1 {

           5) vector [v] element ([offset]+[i]+[j]*[step]) =
	        vector [v] element ([offset]+[i]+[j]*[step]) +
                vector [entry_temp] element [j]

         }

    }

  6) done

Format 1 decodes partitions exactly as described earlier in the 'Residue Format: residue 1' section. The following pseudocode presents the same algorithm. Assume:

 1) [i] = 0
 2) vector [entry_temp] = read vector from packet using current codebook in VQ context
 3) iterate [j] over the range 0 ... [codebook_dimensions]-1 {

      4) vector [v] element ([offset]+[i]) =
	  vector [v] element ([offset]+[i]) +
          vector [entry_temp] element [j]
      5) increment [i]

    }
 
  6) if ( [i] is less than [n] ) continue at step 2
  7) done

Format 2 is reducible to format 1. It may be implemented as an additional step prior to and an additional post-decode step after a normal format 1 decode.

Format 2 handles 'do not decode' vectors differently than residue 0 or 1; if all vectors are marked 'do not decode', no decode occurrs. However, if at least one vector is to be decoded, all the vectors are decoded. We then request normal format 1 to decode a single vector representing all output channels, rather than a vector for each channel. After decode, deinterleave the vector into independent vectors, one for each output channel. That is:

The "ilog(x)" function returns the position number (1 through n) of the highest set bit in the two's complement integer value [x]. Values of [x] less than zero are defined to return zero.

  1) [return_value] = 0;
  2) if ( [x] is greater than zero ){
      
       3) increment [return_value];
       4) logical shift [x] one bit to the right, padding the MSb with zero
       5) repeat at step 2)

     }

   6) done

Examples:

"float32_unpack(x)" is intended to translate the packed binary representation of a Vorbis codebook float value into the representation used by the decoder for floating point numbers. For purposes of this example, we will unpack a Vorbis float32 into a host-native floating point number.

  1) [mantissa] = [x] bitwise AND 0x1fffff (unsigned result)
  2) [sign] = [x] bitwise AND 0x80000000 (unsigned result)
  3) [exponent] = ( [x] bitwise AND 0x7fe00000) shifted right 21 bits (unsigned result)
  4) if ( [sign] is nonzero ) then negate [mantissa]
  5) return [mantissa] * ( 2 ^ ( [exponent] - 788 ) )

"lookup1_values(codebook_entries,codebook_dimensions)" is used to compute the correct length of the value index for a codebook VQ lookup table of lookup type 1. The values on this list are permuted to construct the VQ vector lookup table of size [codebook_entries].

The return value for this function is defined to be 'the greatest integer value for which [return_value] to the power of [codebook_dimensions] is less than or equal to [codebook_entries]'.

"low_neighbor(v,x)" finds the position n in vector [v] of the greatest value scalar element for which n is less than [x] and vector [v] element n is less than vector [v] element [x].

  1)  [dy] = [y1] - [y0]
  2) [adx] = [x1] - [x0]
  3) [ady] = absolute value of [dy]
  4) [err] = [ady] * ([X] - [x0])
  5) [off] = [err] / [adx] using integer division
  6) if ( [dy] is less than zero ) {

       7) [Y] = [y0] - [off]

     } else {

       8) [Y] = [y0] + [off]
  
     }

  9) done

  1)   [dy] = [y1] - [y0]
  2)  [adx] = [x1] - [x0]
  3)  [ady] = absolute value of [dy]
  4) [base] = [dy] / [adx] using integer division
  5)    [x] = [x0]
  6)    [y] = [y0]
  7)  [err] = 0

  8) if ( [dy] is less than 0 ) {

        9) [sy] = [base] - 1

     } else {

       10) [sy] = [base] + 1

     }

 11) [ady] = [ady] - (absolute value of [base]) * [adx]
 12) vector [v] element [x] = [y]

 13) iterate [x] over the range [x0]+1 ... [x1]-1 {

       14) [err] = [err] + [ady];
       15) if ( [err] >= [adx] ) {

             16) [err] = [err] - [adx]
             17)   [y] = [y] + [sy]

           } else {

             18) [y] = [y] + [base]
   
           }

       19) vector [v] element [x] = [y]

     }