Correct many whitespace errors under libcelt/ and remove
[opus.git] / libcelt / laplace.c
index 087c05c..43c6229 100644 (file)
@@ -1,21 +1,18 @@
-/* (C) 2007 Jean-Marc Valin, CSIRO
-*/
+/* Copyright (c) 2007 CSIRO
+   Copyright (c) 2007-2009 Xiph.Org Foundation
+   Written by Jean-Marc Valin */
 /*
    Redistribution and use in source and binary forms, with or without
    modification, are permitted provided that the following conditions
    are met:
-   
+
    - Redistributions of source code must retain the above copyright
    notice, this list of conditions and the following disclaimer.
-   
+
    - Redistributions in binary form must reproduce the above copyright
    notice, this list of conditions and the following disclaimer in the
    documentation and/or other materials provided with the distribution.
-   
-   - Neither the name of the Xiph.org Foundation nor the names of its
-   contributors may be used to endorse or promote products derived from
-   this software without specific prior written permission.
-   
+
    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 #include "config.h"
 #endif
 
-#include "entenc.h"
-#include "entdec.h"
+#include "laplace.h"
+#include "mathops.h"
 
-static int ec_laplace_get_total(int decay)
+/* The minimum probability of an energy delta (out of 32768). */
+#define LAPLACE_LOG_MINP (0)
+#define LAPLACE_MINP (1<<LAPLACE_LOG_MINP)
+/* The minimum number of guaranteed representable energy deltas (in one
+    direction). */
+#define LAPLACE_NMIN (16)
+
+static int ec_laplace_get_freq1(int fs0, int decay)
 {
-   return (1<<30)/((1<<14) - decay) - (1<<15) + 1;
+   opus_int32 ft;
+   ft = 32768 - LAPLACE_MINP*(2*LAPLACE_NMIN) - fs0;
+   return ft*(16384-decay)>>15;
 }
 
-void ec_laplace_encode(ec_enc *enc, int value, int decay)
+void ec_laplace_encode(ec_enc *enc, int *value, int fs, int decay)
 {
-   int i, fl, fs, ft;
-   int s = 0;
-   if (value < 0)
-   {
-      s = 1;
-      value = -value;
-   }
-   ft = ec_laplace_get_total(decay);
-   fl = -(1<<15);
-   fs = 1<<15;
-   for (i=0;i<value;i++)
+   unsigned fl;
+   int val = *value;
+   fl = 0;
+   if (val)
    {
-      int tmp_l, tmp_s;
-      tmp_l = fl;
-      tmp_s = fs;
-      fl += fs*2;
-      fs = (fs*decay)>>14;
-      if (fs == 0)
+      int s;
+      int i;
+      s = -(val<0);
+      val = val+s^s;
+      fl = fs;
+      fs = ec_laplace_get_freq1(fs, decay);
+      /* Search the decaying part of the PDF.*/
+      for (i=1; fs > 0 && i < val; i++)
+      {
+         fs *= 2;
+         fl += fs+2*LAPLACE_MINP;
+         fs = (fs*(opus_int32)decay)>>15;
+      }
+      /* Everything beyond that has probability LAPLACE_MINP. */
+      if (fs <= 0)
       {
-         fs = tmp_s;
-         fl = tmp_l;
-         break;
+         int di;
+         int ndi_max;
+         ndi_max = (32768-fl+LAPLACE_MINP-1)>>LAPLACE_LOG_MINP;
+         ndi_max = (ndi_max-s)>>1;
+         di = IMIN(val - i, ndi_max - 1);
+         fl += (2*di+1+s)*LAPLACE_MINP;
+         fs = IMIN(LAPLACE_MINP, 32768-fl);
+         *value = i+di+s^s;
       }
+      else
+      {
+         fs += LAPLACE_MINP;
+         fl += fs&~s;
+      }
+      celt_assert(fl+fs<=32768);
+      celt_assert(fs>0);
    }
-   if (fl < 0)
-      fl = 0;
-   if (s)
-      fl += fs;
-   /*printf ("enc: %d %d %d\n", fl, fs, ft);*/
-   ec_encode(enc, fl, fl+fs, ft);
+   ec_encode_bin(enc, fl, fl+fs, 15);
 }
 
-int ec_laplace_decode(ec_dec *dec, int decay)
+
+int ec_laplace_decode(ec_dec *dec, int fs, int decay)
 {
    int val=0;
-   int fl, fh, fs, ft, fm;
-   ft = ec_laplace_get_total(decay);
-   
-   fm = ec_decode(dec, ft);
-   /*printf ("fm: %d/%d\n", fm, ft);*/
+   unsigned fl;
+   int fm;
+   fm = ec_decode_bin(dec, 15);
    fl = 0;
-   fs = 1<<15;
-   fh = fs;
-   while (fm >= fh && fs != 0)
+   if (fm >= fs)
    {
-      fl = fh;
-      fs = (fs*decay)>>14;
-      fh += fs*2;
       val++;
-   }
-   if (fl>0)
-   {
-      if (fm >= fl+fs)
+      fl = fs;
+      fs = ec_laplace_get_freq1(fs, decay)+LAPLACE_MINP;
+      /* Search the decaying part of the PDF.*/
+      while(fs > LAPLACE_MINP && fm >= fl+2*fs)
       {
-         val = -val;
+         fs *= 2;
          fl += fs;
-      } else {
-         fh -= fs;
+         fs = ((fs-2*LAPLACE_MINP)*(opus_int32)decay)>>15;
+         fs += LAPLACE_MINP;
+         val++;
+      }
+      /* Everything beyond that has probability LAPLACE_MINP. */
+      if (fs <= LAPLACE_MINP)
+      {
+         int di;
+         di = (fm-fl)>>(LAPLACE_LOG_MINP+1);
+         val += di;
+         fl += 2*di*LAPLACE_MINP;
       }
+      if (fm < fl+fs)
+         val = -val;
+      else
+         fl += fs;
    }
-   /* Preventing an infinite loop in case something screws up in the decoding */
-   if (fl==fh)
-      fl--;
-   ec_dec_update(dec, fl, fh, ft);
+   celt_assert(fl<32768);
+   celt_assert(fs>0);
+   celt_assert(fl<=fm);
+   celt_assert(fm<IMIN(fl+fs,32768));
+   ec_dec_update(dec, fl, IMIN(fl+fs,32768), 32768);
    return val;
 }
-
-#if 0
-#include <stdio.h>
-int main()
-{
-   int val;
-   ec_enc enc;
-   ec_dec dec;
-   ec_byte_buffer buf;
-   
-   ec_byte_writeinit(&buf);
-   ec_enc_init(&enc,&buf);
-   
-   ec_laplace_encode(&enc, 9, 10000);
-   ec_laplace_encode(&enc, -5, 12000);
-   ec_laplace_encode(&enc, -2, 9000);
-   ec_laplace_encode(&enc, 20, 15000);
-   ec_laplace_encode(&enc, 2, 900);
-   
-   ec_enc_done(&enc);
-
-   ec_byte_readinit(&buf,ec_byte_get_buffer(&buf),ec_byte_bytes(&buf));
-   ec_dec_init(&dec,&buf);
-
-   val = ec_laplace_decode(&dec, 10000);
-   printf ("dec: %d\n", val);
-   val = ec_laplace_decode(&dec, 12000);
-   printf ("dec: %d\n", val);
-   val = ec_laplace_decode(&dec, 9000);
-   printf ("dec: %d\n", val);
-   val = ec_laplace_decode(&dec, 15000);
-   printf ("dec: %d\n", val);
-   val = ec_laplace_decode(&dec, 900);
-   printf ("dec: %d\n", val);
-   
-   
-   ec_byte_writeclear(&buf);
-   return 0;
-}
-#endif
-