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
11 namespace mcld {
12
13 namespace leb128 {
14
15 //===---------------------- LEB128 Encoding APIs -------------------------===//
16 template <>
encode(ByteType * & pBuf,uint64_t pValue)17 size_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 */
35 template <>
encode(ByteType * & pBuf,uint32_t pValue)36 size_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
66 template <>
encode(ByteType * & pBuf,int64_t pValue)67 size_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
88 template <>
encode(ByteType * & pBuf,int32_t pValue)89 size_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
95 template <>
decode(const ByteType * pBuf,size_t & pSize)96 uint64_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
135 template <>
decode(const ByteType * & pBuf)136 uint64_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 */
183 template <>
decode(const ByteType * pBuf,size_t & pSize)184 int64_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
204 template <>
decode(const ByteType * & pBuf)205 int64_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