Line data    Source code

       1             : /*
       2             :  * Written by Wilco Dijkstra, 1996. The following email exchange establishes the
       3             :  * license.
       4             :  *
       5             :  * From: Wilco Dijkstra <Wilco.Dijkstra@ntlworld.com>
       6             :  * Date: Fri, Jun 24, 2011 at 3:20 AM
       7             :  * Subject: Re: sqrt routine
       8             :  * To: Kevin Ma <kma@google.com>
       9             :  * Hi Kevin,
      10             :  * Thanks for asking. Those routines are public domain (originally posted to
      11             :  * comp.sys.arm a long time ago), so you can use them freely for any purpose.
      12             :  * Cheers,
      13             :  * Wilco
      14             :  *
      15             :  * ----- Original Message -----
      16             :  * From: "Kevin Ma" <kma@google.com>
      17             :  * To: <Wilco.Dijkstra@ntlworld.com>
      18             :  * Sent: Thursday, June 23, 2011 11:44 PM
      19             :  * Subject: Fwd: sqrt routine
      20             :  * Hi Wilco,
      21             :  * I saw your sqrt routine from several web sites, including
      22             :  * http://www.finesse.demon.co.uk/steven/sqrt.html.
      23             :  * Just wonder if there's any copyright information with your Successive
      24             :  * approximation routines, or if I can freely use it for any purpose.
      25             :  * Thanks.
      26             :  * Kevin
      27             :  */
      28             : 
      29             : // Minor modifications in code style for WebRTC, 2012.
      30             : 
      31             : #include "webrtc/common_audio/signal_processing/include/signal_processing_library.h"
      32             : 
      33             : /*
      34             :  * Algorithm:
      35             :  * Successive approximation of the equation (root + delta) ^ 2 = N
      36             :  * until delta < 1. If delta < 1 we have the integer part of SQRT (N).
      37             :  * Use delta = 2^i for i = 15 .. 0.
      38             :  *
      39             :  * Output precision is 16 bits. Note for large input values (close to
      40             :  * 0x7FFFFFFF), bit 15 (the highest bit of the low 16-bit half word)
      41             :  * contains the MSB information (a non-sign value). Do with caution
      42             :  * if you need to cast the output to int16_t type.
      43             :  *
      44             :  * If the input value is negative, it returns 0.
      45             :  */
      46             : 
      47             : #define WEBRTC_SPL_SQRT_ITER(N)                 \
      48             :   try1 = root + (1 << (N));                     \
      49             :   if (value >= try1 << (N))                     \
      50             :   {                                             \
      51             :     value -= try1 << (N);                       \
      52             :     root |= 2 << (N);                           \
      53             :   }
      54             : 
      55           0 : int32_t WebRtcSpl_SqrtFloor(int32_t value)
      56             : {
      57           0 :   int32_t root = 0, try1;
      58             : 
      59           0 :   WEBRTC_SPL_SQRT_ITER (15);
      60           0 :   WEBRTC_SPL_SQRT_ITER (14);
      61           0 :   WEBRTC_SPL_SQRT_ITER (13);
      62           0 :   WEBRTC_SPL_SQRT_ITER (12);
      63           0 :   WEBRTC_SPL_SQRT_ITER (11);
      64           0 :   WEBRTC_SPL_SQRT_ITER (10);
      65           0 :   WEBRTC_SPL_SQRT_ITER ( 9);
      66           0 :   WEBRTC_SPL_SQRT_ITER ( 8);
      67           0 :   WEBRTC_SPL_SQRT_ITER ( 7);
      68           0 :   WEBRTC_SPL_SQRT_ITER ( 6);
      69           0 :   WEBRTC_SPL_SQRT_ITER ( 5);
      70           0 :   WEBRTC_SPL_SQRT_ITER ( 4);
      71           0 :   WEBRTC_SPL_SQRT_ITER ( 3);
      72           0 :   WEBRTC_SPL_SQRT_ITER ( 2);
      73           0 :   WEBRTC_SPL_SQRT_ITER ( 1);
      74           0 :   WEBRTC_SPL_SQRT_ITER ( 0);
      75             : 
      76           0 :   return root >> 1;
      77             : }