Publish

6 files changed, 478 insertions, 0 deletions

diff --git a/vespalib/src/tests/zcurve/.gitignore b/vespalib/src/tests/zcurve/.gitignore
new file mode 100644
index 00000000000..dbbe05b223b
--- /dev/null
+++ b/vespalib/src/tests/zcurve/.gitignore
@@ -0,0 +1,5 @@
+.depend
+Makefile
+zcurve_test
+vespalib_zcurve_ranges_test_app
+vespalib_zcurve_test_app
diff --git a/vespalib/src/tests/zcurve/CMakeLists.txt b/vespalib/src/tests/zcurve/CMakeLists.txt
new file mode 100644
index 00000000000..14d08bbe9ba
--- /dev/null
+++ b/vespalib/src/tests/zcurve/CMakeLists.txt
@@ -0,0 +1,15 @@
+# Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(vespalib_zcurve_test_app
+    SOURCES
+    zcurve_test.cpp
+    DEPENDS
+    vespalib
+)
+vespa_add_test(NAME vespalib_zcurve_test_app COMMAND vespalib_zcurve_test_app)
+vespa_add_executable(vespalib_zcurve_ranges_test_app
+    SOURCES
+    zcurve_ranges_test.cpp
+    DEPENDS
+    vespalib
+)
+vespa_add_test(NAME vespalib_zcurve_ranges_test_app COMMAND vespalib_zcurve_ranges_test_app)
diff --git a/vespalib/src/tests/zcurve/DESC b/vespalib/src/tests/zcurve/DESC
new file mode 100644
index 00000000000..e47e3fb171e
--- /dev/null
+++ b/vespalib/src/tests/zcurve/DESC
@@ -0,0 +1 @@
+This is a test for the ZCurve class.
diff --git a/vespalib/src/tests/zcurve/FILES b/vespalib/src/tests/zcurve/FILES
new file mode 100644
index 00000000000..715d2c9dedb
--- /dev/null
+++ b/vespalib/src/tests/zcurve/FILES
@@ -0,0 +1 @@
+zcurve.cpp
diff --git a/vespalib/src/tests/zcurve/zcurve_ranges_test.cpp b/vespalib/src/tests/zcurve/zcurve_ranges_test.cpp
new file mode 100644
index 00000000000..06112045dc2
--- /dev/null
+++ b/vespalib/src/tests/zcurve/zcurve_ranges_test.cpp
@@ -0,0 +1,57 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+#include <vespa/vespalib/testkit/test_kit.h>
+#include <vespa/vespalib/geo/zcurve.h>
+#include <vector>
+
+typedef vespalib::geo::ZCurve Z;
+
+bool inside(int x, int y, const Z::RangeVector &ranges) {
+    int64_t z = Z::encode(x, y);
+    for (auto range: ranges) {
+        if (z >= range.min() && z <= range.max()) {
+            return true;
+        }
+    }
+    fprintf(stderr, "FAILED: (%d, %d) -> (%ld) not in:\n", x, y, z);
+    for (auto range: ranges) {
+        fprintf(stderr, "  [%ld, %ld]\n", range.min(), range.max());
+    }
+    return false;
+}
+
+bool verify_ranges(int min_x, int min_y, int max_x, int max_y) {
+    Z::RangeVector ranges = Z::find_ranges(min_x, min_y, max_x, max_y);
+    for (int x = min_x; x <= max_x; ++x) {
+        for (int y = min_y; y <= max_y; ++y) {
+            if (!EXPECT_TRUE(inside(x, y, ranges))) {
+                return false;
+            }
+        }
+    }
+    return true;
+}
+
+TEST("require that returned ranges contains bounding box") {
+    std::vector<int> values({-13, -1, 0, 1, 13});
+    for (auto min_x: values) {
+        for (auto min_y: values) {
+            for (auto max_x: values) {
+                for (auto max_y: values) {
+                    if (max_x >= min_x && max_y >= min_y) {
+                        if (!EXPECT_TRUE(verify_ranges(min_x, min_y, max_x, max_y))) {
+                            fprintf(stderr, "BOX: (%d, %d) -> (%d, %d)\n",
+                                    min_x, min_y, max_x, max_y);
+                        }
+                    }
+                }
+            }
+        }
+    }
+}
+
+TEST("require that silly bounding box does not explode") {
+    Z::RangeVector ranges = Z::find_ranges(-105, -7000000, 105, 7000000);
+    EXPECT_EQUAL(42u, ranges.size());
+}
+
+TEST_MAIN() { TEST_RUN_ALL(); }
diff --git a/vespalib/src/tests/zcurve/zcurve_test.cpp b/vespalib/src/tests/zcurve/zcurve_test.cpp
new file mode 100644
index 00000000000..e4a5d02d68e
--- /dev/null
+++ b/vespalib/src/tests/zcurve/zcurve_test.cpp
@@ -0,0 +1,399 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/fastos/fastos.h>
+#include <vespa/log/log.h>
+LOG_SETUP("zcurve_test");
+#include <vespa/vespalib/testkit/testapp.h>
+#include <vespa/vespalib/geo/zcurve.h>
+#include <algorithm>
+#include <limits>
+#include <map>
+
+namespace vespalib {
+
+using geo::ZCurve;
+
+class ZCurveTest : public vespalib::TestApp
+{
+public:
+    ZCurveTest(void)
+        : vespalib::TestApp()
+    {
+    }
+
+    void
+    testEncoding(void);
+
+    void
+    testDecoding(void);
+
+    double
+    ftime(void);
+
+    static inline int64_t
+    encodexy3(int32_t x, int32_t y);
+
+#define BMLIMIT 0x1000000
+
+    template <bool decode>
+    int64_t
+    bm(void);
+
+    template <bool decode>
+    int64_t
+    bm2(void);
+
+    template <bool decode>
+    int64_t
+    bm3(void);
+
+    int64_t
+    bmcheck(void);
+
+    int Main(void);
+};
+
+
+void
+ZCurveTest::testEncoding(void)
+{
+    int32_t x = 0;
+    int32_t y = 0;
+    int64_t z = ZCurve::encode(x, y);
+    ASSERT_TRUE(z == 0);
+
+    x = std::numeric_limits<int32_t>::min();
+    y = std::numeric_limits<int32_t>::min();
+    z = ZCurve::encode(x, y);
+    ASSERT_TRUE(static_cast<int64_t>(UINT64_C(0xc000000000000000)) == z);
+
+    x = std::numeric_limits<int32_t>::min();
+    y = std::numeric_limits<int32_t>::max();
+    z = ZCurve::encode(x, y);
+    ASSERT_TRUE(static_cast<int64_t>(UINT64_C(0x6aaaaaaaaaaaaaaa)) == z);
+
+    x = std::numeric_limits<int32_t>::max();
+    y = std::numeric_limits<int32_t>::max();
+    z = ZCurve::encode(x, y);
+    ASSERT_TRUE(static_cast<int64_t>(UINT64_C(0x3fffffffffffffff)) == z);
+
+    x = -1;
+    y = -1;
+    z = ZCurve::encode(x, y);
+    ASSERT_TRUE(static_cast<int64_t>(UINT64_C(0xffffffffffffffff)) ==  z);
+
+    x = std::numeric_limits<int32_t>::max() / 2;
+    y = std::numeric_limits<int32_t>::min() / 2;
+    z = ZCurve::encode(x, y);
+    ASSERT_TRUE(static_cast<int64_t>(UINT64_C(0xa555555555555555)) == z);
+}
+
+
+void
+ZCurveTest::testDecoding(void)
+{
+    int32_t x = 0;
+    int32_t y = 0;
+    int64_t z = ZCurve::encode(x, y);
+    int32_t dx;
+    int32_t dy;
+    dx = 0;
+    dy = 0;
+    ZCurve::decode(z, &dx, &dy);
+    ASSERT_TRUE(dx == x);
+    ASSERT_TRUE(dy == y);
+
+    x = std::numeric_limits<int32_t>::max();
+    y = std::numeric_limits<int32_t>::max();
+    z = ZCurve::encode(x, y);
+    ZCurve::decode(z, &dx, &dy);
+    ASSERT_TRUE(dx == x);
+    ASSERT_TRUE(dy == y);
+
+    x = std::numeric_limits<int32_t>::min();
+    y = std::numeric_limits<int32_t>::min();
+    z = ZCurve::encode(x, y);
+    ZCurve::decode(z, &dx, &dy);
+    ASSERT_TRUE(dx == x);
+    ASSERT_TRUE(dy == y);
+
+    x = std::numeric_limits<int32_t>::min();
+    y = std::numeric_limits<int32_t>::max();
+    z = ZCurve::encode(x, y);
+    ZCurve::decode(z, &dx, &dy);
+    ASSERT_TRUE(dx == x);
+    ASSERT_TRUE(dy == y);
+
+    x = -18;
+    y = 1333;
+    z = ZCurve::encode(x, y);
+    ZCurve::decode(z, &dx, &dy);
+    ASSERT_TRUE(dx == x);
+    ASSERT_TRUE(dy == y);
+
+    x = 0;
+    y = 0;
+    z = ZCurve::encode(x, y);
+    ZCurve::decode(z, &dx, &dy);
+    ASSERT_TRUE(dx == x);
+    ASSERT_TRUE(dy == y);
+}
+
+
+double
+ZCurveTest::ftime(void)
+{
+    struct timeval tv;
+    gettimeofday(&tv, NULL);
+    return tv.tv_sec + tv.tv_usec / 1000000.0;
+}
+
+int64_t
+ZCurveTest::encodexy3(int32_t x, int32_t y)
+{
+    uint32_t resxl;
+    uint32_t resxh;
+    uint32_t resyl;
+    uint32_t resyh;
+
+    resxl = (static_cast<uint32_t>(x) & 0x0000ffffu);
+    resxh = (static_cast<uint32_t>(x) & 0xffff0000u) >> 16;
+    resyl = (static_cast<uint32_t>(y) & 0x0000ffffu);
+    resyh = (static_cast<uint32_t>(y) & 0xffff0000u) >> 16;
+    resxl = ((resxl & 0xff00ff00u) << 8) | (resxl & 0x00ff00ffu);
+    resyl = ((resyl & 0xff00ff00u) << 8) | (resyl & 0x00ff00ffu);
+    resxh = ((resxh & 0xff00ff00u) << 8) | (resxh & 0x00ff00ffu);
+    resyh = ((resyh & 0xff00ff00u) << 8) | (resyh & 0x00ff00ffu);
+    resxl = ((resxl & 0xf0f0f0f0u) << 4) | (resxl & 0x0f0f0f0fu);
+    resyl = ((resyl & 0xf0f0f0f0u) << 4) | (resyl & 0x0f0f0f0fu);
+    resxh = ((resxh & 0xf0f0f0f0u) << 4) | (resxh & 0x0f0f0f0fu);
+    resyh = ((resyh & 0xf0f0f0f0u) << 4) | (resyh & 0x0f0f0f0fu);
+    resxl = ((resxl & 0xccccccccu) << 2) | (resxl & 0x33333333u);
+    resyl = ((resyl & 0xccccccccu) << 2) | (resyl & 0x33333333u);
+    resxh = ((resxh & 0xccccccccu) << 2) | (resxh & 0x33333333u);
+    resyh = ((resyh & 0xccccccccu) << 2) | (resyh & 0x33333333u);
+    resxl = ((resxl & 0xaaaaaaaau) << 1) | (resxl & 0x55555555u);
+    resyl = ((resyl & 0xaaaaaaaau) << 1) | (resyl & 0x55555555u);
+    resxh = ((resxh & 0xaaaaaaaau) << 1) | (resxh & 0x55555555u);
+    resyh = ((resyh & 0xaaaaaaaau) << 1) | (resyh & 0x55555555u);
+    return static_cast<int64_t>(resxl | (resyl << 1) |
+                                (static_cast<uint64_t>(resxh |
+                                        (resyh << 1)) << 32));
+}
+
+
+template <bool decode>
+int64_t
+ZCurveTest::bm(void)
+{
+    int64_t res = 0;
+    double before = ftime();
+    int32_t x = 0;
+    do {
+        x++;
+        int64_t enc = ZCurve::encodeSlow(x, 0);
+        res += enc;
+        if (decode) {
+            int32_t checkx = 0;
+            int32_t checky = 0;
+            ZCurve::decodeSlow(enc, &checkx, &checky);
+            ASSERT_TRUE(checkx == x);
+            ASSERT_TRUE(checky == 0);
+        }
+    } while (x != BMLIMIT);
+    int32_t y = 0;
+    do {
+        y++;
+        int64_t enc = ZCurve::encodeSlow(0, y);
+        res += enc;
+        if (decode) {
+            int32_t checkx = 0;
+            int32_t checky = 0;
+            ZCurve::decodeSlow(enc, &checkx, &checky);
+            ASSERT_TRUE(checkx == 0);
+            ASSERT_TRUE(checky == y);
+        }
+    } while (y != BMLIMIT);
+    double after = ftime();
+    LOG(info,
+        "Elapsed bm<decode = %s> = %6.2f",
+        decode ? "true" : "false",
+        after - before);
+    return res;
+}
+
+
+template <bool decode>
+int64_t
+ZCurveTest::bm2(void)
+{
+    int64_t res = 0;
+    double before = ftime();
+    int32_t x = 0;
+    do {
+        x++;
+        int64_t enc = ZCurve::encode(x, 0);
+        res += enc;
+        if (decode) {
+            int32_t checkx = 0;
+            int32_t checky = 0;
+            ZCurve::decode(enc, &checkx, &checky);
+            ASSERT_TRUE(checkx == x);
+            ASSERT_TRUE(checky == 0);
+        }
+    } while (x != BMLIMIT);
+    int32_t y = 0;
+    do {
+        y++;
+        int64_t enc = ZCurve::encode(0, y);
+        res += enc;
+        if (decode) {
+            int32_t checkx = 0;
+            int32_t checky = 0;
+            ZCurve::decode(enc, &checkx, &checky);
+            ASSERT_TRUE(checkx == 0);
+            ASSERT_TRUE(checky == y);
+        }
+    } while (y != BMLIMIT);
+    double after = ftime();
+    LOG(info,
+        "Elapsed bm2<decode = %s> = %6.2f",
+        decode ? "true" : "false",
+        after - before);
+    return res;
+}
+
+
+template <bool decode>
+int64_t
+ZCurveTest::bm3(void)
+{
+    int64_t res = 0;
+    double before = ftime();
+    int32_t x = 0;
+    do {
+        x++;
+        int64_t enc = encodexy3(x, 0);
+        res += enc;
+        if (decode) {
+            int32_t checkx = 0;
+            int32_t checky = 0;
+            ZCurve::decode(enc, &checkx, &checky);
+            ASSERT_TRUE(checkx == x);
+            ASSERT_TRUE(checky == 0);
+        }
+    } while (x != BMLIMIT);
+    int32_t y = 0;
+    do {
+        y++;
+        int64_t enc = encodexy3(0, y);
+        res += enc;
+        if (decode) {
+            int32_t checkx = 0;
+            int32_t checky = 0;
+            ZCurve::decode(enc, &checkx, &checky);
+            ASSERT_TRUE(checkx == 0);
+            ASSERT_TRUE(checky == y);
+        }
+    } while (y != BMLIMIT);
+    double after = ftime();
+    LOG(info,
+        "Elapsed bm3<decode = %s> = %6.2f",
+        decode ? "true" : "false",
+        after - before);
+    return res;
+}
+
+
+int64_t
+ZCurveTest::bmcheck(void)
+{
+    int64_t res = 0;
+    double before = ftime();
+    int32_t x = 0;
+    do {
+        x++;
+        int64_t enc = ZCurve::encodeSlow(x, 0);
+        int64_t enc2 = ZCurve::encode(x, 0);
+        int64_t enc3 = encodexy3(x, 0);
+        ASSERT_TRUE(enc == enc2);
+        ASSERT_TRUE(enc == enc3);
+        res += enc;
+        int32_t checkx = 0;
+        int32_t checky = 0;
+        ZCurve::decode(enc, &checkx, &checky);
+        ASSERT_TRUE(checkx == x);
+        ASSERT_TRUE(checky == 0);
+    } while (x != BMLIMIT);
+    int32_t y = 0;
+    do {
+        y++;
+        int64_t enc = ZCurve::encodeSlow(0, y);
+        int64_t enc2 = ZCurve::encode(0, y);
+        int64_t enc3 = encodexy3(0, y);
+        ASSERT_TRUE(enc == enc2);
+        ASSERT_TRUE(enc == enc3);
+        res += enc;
+        int32_t checkx = 0;
+        int32_t checky = 0;
+        ZCurve::decode(enc, &checkx, &checky);
+        ASSERT_TRUE(checkx == 0);
+        ASSERT_TRUE(checky == y);
+    } while (y != BMLIMIT);
+    double after = ftime();
+    LOG(info,
+        "Elapsed bmcheck = %6.2f",
+        after - before);
+    return res;
+}
+
+
+int
+ZCurveTest::Main(void)
+{
+    TEST_INIT("zcurve_test");
+
+    for (int32_t x = 0; x < 4; x++) {
+        for (int32_t y = 0; y < 4; y++) {
+            int64_t enc = 0;
+            int64_t enc2 = 0;
+            int64_t enc3 = 0;
+            int32_t checkx = 0;
+            int32_t checky = 0;
+            enc = ZCurve::encodeSlow(x, y);
+            enc2 = ZCurve::encode(x, y);
+            enc3 = encodexy3(x, y);
+            ASSERT_TRUE(enc == enc2);
+            ASSERT_TRUE(enc == enc3);
+            // printf("x=%u, y=%u, enc=%" PRId64 "\n", x, y, enc);
+            checkx = 0;
+            checky = 0;
+            ZCurve::decodeSlow(enc, &checkx, &checky);
+            ASSERT_TRUE(x == checkx);
+            ASSERT_TRUE(y == checky);
+        }
+    }
+    testEncoding();
+    testDecoding();
+    if (_argc >= 2) {
+        int64_t enc1 = bm<true>();
+        int64_t enc1b = bm<false>();
+        int64_t enc2 = bm2<true>();
+        int64_t enc2b = bm2<false>();
+        int64_t enc3 = bm3<true>();
+        int64_t enc3b = bm3<false>();
+        int64_t enc4 = bmcheck();
+        ASSERT_TRUE(enc1 == enc1b);
+        ASSERT_TRUE(enc1 == enc2);
+        ASSERT_TRUE(enc1 == enc2b);
+        ASSERT_TRUE(enc1 == enc3);
+        ASSERT_TRUE(enc1 == enc3b);
+        ASSERT_TRUE(enc1 == enc4);
+    }
+
+    TEST_DONE();
+}
+
+}
+
+TEST_APPHOOK(vespalib::ZCurveTest);