blob: 0e80fe23071e556e38493de478d5545ecc19c5cc [file] [log] [blame]
Elliott Hughes2faa5f12012-01-30 14:42:07 -08001/*
2 * Copyright (C) 2011 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
Carl Shapiro1fb86202011-06-27 17:43:13 -070016
Brian Carlstromfc0e3212013-07-17 14:40:12 -070017#ifndef ART_RUNTIME_LEB128_H_
18#define ART_RUNTIME_LEB128_H_
Carl Shapiro1fb86202011-06-27 17:43:13 -070019
Brian Carlstrom578bbdc2011-07-21 14:07:47 -070020#include "globals.h"
Vladimir Marko1e6cb632013-11-28 16:27:29 +000021#include "utils.h"
Carl Shapiro1fb86202011-06-27 17:43:13 -070022
23namespace art {
24
25// Reads an unsigned LEB128 value, updating the given pointer to point
26// just past the end of the read value. This function tolerates
27// non-zero high-order bits in the fifth encoded byte.
Ian Rogers96faf5b2013-08-09 22:05:32 -070028static inline uint32_t DecodeUnsignedLeb128(const uint8_t** data) {
29 const uint8_t* ptr = *data;
Carl Shapiro1fb86202011-06-27 17:43:13 -070030 int result = *(ptr++);
31 if (result > 0x7f) {
32 int cur = *(ptr++);
33 result = (result & 0x7f) | ((cur & 0x7f) << 7);
34 if (cur > 0x7f) {
35 cur = *(ptr++);
36 result |= (cur & 0x7f) << 14;
37 if (cur > 0x7f) {
38 cur = *(ptr++);
39 result |= (cur & 0x7f) << 21;
40 if (cur > 0x7f) {
41 // Note: We don't check to see if cur is out of range here,
42 // meaning we tolerate garbage in the four high-order bits.
43 cur = *(ptr++);
44 result |= cur << 28;
45 }
46 }
47 }
48 }
49 *data = ptr;
buzbeecbd6d442012-11-17 14:11:25 -080050 return static_cast<uint32_t>(result);
Carl Shapiro1fb86202011-06-27 17:43:13 -070051}
52
Shih-wei Liao195487c2011-08-20 13:29:04 -070053// Reads an unsigned LEB128 + 1 value. updating the given pointer to point
54// just past the end of the read value. This function tolerates
55// non-zero high-order bits in the fifth encoded byte.
56// It is possible for this function to return -1.
Ian Rogers96faf5b2013-08-09 22:05:32 -070057static inline int32_t DecodeUnsignedLeb128P1(const uint8_t** data) {
Shih-wei Liao195487c2011-08-20 13:29:04 -070058 return DecodeUnsignedLeb128(data) - 1;
59}
60
Carl Shapiro1fb86202011-06-27 17:43:13 -070061// Reads a signed LEB128 value, updating the given pointer to point
62// just past the end of the read value. This function tolerates
63// non-zero high-order bits in the fifth encoded byte.
Ian Rogers96faf5b2013-08-09 22:05:32 -070064static inline int32_t DecodeSignedLeb128(const uint8_t** data) {
65 const uint8_t* ptr = *data;
Carl Shapiro1fb86202011-06-27 17:43:13 -070066 int32_t result = *(ptr++);
67 if (result <= 0x7f) {
68 result = (result << 25) >> 25;
69 } else {
70 int cur = *(ptr++);
71 result = (result & 0x7f) | ((cur & 0x7f) << 7);
72 if (cur <= 0x7f) {
73 result = (result << 18) >> 18;
74 } else {
75 cur = *(ptr++);
76 result |= (cur & 0x7f) << 14;
77 if (cur <= 0x7f) {
78 result = (result << 11) >> 11;
79 } else {
80 cur = *(ptr++);
81 result |= (cur & 0x7f) << 21;
82 if (cur <= 0x7f) {
83 result = (result << 4) >> 4;
84 } else {
85 // Note: We don't check to see if cur is out of range here,
86 // meaning we tolerate garbage in the four high-order bits.
87 cur = *(ptr++);
88 result |= cur << 28;
89 }
90 }
91 }
92 }
93 *data = ptr;
94 return result;
95}
96
jeffhaod1f0fde2011-09-08 17:25:33 -070097// Returns the number of bytes needed to encode the value in unsigned LEB128.
98static inline uint32_t UnsignedLeb128Size(uint32_t data) {
Vladimir Marko1e6cb632013-11-28 16:27:29 +000099 // bits_to_encode = (data != 0) ? 32 - CLZ(x) : 1 // 32 - CLZ(data | 1)
100 // bytes = ceil(bits_to_encode / 7.0); // (6 + bits_to_encode) / 7
101 uint32_t x = 6 + 32 - CLZ(data | 1);
102 // Division by 7 is done by (x * 37) >> 8 where 37 = ceil(256 / 7).
103 // This works for 0 <= x < 256 / (7 * 37 - 256), i.e. 0 <= x <= 85.
104 return (x * 37) >> 8;
105}
106
107// Returns the number of bytes needed to encode the value in unsigned LEB128.
108static inline uint32_t SignedLeb128Size(int32_t data) {
109 // Like UnsignedLeb128Size(), but we need one bit beyond the highest bit that differs from sign.
110 data = data ^ (data >> 31);
111 uint32_t x = 1 /* we need to encode the sign bit */ + 6 + 32 - CLZ(data | 1);
112 return (x * 37) >> 8;
jeffhaod1f0fde2011-09-08 17:25:33 -0700113}
114
Brian Carlstroma1ce1fe2014-02-24 23:23:58 -0800115static inline uint8_t* EncodeUnsignedLeb128(uint8_t* dest, uint32_t value) {
116 uint8_t out = value & 0x7f;
117 value >>= 7;
118 while (value != 0) {
119 *dest++ = out | 0x80;
120 out = value & 0x7f;
121 value >>= 7;
122 }
123 *dest++ = out;
124 return dest;
125}
126
127static inline uint8_t* EncodeSignedLeb128(uint8_t* dest, int32_t value) {
128 uint32_t extra_bits = static_cast<uint32_t>(value ^ (value >> 31)) >> 6;
129 uint8_t out = value & 0x7f;
130 while (extra_bits != 0u) {
131 *dest++ = out | 0x80;
132 value >>= 7;
133 out = value & 0x7f;
134 extra_bits >>= 7;
135 }
136 *dest++ = out;
137 return dest;
138}
139
140// An encoder with an API similar to vector<uint32_t> where the data is captured in ULEB128 format.
141class Leb128EncodingVector {
142 public:
143 Leb128EncodingVector() {
144 }
145
146 void Reserve(uint32_t size) {
147 data_.reserve(size);
148 }
149
150 void PushBackUnsigned(uint32_t value) {
151 uint8_t out = value & 0x7f;
152 value >>= 7;
153 while (value != 0) {
154 data_.push_back(out | 0x80);
155 out = value & 0x7f;
156 value >>= 7;
157 }
158 data_.push_back(out);
159 }
160
161 template<typename It>
162 void InsertBackUnsigned(It cur, It end) {
163 for (; cur != end; ++cur) {
164 PushBackUnsigned(*cur);
165 }
166 }
167
168 void PushBackSigned(int32_t value) {
169 uint32_t extra_bits = static_cast<uint32_t>(value ^ (value >> 31)) >> 6;
170 uint8_t out = value & 0x7f;
171 while (extra_bits != 0u) {
172 data_.push_back(out | 0x80);
173 value >>= 7;
174 out = value & 0x7f;
175 extra_bits >>= 7;
176 }
177 data_.push_back(out);
178 }
179
180 template<typename It>
181 void InsertBackSigned(It cur, It end) {
182 for (; cur != end; ++cur) {
183 PushBackSigned(*cur);
184 }
185 }
186
187 const std::vector<uint8_t>& GetData() const {
188 return data_;
189 }
190
191 private:
192 std::vector<uint8_t> data_;
193
194 DISALLOW_COPY_AND_ASSIGN(Leb128EncodingVector);
195};
196
Carl Shapiro1fb86202011-06-27 17:43:13 -0700197} // namespace art
198
Brian Carlstromfc0e3212013-07-17 14:40:12 -0700199#endif // ART_RUNTIME_LEB128_H_