1 /* 2 datagen.c - compressible data generator test tool 3 Copyright (C) Yann Collet 2012-2016 4 5 GPL v2 License 6 7 This program is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 2 of the License, or 10 (at your option) any later version. 11 12 This program is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License along 18 with this program; if not, write to the Free Software Foundation, Inc., 19 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 20 21 You can contact the author at : 22 - LZ4 source repository : https://github.com/lz4/lz4 23 - Public forum : https://groups.google.com/forum/#!forum/lz4c 24 */ 25 26 /************************************** 27 * Includes 28 **************************************/ 29 #include "platform.h" /* Compiler options, SET_BINARY_MODE */ 30 #include "util.h" /* U32 */ 31 #include <stdlib.h> /* malloc */ 32 #include <stdio.h> /* FILE, fwrite */ 33 #include <string.h> /* memcpy */ 34 35 36 /************************************** 37 * Constants 38 **************************************/ 39 #define KB *(1 <<10) 40 41 #define PRIME1 2654435761U 42 #define PRIME2 2246822519U 43 44 45 /************************************** 46 * Local types 47 **************************************/ 48 #define LTLOG 13 49 #define LTSIZE (1<<LTLOG) 50 #define LTMASK (LTSIZE-1) 51 typedef BYTE litDistribTable[LTSIZE]; 52 53 54 55 /********************************************************* 56 * Local Functions 57 *********************************************************/ 58 #define MIN(a,b) ( (a) < (b) ? (a) :(b) ) 59 #define RDG_rotl32(x,r) ((x << r) | (x >> (32 - r))) 60 static unsigned int RDG_rand(U32* src) 61 { 62 U32 rand32 = *src; 63 rand32 *= PRIME1; 64 rand32 ^= PRIME2; 65 rand32 = RDG_rotl32(rand32, 13); 66 *src = rand32; 67 return rand32; 68 } 69 70 71 static void RDG_fillLiteralDistrib(litDistribTable lt, double ld) 72 { 73 BYTE const firstChar = ld <= 0.0 ? 0 : '('; 74 BYTE const lastChar = ld <= 0.0 ? 255 : '}'; 75 BYTE character = ld <= 0.0 ? 0 : '0'; 76 U32 u = 0; 77 78 while (u<LTSIZE) { 79 U32 const weight = (U32)((double)(LTSIZE - u) * ld) + 1; 80 U32 const end = MIN(u+weight, LTSIZE); 81 while (u < end) lt[u++] = character; 82 character++; 83 if (character > lastChar) character = firstChar; 84 } 85 } 86 87 88 static BYTE RDG_genChar(U32* seed, const litDistribTable lt) 89 { 90 U32 id = RDG_rand(seed) & LTMASK; 91 return (lt[id]); 92 } 93 94 95 #define RDG_DICTSIZE (32 KB) 96 #define RDG_RAND15BITS ((RDG_rand(seed) >> 3) & 32767) 97 #define RDG_RANDLENGTH ( ((RDG_rand(seed) >> 7) & 7) ? (RDG_rand(seed) & 15) : (RDG_rand(seed) & 511) + 15) 98 void RDG_genBlock(void* buffer, size_t buffSize, size_t prefixSize, double matchProba, litDistribTable lt, unsigned* seedPtr) 99 { 100 BYTE* buffPtr = (BYTE*)buffer; 101 const U32 matchProba32 = (U32)(32768 * matchProba); 102 size_t pos = prefixSize; 103 U32* seed = seedPtr; 104 105 /* special case */ 106 while (matchProba >= 1.0) 107 { 108 size_t size0 = RDG_rand(seed) & 3; 109 size0 = (size_t)1 << (16 + size0 * 2); 110 size0 += RDG_rand(seed) & (size0-1); /* because size0 is power of 2*/ 111 if (buffSize < pos + size0) 112 { 113 memset(buffPtr+pos, 0, buffSize-pos); 114 return; 115 } 116 memset(buffPtr+pos, 0, size0); 117 pos += size0; 118 buffPtr[pos-1] = RDG_genChar(seed, lt); 119 } 120 121 /* init */ 122 if (pos==0) buffPtr[0] = RDG_genChar(seed, lt), pos=1; 123 124 /* Generate compressible data */ 125 while (pos < buffSize) 126 { 127 /* Select : Literal (char) or Match (within 32K) */ 128 if (RDG_RAND15BITS < matchProba32) 129 { 130 /* Copy (within 32K) */ 131 size_t match; 132 size_t d; 133 int length = RDG_RANDLENGTH + 4; 134 U32 offset = RDG_RAND15BITS + 1; 135 if (offset > pos) offset = (U32)pos; 136 match = pos - offset; 137 d = pos + length; 138 if (d > buffSize) d = buffSize; 139 while (pos < d) buffPtr[pos++] = buffPtr[match++]; 140 } 141 else 142 { 143 /* Literal (noise) */ 144 size_t d; 145 size_t length = RDG_RANDLENGTH; 146 d = pos + length; 147 if (d > buffSize) d = buffSize; 148 while (pos < d) buffPtr[pos++] = RDG_genChar(seed, lt); 149 } 150 } 151 } 152 153 154 void RDG_genBuffer(void* buffer, size_t size, double matchProba, double litProba, unsigned seed) 155 { 156 litDistribTable lt; 157 if (litProba==0.0) litProba = matchProba / 4.5; 158 RDG_fillLiteralDistrib(lt, litProba); 159 RDG_genBlock(buffer, size, 0, matchProba, lt, &seed); 160 } 161 162 163 #define RDG_BLOCKSIZE (128 KB) 164 void RDG_genOut(unsigned long long size, double matchProba, double litProba, unsigned seed) 165 { 166 BYTE buff[RDG_DICTSIZE + RDG_BLOCKSIZE]; 167 U64 total = 0; 168 size_t genBlockSize = RDG_BLOCKSIZE; 169 litDistribTable lt; 170 171 /* init */ 172 if (litProba==0.0) litProba = matchProba / 4.5; 173 RDG_fillLiteralDistrib(lt, litProba); 174 SET_BINARY_MODE(stdout); 175 176 /* Generate dict */ 177 RDG_genBlock(buff, RDG_DICTSIZE, 0, matchProba, lt, &seed); 178 179 /* Generate compressible data */ 180 while (total < size) 181 { 182 RDG_genBlock(buff, RDG_DICTSIZE+RDG_BLOCKSIZE, RDG_DICTSIZE, matchProba, lt, &seed); 183 if (size-total < RDG_BLOCKSIZE) genBlockSize = (size_t)(size-total); 184 total += genBlockSize; 185 fwrite(buff, 1, genBlockSize, stdout); 186 /* update dict */ 187 memcpy(buff, buff + RDG_BLOCKSIZE, RDG_DICTSIZE); 188 } 189 } 190