1 2 /* ==================================================================== 3 * The Apache Software License, Version 1.1 4 * 5 * Copyright (c) 2002 The Apache Software Foundation. All rights 6 * reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in 17 * the documentation and/or other materials provided with the 18 * distribution. 19 * 20 * 3. The end-user documentation included with the redistribution, 21 * if any, must include the following acknowledgment: 22 * "This product includes software developed by the 23 * Apache Software Foundation (http://www.apache.org/)." 24 * Alternately, this acknowledgment may appear in the software itself, 25 * if and wherever such third-party acknowledgments normally appear. 26 * 27 * 4. The names "Apache" and "Apache Software Foundation" and 28 * "Apache POI" must not be used to endorse or promote products 29 * derived from this software without prior written permission. For 30 * written permission, please contact apache@apache.org. 31 * 32 * 5. Products derived from this software may not be called "Apache", 33 * "Apache POI", nor may "Apache" appear in their name, without 34 * prior written permission of the Apache Software Foundation. 35 * 36 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED 37 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 38 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 39 * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR 40 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 41 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 42 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF 43 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 44 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 45 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 46 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 47 * SUCH DAMAGE. 48 * ==================================================================== 49 * 50 * This software consists of voluntary contributions made by many 51 * individuals on behalf of the Apache Software Foundation. For more 52 * information on the Apache Software Foundation, please see 53 * <http://www.apache.org/>. 54 */ 55 56 package org.apache.poi.poifs.storage; 57 58 import java.io.IOException; 59 import java.io.OutputStream; 60 61 import java.util.*; 62 63 import org.apache.poi.poifs.common.POIFSConstants; 64 import org.apache.poi.util.IntList; 65 import org.apache.poi.util.LittleEndian; 66 import org.apache.poi.util.LittleEndianConsts; 67 68 /** 69 * This class manages and creates the Block Allocation Table, which is 70 * basically a set of linked lists of block indices. 71 * <P> 72 * Each block of the filesystem has an index. The first block, the 73 * header, is skipped; the first block after the header is index 0, 74 * the next is index 1, and so on. 75 * <P> 76 * A block's index is also its index into the Block Allocation 77 * Table. The entry that it finds in the Block Allocation Table is the 78 * index of the next block in the linked list of blocks making up a 79 * file, or it is set to -2: end of list. 80 * 81 * @author Marc Johnson (mjohnson at apache dot org) 82 */ 83 84 public class BlockAllocationTableReader 85 { 86 private IntList _entries; 87 88 /** 89 * create a BlockAllocationTableReader for an existing filesystem. Side 90 * effect: when this method finishes, the BAT blocks will have 91 * been removed from the raw block list, and any blocks labeled as 92 * 'unused' in the block allocation table will also have been 93 * removed from the raw block list. 94 * 95 * @param block_count the number of BAT blocks making up the block 96 * allocation table 97 * @param block_array the array of BAT block indices from the 98 * filesystem's header 99 * @param xbat_count the number of XBAT blocks 100 * @param xbat_index the index of the first XBAT block 101 * @param raw_block_list the list of RawDataBlocks 102 * 103 * @exception IOException if, in trying to create the table, we 104 * encounter logic errors 105 */ 106 107 public BlockAllocationTableReader(final int block_count, 108 final int [] block_array, 109 final int xbat_count, 110 final int xbat_index, 111 final BlockList raw_block_list) 112 throws IOException 113 { 114 this(); 115 if (block_count <= 0) 116 { 117 throw new IOException( 118 "Illegal block count; minimum count is 1, got " + block_count 119 + " instead"); 120 } 121 122 // acquire raw data blocks containing the BAT block data 123 RawDataBlock blocks[] = new RawDataBlock[ block_count ]; 124 int limit = Math.min(block_count, block_array.length); 125 int block_index; 126 127 for (block_index = 0; block_index < limit; block_index++) 128 { 129 blocks[ block_index ] = 130 ( Rawremoveock ) raw_block_list 131 .remove(block_array[ block_index ]); 132 } 133 if (block_index < block_count) 134 { 135 136 // must have extended blocks 137 if (xbat_index < 0) 138 { 139 throw new IOException( 140 "BAT count exceeds limit, yet XBAT index indicates no valid entries"); 141 } 142 int chain_index = xbat_index; 143 int max_entries_per_block = BATBlock.entriesPerXBATBlock(); 144 int chain_index_offset = BATBlock.getXBATChainOffset(); 145 146 for (int j = 0; j < xbat_count; j++) 147 { 148 limit = Math.min(block_count - block_index, 149 max_entries_per_block); 150 byte[] data = raw_block_list.remove(chain_index).getData(); 151 int offset = 0; 152 153 for (int k = 0; k < limit; k++) 154 { 155 blocks[ block_index++ ] = 156 ( Rawremoveock ) raw_block_list 157 .remove(LittleEndian.getInt(data, offset)); 158 offset += LittleEndianConsts.INT_SIZE; 159 } 160 chain_index = LittleEndian.getInt(data, chain_index_offset); 161 if (chain_index == POIFSConstants.END_OF_CHAIN) 162 { 163 break; 164 } 165 } 166 } 167 if (block_index != block_count) 168 { 169 throw new IOException("Could not find all blocks"); 170 } 171 172 // now that we have all of the raw data blocks, go through and 173 // create the indices 174 setEntries(blocks, raw_block_list); 175 } 176 177 /** 178 * create a BlockAllocationTableReader from an array of raw data blocks 179 * 180 * @param blocks the raw data 181 * @param raw_block_list the list holding the managed blocks 182 * 183 * @exception IOException 184 */ 185 186 BlockAllocationTableReader(final ListManagedBlock [] blocks, 187 final BlockList raw_block_list) 188 throws IOException 189 { 190 this(); 191 setEntries(blocks, raw_block_list); 192 } 193 194 /** 195 * Constructor BlockAllocationTableReader 196 * 197 * 198 */ 199 200 BlockAllocationTableReader() 201 { 202 _entries = new IntList(); 203 } 204 205 /** 206 * walk the entries from a specified point and return the 207 * associated blocks. The associated blocks are removed from the 208 * block list 209 * 210 * @param startBlock the first block in the chain 211 * @param blockList the raw data block list 212 * 213 * @return array of ListManagedBlocks, in their correct order 214 * 215 * @exception IOException if there is a problem acquiring the blocks 216 */ 217 218 ListManagedBlock [] fetchBlocks(final int startBlock, 219 final BlockList blockList) 220 throws IOException 221 { 222 List blocks = new ArrayList(); 223 int currentBlock = startBlock; 224 225 while (currentBlock != POIFSConstants.END_OF_CHAIN) 226 { 227 blocks.add(blockList.remove(currentBlock)); 228 currentBlock = _entries.get(currentBlock); 229 } 230 return ( ListManagedBlock [] ) blocks 231 .toArray(new ListManagedBlock[ 0 ]); 232 } 233 234 // methods for debugging reader 235 236 /** 237 * determine whether the block specified by index is used or not 238 * 239 * @param index index of block in question 240 * 241 * @return true if the specific block is used, else false 242 */ 243 244 boolean isUsed(final int index) 245 { 246 boolean rval = false; 247 248 try 249 { 250 rval = _entries.get(index) != -1; 251 } 252 catch (IndexOutOfBoundsException ignored) 253 { 254 } 255 return rval; 256 } 257 258 /** 259 * return the next block index 260 * 261 * @param index of the current block 262 * 263 * @return index of the next block (may be 264 * POIFSConstants.END_OF_CHAIN, indicating end of chain 265 * (duh)) 266 * 267 * @exception IOException if the current block is unused 268 */ 269 270 int getNextBlockIndex(final int index) 271 throws IOException 272 { 273 if (isUsed(index)) 274 { 275 return _entries.get(index); 276 } 277 else 278 { 279 throw new IOException("index " + index + " is unused"); 280 } 281 } 282 283 /** 284 * Convert an array of blocks into a set of integer indices 285 * 286 * @param blocks the array of blocks containing the indices 287 * @param raw_blocks the list of blocks being managed. Unused 288 * blocks will be eliminated from the list 289 * 290 * @exception IOException 291 */ 292 293 private void setEntries(final ListManagedBlock [] blocks, 294 final BlockList raw_blocks) 295 throws IOException 296 { 297 int limit = BATBlock.entriesPerBlock(); 298 299 for (int block_index = 0; block_index < blocks.length; block_index++) 300 { 301 byte[] data = blocks[ block_index ].getData(); 302 int offset = 0; 303 304 for (int k = 0; k < limit; k++) 305 { 306 int entry = LittleEndian.getInt(data, offset); 307 308 if (entry == POIFSConstants.UNUSED_BLOCK) 309 { 310 raw_blocks.zap(_entries.size()); 311 } 312 _entries.add(entry); 313 offset += LittleEndianConsts.INT_SIZE; 314 } 315 316 // discard block 317 blocks[ block_index ] = null; 318 } 319 raw_blocks.setBAT(this); 320 } 321 } // end class BlockAllocationTableReader 322 323