diff options
author | Alexei Frolov <frolv@google.com> | 2021-01-20 15:14:06 -0800 |
---|---|---|
committer | CQ Bot Account <pigweed-scoped@luci-project-accounts.iam.gserviceaccount.com> | 2021-01-27 22:22:35 +0000 |
commit | 5039a81e9139a1dd1bdd3f21bc350f86ecabd72e (patch) | |
tree | d4272170306070a4fb86912a4ab40d82408861a7 /pw_hdlc | |
parent | 5af57d1b50867227041391ac4f2286ff6dba42b4 (diff) | |
download | pigweed-5039a81e9139a1dd1bdd3f21bc350f86ecabd72e.tar.gz |
pw_hdlc: Add wire-encoded frame parser
This adds a PacketParser for wire-encoded HDLC frames to the HDLC
module. To support this, the decoder is updated to calculate the FCS in
a single pass as it processes data.
Change-Id: Ided11f4442d3b804a3d5a6b66b588bb50a5d0176
Reviewed-on: https://pigweed-review.googlesource.com/c/pigweed/pigweed/+/30180
Reviewed-by: Keir Mierle <keir@google.com>
Reviewed-by: Wyatt Hepler <hepler@google.com>
Commit-Queue: Alexei Frolov <frolv@google.com>
Diffstat (limited to 'pw_hdlc')
-rw-r--r-- | pw_hdlc/BUILD | 23 | ||||
-rw-r--r-- | pw_hdlc/BUILD.gn | 32 | ||||
-rw-r--r-- | pw_hdlc/CMakeLists.txt | 2 | ||||
-rw-r--r-- | pw_hdlc/decoder.cc | 50 | ||||
-rw-r--r-- | pw_hdlc/decoder_test.cc | 10 | ||||
-rw-r--r-- | pw_hdlc/public/pw_hdlc/decoder.h | 27 | ||||
-rw-r--r-- | pw_hdlc/public/pw_hdlc/wire_packet_parser.h | 45 | ||||
-rw-r--r-- | pw_hdlc/pw_hdlc_private/protocol.h | 5 | ||||
-rw-r--r-- | pw_hdlc/wire_packet_parser.cc | 51 | ||||
-rw-r--r-- | pw_hdlc/wire_packet_parser_test.cc | 131 |
10 files changed, 342 insertions, 34 deletions
diff --git a/pw_hdlc/BUILD b/pw_hdlc/BUILD index 8316bb8b3..ad4a3af9a 100644 --- a/pw_hdlc/BUILD +++ b/pw_hdlc/BUILD @@ -67,6 +67,20 @@ pw_cc_library( ], ) +pw_cc_library( + name = "packet_parser", + srcs = ["wire_packet_parser.cc"], + hdrs = ["public/pw_hdlc/wire_packet_parser.h"], + includes = ["public"], + deps = [ + ":pw_hdlc", + "//pw_assert", + "//pw_bytes", + "//pw_checksum", + "//pw_router:packet_parser", + ], +) + cc_test( name = "encoder_test", srcs = ["encoder_test.cc"], @@ -89,6 +103,15 @@ cc_test( ) cc_test( + name = "wire_packet_parser_test", + srcs = ["wire_packet_parser_test.cc"], + deps = [ + ":packet_parser", + "//pw_bytes", + ], +) + +cc_test( name = "rpc_channel_test", srcs = ["rpc_channel_test.cc"], deps = [ diff --git a/pw_hdlc/BUILD.gn b/pw_hdlc/BUILD.gn index ad53f5492..c3f0dade5 100644 --- a/pw_hdlc/BUILD.gn +++ b/pw_hdlc/BUILD.gn @@ -1,4 +1,4 @@ -# Copyright 2020 The Pigweed Authors +# Copyright 2021 The Pigweed Authors # # Licensed under the Apache License, Version 2.0 (the "License"); you may not # use this file except in compliance with the License. You may obtain a copy of @@ -38,13 +38,11 @@ pw_source_set("decoder") { ] public_deps = [ dir_pw_bytes, + dir_pw_checksum, dir_pw_result, dir_pw_status, ] - deps = [ - dir_pw_checksum, - dir_pw_log, - ] + deps = [ dir_pw_log ] friend = [ ":*" ] } @@ -86,11 +84,27 @@ pw_source_set("pw_rpc") { ] } +pw_source_set("packet_parser") { + public_configs = [ ":default_config" ] + public = [ "public/pw_hdlc/wire_packet_parser.h" ] + sources = [ "wire_packet_parser.cc" ] + public_deps = [ + ":pw_hdlc", + "$dir_pw_router:packet_parser", + dir_pw_assert, + ] + deps = [ + dir_pw_bytes, + dir_pw_checksum, + ] +} + pw_test_group("tests") { tests = [ ":encoder_test", ":decoder_test", ":rpc_channel_test", + ":wire_packet_parser_test", ] group_deps = [ "$dir_pw_preprocessor:tests", @@ -127,6 +141,14 @@ pw_test("rpc_channel_test") { sources = [ "rpc_channel_test.cc" ] } +pw_test("wire_packet_parser_test") { + deps = [ + ":packet_parser", + dir_pw_bytes, + ] + sources = [ "wire_packet_parser_test.cc" ] +} + pw_doc_group("docs") { sources = [ "docs.rst", diff --git a/pw_hdlc/CMakeLists.txt b/pw_hdlc/CMakeLists.txt index b61d88551..3241a39c8 100644 --- a/pw_hdlc/CMakeLists.txt +++ b/pw_hdlc/CMakeLists.txt @@ -16,8 +16,10 @@ include($ENV{PW_ROOT}/pw_build/pigweed.cmake) pw_auto_add_simple_module(pw_hdlc PUBLIC_DEPS + pw_assert pw_bytes pw_result + pw_router.packet_parser pw_rpc.common pw_status pw_stream diff --git a/pw_hdlc/decoder.cc b/pw_hdlc/decoder.cc index b1cc2625c..b82ce866a 100644 --- a/pw_hdlc/decoder.cc +++ b/pw_hdlc/decoder.cc @@ -16,18 +16,12 @@ #include "pw_assert/assert.h" #include "pw_bytes/endian.h" -#include "pw_checksum/crc32.h" #include "pw_hdlc_private/protocol.h" #include "pw_log/log.h" using std::byte; namespace pw::hdlc { -namespace { - -constexpr byte kUnescapeConstant = byte{0x20}; - -} // namespace Result<Frame> Decoder::Process(const byte new_byte) { switch (state_) { @@ -37,7 +31,7 @@ Result<Frame> Decoder::Process(const byte new_byte) { // Report an error if non-flag bytes were read between frames. if (current_frame_size_ != 0u) { - current_frame_size_ = 0; + Reset(); return Status::DataLoss(); } } else { @@ -50,9 +44,8 @@ Result<Frame> Decoder::Process(const byte new_byte) { if (new_byte == kFlag) { const Status status = CheckFrame(); - state_ = State::kFrame; const size_t completed_frame_size = current_frame_size_; - current_frame_size_ = 0; + Reset(); if (status.ok()) { return Frame(buffer_.first(completed_frame_size)); @@ -71,7 +64,7 @@ Result<Frame> Decoder::Process(const byte new_byte) { // The flag character cannot be escaped; return an error. if (new_byte == kFlag) { state_ = State::kFrame; - current_frame_size_ = 0; + Reset(); return Status::DataLoss(); } @@ -84,7 +77,7 @@ Result<Frame> Decoder::Process(const byte new_byte) { current_frame_size_ += 1; } else { state_ = State::kFrame; - AppendByte(new_byte ^ kUnescapeConstant); + AppendByte(Escape(new_byte)); } return Status::Unavailable(); } @@ -97,6 +90,15 @@ void Decoder::AppendByte(byte new_byte) { buffer_[current_frame_size_] = new_byte; } + if (current_frame_size_ >= last_read_bytes_.size()) { + // A byte will be ejected. Add it to the running checksum. + fcs_.Update(last_read_bytes_[last_read_bytes_index_]); + } + + last_read_bytes_[last_read_bytes_index_] = new_byte; + last_read_bytes_index_ = + (last_read_bytes_index_ + 1) % last_read_bytes_.size(); + // Always increase size: if it is larger than the buffer, overflow occurred. current_frame_size_ += 1; } @@ -113,6 +115,11 @@ Status Decoder::CheckFrame() const { return Status::DataLoss(); } + if (!VerifyFrameCheckSequence()) { + PW_LOG_ERROR("Frame check sequence verification failed"); + return Status::DataLoss(); + } + if (current_frame_size_ > max_size()) { PW_LOG_ERROR("Frame size [%lu] exceeds the maximum buffer size [%lu]", static_cast<unsigned long>(current_frame_size_), @@ -120,19 +127,22 @@ Status Decoder::CheckFrame() const { return Status::ResourceExhausted(); } - if (!VerifyFrameCheckSequence()) { - PW_LOG_ERROR("Frame check sequence verification failed"); - return Status::DataLoss(); - } - return OkStatus(); } bool Decoder::VerifyFrameCheckSequence() const { - uint32_t fcs = bytes::ReadInOrder<uint32_t>( - std::endian::little, buffer_.data() + current_frame_size_ - sizeof(fcs)); - return fcs == checksum::Crc32::Calculate( - buffer_.first(current_frame_size_ - sizeof(fcs))); + // De-ring the last four bytes read, which at this point contain the FCS. + std::array<std::byte, sizeof(uint32_t)> fcs_buffer; + size_t index = last_read_bytes_index_; + + for (size_t i = 0; i < fcs_buffer.size(); ++i) { + fcs_buffer[i] = last_read_bytes_[index]; + index = (index + 1) % last_read_bytes_.size(); + } + + uint32_t actual_fcs = + bytes::ReadInOrder<uint32_t>(std::endian::little, fcs_buffer); + return actual_fcs == fcs_.value(); } } // namespace pw::hdlc diff --git a/pw_hdlc/decoder_test.cc b/pw_hdlc/decoder_test.cc index dcf12e31c..bd174142c 100644 --- a/pw_hdlc/decoder_test.cc +++ b/pw_hdlc/decoder_test.cc @@ -45,7 +45,7 @@ TEST(Decoder, Clear) { decoder.Process(bytes::String("~1234abcd"), [](const Result<Frame>&) { FAIL(); }); - decoder.clear(); + decoder.Clear(); Status status = Status::Unknown(); decoder.Process( @@ -83,12 +83,12 @@ TEST(Decoder, MinimumSizedBuffer) { TEST(Decoder, TooLargeForBuffer_ReportsResourceExhausted) { DecoderBuffer<8> decoder; - for (byte b : bytes::String("~123456789")) { + for (byte b : bytes::String("~12345\x1c\x3a\xf5\xcb")) { EXPECT_EQ(Status::Unavailable(), decoder.Process(b).status()); } EXPECT_EQ(Status::ResourceExhausted(), decoder.Process(kFlag).status()); - for (byte b : bytes::String("~123456789012345678901234567890")) { + for (byte b : bytes::String("~12345678901234567890\xf2\x19\x63\x90")) { EXPECT_EQ(Status::Unavailable(), decoder.Process(b).status()); } EXPECT_EQ(Status::ResourceExhausted(), decoder.Process(kFlag).status()); @@ -99,7 +99,7 @@ TEST(Decoder, TooLargeForBuffer_StaysWithinBufferBoundaries) { Decoder decoder(std::span(buffer.data(), 8)); - for (byte b : bytes::String("~1234567890123456789012345678901234567890")) { + for (byte b : bytes::String("~12345678901234567890\xf2\x19\x63\x90")) { EXPECT_EQ(Status::Unavailable(), decoder.Process(b).status()); } @@ -113,7 +113,7 @@ TEST(Decoder, TooLargeForBuffer_StaysWithinBufferBoundaries) { TEST(Decoder, TooLargeForBuffer_DecodesNextFrame) { DecoderBuffer<8> decoder; - for (byte b : bytes::String("~123456789012345678901234567890")) { + for (byte b : bytes::String("~12345678901234567890\xf2\x19\x63\x90")) { EXPECT_EQ(Status::Unavailable(), decoder.Process(b).status()); } EXPECT_EQ(Status::ResourceExhausted(), decoder.Process(kFlag).status()); diff --git a/pw_hdlc/public/pw_hdlc/decoder.h b/pw_hdlc/public/pw_hdlc/decoder.h index 77a32a388..fd9b909aa 100644 --- a/pw_hdlc/public/pw_hdlc/decoder.h +++ b/pw_hdlc/public/pw_hdlc/decoder.h @@ -20,6 +20,7 @@ #include <functional> // std::invoke #include "pw_bytes/span.h" +#include "pw_checksum/crc32.h" #include "pw_result/result.h" #include "pw_status/status.h" @@ -74,7 +75,11 @@ class Frame { class Decoder { public: constexpr Decoder(ByteSpan buffer) - : buffer_(buffer), current_frame_size_(0), state_(State::kInterFrame) {} + : buffer_(buffer), + last_read_bytes_({}), + last_read_bytes_index_(0), + current_frame_size_(0), + state_(State::kInterFrame) {} Decoder(const Decoder&) = delete; Decoder& operator=(const Decoder&) = delete; @@ -109,9 +114,9 @@ class Decoder { size_t max_size() const { return buffer_.size(); } // Clears and resets the decoder. - void clear() { - current_frame_size_ = 0; + void Clear() { state_ = State::kInterFrame; + Reset(); }; private: @@ -122,6 +127,12 @@ class Decoder { kFrameEscape, }; + void Reset() { + current_frame_size_ = 0; + last_read_bytes_index_ = 0; + fcs_.clear(); + } + void AppendByte(std::byte new_byte); Status CheckFrame() const; @@ -130,6 +141,16 @@ class Decoder { const ByteSpan buffer_; + // Ring buffer of the last four bytes read into the current frame, to allow + // calculating the frame's CRC incrementally. As data is evicted from this + // buffer, it is added to the running CRC. Once a frame is complete, the + // buffer contains the frame's FCS. + std::array<std::byte, sizeof(uint32_t)> last_read_bytes_; + size_t last_read_bytes_index_; + + // Incremental checksum of the current frame. + checksum::Crc32 fcs_; + size_t current_frame_size_; State state_; diff --git a/pw_hdlc/public/pw_hdlc/wire_packet_parser.h b/pw_hdlc/public/pw_hdlc/wire_packet_parser.h new file mode 100644 index 000000000..7187773eb --- /dev/null +++ b/pw_hdlc/public/pw_hdlc/wire_packet_parser.h @@ -0,0 +1,45 @@ +// Copyright 2021 The Pigweed Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. +#pragma once + +#include "pw_assert/light.h" +#include "pw_router/packet_parser.h" + +namespace pw::hdlc { + +// HDLC frame parser for routers that operates on wire-encoded frames. +// +// Currently, this assumes 1-byte HDLC address fields. An optional address_bits +// value can be provided to the constructor to use a smaller address size. +class WirePacketParser final : public router::PacketParser { + public: + constexpr WirePacketParser(uint8_t address_bits = 8) + : address_(0), address_shift_(8 - address_bits) { + PW_ASSERT(address_bits <= 8); + } + + // Verifies and parses an HDLC frame. Packet passed in is expected to be a + // single, complete, wire-encoded frame, starting and ending with a flag. + bool Parse(ConstByteSpan packet) final; + + std::optional<uint32_t> GetDestinationAddress() const final { + return address_; + } + + private: + uint8_t address_; + uint8_t address_shift_; +}; + +} // namespace pw::hdlc diff --git a/pw_hdlc/pw_hdlc_private/protocol.h b/pw_hdlc/pw_hdlc_private/protocol.h index 496d9b13b..1e6e21074 100644 --- a/pw_hdlc/pw_hdlc_private/protocol.h +++ b/pw_hdlc/pw_hdlc_private/protocol.h @@ -1,4 +1,4 @@ -// Copyright 2020 The Pigweed Authors +// Copyright 2021 The Pigweed Authors // // Licensed under the Apache License, Version 2.0 (the "License"); you may not // use this file except in compliance with the License. You may obtain a copy of @@ -19,6 +19,7 @@ namespace pw::hdlc { inline constexpr std::byte kFlag = std::byte{0x7E}; inline constexpr std::byte kEscape = std::byte{0x7D}; +inline constexpr std::byte kEscapeConstant = std::byte{0x20}; inline constexpr std::array<std::byte, 2> kEscapedFlag = {kEscape, std::byte{0x5E}}; @@ -29,6 +30,8 @@ constexpr bool NeedsEscaping(std::byte b) { return (b == kFlag || b == kEscape); } +constexpr std::byte Escape(std::byte b) { return b ^ kEscapeConstant; } + // Class that manages the 1-byte control field of an HDLC U-frame. class UFrameControl { public: diff --git a/pw_hdlc/wire_packet_parser.cc b/pw_hdlc/wire_packet_parser.cc new file mode 100644 index 000000000..5ced2fb6b --- /dev/null +++ b/pw_hdlc/wire_packet_parser.cc @@ -0,0 +1,51 @@ +// Copyright 2021 The Pigweed Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#include "pw_hdlc/wire_packet_parser.h" + +#include "pw_bytes/endian.h" +#include "pw_checksum/crc32.h" +#include "pw_hdlc/decoder.h" +#include "pw_hdlc_private/protocol.h" + +namespace pw::hdlc { + +bool WirePacketParser::Parse(ConstByteSpan packet) { + if (packet.size_bytes() < Frame::kMinSizeBytes) { + return false; + } + + if (packet.front() != kFlag || packet.back() != kFlag) { + return false; + } + + // Partially decode into a buffer with space only for the first two bytes + // (address and control) of the frame. The decoder will verify the frame's + // FCS field. + std::array<std::byte, 2> buffer = {}; + Decoder decoder(buffer); + Status status = Status::Unknown(); + + decoder.Process(packet, [&status](const Result<Frame>& result) { + status = result.status(); + }); + + // Address is the first byte in the packet. + address_ = static_cast<uint8_t>(buffer[0]) >> address_shift_; + + // RESOURCE_EXHAUSTED is expected as the buffer is too small for the packet. + return status.ok() || status.IsResourceExhausted(); +} + +} // namespace pw::hdlc diff --git a/pw_hdlc/wire_packet_parser_test.cc b/pw_hdlc/wire_packet_parser_test.cc new file mode 100644 index 000000000..4602e8556 --- /dev/null +++ b/pw_hdlc/wire_packet_parser_test.cc @@ -0,0 +1,131 @@ +// Copyright 2021 The Pigweed Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#include "pw_hdlc/wire_packet_parser.h" + +#include "gtest/gtest.h" +#include "pw_bytes/array.h" +#include "pw_hdlc_private/protocol.h" + +namespace pw::hdlc { +namespace { + +constexpr uint8_t kAddress = 0x6a; +constexpr uint8_t kControl = 0x03; + +TEST(WirePacketParser, Parse_ValidPacket) { + WirePacketParser parser; + EXPECT_TRUE(parser.Parse(bytes::Concat( + kFlag, kAddress, kControl, bytes::String("hello"), 0xc40cefe0, kFlag))); + auto maybe_address = parser.GetDestinationAddress(); + EXPECT_TRUE(maybe_address.has_value()); + EXPECT_EQ(maybe_address.value(), kAddress); +} + +TEST(WirePacketParser, Parse_EscapedAddress) { + WirePacketParser parser; + EXPECT_TRUE(parser.Parse(bytes::Concat(kFlag, + kEscape, + uint8_t{0x7e ^ 0x20}, + kControl, + bytes::String("hello"), + 0x579d573d, + kFlag))); + auto maybe_address = parser.GetDestinationAddress(); + EXPECT_TRUE(maybe_address.has_value()); + EXPECT_EQ(maybe_address.value(), 0x7eu); +} + +TEST(WirePacketParser, Parse_EscapedPayload) { + WirePacketParser parser; + EXPECT_TRUE(parser.Parse(bytes::Concat(kFlag, + kAddress, + kControl, + bytes::String("hello"), + kEscapedEscape, + bytes::String("world"), + 0x9a9b934a, + kFlag))); + auto maybe_address = parser.GetDestinationAddress(); + EXPECT_TRUE(maybe_address.has_value()); + EXPECT_EQ(maybe_address.value(), kAddress); +} + +TEST(WirePacketParser, Parse_EscapedFcs) { + WirePacketParser parser; + EXPECT_TRUE(parser.Parse(bytes::Concat(kFlag, + kAddress, + kControl, + bytes::String("qwertyu"), + // FCS: e0 7d e9 3b + bytes::String("\x3b\xe9\x7d\x5d\xe0"), + kFlag))); + auto maybe_address = parser.GetDestinationAddress(); + EXPECT_TRUE(maybe_address.has_value()); + EXPECT_EQ(maybe_address.value(), kAddress); +} + +TEST(WirePacketParser, Parse_MultipleEscapes) { + WirePacketParser parser; + EXPECT_TRUE(parser.Parse(bytes::Concat(kFlag, + kEscapedFlag, + kControl, + kEscapedEscape, + kEscapedFlag, + kEscapedFlag, + 0xc85df51d, + kFlag))); + auto maybe_address = parser.GetDestinationAddress(); + EXPECT_TRUE(maybe_address.has_value()); + EXPECT_EQ(maybe_address.value(), static_cast<uint32_t>(kFlag)); +} + +TEST(WirePacketParser, Parse_AddressBits) { + WirePacketParser parser(4); + EXPECT_TRUE(parser.Parse(bytes::Concat(kFlag, + std::byte{0xab}, + kControl, + bytes::String("hello"), + 0xae667bdf, + kFlag))); + auto maybe_address = parser.GetDestinationAddress(); + EXPECT_TRUE(maybe_address.has_value()); + EXPECT_EQ(maybe_address.value(), 0xau); +} + +TEST(WirePacketParser, Parse_BadFcs) { + WirePacketParser parser; + EXPECT_FALSE(parser.Parse(bytes::Concat( + kFlag, kAddress, kControl, bytes::String("hello"), 0x1badda7a, kFlag))); +} + +TEST(WirePacketParser, Parse_DoubleEscape) { + WirePacketParser parser; + EXPECT_FALSE(parser.Parse(bytes::Concat( + kFlag, kAddress, kControl, bytes::String("hello"), 0x01027d7d, kFlag))); +} + +TEST(WirePacketParser, Parse_FlagInFrame) { + WirePacketParser parser; + EXPECT_FALSE(parser.Parse(bytes::Concat( + kFlag, kAddress, kControl, bytes::String("he~lo"), 0xdbae98fe, kFlag))); +} + +TEST(WirePacketParser, Parse_EmptyPacket) { + WirePacketParser parser; + EXPECT_FALSE(parser.Parse({})); +} + +} // namespace +} // namespace pw::hdlc |