From f1b2382773bc15f92454c6079b1728edaf1865b4 Mon Sep 17 00:00:00 2001 From: Monty Date: Tue, 16 Jul 2002 09:24:55 +0000 Subject: [PATCH] codebook doc -> CVS svn path=/trunk/vorbis/; revision=3635 --- doc/vorbis-spec-codebook.html | 399 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 399 insertions(+) create mode 100644 doc/vorbis-spec-codebook.html diff --git a/doc/vorbis-spec-codebook.html b/doc/vorbis-spec-codebook.html new file mode 100644 index 0000000..ad69f57 --- /dev/null +++ b/doc/vorbis-spec-codebook.html @@ -0,0 +1,399 @@ +xiph.org: Ogg Vorbis documentation + +

+ +

+Ogg Vorbis I format specification: probability model and codebooks +

+ +Last update to this document: July 16, 2002
+ +

Overview

+ +Unlike practically every other mainstream audio codec, Vorbis has no +statically configured probability model, instead packing all entropy +decoding configuration, VQ and Huffman, into the bitstream itself in +the third header, the codec setup header. This packed configuration +consists of multiple 'codebooks', each containing a specific +Huffman-equivalent representation for decoding compressed codewords as +well as an optional lookup table of output vector values to which a +decoded Huffman value is applied as an offset, generating the final +decoded output corresponding to a given compressed codeword. + +

bitwise operation

+ +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 the Vorbis bitpacking +convention. + +

Packed Codebook Format

+ +For purposes of the below examples, we assume that the storage +system's native byte width is eight bits. This is not universally +true; see the Vorbis bitpacking +convention document for discussion relating to non-eight-bit +bytes.

+ +

codebook decode

+ +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)
+
+

+ +We now read the list of codeword lengths; each entry (numbering a +total of [codebook_entries]) is assigned a codeword length. However, +decode of lengths is according to whether the [ordered] flag is +set or unset. + +

If the [ordered] flag is unset, the codeword list is not + length ordered and the decoder needs to read each codeword length + one-by-one.

The decoder first reads one additional bit flag, the + [sparse] flag. This flag determines whether or not the + codebook contains unused entries that are not to be included in the + codeword decode tree:

+ +

+byte 8: [             X 1 ] [sparse] flag (1 bit)
+

+ + The decoder now performs for each of the [codebook_entries] code book entries: + +

+  
+  1) if([sparse] is set){
+
+         2) [flag] = read one bit;
+         3) if([flag] is set){
+
+              4) [length] = read a five bit unsigned integer;
+              5) codeword length for this entry is [length]+1;
+
+            } else {
+
+              6) this entry is unused.  mark it as such.
+
+            }
+
+     } else the sparse flag is not set {
+
+        7) [length] = read a five bit unsigned integer;
+        8) the codeword length for this entry is [length]+1;
+        
+     }
+
+

+ +

If the [ordered] flag is set, the codeword list for this + codebook is encoded in ascending length order. Rather than reading + a length for every codeword, the encoder reads the number of + codewords per length. That is, beginning at entry zero: + +

+  1) [current_entry] = 0;
+  2) [current_length] = read a five bit unsigned integer and add one;
+  3) [number] = read ilog([codebook_entries] - [current_entry]) bits as an unsigned integer
+  4) set the entries [current_entry] through [current_entry]+[n]-1 
+     inclusive of the [codebook_codeword_lengths] array to [current_length]
+  5) set [current_entry] to [number] + [current_entry]
+  6) increment [current_length]
+  7) if [current_entry] is greater than [codebook_entries] ERROR CONDITION; the decoder will
+     not be able to read this stream.
+  8) if [current_entry] is less than [codebook_entries], repeat process starting at 3)
+  9) done.
+

+ +

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

No lookup +
Implicitly populated value mapping (lattice VQ) +
Explicitly populated value mapping (tessellated or 'foam' VQ) +

+ +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]: +

Lookup type zero indicates no lookup to be read. Proceed past +lookup decode. + +

Lookup types one and two are similar, differing only in the +number of lookup values to be read. Lookup type one reads a list of +values that are permuted in a set pattern to build a list of vectors, +each vector of order [codebook_dimensions] scalars. Lookup +type two builds the same vector list, but reads each scalar for each +vector explicitly, rather than building vectors from a smaller list of +possible scalar values. Lookup decode proceeds as follows: + +

+  1) [codebook_minimum_value] = float32_unpack( read 32 bits as an unsigned integer) 
+  2) [codebook_delta_value] = float32_unpack( read 32 bits as an unsigned integer) 
+  3) [codebook_value_bits] = read 4 bits as an unsigned integer and add one
+  4) [codebook_sequence_p] = read 1 bit as a boolean flag
+
+  if ( [codebook_lookup_type] is 1 ) {
+   
+     5) [codebook_lookup_values] = lookup1_values( [codebook_entries], [codebook_dimensions] )
+
+  } else {
+
+     6) [codebook_lookup_values] = [codebook_entries] * [codebook_dimensions]
+
+  }
+
+  7) read a total of [codebook_lookup_values] unsigned integers of [codebook_value_bits] each; 
+     store these in order in the array [codebook_multiplicands]
+
+

A [codebook_lookup_type] of greater than two is reserved and indicates +a stream that's not decodable by the specification in this document. + +

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

+ +

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 that 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.

+ +

VQ lookup table vector representation

+ +Decoding the VQ lookup table vectors relies on the following values: +

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

+ +Decoding a specific vector in the vector lookup table proceeds +according to [codebook_lookup_type].

+ +

Vector value decode: Lookup type 1

+ +Lookup type one specifies a lattice VQ lookup table built +algorithmically from a list of scalar values. The scalar values of a +specific vector entry are calculated as follows, assuming +[lookup_offset] specifies the vector to be +calculated:

+ +

+  1) [last] = zero;
+  2) [index_divisor] = one;
+  3) iterate [codebook_dimensions] times, once for each scalar value in the vector {
+       
+       4) [multiplicand_offset] = ( [lookup_offset] divided by [index_divisor] using integer 
+          division ) integer modulo [codebook_lookup_values]
+
+       5) set this iteration's scalar value = 
+            ( [codebook_multiplicands] array element number [multiplicand_offset] ) *
+            [codebook_delta_value] + [codebook_minimum_value] + [last];
+
+       6) if ( [codebook_sequence_p] is set ) then set [last] = this iteration's scalar value
+
+       7) [index_divisor] = [index_divisor] * [codebook_lookup_values]
+
+     }
+ 
+  8) vector calculation completed.
+

+ +

Vector value decode: Lookup type 2

+ +Lookup type two specifies a VQ lookup table in which each scalar in +each vector is explicitly set by the [codebook_multiplicands] +array in a one-to-one mapping. The scalar values of a specific vector +entry in the lookup table are calculated as follows, assuming +[lookup_offset] specifies the vector to be calculated:

+ +

+  1) [last] = zero;
+  2) [multiplicand_offset] = [lookup_offset] * [codebook_dimensions]
+  3) iterate [codebook_dimensions] times, once for each scalar value in the vector {
+
+       4) set this iteration's scalar value = 
+            ( [codebook_multiplicands] array element number [multiplicand_offset] ) *
+            [codebook_delta_value] + [codebook_minimum_value] + [last];
+
+       5) if ( [codebook_sequence_p] is set ) then set [last] = this iteration's scalar value
+
+       6) increment [multiplicand_offset]
+
+     }
+ 
+  7) vector calculation completed.
+

+ +

Use of the codebook abstraction

+ +The decoder uses the codebook abstraction much as it does the +bit-unpacking convention; a specific codebook reads a +codeword from the bitstream, decoding it into an entry number, and then +returns that entry number to the decoder (when used in a scalar +entropy coding context), or uses that entry number as an offset into +the VQ lookup table, returning a vector of values (when used in a context +desiring a VQ value). Scalar or VQ context is always explicit; any call +to the codebook mechanism requests either a scalar entry number or a +lookup vector.

+ +Note that VQ lookup type zero indicates that there is no lookup table; +requesting decode using a codebook of lookup type 0 in any context +expecting a vector return value (even in a case where a vector of +dimension one) is forbidden. If decoder setup or decode requests such +an action, that is an error condition rendering the packet +undecodable.

+ +Using a codebook to read from the packet bitstream consists first of +reading and decoding the next codeword in the bitstream. The decoder +reads bits until the accumulated bits match a codeword in the +codebook. This process can be though of as logically walking the +Huffman decode tree by reading one bit at a time from the bitstream, +and using the bit as a decision boolean to take the 0 branch (left in +the above examples) or the 1 branch (right in the above examples). +Walking the tree finishes when the decode process hits a leaf in the +decision tree; the result is the entry number corresponding to that +leaf. Reading past the end of a packet propagates the 'end-of-stream' +condition to the decoder.

+ +When used in a scalar context, the resulting codeword entry is the +desired return value.

+ +When used in a VQ context, the codeword entry number is used as an +offset into the VQ lookup table. The value returned to the decoder is +the vector of scalars corresponding to this offset.

+ +

+ + + +Ogg is a Xiph.org Foundation effort +to protect essential tenets of Internet multimedia from corporate +hostage-taking; Open Source is the net's greatest tool to keep +everyone honest. See About +the Xiph.org Foundation for details. +

+ +Ogg Vorbis is the first Ogg audio CODEC. Anyone may freely use and +distribute the Ogg and Vorbis specification, whether in a private, +public or corporate capacity. However, the Xiph.org Foundation and +the Ogg project (xiph.org) reserve the right to set the Ogg Vorbis +specification and certify specification compliance.

+ +Xiph.org's Vorbis software CODEC implementation is distributed under a +BSD-like license. This does not restrict third parties from +distributing independent implementations of Vorbis software under +other licenses.

+ + + -- 2.7.4