diff options
Diffstat (limited to 'thirdparty/thorvg/src/common')
| -rw-r--r-- | thirdparty/thorvg/src/common/tvgArray.h | 186 | ||||
| -rw-r--r-- | thirdparty/thorvg/src/common/tvgBezier.cpp | 193 | ||||
| -rw-r--r-- | thirdparty/thorvg/src/common/tvgBezier.h | 49 | ||||
| -rw-r--r-- | thirdparty/thorvg/src/common/tvgCompressor.cpp | 475 | ||||
| -rw-r--r-- | thirdparty/thorvg/src/common/tvgCompressor.h | 35 | ||||
| -rw-r--r-- | thirdparty/thorvg/src/common/tvgList.h | 90 | ||||
| -rw-r--r-- | thirdparty/thorvg/src/common/tvgMath.cpp | 102 | ||||
| -rw-r--r-- | thirdparty/thorvg/src/common/tvgMath.h | 184 | ||||
| -rw-r--r-- | thirdparty/thorvg/src/common/tvgStr.cpp | 239 | ||||
| -rw-r--r-- | thirdparty/thorvg/src/common/tvgStr.h | 37 |
10 files changed, 1590 insertions, 0 deletions
diff --git a/thirdparty/thorvg/src/common/tvgArray.h b/thirdparty/thorvg/src/common/tvgArray.h new file mode 100644 index 0000000000..08eb25329c --- /dev/null +++ b/thirdparty/thorvg/src/common/tvgArray.h @@ -0,0 +1,186 @@ +/* + * Copyright (c) 2020 - 2023 the ThorVG project. All rights reserved. + + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#ifndef _TVG_ARRAY_H_ +#define _TVG_ARRAY_H_ + +#include <memory.h> +#include <cstdint> + +namespace tvg +{ + +template<class T> +struct Array +{ + T* data = nullptr; + uint32_t count = 0; + uint32_t reserved = 0; + + Array(){} + + Array(const Array& rhs) + { + reset(); + *this = rhs; + } + + void push(T element) + { + if (count + 1 > reserved) { + reserved = count + (count + 2) / 2; + data = static_cast<T*>(realloc(data, sizeof(T) * reserved)); + } + data[count++] = element; + } + + void push(Array<T>& rhs) + { + grow(rhs.count); + memcpy(data + count, rhs.data, rhs.count * sizeof(T)); + count += rhs.count; + } + + bool reserve(uint32_t size) + { + if (size > reserved) { + reserved = size; + data = static_cast<T*>(realloc(data, sizeof(T) * reserved)); + } + return true; + } + + bool grow(uint32_t size) + { + return reserve(count + size); + } + + const T& operator[](size_t idx) const + { + return data[idx]; + } + + T& operator[](size_t idx) + { + return data[idx]; + } + + T* end() + { + return data + count; + } + + const T* end() const + { + return data + count; + } + + const T& last() const + { + return data[count - 1]; + } + + const T& first() const + { + return data[0]; + } + + T& last() + { + return data[count - 1]; + } + + T& first() + { + return data[0]; + } + + void pop() + { + if (count > 0) --count; + } + + void reset() + { + free(data); + data = nullptr; + count = reserved = 0; + } + + void clear() + { + count = 0; + } + + bool empty() const + { + return count == 0; + } + + template<class COMPARE> + void sort() + { + qsort<COMPARE>(data, 0, static_cast<int32_t>(count) - 1); + } + + void operator=(const Array& rhs) + { + reserve(rhs.count); + if (rhs.count > 0) memcpy(data, rhs.data, sizeof(T) * rhs.count); + count = rhs.count; + } + + ~Array() + { + free(data); + } + +private: + template<class COMPARE> + void qsort(T* arr, int32_t low, int32_t high) + { + if (low < high) { + int32_t i = low; + int32_t j = high; + T tmp = arr[low]; + while (i < j) { + while (i < j && !COMPARE{}(arr[j], tmp)) --j; + if (i < j) { + arr[i] = arr[j]; + ++i; + } + while (i < j && COMPARE{}(arr[i], tmp)) ++i; + if (i < j) { + arr[j] = arr[i]; + --j; + } + } + arr[i] = tmp; + qsort<COMPARE>(arr, low, i - 1); + qsort<COMPARE>(arr, i + 1, high); + } + } +}; + +} + +#endif //_TVG_ARRAY_H_ diff --git a/thirdparty/thorvg/src/common/tvgBezier.cpp b/thirdparty/thorvg/src/common/tvgBezier.cpp new file mode 100644 index 0000000000..f9daf07b84 --- /dev/null +++ b/thirdparty/thorvg/src/common/tvgBezier.cpp @@ -0,0 +1,193 @@ +/* + * Copyright (c) 2020 - 2023 the ThorVG project. All rights reserved. + + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#include "tvgMath.h" +#include "tvgBezier.h" + +#define BEZIER_EPSILON 1e-4f + +/************************************************************************/ +/* Internal Class Implementation */ +/************************************************************************/ + +static float _lineLength(const Point& pt1, const Point& pt2) +{ + /* approximate sqrt(x*x + y*y) using alpha max plus beta min algorithm. + With alpha = 1, beta = 3/8, giving results with the largest error less + than 7% compared to the exact value. */ + Point diff = {pt2.x - pt1.x, pt2.y - pt1.y}; + if (diff.x < 0) diff.x = -diff.x; + if (diff.y < 0) diff.y = -diff.y; + return (diff.x > diff.y) ? (diff.x + diff.y * 0.375f) : (diff.y + diff.x * 0.375f); +} + + +/************************************************************************/ +/* External Class Implementation */ +/************************************************************************/ + +namespace tvg +{ + +void bezSplit(const Bezier&cur, Bezier& left, Bezier& right) +{ + auto c = (cur.ctrl1.x + cur.ctrl2.x) * 0.5f; + left.ctrl1.x = (cur.start.x + cur.ctrl1.x) * 0.5f; + right.ctrl2.x = (cur.ctrl2.x + cur.end.x) * 0.5f; + left.start.x = cur.start.x; + right.end.x = cur.end.x; + left.ctrl2.x = (left.ctrl1.x + c) * 0.5f; + right.ctrl1.x = (right.ctrl2.x + c) * 0.5f; + left.end.x = right.start.x = (left.ctrl2.x + right.ctrl1.x) * 0.5f; + + c = (cur.ctrl1.y + cur.ctrl2.y) * 0.5f; + left.ctrl1.y = (cur.start.y + cur.ctrl1.y) * 0.5f; + right.ctrl2.y = (cur.ctrl2.y + cur.end.y) * 0.5f; + left.start.y = cur.start.y; + right.end.y = cur.end.y; + left.ctrl2.y = (left.ctrl1.y + c) * 0.5f; + right.ctrl1.y = (right.ctrl2.y + c) * 0.5f; + left.end.y = right.start.y = (left.ctrl2.y + right.ctrl1.y) * 0.5f; +} + + +float bezLength(const Bezier& cur) +{ + Bezier left, right; + auto len = _lineLength(cur.start, cur.ctrl1) + _lineLength(cur.ctrl1, cur.ctrl2) + _lineLength(cur.ctrl2, cur.end); + auto chord = _lineLength(cur.start, cur.end); + + if (fabsf(len - chord) > BEZIER_EPSILON) { + bezSplit(cur, left, right); + return bezLength(left) + bezLength(right); + } + return len; +} + + +void bezSplitLeft(Bezier& cur, float at, Bezier& left) +{ + left.start = cur.start; + + left.ctrl1.x = cur.start.x + at * (cur.ctrl1.x - cur.start.x); + left.ctrl1.y = cur.start.y + at * (cur.ctrl1.y - cur.start.y); + + left.ctrl2.x = cur.ctrl1.x + at * (cur.ctrl2.x - cur.ctrl1.x); //temporary holding spot + left.ctrl2.y = cur.ctrl1.y + at * (cur.ctrl2.y - cur.ctrl1.y); //temporary holding spot + + cur.ctrl2.x = cur.ctrl2.x + at * (cur.end.x - cur.ctrl2.x); + cur.ctrl2.y = cur.ctrl2.y + at * (cur.end.y - cur.ctrl2.y); + + cur.ctrl1.x = left.ctrl2.x + at * (cur.ctrl2.x - left.ctrl2.x); + cur.ctrl1.y = left.ctrl2.y + at * (cur.ctrl2.y - left.ctrl2.y); + + left.ctrl2.x = left.ctrl1.x + at * (left.ctrl2.x - left.ctrl1.x); + left.ctrl2.y = left.ctrl1.y + at * (left.ctrl2.y - left.ctrl1.y); + + left.end.x = cur.start.x = left.ctrl2.x + at * (cur.ctrl1.x - left.ctrl2.x); + left.end.y = cur.start.y = left.ctrl2.y + at * (cur.ctrl1.y - left.ctrl2.y); +} + + +float bezAt(const Bezier& bz, float at, float length) +{ + auto biggest = 1.0f; + auto smallest = 0.0f; + auto t = 0.5f; + + //just in case to prevent an infinite loop + if (at <= 0) return 0.0f; + if (at >= length) return 1.0f; + + while (true) { + auto right = bz; + Bezier left; + bezSplitLeft(right, t, left); + length = bezLength(left); + if (fabsf(length - at) < BEZIER_EPSILON || fabsf(smallest - biggest) < BEZIER_EPSILON) { + break; + } + if (length < at) { + smallest = t; + t = (t + biggest) * 0.5f; + } else { + biggest = t; + t = (smallest + t) * 0.5f; + } + } + return t; +} + + +void bezSplitAt(const Bezier& cur, float at, Bezier& left, Bezier& right) +{ + right = cur; + auto t = bezAt(right, at, bezLength(right)); + bezSplitLeft(right, t, left); +} + + +Point bezPointAt(const Bezier& bz, float t) +{ + Point cur; + auto it = 1.0f - t; + + auto ax = bz.start.x * it + bz.ctrl1.x * t; + auto bx = bz.ctrl1.x * it + bz.ctrl2.x * t; + auto cx = bz.ctrl2.x * it + bz.end.x * t; + ax = ax * it + bx * t; + bx = bx * it + cx * t; + cur.x = ax * it + bx * t; + + float ay = bz.start.y * it + bz.ctrl1.y * t; + float by = bz.ctrl1.y * it + bz.ctrl2.y * t; + float cy = bz.ctrl2.y * it + bz.end.y * t; + ay = ay * it + by * t; + by = by * it + cy * t; + cur.y = ay * it + by * t; + + return cur; +} + + +float bezAngleAt(const Bezier& bz, float t) +{ + if (t < 0 || t > 1) return 0; + + //derivate + // p'(t) = 3 * (-(1-2t+t^2) * p0 + (1 - 4 * t + 3 * t^2) * p1 + (2 * t - 3 * + // t^2) * p2 + t^2 * p3) + float mt = 1.0f - t; + float d = t * t; + float a = -mt * mt; + float b = 1 - 4 * t + 3 * d; + float c = 2 * t - 3 * d; + + Point pt ={a * bz.start.x + b * bz.ctrl1.x + c * bz.ctrl2.x + d * bz.end.x, a * bz.start.y + b * bz.ctrl1.y + c * bz.ctrl2.y + d * bz.end.y}; + pt.x *= 3; + pt.y *= 3; + + return atan2(pt.x, pt.y) * 180.0f / 3.141592f; +} + + +} diff --git a/thirdparty/thorvg/src/common/tvgBezier.h b/thirdparty/thorvg/src/common/tvgBezier.h new file mode 100644 index 0000000000..539a63bdd3 --- /dev/null +++ b/thirdparty/thorvg/src/common/tvgBezier.h @@ -0,0 +1,49 @@ +/* + * Copyright (c) 2020 - 2023 the ThorVG project. All rights reserved. + + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#ifndef _TVG_BEZIER_H_ +#define _TVG_BEZIER_H_ + +#include "tvgCommon.h" + +namespace tvg +{ + +struct Bezier +{ + Point start; + Point ctrl1; + Point ctrl2; + Point end; +}; + +void bezSplit(const Bezier&cur, Bezier& left, Bezier& right); +float bezLength(const Bezier& cur); +void bezSplitLeft(Bezier& cur, float at, Bezier& left); +float bezAt(const Bezier& bz, float at, float length); +void bezSplitAt(const Bezier& cur, float at, Bezier& left, Bezier& right); +Point bezPointAt(const Bezier& bz, float t); +float bezAngleAt(const Bezier& bz, float t); + +} + +#endif //_TVG_BEZIER_H_ diff --git a/thirdparty/thorvg/src/common/tvgCompressor.cpp b/thirdparty/thorvg/src/common/tvgCompressor.cpp new file mode 100644 index 0000000000..e38940f3d0 --- /dev/null +++ b/thirdparty/thorvg/src/common/tvgCompressor.cpp @@ -0,0 +1,475 @@ +/* + * Copyright (c) 2020 - 2023 the ThorVG project. All rights reserved. + + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +/* + * Lempel–Ziv–Welch (LZW) encoder/decoder by Guilherme R. Lampert(guilherme.ronaldo.lampert@gmail.com) + + * This is the compression scheme used by the GIF image format and the Unix 'compress' tool. + * Main differences from this implementation is that End Of Input (EOI) and Clear Codes (CC) + * are not stored in the output and the max code length in bits is 12, vs 16 in compress. + * + * EOI is simply detected by the end of the data stream, while CC happens if the + * dictionary gets filled. Data is written/read from bit streams, which handle + * byte-alignment for us in a transparent way. + + * The decoder relies on the hardcoded data layout produced by the encoder, since + * no additional reconstruction data is added to the output, so they must match. + * The nice thing about LZW is that we can reconstruct the dictionary directly from + * the stream of codes generated by the encoder, so this avoids storing additional + * headers in the bit stream. + + * The output code length is variable. It starts with the minimum number of bits + * required to store the base byte-sized dictionary and automatically increases + * as the dictionary gets larger (it starts at 9-bits and grows to 10-bits when + * code 512 is added, then 11-bits when 1024 is added, and so on). If the dictionary + * is filled (4096 items for a 12-bits dictionary), the whole thing is cleared and + * the process starts over. This is the main reason why the encoder and the decoder + * must match perfectly, since the lengths of the codes will not be specified with + * the data itself. + + * USEFUL LINKS: + * https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch + * http://rosettacode.org/wiki/LZW_compression + * http://www.cs.duke.edu/csed/curious/compression/lzw.html + * http://www.cs.cf.ac.uk/Dave/Multimedia/node214.html + * http://marknelson.us/1989/10/01/lzw-data-compression/ + */ +#include "config.h" + + + +#include <string> +#include <memory.h> +#include "tvgCompressor.h" + +namespace tvg { + + +/************************************************************************/ +/* LZW Implementation */ +/************************************************************************/ + + +//LZW Dictionary helper: +constexpr int Nil = -1; +constexpr int MaxDictBits = 12; +constexpr int StartBits = 9; +constexpr int FirstCode = (1 << (StartBits - 1)); // 256 +constexpr int MaxDictEntries = (1 << MaxDictBits); // 4096 + + +//Round up to the next power-of-two number, e.g. 37 => 64 +static int nextPowerOfTwo(int num) +{ + --num; + for (size_t i = 1; i < sizeof(num) * 8; i <<= 1) { + num = num | num >> i; + } + return ++num; +} + + +struct BitStreamWriter +{ + uint8_t* stream; //Growable buffer to store our bits. Heap allocated & owned by the class instance. + int bytesAllocated; //Current size of heap-allocated stream buffer *in bytes*. + int granularity; //Amount bytesAllocated multiplies by when auto-resizing in appendBit(). + int currBytePos; //Current byte being written to, from 0 to bytesAllocated-1. + int nextBitPos; //Bit position within the current byte to access next. 0 to 7. + int numBitsWritten; //Number of bits in use from the stream buffer, not including byte-rounding padding. + + void internalInit() + { + stream = nullptr; + bytesAllocated = 0; + granularity = 2; + currBytePos = 0; + nextBitPos = 0; + numBitsWritten = 0; + } + + uint8_t* allocBytes(const int bytesWanted, uint8_t * oldPtr, const int oldSize) + { + auto newMemory = static_cast<uint8_t *>(malloc(bytesWanted)); + memset(newMemory, 0, bytesWanted); + + if (oldPtr) { + memcpy(newMemory, oldPtr, oldSize); + free(oldPtr); + } + return newMemory; + } + + BitStreamWriter() + { + /* 8192 bits for a start (1024 bytes). It will resize if needed. + Default granularity is 2. */ + internalInit(); + allocate(8192); + } + + BitStreamWriter(const int initialSizeInBits, const int growthGranularity = 2) + { + internalInit(); + setGranularity(growthGranularity); + allocate(initialSizeInBits); + } + + ~BitStreamWriter() + { + free(stream); + } + + void allocate(int bitsWanted) + { + //Require at least a byte. + if (bitsWanted <= 0) bitsWanted = 8; + + //Round upwards if needed: + if ((bitsWanted % 8) != 0) bitsWanted = nextPowerOfTwo(bitsWanted); + + //We might already have the required count. + const int sizeInBytes = bitsWanted / 8; + if (sizeInBytes <= bytesAllocated) return; + + stream = allocBytes(sizeInBytes, stream, bytesAllocated); + bytesAllocated = sizeInBytes; + } + + void appendBit(const int bit) + { + const uint32_t mask = uint32_t(1) << nextBitPos; + stream[currBytePos] = (stream[currBytePos] & ~mask) | (-bit & mask); + ++numBitsWritten; + + if (++nextBitPos == 8) { + nextBitPos = 0; + if (++currBytePos == bytesAllocated) allocate(bytesAllocated * granularity * 8); + } + } + + void appendBitsU64(const uint64_t num, const int bitCount) + { + for (int b = 0; b < bitCount; ++b) { + const uint64_t mask = uint64_t(1) << b; + const int bit = !!(num & mask); + appendBit(bit); + } + } + + uint8_t* release() + { + auto oldPtr = stream; + internalInit(); + return oldPtr; + } + + void setGranularity(const int growthGranularity) + { + granularity = (growthGranularity >= 2) ? growthGranularity : 2; + } + + int getByteCount() const + { + int usedBytes = numBitsWritten / 8; + int leftovers = numBitsWritten % 8; + if (leftovers != 0) ++usedBytes; + return usedBytes; + } +}; + + +struct BitStreamReader +{ + const uint8_t* stream; // Pointer to the external bit stream. Not owned by the reader. + const int sizeInBytes; // Size of the stream *in bytes*. Might include padding. + const int sizeInBits; // Size of the stream *in bits*, padding *not* include. + int currBytePos = 0; // Current byte being read in the stream. + int nextBitPos = 0; // Bit position within the current byte to access next. 0 to 7. + int numBitsRead = 0; // Total bits read from the stream so far. Never includes byte-rounding padding. + + BitStreamReader(const uint8_t* bitStream, const int byteCount, const int bitCount) : stream(bitStream), sizeInBytes(byteCount), sizeInBits(bitCount) + { + } + + bool readNextBit(int& bitOut) + { + if (numBitsRead >= sizeInBits) return false; //We are done. + + const uint32_t mask = uint32_t(1) << nextBitPos; + bitOut = !!(stream[currBytePos] & mask); + ++numBitsRead; + + if (++nextBitPos == 8) { + nextBitPos = 0; + ++currBytePos; + } + return true; + } + + uint64_t readBitsU64(const int bitCount) + { + uint64_t num = 0; + for (int b = 0; b < bitCount; ++b) { + int bit; + if (!readNextBit(bit)) break; + /* Based on a "Stanford bit-hack": + http://graphics.stanford.edu/~seander/bithacks.html#ConditionalSetOrClearBitsWithoutBranching */ + const uint64_t mask = uint64_t(1) << b; + num = (num & ~mask) | (-bit & mask); + } + return num; + } + + bool isEndOfStream() const + { + return numBitsRead >= sizeInBits; + } +}; + + +struct Dictionary +{ + struct Entry + { + int code; + int value; + }; + + //Dictionary entries 0-255 are always reserved to the byte/ASCII range. + int size; + Entry entries[MaxDictEntries]; + + Dictionary() + { + /* First 256 dictionary entries are reserved to the byte/ASCII range. + Additional entries follow for the character sequences found in the input. + Up to 4096 - 256 (MaxDictEntries - FirstCode). */ + size = FirstCode; + + for (int i = 0; i < size; ++i) { + entries[i].code = Nil; + entries[i].value = i; + } + } + + int findIndex(const int code, const int value) const + { + if (code == Nil) return value; + + //Linear search for now. + //TODO: Worth optimizing with a proper hash-table? + for (int i = 0; i < size; ++i) { + if (entries[i].code == code && entries[i].value == value) return i; + } + return Nil; + } + + bool add(const int code, const int value) + { + if (size == MaxDictEntries) return false; + entries[size].code = code; + entries[size].value = value; + ++size; + return true; + } + + bool flush(int & codeBitsWidth) + { + if (size == (1 << codeBitsWidth)) { + ++codeBitsWidth; + if (codeBitsWidth > MaxDictBits) { + //Clear the dictionary (except the first 256 byte entries). + codeBitsWidth = StartBits; + size = FirstCode; + return true; + } + } + return false; + } +}; + + +static bool outputByte(int code, uint8_t*& output, int outputSizeBytes, int& bytesDecodedSoFar) +{ + if (bytesDecodedSoFar >= outputSizeBytes) return false; + *output++ = static_cast<uint8_t>(code); + ++bytesDecodedSoFar; + return true; +} + + +static bool outputSequence(const Dictionary& dict, int code, uint8_t*& output, int outputSizeBytes, int& bytesDecodedSoFar, int& firstByte) +{ + /* A sequence is stored backwards, so we have to write + it to a temp then output the buffer in reverse. */ + int i = 0; + uint8_t sequence[MaxDictEntries]; + + do { + sequence[i++] = dict.entries[code].value; + code = dict.entries[code].code; + } while (code >= 0); + + firstByte = sequence[--i]; + + for (; i >= 0; --i) { + if (!outputByte(sequence[i], output, outputSizeBytes, bytesDecodedSoFar)) return false; + } + return true; +} + + +uint8_t* lzwDecode(const uint8_t* compressed, uint32_t compressedSizeBytes, uint32_t compressedSizeBits, uint32_t uncompressedSizeBytes) +{ + int code = Nil; + int prevCode = Nil; + int firstByte = 0; + int bytesDecoded = 0; + int codeBitsWidth = StartBits; + auto uncompressed = (uint8_t*) malloc(sizeof(uint8_t) * uncompressedSizeBytes); + auto ptr = uncompressed; + + /* We'll reconstruct the dictionary based on the bit stream codes. + Unlike Huffman encoding, we don't store the dictionary as a prefix to the data. */ + Dictionary dictionary; + BitStreamReader bitStream(compressed, compressedSizeBytes, compressedSizeBits); + + /* We check to avoid an overflow of the user buffer. + If the buffer is smaller than the decompressed size, we break the loop and return the current decompression count. */ + while (!bitStream.isEndOfStream()) { + code = static_cast<int>(bitStream.readBitsU64(codeBitsWidth)); + + if (prevCode == Nil) { + if (!outputByte(code, ptr, uncompressedSizeBytes, bytesDecoded)) break; + firstByte = code; + prevCode = code; + continue; + } + if (code >= dictionary.size) { + if (!outputSequence(dictionary, prevCode, ptr, uncompressedSizeBytes, bytesDecoded, firstByte)) break; + if (!outputByte(firstByte, ptr, uncompressedSizeBytes, bytesDecoded)) break; + } else if (!outputSequence(dictionary, code, ptr, uncompressedSizeBytes, bytesDecoded, firstByte)) break; + + dictionary.add(prevCode, firstByte); + if (dictionary.flush(codeBitsWidth)) prevCode = Nil; + else prevCode = code; + } + + return uncompressed; +} + + +uint8_t* lzwEncode(const uint8_t* uncompressed, uint32_t uncompressedSizeBytes, uint32_t* compressedSizeBytes, uint32_t* compressedSizeBits) +{ + //LZW encoding context: + int code = Nil; + int codeBitsWidth = StartBits; + Dictionary dictionary; + + //Output bit stream we write to. This will allocate memory as needed to accommodate the encoded data. + BitStreamWriter bitStream; + + for (; uncompressedSizeBytes > 0; --uncompressedSizeBytes, ++uncompressed) { + const int value = *uncompressed; + const int index = dictionary.findIndex(code, value); + + if (index != Nil) { + code = index; + continue; + } + + //Write the dictionary code using the minimum bit-with: + bitStream.appendBitsU64(code, codeBitsWidth); + + //Flush it when full so we can restart the sequences. + if (!dictionary.flush(codeBitsWidth)) { + //There's still space for this sequence. + dictionary.add(code, value); + } + code = value; + } + + //Residual code at the end: + if (code != Nil) bitStream.appendBitsU64(code, codeBitsWidth); + + //Pass ownership of the compressed data buffer to the user pointer: + *compressedSizeBytes = bitStream.getByteCount(); + *compressedSizeBits = bitStream.numBitsWritten; + + return bitStream.release(); +} + + +/************************************************************************/ +/* B64 Implementation */ +/************************************************************************/ + + +size_t b64Decode(const char* encoded, const size_t len, char** decoded) +{ + static constexpr const char B64_INDEX[256] = + { + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 62, 63, 62, 62, 63, 52, 53, 54, 55, 56, 57, + 58, 59, 60, 61, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, + 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, + 25, 0, 0, 0, 0, 63, 0, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, + 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51 + }; + + + if (!decoded || !encoded || len == 0) return 0; + + auto reserved = 3 * (1 + (len >> 2)) + 1; + auto output = static_cast<char*>(malloc(reserved * sizeof(char))); + if (!output) return 0; + output[reserved - 1] = '\0'; + + size_t idx = 0; + + while (*encoded && *(encoded + 1)) { + if (*encoded <= 0x20) { + ++encoded; + continue; + } + + auto value1 = B64_INDEX[(size_t)encoded[0]]; + auto value2 = B64_INDEX[(size_t)encoded[1]]; + output[idx++] = (value1 << 2) + ((value2 & 0x30) >> 4); + + if (!encoded[2] || encoded[2] == '=' || encoded[2] == '.') break; + auto value3 = B64_INDEX[(size_t)encoded[2]]; + output[idx++] = ((value2 & 0x0f) << 4) + ((value3 & 0x3c) >> 2); + + if (!encoded[3] || encoded[3] == '=' || encoded[3] == '.') break; + auto value4 = B64_INDEX[(size_t)encoded[3]]; + output[idx++] = ((value3 & 0x03) << 6) + value4; + encoded += 4; + } + *decoded = output; + return reserved; +} + + +} diff --git a/thirdparty/thorvg/src/common/tvgCompressor.h b/thirdparty/thorvg/src/common/tvgCompressor.h new file mode 100644 index 0000000000..05d23f4293 --- /dev/null +++ b/thirdparty/thorvg/src/common/tvgCompressor.h @@ -0,0 +1,35 @@ +/* + * Copyright (c) 2020 - 2023 the ThorVG project. All rights reserved. + + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#ifndef _TVG_COMPRESSOR_H_ +#define _TVG_COMPRESSOR_H_ + +#include <cstdint> + +namespace tvg +{ + uint8_t* lzwEncode(const uint8_t* uncompressed, uint32_t uncompressedSizeBytes, uint32_t* compressedSizeBytes, uint32_t* compressedSizeBits); + uint8_t* lzwDecode(const uint8_t* compressed, uint32_t compressedSizeBytes, uint32_t compressedSizeBits, uint32_t uncompressedSizeBytes); + size_t b64Decode(const char* encoded, const size_t len, char** decoded); +} + +#endif //_TVG_COMPRESSOR_H_ diff --git a/thirdparty/thorvg/src/common/tvgList.h b/thirdparty/thorvg/src/common/tvgList.h new file mode 100644 index 0000000000..01e87a840f --- /dev/null +++ b/thirdparty/thorvg/src/common/tvgList.h @@ -0,0 +1,90 @@ +/* + * Copyright (c) 2023 the ThorVG project. All rights reserved. + + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#ifndef _TVG_LIST_H_ +#define _TVG_LIST_H_ + +namespace tvg { + +template<typename T> +struct LinkedList +{ + T *head = nullptr; + T *tail = nullptr; + + LinkedList() = default; + LinkedList(T *head, T *tail) : head(head), tail(tail) + { + } + + template<T *T::*Prev, T *T::*Next> + static void insert(T *t, T *prev, T *next, T **head, T **tail) + { + t->*Prev = prev; + t->*Next = next; + + if (prev) { + prev->*Next = t; + } else if (head) { + *head = t; + } + + if (next) { + next->*Prev = t; + } else if (tail) { + *tail = t; + } + } + + template<T *T::*Prev, T *T::*Next> + static void remove(T *t, T **head, T **tail) + { + if (t->*Prev) { + t->*Prev->*Next = t->*Next; + } else if (head) { + *head = t->*Next; + } + + if (t->*Next) { + t->*Next->*Prev = t->*Prev; + } else if (tail) { + *tail = t->*Prev; + } + + t->*Prev = t->*Next = nullptr; + } + + template <T* T::*Next> + static bool contains(T *t, T **head, T **tail) { + for (T *it = *head; it; it = it->*Next) { + if (it == t) { + return true; + } + } + + return false; + } +}; + +} + +#endif // _TVG_LIST_H_ diff --git a/thirdparty/thorvg/src/common/tvgMath.cpp b/thirdparty/thorvg/src/common/tvgMath.cpp new file mode 100644 index 0000000000..a9463c8077 --- /dev/null +++ b/thirdparty/thorvg/src/common/tvgMath.cpp @@ -0,0 +1,102 @@ +/* + * Copyright (c) 2021 - 2023 the ThorVG project. All rights reserved. + + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#include "tvgMath.h" + + +bool mathInverse(const Matrix* m, Matrix* out) +{ + auto det = m->e11 * (m->e22 * m->e33 - m->e32 * m->e23) - + m->e12 * (m->e21 * m->e33 - m->e23 * m->e31) + + m->e13 * (m->e21 * m->e32 - m->e22 * m->e31); + + if (mathZero(det)) return false; + + auto invDet = 1 / det; + + out->e11 = (m->e22 * m->e33 - m->e32 * m->e23) * invDet; + out->e12 = (m->e13 * m->e32 - m->e12 * m->e33) * invDet; + out->e13 = (m->e12 * m->e23 - m->e13 * m->e22) * invDet; + out->e21 = (m->e23 * m->e31 - m->e21 * m->e33) * invDet; + out->e22 = (m->e11 * m->e33 - m->e13 * m->e31) * invDet; + out->e23 = (m->e21 * m->e13 - m->e11 * m->e23) * invDet; + out->e31 = (m->e21 * m->e32 - m->e31 * m->e22) * invDet; + out->e32 = (m->e31 * m->e12 - m->e11 * m->e32) * invDet; + out->e33 = (m->e11 * m->e22 - m->e21 * m->e12) * invDet; + + return true; +} + + +Matrix mathMultiply(const Matrix* lhs, const Matrix* rhs) +{ + Matrix m; + + m.e11 = lhs->e11 * rhs->e11 + lhs->e12 * rhs->e21 + lhs->e13 * rhs->e31; + m.e12 = lhs->e11 * rhs->e12 + lhs->e12 * rhs->e22 + lhs->e13 * rhs->e32; + m.e13 = lhs->e11 * rhs->e13 + lhs->e12 * rhs->e23 + lhs->e13 * rhs->e33; + + m.e21 = lhs->e21 * rhs->e11 + lhs->e22 * rhs->e21 + lhs->e23 * rhs->e31; + m.e22 = lhs->e21 * rhs->e12 + lhs->e22 * rhs->e22 + lhs->e23 * rhs->e32; + m.e23 = lhs->e21 * rhs->e13 + lhs->e22 * rhs->e23 + lhs->e23 * rhs->e33; + + m.e31 = lhs->e31 * rhs->e11 + lhs->e32 * rhs->e21 + lhs->e33 * rhs->e31; + m.e32 = lhs->e31 * rhs->e12 + lhs->e32 * rhs->e22 + lhs->e33 * rhs->e32; + m.e33 = lhs->e31 * rhs->e13 + lhs->e32 * rhs->e23 + lhs->e33 * rhs->e33; + + return m; +} + + +void mathRotate(Matrix* m, float degree) +{ + if (degree == 0.0f) return; + + auto radian = degree / 180.0f * M_PI; + auto cosVal = cosf(radian); + auto sinVal = sinf(radian); + + m->e12 = m->e11 * -sinVal; + m->e11 *= cosVal; + m->e21 = m->e22 * sinVal; + m->e22 *= cosVal; +} + + +bool mathIdentity(const Matrix* m) +{ + if (m->e11 != 1.0f || m->e12 != 0.0f || m->e13 != 0.0f || + m->e21 != 0.0f || m->e22 != 1.0f || m->e23 != 0.0f || + m->e31 != 0.0f || m->e32 != 0.0f || m->e33 != 1.0f) { + return false; + } + return true; +} + + +void mathMultiply(Point* pt, const Matrix* transform) +{ + auto tx = pt->x * transform->e11 + pt->y * transform->e12 + transform->e13; + auto ty = pt->x * transform->e21 + pt->y * transform->e22 + transform->e23; + pt->x = tx; + pt->y = ty; +} diff --git a/thirdparty/thorvg/src/common/tvgMath.h b/thirdparty/thorvg/src/common/tvgMath.h new file mode 100644 index 0000000000..004fff1e7b --- /dev/null +++ b/thirdparty/thorvg/src/common/tvgMath.h @@ -0,0 +1,184 @@ +/* + * Copyright (c) 2021 - 2023 the ThorVG project. All rights reserved. + + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#ifndef _TVG_MATH_H_ +#define _TVG_MATH_H_ + + #define _USE_MATH_DEFINES + +#include <float.h> +#include <math.h> +#include "tvgCommon.h" + +#define MATH_PI 3.14159265358979323846f +#define MATH_PI2 1.57079632679489661923f + +#define mathMin(x, y) (((x) < (y)) ? (x) : (y)) +#define mathMax(x, y) (((x) > (y)) ? (x) : (y)) + + +bool mathInverse(const Matrix* m, Matrix* out); +Matrix mathMultiply(const Matrix* lhs, const Matrix* rhs); +void mathRotate(Matrix* m, float degree); +bool mathIdentity(const Matrix* m); +void mathMultiply(Point* pt, const Matrix* transform); + + +static inline bool mathZero(float a) +{ + return (fabsf(a) < FLT_EPSILON) ? true : false; +} + + +static inline bool mathEqual(float a, float b) +{ + return (fabsf(a - b) < FLT_EPSILON); +} + + +static inline bool mathEqual(const Matrix& a, const Matrix& b) +{ + if (!mathEqual(a.e11, b.e11) || !mathEqual(a.e12, b.e12) || !mathEqual(a.e13, b.e13) || + !mathEqual(a.e21, b.e21) || !mathEqual(a.e22, b.e22) || !mathEqual(a.e23, b.e23) || + !mathEqual(a.e31, b.e31) || !mathEqual(a.e32, b.e32) || !mathEqual(a.e33, b.e33)) { + return false; + } + return true; +} + + +static inline bool mathRightAngle(const Matrix* m) +{ + auto radian = fabsf(atan2f(m->e21, m->e11)); + if (radian < FLT_EPSILON || mathEqual(radian, float(M_PI_2)) || mathEqual(radian, float(M_PI))) return true; + return false; +} + + +static inline bool mathSkewed(const Matrix* m) +{ + return (fabsf(m->e21 + m->e12) > FLT_EPSILON); +} + + +static inline void mathIdentity(Matrix* m) +{ + m->e11 = 1.0f; + m->e12 = 0.0f; + m->e13 = 0.0f; + m->e21 = 0.0f; + m->e22 = 1.0f; + m->e23 = 0.0f; + m->e31 = 0.0f; + m->e32 = 0.0f; + m->e33 = 1.0f; +} + + +static inline void mathTransform(Matrix* transform, Point* coord) +{ + auto x = coord->x; + auto y = coord->y; + coord->x = x * transform->e11 + y * transform->e12 + transform->e13; + coord->y = x * transform->e21 + y * transform->e22 + transform->e23; +} + + +static inline void mathScale(Matrix* m, float sx, float sy) +{ + m->e11 *= sx; + m->e22 *= sy; +} + + +static inline void mathScaleR(Matrix* m, float x, float y) +{ + if (x != 1.0f) { + m->e11 *= x; + m->e21 *= x; + } + if (y != 1.0f) { + m->e22 *= y; + m->e12 *= y; + } +} + + +static inline void mathTranslate(Matrix* m, float x, float y) +{ + m->e13 += x; + m->e23 += y; +} + + +static inline void mathTranslateR(Matrix* m, float x, float y) +{ + if (x == 0.0f && y == 0.0f) return; + m->e13 += (x * m->e11 + y * m->e12); + m->e23 += (x * m->e21 + y * m->e22); +} + + +static inline void mathLog(Matrix* m) +{ + TVGLOG("MATH", "Matrix: [%f %f %f] [%f %f %f] [%f %f %f]", m->e11, m->e12, m->e13, m->e21, m->e22, m->e23, m->e31, m->e32, m->e33); +} + + +static inline float mathLength(const Point* a, const Point* b) +{ + auto x = b->x - a->x; + auto y = b->y - a->y; + + if (x < 0) x = -x; + if (y < 0) y = -y; + + return (x > y) ? (x + 0.375f * y) : (y + 0.375f * x); +} + + +static inline Point operator-(const Point& lhs, const Point& rhs) +{ + return {lhs.x - rhs.x, lhs.y - rhs.y}; +} + + +static inline Point operator+(const Point& lhs, const Point& rhs) +{ + return {lhs.x + rhs.x, lhs.y + rhs.y}; +} + + +static inline Point operator*(const Point& lhs, float rhs) +{ + return {lhs.x * rhs, lhs.y * rhs}; +} + + +template <typename T> +static inline T mathLerp(const T &start, const T &end, float t) +{ + return static_cast<T>(start + (end - start) * t); +} + + +#endif //_TVG_MATH_H_ diff --git a/thirdparty/thorvg/src/common/tvgStr.cpp b/thirdparty/thorvg/src/common/tvgStr.cpp new file mode 100644 index 0000000000..eeed4fc404 --- /dev/null +++ b/thirdparty/thorvg/src/common/tvgStr.cpp @@ -0,0 +1,239 @@ +/* + * Copyright (c) 2020 - 2023 the ThorVG project. All rights reserved. + + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#include "config.h" +#include <cstring> +#include <memory.h> +#include "tvgMath.h" +#include "tvgStr.h" + + +/************************************************************************/ +/* Internal Class Implementation */ +/************************************************************************/ + +static inline bool _floatExact(float a, float b) +{ + return memcmp(&a, &b, sizeof(float)) == 0; +} + + +/************************************************************************/ +/* External Class Implementation */ +/************************************************************************/ + +namespace tvg { + +/* + * https://docs.microsoft.com/en-us/cpp/c-runtime-library/reference/strtof-strtof-l-wcstof-wcstof-l?view=msvc-160 + * + * src should be one of the following form : + * + * [whitespace] [sign] {digits [radix digits] | radix digits} [{e | E} [sign] digits] + * [whitespace] [sign] {INF | INFINITY} + * [whitespace] [sign] NAN [sequence] + * + * No hexadecimal form supported + * no sequence supported after NAN + */ +float strToFloat(const char *nPtr, char **endPtr) +{ + if (endPtr) *endPtr = (char *) (nPtr); + if (!nPtr) return 0.0f; + + auto a = nPtr; + auto iter = nPtr; + auto val = 0.0f; + unsigned long long integerPart = 0; + int minus = 1; + + //ignore leading whitespaces + while (isspace(*iter)) iter++; + + //signed or not + if (*iter == '-') { + minus = -1; + iter++; + } else if (*iter == '+') { + iter++; + } + + if (tolower(*iter) == 'i') { + if ((tolower(*(iter + 1)) == 'n') && (tolower(*(iter + 2)) == 'f')) iter += 3; + else goto error; + + if (tolower(*(iter)) == 'i') { + if ((tolower(*(iter + 1)) == 'n') && (tolower(*(iter + 2)) == 'i') && (tolower(*(iter + 3)) == 't') && + (tolower(*(iter + 4)) == 'y')) + iter += 5; + else goto error; + } + if (endPtr) *endPtr = (char *) (iter); + return (minus == -1) ? -INFINITY : INFINITY; + } + + if (tolower(*iter) == 'n') { + if ((tolower(*(iter + 1)) == 'a') && (tolower(*(iter + 2)) == 'n')) iter += 3; + else goto error; + + if (endPtr) *endPtr = (char *) (iter); + return (minus == -1) ? -NAN : NAN; + } + + //Optional: integer part before dot + if (isdigit(*iter)) { + for (; isdigit(*iter); iter++) { + integerPart = integerPart * 10ULL + (unsigned long long) (*iter - '0'); + } + a = iter; + } else if (*iter != '.') { + goto success; + } + + val = static_cast<float>(integerPart); + + //Optional: decimal part after dot + if (*iter == '.') { + unsigned long long decimalPart = 0; + unsigned long long pow10 = 1; + int count = 0; + + iter++; + + if (isdigit(*iter)) { + for (; isdigit(*iter); iter++, count++) { + if (count < 19) { + decimalPart = decimalPart * 10ULL + +static_cast<unsigned long long>(*iter - '0'); + pow10 *= 10ULL; + } + } + } else if (isspace(*iter)) { //skip if there is a space after the dot. + a = iter; + goto success; + } + + val += static_cast<float>(decimalPart) / static_cast<float>(pow10); + a = iter; + } + + //Optional: exponent + if (*iter == 'e' || *iter == 'E') { + ++iter; + + //Exception: svg may have 'em' unit for fonts. ex) 5em, 10.5em + if ((*iter == 'm') || (*iter == 'M')) { + //TODO: We don't support font em unit now, but has to multiply val * font size later... + a = iter + 1; + goto success; + } + + //signed or not + int minus_e = 1; + + if (*iter == '-') { + minus_e = -1; + ++iter; + } else if (*iter == '+') { + iter++; + } + + unsigned int exponentPart = 0; + + if (isdigit(*iter)) { + while (*iter == '0') iter++; + for (; isdigit(*iter); iter++) { + exponentPart = exponentPart * 10U + static_cast<unsigned int>(*iter - '0'); + } + } else if (!isdigit(*(a - 1))) { + a = nPtr; + goto success; + } else if (*iter == 0) { + goto success; + } + + //if ((_floatExact(val, 2.2250738585072011f)) && ((minus_e * static_cast<int>(exponentPart)) <= -308)) { + if ((_floatExact(val, 1.175494351f)) && ((minus_e * static_cast<int>(exponentPart)) <= -38)) { + //val *= 1.0e-308f; + val *= 1.0e-38f; + a = iter; + goto success; + } + + a = iter; + auto scale = 1.0f; + + while (exponentPart >= 8U) { + scale *= 1E8; + exponentPart -= 8U; + } + while (exponentPart > 0U) { + scale *= 10.0f; + exponentPart--; + } + val = (minus_e == -1) ? (val / scale) : (val * scale); + } else if ((iter > nPtr) && !isdigit(*(iter - 1))) { + a = nPtr; + goto success; + } + +success: + if (endPtr) *endPtr = (char *)(a); + return minus * val; + +error: + if (endPtr) *endPtr = (char *)(nPtr); + return 0.0f; +} + + +int str2int(const char* str, size_t n) +{ + int ret = 0; + for(size_t i = 0; i < n; ++i) { + ret = ret * 10 + (str[i] - '0'); + } + return ret; +} + +char* strDuplicate(const char *str, size_t n) +{ + auto len = strlen(str); + if (len < n) n = len; + + auto ret = (char *) malloc(n + 1); + if (!ret) return nullptr; + ret[n] = '\0'; + + return (char *) memcpy(ret, str, n); +} + +char* strDirname(const char* path) +{ + const char *ptr = strrchr(path, '/'); +#ifdef _WIN32 + if (ptr) ptr = strrchr(ptr + 1, '\\'); +#endif + int len = int(ptr + 1 - path); // +1 to include '/' + return strDuplicate(path, len); +} + +} diff --git a/thirdparty/thorvg/src/common/tvgStr.h b/thirdparty/thorvg/src/common/tvgStr.h new file mode 100644 index 0000000000..448cc69336 --- /dev/null +++ b/thirdparty/thorvg/src/common/tvgStr.h @@ -0,0 +1,37 @@ +/* + * Copyright (c) 2020 - 2023 the ThorVG project. All rights reserved. + + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#ifndef _TVG_STR_H_ +#define _TVG_STR_H_ + +#include <cstddef> + +namespace tvg +{ + +float strToFloat(const char *nPtr, char **endPtr); //convert to float +int str2int(const char* str, size_t n); //convert to integer +char* strDuplicate(const char *str, size_t n); //copy the string +char* strDirname(const char* path); //return the full directory name + +} +#endif //_TVG_STR_H_ |