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