#include "gtest/gtest.h"
#include "gmock/gmock.h"
#include <cassert>

/** Counts the number of leading (left-most) zero bits in a 32-bit value.
 * Example: leadingZeros(0x2A) == leadingZeros(0000.0000.0000.0000.0000.0000.0010.1010) == 26
 * @param n Value.
 * @return Number of leading zeros in n.
 */
static inline size_t leadingZeros(size_t n) {
    assert(sizeof(n) >= 4);
    size_t count = 0;
    size_t mask = (1 << 31);

    while ((mask & n) != mask) {
        ++count;
        mask >>= 1;
    }

    return count;
}

/** Calculates the ceil'ed integer log2 of a given 32-bit value (ie. rounded up to the next larger integer).
 * Example log2ceil(1024) == 10, log2ceil(1023) == 10, log2ceil(1025) == 11.
 * @param n Value Must be > 0.
 * return Ceil'ed integer log2 of n.
 */
size_t log2ceil(size_t n) {
    assert(n != 0);
    // Subtract 1 from argument and add 1 to result to get ceiled value.
    return 31 - leadingZeros(n - 1) + 1;
}


//////////////////////////////////////////////////
// Unit tests.
//

using namespace testing;

TEST(LeadingZerosTest, simple) {
    EXPECT_EQ(26, leadingZeros(0x2A));
    EXPECT_EQ(0, leadingZeros(0xFFFFFFFF));
    EXPECT_EQ(32, leadingZeros(0));
    EXPECT_EQ(31, leadingZeros(1));
}

TEST(Log2CeilTest, simple) {
    EXPECT_EQ(10, log2ceil(1024));
    EXPECT_EQ(10, log2ceil(1023));
    EXPECT_EQ(11, log2ceil(1025));

    EXPECT_EQ(0, log2ceil(1));
    EXPECT_EQ(1, log2ceil(2));
    EXPECT_EQ(2, log2ceil(3));
    EXPECT_EQ(2, log2ceil(4));

    EXPECT_EQ(15, log2ceil(0x8000));
    EXPECT_EQ(31, log2ceil(0x80000000));
    EXPECT_EQ(32, log2ceil(0xffffffff));
}

int main(int argc, char* argv[]) {
    testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}