1885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/*********************************************************************** 2885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgCopyright (c) 2006-2011, Skype Limited. All rights reserved. 3885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgRedistribution and use in source and binary forms, with or without 4885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgmodification, are permitted provided that the following conditions 5885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgare met: 6885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org- Redistributions of source code must retain the above copyright notice, 7885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgthis list of conditions and the following disclaimer. 8885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org- Redistributions in binary form must reproduce the above copyright 9885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgnotice, this list of conditions and the following disclaimer in the 10885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgdocumentation and/or other materials provided with the distribution. 11e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org- Neither the name of Internet Society, IETF or IETF Trust, nor the 12885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgnames of specific contributors, may be used to endorse or promote 13885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgproducts derived from this software without specific prior written 14885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgpermission. 15e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.orgTHIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 16885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgAND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgIMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 19885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgLIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 20885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgCONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 21885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgSUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 22885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgINTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 23885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgCONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 24885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 25885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgPOSSIBILITY OF SUCH DAMAGE. 26885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org***********************************************************************/ 27885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 28885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#ifdef HAVE_CONFIG_H 29885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "config.h" 30885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif 31885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 32885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* Insertion sort (fast for already almost sorted arrays): */ 33885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* Best case: O(n) for an already sorted array */ 34885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* Worst case: O(n^2) for an inversely sorted array */ 35885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* */ 36885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* Shell short: http://en.wikipedia.org/wiki/Shell_sort */ 37885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 38885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "SigProc_FIX.h" 39885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 40885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid silk_insertion_sort_increasing( 41885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_int32 *a, /* I/O Unsorted / Sorted vector */ 42885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_int *idx, /* O Index vector for the sorted elements */ 43885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org const opus_int L, /* I Vector length */ 44885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org const opus_int K /* I Number of correctly sorted positions */ 45885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org) 46885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org{ 47885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_int32 value; 48885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_int i, j; 49885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 50885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /* Safety checks */ 51885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org silk_assert( K > 0 ); 52885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org silk_assert( L > 0 ); 53885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org silk_assert( L >= K ); 54885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 55885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /* Write start indices in index vector */ 56885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org for( i = 0; i < K; i++ ) { 57885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org idx[ i ] = i; 58885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 59885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 60885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /* Sort vector elements by value, increasing order */ 61885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org for( i = 1; i < K; i++ ) { 62885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org value = a[ i ]; 63885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org for( j = i - 1; ( j >= 0 ) && ( value < a[ j ] ); j-- ) { 64885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org a[ j + 1 ] = a[ j ]; /* Shift value */ 65885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org idx[ j + 1 ] = idx[ j ]; /* Shift index */ 66885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 67885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org a[ j + 1 ] = value; /* Write value */ 68885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org idx[ j + 1 ] = i; /* Write index */ 69885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 70885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 71885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /* If less than L values are asked for, check the remaining values, */ 72885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /* but only spend CPU to ensure that the K first values are correct */ 73885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org for( i = K; i < L; i++ ) { 74885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org value = a[ i ]; 75885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if( value < a[ K - 1 ] ) { 76885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org for( j = K - 2; ( j >= 0 ) && ( value < a[ j ] ); j-- ) { 77885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org a[ j + 1 ] = a[ j ]; /* Shift value */ 78885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org idx[ j + 1 ] = idx[ j ]; /* Shift index */ 79885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 80885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org a[ j + 1 ] = value; /* Write value */ 81885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org idx[ j + 1 ] = i; /* Write index */ 82885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 83885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 84885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 85885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 86885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#ifdef FIXED_POINT 87885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* This function is only used by the fixed-point build */ 88885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid silk_insertion_sort_decreasing_int16( 89885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_int16 *a, /* I/O Unsorted / Sorted vector */ 90885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_int *idx, /* O Index vector for the sorted elements */ 91885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org const opus_int L, /* I Vector length */ 92885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org const opus_int K /* I Number of correctly sorted positions */ 93885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org) 94885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org{ 95885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_int i, j; 96885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_int value; 97885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 98885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /* Safety checks */ 99885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org silk_assert( K > 0 ); 100885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org silk_assert( L > 0 ); 101885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org silk_assert( L >= K ); 102885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 103885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /* Write start indices in index vector */ 104885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org for( i = 0; i < K; i++ ) { 105885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org idx[ i ] = i; 106885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 107885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 108885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /* Sort vector elements by value, decreasing order */ 109885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org for( i = 1; i < K; i++ ) { 110885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org value = a[ i ]; 111885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org for( j = i - 1; ( j >= 0 ) && ( value > a[ j ] ); j-- ) { 112885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org a[ j + 1 ] = a[ j ]; /* Shift value */ 113885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org idx[ j + 1 ] = idx[ j ]; /* Shift index */ 114885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 115885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org a[ j + 1 ] = value; /* Write value */ 116885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org idx[ j + 1 ] = i; /* Write index */ 117885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 118885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 119885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /* If less than L values are asked for, check the remaining values, */ 120885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /* but only spend CPU to ensure that the K first values are correct */ 121885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org for( i = K; i < L; i++ ) { 122885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org value = a[ i ]; 123885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if( value > a[ K - 1 ] ) { 124885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org for( j = K - 2; ( j >= 0 ) && ( value > a[ j ] ); j-- ) { 125885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org a[ j + 1 ] = a[ j ]; /* Shift value */ 126885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org idx[ j + 1 ] = idx[ j ]; /* Shift index */ 127885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 128885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org a[ j + 1 ] = value; /* Write value */ 129885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org idx[ j + 1 ] = i; /* Write index */ 130885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 131885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 132885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 133885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif 134885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 135885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid silk_insertion_sort_increasing_all_values_int16( 136885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_int16 *a, /* I/O Unsorted / Sorted vector */ 137885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org const opus_int L /* I Vector length */ 138885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org) 139885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org{ 140885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_int value; 141885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_int i, j; 142885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 143885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /* Safety checks */ 144885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org silk_assert( L > 0 ); 145885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 146885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /* Sort vector elements by value, increasing order */ 147885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org for( i = 1; i < L; i++ ) { 148885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org value = a[ i ]; 149885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org for( j = i - 1; ( j >= 0 ) && ( value < a[ j ] ); j-- ) { 150885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org a[ j + 1 ] = a[ j ]; /* Shift value */ 151885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 152885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org a[ j + 1 ] = value; /* Write value */ 153885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 154885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 155