silo/third-party/lz4/lz4_encoder.h

   1 /*\r
   2    LZ4 Encoder - Part of LZ4 compression algorithm\r
   3    Copyright (C) 2011-2013, Yann Collet.\r
   4    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)\r
   5 \r
   6    Redistribution and use in source and binary forms, with or without\r
   7    modification, are permitted provided that the following conditions are\r
   8    met:\r
   9 \r
  10        * Redistributions of source code must retain the above copyright\r
  11    notice, this list of conditions and the following disclaimer.\r
  12        * Redistributions in binary form must reproduce the above\r
  13    copyright notice, this list of conditions and the following disclaimer\r
  14    in the documentation and/or other materials provided with the\r
  15    distribution.\r
  16 \r
  17    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS\r
  18    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT\r
  19    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR\r
  20    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT\r
  21    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\r
  22    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT\r
  23    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\r
  24    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\r
  25    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\r
  26    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE\r
  27    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\r
  28 \r
  29    You can contact the author at :\r
  30    - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html\r
  31    - LZ4 source repository : http://code.google.com/p/lz4/\r
  32 */\r
  33 \r
  34 /* lz4_encoder.h must be included into lz4.c\r
  35    The objective of this file is to create a single LZ4 compression function source\r
  36    which will be instanciated multiple times with minor variations\r
  37    depending on a set of #define.\r
  38 */\r
  39 \r
  40 \r
  41 \r
  42 //****************************\r
  43 // Check required defines\r
  44 //****************************\r
  45 \r
  46 #ifndef FUNCTION_NAME\r
  47 #  error "FUNTION_NAME is not defined"\r
  48 #endif\r
  49 \r
  50 \r
  51 //****************************\r
  52 // Local definitions\r
  53 //****************************\r
  54 \r
  55 #ifdef COMPRESS_64K\r
  56 #  define HASHLOG (MEMORY_USAGE-1)\r
  57 #  define CURRENT_H_TYPE U16\r
  58 #  define CURRENTBASE(base) const BYTE* const base = ip\r
  59 #else\r
  60 #  define HASHLOG (MEMORY_USAGE-2)\r
  61 #  define CURRENT_H_TYPE HTYPE\r
  62 #  define CURRENTBASE(base) INITBASE(base)\r
  63 #endif\r
  64 \r
  65 #define HASHTABLE_NBCELLS  (1U<<HASHLOG)\r
  66 #define LZ4_HASH(i)        (((i) * 2654435761U) >> ((MINMATCH*8)-HASHLOG))\r
  67 #define LZ4_HASHVALUE(p)   LZ4_HASH(A32(p))\r
  68 \r
  69 \r
  70 \r
  71 //****************************\r
  72 // Function code\r
  73 //****************************\r
  74 \r
  75 int FUNCTION_NAME(\r
  76 #ifdef USE_HEAPMEMORY\r
  77                  void* ctx,\r
  78 #endif\r
  79                  const char* source,\r
  80                  char* dest,\r
  81                  int inputSize\r
  82 #ifdef LIMITED_OUTPUT\r
  83                 ,int maxOutputSize\r
  84 #endif\r
  85                  )\r
  86 {\r
  87 #ifdef USE_HEAPMEMORY\r
  88     CURRENT_H_TYPE* HashTable = (CURRENT_H_TYPE*)ctx;\r
  89 #else\r
  90     CURRENT_H_TYPE HashTable[HASHTABLE_NBCELLS] = {0};\r
  91 #endif\r
  92 \r
  93     const BYTE* ip = (BYTE*) source;\r
  94     CURRENTBASE(base);\r
  95     const BYTE* anchor = ip;\r
  96     const BYTE* const iend = ip + inputSize;\r
  97     const BYTE* const mflimit = iend - MFLIMIT;\r
  98 #define matchlimit (iend - LASTLITERALS)\r
  99 \r
 100     BYTE* op = (BYTE*) dest;\r
 101 #ifdef LIMITED_OUTPUT\r
 102     BYTE* const oend = op + maxOutputSize;\r
 103 #endif\r
 104 \r
 105     int length;\r
 106     const int skipStrength = SKIPSTRENGTH;\r
 107     U32 forwardH;\r
 108 \r
 109 \r
 110     // Init\r
 111     if (inputSize<MINLENGTH) goto _last_literals;\r
 112 #ifdef COMPRESS_64K\r
 113     if (inputSize>LZ4_64KLIMIT) return 0;   // Size too large (not within 64K limit)\r
 114 #endif\r
 115 #ifdef USE_HEAPMEMORY\r
 116     memset((void*)HashTable, 0, HASHTABLESIZE);\r
 117 #endif\r
 118 \r
 119     // First Byte\r
 120     HashTable[LZ4_HASHVALUE(ip)] = (CURRENT_H_TYPE)(ip - base);\r
 121     ip++; forwardH = LZ4_HASHVALUE(ip);\r
 122 \r
 123     // Main Loop\r
 124     for ( ; ; )\r
 125     {\r
 126         int findMatchAttempts = (1U << skipStrength) + 3;\r
 127         const BYTE* forwardIp = ip;\r
 128         const BYTE* ref;\r
 129         BYTE* token;\r
 130 \r
 131         // Find a match\r
 132         do {\r
 133             U32 h = forwardH;\r
 134             int step = findMatchAttempts++ >> skipStrength;\r
 135             ip = forwardIp;\r
 136             forwardIp = ip + step;\r
 137 \r
 138             if unlikely(forwardIp > mflimit) { goto _last_literals; }\r
 139 \r
 140             forwardH = LZ4_HASHVALUE(forwardIp);\r
 141             ref = base + HashTable[h];\r
 142             HashTable[h] = (CURRENT_H_TYPE)(ip - base);\r
 143 \r
 144         } while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip)));\r
 145 \r
 146         // Catch up\r
 147         while ((ip>anchor) && (ref>(BYTE*)source) && unlikely(ip[-1]==ref[-1])) { ip--; ref--; }\r
 148 \r
 149         // Encode Literal length\r
 150         length = (int)(ip - anchor);\r
 151         token = op++;\r
 152 #ifdef LIMITED_OUTPUT\r
 153         if unlikely(op + length + (2 + 1 + LASTLITERALS) + (length>>8) > oend) return 0;   // Check output limit\r
 154 #endif\r
 155         if (length>=(int)RUN_MASK)\r
 156         {\r
 157             int len = length-RUN_MASK;\r
 158             *token=(RUN_MASK<<ML_BITS);\r
 159             for(; len >= 255 ; len-=255) *op++ = 255;\r
 160             *op++ = (BYTE)len;\r
 161         }\r
 162         else *token = (BYTE)(length<<ML_BITS);\r
 163 \r
 164         // Copy Literals\r
 165         LZ4_BLINDCOPY(anchor, op, length);\r
 166 \r
 167 _next_match:\r
 168         // Encode Offset\r
 169         LZ4_WRITE_LITTLEENDIAN_16(op,(U16)(ip-ref));\r
 170 \r
 171         // Start Counting\r
 172         ip+=MINMATCH; ref+=MINMATCH;    // MinMatch already verified\r
 173         anchor = ip;\r
 174         while likely(ip<matchlimit-(STEPSIZE-1))\r
 175         {\r
 176             UARCH diff = AARCH(ref) ^ AARCH(ip);\r
 177             if (!diff) { ip+=STEPSIZE; ref+=STEPSIZE; continue; }\r
 178             ip += LZ4_NbCommonBytes(diff);\r
 179             goto _endCount;\r
 180         }\r
 181         if (LZ4_ARCH64) if ((ip<(matchlimit-3)) && (A32(ref) == A32(ip))) { ip+=4; ref+=4; }\r
 182         if ((ip<(matchlimit-1)) && (A16(ref) == A16(ip))) { ip+=2; ref+=2; }\r
 183         if ((ip<matchlimit) && (*ref == *ip)) ip++;\r
 184 _endCount:\r
 185 \r
 186         // Encode MatchLength\r
 187         length = (int)(ip - anchor);\r
 188 #ifdef LIMITED_OUTPUT\r
 189         if unlikely(op + (1 + LASTLITERALS) + (length>>8) > oend) return 0;    // Check output limit\r
 190 #endif\r
 191         if (length>=(int)ML_MASK)\r
 192         {\r
 193             *token += ML_MASK;\r
 194             length -= ML_MASK;\r
 195             for (; length > 509 ; length-=510) { *op++ = 255; *op++ = 255; }\r
 196             if (length >= 255) { length-=255; *op++ = 255; }\r
 197             *op++ = (BYTE)length;\r
 198         }\r
 199         else *token += (BYTE)(length);\r
 200 \r
 201         // Test end of chunk\r
 202         if (ip > mflimit) { anchor = ip;  break; }\r
 203 \r
 204         // Fill table\r
 205         HashTable[LZ4_HASHVALUE(ip-2)] = (CURRENT_H_TYPE)(ip - 2 - base);\r
 206 \r
 207         // Test next position\r
 208         ref = base + HashTable[LZ4_HASHVALUE(ip)];\r
 209         HashTable[LZ4_HASHVALUE(ip)] = (CURRENT_H_TYPE)(ip - base);\r
 210         if ((ref >= ip - MAX_DISTANCE) && (A32(ref) == A32(ip))) { token = op++; *token=0; goto _next_match; }\r
 211 \r
 212         // Prepare next loop\r
 213         anchor = ip++;\r
 214         forwardH = LZ4_HASHVALUE(ip);\r
 215     }\r
 216 \r
 217 _last_literals:\r
 218     // Encode Last Literals\r
 219     {\r
 220         int lastRun = (int)(iend - anchor);\r
 221 #ifdef LIMITED_OUTPUT\r
 222         if (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize) return 0;  // Check output limit\r
 223 #endif\r
 224         if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun >= 255 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }\r
 225         else *op++ = (BYTE)(lastRun<<ML_BITS);\r
 226         memcpy(op, anchor, iend - anchor);\r
 227         op += iend-anchor;\r
 228     }\r
 229 \r
 230     // End\r
 231     return (int) (((char*)op)-dest);\r
 232 }\r
 233 \r
 234 \r
 235 \r
 236 //****************************\r
 237 // Clean defines\r
 238 //****************************\r
 239 \r
 240 // Required defines\r
 241 #undef FUNCTION_NAME\r
 242 \r
 243 // Locally Generated\r
 244 #undef HASHLOG\r
 245 #undef HASHTABLE_NBCELLS\r
 246 #undef LZ4_HASH\r
 247 #undef LZ4_HASHVALUE\r
 248 #undef CURRENT_H_TYPE\r
 249 #undef CURRENTBASE\r
 250 \r
 251 // Optional defines\r
 252 #ifdef LIMITED_OUTPUT\r
 253 #undef LIMITED_OUTPUT\r
 254 #endif\r
 255 \r
 256 #ifdef USE_HEAPMEMORY\r
 257 #undef USE_HEAPMEMORY\r
 258 #endif\r
 259 \r
 260 #ifdef COMPRESS_64K\r
 261 #undef COMPRESS_64K\r
 262 #endif\r