Packet buffer for the new jitter buffer.

webrtc/modules/video_coding/packet_buffer.cc

Index: webrtc/modules/video_coding/packet_buffer.cc
diff --git a/webrtc/modules/video_coding/packet_buffer.cc b/webrtc/modules/video_coding/packet_buffer.cc
new file mode 100644
index 0000000000000000000000000000000000000000..7f1e3dc14826394ce797fdfeaa1e680014a4656e
--- /dev/null
+++ b/webrtc/modules/video_coding/packet_buffer.cc
@@ -0,0 +1,187 @@
+/*
+ *  Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "webrtc/modules/video_coding/packet_buffer.h"
+
+#include <algorithm>
+#include <limits>
+
+#include "webrtc/base/mod_ops.h"
+#include "webrtc/base/checks.h"
+#include "webrtc/modules/video_coding/frame_object.h"
+
+namespace webrtc {
+namespace video_coding {
+
+PacketBuffer::PacketBuffer(size_t start_buffer_size,
+                           size_t max_buffer_size,
+                           OnCompleteFrameCallback* frame_callback)
+    : size_(start_buffer_size),
+      max_size_(max_buffer_size),
+      clear_up_to_(0),
+      initialized_(false),
+      data_buffer_(start_buffer_size),
+      sequence_buffer_(start_buffer_size),
+      frame_callback_(frame_callback) {
+  RTC_DCHECK_LE(start_buffer_size, max_buffer_size);
+  // Buffer size must always be a power of 2.
+  RTC_DCHECK((start_buffer_size & start_buffer_size - 1) == 0);
+  RTC_DCHECK((max_buffer_size & max_buffer_size - 1) == 0);
+}
+
+bool PacketBuffer::InsertPacket(const VCMPacket& packet) {
+  rtc::CritScope lock(&crit_);
+  uint16_t seq_num = packet.seqNum;
+  int index = seq_num % size_;
+
+  if (!initialized_) {
+    clear_up_to_ = seq_num;
+    initialized_ = true;
+  }
+
+  if (sequence_buffer_[index].used) {
+    // Duplicate packet, do nothing.
+    if (data_buffer_[index].seqNum == packet.seqNum)
+      return false;
+
+    // The packet buffer is full, try to expand the buffer.
+    while (ExpandBufferSize() && sequence_buffer_[seq_num % size_].used) {}
+    index = seq_num % size_;
+    // If still full, test if the old packet can be discarded (overwritten
+    // later in the code), if not, return false.
+    if (sequence_buffer_[index].used &&
+        AheadOrAt(sequence_buffer_[index].seq_num, clear_up_to_))
+      return false;
+  }
+
+  sequence_buffer_[index].frame_begin = packet.isFirstPacket;
+  sequence_buffer_[index].frame_end = packet.markerBit;
+  sequence_buffer_[index].seq_num = packet.seqNum;
+  sequence_buffer_[index].continuous = false;
+  sequence_buffer_[index].used = true;
+  data_buffer_[index] = packet;
+
+  FindCompleteFrames(seq_num);
+  return true;
+}
+
+void PacketBuffer::ClearUpTo(uint16_t seq_num) {
+  rtc::CritScope lock(&crit_);
+  clear_up_to_ = seq_num;

[stefan-webrtc, 2016/03/30 11:59:32]

Why doesn't this simply clear the packet_buffer_ instead of storing it?

[philipel, 2016/03/30 12:40:11]

Since both the |data_buffer_| and the |sequence_buffer_| is a vector (and not a
map) it is not possible to remove (mark them as not used) the correct elements
without having to loop over all the elements in both vectors.

Instead we save how far packets has been cleared and then later on when a packet
is inserted we check if the current packet in the buffer has indeed been removed
and if so we overwrite it.

[stefan-webrtc, 2016/03/30 12:56:20]

Change as discussed offline

+}
+
+bool PacketBuffer::ExpandBufferSize() {
+  if (size_ == max_size_) {
+    return false;
+  }
+
+  size_t new_size = std::min(max_size_, 2 * size_);
+  std::vector<VCMPacket> new_data_buffer(new_size);
+  std::vector<ContinuityInfo> new_sequence_buffer(new_size);
+  for (size_t i = 0; i < size_; ++i) {
+    if (sequence_buffer_[i].used) {
+      int index = sequence_buffer_[i].seq_num % new_size;
+      new_sequence_buffer[index] = sequence_buffer_[i];
+      new_data_buffer[index] = data_buffer_[i];
+    }
+  }
+  size_ = new_size;
+  sequence_buffer_ = std::move(new_sequence_buffer);
+  data_buffer_ = std::move(new_data_buffer);
+  return true;
+}
+
+bool PacketBuffer::IsContinuous(uint16_t seq_num) const {
+  int index = seq_num % size_;
+  int prev_index = index > 0 ? index - 1 : size_ - 1;
+  if (!sequence_buffer_[index].used)

[stefan-webrtc, 2016/03/30 11:59:31]

We should be able to DCHECK on this, right? We should never be calling
IsContinuous on a seq num we haven't added.

[philipel, 2016/03/30 12:40:11]

We are guaranteed to check sequence numbers that has not yet been inserted into
the packet buffer. This is done in the loop in FindCompleteFrames().

[stefan-webrtc, 2016/03/30 12:56:20]

Ah, yes, my mistake.

+    return false;
+  if (sequence_buffer_[index].frame_begin)
+    return true;
+  if (!sequence_buffer_[prev_index].used)
+    return false;
+  if (sequence_buffer_[prev_index].continuous)
+    return true;
+
+  return false;

[stefan-webrtc, 2016/03/30 11:59:31]

Can we rewrite this method so that we have a single "return true", I think it
would be easier to read. For instance by changing line 110 and line 106 to check
the opposite.

[philipel, 2016/03/30 12:40:11]

Hmm... Negating the condition on line 106 and 110 does not mean we should return
the opposite, it means we should perform more checks...

[stefan-webrtc, 2016/03/30 12:56:20]

That's right, maybe it gets more complicated.

+}
+
+void PacketBuffer::FindCompleteFrames(uint16_t seq_num) {
+  int index = seq_num % size_;
+  while (IsContinuous(seq_num)) {
+    sequence_buffer_[index].continuous = true;
+
+    // If the frame is complete, find the first packet of the frame and

[stefan-webrtc, 2016/03/30 11:59:31]

Should this say "If the frame has the last packet, determine if it is complete
and if so create a FrameObject."?

[philipel, 2016/03/30 12:40:11]

No, if we have reached a packet that is marked with frame_end then it means that
we have all packets required for this frame, so we only have to find where it
begins and then create a frame object using those sequence numbers.

[stefan-webrtc, 2016/03/30 12:56:20]

Maybe change the comment to what you just wrote instead. :)

+    // create a FrameObject.
+    if (sequence_buffer_[index].frame_end) {
+      int rindex = index;
+      uint16_t start_seq_num = seq_num;
+      while (!sequence_buffer_[rindex].frame_begin) {
+        rindex = rindex > 0 ? rindex - 1 : size_ - 1;
+        start_seq_num--;
+      }

[stefan-webrtc, 2016/03/30 11:59:31]

Can we DCHECK on that we actually found the first packet of the same frame?

[philipel, 2016/03/30 12:40:11]

I guess, but then we have to save the capture timestamp of the frame as well,
and only in order to perform that check at this point.

[stefan-webrtc, 2016/03/30 12:56:20]

Can we add a check on picture id instead then?

+
+      std::unique_ptr<FrameObject> frame(
+          new RtpFrameObject(this, 1, start_seq_num, seq_num));
+      frame_callback_->OnCompleteFrame(std::move(frame));
+    }
+
+    index = (index + 1) % size_;
+    ++seq_num;
+  }
+}
+
+void PacketBuffer::ReturnFrame(RtpFrameObject* frame) {
+  rtc::CritScope lock(&crit_);
+  int index = frame->first_packet() % size_;
+  int end = (frame->last_packet() + 1) % size_;
+  uint16_t seq_num = frame->first_packet();
+  while (index != end) {
+    if (sequence_buffer_[index].seq_num == seq_num) {
+      sequence_buffer_[index].used = false;
+      sequence_buffer_[index].continuous = false;
+    }
+    index = (index + 1) % size_;
+    ++seq_num;
+  }
+}
+
+bool PacketBuffer::GetBitstream(const RtpFrameObject& frame,
+                                uint8_t* destination) {

[stefan-webrtc, 2016/03/30 11:59:31]

Is it up to the caller to ensure this buffer is large enough? How would that be
done without a way of asking the PacketBuffer how large the frame is?

[philipel, 2016/03/30 12:40:11]

It's up to the caller, I guess we could (shoud?) add a GetSize() method to the
FrameObject class.

[stefan-webrtc, 2016/03/30 12:56:20]

I think that'd be good, otherwise I suspect it'd be difficult to use.

+  rtc::CritScope lock(&crit_);
+
+  int index = frame.first_packet() % size_;
+  int end = (frame.last_packet() + 1) % size_;
+  uint16_t seq_num = frame.first_packet();
+  while (index != end) {
+    if (!sequence_buffer_[index].used ||
+        sequence_buffer_[index].seq_num != seq_num)

[stefan-webrtc, 2016/03/30 11:59:31]

{} since this if statement is > 2 lines.

[philipel, 2016/03/30 12:40:11]

Done.

+      return false;
+
+    const uint8_t* source = data_buffer_[index].dataPtr;
+    size_t length = data_buffer_[index].sizeBytes;
+    memcpy(destination, source, length);
+    destination += length;
+    index = (index + 1) % size_;
+    ++seq_num;
+  }
+  return true;
+}
+
+void PacketBuffer::Flush() {
+  rtc::CritScope lock(&crit_);
+  for (size_t i = 0; i < size_; ++i) {
+    sequence_buffer_[i].used = false;
+    sequence_buffer_[i].continuous = false;
+  }
+}
+
+}  // namespace video_coding
+}  // namespace webrtc