Merge branch 'master' into libuv010

Conflicts:
	setup-libraries.sh

29 files changed, 450 insertions, 582 deletions

diff --git a/common/platform_default.cpp b/common/platform_default.cpp
new file mode 100644
index 0000000000..1acbfa8508
--- /dev/null
+++ b/common/platform_default.cpp
@@ -0,0 +1,25 @@
+#include <mbgl/platform/platform.hpp>
+
+#include <locale>
+
+namespace mbgl {
+namespace platform {
+
+std::string uppercase(const std::string& string) {
+    // TODO: Use a proper Unicode Special Casing-aware algorithm.
+    const auto &convert = std::use_facet<std::ctype<char>>(std::locale());
+    std::string converted = string;
+    convert.toupper(&converted[0], &converted[0] + converted.size());
+    return converted;
+}
+
+std::string lowercase(const std::string& string) {
+    // TODO: Use a proper Unicode Special Casing-aware algorithm.
+    const auto &convert = std::use_facet<std::ctype<char>>(std::locale());
+    std::string converted = string;
+    convert.tolower(&converted[0], &converted[0] + converted.size());
+    return converted;
+}
+
+}
+}
diff --git a/common/platform_nsstring.mm b/common/platform_nsstring.mm
new file mode 100644
index 0000000000..9119f2a8fe
--- /dev/null
+++ b/common/platform_nsstring.mm
@@ -0,0 +1,21 @@
+#import <Foundation/Foundation.h>
+
+#include <mbgl/platform/platform.hpp>
+
+namespace mbgl {
+namespace platform {
+
+std::string uppercase(const std::string &string) {
+    NSString *nsstring = [[NSString alloc] initWithBytesNoCopy:const_cast<char *>(string.data()) length:string.size() encoding:NSUTF8StringEncoding freeWhenDone:NO];
+    nsstring = [nsstring uppercaseString];
+    return { [nsstring cStringUsingEncoding:NSUTF8StringEncoding], [nsstring lengthOfBytesUsingEncoding:NSUTF8StringEncoding] };
+}
+
+std::string lowercase(const std::string &string) {
+    NSString *nsstring = [[NSString alloc] initWithBytesNoCopy:const_cast<char *>(string.data()) length:string.size() encoding:NSUTF8StringEncoding freeWhenDone:NO];
+    nsstring = [nsstring lowercaseString];
+    return { [nsstring cStringUsingEncoding:NSUTF8StringEncoding], [nsstring lengthOfBytesUsingEncoding:NSUTF8StringEncoding] };
+}
+
+}
+}
\ No newline at end of file
diff --git a/include/mbgl/map/source.hpp b/include/mbgl/map/source.hpp
index 5b51268bfe..4bc4c86dd0 100644
--- a/include/mbgl/map/source.hpp
+++ b/include/mbgl/map/source.hpp
@@ -38,6 +38,7 @@ public:
     void finishRender(Painter &painter);
 
     std::forward_list<Tile::ID> getIDs() const;
+    std::forward_list<Tile *> getLoadedTiles() const;
     void updateClipIDs(const std::map<Tile::ID, ClipID> &mapping);
 
 private:
diff --git a/include/mbgl/map/tile.hpp b/include/mbgl/map/tile.hpp
index 9cf5ff5341..24845c81a0 100644
--- a/include/mbgl/map/tile.hpp
+++ b/include/mbgl/map/tile.hpp
@@ -18,11 +18,15 @@ namespace mbgl {
 class TileData;
 
 struct ClipID {
-    explicit ClipID() {}
-    explicit ClipID(const std::bitset<8> &mask, uint8_t length) : mask(mask), length(length) {}
-    explicit ClipID(const std::string &mask, uint8_t length) : mask(mask), length(length) {}
+    inline ClipID() {}
+    inline ClipID(const std::string &mask_, const std::string &reference_) : mask(mask_), reference(reference_) {}
+
     std::bitset<8> mask;
-    uint8_t length = 0;
+    std::bitset<8> reference;
+
+    inline bool operator==(const ClipID &other) const {
+        return mask == other.mask && reference == other.reference;
+    }
 };
 
 class Tile : private util::noncopyable {
@@ -47,6 +51,10 @@ public:
             return w == rhs.w && z == rhs.z && x == rhs.x && y == rhs.y;
         }
 
+        inline bool operator!=(const ID& rhs) const {
+            return !operator==(rhs);
+        }
+
         inline bool operator<(const ID &rhs) const {
             if (w != rhs.w) return w < rhs.w;
             if (z != rhs.z) return z < rhs.z;
diff --git a/include/mbgl/map/tile_data.hpp b/include/mbgl/map/tile_data.hpp
index 3e639fcea1..9aaef84e04 100644
--- a/include/mbgl/map/tile_data.hpp
+++ b/include/mbgl/map/tile_data.hpp
@@ -49,6 +49,10 @@ public:
     void reparse();
     const std::string toString() const;
 
+    inline bool ready() const {
+        return state == State::parsed;
+    }
+
     // Override this in the child class.
     virtual void beforeParse();
     virtual void parse() = 0;
diff --git a/include/mbgl/platform/platform.hpp b/include/mbgl/platform/platform.hpp
index 43c6ce4f5e..22405a4cfd 100644
--- a/include/mbgl/platform/platform.hpp
+++ b/include/mbgl/platform/platform.hpp
@@ -28,6 +28,12 @@ std::shared_ptr<Request> request_http(const std::string &url,
                                       std::function<void(Response *)> callback,
                                       std::shared_ptr<uv::loop> loop = nullptr);
 
+// Uppercase a string, potentially using platform-specific routines.
+std::string uppercase(const std::string &string);
+
+// Lowercase a string, potentially using platform-specific routines.
+std::string lowercase(const std::string &string);
+
 // Cancels an HTTP request.
 void cancel_request_http(const std::shared_ptr<Request> &req);
 
diff --git a/include/mbgl/text/collision.hpp b/include/mbgl/text/collision.hpp
index 7e65e979da..8eec30f216 100644
--- a/include/mbgl/text/collision.hpp
+++ b/include/mbgl/text/collision.hpp
@@ -5,8 +5,9 @@
 
 #pragma GCC diagnostic push
 #pragma GCC diagnostic ignored "-Wunused-parameter"
+#ifdef __clang__
 #pragma GCC diagnostic ignored "-Wdeprecated-register"
-#ifndef __clang__
+#else
 #pragma GCC diagnostic ignored "-Wunused-local-typedefs"
 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
 #endif
diff --git a/include/mbgl/text/types.hpp b/include/mbgl/text/types.hpp
index e2539bff62..dbb483ea8f 100644
--- a/include/mbgl/text/types.hpp
+++ b/include/mbgl/text/types.hpp
@@ -101,7 +101,7 @@ struct PlacementProperty {
         : zoom(zoom), rotationRange(rotationRange) {}
 
     inline operator bool() const {
-        return !isnan(zoom) && zoom != std::numeric_limits<float>::infinity() &&
+        return !std::isnan(zoom) && zoom != std::numeric_limits<float>::infinity() &&
                rotationRange[0] != rotationRange[1];
     }
 
diff --git a/include/mbgl/util/clip_ids.hpp b/include/mbgl/util/clip_ids.hpp
index 748d3d8f5f..5855b16af7 100644
--- a/include/mbgl/util/clip_ids.hpp
+++ b/include/mbgl/util/clip_ids.hpp
@@ -4,15 +4,34 @@
 #include <mbgl/map/tile.hpp>
 #include <list>
 #include <set>
+#include <vector>
+#include <forward_list>
 #include <map>
 
 namespace mbgl {
 
-static constexpr uint8_t clipMask[9] { 0x00, 0x80, 0xC0, 0xE0, 0xF0, 0xF8, 0xFC, 0xFE, 0xFF };
+class ClipIDGenerator {
+private:
+    struct Leaf {
+        Leaf(Tile &tile);
+        void add(const Tile::ID &p);
+        bool operator==(const Leaf &other) const;
 
-void updateClipIDs(const std::list<Tile *> &array);
+        Tile &tile;
+        std::forward_list<Tile::ID> children;
+    };
+
+    typedef std::vector<Leaf> Pool;
+    std::forward_list<Pool> pools;
+    uint8_t bit_offset = 0;
+
+private:
+    bool reuseExisting(Leaf &leaf);
+
+public:
+    void update(std::forward_list<Tile *> tiles);
+};
 
-std::map<Tile::ID, ClipID> computeClipIDs(std::forward_list<Tile::ID> array);
 
 }
 
diff --git a/include/mbgl/util/math.hpp b/include/mbgl/util/math.hpp
index fde2a4720b..2bef5b18e2 100644
--- a/include/mbgl/util/math.hpp
+++ b/include/mbgl/util/math.hpp
@@ -104,6 +104,10 @@ T smoothstep(T edge0, T edge1, T x) {
     return t * t * (T(3) - T(2) * t);
 }
 
+// Computes the log2(x) rounded up to the next integer.
+// (== number of bits required to store x)
+uint32_t ceil_log2(uint64_t x);
+
 }
 }
 
diff --git a/include/mbgl/util/threadpool.hpp b/include/mbgl/util/threadpool.hpp
deleted file mode 100644
index 497d4e3083..0000000000
--- a/include/mbgl/util/threadpool.hpp
+++ /dev/null
@@ -1,45 +0,0 @@
-#ifndef MBGL_UTIL_THREADPOOL
-#define MBGL_UTIL_THREADPOOL
-
-#include <pthread.h>
-#include <forward_list>
-#include <queue>
-
-namespace mbgl {
-namespace util {
-
-class Threadpool {
-private:
-    class Worker {
-    public:
-        Worker(Threadpool& pool);
-        ~Worker();
-        static void *loop(void *ptr);
-
-    private:
-        Threadpool& pool;
-        pthread_t thread;
-    };
-
-public:
-    Threadpool(int max_workers = 4);
-    typedef void (*Callback)(void *);
-    void add(Callback callback, void *data);
-
-private:
-    typedef std::pair<Callback, void *> Task;
-    const int max_workers;
-    pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
-    pthread_cond_t condition = PTHREAD_COND_INITIALIZER;
-    std::forward_list<Worker> workers;
-    int worker_count = 0;
-    std::queue<Task> tasks;
-};
-
-extern std::unique_ptr<Threadpool> threadpool;
-
-}
-}
-
-#endif
-
diff --git a/include/mbgl/util/utf.hpp b/include/mbgl/util/utf.hpp
index 5dfc4ad2d1..bb63179123 100644
--- a/include/mbgl/util/utf.hpp
+++ b/include/mbgl/util/utf.hpp
@@ -4,14 +4,13 @@
 #include <memory>
 
 // g++/libstdc++ is missing c++11 codecvt support
-#ifdef __linux__
+#if ! defined(__clang__) || defined(__linux__)
 #pragma GCC diagnostic push
-#ifndef __clang__
 #pragma GCC diagnostic ignored "-Wunused-local-typedefs"
-#endif
 #include <boost/locale.hpp>
 #pragma GCC diagnostic pop
 #else
+// Assume that codecvt is present on clang on non-linux systems
 #include <codecvt>
 #include <locale>
 #endif
@@ -20,7 +19,7 @@ namespace mbgl {
 
 namespace util {
 
-#ifdef __linux__
+#if ! defined(__clang__) || defined(__linux__)
 
 class utf8_to_utf32 {
  public:
diff --git a/include/mbgl/util/vec.hpp b/include/mbgl/util/vec.hpp
index 0b9bf63d53..a5fbee477b 100644
--- a/include/mbgl/util/vec.hpp
+++ b/include/mbgl/util/vec.hpp
@@ -71,7 +71,7 @@ struct vec2 {
 
     template<typename U = T, typename std::enable_if<std::numeric_limits<U>::has_quiet_NaN, int>::type = 0>
     inline operator bool() const {
-        return !isnan(x) && !isnan(y);
+        return !std::isnan(x) && !std::isnan(y);
     }
 
     template<typename U = T, typename std::enable_if<!std::numeric_limits<U>::has_quiet_NaN, int>::type = 0>
diff --git a/linux/mapboxgl-app.gyp b/linux/mapboxgl-app.gyp
index 7b703ed75c..e19768caf9 100644
--- a/linux/mapboxgl-app.gyp
+++ b/linux/mapboxgl-app.gyp
@@ -12,6 +12,7 @@
         './main.cpp',
         '../common/settings_json.cpp',
         '../common/settings_json.hpp',
+        '../common/platform_default.cpp',
         '../common/glfw_view.hpp',
         '../common/glfw_view.cpp',
         '../common/curl_request.cpp',
diff --git a/macosx/mapboxgl-app.gyp b/macosx/mapboxgl-app.gyp
index 480dc2a114..da5c68ea35 100644
--- a/macosx/mapboxgl-app.gyp
+++ b/macosx/mapboxgl-app.gyp
@@ -12,6 +12,7 @@
         './main.mm',
         '../common/settings_nsuserdefaults.hpp',
         '../common/settings_nsuserdefaults.mm',
+        '../common/platform_nsstring.mm',
         '../common/glfw_view.hpp',
         '../common/glfw_view.cpp',
         '../common/foundation_request.h',
diff --git a/scripts/travis_script.sh b/scripts/travis_script.sh
index 4f02c5b7e5..f8325e41cc 100755
--- a/scripts/travis_script.sh
+++ b/scripts/travis_script.sh
@@ -10,17 +10,19 @@ if [[ ${TRAVIS_OS_NAME} == "linux" ]]; then
     make linux -j4 BUILDTYPE=${BUILDTYPE}
     make test -j4 BUILDTYPE=${BUILDTYPE}
     ./scripts/run_tests.sh
-    (cd ./node_modules/mapbox-gl-test-suite/ && (./bin/compare_images.js || true; ./bin/deploy_results.sh))
+    (cd ./node_modules/mapbox-gl-test-suite/ && (./bin/compare_images.js || true; [[ $TRAVIS_PULL_REQUEST = "false" ]] && ./bin/deploy_results.sh))
+
 elif [[ ${TRAVIS_OS_NAME} == "osx" ]]; then
     #
     # build OS X
     #
     make xproj-cli
-    xcodebuild -project ./build/macosx/mapboxgl-app.xcodeproj
+    xcodebuild -project ./build/macosx/mapboxgl-app.xcodeproj -jobs 4
     #
     # build iOS
     #
-    git clone --depth 1 https://github.com/mapbox/mapbox-gl-cocoa ios/mapbox-gl-cocoa
+    git submodule init
+    git submodule update
     make iproj-cli
-    xcodebuild -project ./build/ios/mapbox-gl-cocoa/app/mapboxgl-app.xcodeproj -sdk iphonesimulator ONLY_ACTIVE_ARCH=NO
+    xcodebuild -project ./build/ios/mapbox-gl-cocoa/app/mapboxgl-app.xcodeproj -sdk iphonesimulator ONLY_ACTIVE_ARCH=NO -jobs 4
 fi
diff --git a/setup-libraries.sh b/setup-libraries.sh
index bcf318ae81..e442333f49 100755
--- a/setup-libraries.sh
+++ b/setup-libraries.sh
@@ -51,7 +51,8 @@ set -u
 NODE=$(which node)
 NPM=$(which npm)
 
-MP_HASH="c07b197"
+MP_HASH="e741a075d28812e5d16b581e1540248fe19c52ce"
+DIR_HASH=$(echo `pwd` | git hash-object --stdin)
 if [ ! -d 'mapnik-packaging/' ]; then
   git clone https://github.com/mapnik/mapnik-packaging.git
 fi
@@ -66,9 +67,9 @@ export CXX11=true
 if [ ${UNAME} = 'Darwin' ]; then
 
 if [ ! -z "${TRAVIS:-}" ]; then
-    if aws s3 cp s3://${AWS_S3_BUCKET}/dependencies/build-cpp11-libcpp-universal_${MP_HASH}.tar.gz ./out/ ; then
+    if aws s3 cp s3://${AWS_S3_BUCKET}/dependencies/build-cpp11-libcpp-universal_${MP_HASH}_${DIR_HASH}.tar.gz ./out/ ; then
         rm -rf out/build-cpp11-libcpp-universal
-        tar -xzf out/build-cpp11-libcpp-universal_${MP_HASH}.tar.gz
+        tar -xzf out/build-cpp11-libcpp-universal_${MP_HASH}_${DIR_HASH}.tar.gz
     fi
 fi
 
@@ -82,14 +83,14 @@ export LIBUV_VERSION=0.10.28
 
 source iPhoneOSs.sh
 export LIBUV_VERSION=0.10.28
-    if [ ! -f out/build-cpp11-libcpp-armv7s-iphoneos/lib/libpng.a ] ; then ./scripts/build_png.sh ; fi
-    if [ ! -f out/build-cpp11-libcpp-armv7s-iphoneos/lib/libuv.a ] ; then ./scripts/build_libuv.sh ; fi
+    if [ ! -f out/build-cpp11-libcpp-armv7s-iphoneoss/lib/libpng.a ] ; then ./scripts/build_png.sh ; fi
+    if [ ! -f out/build-cpp11-libcpp-armv7s-iphoneoss/lib/libuv.a ] ; then ./scripts/build_libuv.sh ; fi
     echo '     ...done'
 
 source iPhoneOS64.sh
 export LIBUV_VERSION=0.10.28
-    if [ ! -f out/build-cpp11-libcpp-arm64-iphoneos/lib/libpng.a ] ; then ./scripts/build_png.sh ; fi
-    if [ ! -f out/build-cpp11-libcpp-arm64-iphoneos/lib/libuv.a ] ; then ./scripts/build_libuv.sh ; fi
+    if [ ! -f out/build-cpp11-libcpp-arm64-iphoneos64/lib/libpng.a ] ; then ./scripts/build_png.sh ; fi
+    if [ ! -f out/build-cpp11-libcpp-arm64-iphoneos64/lib/libuv.a ] ; then ./scripts/build_libuv.sh ; fi
     echo '     ...done'
 
 source iPhoneSimulator.sh
@@ -117,9 +118,9 @@ export LIBUV_VERSION=0.10.28
 
 ./scripts/make_universal.sh
 
-if [ ! -z "${TRAVIS:-}" ]; then
-    tar -zcf out/build-cpp11-libcpp-universal_${MP_HASH}.tar.gz out/build-cpp11-libcpp-universal
-    aws s3 cp out/build-cpp11-libcpp-universal_${MP_HASH}.tar.gz s3://${AWS_S3_BUCKET}/dependencies/
+if [[ $TRAVIS_PULL_REQUEST = "false" ]]; then
+    tar -zcf out/build-cpp11-libcpp-universal_${MP_HASH}_${DIR_HASH}.tar.gz out/build-cpp11-libcpp-universal
+    aws s3 cp --acl public-read out/build-cpp11-libcpp-universal_${MP_HASH}_${DIR_HASH}.tar.gz s3://${AWS_S3_BUCKET}/dependencies/
 fi
 
 fi
@@ -149,10 +150,10 @@ export LIBUV_VERSION=0.10.28
     if [ ! -f out/build-cpp11-libstdcpp-gcc-x86_64-linux/lib/libcurl.a ] ; then ./scripts/build_curl.sh ; fi
     if [ ! -f out/build-cpp11-libstdcpp-gcc-x86_64-linux/lib/libboost_regex.a ] ; then ./scripts/build_boost.sh --with-regex ; fi
 
-if [ ! -z "${TRAVIS:-}" ]; then
+if [[ $TRAVIS_PULL_REQUEST = "false" ]]; then
     if ! tar --compare -zf out/build-cpp11-libstdcpp-gcc-x86_64-linux.tar.gz ; then
         tar -zcf out/build-cpp11-libstdcpp-gcc-x86_64-linux.tar.gz out/build-cpp11-libstdcpp-gcc-x86_64-linux
-        aws s3 cp out/build-cpp11-libstdcpp-gcc-x86_64-linux.tar.gz s3://${AWS_S3_BUCKET}/dependencies/
+        aws s3 cp --acl public-read out/build-cpp11-libstdcpp-gcc-x86_64-linux.tar.gz s3://${AWS_S3_BUCKET}/dependencies/
     fi
 fi
 
diff --git a/src/map/map.cpp b/src/map/map.cpp
index 8590b464bb..b657ab6890 100644
--- a/src/map/map.cpp
+++ b/src/map/map.cpp
@@ -511,18 +511,12 @@ void Map::updateTiles() {
 }
 
 void Map::updateRenderState() {
-    std::forward_list<Tile::ID> ids;
-
+    // Update all clipping IDs.
+    ClipIDGenerator generator;
     for (const std::shared_ptr<StyleSource> &source : getActiveSources()) {
-        ids.splice_after(ids.before_begin(), source->source->getIDs());
+        generator.update(source->source->getLoadedTiles());
         source->source->updateMatrices(painter.projMatrix, state);
     }
-
-    const std::map<Tile::ID, ClipID> clipIDs = computeClipIDs(ids);
-
-    for (const std::shared_ptr<StyleSource> &source : getActiveSources()) {
-        source->source->updateClipIDs(clipIDs);
-    }
 }
 
 void Map::prepare() {
diff --git a/src/map/source.cpp b/src/map/source.cpp
index b83384f25f..3fe5bf42fa 100644
--- a/src/map/source.cpp
+++ b/src/map/source.cpp
@@ -121,7 +121,6 @@ void Source::finishRender(Painter &painter) {
     }
 }
 
-
 std::forward_list<Tile::ID> Source::getIDs() const {
     std::forward_list<Tile::ID> ptrs;
 
@@ -132,6 +131,18 @@ std::forward_list<Tile::ID> Source::getIDs() const {
     return ptrs;
 }
 
+std::forward_list<Tile *> Source::getLoadedTiles() const {
+    std::forward_list<Tile *> ptrs;
+    auto it = ptrs.before_begin();
+    for (const auto &pair : tiles) {
+        if (pair.second->data->ready()) {
+            it = ptrs.insert_after(it, pair.second.get());
+        }
+    }
+    return ptrs;
+}
+
+
 TileData::State Source::hasTile(const Tile::ID& id) {
     auto it = tiles.find(id);
     if (it != tiles.end()) {
diff --git a/src/renderer/painter.cpp b/src/renderer/painter.cpp
index e813ad24eb..240aff6887 100644
--- a/src/renderer/painter.cpp
+++ b/src/renderer/painter.cpp
@@ -169,9 +169,9 @@ void Painter::setStrata(float value) {
 }
 
 void Painter::prepareTile(const Tile& tile) {
-    GLint id = (GLint)tile.clip.mask.to_ulong();
-    GLuint mask = clipMask[tile.clip.length];
-    glStencilFunc(GL_EQUAL, id, mask);
+    const GLint ref = (GLint)tile.clip.reference.to_ulong();
+    const GLuint mask = (GLuint)tile.clip.mask.to_ulong();
+    glStencilFunc(GL_EQUAL, ref, mask);
 }
 
 void Painter::renderTileLayer(const Tile& tile, std::shared_ptr<StyleLayer> layer_desc, const mat4 &matrix) {
diff --git a/src/renderer/painter_clipping.cpp b/src/renderer/painter_clipping.cpp
index e94646d922..d8fa3693bd 100644
--- a/src/renderer/painter_clipping.cpp
+++ b/src/renderer/painter_clipping.cpp
@@ -14,7 +14,6 @@ void Painter::drawClippingMasks(const std::set<std::shared_ptr<StyleSource>> &so
     depthMask(false);
     glColorMask(false, false, false, false);
     depthRange(1.0f, 1.0f);
-    glStencilMask(0xFF);
 
     coveringPlainArray.bind(*plainShader, tileStencilBuffer, BUFFER_OFFSET(0));
 
@@ -31,9 +30,10 @@ void Painter::drawClippingMasks(const std::set<std::shared_ptr<StyleSource>> &so
 void Painter::drawClippingMask(const mat4& matrix, const ClipID &clip) {
     plainShader->setMatrix(matrix);
 
-    GLint id = static_cast<GLint>(clip.mask.to_ulong());
-    GLuint mask = clipMask[clip.length];
-    glStencilFunc(GL_ALWAYS, id, mask);
+    const GLint ref = (GLint)(clip.reference.to_ulong());
+    const GLuint mask = (GLuint)(clip.mask.to_ulong());
+    glStencilFunc(GL_ALWAYS, ref, mask);
+    glStencilMask(mask);
 
     glDrawArrays(GL_TRIANGLES, 0, (GLsizei)tileStencilBuffer.index());
 }
diff --git a/src/renderer/symbol_bucket.cpp b/src/renderer/symbol_bucket.cpp
index e8c0fd1829..fd89315096 100644
--- a/src/renderer/symbol_bucket.cpp
+++ b/src/renderer/symbol_bucket.cpp
@@ -75,11 +75,10 @@ std::vector<SymbolFeature> SymbolBucket::processFeatures(const VectorTileLayer &
         if (text) {
             std::string u8string = util::replaceTokens(properties.text.field, feature.properties);
 
-            auto &convert = std::use_facet<std::ctype<char>>(std::locale());
             if (properties.text.transform == TextTransformType::Uppercase) {
-                convert.toupper(&u8string[0], &u8string[0] + u8string.size());
+                u8string = platform::uppercase(u8string);
             } else if (properties.text.transform == TextTransformType::Lowercase) {
-                convert.tolower(&u8string[0], &u8string[0] + u8string.size());
+                u8string = platform::lowercase(u8string);
             }
 
             ft.label = ucs4conv.convert(u8string);
@@ -296,7 +295,7 @@ void SymbolBucket::addFeature(const std::vector<Coordinate> &line, const Shaping
         }
 
         // Insert final placement into collision tree and add glyphs/icons to buffers
-        if (glyphScale) {
+        if (glyphScale && std::isfinite(glyphScale)) {
             if (!properties.text.ignore_placement) {
                 collision.insert(glyphPlacement.boxes, anchor, glyphScale, glyphRange,
                                  horizontalText);
@@ -304,7 +303,7 @@ void SymbolBucket::addFeature(const std::vector<Coordinate> &line, const Shaping
             if (inside) addSymbols(text, glyphPlacement.shapes, glyphScale, glyphRange);
         }
 
-        if (iconScale) {
+        if (iconScale && std::isfinite(iconScale)) {
             if (!properties.icon.ignore_placement) {
                 collision.insert(iconPlacement.boxes, anchor, iconScale, iconRange, horizontalIcon);
             }
diff --git a/src/text/collision.cpp b/src/text/collision.cpp
index 89e91d6844..6326bea825 100644
--- a/src/text/collision.cpp
+++ b/src/text/collision.cpp
@@ -166,10 +166,10 @@ float Collision::getPlacementScale(const GlyphBoxes &glyphs, float minPlacementS
                 float s4 = (ob.br.y - nb.tl.y + padding) /
                            (na.y - oa.y); // scale at which new box is to the bottom of old box
 
-                if (isnan(s1) || isnan(s2)) {
+                if (std::isnan(s1) || std::isnan(s2)) {
                     s1 = s2 = 1;
                 }
-                if (isnan(s3) || isnan(s4)) {
+                if (std::isnan(s3) || std::isnan(s4)) {
                     s3 = s4 = 1;
                 }
 
diff --git a/src/text/rotation_range.cpp b/src/text/rotation_range.cpp
index 3ebdfe91cb..664ea9c709 100644
--- a/src/text/rotation_range.cpp
+++ b/src/text/rotation_range.cpp
@@ -95,7 +95,7 @@ rotatingRotatingCollisions(const CollisionRect &a, const CollisionRect &b,
     std::vector<float> f;
     for (size_t i = 0; i < c.size(); i++) {
         // Check if they are close enough to collide
-        if (!isnan(c[i]) && d_sq <= e[i]) {
+        if (!std::isnan(c[i]) && d_sq <= e[i]) {
             // So far, angles have been calulated as relative to the vector
             // between anchors.
             // Convert the angles to angles from north.
diff --git a/src/util/clip_ids.cpp b/src/util/clip_ids.cpp
index d815876a06..9c391c38ad 100644
--- a/src/util/clip_ids.cpp
+++ b/src/util/clip_ids.cpp
@@ -12,187 +12,85 @@
 
 namespace mbgl {
 
-struct TileHierarchy {
-    TileHierarchy(Tile::ID id, std::list<TileHierarchy> &&children)
-        : id(id), children(std::move(children)) {}
-
-    const Tile::ID id;
-    ClipID clip;
-    std::list<TileHierarchy> children;
-};
-
-std::list<TileHierarchy> partition(std::forward_list<Tile::ID> &&array) {
-    if (array.empty()) {
-        // We don't have to update the clipping mask because there are no tiles
-        // anyway.
-        return {};
-    }
-
-    int8_t minZ = array.begin()->z;
-
-    std::list<TileHierarchy> result;
-    std::forward_list<Tile::ID> remainder;
-    auto remainder_it = remainder.before_begin();
-
-    while (!array.empty()) {
-        const Tile::ID id = array.front();
-        array.pop_front();
-        if (id.z == minZ) {
-            std::forward_list<Tile::ID> children;
-            auto children_it = children.before_begin();
-
-            array.remove_if([&id, &children, &children_it](const Tile::ID &child) {
-                if (child.isChildOf(id)) {
-                    children_it = children.insert_after(children_it, child);
-                    return true;
-                } else {
-                    return false;
-                }
-            });
-
-            result.emplace_back(id, partition(std::move(children)));
-        } else {
-            remainder_it = remainder.insert_after(remainder_it, id);
+ClipIDGenerator::Leaf::Leaf(Tile &tile_) : tile(tile_) {}
+
+void ClipIDGenerator::Leaf::add(const Tile::ID &p) {
+    if (p.isChildOf(tile.id)) {
+        // Ensure that no already present child is a parent of the new p.
+        for (const Tile::ID &child : children) {
+            if (p.isChildOf(child))
+                return;
         }
+        children.push_front(p);
     }
-
-    // Concatenate the remainder.
-    if (!remainder.empty()) {
-        result.splice(result.begin(), partition(std::move(remainder)));
-    }
-
-    return result;
 }
 
-uint8_t prefix(std::list<TileHierarchy> &array, TileHierarchy *parent = nullptr) {
-    if (array.empty()) {
-        return 0;
-    }
-
-    bool all_children_are_immediate = true;
-    uint8_t max_child_prefix_length = 0;
-
-    struct Huffman {
-        explicit Huffman(int prefix_length, TileHierarchy *item)
-            : prefix_length(prefix_length), children(1, item) {}
-        uint8_t prefix_length;
-        std::vector<TileHierarchy *> children;
-    };
-
-    // Create a temporary structure that we use for sorting the prefix tree.
-    std::list<Huffman> huffman;
-    std::transform(array.begin(), array.end(), std::back_inserter(huffman), [parent, &all_children_are_immediate, &max_child_prefix_length](TileHierarchy &item) {
-        uint8_t prefix_length = prefix(item.children, &item);
+bool ClipIDGenerator::Leaf::operator==(const Leaf &other) const {
+    return tile.id == other.tile.id && children == other.children;
+}
 
-        if (prefix_length > max_child_prefix_length) {
-            max_child_prefix_length = prefix_length;
+bool ClipIDGenerator::reuseExisting(Leaf &leaf) {
+    for (const std::vector<Leaf> &pool : pools) {
+        auto existing = std::find(pool.begin(), pool.end(), leaf);
+        if (existing != pool.end()) {
+            leaf.tile.clip = existing->tile.clip;
+            return true;
         }
+    }
+    return false;
+}
 
-        if (!parent || item.id.z != parent->id.z + 1) {
-            all_children_are_immediate = false;
-        }
+void ClipIDGenerator::update(std::forward_list<Tile *> tiles) {
+    Pool pool;
 
-        return Huffman { prefix_length + 1, &item };
+    tiles.sort([](const Tile *a, const Tile *b) {
+        return a->id < b->id;
     });
 
-    while (huffman.size() > 1) {
-        huffman.sort([](const Huffman &a, const Huffman &b) {
-            return a.prefix_length < b.prefix_length;
-        });
-
-        Huffman &first = *huffman.begin();
-        Huffman &second = *(++huffman.begin());
-
-        assert(&first != &second);
-
-        // Prefix with 0
-        std::for_each(first.children.begin(), first.children.end(), [](TileHierarchy *child) {
-            child->clip.mask >>= 1;
-            child->clip.mask.set(7, false); // noop
-            child->clip.length++;
-        });
-        first.prefix_length++;
-
-        // Prefix with 1
-        std::for_each(second.children.begin(), second.children.end(), [](TileHierarchy *child) {
-            child->clip.mask >>= 1;
-            child->clip.mask.set(7, true);
-            child->clip.length++;
-        });
-        second.prefix_length++;
-
-        second.children.insert(second.children.end(), first.children.begin(), first.children.end());
-        second.prefix_length = first.prefix_length + second.prefix_length;
-
-        // Remove the first child as we've just merged it into the second version.
-        huffman.erase(huffman.begin());
-    }
-
-    uint8_t prefix_length = 0;
+    const auto end = tiles.end();
+    for (auto it = tiles.begin(); it != end; it++) {
+        if (!*it) {
+            // Handle null pointers.
+            continue;
+        }
 
-    // Filter out all-zero bits
-    bool filter_zero = !all_children_are_immediate || array.size() != 4;
+        Tile &tile = **it;
+        Leaf clip { tile };
 
-    for (TileHierarchy &item : array) {
-        if (filter_zero && !item.clip.mask.any()) {
-            // Make sure we don't have a prefix that is all zeros.
-            // item.clip.mask |= (0x80 >> item.length);
-            item.clip.mask.set(7 - item.clip.length);
-            item.clip.length++;
+        // Try to add all remaining ids as children. We sorted the tile list
+        // by z earlier, so all preceding items cannot be children of the current
+        // tile.
+        for (auto child_it = std::next(it); child_it != end; child_it++) {
+            clip.add((*child_it)->id);
         }
+        clip.children.sort();
 
-        if (item.clip.length > prefix_length) {
-            prefix_length = item.clip.length;
+        // Loop through all existing pools and try to find a matching ClipID.
+        if (!reuseExisting(clip)) {
+            // We haven't found an existing clip ID
+            pool.push_back(std::move(clip));
         }
     }
 
-    return max_child_prefix_length + prefix_length;
-}
-
-void propagate(std::map<Tile::ID, ClipID> &mapping, std::list<TileHierarchy> &array, const ClipID &parent = ClipID{}) {
-    for (auto &item : array) {
-        item.clip.mask >>= parent.length;
-        item.clip.mask |= parent.mask;
-        item.clip.length += parent.length;
-#if defined(DEBUG)
-        auto result = mapping.emplace(item.id, item.clip);
-        assert("Tried to insert a duplicate item" && result.second == true);
-#else
-        mapping.emplace(item.id, item.clip);
-#endif
-        propagate(mapping, item.children, const_cast<const ClipID &>(item.clip));
-    };
-}
-
-void updateClipIDs(const std::list<Tile *> &array) {
-    std::forward_list<Tile::ID> ids;
-    std::transform(array.begin(), array.end(), std::front_inserter(ids), [](Tile *item) {
-        return item->id;
-    });
+    if (pool.size()) {
+        const uint32_t bit_count = util::ceil_log2(pool.size() + 1);
+        const std::bitset<8> mask = uint64_t(((1 << bit_count) - 1) << bit_offset);
 
-    const std::map<Tile::ID, ClipID> mapping = computeClipIDs(ids);
-
-    std::for_each(array.begin(), array.end(), [&mapping](Tile *item) {
-        auto it = mapping.find(item->id);
-        if (it != mapping.end()) {
-            item->clip = it->second;
-        } else {
-            item->clip = ClipID {};
+        // We are starting our count with 1 since we need at least 1 bit set to distinguish between
+        // areas without any tiles whatsoever and the current area.
+        uint8_t count = 1;
+        for (Leaf &leaf : pool) {
+            leaf.tile.clip.mask = mask;
+            leaf.tile.clip.reference = count++ << bit_offset;
         }
-    });
-}
 
-std::map<Tile::ID, ClipID> computeClipIDs(std::forward_list<Tile::ID> array) {
-    // Sort by zoom level and make sure that we don't have duplicate elements.
-    array.sort();
-    array.unique();
-
-    std::list<TileHierarchy> hierarchy = partition(std::move(array));
-    prefix(hierarchy);
+        bit_offset += bit_count;
+        pools.push_front(std::move(pool));
+    }
 
-    std::map<Tile::ID, ClipID> mapping;
-    propagate(mapping, hierarchy);
-    return mapping;
+    if (bit_offset > 8) {
+        fprintf(stderr, "stencil mask overflow\n");
+    }
 }
 
 }
diff --git a/src/util/math.cpp b/src/util/math.cpp
new file mode 100644
index 0000000000..a7eab2d771
--- /dev/null
+++ b/src/util/math.cpp
@@ -0,0 +1,25 @@
+#include <mbgl/util/math.hpp>
+
+namespace mbgl {
+namespace util {
+
+// From http://stackoverflow.com/questions/3272424/compute-fast-log-base-2-ceiling
+uint32_t ceil_log2(uint64_t x) {
+    static const uint64_t t[6] = {0xFFFFFFFF00000000, 0x00000000FFFF0000,
+                                  0x000000000000FF00, 0x00000000000000F0,
+                                  0x000000000000000C, 0x0000000000000002};
+    uint32_t y = (((x & (x - 1)) == 0) ? 0 : 1);
+    uint32_t j = 32;
+
+    for (int32_t i = 0; i < 6; i++) {
+        const uint32_t k = (((x & t[i]) == 0) ? 0 : j);
+        y += k;
+        x >>= k;
+        j >>= 1;
+    }
+
+    return y;
+}
+
+}
+}
\ No newline at end of file
diff --git a/src/util/threadpool.cpp b/src/util/threadpool.cpp
deleted file mode 100644
index f19032ee01..0000000000
--- a/src/util/threadpool.cpp
+++ /dev/null
@@ -1,54 +0,0 @@
-#include <mbgl/util/threadpool.hpp>
-#include <mbgl/util/std.hpp>
-#include <thread>
-#include <memory>
-
-using namespace mbgl::util;
-
-std::unique_ptr<Threadpool> mbgl::util::threadpool = std::make_unique<Threadpool>(std::thread::hardware_concurrency());
-
-Threadpool::Threadpool(int max_workers)
-    : max_workers(max_workers) {
-}
-
-void Threadpool::add(Callback callback, void *data) {
-    if (worker_count < max_workers) {
-        worker_count++;
-        workers.emplace_front(*this);
-    }
-
-    pthread_mutex_lock(&mutex);
-    tasks.push(std::make_pair(callback, data));
-    pthread_mutex_unlock(&mutex);
-    pthread_cond_signal(&condition);
-}
-
-Threadpool::Worker::Worker(Threadpool& pool)
-    : pool(pool) {
-    pthread_create(&thread, nullptr, loop, (void *)this);
-}
-
-Threadpool::Worker::~Worker() {
-    pthread_cancel(thread);
-}
-
-
-void *Threadpool::Worker::loop(void *ptr) {
-    Worker *worker = static_cast<Worker *>(ptr);
-    Threadpool& pool = worker->pool;
-
-    pthread_mutex_lock(&pool.mutex);
-    while (true) {
-        if (pool.tasks.size()) {
-            Threadpool::Task task = pool.tasks.front();
-            pool.tasks.pop();
-            pthread_mutex_unlock(&pool.mutex);
-            task.first(task.second);
-            pthread_mutex_lock(&pool.mutex);
-        } else {
-            pthread_cond_wait(&pool.condition, &pool.mutex);
-        }
-    }
-
-    return nullptr;
-}
diff --git a/test/clip_ids.cpp b/test/clip_ids.cpp
index f2e8be98bc..18ef9658e5 100644
--- a/test/clip_ids.cpp
+++ b/test/clip_ids.cpp
@@ -8,298 +8,244 @@
 
 using namespace mbgl;
 
-TEST(ClipIDs, ClipMasks) {
-    ASSERT_EQ(0, clipMask[0]);
-    ASSERT_EQ(0x80, clipMask[1]);
-    ASSERT_EQ(0xC0, clipMask[2]);
-    ASSERT_EQ(0xE0, clipMask[3]);
-    ASSERT_EQ(0xF0, clipMask[4]);
-    ASSERT_EQ(0xF8, clipMask[5]);
-    ASSERT_EQ(0xFC, clipMask[6]);
-    ASSERT_EQ(0xFE, clipMask[7]);
-    ASSERT_EQ(0xFF, clipMask[8]);
+template <typename T> void generate(const T &sources) {
+    ClipIDGenerator generator;
+
+    for (size_t j = 0; j < sources.size(); j++) {
+        std::forward_list<Tile *> tile_ptrs;
+        std::transform(sources[j].begin(), sources[j].end(), std::front_inserter(tile_ptrs), [](const std::shared_ptr<Tile> &tile) { return tile.get(); });
+        generator.update(tile_ptrs);
+    }
 }
 
+template <typename T> void print(const T &sources) {
+    for (size_t j = 0; j < sources.size(); j++) {
+        for (size_t i = 0; i < sources[j].size(); i++) {
+            std::cout << "    ASSERT_EQ(ClipID(\"" << sources[j][i]->clip.mask << "\", \"" << sources[j][i]->clip.reference << "\"), sources[" << j << "][" << i << "]->clip);\n";
+        }
+    }
+}
 
 TEST(ClipIDs, ParentAndFourChildren) {
-    std::array<std::unique_ptr<Tile>, 5> tiles {{
-        std::make_unique<Tile>(Tile::ID { 1, 0, 0 }), // 1/0/0: 11000000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, 0, 1 }), // 1/0/1: 11100000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, 1, 0 }), // 1/1/0: 10000000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, 1, 1 }), // 1/1/1: 10100000 (3)
-        std::make_unique<Tile>(Tile::ID { 0, 0, 0 }), // 0/0/0: 10000000 (1)
-    }};
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[0]->clip.mask); ASSERT_EQ(3, tiles[0]->clip.length);
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[4]->clip.mask); ASSERT_EQ(1, tiles[4]->clip.length);
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 1, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 0, 1 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 0, 0, 0 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][4]->clip);
 }
 
 TEST(ClipIDs, ParentAndFourChildrenNegative) {
-    std::array<std::unique_ptr<Tile>, 5> tiles {{
-        std::make_unique<Tile>(Tile::ID { 1, -2, 0 }), // 1/0/0: 11000000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, -2, 1 }), // 1/0/1: 11100000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, -1, 0 }), // 1/1/0: 10000000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, -1, 1 }), // 1/1/1: 10100000 (3)
-        std::make_unique<Tile>(Tile::ID { 0, -1, 0 }), // 0/0/0: 10000000 (1)
-    }};
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[0]->clip.mask); ASSERT_EQ(3, tiles[0]->clip.length);
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[4]->clip.mask); ASSERT_EQ(1, tiles[4]->clip.length);
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 1, -2, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, -2, 1 }),
+            std::make_shared<Tile>(Tile::ID { 1, -1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, -1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 0, -1, 0 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][4]->clip);
 }
 
 TEST(ClipIDs, NegativeParentAndMissingLevel) {
-    std::array<std::unique_ptr<Tile>, 5> tiles {{
-        std::make_unique<Tile>(Tile::ID { 1, -1, 0 }), // 1/-1/0: 10000000 (1)
-        std::make_unique<Tile>(Tile::ID { 2, -1, 0 }), // 2/-1/0: 10000000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, -2, 1 }), // 2/-2/1: 11100000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, -1, 1 }), // 2/-1/1: 10100000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, -2, 0 }), // 2/-2/0: 11000000 (3)
-    }};
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[0]->clip.mask); ASSERT_EQ(1, tiles[0]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length);
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length);
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[4]->clip.mask); ASSERT_EQ(3, tiles[4]->clip.length);
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 1, -1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, -1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, -2, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, -1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, -2, 0 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][4]->clip);
 }
 
 
 TEST(ClipIDs, SevenOnSameLevel) {
-    std::array<std::unique_ptr<Tile>, 7> tiles {{
-        std::make_unique<Tile>(Tile::ID { 2, 0, 0 }), // 2/0/0: 11000000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 0, 1 }), // 2/0/1: 11100000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 0, 2 }), // 2/0/2: 10000000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 1, 0 }), // 2/1/0: 10100000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 1, 1 }), // 2/1/1: 01000000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 1, 2 }), // 2/1/2: 01100000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 2, 0 }), // 2/2/0: 00100000 (3)
-    }};
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[0]->clip.mask); ASSERT_EQ(3, tiles[0]->clip.length);
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length);
-    ASSERT_EQ(std::bitset<8>("01000000"), tiles[4]->clip.mask); ASSERT_EQ(3, tiles[4]->clip.length);
-    ASSERT_EQ(std::bitset<8>("01100000"), tiles[5]->clip.mask); ASSERT_EQ(3, tiles[5]->clip.length);
-    ASSERT_EQ(std::bitset<8>("00100000"), tiles[6]->clip.mask); ASSERT_EQ(3, tiles[6]->clip.length);
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 2, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, 0, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 0, 2 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 2 }),
+            std::make_shared<Tile>(Tile::ID { 2, 2, 0 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][4]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000110"), sources[0][5]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000111"), sources[0][6]->clip);
 }
 
 TEST(ClipIDs, MultipleLevels) {
-    std::array<std::unique_ptr<Tile>, 12> tiles {{
-        std::make_unique<Tile>(Tile::ID { 2, 0, 0 }),           // 2/0/0: 10000000 (1)
-            std::make_unique<Tile>(Tile::ID { 3, 0, 0 }),       //     3/0/0: 10000000 (3)
-            std::make_unique<Tile>(Tile::ID { 3, 0, 1 }),       //     3/0/1: 11100000 (3)
-                std::make_unique<Tile>(Tile::ID { 4, 0, 2 }),   //         4/0/2: 11110000 (5)
-                std::make_unique<Tile>(Tile::ID { 4, 1, 2 }),   //         4/0/3: 11111000 (5)
-                std::make_unique<Tile>(Tile::ID { 4, 0, 3 }),   //         4/1/2: 11100000 (5)
-                std::make_unique<Tile>(Tile::ID { 4, 1, 3 }),   //         4/1/3: 11101000 (5)
-            std::make_unique<Tile>(Tile::ID { 3, 1, 0 }),       //     3/1/0: 10100000 (3)
-            std::make_unique<Tile>(Tile::ID { 3, 1, 1 }),       //     3/1/1: 11000000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 1, 0 }),           // 2/1/0: 01000000 (2)
-            std::make_unique<Tile>(Tile::ID { 3, 2, 0 }),       //     3/2/0: 01010000 (4)
-            std::make_unique<Tile>(Tile::ID { 3, 2, 1 }),       //     3/2/1: 01100000 (3)
-    }};
-
-    // Use a random order to verify that the result of this algorithm is independent of the
-    std::random_shuffle(tiles.begin(), tiles.end());
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // Sort them by tile ID so that we know what order we have to test in.
-    std::sort(tiles.begin(), tiles.end(), [](const std::unique_ptr<Tile> &a, const std::unique_ptr<Tile> &b) {
-        return a->id < b->id;
-    });
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::string("2/0/0"), std::string(tiles[0]->id));
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[0]->clip.mask);
-    ASSERT_EQ(1, tiles[0]->clip.length);
-
-    ASSERT_EQ(std::string("2/1/0"), std::string(tiles[1]->id));
-    ASSERT_EQ(std::bitset<8>("01000000"), tiles[1]->clip.mask);
-    ASSERT_EQ(2, tiles[1]->clip.length);
-
-    ASSERT_EQ(std::string("3/0/0"), std::string(tiles[2]->id));
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask);
-    ASSERT_EQ(3, tiles[2]->clip.length);
-
-    ASSERT_EQ(std::string("3/0/1"), std::string(tiles[3]->id));
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[3]->clip.mask);
-    ASSERT_EQ(3, tiles[3]->clip.length);
-
-    ASSERT_EQ(std::string("3/1/0"), std::string(tiles[4]->id));
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[4]->clip.mask);
-    ASSERT_EQ(3, tiles[4]->clip.length);
-
-    ASSERT_EQ(std::string("3/1/1"), std::string(tiles[5]->id));
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[5]->clip.mask);
-    ASSERT_EQ(3, tiles[5]->clip.length);
-
-    ASSERT_EQ(std::string("3/2/0"), std::string(tiles[6]->id));
-    ASSERT_EQ(std::bitset<8>("01010000"), tiles[6]->clip.mask);
-    ASSERT_EQ(4, tiles[6]->clip.length);
-
-    ASSERT_EQ(std::string("3/2/1"), std::string(tiles[7]->id));
-    ASSERT_EQ(std::bitset<8>("01100000"), tiles[7]->clip.mask);
-    ASSERT_EQ(3, tiles[7]->clip.length);
-
-    ASSERT_EQ(std::string("4/0/2"), std::string(tiles[8]->id));
-    ASSERT_EQ(std::bitset<8>("11110000"), tiles[8]->clip.mask);
-    ASSERT_EQ(5, tiles[8]->clip.length);
-
-    ASSERT_EQ(std::string("4/0/3"), std::string(tiles[9]->id));
-    ASSERT_EQ(std::bitset<8>("11111000"), tiles[9]->clip.mask);
-    ASSERT_EQ(5, tiles[9]->clip.length);
-
-    ASSERT_EQ(std::string("4/1/2"), std::string(tiles[10]->id));
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[10]->clip.mask);
-    ASSERT_EQ(5, tiles[10]->clip.length);
-
-    ASSERT_EQ(std::string("4/1/3"), std::string(tiles[11]->id));
-    ASSERT_EQ(std::bitset<8>("11101000"), tiles[11]->clip.mask);
-    ASSERT_EQ(5, tiles[11]->clip.length);
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 2, 0, 0 }),
+                std::make_shared<Tile>(Tile::ID { 3, 0, 0 }),
+                std::make_shared<Tile>(Tile::ID { 3, 0, 1 }),
+                    std::make_shared<Tile>(Tile::ID { 4, 0, 2 }),
+                    std::make_shared<Tile>(Tile::ID { 4, 1, 2 }),
+                    std::make_shared<Tile>(Tile::ID { 4, 0, 3 }),
+                    std::make_shared<Tile>(Tile::ID { 4, 1, 3 }),
+                std::make_shared<Tile>(Tile::ID { 3, 1, 0 }),
+                std::make_shared<Tile>(Tile::ID { 3, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 0 }),
+                std::make_shared<Tile>(Tile::ID { 3, 2, 0 }),
+                std::make_shared<Tile>(Tile::ID { 3, 2, 1 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00001111", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000011"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000100"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001001"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001011"), sources[0][4]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001010"), sources[0][5]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001100"), sources[0][6]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000101"), sources[0][7]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000110"), sources[0][8]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000010"), sources[0][9]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000111"), sources[0][10]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001000"), sources[0][11]->clip);
 }
 
 
 TEST(ClipIDs, Bug206) {
-    std::array<std::unique_ptr<Tile>, 11> tiles {{
-        std::make_unique<Tile>(Tile::ID { 10, 162, 395 }),      // 10/162/395: 10000000 (3)
-        std::make_unique<Tile>(Tile::ID { 10, 162, 396 }),      // 10/162/396: 10100000 (3)
-        std::make_unique<Tile>(Tile::ID { 10, 163, 395 }),      // 10/163/395: 11000000 (2)
-            std::make_unique<Tile>(Tile::ID { 11, 326, 791 }),  //     11/326/791: 11100000 (4)
-            std::make_unique<Tile>(Tile::ID { 12, 654, 1582 }), //     12/654/1582: 11001000 (5)
-            std::make_unique<Tile>(Tile::ID { 12, 654, 1583 }), //     12/654/1583: 11010000 (4)
-            std::make_unique<Tile>(Tile::ID { 12, 655, 1582 }), //     12/655/1582: 11110000 (5)
-            std::make_unique<Tile>(Tile::ID { 12, 655, 1583 }), //     12/655/1583: 11111000 (5)
-        std::make_unique<Tile>(Tile::ID { 10, 163, 396 }),      // 10/163/396: 01000000 (3)
-        std::make_unique<Tile>(Tile::ID { 10, 164, 395 }),      // 10/164/395: 01100000 (3)
-        std::make_unique<Tile>(Tile::ID { 10, 164, 396 }),      // 10/164/396: 00100000 (3)
-    }};
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::string("10/162/395"), std::string(tiles[0]->id));
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[0]->clip.mask);
-    ASSERT_EQ(3, tiles[0]->clip.length);
-
-    ASSERT_EQ(std::string("10/162/396"), std::string(tiles[1]->id));
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[1]->clip.mask);
-    ASSERT_EQ(3, tiles[1]->clip.length);
-
-    ASSERT_EQ(std::string("10/163/395"), std::string(tiles[2]->id));
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[2]->clip.mask);
-    ASSERT_EQ(2, tiles[2]->clip.length);
-
-    ASSERT_EQ(std::string("11/326/791"), std::string(tiles[3]->id));
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[3]->clip.mask);
-    ASSERT_EQ(4, tiles[3]->clip.length);
-
-    ASSERT_EQ(std::string("12/654/1582"), std::string(tiles[4]->id));
-    ASSERT_EQ(std::bitset<8>("11001000"), tiles[4]->clip.mask);
-    ASSERT_EQ(5, tiles[4]->clip.length);
-
-    ASSERT_EQ(std::string("12/654/1583"), std::string(tiles[5]->id));
-    ASSERT_EQ(std::bitset<8>("11010000"), tiles[5]->clip.mask);
-    ASSERT_EQ(4, tiles[5]->clip.length);
-
-    ASSERT_EQ(std::string("12/655/1582"), std::string(tiles[6]->id));
-    ASSERT_EQ(std::bitset<8>("11110000"), tiles[6]->clip.mask);
-    ASSERT_EQ(5, tiles[6]->clip.length);
-
-    ASSERT_EQ(std::string("12/655/1583"), std::string(tiles[7]->id));
-    ASSERT_EQ(std::bitset<8>("11111000"), tiles[7]->clip.mask);
-    ASSERT_EQ(5, tiles[7]->clip.length);
-
-    ASSERT_EQ(std::string("10/163/396"), std::string(tiles[8]->id));
-    ASSERT_EQ(std::bitset<8>("01000000"), tiles[8]->clip.mask);
-    ASSERT_EQ(3, tiles[8]->clip.length);
-
-    ASSERT_EQ(std::string("10/164/395"), std::string(tiles[9]->id));
-    ASSERT_EQ(std::bitset<8>("01100000"), tiles[9]->clip.mask);
-    ASSERT_EQ(3, tiles[9]->clip.length);
-
-    ASSERT_EQ(std::string("10/164/396"), std::string(tiles[10]->id));
-    ASSERT_EQ(std::bitset<8>("00100000"), tiles[10]->clip.mask);
-    ASSERT_EQ(3, tiles[10]->clip.length);
-
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 10, 162, 395 }),
+            std::make_shared<Tile>(Tile::ID { 10, 162, 396 }),
+            std::make_shared<Tile>(Tile::ID { 10, 163, 395 }),
+                std::make_shared<Tile>(Tile::ID { 11, 326, 791 }),
+                std::make_shared<Tile>(Tile::ID { 12, 654, 1582 }),
+                std::make_shared<Tile>(Tile::ID { 12, 654, 1583 }),
+                std::make_shared<Tile>(Tile::ID { 12, 655, 1582 }),
+                std::make_shared<Tile>(Tile::ID { 12, 655, 1583 }),
+            std::make_shared<Tile>(Tile::ID { 10, 163, 396 }),
+            std::make_shared<Tile>(Tile::ID { 10, 164, 395 }),
+            std::make_shared<Tile>(Tile::ID { 10, 164, 396 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00001111", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000010"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000011"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000111"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001000"), sources[0][4]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001001"), sources[0][5]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001010"), sources[0][6]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001011"), sources[0][7]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000100"), sources[0][8]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000101"), sources[0][9]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000110"), sources[0][10]->clip);
 }
 
-TEST(ClipIDs, DuplicateIDs) {
-
-    std::forward_list<Tile::ID> tiles {{
-        Tile::ID { 2, 0, 0 },
-        Tile::ID { 2, 0, 1 },
-        Tile::ID { 2, 0, 0 },
-        Tile::ID { 2, 0, 1 },
-        Tile::ID { 2, 0, 1 },
-    }};
 
-    std::map<Tile::ID, ClipID> mapping = computeClipIDs(tiles);
-
-    ASSERT_EQ(2ull, mapping.size());
-
-    // for (const auto &it : mapping) {
-    //     std::cout << std::string(it.first) << "(" << it.first << ")" << ": " << it.second.mask << " (" << (int)it.second.length << ")" << std::endl;
-    // }
+TEST(ClipIDs, MultipleSources) {
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 0, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 2, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 2, 2 }),
+        },
+        {
+            std::make_shared<Tile>(Tile::ID { 0, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 2, 2 }),
+        },
+        {
+            std::make_shared<Tile>(Tile::ID { 1, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 0, 1 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 1 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00011000", "00001000"), sources[1][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[1][1]->clip);
+    ASSERT_EQ(ClipID("00011000", "00010000"), sources[1][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[1][3]->clip);
+    ASSERT_EQ(ClipID("11100000", "00100000"), sources[2][0]->clip);
+    ASSERT_EQ(ClipID("11100000", "01000000"), sources[2][1]->clip);
+    ASSERT_EQ(ClipID("11100000", "01100000"), sources[2][2]->clip);
+    ASSERT_EQ(ClipID("11100000", "10000000"), sources[2][3]->clip);
+    ASSERT_EQ(ClipID("00011000", "00010000"), sources[2][4]->clip);
+}
 
-    ASSERT_EQ(std::bitset<8>("01000000"), mapping[Tile::ID(2, 0, 0)].mask);
-    ASSERT_EQ(2, mapping[Tile::ID(2, 0, 0)].length);
 
-    ASSERT_EQ(std::bitset<8>("10000000"), mapping[Tile::ID(2, 0, 1)].mask);
-    ASSERT_EQ(1, mapping[Tile::ID(2, 0, 1)].length);
+TEST(ClipIDs, DuplicateIDs) {
+        const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 2, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, 0, 1 }),
+        },
+        {
+            std::make_shared<Tile>(Tile::ID { 2, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, 0, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 0, 1 }),
+        }
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000011", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000011", "00000010"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000011", "00000001"), sources[1][0]->clip);
+    ASSERT_EQ(ClipID("00000011", "00000010"), sources[1][1]->clip);
+    ASSERT_EQ(ClipID("00000011", "00000010"), sources[1][2]->clip);
 }
diff --git a/test/test.gyp b/test/test.gyp
index 07709ecc86..fd7725bb03 100644
--- a/test/test.gyp
+++ b/test/test.gyp
@@ -201,6 +201,7 @@
             "./headless.cpp",
             "../common/headless_view.hpp",
             "../common/headless_view.cpp",
+            "../common/platform_default.cpp",
             "./fixtures/fixture_request.cpp",
             "./fixtures/fixture_log.hpp",
             "./fixtures/fixture_log.cpp",