Generalize FEC header formatting. (pt. 4)

webrtc/modules/rtp_rtcp/source/forward_error_correction.h

 /*
  *  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 WEBRTC_MODULES_RTP_RTCP_SOURCE_FORWARD_ERROR_CORRECTION_H_
 #define WEBRTC_MODULES_RTP_RTCP_SOURCE_FORWARD_ERROR_CORRECTION_H_
 
 #include <stdint.h>
 
 #include <list>
+#include <map>
 #include <memory>
+#include <tuple>
 #include <vector>
 
+#include "webrtc/base/basictypes.h"
+#include "webrtc/base/constructormagic.h"
 #include "webrtc/base/refcount.h"
 #include "webrtc/base/scoped_ref_ptr.h"
 #include "webrtc/modules/rtp_rtcp/include/rtp_rtcp_defines.h"
 #include "webrtc/modules/rtp_rtcp/source/forward_error_correction_internal.h"
-#include "webrtc/typedefs.h"
 
 namespace webrtc {
 
+class FecHeaderReader;
+class FecHeaderWriter;
+
 // Performs codec-independent forward error correction (FEC), based on RFC 5109.
 // Option exists to enable unequal protection (UEP) across packets.
 // This is not to be confused with protection within packets
 // (referred to as uneven level protection (ULP) in RFC 5109).
 class ForwardErrorCorrection {
  public:
-  // Maximum number of media packets we can protect
-  static constexpr size_t kMaxMediaPackets = 48u;
-
   // TODO(holmer): As a next step all these struct-like packet classes should be
   // refactored into proper classes, and their members should be made private.
   // This will require parts of the functionality in forward_error_correction.cc
   // and receiver_fec.cc to be refactored into the packet classes.
   class Packet {
    public:
     Packet() : length(0), data(), ref_count_(0) {}
     virtual ~Packet() {}
 
     // Add a reference.
@@ skipping 25 matching lines @@
 
   // The received list parameter of DecodeFec() references structs of this type.
   //
   // The ssrc member is needed to ensure that we can restore the SSRC field of
   // recovered packets. In most situations this could be retrieved from other
   // media packets, but in the case of an FEC packet protecting a single
   // missing media packet, we have no other means of obtaining it.
   // TODO(holmer): Refactor into a proper class.
   class ReceivedPacket : public SortablePacket {
    public:
-    ReceivedPacket();
-    ~ReceivedPacket();
-
     uint32_t ssrc;  // SSRC of the current frame. Must be set for FEC
                     // packets, but not required for media packets.
     bool is_fec;    // Set to true if this is an FEC packet and false
                     // otherwise.
     rtc::scoped_refptr<Packet> pkt;  // Pointer to the packet storage.
   };
 
-  // The recovered list parameter of #DecodeFec() references structs of
+  // The recovered list parameter of DecodeFec() references structs of
   // this type.
   // TODO(holmer): Refactor into a proper class.
   class RecoveredPacket : public SortablePacket {
    public:
-    RecoveredPacket();
-    ~RecoveredPacket();
-
     bool was_recovered;  // Will be true if this packet was recovered by
                          // the FEC. Otherwise it was a media packet passed in
                          // through the received packet list.
     bool returned;  // True when the packet already has been returned to the
                     // caller through the callback.
-    uint8_t length_recovery[2];  // Two bytes used for recovering the packet
-                                 // length with XOR operations.
     rtc::scoped_refptr<Packet> pkt;  // Pointer to the packet storage.
   };
 
+  // Used to link media packets to their protecting FEC packets.
+  //
+  // TODO(holmer): Refactor into a proper class.
+  class ProtectedPacket : public ForwardErrorCorrection::SortablePacket {

[danilchap, 2016/08/22 13:00:41]

any reason to have ProtectedPacket in the public section?

[brandtr, 2016/08/23 08:19:11]

I think so, since it is used in the public interface of ReceivedFecPacket :(

Depending on time, it is my intention to refactor these packet classes. This
might be done in conjunction with the switch to RtpPacket's.

+   public:
+    rtc::scoped_refptr<ForwardErrorCorrection::Packet> pkt;
+  };
+
+  using ProtectedPacketList = std::list<std::unique_ptr<ProtectedPacket>>;
+
+  // Used for internal storage of received FEC packets in a list.
+  //
+  // TODO(holmer): Refactor into a proper class.
+  class ReceivedFecPacket : public ForwardErrorCorrection::SortablePacket {
+   public:
+    ProtectedPacketList protected_packets;
+    // RTP header fields.
+    uint32_t rtp_ssrc;
+    // FEC header fields.
+    size_t fec_header_size;
+    size_t protection_length;
+    // Packet masks metadata.
+    // SSRC -> [SN base, packet mask offset, packet mask size (bytes)]
+    std::map<uint32_t, std::tuple<uint16_t, size_t, size_t>> packet_mask_info;
+    // Raw data.
+    rtc::scoped_refptr<ForwardErrorCorrection::Packet> pkt;
+  };
+
   using PacketList = std::list<std::unique_ptr<Packet>>;
   using ReceivedPacketList = std::list<std::unique_ptr<ReceivedPacket>>;
   using RecoveredPacketList = std::list<std::unique_ptr<RecoveredPacket>>;
+  using ReceivedFecPacketList = std::list<std::unique_ptr<ReceivedFecPacket>>;
 
-  ForwardErrorCorrection();
-  virtual ~ForwardErrorCorrection();
+  // Moveable but not copyable.
+  RTC_DISALLOW_COPY_AND_ASSIGN(ForwardErrorCorrection);

[danilchap, 2016/08/22 13:00:41]

this line should always be the last in the class definiton.

[brandtr, 2016/08/23 08:19:11]

Done, see
https://codereview.webrtc.org/2260803002/diff/20001/webrtc/modules/rtp_rtcp/s....

+  ForwardErrorCorrection(ForwardErrorCorrection&&) = default;
 
-  //
+  // Creates a ForwardErrorCorrection tailored for a specific FEC scheme.
+  static ForwardErrorCorrection CreateUlpfec();

[danilchap, 2016/08/22 13:00:41]

ForwardErrorCorrection is not a small class to return it by value.

May be return std::unique_ptr<ForwardErrorCorrection> instead.
Or, since the only difference is header reader/writer, join those two interfaces
into one (since they always have to match: it doesn't make sense to have
UlpReader with FlexWriter)
Make a public constructor
ForwardErrorCorrection(std::unique_ptr<FecHeaderFormat>)
and in the interface FecHeaderFormat have
static std::unique_ptr<FecHeaderFormat> CreateUlpfec();
static std::unique_ptr<FecHeaderFormat> CreateFlexfec();

[brandtr, 2016/08/23 08:19:11]

Right, but since ForwardErrorCorrection is neither copyable nor assignable, this
function call will only ever result in moves, which should be OK? I initially
considered returning a unique_ptr, but I didn't see the point of the additional
indirection since this class is not polymorphic.
I agree that they always have to match, but later on I plan to split
ForwardErrorCorrection into two classes: ParityErasureCodeEncoder (which has a
FecHeaderWriter) and ParityErasureCodeDecoder (which has a FecHeaderReader).
This will make the structure of the code easier to follow. It will be up to
higher layers to ensure that the correct decoder is paired with the current
encoder.

[brandtr, 2016/08/23 11:17:47]

Reimplemented to use std::unique_ptr's.

+  static ForwardErrorCorrection CreateFlexfec();
+
   // Generates a list of FEC packets from supplied media packets.
   //
   // Input:  media_packets          List of media packets to protect, of type
   //                                Packet. All packets must belong to the
   //                                same frame and the list must not be empty.
   // Input:  protection_factor      FEC protection overhead in the [0, 255]
   //                                domain. To obtain 100% overhead, or an
   //                                equal number of FEC packets as
   //                                media packets, use 255.
   // Input:  num_important_packets  The number of "important" packets in the
@@ skipping 12 matching lines @@
   // Input:  fec_mask_type          The type of packet mask used in the FEC.
   //                                Random or bursty type may be selected. The
   //                                bursty type is only defined up to 12 media
   //                                packets. If the number of media packets is
   //                                above 12, the packet masks from the random
   //                                table will be selected.
   // Output: fec_packets            List of pointers to generated FEC packets,
   //                                of type Packet. Must be empty on entry.
   //                                The memory available through the list will
   //                                be valid until the next call to
-  //                                GenerateFec().
+  //                                EncodeFec().
   //
   // Returns 0 on success, -1 on failure.
   //
-  int GenerateFec(const PacketList& media_packets,
-                  uint8_t protection_factor, int num_important_packets,
-                  bool use_unequal_protection, FecMaskType fec_mask_type,
-                  std::list<Packet*>* fec_packets);
+  int EncodeFec(const PacketList& media_packets,
+                uint8_t protection_factor,
+                int num_important_packets,
+                bool use_unequal_protection,
+                FecMaskType fec_mask_type,
+                std::list<Packet*>* fec_packets);
 
-  //
   // Decodes a list of received media and FEC packets. It will parse the
   // |received_packets|, storing FEC packets internally, and move
   // media packets to |recovered_packets|. The recovered list will be
   // sorted by ascending sequence number and have duplicates removed.
   // The function should be called as new packets arrive, and
   // |recovered_packets| will be progressively assembled with each call.
   // When the function returns, |received_packets| will be empty.
   //
   // The caller will allocate packets submitted through |received_packets|.
   // The function will handle allocation of recovered packets.
   //
   // Input:  received_packets   List of new received packets, of type
   //                            ReceivedPacket, belonging to a single
   //                            frame. At output the list will be empty,
   //                            with packets either stored internally,
   //                            or accessible through the recovered list.
   // Output: recovered_packets  List of recovered media packets, of type
   //                            RecoveredPacket, belonging to a single
   //                            frame. The memory available through the
   //                            list will be valid until the next call to
   //                            DecodeFec().
   //
   // Returns 0 on success, -1 on failure.
   //
   int DecodeFec(ReceivedPacketList* received_packets,
                 RecoveredPacketList* recovered_packets);
 
   // Get the number of generated FEC packets, given the number of media packets
   // and the protection factor.
-  int GetNumberOfFecPackets(int num_media_packets, int protection_factor);
+  static int NumFecPackets(int num_media_packets, int protection_factor);
 
-  // Gets the size in bytes of the FEC/ULP headers, which must be accounted for
-  // as packet overhead. Returns the packet overhead in bytes.
-  static size_t PacketOverhead();
+  // Gets the maximum size of the FEC headers in bytes, which must be
+  // accounted for as packet overhead.
+  size_t MaxPacketOverhead() const;
 
   // Reset internal states from last frame and clear |recovered_packets|.
   // Frees all memory allocated by this class.
   void ResetState(RecoveredPacketList* recovered_packets);
 
+  // TODO(brandtr): Remove these functions when the Packet classes
+  // have been refactored.
+  static uint16_t ParseSequenceNumber(uint8_t* packet);
+  static uint32_t ParseSsrc(uint8_t* packet);
+
  private:
-  // Used to link media packets to their protecting FEC packets.
-  //
-  // TODO(holmer): Refactor into a proper class.
-  class ProtectedPacket : public ForwardErrorCorrection::SortablePacket {
-   public:
-    rtc::scoped_refptr<ForwardErrorCorrection::Packet> pkt;
-  };
-
-  using ProtectedPacketList = std::list<std::unique_ptr<ProtectedPacket>>;
-
-  // Used for internal storage of received FEC packets in a list.
-  //
-  // TODO(holmer): Refactor into a proper class.
-  class ReceivedFecPacket : public ForwardErrorCorrection::SortablePacket {
-   public:
-    ProtectedPacketList protected_packets;
-    uint32_t ssrc;  // SSRC of the current frame.
-    rtc::scoped_refptr<ForwardErrorCorrection::Packet> pkt;
-  };
-
-  using ReceivedFecPacketList = std::list<std::unique_ptr<ReceivedFecPacket>>;
+  ForwardErrorCorrection(std::unique_ptr<FecHeaderReader> fec_header_reader,
+                         std::unique_ptr<FecHeaderWriter> fec_header_writer);
 
   // Analyzes |media_packets| for holes in the sequence and inserts zero columns
   // into the |packet_mask| where those holes are found. Zero columns means that
   // those packets will have no protection.
   // Returns the number of bits used for one row of the new packet mask.
   // Requires that |packet_mask| has at least 6 * |num_fec_packets| bytes
   // allocated.
-  int InsertZerosInBitMasks(const PacketList& media_packets,
-                            uint8_t* packet_mask, int num_mask_bytes,
-                            int num_fec_packets);
+  int InsertZerosInPacketMasks(const PacketList& media_packets,
+                               size_t num_fec_packets);
 
-  // Inserts |num_zeros| zero columns into |new_mask| at position
-  // |new_bit_index|. If the current byte of |new_mask| can't fit all zeros, the
-  // byte will be filled with zeros from |new_bit_index|, but the next byte will
-  // be untouched.
-  static void InsertZeroColumns(int num_zeros, uint8_t* new_mask,
-                                int new_mask_bytes, int num_fec_packets,
-                                int new_bit_index);
+  // Writes FEC payload and some recovery fields in the FEC headers.
+  void GenerateFecPayloads(const PacketList& media_packets,
+                           size_t num_fec_packets);
 
-  // Copies the left most bit column from the byte pointed to by
-  // |old_bit_index| in |old_mask| to the right most column of the byte pointed
-  // to by |new_bit_index| in |new_mask|. |old_mask_bytes| and |new_mask_bytes|
-  // represent the number of bytes used per row for each mask. |num_fec_packets|
-  // represent the number of rows of the masks.
-  // The copied bit is shifted out from |old_mask| and is shifted one step to
-  // the left in |new_mask|. |new_mask| will contain "xxxx xxn0" after this
-  // operation, where x are previously inserted bits and n is the new bit.
-  static void CopyColumn(uint8_t* new_mask, int new_mask_bytes,
-                         uint8_t* old_mask, int old_mask_bytes,
-                         int num_fec_packets, int new_bit_index,
-                         int old_bit_index);
-
-  void GenerateFecUlpHeaders(const PacketList& media_packets,
-                             uint8_t* packet_mask, int num_fec_packets,
-                             bool l_bit);
-
-  void GenerateFecBitStrings(const PacketList& media_packets,
-                             uint8_t* packet_mask, int num_fec_packets,
-                             bool l_bit);
+  // Writes the FEC header fields that are not written by GenerateFecPayloads.
+  // This includes writing the packet masks.
+  void FinalizeFecHeaders(const PacketList& media_packets,
+                          size_t num_fec_packets);
 
   // Inserts the |received_packets| into the internal received FEC packet list
   // or into |recovered_packets|.
   void InsertPackets(ReceivedPacketList* received_packets,
                      RecoveredPacketList* recovered_packets);
 
   // Inserts the |received_packet| into |recovered_packets|. Deletes duplicates.
   void InsertMediaPacket(ReceivedPacket* received_packet,
                          RecoveredPacketList* recovered_packets);
 
   // Assigns pointers to the recovered packet from all FEC packets which cover
   // it.
   // Note: This reduces the complexity when we want to try to recover a packet
   // since we don't have to find the intersection between recovered packets and
   // packets covered by the FEC packet.
   void UpdateCoveringFecPackets(RecoveredPacket* packet);
 
   // Insert |received_packet| into internal FEC list. Deletes duplicates.
   void InsertFecPacket(ReceivedPacket* received_packet,
                        const RecoveredPacketList* recovered_packets);
 
   // Assigns pointers to already recovered packets covered by |fec_packet|.
   static void AssignRecoveredPackets(
       ReceivedFecPacket* fec_packet,
       const RecoveredPacketList* recovered_packets);
 
-  // Insert |rec_packet_to_insert| into |recovered_packets| in correct position.
-  void InsertRecoveredPacket(RecoveredPacket* rec_packet_to_insert,
-                             RecoveredPacketList* recovered_packets);
-
   // Attempt to recover missing packets, using the internally stored
   // received FEC packets.
-  void AttemptRecover(RecoveredPacketList* recovered_packets);
-
-  // Initializes packet recovery using the received |fec_packet|.
-  static bool StartPacketRecovery(const ReceivedFecPacket* fec_packet,
-                                  RecoveredPacket* recovered_packet);
+  void AttemptRecovery(RecoveredPacketList* recovered_packets);
 
   // Performs XOR between |src| and |dst| and stores the result in |dst|.
-  static void XorPackets(const Packet* src, RecoveredPacket* dst);
+  // The parameters |src_offset| and |dst_offset| determines at what byte
+  // the XOR operation starts in |src| and |dst|, respectively. In total,
+  // |payload_length| bytes are XORed.
+  static void XorPackets(const Packet* src,
+                         size_t src_offset,
+                         size_t payload_length,
+                         size_t dst_offset,
+                         Packet* dst);
 
-  // Finish up the recovery of a packet.
-  static bool FinishPacketRecovery(RecoveredPacket* recovered_packet);
+  // Initializes headers and payload before the XOR operation
+  // that recovers a packet.
+  bool StartPacketRecovery(ReceivedFecPacket* fec_packet,
+                           RecoveredPacket* recovered_packet) const;
+
+  // Finalizes recovery of packet by setting RTP header fields.
+  // This is not specific to the FEC scheme used.
+  static bool FinishPacketRecovery(const ReceivedFecPacket* fec_packet,
+                                   RecoveredPacket* recovered_packet);
 
   // Recover a missing packet.
-  bool RecoverPacket(const ReceivedFecPacket* fec_packet,
-                     RecoveredPacket* rec_packet_to_insert);
+  bool RecoverPacket(ReceivedFecPacket* fec_packet,
+                     RecoveredPacket* recovered_packet);
 
   // Get the number of missing media packets which are covered by |fec_packet|.
   // An FEC packet can recover at most one packet, and if zero packets are
   // missing the FEC packet can be discarded. This function returns 2 when two
   // or more packets are missing.
   static int NumCoveredPacketsMissing(const ReceivedFecPacket* fec_packet);
 
   // Discards old packets in |recovered_packets|, which are no longer relevant
   // for recovering lost packets.
-  static void DiscardOldRecoveredPackets(
-      RecoveredPacketList* recovered_packets);
-  static uint16_t ParseSequenceNumber(uint8_t* packet);
+  void DiscardOldRecoveredPackets(RecoveredPacketList* recovered_packets);
+
+  std::unique_ptr<FecHeaderReader> fec_header_reader_;
+  std::unique_ptr<FecHeaderWriter> fec_header_writer_;
 
   std::vector<Packet> generated_fec_packets_;
   ReceivedFecPacketList received_fec_packets_;
 
   // Arrays used to avoid dynamically allocating memory when generating
-  // the packet masks in the ULPFEC headers.
-  // (There are never more than |kMaxMediaPackets| FEC packets generated.)
-  uint8_t packet_mask_[kMaxMediaPackets * kMaskSizeLBitSet];
-  uint8_t tmp_packet_mask_[kMaxMediaPackets * kMaskSizeLBitSet];
+  // the packet masks.
+  // (There are never more than |kUlpfecMaxMediaPackets| FEC packets generated.)
+  uint8_t packet_masks_[kUlpfecMaxMediaPackets * kUlpfecPacketMaskSizeLBitSet];
+  uint8_t
+      tmp_packet_masks_[kUlpfecMaxMediaPackets * kUlpfecPacketMaskSizeLBitSet];
+  size_t packet_mask_size_;  //
 };
+
+// Classes derived from FecHeader{Reader,Writer} encapsulate the
+// specifics of reading and writing FEC header for, e.g., ULPFEC
+// and FlexFEC.
+class FecHeaderReader {
+ public:
+  virtual ~FecHeaderReader();
+
+  // The maximum number of media packets that can be covered by one FEC packet.
+  size_t MaxMediaPackets() const;
+
+  // The maximum number of FEC packets that is supported, per call
+  // to ForwardErrorCorrection::EncodeFec().
+  size_t MaxFecPackets() const;
+
+  // Parses FEC header and stores information in ReceivedFecPacket members.
+  virtual bool ReadFecHeader(
+      ForwardErrorCorrection::ReceivedFecPacket* fec_packet) const = 0;
+
+ protected:
+  FecHeaderReader(size_t max_media_packets, size_t max_fec_packets);
+
+  const size_t max_media_packets_;
+  const size_t max_fec_packets_;
+};
+
+class FecHeaderWriter {
+ public:
+  FecHeaderWriter(size_t max_media_packets, size_t max_fec_packets);
+  virtual ~FecHeaderWriter();
+
+  // The maximum number of media packets that can be covered by one FEC packet.
+  size_t MaxMediaPackets() const;
+
+  // The maximum number of FEC packets that is supported, per call
+  // to ForwardErrorCorrection::EncodeFec().
+  size_t MaxFecPackets() const;
+
+  // The maximum overhead (in bytes) per packet, due to FEC headers.
+  size_t MaxPacketOverhead() const;
+
+  // Calculates the minimum packet mask size needed (in bytes),
+  // given the discrete options of the ULPFEC masks and the bits
+  // set in the current packet mask.
+  virtual size_t MinPacketMaskSize(const uint8_t* packet_mask,
+                                   size_t packet_mask_size) const = 0;
+
+  // The header size (in bytes), given the packet mask size.
+  virtual size_t FecHeaderSize(size_t packet_mask_size) const = 0;
+
+  // Writes FEC header.
+  virtual void FinalizeFecHeader(
+      const ForwardErrorCorrection::PacketList& media_packets,
+      const uint8_t* packet_mask,
+      size_t packet_mask_size,
+      ForwardErrorCorrection::Packet* fec_packet) const = 0;
+
+ protected:
+  FecHeaderWriter(size_t max_media_packets,
+                  size_t max_fec_packets,
+                  size_t max_packet_overhead_);
+
+  const size_t max_media_packets_;
+  const size_t max_fec_packets_;
+  const size_t max_packet_overhead_;
+};
+
 }  // namespace webrtc
+
 #endif  // WEBRTC_MODULES_RTP_RTCP_SOURCE_FORWARD_ERROR_CORRECTION_H_