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) | (*pBuf & 0x7f);
105  } else if ((*(pBuf + 2) & 0x80) == 0) {
106    pSize = 3;
107    return ((*(pBuf + 2) & 0x7f) << 14) | ((*(pBuf + 1) & 0x7f) << 7) |
108           (*pBuf & 0x7f);
109  } else {
110    pSize = 4;
111    result = ((*(pBuf + 3) & 0x7f) << 21) | ((*(pBuf + 2) & 0x7f) << 14) |
112             ((*(pBuf + 1) & 0x7f) << 7) | (*pBuf & 0x7f);
113  }
114
115  if ((*(pBuf + 3) & 0x80) != 0) {
116    // Large number which is an unusual case.
117    unsigned shift;
118    ByteType byte;
119
120    // Start the read from the 4th byte.
121    shift = 28;
122    pBuf += 4;
123    do {
124      byte = *pBuf;
125      pBuf++;
126      pSize++;
127      result |= (static_cast<uint64_t>(byte & 0x7f) << shift);
128      shift += 7;
129    } while (byte & 0x80);
130  }
131
132  return result;
133}
134
135template <>
136uint64_t decode<uint64_t>(const ByteType*& pBuf) {
137  ByteType byte;
138  uint64_t result;
139
140  byte = *pBuf++;
141  result = byte & 0x7f;
142  if ((byte & 0x80) == 0) {
143    return result;
144  } else {
145    byte = *pBuf++;
146    result |= ((byte & 0x7f) << 7);
147    if ((byte & 0x80) == 0) {
148      return result;
149    } else {
150      byte = *pBuf++;
151      result |= (byte & 0x7f) << 14;
152      if ((byte & 0x80) == 0) {
153        return result;
154      } else {
155        byte = *pBuf++;
156        result |= (byte & 0x7f) << 21;
157        if ((byte & 0x80) == 0) {
158          return result;
159        }
160      }
161    }
162  }
163
164  // Large number which is an unusual case.
165  unsigned shift;
166
167  // Start the read from the 4th byte.
168  shift = 28;
169  do {
170    byte = *pBuf++;
171    result |= (static_cast<uint64_t>(byte & 0x7f) << shift);
172    shift += 7;
173  } while (byte & 0x80);
174
175  return result;
176}
177
178/*
179 * Signed LEB128 decoding is Similar to the unsigned version but setup the sign
180 * bit if necessary. This is rarely used, therefore we don't provide unrolling
181 * version like decode() to save the code size.
182 */
183template <>
184int64_t decode<int64_t>(const ByteType* pBuf, size_t& pSize) {
185  uint64_t result = 0;
186  ByteType byte;
187  unsigned shift = 0;
188
189  pSize = 0;
190  do {
191    byte = *pBuf;
192    pBuf++;
193    pSize++;
194    result |= (static_cast<uint64_t>(byte & 0x7f) << shift);
195    shift += 7;
196  } while (byte & 0x80);
197
198  if ((shift < (8 * sizeof(result))) && (byte & 0x40))
199    result |= ((static_cast<uint64_t>(-1)) << shift);
200
201  return result;
202}
203
204template <>
205int64_t decode<int64_t>(const ByteType*& pBuf) {
206  uint64_t result = 0;
207  ByteType byte;
208  unsigned shift = 0;
209
210  do {
211    byte = *pBuf;
212    pBuf++;
213    result |= (static_cast<uint64_t>(byte & 0x7f) << shift);
214    shift += 7;
215  } while (byte & 0x80);
216
217  if ((shift < (8 * sizeof(result))) && (byte & 0x40))
218    result |= ((static_cast<uint64_t>(-1)) << shift);
219
220  return result;
221}
222
223}  // namespace leb128
224}  // namespace mcld
225