First-order-FEC recoverability calculation

webrtc/test/fuzzers/transport_feedback_packet_loss_tracker_fuzzer.cc

Index: webrtc/test/fuzzers/transport_feedback_packet_loss_tracker_fuzzer.cc
diff --git a/webrtc/test/fuzzers/transport_feedback_packet_loss_tracker_fuzzer.cc b/webrtc/test/fuzzers/transport_feedback_packet_loss_tracker_fuzzer.cc
index 837ae883f6c83f213c9951d0f21832d363359cc7..4a08ed5898411a70aef92da1403678260d284efc 100644
--- a/webrtc/test/fuzzers/transport_feedback_packet_loss_tracker_fuzzer.cc
+++ b/webrtc/test/fuzzers/transport_feedback_packet_loss_tracker_fuzzer.cc
@@ -19,6 +19,30 @@ namespace webrtc {
 
 namespace {
 
+template <typename T>
+T FuzzInput(const uint8_t** data, size_t* size) {
+  RTC_CHECK(*size >= sizeof(T));
+  T rc = ByteReader<T>::ReadBigEndian(*data);
+  *data += sizeof(T);
+  *size -= sizeof(T);
+  return rc;
+}
+
+size_t FuzzInRange(const uint8_t** data,

[minyue-webrtc, 2017/01/31 08:28:11]

I see that you want a uniformly distributed value between lower and upper

then you'd better do

static_cast<float>(FuzzInput<uint16_t>(data, size)) / 0xffff * range;

[elad.alon_webrtc.org, 2017/01/31 12:42:23]

Good suggestion, thanks. I'll just modify to 0x10000 instead, to avoid the
highest possible value having a much lower probability than the others. Then
(range + 1) too, to extend the range back to include the highest value.

+                   size_t* size,
+                   size_t lower,
+                   size_t upper) {
+  RTC_CHECK_LE(lower, upper);
+  RTC_CHECK_LT(upper - lower, 1 << (8 * sizeof(uint16_t)));
+  // Decrease the bias created by min-max by making sure we only use the
+  // minimum number of randomized bits necessary.
+  const size_t range = upper - lower;
+  size_t mask = 1;
+  while (mask < range)
+    mask = (mask << 1) | 1;
+  return lower + std::min(FuzzInput<uint16_t>(data, size) & mask, range);
+}
+
 class TransportFeedbackGenerator {
  public:
   explicit TransportFeedbackGenerator(rtc::ArrayView<const uint8_t> data)
@@ -63,7 +87,7 @@ class TransportFeedbackGenerator {
  private:
   template <typename T>
   bool ReadData(T* value) {
-    RTC_DCHECK(!ended_);
+    RTC_CHECK(!ended_);
     if (data_idx_ + sizeof(T) > data_.size()) {
       ended_ = true;
       return false;
@@ -81,25 +105,25 @@ class TransportFeedbackGenerator {
 }  // namespace
 
 void FuzzOneInput(const uint8_t* data, size_t size) {
-  if (size < sizeof(uint32_t)) {
+  if (size < 3 * sizeof(uint16_t)) {
     return;
   }
   constexpr size_t kSeqNumHalf = 0x8000u;
-  const size_t window_size_1 = std::min<size_t>(
-      kSeqNumHalf,
-      std::max<uint16_t>(1, ByteReader<uint16_t>::ReadBigEndian(data)));
-  data += sizeof(uint16_t);
-  const size_t window_size_2 = std::min<size_t>(
-      kSeqNumHalf,
-      std::max<uint16_t>(1, ByteReader<uint16_t>::ReadBigEndian(data)));
-  data += sizeof(uint16_t);
-  size -= 2 * sizeof(uint16_t);
+
+  // 0x8000 >= max_window_size >= plr_min_num_packets > rplr_min_num_pairs >= 1
+  // (The distribution isn't uniform, but it's enough; more would be overkill.)
+  const size_t max_window_size = FuzzInRange(&data, &size, 2, kSeqNumHalf);
+  const size_t plr_min_num_packets =
+      FuzzInRange(&data, &size, 2, max_window_size);
+  const size_t rplr_min_num_pairs =
+      FuzzInRange(&data, &size, 1, plr_min_num_packets - 1);
 
   TransportFeedbackPacketLossTracker tracker(
-      std::min(window_size_1, window_size_2),
-      std::max(window_size_1, window_size_2));
+      max_window_size, plr_min_num_packets, rplr_min_num_pairs);
+
   TransportFeedbackGenerator feedback_generator(
       rtc::ArrayView<const uint8_t>(data, size));
+
   while (!feedback_generator.ended()) {
     rtcp::TransportFeedback feedback;
     feedback_generator.GetNextTransportFeedback(&feedback);