The code here is just for research purposes. You know the drill. Use any code at your own risk.
Sample Code:
// Sample.cpp // // Randy McNabb // December 1, 2005 // // DESCRIPTION // // // This program is intended to demonstrate // the ability to effectively output bits // from the encoding process in blocks // instead of bit by bit. // // The program takes two arguments, an input // file name and an output file name which // are assigned to stdin and stdout. Full // 32 bit values are used for the high and // low registers. A single set bit is // written to the output file to flush the // encoder as it is intended for the decoder // to supply 0 bits past the end of the file. // Output bytes are filled from left to right // in both output examples. // // The model is a simple segmented cumulative // table to decrease the number of updates // needed to maintain the frequencies. // // Pre-compiler directives are used to cut // out code not used by the chosen output // method. Define Use_Block_Output the // enable block output of the encoded data // or comment it out the use the usual encoding // method described in the 1987 CACM article by // Witten, Neal, and Cleary. // // I offer my apologies for any lack in // programming skills. // // Comment out to output bit by bit #define Use_Block_Output #include <stdio.h> #include <time.h> #include <memory.h> // routines void Flush_Buffer(); void EncodeSymbol(unsigned char symbol); void IntializeEncoder(); void StartModel(); void UpdateModel(unsigned long symbol); unsigned long Read_Data(unsigned long bits_needed); // Encoder variables unsigned long low; unsigned long high; unsigned long hold_bits; unsigned long bit_count; unsigned long code; // output stuff #define BUFFERSIZE 65536 #define ROOMFORCARRY 8 #define BUFFERPADDING BUFFERSIZE + ROOMFORCARRY + 4 unsigned char outbuffer[BUFFERSIZE + BUFFERPADDING]; unsigned char *currentbyte = outbuffer; unsigned char *bufferoverrun = outbuffer + BUFFERSIZE; #ifdef Use_Block_Output // ******** exclusive to block output ************** void Write_Data( unsigned long data, unsigned int bits_needed); unsigned char *maxbuffer = bufferoverrun + ROOMFORCARRY; unsigned char *outbyte = ((unsigned char *)&hold_bits) + 3; // ************************************************* #else // ******** exclusive to regular output ************ #define First_qtr 0x40000000ul #define Half (2*First_qtr) #define Third_qtr (3*First_qtr) unsigned long underflow_count; // ************************************************* #endif // Model stuff #define ALPHABETCOUNT 256 #define MAXSCALE 0X40000000 unsigned long table[ALPHABETCOUNT + 1]; unsigned long toffs[(ALPHABETCOUNT>>4)+1] = {0}; int main(int argc, char* argv[]) { fprintf( stderr, "Encoding " ); if ( argc > 1 ) { freopen( argv[ 1 ], "rb", stdin ); fprintf( stderr, "%s", argv[ 1 ] ); } else fprintf( stderr, "stdin" ); fprintf( stderr, " to " ); if ( argc > 2 ) { freopen( argv[ 2 ], "wb", stdout ); fprintf( stderr, "%s", argv[ 2 ] ); } else fprintf( stderr, "stdout" ); fprintf( stderr, "\n" ); int inchar; // time check clock_t start, finish; double duration; start = clock(); IntializeEncoder(); StartModel(); for (;;){ // Loop through characters. // inchar = getc(stdin); // Read the next character. if (inchar==EOF) break; // Exit loop on end-of-file. EncodeSymbol(inchar); UpdateModel(inchar); } Flush_Buffer(); finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; fprintf( stderr, "Compression Time : %2.2f seconds\n", duration ); return 0; } #ifdef Use_Block_Output void Write_Data( unsigned long data, unsigned int bits_needed) { if ( bits_needed > bit_count ){ unsigned int leftoverbits = bits_needed - bit_count; Write_Data(data >> leftoverbits, bit_count); bit_count--; // don't write over last bit Write_Data(data & (~(0XFFFFFFFF << leftoverbits)), leftoverbits); } else{ bit_count -= bits_needed; unsigned long t = hold_bits + (data << bit_count); // check for carry if ( t < hold_bits ){ unsigned char *tempbyte = currentbyte - 1; while ( *tempbyte == 0XFF ){ *tempbyte = 0; tempbyte--; } *tempbyte = *tempbyte + 1;; } hold_bits = t; // adjust to overlap first bit of next data written bit_count ++; // write whole bytes to outbuffer while ( bit_count < 25 ){ *currentbyte = *outbyte;// outbyte points to highest byte of hold_bits currentbyte++; hold_bits <<= 8; bit_count += 8; } } // is outbuffer full if ( currentbyte >= maxbuffer ){ fwrite(outbuffer, 1, BUFFERSIZE, stdout); memcpy(outbuffer, bufferoverrun, BUFFERPADDING); currentbyte -= BUFFERSIZE; } } #else inline void output_bit( int bit ) { hold_bits <<= 1; if (bit) hold_bits |= 0x01; bit_count -= 1; if (bit_count==0) { *currentbyte = (char) hold_bits; currentbyte++; if ( currentbyte == bufferoverrun ){ fwrite(outbuffer, 1, BUFFERSIZE, stdout); currentbyte = outbuffer; } bit_count = 8; } } #endif void Flush_Buffer() { #ifdef Use_Block_Output Write_Data(1, 1); while ( hold_bits ){ *currentbyte = *outbyte; currentbyte++; hold_bits <<= 8; } #else output_bit(1); while ( underflow_count ){ output_bit(0); underflow_count--; } hold_bits <<= bit_count; if ( (unsigned char )hold_bits ){ *currentbyte = (char) hold_bits; currentbyte++; } #endif fwrite(outbuffer, 1, currentbyte - outbuffer, stdout); } void EncodeSymbol(unsigned char symbol) { // calculate new high and low __int64 range = (__int64)high - low + 1; high = low + (unsigned long)((range * (table[symbol]+ toffs[symbol>>4])/(table[0]+toffs[0])) - 1); low = low + (unsigned long)(range * (table[symbol + 1]+ toffs[(symbol+1)>>4])/(table[0]+toffs[0])); #ifdef Use_Block_Output unsigned long mincount; if ( high == low ){ Write_Data(low, 32); low = 0; high = 0XFFFFFFFF; bit_count--; // don't write over last bit } else{ // build mask unsigned long temp = high ^ low; unsigned long mask = (temp^((low & temp)<<1)); // find index double hold = (temp^((low & temp)<<1)); mincount = 1055-(*(((unsigned long*)&hold)+1)>>20); // output bits Write_Data(low >>(32 - mincount), mincount--); // Update high and low low = (low << (mincount))&0X7FFFFFFF; high = (~((~high) << ( mincount))) | 0X80000000; } #else for (;;) { if (high<Half) { output_bit(0); while ( underflow_count ){ output_bit(1); underflow_count--; } } else if (low>=Half) { output_bit(1); while ( underflow_count ){ output_bit(0); underflow_count--; } low -= Half; high -= Half; } else if (low>=First_qtr && high<Third_qtr) { underflow_count += 1; low -= First_qtr; high -= First_qtr; } else break; low = low<<1; high = (high<<1)+1; } #endif } void IntializeEncoder() { low = 0; high = 0xFFFFFFFF; hold_bits = 0; #ifdef Use_Block_Output bit_count = 32; #else bit_count = 8; underflow_count = 0; #endif } void StartModel() { // set up main table int index = ALPHABETCOUNT; unsigned long current_count = 0; while ( index >= 0 ){ table[index--] = current_count++; } // set up offset table index = (ALPHABETCOUNT >> 4); while ( index >= 0 ){ toffs[index] = 0; index--; } } void UpdateModel(unsigned long symbol) { int index = (symbol >> 4) - 1; while ( index >= 0 ){ toffs[index--]++; } index = symbol & 0xF; while ( index >= 0 ){ table[symbol--]++; index--; } // downsize model if ( (toffs[0]+table[0]) > MAXSCALE ){ unsigned long hold; unsigned long last = 0; index = ALPHABETCOUNT - 1; while ( index >= 0 ){ hold = table[index] + toffs[index >> 4]; table[index] = ((hold - last) >> 2) + 1 + table[index + 1]; last = hold; index--; } index = (ALPHABETCOUNT >> 4); while ( index >= 0 ){ toffs[index] = 0; index--; } } }
