Re: [Cellar] Timestamps again

Steve Lhomme <slhomme@matroska.org> Sun, 11 July 2021 12:13 UTC

Return-Path: <slhomme@matroska.org>
X-Original-To: cellar@ietfa.amsl.com
Delivered-To: cellar@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 607623A00E5 for <cellar@ietfa.amsl.com>; Sun, 11 Jul 2021 05:13:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.002
X-Spam-Level:
X-Spam-Status: No, score=0.002 tagged_above=-999 required=5 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, NICE_REPLY_A=-0.001, RCVD_IN_DNSWL_BLOCKED=0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=matroska-org.20150623.gappssmtp.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id IisLKuGUnCnf for <cellar@ietfa.amsl.com>; Sun, 11 Jul 2021 05:13:17 -0700 (PDT)
Received: from mail-wm1-x335.google.com (mail-wm1-x335.google.com [IPv6:2a00:1450:4864:20::335]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 52E203A00E1 for <cellar@ietf.org>; Sun, 11 Jul 2021 05:13:16 -0700 (PDT)
Received: by mail-wm1-x335.google.com with SMTP id l17-20020a05600c1d11b029021f84fcaf75so2430234wms.1 for <cellar@ietf.org>; Sun, 11 Jul 2021 05:13:16 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=matroska-org.20150623.gappssmtp.com; s=20150623; h=subject:to:references:from:message-id:date:user-agent:mime-version :in-reply-to:content-language:content-transfer-encoding; bh=sOVec27Ju5TeY1SRI6XU8N2qRlhKtENQvURIXF1XgTw=; b=o8/qXwJ77Rj4I6sG1vkhk9xJWQ4D1KHDV9wKE+b1sgyNHHTNGKkjp0OI9ejgQEZfig pTUSaDmiet3aFIgdoK7ibrLlmrCvgf8dWajqPqCYU33aaVzDbckr8AKmVuoe4Bl585g9 jxFn/zG7RwLfNhZz7Mo0lz3Lagkhcn/XleTPT90byvLXmyusrmRVIiNdPbsEBPfv77/F UYn5H/42Nnbx10Aq/ubhs9e/0D1xenYQWstxwZL2EST9dggD5rwumuSQLhpglTIlgOVZ Z8E2oUc/3EtPM6iz4dIDCU70MDwhQmkoAgpRxKwpixXZ9fUq8M7UhT1Pz5wcQ3iCqMKq Vw5A==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=sOVec27Ju5TeY1SRI6XU8N2qRlhKtENQvURIXF1XgTw=; b=Hy5OYguIF+CFlYsoAFdXSGdnSCXCIq7OT0KZXPJNMd71rTv6Ksoyc+kh6U+INuVr1E t8z3B5Nu8TFaNGK7wrSqFkjmf6luvWCosPtuyBN8wOeByEJDHZGIvZcP/bee9ecdC1we r4SDU/SCws2ZGRd4E5aYObJnAeyJl4oTI2Onq7ZKeND1y27I/+mp7e1WFPdETrbf+SLl 0TehQAL/DJdA9N0cQPugwVyuQyjRvTH76ijXf8gk6gSSAu1danQy8YPjxcYA+tM8CNJR RFHl569Z2qvEMxlqdn2wkG0ZBLpbGFua6EZmTxKApZp2N5NFuoc9VhQW/iU2PdRBXiu7 a0cA==
X-Gm-Message-State: AOAM532B6uAkCsktzyzAvaJ/WpH6k7ZaBk8Qulfkdl1sTXSbj+jxOhJA oUYypGUntkaKyVnDDTthPzvHr01SYM/X/3Lg
X-Google-Smtp-Source: ABdhPJy3dL71Ds+qYdYDCIWpmpm8rPgQHn38wij1eHCzCgWx++s5jlcmN2Z3VXuNi3cMvA1xYlo3Ww==
X-Received: by 2002:a05:600c:4ec8:: with SMTP id g8mr9283483wmq.150.1626005594521; Sun, 11 Jul 2021 05:13:14 -0700 (PDT)
Received: from ?IPv6:2a01:cb0c:20:e900:f54b:af79:56b2:bbbb? (2a01cb0c0020e900f54baf7956b2bbbb.ipv6.abo.wanadoo.fr. [2a01:cb0c:20:e900:f54b:af79:56b2:bbbb]) by smtp.gmail.com with ESMTPSA id j10sm10965583wrt.35.2021.07.11.05.13.13 for <cellar@ietf.org> (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sun, 11 Jul 2021 05:13:14 -0700 (PDT)
To: cellar@ietf.org
References: <1dee863c-3589-21f6-da13-db5beee25d8a@xiph.org>
From: Steve Lhomme <slhomme@matroska.org>
Message-ID: <bfdd125b-4261-690f-2c03-0e068b669c5e@matroska.org>
Date: Sun, 11 Jul 2021 14:13:13 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.11.0
MIME-Version: 1.0
In-Reply-To: <1dee863c-3589-21f6-da13-db5beee25d8a@xiph.org>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cellar/ECiFNH-SqSN0oU-60LAG9dtgzyo>
Subject: Re: [Cellar] Timestamps again
X-BeenThere: cellar@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Codec Encoding for LossLess Archiving and Realtime transmission <cellar.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/cellar>, <mailto:cellar-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cellar/>
List-Post: <mailto:cellar@ietf.org>
List-Help: <mailto:cellar-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/cellar>, <mailto:cellar-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sun, 11 Jul 2021 12:13:19 -0000

On 2021-06-11 23:31, Timothy B. Terriberry wrote:
> 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).

I finally rewrote the parts about timestamp handling:
https://github.com/ietf-wg-cellar/matroska-specification/pull/521

Things are now expressed as ticks: Matroska, Segment, Track. Segment and 
Track being the same if TrackTimestampScale is left to 1.0.

There's a paragraph explaining the rounding that the muxer should use, 
knowing the correct sampling rate, to write "ticks" that can be 
interpreted by the reader accurately to match the samples.

The example you found was not correct seem to match with the formula I 
gave for the muxer and the demuxer. It's a bit counter intuitive as the 
muxer has to estimate the drift that will occur on the Reader math to 
write the value that may not end up giving the proper tick value.

Given the Segment and Track ticks are always(*) the same, the same 
applies to the ticks stored in `Cluster\Timestamp`. And that's where 
most of the drift happens, given a Cluster contains only 65535 ticks. 
I'm not sure existing muxers use that. Otherwise they probably have a 
slight drift in timestamps.

(*) pending 
https://github.com/ietf-wg-cellar/matroska-specification/pull/437 we may 
or may not use the `TrackTimestampScale` again so that the tick to store 
is also be the sample number.