src/zonedetect.cc

   1 /*
   2  * Copyright (c) 2018, Bertold Van den Bergh (vandenbergh@bertold.org)
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are met:
   7  *     * Redistributions of source code must retain the above copyright
   8  *       notice, this list of conditions and the following disclaimer.
   9  *     * Redistributions in binary form must reproduce the above copyright
  10  *       notice, this list of conditions and the following disclaimer in the
  11  *       documentation and/or other materials provided with the distribution.
  12  *     * Neither the name of the author nor the
  13  *       names of its contributors may be used to endorse or promote products
  14  *       derived from this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
  17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR DISTRIBUTOR BE LIABLE FOR ANY
  20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include <cassert>
  29 #include <cmath>
  30 #include <cstdlib>
  31 #include <cstring>
  32 #if defined(_MSC_VER) || defined(__MINGW32__)
  33 #include <windows.h>
  34 #elif defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
  35 #include <cerrno>
  36 #include <memory>
  37 #include <vector>
  38
  39 #include <fcntl.h>
  40 #include <sys/mman.h>
  41 #include <unistd.h>
  42 #endif
  43
  44 #include "zonedetect.h"
  45
  46 enum ZDInternalError {
  47     ZD_OK,
  48     ZD_E_DB_OPEN,
  49     ZD_E_DB_SEEK,
  50     ZD_E_DB_MMAP,
  51 #if defined(_MSC_VER) || defined(__MINGW32__)
  52     ZD_E_DB_MMAP_MSVIEW,
  53     ZD_E_DB_MAP_EXCEPTION,
  54     ZD_E_DB_MUNMAP_MSVIEW,
  55 #endif
  56     ZD_E_DB_MUNMAP,
  57     ZD_E_DB_CLOSE,
  58     ZD_E_PARSE_HEADER
  59 };
  60
  61 struct ZoneDetect {
  62 #if defined(_MSC_VER) || defined(__MINGW32__)
  63     HANDLE fd;
  64     HANDLE fdMap;
  65     int32_t length;
  66     int32_t padding;
  67 #elif defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
  68     int fd;
  69     off_t length;
  70 #else
  71     int length;
  72 #endif
  73
  74     uint8_t closeType;
  75     uint8_t *mapping;
  76
  77     uint8_t tableType;
  78     uint8_t version;
  79     uint8_t precision;
  80     uint8_t numFields;
  81
  82     char *notice;
  83     char **fieldNames;
  84
  85     uint32_t bboxOffset;
  86     uint32_t metadataOffset;
  87     uint32_t dataOffset;
  88 };
  89
  90 static void (*zdErrorHandler)(int, int);
  91 static void zdError(enum ZDInternalError errZD, int errNative)
  92 {
  93     if (zdErrorHandler) zdErrorHandler(static_cast<int>(errZD), errNative);
  94 }
  95
  96 static int32_t ZDFloatToFixedPoint(float input, float scale, unsigned int precision)
  97 {
  98     const float inputScaled = input / scale;
  99     return static_cast<int32_t>(inputScaled * static_cast<float>(1 << (precision - 1)));
 100 }
 101
 102 static float ZDFixedPointToFloat(int32_t input, float scale, unsigned int precision)
 103 {
 104     const float value = static_cast<float>(input) / static_cast<float>(1 << (precision - 1));
 105     return value * scale;
 106 }
 107
 108 static unsigned int ZDDecodeVariableLengthUnsigned(const ZoneDetect *library, uint32_t *index, uint64_t *result)
 109 {
 110     if(*index >= static_cast<uint32_t>(library->length)) {
 111         return 0;
 112     }
 113
 114     uint64_t value = 0;
 115     unsigned int i = 0;
 116 #if defined(_MSC_VER)
 117     __try {
 118 #endif
 119         uint8_t *const buffer = library->mapping + *index;
 120         uint8_t *const bufferEnd = library->mapping + library->length - 1;
 121
 122         unsigned int shift = 0;
 123         while(true) {
 124             value |= (((static_cast<uint64_t>(buffer[i])) & UINT8_C(0x7F)) << shift);
 125             shift += 7u;
 126
 127             if(!(buffer[i] & UINT8_C(0x80))) {
 128                 break;
 129             }
 130
 131             i++;
 132             if(buffer + i > bufferEnd) {
 133                 return 0;
 134             }
 135         }
 136 #if defined(_MSC_VER)
 137     } __except(GetExceptionCode() == EXCEPTION_IN_PAGE_ERROR
 138                ? EXCEPTION_EXECUTE_HANDLER
 139                : EXCEPTION_CONTINUE_SEARCH) { /* file mapping SEH exception occurred */
 140         zdError(ZD_E_DB_MAP_EXCEPTION, (int)GetLastError());
 141         return 0;
 142     }
 143 #endif
 144
 145     i++;
 146     *result = value;
 147     *index += i;
 148     return i;
 149 }
 150
 151 static unsigned int ZDDecodeVariableLengthUnsignedReverse(const ZoneDetect *library, uint32_t *index, uint64_t *result)
 152 {
 153     uint32_t i = *index;
 154
 155     if(*index >= static_cast<uint32_t>(library->length)) {
 156         return 0;
 157     }
 158
 159 #if defined(_MSC_VER)
 160     __try {
 161 #endif
 162
 163         if(library->mapping[i] & UINT8_C(0x80)) {
 164             return 0;
 165         }
 166
 167         if(!i) {
 168             return 0;
 169         }
 170         i--;
 171
 172         while(library->mapping[i] & UINT8_C(0x80)) {
 173             if(!i) {
 174                 return 0;
 175             }
 176             i--;
 177         }
 178
 179 #if defined(_MSC_VER)
 180     } __except(GetExceptionCode() == EXCEPTION_IN_PAGE_ERROR
 181                ? EXCEPTION_EXECUTE_HANDLER
 182                : EXCEPTION_CONTINUE_SEARCH) { /* file mapping SEH exception occurred */
 183         zdError(ZD_E_DB_MAP_EXCEPTION, (int)GetLastError());
 184         return 0;
 185     }
 186 #endif
 187
 188     *index = i;
 189
 190     i++;
 191
 192     uint32_t i2 = i;
 193     return ZDDecodeVariableLengthUnsigned(library, &i2, result);
 194 }
 195
 196 static int64_t ZDDecodeUnsignedToSigned(uint64_t value)
 197 {
 198     return (value & 1) ? -static_cast<int64_t>(value / 2) : static_cast<int64_t>(value / 2);
 199 }
 200
 201 static unsigned int ZDDecodeVariableLengthSigned(const ZoneDetect *library, uint32_t *index, int32_t *result)
 202 {
 203     uint64_t value = 0;
 204     const unsigned int retVal = ZDDecodeVariableLengthUnsigned(library, index, &value);
 205     *result = static_cast<int32_t>(ZDDecodeUnsignedToSigned(value));
 206     return retVal;
 207 }
 208
 209 static char *ZDParseString(const ZoneDetect *library, uint32_t *index)
 210 {
 211     uint64_t strLength;
 212     if(!ZDDecodeVariableLengthUnsigned(library, index, &strLength)) {
 213         return nullptr;
 214     }
 215
 216     uint32_t strOffset = *index;
 217     unsigned int remoteStr = 0;
 218     if(strLength >= 256) {
 219         strOffset = library->metadataOffset + static_cast<uint32_t>(strLength) - 256;
 220         remoteStr = 1;
 221
 222         if(!ZDDecodeVariableLengthUnsigned(library, &strOffset, &strLength)) {
 223             return nullptr;
 224         }
 225
 226         if(strLength > 256) {
 227             return nullptr;
 228         }
 229     }
 230
 231     auto str = static_cast<char *>(malloc(static_cast<size_t>(strLength + 1)));
 232
 233     if(str) {
 234 #if defined(_MSC_VER)
 235         __try {
 236 #endif
 237             size_t i;
 238             for(i = 0; i < strLength; i++) {
 239                 str[i] = static_cast<char>(library->mapping[strOffset + i] ^ UINT8_C(0x80));
 240             }
 241 #if defined(_MSC_VER)
 242         } __except(GetExceptionCode() == EXCEPTION_IN_PAGE_ERROR
 243                    ? EXCEPTION_EXECUTE_HANDLER
 244                    : EXCEPTION_CONTINUE_SEARCH) { /* file mapping SEH exception occurred */
 245             zdError(ZD_E_DB_MAP_EXCEPTION, (int)GetLastError());
 246             return 0;
 247         }
 248 #endif
 249         str[strLength] = 0;
 250     }
 251
 252     if(!remoteStr) {
 253         *index += static_cast<uint32_t>(strLength);
 254     }
 255
 256     return str;
 257 }
 258
 259 static int ZDParseHeader(ZoneDetect *library)
 260 {
 261     if(library->length < 7) {
 262         return -1;
 263     }
 264
 265 #if defined(_MSC_VER)
 266     __try {
 267 #endif
 268         if(memcmp(library->mapping, "PLB", 3)) {
 269             return -1;
 270         }
 271
 272         library->tableType = library->mapping[3];
 273         library->version   = library->mapping[4];
 274         library->precision = library->mapping[5];
 275         library->numFields = library->mapping[6];
 276 #if defined(_MSC_VER)
 277     } __except(GetExceptionCode() == EXCEPTION_IN_PAGE_ERROR
 278                ? EXCEPTION_EXECUTE_HANDLER
 279                : EXCEPTION_CONTINUE_SEARCH) { /* file mapping SEH exception occurred */
 280         zdError(ZD_E_DB_MAP_EXCEPTION, (int)GetLastError());
 281         return 0;
 282     }
 283 #endif
 284
 285     if(library->version >= 2) {
 286         return -1;
 287     }
 288
 289     uint32_t index = UINT32_C(7);
 290
 291     library->fieldNames = static_cast<char **>(malloc(library->numFields * sizeof *library->fieldNames));
 292     if (!library->fieldNames) {
 293         return -1;
 294     }
 295
 296     size_t i;
 297     for(i = 0; i < library->numFields; i++) {
 298         library->fieldNames[i] = ZDParseString(library, &index);
 299     }
 300
 301     library->notice = ZDParseString(library, &index);
 302     if(!library->notice) {
 303         return -1;
 304     }
 305
 306     uint64_t tmp;
 307     /* Read section sizes */
 308     /* By memset: library->bboxOffset = 0 */
 309
 310     if(!ZDDecodeVariableLengthUnsigned(library, &index, &tmp)) return -1;
 311     library->metadataOffset = static_cast<uint32_t>(tmp) + library->bboxOffset;
 312
 313     if(!ZDDecodeVariableLengthUnsigned(library, &index, &tmp))return -1;
 314     library->dataOffset = static_cast<uint32_t>(tmp) + library->metadataOffset;
 315
 316     if(!ZDDecodeVariableLengthUnsigned(library, &index, &tmp)) return -1;
 317
 318     /* Add header size to everything */
 319     library->bboxOffset += index;
 320     library->metadataOffset += index;
 321     library->dataOffset += index;
 322
 323     /* Verify file length */
 324     if(tmp + library->dataOffset != static_cast<uint32_t>(library->length)) {
 325         return -2;
 326     }
 327
 328     return 0;
 329 }
 330
 331 static int ZDPointInBox(int32_t xl, int32_t x, int32_t xr, int32_t yl, int32_t y, int32_t yr)
 332 {
 333     if((xl <= x && x <= xr) || (xr <= x && x <= xl)) {
 334         if((yl <= y && y <= yr) || (yr <= y && y <= yl)) {
 335             return 1;
 336         }
 337     }
 338
 339     return 0;
 340 }
 341
 342 static uint32_t ZDUnshuffle(uint64_t w)
 343 {
 344     w &=                  0x5555555555555555llu;
 345     w = (w | (w >> 1))  & 0x3333333333333333llu;
 346     w = (w | (w >> 2))  & 0x0F0F0F0F0F0F0F0Fllu;
 347     w = (w | (w >> 4))  & 0x00FF00FF00FF00FFllu;
 348     w = (w | (w >> 8))  & 0x0000FFFF0000FFFFllu;
 349     w = (w | (w >> 16)) & 0x00000000FFFFFFFFllu;
 350     return static_cast<uint32_t>(w);
 351 }
 352
 353 static void ZDDecodePoint(uint64_t point, int32_t* lat, int32_t* lon)
 354 {
 355     *lat = static_cast<int32_t>(ZDDecodeUnsignedToSigned(ZDUnshuffle(point)));
 356     *lon = static_cast<int32_t>(ZDDecodeUnsignedToSigned(ZDUnshuffle(point >> 1)));
 357 }
 358
 359 struct Reader {
 360     const ZoneDetect *library;
 361     uint32_t polygonIndex;
 362
 363     uint64_t numVertices;
 364
 365     uint8_t done, first;
 366     uint32_t referenceStart, referenceEnd;
 367     int32_t referenceDirection;
 368
 369     int32_t pointLat, pointLon;
 370     int32_t firstLat, firstLon;
 371 };
 372
 373 static void ZDReaderInit(struct Reader *reader, const ZoneDetect *library, uint32_t polygonIndex)
 374 {
 375     memset(reader, 0, sizeof(*reader));
 376
 377     reader->library = library;
 378     reader->polygonIndex = polygonIndex;
 379
 380     reader->first = 1;
 381 }
 382
 383 static int ZDReaderGetPoint(struct Reader *reader, int32_t *pointLat, int32_t *pointLon)
 384 {
 385     int32_t diffLat = 0, diffLon = 0;
 386
 387     while(true) {
 388         if(reader->done > 1) {
 389             return 0;
 390         }
 391
 392         if(reader->first && reader->library->version == 0) {
 393             if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, &reader->numVertices)) return -1;
 394             if(!reader->numVertices) return -1;
 395         }
 396
 397         uint8_t referenceDone = 0;
 398
 399         if(reader->library->version == 1) {
 400             uint64_t point = 0;
 401
 402             if(!reader->referenceDirection) {
 403                 if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, &point)) return -1;
 404             } else {
 405                 if(reader->referenceDirection > 0) {
 406                     /* Read reference forward */
 407                     if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->referenceStart, &point)) return -1;
 408                     if(reader->referenceStart >= reader->referenceEnd) {
 409                         referenceDone = 1;
 410                     }
 411                 } else if(reader->referenceDirection < 0) {
 412                     /* Read reference backwards */
 413                     if(!ZDDecodeVariableLengthUnsignedReverse(reader->library, &reader->referenceStart, &point)) return -1;
 414                     if(reader->referenceStart <= reader->referenceEnd) {
 415                         referenceDone = 1;
 416                     }
 417                 }
 418             }
 419
 420             if(!point) {
 421                 /* This is a special marker, it is not allowed in reference mode */
 422                 if(reader->referenceDirection) {
 423                     return -1;
 424                 }
 425
 426                 uint64_t value;
 427                 if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, &value)) return -1;
 428
 429                 if(value == 0) {
 430                     reader->done = 2;
 431                 } else if(value == 1) {
 432                     int32_t diff;
 433                     int64_t start;
 434                     if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, reinterpret_cast<uint64_t*>(&start))) return -1;
 435                     if(!ZDDecodeVariableLengthSigned(reader->library, &reader->polygonIndex, &diff)) return -1;
 436
 437                     reader->referenceStart = reader->library->dataOffset+static_cast<uint32_t>(start);
 438                     reader->referenceEnd = reader->library->dataOffset+static_cast<uint32_t>(start + diff);
 439                     reader->referenceDirection = diff;
 440                     if(diff < 0) {
 441                         reader->referenceStart--;
 442                         reader->referenceEnd--;
 443                     }
 444                     continue;
 445                 }
 446             } else {
 447                 ZDDecodePoint(point, &diffLat, &diffLon);
 448                 if(reader->referenceDirection < 0) {
 449                     diffLat = -diffLat;
 450                     diffLon = -diffLon;
 451                 }
 452             }
 453         }
 454
 455         if(reader->library->version == 0) {
 456             if(!ZDDecodeVariableLengthSigned(reader->library, &reader->polygonIndex, &diffLat)) return -1;
 457             if(!ZDDecodeVariableLengthSigned(reader->library, &reader->polygonIndex, &diffLon)) return -1;
 458         }
 459
 460         if(!reader->done) {
 461             reader->pointLat += diffLat;
 462             reader->pointLon += diffLon;
 463             if(reader->first) {
 464                 reader->firstLat = reader->pointLat;
 465                 reader->firstLon = reader->pointLon;
 466             }
 467         } else {
 468             /* Close the polygon (the closing point is not encoded) */
 469             reader->pointLat = reader->firstLat;
 470             reader->pointLon = reader->firstLon;
 471             reader->done = 2;
 472         }
 473
 474         reader->first = 0;
 475
 476         if(reader->library->version == 0) {
 477             reader->numVertices--;
 478             if(!reader->numVertices) {
 479                 reader->done = 1;
 480             }
 481             if(!diffLat && !diffLon) {
 482                 continue;
 483             }
 484         }
 485
 486         if(referenceDone) {
 487             reader->referenceDirection = 0;
 488         }
 489
 490         break;
 491     }
 492
 493     if(pointLat) {
 494         *pointLat = reader->pointLat;
 495     }
 496
 497     if(pointLon) {
 498         *pointLon = reader->pointLon;
 499     }
 500
 501     return 1;
 502 }
 503
 504 static int ZDFindPolygon(const ZoneDetect *library, uint32_t wantedId, uint32_t* metadataIndexPtr, uint32_t* polygonIndexPtr)
 505 {
 506     uint32_t polygonId = 0;
 507     uint32_t bboxIndex = library->bboxOffset;
 508
 509     uint32_t metadataIndex = 0, polygonIndex = 0;
 510
 511     while(bboxIndex < library->metadataOffset) {
 512         uint64_t polygonIndexDelta;
 513         int32_t metadataIndexDelta;
 514         int32_t tmp;
 515         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
 516         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
 517         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
 518         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
 519         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &metadataIndexDelta)) break;
 520         if(!ZDDecodeVariableLengthUnsigned(library, &bboxIndex, &polygonIndexDelta)) break;
 521
 522         metadataIndex += static_cast<uint32_t>(metadataIndexDelta);
 523         polygonIndex += static_cast<uint32_t>(polygonIndexDelta);
 524
 525         if(polygonId == wantedId) {
 526             if(metadataIndexPtr) {
 527                 metadataIndex += library->metadataOffset;
 528                 *metadataIndexPtr = metadataIndex;
 529             }
 530             if(polygonIndexPtr) {
 531                 polygonIndex += library->dataOffset;
 532                 *polygonIndexPtr = polygonIndex;
 533             }
 534             return 1;
 535         }
 536
 537         polygonId ++;
 538     }
 539
 540     return 0;
 541 }
 542
 543 static std::vector<int32_t> ZDPolygonToListInternal(const ZoneDetect *library, uint32_t polygonIndex)
 544 {
 545     struct Reader reader;
 546     ZDReaderInit(&reader, library, polygonIndex);
 547
 548     constexpr size_t listLength = 2 * 100;
 549     std::vector<int32_t> list;
 550     list.reserve(listLength);
 551
 552     while(true) {
 553         int32_t pointLat, pointLon;
 554         int result = ZDReaderGetPoint(&reader, &pointLat, &pointLon);
 555         if(result < 0) {
 556             return {};
 557         }
 558         if(result == 0) {
 559             break;
 560         }
 561
 562         list.push_back(pointLat);
 563         list.push_back(pointLon);
 564
 565         if(list.size() >= 1048576) {
 566             return {};
 567         }
 568     }
 569
 570     return list;
 571 }
 572
 573 float* ZDPolygonToList(const ZoneDetect *library, uint32_t polygonId, size_t* lengthPtr)
 574 {
 575     uint32_t polygonIndex;
 576     float* flData = nullptr;
 577
 578     if (!ZDFindPolygon(library, polygonId, nullptr, &polygonIndex))
 579         return nullptr;
 580
 581     const auto data = ZDPolygonToListInternal(library, polygonIndex);
 582     if (data.empty())
 583         return nullptr;
 584
 585     size_t length = data.size();
 586
 587     flData = static_cast<float *>(malloc(sizeof(float) * length));
 588     if(!flData) {
 589         return nullptr;
 590     }
 591
 592     for(size_t i = 0; i<length; i+= 2) {
 593         int32_t lat = data[i];
 594         int32_t lon = data[i+1];
 595
 596         flData[i] = ZDFixedPointToFloat(lat, 90, library->precision);
 597         flData[i+1] = ZDFixedPointToFloat(lon, 180, library->precision);
 598     }
 599
 600     if(lengthPtr) {
 601         *lengthPtr = length;
 602     }
 603
 604     return flData;
 605 }
 606
 607 static ZDLookupResult ZDPointInPolygon(const ZoneDetect *library, uint32_t polygonIndex, int32_t latFixedPoint, int32_t lonFixedPoint, uint64_t *distanceSqrMin)
 608 {
 609     int32_t pointLat, pointLon, prevLat = 0, prevLon = 0;
 610     int prevQuadrant = 0, winding = 0;
 611
 612     uint8_t first = 1;
 613
 614     struct Reader reader;
 615     ZDReaderInit(&reader, library, polygonIndex);
 616
 617     while(true) {
 618         int result = ZDReaderGetPoint(&reader, &pointLat, &pointLon);
 619         if(result < 0) {
 620             return ZD_LOOKUP_PARSE_ERROR;
 621         } else if(result == 0) {
 622             break;
 623         }
 624
 625         /* Check if point is ON the border */
 626         if(pointLat == latFixedPoint && pointLon == lonFixedPoint) {
 627             if(distanceSqrMin) *distanceSqrMin = 0;
 628             return ZD_LOOKUP_ON_BORDER_VERTEX;
 629         }
 630
 631         /* Find quadrant */
 632         int quadrant;
 633         if(pointLat >= latFixedPoint) {
 634             if(pointLon >= lonFixedPoint) {
 635                 quadrant = 0;
 636             } else {
 637                 quadrant = 1;
 638             }
 639         } else {
 640             if(pointLon >= lonFixedPoint) {
 641                 quadrant = 3;
 642             } else {
 643                 quadrant = 2;
 644             }
 645         }
 646
 647         if(!first) {
 648             int windingNeedCompare = 0, lineIsStraight = 0;
 649             float a = 0, b = 0;
 650
 651             /* Calculate winding number */
 652             if(quadrant == prevQuadrant) {
 653                 /* Do nothing */
 654             } else if(quadrant == (prevQuadrant + 1) % 4) {
 655                 winding ++;
 656             } else if((quadrant + 1) % 4 == prevQuadrant) {
 657                 winding --;
 658             } else {
 659                 windingNeedCompare = 1;
 660             }
 661
 662             /* Avoid horizontal and vertical lines */
 663             if((pointLon == prevLon || pointLat == prevLat)) {
 664                 lineIsStraight = 1;
 665             }
 666
 667             /* Calculate the parameters of y=ax+b if needed */
 668             if(!lineIsStraight && (distanceSqrMin || windingNeedCompare)) {
 669                 a = (static_cast<float>(pointLat) - static_cast<float>(prevLat)) / (static_cast<float>(pointLon) - static_cast<float>(prevLon));
 670                 b = static_cast<float>(pointLat) - a * static_cast<float>(pointLon);
 671             }
 672
 673             int onStraight = ZDPointInBox(pointLat, latFixedPoint, prevLat, pointLon, lonFixedPoint, prevLon);
 674             if(lineIsStraight && (onStraight || windingNeedCompare)) {
 675                 if(distanceSqrMin) *distanceSqrMin = 0;
 676                 return ZD_LOOKUP_ON_BORDER_SEGMENT;
 677             }
 678
 679             /* Jumped two quadrants. */
 680             if(windingNeedCompare) {
 681                 /* Check if the target is on the border */
 682                 const auto intersectLon = static_cast<int32_t>((static_cast<float>(latFixedPoint) - b) / a);
 683                 if(intersectLon >= lonFixedPoint-1 && intersectLon <= lonFixedPoint+1) {
 684                     if(distanceSqrMin) *distanceSqrMin = 0;
 685                     return ZD_LOOKUP_ON_BORDER_SEGMENT;
 686                 }
 687
 688                 /* Ok, it's not. In which direction did we go round the target? */
 689                 const int sign = (intersectLon < lonFixedPoint) ? 2 : -2;
 690                 if(quadrant == 2 || quadrant == 3) {
 691                     winding += sign;
 692                 } else {
 693                     winding -= sign;
 694                 }
 695             }
 696
 697             /* Calculate closest point on line (if needed) */
 698             if(distanceSqrMin) {
 699                 float closestLon, closestLat;
 700                 if(!lineIsStraight) {
 701                     closestLon = (static_cast<float>(lonFixedPoint) + a * static_cast<float>(latFixedPoint) - a * b) / (a * a + 1);
 702                     closestLat = (a * (static_cast<float>(lonFixedPoint) + a * static_cast<float>(latFixedPoint)) + b) / (a * a + 1);
 703                 } else {
 704                     if(pointLon == prevLon) {
 705                         closestLon = static_cast<float>(pointLon);
 706                         closestLat = static_cast<float>(latFixedPoint);
 707                     } else {
 708                         closestLon = static_cast<float>(lonFixedPoint);
 709                         closestLat = static_cast<float>(pointLat);
 710                     }
 711                 }
 712
 713                 const int closestInBox = ZDPointInBox(pointLon, static_cast<int32_t>(closestLon), prevLon, pointLat, static_cast<int32_t>(closestLat), prevLat);
 714
 715                 int64_t diffLat, diffLon;
 716                 if(closestInBox) {
 717                     /* Calculate squared distance to segment. */
 718                     diffLat = static_cast<int64_t>(closestLat - static_cast<float>(latFixedPoint));
 719                     diffLon = static_cast<int64_t>(closestLon - static_cast<float>(lonFixedPoint));
 720                 } else {
 721                     /*
 722                      * Calculate squared distance to vertices
 723                      * It is enough to check the current point since the polygon is closed.
 724                      */
 725                     diffLat = static_cast<int64_t>(pointLat - latFixedPoint);
 726                     diffLon = static_cast<int64_t>(pointLon - lonFixedPoint);
 727                 }
 728
 729                 /* Note: lon has half scale */
 730                 uint64_t distanceSqr = static_cast<uint64_t>(diffLat * diffLat) + static_cast<uint64_t>(diffLon * diffLon) * 4;
 731                 if(distanceSqr < *distanceSqrMin) *distanceSqrMin = distanceSqr;
 732             }
 733         }
 734
 735         prevQuadrant = quadrant;
 736         prevLat = pointLat;
 737         prevLon = pointLon;
 738         first = 0;
 739     };
 740
 741     if(winding == -4) {
 742         return ZD_LOOKUP_IN_ZONE;
 743     } else if(winding == 4) {
 744         return ZD_LOOKUP_IN_EXCLUDED_ZONE;
 745     } else if(winding == 0) {
 746         return ZD_LOOKUP_NOT_IN_ZONE;
 747     }
 748
 749     /* Should not happen */
 750     if(distanceSqrMin) *distanceSqrMin = 0;
 751     return ZD_LOOKUP_ON_BORDER_SEGMENT;
 752 }
 753
 754 void ZDCloseDatabase(ZoneDetect *library)
 755 {
 756     if(library) {
 757         if(library->fieldNames) {
 758             size_t i;
 759             for(i = 0; i < static_cast<size_t>(library->numFields); i++) {
 760                 if(library->fieldNames[i]) {
 761                     free(library->fieldNames[i]);
 762                 }
 763             }
 764             free(library->fieldNames);
 765         }
 766         if(library->notice) {
 767             free(library->notice);
 768         }
 769
 770         if(library->closeType == 0) {
 771 #if defined(_MSC_VER) || defined(__MINGW32__)
 772             if(library->mapping && !UnmapViewOfFile(library->mapping)) zdError(ZD_E_DB_MUNMAP_MSVIEW, (int)GetLastError());
 773             if(library->fdMap && !CloseHandle(library->fdMap))         zdError(ZD_E_DB_MUNMAP, (int)GetLastError());
 774             if(library->fd && !CloseHandle(library->fd))               zdError(ZD_E_DB_CLOSE, (int)GetLastError());
 775 #elif defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
 776             if(library->mapping && munmap(library->mapping, static_cast<size_t>(library->length))) zdError(ZD_E_DB_MUNMAP, 0);
 777             if(library->fd >= 0 && close(library->fd))                                  zdError(ZD_E_DB_CLOSE, 0);
 778 #endif
 779         }
 780
 781         free(library);
 782     }
 783 }
 784
 785 struct ZoneDetectDeleter {
 786     void operator()(ZoneDetect *library)
 787     {
 788         ZDCloseDatabase(library);
 789     }
 790 };
 791
 792 using ZoneDetectPtr = std::unique_ptr<ZoneDetect, ZoneDetectDeleter>;
 793
 794 ZoneDetect *ZDOpenDatabaseFromMemory(void* buffer, size_t length)
 795 {
 796     ZoneDetectPtr library{static_cast<ZoneDetect *>(calloc(1, sizeof(ZoneDetect)))};
 797
 798     if(library) {
 799         library->closeType = 1;
 800         library->length = static_cast<long int>(length);
 801
 802         if(library->length <= 0) {
 803 #if defined(_MSC_VER) || defined(__MINGW32__) || defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
 804             zdError(ZD_E_DB_SEEK, errno);
 805 #else
 806             zdError(ZD_E_DB_SEEK, 0);
 807 #endif
 808             return nullptr;
 809         }
 810
 811         library->mapping = static_cast<uint8_t *>(buffer);
 812
 813         /* Parse the header */
 814         if(ZDParseHeader(library.get())) {
 815             zdError(ZD_E_PARSE_HEADER, 0);
 816             return nullptr;
 817         }
 818     }
 819
 820     return library.release();
 821 }
 822
 823 ZoneDetect *ZDOpenDatabase(const char *path)
 824 {
 825     ZoneDetectPtr library{static_cast<ZoneDetect *>(calloc(1, sizeof(ZoneDetect)))};
 826
 827     if(library) {
 828 #if defined(_MSC_VER) || defined(__MINGW32__)
 829         library->fd = CreateFile(path, GENERIC_READ, 0, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
 830         if (library->fd == INVALID_HANDLE_VALUE) {
 831             zdError(ZD_E_DB_OPEN, (int)GetLastError());
 832             return nullptr;
 833         }
 834
 835         const DWORD fsize = GetFileSize(library->fd, NULL);
 836         if (fsize == INVALID_FILE_SIZE) {
 837             zdError(ZD_E_DB_SEEK, (int)GetLastError());
 838             return nullptr;
 839         }
 840         library->length = (int32_t)fsize;
 841
 842         library->fdMap = CreateFileMappingA(library->fd, NULL, PAGE_READONLY, 0, 0, NULL);
 843         if (!library->fdMap) {
 844             zdError(ZD_E_DB_MMAP, (int)GetLastError());
 845             return nullptr;
 846         }
 847
 848         library->mapping = MapViewOfFile(library->fdMap, FILE_MAP_READ, 0, 0, 0);
 849         if (!library->mapping) {
 850             zdError(ZD_E_DB_MMAP_MSVIEW, (int)GetLastError());
 851             return nullptr;
 852         }
 853 #elif defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
 854         library->fd = open(path, O_RDONLY | O_CLOEXEC);
 855         if(library->fd < 0) {
 856             zdError(ZD_E_DB_OPEN, errno);
 857             return nullptr;
 858         }
 859
 860         library->length = lseek(library->fd, 0, SEEK_END);
 861         if(library->length <= 0 || library->length > 50331648) {
 862             zdError(ZD_E_DB_SEEK, errno);
 863             return nullptr;
 864         }
 865         lseek(library->fd, 0, SEEK_SET);
 866
 867         library->mapping = static_cast<uint8_t *>(mmap(nullptr, static_cast<size_t>(library->length), PROT_READ, MAP_PRIVATE | MAP_FILE, library->fd, 0));
 868         if(library->mapping == MAP_FAILED) {
 869             zdError(ZD_E_DB_MMAP, errno);
 870             return nullptr;
 871         }
 872 #endif
 873
 874         /* Parse the header */
 875         if(ZDParseHeader(library.get())) {
 876             zdError(ZD_E_PARSE_HEADER, 0);
 877             return nullptr;
 878         }
 879     }
 880
 881     return library.release();
 882 }
 883
 884 ZoneDetectResult *ZDLookup(const ZoneDetect *library, float lat, float lon, float *safezone)
 885 {
 886     const int32_t latFixedPoint = ZDFloatToFixedPoint(lat, 90, library->precision);
 887     const int32_t lonFixedPoint = ZDFloatToFixedPoint(lon, 180, library->precision);
 888     size_t numResults = 0;
 889     auto distanceSqrMin = static_cast<uint64_t>(-1);
 890
 891     /* Iterate over all polygons */
 892     uint32_t bboxIndex = library->bboxOffset;
 893     uint32_t metadataIndex = 0;
 894     uint32_t polygonIndex = 0;
 895
 896     auto results = static_cast<ZoneDetectResult *>(malloc(sizeof(ZoneDetectResult)));
 897     if(!results) {
 898         return nullptr;
 899     }
 900
 901     uint32_t polygonId = 0;
 902
 903     while(bboxIndex < library->metadataOffset) {
 904         int32_t minLat, minLon, maxLat, maxLon, metadataIndexDelta;
 905         uint64_t polygonIndexDelta;
 906         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &minLat)) break;
 907         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &minLon)) break;
 908         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &maxLat)) break;
 909         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &maxLon)) break;
 910         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &metadataIndexDelta)) break;
 911         if(!ZDDecodeVariableLengthUnsigned(library, &bboxIndex, &polygonIndexDelta)) break;
 912
 913         metadataIndex += static_cast<uint32_t>(metadataIndexDelta);
 914         polygonIndex += static_cast<uint32_t>(polygonIndexDelta);
 915
 916         if(latFixedPoint >= minLat) {
 917             if(latFixedPoint <= maxLat &&
 918                     lonFixedPoint >= minLon &&
 919                     lonFixedPoint <= maxLon) {
 920
 921                 const ZDLookupResult lookupResult = ZDPointInPolygon(library, library->dataOffset + polygonIndex, latFixedPoint, lonFixedPoint, (safezone) ? &distanceSqrMin : nullptr);
 922                 if(lookupResult == ZD_LOOKUP_PARSE_ERROR) {
 923                     break;
 924                 } else if(lookupResult != ZD_LOOKUP_NOT_IN_ZONE) {
 925                     auto newResults = static_cast<ZoneDetectResult *>(realloc(results, sizeof(ZoneDetectResult) * (numResults + 2)));
 926
 927                     if(newResults) {
 928                         results = newResults;
 929                         results[numResults].polygonId = polygonId;
 930                         results[numResults].metaId = metadataIndex;
 931                         results[numResults].numFields = library->numFields;
 932                         results[numResults].fieldNames = library->fieldNames;
 933                         results[numResults].lookupResult = lookupResult;
 934
 935                         numResults++;
 936                     } else {
 937                         break;
 938                     }
 939                 }
 940             }
 941         } else {
 942             /* The data is sorted along minLat */
 943             break;
 944         }
 945
 946         polygonId++;
 947     }
 948
 949     /* Clean up results */
 950     size_t i;
 951     for(i = 0; i < numResults; i++) {
 952         int insideSum = 0;
 953         ZDLookupResult overrideResult = ZD_LOOKUP_IGNORE;
 954         size_t j;
 955         for(j = i; j < numResults; j++) {
 956             if(results[i].metaId == results[j].metaId) {
 957                 ZDLookupResult tmpResult = results[j].lookupResult;
 958                 results[j].lookupResult = ZD_LOOKUP_IGNORE;
 959
 960                 /* This is the same result. Is it an exclusion zone? */
 961                 if(tmpResult == ZD_LOOKUP_IN_ZONE) {
 962                     insideSum++;
 963                 } else if(tmpResult == ZD_LOOKUP_IN_EXCLUDED_ZONE) {
 964                     insideSum--;
 965                 } else {
 966                     /* If on the bodrder then the final result is on the border */
 967                     overrideResult = tmpResult;
 968                 }
 969
 970             }
 971         }
 972
 973         if(overrideResult != ZD_LOOKUP_IGNORE) {
 974             results[i].lookupResult = overrideResult;
 975         } else {
 976             if(insideSum) {
 977                 results[i].lookupResult = ZD_LOOKUP_IN_ZONE;
 978             }
 979         }
 980     }
 981
 982     /* Remove zones to ignore */
 983     size_t newNumResults = 0;
 984     for(i = 0; i < numResults; i++) {
 985         if(results[i].lookupResult != ZD_LOOKUP_IGNORE) {
 986             results[newNumResults] = results[i];
 987             newNumResults++;
 988         }
 989     }
 990     numResults = newNumResults;
 991
 992     /* Lookup metadata */
 993     for(i = 0; i < numResults; i++) {
 994         uint32_t tmpIndex = library->metadataOffset + results[i].metaId;
 995         results[i].data = static_cast<char **>(malloc(library->numFields * sizeof *results[i].data));
 996         if(results[i].data) {
 997             size_t j;
 998             for(j = 0; j < library->numFields; j++) {
 999                 results[i].data[j] = ZDParseString(library, &tmpIndex);
1000                 if (!results[i].data[j]) {
1001                     /* free all allocated memory */
1002                     size_t m;
1003                     for(m = 0; m < j; m++) {
1004                         if(results[i].data[m]) {
1005                             free(results[i].data[m]);
1006                         }
1007                     }
1008                     size_t k;
1009                     for(k = 0; k < i; k++) {
1010                         size_t l;
1011                         for(l = 0; l < static_cast<size_t>(results[k].numFields); l++) {
1012                             if(results[k].data[l]) {
1013                                 free(results[k].data[l]);
1014                             }
1015                         }
1016                         if (results[k].data) {
1017                             free(results[k].data);
1018                         }
1019                     }
1020                     free(results);
1021                     return nullptr;
1022                 }
1023             }
1024         }
1025         else {
1026             /* free all allocated memory */
1027             size_t k;
1028             for(k = 0; k < i; k++) {
1029                 size_t l;
1030                 for(l = 0; l < static_cast<size_t>(results[k].numFields); l++) {
1031                     if(results[k].data[l]) {
1032                         free(results[k].data[l]);
1033                     }
1034                 }
1035                 if (results[k].data) {
1036                     free(results[k].data);
1037                 }
1038             }
1039             free(results);
1040             return nullptr;
1041         }
1042     }
1043
1044     /* Write end marker */
1045     results[numResults].lookupResult = ZD_LOOKUP_END;
1046     results[numResults].numFields = 0;
1047     results[numResults].fieldNames = nullptr;
1048     results[numResults].data = nullptr;
1049
1050     if(safezone) {
1051         *safezone = sqrtf(static_cast<float>(distanceSqrMin)) * 90 / static_cast<float>(1 << (library->precision - 1));
1052     }
1053
1054     return results;
1055 }
1056
1057 void ZDFreeResults(ZoneDetectResult *results)
1058 {
1059     unsigned int index = 0;
1060
1061     if(!results) {
1062         return;
1063     }
1064
1065     while(results[index].lookupResult != ZD_LOOKUP_END) {
1066         if(results[index].data) {
1067             size_t i;
1068             for(i = 0; i < static_cast<size_t>(results[index].numFields); i++) {
1069                 if(results[index].data[i]) {
1070                     free(results[index].data[i]);
1071                 }
1072             }
1073             free(results[index].data);
1074         }
1075         index++;
1076     }
1077     free(results);
1078 }
1079
1080 const char *ZDGetNotice(const ZoneDetect *library)
1081 {
1082     return library->notice;
1083 }
1084
1085 uint8_t ZDGetTableType(const ZoneDetect *library)
1086 {
1087     return library->tableType;
1088 }
1089
1090 const char *ZDLookupResultToString(ZDLookupResult result)
1091 {
1092     switch(result) {
1093         case ZD_LOOKUP_IGNORE:
1094             return "Ignore";
1095         case ZD_LOOKUP_END:
1096             return "End";
1097         case ZD_LOOKUP_PARSE_ERROR:
1098             return "Parsing error";
1099         case ZD_LOOKUP_NOT_IN_ZONE:
1100             return "Not in zone";
1101         case ZD_LOOKUP_IN_ZONE:
1102             return "In zone";
1103         case ZD_LOOKUP_IN_EXCLUDED_ZONE:
1104             return "In excluded zone";
1105         case ZD_LOOKUP_ON_BORDER_VERTEX:
1106             return "Target point is border vertex";
1107         case ZD_LOOKUP_ON_BORDER_SEGMENT:
1108             return "Target point is on border";
1109     }
1110
1111     return "Unknown";
1112 }
1113
1114 #define ZD_E_COULD_NOT(msg) "could not " msg
1115
1116 const char *ZDGetErrorString(int errZD)
1117 {
1118     switch (static_cast<enum ZDInternalError>(errZD)) {
1119         default:
1120             assert(0);
1121         case ZD_OK                :
1122             return "";
1123         case ZD_E_DB_OPEN         :
1124             return ZD_E_COULD_NOT("open database file");
1125         case ZD_E_DB_SEEK         :
1126             return ZD_E_COULD_NOT("retrieve database file size");
1127         case ZD_E_DB_MMAP         :
1128             return ZD_E_COULD_NOT("map database file to system memory");
1129 #if defined(_MSC_VER) || defined(__MINGW32__)
1130         case ZD_E_DB_MMAP_MSVIEW  :
1131             return ZD_E_COULD_NOT("open database file view");
1132         case ZD_E_DB_MAP_EXCEPTION:
1133             return "I/O exception occurred while accessing database file view";
1134         case ZD_E_DB_MUNMAP_MSVIEW:
1135             return ZD_E_COULD_NOT("close database file view");
1136 #endif
1137         case ZD_E_DB_MUNMAP       :
1138             return ZD_E_COULD_NOT("unmap database");
1139         case ZD_E_DB_CLOSE        :
1140             return ZD_E_COULD_NOT("close database file");
1141         case ZD_E_PARSE_HEADER    :
1142             return ZD_E_COULD_NOT("parse database header");
1143     }
1144 }
1145
1146 #undef ZD_E_COULD_NOT
1147
1148 int ZDSetErrorHandler(void (*handler)(int, int))
1149 {
1150     zdErrorHandler = handler;
1151     return 0;
1152 }
1153
1154 char* ZDHelperSimpleLookupString(const ZoneDetect* library, float lat, float lon)
1155 {
1156     std::unique_ptr<ZoneDetectResult, decltype(&ZDFreeResults)> result{ZDLookup(library, lat, lon, nullptr), ZDFreeResults};
1157     if(!result) {
1158         return nullptr;
1159     }
1160
1161     char* output = nullptr;
1162     size_t length = 0;
1163     char* strings[2] = {nullptr};
1164
1165     if(result->lookupResult == ZD_LOOKUP_END) {
1166         return nullptr;
1167     }
1168
1169     for(int i = 0; i < result->numFields; i++) {
1170         if(result->fieldNames[i] && result->data[i]) {
1171             if(library->tableType == 'T') {
1172                 if(!strcmp(result->fieldNames[i], "TimezoneIdPrefix")) {
1173                     strings[0] = result->data[i];
1174                 }
1175                 if(!strcmp(result->fieldNames[i], "TimezoneId")) {
1176                     strings[1] = result->data[i];
1177                 }
1178             }
1179             if(library->tableType == 'C') {
1180                 if(!strcmp(result->fieldNames[i], "Name")) {
1181                     strings[0] = result->data[i];
1182                 }
1183             }
1184         }
1185     }
1186
1187     for(const auto& string : strings) {
1188         if(string) {
1189             size_t partLength = strlen(string);
1190             if(partLength > 512) {
1191                 return nullptr;
1192             }
1193             length += partLength;
1194         }
1195     }
1196
1197     if(length == 0) {
1198         return nullptr;
1199     }
1200
1201     length += 1;
1202
1203     output = static_cast<char*>(malloc(length));
1204     if(output) {
1205         output[0] = 0;
1206         for(const auto& string : strings) {
1207             if(string) {
1208                 strcat(output + strlen(output), string);
1209             }
1210         }
1211     }
1212
1213     return output;
1214 }