michael@0: /* Copyright (c) 2007 CSIRO
michael@0:    Copyright (c) 2007-2009 Xiph.Org Foundation
michael@0:    Written by Jean-Marc Valin */
michael@0: /*
michael@0:    Redistribution and use in source and binary forms, with or without
michael@0:    modification, are permitted provided that the following conditions
michael@0:    are met:
michael@0: 
michael@0:    - Redistributions of source code must retain the above copyright
michael@0:    notice, this list of conditions and the following disclaimer.
michael@0: 
michael@0:    - Redistributions in binary form must reproduce the above copyright
michael@0:    notice, this list of conditions and the following disclaimer in the
michael@0:    documentation and/or other materials provided with the distribution.
michael@0: 
michael@0:    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
michael@0:    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
michael@0:    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
michael@0:    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
michael@0:    OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
michael@0:    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
michael@0:    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
michael@0:    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
michael@0:    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
michael@0:    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
michael@0:    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
michael@0: */
michael@0: 
michael@0: #ifdef HAVE_CONFIG_H
michael@0: #include "config.h"
michael@0: #endif
michael@0: 
michael@0: #include "laplace.h"
michael@0: #include "mathops.h"
michael@0: 
michael@0: /* The minimum probability of an energy delta (out of 32768). */
michael@0: #define LAPLACE_LOG_MINP (0)
michael@0: #define LAPLACE_MINP (1<<LAPLACE_LOG_MINP)
michael@0: /* The minimum number of guaranteed representable energy deltas (in one
michael@0:     direction). */
michael@0: #define LAPLACE_NMIN (16)
michael@0: 
michael@0: /* When called, decay is positive and at most 11456. */
michael@0: static unsigned ec_laplace_get_freq1(unsigned fs0, int decay)
michael@0: {
michael@0:    unsigned ft;
michael@0:    ft = 32768 - LAPLACE_MINP*(2*LAPLACE_NMIN) - fs0;
michael@0:    return ft*(opus_int32)(16384-decay)>>15;
michael@0: }
michael@0: 
michael@0: void ec_laplace_encode(ec_enc *enc, int *value, unsigned fs, int decay)
michael@0: {
michael@0:    unsigned fl;
michael@0:    int val = *value;
michael@0:    fl = 0;
michael@0:    if (val)
michael@0:    {
michael@0:       int s;
michael@0:       int i;
michael@0:       s = -(val<0);
michael@0:       val = (val+s)^s;
michael@0:       fl = fs;
michael@0:       fs = ec_laplace_get_freq1(fs, decay);
michael@0:       /* Search the decaying part of the PDF.*/
michael@0:       for (i=1; fs > 0 && i < val; i++)
michael@0:       {
michael@0:          fs *= 2;
michael@0:          fl += fs+2*LAPLACE_MINP;
michael@0:          fs = (fs*(opus_int32)decay)>>15;
michael@0:       }
michael@0:       /* Everything beyond that has probability LAPLACE_MINP. */
michael@0:       if (!fs)
michael@0:       {
michael@0:          int di;
michael@0:          int ndi_max;
michael@0:          ndi_max = (32768-fl+LAPLACE_MINP-1)>>LAPLACE_LOG_MINP;
michael@0:          ndi_max = (ndi_max-s)>>1;
michael@0:          di = IMIN(val - i, ndi_max - 1);
michael@0:          fl += (2*di+1+s)*LAPLACE_MINP;
michael@0:          fs = IMIN(LAPLACE_MINP, 32768-fl);
michael@0:          *value = (i+di+s)^s;
michael@0:       }
michael@0:       else
michael@0:       {
michael@0:          fs += LAPLACE_MINP;
michael@0:          fl += fs&~s;
michael@0:       }
michael@0:       celt_assert(fl+fs<=32768);
michael@0:       celt_assert(fs>0);
michael@0:    }
michael@0:    ec_encode_bin(enc, fl, fl+fs, 15);
michael@0: }
michael@0: 
michael@0: int ec_laplace_decode(ec_dec *dec, unsigned fs, int decay)
michael@0: {
michael@0:    int val=0;
michael@0:    unsigned fl;
michael@0:    unsigned fm;
michael@0:    fm = ec_decode_bin(dec, 15);
michael@0:    fl = 0;
michael@0:    if (fm >= fs)
michael@0:    {
michael@0:       val++;
michael@0:       fl = fs;
michael@0:       fs = ec_laplace_get_freq1(fs, decay)+LAPLACE_MINP;
michael@0:       /* Search the decaying part of the PDF.*/
michael@0:       while(fs > LAPLACE_MINP && fm >= fl+2*fs)
michael@0:       {
michael@0:          fs *= 2;
michael@0:          fl += fs;
michael@0:          fs = ((fs-2*LAPLACE_MINP)*(opus_int32)decay)>>15;
michael@0:          fs += LAPLACE_MINP;
michael@0:          val++;
michael@0:       }
michael@0:       /* Everything beyond that has probability LAPLACE_MINP. */
michael@0:       if (fs <= LAPLACE_MINP)
michael@0:       {
michael@0:          int di;
michael@0:          di = (fm-fl)>>(LAPLACE_LOG_MINP+1);
michael@0:          val += di;
michael@0:          fl += 2*di*LAPLACE_MINP;
michael@0:       }
michael@0:       if (fm < fl+fs)
michael@0:          val = -val;
michael@0:       else
michael@0:          fl += fs;
michael@0:    }
michael@0:    celt_assert(fl<32768);
michael@0:    celt_assert(fs>0);
michael@0:    celt_assert(fl<=fm);
michael@0:    celt_assert(fm<IMIN(fl+fs,32768));
michael@0:    ec_dec_update(dec, fl, IMIN(fl+fs,32768), 32768);
michael@0:    return val;
michael@0: }