1 // Copyright 2023 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14
15 #include "pw_bluetooth_sapphire/internal/host/l2cap/fcs.h"
16
17 namespace bt::l2cap {
18 namespace {
19
20 // When constructed, memoizes the remainders yielded by running
21 // RemainderForOctet on each of the possible octet values.
22 class RemainderTable {
23 public:
RemainderTable()24 constexpr RemainderTable() {
25 for (unsigned i = 0; i < sizeof(remainders_) / sizeof(remainders_[0]);
26 i++) {
27 remainders_[i] = ComputeRemainderForOctet(static_cast<uint8_t>(i));
28 }
29 }
30
GetRemainderForOctet(uint8_t b) const31 constexpr uint16_t GetRemainderForOctet(uint8_t b) const {
32 return remainders_[b];
33 }
34
35 private:
36 // Subtrahend for each iteration of the linear feedback shift register (LFSR)
37 // representing the polynomial D**16 + D**15 + D**2 + D**0, written in
38 // LSb-left form with the (implicit) D**16 coefficient omitted.
39 static constexpr uint16_t kPolynomial = 0b1010'0000'0000'0001;
40
41 // Compute the remainder of |b| divided by |kPolynomial| in which each bit
42 // position is a mod 2 coefficient of a polynomial, with the rightmost bit as
43 // the coefficient of the greatest power. This performs the same function as
44 // loading LFSR bits [8:15] (v5.0, Vol 3, Part A, Section 3.3.5, Figure 3.4)
45 // with |b| bits [7:0], then operating it for eight cycles, and returns the
46 // value in the register (i.e. as if the Figure 3.4 switch were set to
47 // position 2).
48 //
49 // Note: polynomial mod 2 arithmetic implies that addition and subtraction do
50 // not carry. Hence both are equivalent to XOR, and the use of "add" or
51 // "subtract" are analogies to regular long division.
ComputeRemainderForOctet(const uint8_t b)52 static constexpr uint16_t ComputeRemainderForOctet(const uint8_t b) {
53 uint16_t accumulator = b;
54 for (size_t i = 0; i < 8; i++) {
55 // Subtract the divisor if accumulator is greater than it. Polynomial mod
56 // 2 comparison only looks at the most powerful coefficient (which is the
57 // rightmost bit).
58 const bool subtract = accumulator & 0b1;
59
60 // Because data shifts in LSb-first (Figure 3.4), this shifts in the
61 // MSb-to-LSb direction, which is towards the right.
62 accumulator >>= 1;
63 if (subtract) {
64 accumulator ^= kPolynomial;
65 }
66 }
67 return accumulator;
68 }
69
70 uint16_t remainders_[1 << 8] = {};
71 };
72
73 constexpr RemainderTable gRemainderTable;
74
75 } // namespace
76
77 // First principles derivation of the Bluetooth FCS specification referenced "A
78 // Painless Guide to CRC Error Detection Algorithms" by Ross Williams, accessed
79 // at https://archive.org/stream/PainlessCRC/crc_v3.txt
ComputeFcs(BufferView view,FrameCheckSequence initial_value)80 FrameCheckSequence ComputeFcs(BufferView view,
81 FrameCheckSequence initial_value) {
82 // Initial state of the accumulation register is all zeroes per Figure 3.5.
83 uint16_t remainder = initial_value.fcs;
84
85 // Each iteration operates the LFSR for eight cycles, shifting in an octet of
86 // message.
87 for (const uint8_t byte : view) {
88 // Add the remainder to the next eight bits of message.
89 const uint8_t dividend = static_cast<uint8_t>(byte ^ remainder);
90
91 // Because only the least significant eight bits are fed back into the LFSR,
92 // the other bits can be shifted within the accumulation register without
93 // modification.
94 const uint16_t unused_remainder = remainder >> 8;
95
96 // Perform eight rounds of division. Add the remainder produced to the bits
97 // of the remainder that we haven't used (the above shifting is associative
98 // wrt this addition).
99 remainder =
100 gRemainderTable.GetRemainderForOctet(dividend) ^ unused_remainder;
101 }
102
103 return FrameCheckSequence{remainder};
104 }
105
106 } // namespace bt::l2cap
107