/*-------------------------------------------------------------------------
* drawElements Base Portability Library
* -------------------------------------
*
* Copyright 2014 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
*//*!
* \file
* \brief 32-bit integer math.
*//*--------------------------------------------------------------------*/
#include "deInt32.h"
DE_BEGIN_EXTERN_C
const deInt8 g_clzLUT[256] =
{
8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
const deInt8 g_ctzLUT[256] =
{
8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};
/*--------------------------------------------------------------------*//*!
* \brief Compute the reciprocal of an integer.
* \param a Input value.
* \param rcp Pointer to resulting reciprocal "mantissa" value.
* \param exp Pointer to resulting exponent value.
*
* The returned value is split into an exponent part and a mantissa part for
* practical reasons. The actual reciprocal can be computed with the formula:
* result = exp2(exp) * rcp / (1<<DE_RCP_FRAC_BITS).
*//*--------------------------------------------------------------------*/
void deRcp32 (deUint32 a, deUint32* rcp, int* exp)
{
enum { RCP_LUT_BITS = 8 };
static const deUint32 s_rcpLUT[1<<RCP_LUT_BITS] =
{
0x40000000, 0x3fc03fc0, 0x3f80fe03, 0x3f423954,
0x3f03f03f, 0x3ec62159, 0x3e88cb3c, 0x3e4bec88,
0x3e0f83e0, 0x3dd38ff0, 0x3d980f66, 0x3d5d00f5,
0x3d226357, 0x3ce8354b, 0x3cae7592, 0x3c7522f3,
0x3c3c3c3c, 0x3c03c03c, 0x3bcbadc7, 0x3b9403b9,
0x3b5cc0ed, 0x3b25e446, 0x3aef6ca9, 0x3ab95900,
0x3a83a83a, 0x3a4e5947, 0x3a196b1e, 0x39e4dcb8,
0x39b0ad12, 0x397cdb2c, 0x3949660a, 0x39164cb5,
0x38e38e38, 0x38b129a2, 0x387f1e03, 0x384d6a72,
0x381c0e07, 0x37eb07dd, 0x37ba5713, 0x3789facb,
0x3759f229, 0x372a3c56, 0x36fad87b, 0x36cbc5c7,
0x369d0369, 0x366e9095, 0x36406c80, 0x36129663,
0x35e50d79, 0x35b7d0ff, 0x358ae035, 0x355e3a5f,
0x3531dec0, 0x3505cca2, 0x34da034d, 0x34ae820e,
0x34834834, 0x3458550f, 0x342da7f2, 0x34034034,
0x33d91d2a, 0x33af3e2e, 0x3385a29d, 0x335c49d4,
0x33333333, 0x330a5e1b, 0x32e1c9f0, 0x32b97617,
0x329161f9, 0x32698cff, 0x3241f693, 0x321a9e24,
0x31f3831f, 0x31cca4f5, 0x31a6031a, 0x317f9d00,
0x3159721e, 0x313381ec, 0x310dcbe1, 0x30e84f79,
0x30c30c30, 0x309e0184, 0x30792ef5, 0x30549403,
0x30303030, 0x300c0300, 0x2fe80bfa, 0x2fc44aa2,
0x2fa0be82, 0x2f7d6724, 0x2f5a4411, 0x2f3754d7,
0x2f149902, 0x2ef21023, 0x2ecfb9c8, 0x2ead9584,
0x2e8ba2e8, 0x2e69e18a, 0x2e4850fe, 0x2e26f0db,
0x2e05c0b8, 0x2de4c02d, 0x2dc3eed6, 0x2da34c4d,
0x2d82d82d, 0x2d629215, 0x2d4279a2, 0x2d228e75,
0x2d02d02d, 0x2ce33e6c, 0x2cc3d8d4, 0x2ca49f0a,
0x2c8590b2, 0x2c66ad71, 0x2c47f4ee, 0x2c2966d0,
0x2c0b02c0, 0x2becc868, 0x2bceb771, 0x2bb0cf87,
0x2b931057, 0x2b75798c, 0x2b580ad6, 0x2b3ac3e2,
0x2b1da461, 0x2b00ac02, 0x2ae3da78, 0x2ac72f74,
0x2aaaaaaa, 0x2a8e4bcd, 0x2a721291, 0x2a55fead,
0x2a3a0fd5, 0x2a1e45c2, 0x2a02a02a, 0x29e71ec5,
0x29cbc14e, 0x29b0877d, 0x2995710e, 0x297a7dbb,
0x295fad40, 0x2944ff5a, 0x292a73c7, 0x29100a44,
0x28f5c28f, 0x28db9c68, 0x28c1978f, 0x28a7b3c5,
0x288df0ca, 0x28744e61, 0x285acc4b, 0x28416a4c,
0x28282828, 0x280f05a2, 0x27f6027f, 0x27dd1e85,
0x27c45979, 0x27abb323, 0x27932b48, 0x277ac1b2,
0x27627627, 0x274a4870, 0x27323858, 0x271a45a6,
0x27027027, 0x26eab7a3, 0x26d31be7, 0x26bb9cbf,
0x26a439f6, 0x268cf359, 0x2675c8b6, 0x265eb9da,
0x2647c694, 0x2630eeb1, 0x261a3202, 0x26039055,
0x25ed097b, 0x25d69d43, 0x25c04b80, 0x25aa1402,
0x2593f69b, 0x257df31c, 0x2568095a, 0x25523925,
0x253c8253, 0x2526e4b7, 0x25116025, 0x24fbf471,
0x24e6a171, 0x24d166f9, 0x24bc44e1, 0x24a73afd,
0x24924924, 0x247d6f2e, 0x2468acf1, 0x24540245,
0x243f6f02, 0x242af300, 0x24168e18, 0x24024024,
0x23ee08fb, 0x23d9e878, 0x23c5de76, 0x23b1eace,
0x239e0d5b, 0x238a45f8, 0x23769480, 0x2362f8cf,
0x234f72c2, 0x233c0233, 0x2328a701, 0x23156107,
0x23023023, 0x22ef1432, 0x22dc0d12, 0x22c91aa1,
0x22b63cbe, 0x22a37347, 0x2290be1c, 0x227e1d1a,
0x226b9022, 0x22591713, 0x2246b1ce, 0x22346033,
0x22222222, 0x220ff77c, 0x21fde021, 0x21ebdbf5,
0x21d9ead7, 0x21c80cab, 0x21b64151, 0x21a488ac,
0x2192e29f, 0x21814f0d, 0x216fcdd8, 0x215e5ee4,
0x214d0214, 0x213bb74d, 0x212a7e72, 0x21195766,
0x21084210, 0x20f73e53, 0x20e64c14, 0x20d56b38,
0x20c49ba5, 0x20b3dd40, 0x20a32fef, 0x20929398,
0x20820820, 0x20718d6f, 0x2061236a, 0x2050c9f8,
0x20408102, 0x2030486c, 0x20202020, 0x20100804
};
DE_STATIC_ASSERT(DE_LENGTH_OF_ARRAY(s_rcpLUT) == (1<<RCP_LUT_BITS));
int shift = deClz32(a);
deUint32 normalized = (deUint32)a << shift; /* Highest bit is always 1. */
int lookupNdx = (normalized >> (31 - RCP_LUT_BITS)) & ((1<<RCP_LUT_BITS)-1); /* Discard high bit, leave 8 next highest bits to lowest bits of normalized. */
deUint32 result;
deUint32 tmp;
/* Must be non-negative. */
DE_ASSERT(a > 0);
/* First approximation from lookup table. */
DE_ASSERT(lookupNdx >= 0 && lookupNdx < (1<<RCP_LUT_BITS));
result = s_rcpLUT[lookupNdx];
/* Newton-Raphson iteration for improved accuracy (has 16 bits of accuracy afterwards). */
tmp = deSafeMuluAsr32(result, normalized, 31);
result = deSafeMuluAsr32(result, (2u<<DE_RCP_FRAC_BITS) - tmp, DE_RCP_FRAC_BITS);
/* Second Newton-Raphson iteration (now has full accuracy). */
tmp = deSafeMuluAsr32(result, normalized, 31);
result = deSafeMuluAsr32(result, (2u<<DE_RCP_FRAC_BITS) - tmp, DE_RCP_FRAC_BITS);
/* Return results. */
*rcp = result;
*exp = 31 - shift;
}
DE_END_EXTERN_C