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 "isal_crypto_api.h" 35 #include "rolling_hashx.h" 36 37 #ifndef FUT_run 38 #define FUT_run isal_rolling_hash2_run 39 #endif 40 #ifndef FUT_init 41 #define FUT_init isal_rolling_hash2_init 42 #endif 43 #ifndef FUT_reset 44 #define FUT_reset isal_rolling_hash2_reset 45 #endif 46 #ifndef FUT_ref 47 #define FUT_ref rolling_hash2_ref 48 #endif 49 50 #define str(s) #s 51 #define xstr(s) str(s) 52 53 #define MAX_BUFFER_SIZE 128 * 1024 * 1024 54 #define MAX_ROLLING_HASH_WIDTH 32 55 56 #ifndef RANDOMS 57 #define RANDOMS 200 58 #endif 59 #ifndef TEST_SEED 60 #define TEST_SEED 0x1234 61 #endif 62 63 static uint64_t 64 rolling_hash2_ref(struct rh_state2 *state, unsigned char *p, int len, 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 77 ones_in_mask(uint32_t in) 78 { 79 int count; 80 81 for (count = 0; in != 0; in &= (in - 1)) 82 count++; 83 84 return count; 85 } 86 87 /* 88 * Utility function to pick a random mask. Not uniform in number of bits. 89 */ 90 uint32_t 91 pick_rand_mask_in_range(int min_bits, int max_bits) 92 { 93 uint32_t mask = 0; 94 int ones; 95 96 do { 97 mask = rand(); 98 #if defined(_WIN32) || defined(_WIN64) 99 mask = (mask << 16) ^ rand(); 100 #endif 101 ones = ones_in_mask(mask); 102 } while (ones < min_bits || ones > max_bits); 103 104 return mask; 105 } 106 107 int 108 main(void) 109 { 110 uint8_t *buffer; 111 uint64_t hash; 112 uint32_t w, max, mask, trigger, offset = 0; 113 int i, r, ret, match, errors = 0; 114 uint32_t offset_fut; 115 struct rh_state2 state; 116 117 printf(xstr(FUT_run) ": " xstr(MAX_BUFFER_SIZE)); 118 119 buffer = malloc(MAX_BUFFER_SIZE); 120 if (buffer == NULL) { 121 printf("cannot allocate mem\n"); 122 return -1; 123 } 124 srand(TEST_SEED); 125 126 // Test case 1, compare trigger case at boundary with reference hash 127 w = 32; 128 mask = 0xffff0; 129 trigger = 0x3df0; 130 trigger &= mask; 131 132 for (i = 0; i < MAX_BUFFER_SIZE; i++) 133 buffer[i] = rand(); 134 135 FUT_init(&state, w); 136 FUT_reset(&state, buffer); 137 138 uint8_t *p = buffer; 139 uint32_t remain = MAX_BUFFER_SIZE; 140 match = FINGERPRINT_RET_HIT; 141 142 while ((match == FINGERPRINT_RET_HIT) && (remain > 0)) { 143 ret = FUT_run(&state, p, remain, mask, trigger, &offset, &match); 144 145 if (ret != ISAL_CRYPTO_ERR_NONE) { 146 printf(" %s (TC1) returned error %d\n", xstr(FUT_run), ret); 147 errors++; 148 } 149 150 if (offset > remain) { 151 printf(" error offset past remaining limit\n"); 152 errors++; 153 } 154 155 if ((match == FINGERPRINT_RET_HIT) && (&p[offset] > &buffer[w])) { 156 hash = FUT_ref(&state, &p[offset] - w, w, 0); 157 if ((hash & mask) != trigger) { 158 printf(" mismatch chunk from ref"); 159 printf(" hit: offset=%u %llx %llx\n", (unsigned) offset, 160 (unsigned long long) state.hash, (unsigned long long) hash); 161 errors++; 162 } 163 } 164 p += offset; 165 remain -= offset; 166 putchar('.'); 167 } 168 169 putchar('.'); // Finished test 1 170 171 // Test case 2, check if reference function hits same chunk boundary as test 172 173 w = 32; 174 mask = 0xffff; 175 trigger = rand(); 176 trigger &= mask; 177 p = buffer; 178 179 // Function under test 180 FUT_init(&state, w); 181 FUT_reset(&state, p); 182 FUT_run(&state, p + w, MAX_BUFFER_SIZE - w, mask, trigger, &offset_fut, &match); 183 offset_fut += w; 184 185 // Reference 186 for (p++, offset = w + 1; offset < MAX_BUFFER_SIZE; offset++) { 187 hash = FUT_ref(&state, p++, w, 0); 188 if ((hash & mask) == trigger) 189 break; 190 } 191 192 if (offset != offset_fut) { 193 printf("\ncase 2, offset of chunk different from ref\n"); 194 printf(" case 2: stop fut at offset=%d\n", offset_fut); 195 printf(" case 2: stop ref at offset=%d\n", offset); 196 errors++; 197 goto end; 198 } 199 putchar('.'); // Finished test 2 200 201 // Do case 2 above with random args 202 203 for (r = 0; r < RANDOMS; r++) { 204 w = rand() % MAX_ROLLING_HASH_WIDTH; 205 if (w < 3) 206 continue; 207 208 mask = pick_rand_mask_in_range(4, 20); 209 trigger = rand() & mask; 210 p = buffer; 211 212 // Function under test 213 FUT_init(&state, w); 214 FUT_reset(&state, p); 215 FUT_run(&state, p + w, MAX_BUFFER_SIZE - w, mask, trigger, &offset_fut, &match); 216 offset_fut += w; 217 218 // Reference 219 for (p++, offset = w + 1; offset < MAX_BUFFER_SIZE; offset++) { 220 hash = FUT_ref(&state, p++, w, 0); 221 if ((hash & mask) == trigger) 222 break; 223 } 224 225 if (offset != offset_fut) { 226 printf("\nrand case 2 #%d: w=%d, mask=0x%x, trigger=0x%x\n", r, w, mask, 227 trigger); 228 printf(" offset of chunk different from ref\n"); 229 printf(" case 2r: stop fut at offset=%d\n", offset_fut); 230 printf(" case 2r: stop ref at offset=%d\n", offset); 231 errors++; 232 goto end; 233 } 234 putchar('.'); 235 } 236 237 // Test case 3, check if max bound is same 238 239 w = 32; 240 mask = 0xfffff; 241 trigger = rand(); 242 trigger &= mask; 243 putchar('|'); 244 245 for (max = w + 1; max < 500; max++) { 246 p = buffer; 247 FUT_init(&state, w); 248 FUT_reset(&state, p); 249 250 ret = FUT_run(&state, p + w, max - w, mask, trigger, &offset_fut, &match); 251 252 if (ret != ISAL_CRYPTO_ERR_NONE) { 253 printf(" %s (TC3) returned error %d\n", xstr(FUT_run), ret); 254 errors++; 255 } 256 257 offset_fut += w; 258 259 int ret_ref = FINGERPRINT_RET_MAX; 260 for (p++, offset = w + 1; offset < max; offset++) { 261 hash = FUT_ref(&state, p++, w, 0); 262 if ((hash & mask) == trigger) { 263 ret_ref = FINGERPRINT_RET_HIT; 264 break; 265 } 266 } 267 268 if (offset != offset_fut || match != ret_ref) { 269 printf("\ncase 3 max=%d, offset of chunk different from ref\n", max); 270 printf(" case 3: stop fut at offset=%d\n", offset_fut); 271 printf(" case 3: stop ref at offset=%d\n", offset); 272 printf(" case 3: ret_fut=%d ret_ref=%d\n", match, ret_ref); 273 errors++; 274 goto end; 275 } 276 putchar('.'); // Finished test 3 277 } 278 279 // Test case 4, check if max bound is same under random params 280 281 for (r = 0; r < RANDOMS; r++) { 282 p = buffer; 283 mask = pick_rand_mask_in_range(24, 30); // Pick an unlikely mask 284 trigger = rand() & mask; 285 w = rand() % MAX_ROLLING_HASH_WIDTH; 286 max = rand() % 1024; 287 288 if (w < 3 || max < 2 * MAX_ROLLING_HASH_WIDTH) 289 continue; 290 291 FUT_init(&state, w); 292 FUT_reset(&state, p); 293 294 ret = FUT_run(&state, p, max, mask, trigger, &offset_fut, &match); 295 296 if (ret != ISAL_CRYPTO_ERR_NONE) { 297 printf(" %s (TC4) returned error %d\n", xstr(FUT_run), ret); 298 errors++; 299 } 300 301 if (offset_fut <= w) 302 continue; 303 304 int ret_ref = FINGERPRINT_RET_MAX; 305 for (p++, offset = w + 1; offset < max; offset++) { 306 hash = FUT_ref(&state, p++, w, 0); 307 if ((hash & mask) == trigger) { 308 ret_ref = FINGERPRINT_RET_HIT; 309 break; 310 } 311 } 312 313 if (offset != offset_fut || match != ret_ref) { 314 printf("\ncase 4 rand case different from ref, max=%d w=%d\n", max, w); 315 printf(" case 4: stop fut at offset=%d\n", offset_fut); 316 printf(" case 4: stop ref at offset=%d\n", offset); 317 printf(" case 4: ret_fut=%d ret_ref=%d\n", match, ret_ref); 318 errors++; 319 goto end; 320 } 321 putchar('.'); // Finished test 4 322 323 if (match == FINGERPRINT_RET_HIT) { 324 p[-1] = rand(); // Keep hits from repeating 325 } 326 } 327 328 end: 329 if (buffer != NULL) 330 free(buffer); 331 332 if (errors > 0) 333 printf(" Fail: %d\n", errors); 334 else 335 printf(" Pass\n"); 336 return errors; 337 } 338