You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by le...@apache.org on 2026/10/08 01:09:42 UTC
(datasketches-java) 01/01: Theta: fix EmptyCompactSketch preamble check for historical images
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch theta-empty-mask
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 988a333698a4af5e6f455ee52f8a43b014031dcd
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Wed Oct 7 18:09:32 2026 -0700
Theta: fix EmptyCompactSketch preamble check for historical images
The empty compact sketch check now uses a mask that ignores the ordered
flag, so it accepts empty images written by C++ before 3.3.0 and Java
before 1.0.0, which did not always set it. Bytes 3 and 4 must be zero
and reserved flag bits 0, 6 and 7 must be clear.
It also accepts the legacy 24-byte empty form (preamble longs 3) that
Java wrote before 1.0.0 for sketches with p < 1. That form must have no
retained entries and carry the expected seed hash.
CompactThetaSketch.heapify now applies the same check as wrap.
Co-Authored-By: Claude Opus 5.5 <no...@anthropic.com>
---
.../datasketches/theta/CompactThetaSketch.java | 7 ++-
.../datasketches/theta/EmptyCompactSketch.java | 38 +++++++++---
.../org/apache/datasketches/theta/EmptyTest.java | 70 ++++++++++++++++++++++
3 files changed, 105 insertions(+), 10 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/theta/CompactThetaSketch.java b/src/main/java/org/apache/datasketches/theta/CompactThetaSketch.java
index 5b784469c..10f2f4986 100644
--- a/src/main/java/org/apache/datasketches/theta/CompactThetaSketch.java
+++ b/src/main/java/org/apache/datasketches/theta/CompactThetaSketch.java
@@ -107,7 +107,8 @@ public abstract class CompactThetaSketch extends ThetaSketch {
final int flags = extractFlags(srcSeg);
final boolean srcOrdered = (flags & ORDERED_FLAG_MASK) != 0;
final boolean empty = (flags & EMPTY_FLAG_MASK) != 0;
- if (!empty) { PreambleUtil.checkSegmentSeedHash(srcSeg, expectedSeed); }
+ if (empty) { return EmptyCompactSketch.getHeapInstance(srcSeg, Util.computeSeedHash(expectedSeed)); }
+ PreambleUtil.checkSegmentSeedHash(srcSeg, expectedSeed);
return CompactOperations.segmentToCompact(srcSeg, srcOrdered, null);
}
//not SerVer 3 or 4
@@ -161,7 +162,7 @@ public abstract class CompactThetaSketch extends ThetaSketch {
if (serVer == 3) {
if (PreambleUtil.isEmptyFlag(srcSeg)) {
- return EmptyCompactSketch.getHeapInstance(srcSeg);
+ return EmptyCompactSketch.getHeapInstance(srcSeg, seedHash);
}
if (checkForSingleItem(srcSeg)) {
return SingleItemSketch.heapify(srcSeg, seedHash);
@@ -239,7 +240,7 @@ public abstract class CompactThetaSketch extends ThetaSketch {
if (serVer == 3) {
final int flags = bytes[FLAGS_BYTE];
if ((flags & EMPTY_FLAG_MASK) > 0) {
- return EmptyCompactSketch.getHeapInstance(MemorySegment.ofArray(bytes));
+ return EmptyCompactSketch.getHeapInstance(MemorySegment.ofArray(bytes), seedHash);
}
final int preLongs = bytes[PREAMBLE_LONGS_BYTE];
if (checkForSingleItem(preLongs, serVer, familyId, flags)) {
diff --git a/src/main/java/org/apache/datasketches/theta/EmptyCompactSketch.java b/src/main/java/org/apache/datasketches/theta/EmptyCompactSketch.java
index 1ebc47afe..27dc1de75 100644
--- a/src/main/java/org/apache/datasketches/theta/EmptyCompactSketch.java
+++ b/src/main/java/org/apache/datasketches/theta/EmptyCompactSketch.java
@@ -20,11 +20,16 @@
package org.apache.datasketches.theta;
import static java.lang.foreign.ValueLayout.JAVA_BYTE;
+import static java.lang.foreign.ValueLayout.JAVA_INT_UNALIGNED;
import static java.lang.foreign.ValueLayout.JAVA_LONG_UNALIGNED;
+import static java.lang.foreign.ValueLayout.JAVA_SHORT_UNALIGNED;
+import static org.apache.datasketches.theta.PreambleUtil.RETAINED_ENTRIES_INT;
+import static org.apache.datasketches.theta.PreambleUtil.SEED_HASH_SHORT;
import java.lang.foreign.MemorySegment;
import org.apache.datasketches.common.SketchesArgumentException;
+import org.apache.datasketches.common.Util;
/**
* Singleton Empty CompactThetaSketch.
@@ -33,12 +38,23 @@ import org.apache.datasketches.common.SketchesArgumentException;
*/
final class EmptyCompactSketch extends CompactThetaSketch {
- // For backward compatibility, a candidate EmptyCompactSketch
- // must have Flags: compact, empty, read-only;
- // and bytes: COMPACT-Family=3, SerVer=3, PreLongs=1; and be exactly 8 bytes long.
- // NOTE: The seedHash bytes are ignored
- private static final long EMPTY_SKETCH_MASK = 0X00_00_FF_FF_FF_FF_FF_FFL;
- private static final long EMPTY_SKETCH_TEST = 0X00_00_1E_00_00_03_03_01L;
+ // The MASK selects which bits of the first 8 bytes are examined; it must accept historical images.
+ // The TEST gives the required values of the examined bits; it must lie within the MASK.
+ // The ARR is what we write going forward; (ARR & MASK) must equal TEST.
+ //
+ // A candidate EmptyCompactSketch must have
+ // bytes: PreLongs=1, SerVer=3, COMPACT-Family=3, bytes 3,4 = 0 (not used by compact);
+ // flags: read-only, empty, compact set; single-item and reserved bits 0, 6, 7 clear.
+ // The ordered flag is ignored: Java before 1.0.0 and C++ before 3.3.0 wrote empty images without it.
+ // The reserved flag bits must be zero for SerVer 3. Any future use of them requires a new SerVer.
+ // The seedHash bytes are ignored: they may be 0 or the seed hash, depending on the writer.
+ //
+ // Legacy form: versions before 1.0.0 wrote empty sketches with p < 1 in the full 24-byte form,
+ // with PreLongs=3 and theta = p. These must pass EMPTY_SKETCH_TEST_LEGACY, have zero retained
+ // entries and carry the expected seed hash. Empty implies theta = 1.0, so theta is ignored.
+ static final long EMPTY_SKETCH_MASK = 0X00_00_EF_FF_FF_FF_FF_FFL;
+ static final long EMPTY_SKETCH_TEST = 0X00_00_0E_00_00_03_03_01L;
+ static final long EMPTY_SKETCH_TEST_LEGACY = 0X00_00_0E_00_00_03_03_03L;
//When returning a byte array the following flags are set: ordered, compact, empty, read-only
static final byte[] EMPTY_COMPACT_SKETCH_ARR = { 1, 3, 3, 0, 0, 0x1E, 0, 0 };
private static final EmptyCompactSketch EMPTY_COMPACT_SKETCH = new EmptyCompactSketch();
@@ -50,11 +66,19 @@ final class EmptyCompactSketch extends CompactThetaSketch {
}
//This is effectively a heapify
- static EmptyCompactSketch getHeapInstance(final MemorySegment srcSeg) {
+ static EmptyCompactSketch getHeapInstance(final MemorySegment srcSeg, final short expectedSeedHash) {
final long pre0 = srcSeg.get(JAVA_LONG_UNALIGNED, 0);
if (testCandidatePre0(pre0)) {
return EMPTY_COMPACT_SKETCH;
}
+ if ((pre0 & EMPTY_SKETCH_MASK) == EMPTY_SKETCH_TEST_LEGACY) {
+ if ((srcSeg.byteSize() < 24) || (srcSeg.get(JAVA_INT_UNALIGNED, RETAINED_ENTRIES_INT) != 0)) {
+ throw new SketchesArgumentException(
+ "Input MemorySegment is a legacy empty image, but is too short or has retained entries.");
+ }
+ Util.checkSeedHashes(expectedSeedHash, srcSeg.get(JAVA_SHORT_UNALIGNED, SEED_HASH_SHORT));
+ return EMPTY_COMPACT_SKETCH;
+ }
final long maskedPre0 = pre0 & EMPTY_SKETCH_MASK;
throw new SketchesArgumentException("Input MemorySegment does not match required Preamble. "
+ "MemorySegment Pre0: " + Long.toHexString(maskedPre0)
diff --git a/src/test/java/org/apache/datasketches/theta/EmptyTest.java b/src/test/java/org/apache/datasketches/theta/EmptyTest.java
index fec264b26..f44bef9bb 100644
--- a/src/test/java/org/apache/datasketches/theta/EmptyTest.java
+++ b/src/test/java/org/apache/datasketches/theta/EmptyTest.java
@@ -19,12 +19,16 @@
package org.apache.datasketches.theta;
+import static java.lang.foreign.ValueLayout.JAVA_LONG_UNALIGNED;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertTrue;
+import static org.testng.Assert.fail;
import java.lang.foreign.MemorySegment;
+import org.apache.datasketches.common.SketchesArgumentException;
+import org.apache.datasketches.common.Util;
import org.testng.annotations.Test;
/**
@@ -114,6 +118,72 @@ public class EmptyTest {
assertEquals(csk2.getCurrentPreambleLongs(), 1);
}
+ @Test
+ public void checkEmptyMaskTestArrInvariants() {
+ final long mask = EmptyCompactSketch.EMPTY_SKETCH_MASK;
+ final long test = EmptyCompactSketch.EMPTY_SKETCH_TEST;
+ final long arr = MemorySegment.ofArray(EmptyCompactSketch.EMPTY_COMPACT_SKETCH_ARR)
+ .get(JAVA_LONG_UNALIGNED, 0);
+ assertEquals(test & ~mask, 0L); //the TEST must lie within the MASK
+ assertEquals(arr & mask, test); //our own output must pass
+ assertEquals(EmptyCompactSketch.EMPTY_SKETCH_TEST_LEGACY & ~mask, 0L);
+ }
+
+ @Test
+ public void checkEmptyAcceptsHistoricalImages() {
+ //Java image: ordered flag set, seed hash 0
+ checkEmptyAccepted(new byte[] { 1, 3, 3, 0, 0, 0x1E, 0, 0 });
+ //C++ image: ordered flag set, seed hash present
+ checkEmptyAccepted(new byte[] { 1, 3, 3, 0, 0, 0x1E, (byte) 0xCC, (byte) 0x93 });
+ //C++ before 3.3.0: ordered flag not set
+ checkEmptyAccepted(new byte[] { 1, 3, 3, 0, 0, 0x0E, (byte) 0xCC, (byte) 0x93 });
+ //sketches-core 0.9.0, p = 0.5: full 24-byte form, count = 0, p = 1.0f, theta = 0.5
+ checkEmptyAccepted(legacyEmptyP05((byte) 0x1E, 0)); //ordered
+ checkEmptyAccepted(legacyEmptyP05((byte) 0x0E, 0)); //unordered
+ }
+
+ private static byte[] legacyEmptyP05(final byte flags, final int count) {
+ return new byte[] {
+ 3, 3, 3, 0, 0, flags, (byte) 0xCC, (byte) 0x93,
+ (byte) count, 0, 0, 0, 0, 0, (byte) 0x80, 0x3F,
+ 0, 0, 0, 0, 0, 0, 0, 0x40 };
+ }
+
+ @Test
+ public void checkEmptyRejectsMangledImages() {
+ checkEmptyRejected(new byte[] { 1, 3, 3, 1, 0, 0x1E, 0, 0 }); //byte 3 not zero
+ checkEmptyRejected(new byte[] { 1, 3, 3, 0, 1, 0x1E, 0, 0 }); //byte 4 not zero
+ checkEmptyRejected(new byte[] { 1, 3, 3, 0, 0, 0x1F, 0, 0 }); //reserved bit 0 set
+ checkEmptyRejected(new byte[] { 1, 3, 3, 0, 0, 0x5E, 0, 0 }); //reserved bit 6 set
+ checkEmptyRejected(new byte[] { 1, 3, 3, 0, 0, (byte) 0x9E, 0, 0 }); //reserved bit 7 set
+ checkEmptyRejected(new byte[] { 1, 3, 3, 0, 0, 0x3E, 0, 0 }); //single-item set
+ checkEmptyRejected(new byte[] { 1, 3, 3, 0, 0, 0x1C, 0, 0 }); //read-only not set
+ checkEmptyRejected(new byte[] { 1, 3, 3, 0, 0, 0x16, 0, 0 }); //compact not set
+ checkEmptyRejected(new byte[] { 2, 3, 3, 0, 0, 0x1E, 0, 0 }); //preLongs 2
+ checkEmptyRejected(legacyEmptyP05((byte) 0x1E, 1)); //preLongs 3, count not 0
+ checkEmptyRejected(new byte[] { 3, 3, 3, 0, 0, 0x1E, 0, 0 }); //preLongs 3, too short
+ final byte[] wrongSeed = legacyEmptyP05((byte) 0x1E, 0);
+ wrongSeed[6] = 0; wrongSeed[7] = 0;
+ checkEmptyRejected(wrongSeed); //preLongs 3, seed hash mismatch
+ }
+
+ private static void checkEmptyAccepted(final byte[] image) {
+ final long seed = Util.DEFAULT_UPDATE_SEED;
+ assertTrue(CompactThetaSketch.heapify(MemorySegment.ofArray(image), seed) instanceof EmptyCompactSketch);
+ assertTrue(CompactThetaSketch.wrap(MemorySegment.ofArray(image), seed) instanceof EmptyCompactSketch);
+ assertTrue(CompactThetaSketch.wrap(image, seed) instanceof EmptyCompactSketch);
+ }
+
+ private static void checkEmptyRejected(final byte[] image) {
+ final long seed = Util.DEFAULT_UPDATE_SEED;
+ try { CompactThetaSketch.heapify(MemorySegment.ofArray(image), seed); fail("heapify"); }
+ catch (final SketchesArgumentException e) { /* expected */ }
+ try { CompactThetaSketch.wrap(MemorySegment.ofArray(image), seed); fail("wrap segment"); }
+ catch (final SketchesArgumentException e) { /* expected */ }
+ try { CompactThetaSketch.wrap(image, seed); fail("wrap bytes"); }
+ catch (final SketchesArgumentException e) { /* expected */ }
+ }
+
/**
* @param s value to print
*/
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org