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 mIndicesCount = (mMaxVal + kPageMask) >> kLogValuesPerPage;
59 // Avoid zero-filling mOwnedIndices.
60 mOwnedIndices.reset(new uint16_t[mIndicesCount]);
61 mIndices = mOwnedIndices.get();
62 uint32_t nPages = calcNumPages(ranges, nRanges);
63 mBitmapsCount = nPages << (kLogValuesPerPage - kLogBitsPerEl);
64 mOwnedBitmaps = std::make_unique<element[]>(mBitmapsCount);
65 mBitmaps = mOwnedBitmaps.get();
66 mZeroPageIndex = noZeroPage;
67 uint32_t nonzeroPageEnd = 0;
68 uint32_t currentPage = 0;
69 for (size_t i = 0; i < nRanges; i++) {
70 uint32_t start = ranges[i * 2];
71 uint32_t end = ranges[i * 2 + 1];
72 MINIKIN_ASSERT(start <= end, "Range size must be nonnegative");
73 uint32_t startPage = start >> kLogValuesPerPage;
74 uint32_t endPage = (end - 1) >> kLogValuesPerPage;
75 if (startPage >= nonzeroPageEnd) {
76 if (startPage > nonzeroPageEnd) {
77 if (mZeroPageIndex == noZeroPage) {
78 mZeroPageIndex = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
79 }
80 for (uint32_t j = nonzeroPageEnd; j < startPage; j++) {
81 mOwnedIndices[j] = mZeroPageIndex;
82 }
83 }
84 mOwnedIndices[startPage] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
85 }
86
87 size_t index = ((currentPage - 1) << (kLogValuesPerPage - kLogBitsPerEl)) +
88 ((start & kPageMask) >> kLogBitsPerEl);
89 size_t nElements = (end - (start & ~kElMask) + kElMask) >> kLogBitsPerEl;
90 if (nElements == 1) {
91 mOwnedBitmaps[index] |=
92 (kElAllOnes >> (start & kElMask)) & (kElAllOnes << ((~end + 1) & kElMask));
93 } else {
94 mOwnedBitmaps[index] |= kElAllOnes >> (start & kElMask);
95 for (size_t j = 1; j < nElements - 1; j++) {
96 mOwnedBitmaps[index + j] = kElAllOnes;
97 }
98 mOwnedBitmaps[index + nElements - 1] |= kElAllOnes << ((~end + 1) & kElMask);
99 }
100 for (size_t j = startPage + 1; j < endPage + 1; j++) {
101 mOwnedIndices[j] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
102 }
103 nonzeroPageEnd = endPage + 1;
104 }
105 }
106
initFromBuffer(BufferReader * reader)107 void SparseBitSet::initFromBuffer(BufferReader* reader) {
108 mMaxVal = reader->read<uint32_t>();
109 // mIndices and mBitmaps are not initialized when mMaxVal == 0
110 if (mMaxVal == 0) return;
111 std::tie(mIndices, mIndicesCount) = reader->readArray<uint16_t>();
112 // element is uint32_t
113 static_assert(sizeof(element) == 4);
114 std::tie(mBitmaps, mBitmapsCount) = reader->readArray<element>();
115 mZeroPageIndex = reader->read<uint16_t>();
116 }
117
writeTo(BufferWriter * writer) const118 void SparseBitSet::writeTo(BufferWriter* writer) const {
119 writer->write<uint32_t>(mMaxVal);
120 // mIndices and mBitmaps are not initialized when mMaxVal == 0
121 if (mMaxVal == 0) return;
122 writer->writeArray<uint16_t>(mIndices, mIndicesCount);
123 writer->writeArray<element>(mBitmaps, mBitmapsCount);
124 writer->write<uint16_t>(mZeroPageIndex);
125 }
126
CountLeadingZeros(element x)127 int SparseBitSet::CountLeadingZeros(element x) {
128 // Note: GCC / clang builtin
129 return sizeof(element) <= sizeof(int) ? __builtin_clz(x) : __builtin_clzl(x);
130 }
131
nextSetBit(uint32_t fromIndex) const132 uint32_t SparseBitSet::nextSetBit(uint32_t fromIndex) const {
133 if (fromIndex >= mMaxVal) {
134 return kNotFound;
135 }
136 uint32_t fromPage = fromIndex >> kLogValuesPerPage;
137 const element* bitmap = &mBitmaps[mIndices[fromPage]];
138 uint32_t offset = (fromIndex & kPageMask) >> kLogBitsPerEl;
139 element e = bitmap[offset] & (kElAllOnes >> (fromIndex & kElMask));
140 if (e != 0) {
141 return (fromIndex & ~kElMask) + CountLeadingZeros(e);
142 }
143 for (uint32_t j = offset + 1; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) {
144 e = bitmap[j];
145 if (e != 0) {
146 return (fromIndex & ~kPageMask) + (j << kLogBitsPerEl) + CountLeadingZeros(e);
147 }
148 }
149 uint32_t maxPage = (mMaxVal + kPageMask) >> kLogValuesPerPage;
150 for (uint32_t page = fromPage + 1; page < maxPage; page++) {
151 uint16_t index = mIndices[page];
152 if (index == mZeroPageIndex) {
153 continue;
154 }
155 bitmap = &mBitmaps[index];
156 for (uint32_t j = 0; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) {
157 e = bitmap[j];
158 if (e != 0) {
159 return (page << kLogValuesPerPage) + (j << kLogBitsPerEl) + CountLeadingZeros(e);
160 }
161 }
162 }
163 return kNotFound;
164 }
165
166 } // namespace minikin
167