// Copyright 2016 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 "components/cryptauth/eid_generator.h"

#include <cstring>

#include "base/memory/ptr_util.h"
#include "base/strings/string_util.h"
#include "base/sys_byteorder.h"
#include "base/time/default_clock.h"
#include "base/time/time.h"
#include "components/cryptauth/proto/cryptauth_api.pb.h"
#include "components/cryptauth/remote_device.h"
#include "components/proximity_auth/logging/logging.h"
#include "crypto/sha2.h"

namespace cryptauth {

namespace {
const int64_t kNoTimestamp = 0;
const int64_t kMaxPositiveInt64TValue = 0x7FFFFFFF;
}  // namespace

const int64_t EidGenerator::kNumMsInEidPeriod =
    base::TimeDelta::FromHours(8).InMilliseconds();
const int64_t EidGenerator::kNumMsInBeginningOfEidPeriod =
    base::TimeDelta::FromHours(2).InMilliseconds();
const int32_t EidGenerator::kNumBytesInEidValue = 2;
const int8_t EidGenerator::kBluetooth4Flag = 0x01;

// static
EidGenerator* EidGenerator::GetInstance() {
  return base::Singleton<EidGenerator>::get();
}

std::string EidGenerator::EidComputationHelperImpl::GenerateEidDataForDevice(
    const std::string& eid_seed,
    const int64_t start_of_period_timestamp_ms,
    const std::string* extra_entropy) {
  // The data to hash is the eid seed, followed by the extra entropy (if it
  // exists), followed by the timestamp.
  std::string to_hash = eid_seed;
  if (extra_entropy) {
    to_hash += *extra_entropy;
  }
  uint64_t timestamp_data =
      base::HostToNet64(static_cast<uint64_t>(start_of_period_timestamp_ms));
  to_hash.append(reinterpret_cast<char*>(&timestamp_data), sizeof(uint64_t));

  std::string result = crypto::SHA256HashString(to_hash);
  result.resize(EidGenerator::kNumBytesInEidValue);
  return result;
}

EidGenerator::EidData::EidData(const DataWithTimestamp current_data,
                               std::unique_ptr<DataWithTimestamp> adjacent_data)
    : current_data(current_data), adjacent_data(std::move(adjacent_data)) {}

EidGenerator::EidData::~EidData() {}

EidGenerator::EidData::AdjacentDataType
EidGenerator::EidData::GetAdjacentDataType() const {
  if (!adjacent_data) {
    return AdjacentDataType::NONE;
  }

  if (adjacent_data->start_timestamp_ms < current_data.start_timestamp_ms) {
    return AdjacentDataType::PAST;
  }

  return AdjacentDataType::FUTURE;
}

std::string EidGenerator::EidData::DataInHex() const {
  std::string str = "[" + current_data.DataInHex();

  if (adjacent_data) {
    return str + ", " + adjacent_data->DataInHex() + "]";
  }

  return str + "]";
}

EidGenerator::DataWithTimestamp::DataWithTimestamp(
    const std::string& data,
    const int64_t start_timestamp_ms,
    const int64_t end_timestamp_ms)
    : data(data),
      start_timestamp_ms(start_timestamp_ms),
      end_timestamp_ms(end_timestamp_ms) {
  DCHECK(start_timestamp_ms < end_timestamp_ms);
  DCHECK(data.size());
}

EidGenerator::DataWithTimestamp::DataWithTimestamp(
    const DataWithTimestamp& other)
    : data(other.data),
      start_timestamp_ms(other.start_timestamp_ms),
      end_timestamp_ms(other.end_timestamp_ms) {
  DCHECK(start_timestamp_ms < end_timestamp_ms);
  DCHECK(data.size());
}

bool EidGenerator::DataWithTimestamp::ContainsTime(
    const int64_t timestamp_ms) const {
  return start_timestamp_ms <= timestamp_ms && timestamp_ms < end_timestamp_ms;
}

std::string EidGenerator::DataWithTimestamp::DataInHex() const {
  std::stringstream ss;
  ss << "0x" << std::hex;

  for (size_t i = 0; i < data.size(); i++) {
    ss << static_cast<int>(data.data()[i]);
  }

  return ss.str();
}

EidGenerator::EidGenerator()
    : EidGenerator(base::WrapUnique(new EidComputationHelperImpl()),
                   base::WrapUnique(new base::DefaultClock())) {}

EidGenerator::EidGenerator(
    std::unique_ptr<EidComputationHelper> computation_helper,
    std::unique_ptr<base::Clock> clock)
    : clock_(std::move(clock)),
      eid_computation_helper_(std::move(computation_helper)) {}

EidGenerator::~EidGenerator() {}

std::unique_ptr<EidGenerator::EidData>
EidGenerator::GenerateBackgroundScanFilter(
    const std::vector<BeaconSeed>& scanning_device_beacon_seeds) const {
  std::unique_ptr<EidPeriodTimestamps> timestamps =
      GetEidPeriodTimestamps(scanning_device_beacon_seeds);
  if (!timestamps) {
    // If the device does not have seeds for the correct period, no EIDs can be
    // generated.
    return nullptr;
  }

  std::unique_ptr<DataWithTimestamp> current_eid = GenerateEidDataWithTimestamp(
      scanning_device_beacon_seeds,
      timestamps->current_period_start_timestamp_ms,
      timestamps->current_period_end_timestamp_ms);
  if (!current_eid) {
    // The current EID could not be generated.
    return nullptr;
  }

  std::unique_ptr<DataWithTimestamp> adjacent_eid =
      GenerateEidDataWithTimestamp(
          scanning_device_beacon_seeds,
          timestamps->adjacent_period_start_timestamp_ms,
          timestamps->adjacent_period_end_timestamp_ms);
  return base::WrapUnique(new EidData(*current_eid, std::move(adjacent_eid)));
}

std::unique_ptr<EidGenerator::DataWithTimestamp>
EidGenerator::GenerateAdvertisement(
    const std::string& advertising_device_public_key,
    const std::vector<BeaconSeed>& scanning_device_beacon_seeds) const {
  std::unique_ptr<EidPeriodTimestamps> timestamps =
      GetEidPeriodTimestamps(scanning_device_beacon_seeds);
  if (!timestamps) {
    return nullptr;
  }

  return GenerateAdvertisement(advertising_device_public_key,
                               scanning_device_beacon_seeds,
                               timestamps->current_period_start_timestamp_ms,
                               timestamps->current_period_end_timestamp_ms);
}

RemoteDevice const* EidGenerator::IdentifyRemoteDeviceByAdvertisement(
    const std::string& advertisement_service_data,
    const std::vector<RemoteDevice>& device_list,
    const std::vector<BeaconSeed>& scanning_device_beacon_seeds) const {
  // Resize the service data to analyze only the first |2 * kNumBytesInEidValue|
  // bytes. The bytes following these are flags, so they are not needed to
  // identify the device which sent a message.
  std::string service_data_without_flags = advertisement_service_data;
  service_data_without_flags.resize(2 * kNumBytesInEidValue);

  for (const auto& remote_device : device_list) {
    std::vector<std::string> possible_advertisements =
        GeneratePossibleAdvertisements(remote_device.public_key,
                                       scanning_device_beacon_seeds);
    for (const auto& possible_advertisement : possible_advertisements) {
      if (service_data_without_flags == possible_advertisement) {
        return const_cast<RemoteDevice*>(&remote_device);
      }
    }
  }

  return nullptr;
}

std::vector<std::string> EidGenerator::GeneratePossibleAdvertisements(
    const std::string& advertising_device_public_key,
    const std::vector<BeaconSeed>& scanning_device_beacon_seeds) const {
  std::vector<std::string> possible_advertisements;

  std::unique_ptr<EidPeriodTimestamps> timestamps =
      GetEidPeriodTimestamps(scanning_device_beacon_seeds, true);
  if (!timestamps) {
    // If the devices do not have seeds for the correct period, no
    // advertisements can be generated.
    return possible_advertisements;
  }

  if (timestamps->current_period_start_timestamp_ms != kNoTimestamp) {
    std::unique_ptr<DataWithTimestamp> current_advertisement =
        GenerateAdvertisement(advertising_device_public_key,
                              scanning_device_beacon_seeds,
                              timestamps->current_period_start_timestamp_ms,
                              timestamps->current_period_end_timestamp_ms);
    if (current_advertisement) {
      possible_advertisements.push_back(current_advertisement->data);
    }
  }

  std::unique_ptr<DataWithTimestamp> adjacent_advertisement =
      GenerateAdvertisement(advertising_device_public_key,
                            scanning_device_beacon_seeds,
                            timestamps->adjacent_period_start_timestamp_ms,
                            timestamps->adjacent_period_end_timestamp_ms);
  if (adjacent_advertisement) {
    possible_advertisements.push_back(adjacent_advertisement->data);
  }

  return possible_advertisements;
}

std::unique_ptr<EidGenerator::DataWithTimestamp>
EidGenerator::GenerateAdvertisement(
    const std::string& advertising_device_public_key,
    const std::vector<BeaconSeed>& scanning_device_beacon_seeds,
    const int64_t start_of_period_timestamp_ms,
    const int64_t end_of_period_timestamp_ms) const {
  std::unique_ptr<DataWithTimestamp> advertising_device_identifying_data =
      GenerateEidDataWithTimestamp(
          scanning_device_beacon_seeds, start_of_period_timestamp_ms,
          end_of_period_timestamp_ms, &advertising_device_public_key);
  std::unique_ptr<DataWithTimestamp> scanning_device_identifying_data =
      GenerateEidDataWithTimestamp(scanning_device_beacon_seeds,
                                   start_of_period_timestamp_ms,
                                   end_of_period_timestamp_ms);
  if (!advertising_device_identifying_data ||
      !scanning_device_identifying_data) {
    return nullptr;
  }

  std::string full_advertisement = scanning_device_identifying_data->data +
                                   advertising_device_identifying_data->data;
  return base::WrapUnique(new DataWithTimestamp(full_advertisement,
                                                start_of_period_timestamp_ms,
                                                end_of_period_timestamp_ms));
}

std::unique_ptr<EidGenerator::DataWithTimestamp>
EidGenerator::GenerateEidDataWithTimestamp(
    const std::vector<BeaconSeed>& scanning_device_beacon_seeds,
    const int64_t start_of_period_timestamp_ms,
    const int64_t end_of_period_timestamp_ms) const {
  return GenerateEidDataWithTimestamp(scanning_device_beacon_seeds,
                                      start_of_period_timestamp_ms,
                                      end_of_period_timestamp_ms, nullptr);
}

std::unique_ptr<EidGenerator::DataWithTimestamp>
EidGenerator::GenerateEidDataWithTimestamp(
    const std::vector<BeaconSeed>& scanning_device_beacon_seeds,
    const int64_t start_of_period_timestamp_ms,
    const int64_t end_of_period_timestamp_ms,
    const std::string* extra_entropy) const {
  std::unique_ptr<std::string> eid_seed = GetEidSeedForPeriod(
      scanning_device_beacon_seeds, start_of_period_timestamp_ms);
  if (!eid_seed) {
    return nullptr;
  }

  std::string eid_data = eid_computation_helper_->GenerateEidDataForDevice(
      *eid_seed, start_of_period_timestamp_ms, extra_entropy);

  return base::WrapUnique(new DataWithTimestamp(
      eid_data, start_of_period_timestamp_ms, end_of_period_timestamp_ms));
}

std::unique_ptr<std::string> EidGenerator::GetEidSeedForPeriod(
    const std::vector<BeaconSeed>& scanning_device_beacon_seeds,
    const int64_t start_of_period_timestamp_ms) const {
  for (auto seed : scanning_device_beacon_seeds) {
    if (seed.start_time_millis() <= start_of_period_timestamp_ms &&
        start_of_period_timestamp_ms < seed.end_time_millis()) {
      return base::WrapUnique(new std::string(seed.data()));
    }
  }

  return nullptr;
}

std::unique_ptr<EidGenerator::EidPeriodTimestamps>
EidGenerator::GetEidPeriodTimestamps(
    const std::vector<BeaconSeed>& scanning_device_beacon_seeds) const {
  return GetEidPeriodTimestamps(scanning_device_beacon_seeds, false);
}

std::unique_ptr<EidGenerator::EidPeriodTimestamps>
EidGenerator::GetEidPeriodTimestamps(
    const std::vector<BeaconSeed>& scanning_device_beacon_seeds,
    const bool allow_non_current_periods) const {
  base::Time now = clock_->Now();
  int64_t current_time_ms = now.ToJavaTime();

  std::unique_ptr<BeaconSeed> current_seed = GetBeaconSeedForCurrentPeriod(
      scanning_device_beacon_seeds, current_time_ms);
  if (!current_seed) {
    if (!allow_non_current_periods) {
      // No seed existed for the current time.
      return nullptr;
    }

    return GetClosestPeriod(scanning_device_beacon_seeds, current_time_ms);
  }

  // Now that the start of the 14-day EID seed period has been determined, the
  // current EID period must be determined.
  for (int64_t start_of_eid_period_ms = current_seed->start_time_millis();
       start_of_eid_period_ms <= current_seed->end_time_millis();
       start_of_eid_period_ms += kNumMsInEidPeriod) {
    int64_t end_of_eid_period_ms = start_of_eid_period_ms + kNumMsInEidPeriod;
    if (start_of_eid_period_ms <= current_time_ms &&
        current_time_ms < end_of_eid_period_ms) {
      int64_t start_of_adjacent_period_ms;
      int64_t end_of_adjacent_period_ms;
      if (IsCurrentTimeAtStartOfEidPeriod(
              start_of_eid_period_ms, end_of_eid_period_ms, current_time_ms)) {
        // If the current time is at the beginning of the period, the "adjacent
        // period" is the period before this one.
        start_of_adjacent_period_ms =
            start_of_eid_period_ms - kNumMsInEidPeriod;
        end_of_adjacent_period_ms = start_of_eid_period_ms;
      } else {
        // Otherwise, the "adjacent period" is the one after this one.
        start_of_adjacent_period_ms = end_of_eid_period_ms;
        end_of_adjacent_period_ms = end_of_eid_period_ms + kNumMsInEidPeriod;
      }

      return base::WrapUnique(new EidPeriodTimestamps{
          start_of_eid_period_ms, end_of_eid_period_ms,
          start_of_adjacent_period_ms, end_of_adjacent_period_ms});
    }
  }

  PA_LOG(ERROR) << "Could not find valid EID period for seed. "
                << "seed.start_timestamp_ms: "
                << current_seed->start_time_millis()
                << ", seed.end_timestamp_ms: "
                << current_seed->end_time_millis();
  NOTREACHED();
  return nullptr;
}

std::unique_ptr<BeaconSeed> EidGenerator::GetBeaconSeedForCurrentPeriod(
    const std::vector<BeaconSeed>& scanning_device_beacon_seeds,
    const int64_t current_time_ms) const {
  for (auto seed : scanning_device_beacon_seeds) {
    int64_t seed_period_length_ms =
        seed.end_time_millis() - seed.start_time_millis();
    if (seed_period_length_ms % kNumMsInEidPeriod != 0) {
      PA_LOG(WARNING) << "Seed has period length which is not an multiple of "
                      << "the rotation length.";
      continue;
    }

    if (seed.start_time_millis() <= current_time_ms &&
        current_time_ms < seed.end_time_millis()) {
      return base::WrapUnique(new BeaconSeed(seed));
    }
  }

  return nullptr;
}

std::unique_ptr<EidGenerator::EidPeriodTimestamps>
EidGenerator::GetClosestPeriod(
    const std::vector<BeaconSeed>& scanning_device_beacon_seeds,
    const int64_t current_time_ms) const {
  int64_t smallest_diff_so_far_ms = kMaxPositiveInt64TValue;
  int64_t start_of_period_timestamp_ms = kMaxPositiveInt64TValue;
  int64_t end_of_period_timestamp_ms = 0;

  for (auto seed : scanning_device_beacon_seeds) {
    int64_t seed_period_length_ms =
        seed.end_time_millis() - seed.start_time_millis();
    if (seed_period_length_ms % kNumMsInEidPeriod != 0) {
      PA_LOG(WARNING) << "Seed has period length which is not an multiple of "
                      << "the rotation length.";
      continue;
    }

    DCHECK(seed.start_time_millis() > current_time_ms ||
           current_time_ms >= seed.end_time_millis());

    if (seed.start_time_millis() > current_time_ms) {
      int64_t diff = seed.start_time_millis() - current_time_ms;
      if (diff < smallest_diff_so_far_ms) {
        smallest_diff_so_far_ms = diff;
        start_of_period_timestamp_ms = seed.start_time_millis();
        end_of_period_timestamp_ms =
            seed.start_time_millis() + kNumMsInEidPeriod;
      }
    } else if (seed.end_time_millis() <= current_time_ms) {
      int64_t diff = current_time_ms - seed.end_time_millis();
      if (diff < smallest_diff_so_far_ms) {
        smallest_diff_so_far_ms = diff;
        end_of_period_timestamp_ms = seed.end_time_millis();
        start_of_period_timestamp_ms =
            end_of_period_timestamp_ms - kNumMsInEidPeriod;
      }
    }
  }

  if (smallest_diff_so_far_ms < kMaxPositiveInt64TValue &&
      smallest_diff_so_far_ms > kNumMsInEidPeriod) {
    return nullptr;
  }

  return base::WrapUnique(new EidPeriodTimestamps{
      kNoTimestamp,  // current_period_start_timestamp_ms is unused.
      kNoTimestamp,  // current_period_end_timestamp_ms is unused.
      start_of_period_timestamp_ms, end_of_period_timestamp_ms});
}

bool EidGenerator::IsCurrentTimeAtStartOfEidPeriod(
    const int64_t start_of_period_timestamp_ms,
    const int64_t end_of_period_timestamp_ms,
    const int64_t current_timestamp_ms) {
  DCHECK(start_of_period_timestamp_ms <= current_timestamp_ms);
  DCHECK(current_timestamp_ms < end_of_period_timestamp_ms);

  return current_timestamp_ms <
         start_of_period_timestamp_ms + kNumMsInBeginningOfEidPeriod;
}

}  // namespace cryptauth