?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Fix a comment.
[rsync/qnx.git] / token.c
blob75d2b17b48fffc432f70e86da279861a6e337283
1 /*
2 * Routines used by the file-transfer code.
3 *
4 * Copyright (C) 1996 Andrew Tridgell
5 * Copyright (C) 1996 Paul Mackerras
6 * Copyright (C) 2003-2009 Wayne Davison
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License along
19 * with this program; if not, visit the http://fsf.org website.
20 */
21
22 #include "rsync.h"
23 #include "itypes.h"
24 #include "zlib/zlib.h"
25
26 extern int do_compression;
27 extern int module_id;
28 extern int def_compress_level;
29 extern char *skip_compress;
30
31 static int compression_level, per_file_default_level;
32
33 struct suffix_tree {
34 struct suffix_tree *sibling;
35 struct suffix_tree *child;
36 char letter, word_end;
37 };
38
39 static char *match_list;
40 static struct suffix_tree *suftree;
41
42 static void add_suffix(struct suffix_tree **prior, char ltr, const char *str)
43 {
44 struct suffix_tree *node, *newnode;
45
46 if (ltr == '[') {
47 const char *after = strchr(str, ']');
48 /* Treat "[foo" and "[]" as having a literal '['. */
49 if (after && after++ != str+1) {
50 while ((ltr = *str++) != ']')
51 add_suffix(prior, ltr, after);
52 return;
53 }
54 }
55
56 for (node = *prior; node; prior = &node->sibling, node = node->sibling) {
57 if (node->letter == ltr) {
58 if (*str)
59 add_suffix(&node->child, *str, str+1);
60 else
61 node->word_end = 1;
62 return;
63 }
64 if (node->letter > ltr)
65 break;
66 }
67 if (!(newnode = new(struct suffix_tree)))
68 out_of_memory("add_suffix");
69 newnode->sibling = node;
70 newnode->child = NULL;
71 newnode->letter = ltr;
72 *prior = newnode;
73 if (*str) {
74 add_suffix(&newnode->child, *str, str+1);
75 newnode->word_end = 0;
76 } else
77 newnode->word_end = 1;
78 }
79
80 static void add_nocompress_suffixes(const char *str)
81 {
82 char *buf, *t;
83 const char *f = str;
84
85 if (!(buf = new_array(char, strlen(f) + 1)))
86 out_of_memory("add_nocompress_suffixes");
87
88 while (*f) {
89 if (*f == '/') {
90 f++;
91 continue;
92 }
93
94 t = buf;
95 do {
96 if (isUpper(f))
97 *t++ = toLower(f);
98 else
99 *t++ = *f;
100 } while (*++f != '/' && *f);
101 *t++ = '\0';
102
103 add_suffix(&suftree, *buf, buf+1);
104 }
105
106 free(buf);
107 }
108
109 static void init_set_compression(void)
110 {
111 const char *f;
112 char *t, *start;
113
114 if (skip_compress)
115 add_nocompress_suffixes(skip_compress);
116
117 /* A non-daemon transfer skips the default suffix list if the
118 * user specified --skip-compress. */
119 if (skip_compress && module_id < 0)
120 f = "";
121 else
122 f = lp_dont_compress(module_id);
123
124 if (!(match_list = t = new_array(char, strlen(f) + 2)))
125 out_of_memory("set_compression");
126
127 per_file_default_level = def_compress_level;
128
129 while (*f) {
130 if (*f == ' ') {
131 f++;
132 continue;
133 }
134
135 start = t;
136 do {
137 if (isUpper(f))
138 *t++ = toLower(f);
139 else
140 *t++ = *f;
141 } while (*++f != ' ' && *f);
142 *t++ = '\0';
143
144 if (t - start == 1+1 && *start == '*') {
145 /* Optimize a match-string of "*". */
146 *match_list = '\0';
147 suftree = NULL;
148 per_file_default_level = 0;
149 break;
150 }
151
152 /* Move *.foo items into the stuffix tree. */
153 if (*start == '*' && start[1] == '.' && start[2]
154 && !strpbrk(start+2, ".?*")) {
155 add_suffix(&suftree, start[2], start+3);
156 t = start;
157 }
158 }
159 *t++ = '\0';
160 }
161
162 /* determine the compression level based on a wildcard filename list */
163 void set_compression(const char *fname)
164 {
165 const struct suffix_tree *node;
166 const char *s;
167 char ltr;
168
169 if (!do_compression)
170 return;
171
172 if (!match_list)
173 init_set_compression();
174
175 compression_level = per_file_default_level;
176
177 if (!*match_list && !suftree)
178 return;
179
180 if ((s = strrchr(fname, '/')) != NULL)
181 fname = s + 1;
182
183 for (s = match_list; *s; s += strlen(s) + 1) {
184 if (iwildmatch(s, fname)) {
185 compression_level = 0;
186 return;
187 }
188 }
189
190 if (!(node = suftree) || !(s = strrchr(fname, '.'))
191 || s == fname || !(ltr = *++s))
192 return;
193
194 while (1) {
195 if (isUpper(&ltr))
196 ltr = toLower(&ltr);
197 while (node->letter != ltr) {
198 if (node->letter > ltr)
199 return;
200 if (!(node = node->sibling))
201 return;
202 }
203 if ((ltr = *++s) == '\0') {
204 if (node->word_end)
205 compression_level = 0;
206 return;
207 }
208 if (!(node = node->child))
209 return;
210 }
211 }
212
213 /* non-compressing recv token */
214 static int32 simple_recv_token(int f, char **data)
215 {
216 static int32 residue;
217 static char *buf;
218 int32 n;
219
220 if (!buf) {
221 buf = new_array(char, CHUNK_SIZE);
222 if (!buf)
223 out_of_memory("simple_recv_token");
224 }
225
226 if (residue == 0) {
227 int32 i = read_int(f);
228 if (i <= 0)
229 return i;
230 residue = i;
231 }
232
233 *data = buf;
234 n = MIN(CHUNK_SIZE,residue);
235 residue -= n;
236 read_buf(f,buf,n);
237 return n;
238 }
239
240 /* non-compressing send token */
241 static void simple_send_token(int f, int32 token, struct map_struct *buf,
242 OFF_T offset, int32 n)
243 {
244 if (n > 0) {
245 int32 len = 0;
246 while (len < n) {
247 int32 n1 = MIN(CHUNK_SIZE, n-len);
248 write_int(f, n1);
249 write_buf(f, map_ptr(buf, offset+len, n1), n1);
250 len += n1;
251 }
252 }
253 /* a -2 token means to send data only and no token */
254 if (token != -2)
255 write_int(f, -(token+1));
256 }
257
258 /* Flag bytes in compressed stream are encoded as follows: */
259 #define END_FLAG 0 /* that's all folks */
260 #define TOKEN_LONG 0x20 /* followed by 32-bit token number */
261 #define TOKENRUN_LONG 0x21 /* ditto with 16-bit run count */
262 #define DEFLATED_DATA 0x40 /* + 6-bit high len, then low len byte */
263 #define TOKEN_REL 0x80 /* + 6-bit relative token number */
264 #define TOKENRUN_REL 0xc0 /* ditto with 16-bit run count */
265
266 #define MAX_DATA_COUNT 16383 /* fit 14 bit count into 2 bytes with flags */
267
268 /* zlib.h says that if we want to be able to compress something in a single
269 * call, avail_out must be at least 0.1% larger than avail_in plus 12 bytes.
270 * We'll add in 0.1%+16, just to be safe (and we'll avoid floating point,
271 * to ensure that this is a compile-time value). */
272 #define AVAIL_OUT_SIZE(avail_in_size) ((avail_in_size)*1001/1000+16)
273
274 /* For coding runs of tokens */
275 static int32 last_token = -1;
276 static int32 run_start;
277 static int32 last_run_end;
278
279 /* Deflation state */
280 static z_stream tx_strm;
281
282 /* Output buffer */
283 static char *obuf;
284
285 /* We want obuf to be able to hold both MAX_DATA_COUNT+2 bytes as well as
286 * AVAIL_OUT_SIZE(CHUNK_SIZE) bytes, so make sure that it's large enough. */
287 #if MAX_DATA_COUNT+2 > AVAIL_OUT_SIZE(CHUNK_SIZE)
288 #define OBUF_SIZE (MAX_DATA_COUNT+2)
289 #else
290 #define OBUF_SIZE AVAIL_OUT_SIZE(CHUNK_SIZE)
291 #endif
292
293 /* Send a deflated token */
294 static void
295 send_deflated_token(int f, int32 token, struct map_struct *buf, OFF_T offset,
296 int32 nb, int32 toklen)
297 {
298 int32 n, r;
299 static int init_done, flush_pending;
300
301 if (last_token == -1) {
302 /* initialization */
303 if (!init_done) {
304 tx_strm.next_in = NULL;
305 tx_strm.zalloc = NULL;
306 tx_strm.zfree = NULL;
307 if (deflateInit2(&tx_strm, compression_level,
308 Z_DEFLATED, -15, 8,
309 Z_DEFAULT_STRATEGY) != Z_OK) {
310 rprintf(FERROR, "compression init failed\n");
311 exit_cleanup(RERR_PROTOCOL);
312 }
313 if ((obuf = new_array(char, OBUF_SIZE)) == NULL)
314 out_of_memory("send_deflated_token");
315 init_done = 1;
316 } else
317 deflateReset(&tx_strm);
318 last_run_end = 0;
319 run_start = token;
320 flush_pending = 0;
321 } else if (last_token == -2) {
322 run_start = token;
323 } else if (nb != 0 || token != last_token + 1
324 || token >= run_start + 65536) {
325 /* output previous run */
326 r = run_start - last_run_end;
327 n = last_token - run_start;
328 if (r >= 0 && r <= 63) {
329 write_byte(f, (n==0? TOKEN_REL: TOKENRUN_REL) + r);
330 } else {
331 write_byte(f, (n==0? TOKEN_LONG: TOKENRUN_LONG));
332 write_int(f, run_start);
333 }
334 if (n != 0) {
335 write_byte(f, n);
336 write_byte(f, n >> 8);
337 }
338 last_run_end = last_token;
339 run_start = token;
340 }
341
342 last_token = token;
343
344 if (nb != 0 || flush_pending) {
345 /* deflate the data starting at offset */
346 int flush = Z_NO_FLUSH;
347 tx_strm.avail_in = 0;
348 tx_strm.avail_out = 0;
349 do {
350 if (tx_strm.avail_in == 0 && nb != 0) {
351 /* give it some more input */
352 n = MIN(nb, CHUNK_SIZE);
353 tx_strm.next_in = (Bytef *)
354 map_ptr(buf, offset, n);
355 tx_strm.avail_in = n;
356 nb -= n;
357 offset += n;
358 }
359 if (tx_strm.avail_out == 0) {
360 tx_strm.next_out = (Bytef *)(obuf + 2);
361 tx_strm.avail_out = MAX_DATA_COUNT;
362 if (flush != Z_NO_FLUSH) {
363 /*
364 * We left the last 4 bytes in the
365 * buffer, in case they are the
366 * last 4. Move them to the front.
367 */
368 memcpy(tx_strm.next_out,
369 obuf+MAX_DATA_COUNT-2, 4);
370 tx_strm.next_out += 4;
371 tx_strm.avail_out -= 4;
372 }
373 }
374 if (nb == 0 && token != -2)
375 flush = Z_SYNC_FLUSH;
376 r = deflate(&tx_strm, flush);
377 if (r != Z_OK) {
378 rprintf(FERROR, "deflate returned %d\n", r);
379 exit_cleanup(RERR_STREAMIO);
380 }
381 if (nb == 0 || tx_strm.avail_out == 0) {
382 n = MAX_DATA_COUNT - tx_strm.avail_out;
383 if (flush != Z_NO_FLUSH) {
384 /*
385 * We have to trim off the last 4
386 * bytes of output when flushing
387 * (they are just 0, 0, ff, ff).
388 */
389 n -= 4;
390 }
391 if (n > 0) {
392 obuf[0] = DEFLATED_DATA + (n >> 8);
393 obuf[1] = n;
394 write_buf(f, obuf, n+2);
395 }
396 }
397 } while (nb != 0 || tx_strm.avail_out == 0);
398 flush_pending = token == -2;
399 }
400
401 if (token == -1) {
402 /* end of file - clean up */
403 write_byte(f, END_FLAG);
404 } else if (token != -2) {
405 /* Add the data in the current block to the compressor's
406 * history and hash table. */
407 do {
408 /* Break up long sections in the same way that
409 * see_deflate_token() does. */
410 int32 n1 = toklen > 0xffff ? 0xffff : toklen;
411 toklen -= n1;
412 tx_strm.next_in = (Bytef *)map_ptr(buf, offset, n1);
413 tx_strm.avail_in = n1;
414 tx_strm.next_out = (Bytef *) obuf;
415 tx_strm.avail_out = AVAIL_OUT_SIZE(CHUNK_SIZE);
416 r = deflate(&tx_strm, Z_INSERT_ONLY);
417 if (r != Z_OK || tx_strm.avail_in != 0) {
418 rprintf(FERROR, "deflate on token returned %d (%d bytes left)\n",
419 r, tx_strm.avail_in);
420 exit_cleanup(RERR_STREAMIO);
421 }
422 } while (toklen > 0);
423 }
424 }
425
426 /* tells us what the receiver is in the middle of doing */
427 static enum { r_init, r_idle, r_running, r_inflating, r_inflated } recv_state;
428
429 /* for inflating stuff */
430 static z_stream rx_strm;
431 static char *cbuf;
432 static char *dbuf;
433
434 /* for decoding runs of tokens */
435 static int32 rx_token;
436 static int32 rx_run;
437
438 /* Receive a deflated token and inflate it */
439 static int32 recv_deflated_token(int f, char **data)
440 {
441 static int init_done;
442 static int32 saved_flag;
443 int32 n, flag;
444 int r;
445
446 for (;;) {
447 switch (recv_state) {
448 case r_init:
449 if (!init_done) {
450 rx_strm.next_out = NULL;
451 rx_strm.zalloc = NULL;
452 rx_strm.zfree = NULL;
453 if (inflateInit2(&rx_strm, -15) != Z_OK) {
454 rprintf(FERROR, "inflate init failed\n");
455 exit_cleanup(RERR_PROTOCOL);
456 }
457 if (!(cbuf = new_array(char, MAX_DATA_COUNT))
458 || !(dbuf = new_array(char, AVAIL_OUT_SIZE(CHUNK_SIZE))))
459 out_of_memory("recv_deflated_token");
460 init_done = 1;
461 } else {
462 inflateReset(&rx_strm);
463 }
464 recv_state = r_idle;
465 rx_token = 0;
466 break;
467
468 case r_idle:
469 case r_inflated:
470 if (saved_flag) {
471 flag = saved_flag & 0xff;
472 saved_flag = 0;
473 } else
474 flag = read_byte(f);
475 if ((flag & 0xC0) == DEFLATED_DATA) {
476 n = ((flag & 0x3f) << 8) + read_byte(f);
477 read_buf(f, cbuf, n);
478 rx_strm.next_in = (Bytef *)cbuf;
479 rx_strm.avail_in = n;
480 recv_state = r_inflating;
481 break;
482 }
483 if (recv_state == r_inflated) {
484 /* check previous inflated stuff ended correctly */
485 rx_strm.avail_in = 0;
486 rx_strm.next_out = (Bytef *)dbuf;
487 rx_strm.avail_out = AVAIL_OUT_SIZE(CHUNK_SIZE);
488 r = inflate(&rx_strm, Z_SYNC_FLUSH);
489 n = AVAIL_OUT_SIZE(CHUNK_SIZE) - rx_strm.avail_out;
490 /*
491 * Z_BUF_ERROR just means no progress was
492 * made, i.e. the decompressor didn't have
493 * any pending output for us.
494 */
495 if (r != Z_OK && r != Z_BUF_ERROR) {
496 rprintf(FERROR, "inflate flush returned %d (%d bytes)\n",
497 r, n);
498 exit_cleanup(RERR_STREAMIO);
499 }
500 if (n != 0 && r != Z_BUF_ERROR) {
501 /* have to return some more data and
502 save the flag for later. */
503 saved_flag = flag + 0x10000;
504 *data = dbuf;
505 return n;
506 }
507 /*
508 * At this point the decompressor should
509 * be expecting to see the 0, 0, ff, ff bytes.
510 */
511 if (!inflateSyncPoint(&rx_strm)) {
512 rprintf(FERROR, "decompressor lost sync!\n");
513 exit_cleanup(RERR_STREAMIO);
514 }
515 rx_strm.avail_in = 4;
516 rx_strm.next_in = (Bytef *)cbuf;
517 cbuf[0] = cbuf[1] = 0;
518 cbuf[2] = cbuf[3] = 0xff;
519 inflate(&rx_strm, Z_SYNC_FLUSH);
520 recv_state = r_idle;
521 }
522 if (flag == END_FLAG) {
523 /* that's all folks */
524 recv_state = r_init;
525 return 0;
526 }
527
528 /* here we have a token of some kind */
529 if (flag & TOKEN_REL) {
530 rx_token += flag & 0x3f;
531 flag >>= 6;
532 } else
533 rx_token = read_int(f);
534 if (flag & 1) {
535 rx_run = read_byte(f);
536 rx_run += read_byte(f) << 8;
537 recv_state = r_running;
538 }
539 return -1 - rx_token;
540
541 case r_inflating:
542 rx_strm.next_out = (Bytef *)dbuf;
543 rx_strm.avail_out = AVAIL_OUT_SIZE(CHUNK_SIZE);
544 r = inflate(&rx_strm, Z_NO_FLUSH);
545 n = AVAIL_OUT_SIZE(CHUNK_SIZE) - rx_strm.avail_out;
546 if (r != Z_OK) {
547 rprintf(FERROR, "inflate returned %d (%d bytes)\n", r, n);
548 exit_cleanup(RERR_STREAMIO);
549 }
550 if (rx_strm.avail_in == 0)
551 recv_state = r_inflated;
552 if (n != 0) {
553 *data = dbuf;
554 return n;
555 }
556 break;
557
558 case r_running:
559 ++rx_token;
560 if (--rx_run == 0)
561 recv_state = r_idle;
562 return -1 - rx_token;
563 }
564 }
565 }
566
567 /*
568 * put the data corresponding to a token that we've just returned
569 * from recv_deflated_token into the decompressor's history buffer.
570 */
571 static void see_deflate_token(char *buf, int32 len)
572 {
573 int r;
574 int32 blklen;
575 unsigned char hdr[5];
576
577 rx_strm.avail_in = 0;
578 blklen = 0;
579 hdr[0] = 0;
580 do {
581 if (rx_strm.avail_in == 0 && len != 0) {
582 if (blklen == 0) {
583 /* Give it a fake stored-block header. */
584 rx_strm.next_in = (Bytef *)hdr;
585 rx_strm.avail_in = 5;
586 blklen = len;
587 if (blklen > 0xffff)
588 blklen = 0xffff;
589 hdr[1] = blklen;
590 hdr[2] = blklen >> 8;
591 hdr[3] = ~hdr[1];
592 hdr[4] = ~hdr[2];
593 } else {
594 rx_strm.next_in = (Bytef *)buf;
595 rx_strm.avail_in = blklen;
596 len -= blklen;
597 blklen = 0;
598 }
599 }
600 rx_strm.next_out = (Bytef *)dbuf;
601 rx_strm.avail_out = AVAIL_OUT_SIZE(CHUNK_SIZE);
602 r = inflate(&rx_strm, Z_SYNC_FLUSH);
603 if (r != Z_OK && r != Z_BUF_ERROR) {
604 rprintf(FERROR, "inflate (token) returned %d\n", r);
605 exit_cleanup(RERR_STREAMIO);
606 }
607 } while (len || rx_strm.avail_out == 0);
608 }
609
610 /**
611 * Transmit a verbatim buffer of length @p n followed by a token.
612 * If token == -1 then we have reached EOF
613 * If n == 0 then don't send a buffer
614 */
615 void send_token(int f, int32 token, struct map_struct *buf, OFF_T offset,
616 int32 n, int32 toklen)
617 {
618 if (!do_compression)
619 simple_send_token(f, token, buf, offset, n);
620 else
621 send_deflated_token(f, token, buf, offset, n, toklen);
622 }
623
624 /*
625 * receive a token or buffer from the other end. If the reurn value is >0 then
626 * it is a data buffer of that length, and *data will point at the data.
627 * if the return value is -i then it represents token i-1
628 * if the return value is 0 then the end has been reached
629 */
630 int32 recv_token(int f, char **data)
631 {
632 int tok;
633
634 if (!do_compression) {
635 tok = simple_recv_token(f,data);
636 } else {
637 tok = recv_deflated_token(f, data);
638 }
639 return tok;
640 }
641
642 /*
643 * look at the data corresponding to a token, if necessary
644 */
645 void see_token(char *data, int32 toklen)
646 {
647 if (do_compression)
648 see_deflate_token(data, toklen);
649 }