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