deps/libchdr/deps/zstd-1.5.5/tests/decodecorpus.c

   1 /*
   2  * Copyright (c) Meta Platforms, Inc. and affiliates.
   3  * All rights reserved.
   4  *
   5  * This source code is licensed under both the BSD-style license (found in the
   6  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
   7  * in the COPYING file in the root directory of this source tree).
   8  * You may select, at your option, one of the above-listed licenses.
   9  */
  10
  11 #include <limits.h>
  12 #include <math.h>
  13 #include <stddef.h>
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <string.h>
  17 #include <time.h>  /* time(), for seed random initialization */
  18
  19 #include "util.h"
  20 #include "timefn.h"   /* UTIL_clockSpanMicro, SEC_TO_MICRO, UTIL_TIME_INITIALIZER */
  21 #include "zstd.h"
  22 #include "zstd_internal.h"
  23 #include "mem.h"
  24 #define ZDICT_STATIC_LINKING_ONLY
  25 #include "zdict.h"
  26
  27 /* Direct access to internal compression functions is required */
  28 #include "compress/zstd_compress.c" /* ZSTD_resetSeqStore, ZSTD_storeSeq, *_TO_OFFBASE, HIST_countFast_wksp, HIST_isError */
  29 #include "decompress/zstd_decompress_block.h" /* ZSTD_decompressBlock_deprecated */
  30
  31 #define XXH_STATIC_LINKING_ONLY
  32 #include "xxhash.h"     /* XXH64 */
  33
  34 #if !(defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */))
  35 # define inline  /* disable */
  36 #endif
  37
  38 /*-************************************
  39 *  DISPLAY Macros
  40 **************************************/
  41 #define DISPLAY(...)          fprintf(stderr, __VA_ARGS__)
  42 #define DISPLAYLEVEL(l, ...)  if (g_displayLevel>=l) { DISPLAY(__VA_ARGS__); }
  43 static U32 g_displayLevel = 2;
  44
  45 #define DISPLAYUPDATE(...)                                                     \
  46     do {                                                                       \
  47         if ((UTIL_clockSpanMicro(g_displayClock) > g_refreshRate) ||           \
  48             (g_displayLevel >= 4)) {                                           \
  49             g_displayClock = UTIL_getTime();                                   \
  50             DISPLAY(__VA_ARGS__);                                              \
  51             if (g_displayLevel >= 4) fflush(stderr);                           \
  52         }                                                                      \
  53     } while (0)
  54
  55 static const U64 g_refreshRate = SEC_TO_MICRO / 6;
  56 static UTIL_time_t g_displayClock = UTIL_TIME_INITIALIZER;
  57
  58 #define CHECKERR(code)                                                         \
  59     do {                                                                       \
  60         if (ZSTD_isError(code)) {                                              \
  61             DISPLAY("Error occurred while generating data: %s\n",              \
  62                     ZSTD_getErrorName(code));                                  \
  63             exit(1);                                                           \
  64         }                                                                      \
  65     } while (0)
  66
  67
  68 /*-*******************************************************
  69 *  Random function
  70 *********************************************************/
  71 static U32 RAND(U32* src)
  72 {
  73 #define RAND_rotl32(x,r) ((x << r) | (x >> (32 - r)))
  74     static const U32 prime1 = 2654435761U;
  75     static const U32 prime2 = 2246822519U;
  76     U32 rand32 = *src;
  77     rand32 *= prime1;
  78     rand32 += prime2;
  79     rand32  = RAND_rotl32(rand32, 13);
  80     *src = rand32;
  81     return RAND_rotl32(rand32, 27);
  82 #undef RAND_rotl32
  83 }
  84
  85 #define DISTSIZE (8192)
  86
  87 /* Write `size` bytes into `ptr`, all of which are less than or equal to `maxSymb` */
  88 static void RAND_bufferMaxSymb(U32* seed, void* ptr, size_t size, int maxSymb)
  89 {
  90     size_t i;
  91     BYTE* op = ptr;
  92
  93     for (i = 0; i < size; i++) {
  94         op[i] = (BYTE) (RAND(seed) % (maxSymb + 1));
  95     }
  96 }
  97
  98 /* Write `size` random bytes into `ptr` */
  99 static void RAND_buffer(U32* seed, void* ptr, size_t size)
 100 {
 101     size_t i;
 102     BYTE* op = ptr;
 103
 104     for (i = 0; i + 4 <= size; i += 4) {
 105         MEM_writeLE32(op + i, RAND(seed));
 106     }
 107     for (; i < size; i++) {
 108         op[i] = RAND(seed) & 0xff;
 109     }
 110 }
 111
 112 /* Write `size` bytes into `ptr` following the distribution `dist` */
 113 static void RAND_bufferDist(U32* seed, BYTE* dist, void* ptr, size_t size)
 114 {
 115     size_t i;
 116     BYTE* op = ptr;
 117
 118     for (i = 0; i < size; i++) {
 119         op[i] = dist[RAND(seed) % DISTSIZE];
 120     }
 121 }
 122
 123 /* Generate a random distribution where the frequency of each symbol follows a
 124  * geometric distribution defined by `weight`
 125  * `dist` should have size at least `DISTSIZE` */
 126 static void RAND_genDist(U32* seed, BYTE* dist, double weight)
 127 {
 128     size_t i = 0;
 129     size_t statesLeft = DISTSIZE;
 130     BYTE symb = (BYTE) (RAND(seed) % 256);
 131     BYTE step = (BYTE) ((RAND(seed) % 256) | 1); /* force it to be odd so it's relatively prime to 256 */
 132
 133     while (i < DISTSIZE) {
 134         size_t states = ((size_t)(weight * (double)statesLeft)) + 1;
 135         size_t j;
 136         for (j = 0; j < states && i < DISTSIZE; j++, i++) {
 137             dist[i] = symb;
 138         }
 139
 140         symb += step;
 141         statesLeft -= states;
 142     }
 143 }
 144
 145 /* Generates a random number in the range [min, max) */
 146 static inline U32 RAND_range(U32* seed, U32 min, U32 max)
 147 {
 148     return (RAND(seed) % (max-min)) + min;
 149 }
 150
 151 #define ROUND(x) ((U32)(x + 0.5))
 152
 153 /* Generates a random number in an exponential distribution with mean `mean` */
 154 static double RAND_exp(U32* seed, double mean)
 155 {
 156     double const u = RAND(seed) / (double) UINT_MAX;
 157     return log(1-u) * (-mean);
 158 }
 159
 160 /*-*******************************************************
 161 *  Constants and Structs
 162 *********************************************************/
 163 const char* BLOCK_TYPES[] = {"raw", "rle", "compressed"};
 164
 165 #define MAX_DECOMPRESSED_SIZE_LOG 20
 166 #define MAX_DECOMPRESSED_SIZE (1ULL << MAX_DECOMPRESSED_SIZE_LOG)
 167
 168 #define MAX_WINDOW_LOG 22 /* Recommended support is 8MB, so limit to 4MB + mantissa */
 169
 170 #define MIN_SEQ_LEN (3)
 171 #define MAX_NB_SEQ ((ZSTD_BLOCKSIZE_MAX + MIN_SEQ_LEN - 1) / MIN_SEQ_LEN)
 172
 173 #ifndef MAX_PATH
 174     #ifdef PATH_MAX
 175         #define MAX_PATH PATH_MAX
 176     #else
 177         #define MAX_PATH 256
 178     #endif
 179 #endif
 180
 181 BYTE CONTENT_BUFFER[MAX_DECOMPRESSED_SIZE];
 182 BYTE FRAME_BUFFER[MAX_DECOMPRESSED_SIZE * 2];
 183 BYTE LITERAL_BUFFER[ZSTD_BLOCKSIZE_MAX];
 184
 185 seqDef SEQUENCE_BUFFER[MAX_NB_SEQ];
 186 BYTE SEQUENCE_LITERAL_BUFFER[ZSTD_BLOCKSIZE_MAX]; /* storeSeq expects a place to copy literals to */
 187 BYTE SEQUENCE_LLCODE[ZSTD_BLOCKSIZE_MAX];
 188 BYTE SEQUENCE_MLCODE[ZSTD_BLOCKSIZE_MAX];
 189 BYTE SEQUENCE_OFCODE[ZSTD_BLOCKSIZE_MAX];
 190
 191 U64 WKSP[HUF_WORKSPACE_SIZE_U64];
 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     HUF_CElt hufTable [HUF_CTABLE_SIZE_ST(255)];
 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 typedef struct {
 235     int useDict;
 236     U32 dictID;
 237     size_t dictContentSize;
 238     BYTE* dictContent;
 239 } dictInfo;
 240
 241 typedef enum {
 242   gt_frame = 0,  /* generate frames */
 243   gt_block,      /* generate compressed blocks without block/frame headers */
 244 } genType_e;
 245
 246 #ifndef MIN
 247     #define MIN(a, b) ((a) < (b) ? (a) : (b))
 248 #endif
 249
 250 /*-*******************************************************
 251 *  Global variables (set from command line)
 252 *********************************************************/
 253 U32 g_maxDecompressedSizeLog = MAX_DECOMPRESSED_SIZE_LOG;  /* <= 20 */
 254 U32 g_maxBlockSize = ZSTD_BLOCKSIZE_MAX;                       /* <= 128 KB */
 255
 256 /*-*******************************************************
 257 *  Generator Functions
 258 *********************************************************/
 259
 260 struct {
 261     int contentSize; /* force the content size to be present */
 262 } opts; /* advanced options on generation */
 263
 264 /* Generate and write a random frame header */
 265 static void writeFrameHeader(U32* seed, frame_t* frame, dictInfo info)
 266 {
 267     BYTE* const op = frame->data;
 268     size_t pos = 0;
 269     frameHeader_t fh;
 270
 271     BYTE windowByte = 0;
 272
 273     int singleSegment = 0;
 274     int contentSizeFlag = 0;
 275     int fcsCode = 0;
 276
 277     memset(&fh, 0, sizeof(fh));
 278
 279     /* generate window size */
 280     {
 281         /* Follow window algorithm from specification */
 282         int const exponent = RAND(seed) % (MAX_WINDOW_LOG - 10);
 283         int const mantissa = RAND(seed) % 8;
 284         windowByte = (BYTE) ((exponent << 3) | mantissa);
 285         fh.windowSize = (1U << (exponent + 10));
 286         fh.windowSize += fh.windowSize / 8 * mantissa;
 287     }
 288
 289     {
 290         /* Generate random content size */
 291         size_t highBit;
 292         if (RAND(seed) & 7 && g_maxDecompressedSizeLog > 7) {
 293             /* do content of at least 128 bytes */
 294             highBit = 1ULL << RAND_range(seed, 7, g_maxDecompressedSizeLog);
 295         } else if (RAND(seed) & 3) {
 296             /* do small content */
 297             highBit = 1ULL << RAND_range(seed, 0, MIN(7, 1U << g_maxDecompressedSizeLog));
 298         } else {
 299             /* 0 size frame */
 300             highBit = 0;
 301         }
 302         fh.contentSize = highBit ? highBit + (RAND(seed) % highBit) : 0;
 303
 304         /* provide size sometimes */
 305         contentSizeFlag = opts.contentSize | (RAND(seed) & 1);
 306
 307         if (contentSizeFlag && (fh.contentSize == 0 || !(RAND(seed) & 7))) {
 308             /* do single segment sometimes */
 309             fh.windowSize = (U32) fh.contentSize;
 310             singleSegment = 1;
 311         }
 312     }
 313
 314     if (contentSizeFlag) {
 315         /* Determine how large fcs field has to be */
 316         int minFcsCode = (fh.contentSize >= 256) +
 317                                (fh.contentSize >= 65536 + 256) +
 318                                (fh.contentSize > 0xFFFFFFFFU);
 319         if (!singleSegment && !minFcsCode) {
 320             minFcsCode = 1;
 321         }
 322         fcsCode = minFcsCode + (RAND(seed) % (4 - minFcsCode));
 323         if (fcsCode == 1 && fh.contentSize < 256) fcsCode++;
 324     }
 325
 326     /* write out the header */
 327     MEM_writeLE32(op + pos, ZSTD_MAGICNUMBER);
 328     pos += 4;
 329
 330     {
 331         /*
 332          * fcsCode: 2-bit flag specifying how many bytes used to represent Frame_Content_Size (bits 7-6)
 333          * singleSegment: 1-bit flag describing if data must be regenerated within a single continuous memory segment. (bit 5)
 334          * contentChecksumFlag: 1-bit flag that is set if frame includes checksum at the end -- set to 1 below (bit 2)
 335          * dictBits: 2-bit flag describing how many bytes Dictionary_ID uses -- set to 3 (bits 1-0)
 336          * For more information: https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#frame_header
 337          */
 338         int const dictBits = info.useDict ? 3 : 0;
 339         BYTE const frameHeaderDescriptor =
 340                 (BYTE) ((fcsCode << 6) | (singleSegment << 5) | (1 << 2) | dictBits);
 341         op[pos++] = frameHeaderDescriptor;
 342     }
 343
 344     if (!singleSegment) {
 345         op[pos++] = windowByte;
 346     }
 347     if (info.useDict) {
 348         MEM_writeLE32(op + pos, (U32) info.dictID);
 349         pos += 4;
 350     }
 351     if (contentSizeFlag) {
 352         switch (fcsCode) {
 353         default: /* Impossible */
 354         case 0: op[pos++] = (BYTE) fh.contentSize; break;
 355         case 1: MEM_writeLE16(op + pos, (U16) (fh.contentSize - 256)); pos += 2; break;
 356         case 2: MEM_writeLE32(op + pos, (U32) fh.contentSize); pos += 4; break;
 357         case 3: MEM_writeLE64(op + pos, (U64) fh.contentSize); pos += 8; break;
 358         }
 359     }
 360
 361     DISPLAYLEVEL(3, " frame content size:\t%u\n", (unsigned)fh.contentSize);
 362     DISPLAYLEVEL(3, " frame window size:\t%u\n", fh.windowSize);
 363     DISPLAYLEVEL(3, " content size flag:\t%d\n", contentSizeFlag);
 364     DISPLAYLEVEL(3, " single segment flag:\t%d\n", singleSegment);
 365
 366     frame->data = op + pos;
 367     frame->header = fh;
 368 }
 369
 370 /* Write a literal block in either raw or RLE form, return the literals size */
 371 static size_t writeLiteralsBlockSimple(U32* seed, frame_t* frame, size_t contentSize)
 372 {
 373     BYTE* op = (BYTE*)frame->data;
 374     int const type = RAND(seed) % 2;
 375     int const sizeFormatDesc = RAND(seed) % 8;
 376     size_t litSize;
 377     size_t maxLitSize = MIN(contentSize, g_maxBlockSize);
 378
 379     if (sizeFormatDesc == 0) {
 380         /* Size_FormatDesc = ?0 */
 381         maxLitSize = MIN(maxLitSize, 31);
 382     } else if (sizeFormatDesc <= 4) {
 383         /* Size_FormatDesc = 01 */
 384         maxLitSize = MIN(maxLitSize, 4095);
 385     } else {
 386         /* Size_Format = 11 */
 387         maxLitSize = MIN(maxLitSize, 1048575);
 388     }
 389
 390     litSize = RAND(seed) % (maxLitSize + 1);
 391     if (frame->src == frame->srcStart && litSize == 0) {
 392         litSize = 1; /* no empty literals if there's nothing preceding this block */
 393     }
 394     if (litSize + 3 > contentSize) {
 395         litSize = contentSize; /* no matches shorter than 3 are allowed */
 396     }
 397     /* use smallest size format that fits */
 398     if (litSize < 32) {
 399         op[0] = (type | (0 << 2) | (litSize << 3)) & 0xff;
 400         op += 1;
 401     } else if (litSize < 4096) {
 402         op[0] = (type | (1 << 2) | (litSize << 4)) & 0xff;
 403         op[1] = (litSize >> 4) & 0xff;
 404         op += 2;
 405     } else {
 406         op[0] = (type | (3 << 2) | (litSize << 4)) & 0xff;
 407         op[1] = (litSize >> 4) & 0xff;
 408         op[2] = (litSize >> 12) & 0xff;
 409         op += 3;
 410     }
 411
 412     if (type == 0) {
 413         /* Raw literals */
 414         DISPLAYLEVEL(4, "   raw literals\n");
 415
 416         RAND_buffer(seed, LITERAL_BUFFER, litSize);
 417         memcpy(op, LITERAL_BUFFER, litSize);
 418         op += litSize;
 419     } else {
 420         /* RLE literals */
 421         BYTE const symb = (BYTE) (RAND(seed) % 256);
 422
 423         DISPLAYLEVEL(4, "   rle literals: 0x%02x\n", (unsigned)symb);
 424
 425         memset(LITERAL_BUFFER, symb, litSize);
 426         op[0] = symb;
 427         op++;
 428     }
 429
 430     frame->data = op;
 431
 432     return litSize;
 433 }
 434
 435 /* Generate a Huffman header for the given source */
 436 static size_t writeHufHeader(U32* seed, HUF_CElt* hufTable, void* dst, size_t dstSize,
 437                                  const void* src, size_t srcSize)
 438 {
 439     BYTE* const ostart = (BYTE*)dst;
 440     BYTE* op = ostart;
 441
 442     unsigned huffLog = 11;
 443     unsigned maxSymbolValue = 255;
 444
 445     unsigned count[HUF_SYMBOLVALUE_MAX+1];
 446
 447     /* Scan input and build symbol stats */
 448     {   size_t const largest = HIST_count_wksp (count, &maxSymbolValue, (const BYTE*)src, srcSize, WKSP, sizeof(WKSP));
 449         assert(!HIST_isError(largest));
 450         if (largest == srcSize) { *ostart = ((const BYTE*)src)[0]; return 0; }   /* single symbol, rle */
 451         if (largest <= (srcSize >> 7)+1) return 0;   /* Fast heuristic : not compressible enough */
 452     }
 453
 454     /* Build Huffman Tree */
 455     /* Max Huffman log is 11, min is highbit(maxSymbolValue)+1 */
 456     huffLog = RAND_range(seed, ZSTD_highbit32(maxSymbolValue)+1, huffLog+1);
 457     DISPLAYLEVEL(6, "     huffman log: %u\n", huffLog);
 458     {   size_t const maxBits = HUF_buildCTable_wksp (hufTable, count, maxSymbolValue, huffLog, WKSP, sizeof(WKSP));
 459         CHECKERR(maxBits);
 460         huffLog = (U32)maxBits;
 461     }
 462
 463     /* Write table description header */
 464     {   size_t const hSize = HUF_writeCTable_wksp (op, dstSize, hufTable, maxSymbolValue, huffLog, WKSP, sizeof(WKSP));
 465         if (hSize + 12 >= srcSize) return 0;   /* not useful to try compression */
 466         op += hSize;
 467     }
 468
 469     return op - ostart;
 470 }
 471
 472 /* Write a Huffman coded literals block and return the literals size */
 473 static size_t writeLiteralsBlockCompressed(U32* seed, frame_t* frame, size_t contentSize)
 474 {
 475     BYTE* origop = (BYTE*)frame->data;
 476     BYTE* opend = (BYTE*)frame->dataEnd;
 477     BYTE* op;
 478     BYTE* const ostart = origop;
 479     int const sizeFormat = RAND(seed) % 4;
 480     size_t litSize;
 481     size_t hufHeaderSize = 0;
 482     size_t compressedSize = 0;
 483     size_t maxLitSize = MIN(contentSize-3, g_maxBlockSize);
 484
 485     symbolEncodingType_e hType;
 486
 487     if (contentSize < 64) {
 488         /* make sure we get reasonably-sized literals for compression */
 489         return ERROR(GENERIC);
 490     }
 491
 492     DISPLAYLEVEL(4, "   compressed literals\n");
 493
 494     switch (sizeFormat) {
 495     case 0: /* fall through, size is the same as case 1 */
 496     case 1:
 497         maxLitSize = MIN(maxLitSize, 1023);
 498         origop += 3;
 499         break;
 500     case 2:
 501         maxLitSize = MIN(maxLitSize, 16383);
 502         origop += 4;
 503         break;
 504     case 3:
 505         maxLitSize = MIN(maxLitSize, 262143);
 506         origop += 5;
 507         break;
 508     default:; /* impossible */
 509     }
 510
 511     do {
 512         op = origop;
 513         do {
 514             litSize = RAND(seed) % (maxLitSize + 1);
 515         } while (litSize < 32); /* avoid small literal sizes */
 516         if (litSize + 3 > contentSize) {
 517             litSize = contentSize; /* no matches shorter than 3 are allowed */
 518         }
 519
 520         /* most of the time generate a new distribution */
 521         if ((RAND(seed) & 3) || !frame->stats.hufInit) {
 522             do {
 523                 if (RAND(seed) & 3) {
 524                     /* add 10 to ensure some compressibility */
 525                     double const weight = ((RAND(seed) % 90) + 10) / 100.0;
 526
 527                     DISPLAYLEVEL(5, "    distribution weight: %d%%\n",
 528                                  (int)(weight * 100));
 529
 530                     RAND_genDist(seed, frame->stats.hufDist, weight);
 531                 } else {
 532                     /* sometimes do restricted range literals to force
 533                      * non-huffman headers */
 534                     DISPLAYLEVEL(5, "    small range literals\n");
 535                     RAND_bufferMaxSymb(seed, frame->stats.hufDist, DISTSIZE,
 536                                        15);
 537                 }
 538                 RAND_bufferDist(seed, frame->stats.hufDist, LITERAL_BUFFER,
 539                                 litSize);
 540
 541                 /* generate the header from the distribution instead of the
 542                  * actual data to avoid bugs with symbols that were in the
 543                  * distribution but never showed up in the output */
 544                 hufHeaderSize = writeHufHeader(
 545                         seed, frame->stats.hufTable, op, opend - op,
 546                         frame->stats.hufDist, DISTSIZE);
 547                 CHECKERR(hufHeaderSize);
 548                 /* repeat until a valid header is written */
 549             } while (hufHeaderSize == 0);
 550             op += hufHeaderSize;
 551             hType = set_compressed;
 552
 553             frame->stats.hufInit = 1;
 554         } else {
 555             /* repeat the distribution/table from last time */
 556             DISPLAYLEVEL(5, "    huffman repeat stats\n");
 557             RAND_bufferDist(seed, frame->stats.hufDist, LITERAL_BUFFER,
 558                             litSize);
 559             hufHeaderSize = 0;
 560             hType = set_repeat;
 561         }
 562
 563         do {
 564             compressedSize =
 565                     sizeFormat == 0
 566                             ? HUF_compress1X_usingCTable(
 567                                       op, opend - op, LITERAL_BUFFER, litSize,
 568                                       frame->stats.hufTable, /* flags */ 0)
 569                             : HUF_compress4X_usingCTable(
 570                                       op, opend - op, LITERAL_BUFFER, litSize,
 571                                       frame->stats.hufTable, /* flags */ 0);
 572             CHECKERR(compressedSize);
 573             /* this only occurs when it could not compress or similar */
 574         } while (compressedSize <= 0);
 575
 576         op += compressedSize;
 577
 578         compressedSize += hufHeaderSize;
 579         DISPLAYLEVEL(5, "    regenerated size: %u\n", (unsigned)litSize);
 580         DISPLAYLEVEL(5, "    compressed size: %u\n", (unsigned)compressedSize);
 581         if (compressedSize >= litSize) {
 582             DISPLAYLEVEL(5, "     trying again\n");
 583             /* if we have to try again, reset the stats so we don't accidentally
 584              * try to repeat a distribution we just made */
 585             frame->stats = frame->oldStats;
 586         } else {
 587             break;
 588         }
 589     } while (1);
 590
 591     /* write header */
 592     switch (sizeFormat) {
 593     case 0: /* fall through, size is the same as case 1 */
 594     case 1: {
 595         U32 const header = hType | (sizeFormat << 2) | ((U32)litSize << 4) |
 596                            ((U32)compressedSize << 14);
 597         MEM_writeLE24(ostart, header);
 598         break;
 599     }
 600     case 2: {
 601         U32 const header = hType | (sizeFormat << 2) | ((U32)litSize << 4) |
 602                            ((U32)compressedSize << 18);
 603         MEM_writeLE32(ostart, header);
 604         break;
 605     }
 606     case 3: {
 607         U32 const header = hType | (sizeFormat << 2) | ((U32)litSize << 4) |
 608                            ((U32)compressedSize << 22);
 609         MEM_writeLE32(ostart, header);
 610         ostart[4] = (BYTE)(compressedSize >> 10);
 611         break;
 612     }
 613     default:; /* impossible */
 614     }
 615
 616     frame->data = op;
 617     return litSize;
 618 }
 619
 620 static size_t writeLiteralsBlock(U32* seed, frame_t* frame, size_t contentSize)
 621 {
 622     /* only do compressed for larger segments to avoid compressibility issues */
 623     if (RAND(seed) & 7 && contentSize >= 64) {
 624         return writeLiteralsBlockCompressed(seed, frame, contentSize);
 625     } else {
 626         return writeLiteralsBlockSimple(seed, frame, contentSize);
 627     }
 628 }
 629
 630 static inline void initSeqStore(seqStore_t *seqStore) {
 631     seqStore->maxNbSeq = MAX_NB_SEQ;
 632     seqStore->maxNbLit = ZSTD_BLOCKSIZE_MAX;
 633     seqStore->sequencesStart = SEQUENCE_BUFFER;
 634     seqStore->litStart = SEQUENCE_LITERAL_BUFFER;
 635     seqStore->llCode = SEQUENCE_LLCODE;
 636     seqStore->mlCode = SEQUENCE_MLCODE;
 637     seqStore->ofCode = SEQUENCE_OFCODE;
 638
 639     ZSTD_resetSeqStore(seqStore);
 640 }
 641
 642 /* Randomly generate sequence commands */
 643 static U32
 644 generateSequences(U32* seed, frame_t* frame, seqStore_t* seqStore,
 645                   size_t contentSize, size_t literalsSize, dictInfo info)
 646 {
 647     /* The total length of all the matches */
 648     size_t const remainingMatch = contentSize - literalsSize;
 649     size_t excessMatch = 0;
 650     U32 numSequences = 0;
 651     U32 i;
 652
 653     const BYTE* literals = LITERAL_BUFFER;
 654     BYTE* srcPtr = frame->src;
 655
 656     if (literalsSize != contentSize) {
 657         /* each match must be at least MIN_SEQ_LEN, so this is the maximum
 658          * number of sequences we can have */
 659         U32 const maxSequences = (U32)remainingMatch / MIN_SEQ_LEN;
 660         numSequences = (RAND(seed) % maxSequences) + 1;
 661
 662         /* the extra match lengths we have to allocate to each sequence */
 663         excessMatch = remainingMatch - numSequences * MIN_SEQ_LEN;
 664     }
 665
 666     DISPLAYLEVEL(5, "    total match lengths: %u\n", (unsigned)remainingMatch);
 667     for (i = 0; i < numSequences; i++) {
 668         /* Generate match and literal lengths by exponential distribution to
 669          * ensure nice numbers */
 670         U32 matchLen =
 671                 MIN_SEQ_LEN +
 672                 ROUND(RAND_exp(seed, (double)excessMatch / (double)(numSequences - i)));
 673         U32 literalLen =
 674                 (RAND(seed) & 7)
 675                         ? ROUND(RAND_exp(seed,
 676                                          (double)literalsSize /
 677                                                  (double)(numSequences - i)))
 678                         : 0;
 679         /* actual offset, code to send, and point to copy up to when shifting
 680          * codes in the repeat offsets history */
 681         U32 offset, offBase, repIndex;
 682
 683         /* bounds checks */
 684         matchLen = (U32) MIN(matchLen, excessMatch + MIN_SEQ_LEN);
 685         literalLen = MIN(literalLen, (U32) literalsSize);
 686         if (i == 0 && srcPtr == frame->srcStart && literalLen == 0) literalLen = 1;
 687         if (i + 1 == numSequences) matchLen = MIN_SEQ_LEN + (U32) excessMatch;
 688
 689         memcpy(srcPtr, literals, literalLen);
 690         srcPtr += literalLen;
 691         do {
 692             if (RAND(seed) & 7) {
 693                 /* do a normal offset */
 694                 U32 const dataDecompressed = (U32)((BYTE*)srcPtr-(BYTE*)frame->srcStart);
 695                 offset = (RAND(seed) %
 696                           MIN(frame->header.windowSize,
 697                               (size_t)((BYTE*)srcPtr - (BYTE*)frame->srcStart))) +
 698                          1;
 699                 if (info.useDict && (RAND(seed) & 1) && i + 1 != numSequences && dataDecompressed < frame->header.windowSize) {
 700                     /* need to occasionally generate offsets that go past the start */
 701                     /* including i+1 != numSequences because the last sequences has to adhere to predetermined contentSize */
 702                     U32 lenPastStart = (RAND(seed) % info.dictContentSize) + 1;
 703                     offset = (U32)((BYTE*)srcPtr - (BYTE*)frame->srcStart)+lenPastStart;
 704                     if (offset > frame->header.windowSize) {
 705                         if (lenPastStart < MIN_SEQ_LEN) {
 706                             /* when offset > windowSize, matchLen bound by end of dictionary (lenPastStart) */
 707                             /* this also means that lenPastStart must be greater than MIN_SEQ_LEN */
 708                             /* make sure lenPastStart does not go past dictionary start though */
 709                             lenPastStart = MIN(lenPastStart+MIN_SEQ_LEN, (U32)info.dictContentSize);
 710                             offset = (U32)((BYTE*)srcPtr - (BYTE*)frame->srcStart) + lenPastStart;
 711                         }
 712                         {   U32 const matchLenBound = MIN(frame->header.windowSize, lenPastStart);
 713                             matchLen = MIN(matchLen, matchLenBound);
 714                         }
 715                     }
 716                 }
 717                 offBase = OFFSET_TO_OFFBASE(offset);
 718                 repIndex = 2;
 719             } else {
 720                 /* do a repeat offset */
 721                 U32 const randomRepIndex = RAND(seed) % 3;
 722                 offBase = REPCODE_TO_OFFBASE(randomRepIndex + 1);  /* expects values between 1 & 3 */
 723                 if (literalLen > 0) {
 724                     offset = frame->stats.rep[randomRepIndex];
 725                     repIndex = randomRepIndex;
 726                 } else {
 727                     /* special case : literalLen == 0 */
 728                     offset = randomRepIndex == 2 ? frame->stats.rep[0] - 1
 729                                            : frame->stats.rep[randomRepIndex + 1];
 730                     repIndex = MIN(2, randomRepIndex + 1);
 731                 }
 732             }
 733         } while (((!info.useDict) && (offset > (size_t)((BYTE*)srcPtr - (BYTE*)frame->srcStart))) || offset == 0);
 734
 735         {   BYTE* const dictEnd = info.dictContent + info.dictContentSize;
 736             size_t j;
 737             for (j = 0; j < matchLen; j++) {
 738                 if ((U32)((BYTE*)srcPtr - (BYTE*)frame->srcStart) < offset) {
 739                     /* copy from dictionary instead of literals */
 740                     size_t const dictOffset = offset - (srcPtr - (BYTE*)frame->srcStart);
 741                     *srcPtr = *(dictEnd - dictOffset);
 742                 }
 743                 else {
 744                     *srcPtr = *(srcPtr-offset);
 745                 }
 746                 srcPtr++;
 747         }   }
 748
 749         {   int r;
 750             for (r = repIndex; r > 0; r--) {
 751                 frame->stats.rep[r] = frame->stats.rep[r - 1];
 752             }
 753             frame->stats.rep[0] = offset;
 754         }
 755
 756         DISPLAYLEVEL(6, "      LL: %5u OF: %5u ML: %5u",
 757                     (unsigned)literalLen, (unsigned)offset, (unsigned)matchLen);
 758         DISPLAYLEVEL(7, " srcPos: %8u seqNb: %3u",
 759                      (unsigned)((BYTE*)srcPtr - (BYTE*)frame->srcStart), (unsigned)i);
 760         DISPLAYLEVEL(6, "\n");
 761         if (OFFBASE_IS_REPCODE(offBase)) {  /* expects sumtype numeric representation of ZSTD_storeSeq() */
 762             DISPLAYLEVEL(7, "        repeat offset: %d\n", (int)repIndex);
 763         }
 764         /* use libzstd sequence handling */
 765         ZSTD_storeSeq(seqStore, literalLen, literals, literals + literalLen,
 766                       offBase, matchLen);
 767
 768         literalsSize -= literalLen;
 769         excessMatch -= (matchLen - MIN_SEQ_LEN);
 770         literals += literalLen;
 771     }
 772
 773     memcpy(srcPtr, literals, literalsSize);
 774     srcPtr += literalsSize;
 775     DISPLAYLEVEL(6, "      excess literals: %5u ", (unsigned)literalsSize);
 776     DISPLAYLEVEL(7, "srcPos: %8u ", (unsigned)((BYTE*)srcPtr - (BYTE*)frame->srcStart));
 777     DISPLAYLEVEL(6, "\n");
 778
 779     return numSequences;
 780 }
 781
 782 static void initSymbolSet(const BYTE* symbols, size_t len, BYTE* set, BYTE maxSymbolValue)
 783 {
 784     size_t i;
 785
 786     memset(set, 0, (size_t)maxSymbolValue+1);
 787
 788     for (i = 0; i < len; i++) {
 789         set[symbols[i]] = 1;
 790     }
 791 }
 792
 793 static int isSymbolSubset(const BYTE* symbols, size_t len, const BYTE* set, BYTE maxSymbolValue)
 794 {
 795     size_t i;
 796
 797     for (i = 0; i < len; i++) {
 798         if (symbols[i] > maxSymbolValue || !set[symbols[i]]) {
 799             return 0;
 800         }
 801     }
 802     return 1;
 803 }
 804
 805 static size_t writeSequences(U32* seed, frame_t* frame, seqStore_t* seqStorePtr,
 806                              size_t nbSeq)
 807 {
 808     /* This code is mostly copied from ZSTD_compressSequences in zstd_compress.c */
 809     unsigned count[MaxSeq+1];
 810     S16 norm[MaxSeq+1];
 811     FSE_CTable* CTable_LitLength = frame->stats.litlengthCTable;
 812     FSE_CTable* CTable_OffsetBits = frame->stats.offcodeCTable;
 813     FSE_CTable* CTable_MatchLength = frame->stats.matchlengthCTable;
 814     U32 LLtype, Offtype, MLtype;   /* compressed, raw or rle */
 815     const seqDef* const sequences = seqStorePtr->sequencesStart;
 816     const BYTE* const ofCodeTable = seqStorePtr->ofCode;
 817     const BYTE* const llCodeTable = seqStorePtr->llCode;
 818     const BYTE* const mlCodeTable = seqStorePtr->mlCode;
 819     BYTE* const oend = (BYTE*)frame->dataEnd;
 820     BYTE* op = (BYTE*)frame->data;
 821     BYTE* seqHead;
 822     BYTE scratchBuffer[FSE_BUILD_CTABLE_WORKSPACE_SIZE(MaxSeq, MaxFSELog)];
 823
 824     /* literals compressing block removed so that can be done separately */
 825
 826     /* Sequences Header */
 827     if ((oend-op) < 3 /*max nbSeq Size*/ + 1 /*seqHead */) return ERROR(dstSize_tooSmall);
 828     if (nbSeq < 0x7F) *op++ = (BYTE)nbSeq;
 829     else if (nbSeq < LONGNBSEQ) op[0] = (BYTE)((nbSeq>>8) + 0x80), op[1] = (BYTE)nbSeq, op+=2;
 830     else op[0]=0xFF, MEM_writeLE16(op+1, (U16)(nbSeq - LONGNBSEQ)), op+=3;
 831
 832     if (nbSeq==0) {
 833         frame->data = op;
 834         return 0;
 835     }
 836
 837     /* seqHead : flags for FSE encoding type */
 838     seqHead = op++;
 839
 840     /* convert length/distances into codes */
 841     ZSTD_seqToCodes(seqStorePtr);
 842
 843     /* CTable for Literal Lengths */
 844     {   unsigned max = MaxLL;
 845         size_t const mostFrequent = HIST_countFast_wksp(count, &max, llCodeTable, nbSeq, WKSP, sizeof(WKSP));   /* cannot fail */
 846         assert(!HIST_isError(mostFrequent));
 847         if (frame->stats.fseInit && !(RAND(seed) & 3) &&
 848                    isSymbolSubset(llCodeTable, nbSeq,
 849                                   frame->stats.litlengthSymbolSet, 35)) {
 850             /* maybe do repeat mode if we're allowed to */
 851             LLtype = set_repeat;
 852         } else if (mostFrequent == nbSeq) {
 853             /* do RLE if we have the chance */
 854             *op++ = llCodeTable[0];
 855             FSE_buildCTable_rle(CTable_LitLength, (BYTE)max);
 856             LLtype = set_rle;
 857         } else if (!(RAND(seed) & 3)) {
 858             /* maybe use the default distribution */
 859             CHECKERR(FSE_buildCTable_wksp(CTable_LitLength, LL_defaultNorm, MaxLL, LL_defaultNormLog, scratchBuffer, sizeof(scratchBuffer)));
 860             LLtype = set_basic;
 861         } else {
 862             /* fall back on a full table */
 863             size_t nbSeq_1 = nbSeq;
 864             const U32 tableLog = FSE_optimalTableLog(LLFSELog, nbSeq, max);
 865             if (count[llCodeTable[nbSeq-1]]>1) { count[llCodeTable[nbSeq-1]]--; nbSeq_1--; }
 866             FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max, nbSeq >= 2048);
 867             { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog);   /* overflow protected */
 868               if (FSE_isError(NCountSize)) return ERROR(GENERIC);
 869               op += NCountSize; }
 870             CHECKERR(FSE_buildCTable_wksp(CTable_LitLength, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer)));
 871             LLtype = set_compressed;
 872     }   }
 873
 874     /* CTable for Offsets */
 875     /* see Literal Lengths for descriptions of mode choices */
 876     {   unsigned max = MaxOff;
 877         size_t const mostFrequent = HIST_countFast_wksp(count, &max, ofCodeTable, nbSeq, WKSP, sizeof(WKSP));   /* cannot fail */
 878         assert(!HIST_isError(mostFrequent));
 879         if (frame->stats.fseInit && !(RAND(seed) & 3) &&
 880                    isSymbolSubset(ofCodeTable, nbSeq,
 881                                   frame->stats.offsetSymbolSet, 28)) {
 882             Offtype = set_repeat;
 883         } else if (mostFrequent == nbSeq) {
 884             *op++ = ofCodeTable[0];
 885             FSE_buildCTable_rle(CTable_OffsetBits, (BYTE)max);
 886             Offtype = set_rle;
 887         } else if (!(RAND(seed) & 3)) {
 888             FSE_buildCTable_wksp(CTable_OffsetBits, OF_defaultNorm, DefaultMaxOff, OF_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
 889             Offtype = set_basic;
 890         } else {
 891             size_t nbSeq_1 = nbSeq;
 892             const U32 tableLog = FSE_optimalTableLog(OffFSELog, nbSeq, max);
 893             if (count[ofCodeTable[nbSeq-1]]>1) { count[ofCodeTable[nbSeq-1]]--; nbSeq_1--; }
 894             FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max, nbSeq >= 2048);
 895             { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog);   /* overflow protected */
 896               if (FSE_isError(NCountSize)) return ERROR(GENERIC);
 897               op += NCountSize; }
 898             FSE_buildCTable_wksp(CTable_OffsetBits, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
 899             Offtype = set_compressed;
 900     }   }
 901
 902     /* CTable for MatchLengths */
 903     /* see Literal Lengths for descriptions of mode choices */
 904     {   unsigned max = MaxML;
 905         size_t const mostFrequent = HIST_countFast_wksp(count, &max, mlCodeTable, nbSeq, WKSP, sizeof(WKSP));   /* cannot fail */
 906         assert(!HIST_isError(mostFrequent));
 907         if (frame->stats.fseInit && !(RAND(seed) & 3) &&
 908                    isSymbolSubset(mlCodeTable, nbSeq,
 909                                   frame->stats.matchlengthSymbolSet, 52)) {
 910             MLtype = set_repeat;
 911         } else if (mostFrequent == nbSeq) {
 912             *op++ = *mlCodeTable;
 913             FSE_buildCTable_rle(CTable_MatchLength, (BYTE)max);
 914             MLtype = set_rle;
 915         } else if (!(RAND(seed) & 3)) {
 916             /* sometimes do default distribution */
 917             FSE_buildCTable_wksp(CTable_MatchLength, ML_defaultNorm, MaxML, ML_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
 918             MLtype = set_basic;
 919         } else {
 920             /* fall back on table */
 921             size_t nbSeq_1 = nbSeq;
 922             const U32 tableLog = FSE_optimalTableLog(MLFSELog, nbSeq, max);
 923             if (count[mlCodeTable[nbSeq-1]]>1) { count[mlCodeTable[nbSeq-1]]--; nbSeq_1--; }
 924             FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max, nbSeq >= 2048);
 925             { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog);   /* overflow protected */
 926               if (FSE_isError(NCountSize)) return ERROR(GENERIC);
 927               op += NCountSize; }
 928             FSE_buildCTable_wksp(CTable_MatchLength, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
 929             MLtype = set_compressed;
 930     }   }
 931     frame->stats.fseInit = 1;
 932     initSymbolSet(llCodeTable, nbSeq, frame->stats.litlengthSymbolSet, 35);
 933     initSymbolSet(ofCodeTable, nbSeq, frame->stats.offsetSymbolSet, 28);
 934     initSymbolSet(mlCodeTable, nbSeq, frame->stats.matchlengthSymbolSet, 52);
 935
 936     DISPLAYLEVEL(5, "    LL type: %d OF type: %d ML type: %d\n", (unsigned)LLtype, (unsigned)Offtype, (unsigned)MLtype);
 937
 938     *seqHead = (BYTE)((LLtype<<6) + (Offtype<<4) + (MLtype<<2));
 939
 940     /* Encoding Sequences */
 941     {   BIT_CStream_t blockStream;
 942         FSE_CState_t  stateMatchLength;
 943         FSE_CState_t  stateOffsetBits;
 944         FSE_CState_t  stateLitLength;
 945
 946         RETURN_ERROR_IF(
 947             ERR_isError(BIT_initCStream(&blockStream, op, oend-op)),
 948             dstSize_tooSmall, "not enough space remaining");
 949
 950         /* first symbols */
 951         FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq-1]);
 952         FSE_initCState2(&stateOffsetBits,  CTable_OffsetBits,  ofCodeTable[nbSeq-1]);
 953         FSE_initCState2(&stateLitLength,   CTable_LitLength,   llCodeTable[nbSeq-1]);
 954         BIT_addBits(&blockStream, sequences[nbSeq-1].litLength, LL_bits[llCodeTable[nbSeq-1]]);
 955         if (MEM_32bits()) BIT_flushBits(&blockStream);
 956         BIT_addBits(&blockStream, sequences[nbSeq-1].mlBase, ML_bits[mlCodeTable[nbSeq-1]]);
 957         if (MEM_32bits()) BIT_flushBits(&blockStream);
 958         BIT_addBits(&blockStream, sequences[nbSeq-1].offBase, ofCodeTable[nbSeq-1]);
 959         BIT_flushBits(&blockStream);
 960
 961         {   size_t n;
 962             for (n=nbSeq-2 ; n<nbSeq ; n--) {      /* intentional underflow */
 963                 BYTE const llCode = llCodeTable[n];
 964                 BYTE const ofCode = ofCodeTable[n];
 965                 BYTE const mlCode = mlCodeTable[n];
 966                 U32  const llBits = LL_bits[llCode];
 967                 U32  const ofBits = ofCode;                                     /* 32b*/  /* 64b*/
 968                 U32  const mlBits = ML_bits[mlCode];
 969                                                                                 /* (7)*/  /* (7)*/
 970                 FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode);       /* 15 */  /* 15 */
 971                 FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode);      /* 24 */  /* 24 */
 972                 if (MEM_32bits()) BIT_flushBits(&blockStream);                  /* (7)*/
 973                 FSE_encodeSymbol(&blockStream, &stateLitLength, llCode);        /* 16 */  /* 33 */
 974                 if (MEM_32bits() || (ofBits+mlBits+llBits >= 64-7-(LLFSELog+MLFSELog+OffFSELog)))
 975                     BIT_flushBits(&blockStream);                                /* (7)*/
 976                 BIT_addBits(&blockStream, sequences[n].litLength, llBits);
 977                 if (MEM_32bits() && ((llBits+mlBits)>24)) BIT_flushBits(&blockStream);
 978                 BIT_addBits(&blockStream, sequences[n].mlBase, mlBits);
 979                 if (MEM_32bits()) BIT_flushBits(&blockStream);                  /* (7)*/
 980                 BIT_addBits(&blockStream, sequences[n].offBase, ofBits);         /* 31 */
 981                 BIT_flushBits(&blockStream);                                    /* (7)*/
 982         }   }
 983
 984         FSE_flushCState(&blockStream, &stateMatchLength);
 985         FSE_flushCState(&blockStream, &stateOffsetBits);
 986         FSE_flushCState(&blockStream, &stateLitLength);
 987
 988         {   size_t const streamSize = BIT_closeCStream(&blockStream);
 989             if (streamSize==0) return ERROR(dstSize_tooSmall);   /* not enough space */
 990             op += streamSize;
 991     }   }
 992
 993     frame->data = op;
 994
 995     return 0;
 996 }
 997
 998 static size_t writeSequencesBlock(U32* seed, frame_t* frame, size_t contentSize,
 999                                   size_t literalsSize, dictInfo info)
1000 {
1001     seqStore_t seqStore;
1002     size_t numSequences;
1003
1004
1005     initSeqStore(&seqStore);
1006
1007     /* randomly generate sequences */
1008     numSequences = generateSequences(seed, frame, &seqStore, contentSize, literalsSize, info);
1009     /* write them out to the frame data */
1010     CHECKERR(writeSequences(seed, frame, &seqStore, numSequences));
1011
1012     return numSequences;
1013 }
1014
1015 static size_t writeCompressedBlock(U32* seed, frame_t* frame, size_t contentSize, dictInfo info)
1016 {
1017     BYTE* const blockStart = (BYTE*)frame->data;
1018     size_t literalsSize;
1019     size_t nbSeq;
1020
1021     DISPLAYLEVEL(4, "  compressed block:\n");
1022
1023     literalsSize = writeLiteralsBlock(seed, frame, contentSize);
1024
1025     DISPLAYLEVEL(4, "   literals size: %u\n", (unsigned)literalsSize);
1026
1027     nbSeq = writeSequencesBlock(seed, frame, contentSize, literalsSize, info);
1028
1029     DISPLAYLEVEL(4, "   number of sequences: %u\n", (unsigned)nbSeq);
1030
1031     return (BYTE*)frame->data - blockStart;
1032 }
1033
1034 static void writeBlock(U32* seed, frame_t* frame, size_t contentSize,
1035                        int lastBlock, dictInfo info)
1036 {
1037     int const blockTypeDesc = RAND(seed) % 8;
1038     size_t blockSize;
1039     int blockType;
1040
1041     BYTE *const header = (BYTE*)frame->data;
1042     BYTE *op = header + 3;
1043
1044     DISPLAYLEVEL(4, " block:\n");
1045     DISPLAYLEVEL(4, "  block content size: %u\n", (unsigned)contentSize);
1046     DISPLAYLEVEL(4, "  last block: %s\n", lastBlock ? "yes" : "no");
1047
1048     if (blockTypeDesc == 0) {
1049         /* Raw data frame */
1050
1051         RAND_buffer(seed, frame->src, contentSize);
1052         memcpy(op, frame->src, contentSize);
1053
1054         op += contentSize;
1055         blockType = 0;
1056         blockSize = contentSize;
1057     } else if (blockTypeDesc == 1 && frame->header.contentSize > 0) {
1058         /* RLE (Don't create RLE block if frame content is 0 since block size of 1 may exceed max block size)*/
1059         BYTE const symbol = RAND(seed) & 0xff;
1060
1061         op[0] = symbol;
1062         memset(frame->src, symbol, contentSize);
1063
1064         op++;
1065         blockType = 1;
1066         blockSize = contentSize;
1067     } else {
1068         /* compressed, most common */
1069         size_t compressedSize;
1070         blockType = 2;
1071
1072         frame->oldStats = frame->stats;
1073
1074         frame->data = op;
1075         compressedSize = writeCompressedBlock(seed, frame, contentSize, info);
1076         if (compressedSize >= contentSize) {   /* compressed block must be strictly smaller than uncompressed one */
1077             blockType = 0;
1078             memcpy(op, frame->src, contentSize);
1079
1080             op += contentSize;
1081             blockSize = contentSize; /* fall back on raw block if data doesn't
1082                                         compress */
1083
1084             frame->stats = frame->oldStats; /* don't update the stats */
1085         } else {
1086             op += compressedSize;
1087             blockSize = compressedSize;
1088         }
1089     }
1090     frame->src = (BYTE*)frame->src + contentSize;
1091
1092     DISPLAYLEVEL(4, "  block type: %s\n", BLOCK_TYPES[blockType]);
1093     DISPLAYLEVEL(4, "  block size field: %u\n", (unsigned)blockSize);
1094
1095     header[0] = (BYTE) ((lastBlock | (blockType << 1) | (blockSize << 3)) & 0xff);
1096     MEM_writeLE16(header + 1, (U16) (blockSize >> 5));
1097
1098     frame->data = op;
1099 }
1100
1101 static void writeBlocks(U32* seed, frame_t* frame, dictInfo info)
1102 {
1103     size_t contentLeft = frame->header.contentSize;
1104     size_t const maxBlockSize = MIN(g_maxBlockSize, frame->header.windowSize);
1105     while (1) {
1106         /* 1 in 4 chance of ending frame */
1107         int const lastBlock = contentLeft > maxBlockSize ? 0 : !(RAND(seed) & 3);
1108         size_t blockContentSize;
1109         if (lastBlock) {
1110             blockContentSize = contentLeft;
1111         } else {
1112             if (contentLeft > 0 && (RAND(seed) & 7)) {
1113                 /* some variable size block */
1114                 blockContentSize = RAND(seed) % (MIN(maxBlockSize, contentLeft)+1);
1115             } else if (contentLeft > maxBlockSize && (RAND(seed) & 1)) {
1116                 /* some full size block */
1117                 blockContentSize = maxBlockSize;
1118             } else {
1119                 /* some empty block */
1120                 blockContentSize = 0;
1121             }
1122         }
1123
1124         writeBlock(seed, frame, blockContentSize, lastBlock, info);
1125
1126         contentLeft -= blockContentSize;
1127         if (lastBlock) break;
1128     }
1129 }
1130
1131 static void writeChecksum(frame_t* frame)
1132 {
1133     /* write checksum so implementations can verify their output */
1134     U64 digest = XXH64(frame->srcStart, (BYTE*)frame->src-(BYTE*)frame->srcStart, 0);
1135     DISPLAYLEVEL(3, "  checksum: %08x\n", (unsigned)digest);
1136     MEM_writeLE32(frame->data, (U32)digest);
1137     frame->data = (BYTE*)frame->data + 4;
1138 }
1139
1140 static void outputBuffer(const void* buf, size_t size, const char* const path)
1141 {
1142     /* write data out to file */
1143     const BYTE* ip = (const BYTE*)buf;
1144     FILE* out;
1145     if (path) {
1146         out = fopen(path, "wb");
1147     } else {
1148         out = stdout;
1149     }
1150     if (!out) {
1151         fprintf(stderr, "Failed to open file at %s: ", path);
1152         perror(NULL);
1153         exit(1);
1154     }
1155
1156     {   size_t fsize = size;
1157         size_t written = 0;
1158         while (written < fsize) {
1159             written += fwrite(ip + written, 1, fsize - written, out);
1160             if (ferror(out)) {
1161                 fprintf(stderr, "Failed to write to file at %s: ", path);
1162                 perror(NULL);
1163                 exit(1);
1164             }
1165         }
1166     }
1167
1168     if (path) {
1169         fclose(out);
1170     }
1171 }
1172
1173 static void initFrame(frame_t* fr)
1174 {
1175     memset(fr, 0, sizeof(*fr));
1176     fr->data = fr->dataStart = FRAME_BUFFER;
1177     fr->dataEnd = FRAME_BUFFER + sizeof(FRAME_BUFFER);
1178     fr->src = fr->srcStart = CONTENT_BUFFER;
1179     fr->srcEnd = CONTENT_BUFFER + sizeof(CONTENT_BUFFER);
1180
1181     /* init repeat codes */
1182     fr->stats.rep[0] = 1;
1183     fr->stats.rep[1] = 4;
1184     fr->stats.rep[2] = 8;
1185 }
1186
1187 /**
1188  * Generated a single zstd compressed block with no block/frame header.
1189  * Returns the final seed.
1190  */
1191 static U32 generateCompressedBlock(U32 seed, frame_t* frame, dictInfo info)
1192 {
1193     size_t blockContentSize;
1194     int blockWritten = 0;
1195     BYTE* op;
1196     DISPLAYLEVEL(4, "block seed: %u\n", (unsigned)seed);
1197     initFrame(frame);
1198     op = (BYTE*)frame->data;
1199
1200     while (!blockWritten) {
1201         size_t cSize;
1202         /* generate window size */
1203         {   int const exponent = RAND(&seed) % (MAX_WINDOW_LOG - 10);
1204             int const mantissa = RAND(&seed) % 8;
1205             frame->header.windowSize = (1U << (exponent + 10));
1206             frame->header.windowSize += (frame->header.windowSize / 8) * mantissa;
1207         }
1208
1209         /* generate content size */
1210         {   size_t const maxBlockSize = MIN(g_maxBlockSize, frame->header.windowSize);
1211             if (RAND(&seed) & 15) {
1212                 /* some full size blocks */
1213                 blockContentSize = maxBlockSize;
1214             } else if (RAND(&seed) & 7 && g_maxBlockSize >= (1U << 7)) {
1215                 /* some small blocks <= 128 bytes*/
1216                 blockContentSize = RAND(&seed) % (1U << 7);
1217             } else {
1218                 /* some variable size blocks */
1219                 blockContentSize = RAND(&seed) % maxBlockSize;
1220             }
1221         }
1222
1223         /* try generating a compressed block */
1224         frame->oldStats = frame->stats;
1225         frame->data = op;
1226         cSize = writeCompressedBlock(&seed, frame, blockContentSize, info);
1227         if (cSize >= blockContentSize) {  /* compressed size must be strictly smaller than decompressed size : https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#blocks */
1228             /* data doesn't compress -- try again */
1229             frame->stats = frame->oldStats; /* don't update the stats */
1230             DISPLAYLEVEL(5, "   can't compress block : try again \n");
1231         } else {
1232             blockWritten = 1;
1233             DISPLAYLEVEL(4, "   block size: %u \n", (unsigned)cSize);
1234             frame->src = (BYTE*)frame->src + blockContentSize;
1235         }
1236     }
1237     return seed;
1238 }
1239
1240 /* Return the final seed */
1241 static U32 generateFrame(U32 seed, frame_t* fr, dictInfo info)
1242 {
1243     /* generate a complete frame */
1244     DISPLAYLEVEL(3, "frame seed: %u\n", (unsigned)seed);
1245     initFrame(fr);
1246
1247     writeFrameHeader(&seed, fr, info);
1248     writeBlocks(&seed, fr, info);
1249     writeChecksum(fr);
1250
1251     return seed;
1252 }
1253
1254 /*_*******************************************************
1255 *  Dictionary Helper Functions
1256 *********************************************************/
1257 /* returns 0 if successful, otherwise returns 1 upon error */
1258 static int genRandomDict(U32 dictID, U32 seed, size_t dictSize, BYTE* fullDict)
1259 {
1260     /* allocate space for samples */
1261     int ret = 0;
1262     unsigned const numSamples = 4;
1263     size_t sampleSizes[4];
1264     BYTE* const samples = malloc(5000*sizeof(BYTE));
1265     if (samples == NULL) {
1266         DISPLAY("Error: could not allocate space for samples\n");
1267         return 1;
1268     }
1269
1270     /* generate samples */
1271     {   unsigned literalValue = 1;
1272         unsigned samplesPos = 0;
1273         size_t currSize = 1;
1274         while (literalValue <= 4) {
1275             sampleSizes[literalValue - 1] = currSize;
1276             {   size_t k;
1277                 for (k = 0; k < currSize; k++) {
1278                     *(samples + (samplesPos++)) = (BYTE)literalValue;
1279             }   }
1280             literalValue++;
1281             currSize *= 16;
1282     }   }
1283
1284     {   size_t dictWriteSize = 0;
1285         ZDICT_params_t zdictParams;
1286         size_t const headerSize = MAX(dictSize/4, 256);
1287         size_t const dictContentSize = dictSize - headerSize;
1288         BYTE* const dictContent = fullDict + headerSize;
1289         if (dictContentSize < ZDICT_CONTENTSIZE_MIN || dictSize < ZDICT_DICTSIZE_MIN) {
1290             DISPLAY("Error: dictionary size is too small\n");
1291             ret = 1;
1292             goto exitGenRandomDict;
1293         }
1294
1295         /* init dictionary params */
1296         memset(&zdictParams, 0, sizeof(zdictParams));
1297         zdictParams.dictID = dictID;
1298         zdictParams.notificationLevel = 1;
1299
1300         /* fill in dictionary content */
1301         RAND_buffer(&seed, (void*)dictContent, dictContentSize);
1302
1303         /* finalize dictionary with random samples */
1304         dictWriteSize = ZDICT_finalizeDictionary(fullDict, dictSize,
1305                                     dictContent, dictContentSize,
1306                                     samples, sampleSizes, numSamples,
1307                                     zdictParams);
1308
1309         if (ZDICT_isError(dictWriteSize)) {
1310             DISPLAY("Could not finalize dictionary: %s\n", ZDICT_getErrorName(dictWriteSize));
1311             ret = 1;
1312         }
1313     }
1314
1315 exitGenRandomDict:
1316     free(samples);
1317     return ret;
1318 }
1319
1320 static dictInfo initDictInfo(int useDict, size_t dictContentSize, BYTE* dictContent, U32 dictID){
1321     /* allocate space statically */
1322     dictInfo dictOp;
1323     memset(&dictOp, 0, sizeof(dictOp));
1324     dictOp.useDict = useDict;
1325     dictOp.dictContentSize = dictContentSize;
1326     dictOp.dictContent = dictContent;
1327     dictOp.dictID = dictID;
1328     return dictOp;
1329 }
1330
1331 /*-*******************************************************
1332 *  Test Mode
1333 *********************************************************/
1334
1335 BYTE DECOMPRESSED_BUFFER[MAX_DECOMPRESSED_SIZE];
1336
1337 static size_t testDecodeSimple(frame_t* fr)
1338 {
1339     /* test decoding the generated data with the simple API */
1340     size_t const ret = ZSTD_decompress(DECOMPRESSED_BUFFER, MAX_DECOMPRESSED_SIZE,
1341                            fr->dataStart, (BYTE*)fr->data - (BYTE*)fr->dataStart);
1342
1343     if (ZSTD_isError(ret)) return ret;
1344
1345     if (memcmp(DECOMPRESSED_BUFFER, fr->srcStart,
1346                (BYTE*)fr->src - (BYTE*)fr->srcStart) != 0) {
1347         return ERROR(corruption_detected);
1348     }
1349
1350     return ret;
1351 }
1352
1353 static size_t testDecodeStreaming(frame_t* fr)
1354 {
1355     /* test decoding the generated data with the streaming API */
1356     ZSTD_DStream* zd = ZSTD_createDStream();
1357     ZSTD_inBuffer in;
1358     ZSTD_outBuffer out;
1359     size_t ret;
1360
1361     if (!zd) return ERROR(memory_allocation);
1362
1363     in.src = fr->dataStart;
1364     in.pos = 0;
1365     in.size = (BYTE*)fr->data - (BYTE*)fr->dataStart;
1366
1367     out.dst = DECOMPRESSED_BUFFER;
1368     out.pos = 0;
1369     out.size = ZSTD_DStreamOutSize();
1370
1371     ZSTD_initDStream(zd);
1372     while (1) {
1373         ret = ZSTD_decompressStream(zd, &out, &in);
1374         if (ZSTD_isError(ret)) goto cleanup; /* error */
1375         if (ret == 0) break; /* frame is done */
1376
1377         /* force decoding to be done in chunks */
1378         out.size += MIN(ZSTD_DStreamOutSize(), MAX_DECOMPRESSED_SIZE - out.size);
1379     }
1380
1381     ret = out.pos;
1382
1383     if (memcmp(out.dst, fr->srcStart, out.pos) != 0) {
1384         return ERROR(corruption_detected);
1385     }
1386
1387 cleanup:
1388     ZSTD_freeDStream(zd);
1389     return ret;
1390 }
1391
1392 static size_t testDecodeWithDict(U32 seed, genType_e genType)
1393 {
1394     /* create variables */
1395     size_t const dictSize = RAND(&seed) % (10 << 20) + ZDICT_DICTSIZE_MIN + ZDICT_CONTENTSIZE_MIN;
1396     U32 const dictID = RAND(&seed);
1397     size_t errorDetected = 0;
1398     BYTE* const fullDict = malloc(dictSize);
1399     if (fullDict == NULL) {
1400         return ERROR(GENERIC);
1401     }
1402
1403     /* generate random dictionary */
1404     if (genRandomDict(dictID, seed, dictSize, fullDict)) {  /* return 0 on success */
1405         errorDetected = ERROR(GENERIC);
1406         goto dictTestCleanup;
1407     }
1408
1409
1410     {   frame_t fr;
1411         dictInfo info;
1412         ZSTD_DCtx* const dctx = ZSTD_createDCtx();
1413         size_t ret;
1414
1415         /* get dict info */
1416         {   size_t const headerSize = MAX(dictSize/4, 256);
1417             size_t const dictContentSize = dictSize-headerSize;
1418             BYTE* const dictContent = fullDict+headerSize;
1419             info = initDictInfo(1, dictContentSize, dictContent, dictID);
1420         }
1421
1422         /* manually decompress and check difference */
1423         if (genType == gt_frame) {
1424             /* Test frame */
1425             generateFrame(seed, &fr, info);
1426             ret = ZSTD_decompress_usingDict(dctx, DECOMPRESSED_BUFFER, MAX_DECOMPRESSED_SIZE,
1427                                             fr.dataStart, (BYTE*)fr.data - (BYTE*)fr.dataStart,
1428                                             fullDict, dictSize);
1429         } else {
1430             /* Test block */
1431             generateCompressedBlock(seed, &fr, info);
1432             ret = ZSTD_decompressBegin_usingDict(dctx, fullDict, dictSize);
1433             if (ZSTD_isError(ret)) {
1434                 errorDetected = ret;
1435                 ZSTD_freeDCtx(dctx);
1436                 goto dictTestCleanup;
1437             }
1438             ret = ZSTD_decompressBlock_deprecated(dctx, DECOMPRESSED_BUFFER, MAX_DECOMPRESSED_SIZE,
1439                                        fr.dataStart, (BYTE*)fr.data - (BYTE*)fr.dataStart);
1440         }
1441         ZSTD_freeDCtx(dctx);
1442
1443         if (ZSTD_isError(ret)) {
1444             errorDetected = ret;
1445             goto dictTestCleanup;
1446         }
1447
1448         if (memcmp(DECOMPRESSED_BUFFER, fr.srcStart, (BYTE*)fr.src - (BYTE*)fr.srcStart) != 0) {
1449             errorDetected = ERROR(corruption_detected);
1450             goto dictTestCleanup;
1451         }
1452     }
1453
1454 dictTestCleanup:
1455     free(fullDict);
1456     return errorDetected;
1457 }
1458
1459 static size_t testDecodeRawBlock(frame_t* fr)
1460 {
1461     ZSTD_DCtx* dctx = ZSTD_createDCtx();
1462     size_t ret = ZSTD_decompressBegin(dctx);
1463     if (ZSTD_isError(ret)) return ret;
1464
1465     ret = ZSTD_decompressBlock_deprecated(
1466             dctx,
1467             DECOMPRESSED_BUFFER, MAX_DECOMPRESSED_SIZE,
1468             fr->dataStart, (BYTE*)fr->data - (BYTE*)fr->dataStart);
1469     ZSTD_freeDCtx(dctx);
1470     if (ZSTD_isError(ret)) return ret;
1471
1472     if (memcmp(DECOMPRESSED_BUFFER, fr->srcStart,
1473                (BYTE*)fr->src - (BYTE*)fr->srcStart) != 0) {
1474         return ERROR(corruption_detected);
1475     }
1476
1477     return ret;
1478 }
1479
1480 static int runBlockTest(U32* seed)
1481 {
1482     frame_t fr;
1483     U32 const seedCopy = *seed;
1484     {   dictInfo const info = initDictInfo(0, 0, NULL, 0);
1485         *seed = generateCompressedBlock(*seed, &fr, info);
1486     }
1487
1488     {   size_t const r = testDecodeRawBlock(&fr);
1489         if (ZSTD_isError(r)) {
1490             DISPLAY("Error in block mode on test seed %u: %s\n",
1491                     (unsigned)seedCopy, ZSTD_getErrorName(r));
1492             return 1;
1493         }
1494     }
1495
1496     {   size_t const r = testDecodeWithDict(*seed, gt_block);
1497         if (ZSTD_isError(r)) {
1498             DISPLAY("Error in block mode with dictionary on test seed %u: %s\n",
1499                     (unsigned)seedCopy, ZSTD_getErrorName(r));
1500             return 1;
1501         }
1502     }
1503     return 0;
1504 }
1505
1506 static int runFrameTest(U32* seed)
1507 {
1508     frame_t fr;
1509     U32 const seedCopy = *seed;
1510     {   dictInfo const info = initDictInfo(0, 0, NULL, 0);
1511         *seed = generateFrame(*seed, &fr, info);
1512     }
1513
1514     {   size_t const r = testDecodeSimple(&fr);
1515         if (ZSTD_isError(r)) {
1516             DISPLAY("Error in simple mode on test seed %u: %s\n",
1517                     (unsigned)seedCopy, ZSTD_getErrorName(r));
1518             return 1;
1519         }
1520     }
1521     {   size_t const r = testDecodeStreaming(&fr);
1522         if (ZSTD_isError(r)) {
1523             DISPLAY("Error in streaming mode on test seed %u: %s\n",
1524                     (unsigned)seedCopy, ZSTD_getErrorName(r));
1525             return 1;
1526         }
1527     }
1528     {   size_t const r = testDecodeWithDict(*seed, gt_frame);  /* avoid big dictionaries */
1529         if (ZSTD_isError(r)) {
1530             DISPLAY("Error in dictionary mode on test seed %u: %s\n",
1531                     (unsigned)seedCopy, ZSTD_getErrorName(r));
1532             return 1;
1533         }
1534     }
1535     return 0;
1536 }
1537
1538 static int runTestMode(U32 seed, unsigned numFiles, unsigned const testDurationS,
1539                        genType_e genType)
1540 {
1541     unsigned fnum;
1542
1543     UTIL_time_t const startClock = UTIL_getTime();
1544     U64 const maxClockSpan = testDurationS * SEC_TO_MICRO;
1545
1546     if (numFiles == 0 && !testDurationS) numFiles = 1;
1547
1548     DISPLAY("seed: %u\n", (unsigned)seed);
1549
1550     for (fnum = 0; fnum < numFiles || UTIL_clockSpanMicro(startClock) < maxClockSpan; fnum++) {
1551         if (fnum < numFiles)
1552             DISPLAYUPDATE("\r%u/%u        ", fnum, numFiles);
1553         else
1554             DISPLAYUPDATE("\r%u           ", fnum);
1555
1556         {   int const ret = (genType == gt_frame) ?
1557                             runFrameTest(&seed) :
1558                             runBlockTest(&seed);
1559             if (ret) return ret;
1560         }
1561     }
1562
1563     DISPLAY("\r%u tests completed: ", fnum);
1564     DISPLAY("OK\n");
1565
1566     return 0;
1567 }
1568
1569 /*-*******************************************************
1570 *  File I/O
1571 *********************************************************/
1572
1573 static int generateFile(U32 seed, const char* const path,
1574                         const char* const origPath, genType_e genType)
1575 {
1576     frame_t fr;
1577
1578     DISPLAY("seed: %u\n", (unsigned)seed);
1579
1580     {   dictInfo const info = initDictInfo(0, 0, NULL, 0);
1581         if (genType == gt_frame) {
1582             generateFrame(seed, &fr, info);
1583         } else {
1584             generateCompressedBlock(seed, &fr, info);
1585         }
1586     }
1587     outputBuffer(fr.dataStart, (BYTE*)fr.data - (BYTE*)fr.dataStart, path);
1588     if (origPath) {
1589         outputBuffer(fr.srcStart, (BYTE*)fr.src - (BYTE*)fr.srcStart, origPath);
1590     }
1591     return 0;
1592 }
1593
1594 static int generateCorpus(U32 seed, unsigned numFiles, const char* const path,
1595                           const char* const origPath, genType_e genType)
1596 {
1597     char outPath[MAX_PATH];
1598     unsigned fnum;
1599
1600     DISPLAY("seed: %u\n", (unsigned)seed);
1601
1602     for (fnum = 0; fnum < numFiles; fnum++) {
1603         frame_t fr;
1604
1605         DISPLAYUPDATE("\r%u/%u        ", fnum, numFiles);
1606
1607         {   dictInfo const info = initDictInfo(0, 0, NULL, 0);
1608             if (genType == gt_frame) {
1609                 seed = generateFrame(seed, &fr, info);
1610             } else {
1611                 seed = generateCompressedBlock(seed, &fr, info);
1612             }
1613         }
1614
1615         if (snprintf(outPath, MAX_PATH, "%s/z%06u.zst", path, fnum) + 1 > MAX_PATH) {
1616             DISPLAY("Error: path too long\n");
1617             return 1;
1618         }
1619         outputBuffer(fr.dataStart, (BYTE*)fr.data - (BYTE*)fr.dataStart, outPath);
1620
1621         if (origPath) {
1622             if (snprintf(outPath, MAX_PATH, "%s/z%06u", origPath, fnum) + 1 > MAX_PATH) {
1623                 DISPLAY("Error: path too long\n");
1624                 return 1;
1625             }
1626             outputBuffer(fr.srcStart, (BYTE*)fr.src - (BYTE*)fr.srcStart, outPath);
1627         }
1628     }
1629
1630     DISPLAY("\r%u/%u      \n", fnum, numFiles);
1631
1632     return 0;
1633 }
1634
1635 static int generateCorpusWithDict(U32 seed, unsigned numFiles, const char* const path,
1636                                   const char* const origPath, const size_t dictSize,
1637                                   genType_e genType)
1638 {
1639     char outPath[MAX_PATH];
1640     BYTE* fullDict;
1641     U32 const dictID = RAND(&seed);
1642     int errorDetected = 0;
1643
1644     if (snprintf(outPath, MAX_PATH, "%s/dictionary", path) + 1 > MAX_PATH) {
1645         DISPLAY("Error: path too long\n");
1646         return 1;
1647     }
1648
1649     /* allocate space for the dictionary */
1650     fullDict = malloc(dictSize);
1651     if (fullDict == NULL) {
1652         DISPLAY("Error: could not allocate space for full dictionary.\n");
1653         return 1;
1654     }
1655
1656     /* randomly generate the dictionary */
1657     {   int const ret = genRandomDict(dictID, seed, dictSize, fullDict);
1658         if (ret != 0) {
1659             errorDetected = ret;
1660             goto dictCleanup;
1661         }
1662     }
1663
1664     /* write out dictionary */
1665     if (numFiles != 0) {
1666         if (snprintf(outPath, MAX_PATH, "%s/dictionary", path) + 1 > MAX_PATH) {
1667             DISPLAY("Error: dictionary path too long\n");
1668             errorDetected = 1;
1669             goto dictCleanup;
1670         }
1671         outputBuffer(fullDict, dictSize, outPath);
1672     }
1673     else {
1674         outputBuffer(fullDict, dictSize, "dictionary");
1675     }
1676
1677     /* generate random compressed/decompressed files */
1678     {   unsigned fnum;
1679         for (fnum = 0; fnum < MAX(numFiles, 1); fnum++) {
1680             frame_t fr;
1681             DISPLAYUPDATE("\r%u/%u        ", fnum, numFiles);
1682             {
1683                 size_t const headerSize = MAX(dictSize/4, 256);
1684                 size_t const dictContentSize = dictSize-headerSize;
1685                 BYTE* const dictContent = fullDict+headerSize;
1686                 dictInfo const info = initDictInfo(1, dictContentSize, dictContent, dictID);
1687                 if (genType == gt_frame) {
1688                     seed = generateFrame(seed, &fr, info);
1689                 } else {
1690                     seed = generateCompressedBlock(seed, &fr, info);
1691                 }
1692             }
1693
1694             if (numFiles != 0) {
1695                 if (snprintf(outPath, MAX_PATH, "%s/z%06u.zst", path, fnum) + 1 > MAX_PATH) {
1696                     DISPLAY("Error: path too long\n");
1697                     errorDetected = 1;
1698                     goto dictCleanup;
1699                 }
1700                 outputBuffer(fr.dataStart, (BYTE*)fr.data - (BYTE*)fr.dataStart, outPath);
1701
1702                 if (origPath) {
1703                     if (snprintf(outPath, MAX_PATH, "%s/z%06u", origPath, fnum) + 1 > MAX_PATH) {
1704                         DISPLAY("Error: path too long\n");
1705                         errorDetected = 1;
1706                         goto dictCleanup;
1707                     }
1708                     outputBuffer(fr.srcStart, (BYTE*)fr.src - (BYTE*)fr.srcStart, outPath);
1709                 }
1710             }
1711             else {
1712                 outputBuffer(fr.dataStart, (BYTE*)fr.data - (BYTE*)fr.dataStart, path);
1713                 if (origPath) {
1714                     outputBuffer(fr.srcStart, (BYTE*)fr.src - (BYTE*)fr.srcStart, origPath);
1715                 }
1716             }
1717         }
1718     }
1719
1720 dictCleanup:
1721     free(fullDict);
1722     return errorDetected;
1723 }
1724
1725
1726 /*_*******************************************************
1727 *  Command line
1728 *********************************************************/
1729 static U32 makeSeed(void)
1730 {
1731     U32 t = (U32) time(NULL);
1732     return XXH32(&t, sizeof(t), 0) % 65536;
1733 }
1734
1735 static unsigned readInt(const char** argument)
1736 {
1737     unsigned val = 0;
1738     while ((**argument>='0') && (**argument<='9')) {
1739         val *= 10;
1740         val += **argument - '0';
1741         (*argument)++;
1742     }
1743     return val;
1744 }
1745
1746 static void usage(const char* programName)
1747 {
1748     DISPLAY( "Usage :\n");
1749     DISPLAY( "      %s [args]\n", programName);
1750     DISPLAY( "\n");
1751     DISPLAY( "Arguments :\n");
1752     DISPLAY( " -p<path> : select output path (default:stdout)\n");
1753     DISPLAY( "                in multiple files mode this should be a directory\n");
1754     DISPLAY( " -o<path> : select path to output original file (default:no output)\n");
1755     DISPLAY( "                in multiple files mode this should be a directory\n");
1756     DISPLAY( " -s#      : select seed (default:random based on time)\n");
1757     DISPLAY( " -n#      : number of files to generate (default:1)\n");
1758     DISPLAY( " -t       : activate test mode (test files against libzstd instead of outputting them)\n");
1759     DISPLAY( " -T#      : length of time to run tests for\n");
1760     DISPLAY( " -v       : increase verbosity level (default:0, max:7)\n");
1761     DISPLAY( " -h/H     : display help/long help and exit\n");
1762 }
1763
1764 static void advancedUsage(const char* programName)
1765 {
1766     usage(programName);
1767     DISPLAY( "\n");
1768     DISPLAY( "Advanced arguments        :\n");
1769     DISPLAY( " --content-size           : always include the content size in the frame header\n");
1770     DISPLAY( " --use-dict=#             : include a dictionary used to decompress the corpus\n");
1771     DISPLAY( " --gen-blocks             : generate raw compressed blocks without block/frame headers\n");
1772     DISPLAY( " --max-block-size-log=#   : max block size log, must be in range [2, 17]\n");
1773     DISPLAY( " --max-content-size-log=# : max content size log, must be <= 20\n");
1774     DISPLAY( "                            (this is ignored with gen-blocks)\n");
1775 }
1776
1777 /*! readU32FromChar() :
1778     @return : unsigned integer value read from input in `char` format
1779     allows and interprets K, KB, KiB, M, MB and MiB suffix.
1780     Will also modify `*stringPtr`, advancing it to position where it stopped reading.
1781     Note : function result can overflow if digit string > MAX_UINT */
1782 static unsigned readU32FromChar(const char** stringPtr)
1783 {
1784     unsigned result = 0;
1785     while ((**stringPtr >='0') && (**stringPtr <='9'))
1786         result *= 10, result += **stringPtr - '0', (*stringPtr)++ ;
1787     if ((**stringPtr=='K') || (**stringPtr=='M')) {
1788         result <<= 10;
1789         if (**stringPtr=='M') result <<= 10;
1790         (*stringPtr)++ ;
1791         if (**stringPtr=='i') (*stringPtr)++;
1792         if (**stringPtr=='B') (*stringPtr)++;
1793     }
1794     return result;
1795 }
1796
1797 /** longCommandWArg() :
1798  *  check if *stringPtr is the same as longCommand.
1799  *  If yes, @return 1 and advances *stringPtr to the position which immediately follows longCommand.
1800  *  @return 0 and doesn't modify *stringPtr otherwise.
1801  */
1802 static unsigned longCommandWArg(const char** stringPtr, const char* longCommand)
1803 {
1804     size_t const comSize = strlen(longCommand);
1805     int const result = !strncmp(*stringPtr, longCommand, comSize);
1806     if (result) *stringPtr += comSize;
1807     return result;
1808 }
1809
1810 int main(int argc, char** argv)
1811 {
1812     U32 seed = 0;
1813     int seedset = 0;
1814     unsigned numFiles = 0;
1815     unsigned testDuration = 0;
1816     int testMode = 0;
1817     const char* path = NULL;
1818     const char* origPath = NULL;
1819     int useDict = 0;
1820     unsigned dictSize = (10 << 10); /* 10 kB default */
1821     genType_e genType = gt_frame;
1822
1823     int argNb;
1824
1825     /* Check command line */
1826     for (argNb=1; argNb<argc; argNb++) {
1827         const char* argument = argv[argNb];
1828         if(!argument) continue;   /* Protection if argument empty */
1829
1830         /* Handle commands. Aggregated commands are allowed */
1831         if (argument[0]=='-') {
1832             argument++;
1833             while (*argument!=0) {
1834                 switch(*argument)
1835                 {
1836                 case 'h':
1837                     usage(argv[0]);
1838                     return 0;
1839                 case 'H':
1840                     advancedUsage(argv[0]);
1841                     return 0;
1842                 case 'v':
1843                     argument++;
1844                     g_displayLevel++;
1845                     break;
1846                 case 's':
1847                     argument++;
1848                     seedset=1;
1849                     seed = readInt(&argument);
1850                     break;
1851                 case 'n':
1852                     argument++;
1853                     numFiles = readInt(&argument);
1854                     break;
1855                 case 'T':
1856                     argument++;
1857                     testDuration = readInt(&argument);
1858                     if (*argument == 'm') {
1859                         testDuration *= 60;
1860                         argument++;
1861                         if (*argument == 'n') argument++;
1862                     }
1863                     break;
1864                 case 'o':
1865                     argument++;
1866                     origPath = argument;
1867                     argument += strlen(argument);
1868                     break;
1869                 case 'p':
1870                     argument++;
1871                     path = argument;
1872                     argument += strlen(argument);
1873                     break;
1874                 case 't':
1875                     argument++;
1876                     testMode = 1;
1877                     break;
1878                 case '-':
1879                     argument++;
1880                     if (strcmp(argument, "content-size") == 0) {
1881                         opts.contentSize = 1;
1882                     } else if (longCommandWArg(&argument, "use-dict=")) {
1883                         dictSize = readU32FromChar(&argument);
1884                         useDict = 1;
1885                     } else if (strcmp(argument, "gen-blocks") == 0) {
1886                         genType = gt_block;
1887                     } else if (longCommandWArg(&argument, "max-block-size-log=")) {
1888                         U32 value = readU32FromChar(&argument);
1889                         if (value >= 2 && value <= ZSTD_BLOCKSIZE_MAX) {
1890                             g_maxBlockSize = 1U << value;
1891                         }
1892                     } else if (longCommandWArg(&argument, "max-content-size-log=")) {
1893                         U32 value = readU32FromChar(&argument);
1894                         g_maxDecompressedSizeLog =
1895                                 MIN(MAX_DECOMPRESSED_SIZE_LOG, value);
1896                     } else {
1897                         advancedUsage(argv[0]);
1898                         return 1;
1899                     }
1900                     argument += strlen(argument);
1901                     break;
1902                 default:
1903                     usage(argv[0]);
1904                     return 1;
1905     }   }   }   }   /* for (argNb=1; argNb<argc; argNb++) */
1906
1907     if (!seedset) {
1908         seed = makeSeed();
1909     }
1910
1911     if (testMode) {
1912         return runTestMode(seed, numFiles, testDuration, genType);
1913     } else {
1914         if (testDuration) {
1915             DISPLAY("Error: -T requires test mode (-t)\n\n");
1916             usage(argv[0]);
1917             return 1;
1918         }
1919     }
1920
1921     if (!path) {
1922         DISPLAY("Error: path is required in file generation mode\n");
1923         usage(argv[0]);
1924         return 1;
1925     }
1926
1927     if (numFiles == 0 && useDict == 0) {
1928         return generateFile(seed, path, origPath, genType);
1929     } else if (useDict == 0){
1930         return generateCorpus(seed, numFiles, path, origPath, genType);
1931     } else {
1932         /* should generate files with a dictionary */
1933         return generateCorpusWithDict(seed, numFiles, path, origPath, dictSize, genType);
1934     }
1935
1936 }