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
, lub0b100000100110000010001110110110111
, lub4374732215
. - 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
Odpowiedzi:
Intel x86,
34302927 bajtówPobiera adres łańcucha zakończonego zerem w ESI i zwraca CRC w EBX:
Demontaż (składnia AT&T):
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, %ebx
instrukcji, która jestretl
instrukcją, 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.źródło
cld
insn (tak jak zrobiłem w mojej odpowiedzi adler32 ). Czy normalną praktyką jest dopuszczanie całkowicie arbitralnych konwencji wywoływania dla odpowiedzi asm?edi
i wskaźnikesi
(może nie rozszerzać zera, więc może fałszować i wymagać 64-bitowy wskaźnik z zerowym rozszerzeniem). (x32, abyś mógł bezpiecznie korzystać z 32-bitowej matematyki wskaźnika, ale nadal masz konwencję wywoływania rejestru-argumentów. Ponieważ nie używaszinc
, nie ma negatywnego wpływu na tryb długi).edx
kolejności odwróconej bajtów?bswap edx
to tylko 2B.shr %edx
wynosi 2B, podobnie jak lewy shiftadd %edx,%edx
. To prawdopodobnie nie jest pomocne; O ile nie pozwoli to na większą optymalizację, oszczędzasz 3B nashl $24, %eax
, ale wydajesz 4Bxor %eax,%eax
na początku ibswap %edx
na końcu. Zeroing eax pozwala na użyciecdq
do zera%edx
, więc ogólnie jest to pranie. Jednak działałby lepiej: unika częściowego spowalniania / zwalniania rejestru przy każdej iteracji od pisania,al
a następnie czytania zaeax
pomocą shl. : PGalaretka, 34 bajty
Wypróbuj online!
źródło
Rubin, 142 bajty
Funkcja anonimowa; pobiera ciąg wejściowy, zwraca liczbę całkowitą.
źródło
Galaretka , 23 bajty
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.
źródło
Pyth, 42 bajty
Zestaw testowy.
źródło
CJam,
3736 bajtówSprawdź to tutaj.
Wyjaśnienie
źródło
q256bYb_,{(4374732215Ybf*1>.^}*Yb
oszczędza kilka bajtów.Pyth, 28 bajtów
Wypróbuj online: pakiet demonstracyjny lub testowy
Wyjaśnienie:
źródło
JavaScript (ES6), 180 bajtów
Brak 33-bitowego operatora XOR, a nawet niepodpisanego 32-bitowego operatora XOR, nie jest pomocny.
źródło
CJam, 33 bajty
Dane wejściowe mają postać ciągu. Wypróbuj online!
Jak to działa
źródło