lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mikemcc...@apache.org
Subject lucene-solr:branch_6x: LUCENE-7312: fix geo3d's encoding to always round down
Date Sat, 04 Jun 2016 22:17:50 GMT
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 <mikemccand@apache.org>
Authored: Sat Jun 4 18:16:04 2016 -0400
Committer: Mike McCandless <mikemccand@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);


Mime
View raw message