14
1
Credits
This challenge originated from @miles.
Create a function that computes the CRC32 hash of an input string. The input will be an ASCII string of any length. The output will be the CRC32 hash of that input string.
Explanation
The algorithm of CRC32 and other CRC are essentially the same, so only CRC3 will be demonstrated here.
Firstly, you have the generator polynomial, which is actually a 4-bit [n+1] integer (would be 33-bit in CRC32).
In this example, the generator polynomial is 1101
.
Then, you will have the string to be hashed, which in this example would be 00010010111100101011001101
.
00010010111100101011001101|000 (1) append three [n] "0"s
1101 (2) align with highest bit
00001000111100101011001101|000 (3) XOR (1) and (2)
1101 (4) align with highest bit
00000101111100101011001101|000 (5) XOR (3) and (4)
1101 (6) align with highest bit
00000011011100101011001101|000 (7) XOR (5) and (6)
1101 (8) align with highest bit
00000000001100101011001101|000 (9) XOR (7) and (8)
1101 (10) align with highest bit
00000000000001101011001101|000 (11) XOR (9) and (10)
1101 (12) align with highest bit
00000000000000000011001101|000 (13) XOR (11) and (12)
1101 (14) align with highest bit
00000000000000000000011101|000 (15) XOR (13) and (14)
1101 (16) align with highest bit
00000000000000000000000111|000 (17) XOR (15) and (16)
110 1 (18) align with highest bit
00000000000000000000000001|100 (19) XOR (17) and (18)
1 101 (20) align with highest bit
00000000000000000000000000|001 (21) XOR (19) and (20)
^--------REGION 1--------^ ^2^
The remainder obtained at (21)
, when region 1 is zero, which is 001
, would be the result of the CRC3 hash.
Specs
- The generator polynomial is
0x104C11DB7
, or0b100000100110000010001110110110111
, or4374732215
. - Input can be a string or a list of integers, or any other reasonable format.
- Output be a hex string or just an integer, or any other reasonable format.
- Built-ins that compute the CRC32 hash are not allowed.
Goal
Standard rules for code-golf apply.
The shortest code wins.
Test cases
input output (hex)
"code-golf" 147743960 08CE64D8
"jelly" 1699969158 65537886
"" 0 00000000
If I understand right, this is doing polynomial division modulo 2 and finding the remainder, i.e. the analogue of mod in XOR multiplication.
– xnor – 2016-05-01T01:43:02.5701
Yep. This is not xnor modulo though, this is xor modulo.
– Leaky Nun – 2016-05-01T01:45:41.980For CRC32, do you first append 31 0's? – xnor – 2016-05-01T01:46:58.493
Yes – – – – – – – – – – Leaky Nun – 2016-05-01T01:47:41.130
1@KennyLau you can ping people with their name, just like chat. – Rɪᴋᴇʀ – 2016-05-01T01:51:28.493
In your example, why is the remainder
001
rather than1100
? – Dennis – 2016-05-01T02:09:11.443@Dennis Added . – Leaky Nun – 2016-05-01T02:10:59.833
Are builtins for polynomial division allowed? – Luis Mendo – 2016-05-01T02:12:20.913
@LuisMendo I don't think there will be any built-in suitable for this challenge. Would you care to provide an example? – Leaky Nun – 2016-05-01T02:13:07.937
But isn't the CRC in your example a 3-bit hash? – Dennis – 2016-05-01T02:13:49.793
@KennyLau I meant this. I'm not sure it helps. It's standard polynomial division
– Luis Mendo – 2016-05-01T02:17:16.733@Dennis Should be fixed now? – Leaky Nun – 2016-05-01T02:23:35.443
@LuisMendo I don't think that would be useful. – Leaky Nun – 2016-05-01T02:24:20.980
You say the string in the example is
00010010111100101011001010
, but the last four bits in stage 1 are1101
. – Dennis – 2016-05-02T05:51:49.827