SparseBitSet.cpp revision fbbc5a6b361c623e47a433f83e7200b4e2ba3501 
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#define LOG_TAG "SparseBitSet"
18
19#include <stddef.h>
20#include <string.h>
21
22#include <log/log.h>
23
24#include <minikin/SparseBitSet.h>
25
26namespace minikin {
27
28const uint32_t SparseBitSet::kNotFound;
29
30void SparseBitSet::clear() {
31    mMaxVal = 0;
32    if (mOwnIndicesAndBitmaps) {
33        delete[] mIndices;
34        delete[] mBitmaps;
35        mIndexSize = 0;
36        mBitmapSize = 0;
37        mOwnIndicesAndBitmaps = false;
38    }
39}
40
41uint32_t SparseBitSet::calcNumPages(const uint32_t* ranges, size_t nRanges) {
42    bool haveZeroPage = false;
43    uint32_t nonzeroPageEnd = 0;
44    uint32_t nPages = 0;
45    for (size_t i = 0; i < nRanges; i++) {
46        uint32_t start = ranges[i * 2];
47        uint32_t end = ranges[i * 2 + 1];
48        uint32_t startPage = start >> kLogValuesPerPage;
49        uint32_t endPage = (end - 1) >> kLogValuesPerPage;
50        if (startPage >= nonzeroPageEnd) {
51            if (startPage > nonzeroPageEnd) {
52                if (!haveZeroPage) {
53                    haveZeroPage = true;
54                    nPages++;
55                }
56            }
57            nPages++;
58        }
59        nPages += endPage - startPage;
60        nonzeroPageEnd = endPage + 1;
61    }
62    return nPages;
63}
64
65void SparseBitSet::initFromRanges(const uint32_t* ranges, size_t nRanges) {
66    if (nRanges == 0) {
67        clear();
68        return;
69    }
70    mMaxVal = ranges[nRanges * 2 - 1];
71    mIndexSize = (mMaxVal + kPageMask) >> kLogValuesPerPage;
72    uint32_t* indices = new uint32_t[mIndexSize];
73    uint32_t nPages = calcNumPages(ranges, nRanges);
74    mBitmapSize = nPages << (kLogValuesPerPage - kLogBitsPerEl);
75    element* bitmaps = new element[mBitmapSize];
76    mOwnIndicesAndBitmaps = true;
77    memset(bitmaps, 0, nPages << (kLogValuesPerPage - 3));
78    mZeroPageIndex = noZeroPage;
79    uint32_t nonzeroPageEnd = 0;
80    uint32_t currentPage = 0;
81    for (size_t i = 0; i < nRanges; i++) {
82        uint32_t start = ranges[i * 2];
83        uint32_t end = ranges[i * 2 + 1];
84        LOG_ALWAYS_FATAL_IF(end < start);  // make sure range size is nonnegative
85        uint32_t startPage = start >> kLogValuesPerPage;
86        uint32_t endPage = (end - 1) >> kLogValuesPerPage;
87        if (startPage >= nonzeroPageEnd) {
88            if (startPage > nonzeroPageEnd) {
89                if (mZeroPageIndex == noZeroPage) {
90                    mZeroPageIndex = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
91                }
92                for (uint32_t j = nonzeroPageEnd; j < startPage; j++) {
93                    indices[j] = mZeroPageIndex;
94                }
95            }
96            indices[startPage] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
97        }
98
99        size_t index = ((currentPage - 1) << (kLogValuesPerPage - kLogBitsPerEl)) +
100            ((start & kPageMask) >> kLogBitsPerEl);
101        size_t nElements = (end - (start & ~kElMask) + kElMask) >> kLogBitsPerEl;
102        if (nElements == 1) {
103            bitmaps[index] |= (kElAllOnes >> (start & kElMask)) &
104                (kElAllOnes << ((~end + 1) & kElMask));
105        } else {
106            bitmaps[index] |= kElAllOnes >> (start & kElMask);
107            for (size_t j = 1; j < nElements - 1; j++) {
108                bitmaps[index + j] = kElAllOnes;
109            }
110            bitmaps[index + nElements - 1] |= kElAllOnes << ((~end + 1) & kElMask);
111        }
112        for (size_t j = startPage + 1; j < endPage + 1; j++) {
113            indices[j] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
114        }
115        nonzeroPageEnd = endPage + 1;
116    }
117    mBitmaps = bitmaps;
118    mIndices = indices;
119}
120
121struct SparseBitSetHeader {
122  uint32_t maxValue;
123  uint32_t zeroPageIndex;
124  uint32_t indexSize;
125  uint32_t bitmapSize;
126};
127
128bool SparseBitSet::initFromBuffer(const uint8_t* data, size_t size) {
129    // No need to be concerned about endianness here since Intel x86 CPUs are little-endian. ARM
130    // CPUs are bi-endian but the endianness is only changeable at reset time and is impossible to
131    // change at runtime. Thus incoming data is guaranteed to have the same endianness as when it
132    // was created.
133
134    if (data == nullptr || size < sizeof(SparseBitSetHeader)) {
135        clear();
136        return false;
137    }
138
139    // The serialized data starts with SparseBitSetHeader.
140    const SparseBitSetHeader* header = reinterpret_cast<const SparseBitSetHeader*>(data);
141    mMaxVal = header->maxValue;
142    mZeroPageIndex = header->zeroPageIndex;
143    mIndexSize = header->indexSize;
144    mBitmapSize = header->bitmapSize;
145
146    mOwnIndicesAndBitmaps = false;
147    if (mIndexSize == 0 || mBitmapSize == 0 || mMaxVal == 0) {
148        const bool isValidEmptyBitSet = (mIndexSize == 0 && mBitmapSize == 0 && mMaxVal == 0);
149        if (!isValidEmptyBitSet) {
150            clear();
151        }
152        return isValidEmptyBitSet;
153    }
154
155    const size_t indicesSizeInBytes = sizeof(mIndices[0]) * mIndexSize;
156    const size_t bitmapsSizeInBytes = sizeof(mBitmaps[0]) * mBitmapSize;
157    if (size != sizeof(SparseBitSetHeader) + indicesSizeInBytes + bitmapsSizeInBytes) {
158        clear();
159        return false;
160    }
161    data += sizeof(SparseBitSetHeader);
162    mIndices = reinterpret_cast<decltype(mIndices)>(data);
163    data += indicesSizeInBytes;
164    mBitmaps = reinterpret_cast<decltype(mBitmaps)>(data);
165    return true;
166}
167
168size_t SparseBitSet::writeToBuffer(uint8_t* out) const{
169    // See comments in SparseBitSet::initFromBuffer for the data structure.
170    const size_t indicesSizeInBytes = sizeof(mIndices[0]) * mIndexSize;
171    const size_t bitmapsSizeInBytes = sizeof(mBitmaps[0]) * mBitmapSize;
172    size_t necessarySize = sizeof(SparseBitSetHeader) + indicesSizeInBytes + bitmapsSizeInBytes;
173    if (out != nullptr) {
174        SparseBitSetHeader* header = reinterpret_cast<SparseBitSetHeader*>(out);
175        header->maxValue = mMaxVal;
176        header->zeroPageIndex = mZeroPageIndex;
177        header->indexSize = mIndexSize;
178        header->bitmapSize = mBitmapSize;
179
180        out += sizeof(SparseBitSetHeader);
181        memcpy(out, mIndices, indicesSizeInBytes);
182        out += indicesSizeInBytes;
183        memcpy(out, mBitmaps, bitmapsSizeInBytes);
184    }
185    return necessarySize;
186}
187
188int SparseBitSet::CountLeadingZeros(element x) {
189    // Note: GCC / clang builtin
190    return sizeof(element) <= sizeof(int) ? __builtin_clz(x) : __builtin_clzl(x);
191}
192
193uint32_t SparseBitSet::nextSetBit(uint32_t fromIndex) const {
194    if (fromIndex >= mMaxVal) {
195        return kNotFound;
196    }
197    uint32_t fromPage = fromIndex >> kLogValuesPerPage;
198    const element* bitmap = &mBitmaps[mIndices[fromPage]];
199    uint32_t offset = (fromIndex & kPageMask) >> kLogBitsPerEl;
200    element e = bitmap[offset] & (kElAllOnes >> (fromIndex & kElMask));
201    if (e != 0) {
202        return (fromIndex & ~kElMask) + CountLeadingZeros(e);
203    }
204    for (uint32_t j = offset + 1; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) {
205        e = bitmap[j];
206        if (e != 0) {
207            return (fromIndex & ~kPageMask) + (j << kLogBitsPerEl) + CountLeadingZeros(e);
208        }
209    }
210    uint32_t maxPage = (mMaxVal + kPageMask) >> kLogValuesPerPage;
211    for (uint32_t page = fromPage + 1; page < maxPage; page++) {
212        uint32_t index = mIndices[page];
213        if (index == mZeroPageIndex) {
214            continue;
215        }
216        bitmap = &mBitmaps[index];
217        for (uint32_t j = 0; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) {
218            e = bitmap[j];
219            if (e != 0) {
220                return (page << kLogValuesPerPage) + (j << kLogBitsPerEl) + CountLeadingZeros(e);
221            }
222        }
223    }
224    return kNotFound;
225}
226
227}  // namespace minikin
228