CRC 계산 간단 자습서

CRC를 polynomial 나눗셈으로 이해하기

CRC는 긴 나눗셈의 나머지다. Message에 CRC를 붙이면 전체 `message+CRC`가 지정한 CRC polynomial의 배수가 된다. 검증할 때 재계산한 CRC와 저장 값을 비교하거나 `message+CRC`의 나머지가 0인지 확인할 수 있다. 많은 hardware 구현이 후자를 사용하므로 많은 protocol이 CRC 뒤에 end-of-frame flag를 둔다.

학교에서 배운 긴 나눗셈과 같지만 binary digit은 0과 1뿐이고 polynomial 나눗셈에는 carry가 없다. 더하고 빼는 대신 XOR하므로 덧셈과 뺄셈의 차이를 느슨하게 말하기도 한다.

모든 나눗셈처럼 나머지는 divisor보다 작다. 32-bit CRC의 divisor는 실제로 33-bit CRC polynomial이다. 길이가 33 bit이므로 bit 32는 항상 설정되어 있고, 보통 hexadecimal로 쓸 때 이 most significant bit를 생략한다. IEEE 754 floating-point의 숨겨진 leading bit와 같은 발상이다.

CRC는 byte가 아니라 bit string에 대해 계산하므로 byte 안의 bit endianness를 정해야 한다. 가장 좋은 오류 검출 특성을 얻으려면 실제 전송 순서와 같아야 한다. 표준 RS-232 serial은 little-endian이라 parity에 쓰이기도 하는 MSB가 마지막에 전송된다. CRC word를 message에 붙일 때도 같은 endianness 순서에 맞춘다.

나눗셈은 한 bit씩 진행한다. 매 단계에서 dividend의 다음 bit를 현재 remainder에 붙인 뒤 divisor의 적절한 배수를 빼 remainder를 범위 안으로 돌린다. Binary에서는 배수가 0 또는 1이며 XOR로 상쇄해야 하므로 remainder의 bit 32 값이 곧 배수다. Quotient는 필요 없으므로 버리고 polynomial의 해당 배수만 remainder에서 빼 다음 bit를 처리한다.

=================================
Brief tutorial on CRC computation
=================================

A CRC is a long-division remainder.  You add the CRC to the message,
and the whole thing (message+CRC) is a multiple of the given
CRC polynomial.  To check the CRC, you can either check that the
CRC matches the recomputed value, *or* you can check that the
remainder computed on the message+CRC is 0.  This latter approach
is used by a lot of hardware implementations, and is why so many
protocols put the end-of-frame flag after the CRC.

It's actually the same long division you learned in school, except that:

- We're working in binary, so the digits are only 0 and 1, and
- When dividing polynomials, there are no carries.  Rather than add and
  subtract, we just xor.  Thus, we tend to get a bit sloppy about
  the difference between adding and subtracting.

Like all division, the remainder is always smaller than the divisor.
To produce a 32-bit CRC, the divisor is actually a 33-bit CRC polynomial.
Since it's 33 bits long, bit 32 is always going to be set, so usually the
CRC is written in hex with the most significant bit omitted.  (If you're
familiar with the IEEE 754 floating-point format, it's the same idea.)

Note that a CRC is computed over a string of *bits*, so you have
to decide on the endianness of the bits within each byte.  To get
the best error-detecting properties, this should correspond to the
order they're actually sent.  For example, standard RS-232 serial is
little-endian; the most significant bit (sometimes used for parity)
is sent last.  And when appending a CRC word to a message, you should
do it in the right order, matching the endianness.

Just like with ordinary division, you proceed one digit (bit) at a time.
Each step of the division you take one more digit (bit) of the dividend
and append it to the current remainder.  Then you figure out the
appropriate multiple of the divisor to subtract to bring the remainder
back into range.  In binary, this is easy - it has to be either 0 or 1,
and to make the XOR cancel, it's just a copy of bit 32 of the remainder.

When computing a CRC, we don't care about the quotient, so we can
throw the quotient bit away, but subtract the appropriate multiple of
the polynomial from the remainder and we're back to where we started,
ready to process the next bit.

Big-endian과 little-endian bit loop

기본 big-endian code는 매 입력 bit마다 기존 remainder의 bit 31을 보고 `CRCPOLY` 또는 0을 `multiple`로 정한다. 그 뒤 remainder를 left shift하고 `next_input_bit()`를 붙여 multiple과 XOR한다. Shift된 remainder의 bit 32를 얻기 위해 shift 전 bit 31을 검사한다.

새 input bit는 32 cycle 뒤까지 의사결정에 영향을 주지 않아 처음 32 cycle은 실질 작업이 적다. CRC를 message 끝에 넣을 32-bit 공간을 만들기 위해 마지막에 0을 shift하는 32 cycle도 필요하다.

표준 최적화는 `next_input_bit()`의 병합을 실제 필요한 순간까지 재배치한다. 처음 32 cycle을 미리 계산하고 끝의 0 32개를 합치는 cycle을 완전히 생략한다. Big-endian에서는 input bit를 bit 31에 먼저 XOR하고 top bit에 따라 polynomial을 선택한 뒤 left shift한다.

이 최적화의 little-endian code는 input bit를 remainder bit 0에 XOR하고 LSB가 1이면 bit-reversed `CRCPOLY`를 선택한 뒤 right shift한다. Remainder polynomial의 highest coefficient가 binary `remainder` variable의 least significant bit에 저장된다. 나머지 endianness 세부는 bit-reversed `CRCPOLY`와 `next_input_bit()`가 감춘다.

A big-endian CRC written this way would be coded like::

	for (i = 0; i < input_bits; i++) {
		multiple = remainder & 0x80000000 ? CRCPOLY : 0;
		remainder = (remainder << 1 | next_input_bit()) ^ multiple;
	}

Notice how, to get at bit 32 of the shifted remainder, we look
at bit 31 of the remainder *before* shifting it.

But also notice how the next_input_bit() bits we're shifting into
the remainder don't actually affect any decision-making until
32 bits later.  Thus, the first 32 cycles of this are pretty boring.
Also, to add the CRC to a message, we need a 32-bit-long hole for it at
the end, so we have to add 32 extra cycles shifting in zeros at the
end of every message.

These details lead to a standard trick: rearrange merging in the
next_input_bit() until the moment it's needed.  Then the first 32 cycles
can be precomputed, and merging in the final 32 zero bits to make room
for the CRC can be skipped entirely.  This changes the code to::

	for (i = 0; i < input_bits; i++) {
		remainder ^= next_input_bit() << 31;
		multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
		remainder = (remainder << 1) ^ multiple;
	}

With this optimization, the little-endian code is particularly simple::

	for (i = 0; i < input_bits; i++) {
		remainder ^= next_input_bit();
		multiple = (remainder & 1) ? CRCPOLY : 0;
		remainder = (remainder >> 1) ^ multiple;
	}

The most significant coefficient of the remainder polynomial is stored
in the least significant bit of the binary "remainder" variable.
The other details of endianness have been hidden in CRCPOLY (which must
be bit-reversed) and next_input_bit().

Byte·word 단위 처리

`next_input_bit`가 합리적인 순서로 bit를 반환한다면 추가 bit를 마지막 순간까지 기다려 합칠 필요는 없다. 한 번에 1 bit 대신 8 bit를 처리할 수 있다.

Big-endian byte loop는 `next_input_byte() << 24`를 remainder에 XOR하고 내부 loop를 8번 돌며 top bit에 따라 `CRCPOLY`를 선택해 left shift한다. Little-endian은 byte를 그대로 XOR하고 LSB를 검사해 right shift한다.

입력이 32 bit의 배수라면 한 번에 32-bit word를 XOR하고 inner loop를 32회 돌릴 수도 있다. Message 본문은 byte 단위로 처리하고 끝의 fractional byte만 bit 단위로 처리하는 식으로 두 loop 방식을 혼합할 수 있다.

As long as next_input_bit is returning the bits in a sensible order, we don't
*have* to wait until the last possible moment to merge in additional bits.
We can do it 8 bits at a time rather than 1 bit at a time::

	for (i = 0; i < input_bytes; i++) {
		remainder ^= next_input_byte() << 24;
		for (j = 0; j < 8; j++) {
			multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
			remainder = (remainder << 1) ^ multiple;
		}
	}

Or in little-endian::

	for (i = 0; i < input_bytes; i++) {
		remainder ^= next_input_byte();
		for (j = 0; j < 8; j++) {
			multiple = (remainder & 1) ? CRCPOLY : 0;
			remainder = (remainder >> 1) ^ multiple;
		}
	}

If the input is a multiple of 32 bits, you can even XOR in a 32-bit
word at a time and increase the inner loop count to 32.

You can also mix and match the two loop styles, for example doing the
bulk of a message byte-at-a-time and adding bit-at-a-time processing
for any fractional bytes at the end.

Sarwate byte lookup table

Conditional branch 수를 줄이기 위해 software는 Dilip V. Sarwate가 1988년 Communications of the ACM 논문에서 널리 알린 byte-at-a-time table 방식을 흔히 쓴다.

한 bit만 shift해 뺄 polynomial 배수를 결정하는 대신 한 byte를 shift한다. 그러면 33-bit가 아닌 40-bit 중간 remainder가 생기며, 상위 8 bit를 index로 하는 256-entry lookup table에서 뺄 polynomial의 올바른 배수를 찾는다. 각 table entry는 해당 one-byte message의 CRC-32다.

Memory가 부족하면 4-bit shift 두 번과 16-entry table lookup을 사용할 수 있다. 이 기법으로 8 bit보다 훨씬 많이 한 번에 처리하는 것은 실용적이지 않다. 256개보다 큰 table은 memory와 특히 L1 cache를 너무 많이 사용한다.

To reduce the number of conditional branches, software commonly uses
the byte-at-a-time table method, popularized by Dilip V. Sarwate,
"Computation of Cyclic Redundancy Checks via Table Look-Up", Comm. ACM
v.31 no.8 (August 1988) p. 1008-1013.

Here, rather than just shifting one bit of the remainder to decide
in the correct multiple to subtract, we can shift a byte at a time.
This produces a 40-bit (rather than a 33-bit) intermediate remainder,
and the correct multiple of the polynomial to subtract is found using
a 256-entry lookup table indexed by the high 8 bits.

(The table entries are simply the CRC-32 of the given one-byte messages.)

When space is more constrained, smaller tables can be used, e.g. two
4-bit shifts followed by a lookup in a 16-entry table.

It is not practical to process much more than 8 bits at a time using this
technique, because tables larger than 256 entries use too much memory and,
more importantly, too much of the L1 cache.

Slicing-by-2·4·8 병렬화

더 높은 software 성능에는 Intel의 `Slicing-by-8` 계열 기법을 사용할 수 있다. Table lookup 수 자체는 바꾸지 않지만 병렬성을 높인다. 고전 Sarwate algorithm은 이전 lookup이 끝나야 다음 index를 계산할 수 있다.

Slicing-by-2는 remainder를 한 번에 16 bit shift해 48-bit 중간 remainder를 만든다. 65536-entry table 하나 대신 상위 두 byte를 서로 다른 256-entry table에서 찾는다. 각 table은 해당 byte를 상쇄하는 remainder를 담는다. 한 table은 `x^32`부터 `x^39`, 다른 table은 `x^40`부터 `x^47` 범위의 서로 다른 polynomial을 상쇄하므로 내용이 다르다.

현대 processor는 여러 memory operation을 병렬 처리하므로 두 lookup은 하나보다 거의 오래 걸리지 않아 기본 Sarwate보다 약 두 배 빠르다. Slicing-by-4는 256-entry table 4개를 사용한다. 매 단계 32-bit data를 가져와 CRC와 XOR하고 byte로 나눠 table을 찾는다. 32-bit shift로 중간 remainder의 low-order bit가 0이므로 최종 CRC는 네 lookup 결과의 XOR이다.

Slicing-by-4도 이전 네 lookup이 모두 끝나야 다음 group을 시작하므로 순차 실행 제약이 남아 load/store unit이 idle일 수 있다. Slicing-by-8은 lookup 8개를 병렬 수행한다. 매 단계 32-bit CRC를 64 bit shift하고 64-bit input data와 XOR한다. 여덟 byte 중 네 개는 이전 CRC에 의존하지 않는 input data 복사본이므로 이전 iteration을 기다리지 않고 즉시 lookup할 수 있다.

항상 네 load를 진행 중으로 유지하면 현대 superscalar processor를 바쁘게 하고 L1 cache를 충분히 활용할 수 있다.

To get higher software performance, a "slicing" technique can be used.
See "High Octane CRC Generation with the Intel Slicing-by-8 Algorithm",
ftp://download.intel.com/technology/comms/perfnet/download/slicing-by-8.pdf

This does not change the number of table lookups, but does increase
the parallelism.  With the classic Sarwate algorithm, each table lookup
must be completed before the index of the next can be computed.

A "slicing by 2" technique would shift the remainder 16 bits at a time,
producing a 48-bit intermediate remainder.  Rather than doing a single
lookup in a 65536-entry table, the two high bytes are looked up in
two different 256-entry tables.  Each contains the remainder required
to cancel out the corresponding byte.  The tables are different because the
polynomials to cancel are different.  One has non-zero coefficients from
x^32 to x^39, while the other goes from x^40 to x^47.

Since modern processors can handle many parallel memory operations, this
takes barely longer than a single table look-up and thus performs almost
twice as fast as the basic Sarwate algorithm.

This can be extended to "slicing by 4" using 4 256-entry tables.
Each step, 32 bits of data is fetched, XORed with the CRC, and the result
broken into bytes and looked up in the tables.  Because the 32-bit shift
leaves the low-order bits of the intermediate remainder zero, the
final CRC is simply the XOR of the 4 table look-ups.

But this still enforces sequential execution: a second group of table
look-ups cannot begin until the previous groups 4 table look-ups have all
been completed.  Thus, the processor's load/store unit is sometimes idle.

To make maximum use of the processor, "slicing by 8" performs 8 look-ups
in parallel.  Each step, the 32-bit CRC is shifted 64 bits and XORed
with 64 bits of input data.  What is important to note is that 4 of
those 8 bytes are simply copies of the input data; they do not depend
on the previous CRC at all.  Thus, those 4 table look-ups may commence
immediately, without waiting for the previous loop iteration.

By always having 4 loads in flight, a modern superscalar processor can
be kept busy and make full use of its L1 cache.

초기값과 최종 반전

실제 CRC 구현에는 두 가지 추가 세부가 있다. Polynomial의 배수인 message 뒤에 0 bit를 붙이면 더 큰 배수가 되므로 기본 CRC는 뒤에 붙은 zero bit나 byte를 검출하지 못한다.

이를 검출하려고 CRC를 message에 붙이기 전에 흔히 반전한다. 그러면 `message+crc`의 remainder는 0이 아니라 고정된 non-zero 값, 즉 inversion pattern `0xffffffff`의 CRC가 된다.

Message 앞에 붙은 zero bit에도 같은 문제가 있어 비슷한 해결책을 쓴다. CRC 계산을 remainder 0으로 시작하지 않고 all ones로 시작한다. Decode할 때도 같은 초기값을 사용하면 결과 해석에는 차이가 없다.

Two more details about CRC implementation in the real world:

Normally, appending zero bits to a message which is already a multiple
of a polynomial produces a larger multiple of that polynomial.  Thus,
a basic CRC will not detect appended zero bits (or bytes).  To enable
a CRC to detect this condition, it's common to invert the CRC before
appending it.  This makes the remainder of the message+crc come out not
as zero, but some fixed non-zero value.  (The CRC of the inversion
pattern, 0xffffffff.)

The same problem applies to zero bits prepended to the message, and a
similar solution is used.  Instead of starting the CRC computation with
a remainder of 0, an initial remainder of all ones is used.  As long as
you start the same way on decoding, it doesn't make a difference.