Subject: [Cellar] Timestamps again

From: "Timothy B. Terriberry" <[email-masked]>
Date: Fri, 11 Jun 2021 14:31:58 -0700

Hello CELLAR friends,

Michael Richardson asked me to review draft-cellar-matroska, which has 
been taking me longer than I had hoped, but I am making progress. 
However, I did run across one issue that might require some discussion 
on the list to resolve, so I thought I would send it sooner rather than 
later.

Namely, I was skeptical that the procedures outlined in Section 26.5 
would be able to reversibly translate between audio sample numbers and 
scaled timestamps. So I wrote a program to check.

I set up the program to evaluate all audio sample rates between 8 kHz 
and 192 kHz in units of 1 Hz, and for each sample rate to check all 
sample numbers between 0 and the product of the sample rate and the 
TimestampScale, divided by the gcd of that number with 1,000,000,000 
(basically, for this number, all of the divisions are exact, and beyond 
that number the remainders should repeat). This is actually quite a lot 
of cases to check exhaustively and would take quite a long time to 
complete. However, it may be able to generate counter-examples very quickly.

I checked both strategies outlined in the text:
(a) Truncate TimestampScale and round all other divisions, and
(b) Use a slightly smaller TimestampScale and truncate the division in 
the raw to absolute timestamp conversion (as suggested in paragraph 5).

In fact, the program (attached), was able to find counter examples for 
both strategies very quickly.

For strategy (a), since 8,000 divides 1,000,000,000 exactly (giving a 
TimestampScale of 125,000), all of the divisions for all sample numbers 
are exact (whether or not you round), and everything is fine. However, 
the first counter example was found for 8,001 Hz (where the 
TimestampScale is 124,984), with sample number 165,781.

The raw timestamp computed in the muxer is thus
   (1,000,000,000*165,781 + 4000)/8001 = 20,720,034,996 ns.
The absolute timestamp is then
   (20,720,034,996 + 62,492)/124,984 = 165,782.
This is approximately the same as the sample number, which given the 
choice of TimestampScale, is to be expected, and is in fact the first 
sample number where the match is not exact. However, the absolute 
timestamp computed in the Reader becomes
   165,782*124,984 = 20,720,097,488 ns.
This produces a sample number of
   (20,720,097,488*8,001 + 500,000,000)/1,000,000,000 = 165,782.
This is off by one (in the positive direction) from the original.

For strategy (b), the first counter example was for 8 kHz (where the 
"slightly smaller" TimestampScale is 124,999), with sample number 62,501.

The raw timestamp computed in the muxer is thus
  (1,000,000,000*62,501 + 4000)/8000 = 7,812,625,000 ns.
The absolute timestamp is then
   (7,812,625,000 + 62,499)/124,999 = 62,501.
Here the match with the sample number is still exact. However, the raw 
timestamp computed in the Reader becomes
   62,501*124,999 = 7,812,562,499 ns.
This produces a sample number of
   (7,812,562,499*8,000 + 500,000,000)/1,000,000,000 = 62,500.
This is also off by one from the original, but in the negative direction.

I have attached the program's source code so that you can check whether 
or not I made any mistakes and modify the parameters to generate your 
own counter-examples (or test approaches to resolving the issue).

---

From: Steve Lhomme <[email-masked]>
Date: Sun, 13 Jun 2021 10:08:07 +0200

> Hello CELLAR friends,

Hi Tim,

> scaled timestamps. So I wrote a program to check.

I think this section is outdated. This is still an ongoing subject as we 
tried to have some form of sample accuracy in Matroska.
See the (lenghty) discussion at issue 422 [1].

One possibility is to use the existing TrackTimestampScale element which 
wasn't designed for that but works pretty well. It's backward compatible 
although there is a high chance a lot of readers don't handle it properly.

A more solid solution would be to write the proper sampling rate of the 
source (but that becomes complicated in case of Variable Frame Rate as 
found nowadays in video games).

> The absolute timestamp is then

I think the TrackTimecodeScale solves both these examples, because it 
using a floating point estimation before rounding the numbers. It allows 
finer granularity for each sample. For audio-only files it's even 
clearer because no matter what the TimestampScale you pick, the 
TrackTimecodeScale is directly related to the sampling frequency, in 
floating point.
The drawback is that the samples are accurate per packed blocks of data, 
then it's up to the decoder to determine the timestamp for each sample 
in a packed block.

I made a program [2] to check the tricky cases where a mixing of track 
types/frequency forces some compromise on the TimestampScale and thus on 
the rounding precision. I ran it with 8001 Hz and there is no error on 
each possible tick of a Cluster, no matter the video frequency.

As seen in this libavformat patch [3], the TrackTimecodeScale is 
TimestampScale * FrameRate. This is very different than what is 
explained in section 26.5 and 26.6 (which are now 27.5 and 27.6) where 
it's normally around 1. I think both sections have to be rewritten to 
clarify this (issue #517 [4]). Both the old way of using 
TrackTimecodeScale and the new way should be mentioned since old files 
may use the old way, although on the player side it will make no difference.

A big side note: this method cannot work in WebM because it doesn't have 
TrackTimecodeScale. Using a rationale number would also not work there 
as it would not supported. So we need to cover both methods in our 
explanations.

I think we should explain the possibilities and limits of both methods 
(with and without TrackTimecodeScale) when solving issue #517. Both when 
muxing and demuxing to explain what rounding should be used.

> own counter-examples (or test approaches to resolving the issue).

[1] https://github.com/ietf-wg-cellar/matroska-specification/issues/422
[2] 
https://github.com/robUx4/matroska-specification/blob/timestampscale-check/fraction_timestamp.c
[3] 
https://github.com/FFmpeg/FFmpeg/compare/master...robUx4:tracktimestampscale/0
[4] https://github.com/ietf-wg-cellar/matroska-specification/issues/517

---

From: "Timothy B. Terriberry" <[email-masked]>
Date: Mon, 21 Jun 2021 08:21:36 -0700

> although there is a high chance a lot of readers don't handle it properly.

There are some other questions I had about interactions of it with other 
features, but given that it was deprecated I was not too worried about 
them. If you are planning to use it for this, maybe I should be, though.

> found nowadays in video games).

Complicated things might be complicated, but you still need a reliable, 
documented way for the 99% of usage that will not have those complications.

> using a floating point estimation before rounding the numbers. It allows 

I think the issue here is not that there is insufficient precision. 
There are enough code points in the timestamp to uniquely identify each 
sample number, but the rounding rules are not constructed in such a way 
as to guarantee a reversible map between them. That problem could be 
exacerbated by introducing floating point if you are not very careful 
about defining how the truncation and rounding works, since not every 
floating point environment is implemented or configured the same way. It 
certainly becomes a lot harder to test exhaustively.

For what it is worth, the program I attached passes using strategy (b) 
if you choose the "slightly smaller value" for TimestampScale to be 1/2 
of the value recommended in the text, instead of the recommended value 
minus one.

> muxing and demuxing to explain what rounding should be used.

I agree. I look forward to seeing the rewrite of these sections.