diff options
Diffstat (limited to 'protocols/Telegram/tdlib/td/tdutils/test')
33 files changed, 5256 insertions, 342 deletions
diff --git a/protocols/Telegram/tdlib/td/tdutils/test/ChainScheduler.cpp b/protocols/Telegram/tdlib/td/tdutils/test/ChainScheduler.cpp new file mode 100644 index 0000000000..d3bcb934fc --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/ChainScheduler.cpp @@ -0,0 +1,244 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/algorithm.h" +#include "td/utils/ChainScheduler.h" +#include "td/utils/common.h" +#include "td/utils/logging.h" +#include "td/utils/misc.h" +#include "td/utils/Random.h" +#include "td/utils/Span.h" +#include "td/utils/StringBuilder.h" +#include "td/utils/tests.h" + +#include <memory> +#include <numeric> + +TEST(ChainScheduler, CreateAfterActive) { + td::ChainScheduler<int> scheduler; + td::vector<td::ChainScheduler<int>::ChainId> chains{1}; + + auto first_task_id = scheduler.create_task(chains, 1); + ASSERT_EQ(first_task_id, scheduler.start_next_task().unwrap().task_id); + auto second_task_id = scheduler.create_task(chains, 2); + ASSERT_EQ(second_task_id, scheduler.start_next_task().unwrap().task_id); +} + +TEST(ChainScheduler, RestartAfterActive) { + td::ChainScheduler<int> scheduler; + std::vector<td::ChainScheduler<int>::ChainId> chains{1}; + + auto first_task_id = scheduler.create_task(chains, 1); + auto second_task_id = scheduler.create_task(chains, 2); + ASSERT_EQ(first_task_id, scheduler.start_next_task().unwrap().task_id); + ASSERT_EQ(second_task_id, scheduler.start_next_task().unwrap().task_id); + + scheduler.reset_task(first_task_id); + ASSERT_EQ(first_task_id, scheduler.start_next_task().unwrap().task_id); + + scheduler.reset_task(second_task_id); + ASSERT_EQ(second_task_id, scheduler.start_next_task().unwrap().task_id); +} + +TEST(ChainScheduler, SendAfterRestart) { + td::ChainScheduler<int> scheduler; + std::vector<td::ChainScheduler<int>::ChainId> chains{1}; + + auto first_task_id = scheduler.create_task(chains, 1); + auto second_task_id = scheduler.create_task(chains, 2); + ASSERT_EQ(first_task_id, scheduler.start_next_task().unwrap().task_id); + ASSERT_EQ(second_task_id, scheduler.start_next_task().unwrap().task_id); + + scheduler.reset_task(first_task_id); + + scheduler.create_task(chains, 3); + + ASSERT_EQ(first_task_id, scheduler.start_next_task().unwrap().task_id); + ASSERT_TRUE(!scheduler.start_next_task()); +} + +TEST(ChainScheduler, Basic) { + td::ChainScheduler<int> scheduler; + for (int i = 0; i < 100; i++) { + scheduler.create_task({td::ChainScheduler<int>::ChainId{1}}, i); + } + int j = 0; + while (j != 100) { + td::vector<td::ChainScheduler<int>::TaskId> tasks; + while (true) { + auto o_task_id = scheduler.start_next_task(); + if (!o_task_id) { + break; + } + auto task_id = o_task_id.value().task_id; + auto extra = *scheduler.get_task_extra(task_id); + auto parents = + td::transform(o_task_id.value().parents, [&](auto parent) { return *scheduler.get_task_extra(parent); }); + LOG(INFO) << "Start " << extra << parents; + CHECK(extra == j); + j++; + tasks.push_back(task_id); + } + for (auto &task_id : tasks) { + auto extra = *scheduler.get_task_extra(task_id); + LOG(INFO) << "Finish " << extra; + scheduler.finish_task(task_id); + } + } +} + +struct ChainSchedulerQuery; +using QueryPtr = std::shared_ptr<ChainSchedulerQuery>; +using ChainId = td::ChainScheduler<QueryPtr>::ChainId; +using TaskId = td::ChainScheduler<QueryPtr>::TaskId; + +struct ChainSchedulerQuery { + int id{}; + TaskId task_id{}; + bool is_ok{}; + bool skipped{}; +}; + +TEST(ChainScheduler, Stress) { + td::Random::Xorshift128plus rnd(123); + int max_query_id = 100000; + int MAX_INFLIGHT_QUERIES = 20; + int ChainsN = 4; + + struct QueryWithParents { + TaskId task_id; + QueryPtr id; + td::vector<QueryPtr> parents; + }; + td::vector<QueryWithParents> active_queries; + + td::ChainScheduler<QueryPtr> scheduler; + td::vector<td::vector<QueryPtr>> chains(ChainsN); + int inflight_queries{}; + int current_query_id{}; + int sent_cnt{}; + bool done = false; + std::vector<TaskId> pending_queries; + + auto schedule_new_query = [&] { + if (current_query_id > max_query_id) { + if (inflight_queries == 0) { + done = true; + } + return; + } + if (inflight_queries >= MAX_INFLIGHT_QUERIES) { + return; + } + auto query_id = current_query_id++; + auto query = std::make_shared<ChainSchedulerQuery>(); + query->id = query_id; + int chain_n = rnd.fast(1, ChainsN); + td::vector<ChainId> chain_ids(ChainsN); + std::iota(chain_ids.begin(), chain_ids.end(), 0); + td::random_shuffle(td::as_mutable_span(chain_ids), rnd); + chain_ids.resize(chain_n); + for (auto chain_id : chain_ids) { + chains[td::narrow_cast<size_t>(chain_id)].push_back(query); + } + auto task_id = scheduler.create_task(chain_ids, query); + query->task_id = task_id; + pending_queries.push_back(task_id); + inflight_queries++; + }; + + auto check_parents_ok = [&](const QueryWithParents &query_with_parents) -> bool { + return td::all_of(query_with_parents.parents, [](auto &parent) { return parent->is_ok; }); + }; + + auto to_query_ptr = [&](TaskId task_id) { + return *scheduler.get_task_extra(task_id); + }; + auto flush_pending_queries = [&] { + while (true) { + auto o_task_with_parents = scheduler.start_next_task(); + if (!o_task_with_parents) { + break; + } + auto task_with_parents = o_task_with_parents.unwrap(); + QueryWithParents query_with_parents; + query_with_parents.task_id = task_with_parents.task_id; + query_with_parents.id = to_query_ptr(task_with_parents.task_id); + query_with_parents.parents = td::transform(task_with_parents.parents, to_query_ptr); + active_queries.push_back(query_with_parents); + sent_cnt++; + } + }; + auto skip_one_query = [&] { + if (pending_queries.empty()) { + return; + } + auto it = pending_queries.begin() + rnd.fast(0, static_cast<int>(pending_queries.size()) - 1); + auto task_id = *it; + pending_queries.erase(it); + td::remove_if(active_queries, [&](auto &q) { return q.task_id == task_id; }); + + auto query = *scheduler.get_task_extra(task_id); + query->skipped = true; + scheduler.finish_task(task_id); + inflight_queries--; + LOG(INFO) << "Skip " << query->id; + }; + auto execute_one_query = [&] { + if (active_queries.empty()) { + return; + } + auto it = active_queries.begin() + rnd.fast(0, static_cast<int>(active_queries.size()) - 1); + auto query_with_parents = *it; + active_queries.erase(it); + + auto query = query_with_parents.id; + if (rnd.fast(0, 20) == 0) { + scheduler.finish_task(query->task_id); + td::remove(pending_queries, query->task_id); + inflight_queries--; + LOG(INFO) << "Fail " << query->id; + } else if (check_parents_ok(query_with_parents)) { + query->is_ok = true; + scheduler.finish_task(query->task_id); + td::remove(pending_queries, query->task_id); + inflight_queries--; + LOG(INFO) << "OK " << query->id; + } else { + scheduler.reset_task(query->task_id); + LOG(INFO) << "Reset " << query->id; + } + }; + + td::RandomSteps steps({{schedule_new_query, 100}, {execute_one_query, 100}, {skip_one_query, 10}}); + while (!done) { + steps.step(rnd); + flush_pending_queries(); + // LOG(INFO) << scheduler; + } + LOG(INFO) << "Sent queries count " << sent_cnt; + LOG(INFO) << "Total queries " << current_query_id; + for (auto &chain : chains) { + int prev_ok = -1; + int failed_cnt = 0; + int ok_cnt = 0; + int skipped_cnt = 0; + for (auto &q : chain) { + if (q->is_ok) { + CHECK(prev_ok < q->id); + prev_ok = q->id; + ok_cnt++; + } else { + if (q->skipped) { + skipped_cnt++; + } else { + failed_cnt++; + } + } + } + LOG(INFO) << "Chain ok " << ok_cnt << " failed " << failed_cnt << " skipped " << skipped_cnt; + } +} diff --git a/protocols/Telegram/tdlib/td/tdutils/test/ConcurrentHashMap.cpp b/protocols/Telegram/tdlib/td/tdutils/test/ConcurrentHashMap.cpp new file mode 100644 index 0000000000..a90f11d525 --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/ConcurrentHashMap.cpp @@ -0,0 +1,252 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/benchmark.h" +#include "td/utils/common.h" +#include "td/utils/ConcurrentHashTable.h" +#include "td/utils/HashTableUtils.h" +#include "td/utils/misc.h" +#include "td/utils/port/Mutex.h" +#include "td/utils/port/thread.h" +#include "td/utils/SpinLock.h" +#include "td/utils/tests.h" + +#include <atomic> + +#if !TD_THREAD_UNSUPPORTED + +#if TD_HAVE_ABSL +#include <absl/container/flat_hash_map.h> +#else +#include <unordered_map> +#endif + +#if TD_WITH_LIBCUCKOO +#include <third-party/libcuckoo/libcuckoo/cuckoohash_map.hh> +#endif + +#if TD_WITH_JUNCTION +#include <junction/ConcurrentMap_Grampa.h> +#include <junction/ConcurrentMap_Leapfrog.h> +#include <junction/ConcurrentMap_Linear.h> +#endif + +// Non resizable HashMap. Just an example +template <class KeyT, class ValueT> +class ArrayHashMap { + public: + explicit ArrayHashMap(std::size_t n) : array_(n) { + } + struct Node { + std::atomic<KeyT> key{KeyT{}}; + std::atomic<ValueT> value{ValueT{}}; + }; + static td::string get_name() { + return "ArrayHashMap"; + } + KeyT empty_key() const { + return KeyT{}; + } + + void insert(KeyT key, ValueT value) { + array_.with_value(key, true, [&](auto &node_value) { node_value.store(value, std::memory_order_release); }); + } + ValueT find(KeyT key, ValueT value) { + array_.with_value(key, false, [&](auto &node_value) { value = node_value.load(std::memory_order_acquire); }); + return value; + } + + private: + td::AtomicHashArray<KeyT, std::atomic<ValueT>> array_; +}; + +template <class KeyT, class ValueT> +class ConcurrentHashMapMutex { + public: + explicit ConcurrentHashMapMutex(std::size_t) { + } + static td::string get_name() { + return "ConcurrentHashMapMutex"; + } + void insert(KeyT key, ValueT value) { + auto guard = mutex_.lock(); + hash_map_.emplace(key, value); + } + ValueT find(KeyT key, ValueT default_value) { + auto guard = mutex_.lock(); + auto it = hash_map_.find(key); + if (it == hash_map_.end()) { + return default_value; + } + return it->second; + } + + private: + td::Mutex mutex_; +#if TD_HAVE_ABSL + absl::flat_hash_map<KeyT, ValueT> hash_map_; +#else + std::unordered_map<KeyT, ValueT, td::Hash<KeyT>> hash_map_; +#endif +}; + +template <class KeyT, class ValueT> +class ConcurrentHashMapSpinlock { + public: + explicit ConcurrentHashMapSpinlock(size_t) { + } + static td::string get_name() { + return "ConcurrentHashMapSpinlock"; + } + void insert(KeyT key, ValueT value) { + auto guard = spinlock_.lock(); + hash_map_.emplace(key, value); + } + ValueT find(KeyT key, ValueT default_value) { + auto guard = spinlock_.lock(); + auto it = hash_map_.find(key); + if (it == hash_map_.end()) { + return default_value; + } + return it->second; + } + + private: + td::SpinLock spinlock_; +#if TD_HAVE_ABSL + absl::flat_hash_map<KeyT, ValueT> hash_map_; +#else + std::unordered_map<KeyT, ValueT, td::Hash<KeyT>> hash_map_; +#endif +}; + +#if TD_WITH_LIBCUCKOO +template <class KeyT, class ValueT> +class ConcurrentHashMapLibcuckoo { + public: + explicit ConcurrentHashMapLibcuckoo(size_t) { + } + static td::string get_name() { + return "ConcurrentHashMapLibcuckoo"; + } + void insert(KeyT key, ValueT value) { + hash_map_.insert(key, value); + } + ValueT find(KeyT key, ValueT default_value) { + hash_map_.find(key, default_value); + return default_value; + } + + private: + cuckoohash_map<KeyT, ValueT> hash_map_; +}; +#endif + +#if TD_WITH_JUNCTION +template <class KeyT, class ValueT> +class ConcurrentHashMapJunction { + public: + explicit ConcurrentHashMapJunction(std::size_t size) : hash_map_() { + } + static td::string get_name() { + return "ConcurrentHashMapJunction"; + } + void insert(KeyT key, ValueT value) { + hash_map_.assign(key, value); + } + ValueT find(KeyT key, ValueT default_value) { + return hash_map_.get(key); + } + + ConcurrentHashMapJunction(const ConcurrentHashMapJunction &) = delete; + ConcurrentHashMapJunction &operator=(const ConcurrentHashMapJunction &) = delete; + ConcurrentHashMapJunction(ConcurrentHashMapJunction &&other) = delete; + ConcurrentHashMapJunction &operator=(ConcurrentHashMapJunction &&) = delete; + ~ConcurrentHashMapJunction() { + junction::DefaultQSBR.flush(); + } + + private: + junction::ConcurrentMap_Leapfrog<KeyT, ValueT> hash_map_; +}; +#endif + +template <class HashMap> +class HashMapBenchmark final : public td::Benchmark { + struct Query { + int key; + int value; + }; + td::vector<Query> queries; + td::unique_ptr<HashMap> hash_map; + + std::size_t threads_n = 16; + static constexpr std::size_t MUL = 7273; //1000000000 + 7; + int n_ = 0; + + public: + explicit HashMapBenchmark(std::size_t threads_n) : threads_n(threads_n) { + } + td::string get_description() const final { + return HashMap::get_name(); + } + void start_up_n(int n) final { + n *= static_cast<int>(threads_n); + n_ = n; + hash_map = td::make_unique<HashMap>(n * 2); + } + + void run(int n) final { + n = n_; + td::vector<td::thread> threads; + + for (std::size_t i = 0; i < threads_n; i++) { + std::size_t l = n * i / threads_n; + std::size_t r = n * (i + 1) / threads_n; + threads.emplace_back([l, r, this] { + for (size_t i = l; i < r; i++) { + auto x = td::narrow_cast<int>((i + 1) * MUL % n_) + 3; + auto y = td::narrow_cast<int>(i + 2); + hash_map->insert(x, y); + } + }); + } + for (auto &thread : threads) { + thread.join(); + } + } + + void tear_down() final { + for (int i = 0; i < n_; i++) { + auto x = td::narrow_cast<int>((i + 1) * MUL % n_) + 3; + auto y = td::narrow_cast<int>(i + 2); + ASSERT_EQ(y, hash_map->find(x, -1)); + } + queries.clear(); + hash_map.reset(); + } +}; + +template <class HashMap> +static void bench_hash_map() { + td::bench(HashMapBenchmark<HashMap>(16)); + td::bench(HashMapBenchmark<HashMap>(1)); +} + +TEST(ConcurrentHashMap, Benchmark) { + bench_hash_map<td::ConcurrentHashMap<td::int32, td::int32>>(); + bench_hash_map<ArrayHashMap<td::int32, td::int32>>(); + bench_hash_map<ConcurrentHashMapSpinlock<td::int32, td::int32>>(); + bench_hash_map<ConcurrentHashMapMutex<td::int32, td::int32>>(); +#if TD_WITH_LIBCUCKOO + bench_hash_map<ConcurrentHashMapLibcuckoo<td::int32, td::int32>>(); +#endif +#if TD_WITH_JUNCTION + bench_hash_map<ConcurrentHashMapJunction<td::int32, td::int32>>(); +#endif +} + +#endif diff --git a/protocols/Telegram/tdlib/td/tdutils/test/Enumerator.cpp b/protocols/Telegram/tdlib/td/tdutils/test/Enumerator.cpp index b617485462..210ab415cc 100644 --- a/protocols/Telegram/tdlib/td/tdutils/test/Enumerator.cpp +++ b/protocols/Telegram/tdlib/td/tdutils/test/Enumerator.cpp @@ -1,5 +1,5 @@ // -// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2018 +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) diff --git a/protocols/Telegram/tdlib/td/tdutils/test/EpochBasedMemoryReclamation.cpp b/protocols/Telegram/tdlib/td/tdutils/test/EpochBasedMemoryReclamation.cpp new file mode 100644 index 0000000000..c97679bb83 --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/EpochBasedMemoryReclamation.cpp @@ -0,0 +1,68 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/common.h" +#include "td/utils/EpochBasedMemoryReclamation.h" +#include "td/utils/logging.h" +#include "td/utils/port/thread.h" +#include "td/utils/Random.h" +#include "td/utils/tests.h" + +#include <atomic> + +#if !TD_THREAD_UNSUPPORTED +TEST(EpochBaseMemoryReclamation, stress) { + struct Node { + std::atomic<std::string *> name_{nullptr}; + char pad[64]; + }; + + int threads_n = 10; + std::vector<Node> nodes(threads_n); + td::EpochBasedMemoryReclamation<std::string> ebmr(threads_n + 1); + auto locker = ebmr.get_locker(threads_n); + locker.lock(); + locker.unlock(); + std::vector<td::thread> threads(threads_n); + int thread_id = 0; + for (auto &thread : threads) { + thread = td::thread([&, thread_id] { + auto locker = ebmr.get_locker(thread_id); + locker.lock(); + for (int i = 0; i < 1000000; i++) { + auto &node = nodes[td::Random::fast(0, threads_n - 1)]; + auto *str = node.name_.load(std::memory_order_acquire); + if (str) { + CHECK(*str == "one" || *str == "twotwo"); + } + if ((i + 1) % 100 == 0) { + locker.retire(); + } + if (td::Random::fast(0, 5) == 0) { + auto *new_str = new td::string(td::Random::fast_bool() ? "one" : "twotwo"); + if (node.name_.compare_exchange_strong(str, new_str, std::memory_order_acq_rel)) { + locker.retire(str); + } else { + delete new_str; + } + } + } + locker.retire_sync(); + locker.unlock(); + }); + thread_id++; + } + for (auto &thread : threads) { + thread.join(); + } + LOG(INFO) << "Undeleted pointers: " << ebmr.to_delete_size_unsafe(); + //CHECK(static_cast<int>(ebmr.to_delete_size_unsafe()) <= threads_n * threads_n); + for (int i = 0; i < threads_n; i++) { + ebmr.get_locker(i).retire_sync(); + } + CHECK(ebmr.to_delete_size_unsafe() == 0); +} +#endif diff --git a/protocols/Telegram/tdlib/td/tdutils/test/HashSet.cpp b/protocols/Telegram/tdlib/td/tdutils/test/HashSet.cpp new file mode 100644 index 0000000000..94ebf8733b --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/HashSet.cpp @@ -0,0 +1,438 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/algorithm.h" +#include "td/utils/common.h" +#include "td/utils/FlatHashMap.h" +#include "td/utils/FlatHashMapChunks.h" +#include "td/utils/FlatHashSet.h" +#include "td/utils/HashTableUtils.h" +#include "td/utils/logging.h" +#include "td/utils/Random.h" +#include "td/utils/Slice.h" +#include "td/utils/tests.h" + +#include <algorithm> +#include <array> +#include <random> +#include <unordered_map> +#include <unordered_set> +#include <utility> + +template <class T> +static auto extract_kv(const T &reference) { + auto expected = td::transform(reference, [](auto &it) { return std::make_pair(it.first, it.second); }); + std::sort(expected.begin(), expected.end()); + return expected; +} + +template <class T> +static auto extract_k(const T &reference) { + auto expected = td::transform(reference, [](auto &it) { return it; }); + std::sort(expected.begin(), expected.end()); + return expected; +} + +TEST(FlatHashMapChunks, basic) { + td::FlatHashMapChunks<int, int> kv; + kv[5] = 3; + ASSERT_EQ(3, kv[5]); + kv[3] = 4; + ASSERT_EQ(4, kv[3]); +} + +TEST(FlatHashMap, probing) { + auto test = [](int buckets, int elements) { + CHECK(buckets >= elements); + td::vector<bool> data(buckets, false); + std::random_device rnd; + std::mt19937 mt(rnd()); + std::uniform_int_distribution<td::int32> d(0, buckets - 1); + for (int i = 0; i < elements; i++) { + int pos = d(mt); + while (data[pos]) { + pos++; + if (pos == buckets) { + pos = 0; + } + } + data[pos] = true; + } + int max_chain = 0; + int cur_chain = 0; + for (auto x : data) { + if (x) { + cur_chain++; + max_chain = td::max(max_chain, cur_chain); + } else { + cur_chain = 0; + } + } + LOG(INFO) << "Buckets=" << buckets << " elements=" << elements << " max_chain=" << max_chain; + }; + test(8192, static_cast<int>(8192 * 0.8)); + test(8192, static_cast<int>(8192 * 0.6)); + test(8192, static_cast<int>(8192 * 0.3)); +} + +struct A { + int a; +}; + +struct AHash { + td::uint32 operator()(A a) const { + return td::Hash<int>()(a.a); + } +}; + +static bool operator==(const A &lhs, const A &rhs) { + return lhs.a == rhs.a; +} + +TEST(FlatHashSet, foreach) { + td::FlatHashSet<A, AHash> s; + for (auto it : s) { + LOG(ERROR) << it.a; + } + s.insert({1}); + LOG(INFO) << s.begin()->a; +} + +TEST(FlatHashSet, TL) { + td::FlatHashSet<int> s; + int N = 100000; + for (int i = 0; i < 10000000; i++) { + s.insert((i + N / 2) % N + 1); + s.erase(i % N + 1); + } +} + +TEST(FlatHashMap, basic) { + { + td::FlatHashMap<td::int32, int> map; + map[1] = 2; + ASSERT_EQ(2, map[1]); + ASSERT_EQ(1, map.find(1)->first); + ASSERT_EQ(2, map.find(1)->second); + // ASSERT_EQ(1, map.find(1)->key()); + // ASSERT_EQ(2, map.find(1)->value()); + for (auto &kv : map) { + ASSERT_EQ(1, kv.first); + ASSERT_EQ(2, kv.second); + } + map.erase(map.find(1)); + } + + td::FlatHashMap<td::int32, std::array<td::unique_ptr<td::string>, 10>> x; + auto y = std::move(x); + x[12]; + x.erase(x.find(12)); + + { + td::FlatHashMap<td::int32, td::string> map = {{1, "hello"}, {2, "world"}}; + ASSERT_EQ("hello", map[1]); + ASSERT_EQ("world", map[2]); + ASSERT_EQ(2u, map.size()); + ASSERT_EQ("", map[3]); + ASSERT_EQ(3u, map.size()); + } + + { + td::FlatHashMap<td::int32, td::string> map = {{1, "hello"}, {1, "world"}}; + ASSERT_EQ("hello", map[1]); + ASSERT_EQ(1u, map.size()); + } + + using KV = td::FlatHashMap<td::string, td::string>; + using Data = td::vector<std::pair<td::string, td::string>>; + auto data = Data{{"a", "b"}, {"c", "d"}}; + { ASSERT_EQ(Data{}, extract_kv(KV())); } + + { + KV kv; + for (auto &pair : data) { + kv.emplace(pair.first, pair.second); + } + ASSERT_EQ(data, extract_kv(kv)); + + KV moved_kv(std::move(kv)); + ASSERT_EQ(data, extract_kv(moved_kv)); + ASSERT_EQ(Data{}, extract_kv(kv)); + ASSERT_TRUE(kv.empty()); + kv = std::move(moved_kv); + ASSERT_EQ(data, extract_kv(kv)); + + KV assign_moved_kv; + assign_moved_kv = std::move(kv); + ASSERT_EQ(data, extract_kv(assign_moved_kv)); + ASSERT_EQ(Data{}, extract_kv(kv)); + ASSERT_TRUE(kv.empty()); + kv = std::move(assign_moved_kv); + + KV it_copy_kv; + for (auto &pair : kv) { + it_copy_kv.emplace(pair.first, pair.second); + } + ASSERT_EQ(data, extract_kv(it_copy_kv)); + } + + { + KV kv; + ASSERT_TRUE(kv.empty()); + ASSERT_EQ(0u, kv.size()); + for (auto &pair : data) { + kv.emplace(pair.first, pair.second); + } + ASSERT_TRUE(!kv.empty()); + ASSERT_EQ(2u, kv.size()); + + ASSERT_EQ("a", kv.find("a")->first); + ASSERT_EQ("b", kv.find("a")->second); + kv.find("a")->second = "c"; + ASSERT_EQ("c", kv.find("a")->second); + ASSERT_EQ("c", kv["a"]); + + ASSERT_EQ(0u, kv.count("x")); + ASSERT_EQ(1u, kv.count("a")); + } + { + KV kv; + kv["d"]; + ASSERT_EQ((Data{{"d", ""}}), extract_kv(kv)); + kv.erase(kv.find("d")); + ASSERT_EQ(Data{}, extract_kv(kv)); + } +} + +TEST(FlatHashMap, remove_if_basic) { + td::Random::Xorshift128plus rnd(123); + + constexpr int TESTS_N = 1000; + constexpr int MAX_TABLE_SIZE = 1000; + for (int test_i = 0; test_i < TESTS_N; test_i++) { + std::unordered_map<td::uint64, td::uint64, td::Hash<td::uint64>> reference; + td::FlatHashMap<td::uint64, td::uint64> table; + int N = rnd.fast(1, MAX_TABLE_SIZE); + for (int i = 0; i < N; i++) { + auto key = rnd(); + auto value = i; + reference[key] = value; + table[key] = value; + } + ASSERT_EQ(extract_kv(reference), extract_kv(table)); + + td::vector<std::pair<td::uint64, td::uint64>> kv; + td::table_remove_if(table, [&](auto &it) { + kv.emplace_back(it.first, it.second); + return it.second % 2 == 0; + }); + std::sort(kv.begin(), kv.end()); + ASSERT_EQ(extract_kv(reference), kv); + + td::table_remove_if(reference, [](auto &it) { return it.second % 2 == 0; }); + ASSERT_EQ(extract_kv(reference), extract_kv(table)); + } +} + +static constexpr size_t MAX_TABLE_SIZE = 1000; +TEST(FlatHashMap, stress_test) { + td::Random::Xorshift128plus rnd(123); + size_t max_table_size = MAX_TABLE_SIZE; // dynamic value + std::unordered_map<td::uint64, td::uint64, td::Hash<td::uint64>> ref; + td::FlatHashMap<td::uint64, td::uint64> tbl; + + auto validate = [&] { + ASSERT_EQ(ref.empty(), tbl.empty()); + ASSERT_EQ(ref.size(), tbl.size()); + ASSERT_EQ(extract_kv(ref), extract_kv(tbl)); + for (auto &kv : ref) { + auto tbl_it = tbl.find(kv.first); + ASSERT_TRUE(tbl_it != tbl.end()); + ASSERT_EQ(kv.second, tbl_it->second); + } + }; + + td::vector<td::RandomSteps::Step> steps; + auto add_step = [&](td::Slice step_name, td::uint32 weight, auto f) { + auto g = [&, f = std::move(f)] { + //ASSERT_EQ(ref.size(), tbl.size()); + f(); + ASSERT_EQ(ref.size(), tbl.size()); + //validate(); + }; + steps.emplace_back(td::RandomSteps::Step{std::move(g), weight}); + }; + + auto gen_key = [&] { + auto key = rnd() % 4000 + 1; + return key; + }; + + add_step("Reset hash table", 1, [&] { + validate(); + td::reset_to_empty(ref); + td::reset_to_empty(tbl); + max_table_size = rnd.fast(1, MAX_TABLE_SIZE); + }); + add_step("Clear hash table", 1, [&] { + validate(); + ref.clear(); + tbl.clear(); + max_table_size = rnd.fast(1, MAX_TABLE_SIZE); + }); + + add_step("Insert random value", 1000, [&] { + if (tbl.size() > max_table_size) { + return; + } + auto key = gen_key(); + auto value = rnd(); + ref[key] = value; + tbl[key] = value; + ASSERT_EQ(ref[key], tbl[key]); + }); + + add_step("Emplace random value", 1000, [&] { + if (tbl.size() > max_table_size) { + return; + } + auto key = gen_key(); + auto value = rnd(); + auto ref_it = ref.emplace(key, value); + auto tbl_it = tbl.emplace(key, value); + ASSERT_EQ(ref_it.second, tbl_it.second); + ASSERT_EQ(key, tbl_it.first->first); + }); + + add_step("empty operator[]", 1000, [&] { + if (tbl.size() > max_table_size) { + return; + } + auto key = gen_key(); + ASSERT_EQ(ref[key], tbl[key]); + }); + + add_step("reserve", 10, [&] { tbl.reserve(static_cast<size_t>(rnd() % max_table_size)); }); + + add_step("find", 1000, [&] { + auto key = gen_key(); + auto ref_it = ref.find(key); + auto tbl_it = tbl.find(key); + ASSERT_EQ(ref_it == ref.end(), tbl_it == tbl.end()); + if (ref_it != ref.end()) { + ASSERT_EQ(ref_it->first, tbl_it->first); + ASSERT_EQ(ref_it->second, tbl_it->second); + } + }); + + add_step("find_and_erase", 100, [&] { + auto key = gen_key(); + auto ref_it = ref.find(key); + auto tbl_it = tbl.find(key); + ASSERT_EQ(ref_it == ref.end(), tbl_it == tbl.end()); + if (ref_it != ref.end()) { + ref.erase(ref_it); + tbl.erase(tbl_it); + } + }); + + add_step("remove_if", 5, [&] { + auto mul = rnd(); + auto bit = rnd() % 64; + auto condition = [&](auto &it) { + return (((it.second * mul) >> bit) & 1) == 0; + }; + td::table_remove_if(tbl, condition); + td::table_remove_if(ref, condition); + }); + + td::RandomSteps runner(std::move(steps)); + for (size_t i = 0; i < 1000000; i++) { + runner.step(rnd); + } +} + +TEST(FlatHashSet, stress_test) { + td::vector<td::RandomSteps::Step> steps; + auto add_step = [&steps](td::Slice, td::uint32 weight, auto f) { + steps.emplace_back(td::RandomSteps::Step{std::move(f), weight}); + }; + + td::Random::Xorshift128plus rnd(123); + size_t max_table_size = MAX_TABLE_SIZE; // dynamic value + std::unordered_set<td::uint64, td::Hash<td::uint64>> ref; + td::FlatHashSet<td::uint64> tbl; + + auto validate = [&] { + ASSERT_EQ(ref.empty(), tbl.empty()); + ASSERT_EQ(ref.size(), tbl.size()); + ASSERT_EQ(extract_k(ref), extract_k(tbl)); + }; + auto gen_key = [&] { + auto key = rnd() % 4000 + 1; + return key; + }; + + add_step("Reset hash table", 1, [&] { + validate(); + td::reset_to_empty(ref); + td::reset_to_empty(tbl); + max_table_size = rnd.fast(1, MAX_TABLE_SIZE); + }); + add_step("Clear hash table", 1, [&] { + validate(); + ref.clear(); + tbl.clear(); + max_table_size = rnd.fast(1, MAX_TABLE_SIZE); + }); + + add_step("Insert random value", 1000, [&] { + if (tbl.size() > max_table_size) { + return; + } + auto key = gen_key(); + ref.insert(key); + tbl.insert(key); + }); + + add_step("reserve", 10, [&] { tbl.reserve(static_cast<size_t>(rnd() % max_table_size)); }); + + add_step("find", 1000, [&] { + auto key = gen_key(); + auto ref_it = ref.find(key); + auto tbl_it = tbl.find(key); + ASSERT_EQ(ref_it == ref.end(), tbl_it == tbl.end()); + if (ref_it != ref.end()) { + ASSERT_EQ(*ref_it, *tbl_it); + } + }); + + add_step("find_and_erase", 100, [&] { + auto key = gen_key(); + auto ref_it = ref.find(key); + auto tbl_it = tbl.find(key); + ASSERT_EQ(ref_it == ref.end(), tbl_it == tbl.end()); + if (ref_it != ref.end()) { + ref.erase(ref_it); + tbl.erase(tbl_it); + } + }); + + add_step("remove_if", 5, [&] { + auto mul = rnd(); + auto bit = rnd() % 64; + auto condition = [&](auto &it) { + return (((it * mul) >> bit) & 1) == 0; + }; + td::table_remove_if(tbl, condition); + td::table_remove_if(ref, condition); + }); + + td::RandomSteps runner(std::move(steps)); + for (size_t i = 0; i < 10000000; i++) { + runner.step(rnd); + } +} diff --git a/protocols/Telegram/tdlib/td/tdutils/test/HazardPointers.cpp b/protocols/Telegram/tdlib/td/tdutils/test/HazardPointers.cpp index 36b0570530..0c4174db0f 100644 --- a/protocols/Telegram/tdlib/td/tdutils/test/HazardPointers.cpp +++ b/protocols/Telegram/tdlib/td/tdutils/test/HazardPointers.cpp @@ -1,13 +1,15 @@ // -// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2018 +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // +#include "td/utils/common.h" #include "td/utils/HazardPointers.h" #include "td/utils/logging.h" #include "td/utils/port/thread.h" #include "td/utils/Random.h" +#include "td/utils/Slice.h" #include "td/utils/tests.h" #include <atomic> @@ -15,7 +17,7 @@ #if !TD_THREAD_UNSUPPORTED TEST(HazardPointers, stress) { struct Node { - std::atomic<std::string *> name_; + std::atomic<std::string *> name_{nullptr}; char pad[64]; }; int threads_n = 10; @@ -25,16 +27,16 @@ TEST(HazardPointers, stress) { int thread_id = 0; for (auto &thread : threads) { thread = td::thread([&, thread_id] { - auto holder = hazard_pointers.get_holder(thread_id, 0); + std::remove_reference_t<decltype(hazard_pointers)>::Holder holder(hazard_pointers, thread_id, 0); for (int i = 0; i < 1000000; i++) { auto &node = nodes[td::Random::fast(0, threads_n - 1)]; auto *str = holder.protect(node.name_); if (str) { - CHECK(*str == "one" || *str == "twotwo"); + CHECK(*str == td::Slice("one") || *str == td::Slice("twotwo")); } holder.clear(); if (td::Random::fast(0, 5) == 0) { - std::string *new_str = new std::string(td::Random::fast(0, 1) == 0 ? "one" : "twotwo"); + auto *new_str = new td::string(td::Random::fast_bool() ? "one" : "twotwo"); if (node.name_.compare_exchange_strong(str, new_str, std::memory_order_acq_rel)) { hazard_pointers.retire(thread_id, str); } else { @@ -48,11 +50,11 @@ TEST(HazardPointers, stress) { for (auto &thread : threads) { thread.join(); } - LOG(ERROR) << "Undeleted pointers: " << hazard_pointers.to_delete_size_unsafe(); + LOG(INFO) << "Undeleted pointers: " << hazard_pointers.to_delete_size_unsafe(); CHECK(static_cast<int>(hazard_pointers.to_delete_size_unsafe()) <= threads_n * threads_n); for (int i = 0; i < threads_n; i++) { hazard_pointers.retire(i); } CHECK(hazard_pointers.to_delete_size_unsafe() == 0); } -#endif //!TD_THREAD_UNSUPPORTED +#endif diff --git a/protocols/Telegram/tdlib/td/tdutils/test/HttpUrl.cpp b/protocols/Telegram/tdlib/td/tdutils/test/HttpUrl.cpp new file mode 100644 index 0000000000..6e91d48803 --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/HttpUrl.cpp @@ -0,0 +1,54 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/common.h" +#include "td/utils/HttpUrl.h" +#include "td/utils/tests.h" + +#include <utility> + +static void test_get_url_query_file_name(const char *prefix, const char *suffix, const char *file_name) { + auto path = td::string(prefix) + td::string(file_name) + td::string(suffix); + ASSERT_STREQ(file_name, td::get_url_query_file_name(path)); + ASSERT_STREQ(file_name, td::get_url_file_name("http://telegram.org" + path)); + ASSERT_STREQ(file_name, td::get_url_file_name("http://telegram.org:80" + path)); + ASSERT_STREQ(file_name, td::get_url_file_name("telegram.org" + path)); +} + +TEST(HttpUrl, get_url_query_file_name) { + for (auto suffix : {"?t=1#test", "#test?t=1", "#?t=1", "?t=1#", "#test", "?t=1", "#", "?", ""}) { + test_get_url_query_file_name("", suffix, ""); + test_get_url_query_file_name("/", suffix, ""); + test_get_url_query_file_name("/a/adasd/", suffix, ""); + test_get_url_query_file_name("/a/lklrjetn/", suffix, "adasd.asdas"); + test_get_url_query_file_name("/", suffix, "a123asadas"); + test_get_url_query_file_name("/", suffix, "\\a\\1\\2\\3\\a\\s\\a\\das"); + } +} + +static void test_parse_url_query(const td::string &query, const td::vector<td::string> &path, + const td::vector<std::pair<td::string, td::string>> &args) { + for (auto hash : {"", "#", "#?t=1", "#t=1&a=b"}) { + auto url_query = td::parse_url_query(query + hash); + ASSERT_EQ(path, url_query.path_); + ASSERT_EQ(args, url_query.args_); + } +} + +TEST(HttpUrl, parse_url_query) { + test_parse_url_query("", {}, {}); + test_parse_url_query("a", {"a"}, {}); + test_parse_url_query("/", {}, {}); + test_parse_url_query("//", {}, {}); + test_parse_url_query("///?a", {}, {{"a", ""}}); + test_parse_url_query("/a/b/c/", {"a", "b", "c"}, {}); + test_parse_url_query("/a/b/?c/", {td::string("a"), td::string("b")}, {{"c/", ""}}); + test_parse_url_query("?", {}, {}); + test_parse_url_query("???", {}, {{"??", ""}}); + test_parse_url_query("?a=b=c=d?e=f=g=h&x=y=z?d=3&", {}, {{"a", "b=c=d?e=f=g=h"}, {"x", "y=z?d=3"}}); + test_parse_url_query("c?&&&a=b", {"c"}, {{"a", "b"}}); + test_parse_url_query("c?&&&=b", {"c"}, {}); +} diff --git a/protocols/Telegram/tdlib/td/tdutils/test/List.cpp b/protocols/Telegram/tdlib/td/tdutils/test/List.cpp new file mode 100644 index 0000000000..02ab080d89 --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/List.cpp @@ -0,0 +1,169 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/common.h" +#include "td/utils/List.h" +#include "td/utils/MovableValue.h" +#include "td/utils/port/thread.h" +#include "td/utils/Random.h" +#include "td/utils/tests.h" +#include "td/utils/TsList.h" + +#include <atomic> +#include <mutex> +#include <set> +#include <utility> + +struct ListData { + td::MovableValue<td::uint64> value_; + td::MovableValue<bool> in_list_; + + ListData() = default; + ListData(td::uint64 value, bool in_list) : value_(value), in_list_(in_list) { + } +}; + +struct Node final : public td::ListNode { + Node() = default; + explicit Node(ListData data) : data_(std::move(data)) { + } + + ListData data_; +}; + +static ListData &get_data(Node &node) { + return node.data_; +} + +static ListData &get_data(td::TsListNode<ListData> &node) { + return node.get_data_unsafe(); +} + +static std::unique_lock<std::mutex> lock(td::ListNode &node) { + return {}; +} + +static std::unique_lock<std::mutex> lock(td::TsListNode<ListData> &node) { + return node.lock(); +} + +template <class ListNodeT, class ListRootT, class NodeT> +static void do_run_list_test(ListRootT &root, std::atomic<td::uint64> &id) { + td::vector<NodeT> nodes; + + td::Random::Xorshift128plus rnd(123); + + auto next_id = [&] { + return ++id; + }; + auto add_node = [&] { + if (nodes.size() >= 20) { + return; + } + nodes.push_back(NodeT({next_id(), false})); + }; + auto pop_node = [&] { + if (nodes.empty()) { + return; + } + nodes.pop_back(); + }; + auto random_node_index = [&] { + CHECK(!nodes.empty()); + return rnd.fast(0, static_cast<int>(nodes.size()) - 1); + }; + + auto link_node = [&] { + if (nodes.empty()) { + return; + } + auto i = random_node_index(); + nodes[i].remove(); + get_data(nodes[i]) = ListData(next_id(), true); + root.put(&nodes[i]); + }; + auto unlink_node = [&] { + if (nodes.empty()) { + return; + } + auto i = random_node_index(); + nodes[i].remove(); + get_data(nodes[i]).in_list_ = false; + }; + auto swap_nodes = [&] { + if (nodes.empty()) { + return; + } + auto i = random_node_index(); + auto j = random_node_index(); + std::swap(nodes[i], nodes[j]); + }; + auto set_node = [&] { + if (nodes.empty()) { + return; + } + auto i = random_node_index(); + auto j = random_node_index(); + nodes[i] = std::move(nodes[j]); + }; + auto validate = [&] { + std::multiset<td::uint64> in_list; + std::multiset<td::uint64> not_in_list; + for (auto &node : nodes) { + if (get_data(node).in_list_.get()) { + in_list.insert(get_data(node).value_.get()); + } else { + not_in_list.insert(get_data(node).value_.get()); + } + } + auto guard = lock(root); + for (auto *begin = root.begin(), *end = root.end(); begin != end; begin = begin->get_next()) { + auto &data = get_data(*static_cast<NodeT *>(begin)); + CHECK(data.in_list_.get()); + CHECK(data.value_.get() != 0); + auto it = in_list.find(data.value_.get()); + if (it != in_list.end()) { + in_list.erase(it); + } else { + ASSERT_EQ(0u, not_in_list.count(data.value_.get())); + } + } + ASSERT_EQ(0u, in_list.size()); + }; + td::RandomSteps steps( + {{add_node, 3}, {pop_node, 1}, {unlink_node, 1}, {link_node, 3}, {swap_nodes, 1}, {set_node, 1}, {validate, 1}}); + for (int i = 0; i < 10000; i++) { + steps.step(rnd); + } +} + +TEST(Misc, List) { + td::ListNode root; + std::atomic<td::uint64> id{0}; + for (std::size_t i = 0; i < 4; i++) { + do_run_list_test<td::ListNode, td::ListNode, Node>(root, id); + } +} + +TEST(Misc, TsList) { + td::TsList<ListData> root; + std::atomic<td::uint64> id{0}; + for (std::size_t i = 0; i < 4; i++) { + do_run_list_test<td::TsListNode<ListData>, td::TsList<ListData>, td::TsListNode<ListData>>(root, id); + } +} + +#if !TD_THREAD_UNSUPPORTED +TEST(Misc, TsListConcurrent) { + td::TsList<ListData> root; + td::vector<td::thread> threads; + std::atomic<td::uint64> id{0}; + for (std::size_t i = 0; i < 4; i++) { + threads.emplace_back( + [&] { do_run_list_test<td::TsListNode<ListData>, td::TsList<ListData>, td::TsListNode<ListData>>(root, id); }); + } +} +#endif diff --git a/protocols/Telegram/tdlib/td/tdutils/test/MpmcQueue.cpp b/protocols/Telegram/tdlib/td/tdutils/test/MpmcQueue.cpp index 2da3f0cd3f..c038303c37 100644 --- a/protocols/Telegram/tdlib/td/tdutils/test/MpmcQueue.cpp +++ b/protocols/Telegram/tdlib/td/tdutils/test/MpmcQueue.cpp @@ -1,9 +1,10 @@ // -// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2018 +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // +#include "td/utils/common.h" #include "td/utils/logging.h" #include "td/utils/MpmcQueue.h" #include "td/utils/port/thread.h" @@ -49,7 +50,7 @@ TEST(OneValue, stress) { std::vector<td::thread> threads; td::OneValue<std::string> value; for (size_t i = 0; i < 2; i++) { - threads.push_back(td::thread([&, id = i] { + threads.emplace_back([&, id = i] { for (td::uint64 round = 1; round < 100000; round++) { if (id == 0) { value.reset(); @@ -68,7 +69,7 @@ TEST(OneValue, stress) { if (set_status) { CHECK(get_status); CHECK(from.empty()); - CHECK(to == "hello") << to; + LOG_CHECK(to == "hello") << to; } else { CHECK(!get_status); CHECK(from == "hello"); @@ -76,17 +77,17 @@ TEST(OneValue, stress) { } } } - })); + }); } for (auto &thread : threads) { thread.join(); } } -#endif //!TD_THREAD_UNSUPPORTED +#endif TEST(MpmcQueueBlock, simple) { // Test doesn't work now and it is ok, try_pop, logic changed - return; + /* td::MpmcQueueBlock<std::string> block(2); std::string x = "hello"; using PushStatus = td::MpmcQueueBlock<std::string>::PushStatus; @@ -111,6 +112,7 @@ TEST(MpmcQueueBlock, simple) { CHECK(pop_status == PopStatus::Ok); pop_status = block.try_pop(x); CHECK(pop_status == PopStatus::Closed); + */ } TEST(MpmcQueue, simple) { @@ -121,7 +123,7 @@ TEST(MpmcQueue, simple) { } for (int i = 0; i < 100; i++) { int x = q.pop(0); - CHECK(x == i) << x << " expected " << i; + LOG_CHECK(x == i) << x << " expected " << i; } } } @@ -188,18 +190,18 @@ TEST(MpmcQueue, multi_thread) { from[data.from] = data.value; } } - CHECK(all.size() == n * qn) << all.size(); + LOG_CHECK(all.size() == n * qn) << all.size(); std::sort(all.begin(), all.end(), [](const auto &a, const auto &b) { return std::tie(a.from, a.value) < std::tie(b.from, b.value); }); for (size_t i = 0; i < n * qn; i++) { CHECK(all[i].from == i / qn); CHECK(all[i].value == i % qn + 1); } - LOG(ERROR) << "Undeleted pointers: " << q.hazard_pointers_to_delele_size_unsafe(); + LOG(INFO) << "Undeleted pointers: " << q.hazard_pointers_to_delele_size_unsafe(); CHECK(q.hazard_pointers_to_delele_size_unsafe() <= (n + m + 1) * (n + m + 1)); for (size_t id = 0; id < n + m + 1; id++) { q.gc(id); } - CHECK(q.hazard_pointers_to_delele_size_unsafe() == 0) << q.hazard_pointers_to_delele_size_unsafe(); + LOG_CHECK(q.hazard_pointers_to_delele_size_unsafe() == 0) << q.hazard_pointers_to_delele_size_unsafe(); } -#endif //!TD_THREAD_UNSUPPORTED +#endif diff --git a/protocols/Telegram/tdlib/td/tdutils/test/MpmcWaiter.cpp b/protocols/Telegram/tdlib/td/tdutils/test/MpmcWaiter.cpp index e27e217713..4ac882dcaf 100644 --- a/protocols/Telegram/tdlib/td/tdutils/test/MpmcWaiter.cpp +++ b/protocols/Telegram/tdlib/td/tdutils/test/MpmcWaiter.cpp @@ -1,5 +1,5 @@ // -// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2018 +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) @@ -13,21 +13,22 @@ #include <atomic> #if !TD_THREAD_UNSUPPORTED -TEST(MpmcWaiter, stress_one_one) { +template <class W> +static void test_waiter_stress_one_one() { td::Stage run; td::Stage check; std::vector<td::thread> threads; - std::atomic<size_t> value; + std::atomic<size_t> value{0}; size_t write_cnt = 10; - std::unique_ptr<td::MpmcWaiter> waiter; + td::unique_ptr<W> waiter; size_t threads_n = 2; for (size_t i = 0; i < threads_n; i++) { threads.push_back(td::thread([&, id = static_cast<td::uint32>(i)] { for (td::uint64 round = 1; round < 100000; round++) { if (id == 0) { value = 0; - waiter = std::make_unique<td::MpmcWaiter>(); + waiter = td::make_unique<W>(); write_cnt = td::Random::fast(1, 10); } run.wait(round * threads_n); @@ -37,17 +38,19 @@ TEST(MpmcWaiter, stress_one_one) { waiter->notify(); } } else { - int yields = 0; + typename W::Slot slot; + W::init_slot(slot, id); for (size_t i = 1; i <= write_cnt; i++) { while (true) { auto x = value.load(std::memory_order_relaxed); if (x >= i) { break; } - yields = waiter->wait(yields, id); + waiter->wait(slot); } - yields = waiter->stop_wait(yields, id); + waiter->stop_wait(slot); } + waiter->stop_wait(slot); } check.wait(round * threads_n); } @@ -57,19 +60,29 @@ TEST(MpmcWaiter, stress_one_one) { thread.join(); } } -TEST(MpmcWaiter, stress) { + +TEST(MpmcEagerWaiter, stress_one_one) { + test_waiter_stress_one_one<td::MpmcEagerWaiter>(); +} + +TEST(MpmcSleepyWaiter, stress_one_one) { + test_waiter_stress_one_one<td::MpmcSleepyWaiter>(); +} + +template <class W> +static void test_waiter_stress() { td::Stage run; td::Stage check; std::vector<td::thread> threads; size_t write_n; size_t read_n; - std::atomic<size_t> write_pos; - std::atomic<size_t> read_pos; + std::atomic<size_t> write_pos{0}; + std::atomic<size_t> read_pos{0}; size_t end_pos; size_t write_cnt; size_t threads_n = 20; - std::unique_ptr<td::MpmcWaiter> waiter; + td::unique_ptr<W> waiter; for (size_t i = 0; i < threads_n; i++) { threads.push_back(td::thread([&, id = static_cast<td::uint32>(i)] { for (td::uint64 round = 1; round < 1000; round++) { @@ -80,7 +93,7 @@ TEST(MpmcWaiter, stress) { end_pos = write_n * write_cnt; write_pos = 0; read_pos = 0; - waiter = std::make_unique<td::MpmcWaiter>(); + waiter = td::make_unique<W>(); } run.wait(round * threads_n); if (id <= write_n) { @@ -92,21 +105,26 @@ TEST(MpmcWaiter, stress) { waiter->notify(); } } else if (id > 10 && id - 10 <= read_n) { - int yields = 0; + typename W::Slot slot; + W::init_slot(slot, id); while (true) { auto x = read_pos.load(std::memory_order_relaxed); if (x == end_pos) { + waiter->stop_wait(slot); break; } if (x == write_pos.load(std::memory_order_relaxed)) { - yields = waiter->wait(yields, id); + waiter->wait(slot); continue; } - yields = waiter->stop_wait(yields, id); + waiter->stop_wait(slot); read_pos.compare_exchange_strong(x, x + 1, std::memory_order_relaxed); } } check.wait(round * threads_n); + if (id == 0) { + waiter->close(); + } } })); } @@ -114,4 +132,12 @@ TEST(MpmcWaiter, stress) { thread.join(); } } -#endif // !TD_THREAD_UNSUPPORTED + +TEST(MpmcEagerWaiter, stress_multi) { + test_waiter_stress<td::MpmcEagerWaiter>(); +} + +TEST(MpmcSleepyWaiter, stress_multi) { + test_waiter_stress<td::MpmcSleepyWaiter>(); +} +#endif diff --git a/protocols/Telegram/tdlib/td/tdutils/test/MpscLinkQueue.cpp b/protocols/Telegram/tdlib/td/tdutils/test/MpscLinkQueue.cpp index 629e5b7223..43b0ccf086 100644 --- a/protocols/Telegram/tdlib/td/tdutils/test/MpscLinkQueue.cpp +++ b/protocols/Telegram/tdlib/td/tdutils/test/MpscLinkQueue.cpp @@ -1,16 +1,17 @@ // -// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2018 +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // +#include "td/utils/common.h" #include "td/utils/format.h" #include "td/utils/logging.h" #include "td/utils/MpscLinkQueue.h" #include "td/utils/port/thread.h" #include "td/utils/tests.h" -class NodeX : public td::MpscLinkQueueImpl::Node { +class NodeX final : public td::MpscLinkQueueImpl::Node { public: explicit NodeX(int value) : value_(value) { } @@ -29,8 +30,8 @@ class NodeX : public td::MpscLinkQueueImpl::Node { }; using QueueNode = td::MpscLinkQueueUniquePtrNode<NodeX>; -QueueNode create_node(int value) { - return QueueNode(std::make_unique<NodeX>(value)); +static QueueNode create_node(int value) { + return QueueNode(td::make_unique<NodeX>(value)); } TEST(MpscLinkQueue, one_thread) { @@ -48,7 +49,7 @@ TEST(MpscLinkQueue, one_thread) { while (auto node = reader.read()) { v.push_back(node.value().value()); } - CHECK((v == std::vector<int>{1, 2, 3, 4})) << td::format::as_array(v); + LOG_CHECK((v == std::vector<int>{1, 2, 3, 4})) << td::format::as_array(v); v.clear(); queue.push(create_node(5)); @@ -56,7 +57,7 @@ TEST(MpscLinkQueue, one_thread) { while (auto node = reader.read()) { v.push_back(node.value().value()); } - CHECK((v == std::vector<int>{5})) << td::format::as_array(v); + LOG_CHECK((v == std::vector<int>{5})) << td::format::as_array(v); } { @@ -70,7 +71,7 @@ TEST(MpscLinkQueue, one_thread) { while (auto node = reader.read()) { v.push_back(node.value().value()); } - CHECK((v == std::vector<int>{3, 2, 1, 0})) << td::format::as_array(v); + LOG_CHECK((v == std::vector<int>{3, 2, 1, 0})) << td::format::as_array(v); } } @@ -112,4 +113,4 @@ TEST(MpscLinkQueue, multi_thread) { thread.join(); } } -#endif //!TD_THREAD_UNSUPPORTED +#endif diff --git a/protocols/Telegram/tdlib/td/tdutils/test/OptionParser.cpp b/protocols/Telegram/tdlib/td/tdutils/test/OptionParser.cpp new file mode 100644 index 0000000000..8600eb9f19 --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/OptionParser.cpp @@ -0,0 +1,82 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/common.h" +#include "td/utils/misc.h" +#include "td/utils/OptionParser.h" +#include "td/utils/Slice.h" +#include "td/utils/tests.h" + +TEST(OptionParser, run) { + td::OptionParser options; + options.set_description("test description"); + + td::string exename = "exename"; + td::vector<td::string> args; + auto run_option_parser = [&](td::string command_line) { + args = td::full_split(std::move(command_line), ' '); + td::vector<char *> argv; + argv.push_back(&exename[0]); + for (auto &arg : args) { + argv.push_back(&arg[0]); + } + return options.run_impl(static_cast<int>(argv.size()), &argv[0], -1); + }; + + td::uint64 chosen_options = 0; + td::vector<td::string> chosen_parameters; + auto test_success = [&](td::string command_line, td::uint64 expected_options, + const td::vector<td::string> &expected_parameters, + const td::vector<td::string> &expected_result) { + chosen_options = 0; + chosen_parameters.clear(); + auto result = run_option_parser(std::move(command_line)); + ASSERT_TRUE(result.is_ok()); + ASSERT_EQ(expected_options, chosen_options); + ASSERT_EQ(expected_parameters, chosen_parameters); + ASSERT_EQ(expected_result.size(), result.ok().size()); + for (size_t i = 0; i < expected_result.size(); i++) { + ASSERT_STREQ(expected_result[i], td::string(result.ok()[i])); + } + }; + auto test_fail = [&](td::string command_line) { + auto result = run_option_parser(std::move(command_line)); + ASSERT_TRUE(result.is_error()); + }; + + options.add_option('q', "", "", [&] { chosen_options += 1; }); + options.add_option('\0', "http-port2", "", [&] { chosen_options += 10; }); + options.add_option('p', "http-port", "", [&](td::Slice parameter) { + chosen_options += 100; + chosen_parameters.push_back(parameter.str()); + }); + options.add_option('v', "test", "", [&] { chosen_options += 1000; }); + + test_fail("-http-port2"); + test_success("-", 0, {}, {"-"}); + test_fail("--http-port"); + test_fail("--http-port3"); + test_fail("--http-por"); + test_fail("--http-port2=1"); + test_fail("--q"); + test_fail("-qvp"); + test_fail("-p"); + test_fail("-u"); + test_success("-q", 1, {}, {}); + test_success("-vvvvvvvvvv", 10000, {}, {}); + test_success("-qpv", 101, {"v"}, {}); + test_success("-qp -v", 101, {"-v"}, {}); + test_success("-qp --http-port2", 101, {"--http-port2"}, {}); + test_success("-qp -- -v", 1101, {"--"}, {}); + test_success("-qvqvpqv", 2102, {"qv"}, {}); + test_success("aba --http-port2 caba --http-port2 dabacaba", 20, {}, {"aba", "caba", "dabacaba"}); + test_success("das -pqwerty -- -v asd --http-port", 100, {"qwerty"}, {"das", "-v", "asd", "--http-port"}); + test_success("-p option --http-port option2 --http-port=option3 --http-port=", 400, + {"option", "option2", "option3", ""}, {}); + test_success("", 0, {}, {}); + test_success("a", 0, {}, {"a"}); + test_success("", 0, {}, {}); +} diff --git a/protocols/Telegram/tdlib/td/tdutils/test/OrderedEventsProcessor.cpp b/protocols/Telegram/tdlib/td/tdutils/test/OrderedEventsProcessor.cpp index 6a5a20015f..c5c963bedc 100644 --- a/protocols/Telegram/tdlib/td/tdutils/test/OrderedEventsProcessor.cpp +++ b/protocols/Telegram/tdlib/td/tdutils/test/OrderedEventsProcessor.cpp @@ -1,5 +1,5 @@ // -// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2018 +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) @@ -18,8 +18,8 @@ TEST(OrderedEventsProcessor, random) { int offset = 1000000; std::vector<std::pair<int, int>> v; for (int i = 0; i < n; i++) { - auto shift = td::Random::fast(0, 1) ? td::Random::fast(0, d) : td::Random::fast(0, 1) * d; - v.push_back({i + shift, i + offset}); + auto shift = td::Random::fast_bool() ? td::Random::fast(0, d) : td::Random::fast(0, 1) * d; + v.emplace_back(i + shift, i + offset); } std::sort(v.begin(), v.end()); diff --git a/protocols/Telegram/tdlib/td/tdutils/test/SharedObjectPool.cpp b/protocols/Telegram/tdlib/td/tdutils/test/SharedObjectPool.cpp index 61d956f4e6..a4762e25f3 100644 --- a/protocols/Telegram/tdlib/td/tdutils/test/SharedObjectPool.cpp +++ b/protocols/Telegram/tdlib/td/tdutils/test/SharedObjectPool.cpp @@ -1,10 +1,10 @@ // -// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2018 +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // -#include "td/utils/logging.h" +#include "td/utils/common.h" #include "td/utils/SharedObjectPool.h" #include "td/utils/tests.h" @@ -56,7 +56,16 @@ TEST(SharedPtr, simple) { ptr2 = std::move(ptr); CHECK(ptr.empty()); CHECK(*ptr2 == "hello"); +#if TD_CLANG +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wunknown-pragmas" +#pragma clang diagnostic ignored "-Wunknown-warning-option" +#pragma clang diagnostic ignored "-Wself-assign-overloaded" +#endif ptr2 = ptr2; +#if TD_CLANG +#pragma clang diagnostic pop +#endif CHECK(*ptr2 == "hello"); CHECK(!Deleter::was_delete()); ptr2.reset(); @@ -80,15 +89,15 @@ TEST(SharedObjectPool, simple) { }; { td::SharedObjectPool<Node> pool; - pool.alloc(); - pool.alloc(); - pool.alloc(); - pool.alloc(); - pool.alloc(); + { auto ptr1 = pool.alloc(); } + { auto ptr2 = pool.alloc(); } + { auto ptr3 = pool.alloc(); } + { auto ptr4 = pool.alloc(); } + { auto ptr5 = pool.alloc(); } CHECK(Node::cnt() == 0); CHECK(pool.total_size() == 1); CHECK(pool.calc_free_size() == 1); - pool.alloc(), pool.alloc(), pool.alloc(); + { auto ptr6 = pool.alloc(), ptr7 = pool.alloc(), ptr8 = pool.alloc(); } CHECK(pool.total_size() == 3); CHECK(pool.calc_free_size() == 3); } diff --git a/protocols/Telegram/tdlib/td/tdutils/test/SharedSlice.cpp b/protocols/Telegram/tdlib/td/tdutils/test/SharedSlice.cpp new file mode 100644 index 0000000000..7327f0dbb3 --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/SharedSlice.cpp @@ -0,0 +1,91 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/common.h" +#include "td/utils/port/thread.h" +#include "td/utils/SharedSlice.h" +#include "td/utils/tests.h" + +char disable_linker_warning_about_empty_file_tdutils_test_shared_slice_cpp TD_UNUSED; + +#if !TD_THREAD_UNSUPPORTED +TEST(SharedSlice, Hands) { + { + td::SharedSlice h("hello"); + ASSERT_EQ("hello", h.as_slice()); + // auto g = h; // CE + auto g = h.clone(); + ASSERT_EQ("hello", h.as_slice()); + ASSERT_EQ("hello", g.as_slice()); + } + + { + td::SharedSlice h("hello"); + td::UniqueSharedSlice g(std::move(h)); + ASSERT_EQ("", h.as_slice()); + ASSERT_EQ("hello", g.as_slice()); + } + { + td::SharedSlice h("hello"); + td::SharedSlice t = h.clone(); + td::UniqueSharedSlice g(std::move(h)); + ASSERT_EQ("", h.as_slice()); + ASSERT_EQ("hello", g.as_slice()); + ASSERT_EQ("hello", t.as_slice()); + } + + { + td::UniqueSharedSlice g(5); + g.as_mutable_slice().copy_from("hello"); + td::SharedSlice h(std::move(g)); + ASSERT_EQ("hello", h); + ASSERT_EQ("", g); + } + + { + td::UniqueSlice h("hello"); + td::UniqueSlice g(std::move(h)); + ASSERT_EQ("", h.as_slice()); + ASSERT_EQ("hello", g.as_slice()); + } + + { + td::SecureString h("hello"); + td::SecureString g(std::move(h)); + ASSERT_EQ("", h.as_slice()); + ASSERT_EQ("hello", g.as_slice()); + } + + { + td::Stage stage; + td::SharedSlice a; + td::SharedSlice b; + td::vector<td::thread> threads(2); + for (int i = 0; i < 2; i++) { + threads[i] = td::thread([i, &stage, &a, &b] { + for (int j = 0; j < 10000; j++) { + if (i == 0) { + a = td::SharedSlice("hello"); + b = a.clone(); + } + stage.wait((2 * j + 1) * 2); + if (i == 0) { + ASSERT_EQ('h', a[0]); + a.clear(); + } else { + td::UniqueSharedSlice c(std::move(b)); + c.as_mutable_slice()[0] = '!'; + } + stage.wait((2 * j + 2) * 2); + } + }); + } + for (auto &thread : threads) { + thread.join(); + } + } +} +#endif diff --git a/protocols/Telegram/tdlib/td/tdutils/test/StealingQueue.cpp b/protocols/Telegram/tdlib/td/tdutils/test/StealingQueue.cpp new file mode 100644 index 0000000000..453a63179f --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/StealingQueue.cpp @@ -0,0 +1,180 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/AtomicRead.h" +#include "td/utils/benchmark.h" +#include "td/utils/common.h" +#include "td/utils/logging.h" +#include "td/utils/MpmcQueue.h" +#include "td/utils/port/thread.h" +#include "td/utils/Random.h" +#include "td/utils/SliceBuilder.h" +#include "td/utils/StealingQueue.h" +#include "td/utils/tests.h" + +#include <atomic> +#include <cstring> + +TEST(StealingQueue, very_simple) { + td::StealingQueue<int, 8> q; + q.local_push(1, [](auto x) { UNREACHABLE(); }); + int x; + CHECK(q.local_pop(x)); + ASSERT_EQ(1, x); +} + +#if !TD_THREAD_UNSUPPORTED +TEST(AtomicRead, simple) { + td::Stage run; + td::Stage check; + + std::size_t threads_n = 10; + td::vector<td::thread> threads; + + int x{0}; + std::atomic<int> version{0}; + + td::int64 res = 0; + for (std::size_t i = 0; i < threads_n; i++) { + threads.emplace_back([&, id = static_cast<td::uint32>(i)] { + for (td::uint64 round = 1; round < 10000; round++) { + run.wait(round * threads_n); + if (id == 0) { + version++; + x++; + version++; + } else { + int y = 0; + auto v1 = version.load(); + y = x; + auto v2 = version.load(); + if (v1 == v2 && v1 % 2 == 0) { + res += y; + } + } + + check.wait(round * threads_n); + } + }); + } + td::do_not_optimize_away(res); + for (auto &thread : threads) { + thread.join(); + } +} + +TEST(AtomicRead, simple2) { + td::Stage run; + td::Stage check; + + std::size_t threads_n = 10; + td::vector<td::thread> threads; + + struct Value { + td::uint64 value = 0; + char str[50] = "0 0 0 0"; + }; + td::AtomicRead<Value> value; + + auto to_str = [](td::uint64 i) { + return PSTRING() << i << " " << i << " " << i << " " << i; + }; + for (std::size_t i = 0; i < threads_n; i++) { + threads.emplace_back([&, id = static_cast<td::uint32>(i)] { + for (td::uint64 round = 1; round < 10000; round++) { + run.wait(round * threads_n); + if (id == 0) { + auto x = value.lock(); + x->value = round; + auto str = to_str(round); + std::memcpy(x->str, str.c_str(), str.size() + 1); + } else { + Value x; + value.read(x); + LOG_CHECK(x.value == round || x.value == round - 1) << x.value << " " << round; + CHECK(x.str == to_str(x.value)); + } + check.wait(round * threads_n); + } + }); + } + for (auto &thread : threads) { + thread.join(); + } +} + +TEST(StealingQueue, simple) { + td::uint64 sum = 0; + std::atomic<td::uint64> got_sum{0}; + + td::Stage run; + td::Stage check; + + std::size_t threads_n = 10; + td::vector<td::thread> threads; + td::vector<td::StealingQueue<int, 8>> lq(threads_n); + td::MpmcQueue<int> gq(threads_n); + + constexpr td::uint64 XN = 20; + td::uint64 x_sum[XN]; + x_sum[0] = 0; + x_sum[1] = 1; + for (td::uint64 i = 2; i < XN; i++) { + x_sum[i] = i + x_sum[i - 1] + x_sum[i - 2]; + } + + td::Random::Xorshift128plus rnd(123); + for (std::size_t i = 0; i < threads_n; i++) { + threads.emplace_back([&, id = static_cast<td::uint32>(i)] { + for (td::uint64 round = 1; round < 1000; round++) { + if (id == 0) { + sum = 0; + auto n = static_cast<int>(rnd() % 5); + for (int j = 0; j < n; j++) { + auto x = static_cast<int>(rnd() % XN); + sum += x_sum[x]; + gq.push(x, id); + } + got_sum = 0; + } + run.wait(round * threads_n); + while (got_sum.load() != sum) { + auto x = [&] { + int res; + if (lq[id].local_pop(res)) { + return res; + } + if (gq.try_pop(res, id)) { + return res; + } + if (lq[id].steal(res, lq[static_cast<size_t>(rnd()) % threads_n])) { + //LOG(ERROR) << "STEAL"; + return res; + } + return 0; + }(); + if (x == 0) { + continue; + } + //LOG(ERROR) << x << " " << got_sum.load() << " " << sum; + got_sum.fetch_add(x, std::memory_order_relaxed); + lq[id].local_push(x - 1, [&](auto y) { + //LOG(ERROR) << "OVERFLOW"; + gq.push(y, id); + }); + if (x > 1) { + lq[id].local_push(x - 2, [&](auto y) { gq.push(y, id); }); + } + } + check.wait(round * threads_n); + } + }); + } + for (auto &thread : threads) { + thread.join(); + } +} +#endif diff --git a/protocols/Telegram/tdlib/td/tdutils/test/WaitFreeHashMap.cpp b/protocols/Telegram/tdlib/td/tdutils/test/WaitFreeHashMap.cpp new file mode 100644 index 0000000000..38def77772 --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/WaitFreeHashMap.cpp @@ -0,0 +1,95 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/common.h" +#include "td/utils/FlatHashMap.h" +#include "td/utils/Random.h" +#include "td/utils/tests.h" +#include "td/utils/WaitFreeHashMap.h" + +TEST(WaitFreeHashMap, stress_test) { + td::Random::Xorshift128plus rnd(123); + td::FlatHashMap<td::uint64, td::uint64> reference; + td::WaitFreeHashMap<td::uint64, td::uint64> map; + + td::vector<td::RandomSteps::Step> steps; + auto add_step = [&](td::uint32 weight, auto f) { + steps.emplace_back(td::RandomSteps::Step{std::move(f), weight}); + }; + + auto gen_key = [&] { + return rnd() % 100000 + 1; + }; + + auto check = [&](bool check_size = false) { + if (check_size) { + ASSERT_EQ(reference.size(), map.calc_size()); + } + ASSERT_EQ(reference.empty(), map.empty()); + + if (reference.size() < 100) { + td::uint64 result = 0; + for (auto &it : reference) { + result += it.first * 101; + result += it.second; + } + map.foreach([&](const td::uint64 &key, td::uint64 &value) { + result -= key * 101; + result -= value; + }); + ASSERT_EQ(0u, result); + } + }; + + add_step(2000, [&] { + auto key = gen_key(); + auto value = rnd(); + reference[key] = value; + if (td::Random::fast_bool()) { + map.set(key, value); + } else { + map[key] = value; + } + ASSERT_EQ(reference[key], map.get(key)); + check(); + }); + + add_step(200, [&] { + auto key = gen_key(); + ASSERT_EQ(reference[key], map[key]); + check(true); + }); + + add_step(2000, [&] { + auto key = gen_key(); + auto ref_it = reference.find(key); + auto ref_value = ref_it == reference.end() ? 0 : ref_it->second; + ASSERT_EQ(ref_value, map.get(key)); + check(); + }); + + add_step(500, [&] { + auto key = gen_key(); + size_t reference_erased_count = reference.erase(key); + size_t map_erased_count = map.erase(key); + ASSERT_EQ(reference_erased_count, map_erased_count); + check(); + }); + + td::RandomSteps runner(std::move(steps)); + for (size_t i = 0; i < 1000000; i++) { + runner.step(rnd); + } + + for (size_t test = 0; test < 1000; test++) { + reference = {}; + map = {}; + + for (size_t i = 0; i < 100; i++) { + runner.step(rnd); + } + } +} diff --git a/protocols/Telegram/tdlib/td/tdutils/test/WaitFreeHashSet.cpp b/protocols/Telegram/tdlib/td/tdutils/test/WaitFreeHashSet.cpp new file mode 100644 index 0000000000..ec4096c850 --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/WaitFreeHashSet.cpp @@ -0,0 +1,73 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/common.h" +#include "td/utils/FlatHashSet.h" +#include "td/utils/Random.h" +#include "td/utils/tests.h" +#include "td/utils/WaitFreeHashSet.h" + +TEST(WaitFreeHashSet, stress_test) { + td::Random::Xorshift128plus rnd(123); + td::FlatHashSet<td::uint64> reference; + td::WaitFreeHashSet<td::uint64> set; + + td::vector<td::RandomSteps::Step> steps; + auto add_step = [&](td::uint32 weight, auto f) { + steps.emplace_back(td::RandomSteps::Step{std::move(f), weight}); + }; + + auto gen_key = [&] { + return rnd() % 100000 + 1; + }; + + auto check = [&](bool check_size = false) { + if (check_size) { + ASSERT_EQ(reference.size(), set.calc_size()); + } + ASSERT_EQ(reference.empty(), set.empty()); + + if (reference.size() < 100) { + td::uint64 result = 0; + for (auto &it : reference) { + result += it * 101; + } + set.foreach([&](const td::uint64 &key) { result -= key * 101; }); + ASSERT_EQ(0u, result); + } + }; + + add_step(2000, [&] { + auto key = gen_key(); + ASSERT_EQ(reference.count(key), set.count(key)); + reference.insert(key); + set.insert(key); + ASSERT_EQ(reference.count(key), set.count(key)); + check(); + }); + + add_step(500, [&] { + auto key = gen_key(); + size_t reference_erased_count = reference.erase(key); + size_t set_erased_count = set.erase(key); + ASSERT_EQ(reference_erased_count, set_erased_count); + check(); + }); + + td::RandomSteps runner(std::move(steps)); + for (size_t i = 0; i < 1000000; i++) { + runner.step(rnd); + } + + for (size_t test = 0; test < 1000; test++) { + reference = {}; + set = {}; + + for (size_t i = 0; i < 100; i++) { + runner.step(rnd); + } + } +} diff --git a/protocols/Telegram/tdlib/td/tdutils/test/WaitFreeVector.cpp b/protocols/Telegram/tdlib/td/tdutils/test/WaitFreeVector.cpp new file mode 100644 index 0000000000..0f0cc58796 --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/WaitFreeVector.cpp @@ -0,0 +1,69 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/common.h" +#include "td/utils/Random.h" +#include "td/utils/tests.h" +#include "td/utils/WaitFreeVector.h" + +TEST(WaitFreeVector, stress_test) { + td::Random::Xorshift128plus rnd(123); + td::vector<td::uint64> reference; + td::WaitFreeVector<td::uint64> vector; + + td::vector<td::RandomSteps::Step> steps; + auto add_step = [&](td::uint32 weight, auto f) { + steps.emplace_back(td::RandomSteps::Step{std::move(f), weight}); + }; + + auto gen_key = [&] { + return static_cast<size_t>(rnd() % reference.size()); + }; + + add_step(2000, [&] { + ASSERT_EQ(reference.size(), vector.size()); + ASSERT_EQ(reference.empty(), vector.empty()); + if (reference.empty()) { + return; + } + auto key = gen_key(); + ASSERT_EQ(reference[key], vector[key]); + auto value = rnd(); + reference[key] = value; + vector[key] = value; + ASSERT_EQ(reference[key], vector[key]); + }); + + add_step(2000, [&] { + ASSERT_EQ(reference.size(), vector.size()); + ASSERT_EQ(reference.empty(), vector.empty()); + auto value = rnd(); + reference.emplace_back(value); + if (rnd() & 1) { + vector.emplace_back(value); + } else if (rnd() & 1) { + vector.push_back(value); + } else { + vector.push_back(std::move(value)); + } + ASSERT_EQ(reference.back(), vector.back()); + }); + + add_step(500, [&] { + ASSERT_EQ(reference.size(), vector.size()); + ASSERT_EQ(reference.empty(), vector.empty()); + if (reference.empty()) { + return; + } + reference.pop_back(); + vector.pop_back(); + }); + + td::RandomSteps runner(std::move(steps)); + for (size_t i = 0; i < 1000000; i++) { + runner.step(rnd); + } +} diff --git a/protocols/Telegram/tdlib/td/tdutils/test/bitmask.cpp b/protocols/Telegram/tdlib/td/tdutils/test/bitmask.cpp new file mode 100644 index 0000000000..e81c406bbe --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/bitmask.cpp @@ -0,0 +1,249 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/common.h" +#include "td/utils/misc.h" +#include "td/utils/Slice.h" +#include "td/utils/Status.h" +#include "td/utils/tests.h" +#include "td/utils/utf8.h" + +#include <algorithm> + +namespace td { + +class RangeSet { + template <class T> + static auto find(T &ranges, int64 begin) { + return std::lower_bound(ranges.begin(), ranges.end(), begin, + [](const Range &range, int64 begin) { return range.end < begin; }); + } + auto find(int64 begin) const { + return find(ranges_, begin); + } + auto find(int64 begin) { + return find(ranges_, begin); + } + + public: + struct Range { + int64 begin; + int64 end; + }; + + static constexpr int64 BIT_SIZE = 1024; + + static RangeSet create_one_range(int64 end, int64 begin = 0) { + RangeSet res; + res.ranges_.push_back({begin, end}); + return res; + } + static Result<RangeSet> decode(CSlice data) { + if (!check_utf8(data)) { + return Status::Error("Invalid encoding"); + } + uint32 curr = 0; + bool is_empty = false; + RangeSet res; + for (auto begin = data.ubegin(); begin != data.uend();) { + uint32 size; + begin = next_utf8_unsafe(begin, &size); + + if (!is_empty && size != 0) { + res.ranges_.push_back({curr * BIT_SIZE, (curr + size) * BIT_SIZE}); + } + curr += size; + is_empty = !is_empty; + } + return res; + } + + string encode(int64 prefix_size = -1) const { + vector<uint32> sizes; + uint32 all_end = 0; + + if (prefix_size != -1) { + prefix_size = (prefix_size + BIT_SIZE - 1) / BIT_SIZE * BIT_SIZE; + } + for (auto it : ranges_) { + if (prefix_size != -1 && it.begin >= prefix_size) { + break; + } + if (prefix_size != -1 && it.end > prefix_size) { + it.end = prefix_size; + } + + CHECK(it.begin % BIT_SIZE == 0); + CHECK(it.end % BIT_SIZE == 0); + auto begin = narrow_cast<uint32>(it.begin / BIT_SIZE); + auto end = narrow_cast<uint32>(it.end / BIT_SIZE); + if (sizes.empty()) { + if (begin != 0) { + sizes.push_back(0); + sizes.push_back(begin); + } + } else { + sizes.push_back(begin - all_end); + } + sizes.push_back(end - begin); + all_end = end; + } + + string res; + for (auto c : sizes) { + append_utf8_character(res, c); + } + return res; + } + + int64 get_ready_prefix_size(int64 offset, int64 file_size = -1) const { + auto it = find(offset); + if (it == ranges_.end()) { + return 0; + } + if (it->begin > offset) { + return 0; + } + CHECK(offset >= it->begin); + CHECK(offset <= it->end); + auto end = it->end; + if (file_size != -1 && end > file_size) { + end = file_size; + } + if (end < offset) { + return 0; + } + return end - offset; + } + int64 get_total_size(int64 file_size) const { + int64 res = 0; + for (auto it : ranges_) { + if (it.begin >= file_size) { + break; + } + if (it.end > file_size) { + it.end = file_size; + } + res += it.end - it.begin; + } + return res; + } + int64 get_ready_parts(int64 offset_part, int32 part_size) const { + auto offset = offset_part * part_size; + auto it = find(offset); + if (it == ranges_.end()) { + return 0; + } + if (it->begin > offset) { + return 0; + } + return (it->end - offset) / part_size; + } + + bool is_ready(int64 begin, int64 end) const { + auto it = find(begin); + if (it == ranges_.end()) { + return false; + } + return it->begin <= begin && end <= it->end; + } + + void set(int64 begin, int64 end) { + CHECK(begin % BIT_SIZE == 0); + CHECK(end % BIT_SIZE == 0); + // 1. skip all with r.end < begin + auto it_begin = find(begin); + + // 2. combine with all r.begin <= end + auto it_end = it_begin; + for (; it_end != ranges_.end() && it_end->begin <= end; ++it_end) { + } + + if (it_begin == it_end) { + ranges_.insert(it_begin, Range{begin, end}); + } else { + begin = td::min(begin, it_begin->begin); + --it_end; + end = td::max(end, it_end->end); + *it_end = Range{begin, end}; + ranges_.erase(it_begin, it_end); + } + } + + vector<int32> as_vector(int32 part_size) const { + vector<int32> res; + for (const auto &it : ranges_) { + auto begin = narrow_cast<int32>((it.begin + part_size - 1) / part_size); + auto end = narrow_cast<int32>(it.end / part_size); + while (begin < end) { + res.push_back(begin++); + } + } + return res; + } + + private: + vector<Range> ranges_; +}; + +TEST(Bitmask, simple) { + auto validate_encoding = [](auto &rs) { + auto str = rs.encode(); + RangeSet rs2 = RangeSet::decode(str).move_as_ok(); + auto str2 = rs2.encode(); + rs = std::move(rs2); + CHECK(str2 == str); + }; + { + RangeSet rs; + int32 S = 128 * 1024; + int32 O = S * 5000; + for (int i = 1; i < 30; i++) { + if (i % 2 == 0) { + rs.set(O + S * i, O + S * (i + 1)); + } + } + validate_encoding(rs); + } + { + RangeSet rs; + int32 S = 1024; + auto get = [&](auto p) { + return rs.get_ready_prefix_size(p * S) / S; + }; + auto set = [&](auto l, auto r) { + rs.set(l * S, r * S); + validate_encoding(rs); + ASSERT_TRUE(rs.is_ready(l * S, r * S)); + ASSERT_TRUE(get(l) >= (r - l)); + }; + set(6, 7); + ASSERT_EQ(1, get(6)); + ASSERT_EQ(0, get(5)); + set(8, 9); + ASSERT_EQ(0, get(7)); + set(7, 8); + ASSERT_EQ(2, get(7)); + ASSERT_EQ(3, get(6)); + set(3, 5); + ASSERT_EQ(1, get(4)); + set(4, 6); + ASSERT_EQ(5, get(4)); + set(10, 11); + set(9, 10); + ASSERT_EQ(8, get(3)); + set(14, 16); + set(12, 13); + ASSERT_EQ(8, get(3)); + + ASSERT_EQ(10, rs.get_ready_prefix_size(S * 3, S * 3 + 10)); + ASSERT_TRUE(!rs.is_ready(S * 11, S * 12)); + ASSERT_EQ(3, rs.get_ready_parts(2, S * 2)); + ASSERT_EQ(vector<int32>({2, 3, 4, 7}), rs.as_vector(S * 2)); + } +} + +} // namespace td diff --git a/protocols/Telegram/tdlib/td/tdutils/test/buffer.cpp b/protocols/Telegram/tdlib/td/tdutils/test/buffer.cpp new file mode 100644 index 0000000000..4bc406cc64 --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/buffer.cpp @@ -0,0 +1,56 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/tests.h" + +#include "td/utils/buffer.h" +#include "td/utils/Random.h" + +TEST(Buffer, buffer_builder) { + { + td::BufferBuilder builder; + builder.append("b"); + builder.prepend("a"); + builder.append("c"); + ASSERT_EQ(builder.extract().as_slice(), "abc"); + } + { + td::BufferBuilder builder{"hello", 0, 0}; + ASSERT_EQ(builder.extract().as_slice(), "hello"); + } + { + td::BufferBuilder builder{"hello", 1, 1}; + builder.prepend("A "); + builder.append(" B"); + ASSERT_EQ(builder.extract().as_slice(), "A hello B"); + } + { + auto str = td::rand_string('a', 'z', 10000); + auto split_str = td::rand_split(str); + + int l = td::Random::fast(0, static_cast<int>(split_str.size() - 1)); + int r = l; + td::BufferBuilder builder(split_str[l], 123, 1000); + while (l != 0 || r != static_cast<int>(split_str.size()) - 1) { + if (l == 0 || (td::Random::fast_bool() && r != static_cast<int>(split_str.size() - 1))) { + r++; + if (td::Random::fast_bool()) { + builder.append(split_str[r]); + } else { + builder.append(td::BufferSlice(split_str[r])); + } + } else { + l--; + if (td::Random::fast_bool()) { + builder.prepend(split_str[l]); + } else { + builder.prepend(td::BufferSlice(split_str[l])); + } + } + } + ASSERT_EQ(builder.extract().as_slice(), str); + } +} diff --git a/protocols/Telegram/tdlib/td/tdutils/test/crypto.cpp b/protocols/Telegram/tdlib/td/tdutils/test/crypto.cpp index faf4ef61a4..9e81ef132c 100644 --- a/protocols/Telegram/tdlib/td/tdutils/test/crypto.cpp +++ b/protocols/Telegram/tdlib/td/tdutils/test/crypto.cpp @@ -1,20 +1,47 @@ // -// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2018 +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // #include "td/utils/base64.h" +#include "td/utils/benchmark.h" #include "td/utils/common.h" #include "td/utils/crypto.h" +#include "td/utils/Random.h" #include "td/utils/Slice.h" +#include "td/utils/SliceBuilder.h" #include "td/utils/tests.h" +#include "td/utils/UInt.h" #include <limits> static td::vector<td::string> strings{"", "1", "short test string", td::string(1000000, 'a')}; #if TD_HAVE_OPENSSL +#if TD_HAVE_ZLIB +TEST(Crypto, Aes) { + td::Random::Xorshift128plus rnd(123); + td::UInt256 key; + rnd.bytes(as_slice(key)); + td::string plaintext(16, '\0'); + td::string encrypted(16, '\0'); + td::string decrypted(16, '\0'); + rnd.bytes(plaintext); + + td::AesState encryptor; + encryptor.init(as_slice(key), true); + td::AesState decryptor; + decryptor.init(as_slice(key), false); + + encryptor.encrypt(td::as_slice(plaintext).ubegin(), td::as_slice(encrypted).ubegin(), 16); + decryptor.decrypt(td::as_slice(encrypted).ubegin(), td::as_slice(decrypted).ubegin(), 16); + + CHECK(decrypted == plaintext); + CHECK(decrypted != encrypted); + CHECK(td::crc32(encrypted) == 178892237); +} + TEST(Crypto, AesCtrState) { td::vector<td::uint32> answers1{0u, 1141589763u, 596296607u, 3673001485u, 2302125528u, 330967191u, 2047392231u, 3537459563u, 307747798u, 2149598133u}; @@ -42,46 +69,177 @@ TEST(Crypto, AesCtrState) { } td::AesCtrState state; - state.init(key, iv); + state.init(as_slice(key), as_slice(iv)); td::string t(length, '\0'); - state.encrypt(s, t); + std::size_t pos = 0; + for (const auto &str : td::rand_split(td::string(length, '\0'))) { + auto len = str.size(); + state.encrypt(td::Slice(s).substr(pos, len), td::MutableSlice(t).substr(pos, len)); + pos += len; + } ASSERT_EQ(answers1[i], td::crc32(t)); - state.init(key, iv); - state.decrypt(t, t); - ASSERT_STREQ(s, t); + state.init(as_slice(key), as_slice(iv)); + pos = 0; + for (const auto &str : td::rand_split(td::string(length, '\0'))) { + auto len = str.size(); + state.decrypt(td::Slice(t).substr(pos, len), td::MutableSlice(t).substr(pos, len)); + pos += len; + } + ASSERT_STREQ(td::base64_encode(s), td::base64_encode(t)); for (auto &c : iv.raw) { c = 0xFF; } - state.init(key, iv); - state.encrypt(s, t); + state.init(as_slice(key), as_slice(iv)); + pos = 0; + for (const auto &str : td::rand_split(td::string(length, '\0'))) { + auto len = str.size(); + state.encrypt(td::Slice(s).substr(pos, len), td::MutableSlice(t).substr(pos, len)); + pos += len; + } ASSERT_EQ(answers2[i], td::crc32(t)); i++; } } +TEST(Crypto, AesIgeState) { + td::vector<td::uint32> answers1{0u, 2045698207u, 2423540300u, 525522475u, 1545267325u, 724143417u}; + + std::size_t i = 0; + for (auto length : {0, 16, 32, 256, 1024, 65536}) { + td::uint32 seed = length; + td::string s(length, '\0'); + for (auto &c : s) { + seed = seed * 123457567u + 987651241u; + c = static_cast<char>((seed >> 23) & 255); + } + + td::UInt256 key; + for (auto &c : key.raw) { + seed = seed * 123457567u + 987651241u; + c = (seed >> 23) & 255; + } + td::UInt256 iv; + for (auto &c : iv.raw) { + seed = seed * 123457567u + 987651241u; + c = (seed >> 23) & 255; + } + + td::AesIgeState state; + state.init(as_slice(key), as_slice(iv), true); + td::string t(length, '\0'); + td::UInt256 iv_copy = iv; + td::string u(length, '\0'); + std::size_t pos = 0; + for (const auto &str : td::rand_split(td::string(length / 16, '\0'))) { + auto len = 16 * str.size(); + state.encrypt(td::Slice(s).substr(pos, len), td::MutableSlice(t).substr(pos, len)); + td::aes_ige_encrypt(as_slice(key), as_slice(iv_copy), td::Slice(s).substr(pos, len), + td::MutableSlice(u).substr(pos, len)); + pos += len; + } + + ASSERT_EQ(answers1[i], td::crc32(t)); + ASSERT_EQ(answers1[i], td::crc32(u)); + + state.init(as_slice(key), as_slice(iv), false); + iv_copy = iv; + pos = 0; + for (const auto &str : td::rand_split(td::string(length / 16, '\0'))) { + auto len = 16 * str.size(); + state.decrypt(td::Slice(t).substr(pos, len), td::MutableSlice(t).substr(pos, len)); + td::aes_ige_decrypt(as_slice(key), as_slice(iv_copy), td::Slice(u).substr(pos, len), + td::MutableSlice(u).substr(pos, len)); + pos += len; + } + ASSERT_STREQ(td::base64_encode(s), td::base64_encode(t)); + ASSERT_STREQ(td::base64_encode(s), td::base64_encode(u)); + + i++; + } +} + +TEST(Crypto, AesCbcState) { + td::vector<td::uint32> answers1{0u, 3617355989u, 3449188102u, 186999968u, 4244808847u, 2626031206u}; + + std::size_t i = 0; + for (auto length : {0, 16, 32, 256, 1024, 65536}) { + td::uint32 seed = length; + td::string s(length, '\0'); + for (auto &c : s) { + seed = seed * 123457567u + 987651241u; + c = static_cast<char>((seed >> 23) & 255); + } + + td::UInt256 key; + for (auto &c : key.raw) { + seed = seed * 123457567u + 987651241u; + c = (seed >> 23) & 255; + } + td::UInt128 iv; + for (auto &c : iv.raw) { + seed = seed * 123457567u + 987651241u; + c = (seed >> 23) & 255; + } + + td::AesCbcState state(as_slice(key), as_slice(iv)); + td::string t(length, '\0'); + td::UInt128 iv_copy = iv; + td::string u(length, '\0'); + std::size_t pos = 0; + for (const auto &str : td::rand_split(td::string(length / 16, '\0'))) { + auto len = 16 * str.size(); + state.encrypt(td::Slice(s).substr(pos, len), td::MutableSlice(t).substr(pos, len)); + td::aes_cbc_encrypt(as_slice(key), as_slice(iv_copy), td::Slice(s).substr(pos, len), + td::MutableSlice(u).substr(pos, len)); + pos += len; + } + + ASSERT_EQ(answers1[i], td::crc32(t)); + ASSERT_EQ(answers1[i], td::crc32(u)); + + state = td::AesCbcState(as_slice(key), as_slice(iv)); + iv_copy = iv; + pos = 0; + for (const auto &str : td::rand_split(td::string(length / 16, '\0'))) { + auto len = 16 * str.size(); + state.decrypt(td::Slice(t).substr(pos, len), td::MutableSlice(t).substr(pos, len)); + td::aes_cbc_decrypt(as_slice(key), as_slice(iv_copy), td::Slice(u).substr(pos, len), + td::MutableSlice(u).substr(pos, len)); + pos += len; + } + ASSERT_STREQ(td::base64_encode(s), td::base64_encode(t)); + ASSERT_STREQ(td::base64_encode(s), td::base64_encode(u)); + + i++; + } +} +#endif + TEST(Crypto, Sha256State) { for (auto length : {0, 1, 31, 32, 33, 9999, 10000, 10001, 999999, 1000001}) { auto s = td::rand_string(std::numeric_limits<char>::min(), std::numeric_limits<char>::max(), length); td::UInt256 baseline; - td::sha256(s, td::MutableSlice(baseline.raw, 32)); + td::sha256(s, as_slice(baseline)); td::Sha256State state; - td::sha256_init(&state); + state.init(); + td::Sha256State state2 = std::move(state); auto v = td::rand_split(s); for (auto &x : v) { - td::sha256_update(x, &state); + state2.feed(x); } + state = std::move(state2); td::UInt256 result; - td::sha256_final(&state, td::MutableSlice(result.raw, 32)); + state.extract(as_slice(result)); ASSERT_TRUE(baseline == result); } } TEST(Crypto, PBKDF) { - td::vector<td::string> passwords{"", "qwerty", std::string(1000, 'a')}; - td::vector<td::string> salts{"", "qwerty", std::string(1000, 'a')}; + td::vector<td::string> passwords{"", "qwerty", td::string(1000, 'a')}; + td::vector<td::string> salts{"", "qwerty", td::string(1000, 'a')}; td::vector<int> iteration_counts{1, 2, 1000}; td::vector<td::Slice> answers{ "984LZT0tcqQQjPWr6RL/3Xd2Ftu7J6cOggTzri0Pb60=", "lzmEEdaupDp3rO+SImq4J41NsGaL0denanJfdoCsRcU=", @@ -145,6 +303,32 @@ TEST(Crypto, md5) { ASSERT_STREQ(answers[i], td::base64_encode(output)); } } + +TEST(Crypto, hmac_sha256) { + td::vector<td::Slice> answers{ + "t33rfT85UOe6N00BhsNwobE+f2TnW331HhdvQ4GdJp8=", "BQl5HF2jqhCz4JTqhAs+H364oxboh7QlluOMHuuRVh8=", + "NCCPuZBsAPBd/qr3SyeYE+e1RNgzkKJCS/+eXDBw8zU=", "mo3ahTkyLKfoQoYA0s7vRZULuH++vqwFJD0U5n9HHw0="}; + + for (std::size_t i = 0; i < strings.size(); i++) { + td::string output(32, '\0'); + td::hmac_sha256("cucumber", strings[i], output); + ASSERT_STREQ(answers[i], td::base64_encode(output)); + } +} + +TEST(Crypto, hmac_sha512) { + td::vector<td::Slice> answers{ + "o28hTN1m/TGlm/VYxDIzOdUE4wMpQzO8hVcTkiP2ezEJXtrOvCjRnl20aOV1S8axA5Te0TzIjfIoEAtpzamIsA==", + "32X3GslSz0HDznSrCNt++ePRcFVSUSD+tfOVannyxS+yLt/om11qILCE64RFTS8/B84gByMzC3FuAlfcIam/KA==", + "BVqe5rK1Fg1i+C7xXTAzT9vDPcf3kQQpTtse6rT/EVDzKo9AUo4ZwyUyJ0KcLHoffIjul/TuJoBg+wLz7Z7r7g==", + "WASmeku5Pcfz7N0Kp4Q3I9sxtO2MiaBXA418CY0HvjdtmAo7QY+K3E0o9UemgGzz41KqeypzRC92MwOAOnXJLA=="}; + + for (std::size_t i = 0; i < strings.size(); i++) { + td::string output(64, '\0'); + td::hmac_sha512("cucumber", strings[i], output); + ASSERT_STREQ(answers[i], td::base64_encode(output)); + } +} #endif #if TD_HAVE_ZLIB @@ -157,6 +341,69 @@ TEST(Crypto, crc32) { } #endif +#if TD_HAVE_CRC32C +TEST(Crypto, crc32c) { + td::vector<td::uint32> answers{0u, 2432014819u, 1077264849u, 1131405888u}; + + for (std::size_t i = 0; i < strings.size(); i++) { + ASSERT_EQ(answers[i], td::crc32c(strings[i])); + + auto v = td::rand_split(strings[i]); + td::uint32 a = 0; + td::uint32 b = 0; + for (auto &x : v) { + a = td::crc32c_extend(a, x); + auto x_crc = td::crc32c(x); + b = td::crc32c_extend(b, x_crc, x.size()); + } + ASSERT_EQ(answers[i], a); + ASSERT_EQ(answers[i], b); + } +} + +TEST(Crypto, crc32c_benchmark) { + class Crc32cExtendBenchmark final : public td::Benchmark { + public: + explicit Crc32cExtendBenchmark(size_t chunk_size) : chunk_size_(chunk_size) { + } + td::string get_description() const final { + return PSTRING() << "Crc32c with chunk_size=" << chunk_size_; + } + void start_up_n(int n) final { + if (n > (1 << 20)) { + cnt_ = n / (1 << 20); + n = (1 << 20); + } else { + cnt_ = 1; + } + data_ = td::string(n, 'a'); + } + void run(int n) final { + td::uint32 res = 0; + for (int i = 0; i < cnt_; i++) { + td::Slice data(data_); + while (!data.empty()) { + auto head = data.substr(0, chunk_size_); + data = data.substr(head.size()); + res = td::crc32c_extend(res, head); + } + } + td::do_not_optimize_away(res); + } + + private: + size_t chunk_size_; + td::string data_; + int cnt_; + }; + bench(Crc32cExtendBenchmark(2)); + bench(Crc32cExtendBenchmark(8)); + bench(Crc32cExtendBenchmark(32)); + bench(Crc32cExtendBenchmark(128)); + bench(Crc32cExtendBenchmark(65536)); +} +#endif + TEST(Crypto, crc64) { td::vector<td::uint64> answers{0ull, 3039664240384658157ull, 17549519902062861804ull, 8794730974279819706ull}; @@ -164,3 +411,61 @@ TEST(Crypto, crc64) { ASSERT_EQ(answers[i], td::crc64(strings[i])); } } + +TEST(Crypto, crc16) { + td::vector<td::uint16> answers{0, 9842, 25046, 37023}; + + for (std::size_t i = 0; i < strings.size(); i++) { + ASSERT_EQ(answers[i], td::crc16(strings[i])); + } +} + +static td::Slice rsa_private_key = R"ABCD( +-----BEGIN PRIVATE KEY----- +MIIEvQIBADANBgkqhkiG9w0BAQEFAASCBKcwggSjAgEAAoIBAQDeYT5/prmLEa2Q +tZND+UwTmif8kl2VlXaMCjj1k1lJJq8BqS8cVM2vPnOPzFoiC2LYykhm4kk7goCC +ZH6wez9yakg28fcq0Ycv0x8DL1K+VKHJuwIhVfQs//IY1/cBOrMESc+NQowPbv1t +TIFxBO2gebnpLuseht8ix7XtpGC4qAaHN2aEvT2cRsnA76TAK1RVxf1OYGUFBDzY +318WpVZfVIjcQ7K9+eU6b2Yb84VLlvJXw3e1rvw+fBzx2EjpD4zhXy11YppWDyV6 +HEb2hs3cGS/LbHfHvdcSfil2omaJP97MDEEY2HFxjR/E5CEf2suvPzX4XS3RE+S3 +2aEJaaQbAgMBAAECggEAKo3XRNwls0wNt5xXcvF4smOUdUuY5u/0AHZQUgYBVvM1 +GA9E+ZnsxjUgLgs/0DX3k16aHj39H4sohksuxxy+lmlqKkGBN8tioC85RwW+Qre1 +QgIsNS7ai+XqcQCavrx51z88nV53qNhnXIwAVR1JT6Ubg1i8G1pZxrEKyk/jRlJd +mGjf6vjitH//PPkghPJ/D42k93YRcy+duOgqYDQpLZp8DiEGfYrX10B1H7HrWLV+ +Wp5KO1YXtKgQUplj6kYy72bVajbxYTvzgjaaKsh74jBO0uT3tHTtXG0dcKGb0VR/ +cqP/1H/lC9bAnAqAGefNusGJQZIElvTsrpIQXOeZsQKBgQD2W04S+FjqYYFjnEFX +6eL4it01afs5M3/C6CcI5JQtN6p+Na4NCSILol33xwhakn87zqdADHawBYQVQ8Uw +dPurl805wfkzN3AbfdDmtx0IJ8vK4HFpktRjfpwBVhlVtm1doAYFqqsuCF2vWW1t +mM2YOSq4AnRHCeBb/P6kRIW0MwKBgQDnFawKKqiC4tuyBOkkEhexlm7x9he0md7D +3Z2hc3Bmdcq1niw4wBq3HUxGLReGCcSr5epKSQwkunlTn5ZSC6Rmbe4zxsGIwbb3 +5W3342swBaoxEIuBokBvZ/xUOXVwiqKj+S/NzVkZcnT6K9V/HnUCQR+JBbQxFQaX +iiezcjKoeQKBgCIVUcDoIQ0UPl10ocmy7xbpx177calhSZzCl5vwW9vBptHdRV5C +VDZ92ThNjgdR205/8b23u7fwm2yBusdQd/0ufFMwVfTTB6yWBI/W56pYLya7VJWB +nebB/n1k1w53tbvNRugDy7kLqUJ4Qd521ILp7dIVbNbjM+omH2jEnibnAoGBAIM5 +a1jaoJay/M86uqohHBNcuePtO8jzF+1iDAGC7HFCsrov+CzB6mnR2V6AfLtBEM4M +4d8NXDf/LKawGUy+D72a74m3dG+UkbJ0Nt5t5pB+pwb1vkL/QFgDVOb/OhGOqI01 +FFBqLA6nUIZAHhzxzsBY+u90rb6xkey8J49faiUBAoGAaMgOgEvQB5H19ZL5tMkl +A/DKtTz/NFzN4Zw/vNPVb7eNn4jg9M25d9xqvL4acOa+nuV3nLHbcUWE1/7STXw1 +gT58CvoEmD1AiP95nup+HKHENJ1DWMgF5MDfVQwGCvWP5/Qy89ybr0eG8HjbldbN +MpSmzz2wOz152oGdOd3syT4= +-----END PRIVATE KEY----- +)ABCD"; + +static td::Slice rsa_public_key = R"ABCD( +-----BEGIN PUBLIC KEY----- +MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA3mE+f6a5ixGtkLWTQ/lM +E5on/JJdlZV2jAo49ZNZSSavAakvHFTNrz5zj8xaIgti2MpIZuJJO4KAgmR+sHs/ +cmpINvH3KtGHL9MfAy9SvlShybsCIVX0LP/yGNf3ATqzBEnPjUKMD279bUyBcQTt +oHm56S7rHobfIse17aRguKgGhzdmhL09nEbJwO+kwCtUVcX9TmBlBQQ82N9fFqVW +X1SI3EOyvfnlOm9mG/OFS5byV8N3ta78Pnwc8dhI6Q+M4V8tdWKaVg8lehxG9obN +3Bkvy2x3x73XEn4pdqJmiT/ezAxBGNhxcY0fxOQhH9rLrz81+F0t0RPkt9mhCWmk +GwIDAQAB +-----END PUBLIC KEY----- +)ABCD"; + +TEST(Crypto, rsa) { + auto value = td::rand_string('a', 'z', 200); + auto encrypted_value = td::rsa_encrypt_pkcs1_oaep(rsa_public_key, value).move_as_ok(); + auto decrypted_value = td::rsa_decrypt_pkcs1_oaep(rsa_private_key, encrypted_value.as_slice()).move_as_ok(); + ASSERT_TRUE(decrypted_value.as_slice().truncate(value.size()) == value); +} diff --git a/protocols/Telegram/tdlib/td/tdutils/test/emoji.cpp b/protocols/Telegram/tdlib/td/tdutils/test/emoji.cpp new file mode 100644 index 0000000000..c8e6539a99 --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/emoji.cpp @@ -0,0 +1,128 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/emoji.h" +#include "td/utils/tests.h" + +TEST(Emoji, is_emoji) { + ASSERT_TRUE(!td::is_emoji("")); + ASSERT_TRUE(td::is_emoji("👩🏼❤💋👩🏻")); + ASSERT_TRUE(td::is_emoji("👩🏼❤️💋👩🏻")); + ASSERT_TRUE(!td::is_emoji("👩🏼❤️️💋👩🏻")); + ASSERT_TRUE(td::is_emoji("⌚")); + ASSERT_TRUE(td::is_emoji("↔")); + ASSERT_TRUE(td::is_emoji("🪗")); + ASSERT_TRUE(td::is_emoji("2️⃣")); + ASSERT_TRUE(td::is_emoji("2⃣")); + ASSERT_TRUE(!td::is_emoji(" 2⃣")); + ASSERT_TRUE(!td::is_emoji("2⃣ ")); + ASSERT_TRUE(!td::is_emoji(" ")); + ASSERT_TRUE(!td::is_emoji("")); + ASSERT_TRUE(!td::is_emoji("1234567890123456789012345678901234567890123456789012345678901234567890")); + ASSERT_TRUE(td::is_emoji("❤️")); + ASSERT_TRUE(td::is_emoji("❤")); + ASSERT_TRUE(td::is_emoji("⌚")); + ASSERT_TRUE(td::is_emoji("🎄")); + ASSERT_TRUE(td::is_emoji("🧑🎄")); +} + +static void test_get_fitzpatrick_modifier(td::string emoji, int result) { + ASSERT_EQ(result, td::get_fitzpatrick_modifier(emoji)); +} + +TEST(Emoji, get_fitzpatrick_modifier) { + test_get_fitzpatrick_modifier("", 0); + test_get_fitzpatrick_modifier("👩🏼❤💋👩🏻", 2); + test_get_fitzpatrick_modifier("👩🏼❤️💋👩🏻", 2); + test_get_fitzpatrick_modifier("👋", 0); + test_get_fitzpatrick_modifier("👋🏻", 2); + test_get_fitzpatrick_modifier("👋🏼", 3); + test_get_fitzpatrick_modifier("👋🏽", 4); + test_get_fitzpatrick_modifier("👋🏾", 5); + test_get_fitzpatrick_modifier("👋🏿", 6); + test_get_fitzpatrick_modifier("🏻", 2); + test_get_fitzpatrick_modifier("🏼", 3); + test_get_fitzpatrick_modifier("🏽", 4); + test_get_fitzpatrick_modifier("🏾", 5); + test_get_fitzpatrick_modifier("🏿", 6); + test_get_fitzpatrick_modifier("⌚", 0); + test_get_fitzpatrick_modifier("↔", 0); + test_get_fitzpatrick_modifier("🪗", 0); + test_get_fitzpatrick_modifier("2️⃣", 0); + test_get_fitzpatrick_modifier("2⃣", 0); + test_get_fitzpatrick_modifier("❤️", 0); + test_get_fitzpatrick_modifier("❤", 0); + test_get_fitzpatrick_modifier("⌚", 0); + test_get_fitzpatrick_modifier("🎄", 0); + test_get_fitzpatrick_modifier("🧑🎄", 0); +} + +static void test_remove_emoji_modifiers(td::string emoji, const td::string &result) { + ASSERT_STREQ(result, td::remove_emoji_modifiers(emoji)); + td::remove_emoji_modifiers_in_place(emoji); + ASSERT_STREQ(result, emoji); + ASSERT_STREQ(emoji, td::remove_emoji_modifiers(emoji)); +} + +TEST(Emoji, remove_emoji_modifiers) { + test_remove_emoji_modifiers("", ""); + test_remove_emoji_modifiers("👩🏼❤💋👩🏻", "👩❤💋👩"); + test_remove_emoji_modifiers("👩🏼❤️💋👩🏻", "👩❤💋👩"); + test_remove_emoji_modifiers("👋🏻", "👋"); + test_remove_emoji_modifiers("👋🏼", "👋"); + test_remove_emoji_modifiers("👋🏽", "👋"); + test_remove_emoji_modifiers("👋🏾", "👋"); + test_remove_emoji_modifiers("👋🏿", "👋"); + test_remove_emoji_modifiers("🏻", "🏻"); + test_remove_emoji_modifiers("🏼", "🏼"); + test_remove_emoji_modifiers("🏽", "🏽"); + test_remove_emoji_modifiers("🏾", "🏾"); + test_remove_emoji_modifiers("🏿", "🏿"); + test_remove_emoji_modifiers("⌚", "⌚"); + test_remove_emoji_modifiers("↔", "↔"); + test_remove_emoji_modifiers("🪗", "🪗"); + test_remove_emoji_modifiers("2️⃣", "2⃣"); + test_remove_emoji_modifiers("2⃣", "2⃣"); + test_remove_emoji_modifiers("❤️", "❤"); + test_remove_emoji_modifiers("❤", "❤"); + test_remove_emoji_modifiers("⌚", "⌚"); + test_remove_emoji_modifiers("️", "️"); + test_remove_emoji_modifiers("️️️🏻", "️️️🏻"); + test_remove_emoji_modifiers("️️️🏻a", "a"); + test_remove_emoji_modifiers("🎄", "🎄"); + test_remove_emoji_modifiers("🧑🎄", "🧑🎄"); +} + +static void test_remove_emoji_selectors(td::string emoji, const td::string &result) { + ASSERT_STREQ(result, td::remove_emoji_selectors(result)); + ASSERT_STREQ(result, td::remove_emoji_selectors(emoji)); +} + +TEST(Emoji, remove_emoji_selectors) { + test_remove_emoji_selectors("", ""); + test_remove_emoji_selectors("👩🏼❤💋👩🏻", "👩🏼❤💋👩🏻"); + test_remove_emoji_selectors("👩🏼❤️💋👩🏻", "👩🏼❤💋👩🏻"); + test_remove_emoji_selectors("👋🏻", "👋🏻"); + test_remove_emoji_selectors("👋🏼", "👋🏼"); + test_remove_emoji_selectors("👋🏽", "👋🏽"); + test_remove_emoji_selectors("👋🏾", "👋🏾"); + test_remove_emoji_selectors("👋🏿", "👋🏿"); + test_remove_emoji_selectors("🏻", "🏻"); + test_remove_emoji_selectors("🏼", "🏼"); + test_remove_emoji_selectors("🏽", "🏽"); + test_remove_emoji_selectors("🏾", "🏾"); + test_remove_emoji_selectors("🏿", "🏿"); + test_remove_emoji_selectors("⌚", "⌚"); + test_remove_emoji_selectors("↔", "↔"); + test_remove_emoji_selectors("🪗", "🪗"); + test_remove_emoji_selectors("2️⃣", "2⃣"); + test_remove_emoji_selectors("2⃣", "2⃣"); + test_remove_emoji_selectors("❤️", "❤"); + test_remove_emoji_selectors("❤", "❤"); + test_remove_emoji_selectors("⌚", "⌚"); + test_remove_emoji_selectors("🎄", "🎄"); + test_remove_emoji_selectors("🧑🎄", "🧑🎄"); +} diff --git a/protocols/Telegram/tdlib/td/tdutils/test/filesystem.cpp b/protocols/Telegram/tdlib/td/tdutils/test/filesystem.cpp index a0a92c14eb..de2def1e5e 100644 --- a/protocols/Telegram/tdlib/td/tdutils/test/filesystem.cpp +++ b/protocols/Telegram/tdlib/td/tdutils/test/filesystem.cpp @@ -1,41 +1,47 @@ // -// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2018 +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // #include "td/utils/filesystem.h" +#include "td/utils/Slice.h" #include "td/utils/tests.h" +static void test_clean_filename(td::CSlice name, td::Slice result) { + ASSERT_STREQ(td::clean_filename(name), result); +} + TEST(Misc, clean_filename) { - using td::clean_filename; - ASSERT_STREQ(clean_filename("-1234567"), "-1234567"); - ASSERT_STREQ(clean_filename(".git"), "git"); - ASSERT_STREQ(clean_filename("../../.git"), "git"); - ASSERT_STREQ(clean_filename(".././.."), ""); - ASSERT_STREQ(clean_filename("../"), ""); - ASSERT_STREQ(clean_filename(".."), ""); - ASSERT_STREQ(clean_filename("test/git/ as dsa . a"), "as dsa.a"); - ASSERT_STREQ(clean_filename(" . "), ""); - ASSERT_STREQ(clean_filename("!@#$%^&*()_+-=[]{;|:\"}'<>?,.`~"), "!@#$%^ ()_+-=[]{; } ,.~"); - ASSERT_STREQ(clean_filename("!@#$%^&*()_+-=[]{}\\|:\";'<>?,.`~"), "; ,.~"); - ASSERT_STREQ(clean_filename("عرفها بعد قد. هذا مع تاريخ اليميني واندونيسيا،, لعدم تاريخ لهيمنة الى"), - "عرفها بعد قد.هذا مع تاريخ اليميني"); - ASSERT_STREQ( - clean_filename( - "012345678901234567890123456789012345678901234567890123456789adsasdasdsaa.01234567890123456789asdasdasdasd"), - "012345678901234567890123456789012345678901234567890123456789.01234567890123456789"); - ASSERT_STREQ(clean_filename("01234567890123456789012345678901234567890123456789<>*?: <>*?:0123456789adsasdasdsaa. " - "0123456789`<><<>><><>0123456789asdasdasdasd"), - "01234567890123456789012345678901234567890123456789.0123456789"); - ASSERT_STREQ(clean_filename("01234567890123456789012345678901234567890123456789<>*?: <>*?:0123456789adsasdasdsaa. " - "0123456789`<><><>0123456789asdasdasdasd"), - "01234567890123456789012345678901234567890123456789.0123456789 012"); - ASSERT_STREQ(clean_filename("C:/document.tar.gz"), "document.tar.gz"); - ASSERT_STREQ(clean_filename("test...."), "test"); - ASSERT_STREQ(clean_filename("....test"), "test"); - ASSERT_STREQ(clean_filename("test.exe...."), "test.exe"); // extension has changed - ASSERT_STREQ(clean_filename("test.exe01234567890123456789...."), - "test.exe01234567890123456789"); // extension may be more then 20 characters - ASSERT_STREQ(clean_filename("....test....asdf"), "test.asdf"); + test_clean_filename("-1234567", "-1234567"); + test_clean_filename(".git", "git"); + test_clean_filename("../../.git", "git"); + test_clean_filename(".././..", ""); + test_clean_filename("../", ""); + test_clean_filename("..", ""); + test_clean_filename("test/git/ as dsa . a", "as dsa.a"); + test_clean_filename(" . ", ""); + test_clean_filename("!@#$%^&*()_+-=[]{;|:\"}'<>?,.`~", "!@#$%^ ()_+-=[]{; } ,.~"); + test_clean_filename("!@#$%^&*()_+-=[]{}\\|:\";'<>?,.`~", "; ,.~"); + test_clean_filename("عرفها بعد قد. هذا مع تاريخ اليميني واندونيسيا،, لعدم تاريخ لهيمنة الى", + "عرفها بعد قد.هذا مع تاريخ الي"); + test_clean_filename( + "012345678901234567890123456789012345678901234567890123456789adsasdasdsaa.01234567890123456789asdasdasdasd", + "012345678901234567890123456789012345678901234567890123456789adsa.0123456789012345"); + test_clean_filename( + "01234567890123456789012345678901234567890123456789adsa<>*?: <>*?:0123456789adsasdasdsaa. " + "0123456789`<><<>><><>0123456789asdasdasdasd", + "01234567890123456789012345678901234567890123456789adsa.0123456789"); + test_clean_filename( + "012345678901234567890123456789012345678901234567890123<>*?: <>*?:0123456789adsasdasdsaa. " + "0123456789`<>0123456789asdasdasdasd", + "012345678901234567890123456789012345678901234567890123.0123456789 012"); + test_clean_filename("C:/document.tar.gz", "document.tar.gz"); + test_clean_filename("test....", "test"); + test_clean_filename("....test", "test"); + test_clean_filename("test.exe....", "test.exe"); // extension has changed + test_clean_filename("test.exe01234567890123456789....", + "test.exe01234567890123456789"); // extension may be more than 16 characters + test_clean_filename("....test....asdf", "test.asdf"); + test_clean_filename("കറുപ്പ്.txt", "കറപപ.txt"); } diff --git a/protocols/Telegram/tdlib/td/tdutils/test/gzip.cpp b/protocols/Telegram/tdlib/td/tdutils/test/gzip.cpp index e4bd81eb0d..32d75474e8 100644 --- a/protocols/Telegram/tdlib/td/tdutils/test/gzip.cpp +++ b/protocols/Telegram/tdlib/td/tdutils/test/gzip.cpp @@ -1,49 +1,59 @@ // -// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2018 +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // +#include "td/utils/algorithm.h" #include "td/utils/buffer.h" #include "td/utils/ByteFlow.h" +#include "td/utils/common.h" #include "td/utils/Gzip.h" #include "td/utils/GzipByteFlow.h" #include "td/utils/logging.h" +#include "td/utils/port/thread_local.h" +#include "td/utils/Slice.h" #include "td/utils/Status.h" #include "td/utils/tests.h" +#include "td/utils/Time.h" -static void encode_decode(td::string s) { +static void encode_decode(const td::string &s) { auto r = td::gzencode(s, 2); ASSERT_TRUE(!r.empty()); - if (r.empty()) { - return; - } - auto new_s = td::gzdecode(r.as_slice()); - ASSERT_TRUE(!new_s.empty()); - if (new_s.empty()) { - return; - } - ASSERT_EQ(s, new_s.as_slice().str()); + ASSERT_EQ(s, td::gzdecode(r.as_slice())); } TEST(Gzip, gzencode_gzdecode) { - auto str = td::rand_string(0, 127, 1000); - encode_decode(str); - str = td::rand_string('a', 'z', 1000000); - encode_decode(str); - str = td::string(1000000, 'a'); - encode_decode(str); + encode_decode(td::rand_string(0, 255, 1000)); + encode_decode(td::rand_string('a', 'z', 1000000)); + encode_decode(td::string(1000000, 'a')); +} + +static void test_gzencode(const td::string &s) { + auto begin_time = td::Time::now(); + auto r = td::gzencode(s, td::max(2, static_cast<int>(100 / s.size()))); + ASSERT_TRUE(!r.empty()); + LOG(INFO) << "Encoded string of size " << s.size() << " in " << (td::Time::now() - begin_time) + << " with compression ratio " << static_cast<double>(r.size()) / static_cast<double>(s.size()); +} + +TEST(Gzip, gzencode) { + for (size_t len = 1; len <= 10000000; len *= 10) { + test_gzencode(td::rand_string('a', 'a', len)); + test_gzencode(td::rand_string('a', 'z', len)); + test_gzencode(td::rand_string(0, 255, len)); + } } TEST(Gzip, flow) { auto str = td::rand_string('a', 'z', 1000000); auto parts = td::rand_split(str); - auto input_writer = td::ChainBufferWriter::create_empty(); + td::ChainBufferWriter input_writer; auto input = input_writer.extract_reader(); td::ByteFlowSource source(&input); - td::GzipByteFlow gzip_flow(td::Gzip::Encode); - gzip_flow = td::GzipByteFlow(td::Gzip::Encode); + td::GzipByteFlow gzip_flow(td::Gzip::Mode::Encode); + gzip_flow = td::GzipByteFlow(td::Gzip::Mode::Encode); td::ByteFlowSink sink; source >> gzip_flow >> sink; @@ -63,14 +73,15 @@ TEST(Gzip, flow) { } TEST(Gzip, flow_error) { auto str = td::rand_string('a', 'z', 1000000); - auto zip = td::gzencode(str).as_slice().str(); + auto zip = td::gzencode(str, 0.9).as_slice().str(); + ASSERT_TRUE(!zip.empty()); zip.resize(zip.size() - 1); auto parts = td::rand_split(zip); auto input_writer = td::ChainBufferWriter(); auto input = input_writer.extract_reader(); td::ByteFlowSource source(&input); - td::GzipByteFlow gzip_flow(td::Gzip::Decode); + td::GzipByteFlow gzip_flow(td::Gzip::Mode::Decode); td::ByteFlowSink sink; source >> gzip_flow >> sink; @@ -89,13 +100,13 @@ TEST(Gzip, flow_error) { TEST(Gzip, encode_decode_flow) { auto str = td::rand_string('a', 'z', 1000000); auto parts = td::rand_split(str); - auto input_writer = td::ChainBufferWriter::create_empty(); + td::ChainBufferWriter input_writer; auto input = input_writer.extract_reader(); td::ByteFlowSource source(&input); - td::GzipByteFlow gzip_encode_flow(td::Gzip::Encode); - td::GzipByteFlow gzip_decode_flow(td::Gzip::Decode); - td::GzipByteFlow gzip_encode_flow2(td::Gzip::Encode); - td::GzipByteFlow gzip_decode_flow2(td::Gzip::Decode); + td::GzipByteFlow gzip_encode_flow(td::Gzip::Mode::Encode); + td::GzipByteFlow gzip_decode_flow(td::Gzip::Mode::Decode); + td::GzipByteFlow gzip_encode_flow2(td::Gzip::Mode::Encode); + td::GzipByteFlow gzip_decode_flow2(td::Gzip::Mode::Decode); td::ByteFlowSink sink; source >> gzip_encode_flow >> gzip_decode_flow >> gzip_encode_flow2 >> gzip_decode_flow2 >> sink; @@ -111,3 +122,126 @@ TEST(Gzip, encode_decode_flow) { ASSERT_TRUE(sink.status().is_ok()); ASSERT_EQ(str, sink.result()->move_as_buffer_slice().as_slice().str()); } + +TEST(Gzip, encode_decode_flow_big) { + td::clear_thread_locals(); + auto start_mem = td::BufferAllocator::get_buffer_mem(); + { + auto str = td::string(200000, 'a'); + td::ChainBufferWriter input_writer; + auto input = input_writer.extract_reader(); + td::ByteFlowSource source(&input); + td::GzipByteFlow gzip_encode_flow(td::Gzip::Mode::Encode); + td::GzipByteFlow gzip_decode_flow(td::Gzip::Mode::Decode); + td::GzipByteFlow gzip_encode_flow2(td::Gzip::Mode::Encode); + td::GzipByteFlow gzip_decode_flow2(td::Gzip::Mode::Decode); + td::ByteFlowSink sink; + source >> gzip_encode_flow >> gzip_decode_flow >> gzip_encode_flow2 >> gzip_decode_flow2 >> sink; + + ASSERT_TRUE(!sink.is_ready()); + size_t n = 200; + size_t left_size = n * str.size(); + auto validate = [&](td::Slice chunk) { + CHECK(chunk.size() <= left_size); + left_size -= chunk.size(); + ASSERT_TRUE(td::all_of(chunk, [](auto c) { return c == 'a'; })); + }; + + for (size_t i = 0; i < n; i++) { + input_writer.append(str); + source.wakeup(); + auto extra_mem = td::BufferAllocator::get_buffer_mem() - start_mem; + // limit means nothing. just check that we do not use 200Mb or so + CHECK(extra_mem < (10 << 20)); + + auto size = sink.get_output()->size(); + validate(sink.get_output()->cut_head(size).move_as_buffer_slice().as_slice()); + } + ASSERT_TRUE(!sink.is_ready()); + source.close_input(td::Status::OK()); + ASSERT_TRUE(sink.is_ready()); + LOG_IF(ERROR, sink.status().is_error()) << sink.status(); + ASSERT_TRUE(sink.status().is_ok()); + validate(sink.result()->move_as_buffer_slice().as_slice()); + ASSERT_EQ(0u, left_size); + } + td::clear_thread_locals(); + ASSERT_EQ(start_mem, td::BufferAllocator::get_buffer_mem()); +} + +TEST(Gzip, decode_encode_flow_bomb) { + td::string gzip_bomb_str; + size_t N = 200; + { + td::ChainBufferWriter input_writer; + auto input = input_writer.extract_reader(); + td::GzipByteFlow gzip_flow(td::Gzip::Mode::Encode); + td::ByteFlowSource source(&input); + td::ByteFlowSink sink; + source >> gzip_flow >> sink; + + td::string s(1 << 16, 'a'); + for (size_t i = 0; i < N; i++) { + input_writer.append(s); + source.wakeup(); + } + source.close_input(td::Status::OK()); + ASSERT_TRUE(sink.is_ready()); + LOG_IF(ERROR, sink.status().is_error()) << sink.status(); + ASSERT_TRUE(sink.status().is_ok()); + gzip_bomb_str = sink.result()->move_as_buffer_slice().as_slice().str(); + } + + td::clear_thread_locals(); + auto start_mem = td::BufferAllocator::get_buffer_mem(); + { + td::ChainBufferWriter input_writer; + auto input = input_writer.extract_reader(); + td::ByteFlowSource source(&input); + td::GzipByteFlow::Options decode_options; + decode_options.write_watermark.low = 2 << 20; + decode_options.write_watermark.high = 4 << 20; + td::GzipByteFlow::Options encode_options; + encode_options.read_watermark.low = 2 << 20; + encode_options.read_watermark.high = 4 << 20; + td::GzipByteFlow gzip_decode_flow(td::Gzip::Mode::Decode); + gzip_decode_flow.set_options(decode_options); + td::GzipByteFlow gzip_encode_flow(td::Gzip::Mode::Encode); + gzip_encode_flow.set_options(encode_options); + td::GzipByteFlow gzip_decode_flow2(td::Gzip::Mode::Decode); + gzip_decode_flow2.set_options(decode_options); + td::GzipByteFlow gzip_encode_flow2(td::Gzip::Mode::Encode); + gzip_encode_flow2.set_options(encode_options); + td::GzipByteFlow gzip_decode_flow3(td::Gzip::Mode::Decode); + gzip_decode_flow3.set_options(decode_options); + td::ByteFlowSink sink; + source >> gzip_decode_flow >> gzip_encode_flow >> gzip_decode_flow2 >> gzip_encode_flow2 >> gzip_decode_flow3 >> + sink; + + ASSERT_TRUE(!sink.is_ready()); + size_t left_size = N * (1 << 16); + auto validate = [&](td::Slice chunk) { + CHECK(chunk.size() <= left_size); + left_size -= chunk.size(); + ASSERT_TRUE(td::all_of(chunk, [](auto c) { return c == 'a'; })); + }; + + input_writer.append(gzip_bomb_str); + source.close_input(td::Status::OK()); + + do { + gzip_decode_flow3.wakeup(); + gzip_decode_flow2.wakeup(); + gzip_decode_flow.wakeup(); + source.wakeup(); + auto extra_mem = td::BufferAllocator::get_buffer_mem() - start_mem; + // limit means nothing. just check that we do not use 15Mb or so + CHECK(extra_mem < (5 << 20)); + auto size = sink.get_output()->size(); + validate(sink.get_output()->cut_head(size).move_as_buffer_slice().as_slice()); + } while (!sink.is_ready()); + ASSERT_EQ(0u, left_size); + } + td::clear_thread_locals(); + ASSERT_EQ(start_mem, td::BufferAllocator::get_buffer_mem()); +} diff --git a/protocols/Telegram/tdlib/td/tdutils/test/hashset_benchmark.cpp b/protocols/Telegram/tdlib/td/tdutils/test/hashset_benchmark.cpp new file mode 100644 index 0000000000..f07f58c8f0 --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/hashset_benchmark.cpp @@ -0,0 +1,647 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/algorithm.h" +#include "td/utils/common.h" +#include "td/utils/FlatHashMap.h" +#include "td/utils/FlatHashMapChunks.h" +#include "td/utils/FlatHashTable.h" +#include "td/utils/format.h" +#include "td/utils/HashTableUtils.h" +#include "td/utils/logging.h" +#include "td/utils/MapNode.h" +#include "td/utils/Random.h" +#include "td/utils/Slice.h" +#include "td/utils/Span.h" +#include "td/utils/StringBuilder.h" +#include "td/utils/Time.h" +#include "td/utils/VectorQueue.h" + +#ifdef SCOPE_EXIT +#undef SCOPE_EXIT +#endif + +#include <absl/container/flat_hash_map.h> +#include <absl/hash/hash.h> +#include <algorithm> +#include <benchmark/benchmark.h> +#include <folly/container/F14Map.h> +#include <functional> +#include <map> +#include <random> +#include <unordered_map> +#include <utility> + +template <class TableT> +static void reserve(TableT &table, std::size_t size) { + table.reserve(size); +} + +template <class A, class B> +static void reserve(std::map<A, B> &table, std::size_t size) { +} + +template <class KeyT, class ValueT> +class NoOpTable { + public: + using key_type = KeyT; + using value_type = std::pair<const KeyT, ValueT>; + template <class It> + NoOpTable(It begin, It end) { + } + + ValueT &operator[](const KeyT &) const { + static ValueT dummy; + return dummy; + } + + KeyT find(const KeyT &key) const { + return key; + } +}; + +template <class KeyT, class ValueT> +class VectorTable { + public: + using key_type = KeyT; + using value_type = std::pair<const KeyT, ValueT>; + template <class It> + VectorTable(It begin, It end) : table_(begin, end) { + } + + ValueT &operator[](const KeyT &needle) { + auto it = find(needle); + if (it == table_.end()) { + table_.emplace_back(needle, ValueT{}); + return table_.back().second; + } + return it->second; + } + auto find(const KeyT &needle) { + return std::find_if(table_.begin(), table_.end(), [&](auto &key) { return key.first == needle; }); + } + + private: + using KeyValue = value_type; + td::vector<KeyValue> table_; +}; + +template <class KeyT, class ValueT> +class SortedVectorTable { + public: + using key_type = KeyT; + using value_type = std::pair<KeyT, ValueT>; + template <class It> + SortedVectorTable(It begin, It end) : table_(begin, end) { + std::sort(table_.begin(), table_.end()); + } + + ValueT &operator[](const KeyT &needle) { + auto it = std::lower_bound(table_.begin(), table_.end(), needle, + [](const auto &l, const auto &r) { return l.first < r; }); + if (it == table_.end() || it->first != needle) { + it = table_.insert(it, {needle, ValueT{}}); + } + return it->second; + } + + auto find(const KeyT &needle) { + auto it = std::lower_bound(table_.begin(), table_.end(), needle, + [](const auto &l, const auto &r) { return l.first < r; }); + if (it != table_.end() && it->first == needle) { + return it; + } + return table_.end(); + } + + private: + using KeyValue = value_type; + td::vector<KeyValue> table_; +}; + +template <class KeyT, class ValueT, class HashT = td::Hash<KeyT>> +class SimpleHashTable { + public: + using key_type = KeyT; + using value_type = std::pair<KeyT, ValueT>; + template <class It> + SimpleHashTable(It begin, It end) { + nodes_.resize((end - begin) * 2); + for (; begin != end; ++begin) { + insert(begin->first, begin->second); + } + } + + ValueT &operator[](const KeyT &needle) { + UNREACHABLE(); + } + + ValueT *find(const KeyT &needle) { + auto hash = HashT()(needle); + std::size_t i = hash % nodes_.size(); + while (true) { + if (nodes_[i].key == needle) { + return &nodes_[i].value; + } + if (nodes_[i].hash == 0) { + return nullptr; + } + i++; + if (i == nodes_.size()) { + i = 0; + } + } + } + + private: + using KeyValue = value_type; + struct Node { + std::size_t hash{0}; + KeyT key; + ValueT value; + }; + td::vector<Node> nodes_; + + void insert(KeyT key, ValueT value) { + auto hash = HashT()(key); + std::size_t i = hash % nodes_.size(); + while (true) { + if (nodes_[i].hash == 0 || (nodes_[i].hash == hash && nodes_[i].key == key)) { + nodes_[i].value = value; + nodes_[i].key = key; + nodes_[i].hash = hash; + return; + } + i++; + if (i == nodes_.size()) { + i = 0; + } + } + } +}; + +template <typename TableT> +static void BM_Get(benchmark::State &state) { + std::size_t n = state.range(0); + constexpr std::size_t BATCH_SIZE = 1024; + td::Random::Xorshift128plus rnd(123); + using Key = typename TableT::key_type; + using Value = typename TableT::value_type::second_type; + using KeyValue = std::pair<Key, Value>; + td::vector<KeyValue> data; + td::vector<Key> keys; + + TableT table; + for (std::size_t i = 0; i < n; i++) { + auto key = rnd(); + auto value = rnd(); + data.emplace_back(key, value); + table.emplace(key, value); + keys.push_back(key); + } + + std::size_t key_i = 0; + td::random_shuffle(td::as_mutable_span(keys), rnd); + auto next_key = [&] { + key_i++; + if (key_i == data.size()) { + key_i = 0; + } + return keys[key_i]; + }; + + while (state.KeepRunningBatch(BATCH_SIZE)) { + for (std::size_t i = 0; i < BATCH_SIZE; i++) { + benchmark::DoNotOptimize(table.find(next_key())); + } + } +} + +template <typename TableT> +static void BM_find_same(benchmark::State &state) { + td::Random::Xorshift128plus rnd(123); + TableT table; + constexpr std::size_t N = 100000; + constexpr std::size_t BATCH_SIZE = 1024; + reserve(table, N); + + for (std::size_t i = 0; i < N; i++) { + table.emplace(rnd(), i); + } + + auto key = td::Random::secure_uint64(); + table[key] = 123; + + while (state.KeepRunningBatch(BATCH_SIZE)) { + for (std::size_t i = 0; i < BATCH_SIZE; i++) { + benchmark::DoNotOptimize(table.find(key)); + } + } +} + +template <typename TableT> +static void BM_emplace_same(benchmark::State &state) { + td::Random::Xorshift128plus rnd(123); + TableT table; + constexpr std::size_t N = 100000; + constexpr std::size_t BATCH_SIZE = 1024; + reserve(table, N); + + for (std::size_t i = 0; i < N; i++) { + table.emplace(rnd(), i); + } + + auto key = 123743; + table[key] = 123; + + while (state.KeepRunningBatch(BATCH_SIZE)) { + for (std::size_t i = 0; i < BATCH_SIZE; i++) { + benchmark::DoNotOptimize(table.emplace(key + (i & 15) * 100, 43784932)); + } + } +} + +template <typename TableT> +static void BM_emplace_string(benchmark::State &state) { + td::Random::Xorshift128plus rnd(123); + TableT table; + constexpr std::size_t N = 100000; + constexpr std::size_t BATCH_SIZE = 1024; + reserve(table, N); + + for (std::size_t i = 0; i < N; i++) { + table.emplace(td::to_string(rnd()), i); + } + + table["0"] = 123; + td::vector<td::string> strings; + for (std::size_t i = 0; i < 16; i++) { + strings.emplace_back(1, static_cast<char>('0' + i)); + } + + while (state.KeepRunningBatch(BATCH_SIZE)) { + for (std::size_t i = 0; i < BATCH_SIZE; i++) { + benchmark::DoNotOptimize(table.emplace(strings[i & 15], 43784932)); + } + } +} + +namespace td { +template <class K, class V, class FunctT> +static void table_remove_if(absl::flat_hash_map<K, V> &table, FunctT &&func) { + for (auto it = table.begin(); it != table.end();) { + if (func(*it)) { + auto copy = it; + ++it; + table.erase(copy); + } else { + ++it; + } + } +} +} // namespace td + +template <typename TableT> +static void BM_remove_if(benchmark::State &state) { + constexpr std::size_t N = 100000; + constexpr std::size_t BATCH_SIZE = N; + + TableT table; + reserve(table, N); + while (state.KeepRunningBatch(BATCH_SIZE)) { + state.PauseTiming(); + td::Random::Xorshift128plus rnd(123); + for (std::size_t i = 0; i < N; i++) { + table.emplace(rnd(), i); + } + state.ResumeTiming(); + + td::table_remove_if(table, [](auto &it) { return it.second % 2 == 0; }); + } +} + +template <typename TableT> +static void BM_erase_all_with_begin(benchmark::State &state) { + constexpr std::size_t N = 100000; + constexpr std::size_t BATCH_SIZE = N; + + TableT table; + td::Random::Xorshift128plus rnd(123); + while (state.KeepRunningBatch(BATCH_SIZE)) { + for (std::size_t i = 0; i < BATCH_SIZE; i++) { + table.emplace(rnd() + 1, i); + } + while (!table.empty()) { + table.erase(table.begin()); + } + } +} + +template <typename TableT> +static void BM_cache(benchmark::State &state) { + constexpr std::size_t N = 1000; + constexpr std::size_t BATCH_SIZE = 1000000; + + TableT table; + td::Random::Xorshift128plus rnd(123); + td::VectorQueue<td::uint64> keys; + while (state.KeepRunningBatch(BATCH_SIZE)) { + for (std::size_t i = 0; i < BATCH_SIZE; i++) { + auto key = rnd() + 1; + keys.push(key); + table.emplace(key, i); + if (table.size() > N) { + table.erase(keys.pop()); + } + } + } +} + +template <typename TableT> +static void BM_cache2(benchmark::State &state) { + constexpr std::size_t N = 1000; + constexpr std::size_t BATCH_SIZE = 1000000; + + TableT table; + td::Random::Xorshift128plus rnd(123); + td::VectorQueue<td::uint64> keys; + while (state.KeepRunningBatch(BATCH_SIZE)) { + for (std::size_t i = 0; i < BATCH_SIZE; i++) { + auto key = rnd() + 1; + keys.push(key); + table.emplace(key, i); + if (table.size() > N) { + table.erase(keys.pop_rand(rnd)); + } + } + } +} + +template <typename TableT> +static void BM_cache3(benchmark::State &state) { + std::size_t N = state.range(0); + constexpr std::size_t BATCH_SIZE = 1000000; + + TableT table; + td::Random::Xorshift128plus rnd(123); + td::VectorQueue<td::uint64> keys; + std::size_t step = 20; + while (state.KeepRunningBatch(BATCH_SIZE)) { + for (std::size_t i = 0; i < BATCH_SIZE; i += step) { + auto key = rnd() + 1; + keys.push(key); + table.emplace(key, i); + + for (std::size_t j = 1; j < step; j++) { + auto key_to_find = keys.data()[rnd() % keys.size()]; + benchmark::DoNotOptimize(table.find(key_to_find)); + } + + if (table.size() > N) { + table.erase(keys.pop_rand(rnd)); + } + } + } +} + +template <typename TableT> +static void BM_remove_if_slow(benchmark::State &state) { + constexpr std::size_t N = 5000; + constexpr std::size_t BATCH_SIZE = 500000; + + TableT table; + td::Random::Xorshift128plus rnd(123); + for (std::size_t i = 0; i < N; i++) { + table.emplace(rnd() + 1, i); + } + auto first_key = table.begin()->first; + { + std::size_t cnt = 0; + td::table_remove_if(table, [&cnt, n = N](auto &) { + cnt += 2; + return cnt <= n; + }); + } + while (state.KeepRunningBatch(BATCH_SIZE)) { + for (std::size_t i = 0; i < BATCH_SIZE; i++) { + table.emplace(first_key, i); + table.erase(first_key); + } + } +} + +template <typename TableT> +static void BM_remove_if_slow_old(benchmark::State &state) { + constexpr std::size_t N = 100000; + constexpr std::size_t BATCH_SIZE = 5000000; + + TableT table; + while (state.KeepRunningBatch(BATCH_SIZE)) { + td::Random::Xorshift128plus rnd(123); + for (std::size_t i = 0; i < BATCH_SIZE; i++) { + table.emplace(rnd() + 1, i); + if (table.size() > N) { + std::size_t cnt = 0; + td::table_remove_if(table, [&cnt, n = N](auto &) { + cnt += 2; + return cnt <= n; + }); + } + } + } +} + +template <typename TableT> +static void benchmark_create(td::Slice name) { + td::Random::Xorshift128plus rnd(123); + { + constexpr std::size_t N = 10000000; + TableT table; + reserve(table, N); + auto start = td::Timestamp::now(); + for (std::size_t i = 0; i < N; i++) { + table.emplace(rnd(), i); + } + auto end = td::Timestamp::now(); + LOG(INFO) << name << ": create " << N << " elements: " << td::format::as_time(end.at() - start.at()); + + double res = 0; + td::vector<std::pair<std::size_t, td::format::Time>> pauses; + for (std::size_t i = 0; i < N; i++) { + auto emplace_start = td::Timestamp::now(); + table.emplace(rnd(), i); + auto emplace_end = td::Timestamp::now(); + auto pause = emplace_end.at() - emplace_start.at(); + res = td::max(pause, res); + if (pause > 0.001) { + pauses.emplace_back(i, td::format::as_time(pause)); + } + } + + LOG(INFO) << name << ": create another " << N << " elements, max pause = " << td::format::as_time(res) << " " + << pauses; + } +} + +struct CacheMissNode { + td::uint32 data{}; + char padding[64 - sizeof(data)]; +}; + +class IterateFast { + public: + static td::uint32 iterate(CacheMissNode *ptr, std::size_t max_shift) { + td::uint32 res = 1; + for (std::size_t i = 0; i < max_shift; i++) { + if (ptr[i].data % max_shift != 0) { + res *= ptr[i].data; + } else { + res /= ptr[i].data; + } + } + return res; + } +}; + +class IterateSlow { + public: + static td::uint32 iterate(CacheMissNode *ptr, std::size_t max_shift) { + td::uint32 res = 1; + for (std::size_t i = 0;; i++) { + if (ptr[i].data % max_shift != 0) { + res *= ptr[i].data; + } else { + break; + } + } + return res; + } +}; + +template <class F> +static void BM_cache_miss(benchmark::State &state) { + td::uint32 max_shift = state.range(0); + bool flag = state.range(1); + std::random_device rd; + std::mt19937 rnd(rd()); + int N = 50000000; + td::vector<CacheMissNode> nodes(N); + td::uint32 i = 0; + for (auto &node : nodes) { + if (flag) { + node.data = i++ % max_shift; + } else { + node.data = rnd(); + } + } + + td::vector<int> positions(N); + std::uniform_int_distribution<td::uint32> rnd_pos(0, N - 1000); + for (auto &pos : positions) { + pos = rnd_pos(rnd); + if (flag) { + pos = pos / max_shift * max_shift + 1; + } + } + + while (state.KeepRunningBatch(positions.size())) { + for (const auto pos : positions) { + auto *ptr = &nodes[pos]; + auto res = F::iterate(ptr, max_shift); + benchmark::DoNotOptimize(res); + } + } +} + +static td::uint64 equal_mask_slow(td::uint8 *bytes, td::uint8 needle) { + td::uint64 mask = 0; + for (int i = 0; i < 16; i++) { + mask |= (bytes[i] == needle) << i; + } + return mask; +} + +template <class MaskT> +static void BM_mask(benchmark::State &state) { + std::size_t BATCH_SIZE = 1024; + td::vector<td::uint8> bytes(BATCH_SIZE + 16); + for (auto &b : bytes) { + b = static_cast<td::uint8>(td::Random::fast(0, 17)); + } + + while (state.KeepRunningBatch(BATCH_SIZE)) { + for (std::size_t i = 0; i < BATCH_SIZE; i++) { + benchmark::DoNotOptimize(MaskT::equal_mask(bytes.data() + i, 17)); + } + } +} + +BENCHMARK_TEMPLATE(BM_mask, td::MaskPortable); +#ifdef __aarch64__ +BENCHMARK_TEMPLATE(BM_mask, td::MaskNeonFolly); +BENCHMARK_TEMPLATE(BM_mask, td::MaskNeon); +#endif +#if TD_SSE2 +BENCHMARK_TEMPLATE(BM_mask, td::MaskSse2); +#endif + +template <class KeyT, class ValueT, class HashT = td::Hash<KeyT>, class EqT = std::equal_to<KeyT>> +using FlatHashMapImpl = td::FlatHashTable<td::MapNode<KeyT, ValueT>, HashT, EqT>; + +#define FOR_EACH_TABLE(F) \ + F(FlatHashMapImpl) \ + F(td::FlatHashMapChunks) \ + F(folly::F14FastMap) \ + F(absl::flat_hash_map) \ + F(std::unordered_map) \ + F(std::map) + +//BENCHMARK(BM_cache_miss<IterateSlow>)->Ranges({{1, 16}, {0, 1}}); +//BENCHMARK(BM_cache_miss<IterateFast>)->Ranges({{1, 16}, {0, 1}}); +//BENCHMARK_TEMPLATE(BM_Get, VectorTable<td::uint64, td::uint64>)->Range(1, 1 << 26); +//BENCHMARK_TEMPLATE(BM_Get, SortedVectorTable<td::uint64, td::uint64>)->Range(1, 1 << 26); +//BENCHMARK_TEMPLATE(BM_Get, NoOpTable<td::uint64, td::uint64>)->Range(1, 1 << 26); + +#define REGISTER_GET_BENCHMARK(HT) BENCHMARK_TEMPLATE(BM_Get, HT<td::uint64, td::uint64>)->Range(1, 1 << 23); + +#define REGISTER_FIND_BENCHMARK(HT) \ + BENCHMARK_TEMPLATE(BM_find_same, HT<td::uint64, td::uint64>) \ + ->ComputeStatistics("max", [](const td::vector<double> &v) { return *std::max_element(v.begin(), v.end()); }) \ + ->ComputeStatistics("min", [](const td::vector<double> &v) { return *std::min_element(v.begin(), v.end()); }) \ + ->Repetitions(20) \ + ->DisplayAggregatesOnly(true); + +#define REGISTER_REMOVE_IF_BENCHMARK(HT) BENCHMARK_TEMPLATE(BM_remove_if, HT<td::uint64, td::uint64>); +#define REGISTER_EMPLACE_BENCHMARK(HT) BENCHMARK_TEMPLATE(BM_emplace_same, HT<td::uint64, td::uint64>); +#define REGISTER_EMPLACE_STRING_BENCHMARK(HT) BENCHMARK_TEMPLATE(BM_emplace_string, HT<td::string, td::uint64>); +#define REGISTER_CACHE_BENCHMARK(HT) BENCHMARK_TEMPLATE(BM_cache, HT<td::uint64, td::uint64>); +#define REGISTER_CACHE2_BENCHMARK(HT) BENCHMARK_TEMPLATE(BM_cache2, HT<td::uint64, td::uint64>); +#define REGISTER_CACHE3_BENCHMARK(HT) BENCHMARK_TEMPLATE(BM_cache3, HT<td::uint64, td::uint64>)->Range(1, 1 << 23); +#define REGISTER_ERASE_ALL_BENCHMARK(HT) BENCHMARK_TEMPLATE(BM_erase_all_with_begin, HT<td::uint64, td::uint64>); +#define REGISTER_REMOVE_IF_SLOW_BENCHMARK(HT) BENCHMARK_TEMPLATE(BM_remove_if_slow, HT<td::uint64, td::uint64>); +#define REGISTER_REMOVE_IF_SLOW_OLD_BENCHMARK(HT) BENCHMARK_TEMPLATE(BM_remove_if_slow_old, HT<td::uint64, td::uint64>); + +FOR_EACH_TABLE(REGISTER_GET_BENCHMARK) +FOR_EACH_TABLE(REGISTER_CACHE3_BENCHMARK) +FOR_EACH_TABLE(REGISTER_CACHE2_BENCHMARK) +FOR_EACH_TABLE(REGISTER_CACHE_BENCHMARK) +FOR_EACH_TABLE(REGISTER_REMOVE_IF_BENCHMARK) +FOR_EACH_TABLE(REGISTER_EMPLACE_BENCHMARK) +FOR_EACH_TABLE(REGISTER_EMPLACE_STRING_BENCHMARK) +FOR_EACH_TABLE(REGISTER_ERASE_ALL_BENCHMARK) +FOR_EACH_TABLE(REGISTER_FIND_BENCHMARK) +FOR_EACH_TABLE(REGISTER_REMOVE_IF_SLOW_OLD_BENCHMARK) +FOR_EACH_TABLE(REGISTER_REMOVE_IF_SLOW_BENCHMARK) + +#define RUN_CREATE_BENCHMARK(HT) benchmark_create<HT<td::uint64, td::uint64>>(#HT); + +int main(int argc, char **argv) { + // FOR_EACH_TABLE(RUN_CREATE_BENCHMARK); + + benchmark::Initialize(&argc, argv); + benchmark::RunSpecifiedBenchmarks(); + benchmark::Shutdown(); +} diff --git a/protocols/Telegram/tdlib/td/tdutils/test/heap.cpp b/protocols/Telegram/tdlib/td/tdutils/test/heap.cpp index 0dcfcf98ff..02b6d81424 100644 --- a/protocols/Telegram/tdlib/td/tdutils/test/heap.cpp +++ b/protocols/Telegram/tdlib/td/tdutils/test/heap.cpp @@ -1,5 +1,5 @@ // -// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2018 +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) @@ -8,29 +8,24 @@ #include "td/utils/common.h" #include "td/utils/Heap.h" -#include "td/utils/logging.h" #include "td/utils/Random.h" +#include "td/utils/Span.h" -#include <algorithm> #include <cstdio> -#include <cstdlib> #include <set> #include <utility> -REGISTER_TESTS(heap) - -using namespace td; - TEST(Heap, sort_random_perm) { int n = 1000000; - std::vector<int> v(n); + + td::vector<int> v(n); for (int i = 0; i < n; i++) { v[i] = i; } - std::srand(123); - std::random_shuffle(v.begin(), v.end()); - std::vector<HeapNode> nodes(n); - KHeap<int> kheap; + td::Random::Xorshift128plus rnd(123); + td::random_shuffle(td::as_mutable_span(v), rnd); + td::vector<td::HeapNode> nodes(n); + td::KHeap<int> kheap; for (int i = 0; i < n; i++) { kheap.insert(v[i], &nodes[i]); } @@ -38,7 +33,7 @@ TEST(Heap, sort_random_perm) { ASSERT_EQ(i, kheap.top_key()); kheap.pop(); } -}; +} class CheckedHeap { public: @@ -51,7 +46,7 @@ class CheckedHeap { nodes[i].value = i; } } - static void xx(int key, const HeapNode *heap_node) { + static void xx(int key, const td::HeapNode *heap_node) { const Node *node = static_cast<const Node *>(heap_node); std::fprintf(stderr, "(%d;%d)", node->key, node->value); } @@ -66,9 +61,9 @@ class CheckedHeap { } int random_id() const { CHECK(!empty()); - return ids[Random::fast(0, static_cast<int>(ids.size() - 1))]; + return ids[td::Random::fast(0, static_cast<int>(ids.size() - 1))]; } - size_t size() const { + std::size_t size() const { return ids.size(); } bool empty() const { @@ -140,19 +135,19 @@ class CheckedHeap { } private: - struct Node : public HeapNode { + struct Node final : public td::HeapNode { Node() = default; Node(int key, int value) : key(key), value(value) { } int key = 0; int value = 0; }; - vector<int> ids; - vector<int> rev_ids; - vector<int> free_ids; - vector<Node> nodes; + td::vector<int> ids; + td::vector<int> rev_ids; + td::vector<int> free_ids; + td::vector<Node> nodes; std::set<std::pair<int, int>> set_heap; - KHeap<int> kheap; + td::KHeap<int> kheap; }; TEST(Heap, random_events) { @@ -163,11 +158,11 @@ TEST(Heap, random_events) { heap.top_key(); } - int x = Random::fast(0, 4); + int x = td::Random::fast(0, 4); if (heap.empty() || (x < 2 && heap.size() < 1000)) { - heap.insert(Random::fast(0, 99)); + heap.insert(td::Random::fast(0, 99)); } else if (x < 3) { - heap.fix_key(Random::fast(0, 99), heap.random_id()); + heap.fix_key(td::Random::fast(0, 99), heap.random_id()); } else if (x < 4) { heap.erase(heap.random_id()); } else if (x < 5) { diff --git a/protocols/Telegram/tdlib/td/tdutils/test/json.cpp b/protocols/Telegram/tdlib/td/tdutils/test/json.cpp index deca81a791..4e57b2d562 100644 --- a/protocols/Telegram/tdlib/td/tdutils/test/json.cpp +++ b/protocols/Telegram/tdlib/td/tdutils/test/json.cpp @@ -1,31 +1,26 @@ // -// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2018 +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // -#include "td/utils/tests.h" - #include "td/utils/JsonBuilder.h" #include "td/utils/logging.h" +#include "td/utils/Slice.h" #include "td/utils/StringBuilder.h" +#include "td/utils/tests.h" -#include <tuple> #include <utility> -REGISTER_TESTS(json) - -using namespace td; - -static void decode_encode(string str, string result = "") { +static void decode_encode(const td::string &str, td::string result = td::string()) { auto str_copy = str; - auto r_value = json_decode(str_copy); + auto r_value = td::json_decode(str_copy); ASSERT_TRUE(r_value.is_ok()); if (r_value.is_error()) { LOG(INFO) << r_value.error(); return; } - auto new_str = json_encode<string>(r_value.ok()); + auto new_str = td::json_encode<td::string>(r_value.ok()); if (result.empty()) { result = str; } @@ -34,21 +29,22 @@ static void decode_encode(string str, string result = "") { TEST(JSON, array) { char tmp[1000]; - StringBuilder sb({tmp, sizeof(tmp)}); - JsonBuilder jb(std::move(sb)); + td::StringBuilder sb(td::MutableSlice{tmp, sizeof(tmp)}); + td::JsonBuilder jb(std::move(sb)); jb.enter_value().enter_array() << "Hello" << -123; ASSERT_EQ(jb.string_builder().is_error(), false); auto encoded = jb.string_builder().as_cslice().str(); ASSERT_EQ("[\"Hello\",-123]", encoded); decode_encode(encoded); } + TEST(JSON, object) { char tmp[1000]; - StringBuilder sb({tmp, sizeof(tmp)}); - JsonBuilder jb(std::move(sb)); + td::StringBuilder sb(td::MutableSlice{tmp, sizeof(tmp)}); + td::JsonBuilder jb(std::move(sb)); auto c = jb.enter_object(); - c << std::tie("key", "value"); - c << std::make_pair("1", 2); + c("key", "value"); + c("1", 2); c.leave(); ASSERT_EQ(jb.string_builder().is_error(), false); auto encoded = jb.string_builder().as_cslice().str(); @@ -58,8 +54,8 @@ TEST(JSON, object) { TEST(JSON, nested) { char tmp[1000]; - StringBuilder sb({tmp, sizeof(tmp)}); - JsonBuilder jb(std::move(sb)); + td::StringBuilder sb(td::MutableSlice{tmp, sizeof(tmp)}); + td::JsonBuilder jb(std::move(sb)); { auto a = jb.enter_array(); a << 1; diff --git a/protocols/Telegram/tdlib/td/tdutils/test/log.cpp b/protocols/Telegram/tdlib/td/tdutils/test/log.cpp new file mode 100644 index 0000000000..34af21353c --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/log.cpp @@ -0,0 +1,187 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/AsyncFileLog.h" +#include "td/utils/benchmark.h" +#include "td/utils/CombinedLog.h" +#include "td/utils/FileLog.h" +#include "td/utils/format.h" +#include "td/utils/logging.h" +#include "td/utils/MemoryLog.h" +#include "td/utils/NullLog.h" +#include "td/utils/port/path.h" +#include "td/utils/port/thread.h" +#include "td/utils/Slice.h" +#include "td/utils/SliceBuilder.h" +#include "td/utils/tests.h" +#include "td/utils/TsFileLog.h" +#include "td/utils/TsLog.h" + +#include <functional> +#include <limits> + +char disable_linker_warning_about_empty_file_tdutils_test_log_cpp TD_UNUSED; + +#if !TD_THREAD_UNSUPPORTED +template <class Log> +class LogBenchmark final : public td::Benchmark { + public: + LogBenchmark(std::string name, int threads_n, bool test_full_logging, std::function<td::unique_ptr<Log>()> creator) + : name_(std::move(name)) + , threads_n_(threads_n) + , test_full_logging_(test_full_logging) + , creator_(std::move(creator)) { + } + std::string get_description() const final { + return PSTRING() << name_ << " " << (test_full_logging_ ? "ERROR" : "PLAIN") << " " + << td::tag("threads_n", threads_n_); + } + void start_up() final { + log_ = creator_(); + threads_.resize(threads_n_); + } + void tear_down() final { + if (log_ == nullptr) { + return; + } + for (const auto &path : log_->get_file_paths()) { + td::unlink(path).ignore(); + } + log_.reset(); + } + void run(int n) final { + auto old_log_interface = td::log_interface; + if (log_ != nullptr) { + td::log_interface = log_.get(); + } + + for (auto &thread : threads_) { + thread = td::thread([this, n] { this->run_thread(n); }); + } + for (auto &thread : threads_) { + thread.join(); + } + + td::log_interface = old_log_interface; + } + + void run_thread(int n) { + auto str = PSTRING() << "#" << n << " : fsjklfdjsklfjdsklfjdksl\n"; + for (int i = 0; i < n; i++) { + if (i % 10000 == 0 && log_ != nullptr) { + log_->after_rotation(); + } + if (test_full_logging_) { + LOG(ERROR) << str; + } else { + LOG(PLAIN) << str; + } + } + } + + private: + std::string name_; + td::unique_ptr<td::LogInterface> log_; + int threads_n_{0}; + bool test_full_logging_{false}; + std::function<td::unique_ptr<Log>()> creator_; + std::vector<td::thread> threads_; +}; + +template <class F> +static void bench_log(std::string name, F &&f) { + for (auto test_full_logging : {false, true}) { + for (auto threads_n : {1, 4, 8}) { + bench(LogBenchmark<typename decltype(f())::element_type>(name, threads_n, test_full_logging, f)); + } + } +} + +TEST(Log, Bench) { + bench_log("NullLog", [] { return td::make_unique<td::NullLog>(); }); + + // bench_log("Default", []() -> td::unique_ptr<td::NullLog> { return nullptr; }); + + bench_log("MemoryLog", [] { return td::make_unique<td::MemoryLog<1 << 20>>(); }); + + bench_log("CombinedLogEmpty", [] { return td::make_unique<td::CombinedLog>(); }); + + bench_log("CombinedLogMemory", [] { + auto result = td::make_unique<td::CombinedLog>(); + static td::NullLog null_log; + static td::MemoryLog<1 << 20> memory_log; + result->set_first(&null_log); + result->set_second(&memory_log); + result->set_first_verbosity_level(VERBOSITY_NAME(DEBUG)); + result->set_second_verbosity_level(VERBOSITY_NAME(DEBUG)); + return result; + }); + + bench_log("TsFileLog", + [] { return td::TsFileLog::create("tmplog", std::numeric_limits<td::int64>::max(), false).move_as_ok(); }); + + bench_log("FileLog + TsLog", [] { + class FileLog final : public td::LogInterface { + public: + FileLog() { + file_log_.init("tmplog", std::numeric_limits<td::int64>::max(), false).ensure(); + ts_log_.init(&file_log_); + } + void do_append(int log_level, td::CSlice slice) final { + static_cast<td::LogInterface &>(ts_log_).do_append(log_level, slice); + } + std::vector<std::string> get_file_paths() final { + return file_log_.get_file_paths(); + } + + private: + td::FileLog file_log_; + td::TsLog ts_log_{nullptr}; + }; + return td::make_unique<FileLog>(); + }); + + bench_log("FileLog", [] { + class FileLog final : public td::LogInterface { + public: + FileLog() { + file_log_.init("tmplog", std::numeric_limits<td::int64>::max(), false).ensure(); + } + void do_append(int log_level, td::CSlice slice) final { + static_cast<td::LogInterface &>(file_log_).do_append(log_level, slice); + } + std::vector<std::string> get_file_paths() final { + return file_log_.get_file_paths(); + } + + private: + td::FileLog file_log_; + }; + return td::make_unique<FileLog>(); + }); + +#if !TD_EVENTFD_UNSUPPORTED + bench_log("AsyncFileLog", [] { + class AsyncFileLog final : public td::LogInterface { + public: + AsyncFileLog() { + file_log_.init("tmplog", std::numeric_limits<td::int64>::max()).ensure(); + } + void do_append(int log_level, td::CSlice slice) final { + static_cast<td::LogInterface &>(file_log_).do_append(log_level, slice); + } + std::vector<std::string> get_file_paths() final { + return static_cast<td::LogInterface &>(file_log_).get_file_paths(); + } + + private: + td::AsyncFileLog file_log_; + }; + return td::make_unique<AsyncFileLog>(); + }); +#endif +} +#endif diff --git a/protocols/Telegram/tdlib/td/tdutils/test/misc.cpp b/protocols/Telegram/tdlib/td/tdutils/test/misc.cpp index dd1f1ec457..7db990dad1 100644 --- a/protocols/Telegram/tdlib/td/tdutils/test/misc.cpp +++ b/protocols/Telegram/tdlib/td/tdutils/test/misc.cpp @@ -1,47 +1,91 @@ // -// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2018 +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // +#include "td/utils/algorithm.h" +#include "td/utils/as.h" #include "td/utils/base64.h" -#include "td/utils/HttpUrl.h" +#include "td/utils/BigNum.h" +#include "td/utils/bits.h" +#include "td/utils/CancellationToken.h" +#include "td/utils/common.h" +#include "td/utils/ExitGuard.h" +#include "td/utils/FloodControlFast.h" +#include "td/utils/Hash.h" +#include "td/utils/HashMap.h" +#include "td/utils/HashSet.h" +#include "td/utils/HashTableUtils.h" +#include "td/utils/invoke.h" #include "td/utils/logging.h" #include "td/utils/misc.h" #include "td/utils/port/EventFd.h" #include "td/utils/port/FileFd.h" +#include "td/utils/port/IPAddress.h" #include "td/utils/port/path.h" #include "td/utils/port/sleep.h" #include "td/utils/port/Stat.h" #include "td/utils/port/thread.h" +#include "td/utils/port/uname.h" +#include "td/utils/port/wstring_convert.h" #include "td/utils/Random.h" #include "td/utils/Slice.h" +#include "td/utils/SliceBuilder.h" +#include "td/utils/Status.h" #include "td/utils/StringBuilder.h" #include "td/utils/tests.h" +#include "td/utils/Time.h" +#include "td/utils/tl_helpers.h" +#include "td/utils/translit.h" +#include "td/utils/uint128.h" +#include "td/utils/unicode.h" +#include "td/utils/utf8.h" +#include <algorithm> #include <atomic> -#include <clocale> #include <limits> #include <locale> +#include <unordered_map> +#include <utility> -using namespace td; +#if TD_HAVE_ABSL +#include <absl/container/flat_hash_map.h> +#include <absl/hash/hash.h> +#endif + +struct CheckExitGuard { + explicit CheckExitGuard(bool expected_value) : expected_value_(expected_value) { + } + CheckExitGuard(CheckExitGuard &&) = delete; + CheckExitGuard &operator=(CheckExitGuard &&) = delete; + CheckExitGuard(const CheckExitGuard &) = delete; + CheckExitGuard &operator=(const CheckExitGuard &) = delete; + ~CheckExitGuard() { + ASSERT_EQ(expected_value_, td::ExitGuard::is_exited()); + } + + bool expected_value_; +}; + +static CheckExitGuard check_exit_guard_true{true}; +static td::ExitGuard exit_guard; #if TD_LINUX || TD_DARWIN TEST(Misc, update_atime_saves_mtime) { - SET_VERBOSITY_LEVEL(VERBOSITY_NAME(ERROR)); - std::string name = "test_file"; - unlink(name).ignore(); - auto r_file = FileFd::open(name, FileFd::Read | FileFd::Flags::Create | FileFd::Flags::Truncate); + td::string name = "test_file"; + td::unlink(name).ignore(); + auto r_file = td::FileFd::open(name, td::FileFd::Read | td::FileFd::Flags::Create | td::FileFd::Flags::Truncate); LOG_IF(ERROR, r_file.is_error()) << r_file.error(); ASSERT_TRUE(r_file.is_ok()); r_file.move_as_ok().close(); - auto info = stat(name).ok(); - int32 tests_ok = 0; - int32 tests_wa = 0; + auto info = td::stat(name).ok(); + td::int32 tests_ok = 0; + td::int32 tests_wa = 0; for (int i = 0; i < 10000; i++) { - update_atime(name).ensure(); - auto new_info = stat(name).ok(); + td::update_atime(name).ensure(); + auto new_info = td::stat(name).ok(); if (info.mtime_nsec_ == new_info.mtime_nsec_) { tests_ok++; } else { @@ -49,31 +93,30 @@ TEST(Misc, update_atime_saves_mtime) { info.mtime_nsec_ = new_info.mtime_nsec_; } ASSERT_EQ(info.mtime_nsec_, new_info.mtime_nsec_); - usleep_for(Random::fast(0, 1000)); + td::usleep_for(td::Random::fast(0, 1000)); } if (tests_wa > 0) { LOG(ERROR) << "Access time was unexpectedly updated " << tests_wa << " times"; } - unlink(name).ensure(); + td::unlink(name).ensure(); } TEST(Misc, update_atime_change_atime) { - SET_VERBOSITY_LEVEL(VERBOSITY_NAME(ERROR)); - std::string name = "test_file"; - unlink(name).ignore(); - auto r_file = FileFd::open(name, FileFd::Read | FileFd::Flags::Create | FileFd::Flags::Truncate); + td::string name = "test_file"; + td::unlink(name).ignore(); + auto r_file = td::FileFd::open(name, td::FileFd::Read | td::FileFd::Flags::Create | td::FileFd::Flags::Truncate); LOG_IF(ERROR, r_file.is_error()) << r_file.error(); ASSERT_TRUE(r_file.is_ok()); r_file.move_as_ok().close(); - auto info = stat(name).ok(); + auto info = td::stat(name).ok(); // not enough for fat and e.t.c. - usleep_for(5000000); - update_atime(name).ensure(); - auto new_info = stat(name).ok(); + td::usleep_for(5000000); + td::update_atime(name).ensure(); + auto new_info = td::stat(name).ok(); if (info.atime_nsec_ == new_info.atime_nsec_) { LOG(ERROR) << "Access time was unexpectedly not changed"; } - unlink(name).ensure(); + td::unlink(name).ensure(); } #endif @@ -84,9 +127,9 @@ TEST(Misc, errno_tls_bug) { // CHECK(errno == 0); #if !TD_THREAD_UNSUPPORTED && !TD_EVENTFD_UNSUPPORTED - EventFd test_event_fd; + td::EventFd test_event_fd; test_event_fd.init(); - std::atomic<int> s(0); + std::atomic<int> s{0}; s = 1; td::thread th([&] { while (s != 1) { @@ -96,21 +139,21 @@ TEST(Misc, errno_tls_bug) { th.join(); for (int i = 0; i < 1000; i++) { - vector<EventFd> events(10); - vector<td::thread> threads; + td::vector<td::EventFd> events(10); + td::vector<td::thread> threads; for (auto &event : events) { event.init(); event.release(); } for (auto &event : events) { - threads.push_back(td::thread([&] { + threads.emplace_back([&] { { - EventFd tmp; + td::EventFd tmp; tmp.init(); tmp.acquire(); } event.acquire(); - })); + }); } for (auto &thread : threads) { thread.join(); @@ -119,81 +162,281 @@ TEST(Misc, errno_tls_bug) { #endif } +TEST(Misc, get_last_argument) { + auto a = td::make_unique<int>(5); + ASSERT_EQ(*td::get_last_argument(std::move(a)), 5); + ASSERT_EQ(*td::get_last_argument(1, 2, 3, 4, a), 5); + ASSERT_EQ(*td::get_last_argument(a), 5); + auto b = td::get_last_argument(1, 2, 3, std::move(a)); + ASSERT_TRUE(!a); + ASSERT_EQ(*b, 5); +} + +TEST(Misc, call_n_arguments) { + auto f = [](int, int) { + }; + td::call_n_arguments<2>(f, 1, 3, 4); +} + TEST(Misc, base64) { - ASSERT_TRUE(is_base64("dGVzdA==") == true); - ASSERT_TRUE(is_base64("dGVzdB==") == false); - ASSERT_TRUE(is_base64("dGVzdA=") == false); - ASSERT_TRUE(is_base64("dGVzdA") == false); - ASSERT_TRUE(is_base64("dGVz") == true); - ASSERT_TRUE(is_base64("") == true); - ASSERT_TRUE(is_base64("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/") == true); - ASSERT_TRUE(is_base64("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=") == false); - ASSERT_TRUE(is_base64("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-/") == false); - ASSERT_TRUE(is_base64("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_") == false); - ASSERT_TRUE(is_base64("====") == false); - - ASSERT_TRUE(is_base64url("dGVzdA==") == true); - ASSERT_TRUE(is_base64url("dGVzdB==") == false); - ASSERT_TRUE(is_base64url("dGVzdA=") == false); - ASSERT_TRUE(is_base64url("dGVzdA") == true); - ASSERT_TRUE(is_base64url("dGVz") == true); - ASSERT_TRUE(is_base64url("") == true); - ASSERT_TRUE(is_base64url("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_") == true); - ASSERT_TRUE(is_base64url("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_=") == false); - ASSERT_TRUE(is_base64url("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-/") == false); - ASSERT_TRUE(is_base64url("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/") == false); - ASSERT_TRUE(is_base64url("====") == false); + ASSERT_TRUE(td::is_base64("dGVzdA==") == true); + ASSERT_TRUE(td::is_base64("dGVzdB==") == false); + ASSERT_TRUE(td::is_base64("dGVzdA=") == false); + ASSERT_TRUE(td::is_base64("dGVzdA") == false); + ASSERT_TRUE(td::is_base64("dGVzd") == false); + ASSERT_TRUE(td::is_base64("dGVz") == true); + ASSERT_TRUE(td::is_base64("dGVz====") == false); + ASSERT_TRUE(td::is_base64("") == true); + ASSERT_TRUE(td::is_base64("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/") == true); + ASSERT_TRUE(td::is_base64("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=") == false); + ASSERT_TRUE(td::is_base64("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-/") == false); + ASSERT_TRUE(td::is_base64("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_") == false); + ASSERT_TRUE(td::is_base64("====") == false); + + ASSERT_TRUE(td::is_base64url("dGVzdA==") == true); + ASSERT_TRUE(td::is_base64url("dGVzdB==") == false); + ASSERT_TRUE(td::is_base64url("dGVzdA=") == false); + ASSERT_TRUE(td::is_base64url("dGVzdA") == true); + ASSERT_TRUE(td::is_base64url("dGVzd") == false); + ASSERT_TRUE(td::is_base64url("dGVz") == true); + ASSERT_TRUE(td::is_base64url("dGVz====") == false); + ASSERT_TRUE(td::is_base64url("") == true); + ASSERT_TRUE(td::is_base64url("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_") == true); + ASSERT_TRUE(td::is_base64url("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_=") == false); + ASSERT_TRUE(td::is_base64url("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-/") == false); + ASSERT_TRUE(td::is_base64url("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/") == false); + ASSERT_TRUE(td::is_base64url("====") == false); + + ASSERT_TRUE(td::is_base64_characters("dGVzdA==") == false); + ASSERT_TRUE(td::is_base64_characters("dGVzdB==") == false); + ASSERT_TRUE(td::is_base64_characters("dGVzdA=") == false); + ASSERT_TRUE(td::is_base64_characters("dGVzdA") == true); + ASSERT_TRUE(td::is_base64_characters("dGVz") == true); + ASSERT_TRUE(td::is_base64_characters("") == true); + ASSERT_TRUE(td::is_base64_characters("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/") == true); + ASSERT_TRUE(td::is_base64_characters("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=") == false); + ASSERT_TRUE(td::is_base64_characters("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-/") == false); + ASSERT_TRUE(td::is_base64_characters("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_") == false); + ASSERT_TRUE(td::is_base64_characters("====") == false); + + ASSERT_TRUE(td::is_base64url_characters("dGVzdA==") == false); + ASSERT_TRUE(td::is_base64url_characters("dGVzdB==") == false); + ASSERT_TRUE(td::is_base64url_characters("dGVzdA=") == false); + ASSERT_TRUE(td::is_base64url_characters("dGVzdA") == true); + ASSERT_TRUE(td::is_base64url_characters("dGVz") == true); + ASSERT_TRUE(td::is_base64url_characters("") == true); + ASSERT_TRUE(td::is_base64url_characters("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_") == true); + ASSERT_TRUE(td::is_base64url_characters("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_=") == + false); + ASSERT_TRUE(td::is_base64url_characters("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-/") == false); + ASSERT_TRUE(td::is_base64url_characters("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/") == false); + ASSERT_TRUE(td::is_base64url_characters("====") == false); for (int l = 0; l < 300000; l += l / 20 + l / 1000 * 500 + 1) { for (int t = 0; t < 10; t++) { - string s = rand_string(std::numeric_limits<char>::min(), std::numeric_limits<char>::max(), l); - string encoded = base64url_encode(s); - auto decoded = base64url_decode(encoded); + auto s = td::rand_string(std::numeric_limits<char>::min(), std::numeric_limits<char>::max(), l); + auto encoded = td::base64url_encode(s); + auto decoded = td::base64url_decode(encoded); ASSERT_TRUE(decoded.is_ok()); ASSERT_TRUE(decoded.ok() == s); - encoded = base64_encode(s); - decoded = base64_decode(encoded); + encoded = td::base64_encode(s); + decoded = td::base64_decode(encoded); ASSERT_TRUE(decoded.is_ok()); ASSERT_TRUE(decoded.ok() == s); + + auto decoded_secure = td::base64_decode_secure(encoded); + ASSERT_TRUE(decoded_secure.is_ok()); + ASSERT_TRUE(decoded_secure.ok().as_slice() == s); } } - ASSERT_TRUE(base64url_decode("dGVzdA").is_ok()); - ASSERT_TRUE(base64url_decode("dGVzdB").is_error()); - ASSERT_TRUE(base64_encode(base64url_decode("dGVzdA").ok()) == "dGVzdA=="); - ASSERT_TRUE(base64_encode("any carnal pleas") == "YW55IGNhcm5hbCBwbGVhcw=="); - ASSERT_TRUE(base64_encode("any carnal pleasu") == "YW55IGNhcm5hbCBwbGVhc3U="); - ASSERT_TRUE(base64_encode("any carnal pleasur") == "YW55IGNhcm5hbCBwbGVhc3Vy"); - ASSERT_TRUE(base64_encode(" /'.;.';≤.];,].',[.;/,.;/]/..;!@#!*(%?::;!%\";") == - "ICAgICAgLycuOy4nO+KJpC5dOyxdLicsWy47LywuOy9dLy4uOyFAIyEqKCU/" - "Ojo7ISUiOw=="); + ASSERT_TRUE(td::base64url_decode("dGVzdA").is_ok()); + ASSERT_TRUE(td::base64url_decode("dGVzdB").is_error()); + ASSERT_TRUE(td::base64_encode(td::base64url_decode("dGVzdA").ok()) == "dGVzdA=="); + ASSERT_TRUE(td::base64_encode("any carnal pleas") == "YW55IGNhcm5hbCBwbGVhcw=="); + ASSERT_TRUE(td::base64_encode("any carnal pleasu") == "YW55IGNhcm5hbCBwbGVhc3U="); + ASSERT_TRUE(td::base64_encode("any carnal pleasur") == "YW55IGNhcm5hbCBwbGVhc3Vy"); + ASSERT_TRUE(td::base64_encode(" /'.;.';≤.];,].',[.;/,.;/]/..;!@#!*(%?::;!%\";") == + "ICAgICAgLycuOy4nO+KJpC5dOyxdLicsWy47LywuOy9dLy4uOyFAIyEqKCU/Ojo7ISUiOw=="); + ASSERT_TRUE(td::base64url_encode("ab><") == "YWI-PA"); + ASSERT_TRUE(td::base64url_encode("ab><c") == "YWI-PGM"); + ASSERT_TRUE(td::base64url_encode("ab><cd") == "YWI-PGNk"); +} + +template <class T> +static void test_remove_if(td::vector<int> v, const T &func, const td::vector<int> &expected) { + td::remove_if(v, func); + if (expected != v) { + LOG(FATAL) << "Receive " << v << ", expected " << expected << " in remove_if"; + } +} + +TEST(Misc, remove_if) { + auto odd = [](int x) { + return x % 2 == 1; + }; + auto even = [](int x) { + return x % 2 == 0; + }; + auto all = [](int x) { + return true; + }; + auto none = [](int x) { + return false; + }; + + td::vector<int> v{1, 2, 3, 4, 5, 6}; + test_remove_if(v, odd, {2, 4, 6}); + test_remove_if(v, even, {1, 3, 5}); + test_remove_if(v, all, {}); + test_remove_if(v, none, v); + + v = td::vector<int>{1, 3, 5, 2, 4, 6}; + test_remove_if(v, odd, {2, 4, 6}); + test_remove_if(v, even, {1, 3, 5}); + test_remove_if(v, all, {}); + test_remove_if(v, none, v); + + v.clear(); + test_remove_if(v, odd, v); + test_remove_if(v, even, v); + test_remove_if(v, all, v); + test_remove_if(v, none, v); + + v.push_back(-1); + test_remove_if(v, odd, v); + test_remove_if(v, even, v); + test_remove_if(v, all, {}); + test_remove_if(v, none, v); + + v[0] = 1; + test_remove_if(v, odd, {}); + test_remove_if(v, even, v); + test_remove_if(v, all, {}); + test_remove_if(v, none, v); + + v[0] = 2; + test_remove_if(v, odd, v); + test_remove_if(v, even, {}); + test_remove_if(v, all, {}); + test_remove_if(v, none, v); +} + +static void test_remove(td::vector<int> v, int value, const td::vector<int> &expected) { + bool is_found = expected != v; + ASSERT_EQ(is_found, td::remove(v, value)); + if (expected != v) { + LOG(FATAL) << "Receive " << v << ", expected " << expected << " in remove"; + } +} + +TEST(Misc, remove) { + td::vector<int> v{1, 2, 3, 4, 5, 6}; + test_remove(v, 0, {1, 2, 3, 4, 5, 6}); + test_remove(v, 1, {2, 3, 4, 5, 6}); + test_remove(v, 2, {1, 3, 4, 5, 6}); + test_remove(v, 3, {1, 2, 4, 5, 6}); + test_remove(v, 4, {1, 2, 3, 5, 6}); + test_remove(v, 5, {1, 2, 3, 4, 6}); + test_remove(v, 6, {1, 2, 3, 4, 5}); + test_remove(v, 7, {1, 2, 3, 4, 5, 6}); + + v.clear(); + test_remove(v, -1, v); + test_remove(v, 0, v); + test_remove(v, 1, v); +} + +static void test_unique(td::vector<int> v, const td::vector<int> &expected) { + auto v_str = td::transform(v, &td::to_string<int>); + auto expected_str = td::transform(expected, &td::to_string<int>); + + td::unique(v); + ASSERT_EQ(expected, v); + + td::unique(v_str); + ASSERT_EQ(expected_str, v_str); +} + +TEST(Misc, unique) { + test_unique({1, 2, 3, 4, 5, 6}, {1, 2, 3, 4, 5, 6}); + test_unique({5, 2, 1, 6, 3, 4}, {1, 2, 3, 4, 5, 6}); + test_unique({}, {}); + test_unique({0}, {0}); + test_unique({0, 0}, {0}); + test_unique({0, 1}, {0, 1}); + test_unique({1, 0}, {0, 1}); + test_unique({1, 1}, {1}); + test_unique({1, 1, 0, 0}, {0, 1}); + test_unique({3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 0}, {0, 1, 2, 3}); + test_unique({3, 3, 3, 3, 3}, {3}); + test_unique({3, 3, -1, 3, 3}, {-1, 3}); +} + +TEST(Misc, contains) { + td::vector<int> v{1, 3, 5, 7, 4, 2}; + for (int i = -10; i < 20; i++) { + ASSERT_EQ(td::contains(v, i), (1 <= i && i <= 5) || i == 7); + } + + v.clear(); + ASSERT_TRUE(!td::contains(v, 0)); + ASSERT_TRUE(!td::contains(v, 1)); + + td::string str = "abacaba"; + ASSERT_TRUE(!td::contains(str, '0')); + ASSERT_TRUE(!td::contains(str, 0)); + ASSERT_TRUE(!td::contains(str, 'd')); + ASSERT_TRUE(td::contains(str, 'a')); + ASSERT_TRUE(td::contains(str, 'b')); + ASSERT_TRUE(td::contains(str, 'c')); +} + +TEST(Misc, base32) { + ASSERT_EQ("", td::base32_encode("")); + ASSERT_EQ("me", td::base32_encode("a")); + td::base32_decode("me").ensure(); + ASSERT_EQ("mfra", td::base32_encode("ab")); + ASSERT_EQ("mfrgg", td::base32_encode("abc")); + ASSERT_EQ("mfrggza", td::base32_encode("abcd")); + ASSERT_EQ("mfrggzdg", td::base32_encode("abcdf")); + ASSERT_EQ("mfrggzdgm4", td::base32_encode("abcdfg")); + for (int l = 0; l < 300000; l += l / 20 + l / 1000 * 500 + 1) { + for (int t = 0; t < 10; t++) { + auto s = td::rand_string(std::numeric_limits<char>::min(), std::numeric_limits<char>::max(), l); + auto encoded = td::base32_encode(s); + auto decoded = td::base32_decode(encoded); + ASSERT_TRUE(decoded.is_ok()); + ASSERT_TRUE(decoded.ok() == s); + } + } } TEST(Misc, to_integer) { - ASSERT_EQ(to_integer<int32>("-1234567"), -1234567); - ASSERT_EQ(to_integer<int64>("-1234567"), -1234567); - ASSERT_EQ(to_integer<uint32>("-1234567"), 0u); - ASSERT_EQ(to_integer<int16>("-1234567"), 10617); - ASSERT_EQ(to_integer<uint16>("-1234567"), 0u); - ASSERT_EQ(to_integer<int16>("-1254567"), -9383); - ASSERT_EQ(to_integer<uint16>("1254567"), 9383u); - ASSERT_EQ(to_integer<int64>("-12345678910111213"), -12345678910111213); - ASSERT_EQ(to_integer<uint64>("12345678910111213"), 12345678910111213ull); - - ASSERT_EQ(to_integer_safe<int32>("-1234567").ok(), -1234567); - ASSERT_EQ(to_integer_safe<int64>("-1234567").ok(), -1234567); - ASSERT_TRUE(to_integer_safe<uint32>("-1234567").is_error()); - ASSERT_TRUE(to_integer_safe<int16>("-1234567").is_error()); - ASSERT_TRUE(to_integer_safe<uint16>("-1234567").is_error()); - ASSERT_TRUE(to_integer_safe<int16>("-1254567").is_error()); - ASSERT_TRUE(to_integer_safe<uint16>("1254567").is_error()); - ASSERT_EQ(to_integer_safe<int64>("-12345678910111213").ok(), -12345678910111213); - ASSERT_EQ(to_integer_safe<uint64>("12345678910111213").ok(), 12345678910111213ull); - ASSERT_TRUE(to_integer_safe<uint64>("-12345678910111213").is_error()); -} - -static void test_to_double_one(CSlice str, Slice expected, int precision = 6) { + ASSERT_EQ(td::to_integer<td::int32>("-1234567"), -1234567); + ASSERT_EQ(td::to_integer<td::int64>("-1234567"), -1234567); + ASSERT_EQ(td::to_integer<td::uint32>("-1234567"), 0u); + ASSERT_EQ(td::to_integer<td::int16>("-1234567"), 10617); + ASSERT_EQ(td::to_integer<td::uint16>("-1234567"), 0u); + ASSERT_EQ(td::to_integer<td::int16>("-1254567"), -9383); + ASSERT_EQ(td::to_integer<td::uint16>("1254567"), 9383u); + ASSERT_EQ(td::to_integer<td::int64>("-12345678910111213"), -12345678910111213); + ASSERT_EQ(td::to_integer<td::uint64>("12345678910111213"), 12345678910111213ull); + + ASSERT_EQ(td::to_integer_safe<td::int32>("-1234567").ok(), -1234567); + ASSERT_EQ(td::to_integer_safe<td::int64>("-1234567").ok(), -1234567); + ASSERT_TRUE(td::to_integer_safe<td::uint32>("-1234567").is_error()); + ASSERT_TRUE(td::to_integer_safe<td::int16>("-1234567").is_error()); + ASSERT_TRUE(td::to_integer_safe<td::uint16>("-1234567").is_error()); + ASSERT_TRUE(td::to_integer_safe<td::int16>("-1254567").is_error()); + ASSERT_TRUE(td::to_integer_safe<td::uint16>("1254567").is_error()); + ASSERT_EQ(td::to_integer_safe<td::int64>("-12345678910111213").ok(), -12345678910111213); + ASSERT_EQ(td::to_integer_safe<td::uint64>("12345678910111213").ok(), 12345678910111213ull); + ASSERT_TRUE(td::to_integer_safe<td::uint64>("-12345678910111213").is_error()); +} + +static void test_to_double_one(td::CSlice str, td::Slice expected, int precision = 6) { auto result = PSTRING() << td::StringBuilder::FixedDouble(to_double(str), precision); if (expected != result) { LOG(ERROR) << "To double conversion failed: have " << str << ", expected " << expected << ", parsed " @@ -234,29 +477,786 @@ static void test_to_double() { TEST(Misc, to_double) { test_to_double(); - const char *locale_name = (std::setlocale(LC_ALL, "fr-FR") == nullptr ? "" : "fr-FR"); - std::locale new_locale(locale_name); - std::locale::global(new_locale); + std::locale new_locale("C"); + auto host_locale = std::locale::global(new_locale); + test_to_double(); + new_locale = std::locale::global(std::locale::classic()); test_to_double(); - std::locale::global(std::locale::classic()); + auto classic_locale = std::locale::global(host_locale); test_to_double(); } -static void test_get_url_query_file_name_one(const char *prefix, const char *suffix, const char *file_name) { - auto path = string(prefix) + string(file_name) + string(suffix); - ASSERT_STREQ(file_name, get_url_query_file_name(path)); - ASSERT_STREQ(file_name, get_url_file_name("http://telegram.org" + path)); - ASSERT_STREQ(file_name, get_url_file_name("http://telegram.org:80" + path)); - ASSERT_STREQ(file_name, get_url_file_name("telegram.org" + path)); +TEST(Misc, print_int) { + ASSERT_STREQ("-9223372036854775808", PSLICE() << -9223372036854775807 - 1); + ASSERT_STREQ("-2147483649", PSLICE() << -2147483649ll); + ASSERT_STREQ("-2147483648", PSLICE() << -2147483647 - 1); + ASSERT_STREQ("-2147483647", PSLICE() << -2147483647); + ASSERT_STREQ("-123456789", PSLICE() << -123456789); + ASSERT_STREQ("-1", PSLICE() << -1); + ASSERT_STREQ("0", PSLICE() << 0); + ASSERT_STREQ("1", PSLICE() << 1); + ASSERT_STREQ("9", PSLICE() << 9); + ASSERT_STREQ("10", PSLICE() << 10); + ASSERT_STREQ("2147483647", PSLICE() << 2147483647); + ASSERT_STREQ("2147483648", PSLICE() << 2147483648ll); + ASSERT_STREQ("2147483649", PSLICE() << 2147483649ll); + ASSERT_STREQ("9223372036854775807", PSLICE() << 9223372036854775807ll); +} + +TEST(Misc, print_uint) { + ASSERT_STREQ("0", PSLICE() << 0u); + ASSERT_STREQ("1", PSLICE() << 1u); + ASSERT_STREQ("9", PSLICE() << 9u); + ASSERT_STREQ("10", PSLICE() << 10u); + ASSERT_STREQ("2147483647", PSLICE() << 2147483647u); + ASSERT_STREQ("2147483648", PSLICE() << 2147483648u); + ASSERT_STREQ("2147483649", PSLICE() << 2147483649u); + ASSERT_STREQ("9223372036854775807", PSLICE() << 9223372036854775807u); +} + +static void test_idn_to_ascii_one(const td::string &host, const td::string &result) { + if (result != td::idn_to_ascii(host).ok()) { + LOG(ERROR) << "Failed to convert " << host << " to " << result << ", got \"" << td::idn_to_ascii(host).ok() << "\""; + } +} + +TEST(Misc, idn_to_ascii) { + test_idn_to_ascii_one("::::::::::::::::::::::::::::::::::::::@/", "::::::::::::::::::::::::::::::::::::::@/"); + test_idn_to_ascii_one("", ""); + test_idn_to_ascii_one("%30", "%30"); + test_idn_to_ascii_one("127.0.0.1", "127.0.0.1"); + test_idn_to_ascii_one("fe80::", "fe80::"); + test_idn_to_ascii_one("fe80:0:0:0:200:f8ff:fe21:67cf", "fe80:0:0:0:200:f8ff:fe21:67cf"); + test_idn_to_ascii_one("2001:0db8:11a3:09d7:1f34:8a2e:07a0:765d", "2001:0db8:11a3:09d7:1f34:8a2e:07a0:765d"); + test_idn_to_ascii_one("::ffff:192.0.2.1", "::ffff:192.0.2.1"); + test_idn_to_ascii_one("ABCDEF", "abcdef"); + test_idn_to_ascii_one("abcdef", "abcdef"); + test_idn_to_ascii_one("abæcdöef", "xn--abcdef-qua4k"); + test_idn_to_ascii_one("schön", "xn--schn-7qa"); + test_idn_to_ascii_one("ยจฆฟคฏข", "xn--22cdfh1b8fsa"); + test_idn_to_ascii_one("☺", "xn--74h"); + test_idn_to_ascii_one("правда", "xn--80aafi6cg"); + test_idn_to_ascii_one("büücher", "xn--bcher-kvaa"); + test_idn_to_ascii_one("BüüCHER", "xn--bcher-kvaa"); + test_idn_to_ascii_one("bücüher", "xn--bcher-kvab"); + test_idn_to_ascii_one("bücherü", "xn--bcher-kvae"); + test_idn_to_ascii_one("ýbücher", "xn--bcher-kvaf"); + test_idn_to_ascii_one("übücher", "xn--bcher-jvab"); + test_idn_to_ascii_one("bücher.tld", "xn--bcher-kva.tld"); + test_idn_to_ascii_one("кто.рф", "xn--j1ail.xn--p1ai"); + test_idn_to_ascii_one("wіkіреdіа.org", "xn--wkd-8cdx9d7hbd.org"); + test_idn_to_ascii_one("cnwin2k8中国.avol.com", "xn--cnwin2k8-sd0mx14e.avol.com"); + test_idn_to_ascii_one("win-2k12r2-addc.阿伯测阿伯测ad.hai.com", "win-2k12r2-addc.xn--ad-tl3ca3569aba8944eca.hai.com"); + test_idn_to_ascii_one("✌.ws", "xn--7bi.ws"); + // test_idn_to_ascii_one("✌️.ws", "xn--7bi.ws"); // needs nameprep to succeed + test_idn_to_ascii_one("⛧", "xn--59h"); + test_idn_to_ascii_one("--рф.рф", "xn-----mmcq.xn--p1ai"); + ASSERT_TRUE(td::idn_to_ascii("\xc0").is_error()); +} + +#if TD_WINDOWS +static void test_to_wstring_one(const td::string &str) { + ASSERT_STREQ(str, td::from_wstring(td::to_wstring(str).ok()).ok()); +} + +TEST(Misc, to_wstring) { + test_to_wstring_one(""); + for (int i = 0; i < 10; i++) { + test_to_wstring_one("test"); + test_to_wstring_one("тест"); + } + td::string str; + for (td::uint32 i = 0; i <= 0xD7FF; i++) { + td::append_utf8_character(str, i); + } + for (td::uint32 i = 0xE000; i <= 0x10FFFF; i++) { + td::append_utf8_character(str, i); + } + test_to_wstring_one(str); + ASSERT_TRUE(td::to_wstring("\xc0").is_error()); + auto emoji = td::to_wstring("🏟").ok(); + ASSERT_TRUE(td::from_wstring(emoji).ok() == "🏟"); + ASSERT_TRUE(emoji.size() == 2); + auto emoji2 = emoji; + emoji[0] = emoji[1]; + emoji2[1] = emoji2[0]; + ASSERT_TRUE(td::from_wstring(emoji).is_error()); + ASSERT_TRUE(td::from_wstring(emoji2).is_error()); + emoji2[0] = emoji[0]; + ASSERT_TRUE(td::from_wstring(emoji2).is_error()); +} +#endif + +static void test_translit(const td::string &word, const td::vector<td::string> &result, bool allow_partial = true) { + ASSERT_EQ(result, td::get_word_transliterations(word, allow_partial)); +} + +TEST(Misc, translit) { + test_translit("word", {"word", "ворд"}); + test_translit("", {}); + test_translit("ььььььььь", {"ььььььььь"}); + test_translit("крыло", {"krylo", "крыло"}); + test_translit("krylo", {"krylo", "крило"}); + test_translit("crylo", {"crylo", "крило"}); + test_translit("cheiia", {"cheiia", "кхеииа", "чейия"}); + test_translit("cheii", {"cheii", "кхеии", "чейи", "чейий", "чейия"}); + test_translit("s", {"s", "с", "ш", "щ"}); + test_translit("y", {"e", "y", "е", "и", "ю", "я"}); + test_translit("j", {"e", "j", "е", "й", "ю", "я"}); + test_translit("yo", {"e", "yo", "е", "ио"}); + test_translit("artjom", {"artem", "artjom", "артем", "артйом"}); + test_translit("artyom", {"artem", "artyom", "артем", "артиом"}); + test_translit("arty", {"arte", "arty", "арте", "арти", "артю", "артя"}); + test_translit("льи", {"li", "lia", "ly", "льи"}); + test_translit("y", {"y", "и"}, false); + test_translit("yo", {"e", "yo", "е", "ио"}, false); +} + +static void test_unicode(td::uint32 (*func)(td::uint32)) { + for (td::uint32 i = 0; i <= 0x110000; i++) { + auto res = func(i); + CHECK(res <= 0x10ffff); + } +} + +TEST(Misc, unicode) { + test_unicode(td::prepare_search_character); + test_unicode(td::unicode_to_lower); + test_unicode(td::remove_diacritics); +} + +TEST(Misc, get_unicode_simple_category) { + td::uint32 result = 0; + for (size_t t = 0; t < 100; t++) { + for (td::uint32 i = 0; i <= 0x10ffff; i++) { + result = result * 123 + static_cast<td::uint32>(static_cast<int>(td::get_unicode_simple_category(i))); + } + } + LOG(INFO) << result; +} + +TEST(Misc, get_unicode_simple_category_small) { + td::uint32 result = 0; + for (size_t t = 0; t < 1000; t++) { + for (td::uint32 i = 0; i <= 0xffff; i++) { + result = result * 123 + static_cast<td::uint32>(static_cast<int>(td::get_unicode_simple_category(i))); + } + } + LOG(INFO) << result; +} + +TEST(BigNum, from_decimal) { + ASSERT_TRUE(td::BigNum::from_decimal("").is_error()); + ASSERT_TRUE(td::BigNum::from_decimal("a").is_error()); + ASSERT_TRUE(td::BigNum::from_decimal("123a").is_error()); + ASSERT_TRUE(td::BigNum::from_decimal("-123a").is_error()); + // ASSERT_TRUE(td::BigNum::from_decimal("-").is_error()); + ASSERT_TRUE(td::BigNum::from_decimal("123").is_ok()); + ASSERT_TRUE(td::BigNum::from_decimal("-123").is_ok()); + ASSERT_TRUE(td::BigNum::from_decimal("0").is_ok()); + ASSERT_TRUE(td::BigNum::from_decimal("-0").is_ok()); + ASSERT_TRUE(td::BigNum::from_decimal("-999999999999999999999999999999999999999999999999").is_ok()); + ASSERT_TRUE(td::BigNum::from_decimal("999999999999999999999999999999999999999999999999").is_ok()); +} + +TEST(BigNum, from_binary) { + ASSERT_STREQ(td::BigNum::from_binary("").to_decimal(), "0"); + ASSERT_STREQ(td::BigNum::from_binary("a").to_decimal(), "97"); + ASSERT_STREQ(td::BigNum::from_binary("\x00\xff").to_decimal(), "255"); + ASSERT_STREQ(td::BigNum::from_binary("\x00\x01\x00\x00").to_decimal(), "65536"); + ASSERT_STREQ(td::BigNum::from_le_binary("").to_decimal(), "0"); + ASSERT_STREQ(td::BigNum::from_le_binary("a").to_decimal(), "97"); + ASSERT_STREQ(td::BigNum::from_le_binary("\x00\xff").to_decimal(), "65280"); + ASSERT_STREQ(td::BigNum::from_le_binary("\x00\x01\x00\x00").to_decimal(), "256"); + ASSERT_STREQ(td::BigNum::from_decimal("255").move_as_ok().to_binary(), "\xff"); + ASSERT_STREQ(td::BigNum::from_decimal("255").move_as_ok().to_le_binary(), "\xff"); + ASSERT_STREQ(td::BigNum::from_decimal("255").move_as_ok().to_binary(2), "\x00\xff"); + ASSERT_STREQ(td::BigNum::from_decimal("255").move_as_ok().to_le_binary(2), "\xff\x00"); + ASSERT_STREQ(td::BigNum::from_decimal("65280").move_as_ok().to_binary(), "\xff\x00"); + ASSERT_STREQ(td::BigNum::from_decimal("65280").move_as_ok().to_le_binary(), "\x00\xff"); + ASSERT_STREQ(td::BigNum::from_decimal("65280").move_as_ok().to_binary(2), "\xff\x00"); + ASSERT_STREQ(td::BigNum::from_decimal("65280").move_as_ok().to_le_binary(2), "\x00\xff"); + ASSERT_STREQ(td::BigNum::from_decimal("65536").move_as_ok().to_binary(), "\x01\x00\x00"); + ASSERT_STREQ(td::BigNum::from_decimal("65536").move_as_ok().to_le_binary(), "\x00\x00\x01"); + ASSERT_STREQ(td::BigNum::from_decimal("65536").move_as_ok().to_binary(4), "\x00\x01\x00\x00"); + ASSERT_STREQ(td::BigNum::from_decimal("65536").move_as_ok().to_le_binary(4), "\x00\x00\x01\x00"); +} + +static void test_get_ipv4(td::uint32 ip) { + td::IPAddress ip_address; + ip_address.init_ipv4_port(td::IPAddress::ipv4_to_str(ip), 80).ensure(); + ASSERT_EQ(ip_address.get_ipv4(), ip); +} + +TEST(Misc, IPAddress_get_ipv4) { + test_get_ipv4(0x00000000); + test_get_ipv4(0x010000FF); + test_get_ipv4(0xFF000001); + test_get_ipv4(0x01020304); + test_get_ipv4(0x04030201); + test_get_ipv4(0xFFFFFFFF); +} + +static void test_is_reserved(const td::string &ip, bool is_reserved) { + td::IPAddress ip_address; + ip_address.init_ipv4_port(ip, 80).ensure(); + ASSERT_EQ(is_reserved, ip_address.is_reserved()); +} + +TEST(Misc, IPAddress_is_reserved) { + test_is_reserved("0.0.0.0", true); + test_is_reserved("0.255.255.255", true); + test_is_reserved("1.0.0.0", false); + test_is_reserved("5.0.0.0", false); + test_is_reserved("9.255.255.255", false); + test_is_reserved("10.0.0.0", true); + test_is_reserved("10.255.255.255", true); + test_is_reserved("11.0.0.0", false); + test_is_reserved("100.63.255.255", false); + test_is_reserved("100.64.0.0", true); + test_is_reserved("100.127.255.255", true); + test_is_reserved("100.128.0.0", false); + test_is_reserved("126.255.255.255", false); + test_is_reserved("127.0.0.0", true); + test_is_reserved("127.255.255.255", true); + test_is_reserved("128.0.0.0", false); + test_is_reserved("169.253.255.255", false); + test_is_reserved("169.254.0.0", true); + test_is_reserved("169.254.255.255", true); + test_is_reserved("169.255.0.0", false); + test_is_reserved("172.15.255.255", false); + test_is_reserved("172.16.0.0", true); + test_is_reserved("172.31.255.255", true); + test_is_reserved("172.32.0.0", false); + test_is_reserved("191.255.255.255", false); + test_is_reserved("192.0.0.0", true); + test_is_reserved("192.0.0.255", true); + test_is_reserved("192.0.1.0", false); + test_is_reserved("192.0.1.255", false); + test_is_reserved("192.0.2.0", true); + test_is_reserved("192.0.2.255", true); + test_is_reserved("192.0.3.0", false); + test_is_reserved("192.88.98.255", false); + test_is_reserved("192.88.99.0", true); + test_is_reserved("192.88.99.255", true); + test_is_reserved("192.88.100.0", false); + test_is_reserved("192.167.255.255", false); + test_is_reserved("192.168.0.0", true); + test_is_reserved("192.168.255.255", true); + test_is_reserved("192.169.0.0", false); + test_is_reserved("198.17.255.255", false); + test_is_reserved("198.18.0.0", true); + test_is_reserved("198.19.255.255", true); + test_is_reserved("198.20.0.0", false); + test_is_reserved("198.51.99.255", false); + test_is_reserved("198.51.100.0", true); + test_is_reserved("198.51.100.255", true); + test_is_reserved("198.51.101.0", false); + test_is_reserved("203.0.112.255", false); + test_is_reserved("203.0.113.0", true); + test_is_reserved("203.0.113.255", true); + test_is_reserved("203.0.114.0", false); + test_is_reserved("223.255.255.255", false); + test_is_reserved("224.0.0.0", true); + test_is_reserved("239.255.255.255", true); + test_is_reserved("240.0.0.0", true); + test_is_reserved("255.255.255.254", true); + test_is_reserved("255.255.255.255", true); +} + +TEST(Misc, ipv6_clear) { + td::IPAddress ip_address; + ip_address.init_host_port("2001:0db8:85a3:0000:0000:8a2e:0370:7334", 123).ensure(); + ASSERT_EQ("2001:db8:85a3::8a2e:370:7334", ip_address.get_ip_str()); + ip_address.clear_ipv6_interface(); + ASSERT_EQ("2001:db8:85a3::", ip_address.get_ip_str()); +} + +static void test_split(td::Slice str, std::pair<td::Slice, td::Slice> expected) { + ASSERT_EQ(expected, td::split(str)); +} + +TEST(Misc, split) { + test_split("", {"", ""}); + test_split(" ", {"", ""}); + test_split("abcdef", {"abcdef", ""}); + test_split("abc def", {"abc", "def"}); + test_split("a bcdef", {"a", "bcdef"}); + test_split(" abcdef", {"", "abcdef"}); + test_split("abcdef ", {"abcdef", ""}); + test_split("ab cd ef", {"ab", "cd ef"}); + test_split("ab cdef ", {"ab", "cdef "}); + test_split(" abcd ef", {"", "abcd ef"}); + test_split(" abcdef ", {"", "abcdef "}); } -TEST(Misc, get_url_query_file_name) { - for (auto suffix : {"?t=1#test", "#test?t=1", "#?t=1", "?t=1#", "#test", "?t=1", "#", "?", ""}) { - test_get_url_query_file_name_one("", suffix, ""); - test_get_url_query_file_name_one("/", suffix, ""); - test_get_url_query_file_name_one("/a/adasd/", suffix, ""); - test_get_url_query_file_name_one("/a/lklrjetn/", suffix, "adasd.asdas"); - test_get_url_query_file_name_one("/", suffix, "a123asadas"); - test_get_url_query_file_name_one("/", suffix, "\\a\\1\\2\\3\\a\\s\\a\\das"); +static void test_full_split(td::Slice str, const td::vector<td::Slice> &expected) { + ASSERT_EQ(expected, td::full_split(str)); +} + +static void test_full_split(td::Slice str, char c, std::size_t max_parts, const td::vector<td::Slice> &expected) { + ASSERT_EQ(expected, td::full_split(str, c, max_parts)); +} + +TEST(Misc, full_split) { + test_full_split("", {}); + test_full_split(" ", {"", ""}); + test_full_split(" ", {"", "", ""}); + test_full_split("abcdef", {"abcdef"}); + test_full_split("abc def", {"abc", "def"}); + test_full_split("a bcdef", {"a", "bcdef"}); + test_full_split(" abcdef", {"", "abcdef"}); + test_full_split("abcdef ", {"abcdef", ""}); + test_full_split("ab cd ef", {"ab", "cd", "ef"}); + test_full_split("ab cdef ", {"ab", "cdef", ""}); + test_full_split(" abcd ef", {"", "abcd", "ef"}); + test_full_split(" abcdef ", {"", "abcdef", ""}); + test_full_split(" ab cd ef ", {"", "ab", "cd", "ef", ""}); + test_full_split(" ab cd ef ", {"", "", "ab", "", "cd", "", "ef", "", ""}); + test_full_split("ab cd ef gh", ' ', 3, {"ab", "cd", "ef gh"}); +} + +TEST(Misc, StringBuilder) { + auto small_str = td::string{"abcdefghij"}; + auto big_str = td::string(1000, 'a'); + using V = td::vector<td::string>; + for (auto use_buf : {false, true}) { + for (std::size_t initial_buffer_size : {0, 1, 5, 10, 100, 1000, 2000}) { + for (const auto &test : + {V{small_str}, V{small_str, big_str, big_str, small_str}, V{big_str, small_str, big_str}}) { + td::string buf(initial_buffer_size, '\0'); + td::StringBuilder sb(buf, use_buf); + td::string res; + for (const auto &x : test) { + res += x; + sb << x; + } + if (use_buf) { + ASSERT_EQ(res, sb.as_cslice()); + } else { + auto got = sb.as_cslice(); + res.resize(got.size()); + ASSERT_EQ(res, got); + } + } + } + } +} + +TEST(Misc, As) { + char buf[100]; + td::as<int>(buf) = 123; + ASSERT_EQ(123, td::as<int>(static_cast<const char *>(buf))); + ASSERT_EQ(123, td::as<int>(static_cast<char *>(buf))); + char buf2[100]; + td::as<int>(buf2) = td::as<int>(buf); + ASSERT_EQ(123, td::as<int>(static_cast<const char *>(buf2))); + ASSERT_EQ(123, td::as<int>(static_cast<char *>(buf2))); +} + +TEST(Misc, Regression) { + td::string name = "regression_db"; + td::RegressionTester::destroy(name); + + { + auto tester = td::RegressionTester::create(name); + tester->save_db(); + tester->verify_test("one_plus_one", "two").ensure(); + tester->verify_test("one_plus_one", "two").ensure(); + tester->verify_test("two_plus_one", "three").ensure(); + tester->verify_test("one_plus_one", "two").ensure(); + tester->verify_test("two_plus_one", "three").ensure(); + tester->save_db(); + } + { + auto tester = td::RegressionTester::create(name); + tester->save_db(); + tester->verify_test("one_plus_one", "two").ensure(); + tester->verify_test("one_plus_one", "two").ensure(); + tester->verify_test("two_plus_one", "three").ensure(); + tester->verify_test("one_plus_one", "two").ensure(); + tester->verify_test("two_plus_one", "three").ensure(); + tester->save_db(); + tester->verify_test("one_plus_one", "three").ensure_error(); + tester->verify_test("two_plus_one", "two").ensure_error(); + } + { + auto tester = td::RegressionTester::create(name); + tester->verify_test("one_plus_one", "three").ensure_error(); + tester->verify_test("two_plus_one", "two").ensure_error(); + } +} + +TEST(Misc, Bits) { + ASSERT_EQ(32, td::count_leading_zeroes32(0)); + ASSERT_EQ(64, td::count_leading_zeroes64(0)); + ASSERT_EQ(32, td::count_trailing_zeroes32(0)); + ASSERT_EQ(64, td::count_trailing_zeroes64(0)); + + for (int i = 0; i < 32; i++) { + ASSERT_EQ(31 - i, td::count_leading_zeroes32(1u << i)); + ASSERT_EQ(i, td::count_trailing_zeroes32(1u << i)); + ASSERT_EQ(31 - i, td::count_leading_zeroes_non_zero32(1u << i)); + ASSERT_EQ(i, td::count_trailing_zeroes_non_zero32(1u << i)); + } + for (int i = 0; i < 64; i++) { + ASSERT_EQ(63 - i, td::count_leading_zeroes64(1ull << i)); + ASSERT_EQ(i, td::count_trailing_zeroes64(1ull << i)); + ASSERT_EQ(63 - i, td::count_leading_zeroes_non_zero64(1ull << i)); + ASSERT_EQ(i, td::count_trailing_zeroes_non_zero64(1ull << i)); + } + + ASSERT_EQ(0x12345678u, td::bswap32(0x78563412u)); + ASSERT_EQ(0x12345678abcdef67ull, td::bswap64(0x67efcdab78563412ull)); + + td::uint8 buf[8] = {1, 90, 2, 18, 129, 255, 0, 2}; + td::uint64 num2 = td::bswap64(td::as<td::uint64>(buf)); + td::uint64 num = (static_cast<td::uint64>(buf[0]) << 56) | (static_cast<td::uint64>(buf[1]) << 48) | + (static_cast<td::uint64>(buf[2]) << 40) | (static_cast<td::uint64>(buf[3]) << 32) | + (static_cast<td::uint64>(buf[4]) << 24) | (static_cast<td::uint64>(buf[5]) << 16) | + (static_cast<td::uint64>(buf[6]) << 8) | (static_cast<td::uint64>(buf[7])); + ASSERT_EQ(num, num2); + + ASSERT_EQ(0, td::count_bits32(0)); + ASSERT_EQ(0, td::count_bits64(0)); + ASSERT_EQ(4, td::count_bits32((1u << 31) | 7)); + ASSERT_EQ(4, td::count_bits64((1ull << 63) | 7)); +} + +TEST(Misc, BitsRange) { + auto to_vec_a = [](td::uint64 x) { + td::vector<td::int32> bits; + for (auto i : td::BitsRange(x)) { + bits.push_back(i); + } + return bits; + }; + + auto to_vec_b = [](td::uint64 x) { + td::vector<td::int32> bits; + td::int32 pos = 0; + while (x != 0) { + if ((x & 1) != 0) { + bits.push_back(pos); + } + x >>= 1; + pos++; + } + return bits; + }; + + auto do_check = [](const td::vector<td::int32> &a, const td::vector<td::int32> &b) { + ASSERT_EQ(b, a); + }; + auto check = [&](td::uint64 x) { + do_check(to_vec_a(x), to_vec_b(x)); + }; + + do_check(to_vec_a(21), {0, 2, 4}); + for (int x = 0; x < 100; x++) { + check(x); + check(std::numeric_limits<td::uint32>::max() - x); + check(std::numeric_limits<td::uint64>::max() - x); + } +} + +#if !TD_THREAD_UNSUPPORTED +TEST(Misc, Time) { + td::Stage run; + td::Stage check; + td::Stage finish; + + std::size_t threads_n = 3; + td::vector<td::thread> threads; + td::vector<std::atomic<double>> ts(threads_n); + for (std::size_t i = 0; i < threads_n; i++) { + threads.emplace_back([&, thread_id = i] { + for (td::uint64 round = 1; round < 10000; round++) { + ts[thread_id] = 0; + run.wait(round * threads_n); + ts[thread_id] = td::Time::now(); + check.wait(round * threads_n); + for (auto &ts_ref : ts) { + auto other_ts = ts_ref.load(); + if (other_ts != 0) { + ASSERT_TRUE(other_ts <= td::Time::now_cached()); + } + } + + finish.wait(round * threads_n); + } + }); + } + for (auto &thread : threads) { + thread.join(); + } +} +#endif + +TEST(Misc, uint128) { + td::vector<td::uint64> parts = {0, + 1, + 2000, + 2001, + std::numeric_limits<td::uint64>::max(), + std::numeric_limits<td::uint64>::max() - 1, + std::numeric_limits<td::uint32>::max(), + static_cast<td::uint64>(std::numeric_limits<td::uint32>::max()) + 1}; + td::vector<td::int64> signed_parts = {0, + 1, + 2000, + 2001, + -1, + -2000, + -2001, + std::numeric_limits<td::int64>::max(), + std::numeric_limits<td::int64>::max() - 1, + std::numeric_limits<td::int64>::min(), + std::numeric_limits<td::int64>::min() + 1, + std::numeric_limits<td::int32>::max(), + static_cast<td::int64>(std::numeric_limits<td::int32>::max()) + 1, + std::numeric_limits<td::int32>::max() - 1, + std::numeric_limits<td::int32>::min(), + std::numeric_limits<td::int32>::min() + 1, + static_cast<td::int64>(std::numeric_limits<td::int32>::min()) - 1}; + +#if TD_HAVE_INT128 + auto to_intrinsic = [](td::uint128_emulated num) { + return td::uint128_intrinsic(num.hi(), num.lo()); + }; + auto eq = [](td::uint128_emulated a, td::uint128_intrinsic b) { + return a.hi() == b.hi() && a.lo() == b.lo(); + }; + auto ensure_eq = [&](td::uint128_emulated a, td::uint128_intrinsic b) { + if (!eq(a, b)) { + LOG(FATAL) << "[" << a.hi() << ";" << a.lo() << "] vs [" << b.hi() << ";" << b.lo() << "]"; + } + }; +#endif + + td::vector<td::uint128_emulated> nums; + for (auto hi : parts) { + for (auto lo : parts) { + auto a = td::uint128_emulated(hi, lo); +#if TD_HAVE_INT128 + auto ia = td::uint128_intrinsic(hi, lo); + ensure_eq(a, ia); +#endif + nums.push_back(a); + nums.pop_back(); + nums.push_back({hi, lo}); + } + } + +#if TD_HAVE_INT128 + for (auto a : nums) { + auto ia = to_intrinsic(a); + ensure_eq(a, ia); + CHECK(a.is_zero() == ia.is_zero()); + for (int i = 0; i <= 130; i++) { + ensure_eq(a.shl(i), ia.shl(i)); + ensure_eq(a.shr(i), ia.shr(i)); + } + for (auto b : parts) { + ensure_eq(a.mult(b), ia.mult(b)); + } + for (auto b : signed_parts) { + ensure_eq(a.mult_signed(b), ia.mult_signed(b)); + if (b == 0) { + continue; + } + td::int64 q; + td::int64 r; + a.divmod_signed(b, &q, &r); + td::int64 iq; + td::int64 ir; + ia.divmod_signed(b, &iq, &ir); + ASSERT_EQ(q, iq); + ASSERT_EQ(r, ir); + } + for (auto b : nums) { + auto ib = to_intrinsic(b); + //LOG(ERROR) << ia.hi() << ";" << ia.lo() << " " << ib.hi() << ";" << ib.lo(); + ensure_eq(a.mult(b), ia.mult(ib)); + ensure_eq(a.add(b), ia.add(ib)); + ensure_eq(a.sub(b), ia.sub(ib)); + if (!b.is_zero()) { + ensure_eq(a.div(b), ia.div(ib)); + ensure_eq(a.mod(b), ia.mod(ib)); + } + } + } + + for (auto signed_part : signed_parts) { + auto a = td::uint128_emulated::from_signed(signed_part); + auto ia = td::uint128_intrinsic::from_signed(signed_part); + ensure_eq(a, ia); + } +#endif +} + +template <template <class T> class HashT, class ValueT> +static td::Status test_hash(const td::vector<ValueT> &values) { + for (std::size_t i = 0; i < values.size(); i++) { + for (std::size_t j = i; j < values.size(); j++) { + auto &a = values[i]; + auto &b = values[j]; + auto a_hash = HashT<ValueT>()(a); + auto b_hash = HashT<ValueT>()(b); + if (a == b) { + if (a_hash != b_hash) { + return td::Status::Error("Hash differs for same values"); + } + } else { + if (a_hash == b_hash) { + return td::Status::Error("Hash is the same for different values"); + } + } + } + } + return td::Status::OK(); +} + +class BadValue { + public: + explicit BadValue(std::size_t value) : value_(value) { + } + + template <class H> + friend H AbslHashValue(H hasher, const BadValue &value) { + return hasher; + } + bool operator==(const BadValue &other) const { + return value_ == other.value_; + } + + private: + std::size_t value_; +}; + +class ValueA { + public: + explicit ValueA(std::size_t value) : value_(value) { + } + template <class H> + friend H AbslHashValue(H hasher, ValueA value) { + return H::combine(std::move(hasher), value.value_); + } + bool operator==(const ValueA &other) const { + return value_ == other.value_; + } + + private: + std::size_t value_; +}; + +class ValueB { + public: + explicit ValueB(std::size_t value) : value_(value) { + } + + template <class H> + friend H AbslHashValue(H hasher, ValueB value) { + return H::combine(std::move(hasher), value.value_); + } + bool operator==(const ValueB &other) const { + return value_ == other.value_; + } + + private: + std::size_t value_; +}; + +template <template <class T> class HashT> +static void test_hash() { + // Just check that the following compiles + AbslHashValue(td::Hasher(), ValueA{1}); + HashT<ValueA>()(ValueA{1}); + std::unordered_map<ValueA, int, HashT<ValueA>> s; + s[ValueA{1}] = 1; + td::HashMap<ValueA, int> su; + su[ValueA{1}] = 1; + td::HashSet<ValueA> su2; + su2.insert(ValueA{1}); +#if TD_HAVE_ABSL + std::unordered_map<ValueA, int, absl::Hash<ValueA>> x; + absl::flat_hash_map<ValueA, int, HashT<ValueA>> sa; + sa[ValueA{1}] = 1; +#endif + + test_hash<HashT, std::size_t>({1, 2, 3, 4, 5}).ensure(); + test_hash<HashT, BadValue>({BadValue{1}, BadValue{2}}).ensure_error(); + test_hash<HashT, ValueA>({ValueA{1}, ValueA{2}}).ensure(); + test_hash<HashT, ValueB>({ValueB{1}, ValueB{2}}).ensure(); + test_hash<HashT, std::pair<int, int>>({{1, 1}, {1, 2}}).ensure(); + // FIXME: use some better hash + //test_hash<HashT, std::pair<int, int>>({{1, 1}, {1, 2}, {2, 1}, {2, 2}}).ensure(); +} + +TEST(Misc, Hasher) { + test_hash<td::TdHash>(); +#if TD_HAVE_ABSL + test_hash<td::AbslHash>(); +#endif +} + +TEST(Misc, CancellationToken) { + td::CancellationTokenSource source; + source.cancel(); + auto token1 = source.get_cancellation_token(); + auto token2 = source.get_cancellation_token(); + CHECK(!token1); + source.cancel(); + CHECK(token1); + CHECK(token2); + auto token3 = source.get_cancellation_token(); + CHECK(!token3); + source.cancel(); + CHECK(token3); + + auto token4 = source.get_cancellation_token(); + CHECK(!token4); + source = td::CancellationTokenSource{}; + CHECK(token4); +} + +TEST(Misc, Xorshift128plus) { + td::Random::Xorshift128plus rnd(123); + ASSERT_EQ(11453256657207062272ull, rnd()); + ASSERT_EQ(14917490455889357332ull, rnd()); + ASSERT_EQ(5645917797309401285ull, rnd()); + ASSERT_EQ(13554822455746959330ull, rnd()); +} + +TEST(Misc, uname) { + auto first_version = td::get_operating_system_version(); + auto second_version = td::get_operating_system_version(); + ASSERT_STREQ(first_version, second_version); + ASSERT_EQ(first_version.begin(), second_version.begin()); + ASSERT_TRUE(!first_version.empty()); +} + +TEST(Misc, serialize) { + td::int32 x = 1; + ASSERT_EQ(td::base64_encode(td::serialize(x)), td::base64_encode(td::string("\x01\x00\x00\x00", 4))); + td::int64 y = -2; + ASSERT_EQ(td::base64_encode(td::serialize(y)), td::base64_encode(td::string("\xfe\xff\xff\xff\xff\xff\xff\xff", 8))); +} + +TEST(Misc, check_reset_guard) { + CheckExitGuard check_exit_guard{false}; +} + +TEST(FloodControl, Fast) { + td::FloodControlFast fc; + fc.add_limit(1, 5); + fc.add_limit(5, 10); + + td::int32 count = 0; + double now = 0; + for (int i = 0; i < 100; i++) { + now = fc.get_wakeup_at(); + fc.add_event(now); + LOG(INFO) << ++count << ": " << now; } } diff --git a/protocols/Telegram/tdlib/td/tdutils/test/port.cpp b/protocols/Telegram/tdlib/td/tdutils/test/port.cpp new file mode 100644 index 0000000000..92b1729977 --- /dev/null +++ b/protocols/Telegram/tdlib/td/tdutils/test/port.cpp @@ -0,0 +1,316 @@ +// +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 +// +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +#include "td/utils/algorithm.h" +#include "td/utils/common.h" +#include "td/utils/logging.h" +#include "td/utils/misc.h" +#include "td/utils/port/EventFd.h" +#include "td/utils/port/FileFd.h" +#include "td/utils/port/IoSlice.h" +#include "td/utils/port/path.h" +#include "td/utils/port/signals.h" +#include "td/utils/port/sleep.h" +#include "td/utils/port/thread.h" +#include "td/utils/port/thread_local.h" +#include "td/utils/Random.h" +#include "td/utils/ScopeGuard.h" +#include "td/utils/Slice.h" +#include "td/utils/SliceBuilder.h" +#include "td/utils/tests.h" +#include "td/utils/Time.h" + +#if TD_PORT_POSIX && !TD_THREAD_UNSUPPORTED +#include <algorithm> +#include <atomic> +#include <mutex> + +#include <pthread.h> +#include <signal.h> +#endif + +TEST(Port, files) { + td::CSlice main_dir = "test_dir"; + td::rmrf(main_dir).ignore(); + ASSERT_TRUE(td::FileFd::open(main_dir, td::FileFd::Write).is_error()); + ASSERT_TRUE(td::walk_path(main_dir, [](td::CSlice name, td::WalkPath::Type type) { UNREACHABLE(); }).is_error()); + td::mkdir(main_dir).ensure(); + td::mkdir(PSLICE() << main_dir << TD_DIR_SLASH << "A").ensure(); + td::mkdir(PSLICE() << main_dir << TD_DIR_SLASH << "B").ensure(); + td::mkdir(PSLICE() << main_dir << TD_DIR_SLASH << "B" << TD_DIR_SLASH << "D").ensure(); + td::mkdir(PSLICE() << main_dir << TD_DIR_SLASH << "C").ensure(); + ASSERT_TRUE(td::FileFd::open(main_dir, td::FileFd::Write).is_error()); + td::string fd_path = PSTRING() << main_dir << TD_DIR_SLASH << "t.txt"; + td::string fd2_path = PSTRING() << main_dir << TD_DIR_SLASH << "C" << TD_DIR_SLASH << "t2.txt"; + + auto fd = td::FileFd::open(fd_path, td::FileFd::Write | td::FileFd::CreateNew).move_as_ok(); + auto fd2 = td::FileFd::open(fd2_path, td::FileFd::Write | td::FileFd::CreateNew).move_as_ok(); + fd2.close(); + + int cnt = 0; + const int ITER_COUNT = 1000; + for (int i = 0; i < ITER_COUNT; i++) { + td::walk_path(main_dir, [&](td::CSlice name, td::WalkPath::Type type) { + if (type == td::WalkPath::Type::NotDir) { + ASSERT_TRUE(name == fd_path || name == fd2_path); + } + cnt++; + }).ensure(); + } + ASSERT_EQ((5 * 2 + 2) * ITER_COUNT, cnt); + bool was_abort = false; + td::walk_path(main_dir, [&](td::CSlice name, td::WalkPath::Type type) { + CHECK(!was_abort); + if (type == td::WalkPath::Type::EnterDir && ends_with(name, PSLICE() << TD_DIR_SLASH << "B")) { + was_abort = true; + return td::WalkPath::Action::Abort; + } + return td::WalkPath::Action::Continue; + }).ensure(); + CHECK(was_abort); + + cnt = 0; + bool is_first_dir = true; + td::walk_path(main_dir, [&](td::CSlice name, td::WalkPath::Type type) { + cnt++; + if (type == td::WalkPath::Type::EnterDir) { + if (is_first_dir) { + is_first_dir = false; + } else { + return td::WalkPath::Action::SkipDir; + } + } + return td::WalkPath::Action::Continue; + }).ensure(); + ASSERT_EQ(6, cnt); + + ASSERT_EQ(0u, fd.get_size().move_as_ok()); + ASSERT_EQ(12u, fd.write("Hello world!").move_as_ok()); + ASSERT_EQ(4u, fd.pwrite("abcd", 1).move_as_ok()); + char buf[100]; + td::MutableSlice buf_slice(buf, sizeof(buf)); + ASSERT_TRUE(fd.pread(buf_slice.substr(0, 4), 2).is_error()); + fd.seek(11).ensure(); + ASSERT_EQ(2u, fd.write("?!").move_as_ok()); + + ASSERT_TRUE(td::FileFd::open(main_dir, td::FileFd::Read | td::FileFd::CreateNew).is_error()); + fd = td::FileFd::open(fd_path, td::FileFd::Read | td::FileFd::Create).move_as_ok(); + ASSERT_EQ(13u, fd.get_size().move_as_ok()); + ASSERT_EQ(4u, fd.pread(buf_slice.substr(0, 4), 1).move_as_ok()); + ASSERT_STREQ("abcd", buf_slice.substr(0, 4)); + + fd.seek(0).ensure(); + ASSERT_EQ(13u, fd.read(buf_slice.substr(0, 13)).move_as_ok()); + ASSERT_STREQ("Habcd world?!", buf_slice.substr(0, 13)); +} + +TEST(Port, SparseFiles) { + td::CSlice path = "sparse.txt"; + td::unlink(path).ignore(); + auto fd = td::FileFd::open(path, td::FileFd::Write | td::FileFd::CreateNew).move_as_ok(); + ASSERT_EQ(0, fd.get_size().move_as_ok()); + td::int64 offset = 100000000; + fd.pwrite("a", offset).ensure(); + ASSERT_EQ(offset + 1, fd.get_size().move_as_ok()); + auto real_size = fd.get_real_size().move_as_ok(); + if (real_size >= offset + 1) { + LOG(ERROR) << "File system doesn't support sparse files, rewind during streaming can be slow"; + } + td::unlink(path).ensure(); +} + +TEST(Port, LargeFiles) { + td::CSlice path = "large.txt"; + td::unlink(path).ignore(); + auto fd = td::FileFd::open(path, td::FileFd::Write | td::FileFd::CreateNew).move_as_ok(); + ASSERT_EQ(0, fd.get_size().move_as_ok()); + td::int64 offset = static_cast<td::int64>(3) << 30; + if (fd.pwrite("abcd", offset).is_error()) { + LOG(ERROR) << "Writing to large files isn't supported"; + td::unlink(path).ensure(); + return; + } + fd = td::FileFd::open(path, td::FileFd::Read).move_as_ok(); + ASSERT_EQ(offset + 4, fd.get_size().move_as_ok()); + td::string res(4, '\0'); + if (fd.pread(res, offset).is_error()) { + LOG(ERROR) << "Reading of large files isn't supported"; + td::unlink(path).ensure(); + return; + } + ASSERT_STREQ(res, "abcd"); + fd.close(); + td::unlink(path).ensure(); +} + +TEST(Port, Writev) { + td::vector<td::IoSlice> vec; + td::CSlice test_file_path = "test.txt"; + td::unlink(test_file_path).ignore(); + auto fd = td::FileFd::open(test_file_path, td::FileFd::Write | td::FileFd::CreateNew).move_as_ok(); + vec.push_back(td::as_io_slice("a")); + vec.push_back(td::as_io_slice("b")); + vec.push_back(td::as_io_slice("cd")); + ASSERT_EQ(4u, fd.writev(vec).move_as_ok()); + vec.clear(); + vec.push_back(td::as_io_slice("efg")); + vec.push_back(td::as_io_slice("")); + vec.push_back(td::as_io_slice("hi")); + ASSERT_EQ(5u, fd.writev(vec).move_as_ok()); + fd.close(); + fd = td::FileFd::open(test_file_path, td::FileFd::Read).move_as_ok(); + td::Slice expected_content = "abcdefghi"; + ASSERT_EQ(static_cast<td::int64>(expected_content.size()), fd.get_size().ok()); + td::string content(expected_content.size(), '\0'); + ASSERT_EQ(content.size(), fd.read(content).move_as_ok()); + ASSERT_EQ(expected_content, content); +} + +#if TD_PORT_POSIX && !TD_THREAD_UNSUPPORTED + +static std::mutex m; +static td::vector<td::string> ptrs; +static td::vector<int *> addrs; +static TD_THREAD_LOCAL int thread_id; + +static void on_user_signal(int sig) { + int addr; + addrs[thread_id] = &addr; + std::unique_lock<std::mutex> guard(m); + ptrs.push_back(td::to_string(thread_id)); +} + +TEST(Port, SignalsAndThread) { + td::setup_signals_alt_stack().ensure(); + td::set_signal_handler(td::SignalType::User, on_user_signal).ensure(); + SCOPE_EXIT { + td::set_signal_handler(td::SignalType::User, nullptr).ensure(); + }; + td::vector<td::string> ans = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}; + { + td::vector<td::thread> threads; + int thread_n = 10; + td::vector<td::Stage> stages(thread_n); + ptrs.clear(); + addrs.resize(thread_n); + for (int i = 0; i < 10; i++) { + threads.emplace_back([&, i] { + td::setup_signals_alt_stack().ensure(); + if (i != 0) { + stages[i].wait(2); + } + thread_id = i; + pthread_kill(pthread_self(), SIGUSR1); + if (i + 1 < thread_n) { + stages[i + 1].wait(2); + } + }); + } + for (auto &t : threads) { + t.join(); + } + CHECK(ptrs == ans); + + //LOG(ERROR) << ptrs; + //LOG(ERROR) << addrs; + } + + { + td::Stage stage; + td::vector<td::thread> threads; + int thread_n = 10; + ptrs.clear(); + addrs.resize(thread_n); + for (int i = 0; i < 10; i++) { + threads.emplace_back([&, i] { + stage.wait(thread_n); + thread_id = i; + pthread_kill(pthread_self(), SIGUSR1); + }); + } + for (auto &t : threads) { + t.join(); + } + std::sort(ptrs.begin(), ptrs.end()); + CHECK(ptrs == ans); + auto addrs_size = addrs.size(); + td::unique(addrs); + ASSERT_EQ(addrs_size, addrs.size()); + //LOG(ERROR) << addrs; + } +} + +#if !TD_EVENTFD_UNSUPPORTED +TEST(Port, EventFdAndSignals) { + td::set_signal_handler(td::SignalType::User, [](int signal) {}).ensure(); + SCOPE_EXIT { + td::set_signal_handler(td::SignalType::User, nullptr).ensure(); + }; + + std::atomic_flag flag; + flag.test_and_set(); + auto main_thread = pthread_self(); + td::thread interrupt_thread{[&flag, &main_thread] { + td::setup_signals_alt_stack().ensure(); + while (flag.test_and_set()) { + pthread_kill(main_thread, SIGUSR1); + td::usleep_for(1000 * td::Random::fast(1, 10)); // 0.001s - 0.01s + } + }}; + + for (int timeout_ms : {0, 1, 2, 10, 100, 500}) { + double min_diff = 10000000; + double max_diff = 0; + for (int t = 0; t < td::max(5, 1000 / td::max(timeout_ms, 1)); t++) { + td::EventFd event_fd; + event_fd.init(); + auto start = td::Timestamp::now(); + event_fd.wait(timeout_ms); + auto end = td::Timestamp::now(); + auto passed = end.at() - start.at(); + auto diff = passed * 1000 - timeout_ms; + min_diff = td::min(min_diff, diff); + max_diff = td::max(max_diff, diff); + } + + LOG_CHECK(min_diff >= 0) << min_diff; + // LOG_CHECK(max_diff < 10) << max_diff; + LOG(INFO) << min_diff << " " << max_diff; + } + flag.clear(); +} +#endif +#endif + +#if TD_HAVE_THREAD_AFFINITY +TEST(Port, ThreadAffinityMask) { + auto thread_id = td::this_thread::get_id(); + auto old_mask = td::thread::get_affinity_mask(thread_id); + LOG(INFO) << "Initial thread " << thread_id << " affinity mask: " << old_mask; + for (size_t i = 0; i < 64; i++) { + auto mask = td::thread::get_affinity_mask(thread_id); + LOG(INFO) << mask; + auto result = td::thread::set_affinity_mask(thread_id, static_cast<td::uint64>(1) << i); + LOG(INFO) << i << ": " << result << ' ' << td::thread::get_affinity_mask(thread_id); + + if (i <= 1) { + td::thread thread([] { + auto thread_id = td::this_thread::get_id(); + auto mask = td::thread::get_affinity_mask(thread_id); + LOG(INFO) << "New thread " << thread_id << " affinity mask: " << mask; + auto result = td::thread::set_affinity_mask(thread_id, 1); + LOG(INFO) << "Thread " << thread_id << ": " << result << ' ' << td::thread::get_affinity_mask(thread_id); + }); + LOG(INFO) << "Will join new thread " << thread.get_id() + << " with affinity mask: " << td::thread::get_affinity_mask(thread.get_id()); + } + } + auto result = td::thread::set_affinity_mask(thread_id, old_mask); + LOG(INFO) << result; + old_mask = td::thread::get_affinity_mask(thread_id); + LOG(INFO) << old_mask; +} +#endif diff --git a/protocols/Telegram/tdlib/td/tdutils/test/pq.cpp b/protocols/Telegram/tdlib/td/tdutils/test/pq.cpp index 5210cc2638..d919d661b5 100644 --- a/protocols/Telegram/tdlib/td/tdutils/test/pq.cpp +++ b/protocols/Telegram/tdlib/td/tdutils/test/pq.cpp @@ -1,29 +1,24 @@ // -// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2018 +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // #include "td/utils/tests.h" +#include "td/utils/algorithm.h" #include "td/utils/BigNum.h" #include "td/utils/common.h" #include "td/utils/crypto.h" #include "td/utils/format.h" #include "td/utils/logging.h" -#include "td/utils/misc.h" +#include "td/utils/SliceBuilder.h" -#include <algorithm> #include <limits> #include <utility> -REGISTER_TESTS(pq) - -using namespace td; - -#if TD_HAVE_OPENSSL -static bool is_prime(uint64 x) { - for (uint64 d = 2; d < x && d * d <= x; d++) { +static bool is_prime(td::uint64 x) { + for (td::uint64 d = 2; d < x && d * d <= x; d++) { if (x % d == 0) { return false; } @@ -31,9 +26,9 @@ static bool is_prime(uint64 x) { return true; } -static std::vector<uint64> gen_primes(uint64 L, uint64 R, int limit = 0) { - std::vector<uint64> res; - for (auto x = L; x <= R && (limit <= 0 || res.size() < static_cast<std::size_t>(limit)); x++) { +static td::vector<td::uint64> gen_primes(td::uint64 L, td::uint64 R, std::size_t limit = 0) { + td::vector<td::uint64> res; + for (auto x = L; x <= R && (limit <= 0 || res.size() < limit); x++) { if (is_prime(x)) { res.push_back(x); } @@ -41,22 +36,26 @@ static std::vector<uint64> gen_primes(uint64 L, uint64 R, int limit = 0) { return res; } -static std::vector<uint64> gen_primes() { - std::vector<uint64> result; - append(result, gen_primes(1, 100)); - append(result, gen_primes((1ull << 31) - 500000, std::numeric_limits<uint64>::max(), 5)); - append(result, gen_primes((1ull << 32) - 500000, std::numeric_limits<uint64>::max(), 5)); - append(result, gen_primes((1ull << 39) - 500000, std::numeric_limits<uint64>::max(), 1)); +static td::vector<td::uint64> gen_primes(int mode) { + td::vector<td::uint64> result; + if (mode == 1) { + for (size_t i = 10; i <= 19; i++) { + td::append(result, gen_primes(i * 100000000, (i + 1) * 100000000, 1)); + } + } else { + td::append(result, gen_primes(1, 100)); + td::append(result, gen_primes((1ull << 31) - 500000, std::numeric_limits<td::uint64>::max(), 5)); + td::append(result, gen_primes((1ull << 32) - 500000, std::numeric_limits<td::uint64>::max(), 2)); + td::append(result, gen_primes((1ull << 39) - 500000, std::numeric_limits<td::uint64>::max(), 1)); + } return result; } -using PqQuery = std::pair<uint64, uint64>; -static bool cmp(const PqQuery &a, const PqQuery &b) { - return a.first * a.second < b.first * b.second; -} -static std::vector<PqQuery> gen_pq_queries() { - std::vector<PqQuery> res; - auto primes = gen_primes(); +using PqQuery = std::pair<td::uint64, td::uint64>; + +static td::vector<PqQuery> gen_pq_queries(int mode = 0) { + td::vector<PqQuery> res; + auto primes = gen_primes(mode); for (auto q : primes) { for (auto p : primes) { if (p > q) { @@ -65,28 +64,56 @@ static std::vector<PqQuery> gen_pq_queries() { res.emplace_back(p, q); } } - std::sort(res.begin(), res.end(), cmp); return res; } -static void test_pq(uint64 first, uint64 second) { - BigNum p = BigNum::from_decimal(PSLICE() << first); - BigNum q = BigNum::from_decimal(PSLICE() << second); +static td::string to_binary(td::uint64 x) { + td::string result; + do { + result = static_cast<char>(x & 255) + result; + x >>= 8; + } while (x > 0); + return result; +} + +static void test_pq_fast(td::uint64 first, td::uint64 second) { + if ((static_cast<td::uint64>(1) << 63) / first <= second) { + return; + } + + td::string p_str; + td::string q_str; + int err = td::pq_factorize(to_binary(first * second), &p_str, &q_str); + ASSERT_EQ(err, 0); + + ASSERT_STREQ(p_str, to_binary(first)); + ASSERT_STREQ(q_str, to_binary(second)); +} + +#if TD_HAVE_OPENSSL +static void test_pq_slow(td::uint64 first, td::uint64 second) { + if ((static_cast<td::uint64>(1) << 63) / first > second) { + return; + } + + td::BigNum p = td::BigNum::from_decimal(PSLICE() << first).move_as_ok(); + td::BigNum q = td::BigNum::from_decimal(PSLICE() << second).move_as_ok(); - BigNum pq; - BigNumContext context; - BigNum::mul(pq, p, q, context); - std::string pq_str = pq.to_binary(); + td::BigNum pq; + td::BigNumContext context; + td::BigNum::mul(pq, p, q, context); + td::string pq_str = pq.to_binary(); - std::string p_str, q_str; + td::string p_str; + td::string q_str; int err = td::pq_factorize(pq_str, &p_str, &q_str); - CHECK(err == 0) << first << " * " << second; + LOG_CHECK(err == 0) << first << " * " << second; - BigNum p_res = BigNum::from_binary(p_str); - BigNum q_res = BigNum::from_binary(q_str); + td::BigNum p_res = td::BigNum::from_binary(p_str); + td::BigNum q_res = td::BigNum::from_binary(q_str); - CHECK(p_str == p.to_binary()) << td::tag("got", p_res.to_decimal()) << td::tag("expected", first); - CHECK(q_str == q.to_binary()) << td::tag("got", q_res.to_decimal()) << td::tag("expected", second); + LOG_CHECK(p_str == p.to_binary()) << td::tag("got", p_res.to_decimal()) << td::tag("expected", first); + LOG_CHECK(q_str == q.to_binary()) << td::tag("got", q_res.to_decimal()) << td::tag("expected", second); } #endif @@ -101,18 +128,35 @@ TEST(CryptoPQ, hands) { ASSERT_EQ(179424611ull, td::pq_factorize(179424611ull * 179424673ull)); #if TD_HAVE_OPENSSL - test_pq(4294467311, 4294467449); + test_pq_slow(4294467311, 4294467449); #endif } -#if TD_HAVE_OPENSSL -TEST(CryptoPQ, generated_slow) { +TEST(CryptoPQ, four) { for (int i = 0; i < 100000; i++) { - test_pq(2, 2); + test_pq_fast(2, 2); + } +} + +TEST(CryptoPQ, generated_fast) { + auto queries = gen_pq_queries(); + for (const auto &query : queries) { + test_pq_fast(query.first, query.second); } +} + +TEST(CryptoPQ, generated_server) { + auto queries = gen_pq_queries(1); + for (const auto &query : queries) { + test_pq_fast(query.first, query.second); + } +} + +#if TD_HAVE_OPENSSL +TEST(CryptoPQ, generated_slow) { auto queries = gen_pq_queries(); - for (auto query : queries) { - test_pq(query.first, query.second); + for (const auto &query : queries) { + test_pq_slow(query.first, query.second); } } -#endif
\ No newline at end of file +#endif diff --git a/protocols/Telegram/tdlib/td/tdutils/test/variant.cpp b/protocols/Telegram/tdlib/td/tdutils/test/variant.cpp index 5c5e18d1d8..755acdfa98 100644 --- a/protocols/Telegram/tdlib/td/tdutils/test/variant.cpp +++ b/protocols/Telegram/tdlib/td/tdutils/test/variant.cpp @@ -1,5 +1,5 @@ // -// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2018 +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) @@ -9,22 +9,18 @@ #include "td/utils/tests.h" #include "td/utils/Variant.h" -REGISTER_TESTS(variant); - -using namespace td; - static const size_t BUF_SIZE = 1024 * 1024; static char buf[BUF_SIZE], buf2[BUF_SIZE]; -static StringBuilder sb(MutableSlice(buf, BUF_SIZE - 1)); -static StringBuilder sb2(MutableSlice(buf2, BUF_SIZE - 1)); +static td::StringBuilder sb(td::MutableSlice(buf, BUF_SIZE - 1)); +static td::StringBuilder sb2(td::MutableSlice(buf2, BUF_SIZE - 1)); -static std::string move_sb() { +static td::string move_sb() { auto res = sb.as_cslice().str(); sb.clear(); return res; } -static std::string name(int id) { +static td::string name(int id) { if (id == 1) { return "A"; } @@ -58,18 +54,18 @@ using C = Class<3>; TEST(Variant, simple) { { - Variant<std::unique_ptr<A>, std::unique_ptr<B>, std::unique_ptr<C>> abc; + td::Variant<td::unique_ptr<A>, td::unique_ptr<B>, td::unique_ptr<C>> abc; ASSERT_STREQ("", sb.as_cslice()); - abc = std::make_unique<A>(); + abc = td::make_unique<A>(); ASSERT_STREQ("+A", sb.as_cslice()); sb.clear(); - abc = std::make_unique<B>(); + abc = td::make_unique<B>(); ASSERT_STREQ("+B-A", sb.as_cslice()); sb.clear(); - abc = std::make_unique<C>(); + abc = td::make_unique<C>(); ASSERT_STREQ("+C-B", sb.as_cslice()); sb.clear(); } ASSERT_STREQ("-C", move_sb()); sb.clear(); -}; +} |