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 #ifndef MINIKIN_SPARSE_BIT_SET_H
18 #define MINIKIN_SPARSE_BIT_SET_H
19 
20 #include <minikin/Buffer.h>
21 #include <sys/types.h>
22 
23 #include <cstdint>
24 #include <memory>
25 
26 // ---------------------------------------------------------------------------
27 
28 namespace minikin {
29 
30 // This is an implementation of a set of integers. It is optimized for
31 // values that are somewhat sparse, in the ballpark of a maximum value
32 // of thousands to millions. It is particularly efficient when there are
33 // large gaps. The motivating example is Unicode coverage of a font, but
34 // the abstraction itself is fully general.
35 class SparseBitSet {
36 public:
37     // Create an empty bit set.
SparseBitSet()38     SparseBitSet() : mData(nullptr) {}
39 
40     // Initialize the set to a new value, represented by ranges. For
41     // simplicity, these ranges are arranged as pairs of values,
42     // inclusive of start, exclusive of end, laid out in a uint32 array.
SparseBitSet(const uint32_t * ranges,size_t nRanges)43     SparseBitSet(const uint32_t* ranges, size_t nRanges) : SparseBitSet() {
44         initFromRanges(ranges, nRanges);
45     }
46 
SparseBitSet(BufferReader * reader)47     explicit SparseBitSet(BufferReader* reader) : SparseBitSet() { initFromBuffer(reader); }
48 
49     SparseBitSet(SparseBitSet&&) = default;
50     SparseBitSet& operator=(SparseBitSet&&) = default;
51 
52     void writeTo(BufferWriter* writer) const;
53 
54     // Determine whether the value is included in the set
get(uint32_t ch)55     bool get(uint32_t ch) const {
56         if (ch >= length()) return false;
57         const uint32_t* bitmap = mData->bitmaps() + mData->indices()[ch >> kLogValuesPerPage];
58         uint32_t index = ch & kPageMask;
59         return (bitmap[index >> kLogBitsPerEl] & (kElFirst >> (index & kElMask))) != 0;
60     }
61 
62     // One more than the maximum value in the set, or zero if empty
length()63     uint32_t length() const { return mData != nullptr ? mData->mMaxVal : 0; }
64 
empty()65     bool empty() const { return mData == nullptr || mData->mMaxVal == 0; }
66 
67     // The next set bit starting at fromIndex, inclusive, or kNotFound
68     // if none exists.
69     uint32_t nextSetBit(uint32_t fromIndex) const;
70 
71     static const uint32_t kNotFound = ~0u;
72 
73 private:
74     void initFromRanges(const uint32_t* ranges, size_t nRanges);
75     void initFromBuffer(BufferReader* reader);
76 
77     static const uint32_t kMaximumCapacity = 0xFFFFFF;
78     static const int kLogValuesPerPage = 8;
79     static const int kPageMask = (1 << kLogValuesPerPage) - 1;
80     static const int kLogBytesPerEl = 2;
81     static const int kLogBitsPerEl = kLogBytesPerEl + 3;
82     static const int kElMask = (1 << kLogBitsPerEl) - 1;
83     // invariant: sizeof(element) == (1 << kLogBytesPerEl)
84     typedef uint32_t element;
85     static const element kElAllOnes = ~((element)0);
86     static const element kElFirst = ((element)1) << kElMask;
87     static const uint16_t noZeroPage = 0xFFFF;
88 
89     static uint32_t calcNumPages(const uint32_t* ranges, size_t nRanges);
90     static int CountLeadingZeros(element x);
91 
92     // MappableData represents memory block holding SparseBitSet's fields.
93     // 'packed' is used so that the object layout won't change between
94     // 32-bit and 64-bit processes.
95     // 'aligned(4)' is only for optimization.
96     struct __attribute__((packed, aligned(4))) MappableData {
97         uint32_t mMaxVal;
98         uint32_t mIndicesCount;
99         uint32_t mBitmapsCount;
100         uint16_t mZeroPageIndex;
101         // Whether the memory is mapped (BufferReader::map()) or allocated
102         // (malloc()).
103         uint16_t mIsMapped;
104         // mArray packs two arrays:
105         // element mBitmaps[mBitmapsCount];
106         // uint16_t mIndices[mIndicesCount];
107         __attribute__((aligned(4))) uint32_t mArray[];
bitmapsMappableData108         const element* bitmaps() const { return mArray; }
bitmapsMappableData109         element* bitmaps() { return mArray; }
indicesMappableData110         const uint16_t* indices() const {
111             return reinterpret_cast<const uint16_t*>(mArray + mBitmapsCount);
112         }
indicesMappableData113         uint16_t* indices() { return reinterpret_cast<uint16_t*>(mArray + mBitmapsCount); }
sizeMappableData114         size_t size() const { return calcSize(mIndicesCount, mBitmapsCount); }
calcSizeMappableData115         static size_t calcSize(uint32_t indicesCount, uint32_t bitmapsCount) {
116             static_assert(std::is_same<element, uint32_t>::value);
117             static_assert(sizeof(uint32_t) == 4);
118             static_assert(sizeof(uint16_t) == 2);
119             // Round-up indicesCount / 2
120             size_t arrayCount = bitmapsCount + (indicesCount + 1) / 2;
121             return offsetof(MappableData, mArray) + sizeof(uint32_t) * arrayCount;
122         }
123         static MappableData* allocate(uint32_t indicesCount, uint32_t bitmapsCount);
124     };
125 
126     // MappableDataDeleter does NOT call free() if the data is on a memory map.
127     class MappableDataDeleter {
128     public:
operator()129         void operator()(const MappableData* data) const {
130             if (data != nullptr && !data->mIsMapped) free((void*)data);
131         }
132     };
133 
134     std::unique_ptr<const MappableData, MappableDataDeleter> mData;
135 
136     // Forbid copy and assign.
137     SparseBitSet(const SparseBitSet&) = delete;
138     SparseBitSet& operator=(const SparseBitSet&) = delete;
139 };
140 
141 }  // namespace minikin
142 
143 #endif  // MINIKIN_SPARSE_BIT_SET_H
144