org.spearce.jgit/src/org/spearce/jgit/lib/AbbreviatedObjectId.java

   1 /*
   2  * Copyright (C) 2008, Google Inc.
   3  *
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or
   7  * without modification, are permitted provided that the following
   8  * conditions are met:
   9  *
  10  * - Redistributions of source code must retain the above copyright
  11  *   notice, this list of conditions and the following disclaimer.
  12  *
  13  * - Redistributions in binary form must reproduce the above
  14  *   copyright notice, this list of conditions and the following
  15  *   disclaimer in the documentation and/or other materials provided
  16  *   with the distribution.
  17  *
  18  * - Neither the name of the Git Development Community nor the
  19  *   names of its contributors may be used to endorse or promote
  20  *   products derived from this software without specific prior
  21  *   written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  24  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  25  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  26  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  28  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  29  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  30  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  31  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  32  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  33  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  34  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  35  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36  */
  37
  38 package org.spearce.jgit.lib;
  39
  40 import java.io.UnsupportedEncodingException;
  41
  42 import org.spearce.jgit.util.NB;
  43
  44 /**
  45  * A prefix abbreviation of an {@link ObjectId}.
  46  * <p>
  47  * Sometimes Git produces abbreviated SHA-1 strings, using sufficient leading
  48  * digits from the ObjectId name to still be unique within the repository the
  49  * string was generated from. These ids are likely to be unique for a useful
  50  * period of time, especially if they contain at least 6-10 hex digits.
  51  * <p>
  52  * This class converts the hex string into a binary form, to make it more
  53  * efficient for matching against an object.
  54  */
  55 public class AbbreviatedObjectId {
  56         /**
  57          * Convert an AbbreviatedObjectId from hex characters (US-ASCII).
  58          *
  59          * @param buf
  60          *            the US-ASCII buffer to read from.
  61          * @param offset
  62          *            position to read the first character from.
  63          * @param end
  64          *            one past the last position to read (<code>end-offset</code> is
  65          *            the length of the string).
  66          * @return the converted object id.
  67          */
  68         public static final AbbreviatedObjectId fromString(final byte[] buf,
  69                         final int offset, final int end) {
  70                 if (end - offset > AnyObjectId.STR_LEN)
  71                         throw new IllegalArgumentException("Invalid id");
  72                 return fromHexString(buf, offset, end);
  73         }
  74
  75         /**
  76          * Convert an AbbreviatedObjectId from hex characters.
  77          *
  78          * @param str
  79          *            the string to read from. Must be &lt;= 40 characters.
  80          * @return the converted object id.
  81          */
  82         public static final AbbreviatedObjectId fromString(final String str) {
  83                 if (str.length() > AnyObjectId.STR_LEN)
  84                         throw new IllegalArgumentException("Invalid id: " + str);
  85                 final byte[] b = Constants.encodeASCII(str);
  86                 return fromHexString(b, 0, b.length);
  87         }
  88
  89         private static final AbbreviatedObjectId fromHexString(final byte[] bs,
  90                         int ptr, final int end) {
  91                 try {
  92                         final int a = hexUInt32(bs, ptr, end);
  93                         final int b = hexUInt32(bs, ptr + 8, end);
  94                         final int c = hexUInt32(bs, ptr + 16, end);
  95                         final int d = hexUInt32(bs, ptr + 24, end);
  96                         final int e = hexUInt32(bs, ptr + 32, end);
  97                         return new AbbreviatedObjectId(end - ptr, a, b, c, d, e);
  98                 } catch (ArrayIndexOutOfBoundsException e1) {
  99                         try {
 100                                 final String str = new String(bs, ptr, end - ptr, "US-ASCII");
 101                                 throw new IllegalArgumentException("Invalid id: " + str);
 102                         } catch (UnsupportedEncodingException e2) {
 103                                 throw new IllegalArgumentException("Invalid id");
 104                         }
 105                 }
 106         }
 107
 108         private static final int hexUInt32(final byte[] bs, int p, final int end) {
 109                 if (8 <= end - p)
 110                         return AnyObjectId.hexUInt32(bs, p);
 111
 112                 int r = 0, n = 0;
 113                 while (n < 8 && p < end) {
 114                         final int v = AnyObjectId.fromhex[bs[p++]];
 115                         if (v < 0)
 116                                 throw new ArrayIndexOutOfBoundsException();
 117                         r <<= 4;
 118                         r |= v;
 119                         n++;
 120                 }
 121                 return r << (8 - n) * 4;
 122         }
 123
 124         static int mask(final int nibbles, final int word, final int v) {
 125                 final int b = (word - 1) * 8;
 126                 if (b + 8 <= nibbles) {
 127                         // We have all of the bits required for this word.
 128                         //
 129                         return v;
 130                 }
 131
 132                 if (nibbles < b) {
 133                         // We have none of the bits required for this word.
 134                         //
 135                         return 0;
 136                 }
 137
 138                 final int s = 32 - (nibbles - b) * 4;
 139                 return (v >>> s) << s;
 140         }
 141
 142         /** Number of half-bytes used by this id. */
 143         final int nibbles;
 144
 145         final int w1;
 146
 147         final int w2;
 148
 149         final int w3;
 150
 151         final int w4;
 152
 153         final int w5;
 154
 155         private AbbreviatedObjectId(final int n, final int new_1, final int new_2,
 156                         final int new_3, final int new_4, final int new_5) {
 157                 nibbles = n;
 158                 w1 = new_1;
 159                 w2 = new_2;
 160                 w3 = new_3;
 161                 w4 = new_4;
 162                 w5 = new_5;
 163         }
 164
 165         /** @return number of hex digits appearing in this id */
 166         public int length() {
 167                 return nibbles;
 168         }
 169
 170         /** @return true if this ObjectId is actually a complete id. */
 171         public boolean isComplete() {
 172                 return length() == AnyObjectId.RAW_LEN * 2;
 173         }
 174
 175         /** @return a complete ObjectId; null if {@link #isComplete()} is false */
 176         public ObjectId toObjectId() {
 177                 return isComplete() ? new ObjectId(w1, w2, w3, w4, w5) : null;
 178         }
 179
 180         /**
 181          * Compares this abbreviation to a full object id.
 182          *
 183          * @param other
 184          *            the other object id.
 185          * @return &lt;0 if this abbreviation names an object that is less than
 186          *         <code>other</code>; 0 if this abbreviation exactly matches the
 187          *         first {@link #length()} digits of <code>other.name()</code>;
 188          *         &gt;0 if this abbreviation names an object that is after
 189          *         <code>other</code>.
 190          */
 191         public int prefixCompare(final AnyObjectId other) {
 192                 int cmp;
 193
 194                 cmp = NB.compareUInt32(w1, mask(1, other.w1));
 195                 if (cmp != 0)
 196                         return cmp;
 197
 198                 cmp = NB.compareUInt32(w2, mask(2, other.w2));
 199                 if (cmp != 0)
 200                         return cmp;
 201
 202                 cmp = NB.compareUInt32(w3, mask(3, other.w3));
 203                 if (cmp != 0)
 204                         return cmp;
 205
 206                 cmp = NB.compareUInt32(w4, mask(4, other.w4));
 207                 if (cmp != 0)
 208                         return cmp;
 209
 210                 return NB.compareUInt32(w5, mask(5, other.w5));
 211         }
 212
 213         private int mask(final int word, final int v) {
 214                 return mask(nibbles, word, v);
 215         }
 216
 217         @Override
 218         public int hashCode() {
 219                 return w2;
 220         }
 221
 222         @Override
 223         public boolean equals(final Object o) {
 224                 if (o instanceof AbbreviatedObjectId) {
 225                         final AbbreviatedObjectId b = (AbbreviatedObjectId) o;
 226                         return nibbles == b.nibbles && w1 == b.w1 && w2 == b.w2
 227                                         && w3 == b.w3 && w4 == b.w4 && w5 == b.w5;
 228                 }
 229                 return false;
 230         }
 231
 232         /**
 233          * @return string form of the abbreviation, in lower case hexadecimal.
 234          */
 235         public final String name() {
 236                 final char[] b = new char[AnyObjectId.STR_LEN];
 237
 238                 AnyObjectId.formatHexChar(b, 0, w1);
 239                 if (nibbles <= 8)
 240                         return new String(b, 0, nibbles);
 241
 242                 AnyObjectId.formatHexChar(b, 8, w2);
 243                 if (nibbles <= 16)
 244                         return new String(b, 0, nibbles);
 245
 246                 AnyObjectId.formatHexChar(b, 16, w3);
 247                 if (nibbles <= 24)
 248                         return new String(b, 0, nibbles);
 249
 250                 AnyObjectId.formatHexChar(b, 24, w4);
 251                 if (nibbles <= 32)
 252                         return new String(b, 0, nibbles);
 253
 254                 AnyObjectId.formatHexChar(b, 32, w5);
 255                 return new String(b, 0, nibbles);
 256         }
 257
 258         @Override
 259         public String toString() {
 260                 return "AbbreviatedObjectId[" + name() + "]";
 261         }
 262 }