[Mndiff-dev] [mndiff]: r15 - trunk/mnzip/mnzip.c
michael
subversion at mplayerhq.hu
Sat Jun 9 12:44:15 CEST 2007
Author: michael
Date: Sat Jun 9 12:44:14 2007
New Revision: 15
Log:
borrow AC state transition table from paq8
1% better compression
GPL now due to the table
Modified:
trunk/mnzip/mnzip.c
Modified: trunk/mnzip/mnzip.c
==============================================================================
--- trunk/mnzip/mnzip.c (original)
+++ trunk/mnzip/mnzip.c Sat Jun 9 12:44:14 2007
@@ -1,20 +1,21 @@
/*
* Copyright (c) 2007 Michael Niedermayer <michaelni at gmx.at>
*
- * mnzip is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2.1 of the License, or (at your option) any later version.
+ * mnzip is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
*
* mnzip is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * Lesser General Public License for more details.
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
*
- * You should have received a copy of the GNU Lesser General Public
- * License along with mnzip; if not, write to the Free Software
+ * You should have received a copy of the GNU General Public License
+ * along with mnzip; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*
+ * Note everything in this file except the state_table can be used under LGPL
*/
#include <stdlib.h>
@@ -349,6 +350,74 @@ static int ibwt(uint8_t *in, unsigned in
free(idx);
return 0;
}
+
+//from paq8l.cpp GPL
+static const uint8_t state_table[256][4]={
+ { 1, 2, 0, 0},{ 3, 5, 1, 0},{ 4, 6, 0, 1},{ 7, 10, 2, 0}, // 0-3
+ { 8, 12, 1, 1},{ 9, 13, 1, 1},{ 11, 14, 0, 2},{ 15, 19, 3, 0}, // 4-7
+ { 16, 23, 2, 1},{ 17, 24, 2, 1},{ 18, 25, 2, 1},{ 20, 27, 1, 2}, // 8-11
+ { 21, 28, 1, 2},{ 22, 29, 1, 2},{ 26, 30, 0, 3},{ 31, 33, 4, 0}, // 12-15
+ { 32, 35, 3, 1},{ 32, 35, 3, 1},{ 32, 35, 3, 1},{ 32, 35, 3, 1}, // 16-19
+ { 34, 37, 2, 2},{ 34, 37, 2, 2},{ 34, 37, 2, 2},{ 34, 37, 2, 2}, // 20-23
+ { 34, 37, 2, 2},{ 34, 37, 2, 2},{ 36, 39, 1, 3},{ 36, 39, 1, 3}, // 24-27
+ { 36, 39, 1, 3},{ 36, 39, 1, 3},{ 38, 40, 0, 4},{ 41, 43, 5, 0}, // 28-31
+ { 42, 45, 4, 1},{ 42, 45, 4, 1},{ 44, 47, 3, 2},{ 44, 47, 3, 2}, // 32-35
+ { 46, 49, 2, 3},{ 46, 49, 2, 3},{ 48, 51, 1, 4},{ 48, 51, 1, 4}, // 36-39
+ { 50, 52, 0, 5},{ 53, 43, 6, 0},{ 54, 57, 5, 1},{ 54, 57, 5, 1}, // 40-43
+ { 56, 59, 4, 2},{ 56, 59, 4, 2},{ 58, 61, 3, 3},{ 58, 61, 3, 3}, // 44-47
+ { 60, 63, 2, 4},{ 60, 63, 2, 4},{ 62, 65, 1, 5},{ 62, 65, 1, 5}, // 48-51
+ { 50, 66, 0, 6},{ 67, 55, 7, 0},{ 68, 57, 6, 1},{ 68, 57, 6, 1}, // 52-55
+ { 70, 73, 5, 2},{ 70, 73, 5, 2},{ 72, 75, 4, 3},{ 72, 75, 4, 3}, // 56-59
+ { 74, 77, 3, 4},{ 74, 77, 3, 4},{ 76, 79, 2, 5},{ 76, 79, 2, 5}, // 60-63
+ { 62, 81, 1, 6},{ 62, 81, 1, 6},{ 64, 82, 0, 7},{ 83, 69, 8, 0}, // 64-67
+ { 84, 71, 7, 1},{ 84, 71, 7, 1},{ 86, 73, 6, 2},{ 86, 73, 6, 2}, // 68-71
+ { 44, 59, 5, 3},{ 44, 59, 5, 3},{ 58, 61, 4, 4},{ 58, 61, 4, 4}, // 72-75
+ { 60, 49, 3, 5},{ 60, 49, 3, 5},{ 76, 89, 2, 6},{ 76, 89, 2, 6}, // 76-79
+ { 78, 91, 1, 7},{ 78, 91, 1, 7},{ 80, 92, 0, 8},{ 93, 69, 9, 0}, // 80-83
+ { 94, 87, 8, 1},{ 94, 87, 8, 1},{ 96, 45, 7, 2},{ 96, 45, 7, 2}, // 84-87
+ { 48, 99, 2, 7},{ 48, 99, 2, 7},{ 88,101, 1, 8},{ 88,101, 1, 8}, // 88-91
+ { 80,102, 0, 9},{103, 69,10, 0},{104, 87, 9, 1},{104, 87, 9, 1}, // 92-95
+ {106, 57, 8, 2},{106, 57, 8, 2},{ 62,109, 2, 8},{ 62,109, 2, 8}, // 96-99
+ { 88,111, 1, 9},{ 88,111, 1, 9},{ 80,112, 0,10},{113, 85,11, 0}, // 100-103
+ {114, 87,10, 1},{114, 87,10, 1},{116, 57, 9, 2},{116, 57, 9, 2}, // 104-107
+ { 62,119, 2, 9},{ 62,119, 2, 9},{ 88,121, 1,10},{ 88,121, 1,10}, // 108-111
+ { 90,122, 0,11},{123, 85,12, 0},{124, 97,11, 1},{124, 97,11, 1}, // 112-115
+ {126, 57,10, 2},{126, 57,10, 2},{ 62,129, 2,10},{ 62,129, 2,10}, // 116-119
+ { 98,131, 1,11},{ 98,131, 1,11},{ 90,132, 0,12},{133, 85,13, 0}, // 120-123
+ {134, 97,12, 1},{134, 97,12, 1},{136, 57,11, 2},{136, 57,11, 2}, // 124-127
+ { 62,139, 2,11},{ 62,139, 2,11},{ 98,141, 1,12},{ 98,141, 1,12}, // 128-131
+ { 90,142, 0,13},{143, 95,14, 0},{144, 97,13, 1},{144, 97,13, 1}, // 132-135
+ { 68, 57,12, 2},{ 68, 57,12, 2},{ 62, 81, 2,12},{ 62, 81, 2,12}, // 136-139
+ { 98,147, 1,13},{ 98,147, 1,13},{100,148, 0,14},{149, 95,15, 0}, // 140-143
+ {150,107,14, 1},{150,107,14, 1},{108,151, 1,14},{108,151, 1,14}, // 144-147
+ {100,152, 0,15},{153, 95,16, 0},{154,107,15, 1},{108,155, 1,15}, // 148-151
+ {100,156, 0,16},{157, 95,17, 0},{158,107,16, 1},{108,159, 1,16}, // 152-155
+ {100,160, 0,17},{161,105,18, 0},{162,107,17, 1},{108,163, 1,17}, // 156-159
+ {110,164, 0,18},{165,105,19, 0},{166,117,18, 1},{118,167, 1,18}, // 160-163
+ {110,168, 0,19},{169,105,20, 0},{170,117,19, 1},{118,171, 1,19}, // 164-167
+ {110,172, 0,20},{173,105,21, 0},{174,117,20, 1},{118,175, 1,20}, // 168-171
+ {110,176, 0,21},{177,105,22, 0},{178,117,21, 1},{118,179, 1,21}, // 172-175
+ {110,180, 0,22},{181,115,23, 0},{182,117,22, 1},{118,183, 1,22}, // 176-179
+ {120,184, 0,23},{185,115,24, 0},{186,127,23, 1},{128,187, 1,23}, // 180-183
+ {120,188, 0,24},{189,115,25, 0},{190,127,24, 1},{128,191, 1,24}, // 184-187
+ {120,192, 0,25},{193,115,26, 0},{194,127,25, 1},{128,195, 1,25}, // 188-191
+ {120,196, 0,26},{197,115,27, 0},{198,127,26, 1},{128,199, 1,26}, // 192-195
+ {120,200, 0,27},{201,115,28, 0},{202,127,27, 1},{128,203, 1,27}, // 196-199
+ {120,204, 0,28},{205,115,29, 0},{206,127,28, 1},{128,207, 1,28}, // 200-203
+ {120,208, 0,29},{209,125,30, 0},{210,127,29, 1},{128,211, 1,29}, // 204-207
+ {130,212, 0,30},{213,125,31, 0},{214,137,30, 1},{138,215, 1,30}, // 208-211
+ {130,216, 0,31},{217,125,32, 0},{218,137,31, 1},{138,219, 1,31}, // 212-215
+ {130,220, 0,32},{221,125,33, 0},{222,137,32, 1},{138,223, 1,32}, // 216-219
+ {130,224, 0,33},{225,125,34, 0},{226,137,33, 1},{138,227, 1,33}, // 220-223
+ {130,228, 0,34},{229,125,35, 0},{230,137,34, 1},{138,231, 1,34}, // 224-227
+ {130,232, 0,35},{233,125,36, 0},{234,137,35, 1},{138,235, 1,35}, // 228-231
+ {130,236, 0,36},{237,125,37, 0},{238,137,36, 1},{138,239, 1,36}, // 232-235
+ {130,240, 0,37},{241,125,38, 0},{242,137,37, 1},{138,243, 1,37}, // 236-239
+ {130,244, 0,38},{245,135,39, 0},{246,137,38, 1},{138,247, 1,38}, // 240-243
+ {140,248, 0,39},{249,135,40, 0},{250, 69,39, 1},{ 80,251, 1,39}, // 244-247
+ {140,252, 0,40},{249,135,41, 0},{250, 69,40, 1},{ 80,251, 1,40}, // 248-251
+ {140,252, 0,41}}; // 252, 253-255 are reserved
+
#if 1
static inline int clip(int a, int amin, int amax){
if (a < amin) return amin;
@@ -356,7 +425,18 @@ static inline int clip(int a, int amin,
else return a;
}
#endif
-static inline void putbit_clip(RangeCoder *c, uint16_t *state, int b, int min, int max){
+
+static unsigned short prob[32][256];
+
+static void init_prob(unsigned short *prob){
+ int i;
+ for(i=0;i<256*32; i++){
+ int ctx= i&0xFF;
+ prob[i]= 256*256*(state_table[ctx][3]+1) / (state_table[ctx][2] + state_table[ctx][3]+2);
+ }
+}
+
+static inline void putbit_clip(RangeCoder *c, uint32_t *state, int b, int min, int max, unsigned short *prob){
#if 0
if(*state &1){
int x= (*state&0xFF)>>1;
@@ -380,93 +460,99 @@ static inline void putbit_clip(RangeCode
#elif 0
put_rac(c, (uint8_t*)state + 1, b);
#else
- uint8_t s= clip(*state>>8, 1, 255);
+ int ctx= *state;
+
+ uint8_t s= clip(prob[ctx]>>8, 1, 255);
put_rac(c, &s, b);
+ prob[ctx]+= ((b*65536 - prob[ctx])*4 + 512)>>10;
- *state+= ((b*65536 - *state)*30 + 512)>>10;
+ *state= state_table[ctx][b];
#endif
}
-static inline void putbit(RangeCoder *c, uint16_t *state, int b){
- putbit_clip(c, state, b, 1, 255);
+static inline void putbit(RangeCoder *c, uint32_t *state, int b, unsigned short *prob){
+ putbit_clip(c, state, b, 1, 255, prob);
}
-static inline int getbit(RangeCoder *c, uint16_t *state){
- uint8_t s= clip(*state>>8, 1, 255);
+static inline int getbit(RangeCoder *c, uint32_t *state, unsigned short *prob){
+ int ctx= *state;
+
+ uint8_t s= clip(prob[ctx]>>8, 1, 255);
int b= get_rac(c, &s);
+ prob[ctx]+= ((b*65536 - prob[ctx])*4 + 512)>>10;
- *state+= ((b*65536 - *state)*30 + 512)>>10;
+ *state= state_table[ctx][b];
return b;
}
-static inline void put_symbol(RangeCoder *c, uint16_t *state, int v){
+static inline void put_symbol(RangeCoder *c, uint32_t *state, int v){
int i;
if(v){
const int e= av_log2(v);
const int el= MIN(e, 8);
- putbit(c, state+0, 0);
+ putbit(c, state+0, 0, prob[0]);
for(i=0; i<el; i++){
- putbit(c, state+1+i, 1); //1..8
+ putbit(c, state+1+i, 1, prob[1+i]); //1..8
}
for(; i<e; i++){
- putbit(c, state+1+7, 1); //1..8
+ putbit(c, state+1+7, 1, prob[1+7]); //1..8
}
- putbit(c, state+1+MIN(i,7), 0);
+ putbit(c, state+1+MIN(i,7), 0, prob[1+MIN(i,7)]);
for(i=e-1; i>=el; i--){
- putbit(c, state+9+7, (v>>i)&1); //9..16
+ putbit(c, state+9+7, (v>>i)&1, prob[9+7]); //9..16
}
for(; i>=0; i--){
- putbit(c, state+9+i, (v>>i)&1); //9..16
+ putbit(c, state+9+i, (v>>i)&1, prob[9+i]); //9..16
}
}else{
- putbit(c, state+0, 1);
+ putbit(c, state+0, 1, prob[0]);
}
}
-static inline void put_symbol_255(RangeCoder *c, uint16_t *state, int v){
+static inline void put_symbol_255(RangeCoder *c, uint32_t *state, int v){
const int e= av_log2(v);
int i;
assert(v);
assert(e<8);
- putbit(c, state, e>3); //0
- putbit(c, state+1+(e>3), (e&2)>>1); //1..2
- putbit(c, state+3+(e>>1), (e&1)); //3..6
+ putbit(c, state , e>3 , prob[17]); //0
+ putbit(c, state+1+(e>3) , (e&2)>>1, prob[17+1+(e>3)]); //1..2
+ putbit(c, state+3+(e>>1), (e&1) , prob[17+3+(e>>1)]); //3..6
for(i=e-1; i>=0; i--)
- putbit(c, state+7+i, (v>>i)&1); //7..13
+ putbit(c, state+7+i, (v>>i)&1 , prob[17+7+i]); //7..13
}
-static inline int get_symbol_255(RangeCoder *c, uint16_t *state){
+static inline int get_symbol_255(RangeCoder *c, uint32_t *state){
int e,a,i;
- e =4*getbit(c, state); //0
- e+=2*getbit(c, state+1+(e>3)); //1..2
- e+= getbit(c, state+3+(e>>1)); //3..6
+ e =4*getbit(c, state , prob[17]); //0
+ e+=2*getbit(c, state+1+(e>3) , prob[17+1+(e>3)]); //1..2
+ e+= getbit(c, state+3+(e>>1), prob[17+3+(e>>1)]); //3..6
a= 1;
for(i=e-1; i>=0; i--)
- a += a + getbit(c, state+7 + i); //7..13
+ a += a + getbit(c, state+7 + i, prob[17+7+i]); //7..13
return a;
}
-static inline int get_symbol(RangeCoder *c, uint16_t *state){
- if(getbit(c, state+0))
+static inline int get_symbol(RangeCoder *c, uint32_t *state){
+ if(getbit(c, state+0, prob[0]))
return 0;
else{
int i, e, a;
e= 0;
- while(getbit(c, state+1 + MIN(e,7))) //1..8
+ while(getbit(c, state+1 + MIN(e,7), prob[1 + MIN(e,7)])) //1..8
e++;
a= 1;
for(i=e-1; i>=0; i--)
- a += a + getbit(c, state+9 + MIN(i,7)); //9..16
+ a += a + getbit(c, state+9 + MIN(i,7), prob[9 + MIN(i,7)]); //9..16
return a;
}
@@ -488,7 +574,7 @@ static unsigned int compress(uint8_t *ou
unsigned int start,j, out_size;
int i;
RangeCoder c;
- uint16_t state[16*512*32+1];
+ uint32_t state[16*512*32+1];
int mtf[256];
fprintf(stderr, "bwt\n");
start= bwt(tmp, in, len);
@@ -500,7 +586,7 @@ fprintf(stderr,"range coding (%d %d)\n",
wb32(out, start); out+=4;
wb32(out, 0 ); out+=4;
- memset(state, 128, sizeof(state));
+ memset(state, 0, sizeof(state));
//memset(state, 3, sizeof(state));
for(i=0; i<256; i++)
@@ -554,7 +640,7 @@ static int decompress(FILE *fi, int low_
int ret;
uint8_t *tmp; //FIXME reduce memory needs
RangeCoder c;
- uint16_t state[32*1024+1]; //FIXME isnt needed to be that large
+ uint32_t state[32*1024+1]; //FIXME isnt needed to be that large
unsigned int histogram[256]={0};
int mtf[256];
uint8_t tmpX[16];
@@ -582,7 +668,7 @@ fprintf(stderr," block (%d %d %d)\n", ou
//FIXME check all fread
- memset(state, 128, sizeof(state));
+ memset(state, 0, sizeof(state));
ff_init_range_decoder(&c, in, in_len);
ff_build_rac_states(&c, 0.04*(1LL<<32), 256-4);
@@ -657,6 +743,8 @@ int main(int argc, char **argv){
}
}
+ init_prob(prob);
+
if(comp){
in = malloc(block_size+RADIX_PASSES);
out= malloc(2*block_size + 5000);//FIXME int and buffer overfl
More information about the Mndiff-dev
mailing list