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 #include "main_FIX.h"
33 #include "stack_alloc.h"
34 #include "tuning_parameters.h"
35
36 /*****************************/
37 /* Internal function headers */
38 /*****************************/
39
40 typedef struct {
41 opus_int32 Q36_part;
42 opus_int32 Q48_part;
43 } inv_D_t;
44
45 /* Factorize square matrix A into LDL form */
46 static OPUS_INLINE void silk_LDL_factorize_FIX(
47 opus_int32 *A, /* I/O Pointer to Symetric Square Matrix */
48 opus_int M, /* I Size of Matrix */
49 opus_int32 *L_Q16, /* I/O Pointer to Square Upper triangular Matrix */
50 inv_D_t *inv_D /* I/O Pointer to vector holding inverted diagonal elements of D */
51 );
52
53 /* Solve Lx = b, when L is lower triangular and has ones on the diagonal */
54 static OPUS_INLINE void silk_LS_SolveFirst_FIX(
55 const opus_int32 *L_Q16, /* I Pointer to Lower Triangular Matrix */
56 opus_int M, /* I Dim of Matrix equation */
57 const opus_int32 *b, /* I b Vector */
58 opus_int32 *x_Q16 /* O x Vector */
59 );
60
61 /* Solve L^t*x = b, where L is lower triangular with ones on the diagonal */
62 static OPUS_INLINE void silk_LS_SolveLast_FIX(
63 const opus_int32 *L_Q16, /* I Pointer to Lower Triangular Matrix */
64 const opus_int M, /* I Dim of Matrix equation */
65 const opus_int32 *b, /* I b Vector */
66 opus_int32 *x_Q16 /* O x Vector */
67 );
68
69 static OPUS_INLINE void silk_LS_divide_Q16_FIX(
70 opus_int32 T[], /* I/O Numenator vector */
71 inv_D_t *inv_D, /* I 1 / D vector */
72 opus_int M /* I dimension */
73 );
74
75 /* Solves Ax = b, assuming A is symmetric */
silk_solve_LDL_FIX(opus_int32 * A,opus_int M,const opus_int32 * b,opus_int32 * x_Q16)76 void silk_solve_LDL_FIX(
77 opus_int32 *A, /* I Pointer to symetric square matrix A */
78 opus_int M, /* I Size of matrix */
79 const opus_int32 *b, /* I Pointer to b vector */
80 opus_int32 *x_Q16 /* O Pointer to x solution vector */
81 )
82 {
83 VARDECL( opus_int32, L_Q16 );
84 opus_int32 Y[ MAX_MATRIX_SIZE ];
85 inv_D_t inv_D[ MAX_MATRIX_SIZE ];
86 SAVE_STACK;
87
88 silk_assert( M <= MAX_MATRIX_SIZE );
89 ALLOC( L_Q16, M * M, opus_int32 );
90
91 /***************************************************
92 Factorize A by LDL such that A = L*D*L',
93 where L is lower triangular with ones on diagonal
94 ****************************************************/
95 silk_LDL_factorize_FIX( A, M, L_Q16, inv_D );
96
97 /****************************************************
98 * substitute D*L'*x = Y. ie:
99 L*D*L'*x = b => L*Y = b <=> Y = inv(L)*b
100 ******************************************************/
101 silk_LS_SolveFirst_FIX( L_Q16, M, b, Y );
102
103 /****************************************************
104 D*L'*x = Y <=> L'*x = inv(D)*Y, because D is
105 diagonal just multiply with 1/d_i
106 ****************************************************/
107 silk_LS_divide_Q16_FIX( Y, inv_D, M );
108
109 /****************************************************
110 x = inv(L') * inv(D) * Y
111 *****************************************************/
112 silk_LS_SolveLast_FIX( L_Q16, M, Y, x_Q16 );
113 RESTORE_STACK;
114 }
115
silk_LDL_factorize_FIX(opus_int32 * A,opus_int M,opus_int32 * L_Q16,inv_D_t * inv_D)116 static OPUS_INLINE void silk_LDL_factorize_FIX(
117 opus_int32 *A, /* I/O Pointer to Symetric Square Matrix */
118 opus_int M, /* I Size of Matrix */
119 opus_int32 *L_Q16, /* I/O Pointer to Square Upper triangular Matrix */
120 inv_D_t *inv_D /* I/O Pointer to vector holding inverted diagonal elements of D */
121 )
122 {
123 opus_int i, j, k, status, loop_count;
124 const opus_int32 *ptr1, *ptr2;
125 opus_int32 diag_min_value, tmp_32, err;
126 opus_int32 v_Q0[ MAX_MATRIX_SIZE ], D_Q0[ MAX_MATRIX_SIZE ];
127 opus_int32 one_div_diag_Q36, one_div_diag_Q40, one_div_diag_Q48;
128
129 silk_assert( M <= MAX_MATRIX_SIZE );
130
131 status = 1;
132 diag_min_value = silk_max_32( silk_SMMUL( silk_ADD_SAT32( A[ 0 ], A[ silk_SMULBB( M, M ) - 1 ] ), SILK_FIX_CONST( FIND_LTP_COND_FAC, 31 ) ), 1 << 9 );
133 for( loop_count = 0; loop_count < M && status == 1; loop_count++ ) {
134 status = 0;
135 for( j = 0; j < M; j++ ) {
136 ptr1 = matrix_adr( L_Q16, j, 0, M );
137 tmp_32 = 0;
138 for( i = 0; i < j; i++ ) {
139 v_Q0[ i ] = silk_SMULWW( D_Q0[ i ], ptr1[ i ] ); /* Q0 */
140 tmp_32 = silk_SMLAWW( tmp_32, v_Q0[ i ], ptr1[ i ] ); /* Q0 */
141 }
142 tmp_32 = silk_SUB32( matrix_ptr( A, j, j, M ), tmp_32 );
143
144 if( tmp_32 < diag_min_value ) {
145 tmp_32 = silk_SUB32( silk_SMULBB( loop_count + 1, diag_min_value ), tmp_32 );
146 /* Matrix not positive semi-definite, or ill conditioned */
147 for( i = 0; i < M; i++ ) {
148 matrix_ptr( A, i, i, M ) = silk_ADD32( matrix_ptr( A, i, i, M ), tmp_32 );
149 }
150 status = 1;
151 break;
152 }
153 D_Q0[ j ] = tmp_32; /* always < max(Correlation) */
154
155 /* two-step division */
156 one_div_diag_Q36 = silk_INVERSE32_varQ( tmp_32, 36 ); /* Q36 */
157 one_div_diag_Q40 = silk_LSHIFT( one_div_diag_Q36, 4 ); /* Q40 */
158 err = silk_SUB32( (opus_int32)1 << 24, silk_SMULWW( tmp_32, one_div_diag_Q40 ) ); /* Q24 */
159 one_div_diag_Q48 = silk_SMULWW( err, one_div_diag_Q40 ); /* Q48 */
160
161 /* Save 1/Ds */
162 inv_D[ j ].Q36_part = one_div_diag_Q36;
163 inv_D[ j ].Q48_part = one_div_diag_Q48;
164
165 matrix_ptr( L_Q16, j, j, M ) = 65536; /* 1.0 in Q16 */
166 ptr1 = matrix_adr( A, j, 0, M );
167 ptr2 = matrix_adr( L_Q16, j + 1, 0, M );
168 for( i = j + 1; i < M; i++ ) {
169 tmp_32 = 0;
170 for( k = 0; k < j; k++ ) {
171 tmp_32 = silk_SMLAWW( tmp_32, v_Q0[ k ], ptr2[ k ] ); /* Q0 */
172 }
173 tmp_32 = silk_SUB32( ptr1[ i ], tmp_32 ); /* always < max(Correlation) */
174
175 /* tmp_32 / D_Q0[j] : Divide to Q16 */
176 matrix_ptr( L_Q16, i, j, M ) = silk_ADD32( silk_SMMUL( tmp_32, one_div_diag_Q48 ),
177 silk_RSHIFT( silk_SMULWW( tmp_32, one_div_diag_Q36 ), 4 ) );
178
179 /* go to next column */
180 ptr2 += M;
181 }
182 }
183 }
184
185 silk_assert( status == 0 );
186 }
187
silk_LS_divide_Q16_FIX(opus_int32 T[],inv_D_t * inv_D,opus_int M)188 static OPUS_INLINE void silk_LS_divide_Q16_FIX(
189 opus_int32 T[], /* I/O Numenator vector */
190 inv_D_t *inv_D, /* I 1 / D vector */
191 opus_int M /* I dimension */
192 )
193 {
194 opus_int i;
195 opus_int32 tmp_32;
196 opus_int32 one_div_diag_Q36, one_div_diag_Q48;
197
198 for( i = 0; i < M; i++ ) {
199 one_div_diag_Q36 = inv_D[ i ].Q36_part;
200 one_div_diag_Q48 = inv_D[ i ].Q48_part;
201
202 tmp_32 = T[ i ];
203 T[ i ] = silk_ADD32( silk_SMMUL( tmp_32, one_div_diag_Q48 ), silk_RSHIFT( silk_SMULWW( tmp_32, one_div_diag_Q36 ), 4 ) );
204 }
205 }
206
207 /* Solve Lx = b, when L is lower triangular and has ones on the diagonal */
silk_LS_SolveFirst_FIX(const opus_int32 * L_Q16,opus_int M,const opus_int32 * b,opus_int32 * x_Q16)208 static OPUS_INLINE void silk_LS_SolveFirst_FIX(
209 const opus_int32 *L_Q16, /* I Pointer to Lower Triangular Matrix */
210 opus_int M, /* I Dim of Matrix equation */
211 const opus_int32 *b, /* I b Vector */
212 opus_int32 *x_Q16 /* O x Vector */
213 )
214 {
215 opus_int i, j;
216 const opus_int32 *ptr32;
217 opus_int32 tmp_32;
218
219 for( i = 0; i < M; i++ ) {
220 ptr32 = matrix_adr( L_Q16, i, 0, M );
221 tmp_32 = 0;
222 for( j = 0; j < i; j++ ) {
223 tmp_32 = silk_SMLAWW( tmp_32, ptr32[ j ], x_Q16[ j ] );
224 }
225 x_Q16[ i ] = silk_SUB32( b[ i ], tmp_32 );
226 }
227 }
228
229 /* Solve L^t*x = b, where L is lower triangular with ones on the diagonal */
silk_LS_SolveLast_FIX(const opus_int32 * L_Q16,const opus_int M,const opus_int32 * b,opus_int32 * x_Q16)230 static OPUS_INLINE void silk_LS_SolveLast_FIX(
231 const opus_int32 *L_Q16, /* I Pointer to Lower Triangular Matrix */
232 const opus_int M, /* I Dim of Matrix equation */
233 const opus_int32 *b, /* I b Vector */
234 opus_int32 *x_Q16 /* O x Vector */
235 )
236 {
237 opus_int i, j;
238 const opus_int32 *ptr32;
239 opus_int32 tmp_32;
240
241 for( i = M - 1; i >= 0; i-- ) {
242 ptr32 = matrix_adr( L_Q16, 0, i, M );
243 tmp_32 = 0;
244 for( j = M - 1; j > i; j-- ) {
245 tmp_32 = silk_SMLAWW( tmp_32, ptr32[ silk_SMULBB( j, M ) ], x_Q16[ j ] );
246 }
247 x_Q16[ i ] = silk_SUB32( b[ i ], tmp_32 );
248 }
249 }
250