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 <algorithm>
17
18 #include "webrtc/base/checks.h"
19 #include "webrtc/modules/rtp_rtcp/source/fec_private_tables_bursty.h"
20 #include "webrtc/modules/rtp_rtcp/source/fec_private_tables_random.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*** PacketMaskTable::InitMaskTable(FecMaskType fec_mask_type) {
183 switch (fec_mask_type) {
184 case kFecMaskRandom: {
185 return kPacketMaskRandomTbl;
186 }
187 case kFecMaskBursty: {
188 return kPacketMaskBurstyTbl;
189 }
190 }
191 assert(false);
192 return kPacketMaskRandomTbl;
193 }
194
195 // 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)196 void RemainingPacketProtection(int num_media_packets,
197 int num_fec_remaining,
198 int num_fec_for_imp_packets,
199 int num_mask_bytes,
200 ProtectionMode mode,
201 uint8_t* packet_mask,
202 const PacketMaskTable& mask_table) {
203 if (mode == kModeNoOverlap) {
204 // sub_mask21
205
206 const int res_mask_bytes =
207 PacketMaskSize(num_media_packets - num_fec_for_imp_packets);
208
209 const uint8_t* packet_mask_sub_21 =
210 mask_table.fec_packet_mask_table()[num_media_packets -
211 num_fec_for_imp_packets -
212 1][num_fec_remaining - 1];
213
214 ShiftFitSubMask(num_mask_bytes, res_mask_bytes, num_fec_for_imp_packets,
215 (num_fec_for_imp_packets + num_fec_remaining),
216 packet_mask_sub_21, packet_mask);
217
218 } else if (mode == kModeOverlap || mode == kModeBiasFirstPacket) {
219 // sub_mask22
220
221 const uint8_t* packet_mask_sub_22 =
222 mask_table.fec_packet_mask_table()[num_media_packets -
223 1][num_fec_remaining - 1];
224
225 FitSubMask(num_mask_bytes, num_mask_bytes, num_fec_remaining,
226 packet_mask_sub_22,
227 &packet_mask[num_fec_for_imp_packets * num_mask_bytes]);
228
229 if (mode == kModeBiasFirstPacket) {
230 for (int i = 0; i < num_fec_remaining; ++i) {
231 int pkt_mask_idx = i * num_mask_bytes;
232 packet_mask[pkt_mask_idx] = packet_mask[pkt_mask_idx] | (1 << 7);
233 }
234 }
235 } else {
236 assert(false);
237 }
238 }
239
240 // 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)241 void ImportantPacketProtection(int num_fec_for_imp_packets,
242 int num_imp_packets,
243 int num_mask_bytes,
244 uint8_t* packet_mask,
245 const PacketMaskTable& mask_table) {
246 const int num_imp_mask_bytes = PacketMaskSize(num_imp_packets);
247
248 // Get sub_mask1 from table
249 const uint8_t* packet_mask_sub_1 =
250 mask_table.fec_packet_mask_table()[num_imp_packets -
251 1][num_fec_for_imp_packets - 1];
252
253 FitSubMask(num_mask_bytes, num_imp_mask_bytes, num_fec_for_imp_packets,
254 packet_mask_sub_1, packet_mask);
255 }
256
257 // This function sets the protection allocation: i.e., how many FEC packets
258 // to use for num_imp (1st partition) packets, given the: number of media
259 // packets, number of FEC packets, and number of 1st partition packets.
SetProtectionAllocation(int num_media_packets,int num_fec_packets,int num_imp_packets)260 int SetProtectionAllocation(int num_media_packets,
261 int num_fec_packets,
262 int num_imp_packets) {
263 // TODO(marpan): test different cases for protection allocation:
264
265 // Use at most (alloc_par * num_fec_packets) for important packets.
266 float alloc_par = 0.5;
267 int max_num_fec_for_imp = alloc_par * num_fec_packets;
268
269 int num_fec_for_imp_packets = (num_imp_packets < max_num_fec_for_imp)
270 ? num_imp_packets
271 : max_num_fec_for_imp;
272
273 // Fall back to equal protection in this case
274 if (num_fec_packets == 1 && (num_media_packets > 2 * num_imp_packets)) {
275 num_fec_for_imp_packets = 0;
276 }
277
278 return num_fec_for_imp_packets;
279 }
280
281 // Modification for UEP: reuse the off-line tables for the packet masks.
282 // Note: these masks were designed for equal packet protection case,
283 // assuming random packet loss.
284
285 // Current version has 3 modes (options) to build UEP mask from existing ones.
286 // Various other combinations may be added in future versions.
287 // Longer-term, we may add another set of tables specifically for UEP cases.
288 // TODO(marpan): also consider modification of masks for bursty loss cases.
289
290 // Mask is characterized as (#packets_to_protect, #fec_for_protection).
291 // Protection factor defined as: (#fec_for_protection / #packets_to_protect).
292
293 // Let k=num_media_packets, n=total#packets, (n-k)=num_fec_packets,
294 // m=num_imp_packets.
295
296 // For ProtectionMode 0 and 1:
297 // one mask (sub_mask1) is used for 1st partition packets,
298 // the other mask (sub_mask21/22, for 0/1) is for the remaining FEC packets.
299
300 // In both mode 0 and 1, the packets of 1st partition (num_imp_packets) are
301 // treated equally important, and are afforded more protection than the
302 // residual partition packets.
303
304 // For num_imp_packets:
305 // sub_mask1 = (m, t): protection = t/(m), where t=F(k,n-k,m).
306 // t=F(k,n-k,m) is the number of packets used to protect first partition in
307 // sub_mask1. This is determined from the function SetProtectionAllocation().
308
309 // For the left-over protection:
310 // Mode 0: sub_mask21 = (k-m,n-k-t): protection = (n-k-t)/(k-m)
311 // mode 0 has no protection overlap between the two partitions.
312 // For mode 0, we would typically set t = min(m, n-k).
313
314 // Mode 1: sub_mask22 = (k, n-k-t), with protection (n-k-t)/(k)
315 // mode 1 has protection overlap between the two partitions (preferred).
316
317 // For ProtectionMode 2:
318 // This gives 1st packet of list (which is 1st packet of 1st partition) more
319 // protection. In mode 2, the equal protection mask (which is obtained from
320 // mode 1 for t=0) is modified (more "1s" added in 1st column of packet mask)
321 // to bias higher protection for the 1st source packet.
322
323 // Protection Mode 2 may be extended for a sort of sliding protection
324 // (i.e., vary the number/density of "1s" across columns) across packets.
325
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)326 void UnequalProtectionMask(int num_media_packets,
327 int num_fec_packets,
328 int num_imp_packets,
329 int num_mask_bytes,
330 uint8_t* packet_mask,
331 const PacketMaskTable& mask_table) {
332 // Set Protection type and allocation
333 // TODO(marpan): test/update for best mode and some combinations thereof.
334
335 ProtectionMode mode = kModeOverlap;
336 int num_fec_for_imp_packets = 0;
337
338 if (mode != kModeBiasFirstPacket) {
339 num_fec_for_imp_packets = SetProtectionAllocation(
340 num_media_packets, num_fec_packets, num_imp_packets);
341 }
342
343 int num_fec_remaining = num_fec_packets - num_fec_for_imp_packets;
344 // Done with setting protection type and allocation
345
346 //
347 // Generate sub_mask1
348 //
349 if (num_fec_for_imp_packets > 0) {
350 ImportantPacketProtection(num_fec_for_imp_packets, num_imp_packets,
351 num_mask_bytes, packet_mask, mask_table);
352 }
353
354 //
355 // Generate sub_mask2
356 //
357 if (num_fec_remaining > 0) {
358 RemainingPacketProtection(num_media_packets, num_fec_remaining,
359 num_fec_for_imp_packets, num_mask_bytes, mode,
360 packet_mask, mask_table);
361 }
362 }
363
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)364 void GeneratePacketMasks(int num_media_packets,
365 int num_fec_packets,
366 int num_imp_packets,
367 bool use_unequal_protection,
368 const PacketMaskTable& mask_table,
369 uint8_t* packet_mask) {
370 assert(num_media_packets > 0);
371 assert(num_fec_packets <= num_media_packets && num_fec_packets > 0);
372 assert(num_imp_packets <= num_media_packets && num_imp_packets >= 0);
373
374 const int num_mask_bytes = PacketMaskSize(num_media_packets);
375
376 // Equal-protection for these cases.
377 if (!use_unequal_protection || num_imp_packets == 0) {
378 // Retrieve corresponding mask table directly:for equal-protection case.
379 // Mask = (k,n-k), with protection factor = (n-k)/k,
380 // where k = num_media_packets, n=total#packets, (n-k)=num_fec_packets.
381 memcpy(packet_mask,
382 mask_table.fec_packet_mask_table()[num_media_packets -
383 1][num_fec_packets - 1],
384 num_fec_packets * num_mask_bytes);
385 } else { // UEP case
386 UnequalProtectionMask(num_media_packets, num_fec_packets, num_imp_packets,
387 num_mask_bytes, packet_mask, mask_table);
388 } // End of UEP modification
389 } // End of GetPacketMasks
390
PacketMaskSize(size_t num_sequence_numbers)391 size_t PacketMaskSize(size_t num_sequence_numbers) {
392 RTC_DCHECK_LE(num_sequence_numbers, 8 * kUlpfecPacketMaskSizeLBitSet);
393 if (num_sequence_numbers > 8 * kUlpfecPacketMaskSizeLBitClear) {
394 return kUlpfecPacketMaskSizeLBitSet;
395 }
396 return kUlpfecPacketMaskSizeLBitClear;
397 }
398
InsertZeroColumns(int num_zeros,uint8_t * new_mask,int new_mask_bytes,int num_fec_packets,int new_bit_index)399 void InsertZeroColumns(int num_zeros,
400 uint8_t* new_mask,
401 int new_mask_bytes,
402 int num_fec_packets,
403 int new_bit_index) {
404 for (uint16_t row = 0; row < num_fec_packets; ++row) {
405 const int new_byte_index = row * new_mask_bytes + new_bit_index / 8;
406 const int max_shifts = (7 - (new_bit_index % 8));
407 new_mask[new_byte_index] <<= std::min(num_zeros, max_shifts);
408 }
409 }
410
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)411 void CopyColumn(uint8_t* new_mask,
412 int new_mask_bytes,
413 uint8_t* old_mask,
414 int old_mask_bytes,
415 int num_fec_packets,
416 int new_bit_index,
417 int old_bit_index) {
418 // Copy column from the old mask to the beginning of the new mask and shift it
419 // out from the old mask.
420 for (uint16_t row = 0; row < num_fec_packets; ++row) {
421 int new_byte_index = row * new_mask_bytes + new_bit_index / 8;
422 int old_byte_index = row * old_mask_bytes + old_bit_index / 8;
423 new_mask[new_byte_index] |= ((old_mask[old_byte_index] & 0x80) >> 7);
424 if (new_bit_index % 8 != 7) {
425 new_mask[new_byte_index] <<= 1;
426 }
427 old_mask[old_byte_index] <<= 1;
428 }
429 }
430
431 } // namespace internal
432 } // namespace webrtc
433