1 /* b_i_t.h */ 2 /* this implements bit indexed trees for culmulative frequency storeage */ 3 /* described in */ 4 /* Peter Fenwick: A New Data Structure for Cumulative Probability Tables */ 5 /* Technical Report 88, Dep. of Computer Science, University of Auckland, NZ */ 6 7 #ifndef b_i_t_h 8 #define b_i_t_h 9 10 #include "port.h" 11 #include "rangecod.h" 12 //typedef uint4 freq; 13 typedef uint4 symb; 14 15 typedef struct { 16 symb size, mask; 17 freq *cf, *f, totfreq; 18 } cumtbl; 19 20 /* returns the culmulative frequency < the given symbol */ 21 Inline freq getcf(symb s, cumtbl *tbl); 22 23 /* updates the given frequency */ 24 #define updatefreq(_s,_tbl,_delta) \ 25 { int upd_delta = (_delta); \ 26 symb upd_s = (_s); \ 27 (_tbl)->f[upd_s] += upd_delta; \ 28 updatecumonly(upd_s,_tbl,upd_delta); } 29 30 /* updates the given culmulative frequency */ 31 Inline void updatecumonly(symb s, cumtbl *tbl, int delta); 32 33 /* get symbol for this culmulative frequency */ 34 Inline symb getsym(freq f, cumtbl *tbl); 35 36 /* scales the culmulative frequency tables by 0.5 and keeps nonzero values */ 37 void scalefreq(cumtbl *tbl); 38 39 /* scales the culmulative frequency tables by 0.5 and keeps nonzero values */ 40 void scalefreqcond(cumtbl *tbl, uint *donotuse); 41 42 /* allocates memory for the frequency table and initializes it */ 43 int initfreq(cumtbl *tbl, symb tblsize, freq initvalue); 44 45 /* does the obvious thing */ 46 void freefreq(cumtbl *tbl); 47 48 #endif 49