libs/minikin/SparseBitSet.cpp

/*
 * Copyright (C) 2012 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "minikin/SparseBitSet.h"

#include "MinikinInternal.h"

namespace minikin {

const uint32_t SparseBitSet::kNotFound;

uint32_t SparseBitSet::calcNumPages(const uint32_t* ranges, size_t nRanges) {
    bool haveZeroPage = false;
    uint32_t nonzeroPageEnd = 0;
    uint32_t nPages = 0;
    for (size_t i = 0; i < nRanges; i++) {
        uint32_t start = ranges[i * 2];
        uint32_t end = ranges[i * 2 + 1];
        uint32_t startPage = start >> kLogValuesPerPage;
        uint32_t endPage = (end - 1) >> kLogValuesPerPage;
        if (startPage >= nonzeroPageEnd) {
            if (startPage > nonzeroPageEnd) {
                if (!haveZeroPage) {
                    haveZeroPage = true;
                    nPages++;
                }
            }
            nPages++;
        }
        nPages += endPage - startPage;
        nonzeroPageEnd = endPage + 1;
    }
    return nPages;
}

void SparseBitSet::initFromRanges(const uint32_t* ranges, size_t nRanges) {
    if (nRanges == 0) {
        return;
    }
    const uint32_t maxVal = ranges[nRanges * 2 - 1];
    if (maxVal >= kMaximumCapacity) {
        return;
    }
    uint32_t indicesCount = (maxVal + kPageMask) >> kLogValuesPerPage;
    uint32_t nPages = calcNumPages(ranges, nRanges);
    uint32_t bitmapsCount = nPages << (kLogValuesPerPage - kLogBitsPerEl);
    MappableData* data = MappableData::allocate(indicesCount, bitmapsCount);
    mData.reset(data);
    data->mMaxVal = maxVal;
    uint16_t* indices = data->indices();
    element* bitmaps = data->bitmaps();
    memset(bitmaps, 0, sizeof(uint32_t) * bitmapsCount);
    data->mZeroPageIndex = noZeroPage;
    uint32_t nonzeroPageEnd = 0;
    uint32_t currentPage = 0;
    for (size_t i = 0; i < nRanges; i++) {
        uint32_t start = ranges[i * 2];
        uint32_t end = ranges[i * 2 + 1];
        MINIKIN_ASSERT(start <= end, "Range size must be nonnegative");
        uint32_t startPage = start >> kLogValuesPerPage;
        uint32_t endPage = (end - 1) >> kLogValuesPerPage;
        if (startPage >= nonzeroPageEnd) {
            if (startPage > nonzeroPageEnd) {
                if (data->mZeroPageIndex == noZeroPage) {
                    data->mZeroPageIndex = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
                }
                for (uint32_t j = nonzeroPageEnd; j < startPage; j++) {
                    indices[j] = data->mZeroPageIndex;
                }
            }
            indices[startPage] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
        }

        size_t index = ((currentPage - 1) << (kLogValuesPerPage - kLogBitsPerEl)) +
                       ((start & kPageMask) >> kLogBitsPerEl);
        size_t nElements = (end - (start & ~kElMask) + kElMask) >> kLogBitsPerEl;
        if (nElements == 1) {
            bitmaps[index] |=
                    (kElAllOnes >> (start & kElMask)) & (kElAllOnes << ((~end + 1) & kElMask));
        } else {
            bitmaps[index] |= kElAllOnes >> (start & kElMask);
            for (size_t j = 1; j < nElements - 1; j++) {
                bitmaps[index + j] = kElAllOnes;
            }
            bitmaps[index + nElements - 1] |= kElAllOnes << ((~end + 1) & kElMask);
        }
        for (size_t j = startPage + 1; j < endPage + 1; j++) {
            indices[j] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
        }
        nonzeroPageEnd = endPage + 1;
    }
}

void SparseBitSet::initFromBuffer(BufferReader* reader) {
    uint32_t size = reader->read<uint32_t>();
    if (size == 0) return;
    mData.reset(reader->map<MappableData, alignof(MappableData)>(size));
}

void SparseBitSet::writeTo(BufferWriter* writer) const {
    if (mData == nullptr) {
        // Write 0 for empty SparseBitSet.
        writer->write<uint32_t>(0);
        return;
    }
    size_t size = mData->size();
    writer->write<uint32_t>(size);
    static_assert(alignof(MappableData) == 4);
    MappableData* out = writer->reserve<MappableData, alignof(MappableData)>(size);
    if (out != nullptr) {
        memcpy(out, mData.get(), size);
        out->mIsMapped = 1;
    }
}

int SparseBitSet::CountLeadingZeros(element x) {
    // Note: GCC / clang builtin
    return sizeof(element) <= sizeof(int) ? __builtin_clz(x) : __builtin_clzl(x);
}

uint32_t SparseBitSet::nextSetBit(uint32_t fromIndex) const {
    if (mData == nullptr || fromIndex >= mData->mMaxVal) {
        return kNotFound;
    }
    uint32_t fromPage = fromIndex >> kLogValuesPerPage;
    const element* bitmap = mData->bitmaps() + mData->indices()[fromPage];
    uint32_t offset = (fromIndex & kPageMask) >> kLogBitsPerEl;
    element e = bitmap[offset] & (kElAllOnes >> (fromIndex & kElMask));
    if (e != 0) {
        return (fromIndex & ~kElMask) + CountLeadingZeros(e);
    }
    for (uint32_t j = offset + 1; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) {
        e = bitmap[j];
        if (e != 0) {
            return (fromIndex & ~kPageMask) + (j << kLogBitsPerEl) + CountLeadingZeros(e);
        }
    }
    uint32_t maxPage = (mData->mMaxVal + kPageMask) >> kLogValuesPerPage;
    for (uint32_t page = fromPage + 1; page < maxPage; page++) {
        uint16_t index = mData->indices()[page];
        if (index == mData->mZeroPageIndex) {
            continue;
        }
        bitmap = mData->bitmaps() + index;
        for (uint32_t j = 0; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) {
            e = bitmap[j];
            if (e != 0) {
                return (page << kLogValuesPerPage) + (j << kLogBitsPerEl) + CountLeadingZeros(e);
            }
        }
    }
    return kNotFound;
}

// static
SparseBitSet::MappableData* SparseBitSet::MappableData::allocate(uint32_t indicesCount,
                                                                 uint32_t bitmapsCount) {
    MappableData* data = reinterpret_cast<MappableData*>(
            malloc(MappableData::calcSize(indicesCount, bitmapsCount)));
    data->mIndicesCount = indicesCount;
    data->mBitmapsCount = bitmapsCount;
    data->mIsMapped = 0;
    return data;
}

}  // namespace minikin