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