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 /** 31 * @file rolling_hashx.h 32 * @brief Fingerprint functions based on rolling hash 33 * 34 * rolling_hash2 - checks hash in a sliding window based on random 64-bit hash. 35 */ 36 37 #ifndef _ROLLING_HASHX_H_ 38 #define _ROLLING_HASHX_H_ 39 40 #ifdef __cplusplus 41 extern "C" { 42 #endif 43 44 #include <stdint.h> 45 46 /** 47 *@brief rolling hash return values 48 */ 49 enum { 50 FINGERPRINT_RET_HIT = 0, //!< Fingerprint trigger hit 51 FINGERPRINT_RET_MAX, //!< Fingerprint max length reached before hit 52 FINGERPRINT_RET_OTHER //!< Fingerprint function error returned 53 }; 54 55 #define FINGERPRINT_MAX_WINDOW 48 56 57 /** 58 * @brief Context for rolling_hash2 functions 59 */ 60 struct rh_state2 { 61 uint8_t history[FINGERPRINT_MAX_WINDOW]; 62 uint64_t table1[256]; 63 uint64_t table2[256]; 64 uint64_t hash; 65 uint32_t w; 66 }; 67 68 /** 69 * @brief Initialize state object for rolling hash2 70 * 71 * @param state Structure holding state info on current rolling hash 72 * @param w Window width (1 <= w <= 32) 73 * @returns 0 - success, -1 - failure 74 */ 75 int 76 rolling_hash2_init(struct rh_state2 *state, uint32_t w); 77 78 /** 79 * @brief Reset the hash state history 80 * 81 * @param state Structure holding state info on current rolling hash 82 * @param init_bytes Optional window size buffer to pre-init hash 83 * @returns none 84 */ 85 void 86 rolling_hash2_reset(struct rh_state2 *state, uint8_t *init_bytes); 87 88 /** 89 * @brief Run rolling hash function until trigger met or max length reached 90 * 91 * Checks for trigger based on a random hash in a sliding window. 92 * @param state Structure holding state info on current rolling hash 93 * @param buffer Pointer to input buffer to run windowed hash on 94 * @param max_len Max length to run over input 95 * @param mask Mask bits ORed with hash before test with trigger 96 * @param trigger Match value to compare with windowed hash at each input byte 97 * @param offset Offset from buffer to match, set if match found 98 * @returns FINGERPRINT_RET_HIT - match found, FINGERPRINT_RET_MAX - exceeded max length 99 */ 100 int 101 rolling_hash2_run(struct rh_state2 *state, uint8_t *buffer, uint32_t max_len, uint32_t mask, 102 uint32_t trigger, uint32_t *offset); 103 104 /** 105 * @brief Generate an appropriate mask to target mean hit rate 106 * 107 * @param mean Target chunk size in bytes 108 * @param shift Bits to rotate result to get independent masks 109 * @returns 32-bit mask value 110 */ 111 uint32_t 112 rolling_hashx_mask_gen(long mean, int shift); 113 114 #ifdef __cplusplus 115 } 116 #endif 117 118 #endif // _ROLLING_HASHX_H_ 119