1/*
2 * Copyright (c) 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25#include "precompiled.hpp"
26#include "libadt/vectset.hpp"
27#include "runtime/os.hpp"
28#include "utilities/population_count.hpp"
29#include "utilities/globalDefinitions.hpp"
30#include "unittest.hpp"
31
32uint8_t test_popcnt_bitsInByte[BITS_IN_BYTE_ARRAY_SIZE] = {
33 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
34 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
35 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
36 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
37 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
38 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
39 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
40 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
41 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
42 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
43 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
44 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
45 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
46 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
47 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
48 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
49};
50
51TEST(population_count, sparse) {
52 // Step through the entire input range from a random starting point,
53 // verify population_count return values against the lookup table
54 // approach used historically
55 uint32_t step = 4711;
56 for (uint32_t value = os::random() % step; value < UINT_MAX - step; value += step) {
57 uint32_t lookup = test_popcnt_bitsInByte[(value >> 24) & 0xff] +
58 test_popcnt_bitsInByte[(value >> 16) & 0xff] +
59 test_popcnt_bitsInByte[(value >> 8) & 0xff] +
60 test_popcnt_bitsInByte[ value & 0xff];
61
62 EXPECT_EQ(lookup, population_count(value))
63 << "value = " << value;
64 }
65
66 // Test a few edge cases
67 EXPECT_EQ(0u, population_count(0u))
68 << "value = " << 0;
69 EXPECT_EQ(1u, population_count(1u))
70 << "value = " << 1;
71 EXPECT_EQ(1u, population_count(2u))
72 << "value = " << 2;
73 EXPECT_EQ(32u, population_count(UINT_MAX))
74 << "value = " << UINT_MAX;
75 EXPECT_EQ(31u, population_count(UINT_MAX - 1))
76 << "value = " << (UINT_MAX - 1);
77}
78