Repository: mwlon/pcodec (language: python)

Issue:
logic bugs in q_compress rust crate
I've been fuzzing a little project using q_compress in Rust, and managed to find some weird corner cases in the compressor/decompressor.

Minimal Reproduction Case:
```rust
#!/usr/bin/env -S cargo -Zscript
---
[dependencies]
q_compress = "0.11.7"
---

fn main() {
    use q_compress::{Compressor, Decompressor, DecompressorConfig, CompressorConfig};
    use std::io::Write;

    let a = f64::from_bits(0x8000000000004000);
    let b = f64::from_bits(0x8000000000000000);
    let cfg = CompressorConfig::default()
        .with_use_gcds(false)
        .with_delta_encoding_order(1)
        .with_compression_level(8);
    let mut compressor = Compressor::<f64>::from_config(cfg);
    let compressed = compressor.simple_compress(&[a, -a, b]);
    let mut decompressor: Decompressor<f64> = Decompressor::from_config(DecompressorConfig::default());
    decompressor.write_all(&compressed).unwrap();
    let decompressed = decompressor.simple_decompress().unwrap();
    assert_eq!(&[a, -a, b], decompressed.as_slice());
}
```

The above script tests a compress/decompress roundtrip using minimal input.
When run in debug mode, the code panics due to a "subtract with overflow" error in q_compress: 
`thread 'main' panicked at /home/crux/.cache/cargo/registry/src/index.crates.io-6f17d22bba15001f/q_compress-0.11.7/src/prefix.rs:89:29:
attempt to subtract with overflow`

running in release mode, all overflow checks are disabled.
the program still crashes at the `simple_decompress().unwrap()` call:
`called `Result::unwrap()` on an `Err` value: QCompressError { kind: Corruption, message: "expected the compressed body to contain 136 bits but instead processed 128" }`



Discussion / hints:
Cool, thanks for fuzzing and sharing those details!

q_compress has been succeeded by pco now, and it's highly recommended to switch. Pco does not express this particular issue, and the code is generally better written. Do you want to start fuzzing Pco instead, if you aren't already?

That said, I see the issue and will make a fix since I think there might still be a few q_compress users out there.
I'll check out the pco apis, thanks

Fix patch:
diff --git a/quantile-compression/q_compress/src/prefix.rs b/quantile-compression/q_compress/src/prefix.rs
index a5c32789..51fbf512 100644
--- a/quantile-compression/q_compress/src/prefix.rs
+++ b/quantile-compression/q_compress/src/prefix.rs
@@ -86,7 +86,11 @@ impl<T: NumberLike> Prefix<T> {
     } else {
       (T::Unsigned::ONE << k) - T::Unsigned::ONE
     };
-    let only_k_bits_lower = diff - only_k_bits_upper;
+    let only_k_bits_lower = if diff >= only_k_bits_upper {
+      diff - only_k_bits_upper
+    } else {
+      T::Unsigned::ZERO
+    };
 
     KInfo {
       k,


Test patch:
diff --git a/quantile-compression/q_compress/src/tests/recovery.rs b/quantile-compression/q_compress/src/tests/recovery.rs
index 8040aa4e..b3e8f12c 100644
--- a/quantile-compression/q_compress/src/tests/recovery.rs
+++ b/quantile-compression/q_compress/src/tests/recovery.rs
@@ -204,6 +204,15 @@ fn test_sparse_islands() {
   assert_recovers(nums, 4, "sparse islands");
 }
 
+#[test]
+fn test_issue_229() {
+  // this example once caused an underflow or downstream panic
+  let a = f64::from_bits(0x8000000000004000);
+  let b = f64::from_bits(0x8000000000000000);
+  let nums = vec![a, -a, b];
+  assert_recovers(nums, 8, "issue_229");
+}
+
 fn assert_recovers<T: NumberLike>(nums: Vec<T>, compression_level: usize, name: &str) {
   for delta_encoding_order in [0, 1, 7] {
     for use_gcds in [false, true] {