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