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
23 /* Apply the transformation source->target to reconstruct target
24 ** This code is designed to work even if the local machine has
25 ** word size smaller than that of the machine where the delta
26 ** was computed. A requirement is that "long" on the local
27 ** machine must be large enough to hold source and target sizes.
28 ** It is also assumed that if an array is given, the size of
29 ** that array in bytes must be storable in an "int". This is
30 ** used in various cast from "long" to "int".
31 **
32 ** Written by Kiem-Phong Vo, kpv@research.att.com, 5/20/94
33 */
34
35 /* structure for update table */
36 typedef struct _utable_s
37 { Vdio_t io; /* io structure */
38 Vddisc_t* source; /* source data discipline */
39 Vddisc_t* target; /* target data discipline */
40 uchar* src; /* source string */
41 long n_src;
42 uchar* tar; /* target string */
43 long n_tar;
44 long s_org; /* start of window in source */
45 long t_org; /* start of window in target */
46 uchar data[1024]; /* buffer for data transferring */
47 char s_alloc; /* 1 if source was allocated */
48 char t_alloc; /* 1 if target was allocated */
49 char compress; /* 1 if compressing only */
50 K_UDECL(quick,recent,rhere); /* address caches */
51 } Utable_t;
52
53 #if __STD_C
vdunfold(Utable_t * tab)54 static int vdunfold(Utable_t* tab)
55 #else
56 static int vdunfold(tab)
57 Utable_t* tab;
58 #endif
59 {
60 reg long size, copy;
61 reg int inst, k_type, n, r;
62 reg uchar *tar, *src, *to, *fr;
63 reg long t, c_addr, n_tar, n_src;
64 reg Vddisc_t *target, *source;
65
66 n_tar = tab->n_tar;
67 tar = tab->tar;
68 n_src = tab->n_src;
69 src = tab->src;
70 target = tab->target;
71 source = tab->source;
72
73 for(t = 0, c_addr = n_src; t < n_tar; )
74 { if((inst = VDGETC((Vdio_t*)tab)) < 0)
75 return -1;
76 k_type = K_GET(inst);
77
78 if(!VD_ISCOPY(k_type))
79 { if(K_ISMERGE(k_type)) /* merge/add instruction */
80 size = A_TGET(inst);
81 else if(A_ISHERE(inst)) /* locally coded ADD size */
82 size = A_LGET(inst);
83 else /* non-local ADD size */
84 { if((size = VDGETC((Vdio_t*)tab)) < 0)
85 return -1;
86 if(size >= I_MORE &&
87 (size = (long)(*_Vdgetu)((Vdio_t*)tab,size)) < 0)
88 return -1;
89 size = A_GET(size);
90 }
91 if((t+size) > n_tar) /* out of sync */
92 return -1;
93 c_addr += size;
94
95 /* copy data from the delta stream to target */
96 for(;;)
97 { if(!tar)
98 { if((long)(n = sizeof(tab->data)) > size)
99 n = (int)size;
100 if((*_Vdread)((Vdio_t*)tab,tab->data,n) != n )
101 return -1;
102 r = (*target->writef)((Void_t*)tab->data, n,
103 tab->t_org+t, target);
104 if(r != n)
105 return -1;
106 }
107 else
108 { n = (int)size;
109 if((*_Vdread)((Vdio_t*)tab,tar+t,n) != n)
110 return -1;
111 }
112 t += n;
113 if((size -= n) <= 0)
114 break;
115 }
116
117 if(K_ISMERGE(k_type))
118 { size = C_TGET(inst);
119 k_type -= K_MERGE;
120 goto do_copy;
121 }
122 }
123 else
124 { if(C_ISHERE(inst)) /* locally coded COPY size */
125 size = C_LGET(inst);
126 else
127 { if((size = VDGETC((Vdio_t*)tab)) < 0)
128 return -1;
129 if(size >= I_MORE &&
130 (size = (long)(*_Vdgetu)((Vdio_t*)tab,size)) < 0)
131 return -1;
132 size = C_GET(size);
133 }
134 do_copy:
135 if((t+size) > n_tar) /* out of sync */
136 return -1;
137
138 if((copy = VDGETC((Vdio_t*)tab)) < 0)
139 return -1;
140 if(k_type >= K_QUICK && k_type < (K_QUICK+K_QTYPE) )
141 copy = tab->quick[copy + ((k_type-K_QUICK)<<VD_BITS)];
142 else
143 { if(copy >= I_MORE &&
144 (copy = (long)(*_Vdgetu)((Vdio_t*)tab,copy)) < 0)
145 return -1;
146 if(k_type >= K_RECENT && k_type < (K_RECENT+K_RTYPE) )
147 copy += tab->recent[k_type - K_RECENT];
148 else if(k_type == K_HERE)
149 copy = c_addr - copy;
150 /* else k_type == K_SELF */
151 }
152 K_UPDATE(tab->quick,tab->recent,tab->rhere,copy);
153 c_addr += size;
154
155 if(copy < n_src) /* copy from source data */
156 { if((copy+size) > n_src) /* out of sync */
157 return -1;
158 if(src)
159 { n = (int)size;
160 fr = src+copy;
161 if(tar)
162 { to = tar+t;
163 MEMCPY(to,fr,n);
164 }
165 else
166 { r = (*target->writef)((Void_t*)fr, n,
167 tab->t_org+t, target);
168 if(r != n)
169 return -1;
170 }
171 t += n;
172 }
173 else
174 { reg Vddisc_t* disc;
175
176 if(tab->compress)
177 { copy += tab->t_org - tab->n_src;
178 disc = target;
179 }
180 else
181 { copy += tab->s_org;
182 disc = source;
183 }
184 for(;;)
185 { if(tar)
186 { n = (int)size;
187 r = (*disc->readf)
188 ((Void_t*)(tar+t), n,
189 copy, disc );
190 }
191 else
192 { n = sizeof(tab->data);
193 if((long)n > size)
194 n = (int)size;
195 r = (*disc->readf)
196 ((Void_t*)tab->data, n,
197 copy, disc );
198 if(r != n)
199 return -1;
200 r = (*target->writef)
201 ((Void_t*)tab->data, n,
202 tab->t_org+t, target);
203 }
204 if(r != n)
205 return -1;
206 t += n;
207 if((size -= n) <= 0)
208 break;
209 copy += n;
210 }
211 }
212 }
213 else /* copy from target data */
214 { copy -= n_src;
215 if(copy >= t || (copy+size) > n_tar) /* out-of-sync */
216 return -1;
217 for(;;) /* allow for copying overlapped data */
218 { reg long s, a;
219 if((s = t-copy) > size)
220 s = size;
221 if(tar)
222 { to = tar+t; fr = tar+copy; n = (int)s;
223 MEMCPY(to,fr,n);
224 t += n;
225 goto next;
226 }
227
228 /* hard read/write */
229 a = copy;
230 for(;;)
231 { if((long)(n = sizeof(tab->data)) > s)
232 n = (int)s;
233 r = (*target->readf)
234 ((Void_t*)tab->data, n,
235 a + tab->t_org, target );
236 if(r != n)
237 return -1;
238 r = (*target->writef)
239 ((Void_t*)tab->data, n,
240 t + tab->t_org, target );
241 if(r != n)
242 return -1;
243 t += n;
244 if((s -= n) <= 0)
245 break;
246 a += n;
247 }
248
249 next: if((size -= s) == 0)
250 break;
251 }
252 }
253 }
254 }
255
256 return 0;
257 }
258
259 #if __STD_C
vdupdate(Vddisc_t * source,Vddisc_t * target,Vddisc_t * delta)260 long vdupdate(Vddisc_t* source, Vddisc_t* target, Vddisc_t* delta)
261 #else
262 long vdupdate(source,target,delta)
263 Vddisc_t* source; /* source data */
264 Vddisc_t* target; /* target data */
265 Vddisc_t* delta; /* delta data */
266 #endif
267 {
268 reg int n, r;
269 reg uchar *tar, *src;
270 reg long t, p, window, n_src, n_tar;
271 reg uchar *data;
272 uchar magic[8];
273 Utable_t tab;
274
275 if(!target || (!target->data && !target->writef) )
276 return -1;
277 if(!delta || (!delta->data && !delta->readf) )
278 return -1;
279
280 /* initialize I/O buffer */
281 INIT(&tab.io,delta);
282 tab.source = source;
283 tab.target = target;
284
285 /* check magic header */
286 /* VD_MAGIC is the preferred binary magic */
287 /* VD_MAGIC_OLD is the deprecated ascii magic */
288 data = (uchar*)(VD_MAGIC);
289 n = sizeof(VD_MAGIC) - 1;
290 if((*_Vdread)(&tab.io,magic,n) != n)
291 return -1;
292 for(r = 0; r < n; ++r)
293 if(data[r] != magic[r])
294 { data = (uchar*)(VD_MAGIC_OLD);
295 for (r = 0; r < n; ++r)
296 if(data[r] != magic[r])
297 #if _PACKAGE_ast
298 return _vdupdate_01(source,target,delta);
299 #else
300 return -1;
301 #endif
302 break;
303 }
304
305 /* get true target size */
306 if((t = (long)(*_Vdgetu)(&tab.io,0)) < 0 ||
307 (target->data && target->size < t) )
308 return -1;
309 n_tar = t;
310
311 /* get true source size */
312 if((t = (long)(*_Vdgetu)(&tab.io,0)) < 0)
313 return -1;
314 else if(t > 0)
315 { if(!source || (!source->data && !source->readf) )
316 return -1;
317 if(source->data && source->size < t)
318 return -1;
319 }
320 n_src = t;
321
322 /* get window size */
323 if((window = (long)(*_Vdgetu)(&tab.io,0)) < 0)
324 return -1;
325
326 tab.compress = n_src == 0 ? 1 : 0;
327
328 /* if we have space, it'll be faster to unfold */
329 tab.tar = tab.src = NIL(uchar*);
330 tab.t_alloc = tab.s_alloc = 0;
331
332 n = (!target->data && window < (long)MAXINT) ? (int)window : 0;
333 if(n > n_tar)
334 n = n_tar;
335 if(n > 0 && (tab.tar = (uchar*)malloc(n*sizeof(uchar))) )
336 tab.t_alloc = 1;
337
338 if(n_src <= 0)
339 { if(target->data || window >= (long)MAXINT || window >= n_tar)
340 n = 0;
341 else n = (int)HEADER(window);
342 }
343 else
344 { n = (!source->data && window < (long)MAXINT) ? (int)window : 0;
345 if(n > n_src)
346 n = n_src;
347 }
348 if(n > 0 && (tab.src = (uchar*)malloc(n*sizeof(uchar))) )
349 tab.s_alloc = 1;
350
351 tar = (uchar*)target->data;
352 src = (uchar*)(source ? source->data : NIL(Void_t*));
353 for(t = 0; t < n_tar; )
354 { tab.t_org = t; /* current location in target stream */
355
356 if(n_src <= 0) /* data compression */
357 { tab.s_org = 0;
358
359 if(t == 0)
360 tab.n_src = 0;
361 else
362 { tab.n_src = HEADER(window);
363 p = t - tab.n_src;
364 if(tar)
365 tab.src = tar + p;
366 else if(tab.src)
367 { n = (int)tab.n_src;
368 if(tab.tar)
369 { data = tab.tar + tab.n_tar - n;
370 memcpy((Void_t*)tab.src,(Void_t*)data,n);
371 }
372 else
373 { r = (*target->readf)(tab.src,n,p,target);
374 if(r != n)
375 goto done;
376 }
377 }
378 }
379 }
380 else /* data differencing */
381 { if(t < n_src)
382 { if(window >= n_src)
383 p = 0;
384 else if((t+window) > n_src)
385 p = n_src-window;
386 else p = t;
387 if((tab.n_src = n_src-p) > window)
388 tab.n_src = window;
389 tab.s_org = p;
390
391 if(src)
392 tab.src = src + p;
393 else if(tab.src)
394 { n = (int)tab.n_src;
395 r = (*source->readf)(tab.src,n,p,source);
396 if(r != n)
397 goto done;
398 }
399 }
400 /* else use last window */
401 }
402
403 if(tar)
404 tab.tar = (uchar*)tar+t;
405 tab.n_tar = window < (n_tar-t) ? window : (n_tar-t);
406
407 K_INIT(tab.quick,tab.recent,tab.rhere);
408 if(vdunfold(&tab) < 0)
409 goto done;
410 if(!target->data && tab.tar)
411 { p = (*target->writef)((Void_t*)tab.tar,(int)tab.n_tar,t,target);
412 if(p != tab.n_tar)
413 goto done;
414 }
415
416 t += tab.n_tar;
417 }
418
419 done:
420 if(tab.t_alloc)
421 free((Void_t*)tab.tar);
422 if(tab.s_alloc)
423 free((Void_t*)tab.src);
424
425 return t;
426 }
427