Вычислить хэш CRC32

14

кредиты

Эта проблема возникла из @miles .

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

объяснение

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

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

В этом примере генератор полинома есть 1101.

Затем у вас будет строка для хеширования, которая в этом примере будет 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^

Остаток, полученный в момент (21), когда область 1 равна нулю, то есть 001будет результатом хэша CRC3.

Спекуляции

  • Генераторный полином есть 0x104C11DB7, или 0b100000100110000010001110110110111, или 4374732215.
  • Входные данные могут быть строкой или списком целых чисел или любым другим приемлемым форматом.
  • Выход будет шестнадцатеричная строка или просто целое число, или любой другой разумный формат.
  • Встроенные модули, которые вычисляют хэш CRC32, не допускаются.

Цель

Стандартные правила для кода-гольфа применяются.

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

Контрольные примеры

input         output      (hex)
"code-golf"   147743960   08CE64D8
"jelly"       1699969158  65537886
""            0           00000000
code-golf bitwise hashing Дрянная Монахиня
источник
Если я правильно понимаю, это делает деление по полиному по модулю 2 и находит остаток, то есть аналог mod в умножении XOR .
xnor
1
Ага. Это не xnor по модулю, это xor по модулю.
Утренняя монахиня
Для CRC32 вы сначала добавляете 31 0?
xnor
Да - - - - - - - - -
Утренняя монахиня
1
@KennyLau вы можете пинговать людей с их именем, как в чате.
января

Ответы:

12

Intel x86, 34 30 29 27 байт

Берет адрес строки с нулевым символом в ESI и возвращает CRC в 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

Разборка (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

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

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

Включение предложения Питера Ферри , чтобы перейти ко второму байту в xorl %eax, %ebxинструкции , которая является retlинструкцией, в сочетании с изменением интерфейса подпрограммы взять завершаются нулем строки вместо длины, сохраняя два байта в общей сложности.

Марк Адлер
источник
Используйте соглашение о вызовах, которое требует очистки флага направления при входе, чтобы вы могли сохранить cldinsn (как я сделал в моем ответе adler32 ). Является ли нормальная практика разрешать совершенно произвольные соглашения о вызовах для ответов asm?
Питер Кордес
В любом случае, похоже, что ваш код будет работать как машинный код x86-64, и вы могли бы использовать соглашение о вызовах SysV x32 для x86-64, чтобы принять подсчет ediи указатель esi(возможно, не с расширением нуля, так что, возможно, вычеркните вещи и потребуйте 64-битный нулевой расширенный указатель). (x32, так что вы можете безопасно использовать 32-битную указательную математику, но при этом иметь соглашение о вызовах register-args. Поскольку вы не используете inc, нет недостатка в длинном режиме.)
Peter Cordes
Рассматривали ли вы держать edxв порядке в обратном порядке? bswap edxтолько 2B. shr %edx2B, так же, как ваш левый сдвиг с add %edx,%edx. Это, вероятно, не полезно; Если это не обеспечивает более оптимизацию, вы сохраняете 3B для shl $24, %eax, но вы тратите 4B для xor %eax,%eaxначала и bswap %edxв конце. Обнуление eax позволяет использовать cdqноль %edx, так что в целом это мытье. Тем не менее, он будет работать лучше: он предотвращает частичное или медленное торможение при каждой итерации при записи alи последующем чтении eaxс помощью shl. : P
Питер Кордес
1
Запутался с вопросом Адлера-32, который имеет ограничение по длине. Этот вопрос не имеет явного ограничения длины.
Марк Адлер
1
Может быть способ сделать это короче с помощью инструкции PCLMULQDQ. Однако для его использования обычно требуется много констант, поэтому, возможно, нет.
Марк Адлер
4

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

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

->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}
Значение чернил
источник
2
Можете ли вы изменить свое имя, чтобы люди могли отличить нас? XD
Утренняя монахиня
2
@KennyLau ты должен быть таким разборчивым ... Ладно, хорошо
Value Ink
Я просто шучу XD
дырявой монахине
4

Желе , 23 байта

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

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

Как это устроено

В то время как у Jelly есть битовое XOR, заполнение ввода нулями и выравнивание полинома с наиболее значимой двоичной цифрой делает этот подход, который использует списки битов, немного короче.

ḅ⁹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.
Деннис
источник
3

CJam, 37 36 байт

q256b32m<{Yb4374732215Yb.^Yb_Yb32>}g

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

объяснение

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
Мартин Эндер
источник
q256bYb_,{(4374732215Ybf*1>.^}*Ybсохраняет несколько байтов.
Деннис
@Dennis Это действительно умно, не стесняйтесь сделать это отдельным ответом. :)
Мартин Эндер
3

Pyth, 28 байт

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

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

Объяснение:

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
источник
2

JavaScript (ES6), 180 байт

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)

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

Нил
источник
1

CJam, 33 байта

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

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

Как это устроено

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.
Деннис
источник