12bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian/* Copyright (c) 2007 CSIRO 22bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian Copyright (c) 2007-2009 Xiph.Org Foundation 32bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian Written by Jean-Marc Valin */ 42bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian/* 52bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian Redistribution and use in source and binary forms, with or without 62bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian modification, are permitted provided that the following conditions 72bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian are met: 82bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian 92bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian - Redistributions of source code must retain the above copyright 102bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian notice, this list of conditions and the following disclaimer. 112bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian 122bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian - Redistributions in binary form must reproduce the above copyright 132bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian notice, this list of conditions and the following disclaimer in the 142bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian documentation and/or other materials provided with the distribution. 152bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian 162bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 202bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 212bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 222bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 232bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 242bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 252bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 262bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian*/ 282bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian 292bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian#ifdef HAVE_CONFIG_H 302bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian#include "config.h" 312bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian#endif 322bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian 332bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian#include "laplace.h" 342bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian#include "mathops.h" 352bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian 362bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian/* The minimum probability of an energy delta (out of 32768). */ 372bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian#define LAPLACE_LOG_MINP (0) 382bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian#define LAPLACE_MINP (1<<LAPLACE_LOG_MINP) 392bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian/* The minimum number of guaranteed representable energy deltas (in one 402bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian direction). */ 412bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian#define LAPLACE_NMIN (16) 422bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian 432bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian/* When called, decay is positive and at most 11456. */ 442bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanianstatic unsigned ec_laplace_get_freq1(unsigned fs0, int decay) 452bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian{ 462bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian unsigned ft; 472bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian ft = 32768 - LAPLACE_MINP*(2*LAPLACE_NMIN) - fs0; 482bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian return ft*(opus_int32)(16384-decay)>>15; 492bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian} 502bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian 512bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanianvoid ec_laplace_encode(ec_enc *enc, int *value, unsigned fs, int decay) 522bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian{ 532bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian unsigned fl; 542bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian int val = *value; 552bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fl = 0; 562bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian if (val) 572bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian { 582bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian int s; 592bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian int i; 602bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian s = -(val<0); 612bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian val = (val+s)^s; 622bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fl = fs; 632bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fs = ec_laplace_get_freq1(fs, decay); 642bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian /* Search the decaying part of the PDF.*/ 652bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian for (i=1; fs > 0 && i < val; i++) 662bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian { 672bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fs *= 2; 682bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fl += fs+2*LAPLACE_MINP; 692bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fs = (fs*(opus_int32)decay)>>15; 702bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian } 712bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian /* Everything beyond that has probability LAPLACE_MINP. */ 722bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian if (!fs) 732bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian { 742bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian int di; 752bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian int ndi_max; 762bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian ndi_max = (32768-fl+LAPLACE_MINP-1)>>LAPLACE_LOG_MINP; 772bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian ndi_max = (ndi_max-s)>>1; 782bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian di = IMIN(val - i, ndi_max - 1); 792bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fl += (2*di+1+s)*LAPLACE_MINP; 802bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fs = IMIN(LAPLACE_MINP, 32768-fl); 812bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian *value = (i+di+s)^s; 822bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian } 832bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian else 842bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian { 852bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fs += LAPLACE_MINP; 862bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fl += fs&~s; 872bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian } 882bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian celt_assert(fl+fs<=32768); 892bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian celt_assert(fs>0); 902bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian } 912bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian ec_encode_bin(enc, fl, fl+fs, 15); 922bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian} 932bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian 942bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanianint ec_laplace_decode(ec_dec *dec, unsigned fs, int decay) 952bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian{ 962bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian int val=0; 972bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian unsigned fl; 982bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian unsigned fm; 992bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fm = ec_decode_bin(dec, 15); 1002bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fl = 0; 1012bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian if (fm >= fs) 1022bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian { 1032bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian val++; 1042bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fl = fs; 1052bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fs = ec_laplace_get_freq1(fs, decay)+LAPLACE_MINP; 1062bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian /* Search the decaying part of the PDF.*/ 1072bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian while(fs > LAPLACE_MINP && fm >= fl+2*fs) 1082bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian { 1092bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fs *= 2; 1102bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fl += fs; 1112bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fs = ((fs-2*LAPLACE_MINP)*(opus_int32)decay)>>15; 1122bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fs += LAPLACE_MINP; 1132bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian val++; 1142bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian } 1152bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian /* Everything beyond that has probability LAPLACE_MINP. */ 1162bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian if (fs <= LAPLACE_MINP) 1172bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian { 1182bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian int di; 1192bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian di = (fm-fl)>>(LAPLACE_LOG_MINP+1); 1202bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian val += di; 1212bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fl += 2*di*LAPLACE_MINP; 1222bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian } 1232bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian if (fm < fl+fs) 1242bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian val = -val; 1252bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian else 1262bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fl += fs; 1272bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian } 1282bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian celt_assert(fl<32768); 1292bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian celt_assert(fs>0); 1302bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian celt_assert(fl<=fm); 1312bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian celt_assert(fm<IMIN(fl+fs,32768)); 1322bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian ec_dec_update(dec, fl, IMIN(fl+fs,32768), 32768); 1332bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian return val; 1342bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian} 135