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