1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
/* This file is part of the software similarity tester SIM.
Written by Dick Grune, Vrije Universiteit, Amsterdam.
$Id: compare.c,v 2.5 2001/09/28 09:03:47 dick Exp $
*/
#include "sim.h"
#include "tokenarray.h"
#include "hash.h"
#include "language.h"
#include "options.h"
#include "add_run.h"
#include "compare.h"
static void compare1text(int, int, int);
static unsigned int lcs(
struct text *, unsigned int, struct text **, unsigned int *,
unsigned int, unsigned int
);
/* The overall structure of the routine Compare() is:
for all new files
for all texts it must be compared to
for all positions in the new file
for all positions in the text
for ever increasing sizes
try to match and keep the best
*/
void
Compare(void) {
register int n;
for (n = 0; n < NumberOfNewTexts; n++) {
register int first =
( option_set('S') ? NumberOfNewTexts + 1
: option_set('s') ? n + 1
: n
);
if (option_set('e')) {
/* from first to NumberOfTexts in steps */
register int m;
for (m = first; m < NumberOfTexts; m++) {
compare1text(n, m, m+1);
}
}
else {
/* from first to NumberOfTexts in one action */
if (first < NumberOfTexts) {
compare1text(n, first, NumberOfTexts);
}
}
}
}
static void
compare1text(
int n, /* text to be compared */
int first, /* first text to be compared to */
int limit /* limit text in comparison */
) {
register unsigned int i_first = Text[first].tx_start;
register unsigned int i_limit = Text[limit-1].tx_limit;
register struct text *txt0 = &Text[n];
register unsigned int i0 = txt0->tx_start;
while ( /* there may still be a useful substring */
i0 + MinRunSize - 1 < txt0->tx_limit
) {
/* see if there really is one */
struct text *txt_best;
unsigned int i_best;
register unsigned int size_best =
lcs(txt0, i0, &txt_best, &i_best, i_first, i_limit);
if (size_best) {
/* good run found; enter it */
add_run(txt0, i0, txt_best, i_best, size_best);
/* and skip it */
i0 += size_best;
}
else {
/* we try our luck at the next token */
i0++;
}
}
}
static unsigned int
lcs( struct text *txt0, /* input: starting position */
unsigned int i0,
struct text **tbp, /* output: position of best run */
unsigned int *ibp,
unsigned int i_first, /* no comparison before this pos. */
unsigned int i_limit /* no comparison after this pos. */
) {
/* Finds the longest common substring (not -sequence) in:
txt0, starting precisely at i0 and
the text between i_first and i_limit.
Writes the position in tbp and ibp and returns the size.
Returns 0 if no common substring is found.
*/
register struct text *txt1 = txt0;
register unsigned int i1 = i0;
register unsigned int size_best = 0;
register unsigned int txt0limit = txt0->tx_limit;
register unsigned int txt1limit = txt1->tx_limit;
while ( /* there is a next opportunity */
(i1 = ForwardReference(i1))
&& /* it is still in range */
i1 < i_limit
) {
register unsigned int min_size;
register unsigned int new_size;
register unsigned int j0;
register unsigned int j1;
if (i1 < i_first) { /* not in range */
continue;
}
/* bump txt1; we may have skipped a text or two */
while (i1 >= txt1->tx_limit) {
txt1++;
}
txt1limit = txt1->tx_limit;
min_size = (size_best ? size_best+1 : MinRunSize);
/* are we looking at something better than we have got? */
{
j0 = i0 + min_size - 1;
j1 = i1 + min_size - 1;
if ( /* j0 still inside txt0 */
j0 < txt0limit
&& /* j1 still inside txt1 */
j1 < txt1limit
&& /* j0 and j1 don't overlap */
j0 < j1 - min_size + 1
) {
/* there would be room enough */
register int cnt = min_size;
/* does the text match? */
while ( cnt
&& TOKEN_EQ(TokenArray[j0], TokenArray[j1])
) {
cnt--, j0--, j1--;
}
if (cnt) continue; /* forget it */
}
else continue; /* forget it */
}
/* yes, we are; how long can we make it? */
{
register unsigned int size = min_size;
j0 = i0 + min_size;
j1 = i1 + min_size;
while ( /* j0 still inside txt0 */
j0 < txt0limit
&& /* j1 still inside txt1 */
j1 < txt1limit
&& /* j0 and j1 don't overlap */
j0 + size < j1
&& /* tokens are the same */
TOKEN_EQ(TokenArray[j0], TokenArray[j1])
) {
j0++, j1++, size++;
}
new_size = size;
}
/* offer the run to the Language Department which may
reject it or may cut its tail
*/
new_size = ( MayBeStartOfRun(TokenArray[i0])
? CheckRun(&TokenArray[i0], new_size)
: 0
);
if ( /* we still have something acceptable */
new_size >= MinRunSize
&& /* it is better still than what we had */
new_size > size_best
) {
/* record it */
*tbp = txt1;
*ibp = i1;
size_best = new_size;
}
}
return size_best;
}
|
