Hitung CRC32 Hash

14

Kredit

Tantangan ini berasal dari @miles .


Buat fungsi yang menghitung hash CRC32 dari string input. Input akan berupa string ASCII dengan panjang berapa pun. Output akan menjadi hash CRC32 dari string input itu.

Penjelasan

Algoritma CRC32 dan CRC lainnya pada dasarnya sama, jadi hanya CRC3 yang akan ditunjukkan di sini.

Pertama, Anda memiliki polinomial generator, yang sebenarnya merupakan bilangan bulat [n +1] 4-bit (akan menjadi 33-bit dalam CRC32).

Dalam contoh ini, polinomial generator adalah 1101.

Kemudian, Anda akan memiliki string yang harus di-hash, yang dalam contoh ini akan menjadi 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^

Sisanya diperoleh pada (21), ketika wilayah 1 adalah nol, yang merupakan 001hasil hash CRC3.

Spesifikasi

  • Polinomial generator adalah 0x104C11DB7, atau 0b100000100110000010001110110110111, atau 4374732215.
  • Input dapat berupa string atau daftar bilangan bulat, atau format wajar lainnya.
  • Keluaran menjadi string hex atau hanya integer, atau format wajar lainnya.
  • Built-in yang menghitung hash CRC32 tidak diizinkan.

Tujuan

Aturan standar untuk berlaku.

Kode terpendek menang.

Uji kasus

input         output      (hex)
"code-golf"   147743960   08CE64D8
"jelly"       1699969158  65537886
""            0           00000000
Biarawati Bocor
sumber
Jika saya mengerti benar, ini melakukan pembagian modulo 2 polinomial dan menemukan sisanya, yaitu analog mod dalam perkalian XOR .
xnor
1
Ya. Ini bukan xnor modulo, ini adalah xor modulo.
Leaky Nun
Untuk CRC32, apakah Anda pertama kali menambahkan 31 0?
xnor
Ya - - - - - - - - -
Leaky Nun
1
@ KennyLau Anda dapat melakukan ping ke orang dengan nama mereka, seperti halnya obrolan.
Rɪᴋᴇʀ

Jawaban:

12

Intel x86, 34 30 29 27 byte

Mengambil alamat string yang diakhiri nol di ESI, dan mengembalikan CRC di 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

Memasukkan saran dari Peter Cordes untuk menghemat empat byte lagi. Ini mengasumsikan konvensi pemanggilan di mana bendera arah untuk instruksi string dihapus pada entri.

Menyertakan saran Peter Ferrie untuk menggunakan push literal dan pop untuk memuat konstanta, menghemat satu byte.

Menyertakan saran Peter Ferrie untuk melompat ke byte kedua dari xorl %eax, %ebxinstruksi yang merupakan retlinstruksi, dikombinasikan dengan mengubah antarmuka rutin untuk mengambil string yang diakhiri nol alih-alih panjang, menghemat total dua byte.

Mark Adler
sumber
Gunakan konvensi pemanggilan yang mengharuskan bendera arah harus dibersihkan pada entri, sehingga Anda dapat menyimpan cldinsn (seperti yang saya lakukan dalam jawaban adler32 saya ). Apakah itu praktik normal untuk memungkinkan konvensi pemanggilan yang sepenuhnya sewenang-wenang untuk jawaban asm?
Peter Cordes
Lagi pula, sepertinya kode Anda akan berfungsi sebagai kode mesin x86-64, dan Anda bisa menggunakan konvensi pemanggilan x86-64 SysV x32 untuk menghitung edidan penunjuk esi(mungkin tidak diperpanjang, jadi mungkin memalsukan hal-hal dan memerlukan 64bit zero-extended pointer). (x32 sehingga Anda dapat menggunakan matematika pointer 32-bit dengan aman, tetapi masih memiliki konvensi pemanggilan register-arg. Karena Anda tidak menggunakan inc, tidak ada downside ke mode lama.)
Peter Cordes
Apakah Anda mempertimbangkan untuk tetap edxdalam urutan byte-terbalik? bswap edxhanya 2B. shr %edxadalah 2B, sama dengan shift kiri Anda add %edx,%edx. Ini mungkin tidak membantu; Kecuali itu memungkinkan lebih banyak optimasi, Anda menyimpan 3B untuk shl $24, %eax, tetapi Anda menghabiskan 4B untuk xor %eax,%eaxdi awal dan bswap %edxdi akhir. Zeroing eax memang memungkinkan Anda cdquntuk menggunakan ke nol %edx, jadi secara keseluruhan itu adalah cuci. Itu akan berkinerja lebih baik: ia menghindari kios / perlambatan register parsial pada setiap iterasi dari menulis aldan kemudian membaca eaxdengan shl. : P
Peter Cordes
1
Bingung dengan pertanyaan Adler-32, yang memiliki batas panjang. Pertanyaan ini tidak memiliki batas panjang eksplisit.
Mark Adler
1
Mungkin ada cara untuk mempersingkat ini dengan instruksi PCLMULQDQ. Namun penggunaannya cenderung membutuhkan banyak konstanta, jadi mungkin tidak.
Mark Adler
4

Jelly, 34 byte

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

Cobalah online!

Biarawati Bocor
sumber
4

Ruby, 142 byte

Fungsi anonim; mengambil string sebagai input, mengembalikan 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}
Nilai Tinta
sumber
2
Bisakah Anda mengubah nama Anda sehingga orang dapat membedakan kami? XD
Leaky Nun
2
@ KennyLau Anda harus pilih-pilih ... OK baik
Nilai Tinta
Saya hanya bercanda xd
Leaky Nun
4

Jelly , 23 byte

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

Input berupa daftar bilangan bulat. Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

Sementara Jelly memiliki bitor XOR, mengisi input dengan nol dan menyelaraskan polinomial dengan digit biner yang paling signifikan membuat pendekatan ini, yang menggunakan daftar bit sebagai gantinya, sedikit lebih pendek.

ḅ⁹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.
Dennis
sumber
3

Pyth, 42 byte

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

Suite uji.

Biarawati Bocor
sumber
3

CJam, 37 36 byte

q256b32m<{Yb4374732215Yb.^Yb_Yb32>}g

Uji di sini.

Penjelasan

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
Martin Ender
sumber
q256bYb_,{(4374732215Ybf*1>.^}*Ybmenghemat beberapa byte.
Dennis
@ Dennis Itu benar-benar pintar, merasa bebas untuk membuatnya menjadi jawaban yang terpisah. :)
Martin Ender
3

Pyth, 28 byte

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

Cobalah online: Demonstrasi atau Test Suite

Penjelasan:

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
Jakube
sumber
2

JavaScript (ES6), 180 byte

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)

Kurangnya operator XOR 33-bit, atau bahkan operator XOR 32-bit yang tidak ditandatangani, tidak membantu.

Neil
sumber
1

CJam, 33 byte

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

Input dalam bentuk string. Cobalah online!

Bagaimana itu bekerja

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.
Dennis
sumber