1 /*
2 * Copyright 2019 Google LLC
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 * https://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 <memory>
20 #include <sstream>
21 #include <stack>
22 #include <type_traits>
23 #include "cppbor.h"
24
25 #ifndef __TRUSTY__
26 #include <android-base/logging.h>
27 #define LOG_TAG "CppBor"
28 #else
29 #define CHECK(x) (void)(x)
30 #endif
31
32 namespace cppbor {
33
34 namespace {
35
insufficientLengthString(size_t bytesNeeded,size_t bytesAvail,const std::string & type)36 std::string insufficientLengthString(size_t bytesNeeded, size_t bytesAvail,
37 const std::string& type) {
38 char buf[1024];
39 snprintf(buf, sizeof(buf), "Need %zu byte(s) for %s, have %zu.", bytesNeeded, type.c_str(),
40 bytesAvail);
41 return std::string(buf);
42 }
43
44 template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
parseLength(const uint8_t * pos,const uint8_t * end,ParseClient * parseClient)45 std::tuple<bool, uint64_t, const uint8_t*> parseLength(const uint8_t* pos, const uint8_t* end,
46 ParseClient* parseClient) {
47 if (pos + sizeof(T) > end) {
48 parseClient->error(pos - 1, insufficientLengthString(sizeof(T), end - pos, "length field"));
49 return {false, 0, pos};
50 }
51
52 const uint8_t* intEnd = pos + sizeof(T);
53 T result = 0;
54 do {
55 result = static_cast<T>((result << 8) | *pos++);
56 } while (pos < intEnd);
57 return {true, result, pos};
58 }
59
60 std::tuple<const uint8_t*, ParseClient*> parseRecursively(const uint8_t* begin, const uint8_t* end,
61 bool emitViews, ParseClient* parseClient);
62
handleUint(uint64_t value,const uint8_t * hdrBegin,const uint8_t * hdrEnd,ParseClient * parseClient)63 std::tuple<const uint8_t*, ParseClient*> handleUint(uint64_t value, const uint8_t* hdrBegin,
64 const uint8_t* hdrEnd,
65 ParseClient* parseClient) {
66 std::unique_ptr<Item> item = std::make_unique<Uint>(value);
67 return {hdrEnd,
68 parseClient->item(item, hdrBegin, hdrEnd /* valueBegin */, hdrEnd /* itemEnd */)};
69 }
70
handleNint(uint64_t value,const uint8_t * hdrBegin,const uint8_t * hdrEnd,ParseClient * parseClient)71 std::tuple<const uint8_t*, ParseClient*> handleNint(uint64_t value, const uint8_t* hdrBegin,
72 const uint8_t* hdrEnd,
73 ParseClient* parseClient) {
74 if (value > std::numeric_limits<int64_t>::max()) {
75 parseClient->error(hdrBegin, "NINT values that don't fit in int64_t are not supported.");
76 return {hdrBegin, nullptr /* end parsing */};
77 }
78 std::unique_ptr<Item> item = std::make_unique<Nint>(-1 - static_cast<int64_t>(value));
79 return {hdrEnd,
80 parseClient->item(item, hdrBegin, hdrEnd /* valueBegin */, hdrEnd /* itemEnd */)};
81 }
82
handleBool(uint64_t value,const uint8_t * hdrBegin,const uint8_t * hdrEnd,ParseClient * parseClient)83 std::tuple<const uint8_t*, ParseClient*> handleBool(uint64_t value, const uint8_t* hdrBegin,
84 const uint8_t* hdrEnd,
85 ParseClient* parseClient) {
86 std::unique_ptr<Item> item = std::make_unique<Bool>(value == TRUE);
87 return {hdrEnd,
88 parseClient->item(item, hdrBegin, hdrEnd /* valueBegin */, hdrEnd /* itemEnd */)};
89 }
90
handleNull(const uint8_t * hdrBegin,const uint8_t * hdrEnd,ParseClient * parseClient)91 std::tuple<const uint8_t*, ParseClient*> handleNull(const uint8_t* hdrBegin, const uint8_t* hdrEnd,
92 ParseClient* parseClient) {
93 std::unique_ptr<Item> item = std::make_unique<Null>();
94 return {hdrEnd,
95 parseClient->item(item, hdrBegin, hdrEnd /* valueBegin */, hdrEnd /* itemEnd */)};
96 }
97
98 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)99 std::tuple<const uint8_t*, ParseClient*> handleString(uint64_t length, const uint8_t* hdrBegin,
100 const uint8_t* valueBegin, const uint8_t* end,
101 const std::string& errLabel,
102 ParseClient* parseClient) {
103 ssize_t signed_length = static_cast<ssize_t>(length);
104 if (end - valueBegin < signed_length || signed_length < 0) {
105 parseClient->error(hdrBegin, insufficientLengthString(length, end - valueBegin, errLabel));
106 return {hdrBegin, nullptr /* end parsing */};
107 }
108
109 std::unique_ptr<Item> item = std::make_unique<T>(valueBegin, valueBegin + length);
110 return {valueBegin + length,
111 parseClient->item(item, hdrBegin, valueBegin, valueBegin + length)};
112 }
113
114 class IncompleteItem {
115 public:
116 static IncompleteItem* cast(Item* item);
117
~IncompleteItem()118 virtual ~IncompleteItem() {}
119 virtual void add(std::unique_ptr<Item> item) = 0;
120 virtual std::unique_ptr<Item> finalize() && = 0;
121 };
122
123 class IncompleteArray : public Array, public IncompleteItem {
124 public:
IncompleteArray(size_t size)125 explicit IncompleteArray(size_t size) : mSize(size) {}
126
127 // We return the "complete" size, rather than the actual size.
size() const128 size_t size() const override { return mSize; }
129
add(std::unique_ptr<Item> item)130 void add(std::unique_ptr<Item> item) override {
131 mEntries.push_back(std::move(item));
132 }
133
finalize()134 virtual std::unique_ptr<Item> finalize() && override {
135 // Use Array explicitly so the compiler picks the correct ctor overload
136 Array* thisArray = this;
137 return std::make_unique<Array>(std::move(*thisArray));
138 }
139
140 private:
141 size_t mSize;
142 };
143
144 class IncompleteMap : public Map, public IncompleteItem {
145 public:
IncompleteMap(size_t size)146 explicit IncompleteMap(size_t size) : mSize(size) {}
147
148 // We return the "complete" size, rather than the actual size.
size() const149 size_t size() const override { return mSize; }
150
add(std::unique_ptr<Item> item)151 void add(std::unique_ptr<Item> item) override {
152 if (mKeyHeldForAdding) {
153 mEntries.push_back({std::move(mKeyHeldForAdding), std::move(item)});
154 } else {
155 mKeyHeldForAdding = std::move(item);
156 }
157 }
158
finalize()159 virtual std::unique_ptr<Item> finalize() && override {
160 return std::make_unique<Map>(std::move(*this));
161 }
162
163 private:
164 std::unique_ptr<Item> mKeyHeldForAdding;
165 size_t mSize;
166 };
167
168 class IncompleteSemanticTag : public SemanticTag, public IncompleteItem {
169 public:
IncompleteSemanticTag(uint64_t value)170 explicit IncompleteSemanticTag(uint64_t value) : SemanticTag(value) {}
171
172 // We return the "complete" size, rather than the actual size.
size() const173 size_t size() const override { return 1; }
174
add(std::unique_ptr<Item> item)175 void add(std::unique_ptr<Item> item) override { mTaggedItem = std::move(item); }
176
finalize()177 virtual std::unique_ptr<Item> finalize() && override {
178 return std::make_unique<SemanticTag>(std::move(*this));
179 }
180 };
181
cast(Item * item)182 IncompleteItem* IncompleteItem::cast(Item* item) {
183 CHECK(item->isCompound());
184 // Semantic tag must be check first, because SemanticTag::type returns the wrapped item's type.
185 if (item->asSemanticTag()) {
186 #if __has_feature(cxx_rtti)
187 CHECK(dynamic_cast<IncompleteSemanticTag*>(item));
188 #endif
189 return static_cast<IncompleteSemanticTag*>(item);
190 } else if (item->type() == ARRAY) {
191 #if __has_feature(cxx_rtti)
192 CHECK(dynamic_cast<IncompleteArray*>(item));
193 #endif
194 return static_cast<IncompleteArray*>(item);
195 } else if (item->type() == MAP) {
196 #if __has_feature(cxx_rtti)
197 CHECK(dynamic_cast<IncompleteMap*>(item));
198 #endif
199 return static_cast<IncompleteMap*>(item);
200 } else {
201 CHECK(false); // Impossible to get here.
202 }
203 return nullptr;
204 }
205
handleEntries(size_t entryCount,const uint8_t * hdrBegin,const uint8_t * pos,const uint8_t * end,const std::string & typeName,bool emitViews,ParseClient * parseClient)206 std::tuple<const uint8_t*, ParseClient*> handleEntries(size_t entryCount, const uint8_t* hdrBegin,
207 const uint8_t* pos, const uint8_t* end,
208 const std::string& typeName,
209 bool emitViews,
210 ParseClient* parseClient) {
211 while (entryCount > 0) {
212 --entryCount;
213 if (pos == end) {
214 parseClient->error(hdrBegin, "Not enough entries for " + typeName + ".");
215 return {hdrBegin, nullptr /* end parsing */};
216 }
217 std::tie(pos, parseClient) = parseRecursively(pos, end, emitViews, parseClient);
218 if (!parseClient) return {hdrBegin, nullptr};
219 }
220 return {pos, parseClient};
221 }
222
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,bool emitViews,ParseClient * parseClient)223 std::tuple<const uint8_t*, ParseClient*> handleCompound(
224 std::unique_ptr<Item> item, uint64_t entryCount, const uint8_t* hdrBegin,
225 const uint8_t* valueBegin, const uint8_t* end, const std::string& typeName,
226 bool emitViews, ParseClient* parseClient) {
227 parseClient =
228 parseClient->item(item, hdrBegin, valueBegin, valueBegin /* don't know the end yet */);
229 if (!parseClient) return {hdrBegin, nullptr};
230
231 const uint8_t* pos;
232 std::tie(pos, parseClient) =
233 handleEntries(entryCount, hdrBegin, valueBegin, end, typeName, emitViews, parseClient);
234 if (!parseClient) return {hdrBegin, nullptr};
235
236 return {pos, parseClient->itemEnd(item, hdrBegin, valueBegin, pos)};
237 }
238
parseRecursively(const uint8_t * begin,const uint8_t * end,bool emitViews,ParseClient * parseClient)239 std::tuple<const uint8_t*, ParseClient*> parseRecursively(const uint8_t* begin, const uint8_t* end,
240 bool emitViews, ParseClient* parseClient) {
241 if (begin == end) {
242 parseClient->error(
243 begin,
244 "Input buffer is empty. Begin and end cannot point to the same location.");
245 return {begin, nullptr};
246 }
247
248 const uint8_t* pos = begin;
249
250 MajorType type = static_cast<MajorType>(*pos & 0xE0);
251 uint8_t tagInt = *pos & 0x1F;
252 ++pos;
253
254 bool success = true;
255 uint64_t addlData;
256 if (tagInt < ONE_BYTE_LENGTH) {
257 addlData = tagInt;
258 } else if (tagInt > EIGHT_BYTE_LENGTH) {
259 parseClient->error(
260 begin,
261 "Reserved additional information value or unsupported indefinite length item.");
262 return {begin, nullptr};
263 } else {
264 switch (tagInt) {
265 case ONE_BYTE_LENGTH:
266 std::tie(success, addlData, pos) = parseLength<uint8_t>(pos, end, parseClient);
267 break;
268
269 case TWO_BYTE_LENGTH:
270 std::tie(success, addlData, pos) = parseLength<uint16_t>(pos, end, parseClient);
271 break;
272
273 case FOUR_BYTE_LENGTH:
274 std::tie(success, addlData, pos) = parseLength<uint32_t>(pos, end, parseClient);
275 break;
276
277 case EIGHT_BYTE_LENGTH:
278 std::tie(success, addlData, pos) = parseLength<uint64_t>(pos, end, parseClient);
279 break;
280
281 default:
282 CHECK(false); // It's impossible to get here
283 break;
284 }
285 }
286
287 if (!success) return {begin, nullptr};
288
289 switch (type) {
290 case UINT:
291 return handleUint(addlData, begin, pos, parseClient);
292
293 case NINT:
294 return handleNint(addlData, begin, pos, parseClient);
295
296 case BSTR:
297 if (emitViews) {
298 return handleString<ViewBstr>(addlData, begin, pos, end, "byte string", parseClient);
299 } else {
300 return handleString<Bstr>(addlData, begin, pos, end, "byte string", parseClient);
301 }
302
303 case TSTR:
304 if (emitViews) {
305 return handleString<ViewTstr>(addlData, begin, pos, end, "text string", parseClient);
306 } else {
307 return handleString<Tstr>(addlData, begin, pos, end, "text string", parseClient);
308 }
309
310 case ARRAY:
311 return handleCompound(std::make_unique<IncompleteArray>(addlData), addlData, begin, pos,
312 end, "array", emitViews, parseClient);
313
314 case MAP:
315 return handleCompound(std::make_unique<IncompleteMap>(addlData), addlData * 2, begin,
316 pos, end, "map", emitViews, parseClient);
317
318 case SEMANTIC:
319 return handleCompound(std::make_unique<IncompleteSemanticTag>(addlData), 1, begin, pos,
320 end, "semantic", emitViews, parseClient);
321
322 case SIMPLE:
323 switch (addlData) {
324 case TRUE:
325 case FALSE:
326 return handleBool(addlData, begin, pos, parseClient);
327 case NULL_V:
328 return handleNull(begin, pos, parseClient);
329 default:
330 parseClient->error(begin, "Unsupported floating-point or simple value.");
331 return {begin, nullptr};
332 }
333 }
334 CHECK(false); // Impossible to get here.
335 return {};
336 }
337
338 class FullParseClient : public ParseClient {
339 public:
item(std::unique_ptr<Item> & item,const uint8_t *,const uint8_t *,const uint8_t * end)340 virtual ParseClient* item(std::unique_ptr<Item>& item, const uint8_t*, const uint8_t*,
341 const uint8_t* end) override {
342 if (mParentStack.empty() && !item->isCompound()) {
343 // This is the first and only item.
344 mTheItem = std::move(item);
345 mPosition = end;
346 return nullptr; // We're done.
347 }
348
349 if (item->isCompound()) {
350 // Starting a new compound data item, i.e. a new parent. Save it on the parent stack.
351 // It's safe to save a raw pointer because the unique_ptr is guaranteed to stay in
352 // existence until the corresponding itemEnd() call.
353 mParentStack.push(item.get());
354 return this;
355 } else {
356 appendToLastParent(std::move(item));
357 return this;
358 }
359 }
360
itemEnd(std::unique_ptr<Item> & item,const uint8_t *,const uint8_t *,const uint8_t * end)361 virtual ParseClient* itemEnd(std::unique_ptr<Item>& item, const uint8_t*, const uint8_t*,
362 const uint8_t* end) override {
363 CHECK(item->isCompound() && item.get() == mParentStack.top());
364 mParentStack.pop();
365 IncompleteItem* incompleteItem = IncompleteItem::cast(item.get());
366 std::unique_ptr<Item> finalizedItem = std::move(*incompleteItem).finalize();
367
368 if (mParentStack.empty()) {
369 mTheItem = std::move(finalizedItem);
370 mPosition = end;
371 return nullptr; // We're done
372 } else {
373 appendToLastParent(std::move(finalizedItem));
374 return this;
375 }
376 }
377
error(const uint8_t * position,const std::string & errorMessage)378 virtual void error(const uint8_t* position, const std::string& errorMessage) override {
379 mPosition = position;
380 mErrorMessage = errorMessage;
381 }
382
383 std::tuple<std::unique_ptr<Item> /* result */, const uint8_t* /* newPos */,
384 std::string /* errMsg */>
parseResult()385 parseResult() {
386 std::unique_ptr<Item> p = std::move(mTheItem);
387 return {std::move(p), mPosition, std::move(mErrorMessage)};
388 }
389
390 private:
appendToLastParent(std::unique_ptr<Item> item)391 void appendToLastParent(std::unique_ptr<Item> item) {
392 auto parent = mParentStack.top();
393 IncompleteItem::cast(parent)->add(std::move(item));
394 }
395
396 std::unique_ptr<Item> mTheItem;
397 std::stack<Item*> mParentStack;
398 const uint8_t* mPosition = nullptr;
399 std::string mErrorMessage;
400 };
401
402 } // anonymous namespace
403
parse(const uint8_t * begin,const uint8_t * end,ParseClient * parseClient)404 void parse(const uint8_t* begin, const uint8_t* end, ParseClient* parseClient) {
405 parseRecursively(begin, end, false, parseClient);
406 }
407
408 std::tuple<std::unique_ptr<Item> /* result */, const uint8_t* /* newPos */,
409 std::string /* errMsg */>
parse(const uint8_t * begin,const uint8_t * end)410 parse(const uint8_t* begin, const uint8_t* end) {
411 FullParseClient parseClient;
412 parse(begin, end, &parseClient);
413 return parseClient.parseResult();
414 }
415
parseWithViews(const uint8_t * begin,const uint8_t * end,ParseClient * parseClient)416 void parseWithViews(const uint8_t* begin, const uint8_t* end, ParseClient* parseClient) {
417 parseRecursively(begin, end, true, parseClient);
418 }
419
420 std::tuple<std::unique_ptr<Item> /* result */, const uint8_t* /* newPos */,
421 std::string /* errMsg */>
parseWithViews(const uint8_t * begin,const uint8_t * end)422 parseWithViews(const uint8_t* begin, const uint8_t* end) {
423 FullParseClient parseClient;
424 parseWithViews(begin, end, &parseClient);
425 return parseClient.parseResult();
426 }
427
428 } // namespace cppbor
429