/**
  isqrt module - Copyright (C) 2002 John L. Dahlstrom
 
  You are granted the rights to redistribute, use, merge,
  modify, publish, and/or sell copies of this software, in
  source or binary form, only under the following terms:

  1. Redistributed source code must retain this original notice,
     including copyright, terms, and disclaimer.

  2. Redistributed binary forms must be accompanied by this
     notice, including copyright, terms, and disclaimer, in
     documentation and/or other prominent media bundled upon
     distribution.

  Disclaimer
  THIS SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
  KIND, EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE
  WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  PURPOSE, AND NON-INFRINGEMENT OF THIRD PARTY RIGHTS.  IN NO
  EVENT SHALL ANY AUTHOR BE LIABLE FOR ANY CLAIM OR DAMAGES,
  INCLUDING DIRECT, INDIRECT, INCIDENTAL, CONSEQUENTIAL, OR
  SPECIAL DAMAGES, ARISING OUT OF OR IN CONNECTION WITH THE USE,
  MISUSE, PERFORMANCE, OR MALFUNCTION OF THE SOFTWARE, EVEN IF
  ANY AUTHOR OR CONTRIBUTOR HAS BEEN ADVISED OF SUCH DAMAGES.

*/

#include <stdint.h>
/* typedef unsigned long uint32_t; */

/**
  isqrt returns the integer truncated square root of n, a 32-bit integer
*/
uint32_t
isqrt( uint32_t n )
{
  uint32_t rs = 0;
  uint32_t dP2 = 1 << 30;
  uint32_t gs;
				/* Iteration specific constants may replace */
				/* dP2; an optimizing compiler may do this. */
#define isqrt_iter \
  { gs = rs | dP2; rs >>= 1; if( n >= gs ) { n -= gs; rs |= dP2; } dP2 >>=2; }

  isqrt_iter;  isqrt_iter;  isqrt_iter;  isqrt_iter;
  isqrt_iter;  isqrt_iter;  isqrt_iter;  isqrt_iter;
  isqrt_iter;  isqrt_iter;  isqrt_iter;  isqrt_iter;
  isqrt_iter;  isqrt_iter;  isqrt_iter;  isqrt_iter;

  return rs;
}