1/*
2 * Written by Wilco Dijkstra, 1996.
3 * Refer to NOTICE file at the root of git project.
4 *
5 * Minor modifications in code style for WebRTC, 2012.
6 */
7
8#include "signal_processing_library.h"
9
10/*
11 * Algorithm:
12 * Successive approximation of the equation (root + delta) ^ 2 = N
13 * until delta < 1. If delta < 1 we have the integer part of SQRT (N).
14 * Use delta = 2^i for i = 15 .. 0.
15 *
16 * Output precision is 16 bits. Note for large input values (close to
17 * 0x7FFFFFFF), bit 15 (the highest bit of the low 16-bit half word)
18 * contains the MSB information (a non-sign value). Do with caution
19 * if you need to cast the output to int16_t type.
20 *
21 * If the input value is negative, it returns 0.
22 */
23
24#define WEBRTC_SPL_SQRT_ITER(N)                 \
25  try1 = root + (1 << (N));                     \
26  if (value >= try1 << (N))                     \
27  {                                             \
28    value -= try1 << (N);                       \
29    root |= 2 << (N);                           \
30  }
31
32int32_t WebRtcSpl_SqrtFloor(int32_t value)
33{
34  int32_t root = 0, try1;
35
36  WEBRTC_SPL_SQRT_ITER (15);
37  WEBRTC_SPL_SQRT_ITER (14);
38  WEBRTC_SPL_SQRT_ITER (13);
39  WEBRTC_SPL_SQRT_ITER (12);
40  WEBRTC_SPL_SQRT_ITER (11);
41  WEBRTC_SPL_SQRT_ITER (10);
42  WEBRTC_SPL_SQRT_ITER ( 9);
43  WEBRTC_SPL_SQRT_ITER ( 8);
44  WEBRTC_SPL_SQRT_ITER ( 7);
45  WEBRTC_SPL_SQRT_ITER ( 6);
46  WEBRTC_SPL_SQRT_ITER ( 5);
47  WEBRTC_SPL_SQRT_ITER ( 4);
48  WEBRTC_SPL_SQRT_ITER ( 3);
49  WEBRTC_SPL_SQRT_ITER ( 2);
50  WEBRTC_SPL_SQRT_ITER ( 1);
51  WEBRTC_SPL_SQRT_ITER ( 0);
52
53  return root >> 1;
54}
55