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