@@ -29,6 +29,7 @@ __FBSDID("$FreeBSD: src/usr.bin/bsdiff/bsdiff/bsdiff.c, v 1.1 2005/08/06 01:59:0
2929#endif
3030
3131#include <sys/types.h>
32+ #include "sais.h"
3233
3334#include <err.h>
3435#include <fcntl.h>
@@ -39,138 +40,6 @@ __FBSDID("$FreeBSD: src/usr.bin/bsdiff/bsdiff/bsdiff.c, v 1.1 2005/08/06 01:59:0
3940
4041#define MIN (x , y ) (((x)<(y)) ? (x) : (y))
4142
42- static void split (off_t * I , off_t * V , off_t start , off_t len , off_t h )
43- {
44- off_t i , j , k , x , tmp , jj , kk ;
45-
46- if (len < 16 ) {
47- for (k = start ; k < start + len ; k += j ) {
48- j = 1 ; x = V [I [k ] + h ];
49- for (i = 1 ; k + i < start + len ; i ++ ) {
50- if (V [I [k + i ] + h ] < x ) {
51- x = V [I [k + i ] + h ];
52- j = 0 ;
53- };
54- if (V [I [k + i ] + h ] == x ) {
55- tmp = I [k + j ]; I [k + j ] = I [k + i ]; I [k + i ] = tmp ;
56- j ++ ;
57- };
58- };
59- for (i = 0 ; i < j ; i ++ )
60- V [I [k + i ]] = k + j - 1 ;
61- if (j == 1 )
62- I [k ] = -1 ;
63- };
64- return ;
65- };
66-
67- x = V [I [start + len /2 ] + h ];
68- jj = 0 ; kk = 0 ;
69- for (i = start ; i < start + len ; i ++ ) {
70- if (V [I [i ] + h ] < x )
71- jj ++ ;
72- if (V [I [i ] + h ] == x )
73- kk ++ ;
74- };
75- jj += start ; kk += jj ;
76-
77- i = start ; j = 0 ; k = 0 ;
78- while (i < jj ) {
79- if (V [I [i ] + h ] < x ) {
80- i ++ ;
81- } else if (V [I [i ] + h ] == x ) {
82- tmp = I [i ]; I [i ] = I [jj + j ]; I [jj + j ] = tmp ;
83- j ++ ;
84- } else {
85- tmp = I [i ]; I [i ] = I [kk + k ]; I [kk + k ] = tmp ;
86- k ++ ;
87- };
88- };
89-
90- while (jj + j < kk ) {
91- if (V [I [jj + j ] + h ] == x ) {
92- j ++ ;
93- } else {
94- tmp = I [jj + j ]; I [jj + j ] = I [kk + k ]; I [kk + k ] = tmp ;
95- k ++ ;
96- };
97- };
98-
99- if (jj > start )
100- split (I , V , start , jj - start , h );
101-
102- for (i = 0 ; i < kk - jj ; i ++ )
103- V [I [jj + i ]] = kk - 1 ;
104- if (jj == kk - 1 )
105- I [jj ] = -1 ;
106-
107- if (start + len > kk )
108- split (I , V , kk , start + len - kk , h );
109- }
110-
111- /* qsufsort(I, V, old, oldsize)
112- *
113- * Computes the suffix sort of the string at 'old' and stores the resulting
114- * indices in 'I', using 'V' as a temporary array for the computation. */
115- static void qsufsort (off_t * I , off_t * V , u_char * old , off_t oldsize )
116- {
117- off_t buckets [256 ];
118- off_t i , h , len ;
119-
120- /* count number of each byte */
121- for (i = 0 ; i < 256 ; i ++ )
122- buckets [i ] = 0 ;
123- for (i = 0 ; i < oldsize ; i ++ )
124- buckets [old [i ]]++ ;
125- /* make buckets cumulative */
126- for (i = 1 ; i < 256 ; i ++ )
127- buckets [i ] += buckets [i - 1 ];
128- /* shift right by one */
129- for (i = 255 ; i > 0 ; i -- )
130- buckets [i ] = buckets [i - 1 ];
131- buckets [0 ] = 0 ;
132- /* at this point, buckets[c] is the number of bytes in the old file with
133- * value less than c. */
134-
135- /* set up the sort order of the suffixes based solely on the first
136- * character */
137- for (i = 0 ; i < oldsize ; i ++ )
138- I [++ buckets [old [i ]]] = i ;
139- I [0 ] = oldsize ;
140- /* ? */
141- for (i = 0 ; i < oldsize ; i ++ )
142- V [i ] = buckets [old [i ]];
143- V [oldsize ] = 0 ;
144- /* forward any entries in the ordering which have the same initial
145- * character */
146- for (i = 1 ; i < 256 ; i ++ ) {
147- if (buckets [i ] == buckets [i - 1 ] + 1 )
148- I [buckets [i ]] = -1 ;
149- }
150- I [0 ] = -1 ;
151-
152- for (h = 1 ; I [0 ] != - (oldsize + 1 ); h += h ) {
153- len = 0 ;
154- for (i = 0 ; i < oldsize + 1 ;) {
155- if (I [i ] < 0 ) {
156- len -= I [i ];
157- i -= I [i ];
158- } else {
159- if (len )
160- I [i - len ] = - len ;
161- len = V [I [i ]] + 1 - i ;
162- split (I , V , i , len , h );
163- i += len ;
164- len = 0 ;
165- }
166- }
167- if (len )
168- I [i - len ] = - len ;
169- };
170-
171- for (i = 0 ; i < oldsize + 1 ; i ++ ) I [V [i ]] = i ;
172- }
173-
17443/* matchlen(old, oldsize, new, newsize)
17544 *
17645 * Returns the length of the longest common prefix between 'old' and 'new'. */
@@ -288,7 +157,7 @@ int bsdiff(int argc, char *argv[])
288157 err (1 , NULL );
289158
290159 /* Do a suffix sort on the old file. */
291- qsufsort ( I , V , old , oldsize );
160+ I [ 0 ] = oldsize ; sais ( old , I + 1 , oldsize );
292161
293162 free (V );
294163
0 commit comments