Bit of cleaning up in the byte dumping part. Making use of any remaining bit(s)
[opus.git] / libentcode / bitree.c
1 #include "bitree.h"
2
3 void ec_bitree_to_counts(unsigned *_this,int _sz,int _split){
4   int p;
5   int q;
6   int s;
7   for(p=_split;p>1;p=q){
8     q=p>>1;
9     for(s=p-1;s<_sz;s+=p)_this[s]-=_this[s-q];
10   }
11 }
12
13 void ec_bitree_from_counts(unsigned *_this,int _sz){
14   int p;
15   int q;
16   int s;
17   for(q=1,p=2;p<=_sz;q=p,p=q<<1){
18     for(s=p-1;s<_sz;s+=p)_this[s]+=_this[s-q];
19   }
20 }
21
22 unsigned ec_bitree_get_cumul(const unsigned *_this,int _sym){
23   unsigned ret;
24   ret=0;
25   while(_sym>0){
26     ret+=_this[_sym-1];
27     _sym&=_sym-1;
28   }
29   return ret;
30 }
31
32 unsigned ec_bitree_get_freq(const unsigned *_this,int _sym){
33   unsigned ret;
34   int      p;
35   ret=_this[_sym];
36   p=_sym&_sym+1;
37   while(_sym!=p){
38     ret-=_this[_sym-1];
39     _sym&=_sym-1;
40   }
41   return ret;
42 }
43
44 #if 0
45 /*Fenwick's approach to re-scaling the counts.
46   This tests to be twice as slow or more than the one below, even with inline
47    functions enabled, and without loop vectorization (which would make Moffat's
48    approach even faster).*/
49 void ec_bitree_halve(unsigned *_this,int _sz,int _split){
50   int i;
51   for(i=_sz;i-->0;){
52     ec_bitree_update(_this,_sz,i,-(int)(ec_bitree_get_freq(_this,i)>>1));
53   }
54 }
55 #else
56 /*Fenwick mentions that this approach is also possible, and this is what
57    Moffat uses.
58   Simply convert the tree into a simple array of counts, perform the halving,
59    and then convert it back.*/
60 void ec_bitree_halve(unsigned *_this,int _sz,int _split){
61   int i;
62   ec_bitree_to_counts(_this,_sz,_split);
63   /*LOOP VECTORIZES.*/
64   for(i=0;i<_sz;i++)_this[i]-=_this[i]>>1;
65   ec_bitree_from_counts(_this,_sz);
66 }
67 #endif
68
69 #if 0
70 #include <stdio.h>
71 /*Simple regression test code.
72   Compile with bitrenc.c and bitrdec.c as well.*/
73
74 static void ec_bitree_print(unsigned *_this,int _sz){
75   int i;
76   for(i=0;i<_sz;i++)printf("%3i%c",_this[i],i+1<_sz?' ':'\n');
77 }
78
79 int main(void){
80   unsigned t[16]={0,8,4,9,2,10,5,11,1,12,6,13,3,14,7,15};
81   int      fl;
82   int      s;
83   int      i;
84   ec_bitree_print(t,16);
85   ec_bitree_from_counts(t,16);
86   ec_bitree_print(t,16);
87   for(i=0;i<=16;i++)printf("%3i%c",ec_bitree_get_cumul(t,i),i<16?' ':'\n');
88   for(i=0;i<t[15];i++){
89     s=ec_bitree_find_and_update(t,16,16,i,&fl,0);
90     printf("%3i: %i %3i\n",i,s,fl);
91   }
92   for(i=0;i<16;i++){
93     s=ec_bitree_find_and_update(t,16,ec_bitree_get_cumul(t,i),&fl,100);
94     ec_bitree_to_counts(t,16,16);
95     ec_bitree_print(t,16);
96     ec_bitree_from_counts(t,16);
97     ec_bitree_update(t,16,s,-100);
98   }
99   return 0;
100 }
101 #endif