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) != 0) {
 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;
 386     int32_t diffLon = 0;
 387
 388     while(true) {
 389         if(reader->done > 1) {
 390             return 0;
 391         }
 392
 393         if(reader->first && reader->library->version == 0) {
 394             if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, &reader->numVertices)) return -1;
 395             if(!reader->numVertices) return -1;
 396         }
 397
 398         uint8_t referenceDone = 0;
 399
 400         if(reader->library->version == 1) {
 401             uint64_t point = 0;
 402
 403             if(!reader->referenceDirection) {
 404                 if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, &point)) return -1;
 405             } else {
 406                 if(reader->referenceDirection > 0) {
 407                     /* Read reference forward */
 408                     if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->referenceStart, &point)) return -1;
 409                     if(reader->referenceStart >= reader->referenceEnd) {
 410                         referenceDone = 1;
 411                     }
 412                 } else if(reader->referenceDirection < 0) {
 413                     /* Read reference backwards */
 414                     if(!ZDDecodeVariableLengthUnsignedReverse(reader->library, &reader->referenceStart, &point)) return -1;
 415                     if(reader->referenceStart <= reader->referenceEnd) {
 416                         referenceDone = 1;
 417                     }
 418                 }
 419             }
 420
 421             if(!point) {
 422                 /* This is a special marker, it is not allowed in reference mode */
 423                 if(reader->referenceDirection) {
 424                     return -1;
 425                 }
 426
 427                 uint64_t value;
 428                 if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, &value)) return -1;
 429
 430                 if(value == 0) {
 431                     reader->done = 2;
 432                 } else if(value == 1) {
 433                     int32_t diff;
 434                     int64_t start;
 435                     if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, reinterpret_cast<uint64_t*>(&start))) return -1;
 436                     if(!ZDDecodeVariableLengthSigned(reader->library, &reader->polygonIndex, &diff)) return -1;
 437
 438                     reader->referenceStart = reader->library->dataOffset+static_cast<uint32_t>(start);
 439                     reader->referenceEnd = reader->library->dataOffset+static_cast<uint32_t>(start + diff);
 440                     reader->referenceDirection = diff;
 441                     if(diff < 0) {
 442                         reader->referenceStart--;
 443                         reader->referenceEnd--;
 444                     }
 445                     continue;
 446                 }
 447             } else {
 448                 ZDDecodePoint(point, &diffLat, &diffLon);
 449                 if(reader->referenceDirection < 0) {
 450                     diffLat = -diffLat;
 451                     diffLon = -diffLon;
 452                 }
 453             }
 454         }
 455
 456         if(reader->library->version == 0) {
 457             if(!ZDDecodeVariableLengthSigned(reader->library, &reader->polygonIndex, &diffLat)) return -1;
 458             if(!ZDDecodeVariableLengthSigned(reader->library, &reader->polygonIndex, &diffLon)) return -1;
 459         }
 460
 461         if(!reader->done) {
 462             reader->pointLat += diffLat;
 463             reader->pointLon += diffLon;
 464             if(reader->first) {
 465                 reader->firstLat = reader->pointLat;
 466                 reader->firstLon = reader->pointLon;
 467             }
 468         } else {
 469             /* Close the polygon (the closing point is not encoded) */
 470             reader->pointLat = reader->firstLat;
 471             reader->pointLon = reader->firstLon;
 472             reader->done = 2;
 473         }
 474
 475         reader->first = 0;
 476
 477         if(reader->library->version == 0) {
 478             reader->numVertices--;
 479             if(!reader->numVertices) {
 480                 reader->done = 1;
 481             }
 482             if(!diffLat && !diffLon) {
 483                 continue;
 484             }
 485         }
 486
 487         if(referenceDone) {
 488             reader->referenceDirection = 0;
 489         }
 490
 491         break;
 492     }
 493
 494     if(pointLat) {
 495         *pointLat = reader->pointLat;
 496     }
 497
 498     if(pointLon) {
 499         *pointLon = reader->pointLon;
 500     }
 501
 502     return 1;
 503 }
 504
 505 static int ZDFindPolygon(const ZoneDetect *library, uint32_t wantedId, uint32_t* metadataIndexPtr, uint32_t* polygonIndexPtr)
 506 {
 507     uint32_t polygonId = 0;
 508     uint32_t bboxIndex = library->bboxOffset;
 509
 510     uint32_t metadataIndex = 0;
 511     uint32_t polygonIndex = 0;
 512
 513     while(bboxIndex < library->metadataOffset) {
 514         uint64_t polygonIndexDelta;
 515         int32_t metadataIndexDelta;
 516         int32_t tmp;
 517         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
 518         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
 519         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
 520         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
 521         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &metadataIndexDelta)) break;
 522         if(!ZDDecodeVariableLengthUnsigned(library, &bboxIndex, &polygonIndexDelta)) break;
 523
 524         metadataIndex += static_cast<uint32_t>(metadataIndexDelta);
 525         polygonIndex += static_cast<uint32_t>(polygonIndexDelta);
 526
 527         if(polygonId == wantedId) {
 528             if(metadataIndexPtr) {
 529                 metadataIndex += library->metadataOffset;
 530                 *metadataIndexPtr = metadataIndex;
 531             }
 532             if(polygonIndexPtr) {
 533                 polygonIndex += library->dataOffset;
 534                 *polygonIndexPtr = polygonIndex;
 535             }
 536             return 1;
 537         }
 538
 539         polygonId ++;
 540     }
 541
 542     return 0;
 543 }
 544
 545 static std::vector<int32_t> ZDPolygonToListInternal(const ZoneDetect *library, uint32_t polygonIndex)
 546 {
 547     struct Reader reader;
 548     ZDReaderInit(&reader, library, polygonIndex);
 549
 550     constexpr size_t listLength = 2 * 100;
 551     std::vector<int32_t> list;
 552     list.reserve(listLength);
 553
 554     while(true) {
 555         int32_t pointLat;
 556         int32_t pointLon;
 557         int result = ZDReaderGetPoint(&reader, &pointLat, &pointLon);
 558         if(result < 0) {
 559             return {};
 560         }
 561         if(result == 0) {
 562             break;
 563         }
 564
 565         list.push_back(pointLat);
 566         list.push_back(pointLon);
 567
 568         if(list.size() >= 1048576) {
 569             return {};
 570         }
 571     }
 572
 573     return list;
 574 }
 575
 576 float* ZDPolygonToList(const ZoneDetect *library, uint32_t polygonId, size_t* lengthPtr)
 577 {
 578     uint32_t polygonIndex;
 579     float* flData = nullptr;
 580
 581     if (!ZDFindPolygon(library, polygonId, nullptr, &polygonIndex))
 582         return nullptr;
 583
 584     const auto data = ZDPolygonToListInternal(library, polygonIndex);
 585     if (data.empty())
 586         return nullptr;
 587
 588     size_t length = data.size();
 589
 590     flData = static_cast<float *>(malloc(sizeof(float) * length));
 591     if(!flData) {
 592         return nullptr;
 593     }
 594
 595     for(size_t i = 0; i<length; i+= 2) {
 596         int32_t lat = data[i];
 597         int32_t lon = data[i+1];
 598
 599         flData[i] = ZDFixedPointToFloat(lat, 90, library->precision);
 600         flData[i+1] = ZDFixedPointToFloat(lon, 180, library->precision);
 601     }
 602
 603     if(lengthPtr) {
 604         *lengthPtr = length;
 605     }
 606
 607     return flData;
 608 }
 609
 610 static ZDLookupResult ZDPointInPolygon(const ZoneDetect *library, uint32_t polygonIndex, int32_t latFixedPoint, int32_t lonFixedPoint, uint64_t *distanceSqrMin)
 611 {
 612     int32_t pointLat;
 613     int32_t pointLon;
 614     int32_t prevLat = 0;
 615     int32_t prevLon = 0;
 616     int prevQuadrant = 0;
 617     int winding = 0;
 618
 619     uint8_t first = 1;
 620
 621     struct Reader reader;
 622     ZDReaderInit(&reader, library, polygonIndex);
 623
 624     while(true) {
 625         int result = ZDReaderGetPoint(&reader, &pointLat, &pointLon);
 626         if(result < 0) {
 627             return ZD_LOOKUP_PARSE_ERROR;
 628         } if(result == 0) {
 629             break;
 630         }
 631
 632         /* Check if point is ON the border */
 633         if(pointLat == latFixedPoint && pointLon == lonFixedPoint) {
 634             if(distanceSqrMin) *distanceSqrMin = 0;
 635             return ZD_LOOKUP_ON_BORDER_VERTEX;
 636         }
 637
 638         /* Find quadrant */
 639         int quadrant;
 640         if(pointLat >= latFixedPoint) {
 641             if(pointLon >= lonFixedPoint) {
 642                 quadrant = 0;
 643             } else {
 644                 quadrant = 1;
 645             }
 646         } else {
 647             if(pointLon >= lonFixedPoint) {
 648                 quadrant = 3;
 649             } else {
 650                 quadrant = 2;
 651             }
 652         }
 653
 654         if(!first) {
 655             int windingNeedCompare = 0;
 656             int lineIsStraight = 0;
 657             float a = 0;
 658             float b = 0;
 659
 660             /* Calculate winding number */
 661             if(quadrant == prevQuadrant) {
 662                 /* Do nothing */
 663             } else if(quadrant == (prevQuadrant + 1) % 4) {
 664                 winding ++;
 665             } else if((quadrant + 1) % 4 == prevQuadrant) {
 666                 winding --;
 667             } else {
 668                 windingNeedCompare = 1;
 669             }
 670
 671             /* Avoid horizontal and vertical lines */
 672             if((pointLon == prevLon || pointLat == prevLat)) {
 673                 lineIsStraight = 1;
 674             }
 675
 676             /* Calculate the parameters of y=ax+b if needed */
 677             if(!lineIsStraight && (distanceSqrMin || windingNeedCompare)) {
 678                 a = (static_cast<float>(pointLat) - static_cast<float>(prevLat)) / (static_cast<float>(pointLon) - static_cast<float>(prevLon));
 679                 b = static_cast<float>(pointLat) - a * static_cast<float>(pointLon);
 680             }
 681
 682             int onStraight = ZDPointInBox(pointLat, latFixedPoint, prevLat, pointLon, lonFixedPoint, prevLon);
 683             if(lineIsStraight && (onStraight || windingNeedCompare)) {
 684                 if(distanceSqrMin) *distanceSqrMin = 0;
 685                 return ZD_LOOKUP_ON_BORDER_SEGMENT;
 686             }
 687
 688             /* Jumped two quadrants. */
 689             if(windingNeedCompare) {
 690                 /* Check if the target is on the border */
 691                 const auto intersectLon = static_cast<int32_t>((static_cast<float>(latFixedPoint) - b) / a);
 692                 if(intersectLon >= lonFixedPoint-1 && intersectLon <= lonFixedPoint+1) {
 693                     if(distanceSqrMin) *distanceSqrMin = 0;
 694                     return ZD_LOOKUP_ON_BORDER_SEGMENT;
 695                 }
 696
 697                 /* Ok, it's not. In which direction did we go round the target? */
 698                 const int sign = (intersectLon < lonFixedPoint) ? 2 : -2;
 699                 if(quadrant == 2 || quadrant == 3) {
 700                     winding += sign;
 701                 } else {
 702                     winding -= sign;
 703                 }
 704             }
 705
 706             /* Calculate closest point on line (if needed) */
 707             if(distanceSqrMin) {
 708                 float closestLon;
 709                 float closestLat;
 710                 if(!lineIsStraight) {
 711                     closestLon = (static_cast<float>(lonFixedPoint) + a * static_cast<float>(latFixedPoint) - a * b) / (a * a + 1);
 712                     closestLat = (a * (static_cast<float>(lonFixedPoint) + a * static_cast<float>(latFixedPoint)) + b) / (a * a + 1);
 713                 } else {
 714                     if(pointLon == prevLon) {
 715                         closestLon = static_cast<float>(pointLon);
 716                         closestLat = static_cast<float>(latFixedPoint);
 717                     } else {
 718                         closestLon = static_cast<float>(lonFixedPoint);
 719                         closestLat = static_cast<float>(pointLat);
 720                     }
 721                 }
 722
 723                 const int closestInBox = ZDPointInBox(pointLon, static_cast<int32_t>(closestLon), prevLon, pointLat, static_cast<int32_t>(closestLat), prevLat);
 724
 725                 int64_t diffLat;
 726                 int64_t diffLon;
 727                 if(closestInBox) {
 728                     /* Calculate squared distance to segment. */
 729                     diffLat = static_cast<int64_t>(closestLat - static_cast<float>(latFixedPoint));
 730                     diffLon = static_cast<int64_t>(closestLon - static_cast<float>(lonFixedPoint));
 731                 } else {
 732                     /*
 733                      * Calculate squared distance to vertices
 734                      * It is enough to check the current point since the polygon is closed.
 735                      */
 736                     diffLat = static_cast<int64_t>(pointLat - latFixedPoint);
 737                     diffLon = static_cast<int64_t>(pointLon - lonFixedPoint);
 738                 }
 739
 740                 /* Note: lon has half scale */
 741                 uint64_t distanceSqr = static_cast<uint64_t>(diffLat * diffLat) + static_cast<uint64_t>(diffLon * diffLon) * 4;
 742                 if(distanceSqr < *distanceSqrMin) *distanceSqrMin = distanceSqr;
 743             }
 744         }
 745
 746         prevQuadrant = quadrant;
 747         prevLat = pointLat;
 748         prevLon = pointLon;
 749         first = 0;
 750     };
 751
 752     if(winding == -4) {
 753         return ZD_LOOKUP_IN_ZONE;
 754     } if(winding == 4) {
 755         return ZD_LOOKUP_IN_EXCLUDED_ZONE;
 756     } if(winding == 0) {
 757         return ZD_LOOKUP_NOT_IN_ZONE;
 758     }
 759
 760     /* Should not happen */
 761     if(distanceSqrMin) *distanceSqrMin = 0;
 762     return ZD_LOOKUP_ON_BORDER_SEGMENT;
 763 }
 764
 765 void ZDCloseDatabase(ZoneDetect *library)
 766 {
 767     if(library) {
 768         if(library->fieldNames) {
 769             size_t i;
 770             for(i = 0; i < static_cast<size_t>(library->numFields); i++) {
 771                 if(library->fieldNames[i]) {
 772                     free(library->fieldNames[i]);
 773                 }
 774             }
 775             free(library->fieldNames);
 776         }
 777         if(library->notice) {
 778             free(library->notice);
 779         }
 780
 781         if(library->closeType == 0) {
 782 #if defined(_MSC_VER) || defined(__MINGW32__)
 783             if(library->mapping && !UnmapViewOfFile(library->mapping)) zdError(ZD_E_DB_MUNMAP_MSVIEW, (int)GetLastError());
 784             if(library->fdMap && !CloseHandle(library->fdMap))         zdError(ZD_E_DB_MUNMAP, (int)GetLastError());
 785             if(library->fd && !CloseHandle(library->fd))               zdError(ZD_E_DB_CLOSE, (int)GetLastError());
 786 #elif defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
 787             if(library->mapping && munmap(library->mapping, static_cast<size_t>(library->length))) zdError(ZD_E_DB_MUNMAP, 0);
 788             if(library->fd >= 0 && close(library->fd))                                  zdError(ZD_E_DB_CLOSE, 0);
 789 #endif
 790         }
 791
 792         free(library);
 793     }
 794 }
 795
 796 struct ZoneDetectDeleter {
 797     void operator()(ZoneDetect *library)
 798     {
 799         ZDCloseDatabase(library);
 800     }
 801 };
 802
 803 using ZoneDetectPtr = std::unique_ptr<ZoneDetect, ZoneDetectDeleter>;
 804
 805 ZoneDetect *ZDOpenDatabaseFromMemory(void* buffer, size_t length)
 806 {
 807     ZoneDetectPtr library{static_cast<ZoneDetect *>(calloc(1, sizeof(ZoneDetect)))};
 808
 809     if(library) {
 810         library->closeType = 1;
 811         library->length = static_cast<long int>(length);
 812
 813         if(library->length <= 0) {
 814 #if defined(_MSC_VER) || defined(__MINGW32__) || defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
 815             zdError(ZD_E_DB_SEEK, errno);
 816 #else
 817             zdError(ZD_E_DB_SEEK, 0);
 818 #endif
 819             return nullptr;
 820         }
 821
 822         library->mapping = static_cast<uint8_t *>(buffer);
 823
 824         /* Parse the header */
 825         if(ZDParseHeader(library.get())) {
 826             zdError(ZD_E_PARSE_HEADER, 0);
 827             return nullptr;
 828         }
 829     }
 830
 831     return library.release();
 832 }
 833
 834 ZoneDetect *ZDOpenDatabase(const char *path)
 835 {
 836     ZoneDetectPtr library{static_cast<ZoneDetect *>(calloc(1, sizeof(ZoneDetect)))};
 837
 838     if(library) {
 839 #if defined(_MSC_VER) || defined(__MINGW32__)
 840         library->fd = CreateFile(path, GENERIC_READ, 0, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
 841         if (library->fd == INVALID_HANDLE_VALUE) {
 842             zdError(ZD_E_DB_OPEN, (int)GetLastError());
 843             return nullptr;
 844         }
 845
 846         const DWORD fsize = GetFileSize(library->fd, NULL);
 847         if (fsize == INVALID_FILE_SIZE) {
 848             zdError(ZD_E_DB_SEEK, (int)GetLastError());
 849             return nullptr;
 850         }
 851         library->length = (int32_t)fsize;
 852
 853         library->fdMap = CreateFileMappingA(library->fd, NULL, PAGE_READONLY, 0, 0, NULL);
 854         if (!library->fdMap) {
 855             zdError(ZD_E_DB_MMAP, (int)GetLastError());
 856             return nullptr;
 857         }
 858
 859         library->mapping = MapViewOfFile(library->fdMap, FILE_MAP_READ, 0, 0, 0);
 860         if (!library->mapping) {
 861             zdError(ZD_E_DB_MMAP_MSVIEW, (int)GetLastError());
 862             return nullptr;
 863         }
 864 #elif defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
 865         library->fd = open(path, O_RDONLY | O_CLOEXEC);
 866         if(library->fd < 0) {
 867             zdError(ZD_E_DB_OPEN, errno);
 868             return nullptr;
 869         }
 870
 871         library->length = lseek(library->fd, 0, SEEK_END);
 872         if(library->length <= 0 || library->length > 50331648) {
 873             zdError(ZD_E_DB_SEEK, errno);
 874             return nullptr;
 875         }
 876         lseek(library->fd, 0, SEEK_SET);
 877
 878         library->mapping = static_cast<uint8_t *>(mmap(nullptr, static_cast<size_t>(library->length), PROT_READ, MAP_PRIVATE | MAP_FILE, library->fd, 0));
 879         if(library->mapping == MAP_FAILED) {
 880             zdError(ZD_E_DB_MMAP, errno);
 881             return nullptr;
 882         }
 883 #endif
 884
 885         /* Parse the header */
 886         if(ZDParseHeader(library.get())) {
 887             zdError(ZD_E_PARSE_HEADER, 0);
 888             return nullptr;
 889         }
 890     }
 891
 892     return library.release();
 893 }
 894
 895 ZoneDetectResult *ZDLookup(const ZoneDetect *library, float lat, float lon, float *safezone)
 896 {
 897     const int32_t latFixedPoint = ZDFloatToFixedPoint(lat, 90, library->precision);
 898     const int32_t lonFixedPoint = ZDFloatToFixedPoint(lon, 180, library->precision);
 899     size_t numResults = 0;
 900     auto distanceSqrMin = static_cast<uint64_t>(-1);
 901
 902     /* Iterate over all polygons */
 903     uint32_t bboxIndex = library->bboxOffset;
 904     uint32_t metadataIndex = 0;
 905     uint32_t polygonIndex = 0;
 906
 907     auto results = static_cast<ZoneDetectResult *>(malloc(sizeof(ZoneDetectResult)));
 908     if(!results) {
 909         return nullptr;
 910     }
 911
 912     uint32_t polygonId = 0;
 913
 914     while(bboxIndex < library->metadataOffset) {
 915         int32_t minLat;
 916         int32_t minLon;
 917         int32_t maxLat;
 918         int32_t maxLon;
 919         int32_t metadataIndexDelta;
 920         uint64_t polygonIndexDelta;
 921         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &minLat)) break;
 922         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &minLon)) break;
 923         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &maxLat)) break;
 924         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &maxLon)) break;
 925         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &metadataIndexDelta)) break;
 926         if(!ZDDecodeVariableLengthUnsigned(library, &bboxIndex, &polygonIndexDelta)) break;
 927
 928         metadataIndex += static_cast<uint32_t>(metadataIndexDelta);
 929         polygonIndex += static_cast<uint32_t>(polygonIndexDelta);
 930
 931         if(latFixedPoint >= minLat) {
 932             if(latFixedPoint <= maxLat &&
 933                     lonFixedPoint >= minLon &&
 934                     lonFixedPoint <= maxLon) {
 935
 936                 const ZDLookupResult lookupResult = ZDPointInPolygon(library, library->dataOffset + polygonIndex, latFixedPoint, lonFixedPoint, (safezone) ? &distanceSqrMin : nullptr);
 937                 if(lookupResult == ZD_LOOKUP_PARSE_ERROR) {
 938                     break;
 939                 } if(lookupResult != ZD_LOOKUP_NOT_IN_ZONE) {
 940                     auto newResults = static_cast<ZoneDetectResult *>(realloc(results, sizeof(ZoneDetectResult) * (numResults + 2)));
 941
 942                     if(newResults) {
 943                         results = newResults;
 944                         results[numResults].polygonId = polygonId;
 945                         results[numResults].metaId = metadataIndex;
 946                         results[numResults].numFields = library->numFields;
 947                         results[numResults].fieldNames = library->fieldNames;
 948                         results[numResults].lookupResult = lookupResult;
 949
 950                         numResults++;
 951                     } else {
 952                         break;
 953                     }
 954                 }
 955             }
 956         } else {
 957             /* The data is sorted along minLat */
 958             break;
 959         }
 960
 961         polygonId++;
 962     }
 963
 964     /* Clean up results */
 965     size_t i;
 966     for(i = 0; i < numResults; i++) {
 967         int insideSum = 0;
 968         ZDLookupResult overrideResult = ZD_LOOKUP_IGNORE;
 969         size_t j;
 970         for(j = i; j < numResults; j++) {
 971             if(results[i].metaId == results[j].metaId) {
 972                 ZDLookupResult tmpResult = results[j].lookupResult;
 973                 results[j].lookupResult = ZD_LOOKUP_IGNORE;
 974
 975                 /* This is the same result. Is it an exclusion zone? */
 976                 if(tmpResult == ZD_LOOKUP_IN_ZONE) {
 977                     insideSum++;
 978                 } else if(tmpResult == ZD_LOOKUP_IN_EXCLUDED_ZONE) {
 979                     insideSum--;
 980                 } else {
 981                     /* If on the bodrder then the final result is on the border */
 982                     overrideResult = tmpResult;
 983                 }
 984
 985             }
 986         }
 987
 988         if(overrideResult != ZD_LOOKUP_IGNORE) {
 989             results[i].lookupResult = overrideResult;
 990         } else {
 991             if(insideSum) {
 992                 results[i].lookupResult = ZD_LOOKUP_IN_ZONE;
 993             }
 994         }
 995     }
 996
 997     /* Remove zones to ignore */
 998     size_t newNumResults = 0;
 999     for(i = 0; i < numResults; i++) {
1000         if(results[i].lookupResult != ZD_LOOKUP_IGNORE) {
1001             results[newNumResults] = results[i];
1002             newNumResults++;
1003         }
1004     }
1005     numResults = newNumResults;
1006
1007     /* Lookup metadata */
1008     for(i = 0; i < numResults; i++) {
1009         uint32_t tmpIndex = library->metadataOffset + results[i].metaId;
1010         results[i].data = static_cast<char **>(malloc(library->numFields * sizeof *results[i].data));
1011         if(results[i].data) {
1012             size_t j;
1013             for(j = 0; j < library->numFields; j++) {
1014                 results[i].data[j] = ZDParseString(library, &tmpIndex);
1015                 if (!results[i].data[j]) {
1016                     /* free all allocated memory */
1017                     size_t m;
1018                     for(m = 0; m < j; m++) {
1019                         if(results[i].data[m]) {
1020                             free(results[i].data[m]);
1021                         }
1022                     }
1023                     size_t k;
1024                     for(k = 0; k < i; k++) {
1025                         size_t l;
1026                         for(l = 0; l < static_cast<size_t>(results[k].numFields); l++) {
1027                             if(results[k].data[l]) {
1028                                 free(results[k].data[l]);
1029                             }
1030                         }
1031                         if (results[k].data) {
1032                             free(results[k].data);
1033                         }
1034                     }
1035                     free(results);
1036                     return nullptr;
1037                 }
1038             }
1039         }
1040         else {
1041             /* free all allocated memory */
1042             size_t k;
1043             for(k = 0; k < i; k++) {
1044                 size_t l;
1045                 for(l = 0; l < static_cast<size_t>(results[k].numFields); l++) {
1046                     if(results[k].data[l]) {
1047                         free(results[k].data[l]);
1048                     }
1049                 }
1050                 if (results[k].data) {
1051                     free(results[k].data);
1052                 }
1053             }
1054             free(results);
1055             return nullptr;
1056         }
1057     }
1058
1059     /* Write end marker */
1060     results[numResults].lookupResult = ZD_LOOKUP_END;
1061     results[numResults].numFields = 0;
1062     results[numResults].fieldNames = nullptr;
1063     results[numResults].data = nullptr;
1064
1065     if(safezone) {
1066         *safezone = sqrtf(static_cast<float>(distanceSqrMin)) * 90 / static_cast<float>(1 << (library->precision - 1));
1067     }
1068
1069     return results;
1070 }
1071
1072 void ZDFreeResults(ZoneDetectResult *results)
1073 {
1074     unsigned int index = 0;
1075
1076     if(!results) {
1077         return;
1078     }
1079
1080     while(results[index].lookupResult != ZD_LOOKUP_END) {
1081         if(results[index].data) {
1082             size_t i;
1083             for(i = 0; i < static_cast<size_t>(results[index].numFields); i++) {
1084                 if(results[index].data[i]) {
1085                     free(results[index].data[i]);
1086                 }
1087             }
1088             free(results[index].data);
1089         }
1090         index++;
1091     }
1092     free(results);
1093 }
1094
1095 const char *ZDGetNotice(const ZoneDetect *library)
1096 {
1097     return library->notice;
1098 }
1099
1100 uint8_t ZDGetTableType(const ZoneDetect *library)
1101 {
1102     return library->tableType;
1103 }
1104
1105 const char *ZDLookupResultToString(ZDLookupResult result)
1106 {
1107     switch(result) {
1108         case ZD_LOOKUP_IGNORE:
1109             return "Ignore";
1110         case ZD_LOOKUP_END:
1111             return "End";
1112         case ZD_LOOKUP_PARSE_ERROR:
1113             return "Parsing error";
1114         case ZD_LOOKUP_NOT_IN_ZONE:
1115             return "Not in zone";
1116         case ZD_LOOKUP_IN_ZONE:
1117             return "In zone";
1118         case ZD_LOOKUP_IN_EXCLUDED_ZONE:
1119             return "In excluded zone";
1120         case ZD_LOOKUP_ON_BORDER_VERTEX:
1121             return "Target point is border vertex";
1122         case ZD_LOOKUP_ON_BORDER_SEGMENT:
1123             return "Target point is on border";
1124     }
1125
1126     return "Unknown";
1127 }
1128
1129 #define ZD_E_COULD_NOT(msg) "could not " msg
1130
1131 const char *ZDGetErrorString(int errZD)
1132 {
1133     switch (static_cast<enum ZDInternalError>(errZD)) {
1134         default:
1135             assert(0);
1136         case ZD_OK                :
1137             return "";
1138         case ZD_E_DB_OPEN         :
1139             return ZD_E_COULD_NOT("open database file");
1140         case ZD_E_DB_SEEK         :
1141             return ZD_E_COULD_NOT("retrieve database file size");
1142         case ZD_E_DB_MMAP         :
1143             return ZD_E_COULD_NOT("map database file to system memory");
1144 #if defined(_MSC_VER) || defined(__MINGW32__)
1145         case ZD_E_DB_MMAP_MSVIEW  :
1146             return ZD_E_COULD_NOT("open database file view");
1147         case ZD_E_DB_MAP_EXCEPTION:
1148             return "I/O exception occurred while accessing database file view";
1149         case ZD_E_DB_MUNMAP_MSVIEW:
1150             return ZD_E_COULD_NOT("close database file view");
1151 #endif
1152         case ZD_E_DB_MUNMAP       :
1153             return ZD_E_COULD_NOT("unmap database");
1154         case ZD_E_DB_CLOSE        :
1155             return ZD_E_COULD_NOT("close database file");
1156         case ZD_E_PARSE_HEADER    :
1157             return ZD_E_COULD_NOT("parse database header");
1158     }
1159 }
1160
1161 #undef ZD_E_COULD_NOT
1162
1163 int ZDSetErrorHandler(void (*handler)(int, int))
1164 {
1165     zdErrorHandler = handler;
1166     return 0;
1167 }
1168
1169 char* ZDHelperSimpleLookupString(const ZoneDetect* library, float lat, float lon)
1170 {
1171     std::unique_ptr<ZoneDetectResult, decltype(&ZDFreeResults)> result{ZDLookup(library, lat, lon, nullptr), ZDFreeResults};
1172     if(!result) {
1173         return nullptr;
1174     }
1175
1176     char* output = nullptr;
1177     size_t length = 0;
1178     char* strings[2] = {nullptr};
1179
1180     if(result->lookupResult == ZD_LOOKUP_END) {
1181         return nullptr;
1182     }
1183
1184     for(int i = 0; i < result->numFields; i++) {
1185         if(result->fieldNames[i] && result->data[i]) {
1186             if(library->tableType == 'T') {
1187                 if(!strcmp(result->fieldNames[i], "TimezoneIdPrefix")) {
1188                     strings[0] = result->data[i];
1189                 }
1190                 if(!strcmp(result->fieldNames[i], "TimezoneId")) {
1191                     strings[1] = result->data[i];
1192                 }
1193             }
1194             if(library->tableType == 'C') {
1195                 if(!strcmp(result->fieldNames[i], "Name")) {
1196                     strings[0] = result->data[i];
1197                 }
1198             }
1199         }
1200     }
1201
1202     for(const auto& string : strings) {
1203         if(string) {
1204             size_t partLength = strlen(string);
1205             if(partLength > 512) {
1206                 return nullptr;
1207             }
1208             length += partLength;
1209         }
1210     }
1211
1212     if(length == 0) {
1213         return nullptr;
1214     }
1215
1216     length += 1;
1217
1218     output = static_cast<char*>(malloc(length));
1219     if(output) {
1220         output[0] = 0;
1221         for(const auto& string : strings) {
1222             if(string) {
1223                 strcat(output + strlen(output), string);
1224             }
1225         }
1226     }
1227
1228     return output;
1229 }