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