减压措施II

Question

下面是对我上一个线程你可以在这里找到的更新。同样，我非常感谢关于程序的结构/逻辑、代码的样式或特性的可重用性的任何建议或评论。

对fread_twelve函数进行了大量修改，以处理从12位到16位的最后一个条目的检测和读取。让我知道你的想法！

我也非常渴望听到我如何平衡堆。瓦兰说我有"778份配给，354份免费“一次运行，但我认为我已经释放了我的所有分配！

/**
 *  file: lzw.h
 *
 *  function declarations for lempel ziv-welch decompression algorithm.
 */

#ifndef LZW_H
#define LZW_H

#include <stdio.h>
#include <stdlib.h>

typedef uint8_t byte;

/**
 *  Frees all blocks between 'from' and 'to' (inclusive) in the dict.
 */
void free_dict (byte* dict[], int from, int to);

/**
 *  Enters the first 256 ASCII values into dict, and their respective sizes into sizes.
 */
void load_dict_defaults (byte* dict[], int sizes[]);

/**
 *  Reads 12 bits from source and returns them as an int.
 */
int fread_twelve(FILE* source);

/**
 *  LZW decompression of source to dest.
 *  Returns 0 if successful, a positive integer otherwise.
 */
int decompress (FILE* source, FILE* dest);

#endif // LZW_H

/**
 *  file: decompress.c
 *
 *  implementation of lempel ziv-welch decompression algorithm using 12-bit fixed-width compression format.
 *
 *  usage: decompress source output
 */

#include "lzw.h"
#include <stdio.h>
#include <stdlib.h>

int main (int argc, char* argv[])
{   
    // check for correct number of args
    if (argc != 3)
    {
        printf("Usage: decompress source output\n");
        return 1;
    }

    // open compressed file
    FILE* source = fopen(argv[1], "rb");
    if (source == NULL)
    {
        printf("Error: cannot open %s\n", argv[1]);
        return 1;
    }

    // open destination file
    FILE* dest = fopen(argv[2], "wb");
    if (dest == NULL)
    {
        printf("Error: cannot open %s\n", argv[2]);
        return 1;
    }

    // decompress
    if (decompress(source, dest) == 1)
    {
        printf("Decompression failed\n");
        fclose(source);
        fclose(dest);
        return 1;
    }
    else
    {
        fclose(source);
        fclose(dest);
        return 0;
    }
}

/**
 *  file: lzw.c
 *  
 *  
 *  Implementation of lempel ziv-welch decompression algorithm using 12-bit fixed-width compression format.
 *
 */

#include "lzw.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

byte* dictionary[4096];
int dict_entry_sizes[4096];

/**
 *  Enters the first 256 ASCII values into dict.
 */
void load_dict_defaults (byte* dict[], int sizes[])
{
    byte* temp;
    byte c = 0;
    for (int i = 0; i < 256; i++)
    {
        temp = malloc(1);
        temp[0] = c++;
        dict[i] = temp;
        dict_entry_sizes[i] = 1;
    }
}

/**
 *  Frees all blocks between 'from' and 'to' (inclusive) in the dict.
 */
void free_dict (byte* dict[], int from, int to)
{
    for (int i = from; i <= to; i++)
    {
        free(dict[i]);
    }
}

/**
 *  Gets 12 bits from source and returns them as an int.
 *  Returns 0 on an error or EOF.
 */
int fread_twelve(FILE* source)
{
    int value;
    static bool left = true;
    static byte prevBytes[2];

    byte buf[3];

    if (left)
    {
        if (fread(buf, 1, 2, source) != 2) 
        {
            // reached eof: even number of entries
            return 0;
        }
        if (fread(buf+2, 1, 1, source) != 1)
        {
            // reached eof: buf[0] and buf[1] are the padded last entry
            value = (buf[0] << 8) | buf[1];
        }
        else
        {
            value = (buf[0] << 4) | (buf[1] >> 4);
            left = false;
            prevBytes[0] = buf[1];
            prevBytes[1] = buf[2];
        }
    }
    else
    {
        value = ((prevBytes[0] & 0x0F) << 8) | prevBytes[1];
        left = true;
    }
    return value;
}

/**
 *  LZW decompression of source to dest.
 *  Returns 0 if successful, a positive integer otherwise.
 */
int decompress (FILE* source, FILE* dest)
{
    load_dict_defaults(dictionary, dict_entry_sizes);

    int dictPos = 256;

    int prevCode, currCode;
    byte* prevString, *currString;

    // read in the first character
    currCode = fread_twelve(source);
    size_t size = dict_entry_sizes[currCode];
    currString = malloc(size + 1); //+1 for upcoming char
    if (currString == NULL)
    {
        fprintf(stderr, "decompress: error assigning currString.\n");
        return 1;
    }
    memcpy(currString, dictionary[currCode], size);
    fwrite(currString, size, 1, dest);
    prevCode = currCode;
    prevString = currString;

    // read in the rest of the characters
    size_t oldSize;
    while ( (currCode = fread_twelve(source)) && currCode )
    {       
        if (currCode > dictPos)
        {
            fprintf(stderr, "decompress: currCode out of dictionary range.\n");
            return 1;
        }

        oldSize = dict_entry_sizes[prevCode];

        if (currCode < dictPos)     // code in dict
        {
            size = dict_entry_sizes[currCode];
            currString = malloc(size + 1); // +1 for adding char on next loop
            if (currString == NULL)
            {
                fprintf(stderr, "decompress: error assigning currString.\n");
                return 1;
            }
            memcpy(currString, dictionary[currCode], size);
            fwrite(currString, size, 1, dest);

            memcpy(prevString + oldSize, currString, 1);
            dictionary[dictPos] = prevString;
            dict_entry_sizes[dictPos++] = oldSize + 1;

            // restart dict if full. 
            if (dictPos >= 4096)
            {
                free_dict(dictionary, 256, 4095);
                dictPos = 256;
            }
        }
        else    // code not in dict until this pass
        {
            memmove(prevString + oldSize, prevString, 1);   // memmove allows overlap
            size = oldSize + 1;
            fwrite(prevString, size, 1, dest);
            dictionary[dictPos] = prevString;
            dict_entry_sizes[dictPos++] = size; 
            currString = malloc(size + 1);  // +1 for adding char on next loop
            if (currString == NULL)
            {
                fprintf(stderr, "decompress: error assigning currString.\n");
                return 1;
            }
            memcpy(currString, prevString, size);
        }
        prevCode = currCode;
        prevString = currString;
    }

    free(prevString);       
    free_dict(dictionary, 0, dictPos-1);

    return 0;
}

Answer 1

前言

在我开始复习之前，我想说在没有编码器的情况下很难测试你的程序。所以我写了我自己的编码器，考虑到了你的译码器规范(12位代码，MSB格式，4096条重设字典，等等)。我还写了我自己的解码器，以确保我的编码器工作。你可以找到这两个项目都在这里。在我的译码器和你的解码器之间有一些谨慎的地方，我将在下面提到。

不需要备忘录1字符

在几个地方，您可以使用memcpy将单个字符插入缓冲区的末尾。您可以简化这些调用：

memcpy(prevString + oldSize, currString, 1);

只想：

        prevString[oldSize] = currString[0];

可以简化代码以添加到字典

中。

您的“使用刚才添加的条目”和“使用现有条目”的两种情况可以合并为一种情况。您可以提前(在需要使用该项之前)处理这两种情况。唯一的区别是新条目的最后一个字符来自哪里。所以我重写了你的循环如下：

    while ( (currCode = fread_twelve(source)) && currCode )
    {
        if (currCode > dictPos)
        {
            fprintf(stderr, "decompress: currCode out of dictionary range.\n");
            return 1;
        }

        oldSize = dict_entry_sizes[prevCode];

        // Add entry to dictionary first, in case we need to use it below.
        if (currCode < dictPos)
            prevString[oldSize] = dictionary[currCode][0];
        else
            prevString[oldSize] = prevString[0];
        dictionary[dictPos] = prevString;
        dict_entry_sizes[dictPos++] = oldSize + 1;

        size = dict_entry_sizes[currCode];
        currString = malloc(size + 1); // +1 for adding char on next loop
        if (currString == NULL)
        {
            fprintf(stderr, "decompress: error assigning currString.\n");
            return 1;
        }
        memcpy(currString, dictionary[currCode], size);
        fwrite(currString, size, 1, dest);

        // restart dict if full.
        if (dictPos >= 4096)
        {
            free_dict(dictionary, 256, 4095);
            dictPos = 256;
        }
        prevCode = currCode;
        prevString = currString;
    }

文件处理的

端

当我编写编码器时，我用四位尾随零输出MSB格式的最后一部分代码。我觉得这是最自然的方法。例如，如果最后一段代码是0x123，最后一段代码是在字节边界上输出的，那么我的编码文件将以以下两个字节结束：12 30。

您的解码器似乎期望最后两个字节看起来如下所示：01 23。在这里，4位填充物来自左侧。虽然这是一种可能的编码，但它需要您的fread_twelve()函数为它做一个特例。如果您使用我的编码，您的文件大小写将看起来像正常的情况，您可以删除它的特殊情况。

字典复位处理

我不确定你的解码器是否正确地处理字典重置。这可能是我的编码器和你的编码器之间的区别。但是当我在我的编码器上运行你的解码器时，它在第一次字典重置后没有同步。如果前面的代码高于255，那么在重置后，您的代码可能会使用一个已释放的字典条目，但根据编码器的不同，我也不确定这是否正确。