compress.c revision 7e7bd3dccbfe8f79e25e5c1554b5bc3a9aaca321
/**
* compress.c - Compressed attribute handling code. Part of the Linux-NTFS
* project.
*
* Copyright (c) 2004-2005 Anton Altaparmakov
* Copyright (c) 2005 Yura Pakhuchiy
*
* modify it under the terms of the GNU General Public License as published
* by the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* useful, but WITHOUT ANY WARRANTY; without even the implied warranty
* of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program (in the main directory of the Linux-NTFS
* distribution in the file COPYING); if not, write to the Free Software
* Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#ifdef HAVE_STDIO_H
#include <stdio.h>
#endif
#ifdef HAVE_STRING_H
#include <string.h>
#endif
#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif
#ifdef HAVE_ERRNO_H
#include <errno.h>
#endif
#include "attrib.h"
#include "debug.h"
#include "volume.h"
#include "types.h"
#include "layout.h"
#include "runlist.h"
#include "compress.h"
#include "logging.h"
/**
* enum ntfs_compression_constants - constants used in the compression code
*/
typedef enum {
/* Token types and access mask. */
NTFS_SYMBOL_TOKEN = 0,
NTFS_PHRASE_TOKEN = 1,
NTFS_TOKEN_MASK = 1,
/* Compression sub-block constants. */
NTFS_SB_SIZE_MASK = 0x0fff,
NTFS_SB_SIZE = 0x1000,
NTFS_SB_IS_COMPRESSED = 0x8000,
/**
* ntfs_decompress - decompress a compression block into an array of pages
* @dest: buffer to which to write the decompressed data
* @dest_size: size of buffer @dest in bytes
* @cb_start: compression block to decompress
* @cb_size: size of compression block @cb_start in bytes
*
* This decompresses the compression block @cb_start into the destination
* buffer @dest.
*
* @cb_start is a pointer to the compression block which needs decompressing
* and @cb_size is the size of @cb_start in bytes (8-64kiB).
*
* Return 0 if success or -EOVERFLOW on error in the compressed stream.
*/
{
/*
* Pointers into the compressed data, i.e. the compression block (cb),
* and the therein contained sub-blocks (sb).
*/
/* Variables for uncompressed data / destination. */
/* Variables for tag and token parsing. */
int token; /* Loop counter for the eight tokens in tag. */
ntfs_log_debug("Beginning sub-block at offset = 0x%x in the cb.\n",
/*
* Have we reached the end of the compression block or the end of the
* decompressed data? The latter can happen for example if the current
* position in the compression block is one byte before its end so the
* first two checks do not detect it.
*/
ntfs_log_debug("Completed. Returning success (0).\n");
return 0;
}
/* Setup offset for the current sub-block destination. */
/* Check that we are still within allowed boundaries. */
if (dest_sb_end > dest_end)
goto return_overflow;
/* Does the minimum size of a compressed sb overflow valid range? */
goto return_overflow;
/* Setup the current sub-block source pointers and validate range. */
cb_sb_start = cb;
+ 3;
goto return_overflow;
/* Now, we are ready to process the current sub-block (sb). */
ntfs_log_debug("Found uncompressed sub-block.\n");
/* This sb is not compressed, just copy it into destination. */
/* Advance source position to first data byte. */
cb += 2;
/* An uncompressed sb must be full size. */
goto return_overflow;
/* Copy the block and advance the source position. */
cb += NTFS_SB_SIZE;
/* Advance destination position to next sub-block. */
dest += NTFS_SB_SIZE;
goto do_next_sb;
}
ntfs_log_debug("Found compressed sub-block.\n");
/* This sb is compressed, decompress it into destination. */
/* Forward to the first tag in the sub-block. */
cb += 2;
/* Check if the decompressed sub-block was not full-length. */
if (dest < dest_sb_end) {
ntfs_log_debug("Filling incomplete sub-block with zeroes.\n");
/* Zero remainder and update destination position. */
}
/* We have finished the current sub-block. */
goto do_next_sb;
}
/* Check we are still in range. */
goto return_overflow;
/* Get the next tag and advance to first token. */
/* Parse the eight tokens described by the tag. */
register u16 i;
/* Check if we are done / still in range. */
break;
/* Determine token type and parse appropriately.*/
/*
* We have a symbol token, copy the symbol across, and
* advance the source and destination positions.
*/
/* Continue with the next token. */
continue;
}
/*
* We have a phrase token. Make sure it is not the first tag in
* the sb as this is illegal and would confuse the code below.
*/
if (dest == dest_sb_start)
goto return_overflow;
/*
* Determine the number of bytes to go back (p) and the number
* of bytes to copy (l). We use an optimized algorithm in which
* we first calculate log2(current destination position in sb),
* which allows determination of l and p in O(1) rather than
* O(n). We just need an arch-optimized log2() function now.
*/
lg = 0;
lg++;
/* Get the phrase token into i. */
/*
* Calculate starting position of the byte sequence in
* the destination using the fact that p = (pt >> (12 - lg)) + 1
* and make sure we don't go too far back.
*/
if (dest_back_addr < dest_sb_start)
goto return_overflow;
/* Now calculate the length of the byte sequence. */
/* Verify destination is in range. */
goto return_overflow;
/* The number of non-overlapping bytes. */
if (length <= max_non_overlap) {
/* The byte sequence doesn't overlap, just copy it. */
/* Advance destination pointer. */
} else {
/*
* The byte sequence does overlap, copy non-overlapping
* part and then do a slow byte by byte copy for the
* overlapping part. Also, advance the destination
* pointer.
*/
dest += max_non_overlap;
while (length--)
*dest++ = *dest_back_addr++;
}
/* Advance source position and continue with the next token. */
cb += 2;
}
/* No tokens left in the current tag. Continue with the next tag. */
goto do_next_tag;
ntfs_log_debug("Failed. Returning -EOVERFLOW.\n");
return -1;
}
/**
* ntfs_is_cb_compressed - internal function, do not use
*
* This is a very specialised function determining if a cb is compressed or
* uncompressed. It is assumed that checking for a sparse cb has already been
* performed and that the cb is not sparse. It makes all sorts of other
* assumptions as well and hence it is not useful anywhere other than where it
* is used at the moment. Please, do not make this function available for use
* outside of compress.c as it is bound to confuse people and not do what they
* want.
*
* Return TRUE on errors so that the error will be detected later on in the
* code. Might be a bit confusing to debug but there really should never be
* errors coming from here.
*/
{
/*
* The simplest case: the run starting at @cb_start_vcn contains
* @cb_clusters clusters which are all not sparse, thus the cb is not
* compressed.
*/
while (cb_clusters > 0) {
/* Go to the next run. */
rl++;
/* Map the next runlist fragment if it is not mapped. */
return TRUE;
/*
* If the runs were merged need to deal with the
* resulting partial run so simply restart.
*/
goto restart;
}
/* If the current run is sparse, the cb is compressed. */
return TRUE;
/* If the whole cb is not sparse, it is not compressed. */
return FALSE;
};
/* All cb_clusters were not sparse thus the cb is not compressed. */
return FALSE;
}
/**
* ntfs_compressed_attr_pread - read from a compressed attribute
* @na: ntfs attribute to read from
* @pos: byte position in the attribute to begin reading from
* @count: number of bytes to read
* @b: output data buffer
*
* NOTE: You probably want to be using attrib.c::ntfs_attr_pread() instead.
*
* This function will read @count bytes starting at offset @pos from the
* compressed ntfs attribute @na into the data buffer @b.
*
* On success, return the number of successfully read bytes. If this number
* is lower than @count this means that the read reached end of file or that
* an error was encountered during the read so that the read is partial.
* 0 means end of file or nothing was read (also return 0 when @count is 0).
*
* On error and nothing has been read, return -1 with errno set appropriately
* to the return code of ntfs_pread(), or to EINVAL in case of invalid
* arguments.
*/
{
int err;
unsigned int nr_cbs, cb_clusters;
ntfs_log_trace("Entering for inode 0x%llx, attr 0x%x, pos 0x%llx, count 0x%llx.\n",
return -1;
}
/*
* Encrypted attributes are not supported. We return access denied,
* which is what Windows NT4 does, too.
*/
if (NAttrEncrypted(na)) {
return -1;
}
if (!count)
return 0;
/* Truncate reads beyond end of attribute. */
return 0;
}
}
/* If it is a resident attribute, simply use ntfs_attr_pread(). */
if (!NAttrNonResident(na))
/* Zero out reads beyond initialized size. */
return count;
}
}
/* Need a temporary buffer for each loaded compression block. */
if (!cb)
return -1;
/* Need a temporary buffer for each uncompressed block. */
if (!dest) {
return -1;
}
/*
* The first vcn in the first compression block (cb) which we need to
* decompress.
*/
/* Offset in the uncompressed cb at which to start reading data. */
/*
* The first vcn in the cb after the last cb which we need to
* decompress.
*/
/* Number of compression blocks (cbs) in the wanted vcn range. */
nr_cbs--;
start_vcn += cb_clusters;
/* Check whether the compression block is sparse. */
if (total)
return total;
/* FIXME: Do we want EIO or the error code? (AIA) */
return -1;
}
/* Sparse cb, zero out destination range overlapping the cb. */
ntfs_log_debug("Found sparse compression block.\n");
ofs = 0;
/*
* Uncompressed cb, read it straight into the destination range
* overlapping the cb.
*/
ntfs_log_debug("Found uncompressed compression block.\n");
/*
* Read the uncompressed data into the destination buffer.
* NOTE: We cheat a little bit here by marking the attribute as
* not compressed in the ntfs_attr structure so that we can
* read the data by simply using ntfs_attr_pread(). (-8
* NOTE: we have to modify data_size and initialized_size
* temporarily as well...
*/
do {
if (br < 0) {
if (total)
return total;
return br;
}
} while (to_read > 0);
ofs = 0;
} else {
/*
* Compressed cb, decompress it into the temporary buffer, then
* copy the data to the destination range overlapping the cb.
*/
ntfs_log_debug("Found compressed compression block.\n");
/*
* Read the compressed data into the temporary buffer.
* NOTE: We cheat a little bit here by marking the attribute as
* not compressed in the ntfs_attr structure so that we can
* read the raw, compressed data by simply using
* ntfs_attr_pread(). (-8
* NOTE: We have to modify data_size and initialized_size
* temporarily as well...
*/
do {
if (br < 0) {
if (total)
return total;
return br;
}
} while (to_read > 0);
/* Just a precaution. */
ntfs_log_debug("Successfully read the compression block.\n");
if (total)
return total;
return -1;
}
ofs = 0;
}
/* Do we have more work to do? */
if (nr_cbs)
goto do_next_cb;
/* We no longer need the buffers. */
/* Return number of bytes read. */
}