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// This is the implementation of the PacketBuffer class. It is mostly based on
12// an STL list. The list is kept sorted at all times so that the next packet to
13// decode is at the beginning of the list.
14
15#include "webrtc/modules/audio_coding/neteq/packet_buffer.h"
16
17#include <algorithm>  // find_if()
18
19#include "webrtc/base/logging.h"
20#include "webrtc/modules/audio_coding/codecs/audio_decoder.h"
21#include "webrtc/modules/audio_coding/neteq/decoder_database.h"
22
23namespace webrtc {
24
25// Predicate used when inserting packets in the buffer list.
26// Operator() returns true when |packet| goes before |new_packet|.
27class NewTimestampIsLarger {
28 public:
29  explicit NewTimestampIsLarger(const Packet* new_packet)
30      : new_packet_(new_packet) {
31  }
32  bool operator()(Packet* packet) {
33    return (*new_packet_ >= *packet);
34  }
35
36 private:
37  const Packet* new_packet_;
38};
39
40PacketBuffer::PacketBuffer(size_t max_number_of_packets)
41    : max_number_of_packets_(max_number_of_packets) {}
42
43// Destructor. All packets in the buffer will be destroyed.
44PacketBuffer::~PacketBuffer() {
45  Flush();
46}
47
48// Flush the buffer. All packets in the buffer will be destroyed.
49void PacketBuffer::Flush() {
50  DeleteAllPackets(&buffer_);
51}
52
53bool PacketBuffer::Empty() const {
54  return buffer_.empty();
55}
56
57int PacketBuffer::InsertPacket(Packet* packet) {
58  if (!packet || !packet->payload) {
59    if (packet) {
60      delete packet;
61    }
62    LOG(LS_WARNING) << "InsertPacket invalid packet";
63    return kInvalidPacket;
64  }
65
66  int return_val = kOK;
67
68  if (buffer_.size() >= max_number_of_packets_) {
69    // Buffer is full. Flush it.
70    Flush();
71    LOG(LS_WARNING) << "Packet buffer flushed";
72    return_val = kFlushed;
73  }
74
75  // Get an iterator pointing to the place in the buffer where the new packet
76  // should be inserted. The list is searched from the back, since the most
77  // likely case is that the new packet should be near the end of the list.
78  PacketList::reverse_iterator rit = std::find_if(
79      buffer_.rbegin(), buffer_.rend(),
80      NewTimestampIsLarger(packet));
81
82  // The new packet is to be inserted to the right of |rit|. If it has the same
83  // timestamp as |rit|, which has a higher priority, do not insert the new
84  // packet to list.
85  if (rit != buffer_.rend() &&
86      packet->header.timestamp == (*rit)->header.timestamp) {
87    delete [] packet->payload;
88    delete packet;
89    return return_val;
90  }
91
92  // The new packet is to be inserted to the left of |it|. If it has the same
93  // timestamp as |it|, which has a lower priority, replace |it| with the new
94  // packet.
95  PacketList::iterator it = rit.base();
96  if (it != buffer_.end() &&
97      packet->header.timestamp == (*it)->header.timestamp) {
98    delete [] (*it)->payload;
99    delete *it;
100    it = buffer_.erase(it);
101  }
102  buffer_.insert(it, packet);  // Insert the packet at that position.
103
104  return return_val;
105}
106
107int PacketBuffer::InsertPacketList(PacketList* packet_list,
108                                   const DecoderDatabase& decoder_database,
109                                   uint8_t* current_rtp_payload_type,
110                                   uint8_t* current_cng_rtp_payload_type) {
111  bool flushed = false;
112  while (!packet_list->empty()) {
113    Packet* packet = packet_list->front();
114    if (decoder_database.IsComfortNoise(packet->header.payloadType)) {
115      if (*current_cng_rtp_payload_type != 0xFF &&
116          *current_cng_rtp_payload_type != packet->header.payloadType) {
117        // New CNG payload type implies new codec type.
118        *current_rtp_payload_type = 0xFF;
119        Flush();
120        flushed = true;
121      }
122      *current_cng_rtp_payload_type = packet->header.payloadType;
123    } else if (!decoder_database.IsDtmf(packet->header.payloadType)) {
124      // This must be speech.
125      if (*current_rtp_payload_type != 0xFF &&
126          *current_rtp_payload_type != packet->header.payloadType) {
127        *current_cng_rtp_payload_type = 0xFF;
128        Flush();
129        flushed = true;
130      }
131      *current_rtp_payload_type = packet->header.payloadType;
132    }
133    int return_val = InsertPacket(packet);
134    packet_list->pop_front();
135    if (return_val == kFlushed) {
136      // The buffer flushed, but this is not an error. We can still continue.
137      flushed = true;
138    } else if (return_val != kOK) {
139      // An error occurred. Delete remaining packets in list and return.
140      DeleteAllPackets(packet_list);
141      return return_val;
142    }
143  }
144  return flushed ? kFlushed : kOK;
145}
146
147int PacketBuffer::NextTimestamp(uint32_t* next_timestamp) const {
148  if (Empty()) {
149    return kBufferEmpty;
150  }
151  if (!next_timestamp) {
152    return kInvalidPointer;
153  }
154  *next_timestamp = buffer_.front()->header.timestamp;
155  return kOK;
156}
157
158int PacketBuffer::NextHigherTimestamp(uint32_t timestamp,
159                                      uint32_t* next_timestamp) const {
160  if (Empty()) {
161    return kBufferEmpty;
162  }
163  if (!next_timestamp) {
164    return kInvalidPointer;
165  }
166  PacketList::const_iterator it;
167  for (it = buffer_.begin(); it != buffer_.end(); ++it) {
168    if ((*it)->header.timestamp >= timestamp) {
169      // Found a packet matching the search.
170      *next_timestamp = (*it)->header.timestamp;
171      return kOK;
172    }
173  }
174  return kNotFound;
175}
176
177const RTPHeader* PacketBuffer::NextRtpHeader() const {
178  if (Empty()) {
179    return NULL;
180  }
181  return const_cast<const RTPHeader*>(&(buffer_.front()->header));
182}
183
184Packet* PacketBuffer::GetNextPacket(size_t* discard_count) {
185  if (Empty()) {
186    // Buffer is empty.
187    return NULL;
188  }
189
190  Packet* packet = buffer_.front();
191  // Assert that the packet sanity checks in InsertPacket method works.
192  assert(packet && packet->payload);
193  buffer_.pop_front();
194
195  // Discard other packets with the same timestamp. These are duplicates or
196  // redundant payloads that should not be used.
197  size_t discards = 0;
198
199  while (!Empty() &&
200      buffer_.front()->header.timestamp == packet->header.timestamp) {
201    if (DiscardNextPacket() != kOK) {
202      assert(false);  // Must be ok by design.
203    }
204    ++discards;
205  }
206  // The way of inserting packet should not cause any packet discarding here.
207  // TODO(minyue): remove |discard_count|.
208  assert(discards == 0);
209  if (discard_count)
210    *discard_count = discards;
211
212  return packet;
213}
214
215int PacketBuffer::DiscardNextPacket() {
216  if (Empty()) {
217    return kBufferEmpty;
218  }
219  // Assert that the packet sanity checks in InsertPacket method works.
220  assert(buffer_.front());
221  assert(buffer_.front()->payload);
222  DeleteFirstPacket(&buffer_);
223  return kOK;
224}
225
226int PacketBuffer::DiscardOldPackets(uint32_t timestamp_limit,
227                                    uint32_t horizon_samples) {
228  while (!Empty() && timestamp_limit != buffer_.front()->header.timestamp &&
229         IsObsoleteTimestamp(buffer_.front()->header.timestamp,
230                             timestamp_limit,
231                             horizon_samples)) {
232    if (DiscardNextPacket() != kOK) {
233      assert(false);  // Must be ok by design.
234    }
235  }
236  return 0;
237}
238
239int PacketBuffer::DiscardAllOldPackets(uint32_t timestamp_limit) {
240  return DiscardOldPackets(timestamp_limit, 0);
241}
242
243size_t PacketBuffer::NumPacketsInBuffer() const {
244  return buffer_.size();
245}
246
247size_t PacketBuffer::NumSamplesInBuffer(DecoderDatabase* decoder_database,
248                                        size_t last_decoded_length) const {
249  PacketList::const_iterator it;
250  size_t num_samples = 0;
251  size_t last_duration = last_decoded_length;
252  for (it = buffer_.begin(); it != buffer_.end(); ++it) {
253    Packet* packet = (*it);
254    AudioDecoder* decoder =
255        decoder_database->GetDecoder(packet->header.payloadType);
256    if (decoder && !packet->sync_packet) {
257      if (!packet->primary) {
258        continue;
259      }
260      int duration =
261          decoder->PacketDuration(packet->payload, packet->payload_length);
262      if (duration >= 0) {
263        last_duration = duration;  // Save the most up-to-date (valid) duration.
264      }
265    }
266    num_samples += last_duration;
267  }
268  return num_samples;
269}
270
271void PacketBuffer::IncrementWaitingTimes(int inc) {
272  PacketList::iterator it;
273  for (it = buffer_.begin(); it != buffer_.end(); ++it) {
274    (*it)->waiting_time += inc;
275  }
276}
277
278bool PacketBuffer::DeleteFirstPacket(PacketList* packet_list) {
279  if (packet_list->empty()) {
280    return false;
281  }
282  Packet* first_packet = packet_list->front();
283  delete [] first_packet->payload;
284  delete first_packet;
285  packet_list->pop_front();
286  return true;
287}
288
289void PacketBuffer::DeleteAllPackets(PacketList* packet_list) {
290  while (DeleteFirstPacket(packet_list)) {
291    // Continue while the list is not empty.
292  }
293}
294
295void PacketBuffer::BufferStat(int* num_packets, int* max_num_packets) const {
296  *num_packets = static_cast<int>(buffer_.size());
297  *max_num_packets = static_cast<int>(max_number_of_packets_);
298}
299
300}  // namespace webrtc
301