1 /*
2 * Copyright (c) 2019, 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 */
16
17 #include "cppbor_parse.h"
18
19 #include <sstream>
20 #include <stack>
21
22 #define LOG_TAG "CppBor"
23 #include <android-base/logging.h>
24
25 namespace cppbor {
26
27 namespace {
28
insufficientLengthString(size_t bytesNeeded,size_t bytesAvail,const std::string & type)29 std::string insufficientLengthString(size_t bytesNeeded, size_t bytesAvail,
30 const std::string& type) {
31 std::stringstream errStream;
32 errStream << "Need " << bytesNeeded << " byte(s) for " << type << ", have " << bytesAvail
33 << ".";
34 return errStream.str();
35 }
36
37 template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
parseLength(const uint8_t * pos,const uint8_t * end,ParseClient * parseClient)38 std::tuple<bool, uint64_t, const uint8_t*> parseLength(const uint8_t* pos, const uint8_t* end,
39 ParseClient* parseClient) {
40 if (pos + sizeof(T) > end) {
41 parseClient->error(pos - 1, insufficientLengthString(sizeof(T), end - pos, "length field"));
42 return {false, 0, pos};
43 }
44
45 const uint8_t* intEnd = pos + sizeof(T);
46 T result = 0;
47 do {
48 result = static_cast<T>((result << 8) | *pos++);
49 } while (pos < intEnd);
50 return {true, result, pos};
51 }
52
53 std::tuple<const uint8_t*, ParseClient*> parseRecursively(const uint8_t* begin, const uint8_t* end,
54 ParseClient* parseClient);
55
handleUint(uint64_t value,const uint8_t * hdrBegin,const uint8_t * hdrEnd,ParseClient * parseClient)56 std::tuple<const uint8_t*, ParseClient*> handleUint(uint64_t value, const uint8_t* hdrBegin,
57 const uint8_t* hdrEnd,
58 ParseClient* parseClient) {
59 std::unique_ptr<Item> item = std::make_unique<Uint>(value);
60 return {hdrEnd,
61 parseClient->item(item, hdrBegin, hdrEnd /* valueBegin */, hdrEnd /* itemEnd */)};
62 }
63
handleNint(uint64_t value,const uint8_t * hdrBegin,const uint8_t * hdrEnd,ParseClient * parseClient)64 std::tuple<const uint8_t*, ParseClient*> handleNint(uint64_t value, const uint8_t* hdrBegin,
65 const uint8_t* hdrEnd,
66 ParseClient* parseClient) {
67 if (value > std::numeric_limits<int64_t>::max()) {
68 parseClient->error(hdrBegin, "NINT values that don't fit in int64_t are not supported.");
69 return {hdrBegin, nullptr /* end parsing */};
70 }
71 std::unique_ptr<Item> item = std::make_unique<Nint>(-1 - static_cast<uint64_t>(value));
72 return {hdrEnd,
73 parseClient->item(item, hdrBegin, hdrEnd /* valueBegin */, hdrEnd /* itemEnd */)};
74 }
75
handleBool(uint64_t value,const uint8_t * hdrBegin,const uint8_t * hdrEnd,ParseClient * parseClient)76 std::tuple<const uint8_t*, ParseClient*> handleBool(uint64_t value, const uint8_t* hdrBegin,
77 const uint8_t* hdrEnd,
78 ParseClient* parseClient) {
79 std::unique_ptr<Item> item = std::make_unique<Bool>(value == TRUE);
80 return {hdrEnd,
81 parseClient->item(item, hdrBegin, hdrEnd /* valueBegin */, hdrEnd /* itemEnd */)};
82 }
83
handleNull(const uint8_t * hdrBegin,const uint8_t * hdrEnd,ParseClient * parseClient)84 std::tuple<const uint8_t*, ParseClient*> handleNull(const uint8_t* hdrBegin, const uint8_t* hdrEnd,
85 ParseClient* parseClient) {
86 std::unique_ptr<Item> item = std::make_unique<Null>();
87 return {hdrEnd,
88 parseClient->item(item, hdrBegin, hdrEnd /* valueBegin */, hdrEnd /* itemEnd */)};
89 }
90
91 template <typename T>
handleString(uint64_t length,const uint8_t * hdrBegin,const uint8_t * valueBegin,const uint8_t * end,const std::string & errLabel,ParseClient * parseClient)92 std::tuple<const uint8_t*, ParseClient*> handleString(uint64_t length, const uint8_t* hdrBegin,
93 const uint8_t* valueBegin, const uint8_t* end,
94 const std::string& errLabel,
95 ParseClient* parseClient) {
96 if (end - valueBegin < static_cast<ssize_t>(length)) {
97 parseClient->error(hdrBegin, insufficientLengthString(length, end - valueBegin, errLabel));
98 return {hdrBegin, nullptr /* end parsing */};
99 }
100
101 std::unique_ptr<Item> item = std::make_unique<T>(valueBegin, valueBegin + length);
102 return {valueBegin + length,
103 parseClient->item(item, hdrBegin, valueBegin, valueBegin + length)};
104 }
105
106 class IncompleteItem {
107 public:
~IncompleteItem()108 virtual ~IncompleteItem() {}
109 virtual void add(std::unique_ptr<Item> item) = 0;
110 };
111
112 class IncompleteArray : public Array, public IncompleteItem {
113 public:
IncompleteArray(size_t size)114 IncompleteArray(size_t size) : mSize(size) {}
115
116 // We return the "complete" size, rather than the actual size.
size() const117 size_t size() const override { return mSize; }
118
add(std::unique_ptr<Item> item)119 void add(std::unique_ptr<Item> item) override {
120 mEntries.reserve(mSize);
121 mEntries.push_back(std::move(item));
122 }
123
124 private:
125 size_t mSize;
126 };
127
128 class IncompleteMap : public Map, public IncompleteItem {
129 public:
IncompleteMap(size_t size)130 IncompleteMap(size_t size) : mSize(size) {}
131
132 // We return the "complete" size, rather than the actual size.
size() const133 size_t size() const override { return mSize; }
134
add(std::unique_ptr<Item> item)135 void add(std::unique_ptr<Item> item) override {
136 mEntries.reserve(mSize * 2);
137 mEntries.push_back(std::move(item));
138 }
139
140 private:
141 size_t mSize;
142 };
143
144 class IncompleteSemantic : public Semantic, public IncompleteItem {
145 public:
IncompleteSemantic(uint64_t value)146 IncompleteSemantic(uint64_t value) : Semantic(value) {}
147
148 // We return the "complete" size, rather than the actual size.
size() const149 size_t size() const override { return 1; }
150
add(std::unique_ptr<Item> item)151 void add(std::unique_ptr<Item> item) override {
152 mEntries.reserve(1);
153 mEntries.push_back(std::move(item));
154 }
155 };
156
handleEntries(size_t entryCount,const uint8_t * hdrBegin,const uint8_t * pos,const uint8_t * end,const std::string & typeName,ParseClient * parseClient)157 std::tuple<const uint8_t*, ParseClient*> handleEntries(size_t entryCount, const uint8_t* hdrBegin,
158 const uint8_t* pos, const uint8_t* end,
159 const std::string& typeName,
160 ParseClient* parseClient) {
161 while (entryCount > 0) {
162 --entryCount;
163 if (pos == end) {
164 parseClient->error(hdrBegin, "Not enough entries for " + typeName + ".");
165 return {hdrBegin, nullptr /* end parsing */};
166 }
167 std::tie(pos, parseClient) = parseRecursively(pos, end, parseClient);
168 if (!parseClient) return {hdrBegin, nullptr};
169 }
170 return {pos, parseClient};
171 }
172
handleCompound(std::unique_ptr<Item> item,uint64_t entryCount,const uint8_t * hdrBegin,const uint8_t * valueBegin,const uint8_t * end,const std::string & typeName,ParseClient * parseClient)173 std::tuple<const uint8_t*, ParseClient*> handleCompound(
174 std::unique_ptr<Item> item, uint64_t entryCount, const uint8_t* hdrBegin,
175 const uint8_t* valueBegin, const uint8_t* end, const std::string& typeName,
176 ParseClient* parseClient) {
177 parseClient =
178 parseClient->item(item, hdrBegin, valueBegin, valueBegin /* don't know the end yet */);
179 if (!parseClient) return {hdrBegin, nullptr};
180
181 const uint8_t* pos;
182 std::tie(pos, parseClient) =
183 handleEntries(entryCount, hdrBegin, valueBegin, end, typeName, parseClient);
184 if (!parseClient) return {hdrBegin, nullptr};
185
186 return {pos, parseClient->itemEnd(item, hdrBegin, valueBegin, pos)};
187 }
188
parseRecursively(const uint8_t * begin,const uint8_t * end,ParseClient * parseClient)189 std::tuple<const uint8_t*, ParseClient*> parseRecursively(const uint8_t* begin, const uint8_t* end,
190 ParseClient* parseClient) {
191 const uint8_t* pos = begin;
192
193 MajorType type = static_cast<MajorType>(*pos & 0xE0);
194 uint8_t tagInt = *pos & 0x1F;
195 ++pos;
196
197 bool success = true;
198 uint64_t addlData;
199 if (tagInt < ONE_BYTE_LENGTH || tagInt > EIGHT_BYTE_LENGTH) {
200 addlData = tagInt;
201 } else {
202 switch (tagInt) {
203 case ONE_BYTE_LENGTH:
204 std::tie(success, addlData, pos) = parseLength<uint8_t>(pos, end, parseClient);
205 break;
206
207 case TWO_BYTE_LENGTH:
208 std::tie(success, addlData, pos) = parseLength<uint16_t>(pos, end, parseClient);
209 break;
210
211 case FOUR_BYTE_LENGTH:
212 std::tie(success, addlData, pos) = parseLength<uint32_t>(pos, end, parseClient);
213 break;
214
215 case EIGHT_BYTE_LENGTH:
216 std::tie(success, addlData, pos) = parseLength<uint64_t>(pos, end, parseClient);
217 break;
218
219 default:
220 CHECK(false); // It's impossible to get here
221 break;
222 }
223 }
224
225 if (!success) return {begin, nullptr};
226
227 switch (type) {
228 case UINT:
229 return handleUint(addlData, begin, pos, parseClient);
230
231 case NINT:
232 return handleNint(addlData, begin, pos, parseClient);
233
234 case BSTR:
235 return handleString<Bstr>(addlData, begin, pos, end, "byte string", parseClient);
236
237 case TSTR:
238 return handleString<Tstr>(addlData, begin, pos, end, "text string", parseClient);
239
240 case ARRAY:
241 return handleCompound(std::make_unique<IncompleteArray>(addlData), addlData, begin, pos,
242 end, "array", parseClient);
243
244 case MAP:
245 return handleCompound(std::make_unique<IncompleteMap>(addlData), addlData * 2, begin,
246 pos, end, "map", parseClient);
247
248 case SEMANTIC:
249 return handleCompound(std::make_unique<IncompleteSemantic>(addlData), 1, begin, pos,
250 end, "semantic", parseClient);
251
252 case SIMPLE:
253 switch (addlData) {
254 case TRUE:
255 case FALSE:
256 return handleBool(addlData, begin, pos, parseClient);
257 case NULL_V:
258 return handleNull(begin, pos, parseClient);
259 }
260 }
261 CHECK(false); // Impossible to get here.
262 return {};
263 }
264
265 class FullParseClient : public ParseClient {
266 public:
item(std::unique_ptr<Item> & item,const uint8_t *,const uint8_t *,const uint8_t * end)267 virtual ParseClient* item(std::unique_ptr<Item>& item, const uint8_t*, const uint8_t*,
268 const uint8_t* end) override {
269 if (mParentStack.empty() && !item->isCompound()) {
270 // This is the first and only item.
271 mTheItem = std::move(item);
272 mPosition = end;
273 return nullptr; // We're done.
274 }
275
276 if (item->isCompound()) {
277 // Starting a new compound data item, i.e. a new parent. Save it on the parent stack.
278 // It's safe to save a raw pointer because the unique_ptr is guaranteed to stay in
279 // existence until the corresponding itemEnd() call.
280 assert(dynamic_cast<CompoundItem*>(item.get()));
281 mParentStack.push(static_cast<CompoundItem*>(item.get()));
282 return this;
283 } else {
284 appendToLastParent(std::move(item));
285 return this;
286 }
287 }
288
itemEnd(std::unique_ptr<Item> & item,const uint8_t *,const uint8_t *,const uint8_t * end)289 virtual ParseClient* itemEnd(std::unique_ptr<Item>& item, const uint8_t*, const uint8_t*,
290 const uint8_t* end) override {
291 CHECK(item->isCompound() && item.get() == mParentStack.top());
292 mParentStack.pop();
293
294 if (mParentStack.empty()) {
295 mTheItem = std::move(item);
296 mPosition = end;
297 return nullptr; // We're done
298 } else {
299 appendToLastParent(std::move(item));
300 return this;
301 }
302 }
303
error(const uint8_t * position,const std::string & errorMessage)304 virtual void error(const uint8_t* position, const std::string& errorMessage) override {
305 mPosition = position;
306 mErrorMessage = errorMessage;
307 }
308
309 std::tuple<std::unique_ptr<Item> /* result */, const uint8_t* /* newPos */,
310 std::string /* errMsg */>
parseResult()311 parseResult() {
312 std::unique_ptr<Item> p = std::move(mTheItem);
313 return {std::move(p), mPosition, std::move(mErrorMessage)};
314 }
315
316 private:
appendToLastParent(std::unique_ptr<Item> item)317 void appendToLastParent(std::unique_ptr<Item> item) {
318 auto parent = mParentStack.top();
319 assert(dynamic_cast<IncompleteItem*>(parent));
320 if (parent->type() == ARRAY) {
321 static_cast<IncompleteArray*>(parent)->add(std::move(item));
322 } else if (parent->type() == MAP) {
323 static_cast<IncompleteMap*>(parent)->add(std::move(item));
324 } else if (parent->type() == SEMANTIC) {
325 static_cast<IncompleteSemantic*>(parent)->add(std::move(item));
326 } else {
327 CHECK(false); // Impossible to get here.
328 }
329 }
330
331 std::unique_ptr<Item> mTheItem;
332 std::stack<CompoundItem*> mParentStack;
333 const uint8_t* mPosition = nullptr;
334 std::string mErrorMessage;
335 };
336
337 } // anonymous namespace
338
parse(const uint8_t * begin,const uint8_t * end,ParseClient * parseClient)339 void parse(const uint8_t* begin, const uint8_t* end, ParseClient* parseClient) {
340 parseRecursively(begin, end, parseClient);
341 }
342
343 std::tuple<std::unique_ptr<Item> /* result */, const uint8_t* /* newPos */,
344 std::string /* errMsg */>
parse(const uint8_t * begin,const uint8_t * end)345 parse(const uint8_t* begin, const uint8_t* end) {
346 FullParseClient parseClient;
347 parse(begin, end, &parseClient);
348 return parseClient.parseResult();
349 }
350
351 } // namespace cppbor
352