cm.cpp

cm 压缩算法的源代码

{  unsigned char carry = enlow >> CODE_BITS;
   unsigned char tmp = enbuffer + carry;
   WriteOutputFile( tmp );
   carry += 0xff;                         /* carry = carry? 0x00 : 0xff    */
   while (bytes_to_follow) {
      WriteOutputFile( carry );
      bytes_to_follow --;
   }
}


/* START ENCODING A STREAM OF SYMBOLS. c preceeds the coded message and is */
/* returned by start_decoding                                              */
void start_encoding( char c )
{  enlow = 0;                                 /* Full code range.          */
   enrange = Top_value;
   enbuffer = c;                              /* byte to output first      */
   bytes_to_follow = 0;                       /* No bytes to follow        */
}


/* START DECODING A STREAM OF SYMBOLS. returns the char passed to          */
/* start_encoding() or EOF                                                 */
int start_decoding( void )
{  int c = ReadInputFile();
   debuffer = ReadInputFile();
   deoffs = debuffer >> (8-EXTRA_BITS);
   derange = 1 << EXTRA_BITS;
   return c;
}


/* Encode a symbol */
inline void encode_freq(
    unsigned int sy_f,    /* frequency of symbol */
    unsigned int lt_f,    /* frequency of symbols < the decoded symbol */
    unsigned int tot_f)   /* frequency of all symbols */
{  code_value r, tmp;
   r = enrange / tot_f;   /* consider replacing this / by >> if tot_f is */
                          /* a power of two                              */
   tmp = r * lt_f;
   enlow += tmp;
   if (lt_f+sy_f < tot_f) /* consider doing the old CACM style coding    */
                          /* if tot_f is a power of 2 to avoid this if   */
      enrange = r * sy_f;
   else
      enrange -= tmp;
   while (enrange <= Bottom_value) {   /* this while can be unrolled if  */
                                       /* sy_f/tot_f > 1/256             */
      unsigned char byte = enlow >> SHIFT_BITS;
      if (byte == 0xff) {
#ifdef NOWARN
         bytes_to_follow ++;
#else
         if (bytes_to_follow++ == 0xffffffffL) {
            fprintf(stderr,"Too many bytes outstanding - File too large\n");
            exit(1);
         }
#endif
      } else {
         outbyte();
         enbuffer = byte;
      }
      enlow = (enlow << 8) & (Top_value-1);
      enrange <<= 8;
   }
}


/* Calculate culmulative frequency for next symbol. Does NO update!        */
inline unsigned int decode_culfreq( unsigned int tot_f )
{  unsigned int tmp;
   while (derange <= Bottom_value) {
      deoffs = (deoffs<<8) | ((debuffer<<EXTRA_BITS)&0xff);
      debuffer = ReadInputFile();
      deoffs |= debuffer >> (8-EXTRA_BITS);
      derange <<= 8;
   }
   der = derange/tot_f;
   tmp = deoffs/der;
   return (tmp>=tot_f ? tot_f-1 : tmp);
}
/* the considerations about / versus >> and if versus 2 operations written */
/* as comments in encode_freq have influence on the decoding routines too! */


/* Update decoding variables */
inline void decode_update(
    unsigned int sy_f,    /* frequency of symbol */
    unsigned int lt_f,    /* frequency of symbols < the decoded symbol */
    unsigned int tot_f)   /* frequency of all symbols */
{  code_value tmp;
   tmp = der * lt_f;
   deoffs -= tmp;
   if (lt_f + sy_f < tot_f)
     derange = der * sy_f;
   else
     derange -= tmp;
}


/* FINISH ENCODING THE STREAM. */
void done_encoding( void )
{  enlow += enrange >> 1;                      /* select middle of interval*/
   outbyte();                                  /* output outstanding bytes */
   WriteOutputFile( (char)(enbuffer>>SHIFT_BITS) );
   WriteOutputFile( (char)(enbuffer>>(SHIFT_BITS-8)) );
}


/* FINISH DECODING THE STREAM. */
void done_decoding( void )
{
}

#else

#define start_encoding(c)                   void(0)
#define encode_freq( sy_f, lt_f, tot_f )    outfile.WriteInt( lt_f )
#define done_encoding()                     void(0)
#define start_decoding()                    void(0)
#define decode_culfreq( tot_f )             infile.ReadInt()
#define decode_update( sy_f, lt_f, tot_f )  void(0)
#define done_decoding()                     void(0)

#endif

/*
        Determine integer value of base 2 logarithm of integer value
        Use smallest power of two less than input value
*/

static int log2 (unsigned n)

{
        int i;

        for (i = 0; n > 1; i ++, n >>= 1);
        return i;
}




// Arith section ***********************************************************

struct Arith {
    static uint ints, chars, codes, emptycodes, escapes, first_escapes, zeroes, ones;

#ifdef PRINT_STATS
    static void ClearCnts()         { ints=chars=codes=emptycodes=escapes=first_escapes=zeroes=ones=0; }
    static void intspp()            { ints++;  }
    static void charspp()           { chars++; }
    static void codespp()           { codes++; }
    static void emptycodespp()      { emptycodes++; }
    static void escapespp()         { escapes++; }
    static void first_escapespp()   { first_escapes++; }
    static void zeroespp()          { zeroes++; }
    static void onespp()            { ones++; }
#else
    static void ClearCnts()         {}
    static void intspp()            {}
    static void charspp()           {}
    static void codespp()           {}
    static void emptycodespp()      {}
    static void escapespp()         {}
    static void first_escapespp()   {}
    static void zeroespp()          {}
    static void onespp()            {}
#endif

    static void  init();
    static void  done();
    static void  Encode(uint base,uint count,uint range);
    static void  EncodeEscape(uint base,uint count,uint range);
    static void  Encode1(uint base,uint range);
    static void  Encode256(uint n);
    static void  EncodeChar(uchar c);
    static void  EncodeInt(uint n);
    static uint  Decode256();
    static uchar DecodeChar();
    static uint  DecodeInt();
    static uint  Decode(uint range);
    static void  Update(uint base,uint count,uint range);
    static uint  Decode1(uint range);

} dummyArith;
uint Arith::ints=0, Arith::chars=0, Arith::codes=0,
     Arith::emptycodes=0, Arith::escapes=0, Arith::first_escapes=0,
     Arith::zeroes=0, Arith::ones=0;

INLINE void Arith::init() {
    CodedBytes=0;
    test_command( start_encoding(0), (void)start_decoding() );
}

INLINE void Arith::done() {
    test_command( done_encoding(), done_decoding() );
}

inline void Arith::Encode( uint base, uint count, uint range ) {
#ifdef ARITH_PRINT
    printf( " %u %u %u\n", base, count, range );
#endif

    codespp();
#ifdef DEBUG
    if(!( range>0 && range<MIN_RANGE && count>0 && base+count<=range )) {
        debug_printf(( " %u %u %u\n", base, count, range ));
        assert(0);
    }
#endif
    encode_freq( count, base, range );
    if( count==range ) {
        emptycodespp();
    }
}

inline void Arith::EncodeEscape( uint base, uint count, uint range ) {
    escapespp();
    Encode( base, count, range );
}

inline void Arith::Encode1( uint base, uint range ) {
    Encode( base, 1, range );
}

inline void Arith::Encode256( uint n ) {
    assert( n<=255 );
    if( n==0 ) {
        zeroespp();
    } else if( n==1 ) {
        onespp();
    }
    Encode1( n, 256 );
}

inline void Arith::EncodeChar( uchar c ) {
    charspp();
    Encode256(c);
}

INLINE void Arith::EncodeInt( uint n ) {
    intspp();
    if( n<254 ) {
        Encode256(n);
    } else if( n<=65535u ) {
        Encode256(254);
        Encode256(n&255);
        Encode256(n>>8);
    } else {
        uchar *p=(uchar*)&n;
        uint  i=sizeof(n);

        Encode256(255);
        do {
            Encode256(*p++);
        } while( --i );
    }
}

inline uint Arith::Decode( uint range ) {
    assert( range<MIN_RANGE );
    return decode_culfreq(range);
}

inline void Arith::Update( uint base, uint count, uint range ) {
#ifdef ARITH_PRINT
    printf( " %u %u %u\n", base, count, range );
#endif

    assert( range>0 && range<MIN_RANGE && count>0 && base+count<=range );
    decode_update( count, base, range );
}

inline uint Arith::Decode1( uint range ) {
    uint n = Decode(range);
    Update( n, 1, range );
    return n;
}

inline uint Arith::Decode256() {
    return Decode1(256);
}

inline uchar Arith::DecodeChar() {
    charspp();
    return Decode256();
}

INLINE uint Arith::DecodeInt() {
    intspp();

    uint n = Decode256();
    if( n==254 ) {
        n = Decode256();
        n += Decode256()<<8;
    } else if( n==255 ) {
        uchar *p=(uchar*)&n;
        uint  i=sizeof(n);

        do {
            *p++ = Decode256();
        } while( --i );
    }
    return n;
}



// Context tree structures section *****************************************

struct FreeMem {
    static uchar *table, *ptr;
    static uint size;
    static void init() {
        table=new uchar[size];
        if( table==0 ) {
            error( M_NOTREE );
        }
    }
    static void clear() {
        ptr=table+size;
    }
    static void* alloc(size_t bytes) {
        if( ptr-table < bytes ) {
            error(M_NOMEMORY);
        }
        return (void*)(ptr-=bytes);
    }
    static void done() {
    }
} dummyFreeMem;
uchar *FreeMem::table=0, *FreeMem::ptr=0;
uint FreeMem::size=0;

struct allocator {
    void* operator new(size_t bytes) {
        return FreeMem::alloc(bytes);
    }
    void operator delete(void*) {}
};

struct context;

struct node : allocator {
    static uint cnt, origcnt;
    uint count, base;
    node *next;
    context *hint;
    uchar c;

#ifdef TEST_TREE
    void Test(uint level);
#endif

#if defined(DEBUG) || defined(PRINT_STATS)
    static void cntpp() { cnt++; }
    static void cntmm() { cnt--; }
#else
    static void cntpp() {}
    static void cntmm() {}
#endif

    node( uchar new_c, uint new_count ) {
        c=new_c;
        count=new_count;
        next=0;
        hint=0;
        cntpp();
    }
    node( uchar new_c, uint new_base, uint new_count ) {
        c=new_c;
        base=new_base;
        count=new_count;
        next=0;
        hint=0;
        cntpp();
    }
    void AddCount( uint new_count ) {
        // 忇