///////////////////////////////////////////////////////////////////////////////////
/// OpenGL Mathematics (glm.g-truc.net)
///
/// Copyright (c) 2005 - 2015 G-Truc Creation (www.g-truc.net)
/// Permission is hereby granted, free of charge, to any person obtaining a copy
/// of this software and associated documentation files (the "Software"), to deal
/// in the Software without restriction, including without limitation the rights
/// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
/// copies of the Software, and to permit persons to whom the Software is
/// furnished to do so, subject to the following conditions:
/// 
/// The above copyright notice and this permission notice shall be included in
/// all copies or substantial portions of the Software.
/// 
/// Restrictions:
///             By making use of the Software for military purposes, you choose to make
///             a Bunny unhappy.
/// 
/// THE 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 NONINFRINGEMENT. IN NO EVENT SHALL THE
/// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
/// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
/// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
/// THE SOFTWARE.
///
/// @ref gtx_integer
/// @file glm/gtx/integer.inl
/// @date 2005-12-24 / 2011-10-13
/// @author Christophe Riccio
///////////////////////////////////////////////////////////////////////////////////////////////////

namespace glm
{
        // pow
        GLM_FUNC_QUALIFIER int pow(int x, int y)
        {
                if(y == 0)
                        return 1;
                int result = x;
                for(int i = 1; i < y; ++i)
                        result *= x;
                return result;
        }

        // sqrt: From Christopher J. Musial, An integer square root, Graphics Gems, 1990, page 387
        GLM_FUNC_QUALIFIER int sqrt(int x)
        {
                if(x <= 1) return x;

                int NextTrial = x >> 1;
                int CurrentAnswer;

                do
                {
                        CurrentAnswer = NextTrial;
                        NextTrial = (NextTrial + x / NextTrial) >> 1;
                } while(NextTrial < CurrentAnswer);

                return CurrentAnswer;
        }

// Henry Gordon Dietz: http://aggregate.org/MAGIC/
namespace detail
{
        GLM_FUNC_QUALIFIER unsigned int ones32(unsigned int x)
        {
                /* 32-bit recursive reduction using SWAR...
                but first step is mapping 2-bit values
                into sum of 2 1-bit values in sneaky way
                */
                x -= ((x >> 1) & 0x55555555);
                x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
                x = (((x >> 4) + x) & 0x0f0f0f0f);
                x += (x >> 8);
                x += (x >> 16);
                return(x & 0x0000003f);
        }
}//namespace detail

        // Henry Gordon Dietz: http://aggregate.org/MAGIC/
/*
        GLM_FUNC_QUALIFIER unsigned int floor_log2(unsigned int x)
        {
                x |= (x >> 1);
                x |= (x >> 2);
                x |= (x >> 4);
                x |= (x >> 8);
                x |= (x >> 16);

                return _detail::ones32(x) >> 1;
        }
*/
        // mod
        GLM_FUNC_QUALIFIER int mod(int x, int y)
        {
                return x - y * (x / y);
        }

        // factorial (!12 max, integer only)
        template <typename genType>
        GLM_FUNC_QUALIFIER genType factorial(genType const & x)
        {
                genType Temp = x;
                genType Result;
                for(Result = 1; Temp > 1; --Temp)
                        Result *= Temp;
                return Result;
        }

        template <typename T, precision P>
        GLM_FUNC_QUALIFIER tvec2<T, P> factorial(
                tvec2<T, P> const & x)
        {
                return tvec2<T, P>(
                        factorial(x.x),
                        factorial(x.y));
        }

        template <typename T, precision P>
        GLM_FUNC_QUALIFIER tvec3<T, P> factorial(
                tvec3<T, P> const & x)
        {
                return tvec3<T, P>(
                        factorial(x.x),
                        factorial(x.y),
                        factorial(x.z));
        }

        template <typename T, precision P>
        GLM_FUNC_QUALIFIER tvec4<T, P> factorial(
                tvec4<T, P> const & x)
        {
                return tvec4<T, P>(
                        factorial(x.x),
                        factorial(x.y),
                        factorial(x.z),
                        factorial(x.w));
        }

        GLM_FUNC_QUALIFIER uint pow(uint x, uint y)
        {
                uint result = x;
                for(uint i = 1; i < y; ++i)
                        result *= x;
                return result;
        }

        GLM_FUNC_QUALIFIER uint sqrt(uint x)
        {
                if(x <= 1) return x;

                uint NextTrial = x >> 1;
                uint CurrentAnswer;

                do
                {
                        CurrentAnswer = NextTrial;
                        NextTrial = (NextTrial + x / NextTrial) >> 1;
                } while(NextTrial < CurrentAnswer);

                return CurrentAnswer;
        }

        GLM_FUNC_QUALIFIER uint mod(uint x, uint y)
        {
                return x - y * (x / y);
        }

#if(GLM_COMPILER & (GLM_COMPILER_VC | GLM_COMPILER_GCC))

        GLM_FUNC_QUALIFIER unsigned int nlz(unsigned int x) 
        {
                return 31u - findMSB(x);
        }

#else

        // Hackers Delight: http://www.hackersdelight.org/HDcode/nlz.c.txt
        GLM_FUNC_QUALIFIER unsigned int nlz(unsigned int x) 
        {
                int y, m, n;

                y = -int(x >> 16);      // If left half of x is 0,
                m = (y >> 16) & 16;  // set n = 16.  If left half
                n = 16 - m;          // is nonzero, set n = 0 and
                x = x >> m;          // shift x right 16.
                                                        // Now x is of the form 0000xxxx.
                y = x - 0x100;       // If positions 8-15 are 0,
                m = (y >> 16) & 8;   // add 8 to n and shift x left 8.
                n = n + m;
                x = x << m;

                y = x - 0x1000;      // If positions 12-15 are 0,
                m = (y >> 16) & 4;   // add 4 to n and shift x left 4.
                n = n + m;
                x = x << m;

                y = x - 0x4000;      // If positions 14-15 are 0,
                m = (y >> 16) & 2;   // add 2 to n and shift x left 2.
                n = n + m;
                x = x << m;

                y = x >> 14;         // Set y = 0, 1, 2, or 3.
                m = y & ~(y >> 1);   // Set m = 0, 1, 2, or 2 resp.
                return unsigned(n + 2 - m);
        }

#endif//(GLM_COMPILER)

}//namespace glm