Codegolf — Вычислить Хэш Crc32

Александр Бревко

Кредиты

Этот вызов возник из @миль.

Создайте функцию, которая вычисляет хэш CRC32 входной строки. Входными данными будет строка ASCII любой длины. Выходными данными будет хэш CRC32 этой входной строки.

Объяснение

Алгоритм CRC32 и других CRC по сути одинаков, поэтому здесь будет продемонстрирован только CRC3.

Во-первых, у вас есть полином-генератор, который на самом деле представляет собой 4-битное целое число [n+1] (в CRC32 оно будет 33-битным).

В этом примере полином генератора равен

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

.

Затем у вас будет строка для хеширования, которая в этом примере будет иметь вид 4374732215 .

0b100000100110000010001110110110111

Остаток, полученный в 0x104C11DB7 , when region 1 is zero, which is 001 , будет результатом хэша CRC3.

Характеристики

Полином генератора (21) , или 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^ , or 00010010111100101011001101 .
Входные данные могут быть строкой, списком целых чисел или любым другим разумным форматом.
Вывод может быть шестнадцатеричной строкой, целым числом или любым другим разумным форматом.
Встроенные модули, вычисляющие хэш CRC32, не допускаются.

Цель

Стандартные правила подачи заявки.

Выигрывает самый короткий код.

Тестовые случаи

1101

#code-golf #code-golf #побитовое #хеширование

Homer001

Intel x86, 34 30 29 27 байт

Принимает адрес строки с нулевым завершением в ESI и возвращает CRC в EBX:

              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.

Дизассемблирование (синтаксис AT&T):

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

Включены предложения Питера Кордеса по экономии еще четырех байтов. Это предполагает соглашение о вызовах, при котором флаг направления для строковых инструкций очищается при входе.

Включено предложение Питера Ферри использовать push-литерал и pop для загрузки константы, экономя один байт.

Включая предложение Питера Ферри перейти ко второму байту 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) instruction which is a 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 инструкции в сочетании с изменением интерфейса процедуры для использования строки с нулевым завершением вместо длины, что в общей сложности экономит два байта.

Geeko

Желе, 34 байта

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

Попробуйте онлайн!

Виктор Елисев

Рубин, 142 байта

Анонимная функция; принимает строку в качестве входных данных и возвращает целое число.

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

||answer||

Желе, 23 байты

q256b32m<{Yb4374732215Yb.^Yb_Yb32>}g

Входные данные имеют форму списка целых чисел. Попробуйте онлайн! или проверить все тестовые случаи.

Как это работает

Хотя в Jelly используется побитовое исключающее ИЛИ, заполнение входных данных нулями и выравнивание полинома по старшей двоичной цифре делает этот подход, в котором вместо этого используются списки битов, немного короче.

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

||answer||

Пиф, 42 байта

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

Тестовый набор.

Pavel1964

CJam, 37 36 байт

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

Проверьте это здесь.

Объяснение

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

||answer||

Пиф, 28 байт

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

Попробуйте онлайн: Демонстрация или Тестовый набор

Объяснение:

retl ||answer||

JavaScript (ES6), 180 байт

xorl %eax, %ebx

Отсутствие 33-битного оператора XOR или даже беззнакового 32-битного оператора XOR бесполезно.

Kowar

CJam, 33 байта

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

Ввод имеет форму строки. Попробуйте онлайн!

Как это работает

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

Похожие темы	Дата
Семантический Серверный Синонимайзер Рерайтер	19.12.2024, 05:12
[Fandroid] Сборник продвинутых курсов по разработке android-приложений (2019)	19.12.2024, 05:12
Codegolf — Использование Генетического Алгоритма Для Воссоздания Строки	19.12.2024, 05:12
Codegolf - Взрывы На Шахматной Доске	19.12.2024, 05:12
Гольф Мой "До Игры В Гольф" C	19.12.2024, 05:12
Codegolf — Решатель Линейных Функций По Двум Точкам (X,Y)	19.12.2024, 05:12
Codegolf - 3-D Антиферромагнетизм	19.12.2024, 05:12
Строка - Словосочетание Английского Языка	19.12.2024, 05:12
Codegolf — Проверка Радиоактивных Битов	19.12.2024, 05:12
Codegolf — Какая Странная Функция	19.12.2024, 05:12

Codegolf — Вычислить Хэш Crc32

Кредиты

Объяснение

Характеристики

Цель

Тестовые случаи

Александр Бревко

Intel x86, 34 30 29 27 байт

Homer001

Желе, 34 байта

Geeko

Рубин, 142 байта

Желе, 23 байты

Как это работает

Пиф, 42 байта

Виктор Елисев

CJam, 37 36 байт

Объяснение

Пиф, 28 байт

Объяснение:

JavaScript (ES6), 180 байт

Pavel1964

CJam, 33 байта

Как это работает

Kowar

I AM

Интересно