sys/contrib/zstd/programs/datagen.c

   1 /*
   2  * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
   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
  12
  13 /*-************************************
  14 *  Dependencies
  15 **************************************/
  16 #include "datagen.h"
  17 #include "platform.h"  /* SET_BINARY_MODE */
  18 #include <stdlib.h>    /* malloc, free */
  19 #include <stdio.h>     /* FILE, fwrite, fprintf */
  20 #include <string.h>    /* memcpy */
  21 #include "mem.h"       /* U32 */
  22
  23
  24 /*-************************************
  25 *  Macros
  26 **************************************/
  27 #define KB *(1 <<10)
  28 #define MIN(a,b)  ( (a) < (b) ? (a) : (b) )
  29
  30 #define RDG_DEBUG 0
  31 #define TRACE(...)   if (RDG_DEBUG) fprintf(stderr, __VA_ARGS__ )
  32
  33
  34 /*-************************************
  35 *  Local constants
  36 **************************************/
  37 #define LTLOG 13
  38 #define LTSIZE (1<<LTLOG)
  39 #define LTMASK (LTSIZE-1)
  40
  41
  42 /*-*******************************************************
  43 *  Local Functions
  44 *********************************************************/
  45 #define RDG_rotl32(x,r) ((x << r) | (x >> (32 - r)))
  46 static U32 RDG_rand(U32* src)
  47 {
  48     static const U32 prime1 = 2654435761U;
  49     static const U32 prime2 = 2246822519U;
  50     U32 rand32 = *src;
  51     rand32 *= prime1;
  52     rand32 ^= prime2;
  53     rand32  = RDG_rotl32(rand32, 13);
  54     *src = rand32;
  55     return rand32 >> 5;
  56 }
  57
  58
  59 static void RDG_fillLiteralDistrib(BYTE* ldt, double ld)
  60 {
  61     BYTE const firstChar = (ld<=0.0) ?   0 : '(';
  62     BYTE const lastChar  = (ld<=0.0) ? 255 : '}';
  63     BYTE character = (ld<=0.0) ? 0 : '0';
  64     U32 u;
  65
  66     if (ld<=0.0) ld = 0.0;
  67     for (u=0; u<LTSIZE; ) {
  68         U32 const weight = (U32)((double)(LTSIZE - u) * ld) + 1;
  69         U32 const end = MIN ( u + weight , LTSIZE);
  70         while (u < end) ldt[u++] = character;
  71         character++;
  72         if (character > lastChar) character = firstChar;
  73     }
  74 }
  75
  76
  77 static BYTE RDG_genChar(U32* seed, const BYTE* ldt)
  78 {
  79     U32 const id = RDG_rand(seed) & LTMASK;
  80     return ldt[id];  /* memory-sanitizer fails here, stating "uninitialized value" when table initialized with P==0.0. Checked : table is fully initialized */
  81 }
  82
  83
  84 static U32 RDG_rand15Bits (U32* seedPtr)
  85 {
  86     return RDG_rand(seedPtr) & 0x7FFF;
  87 }
  88
  89 static U32 RDG_randLength(U32* seedPtr)
  90 {
  91     if (RDG_rand(seedPtr) & 7) return (RDG_rand(seedPtr) & 0xF);   /* small length */
  92     return (RDG_rand(seedPtr) & 0x1FF) + 0xF;
  93 }
  94
  95 static void RDG_genBlock(void* buffer, size_t buffSize, size_t prefixSize, double matchProba, const BYTE* ldt, U32* seedPtr)
  96 {
  97     BYTE* const buffPtr = (BYTE*)buffer;
  98     U32 const matchProba32 = (U32)(32768 * matchProba);
  99     size_t pos = prefixSize;
 100     U32 prevOffset = 1;
 101
 102     /* special case : sparse content */
 103     while (matchProba >= 1.0) {
 104         size_t size0 = RDG_rand(seedPtr) & 3;
 105         size0  = (size_t)1 << (16 + size0 * 2);
 106         size0 += RDG_rand(seedPtr) & (size0-1);   /* because size0 is power of 2*/
 107         if (buffSize < pos + size0) {
 108             memset(buffPtr+pos, 0, buffSize-pos);
 109             return;
 110         }
 111         memset(buffPtr+pos, 0, size0);
 112         pos += size0;
 113         buffPtr[pos-1] = RDG_genChar(seedPtr, ldt);
 114         continue;
 115     }
 116
 117     /* init */
 118     if (pos==0) buffPtr[0] = RDG_genChar(seedPtr, ldt), pos=1;
 119
 120     /* Generate compressible data */
 121     while (pos < buffSize) {
 122         /* Select : Literal (char) or Match (within 32K) */
 123         if (RDG_rand15Bits(seedPtr) < matchProba32) {
 124             /* Copy (within 32K) */
 125             U32 const length = RDG_randLength(seedPtr) + 4;
 126             U32 const d = (U32) MIN(pos + length , buffSize);
 127             U32 const repeatOffset = (RDG_rand(seedPtr) & 15) == 2;
 128             U32 const randOffset = RDG_rand15Bits(seedPtr) + 1;
 129             U32 const offset = repeatOffset ? prevOffset : (U32) MIN(randOffset , pos);
 130             size_t match = pos - offset;
 131             while (pos < d) buffPtr[pos++] = buffPtr[match++];   /* correctly manages overlaps */
 132             prevOffset = offset;
 133         } else {
 134             /* Literal (noise) */
 135             U32 const length = RDG_randLength(seedPtr);
 136             U32 const d = (U32) MIN(pos + length, buffSize);
 137             while (pos < d) buffPtr[pos++] = RDG_genChar(seedPtr, ldt);
 138     }   }
 139 }
 140
 141
 142 void RDG_genBuffer(void* buffer, size_t size, double matchProba, double litProba, unsigned seed)
 143 {
 144     U32 seed32 = seed;
 145     BYTE ldt[LTSIZE];
 146     memset(ldt, '0', sizeof(ldt));  /* yes, character '0', this is intentional */
 147     if (litProba<=0.0) litProba = matchProba / 4.5;
 148     RDG_fillLiteralDistrib(ldt, litProba);
 149     RDG_genBlock(buffer, size, 0, matchProba, ldt, &seed32);
 150 }
 151
 152
 153 void RDG_genStdout(unsigned long long size, double matchProba, double litProba, unsigned seed)
 154 {
 155     U32 seed32 = seed;
 156     size_t const stdBlockSize = 128 KB;
 157     size_t const stdDictSize = 32 KB;
 158     BYTE* const buff = (BYTE*)malloc(stdDictSize + stdBlockSize);
 159     U64 total = 0;
 160     BYTE ldt[LTSIZE];   /* literals distribution table */
 161
 162     /* init */
 163     if (buff==NULL) { perror("datagen"); exit(1); }
 164     if (litProba<=0.0) litProba = matchProba / 4.5;
 165     memset(ldt, '0', sizeof(ldt));   /* yes, character '0', this is intentional */
 166     RDG_fillLiteralDistrib(ldt, litProba);
 167     SET_BINARY_MODE(stdout);
 168
 169     /* Generate initial dict */
 170     RDG_genBlock(buff, stdDictSize, 0, matchProba, ldt, &seed32);
 171
 172     /* Generate compressible data */
 173     while (total < size) {
 174         size_t const genBlockSize = (size_t) (MIN (stdBlockSize, size-total));
 175         RDG_genBlock(buff, stdDictSize+stdBlockSize, stdDictSize, matchProba, ldt, &seed32);
 176         total += genBlockSize;
 177         { size_t const unused = fwrite(buff, 1, genBlockSize, stdout); (void)unused; }
 178         /* update dict */
 179         memcpy(buff, buff + stdBlockSize, stdDictSize);
 180     }
 181
 182     /* cleanup */
 183     free(buff);
 184 }