12bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian/* Copyright (c) 2011 Xiph.Org Foundation 22bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian Written by Gregory Maxwell */ 32bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian/* 42bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian Redistribution and use in source and binary forms, with or without 52bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian modification, are permitted provided that the following conditions 62bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian are met: 72bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian 82bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian - Redistributions of source code must retain the above copyright 92bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian notice, this list of conditions and the following disclaimer. 102bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian 112bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian - Redistributions in binary form must reproduce the above copyright 122bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian notice, this list of conditions and the following disclaimer in the 132bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian documentation and/or other materials provided with the distribution. 142bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian 152bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 162bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 172bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 182bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 192bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 202bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 212bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 222bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 232bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 242bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 252bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 262bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian*/ 272bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian 282bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanianstatic OPUS_INLINE void deb2_impl(unsigned char *_t,unsigned char **_p,int _k,int _x,int _y) 292bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian{ 302bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian int i; 312bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian if(_x>2){ 322bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian if(_y<3)for(i=0;i<_y;i++)*(--*_p)=_t[i+1]; 332bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian }else{ 342bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian _t[_x]=_t[_x-_y]; 352bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian deb2_impl(_t,_p,_k,_x+1,_y); 362bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian for(i=_t[_x-_y]+1;i<_k;i++){ 372bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian _t[_x]=i; 382bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian deb2_impl(_t,_p,_k,_x+1,_x); 392bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian } 402bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian } 412bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian} 422bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian 432bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian/*Generates a De Bruijn sequence (k,2) with length k^2*/ 442bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanianstatic OPUS_INLINE void debruijn2(int _k, unsigned char *_res) 452bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian{ 462bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian unsigned char *p; 472bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian unsigned char *t; 482bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian t=malloc(sizeof(unsigned char)*_k*2); 492bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian memset(t,0,sizeof(unsigned char)*_k*2); 502bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian p=&_res[_k*_k]; 512bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian deb2_impl(t,&p,_k,1,1); 522bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian free(t); 532bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian} 542bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian 552bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian/*MWC RNG of George Marsaglia*/ 562bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanianstatic opus_uint32 Rz, Rw; 572bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanianstatic OPUS_INLINE opus_uint32 fast_rand(void) 582bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian{ 592bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian Rz=36969*(Rz&65535)+(Rz>>16); 602bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian Rw=18000*(Rw&65535)+(Rw>>16); 612bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian return (Rz<<16)+Rw; 622bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian} 632bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanianstatic opus_uint32 iseed; 642bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian 652bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian#ifdef __GNUC__ 662bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian__attribute__((noreturn)) 672bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian#endif 682bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanianstatic OPUS_INLINE void _test_failed(const char *file, int line) 692bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian{ 702bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fprintf(stderr,"\n ***************************************************\n"); 712bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fprintf(stderr," *** A fatal error was detected. ***\n"); 722bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fprintf(stderr," ***************************************************\n"); 732bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fprintf(stderr,"Please report this failure and include\n"); 742bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fprintf(stderr,"'make check SEED=%u fails %s at line %d for %s'\n",iseed,file,line,opus_get_version_string()); 752bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian fprintf(stderr,"and any relevant details about your system.\n\n"); 762bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian abort(); 772bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian} 782bd8b54017b5320bc0c1df9bf86f4cdc9f8db242Vignesh Venkatasubramanian#define test_failed() _test_failed(__FILE__, __LINE__); 79