1
2 package st.ata.util;
3
4 import java.util.Hashtable;
5
6 /***
7
8 <p> This class provides methods that construct fingerprints of strings
9 of bytes via operations in <i>GF[2^d]</i> for <i>0 < d <= 64</i>.
10 <i>GF[2^d]</i> is represented as the set of polynomials of degree
11 <i>d</i> with coefficients in <i>Z(2)</i>, modulo an irreducible
12 polynomial <i>P</i> of degree <i>d</i>. The representation of
13 polynomials is as an unsigned binary number in which the least
14 significant exponent is kept in the most significant bit.
15
16 <p> Let S be a string of bytes and <i>g(S)</i> the string obtained by
17 taking the byte <code>0x01</code> followed by eight <code>0x00</code>
18 bytes followed by <code>S</code>. Let <i>f(S)</i> be the polynomial
19 associated to the string <i>S</i> viewed as a polynomial with
20 coefficients in the field <i>Z(2)</i>. The fingerprint of S is simply
21 the value <i>f(g(S))</i> modulo <i>P</i>. Because polynomials are
22 represented with the least significant coefficient in the most
23 significant bit, fingerprints of degree <i>d</i> are stored in the
24 <code>d</code> <strong>most</code> significant bits of a long word.
25
26 <p> Fingerprints can be used as a probably unique id for the input
27 string. More precisely, if <i>P</i> is chosen at random among
28 irreducible polynomials of degree <i>d</i>, then the probability that
29 any two strings <i>A</i> and <i>B</i> have the same fingerprint is
30 less than <i>max(|A|,|B|)/2^(d+1)</i> where <i>|A|</i> is the length
31 of A in bits.
32
33 <p> The routines named <code>extend[8]</code> and <code>fp[8]</code>
34 return reduced results, while <code>extend_[byte/char/int/long]</code>
35 do not. An <em>un</em>reduced result is a number that is equal (mod
36 </code>polynomial</code> to the desired fingerprint but may have
37 degree <code>degree</code> or higher. The method <code>reduce</code>
38 reduces such a result to a polynomial of degree less than
39 <code>degree</code>. Obtaining reduced results takes longer than
40 obtaining unreduced results; thus, when fingerprinting long strings,
41 it's better to obtain irreduced results inside the fingerprinting loop
42 and use <code>reduce</code> to reduce to a fingerprint after the loop.
43
44 */
45
46
47 @SuppressWarnings("unchecked")
48 public final class FPGenerator {
49
50 /*** Return a fingerprint generator. The fingerprints generated
51 will have degree <code>degree</code> and will be generated by
52 <code>polynomial</code>. If a generator based on
53 <code>polynomial</code> has already been created, it will be
54 returned. Requires that <code>polynomial</code> is an
55 irreducible polynomial of degree <code>degree</code> (the
56 array <code>polynomials</code> contains some irreducible
57 polynomials). */
58 public static FPGenerator make(long polynomial, int degree) {
59 Long l = new Long(polynomial);
60 FPGenerator fpgen = (FPGenerator) generators.get(l);
61 if (fpgen == null) {
62 fpgen = new FPGenerator(polynomial, degree);
63 generators.put(l, fpgen);
64 }
65 return fpgen;
66 }
67 private static final Hashtable generators = new Hashtable(10);
68
69 private static final long zero = 0;
70 private static final long one = 0x8000000000000000L;
71
72
73 /*** Return a value equal (mod <code>polynomial</code>) to
74 <code>fp</code> and of degree less than <code>degree</code>. */
75 public long reduce(long fp) {
76 int N = (8 - degree/8);
77 long local = (N == 8 ? 0 : fp & (-1L << 8*N));
78 long temp = zero;
79 for (int i = 0; i < N; i++) {
80 temp ^= ByteModTable[8+i][((int)fp) & 0xff];
81 fp >>>= 8;
82 };
83 return local ^ temp;
84 }
85
86 /*** Extends <code>f</code> with lower eight bits of <code>v</code>
87 with<em>out</em> full reduction. In other words, returns a
88 polynomial that is equal (mod <code>polynomial</code>) to the
89 desired fingerprint but may be of higher degree than the
90 desired fingerprint. */
91 public long extend_byte(long f, int v) {
92 f ^= (0xff & v);
93 int i = (int)f;
94 long result = (f>>>8);
95 result ^= ByteModTable[7][i & 0xff];
96 return result;
97 }
98
99 /*** Extends <code>f</code> with lower sixteen bits of <code>v</code>.
100 Does not reduce. */
101 public long extend_char(long f, int v) {
102 f ^= (0xffff & v);
103 int i = (int)f;
104 long result = (f>>>16);
105 result ^= ByteModTable[6][i & 0xff]; i >>>= 8;
106 result ^= ByteModTable[7][i & 0xff];
107 return result;
108 }
109
110 /*** Extends <code>f</code> with (all bits of) <code>v</code>.
111 Does not reduce. */
112 public long extend_int(long f, int v) {
113 f ^= (0xffffffffL & v);
114 int i = (int)f;
115 long result = (f>>>32);
116 result ^= ByteModTable[4][i & 0xff]; i >>>= 8;
117 result ^= ByteModTable[5][i & 0xff]; i >>>= 8;
118 result ^= ByteModTable[6][i & 0xff]; i >>>= 8;
119 result ^= ByteModTable[7][i & 0xff];
120 return result;
121 }
122
123 /*** Extends <code>f</code> with <code>v</code>.
124 Does not reduce. */
125 public long extend_long(long f, long v) {
126 f ^= v;
127 long result = ByteModTable[0][(int)(f & 0xff)]; f >>>= 8;
128 result ^= ByteModTable[1][(int)(f & 0xff)]; f >>>= 8;
129 result ^= ByteModTable[2][(int)(f & 0xff)]; f >>>= 8;
130 result ^= ByteModTable[3][(int)(f & 0xff)]; f >>>= 8;
131 result ^= ByteModTable[4][(int)(f & 0xff)]; f >>>= 8;
132 result ^= ByteModTable[5][(int)(f & 0xff)]; f >>>= 8;
133 result ^= ByteModTable[6][(int)(f & 0xff)]; f >>>= 8;
134 result ^= ByteModTable[7][(int)(f & 0xff)];
135 return result;
136 }
137
138
139 /*** Compute fingerprint of "n" bytes of "buf" starting from
140 "buf[start]". Requires "[start, start+n)" is in bounds. */
141 public long fp(byte[] buf, int start, int n) {
142 return extend(empty, buf, start, n);
143 }
144
145 /*** Compute fingerprint of (all bits of) "n" characters of "buf"
146 starting from "buf[i]". Requires "[i, i+n)" is in bounds. */
147 public long fp(char[] buf, int start, int n) {
148 return extend(empty, buf, start, n);
149 }
150
151
152 /*** Compute fingerprint of (all bits of) <code>t</code> */
153
154
155
156 /*** Compute fingerprint of (all bits of) the characters of "s". */
157 public long fp(CharSequence s) {
158 return extend(empty, s);
159 }
160
161 /*** Compute fingerprint of (all bits of) "n" characters of "buf"
162 starting from "buf[i]". Requires "[i, i+n)" is in bounds. */
163 public long fp(int[] buf, int start, int n) {
164 return extend(empty, buf, start, n);
165 }
166
167 /*** Compute fingerprint of (all bits of) "n" characters of "buf"
168 starting from "buf[i]". Requires "[i, i+n)" is in bounds. */
169 public long fp(long[] buf, int start, int n) {
170 return extend(empty, buf, start, n);
171 }
172
173 /*** Compute fingerprint of the lower eight bits of the characters
174 of "s". */
175 public long fp8(String s) {
176 return extend8(empty, s);
177 }
178
179 /*** Compute fingerprint of the lower eight bits of "n" characters
180 of "buf" starting from "buf[i]". Requires "[i, i+n)" is in
181 bounds. */
182 public long fp8(char[] buf, int start, int n) {
183 return extend8(empty, buf, start, n);
184 }
185
186
187 /*** Extends fingerprint <code>f</code> by adding the low eight
188 bits of "b". */
189 public long extend(long f, byte v) {
190 return reduce(extend_byte(f, v));
191 }
192
193 /*** Extends fingerprint <code>f</code> by adding (all bits of)
194 "v". */
195 public long extend(long f, char v) {
196 return reduce(extend_char(f, v));
197 }
198
199 /*** Extends fingerprint <code>f</code> by adding (all bits of)
200 "v". */
201 public long extend(long f, int v) {
202 return reduce(extend_int(f, v));
203 }
204
205 /*** Extends fingerprint <code>f</code> by adding (all bits of)
206 "v". */
207 public long extend(long f, long v) {
208 return reduce(extend_long(f, v));
209 }
210
211 /*** Extends fingerprint <code>f</code> by adding "n" bytes of
212 "buf" starting from "buf[start]".
213 Result is reduced.
214 Requires "[i, i+n)" is in bounds. */
215 public long extend(long f, byte[] buf, int start, int n) {
216 for (int i = 0; i < n; i++) {
217 f = extend_byte(f, buf[start+i]);
218 }
219 return reduce(f);
220 }
221
222 /*** Extends fingerprint <code>f</code> by adding (all bits of) "n"
223 characters of "buf" starting from "buf[i]".
224 Result is reduced.
225 Requires "[i, i+n)" is in bounds. */
226 public long extend(long f, char[] buf, int start, int n) {
227 for (int i = 0; i < n; i++) {
228 f = extend_char(f, buf[start+i]);
229 }
230 return reduce(f);
231 }
232
233 /*** Extends fingerprint <code>f</code> by adding (all bits of)
234 the characters of "s".
235 Result is reduced. */
236 public long extend(long f, CharSequence s) {
237 int n = s.length();
238 for (int i = 0; i < n; i++) {
239 int v = (int) s.charAt(i);
240 f = extend_char(f, v);
241 }
242 return reduce(f);
243 }
244
245
246 /*** Extends fingerprint <code>f</code> by adding (all bits of)
247 // * <code>t</code> */
248
249
250
251
252
253 /*** Extends fingerprint <code>f</code> by adding (all bits of) "n"
254 characters of "buf" starting from "buf[i]".
255 Result is reduced.
256 Requires "[i, i+n)" is in bounds. */
257 public long extend(long f, int[] buf, int start, int n) {
258 for (int i = 0; i < n; i++) {
259 f = extend_int(f, buf[start+i]);
260 }
261 return reduce(f);
262 }
263
264 /*** Extends fingerprint <code>f</code> by adding (all bits of) "n"
265 characters of "buf" starting from "buf[i]".
266 Result is reduced.
267 Requires "[i, i+n)" is in bounds. */
268 public long extend(long f, long[] buf, int start, int n) {
269 for (int i = 0; i < n; i++) {
270 f = extend_long(f, buf[start+i]);
271 }
272 return reduce(f);
273 }
274
275 /*** Extends fingerprint <code>f</code> by adding the lower eight
276 bits of the characters of "s".
277 Result is reduced. */
278 public long extend8(long f, String s) {
279 int n = s.length();
280 for (int i = 0; i < n; i++) {
281 int x = (int) s.charAt(i);
282 f = extend_byte(f, x);
283 }
284 return reduce(f);
285 }
286
287 /*** Extends fingerprint <code>f</code> by adding the lower eight
288 bits of "n" characters of "buf" starting from "buf[i]".
289 Result is reduced.
290 Requires "[i, i+n)" is in bounds. */
291 public long extend8(long f, char[] buf, int start, int n) {
292 for (int i = 0; i < n; i++) {
293 f = extend_byte(f, buf[start+i]);
294 }
295 return reduce(f);
296 }
297
298
299 /*** Fingerprint of the empty string of bytes. */
300 public final long empty;
301
302 /*** The number of bits in fingerprints generated by
303 <code>this</code>. */
304 public final int degree;
305
306 /*** The polynomial used by <code>this</code> to generate
307 fingerprints. */
308 public long polynomial;
309
310 /*** Result of reducing certain polynomials. Specifically, if
311 <code>f(S)</code> is bit string <code>S</code> interpreted as
312 a polynomial, <code>f(ByteModTable[i][j])</code> equals
313 <code>mod(x^(127 - 8*i) * f(j), P)</code>. */
314 private long[][] ByteModTable;
315
316 /*** Create a fingerprint generator. The fingerprints generated
317 will have degree <code>degree</code> and will be generated by
318 <code>polynomial</code>. Requires that
319 <code>polynomial</code> is an irreducible polynomial of degree
320 <code>degree</code> (the array <code>polynomials</code>
321 contains some irreducible polynomials). */
322 private FPGenerator(long polynomial, int degree) {
323 this.degree = degree;
324 this.polynomial = polynomial;
325 ByteModTable = new long[16][256];
326
327 long[] PowerTable = new long[128];
328
329 long x_to_the_i = one;
330 long x_to_the_degree_minus_one = (one >>> (degree-1));
331 for (int i = 0; i < 128; i++) {
332
333
334
335 PowerTable[i] = x_to_the_i;
336 boolean overflow = ((x_to_the_i & x_to_the_degree_minus_one) != 0);
337 x_to_the_i >>>= 1;
338 if (overflow) {
339 x_to_the_i ^= polynomial;
340 }
341 }
342 this.empty = PowerTable[64];
343
344 for (int i = 0; i < 16; i++) {
345
346
347 for (int j = 0; j < 256; j++) {
348
349
350 long v = zero;
351 for (int k = 0; k < 8; k++) {
352
353
354 if ((j & (1 << k)) != 0) {
355 v ^= PowerTable[127 - i*8 - k];
356 }
357 }
358 ByteModTable[i][j] = v;
359 }
360 }
361 }
362
363 /*** Array of irreducible polynomials. For each degree
364 <code>d</code> between 1 and 64 (inclusive),
365 <code>polynomials[d][i]</code> is an irreducible polynomial of
366 degree <code>d</code>. There are at least two irreducible
367 polynomials for each degree. */
368 public static final long polynomials[][] = {
369 null,
370 {0xC000000000000000L, 0xC000000000000000L},
371 {0xE000000000000000L, 0xE000000000000000L},
372 {0xD000000000000000L, 0xB000000000000000L},
373 {0xF800000000000000L, 0xF800000000000000L},
374 {0xEC00000000000000L, 0xBC00000000000000L},
375 {0xDA00000000000000L, 0xB600000000000000L},
376 {0xE500000000000000L, 0xE500000000000000L},
377 {0x9680000000000000L, 0xD480000000000000L},
378 {0x80C0000000000000L, 0x8840000000000000L},
379 {0xB0A0000000000000L, 0xE9A0000000000000L},
380 {0xD9F0000000000000L, 0xC9B0000000000000L},
381 {0xE758000000000000L, 0xDE98000000000000L},
382 {0xE42C000000000000L, 0x94E4000000000000L},
383 {0xD4CE000000000000L, 0xB892000000000000L},
384 {0xE2AB000000000000L, 0x9E39000000000000L},
385 {0xCCE4800000000000L, 0x9783800000000000L},
386 {0xD8F8C00000000000L, 0xA9CDC00000000000L},
387 {0x9A28200000000000L, 0xFD79E00000000000L},
388 {0xC782500000000000L, 0x96CD300000000000L},
389 {0xBEE6880000000000L, 0xE902C80000000000L},
390 {0x86D7E40000000000L, 0xF066340000000000L},
391 {0x9888060000000000L, 0x910ABE0000000000L},
392 {0xFF30E30000000000L, 0xB27EFB0000000000L},
393 {0x8E375B8000000000L, 0xA03D948000000000L},
394 {0xD1415C4000000000L, 0xF5357CC000000000L},
395 {0x91A916E000000000L, 0xB6CE66E000000000L},
396 {0xE6D2FC5000000000L, 0xD55882B000000000L},
397 {0x9A3BA0B800000000L, 0xFBD654E800000000L},
398 {0xAEA5D2E400000000L, 0xF0E533AC00000000L},
399 {0xDA88B7BE00000000L, 0xAA3AAEDE00000000L},
400 {0xBA75BB4300000000L, 0xF5A811C500000000L},
401 {0x9B6C9A2F80000000L, 0x9603CCED80000000L},
402 {0xFABB538840000000L, 0xE2747090C0000000L},
403 {0x8358898EA0000000L, 0x8C698D3D20000000L},
404 {0xDA8ABD5BF0000000L, 0xF6DF3A0AF0000000L},
405 {0xB090C3F758000000L, 0xD3B4D3D298000000L},
406 {0xAD9882F5BC000000L, 0x88DA4FB544000000L},
407 {0xC3C366272A000000L, 0xDCCF2A2262000000L},
408 {0x9BC0224A97000000L, 0xAF5D96F273000000L},
409 {0x8643FFF621800000L, 0x8E390C6EDC800000L},
410 {0xE45C01919BC00000L, 0xCBB34C8945C00000L},
411 {0x80D8141BC2E00000L, 0x886AFC3912200000L},
412 {0xF605807C26500000L, 0xA3B92D28F6300000L},
413 {0xCE9A2CFC76280000L, 0x98400C1921280000L},
414 {0xF61894904C040000L, 0xC8BE6DBCEC8C0000L},
415 {0xE3A44C104D160000L, 0xCA84A59443760000L},
416 {0xC7E84953A11B0000L, 0xD9D4F6AA02CB0000L},
417 {0xC26CDD1C9A358000L, 0x8BE8478434328000L},
418 {0xAE125DBEB198C000L, 0xFCC5DBFD5AAAC000L},
419 {0x86DE52A079A6A000L, 0xC5F16BD883816000L},
420 {0xDF82486AAFE37000L, 0xA293EC735692D000L},
421 {0xE91ABA275C272800L, 0xD686192874E3C800L},
422 {0x963D0960DAB3FC00L, 0xBA9DE62072621400L},
423 {0xA2188C4E8A46CE00L, 0xD31F75BCB4977E00L},
424 {0xC43A416020A6CB00L, 0x99F57FECA12B3900L},
425 {0xA4F72EF82A58AE80L, 0xCECE4391B81DA380L},
426 {0xB39F119264BC0940L, 0x80A277D20DABB9C0L},
427 {0xFD6616C0CBFA0B20L, 0xED16E64117DC11A0L},
428 {0xFFA8BC44327B5390L, 0xEDFB13DB3B66C210L},
429 {0xCAE8EB99E73AB548L, 0xC86135B6EA2F0B98L},
430 {0xBA49BADCDD19B16CL, 0x8F1944AFB18564C4L},
431 {0xECFC86D765EABBEEL, 0x9190E1C46CC13702L},
432 {0xE1F8D6B3195D6D97L, 0xDF70267FF5E4C979L},
433 {0xD74307D3FD3382DBL, 0x9999B3FFDC769B48L}
434 };
435
436 /*** The standard 64-bit fingerprint generator using
437 <code>polynomials[0][64]</code>. */
438 public static final FPGenerator std64 = make(polynomials[64][0], 64);
439
440 /*** A standard 32-bit fingerprint generator using
441 <code>polynomials[0][32]</code>. */
442 public static final FPGenerator std32 = make(polynomials[32][0], 32);
443
444
445 /*** A standard 40-bit fingerprint generator using
446 <code>polynomials[0][40]</code>. */
447 public static final FPGenerator std40 = make(polynomials[40][0], 40);
448 /*** A standard 24-bit fingerprint generator using
449 <code>polynomials[0][24]</code>. */
450 public static final FPGenerator std24 = make(polynomials[24][0], 24);
451 }