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) | (*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 <> 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 <> 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 <> 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
