Kredyty

To wyzwanie pochodzi od @miles .

Utwórz funkcję, która oblicza skrót CRC32 ciągu wejściowego. Dane wejściowe będą ciągiem ASCII o dowolnej długości. Wyjściem będzie skrót CRC32 tego ciągu wejściowego.

Wyjaśnienie

Algorytm CRC32 i inne CRC są zasadniczo takie same, więc tylko CRC3 zostanie tutaj pokazany.

Po pierwsze, mamy wielomian generatora, który jest w rzeczywistości 4-bitową liczbą całkowitą [n + 1] (w CRC32 byłby 33-bitowy).

W tym przykładzie wielomian generatora to 1101.

Następnie będziesz miał ciąg do mieszania, co w tym przykładzie byłoby 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^

Reszta uzyskana w (21), gdy region 1 wynosi zero, co oznacza 001, że byłby wynikiem skrótu CRC3.

Okular

• Wielomian generatora to 0x104C11DB7, lub 0b100000100110000010001110110110111, lub 4374732215.
• Dane wejściowe mogą być ciągiem znaków lub listą liczb całkowitych lub dowolnym innym rozsądnym formatem.
• Dane wyjściowe mogą być ciągiem szesnastkowym lub tylko liczbą całkowitą lub innym rozsądnym formatem.
• Wbudowane obliczające wartość skrótu CRC32 są niedozwolone.

Cel

Obowiązują standardowe zasady gry w golfa kodowego .

Najkrótszy kod wygrywa.

Przypadki testowe

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

Intel x86, 34 30 29 27 bajtów

Pobiera adres łańcucha zakończonego zerem w ESI i zwraca CRC w 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

Demontaż (składnia 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

Włączenie sugestii od Petera Cordesa, aby zaoszczędzić jeszcze cztery bajty. To zakłada konwencję wywoływania, w której flaga kierunku dla instrukcji łańcuchowych jest usuwana przy wejściu.

Uwzględnienie sugestii Petera Ferrie, aby użyć literału push i pop, aby załadować stałą, oszczędzając jeden bajt.

Uwzględnienie sugestii Petera Ferrie, aby przejść do drugiego bajtu xorl %eax, %ebxinstrukcji, która jest retlinstrukcją, w połączeniu ze zmianą interfejsu procedury, tak aby przyjmowała ciąg zakończony zerami zamiast długości, co pozwoliło zaoszczędzić w sumie dwa bajty.

Galaretka, 34 bajty

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

Wypróbuj online!

Rubin, 142 bajty

Funkcja anonimowa; pobiera ciąg wejściowy, zwraca liczbę całkowitą.

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

Galaretka , 23 bajty

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

Dane wejściowe mają postać listy liczb całkowitych. Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

Podczas gdy Jelly ma bitowy XOR, wypełnienie wejścia zerami i wyrównanie wielomianu do najbardziej znaczącej cyfry binarnej sprawia, że ​​to podejście, które zamiast tego używa list bitów, jest nieco krótsze.

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

Pyth, 42 bajty

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

Zestaw testowy.

CJam, 37 36 bajtów

q256b32m<{Yb4374732215Yb.^Yb_Yb32>}g

Sprawdź to tutaj.

Wyjaśnienie

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

Pyth, 28 bajtów

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

Wypróbuj online: pakiet demonstracyjny lub testowy

Wyjaśnienie:

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 bajtów

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)

Brak 33-bitowego operatora XOR, a nawet niepodpisanego 32-bitowego operatora XOR, nie jest pomocny.

CJam, 33 bajty

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

Dane wejściowe mają postać ciągu. Wypróbuj online!

Jak to działa

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.