1 /*
2 * Copyright (C) 2012 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 "minikin/SparseBitSet.h"
18
19 #include "MinikinInternal.h"
20
21 namespace minikin {
22
23 const uint32_t SparseBitSet::kNotFound;
24
calcNumPages(const uint32_t * ranges,size_t nRanges)25 uint32_t SparseBitSet::calcNumPages(const uint32_t* ranges, size_t nRanges) {
26 bool haveZeroPage = false;
27 uint32_t nonzeroPageEnd = 0;
28 uint32_t nPages = 0;
29 for (size_t i = 0; i < nRanges; i++) {
30 uint32_t start = ranges[i * 2];
31 uint32_t end = ranges[i * 2 + 1];
32 uint32_t startPage = start >> kLogValuesPerPage;
33 uint32_t endPage = (end - 1) >> kLogValuesPerPage;
34 if (startPage >= nonzeroPageEnd) {
35 if (startPage > nonzeroPageEnd) {
36 if (!haveZeroPage) {
37 haveZeroPage = true;
38 nPages++;
39 }
40 }
41 nPages++;
42 }
43 nPages += endPage - startPage;
44 nonzeroPageEnd = endPage + 1;
45 }
46 return nPages;
47 }
48
initFromRanges(const uint32_t * ranges,size_t nRanges)49 void SparseBitSet::initFromRanges(const uint32_t* ranges, size_t nRanges) {
50 if (nRanges == 0) {
51 return;
52 }
53 const uint32_t maxVal = ranges[nRanges * 2 - 1];
54 if (maxVal >= kMaximumCapacity) {
55 return;
56 }
57 mMaxVal = maxVal;
58 mIndices.reset(new uint16_t[(mMaxVal + kPageMask) >> kLogValuesPerPage]);
59 uint32_t nPages = calcNumPages(ranges, nRanges);
60 mBitmaps.reset(new element[nPages << (kLogValuesPerPage - kLogBitsPerEl)]());
61 mZeroPageIndex = noZeroPage;
62 uint32_t nonzeroPageEnd = 0;
63 uint32_t currentPage = 0;
64 for (size_t i = 0; i < nRanges; i++) {
65 uint32_t start = ranges[i * 2];
66 uint32_t end = ranges[i * 2 + 1];
67 MINIKIN_ASSERT(start <= end, "Range size must be nonnegative");
68 uint32_t startPage = start >> kLogValuesPerPage;
69 uint32_t endPage = (end - 1) >> kLogValuesPerPage;
70 if (startPage >= nonzeroPageEnd) {
71 if (startPage > nonzeroPageEnd) {
72 if (mZeroPageIndex == noZeroPage) {
73 mZeroPageIndex = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
74 }
75 for (uint32_t j = nonzeroPageEnd; j < startPage; j++) {
76 mIndices[j] = mZeroPageIndex;
77 }
78 }
79 mIndices[startPage] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
80 }
81
82 size_t index = ((currentPage - 1) << (kLogValuesPerPage - kLogBitsPerEl)) +
83 ((start & kPageMask) >> kLogBitsPerEl);
84 size_t nElements = (end - (start & ~kElMask) + kElMask) >> kLogBitsPerEl;
85 if (nElements == 1) {
86 mBitmaps[index] |=
87 (kElAllOnes >> (start & kElMask)) & (kElAllOnes << ((~end + 1) & kElMask));
88 } else {
89 mBitmaps[index] |= kElAllOnes >> (start & kElMask);
90 for (size_t j = 1; j < nElements - 1; j++) {
91 mBitmaps[index + j] = kElAllOnes;
92 }
93 mBitmaps[index + nElements - 1] |= kElAllOnes << ((~end + 1) & kElMask);
94 }
95 for (size_t j = startPage + 1; j < endPage + 1; j++) {
96 mIndices[j] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
97 }
98 nonzeroPageEnd = endPage + 1;
99 }
100 }
101
CountLeadingZeros(element x)102 int SparseBitSet::CountLeadingZeros(element x) {
103 // Note: GCC / clang builtin
104 return sizeof(element) <= sizeof(int) ? __builtin_clz(x) : __builtin_clzl(x);
105 }
106
nextSetBit(uint32_t fromIndex) const107 uint32_t SparseBitSet::nextSetBit(uint32_t fromIndex) const {
108 if (fromIndex >= mMaxVal) {
109 return kNotFound;
110 }
111 uint32_t fromPage = fromIndex >> kLogValuesPerPage;
112 const element* bitmap = &mBitmaps[mIndices[fromPage]];
113 uint32_t offset = (fromIndex & kPageMask) >> kLogBitsPerEl;
114 element e = bitmap[offset] & (kElAllOnes >> (fromIndex & kElMask));
115 if (e != 0) {
116 return (fromIndex & ~kElMask) + CountLeadingZeros(e);
117 }
118 for (uint32_t j = offset + 1; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) {
119 e = bitmap[j];
120 if (e != 0) {
121 return (fromIndex & ~kPageMask) + (j << kLogBitsPerEl) + CountLeadingZeros(e);
122 }
123 }
124 uint32_t maxPage = (mMaxVal + kPageMask) >> kLogValuesPerPage;
125 for (uint32_t page = fromPage + 1; page < maxPage; page++) {
126 uint16_t index = mIndices[page];
127 if (index == mZeroPageIndex) {
128 continue;
129 }
130 bitmap = &mBitmaps[index];
131 for (uint32_t j = 0; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) {
132 e = bitmap[j];
133 if (e != 0) {
134 return (page << kLogValuesPerPage) + (j << kLogBitsPerEl) + CountLeadingZeros(e);
135 }
136 }
137 }
138 return kNotFound;
139 }
140
141 } // namespace minikin
142