You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by sh...@apache.org on 2013/03/10 16:05:21 UTC

svn commit: r1454862 [13/49] - in /lucene/dev/branches/lucene4258: ./ dev-tools/ dev-tools/eclipse/ dev-tools/idea/.idea/ dev-tools/idea/.idea/libraries/ dev-tools/idea/lucene/demo/ dev-tools/idea/lucene/facet/ dev-tools/idea/lucene/highlighter/ dev-to...

Modified: lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/fst/FST.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/fst/FST.java?rev=1454862&r1=1454861&r2=1454862&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/fst/FST.java (original)
+++ lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/fst/FST.java Sun Mar 10 15:04:57 2013
@@ -29,17 +29,22 @@ import java.util.HashMap;
 import java.util.Map;
 
 import org.apache.lucene.codecs.CodecUtil;
+import org.apache.lucene.store.ByteArrayDataOutput;
 import org.apache.lucene.store.DataInput;
 import org.apache.lucene.store.DataOutput;
 import org.apache.lucene.store.InputStreamDataInput;
 import org.apache.lucene.store.OutputStreamDataOutput;
+import org.apache.lucene.store.RAMOutputStream;
 import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.Constants;
 import org.apache.lucene.util.IOUtils;
 import org.apache.lucene.util.IntsRef;
 import org.apache.lucene.util.PriorityQueue;
 import org.apache.lucene.util.fst.Builder.UnCompiledNode;
 import org.apache.lucene.util.packed.GrowableWriter;
 import org.apache.lucene.util.packed.PackedInts;
+//import java.io.Writer;
+//import java.io.OutputStreamWriter;
 
 // TODO: break this into WritableFST and ReadOnlyFST.. then
 // we can have subclasses of ReadOnlyFST to handle the
@@ -50,9 +55,6 @@ import org.apache.lucene.util.packed.Pac
 // job, ie, once we are at a 'suffix only', just store the
 // completion labels as a string not as a series of arcs.
 
-// TODO: maybe make an explicit thread state that holds
-// reusable stuff eg BytesReader, a scratch arc
-
 // NOTE: while the FST is able to represent a non-final
 // dead-end state (NON_FINAL_END_NODE=0), the layers above
 // (FSTEnum, Util) have problems with this!!
@@ -64,8 +66,6 @@ import org.apache.lucene.util.packed.Pac
  *  
  *  <p> See the {@link org.apache.lucene.util.fst package
  *      documentation} for some simple examples.
- *  <p><b>NOTE</b>: the FST cannot be larger than ~2.1 GB
- *  because it uses int to address the byte[].
  *
  * @lucene.experimental
  */
@@ -92,6 +92,8 @@ public final class FST<T> {
   // position:
   private final static int BIT_TARGET_DELTA = 1 << 6;
 
+  // We use this as a marker (because this one flag is
+  // illegal by itself ...):
   private final static byte ARCS_AS_FIXED_ARRAY = BIT_ARC_HAS_FINAL_OUTPUT;
 
   /**
@@ -124,36 +126,41 @@ public final class FST<T> {
   /** Added optional packed format. */
   private final static int VERSION_PACKED = 3;
 
-  private final static int VERSION_CURRENT = VERSION_PACKED;
+  /** Changed from int to vInt for encoding arc targets. 
+   *  Also changed maxBytesPerArc from int to vInt in the array case. */
+  private final static int VERSION_VINT_TARGET = 4;
+
+  private final static int VERSION_CURRENT = VERSION_VINT_TARGET;
 
   // Never serialized; just used to represent the virtual
   // final node w/ no arcs:
-  private final static int FINAL_END_NODE = -1;
+  private final static long FINAL_END_NODE = -1;
 
   // Never serialized; just used to represent the virtual
   // non-final node w/ no arcs:
-  private final static int NON_FINAL_END_NODE = 0;
+  private final static long NON_FINAL_END_NODE = 0;
 
   // if non-null, this FST accepts the empty string and
   // produces this output
   T emptyOutput;
-  private byte[] emptyOutputBytes;
 
-  // Not private to avoid synthetic access$NNN methods:
-  byte[] bytes;
-  int byteUpto = 0;
+  final BytesStore bytes;
 
-  private int startNode = -1;
+  private long startNode = -1;
 
   public final Outputs<T> outputs;
 
-  private int lastFrozenNode;
+  // Used for the BIT_TARGET_NEXT optimization (whereby
+  // instead of storing the address of the target node for
+  // a given arc, we mark a single bit noting that the next
+  // node in the byte[] is the target node):
+  private long lastFrozenNode;
 
   private final T NO_OUTPUT;
 
-  public int nodeCount;
-  public int arcCount;
-  public int arcWithOutputCount;
+  public long nodeCount;
+  public long arcCount;
+  public long arcWithOutputCount;
 
   private final boolean packed;
   private PackedInts.Reader nodeRefToAddress;
@@ -161,7 +168,7 @@ public final class FST<T> {
   /** If arc has this label then that arc is final/accepted */
   public static final int END_LABEL = -1;
 
-  private boolean allowArrayArcs = true;
+  private final boolean allowArrayArcs;
 
   private Arc<T> cachedRootArcs[];
 
@@ -172,19 +179,19 @@ public final class FST<T> {
 
     // From node (ord or address); currently only used when
     // building an FST w/ willPackFST=true:
-    int node;
+    long node;
 
     /** To node (ord or address) */
-    public int target;
+    public long target;
 
     byte flags;
     public T nextFinalOutput;
 
     // address (into the byte[]), or ord/address if label == END_LABEL
-    int nextArc;
+    long nextArc;
 
     // This is non-zero if current arcs are fixed array:
-    int posArcsStart;
+    long posArcsStart;
     int bytesPerArc;
     int arcIdx;
     int numArcs;
@@ -251,8 +258,6 @@ public final class FST<T> {
     return (flags & bit) != 0;
   }
 
-  private final BytesWriter writer;
-
   private GrowableWriter nodeAddress;
 
   // TODO: we could be smarter here, and prune periodically
@@ -260,47 +265,72 @@ public final class FST<T> {
   // clear early on:
   private GrowableWriter inCounts;
 
+  private final int version;
+
   // make a new empty FST, for building; Builder invokes
   // this ctor
-  FST(INPUT_TYPE inputType, Outputs<T> outputs, boolean willPackFST, float acceptableOverheadRatio) {
+  FST(INPUT_TYPE inputType, Outputs<T> outputs, boolean willPackFST, float acceptableOverheadRatio, boolean allowArrayArcs, int bytesPageBits) {
     this.inputType = inputType;
     this.outputs = outputs;
-    bytes = new byte[128];
+    this.allowArrayArcs = allowArrayArcs;
+    version = VERSION_CURRENT;
+    bytes = new BytesStore(bytesPageBits);
+    // pad: ensure no node gets address 0 which is reserved to mean
+    // the stop state w/ no arcs
+    bytes.writeByte((byte) 0);
     NO_OUTPUT = outputs.getNoOutput();
     if (willPackFST) {
-      nodeAddress = new GrowableWriter(PackedInts.bitsRequired(bytes.length - 1), 8, acceptableOverheadRatio);
+      nodeAddress = new GrowableWriter(15, 8, acceptableOverheadRatio);
       inCounts = new GrowableWriter(1, 8, acceptableOverheadRatio);
     } else {
       nodeAddress = null;
       inCounts = null;
     }
-    
-    writer = new DefaultBytesWriter();
 
     emptyOutput = null;
     packed = false;
     nodeRefToAddress = null;
   }
 
+  public static final int DEFAULT_MAX_BLOCK_BITS = Constants.JRE_IS_64BIT ? 30 : 28;
+
   /** Load a previously saved FST. */
   public FST(DataInput in, Outputs<T> outputs) throws IOException {
+    this(in, outputs, DEFAULT_MAX_BLOCK_BITS);
+  }
+
+  /** Load a previously saved FST; maxBlockBits allows you to
+   *  control the size of the byte[] pages used to hold the FST bytes. */
+  public FST(DataInput in, Outputs<T> outputs, int maxBlockBits) throws IOException {
     this.outputs = outputs;
-    writer = null;
+
+    if (maxBlockBits < 1 || maxBlockBits > 30) {
+      throw new IllegalArgumentException("maxBlockBits should be 1 .. 30; got " + maxBlockBits);
+    }
+
     // NOTE: only reads most recent format; we don't have
     // back-compat promise for FSTs (they are experimental):
-    CodecUtil.checkHeader(in, FILE_FORMAT_NAME, VERSION_PACKED, VERSION_PACKED);
+    version = CodecUtil.checkHeader(in, FILE_FORMAT_NAME, VERSION_PACKED, VERSION_VINT_TARGET);
     packed = in.readByte() == 1;
     if (in.readByte() == 1) {
       // accepts empty string
+      // 1 KB blocks:
+      BytesStore emptyBytes = new BytesStore(10);
       int numBytes = in.readVInt();
-      // messy
-      bytes = new byte[numBytes];
-      in.readBytes(bytes, 0, numBytes);
+      emptyBytes.copyBytes(in, numBytes);
+
+      // De-serialize empty-string output:
       BytesReader reader;
       if (packed) {
-        reader = getBytesReader(0);
+        reader = emptyBytes.getForwardReader();
       } else {
-        reader = getBytesReader(numBytes-1);
+        reader = emptyBytes.getReverseReader();
+        // NoOutputs uses 0 bytes when writing its output,
+        // so we have to check here else BytesStore gets
+        // angry:
+        if (numBytes > 0) {
+          reader.setPosition(numBytes-1);
+        }
       }
       emptyOutput = outputs.readFinalOutput(reader);
     } else {
@@ -325,16 +355,31 @@ public final class FST<T> {
     } else {
       nodeRefToAddress = null;
     }
-    startNode = in.readVInt();
-    nodeCount = in.readVInt();
-    arcCount = in.readVInt();
-    arcWithOutputCount = in.readVInt();
+    startNode = in.readVLong();
+    nodeCount = in.readVLong();
+    arcCount = in.readVLong();
+    arcWithOutputCount = in.readVLong();
 
-    bytes = new byte[in.readVInt()];
-    in.readBytes(bytes, 0, bytes.length);
+    long numBytes = in.readVLong();
+    bytes = new BytesStore(in, numBytes, 1<<maxBlockBits);
+    
     NO_OUTPUT = outputs.getNoOutput();
 
     cacheRootArcs();
+
+    // NOTE: bogus because this is only used during
+    // building; we need to break out mutable FST from
+    // immutable
+    allowArrayArcs = false;
+
+    /*
+    if (bytes.length == 665) {
+      Writer w = new OutputStreamWriter(new FileOutputStream("out.dot"), "UTF-8");
+      Util.toDot(this, w, false, false);
+      w.close();
+      System.out.println("Wrote FST to out.dot");
+    }
+    */
   }
 
   public INPUT_TYPE getInputType() {
@@ -342,8 +387,8 @@ public final class FST<T> {
   }
 
   /** Returns bytes used to represent the FST */
-  public int sizeInBytes() {
-    int size = bytes.length;
+  public long sizeInBytes() {
+    long size = bytes.getPosition();
     if (packed) {
       size += nodeRefToAddress.ramBytesUsed();
     } else if (nodeAddress != null) {
@@ -353,25 +398,23 @@ public final class FST<T> {
     return size;
   }
 
-  void finish(int startNode) throws IOException {
-    if (startNode == FINAL_END_NODE && emptyOutput != null) {
-      startNode = 0;
-    }
+  void finish(long startNode) throws IOException {
     if (this.startNode != -1) {
       throw new IllegalStateException("already finished");
     }
-    byte[] finalBytes = new byte[writer.getPosition()];
-    System.arraycopy(bytes, 0, finalBytes, 0, writer.getPosition());
-    bytes = finalBytes;
+    if (startNode == FINAL_END_NODE && emptyOutput != null) {
+      startNode = 0;
+    }
     this.startNode = startNode;
+    bytes.finish();
 
     cacheRootArcs();
   }
 
-  private int getNodeAddress(int node) {
+  private long getNodeAddress(long node) {
     if (nodeAddress != null) {
       // Deref
-      return (int) nodeAddress.get(node);
+      return nodeAddress.get((int) node);
     } else {
       // Straight
       return node;
@@ -384,7 +427,7 @@ public final class FST<T> {
     cachedRootArcs = (Arc<T>[]) new Arc[0x80];
     final Arc<T> arc = new Arc<T>();
     getFirstArc(arc);
-    final BytesReader in = getBytesReader(0);
+    final BytesReader in = getBytesReader();
     if (targetHasArcs(arc)) {
       readFirstRealTargetArc(arc.target, arc, in);
       while(true) {
@@ -412,26 +455,6 @@ public final class FST<T> {
     } else {
       emptyOutput = v;
     }
-
-    // TODO: this is messy -- replace with sillyBytesWriter; maybe make
-    // bytes private
-    final int posSave = writer.getPosition();
-    outputs.writeFinalOutput(emptyOutput, writer);
-    emptyOutputBytes = new byte[writer.getPosition()-posSave];
-
-    if (!packed) {
-      // reverse
-      final int stopAt = (writer.getPosition() - posSave)/2;
-      int upto = 0;
-      while(upto < stopAt) {
-        final byte b = bytes[posSave + upto];
-        bytes[posSave+upto] = bytes[writer.getPosition()-upto-1];
-        bytes[writer.getPosition()-upto-1] = b;
-        upto++;
-      }
-    }
-    System.arraycopy(bytes, posSave, emptyOutputBytes, 0, writer.getPosition()-posSave);
-    writer.setPosition(posSave);
   }
 
   public void save(DataOutput out) throws IOException {
@@ -453,7 +476,27 @@ public final class FST<T> {
     // TODO: really we should encode this as an arc, arriving
     // to the root node, instead of special casing here:
     if (emptyOutput != null) {
+      // Accepts empty string
       out.writeByte((byte) 1);
+
+      // Serialize empty-string output:
+      RAMOutputStream ros = new RAMOutputStream();
+      outputs.writeFinalOutput(emptyOutput, ros);
+      
+      byte[] emptyOutputBytes = new byte[(int) ros.getFilePointer()];
+      ros.writeTo(emptyOutputBytes, 0);
+
+      if (!packed) {
+        // reverse
+        final int stopAt = emptyOutputBytes.length/2;
+        int upto = 0;
+        while(upto < stopAt) {
+          final byte b = emptyOutputBytes[upto];
+          emptyOutputBytes[upto] = emptyOutputBytes[emptyOutputBytes.length-upto-1];
+          emptyOutputBytes[emptyOutputBytes.length-upto-1] = b;
+          upto++;
+        }
+      }
       out.writeVInt(emptyOutputBytes.length);
       out.writeBytes(emptyOutputBytes, 0, emptyOutputBytes.length);
     } else {
@@ -471,12 +514,13 @@ public final class FST<T> {
     if (packed) {
       ((PackedInts.Mutable) nodeRefToAddress).save(out);
     }
-    out.writeVInt(startNode);
-    out.writeVInt(nodeCount);
-    out.writeVInt(arcCount);
-    out.writeVInt(arcWithOutputCount);
-    out.writeVInt(bytes.length);
-    out.writeBytes(bytes, 0, bytes.length);
+    out.writeVLong(startNode);
+    out.writeVLong(nodeCount);
+    out.writeVLong(arcCount);
+    out.writeVLong(arcWithOutputCount);
+    long numBytes = bytes.getPosition();
+    out.writeVLong(numBytes);
+    bytes.writeTo(out);
   }
   
   /**
@@ -516,17 +560,16 @@ public final class FST<T> {
     }
   }
 
-  private void writeLabel(int v) throws IOException {
+  private void writeLabel(DataOutput out, int v) throws IOException {
     assert v >= 0: "v=" + v;
     if (inputType == INPUT_TYPE.BYTE1) {
       assert v <= 255: "v=" + v;
-      writer.writeByte((byte) v);
+      out.writeByte((byte) v);
     } else if (inputType == INPUT_TYPE.BYTE2) {
       assert v <= 65535: "v=" + v;
-      writer.writeShort((short) v);
+      out.writeShort((short) v);
     } else {
-      //writeInt(v);
-      writer.writeVInt(v);
+      out.writeVInt(v);
     }
   }
 
@@ -552,8 +595,9 @@ public final class FST<T> {
 
   // serializes new node by appending its bytes to the end
   // of the current byte[]
-  int addNode(Builder.UnCompiledNode<T> nodeIn) throws IOException {
-    //System.out.println("FST.addNode pos=" + writer.posWrite + " numArcs=" + nodeIn.numArcs);
+  long addNode(Builder.UnCompiledNode<T> nodeIn) throws IOException {
+
+    //System.out.println("FST.addNode pos=" + bytes.getPosition() + " numArcs=" + nodeIn.numArcs);
     if (nodeIn.numArcs == 0) {
       if (nodeIn.isFinal) {
         return FINAL_END_NODE;
@@ -562,38 +606,28 @@ public final class FST<T> {
       }
     }
 
-    int startAddress = writer.getPosition();
+    final long startAddress = bytes.getPosition();
     //System.out.println("  startAddr=" + startAddress);
 
     final boolean doFixedArray = shouldExpand(nodeIn);
-    final int fixedArrayStart;
     if (doFixedArray) {
+      //System.out.println("  fixedArray");
       if (bytesPerArc.length < nodeIn.numArcs) {
         bytesPerArc = new int[ArrayUtil.oversize(nodeIn.numArcs, 1)];
       }
-      // write a "false" first arc:
-      writer.writeByte(ARCS_AS_FIXED_ARRAY);
-      writer.writeVInt(nodeIn.numArcs);
-      // placeholder -- we'll come back and write the number
-      // of bytes per arc (int) here:
-      // TODO: we could make this a vInt instead
-      writer.writeInt(0);
-      fixedArrayStart = writer.getPosition();
-      //System.out.println("  do fixed arcs array arcsStart=" + fixedArrayStart);
-    } else {
-      fixedArrayStart = 0;
     }
 
     arcCount += nodeIn.numArcs;
     
     final int lastArc = nodeIn.numArcs-1;
 
-    int lastArcStart = writer.getPosition();
+    long lastArcStart = bytes.getPosition();
     int maxBytesPerArc = 0;
     for(int arcIdx=0;arcIdx<nodeIn.numArcs;arcIdx++) {
       final Builder.Arc<T> arc = nodeIn.arcs[arcIdx];
       final Builder.CompiledNode target = (Builder.CompiledNode) arc.target;
       int flags = 0;
+      //System.out.println("  arc " + arcIdx + " label=" + arc.label + " -> target=" + target.node);
 
       if (arcIdx == lastArc) {
         flags += BIT_LAST_ARC;
@@ -620,111 +654,135 @@ public final class FST<T> {
       if (!targetHasArcs) {
         flags += BIT_STOP_NODE;
       } else if (inCounts != null) {
-        inCounts.set(target.node, inCounts.get(target.node) + 1);
+        inCounts.set((int) target.node, inCounts.get((int) target.node) + 1);
       }
 
       if (arc.output != NO_OUTPUT) {
         flags += BIT_ARC_HAS_OUTPUT;
       }
 
-      writer.writeByte((byte) flags);
-      writeLabel(arc.label);
+      bytes.writeByte((byte) flags);
+      writeLabel(bytes, arc.label);
 
-      // System.out.println("  write arc: label=" + (char) arc.label + " flags=" + flags + " target=" + target.node + " pos=" + writer.posWrite + " output=" + outputs.outputToString(arc.output));
+      // System.out.println("  write arc: label=" + (char) arc.label + " flags=" + flags + " target=" + target.node + " pos=" + bytes.getPosition() + " output=" + outputs.outputToString(arc.output));
 
       if (arc.output != NO_OUTPUT) {
-        outputs.write(arc.output, writer);
+        outputs.write(arc.output, bytes);
         //System.out.println("    write output");
         arcWithOutputCount++;
       }
 
       if (arc.nextFinalOutput != NO_OUTPUT) {
         //System.out.println("    write final output");
-        outputs.writeFinalOutput(arc.nextFinalOutput, writer);
+        outputs.writeFinalOutput(arc.nextFinalOutput, bytes);
       }
 
       if (targetHasArcs && (flags & BIT_TARGET_NEXT) == 0) {
         assert target.node > 0;
         //System.out.println("    write target");
-        writer.writeInt(target.node);
+        bytes.writeVLong(target.node);
       }
 
       // just write the arcs "like normal" on first pass,
       // but record how many bytes each one took, and max
       // byte size:
       if (doFixedArray) {
-        bytesPerArc[arcIdx] = writer.getPosition() - lastArcStart;
-        lastArcStart = writer.getPosition();
+        bytesPerArc[arcIdx] = (int) (bytes.getPosition() - lastArcStart);
+        lastArcStart = bytes.getPosition();
         maxBytesPerArc = Math.max(maxBytesPerArc, bytesPerArc[arcIdx]);
         //System.out.println("    bytes=" + bytesPerArc[arcIdx]);
       }
     }
-
-    // TODO: if arc'd arrays will be "too wasteful" by some
-    // measure, eg if arcs have vastly different sized
-    // outputs, then we should selectively disable array for
-    // such cases
+    
+    // TODO: try to avoid wasteful cases: disable doFixedArray in that case
+    /* 
+     * 
+     * LUCENE-4682: what is a fair heuristic here?
+     * It could involve some of these:
+     * 1. how "busy" the node is: nodeIn.inputCount relative to frontier[0].inputCount?
+     * 2. how much binSearch saves over scan: nodeIn.numArcs
+     * 3. waste: numBytes vs numBytesExpanded
+     * 
+     * the one below just looks at #3
+    if (doFixedArray) {
+      // rough heuristic: make this 1.25 "waste factor" a parameter to the phd ctor????
+      int numBytes = lastArcStart - startAddress;
+      int numBytesExpanded = maxBytesPerArc * nodeIn.numArcs;
+      if (numBytesExpanded > numBytes*1.25) {
+        doFixedArray = false;
+      }
+    }
+    */
 
     if (doFixedArray) {
-      //System.out.println("  doFixedArray");
+      final int MAX_HEADER_SIZE = 11; // header(byte) + numArcs(vint) + numBytes(vint)
       assert maxBytesPerArc > 0;
       // 2nd pass just "expands" all arcs to take up a fixed
       // byte size
-      final int sizeNeeded = fixedArrayStart + nodeIn.numArcs * maxBytesPerArc;
-      assert ((long) fixedArrayStart) + ((long) nodeIn.numArcs) * maxBytesPerArc < Integer.MAX_VALUE: "FST too large (> 2.1 GB)";
 
-      bytes = ArrayUtil.grow(bytes, sizeNeeded);
-      // TODO: we could make this a vInt instead
-      bytes[fixedArrayStart-4] = (byte) (maxBytesPerArc >> 24);
-      bytes[fixedArrayStart-3] = (byte) (maxBytesPerArc >> 16);
-      bytes[fixedArrayStart-2] = (byte) (maxBytesPerArc >> 8);
-      bytes[fixedArrayStart-1] = (byte) maxBytesPerArc;
+      //System.out.println("write int @pos=" + (fixedArrayStart-4) + " numArcs=" + nodeIn.numArcs);
+      // create the header
+      // TODO: clean this up: or just rewind+reuse and deal with it
+      byte header[] = new byte[MAX_HEADER_SIZE]; 
+      ByteArrayDataOutput bad = new ByteArrayDataOutput(header);
+      // write a "false" first arc:
+      bad.writeByte(ARCS_AS_FIXED_ARRAY);
+      bad.writeVInt(nodeIn.numArcs);
+      bad.writeVInt(maxBytesPerArc);
+      int headerLen = bad.getPosition();
+      
+      final long fixedArrayStart = startAddress + headerLen;
 
       // expand the arcs in place, backwards
-      int srcPos = writer.getPosition();
-      int destPos = fixedArrayStart + nodeIn.numArcs*maxBytesPerArc;
-      writer.setPosition(destPos);
-      for(int arcIdx=nodeIn.numArcs-1;arcIdx>=0;arcIdx--) {
-        //System.out.println("  repack arcIdx=" + arcIdx + " srcPos=" + srcPos + " destPos=" + destPos);
-        destPos -= maxBytesPerArc;
-        srcPos -= bytesPerArc[arcIdx];
-        if (srcPos != destPos) {
-          assert destPos > srcPos: "destPos=" + destPos + " srcPos=" + srcPos + " arcIdx=" + arcIdx + " maxBytesPerArc=" + maxBytesPerArc + " bytesPerArc[arcIdx]=" + bytesPerArc[arcIdx] + " nodeIn.numArcs=" + nodeIn.numArcs;
-          System.arraycopy(bytes, srcPos, bytes, destPos, bytesPerArc[arcIdx]);
+      long srcPos = bytes.getPosition();
+      long destPos = fixedArrayStart + nodeIn.numArcs*maxBytesPerArc;
+      assert destPos >= srcPos;
+      if (destPos > srcPos) {
+        bytes.skipBytes((int) (destPos - srcPos));
+        for(int arcIdx=nodeIn.numArcs-1;arcIdx>=0;arcIdx--) {
+          destPos -= maxBytesPerArc;
+          srcPos -= bytesPerArc[arcIdx];
+          //System.out.println("  repack arcIdx=" + arcIdx + " srcPos=" + srcPos + " destPos=" + destPos);
+          if (srcPos != destPos) {
+            //System.out.println("  copy len=" + bytesPerArc[arcIdx]);
+            assert destPos > srcPos: "destPos=" + destPos + " srcPos=" + srcPos + " arcIdx=" + arcIdx + " maxBytesPerArc=" + maxBytesPerArc + " bytesPerArc[arcIdx]=" + bytesPerArc[arcIdx] + " nodeIn.numArcs=" + nodeIn.numArcs;
+            bytes.copyBytes(srcPos, destPos, bytesPerArc[arcIdx]);
+          }
         }
       }
+      
+      // now write the header
+      bytes.writeBytes(startAddress, header, 0, headerLen);
     }
 
-    // reverse bytes in-place; we do this so that the
-    // "BIT_TARGET_NEXT" opto can work, ie, it reads the
-    // node just before the current one
-    final int endAddress = writer.getPosition() - 1;
-
-    int left = startAddress;
-    int right = endAddress;
-    while (left < right) {
-      final byte b = bytes[left];
-      bytes[left++] = bytes[right];
-      bytes[right--] = b;
+    final long thisNodeAddress = bytes.getPosition()-1;
+
+    bytes.reverse(startAddress, thisNodeAddress);
+
+    // PackedInts uses int as the index, so we cannot handle
+    // > 2.1B nodes when packing:
+    if (nodeAddress != null && nodeCount == Integer.MAX_VALUE) {
+      throw new IllegalStateException("cannot create a packed FST with more than 2.1 billion nodes");
     }
-    //System.out.println("  endAddress=" + endAddress);
 
     nodeCount++;
-    final int node;
+    final long node;
     if (nodeAddress != null) {
+
       // Nodes are addressed by 1+ord:
-      if (nodeCount == nodeAddress.size()) {
+      if ((int) nodeCount == nodeAddress.size()) {
         nodeAddress = nodeAddress.resize(ArrayUtil.oversize(nodeAddress.size() + 1, nodeAddress.getBitsPerValue()));
         inCounts = inCounts.resize(ArrayUtil.oversize(inCounts.size() + 1, inCounts.getBitsPerValue()));
       }
-      nodeAddress.set(nodeCount, endAddress);
+      nodeAddress.set((int) nodeCount, thisNodeAddress);
       // System.out.println("  write nodeAddress[" + nodeCount + "] = " + endAddress);
       node = nodeCount;
     } else {
-      node = endAddress;
+      node = thisNodeAddress;
     }
     lastFrozenNode = node;
 
+    //System.out.println("  ret node=" + node + " address=" + thisNodeAddress + " nodeAddress=" + nodeAddress);
     return node;
   }
 
@@ -753,7 +811,7 @@ public final class FST<T> {
    * 
    * @return Returns the second argument
    * (<code>arc</code>). */
-  public Arc<T> readLastTargetArc(Arc<T> follow, Arc<T> arc, FST.BytesReader in) throws IOException {
+  public Arc<T> readLastTargetArc(Arc<T> follow, Arc<T> arc, BytesReader in) throws IOException {
     //System.out.println("readLast");
     if (!targetHasArcs(follow)) {
       //System.out.println("  end node");
@@ -764,19 +822,19 @@ public final class FST<T> {
       arc.flags = BIT_LAST_ARC;
       return arc;
     } else {
-      in.pos = getNodeAddress(follow.target);
+      in.setPosition(getNodeAddress(follow.target));
       arc.node = follow.target;
       final byte b = in.readByte();
       if (b == ARCS_AS_FIXED_ARRAY) {
         // array: jump straight to end
         arc.numArcs = in.readVInt();
-        if (packed) {
+        if (packed || version >= VERSION_VINT_TARGET) {
           arc.bytesPerArc = in.readVInt();
         } else {
           arc.bytesPerArc = in.readInt();
         }
         //System.out.println("  array numArcs=" + arc.numArcs + " bpa=" + arc.bytesPerArc);
-        arc.posArcsStart = in.pos;
+        arc.posArcsStart = in.getPosition();
         arc.arcIdx = arc.numArcs - 2;
       } else {
         arc.flags = b;
@@ -794,18 +852,16 @@ public final class FST<T> {
           }
           if (arc.flag(BIT_STOP_NODE)) {
           } else if (arc.flag(BIT_TARGET_NEXT)) {
+          } else if (packed) {
+            in.readVLong();
           } else {
-            if (packed) {
-              in.readVInt();
-            } else {
-              in.skip(4);
-            }
+            readUnpackedNodeTarget(in);
           }
           arc.flags = in.readByte();
         }
-        // Undo the byte flags we read: 
-        in.skip(-1);
-        arc.nextArc = in.pos;
+        // Undo the byte flags we read:
+        in.skipBytes(-1);
+        arc.nextArc = in.getPosition();
       }
       readNextRealArc(arc, in);
       assert arc.isLast();
@@ -813,6 +869,16 @@ public final class FST<T> {
     }
   }
 
+  private long readUnpackedNodeTarget(BytesReader in) throws IOException {
+    long target;
+    if (version < VERSION_VINT_TARGET) {
+      target = in.readInt();
+    } else {
+      target = in.readVLong();
+    }
+    return target;
+  }
+
   /**
    * Follow the <code>follow</code> arc and read the first arc of its target;
    * this changes the provided <code>arc</code> (2nd arg) in-place and returns
@@ -843,10 +909,9 @@ public final class FST<T> {
     }
   }
 
-  public Arc<T> readFirstRealTargetArc(int node, Arc<T> arc, final BytesReader in) throws IOException {
-    assert in.bytes == bytes;
-    final int address = getNodeAddress(node);
-    in.pos = address;
+  public Arc<T> readFirstRealTargetArc(long node, Arc<T> arc, final BytesReader in) throws IOException {
+    final long address = getNodeAddress(node);
+    in.setPosition(address);
     //System.out.println("  readFirstRealTargtArc address="
     //+ address);
     //System.out.println("   flags=" + arc.flags);
@@ -856,13 +921,13 @@ public final class FST<T> {
       //System.out.println("  fixedArray");
       // this is first arc in a fixed-array
       arc.numArcs = in.readVInt();
-      if (packed) {
+      if (packed || version >= VERSION_VINT_TARGET) {
         arc.bytesPerArc = in.readVInt();
       } else {
         arc.bytesPerArc = in.readInt();
       }
       arc.arcIdx = -1;
-      arc.nextArc = arc.posArcsStart = in.pos;
+      arc.nextArc = arc.posArcsStart = in.getPosition();
       //System.out.println("  bytesPer=" + arc.bytesPerArc + " numArcs=" + arc.numArcs + " arcsStart=" + pos);
     } else {
       //arc.flags = b;
@@ -879,11 +944,11 @@ public final class FST<T> {
    * @return Returns <code>true</code> if <code>arc</code> points to a state in an
    * expanded array format.
    */
-  boolean isExpandedTarget(Arc<T> follow, FST.BytesReader in) throws IOException {
+  boolean isExpandedTarget(Arc<T> follow, BytesReader in) throws IOException {
     if (!targetHasArcs(follow)) {
       return false;
     } else {
-      in.pos = getNodeAddress(follow.target);
+      in.setPosition(getNodeAddress(follow.target));
       return in.readByte() == ARCS_AS_FIXED_ARRAY;
     }
   }
@@ -907,30 +972,36 @@ public final class FST<T> {
     assert !arc.isLast();
 
     if (arc.label == END_LABEL) {
-      //System.out.println("    nextArc fake " + arc.nextArc);
-      int pos = in.pos = getNodeAddress(arc.nextArc);
+      //System.out.println("    nextArc fake " +
+      //arc.nextArc);
+      
+      long pos = getNodeAddress(arc.nextArc);
+      in.setPosition(pos);
+
       final byte b = in.readByte();
       if (b == ARCS_AS_FIXED_ARRAY) {
-        //System.out.println("    nextArc fake array");
+        //System.out.println("    nextArc fixed array");
         in.readVInt();
-        if (packed) {
+
+        // Skip bytesPerArc:
+        if (packed || version >= VERSION_VINT_TARGET) {
           in.readVInt();
         } else {
           in.readInt();
         }
       } else {
-        in.pos = pos;
+        in.setPosition(pos);
       }
     } else {
       if (arc.bytesPerArc != 0) {
         //System.out.println("    nextArc real array");
         // arcs are at fixed entries
-        in.pos = arc.posArcsStart;
-        in.skip((1+arc.arcIdx)*arc.bytesPerArc);
+        in.setPosition(arc.posArcsStart);
+        in.skipBytes((1+arc.arcIdx)*arc.bytesPerArc);
       } else {
         // arcs are packed
         //System.out.println("    nextArc real packed");
-        in.pos = arc.nextArc;
+        in.setPosition(arc.nextArc);
       }
     }
     // skip flags
@@ -941,7 +1012,6 @@ public final class FST<T> {
   /** Never returns null, but you should never call this if
    *  arc.isLast() is true. */
   public Arc<T> readNextRealArc(Arc<T> arc, final BytesReader in) throws IOException {
-    assert in.bytes == bytes;
 
     // TODO: can't assert this because we call from readFirstArc
     // assert !flag(arc.flags, BIT_LAST_ARC);
@@ -951,10 +1021,11 @@ public final class FST<T> {
       // arcs are at fixed entries
       arc.arcIdx++;
       assert arc.arcIdx < arc.numArcs;
-      in.skip(arc.posArcsStart, arc.arcIdx*arc.bytesPerArc);
+      in.setPosition(arc.posArcsStart);
+      in.skipBytes(arc.arcIdx*arc.bytesPerArc);
     } else {
       // arcs are packed
-      in.pos = arc.nextArc;
+      in.setPosition(arc.nextArc);
     }
     arc.flags = in.readByte();
     arc.label = readLabel(in);
@@ -977,9 +1048,9 @@ public final class FST<T> {
       } else {
         arc.target = NON_FINAL_END_NODE;
       }
-      arc.nextArc = in.pos;
+      arc.nextArc = in.getPosition();
     } else if (arc.flag(BIT_TARGET_NEXT)) {
-      arc.nextArc = in.pos;
+      arc.nextArc = in.getPosition();
       // TODO: would be nice to make this lazy -- maybe
       // caller doesn't need the target and is scanning arcs...
       if (nodeAddress == null) {
@@ -988,35 +1059,36 @@ public final class FST<T> {
             // must scan
             seekToNextNode(in);
           } else {
-            in.skip(arc.posArcsStart, arc.bytesPerArc * arc.numArcs);
+            in.setPosition(arc.posArcsStart);
+            in.skipBytes(arc.bytesPerArc * arc.numArcs);
           }
         }
-        arc.target = in.pos;
+        arc.target = in.getPosition();
       } else {
         arc.target = arc.node - 1;
         assert arc.target > 0;
       }
     } else {
       if (packed) {
-        final int pos = in.pos;
-        final int code = in.readVInt();
+        final long pos = in.getPosition();
+        final long code = in.readVLong();
         if (arc.flag(BIT_TARGET_DELTA)) {
           // Address is delta-coded from current address:
           arc.target = pos + code;
           //System.out.println("    delta pos=" + pos + " delta=" + code + " target=" + arc.target);
         } else if (code < nodeRefToAddress.size()) {
           // Deref
-          arc.target = (int) nodeRefToAddress.get(code);
+          arc.target = nodeRefToAddress.get((int) code);
           //System.out.println("    deref code=" + code + " target=" + arc.target);
         } else {
           // Absolute
           arc.target = code;
-          //System.out.println("    abs code=" + code + " derefLen=" + nodeRefToAddress.length);
+          //System.out.println("    abs code=" + code);
         }
       } else {
-        arc.target = in.readInt();
+        arc.target = readUnpackedNodeTarget(in);
       }
-      arc.nextArc = in.pos;
+      arc.nextArc = in.getPosition();
     }
     return arc;
   }
@@ -1025,7 +1097,6 @@ public final class FST<T> {
    *  This returns null if the arc was not found, else the incoming arc. */
   public Arc<T> findTargetArc(int labelToMatch, Arc<T> follow, Arc<T> arc, BytesReader in) throws IOException {
     assert cachedRootArcs != null;
-    assert in.bytes == bytes;
 
     if (labelToMatch == END_LABEL) {
       if (follow.isFinal()) {
@@ -1060,7 +1131,7 @@ public final class FST<T> {
       return null;
     }
 
-    in.pos = getNodeAddress(follow.target);
+    in.setPosition(getNodeAddress(follow.target));
 
     arc.node = follow.target;
 
@@ -1069,18 +1140,19 @@ public final class FST<T> {
     if (in.readByte() == ARCS_AS_FIXED_ARRAY) {
       // Arcs are full array; do binary search:
       arc.numArcs = in.readVInt();
-      if (packed) {
+      if (packed || version >= VERSION_VINT_TARGET) {
         arc.bytesPerArc = in.readVInt();
       } else {
         arc.bytesPerArc = in.readInt();
       }
-      arc.posArcsStart = in.pos;
+      arc.posArcsStart = in.getPosition();
       int low = 0;
       int high = arc.numArcs-1;
       while (low <= high) {
         //System.out.println("    cycle");
         int mid = (low + high) >>> 1;
-        in.skip(arc.posArcsStart, arc.bytesPerArc*mid + 1);
+        in.setPosition(arc.posArcsStart);
+        in.skipBytes(arc.bytesPerArc*mid + 1);
         int midLabel = readLabel(in);
         final int cmp = midLabel - labelToMatch;
         if (cmp < 0) {
@@ -1135,9 +1207,9 @@ public final class FST<T> {
 
       if (!flag(flags, BIT_STOP_NODE) && !flag(flags, BIT_TARGET_NEXT)) {
         if (packed) {
-          in.readVInt();
+          in.readVLong();
         } else {
-          in.readInt();
+          readUnpackedNodeTarget(in);
         }
       }
 
@@ -1147,23 +1219,19 @@ public final class FST<T> {
     }
   }
 
-  public int getNodeCount() {
+  public long getNodeCount() {
     // 1+ in order to count the -1 implicit final node
     return 1+nodeCount;
   }
   
-  public int getArcCount() {
+  public long getArcCount() {
     return arcCount;
   }
 
-  public int getArcWithOutputCount() {
+  public long getArcWithOutputCount() {
     return arcWithOutputCount;
   }
 
-  public void setAllowArrayArcs(boolean v) {
-    allowArrayArcs = v;
-  }
-  
   /**
    * Nodes will be expanded if their depth (distance from the root node) is
    * &lt;= this value and their number of arcs is &gt;=
@@ -1185,145 +1253,32 @@ public final class FST<T> {
        node.numArcs >= FIXED_ARRAY_NUM_ARCS_DEEP);
   }
   
-  static abstract class BytesWriter extends DataOutput {
-    public abstract void setPosition(int posWrite);
-    public abstract int getPosition();
-  }
-
-  // Non-static: writes to FST's byte[]
-  class DefaultBytesWriter extends BytesWriter {
-    int posWrite;
-
-    public DefaultBytesWriter() {
-      // pad: ensure no node gets address 0 which is reserved to mean
-      // the stop state w/ no arcs
-      posWrite = 1;
-    }
-
-    @Override
-    public void writeByte(byte b) {
-      assert posWrite <= bytes.length;
-      if (bytes.length == posWrite) {
-        assert bytes.length < Integer.MAX_VALUE: "FST too large (> 2.1 GB)";
-        bytes = ArrayUtil.grow(bytes);
-      }
-      assert posWrite < bytes.length: "posWrite=" + posWrite + " bytes.length=" + bytes.length;
-      bytes[posWrite++] = b;
-    }
-
-    @Override
-    public int getPosition() {
-      return posWrite;
-    }
-
-    @Override
-    public void setPosition(int posWrite) {
-      this.posWrite = posWrite;
-      if (bytes.length < posWrite) {
-        assert bytes.length < Integer.MAX_VALUE: "FST too large (> 2.1 GB)";
-        bytes = ArrayUtil.grow(bytes, posWrite);
-      }
-    }
-
-    @Override
-    public void writeBytes(byte[] b, int offset, int length) {
-      final int size = posWrite + length;
-      assert bytes.length < Integer.MAX_VALUE: "FST too large (> 2.1 GB)";
-      bytes = ArrayUtil.grow(bytes, size);
-      System.arraycopy(b, offset, bytes, posWrite, length);
-      posWrite += length;
-    }
-  }
-
   /** Returns a {@link BytesReader} for this FST, positioned at
    *  position 0. */
   public BytesReader getBytesReader() {
-    return getBytesReader(0);
-  }
-
-  /** Returns a {@link BytesReader} for this FST, positioned at
-   *  the provided position. */
-  public BytesReader getBytesReader(int pos) {
-    // TODO: maybe re-use via ThreadLocal?
+    BytesReader in;
     if (packed) {
-      return new ForwardBytesReader(bytes, pos);
+      in = bytes.getForwardReader();
     } else {
-      return new ReverseBytesReader(bytes, pos);
+      in = bytes.getReverseReader();
     }
+    return in;
   }
 
-  /** Reads the bytes from this FST.  Use {@link
-   *  #getBytesReader(int)} to obtain an instance for this
-   *  FST; re-use across calls (but only within a single
-   *  thread) for better performance. */
+  /** Reads bytes stored in an FST. */
   public static abstract class BytesReader extends DataInput {
-    protected int pos;
-    protected final byte[] bytes;
-    protected BytesReader(byte[] bytes, int pos) {
-      this.bytes = bytes;
-      this.pos = pos;
-    }
-    abstract void skip(int byteCount);
-    abstract void skip(int base, int byteCount);
-  }
-
-  final static class ReverseBytesReader extends BytesReader {
-
-    public ReverseBytesReader(byte[] bytes, int pos) {
-      super(bytes, pos);
-    }
-
-    @Override
-    public byte readByte() {
-      return bytes[pos--];
-    }
-
-    @Override
-    public void readBytes(byte[] b, int offset, int len) {
-      for(int i=0;i<len;i++) {
-        b[offset+i] = bytes[pos--];
-      }
-    }
+    /** Get current read position. */
+    public abstract long getPosition();
 
-    @Override
-    public void skip(int count) {
-      pos -= count;
-    }
-
-    @Override
-    public void skip(int base, int count) {
-      pos = base - count;
-    }
-  }
-
-  // TODO: can we use just ByteArrayDataInput...?  need to
-  // add a .skipBytes to DataInput.. hmm and .setPosition
-  final static class ForwardBytesReader extends BytesReader {
-
-    public ForwardBytesReader(byte[] bytes, int pos) {
-      super(bytes, pos);
-    }
-
-    @Override
-    public byte readByte() {
-      return bytes[pos++];
-    }
+    /** Set current read position. */
+    public abstract void setPosition(long pos);
 
-    @Override
-    public void readBytes(byte[] b, int offset, int len) {
-      System.arraycopy(bytes, pos, b, offset, len);
-      pos += len;
-    }
+    /** Returns true if this reader uses reversed bytes
+     *  under-the-hood. */
+    public abstract boolean reversed();
 
-    @Override
-    public void skip(int count) {
-      pos += count;
-    }
-
-    @Override
-    public void skip(int base, int count) {
-      pos = base + count;
-    }
+    /** Skips bytes. */
+    public abstract void skipBytes(int count);
   }
 
   private static class ArcAndState<T> {
@@ -1445,14 +1400,18 @@ public final class FST<T> {
  */
 
   // Creates a packed FST
-  private FST(INPUT_TYPE inputType, PackedInts.Reader nodeRefToAddress, Outputs<T> outputs) {
+  private FST(INPUT_TYPE inputType, Outputs<T> outputs, int bytesPageBits) {
+    version = VERSION_CURRENT;
     packed = true;
     this.inputType = inputType;
-    bytes = new byte[128];
-    this.nodeRefToAddress = nodeRefToAddress;
+    bytes = new BytesStore(bytesPageBits);
     this.outputs = outputs;
     NO_OUTPUT = outputs.getNoOutput();
-    writer = new DefaultBytesWriter();
+    
+    // NOTE: bogus because this is only used during
+    // building; we need to break out mutable FST from
+    // immutable
+    allowArrayArcs = false;
   }
 
   /** Expert: creates an FST by packing this one.  This
@@ -1469,6 +1428,9 @@ public final class FST<T> {
    */
   FST<T> pack(int minInCountDeref, int maxDerefNodes, float acceptableOverheadRatio) throws IOException {
 
+    // NOTE: maxDerefNodes is intentionally int: we cannot
+    // support > 2.1B deref nodes
+
     // TODO: other things to try
     //   - renumber the nodes to get more next / better locality?
     //   - allow multiple input labels on an arc, so
@@ -1486,7 +1448,7 @@ public final class FST<T> {
 
     Arc<T> arc = new Arc<T>();
 
-    final BytesReader r = getBytesReader(0);
+    final BytesReader r = getBytesReader();
 
     final int topN = Math.min(maxDerefNodes, inCounts.size());
 
@@ -1518,17 +1480,13 @@ public final class FST<T> {
       //System.out.println("map node=" + n.node + " inCount=" + n.count + " to newID=" + downTo);
     }
 
-    final FST<T> fst = new FST<T>(inputType, null, outputs);
-
-    final BytesWriter writer = fst.writer;
-
     // +1 because node ords start at 1 (0 is reserved as stop node):
     final GrowableWriter newNodeAddress = new GrowableWriter(
-        PackedInts.bitsRequired(bytes.length), 1 + nodeCount, acceptableOverheadRatio);
+                       PackedInts.bitsRequired(this.bytes.getPosition()), (int) (1 + nodeCount), acceptableOverheadRatio);
 
     // Fill initial coarse guess:
     for(int node=1;node<=nodeCount;node++) {
-      newNodeAddress.set(node, 1 + bytes.length - nodeAddress.get(node));
+      newNodeAddress.set(node, 1 + this.bytes.getPosition() - nodeAddress.get(node));
     }
 
     int absCount;
@@ -1536,6 +1494,8 @@ public final class FST<T> {
     int topCount;
     int nextCount;
 
+    FST<T> fst;
+
     // Iterate until we converge:
     while(true) {
 
@@ -1545,7 +1505,10 @@ public final class FST<T> {
       // for assert:
       boolean negDelta = false;
 
-      writer.setPosition(0);
+      fst = new FST<T>(inputType, outputs, bytes.getBlockBits());
+      
+      final BytesStore writer = fst.bytes;
+
       // Skip 0 byte since 0 is reserved target:
       writer.writeByte((byte) 0);
 
@@ -1557,19 +1520,20 @@ public final class FST<T> {
 
       int changedCount = 0;
 
-      int addressError = 0;
+      long addressError = 0;
 
       //int totWasted = 0;
 
       // Since we re-reverse the bytes, we now write the
       // nodes backwards, so that BIT_TARGET_NEXT is
       // unchanged:
-      for(int node=nodeCount;node>=1;node--) {
+      for(int node=(int)nodeCount;node>=1;node--) {
         fst.nodeCount++;
-        final int address = writer.getPosition();
+        final long address = writer.getPosition();
+
         //System.out.println("  node: " + node + " address=" + address);
         if (address != newNodeAddress.get(node)) {
-          addressError = address - (int) newNodeAddress.get(node);
+          addressError = address - newNodeAddress.get(node);
           //System.out.println("    change: " + (address - newNodeAddress[node]));
           changed = true;
           newNodeAddress.set(node, address);
@@ -1589,6 +1553,7 @@ public final class FST<T> {
         writeNode:
         while(true) { // retry writing this node
 
+          //System.out.println("  cycle: retry");
           readFirstRealTargetArc(node, arc, r);
 
           final boolean useArcArray = arc.bytesPerArc != 0;
@@ -1606,9 +1571,9 @@ public final class FST<T> {
           int maxBytesPerArc = 0;
           //int wasted = 0;
           while(true) {  // iterate over all arcs for this node
+            //System.out.println("    cycle next arc");
 
-            //System.out.println("    arc label=" + arc.label + " target=" + arc.target + " pos=" + writer.posWrite);
-            final int arcStartPos = writer.getPosition();
+            final long arcStartPos = writer.getPosition();
             nodeArcCount++;
 
             byte flags = 0;
@@ -1643,19 +1608,18 @@ public final class FST<T> {
               flags += BIT_ARC_HAS_OUTPUT;
             }
 
-            final Integer ptr;
-            final int absPtr;
+            final long absPtr;
             final boolean doWriteTarget = targetHasArcs(arc) && (flags & BIT_TARGET_NEXT) == 0;
             if (doWriteTarget) {
 
-              ptr = topNodeMap.get(arc.target);
+              final Integer ptr = topNodeMap.get(arc.target);
               if (ptr != null) {
                 absPtr = ptr;
               } else {
-                absPtr = topNodeMap.size() + (int) newNodeAddress.get(arc.target) + addressError;
+                absPtr = topNodeMap.size() + newNodeAddress.get((int) arc.target) + addressError;
               }
 
-              int delta = (int) newNodeAddress.get(arc.target) + addressError - writer.getPosition() - 2;
+              long delta = newNodeAddress.get((int) arc.target) + addressError - writer.getPosition() - 2;
               if (delta < 0) {
                 //System.out.println("neg: " + delta);
                 anyNegDelta = true;
@@ -1666,12 +1630,13 @@ public final class FST<T> {
                 flags |= BIT_TARGET_DELTA;
               }
             } else {
-              ptr = null;
               absPtr = 0;
             }
 
+            assert flags != ARCS_AS_FIXED_ARRAY;
             writer.writeByte(flags);
-            fst.writeLabel(arc.label);
+
+            fst.writeLabel(writer, arc.label);
 
             if (arc.output != NO_OUTPUT) {
               outputs.write(arc.output, writer);
@@ -1685,7 +1650,7 @@ public final class FST<T> {
 
             if (doWriteTarget) {
 
-              int delta = (int) newNodeAddress.get(arc.target) + addressError - writer.getPosition();
+              long delta = newNodeAddress.get((int) arc.target) + addressError - writer.getPosition();
               if (delta < 0) {
                 anyNegDelta = true;
                 //System.out.println("neg: " + delta);
@@ -1694,7 +1659,7 @@ public final class FST<T> {
 
               if (flag(flags, BIT_TARGET_DELTA)) {
                 //System.out.println("        delta");
-                writer.writeVInt(delta);
+                writer.writeVLong(delta);
                 if (!retry) {
                   deltaCount++;
                 }
@@ -1706,7 +1671,7 @@ public final class FST<T> {
                   System.out.println("        abs");
                 }
                 */
-                writer.writeVInt(absPtr);
+                writer.writeVLong(absPtr);
                 if (!retry) {
                   if (absPtr >= topNodeMap.size()) {
                     absCount++;
@@ -1718,7 +1683,7 @@ public final class FST<T> {
             }
 
             if (useArcArray) {
-              final int arcBytes = writer.getPosition() - arcStartPos;
+              final int arcBytes = (int) (writer.getPosition() - arcStartPos);
               //System.out.println("  " + arcBytes + " bytes");
               maxBytesPerArc = Math.max(maxBytesPerArc, arcBytes);
               // NOTE: this may in fact go "backwards", if
@@ -1728,7 +1693,7 @@ public final class FST<T> {
               // will retry (below) so it's OK to ovewrite
               // bytes:
               //wasted += bytesPerArc - arcBytes;
-              writer.setPosition(arcStartPos + bytesPerArc);
+              writer.skipBytes((int) (arcStartPos + bytesPerArc - writer.getPosition()));
             }
 
             if (arc.isLast()) {
@@ -1753,11 +1718,12 @@ public final class FST<T> {
 
           // Retry:
           bytesPerArc = maxBytesPerArc;
-          writer.setPosition(address);
+          writer.truncate(address);
           nodeArcCount = 0;
           retry = true;
           anyNegDelta = false;
         }
+
         negDelta |= anyNegDelta;
 
         fst.arcCount += nodeArcCount;
@@ -1777,8 +1743,8 @@ public final class FST<T> {
     }
 
     long maxAddress = 0;
-    for (int key : topNodeMap.keySet()) {
-      maxAddress = Math.max(maxAddress, newNodeAddress.get(key));
+    for (long key : topNodeMap.keySet()) {
+      maxAddress = Math.max(maxAddress, newNodeAddress.get((int) key));
     }
 
     PackedInts.Mutable nodeRefToAddressIn = PackedInts.getMutable(topNodeMap.size(),
@@ -1788,8 +1754,7 @@ public final class FST<T> {
     }
     fst.nodeRefToAddress = nodeRefToAddressIn;
     
-
-    fst.startNode = (int) newNodeAddress.get(startNode);
+    fst.startNode = newNodeAddress.get((int) startNode);
     //System.out.println("new startNode=" + fst.startNode + " old startNode=" + startNode);
 
     if (emptyOutput != null) {
@@ -1799,11 +1764,8 @@ public final class FST<T> {
     assert fst.nodeCount == nodeCount: "fst.nodeCount=" + fst.nodeCount + " nodeCount=" + nodeCount;
     assert fst.arcCount == arcCount;
     assert fst.arcWithOutputCount == arcWithOutputCount: "fst.arcWithOutputCount=" + fst.arcWithOutputCount + " arcWithOutputCount=" + arcWithOutputCount;
-    
-    final byte[] finalBytes = new byte[writer.getPosition()];
-    //System.out.println("resize " + fst.bytes.length + " down to " + writer.posWrite);
-    System.arraycopy(fst.bytes, 0, finalBytes, 0, writer.getPosition());
-    fst.bytes = finalBytes;
+
+    fst.bytes.finish();
     fst.cacheRootArcs();
 
     //final int size = fst.sizeInBytes();

Modified: lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/fst/FSTEnum.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/fst/FSTEnum.java?rev=1454862&r1=1454861&r2=1454862&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/fst/FSTEnum.java (original)
+++ lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/fst/FSTEnum.java Sun Mar 10 15:04:57 2013
@@ -17,11 +17,11 @@ package org.apache.lucene.util.fst;
  * limitations under the License.
  */
 
+import java.io.IOException;
+
 import org.apache.lucene.util.ArrayUtil;
 import org.apache.lucene.util.RamUsageEstimator;
 
-import java.io.IOException;
-
 /** Can next() and advance() through the terms in an FST
  *
   * @lucene.experimental
@@ -46,7 +46,7 @@ abstract class FSTEnum<T> {
    *  term before target.  */
   protected FSTEnum(FST<T> fst) {
     this.fst = fst;
-    fstReader = fst.getBytesReader(0);
+    fstReader = fst.getBytesReader();
     NO_OUTPUT = fst.outputs.getNoOutput();
     fst.getFirstArc(getArc(0));
     output[0] = NO_OUTPUT;
@@ -145,7 +145,7 @@ abstract class FSTEnum<T> {
         // Arcs are fixed array -- use binary search to find
         // the target.
 
-        final FST.BytesReader in = fst.getBytesReader(0);
+        final FST.BytesReader in = fst.getBytesReader();
         int low = arc.arcIdx;
         int high = arc.numArcs-1;
         int mid = 0;
@@ -153,8 +153,8 @@ abstract class FSTEnum<T> {
         boolean found = false;
         while (low <= high) {
           mid = (low + high) >>> 1;
-          in.pos = arc.posArcsStart;
-          in.skip(arc.bytesPerArc*mid+1);
+          in.setPosition(arc.posArcsStart);
+          in.skipBytes(arc.bytesPerArc*mid+1);
           final int midLabel = fst.readLabel(in);
           final int cmp = midLabel - targetLabel;
           //System.out.println("  cycle low=" + low + " high=" + high + " mid=" + mid + " midLabel=" + midLabel + " cmp=" + cmp);
@@ -284,7 +284,7 @@ abstract class FSTEnum<T> {
         // Arcs are fixed array -- use binary search to find
         // the target.
 
-        final FST.BytesReader in = fst.getBytesReader(0);
+        final FST.BytesReader in = fst.getBytesReader();
         int low = arc.arcIdx;
         int high = arc.numArcs-1;
         int mid = 0;
@@ -292,8 +292,8 @@ abstract class FSTEnum<T> {
         boolean found = false;
         while (low <= high) {
           mid = (low + high) >>> 1;
-          in.pos = arc.posArcsStart;
-          in.skip(arc.bytesPerArc*mid+1);
+          in.setPosition(arc.posArcsStart);
+          in.skipBytes(arc.bytesPerArc*mid+1);
           final int midLabel = fst.readLabel(in);
           final int cmp = midLabel - targetLabel;
           //System.out.println("  cycle low=" + low + " high=" + high + " mid=" + mid + " midLabel=" + midLabel + " cmp=" + cmp);
@@ -434,7 +434,7 @@ abstract class FSTEnum<T> {
     FST.Arc<T> arc = getArc(upto-1);
     int targetLabel = getTargetLabel();
 
-    final FST.BytesReader fstReader = fst.getBytesReader(0);
+    final FST.BytesReader fstReader = fst.getBytesReader();
 
     while(true) {
       //System.out.println("  cycle target=" + (targetLabel == -1 ? "-1" : (char) targetLabel));

Modified: lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java?rev=1454862&r1=1454861&r2=1454862&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java (original)
+++ lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java Sun Mar 10 15:04:57 2013
@@ -19,22 +19,27 @@ package org.apache.lucene.util.fst;
 
 import java.io.IOException;
 
+import org.apache.lucene.util.packed.GrowableWriter;
+import org.apache.lucene.util.packed.PackedInts;
+
 // Used to dedup states (lookup already-frozen states)
 final class NodeHash<T> {
 
-  private int[] table;
+  private GrowableWriter table;
   private int count;
   private int mask;
   private final FST<T> fst;
   private final FST.Arc<T> scratchArc = new FST.Arc<T>();
+  private final FST.BytesReader in;
 
-  public NodeHash(FST<T> fst) {
-    table = new int[16];
+  public NodeHash(FST<T> fst, FST.BytesReader in) {
+    table = new GrowableWriter(8, 16, PackedInts.COMPACT);
     mask = 15;
     this.fst = fst;
+    this.in = in;
   }
 
-  private boolean nodesEqual(Builder.UnCompiledNode<T> node, int address, FST.BytesReader in) throws IOException {
+  private boolean nodesEqual(Builder.UnCompiledNode<T> node, long address) throws IOException {
     fst.readFirstRealTargetArc(address, scratchArc, in);
     if (scratchArc.bytesPerArc != 0 && node.numArcs != scratchArc.numArcs) {
       return false;
@@ -73,7 +78,8 @@ final class NodeHash<T> {
       final Builder.Arc<T> arc = node.arcs[arcIdx];
       //System.out.println("  label=" + arc.label + " target=" + ((Builder.CompiledNode) arc.target).node + " h=" + h + " output=" + fst.outputs.outputToString(arc.output) + " isFinal?=" + arc.isFinal);
       h = PRIME * h + arc.label;
-      h = PRIME * h + ((Builder.CompiledNode) arc.target).node;
+      long n = ((Builder.CompiledNode) arc.target).node;
+      h = PRIME * h + (int) (n^(n>>32));
       h = PRIME * h + arc.output.hashCode();
       h = PRIME * h + arc.nextFinalOutput.hashCode();
       if (arc.isFinal) {
@@ -85,16 +91,15 @@ final class NodeHash<T> {
   }
 
   // hash code for a frozen node
-  private int hash(int node) throws IOException {
+  private int hash(long node) throws IOException {
     final int PRIME = 31;
-    final FST.BytesReader in = fst.getBytesReader(0);
     //System.out.println("hash frozen node=" + node);
     int h = 0;
     fst.readFirstRealTargetArc(node, scratchArc, in);
     while(true) {
-      //System.out.println("  label=" + scratchArc.label + " target=" + scratchArc.target + " h=" + h + " output=" + fst.outputs.outputToString(scratchArc.output) + " next?=" + scratchArc.flag(4) + " final?=" + scratchArc.isFinal());
+      //System.out.println("  label=" + scratchArc.label + " target=" + scratchArc.target + " h=" + h + " output=" + fst.outputs.outputToString(scratchArc.output) + " next?=" + scratchArc.flag(4) + " final?=" + scratchArc.isFinal() + " pos=" + in.getPosition());
       h = PRIME * h + scratchArc.label;
-      h = PRIME * h + scratchArc.target;
+      h = PRIME * h + (int) (scratchArc.target^(scratchArc.target>>32));
       h = PRIME * h + scratchArc.output.hashCode();
       h = PRIME * h + scratchArc.nextFinalOutput.hashCode();
       if (scratchArc.isFinal()) {
@@ -109,26 +114,25 @@ final class NodeHash<T> {
     return h & Integer.MAX_VALUE;
   }
 
-  public int add(Builder.UnCompiledNode<T> nodeIn) throws IOException {
-    // System.out.println("hash: add count=" + count + " vs " + table.length);
-    final FST.BytesReader in = fst.getBytesReader(0);
+  public long add(Builder.UnCompiledNode<T> nodeIn) throws IOException {
+    // System.out.println("hash: add count=" + count + " vs " + table.size());
     final int h = hash(nodeIn);
     int pos = h & mask;
     int c = 0;
     while(true) {
-      final int v = table[pos];
+      final long v = table.get(pos);
       if (v == 0) {
         // freeze & add
-        final int node = fst.addNode(nodeIn);
+        final long node = fst.addNode(nodeIn);
         //System.out.println("  now freeze node=" + node);
         assert hash(node) == h : "frozenHash=" + hash(node) + " vs h=" + h;
         count++;
-        table[pos] = node;
-        if (table.length < 2*count) {
+        table.set(pos, node);
+        if (table.size() < 2*count) {
           rehash();
         }
         return node;
-      } else if (nodesEqual(nodeIn, v, in)) {
+      } else if (nodesEqual(nodeIn, v)) {
         // same node is already here
         return v;
       }
@@ -139,12 +143,12 @@ final class NodeHash<T> {
   }
 
   // called only by rehash
-  private void addNew(int address) throws IOException {
+  private void addNew(long address) throws IOException {
     int pos = hash(address) & mask;
     int c = 0;
     while(true) {
-      if (table[pos] == 0) {
-        table[pos] = address;
+      if (table.get(pos) == 0) {
+        table.set(pos, address);
         break;
       }
 
@@ -154,16 +158,16 @@ final class NodeHash<T> {
   }
 
   private void rehash() throws IOException {
-    final int[] oldTable = table;
+    final GrowableWriter oldTable = table;
 
-    if (oldTable.length >= Integer.MAX_VALUE/2) {
+    if (oldTable.size() >= Integer.MAX_VALUE/2) {
       throw new IllegalStateException("FST too large (> 2.1 GB)");
     }
 
-    table = new int[2*table.length];
-    mask = table.length-1;
-    for(int idx=0;idx<oldTable.length;idx++) {
-      final int address = oldTable[idx];
+    table = new GrowableWriter(oldTable.getBitsPerValue(), 2*oldTable.size(), PackedInts.COMPACT);
+    mask = table.size()-1;
+    for(int idx=0;idx<oldTable.size();idx++) {
+      final long address = oldTable.get(idx);
       if (address != 0) {
         addNew(address);
       }

Modified: lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/fst/Util.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/fst/Util.java?rev=1454862&r1=1454861&r2=1454862&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/fst/Util.java (original)
+++ lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/fst/Util.java Sun Mar 10 15:04:57 2013
@@ -39,7 +39,7 @@ public final class Util {
     // TODO: would be nice not to alloc this on every lookup
     final FST.Arc<T> arc = fst.getFirstArc(new FST.Arc<T>());
 
-    final FST.BytesReader fstReader = fst.getBytesReader(0);
+    final BytesReader fstReader = fst.getBytesReader();
 
     // Accumulate output as we go
     T output = fst.outputs.getNoOutput();
@@ -64,7 +64,7 @@ public final class Util {
   public static<T> T get(FST<T> fst, BytesRef input) throws IOException {
     assert fst.inputType == FST.INPUT_TYPE.BYTE1;
 
-    final FST.BytesReader fstReader = fst.getBytesReader(0);
+    final BytesReader fstReader = fst.getBytesReader();
 
     // TODO: would be nice not to alloc this on every lookup
     final FST.Arc<T> arc = fst.getFirstArc(new FST.Arc<T>());
@@ -101,7 +101,7 @@ public final class Util {
    *  fit this. */
   public static IntsRef getByOutput(FST<Long> fst, long targetOutput) throws IOException {
 
-    final FST.BytesReader in = fst.getBytesReader(0);
+    final BytesReader in = fst.getBytesReader();
 
     // TODO: would be nice not to alloc this on every lookup
     FST.Arc<Long> arc = fst.getFirstArc(new FST.Arc<Long>());
@@ -109,7 +109,15 @@ public final class Util {
     FST.Arc<Long> scratchArc = new FST.Arc<Long>();
 
     final IntsRef result = new IntsRef();
-
+    
+    return getByOutput(fst, targetOutput, in, arc, scratchArc, result);
+  }
+    
+  /** 
+   * Expert: like {@link Util#getByOutput(FST, long)} except reusing 
+   * BytesReader, initial and scratch Arc, and result.
+   */
+  public static IntsRef getByOutput(FST<Long> fst, long targetOutput, BytesReader in, Arc<Long> arc, Arc<Long> scratchArc, IntsRef result) throws IOException {
     long output = arc.output;
     int upto = 0;
 
@@ -147,8 +155,8 @@ public final class Util {
           boolean exact = false;
           while (low <= high) {
             mid = (low + high) >>> 1;
-            in.pos = arc.posArcsStart;
-            in.skip(arc.bytesPerArc*mid);
+            in.setPosition(arc.posArcsStart);
+            in.skipBytes(arc.bytesPerArc*mid);
             final byte flags = in.readByte();
             fst.readLabel(in);
             final long minArcOutput;
@@ -273,7 +281,7 @@ public final class Util {
   public static class TopNSearcher<T> {
 
     private final FST<T> fst;
-    private final FST.BytesReader bytesReader;
+    private final BytesReader bytesReader;
     private final int topN;
     private final int maxQueueDepth;
 
@@ -285,7 +293,7 @@ public final class Util {
 
     public TopNSearcher(FST<T> fst, int topN, int maxQueueDepth, Comparator<T> comparator) {
       this.fst = fst;
-      this.bytesReader = fst.getBytesReader(0);
+      this.bytesReader = fst.getBytesReader();
       this.topN = topN;
       this.maxQueueDepth = maxQueueDepth;
       this.comparator = comparator;
@@ -374,7 +382,7 @@ public final class Util {
 
       //System.out.println("search topN=" + topN);
 
-      final FST.BytesReader fstReader = fst.getBytesReader(0);
+      final BytesReader fstReader = fst.getBytesReader();
       final T NO_OUTPUT = fst.outputs.getNoOutput();
 
       // TODO: we could enable FST to sorting arcs by weight
@@ -544,7 +552,9 @@ public final class Util {
    * </pre>
    * 
    * <p>
-   * Note: larger FSTs (a few thousand nodes) won't even render, don't bother.
+   * Note: larger FSTs (a few thousand nodes) won't even
+   * render, don't bother.  If the FST is > 2.1 GB in size
+   * then this method will throw strange exceptions.
    * 
    * @param sameRank
    *          If <code>true</code>, the resulting <code>dot</code> file will try
@@ -578,7 +588,7 @@ public final class Util {
 
     // A bitset of already seen states (target offset).
     final BitSet seen = new BitSet();
-    seen.set(startArc.target);
+    seen.set((int) startArc.target);
 
     // Shape for states.
     final String stateShape = "circle";
@@ -595,7 +605,7 @@ public final class Util {
     emitDotState(out, "initial", "point", "white", "");
 
     final T NO_OUTPUT = fst.outputs.getNoOutput();
-    final FST.BytesReader r = fst.getBytesReader(0);
+    final BytesReader r = fst.getBytesReader();
 
     // final FST.Arc<T> scratchArc = new FST.Arc<T>();
 
@@ -617,7 +627,7 @@ public final class Util {
         finalOutput = null;
       }
       
-      emitDotState(out, Integer.toString(startArc.target), isFinal ? finalStateShape : stateShape, stateColor, finalOutput == null ? "" : fst.outputs.outputToString(finalOutput));
+      emitDotState(out, Long.toString(startArc.target), isFinal ? finalStateShape : stateShape, stateColor, finalOutput == null ? "" : fst.outputs.outputToString(finalOutput));
     }
 
     out.write("  initial -> " + startArc.target + "\n");
@@ -638,7 +648,8 @@ public final class Util {
         if (FST.targetHasArcs(arc)) {
           // scan all target arcs
           //System.out.println("  readFirstTarget...");
-          final int node = arc.target;
+
+          final long node = arc.target;
 
           fst.readFirstRealTargetArc(arc.target, arc, r);
 
@@ -648,7 +659,7 @@ public final class Util {
 
             //System.out.println("  cycle arc=" + arc);
             // Emit the unseen state and add it to the queue for the next level.
-            if (arc.target >= 0 && !seen.get(arc.target)) {
+            if (arc.target >= 0 && !seen.get((int) arc.target)) {
 
               /*
               boolean isFinal = false;
@@ -675,12 +686,12 @@ public final class Util {
                 finalOutput = "";
               }
 
-              emitDotState(out, Integer.toString(arc.target), stateShape, stateColor, finalOutput);
+              emitDotState(out, Long.toString(arc.target), stateShape, stateColor, finalOutput);
               // To see the node address, use this instead:
               //emitDotState(out, Integer.toString(arc.target), stateShape, stateColor, String.valueOf(arc.target));
-              seen.set(arc.target);
+              seen.set((int) arc.target);
               nextLevelQueue.add(new FST.Arc<T>().copyFrom(arc));
-              sameLevelStates.add(arc.target);
+              sameLevelStates.add((int) arc.target);
             }
 
             String outs;
@@ -893,8 +904,8 @@ public final class Util {
       // " targetLabel=" + targetLabel);
       while (low <= high) {
         mid = (low + high) >>> 1;
-        in.pos = arc.posArcsStart;
-        in.skip(arc.bytesPerArc * mid + 1);
+        in.setPosition(arc.posArcsStart);
+        in.skipBytes(arc.bytesPerArc * mid + 1);
         final int midLabel = fst.readLabel(in);
         final int cmp = midLabel - label;
         // System.out.println("  cycle low=" + low + " high=" + high + " mid=" +

Modified: lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperation.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperation.java?rev=1454862&r1=1454861&r2=1454862&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperation.java (original)
+++ lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperation.java Sun Mar 10 15:04:57 2013
@@ -2,7 +2,6 @@
 
 package org.apache.lucene.util.packed;
 
-
 /*
  * Licensed to the Apache Software Foundation (ASF) under one or more
  * contributor license agreements.  See the NOTICE file distributed with
@@ -153,35 +152,30 @@ abstract class BulkOperation implements 
    * For every number of bits per value, there is a minimum number of
    * blocks (b) / values (v) you need to write in order to reach the next block
    * boundary:
-   *  - 16 bits per value -> b=1, v=4
-   *  - 24 bits per value -> b=3, v=8
-   *  - 50 bits per value -> b=25, v=32
-   *  - 63 bits per value -> b=63, v=64
+   *  - 16 bits per value -> b=2, v=1
+   *  - 24 bits per value -> b=3, v=1
+   *  - 50 bits per value -> b=25, v=4
+   *  - 63 bits per value -> b=63, v=8
    *  - ...
-   * <p>
+   *
    * A bulk read consists in copying <code>iterations*v</code> values that are
    * contained in <code>iterations*b</code> blocks into a <code>long[]</code>
    * (higher values of <code>iterations</code> are likely to yield a better
-   * throughput) => this requires n * (b + v) longs in memory.
-   * <p>
+   * throughput) => this requires n * (b + 8v) bytes of memory.
+   *
    * This method computes <code>iterations</code> as
-   * <code>ramBudget / (8 * (b + v))</code> (since a long is 8 bytes).
-   * <p>
-   * The resulting number of iterations of this method is guaranteed not to
-   * overflow when multiplied by
-   * <tt>8 * {@link PackedInts.Encoder#blockCount()}</tt> or
-   * <tt>8 * {@link PackedInts.Decoder#blockCount()}</tt>.
+   * <code>ramBudget / (b + 8v)</code> (since a long is 8 bytes).
    */
   public final int computeIterations(int valueCount, int ramBudget) {
-    final int iterations = (ramBudget >>> 3) / (blockCount() + valueCount());
+    final int iterations = ramBudget / (byteBlockCount() + 8 * byteValueCount());
     if (iterations == 0) {
       // at least 1
       return 1;
-    } else if ((iterations - 1) * blockCount() >= valueCount) {
+    } else if ((iterations - 1) * byteValueCount() >= valueCount) {
       // don't allocate for more than the size of the reader
-      return (int) Math.ceil((double) valueCount / valueCount());
+      return (int) Math.ceil((double) valueCount / byteValueCount());
     } else {
       return iterations;
     }
   }
-}
\ No newline at end of file
+}

Modified: lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked.java?rev=1454862&r1=1454861&r2=1454862&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked.java (original)
+++ lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked.java Sun Mar 10 15:04:57 2013
@@ -1,5 +1,6 @@
 package org.apache.lucene.util.packed;
 
+
 /*
  * Licensed to the Apache Software Foundation (ASF) under one or more
  * contributor license agreements.  See the NOTICE file distributed with
@@ -23,9 +24,12 @@ package org.apache.lucene.util.packed;
 class BulkOperationPacked extends BulkOperation {
 
   private final int bitsPerValue;
-  private final int blockCount;
-  private final int valueCount;
+  private final int longBlockCount;
+  private final int longValueCount;
+  private final int byteBlockCount;
+  private final int byteValueCount;
   private final long mask;
+  private final int intMask;
 
   public BulkOperationPacked(int bitsPerValue) {
     this.bitsPerValue = bitsPerValue;
@@ -34,31 +38,50 @@ class BulkOperationPacked extends BulkOp
     while ((blocks & 1) == 0) {
       blocks >>>= 1;
     }
-    this.blockCount = blocks;
-    this.valueCount = 64 * blockCount / bitsPerValue;
+    this.longBlockCount = blocks;
+    this.longValueCount = 64 * longBlockCount / bitsPerValue;
+    int byteBlockCount = 8 * longBlockCount;
+    int byteValueCount = longValueCount;
+    while ((byteBlockCount & 1) == 0 && (byteValueCount & 1) == 0) {
+      byteBlockCount >>>= 1;
+      byteValueCount >>>= 1;
+    }
+    this.byteBlockCount = byteBlockCount;
+    this.byteValueCount = byteValueCount;
     if (bitsPerValue == 64) {
       this.mask = ~0L;
     } else {
       this.mask = (1L << bitsPerValue) - 1;
     }
-    assert valueCount * bitsPerValue == 64 * blockCount;
+    this.intMask = (int) mask;
+    assert longValueCount * bitsPerValue == 64 * longBlockCount;
+  }
+
+  @Override
+  public int longBlockCount() {
+    return longBlockCount;
   }
 
   @Override
-  public int blockCount() {
-    return blockCount;
+  public int longValueCount() {
+    return longValueCount;
   }
 
   @Override
-  public int valueCount() {
-    return valueCount;
+  public int byteBlockCount() {
+    return byteBlockCount;
+  }
+
+  @Override
+  public int byteValueCount() {
+    return byteValueCount;
   }
 
   @Override
   public void decode(long[] blocks, int blocksOffset, long[] values,
       int valuesOffset, int iterations) {
     int bitsLeft = 64;
-    for (int i = 0; i < valueCount * iterations; ++i) {
+    for (int i = 0; i < longValueCount * iterations; ++i) {
       bitsLeft -= bitsPerValue;
       if (bitsLeft < 0) {
         values[valuesOffset++] =
@@ -74,22 +97,28 @@ class BulkOperationPacked extends BulkOp
   @Override
   public void decode(byte[] blocks, int blocksOffset, long[] values,
       int valuesOffset, int iterations) {
-    int blockBitsLeft = 8;
-    int valueBitsLeft = bitsPerValue;
-    long nextValue = 0;
-    for (int end = valuesOffset + iterations * valueCount; valuesOffset < end; ) {
-      if (valueBitsLeft > blockBitsLeft) {
-        nextValue |= (blocks[blocksOffset++] & ((1L << blockBitsLeft) - 1)) << (valueBitsLeft - blockBitsLeft);
-        valueBitsLeft -= blockBitsLeft;
-        blockBitsLeft = 8;
-      } else {
-        nextValue |= ((blocks[blocksOffset] & 0xFFL) >>> (blockBitsLeft - valueBitsLeft)) & ((1L << valueBitsLeft) - 1);
-        values[valuesOffset++] = nextValue;
-        nextValue = 0;
-        blockBitsLeft -= valueBitsLeft;
-        valueBitsLeft = bitsPerValue;
+    long nextValue = 0L;
+    int bitsLeft = bitsPerValue;
+    for (int i = 0; i < iterations * byteBlockCount; ++i) {
+      final long bytes = blocks[blocksOffset++] & 0xFFL;
+      if (bitsLeft > 8) {
+        // just buffer
+        bitsLeft -= 8;
+        nextValue |= bytes << bitsLeft;
+      } else {
+        // flush
+        int bits = 8 - bitsLeft;
+        values[valuesOffset++] = nextValue | (bytes >>> bits);
+        while (bits >= bitsPerValue) {
+          bits -= bitsPerValue;
+          values[valuesOffset++] = (bytes >>> bits) & mask;
+        }
+        // then buffer
+        bitsLeft = bitsPerValue - bits;
+        nextValue = (bytes & ((1L << bits) - 1)) << bitsLeft;
       }
     }
+    assert bitsLeft == bitsPerValue;
   }
 
   @Override
@@ -99,7 +128,7 @@ class BulkOperationPacked extends BulkOp
       throw new UnsupportedOperationException("Cannot decode " + bitsPerValue + "-bits values into an int[]");
     }
     int bitsLeft = 64;
-    for (int i = 0; i < valueCount * iterations; ++i) {
+    for (int i = 0; i < longValueCount * iterations; ++i) {
       bitsLeft -= bitsPerValue;
       if (bitsLeft < 0) {
         values[valuesOffset++] = (int)
@@ -115,25 +144,28 @@ class BulkOperationPacked extends BulkOp
   @Override
   public void decode(byte[] blocks, int blocksOffset, int[] values,
       int valuesOffset, int iterations) {
-    if (bitsPerValue > 32) {
-      throw new UnsupportedOperationException("Cannot decode " + bitsPerValue + "-bits values into an int[]");
-    }
-    int blockBitsLeft = 8;
-    int valueBitsLeft = bitsPerValue;
     int nextValue = 0;
-    for (int end = valuesOffset + iterations * valueCount; valuesOffset < end; ) {
-      if (valueBitsLeft > blockBitsLeft) {
-        nextValue |= (blocks[blocksOffset++] & ((1L << blockBitsLeft) - 1)) << (valueBitsLeft - blockBitsLeft);
-        valueBitsLeft -= blockBitsLeft;
-        blockBitsLeft = 8;
-      } else {
-        nextValue |= ((blocks[blocksOffset] & 0xFFL) >>> (blockBitsLeft - valueBitsLeft)) & ((1L << valueBitsLeft) - 1);
-        values[valuesOffset++] = nextValue;
-        nextValue = 0;
-        blockBitsLeft -= valueBitsLeft;
-        valueBitsLeft = bitsPerValue;
+    int bitsLeft = bitsPerValue;
+    for (int i = 0; i < iterations * byteBlockCount; ++i) {
+      final int bytes = blocks[blocksOffset++] & 0xFF;
+      if (bitsLeft > 8) {
+        // just buffer
+        bitsLeft -= 8;
+        nextValue |= bytes << bitsLeft;
+      } else {
+        // flush
+        int bits = 8 - bitsLeft;
+        values[valuesOffset++] = nextValue | (bytes >>> bits);
+        while (bits >= bitsPerValue) {
+          bits -= bitsPerValue;
+          values[valuesOffset++] = (bytes >>> bits) & intMask;
+        }
+        // then buffer
+        bitsLeft = bitsPerValue - bits;
+        nextValue = (bytes & ((1 << bits) - 1)) << bitsLeft;
       }
     }
+    assert bitsLeft == bitsPerValue;
   }
 
   @Override
@@ -141,7 +173,7 @@ class BulkOperationPacked extends BulkOp
       int blocksOffset, int iterations) {
     long nextBlock = 0;
     int bitsLeft = 64;
-    for (int i = 0; i < valueCount * iterations; ++i) {
+    for (int i = 0; i < longValueCount * iterations; ++i) {
       bitsLeft -= bitsPerValue;
       if (bitsLeft > 0) {
         nextBlock |= values[valuesOffset++] << bitsLeft;
@@ -164,7 +196,7 @@ class BulkOperationPacked extends BulkOp
       int blocksOffset, int iterations) {
     long nextBlock = 0;
     int bitsLeft = 64;
-    for (int i = 0; i < valueCount * iterations; ++i) {
+    for (int i = 0; i < longValueCount * iterations; ++i) {
       bitsLeft -= bitsPerValue;
       if (bitsLeft > 0) {
         nextBlock |= (values[valuesOffset++] & 0xFFFFFFFFL) << bitsLeft;
@@ -185,47 +217,57 @@ class BulkOperationPacked extends BulkOp
   @Override
   public void encode(long[] values, int valuesOffset, byte[] blocks,
       int blocksOffset, int iterations) {
-    long nextBlock = 0;
-    int bitsLeft = 64;
-    for (int i = 0; i < valueCount * iterations; ++i) {
-      bitsLeft -= bitsPerValue;
-      if (bitsLeft > 0) {
-        nextBlock |= values[valuesOffset++] << bitsLeft;
-      } else if (bitsLeft == 0) {
-        nextBlock |= values[valuesOffset++];
-        blocksOffset = writeLong(nextBlock, blocks, blocksOffset);
-        nextBlock = 0;
-        bitsLeft = 64;
-      } else { // bitsLeft < 0
-        nextBlock |= values[valuesOffset] >>> -bitsLeft;
-        blocksOffset = writeLong(nextBlock, blocks, blocksOffset);
-        nextBlock = (values[valuesOffset++] & ((1L << -bitsLeft) - 1)) << (64 + bitsLeft);
-        bitsLeft += 64;
+    int nextBlock = 0;
+    int bitsLeft = 8;
+    for (int i = 0; i < byteValueCount * iterations; ++i) {
+      final long v = values[valuesOffset++];
+      assert bitsPerValue == 64 || PackedInts.bitsRequired(v) <= bitsPerValue;
+      if (bitsPerValue < bitsLeft) {
+        // just buffer
+        nextBlock |= v << (bitsLeft - bitsPerValue);
+        bitsLeft -= bitsPerValue;
+      } else {
+        // flush as many blocks as possible
+        int bits = bitsPerValue - bitsLeft;
+        blocks[blocksOffset++] = (byte) (nextBlock | (v >>> bits));
+        while (bits >= 8) {
+          bits -= 8;
+          blocks[blocksOffset++] = (byte) (v >>> bits);
+        }
+        // then buffer
+        bitsLeft = 8 - bits;
+        nextBlock = (int) ((v & ((1L << bits) - 1)) << bitsLeft);
       }
     }
+    assert bitsLeft == 8;
   }
 
   @Override
   public void encode(int[] values, int valuesOffset, byte[] blocks,
       int blocksOffset, int iterations) {
-    long nextBlock = 0;
-    int bitsLeft = 64;
-    for (int i = 0; i < valueCount * iterations; ++i) {
-      bitsLeft -= bitsPerValue;
-      if (bitsLeft > 0) {
-        nextBlock |= (values[valuesOffset++] & 0xFFFFFFFFL) << bitsLeft;
-      } else if (bitsLeft == 0) {
-        nextBlock |= (values[valuesOffset++] & 0xFFFFFFFFL);
-        blocksOffset = writeLong(nextBlock, blocks, blocksOffset);
-        nextBlock = 0;
-        bitsLeft = 64;
-      } else { // bitsLeft < 0
-        nextBlock |= (values[valuesOffset] & 0xFFFFFFFFL) >>> -bitsLeft;
-        blocksOffset = writeLong(nextBlock, blocks, blocksOffset);
-        nextBlock = (values[valuesOffset++] & ((1L << -bitsLeft) - 1)) << (64 + bitsLeft);
-        bitsLeft += 64;
+    int nextBlock = 0;
+    int bitsLeft = 8;
+    for (int i = 0; i < byteValueCount * iterations; ++i) {
+      final int v = values[valuesOffset++];
+      assert PackedInts.bitsRequired(v & 0xFFFFFFFFL) <= bitsPerValue;
+      if (bitsPerValue < bitsLeft) {
+        // just buffer
+        nextBlock |= v << (bitsLeft - bitsPerValue);
+        bitsLeft -= bitsPerValue;
+      } else {
+        // flush as many blocks as possible
+        int bits = bitsPerValue - bitsLeft;
+        blocks[blocksOffset++] = (byte) (nextBlock | (v >>> bits));
+        while (bits >= 8) {
+          bits -= 8;
+          blocks[blocksOffset++] = (byte) (v >>> bits);
+        }
+        // then buffer
+        bitsLeft = 8 - bits;
+        nextBlock = (v & ((1 << bits) - 1)) << bitsLeft;
       }
     }
+    assert bitsLeft == 8;
   }
 
 }

Modified: lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked1.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked1.java?rev=1454862&r1=1454861&r2=1454862&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked1.java (original)
+++ lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked1.java Sun Mar 10 15:04:57 2013
@@ -26,8 +26,6 @@ final class BulkOperationPacked1 extends
 
   public BulkOperationPacked1() {
     super(1);
-    assert blockCount() == 1;
-    assert valueCount() == 64;
   }
 
   @Override
@@ -42,7 +40,7 @@ final class BulkOperationPacked1 extends
 
   @Override
   public void decode(byte[] blocks, int blocksOffset, int[] values, int valuesOffset, int iterations) {
-    for (int j = 0; j < 8 * iterations; ++j) {
+    for (int j = 0; j < iterations; ++j) {
       final byte block = blocks[blocksOffset++];
       values[valuesOffset++] = (block >>> 7) & 1;
       values[valuesOffset++] = (block >>> 6) & 1;
@@ -67,7 +65,7 @@ final class BulkOperationPacked1 extends
 
   @Override
   public void decode(byte[] blocks, int blocksOffset, long[] values, int valuesOffset, int iterations) {
-    for (int j = 0; j < 8 * iterations; ++j) {
+    for (int j = 0; j < iterations; ++j) {
       final byte block = blocks[blocksOffset++];
       values[valuesOffset++] = (block >>> 7) & 1;
       values[valuesOffset++] = (block >>> 6) & 1;

Modified: lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked10.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked10.java?rev=1454862&r1=1454861&r2=1454862&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked10.java (original)
+++ lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked10.java Sun Mar 10 15:04:57 2013
@@ -26,8 +26,6 @@ final class BulkOperationPacked10 extend
 
   public BulkOperationPacked10() {
     super(10);
-    assert blockCount() == 5;
-    assert valueCount() == 32;
   }
 
   @Override
@@ -75,7 +73,7 @@ final class BulkOperationPacked10 extend
 
   @Override
   public void decode(byte[] blocks, int blocksOffset, int[] values, int valuesOffset, int iterations) {
-    for (int i = 0; i < 8 * iterations; ++i) {
+    for (int i = 0; i < iterations; ++i) {
       final int byte0 = blocks[blocksOffset++] & 0xFF;
       final int byte1 = blocks[blocksOffset++] & 0xFF;
       values[valuesOffset++] = (byte0 << 2) | (byte1 >>> 6);
@@ -133,7 +131,7 @@ final class BulkOperationPacked10 extend
 
   @Override
   public void decode(byte[] blocks, int blocksOffset, long[] values, int valuesOffset, int iterations) {
-    for (int i = 0; i < 8 * iterations; ++i) {
+    for (int i = 0; i < iterations; ++i) {
       final long byte0 = blocks[blocksOffset++] & 0xFF;
       final long byte1 = blocks[blocksOffset++] & 0xFF;
       values[valuesOffset++] = (byte0 << 2) | (byte1 >>> 6);

Modified: lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked11.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked11.java?rev=1454862&r1=1454861&r2=1454862&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked11.java (original)
+++ lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked11.java Sun Mar 10 15:04:57 2013
@@ -26,8 +26,6 @@ final class BulkOperationPacked11 extend
 
   public BulkOperationPacked11() {
     super(11);
-    assert blockCount() == 11;
-    assert valueCount() == 64;
   }
 
   @Override
@@ -113,7 +111,7 @@ final class BulkOperationPacked11 extend
 
   @Override
   public void decode(byte[] blocks, int blocksOffset, int[] values, int valuesOffset, int iterations) {
-    for (int i = 0; i < 8 * iterations; ++i) {
+    for (int i = 0; i < iterations; ++i) {
       final int byte0 = blocks[blocksOffset++] & 0xFF;
       final int byte1 = blocks[blocksOffset++] & 0xFF;
       values[valuesOffset++] = (byte0 << 3) | (byte1 >>> 5);
@@ -219,7 +217,7 @@ final class BulkOperationPacked11 extend
 
   @Override
   public void decode(byte[] blocks, int blocksOffset, long[] values, int valuesOffset, int iterations) {
-    for (int i = 0; i < 8 * iterations; ++i) {
+    for (int i = 0; i < iterations; ++i) {
       final long byte0 = blocks[blocksOffset++] & 0xFF;
       final long byte1 = blocks[blocksOffset++] & 0xFF;
       values[valuesOffset++] = (byte0 << 3) | (byte1 >>> 5);

Modified: lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked12.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked12.java?rev=1454862&r1=1454861&r2=1454862&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked12.java (original)
+++ lucene/dev/branches/lucene4258/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked12.java Sun Mar 10 15:04:57 2013
@@ -26,8 +26,6 @@ final class BulkOperationPacked12 extend
 
   public BulkOperationPacked12() {
     super(12);
-    assert blockCount() == 3;
-    assert valueCount() == 16;
   }
 
   @Override
@@ -57,7 +55,7 @@ final class BulkOperationPacked12 extend
 
   @Override
   public void decode(byte[] blocks, int blocksOffset, int[] values, int valuesOffset, int iterations) {
-    for (int i = 0; i < 8 * iterations; ++i) {
+    for (int i = 0; i < iterations; ++i) {
       final int byte0 = blocks[blocksOffset++] & 0xFF;
       final int byte1 = blocks[blocksOffset++] & 0xFF;
       values[valuesOffset++] = (byte0 << 4) | (byte1 >>> 4);
@@ -93,7 +91,7 @@ final class BulkOperationPacked12 extend
 
   @Override
   public void decode(byte[] blocks, int blocksOffset, long[] values, int valuesOffset, int iterations) {
-    for (int i = 0; i < 8 * iterations; ++i) {
+    for (int i = 0; i < iterations; ++i) {
       final long byte0 = blocks[blocksOffset++] & 0xFF;
       final long byte1 = blocks[blocksOffset++] & 0xFF;
       values[valuesOffset++] = (byte0 << 4) | (byte1 >>> 4);