arrays - C 压缩器 - 数组下标的类型为 char

Question

我是一个真正的 C 初学者，所以我不知道为什么会出现这个错误。我将代码发送给我的 friend ，它对他有用，没有任何错误，也没有改变。我在 Oracle VM VirtualBox 上运行它。压缩程序还有更多文件。当我想使用 cmake 创建 Makefile 和正在运行的程序时，就会发生这种情况。

错误出在条件 if(isLeaf(root)) 的函数 buildDictionary 中。

我应该如何解决这个问题？有什么想法吗？

#include "huffman.h"

void buildDictionary(struct MinHeapNode *root, int arr[], int top, HuffmanDictionary *dictionary) {
    if (root->left) {
        arr[top] = 0;
        buildDictionary(root->left, arr, top + 1, dictionary);
    }

    if (root->right) {
        arr[top] = 1;
        buildDictionary(root->right, arr, top + 1, dictionary);
    }

    if (isLeaf(root)) {
        dictionary->symbol[root->data] = root->data;
        dictionary->code[root->data].code = encodeBits(arr, top);
        dictionary->code[root->data].size = top;
    }
}

void printDictionary(HuffmanDictionary *dictionary) {
    for (int i = 0; i < 256; i++) {
        int bs[MAX_TREE_HT];
        decodeBits(dictionary->code[i].code, dictionary->code[i].size, bs);
        printf("%c:", dictionary->symbol[i]);
        for (int a = 0; a < dictionary->code[i].size; a++) {
            printf("%d", bs[a]);
        }
        printf("\n");
    }
}

long huffman_compress(const uint8_t *src, long size, uint8_t *dst, HuffmanDictionary *dictionary) {
    FreqencyData *fd = malloc(sizeof(FreqencyData) * 256);
    buildFrequencyData(src, size, fd);
    uint8_t words[256];
    int frequencies[256];
    int count = 0;
    for (int a = 0; a < 256; a++) {
        if (fd[a].frequency > 0) {
            words[count] = (uint8_t) a;
            frequencies[count] = fd[a].frequency;
            count++;
        }
    }

    struct MinHeapNode *root
            = buildHuffmanTree(words, frequencies, count);
    int arr[MAX_TREE_HT], top = 0;

    buildDictionary(root, arr, top, dictionary);
    uint8_t *bits = malloc(size * MAX_TREE_HT);
    memset(bits, 0, size * MAX_TREE_HT);

    long numOfBits = 0;
    for (long i = 0; i < size; i++) {
        int n = dictionary->code[src[i]].size;
        uint32_t b = dictionary->code[src[i]].code;
        int bs[n];
        decodeBits(b, n, bs);
        for (int a = 0; a < n; a++) {
            bits[numOfBits + a] = bs[a];
        }
        numOfBits += n;
    }

    long cx = 0;
    for (long i = 0; i < numOfBits; i += 8) {
        int bs[8];
        for (int a = 0; a < 8; a++) {
            bs[a] = bits[i + a];
        }
        dst[cx] = encodeBitsArr(bs);
        cx++;
    }
    return cx;
}

uint32_t encodeBits(int arr[], int n) {
    uint32_t ret = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == 1) {
            ret += pow(2, i);
        }
    }

    return ret;
}

uint8_t encodeBitsArr(const int arr[8]) {
    uint8_t ret = 0;
    for (int i = 0; i < 8; i++) {
        if (arr[i] == 1) {
            ret += pow(2, i);
        }
    }

    return ret;
}

void decodeBits(uint32_t b, int n, int bits[]) {
    for (int i = 0; i < n; i++) {
        bits[i] = (int) ((b >> i) & ONE_BIT_MASK_32BITS) != 0;
    }
}

void decodeBitsFromByte(uint8_t b, int bits[]) {
    for (int i = 0; i < 8; i++) {
        bits[i] = (int) ((b >> i) & 0x01) != 0;
    }
}

int findMatchingSymbol(const int bits[MAX_TREE_HT], HuffmanDictionary *dictionary,int* foundSize) {
    for (int i = 0; i < 256; i++) {
        int bs[MAX_TREE_HT];
        decodeBits(dictionary->code[i].code, dictionary->code[i].size, bs);
        bool found = false;
        for (int a = 0; a < dictionary->code[i].size; a++) {
            if (bs[a] == bits[a]) {
                found = true;
            } else {
                found = false;
                break;
            }
        }

        if (found) {
            *foundSize = dictionary->code[i].size - 1;
            return dictionary->symbol[i];
        }
    }

    return -1;
}

long huffman_extract(const uint8_t *src, long size, uint8_t *dst, HuffmanDictionary *dictionary) {
    uint8_t *bits = malloc(size * 8);
    memset(bits, 0, size * 8);

    for (long i = 0; i < size; i++) {
        int bs[8];
        decodeBitsFromByte(src[i], bs);
        for (int a = 0; a < 8; a++) {
            bits[(i * 8) + a] = bs[a];
        }
    }

    long foundBytes = 0;
    int bs[MAX_TREE_HT];
    for (long l = 0; l < size * 8; l++) {
        for (int a = 0; a < MAX_TREE_HT; a++) {
            bs[a] = bits[l + a];
        }
        int* foundSize = malloc(sizeof(int));

        uint8_t b = findMatchingSymbol(bs, dictionary, foundSize);
        if (b >= 0) {
            dst[foundBytes] = b;
            l+= *foundSize;
            foundBytes++;
        }
    }

    return foundBytes;
}

void buildFrequencyData(const uint8_t *src, long size, FreqencyData *fd) {
    for (long i = 0; i < size; i++) {
        fd[src[i]].frequency++;
    }
}

struct MinHeapNode *newNode(uint8_t data, unsigned freq) {
    struct MinHeapNode *temp = (struct MinHeapNode *)malloc(
            sizeof(struct MinHeapNode));

    temp->left = temp->right = NULL;
    temp->data = data;
    temp->freq = freq;

    return temp;
}

struct MinHeap *createMinHeap(unsigned capacity) {
    struct MinHeap *minHeap
            = (struct MinHeap *) malloc(sizeof(struct MinHeap));

    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (struct MinHeapNode **)malloc(
            minHeap->capacity * sizeof(struct MinHeapNode *));
    return minHeap;
}

void swapMinHeapNode(struct MinHeapNode **a,
                     struct MinHeapNode **b) {
    struct MinHeapNode *t = *a;
    *a = *b;
    *b = t;
}

void minHeapify(struct MinHeap *minHeap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < minHeap->size
        && minHeap->array[left]->freq
           < minHeap->array[smallest]->freq)
        smallest = left;

    if (right < minHeap->size
        && minHeap->array[right]->freq
           < minHeap->array[smallest]->freq)
        smallest = right;

    if (smallest != idx) {
        swapMinHeapNode(&minHeap->array[smallest],
                        &minHeap->array[idx]);
        minHeapify(minHeap, smallest);
    }
}

int isSizeOne(struct MinHeap *minHeap) {
    return (minHeap->size == 1);
}

struct MinHeapNode *extractMin(struct MinHeap *minHeap) {
    struct MinHeapNode *temp = minHeap->array[0];
    minHeap->array[0] = minHeap->array[minHeap->size - 1];

    --minHeap->size;
    minHeapify(minHeap, 0);

    return temp;
}

void insertMinHeap(struct MinHeap *minHeap,
                   struct MinHeapNode *minHeapNode) {
    ++minHeap->size;
    int i = minHeap->size - 1;

    while (i
           && minHeapNode->freq
              < minHeap->array[(i - 1) / 2]->freq) {

        minHeap->array[i] = minHeap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }

    minHeap->array[i] = minHeapNode;
}

void buildMinHeap(struct MinHeap *minHeap) {
    int n = minHeap->size - 1;
    int i;

    for (i = (n - 1) / 2; i >= 0; --i)
        minHeapify(minHeap, i);
}

int isLeaf(struct MinHeapNode *root) {
    return !(root->left) && !(root->right);
}

struct MinHeap *createAndBuildMinHeap(uint8_t data[],
                                      int freq[], int size) {
    struct MinHeap *minHeap = createMinHeap(size);

    for (int i = 0; i < size; ++i)
        minHeap->array[i] = newNode(data[i], freq[i]);

    minHeap->size = size;
    buildMinHeap(minHeap);

    return minHeap;
}

struct MinHeapNode *buildHuffmanTree(uint8_t data[],
                                     int freq[], int size) {
    struct MinHeapNode *left, *right, *top;

    struct MinHeap *minHeap
            = createAndBuildMinHeap(data, freq, size);

    while (!isSizeOne(minHeap)) {
        left = extractMin(minHeap);
        right = extractMin(minHeap);

        top = newNode('$', left->freq + right->freq);

        top->left = left;
        top->right = right;

        insertMinHeap(minHeap, top);
    }

    return extractMin(minHeap);
}

我没有尝试任何操作，因为代码在其他计算机上正常运行，但在我的计算机上却运行不正常。

Answer 1

在头文件 huffman.h 中，结构体 MinHeapNode 有一个类型为 char 的成员 data，在默认情况下对 char 类型进行签名的某些体系结构上，可以具有负值。这会在索引 dictionary->symbol[root->data] 或 dictionary->code[root->data] 时导致未定义的行为，因为您将取消引用外部元素数组边界。只需将类型更改为 unsigned char 或 uint8_t 即可避免此问题并修复警告，即 -Werror 变成了错误。