CS
Problems Base course RU

Problem

CRC line by line

precomputation hashing bit tricks

The CRC checksum is computed as follows. The state c is a 32-bit number, initially all ones, FFFFFFFF. For each byte b of data: c = c XOR b, and then eight times: if the lowest bit of c is one, c = (c >> 1) XOR P, otherwise c = c >> 1. At the end the result is c XOR FFFFFFFF. The number P sets the CRC variant: for the CRC-32 of zip and PNG it is EDB88320, for the CRC-32C of iSCSI and file systems 82F63B78.

Compute the CRC of every input line, over the bytes of its UTF-8 encoding without the line break.

Input

The first line holds P, eight hexadecimal digits. The second holds the number of lines q. Then q lines of text, possibly empty. All the bytes of the lines together number at most 2.5·10⁶.

Output

For each line, its CRC as eight hexadecimal digits in lower case.

Examples

Example 1

Input
EDB88320
4
Война и мир
War and Peace
War and peace
123456789
Output
5d1bede8
d9b331de
18721eda
cbf43926

Limits

Time · Python
1000 ms
Time · Go
1000 ms
Memory
256 MB
Judging
6 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

The eight steps per byte depend on just one number: the low byte of the state after the XOR with the data byte. How many different values does this number have?

2The idea

Two hundred and fifty-six. Compute in advance what the eight steps turn each of them into: T[i] is eight shifts starting from the number i. Then a byte is processed in one step: c = (c >> 8) XOR T[(c XOR b) & FF]. The table is 256 numbers, a kilobyte of memory, built once in 2048 steps.

3Walkthrough

Why this is correct. The eight steps do two things to the state: the upper 24 bits simply move 8 positions to the right, and the lower 8 bits decide which copies of P will be subtracted by XOR. The subtractions depend only on the low byte, and all they do is XOR with one and the same number, which is what is stored in T. Shift and XOR can be swapped, so eight steps equal one: a shift by a byte and an XOR with a table entry.

The bit-by-bit solution is correct but makes eight loop steps for every byte. In Python that is eight times more expensive, and on the tests with the text of War and Peace it does not fit in the limit. In real life CRC-32 is computed with ready-made functions, zlib.crc32 in Python and hash/crc32 in Go, and they use even bigger tables or special processor instructions; how the speed grows with the size of the table and where it stops growing is shown in the article “Precomputation and lookup tables”. The fifth test computes CRC-32C, which the Python standard library does not have.

A handy self-check is the string “123456789”: its CRC-32 is cbf43926, and its CRC-32C is e3069283. These “check values” are given in the description of every CRC variant.

3+Solution
4Complexity

O(256 · 8) for the table and O(1) per byte: O(total length of the lines) in all.

5Common mistakes
  • No table. Correct, but eight steps per byte: the fourth test.
  • Letters, not bytes. CRC is computed over UTF-8 bytes: a Cyrillic letter is two bytes.
  • An empty line. Its CRC is 00000000: the initial ones are removed by the final XOR.
  • Leading zeros. CRC is always printed with eight digits.

Algorithms behind it

TEC Technique Precomputation and lookup tables Compute the answers in advance and read them from a table: CRC-32 a byte per step instead of a bit, and where the table stops helping. O(table size) once, then O(1) per query 1 problem TEC Technique Bit tricks A number as a set of flags: masks, the lowest set bit, counting ones and going through subsets without recursion. O(1) per operation on a word 1 problem
The algorithms catalogue