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/****************************************************************************************
19Portions 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)
26Permission to distribute, modify and use this file under the standard license
27terms 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
154Word32 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
221Word32 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