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:41 UTC

(datasketches-java) branch theta-empty-mask created (now 988a33369)

This is an automated email from the ASF dual-hosted git repository.

leerho pushed a change to branch theta-empty-mask
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git


      at 988a33369 Theta: fix EmptyCompactSketch preamble check for historical images

This branch includes the following new commits:

     new 988a33369 Theta: fix EmptyCompactSketch preamble check for historical images

The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails.  The revisions
listed as "add" were already present in the repository and have only
been added to this reference.



---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org


(datasketches-java) 01/01: Theta: fix EmptyCompactSketch preamble check for historical images

Posted by le...@apache.org.
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