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