CMPUT690 Term Project
Fingerprinting using Polynomial(Rabin’s method)
Calvin Chan

Hahua Lu

December 4, 2001

2

Executive Summary
The purpose of this project is to implement the Rabin’s methodof fingerprinting using irreducible polynomials. This project
team has successfully implemented the method and test run ona given dataset. Test results show that the time efficiency of thismethod is comparable to the other well known hashing functions while outperfoming them in the sense of lower or even nocollision occurences.

3

4

Table of Contents

1

2Introduction

7

1.1

Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.1.1

Terms of Reference . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.1.2

Project Team Members . . . . . . . . . . . . . . . . . . . . . . . .

7

1.2

Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.3

Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8Rabin’s method

9

2.1

Method Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.1.1

The Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.1.2

Bound of Error . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.1.3

Properties and Characteristics . . . . . . . . . . . . . . . . . . . . 11

2.2

2.3

3

Irreducible Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1

Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.2.2

Algorithm for generation . . . . . . . . . . . . . . . . . . . . . . . 12

An Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1

Mathematical Work . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.3.2

Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3.3

Implementation Scheme . . . . . . . . . . . . . . . . . . . . . . . 23

Hashing Algorithms

25
5

4

5

6

7

3.1

General Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.2

Scheme djb2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.3

Scheme sdbm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.4

Horner’s Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.5

Conversion function url2pid() . . . . . . . . . . . . . . . . . . . . . . . . . 26

The Experiment

27

4.1

Test Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.2

Outline of Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.3

Details of the Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Results and Analyses

29

5.1

Test Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5.2

Analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.2.1

Expected Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

5.2.2

Actual Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

5.2.3

Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5.2.4

Fingerprint method . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Conclusion

35

6.1

Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

6.2

Related and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6.2.1

Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

6.2.2

Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

Source Codes

37

7.1

Source Codes for Fingerprinting . . . . . . . . . . . . . . . . . . . . . . . 37

7.2

Source Codes for “url2pid” . . . . . . . . . . . . . . . . . . . . . . . . . . 45

6

Chapter 1
Introduction
1.1

Reference

1.1.1 Terms of ReferenceThis term project is carried out with the purpose of fulfilling the course requirement of
CMPUT690.
CMPUT690 is a graduate course in Advanced Database Systems offered by the Departmentof Computing Science, Faculty of Science, University of Alberta. The instructor of thecourse is Professor Davood Rafiei.

1.1.2 Project Team Members
The project team consists of the following team members:• Calvin Chan
• Hai-Hua Lu

1.2

Motivation

Traditionally, a hashing function is used to map a character string of undetermined length
to a storage address. The mapping is done by computing the residue of that string, viewed
as a large integer, modulo p - a prime number[1].
7Since this is a mapping from an unbounded domain into a finite range of integers, it would
be very difficult to devise a good hashing function that will produce a set of distinct mappedvalues with minimal chance of collisions. This is especially true when the set of character
strings to be mapped is of a huge size.
In 1981, Michael O. Rabin published a paper [1] descibing a fingerprinting method using
polynomials. It is claimed that the method provides efficient mapping that has little chanceof collision even with huge dataset.

1.3

Objectives

In this project, it is intended to achieve the followings:§ to implement the Rabin’s method and to test it against a dataset§ to examine the relationship between the percentage of collisions (distinct strings withthe same fingerprint) and the degree of the chosen irreducible polynomial§ to compare the effectiveness of using Rabin’s method with that of using hashing
functions8

Chapter 2
Rabin’s method
2.1

Method Outline

2.1.1 The Scheme
Suppose the character string A is a bit string containing m bits [b1 , . . . , bm ]. It is thenassociated to a polynomial of degree (m − 1) in indeterminate t as follows.
A(t) = b1 tm−1 + b2 tm−2 + . . . + bm−1 t + bm
Given a polynomial P(t) of degree k,P(t) = a1 tk + a2 tk−1 + . . . + ak−1 t + ak
the residue f (t) = A(t) mod P(t) will be of degree (k − 1).
In Rabin’s fingerprinting method, an irreducible polynomial is used for P(t). More details
about irreducible polynomials can be found in section 2.2. Since we are dealing with bit
strings, all the coefficients of A(t) are in Z2 . Thus P(t) will be chosen using ai ’s in Z2 .
With this in mind, the fingerprinting function is defined as follows:
Definition

Given a character string A, the fingerprint of A isf (A) = A(t) mod P(t)2.1.2 Bound of Error
In his paper [1], Rabin finds a bound for error in the steps as follows:
9(1)

1. The number of irreducible polynomial P(t) of degree k is
2k − 22k≈kk.
2. Given a dataset S containing n character strings of maximum length m bits, constructa polynomial
Y
Q(t) =(A(t) − B(t)){A,B∈S}.

3. If degree of Q(t) = degQ, thenX
degQ =deg (A(t) − B(t)){A,B∈S}≤X

max{deg A(t), deg B(t)}{A,B∈S}≤X

m{A,B∈S}≤ n2 m2≤ n km .
4. Maximum number of irreducible factors of degree k of Q(t) = degQk
5. For f (A) = f (B) given A 6= B, one must have P(t) | (A(t)−B(t)) and P(t) | Q(t).
6. Probability of making an error = probability of picking a factor of Q(t)7. The bound of error is estimated as
degQ  2k − 2
k
k
degQ
≈
2k
2
nm
≤ k
2

P r{f (A) = f (B) | A =6 B} =

Rabin [1] suggests two ways to lower the probability of error:• The probability of a wrong output will be lowered by increasing the value of k. This
will require a larger word-length.
• The probability can also be lowered by using two different irreducible polynomials
P1 (t) and P2 (t) of the same degree k. The algorithm is then run twice by interleaving
steps, one time with P1 (t) and another time with P2 (t). Since the error probabilities
are independent, the maximum probability of collision becomes
n2 m
.
22k
10

2.1.3 Properties and Characteristics
The general features are specialized for this project (domain in Z2 ) as follows[2]:1. A(t) + B(t) ≡ A XOR B
2. A(t)t ≡ A << 1
proof
If

A(t) = a1 tm + a2 tm−1 + . . . + am−1 t + am ,then

A(t)t = (a1 tl + a2 tl−1 + . . . + al−1 t + al )t= a1 tl+1 + a2 tl + . . . + al−1 t2 + al t + 0

3. p1 tk mod P(t) is equivalent to dropping the leading bit off P(t)proof
If p1 = 0, then

p1 tk mod P(t) = 0

If p1 = 1 andP(t) = p1 tk + p2 tk−1 + . . . + pk−1 t + pk ,then

p1 tk = P(t) − p2 tk−1 − . . . − pk−1 t − pk
p1 tk mod P(t) = −p2 tk−1 − . . . − pk−1 t − pk
= p2 tk−1 + . . . + pk−1 t + pk = P(t) − p1 tk

4. f (A + B) = f (A) + f (B)
5. f (concat(A, B)) = f (concat(f (A), B))
6. If B is of length l, thenf (concat(A, B)) = {A(t)tl + B(t)} mod P(t)= f (f (A) ∗ f (tl )) + f (B)
7. 1-bit extensionIff ([a1 , . . . , al ]) = (a1 tl + a2 tl−1 + . . . + al−1 t + al ) mod P(t)= r1 tk−1 + r2 tk−2 + . . . + rk−1 t + rk

thenf ([a1 , . . . , al+1 ]) = (a1 tl+1 + a2 tl + . . . + al−1 t2 + al t + al+1 ) mod P(t)= (t(a1 tl + a2 tl−1 + . . . + al−1 t + al ) + al+1 ) mod P(t)= t(a1 tl + a2 tl−1 + . . . + al−1 t + al ) mod P(t) + al+1 mod P(t)= (r1 tk + r2 tk−1 + . . . + rk−1 t2 + rk t + al+1 ) mod P(t)= r2 tk−1 + . . . + rk−1 t2 + rk t + al+1 +|{z}(f ([a1 ,...,al ])<<1), input al+1

|

{z

XOR

11

r1 tk mod P(t)|{z}drop leading bit of P(t) conditioned on r1

}

2.2

Irreducible Polynomials

Irreducible polynomial is a topic in the ”finite fields” area and is not within the scope of
this project. However, it would definitely help if a short note about irreducible polynomials
is included in this chapter. A full discussion is too broad to be included so only a simplified
version is included.

2.2.1 Criteria
From literatures[3, 4] of related topics, one can identify the following characteristics ofirreducible polynomials in Z2 :• The Galois Field Z2 = {0, 1}.
• Given P(t) = a1 tk + a2 tk−1 + . . . + ak−1 t + ak in Z2 of degree k, the following
holds:(
a1 = 1ai ∈ Z2 , ∀ i ∈ {1, . . . , k}
• All polynomials P(t) with no constant term must be factorable.
• P(t) is irreducible if P(t) does not evaluate to 0 for all elements of Z2 .
For
P(t) = a1 tk + a2 tk−1 + . . . + ak−1 t + ak
to be irreducible,one can conclude the following criteria based on the above characteristics:
1. ai ∈ Z2 , ∀ i ∈ {1, . . . , k}
2. a1 = 1
3. ak = 1
4. P(t) 6= 0, ∀ t ∈ Z2

orP(t) = 1, ∀ t ∈ Z2

2.2.2 Algorithm for generation
From the criteria set in the previous section, one can see that P(t) = 1 when t = 0. Thus,
0 is definitely not a zero of P(t).
When t = 1, P(t) will evaluate to 0 when there is an even number of ai 6= 0. Thus, there
must be an odd number of ai 6= 0 in order that P(t) does not evaluate to 0. In other words,
P(t) is irreducible if there is an odd number of ai 6= 0.
12

When P(t) is of degree k, it requires k + 1 bits to represent the polynomial. In otherwords, a polynomial of degree 64 needs 65 bits. In C, word length is 32 bits. In order tomake full use of the word size, it is decided to drop the MSB since it is always 1. The
following algorithm is designed for the purpose of generating an irreducible polynomial in
Z2 of degree k (multiples of 32). The result will be stored in 32-bit words Wj with the
MSB dropped.

Pre-condition: k ≥ 0 and 32 | k.
h  i
1. int r := random number ∈ 0, k−1−
1
2
2. r := 2r + 1
3. A := int Array[0 . . . k − 1],

A[i] := 0, ∀ i ∈ {0, . . . , k − 1}

4. A[0] := 1
5. For i := 1 . . . r, dorepeatint j := random number ∈ [0, k − 2]
until A[j + 1] == 0
A[j + 1] := 1i := i + 1
enddo
6. n := k div 32
7. For j := 1, . . . , n do
Wj := 0For i := 32 ∗ j − 1, 32 ∗ j − 2, . . . , 32 ∗ j − 32 do
Wj := 2 ∗ Wj + A[i]
enddo
enddo
Post conditions:
P div 32
1. sum := kj=1
Wj ∗ 2j−1 representsin binary form P(t) with MSB dropped.
2. Wj , j = 1, . . . , n are the n 32-bit words storing sum,
3. P(t) (with MSB dropped) is represented in the form [Wn , . . . , W2 , W1 ]

13

2.3

An Implementation

Andrei Broder [5] has proposed an implementation scheme for Rabin’s method for k = 64.
Since no mathematical work supporting this scheme is included in the paper, it is difficult
to follow and to extend to other values of k. In order to allow the readers to appreciate
the scheme and to allow implementers to extend the application to other values of k, themathematical work is reproduced in section 2.3.1.

2.3.1 Mathematical Work2.3.1.1

NotationsBits, Bytes and Words
wi 7→ ith bit of W,

Wi 7→ ith byte of W,

L[i] 7→ ith word of L

Given a byte B, B = [b1 , b2 , . . . , b7 , b8 ]Given a 32-bit word W,
W = [w1 , w2 , . . . , w31 , w32 ] = [W1 , W2 , W3 , W4 ]Given a 64-bit value D,
D = [d1 , d2 , . . . , d63 , d64 ] = [D1 , D2 , . . . D7 , D8 ]D[1] = [D1 , D2 , D3 , D4 ]
D[2] = [D5 , D6 , D7 , D8 ]Given a 96-bit value L,
L = [l1 , l2 , . . . , l95 , l96 ] = [L1 , L2 , . . . L11 , L12 ]L[1] = [L1 , L2 , L3 , L4 ]L[2] = [L5 , L6 , L7 , L8 ]L[3] = [L9 , L10 , L11 , L12 ]Associated polynomials
If W = [W1 , W2 , W3 , W4 ], then.
W(t) = W1 (t)t24 + W2 (t)t16 + W3 (t)t8 + W4 (t).
W1 (t) = w1 t7 + w2 t6 + w3 t5 + w4 t4 + w5 t3 + w6 t2 + w7 t + w8.
W2 (t) = w9 t7 + w10 t6 + w11 t5 + w12 t4 + w13 t3 + w14 t2 + w15 t + w16.
W3 (t) = w17 t7 + w18 t6 + w19 t5 + w20 t4 + w21 t3 + w22 t2 + w24 t + w24.
W4 (t) = w25 t7 + w26 t6 + w27 t5 + w28 t4 + w29 t3 + w30 t2 + w31 t + w32
Fingerprinting
S = processed string with fingerprint Fc = f (S)W = [Wa , W2 , W3 , W4 ] = next word to be processed
Fn = the new fingerprint = f (concat(S, W))
14

2.3.1.2

For k = deg(P(t)) = 32
Fc = [Fc1 , Fc2 , Fc3 , Fc4 ]By property 5 and 6 of section 2.1.3, we have
Fn = f (concat(S, W))= f (concat(Fc , W))= (Fc (t)t32 + W(t)) mod P(t)= (Fc (t)t32 ) mod P(t) + W(t)) mod P(t)= (Fc1 (t)t56 + Fc2 (t)t48 + Fc3 (t)t40 + Fc4 (t)t32 + W(t)) mod P(t)= TA(t) + TB(t) + TC(t) + TD(t) + T W (t)TA(t) = (Fc1 (t)t56 ) mod P(t)TB(t) = (Fc2 (t)t48 ) mod P(t)TC(t) = (Fc3 (t)t40 ) mod P(t)TD(t) = (Fc4 (t)t32 ) mod P(t)T W (t) = W(t) mod P(t)

where

Thus,

2.3.1.3.
Fn = TW XOR TA XOR TB XOR TC XOR TD(2)

For k = deg(P(t)) = 64
Fc = [Fc1 , Fc2 , . . . Fc7 , Fc8 ] = Fc [1], Fc [2]By property 5 and 6 of section 2.1.3, we have
Fn =f (concat(S, W))=f (concat(Fc , W))=(Fc (t)t32 + W(t)) mod P(t)=(t32 {t32 Fc [1](t) + Fc [2](t)} + W(t)) mod P(t)=(Fc1 (t)t88 + Fc2 (t)t80 + Fc3 (t)t72 + Fc4 (t)t64 + Fc [2](t)t32 + W(t)) mod P(t)= TA[1](t)t32 + TA[2](t) + TB[1](t)t32 + TB[2](t) + TC[1](t)t32 + TC[2](t)
|
{z
} |
{z
} |
{z
}
from Fc1 (t)t88 mod P(t)from Fc2 (t)t80 mod P(t)from Fc3 (t)t72 mod P(t)+ TD[1](t)t32 + TD[2](t) +Fc [2](t)t32 + W(t)|{z}from Fc4 (t)t64 mod P(t)=t32 {Fc [2](t) + TA[1](t) + TB[1](t) + TC[1](t) + TD[1](t)}+ {W(t) + TA[2](t) + TB[2](t) + TC[2](t) + TD[2](t)}=Fn [1](t)t32 + Fn [2](t)Thus,.
Fn [1] = Fc [2] XOR TA[1] XOR TB[1] XOR TC[1] XOR TD[1].
Fn [2] = W XOR TA[2] XOR TB[2] XOR TC[2] XOR TD[2]
15

(3)
(4)

2.3.1.4

For k = deg(P(t)) = 96
Fc = [Fc1 , Fc2 , . . . Fc11 , Fc12 ] = Fc [1], Fc [2], Fc [3]By property 5 and 6 of section 2.1.3, we have

Fn =f (concat(S, W)) = f (concat(Fc , W))=(Fc (t)t32 + W(t)) mod P(t)=(t32 {t64 Fc [1](t) + t32 Fc [2](t) + Fc [3](t)} + W(t)) mod P(t)=(Fc1 (t)t120 + Fc2 (t)t112 + Fc3 (t)t104 + Fc4 (t)t96 + Fc [2](t)t64 + Fc [3](t)t32 + W(t)) mod P(t)= TA[1](t)t64 + TA[2](t)t32 + TA[3](t) + TB[1](t)t64 + TB[2](t)t32 + TB[3](t)
|
{z
} |
{z
}
from Fc1 (t)t120 mod P(t)64from Fc2 (t)t112 mod P(t)32

+ TC[1](t)t + TC[2](t)t + TC[3](t) + TD[1](t)t64 + TD[2](t)t32 + TD[3](t)
|
{z
} |
{z
}
from Fc3 (t)t104 mod P(t)from Fc4 (t)t96 mod P(t)+ Fc [2](t)t64 + Fc [3](t)t32 + W(t)=t64 {Fc [2](t) + TA[1](t) + TB[1](t) + TC[1](t) + TD[1](t)}+ t32 {Fc [3](t) + TA[2](t) + TB[2](t) + TC[2](t) + TD[2](t)}+ {W(t) + TA[3](t) + TB[3](t) + TC[3](t) + TD[3](t)}=Fn [1](t)t64 + Fn [2](t)t32 + Fn [3](t)Thus,

2.3.1.5.
Fn [1] = Fc [2] XOR TA[1] XOR TB[1] XOR TC[1] XOR TD[1].
Fn [2] = Fc [3] XOR TA[2] XOR TB[2] XOR TC[2] XOR TD[2].
Fn [3] = W XOR TA[3] XOR TB[3] XOR TC[3] XOR TD[3]

(5)
(6)
(7)

Summary of Operations for Implementation

From works in this section (equations 2 to 7), the following is a summary of the essentials
for the implementation of Rabin’s method.
k = deg P(t)Fingerprint Value
Processes
Basic Operations

32
Fn = [Fn1 , Fn2 , Fn3 , Fn4 ].
Fn = T W XOR TA XOR TB XOR TC XOR TD
TA(t) = (Fc1 (t)t56 ) mod P(t)TB(t) = (Fc2 (t)t48 ) mod P(t)TC(t) = (Fc3 (t)t40 ) mod P(t)TD(t) = (Fc4 (t)t32 ) mod P(t)T W (t) = W(t) mod P(t)16k = deg P(t)Fingerprint Value
Processes
Basic Operations

k = deg P(t)Fingerprint Value
Processes

Basic Operations

2.3.2

64


Fn = [Fn1 , . . . , Fn8 ] = Fn [1], Fn [2].
Fn [1] = Fc [2] XOR TA[1] XOR TB[1] XOR TC[1] XOR TD[1].
Fn [2] = W XOR TA[2] XOR TB[2] XOR TC[2] XOR TD[2]TA(t) = (Fc1 (t)t88 ) mod P(t)TB(t) = (Fc2 (t)t80 ) mod P(t)TC(t) = (Fc3 (t)t72 ) mod P(t)TD(t) = (Fc4 (t)t64 ) mod P(t)96Fn = [Fn1 , . . . , Fn12 ] = Fn [1], Fn [2], Fn [3].
Fn [1] = Fc [2] XOR TA[1] XOR TB[1] XOR TC[1] XOR TD[1].
Fn [2] = Fn [3] XOR TA[2] XOR TB[2] XOR TC[2] XOR TD[2].
Fn [3] = W XOR TA[3] XOR TB[3] XOR TC[3] XOR TD[3]TA(t) = (Fc1 (t)t120 ) mod P(t)TB(t) = (Fc2 (t)t112 ) mod P(t)TC(t) = (Fc3 (t)t104 ) mod P(t)TD(t) = (Fc4 (t)t96 ) mod P(t)Implementation Issues

To implement the Rabin’s method of fingerprinting, several issues have to be dealt with.
These include the choice of programming language, representation of the irreducible polynomial and the fingerprint value, and implementing the basic operations. These will be
discussed in the subsequent sections.

2.3.2.1

Programming Language

It is decided to use C++ as the programming language for implementing Rabin’s method
for the following reasons:
1. Embedded SQL can be used with C language. This facilitates the access of thedatabase storing snapshots of webpages and their URLs which may be used as thedataset for the experiments in this project. Embedded SQL also facilitates the direct
manipulation of data in databases.
2. Language C permits low level programming which is required to implement the Rabin’s method using bit shift and bit-wise exclusive OR operations.
3. Language C++ permits use of codes written in C and also allows object-oriented
programming which may make coding in the project easier.
172.3.2.2

Representation

As discussed in section 2.2, the irreducible polynomial with the MSB dropped will be
stored in several 32-bit words. This can also be used for storing the fingerprint value.
When using P(t) of degree k, k bits will be required to store the fingerprint value.
In order to genrealize the codes, the following scheme is used to store the fingerprint valuef (S) and P(t):1. The values will be stored in n =k32

32-bit words.

2. The n 32-bit words will be stored in a data structure (array).
3. The first element of the array is the word containing the LSB.

2.3.2.3

Bit Shift

From properties listed in section 2.1.3, one can see that most of the operations requiredfor implementing Rabin’s method need low level bits shifting and bitwise exclusive OR.
However, these operations are available to 32 bit words only. Thus, a set of special procedures are required for implementing shifts for word size greater than 32 bits. The following
blocks are written for k > 32 with sWord representing the data structure containing theword to be operated on.

void longLeftShift(int * sWord, int s) {int len = number of elements contained in sWord;
int temp;
int mask = 0x00000000;// generate mask for extracting s bitsfor (int i = 0; i < s; i++)mask = mask << 1 | 0x00000001;
for (int i = len - 1; i > 0; i--) {// extract s highest bits from lower word
temp = sWord[i - 1] >> (32 - s) & mask;// insert as s lowest bits in higher word
sWord[i] = sWord[i] << s | temp;}
sWord[0] = sWord[0] << s}18Computing W(t) mod P(t)2.3.2.4

Using the same notation used in section 2.3.1, W is a 32 bit word. Thus W(t) is of degree
31 and we haveW(t) mod P(t) = W(t)∀k ≥ 32

As we are only dealling withk ≥ 32in this project, the above relation holds for all computation in this project.

Computing i × t8 mod P(t)2.3.2.5

Another commonly found operation in the implementation is i × t8 mod P(t) where 0 ≤i ≤ 255 and i is stored in the lowest byte of W. This can be achieved by applying property
7 of section 2.1.3 eight times. Once again, all P(t) representations are with MSB dropped.
With sWord and P denoting W and P(t), the code block is as follows:

void multiT8(int * sWord, int * P){
int len = number of elements contained in sWord;
int needXOR;
for (int i = 0; i < 8; i++) {// XOR conditioned on MSB
needXOR =((sWord[len - 1] & 0x80000000) == 0x80000000);// left shift 1 bit
longLeftShift(sWord, 1);
if( ( needXOR ) {for (int j = 0; j < len; j++) {sWord[j] = sWord[j] ∧ P[j];
}
}
}
}

19

Computing i × tk−8 mod P(t)2.3.2.6

Since i is an 8-bit value stored in a 32-bit word and the associated polynomial is of degree
7, i × tk−8 mod P(t) can be found by putting the 8 bits as the 8 MSB of the result whichis stored in sWord.

void byteShift(int *sWord, int i){
int len = number of elements contained in sWord;sWord[len - 1] = i << 24;
for (int j = 0; j < len - 1; j++) {sWord[j] = 0x00000000;}}

2.3.2.7

Pre-computed Table

In section 2.3.1, equations (2) to (7) indicates that TA, TB, TC and TD values are frequently
used to compute the fingerprint values. Since a byte can only take values between 0 and
255, it is efficient to have all possible values of TA, TB, TC and TD to be pre-computed
and stored in a table for future reference. Suppose the tables are known as TA, TB, TC andTD, we find the following relationships:

TD[i] = i ∗ tk mod P(t) = (i ∗ tk−8 ) ∗ t8 mod P(t)TC[i] = i ∗ t(k+8) mod P(t) = TD[i] ∗ t8 mod P(t)TB[i] = i ∗ t(k+16) mod P(t) = TC[i] ∗ t8 mod P(t)TA[i] = i ∗ t(k+24) mod P(t) = TB[i] ∗ t8 mod P(t)This can achieved by applying the code blocks discussed in the previous two sections repeatedly. Once again, with P denoting P(t), the code block for computing the tables (TA,TB, TC and TD), which are assumed to be globally accessible, is as follows:20

void computeTable( int * P ) {int len = number of elements contained in sWord;for (int i = 0; i < 256; i++) {for (int j = 0; j < len; j++) {TD[i][j] = 0;}
byteShift(TD[i], i);
multiT8(TD[i], P);// TD[i] = i × tk−8// TD[i] = i × t8

for (int j = 0; j < len; j++) {TC[i][j] = TD[i][j];}multiT8(TC[i], P);
for (int j = 0; j < len; j++) {TB[i][j] = TC[i][j];}multiT8(TB[i], P);
for (int j = 0; j < len; j++) {TA[i][j] = TB[i][j];}multiT8(TA[i], P);}}

2.3.2.8

Fingerprinting (concatenating 4-character string)

According to work in section 2.3.1.5, each cycle of computation will take on 4 bytes. Suppose the next 4 characters to be concatenated are contained in 32-bit word W as [W1, W2,
W3, W4]. Assuming that the previous fingerprint value is stored in sWord and P(t) representated by P, the function to compute the new fingerprint will be as shown below basedon equations 2 to 7 and the assumption that the tables (TA, TB, TC and TD) are globally
accessible:
21

void fp4(int * sWord, char W1, char W2, char W3,
char W4){
int len = number of elements contained in sWord;
int f1 = sWord[len - 1] >> 24 & 0xffff;
int f2 = sWord[len - 1] >> 16 & 0xffff;
int f3 = sWord[len - 1] >> 8 & 0xffff;
int f4 = sWord[len - 1] & 0xffff;
int W = (((W | W1) << 8 | W2) << 8 | W3) << 8 |W4;for (int j = len - 1; j > 0; j--) {sWord[j] = sWord[j - 1] ∧ TA[f1][j] ∧TB[f2][j] ∧ TC[f3][j] ∧ TD[f4][j];}sWord[0] = W ∧ TA[f1][0] ∧ TB[f2][0] ∧ TC[f3][0]∧ TD[f4][0];}2.3.2.9

Fingerprinting (concatenating 1 character)

The sitauation that the end chunk of a string is not a 32-bit word can be handled by dealing
with 1 character at a time using property 7 of section 2.1.3. Code block as follows:

void fp1(int * sWord, int * P, char S){
int len = number of elements contained in sWord;
int W, needXOR;
for (int i = 0; i < 8; i++) {needXOR = (sWord[len - 1] & 0x80000000);
W = S & 0x80;
S = S << 1;longLeftShift(sWord, 1);sWord[0] = sWord[0] | (W >> 7);
if ( needXOR ) {for (int j = len - 1; j >= 0; j --) {sWord[j] = sWord[j] ∧ P[j];
}
}
}
}

22

2.3.3 Implementation Scheme
This scheme is designed for k ≥ 32 based on discussions in the previous sections. The
source codes of this implementation is included in the section 7.1.

Pre-condition:

S is a non-zero length character string

1. Obtain P(t) of degree k and store as P
2. computeTable
3. set F = 0
4. int n := len(S) div 4
5. For i := 1 . . . n, do
Performfp4(*F, S[4*i-4], S[4*i-3], S[4*i-2], S[4*i-1])
enddo
6. For each of the character c in the remaining chunk,doPerform fp1(F, P, c)
enddo
Post condition: f (S) is stored as F

23

24

Chapter 3
Hashing Algorithms
3.1

General Considerations

In this project, result of using Rabin’s method will be compared with those using hasing functions. Four schemes have been chosen after evaluating several published hashingmethods. they are described in the following sections.

3.2

Scheme djb2

Dan Bernstein [6] reported this algorithm many years ago. The code block is included below for reference. The codes are self-explanatory.

unsigned int djb2( char* str ) {unsigned int hash = 5381;
int c;
while ( c = *str++ )hash = ((hash << 5) + hash) + c;// hash * 33 + creturn hash;
}

25

3.3

Scheme sdbm

It is reported [6] that this algorithm is created for the sdbm database library. The underlying
function ishash(i) = hash(i − 1) ∗ 65599 + str[i]unsigned int sdbm( char* str ) {unsigned int hash = 0; int c;
while ( c = *str++ )hash = c + (hash << 6) + (hash << 16) - hash;return hash;}

3.4

Horner’s Rule

Bruno Preiss [7] adopted the Horner’s rule1 to write the following hashing function.

unsigned int hhash( char* str ) {unsigned int hash = 0;
int c;
while ( c = *str++ )hash = hash << 7 ∧ c;return hash;}

3.5

Conversion function url2pid()This is a conversion function used in the database storing the target dataset for convertinga character string into an 8 byte character string used as identifying key. The codes can befound in the section 7.2.
1Pn
By Horner’s rule, the value result = i=0 ai xi can be found by the algorithm:
result := an ; for i := n - 1,. . . ,1,0 result := result * x + ai

26

Chapter 4
The Experiment
4.1

Test Objects

The experiment is designed to find out the following:
I the dependency of the percentage of collisions (distinct strings with the same fingerprint) and the choice of P(t) of the same degree k
I the relationship between the percentage of collisions (distinct strings with the same
fingerprint) and the degree of P(t)I the effectiveness of using Rabin’s method with that of using hashing functions
I the efficiency of Rabin’s method in terms of CPU time required as compared withthe time required using various hashing fuctions

4.2 Outline of Experiment
One of the tables stored in the research databases1 contains a collection of the URL of morethan 23.5 million web pages. These URLs will be the target strings to be fingerprinted. The
records are also recorded in a text file with each record contained in one single line of text.
Each line of text contains data in the order as follows:name of attributes data format descriptionspidchar(8)page identityurlchar(128)
first part of the URL
url2char(872)
remaining part of the URL
1

At the time of the project, it is located at /usr/bluesky-r1/cmput690/db2/

27

4.3

Details of the Experiment

The following tests will be performed on the dataset:
1. For each S of the URLs, find f (S) using various P(t) of degree 32, 64 and 96.
2. For each S of the URLs, find djb2(S)
3. For each S of the URLs, find sdbm(S)4. For each S of the URLs, find hhash(S)5. For each S of the URLs, find url2pid(S)6. Each of the finerprints and hash values obtained is stored in a separate text file
7. For each of the above tests, log the CPU time required
8. For each of the above tests, find out the number of duplicate values for distinct URLs
using the sort function

28

Chapter 5
Results and Analyses
5.1

Test Results

When the compiled program is executed, results were recorded in various output log files.
These files are processed and merged into one single result file. The file contents areincluded below for analysis. In order to have a fair comparison in time efficiency, only
the CPU time for each process is measured.
Size of dataset = 23743961****************************************The polynomial is of degree 32
Irreducible polynomial used is 1 4D96487B
Total CPU time for 32 bit fingerprinting = 1617.080000 seconds
Size after removing duplicates = 23678578 f32_1.txt****************************************The polynomial is of degree 32
Irreducible polynomial used is 1 2DC7EEB3
Total CPU time for 32 bit fingerprinting = 1583.680000 seconds
Size after removing duplicates = 23678346 f32_2.txt****************************************The polynomial is of degree 32
Irreducible polynomial used is 1 1100C021
Total CPU time for 32 bit fingerprinting = 1504.040000 seconds

29

Size after removing duplicates = 23678200 f32_3.txt****************************************The polynomial is of degree 32
Irreducible polynomial used is 1 53BCFEDB
Total CPU time for 32 bit fingerprinting = 1506.460000 seconds
Size after removing duplicates = 23678797 f32_4.txt****************************************The polynomial is of degree 32
Irreducible polynomial used is 1 00401003
Total CPU time for 32 bit fingerprinting = 1404.200000 seconds
Size after removing duplicates = 23678626 f32_5.txt****************************************The polynomial is of degree 64
Irreducible polynomial used is 1 460C8808 10028043
Total CPU time for bit fingerprinting = 2005.600000 seconds
Size after removing duplicates = 23743961 f64_1.txt****************************************The polynomial is of degree 64
Irreducible polynomial used is 1 7523C013 A96DD7FF
Total CPU time for 64 bit fingerprinting = 1775.430000 seconds
Size after removing duplicates = 23743961 f64_2.txt****************************************The polynomial is of degree 64
Irreducible polynomial used is 1 7FABFBF6 5FFFFEFF
Total CPU time for 64 bit fingerprinting = 1804.740000 seconds
Size after removing duplicates = 23743961 f64_3.txt****************************************The polynomial is of degree 64
Irreducible polynomial used is 1 01751A98 4D90AF2730

Total CPU time for 64 bit fingerprinting = 1846.320000 seconds
Size after removing duplicates = 23743961 f64_4.txt****************************************The polynomial is of degree 64
Irreducible polynomial used is 1 77FFFFFF FFDFFFBF
Total CPU time for 64 bit fingerprinting = 1884.140000 seconds
Size after removing duplicates = 23743961 f64_5.txt****************************************The polynomial is of degree 96
Irreducible polynomial used is 1 0200100A A0300111 2125200D
Total CPU time for bit fingerprinting = -1934.287296 seconds
Size after removing duplicates = 23743961 f96_1.txt****************************************The polynomial is of degree 96
Irreducible polynomial used is 1 6FF7FFFF FFFE797F FFFFFFFF
Total CPU time for 96 bit fingerprinting = 1960.210000 seconds
Size after removing duplicates = 23743961 f96_2.txt****************************************The polynomial is of degree 96
Irreducible polynomial used is 1 62500258 258182C6 D985013D
Total CPU time for 96 bit fingerprinting = 1888.950000 seconds
Size after removing duplicates = 23743961 f96_3.txt****************************************The polynomial is of degree 96
Irreducible polynomial used is 1 7FFFFFFF FBFFFFFF FFEBFFFF
Total CPU time for 96 bit fingerprinting = 1872.290000 seconds
Size after removing duplicates = 23743958 f96_4.txt****************************************The polynomial is of degree 96

31

Irreducible polynomial used is 1 01040008 00466C86 04001109
Total CPU time for 96 bit fingerprinting = 1989.230000 seconds
Size after removing duplicates = 23743961 f96_5.txt****************************************
Hashing result
Hashing algorithm used : djb2
Total CPU time for hashing = 1068.070000 seconds
Size after removing duplicates = 23677811 hash1.dat****************************************
Hashing result
Hashing algorithm used : sdbm
Total CPU time for hashing = 1134.640000 seconds
Size after removing duplicates = 23678248 hash2.dat****************************************
Hashing result
Hashing algorithm used : Horner’s rule
Total CPU time for hashing = 1273.920000 seconds
Size after removing duplicates = 724143 hash3.dat****************************************
Hashing result
Hashing algorithm used : url2pid
Total CPU time for hashing = 2121.483520 seconds
Size after removing duplicates = 23736299 dhash.dat****************************************

32

5.2

Analyses

5.2.1 Expected Errors
Given the context of this experiment, the number of collisions expected in each of theexperiments can be calculated according to the bound of error (2.1.2) proposed by Rabinin his paper [1] as follows:n = number of character strings= 23, 743, 961
m = maximum length of strings in bits
= 8 × 1, 000 = 8, 000
For k = 32, P r ≤ 1.05 × 1011 %,maximum collisions = 23, 743, 961
For k = 64, P r ≤ 24.45%,
maximum collisions = 5, 805, 368−9
For k = 96, P r ≤ 5.69 × 10 %,maximum collisions = 1.35 × 10−3 ≈ 0
In case k = 32, the bound of error is meaningless since it is over 1. This is an indicationthat the value of k should be changed according to the expected total number of candidates
for fingerprinting in order to have a quality output.

5.2.2

Actual Results

As the results file is lengthy, the data are processed and organized into tabular form for easy
reference.
algorithm
32-bit fingerprinting

64-bit fingerprinting

96-bit fingerprinting

hashing - djb2
hashing - sdbm
hashing - Horner’s rulehashing - url2pid

run
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
1
1
1

CPU time (sec)
1,617.08
1,583.68
1,504.04
1,506.46
1,404.20
2,005.60
1,775.43
1,804.74
1,846.32
1,884.14-1,934.29
1,960.21
1,888.95
1,872.29
1,989.23
1,068.07
1,134.64
1,273.92
2,121.48
33

collisions
65,38365,61565,761
65,16465,335
0
0
0
0
0
0
0
0
2
0
66,15065,71323,019,818
7,662% collisions
0.275%
0.276%
0.277%
0.274%
0.275%
0%
0%
0%
0%
0%
0%
0%
0%
≈ 0%
0%
0.279%
0.277%
96.95%
0.032%

5.2.3 Comparisons
5.2.3.1

Note of abnormality

The negative time recorded for the first run with 96 bits fingerprinting method is due to thefact that the codes for that run was not written with the expectation of counter overflow.
This was fixed in the subsequent runs.

5.2.3.2

Collisions

All schemes used in this project are performing well with the exception of the Horner’s rule
which is therefore not included in this discussion any more. As expected, the fingerprint
methods using 64 bits or more give promising results. Fingerprint method employing only
32 bits is simliar to the other hashing functions and thus has errors of the same order ofmagnitude as the others. The url2pid algorithm seems to be edging the other functions ofsimilar base.

5.2.3.3

Time efficiency

While the url2pid algorithm gives a better result (among those 32-bit based algorithms), it is
the slowest of all. The fingerprint methods perform consistently independent of the degreeof the irreducible plynomial. Of the 32-bit based functions, the two hashing functions
namely djb2 and sdbm are the most efficient ones. This explains why they have good
reputation within the community.

5.2.4 Fingerprint method
The following observations can be made from the tabulated test results:
1. The number of collisions is independent of the choice of the irreducible polynomialused for hashing provided that they are of the same degree
2. The expression for estimating the upper bound of errors is not violated in the contetext of the experiment.
3. The performance of the method improves with the increase of the degree of the irreducible polynomial used

34

Chapter 6
Conclusion
6.1

Conclusions

The Rabin’s method of fingerprinting using irreducible polynomials has been studied andimplemented. As a result of the implementation and experiments with a given dataset, thefollowings are verified:

1. The result of application of the Rabin’s method is independent of the choice of irreducible polynomial
2. The probability of error (different strings having the same fingerprint) decreases with
the increase of the degree of the irreducible polynomial used
3. The probability of error is bounded by the expression provided in his paper [1] inwhich Rabin released this fingerprinting method

6.2

Related and Future Work

6.2.1

Related Work

The famous MD4 and MD5 message-digest algorithms are direct applications of this fingerprinting method. Both algorithms employ 128-bit fingerprinting with MD4 being faster.
They use padding at the end of the string to avoid single character concatenation. Eachstring is padded to a length equal to a multiple of 512 bits. A 16-word (32 bit word) blockis processed each cycle.
35

6.2.2 Future WorkDue to the constraint of resources, only a limited number of runs have been performed. To
conform to the Principle of Large Numbers, more runs should be executed to obtain results
to verify the above observations made in the conclusion section.
Besides, 2 collisions were found in the fourth run using polynomial of degree 96, it is notexpected. The situation should be examined to find out the cause of the problem. It would
be good to know if the errors are just coincidence or erratic program codes or some otherreasons. However, this cannot be done in time to meet the submission deadline of thisproject.

36

Chapter 7
Source Codes
7.1

Source Codes for Fingerprinting/**************************************************************************** Authors: Calvin Chan & Haihua Lu* Course Project: CMPUT 690 -- Advanced Database System, December, 2001
* Instructor: Dr. Davood Rafiei** Filename: fingerPrint.cc** Purpose: to run finger printing test on pages.txt** Usage: fp <degree> <output file name> < input stream*
if no output file name is given, "outfp.txt" will be used****************************************************************************/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <iostream.h>#include <math.h>#include <time.h>/***** Type Definitions *****/
typedef unsigned int usInt;/***** Forward Declarations *****/// for generating irreducible polynomial of degree k// wCount being the number of 32 bit words required to hold P(t)usInt* generateIrreduciblePoly(short k, short *wCount);// for generating pre-computed table TA, TB, TC, TD
void computTable

37

(usInt **TA, usInt **TB, usInt **TC, usInt **TD, usInt *P, short wCount);// for left shifting values s bits
void longLeftShift(usInt *words, short wCount, short s);// for computing i*tˆ8 mod P(t)void multiT8(usInt *words, usInt *P, short wCount);// for computing i*tˆ(k-8) mod P(t)void byteShift(usInt *words, short wCount, short value);// for computing f(concat(S, 1 byte))
void fp1(usInt *fP, usInt *P, short wCount, char s);// for computing f(concat(S, 4 bytes))
void fp4(usInt *fP, short wCount, short s1, short s2, short s3, short s4);// return a random number in the range [0, 1]
double getArandom();/***** Global Variables *****/
usInt **TA, **TB, **TC, **TD;/***** Application Entry *****/
int main( int argc, char * argv[] ) {// setting up
FILE* logFile;
FILE* outFile;char* fName;
short wCount, i, j, k;
usInt* P;// open the log and output files to record statistics and resultsif ( (logFile = fopen("result.log", "a")) == NULL ) {fprintf( stderr, "Error opening log file, exiting...\n" );exit(1);};
fName = argc > 2 ? strdup(argv[2]) : strdup("outfp.dat");if ( (outFile = fopen(fName, "w")) == NULL ) {fprintf( stderr, "Error opening output file, exiting...\n" );exit(1);};// retrieve the degree for P from parameter, default to 64// and generate the polynomial, write to log filek = argc > 1 ? atoi( argv[1] ) : 64;
P = generateIrreduciblePoly(k, &wCount);
fprintf(logFile, "\nThe polynomial is of degree %d\n", k);fprintf(logFile, "Irreducible polynomial used is ");for ( j = wCount - 1; j >= 0; j-- ) {38

for (i = 28; i >= 0; i -= 4) fprintf(logFile, "%X", P[j] >> i & 0xf);
fprintf(logFile, " ");}fprintf(logFile, "\n");// allocate memory for tables and generate tables
TA = (usInt **)malloc(256*sizeof(usInt*));TA[0] = (usInt *)malloc(256*wCount*sizeof(usInt));
TB = (usInt **)malloc(256*sizeof(usInt*));TB[0] = (usInt *)malloc(256*wCount*sizeof(usInt));
TC = (usInt **)malloc(256*sizeof(usInt*));TC[0] = (usInt *)malloc(256*wCount*sizeof(usInt));
TD = (usInt **)malloc(256*sizeof(int*));TD[0] = (usInt *)malloc(256*wCount*sizeof(usInt));if((!TA)||(!TB)||(!TC)||(!TD)){fprintf(stderr, "Memory allocate error in main--1\n");exit(1);}if((!TA[0])||(!TB[0])||(!TC[0])||(!TD[0])){fprintf(stderr, "Memory allocate error in main--2\n");exit(1);}computTable(TA, TB, TC, TD, P, wCount);// actual process
int n, len;char pid[8];char url[1001];
char url2[873];
usInt* fP = (usInt *)malloc(wCount*sizeof(usInt)); // for storing fingerprint
if(!fP) {fprintf(stderr, "Memory allocate error in main--3\n");exit(1);}// clean up for next round
pid[0] = ’\0’;
url[0] = ’\0’;
url2[0] = ’\0’;// do some statisitics on time useddouble totalTime = 0;
clock_t t0 = clock();long record = 0;// loop until the file is done
while ( scanf("\"%[ˆ\"]\",\"%[ˆ\"]\",\"%s\n", pid, url, url2) > 0 ) {39

url2[strlen(url2)-1] = ’\0’;
strcat(url, url2);
record++;for ( j = 0; j < wCount; j++ ) fP[j] = 0;len = strlen(url);
n = len / 4;
for ( j = 1; j <= n; j++ ) {fp4(fP, wCount, url[4*j-4], url[4*j-3], url[4*j-2], url[4*j-1]);}
for ( j = 4*n; j < len; j++) {fp1(fP, P, wCount, url[j]);}// output the resultfor ( j = wCount - 1; j >= 0; j-- ) {fprintf(outFile, "%X ", fP[j]);}fprintf(outFile, "\n");// clean up for next round
pid[0] = ’\0’;
url[0] = ’\0’;
url2[0] = ’\0’;
if(record % 1000000 == 0){
clock_t t1 = clock();
totalTime = totalTime + (double)(t1-t0)/CLOCKS_PER_SEC;
t0 = clock();}}
clock_t t1 = clock();
totalTime = totalTime + (double) (t1 - t0) / CLOCKS_PER_SEC;
fprintf( logFile,"Total CPU time for %d fingerprinting = %f seconds\n", k, totalTime);
fprintf( logFile, "\n****************************************\n" );free(P); free(fP);
free(TA[0]); free(TB[0]); free(TC[0]); free(TD[0]);free(TA); free(TB); free(TC); free(TD);// close the files
fclose(logFile);
fclose(outFile);
return 1;}

40

/***** Methods *****/
usInt * generateIrreduciblePoly(short k, short *size) {// precondition
if((k<0)||(k % 32 != 0)){cout<<"Error in Generating Irreducible Polynomial, k - value"<<endl;
exit(1);}//Seed the random-number generator with current time so that//the numbers will be different every time we run.
srand( (unsigned)time( NULL ) );double temp;
for(int n=0; n<5; n++) {//I found the first generated random does not change,//so I choose the fifth one
temp = getArandom(); //temp is [0, 1)}
int r = (int) ( temp * (floor((k-1)/2.0)-1));
r = 2*r + 1; // r is a random odd value within [1, k-2]
usInt *A;//A array is going to store the poly. coefficents.
A = (usInt *)malloc(k*sizeof(usInt)); //allocate memory
if(!A) {cout<<"Memory allocate error for Irreducible Polynomial--1"<<endl;
exit(1);}//initialize the array
A[0] = 1; //A[k-1] = 1;
short i;for(i=1; i<= k-1; i++) // should be i <= k - 1 instead of i < k - 1
A[i] = 0;
for(i=1; i<=r; i++){while(1){temp = getArandom(); //temp is [0, 1)
short j = (short)(temp * (k-2)); // j is [0, k-2)
if(A[j+1]==0){
A[j+1] = 1;
break;}}//end of while loop}//end of for i loop
*size = k/32;
usInt *W;
W = (usInt *)malloc((*size)*sizeof(usInt)); //allocate memory
if(!W) {cout<<"Memory allocatet error for Irreducible Polynomial--2"<<endl;
exit(1);41

}for(short j=0; j<*size; j++){
W[j] = 0;
for(i=32*(j+1)-1; i>=32*(j+1)-32; i--)W[j] = 2*W[j] + A[i];}return W;}
void computTable(usInt **TA, usInt **TB, usInt **TC, usInt **TD, usInt *P, short wCount) {short i;for(i=1; i<256; i++) {TA[i] = TA[i-1] + wCount; //allocate address
TB[i] = TB[i-1] + wCount; //allocate address
TC[i] = TC[i-1] + wCount; //allocate address
TD[i] = TD[i-1] + wCount; //allocate address}for(i=0; i<256; i++) {for(short j=0; j<wCount; j++) {TA[i][j] = 0; //initialize
TB[i][j] = 0; //initialize
TC[i][j] = 0; //initialize
TD[i][j] = 0; //initialize}}
for(i=0; i<256; i++) {short j;for(j=0; j < wCount; j++) {TD[i][j] = 0;}
byteShift(TD[i], wCount, i);
multiT8(TD[i], P, wCount);for(j=0; j < wCount; j++) {TC[i][j] = TD[i][j];}multiT8(TC[i], P, wCount);for(j=0; j < wCount; j++) {TB[i][j] = TC[i][j];}multiT8(TB[i], P, wCount);for(j=0; j < wCount; j++) {TA[i][j] = TB[i][j];42}multiT8(TA[i], P, wCount);}}
void multiT8(usInt *words, usInt *P, short size){
int needXOR;
short i, j;for(i=0; i<8; i++){// XOR is needed only when the MSB = 1
needXOR = ((words[size-1] & 0x80000000) == 0x80000000);// left shift 1 bit
longLeftShift(words, size, 1);
if ( needXOR ){for(j=size-1; j>=0; j--){words[j] = words[j] ˆ P[j];}}}}void byteShift(usInt *words, short len, short value){
short i;usInt temp = value;words[len - 1] = value << 24;
for(i = len - 2; i >= 0; i--){words[i] = 0x00000000;}}
void longLeftShift(usInt *words, short len, short s){usInt temp;
usInt mask = 0x00000000;
short i;for (i = 0; i < s; i++)//create a mask for s LSB
mask = mask << 1 | 0x00000001;
for (i = len - 1; i > 0; i--) {temp = words[i-1] >> (32 - s) & mask; // get a MSB from low
words[i] = words[i] << s | temp; // set as s LSB in high}words[0] = words[0] << s; // shift the low word}43

void fp1(usInt *fP, usInt *P, short wCount, char s) {usInt W;
int needXOR;
short i, j;for ( i = 0; i < 8; i++ ) {W = s & 0x80; // retrieve the MSB of ss = s << 1;// shift for next round
needXOR = ( (fP[wCount-1] & 0x80000000) == 0x80000000 );longLeftShift(fP, wCount, 1);
fP[0] = fP[0] | (W >> 7);
if ( needXOR ) {for( j = wCount - 1; j >= 0; j--) {fP[j] = fP[j] ˆ P[j];}}}}void fp4(usInt *fP, short wCount, short s1, short s2, short s3, short s4) {usInt W = 0;
short i, j;
unsigned short f1, f2, f3, f4;
W = (((W | s1) << 8 | s2 ) << 8 | s3 ) << 8 | s4;
f1 = (fP[wCount - 1] >> 24 ) & 0xff;
f2 = (fP[wCount - 1] >> 16 ) & 0xff;
f3 = (fP[wCount - 1] >> 8 ) & 0xff;
f4 = fP[wCount - 1] & 0xff;
for( j = wCount - 1; j > 0; j--) {fP[j] = fP[j-1] ˆ TA[f1][j] ˆ TB[f2][j] ˆ TC[f3][j] ˆ TD[f4][j];}fP[0] = W ˆ TA[f1][0] ˆ TB[f2][0] ˆ TC[f3][0] ˆ TD[f4][0];}double getArandom() {return rand()/(double)RAND_MAX;
}

44

7.2

Source Codes for “url2pid”

The source codes are contained in a file named “functions.c”.
#include <string.h>#include <math.h>#include <sqludf.h>
double hash1(char *str) {/*Hash function for chaning urls into PIDs.
*/
double val = 0;
int i = 0;char *ptr,*ptr2;
ptr = str;
if (*str) ptr++;ptr2 = ptr;
if (*ptr) ptr2++;
while (*str) {val += pow(10,i%12)*(pow(abs(*str),3) + (*ptr)*(*ptr) + abs(*ptr2));
str++;
ptr++;
if (*ptr2) ptr2++;i++;val = fmod(val,pow(10,18));}
return val;}
double hash2(char *str) {/*Secondary hash function for turning urls into PIDs.
*/
double val = 0;
double pro = 1;
int i;
while (*str) {for (i=1;(i<=5) && (*str);i++) {pro *= abs(*str);
str++;}
val += pro;val = fmod(val,pow(10,17));
pro = 1;}
return val;}
double get_pid(char *url,char *pid, int n) {45

/*Takes the url and generates a pid using a hash function. The pid isreturned through the parameter as a string. The double value of thepid is also returned as the return value.
*/
char temp[16];double val = 0;
double val2,dbl;
int i = 0;
while (n > 1) {val += hash2(url);n--;}val += hash1(url);
val = fmod(val,pow(93,8));less thanthat */
val2 = val;/* 93ˆ8 combinations, want the number infor (i=7;i>=0;i--) {dbl = fmod(val,93);
dbl = floor(dbl);
pid[i] = (int)dbl;
pid[i] += 33;
if (pid[i] == ’"’) pid[i] = 126;
val /= 93;}
pid[8] = 0;/* pid’s can’t contain " */return val2;}/* returns the first pids */void url2pid1 (char *url,/* input */char *pid,/* output */short *nullUrl,/* indicator variable for the input */short *nullPid,/* indicator variable for the output */char *sqlstate,char *fnName,char *specificName,char *message){
int n = 1;
if (*nullUrl) {*nullPid = -1;
return;}46

get_pid(url, pid, n);return;}/* returns a table of pids */void url2pids (char *url,/* input */char *pid,/* output */short *nullUrl,/* indicator variable for the input */short *nullPid,/* indicator variable for the output */char *sqlstate,char *fnName,char *specificName,char *message,
SQLUDF_SCRATCHPAD*scratchpad,/* declared in sqludf.h */SQLUDF_CALL_TYPE*calltype /* declared in sqludf.h */){int *pad = (int *)scratchpad->data;/* scratchpad */switch (*calltype) {case SQL_TF_OPEN: *pad = 0; break;case SQL_TF_FETCH:
while (*pad < 3) {(*pad)++;
get_pid(url, pid, *pad);
strcpy(sqlstate, "00000");
return;}strcpy(sqlstate, "02000");
break;
case SQL_TF_CLOSE: break;
}
}

47

48

Bibliography[1] Michael O. Rabin. Fingerprinting by random polynomials. Report TR-15-81, Center
for Research in Computing Technology, Harvard University, 1981.
[2] Michael O. Rabin. Discovering repetitions in strings. In A. Apostolico and Z. Galil,
editors, Combinatorial Algorithms on Words. Springer-Verlag, 1985.
[3] Bill Cherowitzo. http://www-math.cudenver.edu/˜wcherowi/courses/finflds.html. webpage.
[4] Michael O. Rabin. Probabilistic algorithms in finite fields. In SIAM Journal of Computing, volume 9, pages 273–280, 1980.
[5] Andrei A. Broder. Some applications of Rabin’s fingerprinting method. In A. De Santis R. Capocelli and U. Vaccaro, editors, Sequences II: Methods in Communications,
Security, and Computer Science. Springer-Verlag, 1993.
[6] http://www.cs.yorku.ca/˜oz/hash.html. webpage.
[7] Bruno Preiss.
http://www.pads.uwaterloo.ca/bruno.preiss/books/opus5/html/page220.html#eqnhashingstring. webpage.

49