webrtc/modules/rtp_rtcp/source/rtp_packet_history.cc - platform/external/webrtc - Git at Google

 /*
  *  Copyright (c) 2012 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/rtp_rtcp/source/rtp_packet_history.h"

 #include <assert.h>
 #include <stdlib.h>
 #include <string.h>   // memset
 #include <limits>
 #include <set>

 #include "webrtc/modules/rtp_rtcp/source/rtp_utility.h"
 #include "webrtc/system_wrappers/interface/critical_section_wrapper.h"
 #include "webrtc/system_wrappers/interface/logging.h"

 namespace webrtc {

 static const int kMinPacketRequestBytes = 50;

 RTPPacketHistory::RTPPacketHistory(Clock* clock)
   : clock_(clock),
     critsect_(CriticalSectionWrapper::CreateCriticalSection()),
     store_(false),
     prev_index_(0),
     max_packet_length_(0) {
 }

 RTPPacketHistory::~RTPPacketHistory() {
 }

 void RTPPacketHistory::SetStorePacketsStatus(bool enable,
                                              uint16_t number_to_store) {
   CriticalSectionScoped cs(critsect_.get());
   if (enable) {
     if (store_) {
       LOG(LS_WARNING) << "Purging packet history in order to re-set status.";
       Free();
     }
     assert(!store_);
     Allocate(number_to_store);
   } else {
     Free();
   }
 }

 void RTPPacketHistory::Allocate(size_t number_to_store) {
   assert(number_to_store > 0);
   assert(number_to_store <= kMaxHistoryCapacity);
   store_ = true;
   stored_packets_.resize(number_to_store);
   stored_seq_nums_.resize(number_to_store);
   stored_lengths_.resize(number_to_store);
   stored_times_.resize(number_to_store);
   stored_send_times_.resize(number_to_store);
   stored_types_.resize(number_to_store);
 }

 void RTPPacketHistory::Free() {
   if (!store_) {
     return;
   }

   std::vector<std::vector<uint8_t> >::iterator it;
   for (it = stored_packets_.begin(); it != stored_packets_.end(); ++it) {
     it->clear();
   }

   stored_packets_.clear();
   stored_seq_nums_.clear();
   stored_lengths_.clear();
   stored_times_.clear();
   stored_send_times_.clear();
   stored_types_.clear();

   store_ = false;
   prev_index_ = 0;
   max_packet_length_ = 0;
 }

 bool RTPPacketHistory::StorePackets() const {
   CriticalSectionScoped cs(critsect_.get());
   return store_;
 }

 void RTPPacketHistory::VerifyAndAllocatePacketLength(size_t packet_length,
                                                      uint32_t start_index) {
   assert(packet_length > 0);
   if (!store_) {
     return;
   }

   // If start_index > 0 this is a resize and we must check any new (empty)
   // packets created during the resize.
   if (start_index == 0 && packet_length <= max_packet_length_) {
     return;
   }

   max_packet_length_ = std::max(packet_length, max_packet_length_);

   std::vector<std::vector<uint8_t> >::iterator it;
   for (it = stored_packets_.begin() + start_index; it != stored_packets_.end();
        ++it) {
     it->resize(max_packet_length_);
   }
 }

 int32_t RTPPacketHistory::PutRTPPacket(const uint8_t* packet,
                                        size_t packet_length,
                                        size_t max_packet_length,
                                        int64_t capture_time_ms,
                                        StorageType type) {
   if (type == kDontStore) {
     return 0;
   }

   CriticalSectionScoped cs(critsect_.get());
   if (!store_) {
     return 0;
   }

   assert(packet);
   assert(packet_length > 3);

   VerifyAndAllocatePacketLength(max_packet_length, 0);

   if (packet_length > max_packet_length_) {
     LOG(LS_WARNING) << "Failed to store RTP packet with length: "
                     << packet_length;
     return -1;
   }

   const uint16_t seq_num = (packet[2] << 8) + packet[3];

   // If index we're about to overwrite contains a packet that has not
   // yet been sent (probably pending in paced sender), we need to expand
   // the buffer.
   if (stored_lengths_[prev_index_] > 0 &&
       stored_send_times_[prev_index_] == 0) {
     size_t current_size = static_cast<uint16_t>(stored_packets_.size());
     if (current_size < kMaxHistoryCapacity) {
       size_t expanded_size = std::max(current_size * 3 / 2, current_size + 1);
       expanded_size = std::min(expanded_size, kMaxHistoryCapacity);
       Allocate(expanded_size);
       VerifyAndAllocatePacketLength(max_packet_length, current_size);
       // Causes discontinuity, but that's OK-ish. FindSeqNum() will still work,
       // but may be slower - at least until buffer has wrapped around once.
       prev_index_ = current_size;
     }
   }

   // Store packet
   std::vector<std::vector<uint8_t> >::iterator it =
       stored_packets_.begin() + prev_index_;
   // TODO(sprang): Overhaul this class and get rid of this copy step.
   //               (Finally introduce the RtpPacket class?)
   std::copy(packet, packet + packet_length, it->begin());

   stored_seq_nums_[prev_index_] = seq_num;
   stored_lengths_[prev_index_] = packet_length;
   stored_times_[prev_index_] = (capture_time_ms > 0) ? capture_time_ms :
       clock_->TimeInMilliseconds();
   stored_send_times_[prev_index_] = 0;  // Packet not sent.
   stored_types_[prev_index_] = type;

   ++prev_index_;
   if (prev_index_ >= stored_seq_nums_.size()) {
     prev_index_ = 0;
   }
   return 0;
 }

 bool RTPPacketHistory::HasRTPPacket(uint16_t sequence_number) const {
   CriticalSectionScoped cs(critsect_.get());
   if (!store_) {
     return false;
   }

   int32_t index = 0;
   bool found = FindSeqNum(sequence_number, &index);
   if (!found) {
     return false;
   }

   size_t length = stored_lengths_.at(index);
   if (length == 0 || length > max_packet_length_) {
     // Invalid length.
     return false;
   }
   return true;
 }

 bool RTPPacketHistory::SetSent(uint16_t sequence_number) {
   CriticalSectionScoped cs(critsect_.get());
   if (!store_) {
     return false;
   }

   int32_t index = 0;
   bool found = FindSeqNum(sequence_number, &index);
   if (!found) {
     return false;
   }

   // Send time already set.
   if (stored_send_times_[index] != 0) {
     return false;
   }

   stored_send_times_[index] = clock_->TimeInMilliseconds();
   return true;
 }

 bool RTPPacketHistory::GetPacketAndSetSendTime(uint16_t sequence_number,
                                                int64_t min_elapsed_time_ms,
                                                bool retransmit,
                                                uint8_t* packet,
                                                size_t* packet_length,
                                                int64_t* stored_time_ms) {
   CriticalSectionScoped cs(critsect_.get());
   assert(*packet_length >= max_packet_length_);
   if (!store_) {
     return false;
   }

   int32_t index = 0;
   bool found = FindSeqNum(sequence_number, &index);
   if (!found) {
     LOG(LS_WARNING) << "No match for getting seqNum " << sequence_number;
     return false;
   }

   size_t length = stored_lengths_.at(index);
   assert(length <= max_packet_length_);
   if (length == 0) {
     LOG(LS_WARNING) << "No match for getting seqNum " << sequence_number
                     << ", len " << length;
     return false;
   }

   // Verify elapsed time since last retrieve.
   int64_t now = clock_->TimeInMilliseconds();
   if (min_elapsed_time_ms > 0 &&
       ((now - stored_send_times_.at(index)) < min_elapsed_time_ms)) {
     return false;
   }

   if (retransmit && stored_types_.at(index) == kDontRetransmit) {
     // No bytes copied since this packet shouldn't be retransmitted or is
     // of zero size.
     return false;
   }
   stored_send_times_[index] = clock_->TimeInMilliseconds();
   GetPacket(index, packet, packet_length, stored_time_ms);
   return true;
 }

 void RTPPacketHistory::GetPacket(int index,
                                  uint8_t* packet,
                                  size_t* packet_length,
                                  int64_t* stored_time_ms) const {
   // Get packet.
   size_t length = stored_lengths_.at(index);
   std::vector<std::vector<uint8_t> >::const_iterator it_found_packet =
       stored_packets_.begin() + index;
   std::copy(it_found_packet->begin(), it_found_packet->begin() + length,
             packet);
   *packet_length = length;
   *stored_time_ms = stored_times_.at(index);
 }

 bool RTPPacketHistory::GetBestFittingPacket(uint8_t* packet,
                                             size_t* packet_length,
                                             int64_t* stored_time_ms) {
   CriticalSectionScoped cs(critsect_.get());
   if (!store_)
     return false;
   int index = FindBestFittingPacket(*packet_length);
   if (index < 0)
     return false;
   GetPacket(index, packet, packet_length, stored_time_ms);
   return true;
 }

 // private, lock should already be taken
 bool RTPPacketHistory::FindSeqNum(uint16_t sequence_number,
                                   int32_t* index) const {
   uint16_t temp_sequence_number = 0;
   if (prev_index_ > 0) {
     *index = prev_index_ - 1;
     temp_sequence_number = stored_seq_nums_[*index];
   } else {
     *index = stored_seq_nums_.size() - 1;
     temp_sequence_number = stored_seq_nums_[*index];  // wrap
   }

   int32_t idx = (prev_index_ - 1) - (temp_sequence_number - sequence_number);
   if (idx >= 0 && idx < static_cast<int>(stored_seq_nums_.size())) {
     *index = idx;
     temp_sequence_number = stored_seq_nums_[*index];
   }

   if (temp_sequence_number != sequence_number) {
     // We did not found a match, search all.
     for (uint16_t m = 0; m < stored_seq_nums_.size(); m++) {
       if (stored_seq_nums_[m] == sequence_number) {
         *index = m;
         temp_sequence_number = stored_seq_nums_[*index];
         break;
       }
     }
   }
   if (temp_sequence_number == sequence_number) {
     // We found a match.
     return true;
   }
   return false;
 }

 int RTPPacketHistory::FindBestFittingPacket(size_t size) const {
   if (size < kMinPacketRequestBytes || stored_lengths_.empty())
     return -1;
   size_t min_diff = std::numeric_limits<size_t>::max();
   int best_index = -1;  // Returned unchanged if we don't find anything.
   for (size_t i = 0; i < stored_lengths_.size(); ++i) {
     if (stored_lengths_[i] == 0)
       continue;
     size_t diff = (stored_lengths_[i] > size) ?
         (stored_lengths_[i] - size) : (size - stored_lengths_[i]);
     if (diff < min_diff) {
       min_diff = diff;
       best_index = static_cast<int>(i);
     }
   }
   return best_index;
 }
 }  // namespace webrtc
	/*
	* Copyright (c) 2012 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/rtp_rtcp/source/rtp_packet_history.h"

	#include <assert.h>
	#include <stdlib.h>
	#include <string.h> // memset
	#include <limits>
	#include <set>

	#include "webrtc/modules/rtp_rtcp/source/rtp_utility.h"
	#include "webrtc/system_wrappers/interface/critical_section_wrapper.h"
	#include "webrtc/system_wrappers/interface/logging.h"

	namespace webrtc {

	static const int kMinPacketRequestBytes = 50;

	RTPPacketHistory::RTPPacketHistory(Clock* clock)
	: clock_(clock),
	critsect_(CriticalSectionWrapper::CreateCriticalSection()),
	store_(false),
	prev_index_(0),
	max_packet_length_(0) {
	}

	RTPPacketHistory::~RTPPacketHistory() {
	}

	void RTPPacketHistory::SetStorePacketsStatus(bool enable,
	uint16_t number_to_store) {
	CriticalSectionScoped cs(critsect_.get());
	if (enable) {
	if (store_) {
	LOG(LS_WARNING) << "Purging packet history in order to re-set status.";
	Free();
	}
	assert(!store_);
	Allocate(number_to_store);
	} else {
	Free();
	}
	}

	void RTPPacketHistory::Allocate(size_t number_to_store) {
	assert(number_to_store > 0);
	assert(number_to_store <= kMaxHistoryCapacity);
	store_ = true;
	stored_packets_.resize(number_to_store);
	stored_seq_nums_.resize(number_to_store);
	stored_lengths_.resize(number_to_store);
	stored_times_.resize(number_to_store);
	stored_send_times_.resize(number_to_store);
	stored_types_.resize(number_to_store);
	}

	void RTPPacketHistory::Free() {
	if (!store_) {
	return;
	}

	std::vector<std::vector<uint8_t> >::iterator it;
	for (it = stored_packets_.begin(); it != stored_packets_.end(); ++it) {
	it->clear();
	}

	stored_packets_.clear();
	stored_seq_nums_.clear();
	stored_lengths_.clear();
	stored_times_.clear();
	stored_send_times_.clear();
	stored_types_.clear();

	store_ = false;
	prev_index_ = 0;
	max_packet_length_ = 0;
	}

	bool RTPPacketHistory::StorePackets() const {
	CriticalSectionScoped cs(critsect_.get());
	return store_;
	}

	void RTPPacketHistory::VerifyAndAllocatePacketLength(size_t packet_length,
	uint32_t start_index) {
	assert(packet_length > 0);
	if (!store_) {
	return;
	}

	// If start_index > 0 this is a resize and we must check any new (empty)
	// packets created during the resize.
	if (start_index == 0 && packet_length <= max_packet_length_) {
	return;
	}

	max_packet_length_ = std::max(packet_length, max_packet_length_);

	std::vector<std::vector<uint8_t> >::iterator it;
	for (it = stored_packets_.begin() + start_index; it != stored_packets_.end();
	++it) {
	it->resize(max_packet_length_);
	}
	}

	int32_t RTPPacketHistory::PutRTPPacket(const uint8_t* packet,
	size_t packet_length,
	size_t max_packet_length,
	int64_t capture_time_ms,
	StorageType type) {
	if (type == kDontStore) {
	return 0;
	}

	CriticalSectionScoped cs(critsect_.get());
	if (!store_) {
	return 0;
	}

	assert(packet);
	assert(packet_length > 3);

	VerifyAndAllocatePacketLength(max_packet_length, 0);

	if (packet_length > max_packet_length_) {
	LOG(LS_WARNING) << "Failed to store RTP packet with length: "
	<< packet_length;
	return -1;
	}

	const uint16_t seq_num = (packet[2] << 8) + packet[3];

	// If index we're about to overwrite contains a packet that has not
	// yet been sent (probably pending in paced sender), we need to expand
	// the buffer.
	if (stored_lengths_[prev_index_] > 0 &&
	stored_send_times_[prev_index_] == 0) {
	size_t current_size = static_cast<uint16_t>(stored_packets_.size());
	if (current_size < kMaxHistoryCapacity) {
	size_t expanded_size = std::max(current_size * 3 / 2, current_size + 1);
	expanded_size = std::min(expanded_size, kMaxHistoryCapacity);
	Allocate(expanded_size);
	VerifyAndAllocatePacketLength(max_packet_length, current_size);
	// Causes discontinuity, but that's OK-ish. FindSeqNum() will still work,
	// but may be slower - at least until buffer has wrapped around once.
	prev_index_ = current_size;
	}
	}

	// Store packet
	std::vector<std::vector<uint8_t> >::iterator it =
	stored_packets_.begin() + prev_index_;
	// TODO(sprang): Overhaul this class and get rid of this copy step.
	// (Finally introduce the RtpPacket class?)
	std::copy(packet, packet + packet_length, it->begin());

	stored_seq_nums_[prev_index_] = seq_num;
	stored_lengths_[prev_index_] = packet_length;
	stored_times_[prev_index_] = (capture_time_ms > 0) ? capture_time_ms :
	clock_->TimeInMilliseconds();
	stored_send_times_[prev_index_] = 0; // Packet not sent.
	stored_types_[prev_index_] = type;

	++prev_index_;
	if (prev_index_ >= stored_seq_nums_.size()) {
	prev_index_ = 0;
	}
	return 0;
	}

	bool RTPPacketHistory::HasRTPPacket(uint16_t sequence_number) const {
	CriticalSectionScoped cs(critsect_.get());
	if (!store_) {
	return false;
	}

	int32_t index = 0;
	bool found = FindSeqNum(sequence_number, &index);
	if (!found) {
	return false;
	}

	size_t length = stored_lengths_.at(index);
	if (length == 0 \|\| length > max_packet_length_) {
	// Invalid length.
	return false;
	}
	return true;
	}

	bool RTPPacketHistory::SetSent(uint16_t sequence_number) {
	CriticalSectionScoped cs(critsect_.get());
	if (!store_) {
	return false;
	}

	int32_t index = 0;
	bool found = FindSeqNum(sequence_number, &index);
	if (!found) {
	return false;
	}

	// Send time already set.
	if (stored_send_times_[index] != 0) {
	return false;
	}

	stored_send_times_[index] = clock_->TimeInMilliseconds();
	return true;
	}

	bool RTPPacketHistory::GetPacketAndSetSendTime(uint16_t sequence_number,
	int64_t min_elapsed_time_ms,
	bool retransmit,
	uint8_t* packet,
	size_t* packet_length,
	int64_t* stored_time_ms) {
	CriticalSectionScoped cs(critsect_.get());
	assert(*packet_length >= max_packet_length_);
	if (!store_) {
	return false;
	}

	int32_t index = 0;
	bool found = FindSeqNum(sequence_number, &index);
	if (!found) {
	LOG(LS_WARNING) << "No match for getting seqNum " << sequence_number;
	return false;
	}

	size_t length = stored_lengths_.at(index);
	assert(length <= max_packet_length_);
	if (length == 0) {
	LOG(LS_WARNING) << "No match for getting seqNum " << sequence_number
	<< ", len " << length;
	return false;
	}

	// Verify elapsed time since last retrieve.
	int64_t now = clock_->TimeInMilliseconds();
	if (min_elapsed_time_ms > 0 &&
	((now - stored_send_times_.at(index)) < min_elapsed_time_ms)) {
	return false;
	}

	if (retransmit && stored_types_.at(index) == kDontRetransmit) {
	// No bytes copied since this packet shouldn't be retransmitted or is
	// of zero size.
	return false;
	}
	stored_send_times_[index] = clock_->TimeInMilliseconds();
	GetPacket(index, packet, packet_length, stored_time_ms);
	return true;
	}

	void RTPPacketHistory::GetPacket(int index,
	uint8_t* packet,
	size_t* packet_length,
	int64_t* stored_time_ms) const {
	// Get packet.
	size_t length = stored_lengths_.at(index);
	std::vector<std::vector<uint8_t> >::const_iterator it_found_packet =
	stored_packets_.begin() + index;
	std::copy(it_found_packet->begin(), it_found_packet->begin() + length,
	packet);
	*packet_length = length;
	*stored_time_ms = stored_times_.at(index);
	}

	bool RTPPacketHistory::GetBestFittingPacket(uint8_t* packet,
	size_t* packet_length,
	int64_t* stored_time_ms) {
	CriticalSectionScoped cs(critsect_.get());
	if (!store_)
	return false;
	int index = FindBestFittingPacket(*packet_length);
	if (index < 0)
	return false;
	GetPacket(index, packet, packet_length, stored_time_ms);
	return true;
	}

	// private, lock should already be taken
	bool RTPPacketHistory::FindSeqNum(uint16_t sequence_number,
	int32_t* index) const {
	uint16_t temp_sequence_number = 0;
	if (prev_index_ > 0) {
	*index = prev_index_ - 1;
	temp_sequence_number = stored_seq_nums_[*index];
	} else {
	*index = stored_seq_nums_.size() - 1;
	temp_sequence_number = stored_seq_nums_[*index]; // wrap
	}

	int32_t idx = (prev_index_ - 1) - (temp_sequence_number - sequence_number);
	if (idx >= 0 && idx < static_cast<int>(stored_seq_nums_.size())) {
	*index = idx;
	temp_sequence_number = stored_seq_nums_[*index];
	}

	if (temp_sequence_number != sequence_number) {
	// We did not found a match, search all.
	for (uint16_t m = 0; m < stored_seq_nums_.size(); m++) {
	if (stored_seq_nums_[m] == sequence_number) {
	*index = m;
	temp_sequence_number = stored_seq_nums_[*index];
	break;
	}
	}
	}
	if (temp_sequence_number == sequence_number) {
	// We found a match.
	return true;
	}
	return false;
	}

	int RTPPacketHistory::FindBestFittingPacket(size_t size) const {
	if (size < kMinPacketRequestBytes \|\| stored_lengths_.empty())
	return -1;
	size_t min_diff = std::numeric_limits<size_t>::max();
	int best_index = -1; // Returned unchanged if we don't find anything.
	for (size_t i = 0; i < stored_lengths_.size(); ++i) {
	if (stored_lengths_[i] == 0)
	continue;
	size_t diff = (stored_lengths_[i] > size) ?
	(stored_lengths_[i] - size) : (size - stored_lengths_[i]);
	if (diff < min_diff) {
	min_diff = diff;
	best_index = static_cast<int>(i);
	}
	}
	return best_index;
	}
	} // namespace webrtc