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<> 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<> 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<> 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<> 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<> 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<> 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<> 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<> 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
