001/*
002 * Copyright (C) 2011 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.primitives;
016
017import static com.google.common.base.Preconditions.checkArgument;
018import static com.google.common.base.Preconditions.checkNotNull;
019import static com.google.common.base.Preconditions.checkPositionIndexes;
020
021import com.google.common.annotations.Beta;
022import com.google.common.annotations.GwtCompatible;
023import com.google.errorprone.annotations.CanIgnoreReturnValue;
024import java.math.BigInteger;
025import java.util.Arrays;
026import java.util.Comparator;
027
028/**
029 * Static utility methods pertaining to {@code long} primitives that interpret values as
030 * <i>unsigned</i> (that is, any negative value {@code x} is treated as the positive value {@code
031 * 2^64 + x}). The methods for which signedness is not an issue are in {@link Longs}, as well as
032 * signed versions of methods for which signedness is an issue.
033 *
034 * <p>In addition, this class provides several static methods for converting a {@code long} to a
035 * {@code String} and a {@code String} to a {@code long} that treat the {@code long} as an unsigned
036 * number.
037 *
038 * <p>Users of these utilities must be <i>extremely careful</i> not to mix up signed and unsigned
039 * {@code long} values. When possible, it is recommended that the {@link UnsignedLong} wrapper class
040 * be used, at a small efficiency penalty, to enforce the distinction in the type system.
041 *
042 * <p>See the Guava User Guide article on <a
043 * href="https://github.com/google/guava/wiki/PrimitivesExplained#unsigned-support">unsigned
044 * primitive utilities</a>.
045 *
046 * @author Louis Wasserman
047 * @author Brian Milch
048 * @author Colin Evans
049 * @since 10.0
050 */
051@Beta
052@GwtCompatible
053public final class UnsignedLongs {
054  private UnsignedLongs() {}
055
056  public static final long MAX_VALUE = -1L; // Equivalent to 2^64 - 1
057
058  /**
059   * A (self-inverse) bijection which converts the ordering on unsigned longs to the ordering on
060   * longs, that is, {@code a <= b} as unsigned longs if and only if {@code flip(a) <= flip(b)} as
061   * signed longs.
062   */
063  private static long flip(long a) {
064    return a ^ Long.MIN_VALUE;
065  }
066
067  /**
068   * Compares the two specified {@code long} values, treating them as unsigned values between {@code
069   * 0} and {@code 2^64 - 1} inclusive.
070   *
071   * <p><b>Java 8 users:</b> use {@link Long#compareUnsigned(long, long)} instead.
072   *
073   * @param a the first unsigned {@code long} to compare
074   * @param b the second unsigned {@code long} to compare
075   * @return a negative value if {@code a} is less than {@code b}; a positive value if {@code a} is
076   *     greater than {@code b}; or zero if they are equal
077   */
078  public static int compare(long a, long b) {
079    return Longs.compare(flip(a), flip(b));
080  }
081
082  /**
083   * Returns the least value present in {@code array}, treating values as unsigned.
084   *
085   * @param array a <i>nonempty</i> array of unsigned {@code long} values
086   * @return the value present in {@code array} that is less than or equal to every other value in
087   *     the array according to {@link #compare}
088   * @throws IllegalArgumentException if {@code array} is empty
089   */
090  public static long min(long... array) {
091    checkArgument(array.length > 0);
092    long min = flip(array[0]);
093    for (int i = 1; i < array.length; i++) {
094      long next = flip(array[i]);
095      if (next < min) {
096        min = next;
097      }
098    }
099    return flip(min);
100  }
101
102  /**
103   * Returns the greatest value present in {@code array}, treating values as unsigned.
104   *
105   * @param array a <i>nonempty</i> array of unsigned {@code long} values
106   * @return the value present in {@code array} that is greater than or equal to every other value
107   *     in the array according to {@link #compare}
108   * @throws IllegalArgumentException if {@code array} is empty
109   */
110  public static long max(long... array) {
111    checkArgument(array.length > 0);
112    long max = flip(array[0]);
113    for (int i = 1; i < array.length; i++) {
114      long next = flip(array[i]);
115      if (next > max) {
116        max = next;
117      }
118    }
119    return flip(max);
120  }
121
122  /**
123   * Returns a string containing the supplied unsigned {@code long} values separated by {@code
124   * separator}. For example, {@code join("-", 1, 2, 3)} returns the string {@code "1-2-3"}.
125   *
126   * @param separator the text that should appear between consecutive values in the resulting string
127   *     (but not at the start or end)
128   * @param array an array of unsigned {@code long} values, possibly empty
129   */
130  public static String join(String separator, long... array) {
131    checkNotNull(separator);
132    if (array.length == 0) {
133      return "";
134    }
135
136    // For pre-sizing a builder, just get the right order of magnitude
137    StringBuilder builder = new StringBuilder(array.length * 5);
138    builder.append(toString(array[0]));
139    for (int i = 1; i < array.length; i++) {
140      builder.append(separator).append(toString(array[i]));
141    }
142    return builder.toString();
143  }
144
145  /**
146   * Returns a comparator that compares two arrays of unsigned {@code long} values <a
147   * href="http://en.wikipedia.org/wiki/Lexicographical_order">lexicographically</a>. That is, it
148   * compares, using {@link #compare(long, long)}), the first pair of values that follow any common
149   * prefix, or when one array is a prefix of the other, treats the shorter array as the lesser. For
150   * example, {@code [] < [1L] < [1L, 2L] < [2L] < [1L << 63]}.
151   *
152   * <p>The returned comparator is inconsistent with {@link Object#equals(Object)} (since arrays
153   * support only identity equality), but it is consistent with {@link Arrays#equals(long[],
154   * long[])}.
155   */
156  public static Comparator<long[]> lexicographicalComparator() {
157    return LexicographicalComparator.INSTANCE;
158  }
159
160  enum LexicographicalComparator implements Comparator<long[]> {
161    INSTANCE;
162
163    @Override
164    public int compare(long[] left, long[] right) {
165      int minLength = Math.min(left.length, right.length);
166      for (int i = 0; i < minLength; i++) {
167        if (left[i] != right[i]) {
168          return UnsignedLongs.compare(left[i], right[i]);
169        }
170      }
171      return left.length - right.length;
172    }
173
174    @Override
175    public String toString() {
176      return "UnsignedLongs.lexicographicalComparator()";
177    }
178  }
179
180  /**
181   * Sorts the array, treating its elements as unsigned 64-bit integers.
182   *
183   * @since 23.1
184   */
185  public static void sort(long[] array) {
186    checkNotNull(array);
187    sort(array, 0, array.length);
188  }
189
190  /**
191   * Sorts the array between {@code fromIndex} inclusive and {@code toIndex} exclusive, treating its
192   * elements as unsigned 64-bit integers.
193   *
194   * @since 23.1
195   */
196  public static void sort(long[] array, int fromIndex, int toIndex) {
197    checkNotNull(array);
198    checkPositionIndexes(fromIndex, toIndex, array.length);
199    for (int i = fromIndex; i < toIndex; i++) {
200      array[i] = flip(array[i]);
201    }
202    Arrays.sort(array, fromIndex, toIndex);
203    for (int i = fromIndex; i < toIndex; i++) {
204      array[i] = flip(array[i]);
205    }
206  }
207
208  /**
209   * Sorts the elements of {@code array} in descending order, interpreting them as unsigned 64-bit
210   * integers.
211   *
212   * @since 23.1
213   */
214  public static void sortDescending(long[] array) {
215    checkNotNull(array);
216    sortDescending(array, 0, array.length);
217  }
218
219  /**
220   * Sorts the elements of {@code array} between {@code fromIndex} inclusive and {@code toIndex}
221   * exclusive in descending order, interpreting them as unsigned 64-bit integers.
222   *
223   * @since 23.1
224   */
225  public static void sortDescending(long[] array, int fromIndex, int toIndex) {
226    checkNotNull(array);
227    checkPositionIndexes(fromIndex, toIndex, array.length);
228    for (int i = fromIndex; i < toIndex; i++) {
229      array[i] ^= Long.MAX_VALUE;
230    }
231    Arrays.sort(array, fromIndex, toIndex);
232    for (int i = fromIndex; i < toIndex; i++) {
233      array[i] ^= Long.MAX_VALUE;
234    }
235  }
236
237  /**
238   * Returns dividend / divisor, where the dividend and divisor are treated as unsigned 64-bit
239   * quantities.
240   *
241   * <p><b>Java 8 users:</b> use {@link Long#divideUnsigned(long, long)} instead.
242   *
243   * @param dividend the dividend (numerator)
244   * @param divisor the divisor (denominator)
245   * @throws ArithmeticException if divisor is 0
246   */
247  public static long divide(long dividend, long divisor) {
248    if (divisor < 0) { // i.e., divisor >= 2^63:
249      if (compare(dividend, divisor) < 0) {
250        return 0; // dividend < divisor
251      } else {
252        return 1; // dividend >= divisor
253      }
254    }
255
256    // Optimization - use signed division if dividend < 2^63
257    if (dividend >= 0) {
258      return dividend / divisor;
259    }
260
261    /*
262     * Otherwise, approximate the quotient, check, and correct if necessary. Our approximation is
263     * guaranteed to be either exact or one less than the correct value. This follows from fact that
264     * floor(floor(x)/i) == floor(x/i) for any real x and integer i != 0. The proof is not quite
265     * trivial.
266     */
267    long quotient = ((dividend >>> 1) / divisor) << 1;
268    long rem = dividend - quotient * divisor;
269    return quotient + (compare(rem, divisor) >= 0 ? 1 : 0);
270  }
271
272  /**
273   * Returns dividend % divisor, where the dividend and divisor are treated as unsigned 64-bit
274   * quantities.
275   *
276   * <p><b>Java 8 users:</b> use {@link Long#remainderUnsigned(long, long)} instead.
277   *
278   * @param dividend the dividend (numerator)
279   * @param divisor the divisor (denominator)
280   * @throws ArithmeticException if divisor is 0
281   * @since 11.0
282   */
283  public static long remainder(long dividend, long divisor) {
284    if (divisor < 0) { // i.e., divisor >= 2^63:
285      if (compare(dividend, divisor) < 0) {
286        return dividend; // dividend < divisor
287      } else {
288        return dividend - divisor; // dividend >= divisor
289      }
290    }
291
292    // Optimization - use signed modulus if dividend < 2^63
293    if (dividend >= 0) {
294      return dividend % divisor;
295    }
296
297    /*
298     * Otherwise, approximate the quotient, check, and correct if necessary. Our approximation is
299     * guaranteed to be either exact or one less than the correct value. This follows from the fact
300     * that floor(floor(x)/i) == floor(x/i) for any real x and integer i != 0. The proof is not
301     * quite trivial.
302     */
303    long quotient = ((dividend >>> 1) / divisor) << 1;
304    long rem = dividend - quotient * divisor;
305    return rem - (compare(rem, divisor) >= 0 ? divisor : 0);
306  }
307
308  /**
309   * Returns the unsigned {@code long} value represented by the given decimal string.
310   *
311   * <p><b>Java 8 users:</b> use {@link Long#parseUnsignedLong(String)} instead.
312   *
313   * @throws NumberFormatException if the string does not contain a valid unsigned {@code long}
314   *     value
315   * @throws NullPointerException if {@code string} is null (in contrast to {@link
316   *     Long#parseLong(String)})
317   */
318  @CanIgnoreReturnValue
319  public static long parseUnsignedLong(String string) {
320    return parseUnsignedLong(string, 10);
321  }
322
323  /**
324   * Returns the unsigned {@code long} value represented by a string with the given radix.
325   *
326   * <p><b>Java 8 users:</b> use {@link Long#parseUnsignedLong(String, int)} instead.
327   *
328   * @param string the string containing the unsigned {@code long} representation to be parsed.
329   * @param radix the radix to use while parsing {@code string}
330   * @throws NumberFormatException if the string does not contain a valid unsigned {@code long} with
331   *     the given radix, or if {@code radix} is not between {@link Character#MIN_RADIX} and {@link
332   *     Character#MAX_RADIX}.
333   * @throws NullPointerException if {@code string} is null (in contrast to {@link
334   *     Long#parseLong(String)})
335   */
336  @CanIgnoreReturnValue
337  public static long parseUnsignedLong(String string, int radix) {
338    checkNotNull(string);
339    if (string.length() == 0) {
340      throw new NumberFormatException("empty string");
341    }
342    if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) {
343      throw new NumberFormatException("illegal radix: " + radix);
344    }
345
346    int maxSafePos = ParseOverflowDetection.maxSafeDigits[radix] - 1;
347    long value = 0;
348    for (int pos = 0; pos < string.length(); pos++) {
349      int digit = Character.digit(string.charAt(pos), radix);
350      if (digit == -1) {
351        throw new NumberFormatException(string);
352      }
353      if (pos > maxSafePos && ParseOverflowDetection.overflowInParse(value, digit, radix)) {
354        throw new NumberFormatException("Too large for unsigned long: " + string);
355      }
356      value = (value * radix) + digit;
357    }
358
359    return value;
360  }
361
362  /**
363   * Returns the unsigned {@code long} value represented by the given string.
364   *
365   * <p>Accepts a decimal, hexadecimal, or octal number given by specifying the following prefix:
366   *
367   * <ul>
368   *   <li>{@code 0x}<i>HexDigits</i>
369   *   <li>{@code 0X}<i>HexDigits</i>
370   *   <li>{@code #}<i>HexDigits</i>
371   *   <li>{@code 0}<i>OctalDigits</i>
372   * </ul>
373   *
374   * @throws NumberFormatException if the string does not contain a valid unsigned {@code long}
375   *     value
376   * @since 13.0
377   */
378  @CanIgnoreReturnValue
379  public static long decode(String stringValue) {
380    ParseRequest request = ParseRequest.fromString(stringValue);
381
382    try {
383      return parseUnsignedLong(request.rawValue, request.radix);
384    } catch (NumberFormatException e) {
385      NumberFormatException decodeException =
386          new NumberFormatException("Error parsing value: " + stringValue);
387      decodeException.initCause(e);
388      throw decodeException;
389    }
390  }
391
392  /*
393   * We move the static constants into this class so ProGuard can inline UnsignedLongs entirely
394   * unless the user is actually calling a parse method.
395   */
396  private static final class ParseOverflowDetection {
397    private ParseOverflowDetection() {}
398
399    // calculated as 0xffffffffffffffff / radix
400    static final long[] maxValueDivs = new long[Character.MAX_RADIX + 1];
401    static final int[] maxValueMods = new int[Character.MAX_RADIX + 1];
402    static final int[] maxSafeDigits = new int[Character.MAX_RADIX + 1];
403
404    static {
405      BigInteger overflow = new BigInteger("10000000000000000", 16);
406      for (int i = Character.MIN_RADIX; i <= Character.MAX_RADIX; i++) {
407        maxValueDivs[i] = divide(MAX_VALUE, i);
408        maxValueMods[i] = (int) remainder(MAX_VALUE, i);
409        maxSafeDigits[i] = overflow.toString(i).length() - 1;
410      }
411    }
412
413    /**
414     * Returns true if (current * radix) + digit is a number too large to be represented by an
415     * unsigned long. This is useful for detecting overflow while parsing a string representation of
416     * a number. Does not verify whether supplied radix is valid, passing an invalid radix will give
417     * undefined results or an ArrayIndexOutOfBoundsException.
418     */
419    static boolean overflowInParse(long current, int digit, int radix) {
420      if (current >= 0) {
421        if (current < maxValueDivs[radix]) {
422          return false;
423        }
424        if (current > maxValueDivs[radix]) {
425          return true;
426        }
427        // current == maxValueDivs[radix]
428        return (digit > maxValueMods[radix]);
429      }
430
431      // current < 0: high bit is set
432      return true;
433    }
434  }
435
436  /**
437   * Returns a string representation of x, where x is treated as unsigned.
438   *
439   * <p><b>Java 8 users:</b> use {@link Long#toUnsignedString(long)} instead.
440   */
441  public static String toString(long x) {
442    return toString(x, 10);
443  }
444
445  /**
446   * Returns a string representation of {@code x} for the given radix, where {@code x} is treated as
447   * unsigned.
448   *
449   * <p><b>Java 8 users:</b> use {@link Long#toUnsignedString(long, int)} instead.
450   *
451   * @param x the value to convert to a string.
452   * @param radix the radix to use while working with {@code x}
453   * @throws IllegalArgumentException if {@code radix} is not between {@link Character#MIN_RADIX}
454   *     and {@link Character#MAX_RADIX}.
455   */
456  public static String toString(long x, int radix) {
457    checkArgument(
458        radix >= Character.MIN_RADIX && radix <= Character.MAX_RADIX,
459        "radix (%s) must be between Character.MIN_RADIX and Character.MAX_RADIX",
460        radix);
461    if (x == 0) {
462      // Simply return "0"
463      return "0";
464    } else if (x > 0) {
465      return Long.toString(x, radix);
466    } else {
467      char[] buf = new char[64];
468      int i = buf.length;
469      if ((radix & (radix - 1)) == 0) {
470        // Radix is a power of two so we can avoid division.
471        int shift = Integer.numberOfTrailingZeros(radix);
472        int mask = radix - 1;
473        do {
474          buf[--i] = Character.forDigit(((int) x) & mask, radix);
475          x >>>= shift;
476        } while (x != 0);
477      } else {
478        // Separate off the last digit using unsigned division. That will leave
479        // a number that is nonnegative as a signed integer.
480        long quotient;
481        if ((radix & 1) == 0) {
482          // Fast path for the usual case where the radix is even.
483          quotient = (x >>> 1) / (radix >>> 1);
484        } else {
485          quotient = divide(x, radix);
486        }
487        long rem = x - quotient * radix;
488        buf[--i] = Character.forDigit((int) rem, radix);
489        x = quotient;
490        // Simple modulo/division approach
491        while (x > 0) {
492          buf[--i] = Character.forDigit((int) (x % radix), radix);
493          x /= radix;
494        }
495      }
496      // Generate string
497      return new String(buf, i, buf.length - i);
498    }
499  }
500}