1 /*
2 Fuzzer.c
3 Automated test program for FSE
4 Copyright (C) Yann Collet 2013-2015
5
6 GPL v2 License
7
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License along
19 with this program; if not, write to the Free Software Foundation, Inc.,
20 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21
22 You can contact the author at :
23 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
24 - Public forum : https://groups.google.com/forum/#!forum/lz4c
25 */
26
27
28 /******************************
29 * Compiler options
30 ******************************/
31 #define _CRT_SECURE_NO_WARNINGS /* Visual warning */
32
33
34 /******************************
35 * Include
36 *******************************/
37 #include <stdlib.h> /* malloc, abs */
38 #include <stdio.h> /* printf */
39 #include <string.h> /* memset */
40 #include <sys/timeb.h> /* timeb */
41 #include "mem.h"
42 #include "hist.h"
43 #define FSE_STATIC_LINKING_ONLY
44 #include "fse.h"
45 #include "xxhash.h"
46
47
48 /***************************************************
49 * Constants
50 ***************************************************/
51 #define KB *(1<<10)
52 #define MB *(1<<20)
53 #define BUFFERSIZE ((1 MB) - 1)
54 #define FUZ_NB_TESTS (128 KB)
55 #define PROBATABLESIZE (4 KB)
56 #define FUZ_UPDATERATE 200
57 #define PRIME1 2654435761U
58 #define PRIME2 2246822519U
59
60
61 /***************************************************
62 * Macros
63 ***************************************************/
64 #define DISPLAY(...) fprintf(stderr, __VA_ARGS__)
65 #define DISPLAYLEVEL(l, ...) if (displayLevel>=l) { DISPLAY(__VA_ARGS__); }
66 static unsigned displayLevel = 2; // 0 : no display // 1: errors // 2 : + result + interaction + warnings ; // 3 : + progression; // 4 : + information
67
68
69 /***************************************************
70 * local functions
71 ***************************************************/
FUZ_GetMilliStart(void)72 static int FUZ_GetMilliStart(void)
73 {
74 struct timeb tb;
75 int nCount;
76 ftime ( &tb );
77 nCount = (int) (tb.millitm + (tb.time & 0xfffff) * 1000);
78 return nCount;
79 }
80
81
FUZ_GetMilliSpan(int nTimeStart)82 static int FUZ_GetMilliSpan ( int nTimeStart )
83 {
84 int nSpan = FUZ_GetMilliStart() - nTimeStart;
85 if ( nSpan < 0 )
86 nSpan += 0x100000 * 1000;
87 return nSpan;
88 }
89
90
FUZ_rand(unsigned * src)91 static unsigned FUZ_rand (unsigned* src)
92 {
93 *src = ( (*src) * PRIME1) + PRIME2;
94 return (*src) >> 11;
95 }
96
97
generate(void * buffer,size_t buffSize,double p,U32 * seed)98 static void generate (void* buffer, size_t buffSize, double p, U32* seed)
99 {
100 char table[PROBATABLESIZE] = {0};
101 int remaining = PROBATABLESIZE;
102 int pos = 0;
103 int s = 0;
104 char* op = (char*) buffer;
105 char* oend = op + buffSize;
106
107 /* Build Table */
108 while (remaining)
109 {
110 int n = (int) (remaining * p);
111 int end;
112 if (!n) n=1;
113 end = pos + n;
114 while (pos<end) table[pos++]= (char) s;
115 s++;
116 remaining -= n;
117 }
118
119 /* Fill buffer */
120 while (op<oend)
121 {
122 const int r = FUZ_rand (seed) & (PROBATABLESIZE-1);
123 *op++ = table[r];
124 }
125 }
126
127
generateNoise(void * buffer,size_t buffSize,U32 * seed)128 static void generateNoise (void* buffer, size_t buffSize, U32* seed)
129 {
130 BYTE* op = (BYTE*)buffer;
131 BYTE* const oend = op + buffSize;
132 while (op<oend) *op++ = (BYTE)FUZ_rand(seed);
133 }
134
135
FUZ_checkCount(short * normalizedCount,int tableLog,int maxSV)136 static int FUZ_checkCount (short* normalizedCount, int tableLog, int maxSV)
137 {
138 int total = 1<<tableLog;
139 int count = 0;
140 int i;
141 if (tableLog > 20) return -1;
142 for (i=0; i<=maxSV; i++)
143 count += abs(normalizedCount[i]);
144 if (count != total) return -1;
145 return 0;
146 }
147
148
149 #define CHECK(cond, ...) if (cond) { DISPLAY("Error => "); DISPLAY(__VA_ARGS__); \
150 DISPLAY(" (seed %u, test nb %u) \n", seed, testNb); exit(-1); }
151
FUZ_tests(U32 seed,U32 totalTest,U32 startTestNb)152 static void FUZ_tests (U32 seed, U32 totalTest, U32 startTestNb)
153 {
154 BYTE* bufferP0 = (BYTE*) malloc (BUFFERSIZE+64);
155 BYTE* bufferP1 = (BYTE*) malloc (BUFFERSIZE+64);
156 BYTE* bufferP15 = (BYTE*) malloc (BUFFERSIZE+64);
157 BYTE* bufferP90 = (BYTE*) malloc (BUFFERSIZE+64);
158 BYTE* bufferP100 = (BYTE*) malloc (BUFFERSIZE+64);
159 BYTE* bufferDst = (BYTE*) malloc (BUFFERSIZE+64);
160 BYTE* bufferVerif = (BYTE*) malloc (BUFFERSIZE+64);
161 size_t bufferDstSize = BUFFERSIZE+64;
162 unsigned testNb, maxSV, tableLog;
163 const size_t maxTestSizeMask = 0x1FFFF;
164 U32 rootSeed = seed;
165 U32 time = FUZ_GetMilliStart();
166
167 generateNoise (bufferP0, BUFFERSIZE, &rootSeed);
168 generate (bufferP1 , BUFFERSIZE, 0.01, &rootSeed);
169 generate (bufferP15 , BUFFERSIZE, 0.15, &rootSeed);
170 generate (bufferP90 , BUFFERSIZE, 0.90, &rootSeed);
171 memset(bufferP100, (BYTE)FUZ_rand(&rootSeed), BUFFERSIZE);
172
173 if (startTestNb)
174 {
175 U32 i;
176 for (i=0; i<startTestNb; i++)
177 FUZ_rand (&rootSeed);
178 }
179
180 for (testNb=startTestNb; testNb<totalTest; testNb++)
181 {
182 BYTE* bufferTest;
183 int tag=0;
184 U32 roundSeed = rootSeed ^ 0xEDA5B371;
185 FUZ_rand(&rootSeed);
186
187 DISPLAYLEVEL (4, "\r test %5u ", testNb);
188 if (FUZ_GetMilliSpan (time) > FUZ_UPDATERATE)
189 {
190 DISPLAY ("\r test %5u ", testNb);
191 time = FUZ_GetMilliStart();
192 }
193
194 /* Compression / Decompression tests */
195 {
196 /* determine test sample */
197 size_t sizeOrig = (FUZ_rand (&roundSeed) & maxTestSizeMask) + 1;
198 size_t offset = (FUZ_rand(&roundSeed) % (BUFFERSIZE - 64 - maxTestSizeMask));
199 size_t sizeCompressed;
200 U32 hashOrig;
201
202 if (FUZ_rand(&roundSeed) & 7) bufferTest = bufferP15 + offset;
203 else
204 {
205 switch(FUZ_rand(&roundSeed) & 3)
206 {
207 case 0: bufferTest = bufferP0 + offset; break;
208 case 1: bufferTest = bufferP1 + offset; break;
209 case 2: bufferTest = bufferP90 + offset; break;
210 default : bufferTest = bufferP100 + offset; break;
211 }
212 }
213 DISPLAYLEVEL (4,"%3i ", tag++);;
214 hashOrig = XXH32 (bufferTest, sizeOrig, 0);
215
216 /* compress test */
217 sizeCompressed = FSE_compress (bufferDst, bufferDstSize, bufferTest, sizeOrig);
218 CHECK(FSE_isError(sizeCompressed), "Compression failed !");
219
220 if (sizeCompressed > 1) /* don't check uncompressed & rle corner cases */
221 {
222 /* failed compression test*/
223 {
224 size_t errorCode;
225 void* tooSmallDBuffer = malloc(sizeCompressed-1); /* overflows detected with Valgrind */
226 CHECK(tooSmallDBuffer==NULL, "Not enough memory for tooSmallDBuffer test");
227 errorCode = FSE_compress (tooSmallDBuffer, sizeCompressed-1, bufferTest, sizeOrig);
228 CHECK(errorCode!=0, "Compression should have failed : destination buffer too small");
229 free(tooSmallDBuffer);
230 }
231
232 /* decompression test */
233 {
234 U32 hashEnd;
235 BYTE saved = (bufferVerif[sizeOrig] = 254);
236 size_t result = FSE_decompress (bufferVerif, sizeOrig, bufferDst, sizeCompressed);
237 CHECK(bufferVerif[sizeOrig] != saved, "Output buffer overrun (bufferVerif) : write beyond specified end");
238 CHECK(FSE_isError(result), "Decompression failed");
239 hashEnd = XXH32 (bufferVerif, sizeOrig, 0);
240 CHECK(hashEnd != hashOrig, "Decompressed data corrupted");
241 }
242 }
243 }
244
245 /* Attempt header decoding on bogus data */
246 {
247 short count[256];
248 size_t result;
249 DISPLAYLEVEL (4,"\b\b\b\b%3i ", tag++);
250 maxSV = 255;
251 result = FSE_readNCount (count, &maxSV, &tableLog, bufferTest, FSE_NCOUNTBOUND);
252 if (!FSE_isError(result)) /* an error would be normal */
253 {
254 int checkCount;
255 CHECK(result > FSE_NCOUNTBOUND, "FSE_readHeader() reads too far (buffer overflow)");
256 CHECK(maxSV > 255, "count table overflow (%u)", maxSV+1);
257 checkCount = FUZ_checkCount(count, tableLog, maxSV);
258 CHECK(checkCount==-1, "symbol distribution corrupted");
259 }
260 }
261
262 /* Attempt decompression on bogus data */
263 {
264 size_t maxDstSize = FUZ_rand (&roundSeed) & maxTestSizeMask;
265 size_t sizeCompressed = FUZ_rand (&roundSeed) & maxTestSizeMask;
266 BYTE saved = (bufferDst[maxDstSize] = 253);
267 size_t result;
268 DISPLAYLEVEL (4,"\b\b\b\b%3i ", tag++);;
269 result = FSE_decompress (bufferDst, maxDstSize, bufferTest, sizeCompressed);
270 CHECK(!FSE_isError(result) && (result > maxDstSize), "Decompression overran output buffer");
271 CHECK(bufferDst[maxDstSize] != saved, "FSE_decompress on bogus data : bufferDst write overflow");
272 }
273 }
274
275 /* exit */
276 free (bufferP0);
277 free (bufferP1);
278 free (bufferP15);
279 free (bufferP90);
280 free (bufferP100);
281 free (bufferDst);
282 free (bufferVerif);
283 }
284
285
286 /*****************************************************************
287 * Unitary tests
288 *****************************************************************/
289 extern int FSE_countU16(unsigned* count, const unsigned short* source, unsigned sourceSize, unsigned* maxSymbolValuePtr);
290
291 #define TBSIZE (16 KB)
unitTest(void)292 static void unitTest(void)
293 {
294 BYTE* testBuff = (BYTE*)malloc(TBSIZE);
295 BYTE* cBuff = (BYTE*)malloc(FSE_COMPRESSBOUND(TBSIZE));
296 BYTE* verifBuff = (BYTE*)malloc(TBSIZE);
297 size_t errorCode;
298 U32 seed=0, testNb=0, lseed=0;
299 U32 count[256];
300
301 if ((!testBuff) || (!cBuff) || (!verifBuff))
302 {
303 DISPLAY("Not enough memory, exiting ... \n");
304 free(testBuff);
305 free(cBuff);
306 free(verifBuff);
307 return;
308 }
309
310 /* HIST_count */
311 { U32 max, i;
312 for (i=0; i< TBSIZE; i++) testBuff[i] = (FUZ_rand(&lseed) & 63) + '0';
313 max = '0' + 63;
314 errorCode = HIST_count(count, &max, testBuff, TBSIZE);
315 CHECK(FSE_isError(errorCode), "Error : FSE_count() should have worked");
316 max -= 1;
317 errorCode = HIST_count(count, &max, testBuff, TBSIZE);
318 CHECK(!FSE_isError(errorCode), "Error : FSE_count() should have failed : value > max");
319 max = 65000;
320 errorCode = HIST_count(count, &max, testBuff, TBSIZE);
321 CHECK(FSE_isError(errorCode), "Error : FSE_count() should have worked");
322 }
323
324 /* FSE_optimalTableLog */
325 { U32 max, i, tableLog=12;
326 size_t testSize = 999;
327 for (i=0; i< testSize; i++) testBuff[i] = (BYTE)FUZ_rand(&lseed);
328 max = 256;
329 HIST_count(count, &max, testBuff, testSize);
330 tableLog = FSE_optimalTableLog(tableLog, testSize, max);
331 CHECK(tableLog<=8, "Too small tableLog");
332 }
333
334 /* FSE_normalizeCount */
335 {
336 S16 norm[256];
337 U32 max = 256;
338 HIST_count(count, &max, testBuff, TBSIZE);
339 errorCode = FSE_normalizeCount(norm, 10, count, TBSIZE, max);
340 CHECK(FSE_isError(errorCode), "Error : FSE_normalizeCount() should have worked");
341 errorCode = FSE_normalizeCount(norm, 8, count, TBSIZE, 256);
342 CHECK(!FSE_isError(errorCode), "Error : FSE_normalizeCount() should have failed (max >= 1<<tableLog)");
343 /* limit corner case : try to make internal rank overflow */
344 {
345 U32 i;
346 U32 total = 0;
347 count[0] = 940;
348 count[1] = 910;
349 count[2] = 470;
350 count[3] = 190;
351 count[4] = 90;
352 for(i=5; i<=255; i++) count[i] = 6;
353 for (i=0; i<=255; i++) total += count[i];
354 errorCode = FSE_normalizeCount(norm, 10, count, total, 255);
355 CHECK(FSE_isError(errorCode), "Error : FSE_normalizeCount() should have worked");
356 count[0] = 300;
357 count[1] = 300;
358 count[2] = 300;
359 count[3] = 300;
360 count[4] = 50;
361 for(i=5; i<=80; i++) count[i] = 4;
362 total = 0; for (i=0; i<=80; i++) total += count[i];
363 errorCode = FSE_normalizeCount(norm, 10, count, total, 80);
364 CHECK(FSE_isError(errorCode), "Error : FSE_normalizeCount() should have worked");
365 }
366 /* corner case : try to make normalizeM2 divide by 0 */
367 {
368 U32 i = 0;
369 for (i = 0; i < 22; i++) count[i] = 0;
370 for (; i < 44; i++) count[i] = 1;
371 errorCode = FSE_normalizeCount(norm, 5, count, 22, 43);
372 CHECK(FSE_isError(errorCode), "Error : FSE_normalizeCount() should have worked");
373 }
374 }
375
376 /* FSE_writeNCount, FSE_readNCount */
377 {
378 #define MAXNCOUNTSIZE 513
379 S16 norm[129];
380 BYTE header[513];
381 U32 max, tableLog, i;
382 size_t headerSize;
383
384 for (i=0; i< TBSIZE; i++) testBuff[i] = i % 127;
385 max = 128;
386 errorCode = HIST_count(count, &max, testBuff, TBSIZE);
387 CHECK(FSE_isError(errorCode), "Error : FSE_count() should have worked");
388 tableLog = FSE_optimalTableLog(0, TBSIZE, max);
389 errorCode = FSE_normalizeCount(norm, tableLog, count, TBSIZE, max);
390 CHECK(FSE_isError(errorCode), "Error : FSE_normalizeCount() should have worked");
391
392 headerSize = FSE_NCountWriteBound(max, tableLog);
393 CHECK(headerSize > MAXNCOUNTSIZE, "Error : not enough memory for NCount");
394
395 headerSize = FSE_writeNCount(header, headerSize, norm, max, tableLog);
396 CHECK(FSE_isError(headerSize), "Error : FSE_writeNCount() should have worked");
397
398 header[headerSize-1] = 0;
399 errorCode = FSE_writeNCount(header, headerSize-1, norm, max, tableLog);
400 CHECK(!FSE_isError(errorCode), "Error : FSE_writeNCount() should have failed");
401 CHECK (header[headerSize-1] != 0, "Error : FSE_writeNCount() buffer overwrite");
402
403 errorCode = FSE_writeNCount(header, headerSize+1, norm, max, tableLog);
404 CHECK(FSE_isError(errorCode), "Error : FSE_writeNCount() should have worked");
405
406 { unsigned maxN = 128;
407 size_t const err = FSE_readNCount(norm, &maxN, &tableLog, header, headerSize);
408 CHECK(FSE_isError(err), "Error : FSE_readNCount() should have worked : (error %s)", FSE_getErrorName(err));
409 }
410
411 max = 64;
412 errorCode = FSE_readNCount(norm, &max, &tableLog, header, headerSize);
413 CHECK(!FSE_isError(errorCode), "Error : FSE_readNCount() should have failed (max too small)");
414
415 max = 128;
416 errorCode = FSE_readNCount(norm, &max, &tableLog, header, headerSize-1);
417 CHECK(!FSE_isError(errorCode), "Error : FSE_readNCount() should have failed (size too small)");
418
419 {
420 void* smallBuffer = malloc(headerSize-1); /* outbound read can be caught by valgrind */
421 CHECK(smallBuffer==NULL, "Error : Not enough memory (FSE_readNCount unit test)");
422 memcpy(smallBuffer, header, headerSize-1);
423 max = 129;
424 errorCode = FSE_readNCount(norm, &max, &tableLog, smallBuffer, headerSize-1);
425 CHECK(!FSE_isError(errorCode), "Error : FSE_readNCount() should have failed (size too small)");
426 free(smallBuffer);
427 }
428 }
429
430
431 /* FSE_buildCTable_raw & FSE_buildDTable_raw */
432 {
433 U32 ct[FSE_CTABLE_SIZE_U32(8, 256)];
434 U32 dt[FSE_DTABLE_SIZE_U32(8)];
435 U64 crcOrig, crcVerif;
436 size_t cSize, verifSize;
437
438 U32 i;
439 for (i=0; i< TBSIZE; i++) testBuff[i] = (FUZ_rand(&seed) & 63) + '0';
440 crcOrig = XXH64(testBuff, TBSIZE, 0);
441
442 errorCode = FSE_buildCTable_raw(ct, 8);
443 CHECK(FSE_isError(errorCode), "FSE_buildCTable_raw should have worked");
444 errorCode = FSE_buildDTable_raw(dt, 8);
445 CHECK(FSE_isError(errorCode), "FSE_buildDTable_raw should have worked");
446
447 cSize = FSE_compress_usingCTable(cBuff, FSE_COMPRESSBOUND(TBSIZE), testBuff, TBSIZE, ct);
448 CHECK(FSE_isError(cSize), "FSE_compress_usingCTable should have worked using raw CTable");
449
450 verifSize = FSE_decompress_usingDTable(verifBuff, TBSIZE, cBuff, cSize, dt);
451 CHECK(FSE_isError(verifSize), "FSE_decompress_usingDTable should have worked using raw DTable");
452
453 crcVerif = XXH64(verifBuff, verifSize, 0);
454 CHECK(crcOrig != crcVerif, "Raw regenerated data is corrupted");
455 }
456
457 /* known corner case */
458 {
459 BYTE sample8[8] = { 0, 0, 0, 2, 0, 0, 0, 0 };
460 BYTE* rBuff;
461 errorCode = FSE_compress(cBuff, TBSIZE, sample8, 8);
462 CHECK(FSE_isError(errorCode), "FSE_compress failed compressing sample8");
463 rBuff = (BYTE*)malloc(errorCode); /* in order to catch read overflow with Valgrind */
464 CHECK(rBuff==NULL, "Not enough memory for rBuff");
465 memcpy(rBuff, cBuff, errorCode);
466 errorCode = FSE_decompress(verifBuff, sizeof(sample8), rBuff, errorCode);
467 CHECK(errorCode != sizeof(sample8), "FSE_decompress failed regenerating sample8");
468 free(rBuff);
469 }
470
471 free(testBuff);
472 free(cBuff);
473 free(verifBuff);
474 DISPLAY("Unit tests completed\n");
475 }
476
477
478 /*****************************************************************
479 * Command line
480 *****************************************************************/
481
badUsage(const char * exename)482 int badUsage(const char* exename)
483 {
484 (void) exename;
485 DISPLAY("wrong parameter\n");
486 return 1;
487 }
488
489
main(int argc,char ** argv)490 int main (int argc, char** argv)
491 {
492 U32 seed, startTestNb=0, pause=0, totalTest = FUZ_NB_TESTS;
493 int argNb;
494
495 seed = FUZ_GetMilliStart() % 10000;
496 DISPLAYLEVEL (1, "FSE (%2i bits) automated test\n", (int)sizeof(void*)*8);
497 for (argNb=1; argNb<argc; argNb++)
498 {
499 char* argument = argv[argNb];
500 if (argument[0]=='-')
501 {
502 argument++;
503 while (argument[0]!=0)
504 {
505 switch (argument[0])
506 {
507 /* seed setting */
508 case 's':
509 argument++;
510 seed=0;
511 while ((*argument>='0') && (*argument<='9'))
512 {
513 seed *= 10;
514 seed += *argument - '0';
515 argument++;
516 }
517 break;
518
519 /* total tests */
520 case 'i':
521 argument++;
522 totalTest=0;
523 while ((*argument>='0') && (*argument<='9'))
524 {
525 totalTest *= 10;
526 totalTest += *argument - '0';
527 argument++;
528 }
529 break;
530
531 /* jump to test nb */
532 case 't':
533 argument++;
534 startTestNb=0;
535 while ((*argument>='0') && (*argument<='9'))
536 {
537 startTestNb *= 10;
538 startTestNb += *argument - '0';
539 argument++;
540 }
541 break;
542
543 /* verbose mode */
544 case 'v':
545 argument++;
546 displayLevel=4;
547 break;
548
549 /* pause (hidden) */
550 case 'p':
551 argument++;
552 pause=1;
553 break;
554
555 default:
556 return badUsage(argv[0]);
557 }
558 }
559 }
560 }
561
562 if (startTestNb == 0) unitTest();
563
564 DISPLAY("Fuzzer seed : %u \n", seed);
565 FUZ_tests (seed, totalTest, startTestNb);
566
567 DISPLAY ("\rAll %u tests passed \n", totalTest);
568 if (pause)
569 {
570 int unused;
571 DISPLAY("press enter ...\n");
572 unused = getchar();
573 (void)unused;
574 }
575 return 0;
576 }
577