文件指纹算法

一直在找robinhash的指纹算法

折腾了很久终于解决问题了，因为java实现的源码被我找到了，我改成了c＋＋版本希望对和我有相同问题的朋友有所帮助，大家有更好的可以提出来阿

头文件：

/*<br />* rabinhash-c++.h<br />*<br />* Created on: Mar 31, 2009<br />* Author: luo<br />* 由Sean Owen写的java版本改编而来，算法思想是:<br />*<br />* </p> <p>This class provides an implementation of a hash function based on Rabin fingerprints, one<br />* which can efficiently produce a 32-bit hash value for a sequence of bytes. It does so by considering<br />* strings of bytes as large polynomials over GF(2) — that is, with coefficients of 0 and 1 —<br />* and then reducing them modulo some irreducible polynomial of degree 32. The result is a hash function<br />* with very satisfactory properties. In addition the polynomial operations are fast in hardware;<br />* even in this Java implementation the speed is reasonable.</p> <p>*<br />* </p> <p>Methods in this class can compute a hash value for an array of bytes, chars or ints, as well as<br />* any {@link java.io.Serializable} object, String, file, or resource denoted by URL.</p> <p>*<br />* </p> <p>Methods of this class are all thread-safe, and hash function objects are immutable.</p> <p>*<br />* </p> <p>olynomials of degree 32 are used frequently in this code, and are represented efficiently as<br />* <code>int</code>s. An <code>int</code> has 32 bits, whereas a polynomial of degree 32 has 33 coefficients.<br />* Therefore, the high-order bit of the <code>int</code> is the degree 31 term’s<br />* coefficient, and the low-order bit is the constant coefficient.</p> <p>*<br />* </p> <p>For example the integer 0x00000803, in binary, is:</p> <p>*<br />* </p> <p><code>00000000 00000000 00001000 00000011</code></p> <p>*<br />* </p> <p>Therefore it correponds to the polynomial:</p> <p>*<br />* </p> <p><code>x³² + x¹¹ + x + 1</code></p> <p>*<br />* </p> <p>The implementation is derived from the paper “Some applications of Rabin’s fingerprinting method”<br />* by Andrei Broder. See <a href="http://server3.pa-x.dec.com/SRC/publications/src-papers.html" mce_href="http://server3.pa-x.dec.com/SRC/publications/src-papers.html"><br />* http://server3.pa-x.dec.com/SRC/publications/src-papers.html</a> for a full citation and the paper<br />* in PDF format.</p> <p>*<br />*<br />*/<br />#ifndef RABINHASHC_H_<br />#define RABINHASHC_H_<br />class RabinHashFunction32 {<br />private:<br />/ Represents x³² + x⁷ + x³ + x² + 1. */<br />static const int DEFAULT_IRREDUCIBLE_POLY = 0x0000008D;<br />/ Default hash function, provided for convenience. */<br />//static const RabinHashFunction32 DEFAULT_HASH_FUNCTION =<br />//RabinHashFunction32(DEFAULT_IRREDUCIBLE_POLY);<br />static const int P_DEGREE = 32;<br />static const int X_P_DEGREE = 1 << (P_DEGREE - 1);static const int READ_BUFFER_SIZE = 1024;const int P;int *table32, *table40, *table48, *table56;void initializeTables();public:/ * <p>Creates a RabinHashFunction32 based on the specified polynomial.</p> <p> *<br /> * </p> <p>This class does not test the polynomial for irreducibility; therefore this constructor should<br /> * only be used with polynomials that are already known to be irreducible, or else the hash function<br /> * will not perform optimally.</p> <p> *<br /> * @param P a degree 32 polynomial over GF(2), represented as an <code>int</code><br /> */<br />RabinHashFunction32(const int P);<br />~RabinHashFunction32();<br />/<br /> * @return irreducible polynomial used in this hash function, represented as an <code>int</code><br /> */<br />int getP();<br />int computeWShifted(const int w);<br />/<br /> * </p> <p>Return the Rabin hash value of an array of bytes.</p> <p> *<br /> * @param A the array of bytes<br /> * @return the hash value<br /> * @throws NullPointerException if A is null<br /> */<br />int hash(const char A[], const int size);<br />int hash(const char A[], const int offset, const int length, int w);<br />};<br />#endif /* RABINHASHC_H_ */

cpp：

#include “rabinhash-c++.h” RabinHashFunction32::RabinHashFunction32(const int vP)(vP) { initializeTables(); } RabinHashFunction32::~RabinHashFunction32(){ delete[] table32; delete[] table40; delete[] table48; delete[] table56; } void RabinHashFunction32::initializeTables() { int* mods = new int[P_DEGREE]; // We want to have mods == x^(P_DEGREE+i) mods[0] = P; for (int i = 1; i < P_DEGREE; i++) { const int lastMod = mods[i - 1]; // x^i == x(x^(i-1)) (mod P) int thisMod = lastMod << 1; // if x^(i-1) had a x_(P_DEGREE-1) term then x^i has a // x^P_DEGREE term that 'fell off' the top end. // Since x^P_DEGREE == P (mod P), we should add P // to account for this: if ((lastMod & X_P_DEGREE) != 0) { thisMod ^= P; } mods = thisMod; } // Let i be a number between 0 and 255 (i.e. a byte). // Let its bits be b0, b1, ..., b7. // Let Q32 be the polynomial b0*x^39 + b1*x^38 + ... + b7*x^32 (mod P). // Then table32 is Q32, represented as an int (see below). // Likewise Q40 be the polynomial b0*x^47 + b1*x^46 + ... + b7*x^40 (mod P). // table40 is Q40, represented as an int. Likewise table48 and table56. table32 = new int[256]; table40 = new int[256]; table48 = new int[256]; table56 = new int[256]; for (int i = 0; i < 256; i++) { int c = i; for (int j = 0; j < 8 && c > 0; j++) { if ((c & 1) != 0) { table32 ^= mods[j]; table40 ^= mods[j + 8]; table48 ^= mods[j + 16]; table56 ^= mods[j + 24]; } c >>= 1; } } delete[] mods; } int RabinHashFunction32::getP() { return P; } int RabinHashFunction32::computeWShifted(const int w){ return table32[w & 0xFF] ^table40[(w >> & 0xFF] ^table48[(w >> 16) & 0xFF] ^ table56[(w >> 24) & 0xFF]; } int RabinHashFunction32::hash(const char A[],const int size) { return hash(A, 0, size, 0); } int RabinHashFunction32::hash(const char A[], const int offset, const int length, int w) { int s = offset; // First, process a few bytes so that the number of bytes remaining is a multiple of 4. // This makes the later loop easier. const int starterBytes = length % 4; if (starterBytes != 0) { const int max = offset + starterBytes; while (s < max) { w = (w << ^ (A[s] & 0xFF); s++; } } const int max = offset + length; while (s < max) { w = computeWShifted(w) ^ (A[s] << 24) ^ ((A[s + 1] & 0xFF) << 16) ^ ((A[s + 2] & 0xFF) << ^ (A[s + 3] & 0xFF); s += 4; } return w; }

测试代码：

/* * rabin-test-main.cpp * * Created on: Mar 31, 2009 * Author: luo */ #include “rabinhash-c++.h” #include <stdio.h> int main(){ const char str[10]={‘l’,’u’,’o’,’l’,’e’,’i’,’a’,’b’,’c’,’d’}; RabinHashFunction32 rabin = RabinHashFunction32(1); int value = rabin.hash(str,10); //rabin.h printf(“%s : %d”,str,value); }