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

17 files changed, 1706 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
diff --git a/libs/minikin/AnalyzeStyle.cpp b/libs/minikin/AnalyzeStyle.cpp
new file mode 100644
index 0000000..0961645
--- /dev/null
+++ b/libs/minikin/AnalyzeStyle.cpp
@@ -0,0 +1,43 @@
+/*
+ * 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.
+ */
+
+#include <stdlib.h>
+#include <stdint.h>
+
+#include <minikin/AnalyzeStyle.h>
+
+namespace android {
+
+// should  we have a single FontAnalyzer class this stuff lives in, to avoid dup?
+static int32_t readU16(const uint8_t* data, size_t offset) {
+    return data[offset] << 8 | data[offset + 1];
+}
+
+bool analyzeStyle(const uint8_t* os2_data, size_t os2_size, int* weight, bool* italic) {
+    const size_t kUsWeightClassOffset = 4;
+    const size_t kFsSelectionOffset = 62;
+    const uint16_t kItalicFlag = (1 << 0);
+    if (os2_size < kFsSelectionOffset + 2) {
+        return false;
+    }
+    uint16_t weightClass = readU16(os2_data, kUsWeightClassOffset);
+    *weight = weightClass / 100;
+    uint16_t fsSelection = readU16(os2_data, kFsSelectionOffset);
+    *italic = (fsSelection & kItalicFlag) != 0;
+    return true;
+}
+
+}  // namespace android
diff --git a/libs/minikin/Android.mk b/libs/minikin/Android.mk
new file mode 100644
index 0000000..9795ad0
--- /dev/null
+++ b/libs/minikin/Android.mk
@@ -0,0 +1,43 @@
+# 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.
+
+LOCAL_PATH := $(call my-dir)
+
+include $(CLEAR_VARS)
+include external/stlport/libstlport.mk
+
+LOCAL_SRC_FILES := \
+    AnalyzeStyle.cpp \
+    CmapCoverage.cpp \
+    CssParse.cpp \
+    FontCollection.cpp \
+    FontFamily.cpp \
+    Layout.cpp \
+    SparseBitSet.cpp
+
+LOCAL_MODULE := libminikin
+
+LOCAL_C_INCLUDES += \
+    external/harfbuzz_ng/src \
+    external/freetype/include \
+    frameworks/minikin/include
+
+LOCAL_SHARED_LIBRARIES := \
+    libharfbuzz_ng \
+    libstlport
+
+LOCAL_STATIC_LIBARIES := \
+    libft2
+
+include $(BUILD_STATIC_LIBRARY)
diff --git a/libs/minikin/CmapCoverage.cpp b/libs/minikin/CmapCoverage.cpp
new file mode 100644
index 0000000..4156d69
--- /dev/null
+++ b/libs/minikin/CmapCoverage.cpp
@@ -0,0 +1,179 @@
+/*
+ * 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.
+ */
+
+// Determine coverage of font given its raw "cmap" OpenType table
+
+#ifdef PRINTF_DEBUG
+#include <stdio.h>
+#endif
+
+#include <vector>
+using std::vector;
+
+#include <minikin/SparseBitSet.h>
+#include <minikin/CmapCoverage.h>
+
+namespace android {
+
+// These could perhaps be optimized to use __builtin_bswap16 and friends.
+static uint32_t readU16(const uint8_t* data, size_t offset) {
+    return data[offset] << 8 | data[offset + 1];
+}
+
+static uint32_t readU32(const uint8_t* data, size_t offset) {
+    return data[offset] << 24 | data[offset + 1] << 16 | data[offset + 2] << 8 | data[offset + 3];
+}
+
+static void addRange(vector<uint32_t> &coverage, uint32_t start, uint32_t end) {
+#ifdef PRINTF_DEBUG
+    printf("adding range %d-%d\n", start, end);
+#endif
+    if (coverage.empty() || coverage.back() < start) {
+        coverage.push_back(start);
+        coverage.push_back(end);
+    } else {
+        coverage.back() = end;
+    }
+}
+
+// Get the coverage information out of a Format 12 subtable, storing it in the coverage vector
+static bool getCoverageFormat4(vector<uint32_t>& coverage, const uint8_t* data, size_t size) {
+    const size_t kSegCountOffset = 6;
+    const size_t kEndCountOffset = 14;
+    const size_t kHeaderSize = 16;
+    const size_t kSegmentSize = 8;  // total size of array elements for one segment
+    if (kEndCountOffset > size) {
+        return false;
+    }
+    size_t segCount = readU16(data, kSegCountOffset) >> 1;
+    if (kHeaderSize + segCount * kSegmentSize > size) {
+        return false;
+    }
+    for (size_t i = 0; i < segCount; i++) {
+        int end = readU16(data, kEndCountOffset + 2 * i);
+        int start = readU16(data, kHeaderSize + 2 * (segCount + i));
+        int rangeOffset = readU16(data, kHeaderSize + 2 * (3 * segCount + i));
+        if (rangeOffset == 0) {
+            int delta = readU16(data, kHeaderSize + 2 * (2 * segCount + i));
+            if (((end + delta) & 0xffff) > end - start) {
+                addRange(coverage, start, end + 1);
+            } else {
+                for (int j = start; j < end + 1; j++) {
+                    if (((j + delta) & 0xffff) != 0) {
+                        addRange(coverage, j, j + 1);
+                    }
+                }
+            }
+        } else {
+            for (int j = start; j < end + 1; j++) {
+                uint32_t actualRangeOffset = kHeaderSize + 6 * segCount + rangeOffset +
+                    (i + j - start) * 2;
+                if (actualRangeOffset + 2 > size) {
+                    return false;
+                }
+                int glyphId = readU16(data, actualRangeOffset);
+                if (glyphId != 0) {
+                    addRange(coverage, j, j + 1);
+                }
+            }
+        }
+    }
+    return true;
+}
+
+// Get the coverage information out of a Format 12 subtable, storing it in the coverage vector
+static bool getCoverageFormat12(vector<uint32_t>& coverage, const uint8_t* data, size_t size) {
+    const size_t kNGroupsOffset = 12;
+    const size_t kFirstGroupOffset = 16;
+    const size_t kGroupSize = 12;
+    const size_t kStartCharCodeOffset = 0;
+    const size_t kEndCharCodeOffset = 4;
+    if (kFirstGroupOffset > size) {
+        return false;
+    }
+    uint32_t nGroups = readU32(data, kNGroupsOffset);
+    if (kFirstGroupOffset + nGroups * kGroupSize > size) {
+        return false;
+    }
+    for (uint32_t i = 0; i < nGroups; i++) {
+        uint32_t groupOffset = kFirstGroupOffset + i * kGroupSize;
+        uint32_t start = readU32(data, groupOffset + kStartCharCodeOffset);
+        uint32_t end = readU32(data, groupOffset + kEndCharCodeOffset);
+        addRange(coverage, start, end + 1);  // file is inclusive, vector is exclusive
+    }
+    return true;
+}
+
+bool CmapCoverage::getCoverage(SparseBitSet& coverage, const uint8_t* cmap_data, size_t cmap_size) {
+    vector<uint32_t> coverageVec;
+    const size_t kHeaderSize = 4;
+    const size_t kNumTablesOffset = 2;
+    const size_t kTableSize = 8;
+    const size_t kPlatformIdOffset = 0;
+    const size_t kEncodingIdOffset = 2;
+    const size_t kOffsetOffset = 4;
+    const int kMicrosoftPlatformId = 3;
+    const int kUnicodeBmpEncodingId = 1;
+    const int kUnicodeUcs4EncodingId = 10;
+    if (kHeaderSize > cmap_size) {
+        return false;
+    }
+    int numTables = readU16(cmap_data, kNumTablesOffset);
+    if (kHeaderSize + numTables * kTableSize > cmap_size) {
+        return false;
+    }
+    int bestTable = -1;
+    for (int i = 0; i < numTables; i++) {
+        uint16_t platformId = readU16(cmap_data, kHeaderSize + i * kTableSize + kPlatformIdOffset);
+        uint16_t encodingId = readU16(cmap_data, kHeaderSize + i * kTableSize + kEncodingIdOffset);
+        if (platformId == kMicrosoftPlatformId && encodingId == kUnicodeUcs4EncodingId) {
+            bestTable = i;
+            break;
+        } else if (platformId == kMicrosoftPlatformId && encodingId == kUnicodeBmpEncodingId) {
+            bestTable = i;
+        }
+    }
+#ifdef PRINTF_DEBUG
+    printf("best table = %d\n", bestTable);
+#endif
+    if (bestTable < 0) {
+        return false;
+    }
+    uint32_t offset = readU32(cmap_data, kHeaderSize + bestTable * kTableSize + kOffsetOffset);
+    if (offset + 2 > cmap_size) {
+        return false;
+    }
+    uint16_t format = readU16(cmap_data, offset);
+    bool success = false;
+    const uint8_t* tableData = cmap_data + offset;
+    const size_t tableSize = cmap_size - offset;
+    if (format == 4) {
+        success = getCoverageFormat4(coverageVec, tableData, tableSize);
+    } else if (format == 12) {
+        success = getCoverageFormat12(coverageVec, tableData, tableSize);
+    }
+    if (success) {
+        coverage.initFromRanges(&coverageVec.front(), coverageVec.size() >> 1);
+    }
+#ifdef PRINTF_DEBUG
+    for (int i = 0; i < coverageVec.size(); i += 2) {
+        printf("%x:%x\n", coverageVec[i], coverageVec[i + 1]);
+    }
+#endif
+    return success;
+}
+
+}  // namespace android
diff --git a/libs/minikin/CssParse.cpp b/libs/minikin/CssParse.cpp
new file mode 100644
index 0000000..d4de23b
--- /dev/null
+++ b/libs/minikin/CssParse.cpp
@@ -0,0 +1,162 @@
+/*
+ * 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.
+ */
+
+#include <string>
+#include <cstdlib>
+#include <cstring>
+#include <cstdio> // for sprintf - for debugging
+
+#include <minikin/CssParse.h>
+
+using std::map;
+using std::pair;
+using std::string;
+
+namespace android {
+
+bool strEqC(const string str, size_t off, size_t len, const char* str2) {
+    if (len != strlen(str2)) return false;
+    return !memcmp(str.data() + off, str2, len);
+}
+
+CssTag parseTag(const string str, size_t off, size_t len) {
+    if (len == 0) return unknown;
+    char c = str[off];
+    if (c == 'f') {
+        if (strEqC(str, off, len, "font-size")) return fontSize;
+        if (strEqC(str, off, len, "font-weight")) return fontWeight;
+        if (strEqC(str, off, len, "font-style")) return fontStyle;
+    } else if (c == '-') {
+        if (strEqC(str, off, len, "-minikin-hinting")) return minikinHinting;
+    }
+    return unknown;
+}
+
+bool parseValue(const string str, size_t *off, size_t len, CssTag tag,
+        CssValue* v) {
+    const char* data = str.data();
+    char* endptr;
+    double fv = strtod(data + *off, &endptr);
+    if (endptr == data + *off) {
+        // No numeric value, try tag-specific idents
+        size_t end;
+        for (end = *off; end < len; end++) {
+            char c = data[end];
+            if (c != '-' && !(c >= 'a' && c <= 'z') &&
+                !(c >= '0' && c <= '9')) break;
+        }
+        size_t taglen = end - *off;
+        endptr += taglen;
+        if (tag == fontStyle) {
+            if (strEqC(str, *off, taglen, "normal")) {
+                fv = 0;
+            } else if (strEqC(str, *off, taglen, "italic")) {
+                fv = 1;
+                // TODO: oblique, but who really cares?
+            } else {
+                return false;
+            }
+        } else if (tag == fontWeight) {
+            if (strEqC(str, *off, taglen, "normal")) {
+                fv = 400;
+            } else if (strEqC(str, *off, taglen, "bold")) {
+                fv = 700;
+            } else {
+                return false;
+            }
+        } else {
+            return false;
+        }
+    }
+    v->setFloatValue(fv);
+    *off = endptr - data;
+    return true;
+}
+
+string CssValue::toString(CssTag tag) const {
+    if (mType == FLOAT) {
+        if (tag == fontStyle) {
+            return floatValue ? "italic" : "normal";
+        }
+        char buf[64];
+        sprintf(buf, "%g", floatValue);
+        return string(buf);
+    }
+    return "";
+}
+
+bool CssProperties::parse(const string& str) {
+    size_t len = str.size();
+    size_t i = 0;
+    while (true) {
+        size_t j = i;
+        while (j < len && str[j] == ' ') j++;
+        if (j == len) break;
+        size_t k = str.find_first_of(':', j);
+        if (k == string::npos) {
+            return false;  // error: junk after end
+        }
+        CssTag tag = parseTag(str, j, k - j);
+#ifdef VERBOSE
+        printf("parseTag result %d, ijk %lu %lu %lu\n", tag, i, j, k);
+#endif
+        if (tag == unknown) return false; // error: unknown tag
+        k++;  // skip over colon
+        while (k < len && str[k] == ' ') k++;
+        if (k == len) return false; // error: missing value
+        CssValue v;
+        if (!parseValue(str, &k, len, tag, &v)) break;
+#ifdef VERBOSE
+        printf("parseValue ok\n");
+#endif
+        mMap.insert(pair<CssTag, CssValue>(tag, v));
+        while (k < len && str[k] == ' ') k++;
+        if (k < len) {
+            if (str[k] != ';') return false;
+            k++;
+        }
+        i = k;
+    }
+    return true;
+}
+
+bool CssProperties::hasTag(CssTag tag) const {
+    return (mMap.find(tag) != mMap.end());
+}
+
+CssValue CssProperties::value(CssTag tag) const {
+    map<CssTag, CssValue>::const_iterator it = mMap.find(tag);
+    if (it == mMap.end()) {
+        CssValue unknown;
+        return unknown;
+    } else {
+        return it->second;
+    }
+}
+
+string CssProperties::toString() const {
+    string result;
+    for (map<CssTag, CssValue>::const_iterator it = mMap.begin();
+        it != mMap.end(); it++) {
+        result += cssTagNames[it->first];
+        result += ": ";
+        result += it->second.toString(it->first);
+        result += ";\n";
+    }
+    return result;
+}
+
+}  // namespace android
diff --git a/libs/minikin/FontCollection.cpp b/libs/minikin/FontCollection.cpp
new file mode 100644
index 0000000..7abbd3b
--- /dev/null
+++ b/libs/minikin/FontCollection.cpp
@@ -0,0 +1,150 @@
+/*
+ * 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.
+ */
+
+#ifdef VERBOSE_DEBUG
+#include <stdio.h>  // for debugging - remove
+#endif
+
+#include <minikin/CmapCoverage.h>
+#include <minikin/FontCollection.h>
+
+using std::vector;
+
+namespace android {
+
+template <typename T>
+static inline T max(T a, T b) {
+    return a>b ? a : b;
+}
+
+FontCollection::FontCollection(const vector<FontFamily*>& typefaces) :
+    mMaxChar(0) {
+    vector<uint32_t> lastChar;
+    size_t nTypefaces = typefaces.size();
+#ifdef VERBOSE_DEBUG
+    printf("nTypefaces = %d\n", nTypefaces);
+#endif
+    const FontStyle defaultStyle;
+    for (size_t i = 0; i < nTypefaces; i++) {
+        FontFamily* family = typefaces[i];
+        FontInstance dummy;
+        mInstances.push_back(dummy);  // emplace_back would be better
+        FontInstance* instance = &mInstances.back();
+        instance->mFamily = family;
+        instance->mCoverage = new SparseBitSet;
+        FT_Face typeface = family->getClosestMatch(defaultStyle);
+#ifdef VERBOSE_DEBUG
+        printf("closest match = %x, family size = %d\n", typeface, family->getNumFonts());
+#endif
+        const uint32_t cmapTag = FT_MAKE_TAG('c', 'm', 'a', 'p');
+        FT_ULong cmapSize = 0;
+        FT_Error error = FT_Load_Sfnt_Table(typeface, cmapTag, 0, NULL, &cmapSize);
+        UniquePtr<uint8_t[]> cmapData(new uint8_t[cmapSize]);
+        error = FT_Load_Sfnt_Table(typeface, cmapTag, 0,
+            cmapData.get(), &cmapSize);
+        CmapCoverage::getCoverage(*instance->mCoverage, cmapData.get(), cmapSize);
+#ifdef VERBOSE_DEBUG
+        printf("font coverage length=%d, first ch=%x\n", instance->mCoverage->length(),
+                instance->mCoverage->nextSetBit(0));
+#endif
+        mMaxChar = max(mMaxChar, instance->mCoverage->length());
+        lastChar.push_back(instance->mCoverage->nextSetBit(0));
+        // TODO: should probably ref typeface here, hmm
+    }
+    size_t nPages = mMaxChar >> kLogCharsPerPage;
+    size_t offset = 0;
+    for (size_t i = 0; i < nPages; i++) {
+        Range dummy;
+        mRanges.push_back(dummy);
+        Range* range = &mRanges.back();
+#ifdef VERBOSE_DEBUG
+        printf("i=%d: range start = %d\n", i, offset);
+#endif
+        range->start = offset;
+        for (size_t j = 0; j < nTypefaces; j++) {
+            if (lastChar[j] < (i + 1) << kLogCharsPerPage) {
+                const FontInstance* instance = &mInstances[j];
+                mInstanceVec.push_back(instance);
+                offset++;
+                uint32_t nextChar = instance->mCoverage->nextSetBit((i + 1) << kLogCharsPerPage);
+#ifdef VERBOSE_DEBUG
+                printf("nextChar = %d (j = %d)\n", nextChar, j);
+#endif
+                lastChar[j] = nextChar;
+            }
+        }
+        range->end = offset;
+    }
+}
+
+FontCollection::~FontCollection() {
+    for (size_t i = 0; i < mInstances.size(); i++) {
+        delete mInstances[i].mCoverage;
+        // probably unref the typeface here too
+    }
+}
+
+const FontFamily* FontCollection::getFamilyForChar(uint32_t ch) const {
+    if (ch >= mMaxChar) {
+        return NULL;
+    }
+    const Range& range = mRanges[ch >> kLogCharsPerPage];
+#ifdef VERBOSE_DEBUG
+    printf("querying range %d:%d\n", range.start, range.end);
+#endif
+    for (size_t i = range.start; i < range.end; i++) {
+        const FontInstance* instance = mInstanceVec[i];
+        if (instance->mCoverage->get(ch)) {
+            return instance->mFamily;
+        }
+    }
+    return NULL;
+}
+
+void FontCollection::itemize(const uint16_t *string, size_t string_size, FontStyle style,
+        vector<Run>* result) const {
+    const FontFamily* lastFamily = NULL;
+    Run* run = NULL;
+    int nShorts;
+    for (size_t i = 0; i < string_size; i += nShorts) {
+        nShorts = 1;
+        uint32_t ch = string[i];
+        // sigh, decode UTF-16 by hand here
+        if ((ch & 0xfc00) == 0xd800) {
+            if ((i + 1) < string_size) {
+                ch = 0x10000 + ((ch & 0x3ff) << 10) + (string[i + 1] & 0x3ff);
+                nShorts = 2;
+            }
+        }
+        const FontFamily* family = getFamilyForChar(ch);
+        if (i == 0 || family != lastFamily) {
+            Run dummy;
+            result->push_back(dummy);
+            run = &result->back();
+            if (family == NULL) {
+                run->font = NULL;  // maybe we should do something different here
+            } else {
+                run->font = family->getClosestMatch(style);
+                FT_Reference_Face(run->font);
+            }
+            lastFamily = family;
+            run->start = i;
+        }
+        run->end = i + nShorts;
+    }
+}
+
+}  // namespace android
diff --git a/libs/minikin/FontFamily.cpp b/libs/minikin/FontFamily.cpp
new file mode 100644
index 0000000..dc6e16c
--- /dev/null
+++ b/libs/minikin/FontFamily.cpp
@@ -0,0 +1,95 @@
+/*
+ * 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.
+ */
+
+#define LOG_TAG "Minikin"
+
+#include <cutils/log.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <utils/UniquePtr.h>
+#include <ft2build.h>
+#include FT_FREETYPE_H
+#include FT_TRUETYPE_TABLES_H
+#include <minikin/AnalyzeStyle.h>
+#include <minikin/FontFamily.h>
+
+using std::vector;
+
+namespace android {
+
+bool FontFamily::addFont(FT_Face typeface) {
+    const uint32_t os2Tag = FT_MAKE_TAG('O', 'S', '/', '2');
+    FT_ULong os2Size = 0;
+    FT_Error error = FT_Load_Sfnt_Table(typeface, os2Tag, 0, NULL, &os2Size);
+    if (error != 0) return false;
+    UniquePtr<uint8_t[]> os2Data(new uint8_t[os2Size]);
+    error = FT_Load_Sfnt_Table(typeface, os2Tag, 0, os2Data.get(), &os2Size);
+    if (error != 0) return false;
+    int weight;
+    bool italic;
+    if (analyzeStyle(os2Data.get(), os2Size, &weight, &italic)) {
+        //ALOGD("analyzed weight = %d, italic = %s", weight, italic ? "true" : "false");
+        FontStyle style(weight, italic);
+        addFont(typeface, style);
+        return true;
+    } else {
+        ALOGD("failed to analyze style");
+    }
+    return false;
+}
+
+void FontFamily::addFont(FT_Face typeface, FontStyle style) {
+    mFonts.push_back(Font(typeface, style));
+    ALOGD("added font, mFonts.size() = %d", mFonts.size());
+}
+
+// Compute a matching metric between two styles - 0 is an exact match
+int computeMatch(FontStyle style1, FontStyle style2) {
+    if (style1 == style2) return 0;
+    int score = abs(style1.getWeight() - style2.getWeight());
+    if (style1.getItalic() != style2.getItalic()) {
+        score += 2;
+    }
+    return score;
+}
+
+FT_Face FontFamily::getClosestMatch(FontStyle style) const {
+    const Font* bestFont = NULL;
+    int bestMatch = 0;
+    for (size_t i = 0; i < mFonts.size(); i++) {
+        const Font& font = mFonts[i];
+        int match = computeMatch(font.style, style);
+        if (i == 0 || match < bestMatch) {
+            bestFont = &font;
+            bestMatch = match;
+        }
+    }
+    return bestFont == NULL ? NULL : bestFont->typeface;
+}
+
+size_t FontFamily::getNumFonts() const {
+    return mFonts.size();
+}
+
+FT_Face FontFamily::getFont(size_t index) const {
+    return mFonts[index].typeface;
+}
+
+FontStyle FontFamily::getStyle(size_t index) const {
+    return mFonts[index].style;
+}
+
+}  // namespace android
diff --git a/libs/minikin/Layout.cpp b/libs/minikin/Layout.cpp
new file mode 100644
index 0000000..a8a596d
--- /dev/null
+++ b/libs/minikin/Layout.cpp
@@ -0,0 +1,264 @@
+/*
+ * 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.
+ */
+
+#include <string>
+#include <vector>
+#include <fstream>
+#include <iostream>  // for debugging
+
+#include <minikin/Layout.h>
+
+using std::string;
+using std::vector;
+
+namespace android {
+
+// TODO: globals are not cool, move to a factory-ish object
+hb_buffer_t* buffer = 0;
+
+Bitmap::Bitmap(int width, int height) : width(width), height(height) {
+    buf = new uint8_t[width * height]();
+}
+
+Bitmap::~Bitmap() {
+    delete[] buf;
+}
+
+void Bitmap::writePnm(std::ofstream &o) const {
+    o << "P5" << std::endl;
+    o << width << " " << height << std::endl;
+    o << "255" << std::endl;
+    o.write((const char *)buf, width * height);
+    o.close();
+}
+
+void Bitmap::drawGlyph(const FT_Bitmap& bitmap, int x, int y) {
+    int bmw = bitmap.width;
+    int bmh = bitmap.rows;
+    int x0 = std::max(0, x);
+    int x1 = std::min(width, x + bmw);
+    int y0 = std::max(0, y);
+    int y1 = std::min(height, y + bmh);
+    const unsigned char* src = bitmap.buffer + (y0 - y) * bmw + (x0 - x);
+    uint8_t* dst = buf + y0 * width;
+    for (int yy = y0; yy < y1; yy++) {
+        for (int xx = x0; xx < x1; xx++) {
+            int pixel = (int)dst[xx] + (int)src[xx - x];
+            pixel = pixel > 0xff ? 0xff : pixel;
+            dst[xx] = pixel;
+        }
+        src += bmw;
+        dst += width;
+    }
+}
+
+void Layout::init() {
+    buffer = hb_buffer_create();
+}
+
+void Layout::setFontCollection(const FontCollection *collection) {
+    mCollection = collection;
+}
+
+hb_blob_t* referenceTable(hb_face_t* face, hb_tag_t tag, void* userData)  {
+    FT_Face ftFace = reinterpret_cast<FT_Face>(userData);
+    FT_ULong length = 0;
+    FT_Error error = FT_Load_Sfnt_Table(ftFace, tag, 0, NULL, &length);
+    if (error) {
+        return 0;
+    }
+    char *buffer = reinterpret_cast<char*>(malloc(length));
+    if (!buffer) {
+        return 0;
+    }
+    error = FT_Load_Sfnt_Table(ftFace, tag, 0,
+        reinterpret_cast<FT_Byte*>(buffer), &length);
+    if (error) {
+        free(buffer);
+        return 0;
+    }
+    return hb_blob_create(const_cast<char*>(buffer), length,
+        HB_MEMORY_MODE_WRITABLE, buffer, free);
+}
+
+static hb_bool_t harfbuzzGetGlyph(hb_font_t* hbFont, void* fontData, hb_codepoint_t unicode, hb_codepoint_t variationSelector, hb_codepoint_t* glyph, void* userData)
+{
+    FT_Face ftFace = reinterpret_cast<FT_Face>(fontData);
+    FT_UInt glyph_index = FT_Get_Char_Index(ftFace, unicode);
+    *glyph = glyph_index;
+    return !!*glyph;
+}
+
+static hb_position_t ft_pos_to_hb(FT_Pos pos) {
+    return pos << 2;
+}
+
+static hb_position_t harfbuzzGetGlyphHorizontalAdvance(hb_font_t* hbFont, void* fontData, hb_codepoint_t glyph, void* userData)
+{
+    FT_Face ftFace = reinterpret_cast<FT_Face>(fontData);
+    hb_position_t advance = 0;
+
+    FT_Load_Glyph(ftFace, glyph, FT_LOAD_DEFAULT);
+    return ft_pos_to_hb(ftFace->glyph->advance.x);
+}
+
+static hb_bool_t harfbuzzGetGlyphHorizontalOrigin(hb_font_t* hbFont, void* fontData, hb_codepoint_t glyph, hb_position_t* x, hb_position_t* y, void* userData)
+{
+    // Just return true, following the way that Harfbuzz-FreeType
+    // implementation does.
+    return true;
+}
+
+hb_font_funcs_t* getHbFontFuncs() {
+    static hb_font_funcs_t* hbFontFuncs = 0;
+
+    if (hbFontFuncs == 0) {
+        hbFontFuncs = hb_font_funcs_create();
+        hb_font_funcs_set_glyph_func(hbFontFuncs, harfbuzzGetGlyph, 0, 0);
+        hb_font_funcs_set_glyph_h_advance_func(hbFontFuncs, harfbuzzGetGlyphHorizontalAdvance, 0, 0);
+        hb_font_funcs_set_glyph_h_origin_func(hbFontFuncs, harfbuzzGetGlyphHorizontalOrigin, 0, 0);
+        hb_font_funcs_make_immutable(hbFontFuncs);
+    }
+    return hbFontFuncs;
+}
+
+hb_font_t* create_hb_font(FT_Face ftFace) {
+    hb_face_t* face = hb_face_create_for_tables(referenceTable, ftFace, NULL);
+    hb_font_t* font = hb_font_create(face);
+    hb_font_set_funcs(font, getHbFontFuncs(), ftFace, 0);
+    // TODO: manage ownership of face
+    return font;
+}
+
+static float HBFixedToFloat(hb_position_t v)
+{
+    return scalbnf (v, -8);
+}
+
+static hb_position_t HBFloatToFixed(float v)
+{
+    return scalbnf (v, +8);
+}
+
+void Layout::dump() const {
+    for (size_t i = 0; i < mGlyphs.size(); i++) {
+        const LayoutGlyph& glyph = mGlyphs[i];
+        std::cout << glyph.glyph_id << ": " << glyph.x << ", " << glyph.y << std::endl;
+    }
+}
+
+// A couple of things probably need to change:
+// 1. Deal with multiple sizes in a layout
+// 2. We'll probably store FT_Face as primary and then use a cache
+// for the hb fonts
+int Layout::findFace(FT_Face face) {
+    unsigned int ix;
+    for (ix = 0; ix < mFaces.size(); ix++) {
+        if (mFaces[ix] == face) {
+            return ix;
+        }
+    }
+    double size = mProps.value(fontSize).getFloatValue();
+    FT_Error error = FT_Set_Pixel_Sizes(face, 0, size);
+    mFaces.push_back(face);
+    hb_font_t *font = create_hb_font(face);
+    hb_font_set_ppem(font, size, size);
+    hb_font_set_scale(font, HBFloatToFixed(size), HBFloatToFixed(size));
+    mHbFonts.push_back(font);
+    return ix;
+}
+
+static FontStyle styleFromCss(const CssProperties &props) {
+    int weight = 4;
+    if (props.hasTag(fontWeight)) {
+        weight = props.value(fontWeight).getIntValue() / 100;
+    }
+    bool italic = false;
+    if (props.hasTag(fontStyle)) {
+        italic = props.value(fontStyle).getIntValue() != 0;
+    }
+    // TODO: italic property from CSS
+    return FontStyle(weight, italic);
+}
+
+// TODO: API should probably take context
+void Layout::doLayout(const uint16_t* buf, size_t nchars) {
+    FT_Error error;
+
+    vector<FontCollection::Run> items;
+    FontStyle style = styleFromCss(mProps);
+    mCollection->itemize(buf, nchars, style, &items);
+
+    mGlyphs.clear();
+    mFaces.clear();
+    mHbFonts.clear();
+    float x = 0;
+    float y = 0;
+    for (size_t run_ix = 0; run_ix < items.size(); run_ix++) {
+        FontCollection::Run &run = items[run_ix];
+        int font_ix = findFace(run.font);
+        hb_font_t *hbFont = mHbFonts[font_ix];
+#ifdef VERBOSE
+        std::cout << "Run " << run_ix << ", font " << font_ix <<
+            " [" << run.start << ":" << run.end << "]" << std::endl;
+#endif
+
+        hb_buffer_reset(buffer);
+        hb_buffer_set_direction(buffer, HB_DIRECTION_LTR);
+        hb_buffer_add_utf16(buffer, buf, nchars, run.start, run.end - run.start);
+        hb_shape(hbFont, buffer, NULL, 0);
+        unsigned int numGlyphs;
+        hb_glyph_info_t *info = hb_buffer_get_glyph_infos(buffer, &numGlyphs);
+        hb_glyph_position_t *positions = hb_buffer_get_glyph_positions(buffer, NULL);
+        for (unsigned int i = 0; i < numGlyphs; i++) {
+#ifdef VERBOSE
+            std::cout << positions[i].x_advance << " " << positions[i].y_advance << " " << positions[i].x_offset << " " << positions[i].y_offset << std::endl;            std::cout << "DoLayout " << info[i].codepoint <<
+            ": " << HBFixedToFloat(positions[i].x_advance) << "; " << positions[i].x_offset << ", " << positions[i].y_offset << std::endl;
+#endif
+            hb_codepoint_t glyph_ix = info[i].codepoint;
+            float xoff = HBFixedToFloat(positions[i].x_offset);
+            float yoff = HBFixedToFloat(positions[i].y_offset);
+            LayoutGlyph glyph = {font_ix, glyph_ix, x + xoff, y + yoff};
+            mGlyphs.push_back(glyph);
+            x += HBFixedToFloat(positions[i].x_advance);
+        }
+    }
+}
+
+void Layout::draw(Bitmap* surface, int x0, int y0) const {
+    FT_Error error;
+    FT_Int32 load_flags = FT_LOAD_DEFAULT;
+    if (mProps.hasTag(minikinHinting)) {
+        int hintflags = mProps.value(minikinHinting).getIntValue();
+        if (hintflags & 1) load_flags |= FT_LOAD_NO_HINTING;
+        if (hintflags & 2) load_flags |= FT_LOAD_NO_AUTOHINT;
+    }
+    for (size_t i = 0; i < mGlyphs.size(); i++) {
+        const LayoutGlyph& glyph = mGlyphs[i];
+        FT_Face face = mFaces[glyph.font_ix];
+        error = FT_Load_Glyph(face, glyph.glyph_id, load_flags);
+        error = FT_Render_Glyph(face->glyph, FT_RENDER_MODE_NORMAL);
+        surface->drawGlyph(face->glyph->bitmap,
+            x0 + int(floor(glyph.x + 0.5)) + face->glyph->bitmap_left,
+            y0 + int(floor(glyph.y + 0.5)) - face->glyph->bitmap_top);
+    }
+}
+
+void Layout::setProperties(string css) {
+    mProps.parse(css);
+}
+
+}  // namespace android
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
diff --git a/sample/Android.mk b/sample/Android.mk
new file mode 100644
index 0000000..335e7ce
--- /dev/null
+++ b/sample/Android.mk
@@ -0,0 +1,42 @@
+# 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.
+
+LOCAL_PATH:= $(call my-dir)
+
+include $(CLEAR_VARS)
+include external/stlport/libstlport.mk
+
+LOCAL_MODULE_TAGS := tests
+
+LOCAL_C_INCLUDES += \
+	external/harfbuzz_ng/src \
+	external/freetype/include \
+	external/icu4c/common \
+	frameworks/minikin/include
+
+LOCAL_SRC_FILES:= example.cpp
+
+LOCAL_SHARED_LIBRARIES += \
+	libutils \
+	liblog \
+	libcutils \
+	libstlport \
+	libharfbuzz_ng \
+	libicuuc
+
+LOCAL_STATIC_LIBRARIES += libminikin libft2
+
+LOCAL_MODULE:= minikin_example
+
+include $(BUILD_EXECUTABLE)
diff --git a/sample/example.cpp b/sample/example.cpp
new file mode 100644
index 0000000..3f0ad9d
--- /dev/null
+++ b/sample/example.cpp
@@ -0,0 +1,100 @@
+/*
+ * 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.
+ */
+
+// This is a test program that uses Minikin to layout and draw some text.
+// At the moment, it just draws a string into /data/local/tmp/foo.pgm.
+
+#include <stdio.h>
+#include <vector>
+#include <fstream>
+
+#include <unicode/unistr.h>
+#include <unicode/utf16.h>
+
+#include <minikin/Layout.h>
+
+using std::vector;
+
+namespace android {
+
+FT_Library library;  // TODO: this should not be a global
+
+FontCollection *makeFontCollection() {
+    vector<FontFamily *>typefaces;
+    const char *fns[] = {
+        "/system/fonts/Roboto-Regular.ttf",
+        "/system/fonts/Roboto-Italic.ttf",
+        "/system/fonts/Roboto-BoldItalic.ttf",
+        "/system/fonts/Roboto-Light.ttf",
+        "/system/fonts/Roboto-Thin.ttf",
+        "/system/fonts/Roboto-Bold.ttf",
+        "/system/fonts/Roboto-ThinItalic.ttf",
+        "/system/fonts/Roboto-LightItalic.ttf"
+    };
+
+    FontFamily *family = new FontFamily();
+    FT_Face face;
+    FT_Error error;
+    for (size_t i = 0; i < sizeof(fns)/sizeof(fns[0]); i++) {
+        const char *fn = fns[i];
+        printf("adding %s\n", fn);
+        error = FT_New_Face(library, fn, 0, &face);
+        if (error != 0) {
+            printf("error loading %s, %d\n", fn, error);
+        }
+        family->addFont(face);
+    }
+    typefaces.push_back(family);
+
+#if 0
+    family = new FontFamily();
+    const char *fn = "/system/fonts/DroidSansDevanagari-Regular.ttf";
+    error = FT_New_Face(library, fn, 0, &face);
+    family->addFont(face);
+    typefaces.push_back(family);
+#endif
+
+    return new FontCollection(typefaces);
+}
+
+int runMinikinTest() {
+    FT_Error error = FT_Init_FreeType(&library);
+    if (error) {
+        return -1;
+    }
+    Layout::init();
+
+    FontCollection *collection = makeFontCollection();
+    Layout layout;
+    layout.setFontCollection(collection);
+    layout.setProperties("font-size: 32;");
+    const char *text = "hello world";
+    icu::UnicodeString icuText = icu::UnicodeString::fromUTF8(text);
+    layout.doLayout(icuText.getBuffer(), icuText.length());
+    layout.dump();
+    Bitmap bitmap(200, 50);
+    layout.draw(&bitmap, 10, 40);
+    std::ofstream o;
+    o.open("/data/local/tmp/foo.pgm", std::ios::out | std::ios::binary);
+    bitmap.writePnm(o);
+    return 0;
+}
+
+}
+
+int main(int argc, const char** argv) {
+    return android::runMinikinTest();
+}
\ No newline at end of file