CMSIS2000  0.0.7
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
fuzzer.c
Go to the documentation of this file.
1 /*
2  fuzzer.c - Fuzzer test tool for LZ4
3  Copyright (C) Andrew Mahone - Yann Collet 2012
4  Original code by Andrew Mahone / Modified by Yann Collet
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 homepage : http://fastcompression.blogspot.com/p/lz4.html
23  - LZ4 source repository : http://code.google.com/p/lz4/
24 */
25 
26 //**************************************
27 // Remove Visual warning messages
28 //**************************************
29 #define _CRT_SECURE_NO_WARNINGS // fgets
30 
31 
32 //**************************************
33 // Includes
34 //**************************************
35 #include <stdlib.h>
36 #include <stdio.h> // fgets, sscanf
37 #include <sys/timeb.h> // timeb
38 #include "lz4.h"
39 
40 
41 //**************************************
42 // Constants
43 //**************************************
44 #define NB_ATTEMPTS (1<<18)
45 #define LEN ((1<<15))
46 #define SEQ_POW 2
47 #define NUM_SEQ (1 << SEQ_POW)
48 #define SEQ_MSK ((NUM_SEQ) - 1)
49 #define MOD_SEQ(x) ((((x) >> 8) & 255) == 0)
50 #define NEW_SEQ(x) ((((x) >> 10) %10) == 0)
51 #define PAGE_SIZE 4096
52 #define ROUND_PAGE(x) (((x) + PAGE_SIZE - 1) & ~(PAGE_SIZE - 1))
53 #define PRIME1 2654435761U
54 #define PRIME2 2246822519U
55 #define PRIME3 3266489917U
56 
57 
58 
59 //*********************************************************
60 // Functions
61 //*********************************************************
62 static int FUZ_GetMilliStart()
63 {
64  struct timeb tb;
65  int nCount;
66  ftime( &tb );
67  nCount = (int) (tb.millitm + (tb.time & 0xfffff) * 1000);
68  return nCount;
69 }
70 
71 static int FUZ_GetMilliSpan( int nTimeStart )
72 {
73  int nSpan = FUZ_GetMilliStart() - nTimeStart;
74  if ( nSpan < 0 )
75  nSpan += 0x100000 * 1000;
76  return nSpan;
77 }
78 
79 
80 unsigned int FUZ_rand(unsigned int* src)
81 {
82  *src = ((*src) * PRIME1) + PRIME2;
83  return *src;
84 }
85 
86 
87 int test_canary(unsigned char *buf) {
88  int i;
89  for (i = 0; i < 2048; i++)
90  if (buf[i] != buf[i + 2048])
91  return 0;
92  return 1;
93 }
94 
95 int FUZ_SecurityTest()
96 {
97  char* output;
98  char* input;
99  int i, r;
100 
101  printf("Starting security tests...");
102  input = (char*) malloc (20<<20);
103  output = (char*) malloc (20<<20);
104  input[0] = 0x0F;
105  input[1] = 0x00;
106  input[2] = 0x00;
107  for(i = 3; i < 16840000; i++)
108  input[i] = 0xff;
109  r = LZ4_uncompress(input, output, 20<<20);
110 
111  free(input);
112  free(output);
113  printf(" Completed (r=%i)\n",r);
114  return 0;
115 }
116 
117 
118 //int main(int argc, char *argv[]) {
119 int main() {
120  unsigned long long bytes = 0;
121  unsigned long long cbytes = 0;
122  unsigned char buf[LEN];
123  unsigned char testOut[LEN+1];
124 # define FUZ_max LZ4_COMPRESSBOUND(LEN)
125 # define FUZ_avail ROUND_PAGE(FUZ_max)
126  const int off_full = FUZ_avail - FUZ_max;
127  unsigned char cbuf[FUZ_avail + PAGE_SIZE];
128  unsigned int seed, cur_seq=PRIME3, seeds[NUM_SEQ], timestamp=FUZ_GetMilliStart();
129  int i, j, k, ret, len;
130  char userInput[30] = {0};
131 
132  printf("starting LZ4 fuzzer\n");
133  printf("Select an Initialisation number (default : random) : ");
134  fflush(stdout);
135  if ( fgets(userInput, sizeof userInput, stdin) )
136  {
137  if ( sscanf(userInput, "%d", &seed) == 1 ) {}
138  else seed = FUZ_GetMilliSpan(timestamp);
139  }
140  printf("Seed = %u\n", seed);
141 
142  FUZ_SecurityTest();
143 
144  for (i = 0; i < 2048; i++)
145  cbuf[FUZ_avail + i] = cbuf[FUZ_avail + 2048 + i] = FUZ_rand(&seed) >> 16;
146 
147  for (i = 0; i < NB_ATTEMPTS; i++)
148  {
149  printf("\r%7i /%7i\r", i, NB_ATTEMPTS);
150 
151  FUZ_rand(&seed);
152  for (j = 0; j < NUM_SEQ; j++) {
153  seeds[j] = FUZ_rand(&seed) << 8;
154  seeds[j] ^= (FUZ_rand(&seed) >> 8) & 65535;
155  }
156  for (j = 0; j < LEN; j++) {
157  k = FUZ_rand(&seed);
158  if (j == 0 || NEW_SEQ(k))
159  cur_seq = seeds[(FUZ_rand(&seed) >> 16) & SEQ_MSK];
160  if (MOD_SEQ(k)) {
161  k = (FUZ_rand(&seed) >> 16) & SEQ_MSK;
162  seeds[k] = FUZ_rand(&seed) << 8;
163  seeds[k] ^= (FUZ_rand(&seed) >> 8) & 65535;
164  }
165  buf[j] = FUZ_rand(&cur_seq) >> 16;
166  }
167 
168  // Test compression
169  ret = LZ4_compress_limitedOutput((const char*)buf, (char*)&cbuf[off_full], LEN, FUZ_max);
170  if (ret == 0) { printf("compression failed despite sufficient space: seed %u, len %d\n", seed, LEN); goto _output_error; }
171  len = ret;
172 
173  // Test decoding with output size being exactly what's necessary => must work
174  ret = LZ4_uncompress((char*)&cbuf[off_full], (char*)testOut, LEN);
175  if (ret<0) { printf("decompression failed despite correct space: seed %u, len %d\n", seed, LEN); goto _output_error; }
176 
177  // Test decoding with one byte missing => must fail
178  ret = LZ4_uncompress((char*)&cbuf[off_full], (char*)testOut, LEN-1);
179  if (ret>=0) { printf("decompression should have failed, due to Output Size being too small : seed %u, len %d\n", seed, LEN); goto _output_error; }
180 
181  // Test decoding with one byte too much => must fail
182  ret = LZ4_uncompress((char*)&cbuf[off_full], (char*)testOut, LEN+1);
183  if (ret>=0) { printf("decompression should have failed, due to Output Size being too large : seed %u, len %d\n", seed, LEN); goto _output_error; }
184 
185  // Test decoding with enough output size => must work
186  ret = LZ4_uncompress_unknownOutputSize((char*)&cbuf[off_full], (char*)testOut, len, LEN+1);
187  if (ret<0) { printf("decompression failed despite sufficient space: seed %u, len %d\n", seed, LEN); goto _output_error; }
188 
189  // Test decoding with output size being exactly what's necessary => must work
190  ret = LZ4_uncompress_unknownOutputSize((char*)&cbuf[off_full], (char*)testOut, len, LEN);
191  if (ret<0) { printf("decompression failed despite sufficient space: seed %u, len %d\n", seed, LEN); goto _output_error; }
192 
193  // Test decoding with output size being one byte too short => must fail
194  ret = LZ4_uncompress_unknownOutputSize((char*)&cbuf[off_full], (char*)testOut, len, LEN-1);
195  if (ret>=0) { printf("decompression should have failed, due to Output Size being too small : seed %u, len %d\n", seed, LEN); goto _output_error; }
196 
197  // Test decoding with input size being one byte too short => must fail
198  ret = LZ4_uncompress_unknownOutputSize((char*)&cbuf[off_full], (char*)testOut, len-1, LEN);
199  if (ret>=0) { printf("decompression should have failed, due to input size being too small : seed %u, len %d\n", seed, LEN); goto _output_error; }
200 
201  // Test decoding with input size being one byte too large => must fail
202  ret = LZ4_uncompress_unknownOutputSize((char*)&cbuf[off_full], (char*)testOut, len+1, LEN);
203  if (ret>=0) { printf("decompression should have failed, due to input size being too large : seed %u, len %d\n", seed, LEN); goto _output_error; }
204 
205  // Test compression with output size being exactly what's necessary (should work)
206  ret = LZ4_compress_limitedOutput((const char*)buf, (char*)&cbuf[FUZ_avail-len], LEN, len);
207  if (!test_canary(&cbuf[FUZ_avail])) { printf("compression overran output buffer: seed %u, len %d, olen %d\n", seed, LEN, len); goto _output_error; }
208  if (ret == 0) { printf("compression failed despite sufficient space: seed %u, len %d\n", seed, LEN); goto _output_error; }
209 
210  // Test compression with just one missing byte into output buffer => must fail
211  ret = LZ4_compress_limitedOutput((const char*)buf, (char*)&cbuf[FUZ_avail-(len-1)], LEN, len-1);
212  if (ret) { printf("compression overran output buffer: seed %u, len %d, olen %d => ret %d", seed, LEN, len-1, ret); goto _output_error; }
213  if (!test_canary(&cbuf[FUZ_avail])) { printf("compression overran output buffer: seed %u, len %d, olen %d", seed, LEN, len-1); goto _output_error; }
214 
215  bytes += LEN;
216  cbytes += len;
217  }
218 
219  printf("all tests completed successfully \n");
220  printf("compression ratio: %0.3f%%\n", (double)cbytes/bytes*100);
221  getchar();
222  return 0;
223 
224 _output_error:
225  getchar();
226  return 1;
227 }