iPXE
isqrt.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>.
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License as
00006  * published by the Free Software Foundation; either version 2 of the
00007  * License, or any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful, but
00010  * WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
00017  * 02110-1301, USA.
00018  *
00019  * You can also choose to distribute this program under the terms of
00020  * the Unmodified Binary Distribution Licence (as given in the file
00021  * COPYING.UBDL), provided that you have satisfied its requirements.
00022  */
00023 
00024 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
00025 
00026 /** @file
00027  *
00028  * Integer square root
00029  *
00030  */
00031 
00032 #include <ipxe/isqrt.h>
00033 
00034 /**
00035  * Find integer square root
00036  *
00037  * @v value             Value
00038  * @v isqrt             Integer square root of value
00039  */
00040 unsigned long isqrt ( unsigned long value ) {
00041         unsigned long result = 0;
00042         unsigned long bit = ( 1UL << ( ( 8 * sizeof ( bit ) ) - 2 ) );
00043 
00044         while ( bit > value )
00045                 bit >>= 2;
00046         while ( bit ) {
00047                 if ( value >= ( result + bit ) ) {
00048                         value -= ( result + bit );
00049                         result = ( ( result >> 1 ) + bit );
00050                 } else {
00051                         result >>= 1;
00052                 }
00053                 bit >>= 2;
00054         }
00055         return result;
00056 }