isqrt.c

00001 /*
00002  * Copyright (c) 2014-2018, Arm Limited and affiliates.
00003  * SPDX-License-Identifier: Apache-2.0
00004  *
00005  * Licensed under the Apache License, Version 2.0 (the "License");
00006  * you may not use this file except in compliance with the License.
00007  * You may obtain a copy of the License at
00008  *
00009  *     http://www.apache.org/licenses/LICENSE-2.0
00010  *
00011  * Unless required by applicable law or agreed to in writing, software
00012  * distributed under the License is distributed on an "AS IS" BASIS,
00013  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00014  * See the License for the specific language governing permissions and
00015  * limitations under the License.
00016  */
00017 #include "nsconfig.h"
00018 #include "ns_types.h"
00019 #include "isqrt.h"
00020 
00021 /**
00022  * \brief Calculates integer square root
00023  *
00024  * Algorithm is from http://www.codecodex.com/wiki/Calculate_an_integer_square_root
00025  *
00026  * \param n number
00027  *
00028  * \return square root of the number (rounded down)
00029  */
00030 
00031 uint32_t isqrt32(uint32_t n)
00032 {
00033     uint32_t root, remainder, place;
00034 
00035     root = 0;
00036     remainder = n;
00037     place = 0x40000000;
00038 
00039     while (place > remainder) {
00040         place = place >> 2;
00041     }
00042     while (place)  {
00043         if (remainder >= root + place) {
00044             remainder = remainder - root - place;
00045             root = root + (place << 1);
00046         }
00047         root = root >> 1;
00048         place = place >> 2;
00049     }
00050     return root;
00051 }