Subject: Re: [quicwg/base-drafts] QCRAM encoding requires two passes (#1138)

From: krasic <[email-masked]>
Date: Thu, 01 Mar 2018 12:02:42 -0800

I will poke around here too see if there are strong feelings about loosing the option for streaming mode.   My fuzzy recollection is that it was valued for hardening against memory spikes associated with clusters of pathologically large headers.

FWIW, when I extended my QCRAM protype in the proxygen simulator to split updates from the request-response steram,  it became effectively double encode:  

https://github.com/facebook/proxygen/blob/master/proxygen/lib/http/codec/compress/experimental/qcram/QCRAMEncoder.cpp#L45

-- 
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/issues/1138#issuecomment-369713436

---

From: Mike Bishop <[email-masked]>
Date: Thu, 01 Mar 2018 20:06:44 +0000 (UTC)

The responses, both on-list and from folks I've asked, suggest that streaming decode is much higher priority than streaming encode.

-- 
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/issues/1138#issuecomment-369714565

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 01 Mar 2018 12:19:59 -0800

> The responses, both on-list and from folks I've asked, suggest that streaming decode is much higher priority than streaming encode.

If you are referring to the recent httpbis thread: varnish, haproxy, and squid is a single use case.

-- 
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/issues/1138#issuecomment-369718228

---

From: Mike Bishop <[email-masked]>
Date: Thu, 01 Mar 2018 21:01:05 +0000 (UTC)

Speaking as former owner of a client and server implementation:

- our client API permitted the caller to supply headers onto the request one at a time
- our server API required all response headers be delivered at once (but could stream body)
- our header compression library processed all headers as a single input

Remember, the headers cannot be streamed onto the wire in HTTP/2, nor can you compress headers on any other streams in parallel.  QCRAM is already better than that because, if desired, multiple streams can be actively compressing at once.  (Either queuing their additions into a single table update frame, or compressing against a table state without modifications.)

-- 
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/issues/1138#issuecomment-369729285

---

From: afrind <[email-masked]>
Date: Fri, 09 Mar 2018 16:27:58 -0800

Here's my proposal for single pass encoding.  

In addition to Base and Depends, encode Length, the number of valid dynamic table entries prior to encoding the block.  Dynamic indexes 1..Length are older than Base Index.  Dynamic indexes larger than Length count up from Base Index.  Since Depends can be larger than Base Index, rename Depends to Base Index (the largest entry referenced in the block) and encode the Delta between Base Index and the value of Base Index used for encoding.

Remove the BLOCKING flag, which is now implicit upon receiving a request stream with Base Index higher than the decoder's Base Index.  Instead, add a flag 'EXTENDED_BASE', which is present if the encoder's Base Index changed during an encode.

The wire format for frames with EXTENDED_BASE flag is:

```
    0 1 2 3 4 5 6 7
   +-+-+-+-+-+-+-+-+
   | Base Index(8+)|
   +---------------+
   | Base Delta(8+)|
   +---------------+
   | Length    (8+)|
   +---------------+
```

Here's an example where the encoder began encoding with four entries in the table, and added two during an encode.  Let's assume Base Index prior to encoding was 18.  Here's how entries would be referenced:

```
              E       B
+---+---+---+---+---+---+
+ 4 + 3 + 2 + 1 + 5 + 6 +
+---+---+---+---+---+---+
 15  16  17  18  19  20

E = Encoding Base
B = Base Index
```

The encoder would produce a block that begin with `0x14 0x02 0x04`

Encode algorithm:
```
baseIndex = dynamicTable.baseIndex
length = dynamicTable.numEntries
numInserts = 0
largestReference = 0
for header in headers:
  i = staticTable.getIndex(header)
  if i > 0:
    encodeIndexReference(streamBuffer, i)
    continue
  i = dynamicTable.getAbsoluteIndex(header)
  if i == 0:
    largestReference = max(largestReference, i)
  else if dynamicTable.canIndex(header):
    encodeInsert(controlBuffer, header)
    dynamicTable.add(header)
    numInserts += 1
    i = baseIndex + numInserts  # absolute index of new entry
    largestReference = max(largestReference, i)
  else:
    encodeLiteral(header)
    continue

  if i <= baseIndex:
    i = baseIndex - i + 1
    assert(i <= length)
  else:
    i = i - baseIndex + length

  encodeIndexReference(streamBuffer, i + staticTable.size())

# Write the prefix
encodeInteger(prefixBuffer, largestReference, 8)
if largestReference > baseIndex:
  extendedBase = True
  encodeInteger(prefixBuffer, largestReference - baseIndex, 8)
  encodeInteger(prefixBuffer, length, 8)
else 
  extendedBase = False

return (controlBuffer, prefixBuffer + streamBuffer, extendedBase)
```

Decode Algorithm:

Header:
```
if extendedBase:
  largestReference = decodeInteger(buf, 8)
  encodingBaseIndex = largestReference - decodeInteger(buf, 8)
  length = decodeInteger(buf, 8)
else:
  largestReference = encodingBaseIndex = decodeInteger(buf, 8)
  length = 0
```

Index Processing:
```
index = decodeIndex(buf, N)
if index <= staticTable.size():
  header = staticTable[index]
else:
  index -= staticTable.size()
  if length == 0 or index <= length:
    absoluteIndex = encodingBaseIndex - index + 1
  else
    absoluteIndex = index + encodingBaseIndex - length
  index = dynamicTable.baseIndex - index + 1
  header = dynamicTable[index]
}
```

-- 
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/issues/1138#issuecomment-371983436

---

From: afrind <[email-masked]>
Date: Thu, 15 Mar 2018 22:13:59 +0000 (UTC)

@martinthomson mentioned that he didn't like this approach.  Specifically:

1) He disliked the out-of-band flag

I got rid of the flag and encoded 2 varints (the largest reference and the encoding base) in all stream blocks.  In one-pass encoding, largest reference may be smaller than the encoding base (eg: the block didn't reference the most recent table entry) or larger (the block triggered an insert/duplication).  Just eyeballing it, both are required about half the time, and the delta was always small enough to fit in a single byte.  Note the delta needs to be encoded with a sign bit.

```
[   Depends Index(8+) ]
[ S | Base Delta (7+) ]
```

Where Depends Index is the largest reference in the block, and 
`baseIndex = (S) ? dependsIndex - delta : dependsIndex + delta`

If someone really wanted to save the byte when they are the same, we could encode a flag in the MSB of Depends Index and give it a 7 bit prefix.

2) He thought including length was messy/large and could maybe do it with different instructions, possibly reusing some unused HPACK ones.

Fortunately, there are two unused HPACK instructions on QPACK request streams that can be repurposed.  I changed 'Literal with incremental indexing' to 'Literal with name index higher than base', and 'Table size update' to 'Indexed with index higher than base'.   Indexes in these instructions are found at absolute index = baseIndex + index (- 61 optional, I did it for consistency).  This also leaves only a single HPACK instruction invalid in QPACK (literal on control stream).  I like this approach better than using length.

-- 
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/issues/1138#issuecomment-373539800