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