432fca4796445852b439285eec61371d5a3a8612
[wimlib] / src / lookup_table.c
1 /*
2  * lookup_table.c
3  *
4  * Lookup table, implemented as a hash table, that maps SHA1 message digests to
5  * data streams.
6  */
7
8 /*
9  * Copyright (C) 2012, 2013 Eric Biggers
10  *
11  * This file is part of wimlib, a library for working with WIM files.
12  *
13  * wimlib is free software; you can redistribute it and/or modify it under the
14  * terms of the GNU General Public License as published by the Free
15  * Software Foundation; either version 3 of the License, or (at your option)
16  * any later version.
17  *
18  * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
19  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
20  * A PARTICULAR PURPOSE. See the GNU General Public License for more
21  * details.
22  *
23  * You should have received a copy of the GNU General Public License
24  * along with wimlib; if not, see http://www.gnu.org/licenses/.
25  */
26
27 #include "wimlib_internal.h"
28 #include "lookup_table.h"
29 #include "buffer_io.h"
30 #include <errno.h>
31 #include <stdlib.h>
32
33 #ifdef WITH_FUSE
34 #include <unistd.h>
35 #endif
36
37 struct wim_lookup_table *
38 new_lookup_table(size_t capacity)
39 {
40         struct wim_lookup_table *table;
41         struct hlist_head *array;
42
43         table = CALLOC(1, sizeof(struct wim_lookup_table));
44         if (table) {
45                 array = CALLOC(capacity, sizeof(array[0]));
46                 if (array) {
47                         table->num_entries = 0;
48                         table->capacity = capacity;
49                         table->array = array;
50                 } else {
51                         FREE(table);
52                         table = NULL;
53                         ERROR("Failed to allocate memory for lookup table with capacity %zu",
54                               capacity);
55                 }
56         }
57         return table;
58 }
59
60 struct wim_lookup_table_entry *
61 new_lookup_table_entry()
62 {
63         struct wim_lookup_table_entry *lte;
64
65         lte = CALLOC(1, sizeof(struct wim_lookup_table_entry));
66         if (lte) {
67                 lte->part_number  = 1;
68                 lte->refcnt       = 1;
69         } else {
70                 ERROR("Out of memory (tried to allocate %zu bytes for "
71                       "lookup table entry)",
72                       sizeof(struct wim_lookup_table_entry));
73         }
74         return lte;
75 }
76
77 struct wim_lookup_table_entry *
78 clone_lookup_table_entry(const struct wim_lookup_table_entry *old)
79 {
80         struct wim_lookup_table_entry *new;
81
82         new = MALLOC(sizeof(*new));
83         if (!new)
84                 return NULL;
85
86         memcpy(new, old, sizeof(*old));
87         new->extracted_file = NULL;
88         switch (new->resource_location) {
89 #ifdef __WIN32__
90         case RESOURCE_WIN32:
91         case RESOURCE_WIN32_ENCRYPTED:
92 #endif
93         case RESOURCE_IN_FILE_ON_DISK:
94 #ifdef WITH_FUSE
95         case RESOURCE_IN_STAGING_FILE:
96                 BUILD_BUG_ON((void*)&old->file_on_disk !=
97                              (void*)&old->staging_file_name);
98 #endif
99                 new->file_on_disk = TSTRDUP(old->file_on_disk);
100                 if (!new->file_on_disk)
101                         goto out_free;
102                 break;
103         case RESOURCE_IN_ATTACHED_BUFFER:
104                 new->attached_buffer = MALLOC(wim_resource_size(old));
105                 if (!new->attached_buffer)
106                         goto out_free;
107                 memcpy(new->attached_buffer, old->attached_buffer,
108                        wim_resource_size(old));
109                 break;
110 #ifdef WITH_NTFS_3G
111         case RESOURCE_IN_NTFS_VOLUME:
112                 if (old->ntfs_loc) {
113                         struct ntfs_location *loc;
114                         loc = MALLOC(sizeof(*loc));
115                         if (!loc)
116                                 goto out_free;
117                         memcpy(loc, old->ntfs_loc, sizeof(*loc));
118                         loc->path = NULL;
119                         loc->stream_name = NULL;
120                         new->ntfs_loc = loc;
121                         loc->path = STRDUP(old->ntfs_loc->path);
122                         if (!loc->path)
123                                 goto out_free;
124                         loc->stream_name = MALLOC((loc->stream_name_nchars + 1) * 2);
125                         if (!loc->stream_name)
126                                 goto out_free;
127                         memcpy(loc->stream_name,
128                                old->ntfs_loc->stream_name,
129                                (loc->stream_name_nchars + 1) * 2);
130                 }
131                 break;
132 #endif
133         default:
134                 break;
135         }
136         return new;
137 out_free:
138         free_lookup_table_entry(new);
139         return NULL;
140 }
141
142 void
143 free_lookup_table_entry(struct wim_lookup_table_entry *lte)
144 {
145         if (lte) {
146                 switch (lte->resource_location) {
147         #ifdef __WIN32__
148                 case RESOURCE_WIN32:
149                 case RESOURCE_WIN32_ENCRYPTED:
150         #endif
151         #ifdef WITH_FUSE
152                 case RESOURCE_IN_STAGING_FILE:
153                         BUILD_BUG_ON((void*)&lte->file_on_disk !=
154                                      (void*)&lte->staging_file_name);
155         #endif
156                 case RESOURCE_IN_FILE_ON_DISK:
157                 case RESOURCE_IN_ATTACHED_BUFFER:
158                         BUILD_BUG_ON((void*)&lte->file_on_disk !=
159                                      (void*)&lte->attached_buffer);
160                         FREE(lte->file_on_disk);
161                         break;
162 #ifdef WITH_NTFS_3G
163                 case RESOURCE_IN_NTFS_VOLUME:
164                         if (lte->ntfs_loc) {
165                                 FREE(lte->ntfs_loc->path);
166                                 FREE(lte->ntfs_loc->stream_name);
167                                 FREE(lte->ntfs_loc);
168                         }
169                         break;
170 #endif
171                 default:
172                         break;
173                 }
174                 FREE(lte);
175         }
176 }
177
178 static int
179 do_free_lookup_table_entry(struct wim_lookup_table_entry *entry, void *ignore)
180 {
181         free_lookup_table_entry(entry);
182         return 0;
183 }
184
185
186 void
187 free_lookup_table(struct wim_lookup_table *table)
188 {
189         DEBUG2("Freeing lookup table");
190         if (table) {
191                 if (table->array) {
192                         for_lookup_table_entry(table,
193                                                do_free_lookup_table_entry,
194                                                NULL);
195                         FREE(table->array);
196                 }
197                 FREE(table);
198         }
199 }
200
201 /*
202  * Inserts an entry into the lookup table.
203  *
204  * @table:      A pointer to the lookup table.
205  * @lte:        A pointer to the entry to insert.
206  */
207 void
208 lookup_table_insert(struct wim_lookup_table *table,
209                     struct wim_lookup_table_entry *lte)
210 {
211         size_t i = lte->hash_short % table->capacity;
212         hlist_add_head(&lte->hash_list, &table->array[i]);
213
214         /* XXX Make the table grow when too many entries have been inserted. */
215         table->num_entries++;
216 }
217
218 static void
219 finalize_lte(struct wim_lookup_table_entry *lte)
220 {
221         #ifdef WITH_FUSE
222         if (lte->resource_location == RESOURCE_IN_STAGING_FILE) {
223                 unlink(lte->staging_file_name);
224                 list_del(&lte->unhashed_list);
225         }
226         #endif
227         free_lookup_table_entry(lte);
228 }
229
230 /* Decrements the reference count for the lookup table entry @lte.  If its
231  * reference count reaches 0, it is unlinked from the lookup table.  If,
232  * furthermore, the entry has no opened file descriptors associated with it, the
233  * entry is freed.  */
234 void
235 lte_decrement_refcnt(struct wim_lookup_table_entry *lte,
236                      struct wim_lookup_table *table)
237 {
238         wimlib_assert(lte != NULL);
239         wimlib_assert(lte->refcnt != 0);
240         if (--lte->refcnt == 0) {
241                 if (!lte->unhashed)
242                         lookup_table_unlink(table, lte);
243         #ifdef WITH_FUSE
244                 if (lte->num_opened_fds == 0)
245         #endif
246                         finalize_lte(lte);
247         }
248 }
249
250 #ifdef WITH_FUSE
251 void
252 lte_decrement_num_opened_fds(struct wim_lookup_table_entry *lte)
253 {
254         if (lte->num_opened_fds != 0)
255                 if (--lte->num_opened_fds == 0 && lte->refcnt == 0)
256                         finalize_lte(lte);
257 }
258 #endif
259
260 /* Calls a function on all the entries in the WIM lookup table.  Stop early and
261  * return nonzero if any call to the function returns nonzero. */
262 int
263 for_lookup_table_entry(struct wim_lookup_table *table,
264                        int (*visitor)(struct wim_lookup_table_entry *, void *),
265                        void *arg)
266 {
267         struct wim_lookup_table_entry *lte;
268         struct hlist_node *pos, *tmp;
269         int ret;
270
271         for (size_t i = 0; i < table->capacity; i++) {
272                 hlist_for_each_entry_safe(lte, pos, tmp, &table->array[i],
273                                           hash_list)
274                 {
275                         wimlib_assert2(!(lte->resource_entry.flags & WIM_RESHDR_FLAG_METADATA));
276                         ret = visitor(lte, arg);
277                         if (ret)
278                                 return ret;
279                 }
280         }
281         return 0;
282 }
283
284 int
285 cmp_streams_by_wim_position(const void *p1, const void *p2)
286 {
287         const struct wim_lookup_table_entry *lte1, *lte2;
288         lte1 = *(const struct wim_lookup_table_entry**)p1;
289         lte2 = *(const struct wim_lookup_table_entry**)p2;
290         if (lte1->resource_entry.offset < lte2->resource_entry.offset)
291                 return -1;
292         else if (lte1->resource_entry.offset > lte2->resource_entry.offset)
293                 return 1;
294         else
295                 return 0;
296 }
297
298
299 static int
300 add_lte_to_array(struct wim_lookup_table_entry *lte,
301                  void *_pp)
302 {
303         struct wim_lookup_table_entry ***pp = _pp;
304         *(*pp)++ = lte;
305         return 0;
306 }
307
308 /* Iterate through the lookup table entries, but first sort them by stream
309  * offset in the WIM.  Caution: this is intended to be used when the stream
310  * offset field has actually been set. */
311 int
312 for_lookup_table_entry_pos_sorted(struct wim_lookup_table *table,
313                                   int (*visitor)(struct wim_lookup_table_entry *,
314                                                  void *),
315                                   void *arg)
316 {
317         struct wim_lookup_table_entry **lte_array, **p;
318         size_t num_streams = table->num_entries;
319         int ret;
320
321         lte_array = MALLOC(num_streams * sizeof(lte_array[0]));
322         if (!lte_array)
323                 return WIMLIB_ERR_NOMEM;
324         p = lte_array;
325         for_lookup_table_entry(table, add_lte_to_array, &p);
326
327         wimlib_assert(p == lte_array + num_streams);
328
329         qsort(lte_array, num_streams, sizeof(lte_array[0]),
330               cmp_streams_by_wim_position);
331         ret = 0;
332         for (size_t i = 0; i < num_streams; i++) {
333                 ret = visitor(lte_array[i], arg);
334                 if (ret)
335                         break;
336         }
337         FREE(lte_array);
338         return ret;
339 }
340
341 /*
342  * Reads the lookup table from a WIM file.
343  *
344  * Saves lookup table entries for non-metadata streams in a hash table, and
345  * saves the metadata entry for each image in a special per-image location (the
346  * image_metadata array).
347  */
348 int
349 read_lookup_table(WIMStruct *w)
350 {
351         u64 num_entries;
352         u8 buf[WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE];
353         int ret;
354         struct wim_lookup_table *table;
355         struct wim_lookup_table_entry *cur_entry, *duplicate_entry;
356
357         if (resource_is_compressed(&w->hdr.lookup_table_res_entry)) {
358                 ERROR("Didn't expect a compressed lookup table!");
359                 ERROR("Ask the author to implement support for this.");
360                 return WIMLIB_ERR_COMPRESSED_LOOKUP_TABLE;
361         }
362
363         DEBUG("Reading lookup table: offset %"PRIu64", size %"PRIu64"",
364               w->hdr.lookup_table_res_entry.offset,
365               w->hdr.lookup_table_res_entry.original_size);
366
367         if (fseeko(w->fp, w->hdr.lookup_table_res_entry.offset, SEEK_SET) != 0)
368         {
369                 ERROR_WITH_ERRNO("Failed to seek to byte %"PRIu64" to read "
370                                  "lookup table",
371                                  w->hdr.lookup_table_res_entry.offset);
372                 return WIMLIB_ERR_READ;
373         }
374
375         num_entries = w->hdr.lookup_table_res_entry.original_size /
376                       WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE;
377         table = new_lookup_table(num_entries * 2 + 1);
378         if (!table)
379                 return WIMLIB_ERR_NOMEM;
380
381         w->current_image = 0;
382         while (num_entries--) {
383                 const u8 *p;
384
385                 if (fread(buf, 1, sizeof(buf), w->fp) != sizeof(buf)) {
386                         if (feof(w->fp)) {
387                                 ERROR("Unexpected EOF in WIM lookup table!");
388                         } else {
389                                 ERROR_WITH_ERRNO("Error reading WIM lookup "
390                                                  "table");
391                         }
392                         ret = WIMLIB_ERR_READ;
393                         goto out_free_lookup_table;
394                 }
395                 cur_entry = new_lookup_table_entry();
396                 if (!cur_entry) {
397                         ret = WIMLIB_ERR_NOMEM;
398                         goto out_free_lookup_table;
399                 }
400
401                 cur_entry->wim = w;
402                 cur_entry->resource_location = RESOURCE_IN_WIM;
403                 p = get_resource_entry(buf, &cur_entry->resource_entry);
404                 p = get_u16(p, &cur_entry->part_number);
405                 p = get_u32(p, &cur_entry->refcnt);
406                 p = get_bytes(p, SHA1_HASH_SIZE, cur_entry->hash);
407
408                 if (cur_entry->part_number != w->hdr.part_number) {
409                         ERROR("A lookup table entry in part %hu of the WIM "
410                               "points to part %hu",
411                               w->hdr.part_number, cur_entry->part_number);
412                         ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
413                         goto out_free_cur_entry;
414                 }
415
416                 if (is_zero_hash(cur_entry->hash)) {
417                         ERROR("The WIM lookup table contains an entry with a "
418                               "SHA1 message digest of all 0's");
419                         ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
420                         goto out_free_cur_entry;
421                 }
422
423                 if (!(cur_entry->resource_entry.flags & WIM_RESHDR_FLAG_COMPRESSED)
424                     && (cur_entry->resource_entry.size !=
425                         cur_entry->resource_entry.original_size))
426                 {
427                 #ifdef ENABLE_ERROR_MESSAGES
428                         ERROR("Found uncompressed resource with original size "
429                               "not the same as compressed size");
430                         ERROR("The lookup table entry for the resource is as follows:");
431                         print_lookup_table_entry(cur_entry, stderr);
432                 #endif
433                         ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
434                         goto out_free_cur_entry;
435                 }
436
437                 if (cur_entry->resource_entry.flags & WIM_RESHDR_FLAG_METADATA) {
438                         /* Lookup table entry for a metadata resource */
439                         if (cur_entry->refcnt != 1) {
440                         #ifdef ENABLE_ERROR_MESSAGES
441                                 ERROR("Found metadata resource with refcnt != 1:");
442                                 print_lookup_table_entry(cur_entry, stderr);
443                         #endif
444                                 ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
445                                 goto out_free_cur_entry;
446                         }
447
448                         if (w->hdr.part_number != 1) {
449                                 ERROR("Found a metadata resource in a "
450                                       "non-first part of the split WIM!");
451                                 ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
452                                 goto out_free_cur_entry;
453                         }
454                         if (w->current_image == w->hdr.image_count) {
455                                 ERROR("The WIM header says there are %u images "
456                                       "in the WIM, but we found more metadata "
457                                       "resources than this", w->hdr.image_count);
458                                 ret = WIMLIB_ERR_IMAGE_COUNT;
459                                 goto out_free_cur_entry;
460                         }
461
462                         /* Notice very carefully:  We are assigning the metadata
463                          * resources in the exact order mirrored by their lookup
464                          * table entries on disk, which is the behavior of
465                          * Microsoft's software.  In particular, this overrides
466                          * the actual locations of the metadata resources
467                          * themselves in the WIM file as well as any information
468                          * written in the XML data. */
469                         DEBUG("Found metadata resource for image %u at "
470                               "offset %"PRIu64".",
471                               w->current_image + 1,
472                               cur_entry->resource_entry.offset);
473                         w->image_metadata[
474                                 w->current_image++]->metadata_lte = cur_entry;
475                 } else {
476                         /* Lookup table entry for a stream that is not a
477                          * metadata resource */
478                         duplicate_entry = __lookup_resource(table, cur_entry->hash);
479                         if (duplicate_entry) {
480                         #ifdef ENABLE_ERROR_MESSAGES
481                                 ERROR("The WIM lookup table contains two entries with the "
482                                       "same SHA1 message digest!");
483                                 ERROR("The first entry is:");
484                                 print_lookup_table_entry(duplicate_entry, stderr);
485                                 ERROR("The second entry is:");
486                                 print_lookup_table_entry(cur_entry, stderr);
487                         #endif
488                                 ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
489                                 goto out_free_cur_entry;
490                         }
491                         lookup_table_insert(table, cur_entry);
492                 }
493         }
494
495         if (w->hdr.part_number == 1 &&
496             w->current_image != w->hdr.image_count)
497         {
498                 ERROR("The WIM header says there are %u images "
499                       "in the WIM, but we only found %d metadata "
500                       "resources!", w->hdr.image_count, w->current_image);
501                 ret = WIMLIB_ERR_IMAGE_COUNT;
502                 goto out_free_lookup_table;
503         }
504         DEBUG("Done reading lookup table.");
505         w->lookup_table = table;
506         ret = 0;
507         goto out;
508 out_free_cur_entry:
509         FREE(cur_entry);
510 out_free_lookup_table:
511         free_lookup_table(table);
512 out:
513         w->current_image = 0;
514         return ret;
515 }
516
517
518 /*
519  * Writes a lookup table entry to the output file.
520  */
521 int
522 write_lookup_table_entry(struct wim_lookup_table_entry *lte, void *_out)
523 {
524         FILE *out;
525         u8 buf[WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE];
526         u8 *p;
527
528         out = _out;
529
530         /* Don't write entries that have not had file resources or metadata
531          * resources written for them. */
532         if (lte->out_refcnt == 0)
533                 return 0;
534
535         if (lte->output_resource_entry.flags & WIM_RESHDR_FLAG_METADATA) {
536                 DEBUG("Writing metadata entry at %"PRIu64" "
537                       "(orig size = %"PRIu64")",
538                       ftello(out), lte->output_resource_entry.original_size);
539         }
540
541         p = put_resource_entry(buf, &lte->output_resource_entry);
542         p = put_u16(p, lte->part_number);
543         p = put_u32(p, lte->out_refcnt);
544         p = put_bytes(p, SHA1_HASH_SIZE, lte->hash);
545         if (fwrite(buf, 1, sizeof(buf), out) != sizeof(buf)) {
546                 ERROR_WITH_ERRNO("Failed to write lookup table entry");
547                 return WIMLIB_ERR_WRITE;
548         }
549         return 0;
550 }
551
552 /* Writes the WIM lookup table to the output file. */
553 int
554 write_lookup_table(WIMStruct *w, int image, struct resource_entry *out_res_entry)
555 {
556         FILE *out = w->out_fp;
557         off_t start_offset, end_offset;
558         int ret;
559         int start_image, end_image;
560
561         start_offset = ftello(out);
562         if (start_offset == -1)
563                 return WIMLIB_ERR_WRITE;
564
565         /* Write lookup table entries for metadata resources */
566         if (image == WIMLIB_ALL_IMAGES) {
567                 start_image = 1;
568                 end_image = w->hdr.image_count;
569         } else {
570                 start_image = image;
571                 end_image = image;
572         }
573         for (int i = start_image; i <= end_image; i++) {
574                 struct wim_lookup_table_entry *metadata_lte;
575
576                 metadata_lte = w->image_metadata[i - 1]->metadata_lte;
577                 metadata_lte->out_refcnt = 1;
578                 metadata_lte->output_resource_entry.flags |= WIM_RESHDR_FLAG_METADATA;
579                 ret = write_lookup_table_entry(metadata_lte, out);
580                 if (ret)
581                         return ret;
582         }
583
584         /* Write lookup table entries for other resources */
585         ret = for_lookup_table_entry(w->lookup_table, write_lookup_table_entry, out);
586         if (ret)
587                 return ret;
588
589         /* Fill in the resource entry for the lookup table itself */
590         end_offset = ftello(out);
591         if (end_offset == -1)
592                 return WIMLIB_ERR_WRITE;
593
594         out_res_entry->offset        = start_offset;
595         out_res_entry->size          = end_offset - start_offset;
596         out_res_entry->original_size = end_offset - start_offset;
597         out_res_entry->flags         = WIM_RESHDR_FLAG_METADATA;
598         return 0;
599 }
600
601 int
602 lte_zero_real_refcnt(struct wim_lookup_table_entry *lte, void *_ignore)
603 {
604         lte->real_refcnt = 0;
605         return 0;
606 }
607
608 int
609 lte_zero_out_refcnt(struct wim_lookup_table_entry *lte, void *_ignore)
610 {
611         lte->out_refcnt = 0;
612         return 0;
613 }
614
615 int
616 lte_free_extracted_file(struct wim_lookup_table_entry *lte, void *_ignore)
617 {
618         if (lte->extracted_file != NULL) {
619                 FREE(lte->extracted_file);
620                 lte->extracted_file = NULL;
621         }
622         return 0;
623 }
624
625 void
626 print_lookup_table_entry(const struct wim_lookup_table_entry *lte, FILE *out)
627 {
628         if (!lte) {
629                 tputc(T('\n'), out);
630                 return;
631         }
632         tfprintf(out, T("Offset            = %"PRIu64" bytes\n"),
633                  lte->resource_entry.offset);
634
635         tfprintf(out, T("Size              = %"PRIu64" bytes\n"),
636                  (u64)lte->resource_entry.size);
637
638         tfprintf(out, T("Original size     = %"PRIu64" bytes\n"),
639                  lte->resource_entry.original_size);
640
641         tfprintf(out, T("Part Number       = %hu\n"), lte->part_number);
642         tfprintf(out, T("Reference Count   = %u\n"), lte->refcnt);
643
644         if (lte->unhashed) {
645                 tfprintf(out, T("(Unhashed: inode %p, stream_id = %u)\n"),
646                          lte->back_inode, lte->back_stream_id);
647         } else {
648                 tfprintf(out, T("Hash              = 0x"));
649                 print_hash(lte->hash, out);
650                 tputc(T('\n'), out);
651         }
652
653         tfprintf(out, T("Flags             = "));
654         u8 flags = lte->resource_entry.flags;
655         if (flags & WIM_RESHDR_FLAG_COMPRESSED)
656                 tfputs(T("WIM_RESHDR_FLAG_COMPRESSED, "), out);
657         if (flags & WIM_RESHDR_FLAG_FREE)
658                 tfputs(T("WIM_RESHDR_FLAG_FREE, "), out);
659         if (flags & WIM_RESHDR_FLAG_METADATA)
660                 tfputs(T("WIM_RESHDR_FLAG_METADATA, "), out);
661         if (flags & WIM_RESHDR_FLAG_SPANNED)
662                 tfputs(T("WIM_RESHDR_FLAG_SPANNED, "), out);
663         tputc(T('\n'), out);
664         switch (lte->resource_location) {
665         case RESOURCE_IN_WIM:
666                 if (lte->wim->filename) {
667                         tfprintf(out, T("WIM file          = `%"TS"'\n"),
668                                  lte->wim->filename);
669                 }
670                 break;
671 #ifdef __WIN32__
672         case RESOURCE_WIN32:
673         case RESOURCE_WIN32_ENCRYPTED:
674 #endif
675         case RESOURCE_IN_FILE_ON_DISK:
676                 tfprintf(out, T("File on Disk      = `%"TS"'\n"),
677                          lte->file_on_disk);
678                 break;
679 #ifdef WITH_FUSE
680         case RESOURCE_IN_STAGING_FILE:
681                 tfprintf(out, T("Staging File      = `%"TS"'\n"),
682                                 lte->staging_file_name);
683                 break;
684 #endif
685         default:
686                 break;
687         }
688         tputc(T('\n'), out);
689 }
690
691 static int
692 do_print_lookup_table_entry(struct wim_lookup_table_entry *lte, void *fp)
693 {
694         print_lookup_table_entry(lte, (FILE*)fp);
695         return 0;
696 }
697
698 /*
699  * Prints the lookup table of a WIM file.
700  */
701 WIMLIBAPI void
702 wimlib_print_lookup_table(WIMStruct *w)
703 {
704         for_lookup_table_entry(w->lookup_table,
705                                do_print_lookup_table_entry,
706                                stdout);
707 }
708
709 /* Given a SHA1 message digest, return the corresponding entry in the WIM's
710  * lookup table, or NULL if there is none.  */
711 struct wim_lookup_table_entry *
712 __lookup_resource(const struct wim_lookup_table *table, const u8 hash[])
713 {
714         size_t i;
715         struct wim_lookup_table_entry *lte;
716         struct hlist_node *pos;
717
718         wimlib_assert(table != NULL);
719         wimlib_assert(hash != NULL);
720
721         i = *(size_t*)hash % table->capacity;
722         hlist_for_each_entry(lte, pos, &table->array[i], hash_list)
723                 if (hashes_equal(hash, lte->hash))
724                         return lte;
725         return NULL;
726 }
727
728 #ifdef WITH_FUSE
729 /*
730  * Finds the dentry, lookup table entry, and stream index for a WIM file stream,
731  * given a path name.
732  *
733  * This is only for pre-resolved inodes.
734  */
735 int
736 lookup_resource(WIMStruct *w,
737                 const tchar *path,
738                 int lookup_flags,
739                 struct wim_dentry **dentry_ret,
740                 struct wim_lookup_table_entry **lte_ret,
741                 u16 *stream_idx_ret)
742 {
743         struct wim_dentry *dentry;
744         struct wim_lookup_table_entry *lte;
745         u16 stream_idx;
746         const tchar *stream_name = NULL;
747         struct wim_inode *inode;
748         tchar *p = NULL;
749
750         if (lookup_flags & LOOKUP_FLAG_ADS_OK) {
751                 stream_name = path_stream_name(path);
752                 if (stream_name) {
753                         p = (tchar*)stream_name - 1;
754                         *p = T('\0');
755                 }
756         }
757
758         dentry = get_dentry(w, path);
759         if (p)
760                 *p = T(':');
761         if (!dentry)
762                 return -errno;
763
764         inode = dentry->d_inode;
765
766         wimlib_assert(inode->i_resolved);
767
768         if (!(lookup_flags & LOOKUP_FLAG_DIRECTORY_OK)
769               && inode_is_directory(inode))
770                 return -EISDIR;
771
772         if (stream_name) {
773                 struct wim_ads_entry *ads_entry;
774                 u16 ads_idx;
775                 ads_entry = inode_get_ads_entry(inode, stream_name,
776                                                 &ads_idx);
777                 if (ads_entry) {
778                         stream_idx = ads_idx + 1;
779                         lte = ads_entry->lte;
780                         goto out;
781                 } else {
782                         return -ENOENT;
783                 }
784         } else {
785                 lte = inode->i_lte;
786                 stream_idx = 0;
787         }
788 out:
789         if (dentry_ret)
790                 *dentry_ret = dentry;
791         if (lte_ret)
792                 *lte_ret = lte;
793         if (stream_idx_ret)
794                 *stream_idx_ret = stream_idx;
795         return 0;
796 }
797 #endif
798
799 /* Resolve an inode's lookup table entries
800  *
801  * This replaces the SHA1 hash fields (which are used to lookup an entry in the
802  * lookup table) with pointers directly to the lookup table entries.  A circular
803  * linked list of streams sharing the same lookup table entry is created.
804  *
805  * This function always succeeds; unresolved lookup table entries are given a
806  * NULL pointer.
807  */
808 void
809 inode_resolve_ltes(struct wim_inode *inode, struct wim_lookup_table *table)
810 {
811
812         if (!inode->i_resolved) {
813                 struct wim_lookup_table_entry *lte;
814                 /* Resolve the default file stream */
815                 lte = __lookup_resource(table, inode->i_hash);
816                 inode->i_lte = lte;
817                 inode->i_resolved = 1;
818
819                 /* Resolve the alternate data streams */
820                 for (u16 i = 0; i < inode->i_num_ads; i++) {
821                         struct wim_ads_entry *cur_entry = &inode->i_ads_entries[i];
822                         lte = __lookup_resource(table, cur_entry->hash);
823                         cur_entry->lte = lte;
824                 }
825         }
826 }
827
828 void
829 inode_unresolve_ltes(struct wim_inode *inode)
830 {
831         if (inode->i_resolved) {
832                 if (inode->i_lte)
833                         copy_hash(inode->i_hash, inode->i_lte->hash);
834                 else
835                         zero_out_hash(inode->i_hash);
836
837                 for (u16 i = 0; i < inode->i_num_ads; i++) {
838                         if (inode->i_ads_entries[i].lte)
839                                 copy_hash(inode->i_ads_entries[i].hash,
840                                           inode->i_ads_entries[i].lte->hash);
841                         else
842                                 zero_out_hash(inode->i_ads_entries[i].hash);
843                 }
844                 inode->i_resolved = 0;
845         }
846 }
847
848 /*
849  * Returns the lookup table entry for stream @stream_idx of the inode, where
850  * stream_idx = 0 means the default un-named file stream, and stream_idx >= 1
851  * corresponds to an alternate data stream.
852  *
853  * This works for both resolved and un-resolved inodes.
854  */
855 struct wim_lookup_table_entry *
856 inode_stream_lte(const struct wim_inode *inode, unsigned stream_idx,
857                  const struct wim_lookup_table *table)
858 {
859         if (inode->i_resolved)
860                 return inode_stream_lte_resolved(inode, stream_idx);
861         else
862                 return inode_stream_lte_unresolved(inode, stream_idx, table);
863 }
864
865
866 /* Return the lookup table entry for the unnamed data stream of an inode, or
867  * NULL if there is none.
868  *
869  * You'd think this would be easier than it actually is, since the unnamed data
870  * stream should be the one referenced from the inode itself.  Alas, if there
871  * are named data streams, Microsoft's "imagex.exe" program will put the unnamed
872  * data stream in one of the alternate data streams instead of inside the WIM
873  * dentry itself.  So we need to check the alternate data streams too.
874  *
875  * Also, note that a dentry may appear to have more than one unnamed stream, but
876  * if the SHA1 message digest is all 0's then the corresponding stream does not
877  * really "count" (this is the case for the inode's own file stream when the
878  * file stream that should be there is actually in one of the alternate stream
879  * entries.).  This is despite the fact that we may need to extract such a
880  * missing entry as an empty file or empty named data stream.
881  */
882 struct wim_lookup_table_entry *
883 inode_unnamed_lte(const struct wim_inode *inode,
884                   const struct wim_lookup_table *table)
885 {
886         if (inode->i_resolved)
887                 return inode_unnamed_lte_resolved(inode);
888         else
889                 return inode_unnamed_lte_unresolved(inode, table);
890 }
891
892 static int
893 lte_add_stream_size(struct wim_lookup_table_entry *lte, void *total_bytes_p)
894 {
895         *(u64*)total_bytes_p += lte->resource_entry.size;
896         return 0;
897 }
898
899 u64
900 lookup_table_total_stream_size(struct wim_lookup_table *table)
901 {
902         u64 total_size = 0;
903         for_lookup_table_entry(table, lte_add_stream_size, &total_size);
904         return total_size;
905 }
906
907 struct wim_lookup_table_entry **
908 retrieve_lte_pointer(struct wim_lookup_table_entry *lte)
909 {
910         wimlib_assert(lte->unhashed);
911         struct wim_inode *inode = lte->back_inode;
912         u32 stream_id = lte->back_stream_id;
913         if (stream_id == 0)
914                 return &inode->i_lte;
915         else
916                 for (u16 i = 0; i < inode->i_num_ads; i++)
917                         if (inode->i_ads_entries[i].stream_id == stream_id)
918                                 return &inode->i_ads_entries[i].lte;
919         wimlib_assert(0);
920         return NULL;
921 }
922
923 /* Calculate the SHA1 message digest of a stream and move it from the list of
924  * unhashed streams to the stream lookup table, possibly joining it with an
925  * existing lookup table entry for an identical stream.
926  *
927  * @lte:  An unhashed lookup table entry.
928  * @lookup_table:  Lookup table for the WIM.
929  * @lte_ret:  On success, write a pointer to the resulting lookup table
930  *            entry to this location.  This will be the same as @lte
931  *            if it was inserted into the lookup table, or different if
932  *            a duplicate stream was found.
933  *
934  * Returns 0 on success; nonzero if there is an error reading the stream.
935  */
936 int
937 hash_unhashed_stream(struct wim_lookup_table_entry *lte,
938                      struct wim_lookup_table *lookup_table,
939                      struct wim_lookup_table_entry **lte_ret)
940 {
941         int ret;
942         struct wim_lookup_table_entry *duplicate_lte;
943         struct wim_lookup_table_entry **back_ptr;
944
945         wimlib_assert(lte->unhashed);
946
947         /* back_ptr must be saved because @back_inode and @back_stream_id are in
948          * union with the SHA1 message digest and will no longer be valid once
949          * the SHA1 has been calculated. */
950         back_ptr = retrieve_lte_pointer(lte);
951
952         ret = sha1_resource(lte);
953         if (ret)
954                 return ret;
955
956         /* Look for a duplicate stream */
957         duplicate_lte = __lookup_resource(lookup_table, lte->hash);
958         list_del(&lte->unhashed_list);
959         if (duplicate_lte) {
960                 /* We have a duplicate stream.  Transfer the reference counts
961                  * from this stream to the duplicate, update the reference to
962                  * this stream (in an inode or ads_entry) to point to the
963                  * duplicate, then free this stream. */
964                 wimlib_assert(!(duplicate_lte->unhashed));
965                 duplicate_lte->refcnt += lte->refcnt;
966                 duplicate_lte->out_refcnt += lte->refcnt;
967                 *back_ptr = duplicate_lte;
968                 free_lookup_table_entry(lte);
969                 lte = duplicate_lte;
970         } else {
971                 /* No duplicate stream, so we need to insert
972                  * this stream into the lookup table and treat
973                  * it as a hashed stream. */
974                 lookup_table_insert(lookup_table, lte);
975                 lte->unhashed = 0;
976         }
977         if (lte_ret)
978                 *lte_ret = lte;
979         return 0;
980 }
981