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