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

tisonkun pushed a commit to branch docs/input-hashing-rfc
in repository https://gitbox.apache.org/repos/asf/datasketches-tck.git

commit e320febe048a4b9789fe032ea44c5aae63c590f3
Author: tison <[email protected]>
AuthorDate: Wed Nov 18 17:40:22 2026 +0800

    docs: propose a cross-language input hashing contract
    
    Signed-off-by: tison <[email protected]>
---
 rfcs/0000-input-hashing.md | 78 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 78 insertions(+)

diff --git a/rfcs/0000-input-hashing.md b/rfcs/0000-input-hashing.md
new file mode 100644
index 0000000..ab00c79
--- /dev/null
+++ b/rfcs/0000-input-hashing.md
@@ -0,0 +1,78 @@
+<!--
+  Licensed to the Apache Software Foundation (ASF) under one or more
+  contributor license agreements. See the NOTICE file distributed with
+  this work for additional information regarding copyright ownership.
+  The ASF licenses this file to You under the Apache License, Version 2.0
+  (the "License"); you may not use this file except in compliance with
+  the License. You may obtain a copy of the License at
+
+      http://www.apache.org/licenses/LICENSE-2.0
+
+  Unless required by applicable law or agreed to in writing, software
+  distributed under the License is distributed on an "AS IS" BASIS,
+  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+  See the License for the specific language governing permissions and
+  limitations under the License.
+-->
+
+# RFC 0000: Input hashing
+
+**Draft.** This proposal defines the bytes that interoperable sketches and 
filters feed to their hash functions. Each family specifies its supported item 
types, hash algorithm, seeds, and how hashes select counters, registers, or 
filter bits. For example, [Count-Min 
v2](0021-count-min-format.md#4-item-encoding) supports integers, strings, and 
bytes. Its floating-point input remains undefined.
+
+In [Discussion #20][discussion], Java inserted an empty byte array and `-0.0` 
into separate Bloom filters. Java found each item. C++ successfully read both 
images and returned `false` for both items. For empty bytes the C++ query 
returned early. For negative zero it probed different bits.
+
+## Proposed rules
+
+**Integers.** Encode 64-bit integers as eight little-endian bytes, using two’s 
complement for signed values. Sign-extend narrower signed integers. For 
narrower unsigned integers the family must name its widening rule. Count-Min v2 
preserves the unsigned value. The [C++ HLL overload][cpp-hll] interprets the 
high bit as a sign bit at the original width. Both cases appear in the vectors 
below.
+
+**Strings and bytes.** Encode a sequence of Unicode scalar values as UTF-8. 
Preserve their order and spelling, including embedded NUL. Hash a byte sequence 
verbatim. Both forms omit length prefixes, type tags, and terminators. The text 
`"é"` (U+00E9) and the two bytes `c3 a9` therefore represent the same input. 
Historical UTF-16 overloads such as Java’s `char[]` have a separate input 
contract.
+
+**Floating point.** Where the family accepts floating-point items, widen 
binary32 to binary64. Encode both signed zeros as `0x0000000000000000` and 
every NaN, regardless of sign or payload, as `0x7ff8000000000000`. For every 
other value, including infinities, use its binary64 bits. Feed the resulting 
eight bytes to the hash in little-endian order.
+
+**Null and empty items.** Skip a null item in an API that accepts nulls, an 
empty string, or a zero-length byte sequence. Updates and filter builds omit 
that item. Membership queries return `false`. Query-and-update returns `false` 
and leaves the filter unchanged. Count-Min estimates and both bounds return 
zero even on a populated sketch. A one-byte input `00` is a regular item. 
Families define any additional types, including arrays of numbers and composite 
keys, and their output convent [...]
+
+**API contract.** Apply the same rules when writing and querying. A typed API 
can enforce them internally. A generic API can document a wrapper and a 
caller-side empty check. Conformance tests must exercise the documented calling 
convention. For example, Rust Bloom callers use `raw_bytes` for strings and 
bytes and skip empty inputs before calling the filter. [Rust Bloom 
guidance][rust-bloom]
+
+## Conformance
+
+These vectors give the input bytes in order and the unsigned hexadecimal 
digest of XXH64 with seed zero. The digest checks the encoding in isolation. 
Each family still uses its own hash and seeds.
+
+| Input                                    | Bytes (hex)               | 
XXH64, seed 0      |
+|------------------------------------------|---------------------------|--------------------|
+| `i8(-1)` or sign-extended `u8(255)`      | `ff ff ff ff ff ff ff ff` | 
`85d136adb773c6c9` |
+| `u8(255)`, preserving its unsigned value | `ff 00 00 00 00 00 00 00` | 
`2aa06adfe623603f` |
+| U+00E9 or raw bytes `c3 a9`              | `c3 a9`                   | 
`17d757dfb8b46f78` |
+| One zero byte                            | `00`                      | 
`e934a84adb052768` |
+| `+0.0` or `-0.0`                         | `00 00 00 00 00 00 00 00` | 
`34c96acdcadb1bbb` |
+| `1.5` as binary32 or binary64            | `00 00 00 00 00 00 f8 3f` | 
`49f7b96b6b5ccaf9` |
+| Any NaN                                  | `00 00 00 00 00 00 f8 7f` | 
`e9adb09fee122aac` |
+
+For each supported writer/reader pair, insert one sign of zero and query the 
other after deserialization. Repeat with NaN bit patterns `0x7ff8000000000001` 
and `0xfff8000000000042`, then swap writer and reader where supported. On empty 
and populated structures, check the return value and state after each skipped 
operation. Include a single zero byte as a positive control. For sketches 
without item queries, compare observable state after equivalent update streams.
+
+## Evidence at pinned revisions
+
+- **Java and C++.** The [family-by-family comparison][discussion] records 
opposite empty-byte behavior. Java HLL, CPC, Theta, Tuple keys, and Count-Min 
v1 skip the update. C++ hashes a non-null pointer of length zero in those 
families. For Bloom it is Java that hashes the empty bytes. Java Bloom and XOR 
also preserve the sign of zero, while C++ Bloom canonicalizes it. [Java 
Bloom][java-bloom] · [C++ Bloom][cpp-bloom]
+- **Go.** Bloom hashes a nil or empty byte slice on update, query, and 
query-and-update, skips empty strings, and normalizes scalar signed zero and 
NaNs. Count-Min v1 skips empty byte updates and returns a zero estimate, but 
its upper bound adds a term based on total weight. An empty sketch alone hides 
this difference. [Bloom][go-bloom] · [Count-Min][go-count]
+- **Rust.** The generic APIs accept `Hash` values. The documented wrappers 
supply raw bytes, canonical floats, and two integer widening strategies. HLL 
documents sign extension and Bloom documents value-preserving widening. The 
caller handles empty inputs. [Hash wrappers][rust-hash] · [HLL][rust-hll] · 
[Bloom][rust-bloom]
+- **Python.** The Count-Min binding exposes integer and string overloads for 
update, estimate, and bounds. Its pinned C++ 5.3.0 backend skips empty strings 
and returns zero for all three queries. The binding exposes no separate 
raw-buffer overload for these operations. [Binding][py-count] · [Backend 
pin][py-pin] · [String operations][py-backend]
+
+## Legacy images and open decisions
+
+A Java Bloom image containing only `-0.0` retains the positions chosen by its 
writer. Updating a reader to normalize zero cannot move those bits. A 
serialization version (SerVer) can identify a new contract. Older images of the 
same version may carry different producer conventions. Each affected family 
must specify which legacy queries and mixed-version operations it can support, 
when to reject an image, and when users need the original items to rebuild it.
+
+Review is requested on treating all empty byte sequences as absent and on the 
family-specific unsigned widening rules. Before rollout, complete the inventory 
by family, overload, and operation across Java, C++, Go, Rust, and Python, 
recording any caller steps. Use it to choose a legacy policy per affected 
family and gate cross-language fixtures by the versions each reader supports. 
[Compatibility discussion][legacy] · [Proposed scope][scope]
+
+[discussion]: https://github.com/apache/datasketches-tck/discussions/20
+[legacy]: 
https://github.com/apache/datasketches-tck/discussions/20#discussioncomment-19530843
+[scope]: 
https://github.com/apache/datasketches-tck/discussions/20#discussioncomment-19585778
+[cpp-hll]: 
https://github.com/apache/datasketches-cpp/blob/c22f2b1d41497ff2d331e74d1a65be3cd17b1dc3/hll/include/HllSketch-internal.hpp#L131-L144
+[java-bloom]: 
https://github.com/apache/datasketches-java/blob/ef440a814319f57d165dfbe2c39fc07bf4a0a1e7/src/main/java/org/apache/datasketches/filters/bloomfilter/BloomFilter.java#L278-L311
+[cpp-bloom]: 
https://github.com/apache/datasketches-cpp/blob/c22f2b1d41497ff2d331e74d1a65be3cd17b1dc3/filters/include/bloom_filter_impl.hpp#L812-L838
+[go-bloom]: 
https://github.com/apache/datasketches-go/blob/c9701e7d4c76952c615c3f2938f7d61bf126b561/filters/bloom_filter.go#L262-L408
+[go-count]: 
https://github.com/apache/datasketches-go/blob/c9701e7d4c76952c615c3f2938f7d61bf126b561/count/count_min_sketch.go#L113-L181
+[rust-hash]: 
https://github.com/apache/datasketches-rust/blob/034de1a69a5989e70d2ac03545d181904e895014/datasketches/src/hash/value/mod.rs#L18-L35
+[rust-hll]: 
https://github.com/apache/datasketches-rust/blob/034de1a69a5989e70d2ac03545d181904e895014/datasketches/src/hll/mod.rs#L25-L34
+[rust-bloom]: 
https://github.com/apache/datasketches-rust/blob/034de1a69a5989e70d2ac03545d181904e895014/datasketches/src/bloom/mod.rs#L29-L39
+[py-count]: 
https://github.com/apache/datasketches-python/blob/bd0231d9512bc62b6ff45efd752dc4f4ae4c57e3/src/count_wrapper.cpp#L69-L84
+[py-pin]: 
https://github.com/apache/datasketches-python/blob/bd0231d9512bc62b6ff45efd752dc4f4ae4c57e3/CMakeLists.txt#L117-L122
+[py-backend]: 
https://github.com/apache/datasketches-cpp/blob/5b5524f55d121225a7909c2851271327684585d7/count/include/count_min_impl.hpp#L149-L221


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

Reply via email to