14
\$\begingroup\$

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, or 0b100000100110000010001110110110111, or 4374732215.
  • 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 apply.

The shortest code wins.

Test cases

input         output      (hex)
"code-golf"   147743960   08CE64D8
"jelly"       1699969158  65537886
""            0           00000000
\$\endgroup\$
  • \$\begingroup\$ If I understand right, this is doing polynomial division modulo 2 and finding the remainder, i.e. the analogue of mod in XOR multiplication. \$\endgroup\$ – xnor May 1 '16 at 1:43
  • 1
    \$\begingroup\$ Yep. This is not xnor modulo though, this is xor modulo. \$\endgroup\$ – Leaky Nun May 1 '16 at 1:45
  • \$\begingroup\$ For CRC32, do you first append 31 0's? \$\endgroup\$ – xnor May 1 '16 at 1:46
  • \$\begingroup\$ Yes – – – – – – – – – \$\endgroup\$ – Leaky Nun May 1 '16 at 1:47
  • 1
    \$\begingroup\$ @KennyLau you can ping people with their name, just like chat. \$\endgroup\$ – Rɪᴋᴇʀ May 1 '16 at 1:51
12
\$\begingroup\$

Intel x86, 34 30 29 27 bytes

Takes the address of the zero-terminated string in ESI, and returns the CRC in EBX:

31 db ac c1 e0 18 74 01 31 c3 6a 08 59 01 db 73 
06 81 f3 b7 1d c1 04 e2 f4 eb e7

Disassembly (AT&T syntax):

00000000    xorl    %ebx, %ebx
00000002    lodsb   (%esi), %al
00000003    shll    $24, %eax
00000006    je      0x9
00000008    xorl    %eax, %ebx
0000000a    pushl   $8
0000000c    popl    %ecx
0000000d    addl    %ebx, %ebx
0000000f    jae     0x17
00000011    xorl    $0x4c11db7, %ebx
00000017    loop    0xd
00000019    jmp     0x2
0000001b

Incorporating suggestions from Peter Cordes to save four more bytes. This assumes a calling convention where the direction flag for string instructions is cleared on entry.

Incorporating suggestion of Peter Ferrie to use push literal and pop to load a constant, saving one byte.

Incorporating suggestion of Peter Ferrie to jump to the second byte of an xorl %eax, %ebx instruction which is a retl instruction, combined with changing the interface of the routine to take a zero-terminated string instead of length, saving two bytes in total.

\$\endgroup\$
  • \$\begingroup\$ Use a calling convention that requires the direction flag to be cleared on entry, so you can save the cld insn (like I did in my adler32 answer). Is it normal practice to allow totally arbitrary calling conventions for asm answers? \$\endgroup\$ – Peter Cordes May 2 '16 at 5:15
  • \$\begingroup\$ Anyway, it looks like your code will work as x86-64 machine code, and you could use the x86-64 SysV x32 calling convention to take count in edi and the pointer in esi (maybe not zero-extended, so maybe fudge things and require a 64bit zero-extended pointer). (x32 so you can safely use 32bit pointer math, but still have the register-args calling convention. Since you don't use inc, there's no downside to long mode.) \$\endgroup\$ – Peter Cordes May 2 '16 at 5:17
  • \$\begingroup\$ Did you consider keeping edx in byte-reversed order? bswap edx is only 2B. shr %edx is 2B, same as your left-shift with add %edx,%edx. This probably isn't helpful; Unless it enables more optimization, you save 3B for the shl $24, %eax, but you spend 4B for xor %eax,%eax at the start and bswap %edx at the end. Zeroing eax does let you use cdq to zero %edx, so overall it's a wash. It would perform better, though: it avoids the partial-register stall/slowdown on every iteration from writing al and then reading eax with shl. :P \$\endgroup\$ – Peter Cordes May 2 '16 at 5:33
  • 1
    \$\begingroup\$ Got confused with the Adler-32 question, which has a length limit. This question doesn't have an explicit length limit. \$\endgroup\$ – Mark Adler May 2 '16 at 15:15
  • 1
    \$\begingroup\$ There might be a way to make this shorter with the PCLMULQDQ instruction. However its use tends to need a lot of constants, so possibly not. \$\endgroup\$ – Mark Adler May 2 '16 at 17:51
4
\$\begingroup\$

Jelly, 34 bytes

l2_32Ḟ4374732215æ«^
Oḅ⁹æ«32Çæ»32$¿

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Ruby, 142 bytes

Anonymous function; takes a string as input, returns an integer.

->s{z=8*i=s.size;r=0;h=4374732215<<z
l=->n{j=0;j+=1 while 0<n/=2;j}
s.bytes.map{|e|r+=e*256**(i-=1)};r<<=32
z.times{h/=2;r^=l[h]==l[r]?h:0}
r}
\$\endgroup\$
  • 2
    \$\begingroup\$ Can you change your name so that people can distinguish us? XD \$\endgroup\$ – Leaky Nun May 1 '16 at 3:18
  • 2
    \$\begingroup\$ @KennyLau must you be so picky... OK fine \$\endgroup\$ – Value Ink May 1 '16 at 3:22
  • \$\begingroup\$ I was just kidding xd \$\endgroup\$ – Leaky Nun May 1 '16 at 3:24
4
\$\begingroup\$

Jelly, 23 bytes

ḅ⁹Bµ4374732215B×ḢḊ^µL¡Ḅ

Input is in form of a list of integers. Try it online! or verify all test cases.

How it works

While Jelly has bitwise XOR, padding the input with zeroes and aligning the polynomial with the most significant binary digit makes this approach, which uses lists of bits instead, a tad shorter.

ḅ⁹Bµ4374732215B×ḢḊ^µL¡Ḅ  Main link. Argument: A (list of bytes)

ḅ⁹                       Convert A from base 256 to integer.
  B                      Convert the result to binary, yielding a list.
   µ                     Begin a new, monadic chain. Argument: B (list of bits)
    4374732215B          Convert the integer to binary, yielding a list.
                Ḣ        Pop and yield the first, most significant bit of B.
               ×         Multiply each bit in the polynomial by the popped bit.
                 ^       Compute the element-wise XOR of both lists.
                         If one of the lists is shorter, the elements of the other
                         lists do not get modified, thus avoiding the necessity
                         of right-padding B with zeroes.
                  µ      Convert the previous chain into a link.
                   L¡    Execute the chain L times, where L is the number of bits
                         in the original bit list.
                     Ḅ   Convert from binary to integer.
\$\endgroup\$
3
\$\begingroup\$

Pyth, 42 bytes

?!Q0h<#^2 32.uxN.<4374732215.as-lN32.<CQ32

Test suite.

\$\endgroup\$
3
\$\begingroup\$

CJam, 37 36 bytes

q256b32m<{Yb4374732215Yb.^Yb_Yb32>}g

Test it here.

Explanation

q               e# Read input.
256b            e# Convert to single number by treating the character codes
                e# as base-256 digits.
32m<            e# Left-shift the number by 32 bits, effectively appending 32
                e# zeros to the binary representation.
{               e# While the condition on top of the stack is truthy...
  Yb            e#   Convert the number to base 2.
  4374732215Yb  e#   Convert the polynomial to base 2.
  .^            e#   Take the bitwise XOR. If the number is longer than the
                e#   polynomial, the remaining bits will be left unchanged.
  Yb            e#   Convert the list back from base 2, effectively stripping
                e#   leading zeros for the next iteration.
  _             e#   Duplicate the result.
  Yb            e#   Convert back to base 2.
  32>           e#   Remove the first 32 bits. If any are left, continue the loop.
}g
\$\endgroup\$
  • \$\begingroup\$ q256bYb_,{(4374732215Ybf*1>.^}*Yb saves a few bytes. \$\endgroup\$ – Dennis May 2 '16 at 4:26
  • \$\begingroup\$ @Dennis That's really clever, feel free to make it a separate answer. :) \$\endgroup\$ – Martin Ender May 2 '16 at 8:16
3
\$\begingroup\$

Pyth, 28 bytes

uhS+GmxG.<C"Á·"dlhG.<Cz32

Try it online: Demonstration or Test Suite

Explanation:

uhS+GmxG.<C"..."dlhG.<Cz32   implicit: z = input string
                      Cz     convert to number
                    .<  32   shift it by 32 bits
u                            apply the following expression to G = ^,
                             until it get stuck in a loop:
     m           lhG            map each d in range(0, log2(G+1)) to:
          C"..."                   convert this string to a number (4374732215)
        .<      d                  shift it by d bits
      xG                           xor with G
   +G                           add G to this list
 hS                             take the minimum as new G
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 180 bytes

f=(s,t=(s+`\0\0\0\0`).replace(/[^]/g,(c,i)=>(c.charCodeAt()+256*!!i).toString(2).slice(!!i)))=>t[32]?f(s,t.replace(/.(.{32})/,(_,m)=>(('0b'+m^79764919)>>>0).toString(2))):+('0b'+t)

The lack of a 33-bit XOR operator, or even an unsigned 32-bit XOR operator, is unhelpful.

\$\endgroup\$
1
\$\begingroup\$

CJam, 33 bytes

q256bYb_,{(4374732215Ybf*1>.^}*Yb

Input is in form of a string. Try it online!

How it works

q                                  Read all input from STDIN.
 256bYb                            Convert it from base 256 to base 2.
       _,{                   }*    Compute the length and repeat that many times:
          (                          Shift out the first bit.
           4374732215Yb              Convert the integer to base 2.
                       f*            Multiply each bit by the shifted out bit.
                         1>          Remove the first bit.
                           .^        Compute the element-wise XOR of both lists.
                                     If one of the lists is shorter, the elements
                                     of the other lists do not get modified, thus
                                     avoiding the necessity of right-padding B with
                                     zeroes.
                               Yb  Convert the final result from base 2 to integer.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.