| // Copyright 2019 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 "fcs.h" |
| |
| namespace bt::l2cap { |
| namespace { |
| |
| // When constructed, memoizes the remainders yielded by running RemainderForOctet on each of the |
| // possible octet values. |
| class RemainderTable { |
| public: |
| constexpr RemainderTable() { |
| for (unsigned i = 0; i < sizeof(remainders_) / sizeof(remainders_[0]); i++) { |
| remainders_[i] = ComputeRemainderForOctet(i); |
| } |
| } |
| |
| constexpr uint16_t GetRemainderForOctet(uint8_t b) const { return remainders_[b]; } |
| |
| private: |
| // Subtrahend for each iteration of the linear feedback shift register (LFSR) representing the |
| // polynomial D**16 + D**15 + D**2 + D**0, written in LSb-left form with the (implicit) D**16 |
| // coefficient omitted. |
| static constexpr uint16_t kPolynomial = 0b1010'0000'0000'0001; |
| |
| // Compute the remainder of |b| divided by |kPolynomial| in which each bit position is a mod 2 |
| // coefficient of a polynomial, with the rightmost bit as the coefficient of the greatest power. |
| // This performs the same function as loading LFSR bits [8:15] (v5.0, Vol 3, Part A, |
| // Section 3.3.5, Figure 3.4) with |b| bits [7:0], then operating it for eight cycles, and returns |
| // the value in the register (i.e. as if the Figure 3.4 switch were set to position 2). |
| // |
| // Note: polynomial mod 2 arithmetic implies that addition and subtraction do not carry. Hence |
| // both are equivalent to XOR, and the use of "add" or "subtract" are analogies to regular long |
| // division. |
| static constexpr uint16_t ComputeRemainderForOctet(const uint8_t b) { |
| uint16_t accumulator = b; |
| for (size_t i = 0; i < 8; i++) { |
| // Subtract the divisor if accumulator is greater than it. Polynomial mod 2 comparison only |
| // looks at the most powerful coefficient (which is the rightmost bit). |
| const bool subtract = accumulator & 0b1; |
| |
| // Because data shifts in LSb-first (Figure 3.4), this shifts in the MSb-to-LSb direction, |
| // which is towards the right. |
| accumulator >>= 1; |
| if (subtract) { |
| accumulator ^= kPolynomial; |
| } |
| } |
| return accumulator; |
| } |
| |
| uint16_t remainders_[1 << 8] = {}; |
| }; |
| |
| constexpr RemainderTable gRemainderTable; |
| |
| } // namespace |
| |
| // First principles derivation of the Bluetooth FCS specification referenced "A Painless Guide to |
| // CRC Error Detection Algorithms" by Ross Williams, accessed at |
| // https://archive.org/stream/PainlessCRC/crc_v3.txt |
| FrameCheckSequence ComputeFcs(BufferView view, FrameCheckSequence initial_value) { |
| // Initial state of the accumulation register is all zeroes per Figure 3.5. |
| uint16_t remainder = initial_value.fcs; |
| |
| // Each iteration operates the LFSR for eight cycles, shifting in an octet of message. |
| for (const uint8_t byte : view) { |
| // Add the remainder to the next eight bits of message. |
| const uint8_t dividend = byte ^ remainder; |
| |
| // Because only the least significant eight bits are fed back into the LFSR, the other bits can |
| // be shifted within the accumulation register without modification. |
| const uint16_t unused_remainder = remainder >> 8; |
| |
| // Perform eight rounds of division. Add the remainder produced to the bits of the remainder |
| // that we haven't used (the above shifting is associative wrt this addition). |
| remainder = gRemainderTable.GetRemainderForOctet(dividend) ^ unused_remainder; |
| } |
| |
| return FrameCheckSequence{remainder}; |
| } |
| |
| } // namespace bt::l2cap |