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