1/*
2 *  Copyright (c) 2012 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#include "webrtc/modules/rtp_rtcp/source/rtp_packet_history.h"
12
13#include <assert.h>
14#include <stdlib.h>
15#include <string.h>   // memset
16
17#include <algorithm>
18#include <limits>
19#include <set>
20
21#include "webrtc/base/checks.h"
22#include "webrtc/base/logging.h"
23#include "webrtc/modules/rtp_rtcp/source/rtp_utility.h"
24#include "webrtc/system_wrappers/include/critical_section_wrapper.h"
25
26namespace webrtc {
27
28static const int kMinPacketRequestBytes = 50;
29
30RTPPacketHistory::RTPPacketHistory(Clock* clock)
31    : clock_(clock),
32      critsect_(CriticalSectionWrapper::CreateCriticalSection()),
33      store_(false),
34      prev_index_(0) {}
35
36RTPPacketHistory::~RTPPacketHistory() {
37}
38
39void RTPPacketHistory::SetStorePacketsStatus(bool enable,
40                                             uint16_t number_to_store) {
41  CriticalSectionScoped cs(critsect_.get());
42  if (enable) {
43    if (store_) {
44      LOG(LS_WARNING) << "Purging packet history in order to re-set status.";
45      Free();
46    }
47    assert(!store_);
48    Allocate(number_to_store);
49  } else {
50    Free();
51  }
52}
53
54void RTPPacketHistory::Allocate(size_t number_to_store) {
55  assert(number_to_store > 0);
56  assert(number_to_store <= kMaxHistoryCapacity);
57  store_ = true;
58  stored_packets_.resize(number_to_store);
59}
60
61void RTPPacketHistory::Free() {
62  if (!store_) {
63    return;
64  }
65
66  stored_packets_.clear();
67
68  store_ = false;
69  prev_index_ = 0;
70}
71
72bool RTPPacketHistory::StorePackets() const {
73  CriticalSectionScoped cs(critsect_.get());
74  return store_;
75}
76
77int32_t RTPPacketHistory::PutRTPPacket(const uint8_t* packet,
78                                       size_t packet_length,
79                                       int64_t capture_time_ms,
80                                       StorageType type) {
81  CriticalSectionScoped cs(critsect_.get());
82  if (!store_) {
83    return 0;
84  }
85
86  assert(packet);
87  assert(packet_length > 3);
88
89  if (packet_length > IP_PACKET_SIZE) {
90    LOG(LS_WARNING) << "Failed to store RTP packet with length: "
91                    << packet_length;
92    return -1;
93  }
94
95  const uint16_t seq_num = (packet[2] << 8) + packet[3];
96
97  // If index we're about to overwrite contains a packet that has not
98  // yet been sent (probably pending in paced sender), we need to expand
99  // the buffer.
100  if (stored_packets_[prev_index_].length > 0 &&
101      stored_packets_[prev_index_].send_time == 0) {
102    size_t current_size = static_cast<uint16_t>(stored_packets_.size());
103    if (current_size < kMaxHistoryCapacity) {
104      size_t expanded_size = std::max(current_size * 3 / 2, current_size + 1);
105      expanded_size = std::min(expanded_size, kMaxHistoryCapacity);
106      Allocate(expanded_size);
107      // Causes discontinuity, but that's OK-ish. FindSeqNum() will still work,
108      // but may be slower - at least until buffer has wrapped around once.
109      prev_index_ = current_size;
110    }
111  }
112
113  // Store packet
114  // TODO(sprang): Overhaul this class and get rid of this copy step.
115  //               (Finally introduce the RtpPacket class?)
116  memcpy(stored_packets_[prev_index_].data, packet, packet_length);
117  stored_packets_[prev_index_].length = packet_length;
118
119  stored_packets_[prev_index_].sequence_number = seq_num;
120  stored_packets_[prev_index_].time_ms =
121      (capture_time_ms > 0) ? capture_time_ms : clock_->TimeInMilliseconds();
122  stored_packets_[prev_index_].send_time = 0;  // Packet not sent.
123  stored_packets_[prev_index_].storage_type = type;
124  stored_packets_[prev_index_].has_been_retransmitted = false;
125
126  ++prev_index_;
127  if (prev_index_ >= stored_packets_.size()) {
128    prev_index_ = 0;
129  }
130  return 0;
131}
132
133bool RTPPacketHistory::HasRTPPacket(uint16_t sequence_number) const {
134  CriticalSectionScoped cs(critsect_.get());
135  if (!store_) {
136    return false;
137  }
138
139  int32_t index = 0;
140  bool found = FindSeqNum(sequence_number, &index);
141  if (!found) {
142    return false;
143  }
144
145  if (stored_packets_[index].length == 0) {
146    // Invalid length.
147    return false;
148  }
149  return true;
150}
151
152bool RTPPacketHistory::SetSent(uint16_t sequence_number) {
153  CriticalSectionScoped cs(critsect_.get());
154  if (!store_) {
155    return false;
156  }
157
158  int32_t index = 0;
159  bool found = FindSeqNum(sequence_number, &index);
160  if (!found) {
161    return false;
162  }
163
164  // Send time already set.
165  if (stored_packets_[index].send_time != 0) {
166    return false;
167  }
168
169  stored_packets_[index].send_time = clock_->TimeInMilliseconds();
170  return true;
171}
172
173bool RTPPacketHistory::GetPacketAndSetSendTime(uint16_t sequence_number,
174                                               int64_t min_elapsed_time_ms,
175                                               bool retransmit,
176                                               uint8_t* packet,
177                                               size_t* packet_length,
178                                               int64_t* stored_time_ms) {
179  CriticalSectionScoped cs(critsect_.get());
180  RTC_CHECK_GE(*packet_length, static_cast<size_t>(IP_PACKET_SIZE));
181  if (!store_)
182    return false;
183
184  int32_t index = 0;
185  bool found = FindSeqNum(sequence_number, &index);
186  if (!found) {
187    LOG(LS_WARNING) << "No match for getting seqNum " << sequence_number;
188    return false;
189  }
190
191  size_t length = stored_packets_[index].length;
192  assert(length <= IP_PACKET_SIZE);
193  if (length == 0) {
194    LOG(LS_WARNING) << "No match for getting seqNum " << sequence_number
195                    << ", len " << length;
196    return false;
197  }
198
199  // Verify elapsed time since last retrieve, but only for retransmissions and
200  // always send packet upon first retransmission request.
201  int64_t now = clock_->TimeInMilliseconds();
202  if (min_elapsed_time_ms > 0 && retransmit &&
203      stored_packets_[index].has_been_retransmitted &&
204      ((now - stored_packets_[index].send_time) < min_elapsed_time_ms)) {
205    return false;
206  }
207
208  if (retransmit) {
209    if (stored_packets_[index].storage_type == kDontRetransmit) {
210      // No bytes copied since this packet shouldn't be retransmitted or is
211      // of zero size.
212      return false;
213    }
214    stored_packets_[index].has_been_retransmitted = true;
215  }
216  stored_packets_[index].send_time = clock_->TimeInMilliseconds();
217  GetPacket(index, packet, packet_length, stored_time_ms);
218  return true;
219}
220
221void RTPPacketHistory::GetPacket(int index,
222                                 uint8_t* packet,
223                                 size_t* packet_length,
224                                 int64_t* stored_time_ms) const {
225  // Get packet.
226  size_t length = stored_packets_[index].length;
227  memcpy(packet, stored_packets_[index].data, length);
228  *packet_length = length;
229  *stored_time_ms = stored_packets_[index].time_ms;
230}
231
232bool RTPPacketHistory::GetBestFittingPacket(uint8_t* packet,
233                                            size_t* packet_length,
234                                            int64_t* stored_time_ms) {
235  CriticalSectionScoped cs(critsect_.get());
236  if (!store_)
237    return false;
238  int index = FindBestFittingPacket(*packet_length);
239  if (index < 0)
240    return false;
241  GetPacket(index, packet, packet_length, stored_time_ms);
242  return true;
243}
244
245// private, lock should already be taken
246bool RTPPacketHistory::FindSeqNum(uint16_t sequence_number,
247                                  int32_t* index) const {
248  uint16_t temp_sequence_number = 0;
249  if (prev_index_ > 0) {
250    *index = prev_index_ - 1;
251    temp_sequence_number = stored_packets_[*index].sequence_number;
252  } else {
253    *index = stored_packets_.size() - 1;
254    temp_sequence_number = stored_packets_[*index].sequence_number;  // wrap
255  }
256
257  int32_t idx = (prev_index_ - 1) - (temp_sequence_number - sequence_number);
258  if (idx >= 0 && idx < static_cast<int>(stored_packets_.size())) {
259    *index = idx;
260    temp_sequence_number = stored_packets_[*index].sequence_number;
261  }
262
263  if (temp_sequence_number != sequence_number) {
264    // We did not found a match, search all.
265    for (uint16_t m = 0; m < stored_packets_.size(); m++) {
266      if (stored_packets_[m].sequence_number == sequence_number) {
267        *index = m;
268        temp_sequence_number = stored_packets_[*index].sequence_number;
269        break;
270      }
271    }
272  }
273  if (temp_sequence_number == sequence_number) {
274    // We found a match.
275    return true;
276  }
277  return false;
278}
279
280int RTPPacketHistory::FindBestFittingPacket(size_t size) const {
281  if (size < kMinPacketRequestBytes || stored_packets_.empty())
282    return -1;
283  size_t min_diff = std::numeric_limits<size_t>::max();
284  int best_index = -1;  // Returned unchanged if we don't find anything.
285  for (size_t i = 0; i < stored_packets_.size(); ++i) {
286    if (stored_packets_[i].length == 0)
287      continue;
288    size_t diff = (stored_packets_[i].length > size)
289                      ? (stored_packets_[i].length - size)
290                      : (size - stored_packets_[i].length);
291    if (diff < min_diff) {
292      min_diff = diff;
293      best_index = static_cast<int>(i);
294    }
295  }
296  return best_index;
297}
298
299RTPPacketHistory::StoredPacket::StoredPacket() {}
300
301}  // namespace webrtc
302