1 /*
2  * Copyright (c) 2020 - 2024 the ThorVG project. All rights reserved.
3 
4  * Permission is hereby granted, free of charge, to any person obtaining a copy
5  * of this software and associated documentation files (the "Software"), to deal
6  * in the Software without restriction, including without limitation the rights
7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8  * copies of the Software, and to permit persons to whom the Software is
9  * furnished to do so, subject to the following conditions:
10 
11  * The above copyright notice and this permission notice shall be included in all
12  * copies or substantial portions of the Software.
13 
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20  * SOFTWARE.
21  */
22 
23 #include "../../lv_conf_internal.h"
24 #if LV_USE_THORVG_INTERNAL
25 
26 /*
27  * Lempel–Ziv–Welch (LZW) encoder/decoder by Guilherme R. Lampert(guilherme.ronaldo.lampert@gmail.com)
28 
29  * This is the compression scheme used by the GIF image format and the Unix 'compress' tool.
30  * Main differences from this implementation is that End Of Input (EOI) and Clear Codes (CC)
31  * are not stored in the output and the max code length in bits is 12, vs 16 in compress.
32  *
33  * EOI is simply detected by the end of the data stream, while CC happens if the
34  * dictionary gets filled. Data is written/read from bit streams, which handle
35  * byte-alignment for us in a transparent way.
36 
37  * The decoder relies on the hardcoded data layout produced by the encoder, since
38  * no additional reconstruction data is added to the output, so they must match.
39  * The nice thing about LZW is that we can reconstruct the dictionary directly from
40  * the stream of codes generated by the encoder, so this avoids storing additional
41  * headers in the bit stream.
42 
43  * The output code length is variable. It starts with the minimum number of bits
44  * required to store the base byte-sized dictionary and automatically increases
45  * as the dictionary gets larger (it starts at 9-bits and grows to 10-bits when
46  * code 512 is added, then 11-bits when 1024 is added, and so on). If the dictionary
47  * is filled (4096 items for a 12-bits dictionary), the whole thing is cleared and
48  * the process starts over. This is the main reason why the encoder and the decoder
49  * must match perfectly, since the lengths of the codes will not be specified with
50  * the data itself.
51 
52  * USEFUL LINKS:
53  * https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch
54  * http://rosettacode.org/wiki/LZW_compression
55  * http://www.cs.duke.edu/csed/curious/compression/lzw.html
56  * http://www.cs.cf.ac.uk/Dave/Multimedia/node214.html
57  * http://marknelson.us/1989/10/01/lzw-data-compression/
58  */
59 #include "config.h"
60 
61 
62 
63 #include <string>
64 #include <memory.h>
65 #include "tvgCompressor.h"
66 
67 namespace tvg {
68 
69 
70 /************************************************************************/
71 /* LZW Implementation                                                   */
72 /************************************************************************/
73 
74 
75 //LZW Dictionary helper:
76 constexpr int Nil = -1;
77 constexpr int MaxDictBits = 12;
78 constexpr int StartBits = 9;
79 constexpr int FirstCode = (1 << (StartBits - 1)); // 256
80 constexpr int MaxDictEntries = (1 << MaxDictBits);     // 4096
81 
82 
83 //Round up to the next power-of-two number, e.g. 37 => 64
nextPowerOfTwo(int num)84 static int nextPowerOfTwo(int num)
85 {
86     --num;
87     for (size_t i = 1; i < sizeof(num) * 8; i <<= 1) {
88         num = num | num >> i;
89     }
90     return ++num;
91 }
92 
93 
94 struct BitStreamWriter
95 {
96     uint8_t* stream;       //Growable buffer to store our bits. Heap allocated & owned by the class instance.
97     int bytesAllocated;    //Current size of heap-allocated stream buffer *in bytes*.
98     int granularity;       //Amount bytesAllocated multiplies by when auto-resizing in appendBit().
99     int currBytePos;       //Current byte being written to, from 0 to bytesAllocated-1.
100     int nextBitPos;        //Bit position within the current byte to access next. 0 to 7.
101     int numBitsWritten;    //Number of bits in use from the stream buffer, not including byte-rounding padding.
102 
internalInittvg::BitStreamWriter103     void internalInit()
104     {
105         stream = nullptr;
106         bytesAllocated = 0;
107         granularity = 2;
108         currBytePos = 0;
109         nextBitPos = 0;
110         numBitsWritten = 0;
111     }
112 
allocBytestvg::BitStreamWriter113     uint8_t* allocBytes(const int bytesWanted, uint8_t * oldPtr, const int oldSize)
114     {
115         auto newMemory = static_cast<uint8_t *>(malloc(bytesWanted));
116         memset(newMemory, 0, bytesWanted);
117 
118         if (oldPtr) {
119             memcpy(newMemory, oldPtr, oldSize);
120             free(oldPtr);
121         }
122         return newMemory;
123     }
124 
BitStreamWritertvg::BitStreamWriter125     BitStreamWriter()
126     {
127         /* 8192 bits for a start (1024 bytes). It will resize if needed.
128            Default granularity is 2. */
129         internalInit();
130         allocate(8192);
131     }
132 
BitStreamWritertvg::BitStreamWriter133     BitStreamWriter(const int initialSizeInBits, const int growthGranularity = 2)
134     {
135         internalInit();
136         setGranularity(growthGranularity);
137         allocate(initialSizeInBits);
138     }
139 
~BitStreamWritertvg::BitStreamWriter140     ~BitStreamWriter()
141     {
142         free(stream);
143     }
144 
allocatetvg::BitStreamWriter145     void allocate(int bitsWanted)
146     {
147         //Require at least a byte.
148         if (bitsWanted <= 0) bitsWanted = 8;
149 
150         //Round upwards if needed:
151         if ((bitsWanted % 8) != 0) bitsWanted = nextPowerOfTwo(bitsWanted);
152 
153         //We might already have the required count.
154         const int sizeInBytes = bitsWanted / 8;
155         if (sizeInBytes <= bytesAllocated) return;
156 
157         stream = allocBytes(sizeInBytes, stream, bytesAllocated);
158         bytesAllocated = sizeInBytes;
159     }
160 
appendBittvg::BitStreamWriter161     void appendBit(const int bit)
162     {
163         const uint32_t mask = uint32_t(1) << nextBitPos;
164         stream[currBytePos] = (stream[currBytePos] & ~mask) | (-bit & mask);
165         ++numBitsWritten;
166 
167         if (++nextBitPos == 8) {
168             nextBitPos = 0;
169             if (++currBytePos == bytesAllocated) allocate(bytesAllocated * granularity * 8);
170         }
171     }
172 
appendBitsU64tvg::BitStreamWriter173     void appendBitsU64(const uint64_t num, const int bitCount)
174     {
175         for (int b = 0; b < bitCount; ++b) {
176             const uint64_t mask = uint64_t(1) << b;
177             const int bit = !!(num & mask);
178             appendBit(bit);
179         }
180     }
181 
releasetvg::BitStreamWriter182     uint8_t* release()
183     {
184         auto oldPtr = stream;
185         internalInit();
186         return oldPtr;
187     }
188 
setGranularitytvg::BitStreamWriter189     void setGranularity(const int growthGranularity)
190     {
191         granularity = (growthGranularity >= 2) ? growthGranularity : 2;
192     }
193 
getByteCounttvg::BitStreamWriter194     int getByteCount() const
195     {
196         int usedBytes = numBitsWritten / 8;
197         int leftovers = numBitsWritten % 8;
198         if (leftovers != 0) ++usedBytes;
199         return usedBytes;
200     }
201 };
202 
203 
204 struct BitStreamReader
205 {
206     const uint8_t* stream;       // Pointer to the external bit stream. Not owned by the reader.
207     const int sizeInBytes;       // Size of the stream *in bytes*. Might include padding.
208     const int sizeInBits;        // Size of the stream *in bits*, padding *not* include.
209     int currBytePos = 0;         // Current byte being read in the stream.
210     int nextBitPos = 0;          // Bit position within the current byte to access next. 0 to 7.
211     int numBitsRead = 0;         // Total bits read from the stream so far. Never includes byte-rounding padding.
212 
BitStreamReadertvg::BitStreamReader213     BitStreamReader(const uint8_t* bitStream, const int byteCount, const int bitCount) : stream(bitStream), sizeInBytes(byteCount), sizeInBits(bitCount)
214     {
215     }
216 
readNextBittvg::BitStreamReader217     bool readNextBit(int& bitOut)
218     {
219         if (numBitsRead >= sizeInBits) return false; //We are done.
220 
221         const uint32_t mask = uint32_t(1) << nextBitPos;
222         bitOut = !!(stream[currBytePos] & mask);
223         ++numBitsRead;
224 
225         if (++nextBitPos == 8) {
226             nextBitPos = 0;
227             ++currBytePos;
228         }
229         return true;
230     }
231 
readBitsU64tvg::BitStreamReader232     uint64_t readBitsU64(const int bitCount)
233     {
234         uint64_t num = 0;
235         for (int b = 0; b < bitCount; ++b) {
236             int bit;
237             if (!readNextBit(bit)) break;
238             /* Based on a "Stanford bit-hack":
239                http://graphics.stanford.edu/~seander/bithacks.html#ConditionalSetOrClearBitsWithoutBranching */
240             const uint64_t mask = uint64_t(1) << b;
241             num = (num & ~mask) | (-bit & mask);
242         }
243         return num;
244     }
245 
isEndOfStreamtvg::BitStreamReader246     bool isEndOfStream() const
247     {
248         return numBitsRead >= sizeInBits;
249     }
250 };
251 
252 
253 struct Dictionary
254 {
255     struct Entry
256     {
257         int code;
258         int value;
259     };
260 
261     //Dictionary entries 0-255 are always reserved to the byte/ASCII range.
262     int size;
263     Entry entries[MaxDictEntries];
264 
Dictionarytvg::Dictionary265     Dictionary()
266     {
267         /* First 256 dictionary entries are reserved to the byte/ASCII range.
268            Additional entries follow for the character sequences found in the input.
269            Up to 4096 - 256 (MaxDictEntries - FirstCode). */
270         size = FirstCode;
271 
272         for (int i = 0; i < size; ++i) {
273             entries[i].code  = Nil;
274             entries[i].value = i;
275         }
276     }
277 
findIndextvg::Dictionary278     int findIndex(const int code, const int value) const
279     {
280         if (code == Nil) return value;
281 
282         //Linear search for now.
283         //TODO: Worth optimizing with a proper hash-table?
284         for (int i = 0; i < size; ++i) {
285             if (entries[i].code == code && entries[i].value == value) return i;
286         }
287         return Nil;
288     }
289 
addtvg::Dictionary290     bool add(const int code, const int value)
291     {
292         if (size == MaxDictEntries) return false;
293         entries[size].code  = code;
294         entries[size].value = value;
295         ++size;
296         return true;
297     }
298 
flushtvg::Dictionary299     bool flush(int & codeBitsWidth)
300     {
301         if (size == (1 << codeBitsWidth)) {
302             ++codeBitsWidth;
303             if (codeBitsWidth > MaxDictBits) {
304                 //Clear the dictionary (except the first 256 byte entries).
305                 codeBitsWidth = StartBits;
306                 size = FirstCode;
307                 return true;
308             }
309         }
310         return false;
311     }
312 };
313 
314 
outputByte(int code,uint8_t * & output,int outputSizeBytes,int & bytesDecodedSoFar)315 static bool outputByte(int code, uint8_t*& output, int outputSizeBytes, int& bytesDecodedSoFar)
316 {
317     if (bytesDecodedSoFar >= outputSizeBytes) return false;
318     *output++ = static_cast<uint8_t>(code);
319     ++bytesDecodedSoFar;
320     return true;
321 }
322 
323 
outputSequence(const Dictionary & dict,int code,uint8_t * & output,int outputSizeBytes,int & bytesDecodedSoFar,int & firstByte)324 static bool outputSequence(const Dictionary& dict, int code, uint8_t*& output, int outputSizeBytes, int& bytesDecodedSoFar, int& firstByte)
325 {
326     /* A sequence is stored backwards, so we have to write
327        it to a temp then output the buffer in reverse. */
328     int i = 0;
329     uint8_t sequence[MaxDictEntries];
330 
331     do {
332         sequence[i++] = dict.entries[code].value;
333         code = dict.entries[code].code;
334     } while (code >= 0);
335 
336     firstByte = sequence[--i];
337 
338     for (; i >= 0; --i) {
339         if (!outputByte(sequence[i], output, outputSizeBytes, bytesDecodedSoFar)) return false;
340     }
341     return true;
342 }
343 
344 
lzwDecode(const uint8_t * compressed,uint32_t compressedSizeBytes,uint32_t compressedSizeBits,uint32_t uncompressedSizeBytes)345 uint8_t* lzwDecode(const uint8_t* compressed, uint32_t compressedSizeBytes, uint32_t compressedSizeBits, uint32_t uncompressedSizeBytes)
346 {
347     int code = Nil;
348     int prevCode = Nil;
349     int firstByte = 0;
350     int bytesDecoded = 0;
351     int codeBitsWidth = StartBits;
352     auto uncompressed = (uint8_t*) malloc(sizeof(uint8_t) * uncompressedSizeBytes);
353     auto ptr = uncompressed;
354 
355     /* We'll reconstruct the dictionary based on the bit stream codes.
356        Unlike Huffman encoding, we don't store the dictionary as a prefix to the data. */
357     Dictionary dictionary;
358     BitStreamReader bitStream(compressed, compressedSizeBytes, compressedSizeBits);
359 
360     /* We check to avoid an overflow of the user buffer.
361        If the buffer is smaller than the decompressed size, we break the loop and return the current decompression count. */
362     while (!bitStream.isEndOfStream()) {
363         code = static_cast<int>(bitStream.readBitsU64(codeBitsWidth));
364 
365         if (prevCode == Nil) {
366             if (!outputByte(code, ptr, uncompressedSizeBytes, bytesDecoded)) break;
367             firstByte = code;
368             prevCode  = code;
369             continue;
370         }
371         if (code >= dictionary.size) {
372             if (!outputSequence(dictionary, prevCode, ptr, uncompressedSizeBytes, bytesDecoded, firstByte)) break;
373             if (!outputByte(firstByte, ptr, uncompressedSizeBytes, bytesDecoded)) break;
374         } else if (!outputSequence(dictionary, code, ptr, uncompressedSizeBytes, bytesDecoded, firstByte)) break;
375 
376         dictionary.add(prevCode, firstByte);
377         if (dictionary.flush(codeBitsWidth)) prevCode = Nil;
378         else prevCode = code;
379     }
380 
381     return uncompressed;
382 }
383 
384 
lzwEncode(const uint8_t * uncompressed,uint32_t uncompressedSizeBytes,uint32_t * compressedSizeBytes,uint32_t * compressedSizeBits)385 uint8_t* lzwEncode(const uint8_t* uncompressed, uint32_t uncompressedSizeBytes, uint32_t* compressedSizeBytes, uint32_t* compressedSizeBits)
386 {
387     //LZW encoding context:
388     int code = Nil;
389     int codeBitsWidth = StartBits;
390     Dictionary dictionary;
391 
392     //Output bit stream we write to. This will allocate memory as needed to accommodate the encoded data.
393     BitStreamWriter bitStream;
394 
395     for (; uncompressedSizeBytes > 0; --uncompressedSizeBytes, ++uncompressed) {
396         const int value = *uncompressed;
397         const int index = dictionary.findIndex(code, value);
398 
399         if (index != Nil) {
400             code = index;
401             continue;
402         }
403 
404         //Write the dictionary code using the minimum bit-with:
405         bitStream.appendBitsU64(code, codeBitsWidth);
406 
407         //Flush it when full so we can restart the sequences.
408         if (!dictionary.flush(codeBitsWidth)) {
409             //There's still space for this sequence.
410             dictionary.add(code, value);
411         }
412         code = value;
413     }
414 
415     //Residual code at the end:
416     if (code != Nil) bitStream.appendBitsU64(code, codeBitsWidth);
417 
418     //Pass ownership of the compressed data buffer to the user pointer:
419     *compressedSizeBytes = bitStream.getByteCount();
420     *compressedSizeBits = bitStream.numBitsWritten;
421 
422     return bitStream.release();
423 }
424 
425 
426 /************************************************************************/
427 /* B64 Implementation                                                   */
428 /************************************************************************/
429 
430 
b64Decode(const char * encoded,const size_t len,char ** decoded)431 size_t b64Decode(const char* encoded, const size_t len, char** decoded)
432 {
433     static constexpr const char B64_INDEX[256] =
434     {
435         0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
436         0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
437         0,  0,  0,  0,  0,  0,  0,  62, 63, 62, 62, 63, 52, 53, 54, 55, 56, 57,
438         58, 59, 60, 61, 0,  0,  0,  0,  0,  0,  0,  0,  1,  2,  3,  4,  5,  6,
439         7,  8,  9,  10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
440         25, 0,  0,  0,  0,  63, 0,  26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36,
441         37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51
442     };
443 
444 
445     if (!decoded || !encoded || len == 0) return 0;
446 
447     auto reserved = 3 * (1 + (len >> 2)) + 1;
448     auto output = static_cast<char*>(malloc(reserved * sizeof(char)));
449     if (!output) return 0;
450     output[reserved - 1] = '\0';
451 
452     size_t idx = 0;
453 
454     while (*encoded && *(encoded + 1)) {
455         if (*encoded <= 0x20) {
456             ++encoded;
457             continue;
458         }
459 
460         auto value1 = B64_INDEX[(size_t)encoded[0]];
461         auto value2 = B64_INDEX[(size_t)encoded[1]];
462         output[idx++] = (value1 << 2) + ((value2 & 0x30) >> 4);
463 
464         if (!encoded[2] || encoded[3] < 0 || encoded[2] == '=' || encoded[2] == '.') break;
465         auto value3 = B64_INDEX[(size_t)encoded[2]];
466         output[idx++] = ((value2 & 0x0f) << 4) + ((value3 & 0x3c) >> 2);
467 
468         if (!encoded[3] || encoded[3] < 0 || encoded[3] == '=' || encoded[3] == '.') break;
469         auto value4 = B64_INDEX[(size_t)encoded[3]];
470         output[idx++] = ((value3 & 0x03) << 6) + value4;
471         encoded += 4;
472     }
473     *decoded = output;
474     return idx;
475 }
476 
477 
478 /************************************************************************/
479 /* DJB2 Implementation                                                   */
480 /************************************************************************/
481 
djb2Encode(const char * str)482 unsigned long djb2Encode(const char* str)
483 {
484     if (!str) return 0;
485 
486     unsigned long hash = 5381;
487     int c;
488 
489     while ((c = *str++)) {
490         hash = ((hash << 5) + hash) + c; // hash * 33 + c
491     }
492     return hash;
493 }
494 
495 }
496 
497 #endif /* LV_USE_THORVG_INTERNAL */
498 
499