View Javadoc
1   /*
2    * Copyright (C) 2017, Google Inc. and others
3    *
4    * This program and the accompanying materials are made available under the
5    * terms of the Eclipse Distribution License v. 1.0 which is available at
6    * https://www.eclipse.org/org/documents/edl-v10.php.
7    *
8    * SPDX-License-Identifier: BSD-3-Clause
9    */
10  
11  package org.eclipse.jgit.util.sha1;
12  
13  import static java.lang.Integer.lowestOneBit;
14  import static java.lang.Integer.numberOfTrailingZeros;
15  import static java.lang.Integer.rotateLeft;
16  import static java.lang.Integer.rotateRight;
17  
18  import java.text.MessageFormat;
19  import java.util.Arrays;
20  
21  import org.eclipse.jgit.internal.JGitText;
22  import org.eclipse.jgit.lib.MutableObjectId;
23  import org.eclipse.jgit.lib.ObjectId;
24  import org.eclipse.jgit.util.NB;
25  import org.eclipse.jgit.util.SystemReader;
26  import org.slf4j.Logger;
27  import org.slf4j.LoggerFactory;
28  
29  /**
30   * Pure Java implementation of SHA-1 from FIPS 180-1 / RFC 3174.
31   *
32   * <p>
33   * See <a href="https://tools.ietf.org/html/rfc3174">RFC 3174</a>.
34   * <p>
35   * Unlike MessageDigest, this implementation includes the algorithm used by
36   * {@code sha1dc} to detect cryptanalytic collision attacks against SHA-1, such
37   * as the one used by <a href="https://shattered.it/">SHAttered</a>. See
38   * <a href="https://github.com/cr-marcstevens/sha1collisiondetection">
39   * sha1collisiondetection</a> for more information.
40   * <p>
41   * When detectCollision is true (default), this implementation throws
42   * {@link org.eclipse.jgit.util.sha1.Sha1CollisionException} from any digest
43   * method if a potential collision was detected.
44   *
45   * @since 4.7
46   */
47  public class SHA1 {
48  	private static final Logger LOG = LoggerFactory.getLogger(SHA1.class);
49  	private static final boolean DETECT_COLLISIONS;
50  
51  	static {
52  		SystemReader sr = SystemReader.getInstance();
53  		String v = sr.getProperty("org.eclipse.jgit.util.sha1.detectCollision"); //$NON-NLS-1$
54  		DETECT_COLLISIONS = v != null ? Boolean.parseBoolean(v) : true;
55  	}
56  
57  	/**
58  	 * Create a new context to compute a SHA-1 hash of data.
59  	 *
60  	 * @return a new context to compute a SHA-1 hash of data.
61  	 */
62  	public static SHA1 newInstance() {
63  		return new SHA1();
64  	}
65  
66  	private final State h = new State();
67  	private final int[] w = new int[80];
68  
69  	/** Buffer to accumulate partial blocks to 64 byte alignment. */
70  	private final byte[] buffer = new byte[64];
71  
72  	/** Total number of bytes in the message. */
73  	private long length;
74  
75  	private boolean detectCollision = DETECT_COLLISIONS;
76  	private boolean foundCollision;
77  
78  	private final int[] w2 = new int[80];
79  	private final State state58 = new State();
80  	private final State state65 = new State();
81  	private final State hIn = new State();
82  	private final State hTmp = new State();
83  
84  	private SHA1() {
85  		h.init();
86  	}
87  
88  	/**
89  	 * Enable likely collision detection.
90  	 * <p>
91  	 * Default is {@code true}.
92  	 * <p>
93  	 * May also be set by system property:
94  	 * {@code -Dorg.eclipse.jgit.util.sha1.detectCollision=true}.
95  	 *
96  	 * @param detect
97  	 *            a boolean.
98  	 * @return {@code this}
99  	 */
100 	public SHA1 setDetectCollision(boolean detect) {
101 		detectCollision = detect;
102 		return this;
103 	}
104 
105 	/**
106 	 * Update the digest computation by adding a byte.
107 	 *
108 	 * @param b a byte.
109 	 */
110 	public void update(byte b) {
111 		int bufferLen = (int) (length & 63);
112 		length++;
113 		buffer[bufferLen] = b;
114 		if (bufferLen == 63) {
115 			compress(buffer, 0);
116 		}
117 	}
118 
119 	/**
120 	 * Update the digest computation by adding bytes to the message.
121 	 *
122 	 * @param in
123 	 *            input array of bytes.
124 	 */
125 	public void update(byte[] in) {
126 		update(in, 0, in.length);
127 	}
128 
129 	/**
130 	 * Update the digest computation by adding bytes to the message.
131 	 *
132 	 * @param in
133 	 *            input array of bytes.
134 	 * @param p
135 	 *            offset to start at from {@code in}.
136 	 * @param len
137 	 *            number of bytes to hash.
138 	 */
139 	public void update(byte[] in, int p, int len) {
140 		// SHA-1 compress can only process whole 64 byte blocks.
141 		// Hold partial updates in buffer, whose length is the low bits.
142 		int bufferLen = (int) (length & 63);
143 		length += len;
144 
145 		if (bufferLen > 0) {
146 			int n = Math.min(64 - bufferLen, len);
147 			System.arraycopy(in, p, buffer, bufferLen, n);
148 			p += n;
149 			len -= n;
150 			if (bufferLen + n < 64) {
151 				return;
152 			}
153 			compress(buffer, 0);
154 		}
155 		while (len >= 64) {
156 			compress(in, p);
157 			p += 64;
158 			len -= 64;
159 		}
160 		if (len > 0) {
161 			System.arraycopy(in, p, buffer, 0, len);
162 		}
163 	}
164 
165 	private void compress(byte[] block, int p) {
166 		initBlock(block, p);
167 		int ubcDvMask = detectCollision ? UbcCheck.check(w) : 0;
168 		compress();
169 
170 		while (ubcDvMask != 0) {
171 			int b = numberOfTrailingZeros(lowestOneBit(ubcDvMask));
172 			UbcCheck.DvInfo dv = UbcCheck.DV[b];
173 			for (int i = 0; i < 80; i++) {
174 				w2[i] = w[i] ^ dv.dm[i];
175 			}
176 			recompress(dv.testt);
177 			if (eq(hTmp, h)) {
178 				foundCollision = true;
179 				break;
180 			}
181 			ubcDvMask &= ~(1 << b);
182 		}
183 	}
184 
185 	private void initBlock(byte[] block, int p) {
186 		for (int t = 0; t < 16; t++) {
187 			w[t] = NB.decodeInt32(block, p + (t << 2));
188 		}
189 
190 		// RFC 3174 6.1.b, extend state vector to 80 words.
191 		for (int t = 16; t < 80; t++) {
192 			int x = w[t - 3] ^ w[t - 8] ^ w[t - 14] ^ w[t - 16];
193 			w[t] = rotateLeft(x, 1); // S^1(...)
194 		}
195 	}
196 
197 	private void compress() {
198 		// Method 1 from RFC 3174 section 6.1.
199 		// Method 2 (circular queue of 16 words) is slower.
200 		int a = h.a, b = h.b, c = h.c, d = h.d, e = h.e;
201 
202 		// @formatter:off
203 		 e += s1(a, b, c, d,w[ 0]);  b = rotateLeft( b, 30);
204 		 d += s1(e, a, b, c,w[ 1]);  a = rotateLeft( a, 30);
205 		 c += s1(d, e, a, b,w[ 2]);  e = rotateLeft( e, 30);
206 		 b += s1(c, d, e, a,w[ 3]);  d = rotateLeft( d, 30);
207 		 a += s1(b, c, d, e,w[ 4]);  c = rotateLeft( c, 30);
208 		 e += s1(a, b, c, d,w[ 5]);  b = rotateLeft( b, 30);
209 		 d += s1(e, a, b, c,w[ 6]);  a = rotateLeft( a, 30);
210 		 c += s1(d, e, a, b,w[ 7]);  e = rotateLeft( e, 30);
211 		 b += s1(c, d, e, a,w[ 8]);  d = rotateLeft( d, 30);
212 		 a += s1(b, c, d, e,w[ 9]);  c = rotateLeft( c, 30);
213 		 e += s1(a, b, c, d,w[ 10]);  b = rotateLeft( b, 30);
214 		 d += s1(e, a, b, c,w[ 11]);  a = rotateLeft( a, 30);
215 		 c += s1(d, e, a, b,w[ 12]);  e = rotateLeft( e, 30);
216 		 b += s1(c, d, e, a,w[ 13]);  d = rotateLeft( d, 30);
217 		 a += s1(b, c, d, e,w[ 14]);  c = rotateLeft( c, 30);
218 		 e += s1(a, b, c, d,w[ 15]);  b = rotateLeft( b, 30);
219 		 d += s1(e, a, b, c,w[ 16]);  a = rotateLeft( a, 30);
220 		 c += s1(d, e, a, b,w[ 17]);  e = rotateLeft( e, 30);
221 		 b += s1(c, d, e, a,w[ 18]);  d = rotateLeft( d, 30);
222 		 a += s1(b, c, d, e,w[ 19]);  c = rotateLeft( c, 30);
223 
224 		 e += s2(a, b, c, d,w[ 20]);  b = rotateLeft( b, 30);
225 		 d += s2(e, a, b, c,w[ 21]);  a = rotateLeft( a, 30);
226 		 c += s2(d, e, a, b,w[ 22]);  e = rotateLeft( e, 30);
227 		 b += s2(c, d, e, a,w[ 23]);  d = rotateLeft( d, 30);
228 		 a += s2(b, c, d, e,w[ 24]);  c = rotateLeft( c, 30);
229 		 e += s2(a, b, c, d,w[ 25]);  b = rotateLeft( b, 30);
230 		 d += s2(e, a, b, c,w[ 26]);  a = rotateLeft( a, 30);
231 		 c += s2(d, e, a, b,w[ 27]);  e = rotateLeft( e, 30);
232 		 b += s2(c, d, e, a,w[ 28]);  d = rotateLeft( d, 30);
233 		 a += s2(b, c, d, e,w[ 29]);  c = rotateLeft( c, 30);
234 		 e += s2(a, b, c, d,w[ 30]);  b = rotateLeft( b, 30);
235 		 d += s2(e, a, b, c,w[ 31]);  a = rotateLeft( a, 30);
236 		 c += s2(d, e, a, b,w[ 32]);  e = rotateLeft( e, 30);
237 		 b += s2(c, d, e, a,w[ 33]);  d = rotateLeft( d, 30);
238 		 a += s2(b, c, d, e,w[ 34]);  c = rotateLeft( c, 30);
239 		 e += s2(a, b, c, d,w[ 35]);  b = rotateLeft( b, 30);
240 		 d += s2(e, a, b, c,w[ 36]);  a = rotateLeft( a, 30);
241 		 c += s2(d, e, a, b,w[ 37]);  e = rotateLeft( e, 30);
242 		 b += s2(c, d, e, a,w[ 38]);  d = rotateLeft( d, 30);
243 		 a += s2(b, c, d, e,w[ 39]);  c = rotateLeft( c, 30);
244 
245 		 e += s3(a, b, c, d,w[ 40]);  b = rotateLeft( b, 30);
246 		 d += s3(e, a, b, c,w[ 41]);  a = rotateLeft( a, 30);
247 		 c += s3(d, e, a, b,w[ 42]);  e = rotateLeft( e, 30);
248 		 b += s3(c, d, e, a,w[ 43]);  d = rotateLeft( d, 30);
249 		 a += s3(b, c, d, e,w[ 44]);  c = rotateLeft( c, 30);
250 		 e += s3(a, b, c, d,w[ 45]);  b = rotateLeft( b, 30);
251 		 d += s3(e, a, b, c,w[ 46]);  a = rotateLeft( a, 30);
252 		 c += s3(d, e, a, b,w[ 47]);  e = rotateLeft( e, 30);
253 		 b += s3(c, d, e, a,w[ 48]);  d = rotateLeft( d, 30);
254 		 a += s3(b, c, d, e,w[ 49]);  c = rotateLeft( c, 30);
255 		 e += s3(a, b, c, d,w[ 50]);  b = rotateLeft( b, 30);
256 		 d += s3(e, a, b, c,w[ 51]);  a = rotateLeft( a, 30);
257 		 c += s3(d, e, a, b,w[ 52]);  e = rotateLeft( e, 30);
258 		 b += s3(c, d, e, a,w[ 53]);  d = rotateLeft( d, 30);
259 		 a += s3(b, c, d, e,w[ 54]);  c = rotateLeft( c, 30);
260 		 e += s3(a, b, c, d,w[ 55]);  b = rotateLeft( b, 30);
261 		 d += s3(e, a, b, c,w[ 56]);  a = rotateLeft( a, 30);
262 		 c += s3(d, e, a, b,w[ 57]);  e = rotateLeft( e, 30);
263 		state58.save(a, b, c, d, e);
264 		 b += s3(c, d, e, a,w[ 58]);  d = rotateLeft( d, 30);
265 		 a += s3(b, c, d, e,w[ 59]);  c = rotateLeft( c, 30);
266 
267 		 e += s4(a, b, c, d,w[ 60]);  b = rotateLeft( b, 30);
268 		 d += s4(e, a, b, c,w[ 61]);  a = rotateLeft( a, 30);
269 		 c += s4(d, e, a, b,w[ 62]);  e = rotateLeft( e, 30);
270 		 b += s4(c, d, e, a,w[ 63]);  d = rotateLeft( d, 30);
271 		 a += s4(b, c, d, e,w[ 64]);  c = rotateLeft( c, 30);
272 		state65.save(a, b, c, d, e);
273 		 e += s4(a, b, c, d,w[ 65]);  b = rotateLeft( b, 30);
274 		 d += s4(e, a, b, c,w[ 66]);  a = rotateLeft( a, 30);
275 		 c += s4(d, e, a, b,w[ 67]);  e = rotateLeft( e, 30);
276 		 b += s4(c, d, e, a,w[ 68]);  d = rotateLeft( d, 30);
277 		 a += s4(b, c, d, e,w[ 69]);  c = rotateLeft( c, 30);
278 		 e += s4(a, b, c, d,w[ 70]);  b = rotateLeft( b, 30);
279 		 d += s4(e, a, b, c,w[ 71]);  a = rotateLeft( a, 30);
280 		 c += s4(d, e, a, b,w[ 72]);  e = rotateLeft( e, 30);
281 		 b += s4(c, d, e, a,w[ 73]);  d = rotateLeft( d, 30);
282 		 a += s4(b, c, d, e,w[ 74]);  c = rotateLeft( c, 30);
283 		 e += s4(a, b, c, d,w[ 75]);  b = rotateLeft( b, 30);
284 		 d += s4(e, a, b, c,w[ 76]);  a = rotateLeft( a, 30);
285 		 c += s4(d, e, a, b,w[ 77]);  e = rotateLeft( e, 30);
286 		 b += s4(c, d, e, a,w[ 78]);  d = rotateLeft( d, 30);
287 		 a += s4(b, c, d, e,w[ 79]);  c = rotateLeft( c, 30);
288 
289 		// @formatter:on
290 		h.save(h.a + a, h.b + b, h.c + c, h.d + d, h.e + e);
291 	}
292 
293 	private void recompress(int t) {
294 		State s;
295 		switch (t) {
296 		case 58:
297 			s = state58;
298 			break;
299 		case 65:
300 			s = state65;
301 			break;
302 		default:
303 			throw new IllegalStateException();
304 		}
305 		int a = s.a, b = s.b, c = s.c, d = s.d, e = s.e;
306 
307 		// @formatter:off
308 	  if (t == 65) {
309 		{ c = rotateRight( c, 30);  a -= s4(b, c, d, e,w2[ 64]);}
310 		{ d = rotateRight( d, 30);  b -= s4(c, d, e, a,w2[ 63]);}
311 		{ e = rotateRight( e, 30);  c -= s4(d, e, a, b,w2[ 62]);}
312 		{ a = rotateRight( a, 30);  d -= s4(e, a, b, c,w2[ 61]);}
313 		{ b = rotateRight( b, 30);  e -= s4(a, b, c, d,w2[ 60]);}
314 
315 		{ c = rotateRight( c, 30);  a -= s3(b, c, d, e,w2[ 59]);}
316 		{ d = rotateRight( d, 30);  b -= s3(c, d, e, a,w2[ 58]);}
317 	  }
318 		{ e = rotateRight( e, 30);  c -= s3(d, e, a, b,w2[ 57]);}
319 		{ a = rotateRight( a, 30);  d -= s3(e, a, b, c,w2[ 56]);}
320 		{ b = rotateRight( b, 30);  e -= s3(a, b, c, d,w2[ 55]);}
321 		{ c = rotateRight( c, 30);  a -= s3(b, c, d, e,w2[ 54]);}
322 		{ d = rotateRight( d, 30);  b -= s3(c, d, e, a,w2[ 53]);}
323 		{ e = rotateRight( e, 30);  c -= s3(d, e, a, b,w2[ 52]);}
324 		{ a = rotateRight( a, 30);  d -= s3(e, a, b, c,w2[ 51]);}
325 		{ b = rotateRight( b, 30);  e -= s3(a, b, c, d,w2[ 50]);}
326 		{ c = rotateRight( c, 30);  a -= s3(b, c, d, e,w2[ 49]);}
327 		{ d = rotateRight( d, 30);  b -= s3(c, d, e, a,w2[ 48]);}
328 		{ e = rotateRight( e, 30);  c -= s3(d, e, a, b,w2[ 47]);}
329 		{ a = rotateRight( a, 30);  d -= s3(e, a, b, c,w2[ 46]);}
330 		{ b = rotateRight( b, 30);  e -= s3(a, b, c, d,w2[ 45]);}
331 		{ c = rotateRight( c, 30);  a -= s3(b, c, d, e,w2[ 44]);}
332 		{ d = rotateRight( d, 30);  b -= s3(c, d, e, a,w2[ 43]);}
333 		{ e = rotateRight( e, 30);  c -= s3(d, e, a, b,w2[ 42]);}
334 		{ a = rotateRight( a, 30);  d -= s3(e, a, b, c,w2[ 41]);}
335 		{ b = rotateRight( b, 30);  e -= s3(a, b, c, d,w2[ 40]);}
336 
337 		{ c = rotateRight( c, 30);  a -= s2(b, c, d, e,w2[ 39]);}
338 		{ d = rotateRight( d, 30);  b -= s2(c, d, e, a,w2[ 38]);}
339 		{ e = rotateRight( e, 30);  c -= s2(d, e, a, b,w2[ 37]);}
340 		{ a = rotateRight( a, 30);  d -= s2(e, a, b, c,w2[ 36]);}
341 		{ b = rotateRight( b, 30);  e -= s2(a, b, c, d,w2[ 35]);}
342 		{ c = rotateRight( c, 30);  a -= s2(b, c, d, e,w2[ 34]);}
343 		{ d = rotateRight( d, 30);  b -= s2(c, d, e, a,w2[ 33]);}
344 		{ e = rotateRight( e, 30);  c -= s2(d, e, a, b,w2[ 32]);}
345 		{ a = rotateRight( a, 30);  d -= s2(e, a, b, c,w2[ 31]);}
346 		{ b = rotateRight( b, 30);  e -= s2(a, b, c, d,w2[ 30]);}
347 		{ c = rotateRight( c, 30);  a -= s2(b, c, d, e,w2[ 29]);}
348 		{ d = rotateRight( d, 30);  b -= s2(c, d, e, a,w2[ 28]);}
349 		{ e = rotateRight( e, 30);  c -= s2(d, e, a, b,w2[ 27]);}
350 		{ a = rotateRight( a, 30);  d -= s2(e, a, b, c,w2[ 26]);}
351 		{ b = rotateRight( b, 30);  e -= s2(a, b, c, d,w2[ 25]);}
352 		{ c = rotateRight( c, 30);  a -= s2(b, c, d, e,w2[ 24]);}
353 		{ d = rotateRight( d, 30);  b -= s2(c, d, e, a,w2[ 23]);}
354 		{ e = rotateRight( e, 30);  c -= s2(d, e, a, b,w2[ 22]);}
355 		{ a = rotateRight( a, 30);  d -= s2(e, a, b, c,w2[ 21]);}
356 		{ b = rotateRight( b, 30);  e -= s2(a, b, c, d,w2[ 20]);}
357 
358 		{ c = rotateRight( c, 30);  a -= s1(b, c, d, e,w2[ 19]);}
359 		{ d = rotateRight( d, 30);  b -= s1(c, d, e, a,w2[ 18]);}
360 		{ e = rotateRight( e, 30);  c -= s1(d, e, a, b,w2[ 17]);}
361 		{ a = rotateRight( a, 30);  d -= s1(e, a, b, c,w2[ 16]);}
362 		{ b = rotateRight( b, 30);  e -= s1(a, b, c, d,w2[ 15]);}
363 		{ c = rotateRight( c, 30);  a -= s1(b, c, d, e,w2[ 14]);}
364 		{ d = rotateRight( d, 30);  b -= s1(c, d, e, a,w2[ 13]);}
365 		{ e = rotateRight( e, 30);  c -= s1(d, e, a, b,w2[ 12]);}
366 		{ a = rotateRight( a, 30);  d -= s1(e, a, b, c,w2[ 11]);}
367 		{ b = rotateRight( b, 30);  e -= s1(a, b, c, d,w2[ 10]);}
368 		{ c = rotateRight( c, 30);  a -= s1(b, c, d, e,w2[ 9]);}
369 		{ d = rotateRight( d, 30);  b -= s1(c, d, e, a,w2[ 8]);}
370 		{ e = rotateRight( e, 30);  c -= s1(d, e, a, b,w2[ 7]);}
371 		{ a = rotateRight( a, 30);  d -= s1(e, a, b, c,w2[ 6]);}
372 		{ b = rotateRight( b, 30);  e -= s1(a, b, c, d,w2[ 5]);}
373 		{ c = rotateRight( c, 30);  a -= s1(b, c, d, e,w2[ 4]);}
374 		{ d = rotateRight( d, 30);  b -= s1(c, d, e, a,w2[ 3]);}
375 		{ e = rotateRight( e, 30);  c -= s1(d, e, a, b,w2[ 2]);}
376 		{ a = rotateRight( a, 30);  d -= s1(e, a, b, c,w2[ 1]);}
377 		{ b = rotateRight( b, 30);  e -= s1(a, b, c, d,w2[ 0]);}
378 
379 		hIn.save(a, b, c, d, e);
380 		a = s.a; b = s.b; c = s.c; d = s.d; e = s.e;
381 
382 	  if (t == 58) {
383 		{ b += s3(c, d, e, a,w2[ 58]);  d = rotateLeft( d, 30);}
384 		{ a += s3(b, c, d, e,w2[ 59]);  c = rotateLeft( c, 30);}
385 
386 		{ e += s4(a, b, c, d,w2[ 60]);  b = rotateLeft( b, 30);}
387 		{ d += s4(e, a, b, c,w2[ 61]);  a = rotateLeft( a, 30);}
388 		{ c += s4(d, e, a, b,w2[ 62]);  e = rotateLeft( e, 30);}
389 		{ b += s4(c, d, e, a,w2[ 63]);  d = rotateLeft( d, 30);}
390 		{ a += s4(b, c, d, e,w2[ 64]);  c = rotateLeft( c, 30);}
391 	  }
392 		{ e += s4(a, b, c, d,w2[ 65]);  b = rotateLeft( b, 30);}
393 		{ d += s4(e, a, b, c,w2[ 66]);  a = rotateLeft( a, 30);}
394 		{ c += s4(d, e, a, b,w2[ 67]);  e = rotateLeft( e, 30);}
395 		{ b += s4(c, d, e, a,w2[ 68]);  d = rotateLeft( d, 30);}
396 		{ a += s4(b, c, d, e,w2[ 69]);  c = rotateLeft( c, 30);}
397 		{ e += s4(a, b, c, d,w2[ 70]);  b = rotateLeft( b, 30);}
398 		{ d += s4(e, a, b, c,w2[ 71]);  a = rotateLeft( a, 30);}
399 		{ c += s4(d, e, a, b,w2[ 72]);  e = rotateLeft( e, 30);}
400 		{ b += s4(c, d, e, a,w2[ 73]);  d = rotateLeft( d, 30);}
401 		{ a += s4(b, c, d, e,w2[ 74]);  c = rotateLeft( c, 30);}
402 		{ e += s4(a, b, c, d,w2[ 75]);  b = rotateLeft( b, 30);}
403 		{ d += s4(e, a, b, c,w2[ 76]);  a = rotateLeft( a, 30);}
404 		{ c += s4(d, e, a, b,w2[ 77]);  e = rotateLeft( e, 30);}
405 		{ b += s4(c, d, e, a,w2[ 78]);  d = rotateLeft( d, 30);}
406 		{ a += s4(b, c, d, e,w2[ 79]);  c = rotateLeft( c, 30);}
407 
408 		// @formatter:on
409 		hTmp.save(hIn.a + a, hIn.b + b, hIn.c + c, hIn.d + d, hIn.e + e);
410 	}
411 
412 	private static int s1(int a, int b, int c, int d, int w_t) {
413 		return rotateLeft(a, 5)
414 				// f: 0 <= t <= 19
415 				+ ((b & c) | ((~b) & d))
416 				+ 0x5A827999 + w_t;
417 	}
418 
419 	private static int s2(int a, int b, int c, int d, int w_t) {
420 		return rotateLeft(a, 5)
421 				// f: 20 <= t <= 39
422 				+ (b ^ c ^ d)
423 				+ 0x6ED9EBA1 + w_t;
424 	}
425 
426 	private static int s3(int a, int b, int c, int d, int w_t) {
427 		return rotateLeft(a, 5)
428 				// f: 40 <= t <= 59
429 				+ ((b & c) | (b & d) | (c & d))
430 				+ 0x8F1BBCDC + w_t;
431 	}
432 
433 	private static int s4(int a, int b, int c, int d, int w_t) {
434 		return rotateLeft(a, 5)
435 				// f: 60 <= t <= 79
436 				+ (b ^ c ^ d)
437 				+ 0xCA62C1D6 + w_t;
438 	}
439 
440 	private static boolean eq(State q, State r) {
441 		return q.a == r.a
442 				&& q.b == r.b
443 				&& q.c == r.c
444 				&& q.d == r.d
445 				&& q.e == r.e;
446 	}
447 
448 	private void finish() {
449 		int bufferLen = (int) (length & 63);
450 		if (bufferLen > 55) {
451 			// Last block is too small; pad, compress, pad another block.
452 			buffer[bufferLen++] = (byte) 0x80;
453 			Arrays.fill(buffer, bufferLen, 64, (byte) 0);
454 			compress(buffer, 0);
455 			Arrays.fill(buffer, 0, 56, (byte) 0);
456 		} else {
457 			// Last block can hold padding and length.
458 			buffer[bufferLen++] = (byte) 0x80;
459 			Arrays.fill(buffer, bufferLen, 56, (byte) 0);
460 		}
461 
462 		// SHA-1 appends the length of the message in bits after the
463 		// padding block (above). Here length is in bytes. Multiply by
464 		// 8 by shifting by 3 as part of storing the 64 bit byte length
465 		// into the two words expected in the trailer.
466 		NB.encodeInt32(buffer, 56, (int) (length >>> (32 - 3)));
467 		NB.encodeInt32(buffer, 60, (int) (length << 3));
468 		compress(buffer, 0);
469 
470 		if (foundCollision) {
471 			ObjectId id = h.toObjectId();
472 			LOG.warn(MessageFormat.format(JGitText.get().sha1CollisionDetected,
473 					id.name()));
474 			throw new Sha1CollisionException(id);
475 		}
476 	}
477 
478 	/**
479 	 * Finish the digest and return the resulting hash.
480 	 * <p>
481 	 * Once {@code digest()} is called, this instance should be discarded.
482 	 *
483 	 * @return the bytes for the resulting hash.
484 	 * @throws org.eclipse.jgit.util.sha1.Sha1CollisionException
485 	 *             if a collision was detected and safeHash is false.
486 	 */
487 	public byte[] digest() throws Sha1CollisionException {
488 		finish();
489 
490 		byte[] b = new byte[20];
491 		NB.encodeInt32(b, 0, h.a);
492 		NB.encodeInt32(b, 4, h.b);
493 		NB.encodeInt32(b, 8, h.c);
494 		NB.encodeInt32(b, 12, h.d);
495 		NB.encodeInt32(b, 16, h.e);
496 		return b;
497 	}
498 
499 	/**
500 	 * Finish the digest and return the resulting hash.
501 	 * <p>
502 	 * Once {@code digest()} is called, this instance should be discarded.
503 	 *
504 	 * @return the ObjectId for the resulting hash.
505 	 * @throws org.eclipse.jgit.util.sha1.Sha1CollisionException
506 	 *             if a collision was detected and safeHash is false.
507 	 */
508 	public ObjectId toObjectId() throws Sha1CollisionException {
509 		finish();
510 		return h.toObjectId();
511 	}
512 
513 	/**
514 	 * Finish the digest and return the resulting hash.
515 	 * <p>
516 	 * Once {@code digest()} is called, this instance should be discarded.
517 	 *
518 	 * @param id
519 	 *            destination to copy the digest to.
520 	 * @throws org.eclipse.jgit.util.sha1.Sha1CollisionException
521 	 *             if a collision was detected and safeHash is false.
522 	 */
523 	public void digest(MutableObjectId id) throws Sha1CollisionException {
524 		finish();
525 		id.set(h.a, h.b, h.c, h.d, h.e);
526 	}
527 
528 	/**
529 	 * Check if a collision was detected.
530 	 *
531 	 * <p>
532 	 * This method only returns an accurate result after the digest was obtained
533 	 * through {@link #digest()}, {@link #digest(MutableObjectId)} or
534 	 * {@link #toObjectId()}, as the hashing function must finish processing to
535 	 * know the final state.
536 	 *
537 	 * @return {@code true} if a likely collision was detected.
538 	 */
539 	public boolean hasCollision() {
540 		return foundCollision;
541 	}
542 
543 	/**
544 	 * Reset this instance to compute another hash.
545 	 *
546 	 * @return {@code this}.
547 	 */
548 	public SHA1 reset() {
549 		h.init();
550 		length = 0;
551 		foundCollision = false;
552 		return this;
553 	}
554 
555 	private static final class State {
556 		int a;
557 		int b;
558 		int c;
559 		int d;
560 		int e;
561 
562 		final void init() {
563 			// Magic initialization constants defined by FIPS180.
564 			save(0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0);
565 		}
566 
567 		final void save(int a1, int b1, int c1, int d1, int e1) {
568 			a = a1;
569 			b = b1;
570 			c = c1;
571 			d = d1;
572 			e = e1;
573 		}
574 
575 		ObjectId toObjectId() {
576 			return new ObjectId(a, b, c, d, e);
577 		}
578 	}
579 }