bcb4e51a409d94ae670de96afb8483a4f7855294Stephan Bosch/* Copyright (c) 2001-2018 Dovecot authors, see the included COPYING file */
9fe07780492524a34423686794bc1b4061206246Phil Carmody
9fe07780492524a34423686794bc1b4061206246Phil Carmody/* Unit tests for bit twiddles library */
9fe07780492524a34423686794bc1b4061206246Phil Carmody
9fe07780492524a34423686794bc1b4061206246Phil Carmody#include "test-lib.h"
9fe07780492524a34423686794bc1b4061206246Phil Carmody
9fe07780492524a34423686794bc1b4061206246Phil Carmody#include <stdio.h>
9fe07780492524a34423686794bc1b4061206246Phil Carmody
9fe07780492524a34423686794bc1b4061206246Phil Carmody/* nearest_power(0) = error bits_requiredXX(0) = 0
9fe07780492524a34423686794bc1b4061206246Phil Carmody nearest_power(1) = 1 = 1<<0 bits_requiredXX(1) = 1
9fe07780492524a34423686794bc1b4061206246Phil Carmody nearest_power(2) = 2 = 1<<1 bits_requiredXX(2) = 2
9fe07780492524a34423686794bc1b4061206246Phil Carmody nearest_power(3) = 4 = 1<<2 bits_requiredXX(3) = 2
9fe07780492524a34423686794bc1b4061206246Phil Carmody nearest_power(4) = 4 = 1<<2 bits_requiredXX(4) = 3
9fe07780492524a34423686794bc1b4061206246Phil Carmody nearest_power(5) = 8 = 1<<3 bits_requiredXX(5) = 3
9fe07780492524a34423686794bc1b4061206246Phil Carmody nearest_power(7) = 8 = 1<<3 bits_requiredXX(7) = 3
9fe07780492524a34423686794bc1b4061206246Phil Carmody nearest_power(8) = 8 = 1<<3 bits_requiredXX(8) = 4
9fe07780492524a34423686794bc1b4061206246Phil Carmody*/
9fe07780492524a34423686794bc1b4061206246Phil Carmody
9fe07780492524a34423686794bc1b4061206246Phil Carmody/* nearest_power(num) == 1ULL << bits_required64(num-1) */
9fe07780492524a34423686794bc1b4061206246Phil Carmodystatic void test_nearest_power(void)
9fe07780492524a34423686794bc1b4061206246Phil Carmody{
9fe07780492524a34423686794bc1b4061206246Phil Carmody unsigned int b;
147dbf5e74344caf9baf4048999ce0e5419f9e51Phil Carmody size_t num;
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_begin("nearest_power()");
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_assert(nearest_power(1)==1);
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_assert(nearest_power(2)==2);
147dbf5e74344caf9baf4048999ce0e5419f9e51Phil Carmody for (b = 2; b < CHAR_BIT*sizeof(size_t) - 1; ++b) {
147dbf5e74344caf9baf4048999ce0e5419f9e51Phil Carmody /* b=2 tests 3,4,5; b=3 tests 7,8,9; ... b=30 tests ~1G */
147dbf5e74344caf9baf4048999ce0e5419f9e51Phil Carmody num = (size_t)1 << b;
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_assert_idx(nearest_power(num-1) == num, b);
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_assert_idx(nearest_power(num ) == num, b);
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_assert_idx(nearest_power(num+1) == num<<1, b);
9fe07780492524a34423686794bc1b4061206246Phil Carmody }
147dbf5e74344caf9baf4048999ce0e5419f9e51Phil Carmody /* With 32-bit size_t, now: b=31 tests 2G-1, 2G, not 2G+1. */
147dbf5e74344caf9baf4048999ce0e5419f9e51Phil Carmody num = (size_t)1 << b;
147dbf5e74344caf9baf4048999ce0e5419f9e51Phil Carmody test_assert_idx(nearest_power(num-1) == num, b);
147dbf5e74344caf9baf4048999ce0e5419f9e51Phil Carmody test_assert_idx(nearest_power(num ) == num, b);
147dbf5e74344caf9baf4048999ce0e5419f9e51Phil Carmody /* i_assert()s: test_assert_idx(nearest_power(num+1) == num<<1, b); */
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_end();
9fe07780492524a34423686794bc1b4061206246Phil Carmody}
9fe07780492524a34423686794bc1b4061206246Phil Carmody
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainenstatic void test_bits_is_power_of_two(void)
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen{
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen test_begin("bits_is_power_of_two()");
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen for (unsigned int i = 0; i < 64; i++)
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen test_assert_idx(bits_is_power_of_two(1ULL << i), i);
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen for (unsigned int i = 2; i < 64; i++) {
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen test_assert_idx(!bits_is_power_of_two((1ULL << i) - 1), i);
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen test_assert_idx(!bits_is_power_of_two((1ULL << i) + 1), i);
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen }
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen test_assert(!bits_is_power_of_two(0));
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen test_assert(!bits_is_power_of_two(0xffffffffffffffffULL));
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen test_end();
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen}
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen
9fe07780492524a34423686794bc1b4061206246Phil Carmodystatic void test_bits_requiredXX(void)
9fe07780492524a34423686794bc1b4061206246Phil Carmody{
9fe07780492524a34423686794bc1b4061206246Phil Carmody /* As ..64 depends on ..32 and tests it twice,
9fe07780492524a34423686794bc1b4061206246Phil Carmody * and ..32 depends on ..16 and tests it twice,
9fe07780492524a34423686794bc1b4061206246Phil Carmody * etc., we only test ..64
9fe07780492524a34423686794bc1b4061206246Phil Carmody */
9fe07780492524a34423686794bc1b4061206246Phil Carmody unsigned int b;
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_begin("bits_requiredXX()");
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_assert(bits_required64(0) == 0);
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_assert(bits_required64(1) == 1);
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_assert(bits_required64(2) == 2);
9fe07780492524a34423686794bc1b4061206246Phil Carmody for (b = 2; b < 64; ++b) {
9fe07780492524a34423686794bc1b4061206246Phil Carmody /* b=2 tests 3,4,5; b=3 tests 7,8,9; ... */
9fe07780492524a34423686794bc1b4061206246Phil Carmody uint64_t num = 1ULL << b;
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_assert_idx(bits_required64(num-1) == b, b);
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_assert_idx(bits_required64(num ) == b+1, b);
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_assert_idx(bits_required64(num+1) == b+1, b);
9fe07780492524a34423686794bc1b4061206246Phil Carmody }
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_end();
9fe07780492524a34423686794bc1b4061206246Phil Carmody}
9fe07780492524a34423686794bc1b4061206246Phil Carmody
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainenstatic void test_sum_overflows(void)
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen{
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen#define MAX64 (uint64_t)-1
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen static const struct {
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen uint64_t a, b;
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen bool overflows;
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen } tests[] = {
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen { MAX64-1, 1, FALSE },
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen { MAX64, 1, TRUE },
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen { MAX64-1, 1, FALSE },
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen { MAX64-1, 2, TRUE },
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen { MAX64-1, MAX64-1, TRUE },
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen { MAX64-1, MAX64, TRUE },
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen { MAX64, MAX64, TRUE }
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen };
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen unsigned int i;
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen test_begin("UINT64_SUM_OVERFLOWS");
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen for (i = 0; i < N_ELEMENTS(tests); i++)
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen test_assert(UINT64_SUM_OVERFLOWS(tests[i].a, tests[i].b) == tests[i].overflows);
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen test_end();
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen}
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmodystatic void test_bits_fraclog(void)
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody{
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody unsigned int fracbits;
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody for (fracbits = 0; fracbits < 6; fracbits++) {
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody static char name[] = "fraclog x-bit";
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody name[8] = '0'+ fracbits;
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody test_begin(name);
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody unsigned int i;
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody unsigned int last_end = ~0u;
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody for (i = 0; i < BITS_FRACLOG_BUCKETS(fracbits); i++) {
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody unsigned int start = bits_fraclog_bucket_start(i, fracbits);
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody unsigned int end = bits_fraclog_bucket_end(i, fracbits);
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody test_assert_idx(start == last_end + 1, i);
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody last_end = end;
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody test_assert_idx(bits_fraclog(start, fracbits) == i, i);
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody test_assert_idx(bits_fraclog(end, fracbits) == i, i);
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody }
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody test_assert_idx(last_end == ~0u, fracbits);
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody test_end();
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody }
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody}
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody/* The compiler *should* generate different code when the fracbits parameter
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody is a compile-time constant, so we also need to check that's the case.
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody*/
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmodystatic void test_bits_fraclog_const(void)
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody{
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody#define FRACBITS 2
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody#define STR2(s) #s
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody#define STR(s) STR2(s)
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody test_begin("fraclog constant " STR(FRACBITS) " bit");
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody unsigned int i;
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody unsigned int last_end = ~0u;
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody for (i = 0; i < BITS_FRACLOG_BUCKETS(FRACBITS); i++) {
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody unsigned int start = bits_fraclog_bucket_start(i, FRACBITS);
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody unsigned int end = bits_fraclog_bucket_end(i, FRACBITS);
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody test_assert_idx(start == last_end + 1, i);
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody last_end = end;
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody test_assert_idx(bits_fraclog(start, FRACBITS) == i, i);
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody test_assert_idx(bits_fraclog(end, FRACBITS) == i, i);
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody }
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody test_assert(last_end == ~0u);
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody test_end();
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody}
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomistatic void test_bits_rotl32(void)
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi{
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_begin("bits_rotl32");
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_assert(bits_rotl32(0x1c00000eU, 3) == 0xe0000070U);
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_assert(bits_rotl32(0xe0000070U, 5) == 0x00000e1cU);
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_assert(bits_rotl32(0x00000e1cU, 0) == 0x00000e1cU);
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_end();
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi}
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomistatic void test_bits_rotl64(void)
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi{
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_begin("bits_rotl64");
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_assert(bits_rotl64(0x1c0000000000000eUL, 3) == 0xe000000000000070UL);
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_assert(bits_rotl64(0xe000000000000070UL, 5) == 0x0000000000000e1cUL);
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_assert(bits_rotl64(0x0000000000000e1cUL, 0) == 0x0000000000000e1cUL);
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_end();
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi}
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomistatic void test_bits_rotr32(void)
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi{
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_begin("bits_rotr32");
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_assert(bits_rotr32(0x1c00000eU, 3) == 0xc3800001U);
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_assert(bits_rotr32(0xc3800001U, 5) == 0x0e1c0000U);
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_assert(bits_rotr32(0x00000e1cU, 0) == 0x00000e1cU);
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_end();
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi}
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomistatic void test_bits_rotr64(void)
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi{
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_begin("bits_rotr64");
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_assert(bits_rotr64(0x1c0000000000000eUL, 3) == 0xc380000000000001UL);
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_assert(bits_rotr64(0xc380000000000001UL, 5) == 0x0e1c000000000000UL);
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_assert(bits_rotr64(0x0000000000000e1cUL, 0) == 0x0000000000000e1cUL);
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_end();
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi}
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmodyvoid test_bits(void)
9fe07780492524a34423686794bc1b4061206246Phil Carmody{
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_nearest_power();
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen test_bits_is_power_of_two();
9fe07780492524a34423686794bc1b4061206246Phil Carmody test_bits_requiredXX();
20be2a7b3ad5aa062d15e0d7146aaad3ba172804Phil Carmody test_bits_fraclog();
943ba393dafc67e0df779829c3d33ac34bcb3fa3Phil Carmody test_bits_fraclog_const();
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_bits_rotl32();
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_bits_rotr32();
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_bits_rotl64();
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi test_bits_rotr64();
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen test_sum_overflows();
9fe07780492524a34423686794bc1b4061206246Phil Carmody}