vinooganesh commented on code in PR #3397:
URL: https://github.com/apache/parquet-java/pull/3397#discussion_r4305395884
##########
parquet-column/src/main/java/org/apache/parquet/column/Encoding.java:
##########
@@ -147,6 +149,26 @@ public ValuesReader getValuesReader(ColumnDescriptor
descriptor, ValuesType valu
}
},
+ /**
+ * ALP (Adaptive Lossless floating-Point) encoding for FLOAT and DOUBLE
types.
+ * Works by converting floating-point values to integers using decimal
scaling,
+ * then applying Frame of Reference (FOR) encoding and bit-packing.
Review Comment:
Cut it down to one line plus links to the spec and the blog post @alamb
suggested. Most of the other constants in `Encoding` have a short javadoc, so I
kept the one line, but I can remove it if you'd prefer.
##########
parquet-column/src/main/java/org/apache/parquet/column/values/alp/AlpConstants.java:
##########
@@ -0,0 +1,80 @@
+/*
+ * 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.parquet.column.values.alp;
+
+import org.apache.parquet.Preconditions;
+
+/**
+ * Constants for the ALP (Adaptive Lossless floating-Point) encoding.
+ *
+ * <p>ALP encoding converts floating-point values to integers using decimal
scaling,
+ * then applies Frame of Reference encoding and bit-packing.
+ * Values that cannot be losslessly converted are stored as exceptions.
+ *
+ * <p>Based on the paper: "ALP: Adaptive Lossless floating-Point Compression"
(SIGMOD 2024)
Review Comment:
Removed both, and the same description from the writer's javadoc.
##########
parquet-column/src/main/java/org/apache/parquet/column/values/alp/AlpValuesReader.java:
##########
@@ -0,0 +1,306 @@
+/*
+ * 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.parquet.column.values.alp;
+
+import static
org.apache.parquet.column.values.alp.AlpConstants.ALP_COMPRESSION_MODE;
+import static
org.apache.parquet.column.values.alp.AlpConstants.ALP_HEADER_SIZE;
+import static org.apache.parquet.column.values.alp.AlpConstants.ALP_INFO_SIZE;
+import static
org.apache.parquet.column.values.alp.AlpConstants.ALP_INTEGER_ENCODING_FOR;
+import static
org.apache.parquet.column.values.alp.AlpConstants.MAX_LOG_VECTOR_SIZE;
+import static
org.apache.parquet.column.values.alp.AlpConstants.MIN_LOG_VECTOR_SIZE;
+
+import java.io.IOException;
+import java.nio.ByteBuffer;
+import java.nio.ByteOrder;
+import org.apache.parquet.bytes.ByteBufferInputStream;
+import org.apache.parquet.column.values.ValuesReader;
+import org.apache.parquet.io.ParquetDecodingException;
+
+/**
+ * Abstract base class for ALP values readers with lazy per-vector decoding.
+ *
+ * <p>Reads ALP-encoded values from the interleaved page layout:
Review Comment:
Removed it here, in the float and double readers, and in the writer.
##########
parquet-column/src/main/java/org/apache/parquet/column/values/alp/AlpValuesReader.java:
##########
@@ -0,0 +1,306 @@
+/*
+ * 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.parquet.column.values.alp;
+
+import static
org.apache.parquet.column.values.alp.AlpConstants.ALP_COMPRESSION_MODE;
+import static
org.apache.parquet.column.values.alp.AlpConstants.ALP_HEADER_SIZE;
+import static org.apache.parquet.column.values.alp.AlpConstants.ALP_INFO_SIZE;
+import static
org.apache.parquet.column.values.alp.AlpConstants.ALP_INTEGER_ENCODING_FOR;
+import static
org.apache.parquet.column.values.alp.AlpConstants.MAX_LOG_VECTOR_SIZE;
+import static
org.apache.parquet.column.values.alp.AlpConstants.MIN_LOG_VECTOR_SIZE;
+
+import java.io.IOException;
+import java.nio.ByteBuffer;
+import java.nio.ByteOrder;
+import org.apache.parquet.bytes.ByteBufferInputStream;
+import org.apache.parquet.column.values.ValuesReader;
+import org.apache.parquet.io.ParquetDecodingException;
+
+/**
+ * Abstract base class for ALP values readers with lazy per-vector decoding.
+ *
+ * <p>Reads ALP-encoded values from the interleaved page layout:
+ * <pre>
+ * ┌─────────┬──────────────────────┬──────────────┬──────────────┬─────┐
+ * │ Header │ Offset Array │ Vector 0 │ Vector 1 │ ... │
+ * │ 7 bytes │ 4B × numVectors │ (interleaved)│ (interleaved)│ │
+ * └─────────┴──────────────────────┴──────────────┴──────────────┴─────┘
+ * </pre>
+ *
+ * <p>Each vector is decoded lazily on first access. Skipping values does not
+ * trigger decoding of intermediate vectors.
+ */
+abstract class AlpValuesReader extends ValuesReader {
+
+ protected int vectorSize;
+ protected int totalCount;
+ protected int numVectors;
+ protected int pageValueIndex;
+ protected int currentVectorNumber;
+
+ protected int[] vectorOffsets;
+ protected ByteBuffer vectorsData;
+ protected int offsetArraySize;
+
+ // Scratch buffer for exception positions within a vector; shared by both
readers (int[] in each).
+ protected int[] excPositionsBuffer;
+
+ AlpValuesReader() {
+ this.pageValueIndex = 0;
+ this.totalCount = 0;
+ this.currentVectorNumber = -1;
+ }
+
+ @Override
+ public void initFromPage(int valuesCount, ByteBufferInputStream stream)
+ throws ParquetDecodingException, IOException {
+ ByteBuffer headerBuf =
stream.slice(ALP_HEADER_SIZE).order(ByteOrder.LITTLE_ENDIAN);
+ int compressionMode = headerBuf.get() & 0xFF;
+ int integerEncoding = headerBuf.get() & 0xFF;
+ int logVectorSize = headerBuf.get() & 0xFF;
+ int numElements = headerBuf.getInt();
+
+ if (compressionMode != ALP_COMPRESSION_MODE) {
+ throw new ParquetDecodingException("Unsupported ALP compression mode: "
+ compressionMode);
+ }
+ if (integerEncoding != ALP_INTEGER_ENCODING_FOR) {
+ throw new ParquetDecodingException("Unsupported ALP integer encoding: "
+ integerEncoding);
+ }
+ if (logVectorSize < MIN_LOG_VECTOR_SIZE || logVectorSize >
MAX_LOG_VECTOR_SIZE) {
+ throw new ParquetDecodingException("Invalid ALP log vector size: " +
logVectorSize + ", must be between "
+ + MIN_LOG_VECTOR_SIZE + " and " + MAX_LOG_VECTOR_SIZE);
+ }
+ if (numElements < 0) {
+ throw new ParquetDecodingException("Invalid ALP element count: " +
numElements);
+ }
+ // ALP's num_elements is the count of non-null values that went through
encoding;
+ // valuesCount is the page row count, which is larger when the column has
nulls.
+ // The two are equal only for required (non-null) columns.
+ if (numElements > valuesCount) {
+ throw new ParquetDecodingException(
+ "ALP header element count " + numElements + " exceeds page
valuesCount " + valuesCount);
+ }
+
+ this.vectorSize = 1 << logVectorSize;
+ this.totalCount = numElements;
+
+ // Bound the vector count against the bytes actually present before
allocating anything.
+ // numElements is only capped by valuesCount, which a forged page can set
as high as
+ // Integer.MAX_VALUE, so computing this in int would overflow to a
negative count, and even
+ // without overflow a large count would drive a huge int[] and a huge
stream.slice allocation.
+ // Every vector costs a 4-byte offset entry plus at least its ALP and FOR
headers, which gives
+ // a hard ceiling on how many vectors the remaining bytes can possibly
describe.
+ int minVectorBytes = ALP_INFO_SIZE + forInfoSize();
+ long bodyBytes = stream.available();
+ long numVectorsLong = ((long) numElements + vectorSize - 1) / vectorSize;
+ long minBodyBytes = numVectorsLong * (Integer.BYTES + minVectorBytes);
+ if (minBodyBytes > bodyBytes) {
+ throw new ParquetDecodingException("ALP header element count " +
numElements + " requires at least "
+ + minBodyBytes + " bytes but only " + bodyBytes + " remain in the
page");
+ }
+ this.numVectors = (int) numVectorsLong;
+ this.pageValueIndex = 0;
+ this.currentVectorNumber = -1;
+
+ this.offsetArraySize = numVectors * Integer.BYTES;
+ ByteBuffer offsetBuf =
stream.slice(offsetArraySize).order(ByteOrder.LITTLE_ENDIAN);
+ this.vectorOffsets = new int[numVectors];
+ for (int v = 0; v < numVectors; v++) {
+ vectorOffsets[v] = offsetBuf.getInt();
+ }
+
+ // Slice remaining bytes into a 0-based view so decodeVector can use
+ // absolute get methods (vectorsData.get(pos)) directly.
+ int remainingBytes = (int) stream.available();
+ ByteBuffer rawSlice = stream.slice(remainingBytes);
+ this.vectorsData = rawSlice.slice().order(ByteOrder.LITTLE_ENDIAN);
+
+ validateVectorOffsets(minVectorBytes);
+
+ allocateDecodedBuffer(vectorSize);
+ this.excPositionsBuffer = new int[vectorSize];
+ }
+
+ /**
+ * Validates the offset array against the page body before any vector is
decoded. Offsets are
+ * relative to the start of the compression body (the offset array itself),
so the first vector
+ * must begin exactly where the offset array ends, offsets must increase by
at least one vector's
+ * fixed headers, and every vector must start early enough to fit those
headers. Without this a
+ * forged offset can point into another vector and silently decode the wrong
values.
+ */
+ private void validateVectorOffsets(int minVectorBytes) {
+ int bodyLimit = offsetArraySize + vectorsData.limit();
+ for (int v = 0; v < numVectors; v++) {
+ int offset = vectorOffsets[v];
+ if (v == 0) {
+ if (offset != offsetArraySize) {
+ throw new ParquetDecodingException("ALP first vector offset " +
offset
+ + " must equal the offset array size " + offsetArraySize);
+ }
+ } else if ((long) offset - vectorOffsets[v - 1] < minVectorBytes) {
+ throw new ParquetDecodingException("ALP vector offsets must increase
by at least "
+ + minVectorBytes + " bytes, but vector " + v + " starts at " +
offset + " after vector "
+ + (v - 1) + " at " + vectorOffsets[v - 1]);
+ }
+ if (offset > bodyLimit - minVectorBytes) {
+ throw new ParquetDecodingException("ALP vector " + v + " offset " +
offset
+ + " leaves no room for its headers before the end of the page body
at " + bodyLimit);
+ }
+ }
+ }
+
+ /**
+ * The position just past the last byte vector {@code vectorNumber} may
read, derived from the
+ * next vector's offset (or the end of the body for the final vector).
+ */
+ private int getVectorEndPosition(int vectorNumber) {
+ if (vectorNumber < numVectors - 1) {
+ return vectorOffsets[vectorNumber + 1] - offsetArraySize;
+ }
+ return vectorsData.limit();
+ }
+
+ protected int getVectorLength(int vectorNumber) {
+ if (vectorNumber < numVectors - 1) {
+ return vectorSize;
+ }
+ // Last vector may be partial
+ int lastVectorLen = totalCount % vectorSize;
+ return lastVectorLen == 0 ? vectorSize : lastVectorLen;
+ }
+
+ // Offsets in the page are relative to the compression body (after header),
Review Comment:
Removed it. The javadoc on `getVectorDataPosition` now says offsets are
measured from the start of the offset array.
##########
parquet-column/src/main/java/org/apache/parquet/column/values/alp/AlpValuesReader.java:
##########
@@ -0,0 +1,306 @@
+/*
+ * 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.parquet.column.values.alp;
+
+import static
org.apache.parquet.column.values.alp.AlpConstants.ALP_COMPRESSION_MODE;
+import static
org.apache.parquet.column.values.alp.AlpConstants.ALP_HEADER_SIZE;
+import static org.apache.parquet.column.values.alp.AlpConstants.ALP_INFO_SIZE;
+import static
org.apache.parquet.column.values.alp.AlpConstants.ALP_INTEGER_ENCODING_FOR;
+import static
org.apache.parquet.column.values.alp.AlpConstants.MAX_LOG_VECTOR_SIZE;
+import static
org.apache.parquet.column.values.alp.AlpConstants.MIN_LOG_VECTOR_SIZE;
+
+import java.io.IOException;
+import java.nio.ByteBuffer;
+import java.nio.ByteOrder;
+import org.apache.parquet.bytes.ByteBufferInputStream;
+import org.apache.parquet.column.values.ValuesReader;
+import org.apache.parquet.io.ParquetDecodingException;
+
+/**
+ * Abstract base class for ALP values readers with lazy per-vector decoding.
+ *
+ * <p>Reads ALP-encoded values from the interleaved page layout:
+ * <pre>
+ * ┌─────────┬──────────────────────┬──────────────┬──────────────┬─────┐
+ * │ Header │ Offset Array │ Vector 0 │ Vector 1 │ ... │
+ * │ 7 bytes │ 4B × numVectors │ (interleaved)│ (interleaved)│ │
+ * └─────────┴──────────────────────┴──────────────┴──────────────┴─────┘
+ * </pre>
+ *
+ * <p>Each vector is decoded lazily on first access. Skipping values does not
+ * trigger decoding of intermediate vectors.
+ */
+abstract class AlpValuesReader extends ValuesReader {
+
+ protected int vectorSize;
+ protected int totalCount;
+ protected int numVectors;
+ protected int pageValueIndex;
+ protected int currentVectorNumber;
+
+ protected int[] vectorOffsets;
+ protected ByteBuffer vectorsData;
+ protected int offsetArraySize;
+
+ // Scratch buffer for exception positions within a vector; shared by both
readers (int[] in each).
+ protected int[] excPositionsBuffer;
+
+ AlpValuesReader() {
+ this.pageValueIndex = 0;
+ this.totalCount = 0;
+ this.currentVectorNumber = -1;
+ }
+
+ @Override
+ public void initFromPage(int valuesCount, ByteBufferInputStream stream)
+ throws ParquetDecodingException, IOException {
+ ByteBuffer headerBuf =
stream.slice(ALP_HEADER_SIZE).order(ByteOrder.LITTLE_ENDIAN);
+ int compressionMode = headerBuf.get() & 0xFF;
+ int integerEncoding = headerBuf.get() & 0xFF;
+ int logVectorSize = headerBuf.get() & 0xFF;
+ int numElements = headerBuf.getInt();
+
+ if (compressionMode != ALP_COMPRESSION_MODE) {
+ throw new ParquetDecodingException("Unsupported ALP compression mode: "
+ compressionMode);
+ }
+ if (integerEncoding != ALP_INTEGER_ENCODING_FOR) {
+ throw new ParquetDecodingException("Unsupported ALP integer encoding: "
+ integerEncoding);
+ }
+ if (logVectorSize < MIN_LOG_VECTOR_SIZE || logVectorSize >
MAX_LOG_VECTOR_SIZE) {
+ throw new ParquetDecodingException("Invalid ALP log vector size: " +
logVectorSize + ", must be between "
+ + MIN_LOG_VECTOR_SIZE + " and " + MAX_LOG_VECTOR_SIZE);
+ }
+ if (numElements < 0) {
+ throw new ParquetDecodingException("Invalid ALP element count: " +
numElements);
+ }
+ // ALP's num_elements is the count of non-null values that went through
encoding;
+ // valuesCount is the page row count, which is larger when the column has
nulls.
+ // The two are equal only for required (non-null) columns.
+ if (numElements > valuesCount) {
+ throw new ParquetDecodingException(
+ "ALP header element count " + numElements + " exceeds page
valuesCount " + valuesCount);
+ }
+
+ this.vectorSize = 1 << logVectorSize;
+ this.totalCount = numElements;
+
+ // Bound the vector count against the bytes actually present before
allocating anything.
+ // numElements is only capped by valuesCount, which a forged page can set
as high as
+ // Integer.MAX_VALUE, so computing this in int would overflow to a
negative count, and even
+ // without overflow a large count would drive a huge int[] and a huge
stream.slice allocation.
+ // Every vector costs a 4-byte offset entry plus at least its ALP and FOR
headers, which gives
+ // a hard ceiling on how many vectors the remaining bytes can possibly
describe.
+ int minVectorBytes = ALP_INFO_SIZE + forInfoSize();
+ long bodyBytes = stream.available();
+ long numVectorsLong = ((long) numElements + vectorSize - 1) / vectorSize;
+ long minBodyBytes = numVectorsLong * (Integer.BYTES + minVectorBytes);
+ if (minBodyBytes > bodyBytes) {
+ throw new ParquetDecodingException("ALP header element count " +
numElements + " requires at least "
+ + minBodyBytes + " bytes but only " + bodyBytes + " remain in the
page");
+ }
+ this.numVectors = (int) numVectorsLong;
+ this.pageValueIndex = 0;
+ this.currentVectorNumber = -1;
+
+ this.offsetArraySize = numVectors * Integer.BYTES;
+ ByteBuffer offsetBuf =
stream.slice(offsetArraySize).order(ByteOrder.LITTLE_ENDIAN);
+ this.vectorOffsets = new int[numVectors];
+ for (int v = 0; v < numVectors; v++) {
+ vectorOffsets[v] = offsetBuf.getInt();
+ }
+
+ // Slice remaining bytes into a 0-based view so decodeVector can use
+ // absolute get methods (vectorsData.get(pos)) directly.
+ int remainingBytes = (int) stream.available();
+ ByteBuffer rawSlice = stream.slice(remainingBytes);
+ this.vectorsData = rawSlice.slice().order(ByteOrder.LITTLE_ENDIAN);
+
+ validateVectorOffsets(minVectorBytes);
+
+ allocateDecodedBuffer(vectorSize);
+ this.excPositionsBuffer = new int[vectorSize];
+ }
+
+ /**
+ * Validates the offset array against the page body before any vector is
decoded. Offsets are
+ * relative to the start of the compression body (the offset array itself),
so the first vector
+ * must begin exactly where the offset array ends, offsets must increase by
at least one vector's
+ * fixed headers, and every vector must start early enough to fit those
headers. Without this a
+ * forged offset can point into another vector and silently decode the wrong
values.
+ */
+ private void validateVectorOffsets(int minVectorBytes) {
+ int bodyLimit = offsetArraySize + vectorsData.limit();
+ for (int v = 0; v < numVectors; v++) {
+ int offset = vectorOffsets[v];
+ if (v == 0) {
+ if (offset != offsetArraySize) {
+ throw new ParquetDecodingException("ALP first vector offset " +
offset
+ + " must equal the offset array size " + offsetArraySize);
+ }
+ } else if ((long) offset - vectorOffsets[v - 1] < minVectorBytes) {
+ throw new ParquetDecodingException("ALP vector offsets must increase
by at least "
+ + minVectorBytes + " bytes, but vector " + v + " starts at " +
offset + " after vector "
+ + (v - 1) + " at " + vectorOffsets[v - 1]);
+ }
+ if (offset > bodyLimit - minVectorBytes) {
+ throw new ParquetDecodingException("ALP vector " + v + " offset " +
offset
+ + " leaves no room for its headers before the end of the page body
at " + bodyLimit);
+ }
+ }
+ }
+
+ /**
+ * The position just past the last byte vector {@code vectorNumber} may
read, derived from the
+ * next vector's offset (or the end of the body for the final vector).
Review Comment:
Updated the javadoc to say it's a position in the vector data, not an offset
as the spec defines one.
##########
parquet-column/src/main/java/org/apache/parquet/column/values/alp/AlpCodec.java:
##########
@@ -0,0 +1,394 @@
+/*
+ * 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.parquet.column.values.alp;
+
+import static
org.apache.parquet.column.values.alp.AlpConstants.DOUBLE_MAX_EXPONENT;
+import static
org.apache.parquet.column.values.alp.AlpConstants.FLOAT_MAX_EXPONENT;
+
+import org.apache.parquet.bytes.BytesUtils;
+
+/**
+ * Core ALP (Adaptive Lossless floating-Point) encoding and decoding logic.
+ *
+ * <p>ALP works by converting floating-point values to integers using decimal
scaling,
+ * then applying Frame of Reference encoding and bit-packing.
+ * Values that cannot be losslessly converted are stored as exceptions.
+ *
+ * <p>Encoding formula: encoded = fastRound(value * POW10[e] *
POW10_NEGATIVE[f])
+ * <p>Decoding formula: value = encoded * POW10[f] * POW10_NEGATIVE[e]
+ *
+ * <p>The order of operations is critical for IEEE 754 correctness. Both
formulas must
+ * be evaluated as single expressions — storing the intermediate
multiplication result
+ * in a variable before the second multiply changes IEEE 754 rounding and
produces extra
+ * exceptions. Likewise, scaling uses multiply-by-reciprocal (via
POW10_NEGATIVE) rather than
+ * division: this reproduces the exact IEEE 754 rounding of the ALP reference
algorithm, so the
+ * encoded integers — and therefore which values become exceptions and the
resulting bytes — are
+ * identical across implementations. It is about cross-implementation
determinism, not any one
+ * language.
+ *
+ * <p>Exception conditions:
+ * <ul>
+ * <li>NaN values</li>
+ * <li>Infinity values</li>
+ * <li>Negative zero (-0.0)</li>
+ * <li>Out of integer range</li>
+ * <li>Round-trip failure (decode(encode(v)) != v)</li>
+ * </ul>
+ */
+final class AlpCodec {
+
+ // Magic numbers for the fast-rounding trick (see ALP paper, Section 3.2)
+ static final float MAGIC_FLOAT = 12_582_912.0f; // 2^22 + 2^23
+ static final double MAGIC_DOUBLE = 6_755_399_441_055_744.0; // 2^51 + 2^52
+
+ // POWERS_OF_TEN: positive powers used for scaling up during encode/decode.
+ // Encode: fastRound(value * POW10[e] * POW10_NEGATIVE[f])
+ // Decode: encoded * POW10[f] * POW10_NEGATIVE[e]
+ static final float[] FLOAT_POW10 = {1e0f, 1e1f, 1e2f, 1e3f, 1e4f, 1e5f,
1e6f, 1e7f, 1e8f, 1e9f, 1e10f};
+
+ static final double[] DOUBLE_POW10 = {
+ 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13,
1e14, 1e15, 1e16, 1e17, 1e18
+ };
+
+ // NEGATIVE_POWERS_OF_TEN: reciprocals used for scaling down
(multiply-by-reciprocal).
+ // Multiplying by a precomputed reciprocal instead of dividing keeps the
rounding bit-for-bit
+ // identical to the ALP reference implementation, so encoded values interop
across implementations.
+ static final float[] FLOAT_POW10_NEGATIVE = {
+ 1e0f, 1e-1f, 1e-2f, 1e-3f, 1e-4f, 1e-5f, 1e-6f, 1e-7f, 1e-8f, 1e-9f, 1e-10f
+ };
+
+ static final double[] DOUBLE_POW10_NEGATIVE = {
+ 1e0, 1e-1, 1e-2, 1e-3, 1e-4, 1e-5, 1e-6, 1e-7, 1e-8, 1e-9, 1e-10, 1e-11,
1e-12, 1e-13, 1e-14, 1e-15, 1e-16,
+ 1e-17, 1e-18
+ };
+
+ static final int FLOAT_NEGATIVE_ZERO_BITS = 0x80000000;
+ static final long DOUBLE_NEGATIVE_ZERO_BITS = 0x8000000000000000L;
+
+ private static final double ENCODING_UPPER_LIMIT = 9223372036854774784.0;
+ private static final double ENCODING_LOWER_LIMIT = -9223372036854774784.0;
+ private static final float FLOAT_ENCODING_UPPER_LIMIT = 2147483520.0f;
+ private static final float FLOAT_ENCODING_LOWER_LIMIT = -2147483520.0f;
+
+ private AlpCodec() {
+ // Utility class
+ }
+
+ /** NaN, Inf, and -0.0 can never be encoded regardless of exponent/factor. */
+ static boolean isIntrinsicFloatException(float value) {
+ if (Float.isNaN(value)) {
+ return true;
+ }
+ if (Float.isInfinite(value)) {
+ return true;
+ }
+ return Float.floatToRawIntBits(value) == FLOAT_NEGATIVE_ZERO_BITS;
+ }
+
+ /**
+ * Encodes {@code value} and reports whether it is an exception, doing the
scaling and rounding
+ * once and leaving the outcome in {@code out}.
+ *
+ * <p>Callers that need both the flag and the encoded value should use this
rather than
+ * {@link #isFloatException} followed by {@link #encodeFloat}: the exception
check has to encode
+ * the value to test the round trip, so the pair encodes twice. The scaled
intermediate is reused
+ * here too, so the two multiplies are also only done once. The expression
and its order match
+ * {@link #encodeFloat} exactly, which matters for cross-implementation bit
compatibility.
+ */
+ static void tryEncodeFloat(float value, int exponent, int factor,
EncodeResult out) {
+ if (isIntrinsicFloatException(value)) {
+ out.isException = true;
+ return;
+ }
+ // Check before rounding: overflow or non-finite after scaling
+ float scaled = value * FLOAT_POW10[exponent] *
FLOAT_POW10_NEGATIVE[factor];
+ if (!Float.isFinite(scaled) || scaled > FLOAT_ENCODING_UPPER_LIMIT ||
scaled < FLOAT_ENCODING_LOWER_LIMIT) {
+ out.isException = true;
+ return;
+ }
+ int encoded = fastRoundFloat(scaled);
+ float decoded = decodeFloat(encoded, exponent, factor);
+ if (Float.floatToRawIntBits(value) != Float.floatToRawIntBits(decoded)) {
+ out.isException = true;
+ return;
+ }
+ out.encoded = encoded;
+ out.isException = false;
+ }
+
+ /**
+ * Full exception check for a given (exponent, factor): intrinsic cases plus
round-trip failure.
+ * Prefer {@link #tryEncodeFloat} when the encoded value is wanted as well.
+ */
+ static boolean isFloatException(float value, int exponent, int factor) {
+ EncodeResult result = new EncodeResult();
+ tryEncodeFloat(value, exponent, factor, result);
+ return result.isException;
+ }
+
+ /** Round float to nearest integer using magic-number trick with sign
branching. */
+ static int fastRoundFloat(float value) {
+ if (value >= 0) {
+ return (int) ((value + MAGIC_FLOAT) - MAGIC_FLOAT);
+ } else {
+ return (int) ((value - MAGIC_FLOAT) + MAGIC_FLOAT);
+ }
+ }
+
+ static int encodeFloat(float value, int exponent, int factor) {
+ return fastRoundFloat(value * FLOAT_POW10[exponent] *
FLOAT_POW10_NEGATIVE[factor]);
+ }
+
+ static float decodeFloat(int encoded, int exponent, int factor) {
+ return encoded * FLOAT_POW10[factor] * FLOAT_POW10_NEGATIVE[exponent];
+ }
+
+ /** NaN, Inf, and -0.0 can never be encoded regardless of exponent/factor. */
+ static boolean isIntrinsicDoubleException(double value) {
+ if (Double.isNaN(value)) {
+ return true;
+ }
+ if (Double.isInfinite(value)) {
+ return true;
+ }
+ return Double.doubleToRawLongBits(value) == DOUBLE_NEGATIVE_ZERO_BITS;
+ }
+
+ /**
+ * Encodes {@code value} and reports whether it is an exception, doing the
scaling and rounding
+ * once and leaving the outcome in {@code out}. See {@link #tryEncodeFloat}
for why this exists.
+ */
+ static void tryEncodeDouble(double value, int exponent, int factor,
EncodeResult out) {
+ if (isIntrinsicDoubleException(value)) {
+ out.isException = true;
+ return;
+ }
+ // Check before rounding: overflow or non-finite after scaling
+ double scaled = value * DOUBLE_POW10[exponent] *
DOUBLE_POW10_NEGATIVE[factor];
+ if (!Double.isFinite(scaled) || scaled > ENCODING_UPPER_LIMIT || scaled <
ENCODING_LOWER_LIMIT) {
+ out.isException = true;
+ return;
+ }
+ long encoded = fastRoundDouble(scaled);
+ double decoded = decodeDouble(encoded, exponent, factor);
+ if (Double.doubleToRawLongBits(value) !=
Double.doubleToRawLongBits(decoded)) {
+ out.isException = true;
+ return;
+ }
+ out.encoded = encoded;
+ out.isException = false;
+ }
+
+ /**
+ * Full exception check for a given (exponent, factor): intrinsic cases plus
round-trip failure.
+ * Prefer {@link #tryEncodeDouble} when the encoded value is wanted as well.
+ */
+ static boolean isDoubleException(double value, int exponent, int factor) {
+ EncodeResult result = new EncodeResult();
+ tryEncodeDouble(value, exponent, factor, result);
+ return result.isException;
+ }
+
+ /** Round double to nearest integer using magic-number trick with sign
branching. */
+ static long fastRoundDouble(double value) {
+ if (value >= 0) {
+ return (long) ((value + MAGIC_DOUBLE) - MAGIC_DOUBLE);
+ } else {
+ return (long) ((value - MAGIC_DOUBLE) + MAGIC_DOUBLE);
+ }
+ }
+
+ static long encodeDouble(double value, int exponent, int factor) {
+ return fastRoundDouble(value * DOUBLE_POW10[exponent] *
DOUBLE_POW10_NEGATIVE[factor]);
+ }
+
+ static double decodeDouble(long encoded, int exponent, int factor) {
+ return encoded * DOUBLE_POW10[factor] * DOUBLE_POW10_NEGATIVE[exponent];
+ }
+
+ /**
+ * Outcome of a single {@link #tryEncodeFloat} or {@link #tryEncodeDouble}
call. Mutable and
+ * meant to be reused by the caller so the per-value hot path allocates
nothing; an Optional or a
+ * freshly allocated result here would box on every value. Not thread safe,
so each writer keeps
+ * its own.
+ */
+ static final class EncodeResult {
+ /** The encoded value, meaningful only when {@link #isException} is false.
*/
+ long encoded;
+
+ boolean isException;
+ }
+
+ public static class EncodingParams {
+ final int exponent;
+ final int factor;
+ final int numExceptions;
+
+ EncodingParams(int exponent, int factor, int numExceptions) {
+ this.exponent = exponent;
+ this.factor = factor;
+ this.numExceptions = numExceptions;
+ }
+ }
+
+ // Index positions within an (exponent, factor) pair array.
+ private static final int E = 0;
+ private static final int F = 1;
+
+ // All valid (exponent, factor) pairs for the full search, precomputed in
nested-loop order
+ // (e ascending, then f ascending) so the tie-break and early-exit behave
exactly like an inline
+ // double loop. Reused across every vector to avoid per-call allocation.
+ private static final int[][] ALL_VALID_FLOAT_PAIRS =
buildAllPairs(FLOAT_MAX_EXPONENT);
+ private static final int[][] ALL_VALID_DOUBLE_PAIRS =
buildAllPairs(DOUBLE_MAX_EXPONENT);
+
+ private static int[][] buildAllPairs(int maxExponent) {
+ int count = (maxExponent + 1) * (maxExponent + 2) / 2;
+ int[][] pairs = new int[count][];
+ int idx = 0;
+ for (int e = 0; e <= maxExponent; e++) {
+ for (int f = 0; f <= e; f++) {
+ pairs[idx++] = new int[] {e, f};
+ }
+ }
+ return pairs;
+ }
+
+ /** Try all (exponent, factor) combos and pick the one with the smallest
estimated compressed size. */
+ static EncodingParams findBestFloatParams(float[] values, int offset, int
length) {
+ return pickBestFloat(values, offset, length, ALL_VALID_FLOAT_PAIRS);
+ }
+
+ /** Same as findBestFloatParams but only tries the cached preset combos. */
+ static EncodingParams findBestFloatParamsWithPresets(float[] values, int
offset, int length, int[][] presets) {
+ return pickBestFloat(values, offset, length, presets);
+ }
+
+ /**
+ * Scores each (exponent, factor) pair by estimated compressed size and
returns the best.
+ *
+ * <p>Estimated size (in bits) = {@code length * bitWidth + exceptions *
(Float.SIZE + Short.SIZE)},
+ * where bitWidth is the number of bits needed to represent the signed range
(max - min) of
+ * non-exception encoded values after frame-of-reference subtraction,
matching the writer's FOR
+ * packing. This produces better compression ratios than minimizing
exception count alone. Ties in
+ * size are broken toward the higher exponent, then the higher factor. The
first pair (in {@code
+ * pairs} order) that encodes every value into a single FOR value with zero
exceptions wins
+ * outright. When no pair yields any non-exception values, {@code pairs[0]}
is returned.
+ */
+ private static EncodingParams pickBestFloat(float[] values, int offset, int
length, int[][] pairs) {
+ int bestExponent = pairs[0][E];
+ int bestFactor = pairs[0][F];
+ int bestExceptions = length;
+ long bestEstimatedSize = Long.MAX_VALUE;
+
+ // One reusable result for the whole search: every value below is encoded
exactly once.
+ EncodeResult result = new EncodeResult();
+ for (int[] pair : pairs) {
+ int e = pair[E];
+ int f = pair[F];
+ int exceptions = 0;
+ int minEncoded = Integer.MAX_VALUE;
+ int maxEncoded = Integer.MIN_VALUE;
+ for (int i = 0; i < length; i++) {
+ tryEncodeFloat(values[offset + i], e, f, result);
+ if (result.isException) {
+ exceptions++;
+ } else {
+ int encoded = (int) result.encoded;
+ if (encoded < minEncoded) minEncoded = encoded;
+ if (encoded > maxEncoded) maxEncoded = encoded;
+ }
+ }
+ int nonExceptions = length - exceptions;
+ if (nonExceptions == 0) continue;
+ // Signed subtraction gives the true FOR span; getWidthFromMaxLong
yields the correct
+ // unsigned bit width, and an overflowing large range is penalized with
64 bits. This matches
+ // the writer's FOR packing.
+ long delta = (nonExceptions < 2) ? 0 : ((long) maxEncoded - (long)
minEncoded);
+ int bitsPerValue = BytesUtils.getWidthFromMaxLong(delta);
+ long estimatedSize = (long) length * bitsPerValue + (long) exceptions *
(Float.SIZE + Short.SIZE);
+ if (estimatedSize < bestEstimatedSize
+ || (estimatedSize == bestEstimatedSize
+ && (e > bestExponent || (e == bestExponent && f > bestFactor))))
{
+ bestEstimatedSize = estimatedSize;
+ bestExponent = e;
+ bestFactor = f;
+ bestExceptions = exceptions;
+ if (bestExceptions == 0 && bitsPerValue == 0) {
+ return new EncodingParams(bestExponent, bestFactor, 0);
+ }
+ }
+ }
+ return new EncodingParams(bestExponent, bestFactor, bestExceptions);
+ }
+
+ /** Try all (exponent, factor) combos and pick the one with the smallest
estimated compressed size. */
+ static EncodingParams findBestDoubleParams(double[] values, int offset, int
length) {
+ return pickBestDouble(values, offset, length, ALL_VALID_DOUBLE_PAIRS);
+ }
+
+ /** Same as findBestDoubleParams but only tries the cached preset combos. */
+ static EncodingParams findBestDoubleParamsWithPresets(double[] values, int
offset, int length, int[][] presets) {
+ return pickBestDouble(values, offset, length, presets);
+ }
+
+ /** Double counterpart to {@link #pickBestFloat}; see it for the scoring and
tie-break rules. */
+ private static EncodingParams pickBestDouble(double[] values, int offset,
int length, int[][] pairs) {
+ int bestExponent = pairs[0][E];
+ int bestFactor = pairs[0][F];
+ int bestExceptions = length;
+ long bestEstimatedSize = Long.MAX_VALUE;
+
+ // One reusable result for the whole search: every value below is encoded
exactly once.
+ EncodeResult result = new EncodeResult();
+ for (int[] pair : pairs) {
+ int e = pair[E];
+ int f = pair[F];
+ int exceptions = 0;
+ long minEncoded = Long.MAX_VALUE;
+ long maxEncoded = Long.MIN_VALUE;
+ for (int i = 0; i < length; i++) {
+ tryEncodeDouble(values[offset + i], e, f, result);
Review Comment:
Thanks for digging into this, those numbers are really helpful. I agree it's
the full search over every (e, f) pair. The random doubles case is a good
catch: if the sample happens to contain only one encodable value it scores bit
width 0, while the whole vector needs around 60 bits, so sampling needs some
protection for vectors that are mostly exceptions. I'd rather not change what
the writer produces this close to the vote, so I opened #3863 to follow up,
using your numbers as the starting point.
--
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]
