Hintergrund

Adler-32 ist eine von Mark Adler 1995 erfundene 32-Bit-Prüfsumme, die Teil der weit verbreiteten zlib-Bibliothek (ebenfalls von Adler entwickelt) ist. Adler-32 ist nicht so zuverlässig wie eine zyklische 32-Bit- Redundanzprüfung , aber - zumindest in der Software - viel schneller und einfacher zu implementieren.

Definition

Sei B = [b ₁ , ⋯, b _n ] ein Bytearray.

Die Adler-32-Prüfsumme von B ist definiert als das Ergebnis von low + 65536 × high , wobei:

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

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

Aufgabe

Berechnen Sie mit einem Byte-Array als Eingabe die Adler-32-Prüfsumme und geben Sie sie zurück. Beachten Sie dabei Folgendes.

• Sie können die Eingabe als Array von Bytes oder Ganzzahlen oder als Zeichenfolge verwenden.

  In beiden Fällen werden in der Eingabe nur Bytes verwendet, die druckbaren ASCII-Zeichen entsprechen.

  Sie können davon ausgehen, dass die Länge der Eingabe 0 <Länge ≤ 4096 entspricht .

• Wenn Sie die Ausgabe drucken möchten, können Sie eine beliebige positive Basis bis einschließlich 256 verwenden.

  Wenn Sie Unary wählen, stellen Sie sicher, dass der Interpreter bis zu 2 ³² - 983056 Byte Ausgabe auf einem Computer mit 16 GiB RAM verarbeiten kann.

• Built-Ins, die die Adler-32-Prüfsumme berechnen, sind verboten.

• Es gelten die Standardregeln für Code-Golf .

Testfälle

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

Jelly, 19 17 Bytes

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

Probieren Sie es 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 Bytes

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

Eine anonyme Funktion, die ein Integer-Array verwendet und den Adler-32 zurückgibt, mit einigen Verbesserungen gegenüber Miles und Martin (siehe Kommentare).

Meilen 'ist auch 46 Bytes , aber schneller:

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

Julia, 73 46 Bytes

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

Dies ist eine anonyme Funktion, die ein Array akzeptiert und eine Ganzzahl zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu.

Wir kombinieren sum(x) + 1und sum(cumsum(x) + 1)in ein Array, wo xsich das Eingabearray befindet, und nehmen jedes Modulo 65521. Wir berechnen dann das Skalarprodukt mit 1 und 4 ⁸ , was uns ergibt (sum(x) + 1) + 4^8 * sum(cumsum(x) + 1), was genau die Adler-32-Formel ist.

Probieren Sie es online! (Beinhaltet alle Testfälle)

27 Bytes gespart dank Sp3000 und Dennis!

x86-64-Maschinencodefunktion: 33 32 Byte (oder 31 30 Byte mit einer int[]Eingabe anstelle von char[])

x86-32-Maschinencodefunktion: 31 Byte

Als GNU C-Inline-Asm-Codefragment: Speichert 2B 1B (nur das retInsn).

Kommentierte Quelle und Testfahrer auf Github

Die 64-Bit-Version kann mit dem Standardsystem V x86-64 ABI direkt von C aus aufgerufen werden (mit 2 Dummy-Args können Args in den gewünschten Regs abgerufen werden). Benutzerdefinierte Aufrufkonventionen sind für asm-Code keine Seltenheit, daher ist dies eine Bonusfunktion.

32-Bit-Maschinencode spart 1B, da die hohen und niedrigen Hälften mit zusammengeführt werden push16/push16 => pop32 nur im 32-Bit-Modus funktioniert. Für eine 32-Bit-Funktion wäre eine benutzerdefinierte Aufrufkonvention erforderlich. Wir sollten das nicht ablehnen, aber das Aufrufen von C erfordert eine Wrapper-Funktion.

Nach der Verarbeitung von 4096 ~(ASCII 126) Bytes high = 0x3f040000, low = 0x7e001. Das highhöchstwertige Bit ist also noch nicht gesetzt. Mein Code Vorteil hiervon nimmt, meldet verlauf eaxin edx:eaxmit cdqals eine Möglichkeit der Nullstellung 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 Bytes.

Kommentierte NASM-Quelle:

Tricks:

• xchg eax, r32ist ein Byte; billiger als mov. 8086 brauchte Daten in ax für viel mehr Dinge als> = 386, also beschlossen sie, viel Opcode-Platz für die jetzt selten genutzten zu verwenden xchg ax, r16.

• Durch das Mischen von push64 und push16 zum Zusammenführen von high und low in einem einzigen Register werden Anweisungen zum Verschieben von reg-reg-Daten um zwei Sekunden gespart div. Die 32-Bit-Version dieses Tricks funktioniert sogar noch besser: push16 / push16 / pop32Insgesamt sind es nur 5B, nicht 6.

Da wir Push / Pop verwenden, ist dies im SysV amd64 ABI (mit einer roten Zone) für Inline-Asm nicht sicher .

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:

Ich habe auch erwogen, rcxals Array-Index zu verwenden, anstatt zwei Schleifenzähler zu haben, aber adler32 (s)! = Adler32 (reverse (s)). Also konnten wir nicht verwenden loop. Zählen von -len bis zu null und Verwenden von movzx r32, [rsi+rcx]nur viel zu vielen Bytes.

Wenn wir in Betracht ziehen wollen, den Zeiger selbst zu erhöhen, ist wahrscheinlich 32-Bit-Code der richtige Weg. Sogar der x32 ABI (32-Bit-Zeiger) reicht nicht aus, da er inc esibei amd64 2B, bei i386 1B beträgt. Es ist schwer scheint zu schlagen xor eax,eax/ lodsb/ loop: 4B insgesamt jedes Element zu erhalten wiederum in EAX Null erweitert. inc esi/ movzx r32, byte [esi]/ loopIst 5B.

scasist eine weitere Option zum Inkrementieren eines Zeigers mit einem 1B-Befehl im 64-Bit-Modus. ( rdi/ edistatt rsi, also nehmen wir den Zeiger arg in rdi). Wir können das Flag-Ergebnis von jedoch nicht scasals Schleifenbedingung verwenden, da wir eax nicht auf Null setzen möchten. Eine andere Registerzuordnung könnte möglicherweise ein Byte nach der Schleife speichern.

int[] Eingang

Die vollständige Funktionsübernahme uint8_t[]ist die "Hauptantwort", weil es eine interessantere Herausforderung ist. Auspacken nachint[] ist eine unvernünftige Sache, um unseren Anrufer zu bitten, dies in dieser Sprache zu tun, aber es spart 2B.

Wenn wir unsere Eingabe als entpacktes Array von 32-Bit-Ganzzahlen betrachten, können wir problemlos ein Byte speichern (verwenden lodsdund durch xor eax,eax / cdqnur ersetzen)xor edx,edx ).

Wir können ein weiteres Byte speichern, indem wir edx mit lodsd/ auf Null setzen cdqund die Schleife so neu anordnen, dass das abschließende 0-Element vor dem Verlassen geladen wird . (Wir gehen immer noch davon aus, dass es existiert, obwohl dies ein Array von int, nicht eine Zeichenfolge ist).

; 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

Ich habe auch eine ungetestete Version erstellt, die scasd(1B-Version von add edi,4) und add eax, [rdi]anstelle von verwendet lodsd, aber es sind auch 30 Bytes. Die Einsparungen durch higheax am Ende der Schleife werden durch größeren Code an anderer Stelle ausgeglichen. Es hat den Vorteil, dass es nicht auf ein Abschlusselement 0in der Eingabe ankommt, was für ein entpacktes Array, bei dem wir auch die Länge explizit angeben, möglicherweise nicht zumutbar ist.

C ++ 11 Testtreiber

Siehe den Github-Link. Diese Antwort wurde zu groß und der Testfahrer erhielt mehr Funktionen mit größerem Code.

MATL , 22 Bytes

tsQwYsQsh16W15-\l8Mh*s

Die Eingabe kann ein Array von Zahlen oder die entsprechende ASCII-Zeichenfolge sein.

Probieren Sie es online!

Erläuterung

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

Eigentlich 36 Bytes

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

Probieren Sie es online!

Erläuterung:

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

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

Wenn Java-Lösungen immer vollständig kompilierbarer Code sein sollen, lassen Sie es mich bitte wissen.

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

Hinweis

Sie werden den Eingang konvertieren , Stringum int[]( int[]ein Byte kürzer als byte[]oder char[]).

Ausgabe

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 Codels

Mit Codegröße 20:

Notizen / Wie funktioniert es?

• Da es nicht möglich ist, ein Array oder eine Zeichenfolge als Eingabe zu verwenden, verwendet dieses Programm eine Reihe von Ganzzahlen (die ASCII-Zeichen darstellen) als Eingabe. Anfangs dachte ich über die Verwendung von Zeicheneingaben nach, hatte jedoch Mühe, eine gute Lösung für die Terminierung zu finden. Daher wird die Eingabe jetzt abgebrochen, wenn eine Zahl kleiner als 1 eingegeben wird. Es waren ursprünglich nur negative Werte für die Beendigung, aber ich musste die Initialisierung nach dem Schreiben des Programms ändern, so dass ich jetzt nicht die erforderlichen 2, nur eine 1(26/45 auf dem Trace-Image) anpassen kann. Dies spielt jedoch keine Rolle, da gemäß den Herausforderungsregeln nur druckbare ASCII-Zeichen zulässig sind.

• Ich hatte lange Mühe, in die Schleife zurückzukehren, obwohl ich am Ende die elegante Lösung gefunden habe. Nein pointeroder switchOperationen, nur der Interpreter rennt gegen Wände, bis er wieder in den grünen Codel übergeht, um die Eingabe zu lesen (43-> 44 auf den Trace-Bildern).

• Die Beendigung der Schleife wird erreicht, indem zuerst die Eingabe dupliziert, 1 hinzugefügt und dann überprüft wird, ob sie größer als 1 ist. Ist dies der Fall, wird die Codelauswahl ausgelöst und die Ausführung auf dem unteren Pfad fortgesetzt. Ist dies nicht der Fall, bleibt das Programm links (hellgelbe Codierungen, 31/50 auf den Trace-Bildern).

• Die unterstützte Eingabegröße hängt von der Implementierung des Interpreters ab, obwohl es möglich wäre, eine beliebig große Eingabe mit dem richtigen Interpreter zu unterstützen (z. B. einen Java-Interpreter, der BigIntegerals interne Werte verwendet).

• Ich habe gerade gesehen, dass das Setup eine unnötige DUPund CC(7-> 8-> 9 in den Trace-Bildern) enthält. Keine Ahnung wie das passiert ist. Dies ist jedoch effektiv ein Noop. Es schaltet die Codelauswahl 16-mal um, was zu keiner Änderung führt.

Npiet Spurenbilder

Setup und erste Schleife:

Schleife beenden, ausgeben und beenden:

Ausgänge

Verzeih mir, wenn ich nur eine Ausgabe einbinde, dauert die Eingabe nur sehr lange: ^)

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 Spur für [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 Bytes

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

So testen Sie (kompilieren mit 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;
}

Labyrinth , 37 36 32 31 Bytes

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

Probieren Sie es online!

Eingabe als Liste von Ganzzahlen. Das Programm bricht mit einem Fehler ab (dessen Fehlermeldung an STDERR geht).

Erläuterung

Labyrinth-Grundierung:

• Labyrinth hat zwei Stapel von Ganzzahlen mit willkürlicher Genauigkeit, main und aux (iliary), die anfänglich mit einer (impliziten) unendlichen Menge von Nullen gefüllt sind.
• Der Quellcode ähnelt einem Labyrinth, in dem der Anweisungszeiger (IP) nach Möglichkeit Korridoren folgt (sogar um Ecken). Der Code beginnt beim ersten gültigen Zeichen in der Lesereihenfolge, in diesem Fall also in der linken oberen Ecke. Wenn die IP zu einer beliebigen Art von Junction gelangt (dh zu mehreren benachbarten Zellen zusätzlich zu derjenigen, von der sie stammt), wählt sie eine Richtung basierend auf der Oberseite des Hauptstapels aus. Die Grundregeln sind: links abbiegen, wenn negativ, weiterfahren, wenn null, rechts abbiegen, wenn positiv. Und wenn eine davon nicht möglich ist, weil es eine Mauer gibt, dann geht die IP in die entgegengesetzte Richtung. Die IP dreht sich auch um, wenn Sackgassen getroffen werden.
• Ziffern werden verarbeitet, indem die Oberseite des Hauptstapels mit 10 multipliziert und dann die Ziffer hinzugefügt wird. Um eine neue Nummer zu beginnen, können Sie mit eine Null drücken _.

Obwohl der Code mit einem 4x2 "Raum" beginnt, sind das eigentlich zwei getrennte, zwei mal zwei zusammengedrückte Schleifen. Die IP bleibt aufgrund der Stack-Werte immer nur an einer Schleife hängen.

Der Code beginnt also mit einer 2x2-Schleife (im Uhrzeigersinn), die Eingaben während der Berechnung der Präfixsummen liest:

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

Jetzt haben wir alle Präfixsummen auf dem Aux- Stack sowie eine Kopie der Summe über alle Werte und die 0von EOF auf main . Damit betreten wir eine weitere 2x2-Schleife (im Uhrzeigersinn), die alle zu berechnenden Präfixsummen summiert 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.

Der Hauptstapel hat jetzt LOW - 1und HIGHund Null, außer dass wir das Modulo noch nicht genommen haben. Der Rest des Codes ist vollständig linear:

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.

Die IP stößt jetzt auf eine Sackgasse und dreht sich um. Die +und *sind aufgrund der Nullen am Boden des Stapels im Wesentlichen No-Ops. Das 36verwandelt nun die Oberseite von main in 63, aber die beiden {{ziehen zwei Nullen von aux darüber. Dann wird %versucht, durch Null zu dividieren, wodurch das Programm beendet wird.

Beachten Sie, dass Labyrinth Ganzzahlen mit willkürlicher Genauigkeit verwendet, sodass das Verschieben des Modulos bis zum Ende der Summe keine Probleme mit dem Überlauf von Ganzzahlen verursacht.

Python 2, 60 58 Bytes

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

Ein ziemlich unkomplizierter Ansatz. Dies ist ein vollständiges Programm, das eine Liste von ganzen Zahlen über STDIN aufnimmt, z[72, 105, 33] .

(Danke an @xnor für den tollen Aliasing- / Initialisierungstipp)

J, 30 Bytes

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

Dies könnte wahrscheinlich mit einem anderen Zug mehr kondensiert werden.

Verwendung

Hier x $ yerstellt eine Liste mit xKopien von 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

Erläuterung

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

Oktave, 52 50 Bytes

2 Bytes dank @LuisMendo eingespart

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

Nimmt ein Array von Ganzzahlen als Eingabe.

low wird vom letzten Element von high (vor der Summierung) genommen, anstatt die Summe explizit zu berechnen, wodurch eine Gesamtsumme von ... 1 Byte eingespart wird !

Probelauf auf ideone .

CJam, 30 29 Bytes

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

Eingabe als Liste von Ganzzahlen.

Teste es hier.

Erläuterung

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 Bytes

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

Erläuterung:

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

Prüfung:

#! /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 Bytes)

Basierend auf der Lösung von R. Kap.

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

Ich habe die Multiplikation durch eine Verschiebung ersetzt und ein Paar Klammern entfernt.

Da ich keine Kommentare posten kann, habe ich eine neue Antwort gegeben.

Schema, 195 Bytes

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

Wenn da nicht all diese Klammern wären ...

Haskell, 54 50 Bytes

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

Anwendungsbeispiel: g [69,97,103,108,101,115,32,97,114,101,32,103,114,101,97,116,33]-> 918816254.

scanlBezieht den Startwert (-> 1) in die Liste ein (-> [1,1+b1,1+b1+b2,..]), so sumist 1das deaktiviert, was durch Voranstellen -1der Liste vor der Summierung festgelegt wird.

Edit: Danke @xnor für 4 Bytes.

JavaScript (ES7), 52 50 Bytes

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

ES6 benötigt 51 Bytes (ersetzen Sie 4 ** 8 durch 65536). Wenn Sie eine String-Version wünschen, dann für 69 Bytes:

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

Bearbeiten: 2 Bytes dank @ user81655 gespeichert.

ARM Thumb-2-Funktion akzeptiert uint8_t[]: 40 Bytes (36B für nicht standardmäßige ABI undint[] )

Features: Nicht verzögertes Modulo, daher sind Eingaben mit beliebiger Größe in Ordnung. Verwendet den Divisionsbefehl nicht, ist also nicht langsam. (ähm, zumindest nicht aus diesem Grund: P)

Einsparungen durch weniger strenge Regeln:

• -2B, wenn wir keine Register speichern müssen, bevor wir sie verwenden.
• -2B für die Aufforderung an den Aufrufer, Bytes in ein uint32_t[]Array zu entpacken .

Der beste Fall ist also 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 Bytes

Anmerkungen:

Statt log%mam Ende machen wir das if(low>=m) low-=min der Schleife. Wenn wir Tief vor Hoch machen, wissen wir, dass keines von beiden möglicherweise übersteigen 2*mkann. Modulo ist also nur eine Frage des Subtrahierens oder nicht. A cmpund subvorhergesagt ist nur 6B im Thumb2-Modus. Die Standardsprache für% ist 8B im Thumb2-Modus:

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

Die adler(char *)Version mit impliziter Länge hat dieselbe Codegröße wie die explizite Längeadler(uint8_t[], uint32_t len) . Wir können Flags für die Schleifenausgangsbedingung mit einem einzelnen 2B-Befehl in beide Richtungen setzen.

Die implizite Längenversion hat den Vorteil, dass sie korrekt mit der leeren Zeichenfolge arbeitet, anstatt zu versuchen, 2 ^ 32-mal eine Schleife auszuführen.

zusammenstellen / kompilieren mit:

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

oder

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

Ohne -statichat der Prozess, unter dem ausgeführt wird qemu-arm, seinen dynamischen Linker nicht gefunden. (Und ja, ich einen ARM - Cross-Entwick - Setup installieren nur für diese Antwort, weil ich meine dachte sagt-subtrahieren Idee war ordentlich.) Auf amd64 Ubuntu installieren gcc-arm-linux-gnueabi, g++-arm-linux-gnueabi. Ich fand eine gdb-arm-none-eabiArt kaum funktionierende Verbindung zu qemu-arm -g port.

Kommentierte Quelle:

// 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.cpphat die gleichen testfälle und main()wie für meine x86-64 antwort, startet aber so:

#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-Bit-Maschinencodefunktion: 32 Byte unter Verwendung einer benutzerdefinierten Aufrufkonvention

Argumente in Registern und keine anderen Register als bp (und sp) beibehalten.

Im 16-Bit-Code geben wir einen 32-Bit-Wert im dx:axRegisterpaar zurück. Das heißt , wir nicht ausgeben müssen , um alle Anweisungen Verschmelzung highund lowin eax. (Dies würde auch in 32- und 64-Bit-Code Bytes einsparen, aber wir können nur die Auslagerung dieser Arbeit in 16-Bit-Code an den Aufrufer rechtfertigen.)

Kommentierte Quelle und Testtreiber auf Github (für x86 16, 32 und 64bit und 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 Bytes

Getestet durch Assemblieren des gleichen Codes für den 32-Bit-Modus, damit ich ihn (mit einer Wrapper-Funktion) von C kompiliert mit aufrufen kann -m32. Für mich ist der 16bit-Modus etwas interessant, DOS-Systemaufrufe hingegen nicht. Alle Befehle haben explizite Operanden, mit Ausnahme von loopund lodsb. Daher werden bei der Zusammenstellung für den 32-Bit-Modus Präfixe mit Operandengröße verwendet. Gleiche Anweisung, andere Kodierung. Aber lodsbim 32bit Modus wird verwendet[esi] , so dass diese Testversion mit 32-Bit-Zeigern funktioniert (da wir keine Adressberechnung oder Zeigerinkrementierung / -vergleich durchführen).

Keine Inkongruenzen. Mein Testgeschirr gibt eine Meldung aus, wenn eine Nichtübereinstimmung vorliegt.

$ 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

Bei 16-Bit-Registern können wir die Modulo-Reduzierung erst nach der Schleife aufschieben. Es gibt einen interessanten Unterschied zwischen 16-Bit- und anderen Operandengrößen: m = 65521( 0xFFF1) ist mehr als die Hälfte von 65536. Das Subtrahieren mvon Übertrag hält den Wert unter 2 * m, auch wenn high=0xFFF0 + 0xFFF0. Nach der Schleife reicht ein Vergleichen und Subtrahieren anstelle von a div.

Ich habe eine neuartige Technik zur Modulo-Reduzierung eines Registers nach einer Addition entwickelt, die einen Übertrag erzeugen kann . Anstatt die obere Hälfte der Eingabe für auf Null zu setzen div, verwenden Sie setc dldiese Option, um einen 32-Bit-Dividend zu erstellen, der das nicht abgeschnittene Additionsergebnis enthält ( dhdas bereits auf Null gesetzt ist). ( divMacht 32b / 16b => 16bit Division.)

setcc(3 Bytes) wurde mit 386 eingeführt. Um dies auf 286 oder früher auszuführen, verwendet das Beste, das ich mir ausgedacht habe, den undokumentierten salcBefehl (setze AL aus Carry) . Es ist ein Ein-Byte-Opcode für sbb al,al, so dass wir salc/ neg alvor dem Ausführen des xchg ax, dx(was wir sowieso brauchen) verwenden könnten . Ohne salcgibt es eine 4B-Sequenz: sbb dx,dx/ neg dx. Wir können 3B sbb dx,dx/ nicht verwenden inc dx, da dies setnceher emulieren würde als setc.

Ich habe versucht , eine 32-Bit-Operandengröße anstelle der Verarbeitung von Carry zu verwenden, aber es sind nicht nur die addAnweisungen, die ein Präfix für die Operandengröße benötigen. Anweisungen zum Einrichten der Konstanten usw. benötigen auch Präfixe für die Operandengröße, sodass sie nicht die kleinsten sind.

Pyth, 25, 24 23 Bytes

1 Byte danke an @Jakube .

1 weiteres Byte dank @Jakube .

i%R65521sMeBhMsM._Q^4 8

Probieren Sie es online!

Übersetzung meiner Antwort in Jelly .

Perl 5, 43 Bytes

42 Bytes plus 1 für -aE statt-e

Die Eingabe erfolgt als durch Leerzeichen getrennte Dezimalzahlen.

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

Ein Tipp von meinem Hut zu Sp3000 , von dem ich Ideen für diese Antwort nahm.

Wie es funktioniert:

1. Wegen -a, $. beginnt bei 1 und @Fist das Eingangsarray. $hbeginnt bei 0. $_wird von verwendetmap als Platzhalter für jedes Element eines Arrays verwendet.
2. map$h+=$.+=$_,@Fbedeutet , dass in für jedes Element @Fwir dieses Element hinzufügen $.und fügen Sie dann $.zu $h.
3. Dann machen wir die modulare Arithmetik $.%65521+$h%65521*4**8(das heißt, ($. % 65521) + ( ($h % 65521) * (4**8) )und say(drucken) das Ergebnis.

Faktor 112 109 103 Bytes

Nun , dies ist eine wörtliche Übersetzung des Algorithmus in der Frage ... nun, da ich es tatsächlich gemacht habe, weißt du, richtig.

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

Erwartet eine beliebige Folge von Zahlen oder eine Zeichenfolge (kein großer Unterschied, obwohl sie technisch nicht identisch sind).

Ich weiß nicht, wie dies für die angegebene Grenze für eine mit 32-Bit-Wortgröße kompilierte Version von Factor funktioniert, aber für meine 6-GB-64-Bit-Maschine mit 2,2 GHz:

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

Rubin, 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

Basierend auf der @ Mark Adler- Lösung .

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

Verwendung

=> (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 Zeichen Golf)

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

Golf gespielt

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

Fügen Sie es in die Developers Console ein und geben Sie ihm ein Array of Bytes EG:

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

Und es wird die Prüfsumme an die Konsole zurück

TMP, 55 Bytes

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

Die Implementierung in Lua finden Sie hier: http://preview.ccode.gq/projects/TMP.lua

Python 3.5, 82 Bytes:

( -1 Byte danke an Neil ! )

( -1 byte dank mathmandan ! )

( -4 Bytes dank Dennis ! )

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

Eine anonyme lambdaFunktion. Akzeptiert ein Byte-Array, wendet den gesamten Algorithmus auf das Array an und gibt das Ergebnis aus. Hat erfolgreich für alle Testfälle gearbeitet. Sie rufen dies auf, indem Sie eine Variable zuweisen und diese Variable dann wie eine normale Funktion aufrufen. Wenn Sie die Shell verwenden, sollte diese ohne Druckfunktion ausgegeben werden. Wenn dies nicht der Fall ist, müssen Sie den Funktionsaufruf in den Zeilenumbruch einbindenprint() Funktion einschließen, um die Ausgabe tatsächlich zu sehen.

Probieren Sie es online! (Ideone)

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

Faire Warnung, die einzige Implementierung, auf der ich dies getestet habe, ist mein eigener Port der Sprache zu F #. Es wird nicht golfen, vor allem, weil ich es leichter fand, ein paar lange Läufe zu machen, während sich meine Hauptkonstante am Boden abkühlte, damit ich zurückkommen und es optimieren kann.

Wie funktioniert es?

• Der R'~++Y++~'LBlock verschmilzt eine Konstante 256 und startet sie nach unten, wobei der Massenmultiplikator des Reaktors direkt darunter eingestellt wird.
• Das R'~++A++~'A Block verschmilzt weitere 256 und startet ihn in Richtung des Reaktors, der das Teilchen in zwei Massen-Vielfache von 65536Masse aufspaltet, wobei sie nach links und rechts abgeschossen werden (wobei das rechte Teilchen sofort vom Terminator zerstört wird).
• Das linke Teilchen trifft auf einen anderen Reaktor und wird gespalten, wobei es sich in zwei Teilchen gleicher Masse auf und ab spaltet.
• Das aufwärts wandernde Teilchen mit der Zweierpotenz durchläuft eine Massenmanipulation von Null, reflektiert nach links und stellt dann den Massenmultiplikator des Fusionsreaktors ein. Mit diesem Reaktor multiplizieren wir den H-Block.
• Das nach unten wandernde Teilchen reflektiert nach links und wirft auf lange Sicht Masse ab und erreicht letztendlich eine Masse von 65521 (unserer großen Primzahl) erreicht.
• Der Drehspiegel (Z ) am Ende des Durchlaufs bewirkt, dass das Partikel die Primzahl dupliziert und eine nach rechts zurückschickt, wo sie letztendlich die gespeicherte Masse des Spaltreaktors ( ^) festlegt . So wenden wir den Modul-Operator auf den H-Block an.
• Die zweite Kopie wird zurückgespiegelt und erfüllt dort eine analoge Funktion für den Spaltreaktor (< ), den wir für den L-Block verwenden werden.
• Jetzt, da unsere Konstanten vorhanden sind, führen wir oben links Shenanigans durch, um unsere Eingaben zu lesen und unsere beiden Listen zu generieren. Um ehrlich zu sein, vergesse ich, wie diese funktionieren, aber für die leere Saite musste ich das H-Block-Summierungspartikel verlangsamen, was den |S"Kühlturm" erklärt.
• \Y/ schmilzt den L-Block (der über den linken Kanal hereinkommt) und den H-Block (der über den rechten Kanal hereinkommt) und knallt sie dann in einen Terminator, der den Exit-Code auf die verschmolzene Masse setzt.