Annotation of embedaddon/rsync/token.c, revision 1.1
1.1 ! misho 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 "ifuncs.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(<r))
! 196: ltr = toLower(<r);
! 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_STREAMIO);
! 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_STREAMIO);
! 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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>