long[] values = {10, 4, 9, 16, 132};

public enum Format {
  // 所有的值都是連續(xù)存儲(chǔ)在一起的，允許一個(gè)value編碼結(jié)果跨越多個(gè)block
  PACKED(0) {
	// 忽略不相關(guān)的代碼
  },
  @Deprecated  
  // 一個(gè)value一個(gè)block  
  PACKED_SINGLE_BLOCK(1) {
    // 忽略不相關(guān)的代碼
  };
  // 忽略不相關(guān)的代碼  
}

// acceptableOverheadRatio：允許編碼結(jié)果浪費(fèi)的內(nèi)存比率
public static FormatAndBits fastestFormatAndBits(
    int valueCount, int bitsPerValue, float acceptableOverheadRatio) {
  if (valueCount == -1) { // 如果不清楚要編碼的數(shù)據(jù)量，就把valueCount設(shè)為-1，會(huì)按最大的數(shù)量來(lái)估計(jì)
    valueCount = Integer.MAX_VALUE;
  }
  // acceptableOverheadRatio不能小于COMPACT
  acceptableOverheadRatio = Math.max(COMPACT, acceptableOverheadRatio);
  // acceptableOverheadRatio不能超過(guò)FASTEST
  acceptableOverheadRatio = Math.min(FASTEST, acceptableOverheadRatio);
  // 每個(gè)value可以允許浪費(fèi)的比例  
  float acceptableOverheadPerValue = acceptableOverheadRatio * bitsPerValue; 
  // 每個(gè)value最大可能使用的bit數(shù)  
  int maxBitsPerValue = bitsPerValue + (int) acceptableOverheadPerValue;
  int actualBitsPerValue = -1;
  // block一般是int或者是long，所以8,16,32,64的編碼速度是比較快的
  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 {
    actualBitsPerValue = bitsPerValue;
  }
  // 強(qiáng)制使用Format.PACKED，已經(jīng)不使用PACKED_SINGLE_BLOCK了
  return new FormatAndBits(Format.PACKED, actualBitsPerValue);
}

public static Encoder getEncoder(Format format, int version, int bitsPerValue) {
  checkVersion(version);
  return BulkOperation.of(format, bitsPerValue);
}

public static BulkOperation of(PackedInts.Format format, int bitsPerValue) {
  switch (format) {
    case PACKED:
      assert packedBulkOps[bitsPerValue - 1] != null;
      return packedBulkOps[bitsPerValue - 1];
    case PACKED_SINGLE_BLOCK: // 棄用，不用看了
      assert packedSingleBlockBulkOps[bitsPerValue - 1] != null;
      return packedSingleBlockBulkOps[bitsPerValue - 1];
    default:
      throw new AssertionError();
  }
}

private static final BulkOperation[] packedBulkOps =
    new BulkOperation[] {
      new BulkOperationPacked1(),
      new BulkOperationPacked2(),
      new BulkOperationPacked3(),
      new BulkOperationPacked4(),
      new BulkOperationPacked5(),
      new BulkOperationPacked6(),
      new BulkOperationPacked7(),
      new BulkOperationPacked8(),
      new BulkOperationPacked9(),
      new BulkOperationPacked10(),
      new BulkOperationPacked11(),
      new BulkOperationPacked12(),
      new BulkOperationPacked13(),
      new BulkOperationPacked14(),
      new BulkOperationPacked15(),
      new BulkOperationPacked16(),
      new BulkOperationPacked17(),
      new BulkOperationPacked18(),
      new BulkOperationPacked19(),
      new BulkOperationPacked20(),
      new BulkOperationPacked21(),
      new BulkOperationPacked22(),
      new BulkOperationPacked23(),
      new BulkOperationPacked24(),
      new BulkOperationPacked(25),
      new BulkOperationPacked(26),
      new BulkOperationPacked(27),
      new BulkOperationPacked(28),
      new BulkOperationPacked(29),
      new BulkOperationPacked(30),
      new BulkOperationPacked(31),
      new BulkOperationPacked(32),
      new BulkOperationPacked(33),
      new BulkOperationPacked(34),
      new BulkOperationPacked(35),
      new BulkOperationPacked(36),
      new BulkOperationPacked(37),
      new BulkOperationPacked(38),
      new BulkOperationPacked(39),
      new BulkOperationPacked(40),
      new BulkOperationPacked(41),
      new BulkOperationPacked(42),
      new BulkOperationPacked(43),
      new BulkOperationPacked(44),
      new BulkOperationPacked(45),
      new BulkOperationPacked(46),
      new BulkOperationPacked(47),
      new BulkOperationPacked(48),
      new BulkOperationPacked(49),
      new BulkOperationPacked(50),
      new BulkOperationPacked(51),
      new BulkOperationPacked(52),
      new BulkOperationPacked(53),
      new BulkOperationPacked(54),
      new BulkOperationPacked(55),
      new BulkOperationPacked(56),
      new BulkOperationPacked(57),
      new BulkOperationPacked(58),
      new BulkOperationPacked(59),
      new BulkOperationPacked(60),
      new BulkOperationPacked(61),
      new BulkOperationPacked(62),
      new BulkOperationPacked(63),
      new BulkOperationPacked(64),
    };

// ramBudget限制在編碼過(guò)程中使用的內(nèi)存上限，單位是字節(jié)
public final int computeIterations(int valueCount, int ramBudget) {
  // byteBlockCount()：一個(gè)iteration需要幾個(gè)byte存儲(chǔ)編碼后的結(jié)果
  // byteValueCount(): 一個(gè)iteration需要幾個(gè)byte存儲(chǔ)待編碼的value個(gè)數(shù)，value是都按long類型處理
  // 這里先算出來(lái)ramBudget可以支撐的最大的iteration，并沒(méi)有考慮實(shí)際的valueCount，后面再調(diào)整
  final int iterations = ramBudget / (byteBlockCount() + 8 * byteValueCount());
  if (iterations == 0) { // 至少是1
    return 1;
  } else if ((iterations - 1) * byteValueCount() >= valueCount) { // 如果不需要那么多的迭代次數(shù)
    // 根據(jù)真實(shí)的valueCount計(jì)算合適的iteration  
    return (int) Math.ceil((double) valueCount / byteValueCount()); 
  } else {
    return iterations;
  }
}

private final int bitsPerValue;
// 當(dāng)block是long的時(shí)候，一個(gè)iteration最少會(huì)使用幾個(gè)block
private final int longBlockCount;
// 一個(gè)iteration中，使用longBlockCount個(gè)block可以編碼的value數(shù)量
private final int longValueCount;
// 當(dāng)block是byte的時(shí)候，一個(gè)iteration最少會(huì)使用幾個(gè)block
private final int byteBlockCount;
// 一個(gè)iteration中，使用byteBlockCount個(gè)block可以編碼的value數(shù)量
private final int byteValueCount;
// 用來(lái)獲取value中有效位的掩碼
private final long mask;
// mask的int格式
private final int intMask;

  public BulkOperationPacked(int bitsPerValue) {
    this.bitsPerValue = bitsPerValue;
    assert bitsPerValue > 0 && bitsPerValue <= 64;
    int blocks = bitsPerValue;
    while ((blocks & 1) == 0) { // 如果是2的倍數(shù)則除以2，直到不是2的倍數(shù)
      blocks >>>= 1;
    }
    // 一次迭代用幾個(gè)long  
    this.longBlockCount = blocks;
    // 一次迭代可以處理幾個(gè)value  
    this.longValueCount = 64 * longBlockCount / bitsPerValue;
    // 一次迭代用幾個(gè)byte  
    int byteBlockCount = 8 * longBlockCount;
    // 一次迭代用處理幾個(gè)value  
    int byteValueCount = longValueCount;
    while ((byteBlockCount & 1) == 0 && (byteValueCount & 1) == 0) { // 縮小成直到不是2的倍數(shù)
      byteBlockCount >>>= 1;
      byteValueCount >>>= 1;
    }
    this.byteBlockCount = byteBlockCount;
    this.byteValueCount = byteValueCount;
    // 算掩碼  
    if (bitsPerValue == 64) {
      this.mask = ~0L;
    } else {
      this.mask = (1L << bitsPerValue) - 1;
    }
    this.intMask = (int) mask;
    assert longValueCount * bitsPerValue == 64 * longBlockCount;
  }

  public void encode(
      long[] values, int valuesOffset, long[] blocks, int blocksOffset, int iterations) {
    // 初始化下一個(gè)block的值  
    long nextBlock = 0;
    // 當(dāng)前block中還剩下多少位可以用來(lái)編碼  
    int bitsLeft = 64;
    // longValueCount * iterations：總共可以處理的數(shù)據(jù)  
    for (int i = 0; i < longValueCount * iterations; ++i) {
      // 當(dāng)前block使用bitsPerValue來(lái)進(jìn)行編碼  
      bitsLeft -= bitsPerValue;
      if (bitsLeft > 0) { // 當(dāng)前block放下當(dāng)前value后還有空間
        // 把當(dāng)前value放到當(dāng)前block中  
        nextBlock |= values[valuesOffset++] << bitsLeft;
      } else if (bitsLeft == 0) { // 剛好可以存放最后一個(gè)數(shù)據(jù)的編碼結(jié)果
        nextBlock |= values[valuesOffset++]; // 最后一個(gè)數(shù)據(jù)的編碼結(jié)果放在nextBlock中
        blocks[blocksOffset++] = nextBlock; // 存儲(chǔ)block
        nextBlock = 0; // 重置block
        bitsLeft = 64; // 重置bitsLeft
      } else { // 需要跨block處理
        nextBlock |= values[valuesOffset] >>> -bitsLeft; // 當(dāng)前block剩下的空間存儲(chǔ)部分value
        blocks[blocksOffset++] = nextBlock; 
        // (1L << -bitsLeft) - 1)：取出value剩余數(shù)據(jù)的掩碼
        // (values[valuesOffset++] & ((1L << -bitsLeft) - 1)): 取出剩余數(shù)據(jù)
        // << (64 + bitsLeft)：放到最前面
        nextBlock = (values[valuesOffset++] & ((1L << -bitsLeft) - 1)) << (64 + bitsLeft);
        // 更新block可用空間  
        bitsLeft += 64;
      }
    }
  }

public void encode(
    int[] values, int valuesOffset, long[] blocks, int blocksOffset, int iterations) {
  long nextBlock = 0;
  int bitsLeft = 64;
  for (int i = 0; i < longValueCount * iterations; ++i) {
    bitsLeft -= bitsPerValue;
    if (bitsLeft > 0) {
      nextBlock |= (values[valuesOffset++] & 0xFFFFFFFFL) << bitsLeft;
    } else if (bitsLeft == 0) {
      nextBlock |= (values[valuesOffset++] & 0xFFFFFFFFL);
      blocks[blocksOffset++] = nextBlock;
      nextBlock = 0;
      bitsLeft = 64;
    } else { // bitsLeft < 0
      nextBlock |= (values[valuesOffset] & 0xFFFFFFFFL) >>> -bitsLeft;
      blocks[blocksOffset++] = nextBlock;
      nextBlock = (values[valuesOffset++] & ((1L << -bitsLeft) - 1)) << (64 + bitsLeft);
      bitsLeft += 64;
    }
  }
}

public void encode(
    long[] values, int valuesOffset, byte[] blocks, int blocksOffset, int iterations) {
  int nextBlock = 0;
  int bitsLeft = 8;
  for (int i = 0; i < byteValueCount * iterations; ++i) {
    final long v = values[valuesOffset++];
    assert PackedInts.unsignedBitsRequired(v) <= bitsPerValue;
    if (bitsPerValue < bitsLeft) { // 如果當(dāng)前block還可以容納value的編碼
      nextBlock |= v << (bitsLeft - bitsPerValue);
      bitsLeft -= bitsPerValue;
    } else {
      // 除了當(dāng)前block可以容納之外，還剩下多少bits
      int bits = bitsPerValue - bitsLeft;
      // 當(dāng)前block剩下的空間把value的高位部分先存  
      blocks[blocksOffset++] = (byte) (nextBlock | (v >>> bits));
      while (bits >= 8) { // 如果還需要處理的bits超過(guò)一個(gè)byte
        bits -= 8;
        blocks[blocksOffset++] = (byte) (v >>> bits);
      }
      // 剩下的bits不足一個(gè)byte
      bitsLeft = 8 - bits;
      //  (v & ((1L << bits) - 1)：取出當(dāng)前value的高bits位
      // 存放在nextBlock的高bits位  
      nextBlock = (int) ((v & ((1L << bits) - 1)) << bitsLeft);
    }
  }
  assert bitsLeft == 8;
}

public void encode(
    int[] values, int valuesOffset, byte[] blocks, int blocksOffset, int iterations) {
  int nextBlock = 0;
  int bitsLeft = 8;
  for (int i = 0; i < byteValueCount * iterations; ++i) {
    final int v = values[valuesOffset++];
    assert PackedInts.bitsRequired(v & 0xFFFFFFFFL) <= bitsPerValue;
    if (bitsPerValue < bitsLeft) {
      nextBlock |= v << (bitsLeft - bitsPerValue);
      bitsLeft -= bitsPerValue;
    } else {
      int bits = bitsPerValue - bitsLeft;
      blocks[blocksOffset++] = (byte) (nextBlock | (v >>> bits));
      while (bits >= 8) {
        bits -= 8;
        blocks[blocksOffset++] = (byte) (v >>> bits);
      }
      bitsLeft = 8 - bits;
      nextBlock = (v & ((1 << bits) - 1)) << bitsLeft;
    }
  }
  assert bitsLeft == 8;
}

public void decode(
    long[] blocks, int blocksOffset, long[] values, int valuesOffset, int iterations) {
  // 當(dāng)前block中還剩多少位未解碼  
  int bitsLeft = 64;
  for (int i = 0; i < longValueCount * iterations; ++i) {
    bitsLeft -= bitsPerValue;
    if (bitsLeft < 0) { // 跨block的解碼
      values[valuesOffset++] =
          ((blocks[blocksOffset++] & ((1L << (bitsPerValue + bitsLeft)) - 1)) << -bitsLeft)
              | (blocks[blocksOffset] >>> (64 + bitsLeft));
      bitsLeft += 64;
    } else {
      values[valuesOffset++] = (blocks[blocksOffset] >>> bitsLeft) & mask;
    }
  }
}

public void decode(
    long[] blocks, int blocksOffset, int[] values, int valuesOffset, int iterations) {
  if (bitsPerValue > 32) {
    throw new UnsupportedOperationException(
        "Cannot decode " + bitsPerValue + "-bits values into an int[]");
  }
  int bitsLeft = 64;
  for (int i = 0; i < longValueCount * iterations; ++i) {
    bitsLeft -= bitsPerValue;
    if (bitsLeft < 0) {
      values[valuesOffset++] =
          (int)
              (((blocks[blocksOffset++] & ((1L << (bitsPerValue + bitsLeft)) - 1)) << -bitsLeft)
                  | (blocks[blocksOffset] >>> (64 + bitsLeft)));
      bitsLeft += 64;
    } else {
      values[valuesOffset++] = (int) ((blocks[blocksOffset] >>> bitsLeft) & mask);
    }
  }
}

public void decode(
    byte[] blocks, int blocksOffset, long[] values, int valuesOffset, int iterations) {
  long nextValue = 0L;
  int bitsLeft = bitsPerValue;
  for (int i = 0; i < iterations * byteBlockCount; ++i) {
    final long bytes = blocks[blocksOffset++] & 0xFFL;
    if (bitsLeft > 8) {
      bitsLeft -= 8;
      nextValue |= bytes << bitsLeft;
    } else {
      int bits = 8 - bitsLeft;
      values[valuesOffset++] = nextValue | (bytes >>> bits);
      while (bits >= bitsPerValue) {
        bits -= bitsPerValue;
        values[valuesOffset++] = (bytes >>> bits) & mask;
      }
      bitsLeft = bitsPerValue - bits;
      nextValue = (bytes & ((1L << bits) - 1)) << bitsLeft;
    }
  }
  assert bitsLeft == bitsPerValue;
}

public void decode(
    byte[] blocks, int blocksOffset, int[] values, int valuesOffset, int iterations) {
  int nextValue = 0;
  int bitsLeft = bitsPerValue;
  for (int i = 0; i < iterations * byteBlockCount; ++i) {
    final int bytes = blocks[blocksOffset++] & 0xFF;
    if (bitsLeft > 8) {
      bitsLeft -= 8;
      nextValue |= bytes << bitsLeft;
    } else {
      int bits = 8 - bitsLeft;
      values[valuesOffset++] = nextValue | (bytes >>> bits);
      while (bits >= bitsPerValue) {
        bits -= bitsPerValue;
        values[valuesOffset++] = (bytes >>> bits) & intMask;
      }
      bitsLeft = bitsPerValue - bits;
      nextValue = (bytes & ((1 << bits) - 1)) << bitsLeft;
    }
  }
  assert bitsLeft == bitsPerValue;
}

final class BulkOperationPacked2 extends BulkOperationPacked {
  public BulkOperationPacked2() {
    super(2);
  }
  @Override
  public void decode(
      long[] blocks, int blocksOffset, int[] values, int valuesOffset, int iterations) {
    for (int i = 0; i < iterations; ++i) {
      // 只會(huì)用到一個(gè)block  
      final long block = blocks[blocksOffset++];
      // 需要解析出32個(gè)value   
      for (int shift = 62; shift >= 0; shift -= 2) {
        values[valuesOffset++] = (int) ((block >>> shift) & 3);
      }
    }
  }
  @Override
  public void decode(
      byte[] blocks, int blocksOffset, int[] values, int valuesOffset, int iterations) {
    for (int j = 0; j < iterations; ++j) {
      // 只會(huì)用到一個(gè)block  
      final byte block = blocks[blocksOffset++];
      // 需要解析出4個(gè)value  
      values[valuesOffset++] = (block >>> 6) & 3;
      values[valuesOffset++] = (block >>> 4) & 3;
      values[valuesOffset++] = (block >>> 2) & 3;
      values[valuesOffset++] = block & 3;
    }
  }
  @Override
  public void decode(
      long[] blocks, int blocksOffset, long[] values, int valuesOffset, int iterations) {
    for (int i = 0; i < iterations; ++i) {
      // 只會(huì)用到一個(gè)block  
      final long block = blocks[blocksOffset++];
      // 需要解析出32個(gè)value   
      for (int shift = 62; shift >= 0; shift -= 2) {
        values[valuesOffset++] = (block >>> shift) & 3;
      }
    }
  }
  @Override
  public void decode(
      byte[] blocks, int blocksOffset, long[] values, int valuesOffset, int iterations) {
    for (int j = 0; j < iterations; ++j) {
      // 只會(huì)用到一個(gè)block 
      final byte block = blocks[blocksOffset++];
      // 需要解析出4個(gè)value  
      values[valuesOffset++] = (block >>> 6) & 3;
      values[valuesOffset++] = (block >>> 4) & 3;
      values[valuesOffset++] = (block >>> 2) & 3;
      values[valuesOffset++] = block & 3;
    }
  }
}

final class PackedWriter extends PackedInts.Writer {
  // 是否構(gòu)建結(jié)束
  boolean finished;
  // 9.0.0之后的版本都是Packed
  final PackedInts.Format format;
  // 根據(jù)format和bitsPerValue決定encoder  
  final BulkOperation encoder;
  // 編碼結(jié)果的buffer  
  final byte[] nextBlocks;
  // 待編碼的value的buffer  
  final long[] nextValues;
  // 通過(guò)編碼器計(jì)算得到的iterations  
  final int iterations;
  // nextValues可以寫入的位置 
  int off;
  // 已處理的value的個(gè)數(shù)  
  int written;
  PackedWriter(
      PackedInts.Format format, DataOutput out, int valueCount, int bitsPerValue, int mem) {
    super(out, valueCount, bitsPerValue);
    this.format = format;
    encoder = BulkOperation.of(format, bitsPerValue);
    iterations = encoder.computeIterations(valueCount, mem);
    // 創(chuàng)建合適的大小
    nextBlocks = new byte[iterations * encoder.byteBlockCount()];
    nextValues = new long[iterations * encoder.byteValueCount()];
    off = 0;
    written = 0;
    finished = false;
  }
  @Override
  protected PackedInts.Format getFormat() {
    return format;
  }
  @Override
  public void add(long v) throws IOException {
    if (valueCount != -1 && written >= valueCount) {
      throw new EOFException("Writing past end of stream");
    }
    // 把value臨時(shí)存儲(chǔ)到nextValues中，等到編碼  
    nextValues[off++] = v;
    if (off == nextValues.length) { // 如果nextValues滿了，則進(jìn)行編碼
      flush();
    }
    ++written;
  }
  @Override
  public void finish() throws IOException {
    if (valueCount != -1) { // 如果數(shù)據(jù)沒(méi)有達(dá)到預(yù)期的數(shù)量，則補(bǔ)0
      while (written < valueCount) {
        add(0L);
      }
    }
    flush();
    finished = true;
  }
  private void flush() throws IOException {
    // 編碼  
    encoder.encode(nextValues, 0, nextBlocks, 0, iterations);
    // 以byte作為block的單位，一共幾個(gè)byte  
    final int blockCount = (int) format.byteCount(PackedInts.VERSION_CURRENT, off, bitsPerValue);
    // 編碼的結(jié)果持久化  
    out.writeBytes(nextBlocks, blockCount);
    // 清空nextValues  
    Arrays.fill(nextValues, 0L);
    off = 0;
  }
  @Override
  public int ord() {
    return written - 1;
  }
}

abstract class AbstractBlockPackedWriter {
  // 用來(lái)持久化編碼結(jié)果的
  protected DataOutput out;
  // 暫存待編碼的value  
  protected final long[] values;
  // 存儲(chǔ)編碼后的block  
  protected byte[] blocks;
  protected int off;
  // 處理的第幾個(gè)value  
  protected long ord;
  protected boolean finished;
  // blockSize：段大小  
  protected AbstractBlockPackedWriter(DataOutput out, int blockSize) {
    checkBlockSize(blockSize, MIN_BLOCK_SIZE, MAX_BLOCK_SIZE);
    reset(out);
    values = new long[blockSize];
  }
  public void add(long l) throws IOException {
    checkNotFinished();
    if (off == values.length) { // 如果values滿了，也就是已經(jīng)收集到了一段數(shù)據(jù)了，則進(jìn)行編碼
      flush();
    }
    values[off++] = l;
    ++ord;
  }
  public void finish() throws IOException {
    checkNotFinished();
    if (off > 0) { // 如果有數(shù)據(jù)則flush
      flush();
    }
    finished = true;
  }
  // flush中計(jì)算的就是當(dāng)前段的bitsPerValue，由子類實(shí)現(xiàn)  
  protected abstract void flush() throws IOException;
  // 執(zhí)行編碼，在flush中被調(diào)用，bitsRequired是flush中計(jì)算得到的
  protected final void writeValues(int bitsRequired) throws IOException {
    // 每一段都有自己的編碼器 
    final PackedInts.Encoder encoder =
        PackedInts.getEncoder(PackedInts.Format.PACKED, PackedInts.VERSION_CURRENT, bitsRequired);
    final int iterations = values.length / encoder.byteValueCount();
    final int blockSize = encoder.byteBlockCount() * iterations;
    if (blocks == null || blocks.length < blockSize) {
      blocks = new byte[blockSize];
    }
    if (off < values.length) {
      Arrays.fill(values, off, values.length, 0L);
    }
    encoder.encode(values, 0, blocks, 0, iterations);
    final int blockCount =
        (int) PackedInts.Format.PACKED.byteCount(PackedInts.VERSION_CURRENT, off, bitsRequired);
    // 持久化編碼后的數(shù)據(jù)  
    out.writeBytes(blocks, blockCount);
  }
}

public final class BlockPackedWriter extends AbstractBlockPackedWriter {
  public BlockPackedWriter(DataOutput out, int blockSize) {
    super(out, blockSize);
  }
  @Override
  protected void flush() throws IOException {
    long min = Long.MAX_VALUE, max = Long.MIN_VALUE;
    for (int i = 0; i < off; ++i) { // 尋找最大值和最小值
      min = Math.min(values[i], min);
      max = Math.max(values[i], max);
    }
    // 最大值和最小值的差值  
    final long delta = max - min;
    // 差值的bitsRequired，下面會(huì)把所有的value更新為value和min的差值，所以bitsRequired就是更新后的bitsPerValue
    int bitsRequired = delta == 0 ? 0 : PackedInts.unsignedBitsRequired(delta);
    if (bitsRequired == 64) { // 如果最大和最小的差值都需要64bits來(lái)存儲(chǔ)，那就不用去更新value了
      min = 0L;
    } else if (min > 0L) {
      // 讓min盡量小，因?yàn)閙in會(huì)用VLong編碼，這樣盡可能使用更少的字節(jié)  
      min = Math.max(0L, max - PackedInts.maxValue(bitsRequired));
    }
    // bitsRequired左移一位，最后一位是標(biāo)記位，標(biāo)記min是否是0
    final int token = (bitsRequired << BPV_SHIFT) | (min == 0 ? MIN_VALUE_EQUALS_0 : 0);
    out.writeByte((byte) token);
    if (min != 0) { // VLong編碼min
      writeVLong(out, zigZagEncode(min) - 1);
    }
    if (bitsRequired > 0) {
      if (min != 0) {
        for (int i = 0; i < off; ++i) { // 所有的value更新為與最小值的差值
          values[i] -= min;
        }
      }
      // 編碼并持久化  
      writeValues(bitsRequired);
    }
    off = 0;
  }
}

public final class MonotonicBlockPackedWriter extends AbstractBlockPackedWriter {
  public MonotonicBlockPackedWriter(DataOutput out, int blockSize) {
    super(out, blockSize);
  }
  @Override
  protected void flush() throws IOException {
    // 計(jì)算平均步長(zhǎng)
    final float avg = off == 1 ? 0f : (float) (values[off - 1] - values[0]) / (off - 1);
    long min = values[0];
    for (int i = 1; i < off; ++i) { // 計(jì)算出期望的最小值，保證根據(jù)平均步長(zhǎng)計(jì)算每個(gè)位置的期望值都是正數(shù)
      final long actual = values[i];
      // 相同位置的期望value  
      final long expected = expected(min, avg, i);
      if (expected > actual) { // 如果期望值大于實(shí)際值
        // 調(diào)小期望的最小值  
        min -= (expected - actual);
      }
    }
    // 最大差值，用來(lái)計(jì)算bitsPerValue的
    long maxDelta = 0;
    for (int i = 0; i < off; ++i) { // 所有的值都更新為和期望值的差值
      values[i] = values[i] - expected(min, avg, i);
      maxDelta = Math.max(maxDelta, values[i]);
    }
    out.writeZLong(min);
    out.writeInt(Float.floatToIntBits(avg));
    if (maxDelta == 0) { // 所有的值都一樣
      out.writeVInt(0);
    } else {
      final int bitsRequired = PackedInts.bitsRequired(maxDelta);
      out.writeVInt(bitsRequired);
      // 編碼并持久化  
      writeValues(bitsRequired);
    }
    off = 0;
  }
}

public final class DirectWriter {
  // 每個(gè)value使用幾個(gè)bit存儲(chǔ)  
  final int bitsPerValue;
  // 有幾個(gè)需要存儲(chǔ)的value  
  final long numValues;
  // 數(shù)據(jù)存儲(chǔ)的目的地  
  final DataOutput output;
  // 統(tǒng)計(jì)已經(jīng)處理了幾個(gè)數(shù)據(jù)
  long count;
  // 是否已經(jīng)處理完成了
  boolean finished;
  // nextValues的下一個(gè)寫入的位置
  int off;
  // 存儲(chǔ)block  
  final byte[] nextBlocks;
  // 臨時(shí)存儲(chǔ)數(shù)據(jù)，待構(gòu)建成block  
  final long[] nextValues;
  // DirectWriter支持的bitsPerValue參數(shù)列表  
  static final int[] SUPPORTED_BITS_PER_VALUE =
      new int[] {1, 2, 4, 8, 12, 16, 20, 24, 28, 32, 40, 48, 56, 64};
  DirectWriter(DataOutput output, long numValues, int bitsPerValue) {
    this.output = output;
    this.numValues = numValues;
    this.bitsPerValue = bitsPerValue;
    // 可用的內(nèi)存限制，是nextBlocks和nextValues兩個(gè)數(shù)組合起來(lái)的大小限制
    final int memoryBudgetInBits = Math.multiplyExact(Byte.SIZE, PackedInts.DEFAULT_BUFFER_SIZE);
    // nextValues的大小
    int bufferSize = memoryBudgetInBits / (Long.SIZE + bitsPerValue);
    // 把bufferSize調(diào)整成下一個(gè)64的倍數(shù)的值
    bufferSize = Math.toIntExact(bufferSize + 63) & 0xFFFFFFC0;
    nextValues = new long[bufferSize];
    // add 7 bytes in the end so that any value could be written as a long
    nextBlocks = new byte[bufferSize * bitsPerValue / Byte.SIZE + Long.BYTES - 1];
  }
  // 新增一個(gè)value
  public void add(long l) throws IOException {
    // 校驗(yàn)是否超出了一開始設(shè)定的value總數(shù)
    if (count >= numValues) {
      throw new EOFException("Writing past end of stream");
    }
    // 把數(shù)據(jù)暫存在nextValues中  
    nextValues[off++] = l;
    // 如果nextValues滿了，則進(jìn)行flush編碼  
    if (off == nextValues.length) {
      flush();
    }
    // 處理的value數(shù)+1
    count++;
  }
  // 構(gòu)建一個(gè)block  
  private void flush() throws IOException {
    if (off == 0) {
      return;
    }
    // 把off之后的所有位置設(shè)為0
    Arrays.fill(nextValues, off, nextValues.length, 0L);
    // 將nextValues中的數(shù)據(jù)編碼存儲(chǔ)到nextBlocks中  
    encode(nextValues, off, nextBlocks, bitsPerValue);
    // 一共需要幾個(gè)byte存儲(chǔ)所有編碼好的數(shù)據(jù)  
    final int blockCount =
        (int) PackedInts.Format.PACKED.byteCount(PackedInts.VERSION_CURRENT, off, bitsPerValue);
    // 存儲(chǔ)編碼后的數(shù)據(jù)  
    output.writeBytes(nextBlocks, blockCount);
    off = 0;
  }
  private static void encode(long[] nextValues, int upTo, byte[] nextBlocks, int bitsPerValue) {
    if ((bitsPerValue & 7) == 0) {// bitsPerValue的值是8的倍數(shù): 8, 16, 24, 32, 40, 48, 56, 64
      // 一個(gè)value需要幾個(gè)byte  
      final int bytesPerValue = bitsPerValue / Byte.SIZE;
      // i是nextValues中的下標(biāo)  
      // o是在nextBlocks中下一個(gè)寫入的下標(biāo)  
      for (int i = 0, o = 0; i < upTo; ++i, o += bytesPerValue) {
        final long l = nextValues[i];
        if (bitsPerValue > Integer.SIZE) { // 大于32位的都用long存
          BitUtil.VH_LE_LONG.set(nextBlocks, o, l);
        } else if (bitsPerValue > Short.SIZE) { // 24，32都用int存
          BitUtil.VH_LE_INT.set(nextBlocks, o, (int) l);
        } else if (bitsPerValue > Byte.SIZE) { // 16用short存
          BitUtil.VH_LE_SHORT.set(nextBlocks, o, (short) l);
        } else { // 8用byte存
          nextBlocks[o] = (byte) l;
        }
      }
    } else if (bitsPerValue < 8) {// bitsPerValue的值是 1, 2, 4
      // 一個(gè)long可以存幾個(gè)value  
      final int valuesPerLong = Long.SIZE / bitsPerValue;
      // o是在nextBlocks中的下一個(gè)可以寫入的位置  
      for (int i = 0, o = 0; i < upTo; i += valuesPerLong, o += Long.BYTES) {
        long v = 0;
        // 構(gòu)建一個(gè)block，一個(gè)block就是一個(gè)long  
        for (int j = 0; j < valuesPerLong; ++j) {
          v |= nextValues[i + j] << (bitsPerValue * j);
        }
        BitUtil.VH_LE_LONG.set(nextBlocks, o, v);
      }
    } else {// bitsPerValue的值是 12, 20, 28，此時(shí)不是一個(gè)字節(jié)的整數(shù)倍，所以是2個(gè)2個(gè)處理
      // 2個(gè)value需要幾個(gè)字節(jié)  
      final int numBytesFor2Values = bitsPerValue * 2 / Byte.SIZE;
      // o是在nextBlocks中下一個(gè)可以寫入的位置  
      for (int i = 0, o = 0; i < upTo; i += 2, o += numBytesFor2Values) {
        final long l1 = nextValues[i];
        final long l2 = nextValues[i + 1];
        // 2個(gè)合成一個(gè)  
        final long merged = l1 | (l2 << bitsPerValue);
        if (bitsPerValue <= Integer.SIZE / 2) { // 如果bitsPerValue=12，則以int的方式存兩個(gè)value
          BitUtil.VH_LE_INT.set(nextBlocks, o, (int) merged);
        } else { // bitsPerValue=20或者28，則以long的方式存兩個(gè)value
          BitUtil.VH_LE_LONG.set(nextBlocks, o, merged);
        }
      }
    }
  }
  public void finish() throws IOException {
    if (count != numValues) {
      throw new IllegalStateException(
          "Wrong number of values added, expected: " + numValues + ", got: " + count);
    }
    // 為nextValues中剩下的value編碼  
    flush();
    // DirectWriter的編碼方案存在填充字節(jié)
    int paddingBitsNeeded;
    if (bitsPerValue > Integer.SIZE) {
      paddingBitsNeeded = Long.SIZE - bitsPerValue;
    } else if (bitsPerValue > Short.SIZE) {
      paddingBitsNeeded = Integer.SIZE - bitsPerValue;
    } else if (bitsPerValue > Byte.SIZE) {
      paddingBitsNeeded = Short.SIZE - bitsPerValue;
    } else {
      paddingBitsNeeded = 0;
    }
    final int paddingBytesNeeded = (paddingBitsNeeded + Byte.SIZE - 1) / Byte.SIZE;
    for (int i = 0; i < paddingBytesNeeded; i++) {
      output.writeByte((byte) 0);
    }
    finished = true;
  }
  // 獲取一個(gè)DirectWriter的實(shí)例
  public static DirectWriter getInstance(DataOutput output, long numValues, int bitsPerValue) {
    if (Arrays.binarySearch(SUPPORTED_BITS_PER_VALUE, bitsPerValue) < 0) {
      throw new IllegalArgumentException(
          "Unsupported bitsPerValue " + bitsPerValue + ". Did you use bitsRequired?");
    }
    return new DirectWriter(output, numValues, bitsPerValue);
  }
  // 如果bitsRequired是不支持的，則需要糾正
  private static int roundBits(int bitsRequired) {
    int index = Arrays.binarySearch(SUPPORTED_BITS_PER_VALUE, bitsRequired);
    if (index < 0) { // 如果bitsRequired不是支持的參數(shù)，則使用最接近且大于bitsRequired的參數(shù)
      return SUPPORTED_BITS_PER_VALUE[-index - 1];
    } else {
      return bitsRequired; // 如果是支持的，則使用它自己
    }
  }
  // 通過(guò)有符號(hào)的最大值計(jì)算需要的bitsPerValue
  public static int bitsRequired(long maxValue) {
    return roundBits(PackedInts.bitsRequired(maxValue));
  }
  // 通過(guò)無(wú)符號(hào)的最大值計(jì)算需要的bitsPerValue
  public static int unsignedBitsRequired(long maxValue) {
    return roundBits(PackedInts.unsignedBitsRequired(maxValue));
  }
}

public final class DirectMonotonicWriter {
  public static final int MIN_BLOCK_SHIFT = 2;
  public static final int MAX_BLOCK_SHIFT = 22;
  final IndexOutput meta;
  final IndexOutput data;
  final long numValues;
  final long baseDataPointer;
  final long[] buffer;
  int bufferSize;
  long count;
  boolean finished;
  long previous = Long.MIN_VALUE;
  DirectMonotonicWriter(IndexOutput metaOut, IndexOutput dataOut, long numValues, int blockShift) {
    if (blockShift < MIN_BLOCK_SHIFT || blockShift > MAX_BLOCK_SHIFT) {
      throw new IllegalArgumentException(
          "blockShift must be in ["
              + MIN_BLOCK_SHIFT
              + "-"
              + MAX_BLOCK_SHIFT
              + "], got "
              + blockShift);
    }
    if (numValues < 0) {
      throw new IllegalArgumentException("numValues can't be negative, got " + numValues);
    }
    final long numBlocks = numValues == 0 ? 0 : ((numValues - 1) >>> blockShift) + 1;
    if (numBlocks > ArrayUtil.MAX_ARRAY_LENGTH) {
      throw new IllegalArgumentException(
          "blockShift is too low for the provided number of values: blockShift="
              + blockShift
              + ", numValues="
              + numValues
              + ", MAX_ARRAY_LENGTH="
              + ArrayUtil.MAX_ARRAY_LENGTH);
    }
    this.meta = metaOut;
    this.data = dataOut;
    this.numValues = numValues;
    final int blockSize = 1 << blockShift;
    this.buffer = new long[(int) Math.min(numValues, blockSize)];
    this.bufferSize = 0;
    this.baseDataPointer = dataOut.getFilePointer();
  }
  private void flush() throws IOException {
    assert bufferSize != 0;
    // 估計(jì)數(shù)值遞增的平均步長(zhǎng)
    final float avgInc =
        (float) ((double) (buffer[bufferSize - 1] - buffer[0]) / Math.max(1, bufferSize - 1));
    for (int i = 0; i < bufferSize; ++i) {
      // 按平均步長(zhǎng)算的當(dāng)前位置的期望值  
      final long expected = (long) (avgInc * (long) i);
      // 當(dāng)前真實(shí)值和期望值之差，注意此時(shí)buffer中可能存在負(fù)數(shù) 
      buffer[i] -= expected;
    }
    // 尋找最小的值  
    long min = buffer[0];
    for (int i = 1; i < bufferSize; ++i) {
      min = Math.min(buffer[i], min);
    }
    long maxDelta = 0;
    for (int i = 0; i < bufferSize; ++i) {
      buffer[i] -= min; // 經(jīng)過(guò)這一步，buffer中所有的都是正數(shù)
      maxDelta |= buffer[i];
    }
    meta.writeLong(min);
    meta.writeInt(Float.floatToIntBits(avgInc));
    meta.writeLong(data.getFilePointer() - baseDataPointer);
    if (maxDelta == 0) { // 經(jīng)過(guò)預(yù)處理之后，所有的值都相等
      meta.writeByte((byte) 0);
    } else { // 使用DirectWriter來(lái)進(jìn)行編碼
      final int bitsRequired = DirectWriter.unsignedBitsRequired(maxDelta);
      DirectWriter writer = DirectWriter.getInstance(data, bufferSize, bitsRequired);
      for (int i = 0; i < bufferSize; ++i) {
        writer.add(buffer[i]);
      }
      writer.finish();
      meta.writeByte((byte) bitsRequired);
    }
    bufferSize = 0;
  }
  public void add(long v) throws IOException {
    if (v < previous) { // 如果不是遞增的，則不應(yīng)該使用DirectMonotonicWriter
      throw new IllegalArgumentException("Values do not come in order: " + previous + ", " + v);
    }
    if (bufferSize == buffer.length) { // buffer滿了
      flush();
    }
    buffer[bufferSize++] = v;
    previous = v;
    count++;
  }
  public void finish() throws IOException {
    if (count != numValues) {
      throw new IllegalStateException(
          "Wrong number of values added, expected: " + numValues + ", got: " + count);
    }
    if (finished) {
      throw new IllegalStateException("#finish has been called already");
    }
    if (bufferSize > 0) { // 如果還有數(shù)據(jù)，則先編碼
      flush();
    }
    finished = true;
  }
}