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