lzx-compress.c:  Don't do redundant work in cost calculations

lzx.h: Align 'struct lzx_lru_queue' on x86_64

{lzx,lzms-decompress.c}: Allocate context with DECODE_TABLE_ALIGNMENT

Add aligned malloc and free

Don't make dependent on OS support, since that would break the custom
memory allocation functions and also would need to be different between
UNIX and Windows anyway.

xml.c: Don't count reparse point data and directory streams in <TOTALBYTES>

Don't exclude out-of-tree absolute symlinks in reparse point fix mode

Excluding such links may not be the expected behavior.  In addition,
Microsoft's documentation for ImageX seems to be incorrect when it states
that ImageX excludes such links.  Actually, it does not.  So, for the
sake of consistency and also doing something that may more sense anyway,
just retain such links, but leave their targets as-is.

win32_apply.c: Fix reparse point fixup of device-direct links (no trailing slash)

After extraction these should point to the capture directory.

This was broken in 1.6.2 as well, but in a different way!

unix_apply.c: Honor i_not_rpfixed

This was a regression from 1.6.2

extract.c: Remove unused internal flag

Remove some dead assignments

mount_image.c: Don't pass NULL to mq_send()

xpress-decompress.c: Remove unused 'lens' parameter to xpress_lz_decode()

wimboot.c, win32_apply.c:  Bracket file by #ifdef __WIN32__

This makes compiling all non-Windows source files manually (e.g. with
clang-scan-build.sh) easier.

decompress_common.c: Add util.h back

Update date

lzms-compress.c: Don't underrun window when checking recent offsets

In LZMS, not all recent offsets are initialized to 1, unlike in LZX.

A few comment fixes

Remove a few unnecessary includes

Update public domain dedications

wimexport: Document --wimboot option

wimextract: Rename --no-wildcards to --no-globs; update man page

wimextract: Suggest --nullglob

Update NEWS

lzx-compress.c:  Honor cache_limit

This ensures the match cache is never overrun.  If for some reason we
average more than LZX_CACHE_PER_POS (currently 8) matches per position,
_excluding skipped positions_, just don't return any more matches.

Merge branch 'lz_bt'

Switch from suffix array match-finder to binary tree match-finder

This uses less memory (8 bytes overhead per position vs. 14), is faster,
requires less code (no libdivsufsort), and in some tests actually results
in a better compression ratio.

A binary tree match-finder was used in wimlib v1.5.2 but it didn't seem
as good then, probably because it was combined with a slow block division
algorithm for LZX.

Repeat offsets are now handled differently.  The binary tree match-finder
itself doesn't have any logic for repeat offsets at all; instead, the
match-choosing code (now implemented separately for LZX and LZMS) now
does special checks for matches at repeat offsets.

Since less memory is used for match-finding now, increase the default
LZMS pack chunk size from 2^25 (33554432) to 2^26 (67108864).

lzms-common.c, lzms-compress.c:  Use pthread_once()

Fix creating large solid blocks

Dumb bug that only appeared when at least 4 GiB of data was being
archived...!

lzms-compress.c: Fix typo

Share most e8 processing code between LZX compressor and decompressor

lzx-compress.c: Clarify there must be at least one optimization pass

lzx-compress.c:  Use pointers in lzx_optimize_block()

This makes the performance less reliant on the compiler recognizing that
the 'struct lzx_block_spec' does not change throughout the loop.

inode_fixup.c: Fix check for directory hard links

We shouldn't assume that the attributes are consistent, so we should
check both ways for directory hard links.  Specifically, in the case
where the being-inserted dentry is not marked as a directory but for some
reason it shares an inode number with a dentry marked as a directory, we
want to detect that as a directory hard link.

Optimize Huffman code generation

This commit significantly improves the performance of length-limited
canonical Huffman code generation by introducing several optimizations
based on the 7-Zip implementation.

Altlhough Huffman code generation is not the main bottleneck of any of
the compression algorithms implemented here, an optimized implementation
can still improve overall performance by several percent.  In addition,
it significantly speeds up LZMS decompression, which requires frequent
rebuilding of adaptive Huffman codes.

Some peformance comparisons:

    - The average time taken to generate all three LZX codes (main,
      length, and aligned offset) when compressing a Windows PE
      filesystem with LZX decreased from 73.9 us to 17.3 us.

    - The time taken to compress a Windows PE filesystem with LZX, using
      the "fast" LZX algorithm (hash chain match finder and lazy
      parsing), decreased from 12.3 s to 11.6 s (a 5.7% improvement).

    - The time taken to decompress a Windows PE filesystem with LZMS,
      using solid blocks, decreased from 12.3 s to 9.0 s (a 27%
      improvement).

Revert "lzx-compress.c: Simplify calculation of position footer"

This reverts commit 3adc1ac1ebe221427857d8f6fd06cfb823b4bea6.

If the position footer is unconditionally calculated as the match offset
minus the position base value, the (ultimately unused) position footer
for repeat matches can overflow the number of bits in which it is stored
in the intermediate representation used by this implementation.  For now,
use the old version, which would set the position footers of repeat
matches to 0.

lzx-compress.c: Simplify output of length footer

lzx-compress.c: Simplify calculation of position footer

lzx-decompress.c: Simplify handling of recent offsets

The recent offsets can all be handled by the same code.  This should
remove at least one branch from the generated code.

Remove unused 'num_syms' argument to read_huffsym()

The updated decoder no longer requires that the number of symbols in the
alphabet be provided when decoding each symbol.

Faster Huffman symbol decoding

When decoding a codeword short enough for a direct mapping, we can read
the codeword length at the same time we read the symbol itself.  This
speeds up Huffman decoding slightly.

This commit also updates and improves the comments for
make_huffman_decode_table().

lzx-decompress.c:  One fewer branch in undo_call_insn_translation()

LZX, XPRESS decompression:  Return 0 bits on overrun

If the compressed data is invalid such that the compressed data buffer is
overrun, it's simpler to just return 0 bits instead of explicitly
checking the return value at every call site of bitstream_read_bits() and
read_huffsym().

This doesn't necessarily mean that invalid data will go undetected.  Just
for LZX decompression, chances are there will be another problem if all
0's start being returned (e.g. invalid match or invalid Huffman tree).
For WIM operations like extraction, the uncompressed data is checked with
SHA-1 message digests anyway, so it's virtually impossible for corruption
to go undetected.

Also, the LZMS decompressor already does this.

lzx-decompress.c:  Add SSE2 version of undo_call_insn_preprocessing()

resource.c: Fix two comments

resource.c:  Don't call lseek() if not necessary

To be reading a pipable resource from a pipe, is_pipable must be set in
the 'struct wim_resource_spec', so check that first before calling
filedes_is_seekable().

extract.c: Remove unused internal flag

Update NEWS

xml.c: Export <ARCH> and <WIMBOOT> nodes correctly

The XML data still needs to be handled better in general, but this fixes
the bug that this information was missing from clone_image_info().

Check for case where too many identical files are being extracted

Hoping to add a real fix for this, but for now at least avoid the buffer
overflow in UNIX and NTFS-3g extraction modes.

mount_image.c:  Don't use tchar when not necessary

mount_image.c: Add error.h outside WITH_FUSE conditional

Fix file locking

- Lock in_fd only
- Unlock WIM immediately after commiting mounted image (before
  fuse_main() returns)
- Don't lock WIM for read-only mount

test-imagex-mount: Always use tmp.mnt for mounts

mount_image.c:  Use setxattr wimfs.unmount_info, getxattr wimfs.unmount

This lets us return the unmount status directly, instead of sending it
over the message queue (which is subject to problems, like it being
full).

Also, if commit fails, leave the image mounted, unless doing a forced
unmount.

mount_image.c: Fix comment

inode.h: Fix comment

Remove references to libwim9

Revert "lzx-compress.c:  Disable verification by default"

This reverts commit 5448b9cd60e9b1ebf4efcd2d1b2aac346b2e829c.

Switched from libdivsufsort to libdivsufsort-lite; should be the same,
but just in case I'm leaving verification on for the "slow" algorithm.

tagged_items.c: Include header size when searching items

Track divsufsort.h

Use libdivsufsort-lite, not the full libdivsufsort

Remove xattr configuration option

lzx-compress.c:  Disable verification by default

The algorithm seems to be sufficiently well tested now.  And the data is
checked with SHA-1 message digests anyway.  This slightly improves LZX
compression performance.

dentry.h: Remove unneeded forwards declarations

Move wim_pathname_to_stream() to mount_image.c

Remove unused function lte_filename_valid()

struct wim_dentry:  Union subdir_offset and tmp_list

struct wim_dentry: Remove 'length' field

struct wim_dentry: Rename 'parent' to 'd_parent'

mount_image.c: Update directory timestamps

Remove unused error codes

Explicitly declare error code numbers

Update mount implementation

- Improve comments and documentation
- Speed up fd allocation by tracking lower bound on next available slot
- Open staging files by directory-relative names
- Simplify, and hopefully improve, how unmounting images works.

win32_apply.c: Fix extraction of non-WIMBoot files in WIMBoot mode

Report progress for capture symlink fixups

wimcapture: On non-Windows, warn when the target of an absolute symbolic
link is adjusted.

extract.c: Warn when UNIX metadata is not being extracted

Add support for special files on UNIX

Update version: v1.7.0-BETA

There are too many changes to call the next release 1.6.3.

Recognize tagged metadata items and use for UNIX data

This is undocumented, but the Microsoft implementation seems to allow
variable-length, tagged metadata items to be appended to WIM dentries.
Currently it uses them for Object IDs, which DISM (Windows 8.1) will
backup and restore by default.

This commit adds support for these items, so they can be read and written
unmodified.

In addition, for our UNIX data extension, instead of storing the UNIX
data in the reserved fields of the dentry or in alternate data streams,
store it in a custom tagged item with a randomly chosen tag.  This is
perhaps the best choice compatibility-wise.

split.c: Allow customizing part names

win32_capture.c: Remove unused 'struct winnt_scan_stats' member

update_image.c:  Fix call to progress function in handle_conflict()

journaled_link() needs to be last because it commits the branch.

Also, it's supposed to check WIMLIB_ADD_FLAG_VERBOSE.

win32_apply.c:  Allocate space just before writing each stream

This seems to give better performance compared to allocating space when
each file is created.

win32_apply.c: Fallback to RtlDosPathNameToNtPathName_U()

RtlDosPathNameToNtPathName_U_WithStatus() is not available on Windows XP.

win32_apply.c: Fix error message

win32_apply.c: Use sizeof(wchar_t)

Update progress functions

- Register progress function with WIM instead of explicitly specifying it
  with each function call
- Add support for user-supplied context
- Add support for aborting the current operation by returning a status
  from the progress function

wimlib-imagex: Return --unix-data to help output

New format for UNIX data

This moves the UNIX data into reserved fields of the WIM dentry.

This is theoretically less extensible than the previous format, which was
to add a specially-named alternate data stream entry to each file with
UNIX data.  However, having the UNIX data present in the metadata
resource is simpler and avoids problems when doing sequential extraction.

For now, this also seems to maintain compatibility with the MS
implementation, since it seems simply ignore the reserve fields.

Also, use 32-bit uids, gids, and modes.

Fix path passed to wimboot_set_pointer()

wimexport: Add --wimboot flag

Fix extract progress when hard links not supported

Merge branch 'new_extract'

This rewrites much of the extraction code to give more freedom to
extraction backends about how they extract the files.  This has
advantages for all three backends:

UNIX:  Now does a lot fewer path lookups and should exhibit better data
locality.  Final "set timestamps" pass only processes directories, since
nondirectory timestamps are set before that point.

NTFS-3g:  Now completely based on inode numbers; no paths are ever
created, unless a printable path is needed for an error message.  Got rid
of final "set attributes" and "set timestamps" passes, since all
attributes and timestamps are set before that point.

Windows:  Now uses NT paths relative to the target directory, performs
fewer path lookups, extracts encrypted files without individually reading
ranges from the WIM (expensive for ESD files), and a few other changes.
A lot of code previously in the generic file extract.c actually could be
moved here.

Also, there are no longer any temporary files needed.  All three backends
simply write all the instances of each stream at the same time, which is
more efficient.

Still TODO:
- New format for UNIX data
- Add fallbacks for when number of open files gets too high
- Add fallback for huge encrypted files
- If possible add hardlink and symlink modes back, however these
  are pretty useless.

streamifier_cb(): Adjust cur_stream_offset even if ->consume_chunk() fails

This ensures that ->end_stream() gets called.

dentry.h: Remove unnused declaration of put_dentry()

metadata.h: Parenthesize 'imd' argument to macros

Don't set FILE_ATTRIBUTE_SPARSE on Windows

winnt_openat(): Use FILE_SHARE_VALID_FLAGS

No change in meaning, but this is simpler.

wimextract:  For --to-stdout, set stdout to binary mode on Windows

win32_common.c: Remove duplicate declaration of func_NtOpenFile