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

   1 /*
   2  * blob_table.c
   3  *
   4  * A blob table maps SHA-1 message digests to "blobs", which are nonempty
   5  * sequences of binary data.  Within a WIM file, blobs are single-instanced.
   6  *
   7  * This file also contains code to read and write the corresponding on-disk
   8  * representation of this table in the WIM file format.
   9  */
  10
  11 /*
  12  * Copyright (C) 2012, 2013, 2014, 2015 Eric Biggers
  13  *
  14  * This file is free software; you can redistribute it and/or modify it under
  15  * the terms of the GNU Lesser General Public License as published by the Free
  16  * Software Foundation; either version 3 of the License, or (at your option) any
  17  * later version.
  18  *
  19  * This file is distributed in the hope that it will be useful, but WITHOUT
  20  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  21  * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
  22  * details.
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * along with this file; if not, see http://www.gnu.org/licenses/.
  26  */
  27
  28 #ifdef HAVE_CONFIG_H
  29 #  include "config.h"
  30 #endif
  31
  32 #include <stdlib.h>
  33 #include <string.h>
  34 #include <unistd.h> /* for unlink()  */
  35
  36 #include "wimlib/assert.h"
  37 #include "wimlib/blob_table.h"
  38 #include "wimlib/encoding.h"
  39 #include "wimlib/endianness.h"
  40 #include "wimlib/error.h"
  41 #include "wimlib/metadata.h"
  42 #include "wimlib/ntfs_3g.h"
  43 #include "wimlib/resource.h"
  44 #include "wimlib/unaligned.h"
  45 #include "wimlib/util.h"
  46 #include "wimlib/write.h"
  47
  48 /* A hash table mapping SHA-1 message digests to blob descriptors  */
  49 struct blob_table {
  50         struct hlist_head *array;
  51         size_t num_blobs;
  52         size_t capacity;
  53 };
  54
  55 struct blob_table *
  56 new_blob_table(size_t capacity)
  57 {
  58         struct blob_table *table;
  59         struct hlist_head *array;
  60
  61         table = MALLOC(sizeof(struct blob_table));
  62         if (table == NULL)
  63                 goto oom;
  64
  65         array = CALLOC(capacity, sizeof(array[0]));
  66         if (array == NULL) {
  67                 FREE(table);
  68                 goto oom;
  69         }
  70
  71         table->num_blobs = 0;
  72         table->capacity = capacity;
  73         table->array = array;
  74         return table;
  75
  76 oom:
  77         ERROR("Failed to allocate memory for blob table "
  78               "with capacity %zu", capacity);
  79         return NULL;
  80 }
  81
  82 static int
  83 do_free_blob_descriptor(struct blob_descriptor *blob, void *_ignore)
  84 {
  85         free_blob_descriptor(blob);
  86         return 0;
  87 }
  88
  89 void
  90 free_blob_table(struct blob_table *table)
  91 {
  92         if (table) {
  93                 for_blob_in_table(table, do_free_blob_descriptor, NULL);
  94                 FREE(table->array);
  95                 FREE(table);
  96         }
  97 }
  98
  99 struct blob_descriptor *
 100 new_blob_descriptor(void)
 101 {
 102         BUILD_BUG_ON(BLOB_NONEXISTENT != 0);
 103         return CALLOC(1, sizeof(struct blob_descriptor));
 104 }
 105
 106 struct blob_descriptor *
 107 clone_blob_descriptor(const struct blob_descriptor *old)
 108 {
 109         struct blob_descriptor *new;
 110
 111         new = memdup(old, sizeof(struct blob_descriptor));
 112         if (new == NULL)
 113                 return NULL;
 114
 115         switch (new->blob_location) {
 116         case BLOB_IN_WIM:
 117                 list_add(&new->rdesc_node, &new->rdesc->blob_list);
 118                 break;
 119
 120         case BLOB_IN_FILE_ON_DISK:
 121 #ifdef __WIN32__
 122         case BLOB_IN_WINNT_FILE_ON_DISK:
 123         case BLOB_WIN32_ENCRYPTED:
 124 #endif
 125 #ifdef WITH_FUSE
 126         case BLOB_IN_STAGING_FILE:
 127                 BUILD_BUG_ON((void*)&old->file_on_disk !=
 128                              (void*)&old->staging_file_name);
 129 #endif
 130                 new->file_on_disk = TSTRDUP(old->file_on_disk);
 131                 if (new->file_on_disk == NULL)
 132                         goto out_free;
 133                 break;
 134         case BLOB_IN_ATTACHED_BUFFER:
 135                 new->attached_buffer = memdup(old->attached_buffer, old->size);
 136                 if (new->attached_buffer == NULL)
 137                         goto out_free;
 138                 break;
 139 #ifdef WITH_NTFS_3G
 140         case BLOB_IN_NTFS_VOLUME:
 141                 new->ntfs_loc = clone_ntfs_location(old->ntfs_loc);
 142                 if (!new->ntfs_loc)
 143                         goto out_free;
 144                 break;
 145 #endif
 146         }
 147         return new;
 148
 149 out_free:
 150         free_blob_descriptor(new);
 151         return NULL;
 152 }
 153
 154 static void
 155 blob_release_location(struct blob_descriptor *blob)
 156 {
 157         switch (blob->blob_location) {
 158         case BLOB_IN_WIM:
 159                 list_del(&blob->rdesc_node);
 160                 if (list_empty(&blob->rdesc->blob_list))
 161                         FREE(blob->rdesc);
 162                 break;
 163         case BLOB_IN_FILE_ON_DISK:
 164 #ifdef __WIN32__
 165         case BLOB_IN_WINNT_FILE_ON_DISK:
 166         case BLOB_WIN32_ENCRYPTED:
 167 #endif
 168 #ifdef WITH_FUSE
 169         case BLOB_IN_STAGING_FILE:
 170                 BUILD_BUG_ON((void*)&blob->file_on_disk !=
 171                              (void*)&blob->staging_file_name);
 172 #endif
 173         case BLOB_IN_ATTACHED_BUFFER:
 174                 BUILD_BUG_ON((void*)&blob->file_on_disk !=
 175                              (void*)&blob->attached_buffer);
 176                 FREE(blob->file_on_disk);
 177                 break;
 178 #ifdef WITH_NTFS_3G
 179         case BLOB_IN_NTFS_VOLUME:
 180                 if (blob->ntfs_loc)
 181                         free_ntfs_location(blob->ntfs_loc);
 182                 break;
 183 #endif
 184         }
 185 }
 186
 187 void
 188 free_blob_descriptor(struct blob_descriptor *blob)
 189 {
 190         if (blob) {
 191                 blob_release_location(blob);
 192                 FREE(blob);
 193         }
 194 }
 195
 196 /* Should this blob be retained even if it has no references?  */
 197 static bool
 198 should_retain_blob(const struct blob_descriptor *blob)
 199 {
 200         return blob->blob_location == BLOB_IN_WIM;
 201 }
 202
 203 static void
 204 finalize_blob(struct blob_descriptor *blob)
 205 {
 206         if (!should_retain_blob(blob))
 207                 free_blob_descriptor(blob);
 208 }
 209
 210 /*
 211  * Decrements the reference count of the specified blob, which must be either
 212  * (a) unhashed, or (b) inserted in the specified blob table.
 213  *
 214  * If the blob's reference count reaches 0, we may unlink it from @table and
 215  * free it.  However, we retain blobs with 0 reference count that originated
 216  * from WIM files (BLOB_IN_WIM).  We do this for two reasons:
 217  *
 218  * 1. This prevents information about valid blobs in a WIM file --- blobs which
 219  *    will continue to be present after appending to the WIM file --- from being
 220  *    lost merely because we dropped all references to them.
 221  *
 222  * 2. Blob reference counts we read from WIM files can't be trusted.  It's
 223  *    possible that a WIM has reference counts that are too low; WIMGAPI
 224  *    sometimes creates WIMs where this is the case.  It's also possible that
 225  *    blobs have been referenced from an external WIM; those blobs can
 226  *    potentially have any reference count at all, either lower or higher than
 227  *    would be expected for this WIM ("this WIM" meaning the owner of @table) if
 228  *    it were a standalone WIM.
 229  *
 230  * So we can't take the reference counts too seriously.  But at least, we do
 231  * recalculate by default when writing a new WIM file.
 232  */
 233 void
 234 blob_decrement_refcnt(struct blob_descriptor *blob, struct blob_table *table)
 235 {
 236         blob_subtract_refcnt(blob, table, 1);
 237 }
 238
 239 void
 240 blob_subtract_refcnt(struct blob_descriptor *blob, struct blob_table *table,
 241                      u32 count)
 242 {
 243         if (unlikely(blob->refcnt < count)) {
 244                 blob->refcnt = 0; /* See comment above  */
 245                 return;
 246         }
 247
 248         blob->refcnt -= count;
 249
 250         if (blob->refcnt != 0)
 251                 return;
 252
 253         if (blob->unhashed) {
 254                 list_del(&blob->unhashed_list);
 255         #ifdef WITH_FUSE
 256                 /* If the blob has been extracted to a staging file for a FUSE
 257                  * mount, unlink the staging file.  (Note that there still may
 258                  * be open file descriptors to it.)  */
 259                 if (blob->blob_location == BLOB_IN_STAGING_FILE)
 260                         unlinkat(blob->staging_dir_fd,
 261                                  blob->staging_file_name, 0);
 262         #endif
 263         } else {
 264                 if (!should_retain_blob(blob))
 265                         blob_table_unlink(table, blob);
 266         }
 267
 268         /* If FUSE mounts are enabled, then don't actually free the blob
 269          * descriptor until the last file descriptor to it has been closed.  */
 270 #ifdef WITH_FUSE
 271         if (blob->num_opened_fds == 0)
 272 #endif
 273                 finalize_blob(blob);
 274 }
 275
 276 #ifdef WITH_FUSE
 277 void
 278 blob_decrement_num_opened_fds(struct blob_descriptor *blob)
 279 {
 280         wimlib_assert(blob->num_opened_fds != 0);
 281
 282         if (--blob->num_opened_fds == 0 && blob->refcnt == 0)
 283                 finalize_blob(blob);
 284 }
 285 #endif
 286
 287 static void
 288 blob_table_insert_raw(struct blob_table *table, struct blob_descriptor *blob)
 289 {
 290         size_t i = blob->hash_short % table->capacity;
 291
 292         hlist_add_head(&blob->hash_list, &table->array[i]);
 293 }
 294
 295 static void
 296 enlarge_blob_table(struct blob_table *table)
 297 {
 298         size_t old_capacity, new_capacity;
 299         struct hlist_head *old_array, *new_array;
 300         struct blob_descriptor *blob;
 301         struct hlist_node *tmp;
 302         size_t i;
 303
 304         old_capacity = table->capacity;
 305         new_capacity = old_capacity * 2;
 306         new_array = CALLOC(new_capacity, sizeof(struct hlist_head));
 307         if (new_array == NULL)
 308                 return;
 309         old_array = table->array;
 310         table->array = new_array;
 311         table->capacity = new_capacity;
 312
 313         for (i = 0; i < old_capacity; i++)
 314                 hlist_for_each_entry_safe(blob, tmp, &old_array[i], hash_list)
 315                         blob_table_insert_raw(table, blob);
 316         FREE(old_array);
 317 }
 318
 319 /* Insert a blob descriptor into the blob table.  */
 320 void
 321 blob_table_insert(struct blob_table *table, struct blob_descriptor *blob)
 322 {
 323         blob_table_insert_raw(table, blob);
 324         if (++table->num_blobs > table->capacity)
 325                 enlarge_blob_table(table);
 326 }
 327
 328 /* Unlinks a blob descriptor from the blob table; does not free it.  */
 329 void
 330 blob_table_unlink(struct blob_table *table, struct blob_descriptor *blob)
 331 {
 332         wimlib_assert(!blob->unhashed);
 333         wimlib_assert(table->num_blobs != 0);
 334
 335         hlist_del(&blob->hash_list);
 336         table->num_blobs--;
 337 }
 338
 339 /* Given a SHA-1 message digest, return the corresponding blob descriptor from
 340  * the specified blob table, or NULL if there is none.  */
 341 struct blob_descriptor *
 342 lookup_blob(const struct blob_table *table, const u8 *hash)
 343 {
 344         size_t i;
 345         struct blob_descriptor *blob;
 346
 347         i = load_size_t_unaligned(hash) % table->capacity;
 348         hlist_for_each_entry(blob, &table->array[i], hash_list)
 349                 if (hashes_equal(hash, blob->hash))
 350                         return blob;
 351         return NULL;
 352 }
 353
 354 /* Call a function on all blob descriptors in the specified blob table.  Stop
 355  * early and return nonzero if any call to the function returns nonzero.  */
 356 int
 357 for_blob_in_table(struct blob_table *table,
 358                   int (*visitor)(struct blob_descriptor *, void *), void *arg)
 359 {
 360         struct blob_descriptor *blob;
 361         struct hlist_node *tmp;
 362         int ret;
 363
 364         for (size_t i = 0; i < table->capacity; i++) {
 365                 hlist_for_each_entry_safe(blob, tmp, &table->array[i],
 366                                           hash_list)
 367                 {
 368                         ret = visitor(blob, arg);
 369                         if (ret)
 370                                 return ret;
 371                 }
 372         }
 373         return 0;
 374 }
 375
 376 /*
 377  * This is a qsort() callback that sorts blobs into an order optimized for
 378  * reading.  Sorting is done primarily by blob location, then secondarily by a
 379  * location-dependent order.  For example, blobs in WIM resources are sorted
 380  * such that the underlying WIM files will be read sequentially.  This is
 381  * especially important for WIM files containing solid resources.
 382  */
 383 int
 384 cmp_blobs_by_sequential_order(const void *p1, const void *p2)
 385 {
 386         const struct blob_descriptor *blob1, *blob2;
 387         int v;
 388         WIMStruct *wim1, *wim2;
 389
 390         blob1 = *(const struct blob_descriptor**)p1;
 391         blob2 = *(const struct blob_descriptor**)p2;
 392
 393         v = (int)blob1->blob_location - (int)blob2->blob_location;
 394
 395         /* Different locations?  */
 396         if (v)
 397                 return v;
 398
 399         switch (blob1->blob_location) {
 400         case BLOB_IN_WIM:
 401                 wim1 = blob1->rdesc->wim;
 402                 wim2 = blob2->rdesc->wim;
 403
 404                 /* Different (possibly split) WIMs?  */
 405                 if (wim1 != wim2) {
 406                         v = cmp_guids(wim1->hdr.guid, wim2->hdr.guid);
 407                         if (v)
 408                                 return v;
 409                 }
 410
 411                 /* Different part numbers in the same WIM?  */
 412                 v = (int)wim1->hdr.part_number - (int)wim2->hdr.part_number;
 413                 if (v)
 414                         return v;
 415
 416                 if (blob1->rdesc->offset_in_wim != blob2->rdesc->offset_in_wim)
 417                         return cmp_u64(blob1->rdesc->offset_in_wim,
 418                                        blob2->rdesc->offset_in_wim);
 419
 420                 return cmp_u64(blob1->offset_in_res, blob2->offset_in_res);
 421
 422         case BLOB_IN_FILE_ON_DISK:
 423 #ifdef WITH_FUSE
 424         case BLOB_IN_STAGING_FILE:
 425 #endif
 426 #ifdef __WIN32__
 427         case BLOB_IN_WINNT_FILE_ON_DISK:
 428         case BLOB_WIN32_ENCRYPTED:
 429                 /* Windows: compare by starting LCN (logical cluster number)  */
 430                 v = cmp_u64(blob1->sort_key, blob2->sort_key);
 431                 if (v)
 432                         return v;
 433 #endif
 434                 /* Compare files by path: just a heuristic that will place files
 435                  * in the same directory next to each other.  */
 436                 return tstrcmp(blob1->file_on_disk, blob2->file_on_disk);
 437 #ifdef WITH_NTFS_3G
 438         case BLOB_IN_NTFS_VOLUME:
 439                 return cmp_ntfs_locations(blob1->ntfs_loc, blob2->ntfs_loc);
 440 #endif
 441         default:
 442                 /* No additional sorting order defined for this resource
 443                  * location (e.g. BLOB_IN_ATTACHED_BUFFER); simply compare
 444                  * everything equal to each other.  */
 445                 return 0;
 446         }
 447 }
 448
 449 int
 450 sort_blob_list(struct list_head *blob_list, size_t list_head_offset,
 451                int (*compar)(const void *, const void*))
 452 {
 453         struct list_head *cur;
 454         struct blob_descriptor **array;
 455         size_t i;
 456         size_t array_size;
 457         size_t num_blobs = 0;
 458
 459         list_for_each(cur, blob_list)
 460                 num_blobs++;
 461
 462         if (num_blobs <= 1)
 463                 return 0;
 464
 465         array_size = num_blobs * sizeof(array[0]);
 466         array = MALLOC(array_size);
 467         if (array == NULL)
 468                 return WIMLIB_ERR_NOMEM;
 469
 470         cur = blob_list->next;
 471         for (i = 0; i < num_blobs; i++) {
 472                 array[i] = (struct blob_descriptor*)((u8*)cur - list_head_offset);
 473                 cur = cur->next;
 474         }
 475
 476         qsort(array, num_blobs, sizeof(array[0]), compar);
 477
 478         INIT_LIST_HEAD(blob_list);
 479         for (i = 0; i < num_blobs; i++) {
 480                 list_add_tail((struct list_head*)
 481                                ((u8*)array[i] + list_head_offset), blob_list);
 482         }
 483         FREE(array);
 484         return 0;
 485 }
 486
 487 /* Sort the specified list of blobs in an order optimized for sequential
 488  * reading.  */
 489 int
 490 sort_blob_list_by_sequential_order(struct list_head *blob_list,
 491                                    size_t list_head_offset)
 492 {
 493         return sort_blob_list(blob_list, list_head_offset,
 494                               cmp_blobs_by_sequential_order);
 495 }
 496
 497 static int
 498 add_blob_to_array(struct blob_descriptor *blob, void *_pp)
 499 {
 500         struct blob_descriptor ***pp = _pp;
 501         *(*pp)++ = blob;
 502         return 0;
 503 }
 504
 505 /* Iterate through the blob descriptors in the specified blob table in an order
 506  * optimized for sequential reading.  */
 507 int
 508 for_blob_in_table_sorted_by_sequential_order(struct blob_table *table,
 509                                              int (*visitor)(struct blob_descriptor *, void *),
 510                                              void *arg)
 511 {
 512         struct blob_descriptor **blob_array, **p;
 513         size_t num_blobs = table->num_blobs;
 514         int ret;
 515
 516         blob_array = MALLOC(num_blobs * sizeof(blob_array[0]));
 517         if (!blob_array)
 518                 return WIMLIB_ERR_NOMEM;
 519         p = blob_array;
 520         for_blob_in_table(table, add_blob_to_array, &p);
 521
 522         wimlib_assert(p == blob_array + num_blobs);
 523
 524         qsort(blob_array, num_blobs, sizeof(blob_array[0]),
 525               cmp_blobs_by_sequential_order);
 526         ret = 0;
 527         for (size_t i = 0; i < num_blobs; i++) {
 528                 ret = visitor(blob_array[i], arg);
 529                 if (ret)
 530                         break;
 531         }
 532         FREE(blob_array);
 533         return ret;
 534 }
 535
 536 /* On-disk format of a blob descriptor in a WIM file.
 537  *
 538  * Note: if the WIM file contains solid resource(s), then this structure is
 539  * sometimes overloaded to describe a "resource" rather than a "blob".  See the
 540  * code for details.  */
 541 struct blob_descriptor_disk {
 542
 543         /* Size, offset, and flags of the blob.  */
 544         struct wim_reshdr_disk reshdr;
 545
 546         /* Which part of the split WIM this blob is in; indexed from 1. */
 547         le16 part_number;
 548
 549         /* Reference count of this blob over all WIM images.  (But see comment
 550          * above blob_decrement_refcnt().)  */
 551         le32 refcnt;
 552
 553         /* SHA-1 message digest of the uncompressed data of this blob, or all
 554          * zeroes if this blob is of zero length.  */
 555         u8 hash[SHA1_HASH_SIZE];
 556 } _packed_attribute;
 557
 558 /* Given a nonempty run of consecutive blob descriptors with the SOLID flag set,
 559  * count how many specify resources (as opposed to blobs within those
 560  * resources).
 561  *
 562  * Returns the resulting count.  */
 563 static size_t
 564 count_solid_resources(const struct blob_descriptor_disk *entries, size_t max)
 565 {
 566         size_t count = 0;
 567         do {
 568                 struct wim_reshdr reshdr;
 569
 570                 get_wim_reshdr(&(entries++)->reshdr, &reshdr);
 571
 572                 if (!(reshdr.flags & WIM_RESHDR_FLAG_SOLID)) {
 573                         /* Run was terminated by a stand-alone blob entry.  */
 574                         break;
 575                 }
 576
 577                 if (reshdr.uncompressed_size == SOLID_RESOURCE_MAGIC_NUMBER) {
 578                         /* This is a resource entry.  */
 579                         count++;
 580                 }
 581         } while (--max);
 582         return count;
 583 }
 584
 585 /*
 586  * Given a run of consecutive blob descriptors with the SOLID flag set and
 587  * having @num_rdescs resource entries, load resource information from them into
 588  * the resource descriptors in the @rdescs array.
 589  *
 590  * Returns 0 on success, or a nonzero error code on failure.
 591  */
 592 static int
 593 do_load_solid_info(WIMStruct *wim, struct wim_resource_descriptor **rdescs,
 594                    size_t num_rdescs,
 595                    const struct blob_descriptor_disk *entries)
 596 {
 597         for (size_t i = 0; i < num_rdescs; i++) {
 598                 struct wim_reshdr reshdr;
 599                 struct alt_chunk_table_header_disk hdr;
 600                 struct wim_resource_descriptor *rdesc;
 601                 int ret;
 602
 603                 /* Advance to next resource entry.  */
 604
 605                 do {
 606                         get_wim_reshdr(&(entries++)->reshdr, &reshdr);
 607                 } while (reshdr.uncompressed_size != SOLID_RESOURCE_MAGIC_NUMBER);
 608
 609                 rdesc = rdescs[i];
 610
 611                 wim_reshdr_to_desc(&reshdr, wim, rdesc);
 612
 613                 /* For solid resources, the uncompressed size, compression type,
 614                  * and chunk size are stored in the resource itself, not in the
 615                  * blob table.  */
 616
 617                 ret = full_pread(&wim->in_fd, &hdr,
 618                                  sizeof(hdr), reshdr.offset_in_wim);
 619                 if (ret) {
 620                         ERROR("Failed to read header of solid resource "
 621                               "(offset_in_wim=%"PRIu64")",
 622                               reshdr.offset_in_wim);
 623                         return ret;
 624                 }
 625
 626                 rdesc->uncompressed_size = le64_to_cpu(hdr.res_usize);
 627
 628                 /* Compression format numbers must be the same as in
 629                  * WIMGAPI to be compatible here.  */
 630                 BUILD_BUG_ON(WIMLIB_COMPRESSION_TYPE_NONE != 0);
 631                 BUILD_BUG_ON(WIMLIB_COMPRESSION_TYPE_XPRESS != 1);
 632                 BUILD_BUG_ON(WIMLIB_COMPRESSION_TYPE_LZX != 2);
 633                 BUILD_BUG_ON(WIMLIB_COMPRESSION_TYPE_LZMS != 3);
 634                 rdesc->compression_type = le32_to_cpu(hdr.compression_format);
 635
 636                 rdesc->chunk_size = le32_to_cpu(hdr.chunk_size);
 637
 638                 DEBUG("Solid resource %zu/%zu: %"PRIu64" => %"PRIu64" "
 639                       "(%"TS"/%"PRIu32") @ +%"PRIu64"",
 640                       i + 1, num_rdescs,
 641                       rdesc->uncompressed_size,
 642                       rdesc->size_in_wim,
 643                       wimlib_get_compression_type_string(rdesc->compression_type),
 644                       rdesc->chunk_size,
 645                       rdesc->offset_in_wim);
 646         }
 647         return 0;
 648 }
 649
 650 /*
 651  * Given a nonempty run of consecutive blob descriptors with the SOLID flag set,
 652  * allocate a 'struct wim_resource_descriptor' for each resource within that
 653  * run.
 654  *
 655  * Returns 0 on success, or a nonzero error code on failure.
 656  * Returns the pointers and count in *rdescs_ret and *num_rdescs_ret.
 657  */
 658 static int
 659 load_solid_info(WIMStruct *wim,
 660                 const struct blob_descriptor_disk *entries,
 661                 size_t num_remaining_entries,
 662                 struct wim_resource_descriptor ***rdescs_ret,
 663                 size_t *num_rdescs_ret)
 664 {
 665         size_t num_rdescs;
 666         struct wim_resource_descriptor **rdescs;
 667         size_t i;
 668         int ret;
 669
 670         num_rdescs = count_solid_resources(entries, num_remaining_entries);
 671         rdescs = CALLOC(num_rdescs, sizeof(rdescs[0]));
 672         if (!rdescs)
 673                 return WIMLIB_ERR_NOMEM;
 674
 675         for (i = 0; i < num_rdescs; i++) {
 676                 rdescs[i] = MALLOC(sizeof(struct wim_resource_descriptor));
 677                 if (!rdescs[i]) {
 678                         ret = WIMLIB_ERR_NOMEM;
 679                         goto out_free_rdescs;
 680                 }
 681         }
 682
 683         ret = do_load_solid_info(wim, rdescs, num_rdescs, entries);
 684         if (ret)
 685                 goto out_free_rdescs;
 686
 687         *rdescs_ret = rdescs;
 688         *num_rdescs_ret = num_rdescs;
 689         return 0;
 690
 691 out_free_rdescs:
 692         for (i = 0; i < num_rdescs; i++)
 693                 FREE(rdescs[i]);
 694         FREE(rdescs);
 695         return ret;
 696 }
 697
 698 /* Given a 'struct blob_descriptor' allocated for an on-disk blob descriptor
 699  * with the SOLID flag set, try to assign it to resource in the current solid
 700  * run.  */
 701 static int
 702 assign_blob_to_solid_resource(const struct wim_reshdr *reshdr,
 703                               struct blob_descriptor *blob,
 704                               struct wim_resource_descriptor **rdescs,
 705                               size_t num_rdescs)
 706 {
 707         u64 offset = reshdr->offset_in_wim;
 708
 709         /* XXX: This linear search will be slow in the degenerate case where the
 710          * number of solid resources in the run is huge.  */
 711         blob->size = reshdr->size_in_wim;
 712         for (size_t i = 0; i < num_rdescs; i++) {
 713                 if (offset + blob->size <= rdescs[i]->uncompressed_size) {
 714                         blob_set_is_located_in_wim_resource(blob, rdescs[i], offset);
 715                         return 0;
 716                 }
 717                 offset -= rdescs[i]->uncompressed_size;
 718         }
 719         ERROR("blob could not be assigned to a solid resource");
 720         return WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
 721 }
 722
 723 static void
 724 free_solid_rdescs(struct wim_resource_descriptor **rdescs, size_t num_rdescs)
 725 {
 726         if (rdescs) {
 727                 for (size_t i = 0; i < num_rdescs; i++)
 728                         if (list_empty(&rdescs[i]->blob_list))
 729                                 FREE(rdescs[i]);
 730                 FREE(rdescs);
 731         }
 732 }
 733
 734 static int
 735 cmp_blobs_by_offset_in_res(const void *p1, const void *p2)
 736 {
 737         const struct blob_descriptor *blob1, *blob2;
 738
 739         blob1 = *(const struct blob_descriptor**)p1;
 740         blob2 = *(const struct blob_descriptor**)p2;
 741
 742         return cmp_u64(blob1->offset_in_res, blob2->offset_in_res);
 743 }
 744
 745 /* Validate the size and location of a WIM resource.  */
 746 static int
 747 validate_resource(struct wim_resource_descriptor *rdesc)
 748 {
 749         struct blob_descriptor *blob;
 750         bool out_of_order;
 751         u64 expected_next_offset;
 752         int ret;
 753
 754         /* Verify that the resource itself has a valid offset and size.  */
 755         if (rdesc->offset_in_wim + rdesc->size_in_wim < rdesc->size_in_wim)
 756                 goto invalid_due_to_overflow;
 757
 758         /* Verify that each blob in the resource has a valid offset and size.
 759          */
 760         expected_next_offset = 0;
 761         out_of_order = false;
 762         list_for_each_entry(blob, &rdesc->blob_list, rdesc_node) {
 763                 if (blob->offset_in_res + blob->size < blob->size ||
 764                     blob->offset_in_res + blob->size > rdesc->uncompressed_size)
 765                         goto invalid_due_to_overflow;
 766
 767                 if (blob->offset_in_res >= expected_next_offset)
 768                         expected_next_offset = blob->offset_in_res + blob->size;
 769                 else
 770                         out_of_order = true;
 771         }
 772
 773         /* If the blobs were not located at strictly increasing positions (not
 774          * allowing for overlap), sort them.  Then make sure that none overlap.
 775          */
 776         if (out_of_order) {
 777                 ret = sort_blob_list(&rdesc->blob_list,
 778                                      offsetof(struct blob_descriptor,
 779                                               rdesc_node),
 780                                      cmp_blobs_by_offset_in_res);
 781                 if (ret)
 782                         return ret;
 783
 784                 expected_next_offset = 0;
 785                 list_for_each_entry(blob, &rdesc->blob_list, rdesc_node) {
 786                         if (blob->offset_in_res >= expected_next_offset)
 787                                 expected_next_offset = blob->offset_in_res + blob->size;
 788                         else
 789                                 goto invalid_due_to_overlap;
 790                 }
 791         }
 792
 793         return 0;
 794
 795 invalid_due_to_overflow:
 796         ERROR("Invalid blob table (offset overflow)");
 797         return WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
 798
 799 invalid_due_to_overlap:
 800         ERROR("Invalid blob table (blobs in solid resource overlap)");
 801         return WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
 802 }
 803
 804 static int
 805 finish_solid_rdescs(struct wim_resource_descriptor **rdescs, size_t num_rdescs)
 806 {
 807         int ret = 0;
 808         for (size_t i = 0; i < num_rdescs; i++) {
 809                 ret = validate_resource(rdescs[i]);
 810                 if (ret)
 811                         break;
 812         }
 813         free_solid_rdescs(rdescs, num_rdescs);
 814         return ret;
 815 }
 816
 817 /*
 818  * read_blob_table() -
 819  *
 820  * Read the blob table from a WIM file.  Usually, each entry in this table
 821  * describes a "blob", or equivalently a "resource", that the WIM file contains,
 822  * along with its location and SHA-1 message digest.  Descriptors for
 823  * non-metadata blobs will be saved in the in-memory blob table
 824  * (wim->blob_table), whereas descriptors for metadata blobs will be saved in a
 825  * special location per-image (the wim->image_metadata array).
 826  *
 827  * However, in WIM_VERSION_SOLID (3584) WIMs, a resource may contain multiple
 828  * blobs that are compressed together.  Such a resource is called a "solid
 829  * resource".  Solid resources are still described in the on-disk "blob table",
 830  * although the format is not the most logical.  A consecutive sequence of
 831  * entries that all have flag WIM_RESHDR_FLAG_SOLID (0x10) set is a "solid run".
 832  * A solid run describes a set of solid resources, each of which contains a set
 833  * of blobs.  In a solid run, a 'struct wim_reshdr_disk' with 'uncompressed_size
 834  * = SOLID_RESOURCE_MAGIC_NUMBER (0x100000000)' specifies a solid resource,
 835  * whereas any other 'struct wim_reshdr_disk' specifies a blob within a solid
 836  * resource.  There are some oddities in how we need to determine which solid
 837  * resource a blob is actually in; see the code for details.
 838  *
 839  * Possible return values:
 840  *      WIMLIB_ERR_SUCCESS (0)
 841  *      WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY
 842  *      WIMLIB_ERR_NOMEM
 843  *
 844  *      Or an error code caused by failure to read the blob table from the WIM
 845  *      file.
 846  */
 847 int
 848 read_blob_table(WIMStruct *wim)
 849 {
 850         int ret;
 851         size_t num_entries;
 852         void *buf = NULL;
 853         struct blob_table *table = NULL;
 854         struct blob_descriptor *cur_blob = NULL;
 855         size_t num_duplicate_blobs = 0;
 856         size_t num_empty_blobs = 0;
 857         size_t num_wrong_part_blobs = 0;
 858         u32 image_index = 0;
 859         struct wim_resource_descriptor **cur_solid_rdescs = NULL;
 860         size_t cur_num_solid_rdescs = 0;
 861
 862         DEBUG("Reading blob table.");
 863
 864         /* Calculate the number of entries in the blob table.  */
 865         num_entries = wim->hdr.blob_table_reshdr.uncompressed_size /
 866                       sizeof(struct blob_descriptor_disk);
 867
 868         /* Read the blob table into a buffer.  */
 869         ret = wim_reshdr_to_data(&wim->hdr.blob_table_reshdr, wim, &buf);
 870         if (ret)
 871                 goto out;
 872
 873         /* Allocate a hash table to map SHA-1 message digests into blob
 874          * descriptors.  This is the in-memory "blob table".  */
 875         table = new_blob_table(num_entries * 2 + 1);
 876         if (!table)
 877                 goto oom;
 878
 879         /* Allocate and initalize blob descriptors from the raw blob table
 880          * buffer.  */
 881         for (size_t i = 0; i < num_entries; i++) {
 882                 const struct blob_descriptor_disk *disk_entry =
 883                         &((const struct blob_descriptor_disk*)buf)[i];
 884                 struct wim_reshdr reshdr;
 885                 u16 part_number;
 886
 887                 /* Get the resource header  */
 888                 get_wim_reshdr(&disk_entry->reshdr, &reshdr);
 889
 890                 DEBUG("reshdr: size_in_wim=%"PRIu64", "
 891                       "uncompressed_size=%"PRIu64", "
 892                       "offset_in_wim=%"PRIu64", "
 893                       "flags=0x%02x",
 894                       reshdr.size_in_wim, reshdr.uncompressed_size,
 895                       reshdr.offset_in_wim, reshdr.flags);
 896
 897                 /* Ignore SOLID flag if it isn't supposed to be used in this WIM
 898                  * version.  */
 899                 if (wim->hdr.wim_version == WIM_VERSION_DEFAULT)
 900                         reshdr.flags &= ~WIM_RESHDR_FLAG_SOLID;
 901
 902                 /* Allocate a new 'struct blob_descriptor'.  */
 903                 cur_blob = new_blob_descriptor();
 904                 if (!cur_blob)
 905                         goto oom;
 906
 907                 /* Get the part number, reference count, and hash.  */
 908                 part_number = le16_to_cpu(disk_entry->part_number);
 909                 cur_blob->refcnt = le32_to_cpu(disk_entry->refcnt);
 910                 copy_hash(cur_blob->hash, disk_entry->hash);
 911
 912                 if (reshdr.flags & WIM_RESHDR_FLAG_SOLID) {
 913
 914                         /* SOLID entry  */
 915
 916                         if (!cur_solid_rdescs) {
 917                                 /* Starting new run  */
 918                                 ret = load_solid_info(wim, disk_entry,
 919                                                       num_entries - i,
 920                                                       &cur_solid_rdescs,
 921                                                       &cur_num_solid_rdescs);
 922                                 if (ret)
 923                                         goto out;
 924                         }
 925
 926                         if (reshdr.uncompressed_size == SOLID_RESOURCE_MAGIC_NUMBER) {
 927                                 /* Resource entry, not blob entry  */
 928                                 goto free_cur_blob_and_continue;
 929                         }
 930
 931                         /* Blob entry  */
 932
 933                         ret = assign_blob_to_solid_resource(&reshdr,
 934                                                             cur_blob,
 935                                                             cur_solid_rdescs,
 936                                                             cur_num_solid_rdescs);
 937                         if (ret)
 938                                 goto out;
 939
 940                 } else {
 941                         /* Normal blob/resource entry; SOLID not set.  */
 942
 943                         struct wim_resource_descriptor *rdesc;
 944
 945                         if (unlikely(cur_solid_rdescs)) {
 946                                 /* This entry terminated a solid run.  */
 947                                 ret = finish_solid_rdescs(cur_solid_rdescs,
 948                                                           cur_num_solid_rdescs);
 949                                 cur_solid_rdescs = NULL;
 950                                 if (ret)
 951                                         goto out;
 952                         }
 953
 954                         if (unlikely(!(reshdr.flags & WIM_RESHDR_FLAG_COMPRESSED) &&
 955                                      (reshdr.size_in_wim != reshdr.uncompressed_size)))
 956                         {
 957                                 ERROR("Uncompressed resource has "
 958                                       "size_in_wim != uncompressed_size");
 959                                 ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
 960                                 goto out;
 961                         }
 962
 963                         /* Set up a resource descriptor for this blob.  */
 964
 965                         rdesc = MALLOC(sizeof(struct wim_resource_descriptor));
 966                         if (!rdesc)
 967                                 goto oom;
 968
 969                         wim_reshdr_to_desc_and_blob(&reshdr, wim, rdesc, cur_blob);
 970                 }
 971
 972                 /* cur_blob is now a blob bound to a resource.  */
 973
 974                 /* Ignore entries with all zeroes in the hash field.  */
 975                 if (unlikely(is_zero_hash(cur_blob->hash)))
 976                         goto free_cur_blob_and_continue;
 977
 978                 /* Verify that the blob has nonzero size.  */
 979                 if (unlikely(cur_blob->size == 0)) {
 980                         num_empty_blobs++;
 981                         goto free_cur_blob_and_continue;
 982                 }
 983
 984                 /* Verify that the part number matches that of the underlying
 985                  * WIM file.  */
 986                 if (unlikely(part_number != wim->hdr.part_number)) {
 987                         num_wrong_part_blobs++;
 988                         goto free_cur_blob_and_continue;
 989                 }
 990
 991                 if (reshdr.flags & WIM_RESHDR_FLAG_METADATA) {
 992
 993                         cur_blob->is_metadata = 1;
 994
 995                         /* Blob table entry for a metadata resource.  */
 996
 997                         /* Metadata entries with no references must be ignored.
 998                          * See, for example, the WinPE WIMs from the WAIK v2.1.
 999                          */
1000                         if (cur_blob->refcnt == 0)
1001                                 goto free_cur_blob_and_continue;
1002
1003                         if (cur_blob->refcnt != 1) {
1004                                 /* We don't currently support this case due to
1005                                  * the complications of multiple images sharing
1006                                  * the same metadata resource or a metadata
1007                                  * resource also being referenced by files.  */
1008                                 ERROR("Found metadata resource with refcnt != 1");
1009                                 ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
1010                                 goto out;
1011                         }
1012
1013                         if (reshdr.flags & WIM_RESHDR_FLAG_SOLID) {
1014                                 ERROR("Image metadata in solid resources "
1015                                       "is unsupported.");
1016                                 ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
1017                                 goto out;
1018                         }
1019
1020                         if (wim->hdr.part_number != 1) {
1021                                 WARNING("Ignoring metadata resource found in a "
1022                                         "non-first part of the split WIM");
1023                                 goto free_cur_blob_and_continue;
1024                         }
1025
1026                         /* The number of entries in the blob table with
1027                          * WIM_RESHDR_FLAG_METADATA set should be the same as
1028                          * the image_count field in the WIM header.  */
1029                         if (image_index == wim->hdr.image_count) {
1030                                 WARNING("Found more metadata resources than images");
1031                                 goto free_cur_blob_and_continue;
1032                         }
1033
1034                         /* Notice very carefully:  We are assigning the metadata
1035                          * resources to images in the same order in which their
1036                          * blob table entries occur on disk.  (This is also the
1037                          * behavior of Microsoft's software.)  In particular,
1038                          * this overrides the actual locations of the metadata
1039                          * resources themselves in the WIM file as well as any
1040                          * information written in the XML data.  */
1041                         DEBUG("Found metadata resource for image %"PRIu32" at "
1042                               "offset %"PRIu64".",
1043                               image_index + 1,
1044                               reshdr.offset_in_wim);
1045
1046                         wim->image_metadata[image_index++]->metadata_blob = cur_blob;
1047                 } else {
1048                         /* Blob table entry for a non-metadata blob.  */
1049
1050                         /* Ignore this blob if it's a duplicate.  */
1051                         if (lookup_blob(table, cur_blob->hash)) {
1052                                 num_duplicate_blobs++;
1053                                 goto free_cur_blob_and_continue;
1054                         }
1055
1056                         /* Insert the blob into the in-memory blob table, keyed
1057                          * by its SHA-1 message digest.  */
1058                         blob_table_insert(table, cur_blob);
1059                 }
1060
1061                 continue;
1062
1063         free_cur_blob_and_continue:
1064                 if (cur_solid_rdescs &&
1065                     cur_blob->blob_location == BLOB_IN_WIM)
1066                         blob_unset_is_located_in_wim_resource(cur_blob);
1067                 free_blob_descriptor(cur_blob);
1068         }
1069         cur_blob = NULL;
1070
1071         if (cur_solid_rdescs) {
1072                 /* End of blob table terminated a solid run.  */
1073                 ret = finish_solid_rdescs(cur_solid_rdescs, cur_num_solid_rdescs);
1074                 cur_solid_rdescs = NULL;
1075                 if (ret)
1076                         goto out;
1077         }
1078
1079         if (wim->hdr.part_number == 1 && image_index != wim->hdr.image_count) {
1080                 WARNING("Could not find metadata resources for all images");
1081                 for (u32 i = image_index; i < wim->hdr.image_count; i++)
1082                         put_image_metadata(wim->image_metadata[i], NULL);
1083                 wim->hdr.image_count = image_index;
1084         }
1085
1086         if (num_duplicate_blobs > 0)
1087                 WARNING("Ignoring %zu duplicate blobs", num_duplicate_blobs);
1088
1089         if (num_empty_blobs > 0)
1090                 WARNING("Ignoring %zu empty blobs", num_empty_blobs);
1091
1092         if (num_wrong_part_blobs > 0) {
1093                 WARNING("Ignoring %zu blobs with wrong part number",
1094                         num_wrong_part_blobs);
1095         }
1096
1097         DEBUG("Done reading blob table.");
1098         wim->blob_table = table;
1099         ret = 0;
1100         goto out_free_buf;
1101
1102 oom:
1103         ERROR("Not enough memory to read blob table!");
1104         ret = WIMLIB_ERR_NOMEM;
1105 out:
1106         free_solid_rdescs(cur_solid_rdescs, cur_num_solid_rdescs);
1107         free_blob_descriptor(cur_blob);
1108         free_blob_table(table);
1109 out_free_buf:
1110         FREE(buf);
1111         return ret;
1112 }
1113
1114 static void
1115 write_blob_descriptor(struct blob_descriptor_disk *disk_entry,
1116                       const struct wim_reshdr *out_reshdr,
1117                       u16 part_number, u32 refcnt, const u8 *hash)
1118 {
1119         put_wim_reshdr(out_reshdr, &disk_entry->reshdr);
1120         disk_entry->part_number = cpu_to_le16(part_number);
1121         disk_entry->refcnt = cpu_to_le32(refcnt);
1122         copy_hash(disk_entry->hash, hash);
1123 }
1124
1125 /* Note: the list of blob descriptors must be sorted so that all entries for the
1126  * same solid resource are consecutive.  In addition, blob descriptors for
1127  * metadata resources must be in the same order as the indices of the underlying
1128  * images.  */
1129 int
1130 write_blob_table_from_blob_list(struct list_head *blob_list,
1131                                 struct filedes *out_fd,
1132                                 u16 part_number,
1133                                 struct wim_reshdr *out_reshdr,
1134                                 int write_resource_flags)
1135 {
1136         size_t table_size;
1137         struct blob_descriptor *blob;
1138         struct blob_descriptor_disk *table_buf;
1139         struct blob_descriptor_disk *table_buf_ptr;
1140         int ret;
1141         u64 prev_res_offset_in_wim = ~0ULL;
1142         u64 prev_uncompressed_size;
1143         u64 logical_offset;
1144
1145         table_size = 0;
1146         list_for_each_entry(blob, blob_list, blob_table_list) {
1147                 table_size += sizeof(struct blob_descriptor_disk);
1148
1149                 if (blob->out_reshdr.flags & WIM_RESHDR_FLAG_SOLID &&
1150                     blob->out_res_offset_in_wim != prev_res_offset_in_wim)
1151                 {
1152                         table_size += sizeof(struct blob_descriptor_disk);
1153                         prev_res_offset_in_wim = blob->out_res_offset_in_wim;
1154                 }
1155         }
1156
1157         DEBUG("Writing WIM blob table (size=%zu, offset=%"PRIu64")",
1158               table_size, out_fd->offset);
1159
1160         table_buf = MALLOC(table_size);
1161         if (table_buf == NULL) {
1162                 ERROR("Failed to allocate %zu bytes for temporary blob table",
1163                       table_size);
1164                 return WIMLIB_ERR_NOMEM;
1165         }
1166         table_buf_ptr = table_buf;
1167
1168         prev_res_offset_in_wim = ~0ULL;
1169         prev_uncompressed_size = 0;
1170         logical_offset = 0;
1171         list_for_each_entry(blob, blob_list, blob_table_list) {
1172                 if (blob->out_reshdr.flags & WIM_RESHDR_FLAG_SOLID) {
1173                         struct wim_reshdr tmp_reshdr;
1174
1175                         /* Eww.  When WIMGAPI sees multiple solid resources, it
1176                          * expects the offsets to be adjusted as if there were
1177                          * really only one solid resource.  */
1178
1179                         if (blob->out_res_offset_in_wim != prev_res_offset_in_wim) {
1180                                 /* Put the resource entry for solid resource  */
1181                                 tmp_reshdr.offset_in_wim = blob->out_res_offset_in_wim;
1182                                 tmp_reshdr.size_in_wim = blob->out_res_size_in_wim;
1183                                 tmp_reshdr.uncompressed_size = SOLID_RESOURCE_MAGIC_NUMBER;
1184                                 tmp_reshdr.flags = WIM_RESHDR_FLAG_SOLID;
1185
1186                                 write_blob_descriptor(table_buf_ptr++, &tmp_reshdr,
1187                                                       part_number, 1, zero_hash);
1188
1189                                 logical_offset += prev_uncompressed_size;
1190
1191                                 prev_res_offset_in_wim = blob->out_res_offset_in_wim;
1192                                 prev_uncompressed_size = blob->out_res_uncompressed_size;
1193                         }
1194                         tmp_reshdr = blob->out_reshdr;
1195                         tmp_reshdr.offset_in_wim += logical_offset;
1196                         write_blob_descriptor(table_buf_ptr++, &tmp_reshdr,
1197                                               part_number, blob->out_refcnt, blob->hash);
1198                 } else {
1199                         write_blob_descriptor(table_buf_ptr++, &blob->out_reshdr,
1200                                               part_number, blob->out_refcnt, blob->hash);
1201                 }
1202
1203         }
1204         wimlib_assert((u8*)table_buf_ptr - (u8*)table_buf == table_size);
1205
1206         /* Write the blob table uncompressed.  Although wimlib can handle a
1207          * compressed blob table, MS software cannot.  */
1208         ret = write_wim_resource_from_buffer(table_buf,
1209                                              table_size,
1210                                              true,
1211                                              out_fd,
1212                                              WIMLIB_COMPRESSION_TYPE_NONE,
1213                                              0,
1214                                              out_reshdr,
1215                                              NULL,
1216                                              write_resource_flags);
1217         FREE(table_buf);
1218         DEBUG("ret=%d", ret);
1219         return ret;
1220 }
1221
1222 /* Allocate a blob descriptor for the contents of the buffer, or re-use an
1223  * existing descriptor in @blob_table for an identical blob.  */
1224 struct blob_descriptor *
1225 new_blob_from_data_buffer(const void *buffer, size_t size,
1226                           struct blob_table *blob_table)
1227 {
1228         u8 hash[SHA1_HASH_SIZE];
1229         struct blob_descriptor *blob;
1230         void *buffer_copy;
1231
1232         sha1_buffer(buffer, size, hash);
1233
1234         blob = lookup_blob(blob_table, hash);
1235         if (blob)
1236                 return blob;
1237
1238         blob = new_blob_descriptor();
1239         if (!blob)
1240                 return NULL;
1241
1242         buffer_copy = memdup(buffer, size);
1243         if (!buffer_copy) {
1244                 free_blob_descriptor(blob);
1245                 return NULL;
1246         }
1247         blob_set_is_located_in_attached_buffer(blob, buffer_copy, size);
1248         copy_hash(blob->hash, hash);
1249         blob_table_insert(blob_table, blob);
1250         return blob;
1251 }
1252
1253 struct blob_descriptor *
1254 after_blob_hashed(struct blob_descriptor *blob,
1255                   struct blob_descriptor **back_ptr,
1256                   struct blob_table *blob_table)
1257 {
1258         struct blob_descriptor *duplicate_blob;
1259
1260         list_del(&blob->unhashed_list);
1261         blob->unhashed = 0;
1262
1263         /* Look for a duplicate blob  */
1264         duplicate_blob = lookup_blob(blob_table, blob->hash);
1265         if (duplicate_blob) {
1266                 /* We have a duplicate blob.  Transfer the reference counts from
1267                  * this blob to the duplicate and update the reference to this
1268                  * blob (from a stream) to point to the duplicate.  The caller
1269                  * is responsible for freeing @blob if needed.  */
1270                 wimlib_assert(duplicate_blob->size == blob->size);
1271                 duplicate_blob->refcnt += blob->refcnt;
1272                 blob->refcnt = 0;
1273                 *back_ptr = duplicate_blob;
1274                 return duplicate_blob;
1275         } else {
1276                 /* No duplicate blob, so we need to insert this blob into the
1277                  * blob table and treat it as a hashed blob.  */
1278                 blob_table_insert(blob_table, blob);
1279                 return blob;
1280         }
1281 }
1282
1283 /*
1284  * Calculate the SHA-1 message digest of a blob and move its descriptor from the
1285  * list of unhashed blobs to the blob table, possibly joining it with an
1286  * identical blob.
1287  *
1288  * @blob:
1289  *      The blob to hash
1290  * @blob_table:
1291  *      The blob table in which the blob needs to be indexed
1292  * @blob_ret:
1293  *      On success, a pointer to the resulting blob descriptor is written to
1294  *      this location.  This will be the same as @blob if it was inserted into
1295  *      the blob table, or different if a duplicate blob was found.
1296  *
1297  * Returns 0 on success; nonzero if there is an error reading the blob data.
1298  */
1299 int
1300 hash_unhashed_blob(struct blob_descriptor *blob, struct blob_table *blob_table,
1301                    struct blob_descriptor **blob_ret)
1302 {
1303         struct blob_descriptor **back_ptr;
1304         int ret;
1305
1306         back_ptr = retrieve_pointer_to_unhashed_blob(blob);
1307
1308         ret = sha1_blob(blob);
1309         if (ret)
1310                 return ret;
1311
1312         *blob_ret = after_blob_hashed(blob, back_ptr, blob_table);
1313         return 0;
1314 }
1315
1316 void
1317 blob_to_wimlib_resource_entry(const struct blob_descriptor *blob,
1318                               struct wimlib_resource_entry *wentry)
1319 {
1320         memset(wentry, 0, sizeof(*wentry));
1321
1322         wentry->uncompressed_size = blob->size;
1323         if (blob->blob_location == BLOB_IN_WIM) {
1324                 unsigned res_flags = blob->rdesc->flags;
1325
1326                 wentry->part_number = blob->rdesc->wim->hdr.part_number;
1327                 if (res_flags & WIM_RESHDR_FLAG_SOLID) {
1328                         wentry->offset = blob->offset_in_res;
1329                 } else {
1330                         wentry->compressed_size = blob->rdesc->size_in_wim;
1331                         wentry->offset = blob->rdesc->offset_in_wim;
1332                 }
1333                 wentry->raw_resource_offset_in_wim = blob->rdesc->offset_in_wim;
1334                 wentry->raw_resource_compressed_size = blob->rdesc->size_in_wim;
1335                 wentry->raw_resource_uncompressed_size = blob->rdesc->uncompressed_size;
1336
1337                 wentry->is_compressed = (res_flags & WIM_RESHDR_FLAG_COMPRESSED) != 0;
1338                 wentry->is_free = (res_flags & WIM_RESHDR_FLAG_FREE) != 0;
1339                 wentry->is_spanned = (res_flags & WIM_RESHDR_FLAG_SPANNED) != 0;
1340                 wentry->packed = (res_flags & WIM_RESHDR_FLAG_SOLID) != 0;
1341         }
1342         if (!blob->unhashed)
1343                 copy_hash(wentry->sha1_hash, blob->hash);
1344         wentry->reference_count = blob->refcnt;
1345         wentry->is_metadata = blob->is_metadata;
1346 }
1347
1348 struct iterate_blob_context {
1349         wimlib_iterate_lookup_table_callback_t cb;
1350         void *user_ctx;
1351 };
1352
1353 static int
1354 do_iterate_blob(struct blob_descriptor *blob, void *_ctx)
1355 {
1356         struct iterate_blob_context *ctx = _ctx;
1357         struct wimlib_resource_entry entry;
1358
1359         blob_to_wimlib_resource_entry(blob, &entry);
1360         return (*ctx->cb)(&entry, ctx->user_ctx);
1361 }
1362
1363 /* API function documented in wimlib.h  */
1364 WIMLIBAPI int
1365 wimlib_iterate_lookup_table(WIMStruct *wim, int flags,
1366                             wimlib_iterate_lookup_table_callback_t cb,
1367                             void *user_ctx)
1368 {
1369         if (flags != 0)
1370                 return WIMLIB_ERR_INVALID_PARAM;
1371
1372         struct iterate_blob_context ctx = {
1373                 .cb = cb,
1374                 .user_ctx = user_ctx,
1375         };
1376         if (wim_has_metadata(wim)) {
1377                 int ret;
1378                 for (int i = 0; i < wim->hdr.image_count; i++) {
1379                         struct blob_descriptor *blob;
1380                         struct wim_image_metadata *imd = wim->image_metadata[i];
1381
1382                         ret = do_iterate_blob(imd->metadata_blob, &ctx);
1383                         if (ret)
1384                                 return ret;
1385                         image_for_each_unhashed_blob(blob, imd) {
1386                                 ret = do_iterate_blob(blob, &ctx);
1387                                 if (ret)
1388                                         return ret;
1389                         }
1390                 }
1391         }
1392         return for_blob_in_table(wim->blob_table, do_iterate_blob, &ctx);
1393 }