Compression: Adapthuff Buggy: Help!

Hi! I've been working on file compression for years. Recently, I thought I made a breakthrough but then realized that my rendition of Adaptive Huffman codes is very buggy: starting at the first byte compressed with AdaptHuff, the whole file is corrupt. I attached some example code in the hopes that somebody here can find the bug(s). Any help would be appreciated.

 

In comp huffman.c.txt:

The code you've provided appears to be an implementation of **Adaptive Huffman coding**. While I don't see any glaring syntax errors, there are a few points to consider:
1. **Initialization of `HuffEnv`**:
- The `InitHuffTree` function initializes the `HuffEnv` structure. However, it seems that the variable `tmpcptr` is used without being declared or defined. You might want to ensure that `tmpcptr` is properly declared and initialized before using it in the loop.
2. **Bit Manipulation**:
- In the `WriteB2` function, the line `d=(d<<1)|e2->bit;` performs a bitwise left shift (`<<`) followed by a bitwise OR (`|`). This operation is commonly used for bit manipulation, but it's essential to understand its purpose in the context of Huffman coding.
- Make sure that the `writeoutf` function (which is not defined in the provided code snippet) correctly handles the compressed data.
3. **Boundary Conditions**:
- The `GetHuffGreatestInBlock` function searches for the highest node with the current node's weight. However, the loop condition `tmpcptr>=c` might need further validation to ensure it doesn't go out of bounds.
- Similarly, in the `UpdateHuffCode` function, the condition `if (n>=512)` should be carefully reviewed to avoid accessing invalid memory locations.
4. **Missing Definitions**:
- Some functions, such as `writeoutf`, are referenced but not defined in the snippet. You'll need to provide their implementations or replace them with appropriate I/O operations.
5. **Overall Context**:
- Without the complete context (including the missing parts of the code), it's challenging to identify any other potential issues or bugs.
Remember to verify the missing parts of the code, ensure proper initialization, and test the implementation thoroughly.

 

Everything you say seems to check out. When I get the first hit that is not a NYT, the wrong byte appears: one that appeared before but the wrong one. After that, the whole file is corrupt. I'm thinking I'm not writing the bits properly. Maybe I'm not updating the tree properly. Can you give me an URL to information on AdaptHuff that's better than Wikipedia's article? It's a little confusing.

 

First look at the references section in the Wikipedia article: Adaptive Huffman coding - Wikipedia. This leads you to the original papers on the subject at: Vit87.jacmACMversion.pdf (ku.edu) and adaptive Huffman coding (nist.gov). Also, follow the external links.

Second look at and search other implementations and their interpretation within Github, for example: adaptive-huffman-coding/README.md at master · seanwu1105/adaptive-huffman-coding · GitHub

 

I downloaded the second link you provided and plan to look at it later. Thank you. BTW, I think my main problem is that I'm not swapping the right values when updating the tree. What values do I need to swap?

 

Maybe I'm using different values for the bits compressed and decompressed. How do I handle specifying the right bits between the compressor and the decompressor?