Compute the Adler-32 checksum

Question

Background

Adler-32 is a 32-bit checksum invented by Mark Adler in 1995 which is part of the widely used zlib library (also developed by Adler). Adler-32 is not as reliable as a 32-bit cyclic redundancy check, but – at least in software – it is much faster and easier to implement.

Definition

Let B = [b₁, ⋯, b_n] be a byte array.

The Adler-32 checksum of B is defined as the result of low + 65536 × high, where:

low := ((1 + b₁ + ⋯ + b_n) mod 65521)
high := (((1 + b₁) + (1 + b₁ + b₂) + ⋯ (1 + b₁ + ⋯ + b_n)) mod 65521)

Task

Given a byte array as input, compute and return its Adler-32 checksum, abiding to the following.

You can take the input as an array of bytes or integers, or as a string.

In both cases, only bytes corresponding to printable ASCII characters will occur in the input.

You may assume that the length of the input will satisfy 0 < length ≤ 4096.
If you choose to print the output, you may use any positive base up to and including 256.

If you choose unary, make sure interpreter can handle up to 2³² - 983056 bytes of output on a machine with 16 GiB of RAM.
Built-ins that compute the Adler-32 checksum are forbidden.
Standard code-golf rules apply.

Test cases

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

I will note that many of the answers here will fail with large or very large input sequences when they overflow the 32 or 64-bit integer sums, due to deferring the modulo operation until after the sums are computed. A truly compliant implementation would need to do the modulo operation at least periodically to keep the sums from overflowing. A 32-bit signed integer would overflow after only 4096 0xff's. A 64-bit signed integer would overflow after 256 MiB of 0xff's. — Mark Adler, Apr 30, 2016 at 19:01
@MarkAdler Hm, fair point. Since I didn't specify that the solutions would have to work for arbitrarily long strings and I don't want to invalidate existing answers, I'll set a limit for the input's length. — Dennis, Apr 30, 2016 at 19:20
@MarkAdler I don't think it matters. I'm fairly certain that overflow (signed 32-bit integers) can occur only with 4104 or more bytes of input, as the maximum value of high before the modulo is n*(n+1)/2*255+n. On top of that, the challenge restricts the input to bytes corresponding to printable ASCII characters. — Dennis, Apr 30, 2016 at 22:22
We could also allow languages to overflow their numeric types, and only require that the returned result be equivalent, accounting for overflow, to the correct result. — miles, Apr 30, 2016 at 23:32
@PeterCordes Yes, arrays of 32-bit ints a perfectly fine. At least in my opinion, submissions should focus on golfing the algorithm, and pay as little attention as possible to I/O. — Dennis, May 1, 2016 at 5:53

Rawberry · Accepted Answer · 2016-05-04 14:40:53Z

ABAP, 118 bytes

FORM a TABLES t USING l h.l = 1.LOOP AT t.ADD:t TO l,l TO h.ENDLOOP.l = l MOD 65521 + 65536 * ( h MOD 65521 ).ENDFORM.

Ungolfed

FORM a TABLES t USING l h.
  l = 1.
  LOOP AT t.
    ADD: t TO l,
         l TO h.
  ENDLOOP.
  l = l MOD 65521 + 65536 * ( h MOD 65521 ).
ENDFORM.

This is my first try at code golfing, if I did anything wrong please let me know! I used ABAP because that's my main programming language. Now for the explanation:

FORM a TABLES t USING l h.
  ...
ENDFORM.

This declares the function "a" with the inputs t, l and h. I defined t as a table of integers and filled it with the different numbers from the original post (for test purposes). l and h are defined as DEC variables with length 31 (highest it can go in ABAP). l is also used as the returning variable for the function so I don't have to use an additional variable.

  LOOP AT t.
    ...
  ENDLOOP.

This is a loop over the table t, which is defined as a table with header-line. This means that the table has a header-line which acts as a variable ("t") and it also has a table body ("t[ ]") at the same time. So "LOOP AT t" reads the rows in the table t[ ] (in order) into the header-line t. Header-lines are obsolete but they save quite a bit of bytes over the now used "LOOP AT table INTO variable.".

    ADD: t TO l,
         l TO h.

Within the loop I'm starting a slightly modified version (pretty much just rearranged) of the calculation that Dennis has in his original post. l = low, h = high. I'm adding the current value in the table to the variable l (which i define to start at 1 in the line "l = 1."). Each step in the loop I'm also adding l to h. I use "ADD" because ABAP doesn't have "l += t" and using the code above is shorter than:

l = l + t.
h = h + l.

After the loop we have the following:

l = (1 + b₁ + ⋯ + b_n)
h = ((1 + b₁) + (1 + b₁ + b₂) + ⋯ (1 + b₁ + ⋯ + b_n))

At the end I'm doing the final calculation:

  l = l MOD 65521 + 65536 * ( h MOD 65521 ).

Sadly you need spaces between the operators and numbers/variables because ABAP uses the operators without spaces for different things. For example:

char+4 = 'A'.

This sets the 5th character (because the offset is set as "4") of the character variable "char" as 'A'. So if "char" was "BBBBB" before that line, it would be "BBBBA" after.

I hope this explanation isn't too long (which I think it is, since the code is really straight forward). ABAP doesn't have bitwise operations AFAIK so I couldn't use a shorter algorithm but I think 118 bytes is still pretty good.

Here's the full program in case anyone can and wants to test it:

REPORT z_adler_checksum.

DATA:
  lt_i TYPE TABLE OF i WITH HEADER LINE, "Input table
  l_l  TYPE zz, "Calculation and return variable
  l_h  TYPE zz. "Calculation variable

DO 1040 TIMES. "Filling the table for the last test case in the original post
  APPEND 63 TO lt_i.
ENDDO.

PERFORM a TABLES lt_i USING l_l l_h. "Calling the function

WRITE l_l. "Output of the result

FORM a TABLES t USING l h.
  l = 1.
  LOOP AT t.
    ADD: t TO l,
         l TO h.
  ENDLOOP.
  l = l MOD 65521 + 65536 * ( h MOD 65521 ).
ENDFORM.

scrawl · Accepted Answer · 2019-11-01 10:37:22Z

1

K (ngn/k), 32 bytes

{+/1 65536*65521!(*|x),+/x:1+\x}

Try it online!

answered Nov 1, 2019 at 10:37

scrawl

1,2994 silver badges12 bronze badges

Add a comment |

Razetime · Accepted Answer · 2020-10-05 12:22:46Z

Husk, 22 bytes

+*□256₁m→∫¹₁:1
%65521Σ

Try it online!

May be shorter with a lambda.

Explanation

%65521Σ Function ₁:
      Σ sum of elements of the argument
%65521Σ modulo 65521

+*□256₁m→∫¹₁:1 main program:
           ₁:1 prepend 1(to the input), apply Function ₁
+              plus
         ∫¹    cumulative sums of the input
       m→      increment each sum
      ₁        apply function 1
 *□256         multiply with 256² (65536)

Keith Pinson · Accepted Answer · 2016-05-01 18:37:25Z

0

Scala, 94 Bytes

(s:String)=>{
val t=((1L,0L)/:s){(r,c)=>val a=(c+r._1)%65521
(a,(a+r._2)%65521)};t._1+(t._2<<16)
}

Performs Adler-32 Checksum on Strings, using the alternate for foldLeft, /:

edited May 1, 2016 at 18:37

answered May 1, 2016 at 12:37

Keith Pinson

1213 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

Postgresql, 164 bytes

SELECT t,((SUM(b)+1)%65521)+65536*(SUM(1+b*(LENGTH(t)-r+1))%65521)
FROM v,LATERAL generate_series(1,LENGTH(t))r
,LATERAL(SELECT ASCII(SUBSTRING(t,r,1))b)z GROUP BY t;

SqlFiddleDemo

Output:

╔═══════════════════════════════════╦════════════╗
║                t                  ║  ?column?  ║
╠═══════════════════════════════════╬════════════╣
║ PostgreSQL can handle it          ║ 1850149040 ║
║ ?(x1040)                          ║ 2181038080 ║
║ Programming Puzzles & Code Golf   ║ 3133147946 ║
║ Eagles are great!                 ║  918816254 ║
║ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  ║   68095937 ║
╚═══════════════════════════════════╩════════════╝

Version with parameter as subquery:

SELECT((SUM(b)+1)%65521)+65536*(SUM(1+b*(LENGTH(t)-r+1))%65521)
FROM(SELECT text'Eagles are great!'t)s,LATERAL generate_series(1,LENGTH(t))r
,LATERAL(SELECT ASCII(SUBSTRING(t,r,1))b)z;

SqlFiddleDemo2

Community · Accepted Answer · 2020-06-17 09:04:33Z

Forth (gforth), 117 bytes

: f 2dup bounds 1 -rot do i c@ + loop 65521 mod -rot dup 0 do i for over i + c@ + next loop 65521 mod nip 65536 * + ;

Try it online!

Code explanation

: f                 \ start a new word definition
\ Calculate Low:
  2dup bounds       \ copy the string start address and length and get string end address
  1 -rot            \ start an accumulator to hold low (initialize to 1)
  do                \ loop from start address to end-address
    i c@ +          \ get ascii value for each char and add to accumulator
  loop              \ end loop
  65521 mod -rot    \ get value % 65521 to get Low and move off top of stack

\ Calculate High:
  dup 0 do          \ loop from 0 to string-length - 1
    i for           \ loop from outer-loop index to 0
      over i +      \ get address of current ascii char
      c@ +          \ get value of current char and add to total
    next            \ end inner loop
  loop              \ end outer loop
  65521 mod         \ get value % 65521 to get High
  nip               \ remove extraneous value from stack

\ Calculate Checksum
  65536 * +         \ multiply High by 65536 and add to Low
;                   \ end word definition

Shaggy · Accepted Answer · 2020-10-05 15:19:24Z

0

Japt, 23 bytes

[UåÄ Up1]®x uFnG²²ÃìG²²

Try it

edited Oct 5, 2020 at 15:19

answered Oct 5, 2020 at 14:58

Shaggy

39.6k4 gold badges32 silver badges90 bronze badges

Add a comment |

Shaggy · Accepted Answer · 2020-10-05 15:53:47Z

0

Rockstar, 156 bytes

listen to N
T's1
C's0
while N
let T be+N-0
let C be+T
listen to N

X's65521
let M be C/X
turn down M
let C be-M*X
let M be T/X
turn down M
say T-M*X+C*65536

Try it here (Code will need to be pasted in, with input as newline separated codepoints)

answered Oct 5, 2020 at 15:53

Shaggy

39.6k4 gold badges32 silver badges90 bronze badges

Add a comment |

Stack Exchange Network

Compute the Adler-32 checksum

Background

Definition

Task

Test cases

38 Answers 38

ABAP, 118 bytes

K (ngn/k), 32 bytes

Husk, 22 bytes

Explanation

Scala, 94 Bytes

Postgresql, 164 bytes

Forth (gforth), 117 bytes

Code explanation

Japt, 23 bytes

Rockstar, 156 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
math
arithmetic
checksum
or ask your own question.

Linked

Hot Network Questions

Compute the Adler-32 checksum

Background

Definition

Task

Test cases

38 Answers 38

ABAP, 118 bytes

K (ngn/k), 32 bytes

Husk, 22 bytes

Explanation

Scala, 94 Bytes

Postgresql, 164 bytes

Forth (gforth), 117 bytes

Code explanation

Japt, 23 bytes

Rockstar, 156 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfmatharithmeticchecksum or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
math
arithmetic
checksum
or ask your own question.