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