Convert Vp8 Rtp headers to frame references.

webrtc/modules/video_coding/packet_buffer.cc

 /*
  *  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/checks.h"
 #include "webrtc/modules/video_coding/frame_object.h"
-#include "webrtc/modules/video_coding/sequence_number_util.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),
+      first_seq_num_(0),
       last_seq_num_(0),
-      first_seq_num_(0),
-      initialized_(false),
+      first_packet_received_(false),
       data_buffer_(start_buffer_size),
       sequence_buffer_(start_buffer_size),
-      frame_callback_(frame_callback) {
+      frame_callback_(frame_callback),
+      last_picture_id_(-1),
+      last_unwrap_(-1) {
   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_;
+  size_t index = seq_num % size_;
 
-  if (!initialized_) {
+  if (!first_packet_received_) {
     first_seq_num_ = seq_num - 1;
     last_seq_num_ = seq_num;
-    initialized_ = true;
+    first_packet_received_ = true;
   }
 
   if (sequence_buffer_[index].used) {
     // Duplicate packet, do nothing.
     if (data_buffer_[index].seqNum == packet.seqNum)
       return true;
 
     // The packet buffer is full, try to expand the buffer.
     while (ExpandBufferSize() && sequence_buffer_[seq_num % size_].used) {
     }
     index = seq_num % size_;
 
     // Packet buffer is still full.
     if (sequence_buffer_[index].used)
       return false;
   }
 
   if (AheadOf(seq_num, last_seq_num_))
     last_seq_num_ = seq_num;
 
   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].frame_created = false;
   sequence_buffer_[index].used = true;
   data_buffer_[index] = packet;
 
-  FindCompleteFrames(seq_num);
+  FindFrames(seq_num);
   return true;
 }
 
 void PacketBuffer::ClearTo(uint16_t seq_num) {
   rtc::CritScope lock(&crit_);
-  int index = first_seq_num_ % size_;
+  size_t index = first_seq_num_ % size_;
   while (AheadOf<uint16_t>(seq_num, first_seq_num_ + 1)) {
     index = (index + 1) % size_;
     first_seq_num_ = Add<1 << 16>(first_seq_num_, 1);
     sequence_buffer_[index].used = false;
   }
 }
 
 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;
+      size_t 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_;
+  size_t index = seq_num % size_;
   int prev_index = index > 0 ? index - 1 : size_ - 1;
+
   if (!sequence_buffer_[index].used)
     return false;
+  if (sequence_buffer_[index].frame_created)
+    return false;
   if (sequence_buffer_[index].frame_begin)
     return true;
   if (!sequence_buffer_[prev_index].used)
     return false;
+  if (sequence_buffer_[prev_index].seq_num !=
+      static_cast<uint16_t>(seq_num - 1))
+    return false;
   if (sequence_buffer_[prev_index].continuous)
     return true;
 
   return false;
 }
 
-void PacketBuffer::FindCompleteFrames(uint16_t seq_num) {
-  int index = seq_num % size_;
+void PacketBuffer::FindFrames(uint16_t seq_num) {
+  size_t 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
-    // create a FrameObject.
+    // If all packets of the frame is continuous, find the first packet of the
+    // frame and create an RtpFrameObject.
     if (sequence_buffer_[index].frame_end) {
-      int rindex = index;
+      int start_index = index;
       uint16_t start_seq_num = seq_num;
-      while (!sequence_buffer_[rindex].frame_begin) {
-        rindex = rindex > 0 ? rindex - 1 : size_ - 1;
+
+      while (!sequence_buffer_[start_index].frame_begin) {
+        sequence_buffer_[start_index].frame_created = true;
+        start_index = start_index > 0 ? start_index - 1 : size_ - 1;
         start_seq_num--;
       }
+      sequence_buffer_[start_index].frame_created = true;
 
-      std::unique_ptr<FrameObject> frame(
-          new RtpFrameObject(this, 1, start_seq_num, seq_num));
-      frame_callback_->OnCompleteFrame(std::move(frame));
+      std::unique_ptr<RtpFrameObject> frame(
+          new RtpFrameObject(this, start_seq_num, seq_num));
+      ManageFrame(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_;
+  size_t index = frame->first_packet() % size_;
+  size_t end = (frame->last_packet() + 1) % size_;
   uint16_t seq_num = frame->first_packet();
   while (index != end) {
-    if (sequence_buffer_[index].seq_num == seq_num) {
+    if (sequence_buffer_[index].seq_num == seq_num)
       sequence_buffer_[index].used = false;
-      sequence_buffer_[index].continuous = false;
-    }
+
     index = (index + 1) % size_;
     ++seq_num;
   }
 
   index = first_seq_num_ % size_;
   while (AheadOf<uint16_t>(last_seq_num_, first_seq_num_) &&
          !sequence_buffer_[index].used) {
     ++first_seq_num_;
     index = (index + 1) % size_;
   }
 }
 
 bool PacketBuffer::GetBitstream(const RtpFrameObject& frame,
                                 uint8_t* destination) {
   rtc::CritScope lock(&crit_);
 
-  int index = frame.first_packet() % size_;
-  int end = (frame.last_packet() + 1) % size_;
+  size_t index = frame.first_packet() % size_;
+  size_t 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) {
       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::ManageFrame(std::unique_ptr<RtpFrameObject> frame) {
+  size_t start_index = frame->first_packet() % size_;
+  VideoCodecType codec_type = data_buffer_[start_index].codec;
+
+  if (codec_type == kVideoCodecVP8) {

[stefan-webrtc, 2016/04/07 12:37:04]

switch()

[philipel, 2016/04/07 13:38:42]

If I implement a switch case I am forced by the compiler to implement a case for
all possible values, which are:

kRtpVideoNone,
kRtpVideoGeneric,
kRtpVideoVp8,
kRtpVideoVp9,
kRtpVideoH264,
default

[stefan-webrtc, 2016/04/19 10:38:19]

I think that could be a good thing. If a new type is added we won't forget about
this.

[philipel, 2016/04/19 11:52:07]

Switched to switch case.

+    ManageFrameVp8(std::move(frame));
+  } else if (codec_type == kVideoCodecVP9) {
+    // TODO(philipel): ManageFrameVp9(std::move(frame));
+  } else {
+    ManageFrameGeneric(std::move(frame));
+  }
+}
+
+void PacketBuffer::RetryStashedFrames() {
+  size_t num_stashed_frames = stashed_frames_.size();
+
+  // Clean up stashed frames if there are to many.
+  while (stashed_frames_.size() > 10)
+    stashed_frames_.pop();
+
+  // Since frames are stashed if there is not enough data to determine their
+  // frame references we should at most check |stashed_frames_.size()| in
+  // order to not pop and push frames in and endless loop.
+  for (size_t i = 0; i < num_stashed_frames && !stashed_frames_.empty(); ++i) {
+    std::unique_ptr<RtpFrameObject> frame = std::move(stashed_frames_.front());
+    stashed_frames_.pop();
+    ManageFrame(std::move(frame));
+  }
+}
+
+void PacketBuffer::ManageFrameGeneric(
+    std::unique_ptr<RtpFrameObject> frame) {
+  size_t index = frame->first_packet() % size_;
+  const VCMPacket& packet = data_buffer_[index];
+
+  if (packet.frameType == kVideoFrameKey)
+    last_seq_num_for_kf_[frame->last_packet()] = frame->last_packet();
+
+  // Clean up info for old keyframes but make sure to keep info
+  // for the last keyframe.
+  auto clean_to = last_seq_num_for_kf_.lower_bound(frame->last_packet() - 100);
+  if (clean_to != last_seq_num_for_kf_.end() ||
+      clean_to != (--last_seq_num_for_kf_.end())) {
+    last_seq_num_for_kf_.erase(last_seq_num_for_kf_.begin(), clean_to);
+  }
+
+  // Find the last sequence number of the last frame for the keyframe
+  // that this frame indirectly references.
+  auto seq_num_it = last_seq_num_for_kf_.upper_bound(frame->last_packet());
+  seq_num_it--;
+
+  // Make sure the packet sequence numbers are continuous, otherwise stash
+  // this frame.
+  if (packet.frameType == kVideoFrameDelta) {
+    if (seq_num_it->second !=
+        static_cast<uint16_t>(frame->first_packet() - 1)) {

[stefan-webrtc, 2016/04/07 12:37:04]

I'm reading this as if frame must be next frame after the key frame, otherwise
we stash it. Can't there be delta frames in between?

[philipel, 2016/04/07 13:38:42]

There can be delta frames in between. On line 271 the sequence number (picture
id) in the map is updated.

[stefan-webrtc, 2016/04/19 12:24:29]

I was confused about the last_seq_num_for_kf_. I interpreted it as if it
contained the last sequence numbers for the packets belonging to a key frame,
but it contains the last sequence numbers of each group of independently
decodable frames. Maybe we can rename it as such? GOP (group of pictures) is
often used in video coding when talking about those things.

[philipel, 2016/04/19 13:12:01]

Renamed it to |last_seq_num_gop_|.

+      stashed_frames_.emplace(std::move(frame));
+      return;
+    }
+  }
+
+  RTC_DCHECK(AheadOrAt(frame->last_packet(), seq_num_it->first));
+
+  frame->picture_id = frame->last_packet();

[stefan-webrtc, 2016/04/07 12:37:04]

I find this a bit strange. Why do we assign a packet to a picture_id? We should
clarify the code here in some way. 

[philipel, 2016/04/07 13:38:42]

Added comment which explains why.

[stefan-webrtc, 2016/04/19 10:38:19]

But maybe last_packet() should return last_picture_id() or something? To make it
clear it's actually a picture_id

[philipel, 2016/04/19 11:52:07]

The function last_packet simply returns the sequence number of the last packet
of this frame. In the generic case we use the sequence number of the last packet
as the picture_id.

[stefan-webrtc, 2016/04/19 12:24:29]

Ah, call it last_packet_sequence_number() or last_sequence_number()? My point is
that it doesn't return a Packet.

[philipel, 2016/04/19 13:12:01]

True, renamed |last_packet()| to |last_seq_num()| and |first_packet| to
|first_seq_num()|.

+  frame->num_references = packet.frameType == kVideoFrameDelta;
+  frame->references[0] = seq_num_it->second;

[stefan-webrtc, 2016/04/07 12:37:04]

Always referring to the key frame? I guess this is related to my question on
line 260.

[philipel, 2016/04/07 13:38:42]

Since we update the picture id stored in the map this will always refer back to
the previous frame for some keyframe.

I updated line 271 to: seq_num_it->second = frame->picture_id;
which hopefully makes it clearer.

+  seq_num_it->second = frame->last_packet();
+
+  last_picture_id_ = frame->picture_id;
+  frame_callback_->OnCompleteFrame(std::move(frame));
+  RetryStashedFrames();
+}
+
+void PacketBuffer::ManageFrameVp8(std::unique_ptr<RtpFrameObject> frame) {
+  size_t index = frame->first_packet() % size_;
+  const VCMPacket& packet = data_buffer_[index];
+  const RTPVideoHeaderVP8& codec_header =
+      packet.codecSpecificHeader.codecHeader.VP8;
+
+  if (codec_header.pictureId == kNoPictureId ||
+      codec_header.temporalIdx == kNoTemporalIdx ||
+      codec_header.tl0PicIdx == kNoTl0PicIdx) {
+    ManageFrameGeneric(std::move(frame));
+    return;
+  }
+
+  frame->picture_id = codec_header.pictureId % kPicIdLength;
+
+  if (last_unwrap_ == -1)
+    last_unwrap_ = codec_header.pictureId;
+
+  if (last_picture_id_ == -1)
+    last_picture_id_ = frame->picture_id;
+
+  // Find if there has been a gap in fully received frames and save the picture
+  // id of those frames in |not_yet_received_frames_|.
+  if (AheadOf<uint8_t, kPicIdLength>(frame->picture_id, last_picture_id_)) {
+    last_picture_id_ = Add<kPicIdLength>(last_picture_id_, 1);
+    while (last_picture_id_ != frame->picture_id) {
+      not_yet_received_frames_.insert(last_picture_id_);
+      last_picture_id_ = Add<kPicIdLength>(last_picture_id_, 1);
+    }
+  }
+
+  // Clean up info for base layers that are to old.

[stefan-webrtc, 2016/04/07 12:37:04]

too old

[philipel, 2016/04/07 13:38:42]

Done.

+  uint8_t old_tl0_pic_idx = codec_header.tl0PicIdx - 10;

[stefan-webrtc, 2016/04/07 12:37:04]

Why is 10 frames back too old? Wouldn't it be better to define too old as being
X frames older than the current _if_ a key frame exists which is newer?
Otherwise we might as well wait.

[philipel, 2016/04/07 13:38:42]

The value 10 is just an arbitrary number that is "big enough".

Since a new entry is added to |layer_info_| for every frame on tl0 I can't see
that making the definition of "too old" depend on whether we have newer
keyframes or not to make any difference.

+  auto clean_layer_info_to = layer_info_.lower_bound(old_tl0_pic_idx);
+  layer_info_.erase(layer_info_.begin(), clean_layer_info_to);
+
+  // Clean up info about not yet received frames that are to old.
+  uint16_t old_picture_id = Subtract<kPicIdLength>(frame->picture_id, 20);

[stefan-webrtc, 2016/04/19 10:38:19]

Name this constant, and the same with 10 above.

[philipel, 2016/04/19 11:52:07]

Done.

+  auto clean_frames_to = not_yet_received_frames_.lower_bound(old_picture_id);
+  not_yet_received_frames_.erase(not_yet_received_frames_.begin(),
+                                 clean_frames_to);

[stefan-webrtc, 2016/04/07 12:37:04]

I think we should break out the clean up functionality to a separeate function

[philipel, 2016/04/07 13:38:42]

Hmm... I think the interface of such a function would become kind of messy...

[stefan-webrtc, 2016/04/19 10:38:19]

Maybe. I was thinking something simple, like CleanupOld(picture_id, 
tl0_pic_idx);

not super important

+
+  if (packet.frameType == kVideoFrameKey) {
+    frame->num_references = 0;
+    layer_info_[codec_header.tl0PicIdx].fill(-1);
+    CompletedFrameVp8(std::move(frame));
+    return;
+  }
+
+  auto layer_info_it = layer_info_.find(codec_header.temporalIdx == 0
+                                            ? codec_header.tl0PicIdx - 1

[stefan-webrtc, 2016/04/07 12:37:04]

Should this do Add<...>(codec_header.tl0PicIdx, -1)?

[philipel, 2016/04/07 13:38:42]

Not needed in this case since tl0PicIdx wraps at 255.

[stefan-webrtc, 2016/04/19 10:38:19]

Acknowledged.

+                                            : codec_header.tl0PicIdx);
+
+  // If we don't have the base layer frame yet, stash this frame.
+  if (layer_info_it == layer_info_.end()) {
+    stashed_frames_.emplace(std::move(frame));
+    return;
+  }
+
+  // A non keyframe base layer frame has been received, copy the layer info
+  // from the previous base layer frame and set a reference to the previous
+  // base layer frame.
+  if (codec_header.temporalIdx == 0) {
+    layer_info_it =
+        layer_info_
+            .insert(make_pair(codec_header.tl0PicIdx, layer_info_it->second))
+            .first;
+    frame->num_references = 1;
+    frame->references[0] = layer_info_it->second[0];

[stefan-webrtc, 2016/04/07 12:37:04]

Is it guaranteed that there isn't a gap between "frame" and
layer_info_it->second[0]? I.e., do we know at this point that we have received
all tl0 frames prior to "frame"?

[philipel, 2016/04/07 13:38:42]

On line 327 we check if this is a frame on temporal layer 0, and if so look for
the layer info for tl0PicIdx - 1. If we can't find it then we stash this frame
(line 332).

So at this point we are sure to have the base layer frame needed for this frame.

[stefan-webrtc, 2016/04/19 10:38:19]

Acknowledged.

+    CompletedFrameVp8(std::move(frame));
+    return;
+  }
+
+  // Layer sync frame, this frame only references its base layer frame.
+  if (codec_header.layerSync) {
+    frame->num_references = 1;
+    frame->references[0] = layer_info_it->second[0];
+
+    CompletedFrameVp8(std::move(frame));
+    return;
+  }
+
+  // Find all references for this frame.
+  frame->num_references = 0;
+  for (uint8_t layer = 0; layer <= codec_header.temporalIdx; ++layer) {
+    RTC_DCHECK_NE(-1, layer_info_it->second[layer]);
+    ++frame->num_references;
+    frame->references[layer] = layer_info_it->second[layer];

[stefan-webrtc, 2016/04/07 12:37:04]

Same question here as on line 346, but I see below that you ensure we wait for
any frames in between. Should that be done at line 347 too? And should we really
update frame->references[layer] here if we don't know if it's the right
reference we're setting it to? (I assume we're waiting below because it might
not be the correct reference)

[philipel, 2016/04/07 13:38:42]

Updating the references here doesn't really matter since they will all be
correctly assigned when we have all information needed and this frame is
retried.

[stefan-webrtc, 2016/04/19 10:38:19]

So should we only update the references when we actually know that they are
correct, e.g., on line 377?

[philipel, 2016/04/19 11:52:07]

Changed so that the check occurs before the assignment.

+
+    // If we have not yet received a frame between this frame and the referenced
+    // frame then we have to wait for that frame to be completed first.
+    auto not_received_frame_it =
+                 not_yet_received_frames_.upper_bound(frame->references[layer]);
+    if (not_received_frame_it != not_yet_received_frames_.end() &&
+        AheadOf<uint8_t, kPicIdLength>(frame->picture_id,
+                                       *not_received_frame_it)) {
+          stashed_frames_.emplace(std::move(frame));
+          return;
+    }
+  }
+
+  CompletedFrameVp8(std::move(frame));
+}
+
+void PacketBuffer::CompletedFrameVp8(std::unique_ptr<RtpFrameObject> frame) {
+  size_t index = frame->first_packet() % size_;
+  const VCMPacket& packet = data_buffer_[index];
+  const RTPVideoHeaderVP8& codec_header =
+      packet.codecSpecificHeader.codecHeader.VP8;
+
+  uint8_t tl0_pic_idx = codec_header.tl0PicIdx;
+  uint8_t temporal_index = codec_header.temporalIdx;
+  auto layer_info_it = layer_info_.find(tl0_pic_idx);
+
+  // Update this layer info and newer.
+  while (layer_info_it != layer_info_.end()) {
+    if (layer_info_it->second[temporal_index] != -1 &&
+        AheadOf<uint16_t, kPicIdLength>(layer_info_it->second[temporal_index],
+                                        frame->picture_id)) {
+      // The frame was not newer, then no subsequent layer info have to be
+      // update.
+      break;
+    }
+
+    layer_info_it->second[codec_header.temporalIdx] = frame->picture_id;
+    ++tl0_pic_idx;
+    layer_info_it = layer_info_.find(tl0_pic_idx);
+  }
+  not_yet_received_frames_.erase(frame->picture_id);
+
+  for (size_t r = 0; r < frame->num_references; ++r)
+    frame->references[r] = UnwrapPictureId(frame->references[r]);
+  frame->picture_id = UnwrapPictureId(frame->picture_id);
+
+  frame_callback_->OnCompleteFrame(std::move(frame));
+  RetryStashedFrames();
+}
+
+uint16_t PacketBuffer::UnwrapPictureId(uint16_t picture_id) {
+  if (last_unwrap_ == -1)
+    last_unwrap_ = picture_id;
+
+  uint16_t unwrap_truncated = last_unwrap_ % kPicIdLength;
+  uint16_t diff = MinDiff<uint8_t, kPicIdLength>(unwrap_truncated, picture_id);
+
+  if (AheadOf<uint8_t, kPicIdLength>(picture_id, unwrap_truncated))
+    last_unwrap_ = Add<1 << 16>(last_unwrap_, diff);
+  else
+    last_unwrap_ = Subtract<1 << 16>(last_unwrap_, diff);
+
+  return last_unwrap_;
+}
+
 void PacketBuffer::Flush() {
   rtc::CritScope lock(&crit_);
-  for (size_t i = 0; i < size_; ++i) {
+  for (size_t i = 0; i < size_; ++i)
     sequence_buffer_[i].used = false;
-    sequence_buffer_[i].continuous = false;
-  }
+
+  last_seq_num_for_kf_.clear();
+  while (!stashed_frames_.empty())
+    stashed_frames_.pop();
+  not_yet_received_frames_.clear();
+
+  first_packet_received_ = false;
 }
 
 }  // namespace video_coding
 }  // namespace webrtc