1 /*
2 * Copyright (C) 2015, Matthias Sohn <matthias.sohn@sap.com>
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.lfs.lib;
45
46 import java.io.IOException;
47 import java.io.OutputStream;
48 import java.io.Writer;
49 import java.nio.ByteBuffer;
50
51 import org.eclipse.jgit.lib.AnyObjectId;
52 import org.eclipse.jgit.util.NB;
53
54 /**
55 * A (possibly mutable) SHA-256 abstraction.
56 * <p>
57 * If this is an instance of
58 * {@link org.eclipse.jgit.lfs.lib.MutableLongObjectId} the concept of equality
59 * with this instance can alter at any time, if this instance is modified to
60 * represent a different object name.
61 *
62 * Ported to SHA-256 from {@link org.eclipse.jgit.lib.AnyObjectId}
63 *
64 * @since 4.3
65 */
66 public abstract class AnyLongObjectId implements Comparable<AnyLongObjectId> {
67
68 /**
69 * Compare two object identifier byte sequences for equality.
70 *
71 * @param firstObjectId
72 * the first identifier to compare. Must not be null.
73 * @param secondObjectId
74 * the second identifier to compare. Must not be null.
75 * @return true if the two identifiers are the same.
76 */
77 public static boolean equals(final AnyLongObjectId firstObjectId,
78 final AnyLongObjectId secondObjectId) {
79 if (firstObjectId == secondObjectId)
80 return true;
81
82 // We test word 2 first as odds are someone already used our
83 // word 1 as a hash code, and applying that came up with these
84 // two instances we are comparing for equality. Therefore the
85 // first two words are very likely to be identical. We want to
86 // break away from collisions as quickly as possible.
87 //
88 return firstObjectId.w2 == secondObjectId.w2
89 && firstObjectId.w3 == secondObjectId.w3
90 && firstObjectId.w4 == secondObjectId.w4
91 && firstObjectId.w1 == secondObjectId.w1;
92 }
93
94 long w1;
95
96 long w2;
97
98 long w3;
99
100 long w4;
101
102 /**
103 * Get the first 8 bits of the LongObjectId.
104 *
105 * This is a faster version of {@code getByte(0)}.
106 *
107 * @return a discriminator usable for a fan-out style map. Returned values
108 * are unsigned and thus are in the range [0,255] rather than the
109 * signed byte range of [-128, 127].
110 */
111 public final int getFirstByte() {
112 return (int) (w1 >>> 56);
113 }
114
115 /**
116 * Get the second 8 bits of the LongObjectId.
117 *
118 * @return a discriminator usable for a fan-out style map. Returned values
119 * are unsigned and thus are in the range [0,255] rather than the
120 * signed byte range of [-128, 127].
121 */
122 public final int getSecondByte() {
123 return (int) ((w1 >>> 48) & 0xff);
124 }
125
126 /**
127 * Get any byte from the LongObjectId.
128 *
129 * Callers hard-coding {@code getByte(0)} should instead use the much faster
130 * special case variant {@link #getFirstByte()}.
131 *
132 * @param index
133 * index of the byte to obtain from the raw form of the
134 * LongObjectId. Must be in range [0,
135 * {@link org.eclipse.jgit.lfs.lib.Constants#LONG_OBJECT_ID_LENGTH}).
136 * @return the value of the requested byte at {@code index}. Returned values
137 * are unsigned and thus are in the range [0,255] rather than the
138 * signed byte range of [-128, 127].
139 * @throws java.lang.ArrayIndexOutOfBoundsException
140 * {@code index} is less than 0, equal to
141 * {@link org.eclipse.jgit.lfs.lib.Constants#LONG_OBJECT_ID_LENGTH},
142 * or greater than
143 * {@link org.eclipse.jgit.lfs.lib.Constants#LONG_OBJECT_ID_LENGTH}.
144 */
145 public final int getByte(int index) {
146 long w;
147 switch (index >> 3) {
148 case 0:
149 w = w1;
150 break;
151 case 1:
152 w = w2;
153 break;
154 case 2:
155 w = w3;
156 break;
157 case 3:
158 w = w4;
159 break;
160 default:
161 throw new ArrayIndexOutOfBoundsException(index);
162 }
163
164 return (int) ((w >>> (8 * (15 - (index & 15)))) & 0xff);
165 }
166
167 /**
168 * {@inheritDoc}
169 *
170 * Compare this LongObjectId to another and obtain a sort ordering.
171 */
172 @Override
173 public final int compareTo(AnyLongObjectId other) {
174 if (this == other)
175 return 0;
176
177 int cmp;
178
179 cmp = NB.compareUInt64(w1, other.w1);
180 if (cmp != 0)
181 return cmp;
182
183 cmp = NB.compareUInt64(w2, other.w2);
184 if (cmp != 0)
185 return cmp;
186
187 cmp = NB.compareUInt64(w3, other.w3);
188 if (cmp != 0)
189 return cmp;
190
191 return NB.compareUInt64(w4, other.w4);
192 }
193
194 /**
195 * Compare this LongObjectId to a network-byte-order LongObjectId.
196 *
197 * @param bs
198 * array containing the other LongObjectId in network byte order.
199 * @param p
200 * position within {@code bs} to start the compare at. At least
201 * 32 bytes, starting at this position are required.
202 * @return a negative integer, zero, or a positive integer as this object is
203 * less than, equal to, or greater than the specified object.
204 */
205 public final int compareTo(byte[] bs, int p) {
206 int cmp;
207
208 cmp = NB.compareUInt64(w1, NB.decodeInt64(bs, p));
209 if (cmp != 0)
210 return cmp;
211
212 cmp = NB.compareUInt64(w2, NB.decodeInt64(bs, p + 8));
213 if (cmp != 0)
214 return cmp;
215
216 cmp = NB.compareUInt64(w3, NB.decodeInt64(bs, p + 16));
217 if (cmp != 0)
218 return cmp;
219
220 return NB.compareUInt64(w4, NB.decodeInt64(bs, p + 24));
221 }
222
223 /**
224 * Compare this LongObjectId to a network-byte-order LongObjectId.
225 *
226 * @param bs
227 * array containing the other LongObjectId in network byte order.
228 * @param p
229 * position within {@code bs} to start the compare at. At least 4
230 * longs, starting at this position are required.
231 * @return a negative integer, zero, or a positive integer as this object is
232 * less than, equal to, or greater than the specified object.
233 */
234 public final int compareTo(long[] bs, int p) {
235 int cmp;
236
237 cmp = NB.compareUInt64(w1, bs[p]);
238 if (cmp != 0)
239 return cmp;
240
241 cmp = NB.compareUInt64(w2, bs[p + 1]);
242 if (cmp != 0)
243 return cmp;
244
245 cmp = NB.compareUInt64(w3, bs[p + 2]);
246 if (cmp != 0)
247 return cmp;
248
249 return NB.compareUInt64(w4, bs[p + 3]);
250 }
251
252 /**
253 * Tests if this LongObjectId starts with the given abbreviation.
254 *
255 * @param abbr
256 * the abbreviation.
257 * @return true if this LongObjectId begins with the abbreviation; else
258 * false.
259 */
260 public boolean startsWith(AbbreviatedLongObjectId abbr) {
261 return abbr.prefixCompare(this) == 0;
262 }
263
264 /** {@inheritDoc} */
265 @Override
266 public final int hashCode() {
267 return (int) (w1 >> 32);
268 }
269
270 /**
271 * Determine if this LongObjectId has exactly the same value as another.
272 *
273 * @param other
274 * the other id to compare to. May be null.
275 * @return true only if both LongObjectIds have identical bits.
276 */
277 public final boolean equals(AnyLongObjectId other) {
278 return other != null ? equals(this, other) : false;
279 }
280
281 /** {@inheritDoc} */
282 @Override
283 public final boolean equals(Object o) {
284 if (o instanceof AnyLongObjectId)
285 return equals((AnyLongObjectId) o);
286 else
287 return false;
288 }
289
290 /**
291 * Copy this LongObjectId to an output writer in raw binary.
292 *
293 * @param w
294 * the buffer to copy to. Must be in big endian order.
295 */
296 public void copyRawTo(ByteBuffer w) {
297 w.putLong(w1);
298 w.putLong(w2);
299 w.putLong(w3);
300 w.putLong(w4);
301 }
302
303 /**
304 * Copy this LongObjectId to a byte array.
305 *
306 * @param b
307 * the buffer to copy to.
308 * @param o
309 * the offset within b to write at.
310 */
311 public void copyRawTo(byte[] b, int o) {
312 NB.encodeInt64(b, o, w1);
313 NB.encodeInt64(b, o + 8, w2);
314 NB.encodeInt64(b, o + 16, w3);
315 NB.encodeInt64(b, o + 24, w4);
316 }
317
318 /**
319 * Copy this LongObjectId to an long array.
320 *
321 * @param b
322 * the buffer to copy to.
323 * @param o
324 * the offset within b to write at.
325 */
326 public void copyRawTo(long[] b, int o) {
327 b[o] = w1;
328 b[o + 1] = w2;
329 b[o + 2] = w3;
330 b[o + 3] = w4;
331 }
332
333 /**
334 * Copy this LongObjectId to an output writer in raw binary.
335 *
336 * @param w
337 * the stream to write to.
338 * @throws java.io.IOException
339 * the stream writing failed.
340 */
341 public void copyRawTo(OutputStream w) throws IOException {
342 writeRawLong(w, w1);
343 writeRawLong(w, w2);
344 writeRawLong(w, w3);
345 writeRawLong(w, w4);
346 }
347
348 private static void writeRawLong(OutputStream w, long v)
349 throws IOException {
350 w.write((int) (v >>> 56));
351 w.write((int) (v >>> 48));
352 w.write((int) (v >>> 40));
353 w.write((int) (v >>> 32));
354 w.write((int) (v >>> 24));
355 w.write((int) (v >>> 16));
356 w.write((int) (v >>> 8));
357 w.write((int) v);
358 }
359
360 /**
361 * Copy this LongObjectId to an output writer in hex format.
362 *
363 * @param w
364 * the stream to copy to.
365 * @throws java.io.IOException
366 * the stream writing failed.
367 */
368 public void copyTo(OutputStream w) throws IOException {
369 w.write(toHexByteArray());
370 }
371
372 /**
373 * Copy this LongObjectId to a byte array in hex format.
374 *
375 * @param b
376 * the buffer to copy to.
377 * @param o
378 * the offset within b to write at.
379 */
380 public void copyTo(byte[] b, int o) {
381 formatHexByte(b, o + 0, w1);
382 formatHexByte(b, o + 16, w2);
383 formatHexByte(b, o + 32, w3);
384 formatHexByte(b, o + 48, w4);
385 }
386
387 /**
388 * Copy this LongObjectId to a ByteBuffer in hex format.
389 *
390 * @param b
391 * the buffer to copy to.
392 */
393 public void copyTo(ByteBuffer b) {
394 b.put(toHexByteArray());
395 }
396
397 private byte[] toHexByteArray() {
398 final byte[] dst = new byte[Constants.LONG_OBJECT_ID_STRING_LENGTH];
399 formatHexByte(dst, 0, w1);
400 formatHexByte(dst, 16, w2);
401 formatHexByte(dst, 32, w3);
402 formatHexByte(dst, 48, w4);
403 return dst;
404 }
405
406 private static final byte[] hexbyte = { '0', '1', '2', '3', '4', '5', '6',
407 '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
408
409 private static void formatHexByte(byte[] dst, int p, long w) {
410 int o = p + 15;
411 while (o >= p && w != 0) {
412 dst[o--] = hexbyte[(int) (w & 0xf)];
413 w >>>= 4;
414 }
415 while (o >= p)
416 dst[o--] = '0';
417 }
418
419 /**
420 * Copy this LongObjectId to an output writer in hex format.
421 *
422 * @param w
423 * the stream to copy to.
424 * @throws java.io.IOException
425 * the stream writing failed.
426 */
427 public void copyTo(Writer w) throws IOException {
428 w.write(toHexCharArray());
429 }
430
431 /**
432 * Copy this LongObjectId to an output writer in hex format.
433 *
434 * @param tmp
435 * temporary char array to buffer construct into before writing.
436 * Must be at least large enough to hold 2 digits for each byte
437 * of object id (64 characters or larger).
438 * @param w
439 * the stream to copy to.
440 * @throws java.io.IOException
441 * the stream writing failed.
442 */
443 public void copyTo(char[] tmp, Writer w) throws IOException {
444 toHexCharArray(tmp);
445 w.write(tmp, 0, Constants.LONG_OBJECT_ID_STRING_LENGTH);
446 }
447
448 /**
449 * Copy this LongObjectId to a StringBuilder in hex format.
450 *
451 * @param tmp
452 * temporary char array to buffer construct into before writing.
453 * Must be at least large enough to hold 2 digits for each byte
454 * of object id (64 characters or larger).
455 * @param w
456 * the string to append onto.
457 */
458 public void copyTo(char[] tmp, StringBuilder w) {
459 toHexCharArray(tmp);
460 w.append(tmp, 0, Constants.LONG_OBJECT_ID_STRING_LENGTH);
461 }
462
463 char[] toHexCharArray() {
464 final char[] dst = new char[Constants.LONG_OBJECT_ID_STRING_LENGTH];
465 toHexCharArray(dst);
466 return dst;
467 }
468
469 private void toHexCharArray(char[] dst) {
470 formatHexChar(dst, 0, w1);
471 formatHexChar(dst, 16, w2);
472 formatHexChar(dst, 32, w3);
473 formatHexChar(dst, 48, w4);
474 }
475
476 private static final char[] hexchar = { '0', '1', '2', '3', '4', '5', '6',
477 '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
478
479 static void formatHexChar(char[] dst, int p, long w) {
480 int o = p + 15;
481 while (o >= p && w != 0) {
482 dst[o--] = hexchar[(int) (w & 0xf)];
483 w >>>= 4;
484 }
485 while (o >= p)
486 dst[o--] = '0';
487 }
488
489 /** {@inheritDoc} */
490 @SuppressWarnings("nls")
491 @Override
492 public String toString() {
493 return "AnyLongObjectId[" + name() + "]";
494 }
495
496 /**
497 * Get string form of the SHA-256
498 *
499 * @return string form of the SHA-256, in lower case hexadecimal.
500 */
501 public final String name() {
502 return new String(toHexCharArray());
503 }
504
505 /**
506 * Get string form of the SHA-256
507 *
508 * @return string form of the SHA-256, in lower case hexadecimal.
509 */
510 public final String getName() {
511 return name();
512 }
513
514 /**
515 * Return an abbreviation (prefix) of this object SHA-256.
516 * <p>
517 * This implementation does not guarantee uniqueness. Callers should instead
518 * use
519 * {@link org.eclipse.jgit.lib.ObjectReader#abbreviate(AnyObjectId, int)} to
520 * obtain a unique abbreviation within the scope of a particular object
521 * database.
522 *
523 * @param len
524 * length of the abbreviated string.
525 * @return SHA-256 abbreviation.
526 */
527 public AbbreviatedLongObjectId abbreviate(int len) {
528 final long a = AbbreviatedLongObjectId.mask(len, 1, w1);
529 final long b = AbbreviatedLongObjectId.mask(len, 2, w2);
530 final long c = AbbreviatedLongObjectId.mask(len, 3, w3);
531 final long d = AbbreviatedLongObjectId.mask(len, 4, w4);
532 return new AbbreviatedLongObjectId(len, a, b, c, d);
533 }
534
535 /**
536 * Obtain an immutable copy of this current object.
537 * <p>
538 * Only returns <code>this</code> if this instance is an unsubclassed
539 * instance of {@link org.eclipse.jgit.lfs.lib.LongObjectId}; otherwise a
540 * new instance is returned holding the same value.
541 * <p>
542 * This method is useful to shed any additional memory that may be tied to
543 * the subclass, yet retain the unique identity of the object id for future
544 * lookups within maps and repositories.
545 *
546 * @return an immutable copy, using the smallest memory footprint possible.
547 */
548 public final LongObjectId copy() {
549 if (getClass() == LongObjectId.class)
550 return (LongObjectId) this;
551 return new LongObjectId(this);
552 }
553
554 /**
555 * Obtain an immutable copy of this current object.
556 * <p>
557 * See {@link #copy()} if <code>this</code> is a possibly subclassed (but
558 * immutable) identity and the application needs a lightweight identity
559 * <i>only</i> reference.
560 *
561 * @return an immutable copy. May be <code>this</code> if this is already an
562 * immutable instance.
563 */
564 public abstract LongObjectId toObjectId();
565 }