Home | History | Annotate | Download | only in util
      1 /*
      2  * Copyright (C) 2013 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 package com.android.ex.photo.util;
     18 
     19 import android.util.Log;
     20 
     21 import java.io.IOException;
     22 import java.io.InputStream;
     23 import java.util.Arrays;
     24 
     25 /**
     26  * Wrapper for {@link InputStream} that allows you to read bytes from it like a byte[]. An
     27  * internal buffer is kept as small as possible to avoid large unnecessary allocations.
     28  *
     29  * <p/>
     30  * Care must be taken so that the internal buffer is kept small. The best practice is to
     31  * precalculate the maximum buffer size that you will need. For example,
     32  * say you have a loop that reads bytes from index <code>0</code> to <code>10</code>,
     33  * skips to index <code>N</code>, reads from index <code>N</code> to <code>N+10</code>, etc. Then
     34  * you know that the internal buffer can have a maximum size of <code>10</code>,
     35  * and you should set the <code>bufferSize</code> parameter to <code>10</code> in the constructor.
     36  *
     37  * <p/>
     38  * Use {@link #advanceTo(int)} to declare that you will not need to access lesser indexes. This
     39  * helps to keep the internal buffer small. In the above example, after reading bytes from index
     40  * <code>0</code> to <code>10</code>, you should call <code>advanceTo(N)</code> so that internal
     41  * buffer becomes filled with bytes from index <code>N</code> to <code>N+10</code>.
     42  *
     43  * <p/>
     44  * If you know that you are reading bytes from a <strong>strictly</strong> increasing or equal
     45  * index, then you should set the <code>autoAdvance</code> parameter to <code>true</code> in the
     46  * constructor. For complicated access patterns, or when you prefer to control the internal
     47  * buffer yourself, set <code>autoAdvance</code> to <code>false</code>. When
     48  * <code>autoAdvance</code> is enabled, every time an index is beyond the buffer length,
     49  * the buffer will be shifted forward such that the index requested becomes the first element in
     50  * the buffer.
     51  *
     52  * <p/>
     53  * All public methods with parameter <code>index</code> are absolute indexed. The index is from
     54  * the beginning of the wrapped input stream.
     55  */
     56 public class InputStreamBuffer {
     57 
     58     private static final boolean DEBUG = false;
     59     private static final int DEBUG_MAX_BUFFER_SIZE = 80;
     60     private static final String TAG = "InputStreamBuffer";
     61 
     62     private InputStream mInputStream;
     63     private byte[] mBuffer;
     64     private boolean mAutoAdvance;
     65     /** Byte count the buffer is offset by. */
     66     private int mOffset = 0;
     67     /** Number of bytes filled in the buffer. */
     68     private int mFilled = 0;
     69 
     70     /**
     71      * Construct a new wrapper for an InputStream.
     72      *
     73      * <p/>
     74      * If <code>autoAdvance</code> is true, behavior is undefined if you call {@link #get(int)}
     75      * or {@link #has(int)} with an index N, then some arbitrary time later call {@link #get(int)}
     76      * or {@link #has(int)} with an index M < N. The wrapper may return the right value,
     77      * if the buffer happens to still contain index M, but more likely it will throw an
     78      * {@link IllegalStateException}.
     79      *
     80      * <p/>
     81      * If <code>autoAdvance</code> is false, you must be diligent and call {@link #advanceTo(int)}
     82      * at the appropriate times to ensure that the internal buffer is not unnecessarily resized
     83      * and reallocated.
     84      *
     85      * @param inputStream The input stream to wrap. The input stream will not be closed by the
     86      *                    wrapper.
     87      * @param bufferSize  The initial size for the internal buffer. The buffer size should be
     88      *                    carefully chosen to avoid resizing and reallocating the internal buffer.
     89      *                    The internal buffer size used will be the least power of two greater
     90      *                    than this parameter.
     91      * @param autoAdvance Determines the behavior when you need to read an index that is beyond
     92      *                    the internal buffer size. If true, the internal buffer will shift so
     93      *                    that the requested index becomes the first element. If false,
     94      *                    the internal buffer size will grow to the smallest power of 2 which is
     95      *                    greater than the requested index.
     96      */
     97     public InputStreamBuffer(final InputStream inputStream, int bufferSize,
     98             final boolean autoAdvance) {
     99         mInputStream = inputStream;
    100         if (bufferSize <= 0) {
    101             throw new IllegalArgumentException(
    102                     String.format("Buffer size %d must be positive.", bufferSize));
    103         }
    104         bufferSize = leastPowerOf2(bufferSize);
    105         mBuffer = new byte[bufferSize];
    106         mAutoAdvance = autoAdvance;
    107     }
    108 
    109     /**
    110      * Attempt to get byte at the requested index from the wrapped input stream. If the internal
    111      * buffer contains the requested index, return immediately. If the index is less than the
    112      * head of the buffer, or the index is greater or equal to the size of the wrapped input stream,
    113      * a runtime exception is thrown.
    114      *
    115      * <p/>
    116      * If the index is not in the internal buffer, but it can be requested from the input stream,
    117      * {@link #fill(int)} will be called first, and the byte at the index returned.
    118      *
    119      * <p/>
    120      * You should always call {@link #has(int)} with the same index, unless you are sure that no
    121      * exceptions will be thrown as described above.
    122      *
    123      * <p/>
    124      * Consider calling {@link #advanceTo(int)} if you know that you will never request a lesser
    125      * index in the future.
    126      * @param index The requested index.
    127      * @return The byte at that index.
    128      */
    129     public byte get(final int index) throws IllegalStateException, IndexOutOfBoundsException {
    130         Trace.beginSection("get");
    131         if (has(index)) {
    132             final int i = index - mOffset;
    133             Trace.endSection();
    134             return mBuffer[i];
    135         } else {
    136             Trace.endSection();
    137             throw new IndexOutOfBoundsException(
    138                     String.format("Index %d beyond length.", index));
    139         }
    140     }
    141 
    142     /**
    143      * Attempt to return whether the requested index is within the size of the wrapped input
    144      * stream. One side effect is {@link #fill(int)} will be called.
    145      *
    146      * <p/>
    147      * If this method returns true, it is guaranteed that {@link #get(int)} with the same index
    148      * will not fail. That means that if the requested index is within the size of the wrapped
    149      * input stream, but the index is less than the head of the internal buffer,
    150      * a runtime exception is thrown.
    151      *
    152      * <p/>
    153      * See {@link #get(int)} for caveats. A lot of the same warnings about exceptions and
    154      * <code>advanceTo()</code> apply.
    155      * @param index The requested index.
    156      * @return True if requested index is within the size of the wrapped input stream. False if
    157      * the index is beyond the size.
    158      */
    159     public boolean has(final int index) throws IllegalStateException, IndexOutOfBoundsException {
    160         Trace.beginSection("has");
    161         if (index < mOffset) {
    162             Trace.endSection();
    163             throw new IllegalStateException(
    164                     String.format("Index %d is before buffer %d", index, mOffset));
    165         }
    166 
    167         final int i = index - mOffset;
    168 
    169         // Requested index not in internal buffer.
    170         if (i >= mFilled || i >= mBuffer.length) {
    171             Trace.endSection();
    172             return fill(index);
    173         }
    174 
    175         Trace.endSection();
    176         return true;
    177     }
    178 
    179     /**
    180      * Attempts to advance the head of the buffer to the requested index. If the index is less
    181      * than the head of the buffer, the internal state will not be changed.
    182      *
    183      * <p/>
    184      * Advancing does not fill the internal buffer. The next {@link #get(int)} or
    185      * {@link #has(int)} call will fill the buffer.
    186      */
    187     public void advanceTo(final int index) throws IllegalStateException, IndexOutOfBoundsException {
    188         Trace.beginSection("advance to");
    189         final int i = index - mOffset;
    190         if (i <= 0) {
    191             // noop
    192             Trace.endSection();
    193             return;
    194         } else if (i < mFilled) {
    195             // Shift elements starting at i to position 0.
    196             shiftToBeginning(i);
    197             mOffset = index;
    198             mFilled = mFilled - i;
    199         } else if (mInputStream != null) {
    200             // Burn some bytes from the input stream to match the new index.
    201             int burn = i - mFilled;
    202             boolean empty = false;
    203             int fails = 0;
    204             try {
    205                 while (burn > 0) {
    206                     final long burned = mInputStream.skip(burn);
    207                     if (burned <= 0) {
    208                         fails++;
    209                     } else {
    210                         burn -= burned;
    211                     }
    212 
    213                     if (fails >= 5) {
    214                         empty = true;
    215                         break;
    216                     }
    217                 }
    218             } catch (IOException ignored) {
    219                 empty = true;
    220             }
    221 
    222             if (empty) {
    223                 //Mark input stream as consumed.
    224                 mInputStream = null;
    225             }
    226 
    227             mOffset = index - burn;
    228             mFilled = 0;
    229         } else {
    230             // Advancing beyond the input stream.
    231             mOffset = index;
    232             mFilled = 0;
    233         }
    234 
    235         Log.d(TAG, String.format("advanceTo %d buffer: %s", i, this));
    236         Trace.endSection();
    237     }
    238 
    239     /**
    240      * Attempt to fill the internal buffer fully. The buffer will be modified such that the
    241      * requested index will always be in the buffer. If the index is less
    242      * than the head of the buffer, a runtime exception is thrown.
    243      *
    244      * <p/>
    245      * If the requested index is already in bounds of the buffer, then the buffer will just be
    246      * filled.
    247      *
    248      * <p/>
    249      * Otherwise, if <code>autoAdvance</code> was set to true in the constructor,
    250      * {@link #advanceTo(int)} will be called with the requested index,
    251      * and then the buffer filled. If <code>autoAdvance</code> was set to false,
    252      * we allocate a single larger buffer of a least multiple-of-two size that can contain the
    253      * requested index. The elements in the old buffer are copied over to the head of the new
    254      * buffer. Then the entire buffer is filled.
    255      * @param index The requested index.
    256      * @return True if the byte at the requested index has been filled. False if the wrapped
    257      * input stream ends before we reach the index.
    258      */
    259     private boolean fill(final int index) {
    260         Trace.beginSection("fill");
    261         if (index < mOffset) {
    262             Trace.endSection();
    263             throw new IllegalStateException(
    264                     String.format("Index %d is before buffer %d", index, mOffset));
    265         }
    266 
    267         int i = index - mOffset;
    268         // Can't fill buffer anymore if input stream is consumed.
    269         if (mInputStream == null) {
    270             Trace.endSection();
    271             return false;
    272         }
    273 
    274         // Increase buffer size if necessary.
    275         int length = i + 1;
    276         if (length > mBuffer.length) {
    277             if (mAutoAdvance) {
    278                 advanceTo(index);
    279                 i = index - mOffset;
    280             } else {
    281                 length = leastPowerOf2(length);
    282                 Log.w(TAG, String.format(
    283                         "Increasing buffer length from %d to %d. Bad buffer size chosen, "
    284                                 + "or advanceTo() not called.",
    285                         mBuffer.length, length));
    286                 mBuffer = Arrays.copyOf(mBuffer, length);
    287             }
    288         }
    289 
    290         // Read from input stream to fill buffer.
    291         int read = -1;
    292         try {
    293             read = mInputStream.read(mBuffer, mFilled, mBuffer.length - mFilled);
    294         } catch (IOException ignored) {
    295         }
    296 
    297         if (read != -1) {
    298             mFilled = mFilled + read;
    299         } else {
    300             // Mark input stream as consumed.
    301             mInputStream = null;
    302         }
    303 
    304         Log.d(TAG, String.format("fill %d      buffer: %s", i, this));
    305 
    306         Trace.endSection();
    307         return i < mFilled;
    308     }
    309 
    310     /**
    311      * Modify the internal buffer so that all the bytes are shifted towards the head by
    312      * <code>i</code>. In other words, the byte at index <code>i</code> will now be at index
    313      * <code>0</code>. Bytes from a lesser index are tossed.
    314      * @param i How much to shift left.
    315      */
    316     private void shiftToBeginning(final int i) {
    317         if (i >= mBuffer.length) {
    318             throw new IndexOutOfBoundsException(
    319                     String.format("Index %d out of bounds. Length %d", i, mBuffer.length));
    320         }
    321         for (int j = 0; j + i < mFilled; j++) {
    322             mBuffer[j] = mBuffer[j + i];
    323         }
    324     }
    325 
    326     @Override
    327     public String toString() {
    328         if (DEBUG) {
    329             return toDebugString();
    330         }
    331         return String.format("+%d+%d [%d]", mOffset, mBuffer.length, mFilled);
    332     }
    333 
    334     public String toDebugString() {
    335         Trace.beginSection("to debug string");
    336         final StringBuilder sb = new StringBuilder();
    337         sb.append("+").append(mOffset);
    338         sb.append("+").append(mBuffer.length);
    339         sb.append(" [");
    340         for (int i = 0; i < mBuffer.length && i < DEBUG_MAX_BUFFER_SIZE; i++) {
    341             if (i > 0) {
    342                 sb.append(",");
    343             }
    344             if (i < mFilled) {
    345                 sb.append(String.format("%02X", mBuffer[i]));
    346             } else {
    347                 sb.append("__");
    348             }
    349         }
    350         if (mInputStream != null) {
    351             sb.append("...");
    352         }
    353         sb.append("]");
    354 
    355         Trace.endSection();
    356         return sb.toString();
    357     }
    358 
    359     /**
    360      * Calculate the least power of two greater than or equal to the input.
    361      */
    362     private static int leastPowerOf2(int n) {
    363         n--;
    364         n |= n >> 1;
    365         n |= n >> 2;
    366         n |= n >> 4;
    367         n |= n >> 8;
    368         n |= n >> 16;
    369         n++;
    370         return n;
    371     }
    372 }
    373