A fixed shift of the growing prefix

Last time the register stayed $r$ bits wide, and the loop still read the message followed by $r$ zeros. Appending them made the input longer and added $r$ iterations. Those zeros are a fixed factor $x^{r}$. I put that factor into the polynomial the register holds, and the input stays the message.

A heavier state

After $k$ message bits, $M_{k}$ is that prefix. Last time the register held $\operatorname{rem}_{G}(M_{k})$, so $r$ zeros still had to be shifted in afterwards. The width of that shift is $\deg G$. It stays fixed while the prefix grows. This time the register holds the prefix already multiplied by that fixed power:

Degree less than $r$ is part of that remainder, so $C_{k}\equiv x^{r}M_{k}\pmod{G}$. It is the bits so far, followed by the same $r$ zeros. It becomes the CRC when the prefix has grown into the whole message, and not before.

The empty prefix is $M_{0}=0$. The register starts at $0$, and $C_{0}=0$ satisfies the same relation.

The next bit is $b_{k+1}$, so the prefix grows by

The register has to apply the same fixed shift to the longer prefix:

The remainder replaces $x^{r}M_{k}$ by $C_{k}$, and

Two contributions to $x^{r}$

$C_{k}$ still fits in the register. Split off the coefficient of $x^{r-1}$:

$t_{k}$ may be $0$. It is that fixed coefficient, the bit msb reads. The leading coefficient of $C_{k}$ is whichever highest power is actually nonzero, and it may sit below $x^{r-1}$.

One factor of $x$ lifts the coefficient of $x^{r-1}$ just past the register,

The new bit produces the same power, because the state already includes the $x^{r}$ that last time was written as trailing zeros. The two coefficients add:

In $\mathbb{F}_2$ that sum of coefficients is an XOR. Call it the feedback,

It multiplies $x^{r}$, so it sits one bit past the register: $r+1$ bits in all. Last time $x^{r}\equiv g(x)$, and that congruence is what keeps the step inside the register. The overflow is congruent to $g$, which already fits in $r$ bits. Once $t_{k}$ has moved out, the powers below $x^{r}$ are

Since $\deg L_{k}<r-1$, that product already has degree less than $r$. It is the register after (crc_register << 1) & register_mask. Therefore

The two terms are written in that order. First store $x C_{k}\bmod x^{r}$. Then, when $f_{k+1}=1$, XOR $g$. The incoming bit never enters the low end. It only joins $t_{k}$ in $f_{k+1}$.

When $t_{k}$ and $b_{k+1}$ are both $1$, the two coefficients cancel and $f_{k+1}=0$. The arriving bit is spent on the bit that just left, and $g$ stays out.

The same step is one multiplication by $x$ after the new bit has been added at $x^{r-1}$. For a polynomial $P$ of degree less than $r$,

The split is that operator. The coefficient of $x^{r-1}$ decides whether $g$ is added, and $x P\bmod x^{r}$ is the rest:

Adding $b_{k+1}$ at $x^{r-1}$ makes that coefficient $f_{k+1}$, and the lower part stays $L_{k}$, so

Example

Take $G=10011$, so $r=4$ and $g=0011$. The message is $101101$, and $\operatorname{rem}_{G}(x^{4}M)=1110$. The register starts at $0000$. These six bits are the whole input.

The first bit is $1$. The top is $0$, so the feedback is $1$. Shifting $0000$ leaves $0000$, and the bit arrives as $g$:

0000
^0011
-----
0011

The second bit is $0$. The top is $0$, the feedback is $0$, and $0011$ shifts to $0110$.

The third bit is $1$. The top is $0$, the feedback is $1$, and $0110$ shifts to $1100$:

1100
^0011
-----
1111

The fourth bit is $1$, and the top is already $1$. The feedback is $1+1=0$. Shifting $1111$ gives $1110$, and $g$ is not added. This is the cancellation: both sources of $x^{4}$ were present, and they removed each other.

The fifth bit is $0$. The top of $1110$ is $1$, the feedback is $1$, the shift is $1100$, and the XOR with $0011$ leaves $1111$.

The sixth bit is $1$. The top is $1$ again, so the feedback is $0$, and the shift takes $1111$ to $1110$.

Every message bit is in, so $M_{6}=M$ and

The register reads $1110$. The input was the six message bits, and the loop ran six times.

The program

msb is $[x^{r-1}]C_{k}$. feedback is $f_{k+1}$, written with ^. truncated_generator is $g$. (crc_register << 1) & register_mask is $x C_{k}\bmod x^{r}$. The incoming bit enters only through feedback. The masked shift plus that conditional XOR is $T_{G}(C_{k}+b_{k+1}x^{r-1})$.

// Same register as register_crc. The incoming bit is mixed into the outgoing
// msb, so the message is not padded with `width` zeros.
[[nodiscard]] uint32_t feedback_crc(const std::vector<int>& message_bits,
                                    uint32_t generator) {
  const int width = polynomial_degree(generator);
  uint32_t crc_register = 0;
  const uint32_t register_mask = (1U << width) - 1;
  const uint32_t truncated_generator = generator & register_mask;

  for (const int bit : message_bits) {
    const uint32_t msb = (crc_register >> (width - 1)) & 1U;
    const uint32_t feedback = msb ^ static_cast<uint32_t>(bit);
    crc_register = (crc_register << 1) & register_mask;
    if (feedback == 1) {
      crc_register ^= truncated_generator;
    }
  }

  return crc_register;
}