Re-visit SHA-1 code

- Fixed build failures when configured with --enable-ssse3-sha1.

- Actually calculate the message digest correctly in the SSSE3-optimized
  version!  The Intel code just does block transformations, not arbitrary
  updates; the previous code did not reflect this.

- Use an appropriate fallback when the CPU does not support SSSE3
  instructions; don't just call abort()!

- Improve sha1_update() and sha1_final().  They should now be slightly
  faster, as well as easier to understand.

- Use beXX_to_cpu() and cpu_to_beXX() macros instead of hard-coding
  endian conversions.

avl_tree.c: Remove avl_set_balance_factor()

Speed up LZ77 match copying

xpress-decompress.c:  Store 'len_hdr' and 'offset_bsr' in unsigned ints

This speeds up XPRESS decompression by about 2%.

finish_write():  Read old integrity table into memory if needed

This is a better fix for the problem, since it doesn't prevent the old
table from being used when it can be.

finish_write(): Don't use old integrity table if already overwritten

When updating a WIM in-place without modifying the lookup table, the new
XML data will spill into the old integrity table if the new XML data is
longer than the old XML data.  Temporarily fix this by not using the old
integrity table in this case.

extract.c: Don't compile unneeded code when WITH_NTFS_3G undefined

extract.c: Do endian conversion when checking pipable WIM header

dentry.c:  Cast name length u16 => u32 whenever adding 2

Due to integer promotion this won't make a difference if an 'int' is 4+
bytes anyway, but make the intention clear: this computation should not
overflow.

read_dentry_tree(): Use dentry_set_name()

Does the same thing but is shorter.

compress_serial.c:  Don't store compressed length in context

It can be a local variable.

compress_parallel.c:  Don't bail if not all threads can be created

If pthread_create() fails but at least 2 threads were created, use them
instead of falling back to serial compression.

compress_parallel.c: Use more appropriate type for shift

chunk_compressor: Use u32 for chunk uncompressed size

All chunk sizes must fit in a 32-bit integer because they cannot exceed
'out_chunk_size'.

make_canonical_huffman_code():  Stricter validation of max_codeword_len

max_codeword_len must be long enough to give a distinct codeword to each
symbol.  As we also check that num_syms >= 2, use this check instead of
max_codeword_len > 0.

compress.c:  Always include base compressor size

When the struct compressor_ops does not provide get_needed_memory(),
still include the size of the struct wimlib_compressor.

{de,}compress.c: Sort ops by type number

capture_common.c: Fix comment

Update NEWS

dentry.c: Fix comment

wimlib.h:  Make beginning of docs a bit more friendly

wimlib.h: Update docs

Remove WIMLIB_COMPRESSION_TYPE_INVALID from library

This is actually only used in wimlib-imagex

wimlib_get_compressor_needed_memory(): Include struct wimlib_compressor

make-windows-release: Include all COPYING files

Update Makefile.am

Update Linux packaging

Update README

Update library license: Add LGPLv3 exception

Place programs in examples/ in public domain

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

lzx-compress.c:  Don't compute match/literal array before actually needed

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