pithy.c

00001 //
00002 //  pithy.c
00003 //  http://github.com/johnezang/pithy
00004 //  Licensed under the terms of the BSD License, as specified below.
00005 //
00006 
00007 /*
00008  Copyright (c) 2011, John Engelhart
00009 
00010  All rights reserved.
00011 
00012  Redistribution and use in source and binary forms, with or without
00013  modification, are permitted provided that the following conditions are met:
00014 
00015  * Redistributions of source code must retain the above copyright
00016  notice, this list of conditions and the following disclaimer.
00017 
00018  * Redistributions in binary form must reproduce the above copyright
00019  notice, this list of conditions and the following disclaimer in the
00020  documentation and/or other materials provided with the distribution.
00021 
00022  * Neither the name of the Zang Industries nor the names of its
00023  contributors may be used to endorse or promote products derived from
00024  this software without specific prior written permission.
00025 
00026  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00027  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00028  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
00029  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
00030  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00031  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
00032  TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00033  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00034  LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00035  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00036  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00037 */
00038 
00039 #include <stdio.h>
00040 #include <stdint.h>
00041 #include <stdlib.h>
00042 #include <string.h>
00043 
00044 #if defined(__arm__) && defined(__ARM_NEON__)
00045 #include <arm_neon.h>
00046 #endif
00047 
00048 #include "pithy.h"
00049 
00050 #define kBlockLog   20ul
00051 #define kBlockSize  ((size_t)(1 << kBlockLog))
00052 
00053 // The maximum size that can be compressed while still allowing for the worst case compression expansion.
00054 #define PITHY_UNCOMPRESSED_MAX_LENGTH 0xdb6db6bfu // 0xdb6db6bf == 3681400511, or 3510.857 Mbytes.
00055 
00056 typedef const char *pithy_hashOffset_t;
00057 
00058 enum {
00059     PITHY_LITERAL            = 0,
00060     PITHY_COPY_1_BYTE_OFFSET = 1,
00061     PITHY_COPY_2_BYTE_OFFSET = 2,
00062     PITHY_COPY_3_BYTE_OFFSET = 3
00063 };
00064 
00065 
00066 #if       defined (__GNUC__) && (__GNUC__ >= 3)
00067 #define PITHY_ATTRIBUTES(attr, ...)        __attribute__((attr, ##__VA_ARGS__))
00068 #define PITHY_EXPECTED(cond, expect)       __builtin_expect((long)(cond), (expect))
00069 #define PITHY_EXPECT_T(cond)               PITHY_EXPECTED(cond, 1u)
00070 #define PITHY_EXPECT_F(cond)               PITHY_EXPECTED(cond, 0u)
00071 #define PITHY_PREFETCH(ptr)                __builtin_prefetch(ptr)
00072 #else  // defined (__GNUC__) && (__GNUC__ >= 3) 
00073 #define PITHY_ATTRIBUTES(attr, ...)
00074 #define PITHY_EXPECTED(cond, expect)       (cond)
00075 #define PITHY_EXPECT_T(cond)               (cond)
00076 #define PITHY_EXPECT_F(cond)               (cond)
00077 #define PITHY_PREFETCH(ptr)
00078 #endif // defined (__GNUC__) && (__GNUC__ >= 3) 
00079 
00080 #define PITHY_STATIC_INLINE        static inline PITHY_ATTRIBUTES(always_inline)
00081 #define PITHY_ALIGNED(x)                         PITHY_ATTRIBUTES(aligned(x))
00082 
00083 #if defined(NS_BLOCK_ASSERTIONS) && !defined(NDEBUG)
00084 #define NDEBUG
00085 #endif
00086 
00087 #ifdef NDEBUG
00088 #define DCHECK(condition)
00089 #else
00090 #define DCHECK(condition) do {                                                  \
00091   if(PITHY_EXPECT_F(!(condition))) {                                            \
00092     fprintf(stderr, "%s / %s @ %ld: Invalid parameter not satisfying: %s",      \
00093     __FILE__, __PRETTY_FUNCTION__, (long)__LINE__, #condition); fflush(stderr); \
00094     abort();                                                                    \
00095     }                                                                           \
00096   } while(0)
00097 #endif
00098 
00099 PITHY_STATIC_INLINE const char *pithy_Parse32WithLimit(const char *p, const char *l, size_t *OUTPUT);
00100 PITHY_STATIC_INLINE char       *pithy_Encode32(char *ptr, uint32_t v);
00101 
00102 PITHY_STATIC_INLINE uint32_t    pithy_GetUint32AtOffset(uint64_t v, uint32_t offset);
00103 PITHY_STATIC_INLINE uint32_t    pithy_HashBytes(uint32_t bytes, uint32_t shift);
00104 PITHY_STATIC_INLINE size_t      pithy_FindMatchLength(const char *s1, const char *s2, const char *s2_limit);
00105 PITHY_STATIC_INLINE char       *pithy_EmitLiteral(char *op, const char *literal, size_t len, int allow_fast_path);
00106 PITHY_STATIC_INLINE char       *pithy_EmitCopyGreaterThan63(char *op, size_t offset, size_t len);
00107 PITHY_STATIC_INLINE char       *pithy_EmitCopyLessThan63(char *op, size_t offset, size_t len);
00108 PITHY_STATIC_INLINE char       *pithy_EmitCopy(char *op, size_t offset, size_t len);
00109 
00110 PITHY_STATIC_INLINE uint16_t pithy_Load16(const void *p)        { uint16_t t; memcpy(&t, p, sizeof(t)); return (t); }
00111 PITHY_STATIC_INLINE uint32_t pithy_Load32(const void *p)        { uint32_t t; memcpy(&t, p, sizeof(t)); return (t); }
00112 PITHY_STATIC_INLINE uint64_t pithy_Load64(const void *p)        { uint64_t t; memcpy(&t, p, sizeof(t)); return (t); }
00113 PITHY_STATIC_INLINE void     pithy_Store16(void *p, uint16_t v) { memcpy(p, &v, sizeof(v)); }
00114 PITHY_STATIC_INLINE void     pithy_Store32(void *p, uint32_t v) { memcpy(p, &v, sizeof(v)); }
00115 PITHY_STATIC_INLINE void     pithy_Store64(void *p, uint64_t v) { memcpy(p, &v, sizeof(v)); }
00116 
00117 #define pithy_Move64(dst,src)  pithy_Store64(dst, pithy_Load64(src));
00118 #define pithy_Move128(dst,src) pithy_Move64(dst, src); pithy_Move64(dst + 8ul, src + 8ul);
00119 
00120 #ifdef __BIG_ENDIAN__
00121 
00122 #ifdef _MSC_VER
00123 #include <stdlib.h>
00124 #define pithy_bswap_16(x) _byteswap_ushort(x)
00125 #define pithy_bswap_32(x) _byteswap_ulong(x)
00126 #define pithy_bswap_64(x) _byteswap_uint64(x)
00127 
00128 #elif defined(__APPLE__)
00129 
00130 // Mac OS X / Darwin features
00131 #include <libkern/OSByteOrder.h>
00132 #define pithy_bswap_16(x) OSSwapInt16(x)
00133 #define pithy_bswap_32(x) OSSwapInt32(x)
00134 #define pithy_bswap_64(x) OSSwapInt64(x)
00135 #else
00136 #include <byteswap.h>
00137 #endif
00138 
00139 #endif  // __BIG_ENDIAN__
00140 
00141 // Conversion functions.
00142 #ifdef __BIG_ENDIAN__
00143 #define pithy_FromHost16(x)    ((uint16_t)pithy_bswap_16(x))
00144 #define pithy_ToHost16(x)      ((uint16_t)pithy_bswap_16(x))
00145 #define pithy_FromHost32(x)    ((uint32_t)pithy_bswap_32(x))
00146 #define pithy_ToHost32(x)      ((uint32_t)pithy_bswap_32(x))
00147 #define pithy_IsLittleEndian() (0)
00148 
00149 #else  // !defined(__BIG_ENDIAN__)
00150 #define pithy_FromHost16(x)    ((uint16_t)(x))
00151 #define pithy_ToHost16(x)      ((uint16_t)(x))
00152 #define pithy_FromHost32(x)    ((uint32_t)(x))
00153 #define pithy_ToHost32(x)      ((uint32_t)(x))
00154 #define pithy_IsLittleEndian() (1)
00155 
00156 #endif  // !defined(__BIG_ENDIAN__)
00157 
00158 #define pithy_LoadHost16(p)     pithy_ToHost16(pithy_Load16((const void *)(p)))
00159 #define pithy_StoreHost16(p, v) pithy_Store16((void *)(p), pithy_FromHost16(v))
00160 #define pithy_LoadHost32(p)     pithy_ToHost32(pithy_Load32((p)))
00161 #define pithy_StoreHost32(p, v) pithy_Store32((p), pithy_FromHost32(v))
00162 
00163 PITHY_STATIC_INLINE void pithy_StoreHost24(char *p, uint32_t v)
00164 {
00165     *p++ = (v & 0xffu);
00166     *p++ = ((v >> 8) & 0xffu);
00167     *p++ = ((v >> 16) & 0xffu);
00168 }
00169 
00170 #if defined (__GNUC__) && (__GNUC__ >= 3)
00171 
00172 #define pithy_Log2Floor(n)           ({typeof(n) _n = (n); _n == 0 ? (int)-1 : (int)(31 ^ __builtin_clz(_n));})
00173 #define pithy_FindLSBSetNonZero32(n) ((int)__builtin_ctz((uint32_t)(n)))
00174 #define pithy_FindLSBSetNonZero64(n) ((int)__builtin_ctzll((uint64_t)(n)))
00175 #define pithy_FindMSBSetNonZero32(n) ((int)__builtin_clz((uint32_t)(n)))
00176 #define pithy_FindMSBSetNonZero64(n) ((int)__builtin_clzll((uint64_t)(n)))
00177 
00178 #else  // Portable versions, !GNUC || GNUC < 3
00179 
00180 PITHY_STATIC_INLINE int pithy_Log2Floor(uint32_t n)
00181 {
00182     if (n == 0u) {
00183         return (-1);
00184     }
00185     int i = 0, log = 0;
00186     uint32_t value = n;
00187     for (i = 4; i >= 0; --i) {
00188         int shift = (1 << i);
00189         uint32_t x = value >> shift;
00190         if (x != 0u) {
00191             value = x;
00192             log += shift;
00193         }
00194     }
00195     DCHECK(value == 1);
00196     return (log);
00197 }
00198 
00199 PITHY_STATIC_INLINE int pithy_FindLSBSetNonZero32(uint32_t n)
00200 {
00201     int i = 0, rc = 31, shift = 0;
00202     for (i = 4, shift = 1 << 4; i >= 0; --i) {
00203         const uint32_t x = n << shift;
00204         if (x != 0u) {
00205             n = x;
00206             rc -= shift;
00207         }
00208         shift >>= 1;
00209     }
00210     return (rc);
00211 }
00212 
00213 PITHY_STATIC_INLINE int pithy_FindLSBSetNonZero64(uint64_t n)
00214 {
00215     const uint32_t bottomBits = n;
00216     if (bottomBits == 0u) {
00217         return (32 + pithy_FindLSBSetNonZero32((n >> 32)));
00218     } else {
00219         return (pithy_FindLSBSetNonZero32(bottomBits));
00220     }
00221 }
00222 
00223 PITHY_STATIC_INLINE int pithy_FindMSBSetNonZero32(uint32_t n)
00224 {
00225     int i;
00226     uint32_t x, rc = 32, shift = 1 << 4;
00227     for (i = 3; i >= 0; --i) {
00228         x = n >> shift;
00229         if (x != 0) {
00230             rc -= shift;
00231             n = x;
00232         }
00233         shift >>= 1;
00234     }
00235     x = n >> shift;
00236     return (rc - ((x != 0) ? 2 : n));
00237 }
00238 
00239 PITHY_STATIC_INLINE int pithy_FindMSBSetNonZero64(uint64_t n)
00240 {
00241     const uint32_t upperBits = n >> 32;
00242     if (upperBits == 0u) {
00243         return (32 + pithy_FindMSBSetNonZero32((n)));
00244     } else {
00245         return (pithy_FindMSBSetNonZero32(upperBits));
00246     }
00247 }
00248 
00249 #endif  // End portable versions.
00250 
00251 PITHY_STATIC_INLINE const char *pithy_Parse32WithLimit(const char *p, const char *l, size_t *resultOut)
00252 {
00253     const unsigned char *ptr = (const unsigned char *)p, *limit = (const unsigned char *)l;
00254     size_t   resultShift = 0ul, result = 0ul;
00255     uint32_t encodedByte = 0u;
00256 
00257     for (resultShift = 0ul; resultShift <= 28ul; resultShift += 7ul) {
00258         if (ptr >= limit) {
00259             return (NULL);
00260         }
00261         encodedByte = *(ptr++);
00262         result |= (encodedByte & 127u) << resultShift;
00263         if (encodedByte < ((resultShift == 28ul) ? 16u : 128u)) {
00264             goto done;
00265         }
00266     }
00267     return (NULL);
00268 done:
00269     *resultOut = result;
00270     return ((const char *)ptr);
00271 }
00272 
00273 PITHY_STATIC_INLINE char *pithy_Encode32(char *sptr, uint32_t v)
00274 {
00275     unsigned char *ptr = (unsigned char *)sptr;
00276     if (v < (1u <<  7)) {
00277         *(ptr++) = v;
00278     } else if (v < (1u << 14)) {
00279         *(ptr++) = v | 0x80u;
00280         *(ptr++) = (v >> 7);
00281     } else if (v < (1u << 21)) {
00282         *(ptr++) = v | 0x80u;
00283         *(ptr++) = (v >> 7) | 0x80u;
00284         *(ptr++) = (v >> 14);
00285     } else if (v < (1u << 28)) {
00286         *(ptr++) = v | 0x80u;
00287         *(ptr++) = (v >> 7) | 0x80u;
00288         *(ptr++) = (v >> 14) | 0x80u;
00289         *(ptr++) = (v >> 21);
00290     } else {
00291         *(ptr++) = v | 0x80u;
00292         *(ptr++) = (v >> 7) | 0x80u;
00293         *(ptr++) = (v >> 14) | 0x80u;
00294         *(ptr++) = (v >> 21) | 0x80u;
00295         *(ptr++) = (v >> 28);
00296     }
00297     return ((char *)ptr);
00298 }
00299 
00300 
00301 PITHY_STATIC_INLINE uint32_t pithy_GetUint32AtOffset(uint64_t v, uint32_t offset)
00302 {
00303     DCHECK(offset <= 4);
00304     return (v >> (pithy_IsLittleEndian() ? (8u * offset) : (32u - (8u * offset))));
00305 }
00306 
00307 
00308 PITHY_STATIC_INLINE uint32_t pithy_HashBytes(uint32_t bytes, uint32_t shift)
00309 {
00310     uint32_t kMul = 0x1e35a7bdU;
00311     return ((bytes * kMul) >> shift);
00312 }
00313 
00314 
00315 PITHY_STATIC_INLINE size_t pithy_FindMatchLength(const char *s1, const char *s2, const char *s2_limit)
00316 {
00317     DCHECK(s2_limit >= s2);
00318     const char *ms1 = s1, *ms2 = s2;
00319 
00320 #if defined(__LP64__)
00321     while (PITHY_EXPECT_T(ms2 < (s2_limit - 8ul))) {
00322         uint64_t x = pithy_Load64(ms1) ^ pithy_Load64(ms2);
00323         if (PITHY_EXPECT_F(x == 0ul))  {
00324             ms1 += 8ul;
00325             ms2 += 8ul;
00326         } else {
00327             return ((ms1 - s1) + ((unsigned int)(pithy_IsLittleEndian() ? (pithy_FindLSBSetNonZero64(x) >> 3) :
00328                                                  (pithy_FindMSBSetNonZero64(x) >> 3))));
00329         }
00330     }
00331 #else
00332     while (PITHY_EXPECT_T(ms2 < (s2_limit - 4u ))) {
00333         uint32_t x = pithy_Load32(ms1) ^ pithy_Load32(ms2);
00334         if (PITHY_EXPECT_F(x == 0u))  {
00335             ms1 += 4u;
00336             ms2 += 4u;
00337         } else {
00338             return ((ms1 - s1) + ((unsigned int)(pithy_IsLittleEndian() ?
00339                                     (pithy_FindLSBSetNonZero32(x) >> 3) : (pithy_FindMSBSetNonZero32(x) >> 3))));
00340         }
00341     }
00342 #endif
00343     while (PITHY_EXPECT_T(ms2 <  s2_limit)) {
00344         if (PITHY_EXPECT_T(*ms1 == *ms2)) {
00345             ms1++;
00346             ms2++;
00347         } else {
00348             return (ms1 - s1);
00349         }
00350     }
00351     return (ms1 - s1);
00352 }
00353 
00354 
00355 PITHY_STATIC_INLINE char *pithy_EmitLiteral(char *op, const char *literal, size_t len, int allow_fast_path)
00356 {
00357     int n = len - 1l;
00358     if (PITHY_EXPECT_T(n < 60l)) {
00359         *op++ = PITHY_LITERAL | (n << 2);
00360         if (PITHY_EXPECT_T(allow_fast_path) && PITHY_EXPECT_T(len <= 16ul)) {
00361             pithy_Move128(op, literal);
00362             return (op + len);
00363         }
00364     } else {
00365         char *base = op;
00366         int count = 0;
00367         op++;
00368         while (n > 0l) {
00369             *op++ = n & 0xff;
00370             n >>= 8;
00371             count++;
00372         }
00373         DCHECK((count >= 1) && (count <= 4));
00374         *base = PITHY_LITERAL | ((59 + count) << 2);
00375     }
00376     memcpy(op, literal, len);
00377     return (op + len);
00378 }
00379 
00380 PITHY_STATIC_INLINE char *pithy_EmitCopyGreaterThan63(char *op, size_t offset, size_t len)
00381 {
00382     DCHECK((len < 65536ul) && (len >= 63ul) && (offset < kBlockSize));
00383     if (PITHY_EXPECT_T(offset < 65536ul)) {
00384         if (PITHY_EXPECT_T(len < (256ul + 63ul))) {
00385             *op++ = PITHY_COPY_2_BYTE_OFFSET | (62 << 2);
00386             pithy_StoreHost16(op, offset);
00387             op += 2ul;
00388             *op++ = (len - 63ul);
00389         } else {
00390             *op++ = PITHY_COPY_2_BYTE_OFFSET | (63 << 2);
00391             pithy_StoreHost16(op, offset);
00392             op += 2ul;
00393             pithy_StoreHost16(op, len);
00394             op += 2ul;
00395         }
00396     } else {
00397         if (PITHY_EXPECT_T(len < (256ul + 63ul))) {
00398             *op++ = PITHY_COPY_3_BYTE_OFFSET | (62 << 2);
00399             pithy_StoreHost24(op, offset);
00400             op += 3ul;
00401             *op++ = (len - 63ul);
00402         } else {
00403             *op++ = PITHY_COPY_3_BYTE_OFFSET | (63 << 2);
00404             pithy_StoreHost24(op, offset);
00405             op += 3ul;
00406             pithy_StoreHost16(op, len);
00407             op += 2ul;
00408         }
00409     }
00410     return (op);
00411 }
00412 
00413 PITHY_STATIC_INLINE char *pithy_EmitCopyLessThan63(char *op, size_t offset, size_t len)
00414 {
00415     DCHECK((len < 63ul) && (len >= 4ul) && (offset < kBlockSize));
00416     if (PITHY_EXPECT_T(len < 12ul) && PITHY_EXPECT_T(offset < 2048ul)) {
00417         int lenMinus4 = len - 4l;
00418         DCHECK(lenMinus4 < 8l);
00419         *op++ = PITHY_COPY_1_BYTE_OFFSET | (lenMinus4 << 2) | ((offset >> 8) << 5);
00420         *op++ = offset & 0xff;
00421     } else {
00422         if (PITHY_EXPECT_T(offset < 65536ul)) {
00423             *op++ = PITHY_COPY_2_BYTE_OFFSET | ((len - 1ul) << 2);
00424             pithy_StoreHost16(op, offset);
00425             op += 2ul;
00426         } else {
00427             *op++ = PITHY_COPY_3_BYTE_OFFSET | ((len - 1ul) << 2);
00428             pithy_StoreHost24(op, offset);
00429             op += 3ul;
00430         }
00431     }
00432     return (op);
00433 }
00434 
00435 PITHY_STATIC_INLINE char *pithy_EmitCopy(char *op, size_t offset, size_t len)
00436 {
00437     while (PITHY_EXPECT_F(len >= 63ul)) {
00438         op = pithy_EmitCopyGreaterThan63(op, offset, (len >= 65539ul) ? 65535ul : len);
00439         len -= (len >= 65539ul) ? 65535ul : len;
00440     }
00441     DCHECK((len > 0ul) ? ((len >= 4ul) && (len < 63ul)) : 1);
00442     if ( PITHY_EXPECT_T(len >  0ul)) {
00443         op = pithy_EmitCopyLessThan63(op, offset, len);
00444         len -= len;
00445     }
00446     return (op);
00447 }
00448 
00449 size_t pithy_MaxCompressedLength(size_t inputLength)
00450 {
00451     return ((inputLength >= PITHY_UNCOMPRESSED_MAX_LENGTH) ? 0ul : 32ul + inputLength + (inputLength / 6ul));
00452 }
00453 
00454 size_t pithy_Compress(const char *uncompressed,
00455                       size_t uncompressedLength,
00456                       char *compressedOut,
00457                       size_t compressedOutLength,
00458                       int compressionLevel)
00459 {
00460 
00461     if ((pithy_MaxCompressedLength(uncompressedLength) > compressedOutLength) ||
00462             (uncompressedLength >= PITHY_UNCOMPRESSED_MAX_LENGTH) ||
00463             (uncompressedLength == 0ul)) {
00464         return (0ul);
00465     }
00466 
00467     char *compressedPtr = compressedOut;
00468 
00469     size_t hashTableSize = 0x100ul, maxHashTableSize = 1 << (12ul + (((compressionLevel < 0) ? 0 :
00470                            (compressionLevel > 9) ? 9 : compressionLevel) / 2ul));
00471     while ((hashTableSize < maxHashTableSize) && (hashTableSize < uncompressedLength)) {
00472         hashTableSize <<= 1;
00473     }
00474     pithy_hashOffset_t stackHashTable[hashTableSize], *heapHashTable = NULL, *hashTable = stackHashTable;
00475     if ((sizeof(pithy_hashOffset_t) * hashTableSize) >= (1024ul * 128ul)) {
00476         if ((heapHashTable = malloc(sizeof(pithy_hashOffset_t) * hashTableSize)) == NULL) {
00477             return (0ul);
00478         }
00479         hashTable = heapHashTable;
00480     }
00481     size_t x = 0ul;
00482     for (x = 0ul; x < hashTableSize; x++) {
00483         hashTable[x] = uncompressed;
00484     }
00485 
00486 #ifndef NDEBUG
00487     char *const compressedOutEnd = compressedOut + compressedOutLength;
00488 #endif
00489     compressedPtr = pithy_Encode32(compressedPtr, uncompressedLength);
00490     DCHECK(compressedPtr <= compressedOutEnd);
00491     {
00492         const char *uncompressedPtr = uncompressed;
00493         const char *uncompressedEnd = uncompressed + uncompressedLength;
00494         const char *nextEmitUncompressedPtr = uncompressedPtr;
00495         DCHECK((hashTableSize & (hashTableSize - 1l)) == 0);
00496         const int shift = 32 - pithy_Log2Floor(hashTableSize);
00497         DCHECK((UINT32_MAX >> shift) == (hashTableSize - 1l));
00498         size_t skip = 32ul;
00499 
00500         if (PITHY_EXPECT_T(uncompressedLength >= 15ul)) {
00501             const char *uncompressedEndLimit = uncompressed + uncompressedLength - 15ul;
00502             uint32_t uncompressedBytes;
00503             uint32_t nextUncompressedBytes = pithy_Load32(++uncompressedPtr);
00504             uint32_t nextUncompressedBytesHash = pithy_HashBytes(nextUncompressedBytes, shift);
00505 
00506             while (1) {
00507                 DCHECK(nextEmitUncompressedPtr < uncompressedPtr);
00508                 const char *nextUncompressedPtr = uncompressedPtr, *matchCandidatePtr = NULL;
00509 
00510                 skip = (((skip - 32ul) * 184ul) >> 8) + 32ul;
00511 
00512                 do {
00513                     uncompressedPtr   = nextUncompressedPtr;
00514                     uncompressedBytes = nextUncompressedBytes;
00515                     uint32_t uncompressedBytesHash = nextUncompressedBytesHash;
00516                     DCHECK(uncompressedBytesHash == pithy_HashBytes(uncompressedBytes, shift));
00517                     size_t skipBytesBetweenHashLookups = skip >> 5;
00518                     skip += ((skip * 7ul) >> 11) + 1ul;
00519                     nextUncompressedPtr              = uncompressedPtr + skipBytesBetweenHashLookups;
00520                     if (PITHY_EXPECT_F(nextUncompressedPtr > uncompressedEndLimit)) {
00521                         goto emit_remainder;
00522                     }
00523                     nextUncompressedBytes            = pithy_Load32(nextUncompressedPtr);
00524                     nextUncompressedBytesHash        = pithy_HashBytes(nextUncompressedBytes, shift);
00525                     matchCandidatePtr                = hashTable[uncompressedBytesHash];
00526                     DCHECK((matchCandidatePtr >= uncompressed) && (matchCandidatePtr < uncompressedPtr));
00527                     hashTable[uncompressedBytesHash] = uncompressedPtr;
00528                 } while ((PITHY_EXPECT_T(uncompressedBytes != pithy_Load32(matchCandidatePtr))) ||
00529                          PITHY_EXPECT_F((uncompressedPtr - matchCandidatePtr) >= ((int)(kBlockSize - 2ul))));
00530 
00531                 DCHECK((nextEmitUncompressedPtr + 16ul) <= uncompressedEnd);
00532                 compressedPtr = pithy_EmitLiteral(compressedPtr,
00533                                                   nextEmitUncompressedPtr,
00534                                                   uncompressedPtr - nextEmitUncompressedPtr,
00535                                                   1);
00536                 DCHECK(compressedPtr <= compressedOutEnd);
00537                 uint64_t uncompressedBytes64 = 0ul;
00538 
00539                 do {
00540                     if (compressionLevel > 2) {
00541                         DCHECK((uncompressedPtr + 5ul) <= uncompressedEnd);
00542                         uncompressedBytes64 = pithy_Load64((uint64_t*)uncompressedPtr + 1ul);
00543                         hashTable[pithy_HashBytes(pithy_GetUint32AtOffset(uncompressedBytes64, 0u), shift)] =
00544                             uncompressedPtr + 1ul;
00545                         if (compressionLevel > 4) {
00546                             hashTable[pithy_HashBytes(pithy_GetUint32AtOffset(uncompressedBytes64, 1u), shift)] =
00547                                 uncompressedPtr + 2ul;
00548                         }
00549                     }
00550 
00551                     DCHECK((matchCandidatePtr >= uncompressed) &&
00552                            (matchCandidatePtr <= uncompressedPtr) &&
00553                            ((matchCandidatePtr + 4ul) <= uncompressedEnd) &&
00554                            ((uncompressedPtr + 4ul) <= uncompressedEnd));
00555 
00556                     size_t matchCandidateLength = 4ul + pithy_FindMatchLength(matchCandidatePtr + 4ul,
00557                                                   uncompressedPtr + 4ul,
00558                                                   uncompressedEnd);
00559                     DCHECK(((matchCandidatePtr + matchCandidateLength) >= uncompressed) &&
00560                            ((matchCandidatePtr + matchCandidateLength) <= uncompressedEnd));
00561                     DCHECK(0 == memcmp(uncompressedPtr, matchCandidatePtr, matchCandidateLength));
00562                     compressedPtr = pithy_EmitCopy(compressedPtr,
00563                                                    uncompressedPtr - matchCandidatePtr,
00564                                                    matchCandidateLength);
00565                     DCHECK(compressedPtr <= compressedOutEnd);
00566                     uncompressedPtr += matchCandidateLength;
00567                     DCHECK(uncompressedPtr <= uncompressedEnd);
00568                     nextEmitUncompressedPtr = uncompressedPtr;
00569                     if (PITHY_EXPECT_F(uncompressedPtr >= uncompressedEndLimit)) {
00570                         goto emit_remainder;
00571                     }
00572 
00573                     DCHECK(((uncompressedPtr - 3ul) >= uncompressed) && (uncompressedPtr <= uncompressedEnd));
00574 
00575                     uncompressedBytes64 = pithy_Load64((uint64_t*)uncompressedPtr - 3ul);
00576 
00577                     if (compressionLevel > 0) {
00578                         if (compressionLevel > 8) {
00579                             hashTable[pithy_HashBytes(pithy_GetUint32AtOffset(uncompressedBytes64, 0u), shift)] =
00580                                 uncompressedPtr - 3ul;
00581                         }
00582                         if (compressionLevel > 6) {
00583                             hashTable[pithy_HashBytes(pithy_GetUint32AtOffset(uncompressedBytes64, 1u), shift)] =
00584                                 uncompressedPtr - 2ul;
00585                         }
00586                         hashTable[pithy_HashBytes(pithy_GetUint32AtOffset(uncompressedBytes64, 2u), shift)] =
00587                             uncompressedPtr - 1ul;
00588                     }
00589 
00590                     uncompressedBytes = pithy_GetUint32AtOffset(uncompressedBytes64, 3u);
00591                     uint32_t uncompressedBytesHash = pithy_HashBytes(uncompressedBytes, shift);
00592                     matchCandidatePtr = hashTable[uncompressedBytesHash];
00593                     DCHECK((matchCandidatePtr >= uncompressed) && (matchCandidatePtr < uncompressedPtr));
00594                     hashTable[uncompressedBytesHash] = uncompressedPtr;
00595                 } while (PITHY_EXPECT_F(uncompressedBytes == pithy_Load32(matchCandidatePtr)) &&
00596                          PITHY_EXPECT_T((uncompressedPtr - matchCandidatePtr) < ((int)(kBlockSize - 2ul))));
00597 
00598                 nextUncompressedBytes = pithy_GetUint32AtOffset(uncompressedBytes64, 4u);
00599                 nextUncompressedBytesHash = pithy_HashBytes(nextUncompressedBytes, shift);
00600                 uncompressedPtr++;
00601             }
00602         }
00603 
00604 emit_remainder:
00605         if (nextEmitUncompressedPtr < uncompressedEnd) {
00606             compressedPtr = pithy_EmitLiteral(compressedPtr,
00607                                               nextEmitUncompressedPtr,
00608                                               uncompressedEnd - nextEmitUncompressedPtr,
00609                                               0);
00610         }
00611     }
00612 
00613     pithy_Store32(compressedPtr, 0);
00614     compressedPtr += 4;
00615 
00616     DCHECK((size_t)(compressedPtr - compressedOut) <= compressedOutLength);
00617     if (heapHashTable != NULL) {
00618         free(heapHashTable);
00619         heapHashTable = NULL;
00620         hashTable = NULL;
00621     }
00622     return (compressedPtr - compressedOut);
00623 }
00624 
00625 
00626 static const uint32_t pithy_wordmask[] = {
00627     0u, 0xffu, 0xffffu, 0xffffffu, 0xffffffffu
00628 };
00629 
00630 
00631 static const uint16_t pithy_charTable[256] = {
00632     0x0001, 0x0804, 0x1001, 0x1801, 0x0002, 0x0805, 0x1002, 0x1802,
00633     0x0003, 0x0806, 0x1003, 0x1803, 0x0004, 0x0807, 0x1004, 0x1804,
00634     0x0005, 0x0808, 0x1005, 0x1805, 0x0006, 0x0809, 0x1006, 0x1806,
00635     0x0007, 0x080a, 0x1007, 0x1807, 0x0008, 0x080b, 0x1008, 0x1808,
00636     0x0009, 0x0904, 0x1009, 0x1809, 0x000a, 0x0905, 0x100a, 0x180a,
00637     0x000b, 0x0906, 0x100b, 0x180b, 0x000c, 0x0907, 0x100c, 0x180c,
00638     0x000d, 0x0908, 0x100d, 0x180d, 0x000e, 0x0909, 0x100e, 0x180e,
00639     0x000f, 0x090a, 0x100f, 0x180f, 0x0010, 0x090b, 0x1010, 0x1810,
00640     0x0011, 0x0a04, 0x1011, 0x1811, 0x0012, 0x0a05, 0x1012, 0x1812,
00641     0x0013, 0x0a06, 0x1013, 0x1813, 0x0014, 0x0a07, 0x1014, 0x1814,
00642     0x0015, 0x0a08, 0x1015, 0x1815, 0x0016, 0x0a09, 0x1016, 0x1816,
00643     0x0017, 0x0a0a, 0x1017, 0x1817, 0x0018, 0x0a0b, 0x1018, 0x1818,
00644     0x0019, 0x0b04, 0x1019, 0x1819, 0x001a, 0x0b05, 0x101a, 0x181a,
00645     0x001b, 0x0b06, 0x101b, 0x181b, 0x001c, 0x0b07, 0x101c, 0x181c,
00646     0x001d, 0x0b08, 0x101d, 0x181d, 0x001e, 0x0b09, 0x101e, 0x181e,
00647     0x001f, 0x0b0a, 0x101f, 0x181f, 0x0020, 0x0b0b, 0x1020, 0x1820,
00648     0x0021, 0x0c04, 0x1021, 0x1821, 0x0022, 0x0c05, 0x1022, 0x1822,
00649     0x0023, 0x0c06, 0x1023, 0x1823, 0x0024, 0x0c07, 0x1024, 0x1824,
00650     0x0025, 0x0c08, 0x1025, 0x1825, 0x0026, 0x0c09, 0x1026, 0x1826,
00651     0x0027, 0x0c0a, 0x1027, 0x1827, 0x0028, 0x0c0b, 0x1028, 0x1828,
00652     0x0029, 0x0d04, 0x1029, 0x1829, 0x002a, 0x0d05, 0x102a, 0x182a,
00653     0x002b, 0x0d06, 0x102b, 0x182b, 0x002c, 0x0d07, 0x102c, 0x182c,
00654     0x002d, 0x0d08, 0x102d, 0x182d, 0x002e, 0x0d09, 0x102e, 0x182e,
00655     0x002f, 0x0d0a, 0x102f, 0x182f, 0x0030, 0x0d0b, 0x1030, 0x1830,
00656     0x0031, 0x0e04, 0x1031, 0x1831, 0x0032, 0x0e05, 0x1032, 0x1832,
00657     0x0033, 0x0e06, 0x1033, 0x1833, 0x0034, 0x0e07, 0x1034, 0x1834,
00658     0x0035, 0x0e08, 0x1035, 0x1835, 0x0036, 0x0e09, 0x1036, 0x1836,
00659     0x0037, 0x0e0a, 0x1037, 0x1837, 0x0038, 0x0e0b, 0x1038, 0x1838,
00660     0x0039, 0x0f04, 0x1039, 0x1839, 0x003a, 0x0f05, 0x103a, 0x183a,
00661     0x003b, 0x0f06, 0x103b, 0x183b, 0x003c, 0x0f07, 0x103c, 0x183c,
00662     0x0801, 0x0f08, 0x103d, 0x183d, 0x1001, 0x0f09, 0x103e, 0x183e,
00663     0x1801, 0x0f0a, 0x103f, 0x183f, 0x2001, 0x0f0b, 0x1040, 0x1840
00664 };
00665 
00666 
00667 int pithy_GetDecompressedLength(const char *compressed, size_t compressedLength, size_t *decompressedOutLengthResult)
00668 {
00669     const char *compressedEnd = compressed + compressedLength;
00670     size_t decompressedLength = 0ul;
00671     if (pithy_Parse32WithLimit(compressed, compressedEnd, &decompressedLength) != NULL) {
00672         *decompressedOutLengthResult = decompressedLength;
00673         return (1);
00674     } else {
00675         return (0);
00676     }
00677 }
00678 
00679 
00680 int pithy_Decompress(const char *compressed, size_t compressedLength, char *decompressedOut,
00681                      size_t decompressedOutLength)
00682 {
00683     const char *nextCompressedPtr = NULL, *compressedEnd = (compressed + compressedLength);
00684     size_t parsedDecompressedLength = 0ul;
00685     if (((nextCompressedPtr = pithy_Parse32WithLimit(compressed, compressedEnd, &parsedDecompressedLength)) == NULL) ||
00686             (parsedDecompressedLength > decompressedOutLength)) {
00687         return (0);
00688     }
00689 
00690     char *decompressedPtr = decompressedOut, *decompressedEnd = decompressedOut + parsedDecompressedLength;
00691 
00692     while (1) {
00693         const char *compressedPtr = nextCompressedPtr;
00694         DCHECK(compressedPtr <= compressedEnd);
00695         if (PITHY_EXPECT_F(compressedPtr >= compressedEnd)) {
00696             break;
00697         }
00698 
00699         const unsigned char c          = *((const unsigned char *)(compressedPtr++));
00700         const unsigned char cLowerBits = (c & 0x3u);
00701         const int       spaceLeft  = (decompressedEnd - decompressedPtr);
00702 
00703         if ((cLowerBits == PITHY_LITERAL)) {
00704             size_t literalLength = (c >> 2) + 1;
00705             if (PITHY_EXPECT_T(literalLength <= 16ul) && PITHY_EXPECT_T((compressedEnd - compressedPtr) >= 16l) &&
00706                     PITHY_EXPECT_T(spaceLeft >= 16l)) {
00707                 pithy_Move128(decompressedPtr, compressedPtr);
00708             } else {
00709                 if (PITHY_EXPECT_F(literalLength > 60)) {
00710                     if (PITHY_EXPECT_F((compressedPtr + 4) > compressedEnd)) {
00711                         break;
00712                     }
00713                     size_t literalLengthBytes = literalLength - 60;
00714                     literalLength = (pithy_LoadHost32(compressedPtr) & pithy_wordmask[literalLengthBytes]) + 1;
00715                     compressedPtr += literalLengthBytes;
00716                 }
00717                 if (PITHY_EXPECT_F(spaceLeft < (int)literalLength) ||
00718                         PITHY_EXPECT_F((compressedPtr + literalLength) > compressedEnd)) {
00719                     break;
00720                 }
00721                 memcpy(decompressedPtr, compressedPtr, literalLength);
00722             }
00723             nextCompressedPtr  = compressedPtr + literalLength;
00724             decompressedPtr   += literalLength;
00725         } else {
00726             const uint32_t entry      = pithy_charTable[c];
00727             const size_t   trailer    = pithy_LoadHost32(compressedPtr) & pithy_wordmask[cLowerBits];
00728             size_t   length     = entry & 0xffu;
00729             const size_t   copyOffset = ((entry & 0x700u) + trailer);
00730 
00731             compressedPtr += cLowerBits;
00732 
00733             DCHECK((compressedPtr <= compressedEnd) && (copyOffset > 0ul) && (spaceLeft > 0l) && (length > 0ul));
00734 
00735             if (PITHY_EXPECT_F((decompressedPtr - decompressedOut) <= ((int)copyOffset - 1l))) {
00736                 break;
00737             }
00738             if (PITHY_EXPECT_T(length <= 16ul) && 
00739                 PITHY_EXPECT_T(copyOffset >= 16ul) && 
00740                 PITHY_EXPECT_T(spaceLeft >= 16l)) {
00741                 pithy_Move128(decompressedPtr, decompressedPtr - copyOffset);
00742             } else {
00743                 if (PITHY_EXPECT_F(length >= 63ul)) {
00744                     if (PITHY_EXPECT_T(length == 63ul)) {
00745                         if (PITHY_EXPECT_F((compressedPtr + 1) > compressedEnd)) {
00746                             break;
00747                         }
00748                         length = (*((unsigned char *)compressedPtr++)) + 63ul;
00749                     } else {
00750                         if (PITHY_EXPECT_F((compressedPtr + 2) > compressedEnd)) {
00751                             break;
00752                         }
00753                         length = pithy_LoadHost16(compressedPtr);
00754                         compressedPtr += 2ul;
00755                     }
00756                 }
00757 
00758                 char    *copyFrom   = decompressedPtr - copyOffset, *copyTo = decompressedPtr;
00759                 int  copyLength = (int)length;
00760 
00761                 if (PITHY_EXPECT_F(copyLength > 256l) && PITHY_EXPECT_T(copyOffset > (size_t)copyLength)) {
00762                     if (PITHY_EXPECT_F(spaceLeft < copyLength)) {
00763                         break;
00764                     }
00765                     memcpy(copyTo, copyFrom, copyLength);
00766                 } else {
00767                     if (PITHY_EXPECT_T(spaceLeft >= (copyLength + 24)) && PITHY_EXPECT_T(copyLength > 0l)) {
00768                         while ((copyTo - copyFrom) < 16l) {
00769                             pithy_Move128(copyTo, copyFrom);
00770                             copyLength -= copyTo - copyFrom;
00771                             copyTo += copyTo - copyFrom;
00772                         }
00773                         while (copyLength          > 0l)  {
00774                             pithy_Move128(copyTo, copyFrom);
00775                             copyFrom   += 16l;
00776                             copyTo += 16l;
00777                             copyLength -= 16l;
00778                         }
00779                     } else {
00780                         if (PITHY_EXPECT_F(spaceLeft < copyLength) || PITHY_EXPECT_F(copyLength <= 0l)) {
00781                             break;
00782                         }
00783                         do {
00784                             *copyTo++ = *copyFrom++;
00785                         } while (--copyLength > 0l);
00786                     }
00787                 }
00788             }
00789             nextCompressedPtr  = compressedPtr;
00790             decompressedPtr   += length;
00791         }
00792     }
00793 
00794     return (decompressedPtr == decompressedEnd);
00795 }