add a flag to got_patch to reverse a patch before applying and the -R flag for `got patch'. ok stsp@

as a cheap optimization got-read-patch was sending only the "\ No newline at end of file" lines that follows an addition (a "+" line). To be able to reverse patches in the future got_patch needs to know about all of these lines instead. No functional changes intended. ok stsp@

reminded by and 'looks fine' to stsp@

this allow to apply patches from subdirectories of the work tree root. Prodded by naddy@, ok stsp@.

The SHA implementation is found portably across systems, so don't include sha1.h directly.

This needs to be explicitly installed.

Now that siphash is being looked for in a portable way, don't assume <siphash.h> as this is most likely not going to be the case on non-BSD systems.

Siphash is being used in place of murmurhash for object-id set as this is faster. However, this isn't really seen much in the non-BSD userspace, so provide an implementation for it portably, if one isn't found.

Saves us from doing a malloc/free call for every item on the list. ok op@

Siphash suggested by jrick as a better alternative to murmurhash for this use case. with small fixes from and ok op@

Apline doesn't like the use of cdefs.h

Add Alpine Linux to the list of CI checks. Alpine builds against muscl rather than glibc by default, and there's been a few compilation differenes to warrant having this distribution as a separate CI check.

The skip color marks boundary commits and their ancestors. Boundary commits are reachable both via references which we want to exclude from the pack, and via references which we want to include in the pack. We continue processing commit history up to the point we are left with only skip commits on the queue. This can speed up findtwixt() significantly and avoids wrong results produced by the old algorithm which made no distinction between "drop" and "skip". This idea was first implemented by Michael Forney for git9: https://git.9front.org/plan9front/plan9front/2e47badb88312c5c045a8042dc2ef80148e5ab47/commit.html Michael's log message for git9 is reproduced below: git/query: refactor graph painting algorithm (findtwixt, lca) We now keep track of 3 sets during traversal: - keep: commits we've reached from head commits - drop: commits we've reached from tail commits - skip: ancestors of commits in both 'keep' and 'drop' Commits in 'keep' and/or 'drop' may be added later to the 'skip' set if we discover later that they are part of a common subgraph of the head and tail commits. From these sets we can calculate the commits we are interested in: lca commits are those in 'keep' and 'drop', but not in 'skip'. findtwixt commits are those in 'keep', but not in 'drop' or 'skip'. The "LCA" commit returned is a common ancestor such that there are no other common ancestors that can reach that commit. Although there can be multiple commits that meet this criteria, where one is technically lower on the commit-graph than the other, these cases only happen in complex merge arrangements and any choice is likely a decent merge base. Repainting is now done in paint() directly. When we find a boundary commit, we switch our paint color to 'skip'. 'skip' painting does not stop when it hits another color; we continue until we are left with only 'skip' commits on the queue. This fixes several mishandled cases in the current algorithm: 1. If we hit the common subgraph from tail commits first (if the tail commit was newer than the head commit), we ended up traversing the entire commit graph. This is because we couldn't distinguish between 'drop' commits that were part of the common subgraph, and those that were still looking for it. 2. If we traversed through an initial part of the common subgraph from head commits before reaching it from tail commits, these commits were returned from findtwixt even though they were also reachable from tail commits. 3. In the same case as 2, we might end up choosing an incorrect commit as the LCA, which is an ancestor of the real LCA.