Each new bit updates the remainder

Last time I divided the whole shifted message at once. A high bit, once cancelled, never comes back. The past of the dividend compresses into the remainder I already have, and the next bit is the only new information.

The next prefix

Read the message from the high bit down, bits $b_{1}b_{2}\cdots$. The prefixes of $101101$ are

1
10
101
1011
10110
101101

Let $M_{k}$ be the polynomial of the first $k$ bits, and let $R_{k}=\operatorname{rem}_{G}(M_{k})$. Appending the next bit $b_{k+1}$ shifts that prefix left and writes $b_{k+1}$ in the empty place:

If $M_{k}=Q_{k}G+R_{k}$, then

so

I never need $M_{k}$ again. After $k$ bits the remainder has degree less than $r=\deg G$, which is $r$ bits of state. The loop starts at $R_{0}=0$, the empty prefix.

The direct translation shifts the remainder and then calls the long division from last time:

remainder = (remainder << 1) | static_cast<uint32_t>(bit);
remainder = polynomial_remainder(remainder, generator);

remainder << 1 with bit, that is $b_{k+1}$, in the low place is $x R_{k}+b_{k+1}$. The call is $\operatorname{rem}_{G}$ of that polynomial.

The same message

Take $G=10011$, so $r=4$, and the message $101101$. The running remainder stays under degree $4$ for the first four bits: $1$, $10$, $101$, $1011$. The fifth bit shifts $1011$ to $10110$, and the degree reaches $4$:

  10110
^ 10011
-------
  00101

The sixth bit shifts $0101$ to $01011$. The degree is $3$, so nothing is cancelled, and

That is $\operatorname{rem}_{G}(M)$, not the CRC. The CRC is $\operatorname{rem}_{G}(x^{4}M)$, which is this same walk continued through four zero bits, the room at the end of the message. From $1011$:

  10110
^ 10011
-------
  00101

then $01010$, then

  10100
^ 10011
-------
  00111

then $01110$. The remainder is $1110$, the same CRC as the one-shot division.

streaming_crc appends those width zeros and hands the whole string to streaming_remainder.

One reduction is enough

After $k$ bits, $\deg R_{k}<r$, so

The shifted remainder has at most one bit above $G$. If that bit is $0$, the degree is already less than $r$. If it is $1$, a single XOR with $G$ cancels it, because both leading coefficients are $1$. The long-division loop would run at most once. Bit width is that leading coefficient:

[[nodiscard]] uint32_t streaming_remainder(
    const std::vector<int>& dividend_bits, uint32_t divisor) {
  uint32_t remainder = 0;
  const int width = polynomial_degree(divisor);

  for (const int bit : dividend_bits) {
    remainder = (remainder << 1) | static_cast<uint32_t>(bit);
    if ((remainder & (1LL << width)) > 0) {
      remainder = remainder ^ divisor;
    }
  }

  return remainder;
}

[[nodiscard]] uint32_t streaming_crc(const std::vector<int>& message_bits,
                                     uint32_t generator) {
  const int width = polynomial_degree(generator);
  std::vector<int> augmented = message_bits;
  augmented.resize(augmented.size() + static_cast<size_t>(width), 0);
  return streaming_remainder(augmented, generator);
}

The generator’s leading $1$ is there to cancel the bit that just reached degree $r$. The next step is a register that does not store that bit.