1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1995-2011 AT&T Intellectual Property *
5 * and is licensed under the *
6 * Eclipse Public License, Version 1.0 *
7 * by AT&T Intellectual Property *
8 * *
9 * A copy of the License is available at *
10 * http://www.eclipse.org/org/documents/epl-v10.html *
11 * (with md5 checksum b35adb5213ca9657e911e9befb180842) *
12 * *
13 * Information and Software Systems Research *
14 * AT&T Research *
15 * Florham Park NJ *
16 * *
17 * Phong Vo <kpv@research.att.com> *
18 * *
19 ***********************************************************************/
20 #include "vdelhdr.h"
21
22 /* Squeeze a string.
23 **
24 ** Written by Kiem-Phong Vo, kpv@research.att.com, 2/15/95
25 */
26
27 #ifdef DEBUG
28 long S_copy, S_add; /* amount of input covered by COPY and ADD */
29 long N_copy, N_add; /* # of COPY and ADD instructions */
30 long M_copy, M_add; /* max size of a COPY or ADD instruction */
31 long N_merge; /* # of merged instructions */
32 #endif
33
34 #define MERGABLE(a,c,k) ((a) > 0 && A_ISTINY(a) && \
35 (c) > 0 && C_ISTINY(c) && \
36 (k) >= K_SELF )
37
38 typedef struct _table_s Table_t;
39 struct _table_s
40 { uchar* delta; /* output area */
41 uchar* tar; /* target string */
42 int n_tar;
43 K_DDECL(quick,recent,rhere); /* address caches */
44 int* link; /* base of elements */
45 int size; /* size of hash table */
46 int* hash; /* hash table */
47 };
48
49 /* encode and output delta instructions */
50 #if __STD_C
vdputinst(Table_t * tab,uchar * begs,uchar * here,reg int copy,int n_copy)51 static int vdputinst(Table_t* tab, uchar* begs, uchar* here, reg int copy, int n_copy)
52 #else
53 static int vdputinst(tab, begs, here, copy, n_copy)
54 Table_t* tab;
55 uchar* begs; /* ADD data if any */
56 uchar* here; /* current location */
57 reg int copy; /* best match if any */
58 int n_copy; /* length of match */
59 #endif
60 {
61 reg int n_add, i_add, i_copy, k_type;
62 reg int n, c_addr, best, d;
63 uchar buf[sizeof(long)+1];
64
65 n_add = begs ? here-begs : 0; /* add size */
66 c_addr = here-tab->tar; /* current address */
67 k_type = 0;
68
69 if(copy >= 0) /* process the COPY instruction */
70 { /**/DBTOTAL(N_copy,1); DBTOTAL(S_copy,n_copy); DBMAX(M_copy,n_copy);
71
72 best = copy;
73 k_type = K_SELF;
74 if((d = c_addr - copy) < best)
75 { best = d;
76 k_type = K_HERE;
77 }
78 for(n = 0; n < K_RTYPE; ++n)
79 { if((d = copy - tab->recent[n]) < 0 || d >= best)
80 continue;
81 best = d;
82 k_type = K_RECENT+n;
83 }
84 if(best >= I_MORE && tab->quick[n = copy%K_QSIZE] == copy)
85 { for(d = K_QTYPE-1; d > 0; --d)
86 if(n >= (d<<VD_BITS) )
87 break;
88 best = n - (d<<VD_BITS); /**/ASSERT(best < (1<<VD_BITS));
89 k_type = K_QUICK+d;
90 }
91
92 /**/ASSERT(best >= 0);
93 /**/ASSERT((k_type+K_MERGE) < (1<<I_BITS) );
94
95 /* update address caches */
96 K_UPDATE(tab->quick,tab->recent,tab->rhere,copy);
97
98 /* see if mergable to last ADD instruction */
99 if(MERGABLE(n_add,n_copy,k_type) )
100 { /**/DBTOTAL(N_merge,1);
101 i_add = K_TPUT(k_type)|A_TPUT(n_add)|C_TPUT(n_copy);
102 }
103 else
104 { i_copy = K_PUT(k_type);
105 if(C_ISLOCAL(n_copy) )
106 i_copy |= C_LPUT(n_copy);
107 }
108 }
109
110 if(n_add > 0)
111 { /**/DBTOTAL(N_add,1); DBTOTAL(S_add,n_add); DBMAX(M_add,n_add);
112
113 if(!MERGABLE(n_add,n_copy,k_type) )
114 i_add = A_ISLOCAL(n_add) ? A_LPUT(n_add) : 0;
115
116 STRPUTC(tab, i_add);
117 if(!A_ISLOCAL(n_add) )
118 STRPUTU(tab, (ulong)A_PUT(n_add), buf);
119 STRWRITE(tab, begs, n_add);
120 }
121
122 if(n_copy > 0)
123 { if(!MERGABLE(n_add,n_copy,k_type))
124 STRPUTC(tab, i_copy);
125
126 if(!C_ISLOCAL(n_copy) )
127 STRPUTU(tab, (ulong)C_PUT(n_copy), buf);
128
129 if(k_type >= K_QUICK && k_type < (K_QUICK+K_QTYPE) )
130 STRPUTC(tab, (uchar)best);
131 else STRPUTU(tab, (ulong)best, buf);
132 }
133
134 return 0;
135 }
136
137
138 /* Fold a string */
139 #if __STD_C
vdfold(Table_t * tab)140 static int vdfold(Table_t* tab)
141 #else
142 static int vdfold(tab)
143 Table_t* tab;
144 #endif
145 {
146 reg ulong key, n;
147 reg uchar *s, *sm, *ends, *ss, *heade;
148 reg int m, list, curm, bestm;
149 reg uchar *add, *endfold;
150 reg int head, len;
151 reg int size = tab->size;
152 reg uchar *tar = tab->tar;
153 reg int *link = tab->link, *hash = tab->hash;
154
155 endfold = (s = tar) + tab->n_tar;
156 curm = 0;
157 if(tab->n_tar < M_MIN)
158 return vdputinst(tab,s,endfold,-1,0);
159
160 add = NIL(uchar*);
161 bestm = -1;
162 len = M_MIN-1;
163 HINIT(key,s,n);
164 for(;;)
165 { for(;;) /* search for the longest match */
166 { if((m = hash[key&size]) < 0 )
167 goto endsearch;
168 list = m = link[m]; /* head of list */
169
170 if(bestm >= 0) /* skip over past elements */
171 for(n = bestm+len; m < n;)
172 if((m = link[m]) == list)
173 goto endsearch;
174
175 head = len - (M_MIN-1); /* header before the match */
176 heade = s+head;
177 for(;;)
178 {
179 if((n = m) < head)
180 goto next;
181 sm = tar + n;
182
183 /* make sure that the M_MIN bytes match */
184 if(!EQUAL(heade,sm))
185 goto next;
186
187 /* make sure this is a real match */
188 for(sm -= head, ss = s; ss < heade; )
189 if(*sm++ != *ss++)
190 goto next;
191 ss += M_MIN;
192 sm += M_MIN;
193 ends = endfold;
194 for(; ss < ends; ++ss, ++sm)
195 if(*sm != *ss)
196 goto extend;
197 goto extend;
198
199 next: if((m = link[m]) == list )
200 goto endsearch;
201 }
202
203 extend: bestm = m-head;
204 n = len;
205 len = ss-s;
206 if(ss >= endfold) /* already match everything */
207 goto endsearch;
208
209 /* check for a longer match */
210 ss -= M_MIN-1;
211 if(len == n+1)
212 HNEXT(key,ss,n);
213 else HINIT(key,ss,n);
214 }
215
216 endsearch:
217 if(bestm >= 0)
218 { if(vdputinst(tab,add,s,bestm,len) < 0)
219 return -1;
220
221 /* add a sufficient number of suffices */
222 ends = (s += len);
223 ss = ends - (M_MIN-1);
224 curm = (ss-tar);
225
226 len = M_MIN-1;
227 add = NIL(uchar*);
228 bestm = -1;
229 }
230 else
231 { if(!add)
232 add = s;
233 ss = s;
234 ends = (s += 1); /* add one prefix */
235 }
236
237 if(ends > (endfold - (M_MIN-1)) )
238 ends = endfold - (M_MIN-1);
239
240 if(ss < ends) for(;;) /* add prefices/suffices */
241 { n = key&size;
242 if((m = hash[n]) < 0 )
243 link[curm] = curm;
244 else
245 { link[curm] = link[m];
246 link[m] = curm;
247 }
248 hash[n] = curm++;
249
250 if((ss += 1) >= ends)
251 break;
252 HNEXT(key,ss,n);
253 }
254
255 if(s > endfold-M_MIN) /* too short to match */
256 { if(!add)
257 add = s;
258 break;
259 }
260
261 HNEXT(key,s,n);
262 }
263
264 return vdputinst(tab,add,endfold,-1,0);
265 }
266
267
268 #if __STD_C
vdsqueeze(Void_t * target,reg int size,Void_t * delta)269 int vdsqueeze(Void_t* target, reg int size, Void_t* delta)
270 #else
271 int vdsqueeze(target, size, delta)
272 Void_t* target;
273 reg int size;
274 Void_t* delta;
275 #endif
276 {
277 reg int k, n;
278 Table_t tab;
279 uchar buf[sizeof(long)+1];
280
281 if(size <= 0)
282 return 0;
283 else if(!target || !delta)
284 return -1;
285
286 tab.n_tar = size;
287 tab.tar = (uchar*)target;
288 tab.delta = (uchar*)delta;
289 tab.link = NIL(int*);
290 tab.hash = NIL(int*);
291
292 /* space for the hash table */
293 k = size;
294 n = size/2;
295 do (size = n); while((n &= n-1) != 0);
296 if(size < 64)
297 size = 64;
298 k += size;
299
300 if(!(tab.hash = (int*)malloc(k*sizeof(int))) )
301 return -1;
302 tab.link = tab.hash + size;
303 tab.size = size-1;
304
305 /* initialize table before processing */
306 for(n = tab.size; n >= 0; --n)
307 tab.hash[n] = -1;
308 K_INIT(tab.quick,tab.recent,tab.rhere);
309
310 STRPUTU(&tab,tab.n_tar,buf);
311 n = vdfold(&tab);
312
313 free((Void_t*)tab.hash);
314
315 return n < 0 ? -1 : (tab.delta - (uchar*)delta);
316 }
317