1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/mobile/android/base/favicons/decoders/ICODecoder.java Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,377 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +package org.mozilla.gecko.favicons.decoders;
1.9 +
1.10 +import android.graphics.Bitmap;
1.11 +import org.mozilla.gecko.favicons.Favicons;
1.12 +import org.mozilla.gecko.gfx.BitmapUtils;
1.13 +
1.14 +import android.util.SparseArray;
1.15 +
1.16 +import java.util.Iterator;
1.17 +import java.util.NoSuchElementException;
1.18 +
1.19 +/**
1.20 + * Utility class for determining the region of a provided array which contains the largest bitmap,
1.21 + * assuming the provided array is a valid ICO and the bitmap desired is square, and for pruning
1.22 + * unwanted entries from ICO files, if desired.
1.23 + *
1.24 + * An ICO file is a container format that may hold up to 255 images in either BMP or PNG format.
1.25 + * A mixture of image types may not exist.
1.26 + *
1.27 + * The format consists of a header specifying the number, n, of images, followed by the Icon Directory.
1.28 + *
1.29 + * The Icon Directory consists of n Icon Directory Entries, each 16 bytes in length, specifying, for
1.30 + * the corresponding image, the dimensions, colour information, payload size, and location in the file.
1.31 + *
1.32 + * All numerical fields follow a little-endian byte ordering.
1.33 + *
1.34 + * Header format:
1.35 + *
1.36 + * 0 1 2 3
1.37 + * 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
1.38 + * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1.39 + * | Reserved field. Must be zero | Type (1 for ICO, 2 for CUR) |
1.40 + * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1.41 + * | Image count (n) |
1.42 + * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1.43 + *
1.44 + * The type field is expected to always be 1. CUR format images should not be used for Favicons.
1.45 + *
1.46 + *
1.47 + * Icon Directory Entry format:
1.48 + *
1.49 + * 0 1 2 3
1.50 + * 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
1.51 + * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1.52 + * | Image width | Image height | Palette size | Reserved (0) |
1.53 + * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1.54 + * | Colour plane count | Bits per pixel |
1.55 + * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1.56 + * | Size of image data, in bytes |
1.57 + * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1.58 + * | Start of image data, as an offset from start of file |
1.59 + * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1.60 + *
1.61 + * Image dimensions of zero are to be interpreted as image dimensions of 256.
1.62 + *
1.63 + * The palette size field records the number of colours in the stored BMP, if a palette is used. Zero
1.64 + * if the payload is a PNG or no palette is in use.
1.65 + *
1.66 + * The number of colour planes is, usually, 0 (Not in use) or 1. Values greater than 1 are to be
1.67 + * interpreted not as a colour plane count, but as a multiplying factor on the bits per pixel field.
1.68 + * (Apparently 65535 was not deemed a sufficiently large maximum value of bits per pixel.)
1.69 + *
1.70 + *
1.71 + * The Icon Directory consists of n-many Icon Directory Entries in sequence, with no gaps.
1.72 + *
1.73 + * This class is not thread safe.
1.74 + */
1.75 +public class ICODecoder implements Iterable<Bitmap> {
1.76 + // The number of bytes that compacting will save for us to bother doing it.
1.77 + public static final int COMPACT_THRESHOLD = 4000;
1.78 +
1.79 + // Some geometry of an ICO file.
1.80 + public static final int ICO_HEADER_LENGTH_BYTES = 6;
1.81 + public static final int ICO_ICONDIRENTRY_LENGTH_BYTES = 16;
1.82 +
1.83 + // The buffer containing bytes to attempt to decode.
1.84 + private byte[] decodand;
1.85 +
1.86 + // The region of the decodand to decode.
1.87 + private int offset;
1.88 + private int len;
1.89 +
1.90 + private IconDirectoryEntry[] iconDirectory;
1.91 + private boolean isValid;
1.92 + private boolean hasDecoded;
1.93 +
1.94 + public ICODecoder(byte[] decodand, int offset, int len) {
1.95 + this.decodand = decodand;
1.96 + this.offset = offset;
1.97 + this.len = len;
1.98 + }
1.99 +
1.100 + /**
1.101 + * Decode the Icon Directory for this ICO and store the result in iconDirectory.
1.102 + *
1.103 + * @return true if ICO decoding was considered to probably be a success, false if it certainly
1.104 + * was a failure.
1.105 + */
1.106 + private boolean decodeIconDirectoryAndPossiblyPrune() {
1.107 + hasDecoded = true;
1.108 +
1.109 + // Fail if the end of the described range is out of bounds.
1.110 + if (offset + len > decodand.length) {
1.111 + return false;
1.112 + }
1.113 +
1.114 + // Fail if we don't have enough space for the header.
1.115 + if (len < ICO_HEADER_LENGTH_BYTES) {
1.116 + return false;
1.117 + }
1.118 +
1.119 + // Check that the reserved fields in the header are indeed zero, and that the type field
1.120 + // specifies ICO. If not, we've probably been given something that isn't really an ICO.
1.121 + if (decodand[offset] != 0 ||
1.122 + decodand[offset + 1] != 0 ||
1.123 + decodand[offset + 2] != 1 ||
1.124 + decodand[offset + 3] != 0) {
1.125 + return false;
1.126 + }
1.127 +
1.128 + // Here, and in many other places, byte values are ANDed with 0xFF. This is because Java
1.129 + // bytes are signed - to obtain a numerical value of a longer type which holds the unsigned
1.130 + // interpretation of the byte of interest, we do this.
1.131 + int numEncodedImages = (decodand[offset + 4] & 0xFF) |
1.132 + (decodand[offset + 5] & 0xFF) << 8;
1.133 +
1.134 +
1.135 + // Fail if there are no images or the field is corrupt.
1.136 + if (numEncodedImages <= 0) {
1.137 + return false;
1.138 + }
1.139 +
1.140 + final int headerAndDirectorySize = ICO_HEADER_LENGTH_BYTES + (numEncodedImages * ICO_ICONDIRENTRY_LENGTH_BYTES);
1.141 +
1.142 + // Fail if there is not enough space in the buffer for the stated number of icondir entries,
1.143 + // let alone the data.
1.144 + if (len < headerAndDirectorySize) {
1.145 + return false;
1.146 + }
1.147 +
1.148 + // Put the pointer on the first byte of the first Icon Directory Entry.
1.149 + int bufferIndex = offset + ICO_HEADER_LENGTH_BYTES;
1.150 +
1.151 + // We now iterate over the Icon Directory, decoding each entry as we go. We also need to
1.152 + // discard all entries except one >= the maximum interesting size.
1.153 +
1.154 + // Size of the smallest image larger than the limit encountered.
1.155 + int minimumMaximum = Integer.MAX_VALUE;
1.156 +
1.157 + // Used to track the best entry for each size. The entries we want to keep.
1.158 + SparseArray<IconDirectoryEntry> preferenceArray = new SparseArray<IconDirectoryEntry>();
1.159 +
1.160 + for (int i = 0; i < numEncodedImages; i++, bufferIndex += ICO_ICONDIRENTRY_LENGTH_BYTES) {
1.161 + // Decode the Icon Directory Entry at this offset.
1.162 + IconDirectoryEntry newEntry = IconDirectoryEntry.createFromBuffer(decodand, offset, len, bufferIndex);
1.163 + newEntry.index = i;
1.164 +
1.165 + if (newEntry.isErroneous) {
1.166 + continue;
1.167 + }
1.168 +
1.169 + if (newEntry.width > Favicons.largestFaviconSize) {
1.170 + // If we already have a smaller image larger than the maximum size of interest, we
1.171 + // don't care about the new one which is larger than the smallest image larger than
1.172 + // the maximum size.
1.173 + if (newEntry.width >= minimumMaximum) {
1.174 + continue;
1.175 + }
1.176 +
1.177 + // Remove the previous minimum-maximum.
1.178 + preferenceArray.delete(minimumMaximum);
1.179 +
1.180 + minimumMaximum = newEntry.width;
1.181 + }
1.182 +
1.183 + IconDirectoryEntry oldEntry = preferenceArray.get(newEntry.width);
1.184 + if (oldEntry == null) {
1.185 + preferenceArray.put(newEntry.width, newEntry);
1.186 + continue;
1.187 + }
1.188 +
1.189 + if (oldEntry.compareTo(newEntry) < 0) {
1.190 + preferenceArray.put(newEntry.width, newEntry);
1.191 + }
1.192 + }
1.193 +
1.194 + final int count = preferenceArray.size();
1.195 +
1.196 + // Abort if no entries are desired (Perhaps all are corrupt?)
1.197 + if (count == 0) {
1.198 + return false;
1.199 + }
1.200 +
1.201 + // Allocate space for the icon directory entries in the decoded directory.
1.202 + iconDirectory = new IconDirectoryEntry[count];
1.203 +
1.204 + // The size of the data in the buffer that we find useful.
1.205 + int retainedSpace = ICO_HEADER_LENGTH_BYTES;
1.206 +
1.207 + for (int i = 0; i < count; i++) {
1.208 + IconDirectoryEntry e = preferenceArray.valueAt(i);
1.209 + retainedSpace += ICO_ICONDIRENTRY_LENGTH_BYTES + e.payloadSize;
1.210 + iconDirectory[i] = e;
1.211 + }
1.212 +
1.213 + isValid = true;
1.214 +
1.215 + // Set the number of images field in the buffer to reflect the number of retained entries.
1.216 + decodand[offset + 4] = (byte) iconDirectory.length;
1.217 + decodand[offset + 5] = (byte) (iconDirectory.length >>> 8);
1.218 +
1.219 + if ((len - retainedSpace) > COMPACT_THRESHOLD) {
1.220 + compactingCopy(retainedSpace);
1.221 + }
1.222 +
1.223 + return true;
1.224 + }
1.225 +
1.226 + /**
1.227 + * Copy the buffer into a new array of exactly the required size, omitting any unwanted data.
1.228 + */
1.229 + private void compactingCopy(int spaceRetained) {
1.230 + byte[] buf = new byte[spaceRetained];
1.231 +
1.232 + // Copy the header.
1.233 + System.arraycopy(decodand, offset, buf, 0, ICO_HEADER_LENGTH_BYTES);
1.234 +
1.235 + int headerPtr = ICO_HEADER_LENGTH_BYTES;
1.236 +
1.237 + int payloadPtr = ICO_HEADER_LENGTH_BYTES + (iconDirectory.length * ICO_ICONDIRENTRY_LENGTH_BYTES);
1.238 +
1.239 + int ind = 0;
1.240 + for (IconDirectoryEntry entry : iconDirectory) {
1.241 + // Copy this entry.
1.242 + System.arraycopy(decodand, offset + entry.getOffset(), buf, headerPtr, ICO_ICONDIRENTRY_LENGTH_BYTES);
1.243 +
1.244 + // Copy its payload.
1.245 + System.arraycopy(decodand, offset + entry.payloadOffset, buf, payloadPtr, entry.payloadSize);
1.246 +
1.247 + // Update the offset field.
1.248 + buf[headerPtr + 12] = (byte) payloadPtr;
1.249 + buf[headerPtr + 13] = (byte) (payloadPtr >>> 8);
1.250 + buf[headerPtr + 14] = (byte) (payloadPtr >>> 16);
1.251 + buf[headerPtr + 15] = (byte) (payloadPtr >>> 24);
1.252 +
1.253 + entry.payloadOffset = payloadPtr;
1.254 + entry.index = ind;
1.255 +
1.256 + payloadPtr += entry.payloadSize;
1.257 + headerPtr += ICO_ICONDIRENTRY_LENGTH_BYTES;
1.258 + ind++;
1.259 + }
1.260 +
1.261 + decodand = buf;
1.262 + offset = 0;
1.263 + len = spaceRetained;
1.264 + }
1.265 +
1.266 + /**
1.267 + * Decode and return the bitmap represented by the given index in the Icon Directory, if valid.
1.268 + *
1.269 + * @param index The index into the Icon Directory of the image of interest.
1.270 + * @return The decoded Bitmap object for this image, or null if the entry is invalid or decoding
1.271 + * fails.
1.272 + */
1.273 + public Bitmap decodeBitmapAtIndex(int index) {
1.274 + final IconDirectoryEntry iconDirEntry = iconDirectory[index];
1.275 +
1.276 + if (iconDirEntry.payloadIsPNG) {
1.277 + // PNG payload. Simply extract it and decode it.
1.278 + return BitmapUtils.decodeByteArray(decodand, offset + iconDirEntry.payloadOffset, iconDirEntry.payloadSize);
1.279 + }
1.280 +
1.281 + // The payload is a BMP, so we need to do some magic to get the decoder to do what we want.
1.282 + // We construct an ICO containing just the image we want, and let Android do the rest.
1.283 + byte[] decodeTarget = new byte[ICO_HEADER_LENGTH_BYTES + ICO_ICONDIRENTRY_LENGTH_BYTES + iconDirEntry.payloadSize];
1.284 +
1.285 + // Set the type field in the ICO header.
1.286 + decodeTarget[2] = 1;
1.287 +
1.288 + // Set the num-images field in the header to 1.
1.289 + decodeTarget[4] = 1;
1.290 +
1.291 + // Copy the ICONDIRENTRY we need into the new buffer.
1.292 + System.arraycopy(decodand, offset + iconDirEntry.getOffset(), decodeTarget, ICO_HEADER_LENGTH_BYTES, ICO_ICONDIRENTRY_LENGTH_BYTES);
1.293 +
1.294 + // Copy the payload into the new buffer.
1.295 + final int singlePayloadOffset = ICO_HEADER_LENGTH_BYTES + ICO_ICONDIRENTRY_LENGTH_BYTES;
1.296 + System.arraycopy(decodand, offset + iconDirEntry.payloadOffset, decodeTarget, singlePayloadOffset, iconDirEntry.payloadSize);
1.297 +
1.298 + // Update the offset field of the ICONDIRENTRY to make the new ICO valid.
1.299 + decodeTarget[ICO_HEADER_LENGTH_BYTES + 12] = (byte) singlePayloadOffset;
1.300 + decodeTarget[ICO_HEADER_LENGTH_BYTES + 13] = (byte) (singlePayloadOffset >>> 8);
1.301 + decodeTarget[ICO_HEADER_LENGTH_BYTES + 14] = (byte) (singlePayloadOffset >>> 16);
1.302 + decodeTarget[ICO_HEADER_LENGTH_BYTES + 15] = (byte) (singlePayloadOffset >>> 24);
1.303 +
1.304 + // Decode the newly-constructed singleton-ICO.
1.305 + return BitmapUtils.decodeByteArray(decodeTarget);
1.306 + }
1.307 +
1.308 + /**
1.309 + * Fetch an iterator over the images in this ICO, or null if this ICO seems to be invalid.
1.310 + *
1.311 + * @return An iterator over the Bitmaps stored in this ICO, or null if decoding fails.
1.312 + */
1.313 + @Override
1.314 + public ICOIterator iterator() {
1.315 + // If a previous call to decode concluded this ICO is invalid, abort.
1.316 + if (hasDecoded && !isValid) {
1.317 + return null;
1.318 + }
1.319 +
1.320 + // If we've not been decoded before, but now fail to make any sense of the ICO, abort.
1.321 + if (!hasDecoded) {
1.322 + if (!decodeIconDirectoryAndPossiblyPrune()) {
1.323 + return null;
1.324 + }
1.325 + }
1.326 +
1.327 + // If decoding was a success, return an iterator over the images in this ICO.
1.328 + return new ICOIterator();
1.329 + }
1.330 +
1.331 + /**
1.332 + * Decode this ICO and return the result as a LoadFaviconResult.
1.333 + * @return A LoadFaviconResult representing the decoded ICO.
1.334 + */
1.335 + public LoadFaviconResult decode() {
1.336 + // The call to iterator returns null if decoding fails.
1.337 + Iterator<Bitmap> bitmaps = iterator();
1.338 + if (bitmaps == null) {
1.339 + return null;
1.340 + }
1.341 +
1.342 + LoadFaviconResult result = new LoadFaviconResult();
1.343 +
1.344 + result.bitmapsDecoded = bitmaps;
1.345 + result.faviconBytes = decodand;
1.346 + result.offset = offset;
1.347 + result.length = len;
1.348 + result.isICO = true;
1.349 +
1.350 + return result;
1.351 + }
1.352 +
1.353 + /**
1.354 + * Inner class to iterate over the elements in the ICO represented by the enclosing instance.
1.355 + */
1.356 + private class ICOIterator implements Iterator<Bitmap> {
1.357 + private int mIndex = 0;
1.358 +
1.359 + @Override
1.360 + public boolean hasNext() {
1.361 + return mIndex < iconDirectory.length;
1.362 + }
1.363 +
1.364 + @Override
1.365 + public Bitmap next() {
1.366 + if (mIndex > iconDirectory.length) {
1.367 + throw new NoSuchElementException("No more elements in this ICO.");
1.368 + }
1.369 + return decodeBitmapAtIndex(mIndex++);
1.370 + }
1.371 +
1.372 + @Override
1.373 + public void remove() {
1.374 + if (iconDirectory[mIndex] == null) {
1.375 + throw new IllegalStateException("Remove already called for element " + mIndex);
1.376 + }
1.377 + iconDirectory[mIndex] = null;
1.378 + }
1.379 + }
1.380 +}
