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     uint32_t indicesCount = (maxVal + kPageMask) >> kLogValuesPerPage;
58     uint32_t nPages = calcNumPages(ranges, nRanges);
59     uint32_t bitmapsCount = nPages << (kLogValuesPerPage - kLogBitsPerEl);
60     MappableData* data = MappableData::allocate(indicesCount, bitmapsCount);
61     mData.reset(data);
62     data->mMaxVal = maxVal;
63     uint16_t* indices = data->indices();
64     element* bitmaps = data->bitmaps();
65     memset(bitmaps, 0, sizeof(uint32_t) * bitmapsCount);
66     data->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 (data->mZeroPageIndex == noZeroPage) {
78                     data->mZeroPageIndex = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
79                 }
80                 for (uint32_t j = nonzeroPageEnd; j < startPage; j++) {
81                     indices[j] = data->mZeroPageIndex;
82                 }
83             }
84             indices[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             bitmaps[index] |=
92                     (kElAllOnes >> (start & kElMask)) & (kElAllOnes << ((~end + 1) & kElMask));
93         } else {
94             bitmaps[index] |= kElAllOnes >> (start & kElMask);
95             for (size_t j = 1; j < nElements - 1; j++) {
96                 bitmaps[index + j] = kElAllOnes;
97             }
98             bitmaps[index + nElements - 1] |= kElAllOnes << ((~end + 1) & kElMask);
99         }
100         for (size_t j = startPage + 1; j < endPage + 1; j++) {
101             indices[j] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
102         }
103         nonzeroPageEnd = endPage + 1;
104     }
105 }
106 
initFromBuffer(BufferReader * reader)107 void SparseBitSet::initFromBuffer(BufferReader* reader) {
108     uint32_t size = reader->read<uint32_t>();
109     if (size == 0) return;
110     mData.reset(reader->map<MappableData, alignof(MappableData)>(size));
111 }
112 
writeTo(BufferWriter * writer) const113 void SparseBitSet::writeTo(BufferWriter* writer) const {
114     if (mData == nullptr) {
115         // Write 0 for empty SparseBitSet.
116         writer->write<uint32_t>(0);
117         return;
118     }
119     size_t size = mData->size();
120     writer->write<uint32_t>(size);
121     static_assert(alignof(MappableData) == 4);
122     MappableData* out = writer->reserve<MappableData, alignof(MappableData)>(size);
123     if (out != nullptr) {
124         memcpy(out, mData.get(), size);
125         out->mIsMapped = 1;
126     }
127 }
128 
CountLeadingZeros(element x)129 int SparseBitSet::CountLeadingZeros(element x) {
130     // Note: GCC / clang builtin
131     return sizeof(element) <= sizeof(int) ? __builtin_clz(x) : __builtin_clzl(x);
132 }
133 
nextSetBit(uint32_t fromIndex) const134 uint32_t SparseBitSet::nextSetBit(uint32_t fromIndex) const {
135     if (mData == nullptr || fromIndex >= mData->mMaxVal) {
136         return kNotFound;
137     }
138     uint32_t fromPage = fromIndex >> kLogValuesPerPage;
139     const element* bitmap = mData->bitmaps() + mData->indices()[fromPage];
140     uint32_t offset = (fromIndex & kPageMask) >> kLogBitsPerEl;
141     element e = bitmap[offset] & (kElAllOnes >> (fromIndex & kElMask));
142     if (e != 0) {
143         return (fromIndex & ~kElMask) + CountLeadingZeros(e);
144     }
145     for (uint32_t j = offset + 1; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) {
146         e = bitmap[j];
147         if (e != 0) {
148             return (fromIndex & ~kPageMask) + (j << kLogBitsPerEl) + CountLeadingZeros(e);
149         }
150     }
151     uint32_t maxPage = (mData->mMaxVal + kPageMask) >> kLogValuesPerPage;
152     for (uint32_t page = fromPage + 1; page < maxPage; page++) {
153         uint16_t index = mData->indices()[page];
154         if (index == mData->mZeroPageIndex) {
155             continue;
156         }
157         bitmap = mData->bitmaps() + index;
158         for (uint32_t j = 0; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) {
159             e = bitmap[j];
160             if (e != 0) {
161                 return (page << kLogValuesPerPage) + (j << kLogBitsPerEl) + CountLeadingZeros(e);
162             }
163         }
164     }
165     return kNotFound;
166 }
167 
168 // static
allocate(uint32_t indicesCount,uint32_t bitmapsCount)169 SparseBitSet::MappableData* SparseBitSet::MappableData::allocate(uint32_t indicesCount,
170                                                                  uint32_t bitmapsCount) {
171     MappableData* data = reinterpret_cast<MappableData*>(
172             malloc(MappableData::calcSize(indicesCount, bitmapsCount)));
173     data->mIndicesCount = indicesCount;
174     data->mBitmapsCount = bitmapsCount;
175     data->mIsMapped = 0;
176     return data;
177 }
178 
179 }  // namespace minikin
180