ref: eb5a245ac8622526d45cc46d49f932694745f4c4
parent: 7ff2cbc1bdbe295f3f8979c5bc12a722a8e52be4
author: Jean-Marc Valin <[email protected]>
date: Sun Mar 2 23:11:49 EST 2008
Hadn't realised the bitr* stuff wasn't needed.
--- a/libcelt/Makefile.am
+++ b/libcelt/Makefile.am
@@ -14,7 +14,7 @@
lib_LTLIBRARIES = libcelt.la
# Sources for compilation in the library
-libcelt_la_SOURCES = bands.c bitrdec.c bitree.c bitrenc.c celt.c cwrs.c \
+libcelt_la_SOURCES = bands.c celt.c cwrs.c \
ecintrin.h entcode.c entdec.c entenc.c header.c kiss_fft.c \
kiss_fftr.c laplace.c mdct.c modes.c pitch.c psy.c quant_bands.c \
quant_pitch.c rangedec.c rangeenc.c rate.c vq.c
@@ -23,7 +23,7 @@
libcelt_la_LDFLAGS = -version-info @CELT_LT_CURRENT@:@CELT_LT_REVISION@:@CELT_LT_AGE@
-noinst_HEADERS = _kiss_fft_guts.h arch.h bands.h bitrdec.h bitree.h bitrenc.h \
+noinst_HEADERS = _kiss_fft_guts.h arch.h bands.h \
cwrs.h ecintrin.h entcode.h entdec.h entenc.h fixed_generic.h \
kiss_fft.h kiss_fftr.h laplace.h mdct.h mfrngcod.h mathops.h modes.h \
os_support.h pgain_table.h pitch.h psy.h \
--- a/libcelt/bitrdec.c
+++ /dev/null
@@ -1,28 +1,0 @@
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
-
-#include "bitree.h"
-
-int ec_bitree_find_and_update(unsigned *_this,int _sz,int _split,
- unsigned _freq,unsigned *_fl,int _val){- int base;
- int test;
- int fl;
- base=-1;
- fl=0;
- while(_split>0){- test=base+_split;
- if(test<_sz){- if(_freq>=_this[test]){- _freq-=_this[test];
- fl+=_this[test];
- base=test;
- }
- else _this[test]+=_val;
- }
- _split>>=1;
- }
- *_fl=fl;
- return base+1;
-}
--- a/libcelt/bitrdec.h
+++ /dev/null
@@ -1,22 +1,0 @@
-#if !defined(_bitrenc_H)
-# define _bitredec_H (1)
-# include "bitree.h"
-
-/*Decoder-specific functions for Binary Indexed Trees.
- See bitree.h for more detailed documentation.*/
-
-/*Gets the symbol that corresponds with a given frequency.
- This is an omnibus function that also computes the cumulative frequency of
- the symbols before the one returned, and updates the count of that symbol by
- the given amount.
- _sz: The size of the table.
- _split: The largest power of two less than OR EQUAL to the table size.
- _freq: A frequency in the range of one of the symbols in the alphabet.
- _fl: Returns the sum of the frequencies of the symbols less than that of
- the returned symbol.
- _val: The amount to add to returned symbol's frequency.
- Return: The smallest symbol whose cumulative frequency is greater than freq.*/
-int ec_bitree_find_and_update(unsigned *_this,int _sz,int _split,
- unsigned _freq,unsigned *_fl,int _val);
-
-#endif
--- a/libcelt/bitree.c
+++ /dev/null
@@ -1,72 +1,0 @@
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
-
-#include "bitree.h"
-
-void ec_bitree_to_counts(unsigned *_this,int _sz,int _split){- int p;
- int q;
- int s;
- for(p=_split;p>1;p=q){- q=p>>1;
- for(s=p-1;s<_sz;s+=p)_this[s]-=_this[s-q];
- }
-}
-
-void ec_bitree_from_counts(unsigned *_this,int _sz){- int p;
- int q;
- int s;
- for(q=1,p=2;p<=_sz;q=p,p=q<<1){- for(s=p-1;s<_sz;s+=p)_this[s]+=_this[s-q];
- }
-}
-
-unsigned ec_bitree_get_cumul(const unsigned *_this,int _sym){- unsigned ret;
- ret=0;
- while(_sym>0){- ret+=_this[_sym-1];
- _sym&=_sym-1;
- }
- return ret;
-}
-
-unsigned ec_bitree_get_freq(const unsigned *_this,int _sym){- unsigned ret;
- int p;
- ret=_this[_sym];
- p=_sym&_sym+1;
- while(_sym!=p){- ret-=_this[_sym-1];
- _sym&=_sym-1;
- }
- return ret;
-}
-
-#if 0
-/*Fenwick's approach to re-scaling the counts.
- This tests to be twice as slow or more than the one below, even with inline
- functions enabled, and without loop vectorization (which would make Moffat's
- approach even faster).*/
-void ec_bitree_halve(unsigned *_this,int _sz,int _split){- int i;
- for(i=_sz;i-->0;){- ec_bitree_update(_this,_sz,i,-(int)(ec_bitree_get_freq(_this,i)>>1));
- }
-}
-#else
-/*Fenwick mentions that this approach is also possible, and this is what
- Moffat uses.
- Simply convert the tree into a simple array of counts, perform the halving,
- and then convert it back.*/
-void ec_bitree_halve(unsigned *_this,int _sz,int _split){- int i;
- ec_bitree_to_counts(_this,_sz,_split);
- /*LOOP VECTORIZES.*/
- for(i=0;i<_sz;i++)_this[i]-=_this[i]>>1;
- ec_bitree_from_counts(_this,_sz);
-}
-#endif
-
--- a/libcelt/bitree.h
+++ /dev/null
@@ -1,84 +1,0 @@
-/*Implements Binary Indexed Trees for cumulative probability tables, based
- upon a combination of the techniques described in \cite{Fen93,Fen95,Mof99}.- This is a really, amazingly elegant data structure, that maintains
- cumulative frequency tables in logarithmic time, using exactly the same
- space as an ordinary frequency table.
- In addition, the non-cumulative frequency can be retrieved in constant
- amortized time (under 2 memory references per symbol on average).
-
- We are dealing primarily with relatively small alphabets and are not sorting
- symbols by frequency, and so we adopt Fenwick's tree organization strategy.
- It's complexity has better constant factors, and although it is logarithmic
- in n (the alphabet size) instead of s (the index of the symbol), the latter
- is not expected to be appreciably smaller.
- We modify it however, to remove the special cases surrounding the element 0,
- which greatly streamlines the code.
- Our scheme has the added benefit that for alphabet sizes that are a power of
- 2, the last element of the array is the total cumulative frequency count.
-
- We choose Moffat's approach to halving the entire frequency table, which is
- over twice as fast in practice as that suggested by Fenwick, even though
- they have the same number of memory accesses.
- We also adapt Moffat's suggestion for an omnibus decode function that updates
- the count of the symbol being decoded while it is searching for it.
- We also have it retain and return the cumulative frequency count needed to
- update the arithmetic decoder.
-
- See bitrenc.h and bitrdec.h for encoding- and decoding-specific functions.
-
- @TECHREPORT{Fen93,- author ="Peter Fenwick",
- title ="A new data structure for cumulative probability tables",
- institution="The University of Auckland, Department of Computer Science",
- year =1993,
- number =88,
- month =May,
- URL ="http://www.cs.auckland.ac.nz/~peter-f/FTPfiles/TechRep88.ps"
- }
- @TECHREPORT{Fen95,- author ="Peter Fenwick",
- title ="A new data structure for cumulative probability tables: an
- improved frequency to symbol algorithm",
- institution="The University of Auckland, Department of Computer Science",
- year =1995,
- number =110,
- month =Feb,
- URL ="http://www.cs.auckland.ac.nz/~peter-f/FTPfiles/TechRep110.ps"
- }
- @ARTICLE{Mof99,- author ="Alistair Moffat",
- title ="An improved data structure for cumulative probability tables",
- journal ="Software Practice and Experience",
- volume =29,
- number =7,
- pages ="647--659",
- year =1999
- }*/
-#if !defined(_bitree_H)
-# define _bitree_H (1)
-
-/*Converts an array of frequency counts to our cumulative tree representation.
- _sz: The size of the table.*/
-void ec_bitree_from_counts(unsigned *_this,int _sz);
-
-/*Converts our cumulative tree representation to an array of frequency counts.
- _sz: The size of the table.
- _split: The largest power of two less than OR EQUAL to the table size.*/
-void ec_bitree_to_counts(unsigned *_this,int _sz,int _split);
-
-/*Gets the cumulative frequency of the symbols less than the given one.
- _sym: The symbol to obtain the cumulative frequency for.
- Return: The sum of the frequencies of the symbols less than _sym.*/
-unsigned ec_bitree_get_cumul(const unsigned *_this,int _sym);
-
-/*Gets the frequency of a single symbol.
- _sym: The symbol to obtain the frequency for.
- Return: The frequency of _sym.*/
-unsigned ec_bitree_get_freq(const unsigned *_this,int _sym);
-
-/*Halves the frequency of each symbol, rounding up.
- _sz: The size of the table.
- _split: The largest power of two less than OR EQUAL to the table size.*/
-void ec_bitree_halve(unsigned *_this,int _sz,int _split);
-
-#endif
--- a/libcelt/bitrenc.c
+++ /dev/null
@@ -1,13 +1,0 @@
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
-
-#include "bitrenc.h"
-
-void ec_bitree_update(unsigned *_this,int _sz,int _sym,int _val){- do{- _this[_sym]+=_val;
- _sym+=_sym+1&-(_sym+1);
- }
- while(_sym<_sz);
-}
--- a/libcelt/bitrenc.h
+++ /dev/null
@@ -1,14 +1,0 @@
-#if !defined(_bitrenc_H)
-# define _bitrenc_H (1)
-# include "bitree.h"
-
-/*Encoder-specific functions for Binary Indexed Trees.
- See bitree.h for more detailed documentation.*/
-
-/*Updates the frequency of a given symbol.
- _sz: The size of the table.
- _sym: The symbol to update.
- _val: The amount to add to this symbol's frequency.*/
-void ec_bitree_update(unsigned *_this,int _sz,int _sym,int _val);
-
-#endif