contrib/libarchive/libarchive/archive_read_support_format_mtree.c

   1 /*-
   2  * Copyright (c) 2003-2007 Tim Kientzle
   3  * Copyright (c) 2008 Joerg Sonnenberger
   4  * Copyright (c) 2011-2012 Michihiro NAKAJIMA
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
  17  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  19  * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
  20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  21  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  22  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  23  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  25  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include "archive_platform.h"
  29 __FBSDID("$FreeBSD$");
  30
  31 #ifdef HAVE_SYS_STAT_H
  32 #include <sys/stat.h>
  33 #endif
  34 #ifdef HAVE_ERRNO_H
  35 #include <errno.h>
  36 #endif
  37 #ifdef HAVE_FCNTL_H
  38 #include <fcntl.h>
  39 #endif
  40 #include <stddef.h>
  41 /* #include <stdint.h> */ /* See archive_platform.h */
  42 #ifdef HAVE_STDLIB_H
  43 #include <stdlib.h>
  44 #endif
  45 #ifdef HAVE_STRING_H
  46 #include <string.h>
  47 #endif
  48
  49 #include "archive.h"
  50 #include "archive_entry.h"
  51 #include "archive_private.h"
  52 #include "archive_read_private.h"
  53 #include "archive_string.h"
  54 #include "archive_pack_dev.h"
  55
  56 #ifndef O_BINARY
  57 #define O_BINARY 0
  58 #endif
  59 #ifndef O_CLOEXEC
  60 #define O_CLOEXEC       0
  61 #endif
  62
  63 #define MTREE_HAS_DEVICE        0x0001
  64 #define MTREE_HAS_FFLAGS        0x0002
  65 #define MTREE_HAS_GID           0x0004
  66 #define MTREE_HAS_GNAME         0x0008
  67 #define MTREE_HAS_MTIME         0x0010
  68 #define MTREE_HAS_NLINK         0x0020
  69 #define MTREE_HAS_PERM          0x0040
  70 #define MTREE_HAS_SIZE          0x0080
  71 #define MTREE_HAS_TYPE          0x0100
  72 #define MTREE_HAS_UID           0x0200
  73 #define MTREE_HAS_UNAME         0x0400
  74
  75 #define MTREE_HAS_OPTIONAL      0x0800
  76 #define MTREE_HAS_NOCHANGE      0x1000 /* FreeBSD specific */
  77
  78 #define MTREE_HASHTABLE_SIZE 1024
  79
  80 struct mtree_option {
  81         struct mtree_option *next;
  82         char *value;
  83 };
  84
  85 struct mtree_entry {
  86         struct mtree_entry *next;
  87         struct mtree_option *options;
  88         char *name;
  89         char full;
  90         char used;
  91         unsigned int name_hash;
  92         struct mtree_entry *hashtable_next;
  93 };
  94
  95 struct mtree {
  96         struct archive_string    line;
  97         size_t                   buffsize;
  98         char                    *buff;
  99         int64_t                  offset;
 100         int                      fd;
 101         int                      archive_format;
 102         const char              *archive_format_name;
 103         struct mtree_entry      *entries;
 104         struct mtree_entry      *this_entry;
 105         struct mtree_entry      *entry_hashtable[MTREE_HASHTABLE_SIZE];
 106         struct archive_string    current_dir;
 107         struct archive_string    contents_name;
 108
 109         struct archive_entry_linkresolver *resolver;
 110
 111         int64_t                  cur_size;
 112         char checkfs;
 113 };
 114
 115 static int      bid_keycmp(const char *, const char *, ssize_t);
 116 static int      cleanup(struct archive_read *);
 117 static int      detect_form(struct archive_read *, int *);
 118 static unsigned int     hash(const char *);
 119 static int      mtree_bid(struct archive_read *, int);
 120 static int      parse_file(struct archive_read *, struct archive_entry *,
 121                     struct mtree *, struct mtree_entry *, int *);
 122 static void     parse_escapes(char *, struct mtree_entry *);
 123 static int      parse_line(struct archive_read *, struct archive_entry *,
 124                     struct mtree *, struct mtree_entry *, int *);
 125 static int      parse_keyword(struct archive_read *, struct mtree *,
 126                     struct archive_entry *, struct mtree_option *, int *);
 127 static int      read_data(struct archive_read *a,
 128                     const void **buff, size_t *size, int64_t *offset);
 129 static ssize_t  readline(struct archive_read *, struct mtree *, char **, ssize_t);
 130 static int      skip(struct archive_read *a);
 131 static int      read_header(struct archive_read *,
 132                     struct archive_entry *);
 133 static int64_t  mtree_atol(char **, int base);
 134
 135 /*
 136  * There's no standard for TIME_T_MAX/TIME_T_MIN.  So we compute them
 137  * here.  TODO: Move this to configure time, but be careful
 138  * about cross-compile environments.
 139  */
 140 static int64_t
 141 get_time_t_max(void)
 142 {
 143 #if defined(TIME_T_MAX)
 144         return TIME_T_MAX;
 145 #else
 146         /* ISO C allows time_t to be a floating-point type,
 147            but POSIX requires an integer type.  The following
 148            should work on any system that follows the POSIX
 149            conventions. */
 150         if (((time_t)0) < ((time_t)-1)) {
 151                 /* Time_t is unsigned */
 152                 return (~(time_t)0);
 153         } else {
 154                 /* Time_t is signed. */
 155                 /* Assume it's the same as int64_t or int32_t */
 156                 if (sizeof(time_t) == sizeof(int64_t)) {
 157                         return (time_t)INT64_MAX;
 158                 } else {
 159                         return (time_t)INT32_MAX;
 160                 }
 161         }
 162 #endif
 163 }
 164
 165 static int64_t
 166 get_time_t_min(void)
 167 {
 168 #if defined(TIME_T_MIN)
 169         return TIME_T_MIN;
 170 #else
 171         if (((time_t)0) < ((time_t)-1)) {
 172                 /* Time_t is unsigned */
 173                 return (time_t)0;
 174         } else {
 175                 /* Time_t is signed. */
 176                 if (sizeof(time_t) == sizeof(int64_t)) {
 177                         return (time_t)INT64_MIN;
 178                 } else {
 179                         return (time_t)INT32_MIN;
 180                 }
 181         }
 182 #endif
 183 }
 184
 185 static int
 186 archive_read_format_mtree_options(struct archive_read *a,
 187     const char *key, const char *val)
 188 {
 189         struct mtree *mtree;
 190
 191         mtree = (struct mtree *)(a->format->data);
 192         if (strcmp(key, "checkfs")  == 0) {
 193                 /* Allows to read information missing from the mtree from the file system */
 194                 if (val == NULL || val[0] == 0) {
 195                         mtree->checkfs = 0;
 196                 } else {
 197                         mtree->checkfs = 1;
 198                 }
 199                 return (ARCHIVE_OK);
 200         }
 201
 202         /* Note: The "warn" return is just to inform the options
 203          * supervisor that we didn't handle it.  It will generate
 204          * a suitable error if no one used this option. */
 205         return (ARCHIVE_WARN);
 206 }
 207
 208 static void
 209 free_options(struct mtree_option *head)
 210 {
 211         struct mtree_option *next;
 212
 213         for (; head != NULL; head = next) {
 214                 next = head->next;
 215                 free(head->value);
 216                 free(head);
 217         }
 218 }
 219
 220 int
 221 archive_read_support_format_mtree(struct archive *_a)
 222 {
 223         struct archive_read *a = (struct archive_read *)_a;
 224         struct mtree *mtree;
 225         int r;
 226
 227         archive_check_magic(_a, ARCHIVE_READ_MAGIC,
 228             ARCHIVE_STATE_NEW, "archive_read_support_format_mtree");
 229
 230         mtree = (struct mtree *)calloc(1, sizeof(*mtree));
 231         if (mtree == NULL) {
 232                 archive_set_error(&a->archive, ENOMEM,
 233                     "Can't allocate mtree data");
 234                 return (ARCHIVE_FATAL);
 235         }
 236         mtree->fd = -1;
 237
 238         r = __archive_read_register_format(a, mtree, "mtree",
 239            mtree_bid, archive_read_format_mtree_options, read_header, read_data, skip, NULL, cleanup, NULL, NULL);
 240
 241         if (r != ARCHIVE_OK)
 242                 free(mtree);
 243         return (ARCHIVE_OK);
 244 }
 245
 246 static int
 247 cleanup(struct archive_read *a)
 248 {
 249         struct mtree *mtree;
 250         struct mtree_entry *p, *q;
 251
 252         mtree = (struct mtree *)(a->format->data);
 253
 254         p = mtree->entries;
 255         while (p != NULL) {
 256                 q = p->next;
 257                 free(p->name);
 258                 free_options(p->options);
 259                 free(p);
 260                 p = q;
 261         }
 262         archive_string_free(&mtree->line);
 263         archive_string_free(&mtree->current_dir);
 264         archive_string_free(&mtree->contents_name);
 265         archive_entry_linkresolver_free(mtree->resolver);
 266
 267         free(mtree->buff);
 268         free(mtree);
 269         (a->format->data) = NULL;
 270         return (ARCHIVE_OK);
 271 }
 272
 273 static ssize_t
 274 get_line_size(const char *b, ssize_t avail, ssize_t *nlsize)
 275 {
 276         ssize_t len;
 277
 278         len = 0;
 279         while (len < avail) {
 280                 switch (*b) {
 281                 case '\0':/* Non-ascii character or control character. */
 282                         if (nlsize != NULL)
 283                                 *nlsize = 0;
 284                         return (-1);
 285                 case '\r':
 286                         if (avail-len > 1 && b[1] == '\n') {
 287                                 if (nlsize != NULL)
 288                                         *nlsize = 2;
 289                                 return (len+2);
 290                         }
 291                         /* FALL THROUGH */
 292                 case '\n':
 293                         if (nlsize != NULL)
 294                                 *nlsize = 1;
 295                         return (len+1);
 296                 default:
 297                         b++;
 298                         len++;
 299                         break;
 300                 }
 301         }
 302         if (nlsize != NULL)
 303                 *nlsize = 0;
 304         return (avail);
 305 }
 306
 307 /*
 308  *  <---------------- ravail --------------------->
 309  *  <-- diff ------> <---  avail ----------------->
 310  *                   <---- len ----------->
 311  * | Previous lines | line being parsed  nl extra |
 312  *                  ^
 313  *                  b
 314  *
 315  */
 316 static ssize_t
 317 next_line(struct archive_read *a,
 318     const char **b, ssize_t *avail, ssize_t *ravail, ssize_t *nl)
 319 {
 320         ssize_t len;
 321         int quit;
 322
 323         quit = 0;
 324         if (*avail == 0) {
 325                 *nl = 0;
 326                 len = 0;
 327         } else
 328                 len = get_line_size(*b, *avail, nl);
 329         /*
 330          * Read bytes more while it does not reach the end of line.
 331          */
 332         while (*nl == 0 && len == *avail && !quit) {
 333                 ssize_t diff = *ravail - *avail;
 334                 size_t nbytes_req = (*ravail+1023) & ~1023U;
 335                 ssize_t tested;
 336
 337                 /* Increase reading bytes if it is not enough to at least
 338                  * new two lines. */
 339                 if (nbytes_req < (size_t)*ravail + 160)
 340                         nbytes_req <<= 1;
 341
 342                 *b = __archive_read_ahead(a, nbytes_req, avail);
 343                 if (*b == NULL) {
 344                         if (*ravail >= *avail)
 345                                 return (0);
 346                         /* Reading bytes reaches the end of file. */
 347                         *b = __archive_read_ahead(a, *avail, avail);
 348                         quit = 1;
 349                 }
 350                 *ravail = *avail;
 351                 *b += diff;
 352                 *avail -= diff;
 353                 tested = len;/* Skip some bytes we already determinated. */
 354                 len = get_line_size(*b + len, *avail - len, nl);
 355                 if (len >= 0)
 356                         len += tested;
 357         }
 358         return (len);
 359 }
 360
 361 /*
 362  * Compare characters with a mtree keyword.
 363  * Returns the length of a mtree keyword if matched.
 364  * Returns 0 if not matched.
 365  */
 366 static int
 367 bid_keycmp(const char *p, const char *key, ssize_t len)
 368 {
 369         int match_len = 0;
 370
 371         while (len > 0 && *p && *key) {
 372                 if (*p == *key) {
 373                         --len;
 374                         ++p;
 375                         ++key;
 376                         ++match_len;
 377                         continue;
 378                 }
 379                 return (0);/* Not match */
 380         }
 381         if (*key != '\0')
 382                 return (0);/* Not match */
 383
 384         /* A following character should be specified characters */
 385         if (p[0] == '=' || p[0] == ' ' || p[0] == '\t' ||
 386             p[0] == '\n' || p[0] == '\r' ||
 387            (p[0] == '\\' && (p[1] == '\n' || p[1] == '\r')))
 388                 return (match_len);
 389         return (0);/* Not match */
 390 }
 391
 392 /*
 393  * Test whether the characters 'p' has is mtree keyword.
 394  * Returns the length of a detected keyword.
 395  * Returns 0 if any keywords were not found.
 396  */
 397 static int
 398 bid_keyword(const char *p,  ssize_t len)
 399 {
 400         static const char * const keys_c[] = {
 401                 "content", "contents", "cksum", NULL
 402         };
 403         static const char * const keys_df[] = {
 404                 "device", "flags", NULL
 405         };
 406         static const char * const keys_g[] = {
 407                 "gid", "gname", NULL
 408         };
 409         static const char * const keys_il[] = {
 410                 "ignore", "inode", "link", NULL
 411         };
 412         static const char * const keys_m[] = {
 413                 "md5", "md5digest", "mode", NULL
 414         };
 415         static const char * const keys_no[] = {
 416                 "nlink", "nochange", "optional", NULL
 417         };
 418         static const char * const keys_r[] = {
 419                 "resdevice", "rmd160", "rmd160digest", NULL
 420         };
 421         static const char * const keys_s[] = {
 422                 "sha1", "sha1digest",
 423                 "sha256", "sha256digest",
 424                 "sha384", "sha384digest",
 425                 "sha512", "sha512digest",
 426                 "size", NULL
 427         };
 428         static const char * const keys_t[] = {
 429                 "tags", "time", "type", NULL
 430         };
 431         static const char * const keys_u[] = {
 432                 "uid", "uname", NULL
 433         };
 434         const char * const *keys;
 435         int i;
 436
 437         switch (*p) {
 438         case 'c': keys = keys_c; break;
 439         case 'd': case 'f': keys = keys_df; break;
 440         case 'g': keys = keys_g; break;
 441         case 'i': case 'l': keys = keys_il; break;
 442         case 'm': keys = keys_m; break;
 443         case 'n': case 'o': keys = keys_no; break;
 444         case 'r': keys = keys_r; break;
 445         case 's': keys = keys_s; break;
 446         case 't': keys = keys_t; break;
 447         case 'u': keys = keys_u; break;
 448         default: return (0);/* Unknown key */
 449         }
 450
 451         for (i = 0; keys[i] != NULL; i++) {
 452                 int l = bid_keycmp(p, keys[i], len);
 453                 if (l > 0)
 454                         return (l);
 455         }
 456         return (0);/* Unknown key */
 457 }
 458
 459 /*
 460  * Test whether there is a set of mtree keywords.
 461  * Returns the number of keyword.
 462  * Returns -1 if we got incorrect sequence.
 463  * This function expects a set of "<space characters>keyword=value".
 464  * When "unset" is specified, expects a set of "<space characters>keyword".
 465  */
 466 static int
 467 bid_keyword_list(const char *p,  ssize_t len, int unset, int last_is_path)
 468 {
 469         int l;
 470         int keycnt = 0;
 471
 472         while (len > 0 && *p) {
 473                 int blank = 0;
 474
 475                 /* Test whether there are blank characters in the line. */
 476                 while (len >0 && (*p == ' ' || *p == '\t')) {
 477                         ++p;
 478                         --len;
 479                         blank = 1;
 480                 }
 481                 if (*p == '\n' || *p == '\r')
 482                         break;
 483                 if (p[0] == '\\' && (p[1] == '\n' || p[1] == '\r'))
 484                         break;
 485                 if (!blank && !last_is_path) /* No blank character. */
 486                         return (-1);
 487                 if (last_is_path && len == 0)
 488                                 return (keycnt);
 489
 490                 if (unset) {
 491                         l = bid_keycmp(p, "all", len);
 492                         if (l > 0)
 493                                 return (1);
 494                 }
 495                 /* Test whether there is a correct key in the line. */
 496                 l = bid_keyword(p, len);
 497                 if (l == 0)
 498                         return (-1);/* Unknown keyword was found. */
 499                 p += l;
 500                 len -= l;
 501                 keycnt++;
 502
 503                 /* Skip value */
 504                 if (*p == '=') {
 505                         int value = 0;
 506                         ++p;
 507                         --len;
 508                         while (len > 0 && *p != ' ' && *p != '\t') {
 509                                 ++p;
 510                                 --len;
 511                                 value = 1;
 512                         }
 513                         /* A keyword should have a its value unless
 514                          * "/unset" operation. */
 515                         if (!unset && value == 0)
 516                                 return (-1);
 517                 }
 518         }
 519         return (keycnt);
 520 }
 521
 522 static int
 523 bid_entry(const char *p, ssize_t len, ssize_t nl, int *last_is_path)
 524 {
 525         int f = 0;
 526         static const unsigned char safe_char[256] = {
 527                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 00 - 0F */
 528                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 10 - 1F */
 529                 /* !"$%&'()*+,-./  EXCLUSION:( )(#) */
 530                 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 20 - 2F */
 531                 /* 0123456789:;<>?  EXCLUSION:(=) */
 532                 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, /* 30 - 3F */
 533                 /* @ABCDEFGHIJKLMNO */
 534                 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 40 - 4F */
 535                 /* PQRSTUVWXYZ[\]^_  */
 536                 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 50 - 5F */
 537                 /* `abcdefghijklmno */
 538                 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 60 - 6F */
 539                 /* pqrstuvwxyz{|}~ */
 540                 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, /* 70 - 7F */
 541                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 80 - 8F */
 542                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 90 - 9F */
 543                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* A0 - AF */
 544                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* B0 - BF */
 545                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* C0 - CF */
 546                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* D0 - DF */
 547                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* E0 - EF */
 548                 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* F0 - FF */
 549         };
 550         ssize_t ll;
 551         const char *pp = p;
 552         const char * const pp_end = pp + len;
 553
 554         *last_is_path = 0;
 555         /*
 556          * Skip the path-name which is quoted.
 557          */
 558         for (;pp < pp_end; ++pp) {
 559                 if (!safe_char[*(const unsigned char *)pp]) {
 560                         if (*pp != ' ' && *pp != '\t' && *pp != '\r'
 561                             && *pp != '\n')
 562                                 f = 0;
 563                         break;
 564                 }
 565                 f = 1;
 566         }
 567         ll = pp_end - pp;
 568
 569         /* If a path-name was not found at the first, try to check
 570          * a mtree format(a.k.a form D) ``NetBSD's mtree -D'' creates,
 571          * which places the path-name at the last. */
 572         if (f == 0) {
 573                 const char *pb = p + len - nl;
 574                 int name_len = 0;
 575                 int slash;
 576
 577                 /* The form D accepts only a single line for an entry. */
 578                 if (pb-2 >= p &&
 579                     pb[-1] == '\\' && (pb[-2] == ' ' || pb[-2] == '\t'))
 580                         return (-1);
 581                 if (pb-1 >= p && pb[-1] == '\\')
 582                         return (-1);
 583
 584                 slash = 0;
 585                 while (p <= --pb && *pb != ' ' && *pb != '\t') {
 586                         if (!safe_char[*(const unsigned char *)pb])
 587                                 return (-1);
 588                         name_len++;
 589                         /* The pathname should have a slash in this
 590                          * format. */
 591                         if (*pb == '/')
 592                                 slash = 1;
 593                 }
 594                 if (name_len == 0 || slash == 0)
 595                         return (-1);
 596                 /* If '/' is placed at the first in this field, this is not
 597                  * a valid filename. */
 598                 if (pb[1] == '/')
 599                         return (-1);
 600                 ll = len - nl - name_len;
 601                 pp = p;
 602                 *last_is_path = 1;
 603         }
 604
 605         return (bid_keyword_list(pp, ll, 0, *last_is_path));
 606 }
 607
 608 #define MAX_BID_ENTRY   3
 609
 610 static int
 611 mtree_bid(struct archive_read *a, int best_bid)
 612 {
 613         const char *signature = "#mtree";
 614         const char *p;
 615
 616         (void)best_bid; /* UNUSED */
 617
 618         /* Now let's look at the actual header and see if it matches. */
 619         p = __archive_read_ahead(a, strlen(signature), NULL);
 620         if (p == NULL)
 621                 return (-1);
 622
 623         if (memcmp(p, signature, strlen(signature)) == 0)
 624                 return (8 * (int)strlen(signature));
 625
 626         /*
 627          * There is not a mtree signature. Let's try to detect mtree format.
 628          */
 629         return (detect_form(a, NULL));
 630 }
 631
 632 static int
 633 detect_form(struct archive_read *a, int *is_form_d)
 634 {
 635         const char *p;
 636         ssize_t avail, ravail;
 637         ssize_t detected_bytes = 0, len, nl;
 638         int entry_cnt = 0, multiline = 0;
 639         int form_D = 0;/* The archive is generated by `NetBSD mtree -D'
 640                         * (In this source we call it `form D') . */
 641
 642         if (is_form_d != NULL)
 643                 *is_form_d = 0;
 644         p = __archive_read_ahead(a, 1, &avail);
 645         if (p == NULL)
 646                 return (-1);
 647         ravail = avail;
 648         for (;;) {
 649                 len = next_line(a, &p, &avail, &ravail, &nl);
 650                 /* The terminal character of the line should be
 651                  * a new line character, '\r\n' or '\n'. */
 652                 if (len <= 0 || nl == 0)
 653                         break;
 654                 if (!multiline) {
 655                         /* Leading whitespace is never significant,
 656                          * ignore it. */
 657                         while (len > 0 && (*p == ' ' || *p == '\t')) {
 658                                 ++p;
 659                                 --avail;
 660                                 --len;
 661                         }
 662                         /* Skip comment or empty line. */
 663                         if (p[0] == '#' || p[0] == '\n' || p[0] == '\r') {
 664                                 p += len;
 665                                 avail -= len;
 666                                 continue;
 667                         }
 668                 } else {
 669                         /* A continuance line; the terminal
 670                          * character of previous line was '\' character. */
 671                         if (bid_keyword_list(p, len, 0, 0) <= 0)
 672                                 break;
 673                         if (multiline == 1)
 674                                 detected_bytes += len;
 675                         if (p[len-nl-1] != '\\') {
 676                                 if (multiline == 1 &&
 677                                     ++entry_cnt >= MAX_BID_ENTRY)
 678                                         break;
 679                                 multiline = 0;
 680                         }
 681                         p += len;
 682                         avail -= len;
 683                         continue;
 684                 }
 685                 if (p[0] != '/') {
 686                         int last_is_path, keywords;
 687
 688                         keywords = bid_entry(p, len, nl, &last_is_path);
 689                         if (keywords >= 0) {
 690                                 detected_bytes += len;
 691                                 if (form_D == 0) {
 692                                         if (last_is_path)
 693                                                 form_D = 1;
 694                                         else if (keywords > 0)
 695                                                 /* This line is not `form D'. */
 696                                                 form_D = -1;
 697                                 } else if (form_D == 1) {
 698                                         if (!last_is_path && keywords > 0)
 699                                                 /* This this is not `form D'
 700                                                  * and We cannot accept mixed
 701                                                  * format. */
 702                                                 break;
 703                                 }
 704                                 if (!last_is_path && p[len-nl-1] == '\\')
 705                                         /* This line continues. */
 706                                         multiline = 1;
 707                                 else {
 708                                         /* We've got plenty of correct lines
 709                                          * to assume that this file is a mtree
 710                                          * format. */
 711                                         if (++entry_cnt >= MAX_BID_ENTRY)
 712                                                 break;
 713                                 }
 714                         } else
 715                                 break;
 716                 } else if (len > 4 && strncmp(p, "/set", 4) == 0) {
 717                         if (bid_keyword_list(p+4, len-4, 0, 0) <= 0)
 718                                 break;
 719                         /* This line continues. */
 720                         if (p[len-nl-1] == '\\')
 721                                 multiline = 2;
 722                 } else if (len > 6 && strncmp(p, "/unset", 6) == 0) {
 723                         if (bid_keyword_list(p+6, len-6, 1, 0) <= 0)
 724                                 break;
 725                         /* This line continues. */
 726                         if (p[len-nl-1] == '\\')
 727                                 multiline = 2;
 728                 } else
 729                         break;
 730
 731                 /* Test next line. */
 732                 p += len;
 733                 avail -= len;
 734         }
 735         if (entry_cnt >= MAX_BID_ENTRY || (entry_cnt > 0 && len == 0)) {
 736                 if (is_form_d != NULL) {
 737                         if (form_D == 1)
 738                                 *is_form_d = 1;
 739                 }
 740                 return (32);
 741         }
 742
 743         return (0);
 744 }
 745
 746 /*
 747  * The extended mtree format permits multiple lines specifying
 748  * attributes for each file.  For those entries, only the last line
 749  * is actually used.  Practically speaking, that means we have
 750  * to read the entire mtree file into memory up front.
 751  *
 752  * The parsing is done in two steps.  First, it is decided if a line
 753  * changes the global defaults and if it is, processed accordingly.
 754  * Otherwise, the options of the line are merged with the current
 755  * global options.
 756  */
 757 static int
 758 add_option(struct archive_read *a, struct mtree_option **global,
 759     const char *value, size_t len)
 760 {
 761         struct mtree_option *opt;
 762
 763         if ((opt = malloc(sizeof(*opt))) == NULL) {
 764                 archive_set_error(&a->archive, errno, "Can't allocate memory");
 765                 return (ARCHIVE_FATAL);
 766         }
 767         if ((opt->value = malloc(len + 1)) == NULL) {
 768                 free(opt);
 769                 archive_set_error(&a->archive, errno, "Can't allocate memory");
 770                 return (ARCHIVE_FATAL);
 771         }
 772         memcpy(opt->value, value, len);
 773         opt->value[len] = '\0';
 774         opt->next = *global;
 775         *global = opt;
 776         return (ARCHIVE_OK);
 777 }
 778
 779 static void
 780 remove_option(struct mtree_option **global, const char *value, size_t len)
 781 {
 782         struct mtree_option *iter, *last;
 783
 784         last = NULL;
 785         for (iter = *global; iter != NULL; last = iter, iter = iter->next) {
 786                 if (strncmp(iter->value, value, len) == 0 &&
 787                     (iter->value[len] == '\0' ||
 788                      iter->value[len] == '='))
 789                         break;
 790         }
 791         if (iter == NULL)
 792                 return;
 793         if (last == NULL)
 794                 *global = iter->next;
 795         else
 796                 last->next = iter->next;
 797
 798         free(iter->value);
 799         free(iter);
 800 }
 801
 802 static int
 803 process_global_set(struct archive_read *a,
 804     struct mtree_option **global, const char *line)
 805 {
 806         const char *next, *eq;
 807         size_t len;
 808         int r;
 809
 810         line += 4;
 811         for (;;) {
 812                 next = line + strspn(line, " \t\r\n");
 813                 if (*next == '\0')
 814                         return (ARCHIVE_OK);
 815                 line = next;
 816                 next = line + strcspn(line, " \t\r\n");
 817                 eq = strchr(line, '=');
 818                 if (eq > next)
 819                         len = next - line;
 820                 else
 821                         len = eq - line;
 822
 823                 remove_option(global, line, len);
 824                 r = add_option(a, global, line, next - line);
 825                 if (r != ARCHIVE_OK)
 826                         return (r);
 827                 line = next;
 828         }
 829 }
 830
 831 static int
 832 process_global_unset(struct archive_read *a,
 833     struct mtree_option **global, const char *line)
 834 {
 835         const char *next;
 836         size_t len;
 837
 838         line += 6;
 839         if (strchr(line, '=') != NULL) {
 840                 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
 841                     "/unset shall not contain `='");
 842                 return ARCHIVE_FATAL;
 843         }
 844
 845         for (;;) {
 846                 next = line + strspn(line, " \t\r\n");
 847                 if (*next == '\0')
 848                         return (ARCHIVE_OK);
 849                 line = next;
 850                 len = strcspn(line, " \t\r\n");
 851
 852                 if (len == 3 && strncmp(line, "all", 3) == 0) {
 853                         free_options(*global);
 854                         *global = NULL;
 855                 } else {
 856                         remove_option(global, line, len);
 857                 }
 858
 859                 line += len;
 860         }
 861 }
 862
 863 static int
 864 process_add_entry(struct archive_read *a, struct mtree *mtree,
 865     struct mtree_option **global, const char *line, ssize_t line_len,
 866     struct mtree_entry **last_entry, int is_form_d)
 867 {
 868         struct mtree_entry *entry, *ht_iter;
 869         struct mtree_option *iter;
 870         const char *next, *eq, *name, *end;
 871         size_t name_len, len;
 872         int r, i;
 873         unsigned int ht_idx;
 874
 875         if ((entry = malloc(sizeof(*entry))) == NULL) {
 876                 archive_set_error(&a->archive, errno, "Can't allocate memory");
 877                 return (ARCHIVE_FATAL);
 878         }
 879         entry->next = NULL;
 880         entry->options = NULL;
 881         entry->name = NULL;
 882         entry->used = 0;
 883         entry->full = 0;
 884         entry->name_hash = 0;
 885         entry->hashtable_next = NULL;
 886
 887         /* Add this entry to list. */
 888         if (*last_entry == NULL)
 889                 mtree->entries = entry;
 890         else
 891                 (*last_entry)->next = entry;
 892         *last_entry = entry;
 893
 894         if (is_form_d) {
 895                 /* Filename is last item on line. */
 896                 /* Adjust line_len to trim trailing whitespace */
 897                 while (line_len > 0) {
 898                         char last_character = line[line_len - 1];
 899                         if (last_character == '\r'
 900                             || last_character == '\n'
 901                             || last_character == '\t'
 902                             || last_character == ' ') {
 903                                 line_len--;
 904                         } else {
 905                                 break;
 906                         }
 907                 }
 908                 /* Name starts after the last whitespace separator */
 909                 name = line;
 910                 for (i = 0; i < line_len; i++) {
 911                         if (line[i] == '\r'
 912                             || line[i] == '\n'
 913                             || line[i] == '\t'
 914                             || line[i] == ' ') {
 915                                 name = line + i + 1;
 916                         }
 917                 }
 918                 name_len = line + line_len - name;
 919                 end = name;
 920         } else {
 921                 /* Filename is first item on line */
 922                 name_len = strcspn(line, " \t\r\n");
 923                 name = line;
 924                 line += name_len;
 925                 end = line + line_len;
 926         }
 927         /* name/name_len is the name within the line. */
 928         /* line..end brackets the entire line except the name */
 929
 930         if ((entry->name = malloc(name_len + 1)) == NULL) {
 931                 archive_set_error(&a->archive, errno, "Can't allocate memory");
 932                 return (ARCHIVE_FATAL);
 933         }
 934
 935         memcpy(entry->name, name, name_len);
 936         entry->name[name_len] = '\0';
 937         parse_escapes(entry->name, entry);
 938         entry->name_hash = hash(entry->name);
 939
 940         ht_idx = entry->name_hash % MTREE_HASHTABLE_SIZE;
 941         if ((ht_iter = mtree->entry_hashtable[ht_idx]) != NULL) {
 942                 while (ht_iter->hashtable_next)
 943                         ht_iter = ht_iter->hashtable_next;
 944                 ht_iter->hashtable_next = entry;
 945         } else {
 946                 mtree->entry_hashtable[ht_idx] = entry;
 947         }
 948
 949         for (iter = *global; iter != NULL; iter = iter->next) {
 950                 r = add_option(a, &entry->options, iter->value,
 951                     strlen(iter->value));
 952                 if (r != ARCHIVE_OK)
 953                         return (r);
 954         }
 955
 956         for (;;) {
 957                 next = line + strspn(line, " \t\r\n");
 958                 if (*next == '\0')
 959                         return (ARCHIVE_OK);
 960                 if (next >= end)
 961                         return (ARCHIVE_OK);
 962                 line = next;
 963                 next = line + strcspn(line, " \t\r\n");
 964                 eq = strchr(line, '=');
 965                 if (eq == NULL || eq > next)
 966                         len = next - line;
 967                 else
 968                         len = eq - line;
 969
 970                 remove_option(&entry->options, line, len);
 971                 r = add_option(a, &entry->options, line, next - line);
 972                 if (r != ARCHIVE_OK)
 973                         return (r);
 974                 line = next;
 975         }
 976 }
 977
 978 static int
 979 read_mtree(struct archive_read *a, struct mtree *mtree)
 980 {
 981         ssize_t len;
 982         uintmax_t counter;
 983         char *p;
 984         struct mtree_option *global;
 985         struct mtree_entry *last_entry;
 986         int r, is_form_d;
 987
 988         mtree->archive_format = ARCHIVE_FORMAT_MTREE;
 989         mtree->archive_format_name = "mtree";
 990
 991         global = NULL;
 992         last_entry = NULL;
 993
 994         (void)detect_form(a, &is_form_d);
 995
 996         for (counter = 1; ; ++counter) {
 997                 len = readline(a, mtree, &p, 65536);
 998                 if (len == 0) {
 999                         mtree->this_entry = mtree->entries;
1000                         free_options(global);
1001                         return (ARCHIVE_OK);
1002                 }
1003                 if (len < 0) {
1004                         free_options(global);
1005                         return ((int)len);
1006                 }
1007                 /* Leading whitespace is never significant, ignore it. */
1008                 while (*p == ' ' || *p == '\t') {
1009                         ++p;
1010                         --len;
1011                 }
1012                 /* Skip content lines and blank lines. */
1013                 if (*p == '#')
1014                         continue;
1015                 if (*p == '\r' || *p == '\n' || *p == '\0')
1016                         continue;
1017                 if (*p != '/') {
1018                         r = process_add_entry(a, mtree, &global, p, len,
1019                             &last_entry, is_form_d);
1020                 } else if (len > 4 && strncmp(p, "/set", 4) == 0) {
1021                         if (p[4] != ' ' && p[4] != '\t')
1022                                 break;
1023                         r = process_global_set(a, &global, p);
1024                 } else if (len > 6 && strncmp(p, "/unset", 6) == 0) {
1025                         if (p[6] != ' ' && p[6] != '\t')
1026                                 break;
1027                         r = process_global_unset(a, &global, p);
1028                 } else
1029                         break;
1030
1031                 if (r != ARCHIVE_OK) {
1032                         free_options(global);
1033                         return r;
1034                 }
1035         }
1036
1037         archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1038             "Can't parse line %ju", counter);
1039         free_options(global);
1040         return (ARCHIVE_FATAL);
1041 }
1042
1043 /*
1044  * Read in the entire mtree file into memory on the first request.
1045  * Then use the next unused file to satisfy each header request.
1046  */
1047 static int
1048 read_header(struct archive_read *a, struct archive_entry *entry)
1049 {
1050         struct mtree *mtree;
1051         char *p;
1052         int r, use_next;
1053
1054         mtree = (struct mtree *)(a->format->data);
1055
1056         if (mtree->fd >= 0) {
1057                 close(mtree->fd);
1058                 mtree->fd = -1;
1059         }
1060
1061         if (mtree->entries == NULL) {
1062                 mtree->resolver = archive_entry_linkresolver_new();
1063                 if (mtree->resolver == NULL)
1064                         return ARCHIVE_FATAL;
1065                 archive_entry_linkresolver_set_strategy(mtree->resolver,
1066                     ARCHIVE_FORMAT_MTREE);
1067                 r = read_mtree(a, mtree);
1068                 if (r != ARCHIVE_OK)
1069                         return (r);
1070         }
1071
1072         a->archive.archive_format = mtree->archive_format;
1073         a->archive.archive_format_name = mtree->archive_format_name;
1074
1075         for (;;) {
1076                 if (mtree->this_entry == NULL)
1077                         return (ARCHIVE_EOF);
1078                 if (strcmp(mtree->this_entry->name, "..") == 0) {
1079                         mtree->this_entry->used = 1;
1080                         if (archive_strlen(&mtree->current_dir) > 0) {
1081                                 /* Roll back current path. */
1082                                 p = mtree->current_dir.s
1083                                     + mtree->current_dir.length - 1;
1084                                 while (p >= mtree->current_dir.s && *p != '/')
1085                                         --p;
1086                                 if (p >= mtree->current_dir.s)
1087                                         --p;
1088                                 mtree->current_dir.length
1089                                     = p - mtree->current_dir.s + 1;
1090                         }
1091                 }
1092                 if (!mtree->this_entry->used) {
1093                         use_next = 0;
1094                         r = parse_file(a, entry, mtree, mtree->this_entry,
1095                                 &use_next);
1096                         if (use_next == 0)
1097                                 return (r);
1098                 }
1099                 mtree->this_entry = mtree->this_entry->next;
1100         }
1101 }
1102
1103 /*
1104  * A single file can have multiple lines contribute specifications.
1105  * Parse as many lines as necessary, then pull additional information
1106  * from a backing file on disk as necessary.
1107  */
1108 static int
1109 parse_file(struct archive_read *a, struct archive_entry *entry,
1110     struct mtree *mtree, struct mtree_entry *mentry, int *use_next)
1111 {
1112         const char *path;
1113         struct stat st_storage, *st;
1114         struct mtree_entry *mp;
1115         struct archive_entry *sparse_entry;
1116         int r = ARCHIVE_OK, r1, parsed_kws;
1117
1118         mentry->used = 1;
1119
1120         /* Initialize reasonable defaults. */
1121         archive_entry_set_filetype(entry, AE_IFREG);
1122         archive_entry_set_size(entry, 0);
1123         archive_string_empty(&mtree->contents_name);
1124
1125         /* Parse options from this line. */
1126         parsed_kws = 0;
1127         r = parse_line(a, entry, mtree, mentry, &parsed_kws);
1128
1129         if (mentry->full) {
1130                 archive_entry_copy_pathname(entry, mentry->name);
1131                 /*
1132                  * "Full" entries are allowed to have multiple lines
1133                  * and those lines aren't required to be adjacent.  We
1134                  * don't support multiple lines for "relative" entries
1135                  * nor do we make any attempt to merge data from
1136                  * separate "relative" and "full" entries.  (Merging
1137                  * "relative" and "full" entries would require dealing
1138                  * with pathname canonicalization, which is a very
1139                  * tricky subject.)
1140                  */
1141                 for (mp = mentry->hashtable_next; mp != NULL; mp = mp->hashtable_next) {
1142                         if (mp->full && !mp->used
1143                                         && mentry->name_hash == mp->name_hash
1144                                         && strcmp(mentry->name, mp->name) == 0) {
1145                                 /* Later lines override earlier ones. */
1146                                 mp->used = 1;
1147                                 r1 = parse_line(a, entry, mtree, mp,
1148                                     &parsed_kws);
1149                                 if (r1 < r)
1150                                         r = r1;
1151                         }
1152                 }
1153         } else {
1154                 /*
1155                  * Relative entries require us to construct
1156                  * the full path and possibly update the
1157                  * current directory.
1158                  */
1159                 size_t n = archive_strlen(&mtree->current_dir);
1160                 if (n > 0)
1161                         archive_strcat(&mtree->current_dir, "/");
1162                 archive_strcat(&mtree->current_dir, mentry->name);
1163                 archive_entry_copy_pathname(entry, mtree->current_dir.s);
1164                 if (archive_entry_filetype(entry) != AE_IFDIR)
1165                         mtree->current_dir.length = n;
1166         }
1167
1168         if (mtree->checkfs) {
1169                 /*
1170                  * Try to open and stat the file to get the real size
1171                  * and other file info.  It would be nice to avoid
1172                  * this here so that getting a listing of an mtree
1173                  * wouldn't require opening every referenced contents
1174                  * file.  But then we wouldn't know the actual
1175                  * contents size, so I don't see a really viable way
1176                  * around this.  (Also, we may want to someday pull
1177                  * other unspecified info from the contents file on
1178                  * disk.)
1179                  */
1180                 mtree->fd = -1;
1181                 if (archive_strlen(&mtree->contents_name) > 0)
1182                         path = mtree->contents_name.s;
1183                 else
1184                         path = archive_entry_pathname(entry);
1185
1186                 if (archive_entry_filetype(entry) == AE_IFREG ||
1187                                 archive_entry_filetype(entry) == AE_IFDIR) {
1188                         mtree->fd = open(path, O_RDONLY | O_BINARY | O_CLOEXEC);
1189                         __archive_ensure_cloexec_flag(mtree->fd);
1190                         if (mtree->fd == -1 &&
1191                                 (errno != ENOENT ||
1192                                  archive_strlen(&mtree->contents_name) > 0)) {
1193                                 archive_set_error(&a->archive, errno,
1194                                                 "Can't open %s", path);
1195                                 r = ARCHIVE_WARN;
1196                         }
1197                 }
1198
1199                 st = &st_storage;
1200                 if (mtree->fd >= 0) {
1201                         if (fstat(mtree->fd, st) == -1) {
1202                                 archive_set_error(&a->archive, errno,
1203                                                 "Could not fstat %s", path);
1204                                 r = ARCHIVE_WARN;
1205                                 /* If we can't stat it, don't keep it open. */
1206                                 close(mtree->fd);
1207                                 mtree->fd = -1;
1208                                 st = NULL;
1209                         }
1210                 } else if (lstat(path, st) == -1) {
1211                         st = NULL;
1212                 }
1213
1214                 /*
1215                  * Check for a mismatch between the type in the specification
1216                  * and the type of the contents object on disk.
1217                  */
1218                 if (st != NULL) {
1219                         if (((st->st_mode & S_IFMT) == S_IFREG &&
1220                               archive_entry_filetype(entry) == AE_IFREG)
1221 #ifdef S_IFLNK
1222                           ||((st->st_mode & S_IFMT) == S_IFLNK &&
1223                               archive_entry_filetype(entry) == AE_IFLNK)
1224 #endif
1225 #ifdef S_IFSOCK
1226                           ||((st->st_mode & S_IFSOCK) == S_IFSOCK &&
1227                               archive_entry_filetype(entry) == AE_IFSOCK)
1228 #endif
1229 #ifdef S_IFCHR
1230                           ||((st->st_mode & S_IFMT) == S_IFCHR &&
1231                               archive_entry_filetype(entry) == AE_IFCHR)
1232 #endif
1233 #ifdef S_IFBLK
1234                           ||((st->st_mode & S_IFMT) == S_IFBLK &&
1235                               archive_entry_filetype(entry) == AE_IFBLK)
1236 #endif
1237                           ||((st->st_mode & S_IFMT) == S_IFDIR &&
1238                               archive_entry_filetype(entry) == AE_IFDIR)
1239 #ifdef S_IFIFO
1240                           ||((st->st_mode & S_IFMT) == S_IFIFO &&
1241                               archive_entry_filetype(entry) == AE_IFIFO)
1242 #endif
1243                         ) {
1244                                 /* Types match. */
1245                         } else {
1246                                 /* Types don't match; bail out gracefully. */
1247                                 if (mtree->fd >= 0)
1248                                         close(mtree->fd);
1249                                 mtree->fd = -1;
1250                                 if (parsed_kws & MTREE_HAS_OPTIONAL) {
1251                                         /* It's not an error for an optional
1252                                          * entry to not match disk. */
1253                                         *use_next = 1;
1254                                 } else if (r == ARCHIVE_OK) {
1255                                         archive_set_error(&a->archive,
1256                                             ARCHIVE_ERRNO_MISC,
1257                                             "mtree specification has different"
1258                                             " type for %s",
1259                                             archive_entry_pathname(entry));
1260                                         r = ARCHIVE_WARN;
1261                                 }
1262                                 return (r);
1263                         }
1264                 }
1265
1266                 /*
1267                  * If there is a contents file on disk, pick some of the
1268                  * metadata from that file.  For most of these, we only
1269                  * set it from the contents if it wasn't already parsed
1270                  * from the specification.
1271                  */
1272                 if (st != NULL) {
1273                         if (((parsed_kws & MTREE_HAS_DEVICE) == 0 ||
1274                                 (parsed_kws & MTREE_HAS_NOCHANGE) != 0) &&
1275                                 (archive_entry_filetype(entry) == AE_IFCHR ||
1276                                  archive_entry_filetype(entry) == AE_IFBLK))
1277                                 archive_entry_set_rdev(entry, st->st_rdev);
1278                         if ((parsed_kws & (MTREE_HAS_GID | MTREE_HAS_GNAME))
1279                                 == 0 ||
1280                             (parsed_kws & MTREE_HAS_NOCHANGE) != 0)
1281                                 archive_entry_set_gid(entry, st->st_gid);
1282                         if ((parsed_kws & (MTREE_HAS_UID | MTREE_HAS_UNAME))
1283                                 == 0 ||
1284                             (parsed_kws & MTREE_HAS_NOCHANGE) != 0)
1285                                 archive_entry_set_uid(entry, st->st_uid);
1286                         if ((parsed_kws & MTREE_HAS_MTIME) == 0 ||
1287                             (parsed_kws & MTREE_HAS_NOCHANGE) != 0) {
1288 #if HAVE_STRUCT_STAT_ST_MTIMESPEC_TV_NSEC
1289                                 archive_entry_set_mtime(entry, st->st_mtime,
1290                                                 st->st_mtimespec.tv_nsec);
1291 #elif HAVE_STRUCT_STAT_ST_MTIM_TV_NSEC
1292                                 archive_entry_set_mtime(entry, st->st_mtime,
1293                                                 st->st_mtim.tv_nsec);
1294 #elif HAVE_STRUCT_STAT_ST_MTIME_N
1295                                 archive_entry_set_mtime(entry, st->st_mtime,
1296                                                 st->st_mtime_n);
1297 #elif HAVE_STRUCT_STAT_ST_UMTIME
1298                                 archive_entry_set_mtime(entry, st->st_mtime,
1299                                                 st->st_umtime*1000);
1300 #elif HAVE_STRUCT_STAT_ST_MTIME_USEC
1301                                 archive_entry_set_mtime(entry, st->st_mtime,
1302                                                 st->st_mtime_usec*1000);
1303 #else
1304                                 archive_entry_set_mtime(entry, st->st_mtime, 0);
1305 #endif
1306                         }
1307                         if ((parsed_kws & MTREE_HAS_NLINK) == 0 ||
1308                             (parsed_kws & MTREE_HAS_NOCHANGE) != 0)
1309                                 archive_entry_set_nlink(entry, st->st_nlink);
1310                         if ((parsed_kws & MTREE_HAS_PERM) == 0 ||
1311                             (parsed_kws & MTREE_HAS_NOCHANGE) != 0)
1312                                 archive_entry_set_perm(entry, st->st_mode);
1313                         if ((parsed_kws & MTREE_HAS_SIZE) == 0 ||
1314                             (parsed_kws & MTREE_HAS_NOCHANGE) != 0)
1315                                 archive_entry_set_size(entry, st->st_size);
1316                         archive_entry_set_ino(entry, st->st_ino);
1317                         archive_entry_set_dev(entry, st->st_dev);
1318
1319                         archive_entry_linkify(mtree->resolver, &entry,
1320                                 &sparse_entry);
1321                 } else if (parsed_kws & MTREE_HAS_OPTIONAL) {
1322                         /*
1323                          * Couldn't open the entry, stat it or the on-disk type
1324                          * didn't match.  If this entry is optional, just
1325                          * ignore it and read the next header entry.
1326                          */
1327                         *use_next = 1;
1328                         return ARCHIVE_OK;
1329                 }
1330         }
1331
1332         mtree->cur_size = archive_entry_size(entry);
1333         mtree->offset = 0;
1334
1335         return r;
1336 }
1337
1338 /*
1339  * Each line contains a sequence of keywords.
1340  */
1341 static int
1342 parse_line(struct archive_read *a, struct archive_entry *entry,
1343     struct mtree *mtree, struct mtree_entry *mp, int *parsed_kws)
1344 {
1345         struct mtree_option *iter;
1346         int r = ARCHIVE_OK, r1;
1347
1348         for (iter = mp->options; iter != NULL; iter = iter->next) {
1349                 r1 = parse_keyword(a, mtree, entry, iter, parsed_kws);
1350                 if (r1 < r)
1351                         r = r1;
1352         }
1353         if (r == ARCHIVE_OK && (*parsed_kws & MTREE_HAS_TYPE) == 0) {
1354                 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1355                     "Missing type keyword in mtree specification");
1356                 return (ARCHIVE_WARN);
1357         }
1358         return (r);
1359 }
1360
1361 /*
1362  * Device entries have one of the following forms:
1363  *  - raw dev_t
1364  *  - format,major,minor[,subdevice]
1365  * When parsing succeeded, `pdev' will contain the appropriate dev_t value.
1366  */
1367
1368 /* strsep() is not in C90, but strcspn() is. */
1369 /* Taken from http://unixpapa.com/incnote/string.html */
1370 static char *
1371 la_strsep(char **sp, const char *sep)
1372 {
1373         char *p, *s;
1374         if (sp == NULL || *sp == NULL || **sp == '\0')
1375                 return(NULL);
1376         s = *sp;
1377         p = s + strcspn(s, sep);
1378         if (*p != '\0')
1379                 *p++ = '\0';
1380         *sp = p;
1381         return(s);
1382 }
1383
1384 static int
1385 parse_device(dev_t *pdev, struct archive *a, char *val)
1386 {
1387 #define MAX_PACK_ARGS 3
1388         unsigned long numbers[MAX_PACK_ARGS];
1389         char *p, *dev;
1390         int argc;
1391         pack_t *pack;
1392         dev_t result;
1393         const char *error = NULL;
1394
1395         memset(pdev, 0, sizeof(*pdev));
1396         if ((dev = strchr(val, ',')) != NULL) {
1397                 /*
1398                  * Device's major/minor are given in a specified format.
1399                  * Decode and pack it accordingly.
1400                  */
1401                 *dev++ = '\0';
1402                 if ((pack = pack_find(val)) == NULL) {
1403                         archive_set_error(a, ARCHIVE_ERRNO_FILE_FORMAT,
1404                             "Unknown format `%s'", val);
1405                         return ARCHIVE_WARN;
1406                 }
1407                 argc = 0;
1408                 while ((p = la_strsep(&dev, ",")) != NULL) {
1409                         if (*p == '\0') {
1410                                 archive_set_error(a, ARCHIVE_ERRNO_FILE_FORMAT,
1411                                     "Missing number");
1412                                 return ARCHIVE_WARN;
1413                         }
1414                         if (argc >= MAX_PACK_ARGS) {
1415                                 archive_set_error(a, ARCHIVE_ERRNO_FILE_FORMAT,
1416                                     "Too many arguments");
1417                                 return ARCHIVE_WARN;
1418                         }
1419                         numbers[argc++] = (unsigned long)mtree_atol(&p, 0);
1420                 }
1421                 if (argc < 2) {
1422                         archive_set_error(a, ARCHIVE_ERRNO_FILE_FORMAT,
1423                             "Not enough arguments");
1424                         return ARCHIVE_WARN;
1425                 }
1426                 result = (*pack)(argc, numbers, &error);
1427                 if (error != NULL) {
1428                         archive_set_error(a, ARCHIVE_ERRNO_FILE_FORMAT,
1429                             "%s", error);
1430                         return ARCHIVE_WARN;
1431                 }
1432         } else {
1433                 /* file system raw value. */
1434                 result = (dev_t)mtree_atol(&val, 0);
1435         }
1436         *pdev = result;
1437         return ARCHIVE_OK;
1438 #undef MAX_PACK_ARGS
1439 }
1440
1441 /*
1442  * Parse a single keyword and its value.
1443  */
1444 static int
1445 parse_keyword(struct archive_read *a, struct mtree *mtree,
1446     struct archive_entry *entry, struct mtree_option *opt, int *parsed_kws)
1447 {
1448         char *val, *key;
1449
1450         key = opt->value;
1451
1452         if (*key == '\0')
1453                 return (ARCHIVE_OK);
1454
1455         if (strcmp(key, "nochange") == 0) {
1456                 *parsed_kws |= MTREE_HAS_NOCHANGE;
1457                 return (ARCHIVE_OK);
1458         }
1459         if (strcmp(key, "optional") == 0) {
1460                 *parsed_kws |= MTREE_HAS_OPTIONAL;
1461                 return (ARCHIVE_OK);
1462         }
1463         if (strcmp(key, "ignore") == 0) {
1464                 /*
1465                  * The mtree processing is not recursive, so
1466                  * recursion will only happen for explicitly listed
1467                  * entries.
1468                  */
1469                 return (ARCHIVE_OK);
1470         }
1471
1472         val = strchr(key, '=');
1473         if (val == NULL) {
1474                 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1475                     "Malformed attribute \"%s\" (%d)", key, key[0]);
1476                 return (ARCHIVE_WARN);
1477         }
1478
1479         *val = '\0';
1480         ++val;
1481
1482         switch (key[0]) {
1483         case 'c':
1484                 if (strcmp(key, "content") == 0
1485                     || strcmp(key, "contents") == 0) {
1486                         parse_escapes(val, NULL);
1487                         archive_strcpy(&mtree->contents_name, val);
1488                         break;
1489                 }
1490                 if (strcmp(key, "cksum") == 0)
1491                         break;
1492         case 'd':
1493                 if (strcmp(key, "device") == 0) {
1494                         /* stat(2) st_rdev field, e.g. the major/minor IDs
1495                          * of a char/block special file */
1496                         int r;
1497                         dev_t dev;
1498
1499                         *parsed_kws |= MTREE_HAS_DEVICE;
1500                         r = parse_device(&dev, &a->archive, val);
1501                         if (r == ARCHIVE_OK)
1502                                 archive_entry_set_rdev(entry, dev);
1503                         return r;
1504                 }
1505         case 'f':
1506                 if (strcmp(key, "flags") == 0) {
1507                         *parsed_kws |= MTREE_HAS_FFLAGS;
1508                         archive_entry_copy_fflags_text(entry, val);
1509                         break;
1510                 }
1511         case 'g':
1512                 if (strcmp(key, "gid") == 0) {
1513                         *parsed_kws |= MTREE_HAS_GID;
1514                         archive_entry_set_gid(entry, mtree_atol(&val, 10));
1515                         break;
1516                 }
1517                 if (strcmp(key, "gname") == 0) {
1518                         *parsed_kws |= MTREE_HAS_GNAME;
1519                         archive_entry_copy_gname(entry, val);
1520                         break;
1521                 }
1522         case 'i':
1523                 if (strcmp(key, "inode") == 0) {
1524                         archive_entry_set_ino(entry, mtree_atol(&val, 10));
1525                         break;
1526                 }
1527         case 'l':
1528                 if (strcmp(key, "link") == 0) {
1529                         archive_entry_copy_symlink(entry, val);
1530                         break;
1531                 }
1532         case 'm':
1533                 if (strcmp(key, "md5") == 0 || strcmp(key, "md5digest") == 0)
1534                         break;
1535                 if (strcmp(key, "mode") == 0) {
1536                         if (val[0] >= '0' && val[0] <= '7') {
1537                                 *parsed_kws |= MTREE_HAS_PERM;
1538                                 archive_entry_set_perm(entry,
1539                                     (mode_t)mtree_atol(&val, 8));
1540                         } else {
1541                                 archive_set_error(&a->archive,
1542                                     ARCHIVE_ERRNO_FILE_FORMAT,
1543                                     "Symbolic or non-octal mode \"%s\" unsupported", val);
1544                                 return ARCHIVE_WARN;
1545                         }
1546                         break;
1547                 }
1548         case 'n':
1549                 if (strcmp(key, "nlink") == 0) {
1550                         *parsed_kws |= MTREE_HAS_NLINK;
1551                         archive_entry_set_nlink(entry,
1552                                 (unsigned int)mtree_atol(&val, 10));
1553                         break;
1554                 }
1555         case 'r':
1556                 if (strcmp(key, "resdevice") == 0) {
1557                         /* stat(2) st_dev field, e.g. the device ID where the
1558                          * inode resides */
1559                         int r;
1560                         dev_t dev;
1561
1562                         r = parse_device(&dev, &a->archive, val);
1563                         if (r == ARCHIVE_OK)
1564                                 archive_entry_set_dev(entry, dev);
1565                         return r;
1566                 }
1567                 if (strcmp(key, "rmd160") == 0 ||
1568                     strcmp(key, "rmd160digest") == 0)
1569                         break;
1570         case 's':
1571                 if (strcmp(key, "sha1") == 0 || strcmp(key, "sha1digest") == 0)
1572                         break;
1573                 if (strcmp(key, "sha256") == 0 ||
1574                     strcmp(key, "sha256digest") == 0)
1575                         break;
1576                 if (strcmp(key, "sha384") == 0 ||
1577                     strcmp(key, "sha384digest") == 0)
1578                         break;
1579                 if (strcmp(key, "sha512") == 0 ||
1580                     strcmp(key, "sha512digest") == 0)
1581                         break;
1582                 if (strcmp(key, "size") == 0) {
1583                         archive_entry_set_size(entry, mtree_atol(&val, 10));
1584                         break;
1585                 }
1586         case 't':
1587                 if (strcmp(key, "tags") == 0) {
1588                         /*
1589                          * Comma delimited list of tags.
1590                          * Ignore the tags for now, but the interface
1591                          * should be extended to allow inclusion/exclusion.
1592                          */
1593                         break;
1594                 }
1595                 if (strcmp(key, "time") == 0) {
1596                         int64_t m;
1597                         int64_t my_time_t_max = get_time_t_max();
1598                         int64_t my_time_t_min = get_time_t_min();
1599                         long ns = 0;
1600
1601                         *parsed_kws |= MTREE_HAS_MTIME;
1602                         m = mtree_atol(&val, 10);
1603                         /* Replicate an old mtree bug:
1604                          * 123456789.1 represents 123456789
1605                          * seconds and 1 nanosecond. */
1606                         if (*val == '.') {
1607                                 ++val;
1608                                 ns = (long)mtree_atol(&val, 10);
1609                                 if (ns < 0)
1610                                         ns = 0;
1611                                 else if (ns > 999999999)
1612                                         ns = 999999999;
1613                         }
1614                         if (m > my_time_t_max)
1615                                 m = my_time_t_max;
1616                         else if (m < my_time_t_min)
1617                                 m = my_time_t_min;
1618                         archive_entry_set_mtime(entry, (time_t)m, ns);
1619                         break;
1620                 }
1621                 if (strcmp(key, "type") == 0) {
1622                         switch (val[0]) {
1623                         case 'b':
1624                                 if (strcmp(val, "block") == 0) {
1625                                         archive_entry_set_filetype(entry, AE_IFBLK);
1626                                         break;
1627                                 }
1628                         case 'c':
1629                                 if (strcmp(val, "char") == 0) {
1630                                         archive_entry_set_filetype(entry,
1631                                                 AE_IFCHR);
1632                                         break;
1633                                 }
1634                         case 'd':
1635                                 if (strcmp(val, "dir") == 0) {
1636                                         archive_entry_set_filetype(entry,
1637                                                 AE_IFDIR);
1638                                         break;
1639                                 }
1640                         case 'f':
1641                                 if (strcmp(val, "fifo") == 0) {
1642                                         archive_entry_set_filetype(entry,
1643                                                 AE_IFIFO);
1644                                         break;
1645                                 }
1646                                 if (strcmp(val, "file") == 0) {
1647                                         archive_entry_set_filetype(entry,
1648                                                 AE_IFREG);
1649                                         break;
1650                                 }
1651                         case 'l':
1652                                 if (strcmp(val, "link") == 0) {
1653                                         archive_entry_set_filetype(entry,
1654                                                 AE_IFLNK);
1655                                         break;
1656                                 }
1657                         default:
1658                                 archive_set_error(&a->archive,
1659                                     ARCHIVE_ERRNO_FILE_FORMAT,
1660                                     "Unrecognized file type \"%s\"; "
1661                                     "assuming \"file\"", val);
1662                                 archive_entry_set_filetype(entry, AE_IFREG);
1663                                 return (ARCHIVE_WARN);
1664                         }
1665                         *parsed_kws |= MTREE_HAS_TYPE;
1666                         break;
1667                 }
1668         case 'u':
1669                 if (strcmp(key, "uid") == 0) {
1670                         *parsed_kws |= MTREE_HAS_UID;
1671                         archive_entry_set_uid(entry, mtree_atol(&val, 10));
1672                         break;
1673                 }
1674                 if (strcmp(key, "uname") == 0) {
1675                         *parsed_kws |= MTREE_HAS_UNAME;
1676                         archive_entry_copy_uname(entry, val);
1677                         break;
1678                 }
1679         default:
1680                 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1681                     "Unrecognized key %s=%s", key, val);
1682                 return (ARCHIVE_WARN);
1683         }
1684         return (ARCHIVE_OK);
1685 }
1686
1687 static int
1688 read_data(struct archive_read *a, const void **buff, size_t *size,
1689     int64_t *offset)
1690 {
1691         size_t bytes_to_read;
1692         ssize_t bytes_read;
1693         struct mtree *mtree;
1694
1695         mtree = (struct mtree *)(a->format->data);
1696         if (mtree->fd < 0) {
1697                 *buff = NULL;
1698                 *offset = 0;
1699                 *size = 0;
1700                 return (ARCHIVE_EOF);
1701         }
1702         if (mtree->buff == NULL) {
1703                 mtree->buffsize = 64 * 1024;
1704                 mtree->buff = malloc(mtree->buffsize);
1705                 if (mtree->buff == NULL) {
1706                         archive_set_error(&a->archive, ENOMEM,
1707                             "Can't allocate memory");
1708                         return (ARCHIVE_FATAL);
1709                 }
1710         }
1711
1712         *buff = mtree->buff;
1713         *offset = mtree->offset;
1714         if ((int64_t)mtree->buffsize > mtree->cur_size - mtree->offset)
1715                 bytes_to_read = (size_t)(mtree->cur_size - mtree->offset);
1716         else
1717                 bytes_to_read = mtree->buffsize;
1718         bytes_read = read(mtree->fd, mtree->buff, bytes_to_read);
1719         if (bytes_read < 0) {
1720                 archive_set_error(&a->archive, errno, "Can't read");
1721                 return (ARCHIVE_WARN);
1722         }
1723         if (bytes_read == 0) {
1724                 *size = 0;
1725                 return (ARCHIVE_EOF);
1726         }
1727         mtree->offset += bytes_read;
1728         *size = bytes_read;
1729         return (ARCHIVE_OK);
1730 }
1731
1732 /* Skip does nothing except possibly close the contents file. */
1733 static int
1734 skip(struct archive_read *a)
1735 {
1736         struct mtree *mtree;
1737
1738         mtree = (struct mtree *)(a->format->data);
1739         if (mtree->fd >= 0) {
1740                 close(mtree->fd);
1741                 mtree->fd = -1;
1742         }
1743         return (ARCHIVE_OK);
1744 }
1745
1746 /*
1747  * Since parsing backslash sequences always makes strings shorter,
1748  * we can always do this conversion in-place.
1749  */
1750 static void
1751 parse_escapes(char *src, struct mtree_entry *mentry)
1752 {
1753         char *dest = src;
1754         char c;
1755
1756         if (mentry != NULL && strcmp(src, ".") == 0)
1757                 mentry->full = 1;
1758
1759         while (*src != '\0') {
1760                 c = *src++;
1761                 if (c == '/' && mentry != NULL)
1762                         mentry->full = 1;
1763                 if (c == '\\') {
1764                         switch (src[0]) {
1765                         case '0':
1766                                 if (src[1] < '0' || src[1] > '7') {
1767                                         c = 0;
1768                                         ++src;
1769                                         break;
1770                                 }
1771                                 /* FALLTHROUGH */
1772                         case '1':
1773                         case '2':
1774                         case '3':
1775                                 if (src[1] >= '0' && src[1] <= '7' &&
1776                                     src[2] >= '0' && src[2] <= '7') {
1777                                         c = (src[0] - '0') << 6;
1778                                         c |= (src[1] - '0') << 3;
1779                                         c |= (src[2] - '0');
1780                                         src += 3;
1781                                 }
1782                                 break;
1783                         case 'a':
1784                                 c = '\a';
1785                                 ++src;
1786                                 break;
1787                         case 'b':
1788                                 c = '\b';
1789                                 ++src;
1790                                 break;
1791                         case 'f':
1792                                 c = '\f';
1793                                 ++src;
1794                                 break;
1795                         case 'n':
1796                                 c = '\n';
1797                                 ++src;
1798                                 break;
1799                         case 'r':
1800                                 c = '\r';
1801                                 ++src;
1802                                 break;
1803                         case 's':
1804                                 c = ' ';
1805                                 ++src;
1806                                 break;
1807                         case 't':
1808                                 c = '\t';
1809                                 ++src;
1810                                 break;
1811                         case 'v':
1812                                 c = '\v';
1813                                 ++src;
1814                                 break;
1815                         case '\\':
1816                                 c = '\\';
1817                                 ++src;
1818                                 break;
1819                         }
1820                 }
1821                 *dest++ = c;
1822         }
1823         *dest = '\0';
1824 }
1825
1826 /* Parse a hex digit. */
1827 static int
1828 parsedigit(char c)
1829 {
1830         if (c >= '0' && c <= '9')
1831                 return c - '0';
1832         else if (c >= 'a' && c <= 'f')
1833                 return c - 'a';
1834         else if (c >= 'A' && c <= 'F')
1835                 return c - 'A';
1836         else
1837                 return -1;
1838 }
1839
1840 /*
1841  * Note that this implementation does not (and should not!) obey
1842  * locale settings; you cannot simply substitute strtol here, since
1843  * it does obey locale.
1844  */
1845 static int64_t
1846 mtree_atol(char **p, int base)
1847 {
1848         int64_t l, limit;
1849         int digit, last_digit_limit;
1850
1851         if (base == 0) {
1852                 if (**p != '0')
1853                         base = 10;
1854                 else if ((*p)[1] == 'x' || (*p)[1] == 'X') {
1855                         *p += 2;
1856                         base = 16;
1857                 } else {
1858                         base = 8;
1859                 }
1860         }
1861
1862         if (**p == '-') {
1863                 limit = INT64_MIN / base;
1864                 last_digit_limit = INT64_MIN % base;
1865                 ++(*p);
1866
1867                 l = 0;
1868                 digit = parsedigit(**p);
1869                 while (digit >= 0 && digit < base) {
1870                         if (l < limit || (l == limit && digit > last_digit_limit))
1871                                 return INT64_MIN;
1872                         l = (l * base) - digit;
1873                         digit = parsedigit(*++(*p));
1874                 }
1875                 return l;
1876         } else {
1877                 limit = INT64_MAX / base;
1878                 last_digit_limit = INT64_MAX % base;
1879
1880                 l = 0;
1881                 digit = parsedigit(**p);
1882                 while (digit >= 0 && digit < base) {
1883                         if (l > limit || (l == limit && digit > last_digit_limit))
1884                                 return INT64_MAX;
1885                         l = (l * base) + digit;
1886                         digit = parsedigit(*++(*p));
1887                 }
1888                 return l;
1889         }
1890 }
1891
1892 /*
1893  * Returns length of line (including trailing newline)
1894  * or negative on error.  'start' argument is updated to
1895  * point to first character of line.
1896  */
1897 static ssize_t
1898 readline(struct archive_read *a, struct mtree *mtree, char **start,
1899     ssize_t limit)
1900 {
1901         ssize_t bytes_read;
1902         ssize_t total_size = 0;
1903         ssize_t find_off = 0;
1904         const void *t;
1905         void *nl;
1906         char *u;
1907
1908         /* Accumulate line in a line buffer. */
1909         for (;;) {
1910                 /* Read some more. */
1911                 t = __archive_read_ahead(a, 1, &bytes_read);
1912                 if (t == NULL)
1913                         return (0);
1914                 if (bytes_read < 0)
1915                         return (ARCHIVE_FATAL);
1916                 nl = memchr(t, '\n', bytes_read);
1917                 /* If we found '\n', trim the read to end exactly there. */
1918                 if (nl != NULL) {
1919                         bytes_read = ((const char *)nl) - ((const char *)t) + 1;
1920                 }
1921                 if (total_size + bytes_read + 1 > limit) {
1922                         archive_set_error(&a->archive,
1923                             ARCHIVE_ERRNO_FILE_FORMAT,
1924                             "Line too long");
1925                         return (ARCHIVE_FATAL);
1926                 }
1927                 if (archive_string_ensure(&mtree->line,
1928                         total_size + bytes_read + 1) == NULL) {
1929                         archive_set_error(&a->archive, ENOMEM,
1930                             "Can't allocate working buffer");
1931                         return (ARCHIVE_FATAL);
1932                 }
1933                 /* Append new bytes to string. */
1934                 memcpy(mtree->line.s + total_size, t, bytes_read);
1935                 __archive_read_consume(a, bytes_read);
1936                 total_size += bytes_read;
1937                 mtree->line.s[total_size] = '\0';
1938
1939                 for (u = mtree->line.s + find_off; *u; ++u) {
1940                         if (u[0] == '\n') {
1941                                 /* Ends with unescaped newline. */
1942                                 *start = mtree->line.s;
1943                                 return total_size;
1944                         } else if (u[0] == '#') {
1945                                 /* Ends with comment sequence #...\n */
1946                                 if (nl == NULL) {
1947                                         /* But we've not found the \n yet */
1948                                         break;
1949                                 }
1950                         } else if (u[0] == '\\') {
1951                                 if (u[1] == '\n') {
1952                                         /* Trim escaped newline. */
1953                                         total_size -= 2;
1954                                         mtree->line.s[total_size] = '\0';
1955                                         break;
1956                                 } else if (u[1] != '\0') {
1957                                         /* Skip the two-char escape sequence */
1958                                         ++u;
1959                                 }
1960                         }
1961                 }
1962                 find_off = u - mtree->line.s;
1963         }
1964 }
1965
1966 static unsigned int
1967 hash(const char *p)
1968 {
1969         /* A 32-bit version of Peter Weinberger's (PJW) hash algorithm,
1970            as used by ELF for hashing function names. */
1971         unsigned g, h = 0;
1972         while (*p != '\0') {
1973                 h = (h << 4) + *p++;
1974                 if ((g = h & 0xF0000000) != 0) {
1975                         h ^= g >> 24;
1976                         h &= 0x0FFFFFFF;
1977                 }
1978         }
1979         return h;
1980 }