43 static void split(off_t *I,off_t *V,off_t start,off_t len,off_t h)  in split()  argument
49 			j=1;x=V[I[k]+h];  in split()
51 				if(V[I[k+i]+h]<x) {  in split()
52 					x=V[I[k+i]+h];  in split()
55 				if(V[I[k+i]+h]==x) {  in split()
56 					tmp=I[k+j];I[k+j]=I[k+i];I[k+i]=tmp;  in split()
60 			for(i=0;i<j;i++) V[I[k+i]]=k+j-1;  in split()
61 			if(j==1) I[k]=-1;  in split()
66 	x=V[I[start+len/2]+h];  in split()
69 		if(V[I[i]+h]<x) jj++;  in split()
70 		if(V[I[i]+h]==x) kk++;  in split()
76 		if(V[I[i]+h]<x) {  in split()
78 		} else if(V[I[i]+h]==x) {  in split()
79 			tmp=I[i];I[i]=I[jj+j];I[jj+j]=tmp;  in split()
82 			tmp=I[i];I[i]=I[kk+k];I[kk+k]=tmp;  in split()
88 		if(V[I[jj+j]+h]==x) {  in split()
91 			tmp=I[jj+j];I[jj+j]=I[kk+k];I[kk+k]=tmp;  in split()
96 	if(jj>start) split(I,V,start,jj-start,h);  in split()
98 	for(i=0;i<kk-jj;i++) V[I[jj+i]]=kk-1;  in split()
99 	if(jj==kk-1) I[jj]=-1;  in split()
101 	if(start+len>kk) split(I,V,kk,start+len-kk,h);  in split()
104 static void qsufsort(off_t *I,off_t *V,u_char *old,off_t oldsize)  in qsufsort()  argument
115 	for(i=0;i<oldsize;i++) I[++buckets[old[i]]]=i;  in qsufsort()
116 	I[0]=oldsize;  in qsufsort()
119 	for(i=1;i<256;i++) if(buckets[i]==buckets[i-1]+1) I[buckets[i]]=-1;  in qsufsort()
120 	I[0]=-1;  in qsufsort()
122 	for(h=1;I[0]!=-(oldsize+1);h+=h) {  in qsufsort()
125 			if(I[i]<0) {  in qsufsort()
126 				len-=I[i];  in qsufsort()
127 				i-=I[i];  in qsufsort()
129 				if(len) I[i-len]=-len;  in qsufsort()
130 				len=V[I[i]]+1-i;  in qsufsort()
131 				split(I,V,i,len,h);  in qsufsort()
136 		if(len) I[i-len]=-len;  in qsufsort()
139 	for(i=0;i<oldsize+1;i++) I[V[i]]=i;  in qsufsort()
152 static off_t search(off_t *I,u_char *old,off_t oldsize,  in search()  argument
158 		x=matchlen(old+I[st],oldsize-I[st],new,newsize);  in search()
159 		y=matchlen(old+I[en],oldsize-I[en],new,newsize);  in search()
162 			*pos=I[st];  in search()
165 			*pos=I[en];  in search()
171 	if(memcmp(old+I[x],new,MIN(oldsize-I[x],newsize))<0) {  in search()
172 		return search(I,old,oldsize,new,newsize,x,en,pos);  in search()
174 		return search(I,old,oldsize,new,newsize,st,x,pos);  in search()
201 	off_t *I,*V;  in main()  local
227 	if(((I=malloc((oldsize+1)*sizeof(off_t)))==NULL) ||  in main()
230 	qsufsort(I,V,old,oldsize);  in main()
278 			len=search(I,old,oldsize,new+scan,newsize-scan,  in main()
399 	free(I);  in main()