1 /********************************************************************** 2 Copyright(c) 2011-2017 Intel Corporation All rights reserved. 3 4 Redistribution and use in source and binary forms, with or without 5 modification, are permitted provided that the following conditions 6 are met: 7 * Redistributions of source code must retain the above copyright 8 notice, this list of conditions and the following disclaimer. 9 * Redistributions in binary form must reproduce the above copyright 10 notice, this list of conditions and the following disclaimer in 11 the documentation and/or other materials provided with the 12 distribution. 13 * Neither the name of Intel Corporation nor the names of its 14 contributors may be used to endorse or promote products derived 15 from this software without specific prior written permission. 16 17 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 18 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 19 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 20 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 21 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 22 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 23 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 27 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 **********************************************************************/ 29 30 #include <stdlib.h> 31 #include <stdint.h> 32 #include <string.h> 33 #include <stdio.h> 34 #include "rolling_hashx.h" 35 36 #ifndef FUT_run 37 # define FUT_run rolling_hash2_run 38 #endif 39 #ifndef FUT_init 40 # define FUT_init rolling_hash2_init 41 #endif 42 #ifndef FUT_reset 43 # define FUT_reset rolling_hash2_reset 44 #endif 45 #ifndef FUT_ref 46 # define FUT_ref rolling_hash2_ref 47 #endif 48 49 #define str(s) #s 50 #define xstr(s) str(s) 51 52 #define MAX_BUFFER_SIZE 128*1024*1024 53 #define MAX_ROLLING_HASH_WIDTH 32 54 55 #ifndef RANDOMS 56 # define RANDOMS 200 57 #endif 58 #ifndef TEST_SEED 59 # define TEST_SEED 0x1234 60 #endif 61 62 static 63 uint64_t rolling_hash2_ref(struct rh_state2 *state, unsigned char *p, int len, 64 uint64_t hash_init) 65 { 66 int i; 67 uint64_t h = hash_init; 68 69 for (i = 0; i < len; i++) { 70 h = (h << 1) | (h >> (64 - 1)); 71 h ^= state->table1[*p++]; 72 } 73 return h; 74 } 75 76 int ones_in_mask(uint32_t in) 77 { 78 int count; 79 80 for (count = 0; in != 0; in &= (in - 1)) 81 count++; 82 83 return count; 84 } 85 86 /* 87 * Utility function to pick a random mask. Not uniform in number of bits. 88 */ 89 uint32_t pick_rand_mask_in_range(int min_bits, int max_bits) 90 { 91 uint32_t mask = 0; 92 int ones; 93 94 do { 95 mask = rand(); 96 #if defined(_WIN32) || defined(_WIN64) 97 mask = (mask << 16) ^ rand(); 98 #endif 99 ones = ones_in_mask(mask); 100 } while (ones < min_bits || ones > max_bits); 101 102 return mask; 103 } 104 105 int main(void) 106 { 107 uint8_t *buffer; 108 uint64_t hash; 109 uint32_t mask, trigger, offset = 0; 110 int i, w, r, ret, max, errors = 0; 111 uint32_t offset_fut; 112 struct rh_state2 state; 113 114 printf(xstr(FUT_run) ": " xstr(MAX_BUFFER_SIZE)); 115 116 buffer = malloc(MAX_BUFFER_SIZE); 117 if (buffer == NULL) { 118 printf("cannot allocate mem\n"); 119 return -1; 120 } 121 srand(TEST_SEED); 122 123 // Test case 1, compare trigger case at boundary with reference hash 124 w = 32; 125 mask = 0xffff0; 126 trigger = 0x3df0; 127 trigger &= mask; 128 129 for (i = 0; i < MAX_BUFFER_SIZE; i++) 130 buffer[i] = rand(); 131 132 FUT_init(&state, w); 133 FUT_reset(&state, buffer); 134 135 uint8_t *p = buffer; 136 int remain = MAX_BUFFER_SIZE; 137 ret = FINGERPRINT_RET_HIT; 138 139 while ((ret == FINGERPRINT_RET_HIT) && (remain > 0)) { 140 ret = FUT_run(&state, p, remain, mask, trigger, &offset); 141 142 if (offset > remain) { 143 printf(" error offset past remaining limit\n"); 144 errors++; 145 } 146 147 if ((ret == FINGERPRINT_RET_HIT) && (&p[offset] > &buffer[w])) { 148 hash = FUT_ref(&state, &p[offset] - w, w, 0); 149 if ((hash & mask) != trigger) { 150 printf(" mismatch chunk from ref"); 151 printf(" hit: offset=%d %lx %lx\n", offset, state.hash, hash); 152 errors++; 153 } 154 } 155 p += offset; 156 remain -= offset; 157 putchar('.'); 158 } 159 160 putchar('.'); // Finished test 1 161 162 // Test case 2, check if reference function hits same chunk boundary as test 163 164 w = 32; 165 mask = 0xffff; 166 trigger = rand(); 167 trigger &= mask; 168 p = buffer; 169 170 // Function under test 171 FUT_init(&state, w); 172 FUT_reset(&state, p); 173 ret = FUT_run(&state, p + w, MAX_BUFFER_SIZE - w, mask, trigger, &offset_fut); 174 offset_fut += w; 175 176 // Reference 177 for (p++, offset = w + 1; offset < MAX_BUFFER_SIZE; offset++) { 178 hash = FUT_ref(&state, p++, w, 0); 179 if ((hash & mask) == trigger) 180 break; 181 } 182 183 if (offset != offset_fut) { 184 printf("\ncase 2, offset of chunk different from ref\n"); 185 printf(" case 2: stop fut at offset=%d\n", offset_fut); 186 printf(" case 2: stop ref at offset=%d\n", offset); 187 errors++; 188 goto end; 189 } 190 putchar('.'); // Finished test 2 191 192 // Do case 2 above with random args 193 194 for (r = 0; r < RANDOMS; r++) { 195 w = rand() % MAX_ROLLING_HASH_WIDTH; 196 if (w < 3) 197 continue; 198 199 mask = pick_rand_mask_in_range(4, 20); 200 trigger = rand() & mask; 201 p = buffer; 202 203 // Function under test 204 FUT_init(&state, w); 205 FUT_reset(&state, p); 206 ret = FUT_run(&state, p + w, MAX_BUFFER_SIZE - w, mask, trigger, &offset_fut); 207 offset_fut += w; 208 209 // Reference 210 for (p++, offset = w + 1; offset < MAX_BUFFER_SIZE; offset++) { 211 hash = FUT_ref(&state, p++, w, 0); 212 if ((hash & mask) == trigger) 213 break; 214 } 215 216 if (offset != offset_fut) { 217 printf("\nrand case 2 #%d: w=%d, mask=0x%x, trigger=0x%x\n", r, w, 218 mask, trigger); 219 printf(" offset of chunk different from ref\n"); 220 printf(" case 2r: stop fut at offset=%d\n", offset_fut); 221 printf(" case 2r: stop ref at offset=%d\n", offset); 222 errors++; 223 goto end; 224 } 225 putchar('.'); 226 } 227 228 // Test case 3, check if max bound is same 229 230 w = 32; 231 mask = 0xfffff; 232 trigger = rand(); 233 trigger &= mask; 234 putchar('|'); 235 236 for (max = w + 1; max < 500; max++) { 237 p = buffer; 238 FUT_init(&state, w); 239 FUT_reset(&state, p); 240 241 ret = FUT_run(&state, p + w, max - w, mask, trigger, &offset_fut); 242 offset_fut += w; 243 244 int ret_ref = FINGERPRINT_RET_MAX; 245 for (p++, offset = w + 1; offset < max; offset++) { 246 hash = FUT_ref(&state, p++, w, 0); 247 if ((hash & mask) == trigger) { 248 ret_ref = FINGERPRINT_RET_HIT; 249 break; 250 } 251 } 252 253 if (offset != offset_fut || ret != ret_ref) { 254 printf("\ncase 3 max=%d, offset of chunk different from ref\n", max); 255 printf(" case 3: stop fut at offset=%d\n", offset_fut); 256 printf(" case 3: stop ref at offset=%d\n", offset); 257 printf(" case 3: ret_fut=%d ret_ref=%d\n", ret, ret_ref); 258 errors++; 259 goto end; 260 } 261 putchar('.'); // Finished test 3 262 } 263 264 // Test case 4, check if max bound is same under random params 265 266 for (r = 0; r < RANDOMS; r++) { 267 p = buffer; 268 mask = pick_rand_mask_in_range(24, 30); // Pick an unlikely mask 269 trigger = rand() & mask; 270 w = rand() % MAX_ROLLING_HASH_WIDTH; 271 max = rand() % 1024; 272 273 if (w < 3 || max < 2 * MAX_ROLLING_HASH_WIDTH) 274 continue; 275 276 FUT_init(&state, w); 277 FUT_reset(&state, p); 278 279 ret = FUT_run(&state, p, max, mask, trigger, &offset_fut); 280 281 if (offset_fut <= w) 282 continue; 283 284 int ret_ref = FINGERPRINT_RET_MAX; 285 for (p++, offset = w + 1; offset < max; offset++) { 286 hash = FUT_ref(&state, p++, w, 0); 287 if ((hash & mask) == trigger) { 288 ret_ref = FINGERPRINT_RET_HIT; 289 break; 290 } 291 } 292 293 if (offset != offset_fut || ret != ret_ref) { 294 printf("\ncase 4 rand case different from ref, max=%d w=%d\n", max, w); 295 printf(" case 4: stop fut at offset=%d\n", offset_fut); 296 printf(" case 4: stop ref at offset=%d\n", offset); 297 printf(" case 4: ret_fut=%d ret_ref=%d\n", ret, ret_ref); 298 errors++; 299 goto end; 300 } 301 putchar('.'); // Finished test 4 302 303 if (ret == FINGERPRINT_RET_HIT) { 304 p[-1] = rand(); // Keep hits from repeating 305 } 306 } 307 308 end: 309 if (buffer != NULL) 310 free(buffer); 311 312 if (errors > 0) 313 printf(" Fail: %d\n", errors); 314 else 315 printf(" Pass\n"); 316 return errors; 317 } 318