1//===- LEB128.cpp ---------------------------------------------------------===//
2//
3//                     The MCLinker Project
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9#include <mcld/Support/LEB128.h>
10
11namespace mcld {
12
13namespace leb128 {
14
15//===---------------------- LEB128 Encoding APIs -------------------------===//
16template<>
17size_t encode<uint64_t>(ByteType *&pBuf, uint64_t pValue) {
18  size_t size = 0;
19  do {
20    ByteType byte = pValue & 0x7f;
21    pValue >>= 7;
22    if (pValue)
23      byte |= 0x80;
24    *pBuf++ = byte;
25    size++;
26  } while (pValue);
27
28  return size;
29}
30
31/*
32 * Fast version for encoding 32-bit integer. This unrolls the loop in the
33 * generic version defined above.
34 */
35template<>
36size_t encode<uint32_t>(ByteType *&pBuf, uint32_t pValue) {
37  if ((pValue & ~0x7f) == 0) {
38    *pBuf++ = static_cast<ByteType>(pValue);
39    return 1;
40  } else if ((pValue & ~0x3fff) == 0){
41    *pBuf++ = static_cast<ByteType>((pValue         & 0x7f) | 0x80);
42    *pBuf++ = static_cast<ByteType>((pValue  >>  7) & 0x7f);
43    return 2;
44  } else if ((pValue & ~0x1fffff) == 0) {
45    *pBuf++ = static_cast<ByteType>((pValue         & 0x7f) | 0x80);
46    *pBuf++ = static_cast<ByteType>(((pValue >>  7) & 0x7f) | 0x80);
47    *pBuf++ = static_cast<ByteType>((pValue  >> 14) & 0x7f);
48    return 3;
49  } else if ((pValue & ~0xfffffff) == 0) {
50    *pBuf++ = static_cast<ByteType>((pValue         & 0x7f) | 0x80);
51    *pBuf++ = static_cast<ByteType>(((pValue >>  7) & 0x7f) | 0x80);
52    *pBuf++ = static_cast<ByteType>(((pValue >> 14) & 0x7f) | 0x80);
53    *pBuf++ = static_cast<ByteType>((pValue  >> 21) & 0x7f);
54    return 4;
55  } else {
56    *pBuf++ = static_cast<ByteType>((pValue         & 0x7f) | 0x80);
57    *pBuf++ = static_cast<ByteType>(((pValue >>  7) & 0x7f) | 0x80);
58    *pBuf++ = static_cast<ByteType>(((pValue >> 14) & 0x7f) | 0x80);
59    *pBuf++ = static_cast<ByteType>(((pValue >> 21) & 0x7f) | 0x80);
60    *pBuf++ = static_cast<ByteType>((pValue  >> 28) & 0x7f);
61    return 5;
62  }
63  // unreachable
64}
65
66template<>
67size_t encode<int64_t>(ByteType *&pBuf, int64_t pValue) {
68  size_t size = 0;
69  bool more = true;
70
71  do {
72    ByteType byte = pValue & 0x7f;
73    pValue >>= 7;
74
75    if (((pValue ==  0) && ((byte & 0x40) == 0)) ||
76        ((pValue == -1) && ((byte & 0x40) == 0x40)))
77      more = false;
78    else
79      byte |= 0x80;
80
81    *pBuf++ = byte;
82    size++;
83  } while (more);
84
85  return size;
86}
87
88template<>
89size_t encode<int32_t>(ByteType *&pBuf, int32_t pValue) {
90  return encode<int64_t>(pBuf, static_cast<int64_t>(pValue));
91}
92
93//===---------------------- LEB128 Decoding APIs -------------------------===//
94
95template<>
96uint64_t decode<uint64_t>(const ByteType *pBuf, size_t &pSize) {
97  uint64_t result = 0;
98
99  if ((*pBuf & 0x80) == 0) {
100    pSize = 1;
101    return *pBuf;
102  } else if ((*(pBuf + 1) & 0x80) == 0) {
103    pSize = 2;
104    return ((*(pBuf + 1) & 0x7f) << 7) |
105           (*pBuf & 0x7f);
106  } else if ((*(pBuf + 2) & 0x80) == 0) {
107    pSize = 3;
108    return ((*(pBuf + 2) & 0x7f) << 14) |
109           ((*(pBuf + 1) & 0x7f) <<  7) |
110           (*pBuf & 0x7f);
111  } else {
112    pSize = 4;
113    result = ((*(pBuf + 3) & 0x7f) << 21) |
114             ((*(pBuf + 2) & 0x7f) << 14) |
115             ((*(pBuf + 1) & 0x7f) <<  7) |
116             (*pBuf & 0x7f);
117  }
118
119  if ((*(pBuf + 3) & 0x80) != 0) {
120    // Large number which is an unusual case.
121    unsigned shift;
122    ByteType byte;
123
124    // Start the read from the 4th byte.
125    shift = 28;
126    pBuf += 4;
127    do {
128      byte = *pBuf;
129      pBuf++;
130      pSize++;
131      result |= (static_cast<uint64_t>(byte & 0x7f) << shift);
132      shift += 7;
133    } while (byte & 0x80);
134  }
135
136  return result;
137}
138
139template<>
140uint64_t decode<uint64_t>(const ByteType *&pBuf) {
141  ByteType byte;
142  uint64_t result;
143
144  byte = *pBuf++;
145  result = byte & 0x7f;
146  if ((byte & 0x80) == 0) {
147    return result;
148  } else {
149    byte = *pBuf++;
150    result |=  ((byte & 0x7f) << 7);
151    if ((byte & 0x80) == 0) {
152      return result;
153    } else {
154      byte = *pBuf++;
155      result |= (byte & 0x7f) << 14;
156      if ((byte & 0x80) == 0) {
157        return result;
158      } else {
159        byte = *pBuf++;
160        result |= (byte & 0x7f) << 21;
161        if ((byte & 0x80) == 0) {
162          return result;
163        }
164      }
165    }
166  }
167
168  // Large number which is an unusual case.
169  unsigned shift;
170
171  // Start the read from the 4th byte.
172  shift = 28;
173  do {
174    byte = *pBuf++;
175    result |= (static_cast<uint64_t>(byte & 0x7f) << shift);
176    shift += 7;
177  } while (byte & 0x80);
178
179  return result;
180}
181
182/*
183 * Signed LEB128 decoding is Similar to the unsigned version but setup the sign
184 * bit if necessary. This is rarely used, therefore we don't provide unrolling
185 * version like decode() to save the code size.
186 */
187template<>
188int64_t decode<int64_t>(const ByteType *pBuf, size_t &pSize) {
189  uint64_t result = 0;
190  ByteType byte;
191  unsigned shift = 0;
192
193  pSize = 0;
194  do {
195    byte = *pBuf;
196    pBuf++;
197    pSize++;
198    result |= (static_cast<uint64_t>(byte & 0x7f) << shift);
199    shift += 7;
200  } while (byte & 0x80);
201
202  if ((shift < (8 * sizeof(result))) && (byte & 0x40))
203    result |= ((static_cast<uint64_t>(-1)) << shift);
204
205  return result;
206}
207
208template<>
209int64_t decode<int64_t>(const ByteType *&pBuf) {
210  uint64_t result = 0;
211  ByteType byte;
212  unsigned shift = 0;
213
214  do {
215    byte = *pBuf;
216    pBuf++;
217    result |= (static_cast<uint64_t>(byte & 0x7f) << shift);
218    shift += 7;
219  } while (byte & 0x80);
220
221  if ((shift < (8 * sizeof(result))) && (byte & 0x40))
222    result |= ((static_cast<uint64_t>(-1)) << shift);
223
224  return result;
225}
226
227} // namespace of leb128
228} // namespace of mcld
229