wimlib.net Git - wimlib/blob - src/test_support.c

   1 /*
   2  * test_support.c - Supporting code for tests
   3  */
   4
   5 /*
   6  * Copyright (C) 2015-2016 Eric Biggers
   7  *
   8  * This file is free software; you can redistribute it and/or modify it under
   9  * the terms of the GNU Lesser General Public License as published by the Free
  10  * Software Foundation; either version 3 of the License, or (at your option) any
  11  * later version.
  12  *
  13  * This file is distributed in the hope that it will be useful, but WITHOUT
  14  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  15  * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public License
  19  * along with this file; if not, see http://www.gnu.org/licenses/.
  20  */
  21
  22 /*
  23  * This file contains specialized test code which is only compiled when the
  24  * library is configured with --enable-test-support.  The major features are:
  25  *
  26  *      - Random directory tree generation
  27  *      - Directory tree comparison
  28  */
  29
  30 #ifdef HAVE_CONFIG_H
  31 #  include "config.h"
  32 #endif
  33
  34 #ifdef ENABLE_TEST_SUPPORT
  35
  36 #include <ctype.h>
  37 #include <math.h>
  38 #include <stdlib.h>
  39 #include <sys/stat.h>
  40 #include <unistd.h>
  41
  42 #include "wimlib.h"
  43 #include "wimlib/endianness.h"
  44 #include "wimlib/encoding.h"
  45 #include "wimlib/metadata.h"
  46 #include "wimlib/dentry.h"
  47 #include "wimlib/inode.h"
  48 #include "wimlib/object_id.h"
  49 #include "wimlib/reparse.h"
  50 #include "wimlib/scan.h"
  51 #include "wimlib/security_descriptor.h"
  52 #include "wimlib/test_support.h"
  53 #include "wimlib/unix_data.h"
  54
  55 /*----------------------------------------------------------------------------*
  56  *                            File tree generation                            *
  57  *----------------------------------------------------------------------------*/
  58
  59 struct generation_context {
  60         struct scan_params *params;
  61         struct wim_dentry *used_short_names[256];
  62         bool metadata_only;
  63 };
  64
  65 static u32
  66 rand32(void)
  67 {
  68         static u64 state = 0x55DB93D0AB838771;
  69
  70         /* A simple linear congruential generator  */
  71         state = (state * 25214903917 + 11) & ((1ULL << 48) - 1);
  72         return state >> 16;
  73 }
  74
  75 static bool
  76 randbool(void)
  77 {
  78         return (rand32() & 1) != 0;
  79 }
  80
  81 static u8
  82 rand8(void)
  83 {
  84         return (u8)rand32();
  85 }
  86
  87 static u16
  88 rand16(void)
  89 {
  90         return (u16)rand32();
  91 }
  92
  93 static u64
  94 rand64(void)
  95 {
  96         return ((u64)rand32() << 32) | rand32();
  97 }
  98
  99 static u64
 100 generate_random_timestamp(void)
 101 {
 102         /* When setting timestamps on Windows:
 103          * - 0 is a special value meaning "not specified"
 104          * - if the high bit is set you get STATUS_INVALID_PARAMETER  */
 105         return (1 + rand64()) & ~(1ULL << 63);
 106 }
 107
 108 static inline bool
 109 is_valid_windows_filename_char(utf16lechar c)
 110 {
 111         return le16_to_cpu(c) > 31 &&
 112                 c != cpu_to_le16('/') &&
 113                 c != cpu_to_le16('<') &&
 114                 c != cpu_to_le16('>') &&
 115                 c != cpu_to_le16(':') &&
 116                 c != cpu_to_le16('"') &&
 117                 c != cpu_to_le16('/' ) &&
 118                 c != cpu_to_le16('\\') &&
 119                 c != cpu_to_le16('|') &&
 120                 c != cpu_to_le16('?') &&
 121                 c != cpu_to_le16('*');
 122 }
 123
 124 /* Is the character valid in a filename on the current platform? */
 125 static inline bool
 126 is_valid_filename_char(utf16lechar c)
 127 {
 128 #ifdef __WIN32__
 129         return is_valid_windows_filename_char(c);
 130 #else
 131         return c != cpu_to_le16('\0') && c != cpu_to_le16('/');
 132 #endif
 133 }
 134
 135 /* Generate a random filename and return its length. */
 136 static int
 137 generate_random_filename(utf16lechar name[], int max_len,
 138                          struct generation_context *ctx)
 139 {
 140         int len;
 141
 142         /* Choose the length of the name. */
 143         switch (rand32() % 8) {
 144         default:
 145                 /* short name  */
 146                 len = 1 + (rand32() % 6);
 147                 break;
 148         case 2:
 149         case 3:
 150         case 4:
 151                 /* medium-length name  */
 152                 len = 7 + (rand32() % 8);
 153                 break;
 154         case 5:
 155         case 6:
 156                 /* long name  */
 157                 len = 15 + (rand32() % 15);
 158                 break;
 159         case 7:
 160                 /* very long name  */
 161                 len = 30 + (rand32() % 90);
 162                 break;
 163         }
 164         len = min(len, max_len);
 165
 166 retry:
 167         /* Generate the characters in the name. */
 168         for (int i = 0; i < len; i++) {
 169                 do {
 170                         name[i] = rand16();
 171                 } while (!is_valid_filename_char(name[i]));
 172         }
 173
 174         /* Add a null terminator. */
 175         name[len] = cpu_to_le16('\0');
 176
 177         /* Don't generate . and .. */
 178         if (name[0] == cpu_to_le16('.') &&
 179             (len == 1 || (len == 2 && name[1] == cpu_to_le16('.'))))
 180                 goto retry;
 181
 182         return len;
 183 }
 184
 185 /* The set of characters which are valid in short filenames. */
 186 static const char valid_short_name_chars[] = {
 187         'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
 188         'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
 189         '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
 190         '!', '#', '$', '%', '&', '\'', '(', ')', '-', '@', '^', '_', '`', '{',
 191         '}', '~',
 192         /* Note: Windows does not allow space and 128-255 in short filenames
 193          * (tested on both NTFS and FAT). */
 194 };
 195
 196 static int
 197 generate_short_name_component(utf16lechar p[], int len)
 198 {
 199         for (int i = 0; i < len; i++) {
 200                 char c = valid_short_name_chars[rand32() %
 201                                                 ARRAY_LEN(valid_short_name_chars)];
 202                 p[i] = cpu_to_le16(c);
 203         }
 204         return len;
 205 }
 206
 207 /* Generate a random short (8.3) filename and return its length.
 208  * The @name array must have length >= 13 (8 + 1 + 3 + 1). */
 209 static int
 210 generate_random_short_name(utf16lechar name[], struct generation_context *ctx)
 211 {
 212         /*
 213          * Legal short names on Windows consist of 1 to 8 characters, optionally
 214          * followed by a dot then 1 to 3 more characters.  Only certain
 215          * characters are allowed.
 216          */
 217         int base_len = 1 + (rand32() % 8);
 218         int ext_len = rand32() % 4;
 219         int total_len;
 220
 221         base_len = generate_short_name_component(name, base_len);
 222
 223         if (ext_len) {
 224                 name[base_len] = cpu_to_le16('.');
 225                 ext_len = generate_short_name_component(&name[base_len + 1],
 226                                                         ext_len);
 227                 total_len = base_len + 1 + ext_len;
 228         } else {
 229                 total_len = base_len;
 230         }
 231         name[total_len] = cpu_to_le16('\0');
 232         return total_len;
 233 }
 234
 235
 236 static const struct {
 237         u8 num_subauthorities;
 238         u64 identifier_authority;
 239         u32 subauthorities[6];
 240 } common_sids[] = {
 241         { 1, 0, {0}}, /* NULL_SID  */
 242         { 1, 1, {0}}, /* WORLD_SID */
 243         { 1, 2, {0}}, /* LOCAL_SID */
 244         { 1, 3, {0}}, /* CREATOR_OWNER_SID */
 245         { 1, 3, {1}}, /* CREATOR_GROUP_SID */
 246         { 1, 3, {2}}, /* CREATOR_OWNER_SERVER_SID */
 247         { 1, 3, {3}}, /* CREATOR_GROUP_SERVER_SID */
 248         // { 0, 5, {}},  /* NT_AUTHORITY_SID */
 249         { 1, 5, {1}}, /* DIALUP_SID */
 250         { 1, 5, {2}}, /* NETWORK_SID */
 251         { 1, 5, {3}}, /* BATCH_SID */
 252         { 1, 5, {4}}, /* INTERACTIVE_SID */
 253         { 1, 5, {6}}, /* SERVICE_SID */
 254         { 1, 5, {7}}, /* ANONYMOUS_LOGON_SID */
 255         { 1, 5, {8}}, /* PROXY_SID */
 256         { 1, 5, {9}}, /* SERVER_LOGON_SID */
 257         { 1, 5, {10}}, /* SELF_SID */
 258         { 1, 5, {11}}, /* AUTHENTICATED_USER_SID */
 259         { 1, 5, {12}}, /* RESTRICTED_CODE_SID */
 260         { 1, 5, {13}}, /* TERMINAL_SERVER_SID */
 261         { 1, 5, {18}}, /* NT AUTHORITY\SYSTEM */
 262         { 1, 5, {19}}, /* NT AUTHORITY\LOCAL SERVICE */
 263         { 1, 5, {20}}, /* NT AUTHORITY\NETWORK SERVICE */
 264         { 5 ,80, {956008885, 3418522649, 1831038044, 1853292631, 2271478464}}, /* trusted installer  */
 265         { 2 ,5, {32, 544} } /* BUILTIN\ADMINISTRATORS  */
 266 };
 267
 268 /* Generate a SID and return its size in bytes.  */
 269 static size_t
 270 generate_random_sid(wimlib_SID *sid, struct generation_context *ctx)
 271 {
 272         u32 r = rand32();
 273
 274         sid->revision = 1;
 275
 276         if (r & 1) {
 277                 /* Common SID  */
 278                 r = (r >> 1) % ARRAY_LEN(common_sids);
 279
 280                 sid->sub_authority_count = common_sids[r].num_subauthorities;
 281                 for (int i = 0; i < 6; i++) {
 282                         sid->identifier_authority[i] =
 283                                 common_sids[r].identifier_authority >> (40 - i * 8);
 284                 }
 285                 for (int i = 0; i < common_sids[r].num_subauthorities; i++)
 286                         sid->sub_authority[i] = cpu_to_le32(common_sids[r].subauthorities[i]);
 287         } else {
 288                 /* Random SID  */
 289
 290                 sid->sub_authority_count = 1 + ((r >> 1) % 15);
 291
 292                 for (int i = 0; i < 6; i++)
 293                         sid->identifier_authority[i] = rand8();
 294
 295                 for (int i = 0; i < sid->sub_authority_count; i++)
 296                         sid->sub_authority[i] = cpu_to_le32(rand32());
 297         }
 298         return (u8 *)&sid->sub_authority[sid->sub_authority_count] - (u8 *)sid;
 299 }
 300
 301 /* Generate an ACL and return its size in bytes.  */
 302 static size_t
 303 generate_random_acl(wimlib_ACL *acl, bool dacl, struct generation_context *ctx)
 304 {
 305         u8 *p;
 306         u16 ace_count;
 307
 308         ace_count = rand32() % 16;
 309
 310         acl->revision = 2;
 311         acl->sbz1 = 0;
 312         acl->ace_count = cpu_to_le16(ace_count);
 313         acl->sbz2 = 0;
 314
 315         p = (u8 *)(acl + 1);
 316
 317         for (int i = 0; i < ace_count; i++) {
 318                 wimlib_ACCESS_ALLOWED_ACE *ace = (wimlib_ACCESS_ALLOWED_ACE *)p;
 319
 320                 /* ACCESS_ALLOWED, ACCESS_DENIED, or SYSTEM_AUDIT; format is the
 321                  * same for all  */
 322                 if (dacl)
 323                         ace->hdr.type = rand32() % 2;
 324                 else
 325                         ace->hdr.type = 2;
 326                 ace->hdr.flags = rand8();
 327                 ace->mask = cpu_to_le32(rand32() & 0x001F01FF);
 328
 329                 p += offsetof(wimlib_ACCESS_ALLOWED_ACE, sid) +
 330                         generate_random_sid(&ace->sid, ctx);
 331                 ace->hdr.size = cpu_to_le16(p - (u8 *)ace);
 332         }
 333
 334         acl->acl_size = cpu_to_le16(p - (u8 *)acl);
 335         return p - (u8 *)acl;
 336 }
 337
 338 /* Generate a security descriptor and return its size in bytes.  */
 339 static size_t
 340 generate_random_security_descriptor(void *_desc, struct generation_context *ctx)
 341 {
 342         wimlib_SECURITY_DESCRIPTOR_RELATIVE *desc = _desc;
 343         u16 control;
 344         u8 *p;
 345
 346         control = rand16();
 347
 348         control &= (wimlib_SE_DACL_AUTO_INHERITED |
 349                     wimlib_SE_SACL_AUTO_INHERITED);
 350
 351         control |= wimlib_SE_SELF_RELATIVE |
 352                    wimlib_SE_DACL_PRESENT |
 353                    wimlib_SE_SACL_PRESENT;
 354
 355         desc->revision = 1;
 356         desc->sbz1 = 0;
 357         desc->control = cpu_to_le16(control);
 358
 359         p = (u8 *)(desc + 1);
 360
 361         desc->owner_offset = cpu_to_le32(p - (u8 *)desc);
 362         p += generate_random_sid((wimlib_SID *)p, ctx);
 363
 364         desc->group_offset = cpu_to_le32(p - (u8 *)desc);
 365         p += generate_random_sid((wimlib_SID *)p, ctx);
 366
 367         if ((control & wimlib_SE_DACL_PRESENT) && randbool()) {
 368                 desc->dacl_offset = cpu_to_le32(p - (u8 *)desc);
 369                 p += generate_random_acl((wimlib_ACL *)p, true, ctx);
 370         } else {
 371                 desc->dacl_offset = cpu_to_le32(0);
 372         }
 373
 374         if ((control & wimlib_SE_SACL_PRESENT) && randbool()) {
 375                 desc->sacl_offset = cpu_to_le32(p - (u8 *)desc);
 376                 p += generate_random_acl((wimlib_ACL *)p, false, ctx);
 377         } else {
 378                 desc->sacl_offset = cpu_to_le32(0);
 379         }
 380
 381         return p - (u8 *)desc;
 382 }
 383
 384 static bool
 385 am_root(void)
 386 {
 387 #ifdef __WIN32__
 388         return false;
 389 #else
 390         return (getuid() == 0);
 391 #endif
 392 }
 393
 394 static u32
 395 generate_uid(void)
 396 {
 397 #ifdef __WIN32__
 398         return 0;
 399 #else
 400         if (am_root())
 401                 return rand32();
 402         return getuid();
 403 #endif
 404 }
 405
 406 static u32
 407 generate_gid(void)
 408 {
 409 #ifdef __WIN32__
 410         return 0;
 411 #else
 412         if (am_root())
 413                 return rand32();
 414         return getgid();
 415 #endif
 416 }
 417
 418 #ifdef __WIN32__
 419 #  ifndef S_IFLNK
 420 #    define S_IFLNK  0120000
 421 #  endif
 422 #  ifndef S_IFSOCK
 423 #    define S_IFSOCK 0140000
 424 #  endif
 425 #endif
 426
 427 static int
 428 set_random_unix_metadata(struct wim_inode *inode)
 429 {
 430         struct wimlib_unix_data dat;
 431
 432         dat.uid = generate_uid();
 433         dat.gid = generate_gid();
 434         if (inode_is_symlink(inode))
 435                 dat.mode = S_IFLNK | 0777;
 436         else if (inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY)
 437                 dat.mode = S_IFDIR | 0700 | (rand32() % 07777);
 438         else if (is_zero_hash(inode_get_hash_of_unnamed_data_stream(inode)) &&
 439                  randbool() && am_root())
 440         {
 441                 dat.mode = rand32() % 07777;
 442                 switch (rand32() % 4) {
 443                 case 0:
 444                         dat.mode |= S_IFIFO;
 445                         break;
 446                 case 1:
 447                         dat.mode |= S_IFCHR;
 448                         dat.rdev = 261; /* /dev/zero */
 449                         break;
 450                 case 2:
 451                         dat.mode |= S_IFBLK;
 452                         dat.rdev = 261; /* /dev/zero */
 453                         break;
 454                 default:
 455                         dat.mode |= S_IFSOCK;
 456                         break;
 457                 }
 458         } else {
 459                 dat.mode = S_IFREG | 0400 | (rand32() % 07777);
 460         }
 461         dat.rdev = 0;
 462
 463         if (!inode_set_unix_data(inode, &dat, UNIX_DATA_ALL))
 464                 return WIMLIB_ERR_NOMEM;
 465
 466         return 0;
 467 }
 468
 469 static int
 470 set_random_metadata(struct wim_inode *inode, struct generation_context *ctx)
 471 {
 472         u32 attrib = (rand32() & (FILE_ATTRIBUTE_READONLY |
 473                                   FILE_ATTRIBUTE_HIDDEN |
 474                                   FILE_ATTRIBUTE_SYSTEM |
 475                                   FILE_ATTRIBUTE_ARCHIVE |
 476                                   FILE_ATTRIBUTE_NOT_CONTENT_INDEXED |
 477                                   FILE_ATTRIBUTE_COMPRESSED |
 478                                   FILE_ATTRIBUTE_SPARSE_FILE));
 479
 480         /* File attributes  */
 481         inode->i_attributes |= attrib;
 482
 483         /* Timestamps  */
 484         inode->i_creation_time = generate_random_timestamp();
 485         inode->i_last_access_time = generate_random_timestamp();
 486         inode->i_last_write_time = generate_random_timestamp();
 487
 488         /* Security descriptor  */
 489         if (randbool()) {
 490                 char desc[8192] _aligned_attribute(8);
 491                 size_t size;
 492
 493                 size = generate_random_security_descriptor(desc, ctx);
 494
 495                 wimlib_assert(size <= sizeof(desc));
 496
 497                 inode->i_security_id = sd_set_add_sd(ctx->params->sd_set,
 498                                                      desc, size);
 499                 if (unlikely(inode->i_security_id < 0))
 500                         return WIMLIB_ERR_NOMEM;
 501         }
 502
 503         /* Object ID  */
 504         if (rand32() % 32 == 0) {
 505                 struct wimlib_object_id object_id;
 506
 507                 for (int i = 0; i < sizeof(object_id); i++)
 508                         *((u8 *)&object_id + i) = rand8();
 509                 if (!inode_set_object_id(inode, &object_id, sizeof(object_id)))
 510                         return WIMLIB_ERR_NOMEM;
 511         }
 512
 513         /* Standard UNIX permissions and special files */
 514         if (rand32() % 16 == 0) {
 515                 int ret = set_random_unix_metadata(inode);
 516                 if (ret)
 517                         return ret;
 518         }
 519
 520         return 0;
 521
 522 }
 523
 524 /* Choose a random size for generated file data.  We want to usually generate
 525  * empty, small, or medium files, but occasionally generate large files.  */
 526 static size_t
 527 select_stream_size(struct generation_context *ctx)
 528 {
 529         if (ctx->metadata_only)
 530                 return 0;
 531
 532         switch (rand32() % 2048) {
 533         default:
 534                 /* Empty  */
 535                 return 0;
 536         case 600 ... 799:
 537                 /* Microscopic  */
 538                 return rand32() % 64;
 539         case 800 ... 1319:
 540                 /* Tiny  */
 541                 return rand32() % 4096;
 542         case 1320 ... 1799:
 543                 /* Small  */
 544                 return rand32() % 32768;
 545         case 1800 ... 2046:
 546                 /* Medium  */
 547                 return rand32() % 262144;
 548         case 2047:
 549                 /* Large  */
 550                 return rand32() % 134217728;
 551         }
 552 }
 553
 554 /* Fill 'buffer' with 'size' bytes of "interesting" file data.  */
 555 static void
 556 generate_data(u8 *buffer, size_t size, struct generation_context *ctx)
 557 {
 558         size_t mask = -1;
 559         size_t num_byte_fills = rand32() % 256;
 560
 561         if (size == 0)
 562                 return;
 563
 564         /* Start by initializing to a random byte */
 565         memset(buffer, rand32() % 256, size);
 566
 567         /* Add some random bytes in some random places */
 568         for (size_t i = 0; i < num_byte_fills; i++) {
 569                 u8 b = rand8();
 570
 571                 size_t count = ((double)size / (double)num_byte_fills) *
 572                                 ((double)rand32() / 2e9);
 573                 size_t offset = rand32() & ~mask;
 574
 575                 while (count--) {
 576                         buffer[(offset +
 577                                 ((rand32()) & mask)) % size] = b;
 578                 }
 579
 580
 581                 if (rand32() % 4 == 0)
 582                         mask = (size_t)-1 << rand32() % 4;
 583         }
 584
 585         /* Sometimes add a wave pattern */
 586         if (rand32() % 8 == 0) {
 587                 double magnitude = rand32() % 128;
 588                 double scale = 1.0 / (1 + (rand32() % 256));
 589
 590                 for (size_t i = 0; i < size; i++)
 591                         buffer[i] += (int)(magnitude * cos(i * scale));
 592         }
 593
 594         /* Sometimes add some zero regions (holes) */
 595         if (rand32() % 4 == 0) {
 596                 size_t num_holes = 1 + (rand32() % 16);
 597                 for (size_t i = 0; i < num_holes; i++) {
 598                         size_t hole_offset = rand32() % size;
 599                         size_t hole_len = min(size - hole_offset,
 600                                               size / (1 + (rand32() % 16)));
 601                         memset(&buffer[hole_offset], 0, hole_len);
 602                 }
 603         }
 604 }
 605
 606 static int
 607 add_stream(struct wim_inode *inode, struct generation_context *ctx,
 608            int stream_type, const utf16lechar *stream_name,
 609            void *buffer, size_t size)
 610 {
 611         struct blob_descriptor *blob = NULL;
 612         struct wim_inode_stream *strm;
 613
 614         if (size) {
 615                 blob = new_blob_descriptor();
 616                 if (!blob)
 617                         goto err_nomem;
 618                 blob->attached_buffer = buffer;
 619                 blob->blob_location = BLOB_IN_ATTACHED_BUFFER;
 620                 blob->size = size;
 621         }
 622
 623         strm = inode_add_stream(inode, stream_type, stream_name, blob);
 624         if (unlikely(!strm))
 625                 goto err_nomem;
 626
 627         prepare_unhashed_blob(blob, inode, strm->stream_id,
 628                               ctx->params->unhashed_blobs);
 629         return 0;
 630
 631 err_nomem:
 632         free_blob_descriptor(blob);
 633         return WIMLIB_ERR_NOMEM;
 634 }
 635
 636 static noinline_for_stack int
 637 set_random_reparse_point(struct wim_inode *inode, struct generation_context *ctx)
 638 {
 639         struct reparse_buffer_disk rpbuf;
 640         size_t rpdatalen;
 641
 642         inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
 643
 644         if (randbool()) {
 645                 /* Symlink */
 646                 int target_nchars;
 647                 utf16lechar *targets = (utf16lechar *)rpbuf.link.symlink.data;
 648
 649                 inode->i_reparse_tag = WIM_IO_REPARSE_TAG_SYMLINK;
 650
 651                 target_nchars = generate_random_filename(targets, 255, ctx);
 652
 653                 rpbuf.link.substitute_name_offset = cpu_to_le16(0);
 654                 rpbuf.link.substitute_name_nbytes = cpu_to_le16(2*target_nchars);
 655                 rpbuf.link.print_name_offset = cpu_to_le16(2*(target_nchars + 1));
 656                 rpbuf.link.print_name_nbytes = cpu_to_le16(2*target_nchars);
 657                 targets[target_nchars] = cpu_to_le16(0);
 658                 memcpy(&targets[target_nchars + 1], targets, 2*target_nchars);
 659                 targets[target_nchars + 1 + target_nchars] = cpu_to_le16(0);
 660
 661                 rpbuf.link.symlink.flags = cpu_to_le32(SYMBOLIC_LINK_RELATIVE);
 662                 rpdatalen = ((u8 *)targets - rpbuf.rpdata) +
 663                                 2*(target_nchars + 1 + target_nchars + 1);
 664         } else {
 665                 rpdatalen = select_stream_size(ctx) % REPARSE_DATA_MAX_SIZE;
 666                 generate_data(rpbuf.rpdata, rpdatalen, ctx);
 667
 668                 if (rpdatalen >= GUID_SIZE && randbool()) {
 669                         /* Non-Microsoft reparse tag (16-byte GUID required)  */
 670                         u8 *guid = rpbuf.rpdata;
 671                         guid[6] = (guid[6] & 0x0F) | 0x40;
 672                         guid[8] = (guid[8] & 0x3F) | 0x80;
 673                         inode->i_reparse_tag = 0x00000100;
 674                 } else {
 675                         /* Microsoft reparse tag  */
 676                         inode->i_reparse_tag = 0x80000000;
 677                 }
 678                 inode->i_rp_reserved = rand16();
 679         }
 680
 681         wimlib_assert(rpdatalen < REPARSE_DATA_MAX_SIZE);
 682
 683         if (!inode_add_stream_with_data(inode, STREAM_TYPE_REPARSE_POINT,
 684                                         NO_STREAM_NAME, rpbuf.rpdata,
 685                                         rpdatalen, ctx->params->blob_table))
 686                 return WIMLIB_ERR_NOMEM;
 687
 688         return 0;
 689 }
 690
 691 static int
 692 add_random_data_stream(struct wim_inode *inode, struct generation_context *ctx,
 693                        const utf16lechar *stream_name)
 694 {
 695         void *buffer = NULL;
 696         size_t size;
 697
 698         size = select_stream_size(ctx);
 699         if (size) {
 700                 buffer = MALLOC(size);
 701                 if (!buffer)
 702                         return WIMLIB_ERR_NOMEM;
 703                 generate_data(buffer, size, ctx);
 704         }
 705
 706         return add_stream(inode, ctx, STREAM_TYPE_DATA, stream_name,
 707                           buffer, size);
 708 }
 709
 710 static int
 711 set_random_streams(struct wim_inode *inode, struct generation_context *ctx)
 712 {
 713         int ret;
 714         u32 r;
 715
 716         /* Reparse point (sometimes)  */
 717         if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
 718                 ret = set_random_reparse_point(inode, ctx);
 719                 if (ret)
 720                         return ret;
 721         }
 722
 723         /* Unnamed data stream (nondirectories and non-symlinks only)  */
 724         if (!(inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY) &&
 725             !inode_is_symlink(inode)) {
 726                 ret = add_random_data_stream(inode, ctx, NO_STREAM_NAME);
 727                 if (ret)
 728                         return ret;
 729         }
 730
 731         /* Named data streams (sometimes)  */
 732         r = rand32() % 256;
 733         if (r > 230) {
 734                 utf16lechar stream_name[2] = {cpu_to_le16('a'), '\0'};
 735                 r -= 230;
 736                 while (r--) {
 737                         ret = add_random_data_stream(inode, ctx, stream_name);
 738                         if (ret)
 739                                 return ret;
 740                         stream_name[0] += cpu_to_le16(1);
 741                 }
 742         }
 743
 744         return 0;
 745 }
 746
 747 static u64
 748 select_inode_number(struct generation_context *ctx)
 749 {
 750         const struct wim_inode_table *table = ctx->params->inode_table;
 751         const struct hlist_head *head;
 752         const struct wim_inode *inode;
 753
 754         head = &table->array[rand32() % table->capacity];
 755         hlist_for_each_entry(inode, head, i_hlist_node)
 756                 if (randbool())
 757                         return inode->i_ino;
 758
 759         return rand32();
 760 }
 761
 762 static u32
 763 select_num_children(u32 depth, struct generation_context *ctx)
 764 {
 765         const double b = 1.01230;
 766         u32 r = rand32() % 500;
 767         return ((pow(b, pow(b, r)) - 1) / pow(depth, 1.5)) +
 768                 (2 - exp(0.04/depth));
 769 }
 770
 771 static bool
 772 is_name_valid_in_win32_namespace(const utf16lechar *name)
 773 {
 774         const utf16lechar *p;
 775
 776         static const char * const reserved_names[] = {
 777                  "CON",  "PRN",  "AUX",  "NUL",
 778                  "COM1", "COM2", "COM3", "COM4", "COM5",
 779                  "COM6", "COM7", "COM8", "COM9",
 780                  "LPT1", "LPT2", "LPT3", "LPT4", "LPT5",
 781                  "LPT6", "LPT7", "LPT8", "LPT9",
 782         };
 783
 784         /* The name must be nonempty. */
 785         if (!name || !*name)
 786                 return false;
 787
 788         /* All characters must be valid on Windows. */
 789         for (p = name; *p; p++)
 790                 if (!is_valid_windows_filename_char(*p))
 791                         return false;
 792
 793         /* Note: a trailing dot or space is permitted, even though on Windows
 794          * such a file can only be accessed using a WinNT-style path. */
 795
 796         /* The name can't be one of the reserved names or be a reserved name
 797          * with an extension.  Case insensitive. */
 798         for (size_t i = 0; i < ARRAY_LEN(reserved_names); i++) {
 799                 for (size_t j = 0; ; j++) {
 800                         u16 c1 = le16_to_cpu(name[j]);
 801                         u16 c2 = reserved_names[i][j];
 802                         if (c2 == '\0') {
 803                                 if (c1 == '\0' || c1 == '.')
 804                                         return false;
 805                                 break;
 806                         }
 807                         if (upcase[c1] != upcase[c2])
 808                                 break;
 809                 }
 810         }
 811
 812         return true;
 813 }
 814
 815 static int
 816 set_random_short_name(struct wim_dentry *dir, struct wim_dentry *child,
 817                       struct generation_context *ctx)
 818 {
 819         utf16lechar name[12 + 1];
 820         int name_len;
 821         u32 hash;
 822         struct wim_dentry **bucket;
 823
 824         /* If the long name is not allowed in the Win32 namespace, then it
 825          * cannot be assigned a corresponding short name.  */
 826         if (!is_name_valid_in_win32_namespace(child->d_name))
 827                 return 0;
 828
 829 retry:
 830         /* Don't select a short name that is already used by a long name within
 831          * the same directory.  */
 832         do {
 833                 name_len = generate_random_short_name(name, ctx);
 834         } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
 835                                                     WIMLIB_CASE_INSENSITIVE));
 836
 837
 838         /* Don't select a short name that is already used by another short name
 839          * within the same directory.  */
 840         hash = 0;
 841         for (const utf16lechar *p = name; *p; p++)
 842                 hash = (hash * 31) + *p;
 843         FREE(child->d_short_name);
 844         child->d_short_name = memdup(name, (name_len + 1) * 2);
 845         child->d_short_name_nbytes = name_len * 2;
 846
 847         if (!child->d_short_name)
 848                 return WIMLIB_ERR_NOMEM;
 849
 850         bucket = &ctx->used_short_names[hash % ARRAY_LEN(ctx->used_short_names)];
 851
 852         for (struct wim_dentry *d = *bucket; d != NULL;
 853              d = d->d_next_extraction_alias) {
 854                 if (!cmp_utf16le_strings(child->d_short_name, name_len,
 855                                          d->d_short_name, d->d_short_name_nbytes / 2,
 856                                          true)) {
 857                         goto retry;
 858                 }
 859         }
 860
 861         if (!is_name_valid_in_win32_namespace(child->d_short_name))
 862                 goto retry;
 863
 864         child->d_next_extraction_alias = *bucket;
 865         *bucket = child;
 866         return 0;
 867 }
 868
 869 static bool
 870 inode_has_short_name(const struct wim_inode *inode)
 871 {
 872         const struct wim_dentry *dentry;
 873
 874         inode_for_each_dentry(dentry, inode)
 875                 if (dentry_has_short_name(dentry))
 876                         return true;
 877
 878         return false;
 879 }
 880
 881 static int
 882 generate_dentry_tree_recursive(struct wim_dentry *dir, u32 depth,
 883                                struct generation_context *ctx)
 884 {
 885         u32 num_children = select_num_children(depth, ctx);
 886         struct wim_dentry *child;
 887         int ret;
 888
 889         memset(ctx->used_short_names, 0, sizeof(ctx->used_short_names));
 890
 891         /* Generate 'num_children' dentries within 'dir'.  Some may be
 892          * directories themselves.  */
 893
 894         for (u32 i = 0; i < num_children; i++) {
 895
 896                 /* Generate the next child dentry.  */
 897                 struct wim_inode *inode;
 898                 u64 ino;
 899                 bool is_directory = (rand32() % 16 <= 6);
 900                 bool is_reparse = (rand32() % 8 == 0);
 901                 utf16lechar name[63 + 1]; /* for UNIX extraction: 63 * 4 <= 255 */
 902                 int name_len;
 903                 struct wim_dentry *duplicate;
 904
 905                 /*
 906                  * Select an inode number for the new file.  Sometimes choose an
 907                  * existing inode number (i.e. create a hard link).  However,
 908                  * wimlib intentionally doesn't honor directory hard links, and
 909                  * reparse points cannot be represented in the WIM file format
 910                  * at all; so don't create hard links for such files.
 911                  */
 912                 if (is_directory || is_reparse)
 913                         ino = 0;
 914                 else
 915                         ino = select_inode_number(ctx);
 916
 917                 /* Create the dentry. */
 918                 ret = inode_table_new_dentry(ctx->params->inode_table, NULL,
 919                                              ino, 0, ino == 0, &child);
 920                 if (ret)
 921                         return ret;
 922
 923                 /* Choose a filename that is unique within the directory.*/
 924                 do {
 925                         name_len = generate_random_filename(name,
 926                                                             ARRAY_LEN(name) - 1,
 927                                                             ctx);
 928                 } while (get_dentry_child_with_utf16le_name(dir, name, name_len * 2,
 929                                                             WIMLIB_CASE_PLATFORM_DEFAULT));
 930
 931                 ret = dentry_set_name_utf16le(child, name, name_len * 2);
 932                 if (ret) {
 933                         free_dentry(child);
 934                         return ret;
 935                 }
 936
 937                 /* Add the dentry to the directory. */
 938                 duplicate = dentry_add_child(dir, child);
 939                 wimlib_assert(!duplicate);
 940
 941                 inode = child->d_inode;
 942
 943                 if (inode->i_nlink > 1)  /* Existing inode?  */
 944                         continue;
 945
 946                 /* New inode; set attributes, metadata, and data.  */
 947
 948                 if (is_directory)
 949                         inode->i_attributes |= FILE_ATTRIBUTE_DIRECTORY;
 950                 if (is_reparse)
 951                         inode->i_attributes |= FILE_ATTRIBUTE_REPARSE_POINT;
 952
 953                 ret = set_random_streams(inode, ctx);
 954                 if (ret)
 955                         return ret;
 956
 957                 ret = set_random_metadata(inode, ctx);
 958                 if (ret)
 959                         return ret;
 960
 961                 /* Recurse if it's a directory.  */
 962                 if (is_directory && !is_reparse) {
 963                         ret = generate_dentry_tree_recursive(child, depth + 1,
 964                                                              ctx);
 965                         if (ret)
 966                                 return ret;
 967                 }
 968         }
 969
 970         for_dentry_child(child, dir) {
 971                 /* sometimes generate a unique short name  */
 972                 if (randbool() && !inode_has_short_name(child->d_inode)) {
 973                         ret = set_random_short_name(dir, child, ctx);
 974                         if (ret)
 975                                 return ret;
 976                 }
 977         }
 978
 979         return 0;
 980 }
 981
 982 int
 983 generate_dentry_tree(struct wim_dentry **root_ret, const tchar *_ignored,
 984                      struct scan_params *params)
 985 {
 986         int ret;
 987         struct wim_dentry *root = NULL;
 988         struct generation_context ctx = {
 989                 .params = params,
 990         };
 991
 992         ctx.metadata_only = ((rand32() % 8) != 0); /* usually metadata only  */
 993
 994         ret = inode_table_new_dentry(params->inode_table, NULL, 0, 0, true, &root);
 995         if (!ret) {
 996                 root->d_inode->i_attributes = FILE_ATTRIBUTE_DIRECTORY;
 997                 ret = set_random_streams(root->d_inode, &ctx);
 998         }
 999         if (!ret)
1000                 ret = set_random_metadata(root->d_inode, &ctx);
1001         if (!ret)
1002                 ret = generate_dentry_tree_recursive(root, 1, &ctx);
1003         if (!ret)
1004                 *root_ret = root;
1005         else
1006                 free_dentry_tree(root, params->blob_table);
1007         return ret;
1008 }
1009
1010 /*----------------------------------------------------------------------------*
1011  *                            File tree comparison                            *
1012  *----------------------------------------------------------------------------*/
1013
1014 #define INDEX_NODE_TO_DENTRY(node)      \
1015         ((node) ? avl_tree_entry((node), struct wim_dentry, d_index_node) : NULL)
1016
1017 static struct wim_dentry *
1018 dentry_first_child(struct wim_dentry *dentry)
1019 {
1020         return INDEX_NODE_TO_DENTRY(
1021                         avl_tree_first_in_order(dentry->d_inode->i_children));
1022 }
1023
1024 static struct wim_dentry *
1025 dentry_next_sibling(struct wim_dentry *dentry)
1026 {
1027         return INDEX_NODE_TO_DENTRY(
1028                         avl_tree_next_in_order(&dentry->d_index_node));
1029 }
1030
1031 /*
1032  * Verify that the dentries in the tree 'd1' exactly match the dentries in the
1033  * tree 'd2', considering long and short filenames.  In addition, set
1034  * 'd_corresponding' of each dentry to point to the corresponding dentry in the
1035  * other tree, and set 'i_corresponding' of each inode to point to the
1036  * unverified corresponding inode in the other tree.
1037  */
1038 static int
1039 calc_corresponding_files_recursive(struct wim_dentry *d1, struct wim_dentry *d2,
1040                                    int cmp_flags)
1041 {
1042         struct wim_dentry *child1;
1043         struct wim_dentry *child2;
1044         int ret;
1045
1046         /* Compare long filenames, case sensitively.  */
1047         if (cmp_utf16le_strings(d1->d_name, d1->d_name_nbytes / 2,
1048                                 d2->d_name, d2->d_name_nbytes / 2,
1049                                 false))
1050         {
1051                 ERROR("Filename mismatch; path1=\"%"TS"\", path2=\"%"TS"\"",
1052                       dentry_full_path(d1), dentry_full_path(d2));
1053                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1054         }
1055
1056         /* Compare short filenames, case insensitively.  */
1057         if (!(d2->d_short_name_nbytes == 0 &&
1058               (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) &&
1059             cmp_utf16le_strings(d1->d_short_name, d1->d_short_name_nbytes / 2,
1060                                 d2->d_short_name, d2->d_short_name_nbytes / 2,
1061                                 true))
1062         {
1063                 ERROR("Short name mismatch; path=\"%"TS"\"",
1064                       dentry_full_path(d1));
1065                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1066         }
1067
1068         /* Match up the dentries  */
1069         d1->d_corresponding = d2;
1070         d2->d_corresponding = d1;
1071
1072         /* Match up the inodes (may overwrite previous value)  */
1073         d1->d_inode->i_corresponding = d2->d_inode;
1074         d2->d_inode->i_corresponding = d1->d_inode;
1075
1076         /* Process children  */
1077         child1 = dentry_first_child(d1);
1078         child2 = dentry_first_child(d2);
1079         while (child1 || child2) {
1080
1081                 if (!child1 || !child2) {
1082                         ERROR("Child count mismatch; "
1083                               "path1=\"%"TS"\", path2=\"%"TS"\"",
1084                               dentry_full_path(d1), dentry_full_path(d2));
1085                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1086                 }
1087
1088                 /* Recurse on this pair of children.  */
1089                 ret = calc_corresponding_files_recursive(child1, child2,
1090                                                          cmp_flags);
1091                 if (ret)
1092                         return ret;
1093
1094                 /* Continue to the next pair of children.  */
1095                 child1 = dentry_next_sibling(child1);
1096                 child2 = dentry_next_sibling(child2);
1097         }
1098         return 0;
1099 }
1100
1101 /* Perform sanity checks on an image's inodes.  All assertions here should pass,
1102  * even if the images being compared are different.  */
1103 static void
1104 assert_inodes_sane(const struct wim_image_metadata *imd)
1105 {
1106         const struct wim_inode *inode;
1107         const struct wim_dentry *dentry;
1108         size_t link_count;
1109
1110         image_for_each_inode(inode, imd) {
1111                 link_count = 0;
1112                 inode_for_each_dentry(dentry, inode) {
1113                         wimlib_assert(dentry->d_inode == inode);
1114                         link_count++;
1115                 }
1116                 wimlib_assert(link_count > 0);
1117                 wimlib_assert(link_count == inode->i_nlink);
1118                 wimlib_assert(inode->i_corresponding != NULL);
1119         }
1120 }
1121
1122 static int
1123 check_hard_link(struct wim_dentry *dentry, void *_ignore)
1124 {
1125         /* My inode is my corresponding dentry's inode's corresponding inode,
1126          * and my inode's corresponding inode is my corresponding dentry's
1127          * inode.  */
1128         const struct wim_inode *a = dentry->d_inode;
1129         const struct wim_inode *b = dentry->d_corresponding->d_inode;
1130         if (a == b->i_corresponding && a->i_corresponding == b)
1131                 return 0;
1132         ERROR("Hard link difference; path=%"TS"", dentry_full_path(dentry));
1133         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1134 }
1135
1136 static const struct {
1137         u32 flag;
1138         const char *name;
1139 } file_attr_flags[] = {
1140         {FILE_ATTRIBUTE_READONLY,            "READONLY"},
1141         {FILE_ATTRIBUTE_HIDDEN,              "HIDDEN"},
1142         {FILE_ATTRIBUTE_SYSTEM,              "SYSTEM"},
1143         {FILE_ATTRIBUTE_DIRECTORY,           "DIRECTORY"},
1144         {FILE_ATTRIBUTE_ARCHIVE,             "ARCHIVE"},
1145         {FILE_ATTRIBUTE_DEVICE,              "DEVICE"},
1146         {FILE_ATTRIBUTE_NORMAL,              "NORMAL"},
1147         {FILE_ATTRIBUTE_TEMPORARY,           "TEMPORARY"},
1148         {FILE_ATTRIBUTE_SPARSE_FILE,         "SPARSE_FILE"},
1149         {FILE_ATTRIBUTE_REPARSE_POINT,       "REPARSE_POINT"},
1150         {FILE_ATTRIBUTE_COMPRESSED,          "COMPRESSED"},
1151         {FILE_ATTRIBUTE_OFFLINE,             "OFFLINE"},
1152         {FILE_ATTRIBUTE_NOT_CONTENT_INDEXED, "NOT_CONTENT_INDEXED"},
1153         {FILE_ATTRIBUTE_ENCRYPTED,           "ENCRYPTED"},
1154         {FILE_ATTRIBUTE_VIRTUAL,             "VIRTUAL"},
1155 };
1156
1157 static int
1158 cmp_attributes(const struct wim_inode *inode1,
1159                const struct wim_inode *inode2, int cmp_flags)
1160 {
1161         const u32 changed = inode1->i_attributes ^ inode2->i_attributes;
1162         const u32 set = inode2->i_attributes & ~inode1->i_attributes;
1163         const u32 cleared = inode1->i_attributes & ~inode2->i_attributes;
1164
1165         /* NORMAL may change, but it must never be set along with other
1166          * attributes. */
1167         if ((inode2->i_attributes & FILE_ATTRIBUTE_NORMAL) &&
1168             (inode2->i_attributes & ~FILE_ATTRIBUTE_NORMAL))
1169                 goto mismatch;
1170
1171         /* DIRECTORY may change in UNIX mode for symlinks. */
1172         if (changed & FILE_ATTRIBUTE_DIRECTORY) {
1173                 if (!(inode_is_symlink(inode1) &&
1174                       (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)))
1175                         goto mismatch;
1176         }
1177
1178         /* REPARSE_POINT may be cleared in UNIX mode if the inode is not a
1179          * symlink. */
1180         if ((changed & FILE_ATTRIBUTE_REPARSE_POINT) &&
1181             !((cleared & FILE_ATTRIBUTE_REPARSE_POINT) &&
1182               (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE) &&
1183               !inode_is_symlink(inode1)))
1184                 goto mismatch;
1185
1186         /* SPARSE_FILE may be cleared in UNIX and NTFS-3G modes, or in Windows
1187          * mode if the inode is a directory. */
1188         if ((changed & FILE_ATTRIBUTE_SPARSE_FILE) &&
1189             !((cleared & FILE_ATTRIBUTE_SPARSE_FILE) &&
1190               ((cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1191                              WIMLIB_CMP_FLAG_NTFS_3G_MODE)) ||
1192                ((cmp_flags & WIMLIB_CMP_FLAG_WINDOWS_MODE) &&
1193                 (inode1->i_attributes & FILE_ATTRIBUTE_DIRECTORY)))))
1194                 goto mismatch;
1195
1196         /* COMPRESSED may change in UNIX and NTFS-3G modes.  (It *should* be
1197          * preserved in NTFS-3G mode, but it's not implemented yet.) */
1198         if ((changed & FILE_ATTRIBUTE_COMPRESSED) &&
1199             !(cmp_flags & (WIMLIB_CMP_FLAG_UNIX_MODE |
1200                            WIMLIB_CMP_FLAG_NTFS_3G_MODE)))
1201                 goto mismatch;
1202
1203         /* All other attributes can change in UNIX mode, but not in any other
1204          * mode. */
1205         if ((changed & ~(FILE_ATTRIBUTE_NORMAL |
1206                          FILE_ATTRIBUTE_DIRECTORY |
1207                          FILE_ATTRIBUTE_REPARSE_POINT |
1208                          FILE_ATTRIBUTE_SPARSE_FILE |
1209                          FILE_ATTRIBUTE_COMPRESSED)) &&
1210             !(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1211                 goto mismatch;
1212
1213         return 0;
1214
1215 mismatch:
1216         ERROR("Attribute mismatch for %"TS": 0x%08"PRIx32" vs. 0x%08"PRIx32":",
1217               inode_any_full_path(inode1), inode1->i_attributes,
1218               inode2->i_attributes);
1219         for (size_t i = 0; i < ARRAY_LEN(file_attr_flags); i++) {
1220                 u32 flag = file_attr_flags[i].flag;
1221                 if (changed & flag) {
1222                         fprintf(stderr, "\tFILE_ATTRIBUTE_%s was %s\n",
1223                                 file_attr_flags[i].name,
1224                                 (set & flag) ? "set" : "cleared");
1225                 }
1226         }
1227         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1228 }
1229
1230 static int
1231 cmp_object_ids(const struct wim_inode *inode1,
1232                const struct wim_inode *inode2, int cmp_flags)
1233 {
1234         const void *objid1, *objid2;
1235         u32 len1, len2;
1236
1237         objid1 = inode_get_object_id(inode1, &len1);
1238         objid2 = inode_get_object_id(inode2, &len2);
1239
1240         if (!objid1 && !objid2)
1241                 return 0;
1242
1243         if (objid1 && !objid2) {
1244                 if (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)
1245                         return 0;
1246                 ERROR("%"TS" unexpectedly lost its object ID",
1247                       inode_any_full_path(inode1));
1248                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1249         }
1250
1251         if (!objid1 && objid2) {
1252                 ERROR("%"TS" unexpectedly gained an object ID",
1253                       inode_any_full_path(inode1));
1254                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1255         }
1256
1257         if (len1 != len2 || memcmp(objid1, objid2, len1) != 0) {
1258                 ERROR("Object ID of %"TS" differs",
1259                       inode_any_full_path(inode1));
1260                 fprintf(stderr, "objid1=");
1261                 print_byte_field(objid1, len1, stderr);
1262                 fprintf(stderr, "\nobjid2=");
1263                 print_byte_field(objid2, len2, stderr);
1264                 fprintf(stderr, "\n");
1265                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1266         }
1267
1268         return 0;
1269 }
1270
1271 static int
1272 cmp_unix_metadata(const struct wim_inode *inode1,
1273                   const struct wim_inode *inode2, int cmp_flags)
1274 {
1275         struct wimlib_unix_data dat1, dat2;
1276         bool present1, present2;
1277
1278         present1 = inode_get_unix_data(inode1, &dat1);
1279         present2 = inode_get_unix_data(inode2, &dat2);
1280
1281         if (!present1 && !present2)
1282                 return 0;
1283
1284         if (present1 && !present2) {
1285                 if (cmp_flags & (WIMLIB_CMP_FLAG_NTFS_3G_MODE |
1286                                  WIMLIB_CMP_FLAG_WINDOWS_MODE))
1287                         return 0;
1288                 ERROR("%"TS" unexpectedly lost its UNIX metadata",
1289                       inode_any_full_path(inode1));
1290                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1291         }
1292
1293         if (!present1 && present2) {
1294                 if (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)
1295                         return 0;
1296                 ERROR("%"TS" unexpectedly gained UNIX metadata",
1297                       inode_any_full_path(inode1));
1298                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1299         }
1300
1301         if (memcmp(&dat1, &dat2, sizeof(dat1)) != 0) {
1302                 ERROR("UNIX metadata of %"TS" differs: "
1303                       "[uid=%u, gid=%u, mode=0%o, rdev=%u] vs. "
1304                       "[uid=%u, gid=%u, mode=0%o, rdev=%u]",
1305                       inode_any_full_path(inode1),
1306                       dat1.uid, dat1.gid, dat1.mode, dat1.rdev,
1307                       dat2.uid, dat2.gid, dat2.mode, dat2.rdev);
1308                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1309         }
1310
1311         return 0;
1312 }
1313
1314 static int
1315 cmp_inodes(const struct wim_inode *inode1, const struct wim_inode *inode2,
1316            const struct wim_image_metadata *imd1,
1317            const struct wim_image_metadata *imd2, int cmp_flags)
1318 {
1319         int ret;
1320
1321         /* Compare attributes  */
1322         ret = cmp_attributes(inode1, inode2, cmp_flags);
1323         if (ret)
1324                 return ret;
1325
1326         /* Compare security descriptors  */
1327         if (inode_has_security_descriptor(inode1)) {
1328                 if (inode_has_security_descriptor(inode2)) {
1329                         const void *desc1 = imd1->security_data->descriptors[inode1->i_security_id];
1330                         const void *desc2 = imd2->security_data->descriptors[inode2->i_security_id];
1331                         size_t size1 = imd1->security_data->sizes[inode1->i_security_id];
1332                         size_t size2 = imd2->security_data->sizes[inode2->i_security_id];
1333
1334                         if (size1 != size2 || memcmp(desc1, desc2, size1)) {
1335                                 ERROR("Security descriptor of %"TS" differs!",
1336                                       inode_any_full_path(inode1));
1337                                 return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1338                         }
1339                 } else if (!(cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE)) {
1340                         ERROR("%"TS" has a security descriptor in the first image but "
1341                               "not in the second image!", inode_any_full_path(inode1));
1342                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1343                 }
1344         } else if (inode_has_security_descriptor(inode2)) {
1345                 /* okay --- consider it acceptable if a default security
1346                  * descriptor was assigned  */
1347                 /*ERROR("%"TS" has a security descriptor in the second image but "*/
1348                       /*"not in the first image!", inode_any_full_path(inode1));*/
1349                 /*return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;*/
1350         }
1351
1352         /* Compare streams  */
1353         for (unsigned i = 0; i < inode1->i_num_streams; i++) {
1354                 const struct wim_inode_stream *strm1 = &inode1->i_streams[i];
1355                 const struct wim_inode_stream *strm2;
1356
1357                 if (strm1->stream_type == STREAM_TYPE_REPARSE_POINT &&
1358                     (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE &&
1359                      !inode_is_symlink(inode1)))
1360                         continue;
1361
1362                 if (strm1->stream_type == STREAM_TYPE_UNKNOWN)
1363                         continue;
1364
1365                 /* Get the corresponding stream from the second file  */
1366                 strm2 = inode_get_stream(inode2, strm1->stream_type, strm1->stream_name);
1367
1368                 if (!strm2) {
1369                         /* Corresponding stream not found  */
1370                         if (stream_is_named(strm1) &&
1371                             (cmp_flags & WIMLIB_CMP_FLAG_UNIX_MODE))
1372                                 continue;
1373                         ERROR("Stream of %"TS" is missing in second image; "
1374                               "type %d, named=%d, empty=%d",
1375                               inode_any_full_path(inode1),
1376                               strm1->stream_type,
1377                               stream_is_named(strm1),
1378                               is_zero_hash(stream_hash(strm1)));
1379                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1380                 }
1381
1382                 if (!hashes_equal(stream_hash(strm1), stream_hash(strm2))) {
1383                         ERROR("Stream of %"TS" differs; type %d",
1384                               inode_any_full_path(inode1), strm1->stream_type);
1385                         return WIMLIB_ERR_IMAGES_ARE_DIFFERENT;
1386                 }
1387         }
1388
1389         /* Compare object IDs  */
1390         ret = cmp_object_ids(inode1, inode2, cmp_flags);
1391         if (ret)
1392                 return ret;
1393
1394         /* Compare standard UNIX metadata  */
1395         ret = cmp_unix_metadata(inode1, inode2, cmp_flags);
1396         if (ret)
1397                 return ret;
1398
1399         return 0;
1400 }
1401
1402 static int
1403 cmp_images(const struct wim_image_metadata *imd1,
1404            const struct wim_image_metadata *imd2, int cmp_flags)
1405 {
1406         struct wim_dentry *root1 = imd1->root_dentry;
1407         struct wim_dentry *root2 = imd2->root_dentry;
1408         const struct wim_inode *inode;
1409         int ret;
1410
1411         ret = calc_corresponding_files_recursive(root1, root2, cmp_flags);
1412         if (ret)
1413                 return ret;
1414
1415         /* Verify that the hard links match up between the two images.  */
1416         assert_inodes_sane(imd1);
1417         assert_inodes_sane(imd2);
1418         ret = for_dentry_in_tree(root1, check_hard_link, NULL);
1419         if (ret)
1420                 return ret;
1421
1422         /* Compare corresponding inodes.  */
1423         image_for_each_inode(inode, imd1) {
1424                 ret = cmp_inodes(inode, inode->i_corresponding,
1425                                  imd1, imd2, cmp_flags);
1426                 if (ret)
1427                         return ret;
1428         }
1429
1430         return 0;
1431 }
1432
1433 static int
1434 load_image(WIMStruct *wim, int image, struct wim_image_metadata **imd_ret)
1435 {
1436         int ret = select_wim_image(wim, image);
1437         if (!ret) {
1438                 *imd_ret = wim_get_current_image_metadata(wim);
1439                 mark_image_dirty(*imd_ret);
1440         }
1441         return ret;
1442 }
1443
1444 WIMLIBAPI int
1445 wimlib_compare_images(WIMStruct *wim1, int image1,
1446                       WIMStruct *wim2, int image2, int cmp_flags)
1447 {
1448         int ret;
1449         struct wim_image_metadata *imd1, *imd2;
1450
1451         ret = load_image(wim1, image1, &imd1);
1452         if (!ret)
1453                 ret = load_image(wim2, image2, &imd2);
1454         if (!ret)
1455                 ret = cmp_images(imd1, imd2, cmp_flags);
1456         return ret;
1457 }
1458
1459 #endif /* ENABLE_TEST_SUPPORT */