// ARENC.cpp : Defines the entry point for the console application. // //This is DEMO version of range encoder written for research purposes by //Andrew Polar (www.ezcodesample.com, Dec. 24, 2006). The program reproduce //algorithm of G.N.N. Martin, published in 1979. It was tested, however, //you can use it on your own risk without guaranteed successful encoding //and decoding for every possible data sample. Author does not accept any //responsibility for the use or misuse of this program. //The permission to copy and modify code is hereby granted as long as this //disclaimer stays. In case this code is chosen for production the user is //responsible for purchasing of necessary licenses to avoid possible patent //infringement. Last correction Jan.24, 2007. //No warranty, however, any data sample that crash program or cause wrong //result will be carefully investigated when sent to author. Find contact //information by WHOIS query for www.ezcodesample.com #include #include #include #include #include typedef struct { int* value; int size; }INT_DATA; double entropy24(int* data, int size) { int max_size = 1 << 24; int min, counter; int* buffer; double entropy; double log2 = log(2.0); double prob; min = data[0]; for (counter=0; counter 0) { prob = (double)buffer[counter]; prob /= (double)size; entropy += log(prob)/log2*prob; } } entropy *= -1.0; for (counter=0; counter= 0.5) return ceil(x); else return floor(x); } double MakeData(INT_DATA* int_data, int size, int MIN, int MAX, int redundancy_factor) { int counter, cnt, min, max; double buf; if (redundancy_factor <= 1) redundancy_factor = 1; if (MAX <= MIN) MAX = MIN + 1; if (int_data->size > 0) { if (int_data->value) free(int_data->value); int_data->size = 0; } int_data->size = size; int_data->value = (int*)malloc(int_data->size*sizeof(int)); srand((unsigned)time(0)); for (counter=0; countersize; counter++) { buf = 0; for (cnt=0; cntvalue[counter] = ((int)buf)/redundancy_factor; } min = int_data->value[0]; max = int_data->value[0]; for (counter=0; countersize; counter++) { if (int_data->value[counter] > max) max = int_data->value[counter]; if (int_data->value[counter] < min) min = int_data->value[counter]; } for (counter=0; countersize; counter++) { buf = (double)(int_data->value[counter] - min); buf /= (double)(max - min); buf *= (double)(MAX - MIN); buf = round(buf); int_data->value[counter] = (int)buf + MIN; } return entropy24(int_data->value, int_data->size); } ////////////////////////////////////Encoder//////////////////////////////// unsigned current_byte; unsigned char bit_mask; bool skip_zeros = true; unsigned char* g_bin_data = 0; long long SafeProduct(long long x, int y, int mask, int& shift) { long long p = x * (long long)y; shift = 0; while (p > mask) { p >>= 1; shift++; } return p; } long long getBits(long long msg, int bits) { for (int i=0; i>= 1; if (bit_mask == 0) { current_byte++; bit_mask = 128; } } return msg; } void setBits(long long msg, int bits) { unsigned char shift = 63; for (int i=0; i> shift) & 1) > 0) { g_bin_data[current_byte] |= bit_mask; skip_zeros = false; } shift--; if (skip_zeros == false) { bit_mask >>= 1; if (bit_mask == 0) { current_byte++; bit_mask = 128; } } } } //////////////////////////////////////////////////////////////////////////// int main() { INT_DATA int_data; int SIZE = 1000000; int MIN = 1; int MAX = 200; int redundancy_factor = 10; double entropy = MakeData(&int_data, SIZE, MIN, MAX, redundancy_factor); int Bytes = (int)(ceil((double)(SIZE) * entropy)/8.0); printf("Entropy %f, estimated compressed size %d bytes\n", entropy, Bytes); g_bin_data = (unsigned char*)malloc(Bytes * 2); memset(g_bin_data, 0x00, Bytes * 2); //prepare data for encoding int max = int_data.value[0]; int min = int_data.value[0]; for (int i=0; i int_data.value[i]) min = int_data.value[i]; } for (int i=0; i 0) { Denominator >>= 1; base++; } Denominator = (1 << base); if (Denominator < SIZE) { Denominator <<= 1; } unsigned SIZE_MASK = Denominator - 1; if (SIZE_MASK > 0xFFFF) { SIZE_MASK = 0xFFFF; Denominator = SIZE_MASK + 1; base = 16; } double coeff = (double)(SIZE_MASK)/((double)(int_data.size)); for (int i=0; i 0) { double ff = (double)(f[i]); ff *= coeff; f[i] = (int)(ff); if (f[i] == 0) f[i] = 1; } } int sm = 0; for (int i=0; i 0) { int mx = f[0]; int ps = 0; for (int i=0; i mx) { mx = f[i]; ps = i; } } f[ps] += diff; } if (diff < 0) { i = 0; while (diff < 0) { if (f[i] > 1) { f[i]--; diff++; } i++; if (i == (range-1)) i = 0; } } //end of correction ////////////////////////////////////////////////////// int* c = (int*)malloc((range+1)*sizeof(int)); memset(c, 0x00, (range+1)*sizeof(int)); c[0] = 0; for (i=1; i> (32 - base); long long Message = 1; //We start message from first positive bit //it must be removed from the stream in decoding. The reason for //that is that first cumulative frequency may have leading zeros //like follows 00010101. By setting first positive bit 100010101 //we mark the beginning of codes. long long Freqs = 1; int shift = 0; current_byte = 0; bit_mask = 128; for (int i=0; i