mikemccand commented on code in PR #16245:
URL: https://github.com/apache/lucene/pull/16245#discussion_r3535959234
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/blocktree/IntersectTermsEnumFrame.java:
##########
@@ -190,18 +197,32 @@ void load(TrieReader.Node node) throws IOException {
suffixesReader.reset(suffixBytes, 0, numSuffixBytes);
int numSuffixLengthBytes = ite.in.readVInt();
- final boolean allEqual = (numSuffixLengthBytes & 0x01) != 0;
+ allEqual = (numSuffixLengthBytes & 0x01) != 0;
numSuffixLengthBytes >>>= 1;
- if (suffixLengthBytes.length < numSuffixLengthBytes) {
- suffixLengthBytes = new byte[ArrayUtil.oversize(numSuffixLengthBytes,
1)];
- }
- if (allEqual) {
- Arrays.fill(suffixLengthBytes, 0, numSuffixLengthBytes,
ite.in.readByte());
+ if (isLeafBlock) {
+ if (allEqual) {
+ suffixLength = numSuffixLengthBytes;
+ } else {
+ final int numLongs = numSuffixLengthBytes;
+ suffixLengths = new int[entCount];
+ long[] longs = new long[numLongs];
+ for (int i = 0; i < numLongs; i++) {
+ longs[i] = ite.in.readLong();
+ }
+ // TODO: read and decode one long only when it is needed.
+ Simple64.decodeAll(longs, 0, suffixLengths, 0, entCount);
Review Comment:
So this means we pre-decode all term suffix lengths for the terms in the
block, up front? Vs before when we would incrementally `.readVInt()` on
iterating each term in the block?
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/blocktree/IntersectTermsEnumFrame.java:
##########
@@ -245,8 +266,10 @@ public boolean next() {
public void nextLeaf() {
assert nextEnt != -1 && nextEnt < entCount
: "nextEnt=" + nextEnt + " entCount=" + entCount + " fp=" + fp;
+ if (allEqual == false) {
Review Comment:
Thank you :) (`== false` reduces chanceof future (human) refactoring bugs)
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/blocktree/IntersectTermsEnumFrame.java:
##########
@@ -190,18 +197,32 @@ void load(TrieReader.Node node) throws IOException {
suffixesReader.reset(suffixBytes, 0, numSuffixBytes);
int numSuffixLengthBytes = ite.in.readVInt();
- final boolean allEqual = (numSuffixLengthBytes & 0x01) != 0;
+ allEqual = (numSuffixLengthBytes & 0x01) != 0;
numSuffixLengthBytes >>>= 1;
- if (suffixLengthBytes.length < numSuffixLengthBytes) {
- suffixLengthBytes = new byte[ArrayUtil.oversize(numSuffixLengthBytes,
1)];
- }
- if (allEqual) {
- Arrays.fill(suffixLengthBytes, 0, numSuffixLengthBytes,
ite.in.readByte());
+ if (isLeafBlock) {
+ if (allEqual) {
+ suffixLength = numSuffixLengthBytes;
+ } else {
+ final int numLongs = numSuffixLengthBytes;
+ suffixLengths = new int[entCount];
+ long[] longs = new long[numLongs];
+ for (int i = 0; i < numLongs; i++) {
+ longs[i] = ite.in.readLong();
+ }
+ // TODO: read and decode one long only when it is needed.
+ Simple64.decodeAll(longs, 0, suffixLengths, 0, entCount);
+ }
} else {
- ite.in.readBytes(suffixLengthBytes, 0, numSuffixLengthBytes);
+ if (suffixLengthBytes.length < numSuffixLengthBytes) {
+ suffixLengthBytes = new byte[ArrayUtil.oversize(numSuffixLengthBytes,
1)];
+ }
+ if (allEqual) {
+ Arrays.fill(suffixLengthBytes, 0, numSuffixLengthBytes,
ite.in.readByte());
Review Comment:
Do we only set `allEqual` if lengths are equal *and* less than 128? Should
we at least add `& 0xFF` to move that up to "less than 256"?
Edit: OK nevermind, this is actually correct though kinds sneaky (allEqual
decoded int vs encoded byte depending on leaf vs non-leaf -- let's add
comments).
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/blocktree/Lucene103BlockTreeTermsWriter.java:
##########
@@ -762,11 +763,14 @@ private PendingBlock writeBlock(
boolean absolute = true;
+ int[] suffixLengths = null;
+ boolean allEquals = true;
Review Comment:
`allEqual` (no plural) for consistency w/ reader? Plus @msokolov gets
grumpy if we use plurals heh.
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/blocktree/Lucene103BlockTreeTermsWriter.java:
##########
@@ -931,18 +938,35 @@ private PendingBlock writeBlock(
suffixWriter.setLength(0);
spareWriter.reset();
- // Write suffix lengths
- final int numSuffixBytes = Math.toIntExact(suffixLengthsWriter.size());
- spareBytes = ArrayUtil.growNoCopy(spareBytes, numSuffixBytes);
- suffixLengthsWriter.copyTo(new ByteArrayDataOutput(spareBytes));
- suffixLengthsWriter.reset();
- if (allEqual(spareBytes, 1, numSuffixBytes, spareBytes[0])) {
- // Structured fields like IDs often have most values of the same length
- termsOut.writeVInt((numSuffixBytes << 1) | 1);
- termsOut.writeByte(spareBytes[0]);
+ if (isLeafBlock) {
+ assert suffixLengths != null;
+ if (allEquals) {
+ // All suffix lengths are the same, so we can just write that one
length:
+ termsOut.writeVInt((suffixLengths[0] << 1) | 1);
+ } else {
+ long[] encodedSuffixLengths = new long[suffixLengths.length];
+ int numLongs =
+ Simple64.encodeAll(suffixLengths, 0, suffixLengths.length,
encodedSuffixLengths, 0);
+ termsOut.writeVInt(numLongs << 1);
Review Comment:
Maybe assert `numLongs > 0`? And `numLongs <= suffixLengths.length` maybe.
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/blocktree/SegmentTermsEnumFrame.java:
##########
@@ -49,6 +50,7 @@ final class SegmentTermsEnumFrame {
ByteArrayDataInput suffixesReader;
byte[] suffixLengthBytes;
+ // Only used in non-leaf blocks.
Review Comment:
Maybe add `... because for leaf blocks we fully decode all terms' suffix
lengths up front` or so?
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/blocktree/Lucene103BlockTreeTermsWriter.java:
##########
@@ -931,18 +938,35 @@ private PendingBlock writeBlock(
suffixWriter.setLength(0);
spareWriter.reset();
- // Write suffix lengths
- final int numSuffixBytes = Math.toIntExact(suffixLengthsWriter.size());
- spareBytes = ArrayUtil.growNoCopy(spareBytes, numSuffixBytes);
- suffixLengthsWriter.copyTo(new ByteArrayDataOutput(spareBytes));
- suffixLengthsWriter.reset();
- if (allEqual(spareBytes, 1, numSuffixBytes, spareBytes[0])) {
- // Structured fields like IDs often have most values of the same length
- termsOut.writeVInt((numSuffixBytes << 1) | 1);
- termsOut.writeByte(spareBytes[0]);
+ if (isLeafBlock) {
+ assert suffixLengths != null;
+ if (allEquals) {
+ // All suffix lengths are the same, so we can just write that one
length:
+ termsOut.writeVInt((suffixLengths[0] << 1) | 1);
+ } else {
+ long[] encodedSuffixLengths = new long[suffixLengths.length];
+ int numLongs =
+ Simple64.encodeAll(suffixLengths, 0, suffixLengths.length,
encodedSuffixLengths, 0);
+ termsOut.writeVInt(numLongs << 1);
+ for (int i = 0; i < numLongs; i++) {
+ termsOut.writeLong(encodedSuffixLengths[i]);
Review Comment:
Weird that Lucene doesn't already have sugar somewhere to `writeLongs`
(`writeLongArray` to sidestep plural).
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/blocktree/SegmentTermsEnumFrame.java:
##########
@@ -106,6 +109,7 @@ public SegmentTermsEnumFrame(SegmentTermsEnum ste, int ord)
throws IOException {
this.state = ste.fr.parent.postingsReader.newTermState();
this.state.totalTermFreq = -1;
suffixLengthsReader = new ByteArrayDataInput();
+ suffixLengths = null;
Review Comment:
Not needed -- it's java's default already?
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/blocktree/Lucene103BlockTreeTermsWriter.java:
##########
@@ -931,18 +938,35 @@ private PendingBlock writeBlock(
suffixWriter.setLength(0);
spareWriter.reset();
- // Write suffix lengths
- final int numSuffixBytes = Math.toIntExact(suffixLengthsWriter.size());
- spareBytes = ArrayUtil.growNoCopy(spareBytes, numSuffixBytes);
- suffixLengthsWriter.copyTo(new ByteArrayDataOutput(spareBytes));
- suffixLengthsWriter.reset();
- if (allEqual(spareBytes, 1, numSuffixBytes, spareBytes[0])) {
- // Structured fields like IDs often have most values of the same length
- termsOut.writeVInt((numSuffixBytes << 1) | 1);
- termsOut.writeByte(spareBytes[0]);
+ if (isLeafBlock) {
+ assert suffixLengths != null;
+ if (allEquals) {
+ // All suffix lengths are the same, so we can just write that one
length:
+ termsOut.writeVInt((suffixLengths[0] << 1) | 1);
+ } else {
+ long[] encodedSuffixLengths = new long[suffixLengths.length];
+ int numLongs =
+ Simple64.encodeAll(suffixLengths, 0, suffixLengths.length,
encodedSuffixLengths, 0);
+ termsOut.writeVInt(numLongs << 1);
+ for (int i = 0; i < numLongs; i++) {
+ termsOut.writeLong(encodedSuffixLengths[i]);
+ }
+ }
} else {
- termsOut.writeVInt(numSuffixBytes << 1);
- termsOut.writeBytes(spareBytes, numSuffixBytes);
+ // Write suffix lengths
+ final int numSuffixBytes = Math.toIntExact(suffixLengthsWriter.size());
+ spareBytes = ArrayUtil.growNoCopy(spareBytes, numSuffixBytes);
+ suffixLengthsWriter.copyTo(new ByteArrayDataOutput(spareBytes));
+ suffixLengthsWriter.reset();
+
+ if (allEqual(spareBytes, 1, numSuffixBytes, spareBytes[0])) {
Review Comment:
Hmm I'm confused -- is the `allEqual` concept different for leaf vs non-leaf
blocks? For leaf blocks, we are talking about literally the suffix length of
each term being equal? But then for non-leaf case, we are looking at the
`Simple64` encoded bytes and checking if each `byte` is equal? If so, that's
kinda sneaky, maybe we can rename the method to `allBytesEqual` and sprinkle
some comments explaining the difference?
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/blocktree/SegmentTermsEnumFrame.java:
##########
@@ -79,6 +81,7 @@ final class SegmentTermsEnumFrame {
// True if all entries have the same length.
boolean allEqual;
+ int[] suffixLengths; // only used when !allEqual in leaf blocks.
Review Comment:
`== false` in comment too? (same reason -- even staring at that `!` in my
vision pro (with vision correction "reading glasses") virtual display it's
still maybe easy to miss!).
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/blocktree/SegmentTermsEnumFrame.java:
##########
@@ -209,15 +213,32 @@ void loadBlock() throws IOException {
int numSuffixLengthBytes = ste.in.readVInt();
allEqual = (numSuffixLengthBytes & 0x01) != 0;
numSuffixLengthBytes >>>= 1;
- if (suffixLengthBytes == null || suffixLengthBytes.length <
numSuffixLengthBytes) {
- suffixLengthBytes = new byte[ArrayUtil.oversize(numSuffixLengthBytes,
1)];
- }
- if (allEqual) {
- Arrays.fill(suffixLengthBytes, 0, numSuffixLengthBytes,
ste.in.readByte());
+
+ if (isLeafBlock) {
+ if (allEqual) {
+ suffixLength = numSuffixLengthBytes;
+ } else {
+ final int numLongs = numSuffixLengthBytes;
Review Comment:
We don't usually add pointless/obvious `final` I think? `javac` infers this
well these days?
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/blocktree/SegmentTermsEnumFrame.java:
##########
@@ -690,7 +715,9 @@ public SeekStatus binarySearchTermLeaf(BytesRef target,
boolean exactOnly) throw
assert prefixMatches(target);
- suffixLength = suffixLengthsReader.readVInt();
+ // suffixLength assigned in loadBlock, and all suffixes have the same
length in this block.
+ assert suffixLength >= 0;
Review Comment:
Do we consistently set `suffixLength = -1` when they are *not* all the same?
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/blocktree/SegmentTermsEnumFrame.java:
##########
@@ -690,7 +715,9 @@ public SeekStatus binarySearchTermLeaf(BytesRef target,
boolean exactOnly) throw
assert prefixMatches(target);
- suffixLength = suffixLengthsReader.readVInt();
+ // suffixLength assigned in loadBlock, and all suffixes have the same
length in this block.
Review Comment:
How do we know all suffix lengths are the same here?
##########
lucene/core/src/test/org/apache/lucene/util/TestSimple64.java:
##########
@@ -0,0 +1,208 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util;
+
+import static org.apache.lucene.util.Simple64.BITS;
+import static org.apache.lucene.util.Simple64.COUNTS;
+import static org.apache.lucene.util.Simple64.MASKS;
+
+import java.util.Arrays;
+import java.util.Random;
+import org.apache.lucene.tests.util.LuceneTestCase;
+
+public class TestSimple64 extends LuceneTestCase {
+
+ /** Verify selector table invariants. */
+ public void testSelectorTable() {
+ for (int s = 0; s < 14; s++) {
+ // bits must fit inside the 60 data bits
+ assertTrue("selector " + s + ": COUNTS[s]*BITS[s] <= 60", (long)
COUNTS[s] * BITS[s] <= 60);
+ // max value must be representable as a non-negative int
+ assertTrue(
+ "selector " + s + ": MASKS[s] <= Integer.MAX_VALUE", MASKS[s] <=
Integer.MAX_VALUE);
+ }
+ // selector 13 must cover Integer.MAX_VALUE
+ assertTrue("selector 13 covers Integer.MAX_VALUE", MASKS[13] >=
Integer.MAX_VALUE);
+ }
+
+ /** Each selector should be chosen when values exactly hit its upper bound.
*/
+ public void testSelectorBoundaries() {
+ for (int s = 0; s < 14; s++) {
+ int maxVal = (int) MASKS[s];
+ int[] input = new int[COUNTS[s]];
+ Arrays.fill(input, maxVal);
+ long word = Simple64.encode(input, 0, input.length);
+ assertEquals("selector for bits=" + BITS[s], s, (int) (word >>> 60));
+ }
+ }
+
+ public void testRoundtripSmallValues() {
+ // value=2 needs 2 bits → selector 1 (30 × 2 bits)
+ int[] input = new int[30];
+ Arrays.fill(input, 2);
+ long word = Simple64.encode(input, 0, 30);
+ assertEquals("selector=1 for value=2", 1, (int) (word >>> 60));
+ int[] out = new int[30];
+ assertEquals("decoded count", 30, Simple64.decode(word, out, 0));
+ assertArrayEquals("decoded values", input, out);
+ }
+
+ public void testRoundtripAllSelectors() {
+ for (int s = 0; s < 14; s++) {
+ int count = COUNTS[s];
+ int maxVal = (int) MASKS[s];
+ int[] input = new int[count];
+ Arrays.fill(input, maxVal);
+ long word = Simple64.pack(s, input, 0, count); // force this selector
+ int[] out = new int[count];
+ assertEquals("selector " + s + " decode count", count,
Simple64.decode(word, out, 0));
+ assertArrayEquals("selector " + s + " values", input, out);
+ }
+ }
+
+ public void testFastPathParitySelectors0To3() {
+ Random rng = new Random(7);
+ for (int s = 0; s <= 3; s++) {
+ int[] input = new int[COUNTS[s]];
+ int maxVal = (int) MASKS[s];
+ for (int i = 0; i < input.length; i++) {
+ input[i] = rng.nextInt(maxVal + 1);
+ }
+ assertEquals(
+ "selector " + s + " fast-path word",
+ Simple64.pack(s, input, 0, input.length),
+ Simple64.encode(input, 0, input.length));
+ }
+ }
+
+ /** Selector 13 must handle Integer.MAX_VALUE. */
+ public void testIntegerMaxValue() {
+ int[] input = {Integer.MAX_VALUE};
+ long word = Simple64.encode(input, 0, 1);
+ assertEquals("selector=13 for Integer.MAX_VALUE", 13, (int) (word >>> 60));
+ int[] out = new int[1];
+ Simple64.decode(word, out, 0);
+ assertEquals("decoded Integer.MAX_VALUE", Integer.MAX_VALUE, out[0]);
+ }
+
+ public void testEncodeAll() {
+ int[] input = new int[35];
+ Random rng = new Random(42);
+ for (int i = 0; i < 35; i++) input[i] = rng.nextInt(10) + 1;
+ long[] longs = new long[35];
+ int numLongs = Simple64.encodeAll(input, 0, 35, longs, 0);
+ if (numLongs < longs.length) {
+ assert longs[numLongs] == 0;
+ }
+ int[] decoded = new int[35];
+ Simple64.decodeAll(longs, 0, decoded, 0, 35);
+ assertArrayEquals("encodeAll roundtrip", input, decoded);
+ }
+
+ public void testEncodeAllAndDecodeAllWithOffsets() {
+ int[] input = {7, 2, 6, 6, 5, 1, 8, 2, 7, 2, 3, 4, 5, 6, 7, 8, 9};
+ long[] longs = new long[input.length + 4];
+ Arrays.fill(longs, -1L);
+ int numLongs = Simple64.encodeAll(input, 0, input.length, longs, 2);
+ assertEquals(-1L, longs[1]);
+ if (numLongs + 2 < longs.length) {
+ assertEquals(-1L, longs[numLongs + 2]);
+ }
+
+ int[] decoded = new int[input.length + 6];
+ Arrays.fill(decoded, -1);
+ int consumed = Simple64.decodeAll(longs, 2, decoded, 3, input.length);
+ assertEquals(numLongs, consumed);
+ assertEquals(-1, decoded[2]);
+ assertEquals(-1, decoded[input.length + 3]);
+ assertArrayEquals(input, Arrays.copyOfRange(decoded, 3, 3 + input.length));
+ }
+
+ public void testDecodeWithOutOffset() {
+ int[] input = new int[COUNTS[3]];
+ Arrays.fill(input, 8);
+ long word = Simple64.encode(input, 0, input.length);
+ int[] out = new int[input.length + 4];
+ Arrays.fill(out, -1);
+ assertEquals(input.length, Simple64.decode(word, out, 2));
+ assertEquals(-1, out[1]);
+ assertEquals(-1, out[input.length + 2]);
+ assertArrayEquals(input, Arrays.copyOfRange(out, 2, 2 + input.length));
+ }
+
+ public void testSuffixLengths() {
+ int[] input = {
+ 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4,
3, 3, 8, 3
+ };
+ int len = input.length;
+ long[] longs = new long[len];
+ int numLongs = Simple64.encodeAll(input, 0, len, longs, 0);
+ if (numLongs < longs.length) {
+ assert longs[numLongs] == 0;
+ }
+ int[] decoded = new int[len];
+ Simple64.decodeAll(longs, 0, decoded, 0, len);
+ assertArrayEquals("suffix roundtrip", input, decoded);
+ }
+
+ public void testCountWithoutDecode() {
+ // value=63 needs 6 bits → selector 5 (10 × 6 bits)
+ int[] input = new int[10];
+ Arrays.fill(input, 63);
+ long word = Simple64.encode(input, 0, 10);
+ assertEquals("selector=5 for value=63", 5, (int) (word >>> 60));
+ assertEquals("count()==10", 10, Simple64.count(word));
+ }
+
+ public void testInvalidInputs() {
+ expectThrows(IllegalArgumentException.class, () -> Simple64.encode(new
int[1], 0, 0));
+ expectThrows(IllegalArgumentException.class, () -> Simple64.encode(new
int[] {-1}, 0, 1));
+
+ long invalidSelector = 14L << 60;
+ expectThrows(IllegalArgumentException.class, () ->
Simple64.count(invalidSelector));
+ expectThrows(
+ IllegalArgumentException.class, () -> Simple64.decode(invalidSelector,
new int[1], 0));
+ expectThrows(
+ IllegalArgumentException.class,
+ () -> Simple64.decodeAll(new long[] {invalidSelector}, 0, new int[1],
0, 1));
+ }
+
+ public void testFuzz() {
+ Random rng = new Random(12345);
+ int rounds = 20_000;
+ int errors = 0;
+ for (int r = 0; r < rounds; r++) {
+ int len = rng.nextInt(60) + 1;
+ // random bit-width 1..31 to exercise all selectors including 13
+ int maxBits = rng.nextInt(31) + 1;
+ int maxVal = (maxBits == 31) ? Integer.MAX_VALUE : (1 << maxBits) - 1;
+ int[] input = new int[len];
+ for (int i = 0; i < len; i++)
Review Comment:
MIssing `{ .. }` around for loop body.
##########
lucene/core/src/test/org/apache/lucene/util/TestSimple64.java:
##########
@@ -0,0 +1,208 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util;
+
+import static org.apache.lucene.util.Simple64.BITS;
+import static org.apache.lucene.util.Simple64.COUNTS;
+import static org.apache.lucene.util.Simple64.MASKS;
+
+import java.util.Arrays;
+import java.util.Random;
+import org.apache.lucene.tests.util.LuceneTestCase;
+
+public class TestSimple64 extends LuceneTestCase {
+
+ /** Verify selector table invariants. */
+ public void testSelectorTable() {
+ for (int s = 0; s < 14; s++) {
+ // bits must fit inside the 60 data bits
+ assertTrue("selector " + s + ": COUNTS[s]*BITS[s] <= 60", (long)
COUNTS[s] * BITS[s] <= 60);
+ // max value must be representable as a non-negative int
+ assertTrue(
+ "selector " + s + ": MASKS[s] <= Integer.MAX_VALUE", MASKS[s] <=
Integer.MAX_VALUE);
+ }
+ // selector 13 must cover Integer.MAX_VALUE
+ assertTrue("selector 13 covers Integer.MAX_VALUE", MASKS[13] >=
Integer.MAX_VALUE);
+ }
+
+ /** Each selector should be chosen when values exactly hit its upper bound.
*/
+ public void testSelectorBoundaries() {
+ for (int s = 0; s < 14; s++) {
+ int maxVal = (int) MASKS[s];
+ int[] input = new int[COUNTS[s]];
+ Arrays.fill(input, maxVal);
+ long word = Simple64.encode(input, 0, input.length);
+ assertEquals("selector for bits=" + BITS[s], s, (int) (word >>> 60));
+ }
+ }
+
+ public void testRoundtripSmallValues() {
+ // value=2 needs 2 bits → selector 1 (30 × 2 bits)
+ int[] input = new int[30];
+ Arrays.fill(input, 2);
+ long word = Simple64.encode(input, 0, 30);
+ assertEquals("selector=1 for value=2", 1, (int) (word >>> 60));
+ int[] out = new int[30];
+ assertEquals("decoded count", 30, Simple64.decode(word, out, 0));
+ assertArrayEquals("decoded values", input, out);
+ }
+
+ public void testRoundtripAllSelectors() {
+ for (int s = 0; s < 14; s++) {
+ int count = COUNTS[s];
+ int maxVal = (int) MASKS[s];
+ int[] input = new int[count];
+ Arrays.fill(input, maxVal);
+ long word = Simple64.pack(s, input, 0, count); // force this selector
+ int[] out = new int[count];
+ assertEquals("selector " + s + " decode count", count,
Simple64.decode(word, out, 0));
+ assertArrayEquals("selector " + s + " values", input, out);
+ }
+ }
+
+ public void testFastPathParitySelectors0To3() {
+ Random rng = new Random(7);
+ for (int s = 0; s <= 3; s++) {
+ int[] input = new int[COUNTS[s]];
+ int maxVal = (int) MASKS[s];
+ for (int i = 0; i < input.length; i++) {
+ input[i] = rng.nextInt(maxVal + 1);
+ }
+ assertEquals(
+ "selector " + s + " fast-path word",
+ Simple64.pack(s, input, 0, input.length),
+ Simple64.encode(input, 0, input.length));
+ }
+ }
+
+ /** Selector 13 must handle Integer.MAX_VALUE. */
+ public void testIntegerMaxValue() {
+ int[] input = {Integer.MAX_VALUE};
+ long word = Simple64.encode(input, 0, 1);
+ assertEquals("selector=13 for Integer.MAX_VALUE", 13, (int) (word >>> 60));
+ int[] out = new int[1];
+ Simple64.decode(word, out, 0);
+ assertEquals("decoded Integer.MAX_VALUE", Integer.MAX_VALUE, out[0]);
+ }
+
+ public void testEncodeAll() {
+ int[] input = new int[35];
+ Random rng = new Random(42);
+ for (int i = 0; i < 35; i++) input[i] = rng.nextInt(10) + 1;
+ long[] longs = new long[35];
+ int numLongs = Simple64.encodeAll(input, 0, 35, longs, 0);
+ if (numLongs < longs.length) {
+ assert longs[numLongs] == 0;
+ }
+ int[] decoded = new int[35];
+ Simple64.decodeAll(longs, 0, decoded, 0, 35);
+ assertArrayEquals("encodeAll roundtrip", input, decoded);
+ }
+
+ public void testEncodeAllAndDecodeAllWithOffsets() {
+ int[] input = {7, 2, 6, 6, 5, 1, 8, 2, 7, 2, 3, 4, 5, 6, 7, 8, 9};
+ long[] longs = new long[input.length + 4];
+ Arrays.fill(longs, -1L);
+ int numLongs = Simple64.encodeAll(input, 0, input.length, longs, 2);
+ assertEquals(-1L, longs[1]);
+ if (numLongs + 2 < longs.length) {
+ assertEquals(-1L, longs[numLongs + 2]);
+ }
+
+ int[] decoded = new int[input.length + 6];
+ Arrays.fill(decoded, -1);
+ int consumed = Simple64.decodeAll(longs, 2, decoded, 3, input.length);
+ assertEquals(numLongs, consumed);
+ assertEquals(-1, decoded[2]);
+ assertEquals(-1, decoded[input.length + 3]);
+ assertArrayEquals(input, Arrays.copyOfRange(decoded, 3, 3 + input.length));
+ }
+
+ public void testDecodeWithOutOffset() {
+ int[] input = new int[COUNTS[3]];
+ Arrays.fill(input, 8);
+ long word = Simple64.encode(input, 0, input.length);
+ int[] out = new int[input.length + 4];
+ Arrays.fill(out, -1);
+ assertEquals(input.length, Simple64.decode(word, out, 2));
+ assertEquals(-1, out[1]);
+ assertEquals(-1, out[input.length + 2]);
+ assertArrayEquals(input, Arrays.copyOfRange(out, 2, 2 + input.length));
+ }
+
+ public void testSuffixLengths() {
+ int[] input = {
+ 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4,
3, 3, 8, 3
+ };
+ int len = input.length;
+ long[] longs = new long[len];
+ int numLongs = Simple64.encodeAll(input, 0, len, longs, 0);
+ if (numLongs < longs.length) {
+ assert longs[numLongs] == 0;
+ }
+ int[] decoded = new int[len];
+ Simple64.decodeAll(longs, 0, decoded, 0, len);
+ assertArrayEquals("suffix roundtrip", input, decoded);
+ }
+
+ public void testCountWithoutDecode() {
+ // value=63 needs 6 bits → selector 5 (10 × 6 bits)
+ int[] input = new int[10];
+ Arrays.fill(input, 63);
+ long word = Simple64.encode(input, 0, 10);
+ assertEquals("selector=5 for value=63", 5, (int) (word >>> 60));
+ assertEquals("count()==10", 10, Simple64.count(word));
Review Comment:
We could also `assert` this count when reading / decoding block? In fact,
when we decode all up front in leaf block, we should assert we consumed all
bytes? I guess we do already (`decodeAll`?).
##########
lucene/core/src/test/org/apache/lucene/util/TestSimple64.java:
##########
@@ -0,0 +1,208 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util;
+
+import static org.apache.lucene.util.Simple64.BITS;
+import static org.apache.lucene.util.Simple64.COUNTS;
+import static org.apache.lucene.util.Simple64.MASKS;
+
+import java.util.Arrays;
+import java.util.Random;
+import org.apache.lucene.tests.util.LuceneTestCase;
+
+public class TestSimple64 extends LuceneTestCase {
+
+ /** Verify selector table invariants. */
+ public void testSelectorTable() {
+ for (int s = 0; s < 14; s++) {
+ // bits must fit inside the 60 data bits
+ assertTrue("selector " + s + ": COUNTS[s]*BITS[s] <= 60", (long)
COUNTS[s] * BITS[s] <= 60);
+ // max value must be representable as a non-negative int
+ assertTrue(
+ "selector " + s + ": MASKS[s] <= Integer.MAX_VALUE", MASKS[s] <=
Integer.MAX_VALUE);
+ }
+ // selector 13 must cover Integer.MAX_VALUE
+ assertTrue("selector 13 covers Integer.MAX_VALUE", MASKS[13] >=
Integer.MAX_VALUE);
+ }
+
+ /** Each selector should be chosen when values exactly hit its upper bound.
*/
+ public void testSelectorBoundaries() {
+ for (int s = 0; s < 14; s++) {
+ int maxVal = (int) MASKS[s];
+ int[] input = new int[COUNTS[s]];
+ Arrays.fill(input, maxVal);
+ long word = Simple64.encode(input, 0, input.length);
+ assertEquals("selector for bits=" + BITS[s], s, (int) (word >>> 60));
+ }
+ }
+
+ public void testRoundtripSmallValues() {
+ // value=2 needs 2 bits → selector 1 (30 × 2 bits)
+ int[] input = new int[30];
+ Arrays.fill(input, 2);
+ long word = Simple64.encode(input, 0, 30);
+ assertEquals("selector=1 for value=2", 1, (int) (word >>> 60));
+ int[] out = new int[30];
+ assertEquals("decoded count", 30, Simple64.decode(word, out, 0));
+ assertArrayEquals("decoded values", input, out);
+ }
+
+ public void testRoundtripAllSelectors() {
+ for (int s = 0; s < 14; s++) {
+ int count = COUNTS[s];
+ int maxVal = (int) MASKS[s];
+ int[] input = new int[count];
+ Arrays.fill(input, maxVal);
+ long word = Simple64.pack(s, input, 0, count); // force this selector
+ int[] out = new int[count];
+ assertEquals("selector " + s + " decode count", count,
Simple64.decode(word, out, 0));
+ assertArrayEquals("selector " + s + " values", input, out);
+ }
+ }
+
+ public void testFastPathParitySelectors0To3() {
+ Random rng = new Random(7);
+ for (int s = 0; s <= 3; s++) {
+ int[] input = new int[COUNTS[s]];
+ int maxVal = (int) MASKS[s];
+ for (int i = 0; i < input.length; i++) {
+ input[i] = rng.nextInt(maxVal + 1);
+ }
+ assertEquals(
+ "selector " + s + " fast-path word",
+ Simple64.pack(s, input, 0, input.length),
+ Simple64.encode(input, 0, input.length));
+ }
+ }
+
+ /** Selector 13 must handle Integer.MAX_VALUE. */
+ public void testIntegerMaxValue() {
+ int[] input = {Integer.MAX_VALUE};
+ long word = Simple64.encode(input, 0, 1);
+ assertEquals("selector=13 for Integer.MAX_VALUE", 13, (int) (word >>> 60));
+ int[] out = new int[1];
+ Simple64.decode(word, out, 0);
+ assertEquals("decoded Integer.MAX_VALUE", Integer.MAX_VALUE, out[0]);
+ }
+
+ public void testEncodeAll() {
+ int[] input = new int[35];
+ Random rng = new Random(42);
+ for (int i = 0; i < 35; i++) input[i] = rng.nextInt(10) + 1;
+ long[] longs = new long[35];
+ int numLongs = Simple64.encodeAll(input, 0, 35, longs, 0);
+ if (numLongs < longs.length) {
+ assert longs[numLongs] == 0;
+ }
+ int[] decoded = new int[35];
+ Simple64.decodeAll(longs, 0, decoded, 0, 35);
+ assertArrayEquals("encodeAll roundtrip", input, decoded);
+ }
+
+ public void testEncodeAllAndDecodeAllWithOffsets() {
+ int[] input = {7, 2, 6, 6, 5, 1, 8, 2, 7, 2, 3, 4, 5, 6, 7, 8, 9};
+ long[] longs = new long[input.length + 4];
+ Arrays.fill(longs, -1L);
+ int numLongs = Simple64.encodeAll(input, 0, input.length, longs, 2);
+ assertEquals(-1L, longs[1]);
+ if (numLongs + 2 < longs.length) {
+ assertEquals(-1L, longs[numLongs + 2]);
+ }
+
+ int[] decoded = new int[input.length + 6];
+ Arrays.fill(decoded, -1);
+ int consumed = Simple64.decodeAll(longs, 2, decoded, 3, input.length);
+ assertEquals(numLongs, consumed);
+ assertEquals(-1, decoded[2]);
+ assertEquals(-1, decoded[input.length + 3]);
+ assertArrayEquals(input, Arrays.copyOfRange(decoded, 3, 3 + input.length));
+ }
+
+ public void testDecodeWithOutOffset() {
+ int[] input = new int[COUNTS[3]];
+ Arrays.fill(input, 8);
+ long word = Simple64.encode(input, 0, input.length);
+ int[] out = new int[input.length + 4];
+ Arrays.fill(out, -1);
+ assertEquals(input.length, Simple64.decode(word, out, 2));
+ assertEquals(-1, out[1]);
+ assertEquals(-1, out[input.length + 2]);
+ assertArrayEquals(input, Arrays.copyOfRange(out, 2, 2 + input.length));
+ }
+
+ public void testSuffixLengths() {
+ int[] input = {
+ 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4,
3, 3, 8, 3
+ };
+ int len = input.length;
+ long[] longs = new long[len];
+ int numLongs = Simple64.encodeAll(input, 0, len, longs, 0);
+ if (numLongs < longs.length) {
+ assert longs[numLongs] == 0;
+ }
+ int[] decoded = new int[len];
+ Simple64.decodeAll(longs, 0, decoded, 0, len);
+ assertArrayEquals("suffix roundtrip", input, decoded);
+ }
+
+ public void testCountWithoutDecode() {
+ // value=63 needs 6 bits → selector 5 (10 × 6 bits)
+ int[] input = new int[10];
+ Arrays.fill(input, 63);
+ long word = Simple64.encode(input, 0, 10);
+ assertEquals("selector=5 for value=63", 5, (int) (word >>> 60));
+ assertEquals("count()==10", 10, Simple64.count(word));
+ }
+
+ public void testInvalidInputs() {
+ expectThrows(IllegalArgumentException.class, () -> Simple64.encode(new
int[1], 0, 0));
+ expectThrows(IllegalArgumentException.class, () -> Simple64.encode(new
int[] {-1}, 0, 1));
+
+ long invalidSelector = 14L << 60;
+ expectThrows(IllegalArgumentException.class, () ->
Simple64.count(invalidSelector));
+ expectThrows(
+ IllegalArgumentException.class, () -> Simple64.decode(invalidSelector,
new int[1], 0));
+ expectThrows(
+ IllegalArgumentException.class,
+ () -> Simple64.decodeAll(new long[] {invalidSelector}, 0, new int[1],
0, 1));
+ }
+
+ public void testFuzz() {
+ Random rng = new Random(12345);
+ int rounds = 20_000;
+ int errors = 0;
+ for (int r = 0; r < rounds; r++) {
+ int len = rng.nextInt(60) + 1;
+ // random bit-width 1..31 to exercise all selectors including 13
+ int maxBits = rng.nextInt(31) + 1;
+ int maxVal = (maxBits == 31) ? Integer.MAX_VALUE : (1 << maxBits) - 1;
+ int[] input = new int[len];
+ for (int i = 0; i < len; i++)
+ input[i] = (int) (((long) rng.nextInt() & 0x7FFFFFFFL) % ((long)
maxVal + 1));
+ long[] longs = new long[len + 1];
+ int numLongs = Simple64.encodeAll(input, 0, len, longs, 0);
+ if (numLongs < longs.length) {
+ assert longs[numLongs] == 0;
+ }
+ int[] decoded = new int[len];
+ Simple64.decodeAll(longs, 0, decoded, 0, len);
+ if (!Arrays.equals(input, decoded)) errors++;
Review Comment:
`== false`? And break the if body onto `{ .. }` newline. And throw
immediate exception? As written this test is hard to debug / non-obvious root
cause on failure...
##########
lucene/core/src/test/org/apache/lucene/util/TestSimple64.java:
##########
@@ -0,0 +1,208 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util;
+
+import static org.apache.lucene.util.Simple64.BITS;
+import static org.apache.lucene.util.Simple64.COUNTS;
+import static org.apache.lucene.util.Simple64.MASKS;
+
+import java.util.Arrays;
+import java.util.Random;
+import org.apache.lucene.tests.util.LuceneTestCase;
+
+public class TestSimple64 extends LuceneTestCase {
+
+ /** Verify selector table invariants. */
+ public void testSelectorTable() {
+ for (int s = 0; s < 14; s++) {
+ // bits must fit inside the 60 data bits
+ assertTrue("selector " + s + ": COUNTS[s]*BITS[s] <= 60", (long)
COUNTS[s] * BITS[s] <= 60);
+ // max value must be representable as a non-negative int
+ assertTrue(
+ "selector " + s + ": MASKS[s] <= Integer.MAX_VALUE", MASKS[s] <=
Integer.MAX_VALUE);
+ }
+ // selector 13 must cover Integer.MAX_VALUE
+ assertTrue("selector 13 covers Integer.MAX_VALUE", MASKS[13] >=
Integer.MAX_VALUE);
+ }
+
+ /** Each selector should be chosen when values exactly hit its upper bound.
*/
+ public void testSelectorBoundaries() {
+ for (int s = 0; s < 14; s++) {
+ int maxVal = (int) MASKS[s];
+ int[] input = new int[COUNTS[s]];
+ Arrays.fill(input, maxVal);
+ long word = Simple64.encode(input, 0, input.length);
+ assertEquals("selector for bits=" + BITS[s], s, (int) (word >>> 60));
+ }
+ }
+
+ public void testRoundtripSmallValues() {
+ // value=2 needs 2 bits → selector 1 (30 × 2 bits)
+ int[] input = new int[30];
+ Arrays.fill(input, 2);
+ long word = Simple64.encode(input, 0, 30);
+ assertEquals("selector=1 for value=2", 1, (int) (word >>> 60));
+ int[] out = new int[30];
+ assertEquals("decoded count", 30, Simple64.decode(word, out, 0));
+ assertArrayEquals("decoded values", input, out);
+ }
+
+ public void testRoundtripAllSelectors() {
+ for (int s = 0; s < 14; s++) {
+ int count = COUNTS[s];
+ int maxVal = (int) MASKS[s];
+ int[] input = new int[count];
+ Arrays.fill(input, maxVal);
+ long word = Simple64.pack(s, input, 0, count); // force this selector
+ int[] out = new int[count];
+ assertEquals("selector " + s + " decode count", count,
Simple64.decode(word, out, 0));
+ assertArrayEquals("selector " + s + " values", input, out);
+ }
+ }
+
+ public void testFastPathParitySelectors0To3() {
+ Random rng = new Random(7);
+ for (int s = 0; s <= 3; s++) {
+ int[] input = new int[COUNTS[s]];
+ int maxVal = (int) MASKS[s];
+ for (int i = 0; i < input.length; i++) {
+ input[i] = rng.nextInt(maxVal + 1);
+ }
+ assertEquals(
+ "selector " + s + " fast-path word",
+ Simple64.pack(s, input, 0, input.length),
+ Simple64.encode(input, 0, input.length));
+ }
+ }
+
+ /** Selector 13 must handle Integer.MAX_VALUE. */
+ public void testIntegerMaxValue() {
+ int[] input = {Integer.MAX_VALUE};
+ long word = Simple64.encode(input, 0, 1);
+ assertEquals("selector=13 for Integer.MAX_VALUE", 13, (int) (word >>> 60));
+ int[] out = new int[1];
+ Simple64.decode(word, out, 0);
+ assertEquals("decoded Integer.MAX_VALUE", Integer.MAX_VALUE, out[0]);
+ }
+
+ public void testEncodeAll() {
+ int[] input = new int[35];
+ Random rng = new Random(42);
+ for (int i = 0; i < 35; i++) input[i] = rng.nextInt(10) + 1;
+ long[] longs = new long[35];
+ int numLongs = Simple64.encodeAll(input, 0, 35, longs, 0);
+ if (numLongs < longs.length) {
+ assert longs[numLongs] == 0;
+ }
+ int[] decoded = new int[35];
+ Simple64.decodeAll(longs, 0, decoded, 0, 35);
+ assertArrayEquals("encodeAll roundtrip", input, decoded);
+ }
+
+ public void testEncodeAllAndDecodeAllWithOffsets() {
+ int[] input = {7, 2, 6, 6, 5, 1, 8, 2, 7, 2, 3, 4, 5, 6, 7, 8, 9};
+ long[] longs = new long[input.length + 4];
+ Arrays.fill(longs, -1L);
+ int numLongs = Simple64.encodeAll(input, 0, input.length, longs, 2);
+ assertEquals(-1L, longs[1]);
+ if (numLongs + 2 < longs.length) {
+ assertEquals(-1L, longs[numLongs + 2]);
+ }
+
+ int[] decoded = new int[input.length + 6];
+ Arrays.fill(decoded, -1);
+ int consumed = Simple64.decodeAll(longs, 2, decoded, 3, input.length);
+ assertEquals(numLongs, consumed);
+ assertEquals(-1, decoded[2]);
+ assertEquals(-1, decoded[input.length + 3]);
+ assertArrayEquals(input, Arrays.copyOfRange(decoded, 3, 3 + input.length));
+ }
+
+ public void testDecodeWithOutOffset() {
+ int[] input = new int[COUNTS[3]];
+ Arrays.fill(input, 8);
+ long word = Simple64.encode(input, 0, input.length);
+ int[] out = new int[input.length + 4];
+ Arrays.fill(out, -1);
+ assertEquals(input.length, Simple64.decode(word, out, 2));
+ assertEquals(-1, out[1]);
+ assertEquals(-1, out[input.length + 2]);
+ assertArrayEquals(input, Arrays.copyOfRange(out, 2, 2 + input.length));
+ }
+
+ public void testSuffixLengths() {
+ int[] input = {
+ 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4,
3, 3, 8, 3
+ };
+ int len = input.length;
+ long[] longs = new long[len];
+ int numLongs = Simple64.encodeAll(input, 0, len, longs, 0);
+ if (numLongs < longs.length) {
+ assert longs[numLongs] == 0;
+ }
+ int[] decoded = new int[len];
+ Simple64.decodeAll(longs, 0, decoded, 0, len);
+ assertArrayEquals("suffix roundtrip", input, decoded);
+ }
+
+ public void testCountWithoutDecode() {
+ // value=63 needs 6 bits → selector 5 (10 × 6 bits)
+ int[] input = new int[10];
+ Arrays.fill(input, 63);
+ long word = Simple64.encode(input, 0, 10);
+ assertEquals("selector=5 for value=63", 5, (int) (word >>> 60));
+ assertEquals("count()==10", 10, Simple64.count(word));
+ }
+
+ public void testInvalidInputs() {
+ expectThrows(IllegalArgumentException.class, () -> Simple64.encode(new
int[1], 0, 0));
+ expectThrows(IllegalArgumentException.class, () -> Simple64.encode(new
int[] {-1}, 0, 1));
+
+ long invalidSelector = 14L << 60;
+ expectThrows(IllegalArgumentException.class, () ->
Simple64.count(invalidSelector));
+ expectThrows(
+ IllegalArgumentException.class, () -> Simple64.decode(invalidSelector,
new int[1], 0));
+ expectThrows(
+ IllegalArgumentException.class,
+ () -> Simple64.decodeAll(new long[] {invalidSelector}, 0, new int[1],
0, 1));
+ }
+
+ public void testFuzz() {
+ Random rng = new Random(12345);
+ int rounds = 20_000;
+ int errors = 0;
+ for (int r = 0; r < rounds; r++) {
+ int len = rng.nextInt(60) + 1;
+ // random bit-width 1..31 to exercise all selectors including 13
+ int maxBits = rng.nextInt(31) + 1;
+ int maxVal = (maxBits == 31) ? Integer.MAX_VALUE : (1 << maxBits) - 1;
+ int[] input = new int[len];
+ for (int i = 0; i < len; i++)
+ input[i] = (int) (((long) rng.nextInt() & 0x7FFFFFFFL) % ((long)
maxVal + 1));
+ long[] longs = new long[len + 1];
+ int numLongs = Simple64.encodeAll(input, 0, len, longs, 0);
+ if (numLongs < longs.length) {
Review Comment:
Maybe also `assert numLongs <= len`? Simple64 never expands right (takes
more longs to hold the `int[]` than original count of int values)? Hmm let's
add a test case encoding array of all `Integer.MAX_VALUE`?
Do we confirm `IllegalArgumentException` when passing negative values?
Suffix length 0 is allowed right? (exactly once per block, in the case of
terms dicts usage).
##########
lucene/core/src/java/org/apache/lucene/util/Simple64.java:
##########
@@ -0,0 +1,828 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util;
+
+/**
+ * Simple64: pack multiple small non-negative integers into a single long.
+ *
+ * <p>The high 4 bits of each long are a selector that encodes the bit-width
and count of the packed
+ * integers. The remaining 60 bits hold the actual values, packed from LSB to
MSB.
+ *
+ * <p>Designed for {@code int} values (non-negative, max {@link
Integer#MAX_VALUE} = 2^31 - 1).
+ *
+ * <p>Selector table (14 schemes, selectors 14-15 reserved):
+ *
+ * <pre>
+ * selector | integers | bits each | max value
+ * ---------+----------+-----------+--------------------
+ * 0 | 60 | 1 | 1
+ * 1 | 30 | 2 | 3
+ * 2 | 20 | 3 | 7
+ * 3 | 15 | 4 | 15
+ * 4 | 12 | 5 | 31
+ * 5 | 10 | 6 | 63
+ * 6 | 8 | 7 | 127
+ * 7 | 7 | 8 | 255
+ * 8 | 6 | 10 | 1023
+ * 9 | 5 | 12 | 4095
+ * 10 | 4 | 15 | 32767
+ * 11 | 3 | 20 | 1048575
+ * 12 | 2 | 30 | 1073741823
+ * 13 | 1 | 31 | 2147483647 (Integer.MAX_VALUE)
+ * </pre>
+ *
+ * <p>Every selector has a hand-unrolled pack/decode pair (e.g. {@link
#pack8x7} / {@link
+ * #decode8x7}) used whenever a word is completely full for that selector,
avoiding the generic
+ * shift-loop in {@link #unpack} for the common case.
+ */
+public final class Simple64 {
+ /** Number of integers each selector can pack. */
+ public static final int[] COUNTS = {60, 30, 20, 15, 12, 10, 8, 7, 6, 5, 4,
3, 2, 1};
Review Comment:
`private` or package private? Imagine if somewhere in a Lucene test or a
nasty supply chain source ... I snuck in a `Simple64.COUNTS[3] = 1` heh ...
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/blocktree/Lucene103BlockTreeTermsWriter.java:
##########
@@ -931,18 +938,35 @@ private PendingBlock writeBlock(
suffixWriter.setLength(0);
spareWriter.reset();
- // Write suffix lengths
- final int numSuffixBytes = Math.toIntExact(suffixLengthsWriter.size());
- spareBytes = ArrayUtil.growNoCopy(spareBytes, numSuffixBytes);
- suffixLengthsWriter.copyTo(new ByteArrayDataOutput(spareBytes));
- suffixLengthsWriter.reset();
- if (allEqual(spareBytes, 1, numSuffixBytes, spareBytes[0])) {
- // Structured fields like IDs often have most values of the same length
- termsOut.writeVInt((numSuffixBytes << 1) | 1);
- termsOut.writeByte(spareBytes[0]);
+ if (isLeafBlock) {
+ assert suffixLengths != null;
+ if (allEquals) {
+ // All suffix lengths are the same, so we can just write that one
length:
+ termsOut.writeVInt((suffixLengths[0] << 1) | 1);
+ } else {
+ long[] encodedSuffixLengths = new long[suffixLengths.length];
+ int numLongs =
+ Simple64.encodeAll(suffixLengths, 0, suffixLengths.length,
encodedSuffixLengths, 0);
+ termsOut.writeVInt(numLongs << 1);
+ for (int i = 0; i < numLongs; i++) {
+ termsOut.writeLong(encodedSuffixLengths[i]);
+ }
+ }
} else {
- termsOut.writeVInt(numSuffixBytes << 1);
- termsOut.writeBytes(spareBytes, numSuffixBytes);
+ // Write suffix lengths
+ final int numSuffixBytes = Math.toIntExact(suffixLengthsWriter.size());
+ spareBytes = ArrayUtil.growNoCopy(spareBytes, numSuffixBytes);
+ suffixLengthsWriter.copyTo(new ByteArrayDataOutput(spareBytes));
Review Comment:
Hmm is there really no `.writeBytes` we can use? Seems wasteful to spin up
a whole new single-use `ByteArrayDataOutput` just to copy bytes...
##########
lucene/core/src/java/org/apache/lucene/util/Simple64.java:
##########
@@ -0,0 +1,828 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util;
+
+/**
+ * Simple64: pack multiple small non-negative integers into a single long.
+ *
+ * <p>The high 4 bits of each long are a selector that encodes the bit-width
and count of the packed
+ * integers. The remaining 60 bits hold the actual values, packed from LSB to
MSB.
+ *
+ * <p>Designed for {@code int} values (non-negative, max {@link
Integer#MAX_VALUE} = 2^31 - 1).
+ *
+ * <p>Selector table (14 schemes, selectors 14-15 reserved):
+ *
+ * <pre>
+ * selector | integers | bits each | max value
+ * ---------+----------+-----------+--------------------
+ * 0 | 60 | 1 | 1
+ * 1 | 30 | 2 | 3
+ * 2 | 20 | 3 | 7
+ * 3 | 15 | 4 | 15
+ * 4 | 12 | 5 | 31
+ * 5 | 10 | 6 | 63
+ * 6 | 8 | 7 | 127
+ * 7 | 7 | 8 | 255
+ * 8 | 6 | 10 | 1023
+ * 9 | 5 | 12 | 4095
+ * 10 | 4 | 15 | 32767
+ * 11 | 3 | 20 | 1048575
+ * 12 | 2 | 30 | 1073741823
+ * 13 | 1 | 31 | 2147483647 (Integer.MAX_VALUE)
+ * </pre>
+ *
+ * <p>Every selector has a hand-unrolled pack/decode pair (e.g. {@link
#pack8x7} / {@link
+ * #decode8x7}) used whenever a word is completely full for that selector,
avoiding the generic
+ * shift-loop in {@link #unpack} for the common case.
+ */
+public final class Simple64 {
+ /** Number of integers each selector can pack. */
+ public static final int[] COUNTS = {60, 30, 20, 15, 12, 10, 8, 7, 6, 5, 4,
3, 2, 1};
+
+ /** Bit-width per integer for each selector. */
+ public static final int[] BITS = {1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15, 20,
30, 31};
+
+ /** Bit-mask for extracting one value under each selector. */
+ public static final long[] MASKS = new long[14];
+
+ static {
+ for (int s = 0; s < 14; s++) {
Review Comment:
Change `14` -> `MASKS.length`?
##########
lucene/core/src/java/org/apache/lucene/util/Simple64.java:
##########
@@ -0,0 +1,828 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util;
+
+/**
+ * Simple64: pack multiple small non-negative integers into a single long.
+ *
+ * <p>The high 4 bits of each long are a selector that encodes the bit-width
and count of the packed
+ * integers. The remaining 60 bits hold the actual values, packed from LSB to
MSB.
+ *
+ * <p>Designed for {@code int} values (non-negative, max {@link
Integer#MAX_VALUE} = 2^31 - 1).
+ *
+ * <p>Selector table (14 schemes, selectors 14-15 reserved):
+ *
+ * <pre>
+ * selector | integers | bits each | max value
+ * ---------+----------+-----------+--------------------
+ * 0 | 60 | 1 | 1
+ * 1 | 30 | 2 | 3
+ * 2 | 20 | 3 | 7
+ * 3 | 15 | 4 | 15
+ * 4 | 12 | 5 | 31
+ * 5 | 10 | 6 | 63
+ * 6 | 8 | 7 | 127
+ * 7 | 7 | 8 | 255
+ * 8 | 6 | 10 | 1023
+ * 9 | 5 | 12 | 4095
+ * 10 | 4 | 15 | 32767
+ * 11 | 3 | 20 | 1048575
+ * 12 | 2 | 30 | 1073741823
+ * 13 | 1 | 31 | 2147483647 (Integer.MAX_VALUE)
+ * </pre>
+ *
+ * <p>Every selector has a hand-unrolled pack/decode pair (e.g. {@link
#pack8x7} / {@link
+ * #decode8x7}) used whenever a word is completely full for that selector,
avoiding the generic
+ * shift-loop in {@link #unpack} for the common case.
+ */
+public final class Simple64 {
+ /** Number of integers each selector can pack. */
+ public static final int[] COUNTS = {60, 30, 20, 15, 12, 10, 8, 7, 6, 5, 4,
3, 2, 1};
+
+ /** Bit-width per integer for each selector. */
+ public static final int[] BITS = {1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15, 20,
30, 31};
+
+ /** Bit-mask for extracting one value under each selector. */
+ public static final long[] MASKS = new long[14];
+
+ static {
+ for (int s = 0; s < 14; s++) {
+ MASKS[s] = (1L << BITS[s]) - 1L;
+ }
+ }
+
+ private Simple64() {}
+
+ /**
+ * Encode as many integers from {@code ints[offset..]} as fit into a single
long, using the
+ * most-compact selector whose bit-width can represent every value.
+ *
+ * <p>Call {@link #count(long)} on the returned word to find out how many
integers were consumed.
+ *
+ * <p>NOTE: a selector is only accepted when <em>all</em> {@code
Math.min(COUNTS[selector],
+ * length)} values fit its bit-width, so that {@link #count(long)} always
returns the correct
+ * number of consumed integers. The exception is the last encoded long,
where {@code length <
+ * COUNTS[selector]} leaves it partially filled and {@link #count(long)}
over-reports; this is
+ * harmless because {@link #encodeAll} terminates immediately after.
+ *
+ * @param ints source array of non-negative integers
+ * @param offset start index
+ * @param length number of integers available from {@code offset}
+ * @return encoded long
+ */
+ public static long encode(int[] ints, int offset, int length) {
+ if (length <= 0) {
+ throw new IllegalArgumentException("length must be > 0; got " + length);
+ }
+
+ final int limit = Math.min(COUNTS[0], length);
+ long prefixOr = 0L;
+ int fitMask = 0;
+
+ for (int i = 1; i <= limit; i++) {
+ final int v = ints[offset + i - 1];
+ if (v < 0) {
+ throw new IllegalArgumentException("Simple64 does not support negative
values, got: " + v);
+ }
+ prefixOr |= v;
+ final int bits = bitsRequired(prefixOr);
+
+ switch (i) {
+ case 1 -> fitMask |= 1 << 13;
+ case 2 -> {
+ if (bits <= 30) fitMask |= 1 << 12;
+ }
+ case 3 -> {
+ if (bits <= 20) fitMask |= 1 << 11;
+ }
+ case 4 -> {
+ if (bits <= 15) fitMask |= 1 << 10;
+ }
+ case 5 -> {
+ if (bits <= 12) fitMask |= 1 << 9;
+ }
+ case 6 -> {
+ if (bits <= 10) fitMask |= 1 << 8;
+ }
+ case 7 -> {
+ if (bits <= 8) fitMask |= 1 << 7;
+ }
+ case 8 -> {
+ if (bits <= 7) fitMask |= 1 << 6;
+ }
+ case 10 -> {
+ if (bits <= 6) fitMask |= 1 << 5;
+ }
+ case 12 -> {
+ if (bits <= 5) fitMask |= 1 << 4;
+ }
+ case 15 -> {
+ if (length >= 15 && bits == 4) {
+ return pack15x4(ints, offset);
+ }
+ if (bits <= 4) fitMask |= 1 << 3;
+ }
+ case 20 -> {
+ if (length >= 20 && bits == 3) {
+ return pack20x3(ints, offset);
+ }
+ if (bits <= 3) fitMask |= 1 << 2;
+ }
+ case 30 -> {
+ if (length >= 30 && bits == 2) {
+ return pack30x2(ints, offset);
+ }
+ if (bits <= 2) fitMask |= 1 << 1;
+ }
+ case 60 -> {
+ if (bits == 1) {
+ return pack60x1(ints, offset);
+ }
+ if (bits <= 1) fitMask |= 1;
+ }
+ default -> {}
+ }
+ }
+
+ final int bits = bitsRequired(prefixOr);
+ for (int s = 0; s < 14; s++) {
+ final int count = COUNTS[s];
+ if (count >= length) {
+ if (bits <= BITS[s]) {
+ return pack(s, ints, offset, length);
+ }
+ } else if ((fitMask & (1 << s)) != 0) {
+ return pack(s, ints, offset, count);
+ }
+ }
+
+ // Unreachable: selector 13 covers all non-negative int values (up to
2^31-1).
+ throw new AssertionError("unreachable");
+ }
+
+ /** Pack {@code count} integers using the given selector (low-to-high bit
order). */
+ public static long pack(int selector, int[] ints, int offset, int count) {
+ if (count == COUNTS[selector]) {
+ switch (selector) {
+ case 0:
+ return pack60x1(ints, offset);
+ case 1:
+ return pack30x2(ints, offset);
+ case 2:
+ return pack20x3(ints, offset);
+ case 3:
+ return pack15x4(ints, offset);
+ case 4:
+ return pack12x5(ints, offset);
+ case 5:
+ return pack10x6(ints, offset);
+ case 6:
+ return pack8x7(ints, offset);
+ case 7:
+ return pack7x8(ints, offset);
+ case 8:
+ return pack6x10(ints, offset);
+ case 9:
+ return pack5x12(ints, offset);
+ case 10:
+ return pack4x15(ints, offset);
+ case 11:
+ return pack3x20(ints, offset);
+ case 12:
+ return pack2x30(ints, offset);
+ case 13:
+ return pack1x31(ints, offset);
+ default:
+ break;
+ }
+ }
+
+ final int bits = BITS[selector];
+ long word = (long) selector << 60;
+ for (int i = 0; i < count; i++) {
+ word |= ((long) ints[offset + i]) << (i * bits);
+ }
+ return word;
+ }
+
+ /**
+ * Decode all integers packed in {@code word} into {@code out[outOffset..]}.
+ *
+ * @return number of integers written
+ */
+ public static int decode(long word, int[] out, int outOffset) {
+ final int selector = selector(word);
+ final int count = COUNTS[selector];
+ decodeValues(word, selector, out, outOffset, count);
+ return count;
+ }
+
+ /** Return the number of integers packed in {@code word} without fully
decoding it. */
+ public static int count(long word) {
+ return COUNTS[selector(word)];
+ }
+
+ /**
+ * Encode all {@code length} integers from {@code
ints[offset..offset+length)} into consecutive
+ * longs in {@code out}, starting at {@code out[outOffset]}.
+ *
+ * @return number of longs written
+ */
+ public static int encodeAll(int[] ints, int offset, int length, long[] out,
int outOffset) {
+ int inPos = offset;
+ int outPos = outOffset;
+ final int end = offset + length;
+ while (inPos < end) {
+ long word = encode(ints, inPos, end - inPos);
+ out[outPos++] = word;
+ inPos += count(word);
+ }
+ return outPos - outOffset;
+ }
+
+ /**
+ * Decode exactly {@code count} integers from {@code longs[offset..)} into
{@code out}.
+ *
+ * <p>The caller must supply the original integer count (e.g. stored as a
preceding VInt), because
+ * the last packed long may contain more slots than remaining integers.
+ *
+ * @return number of longs consumed
+ */
+ public static int decodeAll(long[] longs, int offset, int[] out, int
outOffset, int count) {
+ int inPos = offset;
+ int remaining = count;
+ while (remaining > 0) {
+ long word = longs[inPos++];
+ final int selector = selector(word);
+ final int toRead = Math.min(COUNTS[selector], remaining);
+ decodeValues(word, selector, out, outOffset, toRead);
Review Comment:
Maybe `decodeOneLong`?
##########
lucene/core/src/java/org/apache/lucene/util/Simple64.java:
##########
@@ -0,0 +1,828 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util;
+
+/**
+ * Simple64: pack multiple small non-negative integers into a single long.
+ *
+ * <p>The high 4 bits of each long are a selector that encodes the bit-width
and count of the packed
+ * integers. The remaining 60 bits hold the actual values, packed from LSB to
MSB.
+ *
+ * <p>Designed for {@code int} values (non-negative, max {@link
Integer#MAX_VALUE} = 2^31 - 1).
+ *
+ * <p>Selector table (14 schemes, selectors 14-15 reserved):
+ *
+ * <pre>
+ * selector | integers | bits each | max value
+ * ---------+----------+-----------+--------------------
+ * 0 | 60 | 1 | 1
+ * 1 | 30 | 2 | 3
+ * 2 | 20 | 3 | 7
+ * 3 | 15 | 4 | 15
+ * 4 | 12 | 5 | 31
+ * 5 | 10 | 6 | 63
+ * 6 | 8 | 7 | 127
+ * 7 | 7 | 8 | 255
+ * 8 | 6 | 10 | 1023
+ * 9 | 5 | 12 | 4095
+ * 10 | 4 | 15 | 32767
+ * 11 | 3 | 20 | 1048575
+ * 12 | 2 | 30 | 1073741823
+ * 13 | 1 | 31 | 2147483647 (Integer.MAX_VALUE)
+ * </pre>
+ *
+ * <p>Every selector has a hand-unrolled pack/decode pair (e.g. {@link
#pack8x7} / {@link
+ * #decode8x7}) used whenever a word is completely full for that selector,
avoiding the generic
+ * shift-loop in {@link #unpack} for the common case.
+ */
+public final class Simple64 {
+ /** Number of integers each selector can pack. */
+ public static final int[] COUNTS = {60, 30, 20, 15, 12, 10, 8, 7, 6, 5, 4,
3, 2, 1};
+
+ /** Bit-width per integer for each selector. */
+ public static final int[] BITS = {1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15, 20,
30, 31};
+
+ /** Bit-mask for extracting one value under each selector. */
+ public static final long[] MASKS = new long[14];
+
+ static {
+ for (int s = 0; s < 14; s++) {
+ MASKS[s] = (1L << BITS[s]) - 1L;
+ }
+ }
+
+ private Simple64() {}
+
+ /**
+ * Encode as many integers from {@code ints[offset..]} as fit into a single
long, using the
+ * most-compact selector whose bit-width can represent every value.
+ *
+ * <p>Call {@link #count(long)} on the returned word to find out how many
integers were consumed.
+ *
+ * <p>NOTE: a selector is only accepted when <em>all</em> {@code
Math.min(COUNTS[selector],
+ * length)} values fit its bit-width, so that {@link #count(long)} always
returns the correct
+ * number of consumed integers. The exception is the last encoded long,
where {@code length <
+ * COUNTS[selector]} leaves it partially filled and {@link #count(long)}
over-reports; this is
+ * harmless because {@link #encodeAll} terminates immediately after.
+ *
+ * @param ints source array of non-negative integers
+ * @param offset start index
+ * @param length number of integers available from {@code offset}
+ * @return encoded long
+ */
+ public static long encode(int[] ints, int offset, int length) {
+ if (length <= 0) {
+ throw new IllegalArgumentException("length must be > 0; got " + length);
+ }
+
+ final int limit = Math.min(COUNTS[0], length);
+ long prefixOr = 0L;
+ int fitMask = 0;
+
+ for (int i = 1; i <= limit; i++) {
+ final int v = ints[offset + i - 1];
Review Comment:
We don't need all the `final` in local vars?
##########
lucene/core/src/java/org/apache/lucene/util/Simple64.java:
##########
@@ -0,0 +1,828 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util;
+
+/**
+ * Simple64: pack multiple small non-negative integers into a single long.
+ *
+ * <p>The high 4 bits of each long are a selector that encodes the bit-width
and count of the packed
+ * integers. The remaining 60 bits hold the actual values, packed from LSB to
MSB.
+ *
+ * <p>Designed for {@code int} values (non-negative, max {@link
Integer#MAX_VALUE} = 2^31 - 1).
+ *
+ * <p>Selector table (14 schemes, selectors 14-15 reserved):
+ *
+ * <pre>
+ * selector | integers | bits each | max value
+ * ---------+----------+-----------+--------------------
+ * 0 | 60 | 1 | 1
+ * 1 | 30 | 2 | 3
+ * 2 | 20 | 3 | 7
+ * 3 | 15 | 4 | 15
+ * 4 | 12 | 5 | 31
+ * 5 | 10 | 6 | 63
+ * 6 | 8 | 7 | 127
+ * 7 | 7 | 8 | 255
+ * 8 | 6 | 10 | 1023
+ * 9 | 5 | 12 | 4095
+ * 10 | 4 | 15 | 32767
+ * 11 | 3 | 20 | 1048575
+ * 12 | 2 | 30 | 1073741823
+ * 13 | 1 | 31 | 2147483647 (Integer.MAX_VALUE)
+ * </pre>
+ *
+ * <p>Every selector has a hand-unrolled pack/decode pair (e.g. {@link
#pack8x7} / {@link
+ * #decode8x7}) used whenever a word is completely full for that selector,
avoiding the generic
+ * shift-loop in {@link #unpack} for the common case.
+ */
+public final class Simple64 {
+ /** Number of integers each selector can pack. */
+ public static final int[] COUNTS = {60, 30, 20, 15, 12, 10, 8, 7, 6, 5, 4,
3, 2, 1};
+
+ /** Bit-width per integer for each selector. */
+ public static final int[] BITS = {1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15, 20,
30, 31};
+
+ /** Bit-mask for extracting one value under each selector. */
+ public static final long[] MASKS = new long[14];
+
+ static {
+ for (int s = 0; s < 14; s++) {
+ MASKS[s] = (1L << BITS[s]) - 1L;
+ }
+ }
+
+ private Simple64() {}
+
+ /**
+ * Encode as many integers from {@code ints[offset..]} as fit into a single
long, using the
+ * most-compact selector whose bit-width can represent every value.
+ *
+ * <p>Call {@link #count(long)} on the returned word to find out how many
integers were consumed.
+ *
+ * <p>NOTE: a selector is only accepted when <em>all</em> {@code
Math.min(COUNTS[selector],
+ * length)} values fit its bit-width, so that {@link #count(long)} always
returns the correct
+ * number of consumed integers. The exception is the last encoded long,
where {@code length <
+ * COUNTS[selector]} leaves it partially filled and {@link #count(long)}
over-reports; this is
+ * harmless because {@link #encodeAll} terminates immediately after.
+ *
+ * @param ints source array of non-negative integers
+ * @param offset start index
+ * @param length number of integers available from {@code offset}
+ * @return encoded long
+ */
+ public static long encode(int[] ints, int offset, int length) {
+ if (length <= 0) {
+ throw new IllegalArgumentException("length must be > 0; got " + length);
+ }
+
+ final int limit = Math.min(COUNTS[0], length);
+ long prefixOr = 0L;
+ int fitMask = 0;
+
+ for (int i = 1; i <= limit; i++) {
+ final int v = ints[offset + i - 1];
+ if (v < 0) {
+ throw new IllegalArgumentException("Simple64 does not support negative
values, got: " + v);
+ }
+ prefixOr |= v;
+ final int bits = bitsRequired(prefixOr);
+
+ switch (i) {
+ case 1 -> fitMask |= 1 << 13;
+ case 2 -> {
+ if (bits <= 30) fitMask |= 1 << 12;
+ }
+ case 3 -> {
+ if (bits <= 20) fitMask |= 1 << 11;
+ }
+ case 4 -> {
+ if (bits <= 15) fitMask |= 1 << 10;
+ }
+ case 5 -> {
+ if (bits <= 12) fitMask |= 1 << 9;
+ }
+ case 6 -> {
+ if (bits <= 10) fitMask |= 1 << 8;
+ }
+ case 7 -> {
+ if (bits <= 8) fitMask |= 1 << 7;
+ }
+ case 8 -> {
+ if (bits <= 7) fitMask |= 1 << 6;
+ }
+ case 10 -> {
+ if (bits <= 6) fitMask |= 1 << 5;
+ }
+ case 12 -> {
+ if (bits <= 5) fitMask |= 1 << 4;
+ }
+ case 15 -> {
+ if (length >= 15 && bits == 4) {
+ return pack15x4(ints, offset);
+ }
+ if (bits <= 4) fitMask |= 1 << 3;
+ }
+ case 20 -> {
+ if (length >= 20 && bits == 3) {
+ return pack20x3(ints, offset);
+ }
+ if (bits <= 3) fitMask |= 1 << 2;
+ }
+ case 30 -> {
+ if (length >= 30 && bits == 2) {
+ return pack30x2(ints, offset);
+ }
+ if (bits <= 2) fitMask |= 1 << 1;
+ }
+ case 60 -> {
+ if (bits == 1) {
+ return pack60x1(ints, offset);
+ }
+ if (bits <= 1) fitMask |= 1;
+ }
+ default -> {}
+ }
+ }
+
+ final int bits = bitsRequired(prefixOr);
+ for (int s = 0; s < 14; s++) {
+ final int count = COUNTS[s];
+ if (count >= length) {
+ if (bits <= BITS[s]) {
+ return pack(s, ints, offset, length);
+ }
+ } else if ((fitMask & (1 << s)) != 0) {
+ return pack(s, ints, offset, count);
+ }
+ }
+
+ // Unreachable: selector 13 covers all non-negative int values (up to
2^31-1).
+ throw new AssertionError("unreachable");
+ }
+
+ /** Pack {@code count} integers using the given selector (low-to-high bit
order). */
+ public static long pack(int selector, int[] ints, int offset, int count) {
+ if (count == COUNTS[selector]) {
+ switch (selector) {
+ case 0:
+ return pack60x1(ints, offset);
+ case 1:
+ return pack30x2(ints, offset);
+ case 2:
+ return pack20x3(ints, offset);
+ case 3:
+ return pack15x4(ints, offset);
+ case 4:
+ return pack12x5(ints, offset);
+ case 5:
+ return pack10x6(ints, offset);
+ case 6:
+ return pack8x7(ints, offset);
+ case 7:
+ return pack7x8(ints, offset);
+ case 8:
+ return pack6x10(ints, offset);
+ case 9:
+ return pack5x12(ints, offset);
+ case 10:
+ return pack4x15(ints, offset);
+ case 11:
+ return pack3x20(ints, offset);
+ case 12:
+ return pack2x30(ints, offset);
+ case 13:
+ return pack1x31(ints, offset);
+ default:
+ break;
+ }
+ }
+
+ final int bits = BITS[selector];
+ long word = (long) selector << 60;
+ for (int i = 0; i < count; i++) {
+ word |= ((long) ints[offset + i]) << (i * bits);
+ }
+ return word;
+ }
+
+ /**
+ * Decode all integers packed in {@code word} into {@code out[outOffset..]}.
+ *
+ * @return number of integers written
+ */
+ public static int decode(long word, int[] out, int outOffset) {
Review Comment:
`decodeOneLong`?
##########
lucene/core/src/java/org/apache/lucene/util/Simple64.java:
##########
@@ -0,0 +1,828 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util;
+
+/**
+ * Simple64: pack multiple small non-negative integers into a single long.
+ *
+ * <p>The high 4 bits of each long are a selector that encodes the bit-width
and count of the packed
+ * integers. The remaining 60 bits hold the actual values, packed from LSB to
MSB.
+ *
+ * <p>Designed for {@code int} values (non-negative, max {@link
Integer#MAX_VALUE} = 2^31 - 1).
+ *
+ * <p>Selector table (14 schemes, selectors 14-15 reserved):
+ *
+ * <pre>
+ * selector | integers | bits each | max value
+ * ---------+----------+-----------+--------------------
+ * 0 | 60 | 1 | 1
+ * 1 | 30 | 2 | 3
+ * 2 | 20 | 3 | 7
+ * 3 | 15 | 4 | 15
+ * 4 | 12 | 5 | 31
+ * 5 | 10 | 6 | 63
+ * 6 | 8 | 7 | 127
+ * 7 | 7 | 8 | 255
+ * 8 | 6 | 10 | 1023
+ * 9 | 5 | 12 | 4095
+ * 10 | 4 | 15 | 32767
+ * 11 | 3 | 20 | 1048575
+ * 12 | 2 | 30 | 1073741823
+ * 13 | 1 | 31 | 2147483647 (Integer.MAX_VALUE)
+ * </pre>
+ *
+ * <p>Every selector has a hand-unrolled pack/decode pair (e.g. {@link
#pack8x7} / {@link
+ * #decode8x7}) used whenever a word is completely full for that selector,
avoiding the generic
+ * shift-loop in {@link #unpack} for the common case.
+ */
+public final class Simple64 {
+ /** Number of integers each selector can pack. */
+ public static final int[] COUNTS = {60, 30, 20, 15, 12, 10, 8, 7, 6, 5, 4,
3, 2, 1};
+
+ /** Bit-width per integer for each selector. */
+ public static final int[] BITS = {1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15, 20,
30, 31};
+
+ /** Bit-mask for extracting one value under each selector. */
+ public static final long[] MASKS = new long[14];
+
+ static {
+ for (int s = 0; s < 14; s++) {
+ MASKS[s] = (1L << BITS[s]) - 1L;
+ }
+ }
+
+ private Simple64() {}
+
+ /**
+ * Encode as many integers from {@code ints[offset..]} as fit into a single
long, using the
+ * most-compact selector whose bit-width can represent every value.
+ *
+ * <p>Call {@link #count(long)} on the returned word to find out how many
integers were consumed.
+ *
+ * <p>NOTE: a selector is only accepted when <em>all</em> {@code
Math.min(COUNTS[selector],
+ * length)} values fit its bit-width, so that {@link #count(long)} always
returns the correct
+ * number of consumed integers. The exception is the last encoded long,
where {@code length <
+ * COUNTS[selector]} leaves it partially filled and {@link #count(long)}
over-reports; this is
+ * harmless because {@link #encodeAll} terminates immediately after.
+ *
+ * @param ints source array of non-negative integers
+ * @param offset start index
+ * @param length number of integers available from {@code offset}
+ * @return encoded long
+ */
+ public static long encode(int[] ints, int offset, int length) {
Review Comment:
`encodeOneLong` maybe?
##########
lucene/core/src/java/org/apache/lucene/util/Simple64.java:
##########
@@ -0,0 +1,828 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util;
+
+/**
+ * Simple64: pack multiple small non-negative integers into a single long.
+ *
+ * <p>The high 4 bits of each long are a selector that encodes the bit-width
and count of the packed
+ * integers. The remaining 60 bits hold the actual values, packed from LSB to
MSB.
+ *
+ * <p>Designed for {@code int} values (non-negative, max {@link
Integer#MAX_VALUE} = 2^31 - 1).
+ *
+ * <p>Selector table (14 schemes, selectors 14-15 reserved):
+ *
+ * <pre>
+ * selector | integers | bits each | max value
+ * ---------+----------+-----------+--------------------
+ * 0 | 60 | 1 | 1
+ * 1 | 30 | 2 | 3
+ * 2 | 20 | 3 | 7
+ * 3 | 15 | 4 | 15
+ * 4 | 12 | 5 | 31
+ * 5 | 10 | 6 | 63
+ * 6 | 8 | 7 | 127
+ * 7 | 7 | 8 | 255
+ * 8 | 6 | 10 | 1023
+ * 9 | 5 | 12 | 4095
+ * 10 | 4 | 15 | 32767
+ * 11 | 3 | 20 | 1048575
+ * 12 | 2 | 30 | 1073741823
+ * 13 | 1 | 31 | 2147483647 (Integer.MAX_VALUE)
+ * </pre>
+ *
+ * <p>Every selector has a hand-unrolled pack/decode pair (e.g. {@link
#pack8x7} / {@link
+ * #decode8x7}) used whenever a word is completely full for that selector,
avoiding the generic
+ * shift-loop in {@link #unpack} for the common case.
+ */
+public final class Simple64 {
+ /** Number of integers each selector can pack. */
+ public static final int[] COUNTS = {60, 30, 20, 15, 12, 10, 8, 7, 6, 5, 4,
3, 2, 1};
+
+ /** Bit-width per integer for each selector. */
+ public static final int[] BITS = {1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15, 20,
30, 31};
+
+ /** Bit-mask for extracting one value under each selector. */
+ public static final long[] MASKS = new long[14];
+
+ static {
+ for (int s = 0; s < 14; s++) {
+ MASKS[s] = (1L << BITS[s]) - 1L;
+ }
+ }
+
+ private Simple64() {}
+
+ /**
+ * Encode as many integers from {@code ints[offset..]} as fit into a single
long, using the
+ * most-compact selector whose bit-width can represent every value.
+ *
+ * <p>Call {@link #count(long)} on the returned word to find out how many
integers were consumed.
+ *
+ * <p>NOTE: a selector is only accepted when <em>all</em> {@code
Math.min(COUNTS[selector],
+ * length)} values fit its bit-width, so that {@link #count(long)} always
returns the correct
+ * number of consumed integers. The exception is the last encoded long,
where {@code length <
+ * COUNTS[selector]} leaves it partially filled and {@link #count(long)}
over-reports; this is
+ * harmless because {@link #encodeAll} terminates immediately after.
+ *
+ * @param ints source array of non-negative integers
+ * @param offset start index
+ * @param length number of integers available from {@code offset}
+ * @return encoded long
+ */
+ public static long encode(int[] ints, int offset, int length) {
+ if (length <= 0) {
+ throw new IllegalArgumentException("length must be > 0; got " + length);
+ }
+
+ final int limit = Math.min(COUNTS[0], length);
+ long prefixOr = 0L;
+ int fitMask = 0;
+
+ for (int i = 1; i <= limit; i++) {
+ final int v = ints[offset + i - 1];
+ if (v < 0) {
+ throw new IllegalArgumentException("Simple64 does not support negative
values, got: " + v);
+ }
+ prefixOr |= v;
+ final int bits = bitsRequired(prefixOr);
+
+ switch (i) {
+ case 1 -> fitMask |= 1 << 13;
+ case 2 -> {
+ if (bits <= 30) fitMask |= 1 << 12;
+ }
+ case 3 -> {
+ if (bits <= 20) fitMask |= 1 << 11;
+ }
+ case 4 -> {
+ if (bits <= 15) fitMask |= 1 << 10;
+ }
+ case 5 -> {
+ if (bits <= 12) fitMask |= 1 << 9;
+ }
+ case 6 -> {
+ if (bits <= 10) fitMask |= 1 << 8;
+ }
+ case 7 -> {
+ if (bits <= 8) fitMask |= 1 << 7;
+ }
+ case 8 -> {
+ if (bits <= 7) fitMask |= 1 << 6;
+ }
+ case 10 -> {
+ if (bits <= 6) fitMask |= 1 << 5;
+ }
+ case 12 -> {
+ if (bits <= 5) fitMask |= 1 << 4;
+ }
+ case 15 -> {
+ if (length >= 15 && bits == 4) {
+ return pack15x4(ints, offset);
+ }
+ if (bits <= 4) fitMask |= 1 << 3;
+ }
+ case 20 -> {
+ if (length >= 20 && bits == 3) {
+ return pack20x3(ints, offset);
+ }
+ if (bits <= 3) fitMask |= 1 << 2;
+ }
+ case 30 -> {
+ if (length >= 30 && bits == 2) {
+ return pack30x2(ints, offset);
+ }
+ if (bits <= 2) fitMask |= 1 << 1;
+ }
+ case 60 -> {
+ if (bits == 1) {
+ return pack60x1(ints, offset);
+ }
+ if (bits <= 1) fitMask |= 1;
+ }
+ default -> {}
+ }
+ }
+
+ final int bits = bitsRequired(prefixOr);
+ for (int s = 0; s < 14; s++) {
+ final int count = COUNTS[s];
+ if (count >= length) {
+ if (bits <= BITS[s]) {
+ return pack(s, ints, offset, length);
+ }
+ } else if ((fitMask & (1 << s)) != 0) {
+ return pack(s, ints, offset, count);
+ }
+ }
+
+ // Unreachable: selector 13 covers all non-negative int values (up to
2^31-1).
+ throw new AssertionError("unreachable");
+ }
+
+ /** Pack {@code count} integers using the given selector (low-to-high bit
order). */
+ public static long pack(int selector, int[] ints, int offset, int count) {
Review Comment:
`packOneLong` maybe?
Should this be [package] private? Shouldn't outside callers use
`encodeOneLong`?
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/blocktree/SegmentTermsEnumFrame.java:
##########
@@ -209,15 +213,32 @@ void loadBlock() throws IOException {
int numSuffixLengthBytes = ste.in.readVInt();
allEqual = (numSuffixLengthBytes & 0x01) != 0;
numSuffixLengthBytes >>>= 1;
- if (suffixLengthBytes == null || suffixLengthBytes.length <
numSuffixLengthBytes) {
- suffixLengthBytes = new byte[ArrayUtil.oversize(numSuffixLengthBytes,
1)];
- }
- if (allEqual) {
- Arrays.fill(suffixLengthBytes, 0, numSuffixLengthBytes,
ste.in.readByte());
+
+ if (isLeafBlock) {
+ if (allEqual) {
+ suffixLength = numSuffixLengthBytes;
+ } else {
+ final int numLongs = numSuffixLengthBytes;
+ suffixLengths = new int[entCount];
+ long[] longs = new long[numLongs];
+ for (int i = 0; i < numLongs; i++) {
Review Comment:
Also surprising Lucene doesn't already have sugar `readLongs`.
##########
lucene/core/src/test/org/apache/lucene/util/TestSimple64.java:
##########
@@ -0,0 +1,208 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util;
+
+import static org.apache.lucene.util.Simple64.BITS;
+import static org.apache.lucene.util.Simple64.COUNTS;
+import static org.apache.lucene.util.Simple64.MASKS;
+
+import java.util.Arrays;
+import java.util.Random;
+import org.apache.lucene.tests.util.LuceneTestCase;
+
+public class TestSimple64 extends LuceneTestCase {
+
+ /** Verify selector table invariants. */
+ public void testSelectorTable() {
+ for (int s = 0; s < 14; s++) {
+ // bits must fit inside the 60 data bits
+ assertTrue("selector " + s + ": COUNTS[s]*BITS[s] <= 60", (long)
COUNTS[s] * BITS[s] <= 60);
+ // max value must be representable as a non-negative int
+ assertTrue(
+ "selector " + s + ": MASKS[s] <= Integer.MAX_VALUE", MASKS[s] <=
Integer.MAX_VALUE);
+ }
+ // selector 13 must cover Integer.MAX_VALUE
+ assertTrue("selector 13 covers Integer.MAX_VALUE", MASKS[13] >=
Integer.MAX_VALUE);
+ }
+
+ /** Each selector should be chosen when values exactly hit its upper bound.
*/
+ public void testSelectorBoundaries() {
+ for (int s = 0; s < 14; s++) {
+ int maxVal = (int) MASKS[s];
+ int[] input = new int[COUNTS[s]];
+ Arrays.fill(input, maxVal);
+ long word = Simple64.encode(input, 0, input.length);
+ assertEquals("selector for bits=" + BITS[s], s, (int) (word >>> 60));
+ }
+ }
+
+ public void testRoundtripSmallValues() {
+ // value=2 needs 2 bits → selector 1 (30 × 2 bits)
+ int[] input = new int[30];
+ Arrays.fill(input, 2);
+ long word = Simple64.encode(input, 0, 30);
+ assertEquals("selector=1 for value=2", 1, (int) (word >>> 60));
+ int[] out = new int[30];
+ assertEquals("decoded count", 30, Simple64.decode(word, out, 0));
+ assertArrayEquals("decoded values", input, out);
+ }
+
+ public void testRoundtripAllSelectors() {
+ for (int s = 0; s < 14; s++) {
+ int count = COUNTS[s];
+ int maxVal = (int) MASKS[s];
+ int[] input = new int[count];
+ Arrays.fill(input, maxVal);
+ long word = Simple64.pack(s, input, 0, count); // force this selector
+ int[] out = new int[count];
+ assertEquals("selector " + s + " decode count", count,
Simple64.decode(word, out, 0));
+ assertArrayEquals("selector " + s + " values", input, out);
+ }
+ }
+
+ public void testFastPathParitySelectors0To3() {
+ Random rng = new Random(7);
+ for (int s = 0; s <= 3; s++) {
+ int[] input = new int[COUNTS[s]];
+ int maxVal = (int) MASKS[s];
+ for (int i = 0; i < input.length; i++) {
+ input[i] = rng.nextInt(maxVal + 1);
+ }
+ assertEquals(
+ "selector " + s + " fast-path word",
+ Simple64.pack(s, input, 0, input.length),
+ Simple64.encode(input, 0, input.length));
+ }
+ }
+
+ /** Selector 13 must handle Integer.MAX_VALUE. */
+ public void testIntegerMaxValue() {
+ int[] input = {Integer.MAX_VALUE};
+ long word = Simple64.encode(input, 0, 1);
+ assertEquals("selector=13 for Integer.MAX_VALUE", 13, (int) (word >>> 60));
+ int[] out = new int[1];
+ Simple64.decode(word, out, 0);
+ assertEquals("decoded Integer.MAX_VALUE", Integer.MAX_VALUE, out[0]);
+ }
+
+ public void testEncodeAll() {
+ int[] input = new int[35];
+ Random rng = new Random(42);
+ for (int i = 0; i < 35; i++) input[i] = rng.nextInt(10) + 1;
+ long[] longs = new long[35];
+ int numLongs = Simple64.encodeAll(input, 0, 35, longs, 0);
+ if (numLongs < longs.length) {
+ assert longs[numLongs] == 0;
+ }
+ int[] decoded = new int[35];
+ Simple64.decodeAll(longs, 0, decoded, 0, 35);
+ assertArrayEquals("encodeAll roundtrip", input, decoded);
+ }
+
+ public void testEncodeAllAndDecodeAllWithOffsets() {
+ int[] input = {7, 2, 6, 6, 5, 1, 8, 2, 7, 2, 3, 4, 5, 6, 7, 8, 9};
+ long[] longs = new long[input.length + 4];
+ Arrays.fill(longs, -1L);
+ int numLongs = Simple64.encodeAll(input, 0, input.length, longs, 2);
+ assertEquals(-1L, longs[1]);
+ if (numLongs + 2 < longs.length) {
+ assertEquals(-1L, longs[numLongs + 2]);
+ }
+
+ int[] decoded = new int[input.length + 6];
+ Arrays.fill(decoded, -1);
+ int consumed = Simple64.decodeAll(longs, 2, decoded, 3, input.length);
+ assertEquals(numLongs, consumed);
+ assertEquals(-1, decoded[2]);
+ assertEquals(-1, decoded[input.length + 3]);
+ assertArrayEquals(input, Arrays.copyOfRange(decoded, 3, 3 + input.length));
+ }
+
+ public void testDecodeWithOutOffset() {
+ int[] input = new int[COUNTS[3]];
+ Arrays.fill(input, 8);
+ long word = Simple64.encode(input, 0, input.length);
+ int[] out = new int[input.length + 4];
+ Arrays.fill(out, -1);
+ assertEquals(input.length, Simple64.decode(word, out, 2));
+ assertEquals(-1, out[1]);
+ assertEquals(-1, out[input.length + 2]);
+ assertArrayEquals(input, Arrays.copyOfRange(out, 2, 2 + input.length));
+ }
+
+ public void testSuffixLengths() {
+ int[] input = {
+ 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4,
3, 3, 8, 3
+ };
+ int len = input.length;
+ long[] longs = new long[len];
+ int numLongs = Simple64.encodeAll(input, 0, len, longs, 0);
+ if (numLongs < longs.length) {
+ assert longs[numLongs] == 0;
+ }
+ int[] decoded = new int[len];
+ Simple64.decodeAll(longs, 0, decoded, 0, len);
+ assertArrayEquals("suffix roundtrip", input, decoded);
+ }
+
+ public void testCountWithoutDecode() {
+ // value=63 needs 6 bits → selector 5 (10 × 6 bits)
+ int[] input = new int[10];
+ Arrays.fill(input, 63);
+ long word = Simple64.encode(input, 0, 10);
+ assertEquals("selector=5 for value=63", 5, (int) (word >>> 60));
+ assertEquals("count()==10", 10, Simple64.count(word));
+ }
+
+ public void testInvalidInputs() {
+ expectThrows(IllegalArgumentException.class, () -> Simple64.encode(new
int[1], 0, 0));
+ expectThrows(IllegalArgumentException.class, () -> Simple64.encode(new
int[] {-1}, 0, 1));
+
+ long invalidSelector = 14L << 60;
+ expectThrows(IllegalArgumentException.class, () ->
Simple64.count(invalidSelector));
+ expectThrows(
+ IllegalArgumentException.class, () -> Simple64.decode(invalidSelector,
new int[1], 0));
+ expectThrows(
+ IllegalArgumentException.class,
+ () -> Simple64.decodeAll(new long[] {invalidSelector}, 0, new int[1],
0, 1));
+ }
+
+ public void testFuzz() {
+ Random rng = new Random(12345);
+ int rounds = 20_000;
Review Comment:
We can make this larger if `TESTS_NIGHTLY`? We have sugar "next random int"
methods that do that in LTC somewhere I think?
##########
lucene/core/src/java/org/apache/lucene/util/Simple64.java:
##########
@@ -0,0 +1,828 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util;
+
+/**
+ * Simple64: pack multiple small non-negative integers into a single long.
+ *
+ * <p>The high 4 bits of each long are a selector that encodes the bit-width
and count of the packed
+ * integers. The remaining 60 bits hold the actual values, packed from LSB to
MSB.
+ *
+ * <p>Designed for {@code int} values (non-negative, max {@link
Integer#MAX_VALUE} = 2^31 - 1).
+ *
+ * <p>Selector table (14 schemes, selectors 14-15 reserved):
+ *
+ * <pre>
+ * selector | integers | bits each | max value
+ * ---------+----------+-----------+--------------------
+ * 0 | 60 | 1 | 1
+ * 1 | 30 | 2 | 3
+ * 2 | 20 | 3 | 7
+ * 3 | 15 | 4 | 15
+ * 4 | 12 | 5 | 31
+ * 5 | 10 | 6 | 63
+ * 6 | 8 | 7 | 127
+ * 7 | 7 | 8 | 255
+ * 8 | 6 | 10 | 1023
+ * 9 | 5 | 12 | 4095
+ * 10 | 4 | 15 | 32767
+ * 11 | 3 | 20 | 1048575
+ * 12 | 2 | 30 | 1073741823
+ * 13 | 1 | 31 | 2147483647 (Integer.MAX_VALUE)
+ * </pre>
+ *
+ * <p>Every selector has a hand-unrolled pack/decode pair (e.g. {@link
#pack8x7} / {@link
+ * #decode8x7}) used whenever a word is completely full for that selector,
avoiding the generic
+ * shift-loop in {@link #unpack} for the common case.
+ */
+public final class Simple64 {
+ /** Number of integers each selector can pack. */
+ public static final int[] COUNTS = {60, 30, 20, 15, 12, 10, 8, 7, 6, 5, 4,
3, 2, 1};
+
+ /** Bit-width per integer for each selector. */
+ public static final int[] BITS = {1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15, 20,
30, 31};
+
+ /** Bit-mask for extracting one value under each selector. */
+ public static final long[] MASKS = new long[14];
+
+ static {
+ for (int s = 0; s < 14; s++) {
+ MASKS[s] = (1L << BITS[s]) - 1L;
+ }
+ }
+
+ private Simple64() {}
+
+ /**
+ * Encode as many integers from {@code ints[offset..]} as fit into a single
long, using the
+ * most-compact selector whose bit-width can represent every value.
+ *
+ * <p>Call {@link #count(long)} on the returned word to find out how many
integers were consumed.
+ *
+ * <p>NOTE: a selector is only accepted when <em>all</em> {@code
Math.min(COUNTS[selector],
+ * length)} values fit its bit-width, so that {@link #count(long)} always
returns the correct
+ * number of consumed integers. The exception is the last encoded long,
where {@code length <
+ * COUNTS[selector]} leaves it partially filled and {@link #count(long)}
over-reports; this is
+ * harmless because {@link #encodeAll} terminates immediately after.
+ *
+ * @param ints source array of non-negative integers
+ * @param offset start index
+ * @param length number of integers available from {@code offset}
+ * @return encoded long
+ */
+ public static long encode(int[] ints, int offset, int length) {
+ if (length <= 0) {
+ throw new IllegalArgumentException("length must be > 0; got " + length);
+ }
+
+ final int limit = Math.min(COUNTS[0], length);
+ long prefixOr = 0L;
+ int fitMask = 0;
+
+ for (int i = 1; i <= limit; i++) {
+ final int v = ints[offset + i - 1];
+ if (v < 0) {
+ throw new IllegalArgumentException("Simple64 does not support negative
values, got: " + v);
+ }
+ prefixOr |= v;
+ final int bits = bitsRequired(prefixOr);
+
+ switch (i) {
+ case 1 -> fitMask |= 1 << 13;
+ case 2 -> {
+ if (bits <= 30) fitMask |= 1 << 12;
+ }
+ case 3 -> {
+ if (bits <= 20) fitMask |= 1 << 11;
+ }
+ case 4 -> {
+ if (bits <= 15) fitMask |= 1 << 10;
+ }
+ case 5 -> {
+ if (bits <= 12) fitMask |= 1 << 9;
+ }
+ case 6 -> {
+ if (bits <= 10) fitMask |= 1 << 8;
+ }
+ case 7 -> {
+ if (bits <= 8) fitMask |= 1 << 7;
+ }
+ case 8 -> {
+ if (bits <= 7) fitMask |= 1 << 6;
+ }
+ case 10 -> {
+ if (bits <= 6) fitMask |= 1 << 5;
+ }
+ case 12 -> {
+ if (bits <= 5) fitMask |= 1 << 4;
+ }
+ case 15 -> {
+ if (length >= 15 && bits == 4) {
+ return pack15x4(ints, offset);
+ }
+ if (bits <= 4) fitMask |= 1 << 3;
+ }
+ case 20 -> {
+ if (length >= 20 && bits == 3) {
+ return pack20x3(ints, offset);
+ }
+ if (bits <= 3) fitMask |= 1 << 2;
+ }
+ case 30 -> {
+ if (length >= 30 && bits == 2) {
+ return pack30x2(ints, offset);
+ }
+ if (bits <= 2) fitMask |= 1 << 1;
+ }
+ case 60 -> {
+ if (bits == 1) {
+ return pack60x1(ints, offset);
+ }
+ if (bits <= 1) fitMask |= 1;
+ }
+ default -> {}
+ }
+ }
+
+ final int bits = bitsRequired(prefixOr);
+ for (int s = 0; s < 14; s++) {
+ final int count = COUNTS[s];
+ if (count >= length) {
+ if (bits <= BITS[s]) {
+ return pack(s, ints, offset, length);
+ }
+ } else if ((fitMask & (1 << s)) != 0) {
+ return pack(s, ints, offset, count);
+ }
+ }
+
+ // Unreachable: selector 13 covers all non-negative int values (up to
2^31-1).
+ throw new AssertionError("unreachable");
+ }
+
+ /** Pack {@code count} integers using the given selector (low-to-high bit
order). */
+ public static long pack(int selector, int[] ints, int offset, int count) {
+ if (count == COUNTS[selector]) {
+ switch (selector) {
+ case 0:
+ return pack60x1(ints, offset);
+ case 1:
+ return pack30x2(ints, offset);
+ case 2:
+ return pack20x3(ints, offset);
+ case 3:
+ return pack15x4(ints, offset);
+ case 4:
+ return pack12x5(ints, offset);
+ case 5:
+ return pack10x6(ints, offset);
+ case 6:
+ return pack8x7(ints, offset);
+ case 7:
+ return pack7x8(ints, offset);
+ case 8:
+ return pack6x10(ints, offset);
+ case 9:
+ return pack5x12(ints, offset);
+ case 10:
+ return pack4x15(ints, offset);
+ case 11:
+ return pack3x20(ints, offset);
+ case 12:
+ return pack2x30(ints, offset);
+ case 13:
+ return pack1x31(ints, offset);
+ default:
+ break;
+ }
+ }
+
+ final int bits = BITS[selector];
+ long word = (long) selector << 60;
+ for (int i = 0; i < count; i++) {
+ word |= ((long) ints[offset + i]) << (i * bits);
+ }
+ return word;
+ }
+
+ /**
+ * Decode all integers packed in {@code word} into {@code out[outOffset..]}.
+ *
+ * @return number of integers written
+ */
+ public static int decode(long word, int[] out, int outOffset) {
+ final int selector = selector(word);
+ final int count = COUNTS[selector];
+ decodeValues(word, selector, out, outOffset, count);
+ return count;
+ }
+
+ /** Return the number of integers packed in {@code word} without fully
decoding it. */
+ public static int count(long word) {
+ return COUNTS[selector(word)];
+ }
+
+ /**
+ * Encode all {@code length} integers from {@code
ints[offset..offset+length)} into consecutive
+ * longs in {@code out}, starting at {@code out[outOffset]}.
+ *
+ * @return number of longs written
+ */
+ public static int encodeAll(int[] ints, int offset, int length, long[] out,
int outOffset) {
+ int inPos = offset;
+ int outPos = outOffset;
+ final int end = offset + length;
+ while (inPos < end) {
+ long word = encode(ints, inPos, end - inPos);
+ out[outPos++] = word;
+ inPos += count(word);
+ }
+ return outPos - outOffset;
+ }
+
+ /**
+ * Decode exactly {@code count} integers from {@code longs[offset..)} into
{@code out}.
+ *
+ * <p>The caller must supply the original integer count (e.g. stored as a
preceding VInt), because
+ * the last packed long may contain more slots than remaining integers.
+ *
+ * @return number of longs consumed
+ */
+ public static int decodeAll(long[] longs, int offset, int[] out, int
outOffset, int count) {
+ int inPos = offset;
+ int remaining = count;
+ while (remaining > 0) {
+ long word = longs[inPos++];
+ final int selector = selector(word);
+ final int toRead = Math.min(COUNTS[selector], remaining);
+ decodeValues(word, selector, out, outOffset, toRead);
+ outOffset += toRead;
+ remaining -= toRead;
+ }
+ return inPos - offset;
+ }
+
+ private static int selector(long word) {
+ final int selector = (int) (word >>> 60);
+ if (selector >= 14) {
Review Comment:
`MASKS.length`? Or pull these 14s into a shared static constant?
##########
lucene/core/src/java/org/apache/lucene/util/Simple64.java:
##########
@@ -0,0 +1,828 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util;
+
+/**
+ * Simple64: pack multiple small non-negative integers into a single long.
+ *
+ * <p>The high 4 bits of each long are a selector that encodes the bit-width
and count of the packed
+ * integers. The remaining 60 bits hold the actual values, packed from LSB to
MSB.
+ *
+ * <p>Designed for {@code int} values (non-negative, max {@link
Integer#MAX_VALUE} = 2^31 - 1).
+ *
+ * <p>Selector table (14 schemes, selectors 14-15 reserved):
+ *
+ * <pre>
+ * selector | integers | bits each | max value
+ * ---------+----------+-----------+--------------------
+ * 0 | 60 | 1 | 1
+ * 1 | 30 | 2 | 3
+ * 2 | 20 | 3 | 7
+ * 3 | 15 | 4 | 15
+ * 4 | 12 | 5 | 31
+ * 5 | 10 | 6 | 63
+ * 6 | 8 | 7 | 127
+ * 7 | 7 | 8 | 255
+ * 8 | 6 | 10 | 1023
+ * 9 | 5 | 12 | 4095
+ * 10 | 4 | 15 | 32767
+ * 11 | 3 | 20 | 1048575
+ * 12 | 2 | 30 | 1073741823
+ * 13 | 1 | 31 | 2147483647 (Integer.MAX_VALUE)
+ * </pre>
+ *
+ * <p>Every selector has a hand-unrolled pack/decode pair (e.g. {@link
#pack8x7} / {@link
+ * #decode8x7}) used whenever a word is completely full for that selector,
avoiding the generic
+ * shift-loop in {@link #unpack} for the common case.
+ */
+public final class Simple64 {
+ /** Number of integers each selector can pack. */
+ public static final int[] COUNTS = {60, 30, 20, 15, 12, 10, 8, 7, 6, 5, 4,
3, 2, 1};
+
+ /** Bit-width per integer for each selector. */
+ public static final int[] BITS = {1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15, 20,
30, 31};
+
+ /** Bit-mask for extracting one value under each selector. */
+ public static final long[] MASKS = new long[14];
+
+ static {
+ for (int s = 0; s < 14; s++) {
+ MASKS[s] = (1L << BITS[s]) - 1L;
+ }
+ }
+
+ private Simple64() {}
+
+ /**
+ * Encode as many integers from {@code ints[offset..]} as fit into a single
long, using the
+ * most-compact selector whose bit-width can represent every value.
+ *
+ * <p>Call {@link #count(long)} on the returned word to find out how many
integers were consumed.
+ *
+ * <p>NOTE: a selector is only accepted when <em>all</em> {@code
Math.min(COUNTS[selector],
+ * length)} values fit its bit-width, so that {@link #count(long)} always
returns the correct
+ * number of consumed integers. The exception is the last encoded long,
where {@code length <
+ * COUNTS[selector]} leaves it partially filled and {@link #count(long)}
over-reports; this is
+ * harmless because {@link #encodeAll} terminates immediately after.
+ *
+ * @param ints source array of non-negative integers
+ * @param offset start index
+ * @param length number of integers available from {@code offset}
+ * @return encoded long
+ */
+ public static long encode(int[] ints, int offset, int length) {
+ if (length <= 0) {
+ throw new IllegalArgumentException("length must be > 0; got " + length);
+ }
+
+ final int limit = Math.min(COUNTS[0], length);
+ long prefixOr = 0L;
+ int fitMask = 0;
+
+ for (int i = 1; i <= limit; i++) {
+ final int v = ints[offset + i - 1];
+ if (v < 0) {
+ throw new IllegalArgumentException("Simple64 does not support negative
values, got: " + v);
+ }
+ prefixOr |= v;
+ final int bits = bitsRequired(prefixOr);
+
+ switch (i) {
+ case 1 -> fitMask |= 1 << 13;
+ case 2 -> {
+ if (bits <= 30) fitMask |= 1 << 12;
+ }
+ case 3 -> {
+ if (bits <= 20) fitMask |= 1 << 11;
+ }
+ case 4 -> {
+ if (bits <= 15) fitMask |= 1 << 10;
+ }
+ case 5 -> {
+ if (bits <= 12) fitMask |= 1 << 9;
+ }
+ case 6 -> {
+ if (bits <= 10) fitMask |= 1 << 8;
+ }
+ case 7 -> {
+ if (bits <= 8) fitMask |= 1 << 7;
+ }
+ case 8 -> {
+ if (bits <= 7) fitMask |= 1 << 6;
+ }
+ case 10 -> {
+ if (bits <= 6) fitMask |= 1 << 5;
+ }
+ case 12 -> {
+ if (bits <= 5) fitMask |= 1 << 4;
+ }
+ case 15 -> {
+ if (length >= 15 && bits == 4) {
+ return pack15x4(ints, offset);
+ }
+ if (bits <= 4) fitMask |= 1 << 3;
+ }
+ case 20 -> {
+ if (length >= 20 && bits == 3) {
+ return pack20x3(ints, offset);
+ }
+ if (bits <= 3) fitMask |= 1 << 2;
+ }
+ case 30 -> {
+ if (length >= 30 && bits == 2) {
+ return pack30x2(ints, offset);
+ }
+ if (bits <= 2) fitMask |= 1 << 1;
+ }
+ case 60 -> {
+ if (bits == 1) {
+ return pack60x1(ints, offset);
+ }
+ if (bits <= 1) fitMask |= 1;
+ }
+ default -> {}
+ }
+ }
+
+ final int bits = bitsRequired(prefixOr);
+ for (int s = 0; s < 14; s++) {
+ final int count = COUNTS[s];
+ if (count >= length) {
+ if (bits <= BITS[s]) {
+ return pack(s, ints, offset, length);
+ }
+ } else if ((fitMask & (1 << s)) != 0) {
+ return pack(s, ints, offset, count);
+ }
+ }
+
+ // Unreachable: selector 13 covers all non-negative int values (up to
2^31-1).
+ throw new AssertionError("unreachable");
+ }
+
+ /** Pack {@code count} integers using the given selector (low-to-high bit
order). */
+ public static long pack(int selector, int[] ints, int offset, int count) {
+ if (count == COUNTS[selector]) {
+ switch (selector) {
+ case 0:
+ return pack60x1(ints, offset);
+ case 1:
+ return pack30x2(ints, offset);
+ case 2:
+ return pack20x3(ints, offset);
+ case 3:
+ return pack15x4(ints, offset);
+ case 4:
+ return pack12x5(ints, offset);
+ case 5:
+ return pack10x6(ints, offset);
+ case 6:
+ return pack8x7(ints, offset);
+ case 7:
+ return pack7x8(ints, offset);
+ case 8:
+ return pack6x10(ints, offset);
+ case 9:
+ return pack5x12(ints, offset);
+ case 10:
+ return pack4x15(ints, offset);
+ case 11:
+ return pack3x20(ints, offset);
+ case 12:
+ return pack2x30(ints, offset);
+ case 13:
+ return pack1x31(ints, offset);
+ default:
+ break;
+ }
+ }
+
+ final int bits = BITS[selector];
Review Comment:
Add comment that this is fallback case for when there are not enough values
to encode given the selector? Also, assert count is smaller than what selector
could handle?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
