Subject: [quicwg/base-drafts] Simplify time representation (#109)

From: Martin Thomson <[email-masked]>
Date: Mon, 02 Jan 2017 22:01:25 -0800

I note that the IEEE754 reference doesn't help.

-- 
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/109

---

From: janaiyengar <[email-masked]>
Date: Thu, 05 Jan 2017 22:11:08 -0800

The time representation is "inspired by" IEEE754, so it's likely that the reference doesn't help by itself :-)

-- 
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/109#issuecomment-270839194

---

From: ianswett <[email-masked]>
Date: Mon, 16 Jan 2017 06:21:15 -0800

I propose we switch to scaled integers with a scale factor that is supplied by both peers at the beginning of the connection.  If no scale factor is supplied, default to microseconds.  This allows 65ms of time, which is plenty for most cases.

MAX_UINT_16 indicates the value was too large to be specified.

-- 
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/109#issuecomment-272873075

---

From: Marten Seemann <[email-masked]>
Date: Mon, 16 Jan 2017 07:00:17 -0800

I just ran some tests with a quic-go server, and some normal browsing activity using Chrome (all on localhost), and recorded the delay times of incoming ACKs. I'm seeing a few ones that have delay times on the order of 65 ms.
ACKs with a delay of MAX_UINT_16 would probably need to be excluded from contributing to the RTT calculations, right?

What's the reason to change the format at all? Other than that it's a little bit of bit shifting that needs to be implemented (which could be made a lot easier by providing some examples).

-- 
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/109#issuecomment-272884522

---

From: Lars Eggert <[email-masked]>
Date: Mon, 16 Jan 2017 08:20:40 -0800

The reason is that it's not fully specified. We either need to say it's IEEE754 and cite it, or we need to include a spec for what we actually are using.

-- 
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/109#issuecomment-272905078

---

From: ianswett <[email-masked]>
Date: Mon, 16 Jan 2017 11:58:39 -0800

One reason for changing it is that it may be very difficult to get a Linux kernel implementation if we require support for any sort of floating point format, but maybe it could be read and immediately converted to an int.  Similarly, hardware support may be much more challenging.  And though it's sort of neat, I'm not sure it's buying us a lot over a scaled int.

I agree that sometimes the delay times are over 65ms, but I'd expect it's typically either in a connection close frame(where it's not important at all) or when there's reordering and an RTT sample has already been taken for the current largest observed.

-- 
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/109#issuecomment-272949947

---

From: Martin Thomson <[email-masked]>
Date: Mon, 16 Jan 2017 17:44:32 -0800

Can't implementations also avoid providing timing for packets that have large processing delays?  If that means that there are no processing delays reported, that's probably OK too.  Though RTT measurements will then be 65ms+ out of whack, it might be better than sending a useless value.

-- 
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/109#issuecomment-273000676

---

From: Lars Eggert <[email-masked]>
Date: Mon, 16 Jan 2017 23:57:04 -0800

I think 65ms is at least an order of magnitude too short. We don't know where people will want to use QUIC in the future.

-- 
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/109#issuecomment-273045621

---

From: ianswett <[email-masked]>
Date: Tue, 17 Jan 2017 06:36:55 -0800

Agreed Lars, that's why we'd have the ability to scale the value.

-- 
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/109#issuecomment-273183742

---

From: Lars Eggert <[email-masked]>
Date: Tue, 17 Jan 2017 06:40:43 -0800

Sorry I was unclear: We should use a scaling default that results in a sensible range.

-- 
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/109#issuecomment-273185388

---

From: ianswett <[email-masked]>
Date: Tue, 17 Jan 2017 06:55:24 -0800

I'd propose we require a scale factor as part of the handshake, so we ensure this is well exercised, then we don't need to worry too much about whether we've chosen a good default.

For the current use of the custom 2 byte timestamp, 65ms is enough to handle all the cases when a time value is actually useful.  Obviously this would change if we used this time format in different use cases.

-- 
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/109#issuecomment-273190679

---

From: Mark Nottingham <[email-masked]>
Date: Thu, 19 Jan 2017 18:42:26 -0800

Comment from @larseggert in #159:

> There already is a "DISCUSS_AND_REPLACE: Perhaps make this format simpler" note in the spec about the homegrown floating point format used for ACK timestamps. I just wanted to open a corresponding issue.
>
> It would be really good if an encoding could be used that was either trivial to implement from scratch, or a standard for which code is readily available.
>
> As for the latter, the text in the spec sounds like what is desired is something like the "binary16" format in IEEE 754-2008. I'd be great if this could be used. Compiler support seems spotty/sketchy, e.g., gcc says this:
>
> The __fp16 type may only be used as an argument to intrinsics defined in <arm_fp16.h>, or as a storage format. For purposes of arithmetic and other operations, __fp16 values in C or C++ expressions are automatically promoted to float.
And it's only supported on ARM, apparently.

-- 
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/109#issuecomment-273962595

---

From: MikkelFJ <[email-masked]>
Date: Fri, 20 Jan 2017 14:09:03 -0800

I worked through the details before being pointed to this issue.

I have attached a reference implemention that only lacks MSVC optimization. Mind you, it is very recent and has not been reviewed.

While at first I found the format (I call uf16) to be quite daunting, overengineerd, an unclear, I now believe it is actually very well suited for the problem, and it is quite simple and fast to use if the the `uf16_encode` and `uf16_decode` functions are provided as an appendix.

quoting parts of the attached uf16.h file and embedded comments below:

```
The IETF QUIC transport draft Nov. 2016 draft appears to provide an
incorrect example of a delta encoded timestamp in the ACK Frame section.
It is also not clear if the spec is otherwise the same as the Chromium
implemention. The following definition attempts to make this more clear
and follows the logic that Chromium implements as of Jan 2017.

    QUIC uses a custom floating point format uf16 to represent a
    non-negative time delta in microseconds.

    The uf16 format encodes an unsigned 16-bit floating point value with
    non-negative exponent and no special values(*). It can always be
    expanded into a 64-bit signed or unsigned integer. The format is a
    16-bit encoded value v = e(5)f(11) or, when e < 2 a plain unsigned
    12-bit integer v = 0(4)m(12). When v < 2^12 (and therefore e < 2), the
    resulting integer value becomes k = v with no interpretation. When e >=
    2, the effective exponent becomes p = e - 1 and the mantissa, or
    effective fraction, becomes m = f + 2^11 which adds an implicit most
    significant fraction bit. Thus the resulting integer value becomes k = m
     * 2^p, p >= 1 or k = (f + 2^11) * 2^(e - 1), e >= 2.

    (*) The decoded value can comfortably be represented in a 64-bit signed
    or unsigned integer. When encoding an unsigned 64-bit value, any value
    that would overflow the 16-bit encoded representation is clamped to v =
    UF16_MAX = 2^16 - 1 = 0xFFFF, or k = UF16_UINT64_MAX = (2^12 - 1) * 2^30
    =  0x3FFC0000000.

    On common unsigned twos complement 64-bit hardware decoding from uf16
    can be computed as `if v < (1 << 12) then return v; else p = (v >> 11) -
    1; m = (v - p) << 11; k = m << p; return k; endif`. Note that v - p
    exposes the implicit fraction bit while removing the explicit exponent.
    Likewise encoding to uf16 can be computed as `if k < (1 << 12) return k;
    else if k >= UF16_INT64_MAX then return UF16_MAX; else p = 64 - 12 -
    leading_zero_count_uint64(k); v = (p << 11) + (k >> p); return v;
    endif`. Note that adding (p << 11) intentionally overflows the implicit
    fraction bit and increments p by one.

```

quoting the actual encode without support for leading zero count included:

```
/* `__uf16_leading_zero_count_uint64` may be implemented with __builtin_clzll when available. */

#define UF16_MAX UINT16_C(0xFFFF)
#define UF16_UINT64_MAX UINT64_C(0x3FFC0000000)

static inline uint64_t uf16_decode(uint16_t v)
{
    uint16_t p;
    uint64_t m;

    if (v < (1 << 12)) {
        return v;
    }
    p = (v >> 11) - 1;
    m = v - (p << 11);
    return m << p;
}

static uint16_t uf16_encode(uint64_t k)
{
    uint16_t p, f;

    if (k < (1 << 12)) {
        return (uint16_t)k;
    }
    if (k >= UF16_UINT64_MAX) {
        return UF16_MAX;
    }
    p = (uint16_t)(64 - 12 - __uf16_leading_zero_count_uint64(k));
    f = (uint16_t)(k >> p);
    return (p << 11) + f;
}

```
[uf16.h.zip](https://github.com/quicwg/base-drafts/files/720596/uf16.h.zip)

-- 
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/109#issuecomment-274193169

---

From: MikkelFJ <[email-masked]>
Date: Fri, 20 Jan 2017 15:37:52 -0800

`static uint16_t uf16_encode(uint64_t k)` =>
`static inline uint16_t uf16_encode(uint64_t k)`

Here is an updated wording:

```

    The uf16 format encodes an unsigned 64-bit integer value k as an
    unsigned 16-bit floating point value v with non-negative exponent
    and no special values (*). The encoded format is either v =
    e(5)f(11), e >= 2, or a plain unsigned 12-bit integer v = 0(4)m(12),
    e <= 1. When v < 2^12 (and therefore e < 2), the resulting integer
    value becomes k = v with no interpretation. When e >= 2, the
    effective exponent becomes p = e - 1 and the mantissa, or effective
    fraction, becomes m = f + 2^11 which adds an implicit most
    significant fraction bit. Thus the resulting integer value becomes k
    = m * 2^p, p >= 1 or, equivalently, k = (f + 2^11) * 2^(e - 1), e >=
    2, and k = v, e < 2.

    (*) The decoded value can comfortably be represented in a 64-bit
    signed or unsigned integer. When encoding an unsigned 64-bit value,
    any value that would overflow the 16-bit encoded representation is
    clamped to v = UF16_MAX = 2^16 - 1 = 0xFFFF or, correspondingly, k =
    UF16_UINT64_MAX = (2^12 - 1) * 2^30 = 0x3FFC0000000.

    On common hardware supporting unsigned 64-bit two's complement
    arithmetic, decoding from uf16 can be computed as `if v < (1 << 12)
    then return v; else p = (v >> 11) - 1; m = (v - p) << 11; k = m <<
    p; return k; endif`. Note that v - p exposes the implicit fraction
    bit while removing the explicit exponent. Likewise, encoding to uf16
    can be computed as `if k < (1 << 12) return k; else if k >=
    UF16_INT64_MAX then return UF16_MAX; else p = 64 - 12 -
    leading_zero_count_uint64(k); v = (p << 11) + (k >> p); return v;
    endif`. Note that adding (p << 11) intentionally overflows and hides
    the implicit fraction bit and increments the explicit exponent by
    one. `leading_zero_count_uint64(k)` implements `64 - log2_floor(k)`
    and is often a single machine instruction, sometimes provided as
    `__builtin_clzll` in C.

```

-- 
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/109#issuecomment-274208595

---

From: MikkelFJ <[email-masked]>
Date: Sat, 21 Jan 2017 06:37:02 -0800

Updated uf16.h with new wording, and MSVC support, attached.

[uf16.h.zip](https://github.com/quicwg/base-drafts/files/721213/uf16.h.zip)

-- 
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/109#issuecomment-274265481

---

From: MikkelFJ <[email-masked]>
Date: Sat, 21 Jan 2017 09:15:06 -0800

Edited the above text, added MSVC support stolen from llvm headers, moved from leading_zero_count to using logbase2 in algorithm, and cleaned up reference implementation so it is self-contained. Reference pasted below and optimized version with test attached.

```
#include <stdint.h>

/*
 * Preferable provide builtin version when avaible.
 * Only needs to be implemented for [2^12 .. UF16_UINT64_MAx]
 */
#ifndef uf16_logbase2_floor

/* Returns 0 when `k == 0`. */
static inline int __uf16_logbase2_floor_reference(uint64_t k)
{
    k |= (k >> 1);
    k |= (k >> 2);
    k |= (k >> 4);
    k |= (k >> 8);
    k |= (k >> 16);
    k |= (k >> 32);
    k -= (k >> 1) & UINT64_C(0x5555555555555555);
    k = (k & UINT64_C(0x3333333333333333)) + 
        ((k >> 2) & UINT64_C(0x3333333333333333));
    k = (k + (k >> 4)) & UINT64_C(0x0f0f0f0f0f0f0f0f);
    k = (k * UINT64_C(0x0101010101010101)) >> 56;
    return k;
}

#define uf16_logbase2_floor(k) __uf16_logbase2_floor_reference(k)

#endif /* uf16_logbase2_floor */

    if (v < (1 << 12)) {
        return v;
    }
    p = (v >> 11) - 1;
    m = v - (p << 11);
    return m << p;
}

static inline uint16_t uf16_encode(uint64_t k)
{
    uint16_t p, f;

    if (k < (1 << 12)) {
        return (uint16_t)k;
    }
    if (k >= UF16_UINT64_MAX) {
        return UF16_MAX;
    }
    p = (uint16_t)(uf16_logbase2_floor(k) - 12);
    f = (uint16_t)(k >> p);
    return (p << 11) + f;
}
```
[uf16.h.zip](https://github.com/quicwg/base-drafts/files/721330/uf16.h.zip)

-- 
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/109#issuecomment-274274588

---

From: MikkelFJ <[email-masked]>
Date: Sat, 21 Jan 2017 11:59:25 -0800

Discovered that logbase2 can work in 32-bits and debruijn is then very fast.
I have edited the above code snippet reference text to match content of attached file.

I did some benchmarks. Each encode/decode operation consumes less than 5ns with the reference deBruijn logbase2 implementation, and about 3.5ns with clang __builtin_clz. Using the k>>12 trick before logbase2 really added performance. On unoptimized builds the encode/decode operation is about 30ns default, and 20ns builtin.

Considering the heaviest operation is a 32-bit multiplication, or alternatively, a 32-bit leading zero bit count instruction, I'd say its fast enough for most use cases.

[uf16.h.zip](https://github.com/quicwg/base-drafts/files/721429/uf16.h.zip)

-- 
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/109#issuecomment-274284520

---

From: MikkelFJ <[email-masked]>
Date: Sun, 22 Jan 2017 04:34:44 -0800

In addition, I can now say exactly what is wrong in the spec - the first section is correction:

>  The time format used in the ACK frame above is a 16-bit unsigned
>    float with 11 explicit bits of mantissa and 5 bits of explicit
>    exponent, specifying time in microseconds.  The bit format is loosely
>    modeled after IEEE 754.  For example, 1 microsecond is represented as
>    0x1, which has an exponent of zero, presented in the 5 high order
>    bits, and mantissa of 1, presented in the 11 low order bits.

First observe that the explicit, or encoded exponent e in my description only apply when e >= 2, but it is valid include e >= 1 because the computation in either branch results in the same value, it is just more efficient to branch at e >= 2, and this is also what Chromium implements.

>   When  the explicit exponent is greater than zero, an implicit high-order
>    12th bit of 1 is assumed in the mantissa.  

This is only half-true. In fact the effective exponent is always one less than the explicit exponent, so we have effective exponents that are 0 and -1 as well, but it is much more efficient to implement the case e >= 2 separately and documenting the format otherwise is not really helpful to implementers.

The next section is wrong:
> For example, a floating
>    value of 0x800 has an explicit exponent of 1, as well as an explicit
>    mantissa of 0, but then has an effective mantissa of 4096 (12th bit
>    is assumed to be 1).

The explicit exponent is 1, and the implicit 12'th fraction bit has the value 2^11 = 2048.
The effective exponents is one less, so it is 0. Hence the resulting value is 2048 which is also a test case in my attached utf16.h file.

> Additionally, the actual exponent is one-less
>    than the explicit exponent,

This is correct. It is always one less. 

> and the value represents 4096  microseconds.

Incorrect. It represents 2048 microseconds.

>   Any values larger than the representable range are
>    clamped to 0xFFFF.

Correct.

-- 
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/109#issuecomment-274328283

---

From: MikkelFJ <[email-masked]>
Date: Sun, 22 Jan 2017 15:38:15 -0800

Added uf16.h as gist. Includes proposed text for uf16 format spec in comment.

https://gist.github.com/mikkelfj/64deb01b86d68f3d7aacff4b113c22d8

-- 
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/109#issuecomment-274369915

---

From: MikkelFJ <[email-masked]>
Date: Tue, 24 Jan 2017 06:33:38 -0800

One a related note. The first timestamp in the ACK frame is a 32-bit value stated to be relative to the connection start, measured in microseconds. This only allows for 71 minutes of connection time after which it must roll over somehow. If the same field was stored in 2 bytes in uf16 global there is more than enough range and the gradual precision loss relative to the starting time doesn't really matter. It also saves two bytes and avoids two different encodings for the same value type.

-- 
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/109#issuecomment-274819000

---

From: Mark Nottingham <[email-masked]>
Date: Wed, 25 Jan 2017 23:11:15 -0800

As discussed in Tokyo, updated drafts by using the floating point details in this thread

-- 
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/109#issuecomment-275321773

---

From: MikkelFJ <[email-masked]>
Date: Thu, 26 Jan 2017 07:24:35 -0800

Note that I just corrected an incorrect description of the encoding algorithm: v - p should have been v - (p << 1). The reference implementation is correct. Edited in the above. You can also see the text in the gist with revision history. I try to keep this up to date if I find anything wrong or inaccurate.

-- 
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/109#issuecomment-275416123

---

From: Marten Seemann <[email-masked]>
Date: Thu, 26 Jan 2017 07:35:24 -0800

Just for reference, this is how we implemented it in quic-go: https://github.com/lucas-clemente/quic-go/blob/master/utils/float16.go

-- 
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/109#issuecomment-275419164

---

From: MikkelFJ <[email-masked]>
Date: Thu, 26 Jan 2017 07:36:09 -0800

I copied some test cases from that implementation.

-- 
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/109#issuecomment-275419453