Line data Source code
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.
45 0 : 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 0 : if (num_mask_bytes == num_sub_mask_bytes) {
51 0 : memcpy(packet_mask, sub_mask, num_rows * num_sub_mask_bytes);
52 : } else {
53 0 : for (int i = 0; i < num_rows; ++i) {
54 0 : int pkt_mask_idx = i * num_mask_bytes;
55 0 : int pkt_mask_idx2 = i * num_sub_mask_bytes;
56 0 : for (int j = 0; j < num_sub_mask_bytes; ++j) {
57 0 : packet_mask[pkt_mask_idx] = sub_mask[pkt_mask_idx2];
58 0 : pkt_mask_idx++;
59 0 : pkt_mask_idx2++;
60 : }
61 : }
62 : }
63 0 : }
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.
84 0 : 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 0 : const int num_bit_shifts = (num_column_shift % 8);
92 0 : 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 0 : 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 0 : 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 0 : (i - num_column_shift) * res_mask_bytes + res_mask_bytes - 1;
105 :
106 0 : uint8_t shift_right_curr_byte = 0;
107 0 : uint8_t shift_left_prev_byte = 0;
108 0 : 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 0 : if (num_mask_bytes > res_mask_bytes) {
114 0 : shift_left_prev_byte = (sub_mask[pkt_mask_idx2] << (8 - num_bit_shifts));
115 0 : 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 0 : for (int j = res_mask_bytes - 1; j > 0; j--) {
122 : // Shift current byte of sub21 to the right by "numBitShifts".
123 0 : 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 0 : shift_left_prev_byte =
128 0 : (sub_mask[pkt_mask_idx2 - 1] << (8 - num_bit_shifts));
129 :
130 : // Then combine both shifted bytes into new mask byte.
131 0 : comb_new_byte = shift_right_curr_byte | shift_left_prev_byte;
132 :
133 : // Assign to new mask.
134 0 : packet_mask[pkt_mask_idx] = comb_new_byte;
135 0 : pkt_mask_idx--;
136 0 : pkt_mask_idx2--;
137 : }
138 : // For the first byte in the row (j=0 case).
139 0 : shift_right_curr_byte = sub_mask[pkt_mask_idx2] >> num_bit_shifts;
140 0 : packet_mask[pkt_mask_idx] = shift_right_curr_byte;
141 : }
142 0 : }
143 : } // namespace
144 :
145 : namespace webrtc {
146 : namespace internal {
147 :
148 0 : PacketMaskTable::PacketMaskTable(FecMaskType fec_mask_type,
149 0 : int num_media_packets)
150 0 : : fec_mask_type_(InitMaskType(fec_mask_type, num_media_packets)),
151 0 : 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.
157 0 : FecMaskType PacketMaskTable::InitMaskType(FecMaskType fec_mask_type,
158 : int num_media_packets) {
159 : // The mask should not be bigger than |packetMaskTbl|.
160 0 : assert(num_media_packets <= static_cast<int>(sizeof(kPacketMaskRandomTbl) /
161 0 : sizeof(*kPacketMaskRandomTbl)));
162 0 : switch (fec_mask_type) {
163 : case kFecMaskRandom: {
164 0 : return kFecMaskRandom;
165 : }
166 : case kFecMaskBursty: {
167 : int max_media_packets = static_cast<int>(sizeof(kPacketMaskBurstyTbl) /
168 0 : sizeof(*kPacketMaskBurstyTbl));
169 0 : if (num_media_packets > max_media_packets) {
170 0 : return kFecMaskRandom;
171 : } else {
172 0 : return kFecMaskBursty;
173 : }
174 : }
175 : }
176 0 : assert(false);
177 : return kFecMaskRandom;
178 : }
179 :
180 : // Returns the pointer to the packet mask tables corresponding to type
181 : // |fec_mask_type|.
182 0 : const uint8_t*** PacketMaskTable::InitMaskTable(FecMaskType fec_mask_type) {
183 0 : switch (fec_mask_type) {
184 : case kFecMaskRandom: {
185 0 : return kPacketMaskRandomTbl;
186 : }
187 : case kFecMaskBursty: {
188 0 : return kPacketMaskBurstyTbl;
189 : }
190 : }
191 0 : assert(false);
192 : return kPacketMaskRandomTbl;
193 : }
194 :
195 : // Remaining protection after important (first partition) packet protection
196 0 : 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 0 : if (mode == kModeNoOverlap) {
204 : // sub_mask21
205 :
206 : const int res_mask_bytes =
207 0 : PacketMaskSize(num_media_packets - num_fec_for_imp_packets);
208 :
209 : const uint8_t* packet_mask_sub_21 =
210 0 : mask_table.fec_packet_mask_table()[num_media_packets -
211 : num_fec_for_imp_packets -
212 0 : 1][num_fec_remaining - 1];
213 :
214 0 : ShiftFitSubMask(num_mask_bytes, res_mask_bytes, num_fec_for_imp_packets,
215 : (num_fec_for_imp_packets + num_fec_remaining),
216 0 : packet_mask_sub_21, packet_mask);
217 :
218 0 : } else if (mode == kModeOverlap || mode == kModeBiasFirstPacket) {
219 : // sub_mask22
220 :
221 : const uint8_t* packet_mask_sub_22 =
222 0 : mask_table.fec_packet_mask_table()[num_media_packets -
223 0 : 1][num_fec_remaining - 1];
224 :
225 0 : FitSubMask(num_mask_bytes, num_mask_bytes, num_fec_remaining,
226 : packet_mask_sub_22,
227 0 : &packet_mask[num_fec_for_imp_packets * num_mask_bytes]);
228 :
229 0 : if (mode == kModeBiasFirstPacket) {
230 0 : for (int i = 0; i < num_fec_remaining; ++i) {
231 0 : int pkt_mask_idx = i * num_mask_bytes;
232 0 : packet_mask[pkt_mask_idx] = packet_mask[pkt_mask_idx] | (1 << 7);
233 : }
234 0 : }
235 : } else {
236 0 : assert(false);
237 : }
238 0 : }
239 :
240 : // Protection for important (first partition) packets
241 0 : 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 0 : 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 0 : mask_table.fec_packet_mask_table()[num_imp_packets -
251 0 : 1][num_fec_for_imp_packets - 1];
252 :
253 : FitSubMask(num_mask_bytes, num_imp_mask_bytes, num_fec_for_imp_packets,
254 0 : packet_mask_sub_1, packet_mask);
255 0 : }
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.
260 0 : 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 0 : float alloc_par = 0.5;
267 0 : 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 0 : ? num_imp_packets
271 0 : : max_num_fec_for_imp;
272 :
273 : // Fall back to equal protection in this case
274 0 : if (num_fec_packets == 1 && (num_media_packets > 2 * num_imp_packets)) {
275 0 : num_fec_for_imp_packets = 0;
276 : }
277 :
278 0 : 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 :
326 0 : 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 0 : ProtectionMode mode = kModeOverlap;
336 0 : int num_fec_for_imp_packets = 0;
337 :
338 0 : if (mode != kModeBiasFirstPacket) {
339 : num_fec_for_imp_packets = SetProtectionAllocation(
340 0 : num_media_packets, num_fec_packets, num_imp_packets);
341 : }
342 :
343 0 : 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 0 : if (num_fec_for_imp_packets > 0) {
350 : ImportantPacketProtection(num_fec_for_imp_packets, num_imp_packets,
351 0 : num_mask_bytes, packet_mask, mask_table);
352 : }
353 :
354 : //
355 : // Generate sub_mask2
356 : //
357 0 : if (num_fec_remaining > 0) {
358 : RemainingPacketProtection(num_media_packets, num_fec_remaining,
359 : num_fec_for_imp_packets, num_mask_bytes, mode,
360 0 : packet_mask, mask_table);
361 : }
362 0 : }
363 :
364 0 : 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 0 : assert(num_media_packets > 0);
371 0 : assert(num_fec_packets <= num_media_packets && num_fec_packets > 0);
372 0 : assert(num_imp_packets <= num_media_packets && num_imp_packets >= 0);
373 :
374 0 : const int num_mask_bytes = PacketMaskSize(num_media_packets);
375 :
376 : // Equal-protection for these cases.
377 0 : 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 0 : memcpy(packet_mask,
382 0 : mask_table.fec_packet_mask_table()[num_media_packets -
383 0 : 1][num_fec_packets - 1],
384 0 : num_fec_packets * num_mask_bytes);
385 : } else { // UEP case
386 : UnequalProtectionMask(num_media_packets, num_fec_packets, num_imp_packets,
387 0 : num_mask_bytes, packet_mask, mask_table);
388 : } // End of UEP modification
389 0 : } // End of GetPacketMasks
390 :
391 0 : size_t PacketMaskSize(size_t num_sequence_numbers) {
392 0 : RTC_DCHECK_LE(num_sequence_numbers, 8 * kUlpfecPacketMaskSizeLBitSet);
393 0 : if (num_sequence_numbers > 8 * kUlpfecPacketMaskSizeLBitClear) {
394 0 : return kUlpfecPacketMaskSizeLBitSet;
395 : }
396 0 : return kUlpfecPacketMaskSizeLBitClear;
397 : }
398 :
399 0 : 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 0 : for (uint16_t row = 0; row < num_fec_packets; ++row) {
405 0 : const int new_byte_index = row * new_mask_bytes + new_bit_index / 8;
406 0 : const int max_shifts = (7 - (new_bit_index % 8));
407 0 : new_mask[new_byte_index] <<= std::min(num_zeros, max_shifts);
408 : }
409 0 : }
410 :
411 0 : 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 0 : for (uint16_t row = 0; row < num_fec_packets; ++row) {
421 0 : int new_byte_index = row * new_mask_bytes + new_bit_index / 8;
422 0 : int old_byte_index = row * old_mask_bytes + old_bit_index / 8;
423 0 : new_mask[new_byte_index] |= ((old_mask[old_byte_index] & 0x80) >> 7);
424 0 : if (new_bit_index % 8 != 7) {
425 0 : new_mask[new_byte_index] <<= 1;
426 : }
427 0 : old_mask[old_byte_index] <<= 1;
428 : }
429 0 : }
430 :
431 : } // namespace internal
432 : } // namespace webrtc
|
