Note: We no longer publish the latest version of our code here. We primarily use a kumc-bmi github organization. The heron ETL repository, in particular, is not public. Peers in the informatics community should see MultiSiteDev for details on requesting access.

source: webrtc/webrtc/modules/rtp_rtcp/source/forward_error_correction_internal.cc @ 0:4bda6873e34c

pub_scrub_3792 tip
Last change on this file since 0:4bda6873e34c was 0:4bda6873e34c, checked in by Michael Prittie <mprittie@…>, 6 years ago

Scrubbed password for publication.

File size: 15.1 KB
Line 
1/*
2 *  Copyright (c) 2012 The WebRTC project authors. All Rights Reserved.
3 *
4 *  Use of this source code is governed by a BSD-style license
5 *  that can be found in the LICENSE file in the root of the source
6 *  tree. An additional intellectual property rights grant can be found
7 *  in the file PATENTS.  All contributing project authors may
8 *  be found in the AUTHORS file in the root of the source tree.
9 */
10
11#include "webrtc/modules/rtp_rtcp/source/forward_error_correction_internal.h"
12
13#include <assert.h>
14#include <string.h>
15
16#include "webrtc/modules/rtp_rtcp/source/fec_private_tables_bursty.h"
17#include "webrtc/modules/rtp_rtcp/source/fec_private_tables_random.h"
18
19namespace {
20
21// Allow for different modes of protection for packets in UEP case.
22enum ProtectionMode {
23  kModeNoOverlap,
24  kModeOverlap,
25  kModeBiasFirstPacket,
26};
27
28// Fits an input mask (sub_mask) to an output mask.
29// The mask is a matrix where the rows are the FEC packets,
30// and the columns are the source packets the FEC is applied to.
31// Each row of the mask is represented by a number of mask bytes.
32//
33// \param[in]  num_mask_bytes     The number of mask bytes of output mask.
34// \param[in]  num_sub_mask_bytes The number of mask bytes of input mask.
35// \param[in]  num_rows           The number of rows of the input mask.
36// \param[in]  sub_mask           A pointer to hold the input mask, of size
37//                                [0, num_rows * num_sub_mask_bytes]
38// \param[out] packet_mask        A pointer to hold the output mask, of size
39//                                [0, x * num_mask_bytes], where x >= num_rows.
40void FitSubMask(int num_mask_bytes, int num_sub_mask_bytes, int num_rows,
41                const uint8_t* sub_mask, uint8_t* packet_mask) {
42  if (num_mask_bytes == num_sub_mask_bytes) {
43    memcpy(packet_mask, sub_mask, num_rows * num_sub_mask_bytes);
44  } else {
45    for (int i = 0; i < num_rows; ++i) {
46      int pkt_mask_idx = i * num_mask_bytes;
47      int pkt_mask_idx2 = i * num_sub_mask_bytes;
48      for (int j = 0; j < num_sub_mask_bytes; ++j) {
49        packet_mask[pkt_mask_idx] = sub_mask[pkt_mask_idx2];
50        pkt_mask_idx++;
51        pkt_mask_idx2++;
52      }
53    }
54  }
55}
56
57// Shifts a mask by number of columns (bits), and fits it to an output mask.
58// The mask is a matrix where the rows are the FEC packets,
59// and the columns are the source packets the FEC is applied to.
60// Each row of the mask is represented by a number of mask bytes.
61//
62// \param[in]  num_mask_bytes     The number of mask bytes of output mask.
63// \param[in]  num_sub_mask_bytes The number of mask bytes of input mask.
64// \param[in]  num_column_shift   The number columns to be shifted, and
65//                                the starting row for the output mask.
66// \param[in]  end_row            The ending row for the output mask.
67// \param[in]  sub_mask           A pointer to hold the input mask, of size
68//                                [0, (end_row_fec - start_row_fec) *
69//                                    num_sub_mask_bytes]
70// \param[out] packet_mask        A pointer to hold the output mask, of size
71//                                [0, x * num_mask_bytes],
72//                                where x >= end_row_fec.
73// TODO (marpan): This function is doing three things at the same time:
74// shift within a byte, byte shift and resizing.
75// Split up into subroutines.
76void ShiftFitSubMask(int num_mask_bytes, int res_mask_bytes,
77                     int num_column_shift, int end_row, const uint8_t* sub_mask,
78                     uint8_t* packet_mask) {
79
80  // Number of bit shifts within a byte
81  const int num_bit_shifts = (num_column_shift % 8);
82  const int num_byte_shifts = num_column_shift >> 3;
83
84  // Modify new mask with sub-mask21.
85
86  // Loop over the remaining FEC packets.
87  for (int i = num_column_shift; i < end_row; ++i) {
88    // Byte index of new mask, for row i and column res_mask_bytes,
89    // offset by the number of bytes shifts
90    int pkt_mask_idx =
91        i * num_mask_bytes + res_mask_bytes - 1 + num_byte_shifts;
92    // Byte index of sub_mask, for row i and column res_mask_bytes
93    int pkt_mask_idx2 =
94        (i - num_column_shift) * res_mask_bytes + res_mask_bytes - 1;
95
96    uint8_t shift_right_curr_byte = 0;
97    uint8_t shift_left_prev_byte = 0;
98    uint8_t comb_new_byte = 0;
99
100    // Handle case of num_mask_bytes > res_mask_bytes:
101    // For a given row, copy the rightmost "numBitShifts" bits
102    // of the last byte of sub_mask into output mask.
103    if (num_mask_bytes > res_mask_bytes) {
104      shift_left_prev_byte = (sub_mask[pkt_mask_idx2] << (8 - num_bit_shifts));
105      packet_mask[pkt_mask_idx + 1] = shift_left_prev_byte;
106    }
107
108    // For each row i (FEC packet), shift the bit-mask of the sub_mask.
109    // Each row of the mask contains "resMaskBytes" of bytes.
110    // We start from the last byte of the sub_mask and move to first one.
111    for (int j = res_mask_bytes - 1; j > 0; j--) {
112      // Shift current byte of sub21 to the right by "numBitShifts".
113      shift_right_curr_byte = sub_mask[pkt_mask_idx2] >> num_bit_shifts;
114
115      // Fill in shifted bits with bits from the previous (left) byte:
116      // First shift the previous byte to the left by "8-numBitShifts".
117      shift_left_prev_byte =
118          (sub_mask[pkt_mask_idx2 - 1] << (8 - num_bit_shifts));
119
120      // Then combine both shifted bytes into new mask byte.
121      comb_new_byte = shift_right_curr_byte | shift_left_prev_byte;
122
123      // Assign to new mask.
124      packet_mask[pkt_mask_idx] = comb_new_byte;
125      pkt_mask_idx--;
126      pkt_mask_idx2--;
127    }
128    // For the first byte in the row (j=0 case).
129    shift_right_curr_byte = sub_mask[pkt_mask_idx2] >> num_bit_shifts;
130    packet_mask[pkt_mask_idx] = shift_right_curr_byte;
131
132  }
133}
134}  // namespace
135
136namespace webrtc {
137namespace internal {
138
139PacketMaskTable::PacketMaskTable(FecMaskType fec_mask_type,
140                                 int num_media_packets)
141    : fec_mask_type_(InitMaskType(fec_mask_type, num_media_packets)),
142      fec_packet_mask_table_(InitMaskTable(fec_mask_type_)) {}
143
144// Sets |fec_mask_type_| to the type of packet mask selected. The type of
145// packet mask selected is based on |fec_mask_type| and |num_media_packets|.
146// If |num_media_packets| is larger than the maximum allowed by |fec_mask_type|
147// for the bursty type, then the random type is selected.
148FecMaskType PacketMaskTable::InitMaskType(FecMaskType fec_mask_type,
149                                          int num_media_packets) {
150  // The mask should not be bigger than |packetMaskTbl|.
151  assert(num_media_packets <= static_cast<int>(sizeof(kPacketMaskRandomTbl) /
152                                               sizeof(*kPacketMaskRandomTbl)));
153  switch (fec_mask_type) {
154    case kFecMaskRandom: { return kFecMaskRandom; }
155    case kFecMaskBursty: {
156      int max_media_packets = static_cast<int>(sizeof(kPacketMaskBurstyTbl) /
157                                               sizeof(*kPacketMaskBurstyTbl));
158      if (num_media_packets > max_media_packets) {
159        return kFecMaskRandom;
160      } else {
161        return kFecMaskBursty;
162      }
163    }
164  }
165  assert(false);
166  return kFecMaskRandom;
167}
168
169// Returns the pointer to the packet mask tables corresponding to type
170// |fec_mask_type|.
171const uint8_t*** PacketMaskTable::InitMaskTable(FecMaskType fec_mask_type) {
172  switch (fec_mask_type) {
173    case kFecMaskRandom: { return kPacketMaskRandomTbl; }
174    case kFecMaskBursty: { return kPacketMaskBurstyTbl; }
175  }
176  assert(false);
177  return kPacketMaskRandomTbl;
178}
179
180// Remaining protection after important (first partition) packet protection
181void RemainingPacketProtection(int num_media_packets, int num_fec_remaining,
182                               int num_fec_for_imp_packets, int num_mask_bytes,
183                               ProtectionMode mode, uint8_t* packet_mask,
184                               const PacketMaskTable& mask_table) {
185  if (mode == kModeNoOverlap) {
186    // sub_mask21
187
188    const int l_bit =
189        (num_media_packets - num_fec_for_imp_packets) > 16 ? 1 : 0;
190
191    const int res_mask_bytes =
192        (l_bit == 1) ? kMaskSizeLBitSet : kMaskSizeLBitClear;
193
194    const uint8_t* packet_mask_sub_21 = mask_table.fec_packet_mask_table()[
195        num_media_packets - num_fec_for_imp_packets - 1][num_fec_remaining - 1];
196
197    ShiftFitSubMask(num_mask_bytes, res_mask_bytes, num_fec_for_imp_packets,
198                    (num_fec_for_imp_packets + num_fec_remaining),
199                    packet_mask_sub_21, packet_mask);
200
201  } else if (mode == kModeOverlap || mode == kModeBiasFirstPacket) {
202    // sub_mask22
203
204    const uint8_t* packet_mask_sub_22 = mask_table
205        .fec_packet_mask_table()[num_media_packets - 1][num_fec_remaining - 1];
206
207    FitSubMask(num_mask_bytes, num_mask_bytes, num_fec_remaining,
208               packet_mask_sub_22,
209               &packet_mask[num_fec_for_imp_packets * num_mask_bytes]);
210
211    if (mode == kModeBiasFirstPacket) {
212      for (int i = 0; i < num_fec_remaining; ++i) {
213        int pkt_mask_idx = i * num_mask_bytes;
214        packet_mask[pkt_mask_idx] = packet_mask[pkt_mask_idx] | (1 << 7);
215      }
216    }
217  } else {
218    assert(false);
219  }
220
221}
222
223// Protection for important (first partition) packets
224void ImportantPacketProtection(int num_fec_for_imp_packets, int num_imp_packets,
225                               int num_mask_bytes, uint8_t* packet_mask,
226                               const PacketMaskTable& mask_table) {
227  const int l_bit = num_imp_packets > 16 ? 1 : 0;
228  const int num_imp_mask_bytes =
229      (l_bit == 1) ? kMaskSizeLBitSet : kMaskSizeLBitClear;
230
231  // Get sub_mask1 from table
232  const uint8_t* packet_mask_sub_1 = mask_table.fec_packet_mask_table()[
233      num_imp_packets - 1][num_fec_for_imp_packets - 1];
234
235  FitSubMask(num_mask_bytes, num_imp_mask_bytes, num_fec_for_imp_packets,
236             packet_mask_sub_1, packet_mask);
237
238}
239
240// This function sets the protection allocation: i.e., how many FEC packets
241// to use for num_imp (1st partition) packets, given the: number of media
242// packets, number of FEC packets, and number of 1st partition packets.
243int SetProtectionAllocation(int num_media_packets, int num_fec_packets,
244                            int num_imp_packets) {
245
246  // TODO (marpan): test different cases for protection allocation:
247
248  // Use at most (alloc_par * num_fec_packets) for important packets.
249  float alloc_par = 0.5;
250  int max_num_fec_for_imp = alloc_par * num_fec_packets;
251
252  int num_fec_for_imp_packets =
253      (num_imp_packets < max_num_fec_for_imp) ? num_imp_packets
254                                              : max_num_fec_for_imp;
255
256  // Fall back to equal protection in this case
257  if (num_fec_packets == 1 && (num_media_packets > 2 * num_imp_packets)) {
258    num_fec_for_imp_packets = 0;
259  }
260
261  return num_fec_for_imp_packets;
262}
263
264// Modification for UEP: reuse the off-line tables for the packet masks.
265// Note: these masks were designed for equal packet protection case,
266// assuming random packet loss.
267
268// Current version has 3 modes (options) to build UEP mask from existing ones.
269// Various other combinations may be added in future versions.
270// Longer-term, we may add another set of tables specifically for UEP cases.
271// TODO (marpan): also consider modification of masks for bursty loss cases.
272
273// Mask is characterized as (#packets_to_protect, #fec_for_protection).
274// Protection factor defined as: (#fec_for_protection / #packets_to_protect).
275
276// Let k=num_media_packets, n=total#packets, (n-k)=num_fec_packets,
277// m=num_imp_packets.
278
279// For ProtectionMode 0 and 1:
280// one mask (sub_mask1) is used for 1st partition packets,
281// the other mask (sub_mask21/22, for 0/1) is for the remaining FEC packets.
282
283// In both mode 0 and 1, the packets of 1st partition (num_imp_packets) are
284// treated equally important, and are afforded more protection than the
285// residual partition packets.
286
287// For num_imp_packets:
288// sub_mask1 = (m, t): protection = t/(m), where t=F(k,n-k,m).
289// t=F(k,n-k,m) is the number of packets used to protect first partition in
290// sub_mask1. This is determined from the function SetProtectionAllocation().
291
292// For the left-over protection:
293// Mode 0: sub_mask21 = (k-m,n-k-t): protection = (n-k-t)/(k-m)
294// mode 0 has no protection overlap between the two partitions.
295// For mode 0, we would typically set t = min(m, n-k).
296
297// Mode 1: sub_mask22 = (k, n-k-t), with protection (n-k-t)/(k)
298// mode 1 has protection overlap between the two partitions (preferred).
299
300// For ProtectionMode 2:
301// This gives 1st packet of list (which is 1st packet of 1st partition) more
302// protection. In mode 2, the equal protection mask (which is obtained from
303// mode 1 for t=0) is modified (more "1s" added in 1st column of packet mask)
304// to bias higher protection for the 1st source packet.
305
306// Protection Mode 2 may be extended for a sort of sliding protection
307// (i.e., vary the number/density of "1s" across columns) across packets.
308
309void UnequalProtectionMask(int num_media_packets, int num_fec_packets,
310                           int num_imp_packets, int num_mask_bytes,
311                           uint8_t* packet_mask,
312                           const PacketMaskTable& mask_table) {
313
314  // Set Protection type and allocation
315  // TODO (marpan): test/update for best mode and some combinations thereof.
316
317  ProtectionMode mode = kModeOverlap;
318  int num_fec_for_imp_packets = 0;
319
320  if (mode != kModeBiasFirstPacket) {
321    num_fec_for_imp_packets = SetProtectionAllocation(
322        num_media_packets, num_fec_packets, num_imp_packets);
323  }
324
325  int num_fec_remaining = num_fec_packets - num_fec_for_imp_packets;
326  // Done with setting protection type and allocation
327
328  //
329  // Generate sub_mask1
330  //
331  if (num_fec_for_imp_packets > 0) {
332    ImportantPacketProtection(num_fec_for_imp_packets, num_imp_packets,
333                              num_mask_bytes, packet_mask, mask_table);
334  }
335
336  //
337  // Generate sub_mask2
338  //
339  if (num_fec_remaining > 0) {
340    RemainingPacketProtection(num_media_packets, num_fec_remaining,
341                              num_fec_for_imp_packets, num_mask_bytes, mode,
342                              packet_mask, mask_table);
343  }
344
345}
346
347void GeneratePacketMasks(int num_media_packets, int num_fec_packets,
348                         int num_imp_packets, bool use_unequal_protection,
349                         const PacketMaskTable& mask_table,
350                         uint8_t* packet_mask) {
351  assert(num_media_packets > 0);
352  assert(num_fec_packets <= num_media_packets && num_fec_packets > 0);
353  assert(num_imp_packets <= num_media_packets && num_imp_packets >= 0);
354
355  int l_bit = num_media_packets > 16 ? 1 : 0;
356  const int num_mask_bytes =
357      (l_bit == 1) ? kMaskSizeLBitSet : kMaskSizeLBitClear;
358
359  // Equal-protection for these cases.
360  if (!use_unequal_protection || num_imp_packets == 0) {
361    // Retrieve corresponding mask table directly:for equal-protection case.
362    // Mask = (k,n-k), with protection factor = (n-k)/k,
363    // where k = num_media_packets, n=total#packets, (n-k)=num_fec_packets.
364    memcpy(packet_mask, mask_table.fec_packet_mask_table()[
365                            num_media_packets - 1][num_fec_packets - 1],
366           num_fec_packets * num_mask_bytes);
367  } else  //UEP case
368      {
369    UnequalProtectionMask(num_media_packets, num_fec_packets, num_imp_packets,
370                          num_mask_bytes, packet_mask, mask_table);
371
372  }  // End of UEP modification
373}  //End of GetPacketMasks
374
375}  // namespace internal
376}  // namespace webrtc
Note: See TracBrowser for help on using the repository browser.