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 "net/quic/quic_fec_group.h"
6
7#include <algorithm>
8#include <vector>
9
10#include "base/basictypes.h"
11#include "base/logging.h"
12#include "base/memory/scoped_ptr.h"
13#include "testing/gmock/include/gmock/gmock.h"
14
15using ::testing::_;
16using base::StringPiece;
17
18namespace net {
19
20namespace {
21
22const char* kData[] = {
23  "abc12345678",
24  "987defg",
25  "ghi12345",
26  "987jlkmno",
27  "mno4567890",
28  "789pqrstuvw",
29};
30
31const bool kEntropyFlag[] = {
32  false,
33  true,
34  true,
35  false,
36  true,
37  true,
38};
39
40}  // namespace
41
42class 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    for (size_t packet = 0; packet < num_packets; ++packet) {
48      for (size_t i = 0; i < max_len; i++) {
49        if (packet == 0) {
50          // Initialize to the first packet.
51          redundancy[i] = kData[0][i];
52          continue;
53        }
54        // XOR in the remaining packets.
55        uint8 byte = i > strlen(kData[packet]) ? 0x00 : kData[packet][i];
56        redundancy[i] = redundancy[i] ^ byte;
57      }
58    }
59
60    QuicFecGroup group;
61
62    // If we're out of order, send the FEC packet in the position of the
63    // lost packet. Otherwise send all (non-missing) packets, then FEC.
64    if (out_of_order) {
65      // Update the FEC state for each non-lost packet.
66      for (size_t packet = 0; packet < num_packets; packet++) {
67        if (packet == lost_packet) {
68          ASSERT_FALSE(group.IsFinished());
69          QuicFecData fec;
70          fec.fec_group = 0;
71          fec.redundancy = StringPiece(redundancy.get(), strlen(kData[0]));
72          ASSERT_TRUE(group.UpdateFec(ENCRYPTION_FORWARD_SECURE, num_packets,
73                                      fec));
74        } else {
75          QuicPacketHeader header;
76          header.packet_sequence_number = packet;
77          header.entropy_flag = kEntropyFlag[packet];
78          ASSERT_TRUE(group.Update(ENCRYPTION_FORWARD_SECURE, header,
79                                   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(ENCRYPTION_FORWARD_SECURE, header,
94                                 kData[packet]));
95        ASSERT_FALSE(group.CanRevive());
96      }
97
98      ASSERT_FALSE(group.IsFinished());
99      // Attempt to revive the missing packet.
100      QuicFecData fec;
101      fec.fec_group = 0;
102      fec.redundancy = StringPiece(redundancy.get(), strlen(kData[0]));
103
104      ASSERT_TRUE(group.UpdateFec(ENCRYPTION_FORWARD_SECURE, num_packets,
105                                  fec));
106    }
107    QuicPacketHeader header;
108    char recovered[kMaxPacketSize];
109    ASSERT_TRUE(group.CanRevive());
110    size_t len = group.Revive(&header, recovered, arraysize(recovered));
111    ASSERT_NE(0u, len)
112        << "Failed to revive packet " << lost_packet << " out of "
113        << num_packets;
114    EXPECT_EQ(lost_packet, header.packet_sequence_number)
115        << "Failed to revive packet " << lost_packet << " out of "
116        << num_packets;
117    // Revived packets have an unknown entropy.
118    EXPECT_FALSE(header.entropy_flag);
119    ASSERT_GE(len, strlen(kData[lost_packet])) << "Incorrect length";
120    for (size_t i = 0; i < strlen(kData[lost_packet]); i++) {
121      EXPECT_EQ(kData[lost_packet][i], recovered[i]);
122    }
123    ASSERT_TRUE(group.IsFinished());
124  }
125};
126
127TEST_F(QuicFecGroupTest, UpdateAndRevive) {
128  RunTest(2, 0, false);
129  RunTest(2, 1, false);
130
131  RunTest(3, 0, false);
132  RunTest(3, 1, false);
133  RunTest(3, 2, false);
134}
135
136TEST_F(QuicFecGroupTest, UpdateAndReviveOutOfOrder) {
137  RunTest(2, 0, true);
138  RunTest(2, 1, true);
139
140  RunTest(3, 0, true);
141  RunTest(3, 1, true);
142  RunTest(3, 2, true);
143}
144
145TEST_F(QuicFecGroupTest, UpdateFecIfReceivedPacketIsNotCovered) {
146  char data1[] = "abc123";
147  char redundancy[arraysize(data1)];
148  for (size_t i = 0; i < arraysize(data1); i++) {
149    redundancy[i] = data1[i];
150  }
151
152  QuicFecGroup group;
153
154  QuicPacketHeader header;
155  header.packet_sequence_number = 3;
156  group.Update(ENCRYPTION_FORWARD_SECURE, header, data1);
157
158  QuicFecData fec;
159  fec.fec_group = 1;
160  fec.redundancy = redundancy;
161
162  header.packet_sequence_number = 2;
163  ASSERT_FALSE(group.UpdateFec(ENCRYPTION_FORWARD_SECURE, 2, fec));
164}
165
166TEST_F(QuicFecGroupTest, ProtectsPacketsBefore) {
167  QuicPacketHeader header;
168  header.packet_sequence_number = 3;
169
170  QuicFecGroup group;
171  ASSERT_TRUE(group.Update(ENCRYPTION_FORWARD_SECURE, header, kData[0]));
172
173  EXPECT_FALSE(group.ProtectsPacketsBefore(1));
174  EXPECT_FALSE(group.ProtectsPacketsBefore(2));
175  EXPECT_FALSE(group.ProtectsPacketsBefore(3));
176  EXPECT_TRUE(group.ProtectsPacketsBefore(4));
177  EXPECT_TRUE(group.ProtectsPacketsBefore(5));
178  EXPECT_TRUE(group.ProtectsPacketsBefore(50));
179}
180
181TEST_F(QuicFecGroupTest, ProtectsPacketsBeforeWithSeveralPackets) {
182  QuicPacketHeader header;
183  header.packet_sequence_number = 3;
184
185  QuicFecGroup group;
186  ASSERT_TRUE(group.Update(ENCRYPTION_FORWARD_SECURE, header, kData[0]));
187
188  header.packet_sequence_number = 7;
189  ASSERT_TRUE(group.Update(ENCRYPTION_FORWARD_SECURE, header, kData[0]));
190
191  header.packet_sequence_number = 5;
192  ASSERT_TRUE(group.Update(ENCRYPTION_FORWARD_SECURE, header, kData[0]));
193
194  EXPECT_FALSE(group.ProtectsPacketsBefore(1));
195  EXPECT_FALSE(group.ProtectsPacketsBefore(2));
196  EXPECT_FALSE(group.ProtectsPacketsBefore(3));
197  EXPECT_TRUE(group.ProtectsPacketsBefore(4));
198  EXPECT_TRUE(group.ProtectsPacketsBefore(5));
199  EXPECT_TRUE(group.ProtectsPacketsBefore(6));
200  EXPECT_TRUE(group.ProtectsPacketsBefore(7));
201  EXPECT_TRUE(group.ProtectsPacketsBefore(8));
202  EXPECT_TRUE(group.ProtectsPacketsBefore(9));
203  EXPECT_TRUE(group.ProtectsPacketsBefore(50));
204}
205
206TEST_F(QuicFecGroupTest, ProtectsPacketsBeforeWithFecData) {
207  QuicFecData fec;
208  fec.fec_group = 2;
209  fec.redundancy = kData[0];
210
211  QuicFecGroup group;
212  ASSERT_TRUE(group.UpdateFec(ENCRYPTION_FORWARD_SECURE, 3, fec));
213
214  EXPECT_FALSE(group.ProtectsPacketsBefore(1));
215  EXPECT_FALSE(group.ProtectsPacketsBefore(2));
216  EXPECT_TRUE(group.ProtectsPacketsBefore(3));
217  EXPECT_TRUE(group.ProtectsPacketsBefore(4));
218  EXPECT_TRUE(group.ProtectsPacketsBefore(5));
219  EXPECT_TRUE(group.ProtectsPacketsBefore(50));
220}
221
222TEST_F(QuicFecGroupTest, EffectiveEncryptionLevel) {
223  QuicFecGroup group;
224  EXPECT_EQ(NUM_ENCRYPTION_LEVELS, group.effective_encryption_level());
225
226  QuicPacketHeader header;
227  header.packet_sequence_number = 5;
228  ASSERT_TRUE(group.Update(ENCRYPTION_INITIAL, header, kData[0]));
229  EXPECT_EQ(ENCRYPTION_INITIAL, group.effective_encryption_level());
230
231  QuicFecData fec;
232  fec.fec_group = 0;
233  fec.redundancy = kData[0];
234  ASSERT_TRUE(group.UpdateFec(ENCRYPTION_FORWARD_SECURE, 7, fec));
235  EXPECT_EQ(ENCRYPTION_INITIAL, group.effective_encryption_level());
236
237  header.packet_sequence_number = 3;
238  ASSERT_TRUE(group.Update(ENCRYPTION_NONE, header, kData[0]));
239  EXPECT_EQ(ENCRYPTION_NONE, group.effective_encryption_level());
240}
241
242}  // namespace net
243