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