nssalian commented on code in PR #16747: URL: https://github.com/apache/iceberg/pull/16747#discussion_r3746564691
########## core/src/main/java/org/apache/iceberg/mumbling/PFOREncoding.java: ########## @@ -0,0 +1,402 @@ +/* + * 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.iceberg.mumbling; + +import java.nio.ByteBuffer; +import org.apache.iceberg.relocated.com.google.common.base.Preconditions; +import org.apache.iceberg.util.ByteBuffers; +import org.apache.iceberg.util.Pair; + +/** + * Patched Frame of Reference (PFOR) encoding for arrays of unsigned byte values. + * + * <p>Implements the encoding described in Appendix A of the Mumbling bitmap specification. The + * input array is split into 256-value chunks (the last chunk may be shorter). Each chunk is + * independently encoded using 4 configuration values: + * + * <ul> + * <li>{@code b1}: number of bits stored in the primary array for every normalized value + * <li>{@code b2}: number of bits stored per exception value (normalized value of > b1 bits) + * <li>{@code e}: number of exceptions with more than b1 bits + * <li>{@code m}: chunk-local minimum value, subtracted from all values to normalize + * </ul> + * + * <p>Each chunk is stored as: + * + * <ul> + * <li>3-byte header: {@code b1|b2} primary and exception bit widths (byte 0), {@code e} exception + * count (byte 1), {@code m} normalization base value (byte 2) + * <li>Primary array: the low {@code b1} bits of every normalized value, packed MSB-first ({@code + * b1 * n} bits, padded to a byte) + * <li>Exception offsets: chunk-relative positions of exception values ({@code e} bytes) + * <li>Exception values: the high {@code b2} bits of every exception value, packed MSB-first + * ({@code e * b2} bits, padded to a byte. + * </ul> + */ +class PFOREncoding { + private static final int CHUNK_SIZE = 256; + + private PFOREncoding() {} + + /** + * Encodes {@code count} values from an array of unsigned byte values. + * + * @param values unsigned byte values to encode + * @param count number of values to encode + * @return a {@link ByteBuffer} of the encoded values with position and limit set for reading + */ + static ByteBuffer encode(int[] values, int count) { + ByteBuffer out = ByteBuffer.allocate(estimateEncodedSize(count)); + int bytesWritten = encode(values, 0, out, 0, count); + return out.slice(0, bytesWritten); + } + + /** + * Encode {@code count} unsigned byte values from {@code values} into a buffer. + * + * <p>The buffer's position and limit are not modified. + * + * @param values unsigned byte values to encode + * @param valueOffset starting offset of values to encode + * @param out buffer to write encoded values to + * @param outOffset starting offset in the output buffer + * @param count number of values to encode + * @return the number of bytes written to the buffer + */ + static int encode(int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) { + // outOffset is relative to the buffer's position; check the encoded data fits + Preconditions.checkArgument(outOffset >= 0, "Cannot encode at negative offset: %s", outOffset); + Preconditions.checkArgument( + estimateEncodedSize(count) <= out.remaining() - outOffset, + "Cannot encode %s values to buffer with %s remaining space", + count, + out.remaining() - outOffset); + + int bytesWritten = 0; + int valuesEncoded = 0; + + while (valuesEncoded < count) { + int chunkLength = Math.min(CHUNK_SIZE, count - valuesEncoded); + bytesWritten += + encodeChunk( + values, valueOffset + valuesEncoded, out, outOffset + bytesWritten, chunkLength); + valuesEncoded += chunkLength; + } + + return bytesWritten; + } + + /** + * Decode to produce unsigned byte values. + * + * <p>Decodes starting at {@code encoded.position()} and does not modify the input buffer. + * + * @param encoded PFOR-encoded ByteBuffer produced by {@link #encode} + * @param count total number of values to decode + * @return decoded unsigned byte values + */ + static int[] decode(ByteBuffer encoded, int count) { + int[] out = new int[count]; + decode(encoded, 0, out, 0, count); + return out; + } + + /** + * Decode {@code count} unsigned bytes from a buffer into {@code out}. + * + * <p>This does not modify the input buffer. + * + * @param encoded a buffer containing encoded data + * @param offset starting offset of encoded values + * @param out an output value array + * @param outOffset starting offset in the output array + * @param count number of values to decode + * @return the number of bytes read from the encoded buffer + */ + static int decode(ByteBuffer encoded, int offset, int[] out, int outOffset, int count) { + Preconditions.checkArgument(offset >= 0, "Cannot decode at negative offset: %s", offset); + + int bytesRead = 0; + int valuesRead = 0; + + while (valuesRead < count) { + int chunkSize = Math.min(CHUNK_SIZE, count - valuesRead); + bytesRead += decodeChunk(encoded, offset + bytesRead, out, outOffset + valuesRead, chunkSize); + valuesRead += chunkSize; + } + + return bytesRead; + } + + /** + * Encode one chunk into {@code out} starting at absolute position {@code outPos}. + * + * @param values array containing source values to encode + * @param valueOffset starting index of values to encode + * @param out an output {@link ByteBuffer} + * @param outOffset starting index for output in the out buffer + * @param count number of values to encode + * @return the number of bytes written to the output buffer + */ + private static int encodeChunk( + int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) { + Preconditions.checkArgument(count >= 0, "Invalid value count to encode: %s", count); + Preconditions.checkArgument( + valueOffset + count <= values.length, + "Cannot encode %s values starting at %s from int[%s]: not enough values", + count, + valueOffset, + values.length); + + // find base=min(values) for normalization + int base = min(values, valueOffset, count); + + // normalize by subtracting base + int[] normalized = new int[count]; + int setBits = 0; + int normalizedSetBits = 0; + for (int i = 0; i < count; i += 1) { + setBits |= values[valueOffset + i]; + normalized[i] = values[valueOffset + i] - base; + normalizedSetBits |= normalized[i]; + } + + Preconditions.checkArgument( + width(setBits) <= 8, + "Cannot encode values wider than 8 bits: %s bits needed", + width(setBits)); + + // Choose b1 to minimize total encoded data size (excluding 3-byte header) + int maxWidth = width(normalizedSetBits); + Pair<Integer, Integer> widthAndExcCount = chooseBitWidth(normalized, count, maxWidth); + int b1 = widthAndExcCount.first(); + int b2 = maxWidth - b1; + int excCount = widthAndExcCount.second(); + + // check that there is enough space in the buffer for the encoded data + int requiredSize = encodedSize(count, b1, b2, excCount); + Preconditions.checkArgument( + outOffset + requiredSize <= out.remaining(), + "Cannot encode %s values (%s bytes) into buffer with %s remaining bytes", + requiredSize, + out.remaining() - outOffset); + + // Special case: b1=8 means store original values as raw bytes with b2, e, and m set to 0. + if (b1 == 8) { + writeHeader(out, outOffset, b1, 0 /* b2 */, 0 /* excCount */, 0 /* m */); + return 3 + BitPacking.packBits(8, values, valueOffset, out, outOffset + 3, count); + } + + int bytesWritten = writeHeader(out, outOffset, b1, b2, excCount, base); + + // Primary array: low b1 bits of every value + bytesWritten += BitPacking.packBits(b1, normalized, 0, out, outOffset + bytesWritten, count); + + // b2 is the bit width of exception values: (maxWidth - b1) bits of each exception + if (excCount > 0) { + int[] excOffsets = new int[excCount]; + int[] excValues = new int[excCount]; + + // Collect exceptions (values that do not fit in b1 bits) + int excIndex = 0; + int threshold = 1 << b1; + for (int i = 0; i < count; i += 1) { + if (normalized[i] >= threshold) { + excOffsets[excIndex] = i; + excValues[excIndex] = normalized[i] >>> b1; + excIndex += 1; + } + } + + // Exception offsets (one byte per exception) + bytesWritten += + BitPacking.packBits(8, excOffsets, 0, out, outOffset + bytesWritten, excCount); + + // Exception values: remaining high b2 bits of each exception + bytesWritten += + BitPacking.packBits(b2, excValues, 0, out, outOffset + bytesWritten, excCount); + } + + return bytesWritten; + } + + /** + * Decode one chunk of encoded data, writing decoded values into an output array. + * + * @param data buffer containing source data to decode + * @param dataOffset starting index in the buffer to decode + * @param out an output {@link ByteBuffer} + * @param outOffset starting index for output in the out buffer + * @param count number of values to decode + * @return the number of bytes read from {@code data} + */ + private static int decodeChunk( + ByteBuffer data, int dataOffset, int[] out, int outOffset, int count) { + Preconditions.checkArgument(count >= 0, "Invalid value count to decode: %s", count); + Preconditions.checkArgument( + outOffset + count <= out.length, + "Cannot decode %s values starting at %s into int[%s]: not enough space", + count, + outOffset, + out.length); + + int b1 = ByteBuffers.readByte(data, dataOffset) & 0x0F; Review Comment: Since this decodes embedded, possibly-corrupt metadata, could we check dataOffset + 3 <= data.remaining() before reading the header so a truncated chunk fails with a clean typed error? ########## core/src/main/java/org/apache/iceberg/mumbling/PFOREncoding.java: ########## @@ -0,0 +1,402 @@ +/* + * 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.iceberg.mumbling; + +import java.nio.ByteBuffer; +import org.apache.iceberg.relocated.com.google.common.base.Preconditions; +import org.apache.iceberg.util.ByteBuffers; +import org.apache.iceberg.util.Pair; + +/** + * Patched Frame of Reference (PFOR) encoding for arrays of unsigned byte values. + * + * <p>Implements the encoding described in Appendix A of the Mumbling bitmap specification. The + * input array is split into 256-value chunks (the last chunk may be shorter). Each chunk is + * independently encoded using 4 configuration values: + * + * <ul> + * <li>{@code b1}: number of bits stored in the primary array for every normalized value + * <li>{@code b2}: number of bits stored per exception value (normalized value of > b1 bits) + * <li>{@code e}: number of exceptions with more than b1 bits + * <li>{@code m}: chunk-local minimum value, subtracted from all values to normalize + * </ul> + * + * <p>Each chunk is stored as: + * + * <ul> + * <li>3-byte header: {@code b1|b2} primary and exception bit widths (byte 0), {@code e} exception + * count (byte 1), {@code m} normalization base value (byte 2) + * <li>Primary array: the low {@code b1} bits of every normalized value, packed MSB-first ({@code + * b1 * n} bits, padded to a byte) + * <li>Exception offsets: chunk-relative positions of exception values ({@code e} bytes) + * <li>Exception values: the high {@code b2} bits of every exception value, packed MSB-first + * ({@code e * b2} bits, padded to a byte. + * </ul> + */ +class PFOREncoding { + private static final int CHUNK_SIZE = 256; + + private PFOREncoding() {} + + /** + * Encodes {@code count} values from an array of unsigned byte values. + * + * @param values unsigned byte values to encode + * @param count number of values to encode + * @return a {@link ByteBuffer} of the encoded values with position and limit set for reading + */ + static ByteBuffer encode(int[] values, int count) { + ByteBuffer out = ByteBuffer.allocate(estimateEncodedSize(count)); + int bytesWritten = encode(values, 0, out, 0, count); + return out.slice(0, bytesWritten); + } + + /** + * Encode {@code count} unsigned byte values from {@code values} into a buffer. + * + * <p>The buffer's position and limit are not modified. + * + * @param values unsigned byte values to encode + * @param valueOffset starting offset of values to encode + * @param out buffer to write encoded values to + * @param outOffset starting offset in the output buffer + * @param count number of values to encode + * @return the number of bytes written to the buffer + */ + static int encode(int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) { + // outOffset is relative to the buffer's position; check the encoded data fits + Preconditions.checkArgument(outOffset >= 0, "Cannot encode at negative offset: %s", outOffset); + Preconditions.checkArgument( + estimateEncodedSize(count) <= out.remaining() - outOffset, + "Cannot encode %s values to buffer with %s remaining space", + count, + out.remaining() - outOffset); + + int bytesWritten = 0; + int valuesEncoded = 0; + + while (valuesEncoded < count) { + int chunkLength = Math.min(CHUNK_SIZE, count - valuesEncoded); + bytesWritten += + encodeChunk( + values, valueOffset + valuesEncoded, out, outOffset + bytesWritten, chunkLength); + valuesEncoded += chunkLength; + } + + return bytesWritten; + } + + /** + * Decode to produce unsigned byte values. + * + * <p>Decodes starting at {@code encoded.position()} and does not modify the input buffer. + * + * @param encoded PFOR-encoded ByteBuffer produced by {@link #encode} + * @param count total number of values to decode + * @return decoded unsigned byte values + */ + static int[] decode(ByteBuffer encoded, int count) { + int[] out = new int[count]; + decode(encoded, 0, out, 0, count); + return out; + } + + /** + * Decode {@code count} unsigned bytes from a buffer into {@code out}. + * + * <p>This does not modify the input buffer. + * + * @param encoded a buffer containing encoded data + * @param offset starting offset of encoded values + * @param out an output value array + * @param outOffset starting offset in the output array + * @param count number of values to decode + * @return the number of bytes read from the encoded buffer + */ + static int decode(ByteBuffer encoded, int offset, int[] out, int outOffset, int count) { + Preconditions.checkArgument(offset >= 0, "Cannot decode at negative offset: %s", offset); + + int bytesRead = 0; + int valuesRead = 0; + + while (valuesRead < count) { + int chunkSize = Math.min(CHUNK_SIZE, count - valuesRead); + bytesRead += decodeChunk(encoded, offset + bytesRead, out, outOffset + valuesRead, chunkSize); + valuesRead += chunkSize; + } + + return bytesRead; + } + + /** + * Encode one chunk into {@code out} starting at absolute position {@code outPos}. + * + * @param values array containing source values to encode + * @param valueOffset starting index of values to encode + * @param out an output {@link ByteBuffer} + * @param outOffset starting index for output in the out buffer + * @param count number of values to encode + * @return the number of bytes written to the output buffer + */ + private static int encodeChunk( + int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) { + Preconditions.checkArgument(count >= 0, "Invalid value count to encode: %s", count); + Preconditions.checkArgument( + valueOffset + count <= values.length, + "Cannot encode %s values starting at %s from int[%s]: not enough values", + count, + valueOffset, + values.length); + + // find base=min(values) for normalization + int base = min(values, valueOffset, count); + + // normalize by subtracting base + int[] normalized = new int[count]; + int setBits = 0; + int normalizedSetBits = 0; + for (int i = 0; i < count; i += 1) { + setBits |= values[valueOffset + i]; + normalized[i] = values[valueOffset + i] - base; + normalizedSetBits |= normalized[i]; + } + + Preconditions.checkArgument( + width(setBits) <= 8, + "Cannot encode values wider than 8 bits: %s bits needed", + width(setBits)); + + // Choose b1 to minimize total encoded data size (excluding 3-byte header) + int maxWidth = width(normalizedSetBits); + Pair<Integer, Integer> widthAndExcCount = chooseBitWidth(normalized, count, maxWidth); + int b1 = widthAndExcCount.first(); + int b2 = maxWidth - b1; + int excCount = widthAndExcCount.second(); + + // check that there is enough space in the buffer for the encoded data + int requiredSize = encodedSize(count, b1, b2, excCount); + Preconditions.checkArgument( + outOffset + requiredSize <= out.remaining(), + "Cannot encode %s values (%s bytes) into buffer with %s remaining bytes", Review Comment: this message has three %s but only two args (requiredSize and out.remaining() - outOffset), so the leading value count never gets filled in. ########## core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java: ########## @@ -0,0 +1,168 @@ +/* + * 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.iceberg.mumbling; + +import java.nio.ByteBuffer; +import org.apache.iceberg.relocated.com.google.common.base.Preconditions; + +/** + * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}. + * + * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link + * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that + * maps each container index to its absolute byte position in the buffer. This offsets array is the + * only derived state kept by this class. + * + * <p>Format (all integers unsigned, little-endian): + * + * <ul> + * <li>Header (6 bytes): version (1), cardinality (3), container count (2) + * <li>Descriptor array: PFOR-encoded, one byte per container + * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers + * </ul> + */ +class MumblingBitmap { + private static final int VERSION = 1; + private static final int HEADER_SIZE = 6; + private static final int DENSE_CONTAINER_BIT = 0b0010_0000; + + private final ByteBuffer data; + private final int cardinality; + private final int containerCount; + private int[] descriptors = null; + private int[] offsets = null; + + MumblingBitmap(ByteBuffer data) { + int version = data.get(data.position()) & 0xFF; + if (version != VERSION) { + throw new UnsupportedOperationException("Unsupported Mumbling bitmap version: " + version); + } + + this.data = data; + this.cardinality = + (data.get(data.position() + 1) & 0xFF) + | ((data.get(data.position() + 2) & 0xFF) << 8) + | ((data.get(data.position() + 3) & 0xFF) << 16); + this.containerCount = + (data.get(data.position() + 4) & 0xFF) | ((data.get(data.position() + 5) & 0xFF) << 8); + } + + /** Returns the number of bits set in the bitmap. */ + public int cardinality() { + return cardinality; + } + + /** + * Returns {@code true} if the bit at {@code pos} is set in the bitmap. + * + * <p>Positions beyond the range of any container are always unset. + */ + public boolean isSet(int pos) { + Preconditions.checkArgument(pos >= 0, "Invalid bit position: %s < 0", pos); + int containerIndex = pos >>> 8; + int posInContainer = pos & 0xFF; + + if (containerIndex >= containerCount) { + return false; + } + + int containerStart = offset(containerIndex); + int descriptor = descriptor(containerIndex); + + if (isDense(descriptor)) { + // Dense: 32-byte bitset, MSB of byte 0 is position 0 + int byteIndex = posInContainer >>> 3; + int bitShift = 7 - (posInContainer & 0b111); + return ((data.get(containerStart + byteIndex) >>> bitShift) & 0b1) == 0b1; + + } else { + // Sparse: sorted list of set positions; scan until found or exceeded + for (int i = 0; i < descriptor; i += 1) { + int stored = data.get(containerStart + i) & 0xFF; + if (stored == posInContainer) { + return true; + } + + if (stored > posInContainer) { + return false; + } + } + + return false; + } + } + + private int descriptor(int containerIndex) { + if (null == descriptors) { + decodeDescriptors(); + } + + return descriptors[containerIndex]; + } + + private int offset(int containerIndex) { + if (null == offsets) { + decodeDescriptors(); + } + + return offsets[containerIndex]; + } + + /** + * Decode the descriptor array and produce an array of absolute container offsets in the buffer. + */ + private void decodeDescriptors() { + this.descriptors = new int[containerCount]; + int bytesRead = PFOREncoding.decode(data, HEADER_SIZE, descriptors, 0, containerCount); + + this.offsets = new int[containerCount + 1]; + int firstContainerOffset = data.position() + HEADER_SIZE + bytesRead; + descriptorsToOffsets(firstContainerOffset, descriptors, offsets); + } + + private static boolean isDense(int descriptor) { + return (descriptor & DENSE_CONTAINER_BIT) == DENSE_CONTAINER_BIT; + } + + /** + * Convert an array of lengths into an array of offsets starting at 0. + * + * <p>For example, descriptorsToOffsets([1, 1, 2]) produces [0, 1, 2, 4]. + * + * @param baseOffset initial offset of the first container + * @param descriptors an array of descriptor bytes + * @param offsets output array of offsets + */ + private static void descriptorsToOffsets(int baseOffset, int[] descriptors, int[] offsets) { + Preconditions.checkArgument( + offsets.length > descriptors.length, + "Cannot decode %s lengths into %s offsets (not enough space)", + descriptors.length, + offsets.length); + + offsets[0] = baseOffset; + for (int i = 0; i < descriptors.length; i += 1) { + if (isDense(descriptors[i])) { + offsets[i + 1] = offsets[i] + 32; Review Comment: Nit: this 32 is the dense-container byte size (256 bits / 8) and it also shows up in the two comments above. Since the class already has DENSE_CONTAINER_BIT, possibly adding a DENSE_CONTAINER_BYTES = 32 would make the intent obvious here. ########## core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java: ########## @@ -0,0 +1,168 @@ +/* + * 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.iceberg.mumbling; + +import java.nio.ByteBuffer; +import org.apache.iceberg.relocated.com.google.common.base.Preconditions; + +/** + * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}. + * + * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link + * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that + * maps each container index to its absolute byte position in the buffer. This offsets array is the + * only derived state kept by this class. + * + * <p>Format (all integers unsigned, little-endian): + * + * <ul> + * <li>Header (6 bytes): version (1), cardinality (3), container count (2) + * <li>Descriptor array: PFOR-encoded, one byte per container + * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers + * </ul> + */ +class MumblingBitmap { + private static final int VERSION = 1; + private static final int HEADER_SIZE = 6; + private static final int DENSE_CONTAINER_BIT = 0b0010_0000; + + private final ByteBuffer data; + private final int cardinality; + private final int containerCount; + private int[] descriptors = null; + private int[] offsets = null; + + MumblingBitmap(ByteBuffer data) { + int version = data.get(data.position()) & 0xFF; + if (version != VERSION) { + throw new UnsupportedOperationException("Unsupported Mumbling bitmap version: " + version); + } + + this.data = data; + this.cardinality = + (data.get(data.position() + 1) & 0xFF) + | ((data.get(data.position() + 2) & 0xFF) << 8) + | ((data.get(data.position() + 3) & 0xFF) << 16); + this.containerCount = + (data.get(data.position() + 4) & 0xFF) | ((data.get(data.position() + 5) & 0xFF) << 8); + } + + /** Returns the number of bits set in the bitmap. */ + public int cardinality() { + return cardinality; + } + + /** + * Returns {@code true} if the bit at {@code pos} is set in the bitmap. + * + * <p>Positions beyond the range of any container are always unset. + */ + public boolean isSet(int pos) { + Preconditions.checkArgument(pos >= 0, "Invalid bit position: %s < 0", pos); + int containerIndex = pos >>> 8; + int posInContainer = pos & 0xFF; + + if (containerIndex >= containerCount) { + return false; + } + + int containerStart = offset(containerIndex); + int descriptor = descriptor(containerIndex); + + if (isDense(descriptor)) { + // Dense: 32-byte bitset, MSB of byte 0 is position 0 + int byteIndex = posInContainer >>> 3; + int bitShift = 7 - (posInContainer & 0b111); + return ((data.get(containerStart + byteIndex) >>> bitShift) & 0b1) == 0b1; + + } else { + // Sparse: sorted list of set positions; scan until found or exceeded + for (int i = 0; i < descriptor; i += 1) { + int stored = data.get(containerStart + i) & 0xFF; + if (stored == posInContainer) { + return true; + } + + if (stored > posInContainer) { + return false; + } + } + + return false; + } + } + + private int descriptor(int containerIndex) { + if (null == descriptors) { + decodeDescriptors(); + } + + return descriptors[containerIndex]; + } + + private int offset(int containerIndex) { + if (null == offsets) { + decodeDescriptors(); + } + + return offsets[containerIndex]; + } + + /** + * Decode the descriptor array and produce an array of absolute container offsets in the buffer. + */ + private void decodeDescriptors() { + this.descriptors = new int[containerCount]; + int bytesRead = PFOREncoding.decode(data, HEADER_SIZE, descriptors, 0, containerCount); + + this.offsets = new int[containerCount + 1]; + int firstContainerOffset = data.position() + HEADER_SIZE + bytesRead; + descriptorsToOffsets(firstContainerOffset, descriptors, offsets); + } + + private static boolean isDense(int descriptor) { Review Comment: More of a question as I was reading this, isDense keys only on the 0x20 bit, so a descriptor that's neither valid sparse (0-31) nor exactly dense (say 0x40 with the dense bit clear) is read as a sparse container of length 64-255. It's not reachable from the encoder, only from crafted or corrupt input, and the spec reserves the top bits. Do you want the reader to reject unknown descriptor patterns, or is that out of scope for the read-only version? -- 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]
