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 001
hasil hash CRC3.
Spesifikasi
- Polinomial generator adalah
0x104C11DB7
, atau0b100000100110000010001110110110111
, atau4374732215
. - 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 golf kode berlaku.
Kode terpendek menang.
Uji kasus
input output (hex)
"code-golf" 147743960 08CE64D8
"jelly" 1699969158 65537886
"" 0 00000000
Jawaban:
Intel x86,
34302927 byteMengambil alamat string yang diakhiri nol di ESI, dan mengembalikan CRC di EBX:
Disassembly (AT&T syntax):
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, %ebx
instruksi yang merupakanretl
instruksi, dikombinasikan dengan mengubah antarmuka rutin untuk mengambil string yang diakhiri nol alih-alih panjang, menghemat total dua byte.sumber
cld
insn (seperti yang saya lakukan dalam jawaban adler32 saya ). Apakah itu praktik normal untuk memungkinkan konvensi pemanggilan yang sepenuhnya sewenang-wenang untuk jawaban asm?edi
dan penunjukesi
(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 menggunakaninc
, tidak ada downside ke mode lama.)edx
dalam urutan byte-terbalik?bswap edx
hanya 2B.shr %edx
adalah 2B, sama dengan shift kiri Andaadd %edx,%edx
. Ini mungkin tidak membantu; Kecuali itu memungkinkan lebih banyak optimasi, Anda menyimpan 3B untukshl $24, %eax
, tetapi Anda menghabiskan 4B untukxor %eax,%eax
di awal danbswap %edx
di akhir. Zeroing eax memang memungkinkan Andacdq
untuk 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 menulisal
dan kemudian membacaeax
dengan shl. : PJelly, 34 byte
Cobalah online!
sumber
Ruby, 142 byte
Fungsi anonim; mengambil string sebagai input, mengembalikan integer.
sumber
Jelly , 23 byte
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.
sumber
Pyth, 42 byte
Suite uji.
sumber
CJam,
3736 byteUji di sini.
Penjelasan
sumber
q256bYb_,{(4374732215Ybf*1>.^}*Yb
menghemat beberapa byte.Pyth, 28 byte
Cobalah online: Demonstrasi atau Test Suite
Penjelasan:
sumber
JavaScript (ES6), 180 byte
Kurangnya operator XOR 33-bit, atau bahkan operator XOR 32-bit yang tidak ditandatangani, tidak membantu.
sumber
CJam, 33 byte
Input dalam bentuk string. Cobalah online!
Bagaimana itu bekerja
sumber