/*
 *  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.
 */

#ifndef MODULES_VIDEO_CODING_JITTER_BUFFER_H_
#define MODULES_VIDEO_CODING_JITTER_BUFFER_H_

#include <list>
#include <map>
#include <memory>
#include <set>
#include <vector>

#include "modules/include/module_common_types.h"
#include "modules/utility/include/process_thread.h"
#include "modules/video_coding/decoding_state.h"
#include "modules/video_coding/include/video_coding.h"
#include "modules/video_coding/include/video_coding_defines.h"
#include "modules/video_coding/inter_frame_delay.h"
#include "modules/video_coding/jitter_buffer_common.h"
#include "modules/video_coding/jitter_estimator.h"
#include "rtc_base/constructor_magic.h"
#include "rtc_base/critical_section.h"
#include "rtc_base/thread_annotations.h"
#include "system_wrappers/include/event_wrapper.h"

namespace webrtc {

enum VCMNackMode { kNack, kNoNack };

// forward declarations
class Clock;
class VCMFrameBuffer;
class VCMPacket;
class VCMEncodedFrame;

typedef std::list<VCMFrameBuffer*> UnorderedFrameList;

struct VCMJitterSample {
  VCMJitterSample() : timestamp(0), frame_size(0), latest_packet_time(-1) {}
  uint32_t timestamp;
  uint32_t frame_size;
  int64_t latest_packet_time;
};

class TimestampLessThan {
 public:
  bool operator()(uint32_t timestamp1, uint32_t timestamp2) const {
    return IsNewerTimestamp(timestamp2, timestamp1);
  }
};

class FrameList
    : public std::map<uint32_t, VCMFrameBuffer*, TimestampLessThan> {
 public:
  void InsertFrame(VCMFrameBuffer* frame);
  VCMFrameBuffer* PopFrame(uint32_t timestamp);
  VCMFrameBuffer* Front() const;
  VCMFrameBuffer* Back() const;
  int RecycleFramesUntilKeyFrame(FrameList::iterator* key_frame_it,
                                 UnorderedFrameList* free_frames);
  void CleanUpOldOrEmptyFrames(VCMDecodingState* decoding_state,
                               UnorderedFrameList* free_frames);
  void Reset(UnorderedFrameList* free_frames);
};

class Vp9SsMap {
 public:
  typedef std::map<uint32_t, GofInfoVP9, TimestampLessThan> SsMap;
  Vp9SsMap();
  ~Vp9SsMap();

  bool Insert(const VCMPacket& packet);
  void Reset();

  // Removes SS data that are older than |timestamp|.
  // The |timestamp| should be an old timestamp, i.e. packets with older
  // timestamps should no longer be inserted.
  void RemoveOld(uint32_t timestamp);

  bool UpdatePacket(VCMPacket* packet);
  void UpdateFrames(FrameList* frames);

  // Public for testing.
  // Returns an iterator to the corresponding SS data for the input |timestamp|.
  bool Find(uint32_t timestamp, SsMap::iterator* it);

 private:
  // These two functions are called by RemoveOld.
  // Checks if it is time to do a clean up (done each kSsCleanupIntervalSec).
  bool TimeForCleanup(uint32_t timestamp) const;

  // Advances the oldest SS data to handle timestamp wrap in cases where SS data
  // are received very seldom (e.g. only once in beginning, second when
  // IsNewerTimestamp is not true).
  void AdvanceFront(uint32_t timestamp);

  SsMap ss_map_;
};

class VCMJitterBuffer {
 public:
  VCMJitterBuffer(Clock* clock,
                  std::unique_ptr<EventWrapper> event,
                  NackSender* nack_sender = nullptr,
                  KeyFrameRequestSender* keyframe_request_sender = nullptr);

  ~VCMJitterBuffer();

  // Initializes and starts jitter buffer.
  void Start();

  // Signals all internal events and stops the jitter buffer.
  void Stop();

  // Returns true if the jitter buffer is running.
  bool Running() const;

  // Empty the jitter buffer of all its data.
  void Flush();

  // Get the number of received frames, by type, since the jitter buffer
  // was started.
  FrameCounts FrameStatistics() const;

  // Gets number of packets received.
  int num_packets() const;

  // Gets number of duplicated packets received.
  int num_duplicated_packets() const;

  // Gets number of packets discarded by the jitter buffer.
  int num_discarded_packets() const;

  // Statistics, Calculate frame and bit rates.
  void IncomingRateStatistics(unsigned int* framerate, unsigned int* bitrate);

  // Wait |max_wait_time_ms| for a complete frame to arrive.
  // If found, a pointer to the frame is returned. Returns nullptr otherwise.
  VCMEncodedFrame* NextCompleteFrame(uint32_t max_wait_time_ms);

  // Extract frame corresponding to input timestamp.
  // Frame will be set to a decoding state.
  VCMEncodedFrame* ExtractAndSetDecode(uint32_t timestamp);

  // Releases a frame returned from the jitter buffer, should be called when
  // done with decoding.
  void ReleaseFrame(VCMEncodedFrame* frame);

  // Returns the time in ms when the latest packet was inserted into the frame.
  // Retransmitted is set to true if any of the packets belonging to the frame
  // has been retransmitted.
  int64_t LastPacketTime(const VCMEncodedFrame* frame,
                         bool* retransmitted) const;

  // Inserts a packet into a frame returned from GetFrame().
  // If the return value is <= 0, |frame| is invalidated and the pointer must
  // be dropped after this function returns.
  VCMFrameBufferEnum InsertPacket(const VCMPacket& packet, bool* retransmitted);

  // Returns the estimated jitter in milliseconds.
  uint32_t EstimatedJitterMs();

  // Updates the round-trip time estimate.
  void UpdateRtt(int64_t rtt_ms);

  // Set the NACK mode. |high_rtt_nack_threshold_ms| is an RTT threshold in ms
  // above which NACK will be disabled if the NACK mode is |kNack|, -1 meaning
  // that NACK is always enabled in the |kNack| mode.
  // |low_rtt_nack_threshold_ms| is an RTT threshold in ms below which we expect
  // to rely on NACK only, and therefore are using larger buffers to have time
  // to wait for retransmissions.
  void SetNackMode(VCMNackMode mode,
                   int64_t low_rtt_nack_threshold_ms,
                   int64_t high_rtt_nack_threshold_ms);

  void SetNackSettings(size_t max_nack_list_size,
                       int max_packet_age_to_nack,
                       int max_incomplete_time_ms);

  // Returns the current NACK mode.
  VCMNackMode nack_mode() const;

  // Returns a list of the sequence numbers currently missing.
  std::vector<uint16_t> GetNackList(bool* request_key_frame);

  void RegisterStatsCallback(VCMReceiveStatisticsCallback* callback);

 private:
  class SequenceNumberLessThan {
   public:
    bool operator()(const uint16_t& sequence_number1,
                    const uint16_t& sequence_number2) const {
      return IsNewerSequenceNumber(sequence_number2, sequence_number1);
    }
  };
  typedef std::set<uint16_t, SequenceNumberLessThan> SequenceNumberSet;

  // Gets the frame assigned to the timestamp of the packet. May recycle
  // existing frames if no free frames are available. Returns an error code if
  // failing, or kNoError on success. |frame_list| contains which list the
  // packet was in, or NULL if it was not in a FrameList (a new frame).
  VCMFrameBufferEnum GetFrame(const VCMPacket& packet,
                              VCMFrameBuffer** frame,
                              FrameList** frame_list)
      RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);

  // Returns true if |frame| is continuous in |decoding_state|, not taking
  // decodable frames into account.
  bool IsContinuousInState(const VCMFrameBuffer& frame,
                           const VCMDecodingState& decoding_state) const
      RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);
  // Returns true if |frame| is continuous in the |last_decoded_state_|, taking
  // all decodable frames into account.
  bool IsContinuous(const VCMFrameBuffer& frame) const
      RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);
  // Looks for frames in |incomplete_frames_| which are continuous in the
  // provided |decoded_state|. Starts the search from the timestamp of
  // |decoded_state|.
  void FindAndInsertContinuousFramesWithState(
      const VCMDecodingState& decoded_state)
      RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);
  // Looks for frames in |incomplete_frames_| which are continuous in
  // |last_decoded_state_| taking all decodable frames into account. Starts
  // the search from |new_frame|.
  void FindAndInsertContinuousFrames(const VCMFrameBuffer& new_frame)
      RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);
  VCMFrameBuffer* NextFrame() const RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);
  // Returns true if the NACK list was updated to cover sequence numbers up to
  // |sequence_number|. If false a key frame is needed to get into a state where
  // we can continue decoding.
  bool UpdateNackList(uint16_t sequence_number)
      RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);
  bool TooLargeNackList() const;
  // Returns true if the NACK list was reduced without problem. If false a key
  // frame is needed to get into a state where we can continue decoding.
  bool HandleTooLargeNackList() RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);
  bool MissingTooOldPacket(uint16_t latest_sequence_number) const
      RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);
  // Returns true if the too old packets was successfully removed from the NACK
  // list. If false, a key frame is needed to get into a state where we can
  // continue decoding.
  bool HandleTooOldPackets(uint16_t latest_sequence_number)
      RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);
  // Drops all packets in the NACK list up until |last_decoded_sequence_number|.
  void DropPacketsFromNackList(uint16_t last_decoded_sequence_number);

  // Gets an empty frame, creating a new frame if necessary (i.e. increases
  // jitter buffer size).
  VCMFrameBuffer* GetEmptyFrame() RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);

  // Attempts to increase the size of the jitter buffer. Returns true on
  // success, false otherwise.
  bool TryToIncreaseJitterBufferSize() RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);

  // Recycles oldest frames until a key frame is found. Used if jitter buffer is
  // completely full. Returns true if a key frame was found.
  bool RecycleFramesUntilKeyFrame() RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);

  // Updates the frame statistics.
  // Counts only complete frames, so decodable incomplete frames will not be
  // counted.
  void CountFrame(const VCMFrameBuffer& frame)
      RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);

  // Update rolling average of packets per frame.
  void UpdateAveragePacketsPerFrame(int current_number_packets_);

  // Cleans the frame list in the JB from old/empty frames.
  // Should only be called prior to actual use.
  void CleanUpOldOrEmptyFrames() RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);

  // Returns true if |packet| is likely to have been retransmitted.
  bool IsPacketRetransmitted(const VCMPacket& packet) const;

  // The following three functions update the jitter estimate with the
  // payload size, receive time and RTP timestamp of a frame.
  void UpdateJitterEstimate(const VCMJitterSample& sample,
                            bool incomplete_frame);
  void UpdateJitterEstimate(const VCMFrameBuffer& frame, bool incomplete_frame);
  void UpdateJitterEstimate(int64_t latest_packet_time_ms,
                            uint32_t timestamp,
                            unsigned int frame_size,
                            bool incomplete_frame);

  // Returns true if we should wait for retransmissions, false otherwise.
  bool WaitForRetransmissions();

  int NonContinuousOrIncompleteDuration()
      RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);

  uint16_t EstimatedLowSequenceNumber(const VCMFrameBuffer& frame) const;

  void UpdateHistograms() RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);

  // Reset frame buffer and return it to free_frames_.
  void RecycleFrameBuffer(VCMFrameBuffer* frame)
      RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);

  Clock* clock_;
  // If we are running (have started) or not.
  bool running_;
  rtc::CriticalSection crit_sect_;
  // Event to signal when we have a frame ready for decoder.
  std::unique_ptr<EventWrapper> frame_event_;
  // Number of allocated frames.
  int max_number_of_frames_;
  UnorderedFrameList free_frames_ RTC_GUARDED_BY(crit_sect_);
  FrameList decodable_frames_ RTC_GUARDED_BY(crit_sect_);
  FrameList incomplete_frames_ RTC_GUARDED_BY(crit_sect_);
  VCMDecodingState last_decoded_state_ RTC_GUARDED_BY(crit_sect_);
  bool first_packet_since_reset_;

  // Statistics.
  VCMReceiveStatisticsCallback* stats_callback_ RTC_GUARDED_BY(crit_sect_);
  // Frame counts for each type (key, delta, ...)
  FrameCounts receive_statistics_;
  // Latest calculated frame rates of incoming stream.
  unsigned int incoming_frame_rate_;
  unsigned int incoming_frame_count_;
  int64_t time_last_incoming_frame_count_;
  unsigned int incoming_bit_count_;
  unsigned int incoming_bit_rate_;
  // Number of packets in a row that have been too old.
  int num_consecutive_old_packets_;
  // Number of packets received.
  int num_packets_ RTC_GUARDED_BY(crit_sect_);
  // Number of duplicated packets received.
  int num_duplicated_packets_ RTC_GUARDED_BY(crit_sect_);
  // Number of packets discarded by the jitter buffer.
  int num_discarded_packets_ RTC_GUARDED_BY(crit_sect_);
  // Time when first packet is received.
  int64_t time_first_packet_ms_ RTC_GUARDED_BY(crit_sect_);

  // Jitter estimation.
  // Filter for estimating jitter.
  VCMJitterEstimator jitter_estimate_;
  // Calculates network delays used for jitter calculations.
  VCMInterFrameDelay inter_frame_delay_;
  VCMJitterSample waiting_for_completion_;
  int64_t rtt_ms_;

  // NACK and retransmissions.
  VCMNackMode nack_mode_;
  int64_t low_rtt_nack_threshold_ms_;
  int64_t high_rtt_nack_threshold_ms_;
  // Holds the internal NACK list (the missing sequence numbers).
  SequenceNumberSet missing_sequence_numbers_;
  uint16_t latest_received_sequence_number_;
  size_t max_nack_list_size_;
  int max_packet_age_to_nack_;  // Measured in sequence numbers.
  int max_incomplete_time_ms_;

  // Estimated rolling average of packets per frame
  float average_packets_per_frame_;
  // average_packets_per_frame converges fast if we have fewer than this many
  // frames.
  int frame_counter_;

  RTC_DISALLOW_COPY_AND_ASSIGN(VCMJitterBuffer);
};
}  // namespace webrtc

#endif  // MODULES_VIDEO_CODING_JITTER_BUFFER_H_