1. 25 Oct, 2018 1 commit
    • util: provide `git__memmem` function · 83e8a6b3
      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/
      Patrick Steinhardt committed