Fix a possible NPE

String.valueOf is an overloaded and the compiler unfortunately picks
the wrong one since null contains no type information.

Change-Id: Icd197eaa046421f3cfcc5bf3e7601dc5bc7486b6
Mark DeltaWindowEntry methods final

This class and all of its methods are only package visible.
Clarify the methods as final for the benefit of the JIT to
inline trivial code.

Change-Id: I078841f9900dbf299fbe6abf2599f0208ae96856
Micro-optimize DeltaWindow maxMemory test to be != 0

Instead of using a compare-with-0 use a does not equal 0.
javac bytecode has a special instruction for this, as it
is very common in software. We can assume the JIT knows
how to efficiently translate the opcode to machine code,
and processors can do != 0 very quickly.

Change-Id: Idb84c1d744d2874517fd4bfa1db390e2dbf64eac
Micro-optimize DeltaWindow primary loop

javac and the JIT are more likely to understand a boolean being
used as a branch conditional than comparing int against 0 and 1.
Rewrite NEXT_RES and NEXT_SRC constants to be booleans so the
code is clarified for the JIT.

Change-Id: I1bdd8b587a69572975a84609c779b9ebf877b85d
Micro-optimize copy instructions in DeltaEncoder

The copy instruction formatter should not to compute the shifts and
masks twice.  Instead compute them once and assume there is a register
available to store the temporary "b" for compare with 0.

Change-Id: Ic7826f29dca67b16903d8f790bdf785eb478c10d
Replace DeltaWindow array with circularly linked list

Typical window sizes are 10 and 250 (although others are accepted).
In either case the pointer overhead of 1 pointer in an array or
2 pointers for a double linked list is trivial.  A doubly linked
list as used here for window=250 is only another 1024 bytes on a
32 bit machine, or 2048 bytes on a 64 bit machine.

The critical search loops scan through the array in either the
previous direction or the next direction until the cycle is finished,
or some other scan abort condition is reached.  Loading the next
object's pointer from a field in the current object avoids the
branch required to test for wrapping around the edge of the array.
It also saves the array bounds check on each access.

When a delta is chosen the window is shuffled to hoist the currently
selected base as an earlier candidate for the next object. Moving
the window entry is easier in a double-linked list than sliding a
group of array entries.

Change-Id: I9ccf20c3362a78678aede0f0f2cda165e509adff
Remove DFS locality ordering during packing

PackWriter generally chooses the order for objects when it builds the
object lists.  This ordering already depends on history information to
guide placing more recent objects first and historical objects last.

Allow PackWriter to make the basic ordering decisions, instead of
trying to override them.  The old approach of sorting the list caused
DfsReader to override any ordering change PackWriter might have tried
to make when repacking a repository.

This now better matches with WindowCursor's implementation, where
PackWriter solely determines the object ordering.

Change-Id: Ic17ab5631ec539f0758b962966c3a1823735b814
Split remaining delta work on path boundaries

When an idle thread tries to steal work from a sibling's remaining
toSearch queue, always try to split along a path boundary. This
avoids missing delta opportunities in the current window of the
thread whose work is being taken.

The search order is reversed to walk further down the chain from
current position, avoiding the risk of splitting the list within
the path the thread is currently processing.

When selecting which thread to split from use an accurate estimate
of the size to be taken. This avoids selecting a thread that has
only one path remaining but may contain more pending entries than
another thread with several paths remaining.

As there is now a race condition where the straggling thread can
start the next path before the split can finish, the stealWork()
loop spins until it is able to acquire a split or there is only
one path remaining in the siblings.

Change-Id: Ib11ff99f90a4d9efab24bf4a85342cc63203dba5
Correct distribution of allowed delta size along chain length

Nicolas Pitre discovered a very simple rule for selecting between two
different delta base candidates:

  - if based whole object, must be <= 50% of target
  - if at end of a chain, must be <= 1/depth * 50% of target

The rule penalizes deltas near the end of the chain, requiring them to
be very small in order to be kept by the packer.  This favors deltas
that are based on a shorter chain, where the read-time unpack cost is
much lower.  Fewer bytes need to be consulted from the source pack
file, and less copying is required in memory to rebuild the object.

Junio Hamano explained Nico's rule to me today, and this commit fixes
DeltaWindow to implement it as described.

When no base has been chosen the computation is simply the statements
denoted above.  However once a base with depth of 9 has been chosen
(e.g.  when pack.depth is limited to 10), a non-delta source may
create a new delta that is up to 10x larger than the already selected
base.  This reflects the intent of Nico's size distribution rule no
matter what order objects are visited in the DeltaWindow.

With this patch and my other patches applied, repacking JGit with:

  [pack]
    reuseObjects = false
    reuseDeltas = false
    depth = 50
    window = 250
    threads = 4
    compression = 9

  CGit (all) 5,711,735 bytes; real 0m13.942s user 0m47.722s [1]
  JGit heads 5,718,295 bytes; real 0m11.880s user 0m38.177s [2]
       rest      9,809 bytes

The improved JGit result for the head pack is only 6.4 KiB larger than
CGit's resulting pack.  This patch allowed JGit to find an additional
39.7 KiB worth of space savings.  JGit now also often runs 2s faster
than CGit, despite also creating bitmaps and pruning objects after the
head pack creation.

[1] time git repack -a -d -F --window=250 --depth=50
[2] time java -Xmx128m -jar jgit debug-gc

Change-Id: I5caec31359bf7248cabdd2a3254c84d4ee3cd96b
Avoid TemporaryBuffer.Heap on very small deltas

TemporaryBuffer is great when the output size is not known, but must
be bound by a relatively large upper limit that fits in memory, e.g.
64 KiB or 20 MiB.  The buffer gracefully supports growing storage by
allocating 8 KiB blocks and storing them in an ArrayList.

In a Git repository many deltas are less than 8 KiB.  Typical tree
objects are well below this threshold, and their deltas must be
encoded even smaller.

For these much smaller cases avoid the 8 KiB minimum allocation used
by TemporaryBuffer.  Instead allocate a very small OutputStream
writing to an array that is sized at the limit.

Change-Id: Ie25c6d3a8cf4604e0f8cd9a3b5b701a592d6ffca
Always attempt delta compression when reuseDeltas is false

If reuseObjects=true but reuseDeltas=false the caller wants attempt
a delta for every object in the input list. Test for reuseDeltas
to ensure every object passes through the searchInWindow() method.

If no delta is possible for an object and it will be stored whole
(non-delta format), PackWriter may still reuse its content from any
source pack. This avoids an inflate()-deflate() cycle to recompress
the object contents.

Change-Id: I845caeded419ef4551ef1c85787dd5ffd73235d9
Merge changes I845caede,Ie25c6d3a,I5caec313,Ib11ff99f,I9ccf20c3,Ic7826f29,I1bdd8b58,Idb84c1d7,I078841f9

* changes:
  Always attempt delta compression when reuseDeltas is false
  Avoid TemporaryBuffer.Heap on very small deltas
  Correct distribution of allowed delta size along chain length
  Split remaining delta work on path boundaries
  Replace DeltaWindow array with circularly linked list
  Micro-optimize copy instructions in DeltaEncoder
  Micro-optimize DeltaWindow primary loop
  Micro-optimize DeltaWindow maxMemory test to be != 0
  Mark DeltaWindowEntry methods final
Merge "Fix a possible NPE"
NLS warning cleanup

Change-Id: Ia76aa02dd330a1f88096c2b059b363aa38d653e9
Fix boundary conditions in AutoCRLFOutputStream

This fixes some problems with inputs around the size of the internal
buffer in AutoCRLFOutputStream (8000).

Tests supplied by Robin Stocker.

Bug: 405672
Change-Id: I6147897290392b3bfd4040e8006da39c302a3d49
Update PackBitmapIndexRemapper to handle mappings not in the new pack.

Previously, the code assumed all commits in the old pack would also
be present in the new pack. This assumption caused an
ArrayIndexOutOfBoundsException during remapping of ids. Fix the
iterator to only return entries that may be remapped. Furthermore,
update getBitmap() to return null if commit does not exist in the
new pack.

Change-Id: I065babe8cd39a7654c916bd01c7012135733dddf
Fix WWW-Authenticate headers of an HTTP response processing.

The original code was able to process only one WWW-Authenticate
header in an HTTP response, and if this header was not one of
two expected, authentication failed regardless of that there
could be other headers in the response.

All WWW-Authenticate headers in an HTTP response have to be
browsed to find one of supported, i.e. Basic or Digest.
By that if both are present, the Digest one should be used
as more preferable.

Bug: 357719