You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2016/06/04 22:17:50 UTC
lucene-solr:branch_6x: LUCENE-7312: fix geo3d's encoding to always
round down
Repository: lucene-solr
Updated Branches:
refs/heads/branch_6x 3595b9ab2 -> 724f7424e
LUCENE-7312: fix geo3d's encoding to always round down
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/724f7424
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/724f7424
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/724f7424
Branch: refs/heads/branch_6x
Commit: 724f7424eaf19b59acce28edc61a40d6086a3d70
Parents: 3595b9a
Author: Mike McCandless <mi...@apache.org>
Authored: Sat Jun 4 18:16:04 2016 -0400
Committer: Mike McCandless <mi...@apache.org>
Committed: Sat Jun 4 18:17:21 2016 -0400
----------------------------------------------------------------------
lucene/CHANGES.txt | 3 ++
.../org/apache/lucene/spatial3d/Geo3DUtil.java | 49 ++++++++++++++------
.../apache/lucene/spatial3d/TestGeo3DPoint.java | 49 +++++++++++++++++++-
3 files changed, 86 insertions(+), 15 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/724f7424/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 83de9ed..c36a319 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -137,6 +137,9 @@ Bug Fixes
one update batch could be applied in the wrong order resulting in
the wrong updated value (Ishan Chattopadhyaya, hossman, Mike McCandless)
+* LUCENE-7312: Fix geo3d's x/y/z double to int encoding to ensure it always
+ rounds down (Karl Wright, Mike McCandless)
+
Documentation
* LUCENE-7223: Improve XXXPoint javadocs to make it clear that you
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/724f7424/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java
index 2e37b27..b5ce250 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java
@@ -44,8 +44,9 @@ class Geo3DUtil {
private static final double MAX_VALUE = PlanetModel.WGS84.getMaximumMagnitude();
private static final int BITS = 32;
private static final double MUL = (0x1L<<BITS)/(2*MAX_VALUE);
- static final double DECODE = 1/MUL;
+ static final double DECODE = getNextSafeDouble(1/MUL);
private static final int MIN_ENCODED_VALUE = encodeValue(-MAX_VALUE);
+ private static final int MAX_ENCODED_VALUE = encodeValue(MAX_VALUE);
public static int encodeValue(double x) {
if (x > MAX_VALUE) {
@@ -54,20 +55,26 @@ class Geo3DUtil {
if (x < -MAX_VALUE) {
throw new IllegalArgumentException("value=" + x + " is out-of-bounds (less than than WGS84's -planetMax=" + -MAX_VALUE + ")");
}
- // the maximum possible value cannot be encoded without overflow
- if (x == MAX_VALUE) {
- x = Math.nextDown(x);
- }
long result = (long) Math.floor(x / DECODE);
- //System.out.println(" enc: " + x + " -> " + result);
assert result >= Integer.MIN_VALUE;
assert result <= Integer.MAX_VALUE;
return (int) result;
}
public static double decodeValue(int x) {
- // We decode to the center value; this keeps the encoding stable
- return (x+0.5) * DECODE;
+ double result;
+ if (x == MIN_ENCODED_VALUE) {
+ // We must special case this, because -MAX_VALUE is not guaranteed to land precisely at a floor value, and we don't ever want to
+ // return a value outside of the planet's range (I think?). The max value is "safe" because we floor during encode:
+ result = -MAX_VALUE;
+ } else if (x == MAX_ENCODED_VALUE) {
+ result = MAX_VALUE;
+ } else {
+ // We decode to the center value; this keeps the encoding stable
+ result = (x+0.5) * DECODE;
+ }
+ assert result >= -MAX_VALUE && result <= MAX_VALUE;
+ return result;
}
/** Returns smallest double that would encode to int x. */
@@ -76,14 +83,30 @@ class Geo3DUtil {
return x * DECODE;
}
+ /** Returns a double value >= x such that if you multiply that value by an int, and then
+ * divide it by that int again, you get precisely the same value back */
+ private static double getNextSafeDouble(double x) {
+
+ // Move to double space:
+ long bits = Double.doubleToLongBits(x);
+
+ // Make sure we are beyond the actual maximum value:
+ bits += Integer.MAX_VALUE;
+
+ // Clear the bottom 32 bits:
+ bits &= ~((long) Integer.MAX_VALUE);
+
+ // Convert back to double:
+ double result = Double.longBitsToDouble(bits);
+ assert result > x;
+ return result;
+ }
+
/** Returns largest double that would encode to int x. */
// NOTE: keep this package private!!
static double decodeValueCeil(int x) {
- if (x == Integer.MAX_VALUE) {
- return MAX_VALUE;
- } else {
- return Math.nextDown((x+1) * DECODE);
- }
+ assert x < Integer.MAX_VALUE;
+ return Math.nextDown((x+1) * DECODE);
}
/** Converts degress to radians */
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/724f7424/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
index e639489..d651491 100644
--- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
@@ -23,6 +23,7 @@ import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
+import java.util.Random;
import java.util.Set;
import org.apache.lucene.codecs.Codec;
@@ -55,8 +56,6 @@ import org.apache.lucene.index.Term;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.Query;
import org.apache.lucene.search.SimpleCollector;
-import org.apache.lucene.spatial3d.geom.XYZSolid;
-import org.apache.lucene.spatial3d.geom.XYZSolidFactory;
import org.apache.lucene.spatial3d.geom.GeoArea;
import org.apache.lucene.spatial3d.geom.GeoAreaFactory;
import org.apache.lucene.spatial3d.geom.GeoBBox;
@@ -71,6 +70,8 @@ import org.apache.lucene.spatial3d.geom.Plane;
import org.apache.lucene.spatial3d.geom.PlanetModel;
import org.apache.lucene.spatial3d.geom.SidedPlane;
import org.apache.lucene.spatial3d.geom.XYZBounds;
+import org.apache.lucene.spatial3d.geom.XYZSolid;
+import org.apache.lucene.spatial3d.geom.XYZSolidFactory;
import org.apache.lucene.store.Directory;
import org.apache.lucene.util.DocIdSetBuilder;
import org.apache.lucene.util.FixedBitSet;
@@ -1179,6 +1180,50 @@ public class TestGeo3DPoint extends LuceneTestCase {
}
}
+ // poached from TestGeoEncodingUtils.testLatitudeQuantization:
+
+ /**
+ * step through some integers, ensuring they decode to their expected double values.
+ * double values start at -90 and increase by LATITUDE_DECODE for each integer.
+ * check edge cases within the double range and random doubles within the range too.
+ */
+ public void testQuantization() throws Exception {
+ Random random = random();
+ for (int i = 0; i < 10000; i++) {
+ int encoded = random.nextInt();
+ double min = encoded * Geo3DUtil.DECODE;
+ double decoded = Geo3DUtil.decodeValueFloor(encoded);
+ // should exactly equal expected value
+ assertEquals(min, decoded, 0.0D);
+ // should round-trip
+ assertEquals(encoded, Geo3DUtil.encodeValue(decoded));
+ // test within the range
+ if (encoded != Integer.MAX_VALUE) {
+ // this is the next representable value
+ // all double values between [min .. max) should encode to the current integer
+ // all double values between (min .. max] should encodeCeil to the next integer.
+ double max = min + Geo3DUtil.DECODE;
+ assertEquals(max, Geo3DUtil.decodeValueFloor(encoded+1), 0.0D);
+ assertEquals(encoded+1, Geo3DUtil.encodeValue(max));
+
+ // first and last doubles in range that will be quantized
+ double minEdge = Math.nextUp(min);
+ double maxEdge = Math.nextDown(max);
+ assertEquals(encoded, Geo3DUtil.encodeValue(minEdge));
+ assertEquals(encoded, Geo3DUtil.encodeValue(maxEdge));
+
+ // check random values within the double range
+ long minBits = NumericUtils.doubleToSortableLong(minEdge);
+ long maxBits = NumericUtils.doubleToSortableLong(maxEdge);
+ for (int j = 0; j < 100; j++) {
+ double value = NumericUtils.sortableLongToDouble(TestUtil.nextLong(random, minBits, maxBits));
+ // round down
+ assertEquals(encoded, Geo3DUtil.encodeValue(value));
+ }
+ }
+ }
+ }
+
public void testEncodeDecodeIsStable() throws Exception {
int iters = atLeast(1000);