1 /*
2  *  Copyright (c) 2019 The WebRTC project authors. All Rights Reserved.
3  *
4  *  Use of this source code is governed by a BSD-style license
5  *  that can be found in the LICENSE file in the root of the source
6  *  tree. An additional intellectual property rights grant can be found
7  *  in the file PATENTS.  All contributing project authors may
8  *  be found in the AUTHORS file in the root of the source tree.
9  */
10 
11 #ifndef MODULES_RTP_RTCP_SOURCE_RTP_SEQUENCE_NUMBER_MAP_H_
12 #define MODULES_RTP_RTCP_SOURCE_RTP_SEQUENCE_NUMBER_MAP_H_
13 
14 #include <cstddef>
15 #include <cstdint>
16 #include <deque>
17 
18 #include "absl/types/optional.h"
19 
20 namespace webrtc {
21 
22 // Records the association of RTP sequence numbers to timestamps and to whether
23 // the packet was first and/or last in the frame.
24 //
25 // 1. Limits number of entries. Whenever |max_entries| is about to be exceeded,
26 //    the size is reduced by approximately 25%.
27 // 2. RTP sequence numbers wrap around relatively infrequently.
28 //    This class therefore only remembers at most the last 2^15 RTP packets,
29 //    so that the newest packet's sequence number is still AheadOf the oldest
30 //    packet's sequence number.
31 // 3. Media frames are sometimes split into several RTP packets.
32 //    In such a case, Insert() is expected to be called once for each packet.
33 //    The timestamp is not expected to change between those calls.
34 class RtpSequenceNumberMap final {
35  public:
36   struct Info final {
Infofinal37     Info(uint32_t timestamp, bool is_first, bool is_last)
38         : timestamp(timestamp), is_first(is_first), is_last(is_last) {}
39 
40     friend bool operator==(const Info& lhs, const Info& rhs) {
41       return lhs.timestamp == rhs.timestamp && lhs.is_first == rhs.is_first &&
42              lhs.is_last == rhs.is_last;
43     }
44 
45     uint32_t timestamp;
46     bool is_first;
47     bool is_last;
48   };
49 
50   explicit RtpSequenceNumberMap(size_t max_entries);
51   RtpSequenceNumberMap(const RtpSequenceNumberMap& other) = delete;
52   RtpSequenceNumberMap& operator=(const RtpSequenceNumberMap& other) = delete;
53   ~RtpSequenceNumberMap();
54 
55   void InsertPacket(uint16_t sequence_number, Info info);
56   void InsertFrame(uint16_t first_sequence_number,
57                    size_t packet_count,
58                    uint32_t timestamp);
59 
60   absl::optional<Info> Get(uint16_t sequence_number) const;
61 
62   size_t AssociationCountForTesting() const;
63 
64  private:
65   struct Association {
AssociationAssociation66     explicit Association(uint16_t sequence_number)
67         : Association(sequence_number, Info(0, false, false)) {}
68 
AssociationAssociation69     Association(uint16_t sequence_number, Info info)
70         : sequence_number(sequence_number), info(info) {}
71 
72     uint16_t sequence_number;
73     Info info;
74   };
75 
76   const size_t max_entries_;
77 
78   // The non-transitivity of AheadOf() would be problematic with a map,
79   // so we use a deque instead.
80   std::deque<Association> associations_;
81 };
82 
83 }  // namespace webrtc
84 
85 #endif  // MODULES_RTP_RTCP_SOURCE_RTP_SEQUENCE_NUMBER_MAP_H_
86