$treeview $search $mathjax $extrastylesheet
librsync
2.3.1
$projectbrief
|
$projectbrief
|
$searchbox |
00001 /*= -*- c-basic-offset: 4; indent-tabs-mode: nil; -*- 00002 * 00003 * rabinkarp -- The RabinKarp rolling checksum. 00004 * 00005 * Copyright (C) 2019 by Donovan Baarda <abo@minkirri.apana.org.au> 00006 * 00007 * This program is free software; you can redistribute it and/or modify 00008 * it under the terms of the GNU Lesser General Public License as published by 00009 * the Free Software Foundation; either version 2.1 of the License, or 00010 * (at your option) any later version. 00011 * 00012 * This program is distributed in the hope that it will be useful, 00013 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 * GNU Lesser General Public License for more details. 00016 * 00017 * You should have received a copy of the GNU Lesser General Public License 00018 * along with this program; if not, write to the Free Software 00019 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00020 */ 00021 #ifndef _RABINKARP_H_ 00022 # define _RABINKARP_H_ 00023 00024 # include <stddef.h> 00025 # include <stdint.h> 00026 00027 /** The RabinKarp seed value. 00028 * 00029 * The seed ensures different length zero blocks have different hashes. It 00030 * effectively encodes the length into the hash. */ 00031 # define RABINKARP_SEED 1 00032 00033 /** The RabinKarp multiplier. 00034 * 00035 * This multiplier has a bit pattern of 1's getting sparser with significance, 00036 * is the product of 2 large primes, and matches the characterstics for a good 00037 * LCG multiplier. */ 00038 # define RABINKARP_MULT 0x08104225U 00039 00040 /** The RabinKarp inverse multiplier. 00041 * 00042 * This is the inverse of RABINKARP_MULT modular 2^32. Multiplying by this is 00043 * equivalent to dividing by RABINKARP_MULT. */ 00044 # define RABINKARP_INVM 0x98f009adU 00045 00046 /** The RabinKarp seed adjustment. 00047 * 00048 * This is a factor used to adjust for the seed when rolling out values. It's 00049 * equal to; (RABINKARP_MULT - 1) * RABINKARP_SEED */ 00050 # define RABINKARP_ADJ 0x08104224U 00051 00052 /** The rabinkarp_t state type. */ 00053 typedef struct _rabinkarp { 00054 size_t count; /**< Count of bytes included in sum. */ 00055 uint32_t hash; /**< The accumulated hash value. */ 00056 uint32_t mult; /**< The value of RABINKARP_MULT^count. */ 00057 } rabinkarp_t; 00058 00059 static inline void rabinkarp_init(rabinkarp_t *sum) 00060 { 00061 sum->count = 0; 00062 sum->hash = RABINKARP_SEED; 00063 sum->mult = 1; 00064 } 00065 00066 void rabinkarp_update(rabinkarp_t *sum, const unsigned char *buf, size_t len); 00067 00068 static inline void rabinkarp_rotate(rabinkarp_t *sum, unsigned char out, 00069 unsigned char in) 00070 { 00071 sum->hash = 00072 sum->hash * RABINKARP_MULT + in - sum->mult * (out + RABINKARP_ADJ); 00073 } 00074 00075 static inline void rabinkarp_rollin(rabinkarp_t *sum, unsigned char in) 00076 { 00077 sum->hash = sum->hash * RABINKARP_MULT + in; 00078 sum->count++; 00079 sum->mult *= RABINKARP_MULT; 00080 } 00081 00082 static inline void rabinkarp_rollout(rabinkarp_t *sum, unsigned char out) 00083 { 00084 sum->count--; 00085 sum->mult *= RABINKARP_INVM; 00086 sum->hash -= sum->mult * (out + RABINKARP_ADJ); 00087 } 00088 00089 static inline uint32_t rabinkarp_digest(rabinkarp_t *sum) 00090 { 00091 return sum->hash; 00092 } 00093 00094 #endif /* _RABINKARP_H_ */