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

leerho pushed a commit to branch kll-weighted-update
in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git

commit ab49552a67bfb572469c05b2e607571a4bc25f9f
Author: Shani Elharrar <[email protected]>
AuthorDate: Wed Oct 7 14:09:04 2026 +0300

    Fix infinite loop in kll_helper::floor_of_log2_of_fraction for large 
numerators
    
    Doubling denom until it exceeds numer overflows to zero once numer >= 2^63,
    so the loop never terminated. ub_on_num_levels(n) calls it with the merged
    stream weight, which made a merge reaching n >= 2^63 hang. Compare against
    numer / 2 instead, which is equivalent and cannot overflow.
    
    Co-Authored-By: Claude Opus 5.5 <[email protected]>
---
 kll/include/kll_helper_impl.hpp | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/kll/include/kll_helper_impl.hpp b/kll/include/kll_helper_impl.hpp
index 7f958677..e8dc073e 100644
--- a/kll/include/kll_helper_impl.hpp
+++ b/kll/include/kll_helper_impl.hpp
@@ -39,8 +39,9 @@ uint8_t kll_helper::floor_of_log2_of_fraction(uint64_t numer, 
uint64_t denom) {
   if (denom > numer) { return 0; }
   uint8_t count = 0;
   while (true) {
+    // denom * 2 > numer, without overflowing denom
+    if (denom > (numer >> 1)) { return count; }
     denom <<= 1;
-    if (denom > numer) { return count; }
     count++;
   }
 }


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

Reply via email to