ntfs.c

linux下开发的针对所有磁盘的数据恢复的源码

 * is filled with sparse clusters. The entire compression unit
 * can also be sparse. 
 *
 * When the data is compressed, it is broken up into 4k blocks. Each
 * of the blocks is compressed and the resulting data is stored with
 * a 2-byte header that identifies the compressed size.   The 
 * compressed data contains token groups, which contain a 1 byte
 * header followed by 8 variable length tokens.  There are two types
 * of tokens. Symbol tokens are 1 byte in length and the 1byte value
 * should be directly copied into the uncompressed data.  Phrase tokens
 * identify a run of data in the same compression unit that should be 
 * copied to the current location.  Each bit in the 1-byte header identifies
 * the type of the 8 tokens in the group. 
 *
 */

 /* Variables used for ntfs_uncompress() method */
typedef struct {
    char *uncomp_buf;           // Buffer for uncompressed data
    char *comp_buf;             // buffer for compressed data
    size_t comp_len;            // number of bytes used in compressed data
    size_t uncomp_idx;          // Index into buffer for next byte
    size_t buf_size_b;          // size of buffer in bytes (1 compression unit)
} NTFS_COMP_INFO;


/**
 * Reset the values in the NTFS_COMP_INFO structure.  We need to 
 * do this in between every compression unit that we process in the file.
 *
 * @param comp Structure to reset
 */
static void
ntfs_uncompress_reset(NTFS_COMP_INFO * comp)
{
    memset(comp->uncomp_buf, 0, comp->buf_size_b);
    comp->uncomp_idx = 0;
    memset(comp->comp_buf, 0, comp->buf_size_b);
    comp->comp_len = 0;
}

/**
 * Setup the NTFS_COMP_INFO structure with a buffer and 
 * initialize the basic settings.
 *
 * @param fs File system state information
 * @param comp Compression state information to initialize
 * @param compunit_size_c The size (in clusters) of a compression
 * unit
 * @return 1 on error and 0 on success
 */
static int
ntfs_uncompress_setup(TSK_FS_INFO * fs, NTFS_COMP_INFO * comp,
    uint32_t compunit_size_c)
{
    comp->buf_size_b = fs->block_size * compunit_size_c;
    if ((comp->uncomp_buf = tsk_malloc(comp->buf_size_b)) == NULL) {
        comp->buf_size_b = 0;
        return 1;
    }
    if ((comp->comp_buf = tsk_malloc(comp->buf_size_b)) == NULL) {
        comp->buf_size_b = 0;
        return 1;
    }

    ntfs_uncompress_reset(comp);

    return 0;
}

static void
ntfs_uncompress_done(NTFS_COMP_INFO * comp)
{
    if (comp->uncomp_buf)
        free(comp->uncomp_buf);
    comp->uncomp_buf = NULL;
    if (comp->comp_buf)
        free(comp->comp_buf);
    comp->comp_buf = NULL;
    comp->buf_size_b = 0;
}


 /**
  * Uncompress the block of data in comp->comp_buf, 
  * which has a size of comp->comp_len.
  * Store the result in the comp->uncomp_buf. 
  *
  * @param comp Compression unit structure
  *
  * @returns 1 on error and 0 on success
  */
static uint8_t
ntfs_uncompress_compunit(NTFS_COMP_INFO * comp)
{
    size_t cl_index;

    tsk_error_reset();

    comp->uncomp_idx = 0;

    /* Cycle through the compressed data 
     * We maintain state using different levels of loops.
     * We use +1 here because the size value at start of block is 2 bytes.
     */
    for (cl_index = 0; cl_index + 1 < comp->comp_len;) {
        size_t blk_end;         // index into the buffer to where block ends
        size_t blk_size;        // size of the current block 
        uint8_t iscomp;         // set to 1 if block is compressed
        size_t blk_st_uncomp;   // index into uncompressed buffer where block started

        /* The first two bytes of each block contain the size
         * information.*/
        blk_size = ((((unsigned char) comp->comp_buf[cl_index + 1] << 8) |
                ((unsigned char) comp->comp_buf[cl_index])) & 0x0FFF) + 3;

        // this seems to indicate end of block
        if (blk_size == 3)
            break;

        blk_end = cl_index + blk_size;
        if (blk_end > comp->comp_len) {
            tsk_errno = TSK_ERR_FS_FWALK;
            snprintf(tsk_errstr, TSK_ERRSTR_L,
                "ntfs_uncompress_compunit: Block length longer than buffer length: %"
                PRIuSIZE "", blk_end);
            return 1;
        }

        if (tsk_verbose)
            tsk_fprintf(stderr,
                "ntfs_uncompress_compunit: Block size is %" PRIuSIZE "\n",
                blk_size);

        /* The MSB identifies if the block is compressed */
        if ((comp->comp_buf[cl_index + 1] & 0x8000) == 0)
            iscomp = 0;
        else
            iscomp = 1;

        // keep track of where this block started in the buffer
        blk_st_uncomp = comp->uncomp_idx;
        cl_index += 2;

        // the 4096 size seems to occur at the same times as no compression
        if ((iscomp) || (blk_size - 2 != 4096)) {

            // cycle through the block
            while (cl_index < blk_end) {
                int a;

                // get the header header
                unsigned char header = comp->comp_buf[cl_index];
                cl_index++;

                if (tsk_verbose)
                    tsk_fprintf(stderr,
                        "ntfs_uncompress_compunit: New Tag: %x\n", header);

                for (a = 0; a < 8 && cl_index < blk_end; a++) {

                    /* Determine token type and parse appropriately. *
                     * Symbol tokens are the symbol themselves, so copy it
                     * into the umcompressed buffer 
                     */
                    if ((header & NTFS_TOKEN_MASK) == NTFS_SYMBOL_TOKEN) {
                        if (tsk_verbose)
                            tsk_fprintf(stderr,
                                "ntfs_uncompress_compunit: Symbol Token: %"
                                PRIuSIZE "\n", cl_index);

                        if (comp->uncomp_idx >= comp->buf_size_b) {
                            tsk_errno = TSK_ERR_FS_FWALK;
                            snprintf(tsk_errstr, TSK_ERRSTR_L,
                                "ntfs_uncompress_compunit: Trying to write past end of uncompression buffer: %"
                                PRIuSIZE "", comp->uncomp_idx);
                            return 1;
                        }
                        comp->uncomp_buf[comp->uncomp_idx++] =
                            comp->comp_buf[cl_index];

                        cl_index++;
                    }

                    /* Otherwise, it is a phrase token, which points back
                     * to a previous sequence of bytes. 
                     */
                    else {
                        size_t i;
                        int shift;
                        size_t start_position_index = 0;
                        size_t end_position_index = 0;
                        unsigned int offset = 0;
                        unsigned int length = 0;
                        uint16_t pheader;

                        if (cl_index + 1 >= blk_end) {
                            tsk_errno = TSK_ERR_FS_FWALK;
                            snprintf(tsk_errstr, TSK_ERRSTR_L,
                                "ntfs_uncompress_compunit: Phrase token index is past end of block: %d",
                                a);
                            return 1;
                        }

                        pheader =
                            ((((comp->comp_buf[cl_index +
                                            1]) << 8) & 0xFF00) |
                            (comp->comp_buf[cl_index] & 0xFF));
                        cl_index += 2;


                        /* The number of bits for the start and length              
                         * in the 2-byte header change depending on the 
                         * location in the compression unit.  This identifies
                         * how many bits each has */
                        shift = 0;
                        for (i =
                            comp->uncomp_idx -
                            blk_st_uncomp - 1; i >= 0x10; i >>= 1) {
                            shift++;
                        }

                        //tsk_fprintf(stderr, "Start: %X  Shift: %d  UnComp_IDX %d  BlkStart: %lu  BlkIdx: %d  BlkSize: %d\n", (int)(comp->uncomp_idx - comp->blk_st - 1), shift, comp->uncomp_idx, comp->blk_st, comp->blk_idx, comp->blk_size);

                        offset = (pheader >> (12 - shift)) + 1;
                        length = (pheader & (0xFFF >> shift)) + 2;

                        start_position_index = comp->uncomp_idx - offset;
                        end_position_index = start_position_index + length;

                        if (tsk_verbose)
                            tsk_fprintf(stderr,
                                "ntfs_uncompress_compunit: Phrase Token: %"
                                PRIuSIZE "\t%d\t%d\t%x\n", cl_index,
                                length, offset, pheader);

                        /* Sanity checks on values */
                        if (offset > comp->uncomp_idx) {
                            tsk_error_reset();
                            tsk_errno = TSK_ERR_FS_FWALK;
                            snprintf(tsk_errstr, TSK_ERRSTR_L,
                                "ntfs_uncompress_compunit: Phrase token offset is too large:  %d (max: %"
                                PRIuSIZE ")", offset, comp->uncomp_idx);
                            return 1;
                        }
                        else if (length + start_position_index >
                            comp->buf_size_b) {
                            tsk_error_reset();
                            tsk_errno = TSK_ERR_FS_FWALK;
                            snprintf(tsk_errstr, TSK_ERRSTR_L,
                                "ntfs_uncompress_compunit: Phrase token length is too large:  %d (max: %zu)",
                                length,
                                comp->buf_size_b - start_position_index);
                            return 1;
                        }
                        else if (end_position_index -
                            start_position_index + 1 >
                            comp->buf_size_b - comp->uncomp_idx) {
                            tsk_error_reset();
                            tsk_errno = TSK_ERR_FS_FWALK;
                            snprintf(tsk_errstr, TSK_ERRSTR_L,
                                "ntfs_uncompress_compunit: Phrase token length is too large for rest of uncomp buf:  %zu (max: %"
                                PRIuSIZE ")",
                                end_position_index - start_position_index +
                                1, comp->buf_size_b - comp->uncomp_idx);
                            return 1;
                        }

                        for (;
                            start_position_index <= end_position_index
                            && comp->uncomp_idx < comp->buf_size_b;
                            start_position_index++) {

                            // Copy the previous data to the current position
                            comp->uncomp_buf[comp->uncomp_idx++]
                                = comp->uncomp_buf[start_position_index];
                        }
                    }
                    header >>= 1;
                }               // end of loop inside of token group

            }                   // end of loop inside of block
        }

        // this block contains uncompressed data uncompressed data
        else {
            while (cl_index < blk_end && cl_index < comp->comp_len) {
                /* This seems to happen only with corrupt data -- such as
                 * when an unallocated file is being processed... */
                if (comp->uncomp_idx >= comp->buf_size_b) {
                    tsk_error_reset();
                    tsk_errno = TSK_ERR_FS_FWALK;
                    snprintf(tsk_errstr, TSK_ERRSTR_L,
                        "ntfs_uncompress_compunit: Trying to write past end of uncompression buffer (1) -- corrupt data?)");
                    return 1;
                }

                // Place data in uncompression_buffer
                comp->uncomp_buf[comp->uncomp_idx++] =
                    comp->comp_buf[cl_index++];
            }
        }
    }                           // end of loop inside of compression unit

    return 0;
}



/**
 * Process a compression unit and return the decompressed data in a buffer in comp. 
 *
 * @param ntfs File system
 * @param comp Compression state info (output will be stored in here)
 * @param comp_unit List of addresses that store compressed data
 * @param comp_unit_size Number of addresses in comp_unit
 * @returns 1 on error and 0 on success
 */
static uint8_t
ntfs_proc_compunit(NTFS_INFO * ntfs, NTFS_COMP_INFO * comp,
    TSK_DADDR_T * comp_unit, uint32_t comp_unit_size)
{
    TSK_FS_INFO *fs = (TSK_FS_INFO *) ntfs;
    int sparse;
    uint64_t a;

    /* With compressed attributes, there are three scenarios.
     * 1: The compression unit is not compressed,
     * 2: The compression unit is sparse
     * 3: The compression unit is compressed
     */

    /* Check if the entire compression unit is sparse */
    sparse = 1;
    for (a = 0; a < comp_unit_size && sparse == 1; a++) {
        if (comp_unit[a]) {
            sparse = 0;
            break;
        }
    }

    /* Entire comp unit is sparse... */
    if (sparse) {
        if (tsk_verbose)
            tsk_fprintf(stderr,
                "ntfs_proc_compunit: Unit is fully sparse\n");

        memset(comp->uncomp_buf, 0, comp->buf_size_b);
        comp->uncomp_idx = comp->buf_size_b;
    }

    /* Check if the end of the unit is sparse, which means the
     * unit is compressed */
    else if (comp_unit[comp_unit_size - 1] == 0) {

        if (tsk_verbose)
            tsk_fprintf(stderr,
                "ntfs_proc_compunit: Unit is compressed\n");

        // load up the compressed buffer so we can decompress it