AbbreviatedLongObjectId.java

  1. /*
  2.  * Copyright (C) 2015, Matthias Sohn <matthias.sohn@sap.com> 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.  */

  11. package org.eclipse.jgit.lfs.lib;

  13. import java.io.Serializable;
  14. import java.text.MessageFormat;

  16. import org.eclipse.jgit.lfs.errors.InvalidLongObjectIdException;
  17. import org.eclipse.jgit.lfs.internal.LfsText;
  18. import org.eclipse.jgit.util.NB;
  19. import org.eclipse.jgit.util.RawParseUtils;

  21. /**
  22.  * A prefix abbreviation of an {@link org.eclipse.jgit.lfs.lib.LongObjectId}.
  23.  * <p>
  24.  * Enable abbreviating SHA-256 strings used by Git LFS, using sufficient leading
  25.  * digits from the LongObjectId name to still be unique within the repository
  26.  * the string was generated from. These ids are likely to be unique for a useful
  27.  * period of time, especially if they contain at least 6-10 hex digits.
  28.  * <p>
  29.  * This class converts the hex string into a binary form, to make it more
  30.  * efficient for matching against an object.
  31.  *
  32.  * Ported to SHA-256 from {@link org.eclipse.jgit.lib.AbbreviatedObjectId}
  33.  *
  34.  * @since 4.3
  35.  */
  36. public final class AbbreviatedLongObjectId implements Serializable {
  37.     private static final long serialVersionUID = 1L;

  39.     /**
  40.      * Test a string of characters to verify it is a hex format.
  41.      * <p>
  42.      * If true the string can be parsed with {@link #fromString(String)}.
  43.      *
  44.      * @param id
  45.      *            the string to test.
  46.      * @return true if the string can converted into an AbbreviatedObjectId.
  47.      */
  48.     public static final boolean isId(String id) {
  49.         if (id.length() < 2
  50.                 || Constants.LONG_OBJECT_ID_STRING_LENGTH < id.length())
  51.             return false;
  52.         try {
  53.             for (int i = 0; i < id.length(); i++)
  54.                 RawParseUtils.parseHexInt4((byte) id.charAt(i));
  55.             return true;
  56.         } catch (ArrayIndexOutOfBoundsException e) {
  57.             return false;
  58.         }
  59.     }

  61.     /**
  62.      * Convert an AbbreviatedObjectId from hex characters (US-ASCII).
  63.      *
  64.      * @param buf
  65.      *            the US-ASCII buffer to read from.
  66.      * @param offset
  67.      *            position to read the first character from.
  68.      * @param end
  69.      *            one past the last position to read (<code>end-offset</code> is
  70.      *            the length of the string).
  71.      * @return the converted object id.
  72.      */
  73.     public static final AbbreviatedLongObjectId fromString(final byte[] buf,
  74.             final int offset, final int end) {
  75.         if (end - offset > Constants.LONG_OBJECT_ID_STRING_LENGTH)
  76.             throw new IllegalArgumentException(MessageFormat.format(
  77.                             LfsText.get().invalidLongIdLength,
  78.                     Integer.valueOf(end - offset),
  79.                     Integer.valueOf(Constants.LONG_OBJECT_ID_STRING_LENGTH)));
  80.         return fromHexString(buf, offset, end);
  81.     }

  83.     /**
  84.      * Convert an AbbreviatedObjectId from an
  85.      * {@link org.eclipse.jgit.lib.AnyObjectId}.
  86.      * <p>
  87.      * This method copies over all bits of the Id, and is therefore complete
  88.      * (see {@link #isComplete()}).
  89.      *
  90.      * @param id
  91.      *            the {@link org.eclipse.jgit.lib.ObjectId} to convert from.
  92.      * @return the converted object id.
  93.      */
  94.     public static final AbbreviatedLongObjectId fromLongObjectId(
  95.             AnyLongObjectId id) {
  96.         return new AbbreviatedLongObjectId(
  97.                 Constants.LONG_OBJECT_ID_STRING_LENGTH, id.w1, id.w2, id.w3,
  98.                 id.w4);
  99.     }

  101.     /**
  102.      * Convert an AbbreviatedLongObjectId from hex characters.
  103.      *
  104.      * @param str
  105.      *            the string to read from. Must be &lt;= 64 characters.
  106.      * @return the converted object id.
  107.      */
  108.     public static final AbbreviatedLongObjectId fromString(String str) {
  109.         if (str.length() > Constants.LONG_OBJECT_ID_STRING_LENGTH)
  110.             throw new IllegalArgumentException(
  111.                     MessageFormat.format(LfsText.get().invalidLongId, str));
  112.         final byte[] b = org.eclipse.jgit.lib.Constants.encodeASCII(str);
  113.         return fromHexString(b, 0, b.length);
  114.     }

  116.     private static final AbbreviatedLongObjectId fromHexString(final byte[] bs,
  117.             int ptr, final int end) {
  118.         try {
  119.             final long a = hexUInt64(bs, ptr, end);
  120.             final long b = hexUInt64(bs, ptr + 16, end);
  121.             final long c = hexUInt64(bs, ptr + 32, end);
  122.             final long d = hexUInt64(bs, ptr + 48, end);
  123.             return new AbbreviatedLongObjectId(end - ptr, a, b, c, d);
  124.         } catch (ArrayIndexOutOfBoundsException e) {
  125.             InvalidLongObjectIdException e1 = new InvalidLongObjectIdException(
  126.                     bs, ptr, end - ptr);
  127.             e1.initCause(e);
  128.             throw e1;
  129.         }
  130.     }

  132.     private static final long hexUInt64(final byte[] bs, int p, final int end) {
  133.         if (16 <= end - p)
  134.             return RawParseUtils.parseHexInt64(bs, p);

  136.         long r = 0;
  137.         int n = 0;
  138.         while (n < 16 && p < end) {
  139.             r <<= 4;
  140.             r |= RawParseUtils.parseHexInt4(bs[p++]);
  141.             n++;
  142.         }
  143.         return r << ((16 - n) * 4);
  144.     }

  146.     static long mask(int nibbles, long word, long v) {
  147.         final long b = (word - 1) * 16;
  148.         if (b + 16 <= nibbles) {
  149.             // We have all of the bits required for this word.
  150.             //
  151.             return v;
  152.         }

  154.         if (nibbles <= b) {
  155.             // We have none of the bits required for this word.
  156.             //
  157.             return 0;
  158.         }

  160.         final long s = 64 - (nibbles - b) * 4;
  161.         return (v >>> s) << s;
  162.     }

  164.     /** Number of half-bytes used by this id. */
  165.     final int nibbles;

  167.     final long w1;

  169.     final long w2;

  171.     final long w3;

  173.     final long w4;

  175.     AbbreviatedLongObjectId(final int n, final long new_1, final long new_2,
  176.             final long new_3, final long new_4) {
  177.         nibbles = n;
  178.         w1 = new_1;
  179.         w2 = new_2;
  180.         w3 = new_3;
  181.         w4 = new_4;
  182.     }

  184.     /**
  185.      * Get length
  186.      *
  187.      * @return number of hex digits appearing in this id.
  188.      */
  189.     public int length() {
  190.         return nibbles;
  191.     }

  193.     /**
  194.      * Check if this id is complete
  195.      *
  196.      * @return true if this ObjectId is actually a complete id.
  197.      */
  198.     public boolean isComplete() {
  199.         return length() == Constants.LONG_OBJECT_ID_STRING_LENGTH;
  200.     }

  202.     /**
  203.      * Convert to LongObjectId
  204.      *
  205.      * @return a complete ObjectId; null if {@link #isComplete()} is false.
  206.      */
  207.     public LongObjectId toLongObjectId() {
  208.         return isComplete() ? new LongObjectId(w1, w2, w3, w4) : null;
  209.     }

  211.     /**
  212.      * Compares this abbreviation to a full object id.
  213.      *
  214.      * @param other
  215.      *            the other object id.
  216.      * @return &lt;0 if this abbreviation names an object that is less than
  217.      *         <code>other</code>; 0 if this abbreviation exactly matches the
  218.      *         first {@link #length()} digits of <code>other.name()</code>;
  219.      *         &gt;0 if this abbreviation names an object that is after
  220.      *         <code>other</code>.
  221.      */
  222.     public final int prefixCompare(AnyLongObjectId other) {
  223.         int cmp;

  225.         cmp = NB.compareUInt64(w1, mask(1, other.w1));
  226.         if (cmp != 0)
  227.             return cmp;

  229.         cmp = NB.compareUInt64(w2, mask(2, other.w2));
  230.         if (cmp != 0)
  231.             return cmp;

  233.         cmp = NB.compareUInt64(w3, mask(3, other.w3));
  234.         if (cmp != 0)
  235.             return cmp;

  237.         return NB.compareUInt64(w4, mask(4, other.w4));
  238.     }

  240.     /**
  241.      * Compare this abbreviation to a network-byte-order LongObjectId.
  242.      *
  243.      * @param bs
  244.      *            array containing the other LongObjectId in network byte order.
  245.      * @param p
  246.      *            position within {@code bs} to start the compare at. At least
  247.      *            32 bytes, starting at this position are required.
  248.      * @return &lt;0 if this abbreviation names an object that is less than
  249.      *         <code>other</code>; 0 if this abbreviation exactly matches the
  250.      *         first {@link #length()} digits of <code>other.name()</code>;
  251.      *         &gt;0 if this abbreviation names an object that is after
  252.      *         <code>other</code>.
  253.      */
  254.     public final int prefixCompare(byte[] bs, int p) {
  255.         int cmp;

  257.         cmp = NB.compareUInt64(w1, mask(1, NB.decodeInt64(bs, p)));
  258.         if (cmp != 0)
  259.             return cmp;

  261.         cmp = NB.compareUInt64(w2, mask(2, NB.decodeInt64(bs, p + 8)));
  262.         if (cmp != 0)
  263.             return cmp;

  265.         cmp = NB.compareUInt64(w3, mask(3, NB.decodeInt64(bs, p + 16)));
  266.         if (cmp != 0)
  267.             return cmp;

  269.         return NB.compareUInt64(w4, mask(4, NB.decodeInt64(bs, p + 24)));
  270.     }

  272.     /**
  273.      * Compare this abbreviation to a network-byte-order LongObjectId.
  274.      *
  275.      * @param bs
  276.      *            array containing the other LongObjectId in network byte order.
  277.      * @param p
  278.      *            position within {@code bs} to start the compare at. At least 4
  279.      *            longs, starting at this position are required.
  280.      * @return &lt;0 if this abbreviation names an object that is less than
  281.      *         <code>other</code>; 0 if this abbreviation exactly matches the
  282.      *         first {@link #length()} digits of <code>other.name()</code>;
  283.      *         &gt;0 if this abbreviation names an object that is after
  284.      *         <code>other</code>.
  285.      */
  286.     public final int prefixCompare(long[] bs, int p) {
  287.         int cmp;

  289.         cmp = NB.compareUInt64(w1, mask(1, bs[p]));
  290.         if (cmp != 0)
  291.             return cmp;

  293.         cmp = NB.compareUInt64(w2, mask(2, bs[p + 1]));
  294.         if (cmp != 0)
  295.             return cmp;

  297.         cmp = NB.compareUInt64(w3, mask(3, bs[p + 2]));
  298.         if (cmp != 0)
  299.             return cmp;

  301.         return NB.compareUInt64(w4, mask(4, bs[p + 3]));
  302.     }

  304.     /**
  305.      * Get the first byte of this id
  306.      *
  307.      * @return value for a fan-out style map, only valid of length &gt;= 2.
  308.      */
  309.     public final int getFirstByte() {
  310.         return (int) (w1 >>> 56);
  311.     }

  313.     private long mask(long word, long v) {
  314.         return mask(nibbles, word, v);
  315.     }

  317.     /** {@inheritDoc} */
  318.     @Override
  319.     public int hashCode() {
  320.         return (int) (w1 >> 32);
  321.     }

  323.     /** {@inheritDoc} */
  324.     @Override
  325.     public boolean equals(Object o) {
  326.         if (o instanceof AbbreviatedLongObjectId) {
  327.             final AbbreviatedLongObjectId b = (AbbreviatedLongObjectId) o;
  328.             return nibbles == b.nibbles && w1 == b.w1 && w2 == b.w2
  329.                     && w3 == b.w3 && w4 == b.w4;
  330.         }
  331.         return false;
  332.     }

  334.     /**
  335.      * <p>name.</p>
  336.      *
  337.      * @return string form of the abbreviation, in lower case hexadecimal.
  338.      */
  339.     public final String name() {
  340.         final char[] b = new char[Constants.LONG_OBJECT_ID_STRING_LENGTH];

  342.         AnyLongObjectId.formatHexChar(b, 0, w1);
  343.         if (nibbles <= 16)
  344.             return new String(b, 0, nibbles);

  346.         AnyLongObjectId.formatHexChar(b, 16, w2);
  347.         if (nibbles <= 32)
  348.             return new String(b, 0, nibbles);

  350.         AnyLongObjectId.formatHexChar(b, 32, w3);
  351.         if (nibbles <= 48)
  352.             return new String(b, 0, nibbles);

  354.         AnyLongObjectId.formatHexChar(b, 48, w4);
  355.         return new String(b, 0, nibbles);
  356.     }

  358.     /** {@inheritDoc} */
  359.     @SuppressWarnings("nls")
  360.     @Override
  361.     public String toString() {
  362.         return "AbbreviatedLongObjectId[" + name() + "]"; //$NON-NLS-1$
  363.     }
  364. }
Created with JaCoCo 0.8.7.202105040129