lucene-java-3.5.0/lucene/src/java/org/apache/lucene/util/packed/Packed32.java

   1 package org.apache.lucene.util.packed;
   2
   3 /**
   4  * Licensed to the Apache Software Foundation (ASF) under one or more
   5  * contributor license agreements.  See the NOTICE file distributed with
   6  * this work for additional information regarding copyright ownership.
   7  * The ASF licenses this file to You under the Apache License, Version 2.0
   8  * (the "License"); you may not use this file except in compliance with
   9  * the License.  You may obtain a copy of the License at
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 import org.apache.lucene.store.DataInput;
  21 import org.apache.lucene.util.RamUsageEstimator;
  22
  23 import java.io.IOException;
  24 import java.util.Arrays;
  25
  26 /**
  27  * Space optimized random access capable array of values with a fixed number of
  28  * bits. The maximum number of bits/value is 31. Use {@link Packed64} for higher
  29  * numbers.
  30  * </p><p>
  31  * The implementation strives to avoid conditionals and expensive operations,
  32  * sacrificing code clarity to achieve better performance.
  33  */
  34
  35 class Packed32 extends PackedInts.ReaderImpl implements PackedInts.Mutable {
  36   static final int BLOCK_SIZE = 32; // 32 = int, 64 = long
  37   static final int BLOCK_BITS = 5; // The #bits representing BLOCK_SIZE
  38   static final int MOD_MASK = BLOCK_SIZE - 1; // x % BLOCK_SIZE
  39
  40   private static final int ENTRY_SIZE = BLOCK_SIZE + 1;
  41   private static final int FAC_BITPOS = 3;
  42
  43   /*
  44    * In order to make an efficient value-getter, conditionals should be
  45    * avoided. A value can be positioned inside of a block, requiring shifting
  46    * left or right or it can span two blocks, requiring a left-shift on the
  47    * first block and a right-shift on the right block.
  48    * </p><p>
  49    * By always shifting the first block both left and right, we get exactly
  50    * the right bits. By always shifting the second block right and applying
  51    * a mask, we get the right bits there. After that, we | the two bitsets.
  52   */
  53   private static final int[][] SHIFTS =
  54           new int[ENTRY_SIZE][ENTRY_SIZE * FAC_BITPOS];
  55   private static final int[][] MASKS = new int[ENTRY_SIZE][ENTRY_SIZE];
  56
  57   static { // Generate shifts
  58     for (int elementBits = 1 ; elementBits <= BLOCK_SIZE ; elementBits++) {
  59       for (int bitPos = 0 ; bitPos < BLOCK_SIZE ; bitPos++) {
  60         int[] currentShifts = SHIFTS[elementBits];
  61         int base = bitPos * FAC_BITPOS;
  62         currentShifts[base    ] = bitPos;
  63         currentShifts[base + 1] = BLOCK_SIZE - elementBits;
  64         if (bitPos <= BLOCK_SIZE - elementBits) { // Single block
  65           currentShifts[base + 2] = 0;
  66           MASKS[elementBits][bitPos] = 0;
  67         } else { // Two blocks
  68           int rBits = elementBits - (BLOCK_SIZE - bitPos);
  69           currentShifts[base + 2] = BLOCK_SIZE - rBits;
  70           MASKS[elementBits][bitPos] = ~(~0 << rBits);
  71         }
  72       }
  73     }
  74   }
  75
  76   /*
  77    * The setter requires more masking than the getter.
  78   */
  79   private static final int[][] WRITE_MASKS =
  80           new int[ENTRY_SIZE][ENTRY_SIZE * FAC_BITPOS];
  81   static {
  82     for (int elementBits = 1 ; elementBits <= BLOCK_SIZE ; elementBits++) {
  83       int elementPosMask = ~(~0 << elementBits);
  84       int[] currentShifts = SHIFTS[elementBits];
  85       int[] currentMasks = WRITE_MASKS[elementBits];
  86       for (int bitPos = 0 ; bitPos < BLOCK_SIZE ; bitPos++) {
  87         int base = bitPos * FAC_BITPOS;
  88         currentMasks[base  ] =~((elementPosMask
  89                 << currentShifts[base + 1])
  90                 >>> currentShifts[base]);
  91         if (bitPos <= BLOCK_SIZE - elementBits) { // Second block not used
  92           currentMasks[base+1] = ~0; // Keep all bits
  93           currentMasks[base+2] = 0;  // Or with 0
  94         } else {
  95           currentMasks[base+1] = ~(elementPosMask
  96                                    << currentShifts[base + 2]);
  97           currentMasks[base+2] = currentShifts[base + 2] == 0 ? 0 : ~0;
  98         }
  99       }
 100     }
 101   }
 102
 103   /* The bits */
 104   private int[] blocks;
 105
 106   // Cached calculations
 107   private int maxPos;      // blocks.length * BLOCK_SIZE / bitsPerValue - 1
 108   private int[] shifts;    // The shifts for the current bitsPerValue
 109   private int[] readMasks;
 110   private int[] writeMasks;
 111
 112   /**
 113    * Creates an array with the internal structures adjusted for the given
 114    * limits and initialized to 0.
 115    * @param valueCount   the number of elements.
 116    * @param bitsPerValue the number of bits available for any given value.
 117    *        Note: bitsPerValue >32 is not supported by this implementation.
 118    */
 119   public Packed32(int valueCount, int bitsPerValue) {
 120     this(new int[(int)(((long)valueCount) * bitsPerValue / BLOCK_SIZE + 2)],
 121             valueCount, bitsPerValue);
 122   }
 123
 124   /**
 125    * Creates an array with content retrieved from the given DataInput.
 126    * @param in       a DataInput, positioned at the start of Packed64-content.
 127    * @param valueCount  the number of elements.
 128    * @param bitsPerValue the number of bits available for any given value.
 129    * @throws java.io.IOException if the values for the backing array could not
 130    *                             be retrieved.
 131    */
 132   public Packed32(DataInput in, int valueCount, int bitsPerValue)
 133                                                             throws IOException {
 134     super(valueCount, bitsPerValue);
 135     int size = size(bitsPerValue, valueCount);
 136     blocks = new int[size + 1]; // +1 due to non-conditional tricks
 137     // TODO: find a faster way to bulk-read ints...
 138     for(int i = 0 ; i < size ; i++) {
 139       blocks[i] = in.readInt();
 140     }
 141     if (size % 2 == 1) {
 142       in.readInt(); // Align to long
 143     }
 144     updateCached();
 145   }
 146
 147   private static int size(int bitsPerValue, int valueCount) {
 148     final long totBitCount = (long) valueCount * bitsPerValue;
 149     return (int) (totBitCount/32 + ((totBitCount % 32 == 0 ) ? 0:1));
 150   }
 151
 152
 153   /**
 154    * Creates an array backed by the given blocks.
 155    * </p><p>
 156    * Note: The blocks are used directly, so changes to the given block will
 157    * affect the Packed32-structure.
 158    * @param blocks   used as the internal backing array.
 159    * @param valueCount   the number of values.
 160    * @param bitsPerValue the number of bits available for any given value.
 161    *        Note: bitsPerValue >32 is not supported by this implementation.
 162    */
 163   public Packed32(int[] blocks, int valueCount, int bitsPerValue) {
 164     // TODO: Check that blocks.length is sufficient for holding length values
 165     super(valueCount, bitsPerValue);
 166     if (bitsPerValue > 31) {
 167       throw new IllegalArgumentException(String.format(
 168               "This array only supports values of 31 bits or less. The "
 169                       + "required number of bits was %d. The Packed64 "
 170                       + "implementation allows values with more than 31 bits",
 171               bitsPerValue));
 172     }
 173     this.blocks = blocks;
 174     updateCached();
 175   }
 176
 177   private void updateCached() {
 178     readMasks = MASKS[bitsPerValue];
 179     maxPos = (int)((((long)blocks.length) * BLOCK_SIZE / bitsPerValue) - 2);
 180     shifts = SHIFTS[bitsPerValue];
 181     writeMasks = WRITE_MASKS[bitsPerValue];
 182   }
 183
 184   /**
 185    * @param index the position of the value.
 186    * @return the value at the given index.
 187    */
 188   public long get(final int index) {
 189     final long majorBitPos = (long)index * bitsPerValue;
 190     final int elementPos = (int)(majorBitPos >>> BLOCK_BITS); // / BLOCK_SIZE
 191     final int bitPos =     (int)(majorBitPos & MOD_MASK); // % BLOCK_SIZE);
 192
 193     final int base = bitPos * FAC_BITPOS;
 194
 195     return ((blocks[elementPos] << shifts[base]) >>> shifts[base+1]) |
 196             ((blocks[elementPos+1] >>> shifts[base+2]) & readMasks[bitPos]);
 197   }
 198
 199   public void set(final int index, final long value) {
 200     final int intValue = (int)value;
 201     final long majorBitPos = (long)index * bitsPerValue;
 202     final int elementPos = (int)(majorBitPos >>> BLOCK_BITS); // / BLOCK_SIZE
 203     final int bitPos =     (int)(majorBitPos & MOD_MASK); // % BLOCK_SIZE);
 204     final int base = bitPos * FAC_BITPOS;
 205
 206     blocks[elementPos  ] = (blocks[elementPos  ] & writeMasks[base])
 207             | (intValue << shifts[base + 1] >>> shifts[base]);
 208     blocks[elementPos+1] = (blocks[elementPos+1] & writeMasks[base+1])
 209             | ((intValue << shifts[base + 2])
 210             & writeMasks[base+2]);
 211   }
 212
 213   public void clear() {
 214     Arrays.fill(blocks, 0);
 215   }
 216
 217   @Override
 218   public String toString() {
 219     return "Packed32(bitsPerValue=" + bitsPerValue + ", maxPos=" + maxPos
 220             + ", elements.length=" + blocks.length + ")";
 221   }
 222
 223   public long ramBytesUsed() {
 224     return RamUsageEstimator.NUM_BYTES_ARRAY_HEADER
 225             + blocks.length * RamUsageEstimator.NUM_BYTES_INT;
 226   }
 227 }