slightly nudge choices towards less sequences

also slightly improve some strange detrimental corner cases.

Merge branch 'dev' into staticDictCost

Merge pull request #1149 from terrelln/fuzz-py

Small fixes to fuzz.py

Improve compiler detection to work on Mac

Define BIT_DEBUG for --debug

Increase the maximum file size

Small fixes to fuzz.py

Merge pull request #1150 from facebook/fracFse

fix corner case when requiring cost of an FSE symbol

Merge branch 'dev' into fracFse

fix corner case when requiring cost of an FSE symbol

ensure that, when frequency[symbol]==0,
result is (tableLog + 1) bits
with both upper-bit and fractional-bit estimates.

Also : enable BIT_DEBUG in /tests

Merge pull request #1117 from felixhandte/zstd-fast-in-place-dict

ZSTD_fast: Support Searching the Dictionary Context In-Place

Work around bug in zstd decoder (#1147)

Work around bug in zstd decoder

Pull request #1144 exercised a new path in the zstd decoder that proved to
be buggy. Avoid the extremely rare bug by emitting an uncompressed block.

Merge pull request #1146 from terrelln/fse-fix

[zstd] Fix decompression edge case

Variable declarations

Assert that Dict and Current Window are Adjacent in Index Space

Make loadedDictEnd an Index, not the Dict Len

Fixes in re Comments

Don't Attach Empty Dict Contents

In weird corner cases, they produce unexpected results...

Avoid Undefined Behavior in Match Ptr Calculation

Remove Out-of-Date Comment

Moar Renames

Also Attach Dict When Source Size is Unknown

Clear the Dictionary When Sliding the Window

Refine ip Initialization to Avoid ARM Weirdness

Use New Index Invariant to Simplify Conditionals

Force Working Context Indices Greater than Dict Indices

Whitespace Fix

Switch to Original Match Calc for noDict Repcode Check

Rename 'hasDict' to 'dictMode'

Respond to PR Comments; Formatting/Style/Lint Fixes

Rename and Reformat

Change Cut-Off to 8 KB

Fix Rep Code Initialization

Coalesce hasDictMatchState and extDict Checks into One Enum and Rename Stuff

Split Wrapper Functions to Cause Inlining

Add bounds check in repcode tests

Initial Repcode Check Support for Ext Dict Ctx

Preliminary Support in ZSTD_compressBlock_fast_generic() for Ext Dict Ctx

Refer to the Dictionary Match State In-Place (Sometimes)

Error if reported size is too large in edge case

[zstd] Fix decompression edge case

This edge case is only possible with the new optimal encoding selector,
since before zstd would always choose `set_basic` for small numbers of
sequences.

Fix `FSE_readNCount()` to support buffers < 4 bytes.

Credit to OSS-Fuzz

Merge pull request #1144 from terrelln/fse-entropy

Approximate FSE encoding costs for selection

Merge pull request #1145 from terrelln/spec

Clarify what happens when Number_of_Sequences == 0

Clarify what happens when Number_of_Sequences == 0

Fixes

Merge branch 'dev' into staticDictCost

disable 2-passes strategy

Approximate FSE encoding costs for selection

Estimate the cost for using FSE modes `set_basic`, `set_compressed`, and
`set_repeat`, and select the one with the lowest cost.

* The cost of `set_basic` is computed using the cross-entropy cost
  function `ZSTD_crossEntropyCost()`, using the normalized default count
  and the count.
* The cost of `set_repeat` is computed using `FSE_bitCost()`. We check the
  previous table to see if it is able to represent the distribution.
* The cost of `set_compressed` is computed with the entropy cost function
  `ZSTD_entropyCost()`, together with the cost of writing the normalized
  count `ZSTD_NCountCost()`.

Merge pull request #1143 from facebook/tableLevels

Update table of compression levels

Merge branch 'tableLevels' of github.com:facebook/zstd into tableLevels

Merge branch 'dev' into tableLevels

Merge pull request #1142 from terrelln/better-dict

[cover] Small compression ratio improvement

Merge branch 'dev' into tableLevels

updated compression levels for blocks of 256KB

[cover] Small compression ratio improvement

The cover algorithm selects one segment per epoch, and it selects the epoch
size such that `epochs * segmentSize ~= dictSize`. Selecting less epochs
gives the algorithm more candidates to choose from for each segment it
selects, and then it will loop back to the first epoch when it hits the
last one.

The trade off is that now it takes longer to select each segment, since it
has to look at more data before making a choice.

I benchmarked on the following data sets using this command:

```sh
$ZSTD -T0 -3 --train-cover=d=8,steps=256 $DIR -r -o dict && $ZSTD -3 -D dict -rc $DIR | wc -c
```

| Data set     | k (approx) |  Before  |  After   | % difference |
|--------------|------------|----------|----------|--------------|
| GitHub       | ~1000      |   738138 |   746610 |       +1.14% |
| hg-changelog | ~90        |  4295156 |  4285336 |       -0.23% |
| hg-commands  | ~500       |  1095580 |  1079814 |       -1.44% |
| hg-manifest  | ~400       | 16559892 | 16504346 |       -0.34% |

There is some noise in the measurements, since small changes to `k` can
have large differences, which is why I'm using `steps=256`, to try to
minimize the noise. However, the GitHub data set still has some noise.

If I run the GitHub data set on my Mac, which presumably lists directory
entries in a different order, so the dictionary builder sees the files in
a different order, or I use `steps=1024` I see these results.

| Run        | Before | After  | % difference |
|------------|--------|--------|--------------|
| steps=1024 | 738138 | 734470 |       -0.50% |
| MacBook    | 738451 | 737132 |       -0.18% |

Question: Should we expose this as a parameter? I don't think it is
necessary. Someone might want to turn it up to exchange a much longer
dictionary building time in exchange for a slightly better dictionary.
I tested `2`, `4`, and `16`, and `4` got most of the benefit of `16`
with a faster running time.

Merge branch 'dev' into staticDictCost

adding some debug functions to observe statistics

Merge pull request #1139 from fbrosson/prefetch

__builtin_prefetch did probably not exist before gcc 3.1.

__builtin_prefetch did probably not exist before gcc 3.1.

Merge pull request #1140 from fbrosson/cpu-asm

Drop colon in asm snippet to make old versions of gcc happy.

Drop colon in asm snippet to make old versions of gcc happy.

fixed minor conversion warning

fixed a pretty complex bug when combining ldm + btultra

collect statistics for first block in ultra mode

this patch makes btultra do 2 passes on the first block,
the first one being dedicated to collecting statistics
so that the 2nd pass is more accurate.

It translates into a very small compression ratio gain :

enwik7, level 20:
blocks  4K : 2.142 -> 2.153
blocks 16K : 2.447 -> 2.457
blocks 64K : 2.716 -> 2.726

On the other hand, the cpu cost is doubled.

The trade off looks bad.
Though, that's ultimately a price to pay to reach better compression ratio.
So it's only enabled when setting btultra.

slightly improved weight calculation

translating into a tiny compression ratio improvement

update table levels for blocks <= 16K

also : allow hlog to be slighly larger than windowlog,
as it's apparently good for both speed and compression ratio.

introduced bit-fractional cost evaluation

this improves compression ratio by a *tiny* amount.
It also reduces speed by a small amount.

Consequently, bit-fractional evaluation is only turned on for btultra.

Merge pull request #1135 from facebook/frameCSize

decompress: changed error code when input is too large

Merge pull request #1136 from terrelln/fix

Fix failing Travis tests

Fix failing Travis tests

Merge branch 'dev' into staticDictCost

opt: removed static prices

after testing, it's actually always better to use dynamic prices
albeit initialised from dictionary.

Merge pull request #1127 from facebook/staticDictCost

Improved optimal parser with dictionary

decompress: changed error code when input is too large

ZSTD_decompress() can decompress multiple frames sent as a single input.
But the input size must be the exact sum of all compressed frames, no more.

In the case of a mistake on srcSize, being larger than required,
ZSTD_decompress() will try to decompress a new frame after current one, and fail.
As a consequence, it will issue an error code, ERROR(prefix_unknown).

While the error is technically correct
(the decoder could not recognise the header of _next_ frame),
it's confusing, as users will believe that the first header of the first frame is wrong,
which is not the case (it's correct).
It makes it more difficult to understand that the error is in the source size, which is too large.

This patch changes the error code provided in such a scenario.
If (at least) a first frame was successfully decoded,
and then following bytes are garbage values,
the decoder assumes the provided input size is wrong (too large),
and issue the error code ERROR(srcSize_wrong).

Merge branch 'dev' into tableLevels

Merge pull request #1131 from facebook/zstdcli

minor: control numeric argument overflow

Merge pull request #1130 from facebook/man

fix #1115

Merge pull request #1129 from facebook/paramgrill

Paramgrill refactoring

Merge branch 'dev' into tableLevels

Merge pull request #1133 from felixhandte/travis-fix

Make Travis CI Run `apt-get update`

Travis CI Runs apt-get Update

paramgrill: use NB_LEVELS_TRACKED in loop

make it easier to generate/track more levels
than ZSTD_maxClevel()

update table for 128 KB blocks

update compression levels for large inputs

cli: control numeric argument overflow

exit on overflow
backported from paramgrill
added associated test case

minor : factor out errorOut()

fix #1115

paramgrill: subtle change in level spacing

distance between levels is slightly increased
to compensate for level 1 speed improvements
and the will to have stronger level 19
extending the range of speed to cover.

added programmable constraints

generalized use of readU32FromChar()

and check input overflow

replaced FSE_count by FSE_count_simple

to reduce usage of stack memory.

Also : tweaked a few comments, as suggested by @terrelln

Merge pull request #1128 from facebook/libdir

minor Makefile patch

minor patch, ensuring LIBDIR is created before installation

follow-up from #1123

fixed wrong assertion

base can actually overflow

fixed c++ conversion warning

minor adjusting of weights

opt: init statistics from dictionary

instead of starting from fake "default" statistics.

btopt : minor adjustment of update frequencies

Merge pull request #1123 from baruchsiach/fix-install-pc

lib/Makefile: create include directory before headers installation

opt: minor improvements to log traces

slight improvement when using fractional-bit evaluation (opt:dictionay)