Moved sequence number specific operations from mod_ops.h

Moved sequence number specific operations from mod_ops.h
to sequence_number_util.h

Also in this CL:
  - Implemented a MinDiff function which finds the smallest diff of two
    wrapping numbers.
  - Implemented comparators for sequence numbers.

BUG=
R=mflodman@webrtc.org, tommi@webrtc.org, torbjorng@webrtc.org

Committed: https://crrev.com/2cb73413f4d78541b0628603f04aa342d2a6c3ea
Cr-Commit-Position: refs/heads/master@{#12083}

[philipel, 2016-03-17 08:44:59]

philipel@webrtc.org changed reviewers:
+ mflodman@webrtc.org, torbjorng@webrtc.org

[philipel, 2016-03-17 08:45:00]

I have mostly shuffled code around so only a few things are new:
 - The sequence number comparators in sequence_number_util.h
   (and matching unittests).
 - The MinDiff function in ModOps.h
   (and matching unittests).

[torbjorng (webrtc), 2016-03-17 10:47:27]

Please define the exact semantics of the many AheadOf* functions. I cannot tell
if they are correct or incorrect now.

I commented on one more specifically. That comment is partially valid for more
of them.

https://codereview.webrtc.org/1814753002/diff/20001/webrtc/modules/video_codi...
File webrtc/modules/video_coding/sequence_number_util.h (right):

https://codereview.webrtc.org/1814753002/diff/20001/webrtc/modules/video_codi...
webrtc/modules/video_coding/sequence_number_util.h:21: // Test if the sequence
number a is ahead or at sequence number b.
Nit: Please quite variable names, e.g. |a|.

https://codereview.webrtc.org/1814753002/diff/20001/webrtc/modules/video_codi...
webrtc/modules/video_coding/sequence_number_util.h:25: template <typename T, T
M>
I cannot work out the intended semantics of this function, I'm afraid.
The first return criterium looks very suspicious, as it will change for
AheadOrAt(a,b) vs AheadOrAt(a+1 (mod M),b+1 (mod M)) for some a,b.

Defining a criteria for full ordering for a ring is slightly odd.  (It will
be true that a > b, b > c, c > a for some a,b,c, which is confusing.)

Is the "max distance' mentioned in the function comment floor(M/2)?
Please spell that out, and please explain why M/2 and more peculiarly
floor(M/2) bears any meaning.

Perhaps it would make more sense to have a 3-way function which allows
callers to explicitly define a "remaining distance" between |a| and |b| mod M?
A caller that thinks floor(M/2) is a good such limit would pass that in.

[philipel, 2016-03-17 12:32:40]

https://codereview.webrtc.org/1814753002/diff/20001/webrtc/modules/video_codi...
File webrtc/modules/video_coding/sequence_number_util.h (right):

https://codereview.webrtc.org/1814753002/diff/20001/webrtc/modules/video_codi...
webrtc/modules/video_coding/sequence_number_util.h:21: // Test if the sequence
number a is ahead or at sequence number b.
On 2016/03/17 10:47:27, torbjorng (webrtc) wrote:
> Nit: Please quite variable names, e.g. |a|.

Done.

https://codereview.webrtc.org/1814753002/diff/20001/webrtc/modules/video_codi...
webrtc/modules/video_coding/sequence_number_util.h:25: template <typename T, T
M>
On 2016/03/17 10:47:27, torbjorng (webrtc) wrote:
> I cannot work out the intended semantics of this function, I'm afraid.
> The first return criterium looks very suspicious, as it will change for
> AheadOrAt(a,b) vs AheadOrAt(a+1 (mod M),b+1 (mod M)) for some a,b.
> 
> Defining a criteria for full ordering for a ring is slightly odd.  (It will
> be true that a > b, b > c, c > a for some a,b,c, which is confusing.)
> 
> Is the "max distance' mentioned in the function comment floor(M/2)?
> Please spell that out, and please explain why M/2 and more peculiarly
> floor(M/2) bears any meaning.
> 
> Perhaps it would make more sense to have a 3-way function which allows
> callers to explicitly define a "remaining distance" between |a| and |b| mod M?
> A caller that thinks floor(M/2) is a good such limit would pass that in.

The reason for checking if the two numbers are at the maximum distance from each
other is to make sure that AheadOrAt(a,b) != AheadOrAt(b,a) which can cause
sorting algorithms to never finish. But maybe it is better to just DCHECK that
the numbers aren't at max distance from each other since we can't know, even
according to our own definition, which number that is ahead.

About the ordering, you should not think of wrapping sequence numbers as a ring,
you should think of them as a pragmatic solution for sequence numbers. There is
no strict mathematic definition involved, just pragmatic ideas. :)

I will expand the comment with more details of the behavior of this function.

I don't really understand your suggestion about a 3-way function, could you
clarify?

[torbjorng (webrtc), 2016-03-17 14:01:17]

Philip and I talked offline; I will need a day or two before I can complete a
more thorough analysis of these sequence number functions.

[torbjorng (webrtc), 2016-03-21 12:32:27]

lgtm with suggested change.

https://codereview.webrtc.org/1814753002/diff/20001/webrtc/modules/video_codi...
File webrtc/modules/video_coding/sequence_number_util.h (right):

https://codereview.webrtc.org/1814753002/diff/20001/webrtc/modules/video_codi...
webrtc/modules/video_coding/sequence_number_util.h:30: if (MinDiff<T, M>(a, b)
== maxDist)
We agree that this ought to be triggered just for even M.
(Test cases also need updating.)

[philipel, 2016-03-21 12:56:21]

mflodman@, ptal

https://codereview.webrtc.org/1814753002/diff/20001/webrtc/modules/video_codi...
File webrtc/modules/video_coding/sequence_number_util.h (right):

https://codereview.webrtc.org/1814753002/diff/20001/webrtc/modules/video_codi...
webrtc/modules/video_coding/sequence_number_util.h:30: if (MinDiff<T, M>(a, b)
== maxDist)
On 2016/03/21 12:32:26, torbjorng (webrtc) wrote:
> We agree that this ought to be triggered just for even M.
> (Test cases also need updating.)

Done.

[philipel, 2016-03-21 12:57:12]

The CQ bit was checked by philipel@webrtc.org

[philipel, 2016-03-21 12:57:13]

The patchset sent to the CQ was uploaded after l-g-t-m from torbjorng@webrtc.org
Link to the patchset: https://codereview.webrtc.org/1814753002/#ps40001 (title:
"Feedback fixes.")

[commit-bot: I haz the power, 2016-03-21 12:57:18]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1814753002/40001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1814753002/40001

[commit-bot: I haz the power, 2016-03-21 13:15:26]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-03-21 13:15:26]

Try jobs failed on following builders:
  presubmit on tryserver.webrtc (JOB_FAILED,
http://build.chromium.org/p/tryserver.webrtc/builders/presubmit/builds/4316)

[philipel, 2016-03-21 15:43:38]

philipel@webrtc.org changed reviewers:
+ tommi@webrtc.org

[philipel, 2016-03-21 15:43:39]

tommi@, ptal

[tommi, 2016-03-21 16:13:14]

rs lgtm with an appropriate fix for the below (assuming I'm not
misunderstanding)

https://codereview.webrtc.org/1814753002/diff/40001/webrtc/modules/video_codi...
File webrtc/modules/video_coding/sequence_number_util.h (right):

https://codereview.webrtc.org/1814753002/diff/40001/webrtc/modules/video_codi...
webrtc/modules/video_coding/sequence_number_util.h:66: struct SeqNumComp_;
why the postfix underscore?  if it's meant to distinguish public vs internal
impl details, consider putting this into a nested 'internal' namespace.  Since a
postfix underscore means a specific thing in the style guide, I think we
shouldn't imply a different style here.

[philipel, 2016-03-21 16:19:28]

https://codereview.webrtc.org/1814753002/diff/40001/webrtc/modules/video_codi...
File webrtc/modules/video_coding/sequence_number_util.h (right):

https://codereview.webrtc.org/1814753002/diff/40001/webrtc/modules/video_codi...
webrtc/modules/video_coding/sequence_number_util.h:66: struct SeqNumComp_;
On 2016/03/21 16:13:13, tommi-webrtc wrote:
> why the postfix underscore?  if it's meant to distinguish public vs internal
> impl details, consider putting this into a nested 'internal' namespace.  Since
a
> postfix underscore means a specific thing in the style guide, I think we
> shouldn't imply a different style here.

Done.

[philipel, 2016-03-21 16:20:02]

The CQ bit was checked by philipel@webrtc.org

[philipel, 2016-03-21 16:20:02]

The patchset sent to the CQ was uploaded after l-g-t-m from
torbjorng@webrtc.org, tommi@webrtc.org
Link to the patchset: https://codereview.webrtc.org/1814753002/#ps60001 (title:
"Feedback fixes and format.")

[commit-bot: I haz the power, 2016-03-21 16:20:04]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1814753002/60001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1814753002/60001

[commit-bot: I haz the power, 2016-03-21 19:10:29]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-03-21 19:10:30]

Try jobs failed on following builders:
  win_drmemory_light on tryserver.webrtc (JOB_FAILED,
http://build.chromium.org/p/tryserver.webrtc/builders/win_drmemory_light/buil...)

[mflodman, 2016-03-22 08:06:27]

rs lgtm

[philipel, 2016-03-22 09:04:00]

Description was changed from

==========
Moved sequence number specific operations from mod_ops.h
to sequence_number_util.h

Also in this CL:
  - Implemented a MinDiff function which finds the smallest diff of two
    wrapping numbers.
  - Implemented comparators for sequence numbers.

BUG=
==========

to

==========
Moved sequence number specific operations from mod_ops.h
to sequence_number_util.h

Also in this CL:
  - Implemented a MinDiff function which finds the smallest diff of two
    wrapping numbers.
  - Implemented comparators for sequence numbers.

BUG=
R=mflodman@webrtc.org, tommi@webrtc.org, torbjorng@webrtc.org

Committed:
https://chromium.googlesource.com/external/webrtc/+/2cb73413f4d78541b0628603f...
==========

[philipel, 2016-03-22 09:04:01]

Committed patchset #5 (id:80001) manually as
2cb73413f4d78541b0628603f04aa342d2a6c3ea (presubmit successful).

[commit-bot: I haz the power, 2016-03-22 09:04:03]

Description was changed from

==========
Moved sequence number specific operations from mod_ops.h
to sequence_number_util.h

Also in this CL:
  - Implemented a MinDiff function which finds the smallest diff of two
    wrapping numbers.
  - Implemented comparators for sequence numbers.

BUG=
R=mflodman@webrtc.org, tommi@webrtc.org, torbjorng@webrtc.org

Committed:
https://chromium.googlesource.com/external/webrtc/+/2cb73413f4d78541b0628603f...
==========

to

==========
Moved sequence number specific operations from mod_ops.h
to sequence_number_util.h

Also in this CL:
  - Implemented a MinDiff function which finds the smallest diff of two
    wrapping numbers.
  - Implemented comparators for sequence numbers.

BUG=
R=mflodman@webrtc.org, tommi@webrtc.org, torbjorng@webrtc.org

Committed: https://crrev.com/2cb73413f4d78541b0628603f04aa342d2a6c3ea
Cr-Commit-Position: refs/heads/master@{#12083}
==========

[commit-bot: I haz the power, 2016-03-22 09:04:04]

Patchset 5 (id:??) landed as
https://crrev.com/2cb73413f4d78541b0628603f04aa342d2a6c3ea
Cr-Commit-Position: refs/heads/master@{#12083}