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}