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