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 /** 115 * @brief Initialize state object for rolling hash2 116 * 117 * @param[in] state Structure holding state info on current rolling hash 118 * @param[in] w Window width (1 <= w <= 32) 119 * @return Operation status 120 * @retval 0 on success 121 * @retval Non-zero \a ISAL_CRYPTO_ERR on failure 122 */ 123 int 124 isal_rolling_hash2_init(struct rh_state2 *state, const uint32_t w); 125 126 /** 127 * @brief Reset the hash state history 128 * 129 * @param[in] state Structure holding state info on current rolling hash 130 * @param[in] init_bytes Optional window size buffer to pre-init hash 131 * @return Operation status 132 * @retval 0 on success 133 * @retval Non-zero \a ISAL_CRYPTO_ERR on failure 134 */ 135 int 136 isal_rolling_hash2_reset(struct rh_state2 *state, const uint8_t *init_bytes); 137 138 /** 139 * @brief Run rolling hash function until trigger met or max length reached 140 * 141 * Checks for trigger based on a random hash in a sliding window. 142 * @param[in] state Structure holding state info on current rolling hash 143 * @param[in] buffer Pointer to input buffer to run windowed hash on 144 * @param[in] max_len Max length to run over input 145 * @param[in] mask Mask bits ORed with hash before test with trigger 146 * @param[in] trigger Match value to compare with windowed hash at each input byte 147 * @param[out] offset Offset from buffer to match, set if match found 148 * @param[out] match Pointer to fingerprint result status to set 149 * FINGERPRINT_RET_HIT - match found 150 * FINGERPRINT_RET_MAX - exceeded max length 151 * FINGERPRINT_RET_OTHER - error 152 * @return Operation status 153 * @retval 0 on success 154 * @retval Non-zero \a ISAL_CRYPTO_ERR on failure 155 */ 156 int 157 isal_rolling_hash2_run(struct rh_state2 *state, const uint8_t *buffer, const uint32_t max_len, 158 const uint32_t mask, const uint32_t trigger, uint32_t *offset, int *match); 159 160 /** 161 * @brief Generate an appropriate mask to target mean hit rate 162 * 163 * @param[in] mean Target chunk size in bytes 164 * @param[in] shift Bits to rotate result to get independent masks 165 * @param[out] mask Generated 32-bit mask value 166 * @return Operation status 167 * @retval 0 on success 168 * @retval Non-zero \a ISAL_CRYPTO_ERR on failure 169 */ 170 int 171 isal_rolling_hashx_mask_gen(const uint32_t mean, const uint32_t shift, uint32_t *mask); 172 173 #ifdef __cplusplus 174 } 175 #endif 176 177 #endif // _ROLLING_HASHX_H_ 178