1 // Copyright 2020 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef DEVICE_FIDO_CBOR_EXTRACT_H_
6 #define DEVICE_FIDO_CBOR_EXTRACT_H_
7
8 #include "base/callback_forward.h"
9 #include "base/component_export.h"
10 #include "base/containers/span.h"
11 #include "components/cbor/values.h"
12
13 namespace device {
14 namespace cbor_extract {
15
16 // cbor_extract implements a framework for pulling select members out of a
17 // cbor::Value and checking that they have the expected type. It is intended for
18 // use in contexts where code-size is important.
19 //
20 // The top-level cbor::Value must be a map. The extraction is driven by a series
21 // of commands specified by an array of StepOrByte. There are helper functions
22 // below for constructing the StepOrByte values and using them is strongly
23 // advised because they're constexprs, thus have no code-size cost, but they can
24 // statically check for some mistakes.
25 //
26 // As an example, consider a CBOR map {1: 2}. In order to extract the member
27 // with key '1', we can use:
28 //
29 // struct MyObj {
30 // const int64_t *value;
31 // };
32 //
33 // static constexpr StepOrByte<MyObj> kSteps[] = {
34 // ELEMENT(Is::kRequired, MyObj, value),
35 // IntKey<MyObj>(1),
36 // Stop<MyObj>(),
37 // };
38 //
39 // Note that a Stop() is required at the end of every map. If you have nested
40 // maps, they are deliminated by Stop()s.
41 //
42 // ELEMENT specifies an extraction output and whether it's required to have been
43 // found in the input. The target structure should only contain pointers and the
44 // CBOR type is taken from the type of the struct member. (See comments in
45 // |Type| for the list of C++ types.) A value with an incorrect CBOR type is an
46 // error, even if marked optional. Missing optional values result in |nullptr|.
47 //
48 // Only 16 pointers in the output structure can be addressed. Referencing a
49 // member past the 15th is a compile-time error.
50 //
51 // Output values are also pointers into the input cbor::Value, so that cannot
52 // be destroyed until processing is complete.
53 //
54 // Keys for the element are either specified by IntKey<S>(x), where x < 255, or
55 // StringKey<S>() followed by a NUL-terminated string:
56 //
57 // static constexpr StepOrByte<MyObj> kSteps[] = {
58 // ELEMENT(Is::kRequired, MyObj, value),
59 // StringKey<MyObj>(), 'k', 'e', 'y', '\0',
60 // Stop<MyObj>(),
61 // };
62 //
63 // Maps are recursed into and do not result in an output value. (If you want to
64 // extract a map itself, have an output with type |const cbor::Value *|.)
65 //
66 // static constexpr StepOrByte<MyObj> kSteps[] = {
67 // Map<MyObj>(),
68 // IntKey<MyObj>(2),
69 // ELEMENT(Is::kRequired, MyObj, value),
70 // StringKey<MyObj>(), 'k', 'e', 'y', '\0',
71 // Stop<MyObj>(),
72 // };
73 //
74 // A map cannot be optional at this time, although that can be fixed later.
75 //
76 // The target structure names gets repeated a lot. That's C++ templates for you.
77 //
78 // Because the StepOrByte helper functions are constexpr, the steps can be
79 // evaluated at compile time to produce a compact array of bytes. Each element
80 // takes a single byte.
81
82 enum class Is {
83 kRequired,
84 kOptional,
85 };
86
87 namespace internal {
88
89 // Type reflects the type of the struct members that can be given to ELEMENT().
90 enum class Type { // Output type
91 kBytestring = 0, // const std::vector<uint8_t>*
92 kString = 1, // const std::string*
93 kBoolean = 2, // const bool*
94 kInt = 3, // const int64_t*
95 kMap = 4, // <no output>
96 kArray = 5, // const std::vector<cbor::Value>*
97 kValue = 6, // const cbor::Value*
98 kStop = 7, // <no output>
99 };
100
101 // Step is an internal detail that needs to be in the header file in order to
102 // work.
103 struct Step {
104 Step() = default;
StepStep105 constexpr Step(uint8_t in_required,
106 uint8_t in_value_type,
107 uint8_t in_output_index)
108 : required(in_required),
109 value_type(in_value_type),
110 output_index(in_output_index) {}
111
112 struct {
113 bool required : 1;
114 uint8_t value_type : 3;
115 uint8_t output_index : 4;
116 };
117 };
118
119 } // namespace internal
120
121 // StepOrByte is an internal detail that needs to be in the header file in order
122 // to work.
123 template <typename S>
124 struct StepOrByte {
125 // STRING_KEY is the magic value of |u8| that indicates that this is not an
126 // integer key, but the a NUL-terminated string follows.
127 static constexpr uint8_t STRING_KEY = 255;
128
StepOrByteStepOrByte129 constexpr explicit StepOrByte(const internal::Step& in_step)
130 : step(in_step) {}
StepOrByteStepOrByte131 constexpr explicit StepOrByte(uint8_t b) : u8(b) {}
132 // This constructor is deliberately not |explicit| so that it's possible to
133 // write string keys in the steps array.
StepOrByteStepOrByte134 constexpr StepOrByte(char in_c) : c(in_c) {}
135
136 union {
137 char c;
138 uint8_t u8;
139 internal::Step step;
140 };
141 };
142
143 #define ELEMENT(required, clas, member) \
144 ::device::cbor_extract::internal::Element(required, &clas::member, \
145 offsetof(clas, member))
146
147 template <typename S>
IntKey(unsigned key)148 constexpr StepOrByte<S> IntKey(unsigned key) {
149 if (key >= 256 || key == StepOrByte<S>::STRING_KEY) {
150 // It's a compile-time error if __builtin_unreachable is reachable.
151 __builtin_unreachable();
152 }
153 return StepOrByte<S>(static_cast<char>(key));
154 }
155
156 template <typename S>
StringKey()157 constexpr StepOrByte<S> StringKey() {
158 return StepOrByte<S>(static_cast<char>(StepOrByte<S>::STRING_KEY));
159 }
160
161 template <typename S>
Map()162 constexpr StepOrByte<S> Map() {
163 return StepOrByte<S>(
164 internal::Step(true, static_cast<uint8_t>(internal::Type::kMap), -1));
165 }
166
167 template <typename S>
Stop()168 constexpr StepOrByte<S> Stop() {
169 return StepOrByte<S>(
170 internal::Step(false, static_cast<uint8_t>(internal::Type::kStop), 0));
171 }
172
173 namespace internal {
174
175 template <typename S, typename T>
Element(const Is required,T S::* member,uintptr_t offset)176 constexpr StepOrByte<S> Element(const Is required,
177 T S::*member,
178 uintptr_t offset) {
179 // This generic version of |Element| causes a compile-time error if ELEMENT
180 // is used to reference a member with an invalid type.
181 #ifdef __GNUC__
182 __builtin_unreachable();
183 #endif
184 return StepOrByte<S>('\0');
185 }
186
187 // MemberNum translates an offset into a structure into an index if the
188 // structure is considered as an array of pointers.
MemberNum(uintptr_t offset)189 constexpr uint8_t MemberNum(uintptr_t offset) {
190 #ifdef __GNUC__
191 if (offset % sizeof(void*)) {
192 __builtin_unreachable();
193 }
194 #endif
195 const uintptr_t index = offset / sizeof(void*);
196 #ifdef __GNUC__
197 if (index >= 16) {
198 __builtin_unreachable();
199 }
200 #endif
201 return static_cast<uint8_t>(index);
202 }
203
204 template <typename S>
ElementImpl(const Is required,uintptr_t offset,internal::Type type)205 constexpr StepOrByte<S> ElementImpl(const Is required,
206 uintptr_t offset,
207 internal::Type type) {
208 return StepOrByte<S>(internal::Step(required == Is::kRequired,
209 static_cast<uint8_t>(type),
210 MemberNum(offset)));
211 }
212
213 // These are specialisations of Element for each of the value output types.
214
215 template <typename S>
Element(const Is required,const std::vector<uint8_t> * S::* member,uintptr_t offset)216 constexpr StepOrByte<S> Element(const Is required,
217 const std::vector<uint8_t>* S::*member,
218 uintptr_t offset) {
219 return ElementImpl<S>(required, offset, internal::Type::kBytestring);
220 }
221
222 template <typename S>
Element(const Is required,const std::string * S::* member,uintptr_t offset)223 constexpr StepOrByte<S> Element(const Is required,
224 const std::string* S::*member,
225 uintptr_t offset) {
226 return ElementImpl<S>(required, offset, internal::Type::kString);
227 }
228
229 template <typename S>
Element(const Is required,const int64_t * S::* member,uintptr_t offset)230 constexpr StepOrByte<S> Element(const Is required,
231 const int64_t* S::*member,
232 uintptr_t offset) {
233 return ElementImpl<S>(required, offset, internal::Type::kInt);
234 }
235
236 template <typename S>
Element(const Is required,const std::vector<cbor::Value> * S::* member,uintptr_t offset)237 constexpr StepOrByte<S> Element(const Is required,
238 const std::vector<cbor::Value>* S::*member,
239 uintptr_t offset) {
240 return ElementImpl<S>(required, offset, internal::Type::kArray);
241 }
242
243 template <typename S>
Element(const Is required,const cbor::Value * S::* member,uintptr_t offset)244 constexpr StepOrByte<S> Element(const Is required,
245 const cbor::Value* S::*member,
246 uintptr_t offset) {
247 return ElementImpl<S>(required, offset, internal::Type::kValue);
248 }
249
250 template <typename S>
Element(const Is required,const bool * S::* member,uintptr_t offset)251 constexpr StepOrByte<S> Element(const Is required,
252 const bool* S::*member,
253 uintptr_t offset) {
254 return ElementImpl<S>(required, offset, internal::Type::kBoolean);
255 }
256
257 COMPONENT_EXPORT(DEVICE_FIDO)
258 bool Extract(base::span<const void*> outputs,
259 base::span<const StepOrByte<void>> steps,
260 const cbor::Value::MapValue& map);
261
262 } // namespace internal
263
264 template <typename S>
Extract(S * output,base::span<const StepOrByte<S>> steps,const cbor::Value::MapValue & map)265 bool Extract(S* output,
266 base::span<const StepOrByte<S>> steps,
267 const cbor::Value::MapValue& map) {
268 // The compiler enforces that |output| points to the correct type and this
269 // code then erases those types for use in the non-templated internal code. We
270 // don't want to template the internal code because we don't want the compiler
271 // to generate a copy for every type.
272 static_assert(sizeof(S) % sizeof(void*) == 0, "struct contains non-pointers");
273 static_assert(sizeof(S) >= sizeof(void*),
274 "empty output structures are invalid, even if you just want to "
275 "check that maps exist, because the code unconditionally "
276 "indexes offset zero.");
277 base::span<const void*> outputs(reinterpret_cast<const void**>(output),
278 sizeof(S) / sizeof(void*));
279 base::span<const StepOrByte<void>> steps_void(
280 reinterpret_cast<const StepOrByte<void>*>(steps.data()), steps.size());
281 return internal::Extract(outputs, steps_void, map);
282 }
283
284 // ForEachPublicKeyEntry is a helper for dealing with CTAP2 structures. It takes
285 // an array and, for each value in the array, it expects the value to be a map
286 // and, in the map, it expects the key "type" to result in a string. If that
287 // string is not "public-key", it ignores the array element. Otherwise it looks
288 // up |key| in the map and passes it to |callback|.
289 COMPONENT_EXPORT(DEVICE_FIDO)
290 bool ForEachPublicKeyEntry(
291 const cbor::Value::ArrayValue& array,
292 const cbor::Value& key,
293 base::RepeatingCallback<bool(const cbor::Value&)> callback);
294
295 } // namespace cbor_extract
296 } // namespace device
297
298 #endif // DEVICE_FIDO_CBOR_EXTRACT_H_
299