Unfortunately, neither the `memmem` nor the `strnstr` functions are part of any C standard but are merely extensions of C that are implemented by e.g. glibc. Thus, there is no standardized way to search for a string in a block of memory with a limited size, and using `strstr` is to be considered unsafe in case where the buffer has not been sanitized. In fact, there are some uses of `strstr` in exactly that unsafe way in our codebase. Provide a new function `git__memmem` that implements the `memmem` semantics. That is in a given haystack of `n` bytes, search for the occurrence of a byte sequence of `m` bytes and return a pointer to the first occurrence. The implementation chosen is the "Not So Naive" algorithm from [1]. It was chosen as the implementation is comparably simple while still being reasonably efficient in most cases. Preprocessing happens in constant time and space, searching has a time complexity of O(n*m) with a slightly sub-linear average case. [1]: http://www-igm.univ-mlv.fr/~lecroq/string/
Name |
Last commit
|
Last update |
---|---|---|
.github | Loading commit data... | |
ci | Loading commit data... | |
cmake/Modules | Loading commit data... | |
deps | Loading commit data... | |
docs | Loading commit data... | |
examples | Loading commit data... | |
fuzzers | Loading commit data... | |
include | Loading commit data... | |
script | Loading commit data... | |
src | Loading commit data... | |
tests | Loading commit data... | |
.HEADER | Loading commit data... | |
.editorconfig | Loading commit data... | |
.gitattributes | Loading commit data... | |
.gitignore | Loading commit data... | |
.mailmap | Loading commit data... | |
AUTHORS | Loading commit data... | |
CMakeLists.txt | Loading commit data... | |
COPYING | Loading commit data... | |
README.md | Loading commit data... | |
api.docurium | Loading commit data... | |
azure-pipelines.yml | Loading commit data... | |
git.git-authors | Loading commit data... | |
libgit2.pc.in | Loading commit data... | |
libgit2_clar.supp | Loading commit data... | |
package.json | Loading commit data... |