contrib/zstd/tests/decodecorpus.c

   1 /**
   2  * Copyright (c) 2017-present, Facebook, Inc.
   3  * All rights reserved.
   4  *
   5  * This source code is licensed under the BSD-style license found in the
   6  * LICENSE file in the root directory of this source tree. An additional grant
   7  * of patent rights can be found in the PATENTS file in the same directory.
   8  */
   9
  10 #include <limits.h>
  11 #include <math.h>
  12 #include <stddef.h>
  13 #include <stdio.h>
  14 #include <stdlib.h>
  15 #include <string.h>
  16 #include <time.h>
  17
  18 #include "zstd.h"
  19 #include "zstd_internal.h"
  20 #include "mem.h"
  21
  22 // Direct access to internal compression functions is required
  23 #include "zstd_compress.c"
  24
  25 #define XXH_STATIC_LINKING_ONLY
  26 #include "xxhash.h"     /* XXH64 */
  27
  28 #ifndef MIN
  29     #define MIN(a, b) ((a) < (b) ? (a) : (b))
  30 #endif
  31
  32 #ifndef MAX_PATH
  33     #ifdef PATH_MAX
  34         #define MAX_PATH PATH_MAX
  35     #else
  36         #define MAX_PATH 256
  37     #endif
  38 #endif
  39
  40 /*-************************************
  41 *  DISPLAY Macros
  42 **************************************/
  43 #define DISPLAY(...)          fprintf(stderr, __VA_ARGS__)
  44 #define DISPLAYLEVEL(l, ...)  if (g_displayLevel>=l) { DISPLAY(__VA_ARGS__); }
  45 static U32 g_displayLevel = 0;
  46
  47 #define DISPLAYUPDATE(...)                                                     \
  48     do {                                                                       \
  49         if ((clockSpan(g_displayClock) > g_refreshRate) ||                     \
  50             (g_displayLevel >= 4)) {                                           \
  51             g_displayClock = clock();                                          \
  52             DISPLAY(__VA_ARGS__);                                              \
  53             if (g_displayLevel >= 4) fflush(stderr);                           \
  54         }                                                                      \
  55     } while (0)
  56 static const clock_t g_refreshRate = CLOCKS_PER_SEC / 6;
  57 static clock_t g_displayClock = 0;
  58
  59 static clock_t clockSpan(clock_t cStart)
  60 {
  61     return clock() - cStart;   /* works even when overflow; max span ~ 30mn */
  62 }
  63
  64 #define CHECKERR(code)                                                         \
  65     do {                                                                       \
  66         if (ZSTD_isError(code)) {                                              \
  67             DISPLAY("Error occurred while generating data: %s\n",              \
  68                     ZSTD_getErrorName(code));                                  \
  69             exit(1);                                                           \
  70         }                                                                      \
  71     } while (0)
  72
  73 /*-*******************************************************
  74 *  Random function
  75 *********************************************************/
  76 #define CLAMP(x, a, b) ((x) < (a) ? (a) : ((x) > (b) ? (b) : (x)))
  77
  78 static unsigned RAND(unsigned* src)
  79 {
  80 #define RAND_rotl32(x,r) ((x << r) | (x >> (32 - r)))
  81     static const U32 prime1 = 2654435761U;
  82     static const U32 prime2 = 2246822519U;
  83     U32 rand32 = *src;
  84     rand32 *= prime1;
  85     rand32 += prime2;
  86     rand32  = RAND_rotl32(rand32, 13);
  87     *src = rand32;
  88     return RAND_rotl32(rand32, 27);
  89 #undef RAND_rotl32
  90 }
  91
  92 #define DISTSIZE (8192)
  93
  94 /* Write `size` bytes into `ptr`, all of which are less than or equal to `maxSymb` */
  95 static void RAND_bufferMaxSymb(U32* seed, void* ptr, size_t size, int maxSymb)
  96 {
  97     size_t i;
  98     BYTE* op = ptr;
  99
 100     for (i = 0; i < size; i++) {
 101         op[i] = (BYTE) (RAND(seed) % (maxSymb + 1));
 102     }
 103 }
 104
 105 /* Write `size` random bytes into `ptr` */
 106 static void RAND_buffer(U32* seed, void* ptr, size_t size)
 107 {
 108     size_t i;
 109     BYTE* op = ptr;
 110
 111     for (i = 0; i + 4 <= size; i += 4) {
 112         MEM_writeLE32(op + i, RAND(seed));
 113     }
 114     for (; i < size; i++) {
 115         op[i] = RAND(seed) & 0xff;
 116     }
 117 }
 118
 119 /* Write `size` bytes into `ptr` following the distribution `dist` */
 120 static void RAND_bufferDist(U32* seed, BYTE* dist, void* ptr, size_t size)
 121 {
 122     size_t i;
 123     BYTE* op = ptr;
 124
 125     for (i = 0; i < size; i++) {
 126         op[i] = dist[RAND(seed) % DISTSIZE];
 127     }
 128 }
 129
 130 /* Generate a random distribution where the frequency of each symbol follows a
 131  * geometric distribution defined by `weight`
 132  * `dist` should have size at least `DISTSIZE` */
 133 static void RAND_genDist(U32* seed, BYTE* dist, double weight)
 134 {
 135     size_t i = 0;
 136     size_t statesLeft = DISTSIZE;
 137     BYTE symb = (BYTE) (RAND(seed) % 256);
 138     BYTE step = (BYTE) ((RAND(seed) % 256) | 1); /* force it to be odd so it's relatively prime to 256 */
 139
 140     while (i < DISTSIZE) {
 141         size_t states = ((size_t)(weight * statesLeft)) + 1;
 142         size_t j;
 143         for (j = 0; j < states && i < DISTSIZE; j++, i++) {
 144             dist[i] = symb;
 145         }
 146
 147         symb += step;
 148         statesLeft -= states;
 149     }
 150 }
 151
 152 /* Generates a random number in the range [min, max) */
 153 static inline U32 RAND_range(U32* seed, U32 min, U32 max)
 154 {
 155     return (RAND(seed) % (max-min)) + min;
 156 }
 157
 158 #define ROUND(x) ((U32)(x + 0.5))
 159
 160 /* Generates a random number in an exponential distribution with mean `mean` */
 161 static double RAND_exp(U32* seed, double mean)
 162 {
 163     double const u = RAND(seed) / (double) UINT_MAX;
 164     return log(1-u) * (-mean);
 165 }
 166
 167 /*-*******************************************************
 168 *  Constants and Structs
 169 *********************************************************/
 170 const char *BLOCK_TYPES[] = {"raw", "rle", "compressed"};
 171
 172 #define MAX_DECOMPRESSED_SIZE_LOG 20
 173 #define MAX_DECOMPRESSED_SIZE (1ULL << MAX_DECOMPRESSED_SIZE_LOG)
 174
 175 #define MAX_WINDOW_LOG 22 /* Recommended support is 8MB, so limit to 4MB + mantissa */
 176 #define MAX_BLOCK_SIZE (128ULL * 1024)
 177
 178 #define MIN_SEQ_LEN (3)
 179 #define MAX_NB_SEQ ((MAX_BLOCK_SIZE + MIN_SEQ_LEN - 1) / MIN_SEQ_LEN)
 180
 181 BYTE CONTENT_BUFFER[MAX_DECOMPRESSED_SIZE];
 182 BYTE FRAME_BUFFER[MAX_DECOMPRESSED_SIZE * 2];
 183 BYTE LITERAL_BUFFER[MAX_BLOCK_SIZE];
 184
 185 seqDef SEQUENCE_BUFFER[MAX_NB_SEQ];
 186 BYTE SEQUENCE_LITERAL_BUFFER[MAX_BLOCK_SIZE]; /* storeSeq expects a place to copy literals to */
 187 BYTE SEQUENCE_LLCODE[MAX_BLOCK_SIZE];
 188 BYTE SEQUENCE_MLCODE[MAX_BLOCK_SIZE];
 189 BYTE SEQUENCE_OFCODE[MAX_BLOCK_SIZE];
 190
 191 unsigned WKSP[1024];
 192
 193 typedef struct {
 194     size_t contentSize; /* 0 means unknown (unless contentSize == windowSize == 0) */
 195     unsigned windowSize; /* contentSize >= windowSize means single segment */
 196 } frameHeader_t;
 197
 198 /* For repeat modes */
 199 typedef struct {
 200     U32 rep[ZSTD_REP_NUM];
 201
 202     int hufInit;
 203     /* the distribution used in the previous block for repeat mode */
 204     BYTE hufDist[DISTSIZE];
 205     U32 hufTable [256]; /* HUF_CElt is an incomplete type */
 206
 207     int fseInit;
 208     FSE_CTable offcodeCTable  [FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)];
 209     FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)];
 210     FSE_CTable litlengthCTable  [FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)];
 211
 212     /* Symbols that were present in the previous distribution, for use with
 213      * set_repeat */
 214     BYTE litlengthSymbolSet[36];
 215     BYTE offsetSymbolSet[29];
 216     BYTE matchlengthSymbolSet[53];
 217 } cblockStats_t;
 218
 219 typedef struct {
 220     void* data;
 221     void* dataStart;
 222     void* dataEnd;
 223
 224     void* src;
 225     void* srcStart;
 226     void* srcEnd;
 227
 228     frameHeader_t header;
 229
 230     cblockStats_t stats;
 231     cblockStats_t oldStats; /* so they can be rolled back if uncompressible */
 232 } frame_t;
 233
 234 /*-*******************************************************
 235 *  Generator Functions
 236 *********************************************************/
 237
 238 struct {
 239     int contentSize; /* force the content size to be present */
 240 } opts; /* advanced options on generation */
 241
 242 /* Generate and write a random frame header */
 243 static void writeFrameHeader(U32* seed, frame_t* frame)
 244 {
 245     BYTE* const op = frame->data;
 246     size_t pos = 0;
 247     frameHeader_t fh;
 248
 249     BYTE windowByte = 0;
 250
 251     int singleSegment = 0;
 252     int contentSizeFlag = 0;
 253     int fcsCode = 0;
 254
 255     memset(&fh, 0, sizeof(fh));
 256
 257     /* generate window size */
 258     {
 259         /* Follow window algorithm from specification */
 260         int const exponent = RAND(seed) % (MAX_WINDOW_LOG - 10);
 261         int const mantissa = RAND(seed) % 8;
 262         windowByte = (BYTE) ((exponent << 3) | mantissa);
 263         fh.windowSize = (1U << (exponent + 10));
 264         fh.windowSize += fh.windowSize / 8 * mantissa;
 265     }
 266
 267     {
 268         /* Generate random content size */
 269         size_t highBit;
 270         if (RAND(seed) & 7) {
 271             /* do content of at least 128 bytes */
 272             highBit = 1ULL << RAND_range(seed, 7, MAX_DECOMPRESSED_SIZE_LOG);
 273         } else if (RAND(seed) & 3) {
 274             /* do small content */
 275             highBit = 1ULL << RAND_range(seed, 0, 7);
 276         } else {
 277             /* 0 size frame */
 278             highBit = 0;
 279         }
 280         fh.contentSize = highBit ? highBit + (RAND(seed) % highBit) : 0;
 281
 282         /* provide size sometimes */
 283         contentSizeFlag = opts.contentSize | (RAND(seed) & 1);
 284
 285         if (contentSizeFlag && (fh.contentSize == 0 || !(RAND(seed) & 7))) {
 286             /* do single segment sometimes */
 287             fh.windowSize = (U32) fh.contentSize;
 288             singleSegment = 1;
 289         }
 290     }
 291
 292     if (contentSizeFlag) {
 293         /* Determine how large fcs field has to be */
 294         int minFcsCode = (fh.contentSize >= 256) +
 295                                (fh.contentSize >= 65536 + 256) +
 296                                (fh.contentSize > 0xFFFFFFFFU);
 297         if (!singleSegment && !minFcsCode) {
 298             minFcsCode = 1;
 299         }
 300         fcsCode = minFcsCode + (RAND(seed) % (4 - minFcsCode));
 301         if (fcsCode == 1 && fh.contentSize < 256) fcsCode++;
 302     }
 303
 304     /* write out the header */
 305     MEM_writeLE32(op + pos, ZSTD_MAGICNUMBER);
 306     pos += 4;
 307
 308     {
 309         BYTE const frameHeaderDescriptor =
 310                 (BYTE) ((fcsCode << 6) | (singleSegment << 5) | (1 << 2));
 311         op[pos++] = frameHeaderDescriptor;
 312     }
 313
 314     if (!singleSegment) {
 315         op[pos++] = windowByte;
 316     }
 317
 318     if (contentSizeFlag) {
 319         switch (fcsCode) {
 320         default: /* Impossible */
 321         case 0: op[pos++] = (BYTE) fh.contentSize; break;
 322         case 1: MEM_writeLE16(op + pos, (U16) (fh.contentSize - 256)); pos += 2; break;
 323         case 2: MEM_writeLE32(op + pos, (U32) fh.contentSize); pos += 4; break;
 324         case 3: MEM_writeLE64(op + pos, (U64) fh.contentSize); pos += 8; break;
 325         }
 326     }
 327
 328     DISPLAYLEVEL(2, " frame content size:\t%u\n", (U32)fh.contentSize);
 329     DISPLAYLEVEL(2, " frame window size:\t%u\n", fh.windowSize);
 330     DISPLAYLEVEL(2, " content size flag:\t%d\n", contentSizeFlag);
 331     DISPLAYLEVEL(2, " single segment flag:\t%d\n", singleSegment);
 332
 333     frame->data = op + pos;
 334     frame->header = fh;
 335 }
 336
 337 /* Write a literal block in either raw or RLE form, return the literals size */
 338 static size_t writeLiteralsBlockSimple(U32* seed, frame_t* frame, size_t contentSize)
 339 {
 340     BYTE* op = (BYTE*)frame->data;
 341     int const type = RAND(seed) % 2;
 342     int const sizeFormatDesc = RAND(seed) % 8;
 343     size_t litSize;
 344     size_t maxLitSize = MIN(contentSize, MAX_BLOCK_SIZE);
 345
 346     if (sizeFormatDesc == 0) {
 347         /* Size_FormatDesc = ?0 */
 348         maxLitSize = MIN(maxLitSize, 31);
 349     } else if (sizeFormatDesc <= 4) {
 350         /* Size_FormatDesc = 01 */
 351         maxLitSize = MIN(maxLitSize, 4095);
 352     } else {
 353         /* Size_Format = 11 */
 354         maxLitSize = MIN(maxLitSize, 1048575);
 355     }
 356
 357     litSize = RAND(seed) % (maxLitSize + 1);
 358     if (frame->src == frame->srcStart && litSize == 0) {
 359         litSize = 1; /* no empty literals if there's nothing preceding this block */
 360     }
 361     if (litSize + 3 > contentSize) {
 362         litSize = contentSize; /* no matches shorter than 3 are allowed */
 363     }
 364     /* use smallest size format that fits */
 365     if (litSize < 32) {
 366         op[0] = (type | (0 << 2) | (litSize << 3)) & 0xff;
 367         op += 1;
 368     } else if (litSize < 4096) {
 369         op[0] = (type | (1 << 2) | (litSize << 4)) & 0xff;
 370         op[1] = (litSize >> 4) & 0xff;
 371         op += 2;
 372     } else {
 373         op[0] = (type | (3 << 2) | (litSize << 4)) & 0xff;
 374         op[1] = (litSize >> 4) & 0xff;
 375         op[2] = (litSize >> 12) & 0xff;
 376         op += 3;
 377     }
 378
 379     if (type == 0) {
 380         /* Raw literals */
 381         DISPLAYLEVEL(4, "   raw literals\n");
 382
 383         RAND_buffer(seed, LITERAL_BUFFER, litSize);
 384         memcpy(op, LITERAL_BUFFER, litSize);
 385         op += litSize;
 386     } else {
 387         /* RLE literals */
 388         BYTE const symb = (BYTE) (RAND(seed) % 256);
 389
 390         DISPLAYLEVEL(4, "   rle literals: 0x%02x\n", (U32)symb);
 391
 392         memset(LITERAL_BUFFER, symb, litSize);
 393         op[0] = symb;
 394         op++;
 395     }
 396
 397     frame->data = op;
 398
 399     return litSize;
 400 }
 401
 402 /* Generate a Huffman header for the given source */
 403 static size_t writeHufHeader(U32* seed, HUF_CElt* hufTable, void* dst, size_t dstSize,
 404                                  const void* src, size_t srcSize)
 405 {
 406     BYTE* const ostart = (BYTE*)dst;
 407     BYTE* op = ostart;
 408
 409     unsigned huffLog = 11;
 410     U32 maxSymbolValue = 255;
 411
 412     U32 count[HUF_SYMBOLVALUE_MAX+1];
 413
 414     /* Scan input and build symbol stats */
 415     {   size_t const largest = FSE_count_wksp (count, &maxSymbolValue, (const BYTE*)src, srcSize, WKSP);
 416         if (largest == srcSize) { *ostart = ((const BYTE*)src)[0]; return 0; }   /* single symbol, rle */
 417         if (largest <= (srcSize >> 7)+1) return 0;   /* Fast heuristic : not compressible enough */
 418     }
 419
 420     /* Build Huffman Tree */
 421     /* Max Huffman log is 11, min is highbit(maxSymbolValue)+1 */
 422     huffLog = RAND_range(seed, ZSTD_highbit32(maxSymbolValue)+1, huffLog+1);
 423     DISPLAYLEVEL(6, "     huffman log: %u\n", huffLog);
 424     {   size_t const maxBits = HUF_buildCTable_wksp (hufTable, count, maxSymbolValue, huffLog, WKSP, sizeof(WKSP));
 425         CHECKERR(maxBits);
 426         huffLog = (U32)maxBits;
 427     }
 428
 429     /* Write table description header */
 430     {   size_t const hSize = HUF_writeCTable (op, dstSize, hufTable, maxSymbolValue, huffLog);
 431         if (hSize + 12 >= srcSize) return 0;   /* not useful to try compression */
 432         op += hSize;
 433     }
 434
 435     return op - ostart;
 436 }
 437
 438 /* Write a Huffman coded literals block and return the litearls size */
 439 static size_t writeLiteralsBlockCompressed(U32* seed, frame_t* frame, size_t contentSize)
 440 {
 441     BYTE* origop = (BYTE*)frame->data;
 442     BYTE* opend = (BYTE*)frame->dataEnd;
 443     BYTE* op;
 444     BYTE* const ostart = origop;
 445     int const sizeFormat = RAND(seed) % 4;
 446     size_t litSize;
 447     size_t hufHeaderSize = 0;
 448     size_t compressedSize = 0;
 449     size_t maxLitSize = MIN(contentSize-3, MAX_BLOCK_SIZE);
 450
 451     symbolEncodingType_e hType;
 452
 453     if (contentSize < 64) {
 454         /* make sure we get reasonably-sized literals for compression */
 455         return ERROR(GENERIC);
 456     }
 457
 458     DISPLAYLEVEL(4, "   compressed literals\n");
 459
 460     switch (sizeFormat) {
 461     case 0: /* fall through, size is the same as case 1 */
 462     case 1:
 463         maxLitSize = MIN(maxLitSize, 1023);
 464         origop += 3;
 465         break;
 466     case 2:
 467         maxLitSize = MIN(maxLitSize, 16383);
 468         origop += 4;
 469         break;
 470     case 3:
 471         maxLitSize = MIN(maxLitSize, 262143);
 472         origop += 5;
 473         break;
 474     default:; /* impossible */
 475     }
 476
 477     do {
 478         op = origop;
 479         do {
 480             litSize = RAND(seed) % (maxLitSize + 1);
 481         } while (litSize < 32); /* avoid small literal sizes */
 482         if (litSize + 3 > contentSize) {
 483             litSize = contentSize; /* no matches shorter than 3 are allowed */
 484         }
 485
 486         /* most of the time generate a new distribution */
 487         if ((RAND(seed) & 3) || !frame->stats.hufInit) {
 488             do {
 489                 if (RAND(seed) & 3) {
 490                     /* add 10 to ensure some compressability */
 491                     double const weight = ((RAND(seed) % 90) + 10) / 100.0;
 492
 493                     DISPLAYLEVEL(5, "    distribution weight: %d%%\n",
 494                                  (int)(weight * 100));
 495
 496                     RAND_genDist(seed, frame->stats.hufDist, weight);
 497                 } else {
 498                     /* sometimes do restricted range literals to force
 499                      * non-huffman headers */
 500                     DISPLAYLEVEL(5, "    small range literals\n");
 501                     RAND_bufferMaxSymb(seed, frame->stats.hufDist, DISTSIZE,
 502                                        15);
 503                 }
 504                 RAND_bufferDist(seed, frame->stats.hufDist, LITERAL_BUFFER,
 505                                 litSize);
 506
 507                 /* generate the header from the distribution instead of the
 508                  * actual data to avoid bugs with symbols that were in the
 509                  * distribution but never showed up in the output */
 510                 hufHeaderSize = writeHufHeader(
 511                         seed, (HUF_CElt*)frame->stats.hufTable, op, opend - op,
 512                         frame->stats.hufDist, DISTSIZE);
 513                 CHECKERR(hufHeaderSize);
 514                 /* repeat until a valid header is written */
 515             } while (hufHeaderSize == 0);
 516             op += hufHeaderSize;
 517             hType = set_compressed;
 518
 519             frame->stats.hufInit = 1;
 520         } else {
 521             /* repeat the distribution/table from last time */
 522             DISPLAYLEVEL(5, "    huffman repeat stats\n");
 523             RAND_bufferDist(seed, frame->stats.hufDist, LITERAL_BUFFER,
 524                             litSize);
 525             hufHeaderSize = 0;
 526             hType = set_repeat;
 527         }
 528
 529         do {
 530             compressedSize =
 531                     sizeFormat == 0
 532                             ? HUF_compress1X_usingCTable(
 533                                       op, opend - op, LITERAL_BUFFER, litSize,
 534                                       (HUF_CElt*)frame->stats.hufTable)
 535                             : HUF_compress4X_usingCTable(
 536                                       op, opend - op, LITERAL_BUFFER, litSize,
 537                                       (HUF_CElt*)frame->stats.hufTable);
 538             CHECKERR(compressedSize);
 539             /* this only occurs when it could not compress or similar */
 540         } while (compressedSize <= 0);
 541
 542         op += compressedSize;
 543
 544         compressedSize += hufHeaderSize;
 545         DISPLAYLEVEL(5, "    regenerated size: %u\n", (U32)litSize);
 546         DISPLAYLEVEL(5, "    compressed size: %u\n", (U32)compressedSize);
 547         if (compressedSize >= litSize) {
 548             DISPLAYLEVEL(5, "     trying again\n");
 549             /* if we have to try again, reset the stats so we don't accidentally
 550              * try to repeat a distribution we just made */
 551             frame->stats = frame->oldStats;
 552         } else {
 553             break;
 554         }
 555     } while (1);
 556
 557     /* write header */
 558     switch (sizeFormat) {
 559     case 0: /* fall through, size is the same as case 1 */
 560     case 1: {
 561         U32 const header = hType | (sizeFormat << 2) | ((U32)litSize << 4) |
 562                            ((U32)compressedSize << 14);
 563         MEM_writeLE24(ostart, header);
 564         break;
 565     }
 566     case 2: {
 567         U32 const header = hType | (sizeFormat << 2) | ((U32)litSize << 4) |
 568                            ((U32)compressedSize << 18);
 569         MEM_writeLE32(ostart, header);
 570         break;
 571     }
 572     case 3: {
 573         U32 const header = hType | (sizeFormat << 2) | ((U32)litSize << 4) |
 574                            ((U32)compressedSize << 22);
 575         MEM_writeLE32(ostart, header);
 576         ostart[4] = (BYTE)(compressedSize >> 10);
 577         break;
 578     }
 579     default:; /* impossible */
 580     }
 581
 582     frame->data = op;
 583     return litSize;
 584 }
 585
 586 static size_t writeLiteralsBlock(U32* seed, frame_t* frame, size_t contentSize)
 587 {
 588     /* only do compressed for larger segments to avoid compressibility issues */
 589     if (RAND(seed) & 7 && contentSize >= 64) {
 590         return writeLiteralsBlockCompressed(seed, frame, contentSize);
 591     } else {
 592         return writeLiteralsBlockSimple(seed, frame, contentSize);
 593     }
 594 }
 595
 596 static inline void initSeqStore(seqStore_t *seqStore) {
 597     seqStore->sequencesStart = SEQUENCE_BUFFER;
 598     seqStore->litStart = SEQUENCE_LITERAL_BUFFER;
 599     seqStore->llCode = SEQUENCE_LLCODE;
 600     seqStore->mlCode = SEQUENCE_MLCODE;
 601     seqStore->ofCode = SEQUENCE_OFCODE;
 602
 603     ZSTD_resetSeqStore(seqStore);
 604 }
 605
 606 /* Randomly generate sequence commands */
 607 static U32 generateSequences(U32* seed, frame_t* frame, seqStore_t* seqStore,
 608                                 size_t contentSize, size_t literalsSize)
 609 {
 610     /* The total length of all the matches */
 611     size_t const remainingMatch = contentSize - literalsSize;
 612     size_t excessMatch = 0;
 613     U32 numSequences = 0;
 614
 615     U32 i;
 616
 617
 618     const BYTE* literals = LITERAL_BUFFER;
 619     BYTE* srcPtr = frame->src;
 620
 621     if (literalsSize != contentSize) {
 622         /* each match must be at least MIN_SEQ_LEN, so this is the maximum
 623          * number of sequences we can have */
 624         U32 const maxSequences = (U32)remainingMatch / MIN_SEQ_LEN;
 625         numSequences = (RAND(seed) % maxSequences) + 1;
 626
 627         /* the extra match lengths we have to allocate to each sequence */
 628         excessMatch = remainingMatch - numSequences * MIN_SEQ_LEN;
 629     }
 630
 631     DISPLAYLEVEL(5, "    total match lengths: %u\n", (U32)remainingMatch);
 632
 633     for (i = 0; i < numSequences; i++) {
 634         /* Generate match and literal lengths by exponential distribution to
 635          * ensure nice numbers */
 636         U32 matchLen =
 637                 MIN_SEQ_LEN +
 638                 ROUND(RAND_exp(seed, excessMatch / (double)(numSequences - i)));
 639         U32 literalLen =
 640                 (RAND(seed) & 7)
 641                         ? ROUND(RAND_exp(seed,
 642                                          literalsSize /
 643                                                  (double)(numSequences - i)))
 644                         : 0;
 645         /* actual offset, code to send, and point to copy up to when shifting
 646          * codes in the repeat offsets history */
 647         U32 offset, offsetCode, repIndex;
 648
 649         /* bounds checks */
 650         matchLen = (U32) MIN(matchLen, excessMatch + MIN_SEQ_LEN);
 651         literalLen = MIN(literalLen, (U32) literalsSize);
 652         if (i == 0 && srcPtr == frame->srcStart && literalLen == 0) literalLen = 1;
 653         if (i + 1 == numSequences) matchLen = MIN_SEQ_LEN + (U32) excessMatch;
 654
 655         memcpy(srcPtr, literals, literalLen);
 656         srcPtr += literalLen;
 657
 658         do {
 659             if (RAND(seed) & 7) {
 660                 /* do a normal offset */
 661                 offset = (RAND(seed) %
 662                           MIN(frame->header.windowSize,
 663                               (size_t)((BYTE*)srcPtr - (BYTE*)frame->srcStart))) +
 664                          1;
 665                 offsetCode = offset + ZSTD_REP_MOVE;
 666                 repIndex = 2;
 667             } else {
 668                 /* do a repeat offset */
 669                 offsetCode = RAND(seed) % 3;
 670                 if (literalLen > 0) {
 671                     offset = frame->stats.rep[offsetCode];
 672                     repIndex = offsetCode;
 673                 } else {
 674                     /* special case */
 675                     offset = offsetCode == 2 ? frame->stats.rep[0] - 1
 676                                            : frame->stats.rep[offsetCode + 1];
 677                     repIndex = MIN(2, offsetCode + 1);
 678                 }
 679             }
 680         } while (offset > (size_t)((BYTE*)srcPtr - (BYTE*)frame->srcStart) || offset == 0);
 681
 682         {   size_t j;
 683             for (j = 0; j < matchLen; j++) {
 684                 *srcPtr = *(srcPtr-offset);
 685                 srcPtr++;
 686             }
 687         }
 688
 689         {   int r;
 690             for (r = repIndex; r > 0; r--) {
 691                 frame->stats.rep[r] = frame->stats.rep[r - 1];
 692             }
 693             frame->stats.rep[0] = offset;
 694         }
 695
 696         DISPLAYLEVEL(6, "      LL: %5u OF: %5u ML: %5u", literalLen, offset, matchLen);
 697         DISPLAYLEVEL(7, " srcPos: %8u seqNb: %3u",
 698                      (U32)((BYTE*)srcPtr - (BYTE*)frame->srcStart), i);
 699         DISPLAYLEVEL(6, "\n");
 700         if (offsetCode < 3) {
 701             DISPLAYLEVEL(7, "        repeat offset: %d\n", repIndex);
 702         }
 703         /* use libzstd sequence handling */
 704         ZSTD_storeSeq(seqStore, literalLen, literals, offsetCode,
 705                       matchLen - MINMATCH);
 706
 707         literalsSize -= literalLen;
 708         excessMatch -= (matchLen - MIN_SEQ_LEN);
 709         literals += literalLen;
 710     }
 711
 712     memcpy(srcPtr, literals, literalsSize);
 713     srcPtr += literalsSize;
 714     DISPLAYLEVEL(6, "      excess literals: %5u", (U32)literalsSize);
 715     DISPLAYLEVEL(7, " srcPos: %8u", (U32)((BYTE*)srcPtr - (BYTE*)frame->srcStart));
 716     DISPLAYLEVEL(6, "\n");
 717
 718     return numSequences;
 719 }
 720
 721 static void initSymbolSet(const BYTE* symbols, size_t len, BYTE* set, BYTE maxSymbolValue)
 722 {
 723     size_t i;
 724
 725     memset(set, 0, (size_t)maxSymbolValue+1);
 726
 727     for (i = 0; i < len; i++) {
 728         set[symbols[i]] = 1;
 729     }
 730 }
 731
 732 static int isSymbolSubset(const BYTE* symbols, size_t len, const BYTE* set, BYTE maxSymbolValue)
 733 {
 734     size_t i;
 735
 736     for (i = 0; i < len; i++) {
 737         if (symbols[i] > maxSymbolValue || !set[symbols[i]]) {
 738             return 0;
 739         }
 740     }
 741     return 1;
 742 }
 743
 744 static size_t writeSequences(U32* seed, frame_t* frame, seqStore_t* seqStorePtr,
 745                              size_t nbSeq)
 746 {
 747     /* This code is mostly copied from ZSTD_compressSequences in zstd_compress.c */
 748     U32 count[MaxSeq+1];
 749     S16 norm[MaxSeq+1];
 750     FSE_CTable* CTable_LitLength = frame->stats.litlengthCTable;
 751     FSE_CTable* CTable_OffsetBits = frame->stats.offcodeCTable;
 752     FSE_CTable* CTable_MatchLength = frame->stats.matchlengthCTable;
 753     U32 LLtype, Offtype, MLtype;   /* compressed, raw or rle */
 754     const seqDef* const sequences = seqStorePtr->sequencesStart;
 755     const BYTE* const ofCodeTable = seqStorePtr->ofCode;
 756     const BYTE* const llCodeTable = seqStorePtr->llCode;
 757     const BYTE* const mlCodeTable = seqStorePtr->mlCode;
 758     BYTE* const oend = (BYTE*)frame->dataEnd;
 759     BYTE* op = (BYTE*)frame->data;
 760     BYTE* seqHead;
 761     BYTE scratchBuffer[1<<MAX(MLFSELog,LLFSELog)];
 762
 763     /* literals compressing block removed so that can be done separately */
 764
 765     /* Sequences Header */
 766     if ((oend-op) < 3 /*max nbSeq Size*/ + 1 /*seqHead */) return ERROR(dstSize_tooSmall);
 767     if (nbSeq < 0x7F) *op++ = (BYTE)nbSeq;
 768     else if (nbSeq < LONGNBSEQ) op[0] = (BYTE)((nbSeq>>8) + 0x80), op[1] = (BYTE)nbSeq, op+=2;
 769     else op[0]=0xFF, MEM_writeLE16(op+1, (U16)(nbSeq - LONGNBSEQ)), op+=3;
 770
 771     /* seqHead : flags for FSE encoding type */
 772     seqHead = op++;
 773
 774     if (nbSeq==0) {
 775         frame->data = op;
 776
 777         return 0;
 778     }
 779
 780     /* convert length/distances into codes */
 781     ZSTD_seqToCodes(seqStorePtr);
 782
 783     /* CTable for Literal Lengths */
 784     {   U32 max = MaxLL;
 785         size_t const mostFrequent = FSE_countFast_wksp(count, &max, llCodeTable, nbSeq, WKSP);
 786         if (mostFrequent == nbSeq) {
 787             /* do RLE if we have the chance */
 788             *op++ = llCodeTable[0];
 789             FSE_buildCTable_rle(CTable_LitLength, (BYTE)max);
 790             LLtype = set_rle;
 791         } else if (frame->stats.fseInit && !(RAND(seed) & 3) &&
 792                    isSymbolSubset(llCodeTable, nbSeq,
 793                                   frame->stats.litlengthSymbolSet, 35)) {
 794             /* maybe do repeat mode if we're allowed to */
 795             LLtype = set_repeat;
 796         } else if (!(RAND(seed) & 3)) {
 797             /* maybe use the default distribution */
 798             FSE_buildCTable_wksp(CTable_LitLength, LL_defaultNorm, MaxLL, LL_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
 799             LLtype = set_basic;
 800         } else {
 801             /* fall back on a full table */
 802             size_t nbSeq_1 = nbSeq;
 803             const U32 tableLog = FSE_optimalTableLog(LLFSELog, nbSeq, max);
 804             if (count[llCodeTable[nbSeq-1]]>1) { count[llCodeTable[nbSeq-1]]--; nbSeq_1--; }
 805             FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
 806             { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog);   /* overflow protected */
 807               if (FSE_isError(NCountSize)) return ERROR(GENERIC);
 808               op += NCountSize; }
 809             FSE_buildCTable_wksp(CTable_LitLength, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
 810             LLtype = set_compressed;
 811     }   }
 812
 813     /* CTable for Offsets */
 814     /* see Literal Lengths for descriptions of mode choices */
 815     {   U32 max = MaxOff;
 816         size_t const mostFrequent = FSE_countFast_wksp(count, &max, ofCodeTable, nbSeq, WKSP);
 817         if (mostFrequent == nbSeq) {
 818             *op++ = ofCodeTable[0];
 819             FSE_buildCTable_rle(CTable_OffsetBits, (BYTE)max);
 820             Offtype = set_rle;
 821         } else if (frame->stats.fseInit && !(RAND(seed) & 3) &&
 822                    isSymbolSubset(ofCodeTable, nbSeq,
 823                                   frame->stats.offsetSymbolSet, 28)) {
 824             Offtype = set_repeat;
 825         } else if (!(RAND(seed) & 3)) {
 826             FSE_buildCTable_wksp(CTable_OffsetBits, OF_defaultNorm, MaxOff, OF_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
 827             Offtype = set_basic;
 828         } else {
 829             size_t nbSeq_1 = nbSeq;
 830             const U32 tableLog = FSE_optimalTableLog(OffFSELog, nbSeq, max);
 831             if (count[ofCodeTable[nbSeq-1]]>1) { count[ofCodeTable[nbSeq-1]]--; nbSeq_1--; }
 832             FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
 833             { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog);   /* overflow protected */
 834               if (FSE_isError(NCountSize)) return ERROR(GENERIC);
 835               op += NCountSize; }
 836             FSE_buildCTable_wksp(CTable_OffsetBits, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
 837             Offtype = set_compressed;
 838     }   }
 839
 840     /* CTable for MatchLengths */
 841     /* see Literal Lengths for descriptions of mode choices */
 842     {   U32 max = MaxML;
 843         size_t const mostFrequent = FSE_countFast_wksp(count, &max, mlCodeTable, nbSeq, WKSP);
 844         if (mostFrequent == nbSeq) {
 845             *op++ = *mlCodeTable;
 846             FSE_buildCTable_rle(CTable_MatchLength, (BYTE)max);
 847             MLtype = set_rle;
 848         } else if (frame->stats.fseInit && !(RAND(seed) & 3) &&
 849                    isSymbolSubset(mlCodeTable, nbSeq,
 850                                   frame->stats.matchlengthSymbolSet, 52)) {
 851             MLtype = set_repeat;
 852         } else if (!(RAND(seed) & 3)) {
 853             /* sometimes do default distribution */
 854             FSE_buildCTable_wksp(CTable_MatchLength, ML_defaultNorm, MaxML, ML_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
 855             MLtype = set_basic;
 856         } else {
 857             /* fall back on table */
 858             size_t nbSeq_1 = nbSeq;
 859             const U32 tableLog = FSE_optimalTableLog(MLFSELog, nbSeq, max);
 860             if (count[mlCodeTable[nbSeq-1]]>1) { count[mlCodeTable[nbSeq-1]]--; nbSeq_1--; }
 861             FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
 862             { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog);   /* overflow protected */
 863               if (FSE_isError(NCountSize)) return ERROR(GENERIC);
 864               op += NCountSize; }
 865             FSE_buildCTable_wksp(CTable_MatchLength, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
 866             MLtype = set_compressed;
 867     }   }
 868     frame->stats.fseInit = 1;
 869     initSymbolSet(llCodeTable, nbSeq, frame->stats.litlengthSymbolSet, 35);
 870     initSymbolSet(ofCodeTable, nbSeq, frame->stats.offsetSymbolSet, 28);
 871     initSymbolSet(mlCodeTable, nbSeq, frame->stats.matchlengthSymbolSet, 52);
 872
 873     DISPLAYLEVEL(5, "    LL type: %d OF type: %d ML type: %d\n", LLtype, Offtype, MLtype);
 874
 875     *seqHead = (BYTE)((LLtype<<6) + (Offtype<<4) + (MLtype<<2));
 876
 877     /* Encoding Sequences */
 878     {   BIT_CStream_t blockStream;
 879         FSE_CState_t  stateMatchLength;
 880         FSE_CState_t  stateOffsetBits;
 881         FSE_CState_t  stateLitLength;
 882
 883         CHECK_E(BIT_initCStream(&blockStream, op, oend-op), dstSize_tooSmall); /* not enough space remaining */
 884
 885         /* first symbols */
 886         FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq-1]);
 887         FSE_initCState2(&stateOffsetBits,  CTable_OffsetBits,  ofCodeTable[nbSeq-1]);
 888         FSE_initCState2(&stateLitLength,   CTable_LitLength,   llCodeTable[nbSeq-1]);
 889         BIT_addBits(&blockStream, sequences[nbSeq-1].litLength, LL_bits[llCodeTable[nbSeq-1]]);
 890         if (MEM_32bits()) BIT_flushBits(&blockStream);
 891         BIT_addBits(&blockStream, sequences[nbSeq-1].matchLength, ML_bits[mlCodeTable[nbSeq-1]]);
 892         if (MEM_32bits()) BIT_flushBits(&blockStream);
 893         BIT_addBits(&blockStream, sequences[nbSeq-1].offset, ofCodeTable[nbSeq-1]);
 894         BIT_flushBits(&blockStream);
 895
 896         {   size_t n;
 897             for (n=nbSeq-2 ; n<nbSeq ; n--) {      /* intentional underflow */
 898                 BYTE const llCode = llCodeTable[n];
 899                 BYTE const ofCode = ofCodeTable[n];
 900                 BYTE const mlCode = mlCodeTable[n];
 901                 U32  const llBits = LL_bits[llCode];
 902                 U32  const ofBits = ofCode;                                     /* 32b*/  /* 64b*/
 903                 U32  const mlBits = ML_bits[mlCode];
 904                                                                                 /* (7)*/  /* (7)*/
 905                 FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode);       /* 15 */  /* 15 */
 906                 FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode);      /* 24 */  /* 24 */
 907                 if (MEM_32bits()) BIT_flushBits(&blockStream);                  /* (7)*/
 908                 FSE_encodeSymbol(&blockStream, &stateLitLength, llCode);        /* 16 */  /* 33 */
 909                 if (MEM_32bits() || (ofBits+mlBits+llBits >= 64-7-(LLFSELog+MLFSELog+OffFSELog)))
 910                     BIT_flushBits(&blockStream);                                /* (7)*/
 911                 BIT_addBits(&blockStream, sequences[n].litLength, llBits);
 912                 if (MEM_32bits() && ((llBits+mlBits)>24)) BIT_flushBits(&blockStream);
 913                 BIT_addBits(&blockStream, sequences[n].matchLength, mlBits);
 914                 if (MEM_32bits()) BIT_flushBits(&blockStream);                  /* (7)*/
 915                 BIT_addBits(&blockStream, sequences[n].offset, ofBits);         /* 31 */
 916                 BIT_flushBits(&blockStream);                                    /* (7)*/
 917         }   }
 918
 919         FSE_flushCState(&blockStream, &stateMatchLength);
 920         FSE_flushCState(&blockStream, &stateOffsetBits);
 921         FSE_flushCState(&blockStream, &stateLitLength);
 922
 923         {   size_t const streamSize = BIT_closeCStream(&blockStream);
 924             if (streamSize==0) return ERROR(dstSize_tooSmall);   /* not enough space */
 925             op += streamSize;
 926     }   }
 927
 928     frame->data = op;
 929
 930     return 0;
 931 }
 932
 933 static size_t writeSequencesBlock(U32* seed, frame_t* frame, size_t contentSize,
 934                                   size_t literalsSize)
 935 {
 936     seqStore_t seqStore;
 937     size_t numSequences;
 938
 939
 940     initSeqStore(&seqStore);
 941
 942     /* randomly generate sequences */
 943     numSequences = generateSequences(seed, frame, &seqStore, contentSize, literalsSize);
 944     /* write them out to the frame data */
 945     CHECKERR(writeSequences(seed, frame, &seqStore, numSequences));
 946
 947     return numSequences;
 948 }
 949
 950 static size_t writeCompressedBlock(U32* seed, frame_t* frame, size_t contentSize)
 951 {
 952     BYTE* const blockStart = (BYTE*)frame->data;
 953     size_t literalsSize;
 954     size_t nbSeq;
 955
 956     DISPLAYLEVEL(4, "  compressed block:\n");
 957
 958     literalsSize = writeLiteralsBlock(seed, frame, contentSize);
 959
 960     DISPLAYLEVEL(4, "   literals size: %u\n", (U32)literalsSize);
 961
 962     nbSeq = writeSequencesBlock(seed, frame, contentSize, literalsSize);
 963
 964     DISPLAYLEVEL(4, "   number of sequences: %u\n", (U32)nbSeq);
 965
 966     return (BYTE*)frame->data - blockStart;
 967 }
 968
 969 static void writeBlock(U32* seed, frame_t* frame, size_t contentSize,
 970                        int lastBlock)
 971 {
 972     int const blockTypeDesc = RAND(seed) % 8;
 973     size_t blockSize;
 974     int blockType;
 975
 976     BYTE *const header = (BYTE*)frame->data;
 977     BYTE *op = header + 3;
 978
 979     DISPLAYLEVEL(3, " block:\n");
 980     DISPLAYLEVEL(3, "  block content size: %u\n", (U32)contentSize);
 981     DISPLAYLEVEL(3, "  last block: %s\n", lastBlock ? "yes" : "no");
 982
 983     if (blockTypeDesc == 0) {
 984         /* Raw data frame */
 985
 986         RAND_buffer(seed, frame->src, contentSize);
 987         memcpy(op, frame->src, contentSize);
 988
 989         op += contentSize;
 990         blockType = 0;
 991         blockSize = contentSize;
 992     } else if (blockTypeDesc == 1) {
 993         /* RLE */
 994         BYTE const symbol = RAND(seed) & 0xff;
 995
 996         op[0] = symbol;
 997         memset(frame->src, symbol, contentSize);
 998
 999         op++;
1000         blockType = 1;
1001         blockSize = contentSize;
1002     } else {
1003         /* compressed, most common */
1004         size_t compressedSize;
1005         blockType = 2;
1006
1007         frame->oldStats = frame->stats;
1008
1009         frame->data = op;
1010         compressedSize = writeCompressedBlock(seed, frame, contentSize);
1011         if (compressedSize > contentSize) {
1012             blockType = 0;
1013             memcpy(op, frame->src, contentSize);
1014
1015             op += contentSize;
1016             blockSize = contentSize; /* fall back on raw block if data doesn't
1017                                         compress */
1018
1019             frame->stats = frame->oldStats; /* don't update the stats */
1020         } else {
1021             op += compressedSize;
1022             blockSize = compressedSize;
1023         }
1024     }
1025     frame->src = (BYTE*)frame->src + contentSize;
1026
1027     DISPLAYLEVEL(3, "  block type: %s\n", BLOCK_TYPES[blockType]);
1028     DISPLAYLEVEL(3, "  block size field: %u\n", (U32)blockSize);
1029
1030     header[0] = (BYTE) ((lastBlock | (blockType << 1) | (blockSize << 3)) & 0xff);
1031     MEM_writeLE16(header + 1, (U16) (blockSize >> 5));
1032
1033     frame->data = op;
1034 }
1035
1036 static void writeBlocks(U32* seed, frame_t* frame)
1037 {
1038     size_t contentLeft = frame->header.contentSize;
1039     size_t const maxBlockSize = MIN(MAX_BLOCK_SIZE, frame->header.windowSize);
1040     while (1) {
1041         /* 1 in 4 chance of ending frame */
1042         int const lastBlock = contentLeft > maxBlockSize ? 0 : !(RAND(seed) & 3);
1043         size_t blockContentSize;
1044         if (lastBlock) {
1045             blockContentSize = contentLeft;
1046         } else {
1047             if (contentLeft > 0 && (RAND(seed) & 7)) {
1048                 /* some variable size blocks */
1049                 blockContentSize = RAND(seed) % (MIN(maxBlockSize, contentLeft)+1);
1050             } else if (contentLeft > maxBlockSize && (RAND(seed) & 1)) {
1051                 /* some full size blocks */
1052                 blockContentSize = maxBlockSize;
1053             } else {
1054                 /* some empty blocks */
1055                 blockContentSize = 0;
1056             }
1057         }
1058
1059         writeBlock(seed, frame, blockContentSize, lastBlock);
1060
1061         contentLeft -= blockContentSize;
1062         if (lastBlock) break;
1063     }
1064 }
1065
1066 static void writeChecksum(frame_t* frame)
1067 {
1068     /* write checksum so implementations can verify their output */
1069     U64 digest = XXH64(frame->srcStart, (BYTE*)frame->src-(BYTE*)frame->srcStart, 0);
1070     DISPLAYLEVEL(2, "  checksum: %08x\n", (U32)digest);
1071     MEM_writeLE32(frame->data, (U32)digest);
1072     frame->data = (BYTE*)frame->data + 4;
1073 }
1074
1075 static void outputBuffer(const void* buf, size_t size, const char* const path)
1076 {
1077     /* write data out to file */
1078     const BYTE* ip = (const BYTE*)buf;
1079     FILE* out;
1080     if (path) {
1081         out = fopen(path, "wb");
1082     } else {
1083         out = stdout;
1084     }
1085     if (!out) {
1086         fprintf(stderr, "Failed to open file at %s: ", path);
1087         perror(NULL);
1088         exit(1);
1089     }
1090
1091     {
1092         size_t fsize = size;
1093         size_t written = 0;
1094         while (written < fsize) {
1095             written += fwrite(ip + written, 1, fsize - written, out);
1096             if (ferror(out)) {
1097                 fprintf(stderr, "Failed to write to file at %s: ", path);
1098                 perror(NULL);
1099                 exit(1);
1100             }
1101         }
1102     }
1103
1104     if (path) {
1105         fclose(out);
1106     }
1107 }
1108
1109 static void initFrame(frame_t* fr)
1110 {
1111     memset(fr, 0, sizeof(*fr));
1112     fr->data = fr->dataStart = FRAME_BUFFER;
1113     fr->dataEnd = FRAME_BUFFER + sizeof(FRAME_BUFFER);
1114     fr->src = fr->srcStart = CONTENT_BUFFER;
1115     fr->srcEnd = CONTENT_BUFFER + sizeof(CONTENT_BUFFER);
1116
1117     /* init repeat codes */
1118     fr->stats.rep[0] = 1;
1119     fr->stats.rep[1] = 4;
1120     fr->stats.rep[2] = 8;
1121 }
1122
1123 /* Return the final seed */
1124 static U32 generateFrame(U32 seed, frame_t* fr)
1125 {
1126     /* generate a complete frame */
1127     DISPLAYLEVEL(1, "frame seed: %u\n", seed);
1128
1129     initFrame(fr);
1130
1131     writeFrameHeader(&seed, fr);
1132     writeBlocks(&seed, fr);
1133     writeChecksum(fr);
1134
1135     return seed;
1136 }
1137
1138 /*-*******************************************************
1139 *  Test Mode
1140 *********************************************************/
1141
1142 BYTE DECOMPRESSED_BUFFER[MAX_DECOMPRESSED_SIZE];
1143
1144 static size_t testDecodeSimple(frame_t* fr)
1145 {
1146     /* test decoding the generated data with the simple API */
1147     size_t const ret = ZSTD_decompress(DECOMPRESSED_BUFFER, MAX_DECOMPRESSED_SIZE,
1148                            fr->dataStart, (BYTE*)fr->data - (BYTE*)fr->dataStart);
1149
1150     if (ZSTD_isError(ret)) return ret;
1151
1152     if (memcmp(DECOMPRESSED_BUFFER, fr->srcStart,
1153                (BYTE*)fr->src - (BYTE*)fr->srcStart) != 0) {
1154         return ERROR(corruption_detected);
1155     }
1156
1157     return ret;
1158 }
1159
1160 static size_t testDecodeStreaming(frame_t* fr)
1161 {
1162     /* test decoding the generated data with the streaming API */
1163     ZSTD_DStream* zd = ZSTD_createDStream();
1164     ZSTD_inBuffer in;
1165     ZSTD_outBuffer out;
1166     size_t ret;
1167
1168     if (!zd) return ERROR(memory_allocation);
1169
1170     in.src = fr->dataStart;
1171     in.pos = 0;
1172     in.size = (BYTE*)fr->data - (BYTE*)fr->dataStart;
1173
1174     out.dst = DECOMPRESSED_BUFFER;
1175     out.pos = 0;
1176     out.size = ZSTD_DStreamOutSize();
1177
1178     ZSTD_initDStream(zd);
1179     while (1) {
1180         ret = ZSTD_decompressStream(zd, &out, &in);
1181         if (ZSTD_isError(ret)) goto cleanup; /* error */
1182         if (ret == 0) break; /* frame is done */
1183
1184         /* force decoding to be done in chunks */
1185         out.size += MIN(ZSTD_DStreamOutSize(), MAX_DECOMPRESSED_SIZE - out.size);
1186     }
1187
1188     ret = out.pos;
1189
1190     if (memcmp(out.dst, fr->srcStart, out.pos) != 0) {
1191         return ERROR(corruption_detected);
1192     }
1193
1194 cleanup:
1195     ZSTD_freeDStream(zd);
1196     return ret;
1197 }
1198
1199 static int runTestMode(U32 seed, unsigned numFiles, unsigned const testDurationS)
1200 {
1201     unsigned fnum;
1202
1203     clock_t const startClock = clock();
1204     clock_t const maxClockSpan = testDurationS * CLOCKS_PER_SEC;
1205
1206     if (numFiles == 0 && !testDurationS) numFiles = 1;
1207
1208     DISPLAY("seed: %u\n", seed);
1209
1210     for (fnum = 0; fnum < numFiles || clockSpan(startClock) < maxClockSpan; fnum++) {
1211         frame_t fr;
1212
1213         if (fnum < numFiles)
1214             DISPLAYUPDATE("\r%u/%u        ", fnum, numFiles);
1215         else
1216             DISPLAYUPDATE("\r%u           ", fnum);
1217
1218         seed = generateFrame(seed, &fr);
1219
1220         {   size_t const r = testDecodeSimple(&fr);
1221             if (ZSTD_isError(r)) {
1222                 DISPLAY("Error in simple mode on test seed %u: %s\n", seed + fnum,
1223                         ZSTD_getErrorName(r));
1224                 return 1;
1225             }
1226         }
1227         {   size_t const r = testDecodeStreaming(&fr);
1228             if (ZSTD_isError(r)) {
1229                 DISPLAY("Error in streaming mode on test seed %u: %s\n", seed + fnum,
1230                         ZSTD_getErrorName(r));
1231                 return 1;
1232             }
1233         }
1234     }
1235
1236     DISPLAY("\r%u tests completed: ", fnum);
1237     DISPLAY("OK\n");
1238
1239     return 0;
1240 }
1241
1242 /*-*******************************************************
1243 *  File I/O
1244 *********************************************************/
1245
1246 static int generateFile(U32 seed, const char* const path,
1247                          const char* const origPath)
1248 {
1249     frame_t fr;
1250
1251     DISPLAY("seed: %u\n", seed);
1252
1253     generateFrame(seed, &fr);
1254
1255     outputBuffer(fr.dataStart, (BYTE*)fr.data - (BYTE*)fr.dataStart, path);
1256     if (origPath) {
1257         outputBuffer(fr.srcStart, (BYTE*)fr.src - (BYTE*)fr.srcStart, origPath);
1258     }
1259     return 0;
1260 }
1261
1262 static int generateCorpus(U32 seed, unsigned numFiles, const char* const path,
1263                          const char* const origPath)
1264 {
1265     char outPath[MAX_PATH];
1266     unsigned fnum;
1267
1268     DISPLAY("seed: %u\n", seed);
1269
1270     for (fnum = 0; fnum < numFiles; fnum++) {
1271         frame_t fr;
1272
1273         DISPLAYUPDATE("\r%u/%u        ", fnum, numFiles);
1274
1275         seed = generateFrame(seed, &fr);
1276
1277         if (snprintf(outPath, MAX_PATH, "%s/z%06u.zst", path, fnum) + 1 > MAX_PATH) {
1278             DISPLAY("Error: path too long\n");
1279             return 1;
1280         }
1281         outputBuffer(fr.dataStart, (BYTE*)fr.data - (BYTE*)fr.dataStart, outPath);
1282
1283         if (origPath) {
1284             if (snprintf(outPath, MAX_PATH, "%s/z%06u", origPath, fnum) + 1 > MAX_PATH) {
1285                 DISPLAY("Error: path too long\n");
1286                 return 1;
1287             }
1288             outputBuffer(fr.srcStart, (BYTE*)fr.src - (BYTE*)fr.srcStart, outPath);
1289         }
1290     }
1291
1292     DISPLAY("\r%u/%u      \n", fnum, numFiles);
1293
1294     return 0;
1295 }
1296
1297
1298 /*_*******************************************************
1299 *  Command line
1300 *********************************************************/
1301 static U32 makeSeed(void)
1302 {
1303     U32 t = (U32) time(NULL);
1304     return XXH32(&t, sizeof(t), 0) % 65536;
1305 }
1306
1307 static unsigned readInt(const char** argument)
1308 {
1309     unsigned val = 0;
1310     while ((**argument>='0') && (**argument<='9')) {
1311         val *= 10;
1312         val += **argument - '0';
1313         (*argument)++;
1314     }
1315     return val;
1316 }
1317
1318 static void usage(const char* programName)
1319 {
1320     DISPLAY( "Usage :\n");
1321     DISPLAY( "      %s [args]\n", programName);
1322     DISPLAY( "\n");
1323     DISPLAY( "Arguments :\n");
1324     DISPLAY( " -p<path> : select output path (default:stdout)\n");
1325     DISPLAY( "                in multiple files mode this should be a directory\n");
1326     DISPLAY( " -o<path> : select path to output original file (default:no output)\n");
1327     DISPLAY( "                in multiple files mode this should be a directory\n");
1328     DISPLAY( " -s#      : select seed (default:random based on time)\n");
1329     DISPLAY( " -n#      : number of files to generate (default:1)\n");
1330     DISPLAY( " -t       : activate test mode (test files against libzstd instead of outputting them)\n");
1331     DISPLAY( " -T#      : length of time to run tests for\n");
1332     DISPLAY( " -v       : increase verbosity level (default:0, max:7)\n");
1333     DISPLAY( " -h/H     : display help/long help and exit\n");
1334 }
1335
1336 static void advancedUsage(const char* programName)
1337 {
1338     usage(programName);
1339     DISPLAY( "\n");
1340     DISPLAY( "Advanced arguments :\n");
1341     DISPLAY( " --content-size    : always include the content size in the frame header\n");
1342 }
1343
1344 int main(int argc, char** argv)
1345 {
1346     U32 seed = 0;
1347     int seedset = 0;
1348     unsigned numFiles = 0;
1349     unsigned testDuration = 0;
1350     int testMode = 0;
1351     const char* path = NULL;
1352     const char* origPath = NULL;
1353
1354     int argNb;
1355
1356     /* Check command line */
1357     for (argNb=1; argNb<argc; argNb++) {
1358         const char* argument = argv[argNb];
1359         if(!argument) continue;   /* Protection if argument empty */
1360
1361         /* Handle commands. Aggregated commands are allowed */
1362         if (argument[0]=='-') {
1363             argument++;
1364             while (*argument!=0) {
1365                 switch(*argument)
1366                 {
1367                 case 'h':
1368                     usage(argv[0]);
1369                     return 0;
1370                 case 'H':
1371                     advancedUsage(argv[0]);
1372                     return 0;
1373                 case 'v':
1374                     argument++;
1375                     g_displayLevel++;
1376                     break;
1377                 case 's':
1378                     argument++;
1379                     seedset=1;
1380                     seed = readInt(&argument);
1381                     break;
1382                 case 'n':
1383                     argument++;
1384                     numFiles = readInt(&argument);
1385                     break;
1386                 case 'T':
1387                     argument++;
1388                     testDuration = readInt(&argument);
1389                     if (*argument == 'm') {
1390                         testDuration *= 60;
1391                         argument++;
1392                         if (*argument == 'n') argument++;
1393                     }
1394                     break;
1395                 case 'o':
1396                     argument++;
1397                     origPath = argument;
1398                     argument += strlen(argument);
1399                     break;
1400                 case 'p':
1401                     argument++;
1402                     path = argument;
1403                     argument += strlen(argument);
1404                     break;
1405                 case 't':
1406                     argument++;
1407                     testMode = 1;
1408                     break;
1409                 case '-':
1410                     argument++;
1411                     if (strcmp(argument, "content-size") == 0) {
1412                         opts.contentSize = 1;
1413                     } else {
1414                         advancedUsage(argv[0]);
1415                         return 1;
1416                     }
1417                     argument += strlen(argument);
1418                     break;
1419                 default:
1420                     usage(argv[0]);
1421                     return 1;
1422     }   }   }   }   /* for (argNb=1; argNb<argc; argNb++) */
1423
1424     if (!seedset) {
1425         seed = makeSeed();
1426     }
1427
1428     if (testMode) {
1429         return runTestMode(seed, numFiles, testDuration);
1430     } else {
1431         if (testDuration) {
1432             DISPLAY("Error: -T requires test mode (-t)\n\n");
1433             usage(argv[0]);
1434             return 1;
1435         }
1436     }
1437
1438     if (!path) {
1439         DISPLAY("Error: path is required in file generation mode\n");
1440         usage(argv[0]);
1441         return 1;
1442     }
1443
1444     if (numFiles == 0) {
1445         return generateFile(seed, path, origPath);
1446     } else {
1447         return generateCorpus(seed, numFiles, path, origPath);
1448     }
1449 }