Ufyukyu

Question

In a past course one of the assignments was to write a program that can compress files using Huffman Tree algorithm, and uncompress the files that the program generates.

My design is to count the byte occurrences first, then construct a HT based on the counted byte frequency.

My compressed file format is 256*4 bytes of "header" that stores the counted frequency, so it can be used to construct the tree when decompressing the file. Then there's a 4-byte integer that indicates how many bits of the last byte is real data. The rest is the real (compressed) data.

Here is this specific version* of code that I want some feedback. Later versions introduced many messy changes (like GUI and buffered I/O) that is not necessary.

Specifically, I'm looking for feedback on my algorithm and data structure implementation, including but not limited to code style, best practices, potential flaws and defects (see below).

An exception is the last two functions print_help and main. They're intended to be as simple as possible, so they contain the bare minimum amount of code to work in a reasonable way. Data validation and error checking etc. are omitted on purpose.

In order to simplify the idea, during designing and coding, I have assumed that

the program will not be told to uncompress an invalid file, so there's no file validity check in the code

file availability is ensured by the environment. It will always be a regular file, with no chance of generating a read error mid-way

C library functions does not fail for environmental reasons (e.g. host is short of RAM for malloc(3), target disk out of space for fwrite(3) and consequently write(2), or fread(3) as said above)

reading/writing byte-by-byte is fine, because a later version of this code introduced chunk I/O and got a bit messier (I think). Suggestions on making the code run faster without implementing chunk I/O is welcome

so I'm also not looking for feedbacks regarding the above things that I have assumed / intentionally ignored.

I have ensured that the code is working properly, with no warnings when compiled with this command (taken from make output)

gcc -O3 -std=c11 -Wall -Wno-unused-result -o huffman huffman.c

The last option is to suppress the warning about unused result from fread(3).

During my coding process, I run clang-format occasionally and diff the output and my written code to check for potentially bad indentation / styling issues. I am not confident if it can solve everything.

* The link points to my GitHub repo. The code on that page is identical to the code submitted below verbatim.

// File: huffman.c

// Author: iBug



#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <stdint.h>



typedef unsigned char byte;



typedef struct _HuffNode {

    unsigned data;

    struct _HuffNode *left, *right, *parent;

} HuffNode;



void count_frequency(FILE* fp, unsigned* freq) {

    size_t orig_pos = ftell(fp);

    int ch;

    while (1) {

        ch = fgetc(fp);

        if (ch < 0)

            break;

        freq[ch]++;

    }

    fseek(fp, orig_pos, SEEK_SET);

}



void construct_huffman(unsigned* freq_in, HuffNode* tree) {

    int count = 256;

    unsigned freq[256];

    HuffNode *node[256];



    // Initialize data

    for (int i = 0; i < 256; i++) {

        freq[i] = freq_in[i];

        tree[i].data = i;

        tree[i].left = tree[i].right = NULL;

        node[i] = &tree[i];

    }



    // Sort by frequency, decreasing order

    /* WARNING: Although this Quick Sort is an unstable sort,

     * it should at least give the same result for the same input frequency table,

     * therefore I'm leaving this code here

     */

    {

        unsigned lower[256], upper[256], top = 1;

        lower[0] = 0, upper[0] = 256;

        while (top > 0) {

            top--;

            int left = lower[top], right = upper[top];

            int i = left, j = right - 1, flag = 0;

            if (i >= j) // Nothing to sort

                continue;

            while (i < j) {

                if (freq[i] < freq[j]) {

                    unsigned t = freq[i]; freq[i] = freq[j]; freq[j] = t;

                    HuffNode *p = node[i]; node[i] = node[j]; node[j] = p;

                    flag = !flag;

                }

                flag ? i++ : j--;

            }

            lower[top] = left, upper[top] = i;

            lower[top + 1] = i + 1, upper[top + 1] = right;

            top += 2;

        }

    }



    // Construct tree

    while (count > 1) {

        int pos = 512 - count;

        HuffNode *parent = &tree[pos];

        // Select lowest 2 by freq

        int i = count - 2, j = count - 1;

        // Create tree, lower freq left

        parent->left = node[j]; parent->right = node[i];

        node[j]->parent = node[i]->parent = parent;

        node[i] = parent;

        freq[i] += freq[j];

        // Insert

        for (; i > 0 && freq[i] > freq[i - 1]; i--) {

            unsigned t = freq[i]; freq[i] = freq[i - 1]; freq[i - 1] = t;

            HuffNode *p = node[i]; node[i] = node[i - 1]; node[i - 1] = p;

        }

        count--;

    }

    // Now HEAD = node[0] = tree[511]

    node[0]->parent = NULL;

}



void encode_stream(FILE* fin, FILE* fout, HuffNode* tree, unsigned* padding) {

    int n;

    byte ch;

    byte buf = 0, nbuf = 0;

    HuffNode *p;

    byte code[256];

    while (1) {

        n = fgetc(fin);

        if (n < 0)

            break;

        ch = n;



        // Encode

        p = &tree[ch];

        n = 0;

        while (p->parent) {

            if (p == p->parent->left) {

                // Left is 0

                code[n] = 0;

            } else if (p == p->parent->right) {

                code[n] = 1;

            }

            p = p->parent;

            n++;

        }



        // Write

        for (int i = n - 1; i >= 0; i--) {

            buf |= code[i] << nbuf;

            nbuf++;

            if (nbuf == 8) {

                fputc(buf, fout);

                nbuf = buf = 0;

            }

        }

    }

    fputc(buf, fout);

    *padding = 8 - nbuf;

}



void decode_stream(FILE* fin, FILE* fout, HuffNode* tree, unsigned padding) {

    size_t startpos = ftell(fin); // should be 1028

    fseek(fin, 0L, SEEK_END);

    size_t endpos = ftell(fin); // last byte handling

    fseek(fin, startpos, SEEK_SET);

    int count = endpos - startpos;



    byte buf = 0, nbuf = 0, bit;

    HuffNode *p;

    while (count > 0 || nbuf > 0) {

        // Start from tree top

        p = tree + 510;

        while (p->left || p->right) {

            // Prepare next bit if needed

            if (nbuf == 0) {

                if (count <= 0)

                    return;



                buf = fgetc(fin);

                if (count == 1) {

                    // Last bit

                    nbuf = 8 - padding;

                    if (nbuf == 0) {

                        return;

                    }

                } else {

                    nbuf = 8;

                }

                count--;

            }

            // p has child

            bit = buf & 1;

            buf >>= 1;

            nbuf--;

            if (bit == 0)

                p = p->left;

            else

                p = p->right;

        }

        fputc(p->data, fout);

    }

}



void compress_file(const char* filename, const char* newname) {

    FILE *fin = fopen(filename, "rb"),

         *fout = fopen(newname, "wb");



    unsigned freq[256], padding;

    HuffNode tree[512];

    size_t padding_pos;

    count_frequency(fin, freq);

    construct_huffman(freq, tree);

    rewind(fin);

    for (int i = 0; i < 256; i++)

        fwrite(freq + i, 4, 1, fout);

    // Write a placeholder for the padding

    padding_pos = ftell(fout);

    fwrite(&padding, 4, 1, fout);

    encode_stream(fin, fout, tree, &padding);

    // Write the padding to the placeholder

    fseek(fout, padding_pos, SEEK_SET);

    fwrite(&padding, 4, 1, fout);

    fclose(fin);

    fclose(fout);

}



void uncompress_file(const char* filename, const char* newname) {

    FILE *fin = fopen(filename, "rb"),

         *fout = fopen(newname, "wb");



    unsigned freq[256], padding;

    HuffNode tree[512];

    for (int i = 0; i < 256; i++) {

        fread(&padding, 4, 1, fin);

        freq[i] = padding;

    }

    fread(&padding, 4, 1, fin);

    construct_huffman(freq, tree);

    decode_stream(fin, fout, tree, padding);

    fclose(fin);

    fclose(fout);

}



void print_help(void) {

    puts("Usage: huffman (-c|-d) input output");

    puts("  -c    Compress file from input to output");

    puts("  -d    Uncompress file from input to output");

    puts("nCreated by iBug");

}



int main(int argc, char** argv) {

    if (argc != 4) {

        print_help();

        return 1;

    }

    if (!strcmp(argv[1], "-c")) {

        compress_file(argv[2], argv[3]);

    } else if (!strcmp(argv[1], "-d")) {

        uncompress_file(argv[2], argv[3]);

    } else {

        print_help();

        return 1;

    }

    return 0;

}

In addition to the mandatory CC BY-SA 3.0 license by posting on Stack Exchange, the code itself also has a MIT license.

On a side note: Although the course has ended and this code is not maintained anymore, it's still one of the programs that I have written with maximum attention and carefulness, so I believe that any feedback to this code is highly valuable and I will remember them in my future C-coding times.

ReinderienReinderien 4,171822 · Accepted Answer · 2019-01-01 00:34:47Z

Use standard types

You define this:

typedef unsigned char byte;

But you also already #include <stdint.h>. As such, you have access to uint8_t, which is more explicit about its size than char.

Identify local functions

If all of your functions are in the same translation unit (which seems to be the case), make them static.

Forever loops

This is quite minor, but while (1) isn't my favourite way of defining a forever loop. You can either do for (;;) or while (true), after having included stdbool.h. 1 is less expressive than true.

Unite declaration and initialization

int ch;

while (1) {

    ch = fgetc(fp);

can be

while (true) {

    int ch = fgetc(fp);

Define magic numbers

Make a #define or a global const int for 256. It's used all over your code, and it'd be good to replace that with a symbol for legibility and maintainability.

Do one thing at a time

lower[0] = 0, upper[0] = 256;

// ...

unsigned t = freq[i]; freq[i] = freq[j]; freq[j] = t;

It's rarely an improvement to the legibility of code to do multi-statement lines. Just put these on separate lines.

Sanitize loop counters

You have:

unsigned top = 1;

// ...

while (top > 0) {

    top--;

    // ...`continue`s under certain conditions...

    top += 2;

}

This is a little wacky. Just do:

for (int top = 0; top >= 0; top--) {

    // ... continue under certain conditions...

    top += 2;

}

I think those are equivalent.

Sanitize logic

        int flag = 0;

        while (...) {

            if (freq[i] < freq[j]) {

                //...

                flag = !flag;

            }

            flag ? i++ : j--;

        }

This is ternary abuse. The flag should be a bool (from stdbool.h). Rewrite this as:

bool flag = false;

while (...) {

    if (freq[i] < freq[j]) {

        //...

        flag = !flag;

    }

    if (flag) i++;

    else j--;

}

Choose a pointer spacing standard

You do:

void compress_file(const char* filename, const char* newname) {

but you also do:

FILE *fin = fopen(filename, "rb"),

     *fout = fopen(newname, "wb");

Personally I like the latter; either way, you should pick a standard and apply it everywhere.

Let `fwrite` do the iteration

This:

for (int i = 0; i < 256; i++)

    fwrite(freq + i, 4, 1, fout);

is equivalent to:

fwrite(freq, 4, 256, fout);

haroldharold 1,09857 · Accepted Answer · 2018-12-31 19:05:08Z

Header size

256*4 bytes is very big for a header. The size could be reduced substantially by using one or several of these common techniques:

Store the code length instead of symbol frequency. These definitely won't need 32 bits each, 8 would already be a lot. You can pack them in 4 bits each if you set a length limit of 15. Storing lengths is not ambiguous because you can use canonical Huffman codes (there is an easy algorithm to generate them from your table of code lengths, discarding the code itself).

Compress the header with delta encoding: storing the length difference between subsequent codes, using a variable-length encoding. Small differences tend to be more common. (seen in eg DEFLATE)

Remove most zero-lengths from the header, by first storing a sparse bitmap that indicates which symbols occur in the file. (seen in eg bzip2)

Encoding process

Walking up the tree for every byte of the file is needlessly inefficient. You could precompute an array of codes and lengths once in advance and then use the array during encoding. The code could be represented as a single unsigned integer, no array necessary (it won't be that long, and you will want to limit the code lengths anyway for decoding and header reasons). It can be prepended to buf in a couple of simple bitwise operations, similar to how you currently add a single bit, but nbuf++ turns into nbuf += codelength. Together this lets the encoding process take a constant number of operations instead of scaling linearly with the code length.

Decoding process

Currently your code implements bit-by-bit tree walking, which is (as one source puts it) dead slow. The alternative is decoding several bits at the same time by using an array lookup. There are a lot of subtly different ways to do that, but the basis of all of them is that part of the buffer is used to index into a table. Limiting the maximum length of the codes is very useful, because with a limited length you can guarantee that decoding is a single-step process, resolving one symbol from the buffer in a constant number of operations, with no looping.

Some possible relevant sources for these techniques are the one in the previous paragraph and:

Introduction to table based Huffman decoding

An efficient algorithm of Huffman decoder with nearly constant decoding time

Huffman revisited - Part 2 : the Decoder

A Fast and Space - Economical Algorithm for Length - Limited Coding (for a way to generate the code lengths with a length limit)

George BarwoodGeorge Barwood 596 · Accepted Answer · 2019-01-01 18:09:15Z

Harold has given a pretty comprehensive answer. I thought your code for building the Huffman tree was a little obscure, the usual approach is to use a "heap" which efficiently maintains the smallest element of a array in position zero.

I have been working on an implementation of RFC 1951 in C#, so far I have found that it's fairly unusual for the bit length limits to be exceeded in practice ( I am using it to write PDF files ), so my approach was simply to try a smaller block size if the limits were exceeded.

Here's my C# "deflate" code for comparison ( hope it's alright to post code as part of a reply, I am new here ):

using G = System.Collections.Generic; 

using U = System.UInt16; // Could also be UInt32 or UInt64, not sure what is best.



class Encoder : G.List<byte> // Compression per RFC1950, RFC1951.

{

  public G.List<byte> Deflate( byte  inp )

  {

    Clear();

    Add( 0x78); Add( 0x9C ); // RFC 1950 bytes

    ReadInp( inp );

    while ( DoOutput( 1 ) == 0 );

    FlushBitBuf();

    Put32( Adler32( inp ) ); // RFC 1950 checksum

    // System.Console.WriteLine( "Encoder.Deflate, input size=" + inp.Length + " output size=" + this.Count );

    return this;  

  }



  class OffsetList{ public uint Offset; public OffsetList Next; } // List of 3-byte match offsets.



  void ReadInp( byte  inp ) // LZ77 compression, per RFC1951

  { 

    G.Dictionary <uint,OffsetList> lookup = new G.Dictionary<uint,OffsetList>(); // Note: could reduce storage requirement by removing entries outside 32k window

    uint n = (uint)inp.Length;

    SetIBufSize( n );  



    uint w = 0; // holds last 3 bytes of input

    int todo = 0; // number of bytes in w that have not yet been output to IBuf, can be negative when a match is found

    uint pendingMatchLen=0, pendingDist=0;



    for ( uint i = 0; i <= 1 && i < n; i += 1 ) { w = ( ( w << 8 ) | inp[i] ); todo += 1; }



    for ( uint i = 2; i < n; i += 1 )

    {

      w = ( ( w << 8 ) | inp[i] ) & 0xffffffu; todo += 1;

      OffsetList e, x = new OffsetList(); x.Offset = i;

      uint bestMatchLen = 0, bestDist = 0;

      if ( lookup.TryGetValue( w, out e ) )

      {

        x.Next = e;

        OffsetList p = x;

        if ( todo >= 3 ) while ( e != null )

        {

          uint dist = i - e.Offset; if ( dist > 32768 ) { p.Next = null; break; }

          uint matchLen = MatchLen( inp, dist, i );

          if ( matchLen > bestMatchLen ) { bestMatchLen = matchLen; bestDist = dist; }  

          p = e; e = e.Next;         

        }

      }

      lookup[ w ] = x; ISpace();



      // "Lazy matching" RFC 1951 p.15 : if there are overlapping matches, there is a choice over which of the match to use.

      // Example:  abc012bc345.... abc345 : abc345 can be encoded as either [abc][345] or as a[bc345].

      // Since a range needs more bits to encode than a literal the latter is better.



      if ( pendingMatchLen > 0 )

      {

        if ( bestMatchLen > pendingMatchLen || bestMatchLen == pendingMatchLen && bestDist < pendingDist )

        { IPut( inp[i-3] ); todo -= 1; }

        else // Save the pending match, suppress bestMatch if any.

        {

          IPut( (ushort)(257 + pendingMatchLen) );

          IPut( (ushort) pendingDist );

          todo -= (int)pendingMatchLen;

          bestMatchLen = 0;

        }

        pendingMatchLen = 0;

      }

      if ( bestMatchLen > 0 ) { pendingMatchLen = bestMatchLen; pendingDist = bestDist; }

      else if ( todo == 3  ) { IPut( (byte)(w >> 16) ); todo = 2; }      

    } // end for loop

    if ( pendingMatchLen > 0 )

    {

      IPut( (ushort)(257 + pendingMatchLen) );

      IPut( (ushort) pendingDist );

      todo -= (int)pendingMatchLen;

    }

    while ( todo > 0 ){ todo -= 1; IPut( (byte)( w >> (todo*8) ) ); }

  } // end ReadInp



  uint MatchLen( byte  inp, uint dist, uint i )

  {

    // From lookup, we already have a match of 3 bytes, this function computes how many more bytes match.

    uint x = i+1;

    ulong end = (ulong)inp.Length;

    if ( end - i > 256 ) end = i + 256; // Maximum match is 258

    while ( x < end && inp[x] == inp[x-dist] ) x += 1;

    return x - i + 2; 

  }



  ushort  IBuf; // Intermediate buffer, holds output from LZ99 algorithm.

  const uint IBufSizeMax = 0x40000;

  uint IBufSize, IBufI, IBufJ;

  void IPut( ushort x ) { IBuf[IBufI++] = x; if ( IBufI == IBufSize ) IBufI = 0; }

  ushort IGet(){ ushort result = IBuf[IBufJ++]; if ( IBufJ == IBufSize ) IBufJ = 0; return result; }

  uint ICount(){ if ( IBufI >= IBufJ ) return IBufI - IBufJ; else return IBufI + IBufSize - IBufJ; } // Number of values in IBuf

  void ISpace(){ while ( ICount() > IBufSize - 10 ) DoOutput( 0 ); } // Ensure IBuf has space for at least 10 values.

  void SetIBufSize( uint x ) { x += 20; if ( x > IBufSizeMax ) x = IBufSizeMax; if ( IBufSize < x ) { IBufSize = x; IBuf = new ushort[x]; } }



  U DoOutput( U last ) // while DoBlock fails, retry with a smaller amount of input

  {

    uint n = ICount();

    while ( !DoBlock( n, last ) ) { last = 0; n -= n / 20; }

    return last;

  }



  ///////////////////////////////////////////////////////////////////////////////

  // RFC 1951 encoding constants.



  static readonly byte  ClenAlphabet = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; // size = 19

  static readonly byte  MatchExtra = { 0,0,0,0, 0,0,0,0, 1,1,1,1, 2,2,2,2, 3,3,3,3, 4,4,4,4, 5,5,5,5, 0 }; // size = 29

  static readonly ushort  MatchOff = { 3,4,5,6, 7,8,9,10, 11,13,15,17, 19,23,27,31, 35,43,51,59, 67,83,99,115, 131,163,195,227, 258, 0xffff };

  static readonly byte  DistExtra = { 0,0,0,0, 1,1,2,2, 3,3,4,4, 5,5,6,6, 7,7,8,8, 9,9,10,10, 11,11,12,12, 13,13 }; // size = 30

  static readonly ushort  DistOff = { 1,2,3,4, 5,7,9,13, 17,25,33,49, 65,97,129,193, 257,385,513,769, 1025,1537,2049,3073,

     4097,6145,8193,12289, 16385,24577, 0xffff };



  readonly U  LitFreq = new U[288], LitLen = new U[288], LitCode = new U[288];

  readonly U  DistFreq = new U[32], DistLen = new U[32], DistCode = new U[32];

  readonly U  LenFreq = new U[19], LenLen = new U[19], LenCode = new U[19];



  bool DoBlock( uint n, U last )

  {

    Clear( LitFreq ); Clear( DistFreq ); Clear( LenFreq );

    uint saveI = IBufI, saveJ = IBufJ;

    int got = 0; while ( got < n )

    {

      ushort x = IGet(); got += 1;

      if ( x < 256 ) LitFreq[ x ] += 1;

      else

      { 

        x -= 257;

        uint dist = IGet(); got += 1;

        uint mc=0; while ( x >= MatchOff[mc] ) mc += 1; mc -= 1;

        uint dc=0; while ( dist >= DistOff[dc] ) dc += 1; dc -= 1;

        LitFreq[ 257+mc ] += 1;

        DistFreq[ dc ] += 1;

      }

    }

    LitFreq[256] += 1; // end of block code

    IBufI = saveI; IBufJ = saveJ;



    int nLitCode = HE.ComputeCode( 15, LitFreq, LitLen, LitCode ); if ( nLitCode < 0 ) return false;

    int nDistCode = HE.ComputeCode( 15, DistFreq, DistLen, DistCode ); if ( nDistCode < 0 ) return false;



    if ( nDistCode == 0 ) nDistCode = 1;

    LenPass = 1; DoLengths( nLitCode, LitLen, true ); DoLengths( nDistCode, DistLen, false );



    if ( HE.ComputeCode( 7, LenFreq, LenLen, LenCode ) < 0 ) return false;



    int nLenCode = 19;

    while ( nLenCode > 0 && LenLen[ ClenAlphabet[nLenCode-1] ] == 0 ) nLenCode -= 1;



    PutBit( last ); // Last block flag

    PutBits( 2, 2 ); // Dynamic Huffman ( for small blocks fixed coding may work better, not implemented )



    PutBits( 5, (U)( nLitCode - 257 ) ); PutBits( 5, (U)( nDistCode - 1 ) ); PutBits( 4, (U)( nLenCode - 4 ) );

    for ( int i=0; i < nLenCode; i += 1 ) PutBits( 3, LenLen[ ClenAlphabet[i] ] );

    LenPass = 2; DoLengths( nLitCode, LitLen, true ); DoLengths( nDistCode, DistLen, false ); 



    got = 0; while ( got < n )

    {

      U x = IGet(); got += 1;

      if ( x < 256 ) PutBits( LitLen[x], LitCode[x] );

      else

      { 

        x -= 257;

        ushort dist = IGet(); got += 1;

        uint mc=0; while ( x >= MatchOff[mc] ) mc += 1; mc -= 1;

        uint dc=0; while ( dist >= DistOff[dc] ) dc += 1; dc -= 1;

        PutBits( LitLen[257+mc], LitCode[257+mc] );

        PutBits( MatchExtra[mc], (U)(x-MatchOff[mc]) );

        PutBits( DistLen[dc], DistCode[dc] );

        PutBits( DistExtra[dc], (U)(dist-DistOff[dc]) );

      }

    }

    PutBits( LitLen[256], LitCode[256] ); // block end code

    return true;

  } // end DoBlock



  // Encoding of code lengths ( RFC 1951, page 13 ).



  U LenPass, Plen, ZeroRun, Repeat;



  void PutLenCode( U code ) { if ( LenPass == 1 ) LenFreq[code] += 1; else PutBits( LenLen[code], LenCode[code] ); }



  void DoLengths( int n, U  a, bool isLit )

  {

    if ( isLit ) { Plen = 0; ZeroRun = 0; Repeat = 0; }

    for ( int i=0; i<n; i += 1 )

    {

      U len = a[i];

      if ( len == 0 ){ EncRepeat(); ZeroRun += 1; Plen = 0; }

      else if ( len == Plen ) { Repeat += 1; }

      else { EncZeroRun(); EncRepeat(); PutLenCode( len ); Plen = len; }

    }      

    if ( !isLit ) { EncZeroRun(); EncRepeat(); }

  }



  void EncRepeat()

  {

    while ( Repeat > 0 )

    {

      if ( Repeat < 3 ) { PutLenCode( Plen ); Repeat -= 1; }

      else { U x = Repeat; if ( x > 6 ) x = 6; PutLenCode( 16 ); if ( LenPass == 2 ) PutBits( 2,(U)(x-3) ); Repeat -= x;  }

    }

  }



  void EncZeroRun()

  {

    while ( ZeroRun > 0 )

    {

      if ( ZeroRun < 3 ) { PutLenCode( 0 ); ZeroRun -= 1; }

      else if ( ZeroRun < 11 ) { PutLenCode( 17 ); if ( LenPass == 2 ) PutBits( 3, (U)(ZeroRun-3) ); ZeroRun = 0;  }

      else { U x = ZeroRun; if ( x > 138 ) x = 138; PutLenCode( 18 ); if ( LenPass == 2 ) PutBits( 7,(U)(x-11) ); ZeroRun -= x; }

    }

  }



  static void Clear( U  a ){ System.Array.Clear( a, 0, a.Length ); /*for ( int i=0; i < a.Length; i += 1 ) a[i] = 0;*/ }



  public static uint Adler32( byte  b ) // per RFC1950

  {

    uint s1=1, s2=0;

    for ( int i=0; i<b.Length; i+= 1 )

    {

      s1 = ( s1 + b[i] ) % 65521;

      s2 = ( s2 + s1 ) % 65521;

    }

    return s2*65536 + s1;    

  }



  // Output bitstream

  byte Buf = 0, M = 1;

  public void PutBit( U b ) { if ( b != 0 ) Buf |= M; M <<= 1; if ( M == 0 ) { Add(Buf); Buf = 0; M = 1; } }

  public void PutBits( U n, U x ) { for ( int i = 0; i < n; i += 1 ) { PutBit( (U)(x & 1u) ); x >>= 1; } }

  public void FlushBitBuf(){ while ( M != 1 ) PutBit( 0 ); }

  public void Put32( uint x ) { Add( (byte)( x >> 24 ) ); Add( (byte)( x >> 16 ) ); Add( (byte)( x >> 8 ) ); Add( (byte) x ); } 

}  // end class Encoder



////////////////////////////////////////////////////////////////////////////////////////////////////



class HE // Given a list of frequencies (freq), compute Huffman code lengths (nbits) and codes (tree_code).

{

  public static int ComputeCode( int limit, U  freq, U  nbits, U  tree_code )

  {

    int ncode = freq.Length;

    Node  heap = new Node[ncode];

    int hn = 0;

    for ( int i = 0; i < ncode; i += 1 )

    {

      U f = freq[i];

      if ( f > 0 )

      {

        Node n = new Node();

        n.Freq = f;

        n.Code = (U)i;

        HeapInsert( heap, hn, n );

        hn += 1;

      }

    }



    for ( int i = 0; i < nbits.Length; i += 1 ) nbits[i] = 0;

    if ( hn <= 1 ) // Special case

    { if ( hn == 1 ) nbits[ heap[0].Code ] = 1; }

    else

    {

      while ( hn > 1 )

      {

        Node n = new Node();

        hn -= 1; n.Left = HeapRemove( heap, hn );

        hn -= 1; n.Right = HeapRemove( heap, hn );

        n.Freq = (U) ( n.Left.Freq + n.Right.Freq );  

        n.Depth = (U) ( 1 + ( n.Left.Depth > n.Right.Depth ? n.Left.Depth : n.Right.Depth ) );    

        HeapInsert( heap, hn, n );

        hn += 1;

      }

      Walk( nbits, heap[0], 0 ); // Walk the tree to find the code lengths (nbits).

    }



    for ( int i = 0; i < ncode; i += 1 ) if ( nbits[i] > limit ) return -1;



    // Now compute codes, code below is from rfc1951 page 7



    uint maxBits = 0;

    for ( int i = 0; i < ncode; i += 1 ) if ( nbits[i] > maxBits ) maxBits = nbits[i];



    U  bl_count = new U[maxBits+1];

    for ( int i=0; i < ncode; i += 1 ) bl_count[ nbits[i] ] += 1;



    U  next_code = new U[maxBits+1];

    U code = 0; bl_count[0] = 0;

    for ( int i = 0; i < maxBits; i += 1 ) 

    {

      code = (U)( ( code + bl_count[i] ) << 1 );

      next_code[i+1] = code;

    }



    for ( int i = 0; i < ncode; i += 1 ) 

    {

      uint len = nbits[i];

      if (len != 0) 

      {

        tree_code[i] = Reverse( next_code[len], len );

        next_code[len] += 1;

      }

    }



    //System.Console.WriteLine( "Huff Code" );

    //   for ( uint i=0; i < ncode; i += 1 ) if ( nbits[i] > 0 )

    //     System.Console.WriteLine( "i=" + i + " len=" + nbits[i] + " tc=" + tree_code[i].ToString("X") + " freq=" + freq[i] );



    while ( ncode > 0 && nbits[ ncode-1 ] == 0 ) ncode -= 1;

    return ncode;

  }



  class Node{ public U Freq; public U Code, Depth; public Node Left, Right; }



  static U Reverse( U x, uint bits )

  { U result = 0; for ( int i = 0; i < bits; i += 1 ) { result <<= 1; result |= (U)(x & 1u); x >>= 1; } return result; } 



  static void Walk( U  a, Node n,U len )

  { if ( n.Left == null ) a[n.Code] = len; else { Walk( a, n.Left, (U)(len+1) ); Walk( a, n.Right, (U)(len+1) ); } }



  static bool LessThan( Node a, Node b )

  { return a.Freq < b.Freq || a.Freq == b.Freq && a.Depth < b.Depth; }



  static void HeapInsert( Node  heap, int h, Node n ) // h is size of heap before insertion

  {

    int j = h;

    while ( j > 0 )

    {

      int p = ( j - 1 ) / 2; // parent

      Node pn = heap[p];

      if ( !LessThan(n,pn) ) break;

      heap[j] = pn; // move parent down

      j = p;

    }    

    heap[j] = n;

  }



  static Node HeapRemove( Node  heap, int h ) // h is size of heap after removal

  {

    Node result = heap[0];

    Node n = heap[h];

    int j = 0;

    while ( true )

    {

      int c = j * 2 + 1; if ( c >= h ) break;

      Node cn = heap[c];

      if ( c+1 < h )

      {

        Node cn2 = heap[c+1];

        if ( LessThan(cn2,cn) ) { c += 1; cn = cn2; }

      } 

      if ( !LessThan(cn,n) ) break;

      heap[j] = cn; j = c;  

    }

    heap[j] = n;

    return result;

  }

} // end class HE

(Welcome to Code Review!) (hope it's alright to […], I am new here there you go — Jan 1 at 18:40

ReinderienReinderien 4,171822 · Accepted Answer · 2019-01-01 00:34:47Z

Use standard types

You define this:

typedef unsigned char byte;

But you also already #include <stdint.h>. As such, you have access to uint8_t, which is more explicit about its size than char.

Identify local functions

If all of your functions are in the same translation unit (which seems to be the case), make them static.

Forever loops

This is quite minor, but while (1) isn't my favourite way of defining a forever loop. You can either do for (;;) or while (true), after having included stdbool.h. 1 is less expressive than true.

Unite declaration and initialization

int ch;

while (1) {

    ch = fgetc(fp);

can be

while (true) {

    int ch = fgetc(fp);

Define magic numbers

Make a #define or a global const int for 256. It's used all over your code, and it'd be good to replace that with a symbol for legibility and maintainability.

Do one thing at a time

lower[0] = 0, upper[0] = 256;

// ...

unsigned t = freq[i]; freq[i] = freq[j]; freq[j] = t;

It's rarely an improvement to the legibility of code to do multi-statement lines. Just put these on separate lines.

Sanitize loop counters

You have:

unsigned top = 1;

// ...

while (top > 0) {

    top--;

    // ...`continue`s under certain conditions...

    top += 2;

}

This is a little wacky. Just do:

for (int top = 0; top >= 0; top--) {

    // ... continue under certain conditions...

    top += 2;

}

I think those are equivalent.

Sanitize logic

        int flag = 0;

        while (...) {

            if (freq[i] < freq[j]) {

                //...

                flag = !flag;

            }

            flag ? i++ : j--;

        }

This is ternary abuse. The flag should be a bool (from stdbool.h). Rewrite this as:

bool flag = false;

while (...) {

    if (freq[i] < freq[j]) {

        //...

        flag = !flag;

    }

    if (flag) i++;

    else j--;

}

Choose a pointer spacing standard

You do:

void compress_file(const char* filename, const char* newname) {

but you also do:

FILE *fin = fopen(filename, "rb"),

     *fout = fopen(newname, "wb");

Personally I like the latter; either way, you should pick a standard and apply it everywhere.

Let `fwrite` do the iteration

This:

for (int i = 0; i < 256; i++)

    fwrite(freq + i, 4, 1, fout);

is equivalent to:

fwrite(freq, 4, 256, fout);

haroldharold 1,09857 · Accepted Answer · 2018-12-31 19:05:08Z

Header size

256*4 bytes is very big for a header. The size could be reduced substantially by using one or several of these common techniques:

Store the code length instead of symbol frequency. These definitely won't need 32 bits each, 8 would already be a lot. You can pack them in 4 bits each if you set a length limit of 15. Storing lengths is not ambiguous because you can use canonical Huffman codes (there is an easy algorithm to generate them from your table of code lengths, discarding the code itself).

Compress the header with delta encoding: storing the length difference between subsequent codes, using a variable-length encoding. Small differences tend to be more common. (seen in eg DEFLATE)

Remove most zero-lengths from the header, by first storing a sparse bitmap that indicates which symbols occur in the file. (seen in eg bzip2)

Encoding process

Walking up the tree for every byte of the file is needlessly inefficient. You could precompute an array of codes and lengths once in advance and then use the array during encoding. The code could be represented as a single unsigned integer, no array necessary (it won't be that long, and you will want to limit the code lengths anyway for decoding and header reasons). It can be prepended to buf in a couple of simple bitwise operations, similar to how you currently add a single bit, but nbuf++ turns into nbuf += codelength. Together this lets the encoding process take a constant number of operations instead of scaling linearly with the code length.

Decoding process

Currently your code implements bit-by-bit tree walking, which is (as one source puts it) dead slow. The alternative is decoding several bits at the same time by using an array lookup. There are a lot of subtly different ways to do that, but the basis of all of them is that part of the buffer is used to index into a table. Limiting the maximum length of the codes is very useful, because with a limited length you can guarantee that decoding is a single-step process, resolving one symbol from the buffer in a constant number of operations, with no looping.

Some possible relevant sources for these techniques are the one in the previous paragraph and:

Introduction to table based Huffman decoding

An efficient algorithm of Huffman decoder with nearly constant decoding time

Huffman revisited - Part 2 : the Decoder

A Fast and Space - Economical Algorithm for Length - Limited Coding (for a way to generate the code lengths with a length limit)

George BarwoodGeorge Barwood 596 · Accepted Answer · 2019-01-01 18:09:15Z

Harold has given a pretty comprehensive answer. I thought your code for building the Huffman tree was a little obscure, the usual approach is to use a "heap" which efficiently maintains the smallest element of a array in position zero.

I have been working on an implementation of RFC 1951 in C#, so far I have found that it's fairly unusual for the bit length limits to be exceeded in practice ( I am using it to write PDF files ), so my approach was simply to try a smaller block size if the limits were exceeded.

Here's my C# "deflate" code for comparison ( hope it's alright to post code as part of a reply, I am new here ):

using G = System.Collections.Generic; 

using U = System.UInt16; // Could also be UInt32 or UInt64, not sure what is best.



class Encoder : G.List<byte> // Compression per RFC1950, RFC1951.

{

  public G.List<byte> Deflate( byte  inp )

  {

    Clear();

    Add( 0x78); Add( 0x9C ); // RFC 1950 bytes

    ReadInp( inp );

    while ( DoOutput( 1 ) == 0 );

    FlushBitBuf();

    Put32( Adler32( inp ) ); // RFC 1950 checksum

    // System.Console.WriteLine( "Encoder.Deflate, input size=" + inp.Length + " output size=" + this.Count );

    return this;  

  }



  class OffsetList{ public uint Offset; public OffsetList Next; } // List of 3-byte match offsets.



  void ReadInp( byte  inp ) // LZ77 compression, per RFC1951

  { 

    G.Dictionary <uint,OffsetList> lookup = new G.Dictionary<uint,OffsetList>(); // Note: could reduce storage requirement by removing entries outside 32k window

    uint n = (uint)inp.Length;

    SetIBufSize( n );  



    uint w = 0; // holds last 3 bytes of input

    int todo = 0; // number of bytes in w that have not yet been output to IBuf, can be negative when a match is found

    uint pendingMatchLen=0, pendingDist=0;



    for ( uint i = 0; i <= 1 && i < n; i += 1 ) { w = ( ( w << 8 ) | inp[i] ); todo += 1; }



    for ( uint i = 2; i < n; i += 1 )

    {

      w = ( ( w << 8 ) | inp[i] ) & 0xffffffu; todo += 1;

      OffsetList e, x = new OffsetList(); x.Offset = i;

      uint bestMatchLen = 0, bestDist = 0;

      if ( lookup.TryGetValue( w, out e ) )

      {

        x.Next = e;

        OffsetList p = x;

        if ( todo >= 3 ) while ( e != null )

        {

          uint dist = i - e.Offset; if ( dist > 32768 ) { p.Next = null; break; }

          uint matchLen = MatchLen( inp, dist, i );

          if ( matchLen > bestMatchLen ) { bestMatchLen = matchLen; bestDist = dist; }  

          p = e; e = e.Next;         

        }

      }

      lookup[ w ] = x; ISpace();



      // "Lazy matching" RFC 1951 p.15 : if there are overlapping matches, there is a choice over which of the match to use.

      // Example:  abc012bc345.... abc345 : abc345 can be encoded as either [abc][345] or as a[bc345].

      // Since a range needs more bits to encode than a literal the latter is better.



      if ( pendingMatchLen > 0 )

      {

        if ( bestMatchLen > pendingMatchLen || bestMatchLen == pendingMatchLen && bestDist < pendingDist )

        { IPut( inp[i-3] ); todo -= 1; }

        else // Save the pending match, suppress bestMatch if any.

        {

          IPut( (ushort)(257 + pendingMatchLen) );

          IPut( (ushort) pendingDist );

          todo -= (int)pendingMatchLen;

          bestMatchLen = 0;

        }

        pendingMatchLen = 0;

      }

      if ( bestMatchLen > 0 ) { pendingMatchLen = bestMatchLen; pendingDist = bestDist; }

      else if ( todo == 3  ) { IPut( (byte)(w >> 16) ); todo = 2; }      

    } // end for loop

    if ( pendingMatchLen > 0 )

    {

      IPut( (ushort)(257 + pendingMatchLen) );

      IPut( (ushort) pendingDist );

      todo -= (int)pendingMatchLen;

    }

    while ( todo > 0 ){ todo -= 1; IPut( (byte)( w >> (todo*8) ) ); }

  } // end ReadInp



  uint MatchLen( byte  inp, uint dist, uint i )

  {

    // From lookup, we already have a match of 3 bytes, this function computes how many more bytes match.

    uint x = i+1;

    ulong end = (ulong)inp.Length;

    if ( end - i > 256 ) end = i + 256; // Maximum match is 258

    while ( x < end && inp[x] == inp[x-dist] ) x += 1;

    return x - i + 2; 

  }



  ushort  IBuf; // Intermediate buffer, holds output from LZ99 algorithm.

  const uint IBufSizeMax = 0x40000;

  uint IBufSize, IBufI, IBufJ;

  void IPut( ushort x ) { IBuf[IBufI++] = x; if ( IBufI == IBufSize ) IBufI = 0; }

  ushort IGet(){ ushort result = IBuf[IBufJ++]; if ( IBufJ == IBufSize ) IBufJ = 0; return result; }

  uint ICount(){ if ( IBufI >= IBufJ ) return IBufI - IBufJ; else return IBufI + IBufSize - IBufJ; } // Number of values in IBuf

  void ISpace(){ while ( ICount() > IBufSize - 10 ) DoOutput( 0 ); } // Ensure IBuf has space for at least 10 values.

  void SetIBufSize( uint x ) { x += 20; if ( x > IBufSizeMax ) x = IBufSizeMax; if ( IBufSize < x ) { IBufSize = x; IBuf = new ushort[x]; } }



  U DoOutput( U last ) // while DoBlock fails, retry with a smaller amount of input

  {

    uint n = ICount();

    while ( !DoBlock( n, last ) ) { last = 0; n -= n / 20; }

    return last;

  }



  ///////////////////////////////////////////////////////////////////////////////

  // RFC 1951 encoding constants.



  static readonly byte  ClenAlphabet = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; // size = 19

  static readonly byte  MatchExtra = { 0,0,0,0, 0,0,0,0, 1,1,1,1, 2,2,2,2, 3,3,3,3, 4,4,4,4, 5,5,5,5, 0 }; // size = 29

  static readonly ushort  MatchOff = { 3,4,5,6, 7,8,9,10, 11,13,15,17, 19,23,27,31, 35,43,51,59, 67,83,99,115, 131,163,195,227, 258, 0xffff };

  static readonly byte  DistExtra = { 0,0,0,0, 1,1,2,2, 3,3,4,4, 5,5,6,6, 7,7,8,8, 9,9,10,10, 11,11,12,12, 13,13 }; // size = 30

  static readonly ushort  DistOff = { 1,2,3,4, 5,7,9,13, 17,25,33,49, 65,97,129,193, 257,385,513,769, 1025,1537,2049,3073,

     4097,6145,8193,12289, 16385,24577, 0xffff };



  readonly U  LitFreq = new U[288], LitLen = new U[288], LitCode = new U[288];

  readonly U  DistFreq = new U[32], DistLen = new U[32], DistCode = new U[32];

  readonly U  LenFreq = new U[19], LenLen = new U[19], LenCode = new U[19];



  bool DoBlock( uint n, U last )

  {

    Clear( LitFreq ); Clear( DistFreq ); Clear( LenFreq );

    uint saveI = IBufI, saveJ = IBufJ;

    int got = 0; while ( got < n )

    {

      ushort x = IGet(); got += 1;

      if ( x < 256 ) LitFreq[ x ] += 1;

      else

      { 

        x -= 257;

        uint dist = IGet(); got += 1;

        uint mc=0; while ( x >= MatchOff[mc] ) mc += 1; mc -= 1;

        uint dc=0; while ( dist >= DistOff[dc] ) dc += 1; dc -= 1;

        LitFreq[ 257+mc ] += 1;

        DistFreq[ dc ] += 1;

      }

    }

    LitFreq[256] += 1; // end of block code

    IBufI = saveI; IBufJ = saveJ;



    int nLitCode = HE.ComputeCode( 15, LitFreq, LitLen, LitCode ); if ( nLitCode < 0 ) return false;

    int nDistCode = HE.ComputeCode( 15, DistFreq, DistLen, DistCode ); if ( nDistCode < 0 ) return false;



    if ( nDistCode == 0 ) nDistCode = 1;

    LenPass = 1; DoLengths( nLitCode, LitLen, true ); DoLengths( nDistCode, DistLen, false );



    if ( HE.ComputeCode( 7, LenFreq, LenLen, LenCode ) < 0 ) return false;



    int nLenCode = 19;

    while ( nLenCode > 0 && LenLen[ ClenAlphabet[nLenCode-1] ] == 0 ) nLenCode -= 1;



    PutBit( last ); // Last block flag

    PutBits( 2, 2 ); // Dynamic Huffman ( for small blocks fixed coding may work better, not implemented )



    PutBits( 5, (U)( nLitCode - 257 ) ); PutBits( 5, (U)( nDistCode - 1 ) ); PutBits( 4, (U)( nLenCode - 4 ) );

    for ( int i=0; i < nLenCode; i += 1 ) PutBits( 3, LenLen[ ClenAlphabet[i] ] );

    LenPass = 2; DoLengths( nLitCode, LitLen, true ); DoLengths( nDistCode, DistLen, false ); 



    got = 0; while ( got < n )

    {

      U x = IGet(); got += 1;

      if ( x < 256 ) PutBits( LitLen[x], LitCode[x] );

      else

      { 

        x -= 257;

        ushort dist = IGet(); got += 1;

        uint mc=0; while ( x >= MatchOff[mc] ) mc += 1; mc -= 1;

        uint dc=0; while ( dist >= DistOff[dc] ) dc += 1; dc -= 1;

        PutBits( LitLen[257+mc], LitCode[257+mc] );

        PutBits( MatchExtra[mc], (U)(x-MatchOff[mc]) );

        PutBits( DistLen[dc], DistCode[dc] );

        PutBits( DistExtra[dc], (U)(dist-DistOff[dc]) );

      }

    }

    PutBits( LitLen[256], LitCode[256] ); // block end code

    return true;

  } // end DoBlock



  // Encoding of code lengths ( RFC 1951, page 13 ).



  U LenPass, Plen, ZeroRun, Repeat;



  void PutLenCode( U code ) { if ( LenPass == 1 ) LenFreq[code] += 1; else PutBits( LenLen[code], LenCode[code] ); }



  void DoLengths( int n, U  a, bool isLit )

  {

    if ( isLit ) { Plen = 0; ZeroRun = 0; Repeat = 0; }

    for ( int i=0; i<n; i += 1 )

    {

      U len = a[i];

      if ( len == 0 ){ EncRepeat(); ZeroRun += 1; Plen = 0; }

      else if ( len == Plen ) { Repeat += 1; }

      else { EncZeroRun(); EncRepeat(); PutLenCode( len ); Plen = len; }

    }      

    if ( !isLit ) { EncZeroRun(); EncRepeat(); }

  }



  void EncRepeat()

  {

    while ( Repeat > 0 )

    {

      if ( Repeat < 3 ) { PutLenCode( Plen ); Repeat -= 1; }

      else { U x = Repeat; if ( x > 6 ) x = 6; PutLenCode( 16 ); if ( LenPass == 2 ) PutBits( 2,(U)(x-3) ); Repeat -= x;  }

    }

  }



  void EncZeroRun()

  {

    while ( ZeroRun > 0 )

    {

      if ( ZeroRun < 3 ) { PutLenCode( 0 ); ZeroRun -= 1; }

      else if ( ZeroRun < 11 ) { PutLenCode( 17 ); if ( LenPass == 2 ) PutBits( 3, (U)(ZeroRun-3) ); ZeroRun = 0;  }

      else { U x = ZeroRun; if ( x > 138 ) x = 138; PutLenCode( 18 ); if ( LenPass == 2 ) PutBits( 7,(U)(x-11) ); ZeroRun -= x; }

    }

  }



  static void Clear( U  a ){ System.Array.Clear( a, 0, a.Length ); /*for ( int i=0; i < a.Length; i += 1 ) a[i] = 0;*/ }



  public static uint Adler32( byte  b ) // per RFC1950

  {

    uint s1=1, s2=0;

    for ( int i=0; i<b.Length; i+= 1 )

    {

      s1 = ( s1 + b[i] ) % 65521;

      s2 = ( s2 + s1 ) % 65521;

    }

    return s2*65536 + s1;    

  }



  // Output bitstream

  byte Buf = 0, M = 1;

  public void PutBit( U b ) { if ( b != 0 ) Buf |= M; M <<= 1; if ( M == 0 ) { Add(Buf); Buf = 0; M = 1; } }

  public void PutBits( U n, U x ) { for ( int i = 0; i < n; i += 1 ) { PutBit( (U)(x & 1u) ); x >>= 1; } }

  public void FlushBitBuf(){ while ( M != 1 ) PutBit( 0 ); }

  public void Put32( uint x ) { Add( (byte)( x >> 24 ) ); Add( (byte)( x >> 16 ) ); Add( (byte)( x >> 8 ) ); Add( (byte) x ); } 

}  // end class Encoder



////////////////////////////////////////////////////////////////////////////////////////////////////



class HE // Given a list of frequencies (freq), compute Huffman code lengths (nbits) and codes (tree_code).

{

  public static int ComputeCode( int limit, U  freq, U  nbits, U  tree_code )

  {

    int ncode = freq.Length;

    Node  heap = new Node[ncode];

    int hn = 0;

    for ( int i = 0; i < ncode; i += 1 )

    {

      U f = freq[i];

      if ( f > 0 )

      {

        Node n = new Node();

        n.Freq = f;

        n.Code = (U)i;

        HeapInsert( heap, hn, n );

        hn += 1;

      }

    }



    for ( int i = 0; i < nbits.Length; i += 1 ) nbits[i] = 0;

    if ( hn <= 1 ) // Special case

    { if ( hn == 1 ) nbits[ heap[0].Code ] = 1; }

    else

    {

      while ( hn > 1 )

      {

        Node n = new Node();

        hn -= 1; n.Left = HeapRemove( heap, hn );

        hn -= 1; n.Right = HeapRemove( heap, hn );

        n.Freq = (U) ( n.Left.Freq + n.Right.Freq );  

        n.Depth = (U) ( 1 + ( n.Left.Depth > n.Right.Depth ? n.Left.Depth : n.Right.Depth ) );    

        HeapInsert( heap, hn, n );

        hn += 1;

      }

      Walk( nbits, heap[0], 0 ); // Walk the tree to find the code lengths (nbits).

    }



    for ( int i = 0; i < ncode; i += 1 ) if ( nbits[i] > limit ) return -1;



    // Now compute codes, code below is from rfc1951 page 7



    uint maxBits = 0;

    for ( int i = 0; i < ncode; i += 1 ) if ( nbits[i] > maxBits ) maxBits = nbits[i];



    U  bl_count = new U[maxBits+1];

    for ( int i=0; i < ncode; i += 1 ) bl_count[ nbits[i] ] += 1;



    U  next_code = new U[maxBits+1];

    U code = 0; bl_count[0] = 0;

    for ( int i = 0; i < maxBits; i += 1 ) 

    {

      code = (U)( ( code + bl_count[i] ) << 1 );

      next_code[i+1] = code;

    }



    for ( int i = 0; i < ncode; i += 1 ) 

    {

      uint len = nbits[i];

      if (len != 0) 

      {

        tree_code[i] = Reverse( next_code[len], len );

        next_code[len] += 1;

      }

    }



    //System.Console.WriteLine( "Huff Code" );

    //   for ( uint i=0; i < ncode; i += 1 ) if ( nbits[i] > 0 )

    //     System.Console.WriteLine( "i=" + i + " len=" + nbits[i] + " tc=" + tree_code[i].ToString("X") + " freq=" + freq[i] );



    while ( ncode > 0 && nbits[ ncode-1 ] == 0 ) ncode -= 1;

    return ncode;

  }



  class Node{ public U Freq; public U Code, Depth; public Node Left, Right; }



  static U Reverse( U x, uint bits )

  { U result = 0; for ( int i = 0; i < bits; i += 1 ) { result <<= 1; result |= (U)(x & 1u); x >>= 1; } return result; } 



  static void Walk( U  a, Node n,U len )

  { if ( n.Left == null ) a[n.Code] = len; else { Walk( a, n.Left, (U)(len+1) ); Walk( a, n.Right, (U)(len+1) ); } }



  static bool LessThan( Node a, Node b )

  { return a.Freq < b.Freq || a.Freq == b.Freq && a.Depth < b.Depth; }



  static void HeapInsert( Node  heap, int h, Node n ) // h is size of heap before insertion

  {

    int j = h;

    while ( j > 0 )

    {

      int p = ( j - 1 ) / 2; // parent

      Node pn = heap[p];

      if ( !LessThan(n,pn) ) break;

      heap[j] = pn; // move parent down

      j = p;

    }    

    heap[j] = n;

  }



  static Node HeapRemove( Node  heap, int h ) // h is size of heap after removal

  {

    Node result = heap[0];

    Node n = heap[h];

    int j = 0;

    while ( true )

    {

      int c = j * 2 + 1; if ( c >= h ) break;

      Node cn = heap[c];

      if ( c+1 < h )

      {

        Node cn2 = heap[c+1];

        if ( LessThan(cn2,cn) ) { c += 1; cn = cn2; }

      } 

      if ( !LessThan(cn,n) ) break;

      heap[j] = cn; j = c;  

    }

    heap[j] = n;

    return result;

  }

} // end class HE

(Welcome to Code Review!) (hope it's alright to […], I am new here there you go — Jan 1 at 18:40

Category

Random preview

Huffman tree compressing/decompressing in C

3 Answers 3

Use standard types

Identify local functions

Forever loops

Unite declaration and initialization

Define magic numbers

Do one thing at a time

Sanitize loop counters

Sanitize logic

Choose a pointer spacing standard

Let fwrite do the iteration

Header size

Encoding process

Decoding process

Your Answer

Sign up or log in

Post as a guest

Post as a guest

3 Answers 3

3 Answers 3

Use standard types

Identify local functions

Forever loops

Unite declaration and initialization

Define magic numbers

Do one thing at a time

Sanitize loop counters

Sanitize logic

Choose a pointer spacing standard

Let fwrite do the iteration

Use standard types

Identify local functions

Forever loops

Unite declaration and initialization

Define magic numbers

Do one thing at a time

Sanitize loop counters

Sanitize logic

Choose a pointer spacing standard

Let fwrite do the iteration

Use standard types

Identify local functions

Forever loops

Unite declaration and initialization

Define magic numbers

Do one thing at a time

Sanitize loop counters

Sanitize logic

Choose a pointer spacing standard

Let fwrite do the iteration

Use standard types

Identify local functions

Forever loops

Unite declaration and initialization

Define magic numbers

Do one thing at a time

Sanitize loop counters

Sanitize logic

Choose a pointer spacing standard

Let fwrite do the iteration

Header size

Encoding process

Decoding process

Header size

Encoding process

Decoding process

Header size

Encoding process

Decoding process

Header size

Encoding process

Decoding process

Sign up or log in

Post as a guest

Post as a guest

Sign up or log in

Post as a guest

3 Answers
3

Let `fwrite` do the iteration

3 Answers
3

3 Answers
3

Let `fwrite` do the iteration

Let `fwrite` do the iteration

Let `fwrite` do the iteration

Let `fwrite` do the iteration