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 representation.
10 \begin{figure}[here]
11 \caption{Algorithm to encode an unsigned integer}
12 \addtoindexx{LEB128!unsigned, encoding as}
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 \begin{figure}[here]
26 \caption{Algorithm to encode a signed integer}
27 \addtoindexx{LEB128!signed, encoding as}
28 \begin{lstlisting}
29 more = 1;
30 negative = (value < 0);
31 size = no. of bits in signed integer;
32 while(more)
33 {
34     byte = low order 7 bits of value;
35     value >>= 7;
36     /* the following is unnecessary if the
37       * implementation of >>= uses an arithmetic rather
38       * than logical shift for a signed left operand
39       */
40     if (negative)
41         /* sign extend */
42         value |= - (1 <<(size - 7));
43     /* sign bit of byte is second high order bit (0x40) */
44     if ((value == 0 && sign bit of byte is clear) ||
45         (value == -1 && sign bit of byte is set))
46         more = 0;
47     else
48         set high order bit of byte;
49     emit byte;
50 }
51 \end{lstlisting}
52 \end{figure}
54 \begin{figure}[here]
55 \caption{Algorithm to decode an unsigned LEB128 integer}
56 \addtoindexx{LEB128!unsigned, decoding of}
57 \begin{lstlisting}
58 result = 0;
59 shift = 0;
60 while(true)
61 {
62     byte = next byte in input;
63     result |= (low order 7 bits of byte << shift);
64     if (high order bit of byte == 0)
65         break;
66     shift += 7;
67 }
68 \end{lstlisting}
69 \end{figure}
71 \begin{figure}[here]
72 \caption{Algorithm to decode a signed LEB128 integer}
73 \addtoindexx{LEB128!signed, decoding of}
74 \begin{lstlisting}
75 result = 0;
76 shift = 0;
77 size = number of bits in signed integer;
78 while(true)
79 {
80     byte = next byte in input;
81     result |= (low order 7 bits of byte << shift);
82     shift += 7;
83     /* sign bit of byte is second high order bit (0x40) */
84     if (high order bit of byte == 0)
85         break;
86 }
87 if ((shift <size) \&\& (sign bit of byte is set))
88     /* sign extend */
89     result |= - (1 << shift);
90 \end{lstlisting}
91 \end{figure}