src/zonedetect.c

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