// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "net/spdy/fuzzing/hpack_fuzz_util.h"

#include <algorithm>
#include <cmath>

#include "base/rand_util.h"
#include "base/sys_byteorder.h"
#include "net/spdy/hpack_constants.h"

namespace net {

namespace {

// Sampled exponential distribution parameters:
// Number of headers in each header set.
const size_t kHeaderCountMean = 7;
const size_t kHeaderCountMax = 50;
// Selected index within list of headers.
const size_t kHeaderIndexMean = 20;
const size_t kHeaderIndexMax = 200;
// Approximate distribution of header name lengths.
const size_t kNameLengthMean = 5;
const size_t kNameLengthMax = 30;
// Approximate distribution of header value lengths.
const size_t kValueLengthMean = 15;
const size_t kValueLengthMax = 75;

}  //  namespace

using base::StringPiece;
using base::RandBytesAsString;
using std::map;
using std::string;

HpackFuzzUtil::GeneratorContext::GeneratorContext() {}
HpackFuzzUtil::GeneratorContext::~GeneratorContext() {}

HpackFuzzUtil::Input::Input() : offset(0) {}
HpackFuzzUtil::Input::~Input() {}

HpackFuzzUtil::FuzzerContext::FuzzerContext() {}
HpackFuzzUtil::FuzzerContext::~FuzzerContext() {}

// static
void HpackFuzzUtil::InitializeGeneratorContext(GeneratorContext* context) {
  // Seed the generator with common header fixtures.
  context->names.push_back(":authority");
  context->names.push_back(":path");
  context->names.push_back(":status");
  context->names.push_back("cookie");
  context->names.push_back("content-type");
  context->names.push_back("cache-control");
  context->names.push_back("date");
  context->names.push_back("user-agent");
  context->names.push_back("via");

  context->values.push_back("/");
  context->values.push_back("/index.html");
  context->values.push_back("200");
  context->values.push_back("404");
  context->values.push_back("");
  context->values.push_back("baz=bing; foo=bar; garbage");
  context->values.push_back("baz=bing; fizzle=fazzle; garbage");
  context->values.push_back("rudolph=the-red-nosed-reindeer");
  context->values.push_back("had=a;very_shiny=nose");
  context->values.push_back("and\0if\0you\0ever\1saw\0it;");
  context->values.push_back("u; would=even;say-it\xffglows");
}

// static
map<string, string> HpackFuzzUtil::NextGeneratedHeaderSet(
    GeneratorContext* context) {
  map<string, string> headers;

  size_t header_count = 1 + SampleExponential(kHeaderCountMean,
                                              kHeaderCountMax);
  for (size_t j = 0; j != header_count; ++j) {
    size_t name_index = SampleExponential(kHeaderIndexMean,
                                          kHeaderIndexMax);
    size_t value_index = SampleExponential(kHeaderIndexMean,
                                           kHeaderIndexMax);
    string name, value;
    if (name_index >= context->names.size()) {
      context->names.push_back(
          RandBytesAsString(1 + SampleExponential(kNameLengthMean,
                                                  kNameLengthMax)));
      name = context->names.back();
    } else {
      name = context->names[name_index];
    }
    if (value_index >= context->values.size()) {
      context->values.push_back(
          RandBytesAsString(1 + SampleExponential(kValueLengthMean,
                                                  kValueLengthMax)));
      value = context->values.back();
    } else {
      value = context->values[value_index];
    }
    headers[name] = value;
  }
  return headers;
}

// static
size_t HpackFuzzUtil::SampleExponential(size_t mean, size_t sanity_bound) {
  return std::min(static_cast<size_t>(-std::log(base::RandDouble()) * mean),
                  sanity_bound);
}

// static
bool HpackFuzzUtil::NextHeaderBlock(Input* input,
                                    StringPiece* out) {
  // ClusterFuzz may truncate input files if the fuzzer ran out of allocated
  // disk space. Be tolerant of these.
  CHECK_LE(input->offset, input->input.size());
  if (input->remaining() < sizeof(uint32)) {
    return false;
  }

  size_t length = ntohl(*reinterpret_cast<const uint32*>(input->ptr()));
  input->offset += sizeof(uint32);

  if (input->remaining() < length) {
    return false;
  }
  *out = StringPiece(input->ptr(), length);
  input->offset += length;
  return true;
}

// static
string HpackFuzzUtil::HeaderBlockPrefix(size_t block_size) {
  uint32 length = htonl(block_size);
  return string(reinterpret_cast<char*>(&length), sizeof(uint32));
}

// static
void HpackFuzzUtil::InitializeFuzzerContext(FuzzerContext* context) {
  context->first_stage.reset(new HpackDecoder(ObtainHpackHuffmanTable()));
  context->second_stage.reset(new HpackEncoder(ObtainHpackHuffmanTable()));
  context->third_stage.reset(new HpackDecoder(ObtainHpackHuffmanTable()));
}

// static
bool HpackFuzzUtil::RunHeaderBlockThroughFuzzerStages(FuzzerContext* context,
                                                      StringPiece input_block) {
  // First stage: Decode the input header block. This may fail on invalid input.
  if (!context->first_stage->HandleControlFrameHeadersData(
      1, input_block.data(), input_block.size())) {
    return false;
  }
  if (!context->first_stage->HandleControlFrameHeadersComplete(1)) {
    return false;
  }
  // Second stage: Re-encode the decoded header block. This must succeed.
  string second_stage_out;
  CHECK(context->second_stage->EncodeHeaderSet(
      context->first_stage->decoded_block(), &second_stage_out));

  // Third stage: Expect a decoding of the re-encoded block to succeed, but
  // don't require it. It's possible for the stage-two encoder to produce an
  // output which violates decoder size tolerances.
  if (!context->third_stage->HandleControlFrameHeadersData(
          1, second_stage_out.data(), second_stage_out.length())) {
    return false;
  }
  if (!context->third_stage->HandleControlFrameHeadersComplete(1)) {
    return false;
  }
  return true;
}

// static
void HpackFuzzUtil::FlipBits(uint8* buffer, size_t buffer_length,
                             size_t flip_per_thousand) {
  uint64 buffer_bit_length = buffer_length * 8u;
  uint64 bits_to_flip = flip_per_thousand * (1 + buffer_bit_length / 1024);

  // Iteratively identify & flip offsets in the buffer bit-sequence.
  for (uint64 i = 0; i != bits_to_flip; ++i) {
    uint64 bit_offset = base::RandUint64() % buffer_bit_length;
    buffer[bit_offset / 8u] ^= (1 << (bit_offset % 8u));
  }
}

}  // namespace net