Задний план

Adler-32 - это 32-битная контрольная сумма, изобретенная Марком Адлером в 1995 году, которая является частью широко используемой библиотеки zlib (также разработанной Adler). Adler-32 не так надежен, как 32-битная циклическая проверка избыточности , но - по крайней мере в программном обеспечении - он намного быстрее и проще в реализации.

Определение

Пусть B = [b ₁ , ⋯, b _n ] - байтовый массив.

Контрольная сумма Adler-32 для B определяется как результат low + 65536 × high , где:

• низкий: = ((1 + b ₁ + ⋯ + b _n ) мод 65521)

• высокая: = (((1 + b ₁ ) + (1 + b ₁ + b ₂ ) + ⋯ (1 + b ₁ + ⋯ + b _n )) мод 65521)

задача

Получив байтовый массив в качестве входных данных, вычислите и верните его контрольную сумму Adler-32, соблюдая следующее.

• Вы можете принять входные данные в виде массива байтов или целых чисел или в виде строки.

  В обоих случаях во входных данных будут присутствовать только байты, соответствующие печатным символам ASCII.

  Вы можете предположить, что длина ввода будет удовлетворять 0 <длина ≤ 4096 .

• Если вы решите распечатать вывод, вы можете использовать любую положительную базу вплоть до 256 включительно.

  Если вы выбираете унарный, убедитесь, что интерпретатор может обрабатывать до 2 ³² - 983056 байт на машине с 16 ГБ ОЗУ.

• Встроенные модули, которые вычисляют контрольную сумму Adler-32, запрещены.

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

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

String:     "Eagles are great!"
Byte array: [69, 97, 103, 108, 101, 115, 32, 97, 114, 101, 32, 103, 114, 101, 97, 116, 33]
Checksum:   918816254

String:     "Programming Puzzles & Code Golf"
Byte array: [80, 114, 111, 103, 114, 97, 109, 109, 105, 110, 103, 32, 80, 117, 122, 122, 108, 101, 115, 32, 38, 32, 67, 111, 100, 101, 32, 71, 111, 108, 102]
Checksum:   3133147946

String:     "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
Byte array: [126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126]
Checksum:   68095937

String:     <1040 question marks>
Byte array: <1040 copies of 63>
Checksum:   2181038080

Желе, 19 17 байт

+\,S‘S€%65521ḅ⁹²¤

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

+\,S‘S€%65521ḅ⁹²¤    Main monadic chain. Takes array as only argument.

                     The array is shown here as [b1 b2 ... bn].
+\                   Reduce by addition (+) while returning immediate results.
                         yields [b1 b1+b2 ... b1+b2+...+bn].

  ,                  Concatenate with...
   S                 the sum of the argument.
                         yields [[b1 b1+b2 ... b1+b2+...+bn] b1+b2+...+bn].

    ‘                Increment [each].
                         yields [[1+b1 1+b1+b2 ... 1+b1+b2+...+bn] 1+b1+b2+...+bn].

     S€              Sum each list.
                         yields [[1+b1+1+b1+b2+...+1+b1+b2+...+bn] 1+b1+b2+...+bn].

       %65521        Modulo [each] by 65521.

             ḅ⁹²¤    Convert from base    65536    to integer.
              ⁹                        256
               ²                           squared

Mathematica, 46 байтов

{1,4^8}.Fold[##+{0,#&@@#}&,{1,0},#]~Mod~65521&

Анонимная функция, которая принимает целочисленный массив и возвращает Adler-32 с некоторыми улучшениями от Mils и Martin (см. Комментарии).

миль - это тоже 46 байт , но быстрее:

{1,4^8}.{Tr@#+1,Tr[Accumulate@#+1]}~Mod~65521&

Юлия, 73 46 байтов

x->[sum(x)+1;sum(cumsum(x)+1)]%65521⋅[1;4^8]

Это анонимная функция, которая принимает массив и возвращает целое число. Чтобы вызвать его, назначьте его переменной.

Мы объединяем sum(x) + 1и sum(cumsum(x) + 1)в массив, где xнаходится входной массив, и берем каждое по модулю 65521. Затем мы вычисляем скалярное произведение с 1 и 4 ⁸ , что дает нам (sum(x) + 1) + 4^8 * sum(cumsum(x) + 1), что в точности соответствует формуле Адлера-32.

Попробуйте онлайн! (Включает все тестовые случаи)

Сохранено 27 байтов благодаря Sp3000 и Денису!

Функция машинного кода x86-64: 33 32 байта (или 31 30 байтов с int[]вводом вместо char[])

Функция машинного кода x86-32: 31 байт

Как фрагмент кода in-asm GNU C: сохраняет 2B 1B (только retinsn).

Прокомментированный источник и тестовый драйвер на github

64-битная версия вызывается напрямую из C со стандартным ABI System V x86-64 (используя 2 фиктивных аргумента для получения аргументов в нужных мне регистрах). Пользовательские соглашения о вызовах не редкость для asm-кода, так что это бонусная функция.

32-битный машинный код сохраняет 1B, потому что объединение верхних и нижних половин push16/push16 => pop32работает только в 32-битном режиме. Для 32-битной функции потребуется специальное соглашение о вызовах. Мы не должны возражать против этого, но для вызова из C нужна функция-обертка.

После обработки 4096 ~(ASCII 126) байтов high = 0x3f040000, low = 0x7e001. Итак high, самый важный бит еще не установлен. Мой код использует это, знак удлинителей eaxв edx:eaxс cdqкак способ обнуления edx.

# See the NASM source below
0000000000401120 <golfed_adler32_amd64>:
  401120:       31 c0                   xor    eax,eax
  401122:       99                      cdq    
  401123:       8d 7a 01                lea    edi,[rdx+0x1]
0000000000401126 <golfed_adler32_amd64.byteloop>:
  401126:       ac                      lods   al,BYTE PTR ds:[rsi]
  401127:       01 c7                   add    edi,eax
  401129:       01 fa                   add    edx,edi
  40112b:       e2 f9                   loop   401126 <golfed_adler32_amd64.byteloop>
000000000040112d <golfed_adler32_amd64.end>:
  40112d:       66 b9 f1 ff             mov    cx,0xfff1
  401131:       92                      xchg   edx,eax
  401132:       99                      cdq    
  401133:       f7 f1                   div    ecx
  401135:       52                      push   rdx
  401136:       97                      xchg   edi,eax
  401137:       99                      cdq    
  401138:       f7 f1                   div    ecx
  40113a:       66 52                   push   dx      # this is the diff from last version: evil push/pop instead of shift/add
  40113c:       58                      pop    rax
  40113d:       66 5a                   pop    dx
  40113f:       c3                      ret    
0000000000401140 <golfed_adler32_amd64_end>:

0x40 - 0x20 = 32 байта.

Комментарий источника NASM:

трюки:

• xchg eax, r32один байт; дешевле чем мов. 8086 нужны были данные в ax для гораздо большего количества вещей, чем> = 386, поэтому они решили потратить много места для кода операции на редко используемом в настоящее время xchg ax, r16.

• Смешение push64 и push16 для объединения высоких и низких значений в один регистр сохраняет reg-reg инструкции перемещения данных примерно на две divсекунды. 32-битная версия этого трюка работает еще лучше: push16 / push16 / pop32всего 5B, а не 6.

Так как мы нажимаем / выдвигаем, это не безопасно для встроенного asm в ABD SysV amd64 (с красной зоной) .

golfed_adler32_amd64_v3:   ; (int dummy, const char *buf, int dummy, uint64_t len)

    ;; args: len in rcx,  const char *buf in rsi
    ;; Without dummy args, (unsigned len, const char *buf),  mov ecx, edi is the obvious solution, costing 2 bytes

    xor     eax,eax         ; scratch reg for loading bytes
    cdq                     ; edx: high=0
    lea     edi, [rdx+1]    ; edi: low=1
    ;jrcxz  .end            ; We don't handle len=0.  unlike rep, loop only checks rcx after decrementing
.byteloop:
    lodsb                   ; upper 24b of eax stays zeroed (no partial-register stall on Intel P6/SnB-family CPUs, thanks to the xor-zeroing)
    add     edi, eax        ; low += zero_extend(buf[i])
    add     edx, edi        ; high += low
    loop   .byteloop
.end:
    ;; exit when ecx = 0, eax = last byte of buf
    ;; lodsb at this point would load the terminating 0 byte, conveniently leaving eax=0

    mov     cx, 65521       ; ecx = m = adler32 magic constant.  (upper 16b of ecx is zero from the loop exit condition.  This saves 1B over mov r32,imm32)
    ;sub    cx, (65536 - 65521) ; the immediate is small enough to use the imm8 encoding.  No saving over mov, though, since this needs a mod/rm byte

    xchg    eax, edx        ; eax = high,  edx = buf[last_byte]
    cdq                     ; could be removed if we could arrange things so the loop ended with a load of the 0 byte

    div     ecx             ; div instead of idiv to fault instead of returning wrong answers if high has overflowed to negative.  (-1234 % m is negative)
    push    rdx             ; push high%m and 6B of zero padding

    xchg    eax, edi        ; eax=low
    cdq
    div     ecx             ; edx = low%m

    ;; concatenate the two 16bit halves of the result by putting them in contiguous memory
    push    dx              ; push low%m with no padding
    pop     rax             ; pop  high%m << 16 | low%m   (x86 is little-endian)

    pop     dx              ; add rsp, 2 to restore the stack pointer

    ;; outside of 16bit code, we can't justify returning the result in the dx:ax register pair
    ret
golfed_adler32_amd64_end_v3:

Я также рассмотрел использование rcxв качестве индекса массива вместо двух счетчиков циклов, но adler32 (s)! = Adler32 (reverse (s)). Поэтому мы не могли использовать loop. Подсчет от -len до нуля и использование movzx r32, [rsi+rcx]только использует слишком много байтов.

Если мы хотим рассмотреть возможность увеличения указателя самостоятельно, 32-битный код, вероятно, является подходящим способом. Даже x32 ABI (32-битные указатели) не достаточно, потому что inc esiэто 2B на amd64, но 1B на i386. Кажется, трудно побить xor eax,eax/ lodsb/ loop: всего 4B, чтобы каждый элемент по очереди растягивал ноль в eax. inc esi/ movzx r32, byte [esi]/ loopЭто 5B.

scasэто еще одна опция для увеличения указателя с помощью инструкции 1B в 64-битном режиме. ( rdi/ ediвместо того rsi, чтобы мы взяли указатель arg rdi). Мы не можем использовать результат флага from scasкак условие цикла, потому что мы не хотим сохранять значение eax равным нулю. Различное распределение регистров может сохранить байт после цикла.

int[] вход

Полный uint8_t[]набор функций - это «основной» ответ, потому что это более интересная задача. Распаковка в int[]- это необоснованная вещь, чтобы попросить нашего абонента сделать это на этом языке, но это экономит 2B.

Если мы возьмем наши входные данные как распакованный массив из 32-битных целых чисел, мы можем легко сохранить один байт (использовать lodsdи заменить xor eax,eax / cdqна просто xor edx,edx).

Мы можем сохранить еще один байт, обнулив edx с помощью lodsd/ cdqи реорганизовав цикл так, чтобы он загружал завершающий элемент 0 перед выходом. (Мы по-прежнему предполагаем, что он существует, хотя это массив int, а не строка).

; untested: I didn't modify the test driver to unpack strings for this
golfed_adler32_int_array:
    ; xor   edx,edx
    lodsd                   ; first element. only the low byte non-zero
    cdq                     ; edx: high=0
    lea     edi, [rdx+1]    ; edi: low=1
    ;jrcxz  .end            ; handle len=0?  unlike rep, loop only checks rcx after decrementing
.intloop:
    add     edi, eax        ; low += buf[i]
    add     edx, edi        ; high += low
    lodsd                   ; load buf[i+1] for next iteration
    loop   .intloop
.end:
    ;; exit when ecx = 0, eax = terminating 0

    xchg    eax, edx
    ;cdq               ; edx=0 already, ready for div
    ; same as the char version

Я также сделал непроверенную версию, которая использует scasd(1B версия add edi,4) и add eax, [rdi]вместо lodsd, но это также 30 байтов. Экономия от использования higheax в конце цикла компенсируется большим кодом в другом месте. Преимущество этого метода заключается 0в том, что он не зависит от завершающего элемента на входе, что, возможно, нецелесообразно для распакованного массива, где нам также явно указана длина.

C ++ 11 тестовый драйвер

Смотрите ссылку на github. Этот ответ становился слишком большим, и тестовый драйвер получил больше возможностей с большим кодом.

MATL , 22 байта

tsQwYsQsh16W15-\l8Mh*s

Входными данными могут быть массив чисел или соответствующая строка ASCII.

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

объяснение

t       % Take array or string as input. Duplicate
sQ      % Sum all its values, and add 1
wYsQs   % Swap. Cumulative sum, add 1, sum
h       % Concatenate horizontally
16W     % 2^16: gives 65536
15-     % Subtract 15: gives 65521
\       % Element-wise modulo operation
l       % Push 1
8M      % Push 65536 again
h       % Concatenate horizontally: gives array [1, 65535]
*s      % Element-wise multiplication and sum. Display

На самом деле, 36 байт

;Σu@;╗lR`╜HΣu`MΣk`:65521@%`M1#84ⁿ@q*

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

Объяснение:

;Σu@;╗lR`╜HΣu`MΣk`:65521@%`M1#84ⁿ@q*
;Σu                                   sum(input)+1
   @;╗lR                              push a copy of input to reg0, push range(1, len(input)+1)
        `╜HΣu`M                       map over range: sum(head(reg0,n))+1
               Σk                     sum, combine lower and upper into a list
                 `:65521@%`M          modulo each by 65521
                            1#84ⁿ@q*  dot product with [1,4**8]

Java, 84 байта

long a(int[]i){long a=1,b=0;for(int p:i)b=(b+(a=(a+p)%(p=65521)))%p;return b<<16|a;}

Если Java-решения всегда должны быть полностью компилируемым кодом, пожалуйста, дайте мне знать.

Ungolfed

long a(int[] i) {
    long a = 1, b = 0;
    for (int p : i) b = (b + (a = (a + p) % (p = 65521))) % p;
    return b << 16 | a;
}

Заметка

Вам придется преобразовать входные данные Stringв int[]( int[]на один байт короче byte[]илиchar[] ).

Выход

String:     "Eagles are great!"
Byte Array: [69, 97, 103, 108, 101, 115, 32, 97, 114, 101, 32, 103, 114, 101, 97, 116, 33]
Checksum:   918816254
Expected:   918816254

String:     "Programming Puzzles & Code Golf"
Byte Array: [80, 114, 111, 103, 114, 97, 109, 109, 105, 110, 103, 32, 80, 117, 122, 122, 108, 101, 115, 32, 38, 32, 67, 111, 100, 101, 32, 71, 111, 108, 102]
Checksum:   3133147946
Expected:   3133147946

String:     "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
Byte Array: [126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126]
Checksum:   68095937
Expected:   68095937

String:     "?????????...?"
Byte Array: [63, 63, 63, 63, 63, 63, 63, 63, 63, ...,63]
Checksum:   2181038080
Expected:   2181038080

Пит, 120 кодов

С размером кода 20:

Примечания / Как это работает?

• Поскольку невозможно использовать массив или строку в качестве входных данных, эта программа работает, принимая ряд целых чисел (представляющих символы ASCII) в качестве входных данных. Сначала я думал об использовании символьных входов, но изо всех сил пытался найти хорошее решение для завершения, поэтому теперь оно заканчивается, когда вводится любое число меньше 1. Изначально это были только отрицательные значения для завершения, но мне пришлось изменить инициализацию после написания программы, так что теперь я не могу соответствовать требуемому 2, только a 1(26/45 на изображении трассы). Это не имеет значения, потому что в соответствии с правилами вызова разрешены только печатные символы ascii.

• Долгое время боролся с повторным входом в цикл, хотя в конце концов я нашел довольно элегантное решение. Нет pointerили switchопераций, только интерпретатор работает в стенах, пока он не перейдет обратно в зеленый кодел для чтения ввода (43-> 44 на изображениях трассировки).

• Завершение цикла достигается сначала дублированием ввода, добавлением 1, а затем проверкой, если оно больше 1. Если это так, запускается средство выбора кодов, и выполнение продолжается по нижнему пути. Если это не так, программа смещается влево (ярко-желтые кодовые обозначения, 31/50 на изображениях трасс).

• Поддерживаемый размер входных данных зависит от реализации интерпретатора, хотя было бы возможно поддерживать произвольно большой ввод с правильным интерпретатором (скажем, например, интерпретатор Java, который использует в BigIntegerкачестве внутренних значений)

• Только что увидел, что в настройку входит одно ненужное DUPи CC(7-> 8-> 9 в следовых изображениях). Понятия не имею, как это случилось. Это, по сути, просто тупик, он 16 раз переключает средство выбора кода, что не приводит к изменениям.

Npiet след изображения

Настройка и первый цикл:

Завершение цикла, выход и выход:

Выходы

Простите, если я включу только один вывод, это займет много времени для ввода: ^)

String: "Eagles are great!"

PS B:\Marvin\Desktop\Piet> .\npiet.exe adler32.png
? 69
? 97
? 103
? 108
? 101
? 115
? 32
? 97
? 114
? 101
? 32
? 103
? 114
? 101
? 97
? 116
? 33
? -1
918816254

Npiet след для [65, -1]

trace: step 0  (0,0/r,l nR -> 1,0/r,l dR):
action: push, value 4
trace: stack (1 values): 4

trace: step 1  (1,0/r,l dR -> 2,0/r,l dB):
action: duplicate
trace: stack (2 values): 4 4

trace: step 2  (2,0/r,l dB -> 3,0/r,l nM):
action: multiply
trace: stack (1 values): 16

trace: step 3  (3,0/r,l nM -> 4,0/r,l nC):
action: duplicate
trace: stack (2 values): 16 16

trace: step 4  (4,0/r,l nC -> 5,0/r,l nY):
action: duplicate
trace: stack (3 values): 16 16 16

trace: step 5  (5,0/r,l nY -> 6,0/r,l nM):
action: duplicate
trace: stack (4 values): 16 16 16 16

trace: step 6  (6,0/r,l nM -> 7,0/r,l nC):
action: duplicate
trace: stack (5 values): 16 16 16 16 16

trace: step 7  (7,0/r,l nC -> 8,0/r,l nY):
action: duplicate
trace: stack (6 values): 16 16 16 16 16 16

trace: step 8  (8,0/r,l nY -> 9,0/r,l lB):
action: switch
trace: stack (5 values): 16 16 16 16 16
trace: stack (5 values): 16 16 16 16 16

trace: step 9  (9,0/r,l lB -> 10,0/r,l dM):
action: multiply
trace: stack (4 values): 256 16 16 16

trace: step 10  (10,0/r,l dM -> 11,0/r,l nR):
action: multiply
trace: stack (3 values): 4096 16 16

trace: step 11  (11,0/r,l nR -> 12,0/r,l lY):
action: multiply
trace: stack (2 values): 65536 16

trace: step 12  (12,0/r,l lY -> 13,0/r,l lM):
action: duplicate
trace: stack (3 values): 65536 65536 16

trace: step 13  (13,0/r,l lM -> 14,0/r,l nM):
action: push, value 3
trace: stack (4 values): 3 65536 65536 16

trace: step 14  (14,0/r,l nM -> 15,0/r,l dM):
action: push, value 2
trace: stack (5 values): 2 3 65536 65536 16

trace: step 15  (15,0/r,l dM -> 16,0/r,l lC):
action: roll
trace: stack (3 values): 16 65536 65536

trace: step 16  (16,0/r,l lC -> 17,0/r,l nB):
action: sub
trace: stack (2 values): 65520 65536

trace: step 17  (17,0/r,l nB -> 18,0/r,l dB):
action: push, value 1
trace: stack (3 values): 1 65520 65536

trace: step 18  (18,0/r,l dB -> 19,0/r,l dM):
action: add
trace: stack (2 values): 65521 65536

trace: step 19  (19,0/r,l dM -> 19,1/d,r dC):
action: duplicate
trace: stack (3 values): 65521 65521 65536

trace: step 20  (19,1/d,r dC -> 18,1/l,l lC):
action: push, value 1
trace: stack (4 values): 1 65521 65521 65536

trace: step 21  (18,1/l,l lC -> 17,1/l,l nC):
action: push, value 1
trace: stack (5 values): 1 1 65521 65521 65536

trace: step 22  (17,1/l,l nC -> 16,1/l,l dB):
action: sub
trace: stack (4 values): 0 65521 65521 65536

trace: step 23  (16,1/l,l dB -> 15,1/l,l lB):
action: push, value 1
trace: stack (5 values): 1 0 65521 65521 65536

trace: step 24  (15,1/l,l lB -> 13,2/l,l dG):
action: in(number)
? 65
trace: stack (6 values): 65 1 0 65521 65521 65536

trace: step 25  (13,2/l,l dG -> 12,2/l,l dR):
action: duplicate
trace: stack (7 values): 65 65 1 0 65521 65521 65536

trace: step 26  (12,2/l,l dR -> 11,2/l,l lR):
action: push, value 1
trace: stack (8 values): 1 65 65 1 0 65521 65521 65536

trace: step 27  (11,2/l,l lR -> 10,2/l,l lY):
action: add
trace: stack (7 values): 66 65 1 0 65521 65521 65536

trace: step 28  (10,2/l,l lY -> 9,2/l,l nY):
action: push, value 1
trace: stack (8 values): 1 66 65 1 0 65521 65521 65536

trace: step 29  (9,2/l,l nY -> 8,1/l,r nB):
action: greater
trace: stack (7 values): 1 65 1 0 65521 65521 65536

trace: step 30  (8,1/l,r nB -> 7,1/l,r lY):
action: switch
trace: stack (6 values): 65 1 0 65521 65521 65536
trace: stack (6 values): 65 1 0 65521 65521 65536

trace: step 31  (7,1/l,l lY -> 6,2/l,l nY):
action: push, value 2
trace: stack (7 values): 2 65 1 0 65521 65521 65536

trace: step 32  (6,2/l,l nY -> 5,3/l,l dB):
action: pointer
trace: stack (6 values): 65 1 0 65521 65521 65536

trace: step 33  (5,3/r,l dB -> 7,4/r,l dM):
action: add
trace: stack (5 values): 66 0 65521 65521 65536

trace: step 34  (7,4/r,l dM -> 8,4/r,l dC):
action: duplicate
trace: stack (6 values): 66 66 0 65521 65521 65536

trace: step 35  (8,4/r,l dC -> 9,3/r,l lC):
action: push, value 3
trace: stack (7 values): 3 66 66 0 65521 65521 65536

trace: step 36  (9,3/r,l lC -> 10,3/r,l nC):
action: push, value 2
trace: stack (8 values): 2 3 66 66 0 65521 65521 65536

trace: step 37  (10,3/r,l nC -> 11,3/r,l dY):
action: roll
trace: stack (6 values): 0 66 66 65521 65521 65536

trace: step 38  (11,3/r,l dY -> 12,3/r,l dG):
action: add
trace: stack (5 values): 66 66 65521 65521 65536

trace: step 39  (12,3/r,l dG -> 13,3/r,l lG):
action: push, value 2
trace: stack (6 values): 2 66 66 65521 65521 65536

trace: step 40  (13,3/r,l lG -> 14,3/r,l nG):
action: push, value 1
trace: stack (7 values): 1 2 66 66 65521 65521 65536

trace: step 41  (14,3/r,l nG -> 15,3/r,l dR):
action: roll
trace: stack (5 values): 66 66 65521 65521 65536
trace: white cell(s) crossed - continuing with no command at 17,3...

trace: step 42  (15,3/r,l dR -> 17,3/r,l lB):

trace: step 43  (17,3/r,l lB -> 13,2/l,l dG):
action: in(number)
? -1
trace: stack (6 values): -1 66 66 65521 65521 65536

trace: step 44  (13,2/l,l dG -> 12,2/l,l dR):
action: duplicate
trace: stack (7 values): -1 -1 66 66 65521 65521 65536

trace: step 45  (12,2/l,l dR -> 11,2/l,l lR):
action: push, value 1
trace: stack (8 values): 1 -1 -1 66 66 65521 65521 65536

trace: step 46  (11,2/l,l lR -> 10,2/l,l lY):
action: add
trace: stack (7 values): 0 -1 66 66 65521 65521 65536

trace: step 47  (10,2/l,l lY -> 9,2/l,l nY):
action: push, value 1
trace: stack (8 values): 1 0 -1 66 66 65521 65521 65536

trace: step 48  (9,2/l,l nY -> 8,1/l,r nB):
action: greater
trace: stack (7 values): 0 -1 66 66 65521 65521 65536

trace: step 49  (8,1/l,r nB -> 7,1/l,r lY):
action: switch
trace: stack (6 values): -1 66 66 65521 65521 65536
trace: stack (6 values): -1 66 66 65521 65521 65536

trace: step 50  (7,1/l,r lY -> 6,1/l,r dY):
action: pop
trace: stack (5 values): 66 66 65521 65521 65536

trace: step 51  (6,1/l,r dY -> 4,1/l,r lY):
action: push, value 3
trace: stack (6 values): 3 66 66 65521 65521 65536

trace: step 52  (4,1/l,r lY -> 3,1/l,r nY):
action: push, value 2
trace: stack (7 values): 2 3 66 66 65521 65521 65536

trace: step 53  (3,1/l,r nY -> 2,1/l,r nM):
action: duplicate
trace: stack (8 values): 2 2 3 66 66 65521 65521 65536

trace: step 54  (2,1/l,r nM -> 1,1/l,r dG):
action: pointer
trace: stack (7 values): 2 3 66 66 65521 65521 65536

trace: step 55  (1,1/r,r dG -> 2,2/r,r lR):
action: roll
trace: stack (5 values): 65521 66 66 65521 65536

trace: step 56  (2,2/r,r lR -> 2,3/d,l nR):
action: push, value 1
trace: stack (6 values): 1 65521 66 66 65521 65536

trace: step 57  (2,3/d,l nR -> 2,4/d,l lC):
action: switch
trace: stack (5 values): 65521 66 66 65521 65536
trace: stack (5 values): 65521 66 66 65521 65536

trace: step 58  (2,4/d,r lC -> 2,5/d,r nM):
action: mod
trace: stack (4 values): 66 66 65521 65536

trace: step 59  (2,5/d,r nM -> 4,5/r,r dM):
action: push, value 3
trace: stack (5 values): 3 66 66 65521 65536

trace: step 60  (4,5/r,r dM -> 6,5/r,r lM):
action: push, value 2
trace: stack (6 values): 2 3 66 66 65521 65536

trace: step 61  (6,5/r,r lM -> 7,5/r,r nC):
action: roll
trace: stack (4 values): 65521 66 66 65536

trace: step 62  (7,5/r,r nC -> 8,5/r,r dM):
action: mod
trace: stack (3 values): 66 66 65536

trace: step 63  (8,5/r,r dM -> 11,5/r,r lM):
action: push, value 3
trace: stack (4 values): 3 66 66 65536

trace: step 64  (11,5/r,r lM -> 12,5/r,r nM):
action: push, value 1
trace: stack (5 values): 1 3 66 66 65536

trace: step 65  (12,5/r,r nM -> 13,5/r,r dC):
action: roll
trace: stack (3 values): 66 65536 66

trace: step 66  (13,5/r,r dC -> 14,5/r,r nB):
action: multiply
trace: stack (2 values): 4325376 66

trace: step 67  (14,5/r,r nB -> 15,5/r,r nM):
action: add
trace: stack (1 values): 4325442

trace: step 68  (15,5/r,r nM -> 16,5/r,r dB):
action: out(number)
4325442
trace: stack is empty
trace: white cell(s) crossed - continuing with no command at 19,5...

trace: step 69  (16,5/r,r dB -> 19,5/r,r nM):

C89, 70 байт

h,l,m=65521;A(char*B){h=0;l=1;while(*B)h+=l+=*B++;return h%m<<16|l%m;}

Чтобы проверить (скомпилировать с gcc -std=c89 -lm golf.c):

#include <stdio.h>
int main(int argc, char** argv) {
    printf("%u\n", A("Eagles are great!"));
    printf("%u\n", A("Programming Puzzles & Code Golf"));
    printf("%u\n", A("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"));
    return 0;
}

Лабиринт , 37 36 32 31 байт

}?"{655:}21:}%=}){%{{36*+!
:++)

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

Ввод в виде списка целых чисел. Программа завершается с ошибкой (сообщение об ошибке отправляется в STDERR).

объяснение

Лабиринтный праймер:

• Лабиринт имеет два стека целых чисел произвольной точности, основной и вспомогательный (ily), которые изначально заполнены (неявным) бесконечным количеством нулей.
• Исходный код напоминает лабиринт, где указатель инструкций (IP) следует за коридорами, когда это возможно (даже за углами). Код начинается с первого действительного символа в порядке чтения, то есть в этом случае в верхнем левом углу. Когда IP-адрес достигает какой-либо формы соединения (то есть нескольких соседних ячеек в дополнение к той, из которой он получен), он выбирает направление на основе вершины основного стека. Основные правила: поверните налево при отрицательном значении, продолжайте движение вперед при нулевом, поверните направо при положительном. И когда один из них невозможен из-за наличия стены, тогда IP будет идти в противоположном направлении. IP также оборачивается при попадании в тупик.
• Цифры обрабатываются путем умножения вершины основного стека на 10 и последующего добавления цифры. Чтобы начать новый номер, вы можете нажать ноль с _.

Хотя код начинается с «комнаты» 4x2, на самом деле это два отдельных цикла «два на два», сжатых вместе. Просто IP-адрес придерживается одного цикла за раз из-за значений стека.

Таким образом, код начинается с цикла 2x2 (по часовой стрелке), который считывает ввод при вычислении суммы префикса:

}   Move last prefix sum over to aux.
?   Read an integer from STDIN or push 0 on EOF, which exits the loop.
+   Add current value to prefix sum.
:   Duplicate this prefix sum.

Теперь у нас есть все суммы префиксов в стеке aux , а также копия суммы по всем значениям и 0из EOF на main . При этом мы вводим еще один цикл 2x2 (по часовой стрелке), который суммирует все суммы префиксов для вычисления HIGH.

"   No-op. Does nothing.
{   Pull one prefix sum over from aux. When we're done, this fetches a 0,
    which exits the loop.
)   Increment prefix sum.
+   Add it to HIGH.

Основной стек теперь имеет LOW - 1и HIGHи ноль, за исключением того, что мы еще не взяли модуль. Остальная часть кода полностью линейна:

655      Turn the zero into 655.
:}       Make a copy and shift it over to aux.
21       Turn the copy on main into 65521.
:}       Make a copy and shift it over to aux.
%        Take HIGH mod 65521.
=        Swap HIGH with the other copy of 65521 on aux.
}){      Move 65521 back to aux, increment LOW-1 to LOW, 
         move 65521 back to main.
%        Take LOW mod 65521.
{        Move HIGH back to main.
{        Move the other copy of 655 back to main.
36       Turn it into 65536.
*        Multiply HIGH by that.
+        Add it to LOW.
!        Print it.

IP теперь попадает в тупик и оборачивается. +И *практически отсутствуют-OPS, из нулей в нижней части стека. 36Теперь оказывается в верхней части основного INTO 63, но два {{тянуть два нуля из Окса на вершине. затем% пытается разделить на ноль, что завершает программу.

Обратите внимание, что в Лабиринте используются целые числа произвольной точности, поэтому откладывание по модулю до конца суммы не вызовет проблем с переполнением целых чисел.

Python 2, 60 58 байт

H=h=65521
l=1
for n in input():l+=n;h+=l
print h%H<<16|l%H

Довольно простой подход. Это полная программа, которая принимает список целых чисел через STDIN, например [72, 105, 33].

(Спасибо @xnor за замечательный совет по псевдонимам и инициализации)

J, 30 байт

+/(+65536&*)&(65521|+/)&:>:+/\

Это, вероятно, может быть сжато больше с другим поездом.

использование

Здесь x $ yсоздается список с xкопиями y.

   f =: +/(+65536&*)&(65521|+/)&:>:+/\
   f 69 97 103 108 101 115 32 97 114 101 32 103 114 101 97 116 33
918816254
   f 80 114 111 103 114 97 109 109 105 110 103 32 80 117 122 122 108 101 115 32 38 32 67 111 100 101 32 71 111 108 102
3133147946
   f (32 $ 126)
68095937
   f (1040 $ 63)
2181038080
   f (4096 $ 255)
2170679522

объяснение

+/(+65536&*)&(65521|+/)&:>:+/\
f (           g           ) h     Monad train (f g h) y = (f y) g (h y)
+/                                Sum the input list
                           +/\    Sum each prefix of the input, forms a list
x     f   &   g   &:   h    y     Composed verbs, makes (g (h x)) f (g (h y))
                         >:       Increment the sum and increment each prefix sum
               (m f g) y          Hook, makes m f (g y)
                    +/            Sum the prefix sums
              65521|              Take the sum and prefix total mod 65521
    (f g) y                       Hook again
    65536&*                       Multiply the prefix total by 65536
                                  This is a bonded verb, it will only multiply
                                  using a fixed value now
   +                              Add the sum and scaled prefix total

Октава, 52 50 байт

Сохранено 2 байта благодаря @LuisMendo

@(B)mod([sum(S=cumsum(B)+1),S(end)],65521)*[4^8;1]

Принимает массив целых чисел в качестве входных данных.

low берется из последнего элемента high (до суммирования) вместо точного вычисления суммы, сохраняя общий итог ... 1 байт !

Пробный прогон на идеоне .

CJam, 30 29 байт

q~{1$+}*]:)_W>]1fb65521f%2G#b

Ввод в виде списка целых чисел.

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

объяснение

q~       e# Read and evaluate input.
{        e# Fold this block over the list, computing prefix sums.
  1$+    e#   Copy the last prefix and add the current element.
}*
]        e# Wrap the prefix sums in an array.
:)       e# Increment each. This will sum to HIGH.
_W>      e# Copy the list and truncate to only the last element, i.e.
         e# the sum of the entire input plus 1. This is LOW.
]        e# Wrap both of those lists in an array.
1fb      e# Sum each, by treating it as base 1 digits.
65521f%  e# Take each modulo 65521.
2G#b     e# Treat the list as base 65536 digits, computing 65536*HIGH + LOW.

Perl 6 , 60 байт

{(.sum+1)%65521+65536*((sum(1,*+.shift...->{!$_})-1)%65521)}

Объяснение:

{
  # $_ is the implicit parameter for this lambda because this block doesn't have
  # an explicit parameter, and @_ isn't seen inside of it.
  # ( @_ takes precedence over $_ when it is seen by the compiler )

  # .sum is short for $_.sum
  ( .sum + 1 ) % 65521 + 65536
  *
  (
    (
      sum(

        # generate a sequence:

        1,         # starting with 1
        * + .shift # lambda that adds previous result (*) with $_.shift
        ...        # generate until:
        -> { !$_ } # $_ is empty

        # ^ I used a pointy block with zero parameters
        # so that the block doesn't have an implicit parameter
        # like the surrounding block

        # this is so that $_ refers to the outer $_

      ) - 1        # remove starting value
    ) % 65521
  )
}

Тест:

#! /usr/bin/env perl6
use v6.c;
use Test;

# give the lambda a name
my &Adler32 = {(.sum+1)%65521+65536*((sum(1,*+.shift...->{!$_})-1)%65521)}

my @tests = (
  (  918816254,  'Eagles are great!'),
  ( 3133147946,  'Programming Puzzles & Code Golf'),
  (   68095937,  '~' x 32,     "'~' x 32"),
  ( 2181038080,  63 xx 1040,   "'?' x 1040"),
);

plan +@tests;

for @tests -> ($checksum, $input, $gist? ) {
  my @array := do given $input {
    when Str { .encode.Array }
    default { .Array }
  }

  is Adler32(@array), $checksum, $gist // $input.perl
}

1..4
ok 1 - "Eagles are great!"
ok 2 - "Programming Puzzles \& Code Golf"
ok 3 - '~' x 32
ok 4 - '?' x 1040

Python 3 (79 байт)

По решению Р. Капа.

lambda w,E=65521:(1+sum(w))%E+(sum(1+sum(w[:i+1])for i in range(len(w)))%E<<16)

Я заменил умножение на сдвиг и убрал пару скобок.

Поскольку я не могу оставлять комментарии, я сделал новый ответ.

Схема, 195 байт

(define(a b)(+(let L((b b)(s 1))(if(=(length b)0)s(L(cdr b)(modulo(+ s(car b))65521))))(* 65536(let H((b b)(s 1)(t 0))(if(=(length b)0)t(let((S(+ s(car b))))(H(cdr b)S(modulo(+ t S)65521))))))))

Если бы не все эти скобки ...

Haskell, 54 50 байт

m=(`mod`65521).sum
g x=m(-1:scanl(+)1x)*4^8+m(1:x)

Пример использования: g [69,97,103,108,101,115,32,97,114,101,32,103,114,101,97,116,33]-> 918816254.

scanlвключает в себя начальное значение (-> 1) в списке (-> [1,1+b1,1+b1+b2,..]), поэтому значение sumoff отключено 1, что фиксируется добавлением -1к списку перед суммированием.

Редактировать: Спасибо @xnor за 4 байта.

JavaScript (ES7), 52 50 байт

a=>a.map(b=>h+=l+=b,h=0,l=1)&&l%65521+h%65521*4**8

ES6 занимает 51 байт (замените 4 ** 8 на 65536). Если вы хотите строковую версию, то для 69 байтов:

s=>[...s].map(c=>h+=l+=c.charCodeAt(),h=0,l=1)&&l%65521+h%65521*65536

Редактировать: 2 байта сохранены благодаря @ user81655.

Функция ARM Thumb-2 принимает uint8_t[]: 40 байтов (36B для нестандартного ABI и int[])

Особенности: не отложенный по модулю, поэтому входные данные произвольного размера хороши. На самом деле не использует инструкцию деления, поэтому она не медленная. (по крайней мере, не по этой причине: P)

Экономия от следующих менее строгих правил:

• -2B, если нам не нужно сохранять регистры перед их использованием.
• -2B для требования, чтобы вызывающая сторона распаковывала байты в uint32_t[]массив.

Итак, в лучшем случае это 36В.

// uint8_t *buf in r0,  uint32_t len in r1
00000000 <adler32arm_golf2>:
   0:   b570            push    {r4, r5, r6, lr} //
   2:   2201            movs    r2, #1          // low
   4:   2300            movs    r3, #0          // high
   6:   f64f 75f1       movw    r5, #65521      ; 0xfff1 = m
0000000a <adler32arm_golf2.byteloop>:
   a:   f810 4b01       ldrb.w  r4, [r0], #1    // post-increment byte-load
   e:   4422            add     r2, r4          // low += *B
  10:   4413            add     r3, r2          // high += low
  12:   42aa            cmp     r2, r5          // subtract if needed instead of deferred modulo
  14:   bf28            it      cs
  16:   1b52            subcs   r2, r2, r5
  18:   42ab            cmp     r3, r5
  1a:   bf28            it      cs              // Predication in thumb mode is still possible, but takes a separate instruction
  1c:   1b5b            subcs   r3, r3, r5
  1e:   3901            subs    r1, #1          // while(--len)
  20:   d1f3            bne.n   a <.byteloop2>
  22:   eac2 4003       pkhbt   r0, r2, r3, lsl #16   // other options are the same size: ORR or ADD.
  26:   bd70            pop     {r4, r5, r6, pc}  // ARM can return by popping the return address (from lr) into the pc; nifty
00000028 <adler32arm_end_golf2>:

0x28 = 40 байт

Заметки:

Вместо того, log%mчтобы в конце, мы делаем if(low>=m) low-=mвнутри цикла. Если мы делаем низкие до высоких, мы знаем, что ни один из них не может превзойти 2*m, поэтому по модулю это просто вопрос вычитания или нет. А cmpи предикат subсоставляет всего 6В в режиме Thumb2. Стандартная идиома для% 8B в режиме Thumb2:

UDIV R2, R0, R1         // R2 <- R0 / R1
MLS  R0, R1, R2, R0     // R0 <- R0 - (R1 * R2 )

Версия с неявной длиной adler(char *)имеет тот же размер кода, что и явная длина adler(uint8_t[], uint32_t len). Мы можем установить флаги для условия выхода из цикла с помощью одной инструкции 2B в любом случае.

Версия с неявной длиной имеет преимущество правильной работы с пустой строкой, вместо того, чтобы пытаться выполнить цикл 2 ^ 32 раза.

собрать / собрать с:

arm-linux-gnueabi-as --gen-debug -mimplicit-it=always -mfloat-abi=soft -mthumb adler32-arm.S

или

arm-linux-gnueabi-g++ -Wa,-mimplicit-it=always -g -static -std=gnu++14 -Wall -Wextra -Os -march=armv6t2 -mthumb -mfloat-abi=soft test-adler32.cpp -fverbose-asm adler32-arm.S -o test-adler32
qemu-arm ./test-adler32

Без этого -static, запущенный процесс qemu-armне нашел своего динамического компоновщика. (И да, я установить ARM кросс-Devel настройки только для этого ответа, потому что я думал , что моя основывается-вычитать идея была аккуратной.) На amd64 Ubuntu, установить gcc-arm-linux-gnueabi, g++-arm-linux-gnueabi. Я нашел что- gdb-arm-none-eabiто вроде плохо работающего соединения qemu-arm -g port.

Комментарий источника:

// There's no directive to enable implicit-it=always

// gcc uses compiler uses these in its output
.syntax unified
.arch armv8-a
.fpu softvfp

.thumb      @ aka .code 16

.p2align 4
.globl adler32arm_golf    @ put this label on the one we want to test

.thumb_func
adler32arm_golf:
adler32arm_golf2:   @ (uint8_t buf[], uint32_t len)
        @ r0 = buf
        @ r1 = len
        push    {r4, r5, r6, lr}   @ even number of regs keeps the stack aligned.  Good style? since there's no code-size saving

        movs    r2, #1          @ r2: low
        movs    r3, #0          @ r3: high
                                @ r4 = tmp for loading bytes
        movw    r5, #65521      @ r5: modulo constant

adler32arm_golf2.byteloop2:
        ldrb    r4, [r0], #1    @ *(buf++) post-increment addressing.  4B encoding
        @ldrb    r4, [r0, r1]   @ 2B encoding, but unless we make the caller pass us buf+len and -len, it needs extra code somewhere else
        @ldmia   r0!, {r4}      @ int[] version:  r4 = [r0]; r0+=4;  post-increment addressing.  2B encoding.

        add     r2, r2, r4      @ low += tmp
        add     r3, r3, r2      @ high += low;   // I think it's safe to do this before the modulo range-reduction for low, but it would certainly work to put it after.

        cmp     r2, r5
        subhs   r2, r5          @ if(low>=m) low-=m;   @ 6B total for %.  predicated insns require an IT instruction in thumb2

        cmp     r3, r5
        subhs   r3, r5          @ if(high>=m) high-=m;  // equivalent to high %= m.

        @sub    r1, #1          @ 4B encoding: sub.w to not set flags with immediate
        subs    r1, #1          @ len-- and set flags.  2B encoding
        @cmp    r4, #0          @ null-termination check. 2B encoding
        bne     adler32arm_golf2.byteloop2

@        udiv    r0, r2, r5            @ normal way to do one of the modulos
@        mls     r2, r5, r0, r2         @ r2 = low % m.  8B total for %

        PKHBT   r0, r2, r3, lsl #16     @ 4B   r0 = [ high%m <<16  |   low%m  ]
        @orr     r0, r0, r4, lsl #16    @ 4B
        @orr     r0, r0, r4             @ 4B
        @add     r0, r2, r3, lsl #16    @ 4B
        @add     r0, r0, r4             @ 2B
        pop     {r4, r5, r6, pc}        @ ARM can return by popping the return address (saved from lr) into pc.  Nifty
adler32arm_end_golf2:

test-adler32.cppимеет те же тестовые случаи, что и main()для моего ответа x86-64, но начинается так:

#include <stdint.h>
uint32_t adler32_simple(const uint8_t *B) {
  const uint32_t m=65521;

  uint32_t h=0, l=1;
  do {
    l += *B++;        // Borrowed from orlp's answer, as a simple reference implementation
    h += l;
    l %= m; h %= m;   // with non-deferred modulo if this is uncommented
  } while(*B);

  return h%m<<16|l%m;
}


#include <stdio.h>
//#include <zlib.h>
#include <string.h>
#include <assert.h>
#include <string>   // useful for the memset-style constructors that repeat a character n times


extern "C" {
    unsigned golfed_adler32_amd64(int /*dummy1*/, const char *buf, int /*dummy2*/, unsigned len);
    unsigned adler32arm_golf(const char *buf, unsigned len);
}
#ifdef __amd64__
#define golfed_adler32(buf, len)   golfed_adler32_amd64(1234, buf, 1234, len)
#elif  __arm__
#define golfed_adler32(buf, len)   adler32arm_golf(buf, len)
#else
#error "no architecture"
#endif

static void test_adler(const char *str)
{
    unsigned len = strlen(str);
//    unsigned zlib = zlib_adler(len, str);
    unsigned reference = adler32_simple((const uint8_t*)str);
    unsigned golfed = golfed_adler32(str, len);

    printf("%s: c:%u asm:%u\n", str, reference, golfed);
    assert(reference == golfed);
}

// main() to call test_adler() unchanged from my amd64 answer, except that the comments about length limits don't apply

16-битная функция машинного кода x86: 32 байта с использованием пользовательского соглашения о вызовах

Аргументы в регистрах, и не сохраняющие регистры, кроме bp (и sp).

В 16-битном коде мы возвращаем 32-битное значение в dx:axрегистровой паре. Это означает, что нам не нужно тратить какие-либо инструкции на слияние highи lowв eax. (Это также сэкономит байты в 32- и 64-битном коде, но мы можем оправдать только разгрузку этой работы для вызывающей стороны в 16-битном коде.)

Прокомментированный исходный код и тестовый драйвер на github (для x86 16, 32 и 64bit и ARM).

### const char *buf in SI,  uint16_t len in CX
## returns in dx:ax
## also clobbers bx and di.
00000100 <adler32_x16_v6>:
 100:   31 c0                   xor    ax,ax         # set up for lods
 102:   99                      cwd                  # dx= high=0
 103:   bf 01 00                mov    di,0x1        # di= low=0
 106:   bb f1 ff                mov    bx,0xfff1     # bx= m
00000109 <adler32_x16_v6.byteloop>:
 109:   ac                      lods
 10a:   01 c7                   add    di,ax         # low+=buf[i]. modulo-reduce on carry, or on low>=m
 10c:   72 04                   jc     112 <adler32_x16_v6.carry_low>
 10e:   39 df                   cmp    di,bx
 110:   72 02                   jb     114 <adler32_x16_v6.low_mod_m_done>
00000112 <adler32_x16_v6.carry_low>:
 112:   29 df                   sub    di,bx
00000114 <adler32_x16_v6.low_mod_m_done>:
 114:   01 fa                   add    dx,di         # high+=low
 116:   0f 92 d0                setb   al            # store the carry to set up a 32bit dividend.
 119:   92                      xchg   dx,ax
 11a:   f7 f3                   div    bx            # high (including carry) %= m, in dx.  ax=0 or 1 (so we're set for lods next iteration)                                                         
 11c:   e2 eb                   loop   109 <adler32_x16_v6.byteloop>
 11e:   97                      xchg   di,ax         # 
 11f:   c3                      ret    
00000120 <adler32_x16_v6_end>:

0x120 - 0x100 = 32 байта

Протестировано путем сборки того же кода для 32-битного режима, чтобы я мог вызывать его (с помощью функции-оболочки) из C, скомпилированного с -m32. Для меня 16-битный режим несколько интересен, системные вызовы DOS - нет. Все инструкции имеют явные операнды, кроме loopи lodsb, поэтому при сборке для 32-битного режима используются префиксы размера операнда. Та же инструкция, другая кодировка. Но lodsbв 32-битном режиме буду использовать[esi] , так что эта версия для тестирования работает с 32-битными указателями (потому что мы не делаем никакой математики адреса или увеличения / сравнения указателя).

Нет несоответствий. Мой тестовый жгут печатает сообщение, если есть несоответствие.

$ yasm -felf32 -Worphan-labels -gdwarf2 adler32-x86-16.asm -o adler32-x86-16+32.o &&
   g++ -DTEST_16BIT -m32 -std=gnu++11 -O1 -g -Wall -Wextra -o test-adler32-x16  adler32-x86-16+32.o  test-adler32.cpp -lz &&
   ./test-adler32-x16
Eagles are great! (len=17): zlib:0x36c405fe  c:0x36c405fe golfed:0x36c405fe
Programming Puzzles & Code Golf (len=31): zlib:0xbac00b2a  c:0xbac00b2a golfed:0xbac00b2a
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=32): zlib:0x040f0fc1  c:0x040f0fc1 golfed:0x040f0fc1
?????????????????????????????????????????????????? (len=1040): zlib:0x82000000  c:0x82000000 golfed:0x82000000
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=4096): zlib:0xb169e06a  c:0xb169e06a golfed:0xb169e06a
(0xFF repeating) (len=4096): zlib:0x8161f0e2  c:0x8161f0e2 golfed:0x8161f0e2
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=5837): zlib:0x5d2a398c  c:0x5d2a398c golfed:0x5d2a398c
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=5838): zlib:0x97343a0a  c:0x97343a0a golfed:0x97343a0a
(0xFF repeating) (len=9999): zlib:0xcae9ea2c  c:0xcae9ea2c golfed:0xcae9ea2c
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=65535): zlib:0x33bc06e5  c:0x33bc06e5 golfed:0x33bc06e5

С 16-битными регистрами мы не можем отложить уменьшение по модулю до окончания цикла. Существует интересная разница между 16-битным и другими размерами операндов: m = 65521( 0xFFF1) больше половины 65536. Вычитание mпри переносе сохраняет значение ниже 2 * m, даже если high=0xFFF0 + 0xFFF0. После цикла, сравнение и вычитание будет делать трюк, вместо div.

Я придумал новую технику для сокращения модуля по модулю после добавления, которое может производить перенос . Вместо обнуления верхней половины входного значения для div, используйте setc dlдля создания 32-разрядного дивиденда, содержащего результат неусеченного сложения ( dhуже обнулен). ( divделает 32b / 16b => 16-битное деление.)

setcc(3 байта) был введен с 386. Чтобы выполнить это на 286 или более ранней версии, лучшее, что я придумал, использует недокументированную salcинструкцию (установите AL из кода переноса) . Это однобайтовый код операции sbb al,al, поэтому мы могли бы использовать salc/ neg alперед выполнением xchg ax, dx(что нам все равно нужно). Без salc, есть последовательность 4B: sbb dx,dx/ neg dx. Мы не можем использовать 3B sbb dx,dx/ inc dx, потому что это будет подражать, setncа не setc.

Я попытался использовать 32-битный размер операнда вместо обработки переноса, но не только addинструкции нуждаются в префиксе размера операнда. Инструкции по настройке констант и т. Д. Также нуждаются в префиксах размера операнда, поэтому он не стал самым маленьким.

Pyth, 25 24 23 байта

1 байт благодаря @Jakube .

Еще 1 байт благодаря @Jakube .

i%R65521sMeBhMsM._Q^4 8

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

Перевод моего ответа в желе .

Perl 5, 43 байта

42 байта, плюс 1 -aEвместо-e

Ввод в виде десятичных целых чисел, разделенных пробелом.

map$h+=$.+=$_,@F;say$.%65521+$h%65521*4**8

Кончик моей шляпы Sp3000 , у которого я взял идеи для этого ответа.

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

1. Из-за -a, $. начинается с 1 и @Fявляется входным массивом. $hначинается с 0. $_используется mapкак заполнитель для каждого элемента массива.
2. map$h+=$.+=$_,@Fозначает, что для каждого элемента @Fмы добавляем этот элемент в, $.а затем добавляем $.в $h.
3. Затем мы делаем модульную арифметику $.%65521+$h%65521*4**8(то есть ($. % 65521) + ( ($h % 65521) * (4**8) )и say(выводим) результат).

Фактор 112 109 103 байт

Теперь , это буквальный перевод алгоритма в вопросе ... теперь, когда я действительно сделал это, знаете ли, правильным.

[ [ sum 1 + ] [ [ dup length [1,b] reverse v. ] [ length ] bi + ] bi [ 65521 mod ] bi@ 16 shift bitor ]

Ungolfed:

: adler-32 ( seq -- n )
  [ sum 1 + ] 
  [ 
    [ dup length [1,b] reverse v. ] 
    [ length ] bi + 
  ] bi 
  [ 65521 mod ] bi@ 
  16 shift bitor 
  ;

Ожидается любая последовательность чисел или строки (небольшая разница, хотя технически они не одинаковы).

Я не знаю, как это будет работать для данного ограничения в версии Factor, скомпилированной с 32-битным размером слова, но на моей 6-ГБ 64-битной машине с частотой 2,2 ГГц:

IN: scratchpad 1040 63 <array>

--- Data stack:
{ 63 63 63 63 63 63 63 63 63 63 63 63 63 63 ~1026 more~ }
IN: scratchpad [ adler-32 ] time
Running time: 7.326900000000001e-05 seconds

--- Data stack:
2181038080
IN: scratchpad 10,000 63 <array> 

--- Data stack:
2181038080
{ 63 63 63 63 63 63 63 63 63 63 63 63 63 63 ~9986 more~ }
IN: scratchpad [ adler-32 ] time
Running time: 0.000531669 seconds

Рубин, 91 байт

->s{b=s.bytes;z=i=b.size
b.inject(1,:+)%65521+b.map{|e|e*(1+i-=1)}.inject(z,:+)%65521*4**8}

Clojure, 109 байт

На основе @Mark Адлера решения .

(fn f[s](->> s(reduce #(mapv + %(repeat %2)[0(first %)])[1 0])(map #(rem % 65521))(map *[1 65536])(apply +)))

Ungolfed

(fn f [s]
  (->> s
       (reduce #(mapv + % (repeat %2) [0 (first %)]) [1 0])
       (map #(rem % 65521))
       (map * [1 65536])
       (apply +)))

использование

=> (def f (fn f[s](->> s(reduce #(mapv + %(repeat %2)[0(first %)])[1 0])(map #(rem % 65521))(map *[1 65536])(apply +))))
=> (f [69 97 103 108 101 115 32 97 114 101 32 103 114 101 97 116 33])
918816254
=> (f [80 114 111 103 114 97 109 109 105 110 103 32 80 117 122 122 108 101 115 32 38 32 67 111 100 101 32 71 111 108 102])
3133147946
=> (f (repeat 32 126))
68095937
=> (f (repeat 1040 63))
2181038080
=> (f (repeat 4096 255))
2170679522

Javascript (130 символов в гольфе)

Ungolfed

function a(b)
{
    c=1
    for(i=0;i<b.length;i++)
    {
        c+=b[i]
    }
    d=c%65521
    f=""
    e=0
    k=""
    for(j=0;j<b.length;j++)
    {
        k+= "+"+b[j]
        f+= "(1"+k+")"
        e= ((eval(f)))
        if(j!=b.length-1){f+="+"}
    }
    g=e%65521
    h=d+65536*g
    console.log(h)
}

Golfed

a=b=>{for(c=1,k=f="",y=b.length,i=0;i<y;i++)c+=x=b[i],f+="(1"+(k+="+"+x)+")",i<y-1&&(f+="+");return z=65521,c%z+65536*(eval(f)%z)}

Вставьте в консоль разработчика, а затем передайте ей массив байтов, например:

[69, 97, 103, 108, 101, 115, 32, 97, 114, 101, 32, 103, 114, 101, 97, 116, 33]

И он вернет контрольную сумму на консоль

TMP, 55 байт

3a1.3b0.1;4+a>T8%a>xFFF14+b>a8%b>xFFF11~5<b>164|b>a2$b$

Реализацию в Lua можно найти здесь: http://preview.ccode.gq/projects/TMP.lua

Python 3.5, 82 байта:

( -1 байт благодаря Нейлу ! )

( -1 байт благодаря матмандану ! )

( -4 байта благодаря Денису ! )

lambda w:((1+sum(w))%65521)+4**8*(sum(1+sum(w[:i+1])for i in range(len(w)))%65521)

Анонимная lambdaфункция. Принимает байтовый массив, применяет весь алгоритм к массиву и выводит результат. Успешно работал для всех тестовых случаев. Вы вызываете это, присваивая ему переменную, а затем вызывая эту переменную, как если бы вы вызывали обычную функцию. Если вы используете оболочку, то она должна выводиться без функции печати. Однако, если это не так, то вы должны обернуть вызов функции в print()функцию, чтобы увидеть результат.

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

Деление , 324 байта

          /   M
       R_MZ  |S
      D ]    |S
 /?V?\} {}/  |S /    \
R{/A  Z$[/   |S/     {\
  } J{\      |S      ;_
 \^  /       |S   R'~++Y++~'L
 /    /      |S       }Y;
 \  \        ;^/
 /  /         +\+ R'~++A++~'L
 \  <Z________________/
    ;\X       //
              \Y/
               *

Честное предупреждение, единственная реализация, на которой я тестировал это, это мой собственный порт языка для F #. Это не игра в гольф, в основном потому, что мне было проще провести пару длинных пробежек, пока моя основная константа остыла вдоль дна, поэтому я могу вернуться и настроить ее.

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

• R'~++Y++~'LБлок предохранителей 256 константу и запускает его вниз, установив массовый множитель реактора непосредственно под ним.
• R'~++A++~'AБлок предохранителей еще 256 и запускает его вверх в направлении выше реактора, который делений частицы в двух массовых кратных65536 массе каждого, запуская их влево и вправо (где правая частица немедленно уничтожается терминатором).
• Левая частица попадает в другой реактор и подвергается делению, разделяясь на две частицы одинаковой массы, которые движутся вверх и вниз.
• Восходящая движущаяся энергия двух частиц проходит через манипуляцию с нулевой массой, отражается влево, а затем устанавливает множитель массы термоядерного реактора. Этот реактор будет таким, каким мы умножим блок H.
• Нисходящая движущаяся частица отражается влево и в долгосрочной перспективе сбрасывает массу, достигая массы 65521 (нашего большого прайма).
• Вращательное зеркало ( Z) в конце цикла заставляет частицу дублировать простое число, отправляя его обратно вправо, где оно в конечном итоге устанавливает сохраненную массу реактора деления (^ ). Вот как мы будем применять оператор модуля к блоку H.
• Второй экземпляр отражается обратно, где выполняет аналогичную функцию для реактора деления (< ), который мы будем использовать для L-блока.
• Теперь, когда наши константы установлены, мы занимаемся махинациями в верхнем левом углу, чтобы прочитать наш ввод и сгенерировать два наших списка. Честно говоря, я забыл, как они работают, но для пустой строки мне пришлось замедлить суммирование частиц Н-блока, что объясняет |S«градирню».
• \Y/ соединяет блок L (который входит через левый канал) и блок H (который входит через правый канал), затем ударяет их в терминатор, который устанавливает код выхода для слитой массы.