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