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