src/lib/tvgLzw.cpp

   1 /*
   2  * Copyright (c) 2020-2021 Samsung Electronics Co., Ltd. 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 /*
  24  * Lempel–Ziv–Welch (LZW) encoder/decoder by Guilherme R. Lampert(guilherme.ronaldo.lampert@gmail.com)
  25
  26  * This is the compression scheme used by the GIF image format and the Unix 'compress' tool.
  27  * Main differences from this implementation is that End Of Input (EOI) and Clear Codes (CC)
  28  * are not stored in the output and the max code length in bits is 12, vs 16 in compress.
  29  *
  30  * EOI is simply detected by the end of the data stream, while CC happens if the
  31  * dictionary gets filled. Data is written/read from bit streams, which handle
  32  * byte-alignment for us in a transparent way.
  33
  34  * The decoder relies on the hardcoded data layout produced by the encoder, since
  35  * no additional reconstruction data is added to the output, so they must match.
  36  * The nice thing about LZW is that we can reconstruct the dictionary directly from
  37  * the stream of codes generated by the encoder, so this avoids storing additional
  38  * headers in the bit stream.
  39
  40  * The output code length is variable. It starts with the minimum number of bits
  41  * required to store the base byte-sized dictionary and automatically increases
  42  * as the dictionary gets larger (it starts at 9-bits and grows to 10-bits when
  43  * code 512 is added, then 11-bits when 1024 is added, and so on). If the dictionary
  44  * is filled (4096 items for a 12-bits dictionary), the whole thing is cleared and
  45  * the process starts over. This is the main reason why the encoder and the decoder
  46  * must match perfectly, since the lengths of the codes will not be specified with
  47  * the data itself.
  48
  49  * USEFUL LINKS:
  50  * https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch
  51  * http://rosettacode.org/wiki/LZW_compression
  52  * http://www.cs.duke.edu/csed/curious/compression/lzw.html
  53  * http://www.cs.cf.ac.uk/Dave/Multimedia/node214.html
  54  * http://marknelson.us/1989/10/01/lzw-data-compression/
  55  */
  56 #include "config.h"
  57
  58 #if defined(THORVG_TVG_SAVER_SUPPORT) || defined(THORVG_TVG_LOADER_SUPPORT)
  59
  60 /************************************************************************/
  61 /* Internal Class Implementation                                        */
  62 /************************************************************************/
  63
  64 #include <string>
  65 #include <memory.h>
  66 #include "tvgLzw.h"
  67
  68 //LZW Dictionary helper:
  69 constexpr int Nil = -1;
  70 constexpr int MaxDictBits = 12;
  71 constexpr int StartBits = 9;
  72 constexpr int FirstCode = (1 << (StartBits - 1)); // 256
  73 constexpr int MaxDictEntries = (1 << MaxDictBits);     // 4096
  74
  75
  76 //Round up to the next power-of-two number, e.g. 37 => 64
  77 static int nextPowerOfTwo(int num)
  78 {
  79     --num;
  80     for (size_t i = 1; i < sizeof(num) * 8; i <<= 1) {
  81         num = num | num >> i;
  82     }
  83     return ++num;
  84 }
  85
  86
  87 struct BitStreamWriter
  88 {
  89     uint8_t* stream;       //Growable buffer to store our bits. Heap allocated & owned by the class instance.
  90     int bytesAllocated;    //Current size of heap-allocated stream buffer *in bytes*.
  91     int granularity;       //Amount bytesAllocated multiplies by when auto-resizing in appendBit().
  92     int currBytePos;       //Current byte being written to, from 0 to bytesAllocated-1.
  93     int nextBitPos;        //Bit position within the current byte to access next. 0 to 7.
  94     int numBitsWritten;    //Number of bits in use from the stream buffer, not including byte-rounding padding.
  95
  96     void internalInit()
  97     {
  98         stream = nullptr;
  99         bytesAllocated = 0;
 100         granularity = 2;
 101         currBytePos = 0;
 102         nextBitPos = 0;
 103         numBitsWritten = 0;
 104     }
 105
 106     uint8_t* allocBytes(const int bytesWanted, uint8_t * oldPtr, const int oldSize)
 107     {
 108         auto newMemory = static_cast<uint8_t *>(malloc(bytesWanted));
 109         memset(newMemory, 0, bytesWanted);
 110
 111         if (oldPtr) {
 112             memcpy(newMemory, oldPtr, oldSize);
 113             free(oldPtr);
 114         }
 115         return newMemory;
 116     }
 117
 118     BitStreamWriter()
 119     {
 120         /* 8192 bits for a start (1024 bytes). It will resize if needed.
 121            Default granularity is 2. */
 122         internalInit();
 123         allocate(8192);
 124     }
 125
 126     BitStreamWriter(const int initialSizeInBits, const int growthGranularity = 2)
 127     {
 128         internalInit();
 129         setGranularity(growthGranularity);
 130         allocate(initialSizeInBits);
 131     }
 132
 133     ~BitStreamWriter()
 134     {
 135         free(stream);
 136     }
 137
 138     void allocate(int bitsWanted)
 139     {
 140         //Require at least a byte.
 141         if (bitsWanted <= 0) bitsWanted = 8;
 142
 143         //Round upwards if needed:
 144         if ((bitsWanted % 8) != 0) bitsWanted = nextPowerOfTwo(bitsWanted);
 145
 146         //We might already have the required count.
 147         const int sizeInBytes = bitsWanted / 8;
 148         if (sizeInBytes <= bytesAllocated) return;
 149
 150         stream = allocBytes(sizeInBytes, stream, bytesAllocated);
 151         bytesAllocated = sizeInBytes;
 152     }
 153
 154     void appendBit(const int bit)
 155     {
 156         const uint32_t mask = uint32_t(1) << nextBitPos;
 157         stream[currBytePos] = (stream[currBytePos] & ~mask) | (-bit & mask);
 158         ++numBitsWritten;
 159
 160         if (++nextBitPos == 8) {
 161             nextBitPos = 0;
 162             if (++currBytePos == bytesAllocated) allocate(bytesAllocated * granularity * 8);
 163         }
 164     }
 165
 166     void appendBitsU64(const uint64_t num, const int bitCount)
 167     {
 168         for (int b = 0; b < bitCount; ++b) {
 169             const uint64_t mask = uint64_t(1) << b;
 170             const int bit = !!(num & mask);
 171             appendBit(bit);
 172         }
 173     }
 174
 175     uint8_t* release()
 176     {
 177         auto oldPtr = stream;
 178         internalInit();
 179         return oldPtr;
 180     }
 181
 182     void setGranularity(const int growthGranularity)
 183     {
 184         granularity = (growthGranularity >= 2) ? growthGranularity : 2;
 185     }
 186
 187     int getByteCount() const
 188     {
 189         int usedBytes = numBitsWritten / 8;
 190         int leftovers = numBitsWritten % 8;
 191         if (leftovers != 0) ++usedBytes;
 192         return usedBytes;
 193     }
 194 };
 195
 196
 197 struct BitStreamReader
 198 {
 199     const uint8_t* stream;       // Pointer to the external bit stream. Not owned by the reader.
 200     const int sizeInBytes;       // Size of the stream *in bytes*. Might include padding.
 201     const int sizeInBits;        // Size of the stream *in bits*, padding *not* include.
 202     int currBytePos = 0;         // Current byte being read in the stream.
 203     int nextBitPos = 0;          // Bit position within the current byte to access next. 0 to 7.
 204     int numBitsRead = 0;         // Total bits read from the stream so far. Never includes byte-rounding padding.
 205
 206     BitStreamReader(const uint8_t* bitStream, const int byteCount, const int bitCount) : stream(bitStream), sizeInBytes(byteCount), sizeInBits(bitCount)
 207     {
 208     }
 209
 210     bool readNextBit(int& bitOut)
 211     {
 212         if (numBitsRead >= sizeInBits) return false; //We are done.
 213
 214         const uint32_t mask = uint32_t(1) << nextBitPos;
 215         bitOut = !!(stream[currBytePos] & mask);
 216         ++numBitsRead;
 217
 218         if (++nextBitPos == 8) {
 219             nextBitPos = 0;
 220             ++currBytePos;
 221         }
 222         return true;
 223     }
 224
 225     uint64_t readBitsU64(const int bitCount)
 226     {
 227         uint64_t num = 0;
 228         for (int b = 0; b < bitCount; ++b) {
 229             int bit;
 230             if (!readNextBit(bit)) break;
 231             /* Based on a "Stanford bit-hack":
 232                http://graphics.stanford.edu/~seander/bithacks.html#ConditionalSetOrClearBitsWithoutBranching */
 233             const uint64_t mask = uint64_t(1) << b;
 234             num = (num & ~mask) | (-bit & mask);
 235         }
 236         return num;
 237     }
 238
 239     bool isEndOfStream() const
 240     {
 241         return numBitsRead >= sizeInBits;
 242     }
 243 };
 244
 245
 246 struct Dictionary
 247 {
 248     struct Entry
 249     {
 250         int code;
 251         int value;
 252     };
 253
 254     //Dictionary entries 0-255 are always reserved to the byte/ASCII range.
 255     int size;
 256     Entry entries[MaxDictEntries];
 257
 258     Dictionary()
 259     {
 260         /* First 256 dictionary entries are reserved to the byte/ASCII range.
 261            Additional entries follow for the character sequences found in the input.
 262            Up to 4096 - 256 (MaxDictEntries - FirstCode). */
 263         size = FirstCode;
 264
 265         for (int i = 0; i < size; ++i) {
 266             entries[i].code  = Nil;
 267             entries[i].value = i;
 268         }
 269     }
 270
 271     int findIndex(const int code, const int value) const
 272     {
 273         if (code == Nil) return value;
 274
 275         //Linear search for now.
 276         //TODO: Worth optimizing with a proper hash-table?
 277         for (int i = 0; i < size; ++i) {
 278             if (entries[i].code == code && entries[i].value == value) return i;
 279         }
 280         return Nil;
 281     }
 282
 283     bool add(const int code, const int value)
 284     {
 285         if (size == MaxDictEntries) return false;
 286         entries[size].code  = code;
 287         entries[size].value = value;
 288         ++size;
 289         return true;
 290     }
 291
 292     bool flush(int & codeBitsWidth)
 293     {
 294         if (size == (1 << codeBitsWidth)) {
 295             ++codeBitsWidth;
 296             if (codeBitsWidth > MaxDictBits) {
 297                 //Clear the dictionary (except the first 256 byte entries).
 298                 codeBitsWidth = StartBits;
 299                 size = FirstCode;
 300                 return true;
 301             }
 302         }
 303         return false;
 304     }
 305 };
 306
 307
 308 static bool outputByte(int code, uint8_t*& output, int outputSizeBytes, int& bytesDecodedSoFar)
 309 {
 310     if (bytesDecodedSoFar >= outputSizeBytes) return false;
 311     *output++ = static_cast<uint8_t>(code);
 312     ++bytesDecodedSoFar;
 313     return true;
 314 }
 315
 316
 317 static bool outputSequence(const Dictionary& dict, int code, uint8_t*& output, int outputSizeBytes, int& bytesDecodedSoFar, int& firstByte)
 318 {
 319     /* A sequence is stored backwards, so we have to write
 320        it to a temp then output the buffer in reverse. */
 321     int i = 0;
 322     uint8_t sequence[MaxDictEntries];
 323
 324     do {
 325         sequence[i++] = dict.entries[code].value;
 326         code = dict.entries[code].code;
 327     } while (code >= 0);
 328
 329     firstByte = sequence[--i];
 330
 331     for (; i >= 0; --i) {
 332         if (!outputByte(sequence[i], output, outputSizeBytes, bytesDecodedSoFar)) return false;
 333     }
 334     return true;
 335 }
 336
 337
 338
 339 /************************************************************************/
 340 /* External Class Implementation                                        */
 341 /************************************************************************/
 342
 343 namespace tvg {
 344
 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
 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 #endif