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

7 files changed, 481 insertions, 0 deletions

diff --git a/include/minikin/AnalyzeStyle.h b/include/minikin/AnalyzeStyle.h
new file mode 100644
index 0000000..2989477
--- /dev/null
+++ b/include/minikin/AnalyzeStyle.h
@@ -0,0 +1,26 @@
+/*
+ * Copyright (C) 2013 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.
+ */
+
+#ifndef MINIKIN_ANALYZE_STYLE_H
+#define MINIKIN_ANALYZE_STYLE_H
+
+namespace android {
+
+bool analyzeStyle(const uint8_t* os2_data, size_t os2_size, int* weight, bool* italic);
+
+}  // namespace android
+
+#endif  // MINIKIN_ANALYZE_STYLE_H
\ No newline at end of file
diff --git a/include/minikin/CmapCoverage.h b/include/minikin/CmapCoverage.h
new file mode 100644
index 0000000..7054e31
--- /dev/null
+++ b/include/minikin/CmapCoverage.h
@@ -0,0 +1,31 @@
+/*
+ * Copyright (C) 2013 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.
+ */
+
+#ifndef MINIKIN_CMAP_COVERAGE_H
+#define MINIKIN_CMAP_COVERAGE_H
+
+#include <minikin/SparseBitSet.h>
+
+namespace android {
+
+class CmapCoverage {
+public:
+    static bool getCoverage(SparseBitSet &coverage, const uint8_t* cmap_data, size_t cmap_size);
+};
+
+}  // namespace android
+
+#endif  // MINIKIN_CMAP_COVERAGE_H
diff --git a/include/minikin/CssParse.h b/include/minikin/CssParse.h
new file mode 100644
index 0000000..f79ba1f
--- /dev/null
+++ b/include/minikin/CssParse.h
@@ -0,0 +1,86 @@
+/*
+ * Copyright (C) 2013 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.
+ */
+
+#ifndef MINIKIN_CSS_PARSE_H
+#define MINIKIN_CSS_PARSE_H
+
+#include <map>
+#include <string>
+
+namespace android {
+
+enum CssTag {
+    unknown,
+    fontSize,
+    fontWeight,
+    fontStyle,
+    minikinHinting,
+};
+
+const std::string cssTagNames[] = {
+    "unknown",
+    "font-size",
+    "font-weight",
+    "font-style",
+    "-minikin-hinting",
+};
+
+class CssValue {
+public:
+    enum Type {
+        UNKNOWN,
+        FLOAT
+    };
+    enum Units {
+        SCALAR,
+        PERCENT,
+        PX,
+        EM
+    };
+    CssValue() : mType(UNKNOWN) { }
+    explicit CssValue(double v) :
+        mType(FLOAT), floatValue(v), mUnits(SCALAR) { }
+    Type getType() const { return mType; }
+    double getFloatValue() const { return floatValue; }
+    int getIntValue() const { return floatValue; }
+    std::string toString(CssTag tag) const;
+    void setFloatValue(double v) {
+        mType = FLOAT;
+        floatValue = v;
+    }
+private:
+    Type mType;
+    double floatValue;
+    Units mUnits;
+};
+
+class CssProperties {
+public:
+    bool parse(const std::string& str);
+    bool hasTag(CssTag tag) const;
+    CssValue value(CssTag tag) const;
+
+    // primarily for debugging
+    std::string toString() const;
+private:
+    // We'll use STL map for now but can replace it with something
+    // more efficient if needed
+    std::map<CssTag, CssValue> mMap;
+};
+
+}  // namespace android
+
+#endif  // MINIKIN_CSS_PARSE_H
\ No newline at end of file
diff --git a/include/minikin/FontCollection.h b/include/minikin/FontCollection.h
new file mode 100644
index 0000000..3aa2aca
--- /dev/null
+++ b/include/minikin/FontCollection.h
@@ -0,0 +1,90 @@
+/*
+ * Copyright (C) 2013 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.
+ */
+
+#ifndef MINIKIN_FONT_COLLECTION_H
+#define MINIKIN_FONT_COLLECTION_H
+
+#include <vector>
+
+#include <ft2build.h>
+#include FT_FREETYPE_H
+#include FT_TRUETYPE_TABLES_H
+
+#include "SparseBitSet.h"
+#include "FontFamily.h"
+
+namespace android {
+
+class FontCollection {
+public:
+    explicit FontCollection(const std::vector<FontFamily*>& typefaces);
+
+    ~FontCollection();
+
+    const FontFamily* getFamilyForChar(uint32_t ch) const;
+    class Run {
+    public:
+        // Do copy constructor, assignment, destructor so it can be used in vectors
+        Run() : font(NULL) { }
+        Run(const Run& other): font(other.font), start(other.start), end(other.end) {
+            if (font) FT_Reference_Face(font);
+        }
+        Run& operator=(const Run& other) {
+            if (other.font) FT_Reference_Face(other.font);
+            if (font) FT_Done_Face(font);
+            font = other.font;
+            start = other.start;
+            end = other.end;
+            return *this;
+        }
+        ~Run() { if (font) FT_Done_Face(font); }
+
+        FT_Face font;
+        int start;
+        int end;
+    };
+    void itemize(const uint16_t *string, size_t string_length, FontStyle style,
+            std::vector<Run>* result) const;
+    private:
+    static const int kLogCharsPerPage = 8;
+    static const int kPageMask = (1 << kLogCharsPerPage) - 1;
+
+    struct FontInstance {
+        SparseBitSet* mCoverage;
+        FontFamily* mFamily;
+    };
+
+    struct Range {
+        size_t start;
+        size_t end;
+    };
+
+    // Highest UTF-32 code point that can be mapped
+    uint32_t mMaxChar;
+
+    // This vector has ownership of the bitsets and typeface objects.
+    std::vector<FontInstance> mInstances;
+
+    // This vector contains pointers into mInstances
+    std::vector<const FontInstance*> mInstanceVec;
+
+    // These are offsets into mInstanceVec, one range per page
+    std::vector<Range> mRanges;
+};
+
+}  // namespace android
+
+#endif  // MINIKIN_FONT_COLLECTION_H
diff --git a/include/minikin/FontFamily.h b/include/minikin/FontFamily.h
new file mode 100644
index 0000000..01ea232
--- /dev/null
+++ b/include/minikin/FontFamily.h
@@ -0,0 +1,67 @@
+/*
+ * Copyright (C) 2013 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.
+ */
+
+#ifndef MINIKIN_FONT_FAMILY_H
+#define MINIKIN_FONT_FAMILY_H
+
+#include <vector>
+
+namespace android {
+
+// FontStyle represents all style information needed to select an actual font
+// from a collection. The implementation is packed into a single 32-bit word
+// so it can be efficiently copied, embedded in other objects, etc.
+class FontStyle {
+public:
+    FontStyle(int weight = 4, bool italic = false) {
+        bits = (weight & kWeightMask) | (italic ? kItalicMask : 0);
+    }
+    int getWeight() { return bits & kWeightMask; }
+    bool getItalic() { return (bits & kItalicMask) != 0; }
+    bool operator==(const FontStyle other) { return bits == other.bits; }
+    // TODO: language, variant
+private:
+    static const int kWeightMask = 0xf;
+    static const int kItalicMask = 16;
+    uint32_t bits;
+};
+
+class FontFamily {
+public:
+    // Add font to family, extracting style information from the font
+    bool addFont(FT_Face typeface);
+
+    void addFont(FT_Face typeface, FontStyle style);
+    FT_Face getClosestMatch(FontStyle style) const;
+
+    // API's for enumerating the fonts in a family. These don't guarantee any particular order
+    size_t getNumFonts() const;
+    FT_Face getFont(size_t index) const;
+    FontStyle getStyle(size_t index) const;
+private:
+    class Font {
+    public:
+        Font(FT_Face typeface, FontStyle style) :
+            typeface(typeface), style(style) { }
+        FT_Face typeface;
+        FontStyle style;
+    };
+    std::vector<Font> mFonts;
+};
+
+}  // namespace android
+
+#endif  // MINIKIN_FONT_FAMILY_H
diff --git a/include/minikin/Layout.h b/include/minikin/Layout.h
new file mode 100644
index 0000000..7a6c6cf
--- /dev/null
+++ b/include/minikin/Layout.h
@@ -0,0 +1,89 @@
+/*
+ * Copyright (C) 2013 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.
+ */
+
+#ifndef MINIKIN_LAYOUT_H
+#define MINIKIN_LAYOUT_H
+
+#include <ft2build.h>
+#include FT_FREETYPE_H
+
+#include <hb.h>
+
+#include <vector>
+
+#include <minikin/CssParse.h>
+#include <minikin/FontCollection.h>
+
+namespace android {
+
+// The Bitmap class is for debugging. We'll probably move it out
+// of here into a separate lightweight software rendering module
+// (optional, as we'd hope most clients would do their own)
+class Bitmap {
+public:
+    Bitmap(int width, int height);
+    ~Bitmap();
+    void writePnm(std::ofstream& o) const;
+    void drawGlyph(const FT_Bitmap& bitmap, int x, int y);
+private:
+    int width;
+    int height;
+    uint8_t* buf;
+};
+
+struct LayoutGlyph {
+    // index into mFaces and mHbFonts vectors. We could imagine
+    // moving this into a run length representation, because it's
+    // more efficient for long strings, and we'll probably need
+    // something like that for paint attributes (color, underline,
+    // fake b/i, etc), as having those per-glyph is bloated.
+    int font_ix;
+
+    unsigned int glyph_id;
+    float x;
+    float y;
+};
+
+class Layout {
+public:
+    void dump() const;
+    void setFontCollection(const FontCollection *collection);
+    void doLayout(const uint16_t* buf, size_t nchars);
+    void draw(Bitmap*, int x0, int y0) const;
+    void setProperties(const std::string css);
+
+    // This must be called before any invocations.
+	// TODO: probably have a factory instead
+    static void init();
+private:
+    // Find a face in the mFaces vector, or create a new entry
+    int findFace(FT_Face face);
+
+    CssProperties mProps;  // TODO: want spans
+    std::vector<LayoutGlyph> mGlyphs;
+
+    // In future, this will be some kind of mapping from the
+    // identifier used to represent font-family to a font collection.
+    // But for the time being, it should be ok to have just one
+    // per layout.
+    const FontCollection *mCollection;
+    std::vector<FT_Face> mFaces;
+    std::vector<hb_font_t *> mHbFonts;
+};
+
+}  // namespace android
+
+#endif  // MINIKIN_LAYOUT_H
diff --git a/include/minikin/SparseBitSet.h b/include/minikin/SparseBitSet.h
new file mode 100644
index 0000000..4004606
--- /dev/null
+++ b/include/minikin/SparseBitSet.h
@@ -0,0 +1,92 @@
+/*
+ * 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.
+ */
+
+#ifndef MINIKIN_SPARSE_BIT_SET_H
+#define MINIKIN_SPARSE_BIT_SET_H
+
+#include <stdint.h>
+#include <sys/types.h>
+#include "utils/UniquePtr.h"
+
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+// This is an implementation of a set of integers. It is optimized for
+// values that are somewhat sparse, in the ballpark of a maximum value
+// of thousands to millions. It is particularly efficient when there are
+// large gaps. The motivating example is Unicode coverage of a font, but
+// the abstraction itself is fully general.
+
+class SparseBitSet {
+public:
+    SparseBitSet(): mMaxVal(0) {
+    }
+
+    // Clear the set
+    void clear();
+
+    // Initialize the set to a new value, represented by ranges. For
+    // simplicity, these ranges are arranged as pairs of values,
+    // inclusive of start, exclusive of end, laid out in a uint32 array.
+    void initFromRanges(const uint32_t* ranges, size_t nRanges);
+
+    // Determine whether the value is included in the set
+    bool get(uint32_t ch) const {
+        if (ch >= mMaxVal) return false;
+        uint32_t *bitmap = &mBitmaps[mIndices[ch >> kLogValuesPerPage]];
+        uint32_t index = ch & kPageMask;
+        return (bitmap[index >> kLogBitsPerEl] & (kElFirst >> (index & kElMask))) != 0;
+    }
+
+    // One more than the maximum value in the set, or zero if empty
+    uint32_t length() const {
+        return mMaxVal;
+    }
+
+    // The next set bit starting at fromIndex, inclusive, or kNotFound
+    // if none exists.
+    uint32_t nextSetBit(uint32_t fromIndex) const;
+
+    static const uint32_t kNotFound = ~0u;
+
+private:
+    static const int kLogValuesPerPage = 8;
+    static const int kPageMask = (1 << kLogValuesPerPage) - 1;
+    static const int kLogBytesPerEl = 2;
+    static const int kLogBitsPerEl = kLogBytesPerEl + 3;
+    static const int kElMask = (1 << kLogBitsPerEl) - 1;
+    // invariant: sizeof(element) == (1 << kLogBytesPerEl)
+    typedef uint32_t element;
+    static const element kElAllOnes = ~((element)0);
+    static const element kElFirst = ((element)1) << kElMask;
+    static const uint32_t noZeroPage = ~0u;
+
+    static uint32_t calcNumPages(const uint32_t* ranges, size_t nRanges);
+    static int CountLeadingZeros(element x);
+
+    uint32_t mMaxVal;
+    UniquePtr<uint32_t[]> mIndices;
+    UniquePtr<element[]> mBitmaps;
+    uint32_t mZeroPageIndex;
+};
+
+// Note: this thing cannot be used in vectors yet. If that were important, we'd need to
+// make the copy constructor work, and probably set up move traits as well.
+
+}; // namespace android
+
+#endif // MINIKIN_SPARSE_BIT_SET_H