2 * Copyright (c) 2018, Bertold Van den Bergh (vandenbergh@bertold.org)
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.
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.
32 #if defined(_MSC_VER) || defined(__MINGW32__)
34 #elif defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
44 #include "zonedetect.h"
46 enum ZDInternalError {
51 #if defined(_MSC_VER) || defined(__MINGW32__)
53 ZD_E_DB_MAP_EXCEPTION,
54 ZD_E_DB_MUNMAP_MSVIEW,
62 #if defined(_MSC_VER) || defined(__MINGW32__)
67 #elif defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
86 uint32_t metadataOffset;
90 static void (*zdErrorHandler)(int, int);
91 static void zdError(enum ZDInternalError errZD, int errNative)
93 if (zdErrorHandler) zdErrorHandler(static_cast<int>(errZD), errNative);
96 static int32_t ZDFloatToFixedPoint(float input, float scale, unsigned int precision)
98 const float inputScaled = input / scale;
99 return static_cast<int32_t>(inputScaled * static_cast<float>(1 << (precision - 1)));
102 static float ZDFixedPointToFloat(int32_t input, float scale, unsigned int precision)
104 const float value = static_cast<float>(input) / static_cast<float>(1 << (precision - 1));
105 return value * scale;
108 static unsigned int ZDDecodeVariableLengthUnsigned(const ZoneDetect *library, uint32_t *index, uint64_t *result)
110 if(*index >= static_cast<uint32_t>(library->length)) {
116 #if defined(_MSC_VER)
119 uint8_t *const buffer = library->mapping + *index;
120 uint8_t *const bufferEnd = library->mapping + library->length - 1;
122 unsigned int shift = 0;
124 value |= (((static_cast<uint64_t>(buffer[i])) & UINT8_C(0x7F)) << shift);
127 if(!(buffer[i] & UINT8_C(0x80))) {
132 if(buffer + i > bufferEnd) {
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());
151 static unsigned int ZDDecodeVariableLengthUnsignedReverse(const ZoneDetect *library, uint32_t *index, uint64_t *result)
155 if(*index >= static_cast<uint32_t>(library->length)) {
159 #if defined(_MSC_VER)
163 if(library->mapping[i] & UINT8_C(0x80)) {
172 while(library->mapping[i] & UINT8_C(0x80)) {
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());
193 return ZDDecodeVariableLengthUnsigned(library, &i2, result);
196 static int64_t ZDDecodeUnsignedToSigned(uint64_t value)
198 return (value & 1) ? -static_cast<int64_t>(value / 2) : static_cast<int64_t>(value / 2);
201 static unsigned int ZDDecodeVariableLengthSigned(const ZoneDetect *library, uint32_t *index, int32_t *result)
204 const unsigned int retVal = ZDDecodeVariableLengthUnsigned(library, index, &value);
205 *result = static_cast<int32_t>(ZDDecodeUnsignedToSigned(value));
209 static char *ZDParseString(const ZoneDetect *library, uint32_t *index)
212 if(!ZDDecodeVariableLengthUnsigned(library, index, &strLength)) {
216 uint32_t strOffset = *index;
217 unsigned int remoteStr = 0;
218 if(strLength >= 256) {
219 strOffset = library->metadataOffset + static_cast<uint32_t>(strLength) - 256;
222 if(!ZDDecodeVariableLengthUnsigned(library, &strOffset, &strLength)) {
226 if(strLength > 256) {
231 auto str = static_cast<char *>(malloc(static_cast<size_t>(strLength + 1)));
234 #if defined(_MSC_VER)
238 for(i = 0; i < strLength; i++) {
239 str[i] = static_cast<char>(library->mapping[strOffset + i] ^ UINT8_C(0x80));
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());
253 *index += static_cast<uint32_t>(strLength);
259 static int ZDParseHeader(ZoneDetect *library)
261 if(library->length < 7) {
265 #if defined(_MSC_VER)
268 if(memcmp(library->mapping, "PLB", 3) != 0) {
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());
285 if(library->version >= 2) {
289 uint32_t index = UINT32_C(7);
291 library->fieldNames = static_cast<char **>(malloc(library->numFields * sizeof *library->fieldNames));
292 if (!library->fieldNames) {
297 for(i = 0; i < library->numFields; i++) {
298 library->fieldNames[i] = ZDParseString(library, &index);
301 library->notice = ZDParseString(library, &index);
302 if(!library->notice) {
307 /* Read section sizes */
308 /* By memset: library->bboxOffset = 0 */
310 if(!ZDDecodeVariableLengthUnsigned(library, &index, &tmp)) return -1;
311 library->metadataOffset = static_cast<uint32_t>(tmp) + library->bboxOffset;
313 if(!ZDDecodeVariableLengthUnsigned(library, &index, &tmp))return -1;
314 library->dataOffset = static_cast<uint32_t>(tmp) + library->metadataOffset;
316 if(!ZDDecodeVariableLengthUnsigned(library, &index, &tmp)) return -1;
318 /* Add header size to everything */
319 library->bboxOffset += index;
320 library->metadataOffset += index;
321 library->dataOffset += index;
323 /* Verify file length */
324 if(tmp + library->dataOffset != static_cast<uint32_t>(library->length)) {
331 static int ZDPointInBox(int32_t xl, int32_t x, int32_t xr, int32_t yl, int32_t y, int32_t yr)
333 if((xl <= x && x <= xr) || (xr <= x && x <= xl)) {
334 if((yl <= y && y <= yr) || (yr <= y && y <= yl)) {
342 static uint32_t ZDUnshuffle(uint64_t w)
344 w &= 0x5555555555555555llu;
345 w = (w | (w >> 1)) & 0x3333333333333333llu;
346 w = (w | (w >> 2)) & 0x0F0F0F0F0F0F0F0Fllu;
347 w = (w | (w >> 4)) & 0x00FF00FF00FF00FFllu;
348 w = (w | (w >> 8)) & 0x0000FFFF0000FFFFllu;
349 w = (w | (w >> 16)) & 0x00000000FFFFFFFFllu;
350 return static_cast<uint32_t>(w);
353 static void ZDDecodePoint(uint64_t point, int32_t* lat, int32_t* lon)
355 *lat = static_cast<int32_t>(ZDDecodeUnsignedToSigned(ZDUnshuffle(point)));
356 *lon = static_cast<int32_t>(ZDDecodeUnsignedToSigned(ZDUnshuffle(point >> 1)));
360 const ZoneDetect *library;
361 uint32_t polygonIndex;
363 uint64_t numVertices;
366 uint32_t referenceStart, referenceEnd;
367 int32_t referenceDirection;
369 int32_t pointLat, pointLon;
370 int32_t firstLat, firstLon;
373 static void ZDReaderInit(struct Reader *reader, const ZoneDetect *library, uint32_t polygonIndex)
375 memset(reader, 0, sizeof(*reader));
377 reader->library = library;
378 reader->polygonIndex = polygonIndex;
383 static int ZDReaderGetPoint(struct Reader *reader, int32_t *pointLat, int32_t *pointLon)
385 int32_t diffLat = 0, diffLon = 0;
388 if(reader->done > 1) {
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;
397 uint8_t referenceDone = 0;
399 if(reader->library->version == 1) {
402 if(!reader->referenceDirection) {
403 if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, &point)) return -1;
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) {
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) {
421 /* This is a special marker, it is not allowed in reference mode */
422 if(reader->referenceDirection) {
427 if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, &value)) return -1;
431 } else if(value == 1) {
434 if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, reinterpret_cast<uint64_t*>(&start))) return -1;
435 if(!ZDDecodeVariableLengthSigned(reader->library, &reader->polygonIndex, &diff)) return -1;
437 reader->referenceStart = reader->library->dataOffset+static_cast<uint32_t>(start);
438 reader->referenceEnd = reader->library->dataOffset+static_cast<uint32_t>(start + diff);
439 reader->referenceDirection = diff;
441 reader->referenceStart--;
442 reader->referenceEnd--;
447 ZDDecodePoint(point, &diffLat, &diffLon);
448 if(reader->referenceDirection < 0) {
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;
461 reader->pointLat += diffLat;
462 reader->pointLon += diffLon;
464 reader->firstLat = reader->pointLat;
465 reader->firstLon = reader->pointLon;
468 /* Close the polygon (the closing point is not encoded) */
469 reader->pointLat = reader->firstLat;
470 reader->pointLon = reader->firstLon;
476 if(reader->library->version == 0) {
477 reader->numVertices--;
478 if(!reader->numVertices) {
481 if(!diffLat && !diffLon) {
487 reader->referenceDirection = 0;
494 *pointLat = reader->pointLat;
498 *pointLon = reader->pointLon;
504 static int ZDFindPolygon(const ZoneDetect *library, uint32_t wantedId, uint32_t* metadataIndexPtr, uint32_t* polygonIndexPtr)
506 uint32_t polygonId = 0;
507 uint32_t bboxIndex = library->bboxOffset;
509 uint32_t metadataIndex = 0, polygonIndex = 0;
511 while(bboxIndex < library->metadataOffset) {
512 uint64_t polygonIndexDelta;
513 int32_t metadataIndexDelta;
515 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
516 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
517 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
518 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
519 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &metadataIndexDelta)) break;
520 if(!ZDDecodeVariableLengthUnsigned(library, &bboxIndex, &polygonIndexDelta)) break;
522 metadataIndex += static_cast<uint32_t>(metadataIndexDelta);
523 polygonIndex += static_cast<uint32_t>(polygonIndexDelta);
525 if(polygonId == wantedId) {
526 if(metadataIndexPtr) {
527 metadataIndex += library->metadataOffset;
528 *metadataIndexPtr = metadataIndex;
530 if(polygonIndexPtr) {
531 polygonIndex += library->dataOffset;
532 *polygonIndexPtr = polygonIndex;
543 static std::vector<int32_t> ZDPolygonToListInternal(const ZoneDetect *library, uint32_t polygonIndex)
545 struct Reader reader;
546 ZDReaderInit(&reader, library, polygonIndex);
548 constexpr size_t listLength = 2 * 100;
549 std::vector<int32_t> list;
550 list.reserve(listLength);
553 int32_t pointLat, pointLon;
554 int result = ZDReaderGetPoint(&reader, &pointLat, &pointLon);
562 list.push_back(pointLat);
563 list.push_back(pointLon);
565 if(list.size() >= 1048576) {
573 float* ZDPolygonToList(const ZoneDetect *library, uint32_t polygonId, size_t* lengthPtr)
575 uint32_t polygonIndex;
576 float* flData = nullptr;
578 if (!ZDFindPolygon(library, polygonId, nullptr, &polygonIndex))
581 const auto data = ZDPolygonToListInternal(library, polygonIndex);
585 size_t length = data.size();
587 flData = static_cast<float *>(malloc(sizeof(float) * length));
592 for(size_t i = 0; i<length; i+= 2) {
593 int32_t lat = data[i];
594 int32_t lon = data[i+1];
596 flData[i] = ZDFixedPointToFloat(lat, 90, library->precision);
597 flData[i+1] = ZDFixedPointToFloat(lon, 180, library->precision);
607 static ZDLookupResult ZDPointInPolygon(const ZoneDetect *library, uint32_t polygonIndex, int32_t latFixedPoint, int32_t lonFixedPoint, uint64_t *distanceSqrMin)
609 int32_t pointLat, pointLon, prevLat = 0, prevLon = 0;
610 int prevQuadrant = 0, winding = 0;
614 struct Reader reader;
615 ZDReaderInit(&reader, library, polygonIndex);
618 int result = ZDReaderGetPoint(&reader, &pointLat, &pointLon);
620 return ZD_LOOKUP_PARSE_ERROR;
625 /* Check if point is ON the border */
626 if(pointLat == latFixedPoint && pointLon == lonFixedPoint) {
627 if(distanceSqrMin) *distanceSqrMin = 0;
628 return ZD_LOOKUP_ON_BORDER_VERTEX;
633 if(pointLat >= latFixedPoint) {
634 if(pointLon >= lonFixedPoint) {
640 if(pointLon >= lonFixedPoint) {
648 int windingNeedCompare = 0, lineIsStraight = 0;
651 /* Calculate winding number */
652 if(quadrant == prevQuadrant) {
654 } else if(quadrant == (prevQuadrant + 1) % 4) {
656 } else if((quadrant + 1) % 4 == prevQuadrant) {
659 windingNeedCompare = 1;
662 /* Avoid horizontal and vertical lines */
663 if((pointLon == prevLon || pointLat == prevLat)) {
667 /* Calculate the parameters of y=ax+b if needed */
668 if(!lineIsStraight && (distanceSqrMin || windingNeedCompare)) {
669 a = (static_cast<float>(pointLat) - static_cast<float>(prevLat)) / (static_cast<float>(pointLon) - static_cast<float>(prevLon));
670 b = static_cast<float>(pointLat) - a * static_cast<float>(pointLon);
673 int onStraight = ZDPointInBox(pointLat, latFixedPoint, prevLat, pointLon, lonFixedPoint, prevLon);
674 if(lineIsStraight && (onStraight || windingNeedCompare)) {
675 if(distanceSqrMin) *distanceSqrMin = 0;
676 return ZD_LOOKUP_ON_BORDER_SEGMENT;
679 /* Jumped two quadrants. */
680 if(windingNeedCompare) {
681 /* Check if the target is on the border */
682 const auto intersectLon = static_cast<int32_t>((static_cast<float>(latFixedPoint) - b) / a);
683 if(intersectLon >= lonFixedPoint-1 && intersectLon <= lonFixedPoint+1) {
684 if(distanceSqrMin) *distanceSqrMin = 0;
685 return ZD_LOOKUP_ON_BORDER_SEGMENT;
688 /* Ok, it's not. In which direction did we go round the target? */
689 const int sign = (intersectLon < lonFixedPoint) ? 2 : -2;
690 if(quadrant == 2 || quadrant == 3) {
697 /* Calculate closest point on line (if needed) */
699 float closestLon, closestLat;
700 if(!lineIsStraight) {
701 closestLon = (static_cast<float>(lonFixedPoint) + a * static_cast<float>(latFixedPoint) - a * b) / (a * a + 1);
702 closestLat = (a * (static_cast<float>(lonFixedPoint) + a * static_cast<float>(latFixedPoint)) + b) / (a * a + 1);
704 if(pointLon == prevLon) {
705 closestLon = static_cast<float>(pointLon);
706 closestLat = static_cast<float>(latFixedPoint);
708 closestLon = static_cast<float>(lonFixedPoint);
709 closestLat = static_cast<float>(pointLat);
713 const int closestInBox = ZDPointInBox(pointLon, static_cast<int32_t>(closestLon), prevLon, pointLat, static_cast<int32_t>(closestLat), prevLat);
715 int64_t diffLat, diffLon;
717 /* Calculate squared distance to segment. */
718 diffLat = static_cast<int64_t>(closestLat - static_cast<float>(latFixedPoint));
719 diffLon = static_cast<int64_t>(closestLon - static_cast<float>(lonFixedPoint));
722 * Calculate squared distance to vertices
723 * It is enough to check the current point since the polygon is closed.
725 diffLat = static_cast<int64_t>(pointLat - latFixedPoint);
726 diffLon = static_cast<int64_t>(pointLon - lonFixedPoint);
729 /* Note: lon has half scale */
730 uint64_t distanceSqr = static_cast<uint64_t>(diffLat * diffLat) + static_cast<uint64_t>(diffLon * diffLon) * 4;
731 if(distanceSqr < *distanceSqrMin) *distanceSqrMin = distanceSqr;
735 prevQuadrant = quadrant;
742 return ZD_LOOKUP_IN_ZONE;
744 return ZD_LOOKUP_IN_EXCLUDED_ZONE;
746 return ZD_LOOKUP_NOT_IN_ZONE;
749 /* Should not happen */
750 if(distanceSqrMin) *distanceSqrMin = 0;
751 return ZD_LOOKUP_ON_BORDER_SEGMENT;
754 void ZDCloseDatabase(ZoneDetect *library)
757 if(library->fieldNames) {
759 for(i = 0; i < static_cast<size_t>(library->numFields); i++) {
760 if(library->fieldNames[i]) {
761 free(library->fieldNames[i]);
764 free(library->fieldNames);
766 if(library->notice) {
767 free(library->notice);
770 if(library->closeType == 0) {
771 #if defined(_MSC_VER) || defined(__MINGW32__)
772 if(library->mapping && !UnmapViewOfFile(library->mapping)) zdError(ZD_E_DB_MUNMAP_MSVIEW, (int)GetLastError());
773 if(library->fdMap && !CloseHandle(library->fdMap)) zdError(ZD_E_DB_MUNMAP, (int)GetLastError());
774 if(library->fd && !CloseHandle(library->fd)) zdError(ZD_E_DB_CLOSE, (int)GetLastError());
775 #elif defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
776 if(library->mapping && munmap(library->mapping, static_cast<size_t>(library->length))) zdError(ZD_E_DB_MUNMAP, 0);
777 if(library->fd >= 0 && close(library->fd)) zdError(ZD_E_DB_CLOSE, 0);
785 struct ZoneDetectDeleter {
786 void operator()(ZoneDetect *library)
788 ZDCloseDatabase(library);
792 using ZoneDetectPtr = std::unique_ptr<ZoneDetect, ZoneDetectDeleter>;
794 ZoneDetect *ZDOpenDatabaseFromMemory(void* buffer, size_t length)
796 ZoneDetectPtr library{static_cast<ZoneDetect *>(calloc(1, sizeof(ZoneDetect)))};
799 library->closeType = 1;
800 library->length = static_cast<long int>(length);
802 if(library->length <= 0) {
803 #if defined(_MSC_VER) || defined(__MINGW32__) || defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
804 zdError(ZD_E_DB_SEEK, errno);
806 zdError(ZD_E_DB_SEEK, 0);
811 library->mapping = static_cast<uint8_t *>(buffer);
813 /* Parse the header */
814 if(ZDParseHeader(library.get())) {
815 zdError(ZD_E_PARSE_HEADER, 0);
820 return library.release();
823 ZoneDetect *ZDOpenDatabase(const char *path)
825 ZoneDetectPtr library{static_cast<ZoneDetect *>(calloc(1, sizeof(ZoneDetect)))};
828 #if defined(_MSC_VER) || defined(__MINGW32__)
829 library->fd = CreateFile(path, GENERIC_READ, 0, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
830 if (library->fd == INVALID_HANDLE_VALUE) {
831 zdError(ZD_E_DB_OPEN, (int)GetLastError());
835 const DWORD fsize = GetFileSize(library->fd, NULL);
836 if (fsize == INVALID_FILE_SIZE) {
837 zdError(ZD_E_DB_SEEK, (int)GetLastError());
840 library->length = (int32_t)fsize;
842 library->fdMap = CreateFileMappingA(library->fd, NULL, PAGE_READONLY, 0, 0, NULL);
843 if (!library->fdMap) {
844 zdError(ZD_E_DB_MMAP, (int)GetLastError());
848 library->mapping = MapViewOfFile(library->fdMap, FILE_MAP_READ, 0, 0, 0);
849 if (!library->mapping) {
850 zdError(ZD_E_DB_MMAP_MSVIEW, (int)GetLastError());
853 #elif defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
854 library->fd = open(path, O_RDONLY | O_CLOEXEC);
855 if(library->fd < 0) {
856 zdError(ZD_E_DB_OPEN, errno);
860 library->length = lseek(library->fd, 0, SEEK_END);
861 if(library->length <= 0 || library->length > 50331648) {
862 zdError(ZD_E_DB_SEEK, errno);
865 lseek(library->fd, 0, SEEK_SET);
867 library->mapping = static_cast<uint8_t *>(mmap(nullptr, static_cast<size_t>(library->length), PROT_READ, MAP_PRIVATE | MAP_FILE, library->fd, 0));
868 if(library->mapping == MAP_FAILED) {
869 zdError(ZD_E_DB_MMAP, errno);
874 /* Parse the header */
875 if(ZDParseHeader(library.get())) {
876 zdError(ZD_E_PARSE_HEADER, 0);
881 return library.release();
884 ZoneDetectResult *ZDLookup(const ZoneDetect *library, float lat, float lon, float *safezone)
886 const int32_t latFixedPoint = ZDFloatToFixedPoint(lat, 90, library->precision);
887 const int32_t lonFixedPoint = ZDFloatToFixedPoint(lon, 180, library->precision);
888 size_t numResults = 0;
889 auto distanceSqrMin = static_cast<uint64_t>(-1);
891 /* Iterate over all polygons */
892 uint32_t bboxIndex = library->bboxOffset;
893 uint32_t metadataIndex = 0;
894 uint32_t polygonIndex = 0;
896 auto results = static_cast<ZoneDetectResult *>(malloc(sizeof(ZoneDetectResult)));
901 uint32_t polygonId = 0;
903 while(bboxIndex < library->metadataOffset) {
904 int32_t minLat, minLon, maxLat, maxLon, metadataIndexDelta;
905 uint64_t polygonIndexDelta;
906 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &minLat)) break;
907 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &minLon)) break;
908 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &maxLat)) break;
909 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &maxLon)) break;
910 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &metadataIndexDelta)) break;
911 if(!ZDDecodeVariableLengthUnsigned(library, &bboxIndex, &polygonIndexDelta)) break;
913 metadataIndex += static_cast<uint32_t>(metadataIndexDelta);
914 polygonIndex += static_cast<uint32_t>(polygonIndexDelta);
916 if(latFixedPoint >= minLat) {
917 if(latFixedPoint <= maxLat &&
918 lonFixedPoint >= minLon &&
919 lonFixedPoint <= maxLon) {
921 const ZDLookupResult lookupResult = ZDPointInPolygon(library, library->dataOffset + polygonIndex, latFixedPoint, lonFixedPoint, (safezone) ? &distanceSqrMin : nullptr);
922 if(lookupResult == ZD_LOOKUP_PARSE_ERROR) {
924 } if(lookupResult != ZD_LOOKUP_NOT_IN_ZONE) {
925 auto newResults = static_cast<ZoneDetectResult *>(realloc(results, sizeof(ZoneDetectResult) * (numResults + 2)));
928 results = newResults;
929 results[numResults].polygonId = polygonId;
930 results[numResults].metaId = metadataIndex;
931 results[numResults].numFields = library->numFields;
932 results[numResults].fieldNames = library->fieldNames;
933 results[numResults].lookupResult = lookupResult;
942 /* The data is sorted along minLat */
949 /* Clean up results */
951 for(i = 0; i < numResults; i++) {
953 ZDLookupResult overrideResult = ZD_LOOKUP_IGNORE;
955 for(j = i; j < numResults; j++) {
956 if(results[i].metaId == results[j].metaId) {
957 ZDLookupResult tmpResult = results[j].lookupResult;
958 results[j].lookupResult = ZD_LOOKUP_IGNORE;
960 /* This is the same result. Is it an exclusion zone? */
961 if(tmpResult == ZD_LOOKUP_IN_ZONE) {
963 } else if(tmpResult == ZD_LOOKUP_IN_EXCLUDED_ZONE) {
966 /* If on the bodrder then the final result is on the border */
967 overrideResult = tmpResult;
973 if(overrideResult != ZD_LOOKUP_IGNORE) {
974 results[i].lookupResult = overrideResult;
977 results[i].lookupResult = ZD_LOOKUP_IN_ZONE;
982 /* Remove zones to ignore */
983 size_t newNumResults = 0;
984 for(i = 0; i < numResults; i++) {
985 if(results[i].lookupResult != ZD_LOOKUP_IGNORE) {
986 results[newNumResults] = results[i];
990 numResults = newNumResults;
992 /* Lookup metadata */
993 for(i = 0; i < numResults; i++) {
994 uint32_t tmpIndex = library->metadataOffset + results[i].metaId;
995 results[i].data = static_cast<char **>(malloc(library->numFields * sizeof *results[i].data));
996 if(results[i].data) {
998 for(j = 0; j < library->numFields; j++) {
999 results[i].data[j] = ZDParseString(library, &tmpIndex);
1000 if (!results[i].data[j]) {
1001 /* free all allocated memory */
1003 for(m = 0; m < j; m++) {
1004 if(results[i].data[m]) {
1005 free(results[i].data[m]);
1009 for(k = 0; k < i; k++) {
1011 for(l = 0; l < static_cast<size_t>(results[k].numFields); l++) {
1012 if(results[k].data[l]) {
1013 free(results[k].data[l]);
1016 if (results[k].data) {
1017 free(results[k].data);
1026 /* free all allocated memory */
1028 for(k = 0; k < i; k++) {
1030 for(l = 0; l < static_cast<size_t>(results[k].numFields); l++) {
1031 if(results[k].data[l]) {
1032 free(results[k].data[l]);
1035 if (results[k].data) {
1036 free(results[k].data);
1044 /* Write end marker */
1045 results[numResults].lookupResult = ZD_LOOKUP_END;
1046 results[numResults].numFields = 0;
1047 results[numResults].fieldNames = nullptr;
1048 results[numResults].data = nullptr;
1051 *safezone = sqrtf(static_cast<float>(distanceSqrMin)) * 90 / static_cast<float>(1 << (library->precision - 1));
1057 void ZDFreeResults(ZoneDetectResult *results)
1059 unsigned int index = 0;
1065 while(results[index].lookupResult != ZD_LOOKUP_END) {
1066 if(results[index].data) {
1068 for(i = 0; i < static_cast<size_t>(results[index].numFields); i++) {
1069 if(results[index].data[i]) {
1070 free(results[index].data[i]);
1073 free(results[index].data);
1080 const char *ZDGetNotice(const ZoneDetect *library)
1082 return library->notice;
1085 uint8_t ZDGetTableType(const ZoneDetect *library)
1087 return library->tableType;
1090 const char *ZDLookupResultToString(ZDLookupResult result)
1093 case ZD_LOOKUP_IGNORE:
1097 case ZD_LOOKUP_PARSE_ERROR:
1098 return "Parsing error";
1099 case ZD_LOOKUP_NOT_IN_ZONE:
1100 return "Not in zone";
1101 case ZD_LOOKUP_IN_ZONE:
1103 case ZD_LOOKUP_IN_EXCLUDED_ZONE:
1104 return "In excluded zone";
1105 case ZD_LOOKUP_ON_BORDER_VERTEX:
1106 return "Target point is border vertex";
1107 case ZD_LOOKUP_ON_BORDER_SEGMENT:
1108 return "Target point is on border";
1114 #define ZD_E_COULD_NOT(msg) "could not " msg
1116 const char *ZDGetErrorString(int errZD)
1118 switch (static_cast<enum ZDInternalError>(errZD)) {
1124 return ZD_E_COULD_NOT("open database file");
1126 return ZD_E_COULD_NOT("retrieve database file size");
1128 return ZD_E_COULD_NOT("map database file to system memory");
1129 #if defined(_MSC_VER) || defined(__MINGW32__)
1130 case ZD_E_DB_MMAP_MSVIEW :
1131 return ZD_E_COULD_NOT("open database file view");
1132 case ZD_E_DB_MAP_EXCEPTION:
1133 return "I/O exception occurred while accessing database file view";
1134 case ZD_E_DB_MUNMAP_MSVIEW:
1135 return ZD_E_COULD_NOT("close database file view");
1137 case ZD_E_DB_MUNMAP :
1138 return ZD_E_COULD_NOT("unmap database");
1139 case ZD_E_DB_CLOSE :
1140 return ZD_E_COULD_NOT("close database file");
1141 case ZD_E_PARSE_HEADER :
1142 return ZD_E_COULD_NOT("parse database header");
1146 #undef ZD_E_COULD_NOT
1148 int ZDSetErrorHandler(void (*handler)(int, int))
1150 zdErrorHandler = handler;
1154 char* ZDHelperSimpleLookupString(const ZoneDetect* library, float lat, float lon)
1156 std::unique_ptr<ZoneDetectResult, decltype(&ZDFreeResults)> result{ZDLookup(library, lat, lon, nullptr), ZDFreeResults};
1161 char* output = nullptr;
1163 char* strings[2] = {nullptr};
1165 if(result->lookupResult == ZD_LOOKUP_END) {
1169 for(int i = 0; i < result->numFields; i++) {
1170 if(result->fieldNames[i] && result->data[i]) {
1171 if(library->tableType == 'T') {
1172 if(!strcmp(result->fieldNames[i], "TimezoneIdPrefix")) {
1173 strings[0] = result->data[i];
1175 if(!strcmp(result->fieldNames[i], "TimezoneId")) {
1176 strings[1] = result->data[i];
1179 if(library->tableType == 'C') {
1180 if(!strcmp(result->fieldNames[i], "Name")) {
1181 strings[0] = result->data[i];
1187 for(const auto& string : strings) {
1189 size_t partLength = strlen(string);
1190 if(partLength > 512) {
1193 length += partLength;
1203 output = static_cast<char*>(malloc(length));
1206 for(const auto& string : strings) {
1208 strcat(output + strlen(output), string);