libvorbis-1.0.1/doc/framing.html

   1 <HTML><HEAD><TITLE>xiph.org: Ogg Vorbis documentation</TITLE>
   2 <BODY bgcolor="#ffffff" text="#202020" link="#006666" vlink="#000000">
   3 <nobr><a href="http://www.xiph.org/ogg/index.html"><img src="white-ogg.png" border=0><img
   4 src="vorbisword2.png" border=0></a></nobr><p>
   5
   6 <h1><font color=#000070>
   7 Ogg logical bitstream framing
   8 </font></h1>
   9
  10 <em>Last update to this document: July 14, 2002</em><br>
  11
  12 <h2>Ogg bitstreams</h2>
  13
  14 The Ogg transport bitstream is designed to provide framing, error
  15 protection and seeking structure for higher-level codec streams that
  16 consist of raw, unencapsulated data packets, such as the Vorbis audio
  17 codec or Tarkin video codec.
  18
  19 <h2>Application example: Vorbis</h2>
  20 Vorbis encodes short-time blocks of PCM data into raw packets of
  21 bit-packed data.  These raw packets may be used directly by transport
  22 mechanisms that provide their own framing and packet-separation
  23 mechanisms (such as UDP datagrams).  For stream based storage (such as
  24 files) and transport (such as TCP streams or pipes), Vorbis uses the
  25 Ogg bitstream format to provide framing/sync, sync recapture
  26 after error, landmarks during seeking, and enough information to
  27 properly separate data back into packets at the original packet
  28 boundaries without relying on decoding to find packet boundaries.<p>
  29
  30 <h2>Design constraints for Ogg bitstreams</h2>
  31
  32 <ol><li>True streaming; we must not need to seek to build a 100%
  33    complete bitstream.
  34
  35 <li> Use no more than approximately 1-2% of bitstream bandwidth for
  36    packet boundary marking, high-level framing, sync and seeking.
  37
  38 <li> Specification of absolute position within the original sample
  39    stream.
  40
  41 <li> Simple mechanism to ease limited editing, such as a simplified
  42    concatenation mechanism.
  43
  44 <li> Detection of corruption, recapture after error and direct, random
  45    access to data at arbitrary positions in the bitstream.
  46 </ol>
  47
  48 <h2>Logical and Physical Bitstreams</h2>
  49
  50 A <em>logical</em> Ogg bitstream is a contiguous stream of
  51 sequential pages belonging only to the logical bitstream.  A
  52 <em>physical</em> Ogg bitstream is constructed from one or more
  53 than one logical Ogg bitstream (the simplest physical bitstream
  54 is simply a single logical bitstream).  We describe below the exact
  55 formatting of an Ogg logical bitstream.  Combining logical
  56 bitstreams into more complex physical bitstreams is described in the
  57 <a href="oggstream.html">Ogg bitstream overview</a>.  The exact
  58 mapping of raw Vorbis packets into a valid Ogg Vorbis physical
  59 bitstream is described in <a href="vorbis-stream.html">Vorbis
  60 bitstream mapping</a>.
  61
  62 <h2>Bitstream structure</h2>
  63
  64 An Ogg stream is structured by dividing incoming packets into
  65 segments of up to 255 bytes and then wrapping a group of contiguous
  66 packet segments into a variable length page preceded by a page
  67 header.  Both the header size and page size are variable; the page
  68 header contains sizing information and checksum data to determine
  69 header/page size and data integrity.<p>
  70
  71 The bitstream is captured (or recaptured) by looking for the beginning
  72 of a page, specifically the capture pattern.  Once the capture pattern
  73 is found, the decoder verifies page sync and integrity by computing
  74 and comparing the checksum. At that point, the decoder can extract the
  75 packets themselves.<p>
  76
  77 <h3>Packet segmentation</h3>
  78
  79 Packets are logically divided into multiple segments before encoding
  80 into a page. Note that the segmentation and fragmentation process is a
  81 logical one; it's used to compute page header values and the original
  82 page data need not be disturbed, even when a packet spans page
  83 boundaries.<p>
  84
  85 The raw packet is logically divided into [n] 255 byte segments and a
  86 last fractional segment of < 255 bytes.  A packet size may well
  87 consist only of the trailing fractional segment, and a fractional
  88 segment may be zero length.  These values, called "lacing values" are
  89 then saved and placed into the header segment table.<p>
  90
  91 An example should make the basic concept clear:<p>
  92
  93 <pre>
  94 <tt>
  95 raw packet:
  96   ___________________________________________
  97  |______________packet data__________________| 753 bytes
  98
  99 lacing values for page header segment table: 255,255,243
 100 </tt>
 101 </pre>
 102
 103 We simply add the lacing values for the total size; the last lacing
 104 value for a packet is always the value that is less than 255. Note
 105 that this encoding both avoids imposing a maximum packet size as well
 106 as imposing minimum overhead on small packets (as opposed to, eg,
 107 simply using two bytes at the head of every packet and having a max
 108 packet size of 32k.  Small packets (<255, the typical case) are
 109 penalized with twice the segmentation overhead). Using the lacing
 110 values as suggested, small packets see the minimum possible
 111 byte-aligned overheade (1 byte) and large packets, over 512 bytes or
 112 so, see a fairly constant ~.5% overhead on encoding space.<p>
 113
 114 Note that a lacing value of 255 implies that a second lacing value
 115 follows in the packet, and a value of < 255 marks the end of the
 116 packet after that many additional bytes.  A packet of 255 bytes (or a
 117 multiple of 255 bytes) is terminated by a lacing value of 0:<p>
 118
 119 <pre><tt>
 120 raw packet:
 121   _______________________________
 122  |________packet data____________|          255 bytes
 123
 124 lacing values: 255, 0
 125 </tt></pre>
 126
 127 Note also that a 'nil' (zero length) packet is not an error; it
 128 consists of nothing more than a lacing value of zero in the header.<p>
 129
 130 <h3>Packets spanning pages</h3>
 131
 132 Packets are not restricted to beginning and ending within a page,
 133 although individual segments are, by definition, required to do so.
 134 Packets are not restricted to a maximum size, although excessively
 135 large packets in the data stream are discouraged; the Ogg
 136 bitstream specification strongly recommends nominal page size of
 137 approximately 4-8kB (large packets are foreseen as being useful for
 138 initialization data at the beginning of a logical bitstream).<p>
 139
 140 After segmenting a packet, the encoder may decide not to place all the
 141 resulting segments into the current page; to do so, the encoder places
 142 the lacing values of the segments it wishes to belong to the current
 143 page into the current segment table, then finishes the page.  The next
 144 page is begun with the first value in the segment table belonging to
 145 the next packet segment, thus continuing the packet (data in the
 146 packet body must also correspond properly to the lacing values in the
 147 spanned pages. The segment data in the first packet corresponding to
 148 the lacing values of the first page belong in that page; packet
 149 segments listed in the segment table of the following page must begin
 150 the page body of the subsequent page).<p>
 151
 152 The last mechanic to spanning a page boundary is to set the header
 153 flag in the new page to indicate that the first lacing value in the
 154 segment table continues rather than begins a packet; a header flag of
 155 0x01 is set to indicate a continued packet.  Although mandatory, it
 156 is not actually algorithmically necessary; one could inspect the
 157 preceding segment table to determine if the packet is new or
 158 continued.  Adding the information to the packet_header flag allows a
 159 simpler design (with no overhead) that needs only inspect the current
 160 page header after frame capture.  This also allows faster error
 161 recovery in the event that the packet originates in a corrupt
 162 preceding page, implying that the previous page's segment table
 163 cannot be trusted.<p>
 164
 165 Note that a packet can span an arbitrary number of pages; the above
 166 spanning process is repeated for each spanned page boundary.  Also a
 167 'zero termination' on a packet size that is an even multiple of 255
 168 must appear even if the lacing value appears in the next page as a
 169 zero-length continuation of the current packet.  The header flag
 170 should be set to 0x01 to indicate that the packet spanned, even though
 171 the span is a nil case as far as data is concerned.<p>
 172
 173 The encoding looks odd, but is properly optimized for speed and the
 174 expected case of the majority of packets being between 50 and 200
 175 bytes (note that it is designed such that packets of wildly different
 176 sizes can be handled within the model; placing packet size
 177 restrictions on the encoder would have only slightly simplified design
 178 in page generation and increased overall encoder complexity).<p>
 179
 180 The main point behind tracking individual packets (and packet
 181 segments) is to allow more flexible encoding tricks that requiring
 182 explicit knowledge of packet size. An example is simple bandwidth
 183 limiting, implemented by simply truncating packets in the nominal case
 184 if the packet is arranged so that the least sensitive portion of the
 185 data comes last.<p>
 186
 187 <h3>Page header</h3>
 188
 189 The headering mechanism is designed to avoid copying and re-assembly
 190 of the packet data (ie, making the packet segmentation process a
 191 logical one); the header can be generated directly from incoming
 192 packet data.  The encoder buffers packet data until it finishes a
 193 complete page at which point it writes the header followed by the
 194 buffered packet segments.<p>
 195
 196 <h4>capture_pattern</h4>
 197
 198  A header begins with a capture pattern that simplifies identifying
 199  pages; once the decoder has found the capture pattern it can do a more
 200  intensive job of verifying that it has in fact found a page boundary
 201  (as opposed to an inadvertent coincidence in the byte stream).<p>
 202
 203 <pre><tt>
 204  byte value
 205
 206   0  0x4f 'O'
 207   1  0x67 'g'
 208   2  0x67 'g'
 209   3  0x53 'S'
 210 </tt></pre>
 211
 212 <h4>stream_structure_version</h4>
 213
 214  The capture pattern is followed by the stream structure revision:
 215
 216 <pre><tt>
 217  byte value
 218
 219   4  0x00
 220 </tt></pre>
 221
 222 <h4>header_type_flag</h4>
 223
 224  The header type flag identifies this page's context in the bitstream:
 225
 226 <pre><tt>
 227  byte value
 228
 229   5  bitflags: 0x01: unset = fresh packet
 230                        set = continued packet
 231                0x02: unset = not first page of logical bitstream
 232                        set = first page of logical bitstream (bos)
 233                0x04: unset = not last page of logical bitstream
 234                        set = last page of logical bitstream (eos)
 235 </tt></pre>
 236
 237 <h4>absolute granule position</h4>
 238
 239  (This is packed in the same way the rest of Ogg data is packed; LSb
 240  of LSB first.  Note that the 'position' data specifies a 'sample'
 241  number (eg, in a CD quality sample is four octets, 16 bits for left
 242  and 16 bits for right; in video it would likely be the frame number.
 243  It is up to the specific codec in use to define the semantic meaning
 244  of the granule position value).  The position specified is the total
 245  samples encoded after including all packets finished on this page
 246  (packets begun on this page but continuing on to the next page do not
 247  count).  The rationale here is that the position specified in the
 248  frame header of the last page tells how long the data coded by the
 249  bitstream is.  A truncated stream will still return the proper number
 250  of samples that can be decoded fully.
 251 <p>
 252  A special value of '-1' (in two's complement) indicates that no packets
 253  finish on this page.
 254
 255 <pre><tt>
 256  byte value
 257
 258   6  0xXX LSB
 259   7  0xXX
 260   8  0xXX
 261   9  0xXX
 262  10  0xXX
 263  11  0xXX
 264  12  0xXX
 265  13  0xXX MSB
 266 </tt></pre>
 267
 268 <h4>stream serial number</h4>
 269
 270  Ogg allows for separate logical bitstreams to be mixed at page
 271  granularity in a physical bitstream.  The most common case would be
 272  sequential arrangement, but it is possible to interleave pages for
 273  two separate bitstreams to be decoded concurrently.  The serial
 274  number is the means by which pages physical pages are associated with
 275  a particular logical stream.  Each logical stream must have a unique
 276  serial number within a physical stream:
 277
 278 <pre><tt>
 279  byte value
 280
 281  14  0xXX LSB
 282  15  0xXX
 283  16  0xXX
 284  17  0xXX MSB
 285 </tt></pre>
 286
 287 <h4>page sequence no</h4>
 288
 289  Page counter; lets us know if a page is lost (useful where packets
 290  span page boundaries).
 291
 292 <pre><tt>
 293  byte value
 294
 295  18  0xXX LSB
 296  19  0xXX
 297  20  0xXX
 298  21  0xXX MSB
 299 </tt></pre>
 300
 301 <h4>page checksum</h4>
 302
 303  32 bit CRC value (direct algorithm, initial val and final XOR = 0,
 304  generator polynomial=0x04c11db7).  The value is computed over the
 305  entire header (with the CRC field in the header set to zero) and then
 306  continued over the page.  The CRC field is then filled with the
 307  computed value.<p>
 308
 309  (A thorough discussion of CRC algorithms can be found in <a
 310  href="ftp://ftp.rocksoft.com/papers/crc_v3.txt">"A
 311  Painless Guide to CRC Error Detection Algorithms"</a> by Ross
 312  Williams <a
 313  href="mailto:ross@guest.adelaide.edu.au">ross@guest.adelaide.edu.au</a>.)
 314
 315 <pre><tt>
 316  byte value
 317
 318  22  0xXX LSB
 319  23  0xXX
 320  24  0xXX
 321  25  0xXX MSB
 322 </tt></pre>
 323
 324 <h4>page_segments</h4>
 325
 326  The number of segment entries to appear in the segment table. The
 327  maximum number of 255 segments (255 bytes each) sets the maximum
 328  possible physical page size at 65307 bytes or just under 64kB (thus
 329  we know that a header corrupted so as destroy sizing/alignment
 330  information will not cause a runaway bitstream.  We'll read in the
 331  page according to the corrupted size information that's guaranteed to
 332  be a reasonable size regardless, notice the checksum mismatch, drop
 333  sync and then look for recapture).<p>
 334
 335 <pre><tt>
 336  byte value
 337
 338  26 0x00-0xff (0-255)
 339 </tt></pre>
 340
 341 <h4>segment_table (containing packet lacing values)</h4>
 342
 343  The lacing values for each packet segment physically appearing in
 344  this page are listed in contiguous order.
 345
 346 <pre><tt>
 347  byte value
 348
 349  27 0x00-0xff (0-255)
 350  [...]
 351  n  0x00-0xff (0-255, n=page_segments+26)
 352 </tt></pre>
 353
 354 Total page size is calculated directly from the known header size and
 355 lacing values in the segment table. Packet data segments follow
 356 immediately after the header.<p>
 357
 358 Page headers typically impose a flat .25-.5% space overhead assuming
 359 nominal ~8k page sizes.  The segmentation table needed for exact
 360 packet recovery in the streaming layer adds approximately .5-1%
 361 nominal assuming expected encoder behavior in the 44.1kHz, 128kbps
 362 stereo encodings.<p>
 363
 364 <hr>
 365 <a href="http://www.xiph.org/">
 366 <img src="white-xifish.png" align=left border=0>
 367 </a>
 368 <font size=-2 color=#505050>
 369
 370 Ogg is a <a href="http://www.xiph.org">Xiph.org Foundation</a> effort
 371 to protect essential tenets of Internet multimedia from corporate
 372 hostage-taking; Open Source is the net's greatest tool to keep
 373 everyone honest. See <a href="http://www.xiph.org/about.html">About
 374 the Xiph.org Foundation</a> for details.
 375 <p>
 376
 377 Ogg Vorbis is the first Ogg audio CODEC.  Anyone may freely use and
 378 distribute the Ogg and Vorbis specification, whether in a private,
 379 public or corporate capacity.  However, the Xiph.org Foundation and
 380 the Ogg project (xiph.org) reserve the right to set the Ogg Vorbis
 381 specification and certify specification compliance.<p>
 382
 383 Xiph.org's Vorbis software CODEC implementation is distributed under a
 384 BSD-like license.  This does not restrict third parties from
 385 distributing independent implementations of Vorbis software under
 386 other licenses.<p>
 387
 388 Ogg, Vorbis, Xiph.org Foundation and their logos are trademarks (tm)
 389 of the <a href="http://www.xiph.org/">Xiph.org Foundation</a>.  These
 390 pages are copyright (C) 1994-2002 Xiph.org Foundation. All rights
 391 reserved.<p>
 392
 393 </body>
 394
 395