Subject: Re: [httpwg/http-extensions] Switch to Cuckoo Filter (#500)

From: HTTP issue updates <[email-masked]>
Date: Wed, 28 Feb 2018 06:11:54 -0800

@yoavweiss @mnot PTAL

-- 
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/pull/500#issuecomment-369250946

---

From: HTTP issue updates <[email-masked]>
Date: Wed, 28 Feb 2018 14:18:00 +0000 (UTC)

yoavweiss commented on this pull request.

> @@ -375,10 +487,7 @@ The header may represent the cache state of a client or that of a proxy, dependi
 
 # Acknowledgements
 
-Thanks to Adam Langley and Giovanni Bajo for their explorations of Golomb-coded sets. In
-particular, see
-<http://giovanni.bajo.it/post/47119962313/golomb-coded-sets-smaller-than-bloom-filters>, which
-refers to sample code.
+Thanks to Joav Weiss for his idea and text to use Cuckoo Filter.

s/Joav/Yoav/ :D

-- 
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/pull/500#pullrequestreview-100077531

---

From: HTTP issue updates <[email-masked]>
Date: Wed, 28 Feb 2018 06:19:54 -0800

yoavweiss approved this pull request.

LGTM!

-- 
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/pull/500#pullrequestreview-100078257

---

From: HTTP issue updates <[email-masked]>
Date: Wed, 28 Feb 2018 07:22:09 -0800

kazuho commented on this pull request.

 # Acknowledgements

I'm terribly sorry for the mistake. Fixed in f8e63e2.

-- 
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/pull/500#discussion_r171279570

---

From: HTTP issue updates <[email-masked]>
Date: Wed, 28 Feb 2018 15:23:18 +0000 (UTC)

@kazuho pushed 1 commit.

f8e63e2  typo

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/httpwg/http-extensions/pull/500/files/8d9ba5dbcfc571c2802a55313b7ce643401759af..f8e63e273c64717fb6a9cb81a52dc63e5b06371d

---

From: HTTP issue updates <[email-masked]>
Date: Wed, 28 Feb 2018 15:25:53 +0000 (UTC)

@yoavweiss Thank you for checking!

-- 
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/pull/500#issuecomment-369273133

---

From: HTTP issue updates <[email-masked]>
Date: Wed, 28 Feb 2018 18:58:56 +0000 (UTC)

mnot commented on this pull request.

> +9. While `maxcount` is larger than zero:
+    1. Let `position_start` be 40 + `h` * `f` \* `b`.
+    2. Let `position_end` be `position_start` + `f` \* `b`.
+    3. While `position_start` < `position_end`:
+        1. Let `bits` be `f` bits from `digest_value` starting at `position_start`.
+        2. If `bits` is all zeros, set `bits` to `dest_fingerprint` and terminate these steps.
+        3. Add `f` to `position_start`.
+    4. Let `e` be a random number from 0 to `b`.
+    5. Substract `f` * (`b` - `e`) from `position_start`.
+    6. Let `bits` be `f` bits from `digest_value` starting at `position_start`.
+    7. Let `fingerprint` be the value of bits, read as big endian.
+    8. Set `bits` to `dest_fingerprint`.
+    9. Set `dest_fingerprint` to `fingerprint`.
+    10. Let `h` be {{hash2}} with `h`, `dest_fingerprint` and `N` as inputs.
+    11. Substract 1 from `maxcount`.
+13. Substract `f` from `position_start`.

Double check that the generated text and HTML are correct. In the past, list numbers higher than 9 needed to wrap around to 0 to work correctly; not sure if that's been fixed or not.

-- 
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/pull/500#pullrequestreview-100186280

---

From: HTTP issue updates <[email-masked]>
Date: Wed, 28 Feb 2018 17:47:42 -0800

@kazuho pushed 1 commit.

a701924  Merge branch 'master' into kazuho/h2-cache-digest/cuckoo

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/httpwg/http-extensions/pull/500/files/f8e63e273c64717fb6a9cb81a52dc63e5b06371d..a701924ef7e40535e9b4abc1ca4764ad52df32b9

---

From: HTTP issue updates <[email-masked]>
Date: Wed, 28 Feb 2018 17:48:12 -0800

Closed #500.

-- 
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/pull/500#event-1498071889

---

From: HTTP issue updates <[email-masked]>
Date: Thu, 01 Mar 2018 01:51:07 +0000 (UTC)

My bad. I have accidentally removed the branch that caused the PR to get closed.

-- 
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/pull/500#issuecomment-369447361

---

From: HTTP issue updates <[email-masked]>
Date: Wed, 28 Feb 2018 18:05:01 -0800

Thank you for pointing that out.

The numbers were correctly handled by the parser, however the numbers in the markdown were wrong.

The issue has been fixed in 8469d48.

-- 
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/pull/500#discussion_r171445557

---

From: HTTP issue updates <[email-masked]>
Date: Wed, 28 Feb 2018 18:10:50 -0800

Since I accidentally removed the branch, it has become impossible to continue reviewing the changes in this branch. I apologize for the inconvenience.

Fortunately, @yoavweiss and @mnot have already given their comments on the PR. Considering that, I have merged the PR to master in 63284be (FWIW, you can click the commit hash to see the changes that went into master).

If anybody sees an issue, I would appreciate if they could open a new issue (or a PR).

-- 
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/pull/500#issuecomment-369450727

---

From: HTTP issue updates <[email-masked]>
Date: Wed, 28 Feb 2018 20:19:18 -0800

Nothing major, but s/Substract/Subtract/ig

-- 
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/pull/500#issuecomment-369469556

---

From: HTTP issue updates <[email-masked]>
Date: Thu, 01 Mar 2018 05:00:33 +0000 (UTC)

@martinthomson Thank you for pointing that out. I was able to fix that in a8f1ca0 prior to submitting -03.

-- 
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/pull/500#issuecomment-369474562