1// Copyright 2009 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5// Package adler32 implements the Adler-32 checksum.
6//
7// It is defined in RFC 1950:
8//	Adler-32 is composed of two sums accumulated per byte: s1 is
9//	the sum of all bytes, s2 is the sum of all s1 values. Both sums
10//	are done modulo 65521. s1 is initialized to 1, s2 to zero.  The
11//	Adler-32 checksum is stored as s2*65536 + s1 in most-
12//	significant-byte first (network) order.
13package adler32
14
15import (
16	"errors"
17	"hash"
18)
19
20const (
21	// mod is the largest prime that is less than 65536.
22	mod = 65521
23	// nmax is the largest n such that
24	// 255 * n * (n+1) / 2 + (n+1) * (mod-1) <= 2^32-1.
25	// It is mentioned in RFC 1950 (search for "5552").
26	nmax = 5552
27)
28
29// The size of an Adler-32 checksum in bytes.
30const Size = 4
31
32// digest represents the partial evaluation of a checksum.
33// The low 16 bits are s1, the high 16 bits are s2.
34type digest uint32
35
36func (d *digest) Reset() { *d = 1 }
37
38// New returns a new hash.Hash32 computing the Adler-32 checksum. Its
39// Sum method will lay the value out in big-endian byte order. The
40// returned Hash32 also implements encoding.BinaryMarshaler and
41// encoding.BinaryUnmarshaler to marshal and unmarshal the internal
42// state of the hash.
43func New() hash.Hash32 {
44	d := new(digest)
45	d.Reset()
46	return d
47}
48
49func (d *digest) Size() int { return Size }
50
51func (d *digest) BlockSize() int { return 4 }
52
53const (
54	magic         = "adl\x01"
55	marshaledSize = len(magic) + 4
56)
57
58func (d *digest) MarshalBinary() ([]byte, error) {
59	b := make([]byte, 0, marshaledSize)
60	b = append(b, magic...)
61	b = appendUint32(b, uint32(*d))
62	return b, nil
63}
64
65func (d *digest) UnmarshalBinary(b []byte) error {
66	if len(b) < len(magic) || string(b[:len(magic)]) != magic {
67		return errors.New("hash/adler32: invalid hash state identifier")
68	}
69	if len(b) != marshaledSize {
70		return errors.New("hash/adler32: invalid hash state size")
71	}
72	*d = digest(readUint32(b[len(magic):]))
73	return nil
74}
75
76func appendUint32(b []byte, x uint32) []byte {
77	a := [4]byte{
78		byte(x >> 24),
79		byte(x >> 16),
80		byte(x >> 8),
81		byte(x),
82	}
83	return append(b, a[:]...)
84}
85
86func readUint32(b []byte) uint32 {
87	_ = b[3]
88	return uint32(b[3]) | uint32(b[2])<<8 | uint32(b[1])<<16 | uint32(b[0])<<24
89}
90
91// Add p to the running checksum d.
92func update(d digest, p []byte) digest {
93	s1, s2 := uint32(d&0xffff), uint32(d>>16)
94	for len(p) > 0 {
95		var q []byte
96		if len(p) > nmax {
97			p, q = p[:nmax], p[nmax:]
98		}
99		for len(p) >= 4 {
100			s1 += uint32(p[0])
101			s2 += s1
102			s1 += uint32(p[1])
103			s2 += s1
104			s1 += uint32(p[2])
105			s2 += s1
106			s1 += uint32(p[3])
107			s2 += s1
108			p = p[4:]
109		}
110		for _, x := range p {
111			s1 += uint32(x)
112			s2 += s1
113		}
114		s1 %= mod
115		s2 %= mod
116		p = q
117	}
118	return digest(s2<<16 | s1)
119}
120
121func (d *digest) Write(p []byte) (nn int, err error) {
122	*d = update(*d, p)
123	return len(p), nil
124}
125
126func (d *digest) Sum32() uint32 { return uint32(*d) }
127
128func (d *digest) Sum(in []byte) []byte {
129	s := uint32(*d)
130	return append(in, byte(s>>24), byte(s>>16), byte(s>>8), byte(s))
131}
132
133// Checksum returns the Adler-32 checksum of data.
134func Checksum(data []byte) uint32 { return uint32(update(1, data)) }
135