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