Backport Long.divideUnsigned and Long.remainderUnsigned methods
These are only available on API 26 and newer, but the Kotlin compiler will emit references to these when using ULong.rem and ULong.div and targeting Java 8 bytecode.
Bug: 130408977
Test: Java8MethodsTest
Change-Id: I09e18880fb7e33c8e883f69428280049041f8151
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/Java8MethodRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/Java8MethodRewriter.java
index 646f24e..36a08cc 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/Java8MethodRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/Java8MethodRewriter.java
@@ -380,6 +380,14 @@
return new LongMethods(options, method, "sumImpl");
}
+ public static LongMethods divideUnsignedCode(InternalOptions options, DexMethod method) {
+ return new LongMethods(options, method, "divideUnsignedImpl");
+ }
+
+ public static LongMethods remainderUnsignedCode(InternalOptions options, DexMethod method) {
+ return new LongMethods(options, method, "remainderUnsignedImpl");
+ }
+
public static int hashCodeImpl(long i) {
return Long.valueOf(i).hashCode();
}
@@ -395,6 +403,78 @@
public static long sumImpl(long a, long b) {
return a + b;
}
+
+ public static long divideUnsignedImpl(long dividend, long divisor) {
+ // This implementation is adapted from Guava's UnsignedLongs.java and Longs.java.
+
+ if (divisor < 0) { // i.e., divisor >= 2^63:
+ // Reference implementation calls UnsignedLongs.compare(dividend, divisor) whose
+ // implementation is Longs.compare(UnsignedLong.flip(a), UnsignedLong.flip(b)). The
+ // implementations of flip() and compare() are inlined here instead.
+ long dividendFlipped = dividend ^ Long.MIN_VALUE;
+ long divisorFlipped = divisor ^ Long.MIN_VALUE;
+ if (dividendFlipped < divisorFlipped) {
+ return 0; // dividend < divisor
+ } else {
+ return 1; // dividend >= divisor
+ }
+ }
+
+ // Optimization - use signed division if dividend < 2^63
+ if (dividend >= 0) {
+ return dividend / divisor;
+ }
+
+ // Otherwise, approximate the quotient, check, and correct if necessary. Our approximation is
+ // guaranteed to be either exact or one less than the correct value. This follows from the
+ // fact that floor(floor(x)/i) == floor(x/i) for any real x and integer i != 0. The proof is
+ // not quite trivial.
+ long quotient = ((dividend >>> 1) / divisor) << 1;
+ long rem = dividend - quotient * divisor;
+
+ // Reference implementation calls UnsignedLongs.compare(rem, divisor) whose
+ // implementation is Longs.compare(UnsignedLong.flip(a), UnsignedLong.flip(b)). The
+ // implementations of flip() and compare() are inlined here instead.
+ long remFlipped = rem ^ Long.MIN_VALUE;
+ long divisorFlipped = divisor ^ Long.MIN_VALUE;
+ return quotient + (remFlipped >= divisorFlipped ? 1 : 0);
+ }
+
+ public static long remainderUnsignedImpl(long dividend, long divisor) {
+ // This implementation is adapted from Guava's UnsignedLongs.java and Longs.java.
+
+ if (divisor < 0) { // i.e., divisor >= 2^63:
+ // Reference implementation calls UnsignedLongs.compare(dividend, divisor) whose
+ // implementation is Longs.compare(UnsignedLong.flip(a), UnsignedLong.flip(b)). The
+ // implementations of flip() and compare() are inlined here instead.
+ long dividendFlipped = dividend ^ Long.MIN_VALUE;
+ long divisorFlipped = divisor ^ Long.MIN_VALUE;
+ if (dividendFlipped < divisorFlipped) {
+ return dividend; // dividend < divisor
+ } else {
+ return dividend - divisor; // dividend >= divisor
+ }
+ }
+
+ // Optimization - use signed modulus if dividend < 2^63
+ if (dividend >= 0) {
+ return dividend % divisor;
+ }
+
+ // Otherwise, approximate the quotient, check, and correct if necessary. Our approximation is
+ // guaranteed to be either exact or one less than the correct value. This follows from the
+ // fact that floor(floor(x)/i) == floor(x/i) for any real x and integer i != 0. The proof is
+ // not quite trivial.
+ long quotient = ((dividend >>> 1) / divisor) << 1;
+ long rem = dividend - quotient * divisor;
+
+ // Reference implementation calls UnsignedLongs.compare(rem, divisor) whose
+ // implementation is Longs.compare(UnsignedLong.flip(a), UnsignedLong.flip(b)). The
+ // implementations of flip() and compare() are inlined here instead.
+ long remFlipped = rem ^ Long.MIN_VALUE;
+ long divisorFlipped = divisor ^ Long.MIN_VALUE;
+ return rem - (remFlipped >= divisorFlipped ? divisor : 0);
+ }
}
private static final class CharacterMethods extends TemplateMethodCode {
@@ -581,6 +661,19 @@
addOrGetMethod(clazz, method)
.put(proto, new MethodGenerator(LongMethods::sumCode, clazz, method, proto));
+ // long Long.divideUnsigned(long a, long b)
+ method = factory.createString("divideUnsigned");
+ proto = factory.createProto(factory.longType, factory.longType, factory.longType);
+ addOrGetMethod(clazz, method)
+ .put(proto, new MethodGenerator(LongMethods::divideUnsignedCode, clazz, method, proto));
+
+ // long Long.remainderUnsigned(long a, long b)
+ method = factory.createString("remainderUnsigned");
+ proto = factory.createProto(factory.longType, factory.longType, factory.longType);
+ addOrGetMethod(clazz, method)
+ .put(proto,
+ new MethodGenerator(LongMethods::remainderUnsignedCode, clazz, method, proto));
+
// Character
clazz = factory.boxedCharDescriptor;
diff --git a/src/test/java/com/android/tools/r8/desugar/Java8MethodsTest.java b/src/test/java/com/android/tools/r8/desugar/Java8MethodsTest.java
index e8fc973..29a8cc9 100644
--- a/src/test/java/com/android/tools/r8/desugar/Java8MethodsTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/Java8MethodsTest.java
@@ -146,14 +146,18 @@
}
}
- long[] aLongs = new long[]{42L, 1L, -1L, Long.MAX_VALUE, Long.MIN_VALUE};
- long[] bLongs = new long[]{43L, 2L, -2L, Long.MAX_VALUE, Long.MIN_VALUE};
+ long[] aLongs = new long[]{42L, 1L, -1L, Integer.MIN_VALUE, Integer.MAX_VALUE,
+ Long.MAX_VALUE, Long.MIN_VALUE};
+ long[] bLongs = new long[]{43L, 2L, -2L, Integer.MIN_VALUE, Integer.MAX_VALUE,
+ Long.MAX_VALUE, Long.MIN_VALUE};
for (long aLong : aLongs) {
System.out.println(Long.hashCode(aLong));
for (long bLong : bLongs) {
System.out.println(Long.max(aLong, bLong));
System.out.println(Long.min(aLong, bLong));
System.out.println(Long.sum(aLong, bLong));
+ System.out.println(Long.divideUnsigned(aLong, bLong));
+ System.out.println(Long.remainderUnsigned(aLong, bLong));
}
}
