1 /* ------------------------------------------------------------------
2 * Copyright (C) 1998-2009 PacketVideo
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
13 * express or implied.
14 * See the License for the specific language governing permissions
15 * and limitations under the License.
16 * -------------------------------------------------------------------
17 */
18 /****************************************************************************************
19 Portions of this file are derived from the following 3GPP standard:
20
21 3GPP TS 26.073
22 ANSI-C code for the Adaptive Multi-Rate (AMR) speech codec
23 Available from http://www.3gpp.org
24
25 (C) 2004, 3GPP Organizational Partners (ARIB, ATIS, CCSA, ETSI, TTA, TTC)
26 Permission to distribute, modify and use this file under the standard license
27 terms listed above has been obtained from the copyright holder.
28 ****************************************************************************************/
29 /*
30 Pathname: ./audio/gsm-amr/c/src/inv_sqrt.c
31
32 ------------------------------------------------------------------------------
33 REVISION HISTORY
34
35 Description: Put file into template.
36
37 Description: Synchronized file with UMTS version 3.2.0. Updated coding
38 template. Removed unnecessary include files.
39
40 Description: Replaced basic_op.h with the header files of the math functions
41 used in the file.
42
43 Description: Made the following changes per comments from Phase 2/3 review:
44 1. Defined one local variable per line.
45 2. Used "&=", ">>=", and "+=" in the code.
46
47 Description: Updated template. Changed function interface to pass in a
48 pointer to overflow flag into the function instead of using a
49 global flag.
50
51 Description: Removed inclusion of inv_sqrt.tab file. Changed array name
52 from "table" to "inv_sqrt_tbl"
53
54 Description: Removed math operations that were not needed as functions,
55 this because the numbers themselves will not saturate the
56 operators, so there is not need to check for saturation.
57
58 Description: Updated copyrigth year, according to code review comments.
59
60 Description: Replaced "int" and/or "char" with defined types.
61 Added proper casting (Word32) to some left shifting operations
62
63 Who: Date:
64 Description:
65
66 ------------------------------------------------------------------------------
67 */
68
69 /*----------------------------------------------------------------------------
70 ; INCLUDES
71 ----------------------------------------------------------------------------*/
72 #include "inv_sqrt.h"
73 #include "typedef.h"
74 #include "basic_op.h"
75
76 /*----------------------------------------------------------------------------
77 ; MACROS
78 ; Define module specific macros here
79 ----------------------------------------------------------------------------*/
80
81
82 /*----------------------------------------------------------------------------
83 ; DEFINES
84 ; Include all pre-processor statements here. Include conditional
85 ; compile variables also.
86 ----------------------------------------------------------------------------*/
87
88
89 /*----------------------------------------------------------------------------
90 ; LOCAL FUNCTION DEFINITIONS
91 ; Function Prototype declaration
92 ----------------------------------------------------------------------------*/
93
94
95 /*----------------------------------------------------------------------------
96 ; LOCAL STORE/BUFFER/POINTER DEFINITIONS
97 ; Variable declaration - defined here and used outside this module
98 ----------------------------------------------------------------------------*/
99
100
101 /*
102 ------------------------------------------------------------------------------
103 FUNCTION NAME: Inv_sqrt
104 ------------------------------------------------------------------------------
105 INPUT AND OUTPUT DEFINITIONS
106
107 Inputs:
108 L_x = input value (Word32)
109 pOverflow = pointer to overflow flag
110
111 Outputs:
112 pOverflow -> if the Inv_sqrt operation resulted in an overflow.
113
114 Returns:
115 L_y = inverse squareroot of L_x (Word32)
116
117 Global Variables Used:
118 None.
119
120 Local Variables Needed:
121 None.
122
123 ------------------------------------------------------------------------------
124 FUNCTION DESCRIPTION
125
126 This function computes 1/sqrt(L_x), where L_x is positive.
127 If L_x is negative or zero, the result is 1 (3fff ffff).
128
129 The function 1/sqrt(L_x) is approximated by a table and linear
130 interpolation. The inverse square root is computed using the
131 following steps:
132 1- Normalization of L_x.
133 2- If (30-exponent) is even then shift right once.
134 3- exponent = (30-exponent)/2 +1
135 4- i = bit25-b31 of L_x; 16<=i<=63 because of normalization.
136 5- a = bit10-b24
137 6- i -=16
138 7- L_y = table[i]<<16 - (table[i] - table[i+1]) * a * 2
139 8- L_y >>= exponent
140
141 ------------------------------------------------------------------------------
142 REQUIREMENTS
143
144 None.
145
146 ------------------------------------------------------------------------------
147 REFERENCES
148
149 inv_sqrt.c, UMTS GSM AMR speech codec, R99 - Version 3.2.0, March 2, 2001
150
151 ------------------------------------------------------------------------------
152 PSEUDO-CODE
153
154 Word32 Inv_sqrt ( // (o) : output value
155 Word32 L_x // (i) : input value
156 )
157 {
158 Word16 exp, i, a, tmp;
159 Word32 L_y;
160
161 * The reference ETSI code uses a global Overflow flag. In the actual
162 * implementation a pointer to the overflow flag is passed into the function.
163 * This pointer is in turn passed into the basic math functions such as add(),
164 * L_shl(), L_shr(), sub() called by this module.
165
166 if (L_x <= (Word32) 0)
167 return ((Word32) 0x3fffffffL);
168
169 exp = norm_l (L_x);
170 L_x = L_shl (L_x, exp); // L_x is normalize
171
172 exp = sub (30, exp);
173
174 if ((exp & 1) == 0) // If exponent even -> shift right
175 {
176 L_x = L_shr (L_x, 1);
177 }
178 exp = shr (exp, 1);
179 exp = add (exp, 1);
180
181 L_x = L_shr (L_x, 9);
182 i = extract_h (L_x); // Extract b25-b31
183 L_x = L_shr (L_x, 1);
184 a = extract_l (L_x); // Extract b10-b24
185 a = a & (Word16) 0x7fff;
186
187 i = sub (i, 16);
188
189 L_y = L_deposit_h (table[i]); // table[i] << 16
190 tmp = sub (table[i], table[i + 1]); // table[i] - table[i+1])
191 L_y = L_msu (L_y, tmp, a); // L_y -= tmp*a*2
192
193 L_y = L_shr (L_y, exp); // denormalization
194
195 return (L_y);
196 }
197
198 ------------------------------------------------------------------------------
199 RESOURCES USED [optional]
200
201 When the code is written for a specific target processor the
202 the resources used should be documented below.
203
204 HEAP MEMORY USED: x bytes
205
206 STACK MEMORY USED: x bytes
207
208 CLOCK CYCLES: (cycle count equation for this function) + (variable
209 used to represent cycle count for each subroutine
210 called)
211 where: (cycle count variable) = cycle count for [subroutine
212 name]
213
214 ------------------------------------------------------------------------------
215 CAUTION [optional]
216 [State any special notes, constraints or cautions for users of this function]
217
218 ------------------------------------------------------------------------------
219 */
220
Inv_sqrt(Word32 L_x,Flag * pOverflow)221 Word32 Inv_sqrt( /* (o) : output value */
222 Word32 L_x, /* (i) : input value */
223 Flag * pOverflow /* (i) : pointer to overflow flag */
224 )
225 {
226 Word16 exp;
227 Word16 i;
228 Word16 a;
229 Word16 tmp;
230 Word32 L_y;
231 OSCL_UNUSED_ARG(pOverflow);
232
233 if (L_x <= (Word32) 0)
234 {
235 return ((Word32) 0x3fffffffL);
236 }
237
238 exp = norm_l(L_x);
239 L_x <<= exp; /* L_x is normalize */
240
241 exp = 30 - exp;
242
243 if ((exp & 1) == 0) /* If exponent even -> shift right */
244 {
245 L_x >>= 1;
246 }
247 exp >>= 1;
248 exp += 1;
249
250 L_x >>= 9;
251 i = (Word16)(L_x >> 16); /* Extract b25-b31 */
252 a = (Word16)(L_x >> 1); /* Extract b10-b24 */
253 a &= (Word16) 0x7fff;
254
255 i -= 16;
256
257 L_y = (Word32)inv_sqrt_tbl[i] << 16; /* inv_sqrt_tbl[i] << 16 */
258
259 /* inv_sqrt_tbl[i] - inv_sqrt_tbl[i+1]) */
260 tmp = inv_sqrt_tbl[i] - inv_sqrt_tbl[i + 1];
261 /* always a positive number less than 200 */
262
263 L_y -= ((Word32)tmp * a) << 1; /* L_y -= tmp*a*2 */
264 /* always a positive minus a small negative number */
265
266 L_y >>= exp; /* denormalization, exp always 0< exp < 31 */
267
268 return (L_y);
269 }
270
271