XBAT logic in NPOIFS was incorrect - it's a chain of doubly indirect, not singly indirect BATs. Start to correct

git-svn-id: https://svn.apache.org/repos/asf/poi/trunk@1053495 13f79535-47bb-0310-9956-ffa450edef68

3 files changed, 42 insertions, 32 deletions

diff --git a/src/java/org/apache/poi/poifs/filesystem/NDocumentInputStream.java b/src/java/org/apache/poi/poifs/filesystem/NDocumentInputStream.java
index 52c06f808b..2595ba0259 100644
--- a/src/java/org/apache/poi/poifs/filesystem/NDocumentInputStream.java
+++ b/src/java/org/apache/poi/poifs/filesystem/NDocumentInputStream.java
@@ -29,8 +29,6 @@ import org.apache.poi.util.LittleEndianInput;
 /**
  * This class provides methods to read a DocumentEntry managed by a
  * {@link POIFSFileSystem} instance.
- *
- * @author Marc Johnson (mjohnson at apache dot org)
  */
 public final class NDocumentInputStream extends InputStream implements LittleEndianInput {
 	/** returned by read operations if we're at end of document */
diff --git a/src/java/org/apache/poi/poifs/filesystem/NPOIFSFileSystem.java b/src/java/org/apache/poi/poifs/filesystem/NPOIFSFileSystem.java
index a397136c20..9f491313ec 100644
--- a/src/java/org/apache/poi/poifs/filesystem/NPOIFSFileSystem.java
+++ b/src/java/org/apache/poi/poifs/filesystem/NPOIFSFileSystem.java
@@ -77,6 +77,7 @@ public class NPOIFSFileSystem extends BlockStore
    
     private NPOIFSMiniStore _mini_store;
     private NPropertyTable  _property_table;
+    private List<BATBlock>  _xbat_blocks;
     private List<BATBlock>  _bat_blocks;
     private HeaderBlock     _header;
     private DirectoryNode   _root;
@@ -98,6 +99,7 @@ public class NPOIFSFileSystem extends BlockStore
         _header         = new HeaderBlock(bigBlockSize);
         _property_table = new NPropertyTable(_header);
         _mini_store     = new NPOIFSMiniStore(this, _property_table.getRoot(), new ArrayList<BATBlock>(), _header);
+        _xbat_blocks     = new ArrayList<BATBlock>();
         _bat_blocks     = new ArrayList<BATBlock>();
         _root           = null;
     }
@@ -264,14 +266,10 @@ public class NPOIFSFileSystem extends BlockStore
        
        // Read the FAT blocks
        for(int fatAt : _header.getBATArray()) {
-          loopDetector.claim(fatAt);
-          ByteBuffer fatData = getBlockAt(fatAt);
-          BATBlock bat = BATBlock.createBATBlock(bigBlockSize, fatData);
-          bat.setOurBlockIndex(fatAt);
-          _bat_blocks.add(bat);
+          readBAT(fatAt, loopDetector);
        }
        
-       // Now read the XFAT blocks
+       // Now read the XFAT blocks, and the FATs within them
        BATBlock xfat; 
        int nextAt = _header.getXBATIndex();
        for(int i=0; i<_header.getXBATCount(); i++) {
@@ -280,8 +278,13 @@ public class NPOIFSFileSystem extends BlockStore
           xfat = BATBlock.createBATBlock(bigBlockSize, fatData);
           xfat.setOurBlockIndex(nextAt);
           nextAt = xfat.getValueAt(bigBlockSize.getXBATEntriesPerBlock());
+          _xbat_blocks.add(xfat);
           
-          _bat_blocks.add(xfat);
+          for(int j=0; j<bigBlockSize.getXBATEntriesPerBlock(); j++) {
+             int fatAt = xfat.getValueAt(j);
+             if(fatAt == POIFSConstants.UNUSED_BLOCK) break;
+             readBAT(fatAt, loopDetector);
+          }
        }
        
        // We're now able to load steams
@@ -302,6 +305,13 @@ public class NPOIFSFileSystem extends BlockStore
           nextAt = getNextBlock(nextAt);  
        }
     }
+    private void readBAT(int batAt, ChainLoopDetector loopDetector) throws IOException {
+       loopDetector.claim(batAt);
+       ByteBuffer fatData = getBlockAt(batAt);
+       BATBlock bat = BATBlock.createBATBlock(bigBlockSize, fatData);
+       bat.setOurBlockIndex(batAt);
+       _bat_blocks.add(bat);
+    }
     
     /**
      * Load the block at the given offset.
diff --git a/src/java/org/apache/poi/poifs/storage/BATBlock.java b/src/java/org/apache/poi/poifs/storage/BATBlock.java
index 36da6dc38c..3319839f16 100644
--- a/src/java/org/apache/poi/poifs/storage/BATBlock.java
+++ b/src/java/org/apache/poi/poifs/storage/BATBlock.java
@@ -234,16 +234,33 @@ public final class BATBlock extends BigBlock {
     /**
      * Calculates the maximum size of a file which is addressable given the
      *  number of FAT (BAT and XBAT) sectors specified.
-     * The actual file size will be between [size of fatCount-1 blocks] and
-     *  [size of fatCount blocks].
-     * For 512 byte block sizes, this means we may over-estimate by up to 65kb.
-     * For 4096 byte block sizes, this means we may over-estimate by up to 4mb
+     *  
+     * For files with 109 or fewer BATs:
+     *  The actual file size will be between [size of fatCount-1 blocks] and
+     *   [size of fatCount blocks].
+     *  For 512 byte block sizes, this means we may over-estimate by up to 65kb.
+     *  For 4096 byte block sizes, this means we may over-estimate by up to 4mb
+     *  
+     * For files with more than 109 BATs (i.e. has XBATs):
+     *  Each XBAT can hold 127/1023 BATs, which in turn address 128/1024 blocks.
+     *  For 512 byte block sizes, this means we may over-estimate by up to 8mb
+     *  For 4096 byte block sizes, this means we may over-estimate by up to 4gb,
+     *   but only for files of more than 436mb in size
      */
     public static int calculateMaximumSize(final POIFSBigBlockSize bigBlockSize,
           final int numBAT, final int numXBAT) {
        int size = 1; // Header isn't FAT addressed
+       
+       // The header contains up to 109 BATs, each of which can
+       //  address 128/1024 blocks
        size += (numBAT * bigBlockSize.getBATEntriesPerBlock());
-       size += (numXBAT * bigBlockSize.getXBATEntriesPerBlock());
+       
+       // Each XBAT holds up to 127/1024 BATs, each of which can
+       //  address 128/1024 blocks
+       size += (numXBAT * bigBlockSize.getXBATEntriesPerBlock() *
+                          bigBlockSize.getBATEntriesPerBlock());
+       
+       // So far we've been in sector counts, turn into bytes
        return size * bigBlockSize.getBigBlockSize();
     }
     public static int calculateMaximumSize(final HeaderBlock header)
@@ -260,24 +277,9 @@ public final class BATBlock extends BigBlock {
                 final HeaderBlock header, final List<BATBlock> bats) {
        POIFSBigBlockSize bigBlockSize = header.getBigBlockSize();
        
-       // Are we in the BAT or XBAT range
-       int batRangeEndsAt = bigBlockSize.getBATEntriesPerBlock() *
-                            header.getBATCount();
-       
-       if(offset < batRangeEndsAt) {
-          int whichBAT = (int)Math.floor(offset / bigBlockSize.getBATEntriesPerBlock());
-          int index = offset % bigBlockSize.getBATEntriesPerBlock();
-          return new BATBlockAndIndex( index, bats.get(whichBAT) );
-       }
-       
-       // XBATs hold slightly less
-       int relOffset = offset - batRangeEndsAt;
-       int whichXBAT = (int)Math.floor(relOffset / bigBlockSize.getXBATEntriesPerBlock());
-       int index = relOffset % bigBlockSize.getXBATEntriesPerBlock();
-       return new BATBlockAndIndex(
-             index,
-             bats.get(header.getBATCount() + whichXBAT)
-       );
+       int whichBAT = (int)Math.floor(offset / bigBlockSize.getBATEntriesPerBlock());
+       int index = offset % bigBlockSize.getBATEntriesPerBlock();
+       return new BATBlockAndIndex( index, bats.get(whichBAT) );
     }
     
     /**