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