You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2012/07/19 17:59:32 UTC

svn commit: r1363400 [13/31] - in /lucene/dev/branches/pforcodec_3892: ./ dev-tools/ dev-tools/eclipse/ dev-tools/idea/.idea/ dev-tools/idea/.idea/copyright/ dev-tools/idea/.idea/libraries/ dev-tools/idea/lucene/ dev-tools/maven/ dev-tools/maven/lucene...

Modified: lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed16ThreeBlocks.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed16ThreeBlocks.java?rev=1363400&r1=1363399&r2=1363400&view=diff
==============================================================================
--- lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed16ThreeBlocks.java (original)
+++ lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed16ThreeBlocks.java Thu Jul 19 15:58:54 2012
@@ -1,10 +1,6 @@
-package org.apache.lucene.util.packed;
-
-import java.io.IOException;
-import java.util.Arrays;
+// This file has been automatically generated, DO NOT EDIT
 
-import org.apache.lucene.store.DataInput;
-import org.apache.lucene.util.RamUsageEstimator;
+package org.apache.lucene.util.packed;
 
 /*
  * Licensed to the Apache Software Foundation (ASF) under one or more
@@ -23,32 +19,38 @@ import org.apache.lucene.util.RamUsageEs
  * limitations under the License.
  */
 
-/** 48 bitsPerValue backed by short[] */
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.util.RamUsageEstimator;
+
+import java.io.IOException;
+import java.util.Arrays;
+
+/**
+ * Packs integers into 3 shorts (48 bits per value).
+ * @lucene.internal
+ */
 final class Packed16ThreeBlocks extends PackedInts.MutableImpl {
+  final short[] blocks;
 
   public static final int MAX_SIZE = Integer.MAX_VALUE / 3;
 
-  private final short[] blocks;
-
   Packed16ThreeBlocks(int valueCount) {
     super(valueCount, 48);
     if (valueCount > MAX_SIZE) {
       throw new ArrayIndexOutOfBoundsException("MAX_SIZE exceeded");
     }
-    this.blocks = new short[3 * valueCount];
+    blocks = new short[valueCount * 3];
   }
 
   Packed16ThreeBlocks(DataInput in, int valueCount) throws IOException {
     this(valueCount);
-    for (int i = 0; i < blocks.length; i++) {
+    for (int i = 0; i < 3 * valueCount; ++i) {
       blocks[i] = in.readShort();
     }
     final int mod = blocks.length % 4;
     if (mod != 0) {
-      final int pad = 4 - mod;
-      // round out long
-      for (int i = 0; i < pad; i++) {
-        in.readShort();
+      for (int i = mod; i < 4; ++i) {
+         in.readShort();
       }
     }
   }
@@ -56,26 +58,55 @@ final class Packed16ThreeBlocks extends 
   @Override
   public long get(int index) {
     final int o = index * 3;
-    return (blocks[o] & 0xffffL) << 32 | (blocks[o+1] & 0xffffL) << 16 | (blocks[o+2] & 0xffffL);
+    return (blocks[o] & 0xFFFFL) << 32 | (blocks[o+1] & 0xFFFFL) << 16 | (blocks[o+2] & 0xFFFFL);
+  }
+
+  @Override
+  public int get(int index, long[] arr, int off, int len) {
+    assert len > 0 : "len must be > 0 (got " + len + ")";
+    assert index >= 0 && index < valueCount;
+    assert off + len <= arr.length;
+
+    final int gets = Math.min(valueCount - index, len);
+    for (int i = index * 3, end = (index + gets) * 3; i < end; i+=3) {
+      arr[off++] = (blocks[i] & 0xFFFFL) << 32 | (blocks[i+1] & 0xFFFFL) << 16 | (blocks[i+2] & 0xFFFFL);
+    }
+    return gets;
   }
 
   @Override
   public void set(int index, long value) {
     final int o = index * 3;
-    blocks[o] = (short) (value >> 32);
-    blocks[o+1] = (short) (value >> 16);
+    blocks[o] = (short) (value >>> 32);
+    blocks[o+1] = (short) (value >>> 16);
     blocks[o+2] = (short) value;
   }
 
   @Override
+  public int set(int index, long[] arr, int off, int len) {
+    assert len > 0 : "len must be > 0 (got " + len + ")";
+    assert index >= 0 && index < valueCount;
+    assert off + len <= arr.length;
+
+    final int sets = Math.min(valueCount - index, len);
+    for (int i = off, o = index * 3, end = off + sets; i < end; ++i) {
+      final long value = arr[i];
+      blocks[o++] = (short) (value >>> 32);
+      blocks[o++] = (short) (value >>> 16);
+      blocks[o++] = (short) value;
+    }
+    return sets;
+  }
+
+  @Override
   public void fill(int fromIndex, int toIndex, long val) {
-    short block1 = (short) (val >> 32);
-    short block2 = (short) (val >> 16);
-    short block3 = (short) val;
-    for (int i = fromIndex * 3, end = toIndex * 3; i < end; ) {
-      blocks[i++] = block1;
-      blocks[i++] = block2;
-      blocks[i++] = block3;
+    final short block1 = (short) (val >>> 32);
+    final short block2 = (short) (val >>> 16);
+    final short block3 = (short) val;
+    for (int i = fromIndex * 3, end = toIndex * 3; i < end; i += 3) {
+      blocks[i] = block1;
+      blocks[i+1] = block2;
+      blocks[i+2] = block3;
     }
   }
 

Modified: lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed64.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed64.java?rev=1363400&r1=1363399&r2=1363400&view=diff
==============================================================================
--- lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed64.java (original)
+++ lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed64.java Thu Jul 19 15:58:54 2012
@@ -25,99 +25,40 @@ import java.util.Arrays;
 
 /**
  * Space optimized random access capable array of values with a fixed number of
- * bits. For 32 bits/value and less, performance on 32 bit machines is not
- * optimal. Consider using {@link Packed32} for such a setup.
+ * bits/value. Values are packed contiguously.
  * </p><p>
- * The implementation strives to avoid conditionals and expensive operations,
- * sacrificing code clarity to achieve better performance.
+ * The implementation strives to perform af fast as possible under the
+ * constraint of contiguous bits, by avoiding expensive operations. This comes
+ * at the cost of code clarity.
+ * </p><p>
+ * Technical details: This implementation is a refinement of a non-branching
+ * version. The non-branching get and set methods meant that 2 or 4 atomics in
+ * the underlying array were always accessed, even for the cases where only
+ * 1 or 2 were needed. Even with caching, this had a detrimental effect on
+ * performance.
+ * Related to this issue, the old implementation used lookup tables for shifts
+ * and masks, which also proved to be a bit slower than calculating the shifts
+ * and masks on the fly.
+ * See https://issues.apache.org/jira/browse/LUCENE-4062 for details.
+ *
  */
-
 class Packed64 extends PackedInts.MutableImpl {
   static final int BLOCK_SIZE = 64; // 32 = int, 64 = long
   static final int BLOCK_BITS = 6; // The #bits representing BLOCK_SIZE
   static final int MOD_MASK = BLOCK_SIZE - 1; // x % BLOCK_SIZE
 
-  private static final int ENTRY_SIZE = BLOCK_SIZE + 1;
-  static final int FAC_BITPOS = 3;
-
-  /*
-   * In order to make an efficient value-getter, conditionals should be
-   * avoided. A value can be positioned inside of a block, requiring shifting
-   * left or right or it can span two blocks, requiring a left-shift on the
-   * first block and a right-shift on the right block.
-   * </p><p>
-   * By always shifting the first block both left and right, we get exactly
-   * the right bits. By always shifting the second block right and applying
-   * a mask, we get the right bits there. After that, we | the two bitsets.
-  */
-  static final int[][] SHIFTS =
-    new int[ENTRY_SIZE][ENTRY_SIZE * FAC_BITPOS];
-  static final long[][] MASKS = new long[ENTRY_SIZE][ENTRY_SIZE];
-
-  static { // Generate shifts
-      for (int elementBits = 1 ; elementBits <= BLOCK_SIZE ; elementBits++) {
-          for (int bitPos = 0 ; bitPos < BLOCK_SIZE ; bitPos++) {
-              int[] currentShifts = SHIFTS[elementBits];
-              int base = bitPos * FAC_BITPOS;
-              currentShifts[base    ] = bitPos;
-              currentShifts[base + 1] = BLOCK_SIZE - elementBits;
-              if (bitPos <= BLOCK_SIZE - elementBits) { // Single block
-                  currentShifts[base + 2] = 0;
-                  MASKS[elementBits][bitPos] = 0;
-              } else { // Two blocks
-                  int rBits = elementBits - (BLOCK_SIZE - bitPos);
-                  currentShifts[base + 2] = BLOCK_SIZE - rBits;
-                  MASKS[elementBits][bitPos] = ~(~0L << rBits);
-              }
-          }
-      }
-  }
-
-  /*
-   * The setter requires more masking than the getter.
-  */
-  private static final long[][] WRITE_MASKS =
-          new long[ENTRY_SIZE][ENTRY_SIZE * FAC_BITPOS];
-  static {
-      for (int elementBits = 1 ; elementBits <= BLOCK_SIZE ; elementBits++) {
-          long elementPosMask = ~(~0L << elementBits);
-          int[] currentShifts = SHIFTS[elementBits];
-          long[] currentMasks = WRITE_MASKS[elementBits];
-          for (int bitPos = 0 ; bitPos < BLOCK_SIZE ; bitPos++) {
-              int base = bitPos * FAC_BITPOS;
-              currentMasks[base  ] =~((elementPosMask
-                                 << currentShifts[base + 1])
-                                >>> currentShifts[base]);
-              if (bitPos <= BLOCK_SIZE - elementBits) { // Second block not used
-                currentMasks[base+1] = ~0; // Keep all bits
-                currentMasks[base+2] = 0;  // Or with 0
-              } else {
-                currentMasks[base+1] = ~(elementPosMask
-                                         << currentShifts[base + 2]);
-                currentMasks[base+2] = currentShifts[base + 2] == 0 ? 0 : ~0;
-              }
-          }
-      }
-  }
-
-  private static int pgcd(int a, int b) {
-    if (a < b) {
-      return pgcd(b, a);
-    } else if (b == 0) {
-      return a;
-    } else {
-      return pgcd(b, a % b);
-    }
-  }
-
-  /* The bits */
+  /**
+   * Values are stores contiguously in the blocks array.
+   */
   private final long[] blocks;
-
-  // Cached calculations
-  private int maxPos;      // blocks.length * BLOCK_SIZE / elementBits - 1
-  private int[] shifts;    // The shifts for the current elementBits
-  private long[] readMasks;
-  private long[] writeMasks;
+  /**
+   * A right-aligned mask of width BitsPerValue used by {@link #get(int)}.
+   */
+  private final long maskRight;
+  /**
+   * Optimization: Saves one lookup in {@link #get(int)}.
+   */
+  private final int bpvMinusBlockSize;
 
   /**
    * Creates an array with the internal structures adjusted for the given
@@ -126,18 +67,18 @@ class Packed64 extends PackedInts.Mutabl
    * @param bitsPerValue the number of bits available for any given value.
    */
   public Packed64(int valueCount, int bitsPerValue) {
-    // TODO: Test for edge-cases (2^31 values, 63 bitsPerValue)
-    // +2 due to the avoid-conditionals-trick. The last entry is always 0
-    this(new long[(int)((long)valueCount * bitsPerValue / BLOCK_SIZE + 2)],
+    // NOTE: block-size was previously calculated as
+    // valueCount * bitsPerValue / BLOCK_SIZE + 1
+    // due to memory layout requirements dictated by non-branching code
+    this(new long[size(valueCount, bitsPerValue)],
             valueCount, bitsPerValue);
   }
 
-
   /**
    * Creates an array backed by the given blocks.
    * </p><p>
    * Note: The blocks are used directly, so changes to the given block will
-   * affect the Packed32-structure.
+   * affect the Packed64-structure.
    * @param blocks   used as the internal backing array. Not that the last
    *                 element cannot be addressed directly.
    * @param valueCount the number of values.
@@ -146,7 +87,8 @@ class Packed64 extends PackedInts.Mutabl
   public Packed64(long[] blocks, int valueCount, int bitsPerValue) {
     super(valueCount, bitsPerValue);
     this.blocks = blocks;
-    updateCached();
+    maskRight = ~0L << (BLOCK_SIZE-bitsPerValue) >>> (BLOCK_SIZE-bitsPerValue);
+    bpvMinusBlockSize = bitsPerValue - BLOCK_SIZE;
   }
 
   /**
@@ -161,12 +103,12 @@ class Packed64 extends PackedInts.Mutabl
                                                             throws IOException {
     super(valueCount, bitsPerValue);
     int size = size(valueCount, bitsPerValue);
-    blocks = new long[size+1]; // +1 due to non-conditional tricks
-    // TODO: find a faster way to bulk-read longs...
+    blocks = new long[size]; // Previously +1 due to non-conditional tricks
     for(int i=0;i<size;i++) {
       blocks[i] = in.readLong();
     }
-    updateCached();
+    maskRight = ~0L << (BLOCK_SIZE-bitsPerValue) >>> (BLOCK_SIZE-bitsPerValue);
+    bpvMinusBlockSize = bitsPerValue - BLOCK_SIZE;
   }
 
   private static int size(int valueCount, int bitsPerValue) {
@@ -174,48 +116,142 @@ class Packed64 extends PackedInts.Mutabl
     return (int)(totBitCount/64 + ((totBitCount % 64 == 0 ) ? 0:1));
   }
 
-  private void updateCached() {
-    readMasks = MASKS[bitsPerValue];
-    shifts = SHIFTS[bitsPerValue];
-    writeMasks = WRITE_MASKS[bitsPerValue];
-    maxPos = (int)((((long)blocks.length) * BLOCK_SIZE / bitsPerValue) - 2);
-  }
-
   /**
    * @param index the position of the value.
    * @return the value at the given index.
    */
+  @Override
   public long get(final int index) {
-    assert index >= 0 && index < size();
+    // The abstract index in a bit stream
     final long majorBitPos = (long)index * bitsPerValue;
-    final int elementPos = (int)(majorBitPos >>> BLOCK_BITS); // / BLOCK_SIZE
-    final int bitPos =     (int)(majorBitPos & MOD_MASK); // % BLOCK_SIZE);
+    // The index in the backing long-array
+    final int elementPos = (int)(majorBitPos >>> BLOCK_BITS);
+    // The number of value-bits in the second long
+    final long endBits = (majorBitPos & MOD_MASK) + bpvMinusBlockSize;
+
+    if (endBits <= 0) { // Single block
+      return (blocks[elementPos] >>> -endBits) & maskRight;
+    }
+    // Two blocks
+    return ((blocks[elementPos] << endBits)
+        | (blocks[elementPos+1] >>> (BLOCK_SIZE - endBits)))
+        & maskRight;
+  }
+
+  @Override
+  public int get(int index, long[] arr, int off, int len) {
+    assert len > 0 : "len must be > 0 (got " + len + ")";
+    assert index >= 0 && index < valueCount;
+    len = Math.min(len, valueCount - index);
+    assert off + len <= arr.length;
+
+    final int originalIndex = index;
+    final BulkOperation op = BulkOperation.of(PackedInts.Format.PACKED, bitsPerValue);
+
+    // go to the next block where the value does not span across two blocks
+    final int offsetInBlocks = index % op.values();
+    if (offsetInBlocks != 0) {
+      for (int i = offsetInBlocks; i < op.values() && len > 0; ++i) {
+        arr[off++] = get(index++);
+        --len;
+      }
+      if (len == 0) {
+        return index - originalIndex;
+      }
+    }
 
-    final int base = bitPos * FAC_BITPOS;
-    assert elementPos < blocks.length : "elementPos: " + elementPos + "; blocks.len: " + blocks.length;
-    return ((blocks[elementPos] << shifts[base]) >>> shifts[base+1]) |
-            ((blocks[elementPos+1] >>> shifts[base+2]) & readMasks[bitPos]);
+    // bulk get
+    assert index % op.values() == 0;
+    int blockIndex = (int) ((long) index * bitsPerValue) >>> BLOCK_BITS;
+    assert (((long)index * bitsPerValue) & MOD_MASK) == 0;
+    final int iterations = len / op.values();
+    op.get(blocks, blockIndex, arr, off, iterations);
+    final int gotValues = iterations * op.values();
+    index += gotValues;
+    len -= gotValues;
+    assert len >= 0;
+
+    if (index > originalIndex) {
+      // stay at the block boundary
+      return index - originalIndex;
+    } else {
+      // no progress so far => already at a block boundary but no full block to get
+      assert index == originalIndex;
+      return super.get(index, arr, off, len);
+    }
   }
 
+  @Override
   public void set(final int index, final long value) {
+    // The abstract index in a contiguous bit stream
     final long majorBitPos = (long)index * bitsPerValue;
+    // The index in the backing long-array
     final int elementPos = (int)(majorBitPos >>> BLOCK_BITS); // / BLOCK_SIZE
-    final int bitPos =     (int)(majorBitPos & MOD_MASK); // % BLOCK_SIZE);
-    final int base = bitPos * FAC_BITPOS;
+    // The number of value-bits in the second long
+    final long endBits = (majorBitPos & MOD_MASK) + bpvMinusBlockSize;
+
+    if (endBits <= 0) { // Single block
+      blocks[elementPos] = blocks[elementPos] &  ~(maskRight << -endBits)
+         | (value << -endBits);
+      return;
+    }
+    // Two blocks
+    blocks[elementPos] = blocks[elementPos] &  ~(maskRight >>> endBits)
+        | (value >>> endBits);
+    blocks[elementPos+1] = blocks[elementPos+1] &  (~0L >>> endBits)
+        | (value << (BLOCK_SIZE - endBits));
+  }
+
+  @Override
+  public int set(int index, long[] arr, int off, int len) {
+    assert len > 0 : "len must be > 0 (got " + len + ")";
+    assert index >= 0 && index < valueCount;
+    len = Math.min(len, valueCount - index);
+    assert off + len <= arr.length;
+
+    final int originalIndex = index;
+    final BulkOperation op = BulkOperation.of(PackedInts.Format.PACKED, bitsPerValue);
+
+    // go to the next block where the value does not span across two blocks
+    final int offsetInBlocks = index % op.values();
+    if (offsetInBlocks != 0) {
+      for (int i = offsetInBlocks; i < op.values() && len > 0; ++i) {
+        set(index++, arr[off++]);
+        --len;
+      }
+      if (len == 0) {
+        return index - originalIndex;
+      }
+    }
 
-    blocks[elementPos  ] = (blocks[elementPos  ] & writeMasks[base])
-                           | (value << shifts[base + 1] >>> shifts[base]);
-    blocks[elementPos+1] = (blocks[elementPos+1] & writeMasks[base+1])
-                           | ((value << shifts[base + 2]) & writeMasks[base+2]);
+    // bulk get
+    assert index % op.values() == 0;
+    int blockIndex = (int) ((long) index * bitsPerValue) >>> BLOCK_BITS;
+    assert (((long)index * bitsPerValue) & MOD_MASK) == 0;
+    final int iterations = len / op.values();
+    op.set(blocks, blockIndex, arr, off, iterations);
+    final int setValues = iterations * op.values();
+    index += setValues;
+    len -= setValues;
+    assert len >= 0;
+
+    if (index > originalIndex) {
+      // stay at the block boundary
+      return index - originalIndex;
+    } else {
+      // no progress so far => already at a block boundary but no full block to get
+      assert index == originalIndex;
+      return super.set(index, arr, off, len);
+    }
   }
 
   @Override
   public String toString() {
     return "Packed64(bitsPerValue=" + bitsPerValue + ", size="
-            + size() + ", maxPos=" + maxPos
-            + ", elements.length=" + blocks.length + ")";
+            + size() + ", elements.length=" + blocks.length + ")";
   }
 
+  @Override
   public long ramBytesUsed() {
     return RamUsageEstimator.sizeOf(blocks);
   }
@@ -226,7 +262,7 @@ class Packed64 extends PackedInts.Mutabl
     assert fromIndex <= toIndex;
 
     // minimum number of values that use an exact number of full blocks
-    final int nAlignedValues = 64 / pgcd(64, bitsPerValue);
+    final int nAlignedValues = 64 / gcd(64, bitsPerValue);
     final int span = toIndex - fromIndex;
     if (span <= 3 * nAlignedValues) {
       // there needs be at least 2 * nAlignedValues aligned values for the
@@ -270,6 +306,17 @@ class Packed64 extends PackedInts.Mutabl
     }
   }
 
+  private static int gcd(int a, int b) {
+    if (a < b) {
+      return gcd(b, a);
+    } else if (b == 0) {
+      return a;
+    } else {
+      return gcd(b, a % b);
+    }
+  }
+
+  @Override
   public void clear() {
     Arrays.fill(blocks, 0L);
   }

Modified: lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed64SingleBlock.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed64SingleBlock.java?rev=1363400&r1=1363399&r2=1363400&view=diff
==============================================================================
--- lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed64SingleBlock.java (original)
+++ lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed64SingleBlock.java Thu Jul 19 15:58:54 2012
@@ -1,3 +1,5 @@
+// This file has been automatically generated, DO NOT EDIT
+
 package org.apache.lucene.util.packed;
 
 /*
@@ -28,93 +30,36 @@ import org.apache.lucene.util.RamUsageEs
  * speed by ensuring that a single block needs to be read/written in order to
  * read/write a value.
  */
-final class Packed64SingleBlock extends PackedInts.MutableImpl {
-
-  private static final int[] SUPPORTED_BITS_PER_VALUE = new int[] {1, 2, 3, 4,
-      5, 6, 7, 8, 9, 10, 12, 16, 21, 32};
-  static final int MAX_SUPPORTED_BITS_PER_VALUE = 32;
-  private static final long[][] WRITE_MASKS = new long[MAX_SUPPORTED_BITS_PER_VALUE+1][];
-  private static final int[][] SHIFTS = new int[MAX_SUPPORTED_BITS_PER_VALUE+1][];
-  static {
-    for (int bpv : SUPPORTED_BITS_PER_VALUE) {
-      initMasks(bpv);
-    }
-  }
+abstract class Packed64SingleBlock extends PackedInts.MutableImpl {
 
-  protected static void initMasks(int bpv) {
-    int valuesPerBlock = Long.SIZE / bpv;
-    long[] writeMasks = new long[valuesPerBlock];
-    int[] shifts = new int[valuesPerBlock];
-    long bits = (1L << bpv) - 1;
-    for (int i = 0; i < valuesPerBlock; ++i) {
-      shifts[i] = bpv * i;
-      writeMasks[i] = ~(bits << shifts[i]);
-    }
-    WRITE_MASKS[bpv] = writeMasks;
-    SHIFTS[bpv] = shifts;
-  }
-
-  public static Packed64SingleBlock create(int valueCount, int bitsPerValue) {
-    if (isSupported(bitsPerValue)) {
-      return new Packed64SingleBlock(valueCount, bitsPerValue);
-    }
-    throw new IllegalArgumentException("Unsupported bitsPerValue: " + bitsPerValue);
-  }
-
-  public static Packed64SingleBlock create(DataInput in,
-      int valueCount, int bitsPerValue) throws IOException {
-    Packed64SingleBlock reader = create(valueCount, bitsPerValue);
-    for (int i = 0; i < reader.blocks.length; ++i) {
-      reader.blocks[i] = in.readLong();
-    }
-    return reader;
-  }
+  public static final int MAX_SUPPORTED_BITS_PER_VALUE = 32;
+  private static final int[] SUPPORTED_BITS_PER_VALUE = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16, 21, 32};
 
   public static boolean isSupported(int bitsPerValue) {
     return Arrays.binarySearch(SUPPORTED_BITS_PER_VALUE, bitsPerValue) >= 0;
   }
 
-  public static float overheadPerValue(int bitsPerValue) {
-    int valuesPerBlock = 64 / bitsPerValue;
-    int overhead = 64 % bitsPerValue;
-    return (float) overhead / valuesPerBlock;
+  private static int requiredCapacity(int valueCount, int valuesPerBlock) {
+    return valueCount / valuesPerBlock
+        + (valueCount % valuesPerBlock == 0 ? 0 : 1);
   }
 
   final long[] blocks;
-  final int valuesPerBlock;
-  final int[] shifts;
-  final long[] writeMasks;
-  final long readMask;
 
   Packed64SingleBlock(int valueCount, int bitsPerValue) {
     super(valueCount, bitsPerValue);
     assert isSupported(bitsPerValue);
-    valuesPerBlock = Long.SIZE / bitsPerValue;
+    final int valuesPerBlock = 64 / bitsPerValue;
     blocks = new long[requiredCapacity(valueCount, valuesPerBlock)];
-    shifts = SHIFTS[bitsPerValue];
-    writeMasks = WRITE_MASKS[bitsPerValue];
-    readMask = ~writeMasks[0];
-  }
-
-  private static int requiredCapacity(int valueCount, int valuesPerBlock) {
-    return valueCount / valuesPerBlock
-        + (valueCount % valuesPerBlock == 0 ? 0 : 1);
-  }
-
-  private int blockOffset(int offset) {
-    return offset / valuesPerBlock;
-  }
-
-  private int offsetInBlock(int offset) {
-    return offset % valuesPerBlock;
   }
 
   @Override
-  public long get(int index) {
-    final int o = blockOffset(index);
-    final int b = offsetInBlock(index);
+  public void clear() {
+    Arrays.fill(blocks, 0L);
+  }
 
-    return (blocks[o] >>> shifts[b]) & readMask;
+  public long ramBytesUsed() {
+    return RamUsageEstimator.sizeOf(blocks);
   }
 
   @Override
@@ -127,7 +72,8 @@ final class Packed64SingleBlock extends 
     final int originalIndex = index;
 
     // go to the next block boundary
-    final int offsetInBlock = offsetInBlock(index);
+    final int valuesPerBlock = 64 / bitsPerValue;
+    final int offsetInBlock = index % valuesPerBlock;
     if (offsetInBlock != 0) {
       for (int i = offsetInBlock; i < valuesPerBlock && len > 0; ++i) {
         arr[off++] = get(index++);
@@ -139,16 +85,15 @@ final class Packed64SingleBlock extends 
     }
 
     // bulk get
-    assert offsetInBlock(index) == 0;
-    final int startBlock = blockOffset(index);
-    final int endBlock = blockOffset(index + len);
-    final int diff = (endBlock - startBlock) * valuesPerBlock;
+    assert index % valuesPerBlock == 0;
+    final BulkOperation op = BulkOperation.of(PackedInts.Format.PACKED_SINGLE_BLOCK, bitsPerValue);
+    assert op.blocks() == 1;
+    assert op.values() == valuesPerBlock;
+    final int blockIndex = index / valuesPerBlock;
+    final int nblocks = (index + len) / valuesPerBlock - blockIndex;
+    op.get(blocks, blockIndex, arr, off, nblocks);
+    final int diff = nblocks * valuesPerBlock;
     index += diff; len -= diff;
-    for (int block = startBlock; block < endBlock; ++block) {
-      for (int i = 0; i < valuesPerBlock; ++i) {
-        arr[off++] = (blocks[block] >> shifts[i]) & readMask;
-      }
-    }
 
     if (index > originalIndex) {
       // stay at the block boundary
@@ -162,14 +107,6 @@ final class Packed64SingleBlock extends 
   }
 
   @Override
-  public void set(int index, long value) {
-    final int o = blockOffset(index);
-    final int b = offsetInBlock(index);
-
-    blocks[o] = (blocks[o] & writeMasks[b]) | (value << shifts[b]);
-  }
-
-  @Override
   public int set(int index, long[] arr, int off, int len) {
     assert len > 0 : "len must be > 0 (got " + len + ")";
     assert index >= 0 && index < valueCount;
@@ -179,7 +116,8 @@ final class Packed64SingleBlock extends 
     final int originalIndex = index;
 
     // go to the next block boundary
-    final int offsetInBlock = offsetInBlock(index);
+    final int valuesPerBlock = 64 / bitsPerValue;
+    final int offsetInBlock = index % valuesPerBlock;
     if (offsetInBlock != 0) {
       for (int i = offsetInBlock; i < valuesPerBlock && len > 0; ++i) {
         set(index++, arr[off++]);
@@ -191,18 +129,15 @@ final class Packed64SingleBlock extends 
     }
 
     // bulk set
-    assert offsetInBlock(index) == 0;
-    final int startBlock = blockOffset(index);
-    final int endBlock = blockOffset(index + len);
-    final int diff = (endBlock - startBlock) * valuesPerBlock;
+    assert index % valuesPerBlock == 0;
+    final BulkOperation op = BulkOperation.of(PackedInts.Format.PACKED_SINGLE_BLOCK, bitsPerValue);
+    assert op.blocks() == 1;
+    assert op.values() == valuesPerBlock;
+    final int blockIndex = index / valuesPerBlock;
+    final int nblocks = (index + len) / valuesPerBlock - blockIndex;
+    op.set(blocks, blockIndex, arr, off, nblocks);
+    final int diff = nblocks * valuesPerBlock;
     index += diff; len -= diff;
-    for (int block = startBlock; block < endBlock; ++block) {
-      long next = 0L;
-      for (int i = 0; i < valuesPerBlock; ++i) {
-        next |= (arr[off++] << shifts[i]);
-      }
-      blocks[block] = next;
-    }
 
     if (index > originalIndex) {
       // stay at the block boundary
@@ -219,8 +154,9 @@ final class Packed64SingleBlock extends 
   public void fill(int fromIndex, int toIndex, long val) {
     assert fromIndex >= 0;
     assert fromIndex <= toIndex;
-    assert (val & readMask) == val;
+    assert PackedInts.bitsRequired(val) <= bitsPerValue;
 
+    final int valuesPerBlock = 64 / bitsPerValue;
     if (toIndex - fromIndex <= valuesPerBlock << 1) {
       // there needs to be at least one full block to set for the block
       // approach to be worth trying
@@ -229,22 +165,22 @@ final class Packed64SingleBlock extends 
     }
 
     // set values naively until the next block start
-    int fromOffsetInBlock = offsetInBlock(fromIndex);
+    int fromOffsetInBlock = fromIndex % valuesPerBlock;
     if (fromOffsetInBlock != 0) {
       for (int i = fromOffsetInBlock; i < valuesPerBlock; ++i) {
         set(fromIndex++, val);
       }
-      assert offsetInBlock(fromIndex) == 0;
+      assert fromIndex % valuesPerBlock == 0;
     }
 
     // bulk set of the inner blocks
-    final int fromBlock = blockOffset(fromIndex);
-    final int toBlock = blockOffset(toIndex);
+    final int fromBlock = fromIndex / valuesPerBlock;
+    final int toBlock = toIndex / valuesPerBlock;
     assert fromBlock * valuesPerBlock == fromIndex;
 
     long blockValue = 0L;
     for (int i = 0; i < valuesPerBlock; ++i) {
-      blockValue = blockValue | (val << shifts[i]);
+      blockValue = blockValue | (val << (i * bitsPerValue));
     }
     Arrays.fill(blocks, fromBlock, toBlock, blockValue);
 
@@ -255,17 +191,8 @@ final class Packed64SingleBlock extends 
   }
 
   @Override
-  public void clear() {
-    Arrays.fill(blocks, 0L);
-  }
-
-  public long ramBytesUsed() {
-    return RamUsageEstimator.sizeOf(blocks);
-  }
-
-  @Override
-  protected int getFormat() {
-    return PackedInts.PACKED_SINGLE_BLOCK;
+  protected PackedInts.Format getFormat() {
+    return PackedInts.Format.PACKED_SINGLE_BLOCK;
   }
 
   @Override
@@ -274,4 +201,384 @@ final class Packed64SingleBlock extends 
         + ", size=" + size() + ", elements.length=" + blocks.length + ")";
   }
 
+  public static Packed64SingleBlock create(DataInput in,
+      int valueCount, int bitsPerValue) throws IOException {
+    Packed64SingleBlock reader = create(valueCount, bitsPerValue);
+    for (int i = 0; i < reader.blocks.length; ++i) {
+      reader.blocks[i] = in.readLong();
+    }
+    return reader;
+  }
+
+  public static Packed64SingleBlock create(int valueCount, int bitsPerValue) {
+    switch (bitsPerValue) {
+      case 1:
+        return new Packed64SingleBlock1(valueCount);
+      case 2:
+        return new Packed64SingleBlock2(valueCount);
+      case 3:
+        return new Packed64SingleBlock3(valueCount);
+      case 4:
+        return new Packed64SingleBlock4(valueCount);
+      case 5:
+        return new Packed64SingleBlock5(valueCount);
+      case 6:
+        return new Packed64SingleBlock6(valueCount);
+      case 7:
+        return new Packed64SingleBlock7(valueCount);
+      case 8:
+        return new Packed64SingleBlock8(valueCount);
+      case 9:
+        return new Packed64SingleBlock9(valueCount);
+      case 10:
+        return new Packed64SingleBlock10(valueCount);
+      case 12:
+        return new Packed64SingleBlock12(valueCount);
+      case 16:
+        return new Packed64SingleBlock16(valueCount);
+      case 21:
+        return new Packed64SingleBlock21(valueCount);
+      case 32:
+        return new Packed64SingleBlock32(valueCount);
+      default:
+        throw new IllegalArgumentException("Unsupported number of bits per value: " + 32);
+    }
+  }
+
+  static class Packed64SingleBlock1 extends Packed64SingleBlock {
+
+    Packed64SingleBlock1(int valueCount) {
+      super(valueCount, 1);
+    }
+
+    @Override
+    public long get(int index) {
+      final int o = index >>> 6;
+      final int b = index & 63;
+      final int shift = b << 0;
+      return (blocks[o] >>> shift) & 1L;
+    }
+
+    @Override
+    public void set(int index, long value) {
+      final int o = index >>> 6;
+      final int b = index & 63;
+      final int shift = b << 0;
+      blocks[o] = (blocks[o] & ~(1L << shift)) | (value << shift);
+    }
+
+  }
+
+  static class Packed64SingleBlock2 extends Packed64SingleBlock {
+
+    Packed64SingleBlock2(int valueCount) {
+      super(valueCount, 2);
+    }
+
+    @Override
+    public long get(int index) {
+      final int o = index >>> 5;
+      final int b = index & 31;
+      final int shift = b << 1;
+      return (blocks[o] >>> shift) & 3L;
+    }
+
+    @Override
+    public void set(int index, long value) {
+      final int o = index >>> 5;
+      final int b = index & 31;
+      final int shift = b << 1;
+      blocks[o] = (blocks[o] & ~(3L << shift)) | (value << shift);
+    }
+
+  }
+
+  static class Packed64SingleBlock3 extends Packed64SingleBlock {
+
+    Packed64SingleBlock3(int valueCount) {
+      super(valueCount, 3);
+    }
+
+    @Override
+    public long get(int index) {
+      final int o = index / 21;
+      final int b = index % 21;
+      final int shift = b * 3;
+      return (blocks[o] >>> shift) & 7L;
+    }
+
+    @Override
+    public void set(int index, long value) {
+      final int o = index / 21;
+      final int b = index % 21;
+      final int shift = b * 3;
+      blocks[o] = (blocks[o] & ~(7L << shift)) | (value << shift);
+    }
+
+  }
+
+  static class Packed64SingleBlock4 extends Packed64SingleBlock {
+
+    Packed64SingleBlock4(int valueCount) {
+      super(valueCount, 4);
+    }
+
+    @Override
+    public long get(int index) {
+      final int o = index >>> 4;
+      final int b = index & 15;
+      final int shift = b << 2;
+      return (blocks[o] >>> shift) & 15L;
+    }
+
+    @Override
+    public void set(int index, long value) {
+      final int o = index >>> 4;
+      final int b = index & 15;
+      final int shift = b << 2;
+      blocks[o] = (blocks[o] & ~(15L << shift)) | (value << shift);
+    }
+
+  }
+
+  static class Packed64SingleBlock5 extends Packed64SingleBlock {
+
+    Packed64SingleBlock5(int valueCount) {
+      super(valueCount, 5);
+    }
+
+    @Override
+    public long get(int index) {
+      final int o = index / 12;
+      final int b = index % 12;
+      final int shift = b * 5;
+      return (blocks[o] >>> shift) & 31L;
+    }
+
+    @Override
+    public void set(int index, long value) {
+      final int o = index / 12;
+      final int b = index % 12;
+      final int shift = b * 5;
+      blocks[o] = (blocks[o] & ~(31L << shift)) | (value << shift);
+    }
+
+  }
+
+  static class Packed64SingleBlock6 extends Packed64SingleBlock {
+
+    Packed64SingleBlock6(int valueCount) {
+      super(valueCount, 6);
+    }
+
+    @Override
+    public long get(int index) {
+      final int o = index / 10;
+      final int b = index % 10;
+      final int shift = b * 6;
+      return (blocks[o] >>> shift) & 63L;
+    }
+
+    @Override
+    public void set(int index, long value) {
+      final int o = index / 10;
+      final int b = index % 10;
+      final int shift = b * 6;
+      blocks[o] = (blocks[o] & ~(63L << shift)) | (value << shift);
+    }
+
+  }
+
+  static class Packed64SingleBlock7 extends Packed64SingleBlock {
+
+    Packed64SingleBlock7(int valueCount) {
+      super(valueCount, 7);
+    }
+
+    @Override
+    public long get(int index) {
+      final int o = index / 9;
+      final int b = index % 9;
+      final int shift = b * 7;
+      return (blocks[o] >>> shift) & 127L;
+    }
+
+    @Override
+    public void set(int index, long value) {
+      final int o = index / 9;
+      final int b = index % 9;
+      final int shift = b * 7;
+      blocks[o] = (blocks[o] & ~(127L << shift)) | (value << shift);
+    }
+
+  }
+
+  static class Packed64SingleBlock8 extends Packed64SingleBlock {
+
+    Packed64SingleBlock8(int valueCount) {
+      super(valueCount, 8);
+    }
+
+    @Override
+    public long get(int index) {
+      final int o = index >>> 3;
+      final int b = index & 7;
+      final int shift = b << 3;
+      return (blocks[o] >>> shift) & 255L;
+    }
+
+    @Override
+    public void set(int index, long value) {
+      final int o = index >>> 3;
+      final int b = index & 7;
+      final int shift = b << 3;
+      blocks[o] = (blocks[o] & ~(255L << shift)) | (value << shift);
+    }
+
+  }
+
+  static class Packed64SingleBlock9 extends Packed64SingleBlock {
+
+    Packed64SingleBlock9(int valueCount) {
+      super(valueCount, 9);
+    }
+
+    @Override
+    public long get(int index) {
+      final int o = index / 7;
+      final int b = index % 7;
+      final int shift = b * 9;
+      return (blocks[o] >>> shift) & 511L;
+    }
+
+    @Override
+    public void set(int index, long value) {
+      final int o = index / 7;
+      final int b = index % 7;
+      final int shift = b * 9;
+      blocks[o] = (blocks[o] & ~(511L << shift)) | (value << shift);
+    }
+
+  }
+
+  static class Packed64SingleBlock10 extends Packed64SingleBlock {
+
+    Packed64SingleBlock10(int valueCount) {
+      super(valueCount, 10);
+    }
+
+    @Override
+    public long get(int index) {
+      final int o = index / 6;
+      final int b = index % 6;
+      final int shift = b * 10;
+      return (blocks[o] >>> shift) & 1023L;
+    }
+
+    @Override
+    public void set(int index, long value) {
+      final int o = index / 6;
+      final int b = index % 6;
+      final int shift = b * 10;
+      blocks[o] = (blocks[o] & ~(1023L << shift)) | (value << shift);
+    }
+
+  }
+
+  static class Packed64SingleBlock12 extends Packed64SingleBlock {
+
+    Packed64SingleBlock12(int valueCount) {
+      super(valueCount, 12);
+    }
+
+    @Override
+    public long get(int index) {
+      final int o = index / 5;
+      final int b = index % 5;
+      final int shift = b * 12;
+      return (blocks[o] >>> shift) & 4095L;
+    }
+
+    @Override
+    public void set(int index, long value) {
+      final int o = index / 5;
+      final int b = index % 5;
+      final int shift = b * 12;
+      blocks[o] = (blocks[o] & ~(4095L << shift)) | (value << shift);
+    }
+
+  }
+
+  static class Packed64SingleBlock16 extends Packed64SingleBlock {
+
+    Packed64SingleBlock16(int valueCount) {
+      super(valueCount, 16);
+    }
+
+    @Override
+    public long get(int index) {
+      final int o = index >>> 2;
+      final int b = index & 3;
+      final int shift = b << 4;
+      return (blocks[o] >>> shift) & 65535L;
+    }
+
+    @Override
+    public void set(int index, long value) {
+      final int o = index >>> 2;
+      final int b = index & 3;
+      final int shift = b << 4;
+      blocks[o] = (blocks[o] & ~(65535L << shift)) | (value << shift);
+    }
+
+  }
+
+  static class Packed64SingleBlock21 extends Packed64SingleBlock {
+
+    Packed64SingleBlock21(int valueCount) {
+      super(valueCount, 21);
+    }
+
+    @Override
+    public long get(int index) {
+      final int o = index / 3;
+      final int b = index % 3;
+      final int shift = b * 21;
+      return (blocks[o] >>> shift) & 2097151L;
+    }
+
+    @Override
+    public void set(int index, long value) {
+      final int o = index / 3;
+      final int b = index % 3;
+      final int shift = b * 21;
+      blocks[o] = (blocks[o] & ~(2097151L << shift)) | (value << shift);
+    }
+
+  }
+
+  static class Packed64SingleBlock32 extends Packed64SingleBlock {
+
+    Packed64SingleBlock32(int valueCount) {
+      super(valueCount, 32);
+    }
+
+    @Override
+    public long get(int index) {
+      final int o = index >>> 1;
+      final int b = index & 1;
+      final int shift = b << 5;
+      return (blocks[o] >>> shift) & 4294967295L;
+    }
+
+    @Override
+    public void set(int index, long value) {
+      final int o = index >>> 1;
+      final int b = index & 1;
+      final int shift = b << 5;
+      blocks[o] = (blocks[o] & ~(4294967295L << shift)) | (value << shift);
+    }
+
+  }
+
 }
\ No newline at end of file

Modified: lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed8ThreeBlocks.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed8ThreeBlocks.java?rev=1363400&r1=1363399&r2=1363400&view=diff
==============================================================================
--- lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed8ThreeBlocks.java (original)
+++ lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed8ThreeBlocks.java Thu Jul 19 15:58:54 2012
@@ -1,10 +1,6 @@
-package org.apache.lucene.util.packed;
-
-import java.io.IOException;
-import java.util.Arrays;
+// This file has been automatically generated, DO NOT EDIT
 
-import org.apache.lucene.store.DataInput;
-import org.apache.lucene.util.RamUsageEstimator;
+package org.apache.lucene.util.packed;
 
 /*
  * Licensed to the Apache Software Foundation (ASF) under one or more
@@ -23,32 +19,38 @@ import org.apache.lucene.util.RamUsageEs
  * limitations under the License.
  */
 
-/** 24 bitsPerValue backed by byte[] */
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.util.RamUsageEstimator;
+
+import java.io.IOException;
+import java.util.Arrays;
+
+/**
+ * Packs integers into 3 bytes (24 bits per value).
+ * @lucene.internal
+ */
 final class Packed8ThreeBlocks extends PackedInts.MutableImpl {
+  final byte[] blocks;
 
   public static final int MAX_SIZE = Integer.MAX_VALUE / 3;
 
-  private final byte[] blocks;
-
   Packed8ThreeBlocks(int valueCount) {
     super(valueCount, 24);
     if (valueCount > MAX_SIZE) {
       throw new ArrayIndexOutOfBoundsException("MAX_SIZE exceeded");
     }
-    this.blocks = new byte[3 * valueCount];
+    blocks = new byte[valueCount * 3];
   }
 
   Packed8ThreeBlocks(DataInput in, int valueCount) throws IOException {
     this(valueCount);
-    for (int i = 0; i < blocks.length; i++) {
+    for (int i = 0; i < 3 * valueCount; ++i) {
       blocks[i] = in.readByte();
     }
     final int mod = blocks.length % 8;
     if (mod != 0) {
-      final int pad = 8 - mod;
-      // round out long
-      for (int i = 0; i < pad; i++) {
-        in.readByte();
+      for (int i = mod; i < 8; ++i) {
+         in.readByte();
       }
     }
   }
@@ -56,26 +58,55 @@ final class Packed8ThreeBlocks extends P
   @Override
   public long get(int index) {
     final int o = index * 3;
-    return (blocks[o] & 0xffL) << 16 | (blocks[o+1] & 0xffL) << 8 | (blocks[o+2] & 0xffL);
+    return (blocks[o] & 0xFFL) << 16 | (blocks[o+1] & 0xFFL) << 8 | (blocks[o+2] & 0xFFL);
+  }
+
+  @Override
+  public int get(int index, long[] arr, int off, int len) {
+    assert len > 0 : "len must be > 0 (got " + len + ")";
+    assert index >= 0 && index < valueCount;
+    assert off + len <= arr.length;
+
+    final int gets = Math.min(valueCount - index, len);
+    for (int i = index * 3, end = (index + gets) * 3; i < end; i+=3) {
+      arr[off++] = (blocks[i] & 0xFFL) << 16 | (blocks[i+1] & 0xFFL) << 8 | (blocks[i+2] & 0xFFL);
+    }
+    return gets;
   }
 
   @Override
   public void set(int index, long value) {
     final int o = index * 3;
+    blocks[o] = (byte) (value >>> 16);
+    blocks[o+1] = (byte) (value >>> 8);
     blocks[o+2] = (byte) value;
-    blocks[o+1] = (byte) (value >> 8);
-    blocks[o] = (byte) (value >> 16);
+  }
+
+  @Override
+  public int set(int index, long[] arr, int off, int len) {
+    assert len > 0 : "len must be > 0 (got " + len + ")";
+    assert index >= 0 && index < valueCount;
+    assert off + len <= arr.length;
+
+    final int sets = Math.min(valueCount - index, len);
+    for (int i = off, o = index * 3, end = off + sets; i < end; ++i) {
+      final long value = arr[i];
+      blocks[o++] = (byte) (value >>> 16);
+      blocks[o++] = (byte) (value >>> 8);
+      blocks[o++] = (byte) value;
+    }
+    return sets;
   }
 
   @Override
   public void fill(int fromIndex, int toIndex, long val) {
-    byte block1 = (byte) (val >> 16);
-    byte block2 = (byte) (val >> 8);
-    byte block3 = (byte) val;
-    for (int i = fromIndex * 3, end = toIndex * 3; i < end; ) {
-      blocks[i++] = block1;
-      blocks[i++] = block2;
-      blocks[i++] = block3;
+    final byte block1 = (byte) (val >>> 16);
+    final byte block2 = (byte) (val >>> 8);
+    final byte block3 = (byte) val;
+    for (int i = fromIndex * 3, end = toIndex * 3; i < end; i += 3) {
+      blocks[i] = block1;
+      blocks[i+1] = block2;
+      blocks[i+2] = block3;
     }
   }
 
@@ -93,5 +124,4 @@ final class Packed8ThreeBlocks extends P
     return getClass().getSimpleName() + "(bitsPerValue=" + bitsPerValue
         + ", size=" + size() + ", elements.length=" + blocks.length + ")";
   }
-
 }

Modified: lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedInts.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedInts.java?rev=1363400&r1=1363399&r2=1363400&view=diff
==============================================================================
--- lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedInts.java (original)
+++ lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedInts.java Thu Jul 19 15:58:54 2012
@@ -19,10 +19,11 @@ package org.apache.lucene.util.packed;
 
 import java.io.Closeable;
 
+import org.apache.lucene.codecs.CodecUtil;
 import org.apache.lucene.store.DataInput;
 import org.apache.lucene.store.DataOutput;
 import org.apache.lucene.store.IndexInput;
-import org.apache.lucene.util.CodecUtil;
+import org.apache.lucene.util.LongsRef;
 
 import java.io.IOException;
 
@@ -34,7 +35,6 @@ import java.io.IOException;
  *
  * @lucene.internal
  */
-
 public class PackedInts {
 
   /**
@@ -62,12 +62,184 @@ public class PackedInts {
    */
   public static final int DEFAULT_BUFFER_SIZE = 1024; // 1K
 
-  private final static String CODEC_NAME = "PackedInts";
-  private final static int VERSION_START = 0;
-  private final static int VERSION_CURRENT = VERSION_START;
+  public final static String CODEC_NAME = "PackedInts";
+  public final static int VERSION_START = 0;
+  public final static int VERSION_CURRENT = VERSION_START;
+
+  /**
+   * A format to write packed ints.
+   *
+   * @lucene.internal
+   */
+  public enum Format {
+    /**
+     * Compact format, all bits are written contiguously.
+     */
+    PACKED(0) {
+
+      @Override
+      public int nblocks(int bitsPerValue, int values) {
+        return (int) Math.ceil((double) values * bitsPerValue / 64);
+      }
+
+    },
+
+    /**
+     * A format that may insert padding bits to improve encoding and decoding
+     * speed. Since this format doesn't support all possible bits per value, you
+     * should never use it directly, but rather use
+     * {@link PackedInts#fastestFormatAndBits(int, int, float)} to find the
+     * format that best suits your needs.
+     */
+    PACKED_SINGLE_BLOCK(1) {
+
+      @Override
+      public int nblocks(int bitsPerValue, int values) {
+        final int valuesPerBlock = 64 / bitsPerValue;
+        return (int) Math.ceil((double) values / valuesPerBlock);
+      }
+
+      @Override
+      public boolean isSupported(int bitsPerValue) {
+        return Packed64SingleBlock.isSupported(bitsPerValue);
+      }
+
+      @Override
+      public float overheadPerValue(int bitsPerValue) {
+        assert isSupported(bitsPerValue);
+        final int valuesPerBlock = 64 / bitsPerValue;
+        final int overhead = 64 % bitsPerValue;
+        return (float) overhead / valuesPerBlock;
+      }
+
+    };
+
+    /**
+     * Get a format according to its ID.
+     */
+    public static Format byId(int id) {
+      for (Format format : Format.values()) {
+        if (format.getId() == id) {
+          return format;
+        }
+      }
+      throw new IllegalArgumentException("Unknown format id: " + id);
+    }
+
+    private Format(int id) {
+      this.id = id;
+    }
+
+    public int id;
+
+    /**
+     * Returns the ID of the format.
+     */
+    public int getId() {
+      return id;
+    }
+
+    /**
+     * Computes how many blocks are needed to store <code>values</code> values
+     * of size <code>bitsPerValue</code>.
+     */
+    public abstract int nblocks(int bitsPerValue, int values);
+
+    /**
+     * Tests whether the provided number of bits per value is supported by the
+     * format.
+     */
+    public boolean isSupported(int bitsPerValue) {
+      return bitsPerValue >= 1 && bitsPerValue <= 64;
+    }
+
+    /**
+     * Returns the overhead per value, in bits.
+     */
+    public float overheadPerValue(int bitsPerValue) {
+      assert isSupported(bitsPerValue);
+      return 0f;
+    }
+
+    /**
+     * Returns the overhead ratio (<code>overhead per value / bits per value</code>).
+     */
+    public final float overheadRatio(int bitsPerValue) {
+      assert isSupported(bitsPerValue);
+      return overheadPerValue(bitsPerValue) / bitsPerValue;
+    }
+  }
+
+  /**
+   * Simple class that holds a format and a number of bits per value.
+   */
+  public static class FormatAndBits {
+    public final Format format;
+    public final int bitsPerValue;
+    public FormatAndBits(Format format, int bitsPerValue) {
+      this.format = format;
+      this.bitsPerValue = bitsPerValue;
+    }
+  }
+
+  /**
+   * Try to find the {@link Format} and number of bits per value that would
+   * restore from disk the fastest reader whose overhead is less than
+   * <code>acceptableOverheadRatio</code>.
+   * </p><p>
+   * The <code>acceptableOverheadRatio</code> parameter makes sense for
+   * random-access {@link Reader}s. In case you only plan to perform
+   * sequential access on this stream later on, you should probably use
+   * {@link PackedInts#COMPACT}.
+   * </p><p>
+   * If you don't know how many values you are going to write, use
+   * <code>valueCount = -1</code>.
+   */
+  public static FormatAndBits fastestFormatAndBits(int valueCount, int bitsPerValue, float acceptableOverheadRatio) {
+    if (valueCount == -1) {
+      valueCount = Integer.MAX_VALUE;
+    }
+
+    acceptableOverheadRatio = Math.max(COMPACT, acceptableOverheadRatio);
+    acceptableOverheadRatio = Math.min(FASTEST, acceptableOverheadRatio);
+    float acceptableOverheadPerValue = acceptableOverheadRatio * bitsPerValue; // in bits
 
-  static final int PACKED = 0;
-  static final int PACKED_SINGLE_BLOCK = 1;
+    int maxBitsPerValue = bitsPerValue + (int) acceptableOverheadPerValue;
+
+    int actualBitsPerValue = -1;
+    Format format = Format.PACKED;
+
+    if (bitsPerValue <= 8 && maxBitsPerValue >= 8) {
+      actualBitsPerValue = 8;
+    } else if (bitsPerValue <= 16 && maxBitsPerValue >= 16) {
+      actualBitsPerValue = 16;
+    } else if (bitsPerValue <= 32 && maxBitsPerValue >= 32) {
+      actualBitsPerValue = 32;
+    } else if (bitsPerValue <= 64 && maxBitsPerValue >= 64) {
+      actualBitsPerValue = 64;
+    } else if (valueCount <= Packed8ThreeBlocks.MAX_SIZE && bitsPerValue <= 24 && maxBitsPerValue >= 24) {
+      actualBitsPerValue = 24;
+    } else if (valueCount <= Packed16ThreeBlocks.MAX_SIZE && bitsPerValue <= 48 && maxBitsPerValue >= 48) {
+      actualBitsPerValue = 48;
+    } else {
+      for (int bpv = bitsPerValue; bpv <= maxBitsPerValue; ++bpv) {
+        if (Format.PACKED_SINGLE_BLOCK.isSupported(bpv)) {
+          float overhead = Format.PACKED_SINGLE_BLOCK.overheadPerValue(bpv);
+          float acceptableOverhead = acceptableOverheadPerValue + bitsPerValue - bpv;
+          if (overhead <= acceptableOverhead) {
+            actualBitsPerValue = bpv;
+            format = Format.PACKED_SINGLE_BLOCK;
+            break;
+          }
+        }
+      }
+      if (actualBitsPerValue < 0) {
+        actualBitsPerValue = bitsPerValue;
+      }
+    }
+
+    return new FormatAndBits(format, actualBitsPerValue);
+  }
 
   /**
    * A read-only random access array of positive integers.
@@ -132,31 +304,40 @@ public class PackedInts {
   public static interface ReaderIterator extends Closeable {
     /** Returns next value */
     long next() throws IOException;
+    /** Returns at least 1 and at most <code>count</code> next values,
+     * the returned ref MUST NOT be modified */
+    LongsRef next(int count) throws IOException;
     /** Returns number of bits per value */
     int getBitsPerValue();
     /** Returns number of values */
     int size();
     /** Returns the current position */
     int ord();
-    /** Skips to the given ordinal and returns its value.
-     * @return the value at the given position
-     * @throws IOException if reading the value throws an IOException*/
-    long advance(int ord) throws IOException;
   }
 
   static abstract class ReaderIteratorImpl implements ReaderIterator {
 
-    protected final IndexInput in;
+    protected final DataInput in;
     protected final int bitsPerValue;
     protected final int valueCount;
 
-    protected ReaderIteratorImpl(int valueCount, int bitsPerValue, IndexInput in) {
+    protected ReaderIteratorImpl(int valueCount, int bitsPerValue, DataInput in) {
       this.in = in;
       this.bitsPerValue = bitsPerValue;
       this.valueCount = valueCount;
     }
 
     @Override
+    public long next() throws IOException {
+      LongsRef nextValues = next(1);
+      assert nextValues.length > 0;
+      final long result = nextValues.longs[nextValues.offset];
+      ++nextValues.offset;
+      --nextValues.length;
+      return result;
+    }
+
+    @Override
     public int getBitsPerValue() {
       return bitsPerValue;
     }
@@ -168,7 +349,9 @@ public class PackedInts {
 
     @Override
     public void close() throws IOException {
-      in.close();
+      if (in instanceof Closeable) {
+        ((Closeable) in).close();
+      }
     }
   }
 
@@ -217,7 +400,7 @@ public class PackedInts {
    * A simple base for Readers that keeps track of valueCount and bitsPerValue.
    * @lucene.internal
    */
-  public static abstract class ReaderImpl implements Reader {
+  static abstract class ReaderImpl implements Reader {
     protected final int bitsPerValue;
     protected final int valueCount;
 
@@ -257,7 +440,7 @@ public class PackedInts {
 
   }
 
-  public static abstract class MutableImpl extends ReaderImpl implements Mutable {
+  static abstract class MutableImpl extends ReaderImpl implements Mutable {
 
     protected MutableImpl(int valueCount, int bitsPerValue) {
       super(valueCount, bitsPerValue);
@@ -283,13 +466,15 @@ public class PackedInts {
       }
     }
 
-    protected int getFormat() {
-      return PACKED;
+    protected Format getFormat() {
+      return Format.PACKED;
     }
 
     @Override
     public void save(DataOutput out) throws IOException {
-      Writer writer = getWriterByFormat(out, valueCount, bitsPerValue, getFormat());
+      Writer writer = getWriterNoHeader(out, getFormat(),
+          valueCount, bitsPerValue, DEFAULT_BUFFER_SIZE);
+      writer.writeHeader();
       for (int i = 0; i < valueCount; ++i) {
         writer.add(get(i));
       }
@@ -302,121 +487,209 @@ public class PackedInts {
    */
   public static abstract class Writer {
     protected final DataOutput out;
-    protected final int bitsPerValue;
     protected final int valueCount;
+    protected final int bitsPerValue;
 
     protected Writer(DataOutput out, int valueCount, int bitsPerValue)
       throws IOException {
       assert bitsPerValue <= 64;
-
+      assert valueCount >= 0 || valueCount == -1;
       this.out = out;
       this.valueCount = valueCount;
       this.bitsPerValue = bitsPerValue;
+    }
+
+    void writeHeader() throws IOException {
+      assert valueCount != -1;
       CodecUtil.writeHeader(out, CODEC_NAME, VERSION_CURRENT);
       out.writeVInt(bitsPerValue);
       out.writeVInt(valueCount);
-      out.writeVInt(getFormat());
+      out.writeVInt(getFormat().getId());
     }
 
-    protected abstract int getFormat();
+    /** The format used to serialize values. */
+    protected abstract PackedInts.Format getFormat();
+
+    /** Add a value to the stream. */
     public abstract void add(long v) throws IOException;
+
+    /** The number of bits per value. */
+    public final int bitsPerValue() {
+      return bitsPerValue;
+    }
+
+    /** Perform end-of-stream operations. */
     public abstract void finish() throws IOException;
+
+    /**
+     * Returns the current ord in the stream (number of values that have been
+     * written so far minus one).
+     */
+    public abstract int ord();
   }
 
   /**
-   * Retrieve PackedInt data from the DataInput and return a packed int
-   * structure based on it.
+   * Expert: Restore a {@link Reader} from a stream without reading metadata at
+   * the beginning of the stream. This method is useful to restore data from
+   * streams which have been created using
+   * {@link PackedInts#getWriterNoHeader(DataOutput, Format, int, int, int)}.
    *
-   * @param in positioned at the beginning of a stored packed int structure.
-   * @return a read only random access capable array of positive integers.
-   * @throws IOException if the structure could not be retrieved.
+   * @param in           the stream to read data from, positioned at the beginning of the packed values
+   * @param format       the format used to serialize
+   * @param version      the version used to serialize the data
+   * @param valueCount   how many values the stream holds
+   * @param bitsPerValue the number of bits per value
+   * @return             a Reader
+   * @throws IOException
+   * @see PackedInts#getWriterNoHeader(DataOutput, Format, int, int, int)
    * @lucene.internal
    */
-  public static Reader getReader(DataInput in) throws IOException {
-    CodecUtil.checkHeader(in, CODEC_NAME, VERSION_START, VERSION_START);
-    final int bitsPerValue = in.readVInt();
-    assert bitsPerValue > 0 && bitsPerValue <= 64: "bitsPerValue=" + bitsPerValue;
-    final int valueCount = in.readVInt();
-    final int format = in.readVInt();
-
+  public static Reader getReaderNoHeader(DataInput in, Format format, int version,
+      int valueCount, int bitsPerValue) throws IOException {
     switch (format) {
+      case PACKED_SINGLE_BLOCK:
+        return Packed64SingleBlock.create(in, valueCount, bitsPerValue);
       case PACKED:
         switch (bitsPerValue) {
           case 8:
             return new Direct8(in, valueCount);
           case 16:
             return new Direct16(in, valueCount);
-          case 24:
-            return new Packed8ThreeBlocks(in, valueCount);
           case 32:
             return new Direct32(in, valueCount);
-          case 48:
-            return new Packed16ThreeBlocks(in, valueCount);
           case 64:
             return new Direct64(in, valueCount);
-          default:
-            return new Packed64(in, valueCount, bitsPerValue);
+          case 24:
+            if (valueCount <= Packed8ThreeBlocks.MAX_SIZE) {
+              return new Packed8ThreeBlocks(in, valueCount);
+            }
+            break;
+          case 48:
+            if (valueCount <= Packed16ThreeBlocks.MAX_SIZE) {
+              return new Packed16ThreeBlocks(in, valueCount);
+            }
+            break;
         }
-      case PACKED_SINGLE_BLOCK:
-        return Packed64SingleBlock.create(in, valueCount, bitsPerValue);
+        return new Packed64(in, valueCount, bitsPerValue);
       default:
         throw new AssertionError("Unknwown Writer format: " + format);
     }
   }
 
   /**
+   * Restore a {@link Reader} from a stream.
+   *
+   * @param in           the stream to read data from
+   * @return             a Reader
+   * @throws IOException
+   * @lucene.internal
+   */
+  public static Reader getReader(DataInput in) throws IOException {
+    final int version = CodecUtil.checkHeader(in, CODEC_NAME, VERSION_START, VERSION_CURRENT);
+    final int bitsPerValue = in.readVInt();
+    assert bitsPerValue > 0 && bitsPerValue <= 64: "bitsPerValue=" + bitsPerValue;
+    final int valueCount = in.readVInt();
+    final Format format = Format.byId(in.readVInt());
+
+    return getReaderNoHeader(in, format, version, valueCount, bitsPerValue);
+  }
+
+  /**
+   * Expert: Restore a {@link ReaderIterator} from a stream without reading
+   * metadata at the beginning of the stream. This method is useful to restore
+   * data from streams which have been created using
+   * {@link PackedInts#getWriterNoHeader(DataOutput, Format, int, int, int)}.
+   *
+   * @param in           the stream to read data from, positioned at the beginning of the packed values
+   * @param format       the format used to serialize
+   * @param version      the version used to serialize the data
+   * @param valueCount   how many values the stream holds
+   * @param bitsPerValue the number of bits per value
+   * @param mem          how much memory the iterator is allowed to use to read-ahead (likely to speed up iteration)
+   * @return             a ReaderIterator
+   * @throws IOException
+   * @see PackedInts#getWriterNoHeader(DataOutput, Format, int, int, int)
+   * @lucene.internal
+   */
+  public static ReaderIterator getReaderIteratorNoHeader(DataInput in, Format format, int version,
+      int valueCount, int bitsPerValue, int mem) throws IOException {
+    return new PackedReaderIterator(format, valueCount, bitsPerValue, in, mem);
+  }
+
+  /**
    * Retrieve PackedInts as a {@link ReaderIterator}
    * @param in positioned at the beginning of a stored packed int structure.
+   * @param mem how much memory the iterator is allowed to use to read-ahead (likely to speed up iteration)
    * @return an iterator to access the values
    * @throws IOException if the structure could not be retrieved.
    * @lucene.internal
    */
-  public static ReaderIterator getReaderIterator(IndexInput in) throws IOException {
-    CodecUtil.checkHeader(in, CODEC_NAME, VERSION_START, VERSION_START);
+  public static ReaderIterator getReaderIterator(DataInput in, int mem) throws IOException {
+    final int version = CodecUtil.checkHeader(in, CODEC_NAME, VERSION_START, VERSION_CURRENT);
     final int bitsPerValue = in.readVInt();
     assert bitsPerValue > 0 && bitsPerValue <= 64: "bitsPerValue=" + bitsPerValue;
     final int valueCount = in.readVInt();
-    final int format = in.readVInt();
+    final Format format = Format.byId(in.readVInt());
+    return getReaderIteratorNoHeader(in, format, version, valueCount, bitsPerValue, mem);
+  }
+
+  /**
+   * Expert: Construct a direct {@link Reader} from a stream without reading
+   * metadata at the beginning of the stream. This method is useful to restore
+   * data from streams which have been created using
+   * {@link PackedInts#getWriterNoHeader(DataOutput, Format, int, int, int)}.
+   * </p><p>
+   * The returned reader will have very little memory overhead, but every call
+   * to {@link Reader#get(int)} is likely to perform a disk seek.
+   *
+   * @param in           the stream to read data from
+   * @param format       the format used to serialize
+   * @param version      the version used to serialize the data
+   * @param valueCount   how many values the stream holds
+   * @param bitsPerValue the number of bits per value
+   * @return a direct Reader
+   * @throws IOException
+   * @lucene.internal
+   */
+  public static Reader getDirectReaderNoHeader(IndexInput in, Format format,
+      int version, int valueCount, int bitsPerValue) throws IOException {
     switch (format) {
       case PACKED:
-        return new PackedReaderIterator(valueCount, bitsPerValue, in);
+        return new DirectPackedReader(bitsPerValue, valueCount, in);
       case PACKED_SINGLE_BLOCK:
-        return new Packed64SingleBlockReaderIterator(valueCount, bitsPerValue, in);
+        return new DirectPacked64SingleBlockReader(bitsPerValue, valueCount, in);
       default:
-        throw new AssertionError("Unknwown Writer format: " + format);
+        throw new AssertionError("Unknwown format: " + format);
     }
   }
-  
+
   /**
-   * Retrieve PackedInts.Reader that does not load values
-   * into RAM but rather accesses all values via the
-   * provided IndexInput.
-   * @param in positioned at the beginning of a stored packed int structure.
-   * @return an Reader to access the values
-   * @throws IOException if the structure could not be retrieved.
+   * Construct a direct {@link Reader} from an {@link IndexInput}. This method
+   * is useful to restore data from streams which have been created using
+   * {@link PackedInts#getWriter(DataOutput, int, int, float)}.
+   * </p><p>
+   * The returned reader will have very little memory overhead, but every call
+   * to {@link Reader#get(int)} is likely to perform a disk seek.
+   *
+   * @param in           the stream to read data from
+   * @return a direct Reader
+   * @throws IOException
    * @lucene.internal
    */
   public static Reader getDirectReader(IndexInput in) throws IOException {
-    CodecUtil.checkHeader(in, CODEC_NAME, VERSION_START, VERSION_START);
+    final int version = CodecUtil.checkHeader(in, CODEC_NAME, VERSION_START, VERSION_CURRENT);
     final int bitsPerValue = in.readVInt();
     assert bitsPerValue > 0 && bitsPerValue <= 64: "bitsPerValue=" + bitsPerValue;
     final int valueCount = in.readVInt();
-    final int format = in.readVInt();
-    switch (format) {
-      case PACKED:
-        return new DirectPackedReader(bitsPerValue, valueCount, in);
-      case PACKED_SINGLE_BLOCK:
-        return new DirectPacked64SingleBlockReader(bitsPerValue, valueCount, in);
-      default:
-        throw new AssertionError("Unknwown Writer format: " + format);
-    }
+    final Format format = Format.byId(in.readVInt());
+    return getDirectReaderNoHeader(in, format, version, valueCount, bitsPerValue);
   }
   
   /**
    * Create a packed integer array with the given amount of values initialized
    * to 0. the valueCount and the bitsPerValue cannot be changed after creation.
    * All Mutables known by this factory are kept fully in RAM.
-   * 
+   * </p><p>
    * Positive values of <code>acceptableOverheadRatio</code> will trade space
    * for speed by selecting a faster but potentially less memory-efficient
    * implementation. An <code>acceptableOverheadRatio</code> of
@@ -429,110 +702,134 @@ public class PackedInts {
    * @param acceptableOverheadRatio an acceptable overhead
    *        ratio per value
    * @return a mutable packed integer array
-   * @throws java.io.IOException if the Mutable could not be created. With the
-   *         current implementations, this never happens, but the method
-   *         signature allows for future persistence-backed Mutables.
    * @lucene.internal
    */
   public static Mutable getMutable(int valueCount,
       int bitsPerValue, float acceptableOverheadRatio) {
-    acceptableOverheadRatio = Math.max(COMPACT, acceptableOverheadRatio);
-    acceptableOverheadRatio = Math.min(FASTEST, acceptableOverheadRatio);
-    float acceptableOverheadPerValue = acceptableOverheadRatio * bitsPerValue; // in bits
-
-    int maxBitsPerValue = bitsPerValue + (int) acceptableOverheadPerValue;
+    assert valueCount >= 0;
 
-    if (bitsPerValue <= 8 && maxBitsPerValue >= 8) {
-      return new Direct8(valueCount);
-    } else if (bitsPerValue <= 16 && maxBitsPerValue >= 16) {
-      return new Direct16(valueCount);
-    } else if (bitsPerValue <= 32 && maxBitsPerValue >= 32) {
-      return new Direct32(valueCount);
-    } else if (bitsPerValue <= 64 && maxBitsPerValue >= 64) {
-      return new Direct64(valueCount);
-    } else if (valueCount <= Packed8ThreeBlocks.MAX_SIZE && bitsPerValue <= 24 && maxBitsPerValue >= 24) {
-      return new Packed8ThreeBlocks(valueCount);
-    } else if (valueCount <= Packed16ThreeBlocks.MAX_SIZE && bitsPerValue <= 48 && maxBitsPerValue >= 48) {
-      return new Packed16ThreeBlocks(valueCount);
-    } else {
-      for (int bpv = bitsPerValue; bpv <= maxBitsPerValue; ++bpv) {
-        if (Packed64SingleBlock.isSupported(bpv)) {
-          float overhead = Packed64SingleBlock.overheadPerValue(bpv);
-          float acceptableOverhead = acceptableOverheadPerValue + bitsPerValue - bpv;
-          if (overhead <= acceptableOverhead) {
-            return Packed64SingleBlock.create(valueCount, bpv);
-          }
+    final FormatAndBits formatAndBits = fastestFormatAndBits(valueCount, bitsPerValue, acceptableOverheadRatio);
+    switch (formatAndBits.format) {
+      case PACKED_SINGLE_BLOCK:
+        return Packed64SingleBlock.create(valueCount, formatAndBits.bitsPerValue);
+      case PACKED:
+        switch (formatAndBits.bitsPerValue) {
+          case 8:
+            return new Direct8(valueCount);
+          case 16:
+            return new Direct16(valueCount);
+          case 32:
+            return new Direct32(valueCount);
+          case 64:
+            return new Direct64(valueCount);
+          case 24:
+            if (valueCount <= Packed8ThreeBlocks.MAX_SIZE) {
+              return new Packed8ThreeBlocks(valueCount);
+            }
+            break;
+          case 48:
+            if (valueCount <= Packed16ThreeBlocks.MAX_SIZE) {
+              return new Packed16ThreeBlocks(valueCount);
+            }
+            break;
         }
-      }
-      return new Packed64(valueCount, bitsPerValue);
+        return new Packed64(valueCount, formatAndBits.bitsPerValue);
+      default:
+        throw new AssertionError();
     }
   }
 
   /**
-   * Create a packed integer array writer for the given number of values at the
-   * given bits/value. Writers append to the given IndexOutput and has very
-   * low memory overhead.
+   * Expert: Create a packed integer array writer for the given output, format,
+   * value count, and number of bits per value.
+   * </p><p>
+   * The resulting stream will be long-aligned. This means that depending on
+   * the format which is used, up to 63 bits will be wasted. An easy way to
+   * make sure that no space is lost is to always use a <code>valueCount</code>
+   * that is a multiple of 64.
+   * </p><p>
+   * This method does not write any metadata to the stream, meaning that it is
+   * your responsibility to store it somewhere else in order to be able to
+   * recover data from the stream later on:
+   * <ul>
+   *   <li><code>format</code> (using {@link Format#getId()}),</li>
+   *   <li><code>valueCount</code>,</li>
+   *   <li><code>bitsPerValue</code>,</li>
+   *   <li>{@link #VERSION_CURRENT}.</li>
+   * </ul>
+   * </p><p>
+   * It is possible to start writing values without knowing how many of them you
+   * are actually going to write. To do this, just pass <code>-1</code> as
+   * <code>valueCount</code>. On the other hand, for any positive value of
+   * <code>valueCount</code>, the returned writer will make sure that you don't
+   * write more values than expected and pad the end of stream with zeros in
+   * case you have written less than <code>valueCount</code> when calling
+   * {@link Writer#finish()}.
+   * </p><p>
+   * The <code>mem</code> parameter lets you control how much memory can be used
+   * to buffer changes in memory before flushing to disk. High values of
+   * <code>mem</code> are likely to improve throughput. On the other hand, if
+   * speed is not that important to you, a value of <code>0</code> will use as
+   * little memory as possible and should already offer reasonable throughput.
    *
-   * Positive values of <code>acceptableOverheadRatio</code> will trade space
+   * @param out          the data output
+   * @param format       the format to use to serialize the values
+   * @param valueCount   the number of values
+   * @param bitsPerValue the number of bits per value
+   * @param mem          how much memory (in bytes) can be used to speed up serialization
+   * @return             a Writer
+   * @throws IOException
+   * @see PackedInts#getReaderIteratorNoHeader(DataInput, Format, int, int, int, int)
+   * @see PackedInts#getReaderNoHeader(DataInput, Format, int, int, int)
+   * @lucene.internal
+   */
+  public static Writer getWriterNoHeader(
+      DataOutput out, Format format, int valueCount, int bitsPerValue, int mem) throws IOException {
+    return new PackedWriter(format, out, valueCount, bitsPerValue, mem);
+  }
+
+  /**
+   * Create a packed integer array writer for the given output, format, value
+   * count, and number of bits per value.
+   * </p><p>
+   * The resulting stream will be long-aligned. This means that depending on
+   * the format which is used under the hoods, up to 63 bits will be wasted.
+   * An easy way to make sure that no space is lost is to always use a
+   * <code>valueCount</code> that is a multiple of 64.
+   * </p><p>
+   * This method writes metadata to the stream, so that the resulting stream is
+   * sufficient to restore a {@link Reader} from it. You don't need to track
+   * <code>valueCount</code> or <code>bitsPerValue</code> by yourself. In case
+   * this is a problem, you should probably look at
+   * {@link #getWriterNoHeader(DataOutput, Format, int, int, int)}.
+   * </p><p>
+   * The <code>acceptableOverheadRatio</code> parameter controls how
+   * readers that will be restored from this stream trade space
    * for speed by selecting a faster but potentially less memory-efficient
    * implementation. An <code>acceptableOverheadRatio</code> of
    * {@link PackedInts#COMPACT} will make sure that the most memory-efficient
    * implementation is selected whereas {@link PackedInts#FASTEST} will make sure
-   * that the fastest implementation is selected.
+   * that the fastest implementation is selected. In case you are only interested
+   * in reading this stream sequentially later on, you should probably use
+   * {@link PackedInts#COMPACT}.
    *
-   * @param out          the destination for the produced bits.
-   * @param valueCount   the number of elements.
-   * @param bitsPerValue the number of bits available for any given value.
+   * @param out          the data output
+   * @param valueCount   the number of values
+   * @param bitsPerValue the number of bits per value
    * @param acceptableOverheadRatio an acceptable overhead ratio per value
-   * @return a Writer ready for receiving values.
-   * @throws IOException if bits could not be written to out.
+   * @return             a Writer
+   * @throws IOException
    * @lucene.internal
    */
   public static Writer getWriter(DataOutput out,
       int valueCount, int bitsPerValue, float acceptableOverheadRatio)
     throws IOException {
-    acceptableOverheadRatio = Math.max(COMPACT, acceptableOverheadRatio);
-    acceptableOverheadRatio = Math.min(FASTEST, acceptableOverheadRatio);
-    float acceptableOverheadPerValue = acceptableOverheadRatio * bitsPerValue; // in bits
-
-    int maxBitsPerValue = bitsPerValue + (int) acceptableOverheadPerValue;
-
-    if (bitsPerValue <= 8 && maxBitsPerValue >= 8) {
-      return getWriterByFormat(out, valueCount, 8, PACKED);
-    } else if (bitsPerValue <= 16 && maxBitsPerValue >= 16) {
-      return getWriterByFormat(out, valueCount, 16, PACKED);
-    } else if (bitsPerValue <= 32 && maxBitsPerValue >= 32) {
-      return getWriterByFormat(out, valueCount, 32, PACKED);
-    } else if (bitsPerValue <= 64 && maxBitsPerValue >= 64) {
-      return getWriterByFormat(out, valueCount, 64, PACKED);
-    } else if (valueCount <= Packed8ThreeBlocks.MAX_SIZE && bitsPerValue <= 24 && maxBitsPerValue >= 24) {
-      return getWriterByFormat(out, valueCount, 24, PACKED);
-    } else if (valueCount <= Packed16ThreeBlocks.MAX_SIZE && bitsPerValue <= 48 && maxBitsPerValue >= 48) {
-      return getWriterByFormat(out, valueCount, 48, PACKED);
-    } else {
-      for (int bpv = bitsPerValue; bpv <= maxBitsPerValue; ++bpv) {
-        if (Packed64SingleBlock.isSupported(bpv)) {
-          float overhead = Packed64SingleBlock.overheadPerValue(bpv);
-          float acceptableOverhead = acceptableOverheadPerValue + bitsPerValue - bpv;
-          if (overhead <= acceptableOverhead) {
-            return getWriterByFormat(out, valueCount, bpv, PACKED_SINGLE_BLOCK);
-          }
-        }
-      }
-      return getWriterByFormat(out, valueCount, bitsPerValue, PACKED);
-    }
-  }
+    assert valueCount >= 0;
 
-  private static Writer getWriterByFormat(DataOutput out,
-      int valueCount, int bitsPerValue, int format) throws IOException {
-    switch (format) {
-      case PACKED:
-        return new PackedWriter(out, valueCount, bitsPerValue);
-      case PACKED_SINGLE_BLOCK:
-        return new Packed64SingleBlockWriter(out, valueCount, bitsPerValue);
-      default:
-        throw new IllegalArgumentException("Unknown format " + format);
-    }
+    final FormatAndBits formatAndBits = fastestFormatAndBits(valueCount, bitsPerValue, acceptableOverheadRatio);
+    final Writer writer = getWriterNoHeader(out, formatAndBits.format, valueCount, formatAndBits.bitsPerValue, DEFAULT_BUFFER_SIZE);
+    writer.writeHeader();
+    return writer;
   }
 
   /** Returns how many bits are required to hold values up

Modified: lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedReaderIterator.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedReaderIterator.java?rev=1363400&r1=1363399&r2=1363400&view=diff
==============================================================================
--- lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedReaderIterator.java (original)
+++ lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedReaderIterator.java Thu Jul 19 15:58:54 2012
@@ -17,77 +17,71 @@ package org.apache.lucene.util.packed;
  * limitations under the License.
  */
 
-import org.apache.lucene.store.IndexInput;
-
+import java.io.EOFException;
 import java.io.IOException;
 
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.util.LongsRef;
+
 final class PackedReaderIterator extends PackedInts.ReaderIteratorImpl {
-  private long pending;
-  private int pendingBitsLeft;
-  private int position = -1;
 
-  // masks[n-1] masks for bottom n bits
-  private final long[] masks;
+  final PackedInts.Format format;
+  final BulkOperation bulkOperation;
+  final long[] nextBlocks;
+  final LongsRef nextValues;
+  final int iterations;
+  int position;
 
-  public PackedReaderIterator(int valueCount, int bitsPerValue, IndexInput in)
-    throws IOException {
+  PackedReaderIterator(PackedInts.Format format, int valueCount, int bitsPerValue, DataInput in, int mem) {
     super(valueCount, bitsPerValue, in);
+    this.format = format;
+    bulkOperation = BulkOperation.of(format, bitsPerValue);
+    iterations = bulkOperation.computeIterations(valueCount, mem);
+    assert iterations > 0;
+    nextBlocks = new long[iterations * bulkOperation.blocks()];
+    nextValues = new LongsRef(new long[iterations * bulkOperation.values()], 0, 0);
+    assert iterations * bulkOperation.values() == nextValues.longs.length;
+    assert iterations * bulkOperation.blocks() == nextBlocks.length;
+    nextValues.offset = nextValues.longs.length;
+    position = -1;
+  }
 
-    masks = new long[bitsPerValue];
+  @Override
+  public LongsRef next(int count) throws IOException {
+    assert nextValues.length >= 0;
+    assert count > 0;
+    assert nextValues.offset + nextValues.length <= nextValues.longs.length;
+    
+    nextValues.offset += nextValues.length;
 
-    long v = 1;
-    for (int i = 0; i < bitsPerValue; i++) {
-      v *= 2;
-      masks[i] = v - 1;
+    final int remaining = valueCount - position - 1;
+    if (remaining <= 0) {
+      throw new EOFException();
     }
-  }
+    count = Math.min(remaining, count);
 
-  public long next() throws IOException {
-    if (pendingBitsLeft == 0) {
-      pending = in.readLong();
-      pendingBitsLeft = 64;
-    }
-    
-    final long result;
-    if (pendingBitsLeft >= bitsPerValue) { // not split
-      result = (pending >> (pendingBitsLeft - bitsPerValue)) & masks[bitsPerValue-1];
-      pendingBitsLeft -= bitsPerValue;
-    } else { // split
-      final int bits1 = bitsPerValue - pendingBitsLeft;
-      final long result1 = (pending & masks[pendingBitsLeft-1]) << bits1;
-      pending = in.readLong();
-      final long result2 = (pending >> (64 - bits1)) & masks[bits1-1];
-      pendingBitsLeft = 64 + pendingBitsLeft - bitsPerValue;
-      result = result1 | result2;
+    if (nextValues.offset == nextValues.longs.length) {
+      final int remainingBlocks = format.nblocks(bitsPerValue, remaining);
+      final int blocksToRead = Math.min(remainingBlocks, nextBlocks.length);
+      for (int i = 0; i < blocksToRead; ++i) {
+        nextBlocks[i] = in.readLong();
+      }
+      for (int i = blocksToRead; i < nextBlocks.length; ++i) {
+        nextBlocks[i] = 0L;
+      }
+
+      bulkOperation.get(nextBlocks, 0, nextValues.longs, 0, iterations);
+      nextValues.offset = 0;
     }
-    
-    ++position;
-    return result;
+
+    nextValues.length = Math.min(nextValues.longs.length - nextValues.offset, count);
+    position += nextValues.length;
+    return nextValues;
   }
 
+  @Override
   public int ord() {
     return position;
   }
 
-  public long advance(final int ord) throws IOException{
-    assert ord < valueCount : "ord must be less than valueCount";
-    assert ord > position : "ord must be greater than the current position";
-    final long bits = (long) bitsPerValue;
-    final int posToSkip = ord - 1 - position;
-    final long bitsToSkip = (bits * (long)posToSkip);
-    if (bitsToSkip < pendingBitsLeft) { // enough bits left - no seek required
-      pendingBitsLeft -= bitsToSkip;
-    } else {
-      final long skip = bitsToSkip-pendingBitsLeft;
-      final long closestByte = (skip >> 6) << 3;
-      if (closestByte != 0) { // need to seek 
-        final long filePointer = in.getFilePointer();
-        in.seek(filePointer + closestByte);
-      }
-      pending = in.readLong();
-      pendingBitsLeft = 64 - (int)(skip % 64);
-    }
-    position = ord-1;
-    return next();
-  }
 }

Modified: lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedWriter.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedWriter.java?rev=1363400&r1=1363399&r2=1363400&view=diff
==============================================================================
--- lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedWriter.java (original)
+++ lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedWriter.java Thu Jul 19 15:58:54 2012
@@ -19,101 +19,79 @@ package org.apache.lucene.util.packed;
 
 import org.apache.lucene.store.DataOutput;
 
+import java.io.EOFException;
 import java.io.IOException;
 
 // Packs high order byte first, to match
 // IndexOutput.writeInt/Long/Short byte order
 
-/**
- * Generic writer for space-optimal packed values. The resulting bits can be
- * used directly by Packed32, Packed64 and PackedDirect* and will always be
- * long-aligned.
- */
-
-class PackedWriter extends PackedInts.Writer {
-  private long pending;
-  private int pendingBitPos;
-
-  // masks[n-1] masks for bottom n bits
-  private final long[] masks;
-  private int written = 0;
+final class PackedWriter extends PackedInts.Writer {
 
-  public PackedWriter(DataOutput out, int valueCount, int bitsPerValue)
-                                                            throws IOException {
-    super(out, valueCount, bitsPerValue);
-
-    pendingBitPos = 64;
-    masks = new long[bitsPerValue - 1];
+  boolean finished;
+  final PackedInts.Format format;
+  final BulkOperation bulkOperation;
+  final long[] nextBlocks;
+  final long[] nextValues;
+  final int iterations;
+  int off;
+  int written;
 
-    long v = 1;
-    for (int i = 0; i < bitsPerValue - 1; i++) {
-      v *= 2;
-      masks[i] = v - 1;
-    }
+  PackedWriter(PackedInts.Format format, DataOutput out, int valueCount, int bitsPerValue, int mem)
+      throws IOException {
+    super(out, valueCount, bitsPerValue);
+    this.format = format;
+    bulkOperation = BulkOperation.of(format, bitsPerValue);
+    iterations = bulkOperation.computeIterations(valueCount, mem);
+    nextBlocks = new long[iterations * bulkOperation.blocks()];
+    nextValues = new long[iterations * bulkOperation.values()];
+    off = 0;
+    written = 0;
+    finished = false;
   }
 
   @Override
-  protected int getFormat() {
-    return PackedInts.PACKED;
+  protected PackedInts.Format getFormat() {
+    return format;
   }
 
-  /**
-   * Do not call this after finish
-   */
   @Override
   public void add(long v) throws IOException {
-    assert v <= PackedInts.maxValue(bitsPerValue) : "v=" + v
-            + " maxValue=" + PackedInts.maxValue(bitsPerValue);
-    assert v >= 0;
-    //System.out.println("    packedw add v=" + v + " pendingBitPos=" + pendingBitPos);
-
-    // TODO
-    if (pendingBitPos >= bitsPerValue) {
-      // not split
-
-      // write-once, so we can |= w/o first masking to 0s
-      pending |= v << (pendingBitPos - bitsPerValue);
-      if (pendingBitPos == bitsPerValue) {
-        // flush
-        out.writeLong(pending);
-        pending = 0;
-        pendingBitPos = 64;
-      } else {
-        pendingBitPos -= bitsPerValue;
-      }
-
-    } else {
-      // split
-
-      // write top pendingBitPos bits of value into bottom bits of pending
-      pending |= (v >> (bitsPerValue - pendingBitPos)) & masks[pendingBitPos - 1];
-      //System.out.println("      part1 (v >> " + (bitsPerValue - pendingBitPos) + ") & " + masks[pendingBitPos-1]);
-
-      // flush
-      out.writeLong(pending);
-
-      // write bottom (bitsPerValue - pendingBitPos) bits of value into top bits of pending
-      pendingBitPos = 64 - bitsPerValue + pendingBitPos;
-      //System.out.println("      part2 v << " + pendingBitPos);
-      pending = (v << pendingBitPos);
+    assert v >= 0 && v <= PackedInts.maxValue(bitsPerValue);
+    assert !finished;
+    if (valueCount != -1 && written >= valueCount) {
+      throw new EOFException("Writing past end of stream");
+    }
+    nextValues[off++] = v;
+    if (off == nextValues.length) {
+      flush(nextValues.length);
+      off = 0;
     }
-    written++;
+    ++written;
   }
 
   @Override
   public void finish() throws IOException {
-    while (written < valueCount) {
-      add(0L); // Auto flush
+    assert !finished;
+    if (valueCount != -1) {
+      while (written < valueCount) {
+        add(0L);
+      }
     }
+    flush(off);
+    finished = true;
+  }
 
-    if (pendingBitPos != 64) {
-      out.writeLong(pending);
+  private void flush(int nvalues) throws IOException {
+    bulkOperation.set(nextBlocks, 0, nextValues, 0, iterations);
+    final int blocks = format.nblocks(bitsPerValue, nvalues);
+    for (int i = 0; i < blocks; ++i) {
+      out.writeLong(nextBlocks[i]);
     }
+    off = 0;
   }
 
   @Override
-  public String toString() {
-    return "PackedWriter(written " + written + "/" + valueCount + " with "
-            + bitsPerValue + " bits/value)";
+  public int ord() {
+    return written - 1;
   }
 }

Modified: lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/package.html
URL: http://svn.apache.org/viewvc/lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/package.html?rev=1363400&r1=1363399&r2=1363400&view=diff
==============================================================================
--- lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/package.html (original)
+++ lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/package.html Thu Jul 19 15:58:54 2012
@@ -19,9 +19,16 @@
 <head></head>
 <body bgcolor="white">
 
+<p>Packed integer arrays and streams.</p>
+
 <p>
-    The packed package provides random access capable arrays of positive longs.
-    The implementations provides different trade offs between memory usage and
+    The packed package provides
+    <ul>
+    	<li>sequential and random access capable arrays of positive longs,</li>
+    	<li>routines for efficient serialization and deserialization of streams of packed integers.</li>
+    </ul>
+
+    The implementations provide different trade-offs between memory usage and
     access speed. The standard usage scenario is replacing large int or long
     arrays in order to reduce the memory footprint.
 </p><p>