VirtualBox

source: vbox/trunk/src/libs/libvorbis-1.3.7/doc/02-bitpacking.tex@ 103131

Last change on this file since 103131 was 96468, checked in by vboxsync, 2 years ago

libs/libvorbis-1.3.7: Re-exporting, hopefully this time everything is there. bugref:10275

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.3 KB
Line 
1% -*- mode: latex; TeX-master: "Vorbis_I_spec"; -*-
2%!TEX root = Vorbis_I_spec.tex
3\section{Bitpacking Convention} \label{vorbis:spec:bitpacking}
4
5\subsection{Overview}
6
7The Vorbis codec uses relatively unstructured raw packets containing
8arbitrary-width binary integer fields. Logically, these packets are a
9bitstream in which bits are coded one-by-one by the encoder and then
10read one-by-one in the same monotonically increasing order by the
11decoder. Most current binary storage arrangements group bits into a
12native word size of eight bits (octets), sixteen bits, thirty-two bits
13or, less commonly other fixed word sizes. The Vorbis bitpacking
14convention specifies the correct mapping of the logical packet
15bitstream into an actual representation in fixed-width words.
16
17
18\subsubsection{octets, bytes and words}
19
20In most contemporary architectures, a 'byte' is synonymous with an
21'octet', that is, eight bits. This has not always been the case;
22seven, ten, eleven and sixteen bit 'bytes' have been used. For
23purposes of the bitpacking convention, a byte implies the native,
24smallest integer storage representation offered by a platform. On
25modern platforms, this is generally assumed to be eight bits (not
26necessarily because of the processor but because of the
27filesystem/memory architecture. Modern filesystems invariably offer
28bytes as the fundamental atom of storage). A 'word' is an integer
29size that is a grouped multiple of this smallest size.
30
31The most ubiquitous architectures today consider a 'byte' to be an
32octet (eight bits) and a word to be a group of two, four or eight
33bytes (16, 32 or 64 bits). Note however that the Vorbis bitpacking
34convention is still well defined for any native byte size; Vorbis uses
35the native bit-width of a given storage system. This document assumes
36that a byte is one octet for purposes of example.
37
38\subsubsection{bit order}
39
40A byte has a well-defined 'least significant' bit (LSb), which is the
41only bit set when the byte is storing the two's complement integer
42value +1. A byte's 'most significant' bit (MSb) is at the opposite
43end of the byte. Bits in a byte are numbered from zero at the LSb to
44$n$ ($n=7$ in an octet) for the
45MSb.
46
47
48
49\subsubsection{byte order}
50
51Words are native groupings of multiple bytes. Several byte orderings
52are possible in a word; the common ones are 3-2-1-0 ('big endian' or
53'most significant byte first' in which the highest-valued byte comes
54first), 0-1-2-3 ('little endian' or 'least significant byte first' in
55which the lowest value byte comes first) and less commonly 3-1-2-0 and
560-2-1-3 ('mixed endian').
57
58The Vorbis bitpacking convention specifies storage and bitstream
59manipulation at the byte, not word, level, thus host word ordering is
60of a concern only during optimization when writing high performance
61code that operates on a word of storage at a time rather than by byte.
62Logically, bytes are always coded and decoded in order from byte zero
63through byte $n$.
64
65
66
67\subsubsection{coding bits into byte sequences}
68
69The Vorbis codec has need to code arbitrary bit-width integers, from
70zero to 32 bits wide, into packets. These integer fields are not
71aligned to the boundaries of the byte representation; the next field
72is written at the bit position at which the previous field ends.
73
74The encoder logically packs integers by writing the LSb of a binary
75integer to the logical bitstream first, followed by next least
76significant bit, etc, until the requested number of bits have been
77coded. When packing the bits into bytes, the encoder begins by
78placing the LSb of the integer to be written into the least
79significant unused bit position of the destination byte, followed by
80the next-least significant bit of the source integer and so on up to
81the requested number of bits. When all bits of the destination byte
82have been filled, encoding continues by zeroing all bits of the next
83byte and writing the next bit into the bit position 0 of that byte.
84Decoding follows the same process as encoding, but by reading bits
85from the byte stream and reassembling them into integers.
86
87
88
89\subsubsection{signedness}
90
91The signedness of a specific number resulting from decode is to be
92interpreted by the decoder given decode context. That is, the three
93bit binary pattern 'b111' can be taken to represent either 'seven' as
94an unsigned integer, or '-1' as a signed, two's complement integer.
95The encoder and decoder are responsible for knowing if fields are to
96be treated as signed or unsigned.
97
98
99
100\subsubsection{coding example}
101
102Code the 4 bit integer value '12' [b1100] into an empty bytestream.
103Bytestream result:
104
105\begin{Verbatim}[commandchars=\\\{\}]
106 |
107 V
108
109 7 6 5 4 3 2 1 0
110byte 0 [0 0 0 0 1 1 0 0] <-
111byte 1 [ ]
112byte 2 [ ]
113byte 3 [ ]
114 ...
115byte n [ ] bytestream length == 1 byte
116
117\end{Verbatim}
118
119
120Continue by coding the 3 bit integer value '-1' [b111]:
121
122\begin{Verbatim}[commandchars=\\\{\}]
123 |
124 V
125
126 7 6 5 4 3 2 1 0
127byte 0 [0 1 1 1 1 1 0 0] <-
128byte 1 [ ]
129byte 2 [ ]
130byte 3 [ ]
131 ...
132byte n [ ] bytestream length == 1 byte
133\end{Verbatim}
134
135
136Continue by coding the 7 bit integer value '17' [b0010001]:
137
138\begin{Verbatim}[commandchars=\\\{\}]
139 |
140 V
141
142 7 6 5 4 3 2 1 0
143byte 0 [1 1 1 1 1 1 0 0]
144byte 1 [0 0 0 0 1 0 0 0] <-
145byte 2 [ ]
146byte 3 [ ]
147 ...
148byte n [ ] bytestream length == 2 bytes
149 bit cursor == 6
150\end{Verbatim}
151
152
153Continue by coding the 13 bit integer value '6969' [b110 11001110 01]:
154
155\begin{Verbatim}[commandchars=\\\{\}]
156 |
157 V
158
159 7 6 5 4 3 2 1 0
160byte 0 [1 1 1 1 1 1 0 0]
161byte 1 [0 1 0 0 1 0 0 0]
162byte 2 [1 1 0 0 1 1 1 0]
163byte 3 [0 0 0 0 0 1 1 0] <-
164 ...
165byte n [ ] bytestream length == 4 bytes
166
167\end{Verbatim}
168
169
170
171
172\subsubsection{decoding example}
173
174Reading from the beginning of the bytestream encoded in the above example:
175
176\begin{Verbatim}[commandchars=\\\{\}]
177 |
178 V
179
180 7 6 5 4 3 2 1 0
181byte 0 [1 1 1 1 1 1 0 0] <-
182byte 1 [0 1 0 0 1 0 0 0]
183byte 2 [1 1 0 0 1 1 1 0]
184byte 3 [0 0 0 0 0 1 1 0] bytestream length == 4 bytes
185
186\end{Verbatim}
187
188
189We read two, two-bit integer fields, resulting in the returned numbers
190'b00' and 'b11'. Two things are worth noting here:
191
192\begin{itemize}
193\item Although these four bits were originally written as a single
194four-bit integer, reading some other combination of bit-widths from the
195bitstream is well defined. There are no artificial alignment
196boundaries maintained in the bitstream.
197
198\item The second value is the
199two-bit-wide integer 'b11'. This value may be interpreted either as
200the unsigned value '3', or the signed value '-1'. Signedness is
201dependent on decode context.
202\end{itemize}
203
204
205
206
207\subsubsection{end-of-packet alignment}
208
209The typical use of bitpacking is to produce many independent
210byte-aligned packets which are embedded into a larger byte-aligned
211container structure, such as an Ogg transport bitstream. Externally,
212each bytestream (encoded bitstream) must begin and end on a byte
213boundary. Often, the encoded bitstream is not an integer number of
214bytes, and so there is unused (uncoded) space in the last byte of a
215packet.
216
217Unused space in the last byte of a bytestream is always zeroed during
218the coding process. Thus, should this unused space be read, it will
219return binary zeroes.
220
221Attempting to read past the end of an encoded packet results in an
222'end-of-packet' condition. End-of-packet is not to be considered an
223error; it is merely a state indicating that there is insufficient
224remaining data to fulfill the desired read size. Vorbis uses truncated
225packets as a normal mode of operation, and as such, decoders must
226handle reading past the end of a packet as a typical mode of
227operation. Any further read operations after an 'end-of-packet'
228condition shall also return 'end-of-packet'.
229
230
231
232\subsubsection{reading zero bits}
233
234Reading a zero-bit-wide integer returns the value '0' and does not
235increment the stream cursor. Reading to the end of the packet (but
236not past, such that an 'end-of-packet' condition has not triggered)
237and then reading a zero bit integer shall succeed, returning 0, and
238not trigger an end-of-packet condition. Reading a zero-bit-wide
239integer after a previous read sets 'end-of-packet' shall also fail
240with 'end-of-packet'.
241
242
243
244
245
246
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette