silo/third-party/lz4/fuzzer.c

   1 /*\r
   2     fuzzer.c - Fuzzer test tool for LZ4\r
   3     Copyright (C) Yann Collet - Andrew Mahone 2012-2013\r
   4     Code started by Andrew Mahone, modified by Yann Collet\r
   5     GPL v2 License\r
   6 \r
   7     This program is free software; you can redistribute it and/or modify\r
   8     it under the terms of the GNU General Public License as published by\r
   9     the Free Software Foundation; either version 2 of the License, or\r
  10     (at your option) any later version.\r
  11 \r
  12     This program is distributed in the hope that it will be useful,\r
  13     but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  14     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  15     GNU General Public License for more details.\r
  16 \r
  17     You should have received a copy of the GNU General Public License along\r
  18     with this program; if not, write to the Free Software Foundation, Inc.,\r
  19     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.\r
  20 \r
  21     You can contact the author at :\r
  22     - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html\r
  23     - LZ4 source repository : http://code.google.com/p/lz4/\r
  24 */\r
  25 \r
  26 //**************************************\r
  27 // Remove Visual warning messages\r
  28 //**************************************\r
  29 #define _CRT_SECURE_NO_WARNINGS  // fgets\r
  30 \r
  31 \r
  32 //**************************************\r
  33 // Includes\r
  34 //**************************************\r
  35 #include <stdlib.h>\r
  36 #include <stdio.h>      // fgets, sscanf\r
  37 #include <sys/timeb.h>  // timeb\r
  38 #include "lz4.h"\r
  39 #include "lz4hc.h"\r
  40 \r
  41 \r
  42 //**************************************\r
  43 // Constants\r
  44 //**************************************\r
  45 #define NB_ATTEMPTS (1<<17)\r
  46 #define LEN ((1<<15))\r
  47 #define SEQ_POW 2\r
  48 #define NUM_SEQ (1 << SEQ_POW)\r
  49 #define SEQ_MSK ((NUM_SEQ) - 1)\r
  50 #define MOD_SEQ(x) ((((x) >> 8) & 255) == 0)\r
  51 #define NEW_SEQ(x) ((((x) >> 10) %10) == 0)\r
  52 #define PAGE_SIZE 4096\r
  53 #define ROUND_PAGE(x) (((x) + PAGE_SIZE - 1) & ~(PAGE_SIZE - 1))\r
  54 #define PRIME1   2654435761U\r
  55 #define PRIME2   2246822519U\r
  56 #define PRIME3   3266489917U\r
  57 \r
  58 \r
  59 //*********************************************************\r
  60 //  Functions\r
  61 //*********************************************************\r
  62 static int FUZ_GetMilliStart()\r
  63 {\r
  64    struct timeb tb;\r
  65    int nCount;\r
  66    ftime( &tb );\r
  67    nCount = (int) (tb.millitm + (tb.time & 0xfffff) * 1000);\r
  68    return nCount;\r
  69 }\r
  70 \r
  71 \r
  72 static int FUZ_GetMilliSpan( int nTimeStart )\r
  73 {\r
  74    int nSpan = FUZ_GetMilliStart() - nTimeStart;\r
  75    if ( nSpan < 0 )\r
  76       nSpan += 0x100000 * 1000;\r
  77    return nSpan;\r
  78 }\r
  79 \r
  80 \r
  81 unsigned int FUZ_rand(unsigned int* src)\r
  82 {\r
  83     *src =  ((*src) * PRIME1) + PRIME2;\r
  84     return *src;\r
  85 }\r
  86 \r
  87 \r
  88 int test_canary(unsigned char *buf)\r
  89 {\r
  90     int i;\r
  91     for (i = 0; i < 2048; i++)\r
  92         if (buf[i] != buf[i + 2048])\r
  93             return 0;\r
  94     return 1;\r
  95 }\r
  96 \r
  97 \r
  98 int FUZ_SecurityTest()\r
  99 {\r
 100   char* output;\r
 101   char* input;\r
 102   int i, r;\r
 103 \r
 104   printf("Overflow test (issue 52)...");\r
 105   input = (char*) malloc (20<<20);\r
 106   output = (char*) malloc (20<<20);\r
 107   input[0] = 0x0F;\r
 108   input[1] = 0x00;\r
 109   input[2] = 0x00;\r
 110   for(i = 3; i < 16840000; i++)\r
 111     input[i] = 0xff;\r
 112   r = LZ4_decompress_fast(input, output, 20<<20);\r
 113 \r
 114   free(input);\r
 115   free(output);\r
 116   printf(" Passed (return = %i < 0)\n",r);\r
 117   return 0;\r
 118 }\r
 119 \r
 120 \r
 121 //int main(int argc, char *argv[]) {\r
 122 int main() {\r
 123         unsigned long long bytes = 0;\r
 124         unsigned long long cbytes = 0;\r
 125         unsigned long long hcbytes = 0;\r
 126         unsigned char buf[LEN];\r
 127         unsigned char testOut[LEN+1];\r
 128 #       define FUZ_max   LZ4_COMPRESSBOUND(LEN)\r
 129 #       define FUZ_avail ROUND_PAGE(FUZ_max)\r
 130         const int off_full = FUZ_avail - FUZ_max;\r
 131         unsigned char cbuf[FUZ_avail + PAGE_SIZE];\r
 132         unsigned int seed, randState, cur_seq=PRIME3, seeds[NUM_SEQ], timestamp=FUZ_GetMilliStart();\r
 133         int i, j, k, ret, len, lenHC, attemptNb;\r
 134         char userInput[30] = {0};\r
 135 #       define FUZ_CHECKTEST(cond, message) testNb++; if (cond) { printf("Test %i : %s : seed %u, cycle %u \n", testNb, message, seed, attemptNb); goto _output_error; }\r
 136 \r
 137         printf("starting LZ4 fuzzer\n");\r
 138         printf("Select an Initialisation number (default : random) : ");\r
 139         fflush(stdout);\r
 140         if ( fgets(userInput, sizeof userInput, stdin) )\r
 141         {\r
 142             if ( sscanf(userInput, "%d", &seed) == 1 ) {}\r
 143             else seed = FUZ_GetMilliSpan(timestamp);\r
 144         }\r
 145         printf("Seed = %u\n", seed);\r
 146         randState = seed;\r
 147 \r
 148         FUZ_SecurityTest();\r
 149 \r
 150         for (i = 0; i < 2048; i++)\r
 151                 cbuf[FUZ_avail + i] = cbuf[FUZ_avail + 2048 + i] = FUZ_rand(&randState) >> 16;\r
 152 \r
 153         for (attemptNb = 0; attemptNb < NB_ATTEMPTS; attemptNb++) \r
 154         {\r
 155             int testNb = 0;\r
 156 \r
 157             printf("\r%7i /%7i\r", attemptNb, NB_ATTEMPTS);\r
 158             \r
 159             for (j = 0; j < NUM_SEQ; j++) {\r
 160                     seeds[j] = FUZ_rand(&randState) << 8;\r
 161                     seeds[j] ^= (FUZ_rand(&randState) >> 8) & 65535;\r
 162             }\r
 163             for (j = 0; j < LEN; j++) {\r
 164                     k = FUZ_rand(&randState);\r
 165                     if (j == 0 || NEW_SEQ(k))\r
 166                             cur_seq = seeds[(FUZ_rand(&randState) >> 16) & SEQ_MSK];\r
 167                     if (MOD_SEQ(k)) {\r
 168                             k = (FUZ_rand(&randState) >> 16) & SEQ_MSK;\r
 169                             seeds[k] = FUZ_rand(&randState) << 8;\r
 170                             seeds[k] ^= (FUZ_rand(&randState) >> 8) & 65535;\r
 171                     }\r
 172                     buf[j] = FUZ_rand(&cur_seq) >> 16;\r
 173             }\r
 174 \r
 175             // Test compression HC\r
 176             ret = LZ4_compressHC_limitedOutput((const char*)buf, (char*)&cbuf[off_full], LEN, FUZ_max);\r
 177             FUZ_CHECKTEST(ret==0, "HC compression failed despite sufficient space");\r
 178             lenHC = ret;\r
 179 \r
 180             // Test compression\r
 181             ret = LZ4_compress_limitedOutput((const char*)buf, (char*)&cbuf[off_full], LEN, FUZ_max);\r
 182             FUZ_CHECKTEST(ret==0, "compression failed despite sufficient space");\r
 183             len = ret;\r
 184 \r
 185             // Test decoding with output size being exactly what's necessary => must work\r
 186             ret = LZ4_decompress_fast((char*)&cbuf[off_full], (char*)testOut, LEN);\r
 187             FUZ_CHECKTEST(ret<0, "decompression failed despite correct space");\r
 188 \r
 189             // Test decoding with one byte missing => must fail\r
 190             ret = LZ4_decompress_fast((char*)&cbuf[off_full], (char*)testOut, LEN-1);\r
 191             FUZ_CHECKTEST(ret>=0, "decompression should have failed, due to Output Size being too small");\r
 192 \r
 193             // Test decoding with one byte too much => must fail\r
 194             ret = LZ4_decompress_fast((char*)&cbuf[off_full], (char*)testOut, LEN+1);\r
 195             FUZ_CHECKTEST(ret>=0, "decompression should have failed, due to Output Size being too large");\r
 196 \r
 197             // Test decoding with enough output size => must work\r
 198             ret = LZ4_decompress_safe((char*)&cbuf[off_full], (char*)testOut, len, LEN+1);\r
 199             FUZ_CHECKTEST(ret<0, "decompression failed despite sufficient space");\r
 200 \r
 201             // Test decoding with output size being exactly what's necessary => must work\r
 202             ret = LZ4_decompress_safe((char*)&cbuf[off_full], (char*)testOut, len, LEN);\r
 203             FUZ_CHECKTEST(ret<0, "decompression failed despite sufficient space");\r
 204 \r
 205             // Test decoding with output size being one byte too short => must fail\r
 206             ret = LZ4_decompress_safe((char*)&cbuf[off_full], (char*)testOut, len, LEN-1);\r
 207             FUZ_CHECKTEST(ret>=0, "LZ4_decompress_safe should have failed, due to Output Size being one byte too short");\r
 208 \r
 209             // Test decoding with input size being one byte too short => must fail\r
 210             ret = LZ4_decompress_safe((char*)&cbuf[off_full], (char*)testOut, len-1, LEN);\r
 211             FUZ_CHECKTEST(ret>=0, "LZ4_decompress_safe should have failed, due to input size being one byte too short");\r
 212 \r
 213             // Test decoding with input size being one byte too large => must fail\r
 214             ret = LZ4_decompress_safe((char*)&cbuf[off_full], (char*)testOut, len+1, LEN);\r
 215             FUZ_CHECKTEST(ret>=0, "decompression should have failed, due to input size being too large");\r
 216             //if (ret>=0) { printf("Test 10 : decompression should have failed, due to input size being too large : seed %u, len %d\n", seed, LEN); goto _output_error; }\r
 217 \r
 218             // Test partial decoding with target output size being max/2 => must work\r
 219             ret = LZ4_decompress_safe_partial((char*)&cbuf[off_full], (char*)testOut, len, LEN/2, LEN);\r
 220             FUZ_CHECKTEST(ret<0, "partial decompression failed despite sufficient space");\r
 221 \r
 222             // Test partial decoding with target output size being just below max => must work\r
 223             ret = LZ4_decompress_safe_partial((char*)&cbuf[off_full], (char*)testOut, len, LEN-3, LEN);\r
 224             FUZ_CHECKTEST(ret<0, "partial decompression failed despite sufficient space");\r
 225 \r
 226             // Test compression with output size being exactly what's necessary (should work)\r
 227             ret = LZ4_compress_limitedOutput((const char*)buf, (char*)&cbuf[FUZ_avail-len], LEN, len);\r
 228             FUZ_CHECKTEST(!test_canary(&cbuf[FUZ_avail]), "compression overran output buffer");\r
 229             FUZ_CHECKTEST(ret==0, "compression failed despite sufficient space");\r
 230 \r
 231             // Test HC compression with output size being exactly what's necessary (should work)\r
 232             ret = LZ4_compressHC_limitedOutput((const char*)buf, (char*)&cbuf[FUZ_avail-len], LEN, lenHC);\r
 233             FUZ_CHECKTEST(ret==0, "HC compression failed despite sufficient space");\r
 234 \r
 235             // Test compression with just one missing byte into output buffer => must fail\r
 236             ret = LZ4_compress_limitedOutput((const char*)buf, (char*)&cbuf[FUZ_avail-(len-1)], LEN, len-1);\r
 237             FUZ_CHECKTEST(ret, "compression overran output buffer");\r
 238             FUZ_CHECKTEST(!test_canary(&cbuf[FUZ_avail]), "compression overran output buffer");\r
 239 \r
 240             // Test HC compression with just one missing byte into output buffer => must fail\r
 241             ret = LZ4_compressHC_limitedOutput((const char*)buf, (char*)&cbuf[FUZ_avail-(len-1)], LEN, lenHC-1);\r
 242             FUZ_CHECKTEST(ret, "HC compression overran output buffer");\r
 243 \r
 244             bytes += LEN;\r
 245             cbytes += len;\r
 246             hcbytes += lenHC;\r
 247             FUZ_rand(&randState);\r
 248         }\r
 249 \r
 250         printf("all tests completed successfully \n");\r
 251         printf("compression ratio: %0.3f%%\n", (double)cbytes/bytes*100);\r
 252         printf("HC compression ratio: %0.3f%%\n", (double)hcbytes/bytes*100);\r
 253         getchar();\r
 254         return 0;\r
 255 \r
 256 _output_error:\r
 257         getchar();\r
 258         return 1;\r
 259 }\r