integer_sqrt.c

手机加密通话软件

/* Copyright 2001,2002,2003 NAH6
 * All Rights Reserved
 *
 * Parts Copyright DoD, Parts Copyright Starium
 *
 */
/* -*-C-*-
*******************************************************************************
*
* RCS:          $Id: integer_sqrt.c,v 1.3 2003/11/22 16:34:28 itsme Exp $
* Description:  integer square root approximation
* Author:       Eric Blossom
*
* (C) Copyright 1999, Starium, Ltd., all rights reserved.
*
*******************************************************************************
*/

#include "fxpt.h"

/*
 * Compute the integer square root of x using the bisection method.
 * Note that this requires no divides.
 *
 * The value returned is the largest y such that y*y <= x
 */

int16
integer_sqrt (int32 x)
{
  int   i;
  int   t, y;
  int   mask;

  if (x <= 0)
    return 0;

  y = 0;
  mask = 1 << 15;
  for (i = 0; i < 16; i++){
    t = y | mask;
    if (((long) t * t) <= x)
      y = t;
    mask >>= 1;
  }
  return y;
}

fxpt_16
fxpt_sqrt16 (fxpt_16 x)
{
  return integer_sqrt (x << 15);
}