Initial commit of Minikin library

This is the initial draft of Minikin, a library intended to perform text
layout functions. This version does basic weight selection and font runs
for scripts, and also has a simple renderer for drawing into bitmaps,
but is lacking measurement, line breaking, and a number of other
important features. It also lacks caching and other performance
refinements.

Change-Id: I789a2e47d11d71202dc84b4751b51a5e2cd9c451

1 files changed, 147 insertions, 0 deletions

diff --git a/libs/minikin/SparseBitSet.cpp b/libs/minikin/SparseBitSet.cpp
new file mode 100644
index 0000000..e0b3c1d
--- /dev/null
+++ b/libs/minikin/SparseBitSet.cpp
@@ -0,0 +1,147 @@
+/*
+ * 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 <stddef.h>
+#include <string.h>
+#include <minikin/SparseBitSet.h>
+
+namespace android {
+
+const uint32_t SparseBitSet::kNotFound;
+
+void SparseBitSet::clear() {
+    mMaxVal = 0;
+    mIndices.reset();
+    mBitmaps.reset();
+}
+
+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) {
+        mMaxVal = 0;
+        mIndices.reset();
+        mBitmaps.reset();
+        return;
+    }
+    mMaxVal = ranges[nRanges * 2 - 1];
+    size_t indexSize = (mMaxVal + kPageMask) >> kLogValuesPerPage;
+    mIndices.reset(new uint32_t[indexSize]);
+    uint32_t nPages = calcNumPages(ranges, nRanges);
+    mBitmaps.reset(new element[nPages << (kLogValuesPerPage - kLogBitsPerEl)]);
+    memset(mBitmaps.get(), 0, nPages << (kLogValuesPerPage - 3));
+    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];
+        uint32_t startPage = start >> kLogValuesPerPage;
+        uint32_t endPage = (end - 1) >> kLogValuesPerPage;
+        if (startPage >= nonzeroPageEnd) {
+            if (startPage > nonzeroPageEnd) {
+                if (mZeroPageIndex == noZeroPage) {
+                    mZeroPageIndex = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
+                }
+                for (uint32_t j = nonzeroPageEnd; j < startPage; j++) {
+                    mIndices[j] = mZeroPageIndex;
+                }
+            }
+            mIndices[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) {
+            mBitmaps[index] |= (kElAllOnes >> (start & kElMask)) &
+                (kElAllOnes << ((-end) & kElMask));
+        } else {
+            mBitmaps[index] |= kElAllOnes >> (start & kElMask);
+            for (size_t j = 1; j < nElements - 1; j++) {
+                mBitmaps[index + j] = kElAllOnes;
+            }
+            mBitmaps[index + nElements - 1] |= kElAllOnes << ((-end) & kElMask);
+        }
+        for (size_t j = startPage + 1; j < endPage + 1; j++) {
+            mIndices[j] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
+        }
+        nonzeroPageEnd = endPage + 1;
+    }
+}
+
+// Note: this implementation depends on GCC builtin, and also assumes 32-bit elements.
+int SparseBitSet::CountLeadingZeros(element x) {
+    return __builtin_clz(x);
+}
+
+uint32_t SparseBitSet::nextSetBit(uint32_t fromIndex) const {
+    if (fromIndex >= mMaxVal) {
+        return kNotFound;
+    }
+    uint32_t fromPage = fromIndex >> kLogValuesPerPage;
+    const element* bitmap = &mBitmaps[mIndices[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 = (mMaxVal + kPageMask) >> kLogValuesPerPage;
+    for (uint32_t page = fromPage + 1; page < maxPage; page++) {
+        uint32_t index = mIndices[page];
+        if (index == mZeroPageIndex) {
+            continue;
+        }
+        bitmap = &mBitmaps[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;
+}
+
+}  // namespace android