This is the Public Review Draft.
[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 The encode and decode algorithms given here do not take account of C/C++ rules
11 that mean that in \texttt{E1}$ << $\texttt{E2} the type of \texttt{E1} should be
12 a sufficiently large unsigned type to hold the correct mathematical result.
13 The decode algorithms do not take account of
14 or protect from possibly invalid LEB values, such as values
15 that are too large to fit in the target type or that
16 lack a proper terminator byte.
17 Implementation languages may have additional or different rules.
18
19 \vspace{2cm}
20
21 \begin{figure}[hb]
22 \begin{lstlisting}
23 do
24 {
25     byte = low order 7 bits of value;
26     value >>= 7;
27     if (value != 0)     /* more bytes to come */
28         set high order bit of byte;
29     emit byte;
30 } while (value != 0);
31 \end{lstlisting}
32 \caption{Algorithm to encode an unsigned integer}
33 \addtoindexx{LEB128!unsigned, encoding as}
34 \end{figure}
35
36 \begin{figure}[ht]
37 \begin{lstlisting}
38 more = 1;
39 negative = (value < 0);
40 size = no. of bits in signed integer;
41 while(more)
42 {
43     byte = low order 7 bits of value;
44     value >>= 7;
45     /* the following is unnecessary if the
46      * implementation of >>= uses an arithmetic rather
47      * than logical shift for a signed left operand
48      */
49     if (negative)
50         /* sign extend */
51         value |= - (1 <<(size - 7));
52     /* sign bit of byte is second high order bit (0x40) */
53     if ((value == 0 && sign bit of byte is clear) ||
54         (value == -1 && sign bit of byte is set))
55         more = 0;
56     else
57         set high order bit of byte;
58     emit byte;
59 }
60 \end{lstlisting}
61 \caption{Algorithm to encode a signed integer}
62 \addtoindexx{LEB128!signed, encoding as}
63 \end{figure}
64
65 \begin{figure}[ht]
66 \begin{lstlisting}
67 result = 0;
68 shift = 0;
69 while(true)
70 {
71     byte = next byte in input;
72     result |= (low order 7 bits of byte << shift);
73     if (high order bit of byte == 0)
74         break;
75     shift += 7;
76 }
77 \end{lstlisting}
78 \caption{Algorithm to decode an unsigned LEB128 integer}
79 \addtoindexx{LEB128!unsigned, decoding of}
80 \end{figure}
81
82 \begin{figure}[ht]
83 \begin{lstlisting}
84 result = 0;
85 shift = 0;
86 size = number of bits in signed integer;
87 while(true)
88 {
89     byte = next byte in input;
90     result |= (low order 7 bits of byte << shift);
91     shift += 7;
92     /* sign bit of byte is second high order bit (0x40) */
93     if (high order bit of byte == 0)
94         break;
95 }
96 if ((shift <size) && (sign bit of byte is set))
97     /* sign extend */
98     result |= - (1 << shift);
99 \end{lstlisting}
100 \caption{Algorithm to decode a signed LEB128 integer}
101 \addtoindexx{LEB128!signed, decoding of}
102 \end{figure}