blob: e6b9057aeccdbc942ec275063a390ae9c03cb6b2 [file] [log] [blame]
// 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 <fbl/alloc_checker.h>
#include <fbl/intrusive_double_list.h>
#include <fbl/vector.h>
#include <hid-parser/item.h>
#include <hid-parser/parser.h>
namespace {
#define DIV_ROUND_UP(n, d) (((n) + (d)-1) / (d))
// Temporary structure to keep report id data.
struct ReportID {
bool has_report_id;
uint8_t report_id;
size_t input_count;
size_t output_count;
size_t feature_count;
};
// 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));
}
bool report_id_has_items(ReportID id) {
return (id.input_count != 0) || (id.feature_count != 0) || (id.output_count != 0);
}
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) {
// First 8 bits of a report are the report ID.
table_.attributes.offset = 8;
}
bool Init() {
fbl::AllocChecker ac;
coll_.reserve(kMaxCollectionCount, &ac);
if (!ac.check())
return false;
// Add the initial report ID representing "no report_id".
ReportID empty_report_id = {false, 0, 0, 0, 0};
report_ids_.push_back(empty_report_id, &ac);
if (!ac.check())
return false;
table_.report_id = &report_ids_[0];
return true;
}
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.
// Check if we actually have items or report ids before going forward.
if (coll_.size() == 0) {
return kParseMoreNeeded;
}
// If there's one report in |report_ids_| then there's just the null id.
bool no_report_id = report_ids_.size() == 1;
// If we have ids, then erase the null id since it shouldn't have items in it.
if (!no_report_id) {
report_ids_.erase(0);
}
size_t report_count = report_ids_.size();
size_t device_sz = sizeof(DeviceDescriptor) + report_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_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;
for (const ReportID& report_id : report_ids_) {
size_t field_count = 0;
// If we don't have report ids, we start at 0 offset.
// Otherwise we start at an 8 bit offset because the first
// byte is the report id.
size_t input_bit_sz = (no_report_id) ? 0 : 8;
size_t input_count = 0;
ReportField* input_fields_start = &dest_fields[ix];
size_t output_bit_sz = (no_report_id) ? 0 : 8;
size_t output_count = 0;
ReportField* output_fields_start = &input_fields_start[report_id.input_count];
size_t feature_bit_sz = (no_report_id) ? 0 : 8;
size_t feature_count = 0;
ReportField* feature_fields_start = &output_fields_start[report_id.output_count];
// Fill the ReportDescriptor entry with the address
// of the first field, and the report id.
dev->report[ifr] = {};
dev->report[ifr].report_id = report_id.report_id;
dev->report[ifr].input_fields = input_fields_start;
dev->report[ifr].output_fields = output_fields_start;
dev->report[ifr].feature_fields = feature_fields_start;
for (const auto& f : fields_) {
if (f.report_id != report_id.report_id)
continue;
switch (f.type) {
case NodeType::kInput:
if (input_count == report_id.input_count)
return kParseOverflow;
input_fields_start[input_count] = f;
input_fields_start[input_count].col = coll_fixup(f.col);
input_fields_start[input_count].attr.offset = static_cast<uint32_t>(input_bit_sz);
input_bit_sz += f.attr.bit_sz;
++input_count;
break;
case NodeType::kOutput:
if (output_count == report_id.output_count)
return kParseOverflow;
output_fields_start[output_count] = f;
output_fields_start[output_count].col = coll_fixup(f.col);
output_fields_start[output_count].attr.offset = static_cast<uint32_t>(output_bit_sz);
output_bit_sz += f.attr.bit_sz;
++output_count;
break;
case NodeType::kFeature:
if (feature_count == report_id.feature_count)
return kParseOverflow;
feature_fields_start[feature_count] = f;
feature_fields_start[feature_count].col = coll_fixup(f.col);
feature_fields_start[feature_count].attr.offset = static_cast<uint32_t>(feature_bit_sz);
feature_bit_sz += f.attr.bit_sz;
++feature_count;
break;
}
++field_count;
++ix;
}
// If we haven't seen any fields reset the size to 0.
if (input_count == 0)
input_bit_sz = 0;
if (output_count == 0)
output_bit_sz = 0;
if (feature_count == 0)
feature_bit_sz = 0;
// Update the report ReportDescriptor with the final information.
dev->report[ifr].input_count = input_count;
dev->report[ifr].input_byte_sz = DIV_ROUND_UP(input_bit_sz, 8);
dev->report[ifr].output_count = output_count;
dev->report[ifr].output_byte_sz = DIV_ROUND_UP(output_bit_sz, 8);
dev->report[ifr].feature_count = feature_count;
dev->report[ifr].feature_byte_sz = DIV_ROUND_UP(feature_bit_sz, 8);
++ifr;
}
*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 kParseUnexpectedItem;
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) {
attributes.usage = usage_it.next_usage();
auto curr_col = &coll_[coll_.size() - 1];
ReportField field{table_.report_id->report_id, attributes, type, flags, curr_col};
// If physical min/max are zero they should be set to logical values.
if (field.attr.phys_mm.min == 0 && field.attr.phys_mm.max == 0) {
field.attr.phys_mm.min = field.attr.logc_mm.min;
field.attr.phys_mm.max = field.attr.logc_mm.max;
}
fbl::AllocChecker ac;
fields_.push_back(field, &ac);
if (!ac.check())
return kParseNoMemory;
switch (type) {
case kInput:
table_.report_id->input_count++;
break;
case kOutput:
table_.report_id->output_count++;
break;
case kFeature:
table_.report_id->feature_count++;
break;
}
}
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(const hid::Item& item) { // Global
if (table_.attributes.logc_mm.min >= 0) {
table_.attributes.logc_mm.max = item.data();
} else {
table_.attributes.logc_mm.max = item.signed_data();
}
return kParseOk;
}
ParseResult set_physical_min(int32_t data) { // Global
table_.attributes.phys_mm.min = data;
return kParseOk;
}
ParseResult set_physical_max(const hid::Item& item) { // Global
if (table_.attributes.phys_mm.min >= 0) {
table_.attributes.phys_mm.max = item.data();
} else {
table_.attributes.phys_mm.max = item.signed_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;
// It's an error to define a report id after items have been defined with no id.
if (report_id_has_items(report_ids_[0]))
return kParserMissingID;
// Check if we've seen the report id before.
uint8_t id = static_cast<uint8_t>(data);
ReportID* report_ids = report_ids_.data();
for (size_t i = 0; i < report_ids_.size(); i++) {
if (report_ids[i].report_id == id) {
table_.report_id = &report_ids[i];
return kParseOk;
}
}
// We haven't, so allocate the new report id.
ReportID new_report_id = {true, id, 0, 0, 0};
fbl::AllocChecker ac;
report_ids_.push_back(new_report_id, &ac);
if (!ac.check())
return kParseNoMemory;
table_.report_id = &report_ids_[report_ids_.size() - 1];
return kParseOk;
}
ParseResult set_report_count(uint32_t data) { // Global
if (data > UINT16_MAX) {
return kParseNoMemory;
}
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;
ReportID* 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) {
usage_page_ = ps->table_.attributes.usage.page;
if ((ps->usage_range_.max == 0) && (ps->usage_range_.min == 0)) {
usages_ = &ps->usages_;
has_usage_ = (usages_->size() != 0);
} else {
usage_range_ = ps->usage_range_;
has_usage_ = true;
}
}
Usage next_usage() {
Usage usage = {};
if (!has_usage_) {
return usage;
}
int64_t usage_long = 0;
if (usages_ == nullptr) {
usage_long = usage_range_.min + index_;
if (usage_long > usage_range_.max)
usage_long = usage_range_.max;
} else {
usage_long = (index_ < usages_->size()) ? (*usages_)[index_] : last_usage_;
last_usage_ = static_cast<uint32_t>(usage_long);
}
if (!is_array_) {
++index_;
}
usage.page = usage_page_;
usage.usage = static_cast<uint32_t>(usage_long);
return usage;
}
private:
const fbl::Vector<uint32_t>* usages_;
MinMax usage_range_;
int16_t usage_page_;
uint32_t index_;
uint32_t last_usage_;
bool is_array_;
bool has_usage_;
};
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_;
fbl::Vector<ReportID> report_ids_;
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);
case Item::Tag::kPhysicalMinimum:
return state->set_physical_min(item.signed_data());
case Item::Tag::kPhysicalMaximum:
return state->set_physical_max(item);
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 (rpt_desc == nullptr || device == nullptr)
return kParseMoreNeeded;
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);
}
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;
}
#undef DIV_ROUND_UP
} // namespace hid