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 /*
12  * The purpose of this test is to compute metrics to characterize the properties
13  * and efficiency of the packets masks used in the generic XOR FEC code.
14  *
15  * The metrics measure the efficiency (recovery potential or residual loss) of
16  * the FEC code, under various statistical loss models for the packet/symbol
17  * loss events. Various constraints on the behavior of these metrics are
18  * verified, and compared to the reference RS (Reed-Solomon) code. This serves
19  * in some way as a basic check/benchmark for the packet masks.
20  *
21  * By an FEC code, we mean an erasure packet/symbol code, characterized by:
22  * (1) The code size parameters (k,m), where k = number of source/media packets,
23  * and m = number of FEC packets,
24  * (2) The code type: XOR or RS.
25  * In the case of XOR, the residual loss is determined via the set of packet
26  * masks (generator matrix). In the case of RS, the residual loss is determined
27  * directly from the MDS (maximum distance separable) property of RS.
28  *
29  * Currently two classes of packets masks are available (random type and bursty
30  * type), so three codes are considered below: RS, XOR-random, and XOR-bursty.
31  * The bursty class is defined up to k=12, so (k=12,m=12) is largest code size
32  * considered in this test.
33  *
34  * The XOR codes are defined via the RFC 5109 and correspond to the class of
35  * LDGM (low density generator matrix) codes, which is a subset of the LDPC
36  * (low density parity check) codes. Future implementation will consider
37  * extending our XOR codes to include LDPC codes, which explicitly include
38  * protection of FEC packets.
39  *
40  * The type of packet/symbol loss models considered in this test are:
41  * (1) Random loss: Bernoulli process, characterized by the average loss rate.
42  * (2) Bursty loss: Markov chain (Gilbert-Elliot model), characterized by two
43  * parameters: average loss rate and average burst length.
44 */
45 
46 #include <math.h>
47 
48 #include "testing/gtest/include/gtest/gtest.h"
49 #include "webrtc/base/scoped_ptr.h"
50 #include "webrtc/modules/rtp_rtcp/source/forward_error_correction_internal.h"
51 #include "webrtc/modules/rtp_rtcp/test/testFec/average_residual_loss_xor_codes.h"
52 #include "webrtc/test/testsupport/fileutils.h"
53 
54 namespace webrtc {
55 
56 // Maximum number of media packets allows for XOR (RFC 5109) code.
57 enum { kMaxNumberMediaPackets = 48 };
58 
59 // Maximum number of media packets allowed for each mask type.
60 const uint16_t kMaxMediaPackets[] = {kMaxNumberMediaPackets, 12};
61 
62 // Maximum gap size for characterizing the consecutiveness of the loss.
63 const int kMaxGapSize = 2 * kMaxMediaPacketsTest;
64 
65 // Number of gap levels written to file/output.
66 const int kGapSizeOutput = 5;
67 
68 // Maximum number of states for characterizing the residual loss distribution.
69 const int kNumStatesDistribution = 2 * kMaxMediaPacketsTest * kMaxGapSize + 1;
70 
71 // The code type.
72 enum CodeType {
73   xor_random_code,    // XOR with random mask type.
74   xor_bursty_code,    // XOR with bursty mask type.
75   rs_code             // Reed_solomon.
76 };
77 
78 // The code size parameters.
79 struct CodeSizeParams {
80   int num_media_packets;
81   int num_fec_packets;
82   // Protection level: num_fec_packets / (num_media_packets + num_fec_packets).
83   float protection_level;
84   // Number of loss configurations, for a given loss number and gap number.
85   // The gap number refers to the maximum gap/hole of a loss configuration
86   // (used to measure the "consecutiveness" of the loss).
87   int configuration_density[kNumStatesDistribution];
88 };
89 
90 // The type of loss models.
91 enum LossModelType {
92   kRandomLossModel,
93   kBurstyLossModel
94 };
95 
96 struct LossModel {
97   LossModelType loss_type;
98   float average_loss_rate;
99   float average_burst_length;
100 };
101 
102 // Average loss rates.
103 const float kAverageLossRate[] = { 0.025f, 0.05f, 0.1f, 0.25f };
104 
105 // Average burst lengths. The case of |kAverageBurstLength = 1.0| refers to
106 // the random model. Note that for the random (Bernoulli) model, the average
107 // burst length is determined by the average loss rate, i.e.,
108 // AverageBurstLength = 1 / (1 - AverageLossRate) for random model.
109 const float kAverageBurstLength[] = { 1.0f, 2.0f, 4.0f };
110 
111 // Total number of loss models: For each burst length case, there are
112 // a number of models corresponding to the loss rates.
113 const int kNumLossModels =  (sizeof(kAverageBurstLength) /
114     sizeof(*kAverageBurstLength)) * (sizeof(kAverageLossRate) /
115         sizeof(*kAverageLossRate));
116 
117 // Thresholds on the average loss rate of the packet loss model, below which
118 // certain properties of the codes are expected.
119 float loss_rate_upper_threshold = 0.20f;
120 float loss_rate_lower_threshold = 0.025f;
121 
122 // Set of thresholds on the expected average recovery rate, for each code type.
123 // These are global thresholds for now; in future version we may condition them
124 // on the code length/size and protection level.
125 const float kRecoveryRateXorRandom[3] = { 0.94f, 0.50f, 0.19f };
126 const float kRecoveryRateXorBursty[3] = { 0.90f, 0.54f, 0.22f };
127 
128 // Metrics for a given FEC code; each code is defined by the code type
129 // (RS, XOR-random/bursty), and the code size parameters (k,m), where
130 // k = num_media_packets, m = num_fec_packets.
131 struct MetricsFecCode {
132   // The average and variance of the residual loss, as a function of the
133   // packet/symbol loss model. The average/variance is computed by averaging
134   // over all loss configurations wrt the loss probability given by the
135   // underlying loss model.
136   double average_residual_loss[kNumLossModels];
137   double variance_residual_loss[kNumLossModels];
138   // The residual loss, as a function of the loss number and the gap number of
139   // the loss configurations. The gap number refers to the maximum gap/hole of
140   // a loss configuration (used to measure the "consecutiveness" of the loss).
141   double residual_loss_per_loss_gap[kNumStatesDistribution];
142   // The recovery rate as a function of the loss number.
143   double recovery_rate_per_loss[2 * kMaxMediaPacketsTest + 1];
144 };
145 
146 MetricsFecCode kMetricsXorRandom[kNumberCodes];
147 MetricsFecCode kMetricsXorBursty[kNumberCodes];
148 MetricsFecCode kMetricsReedSolomon[kNumberCodes];
149 
150 class FecPacketMaskMetricsTest : public ::testing::Test {
151  protected:
FecPacketMaskMetricsTest()152   FecPacketMaskMetricsTest() { }
153 
154   int max_num_codes_;
155   LossModel loss_model_[kNumLossModels];
156   CodeSizeParams code_params_[kNumberCodes];
157 
158   uint8_t fec_packet_masks_[kMaxNumberMediaPackets][kMaxNumberMediaPackets];
159   FILE* fp_mask_;
160 
161   // Measure of the gap of the loss for configuration given by |state|.
162   // This is to measure degree of consecutiveness for the loss configuration.
163   // Useful if the packets are sent out in order of sequence numbers and there
164   // is little/no re-ordering during transmission.
GapLoss(int tot_num_packets,uint8_t * state)165   int GapLoss(int tot_num_packets, uint8_t* state) {
166     int max_gap_loss = 0;
167     // Find the first loss.
168     int first_loss = 0;
169     for (int i = 0; i < tot_num_packets; i++) {
170       if (state[i] == 1) {
171         first_loss = i;
172         break;
173       }
174     }
175     int prev_loss = first_loss;
176     for (int i = first_loss + 1; i < tot_num_packets; i++) {
177       if (state[i] == 1) {  // Lost state.
178         int gap_loss = (i - prev_loss) - 1;
179         if (gap_loss > max_gap_loss) {
180           max_gap_loss = gap_loss;
181         }
182         prev_loss = i;
183       }
184     }
185     return max_gap_loss;
186   }
187 
188   // Returns the number of recovered media packets for the XOR code, given the
189   // packet mask |fec_packet_masks_|, for the loss state/configuration given by
190   // |state|.
RecoveredMediaPackets(int num_media_packets,int num_fec_packets,uint8_t * state)191   int RecoveredMediaPackets(int num_media_packets,
192                             int num_fec_packets,
193                             uint8_t* state) {
194     rtc::scoped_ptr<uint8_t[]> state_tmp(
195         new uint8_t[num_media_packets + num_fec_packets]);
196     memcpy(state_tmp.get(), state, num_media_packets + num_fec_packets);
197     int num_recovered_packets = 0;
198     bool loop_again = true;
199     while (loop_again) {
200       loop_again = false;
201       bool recovered_new_packet = false;
202       // Check if we can recover anything: loop over all possible FEC packets.
203       for (int i = 0; i < num_fec_packets; i++) {
204         if (state_tmp[i + num_media_packets] == 0) {
205           // We have this FEC packet.
206           int num_packets_in_mask = 0;
207           int num_received_packets_in_mask = 0;
208           for (int j = 0; j < num_media_packets; j++) {
209             if (fec_packet_masks_[i][j] == 1) {
210               num_packets_in_mask++;
211               if (state_tmp[j] == 0) {
212                 num_received_packets_in_mask++;
213               }
214             }
215           }
216           if ((num_packets_in_mask - 1) == num_received_packets_in_mask) {
217             // We can recover the missing media packet for this FEC packet.
218             num_recovered_packets++;
219             recovered_new_packet = true;
220             int jsel = -1;
221             int check_num_recovered = 0;
222             // Update the state with newly recovered media packet.
223             for (int j = 0; j < num_media_packets; j++) {
224               if (fec_packet_masks_[i][j] == 1 && state_tmp[j] == 1) {
225                 // This is the lost media packet we will recover.
226                 jsel = j;
227                 check_num_recovered++;
228               }
229             }
230             // Check that we can only recover 1 packet.
231             assert(check_num_recovered == 1);
232             // Update the state with the newly recovered media packet.
233             state_tmp[jsel] = 0;
234           }
235         }
236       }  // Go to the next FEC packet in the loop.
237       // If we have recovered at least one new packet in this FEC loop,
238       // go through loop again, otherwise we leave loop.
239       if (recovered_new_packet) {
240         loop_again = true;
241       }
242     }
243     return num_recovered_packets;
244   }
245 
246   // Compute the probability of occurence of the loss state/configuration,
247   // given by |state|, for all the loss models considered in this test.
ComputeProbabilityWeight(double * prob_weight,uint8_t * state,int tot_num_packets)248   void ComputeProbabilityWeight(double* prob_weight,
249                                 uint8_t* state,
250                                 int tot_num_packets) {
251     // Loop over the loss models.
252     for (int k = 0; k < kNumLossModels; k++) {
253       double loss_rate = static_cast<double>(
254           loss_model_[k].average_loss_rate);
255       double burst_length = static_cast<double>(
256           loss_model_[k].average_burst_length);
257       double result = 1.0;
258       if (loss_model_[k].loss_type == kRandomLossModel) {
259         for (int i = 0; i < tot_num_packets; i++) {
260           if (state[i] == 0) {
261             result *= (1.0 - loss_rate);
262           } else {
263             result *= loss_rate;
264           }
265         }
266       } else {  // Gilbert-Elliot model for burst model.
267         assert(loss_model_[k].loss_type == kBurstyLossModel);
268         // Transition probabilities: from previous to current state.
269         // Prob. of previous = lost --> current = received.
270         double prob10 = 1.0 / burst_length;
271         // Prob. of previous = lost --> currrent = lost.
272         double prob11 = 1.0 - prob10;
273         // Prob. of previous = received --> current = lost.
274         double prob01 = prob10 * (loss_rate / (1.0 - loss_rate));
275         // Prob. of previous = received --> current = received.
276         double prob00 = 1.0 - prob01;
277 
278         // Use stationary probability for first state/packet.
279         if (state[0] == 0) {  // Received
280           result = (1.0 - loss_rate);
281         } else {   // Lost
282           result = loss_rate;
283         }
284 
285         // Subsequent states: use transition probabilities.
286         for (int i = 1; i < tot_num_packets; i++) {
287           // Current state is received
288           if (state[i] == 0) {
289             if (state[i-1] == 0) {
290               result *= prob00;   // Previous received, current received.
291               } else {
292                 result *= prob10;  // Previous lost, current received.
293               }
294           } else {  // Current state is lost
295             if (state[i-1] == 0) {
296               result *= prob01;  // Previous received, current lost.
297             } else {
298               result *= prob11;  // Previous lost, current lost.
299             }
300           }
301         }
302       }
303       prob_weight[k] = result;
304     }
305   }
306 
CopyMetrics(MetricsFecCode * metrics_output,MetricsFecCode metrics_input)307   void CopyMetrics(MetricsFecCode* metrics_output,
308                    MetricsFecCode metrics_input) {
309     memcpy(metrics_output->average_residual_loss,
310            metrics_input.average_residual_loss,
311            sizeof(double) * kNumLossModels);
312     memcpy(metrics_output->variance_residual_loss,
313            metrics_input.variance_residual_loss,
314            sizeof(double) * kNumLossModels);
315     memcpy(metrics_output->residual_loss_per_loss_gap,
316            metrics_input.residual_loss_per_loss_gap,
317            sizeof(double) * kNumStatesDistribution);
318     memcpy(metrics_output->recovery_rate_per_loss,
319            metrics_input.recovery_rate_per_loss,
320            sizeof(double) * 2 * kMaxMediaPacketsTest);
321   }
322 
323   // Compute the residual loss per gap, by summing the
324   // |residual_loss_per_loss_gap| over all loss configurations up to loss number
325   // = |num_fec_packets|.
ComputeResidualLossPerGap(MetricsFecCode metrics,int gap_number,int num_fec_packets,int code_index)326   double ComputeResidualLossPerGap(MetricsFecCode metrics,
327                                    int gap_number,
328                                    int num_fec_packets,
329                                    int code_index) {
330     double residual_loss_gap = 0.0;
331     int tot_num_configs = 0;
332     for (int loss = 1; loss <= num_fec_packets; loss++) {
333       int index = gap_number * (2 * kMaxMediaPacketsTest) + loss;
334       residual_loss_gap += metrics.residual_loss_per_loss_gap[index];
335       tot_num_configs +=
336           code_params_[code_index].configuration_density[index];
337     }
338     // Normalize, to compare across code sizes.
339     if (tot_num_configs > 0) {
340       residual_loss_gap = residual_loss_gap /
341           static_cast<double>(tot_num_configs);
342     }
343     return residual_loss_gap;
344   }
345 
346   // Compute the recovery rate per loss number, by summing the
347   // |residual_loss_per_loss_gap| over all gap configurations.
ComputeRecoveryRatePerLoss(MetricsFecCode * metrics,int num_media_packets,int num_fec_packets,int code_index)348   void ComputeRecoveryRatePerLoss(MetricsFecCode* metrics,
349                                   int num_media_packets,
350                                   int num_fec_packets,
351                                   int code_index) {
352     for (int loss = 1; loss <= num_media_packets + num_fec_packets; loss++) {
353       metrics->recovery_rate_per_loss[loss] = 0.0;
354       int tot_num_configs = 0;
355       double arl = 0.0;
356       for (int gap = 0; gap < kMaxGapSize; gap ++) {
357         int index = gap * (2 * kMaxMediaPacketsTest) + loss;
358         arl += metrics->residual_loss_per_loss_gap[index];
359         tot_num_configs +=
360             code_params_[code_index].configuration_density[index];
361       }
362       // Normalize, to compare across code sizes.
363       if (tot_num_configs > 0) {
364         arl = arl / static_cast<double>(tot_num_configs);
365       }
366       // Recovery rate for a given loss |loss| is 1 minus the scaled |arl|,
367       // where the scale factor is relative to code size/parameters.
368       double scaled_loss = static_cast<double>(loss * num_media_packets) /
369           static_cast<double>(num_media_packets + num_fec_packets);
370       metrics->recovery_rate_per_loss[loss] = 1.0 - arl / scaled_loss;
371     }
372   }
373 
SetMetricsZero(MetricsFecCode * metrics)374   void SetMetricsZero(MetricsFecCode* metrics) {
375     memset(metrics->average_residual_loss, 0, sizeof(double) * kNumLossModels);
376     memset(metrics->variance_residual_loss, 0, sizeof(double) * kNumLossModels);
377     memset(metrics->residual_loss_per_loss_gap, 0,
378            sizeof(double) * kNumStatesDistribution);
379     memset(metrics->recovery_rate_per_loss, 0,
380            sizeof(double) * 2 * kMaxMediaPacketsTest + 1);
381   }
382 
383   // Compute the metrics for an FEC code, given by the code type |code_type|
384   // (XOR-random/ bursty or RS), and by the code index |code_index|
385   // (which containes the code size parameters/protection length).
ComputeMetricsForCode(CodeType code_type,int code_index)386   void ComputeMetricsForCode(CodeType code_type,
387                              int code_index) {
388     rtc::scoped_ptr<double[]> prob_weight(new double[kNumLossModels]);
389     memset(prob_weight.get() , 0, sizeof(double) * kNumLossModels);
390     MetricsFecCode metrics_code;
391     SetMetricsZero(&metrics_code);
392 
393     int num_media_packets = code_params_[code_index].num_media_packets;
394     int num_fec_packets = code_params_[code_index].num_fec_packets;
395     int tot_num_packets = num_media_packets + num_fec_packets;
396     rtc::scoped_ptr<uint8_t[]> state(new uint8_t[tot_num_packets]);
397     memset(state.get() , 0, tot_num_packets);
398 
399     int num_loss_configurations = static_cast<int>(pow(2.0f, tot_num_packets));
400     // Loop over all loss configurations for the symbol sequence of length
401     // |tot_num_packets|. In this version we process up to (k=12, m=12) codes,
402     // and get exact expressions for the residual loss.
403     // TODO(marpan): For larger codes, loop over some random sample of loss
404     // configurations, sampling driven by the underlying statistical loss model
405     // (importance sampling).
406 
407     // The symbols/packets are arranged as a sequence of source/media packets
408     // followed by FEC packets. This is the sequence ordering used in the RTP.
409     // A configuration refers to a sequence of received/lost (0/1 bit) states
410     // for the string of packets/symbols. For example, for a (k=4,m=3) code
411     // (4 media packets, 3 FEC packets), with 2 losses (one media and one FEC),
412     // the loss configurations is:
413     // Media1   Media2   Media3   Media4   FEC1   FEC2   FEC3
414     //   0         0        1       0        0      1     0
415     for (int i = 1; i < num_loss_configurations; i++) {
416       // Counter for number of packets lost.
417       int num_packets_lost = 0;
418       // Counters for the number of media packets lost.
419       int num_media_packets_lost = 0;
420 
421       // Map configuration number to a loss state.
422       for (int j = 0; j < tot_num_packets; j++) {
423         state[j] = 0;  // Received state.
424         int bit_value = i >> (tot_num_packets - j - 1) & 1;
425         if (bit_value == 1) {
426           state[j] = 1;  // Lost state.
427           num_packets_lost++;
428            if (j < num_media_packets) {
429              num_media_packets_lost++;
430            }
431         }
432       }  // Done with loop over total number of packets.
433       assert(num_media_packets_lost <= num_media_packets);
434       assert(num_packets_lost <= tot_num_packets && num_packets_lost > 0);
435       double residual_loss = 0.0;
436       // Only need to compute residual loss (number of recovered packets) for
437       // configurations that have at least one media packet lost.
438       if (num_media_packets_lost >= 1) {
439         // Compute the number of recovered packets.
440         int num_recovered_packets = 0;
441         if (code_type == xor_random_code || code_type == xor_bursty_code) {
442           num_recovered_packets = RecoveredMediaPackets(num_media_packets,
443                                                         num_fec_packets,
444                                                         state.get());
445         } else {
446           // For the RS code, we can either completely recover all the packets
447           // if the loss is less than or equal to the number of FEC packets,
448           // otherwise we can recover none of the missing packets. This is the
449           // all or nothing (MDS) property of the RS code.
450           if (num_packets_lost <= num_fec_packets) {
451             num_recovered_packets = num_media_packets_lost;
452           }
453         }
454         assert(num_recovered_packets <= num_media_packets);
455         // Compute the residual loss. We only care about recovering media/source
456         // packets, so residual loss is based on lost/recovered media packets.
457         residual_loss = static_cast<double>(num_media_packets_lost -
458                                             num_recovered_packets);
459         // Compute the probability weights for this configuration.
460         ComputeProbabilityWeight(prob_weight.get(),
461                                  state.get(),
462                                  tot_num_packets);
463         // Update the average and variance of the residual loss.
464         for (int k = 0; k < kNumLossModels; k++) {
465           metrics_code.average_residual_loss[k] += residual_loss *
466               prob_weight[k];
467           metrics_code.variance_residual_loss[k] += residual_loss *
468               residual_loss * prob_weight[k];
469         }
470       }  // Done with processing for num_media_packets_lost >= 1.
471       // Update the distribution statistics.
472       // Compute the gap of the loss (the "consecutiveness" of the loss).
473       int gap_loss = GapLoss(tot_num_packets, state.get());
474       assert(gap_loss < kMaxGapSize);
475       int index = gap_loss * (2 * kMaxMediaPacketsTest) + num_packets_lost;
476       assert(index < kNumStatesDistribution);
477       metrics_code.residual_loss_per_loss_gap[index] += residual_loss;
478       if (code_type == xor_random_code) {
479         // The configuration density is only a function of the code length and
480         // only needs to computed for the first |code_type| passed here.
481         code_params_[code_index].configuration_density[index]++;
482       }
483     }  // Done with loop over configurations.
484     // Normalize the average residual loss and compute/normalize the variance.
485     for (int k = 0; k < kNumLossModels; k++) {
486       // Normalize the average residual loss by the total number of packets
487       // |tot_num_packets| (i.e., the code length). For a code with no (zero)
488       // recovery, the average residual loss for that code would be reduced like
489       // ~|average_loss_rate| * |num_media_packets| / |tot_num_packets|. This is
490       // the expected reduction in the average residual loss just from adding
491       // FEC packets to the symbol sequence.
492       metrics_code.average_residual_loss[k] =
493           metrics_code.average_residual_loss[k] /
494           static_cast<double>(tot_num_packets);
495       metrics_code.variance_residual_loss[k] =
496                metrics_code.variance_residual_loss[k] /
497                static_cast<double>(num_media_packets * num_media_packets);
498       metrics_code.variance_residual_loss[k] =
499           metrics_code.variance_residual_loss[k] -
500           (metrics_code.average_residual_loss[k] *
501               metrics_code.average_residual_loss[k]);
502       assert(metrics_code.variance_residual_loss[k] >= 0.0);
503       assert(metrics_code.average_residual_loss[k] > 0.0);
504       metrics_code.variance_residual_loss[k] =
505           sqrt(metrics_code.variance_residual_loss[k]) /
506           metrics_code.average_residual_loss[k];
507     }
508 
509     // Compute marginal distribution as a function of loss parameter.
510     ComputeRecoveryRatePerLoss(&metrics_code,
511                                num_media_packets,
512                                num_fec_packets,
513                                code_index);
514     if (code_type == rs_code) {
515       CopyMetrics(&kMetricsReedSolomon[code_index], metrics_code);
516     } else if (code_type == xor_random_code) {
517       CopyMetrics(&kMetricsXorRandom[code_index], metrics_code);
518     } else if (code_type == xor_bursty_code) {
519       CopyMetrics(&kMetricsXorBursty[code_index], metrics_code);
520     } else {
521       assert(false);
522     }
523   }
524 
WriteOutMetricsAllFecCodes()525   void WriteOutMetricsAllFecCodes()  {
526     std::string filename = test::OutputPath() + "data_metrics_all_codes";
527     FILE* fp = fopen(filename.c_str(), "wb");
528     // Loop through codes up to |kMaxMediaPacketsTest|.
529     int code_index = 0;
530     for (int num_media_packets = 1; num_media_packets <= kMaxMediaPacketsTest;
531         num_media_packets++) {
532       for (int num_fec_packets = 1; num_fec_packets <= num_media_packets;
533           num_fec_packets++) {
534         fprintf(fp, "FOR CODE: (%d, %d) \n", num_media_packets,
535                 num_fec_packets);
536         for (int k = 0; k < kNumLossModels; k++) {
537           float loss_rate = loss_model_[k].average_loss_rate;
538           float burst_length = loss_model_[k].average_burst_length;
539           fprintf(fp, "Loss rate = %.2f, Burst length = %.2f:  %.4f  %.4f  %.4f"
540               " **** %.4f %.4f %.4f \n",
541               loss_rate,
542               burst_length,
543               100 * kMetricsReedSolomon[code_index].average_residual_loss[k],
544               100 * kMetricsXorRandom[code_index].average_residual_loss[k],
545               100 * kMetricsXorBursty[code_index].average_residual_loss[k],
546               kMetricsReedSolomon[code_index].variance_residual_loss[k],
547               kMetricsXorRandom[code_index].variance_residual_loss[k],
548               kMetricsXorBursty[code_index].variance_residual_loss[k]);
549         }
550         for (int gap = 0; gap < kGapSizeOutput; gap ++) {
551           double rs_residual_loss = ComputeResidualLossPerGap(
552               kMetricsReedSolomon[code_index],
553               gap,
554               num_fec_packets,
555               code_index);
556           double xor_random_residual_loss = ComputeResidualLossPerGap(
557               kMetricsXorRandom[code_index],
558               gap,
559               num_fec_packets,
560               code_index);
561           double xor_bursty_residual_loss = ComputeResidualLossPerGap(
562               kMetricsXorBursty[code_index],
563               gap,
564               num_fec_packets,
565               code_index);
566           fprintf(fp, "Residual loss as a function of gap "
567               "%d: %.4f %.4f %.4f \n",
568               gap,
569               rs_residual_loss,
570               xor_random_residual_loss,
571               xor_bursty_residual_loss);
572         }
573         fprintf(fp, "Recovery rate as a function of loss number \n");
574         for (int loss = 1; loss <= num_media_packets + num_fec_packets;
575                      loss ++) {
576           fprintf(fp, "For loss number %d: %.4f %.4f %.4f \n",
577                   loss,
578                   kMetricsReedSolomon[code_index].
579                   recovery_rate_per_loss[loss],
580                   kMetricsXorRandom[code_index].
581                   recovery_rate_per_loss[loss],
582                   kMetricsXorBursty[code_index].
583                   recovery_rate_per_loss[loss]);
584         }
585         fprintf(fp, "******************\n");
586         fprintf(fp, "\n");
587         code_index++;
588       }
589     }
590     fclose(fp);
591   }
592 
SetLossModels()593   void SetLossModels() {
594     int num_loss_rates = sizeof(kAverageLossRate) /
595         sizeof(*kAverageLossRate);
596     int num_burst_lengths = sizeof(kAverageBurstLength) /
597         sizeof(*kAverageBurstLength);
598     int num_loss_models = 0;
599     for (int k = 0; k < num_burst_lengths; k++) {
600       for (int k2 = 0; k2 < num_loss_rates; k2++) {
601         loss_model_[num_loss_models].average_loss_rate = kAverageLossRate[k2];
602         loss_model_[num_loss_models].average_burst_length =
603             kAverageBurstLength[k];
604         // First set of loss models are of random type.
605         if (k == 0) {
606           loss_model_[num_loss_models].loss_type = kRandomLossModel;
607         } else {
608           loss_model_[num_loss_models].loss_type = kBurstyLossModel;
609         }
610         num_loss_models++;
611       }
612     }
613     assert(num_loss_models == kNumLossModels);
614   }
615 
SetCodeParams()616   void SetCodeParams() {
617     int code_index = 0;
618     for (int num_media_packets = 1; num_media_packets <= kMaxMediaPacketsTest;
619         num_media_packets++) {
620       for (int num_fec_packets = 1; num_fec_packets <= num_media_packets;
621           num_fec_packets++) {
622         code_params_[code_index].num_media_packets = num_media_packets;
623         code_params_[code_index].num_fec_packets = num_fec_packets;
624         code_params_[code_index].protection_level =
625             static_cast<float>(num_fec_packets) /
626             static_cast<float>(num_media_packets + num_fec_packets);
627         for (int k = 0; k < kNumStatesDistribution; k++) {
628           code_params_[code_index].configuration_density[k] = 0;
629         }
630         code_index++;
631       }
632     }
633     max_num_codes_ = code_index;
634   }
635 
636   // Make some basic checks on the packet masks. Return -1 if any of these
637   // checks fail.
RejectInvalidMasks(int num_media_packets,int num_fec_packets)638   int RejectInvalidMasks(int num_media_packets, int num_fec_packets) {
639     // Make sure every FEC packet protects something.
640     for (int i = 0; i < num_fec_packets; i++) {
641       int row_degree = 0;
642       for (int j = 0; j < num_media_packets; j++) {
643         if (fec_packet_masks_[i][j] == 1) {
644           row_degree++;
645         }
646       }
647       if (row_degree == 0) {
648         printf("Invalid mask: FEC packet has empty mask (does not protect "
649             "anything) %d %d %d \n", i, num_media_packets, num_fec_packets);
650         return -1;
651       }
652     }
653     // Mask sure every media packet has some protection.
654     for (int j = 0; j < num_media_packets; j++) {
655       int column_degree = 0;
656       for (int i = 0; i < num_fec_packets; i++) {
657         if (fec_packet_masks_[i][j] == 1) {
658           column_degree++;
659         }
660       }
661       if (column_degree == 0) {
662         printf("Invalid mask: Media packet has no protection at all %d %d %d "
663             "\n", j, num_media_packets, num_fec_packets);
664         return -1;
665       }
666     }
667     // Make sure we do not have two identical FEC packets.
668     for (int i = 0; i < num_fec_packets; i++) {
669       for (int i2 = i + 1; i2 < num_fec_packets; i2++) {
670         int overlap = 0;
671         for (int j = 0; j < num_media_packets; j++) {
672           if (fec_packet_masks_[i][j] == fec_packet_masks_[i2][j]) {
673             overlap++;
674           }
675         }
676         if (overlap == num_media_packets) {
677           printf("Invalid mask: Two FEC packets are identical %d %d %d %d \n",
678                  i, i2, num_media_packets, num_fec_packets);
679           return -1;
680         }
681       }
682     }
683     // Avoid codes that have two media packets with full protection (all 1s in
684     // their corresponding columns). This would mean that if we lose those
685     // two packets, we can never recover them even if we receive all the other
686     // packets. Exclude the special cases of 1 or 2 FEC packets.
687     if (num_fec_packets > 2) {
688       for (int j = 0; j < num_media_packets; j++) {
689         for (int j2 = j + 1; j2 < num_media_packets; j2++) {
690           int degree = 0;
691           for (int i = 0; i < num_fec_packets; i++) {
692             if (fec_packet_masks_[i][j] == fec_packet_masks_[i][j2] &&
693                 fec_packet_masks_[i][j] == 1) {
694               degree++;
695             }
696           }
697           if (degree == num_fec_packets) {
698             printf("Invalid mask: Two media packets are have full degree "
699                 "%d %d %d %d \n", j, j2, num_media_packets, num_fec_packets);
700             return -1;
701           }
702         }
703       }
704     }
705     return 0;
706   }
707 
GetPacketMaskConvertToBitMask(uint8_t * packet_mask,int num_media_packets,int num_fec_packets,int mask_bytes_fec_packet,CodeType code_type)708   void GetPacketMaskConvertToBitMask(uint8_t* packet_mask,
709                                      int num_media_packets,
710                                      int num_fec_packets,
711                                      int mask_bytes_fec_packet,
712                                      CodeType code_type) {
713     for (int i = 0; i < num_fec_packets; i++) {
714       for (int j = 0; j < num_media_packets; j++) {
715         const uint8_t byte_mask =
716             packet_mask[i * mask_bytes_fec_packet + j / 8];
717         const int bit_position = (7 - j % 8);
718         fec_packet_masks_[i][j] =
719             (byte_mask & (1 << bit_position)) >> bit_position;
720         fprintf(fp_mask_, "%d ", fec_packet_masks_[i][j]);
721       }
722       fprintf(fp_mask_, "\n");
723     }
724     fprintf(fp_mask_, "\n");
725   }
726 
ProcessXORPacketMasks(CodeType code_type,FecMaskType fec_mask_type)727   int ProcessXORPacketMasks(CodeType code_type,
728                           FecMaskType fec_mask_type) {
729     int code_index = 0;
730     // Maximum number of media packets allowed for the mask type.
731     const int packet_mask_max = kMaxMediaPackets[fec_mask_type];
732     uint8_t* packet_mask = new uint8_t[packet_mask_max * kMaskSizeLBitSet];
733     // Loop through codes up to |kMaxMediaPacketsTest|.
734     for (int num_media_packets = 1; num_media_packets <= kMaxMediaPacketsTest;
735         num_media_packets++) {
736       const int mask_bytes_fec_packet =
737           (num_media_packets > 16) ? kMaskSizeLBitSet : kMaskSizeLBitClear;
738       internal::PacketMaskTable mask_table(fec_mask_type, num_media_packets);
739       for (int num_fec_packets = 1; num_fec_packets <= num_media_packets;
740           num_fec_packets++) {
741         memset(packet_mask, 0, num_media_packets * mask_bytes_fec_packet);
742         memcpy(packet_mask, mask_table.fec_packet_mask_table()
743                [num_media_packets - 1][num_fec_packets - 1],
744                num_fec_packets * mask_bytes_fec_packet);
745         // Convert to bit mask.
746         GetPacketMaskConvertToBitMask(packet_mask,
747                                       num_media_packets,
748                                       num_fec_packets,
749                                       mask_bytes_fec_packet,
750                                       code_type);
751         if (RejectInvalidMasks(num_media_packets, num_fec_packets) < 0) {
752           return -1;
753         }
754         // Compute the metrics for this code/mask.
755         ComputeMetricsForCode(code_type,
756                               code_index);
757         code_index++;
758       }
759     }
760     assert(code_index == kNumberCodes);
761     delete [] packet_mask;
762     return 0;
763   }
764 
ProcessRS(CodeType code_type)765   void ProcessRS(CodeType code_type) {
766     int code_index = 0;
767     for (int num_media_packets = 1; num_media_packets <= kMaxMediaPacketsTest;
768         num_media_packets++) {
769       for (int num_fec_packets = 1; num_fec_packets <= num_media_packets;
770           num_fec_packets++) {
771         // Compute the metrics for this code type.
772         ComputeMetricsForCode(code_type,
773                               code_index);
774         code_index++;
775       }
776     }
777   }
778 
779   // Compute metrics for all code types and sizes.
ComputeMetricsAllCodes()780   void ComputeMetricsAllCodes() {
781     SetLossModels();
782     SetCodeParams();
783     // Get metrics for XOR code with packet masks of random type.
784     std::string filename = test::OutputPath() + "data_packet_masks";
785     fp_mask_ = fopen(filename.c_str(), "wb");
786     fprintf(fp_mask_, "MASK OF TYPE RANDOM: \n");
787     EXPECT_EQ(ProcessXORPacketMasks(xor_random_code, kFecMaskRandom), 0);
788     // Get metrics for XOR code with packet masks of bursty type.
789     fprintf(fp_mask_, "MASK OF TYPE BURSTY: \n");
790     EXPECT_EQ(ProcessXORPacketMasks(xor_bursty_code, kFecMaskBursty), 0);
791     fclose(fp_mask_);
792     // Get metrics for Reed-Solomon code.
793     ProcessRS(rs_code);
794   }
795 };
796 
797 // Verify that the average residual loss, averaged over loss models
798 // appropriate to each mask type, is below some maximum acceptable level. The
799 // acceptable levels are read in from a file, and correspond to a current set
800 // of packet masks. The levels for each code may be updated over time.
TEST_F(FecPacketMaskMetricsTest,FecXorMaxResidualLoss)801 TEST_F(FecPacketMaskMetricsTest, FecXorMaxResidualLoss) {
802   SetLossModels();
803   SetCodeParams();
804   ComputeMetricsAllCodes();
805   WriteOutMetricsAllFecCodes();
806   int num_loss_rates = sizeof(kAverageLossRate) /
807       sizeof(*kAverageLossRate);
808   int num_burst_lengths = sizeof(kAverageBurstLength) /
809       sizeof(*kAverageBurstLength);
810   for (int code_index = 0; code_index < max_num_codes_; code_index++) {
811     double sum_residual_loss_random_mask_random_loss = 0.0;
812     double sum_residual_loss_bursty_mask_bursty_loss = 0.0;
813     // Compute the sum residual loss across the models, for each mask type.
814     for (int k = 0; k < kNumLossModels; k++) {
815       if (loss_model_[k].loss_type == kRandomLossModel) {
816         sum_residual_loss_random_mask_random_loss +=
817             kMetricsXorRandom[code_index].average_residual_loss[k];
818       } else if (loss_model_[k].loss_type == kBurstyLossModel) {
819         sum_residual_loss_bursty_mask_bursty_loss +=
820             kMetricsXorBursty[code_index].average_residual_loss[k];
821       }
822     }
823     float average_residual_loss_random_mask_random_loss =
824         sum_residual_loss_random_mask_random_loss / num_loss_rates;
825     float average_residual_loss_bursty_mask_bursty_loss =
826         sum_residual_loss_bursty_mask_bursty_loss /
827         (num_loss_rates * (num_burst_lengths  - 1));
828     const float ref_random_mask = kMaxResidualLossRandomMask[code_index];
829     const float ref_bursty_mask = kMaxResidualLossBurstyMask[code_index];
830     EXPECT_LE(average_residual_loss_random_mask_random_loss, ref_random_mask);
831     EXPECT_LE(average_residual_loss_bursty_mask_bursty_loss, ref_bursty_mask);
832   }
833 }
834 
835 // Verify the behavior of the XOR codes vs the RS codes.
836 // For random loss model with average loss rates <= the code protection level,
837 // the RS code (optimal MDS code) is more efficient than XOR codes.
838 // However, for larger loss rates (above protection level) and/or bursty
839 // loss models, the RS is not always more efficient than XOR (though in most
840 // cases it still is).
TEST_F(FecPacketMaskMetricsTest,FecXorVsRS)841 TEST_F(FecPacketMaskMetricsTest, FecXorVsRS) {
842   SetLossModels();
843   SetCodeParams();
844   for (int code_index = 0; code_index < max_num_codes_; code_index++) {
845     for (int k = 0; k < kNumLossModels; k++) {
846       float loss_rate = loss_model_[k].average_loss_rate;
847       float protection_level = code_params_[code_index].protection_level;
848       // Under these conditions we expect XOR to not be better than RS.
849        if (loss_model_[k].loss_type == kRandomLossModel &&
850            loss_rate <= protection_level) {
851         EXPECT_GE(kMetricsXorRandom[code_index].average_residual_loss[k],
852                   kMetricsReedSolomon[code_index].average_residual_loss[k]);
853         EXPECT_GE(kMetricsXorBursty[code_index].average_residual_loss[k],
854                   kMetricsReedSolomon[code_index].average_residual_loss[k]);
855        }
856        // TODO(marpan): There are some cases (for high loss rates and/or
857        // burst loss models) where XOR is better than RS. Is there some pattern
858        // we can identify and enforce as a constraint?
859     }
860   }
861 }
862 
863 // Verify the trend (change) in the average residual loss, as a function of
864 // loss rate, of the XOR code relative to the RS code.
865 // The difference between XOR and RS should not get worse as we increase
866 // the average loss rate.
TEST_F(FecPacketMaskMetricsTest,FecTrendXorVsRsLossRate)867 TEST_F(FecPacketMaskMetricsTest, FecTrendXorVsRsLossRate) {
868   SetLossModels();
869   SetCodeParams();
870   // TODO(marpan): Examine this further to see if the condition can be strictly
871   // satisfied (i.e., scale = 1.0) for all codes with different/better masks.
872   double scale = 0.90;
873   int num_loss_rates = sizeof(kAverageLossRate) /
874       sizeof(*kAverageLossRate);
875   int num_burst_lengths = sizeof(kAverageBurstLength) /
876       sizeof(*kAverageBurstLength);
877   for (int code_index = 0; code_index < max_num_codes_; code_index++) {
878     for (int i = 0; i < num_burst_lengths; i++) {
879       for (int j = 0; j < num_loss_rates - 1; j++) {
880         int k = num_loss_rates * i + j;
881         // For XOR random.
882         if (kMetricsXorRandom[code_index].average_residual_loss[k] >
883         kMetricsReedSolomon[code_index].average_residual_loss[k]) {
884           double diff_rs_xor_random_loss1 =
885               (kMetricsXorRandom[code_index].average_residual_loss[k] -
886                kMetricsReedSolomon[code_index].average_residual_loss[k]) /
887                kMetricsXorRandom[code_index].average_residual_loss[k];
888           double diff_rs_xor_random_loss2 =
889               (kMetricsXorRandom[code_index].average_residual_loss[k+1] -
890                kMetricsReedSolomon[code_index].average_residual_loss[k+1]) /
891                kMetricsXorRandom[code_index].average_residual_loss[k+1];
892           EXPECT_GE(diff_rs_xor_random_loss1, scale * diff_rs_xor_random_loss2);
893         }
894         // TODO(marpan): Investigate the cases for the bursty mask where
895         // this trend is not strictly satisfied.
896       }
897     }
898   }
899 }
900 
901 // Verify the average residual loss behavior via the protection level and
902 // the code length. The average residual loss for a given (k1,m1) code
903 // should generally be higher than that of another code (k2,m2), which has
904 // either of the two conditions satisfied:
905 // 1) higher protection & code length at least as large: (k2+m2) >= (k1+m1),
906 // 2) equal protection and larger code length: (k2+m2) > (k1+m1).
907 // Currently does not hold for some cases of the XOR code with random mask.
TEST_F(FecPacketMaskMetricsTest,FecBehaviorViaProtectionLevelAndLength)908 TEST_F(FecPacketMaskMetricsTest, FecBehaviorViaProtectionLevelAndLength) {
909   SetLossModels();
910   SetCodeParams();
911   for (int code_index1 = 0; code_index1 < max_num_codes_; code_index1++) {
912     float protection_level1 = code_params_[code_index1].protection_level;
913     int length1 = code_params_[code_index1].num_media_packets +
914         code_params_[code_index1].num_fec_packets;
915     for (int code_index2 = 0; code_index2 < max_num_codes_; code_index2++) {
916       float protection_level2 = code_params_[code_index2].protection_level;
917       int length2 = code_params_[code_index2].num_media_packets +
918           code_params_[code_index2].num_fec_packets;
919       // Codes with higher protection are more efficient, conditioned on the
920       // length of the code (higher protection but shorter length codes are
921       // generally not more efficient). For two codes with equal protection,
922       // the longer code is generally more efficient. For high loss rate
923       // models, this condition may be violated for some codes with equal or
924       // very close protection levels. High loss rate case is excluded below.
925       if ((protection_level2 > protection_level1 && length2 >= length1) ||
926           (protection_level2 == protection_level1 && length2 > length1)) {
927         for (int k = 0; k < kNumLossModels; k++) {
928           float loss_rate = loss_model_[k].average_loss_rate;
929           if (loss_rate < loss_rate_upper_threshold) {
930             EXPECT_LT(
931                 kMetricsReedSolomon[code_index2].average_residual_loss[k],
932                 kMetricsReedSolomon[code_index1].average_residual_loss[k]);
933             // TODO(marpan): There are some corner cases where this is not
934             // satisfied with the current packet masks. Look into updating
935             // these cases to see if this behavior should/can be satisfied,
936             // with overall lower residual loss for those XOR codes.
937             // EXPECT_LT(
938             //    kMetricsXorBursty[code_index2].average_residual_loss[k],
939             //    kMetricsXorBursty[code_index1].average_residual_loss[k]);
940             // EXPECT_LT(
941             //   kMetricsXorRandom[code_index2].average_residual_loss[k],
942             //   kMetricsXorRandom[code_index1].average_residual_loss[k]);
943           }
944         }
945       }
946     }
947   }
948 }
949 
950 // Verify the beheavior of the variance of the XOR codes.
951 // The partial recovery of the XOR versus the all or nothing behavior of the RS
952 // code means that the variance of the residual loss for XOR should generally
953 // not be worse than RS.
TEST_F(FecPacketMaskMetricsTest,FecVarianceBehaviorXorVsRs)954 TEST_F(FecPacketMaskMetricsTest, FecVarianceBehaviorXorVsRs) {
955   SetLossModels();
956   SetCodeParams();
957   // The condition is not strictly satisfied with the current masks,
958   // i.e., for some codes, the variance of XOR may be slightly higher than RS.
959   // TODO(marpan): Examine this further to see if the condition can be strictly
960   // satisfied (i.e., scale = 1.0) for all codes with different/better masks.
961   double scale = 0.95;
962   for (int code_index = 0; code_index < max_num_codes_; code_index++) {
963     for (int k = 0; k < kNumLossModels; k++) {
964       EXPECT_LE(scale *
965                 kMetricsXorRandom[code_index].variance_residual_loss[k],
966                 kMetricsReedSolomon[code_index].variance_residual_loss[k]);
967       EXPECT_LE(scale *
968                 kMetricsXorBursty[code_index].variance_residual_loss[k],
969                 kMetricsReedSolomon[code_index].variance_residual_loss[k]);
970     }
971   }
972 }
973 
974 // For the bursty mask type, the residual loss must be strictly zero for all
975 // consecutive losses (i.e, gap = 0) with number of losses <= num_fec_packets.
976 // This is a design property of the bursty mask type.
TEST_F(FecPacketMaskMetricsTest,FecXorBurstyPerfectRecoveryConsecutiveLoss)977 TEST_F(FecPacketMaskMetricsTest, FecXorBurstyPerfectRecoveryConsecutiveLoss) {
978   SetLossModels();
979   SetCodeParams();
980   for (int code_index = 0; code_index < max_num_codes_; code_index++) {
981     int num_fec_packets = code_params_[code_index].num_fec_packets;
982     for (int loss = 1; loss <= num_fec_packets; loss++) {
983       int index = loss;  // |gap| is zero.
984       EXPECT_EQ(kMetricsXorBursty[code_index].
985                 residual_loss_per_loss_gap[index], 0.0);
986     }
987   }
988 }
989 
990 // The XOR codes with random mask type are generally better than the ones with
991 // bursty mask type, for random loss models at low loss rates.
992 // The XOR codes with bursty mask types are generally better than the one with
993 // random mask type, for bursty loss models and/or high loss rates.
994 // TODO(marpan): Enable this test when some of the packet masks are updated.
995 // Some isolated cases of the codes don't pass this currently.
996 /*
997 TEST_F(FecPacketMaskMetricsTest, FecXorRandomVsBursty) {
998   SetLossModels();
999   SetCodeParams();
1000   for (int code_index = 0; code_index < max_num_codes_; code_index++) {
1001     double sum_residual_loss_random_mask_random_loss = 0.0;
1002     double sum_residual_loss_bursty_mask_random_loss = 0.0;
1003     double sum_residual_loss_random_mask_bursty_loss = 0.0;
1004     double sum_residual_loss_bursty_mask_bursty_loss = 0.0;
1005     // Compute the sum residual loss across the models, for each mask type.
1006     for (int k = 0; k < kNumLossModels; k++) {
1007       float loss_rate = loss_model_[k].average_loss_rate;
1008       if (loss_model_[k].loss_type == kRandomLossModel &&
1009           loss_rate < loss_rate_upper_threshold) {
1010         sum_residual_loss_random_mask_random_loss +=
1011             kMetricsXorRandom[code_index].average_residual_loss[k];
1012         sum_residual_loss_bursty_mask_random_loss +=
1013             kMetricsXorBursty[code_index].average_residual_loss[k];
1014       } else if (loss_model_[k].loss_type == kBurstyLossModel &&
1015           loss_rate > loss_rate_lower_threshold) {
1016         sum_residual_loss_random_mask_bursty_loss +=
1017             kMetricsXorRandom[code_index].average_residual_loss[k];
1018         sum_residual_loss_bursty_mask_bursty_loss +=
1019             kMetricsXorBursty[code_index].average_residual_loss[k];
1020       }
1021     }
1022     EXPECT_LE(sum_residual_loss_random_mask_random_loss,
1023               sum_residual_loss_bursty_mask_random_loss);
1024     EXPECT_LE(sum_residual_loss_bursty_mask_bursty_loss,
1025               sum_residual_loss_random_mask_bursty_loss);
1026   }
1027 }
1028 */
1029 
1030 // Verify that the average recovery rate for each code is equal or above some
1031 // threshold, for certain loss number conditions.
TEST_F(FecPacketMaskMetricsTest,FecRecoveryRateUnderLossConditions)1032 TEST_F(FecPacketMaskMetricsTest, FecRecoveryRateUnderLossConditions) {
1033   SetLossModels();
1034   SetCodeParams();
1035   for (int code_index = 0; code_index < max_num_codes_; code_index++) {
1036     int num_media_packets = code_params_[code_index].num_media_packets;
1037     int num_fec_packets = code_params_[code_index].num_fec_packets;
1038     // Perfect recovery (|recovery_rate_per_loss| == 1) is expected for
1039     // |loss_number| = 1, for all codes.
1040     int loss_number = 1;
1041     EXPECT_EQ(kMetricsReedSolomon[code_index].
1042               recovery_rate_per_loss[loss_number], 1.0);
1043     EXPECT_EQ(kMetricsXorRandom[code_index].
1044               recovery_rate_per_loss[loss_number], 1.0);
1045     EXPECT_EQ(kMetricsXorBursty[code_index].
1046               recovery_rate_per_loss[loss_number], 1.0);
1047     // For |loss_number| = |num_fec_packets| / 2, we expect the following:
1048     // Perfect recovery for RS, and recovery for XOR above the threshold.
1049     loss_number = num_fec_packets / 2 > 0 ? num_fec_packets / 2 : 1;
1050     EXPECT_EQ(kMetricsReedSolomon[code_index].
1051               recovery_rate_per_loss[loss_number], 1.0);
1052     EXPECT_GE(kMetricsXorRandom[code_index].
1053               recovery_rate_per_loss[loss_number], kRecoveryRateXorRandom[0]);
1054     EXPECT_GE(kMetricsXorBursty[code_index].
1055               recovery_rate_per_loss[loss_number], kRecoveryRateXorBursty[0]);
1056     // For |loss_number| = |num_fec_packets|, we expect the following:
1057     // Perfect recovery for RS, and recovery for XOR above the threshold.
1058     loss_number = num_fec_packets;
1059     EXPECT_EQ(kMetricsReedSolomon[code_index].
1060               recovery_rate_per_loss[loss_number], 1.0);
1061     EXPECT_GE(kMetricsXorRandom[code_index].
1062               recovery_rate_per_loss[loss_number], kRecoveryRateXorRandom[1]);
1063     EXPECT_GE(kMetricsXorBursty[code_index].
1064               recovery_rate_per_loss[loss_number], kRecoveryRateXorBursty[1]);
1065     // For |loss_number| = |num_fec_packets| + 1, we expect the following:
1066     // Zero recovery for RS, but non-zero recovery for XOR.
1067     if (num_fec_packets > 1 && num_media_packets > 2) {
1068       loss_number =  num_fec_packets + 1;
1069       EXPECT_EQ(kMetricsReedSolomon[code_index].
1070                 recovery_rate_per_loss[loss_number], 0.0);
1071       EXPECT_GE(kMetricsXorRandom[code_index].
1072                 recovery_rate_per_loss[loss_number],
1073                 kRecoveryRateXorRandom[2]);
1074       EXPECT_GE(kMetricsXorBursty[code_index].
1075                 recovery_rate_per_loss[loss_number],
1076                 kRecoveryRateXorBursty[2]);
1077     }
1078   }
1079 }
1080 
1081 }  // namespace webrtc
1082