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

leerho pushed a commit to branch 9.1.X
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git

commit c95fb7c9019b342a3406feafa4d2daf39791979f
Author: Lee Rhodes <[email protected]>
AuthorDate: Thu Oct 29 14:28:46 2026 -0700

    Frequencies: check map sizes and item counts in binary images
    
    In FrequentLongsSketch.getInstance(MemorySegment) and
    FrequentItemsSketch.getInstance(MemorySegment, serDe):
    
    - Check that LG_MIN_MAP_SIZE <= lgCurMapSize <= lgMaxMapSize, and that
      activeItems is between 0 and the capacity of the current map, as C++
      check_size() does.
    - Check, in long arithmetic, that the image holds the declared arrays.
    - Rebuild the sketch into a map just large enough for the active items. The
      map grows as needed.
    
    Co-Authored-By: Claude Opus 5.5 <[email protected]>
---
 .../frequencies/FrequentItemsSketch.java           | 15 ++++---
 .../frequencies/FrequentLongsSketch.java           | 15 ++++---
 .../org/apache/datasketches/frequencies/Util.java  | 36 +++++++++++++++
 .../datasketches/frequencies/ItemsSketchTest.java  | 33 ++++++++++++++
 .../datasketches/frequencies/LongsSketchTest.java  | 51 ++++++++++++++++++++++
 5 files changed, 138 insertions(+), 12 deletions(-)

diff --git 
a/src/main/java/org/apache/datasketches/frequencies/FrequentItemsSketch.java 
b/src/main/java/org/apache/datasketches/frequencies/FrequentItemsSketch.java
index 29967491f..a662a9e10 100644
--- a/src/main/java/org/apache/datasketches/frequencies/FrequentItemsSketch.java
+++ b/src/main/java/org/apache/datasketches/frequencies/FrequentItemsSketch.java
@@ -43,6 +43,7 @@ import static 
org.apache.datasketches.frequencies.PreambleUtil.insertPreLongs;
 import static org.apache.datasketches.frequencies.PreambleUtil.insertSerVer;
 import static org.apache.datasketches.frequencies.Util.LG_MIN_MAP_SIZE;
 import static org.apache.datasketches.frequencies.Util.SAMPLE_SIZE;
+import static org.apache.datasketches.frequencies.Util.checkMapSizes;
 import static org.apache.datasketches.frequencies.Util.checkStreamWeight;
 
 import java.lang.foreign.MemorySegment;
@@ -275,17 +276,19 @@ public class FrequentItemsSketch<T> {
     MemorySegment.copy(srcSeg, JAVA_LONG_UNALIGNED, 0, preArr, 0, preLongs);
     checkStreamWeight(preArr[2]);
 
-    final FrequentItemsSketch<T> fis = new FrequentItemsSketch<>(lgMaxMapSize, 
lgCurMapSize);
-    fis.streamWeight = 0; //update after
-    fis.offset = preArr[3];
-
     final int preBytes = preLongs << 3;
     final int activeItems = extractActiveItems(preArr[1]);
+    final int lgStartMapSize =
+        checkMapSizes(lgMaxMapSize, lgCurMapSize, activeItems, 
ReversePurgeItemHashMap.getLoadFactor());
+    final long reqBytes = (preBytes + ((long)activeItems * Long.BYTES)); 
//count Arr only
+    checkBounds(0, reqBytes, srcSeg.byteSize()); //check MemorySegment 
capacity before allocating
+
+    final FrequentItemsSketch<T> fis = new FrequentItemsSketch<>(lgMaxMapSize, 
lgStartMapSize);
+    fis.streamWeight = 0; //update after
+    fis.offset = preArr[3];
 
     //Get countArray
     final long[] countArray = new long[activeItems];
-    final long reqBytes = (preBytes + ((long)activeItems * Long.BYTES)); 
//count Arr only
-    checkBounds(0, reqBytes, srcSeg.byteSize()); //check MemorySegment capacity
 
     MemorySegment.copy(srcSeg, JAVA_LONG_UNALIGNED, preBytes, countArray, 0, 
activeItems);
 
diff --git 
a/src/main/java/org/apache/datasketches/frequencies/FrequentLongsSketch.java 
b/src/main/java/org/apache/datasketches/frequencies/FrequentLongsSketch.java
index 4d5935d76..81da5c8b9 100644
--- a/src/main/java/org/apache/datasketches/frequencies/FrequentLongsSketch.java
+++ b/src/main/java/org/apache/datasketches/frequencies/FrequentLongsSketch.java
@@ -42,6 +42,7 @@ import static 
org.apache.datasketches.frequencies.PreambleUtil.insertPreLongs;
 import static org.apache.datasketches.frequencies.PreambleUtil.insertSerVer;
 import static org.apache.datasketches.frequencies.Util.LG_MIN_MAP_SIZE;
 import static org.apache.datasketches.frequencies.Util.SAMPLE_SIZE;
+import static org.apache.datasketches.frequencies.Util.checkMapSizes;
 import static org.apache.datasketches.frequencies.Util.checkStreamWeight;
 
 import java.lang.foreign.MemorySegment;
@@ -278,17 +279,19 @@ public class FrequentLongsSketch {
     MemorySegment.copy(srcSeg, JAVA_LONG_UNALIGNED, 0, preArr, 0, preLongs);
     checkStreamWeight(preArr[2]);
 
-    final FrequentLongsSketch fls = new FrequentLongsSketch(lgMaxMapSize, 
lgCurMapSize);
-    fls.streamWeight = 0; //update after
-    fls.offset = preArr[3];
-
     final int preBytes = preLongs << 3;
     final int activeItems = extractActiveItems(preArr[1]);
+    final int lgStartMapSize =
+        checkMapSizes(lgMaxMapSize, lgCurMapSize, activeItems, 
ReversePurgeLongHashMap.getLoadFactor());
+    final long reqBytes = preBytes + (2L * activeItems * Long.BYTES); //count 
Arr + Items Arr
+    checkBounds(0, reqBytes, srcSeg.byteSize()); //check MemorySegment 
capacity before allocating
+
+    final FrequentLongsSketch fls = new FrequentLongsSketch(lgMaxMapSize, 
lgStartMapSize);
+    fls.streamWeight = 0; //update after
+    fls.offset = preArr[3];
 
     //Get countArray
     final long[] countArray = new long[activeItems];
-    final int reqBytes = preBytes + (2 * activeItems * Long.BYTES); //count 
Arr + Items Arr
-    checkBounds(0, reqBytes, srcSeg.byteSize()); //check MemorySegment capacity
     MemorySegment.copy(srcSeg, JAVA_LONG_UNALIGNED, preBytes, countArray, 0, 
activeItems);
 
     //Get itemArray
diff --git a/src/main/java/org/apache/datasketches/frequencies/Util.java 
b/src/main/java/org/apache/datasketches/frequencies/Util.java
index f17d98402..bbdadd59a 100644
--- a/src/main/java/org/apache/datasketches/frequencies/Util.java
+++ b/src/main/java/org/apache/datasketches/frequencies/Util.java
@@ -53,6 +53,42 @@ final class Util {
     return key;
   }
 
+  /**
+   * Checks the map sizes and the number of active items read from the 
serialized image of a
+   * non-empty sketch, and returns the log2 size of the map to rebuild the 
sketch into.
+   *
+   * <p>The returned size is just large enough to hold the active items, and 
no larger than
+   * <i>lgCurMapSize</i>. The map then grows as needed while the items are 
inserted, so the memory
+   * allocated is bounded by the size of the image, not by the declared map 
size.</p>
+   *
+   * @param lgMaxMapSize log2 of the maximum map size
+   * @param lgCurMapSize log2 of the current map size
+   * @param activeItems the number of active items
+   * @param loadFactor the load factor of the hash map
+   * @return log2 of the map size to rebuild into
+   * @throws SketchesArgumentException if the values are not consistent
+   */
+  static int checkMapSizes(final int lgMaxMapSize, final int lgCurMapSize, 
final int activeItems,
+      final double loadFactor) {
+    if (lgCurMapSize < LG_MIN_MAP_SIZE) {
+      throw new SketchesArgumentException(
+          "Possible Corruption: LgCurMapSize must be at least " + 
LG_MIN_MAP_SIZE + ": " + lgCurMapSize);
+    }
+    if (lgCurMapSize > lgMaxMapSize) {
+      throw new SketchesArgumentException(
+          "Possible Corruption: LgCurMapSize must not exceed LgMaxMapSize: "
+            + lgCurMapSize + " > " + lgMaxMapSize);
+    }
+    final long maxActive = (long) ((1L << Math.min(lgCurMapSize, 62)) * 
loadFactor);
+    if ((activeItems < 0) || (activeItems > maxActive)) {
+      throw new SketchesArgumentException(
+          "Possible Corruption: ActiveItems exceeds map capacity: " + 
activeItems);
+    }
+    int lgStart = LG_MIN_MAP_SIZE;
+    while ((lgStart < lgCurMapSize) && (((1L << lgStart) * loadFactor) < 
activeItems)) { lgStart++; }
+    return lgStart;
+  }
+
   /**
    * Checks the stream weight read from the serialized image of a non-empty 
sketch.
    * @param streamWeight the stream weight
diff --git 
a/src/test/java/org/apache/datasketches/frequencies/ItemsSketchTest.java 
b/src/test/java/org/apache/datasketches/frequencies/ItemsSketchTest.java
index 73583a3ae..d0507f768 100644
--- a/src/test/java/org/apache/datasketches/frequencies/ItemsSketchTest.java
+++ b/src/test/java/org/apache/datasketches/frequencies/ItemsSketchTest.java
@@ -506,4 +506,37 @@ public class ItemsSketchTest {
   static void println(final String s) {
     //System.out.println(s); //disable here
   }
+
+  private static byte[] itemsImage() {
+    final FrequentItemsSketch<Long> fis = new FrequentItemsSketch<>(1 << 10);
+    for (long i = 0; i < 5; i++) { fis.update(i, i + 1); }
+    return fis.toByteArray(new ArrayOfLongsSerDe());
+  }
+
+  @Test
+  public void checkBinaryDeserLargeDeclaredMapDoesNotAllocate() {
+    final byte[] bytes = itemsImage();
+    bytes[PreambleUtil.LG_MAX_MAP_SIZE_BYTE] = 30;
+    bytes[PreambleUtil.LG_CUR_MAP_SIZE_BYTE] = 30;
+    final MemorySegment seg = MemorySegment.ofArray(bytes);
+    final long allocated = 
org.apache.datasketches.common.AllocationTracker.allocatedBytes(
+        () -> FrequentItemsSketch.getInstance(seg, new ArrayOfLongsSerDe()));
+    assertTrue(allocated < (1 << 20), "allocated " + allocated);
+    final FrequentItemsSketch<Long> fis = FrequentItemsSketch.getInstance(seg, 
new ArrayOfLongsSerDe());
+    assertEquals(fis.getNumActiveItems(), 5);
+    assertEquals(fis.getEstimate(4L), 5);
+  }
+
+  @Test
+  public void checkBinaryDeserInconsistentSizes() {
+    final byte[] curTooBig = itemsImage();
+    curTooBig[PreambleUtil.LG_CUR_MAP_SIZE_BYTE] = (byte) 
(curTooBig[PreambleUtil.LG_MAX_MAP_SIZE_BYTE] + 1);
+    final byte[] tooManyActive = itemsImage();
+    org.apache.datasketches.common.ByteArrayUtil.putIntLE(tooManyActive, 8, 1 
<< 20);
+    for (final byte[] b : new byte[][] {curTooBig, tooManyActive}) {
+      try { FrequentItemsSketch.getInstance(MemorySegment.ofArray(b), new 
ArrayOfLongsSerDe()); fail(); }
+      catch (final SketchesArgumentException e) { }
+    }
+  }
+
 }
diff --git 
a/src/test/java/org/apache/datasketches/frequencies/LongsSketchTest.java 
b/src/test/java/org/apache/datasketches/frequencies/LongsSketchTest.java
index b6527b178..6326f499e 100644
--- a/src/test/java/org/apache/datasketches/frequencies/LongsSketchTest.java
+++ b/src/test/java/org/apache/datasketches/frequencies/LongsSketchTest.java
@@ -796,4 +796,55 @@ public class LongsSketchTest {
     return new FrequentLongsSketch(maxMapSize);
   }
 
+
+  private static byte[] longsImage() {
+    final FrequentLongsSketch fls = new FrequentLongsSketch(1 << 10);
+    for (int i = 0; i < 5; i++) { fls.update(i, i + 1); }
+    return fls.toByteArray();
+  }
+
+  @Test
+  public void checkBinaryDeserLargeDeclaredMapDoesNotAllocate() {
+    final byte[] bytes = longsImage();
+    bytes[PreambleUtil.LG_MAX_MAP_SIZE_BYTE] = 30;
+    bytes[PreambleUtil.LG_CUR_MAP_SIZE_BYTE] = 30;
+    final MemorySegment seg = MemorySegment.ofArray(bytes);
+    final long allocated = 
org.apache.datasketches.common.AllocationTracker.allocatedBytes(
+        () -> FrequentLongsSketch.getInstance(seg));
+    assertTrue(allocated < (1 << 20), "allocated " + allocated);
+    final FrequentLongsSketch fls = FrequentLongsSketch.getInstance(seg);
+    assertEquals(fls.getNumActiveItems(), 5);
+    assertEquals(fls.getEstimate(4), 5);
+  }
+
+  @Test
+  public void checkBinaryDeserInconsistentSizes() {
+    final byte[] curTooBig = longsImage();
+    curTooBig[PreambleUtil.LG_CUR_MAP_SIZE_BYTE] = (byte) 
(curTooBig[PreambleUtil.LG_MAX_MAP_SIZE_BYTE] + 1);
+    final byte[] curTooSmall = longsImage();
+    curTooSmall[PreambleUtil.LG_CUR_MAP_SIZE_BYTE] = 2;
+    final byte[] tooManyActive = longsImage();
+    org.apache.datasketches.common.ByteArrayUtil.putIntLE(tooManyActive, 8, 1 
<< 20);
+    final byte[] negActive = longsImage();
+    org.apache.datasketches.common.ByteArrayUtil.putIntLE(negActive, 8, -1);
+    for (final byte[] b : new byte[][] {curTooBig, curTooSmall, tooManyActive, 
negActive}) {
+      try { FrequentLongsSketch.getInstance(MemorySegment.ofArray(b)); fail(); 
}
+      catch (final SketchesArgumentException e) { }
+    }
+  }
+
+  @Test
+  public void checkBinaryDeserActiveItemsBeyondImage() {
+    final byte[] bytes = longsImage();
+    bytes[PreambleUtil.LG_MAX_MAP_SIZE_BYTE] = 30;
+    bytes[PreambleUtil.LG_CUR_MAP_SIZE_BYTE] = 30;
+    org.apache.datasketches.common.ByteArrayUtil.putIntLE(bytes, 8, 1 << 28); 
//more items than the image holds
+    final MemorySegment seg = MemorySegment.ofArray(bytes);
+    final long allocated = 
org.apache.datasketches.common.AllocationTracker.allocatedBytes(
+        () -> FrequentLongsSketch.getInstance(seg));
+    assertTrue(allocated < (1 << 20), "allocated " + allocated);
+    try { FrequentLongsSketch.getInstance(seg); fail(); }
+    catch (final SketchesArgumentException e) { }
+  }
+
 }


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to