| // Copyright 2017 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include <hid-parser/parser.h> |
| #include <hid-parser/item.h> |
| |
| #include <fbl/alloc_checker.h> |
| #include <fbl/intrusive_double_list.h> |
| #include <fbl/type_support.h> |
| #include <fbl/unique_ptr.h> |
| #include <fbl/vector.h> |
| |
| namespace { |
| // Takes a every bit from 0 to 15 and converts them into a |
| // 01 if 1 or 10 if 0. |
| uint32_t expand_bitfield(uint32_t bitfield) { |
| uint32_t result = 0u; |
| for (uint8_t ix = 0; ix != 16; ++ix) { |
| uint32_t twobit = (bitfield & 0x1) ? 0x02 : 0x01; |
| result |= twobit << (2 * ix); |
| bitfield >>= 1; |
| } |
| return result; |
| } |
| |
| // Helper template class that translates pointers from two different |
| // array allocations using memory offsets. |
| template <typename T> |
| class Fixup { |
| public: |
| Fixup(const T* src_base, T* dest_base) |
| : src_base_(src_base), dest_base_(dest_base) {} |
| |
| T* operator()(const T* src) { |
| return (src == nullptr) ? nullptr : dest_base_ + (src - src_base_); |
| } |
| |
| private: |
| const T* const src_base_; |
| T* const dest_base_; |
| }; |
| |
| } // namespace |
| |
| |
| namespace hid { |
| namespace impl { |
| |
| // Parsing hid report descriptors is is complicated by the fact that |
| // there is a fair amount of flexibility on the format. In particular |
| // the format is to be understood as an opcode-based program that |
| // sets either some global or local state that at defined points is |
| // converted in a series of fields. |
| // |
| // The expected top level structure is: |
| // |
| // App-Collection --> [Collection ... Collection] --> |
| // |
| // Followed by one or more [Input] [Output] [Feature] items, then |
| // followed by one or more end-collection items. |
| // |
| // This is however insufficient. Other items are interspersed that |
| // qualify the above items, both in purpose and in actual report |
| // layout. |
| // |
| // An example for the simplest mouse input report is instructive: |
| // |
| // Collection-Application(Desktop, Mouse) { |
| // Collection-Physical(Pointer) { |
| // Input(1-bit, Data, Button, (1,0)) |
| // Input(1-bit, Data, Button, (1,0)) |
| // Input(1-bit, Data, Button, (1,0)) |
| // Input(5-bit, Padding, Button) |
| // Input(8-bit, Data, X, (127,-127)) |
| // Input(8-bit, Data, Y, (127,-127)) |
| // } |
| // } |
| // |
| // All the qualifiers above inside "(" and ")" are opcodes |
| // interspersed before the collection or input,output,feature |
| // items. The system/utest/hid-parser has many examples captured |
| // from real devices. |
| |
| |
| // Limit on the collection count we can process, complicated devices |
| // such as touch-pad are in the 10 to 20 range. This limitation can be |
| // removed with a bit more code if needed. To note, the other variable |
| // items such fields in a report are only limited by available memory. |
| constexpr size_t kMaxCollectionCount = 128u; |
| |
| bool is_valid_collection(uint32_t col) { |
| return (col <= static_cast<uint32_t>(CollectionType::kVendor)); |
| } |
| |
| bool is_app_collection(uint32_t col) { |
| return (col == static_cast<uint32_t>(CollectionType::kApplication)); |
| } |
| |
| class ParseState { |
| public: |
| static char* Alloc(size_t size) { |
| fbl::AllocChecker ac; |
| auto mem = new (&ac) char[size]; |
| return ac.check() ? mem : nullptr; |
| } |
| |
| static void Free(void* mem) { |
| delete[] reinterpret_cast<char*>(mem); |
| } |
| |
| ParseState() |
| : usage_range_(), |
| table_(), |
| parent_coll_(nullptr), |
| report_id_count_(0) { |
| } |
| |
| bool Init() { |
| fbl::AllocChecker ac; |
| coll_.reserve(kMaxCollectionCount, &ac); |
| return ac.check(); |
| } |
| |
| ParseResult Finish(DeviceDescriptor** device) { |
| // A single heap allocation is used to pack the constructed model so |
| // that the client can do a single free. There are 3 arrays in |
| // order: |
| // - The report array, one entry per unique report id. |
| // - all reports fields |
| // - all collections |
| // |
| // The bottom two need fixups. Which means that inner pointers that |
| // refer to collections in the source need to be translated to pointers |
| // valid within the destination memory area. |
| |
| if (report_id_count_ == 0) { |
| // The reports don't have an id. This is scenario #1 as |
| // explained in the header. |
| report_id_count_ = 1; |
| } |
| |
| size_t device_sz = |
| sizeof(DeviceDescriptor) + report_id_count_ * sizeof(ReportDescriptor); |
| size_t fields_sz = fields_.size() * sizeof(ReportField); |
| size_t collect_sz = coll_.size() * sizeof(Collection); |
| |
| fbl::AllocChecker ac; |
| auto mem = Alloc(device_sz + fields_sz + collect_sz); |
| if (mem == nullptr) |
| return kParseNoMemory; |
| |
| auto dev = new (mem) DeviceDescriptor { report_id_count_, {} }; |
| |
| mem += device_sz; |
| auto dest_fields = reinterpret_cast<ReportField*>(mem); |
| |
| mem += fields_sz; |
| auto dest_colls = reinterpret_cast<Collection*>(mem); |
| |
| Fixup<Collection> coll_fixup(&coll_[0], &dest_colls[0]); |
| |
| size_t ix = 0u; |
| // Copy and fix the collections first. |
| for (const auto& c: coll_) { |
| dest_colls[ix] = c; |
| dest_colls[ix].parent = coll_fixup(c.parent); |
| ++ix; |
| } |
| |
| // Copy and fix the fields next. |
| ix = 0u; |
| size_t ifr = 0u; |
| int32_t last_id = -1; |
| size_t count = 0; |
| |
| for (const auto& f: fields_) { |
| dest_fields[ix] = f; |
| dest_fields[ix].col = coll_fixup(f.col); |
| |
| if (static_cast<int32_t>(f.report_id) != last_id) { |
| // New report id. Fill the next ReportDescriptor entry with the address |
| // of the first field, the new report id. |
| dev->report[ifr] = ReportDescriptor { f.report_id, 0, &dest_fields[ix] }; |
| |
| if (ifr != 0) { |
| // Update the previous ReportDescriptor with the field count. |
| dev->report[ifr - 1].count = count; |
| } |
| |
| last_id = f.report_id; |
| count = 0; |
| ++ifr; |
| } |
| |
| ++count; |
| ++ix; |
| } |
| |
| if (ifr != 0) { |
| // Last ReportDescriptor need field count updated. |
| dev->report[ifr - 1].count = count; |
| } |
| |
| *device = dev; |
| return kParseOk; |
| } |
| |
| ParseResult start_collection(uint32_t data) { // Main |
| if (!is_valid_collection(data)) |
| return kParseInvalidItemValue; |
| |
| // By reserving and doing the size() check here, we ensure |
| // never a re-alloc, keeping the intra-collection pointers valid. |
| if (coll_.size() > kMaxCollectionCount) |
| return kParseOverflow; |
| |
| if (parent_coll_ == nullptr) { |
| // The first collection must be an application collection. |
| if (!is_app_collection(data)) |
| return kParseUnexpectedCol; |
| } |
| |
| uint32_t usage = usages_.is_empty() ? 0 : usages_[0]; |
| |
| Collection col { |
| static_cast<CollectionType>(data), |
| Usage {table_.attributes.usage.page, usage}, |
| parent_coll_ |
| }; |
| |
| coll_.push_back(col); |
| parent_coll_ = &coll_[coll_.size() - 1]; |
| return kParseOk; |
| } |
| |
| ParseResult end_collection(uint32_t data) { |
| if (data != 0u) |
| return kParseInvalidItemValue; |
| if (parent_coll_ == nullptr) |
| return kParseInvalidTag; |
| // We don't free collection items until Finish(). |
| parent_coll_ = parent_coll_->parent; |
| // TODO(cpu): make sure there are fields between start and end |
| // otherwise this is malformed. |
| return kParseOk; |
| } |
| |
| ParseResult add_field(NodeType type, uint32_t data) { // Main |
| if (coll_.size() == 0) |
| return kParseUnexectedItem; |
| |
| if (!validate_ranges()) |
| return kParseInvalidRange; |
| |
| auto flags = expand_bitfield(data); |
| Attributes attributes = table_.attributes; |
| |
| UsageIterator usage_it(this, flags); |
| |
| for (uint32_t ix = 0; ix != table_.report_count; ++ ix) { |
| if (!usage_it.next_usage(&attributes.usage.usage)) |
| return kParseInvalidUsage; |
| |
| auto curr_col = &coll_[coll_.size() - 1]; |
| |
| ReportField field { |
| table_.report_id, |
| attributes, |
| type, |
| flags, |
| curr_col |
| }; |
| |
| fbl::AllocChecker ac; |
| fields_.push_back(field, &ac); |
| if (!ac.check()) |
| return kParseNoMemory; |
| } |
| |
| return kParseOk; |
| } |
| |
| ParseResult reset_usage() { // after each Main |
| // Is it an error to drop pending usages? |
| usages_.reset(); |
| usage_range_ = {}; |
| return kParseOk; |
| } |
| |
| ParseResult add_usage(uint32_t data) { // Local |
| usages_.push_back(data); |
| return kParseOk; |
| } |
| |
| ParseResult set_usage_min(uint32_t data) { // Local |
| if (data > UINT16_MAX) |
| return kParseUnsuported; |
| |
| usage_range_.min = data; |
| return kParseOk; |
| } |
| |
| ParseResult set_usage_max(uint32_t data) { // Local |
| // In add_usage() we don't restrict the value while |
| // here we do. This is because a very large range can |
| // effectively DoS the code in the usage iterator. |
| if (data > UINT16_MAX) |
| return kParseUnsuported; |
| |
| usage_range_.max = data; |
| return kParseOk; |
| } |
| |
| ParseResult set_usage_page(uint32_t data) { // Global |
| if (data > UINT16_MAX) |
| return kParseInvalidRange; |
| |
| table_.attributes.usage.page = |
| static_cast<uint16_t>(data); |
| return kParseOk; |
| } |
| |
| ParseResult set_logical_min(int32_t data) { // Global |
| table_.attributes.logc_mm.min = data; |
| return kParseOk; |
| } |
| |
| ParseResult set_logical_max(int32_t data) { // Global |
| table_.attributes.logc_mm.max = data; |
| return kParseOk; |
| } |
| |
| ParseResult set_physical_min(int32_t data) { // Global |
| table_.attributes.phys_mm.min = data; |
| return kParseOk; |
| } |
| |
| ParseResult set_physical_max(int32_t data) { // Global |
| table_.attributes.phys_mm.max = data; |
| return kParseOk; |
| } |
| |
| ParseResult set_unit(uint32_t data) { |
| // The unit parsing is a complicated per nibble |
| // accumulation of units. Leave that to application. |
| table_.attributes.unit.type = data; |
| return kParseOk; |
| } |
| |
| ParseResult set_unit_exp(uint32_t data) { // Global |
| int32_t exp = static_cast<uint8_t>(data); |
| // The exponent uses a weird, not fully specified |
| // conversion, for example the value 0xf results |
| // in -1 exponent. See USB HID spec doc. |
| if (exp > 7) |
| exp = exp - 16; |
| table_.attributes.unit.exp = exp; |
| return kParseOk; |
| } |
| |
| ParseResult set_report_id(uint32_t data) { // Global |
| if (data == 0) |
| return kParserInvalidID; |
| if (data > UINT8_MAX) |
| return kParseInvalidRange; |
| table_.report_id = static_cast<uint8_t>(data); |
| ++report_id_count_; |
| return kParseOk; |
| } |
| |
| ParseResult set_report_count(uint32_t data) { // Global |
| table_.report_count = data; |
| return kParseOk; |
| } |
| |
| ParseResult set_report_size(uint32_t data) { // Global |
| if (data > UINT8_MAX) |
| return kParseInvalidRange; |
| table_.attributes.bit_sz = static_cast<uint8_t>(data); |
| return kParseOk; |
| } |
| |
| ParseResult push(uint32_t data) { // Global |
| fbl::AllocChecker ac; |
| stack_.push_back(table_, &ac); |
| return ac.check() ? kParseOk : kParseNoMemory; |
| } |
| |
| ParseResult pop(uint32_t data) { // Global |
| if (stack_.size() == 0) |
| return kParserUnexpectedPop; |
| |
| table_ = stack_[stack_.size() -1]; |
| stack_.pop_back(); |
| return kParseOk; |
| } |
| |
| private: |
| struct StateTable { |
| Attributes attributes; |
| uint32_t report_count; |
| uint8_t report_id; |
| }; |
| |
| // Helper class that encapsulates the logic of assigning usages |
| // to input, output and feature items. There are 2 ways to |
| // assign usages: |
| // 1- from the UsageMinimum and UsageMaximum items |
| // 2- from the existing Usage items stored in the usages_ vector |
| // |
| // For method #2, the number of calls to next_usage() can be |
| // greater than the available usages. The standard requires in |
| // this case to return the last usage in all remaining calls. |
| // |
| // If the item is an array, only returns the first usage. |
| // TODO(cpu): this is not completely right, at least reading |
| // from the example in the spec pages 76-77, we are presented |
| // the 17-key keypad: |
| // Usage(0), Usage Minimum(53h), Usage Maximum(63h), |
| // Logical Minimum (0), Logical Maximum (17), |
| // Report Size (8), Report Count (3) |
| // Input (Data, Array) |
| // But on the other hand, the adafruit trinket presents: |
| // Report Count (1), Report Size (2) |
| // Usage (Sys Sleep (82)), Usage (Sys Power Down(81)), Usage (Sys Wake Up(83)) |
| // Input (Data,Array) |
| // |
| // In other words, array might need a lookup table to be generated |
| // see the header for a potential approach. |
| |
| class UsageIterator { |
| public: |
| UsageIterator(ParseState* ps, uint32_t field_type) |
| : usages_(nullptr), |
| usage_range_(), |
| index_(0), |
| last_usage_(0), |
| is_array_(FieldTypeFlags::kArray & field_type) { |
| if ((ps->usage_range_.max == 0) && (ps->usage_range_.min == 0)) { |
| usages_ = &ps->usages_; |
| } else { |
| usage_range_ = ps->usage_range_; |
| } |
| } |
| |
| bool next_usage(uint32_t* usage) { |
| if (usages_ == nullptr) { |
| *usage = static_cast<uint32_t>(usage_range_.min + index_); |
| if (*usage > static_cast<uint32_t>(usage_range_.max)) |
| return false; |
| } else { |
| *usage = (index_ < usages_->size()) ? (*usages_)[index_] : last_usage_; |
| last_usage_ = *usage; |
| } |
| if (!is_array_) |
| ++index_; |
| return true; |
| } |
| |
| private: |
| const fbl::Vector<uint32_t>* usages_; |
| MinMax usage_range_; |
| uint32_t index_; |
| uint32_t last_usage_; |
| bool is_array_; |
| }; |
| |
| bool validate_ranges() const { |
| if (usage_range_.min > usage_range_.max) |
| return false; |
| if (table_.attributes.logc_mm.min > table_.attributes.logc_mm.max) |
| return false; |
| return true; |
| } |
| |
| // Internal state per spec: |
| MinMax usage_range_; |
| StateTable table_; |
| fbl::Vector<StateTable> stack_; |
| fbl::Vector<uint32_t> usages_; |
| // Temporary output model: |
| Collection* parent_coll_; |
| size_t report_id_count_; |
| fbl::Vector<Collection> coll_; |
| fbl::Vector<ReportField> fields_; |
| }; |
| |
| ParseResult ProcessMainItem(const hid::Item& item, ParseState* state) { |
| ParseResult res; |
| switch (item.tag()) { |
| case Item::Tag::kInput: |
| case Item::Tag::kOutput: |
| case Item::Tag::kFeature: |
| res = state->add_field(static_cast<NodeType>(item.tag()), item.data()); |
| break; |
| case Item::Tag::kCollection: res = state->start_collection(item.data()); |
| break; |
| case Item::Tag::kEndCollection: res = state->end_collection(item.data()); |
| break; |
| default: res = kParseInvalidTag; |
| } |
| |
| return (res == kParseOk)? state->reset_usage() : res; |
| } |
| |
| ParseResult ProcessGlobalItem(const hid::Item& item, ParseState* state) { |
| switch (item.tag()) { |
| case Item::Tag::kUsagePage: return state->set_usage_page(item.data()); |
| case Item::Tag::kLogicalMinimum: return state->set_logical_min(item.signed_data()); |
| case Item::Tag::kLogicalMaximum: return state->set_logical_max(item.signed_data()); |
| case Item::Tag::kPhysicalMinimum: return state->set_physical_min(item.signed_data()); |
| case Item::Tag::kPhysicalMaximum: return state->set_physical_max(item.signed_data()); |
| case Item::Tag::kUnitExponent: return state->set_unit_exp(item.data()); |
| case Item::Tag::kUnit: return state->set_unit(item.data()); |
| case Item::Tag::kReportSize: return state->set_report_size(item.data()); |
| case Item::Tag::kReportId: return state->set_report_id(item.data()); |
| case Item::Tag::kReportCount: return state->set_report_count(item.data()); |
| case Item::Tag::kPush: return state->push(item.data()); |
| case Item::Tag::kPop: return state->pop(item.data()); |
| default: return kParseInvalidTag; |
| } |
| } |
| |
| ParseResult ProcessLocalItem(const hid::Item& item, ParseState* state) { |
| switch (item.tag()) { |
| case Item::Tag::kUsage: return state->add_usage(item.data()); |
| case Item::Tag::kUsageMinimum: return state->set_usage_min(item.data()); |
| case Item::Tag::kUsageMaximum: return state->set_usage_max(item.data()); |
| |
| case Item::Tag::kDesignatorIndex: // Fall thru. TODO(cpu) implement. |
| case Item::Tag::kDesignatorMinimum: |
| case Item::Tag::kDesignatorMaximum: |
| case Item::Tag::kStringIndex: |
| case Item::Tag::kStringMinimum: |
| case Item::Tag::kStringMaximum: |
| case Item::Tag::kDelimiter: |
| return kParseUnsuported; |
| default: return kParseInvalidTag; |
| } |
| } |
| |
| ParseResult ProcessItem(const hid::Item& item, ParseState* state) { |
| switch (item.type()) { |
| case Item::Type::kMain: return ProcessMainItem(item, state); |
| case Item::Type::kGlobal: return ProcessGlobalItem(item, state); |
| case Item::Type::kLocal: return ProcessLocalItem(item, state); |
| default: return kParseInvalidItemType; |
| } |
| } |
| |
| } // namespace impl |
| |
| ParseResult ParseReportDescriptor( |
| const uint8_t* rpt_desc, size_t desc_len, |
| DeviceDescriptor** device) { |
| |
| impl::ParseState state; |
| |
| if (!state.Init()) |
| return kParseNoMemory; |
| |
| const uint8_t* buf = rpt_desc; |
| size_t len = desc_len; |
| while (len > 0) { |
| size_t actual = 0; |
| auto item = hid::Item::ReadNext(buf, len, &actual); |
| if (actual > len) |
| return kParseMoreNeeded; |
| if (actual == 0) |
| return kParseUnsuported; |
| |
| auto pr = ProcessItem(item, &state); |
| if (pr != kParseOk) |
| return pr; |
| |
| len -= actual; |
| buf += actual; |
| } |
| |
| return state.Finish(device); |
| } |
| |
| void FreeDeviceDescriptor(DeviceDescriptor* dev_desc) { |
| // memory was allocated via ParseState::Alloc() |
| impl::ParseState::Free(dev_desc); |
| } |
| |
| ReportField* GetFirstInputField(const DeviceDescriptor* dev_desc, |
| size_t* field_count) { |
| if (dev_desc == nullptr) |
| return nullptr; |
| |
| auto rep_count = dev_desc->rep_count; |
| |
| for (size_t ix = 0; ix != rep_count; ix++) { |
| auto fields = dev_desc->report[ix].first_field; |
| if (fields[0].type == hid::kInput) { |
| *field_count = dev_desc->report[ix].count; |
| return &fields[0]; |
| } |
| } |
| |
| *field_count = 0u; |
| return nullptr; |
| } |
| |
| Collection* GetAppCollection(const ReportField* field) { |
| if (field == nullptr) |
| return nullptr; |
| |
| auto collection = field->col; |
| while (collection != nullptr) { |
| if (collection->type == hid::CollectionType::kApplication) |
| break; |
| collection = collection->parent; |
| } |
| return collection; |
| } |
| |
| } // namespace hid |
