1// Copyright 2017 The Fuchsia 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#include <hid-parser/parser.h> 6#include <hid-parser/item.h> 7 8#include <fbl/alloc_checker.h> 9#include <fbl/intrusive_double_list.h> 10#include <fbl/type_support.h> 11#include <fbl/unique_ptr.h> 12#include <fbl/vector.h> 13 14namespace { 15// Takes a every bit from 0 to 15 and converts them into a 16// 01 if 1 or 10 if 0. 17uint32_t expand_bitfield(uint32_t bitfield) { 18 uint32_t result = 0u; 19 for (uint8_t ix = 0; ix != 16; ++ix) { 20 uint32_t twobit = (bitfield & 0x1) ? 0x02 : 0x01; 21 result |= twobit << (2 * ix); 22 bitfield >>= 1; 23 } 24 return result; 25} 26 27// Helper template class that translates pointers from two different 28// array allocations using memory offsets. 29template <typename T> 30class Fixup { 31public: 32 Fixup(const T* src_base, T* dest_base) 33 : src_base_(src_base), dest_base_(dest_base) {} 34 35 T* operator()(const T* src) { 36 return (src == nullptr) ? nullptr : dest_base_ + (src - src_base_); 37 } 38 39private: 40 const T* const src_base_; 41 T* const dest_base_; 42}; 43 44} // namespace 45 46 47namespace hid { 48namespace impl { 49 50// Parsing hid report descriptors is is complicated by the fact that 51// there is a fair amount of flexibility on the format. In particular 52// the format is to be understood as an opcode-based program that 53// sets either some global or local state that at defined points is 54// converted in a series of fields. 55// 56// The expected top level structure is: 57// 58// App-Collection --> [Collection ... Collection] --> 59// 60// Followed by one or more [Input] [Output] [Feature] items, then 61// followed by one or more end-collection items. 62// 63// This is however insufficient. Other items are interspersed that 64// qualify the above items, both in purpose and in actual report 65// layout. 66// 67// An example for the simplest mouse input report is instructive: 68// 69// Collection-Application(Desktop, Mouse) { 70// Collection-Physical(Pointer) { 71// Input(1-bit, Data, Button, (1,0)) 72// Input(1-bit, Data, Button, (1,0)) 73// Input(1-bit, Data, Button, (1,0)) 74// Input(5-bit, Padding, Button) 75// Input(8-bit, Data, X, (127,-127)) 76// Input(8-bit, Data, Y, (127,-127)) 77// } 78// } 79// 80// All the qualifiers above inside "(" and ")" are opcodes 81// interspersed before the collection or input,output,feature 82// items. The system/utest/hid-parser has many examples captured 83// from real devices. 84 85 86// Limit on the collection count we can process, complicated devices 87// such as touch-pad are in the 10 to 20 range. This limitation can be 88// removed with a bit more code if needed. To note, the other variable 89// items such fields in a report are only limited by available memory. 90constexpr size_t kMaxCollectionCount = 128u; 91 92bool is_valid_collection(uint32_t col) { 93 return (col <= static_cast<uint32_t>(CollectionType::kVendor)); 94} 95 96bool is_app_collection(uint32_t col) { 97 return (col == static_cast<uint32_t>(CollectionType::kApplication)); 98} 99 100class ParseState { 101public: 102 static char* Alloc(size_t size) { 103 fbl::AllocChecker ac; 104 auto mem = new (&ac) char[size]; 105 return ac.check() ? mem : nullptr; 106 } 107 108 static void Free(void* mem) { 109 delete[] reinterpret_cast<char*>(mem); 110 } 111 112 ParseState() 113 : usage_range_(), 114 table_(), 115 parent_coll_(nullptr), 116 report_id_count_(0) { 117 } 118 119 bool Init() { 120 fbl::AllocChecker ac; 121 coll_.reserve(kMaxCollectionCount, &ac); 122 return ac.check(); 123 } 124 125 ParseResult Finish(DeviceDescriptor** device) { 126 // A single heap allocation is used to pack the constructed model so 127 // that the client can do a single free. There are 3 arrays in 128 // order: 129 // - The report array, one entry per unique report id. 130 // - all reports fields 131 // - all collections 132 // 133 // The bottom two need fixups. Which means that inner pointers that 134 // refer to collections in the source need to be translated to pointers 135 // valid within the destination memory area. 136 137 if (report_id_count_ == 0) { 138 // The reports don't have an id. This is scenario #1 as 139 // explained in the header. 140 report_id_count_ = 1; 141 } 142 143 size_t device_sz = 144 sizeof(DeviceDescriptor) + report_id_count_ * sizeof(ReportDescriptor); 145 size_t fields_sz = fields_.size() * sizeof(ReportField); 146 size_t collect_sz = coll_.size() * sizeof(Collection); 147 148 fbl::AllocChecker ac; 149 auto mem = Alloc(device_sz + fields_sz + collect_sz); 150 if (mem == nullptr) 151 return kParseNoMemory; 152 153 auto dev = new (mem) DeviceDescriptor { report_id_count_, {} }; 154 155 mem += device_sz; 156 auto dest_fields = reinterpret_cast<ReportField*>(mem); 157 158 mem += fields_sz; 159 auto dest_colls = reinterpret_cast<Collection*>(mem); 160 161 Fixup<Collection> coll_fixup(&coll_[0], &dest_colls[0]); 162 163 size_t ix = 0u; 164 // Copy and fix the collections first. 165 for (const auto& c: coll_) { 166 dest_colls[ix] = c; 167 dest_colls[ix].parent = coll_fixup(c.parent); 168 ++ix; 169 } 170 171 // Copy and fix the fields next. 172 ix = 0u; 173 size_t ifr = 0u; 174 int32_t last_id = -1; 175 size_t count = 0; 176 177 for (const auto& f: fields_) { 178 dest_fields[ix] = f; 179 dest_fields[ix].col = coll_fixup(f.col); 180 181 if (static_cast<int32_t>(f.report_id) != last_id) { 182 // New report id. Fill the next ReportDescriptor entry with the address 183 // of the first field, the new report id. 184 dev->report[ifr] = ReportDescriptor { f.report_id, 0, &dest_fields[ix] }; 185 186 if (ifr != 0) { 187 // Update the previous ReportDescriptor with the field count. 188 dev->report[ifr - 1].count = count; 189 } 190 191 last_id = f.report_id; 192 count = 0; 193 ++ifr; 194 } 195 196 ++count; 197 ++ix; 198 } 199 200 if (ifr != 0) { 201 // Last ReportDescriptor need field count updated. 202 dev->report[ifr - 1].count = count; 203 } 204 205 *device = dev; 206 return kParseOk; 207 } 208 209 ParseResult start_collection(uint32_t data) { // Main 210 if (!is_valid_collection(data)) 211 return kParseInvalidItemValue; 212 213 // By reserving and doing the size() check here, we ensure 214 // never a re-alloc, keeping the intra-collection pointers valid. 215 if (coll_.size() > kMaxCollectionCount) 216 return kParseOverflow; 217 218 if (parent_coll_ == nullptr) { 219 // The first collection must be an application collection. 220 if (!is_app_collection(data)) 221 return kParseUnexpectedCol; 222 } 223 224 uint32_t usage = usages_.is_empty() ? 0 : usages_[0]; 225 226 Collection col { 227 static_cast<CollectionType>(data), 228 Usage {table_.attributes.usage.page, usage}, 229 parent_coll_ 230 }; 231 232 coll_.push_back(col); 233 parent_coll_ = &coll_[coll_.size() - 1]; 234 return kParseOk; 235 } 236 237 ParseResult end_collection(uint32_t data) { 238 if (data != 0u) 239 return kParseInvalidItemValue; 240 if (parent_coll_ == nullptr) 241 return kParseInvalidTag; 242 // We don't free collection items until Finish(). 243 parent_coll_ = parent_coll_->parent; 244 // TODO(cpu): make sure there are fields between start and end 245 // otherwise this is malformed. 246 return kParseOk; 247 } 248 249 ParseResult add_field(NodeType type, uint32_t data) { // Main 250 if (coll_.size() == 0) 251 return kParseUnexectedItem; 252 253 if (!validate_ranges()) 254 return kParseInvalidRange; 255 256 auto flags = expand_bitfield(data); 257 Attributes attributes = table_.attributes; 258 259 UsageIterator usage_it(this, flags); 260 261 for (uint32_t ix = 0; ix != table_.report_count; ++ ix) { 262 if (!usage_it.next_usage(&attributes.usage.usage)) 263 return kParseInvalidUsage; 264 265 auto curr_col = &coll_[coll_.size() - 1]; 266 267 ReportField field { 268 table_.report_id, 269 attributes, 270 type, 271 flags, 272 curr_col 273 }; 274 275 fbl::AllocChecker ac; 276 fields_.push_back(field, &ac); 277 if (!ac.check()) 278 return kParseNoMemory; 279 } 280 281 return kParseOk; 282 } 283 284 ParseResult reset_usage() { // after each Main 285 // Is it an error to drop pending usages? 286 usages_.reset(); 287 usage_range_ = {}; 288 return kParseOk; 289 } 290 291 ParseResult add_usage(uint32_t data) { // Local 292 usages_.push_back(data); 293 return kParseOk; 294 } 295 296 ParseResult set_usage_min(uint32_t data) { // Local 297 if (data > UINT16_MAX) 298 return kParseUnsuported; 299 300 usage_range_.min = data; 301 return kParseOk; 302 } 303 304 ParseResult set_usage_max(uint32_t data) { // Local 305 // In add_usage() we don't restrict the value while 306 // here we do. This is because a very large range can 307 // effectively DoS the code in the usage iterator. 308 if (data > UINT16_MAX) 309 return kParseUnsuported; 310 311 usage_range_.max = data; 312 return kParseOk; 313 } 314 315 ParseResult set_usage_page(uint32_t data) { // Global 316 if (data > UINT16_MAX) 317 return kParseInvalidRange; 318 319 table_.attributes.usage.page = 320 static_cast<uint16_t>(data); 321 return kParseOk; 322 } 323 324 ParseResult set_logical_min(int32_t data) { // Global 325 table_.attributes.logc_mm.min = data; 326 return kParseOk; 327 } 328 329 ParseResult set_logical_max(int32_t data) { // Global 330 table_.attributes.logc_mm.max = data; 331 return kParseOk; 332 } 333 334 ParseResult set_physical_min(int32_t data) { // Global 335 table_.attributes.phys_mm.min = data; 336 return kParseOk; 337 } 338 339 ParseResult set_physical_max(int32_t data) { // Global 340 table_.attributes.phys_mm.max = data; 341 return kParseOk; 342 } 343 344 ParseResult set_unit(uint32_t data) { 345 // The unit parsing is a complicated per nibble 346 // accumulation of units. Leave that to application. 347 table_.attributes.unit.type = data; 348 return kParseOk; 349 } 350 351 ParseResult set_unit_exp(uint32_t data) { // Global 352 int32_t exp = static_cast<uint8_t>(data); 353 // The exponent uses a weird, not fully specified 354 // conversion, for example the value 0xf results 355 // in -1 exponent. See USB HID spec doc. 356 if (exp > 7) 357 exp = exp - 16; 358 table_.attributes.unit.exp = exp; 359 return kParseOk; 360 } 361 362 ParseResult set_report_id(uint32_t data) { // Global 363 if (data == 0) 364 return kParserInvalidID; 365 if (data > UINT8_MAX) 366 return kParseInvalidRange; 367 table_.report_id = static_cast<uint8_t>(data); 368 ++report_id_count_; 369 return kParseOk; 370 } 371 372 ParseResult set_report_count(uint32_t data) { // Global 373 table_.report_count = data; 374 return kParseOk; 375 } 376 377 ParseResult set_report_size(uint32_t data) { // Global 378 if (data > UINT8_MAX) 379 return kParseInvalidRange; 380 table_.attributes.bit_sz = static_cast<uint8_t>(data); 381 return kParseOk; 382 } 383 384 ParseResult push(uint32_t data) { // Global 385 fbl::AllocChecker ac; 386 stack_.push_back(table_, &ac); 387 return ac.check() ? kParseOk : kParseNoMemory; 388 } 389 390 ParseResult pop(uint32_t data) { // Global 391 if (stack_.size() == 0) 392 return kParserUnexpectedPop; 393 394 table_ = stack_[stack_.size() -1]; 395 stack_.pop_back(); 396 return kParseOk; 397 } 398 399private: 400 struct StateTable { 401 Attributes attributes; 402 uint32_t report_count; 403 uint8_t report_id; 404 }; 405 406 // Helper class that encapsulates the logic of assigning usages 407 // to input, output and feature items. There are 2 ways to 408 // assign usages: 409 // 1- from the UsageMinimum and UsageMaximum items 410 // 2- from the existing Usage items stored in the usages_ vector 411 // 412 // For method #2, the number of calls to next_usage() can be 413 // greater than the available usages. The standard requires in 414 // this case to return the last usage in all remaining calls. 415 // 416 // If the item is an array, only returns the first usage. 417 // TODO(cpu): this is not completely right, at least reading 418 // from the example in the spec pages 76-77, we are presented 419 // the 17-key keypad: 420 // Usage(0), Usage Minimum(53h), Usage Maximum(63h), 421 // Logical Minimum (0), Logical Maximum (17), 422 // Report Size (8), Report Count (3) 423 // Input (Data, Array) 424 // But on the other hand, the adafruit trinket presents: 425 // Report Count (1), Report Size (2) 426 // Usage (Sys Sleep (82)), Usage (Sys Power Down(81)), Usage (Sys Wake Up(83)) 427 // Input (Data,Array) 428 // 429 // In other words, array might need a lookup table to be generated 430 // see the header for a potential approach. 431 432 class UsageIterator { 433 public: 434 UsageIterator(ParseState* ps, uint32_t field_type) 435 : usages_(nullptr), 436 usage_range_(), 437 index_(0), 438 last_usage_(0), 439 is_array_(FieldTypeFlags::kArray & field_type) { 440 if ((ps->usage_range_.max == 0) && (ps->usage_range_.min == 0)) { 441 usages_ = &ps->usages_; 442 } else { 443 usage_range_ = ps->usage_range_; 444 } 445 } 446 447 bool next_usage(uint32_t* usage) { 448 if (usages_ == nullptr) { 449 *usage = static_cast<uint32_t>(usage_range_.min + index_); 450 if (*usage > static_cast<uint32_t>(usage_range_.max)) 451 return false; 452 } else { 453 *usage = (index_ < usages_->size()) ? (*usages_)[index_] : last_usage_; 454 last_usage_ = *usage; 455 } 456 if (!is_array_) 457 ++index_; 458 return true; 459 } 460 461 private: 462 const fbl::Vector<uint32_t>* usages_; 463 MinMax usage_range_; 464 uint32_t index_; 465 uint32_t last_usage_; 466 bool is_array_; 467 }; 468 469 bool validate_ranges() const { 470 if (usage_range_.min > usage_range_.max) 471 return false; 472 if (table_.attributes.logc_mm.min > table_.attributes.logc_mm.max) 473 return false; 474 return true; 475 } 476 477 // Internal state per spec: 478 MinMax usage_range_; 479 StateTable table_; 480 fbl::Vector<StateTable> stack_; 481 fbl::Vector<uint32_t> usages_; 482 // Temporary output model: 483 Collection* parent_coll_; 484 size_t report_id_count_; 485 fbl::Vector<Collection> coll_; 486 fbl::Vector<ReportField> fields_; 487}; 488 489ParseResult ProcessMainItem(const hid::Item& item, ParseState* state) { 490 ParseResult res; 491 switch (item.tag()) { 492 case Item::Tag::kInput: 493 case Item::Tag::kOutput: 494 case Item::Tag::kFeature: 495 res = state->add_field(static_cast<NodeType>(item.tag()), item.data()); 496 break; 497 case Item::Tag::kCollection: res = state->start_collection(item.data()); 498 break; 499 case Item::Tag::kEndCollection: res = state->end_collection(item.data()); 500 break; 501 default: res = kParseInvalidTag; 502 } 503 504 return (res == kParseOk)? state->reset_usage() : res; 505} 506 507ParseResult ProcessGlobalItem(const hid::Item& item, ParseState* state) { 508 switch (item.tag()) { 509 case Item::Tag::kUsagePage: return state->set_usage_page(item.data()); 510 case Item::Tag::kLogicalMinimum: return state->set_logical_min(item.signed_data()); 511 case Item::Tag::kLogicalMaximum: return state->set_logical_max(item.signed_data()); 512 case Item::Tag::kPhysicalMinimum: return state->set_physical_min(item.signed_data()); 513 case Item::Tag::kPhysicalMaximum: return state->set_physical_max(item.signed_data()); 514 case Item::Tag::kUnitExponent: return state->set_unit_exp(item.data()); 515 case Item::Tag::kUnit: return state->set_unit(item.data()); 516 case Item::Tag::kReportSize: return state->set_report_size(item.data()); 517 case Item::Tag::kReportId: return state->set_report_id(item.data()); 518 case Item::Tag::kReportCount: return state->set_report_count(item.data()); 519 case Item::Tag::kPush: return state->push(item.data()); 520 case Item::Tag::kPop: return state->pop(item.data()); 521 default: return kParseInvalidTag; 522 } 523} 524 525ParseResult ProcessLocalItem(const hid::Item& item, ParseState* state) { 526 switch (item.tag()) { 527 case Item::Tag::kUsage: return state->add_usage(item.data()); 528 case Item::Tag::kUsageMinimum: return state->set_usage_min(item.data()); 529 case Item::Tag::kUsageMaximum: return state->set_usage_max(item.data()); 530 531 case Item::Tag::kDesignatorIndex: // Fall thru. TODO(cpu) implement. 532 case Item::Tag::kDesignatorMinimum: 533 case Item::Tag::kDesignatorMaximum: 534 case Item::Tag::kStringIndex: 535 case Item::Tag::kStringMinimum: 536 case Item::Tag::kStringMaximum: 537 case Item::Tag::kDelimiter: 538 return kParseUnsuported; 539 default: return kParseInvalidTag; 540 } 541} 542 543ParseResult ProcessItem(const hid::Item& item, ParseState* state) { 544 switch (item.type()) { 545 case Item::Type::kMain: return ProcessMainItem(item, state); 546 case Item::Type::kGlobal: return ProcessGlobalItem(item, state); 547 case Item::Type::kLocal: return ProcessLocalItem(item, state); 548 default: return kParseInvalidItemType; 549 } 550} 551 552} // namespace impl 553 554ParseResult ParseReportDescriptor( 555 const uint8_t* rpt_desc, size_t desc_len, 556 DeviceDescriptor** device) { 557 558 impl::ParseState state; 559 560 if (!state.Init()) 561 return kParseNoMemory; 562 563 const uint8_t* buf = rpt_desc; 564 size_t len = desc_len; 565 while (len > 0) { 566 size_t actual = 0; 567 auto item = hid::Item::ReadNext(buf, len, &actual); 568 if (actual > len) 569 return kParseMoreNeeded; 570 if (actual == 0) 571 return kParseUnsuported; 572 573 auto pr = ProcessItem(item, &state); 574 if (pr != kParseOk) 575 return pr; 576 577 len -= actual; 578 buf += actual; 579 } 580 581 return state.Finish(device); 582} 583 584void FreeDeviceDescriptor(DeviceDescriptor* dev_desc) { 585 // memory was allocated via ParseState::Alloc() 586 impl::ParseState::Free(dev_desc); 587} 588 589ReportField* GetFirstInputField(const DeviceDescriptor* dev_desc, 590 size_t* field_count) { 591 if (dev_desc == nullptr) 592 return nullptr; 593 594 auto rep_count = dev_desc->rep_count; 595 596 for (size_t ix = 0; ix != rep_count; ix++) { 597 auto fields = dev_desc->report[ix].first_field; 598 if (fields[0].type == hid::kInput) { 599 *field_count = dev_desc->report[ix].count; 600 return &fields[0]; 601 } 602 } 603 604 *field_count = 0u; 605 return nullptr; 606} 607 608Collection* GetAppCollection(const ReportField* field) { 609 if (field == nullptr) 610 return nullptr; 611 612 auto collection = field->col; 613 while (collection != nullptr) { 614 if (collection->type == hid::CollectionType::kApplication) 615 break; 616 collection = collection->parent; 617 } 618 return collection; 619} 620 621} // namespace hid 622