/*
* 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.bitmap.util;
import android.util.Log;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
/**
* Wrapper for {@link InputStream} that allows you to read bytes from it like a byte[]. An
* internal buffer is kept as small as possible to avoid large unnecessary allocations.
*
* <p/>
* Care must be taken so that the internal buffer is kept small. The best practice is to
* precalculate the maximum buffer size that you will need. For example,
* say you have a loop that reads bytes from index <code>0</code> to <code>10</code>,
* skips to index <code>N</code>, reads from index <code>N</code> to <code>N+10</code>, etc. Then
* you know that the internal buffer can have a maximum size of <code>10</code>,
* and you should set the <code>bufferSize</code> parameter to <code>10</code> in the constructor.
*
* <p/>
* Use {@link #advanceTo(int)} to declare that you will not need to access lesser indexes. This
* helps to keep the internal buffer small. In the above example, after reading bytes from index
* <code>0</code> to <code>10</code>, you should call <code>advanceTo(N)</code> so that internal
* buffer becomes filled with bytes from index <code>N</code> to <code>N+10</code>.
*
* <p/>
* If you know that you are reading bytes from a <strong>strictly</strong> increasing or equal
* index, then you should set the <code>autoAdvance</code> parameter to <code>true</code> in the
* constructor. For complicated access patterns, or when you prefer to control the internal
* buffer yourself, set <code>autoAdvance</code> to <code>false</code>. When
* <code>autoAdvance</code> is enabled, every time an index is beyond the buffer length,
* the buffer will be shifted forward such that the index requested becomes the first element in
* the buffer.
*
* <p/>
* All public methods with parameter <code>index</code> are absolute indexed. The index is from
* the beginning of the wrapped input stream.
*/
public class InputStreamBuffer {
private static final boolean DEBUG = false;
private static final int DEBUG_MAX_BUFFER_SIZE = 80;
private static final String TAG = InputStreamBuffer.class.getSimpleName();
private InputStream mInputStream;
private byte[] mBuffer;
private boolean mAutoAdvance;
/** Byte count the buffer is offset by. */
private int mOffset = 0;
/** Number of bytes filled in the buffer. */
private int mFilled = 0;
/**
* Construct a new wrapper for an InputStream.
*
* <p/>
* If <code>autoAdvance</code> is true, behavior is undefined if you call {@link #get(int)}
* or {@link #has(int)} with an index N, then some arbitrary time later call {@link #get(int)}
* or {@link #has(int)} with an index M < N. The wrapper may return the right value,
* if the buffer happens to still contain index M, but more likely it will throw an
* {@link IllegalStateException}.
*
* <p/>
* If <code>autoAdvance</code> is false, you must be diligent and call {@link #advanceTo(int)}
* at the appropriate times to ensure that the internal buffer is not unnecessarily resized
* and reallocated.
*
* @param inputStream The input stream to wrap. The input stream will not be closed by the
* wrapper.
* @param bufferSize The initial size for the internal buffer. The buffer size should be
* carefully chosen to avoid resizing and reallocating the internal buffer.
* The internal buffer size used will be the least power of two greater
* than this parameter.
* @param autoAdvance Determines the behavior when you need to read an index that is beyond
* the internal buffer size. If true, the internal buffer will shift so
* that the requested index becomes the first element. If false,
* the internal buffer size will grow to the smallest power of 2 which is
* greater than the requested index.
*/
public InputStreamBuffer(final InputStream inputStream, int bufferSize,
final boolean autoAdvance) {
mInputStream = inputStream;
if (bufferSize <= 0) {
throw new IllegalArgumentException(
String.format("Buffer size %d must be positive.", bufferSize));
}
bufferSize = leastPowerOf2(bufferSize);
mBuffer = new byte[bufferSize];
mAutoAdvance = autoAdvance;
}
/**
* Attempt to get byte at the requested index from the wrapped input stream. If the internal
* buffer contains the requested index, return immediately. If the index is less than the
* head of the buffer, or the index is greater or equal to the size of the wrapped input stream,
* a runtime exception is thrown.
*
* <p/>
* If the index is not in the internal buffer, but it can be requested from the input stream,
* {@link #fill(int)} will be called first, and the byte at the index returned.
*
* <p/>
* You should always call {@link #has(int)} with the same index, unless you are sure that no
* exceptions will be thrown as described above.
*
* <p/>
* Consider calling {@link #advanceTo(int)} if you know that you will never request a lesser
* index in the future.
* @param index The requested index.
* @return The byte at that index.
*/
public byte get(final int index) throws IllegalStateException, IndexOutOfBoundsException {
Trace.beginSection("get");
if (has(index)) {
final int i = index - mOffset;
Trace.endSection();
return mBuffer[i];
} else {
Trace.endSection();
throw new IndexOutOfBoundsException(
String.format("Index %d beyond length.", index));
}
}
/**
* Attempt to return whether the requested index is within the size of the wrapped input
* stream. One side effect is {@link #fill(int)} will be called.
*
* <p/>
* If this method returns true, it is guaranteed that {@link #get(int)} with the same index
* will not fail. That means that if the requested index is within the size of the wrapped
* input stream, but the index is less than the head of the internal buffer,
* a runtime exception is thrown.
*
* <p/>
* See {@link #get(int)} for caveats. A lot of the same warnings about exceptions and
* <code>advanceTo()</code> apply.
* @param index The requested index.
* @return True if requested index is within the size of the wrapped input stream. False if
* the index is beyond the size.
*/
public boolean has(final int index) throws IllegalStateException, IndexOutOfBoundsException {
Trace.beginSection("has");
if (index < mOffset) {
Trace.endSection();
throw new IllegalStateException(
String.format("Index %d is before buffer %d", index, mOffset));
}
final int i = index - mOffset;
// Requested index not in internal buffer.
if (i >= mFilled || i >= mBuffer.length) {
Trace.endSection();
return fill(index);
}
Trace.endSection();
return true;
}
/**
* Attempts to advance the head of the buffer to the requested index. If the index is less
* than the head of the buffer, the internal state will not be changed.
*
* <p/>
* Advancing does not fill the internal buffer. The next {@link #get(int)} or
* {@link #has(int)} call will fill the buffer.
*/
public void advanceTo(final int index) throws IllegalStateException, IndexOutOfBoundsException {
Trace.beginSection("advance to");
final int i = index - mOffset;
if (i <= 0) {
// noop
Trace.endSection();
return;
} else if (i < mFilled) {
// Shift elements starting at i to position 0.
shiftToBeginning(i);
mOffset = index;
mFilled = mFilled - i;
} else if (mInputStream != null) {
// Burn some bytes from the input stream to match the new index.
int burn = i - mFilled;
boolean empty = false;
int fails = 0;
try {
while (burn > 0) {
final long burned = mInputStream.skip(burn);
if (burned <= 0) {
fails++;
} else {
burn -= burned;
}
if (fails >= 5) {
empty = true;
break;
}
}
} catch (IOException ignored) {
empty = true;
}
if (empty) {
//Mark input stream as consumed.
mInputStream = null;
}
mOffset = index - burn;
mFilled = 0;
} else {
// Advancing beyond the input stream.
mOffset = index;
mFilled = 0;
}
if (Log.isLoggable(TAG, Log.DEBUG)) {
Log.d(TAG, String.format("advanceTo %d buffer: %s", i, this));
}
Trace.endSection();
}
/**
* Attempt to fill the internal buffer fully. The buffer will be modified such that the
* requested index will always be in the buffer. If the index is less
* than the head of the buffer, a runtime exception is thrown.
*
* <p/>
* If the requested index is already in bounds of the buffer, then the buffer will just be
* filled.
*
* <p/>
* Otherwise, if <code>autoAdvance</code> was set to true in the constructor,
* {@link #advanceTo(int)} will be called with the requested index,
* and then the buffer filled. If <code>autoAdvance</code> was set to false,
* we allocate a single larger buffer of a least multiple-of-two size that can contain the
* requested index. The elements in the old buffer are copied over to the head of the new
* buffer. Then the entire buffer is filled.
* @param index The requested index.
* @return True if the byte at the requested index has been filled. False if the wrapped
* input stream ends before we reach the index.
*/
private boolean fill(final int index) {
Trace.beginSection("fill");
if (index < mOffset) {
Trace.endSection();
throw new IllegalStateException(
String.format("Index %d is before buffer %d", index, mOffset));
}
int i = index - mOffset;
// Can't fill buffer anymore if input stream is consumed.
if (mInputStream == null) {
Trace.endSection();
return false;
}
// Increase buffer size if necessary.
int length = i + 1;
if (length > mBuffer.length) {
if (mAutoAdvance) {
advanceTo(index);
i = index - mOffset;
} else {
length = leastPowerOf2(length);
Log.w(TAG, String.format(
"Increasing buffer length from %d to %d. Bad buffer size chosen, "
+ "or advanceTo() not called.",
mBuffer.length, length));
mBuffer = Arrays.copyOf(mBuffer, length);
}
}
// Read from input stream to fill buffer.
int read = -1;
try {
read = mInputStream.read(mBuffer, mFilled, mBuffer.length - mFilled);
} catch (IOException ignored) {
}
if (read != -1) {
mFilled = mFilled + read;
} else {
// Mark input stream as consumed.
mInputStream = null;
}
if (Log.isLoggable(TAG, Log.DEBUG)) {
Log.d(TAG, String.format("fill %d buffer: %s", i, this));
}
Trace.endSection();
return i < mFilled;
}
/**
* Modify the internal buffer so that all the bytes are shifted towards the head by
* <code>i</code>. In other words, the byte at index <code>i</code> will now be at index
* <code>0</code>. Bytes from a lesser index are tossed.
* @param i How much to shift left.
*/
private void shiftToBeginning(final int i) {
if (i >= mBuffer.length) {
throw new IndexOutOfBoundsException(
String.format("Index %d out of bounds. Length %d", i, mBuffer.length));
}
for (int j = 0; j + i < mFilled; j++) {
mBuffer[j] = mBuffer[j + i];
}
}
@Override
public String toString() {
if (DEBUG) {
return toDebugString();
}
return String.format("+%d+%d [%d]", mOffset, mBuffer.length, mFilled);
}
public String toDebugString() {
Trace.beginSection("to debug string");
final StringBuilder sb = new StringBuilder();
sb.append("+").append(mOffset);
sb.append("+").append(mBuffer.length);
sb.append(" [");
for (int i = 0; i < mBuffer.length && i < DEBUG_MAX_BUFFER_SIZE; i++) {
if (i > 0) {
sb.append(",");
}
if (i < mFilled) {
sb.append(String.format("%02X", mBuffer[i]));
} else {
sb.append("__");
}
}
if (mInputStream != null) {
sb.append("...");
}
sb.append("]");
Trace.endSection();
return sb.toString();
}
/**
* Calculate the least power of two greater than or equal to the input.
*/
private static int leastPowerOf2(int n) {
n--;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n++;
return n;
}
} |
