cannam@154: /*********************************************************************** cannam@154: Copyright (c) 2006-2011, Skype Limited. All rights reserved. cannam@154: Redistribution and use in source and binary forms, with or without cannam@154: modification, are permitted provided that the following conditions cannam@154: are met: cannam@154: - Redistributions of source code must retain the above copyright notice, cannam@154: this list of conditions and the following disclaimer. cannam@154: - Redistributions in binary form must reproduce the above copyright cannam@154: notice, this list of conditions and the following disclaimer in the cannam@154: documentation and/or other materials provided with the distribution. cannam@154: - Neither the name of Internet Society, IETF or IETF Trust, nor the cannam@154: names of specific contributors, may be used to endorse or promote cannam@154: products derived from this software without specific prior written cannam@154: permission. cannam@154: THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" cannam@154: AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE cannam@154: IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE cannam@154: ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE cannam@154: LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR cannam@154: CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF cannam@154: SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS cannam@154: INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN cannam@154: CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) cannam@154: ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE cannam@154: POSSIBILITY OF SUCH DAMAGE. cannam@154: ***********************************************************************/ cannam@154: cannam@154: #ifdef HAVE_CONFIG_H cannam@154: #include "config.h" cannam@154: #endif cannam@154: cannam@154: /* Insertion sort (fast for already almost sorted arrays): */ cannam@154: /* Best case: O(n) for an already sorted array */ cannam@154: /* Worst case: O(n^2) for an inversely sorted array */ cannam@154: /* */ cannam@154: /* Shell short: https://en.wikipedia.org/wiki/Shell_sort */ cannam@154: cannam@154: #include "SigProc_FIX.h" cannam@154: cannam@154: void silk_insertion_sort_increasing( cannam@154: opus_int32 *a, /* I/O Unsorted / Sorted vector */ cannam@154: opus_int *idx, /* O Index vector for the sorted elements */ cannam@154: const opus_int L, /* I Vector length */ cannam@154: const opus_int K /* I Number of correctly sorted positions */ cannam@154: ) cannam@154: { cannam@154: opus_int32 value; cannam@154: opus_int i, j; cannam@154: cannam@154: /* Safety checks */ cannam@154: celt_assert( K > 0 ); cannam@154: celt_assert( L > 0 ); cannam@154: celt_assert( L >= K ); cannam@154: cannam@154: /* Write start indices in index vector */ cannam@154: for( i = 0; i < K; i++ ) { cannam@154: idx[ i ] = i; cannam@154: } cannam@154: cannam@154: /* Sort vector elements by value, increasing order */ cannam@154: for( i = 1; i < K; i++ ) { cannam@154: value = a[ i ]; cannam@154: for( j = i - 1; ( j >= 0 ) && ( value < a[ j ] ); j-- ) { cannam@154: a[ j + 1 ] = a[ j ]; /* Shift value */ cannam@154: idx[ j + 1 ] = idx[ j ]; /* Shift index */ cannam@154: } cannam@154: a[ j + 1 ] = value; /* Write value */ cannam@154: idx[ j + 1 ] = i; /* Write index */ cannam@154: } cannam@154: cannam@154: /* If less than L values are asked for, check the remaining values, */ cannam@154: /* but only spend CPU to ensure that the K first values are correct */ cannam@154: for( i = K; i < L; i++ ) { cannam@154: value = a[ i ]; cannam@154: if( value < a[ K - 1 ] ) { cannam@154: for( j = K - 2; ( j >= 0 ) && ( value < a[ j ] ); j-- ) { cannam@154: a[ j + 1 ] = a[ j ]; /* Shift value */ cannam@154: idx[ j + 1 ] = idx[ j ]; /* Shift index */ cannam@154: } cannam@154: a[ j + 1 ] = value; /* Write value */ cannam@154: idx[ j + 1 ] = i; /* Write index */ cannam@154: } cannam@154: } cannam@154: } cannam@154: cannam@154: #ifdef FIXED_POINT cannam@154: /* This function is only used by the fixed-point build */ cannam@154: void silk_insertion_sort_decreasing_int16( cannam@154: opus_int16 *a, /* I/O Unsorted / Sorted vector */ cannam@154: opus_int *idx, /* O Index vector for the sorted elements */ cannam@154: const opus_int L, /* I Vector length */ cannam@154: const opus_int K /* I Number of correctly sorted positions */ cannam@154: ) cannam@154: { cannam@154: opus_int i, j; cannam@154: opus_int value; cannam@154: cannam@154: /* Safety checks */ cannam@154: celt_assert( K > 0 ); cannam@154: celt_assert( L > 0 ); cannam@154: celt_assert( L >= K ); cannam@154: cannam@154: /* Write start indices in index vector */ cannam@154: for( i = 0; i < K; i++ ) { cannam@154: idx[ i ] = i; cannam@154: } cannam@154: cannam@154: /* Sort vector elements by value, decreasing order */ cannam@154: for( i = 1; i < K; i++ ) { cannam@154: value = a[ i ]; cannam@154: for( j = i - 1; ( j >= 0 ) && ( value > a[ j ] ); j-- ) { cannam@154: a[ j + 1 ] = a[ j ]; /* Shift value */ cannam@154: idx[ j + 1 ] = idx[ j ]; /* Shift index */ cannam@154: } cannam@154: a[ j + 1 ] = value; /* Write value */ cannam@154: idx[ j + 1 ] = i; /* Write index */ cannam@154: } cannam@154: cannam@154: /* If less than L values are asked for, check the remaining values, */ cannam@154: /* but only spend CPU to ensure that the K first values are correct */ cannam@154: for( i = K; i < L; i++ ) { cannam@154: value = a[ i ]; cannam@154: if( value > a[ K - 1 ] ) { cannam@154: for( j = K - 2; ( j >= 0 ) && ( value > a[ j ] ); j-- ) { cannam@154: a[ j + 1 ] = a[ j ]; /* Shift value */ cannam@154: idx[ j + 1 ] = idx[ j ]; /* Shift index */ cannam@154: } cannam@154: a[ j + 1 ] = value; /* Write value */ cannam@154: idx[ j + 1 ] = i; /* Write index */ cannam@154: } cannam@154: } cannam@154: } cannam@154: #endif cannam@154: cannam@154: void silk_insertion_sort_increasing_all_values_int16( cannam@154: opus_int16 *a, /* I/O Unsorted / Sorted vector */ cannam@154: const opus_int L /* I Vector length */ cannam@154: ) cannam@154: { cannam@154: opus_int value; cannam@154: opus_int i, j; cannam@154: cannam@154: /* Safety checks */ cannam@154: celt_assert( L > 0 ); cannam@154: cannam@154: /* Sort vector elements by value, increasing order */ cannam@154: for( i = 1; i < L; i++ ) { cannam@154: value = a[ i ]; cannam@154: for( j = i - 1; ( j >= 0 ) && ( value < a[ j ] ); j-- ) { cannam@154: a[ j + 1 ] = a[ j ]; /* Shift value */ cannam@154: } cannam@154: a[ j + 1 ] = value; /* Write value */ cannam@154: } cannam@154: }