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}[h]
  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}[h]
  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}[h]
  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}[h]
  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}