Line data Source code
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 0 : 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 : {
47 : opus_int32 value;
48 : opus_int i, j;
49 :
50 : /* Safety checks */
51 0 : silk_assert( K > 0 );
52 0 : silk_assert( L > 0 );
53 0 : silk_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 : }
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 : }
67 0 : a[ j + 1 ] = value; /* Write value */
68 0 : idx[ j + 1 ] = i; /* Write index */
69 : }
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 : }
80 0 : a[ j + 1 ] = value; /* Write value */
81 0 : idx[ j + 1 ] = i; /* Write index */
82 : }
83 : }
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 : silk_assert( K > 0 );
100 : silk_assert( L > 0 );
101 : silk_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 0 : 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 : {
140 : opus_int value;
141 : opus_int i, j;
142 :
143 : /* Safety checks */
144 0 : silk_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 : }
152 0 : a[ j + 1 ] = value; /* Write value */
153 : }
154 0 : }
|
