1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include <algorithm> 6 #include <vector> 7 8 #include "base/logging.h" 9 #include "base/memory/scoped_ptr.h" 10 #include "net/quic/quic_fec_group.h" 11 #include "testing/gmock/include/gmock/gmock.h" 12 13 using ::testing::_; 14 using base::StringPiece; 15 16 namespace net { 17 18 namespace { 19 20 const char* kData[] = { 21 "abc12345678", 22 "987defg", 23 "ghi12345", 24 "987jlkmno", 25 "mno4567890", 26 "789pqrstuvw", 27 }; 28 29 const bool kEntropyFlag[] = { 30 false, 31 true, 32 true, 33 false, 34 true, 35 true, 36 }; 37 38 const bool kTestFecPacketEntropy = false; 39 40 } // namespace 41 42 class QuicFecGroupTest : public ::testing::Test { 43 protected: 44 void RunTest(size_t num_packets, size_t lost_packet, bool out_of_order) { 45 size_t max_len = strlen(kData[0]); 46 scoped_ptr<char[]> redundancy(new char[max_len]); 47 bool entropy_redundancy = false; 48 for (size_t packet = 0; packet < num_packets; ++packet) { 49 for (size_t i = 0; i < max_len; i++) { 50 if (packet == 0) { 51 // Initialize to the first packet. 52 redundancy[i] = kData[0][i]; 53 continue; 54 } 55 // XOR in the remaining packets. 56 uint8 byte = i > strlen(kData[packet]) ? 0x00 : kData[packet][i]; 57 redundancy[i] = redundancy[i] ^ byte; 58 } 59 entropy_redundancy = (entropy_redundancy != kEntropyFlag[packet]); 60 } 61 62 QuicFecGroup group; 63 64 // If we're out of order, send the FEC packet in the position of the 65 // lost packet. Otherwise send all (non-missing) packets, then FEC. 66 if (out_of_order) { 67 // Update the FEC state for each non-lost packet. 68 for (size_t packet = 0; packet < num_packets; packet++) { 69 if (packet == lost_packet) { 70 ASSERT_FALSE(group.IsFinished()); 71 QuicFecData fec; 72 fec.fec_group = 0; 73 fec.redundancy = StringPiece(redundancy.get(), strlen(kData[0])); 74 ASSERT_TRUE(group.UpdateFec(num_packets, entropy_redundancy, fec)); 75 } else { 76 QuicPacketHeader header; 77 header.packet_sequence_number = packet; 78 header.entropy_flag = kEntropyFlag[packet]; 79 ASSERT_TRUE(group.Update(header, kData[packet])); 80 } 81 ASSERT_TRUE(group.CanRevive() == (packet == num_packets - 1)); 82 } 83 } else { 84 // Update the FEC state for each non-lost packet. 85 for (size_t packet = 0; packet < num_packets; packet++) { 86 if (packet == lost_packet) { 87 continue; 88 } 89 90 QuicPacketHeader header; 91 header.packet_sequence_number = packet; 92 header.entropy_flag = kEntropyFlag[packet]; 93 ASSERT_TRUE(group.Update(header, kData[packet])); 94 ASSERT_FALSE(group.CanRevive()); 95 } 96 97 ASSERT_FALSE(group.IsFinished()); 98 // Attempt to revive the missing packet. 99 QuicFecData fec; 100 fec.fec_group = 0; 101 fec.redundancy = StringPiece(redundancy.get(), strlen(kData[0])); 102 103 ASSERT_TRUE(group.UpdateFec(num_packets, entropy_redundancy, fec)); 104 } 105 QuicPacketHeader header; 106 char recovered[kMaxPacketSize]; 107 ASSERT_TRUE(group.CanRevive()); 108 size_t len = group.Revive(&header, recovered, arraysize(recovered)); 109 ASSERT_NE(0u, len) 110 << "Failed to revive packet " << lost_packet << " out of " 111 << num_packets; 112 EXPECT_EQ(lost_packet, header.packet_sequence_number) 113 << "Failed to revive packet " << lost_packet << " out of " 114 << num_packets; 115 EXPECT_EQ(kEntropyFlag[lost_packet], header.entropy_flag); 116 ASSERT_GE(len, strlen(kData[lost_packet])) << "Incorrect length"; 117 for (size_t i = 0; i < strlen(kData[lost_packet]); i++) { 118 EXPECT_EQ(kData[lost_packet][i], recovered[i]); 119 } 120 ASSERT_TRUE(group.IsFinished()); 121 } 122 }; 123 124 TEST_F(QuicFecGroupTest, UpdateAndRevive) { 125 RunTest(2, 0, false); 126 RunTest(2, 1, false); 127 128 RunTest(3, 0, false); 129 RunTest(3, 1, false); 130 RunTest(3, 2, false); 131 } 132 133 TEST_F(QuicFecGroupTest, UpdateAndReviveOutOfOrder) { 134 RunTest(2, 0, true); 135 RunTest(2, 1, true); 136 137 RunTest(3, 0, true); 138 RunTest(3, 1, true); 139 RunTest(3, 2, true); 140 } 141 142 TEST_F(QuicFecGroupTest, UpdateFecIfReceivedPacketIsNotCovered) { 143 char data1[] = "abc123"; 144 char redundancy[arraysize(data1)]; 145 for (size_t i = 0; i < arraysize(data1); i++) { 146 redundancy[i] = data1[i]; 147 } 148 149 QuicFecGroup group; 150 151 QuicPacketHeader header; 152 header.packet_sequence_number = 3; 153 group.Update(header, data1); 154 155 QuicFecData fec; 156 fec.fec_group = 1; 157 fec.redundancy = redundancy; 158 159 header.packet_sequence_number = 2; 160 ASSERT_FALSE(group.UpdateFec(2, kTestFecPacketEntropy, fec)); 161 } 162 163 TEST_F(QuicFecGroupTest, ProtectsPacketsBefore) { 164 QuicPacketHeader header; 165 header.packet_sequence_number = 3; 166 167 QuicFecGroup group; 168 ASSERT_TRUE(group.Update(header, kData[0])); 169 170 EXPECT_FALSE(group.ProtectsPacketsBefore(1)); 171 EXPECT_FALSE(group.ProtectsPacketsBefore(2)); 172 EXPECT_FALSE(group.ProtectsPacketsBefore(3)); 173 EXPECT_TRUE(group.ProtectsPacketsBefore(4)); 174 EXPECT_TRUE(group.ProtectsPacketsBefore(5)); 175 EXPECT_TRUE(group.ProtectsPacketsBefore(50)); 176 } 177 178 TEST_F(QuicFecGroupTest, ProtectsPacketsBeforeWithSeveralPackets) { 179 QuicPacketHeader header; 180 header.packet_sequence_number = 3; 181 182 QuicFecGroup group; 183 ASSERT_TRUE(group.Update(header, kData[0])); 184 185 header.packet_sequence_number = 7; 186 ASSERT_TRUE(group.Update(header, kData[0])); 187 188 header.packet_sequence_number = 5; 189 ASSERT_TRUE(group.Update(header, kData[0])); 190 191 EXPECT_FALSE(group.ProtectsPacketsBefore(1)); 192 EXPECT_FALSE(group.ProtectsPacketsBefore(2)); 193 EXPECT_FALSE(group.ProtectsPacketsBefore(3)); 194 EXPECT_TRUE(group.ProtectsPacketsBefore(4)); 195 EXPECT_TRUE(group.ProtectsPacketsBefore(5)); 196 EXPECT_TRUE(group.ProtectsPacketsBefore(6)); 197 EXPECT_TRUE(group.ProtectsPacketsBefore(7)); 198 EXPECT_TRUE(group.ProtectsPacketsBefore(8)); 199 EXPECT_TRUE(group.ProtectsPacketsBefore(9)); 200 EXPECT_TRUE(group.ProtectsPacketsBefore(50)); 201 } 202 203 TEST_F(QuicFecGroupTest, ProtectsPacketsBeforeWithFecData) { 204 QuicFecData fec; 205 fec.fec_group = 2; 206 fec.redundancy = kData[0]; 207 208 QuicFecGroup group; 209 ASSERT_TRUE(group.UpdateFec(3, kTestFecPacketEntropy, fec)); 210 211 EXPECT_FALSE(group.ProtectsPacketsBefore(1)); 212 EXPECT_FALSE(group.ProtectsPacketsBefore(2)); 213 EXPECT_TRUE(group.ProtectsPacketsBefore(3)); 214 EXPECT_TRUE(group.ProtectsPacketsBefore(4)); 215 EXPECT_TRUE(group.ProtectsPacketsBefore(5)); 216 EXPECT_TRUE(group.ProtectsPacketsBefore(50)); 217 } 218 219 } // namespace net 220
