Line | Count | Source (jump to first uncovered line) |
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 | | /* Shell short: https://en.wikipedia.org/wiki/Shell_sort */ |
37 | | |
38 | | #include "SigProc_FIX.h" |
39 | | |
40 | | void silk_insertion_sort_increasing( |
41 | | opus_int32 *a, /* I/O Unsorted / Sorted vector */ |
42 | | opus_int *idx, /* O Index vector for the sorted elements */ |
43 | | const opus_int L, /* I Vector length */ |
44 | | const opus_int K /* I Number of correctly sorted positions */ |
45 | | ) |
46 | 0 | { |
47 | 0 | opus_int32 value; |
48 | 0 | opus_int i, j; |
49 | | |
50 | | /* Safety checks */ |
51 | 0 | celt_assert( K > 0 ); |
52 | 0 | celt_assert( L > 0 ); |
53 | 0 | celt_assert( L >= K ); |
54 | | |
55 | | /* Write start indices in index vector */ |
56 | 0 | for( i = 0; i < K; i++ ) { |
57 | 0 | idx[ i ] = i; |
58 | 0 | } |
59 | | |
60 | | /* Sort vector elements by value, increasing order */ |
61 | 0 | for( i = 1; i < K; i++ ) { |
62 | 0 | value = a[ i ]; |
63 | 0 | for( j = i - 1; ( j >= 0 ) && ( value < a[ j ] ); j-- ) { |
64 | 0 | a[ j + 1 ] = a[ j ]; /* Shift value */ |
65 | 0 | idx[ j + 1 ] = idx[ j ]; /* Shift index */ |
66 | 0 | } |
67 | 0 | a[ j + 1 ] = value; /* Write value */ |
68 | 0 | idx[ j + 1 ] = i; /* Write index */ |
69 | 0 | } |
70 | | |
71 | | /* If less than L values are asked for, check the remaining values, */ |
72 | | /* but only spend CPU to ensure that the K first values are correct */ |
73 | 0 | for( i = K; i < L; i++ ) { |
74 | 0 | value = a[ i ]; |
75 | 0 | if( value < a[ K - 1 ] ) { |
76 | 0 | for( j = K - 2; ( j >= 0 ) && ( value < a[ j ] ); j-- ) { |
77 | 0 | a[ j + 1 ] = a[ j ]; /* Shift value */ |
78 | 0 | idx[ j + 1 ] = idx[ j ]; /* Shift index */ |
79 | 0 | } |
80 | 0 | a[ j + 1 ] = value; /* Write value */ |
81 | 0 | idx[ j + 1 ] = i; /* Write index */ |
82 | 0 | } |
83 | 0 | } |
84 | 0 | } |
85 | | |
86 | | #ifdef FIXED_POINT |
87 | | /* This function is only used by the fixed-point build */ |
88 | | void silk_insertion_sort_decreasing_int16( |
89 | | opus_int16 *a, /* I/O Unsorted / Sorted vector */ |
90 | | opus_int *idx, /* O Index vector for the sorted elements */ |
91 | | const opus_int L, /* I Vector length */ |
92 | | const opus_int K /* I Number of correctly sorted positions */ |
93 | | ) |
94 | | { |
95 | | opus_int i, j; |
96 | | opus_int value; |
97 | | |
98 | | /* Safety checks */ |
99 | | celt_assert( K > 0 ); |
100 | | celt_assert( L > 0 ); |
101 | | celt_assert( L >= K ); |
102 | | |
103 | | /* Write start indices in index vector */ |
104 | | for( i = 0; i < K; i++ ) { |
105 | | idx[ i ] = i; |
106 | | } |
107 | | |
108 | | /* Sort vector elements by value, decreasing order */ |
109 | | for( i = 1; i < K; i++ ) { |
110 | | value = a[ i ]; |
111 | | for( j = i - 1; ( j >= 0 ) && ( value > a[ j ] ); j-- ) { |
112 | | a[ j + 1 ] = a[ j ]; /* Shift value */ |
113 | | idx[ j + 1 ] = idx[ j ]; /* Shift index */ |
114 | | } |
115 | | a[ j + 1 ] = value; /* Write value */ |
116 | | idx[ j + 1 ] = i; /* Write index */ |
117 | | } |
118 | | |
119 | | /* If less than L values are asked for, check the remaining values, */ |
120 | | /* but only spend CPU to ensure that the K first values are correct */ |
121 | | for( i = K; i < L; i++ ) { |
122 | | value = a[ i ]; |
123 | | if( value > a[ K - 1 ] ) { |
124 | | for( j = K - 2; ( j >= 0 ) && ( value > a[ j ] ); j-- ) { |
125 | | a[ j + 1 ] = a[ j ]; /* Shift value */ |
126 | | idx[ j + 1 ] = idx[ j ]; /* Shift index */ |
127 | | } |
128 | | a[ j + 1 ] = value; /* Write value */ |
129 | | idx[ j + 1 ] = i; /* Write index */ |
130 | | } |
131 | | } |
132 | | } |
133 | | #endif |
134 | | |
135 | | void silk_insertion_sort_increasing_all_values_int16( |
136 | | opus_int16 *a, /* I/O Unsorted / Sorted vector */ |
137 | | const opus_int L /* I Vector length */ |
138 | | ) |
139 | 0 | { |
140 | 0 | opus_int value; |
141 | 0 | opus_int i, j; |
142 | | |
143 | | /* Safety checks */ |
144 | 0 | celt_assert( L > 0 ); |
145 | | |
146 | | /* Sort vector elements by value, increasing order */ |
147 | 0 | for( i = 1; i < L; i++ ) { |
148 | 0 | value = a[ i ]; |
149 | 0 | for( j = i - 1; ( j >= 0 ) && ( value < a[ j ] ); j-- ) { |
150 | 0 | a[ j + 1 ] = a[ j ]; /* Shift value */ |
151 | 0 | } |
152 | 0 | a[ j + 1 ] = value; /* Write value */ |
153 | 0 | } |
154 | 0 | } |