1 /*
   2  * Copyright (c) 2000, 2003, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package javax.imageio.stream;
  27 
  28 import java.util.ArrayList;
  29 import java.io.InputStream;
  30 import java.io.OutputStream;
  31 import java.io.IOException;
  32 
  33 /**
  34  * Package-visible class consolidating common code for
  35  * <code>MemoryCacheImageInputStream</code> and
  36  * <code>MemoryCacheImageOutputStream</code>.
  37  * This class keeps an <code>ArrayList</code> of 8K blocks,
  38  * loaded sequentially.  Blocks may only be disposed of
  39  * from the index 0 forward.  As blocks are freed, the
  40  * corresponding entries in the array list are set to
  41  * <code>null</code>, but no compacting is performed.
  42  * This allows the index for each block to never change,
  43  * and the length of the cache is always the same as the
  44  * total amount of data ever cached.  Cached data is
  45  * therefore always contiguous from the point of last
  46  * disposal to the current length.
  47  *
  48  * <p> The total number of blocks resident in the cache must not
  49  * exceed <code>Integer.MAX_VALUE</code>.  In practice, the limit of
  50  * available memory will be exceeded long before this becomes an
  51  * issue, since a full cache would contain 8192*2^31 = 16 terabytes of
  52  * data.
  53  *
  54  * A <code>MemoryCache</code> may be reused after a call
  55  * to <code>reset()</code>.
  56  */
  57 class MemoryCache {
  58 
  59     private static final int BUFFER_LENGTH = 8192;
  60 
  61     private ArrayList<byte[]> cache = new ArrayList<>();
  62 
  63     private long cacheStart = 0L;
  64 
  65     /**
  66      * The largest position ever written to the cache.
  67      */
  68     private long length = 0L;
  69 
  70     private byte[] getCacheBlock(long blockNum) throws IOException {
  71         long blockOffset = blockNum - cacheStart;
  72         if (blockOffset > Integer.MAX_VALUE) {
  73             // This can only happen when the cache hits 16 terabytes of
  74             // contiguous data...
  75             throw new IOException("Cache addressing limit exceeded!");
  76         }
  77         return cache.get((int)blockOffset);
  78     }
  79 
  80     /**
  81      * Ensures that at least <code>pos</code> bytes are cached,
  82      * or the end of the source is reached.  The return value
  83      * is equal to the smaller of <code>pos</code> and the
  84      * length of the source.
  85      * 
  86      * @throws IOException if there is no more memory for cache
  87      */
  88     public long loadFromStream(InputStream stream, long pos)
  89         throws IOException {
  90         // We've already got enough data cached
  91         if (pos < length) {
  92             return pos;
  93         }
  94 
  95         int offset = (int)(length % BUFFER_LENGTH);
  96         byte [] buf = null;
  97 
  98         long len = pos - length;
  99         if (offset != 0) {
 100             buf = getCacheBlock(length/BUFFER_LENGTH);
 101         }
 102 
 103         while (len > 0) {
 104             if (buf == null) {
 105                 try {
 106                     buf = new byte[BUFFER_LENGTH];
 107                 } catch (OutOfMemoryError e) {
 108                     throw new IOException("No memory left for cache!");
 109                 }
 110                 offset = 0;
 111             }
 112 
 113             int left = BUFFER_LENGTH - offset;
 114             int nbytes = (int)Math.min(len, (long)left);
 115             nbytes = stream.read(buf, offset, nbytes);
 116             if (nbytes == -1) {
 117                 return length; // EOF
 118             }
 119 
 120             if (offset == 0) {
 121                 cache.add(buf);
 122             }
 123 
 124             len -= nbytes;
 125             length += nbytes;
 126             offset += nbytes;
 127 
 128             if (offset >= BUFFER_LENGTH) {
 129                 // we've filled the current buffer, so a new one will be
 130                 // allocated next time around (and offset will be reset to 0)
 131                 buf = null;
 132             }
 133         }
 134 
 135         return pos;
 136     }
 137 
 138     /**
 139      * Writes out a portion of the cache to an <code>OutputStream</code>.
 140      * This method preserves no state about the output stream, and does
 141      * not dispose of any blocks containing bytes written.  To dispose
 142      * blocks, use {@link #disposeBefore <code>disposeBefore()</code>}.
 143      *
 144      * @exception IndexOutOfBoundsException if any portion of
 145      * the requested data is not in the cache (including if <code>pos</code>
 146      * is in a block already disposed), or if either <code>pos</code> or
 147      * <code>len</code> is < 0.
 148      * @throws IOException if there is an I/O exception while writing to the
 149      * stream
 150      */
 151     public void writeToStream(OutputStream stream, long pos, long len)
 152         throws IOException {
 153         if (pos + len > length) {
 154             throw new IndexOutOfBoundsException("Argument out of cache");
 155         }
 156         if ((pos < 0) || (len < 0)) {
 157             throw new IndexOutOfBoundsException("Negative pos or len");
 158         }
 159         if (len == 0) {
 160             return;
 161         }
 162 
 163         long bufIndex = pos/BUFFER_LENGTH;
 164         if (bufIndex < cacheStart) {
 165             throw new IndexOutOfBoundsException("pos already disposed");
 166         }
 167         int offset = (int)(pos % BUFFER_LENGTH);
 168 
 169         byte[] buf = getCacheBlock(bufIndex++);
 170         while (len > 0) {
 171             if (buf == null) {
 172                 buf = getCacheBlock(bufIndex++);
 173                 offset = 0;
 174             }
 175             int nbytes = (int)Math.min(len, (long)(BUFFER_LENGTH - offset));
 176             stream.write(buf, offset, nbytes);
 177             buf = null;
 178             len -= nbytes;
 179         }
 180     }
 181 
 182     /**
 183      * Ensure that there is space to write a byte at the given position.
 184      * 
 185      * throws IOException if there is no more memory left for cache
 186      */
 187     private void pad(long pos) throws IOException {
 188         long currIndex = cacheStart + cache.size() - 1;
 189         long lastIndex = pos/BUFFER_LENGTH;
 190         long numNewBuffers = lastIndex - currIndex;
 191         for (long i = 0; i < numNewBuffers; i++) {
 192             try {
 193                 cache.add(new byte[BUFFER_LENGTH]);
 194             } catch (OutOfMemoryError e) {
 195                 throw new IOException("No memory left for cache!");
 196             }
 197         }
 198     }
 199 
 200     /**
 201      * Overwrites and/or appends the cache from a byte array.
 202      * The length of the cache will be extended as needed to hold
 203      * the incoming data.
 204      *
 205      * @param b an array of bytes containing data to be written.
 206      * @param off the starting offset within the data array.
 207      * @param len the number of bytes to be written.
 208      * @param pos the cache position at which to begin writing.
 209      *
 210      * @exception NullPointerException if <code>b</code> is <code>null</code>.
 211      * @exception IndexOutOfBoundsException if <code>off</code>,
 212      * <code>len</code>, or <code>pos</code> are negative,
 213      * or if <code>off+len > b.length</code>.
 214      * @throws IOException if there is an I/O error while writing to the cache
 215      */
 216     public void write(byte[] b, int off, int len, long pos)
 217         throws IOException {
 218         if (b == null) {
 219             throw new NullPointerException("b == null!");
 220         }
 221         // Fix 4430357 - if off + len < 0, overflow occurred
 222         if ((off < 0) || (len < 0) || (pos < 0) ||
 223             (off + len > b.length) || (off + len < 0)) {
 224             throw new IndexOutOfBoundsException();
 225         }
 226 
 227         // Ensure there is space for the incoming data
 228         long lastPos = pos + len - 1;
 229         if (lastPos >= length) {
 230             pad(lastPos);
 231             length = lastPos + 1;
 232         }
 233 
 234         // Copy the data into the cache, block by block
 235         int offset = (int)(pos % BUFFER_LENGTH);
 236         while (len > 0) {
 237             byte[] buf = getCacheBlock(pos/BUFFER_LENGTH);
 238             int nbytes = Math.min(len, BUFFER_LENGTH - offset);
 239             System.arraycopy(b, off, buf, offset, nbytes);
 240 
 241             pos += nbytes;
 242             off += nbytes;
 243             len -= nbytes;
 244             offset = 0; // Always after the first time
 245         }
 246     }
 247 
 248     /**
 249      * Overwrites or appends a single byte to the cache.
 250      * The length of the cache will be extended as needed to hold
 251      * the incoming data.
 252      *
 253      * @param b an <code>int</code> whose 8 least significant bits
 254      * will be written.
 255      * @param pos the cache position at which to begin writing.
 256      *
 257      * @exception IndexOutOfBoundsException if <code>pos</code> is negative.
 258      * @throws IOException if there is an I/O error while writing to the cache
 259      */
 260     public void write(int b, long pos) throws IOException {
 261         if (pos < 0) {
 262             throw new ArrayIndexOutOfBoundsException("pos < 0");
 263         }
 264 
 265         // Ensure there is space for the incoming data
 266         if (pos >= length) {
 267             pad(pos);
 268             length = pos + 1;
 269         }
 270 
 271         // Insert the data.
 272         byte[] buf = getCacheBlock(pos/BUFFER_LENGTH);
 273         int offset = (int)(pos % BUFFER_LENGTH);
 274         buf[offset] = (byte)b;
 275     }
 276 
 277     /**
 278      * Returns the total length of data that has been cached,
 279      * regardless of whether any early blocks have been disposed.
 280      * This value will only ever increase.
 281      */
 282     public long getLength() {
 283         return length;
 284     }
 285 
 286     /**
 287      * Returns the single byte at the given position, as an
 288      * <code>int</code>.  Returns -1 if this position has
 289      * not been cached or has been disposed.
 290      * 
 291      * @throws IOException if an I/O error occurs while reading from the byte
 292      * array
 293      */
 294     public int read(long pos) throws IOException {
 295         if (pos >= length) {
 296             return -1;
 297         }
 298 
 299         byte[] buf = getCacheBlock(pos/BUFFER_LENGTH);
 300         if (buf == null) {
 301             return -1;
 302         }
 303 
 304         return buf[(int)(pos % BUFFER_LENGTH)] & 0xff;
 305     }
 306 
 307     /**
 308      * Copy <code>len</code> bytes from the cache, starting
 309      * at cache position <code>pos</code>, into the array
 310      * <code>b</code> at offset <code>off</code>.
 311      *
 312      * @exception NullPointerException if b is <code>null</code>
 313      * @exception IndexOutOfBoundsException if <code>off</code>,
 314      * <code>len</code> or <code>pos</code> are negative or if
 315      * <code>off + len > b.length</code> or if any portion of the
 316      * requested data is not in the cache (including if
 317      * <code>pos</code> is in a block that has already been disposed).
 318      * @throws IOException if an I/O exception occurs while reading from the
 319      * byte array
 320      */
 321     public void read(byte[] b, int off, int len, long pos)
 322         throws IOException {
 323         if (b == null) {
 324             throw new NullPointerException("b == null!");
 325         }
 326         // Fix 4430357 - if off + len < 0, overflow occurred
 327         if ((off < 0) || (len < 0) || (pos < 0) ||
 328             (off + len > b.length) || (off + len < 0)) {
 329             throw new IndexOutOfBoundsException();
 330         }
 331         if (pos + len > length) {
 332             throw new IndexOutOfBoundsException();
 333         }
 334 
 335         long index = pos/BUFFER_LENGTH;
 336         int offset = (int)pos % BUFFER_LENGTH;
 337         while (len > 0) {
 338             int nbytes = Math.min(len, BUFFER_LENGTH - offset);
 339             byte[] buf = getCacheBlock(index++);
 340             System.arraycopy(buf, offset, b, off, nbytes);
 341 
 342             len -= nbytes;
 343             off += nbytes;
 344             offset = 0; // Always after the first time
 345         }
 346     }
 347 
 348     /**
 349      * Free the blocks up to the position <code>pos</code>.
 350      * The byte at <code>pos</code> remains available.
 351      *
 352      * @exception IndexOutOfBoundsException if <code>pos</code>
 353      * is in a block that has already been disposed.
 354      */
 355     public void disposeBefore(long pos) {
 356         long index = pos/BUFFER_LENGTH;
 357         if (index < cacheStart) {
 358             throw new IndexOutOfBoundsException("pos already disposed");
 359         }
 360         long numBlocks = Math.min(index - cacheStart, cache.size());
 361         for (long i = 0; i < numBlocks; i++) {
 362             cache.remove(0);
 363         }
 364         this.cacheStart = index;
 365     }
 366 
 367     /**
 368      * Erase the entire cache contents and reset the length to 0.
 369      * The cache object may subsequently be reused as though it had just
 370      * been allocated.
 371      */
 372     public void reset() {
 373         cache.clear();
 374         cacheStart = 0;
 375         length = 0L;
 376     }
 377  }