1885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* Copyright (c) 2007 CSIRO 2885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org Copyright (c) 2007-2009 Xiph.Org Foundation 3885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org Written by Jean-Marc Valin */ 4885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* 5885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org Redistribution and use in source and binary forms, with or without 6885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org modification, are permitted provided that the following conditions 7885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org are met: 8885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 9885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org - Redistributions of source code must retain the above copyright 10885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org notice, this list of conditions and the following disclaimer. 11885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 12885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org - Redistributions in binary form must reproduce the above copyright 13885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org notice, this list of conditions and the following disclaimer in the 14885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org documentation and/or other materials provided with the distribution. 15885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 16885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 20885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 21885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 22885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 23885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 24885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 25885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 26885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org*/ 28885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 29885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#ifdef HAVE_CONFIG_H 30885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "config.h" 31885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif 32885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 33885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "laplace.h" 34885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "mathops.h" 35885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 36885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* The minimum probability of an energy delta (out of 32768). */ 37885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#define LAPLACE_LOG_MINP (0) 38885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#define LAPLACE_MINP (1<<LAPLACE_LOG_MINP) 39885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* The minimum number of guaranteed representable energy deltas (in one 40885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org direction). */ 41885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#define LAPLACE_NMIN (16) 42885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 43885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* When called, decay is positive and at most 11456. */ 44885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgstatic unsigned ec_laplace_get_freq1(unsigned fs0, int decay) 45885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org{ 46885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org unsigned ft; 47885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ft = 32768 - LAPLACE_MINP*(2*LAPLACE_NMIN) - fs0; 48885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org return ft*(opus_int32)(16384-decay)>>15; 49885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 50885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 51885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid ec_laplace_encode(ec_enc *enc, int *value, unsigned fs, int decay) 52885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org{ 53885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org unsigned fl; 54885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int val = *value; 55885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fl = 0; 56885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if (val) 57885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org { 58885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int s; 59885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int i; 60885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org s = -(val<0); 61885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org val = (val+s)^s; 62885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fl = fs; 63885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fs = ec_laplace_get_freq1(fs, decay); 64885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /* Search the decaying part of the PDF.*/ 65885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org for (i=1; fs > 0 && i < val; i++) 66885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org { 67885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fs *= 2; 68885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fl += fs+2*LAPLACE_MINP; 69885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fs = (fs*(opus_int32)decay)>>15; 70885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 71885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /* Everything beyond that has probability LAPLACE_MINP. */ 72885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if (!fs) 73885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org { 74885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int di; 75885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int ndi_max; 76885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ndi_max = (32768-fl+LAPLACE_MINP-1)>>LAPLACE_LOG_MINP; 77885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ndi_max = (ndi_max-s)>>1; 78885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org di = IMIN(val - i, ndi_max - 1); 79885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fl += (2*di+1+s)*LAPLACE_MINP; 80885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fs = IMIN(LAPLACE_MINP, 32768-fl); 81885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org *value = (i+di+s)^s; 82885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 83885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org else 84885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org { 85885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fs += LAPLACE_MINP; 86885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fl += fs&~s; 87885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 88885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org celt_assert(fl+fs<=32768); 89885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org celt_assert(fs>0); 90885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 91885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ec_encode_bin(enc, fl, fl+fs, 15); 92885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 93885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 94885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgint ec_laplace_decode(ec_dec *dec, unsigned fs, int decay) 95885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org{ 96885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int val=0; 97885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org unsigned fl; 98885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org unsigned fm; 99885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fm = ec_decode_bin(dec, 15); 100885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fl = 0; 101885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if (fm >= fs) 102885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org { 103885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org val++; 104885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fl = fs; 105885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fs = ec_laplace_get_freq1(fs, decay)+LAPLACE_MINP; 106885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /* Search the decaying part of the PDF.*/ 107885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org while(fs > LAPLACE_MINP && fm >= fl+2*fs) 108885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org { 109885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fs *= 2; 110885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fl += fs; 111885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fs = ((fs-2*LAPLACE_MINP)*(opus_int32)decay)>>15; 112885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fs += LAPLACE_MINP; 113885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org val++; 114885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 115885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /* Everything beyond that has probability LAPLACE_MINP. */ 116885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if (fs <= LAPLACE_MINP) 117885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org { 118885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int di; 119885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org di = (fm-fl)>>(LAPLACE_LOG_MINP+1); 120885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org val += di; 121885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fl += 2*di*LAPLACE_MINP; 122885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 123885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if (fm < fl+fs) 124885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org val = -val; 125885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org else 126885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fl += fs; 127885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 128885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org celt_assert(fl<32768); 129885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org celt_assert(fs>0); 130885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org celt_assert(fl<=fm); 131885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org celt_assert(fm<IMIN(fl+fs,32768)); 132885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ec_dec_update(dec, fl, IMIN(fl+fs,32768), 32768); 133885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org return val; 134885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 135