Hadn't realised the bitr* stuff wasn't needed.
authorJean-Marc Valin <jean-marc.valin@usherbrooke.ca>
Sun, 2 Mar 2008 17:11:49 +0000 (04:11 +1100)
committerJean-Marc Valin <jean-marc.valin@usherbrooke.ca>
Sun, 2 Mar 2008 17:11:49 +0000 (04:11 +1100)
libcelt/Makefile.am
libcelt/bitrdec.c [deleted file]
libcelt/bitrdec.h [deleted file]
libcelt/bitree.c [deleted file]
libcelt/bitree.h [deleted file]
libcelt/bitrenc.c [deleted file]
libcelt/bitrenc.h [deleted file]

index c96975e..795c8fb 100644 (file)
@@ -14,7 +14,7 @@ noinst_SCRIPTS = match-test.sh
 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_SOURCES = bands.c bitrdec.c bitree.c bitrenc.c celt.c cwrs.c \
 
 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 \
diff --git a/libcelt/bitrdec.c b/libcelt/bitrdec.c
deleted file mode 100644 (file)
index 9db568a..0000000
+++ /dev/null
@@ -1,28 +0,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;
-}
diff --git a/libcelt/bitrdec.h b/libcelt/bitrdec.h
deleted file mode 100644 (file)
index 375ea96..0000000
+++ /dev/null
@@ -1,22 +0,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
diff --git a/libcelt/bitree.c b/libcelt/bitree.c
deleted file mode 100644 (file)
index 9052d50..0000000
+++ /dev/null
@@ -1,72 +0,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
-
diff --git a/libcelt/bitree.h b/libcelt/bitree.h
deleted file mode 100644 (file)
index 1eda404..0000000
+++ /dev/null
@@ -1,84 +0,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
diff --git a/libcelt/bitrenc.c b/libcelt/bitrenc.c
deleted file mode 100644 (file)
index e0ca115..0000000
+++ /dev/null
@@ -1,13 +0,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);
-}
diff --git a/libcelt/bitrenc.h b/libcelt/bitrenc.h
deleted file mode 100644 (file)
index 77d0b5d..0000000
+++ /dev/null
@@ -1,14 +0,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