Return-Path: X-Original-To: quic-issues@ietfa.amsl.com Delivered-To: quic-issues@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8614C130E65 for ; Fri, 28 Sep 2018 09:25:23 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -3 X-Spam-Level: X-Spam-Status: No, score=-3 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, GB_SUMOF=5, HTML_MESSAGE=0.001, MAILING_LIST_MULTI=-1, RCVD_IN_DNSWL_HI=-5, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=github.com Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id zGFZMcPxVEmA for ; Fri, 28 Sep 2018 09:25:22 -0700 (PDT) Received: from out-2.smtp.github.com (out-2.smtp.github.com [192.30.252.193]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 0E8A9130E63 for ; Fri, 28 Sep 2018 09:25:22 -0700 (PDT) Date: Fri, 28 Sep 2018 09:25:20 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=github.com; s=pf2014; t=1538151920; bh=cD0OPMK1s743FH7rjspoidDMVGvchhWxvF4awTo0+Jk=; h=Date:From:Reply-To:To:Cc:In-Reply-To:References:Subject:List-ID: List-Archive:List-Post:List-Unsubscribe:From; b=WMGO8oIUUFPMA5MpPTgVfZYq4tE5j2umbYrN7ZfsZgNZjhRMXXpURJ21R/i20owWI leafMcfBuEmFPsOAhVKlTE0HrF2U2j7KqRw/1DBl3oyxidDr2jxwmYukMLbFqLgP6t Gp6zd93zTIiREvn8yxL5isfUZLg168brH7tYqi0k= From: Mike Bishop Reply-To: quicwg/base-drafts To: quicwg/base-drafts Cc: Subscribed Message-ID: In-Reply-To: References: Subject: Re: [quicwg/base-drafts] QPACK: Encode Largest Reference modulo MaxEntries (#1763) Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="--==_mimepart_5bae55f0d651f_4eb53fd74a8d45bc3620a6"; charset=UTF-8 Content-Transfer-Encoding: 7bit Precedence: list X-GitHub-Sender: MikeBishop X-GitHub-Recipient: quic-issues X-GitHub-Reason: subscribed X-Auto-Response-Suppress: All X-GitHub-Recipient-Address: quic-issues@ietf.org Archived-At: X-BeenThere: quic-issues@ietf.org X-Mailman-Version: 2.1.29 List-Id: Notification list for GitHub issues related to the QUIC WG List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 28 Sep 2018 16:25:23 -0000 ----==_mimepart_5bae55f0d651f_4eb53fd74a8d45bc3620a6 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit MikeBishop approved this pull request. > -safe to process the rest of the block. +safe to process the rest of the block. If Largest Reference is greater than +zero, the encoder transforms it as follows before encoding: + +~~~ + LargestReference = LargestReference mod 2*MaxEntries + 1 +~~~ + +The decoder reconstructs the Largest Reference using the following algorithm: + +~~~ + if LargestReference > 0: + LargestReference -= 1 + CurrentWrapped = TableLargestAbsoluteIndex mod 2*MaxEntries + + if CurrentWrapped >= LargestReference + MaxEntries: It makes sense -- if it can be either `MaxEntries` greater *or* `MaxEntries` lesser, then you have `2*MaxEntries + 1` items, counting the one you're currently on. There's always ambiguity at the far end -- the end values in the range are equivalent -- but because those ambiguous entries are always MaxEntries away, they can't be sent without evicting something unacknowledged or referencing something already evicted, both of which are prohibited. > +### Calculating Table Size + +The size of the dynamic table is the sum of the size of its entries. + +The size of an entry is the sum of its name's length in octets (as defined in +{{string-literals}}), its value's length in octets, and 32. + +The size of an entry is calculated using the length of its name and value +without any Huffman encoding applied. + +`MaxEntries` is the maximum number of entries that the dynamic table can have. +The smallest entry has empty name and value strings and has the size of 32. +The MaxEntries is calculated as + +~~~ + MaxEntries = floor( MaxTableSize / 32 ) I was concerned that the doubling could cause this to give us one less entry than we need, but after playing with some edge table sizes for a few minutes, this seems to work. -- You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub: https://github.com/quicwg/base-drafts/pull/1763#pullrequestreview-159931664 ----==_mimepart_5bae55f0d651f_4eb53fd74a8d45bc3620a6 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 7bit

@MikeBishop approved this pull request.

In draft-ietf-quic-qpack.md:

> -safe to process the rest of the block.
+safe to process the rest of the block.  If Largest Reference is greater than
+zero, the encoder transforms it as follows before encoding:
+
+~~~
+   LargestReference = LargestReference mod 2*MaxEntries + 1
+~~~
+
+The decoder reconstructs the Largest Reference using the following algorithm:
+
+~~~
+   if LargestReference > 0:
+      LargestReference -= 1
+      CurrentWrapped = TableLargestAbsoluteIndex mod 2*MaxEntries
+
+      if CurrentWrapped >= LargestReference + MaxEntries:

It makes sense -- if it can be either MaxEntries greater or MaxEntries lesser, then you have 2*MaxEntries + 1 items, counting the one you're currently on. There's always ambiguity at the far end -- the end values in the range are equivalent -- but because those ambiguous entries are always MaxEntries away, they can't be sent without evicting something unacknowledged or referencing something already evicted, both of which are prohibited.

In draft-ietf-quic-qpack.md:

> +### Calculating Table Size
+
+The size of the dynamic table is the sum of the size of its entries.
+
+The size of an entry is the sum of its name's length in octets (as defined in
+{{string-literals}}), its value's length in octets, and 32.
+
+The size of an entry is calculated using the length of its name and value
+without any Huffman encoding applied.
+
+`MaxEntries` is the maximum number of entries that the dynamic table can have.
+The smallest entry has empty name and value strings and has the size of 32.
+The MaxEntries is calculated as
+
+~~~
+   MaxEntries = floor( MaxTableSize / 32 )

I was concerned that the doubling could cause this to give us one less entry than we need, but after playing with some edge table sizes for a few minutes, this seems to work.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub, or mute the thread.

----==_mimepart_5bae55f0d651f_4eb53fd74a8d45bc3620a6--