system/core: move libsparse into system/core

This moves an exact copy of libsparse from
system/extras/ext4_utils/libsparse to system/core/libsparse in
preparation for linking tools in system/core against it.

Change-Id: If664e4fcfd6612844ac745589beb1517e7f9fe58
libsparse: remove static variables

Removes static variables in backed_block.c to allow multiple
sparse files to be open at the same time.

Change-Id: I012d8a424c6e21a7352408416adb7c72ee8add21
libsparse: cleanups

Move block loops into sparse.c with iterator helpers in backed_block.c.
Simplify chunk writing by moving skip chunk calls from output_file.c to
sparse.c.
Rename variables to be consistent with new naming.
Remove use of u8, u32, u64.

Change-Id: Ic138ad58bef9f96239266ccee12ee83ea285e7eb
libsparse: add support for including fds

Add sparse_file_add_fd to include all or part of the contents
of an fd in the output file.  Will be useful for re-sparsing files
where fd will point to the input sparse file.

Change-Id: I5d4ab07fb37231e8e9c1912f62a2968c8b0a00ef
libsparse: add error reporting functions

Change-Id: I2f21355b6c5339d1d724b4c121ea30d575b2d366
libsparse: merge adjacent blocks of the same type

When a block is added that is adjacent to another block and of the same
type, merge it.  This will be useful for converting regular images to
sparse images, allowing the reader to add a single block at a time and
letting libsparse optimize into larger blocks as it goes.

Does not support merge two blocks that are backed by a data pointer,
only blocks that are backed by a file for now.

Change-Id: I95aa231714cbe01ac194e868c21385806c0bdb97
libsparse: fix windows image writing

Fix write_fd_chunk on windows.  Uses malloc and read instead of mmap.

Change-Id: I75f10db2e04f19e7f3a6ff46b6978d143cb5254e
libsparse: add sparse_file read and convert tools to use it

Abstract the logic from simg2img into libsparse, and add logic
for reading a regular image into libsparse.  simg2img then
becomes a simple wrapper around libsparse.

img2simg was not actually making the file sparse, it was using
sparse files to create multiple files that could be pieced back
together.  Replace it with a simple wrapper around libsparse.
Its functionality will be replaced by an simg2simg that can
resparse a file into smaller chunks.

Change-Id: I266f70e1c750454183ce46c71a7bb66bbb033a26
libsparse: pseudo-subclass output_file for normal and gz files

Create two subclasses of output_file that can handle normal
and gzipped files, and refactor open_output_fd.  Will allow
adding support for an output_file type that is not file
backed.

Change-Id: I26744c74d13f205cf17df1ea9caac1eea9c57357
libsparse: add callback output file type

Add a new output file subclass that will call a callback for
each block as it is written.  Will be used to measure the space
used by each sparse block to allow resparsing files.

Also add sparse_file_callback, which will write out a sparse
file by calling the provided write function.

Change-Id: I18707bd9c357b68da319cc07982e93d1c2b2bee2
libsparse: add function to resparse a file and a utility to use it

Add sparse_file_repsarse, which splits chunks in an existing sparse
file such that the maximum size of a chunk, plus a header and footer,
is smaller than the given size.  This will allow multiple smaller
sparse files to result in the same data as a large sparse file.

Change-Id: I177abdb958a23d5afd394ff265c5b0c6a3ff22fa
libsparse: add sparse_file_len

Add sparse_file_len, which will compute the size of data that would
be produced if sparse_file_write was called.  Useful combined with
sparse_file_callback.

Change-Id: I1a156d1071760f5559483954a5c62ffc20298703
libsparse: rename symbols that conflict with libext4_utils

Until ext4_utils switches to using libsparse, libext4_utils defines some
of the same symbols as libsparse.  Fastboot links statically against
both of them, and there is no easy way to make the symbols hidden, so
just rename them in libsparse.

Change-Id: Idc2cfe20efe3c3a7fb8233f453a89bbbeb0dcc8b
libsparse: fix 32 bit overflow when calculating last chunk

last_block * s->block_size can overflow when writing large filesystems,
cast to 64 bits before multiplying.

Change-Id: I3e54097852ce7d0fd271eab53d65e666284898e4