One byte, then eight shifts

Last time, after $k$ message bits, the register held

and one new bit entered at $x^{r-1}$:

$T_{G}$ is defined for polynomials of degree less than $r$. The input now comes in bytes. I still want this $C_{k}$. XOR the next byte into the top eight bits, then apply $T_{G}$ eight times, and the register should be eight bits further on.

The prefix grows by a byte

The bits are still $b_{1}, b_{2}, \ldots$, high bit first. Byte $j$, for $j=0,1,2,\ldots$, is bits $b_{8j+1}$ through $b_{8j+8}$:

The first of those bits sits on $x^{7}$. The byte $10110110$ is $x^{7}+x^{5}+x^{4}+x^{2}+x$, which is $B_{0}$ when it is the first byte.

One bit grew the prefix by $M_{k+1}=x M_{k}+b_{k+1}$. Eight bits, from a prefix whose length is a multiple of eight, are that same growth:

The byte meets the top of the register

$C_{8(j+1)}$ is the same remainder on the longer prefix:

$x^{r} M_{8j}$ and $C_{8j}$ differ by a multiple of $G$, so $x^{8}$ times either of them has the same remainder. Adding $x^{r} B_{j}$ keeps that:

A byte fits in the register when $r\ge 8$. Then $x^{r} B_{j}=x^{8}(x^{r-8} B_{j})$, and both terms carry $x^{8}$:

$\deg B_{j}\le 7$, so $x^{r-8} B_{j}$ uses degrees $r-8$ through $r-1$: the top eight coefficients. Adding it to $C_{8j}$ is the XOR of the byte into those bits.

Eight times $T_{G}$

Last time a single step was

msb reads $[x^{r-1}]$ of the register. (crc_register << 1) & register_mask is $x P\bmod x^{r}$. When that coefficient is $1$, XOR $g$, which is truncated_generator. On $C_{8j}+x^{r-8} B_{j}$ the byte is already in the polynomial, so these eight steps only multiply by $x$ and reduce.

Applied $m$ times, $T_{G}$ multiplies by $x^{m}$ and reduces:

The case $m=1$ is the definition of $T_{G}$. If the formula holds for $m$, then $T_{G}^{m}(S)$ and $x^{m} S$ differ by a multiple of $G$, so

Eight applications give the remainder above:

Byte boundaries

The message is a sequence of bytes. At each multiple of eight bits the register is $C_{8j}=\operatorname{rem}_{G}(x^{r} M_{8j})$.

The empty prefix is $M_{0}=0$, and the register starts at $C_{0}=0$. Byte $j$ replaces $C_{8j}$ by $T_{G}^{8}(C_{8j}+x^{r-8} B_{j})$, which is $C_{8(j+1)}$.

During those eight steps the register began as

so $C_{8(j+1)}=T_{G}^{8}(\widetilde{C}_{j})$. $\widetilde{C}_{j}$ already holds bits a one-bit loop would still be waiting to read. It is the register between byte boundaries. Once the byte has been fully shifted, the register is $C_{8(j+1)}$ again.

After the last byte, $M_{n}$ is the whole message and the register is the CRC,

That last byte enters as $\widetilde{C}_{j}$ for the last $j$. Eight applications of $T_{G}$ turn it into $C_{n}$.

One byte, two registers

Take $G(x)=x^{8}+x^{2}+x+1$, so $r=8$ and $g=00000111$. The message is the single byte $10110110$, and $C_{0}=00000000$.

Here $r-8=0$, so the top eight bits are the whole register and $\widetilde{C}_{0}=B_{0}=10110110$.

The left column feeds that byte through last time’s update, one bit at a time: each bit is $T_{G}(C_{k}+b_{k+1}x^{r-1})$. The first bit is $1$, the top of $00000000$ is $0$, the feedback is $1$, and XOR with $g$ after the shift leaves $00000111$.

The right column XORs the byte in before any application of $T_{G}$. The first one reads a top coefficient of $1$, so $x P\bmod x^{8}$ is XOR’d with $g$:

01101100
^00000111
---------
01101011

For most of those steps the two registers hold different bits. After eight steps both hold $00001011$. That is $C_{8}$, the CRC of this byte.

The program

The loop is the boxed update. The assert is $r\ge 8$, the same bound as $x^{r-8}$. top_byte_shift is that exponent.

// One byte at a time. The byte is mixed into the top 8 bits, then the
// register shifts once per bit. `width` must be at least 8.
[[nodiscard]] uint32_t byte_crc(const std::vector<uint8_t>& bytes,
                                uint32_t generator) {
  constexpr int kBitsPerByte = 8;
  const int width = polynomial_degree(generator);
  assert(width >= kBitsPerByte);
  uint32_t crc_register = 0;
  const uint32_t register_mask = (1U << width) - 1;
  const uint32_t truncated_generator = generator & register_mask;
  const auto top_byte_shift = static_cast<unsigned>(width - kBitsPerByte);

  for (const uint8_t byte : bytes) {
    crc_register ^= static_cast<uint32_t>(byte) << top_byte_shift;
    for (int bit_index = 0; bit_index < kBitsPerByte; ++bit_index) {
      const uint32_t msb = (crc_register >> (width - 1)) & 1U;
      crc_register = (crc_register << 1) & register_mask;
      if (msb == 1) {
        crc_register ^= truncated_generator;
      }
    }
  }

  return crc_register;
}