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>
diff --git a/pw_hdlc/BUILD b/pw_hdlc/BUILD
index 8316bb8..ad4a3af 100644
--- a/pw_hdlc/BUILD
+++ b/pw_hdlc/BUILD
@@ -67,6 +67,20 @@
],
)
+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(
+ 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 ad53f54..c3f0dad 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 @@
]
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("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 @@
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 b61d885..3241a39 100644
--- a/pw_hdlc/CMakeLists.txt
+++ b/pw_hdlc/CMakeLists.txt
@@ -16,8 +16,10 @@
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 b1cc262..b82ce86 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 @@
// 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 @@
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 @@
// 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 @@
current_frame_size_ += 1;
} else {
state_ = State::kFrame;
- AppendByte(new_byte ^ kUnescapeConstant);
+ AppendByte(Escape(new_byte));
}
return Status::Unavailable();
}
@@ -97,6 +90,15 @@
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 @@
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 @@
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 dcf12e3..bd17414 100644
--- a/pw_hdlc/decoder_test.cc
+++ b/pw_hdlc/decoder_test.cc
@@ -45,7 +45,7 @@
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, 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 @@
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_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 77a32a3..fd9b909 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 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 @@
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 @@
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 @@
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 0000000..7187773
--- /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 496d9b1..1e6e210 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 @@
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 @@
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 0000000..5ced2fb
--- /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 0000000..4602e85
--- /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
