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