$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 #include "rabinkarp.h" 00022 00023 /* Constant for RABINKARP_MULT^2. */ 00024 #define RABINKARP_MULT2 (RABINKARP_MULT*RABINKARP_MULT) 00025 00026 /* Macros for doing 16 bytes with 2 mults that can be done in parallel. Testing 00027 showed this as a performance sweet spot vs 16x1, 8x2, 4x4 1x16 alternative 00028 arrangements. */ 00029 #define PAR2X1(hash,buf,i) (RABINKARP_MULT2*(hash) + \ 00030 RABINKARP_MULT*buf[i] + \ 00031 buf[i+1]) 00032 #define PAR2X2(hash,buf,i) PAR2X1(PAR2X1(hash,buf,i),buf,i+2) 00033 #define PAR2X4(hash,buf,i) PAR2X2(PAR2X2(hash,buf,i),buf,i+4) 00034 #define PAR2X8(hash,buf) PAR2X4(PAR2X4(hash,buf,0),buf,8) 00035 00036 /* Table of RABINKARP_MULT^(2^(i+1)) for power lookups. */ 00037 const static uint32_t RABINKARP_MULT_POW2[32] = { 00038 0x08104225U, 00039 0xa5b71959U, 00040 0xf9c080f1U, 00041 0x7c71e2e1U, 00042 0x0bb409c1U, 00043 0x4dc72381U, 00044 0xd17a8701U, 00045 0x96260e01U, 00046 0x55101c01U, 00047 0x2d303801U, 00048 0x66a07001U, 00049 0xfe40e001U, 00050 0xc081c001U, 00051 0x91038001U, 00052 0x62070001U, 00053 0xc40e0001U, 00054 0x881c0001U, 00055 0x10380001U, 00056 0x20700001U, 00057 0x40e00001U, 00058 0x81c00001U, 00059 0x03800001U, 00060 0x07000001U, 00061 0x0e000001U, 00062 0x1c000001U, 00063 0x38000001U, 00064 0x70000001U, 00065 0xe0000001U, 00066 0xc0000001U, 00067 0x80000001U, 00068 0x00000001U, 00069 0x00000001U 00070 }; 00071 00072 /* Get the value of RABINKARP_MULT^n. */ 00073 static inline uint32_t rabinkarp_pow(uint32_t n) 00074 { 00075 const uint32_t *m = RABINKARP_MULT_POW2; 00076 uint32_t ans = 1; 00077 while (n) { 00078 if (n & 1) { 00079 ans *= *m; 00080 } 00081 m++; 00082 n >>= 1; 00083 } 00084 return ans; 00085 } 00086 00087 void rabinkarp_update(rabinkarp_t *sum, const unsigned char *buf, size_t len) 00088 { 00089 size_t n = len; 00090 uint32_t hash = sum->hash; 00091 00092 while (n >= 16) { 00093 hash = PAR2X8(hash, buf); 00094 buf += 16; 00095 n -= 16; 00096 } 00097 while (n) { 00098 hash = RABINKARP_MULT * hash + *buf++; 00099 n--; 00100 } 00101 sum->hash = hash; 00102 sum->count += len; 00103 sum->mult *= rabinkarp_pow(len); 00104 }