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