|
7de70dbc
|
2015-08-11T11:09:04
|
|
Add missing <stdlib.h> to streams.cc
|
|
17ed2589
|
2015-08-10T13:13:58
|
|
msan bugfixes to the brotli encoder
|
|
|
29c26795
|
2015-07-30T17:42:02
|
|
Fix encoder bug.
Under some circumstances CopyLiteralsToByteArray tried
to read begind ringbuffer.
In this patch we force it to read completely from range [0..mask]
|
|
|
95ddb48a
|
2015-06-29T14:20:25
|
|
Fix some VS compilation errors in the encoder.
- Use std::numeric_limits<double>::infinity() instead of 1.0 / 0.0
- Use FastLog2() instead of log2() in cost model
|
|
|
bad0f4ed
|
2015-06-26T17:37:00
|
|
Brotli Bug Fixes
|
|
|
618287b3
|
2015-06-12T16:50:49
|
|
Deprecate greedy_block_split and enable_context_modeling brotli params.
These affected only quality 11, and now it does not make sense
to disable block splitting or context modeling because most of
the time is spent in zopfli anyway.
Now all speed vs size compromises are controlled by the quality param.
|
|
|
66098830
|
2015-06-12T16:45:17
|
|
Use a static hash table to look up dictionary words and transforms.
This is used for quality 11, for qualities <= 9 we already
have a simpler hash table.
The static data size is 252 kB, and this removes the
need to initialize a huge hash map at startup, which was
the reason why transforms had to be disabled by default.
In comparison, the static dictionary itself is 120 kB.
This supports every transform, except the kOmitFirstN.
|
|
|
b3d3723f
|
2015-06-12T16:25:41
|
|
Add "zopfli"-style backward reference search to brotli.
This commit adopts the backward reference search algorithm
from the zopfli project (see https://github.com/google/zopfli)
to brotli.
This slower backward reference search is run only in quality 11
and it runs two iterations of entropy cost modeling and
shortest path search.
As a result, the original backward reference search function can
be simplified a bit, since we can remove some heuristics that were
replaced with the zopfli-style search.
|
|
|
835a7746
|
2015-06-12T16:14:06
|
|
Change the static dictionary hash table to take into
account word frequency when there are hash collisions.
|
|
|
65f3fc55
|
2015-06-12T16:11:50
|
|
Bug fixes for the brotli encoder.
* Fix an out-of-bounds access to depth_histo in the
bit cost calculation function.
* Change type of distance symbol to uint16_t in block
splitter, because if all postfix bits are used, there
can be 520 distance symbols.
* Save the distance cache between meta-blocks at the
correct place. This fixes a roundtrip failure that
can occur when there is an uncompressed metablock
between two compressed metablocks.
* Fix a bug when setting lgwin to 24 in the encoder parameters
It ended up making metablocks larger than 24 bits in size.
* Fix out-of-bounds memory accesses in parallel encoder.
CreateBackwardReferences can read up to 4 bytes past end of
input if the end of input is before mask.
* Add missing header for memcpy() in port.h
|
|
|
b43df8f6
|
2015-06-12T15:43:54
|
|
Brotli custom LZ77 dictionary support.
Adds functions to prepend such dictionary to the
encoder and decoder, and twiddles their internal
parameters to do as if that was a previous part of
the input. This dictionary is just a prefilled LZ77
window, it is not related to the built in transformable
brotli dictionary.
|
|
|
667f70ad
|
2015-06-12T15:29:06
|
|
Speedups to brotli quality 11.
* Cluster at most 64 histograms at a time in the first
round of clustering.
* Use a faster histogram cost estimation function.
* Don't compute the log2(total) multiple times in the
block splitter.
|
|
|
6622355a
|
2015-05-11T14:11:07
|
|
Use the same hasher for text and font mode.
We use 4-byte hashing in both and look for length 3
matches separately.
|
|
|
cc8d64df
|
2015-05-11T13:51:47
|
|
Fix broken quality 0, make it same as quality 1.
|
|
|
aa853f3c
|
2015-05-11T11:33:19
|
|
Add a MODE_GENERIC compression mode to the interface.
With this the users can distinguish between not knowing
what the input is (ddefault) and knowing that it is text,
and thus can be relied on to force some UTF-8 specific settings.
|
|
|
54f69c9e
|
2015-05-07T17:44:33
|
|
Support window bits 10 - 15 in the decoder.
The previous window bit value 17 is used to
extend the range, since it has not been used
in any previous encoders.
|
|
|
12eb9bfd
|
2015-05-07T17:40:00
|
|
Align distance code meaning in the brotli encoder.
Two different definitions (offset by 1) were used in
command.h and hash.h. Now they have been made the same,
also consistent with the spec (e.g. 0 means use previous dist, etc...)
|
|
|
7cde616c
|
2015-05-07T17:30:10
|
|
Faster encoding for low quality settings.
With this commit, the encoder will skip some
compression optimization steps for quality <= 4,
which results in faster compression but higher
compressed sizes.
|
|
|
945b0d02
|
2015-05-07T17:23:07
|
|
Use a static context map with two buckets for UTF8 data.
Enabled for quality >= 4, and if there are no obvious
UTF8 violations detected.
For each block, we gather two separate histograms, one
for continuation bytes and one for ASCII or lead bytes.
|
|
|
83aa24dc
|
2015-05-07T16:53:43
|
|
Speed and memory usage improvements for the decoder.
* Change order of members of bit reader state structure.
* Remove unused includes for assert. Add BROTLI_DCHECK
macros and use it instead of assert.
* Do not calculate nbits in common case of ReadSymbol.
* Introduce and use PREDICT_TRUE / PREDICT_FALSE macros.
* Allocate less memory in the brotli decoder if it knows
the result size beforehand. Before this, the decoder
would always allocate 16MB if the encoder annotated the
window size as 22 bit (which is the default), even if the
file is only a few KB uncompressed. Now, it'll only
allocate a ringbuffer as large as needed for the result file.
But only if it can know the filesize, it's not possible
to know that if there are multiple metablocks or too large
uncompressed metablock.
|
|
|
0f726df1
|
2015-04-28T10:12:47
|
|
Don't do any block splitting for quality 1.
|
|
|
99af4df8
|
2015-04-23T16:43:38
|
|
Remove the 'override' keyword from ~BrotliFileIn().
Apparently MSVS 2010 does not support this.
|
|
|
98539223
|
2015-04-23T16:20:29
|
|
Remove quality parameter from bitstream writing functions.
Fix a few crashes related to some quality and param combinations.
|
|
|
fdfb1980
|
2015-04-23T15:52:32
|
|
Add a static hash table based dictionary lookup to fast brotli.
|
|
|
2fd80cdc
|
2015-04-23T15:43:37
|
|
Encoder support for new empty meta-block format.
Changed the parallel implementation to sync meta-blocks
to byte boundary by emitting empty meta-blocks.
|
|
|
6d80610f
|
2015-04-23T15:35:16
|
|
Fix entropy calculation.
|
|
|
3dbe2e03
|
2015-04-23T15:26:08
|
|
Encoder implementation using input/output classes.
Add a BrotliCompress() method to the public encoder API
that uses the BrotliIn and BrotliOut classes and use
that in the 'bro' command-line tool.
Use the streaming api in BrotliCompressBuffer() and
BrotliCompressor::WriteMetaBlock().
Use the appropiate hashers for quality <= 9.
|
|
|
09aa9ca4
|
2015-04-23T14:35:43
|
|
Add the streams.* files to Makefile and setup.py
|
|
|
6a530330
|
2015-04-23T14:29:01
|
|
Add input and output classes for streaming compression.
|
|
|
89a6fb85
|
2015-04-23T13:15:42
|
|
Add params to disable static dictionary and context modeling.
Disable all slow features for quality <= 9 (literal cost modeling,
dictionary, context modeling, advanced block splitting).
Change vector<Command> arguments of internal functions
to Command* and size_t.
|
|
|
e377e65f
|
2015-04-02T11:12:04
|
|
Limit the max input meta-block size to 16MB.
|
|
|
1428d541
|
2015-04-01T16:35:52
|
|
Proof-of-concept encoder for parallel compression.
Add a version of the brotli encoder that compresses
each meta-block independently, only using the
original input data from previous meta-blocks
and nothing from the compressor state.
This is a proof-of-concept to show that the
current format is flexible enough to support
parallel multi-threaded compression.
|
|
|
817a3edd
|
2015-04-01T16:29:04
|
|
Add an input block size parameter to brotli.
This will enable processing the input in smaller
chunks than the currently default 2MB for the
slow brotli, while still benefiting from the
larger sliding window.
|
|
|
d6d69ec4
|
2015-04-01T16:10:15
|
|
Add quality and lgwin to the BrotliParams.
Remove the hard-coded constants for window size
and meta-block size.
Initialize internal storage for each metablock
separately and reserve only as much as needed
for the actual input.
|
|
|
ca3a7a98
|
2015-03-30T13:41:52
|
|
Use FastLog2() instead of log() in BitsEntropy().
|
|
|
534654de
|
2015-03-27T14:20:35
|
|
Add a faster but less dense compression mode.
The new mode can be used by setting the greedy_block_split
field of BrotliParams to true.
This commit moves all the meta-block processing code
into its own library and moves the meta-block encoding
code to brotli_bit_stream.cc from encode.cc
|
|
|
497814ee
|
2015-03-24T10:18:06
|
|
Remove the redundant EncodeMetaBlockHeader() function.
Use Store{Compressed,Uncompressed}MetaBlockHeader() instead.
|
|
|
28135ea9
|
2015-02-27T16:53:00
|
|
Fix another use of log2() in literal_cost.cc
|
|
|
fab601e8
|
2015-02-27T16:04:43
|
|
Fix encoder compilation error on MSVS 2010.
As reported by @anthrotype, log2() is missing from MSVS 2010.
This patch uses log() and a multiplication in FastLog2()
for _MSV_VER <= 1600 and uses FastLog2() in literal_cost.cc
instead of log2().
|
|
|
f0b88cbc
|
2015-02-25T18:19:51
|
|
Fixes to the encoder to support visual studio.
Changes suggested by @r-lyeh and @anthrotype.
- Use a portable simple PRNG instead of rand_r()
- add missing <assert.h> include
- disambiguate log2() argument type
- remove endian.h include from write_bits.h
|
|
|
5bc56a17
|
2015-02-25T10:29:24
|
|
Fully qualify std::max_element, std::push_heap and std::pop_heap names.
|
|
|
e643328a
|
2015-02-25T10:24:13
|
|
Speed up FindMatchLength for non-x86 64-bit targets.
This CL enables 64-bit optimization for non-x86 target.
|
|
|
e1739826
|
2014-10-30T13:59:37
|
|
Add command-line tool and tests.
|
|
|
96d04e53
|
2014-10-29T15:39:35
|
|
Disable transforms in the encoder by default.
This change reduces the startup-time of the encoder considerably.
|
|
|
485ad82e
|
2014-10-28T14:05:53
|
|
Fix potential output buffer overflow in encoder.
|
|
|
0428f2d1
|
2014-10-28T13:47:21
|
|
Move the context map encoding function to the brotli_bit_stream library.
|
|
|
f321ba19
|
2014-10-28T13:36:21
|
|
Make the histogram clustering function more generic.
Change the template parameter to be the histogram class
instead of the alphabet size of the histogram.
|
|
|
b4f39bf5
|
2014-10-28T13:25:22
|
|
New version of the backward reference search code.
The new interface of the backward reference search
function makes it possible to use it in a streaming
manner.
Using the advanced cost model and static dictionary
can be turned on/off by template parameters.
The distance short codes are now computed as part of
the backward reference search.
Added a faster version of the Hasher.
|
|
|
03b20347
|
2014-10-28T12:50:33
|
|
Minor tuning of encoder heuristics.
|
|
|
ca8c2890
|
2014-10-28T12:09:18
|
|
Fix storing of the meta-block header for last empty meta-block.
|
|
|
467e6eef
|
2014-10-28T11:53:52
|
|
Move the block switch stroing functions to the brotli_bit_stream library.
|
|
|
39cde017
|
2014-10-15T14:14:34
|
|
Fix TODO markups.
|
|
|
d6d9fc60
|
2014-10-15T14:01:36
|
|
Factor out serialization functions into their own file.
Create a brotli_bit_stream library that is responsible for writing
various structures (headers, Huffman codes, etc.) directly into the
bit-stream.
|
|
|
12c6d1fb
|
2014-10-15T13:33:56
|
|
Apply const qualifier to call operator of comparator class.
|
|
|
fe6e9b01
|
2014-10-14T13:39:48
|
|
Remove broken Makefiles.
Makefiles will be added together with a command-line interface in a
later commit.
|
|
|
e8d668f8
|
2014-10-14T13:08:35
|
|
Add top-level README file.
Remove brotlispec.txt and add a link to the latest internet-draft instead.
|
|
|
3f655b63
|
2014-03-27T16:38:07
|
|
Fix buffer overflow bug in the brotli encoder.
|
|
|
34778194
|
2014-03-25T16:48:25
|
|
Update the dictionary and the transforms.
|
|
|
e7650080
|
2014-03-20T14:32:35
|
|
Updates to Brotli compression format, decoder and encoder
This commit contains a batch of changes that were made to the Brotli
compression algorithm in the last month. Most important changes:
* Format change: don't push distances representing static dictionary words to the distance cache.
* Fix decoder invalid memory access bug caused by building a non-complete Huffman tree.
* Add a mode parameter to the encoder interface.
* Use different hashers for text and font mode.
* Add a heuristics to the hasher for skipping non-compressible data.
* Exhaustive search of static dictionary during backward reference search.
|
|
|
2f268ad1
|
2014-02-17T14:25:36
|
|
Add the initial version of the static dictionary and transforms to Brotli.
|
|
|
0454ab4e
|
2014-02-14T15:04:23
|
|
Updates to Brotli compression format, decoder and encoder
This commit contains a batch of changes that were made to the Brotli
compression algorithm in the last month. Most important changes:
* Fixes to the spec.
* Change of code length code order.
* Use a 2-level Huffman lookup table in the decoder.
* Faster uncompressed meta-block decoding.
* Optimized encoding of the Huffman code.
* Detection of UTF-8 input encoding.
* UTF-8 based literal cost modeling for improved
backward reference selection.
|
|
|
2bcd58bb
|
2014-01-08T12:28:28
|
|
Brotli format change: small improvement to the encoding of Huffman codes
Combine the HSKIP and the simple/complex Huffman code type bits.
|
|
|
d762bc68
|
2014-01-06T16:01:57
|
|
Bug fixes for the brotli encoder and decoder.
|
|
|
1447345c
|
2013-12-17T17:17:57
|
|
Brotli format change: improved encoding of Huffman codes
This change removes the redundant HCLEN, HLENINC and HLEN
fields from the encoding of the complex Huffman codes and
derives these from an invariant of the code length sequence.
Based on a patch by Robert Obryk.
|
|
c23cb1e8
|
2013-12-12T10:43:05
|
|
Support for OSX build; tested using OSX 10.9/clang-500.2.79
|
|
|
60c24c0c
|
2013-12-12T13:18:04
|
|
Updates to Brotli compression format, decoder and encoder
This commit contains a batch of changes that were made to the Brotli
compression algorithm in the last month. Most important changes:
* Updated spec
* Changed Huffman code length alphabet to use run length codes more
efficiently, based on a suggestion by Robert Obryk
* Changed encoding of the number of Huffman code lengths (HLEN)
* Changed encoding of the number of Huffman trees (NTREES)
* Added support for uncompressed meta-blocks
|
|
|
8d7081f2
|
2013-11-28T17:37:13
|
|
Add draft specification of the brotli format
|
|
|
1cdcbd85
|
2013-11-19T14:32:56
|
|
Added Brotli compress/decompress utilities and makefiles
|
|
|
c6b9c7c5
|
2013-11-15T19:02:17
|
|
Updates to Brotli compression format, decoder and encoder
This commit contains a batch of changes that were made to the Brotli
compression algorithm in the last three weeks. Most important changes:
* Added UTF8 context model for good text compression.
* Simplified context modeling by having only 4 context modes.
* Per-block context mode selection.
* Faster backward copying and bit reading functions.
* More efficient histogram coding.
* Streaming support for the decoder and encoder.
|
|
|
c66e4e3e
|
2013-10-23T13:06:13
|
|
Add brotli compressor
This commit is for the encoder for brotli compression format.
Brotli is a generic byte-level compression algorithm.
|