##// END OF EJS Templates
encoding: fix trim() to be O(n) instead of O(n^2)...
encoding: fix trim() to be O(n) instead of O(n^2) `encoding.trim()` iterated over the possible lengths smaller than the input and created a slice for each. It then calculated the column width of the result, which is of course O(n), so the overall algorithm was O(n). This patch rewrites it to iterate over the unicode characters, keeping track of the length so far. Also, the old algorithm started from the end of the string, which made it much worse when the input is large and the limit is small (such as the typical 72 we pass to it). You can time it by running something like this: ``` time python3 -c 'from mercurial.utils import stringutil; print(stringutil.ellipsis(b"0123456789" * 1000, 5))' ``` That drops from 4.05 s to 83 ms with this patch (and most of that is of course startup time). Differential Revision: https://phab.mercurial-scm.org/D12089

File last commit:

r44253:01ec70a8 default
r49518:f1ed5c30 default
Show More
standalone_fuzz_target_runner.cc
45 lines | 1.5 KiB | text/x-c | CppLexer
/ contrib / fuzz / standalone_fuzz_target_runner.cc
// Copyright 2017 Google Inc. All Rights Reserved.
// Licensed under the Apache License, Version 2.0 (the "License");
// Example of a standalone runner for "fuzz targets".
// It reads all files passed as parameters and feeds their contents
// one by one into the fuzz target (LLVMFuzzerTestOneInput).
// This runner does not do any fuzzing, but allows us to run the fuzz target
// on the test corpus (e.g. "do_stuff_test_data") or on a single file,
// e.g. the one that comes from a bug report.
#include <cassert>
#include <fstream>
#include <iostream>
#include <vector>
// Forward declare the "fuzz target" interface.
// We deliberately keep this inteface simple and header-free.
extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size);
extern "C" int LLVMFuzzerInitialize(int *argc, char ***argv);
int main(int argc, char **argv)
{
LLVMFuzzerInitialize(&argc, &argv);
for (int i = 1; i < argc; i++) {
std::ifstream in(argv[i]);
in.seekg(0, in.end);
size_t length = in.tellg();
in.seekg(0, in.beg);
std::cout << "Reading " << length << " bytes from " << argv[i]
<< std::endl;
// Allocate exactly length bytes so that we reliably catch
// buffer overflows.
std::vector<char> bytes(length);
in.read(bytes.data(), bytes.size());
assert(in);
LLVMFuzzerTestOneInput(
reinterpret_cast<const uint8_t *>(bytes.data()),
bytes.size());
std::cout << "Execution successful" << std::endl;
}
return 0;
}
// no-check-code since this is from a third party