SparseBitSetTest.cpp revision fbbc5a6b361c623e47a433f83e7200b4e2ba3501 
1/*
2 * Copyright (C) 2017 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <random>
18
19#include <gtest/gtest.h>
20#include <minikin/SparseBitSet.h>
21
22namespace minikin {
23
24TEST(SparseBitSetTest, randomTest) {
25    const uint32_t kTestRangeNum = 4096;
26
27    std::mt19937 mt;  // Fix seeds to be able to reproduce the result.
28    std::uniform_int_distribution<uint16_t> distribution(1, 512);
29
30    std::vector<uint32_t> range { distribution(mt) };
31    for (size_t i = 1; i < kTestRangeNum * 2; ++i) {
32        range.push_back((range.back() - 1) + distribution(mt));
33    }
34
35    SparseBitSet bitset;
36    bitset.initFromRanges(range.data(), range.size() / 2);
37
38    uint32_t ch = 0;
39    for (size_t i = 0; i < range.size() / 2; ++i) {
40        uint32_t start = range[i * 2];
41        uint32_t end = range[i * 2 + 1];
42
43        for (; ch < start; ch++) {
44            ASSERT_FALSE(bitset.get(ch)) << std::hex << ch;
45        }
46        for (; ch < end; ch++) {
47            ASSERT_TRUE(bitset.get(ch)) << std::hex << ch;
48        }
49    }
50    for (; ch < 0x1FFFFFF; ++ch) {
51        ASSERT_FALSE(bitset.get(ch)) << std::hex << ch;
52    }
53}
54
55TEST(SparseBitSetTest, randomTest_restoredFromBuffer) {
56    const uint32_t kTestRangeNum = 4096;
57
58    std::mt19937 mt;  // Fix seeds to be able to reproduce the result.
59    std::uniform_int_distribution<uint16_t> distribution(1, 512);
60
61    std::vector<uint32_t> range { distribution(mt) };
62    for (size_t i = 1; i < kTestRangeNum * 2; ++i) {
63        range.push_back((range.back() - 1) + distribution(mt));
64    }
65
66    SparseBitSet tmpBitset;
67    tmpBitset.initFromRanges(range.data(), range.size() / 2);
68
69    size_t bufSize = tmpBitset.writeToBuffer(nullptr);
70    ASSERT_NE(0U, bufSize);
71    std::vector<uint8_t> buffer(bufSize);
72    tmpBitset.writeToBuffer(buffer.data());
73
74    SparseBitSet bitset;
75    bitset.initFromBuffer(buffer.data(), buffer.size());
76
77    uint32_t ch = 0;
78    for (size_t i = 0; i < range.size() / 2; ++i) {
79        uint32_t start = range[i * 2];
80        uint32_t end = range[i * 2 + 1];
81
82        for (; ch < start; ch++) {
83            ASSERT_FALSE(bitset.get(ch)) << std::hex << ch;
84        }
85        for (; ch < end; ch++) {
86            ASSERT_TRUE(bitset.get(ch)) << std::hex << ch;
87        }
88    }
89    for (; ch < 0x1FFFFFF; ++ch) {
90        ASSERT_FALSE(bitset.get(ch)) << std::hex << ch;
91    }
92}
93
94TEST(SparseBitSetTest, emptyBitSet) {
95    SparseBitSet bitset;
96    uint32_t empty_bitset[4] = {
97        0 /* max value */, 0 /* zero page index */, 0 /* index size */, 0 /* bitmap size */
98    };
99    EXPECT_TRUE(bitset.initFromBuffer(
100            reinterpret_cast<uint8_t*>(empty_bitset), sizeof(empty_bitset)));
101}
102
103TEST(SparseBitSetTest, invalidData) {
104    SparseBitSet bitset;
105    EXPECT_FALSE(bitset.initFromBuffer(nullptr, 0));
106
107    // Buffer is too small.
108    uint32_t small_buffer[3] = { 0, 0, 0 };
109    EXPECT_FALSE(bitset.initFromBuffer(
110            reinterpret_cast<uint8_t*>(small_buffer), sizeof(small_buffer)));
111
112    // Buffer size does not match with necessary size.
113    uint32_t invalid_size_buffer[4] = {
114        0x12345678 /* max value */, 0 /* zero page index */, 0x50 /* index size*/,
115        0x80 /* bitmap size */
116    };
117    EXPECT_FALSE(bitset.initFromBuffer(
118            reinterpret_cast<uint8_t*>(invalid_size_buffer), sizeof(invalid_size_buffer)));
119
120    // max value, index size, bitmap size must be zero if the bitset is empty.
121    uint32_t invalid_empty_bitset1[4] = {
122        1 /* max value */, 0 /* zero page index */, 0 /* index size */, 0 /* bitmap size */
123    };
124    EXPECT_FALSE(bitset.initFromBuffer(
125            reinterpret_cast<uint8_t*>(invalid_empty_bitset1), sizeof(invalid_empty_bitset1)));
126
127    uint32_t invalid_empty_bitset2[4] = {
128        0 /* max value */, 0 /* zero page index */, 1 /* index size */, 0 /* bitmap size */
129    };
130    EXPECT_FALSE(bitset.initFromBuffer(
131            reinterpret_cast<uint8_t*>(invalid_empty_bitset2), sizeof(invalid_empty_bitset2)));
132
133    uint32_t invalid_empty_bitset3[4] = {
134        0 /* max value */, 0 /* zero page index */, 0 /* index size */, 1 /* bitmap size */
135    };
136    EXPECT_FALSE(bitset.initFromBuffer(
137            reinterpret_cast<uint8_t*>(invalid_empty_bitset3), sizeof(invalid_empty_bitset3)));
138}
139
140}  // namespace minikin
141