tło

Adler-32 to 32-bitowa suma kontrolna wynaleziona przez Marka Adlera w 1995 r., Która jest częścią szeroko używanej biblioteki zlib (opracowanej również przez Adlera). Adler-32 nie jest tak niezawodny jak 32-bitowa cykliczna kontrola nadmiarowa , ale - przynajmniej w oprogramowaniu - jest znacznie szybsza i łatwiejsza do wdrożenia.

Definicja

Niech B = [b ₁ , ⋯, b _n ] będzie tablicą bajtów.

Suma kontrolna Adler-32 B jest zdefiniowana jako wynik niski + 65536 × wysoki , gdzie:

• niski: = ((1 + b ₁ + ⋯ + b _n ) mod 65521)

• wysoki: = (((1 + b ₁ ) + (1 + b ₁ + b ₂ ) + ⋯ (1 + b ₁ + ⋯ + b _n )) mod 65521)

Zadanie

Biorąc pod uwagę tablicę bajtów jako dane wejściowe, oblicz i zwróć sumę kontrolną Adler-32, przestrzegając poniższych wskazówek.

• Możesz wziąć dane wejściowe jako tablicę bajtów lub liczb całkowitych lub jako ciąg znaków.

  W obu przypadkach na wejściu pojawią się tylko bajty odpowiadające drukowanym znakom ASCII.

  Możesz założyć, że długość danych wejściowych spełni 0 <długość ≤ 4096 .

• Jeśli zdecydujesz się wydrukować wydruk, możesz użyć dowolnej dodatniej podstawy do 256 włącznie.

  Jeśli wybierzesz jednoargumentowy, upewnij się, że interpreter może obsłużyć do 2 ³² - 983056 bajtów danych wyjściowych na maszynie z 16 GiB pamięci RAM.

• Wbudowane obliczenia sumy kontrolnej Adler-32 są zabronione.

• Obowiązują standardowe zasady gry w golfa .

Przypadki testowe

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

Galaretka, 19 17 bajtów

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

Wypróbuj online!

+\,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 bajtów

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

Anonimowa funkcja, która pobiera tablicę liczb całkowitych i zwraca Adler-32, z pewnymi ulepszeniami od mile i Martina (patrz komentarze).

mile ”to także 46 bajtów , ale szybciej:

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

Julia, 73 46 bajtów

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

Jest to anonimowa funkcja, która przyjmuje tablicę i zwraca liczbę całkowitą. Aby go wywołać, przypisz go do zmiennej.

Łączymy sum(x) + 1i tworzymy sum(cumsum(x) + 1)tablicę, w której xznajduje się tablica wejściowa, i pobieramy każdy moduł 65521. Następnie obliczamy iloczyn skalarny z 1 i 4 ⁸ , co daje nam (sum(x) + 1) + 4^8 * sum(cumsum(x) + 1), czyli dokładnie wzór Adlera-32.

Wypróbuj online! (Obejmuje wszystkie przypadki testowe)

Zaoszczędź 27 bajtów dzięki Sp3000 i Dennis!

x86-64 funkcja kodu maszynowego: 33 32 bajty (lub 31 30 bajtów z int[]wejściem zamiast char[])

Funkcja kodu maszynowego x86-32: 31 bajtów

Jako fragment kodu inline-asm GNU C: zapisuje 2B 1B (tylko retinsn).

Skomentowano źródło i sterownik testowy na github

Wersja 64-bitowa jest możliwa do wywołania bezpośrednio z C przy użyciu standardowego Systemu V x86-64 ABI (przy użyciu 2 fałszywych argumentów, aby uzyskać argumenty w żądanych regach). Niestandardowe konwencje wywoływania nie są rzadkie w przypadku kodu asm, więc jest to funkcja dodatkowa.

32-bitowy kod maszynowy oszczędza 1B, ponieważ łączenie górnej i dolnej połowy push16/push16 => pop32działa tylko w trybie 32-bitowym. Funkcja 32-bitowa wymagałaby niestandardowej konwencji wywoływania. Nie powinniśmy się temu przejmować, ale wywołanie z C wymaga funkcji otoki.

Po przetworzeniu 4096 ~(ASCII 126) bajtach high = 0x3f040000, low = 0x7e001. Więc highjest najbardziej znaczący bit nie jest jeszcze ustalone. Mój kod korzysta z tego, zaloguj rozciągające eaxsię edx:eaxz cdqjako sposób zerowania 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 bajty.

Skomentowane źródło NASM:

wydziwianie:

• xchg eax, r32jest jednym bajtem; tańsze niż mov. 8086 potrzebowało danych w toporze, aby uzyskać o wiele więcej rzeczy niż> = 386, więc postanowili wydać dużo przestrzeni operacyjnej na rzadko używane obecnie xchg ax, r16.

• Mieszanie push64 i push16 w celu połączenia wysokiego i niskiego rejestru w jeden rejestr pozwala zaoszczędzić instrukcje przenoszenia danych reg-reg około dwóch sekund div. 32-bitowa wersja tej sztuczki działa jeszcze lepiej: push16 / push16 / pop32jest tylko 5B, a nie 6.

Ponieważ pchamy / popujemy, nie jest to bezpieczne dla wbudowanego asm w SysV amd64 ABI (z czerwoną strefą) .

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:

rcxRozważyłem również użycie jako indeksu tablicowego zamiast posiadania dwóch liczników pętli, ale adler32 (s)! = Adler32 (reverse (s)). Więc nie mogliśmy użyć loop. Liczenie od -len w górę do zera i używanie movzx r32, [rsi+rcx]po prostu powoduje użycie zbyt wielu bajtów.

Jeśli chcemy rozważyć samodzielne zwiększenie wskaźnika, prawdopodobnie najlepszym rozwiązaniem jest kod 32-bitowy. Nawet x32 ABI (wskaźniki 32-bitowe) nie jest wystarczające, ponieważ inc esima 2B na amd64, ale 1B na i386. Wydaje się, że trudno jest pokonać sumę xor eax,eax/ lodsb/ loop: 4B, aby z kolei każdy element rozszerzył zero do eax. inc esi/ movzx r32, byte [esi]/ loopwynosi 5B.

scasto kolejna opcja zwiększania wskaźnika za pomocą instrukcji 1B w trybie 64-bitowym. ( rdi/ edizamiast rsi, więc weźmiemy argument arg rdi). Nie możemy jednak użyć wyniku flagi scasjako warunku pętli, ponieważ nie chcemy utrzymywać wartości zerowej eax. Inny przydział rejestrów może zaoszczędzić bajt po pętli.

int[] wkład

Pełne przejmowanie funkcji uint8_t[]jest „główną” odpowiedzią, ponieważ jest to bardziej interesujące wyzwanie. Rozpakowanie do int[]jest nierozsądną rzeczą, o którą prosi nasz rozmówca w tym języku, ale oszczędza 2B.

Jeśli weźmiemy nasz wkład jako rozpakowaną tablicę 32-bitowych liczb całkowitych, możemy łatwo zapisać jeden bajt (używać lodsdi zamieniać na xor eax,eax / cdqjust xor edx,edx).

Możemy zapisać kolejny bajt, zerując edx za pomocą lodsd/ cdq, i ponownie układając pętlę, aby ładowała końcowy element 0 przed wyjściem. (Nadal zakładamy, że istnieje, mimo że jest to tablica int, a nie ciąg znaków).

; 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

Zrobiłem również wersję niesprawdzoną, która używa scasd(wersja 1B add edi,4) i add eax, [rdi]zamiast lodsd, ale to także 30 bajtów. Oszczędności wynikające z posiadania higheax na końcu pętli są równoważone większym kodem w innym miejscu. Ma tę zaletę, że nie zależy od 0elementu końcowego na wejściu, co może być nieuzasadnione w przypadku rozpakowanej tablicy, w której również podano długość.

Sterownik testowy C ++ 11

Zobacz link do github. Ta odpowiedź stawała się zbyt duża, a sterownik testowy miał więcej funkcji z większym kodem.

MATL , 22 bajty

tsQwYsQsh16W15-\l8Mh*s

Dane wejściowe mogą być tablicą liczb lub odpowiednim ciągiem ASCII.

Wypróbuj online!

Wyjaśnienie

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

Właściwie 36 bajtów

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

Wypróbuj online!

Wyjaśnienie:

;Σ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 bajty

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

Jeśli rozwiązania Java zawsze mają być kompletnym kodem, który można skompilować, daj mi znać.

Bez golfa

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

Uwaga

Będziesz musiał przekonwertować dane wejściowe Stringna int[]( int[]jest o jeden bajt krótszy niż byte[]lub char[]).

Wydajność

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

Piet, 120 kodów

Z kodem wielkości 20:

Notatki / Jak to działa?

• Ponieważ nie jest możliwe użycie tablicy lub łańcucha jako danych wejściowych, program ten działa na podstawie szeregu liczb całkowitych (reprezentujących znaki ascii) jako danych wejściowych. Na początku myślałem o wprowadzaniu znaków, ale starałem się znaleźć dobre rozwiązanie dla zakończenia, więc teraz kończy się, gdy zostanie wprowadzona dowolna liczba mniejsza niż 1. Początkowo były to tylko ujemne wartości dla zakończenia, ale musiałem zmienić inicjalizację po napisaniu programu, więc teraz nie mogę dopasować wymaganego 2, tylko 1(26/45 na obrazie śledzenia). Nie ma to jednak znaczenia, ponieważ zgodnie z regułami wyzwania dozwolone są tylko drukowane znaki ascii.

• Długo walczyłem z ponownym wprowadzeniem pętli, choć w końcu znalazłem dość eleganckie rozwiązanie. Nie pointerlub switchoperacje, tylko interpreter wbiega w ściany, dopóki nie przejdzie z powrotem do zielonego kodu w celu odczytania danych wejściowych (43-> 44 na obrazach śladu).

• Zakończenie pętli uzyskuje się najpierw poprzez powielenie wejścia, dodanie 1, a następnie sprawdzenie, czy jest ono większe niż 1. Jeśli tak, to uruchamiany jest selektor koderów i wykonywanie jest kontynuowane na dolnej ścieżce. Jeśli tak nie jest, program pozostaje w lewo (jasnożółte kody, 31/50 na obrazach śladu).

• Obsługiwany rozmiar wejściowy jest zależny od implementacji interpretera, chociaż możliwe byłoby obsługiwanie dowolnie dużego wejścia za pomocą odpowiedniego interpretera (powiedzmy na przykład, interpreter Java, który używa BigIntegerjako wartości wewnętrznych)

• Właśnie zobaczyłem, że konfiguracja zawiera jeden niepotrzebny DUPi CC(7-> 8-> 9 w obrazach śledzenia). Nie mam pojęcia, jak to się stało. Jest to faktycznie noop, przełącza selektor kodów 16 razy, co nie powoduje żadnych zmian.

Obrazy śledzenia Npiet

Konfiguracja i pierwsza pętla:

Zakończenie pętli, wyjście i wyjście:

Wyjścia

Wybacz, jeśli dołączę tylko jedno wyjście, to zajmuje dużo czasu: ^)

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 trace dla [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 bajtów

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

Aby przetestować (skompilować z 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;
}

Labirynt , 37 36 32 31 bajtów

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

Wypróbuj online!

Wprowadź jako listę liczb całkowitych. Program kończy się z błędem (którego komunikat o błędzie trafia do STDERR).

Wyjaśnienie

Podkład labiryntowy:

• Labirynt ma dwa stosy liczb całkowitych o dowolnej precyzji, główny i pomocniczy (iliary), które są początkowo wypełnione (domyślną) nieskończoną liczbą zer.
• Kod źródłowy przypomina labirynt, w którym wskaźnik instrukcji (IP) podąża za korytarzami, kiedy może (nawet wokół rogów). Kod zaczyna się od pierwszego poprawnego znaku w kolejności czytania, tj. W tym przypadku w lewym górnym rogu. Kiedy IP dojdzie do dowolnej formy połączenia (tj. Kilku sąsiednich komórek oprócz tej, z której pochodzi), wybierze kierunek w oparciu o górę głównego stosu. Podstawowe zasady to: skręć w lewo, gdy wartość jest ujemna, idź naprzód, gdy zero, skręć w prawo, gdy wartość dodatnia. A jeśli jeden z nich nie jest możliwy, ponieważ istnieje ściana, wówczas IP przyjmie przeciwny kierunek. IP zmienia się również po trafieniu w ślepe zaułki.
• Cyfry są przetwarzane przez pomnożenie górnej części głównego stosu przez 10, a następnie dodanie cyfry. Aby rozpocząć nowy numer, możesz nacisnąć zero za pomocą _.

Chociaż kod zaczyna się od „pokoju” 4x2, to tak naprawdę dwie oddzielne pętle dwa na dwa ściśnięte razem. IP po prostu przylega do jednej pętli na raz ze względu na wartości stosu.

Tak więc kod zaczyna się od pętli 2x2 (zgodnie z ruchem wskazówek zegara), która odczytuje dane wejściowe podczas obliczania sum prefiksu:

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

Teraz mamy wszystkie sumy prefiksów na stosie Aux , a także kopię sumy nad wszystkimi wartościami i 0z EOF na main . W ten sposób wprowadzamy kolejną pętlę 2x2 (zgodnie z ruchem wskazówek zegara), która sumuje wszystkie sumy prefiksów do obliczenia 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.

Głównym stos ma teraz LOW - 1i HIGHzero, z wyjątkiem, że nie podjęły jeszcze modulo. Pozostała część kodu jest całkowicie liniowa:

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 uderza teraz w ślepy zaułek i się odwraca. +I *są w zasadzie nic nie rób, ze względu na zerowe na dole stosu. 36Teraz okazuje szczyt głównego INTO 63, ale dwa {{ciągnąć dwa zera z AUX na wierzchu. Następnie %próbuje podzielić przez zero, co kończy program.

Zauważ, że Labirynt używa liczb całkowitych o dowolnej precyzji, więc odłożenie modulo do końca sumy nie spowoduje problemów z przepełnieniem liczb całkowitych.

Python 2, 60 58 bajtów

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

Całkiem proste podejście. Jest to pełny program, który pobiera listę liczb całkowitych przez STDIN, np [72, 105, 33].

(Dzięki @xnor za niesamowitą wskazówkę dotyczącą aliasingu / inicjalizacji)

J, 30 bajtów

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

Prawdopodobnie można by to bardziej skondensować z innym pociągiem.

Stosowanie

Tutaj x $ ytworzy listę z xkopiami 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

Wyjaśnienie

+/(+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

Oktawa, 52 50 bajtów

Zaoszczędź 2 bajty dzięki @LuisMendo

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

Pobiera tablicę liczb całkowitych jako danych wejściowych.

niski jest pobierany z ostatniego elementu wysokiego (przed zsumowaniem) zamiast jawnego obliczania sumy, co pozwala zaoszczędzić ... 1 bajt !

Próbka uruchomiona na ideone .

CJam, 30 29 bajtów

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

Wprowadź jako listę liczb całkowitych.

Sprawdź to tutaj.

Wyjaśnienie

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 bajtów

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

Wyjaśnienie:

{
  # $_ 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
  )
}

Test:

#! /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 bajtów)

Na podstawie rozwiązania R. Kapa.

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

Zastąpiłem mnożenie przesunięciem i usunąłem parę wsporników.

Ponieważ nie mogę dodawać komentarzy, udzieliłem nowej odpowiedzi.

Schemat, 195 bajtów

(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))))))))

Gdyby nie te wszystkie nawiasy ...

Haskell, 54 50 bajtów

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

Przykład użycia: g [69,97,103,108,101,115,32,97,114,101,32,103,114,101,97,116,33]-> 918816254.

scanlzawiera wartość początkową (-> 1) na liście (-> [1,1+b1,1+b1+b2,..]), więc sumjest wyłączony przez 1, co jest ustalane przez dodawanie-1 do listy przed zsumowaniem.

Edycja: Dzięki @xnor za 4 bajty.

JavaScript (ES7), 52 50 bajtów

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

ES6 zajmuje 51 bajtów (zamień 4 ** 8 na 65536). Jeśli chcesz wersję ciąg, to dla 69 bajtów:

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

Edycja: Zapisano 2 bajty dzięki @ user81655.

Akceptacja funkcji ARM Thumb-2 uint8_t[]: 40 bajtów (36B dla niestandardowych ABI iint[])

Cechy: nieodroczony moduł, więc dane wejściowe o dowolnej wielkości są w porządku. W rzeczywistości nie używa instrukcji podziału, więc nie jest wolny. (err, przynajmniej nie z tego powodu: P)

Oszczędności wynikające z mniej rygorystycznych zasad:

• -2B, jeśli nie musimy zapisywać rejestrów przed ich użyciem.
• -2B za wymaganie od dzwoniącego rozpakowania bajtów do uint32_t[]tablicy.

Zatem najlepszym przypadkiem jest 36B.

// 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 bajtów

Uwagi:

Zamiast log%mna końcu robimy if(low>=m) low-=mwewnątrz pętli. Jeśli zrobimy niski przed wysokim, wiemy, że żaden nie może przekroczyć 2*m, więc modulo jest po prostu kwestią odejmowania lub nie. A cmpi przewidywane subjest tylko 6B w trybie Thumb2. Standardowy idiom dla% to 8B w trybie Thumb2:

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

Wersja o długości niejawnej adler(char *)ma ten sam rozmiar kodu co długość jawnaadler(uint8_t[], uint32_t len) . Możemy ustawić flagi dla warunku wyjścia z pętli za pomocą jednej instrukcji 2B w obu kierunkach.

Wersja o niejawnej długości ma tę zaletę, że działa poprawnie z pustym łańcuchem, zamiast próbować zapętlić 2 ^ 32 razy.

złożyć / skompilować za pomocą:

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

lub

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

Bez -statictego proces działający pod qemu-armnie znalazł dynamicznego linkera. (I tak, zainstalować ARM cross-devel konfigurację tylko dla tej odpowiedzi, bo myślałem, że mój pomysł opiera-odejmowania był schludny.) Na amd64 Ubuntu, zainstalować gcc-arm-linux-gnueabi, g++-arm-linux-gnueabi. Znalazłem gdb-arm-none-eabirodzaj ledwie działającego połączenia qemu-arm -g port.

Skomentowane źródło:

// 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.cppma te same przypadki testowe i main()co w przypadku mojej odpowiedzi x86-64, ale zaczyna się w ten sposób:

#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

x86 16-bitowa funkcja kodu maszynowego: 32 bajty przy użyciu niestandardowej konwencji wywoływania

Argumenty w rejestrach i nie zachowujące rejestrów innych niż bp (i sp).

W kodzie 16-bitowym zwracamy wartość 32-bitową w dx:axparze rejestrów. Oznacza to, że nie trzeba wydawać żadnych poleceń scalania highi lowpod eax. (Pozwoliłoby to również zaoszczędzić bajty w kodzie 32-bitowym i 64-bitowym, ale możemy jedynie uzasadnić przeniesienie tej pracy do osoby dzwoniącej w kodzie 16-bitowym).

Skomentowano źródło i sterownik testowy na github (dla x86 16, 32 i 64bit oraz 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 bajty

Przetestowany przez montażem tego samego kodu trybie 32-bitowym, tak że może to wywołać (z funkcji owijki) z C skompilowany -m32. Dla mnie tryb 16-bitowy jest dość interesujący, wywołania systemowe DOS nie są. Wszystkie instrukcje mają jawne argumenty, z wyjątkiem, loopa lodsbwięc, w trybie 32-bitowym używa się prefiksów wielkości argumentu. Ta sama instrukcja, inne kodowanie. Ale lodsbw trybie 32bit będzie korzystać[esi] , więc ta wersja do testowania działa z 32-bitowymi wskaźnikami (ponieważ nie wykonujemy żadnych obliczeń adresu ani przyrostu / porównania wskaźnika).

Brak niezgodności. Moja uprząż testowa drukuje komunikat, jeśli występuje niezgodność.

$ 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

W przypadku rejestrów 16-bitowych nie możemy odraczać redukcji modulo aż do zakończenia pętli. Istnieje interesująca różnica między 16-bitowym a innym rozmiarem operandu: m = 65521( 0xFFF1) to ponad połowa 65536. Odejmowanie mprzeniesienia utrzymuje wartość poniżej 2 * m, nawet jeśli high=0xFFF0 + 0xFFF0. Po pętli podpowiedź i odejmij wykona lewę, zamiast adiv .

Wymyśliłem nowatorską technikę zmniejszania modulo rejestru po dodaniu, które może powodować przeniesienie . Zamiast zerować górną połowę wejścia dla div, użyj, setc dlaby stworzyć 32-bitową dywidendę z nieskróconym wynikiem dodania ( dhjest już wyzerowany). ( divrobi podział 32b / 16b => 16bit.)

setcc(3 bajty) wprowadzono z 386. Aby uruchomić to na 286 lub wcześniejszym, najlepiej, co wymyśliłem, używa nieudokumentowanej salcinstrukcji (ustaw AL z carry) . Jest to jednobajtowy kod operacyjny dla sbb al,al, więc moglibyśmy użyć salc/ neg alprzed zrobieniem xchg ax, dx(czego i tak potrzebujemy). Bez salcjest sekwencja 4B: sbb dx,dx/ neg dx. Nie możemy użyć 3B sbb dx,dx/ inc dx, ponieważ to by emulowało, setnca nie setc.

Próbowałem użyć 32-bitowego rozmiaru operandu zamiast obsługi przenoszenia, ale nie tylko addinstrukcje wymagają prefiksu wielkości operandu. Instrukcje konfigurujące stałe i tak dalej również wymagają prefiksów wielkości operandu, więc nie było to najmniejsze.

Pyth, 25 24 23 bytes

1 byte thanks to @Jakube.

1 more byte thanks to @Jakube.

i%R65521sMeBhMsM._Q^4 8

Try it online!

Translation of my answer in Jelly.

Perl 5, 43 bytes

42 bytes, plus 1 for -aE instead of -e

Input is as decimal integers, space-separated.

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

A tip of my hat to Sp3000, from whom I took ideas for this answer.

How it works:

1. Because of -a, $. starts at 1 and @F is the input array. $h starts at 0. $_ is used by map as a placeholder for each element of an array.
2. map$h+=$.+=$_,@F means that for each element in @F we add that element to $. and then add $. to $h.
3. Then we do the modular arithmetic $.%65521+$h%65521*4**8 (that is, ($. % 65521) + ( ($h % 65521) * (4**8) ) and say (print) the result.

Factor, 112 109 103 bytes

Now, this is a literal translation of the algorithm in the question... now that I actually made it, y'know, correct.

[ [ 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 
  ;

Expects any sequence of numbers or a string (not much difference, though they aren't technically the same).

I don't know how this will perform for the given limit on a version of Factor compiled with 32-bit word-size, but on my 6GB 64-bit 2.2GHz machine:

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

Ruby, 91 bytes

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

Based on @Mark Adler's solution.

(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 +)))

Usage

=> (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 Characters Golfed)

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

Paste into Developers Console and then give it an Array of Bytes EG:

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

And it will return the checksum to the console

TMP, 55 bytes

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

Implementation in Lua can be found here: http://preview.ccode.gq/projects/TMP.lua

Python 3.5, 82 bytes:

(-1 byte thanks to Neil!)

(-1 byte thanks to mathmandan!)

(-4 bytes thanks to Dennis!)

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

An anonymous lambda function. Accepts a byte array, applies the entire algorithm to the array, and outputs the result. Has successfully worked for all the test cases. You call this by assigning a variable to it, and then calling that variable just like you would call a normal function. If you are using the shell, then this should output without a print function. However, if you are not, then you must wrap the function call in the print() function to actually see the output.

Try it online! (Ideone)

Fission, 324 bytes

          /   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/
               *

Fair warning, the only implementation I've tested this on is my own port of the language to F#. It's not golfed, mainly because I found it easier to have a couple of long runs while my prime constant cooled along the bottom, so I may come back and tweak it.

How does it work?

• The R'~++Y++~'L block fuses a 256 constant and launches it downwards, setting the mass multiplier of the reactor directly below it.
• The R'~++A++~'A block fuses another 256 and launches it up towards the reactor above, which fissions the particle into two mass multiples of 65536 mass each, launching them left and right (where the right particle is immediately destroyed by the terminator).
• The left particle hits another reactor and undergoes fission, splitting into two particles of equal mass heading up and down.
• The upward travelling power-of-two particle passes through a net-zero mass manipulation, reflects to the left, then sets the mass multiplier of the fusion reactor. This reactor will be how we multiply the H block.
• The downward travelling particle reflects to the left and sheds mass over the long run, ultimately reaching a mass of 65521 (our large prime).
• The rotational mirror (Z) at the end of the run causes the particle to duplicate the prime, sending one back to the right where it ultimately sets the stored mass of the fission reactor (^). This is how we'll be applying the modulus operator to the H block.
• The second copy is reflected back, where it performs an analogous function for the fission reactor (<) we'll be using for the L block.
• Now that our constants are in place, we engage in shenanigans in the upper left to read our input and generate our two lists. To be honest, I forget how those work, but for the empty string I had to slow down the H block summing particle, which explains the |S "cooling tower".
• \Y/ fuses the L block (which comes in through the left channel) and the H block (which comes in through the right channel), then slams them into a terminator which sets the exit code to the fused mass.