001/*
002 * Syncany, www.syncany.org
003 * Copyright (C) 2011-2016 Philipp C. Heckel <philipp.heckel@gmail.com>
004 *
005 * This program is free software: you can redistribute it and/or modify
006 * it under the terms of the GNU General Public License as published by
007 * the Free Software Foundation, either version 3 of the License, or
008 * (at your option) any later version.
009 *
010 * This program is distributed in the hope that it will be useful,
011 * but WITHOUT ANY WARRANTY; without even the implied warranty of
012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
013 * GNU General Public License for more details.
014 *
015 * You should have received a copy of the GNU General Public License
016 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
017 */
018package org.syncany.chunk;
019
020/**
021 * A simple 32-bit "rolling" checksum. This checksum algorithm is based
022 * upon the algorithm outlined in the paper "The rsync algorithm" by
023 * Andrew Tridgell and Paul Mackerras. The algorithm works in such a way
024 * that if one knows the sum of a block
025 * <em>X<sub>k</sub>...X<sub>l</sub></em>, then it is a simple matter to
026 * compute the sum for <em>X<sub>k+1</sub>...X<sub>l+1</sub></em>.
027 *
028 * <p>The class has been adapted to work with the Syncany chunking classes.
029 *
030 * @author Casey Marshall
031 * @author Philipp C. Heckel (philipp.heckel@gmail.com)
032 * @version $Revision: 188 $
033 */
034public class Adler32Fingerprinter extends Fingerprinter {
035        protected final int charOffset;
036
037        /**
038         * The first half of the checksum.
039         */
040        protected int a;
041
042        /**
043         * The second half of the checksum.
044         */
045        protected int b;
046
047        /**
048         * The place from whence the current checksum has been computed.
049         */
050        protected int pos;
051
052        /**
053         * The place to where the current checksum has been computed.
054         */
055        protected int len;
056
057        /**
058         * The block from which the checksum is computed.
059         */
060        protected byte[] block;
061
062        /**
063         * The index in {@link #newBlock} where the newest byte has
064         * been stored.
065         */
066        protected int newIndex;
067
068        /**
069         * The block that is receiving new input.
070         */
071        protected byte[] newBlock;
072
073        /**
074         * Creates a new rolling checksum. The <i>charOffset</i> argument
075         * affects the output of this checksum; rsync uses a char offset of
076         * 0, librsync 31.
077         */
078        public Adler32Fingerprinter(int charOffset) {
079                this.charOffset = charOffset;
080                a = b = 0;
081                pos = 0;
082        }
083
084        public Adler32Fingerprinter() {
085                this(0);
086        }
087
088        @Override
089        public int getValue() {
090                return (a & 0xffff) | (b << 16);
091        }
092
093        @Override
094        public void reset() {
095                pos = 0;
096                a = b = 0;
097                len = 0;
098        }
099
100        /**
101         * "Roll" the checksum. This method takes a single byte as byte
102         * <em>X<sub>l+1</sub></em>, and recomputes the checksum for
103         * <em>X<sub>k+1</sub>...X<sub>l+1</sub></em>. This is the
104         * preferred method for updating the checksum.
105         *
106         * @param bt The next byte.
107         */
108        @Override
109        public void roll(byte bt) {
110                a -= block[pos] + charOffset;
111                b -= len * (block[pos] + charOffset);
112                a += bt + charOffset;
113                b += a;
114                block[pos] = bt;
115                pos++;
116                if (pos == len) {
117                        pos = 0;
118                }
119        }
120
121        /**
122         * Update the checksum by trimming off a byte only, not adding
123         * anything.
124         */
125        public void trim() {
126                a -= block[pos % block.length] + charOffset;
127                b -= len * (block[pos % block.length] + charOffset);
128                pos++;
129                len--;
130        }
131
132        @Override
133        public void check(byte[] buf, int off, int len) {
134                block = new byte[len];
135                System.arraycopy(buf, off, block, 0, len);
136                reset();
137                this.len = block.length;
138                int i;
139
140                for (i = 0; i < block.length - 4; i += 4) {
141                        b += 4 * (a + block[i]) + 3 * block[i + 1]
142                                        + 2 * block[i + 2] + block[i + 3] + 10 * charOffset;
143                        a += block[i] + block[i + 1] + block[i + 2]
144                                        + block[i + 3] + 4 * charOffset;
145                }
146                for (; i < block.length; i++) {
147                        a += block[i] + charOffset;
148                        b += a;
149                }
150        }
151
152        @Override
153        public Object clone() throws CloneNotSupportedException {
154                return super.clone();
155        }
156
157        @Override
158        public int hashCode() {
159                final int prime = 31;
160                int result = 1;
161                result = prime * result + a;
162                result = prime * result + b;
163                return result;
164        }
165
166        @Override
167        public boolean equals(Object o) {
168                if (o == this) {
169                        return true;
170                }
171                if (o instanceof Adler32Fingerprinter) {
172                        return ((Adler32Fingerprinter) o).a == a && ((Adler32Fingerprinter) o).b == b;
173                }
174                return false;
175        }
176
177        @Override
178        public String toString() {
179                return "Adler32";
180        }
181}