[Cellar] Timestamps again

["Timothy B. Terriberry" <[e-mail]>]

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).