Créditos

Esse desafio teve origem em @miles .

Crie uma função que calcule o hash CRC32 de uma sequência de entrada. A entrada será uma sequência ASCII de qualquer tamanho. A saída será o hash CRC32 dessa sequência de entrada.

Explicação

O algoritmo do CRC32 e outro CRC é essencialmente o mesmo, portanto apenas o CRC3 será demonstrado aqui.

Primeiramente, você tem o polinômio do gerador, que na verdade é um número inteiro de 4 bits [n + 1] (seria de 33 bits no CRC32).

Neste exemplo, o polinômio do gerador é 1101.

Então, você terá a string a ser hash, o que neste exemplo seria 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^

O restante obtido em (21), quando a região 1 é zero, ou seja 001, seria o resultado do hash CRC3.

Especificações

• O polinômio do gerador é 0x104C11DB7, ou 0b100000100110000010001110110110111, ou 4374732215.
• A entrada pode ser uma sequência de caracteres ou uma lista de números inteiros ou qualquer outro formato razoável.
• A saída deve ser uma sequência hexadecimal ou apenas um número inteiro ou qualquer outro formato razoável.
• Built-ins que calculam o hash CRC32 não são permitidos.

Objetivo

Aplicam -se regras padrão para o código-golfe .

O código mais curto vence.

Casos de teste

input         output      (hex)
"code-golf"   147743960   08CE64D8
"jelly"       1699969158  65537886
""            0           00000000

Intel x86, 34 30 29 27 bytes

Pega o endereço da sequência terminada em zero no ESI e retorna o CRC no 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

Desmontagem (sintaxe da AT&T):

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

Incorporando sugestões de Peter Cordes para economizar mais quatro bytes. Isso pressupõe uma convenção de chamada em que o sinalizador de direção para instruções de string é limpo na entrada.

Incorporando a sugestão de Peter Ferrie para usar push literal e pop para carregar uma constante, economizando um byte.

Incorporando a sugestão de Peter Ferrie para pular para o segundo byte de uma xorl %eax, %ebxinstrução que é uma retlinstrução, combinada com a alteração da interface da rotina para obter uma string terminada em zero em vez de comprimento, economizando dois bytes no total.

Geléia, 34 bytes

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

Experimente online!

Ruby, 142 bytes

Função anônima; pega uma string como entrada, retorna um número inteiro.

->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}

Gelatina , 23 bytes

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

A entrada está na forma de uma lista de números inteiros. Experimente online! ou verifique todos os casos de teste .

Como funciona

Enquanto o Jelly possui XOR bit a bit, preencher a entrada com zeros e alinhar o polinômio com o dígito binário mais significativo faz com que essa abordagem, que utiliza listas de bits, seja um pouco menor.

ḅ⁹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.

Pitão, 42 bytes

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

Suíte de teste.

CJam, 37 36 bytes

q256b32m<{Yb4374732215Yb.^Yb_Yb32>}g

Teste aqui.

Explicação

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

Pitão, 28 bytes

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

Experimente on-line: Demonstration or Test Suite

Explicação:

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

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)

A falta de um operador XOR de 33 bits, ou mesmo de um operador XOR de 32 bits não assinado, é inútil.

CJam, 33 bytes

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

A entrada está no formato de uma sequência. Experimente online!

Como funciona

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.