silo/third-party/lz4/lz4hc_encoder.h

   1 /*\r
   2    LZ4 HC Encoder - Part of LZ4 HC 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 /* lz4hc_encoder.h must be included into lz4hc.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 // Check required defines\r
  42 //****************************\r
  43 \r
  44 #ifndef FUNCTION_NAME\r
  45 #  error "FUNTION_NAME is not defined"\r
  46 #endif\r
  47 \r
  48 \r
  49 //****************************\r
  50 // Local definitions\r
  51 //****************************\r
  52 #define COMBINED_NAME_RAW(n1,n2) n1 ## n2\r
  53 #define COMBINED_NAME(n1,n2) COMBINED_NAME_RAW(n1,n2)\r
  54 #define ENCODE_SEQUENCE_NAME COMBINED_NAME(FUNCTION_NAME,_encodeSequence)\r
  55 #ifdef LIMITED_OUTPUT\r
  56 #  define ENCODE_SEQUENCE(i,o,a,m,r,d) if (ENCODE_SEQUENCE_NAME(i,o,a,m,r,d)) return 0;\r
  57 #else\r
  58 #  define ENCODE_SEQUENCE(i,o,a,m,r,d) ENCODE_SEQUENCE_NAME(i,o,a,m,r)\r
  59 #endif\r
  60 \r
  61 //****************************\r
  62 // Function code\r
  63 //****************************\r
  64 \r
  65 forceinline static int ENCODE_SEQUENCE_NAME (\r
  66                        const BYTE** ip, \r
  67                        BYTE** op, \r
  68                        const BYTE** anchor, \r
  69                        int matchLength, \r
  70                        const BYTE* ref\r
  71 #ifdef LIMITED_OUTPUT\r
  72                       ,BYTE* oend\r
  73 #endif\r
  74                        )\r
  75 {\r
  76     int length, len; \r
  77     BYTE* token;\r
  78 \r
  79     // Encode Literal length\r
  80     length = (int)(*ip - *anchor);\r
  81     token = (*op)++;\r
  82 #ifdef LIMITED_OUTPUT\r
  83     if ((*op + length + (2 + 1 + LASTLITERALS) + (length>>8)) > oend) return 1;                 // Check output limit\r
  84 #endif\r
  85     if (length>=(int)RUN_MASK) { *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *(*op)++ = 255;  *(*op)++ = (BYTE)len; } \r
  86     else *token = (BYTE)(length<<ML_BITS);\r
  87 \r
  88     // Copy Literals\r
  89     LZ4_BLINDCOPY(*anchor, *op, length);\r
  90 \r
  91     // Encode Offset\r
  92     LZ4_WRITE_LITTLEENDIAN_16(*op,(U16)(*ip-ref));\r
  93 \r
  94     // Encode MatchLength\r
  95     length = (int)(matchLength-MINMATCH);\r
  96 #ifdef LIMITED_OUTPUT\r
  97     if (*op + (1 + LASTLITERALS) + (length>>8) > oend) return 1;                // Check output limit\r
  98 #endif\r
  99     if (length>=(int)ML_MASK) { *token+=ML_MASK; length-=ML_MASK; for(; length > 509 ; length-=510) { *(*op)++ = 255; *(*op)++ = 255; } if (length > 254) { length-=255; *(*op)++ = 255; } *(*op)++ = (BYTE)length; } \r
 100     else *token += (BYTE)(length);      \r
 101 \r
 102     // Prepare next loop\r
 103     *ip += matchLength;\r
 104     *anchor = *ip; \r
 105 \r
 106     return 0;\r
 107 }\r
 108 \r
 109 \r
 110 int COMBINED_NAME(FUNCTION_NAME,_continue) (\r
 111                  void* ctxvoid,\r
 112                  const char* source, \r
 113                  char* dest,\r
 114                  int inputSize\r
 115 #ifdef LIMITED_OUTPUT\r
 116                 ,int maxOutputSize\r
 117 #endif\r
 118                 )\r
 119 {\r
 120     LZ4HC_Data_Structure* ctx = (LZ4HC_Data_Structure*) ctxvoid;\r
 121     const BYTE* ip = (const BYTE*) source;\r
 122     const BYTE* anchor = ip;\r
 123     const BYTE* const iend = ip + inputSize;\r
 124     const BYTE* const mflimit = iend - MFLIMIT;\r
 125     const BYTE* const matchlimit = (iend - LASTLITERALS);\r
 126 \r
 127     BYTE* op = (BYTE*) dest;\r
 128 #ifdef LIMITED_OUTPUT\r
 129     BYTE* const oend = op + maxOutputSize;\r
 130 #endif\r
 131 \r
 132     int ml, ml2, ml3, ml0;\r
 133     const BYTE* ref=NULL;\r
 134     const BYTE* start2=NULL;\r
 135     const BYTE* ref2=NULL;\r
 136     const BYTE* start3=NULL;\r
 137     const BYTE* ref3=NULL;\r
 138     const BYTE* start0;\r
 139     const BYTE* ref0;\r
 140 \r
 141     // Ensure blocks follow each other\r
 142     if (ip != ctx->end) return 0;\r
 143     ctx->end += inputSize;\r
 144 \r
 145     ip++;\r
 146 \r
 147     // Main Loop\r
 148     while (ip < mflimit)\r
 149     {\r
 150         ml = LZ4HC_InsertAndFindBestMatch (ctx, ip, matchlimit, (&ref));\r
 151         if (!ml) { ip++; continue; }\r
 152 \r
 153         // saved, in case we would skip too much\r
 154         start0 = ip;\r
 155         ref0 = ref;\r
 156         ml0 = ml;\r
 157 \r
 158 _Search2:\r
 159         if (ip+ml < mflimit)\r
 160             ml2 = LZ4HC_InsertAndGetWiderMatch(ctx, ip + ml - 2, ip + 1, matchlimit, ml, &ref2, &start2);\r
 161         else ml2 = ml;\r
 162 \r
 163         if (ml2 == ml)  // No better match\r
 164         {\r
 165             ENCODE_SEQUENCE(&ip, &op, &anchor, ml, ref, oend);\r
 166             continue;\r
 167         }\r
 168 \r
 169         if (start0 < ip)\r
 170         {\r
 171             if (start2 < ip + ml0)   // empirical\r
 172             {\r
 173                 ip = start0;\r
 174                 ref = ref0;\r
 175                 ml = ml0;\r
 176             }\r
 177         }\r
 178 \r
 179         // Here, start0==ip\r
 180         if ((start2 - ip) < 3)   // First Match too small : removed\r
 181         {\r
 182             ml = ml2;\r
 183             ip = start2;\r
 184             ref =ref2;\r
 185             goto _Search2;\r
 186         }\r
 187 \r
 188 _Search3:\r
 189         // Currently we have :\r
 190         // ml2 > ml1, and\r
 191         // ip1+3 <= ip2 (usually < ip1+ml1)\r
 192         if ((start2 - ip) < OPTIMAL_ML)\r
 193         {\r
 194             int correction;\r
 195             int new_ml = ml;\r
 196             if (new_ml > OPTIMAL_ML) new_ml = OPTIMAL_ML;\r
 197             if (ip+new_ml > start2 + ml2 - MINMATCH) new_ml = (int)(start2 - ip) + ml2 - MINMATCH;\r
 198             correction = new_ml - (int)(start2 - ip);\r
 199             if (correction > 0)\r
 200             {\r
 201                 start2 += correction;\r
 202                 ref2 += correction;\r
 203                 ml2 -= correction;\r
 204             }\r
 205         }\r
 206         // Now, we have start2 = ip+new_ml, with new_ml = min(ml, OPTIMAL_ML=18)\r
 207 \r
 208         if (start2 + ml2 < mflimit)\r
 209             ml3 = LZ4HC_InsertAndGetWiderMatch(ctx, start2 + ml2 - 3, start2, matchlimit, ml2, &ref3, &start3);\r
 210         else ml3 = ml2;\r
 211 \r
 212         if (ml3 == ml2) // No better match : 2 sequences to encode\r
 213         {\r
 214             // ip & ref are known; Now for ml\r
 215             if (start2 < ip+ml)  ml = (int)(start2 - ip);\r
 216             // Now, encode 2 sequences\r
 217             ENCODE_SEQUENCE(&ip, &op, &anchor, ml, ref, oend);\r
 218             ip = start2;\r
 219             ENCODE_SEQUENCE(&ip, &op, &anchor, ml2, ref2, oend);\r
 220             continue;\r
 221         }\r
 222 \r
 223         if (start3 < ip+ml+3) // Not enough space for match 2 : remove it\r
 224         {\r
 225             if (start3 >= (ip+ml)) // can write Seq1 immediately ==> Seq2 is removed, so Seq3 becomes Seq1\r
 226             {\r
 227                 if (start2 < ip+ml)\r
 228                 {\r
 229                     int correction = (int)(ip+ml - start2);\r
 230                     start2 += correction;\r
 231                     ref2 += correction;\r
 232                     ml2 -= correction;\r
 233                     if (ml2 < MINMATCH)\r
 234                     {\r
 235                         start2 = start3;\r
 236                         ref2 = ref3;\r
 237                         ml2 = ml3;\r
 238                     }\r
 239                 }\r
 240 \r
 241                 ENCODE_SEQUENCE(&ip, &op, &anchor, ml, ref, oend);\r
 242                 ip  = start3;\r
 243                 ref = ref3;\r
 244                 ml  = ml3;\r
 245 \r
 246                 start0 = start2;\r
 247                 ref0 = ref2;\r
 248                 ml0 = ml2;\r
 249                 goto _Search2;\r
 250             }\r
 251 \r
 252             start2 = start3;\r
 253             ref2 = ref3;\r
 254             ml2 = ml3;\r
 255             goto _Search3;\r
 256         }\r
 257 \r
 258         // OK, now we have 3 ascending matches; let's write at least the first one\r
 259         // ip & ref are known; Now for ml\r
 260         if (start2 < ip+ml)\r
 261         {\r
 262             if ((start2 - ip) < (int)ML_MASK)\r
 263             {\r
 264                 int correction;\r
 265                 if (ml > OPTIMAL_ML) ml = OPTIMAL_ML;\r
 266                 if (ip + ml > start2 + ml2 - MINMATCH) ml = (int)(start2 - ip) + ml2 - MINMATCH;\r
 267                 correction = ml - (int)(start2 - ip);\r
 268                 if (correction > 0)\r
 269                 {\r
 270                     start2 += correction;\r
 271                     ref2 += correction;\r
 272                     ml2 -= correction;\r
 273                 }\r
 274             }\r
 275             else\r
 276             {\r
 277                 ml = (int)(start2 - ip);\r
 278             }\r
 279         }\r
 280         ENCODE_SEQUENCE(&ip, &op, &anchor, ml, ref, oend);\r
 281 \r
 282         ip = start2;\r
 283         ref = ref2;\r
 284         ml = ml2;\r
 285 \r
 286         start2 = start3;\r
 287         ref2 = ref3;\r
 288         ml2 = ml3;\r
 289 \r
 290         goto _Search3;\r
 291 \r
 292     }\r
 293 \r
 294     // Encode Last Literals\r
 295     {\r
 296         int lastRun = (int)(iend - anchor);\r
 297 #ifdef LIMITED_OUTPUT\r
 298         if (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize) return 0;  // Check output limit\r
 299 #endif\r
 300         if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; } \r
 301         else *op++ = (BYTE)(lastRun<<ML_BITS);\r
 302         memcpy(op, anchor, iend - anchor);\r
 303         op += iend-anchor;\r
 304     } \r
 305 \r
 306     // End\r
 307     return (int) (((char*)op)-dest);\r
 308 }\r
 309 \r
 310 \r
 311 int FUNCTION_NAME (const char* source, \r
 312                  char* dest,\r
 313                  int inputSize\r
 314 #ifdef LIMITED_OUTPUT\r
 315                 ,int maxOutputSize\r
 316 #endif\r
 317                 )\r
 318 {\r
 319     void* ctx = LZ4_createHC(source);\r
 320     int result;\r
 321     if (ctx==NULL) return 0;\r
 322 #ifdef LIMITED_OUTPUT\r
 323     result = COMBINED_NAME(FUNCTION_NAME,_continue) (ctx, source, dest, inputSize, maxOutputSize);\r
 324 #else\r
 325     result = COMBINED_NAME(FUNCTION_NAME,_continue) (ctx, source, dest, inputSize);\r
 326 #endif\r
 327     LZ4_freeHC(ctx);\r
 328 \r
 329     return result;\r
 330 }\r
 331 \r
 332 \r
 333 //****************************\r
 334 // Clean defines\r
 335 //****************************\r
 336 \r
 337 // Required defines\r
 338 #undef FUNCTION_NAME\r
 339 \r
 340 // Locally Generated\r
 341 #undef ENCODE_SEQUENCE\r
 342 #undef ENCODE_SEQUENCE_NAME\r
 343 \r
 344 // Optional defines\r
 345 #ifdef LIMITED_OUTPUT\r
 346 #undef LIMITED_OUTPUT\r
 347 #endif\r
 348 \r
 349 \r