summaryrefslogtreecommitdiffstats
path: root/services/java/com/android/server/AssetAtlasService.java
blob: 26b4652f4c7dde2a28ba0d97b77028106529d435 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
/*
 * 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.
 */

package com.android.server;

import android.content.Context;
import android.content.pm.PackageInfo;
import android.content.pm.PackageManager;
import android.content.res.Resources;
import android.graphics.Atlas;
import android.graphics.Bitmap;
import android.graphics.Canvas;
import android.graphics.Paint;
import android.graphics.PixelFormat;
import android.graphics.PorterDuff;
import android.graphics.PorterDuffXfermode;
import android.graphics.drawable.Drawable;
import android.os.Environment;
import android.os.RemoteException;
import android.os.SystemProperties;
import android.util.Log;
import android.util.LongSparseArray;
import android.view.GraphicBuffer;
import android.view.IAssetAtlas;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicBoolean;

/**
 * This service is responsible for packing preloaded bitmaps into a single
 * atlas texture. The resulting texture can be shared across processes to
 * reduce overall memory usage.
 *
 * @hide
 */
public class AssetAtlasService extends IAssetAtlas.Stub {
    /**
     * Name of the <code>AssetAtlasService</code>.
     */
    public static final String ASSET_ATLAS_SERVICE = "assetatlas";

    private static final String LOG_TAG = "Atlas";

    // Turns debug logs on/off. Debug logs are kept to a minimum and should
    // remain on to diagnose issues
    private static final boolean DEBUG_ATLAS = true;

    // When set to true the content of the atlas will be saved to disk
    // in /data/system/atlas.png. The shared GraphicBuffer may be empty
    private static final boolean DEBUG_ATLAS_TEXTURE = false;

    // Minimum size in pixels to consider for the resulting texture
    private static final int MIN_SIZE = 768;
    // Maximum size in pixels to consider for the resulting texture
    private static final int MAX_SIZE = 2048;
    // Increment in number of pixels between size variants when looking
    // for the best texture dimensions
    private static final int STEP = 64;

    // This percentage of the total number of pixels represents the minimum
    // number of pixels we want to be able to pack in the atlas
    private static final float PACKING_THRESHOLD = 0.8f;

    // Defines the number of int fields used to represent a single entry
    // in the atlas map. This number defines the size of the array returned
    // by the getMap(). See the mAtlasMap field for more information
    private static final int ATLAS_MAP_ENTRY_FIELD_COUNT = 4;

    // Specifies how our GraphicBuffer will be used. To get proper swizzling
    // the buffer will be written to using OpenGL (from JNI) so we can leave
    // the software flag set to "never"
    private static final int GRAPHIC_BUFFER_USAGE = GraphicBuffer.USAGE_SW_READ_NEVER |
            GraphicBuffer.USAGE_SW_WRITE_NEVER | GraphicBuffer.USAGE_HW_TEXTURE;

    // This boolean is set to true if an atlas was successfully
    // computed and rendered
    private final AtomicBoolean mAtlasReady = new AtomicBoolean(false);

    private final Context mContext;

    // Version name of the current build, used to identify changes to assets list
    private final String mVersionName;

    // Holds the atlas' data. This buffer can be mapped to
    // OpenGL using an EGLImage
    private GraphicBuffer mBuffer;

    // Describes how bitmaps are placed in the atlas. Each bitmap is
    // represented by several entries in the array:
    // int0: SkBitmap*, the native bitmap object
    // int1: x position
    // int2: y position
    // int3: rotated, 1 if the bitmap must be rotated, 0 otherwise
    // NOTE: This will need to be handled differently to support 64 bit pointers
    private int[] mAtlasMap;

    /**
     * Creates a new service. Upon creating, the service will gather the list of
     * assets to consider for packing into the atlas and spawn a new thread to
     * start the packing work.
     *
     * @param context The context giving access to preloaded resources
     */
    public AssetAtlasService(Context context) {
        mContext = context;
        mVersionName = queryVersionName(context);

        ArrayList<Bitmap> bitmaps = new ArrayList<Bitmap>(300);
        int totalPixelCount = 0;

        // We only care about drawables that hold bitmaps
        final Resources resources = context.getResources();
        final LongSparseArray<Drawable.ConstantState> drawables = resources.getPreloadedDrawables();

        final int count = drawables.size();
        for (int i = 0; i < count; i++) {
            final Bitmap bitmap = drawables.valueAt(i).getBitmap();
            if (bitmap != null && bitmap.getConfig() == Bitmap.Config.ARGB_8888) {
                bitmaps.add(bitmap);
                totalPixelCount += bitmap.getWidth() * bitmap.getHeight();
            }
        }

        // Our algorithms perform better when the bitmaps are first sorted
        // The comparator will sort the bitmap by width first, then by height
        Collections.sort(bitmaps, new Comparator<Bitmap>() {
            @Override
            public int compare(Bitmap b1, Bitmap b2) {
                if (b1.getWidth() == b2.getWidth()) {
                    return b2.getHeight() - b1.getHeight();
                }
                return b2.getWidth() - b1.getWidth();
            }
        });

        // Kick off the packing work on a worker thread
        new Thread(new Renderer(bitmaps, totalPixelCount)).start();
    }

    /**
     * Queries the version name stored in framework's AndroidManifest.
     * The version name can be used to identify possible changes to
     * framework resources.
     *
     * @see #getBuildIdentifier(String)
     */
    private static String queryVersionName(Context context) {
        try {
            String packageName = context.getPackageName();
            PackageInfo info = context.getPackageManager().getPackageInfo(packageName, 0);
            return info.versionName;
        } catch (PackageManager.NameNotFoundException e) {
            Log.w(LOG_TAG, "Could not get package info", e);
        }
        return null;
    }

    /**
     * Callback invoked by the server thread to indicate we can now run
     * 3rd party code.
     */
    public void systemRunning() {
    }

    /**
     * The renderer does all the work:
     */
    private class Renderer implements Runnable {
        private final ArrayList<Bitmap> mBitmaps;
        private final int mPixelCount;

        private int mNativeBitmap;

        // Used for debugging only
        private Bitmap mAtlasBitmap;

        Renderer(ArrayList<Bitmap> bitmaps, int pixelCount) {
            mBitmaps = bitmaps;
            mPixelCount = pixelCount;
        }

        /**
         * 1. On first boot or after every update, brute-force through all the
         *    possible atlas configurations and look for the best one (maximimize
         *    number of packed assets and minimize texture size)
         *    a. If a best configuration was computed, write it out to disk for
         *       future use
         * 2. Read best configuration from disk
         * 3. Compute the packing using the best configuration
         * 4. Allocate a GraphicBuffer
         * 5. Render assets in the buffer
         */
        @Override
        public void run() {
            Configuration config = chooseConfiguration(mBitmaps, mPixelCount, mVersionName);
            if (DEBUG_ATLAS) Log.d(LOG_TAG, "Loaded configuration: " + config);

            if (config != null) {
                mBuffer = GraphicBuffer.create(config.width, config.height,
                        PixelFormat.RGBA_8888, GRAPHIC_BUFFER_USAGE);

                if (mBuffer != null) {
                    Atlas atlas = new Atlas(config.type, config.width, config.height, config.flags);
                    if (renderAtlas(mBuffer, atlas, config.count)) {
                        mAtlasReady.set(true);
                    }
                }
            }
        }

        /**
         * Renders a list of bitmaps into the atlas. The position of each bitmap
         * was decided by the packing algorithm and will be honored by this
         * method. If need be this method will also rotate bitmaps.
         *
         * @param buffer The buffer to render the atlas entries into
         * @param atlas The atlas to pack the bitmaps into
         * @param packCount The number of bitmaps that will be packed in the atlas
         *
         * @return true if the atlas was rendered, false otherwise
         */
        @SuppressWarnings("MismatchedReadAndWriteOfArray")
        private boolean renderAtlas(GraphicBuffer buffer, Atlas atlas, int packCount) {
            // Use a Source blend mode to improve performance, the target bitmap
            // will be zero'd out so there's no need to waste time applying blending
            final Paint paint = new Paint();
            paint.setXfermode(new PorterDuffXfermode(PorterDuff.Mode.SRC));

            // We always render the atlas into a bitmap. This bitmap is then
            // uploaded into the GraphicBuffer using OpenGL to swizzle the content
            final Canvas canvas = acquireCanvas(buffer.getWidth(), buffer.getHeight());
            if (canvas == null) return false;

            final Atlas.Entry entry = new Atlas.Entry();

            mAtlasMap = new int[packCount * ATLAS_MAP_ENTRY_FIELD_COUNT];
            int[] atlasMap = mAtlasMap;
            int mapIndex = 0;

            boolean result = false;
            try {
                final long startRender = System.nanoTime();
                final int count = mBitmaps.size();

                for (int i = 0; i < count; i++) {
                    final Bitmap bitmap = mBitmaps.get(i);
                    if (atlas.pack(bitmap.getWidth(), bitmap.getHeight(), entry) != null) {
                        // We have more bitmaps to pack than the current configuration
                        // says, we were most likely not able to detect a change in the
                        // list of preloaded drawables, abort and delete the configuration
                        if (mapIndex >= mAtlasMap.length) {
                            deleteDataFile();
                            break;
                        }

                        canvas.save();
                        canvas.translate(entry.x, entry.y);
                        if (entry.rotated) {
                            canvas.translate(bitmap.getHeight(), 0.0f);
                            canvas.rotate(90.0f);
                        }
                        canvas.drawBitmap(bitmap, 0.0f, 0.0f, null);
                        canvas.restore();

                        atlasMap[mapIndex++] = bitmap.mNativeBitmap;
                        atlasMap[mapIndex++] = entry.x;
                        atlasMap[mapIndex++] = entry.y;
                        atlasMap[mapIndex++] = entry.rotated ? 1 : 0;
                    }
                }

                final long endRender = System.nanoTime();
                if (mNativeBitmap != 0) {
                    result = nUploadAtlas(buffer, mNativeBitmap);
                }

                final long endUpload = System.nanoTime();
                if (DEBUG_ATLAS) {
                    float renderDuration = (endRender - startRender) / 1000.0f / 1000.0f;
                    float uploadDuration = (endUpload - endRender) / 1000.0f / 1000.0f;
                    Log.d(LOG_TAG, String.format("Rendered atlas in %.2fms (%.2f+%.2fms)",
                            renderDuration + uploadDuration, renderDuration, uploadDuration));
                }

            } finally {
                releaseCanvas(canvas);
            }

            return result;
        }

        /**
         * Returns a Canvas for the specified buffer. If {@link #DEBUG_ATLAS_TEXTURE}
         * is turned on, the returned Canvas will render into a local bitmap that
         * will then be saved out to disk for debugging purposes.
         * @param width
         * @param height
         */
        private Canvas acquireCanvas(int width, int height) {
            if (DEBUG_ATLAS_TEXTURE) {
                mAtlasBitmap = Bitmap.createBitmap(width, height, Bitmap.Config.ARGB_8888);
                return new Canvas(mAtlasBitmap);
            } else {
                Canvas canvas = new Canvas();
                mNativeBitmap = nAcquireAtlasCanvas(canvas, width, height);
                return canvas;
            }
        }

        /**
         * Releases the canvas used to render into the buffer. Calling this method
         * will release any resource previously acquired. If {@link #DEBUG_ATLAS_TEXTURE}
         * is turend on, calling this method will write the content of the atlas
         * to disk in /data/system/atlas.png for debugging.
         */
        private void releaseCanvas(Canvas canvas) {
            if (DEBUG_ATLAS_TEXTURE) {
                canvas.setBitmap(null);

                File systemDirectory = new File(Environment.getDataDirectory(), "system");
                File dataFile = new File(systemDirectory, "atlas.png");

                try {
                    FileOutputStream out = new FileOutputStream(dataFile);
                    mAtlasBitmap.compress(Bitmap.CompressFormat.PNG, 100, out);
                    out.close();
                } catch (FileNotFoundException e) {
                    // Ignore
                } catch (IOException e) {
                    // Ignore
                }

                mAtlasBitmap.recycle();
                mAtlasBitmap = null;
            } else {
                nReleaseAtlasCanvas(canvas, mNativeBitmap);
            }
        }
    }

    private static native int nAcquireAtlasCanvas(Canvas canvas, int width, int height);
    private static native void nReleaseAtlasCanvas(Canvas canvas, int bitmap);
    private static native boolean nUploadAtlas(GraphicBuffer buffer, int bitmap);

    @Override
    public boolean isCompatible(int ppid) {
        return ppid == android.os.Process.myPpid();
    }

    @Override
    public GraphicBuffer getBuffer() throws RemoteException {
        return mAtlasReady.get() ? mBuffer : null;
    }

    @Override
    public int[] getMap() throws RemoteException {
        return mAtlasReady.get() ? mAtlasMap : null;
    }

    /**
     * Finds the best atlas configuration to pack the list of supplied bitmaps.
     * This method takes advantage of multi-core systems by spawning a number
     * of threads equal to the number of available cores.
     */
    private static Configuration computeBestConfiguration(
            ArrayList<Bitmap> bitmaps, int pixelCount) {
        if (DEBUG_ATLAS) Log.d(LOG_TAG, "Computing best atlas configuration...");

        long begin = System.nanoTime();
        List<WorkerResult> results = Collections.synchronizedList(new ArrayList<WorkerResult>());

        // Don't bother with an extra thread if there's only one processor
        int cpuCount = Runtime.getRuntime().availableProcessors();
        if (cpuCount == 1) {
            new ComputeWorker(MIN_SIZE, MAX_SIZE, STEP, bitmaps, pixelCount, results, null).run();
        } else {
            int start = MIN_SIZE;
            int end = MAX_SIZE - (cpuCount - 1) * STEP;
            int step = STEP * cpuCount;

            final CountDownLatch signal = new CountDownLatch(cpuCount);

            for (int i = 0; i < cpuCount; i++, start += STEP, end += STEP) {
                ComputeWorker worker = new ComputeWorker(start, end, step,
                        bitmaps, pixelCount, results, signal);
                new Thread(worker, "Atlas Worker #" + (i + 1)).start();
            }

            try {
                signal.await(10, TimeUnit.SECONDS);
            } catch (InterruptedException e) {
                Log.w(LOG_TAG, "Could not complete configuration computation");
                return null;
            }
        }

        // Maximize the number of packed bitmaps, minimize the texture size
        Collections.sort(results, new Comparator<WorkerResult>() {
            @Override
            public int compare(WorkerResult r1, WorkerResult r2) {
                int delta = r2.count - r1.count;
                if (delta != 0) return delta;
                return r1.width * r1.height - r2.width * r2.height;
            }
        });

        if (DEBUG_ATLAS) {
            float delay = (System.nanoTime() - begin) / 1000.0f / 1000.0f / 1000.0f;
            Log.d(LOG_TAG, String.format("Found best atlas configuration in %.2fs", delay));
        }

        WorkerResult result = results.get(0);
        return new Configuration(result.type, result.width, result.height, result.count);
    }

    /**
     * Returns the path to the file containing the best computed
     * atlas configuration.
     */
    private static File getDataFile() {
        File systemDirectory = new File(Environment.getDataDirectory(), "system");
        return new File(systemDirectory, "framework_atlas.config");
    }

    private static void deleteDataFile() {
        Log.w(LOG_TAG, "Current configuration inconsistent with assets list");
        if (!getDataFile().delete()) {
            Log.w(LOG_TAG, "Could not delete the current configuration");
        }
    }

    private File getFrameworkResourcesFile() {
        return new File(mContext.getApplicationInfo().sourceDir);
    }

    /**
     * Returns the best known atlas configuration. This method will either
     * read the configuration from disk or start a brute-force search
     * and save the result out to disk.
     */
    private Configuration chooseConfiguration(ArrayList<Bitmap> bitmaps, int pixelCount,
            String versionName) {
        Configuration config = null;

        final File dataFile = getDataFile();
        if (dataFile.exists()) {
            config = readConfiguration(dataFile, versionName);
        }

        if (config == null) {
            config = computeBestConfiguration(bitmaps, pixelCount);
            if (config != null) writeConfiguration(config, dataFile, versionName);
        }

        return config;
    }

    /**
     * Writes the specified atlas configuration to the specified file.
     */
    private void writeConfiguration(Configuration config, File file, String versionName) {
        BufferedWriter writer = null;
        try {
            writer = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(file)));
            writer.write(getBuildIdentifier(versionName));
            writer.newLine();
            writer.write(config.type.toString());
            writer.newLine();
            writer.write(String.valueOf(config.width));
            writer.newLine();
            writer.write(String.valueOf(config.height));
            writer.newLine();
            writer.write(String.valueOf(config.count));
            writer.newLine();
            writer.write(String.valueOf(config.flags));
            writer.newLine();
        } catch (FileNotFoundException e) {
            Log.w(LOG_TAG, "Could not write " + file, e);
        } catch (IOException e) {
            Log.w(LOG_TAG, "Could not write " + file, e);
        } finally {
            if (writer != null) {
                try {
                    writer.close();
                } catch (IOException e) {
                    // Ignore
                }
            }
        }
    }

    /**
     * Reads an atlas configuration from the specified file. This method
     * returns null if an error occurs or if the configuration is invalid.
     */
    private Configuration readConfiguration(File file, String versionName) {
        BufferedReader reader = null;
        Configuration config = null;
        try {
            reader = new BufferedReader(new InputStreamReader(new FileInputStream(file)));

            if (checkBuildIdentifier(reader, versionName)) {
                Atlas.Type type = Atlas.Type.valueOf(reader.readLine());
                int width = readInt(reader, MIN_SIZE, MAX_SIZE);
                int height = readInt(reader, MIN_SIZE, MAX_SIZE);
                int count = readInt(reader, 0, Integer.MAX_VALUE);
                int flags = readInt(reader, Integer.MIN_VALUE, Integer.MAX_VALUE);

                config = new Configuration(type, width, height, count, flags);
            }
        } catch (IllegalArgumentException e) {
            Log.w(LOG_TAG, "Invalid parameter value in " + file, e);
        } catch (FileNotFoundException e) {
            Log.w(LOG_TAG, "Could not read " + file, e);
        } catch (IOException e) {
            Log.w(LOG_TAG, "Could not read " + file, e);
        } finally {
            if (reader != null) {
                try {
                    reader.close();
                } catch (IOException e) {
                    // Ignore
                }
            }
        }
        return config;
    }

    private static int readInt(BufferedReader reader, int min, int max) throws IOException {
        return Math.max(min, Math.min(max, Integer.parseInt(reader.readLine())));
    }

    /**
     * Compares the next line in the specified buffered reader to the current
     * build identifier. Returns whether the two values are equal.
     *
     * @see #getBuildIdentifier(String)
     */
    private boolean checkBuildIdentifier(BufferedReader reader, String versionName)
            throws IOException {
        String deviceBuildId = getBuildIdentifier(versionName);
        String buildId = reader.readLine();
        return deviceBuildId.equals(buildId);
    }

    /**
     * Returns an identifier for the current build that can be used to detect
     * likely changes to framework resources. The build identifier is made of
     * several distinct values:
     *
     * build fingerprint/framework version name/file size of framework resources apk
     *
     * Only the build fingerprint should be necessary on user builds but
     * the other values are useful to detect changes on eng builds during
     * development.
     *
     * This identifier does not attempt to be exact: a new identifier does not
     * necessarily mean the preloaded drawables have changed. It is important
     * however that whenever the list of preloaded drawables changes, this
     * identifier changes as well.
     *
     * @see #checkBuildIdentifier(java.io.BufferedReader, String)
     */
    private String getBuildIdentifier(String versionName) {
        return SystemProperties.get("ro.build.fingerprint", "") + '/' + versionName + '/' +
                String.valueOf(getFrameworkResourcesFile().length());
    }

    /**
     * Atlas configuration. Specifies the algorithm, dimensions and flags to use.
     */
    private static class Configuration {
        final Atlas.Type type;
        final int width;
        final int height;
        final int count;
        final int flags;

        Configuration(Atlas.Type type, int width, int height, int count) {
            this(type, width, height, count, Atlas.FLAG_DEFAULTS);
        }

        Configuration(Atlas.Type type, int width, int height, int count, int flags) {
            this.type = type;
            this.width = width;
            this.height = height;
            this.count = count;
            this.flags = flags;
        }

        @Override
        public String toString() {
            return type.toString() + " (" + width + "x" + height + ") flags=0x" +
                    Integer.toHexString(flags) + " count=" + count;
        }
    }

    /**
     * Used during the brute-force search to gather information about each
     * variant of the packing algorithm.
     */
    private static class WorkerResult {
        Atlas.Type type;
        int width;
        int height;
        int count;

        WorkerResult(Atlas.Type type, int width, int height, int count) {
            this.type = type;
            this.width = width;
            this.height = height;
            this.count = count;
        }

        @Override
        public String toString() {
            return String.format("%s %dx%d", type.toString(), width, height);
        }
    }

    /**
     * A compute worker will try a finite number of variations of the packing
     * algorithms and save the results in a supplied list.
     */
    private static class ComputeWorker implements Runnable {
        private final int mStart;
        private final int mEnd;
        private final int mStep;
        private final List<Bitmap> mBitmaps;
        private final List<WorkerResult> mResults;
        private final CountDownLatch mSignal;
        private final int mThreshold;

        /**
         * Creates a new compute worker to brute-force through a range of
         * packing algorithms variants.
         *
         * @param start The minimum texture width to try
         * @param end The maximum texture width to try
         * @param step The number of pixels to increment the texture width by at each step
         * @param bitmaps The list of bitmaps to pack in the atlas
         * @param pixelCount The total number of pixels occupied by the list of bitmaps
         * @param results The list of results in which to save the brute-force search results
         * @param signal Latch to decrement when this worker is done, may be null
         */
        ComputeWorker(int start, int end, int step, List<Bitmap> bitmaps, int pixelCount,
                List<WorkerResult> results, CountDownLatch signal) {
            mStart = start;
            mEnd = end;
            mStep = step;
            mBitmaps = bitmaps;
            mResults = results;
            mSignal = signal;

            // Minimum number of pixels we want to be able to pack
            int threshold = (int) (pixelCount * PACKING_THRESHOLD);
            // Make sure we can find at least one configuration
            while (threshold > MAX_SIZE * MAX_SIZE) {
                threshold >>= 1;
            }
            mThreshold = threshold;
        }

        @Override
        public void run() {
            if (DEBUG_ATLAS) Log.d(LOG_TAG, "Running " + Thread.currentThread().getName());

            Atlas.Entry entry = new Atlas.Entry();
            for (Atlas.Type type : Atlas.Type.values()) {
                for (int width = mStart; width < mEnd; width += mStep) {
                    for (int height = MIN_SIZE; height < MAX_SIZE; height += STEP) {
                        // If the atlas is not big enough, skip it
                        if (width * height <= mThreshold) continue;

                        final int count = packBitmaps(type, width, height, entry);
                        if (count > 0) {
                            mResults.add(new WorkerResult(type, width, height, count));
                            // If we were able to pack everything let's stop here
                            // Increasing the height further won't make things better
                            if (count == mBitmaps.size()) {
                                break;
                            }
                        }
                    }
                }
            }

            if (mSignal != null) {
                mSignal.countDown();
            }
        }

        private int packBitmaps(Atlas.Type type, int width, int height, Atlas.Entry entry) {
            int total = 0;
            Atlas atlas = new Atlas(type, width, height);

            final int count = mBitmaps.size();
            for (int i = 0; i < count; i++) {
                final Bitmap bitmap = mBitmaps.get(i);
                if (atlas.pack(bitmap.getWidth(), bitmap.getHeight(), entry) != null) {
                    total++;
                }
            }

            return total;
        }
    }
}