768dcf4b1a95ce516e68b3606618ce3a88096d41
2 \chapter[Encoding/Decoding (Informative)]{Variable Length Data: Encoding/Decoding (Informative)}
3 \label{app:variablelengthdataencodingdecodinginformative}
6 Here are algorithms expressed in a C-like pseudo-code to
7 encode and decode signed and unsigned numbers in LEB128
8 \addtoindexx{LEB128!unsigned, encoding as}
9 representation.
11 \begin{figure}[here]
12 \caption{Algorithm to encode an unsigned integer}
13 \begin{lstlisting}
14 do
15 {
16     byte = low order 7 bits of value;
17     value >>= 7;
18     if (value != 0) /* more bytes to come */
19         set high order bit of byte;
20     emit byte;
21 } while (value != 0);
22 \end{lstlisting}
23 \end{figure}
25 \addtoindexx{LEB128!signed, encoding as}
27 \begin{figure}[here]
28 \caption{Algorithm to encode a signed integer}
29 \begin{lstlisting}
30 more = 1;
31 negative = (value < 0);
32 size = no. of bits in signed integer;
33 while(more)
34 {
35     byte = low order 7 bits of value;
36     value >>= 7;
37     /* the following is unnecessary if the
38       * implementation of >>= uses an arithmetic rather
39       * than logical shift for a signed left operand
40       */
41     if (negative)
42         /* sign extend */
43         value |= - (1 <<(size - 7));
44     /* sign bit of byte is second high order bit (0x40) */
45     if ((value == 0 && sign bit of byte is clear) ||
46         (value == -1 && sign bit of byte is set))
47         more = 0;
48     else
49         set high order bit of byte;
50     emit byte;
51 }
52 \end{lstlisting}
53 \end{figure}
57 \addtoindexx{LEB128!unsigned, decoding of}
59 \begin{figure}[here]
60 \caption{Algorithm to decode an unsigned LEB128 integer}
61 \begin{lstlisting}
62 result = 0;
63 shift = 0;
64 while(true)
65 {
66     byte = next byte in input;
67     result |= (low order 7 bits of byte << shift);
68     if (high order bit of byte == 0)
69         break;
70     shift += 7;
71 }
72 \end{lstlisting}
73 \end{figure}
75 \addtoindexx{LEB128!signed, decoding of}
77 \begin{figure}[here]
78 \caption{Algorithm to decode a signed LEB128 integer}
79 \begin{lstlisting}
80 result = 0;
81 shift = 0;
82 size = number of bits in signed integer;
83 while(true)
84 {
85     byte = next byte in input;
86     result |= (low order 7 bits of byte << shift);
87     shift += 7;
88     /* sign bit of byte is second high order bit (0x40) */
89     if (high order bit of byte == 0)
90         break;
91 }
92 if ((shift <size) \&\& (sign bit of byte is set))
93     /* sign extend */
94     result |= - (1 << shift);
95 \end{lstlisting}
96 \end{figure}