Subject: [tsvwg] Eric Rescorla's Discuss on draft-ietf-tsvwg-rlc-fec-scheme-09: (with DISCUSS and COMMENT)

From: Eric Rescorla <[email-masked]>
Date: Tue, 09 Oct 2018 18:05:45 -0700

Eric Rescorla has entered the following ballot position for
draft-ietf-tsvwg-rlc-fec-scheme-09: Discuss

When responding, please keep the subject line intact and reply to all
email addresses included in the To and CC lines. (Feel free to cut this
introductory paragraph, however.)

Please refer to https://www.ietf.org/iesg/statement/discuss-criteria.html
for more information about IESG DISCUSS and COMMENT positions.

The document, along with other ballot positions, can be found here:
https://datatracker.ietf.org/doc/draft-ietf-tsvwg-rlc-fec-scheme/

----------------------------------------------------------------------
DISCUSS:
----------------------------------------------------------------------

Rich version of this review at:
https://mozphab-ietf.devsvcdev.mozaws.net/D3423

I do not believe that this specification is sufficiently precise to be
interoperably implemented.

DETAIL
S 3.4.
>      value, in addition to the maximum FEC-related latency budget
>      (Section 3.1).
>   
>   3.4.  Pseudo-Random Number Generator (PRNG)
>   
>      The RLC FEC Schemes defined in this document rely on the TinyMT32

What is the normative reference here? We can't really plausibly
normatively reference a github link without even a version hash. Is
the code in the appendix the normative description of the algorithm.

S 3.5.
>      These considerations apply both the RLC over GF(2) and RLC over
>      GF(2^^8), the only difference being the value of the m parameter.
>      With the RLC over GF(2) FEC Scheme (Section 5), m MUST be equal to 1.
>      With RLC over GF(2^^8) FEC Scheme (Section 4), m MUST be equal to 8.
>   
>      <CODE BEGINS>

Again, is the normative reference here the code? I note that this code
contains references to constants which are not defined here and
therefore will not compile

S 6.2.
>      ew_size coding coefficients that are computed by the same coefficient
>      generation function (Section Section 3.5), using the repair key and
>      encoding window descriptions carried in the Repair FEC Payload ID.
>      Whenever possible (i.e., when a sub-system covering one or more lost
>      source symbols is of full rank), decoding is performed in order to
>      recover lost source symbols.  Each time an ADUI can be totally

You should provide an algorithm for solving this system or at least a
pointer to a description of how to do so

S 12.2.
>    #define TINYMT32_MEXP 127
>    #define TINYMT32_SH0 1
>    #define TINYMT32_SH1 10
>    #define TINYMT32_SH8 8
>    #define TINYMT32_MASK UINT32_C(0x7fffffff)
>    #define TINYMT32_MUL (1.0f / 16777216.0f)

ANSI C doesn't specify any particular method of computing floating
point arithmetic, so I don't believe that any of this code is portably
deterministic.

S 12.2.
>        s->status[0] = s->status[1];
>        s->status[1] = s->status[2];
>        s->status[2] = x ^ (y << TINYMT32_SH1);
>        s->status[3] = y;
>        s->status[1] ^= -((int32_t)(y & 1)) & s->mat1;
>        s->status[2] ^= -((int32_t)(y & 1)) & s->mat2;

You also can't assume that negative numbers have any particular
representation (e.g., twos complement) so this XOR is not
deterministic.

----------------------------------------------------------------------
COMMENT:
----------------------------------------------------------------------

S 3.4.
>      RLC FEC Schemes defined in this document, the following parameter set
>      MUST be used:
>   
>      o  mat1 = 0x8f7011ee = 2406486510;
>      o  mat2 = 0xfc78ff1f = 4235788063;
>      o  tmat = 0x3793fdff = 932445695.

What is the significance of the semicolons versus periods?

S 3.5.
>       * provided with the appropriate number of coding coefficients to
>       * use for the repair symbol key provided.
>       *
>       * (in) repair_key    key associated to this repair symbol. This
>       *                    parameter is ignored (useless) if m=2 and dt=15
>       * (in) cc_tab[]      pointer to a table of the right size to store

This is not just in, because you are writing it. It is rather in/out.

S 3.5.
>                      if (tinymt32_rand(&s, 16) <= dt) {
>                          cc_tab[i] = (uint8_t) 1;
>                      } else {
>                          cc_tab[i] = (uint8_t) 0;
>                      }
>                  }

This code can be simplified either by using the ternary operator, as
in:

```
cc_tab[i] = tinymt32_rand(&s, 16) <= dt) ? 1 : 0;
```

Actually, you could just do:

```
cc_tab[i] = tinymt32_rand(&s, 16) <= dt);
```

Because C guarantees that comparison operators produce 1 for true and
0 for false.

S 3.5.
>                      do {
>                          cc_tab[i] = (uint8_t) tinymt32_rand(&s, 256);
>                      } while (cc_tab[i] == 0);
>                  }
>              } else {
>                  /* here a certain fraction of coefficients should be 0 */

It's not a certain fraction, it's just a certain probability.

S 12.2.
>     *    Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12),
>     *    September, 2012.
>     */
>    #define TINYMT32_MAT1_PARAM     0x8f7011ee
>    #define TINYMT32_MAT2_PARAM     0xfc78ff1f
>    #define TINYMT32_TMAT_PARAM     0x3793fdff

Is there a reason not to have these be const uint32_t?

S 12.2.
>        s->status[0] = seed;
>        s->status[1] = s->mat1 = TINYMT32_MAT1_PARAM;
>        s->status[2] = s->mat2 = TINYMT32_MAT2_PARAM;
>        s->status[3] = s->tmat = TINYMT32_TMAT_PARAM;
>        for (int i = 1; i < MIN_LOOP; i++) {
>            s->status[i & 3] ^= i + UINT32_C(1812433253)

This constant should not be int he code like this.

S 12.2.
>    /**
>     * This function outputs an integer in the [0 .. maxv-1] range.
>     * @param s     pointer to tinymt internal state.
>     * @return      32-bit unsigned integer between 0 and maxv-1 inclusive.
>     */
>    uint32_t tinymt32_rand (tinymt32_t * s, uint32_t maxv)

This casting is extremely scary. Are you sure that this code is
portably deterministic?

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 9 Oct 2018 18:16:02 -0700

I looped in Thomas Daede, who works on codecs here at Mozilla. He says
about the cast in S 12.2.

"It is deterministic, but it relies on implementation-defined behavior -
in particular, the format of a double precision float. e.g. you would
need to specify C99 Annex F. The most important platform where this
isn't the case is 32-bit x86.

It would be much better if you could do it with fixed point arithmetic."

-Ekr