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) |
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
139 template<>
decode(const ByteType * & pBuf)140 uint64_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 */
187 template<>
decode(const ByteType * pBuf,size_t & pSize)188 int64_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
208 template<>
decode(const ByteType * & pBuf)209 int64_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