From 1c8799d5e487dd752a4df82170231a9c3e5ea97b Mon Sep 17 00:00:00 2001 From: Etienne Bergeron Date: Sun, 24 Nov 2013 00:17:35 -0500 Subject: [PATCH] [ctf] Simplify the logic of the unsigned long comparator. To understand this modification, let assume the "char 8-bits" domain. unsigned [0 .. 255] signed [-128 .. 127] By receiving the parameters encoded in a signed number, the method receives left: [0..127,-128..-1] (which represents [0..127,128..255]) right: [0..127,-128..-1] (which represents [0..127,128..255]) By definition (on an unconstrained domain), this assertion holds left < right <==> left + k < right + k Thus, the idea is to rotate the domain by k to allow a signed operator to be able to compare to full domain. In this case k must be -128. By rotating the domain, left and right range become [-128..-1,0..127], and are now comparable with the signed operator. Change-Id: I92b27ab00e8f14102a04e085ef807e211e39a7f0 Signed-off-by: Etienne Bergeron Reviewed-on: https://git.eclipse.org/r/18784 Tested-by: Hudson CI Reviewed-by: Mathieu Desnoyers Reviewed-by: Xavier Raynaud IP-Clean: Xavier Raynaud Tested-by: Xavier Raynaud --- .../ctf/core/tests/trace/UtilsTest.java | 25 ++++++++++- .../linuxtools/ctf/core/trace/Utils.java | 43 +++++++++---------- 2 files changed, 44 insertions(+), 24 deletions(-) diff --git a/org.eclipse.linuxtools.ctf.core.tests/src/org/eclipse/linuxtools/ctf/core/tests/trace/UtilsTest.java b/org.eclipse.linuxtools.ctf.core.tests/src/org/eclipse/linuxtools/ctf/core/tests/trace/UtilsTest.java index c2cbecc484..b3fbfdf478 100644 --- a/org.eclipse.linuxtools.ctf.core.tests/src/org/eclipse/linuxtools/ctf/core/tests/trace/UtilsTest.java +++ b/org.eclipse.linuxtools.ctf.core.tests/src/org/eclipse/linuxtools/ctf/core/tests/trace/UtilsTest.java @@ -88,8 +88,31 @@ public class UtilsTest { public void testUnsignedCompare() { long a = 1L; long b = 1L; + int result; - int result = Utils.unsignedCompare(a, b); + result = Utils.unsignedCompare(a, b); assertEquals(0, result); + + result = Utils.unsignedCompare(0L, 1L); + assertEquals(-1, result); + result = Utils.unsignedCompare(0xFFFFFFFFL, 0x100000000L); + assertEquals(-1, result); + result = Utils.unsignedCompare(-4L, -1L); + assertEquals(-1, result); + result = Utils.unsignedCompare(-0x80000000L, -1L); + assertEquals(-1, result); + result = Utils.unsignedCompare(0x7FFFFFFFFFFFFFFEL, 0x7FFFFFFFFFFFFFFFL); + assertEquals(-1, result); + + result = Utils.unsignedCompare(1L, 0L); + assertEquals(1, result); + result = Utils.unsignedCompare(0x100000000L, 0xFFFFFFFFL); + assertEquals(1, result); + result = Utils.unsignedCompare(-1L, -4L); + assertEquals(1, result); + result = Utils.unsignedCompare(-1L, -0x80000000L); + assertEquals(1, result); + result = Utils.unsignedCompare(0x7FFFFFFFFFFFFFFFL, 0x7FFFFFFFFFFFFFFEL); + assertEquals(1, result); } } \ No newline at end of file diff --git a/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/ctf/core/trace/Utils.java b/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/ctf/core/trace/Utils.java index d0cb11e3eb..69b9cfc291 100644 --- a/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/ctf/core/trace/Utils.java +++ b/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/ctf/core/trace/Utils.java @@ -59,31 +59,28 @@ public class Utils { // ------------------------------------------------------------------------ /** - * Unsigned long comparison. + * Performs an unsigned long comparison on two unsigned long numbers. * - * @param a - * First operand. - * @param b - * Second operand. - * @return -1 if a < b, 1 if a > b, 0 if a == b. + * @note As Java does not support unsigned types and arithmetic, parameters + * are received encoded as a signed long (two-complement) but the + * operation is an unsigned comparator. + * + * @param left + * Left operand of the comparator. + * @param right + * Right operand of the comparator. + * @return -1 if left < right, 1 if left > right, 0 if left == right. */ - public static int unsignedCompare(long a, long b) { - boolean aLeftBit = (a & (1 << (Long.SIZE - 1))) != 0; - boolean bLeftBit = (b & (1 << (Long.SIZE - 1))) != 0; - - if (aLeftBit && !bLeftBit) { - return 1; - } else if (!aLeftBit && bLeftBit) { - return -1; - } else { - if (a < b) { - return -1; - } else if (a > b) { - return 1; - } else { - return 0; - } - } + public static int unsignedCompare(long left, long right) { + /* + * This method assumes that the arithmetic overflow on signed + * integer wrap on a circular domain (modulo arithmetic in + * two-complement), which is the defined behavior in Java. + * + * This idea is to rotate the domain by the length of the negative + * space, and then use the signed operator. + */ + return Long.compare(left + Long.MIN_VALUE, right + Long.MIN_VALUE); } /** -- 2.34.1