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 * Test application for core FEC algorithm. Calls encoding and decoding
13 * functions in ForwardErrorCorrection directly.
14 */
15
16 #include <assert.h>
17 #include <stdio.h>
18 #include <stdlib.h>
19 #include <string.h>
20 #include <time.h>
21
22 #include <list>
23
24 #include "testing/gtest/include/gtest/gtest.h"
25 #include "webrtc/base/random.h"
26 #include "webrtc/modules/rtp_rtcp/source/byte_io.h"
27 #include "webrtc/modules/rtp_rtcp/source/forward_error_correction.h"
28 #include "webrtc/modules/rtp_rtcp/source/forward_error_correction_internal.h"
29 #include "webrtc/test/testsupport/fileutils.h"
30
31 // #define VERBOSE_OUTPUT
32
33 namespace webrtc {
34 namespace fec_private_tables {
35 extern const uint8_t** kPacketMaskBurstyTbl[12];
36 }
37 namespace test {
38 using fec_private_tables::kPacketMaskBurstyTbl;
39
ReceivePackets(ForwardErrorCorrection::ReceivedPacketList * toDecodeList,ForwardErrorCorrection::ReceivedPacketList * receivedPacketList,size_t numPacketsToDecode,float reorderRate,float duplicateRate,Random * random)40 void ReceivePackets(
41 ForwardErrorCorrection::ReceivedPacketList* toDecodeList,
42 ForwardErrorCorrection::ReceivedPacketList* receivedPacketList,
43 size_t numPacketsToDecode,
44 float reorderRate,
45 float duplicateRate,
46 Random* random) {
47 assert(toDecodeList->empty());
48 assert(numPacketsToDecode <= receivedPacketList->size());
49
50 ForwardErrorCorrection::ReceivedPacketList::iterator it;
51 for (size_t i = 0; i < numPacketsToDecode; i++) {
52 it = receivedPacketList->begin();
53 // Reorder packets.
54 float randomVariable = random->Rand<float>();
55 while (randomVariable < reorderRate) {
56 ++it;
57 if (it == receivedPacketList->end()) {
58 --it;
59 break;
60 }
61 randomVariable = random->Rand<float>();
62 }
63 ForwardErrorCorrection::ReceivedPacket* receivedPacket = *it;
64 toDecodeList->push_back(receivedPacket);
65
66 // Duplicate packets.
67 randomVariable = random->Rand<float>();
68 while (randomVariable < duplicateRate) {
69 ForwardErrorCorrection::ReceivedPacket* duplicatePacket =
70 new ForwardErrorCorrection::ReceivedPacket;
71 *duplicatePacket = *receivedPacket;
72 duplicatePacket->pkt = new ForwardErrorCorrection::Packet;
73 memcpy(duplicatePacket->pkt->data, receivedPacket->pkt->data,
74 receivedPacket->pkt->length);
75 duplicatePacket->pkt->length = receivedPacket->pkt->length;
76
77 toDecodeList->push_back(duplicatePacket);
78 randomVariable = random->Rand<float>();
79 }
80 receivedPacketList->erase(it);
81 }
82 }
83
TEST(FecTest,FecTest)84 TEST(FecTest, FecTest) {
85 // TODO(marpan): Split this function into subroutines/helper functions.
86 enum { kMaxNumberMediaPackets = 48 };
87 enum { kMaxNumberFecPackets = 48 };
88
89 const uint32_t kNumMaskBytesL0 = 2;
90 const uint32_t kNumMaskBytesL1 = 6;
91
92 // FOR UEP
93 const bool kUseUnequalProtection = true;
94
95 // FEC mask types.
96 const FecMaskType kMaskTypes[] = {kFecMaskRandom, kFecMaskBursty};
97 const int kNumFecMaskTypes = sizeof(kMaskTypes) / sizeof(*kMaskTypes);
98
99 // Maximum number of media packets allowed for the mask type.
100 const uint16_t kMaxMediaPackets[] = {
101 kMaxNumberMediaPackets,
102 sizeof(kPacketMaskBurstyTbl) / sizeof(*kPacketMaskBurstyTbl)};
103
104 ASSERT_EQ(12, kMaxMediaPackets[1]) << "Max media packets for bursty mode not "
105 << "equal to 12.";
106
107 ForwardErrorCorrection fec;
108 ForwardErrorCorrection::PacketList mediaPacketList;
109 ForwardErrorCorrection::PacketList fecPacketList;
110 ForwardErrorCorrection::ReceivedPacketList toDecodeList;
111 ForwardErrorCorrection::ReceivedPacketList receivedPacketList;
112 ForwardErrorCorrection::RecoveredPacketList recoveredPacketList;
113 std::list<uint8_t*> fecMaskList;
114
115 ForwardErrorCorrection::Packet* mediaPacket = NULL;
116 // Running over only one loss rate to limit execution time.
117 const float lossRate[] = {0.5f};
118 const uint32_t lossRateSize = sizeof(lossRate) / sizeof(*lossRate);
119 const float reorderRate = 0.1f;
120 const float duplicateRate = 0.1f;
121
122 uint8_t mediaLossMask[kMaxNumberMediaPackets];
123 uint8_t fecLossMask[kMaxNumberFecPackets];
124 uint8_t fecPacketMasks[kMaxNumberFecPackets][kMaxNumberMediaPackets];
125
126 // Seed the random number generator, storing the seed to file in order to
127 // reproduce past results.
128 const unsigned int randomSeed = static_cast<unsigned int>(time(NULL));
129 Random random(randomSeed);
130 std::string filename = webrtc::test::OutputPath() + "randomSeedLog.txt";
131 FILE* randomSeedFile = fopen(filename.c_str(), "a");
132 fprintf(randomSeedFile, "%u\n", randomSeed);
133 fclose(randomSeedFile);
134 randomSeedFile = NULL;
135
136 uint16_t seqNum = 0;
137 uint32_t timeStamp = random.Rand<uint32_t>();
138 const uint32_t ssrc = random.Rand(1u, 0xfffffffe);
139
140 // Loop over the mask types: random and bursty.
141 for (int mask_type_idx = 0; mask_type_idx < kNumFecMaskTypes;
142 ++mask_type_idx) {
143 for (uint32_t lossRateIdx = 0; lossRateIdx < lossRateSize; ++lossRateIdx) {
144 printf("Loss rate: %.2f, Mask type %d \n", lossRate[lossRateIdx],
145 mask_type_idx);
146
147 const uint32_t packetMaskMax = kMaxMediaPackets[mask_type_idx];
148 uint8_t* packetMask = new uint8_t[packetMaskMax * kNumMaskBytesL1];
149
150 FecMaskType fec_mask_type = kMaskTypes[mask_type_idx];
151
152 for (uint32_t numMediaPackets = 1; numMediaPackets <= packetMaskMax;
153 numMediaPackets++) {
154 internal::PacketMaskTable mask_table(fec_mask_type, numMediaPackets);
155
156 for (uint32_t numFecPackets = 1;
157 numFecPackets <= numMediaPackets && numFecPackets <= packetMaskMax;
158 numFecPackets++) {
159 // Loop over numImpPackets: usually <= (0.3*numMediaPackets).
160 // For this test we check up to ~ (numMediaPackets / 4).
161 uint32_t maxNumImpPackets = numMediaPackets / 4 + 1;
162 for (uint32_t numImpPackets = 0; numImpPackets <= maxNumImpPackets &&
163 numImpPackets <= packetMaskMax;
164 numImpPackets++) {
165 uint8_t protectionFactor =
166 static_cast<uint8_t>(numFecPackets * 255 / numMediaPackets);
167
168 const uint32_t maskBytesPerFecPacket =
169 (numMediaPackets > 16) ? kNumMaskBytesL1 : kNumMaskBytesL0;
170
171 memset(packetMask, 0, numMediaPackets * maskBytesPerFecPacket);
172
173 // Transfer packet masks from bit-mask to byte-mask.
174 internal::GeneratePacketMasks(numMediaPackets, numFecPackets,
175 numImpPackets, kUseUnequalProtection,
176 mask_table, packetMask);
177
178 #ifdef VERBOSE_OUTPUT
179 printf(
180 "%u media packets, %u FEC packets, %u numImpPackets, "
181 "loss rate = %.2f \n",
182 numMediaPackets, numFecPackets, numImpPackets,
183 lossRate[lossRateIdx]);
184 printf("Packet mask matrix \n");
185 #endif
186
187 for (uint32_t i = 0; i < numFecPackets; i++) {
188 for (uint32_t j = 0; j < numMediaPackets; j++) {
189 const uint8_t byteMask =
190 packetMask[i * maskBytesPerFecPacket + j / 8];
191 const uint32_t bitPosition = (7 - j % 8);
192 fecPacketMasks[i][j] =
193 (byteMask & (1 << bitPosition)) >> bitPosition;
194 #ifdef VERBOSE_OUTPUT
195 printf("%u ", fecPacketMasks[i][j]);
196 #endif
197 }
198 #ifdef VERBOSE_OUTPUT
199 printf("\n");
200 #endif
201 }
202 #ifdef VERBOSE_OUTPUT
203 printf("\n");
204 #endif
205 // Check for all zero rows or columns: indicates incorrect mask.
206 uint32_t rowLimit = numMediaPackets;
207 for (uint32_t i = 0; i < numFecPackets; ++i) {
208 uint32_t rowSum = 0;
209 for (uint32_t j = 0; j < rowLimit; ++j) {
210 rowSum += fecPacketMasks[i][j];
211 }
212 ASSERT_NE(0u, rowSum) << "Row is all zero " << i;
213 }
214 for (uint32_t j = 0; j < rowLimit; ++j) {
215 uint32_t columnSum = 0;
216 for (uint32_t i = 0; i < numFecPackets; ++i) {
217 columnSum += fecPacketMasks[i][j];
218 }
219 ASSERT_NE(0u, columnSum) << "Column is all zero " << j;
220 }
221
222 // Construct media packets.
223 // Reset the sequence number here for each FEC code/mask tested
224 // below, to avoid sequence number wrap-around. In actual decoding,
225 // old FEC packets in list are dropped if sequence number wrap
226 // around is detected. This case is currently not handled below.
227 seqNum = 0;
228 for (uint32_t i = 0; i < numMediaPackets; ++i) {
229 mediaPacket = new ForwardErrorCorrection::Packet;
230 mediaPacketList.push_back(mediaPacket);
231 const uint32_t kMinPacketSize = 12;
232 const uint32_t kMaxPacketSize = static_cast<uint32_t>(
233 IP_PACKET_SIZE - 12 - 28 -
234 ForwardErrorCorrection::PacketOverhead());
235 mediaPacket->length = random.Rand(kMinPacketSize, kMaxPacketSize);
236
237 // Generate random values for the first 2 bytes.
238 mediaPacket->data[0] = random.Rand<uint8_t>();
239 mediaPacket->data[1] = random.Rand<uint8_t>();
240
241 // The first two bits are assumed to be 10 by the
242 // FEC encoder. In fact the FEC decoder will set the
243 // two first bits to 10 regardless of what they
244 // actually were. Set the first two bits to 10
245 // so that a memcmp can be performed for the
246 // whole restored packet.
247 mediaPacket->data[0] |= 0x80;
248 mediaPacket->data[0] &= 0xbf;
249
250 // FEC is applied to a whole frame.
251 // A frame is signaled by multiple packets without
252 // the marker bit set followed by the last packet of
253 // the frame for which the marker bit is set.
254 // Only push one (fake) frame to the FEC.
255 mediaPacket->data[1] &= 0x7f;
256
257 ByteWriter<uint16_t>::WriteBigEndian(&mediaPacket->data[2],
258 seqNum);
259 ByteWriter<uint32_t>::WriteBigEndian(&mediaPacket->data[4],
260 timeStamp);
261 ByteWriter<uint32_t>::WriteBigEndian(&mediaPacket->data[8], ssrc);
262 // Generate random values for payload
263 for (size_t j = 12; j < mediaPacket->length; ++j) {
264 mediaPacket->data[j] = random.Rand<uint8_t>();
265 }
266 seqNum++;
267 }
268 mediaPacket->data[1] |= 0x80;
269
270 ASSERT_EQ(0, fec.GenerateFEC(mediaPacketList, protectionFactor,
271 numImpPackets, kUseUnequalProtection,
272 fec_mask_type, &fecPacketList))
273 << "GenerateFEC() failed";
274
275 ASSERT_EQ(numFecPackets, fecPacketList.size())
276 << "We requested " << numFecPackets << " FEC packets, but "
277 << "GenerateFEC() produced " << fecPacketList.size();
278 memset(mediaLossMask, 0, sizeof(mediaLossMask));
279 ForwardErrorCorrection::PacketList::iterator mediaPacketListItem =
280 mediaPacketList.begin();
281 ForwardErrorCorrection::ReceivedPacket* receivedPacket;
282 uint32_t mediaPacketIdx = 0;
283
284 while (mediaPacketListItem != mediaPacketList.end()) {
285 mediaPacket = *mediaPacketListItem;
286 // We want a value between 0 and 1.
287 const float lossRandomVariable = random.Rand<float>();
288
289 if (lossRandomVariable >= lossRate[lossRateIdx]) {
290 mediaLossMask[mediaPacketIdx] = 1;
291 receivedPacket = new ForwardErrorCorrection::ReceivedPacket;
292 receivedPacket->pkt = new ForwardErrorCorrection::Packet;
293 receivedPacketList.push_back(receivedPacket);
294
295 receivedPacket->pkt->length = mediaPacket->length;
296 memcpy(receivedPacket->pkt->data, mediaPacket->data,
297 mediaPacket->length);
298 receivedPacket->seq_num =
299 ByteReader<uint16_t>::ReadBigEndian(&mediaPacket->data[2]);
300 receivedPacket->is_fec = false;
301 }
302 mediaPacketIdx++;
303 ++mediaPacketListItem;
304 }
305 memset(fecLossMask, 0, sizeof(fecLossMask));
306 ForwardErrorCorrection::PacketList::iterator fecPacketListItem =
307 fecPacketList.begin();
308 ForwardErrorCorrection::Packet* fecPacket;
309 uint32_t fecPacketIdx = 0;
310 while (fecPacketListItem != fecPacketList.end()) {
311 fecPacket = *fecPacketListItem;
312 const float lossRandomVariable = random.Rand<float>();
313 if (lossRandomVariable >= lossRate[lossRateIdx]) {
314 fecLossMask[fecPacketIdx] = 1;
315 receivedPacket = new ForwardErrorCorrection::ReceivedPacket;
316 receivedPacket->pkt = new ForwardErrorCorrection::Packet;
317
318 receivedPacketList.push_back(receivedPacket);
319
320 receivedPacket->pkt->length = fecPacket->length;
321 memcpy(receivedPacket->pkt->data, fecPacket->data,
322 fecPacket->length);
323
324 receivedPacket->seq_num = seqNum;
325 receivedPacket->is_fec = true;
326 receivedPacket->ssrc = ssrc;
327
328 fecMaskList.push_back(fecPacketMasks[fecPacketIdx]);
329 }
330 ++fecPacketIdx;
331 ++seqNum;
332 ++fecPacketListItem;
333 }
334
335 #ifdef VERBOSE_OUTPUT
336 printf("Media loss mask:\n");
337 for (uint32_t i = 0; i < numMediaPackets; i++) {
338 printf("%u ", mediaLossMask[i]);
339 }
340 printf("\n\n");
341
342 printf("FEC loss mask:\n");
343 for (uint32_t i = 0; i < numFecPackets; i++) {
344 printf("%u ", fecLossMask[i]);
345 }
346 printf("\n\n");
347 #endif
348
349 std::list<uint8_t*>::iterator fecMaskIt = fecMaskList.begin();
350 uint8_t* fecMask;
351 while (fecMaskIt != fecMaskList.end()) {
352 fecMask = *fecMaskIt;
353 uint32_t hammingDist = 0;
354 uint32_t recoveryPosition = 0;
355 for (uint32_t i = 0; i < numMediaPackets; i++) {
356 if (mediaLossMask[i] == 0 && fecMask[i] == 1) {
357 recoveryPosition = i;
358 ++hammingDist;
359 }
360 }
361 std::list<uint8_t*>::iterator itemToDelete = fecMaskIt;
362 ++fecMaskIt;
363
364 if (hammingDist == 1) {
365 // Recovery possible. Restart search.
366 mediaLossMask[recoveryPosition] = 1;
367 fecMaskIt = fecMaskList.begin();
368 } else if (hammingDist == 0) {
369 // FEC packet cannot provide further recovery.
370 fecMaskList.erase(itemToDelete);
371 }
372 }
373 #ifdef VERBOSE_OUTPUT
374 printf("Recovery mask:\n");
375 for (uint32_t i = 0; i < numMediaPackets; ++i) {
376 printf("%u ", mediaLossMask[i]);
377 }
378 printf("\n\n");
379 #endif
380 // For error-checking frame completion.
381 bool fecPacketReceived = false;
382 while (!receivedPacketList.empty()) {
383 size_t numPacketsToDecode = random.Rand(
384 1u, static_cast<uint32_t>(receivedPacketList.size()));
385 ReceivePackets(&toDecodeList, &receivedPacketList,
386 numPacketsToDecode, reorderRate, duplicateRate,
387 &random);
388
389 if (fecPacketReceived == false) {
390 ForwardErrorCorrection::ReceivedPacketList::iterator
391 toDecodeIt = toDecodeList.begin();
392 while (toDecodeIt != toDecodeList.end()) {
393 receivedPacket = *toDecodeIt;
394 if (receivedPacket->is_fec) {
395 fecPacketReceived = true;
396 }
397 ++toDecodeIt;
398 }
399 }
400 ASSERT_EQ(0, fec.DecodeFEC(&toDecodeList, &recoveredPacketList))
401 << "DecodeFEC() failed";
402 ASSERT_TRUE(toDecodeList.empty())
403 << "Received packet list is not empty.";
404 }
405 mediaPacketListItem = mediaPacketList.begin();
406 mediaPacketIdx = 0;
407 while (mediaPacketListItem != mediaPacketList.end()) {
408 if (mediaLossMask[mediaPacketIdx] == 1) {
409 // Should have recovered this packet.
410 ForwardErrorCorrection::RecoveredPacketList::iterator
411 recoveredPacketListItem = recoveredPacketList.begin();
412
413 ASSERT_FALSE(recoveredPacketListItem ==
414 recoveredPacketList.end())
415 << "Insufficient number of recovered packets.";
416 mediaPacket = *mediaPacketListItem;
417 ForwardErrorCorrection::RecoveredPacket* recoveredPacket =
418 *recoveredPacketListItem;
419
420 ASSERT_EQ(recoveredPacket->pkt->length, mediaPacket->length)
421 << "Recovered packet length not identical to original "
422 << "media packet";
423 ASSERT_EQ(0, memcmp(recoveredPacket->pkt->data,
424 mediaPacket->data, mediaPacket->length))
425 << "Recovered packet payload not identical to original "
426 << "media packet";
427 delete recoveredPacket;
428 recoveredPacketList.pop_front();
429 }
430 ++mediaPacketIdx;
431 ++mediaPacketListItem;
432 }
433 fec.ResetState(&recoveredPacketList);
434 ASSERT_TRUE(recoveredPacketList.empty())
435 << "Excessive number of recovered packets.\t size is: "
436 << recoveredPacketList.size();
437 // -- Teardown --
438 mediaPacketListItem = mediaPacketList.begin();
439 while (mediaPacketListItem != mediaPacketList.end()) {
440 delete *mediaPacketListItem;
441 ++mediaPacketListItem;
442 mediaPacketList.pop_front();
443 }
444 assert(mediaPacketList.empty());
445
446 fecPacketListItem = fecPacketList.begin();
447 while (fecPacketListItem != fecPacketList.end()) {
448 ++fecPacketListItem;
449 fecPacketList.pop_front();
450 }
451
452 // Delete received packets we didn't pass to DecodeFEC(), due to
453 // early frame completion.
454 ForwardErrorCorrection::ReceivedPacketList::iterator
455 receivedPacketIt = receivedPacketList.begin();
456 while (receivedPacketIt != receivedPacketList.end()) {
457 receivedPacket = *receivedPacketIt;
458 delete receivedPacket;
459 ++receivedPacketIt;
460 receivedPacketList.pop_front();
461 }
462 assert(receivedPacketList.empty());
463
464 while (!fecMaskList.empty()) {
465 fecMaskList.pop_front();
466 }
467 timeStamp += 90000 / 30;
468 } // loop over numImpPackets
469 } // loop over FecPackets
470 } // loop over numMediaPackets
471 delete[] packetMask;
472 } // loop over loss rates
473 } // loop over mask types
474
475 // Have DecodeFEC free allocated memory.
476 fec.ResetState(&recoveredPacketList);
477 ASSERT_TRUE(recoveredPacketList.empty())
478 << "Recovered packet list is not empty";
479 }
480
481 } // namespace test
482 } // namespace webrtc
483