contrib/libarchive/libarchive/archive_write_set_format_mtree.c

   1 /*-
   2  * Copyright (c) 2008 Joerg Sonnenberger
   3  * Copyright (c) 2009-2012 Michihiro NAKAJIMA
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  18  * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
  19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #include "archive_platform.h"
  28 __FBSDID("$FreeBSD: head/lib/libarchive/archive_write_set_format_mtree.c 201171 2009-12-29 06:39:07Z kientzle $");
  29
  30 #ifdef HAVE_SYS_TYPES_H
  31 #include <sys/types.h>
  32 #endif
  33 #include <errno.h>
  34 #include <stdlib.h>
  35 #include <string.h>
  36
  37 #include "archive.h"
  38 #include "archive_digest_private.h"
  39 #include "archive_entry.h"
  40 #include "archive_private.h"
  41 #include "archive_rb.h"
  42 #include "archive_string.h"
  43 #include "archive_write_private.h"
  44
  45 #define INDENTNAMELEN   15
  46 #define MAXLINELEN      80
  47 #define SET_KEYS        \
  48         (F_FLAGS | F_GID | F_GNAME | F_MODE | F_TYPE | F_UID | F_UNAME)
  49
  50 struct attr_counter {
  51         struct attr_counter *prev;
  52         struct attr_counter *next;
  53         struct mtree_entry *m_entry;
  54         int count;
  55 };
  56
  57 struct att_counter_set {
  58         struct attr_counter *uid_list;
  59         struct attr_counter *gid_list;
  60         struct attr_counter *mode_list;
  61         struct attr_counter *flags_list;
  62 };
  63
  64 struct mtree_chain {
  65         struct mtree_entry *first;
  66         struct mtree_entry **last;
  67 };
  68
  69 /*
  70  * The Data only for a directory file.
  71  */
  72 struct dir_info {
  73         struct archive_rb_tree rbtree;
  74         struct mtree_chain children;
  75         struct mtree_entry *chnext;
  76         int virtual;
  77 };
  78
  79 /*
  80  * The Data only for a regular file.
  81  */
  82 struct reg_info {
  83         int compute_sum;
  84         uint32_t crc;
  85 #ifdef ARCHIVE_HAS_MD5
  86         unsigned char buf_md5[16];
  87 #endif
  88 #ifdef ARCHIVE_HAS_RMD160
  89         unsigned char buf_rmd160[20];
  90 #endif
  91 #ifdef ARCHIVE_HAS_SHA1
  92         unsigned char buf_sha1[20];
  93 #endif
  94 #ifdef ARCHIVE_HAS_SHA256
  95         unsigned char buf_sha256[32];
  96 #endif
  97 #ifdef ARCHIVE_HAS_SHA384
  98         unsigned char buf_sha384[48];
  99 #endif
 100 #ifdef ARCHIVE_HAS_SHA512
 101         unsigned char buf_sha512[64];
 102 #endif
 103 };
 104
 105 struct mtree_entry {
 106         struct archive_rb_node rbnode;
 107         struct mtree_entry *next;
 108         struct mtree_entry *parent;
 109         struct dir_info *dir_info;
 110         struct reg_info *reg_info;
 111
 112         struct archive_string parentdir;
 113         struct archive_string basename;
 114         struct archive_string pathname;
 115         struct archive_string symlink;
 116         struct archive_string uname;
 117         struct archive_string gname;
 118         struct archive_string fflags_text;
 119         unsigned int nlink;
 120         mode_t filetype;
 121         mode_t mode;
 122         int64_t size;
 123         int64_t uid;
 124         int64_t gid;
 125         time_t mtime;
 126         long mtime_nsec;
 127         unsigned long fflags_set;
 128         unsigned long fflags_clear;
 129         dev_t rdevmajor;
 130         dev_t rdevminor;
 131         dev_t devmajor;
 132         dev_t devminor;
 133         int64_t ino;
 134 };
 135
 136 struct mtree_writer {
 137         struct mtree_entry *mtree_entry;
 138         struct mtree_entry *root;
 139         struct mtree_entry *cur_dirent;
 140         struct archive_string cur_dirstr;
 141         struct mtree_chain file_list;
 142
 143         struct archive_string ebuf;
 144         struct archive_string buf;
 145         int first;
 146         uint64_t entry_bytes_remaining;
 147
 148         /*
 149          * Set global value.
 150          */
 151         struct {
 152                 int             processing;
 153                 mode_t          type;
 154                 int             keys;
 155                 int64_t         uid;
 156                 int64_t         gid;
 157                 mode_t          mode;
 158                 unsigned long   fflags_set;
 159                 unsigned long   fflags_clear;
 160         } set;
 161         struct att_counter_set  acs;
 162         int classic;
 163         int depth;
 164
 165         /* check sum */
 166         int compute_sum;
 167         uint32_t crc;
 168         uint64_t crc_len;
 169 #ifdef ARCHIVE_HAS_MD5
 170         archive_md5_ctx md5ctx;
 171 #endif
 172 #ifdef ARCHIVE_HAS_RMD160
 173         archive_rmd160_ctx rmd160ctx;
 174 #endif
 175 #ifdef ARCHIVE_HAS_SHA1
 176         archive_sha1_ctx sha1ctx;
 177 #endif
 178 #ifdef ARCHIVE_HAS_SHA256
 179         archive_sha256_ctx sha256ctx;
 180 #endif
 181 #ifdef ARCHIVE_HAS_SHA384
 182         archive_sha384_ctx sha384ctx;
 183 #endif
 184 #ifdef ARCHIVE_HAS_SHA512
 185         archive_sha512_ctx sha512ctx;
 186 #endif
 187         /* Keyword options */
 188         int keys;
 189 #define F_CKSUM         0x00000001              /* check sum */
 190 #define F_DEV           0x00000002              /* device type */
 191 #define F_DONE          0x00000004              /* directory done */
 192 #define F_FLAGS         0x00000008              /* file flags */
 193 #define F_GID           0x00000010              /* gid */
 194 #define F_GNAME         0x00000020              /* group name */
 195 #define F_IGN           0x00000040              /* ignore */
 196 #define F_MAGIC         0x00000080              /* name has magic chars */
 197 #define F_MD5           0x00000100              /* MD5 digest */
 198 #define F_MODE          0x00000200              /* mode */
 199 #define F_NLINK         0x00000400              /* number of links */
 200 #define F_NOCHANGE      0x00000800              /* If owner/mode "wrong", do
 201                                                  * not change */
 202 #define F_OPT           0x00001000              /* existence optional */
 203 #define F_RMD160        0x00002000              /* RIPEMD160 digest */
 204 #define F_SHA1          0x00004000              /* SHA-1 digest */
 205 #define F_SIZE          0x00008000              /* size */
 206 #define F_SLINK         0x00010000              /* symbolic link */
 207 #define F_TAGS          0x00020000              /* tags */
 208 #define F_TIME          0x00040000              /* modification time */
 209 #define F_TYPE          0x00080000              /* file type */
 210 #define F_UID           0x00100000              /* uid */
 211 #define F_UNAME         0x00200000              /* user name */
 212 #define F_VISIT         0x00400000              /* file visited */
 213 #define F_SHA256        0x00800000              /* SHA-256 digest */
 214 #define F_SHA384        0x01000000              /* SHA-384 digest */
 215 #define F_SHA512        0x02000000              /* SHA-512 digest */
 216 #define F_INO           0x04000000              /* inode number */
 217 #define F_RESDEV        0x08000000              /* device ID on which the
 218                                                  * entry resides */
 219
 220         /* Options */
 221         int dironly;            /* If it is set, ignore all files except
 222                                  * directory files, like mtree(8) -d option. */
 223         int indent;             /* If it is set, indent output data. */
 224         int output_global_set;  /* If it is set, use /set keyword to set
 225                                  * global values. When generating mtree
 226                                  * classic format, it is set by default. */
 227 };
 228
 229 #define DEFAULT_KEYS    (F_DEV | F_FLAGS | F_GID | F_GNAME | F_SLINK | F_MODE\
 230                          | F_NLINK | F_SIZE | F_TIME | F_TYPE | F_UID\
 231                          | F_UNAME)
 232 #define attr_counter_set_reset  attr_counter_set_free
 233
 234 static void attr_counter_free(struct attr_counter **);
 235 static int attr_counter_inc(struct attr_counter **, struct attr_counter *,
 236         struct attr_counter *, struct mtree_entry *);
 237 static struct attr_counter * attr_counter_new(struct mtree_entry *,
 238         struct attr_counter *);
 239 static int attr_counter_set_collect(struct mtree_writer *,
 240         struct mtree_entry *);
 241 static void attr_counter_set_free(struct mtree_writer *);
 242 static int get_global_set_keys(struct mtree_writer *, struct mtree_entry *);
 243 static int mtree_entry_add_child_tail(struct mtree_entry *,
 244         struct mtree_entry *);
 245 static int mtree_entry_create_virtual_dir(struct archive_write *, const char *,
 246         struct mtree_entry **);
 247 static int mtree_entry_cmp_node(const struct archive_rb_node *,
 248         const struct archive_rb_node *);
 249 static int mtree_entry_cmp_key(const struct archive_rb_node *, const void *);
 250 static int mtree_entry_exchange_same_entry(struct archive_write *,
 251     struct mtree_entry *, struct mtree_entry *);
 252 static void mtree_entry_free(struct mtree_entry *);
 253 static int mtree_entry_new(struct archive_write *, struct archive_entry *,
 254         struct mtree_entry **);
 255 static void mtree_entry_register_free(struct mtree_writer *);
 256 static void mtree_entry_register_init(struct mtree_writer *);
 257 static int mtree_entry_setup_filenames(struct archive_write *,
 258         struct mtree_entry *, struct archive_entry *);
 259 static int mtree_entry_tree_add(struct archive_write *, struct mtree_entry **);
 260 static void sum_init(struct mtree_writer *);
 261 static void sum_update(struct mtree_writer *, const void *, size_t);
 262 static void sum_final(struct mtree_writer *, struct reg_info *);
 263 static void sum_write(struct archive_string *, struct reg_info *);
 264 static int write_mtree_entry(struct archive_write *, struct mtree_entry *);
 265 static int write_dot_dot_entry(struct archive_write *, struct mtree_entry *);
 266
 267 #define COMPUTE_CRC(var, ch)    (var) = (var) << 8 ^ crctab[(var) >> 24 ^ (ch)]
 268 static const uint32_t crctab[] = {
 269         0x0,
 270         0x04c11db7, 0x09823b6e, 0x0d4326d9, 0x130476dc, 0x17c56b6b,
 271         0x1a864db2, 0x1e475005, 0x2608edb8, 0x22c9f00f, 0x2f8ad6d6,
 272         0x2b4bcb61, 0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd,
 273         0x4c11db70, 0x48d0c6c7, 0x4593e01e, 0x4152fda9, 0x5f15adac,
 274         0x5bd4b01b, 0x569796c2, 0x52568b75, 0x6a1936c8, 0x6ed82b7f,
 275         0x639b0da6, 0x675a1011, 0x791d4014, 0x7ddc5da3, 0x709f7b7a,
 276         0x745e66cd, 0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,
 277         0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5, 0xbe2b5b58,
 278         0xbaea46ef, 0xb7a96036, 0xb3687d81, 0xad2f2d84, 0xa9ee3033,
 279         0xa4ad16ea, 0xa06c0b5d, 0xd4326d90, 0xd0f37027, 0xddb056fe,
 280         0xd9714b49, 0xc7361b4c, 0xc3f706fb, 0xceb42022, 0xca753d95,
 281         0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1, 0xe13ef6f4,
 282         0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d, 0x34867077, 0x30476dc0,
 283         0x3d044b19, 0x39c556ae, 0x278206ab, 0x23431b1c, 0x2e003dc5,
 284         0x2ac12072, 0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16,
 285         0x018aeb13, 0x054bf6a4, 0x0808d07d, 0x0cc9cdca, 0x7897ab07,
 286         0x7c56b6b0, 0x71159069, 0x75d48dde, 0x6b93dddb, 0x6f52c06c,
 287         0x6211e6b5, 0x66d0fb02, 0x5e9f46bf, 0x5a5e5b08, 0x571d7dd1,
 288         0x53dc6066, 0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
 289         0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e, 0xbfa1b04b,
 290         0xbb60adfc, 0xb6238b25, 0xb2e29692, 0x8aad2b2f, 0x8e6c3698,
 291         0x832f1041, 0x87ee0df6, 0x99a95df3, 0x9d684044, 0x902b669d,
 292         0x94ea7b2a, 0xe0b41de7, 0xe4750050, 0xe9362689, 0xedf73b3e,
 293         0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2, 0xc6bcf05f,
 294         0xc27dede8, 0xcf3ecb31, 0xcbffd686, 0xd5b88683, 0xd1799b34,
 295         0xdc3abded, 0xd8fba05a, 0x690ce0ee, 0x6dcdfd59, 0x608edb80,
 296         0x644fc637, 0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb,
 297         0x4f040d56, 0x4bc510e1, 0x46863638, 0x42472b8f, 0x5c007b8a,
 298         0x58c1663d, 0x558240e4, 0x51435d53, 0x251d3b9e, 0x21dc2629,
 299         0x2c9f00f0, 0x285e1d47, 0x36194d42, 0x32d850f5, 0x3f9b762c,
 300         0x3b5a6b9b, 0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,
 301         0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623, 0xf12f560e,
 302         0xf5ee4bb9, 0xf8ad6d60, 0xfc6c70d7, 0xe22b20d2, 0xe6ea3d65,
 303         0xeba91bbc, 0xef68060b, 0xd727bbb6, 0xd3e6a601, 0xdea580d8,
 304         0xda649d6f, 0xc423cd6a, 0xc0e2d0dd, 0xcda1f604, 0xc960ebb3,
 305         0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7, 0xae3afba2,
 306         0xaafbe615, 0xa7b8c0cc, 0xa379dd7b, 0x9b3660c6, 0x9ff77d71,
 307         0x92b45ba8, 0x9675461f, 0x8832161a, 0x8cf30bad, 0x81b02d74,
 308         0x857130c3, 0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640,
 309         0x4e8ee645, 0x4a4ffbf2, 0x470cdd2b, 0x43cdc09c, 0x7b827d21,
 310         0x7f436096, 0x7200464f, 0x76c15bf8, 0x68860bfd, 0x6c47164a,
 311         0x61043093, 0x65c52d24, 0x119b4be9, 0x155a565e, 0x18197087,
 312         0x1cd86d30, 0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
 313         0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088, 0x2497d08d,
 314         0x2056cd3a, 0x2d15ebe3, 0x29d4f654, 0xc5a92679, 0xc1683bce,
 315         0xcc2b1d17, 0xc8ea00a0, 0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb,
 316         0xdbee767c, 0xe3a1cbc1, 0xe760d676, 0xea23f0af, 0xeee2ed18,
 317         0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4, 0x89b8fd09,
 318         0x8d79e0be, 0x803ac667, 0x84fbdbd0, 0x9abc8bd5, 0x9e7d9662,
 319         0x933eb0bb, 0x97ffad0c, 0xafb010b1, 0xab710d06, 0xa6322bdf,
 320         0xa2f33668, 0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4
 321 };
 322
 323 static const unsigned char safe_char[256] = {
 324         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 00 - 0F */
 325         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 10 - 1F */
 326         /* !"$%&'()*+,-./  EXCLUSION:0x20( ) 0x23(#) */
 327         0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 20 - 2F */
 328         /* 0123456789:;<>?  EXCLUSION:0x3d(=) */
 329         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, /* 30 - 3F */
 330         /* @ABCDEFGHIJKLMNO */
 331         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 40 - 4F */
 332         /* PQRSTUVWXYZ[]^_ EXCLUSION:0x5c(\)  */
 333         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, /* 50 - 5F */
 334         /* `abcdefghijklmno */
 335         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 60 - 6F */
 336         /* pqrstuvwxyz{|}~ */
 337         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, /* 70 - 7F */
 338         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 80 - 8F */
 339         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 90 - 9F */
 340         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* A0 - AF */
 341         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* B0 - BF */
 342         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* C0 - CF */
 343         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* D0 - DF */
 344         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* E0 - EF */
 345         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* F0 - FF */
 346 };
 347
 348 static void
 349 mtree_quote(struct archive_string *s, const char *str)
 350 {
 351         const char *start;
 352         char buf[4];
 353         unsigned char c;
 354
 355         for (start = str; *str != '\0'; ++str) {
 356                 if (safe_char[*(const unsigned char *)str])
 357                         continue;
 358                 if (start != str)
 359                         archive_strncat(s, start, str - start);
 360                 c = (unsigned char)*str;
 361                 buf[0] = '\\';
 362                 buf[1] = (c / 64) + '0';
 363                 buf[2] = (c / 8 % 8) + '0';
 364                 buf[3] = (c % 8) + '0';
 365                 archive_strncat(s, buf, 4);
 366                 start = str + 1;
 367         }
 368
 369         if (start != str)
 370                 archive_strncat(s, start, str - start);
 371 }
 372
 373 /*
 374  * Indent a line as mtree utility to be readable for people.
 375  */
 376 static void
 377 mtree_indent(struct mtree_writer *mtree)
 378 {
 379         int i, fn, nd, pd;
 380         const char *r, *s, *x;
 381
 382         if (mtree->classic) {
 383                 if (mtree->indent) {
 384                         nd = 0;
 385                         pd = mtree->depth * 4;
 386                 } else {
 387                         nd = mtree->depth?4:0;
 388                         pd = 0;
 389                 }
 390         } else
 391                 nd = pd = 0;
 392         fn = 1;
 393         s = r = mtree->ebuf.s;
 394         x = NULL;
 395         while (*r == ' ')
 396                 r++;
 397         while ((r = strchr(r, ' ')) != NULL) {
 398                 if (fn) {
 399                         fn = 0;
 400                         for (i = 0; i < nd + pd; i++)
 401                                 archive_strappend_char(&mtree->buf, ' ');
 402                         archive_strncat(&mtree->buf, s, r - s);
 403                         if (nd + (r -s) > INDENTNAMELEN) {
 404                                 archive_strncat(&mtree->buf, " \\\n", 3);
 405                                 for (i = 0; i < (INDENTNAMELEN + 1 + pd); i++)
 406                                         archive_strappend_char(&mtree->buf, ' ');
 407                         } else {
 408                                 for (i = (int)(r -s + nd);
 409                                     i < (INDENTNAMELEN + 1); i++)
 410                                         archive_strappend_char(&mtree->buf, ' ');
 411                         }
 412                         s = ++r;
 413                         x = NULL;
 414                         continue;
 415                 }
 416                 if (pd + (r - s) <= MAXLINELEN - 3 - INDENTNAMELEN)
 417                         x = r++;
 418                 else {
 419                         if (x == NULL)
 420                                 x = r;
 421                         archive_strncat(&mtree->buf, s, x - s);
 422                         archive_strncat(&mtree->buf, " \\\n", 3);
 423                         for (i = 0; i < (INDENTNAMELEN + 1 + pd); i++)
 424                                 archive_strappend_char(&mtree->buf, ' ');
 425                         s = r = ++x;
 426                         x = NULL;
 427                 }
 428         }
 429         if (fn) {
 430                 for (i = 0; i < nd + pd; i++)
 431                         archive_strappend_char(&mtree->buf, ' ');
 432                 archive_strcat(&mtree->buf, s);
 433                 s += strlen(s);
 434         }
 435         if (x != NULL && pd + strlen(s) > MAXLINELEN - 3 - INDENTNAMELEN) {
 436                 /* Last keyword is longer. */
 437                 archive_strncat(&mtree->buf, s, x - s);
 438                 archive_strncat(&mtree->buf, " \\\n", 3);
 439                 for (i = 0; i < (INDENTNAMELEN + 1 + pd); i++)
 440                         archive_strappend_char(&mtree->buf, ' ');
 441                 s = ++x;
 442         }
 443         archive_strcat(&mtree->buf, s);
 444         archive_string_empty(&mtree->ebuf);
 445 }
 446
 447 /*
 448  * Write /set keyword.
 449  * Set most used value of uid,gid,mode and fflags, which are
 450  * collected by attr_counter_set_collect() function.
 451  */
 452 static void
 453 write_global(struct mtree_writer *mtree)
 454 {
 455         struct archive_string setstr;
 456         struct archive_string unsetstr;
 457         struct att_counter_set *acs;
 458         int keys, oldkeys, effkeys;
 459
 460         archive_string_init(&setstr);
 461         archive_string_init(&unsetstr);
 462         keys = mtree->keys & SET_KEYS;
 463         oldkeys = mtree->set.keys;
 464         effkeys = keys;
 465         acs = &mtree->acs;
 466         if (mtree->set.processing) {
 467                 /*
 468                  * Check if the global data needs updating.
 469                  */
 470                 effkeys &= ~F_TYPE;
 471                 if (acs->uid_list == NULL)
 472                         effkeys &= ~(F_UNAME | F_UID);
 473                 else if (oldkeys & (F_UNAME | F_UID)) {
 474                         if (acs->uid_list->count < 2 ||
 475                             mtree->set.uid == acs->uid_list->m_entry->uid)
 476                                 effkeys &= ~(F_UNAME | F_UID);
 477                 }
 478                 if (acs->gid_list == NULL)
 479                         effkeys &= ~(F_GNAME | F_GID);
 480                 else if (oldkeys & (F_GNAME | F_GID)) {
 481                         if (acs->gid_list->count < 2 ||
 482                             mtree->set.gid == acs->gid_list->m_entry->gid)
 483                                 effkeys &= ~(F_GNAME | F_GID);
 484                 }
 485                 if (acs->mode_list == NULL)
 486                         effkeys &= ~F_MODE;
 487                 else if (oldkeys & F_MODE) {
 488                         if (acs->mode_list->count < 2 ||
 489                             mtree->set.mode == acs->mode_list->m_entry->mode)
 490                                 effkeys &= ~F_MODE;
 491                 }
 492                 if (acs->flags_list == NULL)
 493                         effkeys &= ~F_FLAGS;
 494                 else if ((oldkeys & F_FLAGS) != 0) {
 495                         if (acs->flags_list->count < 2 ||
 496                             (acs->flags_list->m_entry->fflags_set ==
 497                                 mtree->set.fflags_set &&
 498                              acs->flags_list->m_entry->fflags_clear ==
 499                                 mtree->set.fflags_clear))
 500                                 effkeys &= ~F_FLAGS;
 501                 }
 502         } else {
 503                 if (acs->uid_list == NULL)
 504                         keys &= ~(F_UNAME | F_UID);
 505                 if (acs->gid_list == NULL)
 506                         keys &= ~(F_GNAME | F_GID);
 507                 if (acs->mode_list == NULL)
 508                         keys &= ~F_MODE;
 509                 if (acs->flags_list == NULL)
 510                         keys &= ~F_FLAGS;
 511         }
 512         if ((keys & effkeys & F_TYPE) != 0) {
 513                 if (mtree->dironly) {
 514                         archive_strcat(&setstr, " type=dir");
 515                         mtree->set.type = AE_IFDIR;
 516                 } else {
 517                         archive_strcat(&setstr, " type=file");
 518                         mtree->set.type = AE_IFREG;
 519                 }
 520         }
 521         if ((keys & effkeys & F_UNAME) != 0) {
 522                 if (archive_strlen(&(acs->uid_list->m_entry->uname)) > 0) {
 523                         archive_strcat(&setstr, " uname=");
 524                         mtree_quote(&setstr, acs->uid_list->m_entry->uname.s);
 525                 } else {
 526                         keys &= ~F_UNAME;
 527                         if ((oldkeys & F_UNAME) != 0)
 528                                 archive_strcat(&unsetstr, " uname");
 529                 }
 530         }
 531         if ((keys & effkeys & F_UID) != 0) {
 532                 mtree->set.uid = acs->uid_list->m_entry->uid;
 533                 archive_string_sprintf(&setstr, " uid=%jd",
 534                     (intmax_t)mtree->set.uid);
 535         }
 536         if ((keys & effkeys & F_GNAME) != 0) {
 537                 if (archive_strlen(&(acs->gid_list->m_entry->gname)) > 0) {
 538                         archive_strcat(&setstr, " gname=");
 539                         mtree_quote(&setstr, acs->gid_list->m_entry->gname.s);
 540                 } else {
 541                         keys &= ~F_GNAME;
 542                         if ((oldkeys & F_GNAME) != 0)
 543                                 archive_strcat(&unsetstr, " gname");
 544                 }
 545         }
 546         if ((keys & effkeys & F_GID) != 0) {
 547                 mtree->set.gid = acs->gid_list->m_entry->gid;
 548                 archive_string_sprintf(&setstr, " gid=%jd",
 549                     (intmax_t)mtree->set.gid);
 550         }
 551         if ((keys & effkeys & F_MODE) != 0) {
 552                 mtree->set.mode = acs->mode_list->m_entry->mode;
 553                 archive_string_sprintf(&setstr, " mode=%o",
 554                     (unsigned int)mtree->set.mode);
 555         }
 556         if ((keys & effkeys & F_FLAGS) != 0) {
 557                 if (archive_strlen(
 558                     &(acs->flags_list->m_entry->fflags_text)) > 0) {
 559                         archive_strcat(&setstr, " flags=");
 560                         mtree_quote(&setstr,
 561                             acs->flags_list->m_entry->fflags_text.s);
 562                         mtree->set.fflags_set =
 563                             acs->flags_list->m_entry->fflags_set;
 564                         mtree->set.fflags_clear =
 565                             acs->flags_list->m_entry->fflags_clear;
 566                 } else {
 567                         keys &= ~F_FLAGS;
 568                         if ((oldkeys & F_FLAGS) != 0)
 569                                 archive_strcat(&unsetstr, " flags");
 570                 }
 571         }
 572         if (unsetstr.length > 0)
 573                 archive_string_sprintf(&mtree->buf, "/unset%s\n", unsetstr.s);
 574         archive_string_free(&unsetstr);
 575         if (setstr.length > 0)
 576                 archive_string_sprintf(&mtree->buf, "/set%s\n", setstr.s);
 577         archive_string_free(&setstr);
 578         mtree->set.keys = keys;
 579         mtree->set.processing = 1;
 580 }
 581
 582 static struct attr_counter *
 583 attr_counter_new(struct mtree_entry *me, struct attr_counter *prev)
 584 {
 585         struct attr_counter *ac;
 586
 587         ac = malloc(sizeof(*ac));
 588         if (ac != NULL) {
 589                 ac->prev = prev;
 590                 ac->next = NULL;
 591                 ac->count = 1;
 592                 ac->m_entry = me;
 593         }
 594         return (ac);
 595 }
 596
 597 static void
 598 attr_counter_free(struct attr_counter **top)
 599 {
 600         struct attr_counter *ac, *tac;
 601
 602         if (*top == NULL)
 603                 return;
 604         ac = *top;
 605         while (ac != NULL) {
 606                 tac = ac->next;
 607                 free(ac);
 608                 ac = tac;
 609         }
 610         *top = NULL;
 611 }
 612
 613 static int
 614 attr_counter_inc(struct attr_counter **top, struct attr_counter *ac,
 615     struct attr_counter *last, struct mtree_entry *me)
 616 {
 617         struct attr_counter *pac;
 618
 619         if (ac != NULL) {
 620                 ac->count++;
 621                 if (*top == ac || ac->prev->count >= ac->count)
 622                         return (0);
 623                 for (pac = ac->prev; pac; pac = pac->prev) {
 624                         if (pac->count >= ac->count)
 625                                 break;
 626                 }
 627                 ac->prev->next = ac->next;
 628                 if (ac->next != NULL)
 629                         ac->next->prev = ac->prev;
 630                 if (pac != NULL) {
 631                         ac->prev = pac;
 632                         ac->next = pac->next;
 633                         pac->next = ac;
 634                         if (ac->next != NULL)
 635                                 ac->next->prev = ac;
 636                 } else {
 637                         ac->prev = NULL;
 638                         ac->next = *top;
 639                         *top = ac;
 640                         ac->next->prev = ac;
 641                 }
 642         } else if (last != NULL) {
 643                 ac = attr_counter_new(me, last);
 644                 if (ac == NULL)
 645                         return (-1);
 646                 last->next = ac;
 647         }
 648         return (0);
 649 }
 650
 651 /*
 652  * Tabulate uid,gid,mode and fflags of a entry in order to be used for /set.
 653  */
 654 static int
 655 attr_counter_set_collect(struct mtree_writer *mtree, struct mtree_entry *me)
 656 {
 657         struct attr_counter *ac, *last;
 658         struct att_counter_set *acs = &mtree->acs;
 659         int keys = mtree->keys;
 660
 661         if (keys & (F_UNAME | F_UID)) {
 662                 if (acs->uid_list == NULL) {
 663                         acs->uid_list = attr_counter_new(me, NULL);
 664                         if (acs->uid_list == NULL)
 665                                 return (-1);
 666                 } else {
 667                         last = NULL;
 668                         for (ac = acs->uid_list; ac; ac = ac->next) {
 669                                 if (ac->m_entry->uid == me->uid)
 670                                         break;
 671                                 last = ac;
 672                         }
 673                         if (attr_counter_inc(&acs->uid_list, ac, last, me) < 0)
 674                                 return (-1);
 675                 }
 676         }
 677         if (keys & (F_GNAME | F_GID)) {
 678                 if (acs->gid_list == NULL) {
 679                         acs->gid_list = attr_counter_new(me, NULL);
 680                         if (acs->gid_list == NULL)
 681                                 return (-1);
 682                 } else {
 683                         last = NULL;
 684                         for (ac = acs->gid_list; ac; ac = ac->next) {
 685                                 if (ac->m_entry->gid == me->gid)
 686                                         break;
 687                                 last = ac;
 688                         }
 689                         if (attr_counter_inc(&acs->gid_list, ac, last, me) < 0)
 690                                 return (-1);
 691                 }
 692         }
 693         if (keys & F_MODE) {
 694                 if (acs->mode_list == NULL) {
 695                         acs->mode_list = attr_counter_new(me, NULL);
 696                         if (acs->mode_list == NULL)
 697                                 return (-1);
 698                 } else {
 699                         last = NULL;
 700                         for (ac = acs->mode_list; ac; ac = ac->next) {
 701                                 if (ac->m_entry->mode == me->mode)
 702                                         break;
 703                                 last = ac;
 704                         }
 705                         if (attr_counter_inc(&acs->mode_list, ac, last, me) < 0)
 706                                 return (-1);
 707                 }
 708         }
 709         if (keys & F_FLAGS) {
 710                 if (acs->flags_list == NULL) {
 711                         acs->flags_list = attr_counter_new(me, NULL);
 712                         if (acs->flags_list == NULL)
 713                                 return (-1);
 714                 } else {
 715                         last = NULL;
 716                         for (ac = acs->flags_list; ac; ac = ac->next) {
 717                                 if (ac->m_entry->fflags_set == me->fflags_set &&
 718                                     ac->m_entry->fflags_clear ==
 719                                                         me->fflags_clear)
 720                                         break;
 721                                 last = ac;
 722                         }
 723                         if (attr_counter_inc(&acs->flags_list, ac, last, me) < 0)
 724                                 return (-1);
 725                 }
 726         }
 727
 728         return (0);
 729 }
 730
 731 static void
 732 attr_counter_set_free(struct mtree_writer *mtree)
 733 {
 734         struct att_counter_set *acs = &mtree->acs;
 735
 736         attr_counter_free(&acs->uid_list);
 737         attr_counter_free(&acs->gid_list);
 738         attr_counter_free(&acs->mode_list);
 739         attr_counter_free(&acs->flags_list);
 740 }
 741
 742 static int
 743 get_global_set_keys(struct mtree_writer *mtree, struct mtree_entry *me)
 744 {
 745         int keys;
 746
 747         keys = mtree->keys;
 748
 749         /*
 750          * If a keyword has been set by /set, we do not need to
 751          * output it.
 752          */
 753         if (mtree->set.keys == 0)
 754                 return (keys);/* /set is not used. */
 755
 756         if ((mtree->set.keys & (F_GNAME | F_GID)) != 0 &&
 757              mtree->set.gid == me->gid)
 758                 keys &= ~(F_GNAME | F_GID);
 759         if ((mtree->set.keys & (F_UNAME | F_UID)) != 0 &&
 760              mtree->set.uid == me->uid)
 761                 keys &= ~(F_UNAME | F_UID);
 762         if (mtree->set.keys & F_FLAGS) {
 763                 if (mtree->set.fflags_set == me->fflags_set &&
 764                     mtree->set.fflags_clear == me->fflags_clear)
 765                         keys &= ~F_FLAGS;
 766         }
 767         if ((mtree->set.keys & F_MODE) != 0 && mtree->set.mode == me->mode)
 768                 keys &= ~F_MODE;
 769
 770         switch (me->filetype) {
 771         case AE_IFLNK: case AE_IFSOCK: case AE_IFCHR:
 772         case AE_IFBLK: case AE_IFIFO:
 773                 break;
 774         case AE_IFDIR:
 775                 if ((mtree->set.keys & F_TYPE) != 0 &&
 776                     mtree->set.type == AE_IFDIR)
 777                         keys &= ~F_TYPE;
 778                 break;
 779         case AE_IFREG:
 780         default:        /* Handle unknown file types as regular files. */
 781                 if ((mtree->set.keys & F_TYPE) != 0 &&
 782                     mtree->set.type == AE_IFREG)
 783                         keys &= ~F_TYPE;
 784                 break;
 785         }
 786
 787         return (keys);
 788 }
 789
 790 static int
 791 mtree_entry_new(struct archive_write *a, struct archive_entry *entry,
 792     struct mtree_entry **m_entry)
 793 {
 794         struct mtree_entry *me;
 795         const char *s;
 796         int r;
 797         static const struct archive_rb_tree_ops rb_ops = {
 798                 mtree_entry_cmp_node, mtree_entry_cmp_key
 799         };
 800
 801         me = calloc(1, sizeof(*me));
 802         if (me == NULL) {
 803                 archive_set_error(&a->archive, ENOMEM,
 804                     "Can't allocate memory for a mtree entry");
 805                 *m_entry = NULL;
 806                 return (ARCHIVE_FATAL);
 807         }
 808
 809         r = mtree_entry_setup_filenames(a, me, entry);
 810         if (r < ARCHIVE_WARN) {
 811                 mtree_entry_free(me);
 812                 *m_entry = NULL;
 813                 return (r);
 814         }
 815
 816         if ((s = archive_entry_symlink(entry)) != NULL)
 817                 archive_strcpy(&me->symlink, s);
 818         me->nlink = archive_entry_nlink(entry);
 819         me->filetype = archive_entry_filetype(entry);
 820         me->mode = archive_entry_mode(entry) & 07777;
 821         me->uid = archive_entry_uid(entry);
 822         me->gid = archive_entry_gid(entry);
 823         if ((s = archive_entry_uname(entry)) != NULL)
 824                 archive_strcpy(&me->uname, s);
 825         if ((s = archive_entry_gname(entry)) != NULL)
 826                 archive_strcpy(&me->gname, s);
 827         if ((s = archive_entry_fflags_text(entry)) != NULL)
 828                 archive_strcpy(&me->fflags_text, s);
 829         archive_entry_fflags(entry, &me->fflags_set, &me->fflags_clear);
 830         me->mtime = archive_entry_mtime(entry);
 831         me->mtime_nsec = archive_entry_mtime_nsec(entry);
 832         me->rdevmajor = archive_entry_rdevmajor(entry);
 833         me->rdevminor = archive_entry_rdevminor(entry);
 834         me->devmajor = archive_entry_devmajor(entry);
 835         me->devminor = archive_entry_devminor(entry);
 836         me->ino = archive_entry_ino(entry);
 837         me->size = archive_entry_size(entry);
 838         if (me->filetype == AE_IFDIR) {
 839                 me->dir_info = calloc(1, sizeof(*me->dir_info));
 840                 if (me->dir_info == NULL) {
 841                         mtree_entry_free(me);
 842                         archive_set_error(&a->archive, ENOMEM,
 843                             "Can't allocate memory for a mtree entry");
 844                         *m_entry = NULL;
 845                         return (ARCHIVE_FATAL);
 846                 }
 847                 __archive_rb_tree_init(&me->dir_info->rbtree, &rb_ops);
 848                 me->dir_info->children.first = NULL;
 849                 me->dir_info->children.last = &(me->dir_info->children.first);
 850                 me->dir_info->chnext = NULL;
 851         } else if (me->filetype == AE_IFREG) {
 852                 me->reg_info = calloc(1, sizeof(*me->reg_info));
 853                 if (me->reg_info == NULL) {
 854                         mtree_entry_free(me);
 855                         archive_set_error(&a->archive, ENOMEM,
 856                             "Can't allocate memory for a mtree entry");
 857                         *m_entry = NULL;
 858                         return (ARCHIVE_FATAL);
 859                 }
 860                 me->reg_info->compute_sum = 0;
 861         }
 862
 863         *m_entry = me;
 864         return (ARCHIVE_OK);
 865 }
 866
 867 static void
 868 mtree_entry_free(struct mtree_entry *me)
 869 {
 870         archive_string_free(&me->parentdir);
 871         archive_string_free(&me->basename);
 872         archive_string_free(&me->pathname);
 873         archive_string_free(&me->symlink);
 874         archive_string_free(&me->uname);
 875         archive_string_free(&me->gname);
 876         archive_string_free(&me->fflags_text);
 877         free(me->dir_info);
 878         free(me->reg_info);
 879         free(me);
 880 }
 881
 882 static int
 883 archive_write_mtree_header(struct archive_write *a,
 884     struct archive_entry *entry)
 885 {
 886         struct mtree_writer *mtree= a->format_data;
 887         struct mtree_entry *mtree_entry;
 888         int r, r2;
 889
 890         if (mtree->first) {
 891                 mtree->first = 0;
 892                 archive_strcat(&mtree->buf, "#mtree\n");
 893                 if ((mtree->keys & SET_KEYS) == 0)
 894                         mtree->output_global_set = 0;/* Disabled. */
 895         }
 896
 897         mtree->entry_bytes_remaining = archive_entry_size(entry);
 898
 899         /* While directory only mode, we do not handle non directory files. */
 900         if (mtree->dironly && archive_entry_filetype(entry) != AE_IFDIR)
 901                 return (ARCHIVE_OK);
 902
 903         r2 = mtree_entry_new(a, entry, &mtree_entry);
 904         if (r2 < ARCHIVE_WARN)
 905                 return (r2);
 906         r = mtree_entry_tree_add(a, &mtree_entry);
 907         if (r < ARCHIVE_WARN) {
 908                 mtree_entry_free(mtree_entry);
 909                 return (r);
 910         }
 911         mtree->mtree_entry = mtree_entry;
 912
 913         /* If the current file is a regular file, we have to
 914          * compute the sum of its content.
 915          * Initialize a bunch of sum check context. */
 916         if (mtree_entry->reg_info)
 917                 sum_init(mtree);
 918
 919         return (r2);
 920 }
 921
 922 static int
 923 write_mtree_entry(struct archive_write *a, struct mtree_entry *me)
 924 {
 925         struct mtree_writer *mtree = a->format_data;
 926         struct archive_string *str;
 927         int keys, ret;
 928
 929         if (me->dir_info) {
 930                 if (mtree->classic) {
 931                         /*
 932                          * Output a comment line to describe the full
 933                          * pathname of the entry as mtree utility does
 934                          * while generating classic format.
 935                          */
 936                         if (!mtree->dironly)
 937                                 archive_strappend_char(&mtree->buf, '\n');
 938                         if (me->parentdir.s)
 939                                 archive_string_sprintf(&mtree->buf,
 940                                     "# %s/%s\n",
 941                                     me->parentdir.s, me->basename.s);
 942                         else
 943                                 archive_string_sprintf(&mtree->buf,
 944                                     "# %s\n",
 945                                     me->basename.s);
 946                 }
 947                 if (mtree->output_global_set)
 948                         write_global(mtree);
 949         }
 950         archive_string_empty(&mtree->ebuf);
 951         str = (mtree->indent || mtree->classic)? &mtree->ebuf : &mtree->buf;
 952
 953         if (!mtree->classic && me->parentdir.s) {
 954                 /*
 955                  * If generating format is not classic one(v1), output
 956                  * a full pathname.
 957                  */
 958                 mtree_quote(str, me->parentdir.s);
 959                 archive_strappend_char(str, '/');
 960         }
 961         mtree_quote(str, me->basename.s);
 962
 963         keys = get_global_set_keys(mtree, me);
 964         if ((keys & F_NLINK) != 0 &&
 965             me->nlink != 1 && me->filetype != AE_IFDIR)
 966                 archive_string_sprintf(str, " nlink=%u", me->nlink);
 967
 968         if ((keys & F_GNAME) != 0 && archive_strlen(&me->gname) > 0) {
 969                 archive_strcat(str, " gname=");
 970                 mtree_quote(str, me->gname.s);
 971         }
 972         if ((keys & F_UNAME) != 0 && archive_strlen(&me->uname) > 0) {
 973                 archive_strcat(str, " uname=");
 974                 mtree_quote(str, me->uname.s);
 975         }
 976         if ((keys & F_FLAGS) != 0) {
 977                 if (archive_strlen(&me->fflags_text) > 0) {
 978                         archive_strcat(str, " flags=");
 979                         mtree_quote(str, me->fflags_text.s);
 980                 } else if (mtree->set.processing &&
 981                     (mtree->set.keys & F_FLAGS) != 0)
 982                         /* Overwrite the global parameter. */
 983                         archive_strcat(str, " flags=none");
 984         }
 985         if ((keys & F_TIME) != 0)
 986                 archive_string_sprintf(str, " time=%jd.%jd",
 987                     (intmax_t)me->mtime, (intmax_t)me->mtime_nsec);
 988         if ((keys & F_MODE) != 0)
 989                 archive_string_sprintf(str, " mode=%o", (unsigned int)me->mode);
 990         if ((keys & F_GID) != 0)
 991                 archive_string_sprintf(str, " gid=%jd", (intmax_t)me->gid);
 992         if ((keys & F_UID) != 0)
 993                 archive_string_sprintf(str, " uid=%jd", (intmax_t)me->uid);
 994
 995         if ((keys & F_INO) != 0)
 996                 archive_string_sprintf(str, " inode=%jd", (intmax_t)me->ino);
 997         if ((keys & F_RESDEV) != 0) {
 998                 archive_string_sprintf(str,
 999                     " resdevice=native,%ju,%ju",
1000                     (uintmax_t)me->devmajor,
1001                     (uintmax_t)me->devminor);
1002         }
1003
1004         switch (me->filetype) {
1005         case AE_IFLNK:
1006                 if ((keys & F_TYPE) != 0)
1007                         archive_strcat(str, " type=link");
1008                 if ((keys & F_SLINK) != 0) {
1009                         archive_strcat(str, " link=");
1010                         mtree_quote(str, me->symlink.s);
1011                 }
1012                 break;
1013         case AE_IFSOCK:
1014                 if ((keys & F_TYPE) != 0)
1015                         archive_strcat(str, " type=socket");
1016                 break;
1017         case AE_IFCHR:
1018                 if ((keys & F_TYPE) != 0)
1019                         archive_strcat(str, " type=char");
1020                 if ((keys & F_DEV) != 0) {
1021                         archive_string_sprintf(str,
1022                             " device=native,%ju,%ju",
1023                             (uintmax_t)me->rdevmajor,
1024                             (uintmax_t)me->rdevminor);
1025                 }
1026                 break;
1027         case AE_IFBLK:
1028                 if ((keys & F_TYPE) != 0)
1029                         archive_strcat(str, " type=block");
1030                 if ((keys & F_DEV) != 0) {
1031                         archive_string_sprintf(str,
1032                             " device=native,%ju,%ju",
1033                             (uintmax_t)me->rdevmajor,
1034                             (uintmax_t)me->rdevminor);
1035                 }
1036                 break;
1037         case AE_IFDIR:
1038                 if ((keys & F_TYPE) != 0)
1039                         archive_strcat(str, " type=dir");
1040                 break;
1041         case AE_IFIFO:
1042                 if ((keys & F_TYPE) != 0)
1043                         archive_strcat(str, " type=fifo");
1044                 break;
1045         case AE_IFREG:
1046         default:        /* Handle unknown file types as regular files. */
1047                 if ((keys & F_TYPE) != 0)
1048                         archive_strcat(str, " type=file");
1049                 if ((keys & F_SIZE) != 0)
1050                         archive_string_sprintf(str, " size=%jd",
1051                             (intmax_t)me->size);
1052                 break;
1053         }
1054
1055         /* Write a bunch of sum. */
1056         if (me->reg_info)
1057                 sum_write(str, me->reg_info);
1058
1059         archive_strappend_char(str, '\n');
1060         if (mtree->indent || mtree->classic)
1061                 mtree_indent(mtree);
1062
1063         if (mtree->buf.length > 32768) {
1064                 ret = __archive_write_output(
1065                         a, mtree->buf.s, mtree->buf.length);
1066                 archive_string_empty(&mtree->buf);
1067         } else
1068                 ret = ARCHIVE_OK;
1069         return (ret);
1070 }
1071
1072 static int
1073 write_dot_dot_entry(struct archive_write *a, struct mtree_entry *n)
1074 {
1075         struct mtree_writer *mtree = a->format_data;
1076         int ret;
1077
1078         if (n->parentdir.s) {
1079                 if (mtree->indent) {
1080                         int i, pd = mtree->depth * 4;
1081                         for (i = 0; i < pd; i++)
1082                                 archive_strappend_char(&mtree->buf, ' ');
1083                 }
1084                 archive_string_sprintf(&mtree->buf, "# %s/%s\n",
1085                         n->parentdir.s, n->basename.s);
1086         }
1087
1088         if (mtree->indent) {
1089                 archive_string_empty(&mtree->ebuf);
1090                 archive_strncat(&mtree->ebuf, "..\n\n", (mtree->dironly)?3:4);
1091                 mtree_indent(mtree);
1092         } else
1093                 archive_strncat(&mtree->buf, "..\n\n", (mtree->dironly)?3:4);
1094
1095         if (mtree->buf.length > 32768) {
1096                 ret = __archive_write_output(
1097                         a, mtree->buf.s, mtree->buf.length);
1098                 archive_string_empty(&mtree->buf);
1099         } else
1100                 ret = ARCHIVE_OK;
1101         return (ret);
1102 }
1103
1104 /*
1105  * Write mtree entries saved at attr_counter_set_collect() function.
1106  */
1107 static int
1108 write_mtree_entry_tree(struct archive_write *a)
1109 {
1110         struct mtree_writer *mtree = a->format_data;
1111         struct mtree_entry *np = mtree->root;
1112         struct archive_rb_node *n;
1113         int ret;
1114
1115         do {
1116                 if (mtree->output_global_set) {
1117                         /*
1118                          * Collect attribute information to know which value
1119                          * is frequently used among the children.
1120                          */
1121                         attr_counter_set_reset(mtree);
1122                         ARCHIVE_RB_TREE_FOREACH(n, &(np->dir_info->rbtree)) {
1123                                 struct mtree_entry *e = (struct mtree_entry *)n;
1124                                 if (attr_counter_set_collect(mtree, e) < 0) {
1125                                         archive_set_error(&a->archive, ENOMEM,
1126                                             "Can't allocate memory");
1127                                         return (ARCHIVE_FATAL);
1128                                 }
1129                         }
1130                 }
1131                 if (!np->dir_info->virtual || mtree->classic) {
1132                         ret = write_mtree_entry(a, np);
1133                         if (ret != ARCHIVE_OK)
1134                                 return (ARCHIVE_FATAL);
1135                 } else {
1136                         /* Whenever output_global_set is enabled
1137                          * output global value(/set keywords)
1138                          * even if the directory entry is not allowed
1139                          * to be written because the global values
1140                          * can be used for the children. */
1141                         if (mtree->output_global_set)
1142                                 write_global(mtree);
1143                 }
1144                 /*
1145                  * Output the attribute of all files except directory files.
1146                  */
1147                 mtree->depth++;
1148                 ARCHIVE_RB_TREE_FOREACH(n, &(np->dir_info->rbtree)) {
1149                         struct mtree_entry *e = (struct mtree_entry *)n;
1150
1151                         if (e->dir_info)
1152                                 mtree_entry_add_child_tail(np, e);
1153                         else {
1154                                 ret = write_mtree_entry(a, e);
1155                                 if (ret != ARCHIVE_OK)
1156                                         return (ARCHIVE_FATAL);
1157                         }
1158                 }
1159                 mtree->depth--;
1160
1161                 if (np->dir_info->children.first != NULL) {
1162                         /*
1163                          * Descend the tree.
1164                          */
1165                         np = np->dir_info->children.first;
1166                         if (mtree->indent)
1167                                 mtree->depth++;
1168                         continue;
1169                 } else if (mtree->classic) {
1170                         /*
1171                          * While printing mtree classic, if there are not
1172                          * any directory files(except "." and "..") in the
1173                          * directory, output two dots ".." as returning
1174                          * the parent directory.
1175                          */
1176                         ret = write_dot_dot_entry(a, np);
1177                         if (ret != ARCHIVE_OK)
1178                                 return (ARCHIVE_FATAL);
1179                 }
1180
1181                 while (np != np->parent) {
1182                         if (np->dir_info->chnext == NULL) {
1183                                 /*
1184                                  * Ascend the tree; go back to the parent.
1185                                  */
1186                                 if (mtree->indent)
1187                                         mtree->depth--;
1188                                 if (mtree->classic) {
1189                                         ret = write_dot_dot_entry(a,
1190                                                 np->parent);
1191                                         if (ret != ARCHIVE_OK)
1192                                                 return (ARCHIVE_FATAL);
1193                                 }
1194                                 np = np->parent;
1195                         } else {
1196                                 /*
1197                                  * Switch to next mtree entry in the directory.
1198                                  */
1199                                 np = np->dir_info->chnext;
1200                                 break;
1201                         }
1202                 }
1203         } while (np != np->parent);
1204
1205         return (ARCHIVE_OK);
1206 }
1207
1208 static int
1209 archive_write_mtree_finish_entry(struct archive_write *a)
1210 {
1211         struct mtree_writer *mtree = a->format_data;
1212         struct mtree_entry *me;
1213
1214         if ((me = mtree->mtree_entry) == NULL)
1215                 return (ARCHIVE_OK);
1216         mtree->mtree_entry = NULL;
1217
1218         if (me->reg_info)
1219                 sum_final(mtree, me->reg_info);
1220
1221         return (ARCHIVE_OK);
1222 }
1223
1224 static int
1225 archive_write_mtree_close(struct archive_write *a)
1226 {
1227         struct mtree_writer *mtree= a->format_data;
1228         int ret;
1229
1230         if (mtree->root != NULL) {
1231                 ret = write_mtree_entry_tree(a);
1232                 if (ret != ARCHIVE_OK)
1233                         return (ARCHIVE_FATAL);
1234         }
1235
1236         archive_write_set_bytes_in_last_block(&a->archive, 1);
1237
1238         return __archive_write_output(a, mtree->buf.s, mtree->buf.length);
1239 }
1240
1241 static ssize_t
1242 archive_write_mtree_data(struct archive_write *a, const void *buff, size_t n)
1243 {
1244         struct mtree_writer *mtree= a->format_data;
1245
1246         if (n > mtree->entry_bytes_remaining)
1247                 n = (size_t)mtree->entry_bytes_remaining;
1248         mtree->entry_bytes_remaining -= n;
1249
1250         /* We don't need to compute a regular file sum */
1251         if (mtree->mtree_entry == NULL)
1252                 return (n);
1253
1254         if (mtree->mtree_entry->filetype == AE_IFREG)
1255                 sum_update(mtree, buff, n);
1256
1257         return (n);
1258 }
1259
1260 static int
1261 archive_write_mtree_free(struct archive_write *a)
1262 {
1263         struct mtree_writer *mtree= a->format_data;
1264
1265         if (mtree == NULL)
1266                 return (ARCHIVE_OK);
1267
1268         /* Make sure we dot not leave any entries. */
1269         mtree_entry_register_free(mtree);
1270         archive_string_free(&mtree->cur_dirstr);
1271         archive_string_free(&mtree->ebuf);
1272         archive_string_free(&mtree->buf);
1273         attr_counter_set_free(mtree);
1274         free(mtree);
1275         a->format_data = NULL;
1276         return (ARCHIVE_OK);
1277 }
1278
1279 static int
1280 archive_write_mtree_options(struct archive_write *a, const char *key,
1281     const char *value)
1282 {
1283         struct mtree_writer *mtree= a->format_data;
1284         int keybit = 0;
1285
1286         switch (key[0]) {
1287         case 'a':
1288                 if (strcmp(key, "all") == 0)
1289                         keybit = ~0;
1290                 break;
1291         case 'c':
1292                 if (strcmp(key, "cksum") == 0)
1293                         keybit = F_CKSUM;
1294                 break;
1295         case 'd':
1296                 if (strcmp(key, "device") == 0)
1297                         keybit = F_DEV;
1298                 else if (strcmp(key, "dironly") == 0) {
1299                         mtree->dironly = (value != NULL)? 1: 0;
1300                         return (ARCHIVE_OK);
1301                 }
1302                 break;
1303         case 'f':
1304                 if (strcmp(key, "flags") == 0)
1305                         keybit = F_FLAGS;
1306                 break;
1307         case 'g':
1308                 if (strcmp(key, "gid") == 0)
1309                         keybit = F_GID;
1310                 else if (strcmp(key, "gname") == 0)
1311                         keybit = F_GNAME;
1312                 break;
1313         case 'i':
1314                 if (strcmp(key, "indent") == 0) {
1315                         mtree->indent = (value != NULL)? 1: 0;
1316                         return (ARCHIVE_OK);
1317                 } else if (strcmp(key, "inode") == 0) {
1318                         keybit = F_INO;
1319                 }
1320                 break;
1321         case 'l':
1322                 if (strcmp(key, "link") == 0)
1323                         keybit = F_SLINK;
1324                 break;
1325         case 'm':
1326                 if (strcmp(key, "md5") == 0 ||
1327                     strcmp(key, "md5digest") == 0)
1328                         keybit = F_MD5;
1329                 if (strcmp(key, "mode") == 0)
1330                         keybit = F_MODE;
1331                 break;
1332         case 'n':
1333                 if (strcmp(key, "nlink") == 0)
1334                         keybit = F_NLINK;
1335                 break;
1336         case 'r':
1337                 if (strcmp(key, "resdevice") == 0) {
1338                         keybit = F_RESDEV;
1339                 } else if (strcmp(key, "ripemd160digest") == 0 ||
1340                     strcmp(key, "rmd160") == 0 ||
1341                     strcmp(key, "rmd160digest") == 0)
1342                         keybit = F_RMD160;
1343                 break;
1344         case 's':
1345                 if (strcmp(key, "sha1") == 0 ||
1346                     strcmp(key, "sha1digest") == 0)
1347                         keybit = F_SHA1;
1348                 if (strcmp(key, "sha256") == 0 ||
1349                     strcmp(key, "sha256digest") == 0)
1350                         keybit = F_SHA256;
1351                 if (strcmp(key, "sha384") == 0 ||
1352                     strcmp(key, "sha384digest") == 0)
1353                         keybit = F_SHA384;
1354                 if (strcmp(key, "sha512") == 0 ||
1355                     strcmp(key, "sha512digest") == 0)
1356                         keybit = F_SHA512;
1357                 if (strcmp(key, "size") == 0)
1358                         keybit = F_SIZE;
1359                 break;
1360         case 't':
1361                 if (strcmp(key, "time") == 0)
1362                         keybit = F_TIME;
1363                 else if (strcmp(key, "type") == 0)
1364                         keybit = F_TYPE;
1365                 break;
1366         case 'u':
1367                 if (strcmp(key, "uid") == 0)
1368                         keybit = F_UID;
1369                 else if (strcmp(key, "uname") == 0)
1370                         keybit = F_UNAME;
1371                 else if (strcmp(key, "use-set") == 0) {
1372                         mtree->output_global_set = (value != NULL)? 1: 0;
1373                         return (ARCHIVE_OK);
1374                 }
1375                 break;
1376         }
1377         if (keybit != 0) {
1378                 if (value != NULL)
1379                         mtree->keys |= keybit;
1380                 else
1381                         mtree->keys &= ~keybit;
1382                 return (ARCHIVE_OK);
1383         }
1384
1385         /* Note: The "warn" return is just to inform the options
1386          * supervisor that we didn't handle it.  It will generate
1387          * a suitable error if no one used this option. */
1388         return (ARCHIVE_WARN);
1389 }
1390
1391 static int
1392 archive_write_set_format_mtree_default(struct archive *_a, const char *fn)
1393 {
1394         struct archive_write *a = (struct archive_write *)_a;
1395         struct mtree_writer *mtree;
1396
1397         archive_check_magic(_a, ARCHIVE_WRITE_MAGIC, ARCHIVE_STATE_NEW, fn);
1398
1399         if (a->format_free != NULL)
1400                 (a->format_free)(a);
1401
1402         if ((mtree = calloc(1, sizeof(*mtree))) == NULL) {
1403                 archive_set_error(&a->archive, ENOMEM,
1404                     "Can't allocate mtree data");
1405                 return (ARCHIVE_FATAL);
1406         }
1407
1408         mtree->mtree_entry = NULL;
1409         mtree->first = 1;
1410         memset(&(mtree->set), 0, sizeof(mtree->set));
1411         mtree->keys = DEFAULT_KEYS;
1412         mtree->dironly = 0;
1413         mtree->indent = 0;
1414         archive_string_init(&mtree->ebuf);
1415         archive_string_init(&mtree->buf);
1416         mtree_entry_register_init(mtree);
1417         a->format_data = mtree;
1418         a->format_free = archive_write_mtree_free;
1419         a->format_name = "mtree";
1420         a->format_options = archive_write_mtree_options;
1421         a->format_write_header = archive_write_mtree_header;
1422         a->format_close = archive_write_mtree_close;
1423         a->format_write_data = archive_write_mtree_data;
1424         a->format_finish_entry = archive_write_mtree_finish_entry;
1425         a->archive.archive_format = ARCHIVE_FORMAT_MTREE;
1426         a->archive.archive_format_name = "mtree";
1427
1428         return (ARCHIVE_OK);
1429 }
1430
1431 int
1432 archive_write_set_format_mtree(struct archive *_a)
1433 {
1434         return archive_write_set_format_mtree_default(_a,
1435                 "archive_write_set_format_mtree");
1436 }
1437
1438 int
1439 archive_write_set_format_mtree_classic(struct archive *_a)
1440 {
1441         int r;
1442
1443         r = archive_write_set_format_mtree_default(_a,
1444                 "archive_write_set_format_mtree_classic");
1445         if (r == ARCHIVE_OK) {
1446                 struct archive_write *a = (struct archive_write *)_a;
1447                 struct mtree_writer *mtree;
1448
1449                 mtree = (struct mtree_writer *)a->format_data;
1450
1451                 /* Set to output a mtree archive in classic format. */
1452                 mtree->classic = 1;
1453                 /* Basically, mtree classic format uses '/set' global
1454                  * value. */
1455                 mtree->output_global_set = 1;
1456         }
1457         return (r);
1458 }
1459
1460 static void
1461 sum_init(struct mtree_writer *mtree)
1462 {
1463
1464         mtree->compute_sum = 0;
1465
1466         if (mtree->keys & F_CKSUM) {
1467                 mtree->compute_sum |= F_CKSUM;
1468                 mtree->crc = 0;
1469                 mtree->crc_len = 0;
1470         }
1471 #ifdef ARCHIVE_HAS_MD5
1472         if (mtree->keys & F_MD5) {
1473                 if (archive_md5_init(&mtree->md5ctx) == ARCHIVE_OK)
1474                         mtree->compute_sum |= F_MD5;
1475                 else
1476                         mtree->keys &= ~F_MD5;/* Not supported. */
1477         }
1478 #endif
1479 #ifdef ARCHIVE_HAS_RMD160
1480         if (mtree->keys & F_RMD160) {
1481                 if (archive_rmd160_init(&mtree->rmd160ctx) == ARCHIVE_OK)
1482                         mtree->compute_sum |= F_RMD160;
1483                 else
1484                         mtree->keys &= ~F_RMD160;/* Not supported. */
1485         }
1486 #endif
1487 #ifdef ARCHIVE_HAS_SHA1
1488         if (mtree->keys & F_SHA1) {
1489                 if (archive_sha1_init(&mtree->sha1ctx) == ARCHIVE_OK)
1490                         mtree->compute_sum |= F_SHA1;
1491                 else
1492                         mtree->keys &= ~F_SHA1;/* Not supported. */
1493         }
1494 #endif
1495 #ifdef ARCHIVE_HAS_SHA256
1496         if (mtree->keys & F_SHA256) {
1497                 if (archive_sha256_init(&mtree->sha256ctx) == ARCHIVE_OK)
1498                         mtree->compute_sum |= F_SHA256;
1499                 else
1500                         mtree->keys &= ~F_SHA256;/* Not supported. */
1501         }
1502 #endif
1503 #ifdef ARCHIVE_HAS_SHA384
1504         if (mtree->keys & F_SHA384) {
1505                 if (archive_sha384_init(&mtree->sha384ctx) == ARCHIVE_OK)
1506                         mtree->compute_sum |= F_SHA384;
1507                 else
1508                         mtree->keys &= ~F_SHA384;/* Not supported. */
1509         }
1510 #endif
1511 #ifdef ARCHIVE_HAS_SHA512
1512         if (mtree->keys & F_SHA512) {
1513                 if (archive_sha512_init(&mtree->sha512ctx) == ARCHIVE_OK)
1514                         mtree->compute_sum |= F_SHA512;
1515                 else
1516                         mtree->keys &= ~F_SHA512;/* Not supported. */
1517         }
1518 #endif
1519 }
1520
1521 static void
1522 sum_update(struct mtree_writer *mtree, const void *buff, size_t n)
1523 {
1524         if (mtree->compute_sum & F_CKSUM) {
1525                 /*
1526                  * Compute a POSIX 1003.2 checksum
1527                  */
1528                 const unsigned char *p;
1529                 size_t nn;
1530
1531                 for (nn = n, p = buff; nn--; ++p)
1532                         COMPUTE_CRC(mtree->crc, *p);
1533                 mtree->crc_len += n;
1534         }
1535 #ifdef ARCHIVE_HAS_MD5
1536         if (mtree->compute_sum & F_MD5)
1537                 archive_md5_update(&mtree->md5ctx, buff, n);
1538 #endif
1539 #ifdef ARCHIVE_HAS_RMD160
1540         if (mtree->compute_sum & F_RMD160)
1541                 archive_rmd160_update(&mtree->rmd160ctx, buff, n);
1542 #endif
1543 #ifdef ARCHIVE_HAS_SHA1
1544         if (mtree->compute_sum & F_SHA1)
1545                 archive_sha1_update(&mtree->sha1ctx, buff, n);
1546 #endif
1547 #ifdef ARCHIVE_HAS_SHA256
1548         if (mtree->compute_sum & F_SHA256)
1549                 archive_sha256_update(&mtree->sha256ctx, buff, n);
1550 #endif
1551 #ifdef ARCHIVE_HAS_SHA384
1552         if (mtree->compute_sum & F_SHA384)
1553                 archive_sha384_update(&mtree->sha384ctx, buff, n);
1554 #endif
1555 #ifdef ARCHIVE_HAS_SHA512
1556         if (mtree->compute_sum & F_SHA512)
1557                 archive_sha512_update(&mtree->sha512ctx, buff, n);
1558 #endif
1559 }
1560
1561 static void
1562 sum_final(struct mtree_writer *mtree, struct reg_info *reg)
1563 {
1564
1565         if (mtree->compute_sum & F_CKSUM) {
1566                 uint64_t len;
1567                 /* Include the length of the file. */
1568                 for (len = mtree->crc_len; len != 0; len >>= 8)
1569                         COMPUTE_CRC(mtree->crc, len & 0xff);
1570                 reg->crc = ~mtree->crc;
1571         }
1572 #ifdef ARCHIVE_HAS_MD5
1573         if (mtree->compute_sum & F_MD5)
1574                 archive_md5_final(&mtree->md5ctx, reg->buf_md5);
1575 #endif
1576 #ifdef ARCHIVE_HAS_RMD160
1577         if (mtree->compute_sum & F_RMD160)
1578                 archive_rmd160_final(&mtree->rmd160ctx, reg->buf_rmd160);
1579 #endif
1580 #ifdef ARCHIVE_HAS_SHA1
1581         if (mtree->compute_sum & F_SHA1)
1582                 archive_sha1_final(&mtree->sha1ctx, reg->buf_sha1);
1583 #endif
1584 #ifdef ARCHIVE_HAS_SHA256
1585         if (mtree->compute_sum & F_SHA256)
1586                 archive_sha256_final(&mtree->sha256ctx, reg->buf_sha256);
1587 #endif
1588 #ifdef ARCHIVE_HAS_SHA384
1589         if (mtree->compute_sum & F_SHA384)
1590                 archive_sha384_final(&mtree->sha384ctx, reg->buf_sha384);
1591 #endif
1592 #ifdef ARCHIVE_HAS_SHA512
1593         if (mtree->compute_sum & F_SHA512)
1594                 archive_sha512_final(&mtree->sha512ctx, reg->buf_sha512);
1595 #endif
1596         /* Save what types of sum are computed. */
1597         reg->compute_sum = mtree->compute_sum;
1598 }
1599
1600 #if defined(ARCHIVE_HAS_MD5) || defined(ARCHIVE_HAS_RMD160) || \
1601     defined(ARCHIVE_HAS_SHA1) || defined(ARCHIVE_HAS_SHA256) || \
1602     defined(ARCHIVE_HAS_SHA384) || defined(ARCHIVE_HAS_SHA512)
1603 static void
1604 strappend_bin(struct archive_string *s, const unsigned char *bin, int n)
1605 {
1606         static const char hex[] = "0123456789abcdef";
1607         int i;
1608
1609         for (i = 0; i < n; i++) {
1610                 archive_strappend_char(s, hex[bin[i] >> 4]);
1611                 archive_strappend_char(s, hex[bin[i] & 0x0f]);
1612         }
1613 }
1614 #endif
1615
1616 static void
1617 sum_write(struct archive_string *str, struct reg_info *reg)
1618 {
1619
1620         if (reg->compute_sum & F_CKSUM) {
1621                 archive_string_sprintf(str, " cksum=%ju",
1622                     (uintmax_t)reg->crc);
1623         }
1624 #ifdef ARCHIVE_HAS_MD5
1625         if (reg->compute_sum & F_MD5) {
1626                 archive_strcat(str, " md5digest=");
1627                 strappend_bin(str, reg->buf_md5, sizeof(reg->buf_md5));
1628         }
1629 #endif
1630 #ifdef ARCHIVE_HAS_RMD160
1631         if (reg->compute_sum & F_RMD160) {
1632                 archive_strcat(str, " rmd160digest=");
1633                 strappend_bin(str, reg->buf_rmd160, sizeof(reg->buf_rmd160));
1634         }
1635 #endif
1636 #ifdef ARCHIVE_HAS_SHA1
1637         if (reg->compute_sum & F_SHA1) {
1638                 archive_strcat(str, " sha1digest=");
1639                 strappend_bin(str, reg->buf_sha1, sizeof(reg->buf_sha1));
1640         }
1641 #endif
1642 #ifdef ARCHIVE_HAS_SHA256
1643         if (reg->compute_sum & F_SHA256) {
1644                 archive_strcat(str, " sha256digest=");
1645                 strappend_bin(str, reg->buf_sha256, sizeof(reg->buf_sha256));
1646         }
1647 #endif
1648 #ifdef ARCHIVE_HAS_SHA384
1649         if (reg->compute_sum & F_SHA384) {
1650                 archive_strcat(str, " sha384digest=");
1651                 strappend_bin(str, reg->buf_sha384, sizeof(reg->buf_sha384));
1652         }
1653 #endif
1654 #ifdef ARCHIVE_HAS_SHA512
1655         if (reg->compute_sum & F_SHA512) {
1656                 archive_strcat(str, " sha512digest=");
1657                 strappend_bin(str, reg->buf_sha512, sizeof(reg->buf_sha512));
1658         }
1659 #endif
1660 }
1661
1662 static int
1663 mtree_entry_cmp_node(const struct archive_rb_node *n1,
1664     const struct archive_rb_node *n2)
1665 {
1666         const struct mtree_entry *e1 = (const struct mtree_entry *)n1;
1667         const struct mtree_entry *e2 = (const struct mtree_entry *)n2;
1668
1669         return (strcmp(e2->basename.s, e1->basename.s));
1670 }
1671
1672 static int
1673 mtree_entry_cmp_key(const struct archive_rb_node *n, const void *key)
1674 {
1675         const struct mtree_entry *e = (const struct mtree_entry *)n;
1676
1677         return (strcmp((const char *)key, e->basename.s));
1678 }
1679
1680 #if defined(_WIN32) || defined(__CYGWIN__)
1681 static int
1682 cleanup_backslash_1(char *p)
1683 {
1684         int mb, dos;
1685
1686         mb = dos = 0;
1687         while (*p) {
1688                 if (*(unsigned char *)p > 127)
1689                         mb = 1;
1690                 if (*p == '\\') {
1691                         /* If we have not met any multi-byte characters,
1692                          * we can replace '\' with '/'. */
1693                         if (!mb)
1694                                 *p = '/';
1695                         dos = 1;
1696                 }
1697                 p++;
1698         }
1699         if (!mb || !dos)
1700                 return (0);
1701         return (-1);
1702 }
1703
1704 static void
1705 cleanup_backslash_2(wchar_t *p)
1706 {
1707
1708         /* Convert a path-separator from '\' to  '/' */
1709         while (*p != L'\0') {
1710                 if (*p == L'\\')
1711                         *p = L'/';
1712                 p++;
1713         }
1714 }
1715 #endif
1716
1717 /*
1718  * Generate a parent directory name and a base name from a pathname.
1719  */
1720 static int
1721 mtree_entry_setup_filenames(struct archive_write *a, struct mtree_entry *file,
1722     struct archive_entry *entry)
1723 {
1724         const char *pathname;
1725         char *p, *dirname, *slash;
1726         size_t len;
1727         int ret = ARCHIVE_OK;
1728
1729         archive_strcpy(&file->pathname, archive_entry_pathname(entry));
1730 #if defined(_WIN32) || defined(__CYGWIN__)
1731         /*
1732          * Convert a path-separator from '\' to  '/'
1733          */
1734         if (cleanup_backslash_1(file->pathname.s) != 0) {
1735                 const wchar_t *wp = archive_entry_pathname_w(entry);
1736                 struct archive_wstring ws;
1737
1738                 if (wp != NULL) {
1739                         int r;
1740                         archive_string_init(&ws);
1741                         archive_wstrcpy(&ws, wp);
1742                         cleanup_backslash_2(ws.s);
1743                         archive_string_empty(&(file->pathname));
1744                         r = archive_string_append_from_wcs(&(file->pathname),
1745                             ws.s, ws.length);
1746                         archive_wstring_free(&ws);
1747                         if (r < 0 && errno == ENOMEM) {
1748                                 archive_set_error(&a->archive, ENOMEM,
1749                                     "Can't allocate memory");
1750                                 return (ARCHIVE_FATAL);
1751                         }
1752                 }
1753         }
1754 #else
1755         (void)a; /* UNUSED */
1756 #endif
1757         pathname =  file->pathname.s;
1758         if (strcmp(pathname, ".") == 0) {
1759                 archive_strcpy(&file->basename, ".");
1760                 return (ARCHIVE_OK);
1761         }
1762
1763         archive_strcpy(&(file->parentdir), pathname);
1764
1765         len = file->parentdir.length;
1766         p = dirname = file->parentdir.s;
1767
1768         /*
1769          * Remove leading '/' and '../' elements
1770          */
1771         while (*p) {
1772                 if (p[0] == '/') {
1773                         p++;
1774                         len--;
1775                 } else if (p[0] != '.')
1776                         break;
1777                 else if (p[1] == '.' && p[2] == '/') {
1778                         p += 3;
1779                         len -= 3;
1780                 } else
1781                         break;
1782         }
1783         if (p != dirname) {
1784                 memmove(dirname, p, len+1);
1785                 p = dirname;
1786         }
1787         /*
1788          * Remove "/","/." and "/.." elements from tail.
1789          */
1790         while (len > 0) {
1791                 size_t ll = len;
1792
1793                 if (len > 0 && p[len-1] == '/') {
1794                         p[len-1] = '\0';
1795                         len--;
1796                 }
1797                 if (len > 1 && p[len-2] == '/' && p[len-1] == '.') {
1798                         p[len-2] = '\0';
1799                         len -= 2;
1800                 }
1801                 if (len > 2 && p[len-3] == '/' && p[len-2] == '.' &&
1802                     p[len-1] == '.') {
1803                         p[len-3] = '\0';
1804                         len -= 3;
1805                 }
1806                 if (ll == len)
1807                         break;
1808         }
1809         while (*p) {
1810                 if (p[0] == '/') {
1811                         if (p[1] == '/')
1812                                 /* Convert '//' --> '/' */
1813                                 strcpy(p, p+1);
1814                         else if (p[1] == '.' && p[2] == '/')
1815                                 /* Convert '/./' --> '/' */
1816                                 strcpy(p, p+2);
1817                         else if (p[1] == '.' && p[2] == '.' && p[3] == '/') {
1818                                 /* Convert 'dir/dir1/../dir2/'
1819                                  *     --> 'dir/dir2/'
1820                                  */
1821                                 char *rp = p -1;
1822                                 while (rp >= dirname) {
1823                                         if (*rp == '/')
1824                                                 break;
1825                                         --rp;
1826                                 }
1827                                 if (rp > dirname) {
1828                                         strcpy(rp, p+3);
1829                                         p = rp;
1830                                 } else {
1831                                         strcpy(dirname, p+4);
1832                                         p = dirname;
1833                                 }
1834                         } else
1835                                 p++;
1836                 } else
1837                         p++;
1838         }
1839         p = dirname;
1840         len = strlen(p);
1841
1842         /*
1843          * Add "./" prefix.
1844          * NOTE: If the pathname does not have a path separator, we have
1845          * to add "./" to the head of the pathname because mtree reader
1846          * will suppose that it is v1(a.k.a classic) mtree format and
1847          * change the directory unexpectedly and so it will make a wrong
1848          * path.
1849          */
1850         if (strcmp(p, ".") != 0 && strncmp(p, "./", 2) != 0) {
1851                 struct archive_string as;
1852                 archive_string_init(&as);
1853                 archive_strcpy(&as, "./");
1854                 archive_strncat(&as, p, len);
1855                 archive_string_empty(&file->parentdir);
1856                 archive_string_concat(&file->parentdir, &as);
1857                 archive_string_free(&as);
1858                 p = file->parentdir.s;
1859                 len = archive_strlen(&file->parentdir);
1860         }
1861
1862         /*
1863          * Find out the position which points the last position of
1864          * path separator('/').
1865          */
1866         slash = NULL;
1867         for (; *p != '\0'; p++) {
1868                 if (*p == '/')
1869                         slash = p;
1870         }
1871         if (slash == NULL) {
1872                 /* The pathname doesn't have a parent directory. */
1873                 file->parentdir.length = len;
1874                 archive_string_copy(&(file->basename), &(file->parentdir));
1875                 archive_string_empty(&(file->parentdir));
1876                 *file->parentdir.s = '\0';
1877                 return (ret);
1878         }
1879
1880         /* Make a basename from file->parentdir.s and slash */
1881         *slash  = '\0';
1882         file->parentdir.length = slash - file->parentdir.s;
1883         archive_strcpy(&(file->basename),  slash + 1);
1884         return (ret);
1885 }
1886
1887 static int
1888 mtree_entry_create_virtual_dir(struct archive_write *a, const char *pathname,
1889     struct mtree_entry **m_entry)
1890 {
1891         struct archive_entry *entry;
1892         struct mtree_entry *file;
1893         int r;
1894
1895         entry = archive_entry_new();
1896         if (entry == NULL) {
1897                 *m_entry = NULL;
1898                 archive_set_error(&a->archive, ENOMEM,
1899                     "Can't allocate memory");
1900                 return (ARCHIVE_FATAL);
1901         }
1902         archive_entry_copy_pathname(entry, pathname);
1903         archive_entry_set_mode(entry, AE_IFDIR | 0755);
1904         archive_entry_set_mtime(entry, time(NULL), 0);
1905
1906         r = mtree_entry_new(a, entry, &file);
1907         archive_entry_free(entry);
1908         if (r < ARCHIVE_WARN) {
1909                 *m_entry = NULL;
1910                 archive_set_error(&a->archive, ENOMEM,
1911                     "Can't allocate memory");
1912                 return (ARCHIVE_FATAL);
1913         }
1914
1915         file->dir_info->virtual = 1;
1916
1917         *m_entry = file;
1918         return (ARCHIVE_OK);
1919 }
1920
1921 static void
1922 mtree_entry_register_add(struct mtree_writer *mtree, struct mtree_entry *file)
1923 {
1924         file->next = NULL;
1925         *mtree->file_list.last = file;
1926         mtree->file_list.last = &(file->next);
1927 }
1928
1929 static void
1930 mtree_entry_register_init(struct mtree_writer *mtree)
1931 {
1932         mtree->file_list.first = NULL;
1933         mtree->file_list.last = &(mtree->file_list.first);
1934 }
1935
1936 static void
1937 mtree_entry_register_free(struct mtree_writer *mtree)
1938 {
1939         struct mtree_entry *file, *file_next;
1940
1941         file = mtree->file_list.first;
1942         while (file != NULL) {
1943                 file_next = file->next;
1944                 mtree_entry_free(file);
1945                 file = file_next;
1946         }
1947 }
1948
1949 static int
1950 mtree_entry_add_child_tail(struct mtree_entry *parent,
1951     struct mtree_entry *child)
1952 {
1953         child->dir_info->chnext = NULL;
1954         *parent->dir_info->children.last = child;
1955         parent->dir_info->children.last = &(child->dir_info->chnext);
1956         return (1);
1957 }
1958
1959 /*
1960  * Find a entry from a parent entry with the name.
1961  */
1962 static struct mtree_entry *
1963 mtree_entry_find_child(struct mtree_entry *parent, const char *child_name)
1964 {
1965         struct mtree_entry *np;
1966
1967         if (parent == NULL)
1968                 return (NULL);
1969         np = (struct mtree_entry *)__archive_rb_tree_find_node(
1970             &(parent->dir_info->rbtree), child_name);
1971         return (np);
1972 }
1973
1974 static int
1975 get_path_component(char *name, size_t n, const char *fn)
1976 {
1977         char *p;
1978         size_t l;
1979
1980         p = strchr(fn, '/');
1981         if (p == NULL) {
1982                 if ((l = strlen(fn)) == 0)
1983                         return (0);
1984         } else
1985                 l = p - fn;
1986         if (l > n -1)
1987                 return (-1);
1988         memcpy(name, fn, l);
1989         name[l] = '\0';
1990
1991         return ((int)l);
1992 }
1993
1994 /*
1995  * Add a new entry into the tree.
1996  */
1997 static int
1998 mtree_entry_tree_add(struct archive_write *a, struct mtree_entry **filep)
1999 {
2000 #if defined(_WIN32) && !defined(__CYGWIN__)
2001         char name[_MAX_FNAME];/* Included null terminator size. */
2002 #elif defined(NAME_MAX) && NAME_MAX >= 255
2003         char name[NAME_MAX+1];
2004 #else
2005         char name[256];
2006 #endif
2007         struct mtree_writer *mtree = (struct mtree_writer *)a->format_data;
2008         struct mtree_entry *dent, *file, *np;
2009         const char *fn, *p;
2010         int l, r;
2011
2012         file = *filep;
2013         if (file->parentdir.length == 0 && file->basename.length == 1 &&
2014             file->basename.s[0] == '.') {
2015                 file->parent = file;
2016                 if (mtree->root != NULL) {
2017                         np = mtree->root;
2018                         goto same_entry;
2019                 }
2020                 mtree->root = file;
2021                 mtree_entry_register_add(mtree, file);
2022                 return (ARCHIVE_OK);
2023         }
2024
2025         if (file->parentdir.length == 0) {
2026                 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
2027                     "Internal programing error "
2028                     "in generating canonical name for %s",
2029                     file->pathname.s);
2030                 return (ARCHIVE_FAILED);
2031         }
2032
2033         fn = p = file->parentdir.s;
2034
2035         /*
2036          * If the path of the parent directory of `file' entry is
2037          * the same as the path of `cur_dirent', add `file' entry to
2038          * `cur_dirent'.
2039          */
2040         if (archive_strlen(&(mtree->cur_dirstr))
2041               == archive_strlen(&(file->parentdir)) &&
2042             strcmp(mtree->cur_dirstr.s, fn) == 0) {
2043                 if (!__archive_rb_tree_insert_node(
2044                     &(mtree->cur_dirent->dir_info->rbtree),
2045                     (struct archive_rb_node *)file)) {
2046                         /* There is the same name in the tree. */
2047                         np = (struct mtree_entry *)__archive_rb_tree_find_node(
2048                             &(mtree->cur_dirent->dir_info->rbtree),
2049                             file->basename.s);
2050                         goto same_entry;
2051                 }
2052                 file->parent = mtree->cur_dirent;
2053                 mtree_entry_register_add(mtree, file);
2054                 return (ARCHIVE_OK);
2055         }
2056
2057         dent = mtree->root;
2058         for (;;) {
2059                 l = get_path_component(name, sizeof(name), fn);
2060                 if (l == 0) {
2061                         np = NULL;
2062                         break;
2063                 }
2064                 if (l < 0) {
2065                         archive_set_error(&a->archive,
2066                             ARCHIVE_ERRNO_MISC,
2067                             "A name buffer is too small");
2068                         return (ARCHIVE_FATAL);
2069                 }
2070                 if (l == 1 && name[0] == '.' && dent != NULL &&
2071                     dent == mtree->root) {
2072                         fn += l;
2073                         if (fn[0] == '/')
2074                                 fn++;
2075                         continue;
2076                 }
2077
2078                 np = mtree_entry_find_child(dent, name);
2079                 if (np == NULL || fn[0] == '\0')
2080                         break;
2081
2082                 /* Find next sub directory. */
2083                 if (!np->dir_info) {
2084                         /* NOT Directory! */
2085                         archive_set_error(&a->archive,
2086                             ARCHIVE_ERRNO_MISC,
2087                             "`%s' is not directory, we cannot insert `%s' ",
2088                             np->pathname.s, file->pathname.s);
2089                         return (ARCHIVE_FAILED);
2090                 }
2091                 fn += l;
2092                 if (fn[0] == '/')
2093                         fn++;
2094                 dent = np;
2095         }
2096         if (np == NULL) {
2097                 /*
2098                  * Create virtual parent directories.
2099                  */
2100                 while (fn[0] != '\0') {
2101                         struct mtree_entry *vp;
2102                         struct archive_string as;
2103
2104                         archive_string_init(&as);
2105                         archive_strncat(&as, p, fn - p + l);
2106                         if (as.s[as.length-1] == '/') {
2107                                 as.s[as.length-1] = '\0';
2108                                 as.length--;
2109                         }
2110                         r = mtree_entry_create_virtual_dir(a, as.s, &vp);
2111                         archive_string_free(&as);
2112                         if (r < ARCHIVE_WARN)
2113                                 return (r);
2114
2115                         if (strcmp(vp->pathname.s, ".") == 0) {
2116                                 vp->parent = vp;
2117                                 mtree->root = vp;
2118                         } else {
2119                                 __archive_rb_tree_insert_node(
2120                                     &(dent->dir_info->rbtree),
2121                                     (struct archive_rb_node *)vp);
2122                                 vp->parent = dent;
2123                         }
2124                         mtree_entry_register_add(mtree, vp);
2125                         np = vp;
2126
2127                         fn += l;
2128                         if (fn[0] == '/')
2129                                 fn++;
2130                         l = get_path_component(name, sizeof(name), fn);
2131                         if (l < 0) {
2132                                 archive_string_free(&as);
2133                                 archive_set_error(&a->archive,
2134                                     ARCHIVE_ERRNO_MISC,
2135                                     "A name buffer is too small");
2136                                 return (ARCHIVE_FATAL);
2137                         }
2138                         dent = np;
2139                 }
2140
2141                 /* Found out the parent directory where `file' can be
2142                  * inserted. */
2143                 mtree->cur_dirent = dent;
2144                 archive_string_empty(&(mtree->cur_dirstr));
2145                 archive_string_ensure(&(mtree->cur_dirstr),
2146                     archive_strlen(&(dent->parentdir)) +
2147                     archive_strlen(&(dent->basename)) + 2);
2148                 if (archive_strlen(&(dent->parentdir)) +
2149                     archive_strlen(&(dent->basename)) == 0)
2150                         mtree->cur_dirstr.s[0] = 0;
2151                 else {
2152                         if (archive_strlen(&(dent->parentdir)) > 0) {
2153                                 archive_string_copy(&(mtree->cur_dirstr),
2154                                     &(dent->parentdir));
2155                                 archive_strappend_char(
2156                                     &(mtree->cur_dirstr), '/');
2157                         }
2158                         archive_string_concat(&(mtree->cur_dirstr),
2159                             &(dent->basename));
2160                 }
2161
2162                 if (!__archive_rb_tree_insert_node(
2163                     &(dent->dir_info->rbtree),
2164                     (struct archive_rb_node *)file)) {
2165                         np = (struct mtree_entry *)__archive_rb_tree_find_node(
2166                             &(dent->dir_info->rbtree), file->basename.s);
2167                         goto same_entry;
2168                 }
2169                 file->parent = dent;
2170                 mtree_entry_register_add(mtree, file);
2171                 return (ARCHIVE_OK);
2172         }
2173
2174 same_entry:
2175         /*
2176          * We have already has the entry the filename of which is
2177          * the same.
2178          */
2179         r = mtree_entry_exchange_same_entry(a, np, file);
2180         if (r < ARCHIVE_WARN)
2181                 return (r);
2182         if (np->dir_info)
2183                 np->dir_info->virtual = 0;
2184         *filep = np;
2185         mtree_entry_free(file);
2186         return (ARCHIVE_WARN);
2187 }
2188
2189 static int
2190 mtree_entry_exchange_same_entry(struct archive_write *a, struct mtree_entry *np,
2191     struct mtree_entry *file)
2192 {
2193
2194         if ((np->mode & AE_IFMT) != (file->mode & AE_IFMT)) {
2195                 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
2196                     "Found duplicate entries `%s' and its file type is "
2197                     "different",
2198                     np->pathname.s);
2199                 return (ARCHIVE_FAILED);
2200         }
2201
2202         /* Update the existent mtree entry's attributes by the new one's. */
2203         archive_string_empty(&np->symlink);
2204         archive_string_concat(&np->symlink, &file->symlink);
2205         archive_string_empty(&np->uname);
2206         archive_string_concat(&np->uname, &file->uname);
2207         archive_string_empty(&np->gname);
2208         archive_string_concat(&np->gname, &file->gname);
2209         archive_string_empty(&np->fflags_text);
2210         archive_string_concat(&np->fflags_text, &file->fflags_text);
2211         np->nlink = file->nlink;
2212         np->filetype = file->filetype;
2213         np->mode = file->mode;
2214         np->size = file->size;
2215         np->uid = file->uid;
2216         np->gid = file->gid;
2217         np->fflags_set = file->fflags_set;
2218         np->fflags_clear = file->fflags_clear;
2219         np->mtime = file->mtime;
2220         np->mtime_nsec = file->mtime_nsec;
2221         np->rdevmajor = file->rdevmajor;
2222         np->rdevminor = file->rdevminor;
2223         np->devmajor = file->devmajor;
2224         np->devminor = file->devminor;
2225         np->ino = file->ino;
2226
2227         return (ARCHIVE_WARN);
2228 }