diff options
Diffstat (limited to 'lib/rbcodec/codecs/libopus/silk/float/sort_FLP.c')
-rw-r--r-- | lib/rbcodec/codecs/libopus/silk/float/sort_FLP.c | 83 |
1 files changed, 83 insertions, 0 deletions
diff --git a/lib/rbcodec/codecs/libopus/silk/float/sort_FLP.c b/lib/rbcodec/codecs/libopus/silk/float/sort_FLP.c new file mode 100644 index 0000000000..0e18f31950 --- /dev/null +++ b/lib/rbcodec/codecs/libopus/silk/float/sort_FLP.c | |||
@@ -0,0 +1,83 @@ | |||
1 | /*********************************************************************** | ||
2 | Copyright (c) 2006-2011, Skype Limited. All rights reserved. | ||
3 | Redistribution and use in source and binary forms, with or without | ||
4 | modification, are permitted provided that the following conditions | ||
5 | are met: | ||
6 | - Redistributions of source code must retain the above copyright notice, | ||
7 | this list of conditions and the following disclaimer. | ||
8 | - Redistributions in binary form must reproduce the above copyright | ||
9 | notice, this list of conditions and the following disclaimer in the | ||
10 | documentation and/or other materials provided with the distribution. | ||
11 | - Neither the name of Internet Society, IETF or IETF Trust, nor the | ||
12 | names of specific contributors, may be used to endorse or promote | ||
13 | products derived from this software without specific prior written | ||
14 | permission. | ||
15 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | ||
16 | AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
17 | IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
18 | ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE | ||
19 | LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | ||
20 | CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | ||
21 | SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | ||
22 | INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | ||
23 | CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | ||
24 | ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | ||
25 | POSSIBILITY OF SUCH DAMAGE. | ||
26 | ***********************************************************************/ | ||
27 | |||
28 | #ifdef HAVE_CONFIG_H | ||
29 | #include "config.h" | ||
30 | #endif | ||
31 | |||
32 | /* Insertion sort (fast for already almost sorted arrays): */ | ||
33 | /* Best case: O(n) for an already sorted array */ | ||
34 | /* Worst case: O(n^2) for an inversely sorted array */ | ||
35 | |||
36 | #include "typedef.h" | ||
37 | #include "SigProc_FLP.h" | ||
38 | |||
39 | void silk_insertion_sort_decreasing_FLP( | ||
40 | silk_float *a, /* I/O Unsorted / Sorted vector */ | ||
41 | opus_int *idx, /* O Index vector for the sorted elements */ | ||
42 | const opus_int L, /* I Vector length */ | ||
43 | const opus_int K /* I Number of correctly sorted positions */ | ||
44 | ) | ||
45 | { | ||
46 | silk_float value; | ||
47 | opus_int i, j; | ||
48 | |||
49 | /* Safety checks */ | ||
50 | celt_assert( K > 0 ); | ||
51 | celt_assert( L > 0 ); | ||
52 | celt_assert( L >= K ); | ||
53 | |||
54 | /* Write start indices in index vector */ | ||
55 | for( i = 0; i < K; i++ ) { | ||
56 | idx[ i ] = i; | ||
57 | } | ||
58 | |||
59 | /* Sort vector elements by value, decreasing order */ | ||
60 | for( i = 1; i < K; i++ ) { | ||
61 | value = a[ i ]; | ||
62 | for( j = i - 1; ( j >= 0 ) && ( value > a[ j ] ); j-- ) { | ||
63 | a[ j + 1 ] = a[ j ]; /* Shift value */ | ||
64 | idx[ j + 1 ] = idx[ j ]; /* Shift index */ | ||
65 | } | ||
66 | a[ j + 1 ] = value; /* Write value */ | ||
67 | idx[ j + 1 ] = i; /* Write index */ | ||
68 | } | ||
69 | |||
70 | /* If less than L values are asked check the remaining values, */ | ||
71 | /* but only spend CPU to ensure that the K first values are correct */ | ||
72 | for( i = K; i < L; i++ ) { | ||
73 | value = a[ i ]; | ||
74 | if( value > a[ K - 1 ] ) { | ||
75 | for( j = K - 2; ( j >= 0 ) && ( value > a[ j ] ); j-- ) { | ||
76 | a[ j + 1 ] = a[ j ]; /* Shift value */ | ||
77 | idx[ j + 1 ] = idx[ j ]; /* Shift index */ | ||
78 | } | ||
79 | a[ j + 1 ] = value; /* Write value */ | ||
80 | idx[ j + 1 ] = i; /* Write index */ | ||
81 | } | ||
82 | } | ||
83 | } | ||