Subject: [httpwg/http-extensions] [cache digests] Eliminate requirement that the digest is a power of 2 (#607)

From: HTTP issue updates <[email-masked]>
Date: Thu, 03 May 2018 06:28:12 -0700

During the implementation of the [Cache Digests reference implementation](https://github.com/yoavweiss/cache-digests-cuckoo) I [realized](https://github.com/yoavweiss/cache-digests-cuckoo/commit/3ee4a45bf0bc03ea47ae7125e409b41d57acb198) that the digest size has to be a power of 2. Otherwise the `xor` operation on the primary index can lead to an out-of-bounds write, resulting in memory and correctness issues.

An alternative to that approach would be to:
* Do an out-of-bounds check to the `xor` operation and if it is out-of-bounds, take as an index the out-of-bounds value minus the digest size.
* Add a bit to the fingerprint which indicates that the alternative index was out-of-bounds.
* In the future, when a fingerprint is displaced and need to be returned to the primary index, the "out-of-bounds" bit can be used as an indication that the original `xor` operation was out-of-bounds, and instead of the index, the `xor` operation now can use the original out-of-bounds index.

@kazuho - Does that make sense?

It will cost us a bit more space (extra bit per fingerprint), but will make the digest size significantly more flexible.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/httpwg/http-extensions/issues/607