Mercurial > hg
changeset 30822:b54a2984cdd4
zstd: vendor python-zstandard 0.6.0
Commit 63c68d6f5fc8de4afd9bde81b13b537beb4e47e8 from
https://github.com/indygreg/python-zstandard is imported without
modifications (other than removing unwanted files).
This includes minor performance and feature improvements. It also
changes the vendored zstd library from 1.1.1 to 1.1.2.
# no-check-commit
line wrap: on
line diff
--- a/contrib/python-zstandard/MANIFEST.in Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/MANIFEST.in Sat Jan 14 19:41:43 2017 -0800 @@ -1,2 +1,5 @@ +graft c-ext graft zstd include make_cffi.py +include setup_zstd.py +include zstd.c
--- a/contrib/python-zstandard/NEWS.rst Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/NEWS.rst Sat Jan 14 19:41:43 2017 -0800 @@ -1,6 +1,33 @@ Version History =============== +0.6.0 (released 2017-01-14) +--------------------------- + +* Support for legacy zstd protocols (build time opt in feature). +* Automation improvements to test against Python 3.6, latest versions + of Tox, more deterministic AppVeyor behavior. +* CFFI "parser" improved to use a compiler preprocessor instead of rewriting + source code manually. +* Vendored version of zstd updated to 1.1.2. +* Documentation improvements. +* Introduce a bench.py script for performing (crude) benchmarks. +* ZSTD_CCtx instances are now reused across multiple compress() operations. +* ZstdCompressor.write_to() now has a flush() method. +* ZstdCompressor.compressobj()'s flush() method now accepts an argument to + flush a block (as opposed to ending the stream). +* Disallow compress(b'') when writing content sizes by default (issue #11). + +0.5.2 (released 2016-11-12) +--------------------------- + +* more packaging fixes for source distribution + +0.5.1 (released 2016-11-12) +--------------------------- + +* setup_zstd.py is included in the source distribution + 0.5.0 (released 2016-11-10) ---------------------------
--- a/contrib/python-zstandard/README.rst Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/README.rst Sat Jan 14 19:41:43 2017 -0800 @@ -2,13 +2,17 @@ python-zstandard ================ -This project provides a Python C extension for interfacing with the -`Zstandard <http://www.zstd.net>`_ compression library. +This project provides Python bindings for interfacing with the +`Zstandard <http://www.zstd.net>`_ compression library. A C extension +and CFFI interface is provided. The primary goal of the extension is to provide a Pythonic interface to the underlying C API. This means exposing most of the features and flexibility of the C API while not sacrificing usability or safety that Python provides. +The canonical home for this project is +https://github.com/indygreg/python-zstandard. + | |ci-status| |win-ci-status| State of Project @@ -205,14 +209,32 @@ Defaults to True. The dictionary ID is only written if a dictionary is being used. +Unless specified otherwise, assume that no two methods of ``ZstdCompressor`` +instances can be called from multiple Python threads simultaneously. In other +words, assume instances are not thread safe unless stated otherwise. + Simple API ^^^^^^^^^^ ``compress(data)`` compresses and returns data as a one-shot operation.:: - cctx = zstd.ZsdCompressor() + cctx = zstd.ZstdCompressor() compressed = cctx.compress(b'data to compress') +Unless ``compression_params`` or ``dict_data`` are passed to the +``ZstdCompressor``, each invocation of ``compress()`` will calculate the +optimal compression parameters for the configured compression ``level`` and +input data size (some parameters are fine-tuned for small input sizes). + +If a compression dictionary is being used, the compression parameters +determined from the first input's size will be reused for subsequent +operations. + +There is currently a deficiency in zstd's C APIs that makes it difficult +to round trip empty inputs when ``write_content_size=True``. Attempting +this will raise a ``ValueError`` unless ``allow_empty=True`` is passed +to ``compress()``. + Streaming Input API ^^^^^^^^^^^^^^^^^^^ @@ -226,7 +248,7 @@ ... The argument to ``write_to()`` must have a ``write(data)`` method. As -compressed data is available, ``write()`` will be called with the comrpessed +compressed data is available, ``write()`` will be called with the compressed data as its argument. Many common Python types implement ``write()``, including open file handles and ``io.BytesIO``. @@ -234,6 +256,10 @@ It **must** be used as a context manager. That object's ``write(data)`` method is used to feed data into the compressor. +A ``flush()`` method can be called to evict whatever data remains within the +compressor's internal state into the output object. This may result in 0 or +more ``write()`` calls to the output object. + If the size of the data being fed to this streaming compressor is known, you can declare it before compression begins:: @@ -279,6 +305,10 @@ the buffer protocol is being used). The returned iterator consists of chunks of compressed data. +If reading from the source via ``read()``, ``read()`` will be called until +it raises or returns an empty bytes (``b''``). It is perfectly valid for +the source to deliver fewer bytes than were what requested by ``read(size)``. + Like ``write_to()``, ``read_from()`` also accepts a ``size`` argument declaring the size of the input stream:: @@ -293,6 +323,10 @@ for chunk in cctx.read_from(fh, read_size=16384, write_size=8192): pass +Unlike ``write_to()``, ``read_from()`` does not give direct control over the +sizes of chunks fed into the compressor. Instead, chunk sizes will be whatever +the object being read from delivers. These will often be of a uniform size. + Stream Copying API ^^^^^^^^^^^^^^^^^^ @@ -334,9 +368,15 @@ with ``zlib.compressobj`` and ``bz2.BZ2Compressor``. This allows callers to swap in different compressor objects while using the same API. -Once ``flush()`` is called, the compressor will no longer accept new data -to ``compress()``. ``flush()`` **must** be called to end the compression -context. If not called, the returned data may be incomplete. +``flush()`` accepts an optional argument indicating how to end the stream. +``zstd.COMPRESSOBJ_FLUSH_FINISH`` (the default) ends the compression stream. +Once this type of flush is performed, ``compress()`` and ``flush()`` can +no longer be called. This type of flush **must** be called to end the +compression context. If not called, returned data may be incomplete. + +A ``zstd.COMPRESSOBJ_FLUSH_BLOCK`` argument to ``flush()`` will flush a +zstd block. Flushes of this type can be performed multiple times. The next +call to ``compress()`` will begin a new zstd block. Here is how this API should be used:: @@ -346,6 +386,15 @@ data = cobj.compress(b'raw input 1') data = cobj.flush() +Or to flush blocks:: + + cctx.zstd.ZstdCompressor() + cobj = cctx.compressobj() + data = cobj.compress(b'chunk in first block') + data = cobj.flush(zstd.COMPRESSOBJ_FLUSH_BLOCK) + data = cobj.compress(b'chunk in second block') + data = cobj.flush() + For best performance results, keep input chunks under 256KB. This avoids extra allocations for a large output object. @@ -371,6 +420,10 @@ The interface of this class is very similar to ``ZstdCompressor`` (by design). +Unless specified otherwise, assume that no two methods of ``ZstdDecompressor`` +instances can be called from multiple Python threads simultaneously. In other +words, assume instances are not thread safe unless stated otherwise. + Simple API ^^^^^^^^^^
--- a/contrib/python-zstandard/c-ext/compressiondict.c Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/c-ext/compressiondict.c Sat Jan 14 19:41:43 2017 -0800 @@ -65,14 +65,14 @@ /* Now that we know the total size of the raw simples, we can allocate a buffer for the raw data */ - sampleBuffer = malloc(samplesSize); + sampleBuffer = PyMem_Malloc(samplesSize); if (!sampleBuffer) { PyErr_NoMemory(); return NULL; } - sampleSizes = malloc(samplesLen * sizeof(size_t)); + sampleSizes = PyMem_Malloc(samplesLen * sizeof(size_t)); if (!sampleSizes) { - free(sampleBuffer); + PyMem_Free(sampleBuffer); PyErr_NoMemory(); return NULL; } @@ -87,10 +87,10 @@ sampleOffset = (char*)sampleOffset + sampleSize; } - dict = malloc(capacity); + dict = PyMem_Malloc(capacity); if (!dict) { - free(sampleSizes); - free(sampleBuffer); + PyMem_Free(sampleSizes); + PyMem_Free(sampleBuffer); PyErr_NoMemory(); return NULL; } @@ -100,9 +100,9 @@ zparams); if (ZDICT_isError(zresult)) { PyErr_Format(ZstdError, "Cannot train dict: %s", ZDICT_getErrorName(zresult)); - free(dict); - free(sampleSizes); - free(sampleBuffer); + PyMem_Free(dict); + PyMem_Free(sampleSizes); + PyMem_Free(sampleBuffer); return NULL; } @@ -140,7 +140,7 @@ return -1; } - self->dictData = malloc(sourceSize); + self->dictData = PyMem_Malloc(sourceSize); if (!self->dictData) { PyErr_NoMemory(); return -1; @@ -154,7 +154,7 @@ static void ZstdCompressionDict_dealloc(ZstdCompressionDict* self) { if (self->dictData) { - free(self->dictData); + PyMem_Free(self->dictData); self->dictData = NULL; }
--- a/contrib/python-zstandard/c-ext/compressionwriter.c Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/c-ext/compressionwriter.c Sat Jan 14 19:41:43 2017 -0800 @@ -61,7 +61,7 @@ if (self->cstream && exc_type == Py_None && exc_value == Py_None && exc_tb == Py_None) { - output.dst = malloc(self->outSize); + output.dst = PyMem_Malloc(self->outSize); if (!output.dst) { return PyErr_NoMemory(); } @@ -73,7 +73,7 @@ if (ZSTD_isError(zresult)) { PyErr_Format(ZstdError, "error ending compression stream: %s", ZSTD_getErrorName(zresult)); - free(output.dst); + PyMem_Free(output.dst); return NULL; } @@ -94,7 +94,7 @@ output.pos = 0; } - free(output.dst); + PyMem_Free(output.dst); ZSTD_freeCStream(self->cstream); self->cstream = NULL; } @@ -133,7 +133,7 @@ return NULL; } - output.dst = malloc(self->outSize); + output.dst = PyMem_Malloc(self->outSize); if (!output.dst) { return PyErr_NoMemory(); } @@ -150,7 +150,7 @@ Py_END_ALLOW_THREADS if (ZSTD_isError(zresult)) { - free(output.dst); + PyMem_Free(output.dst); PyErr_Format(ZstdError, "zstd compress error: %s", ZSTD_getErrorName(zresult)); return NULL; } @@ -168,12 +168,63 @@ output.pos = 0; } - free(output.dst); + PyMem_Free(output.dst); /* TODO return bytes written */ Py_RETURN_NONE; +} + +static PyObject* ZstdCompressionWriter_flush(ZstdCompressionWriter* self, PyObject* args) { + size_t zresult; + ZSTD_outBuffer output; + PyObject* res; + + if (!self->entered) { + PyErr_SetString(ZstdError, "flush must be called from an active context manager"); + return NULL; } + output.dst = PyMem_Malloc(self->outSize); + if (!output.dst) { + return PyErr_NoMemory(); + } + output.size = self->outSize; + output.pos = 0; + + while (1) { + Py_BEGIN_ALLOW_THREADS + zresult = ZSTD_flushStream(self->cstream, &output); + Py_END_ALLOW_THREADS + + if (ZSTD_isError(zresult)) { + PyMem_Free(output.dst); + PyErr_Format(ZstdError, "zstd compress error: %s", ZSTD_getErrorName(zresult)); + return NULL; + } + + if (!output.pos) { + break; + } + + /* Copy data from output buffer to writer. */ + if (output.pos) { +#if PY_MAJOR_VERSION >= 3 + res = PyObject_CallMethod(self->writer, "write", "y#", +#else + res = PyObject_CallMethod(self->writer, "write", "s#", +#endif + output.dst, output.pos); + Py_XDECREF(res); + } + output.pos = 0; + } + + PyMem_Free(output.dst); + + /* TODO return bytes written */ + Py_RETURN_NONE; +} + static PyMethodDef ZstdCompressionWriter_methods[] = { { "__enter__", (PyCFunction)ZstdCompressionWriter_enter, METH_NOARGS, PyDoc_STR("Enter a compression context.") }, @@ -183,6 +234,8 @@ PyDoc_STR("Obtain the memory size of the underlying compressor") }, { "write", (PyCFunction)ZstdCompressionWriter_write, METH_VARARGS, PyDoc_STR("Compress data") }, + { "flush", (PyCFunction)ZstdCompressionWriter_flush, METH_NOARGS, + PyDoc_STR("Flush data and finish a zstd frame") }, { NULL, NULL } };
--- a/contrib/python-zstandard/c-ext/compressobj.c Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/c-ext/compressobj.c Sat Jan 14 19:41:43 2017 -0800 @@ -36,8 +36,8 @@ PyObject* result = NULL; Py_ssize_t resultSize = 0; - if (self->flushed) { - PyErr_SetString(ZstdError, "cannot call compress() after flush() has been called"); + if (self->finished) { + PyErr_SetString(ZstdError, "cannot call compress() after compressor finished"); return NULL; } @@ -92,17 +92,62 @@ } } -static PyObject* ZstdCompressionObj_flush(ZstdCompressionObj* self) { +static PyObject* ZstdCompressionObj_flush(ZstdCompressionObj* self, PyObject* args) { + int flushMode = compressorobj_flush_finish; size_t zresult; PyObject* result = NULL; Py_ssize_t resultSize = 0; - if (self->flushed) { - PyErr_SetString(ZstdError, "flush() already called"); + if (!PyArg_ParseTuple(args, "|i", &flushMode)) { + return NULL; + } + + if (flushMode != compressorobj_flush_finish && flushMode != compressorobj_flush_block) { + PyErr_SetString(PyExc_ValueError, "flush mode not recognized"); + return NULL; + } + + if (self->finished) { + PyErr_SetString(ZstdError, "compressor object already finished"); return NULL; } - self->flushed = 1; + assert(self->output.pos == 0); + + if (flushMode == compressorobj_flush_block) { + /* The output buffer is of size ZSTD_CStreamOutSize(), which is + guaranteed to hold a full block. */ + Py_BEGIN_ALLOW_THREADS + zresult = ZSTD_flushStream(self->cstream, &self->output); + Py_END_ALLOW_THREADS + + if (ZSTD_isError(zresult)) { + PyErr_Format(ZstdError, "zstd compress error: %s", ZSTD_getErrorName(zresult)); + return NULL; + } + + /* Output buffer is guaranteed to hold full block. */ + assert(zresult == 0); + + if (self->output.pos) { + result = PyBytes_FromStringAndSize(self->output.dst, self->output.pos); + if (!result) { + return NULL; + } + } + + self->output.pos = 0; + + if (result) { + return result; + } + else { + return PyBytes_FromString(""); + } + } + + assert(flushMode == compressorobj_flush_finish); + self->finished = 1; while (1) { zresult = ZSTD_endStream(self->cstream, &self->output); @@ -151,7 +196,7 @@ static PyMethodDef ZstdCompressionObj_methods[] = { { "compress", (PyCFunction)ZstdCompressionObj_compress, METH_VARARGS, PyDoc_STR("compress data") }, - { "flush", (PyCFunction)ZstdCompressionObj_flush, METH_NOARGS, + { "flush", (PyCFunction)ZstdCompressionObj_flush, METH_VARARGS, PyDoc_STR("finish compression operation") }, { NULL, NULL } };
--- a/contrib/python-zstandard/c-ext/compressor.c Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/c-ext/compressor.c Sat Jan 14 19:41:43 2017 -0800 @@ -10,6 +10,23 @@ extern PyObject* ZstdError; +int populate_cdict(ZstdCompressor* compressor, void* dictData, size_t dictSize, ZSTD_parameters* zparams) { + ZSTD_customMem zmem; + assert(!compressor->cdict); + Py_BEGIN_ALLOW_THREADS + memset(&zmem, 0, sizeof(zmem)); + compressor->cdict = ZSTD_createCDict_advanced(compressor->dict->dictData, + compressor->dict->dictSize, *zparams, zmem); + Py_END_ALLOW_THREADS + + if (!compressor->cdict) { + PyErr_SetString(ZstdError, "could not create compression dictionary"); + return 1; + } + + return 0; +} + /** * Initialize a zstd CStream from a ZstdCompressor instance. * @@ -57,7 +74,6 @@ return cstream; } - PyDoc_STRVAR(ZstdCompressor__doc__, "ZstdCompressor(level=None, dict_data=None, compression_params=None)\n" "\n" @@ -107,6 +123,7 @@ PyObject* writeContentSize = NULL; PyObject* writeDictID = NULL; + self->cctx = NULL; self->dict = NULL; self->cparams = NULL; self->cdict = NULL; @@ -129,6 +146,14 @@ return -1; } + /* We create a ZSTD_CCtx for reuse among multiple operations to reduce the + overhead of each compression operation. */ + self->cctx = ZSTD_createCCtx(); + if (!self->cctx) { + PyErr_NoMemory(); + return -1; + } + self->compressionLevel = level; if (dict) { @@ -165,6 +190,11 @@ self->cdict = NULL; } + if (self->cctx) { + ZSTD_freeCCtx(self->cctx); + self->cctx = NULL; + } + PyObject_Del(self); } @@ -339,7 +369,7 @@ } PyDoc_STRVAR(ZstdCompressor_compress__doc__, -"compress(data)\n" +"compress(data, allow_empty=False)\n" "\n" "Compress data in a single operation.\n" "\n" @@ -350,24 +380,41 @@ "streaming based APIs is preferred for larger values.\n" ); -static PyObject* ZstdCompressor_compress(ZstdCompressor* self, PyObject* args) { +static PyObject* ZstdCompressor_compress(ZstdCompressor* self, PyObject* args, PyObject* kwargs) { + static char* kwlist[] = { + "data", + "allow_empty", + NULL + }; + const char* source; Py_ssize_t sourceSize; + PyObject* allowEmpty = NULL; size_t destSize; - ZSTD_CCtx* cctx; PyObject* output; char* dest; void* dictData = NULL; size_t dictSize = 0; size_t zresult; ZSTD_parameters zparams; - ZSTD_customMem zmem; #if PY_MAJOR_VERSION >= 3 - if (!PyArg_ParseTuple(args, "y#", &source, &sourceSize)) { + if (!PyArg_ParseTupleAndKeywords(args, kwargs, "y#|O", #else - if (!PyArg_ParseTuple(args, "s#", &source, &sourceSize)) { + if (!PyArg_ParseTupleAndKeywords(args, kwargs, "s#|O", #endif + kwlist, &source, &sourceSize, &allowEmpty)) { + return NULL; + } + + /* Limitation in zstd C API doesn't let decompression side distinguish + between content size of 0 and unknown content size. This can make round + tripping via Python difficult. Until this is fixed, require a flag + to fire the footgun. + https://github.com/indygreg/python-zstandard/issues/11 */ + if (0 == sourceSize && self->fparams.contentSizeFlag + && (!allowEmpty || PyObject_Not(allowEmpty))) { + PyErr_SetString(PyExc_ValueError, "cannot write empty inputs when writing content sizes"); return NULL; } @@ -379,13 +426,6 @@ dest = PyBytes_AsString(output); - cctx = ZSTD_createCCtx(); - if (!cctx) { - Py_DECREF(output); - PyErr_SetString(ZstdError, "could not create CCtx"); - return NULL; - } - if (self->dict) { dictData = self->dict->dictData; dictSize = self->dict->dictSize; @@ -406,23 +446,16 @@ /* The raw dict data has to be processed before it can be used. Since this adds overhead - especially if multiple dictionary compression operations are performed on the same ZstdCompressor instance - we create a - ZSTD_CDict once and reuse it for all operations. */ + ZSTD_CDict once and reuse it for all operations. - /* TODO the zparams (which can be derived from the source data size) used - on first invocation are effectively reused for subsequent operations. This - may not be appropriate if input sizes vary significantly and could affect - chosen compression parameters. - https://github.com/facebook/zstd/issues/358 tracks this issue. */ + Note: the compression parameters used for the first invocation (possibly + derived from the source size) will be reused on all subsequent invocations. + https://github.com/facebook/zstd/issues/358 contains more info. We could + potentially add an argument somewhere to control this behavior. + */ if (dictData && !self->cdict) { - Py_BEGIN_ALLOW_THREADS - memset(&zmem, 0, sizeof(zmem)); - self->cdict = ZSTD_createCDict_advanced(dictData, dictSize, zparams, zmem); - Py_END_ALLOW_THREADS - - if (!self->cdict) { + if (populate_cdict(self, dictData, dictSize, &zparams)) { Py_DECREF(output); - ZSTD_freeCCtx(cctx); - PyErr_SetString(ZstdError, "could not create compression dictionary"); return NULL; } } @@ -432,17 +465,15 @@ size. This means the argument to ZstdCompressor to control frame parameters is honored. */ if (self->cdict) { - zresult = ZSTD_compress_usingCDict(cctx, dest, destSize, + zresult = ZSTD_compress_usingCDict(self->cctx, dest, destSize, source, sourceSize, self->cdict); } else { - zresult = ZSTD_compress_advanced(cctx, dest, destSize, + zresult = ZSTD_compress_advanced(self->cctx, dest, destSize, source, sourceSize, dictData, dictSize, zparams); } Py_END_ALLOW_THREADS - ZSTD_freeCCtx(cctx); - if (ZSTD_isError(zresult)) { PyErr_Format(ZstdError, "cannot compress: %s", ZSTD_getErrorName(zresult)); Py_CLEAR(output); @@ -500,7 +531,7 @@ result->compressor = self; Py_INCREF(result->compressor); - result->flushed = 0; + result->finished = 0; return result; } @@ -691,8 +722,8 @@ } static PyMethodDef ZstdCompressor_methods[] = { - { "compress", (PyCFunction)ZstdCompressor_compress, METH_VARARGS, - ZstdCompressor_compress__doc__ }, + { "compress", (PyCFunction)ZstdCompressor_compress, + METH_VARARGS | METH_KEYWORDS, ZstdCompressor_compress__doc__ }, { "compressobj", (PyCFunction)ZstdCompressor_compressobj, METH_VARARGS | METH_KEYWORDS, ZstdCompressionObj__doc__ }, { "copy_stream", (PyCFunction)ZstdCompressor_copy_stream,
--- a/contrib/python-zstandard/c-ext/constants.c Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/c-ext/constants.c Sat Jan 14 19:41:43 2017 -0800 @@ -33,6 +33,9 @@ ZstdError = PyErr_NewException("zstd.ZstdError", NULL, NULL); PyModule_AddObject(mod, "ZstdError", ZstdError); + PyModule_AddIntConstant(mod, "COMPRESSOBJ_FLUSH_FINISH", compressorobj_flush_finish); + PyModule_AddIntConstant(mod, "COMPRESSOBJ_FLUSH_BLOCK", compressorobj_flush_block); + /* For now, the version is a simple tuple instead of a dedicated type. */ zstdVersion = PyTuple_New(3); PyTuple_SetItem(zstdVersion, 0, PyLong_FromLong(ZSTD_VERSION_MAJOR));
--- a/contrib/python-zstandard/c-ext/decompressionwriter.c Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/c-ext/decompressionwriter.c Sat Jan 14 19:41:43 2017 -0800 @@ -85,7 +85,7 @@ return NULL; } - output.dst = malloc(self->outSize); + output.dst = PyMem_Malloc(self->outSize); if (!output.dst) { return PyErr_NoMemory(); } @@ -102,7 +102,7 @@ Py_END_ALLOW_THREADS if (ZSTD_isError(zresult)) { - free(output.dst); + PyMem_Free(output.dst); PyErr_Format(ZstdError, "zstd decompress error: %s", ZSTD_getErrorName(zresult)); return NULL; @@ -120,7 +120,7 @@ } } - free(output.dst); + PyMem_Free(output.dst); /* TODO return bytes written */ Py_RETURN_NONE;
--- a/contrib/python-zstandard/c-ext/python-zstandard.h Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/c-ext/python-zstandard.h Sat Jan 14 19:41:43 2017 -0800 @@ -15,7 +15,12 @@ #include "zstd.h" #include "zdict.h" -#define PYTHON_ZSTANDARD_VERSION "0.5.0" +#define PYTHON_ZSTANDARD_VERSION "0.6.0" + +typedef enum { + compressorobj_flush_finish, + compressorobj_flush_block, +} CompressorObj_Flush; typedef struct { PyObject_HEAD @@ -54,6 +59,7 @@ int compressionLevel; ZstdCompressionDict* dict; + ZSTD_CCtx* cctx; ZSTD_CDict* cdict; CompressionParametersObject* cparams; ZSTD_frameParameters fparams; @@ -67,7 +73,7 @@ ZstdCompressor* compressor; ZSTD_CStream* cstream; ZSTD_outBuffer output; - int flushed; + int finished; } ZstdCompressionObj; extern PyTypeObject ZstdCompressionObjType;
--- a/contrib/python-zstandard/make_cffi.py Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/make_cffi.py Sat Jan 14 19:41:43 2017 -0800 @@ -7,7 +7,10 @@ from __future__ import absolute_import import cffi +import distutils.ccompiler import os +import subprocess +import tempfile HERE = os.path.abspath(os.path.dirname(__file__)) @@ -20,10 +23,8 @@ 'common/zstd_common.c', 'compress/fse_compress.c', 'compress/huf_compress.c', - 'compress/zbuff_compress.c', 'compress/zstd_compress.c', 'decompress/huf_decompress.c', - 'decompress/zbuff_decompress.c', 'decompress/zstd_decompress.c', 'dictBuilder/divsufsort.c', 'dictBuilder/zdict.c', @@ -37,74 +38,71 @@ 'zstd/dictBuilder', )] +# cffi can't parse some of the primitives in zstd.h. So we invoke the +# preprocessor and feed its output into cffi. +compiler = distutils.ccompiler.new_compiler() + +# Needed for MSVC. +if hasattr(compiler, 'initialize'): + compiler.initialize() + +# Distutils doesn't set compiler.preprocessor, so invoke the preprocessor +# manually. +if compiler.compiler_type == 'unix': + args = list(compiler.executables['compiler']) + args.extend([ + '-E', + '-DZSTD_STATIC_LINKING_ONLY', + ]) +elif compiler.compiler_type == 'msvc': + args = [compiler.cc] + args.extend([ + '/EP', + '/DZSTD_STATIC_LINKING_ONLY', + ]) +else: + raise Exception('unsupported compiler type: %s' % compiler.compiler_type) + +# zstd.h includes <stddef.h>, which is also included by cffi's boilerplate. +# This can lead to duplicate declarations. So we strip this include from the +# preprocessor invocation. + with open(os.path.join(HERE, 'zstd', 'zstd.h'), 'rb') as fh: - zstd_h = fh.read() + lines = [l for l in fh if not l.startswith(b'#include <stddef.h>')] + +fd, input_file = tempfile.mkstemp(suffix='.h') +os.write(fd, b''.join(lines)) +os.close(fd) + +args.append(input_file) + +try: + process = subprocess.Popen(args, stdout=subprocess.PIPE) + output = process.communicate()[0] + ret = process.poll() + if ret: + raise Exception('preprocessor exited with error') +finally: + os.unlink(input_file) + +def normalize_output(): + lines = [] + for line in output.splitlines(): + # CFFI's parser doesn't like __attribute__ on UNIX compilers. + if line.startswith(b'__attribute__ ((visibility ("default"))) '): + line = line[len(b'__attribute__ ((visibility ("default"))) '):] + + lines.append(line) + + return b'\n'.join(lines) ffi = cffi.FFI() ffi.set_source('_zstd_cffi', ''' -/* needed for typedefs like U32 references in zstd.h */ -#include "mem.h" #define ZSTD_STATIC_LINKING_ONLY #include "zstd.h" -''', - sources=SOURCES, include_dirs=INCLUDE_DIRS) - -# Rather than define the API definitions from zstd.h inline, munge the -# source in a way that cdef() will accept. -lines = zstd_h.splitlines() -lines = [l.rstrip() for l in lines if l.strip()] - -# Strip preprocessor directives - they aren't important for our needs. -lines = [l for l in lines - if not l.startswith((b'#if', b'#else', b'#endif', b'#include'))] - -# Remove extern C block -lines = [l for l in lines if l not in (b'extern "C" {', b'}')] - -# The version #defines don't parse and aren't necessary. Strip them. -lines = [l for l in lines if not l.startswith(( - b'#define ZSTD_H_235446', - b'#define ZSTD_LIB_VERSION', - b'#define ZSTD_QUOTE', - b'#define ZSTD_EXPAND_AND_QUOTE', - b'#define ZSTD_VERSION_STRING', - b'#define ZSTD_VERSION_NUMBER'))] +''', sources=SOURCES, include_dirs=INCLUDE_DIRS) -# The C parser also doesn't like some constant defines referencing -# other constants. -# TODO we pick the 64-bit constants here. We should assert somewhere -# we're compiling for 64-bit. -def fix_constants(l): - if l.startswith(b'#define ZSTD_WINDOWLOG_MAX '): - return b'#define ZSTD_WINDOWLOG_MAX 27' - elif l.startswith(b'#define ZSTD_CHAINLOG_MAX '): - return b'#define ZSTD_CHAINLOG_MAX 28' - elif l.startswith(b'#define ZSTD_HASHLOG_MAX '): - return b'#define ZSTD_HASHLOG_MAX 27' - elif l.startswith(b'#define ZSTD_CHAINLOG_MAX '): - return b'#define ZSTD_CHAINLOG_MAX 28' - elif l.startswith(b'#define ZSTD_CHAINLOG_MIN '): - return b'#define ZSTD_CHAINLOG_MIN 6' - elif l.startswith(b'#define ZSTD_SEARCHLOG_MAX '): - return b'#define ZSTD_SEARCHLOG_MAX 26' - elif l.startswith(b'#define ZSTD_BLOCKSIZE_ABSOLUTEMAX '): - return b'#define ZSTD_BLOCKSIZE_ABSOLUTEMAX 131072' - else: - return l -lines = map(fix_constants, lines) - -# ZSTDLIB_API isn't handled correctly. Strip it. -lines = [l for l in lines if not l.startswith(b'# define ZSTDLIB_API')] -def strip_api(l): - if l.startswith(b'ZSTDLIB_API '): - return l[len(b'ZSTDLIB_API '):] - else: - return l -lines = map(strip_api, lines) - -source = b'\n'.join(lines) -ffi.cdef(source.decode('latin1')) - +ffi.cdef(normalize_output().decode('latin1')) if __name__ == '__main__': ffi.compile()
--- a/contrib/python-zstandard/setup.py Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/setup.py Sat Jan 14 19:41:43 2017 -0800 @@ -5,6 +5,7 @@ # This software may be modified and distributed under the terms # of the BSD license. See the LICENSE file for details. +import sys from setuptools import setup try: @@ -14,9 +15,15 @@ import setup_zstd +SUPPORT_LEGACY = False + +if "--legacy" in sys.argv: + SUPPORT_LEGACY = True + sys.argv.remove("--legacy") + # Code for obtaining the Extension instance is in its own module to # facilitate reuse in other projects. -extensions = [setup_zstd.get_c_extension()] +extensions = [setup_zstd.get_c_extension(SUPPORT_LEGACY, 'zstd')] if cffi: import make_cffi
--- a/contrib/python-zstandard/setup_zstd.py Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/setup_zstd.py Sat Jan 14 19:41:43 2017 -0800 @@ -16,15 +16,24 @@ 'common/zstd_common.c', 'compress/fse_compress.c', 'compress/huf_compress.c', - 'compress/zbuff_compress.c', 'compress/zstd_compress.c', 'decompress/huf_decompress.c', - 'decompress/zbuff_decompress.c', 'decompress/zstd_decompress.c', 'dictBuilder/divsufsort.c', 'dictBuilder/zdict.c', )] +zstd_sources_legacy = ['zstd/%s' % p for p in ( + 'deprecated/zbuff_compress.c', + 'deprecated/zbuff_decompress.c', + 'legacy/zstd_v01.c', + 'legacy/zstd_v02.c', + 'legacy/zstd_v03.c', + 'legacy/zstd_v04.c', + 'legacy/zstd_v05.c', + 'legacy/zstd_v06.c', + 'legacy/zstd_v07.c' +)] zstd_includes = [ 'c-ext', @@ -35,6 +44,11 @@ 'zstd/dictBuilder', ] +zstd_includes_legacy = [ + 'zstd/deprecated', + 'zstd/legacy', +] + ext_sources = [ 'zstd.c', 'c-ext/compressiondict.c', @@ -51,14 +65,27 @@ 'c-ext/dictparams.c', ] +zstd_depends = [ + 'c-ext/python-zstandard.h', +] -def get_c_extension(name='zstd'): + +def get_c_extension(support_legacy=False, name='zstd'): """Obtain a distutils.extension.Extension for the C extension.""" root = os.path.abspath(os.path.dirname(__file__)) sources = [os.path.join(root, p) for p in zstd_sources + ext_sources] + if support_legacy: + sources.extend([os.path.join(root, p) for p in zstd_sources_legacy]) + include_dirs = [os.path.join(root, d) for d in zstd_includes] + if support_legacy: + include_dirs.extend([os.path.join(root, d) for d in zstd_includes_legacy]) + + depends = [os.path.join(root, p) for p in zstd_depends] # TODO compile with optimizations. return Extension(name, sources, - include_dirs=include_dirs) + include_dirs=include_dirs, + depends=depends, + extra_compile_args=["-DZSTD_LEGACY_SUPPORT=1"] if support_legacy else [])
--- a/contrib/python-zstandard/tests/test_compressor.py Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/tests/test_compressor.py Sat Jan 14 19:41:43 2017 -0800 @@ -41,6 +41,14 @@ self.assertEqual(cctx.compress(b''), b'\x28\xb5\x2f\xfd\x00\x48\x01\x00\x00') + # TODO should be temporary until https://github.com/facebook/zstd/issues/506 + # is fixed. + cctx = zstd.ZstdCompressor(write_content_size=True) + with self.assertRaises(ValueError): + cctx.compress(b'') + + cctx.compress(b'', allow_empty=True) + def test_compress_large(self): chunks = [] for i in range(255): @@ -139,19 +147,45 @@ self.assertEqual(len(with_size), len(no_size) + 1) - def test_compress_after_flush(self): + def test_compress_after_finished(self): cctx = zstd.ZstdCompressor() cobj = cctx.compressobj() cobj.compress(b'foo') cobj.flush() - with self.assertRaisesRegexp(zstd.ZstdError, 'cannot call compress\(\) after flush'): + with self.assertRaisesRegexp(zstd.ZstdError, 'cannot call compress\(\) after compressor'): cobj.compress(b'foo') - with self.assertRaisesRegexp(zstd.ZstdError, 'flush\(\) already called'): + with self.assertRaisesRegexp(zstd.ZstdError, 'compressor object already finished'): cobj.flush() + def test_flush_block_repeated(self): + cctx = zstd.ZstdCompressor(level=1) + cobj = cctx.compressobj() + + self.assertEqual(cobj.compress(b'foo'), b'') + self.assertEqual(cobj.flush(zstd.COMPRESSOBJ_FLUSH_BLOCK), + b'\x28\xb5\x2f\xfd\x00\x48\x18\x00\x00foo') + self.assertEqual(cobj.compress(b'bar'), b'') + # 3 byte header plus content. + self.assertEqual(cobj.flush(), b'\x19\x00\x00bar') + + def test_flush_empty_block(self): + cctx = zstd.ZstdCompressor(write_checksum=True) + cobj = cctx.compressobj() + + cobj.compress(b'foobar') + cobj.flush(zstd.COMPRESSOBJ_FLUSH_BLOCK) + # No-op if no block is active (this is internal to zstd). + self.assertEqual(cobj.flush(zstd.COMPRESSOBJ_FLUSH_BLOCK), b'') + + trailing = cobj.flush() + # 3 bytes block header + 4 bytes frame checksum + self.assertEqual(len(trailing), 7) + header = trailing[0:3] + self.assertEqual(header, b'\x01\x00\x00') + class TestCompressor_copy_stream(unittest.TestCase): def test_no_read(self): @@ -384,6 +418,43 @@ self.assertEqual(len(dest.getvalue()), dest._write_count) + def test_flush_repeated(self): + cctx = zstd.ZstdCompressor(level=3) + dest = OpCountingBytesIO() + with cctx.write_to(dest) as compressor: + compressor.write(b'foo') + self.assertEqual(dest._write_count, 0) + compressor.flush() + self.assertEqual(dest._write_count, 1) + compressor.write(b'bar') + self.assertEqual(dest._write_count, 1) + compressor.flush() + self.assertEqual(dest._write_count, 2) + compressor.write(b'baz') + + self.assertEqual(dest._write_count, 3) + + def test_flush_empty_block(self): + cctx = zstd.ZstdCompressor(level=3, write_checksum=True) + dest = OpCountingBytesIO() + with cctx.write_to(dest) as compressor: + compressor.write(b'foobar' * 8192) + count = dest._write_count + offset = dest.tell() + compressor.flush() + self.assertGreater(dest._write_count, count) + self.assertGreater(dest.tell(), offset) + offset = dest.tell() + # Ending the write here should cause an empty block to be written + # to denote end of frame. + + trailing = dest.getvalue()[offset:] + # 3 bytes block header + 4 bytes frame checksum + self.assertEqual(len(trailing), 7) + + header = trailing[0:3] + self.assertEqual(header, b'\x01\x00\x00') + class TestCompressor_read_from(unittest.TestCase): def test_type_validation(self):
--- a/contrib/python-zstandard/tests/test_module_attributes.py Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/tests/test_module_attributes.py Sat Jan 14 19:41:43 2017 -0800 @@ -9,7 +9,7 @@ class TestModuleAttributes(unittest.TestCase): def test_version(self): - self.assertEqual(zstd.ZSTD_VERSION, (1, 1, 1)) + self.assertEqual(zstd.ZSTD_VERSION, (1, 1, 2)) def test_constants(self): self.assertEqual(zstd.MAX_COMPRESSION_LEVEL, 22)
--- a/contrib/python-zstandard/zstd.c Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd.c Sat Jan 14 19:41:43 2017 -0800 @@ -72,6 +72,26 @@ void decompressoriterator_module_init(PyObject* mod); void zstd_module_init(PyObject* m) { + /* python-zstandard relies on unstable zstd C API features. This means + that changes in zstd may break expectations in python-zstandard. + + python-zstandard is distributed with a copy of the zstd sources. + python-zstandard is only guaranteed to work with the bundled version + of zstd. + + However, downstream redistributors or packagers may unbundle zstd + from python-zstandard. This can result in a mismatch between zstd + versions and API semantics. This essentially "voids the warranty" + of python-zstandard and may cause undefined behavior. + + We detect this mismatch here and refuse to load the module if this + scenario is detected. + */ + if (ZSTD_VERSION_NUMBER != 10102 || ZSTD_versionNumber() != 10102) { + PyErr_SetString(PyExc_ImportError, "zstd C API mismatch; Python bindings not compiled against expected zstd version"); + return; + } + compressionparams_module_init(m); dictparams_module_init(m); compressiondict_module_init(m); @@ -99,6 +119,10 @@ PyObject *m = PyModule_Create(&zstd_module); if (m) { zstd_module_init(m); + if (PyErr_Occurred()) { + Py_DECREF(m); + m = NULL; + } } return m; }
--- a/contrib/python-zstandard/zstd/common/bitstream.h Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd/common/bitstream.h Sat Jan 14 19:41:43 2017 -0800 @@ -266,7 +266,7 @@ bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer); bitD->bitContainer = MEM_readLEST(bitD->ptr); { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1]; - bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0; + bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0; /* ensures bitsConsumed is always set */ if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ } } else { bitD->start = (const char*)srcBuffer; @@ -298,7 +298,7 @@ MEM_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits) { -#if defined(__BMI__) && defined(__GNUC__) /* experimental */ +#if defined(__BMI__) && defined(__GNUC__) && __GNUC__*1000+__GNUC_MINOR__ >= 4008 /* experimental */ # if defined(__x86_64__) if (sizeof(bitContainer)==8) return _bextr_u64(bitContainer, start, nbBits); @@ -367,10 +367,10 @@ } /*! BIT_reloadDStream() : -* Refill `BIT_DStream_t` from src buffer previously defined (see BIT_initDStream() ). +* Refill `bitD` from buffer previously set in BIT_initDStream() . * This function is safe, it guarantees it will not read beyond src buffer. * @return : status of `BIT_DStream_t` internal register. - if status == unfinished, internal register is filled with >= (sizeof(bitD->bitContainer)*8 - 7) bits */ + if status == BIT_DStream_unfinished, internal register is filled with >= (sizeof(bitD->bitContainer)*8 - 7) bits */ MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD) { if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should not happen => corruption detected */
--- a/contrib/python-zstandard/zstd/common/entropy_common.c Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd/common/entropy_common.c Sat Jan 14 19:41:43 2017 -0800 @@ -159,6 +159,7 @@ /*! HUF_readStats() : Read compact Huffman tree, saved by HUF_writeCTable(). `huffWeight` is destination buffer. + `rankStats` is assumed to be a table of at least HUF_TABLELOG_MAX U32. @return : size read from `src` , or an error Code . Note : Needed by HUF_readCTable() and HUF_readDTableX?() . */ @@ -187,16 +188,17 @@ huffWeight[n+1] = ip[n/2] & 15; } } } else { /* header compressed with FSE (normal case) */ + FSE_DTable fseWorkspace[FSE_DTABLE_SIZE_U32(6)]; /* 6 is max possible tableLog for HUF header (maybe even 5, to be tested) */ if (iSize+1 > srcSize) return ERROR(srcSize_wrong); - oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */ + oSize = FSE_decompress_wksp(huffWeight, hwSize-1, ip+1, iSize, fseWorkspace, 6); /* max (hwSize-1) values decoded, as last one is implied */ if (FSE_isError(oSize)) return oSize; } /* collect weight stats */ - memset(rankStats, 0, (HUF_TABLELOG_ABSOLUTEMAX + 1) * sizeof(U32)); + memset(rankStats, 0, (HUF_TABLELOG_MAX + 1) * sizeof(U32)); weightTotal = 0; { U32 n; for (n=0; n<oSize; n++) { - if (huffWeight[n] >= HUF_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected); + if (huffWeight[n] >= HUF_TABLELOG_MAX) return ERROR(corruption_detected); rankStats[huffWeight[n]]++; weightTotal += (1 << huffWeight[n]) >> 1; } } @@ -204,7 +206,7 @@ /* get last non-null symbol weight (implied, total must be 2^n) */ { U32 const tableLog = BIT_highbit32(weightTotal) + 1; - if (tableLog > HUF_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected); + if (tableLog > HUF_TABLELOG_MAX) return ERROR(corruption_detected); *tableLogPtr = tableLog; /* determine last weight */ { U32 const total = 1 << tableLog;
--- a/contrib/python-zstandard/zstd/common/fse.h Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd/common/fse.h Sat Jan 14 19:41:43 2017 -0800 @@ -286,7 +286,7 @@ #define FSE_BLOCKBOUND(size) (size + (size>>7)) #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */ -/* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */ +/* It is possible to statically allocate FSE CTable/DTable as a table of FSE_CTable/FSE_DTable using below macros */ #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2)) #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog)) @@ -294,37 +294,72 @@ /* ***************************************** * FSE advanced API *******************************************/ +/* FSE_count_wksp() : + * Same as FSE_count(), but using an externally provided scratch buffer. + * `workSpace` size must be table of >= `1024` unsigned + */ +size_t FSE_count_wksp(unsigned* count, unsigned* maxSymbolValuePtr, + const void* source, size_t sourceSize, unsigned* workSpace); + +/** FSE_countFast() : + * same as FSE_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr + */ size_t FSE_countFast(unsigned* count, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize); -/**< same as FSE_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr */ + +/* FSE_countFast_wksp() : + * Same as FSE_countFast(), but using an externally provided scratch buffer. + * `workSpace` must be a table of minimum `1024` unsigned + */ +size_t FSE_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize, unsigned* workSpace); + +/*! FSE_count_simple + * Same as FSE_countFast(), but does not use any additional memory (not even on stack). + * This function is unsafe, and will segfault if any value within `src` is `> *maxSymbolValuePtr` (presuming it's also the size of `count`). +*/ +size_t FSE_count_simple(unsigned* count, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize); + + unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus); /**< same as FSE_optimalTableLog(), which used `minus==2` */ +/* FSE_compress_wksp() : + * Same as FSE_compress2(), but using an externally allocated scratch buffer (`workSpace`). + * FSE_WKSP_SIZE_U32() provides the minimum size required for `workSpace` as a table of FSE_CTable. + */ +#define FSE_WKSP_SIZE_U32(maxTableLog, maxSymbolValue) ( FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) + (1<<((maxTableLog>2)?(maxTableLog-2):0)) ) +size_t FSE_compress_wksp (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize); + size_t FSE_buildCTable_raw (FSE_CTable* ct, unsigned nbBits); -/**< build a fake FSE_CTable, designed to not compress an input, where each symbol uses nbBits */ +/**< build a fake FSE_CTable, designed for a flat distribution, where each symbol uses nbBits */ size_t FSE_buildCTable_rle (FSE_CTable* ct, unsigned char symbolValue); /**< build a fake FSE_CTable, designed to compress always the same symbolValue */ +/* FSE_buildCTable_wksp() : + * Same as FSE_buildCTable(), but using an externally allocated scratch buffer (`workSpace`). + * `wkspSize` must be >= `(1<<tableLog)`. + */ +size_t FSE_buildCTable_wksp(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize); + size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits); -/**< build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */ +/**< build a fake FSE_DTable, designed to read a flat distribution where each symbol uses nbBits */ size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue); /**< build a fake FSE_DTable, designed to always generate the same symbolValue */ +size_t FSE_decompress_wksp(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, FSE_DTable* workSpace, unsigned maxLog); +/**< same as FSE_decompress(), using an externally allocated `workSpace` produced with `FSE_DTABLE_SIZE_U32(maxLog)` */ + /* ***************************************** * FSE symbol compression API *******************************************/ /*! This API consists of small unitary functions, which highly benefit from being inlined. - You will want to enable link-time-optimization to ensure these functions are properly inlined in your binary. - Visual seems to do it automatically. - For gcc or clang, you'll need to add -flto flag at compilation and linking stages. - If none of these solutions is applicable, include "fse.c" directly. + Hence their body are included in next section. */ -typedef struct -{ +typedef struct { ptrdiff_t value; const void* stateTable; const void* symbolTT; @@ -384,8 +419,7 @@ /* ***************************************** * FSE symbol decompression API *******************************************/ -typedef struct -{ +typedef struct { size_t state; const void* table; /* precise table may vary, depending on U16 */ } FSE_DState_t;
--- a/contrib/python-zstandard/zstd/common/fse_decompress.c Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd/common/fse_decompress.c Sat Jan 14 19:41:43 2017 -0800 @@ -76,12 +76,6 @@ /* ************************************************************** -* Complex types -****************************************************************/ -typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]; - - -/* ************************************************************** * Templates ****************************************************************/ /* @@ -300,28 +294,34 @@ } -size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize) +size_t FSE_decompress_wksp(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, FSE_DTable* workSpace, unsigned maxLog) { const BYTE* const istart = (const BYTE*)cSrc; const BYTE* ip = istart; short counting[FSE_MAX_SYMBOL_VALUE+1]; - DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */ unsigned tableLog; unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE; - if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */ + /* normal FSE decoding mode */ + size_t const NCountLength = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize); + if (FSE_isError(NCountLength)) return NCountLength; + //if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size; supposed to be already checked in NCountLength, only remaining case : NCountLength==cSrcSize */ + if (tableLog > maxLog) return ERROR(tableLog_tooLarge); + ip += NCountLength; + cSrcSize -= NCountLength; + + CHECK_F( FSE_buildDTable (workSpace, counting, maxSymbolValue, tableLog) ); - /* normal FSE decoding mode */ - { size_t const NCountLength = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize); - if (FSE_isError(NCountLength)) return NCountLength; - if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */ - ip += NCountLength; - cSrcSize -= NCountLength; - } + return FSE_decompress_usingDTable (dst, dstCapacity, ip, cSrcSize, workSpace); /* always return, even if it is an error code */ +} + - CHECK_F( FSE_buildDTable (dt, counting, maxSymbolValue, tableLog) ); +typedef FSE_DTable DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]; - return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); /* always return, even if it is an error code */ +size_t FSE_decompress(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize) +{ + DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */ + return FSE_decompress_wksp(dst, dstCapacity, cSrc, cSrcSize, dt, FSE_MAX_TABLELOG); }
--- a/contrib/python-zstandard/zstd/common/huf.h Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd/common/huf.h Sat Jan 14 19:41:43 2017 -0800 @@ -62,21 +62,19 @@ HUF_decompress() : Decompress HUF data from buffer 'cSrc', of size 'cSrcSize', into already allocated buffer 'dst', of minimum size 'dstSize'. - `dstSize` : **must** be the ***exact*** size of original (uncompressed) data. + `originalSize` : **must** be the ***exact*** size of original (uncompressed) data. Note : in contrast with FSE, HUF_decompress can regenerate RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data, because it knows size to regenerate. - @return : size of regenerated data (== dstSize), + @return : size of regenerated data (== originalSize), or an error code, which can be tested using HUF_isError() */ -size_t HUF_decompress(void* dst, size_t dstSize, +size_t HUF_decompress(void* dst, size_t originalSize, const void* cSrc, size_t cSrcSize); -/* **************************************** -* Tool functions -******************************************/ -#define HUF_BLOCKSIZE_MAX (128 * 1024) +/* *** Tool functions *** */ +#define HUF_BLOCKSIZE_MAX (128 * 1024) /**< maximum input size for a single block compressed with HUF_compress */ size_t HUF_compressBound(size_t size); /**< maximum compressed size (worst case) */ /* Error Management */ @@ -84,12 +82,18 @@ const char* HUF_getErrorName(size_t code); /**< provides error code string (useful for debugging) */ -/* *** Advanced function *** */ +/* *** Advanced function *** */ /** HUF_compress2() : -* Same as HUF_compress(), but offers direct control over `maxSymbolValue` and `tableLog` */ + * Same as HUF_compress(), but offers direct control over `maxSymbolValue` and `tableLog` . + * `tableLog` must be `<= HUF_TABLELOG_MAX` . */ size_t HUF_compress2 (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog); +/** HUF_compress4X_wksp() : +* Same as HUF_compress2(), but uses externally allocated `workSpace`, which must be a table of >= 1024 unsigned */ +size_t HUF_compress4X_wksp (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize); /**< `workSpace` must be a table of at least 1024 unsigned */ + + #ifdef HUF_STATIC_LINKING_ONLY @@ -98,7 +102,7 @@ /* *** Constants *** */ -#define HUF_TABLELOG_ABSOLUTEMAX 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */ +#define HUF_TABLELOG_ABSOLUTEMAX 15 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */ #define HUF_TABLELOG_MAX 12 /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */ #define HUF_TABLELOG_DEFAULT 11 /* tableLog by default, when not specified */ #define HUF_SYMBOLVALUE_MAX 255 @@ -125,9 +129,9 @@ typedef U32 HUF_DTable; #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<(maxTableLog))) #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \ - HUF_DTable DTable[HUF_DTABLE_SIZE((maxTableLog)-1)] = { ((U32)((maxTableLog)-1)*0x1000001) } + HUF_DTable DTable[HUF_DTABLE_SIZE((maxTableLog)-1)] = { ((U32)((maxTableLog)-1) * 0x01000001) } #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \ - HUF_DTable DTable[HUF_DTABLE_SIZE(maxTableLog)] = { ((U32)(maxTableLog)*0x1000001) } + HUF_DTable DTable[HUF_DTABLE_SIZE(maxTableLog)] = { ((U32)(maxTableLog) * 0x01000001) } /* **************************************** @@ -141,10 +145,6 @@ size_t HUF_decompress4X2_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */ size_t HUF_decompress4X4_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */ -size_t HUF_decompress1X_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); -size_t HUF_decompress1X2_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */ -size_t HUF_decompress1X4_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */ - /* **************************************** * HUF detailed API @@ -169,6 +169,12 @@ size_t HUF_compress4X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable); +/** HUF_buildCTable_wksp() : + * Same as HUF_buildCTable(), but using externally allocated scratch buffer. + * `workSpace` must be aligned on 4-bytes boundaries, and be at least as large as a table of 1024 unsigned. + */ +size_t HUF_buildCTable_wksp (HUF_CElt* tree, const U32* count, U32 maxSymbolValue, U32 maxNbBits, void* workSpace, size_t wkspSize); + /*! HUF_readStats() : Read compact Huffman tree, saved by HUF_writeCTable(). `huffWeight` is destination buffer. @@ -208,16 +214,20 @@ /* single stream variants */ size_t HUF_compress1X (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog); +size_t HUF_compress1X_wksp (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize); /**< `workSpace` must be a table of at least 1024 unsigned */ size_t HUF_compress1X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable); size_t HUF_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */ size_t HUF_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */ -size_t HUF_decompress1X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable); +size_t HUF_decompress1X_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); +size_t HUF_decompress1X2_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */ +size_t HUF_decompress1X4_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */ + +size_t HUF_decompress1X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable); /**< automatic selection of sing or double symbol decoder, based on DTable */ size_t HUF_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable); size_t HUF_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable); - #endif /* HUF_STATIC_LINKING_ONLY */
--- a/contrib/python-zstandard/zstd/common/mem.h Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd/common/mem.h Sat Jan 14 19:41:43 2017 -0800 @@ -55,14 +55,16 @@ typedef int32_t S32; typedef uint64_t U64; typedef int64_t S64; + typedef intptr_t iPtrDiff; #else - typedef unsigned char BYTE; + typedef unsigned char BYTE; typedef unsigned short U16; typedef signed short S16; typedef unsigned int U32; typedef signed int S32; typedef unsigned long long U64; typedef signed long long S64; + typedef ptrdiff_t iPtrDiff; #endif
--- a/contrib/python-zstandard/zstd/common/zbuff.h Sat Jan 14 20:05:15 2017 +0530 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,191 +0,0 @@ -/** - * Copyright (c) 2016-present, Yann Collet, Facebook, Inc. - * All rights reserved. - * - * This source code is licensed under the BSD-style license found in the - * LICENSE file in the root directory of this source tree. An additional grant - * of patent rights can be found in the PATENTS file in the same directory. - */ - -/* *************************************************************** -* NOTES/WARNINGS -*****************************************************************/ -/* The streaming API defined here will soon be deprecated by the -* new one in 'zstd.h'; consider migrating towards newer streaming -* API. See 'lib/README.md'. -*****************************************************************/ - -#ifndef ZSTD_BUFFERED_H_23987 -#define ZSTD_BUFFERED_H_23987 - -#if defined (__cplusplus) -extern "C" { -#endif - -/* ************************************* -* Dependencies -***************************************/ -#include <stddef.h> /* size_t */ - - -/* *************************************************************** -* Compiler specifics -*****************************************************************/ -/* ZSTD_DLL_EXPORT : -* Enable exporting of functions when building a Windows DLL */ -#if defined(_WIN32) && defined(ZSTD_DLL_EXPORT) && (ZSTD_DLL_EXPORT==1) -# define ZSTDLIB_API __declspec(dllexport) -#else -# define ZSTDLIB_API -#endif - - -/* ************************************* -* Streaming functions -***************************************/ -/* This is the easier "buffered" streaming API, -* using an internal buffer to lift all restrictions on user-provided buffers -* which can be any size, any place, for both input and output. -* ZBUFF and ZSTD are 100% interoperable, -* frames created by one can be decoded by the other one */ - -typedef struct ZBUFF_CCtx_s ZBUFF_CCtx; -ZSTDLIB_API ZBUFF_CCtx* ZBUFF_createCCtx(void); -ZSTDLIB_API size_t ZBUFF_freeCCtx(ZBUFF_CCtx* cctx); - -ZSTDLIB_API size_t ZBUFF_compressInit(ZBUFF_CCtx* cctx, int compressionLevel); -ZSTDLIB_API size_t ZBUFF_compressInitDictionary(ZBUFF_CCtx* cctx, const void* dict, size_t dictSize, int compressionLevel); - -ZSTDLIB_API size_t ZBUFF_compressContinue(ZBUFF_CCtx* cctx, void* dst, size_t* dstCapacityPtr, const void* src, size_t* srcSizePtr); -ZSTDLIB_API size_t ZBUFF_compressFlush(ZBUFF_CCtx* cctx, void* dst, size_t* dstCapacityPtr); -ZSTDLIB_API size_t ZBUFF_compressEnd(ZBUFF_CCtx* cctx, void* dst, size_t* dstCapacityPtr); - -/*-************************************************* -* Streaming compression - howto -* -* A ZBUFF_CCtx object is required to track streaming operation. -* Use ZBUFF_createCCtx() and ZBUFF_freeCCtx() to create/release resources. -* ZBUFF_CCtx objects can be reused multiple times. -* -* Start by initializing ZBUF_CCtx. -* Use ZBUFF_compressInit() to start a new compression operation. -* Use ZBUFF_compressInitDictionary() for a compression which requires a dictionary. -* -* Use ZBUFF_compressContinue() repetitively to consume input stream. -* *srcSizePtr and *dstCapacityPtr can be any size. -* The function will report how many bytes were read or written within *srcSizePtr and *dstCapacityPtr. -* Note that it may not consume the entire input, in which case it's up to the caller to present again remaining data. -* The content of `dst` will be overwritten (up to *dstCapacityPtr) at each call, so save its content if it matters or change @dst . -* @return : a hint to preferred nb of bytes to use as input for next function call (it's just a hint, to improve latency) -* or an error code, which can be tested using ZBUFF_isError(). -* -* At any moment, it's possible to flush whatever data remains within buffer, using ZBUFF_compressFlush(). -* The nb of bytes written into `dst` will be reported into *dstCapacityPtr. -* Note that the function cannot output more than *dstCapacityPtr, -* therefore, some content might still be left into internal buffer if *dstCapacityPtr is too small. -* @return : nb of bytes still present into internal buffer (0 if it's empty) -* or an error code, which can be tested using ZBUFF_isError(). -* -* ZBUFF_compressEnd() instructs to finish a frame. -* It will perform a flush and write frame epilogue. -* The epilogue is required for decoders to consider a frame completed. -* Similar to ZBUFF_compressFlush(), it may not be able to output the entire internal buffer content if *dstCapacityPtr is too small. -* In which case, call again ZBUFF_compressFlush() to complete the flush. -* @return : nb of bytes still present into internal buffer (0 if it's empty) -* or an error code, which can be tested using ZBUFF_isError(). -* -* Hint : _recommended buffer_ sizes (not compulsory) : ZBUFF_recommendedCInSize() / ZBUFF_recommendedCOutSize() -* input : ZBUFF_recommendedCInSize==128 KB block size is the internal unit, use this value to reduce intermediate stages (better latency) -* output : ZBUFF_recommendedCOutSize==ZSTD_compressBound(128 KB) + 3 + 3 : ensures it's always possible to write/flush/end a full block. Skip some buffering. -* By using both, it ensures that input will be entirely consumed, and output will always contain the result, reducing intermediate buffering. -* **************************************************/ - - -typedef struct ZBUFF_DCtx_s ZBUFF_DCtx; -ZSTDLIB_API ZBUFF_DCtx* ZBUFF_createDCtx(void); -ZSTDLIB_API size_t ZBUFF_freeDCtx(ZBUFF_DCtx* dctx); - -ZSTDLIB_API size_t ZBUFF_decompressInit(ZBUFF_DCtx* dctx); -ZSTDLIB_API size_t ZBUFF_decompressInitDictionary(ZBUFF_DCtx* dctx, const void* dict, size_t dictSize); - -ZSTDLIB_API size_t ZBUFF_decompressContinue(ZBUFF_DCtx* dctx, - void* dst, size_t* dstCapacityPtr, - const void* src, size_t* srcSizePtr); - -/*-*************************************************************************** -* Streaming decompression howto -* -* A ZBUFF_DCtx object is required to track streaming operations. -* Use ZBUFF_createDCtx() and ZBUFF_freeDCtx() to create/release resources. -* Use ZBUFF_decompressInit() to start a new decompression operation, -* or ZBUFF_decompressInitDictionary() if decompression requires a dictionary. -* Note that ZBUFF_DCtx objects can be re-init multiple times. -* -* Use ZBUFF_decompressContinue() repetitively to consume your input. -* *srcSizePtr and *dstCapacityPtr can be any size. -* The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr. -* Note that it may not consume the entire input, in which case it's up to the caller to present remaining input again. -* The content of `dst` will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters, or change `dst`. -* @return : 0 when a frame is completely decoded and fully flushed, -* 1 when there is still some data left within internal buffer to flush, -* >1 when more data is expected, with value being a suggested next input size (it's just a hint, which helps latency), -* or an error code, which can be tested using ZBUFF_isError(). -* -* Hint : recommended buffer sizes (not compulsory) : ZBUFF_recommendedDInSize() and ZBUFF_recommendedDOutSize() -* output : ZBUFF_recommendedDOutSize== 128 KB block size is the internal unit, it ensures it's always possible to write a full block when decoded. -* input : ZBUFF_recommendedDInSize == 128KB + 3; -* just follow indications from ZBUFF_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 . -* *******************************************************************************/ - - -/* ************************************* -* Tool functions -***************************************/ -ZSTDLIB_API unsigned ZBUFF_isError(size_t errorCode); -ZSTDLIB_API const char* ZBUFF_getErrorName(size_t errorCode); - -/** Functions below provide recommended buffer sizes for Compression or Decompression operations. -* These sizes are just hints, they tend to offer better latency */ -ZSTDLIB_API size_t ZBUFF_recommendedCInSize(void); -ZSTDLIB_API size_t ZBUFF_recommendedCOutSize(void); -ZSTDLIB_API size_t ZBUFF_recommendedDInSize(void); -ZSTDLIB_API size_t ZBUFF_recommendedDOutSize(void); - - -#ifdef ZBUFF_STATIC_LINKING_ONLY - -/* ==================================================================================== - * The definitions in this section are considered experimental. - * They should never be used in association with a dynamic library, as they may change in the future. - * They are provided for advanced usages. - * Use them only in association with static linking. - * ==================================================================================== */ - -/*--- Dependency ---*/ -#define ZSTD_STATIC_LINKING_ONLY /* ZSTD_parameters, ZSTD_customMem */ -#include "zstd.h" - - -/*--- Custom memory allocator ---*/ -/*! ZBUFF_createCCtx_advanced() : - * Create a ZBUFF compression context using external alloc and free functions */ -ZSTDLIB_API ZBUFF_CCtx* ZBUFF_createCCtx_advanced(ZSTD_customMem customMem); - -/*! ZBUFF_createDCtx_advanced() : - * Create a ZBUFF decompression context using external alloc and free functions */ -ZSTDLIB_API ZBUFF_DCtx* ZBUFF_createDCtx_advanced(ZSTD_customMem customMem); - - -/*--- Advanced Streaming Initialization ---*/ -ZSTDLIB_API size_t ZBUFF_compressInit_advanced(ZBUFF_CCtx* zbc, - const void* dict, size_t dictSize, - ZSTD_parameters params, unsigned long long pledgedSrcSize); - -#endif /* ZBUFF_STATIC_LINKING_ONLY */ - - -#if defined (__cplusplus) -} -#endif - -#endif /* ZSTD_BUFFERED_H_23987 */
--- a/contrib/python-zstandard/zstd/common/zstd_common.c Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd/common/zstd_common.c Sat Jan 14 19:41:43 2017 -0800 @@ -16,7 +16,6 @@ #include "error_private.h" #define ZSTD_STATIC_LINKING_ONLY #include "zstd.h" /* declaration of ZSTD_isError, ZSTD_getErrorName, ZSTD_getErrorCode, ZSTD_getErrorString, ZSTD_versionNumber */ -#include "zbuff.h" /* declaration of ZBUFF_isError, ZBUFF_getErrorName */ /*-**************************************** @@ -44,16 +43,11 @@ * provides error code string from enum */ const char* ZSTD_getErrorString(ZSTD_ErrorCode code) { return ERR_getErrorName(code); } - -/* ************************************************************** -* ZBUFF Error Management -****************************************************************/ +/* --- ZBUFF Error Management (deprecated) --- */ unsigned ZBUFF_isError(size_t errorCode) { return ERR_isError(errorCode); } - const char* ZBUFF_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); } - /*=************************************************************** * Custom allocator ****************************************************************/
--- a/contrib/python-zstandard/zstd/common/zstd_internal.h Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd/common/zstd_internal.h Sat Jan 14 19:41:43 2017 -0800 @@ -147,7 +147,7 @@ /*! ZSTD_wildcopy() : * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */ #define WILDCOPY_OVERLENGTH 8 -MEM_STATIC void ZSTD_wildcopy(void* dst, const void* src, size_t length) +MEM_STATIC void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length) { const BYTE* ip = (const BYTE*)src; BYTE* op = (BYTE*)dst; @@ -222,6 +222,7 @@ U32 log2litSum; U32 log2offCodeSum; U32 factor; + U32 staticPrices; U32 cachedPrice; U32 cachedLitLength; const BYTE* cachedLiterals; @@ -234,7 +235,9 @@ /* custom memory allocation functions */ void* ZSTD_defaultAllocFunction(void* opaque, size_t size); void ZSTD_defaultFreeFunction(void* opaque, void* address); +#ifndef ZSTD_DLL_IMPORT static const ZSTD_customMem defaultCustomMem = { ZSTD_defaultAllocFunction, ZSTD_defaultFreeFunction, NULL }; +#endif void* ZSTD_malloc(size_t size, ZSTD_customMem customMem); void ZSTD_free(void* ptr, ZSTD_customMem customMem);
--- a/contrib/python-zstandard/zstd/compress/fse_compress.c Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd/compress/fse_compress.c Sat Jan 14 19:41:43 2017 -0800 @@ -71,12 +71,6 @@ /* ************************************************************** -* Complex types -****************************************************************/ -typedef U32 CTable_max_t[FSE_CTABLE_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)]; - - -/* ************************************************************** * Templates ****************************************************************/ /* @@ -100,7 +94,13 @@ /* Function templates */ -size_t FSE_buildCTable(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) + +/* FSE_buildCTable_wksp() : + * Same as FSE_buildCTable(), but using an externally allocated scratch buffer (`workSpace`). + * wkspSize should be sized to handle worst case situation, which is `1<<max_tableLog * sizeof(FSE_FUNCTION_TYPE)` + * workSpace must also be properly aligned with FSE_FUNCTION_TYPE requirements + */ +size_t FSE_buildCTable_wksp(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize) { U32 const tableSize = 1 << tableLog; U32 const tableMask = tableSize - 1; @@ -111,10 +111,11 @@ U32 const step = FSE_TABLESTEP(tableSize); U32 cumul[FSE_MAX_SYMBOL_VALUE+2]; - FSE_FUNCTION_TYPE tableSymbol[FSE_MAX_TABLESIZE]; /* memset() is not necessary, even if static analyzer complain about it */ + FSE_FUNCTION_TYPE* const tableSymbol = (FSE_FUNCTION_TYPE*)workSpace; U32 highThreshold = tableSize-1; /* CTable header */ + if (((size_t)1 << tableLog) * sizeof(FSE_FUNCTION_TYPE) > wkspSize) return ERROR(tableLog_tooLarge); tableU16[-2] = (U16) tableLog; tableU16[-1] = (U16) maxSymbolValue; @@ -181,6 +182,13 @@ } +size_t FSE_buildCTable(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) +{ + FSE_FUNCTION_TYPE tableSymbol[FSE_MAX_TABLESIZE]; /* memset() is not necessary, even if static analyzer complain about it */ + return FSE_buildCTable_wksp(ct, normalizedCounter, maxSymbolValue, tableLog, tableSymbol, sizeof(tableSymbol)); +} + + #ifndef FSE_COMMONDEFS_ONLY @@ -189,7 +197,7 @@ ****************************************************************/ size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog) { - size_t maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3; + size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3; return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND; /* maxSymbolValue==0 ? use default */ } @@ -300,21 +308,20 @@ * Counting histogram ****************************************************************/ /*! FSE_count_simple - This function just counts byte values within `src`, - and store the histogram into table `count`. - This function is unsafe : it doesn't check that all values within `src` can fit into `count`. + This function counts byte values within `src`, and store the histogram into table `count`. + It doesn't use any additional memory. + But this function is unsafe : it doesn't check that all values within `src` can fit into `count`. For this reason, prefer using a table `count` with 256 elements. @return : count of most numerous element */ -static size_t FSE_count_simple(unsigned* count, unsigned* maxSymbolValuePtr, - const void* src, size_t srcSize) +size_t FSE_count_simple(unsigned* count, unsigned* maxSymbolValuePtr, + const void* src, size_t srcSize) { const BYTE* ip = (const BYTE*)src; const BYTE* const end = ip + srcSize; unsigned maxSymbolValue = *maxSymbolValuePtr; unsigned max=0; - memset(count, 0, (maxSymbolValue+1)*sizeof(*count)); if (srcSize==0) { *maxSymbolValuePtr = 0; return 0; } @@ -329,20 +336,24 @@ } -static size_t FSE_count_parallel(unsigned* count, unsigned* maxSymbolValuePtr, +/* FSE_count_parallel_wksp() : + * Same as FSE_count_parallel(), but using an externally provided scratch buffer. + * `workSpace` size must be a minimum of `1024 * sizeof(unsigned)`` */ +static size_t FSE_count_parallel_wksp( + unsigned* count, unsigned* maxSymbolValuePtr, const void* source, size_t sourceSize, - unsigned checkMax) + unsigned checkMax, unsigned* const workSpace) { const BYTE* ip = (const BYTE*)source; const BYTE* const iend = ip+sourceSize; unsigned maxSymbolValue = *maxSymbolValuePtr; unsigned max=0; - + U32* const Counting1 = workSpace; + U32* const Counting2 = Counting1 + 256; + U32* const Counting3 = Counting2 + 256; + U32* const Counting4 = Counting3 + 256; - U32 Counting1[256] = { 0 }; - U32 Counting2[256] = { 0 }; - U32 Counting3[256] = { 0 }; - U32 Counting4[256] = { 0 }; + memset(Counting1, 0, 4*256*sizeof(unsigned)); /* safety checks */ if (!sourceSize) { @@ -388,31 +399,51 @@ if (Counting1[s]) return ERROR(maxSymbolValue_tooSmall); } } - { U32 s; for (s=0; s<=maxSymbolValue; s++) { - count[s] = Counting1[s] + Counting2[s] + Counting3[s] + Counting4[s]; - if (count[s] > max) max = count[s]; - }} + { U32 s; for (s=0; s<=maxSymbolValue; s++) { + count[s] = Counting1[s] + Counting2[s] + Counting3[s] + Counting4[s]; + if (count[s] > max) max = count[s]; + } } while (!count[maxSymbolValue]) maxSymbolValue--; *maxSymbolValuePtr = maxSymbolValue; return (size_t)max; } +/* FSE_countFast_wksp() : + * Same as FSE_countFast(), but using an externally provided scratch buffer. + * `workSpace` size must be table of >= `1024` unsigned */ +size_t FSE_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr, + const void* source, size_t sourceSize, unsigned* workSpace) +{ + if (sourceSize < 1500) return FSE_count_simple(count, maxSymbolValuePtr, source, sourceSize); + return FSE_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, 0, workSpace); +} + /* fast variant (unsafe : won't check if src contains values beyond count[] limit) */ size_t FSE_countFast(unsigned* count, unsigned* maxSymbolValuePtr, const void* source, size_t sourceSize) { - if (sourceSize < 1500) return FSE_count_simple(count, maxSymbolValuePtr, source, sourceSize); - return FSE_count_parallel(count, maxSymbolValuePtr, source, sourceSize, 0); + unsigned tmpCounters[1024]; + return FSE_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, tmpCounters); +} + +/* FSE_count_wksp() : + * Same as FSE_count(), but using an externally provided scratch buffer. + * `workSpace` size must be table of >= `1024` unsigned */ +size_t FSE_count_wksp(unsigned* count, unsigned* maxSymbolValuePtr, + const void* source, size_t sourceSize, unsigned* workSpace) +{ + if (*maxSymbolValuePtr < 255) + return FSE_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, 1, workSpace); + *maxSymbolValuePtr = 255; + return FSE_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace); } size_t FSE_count(unsigned* count, unsigned* maxSymbolValuePtr, - const void* source, size_t sourceSize) + const void* src, size_t srcSize) { - if (*maxSymbolValuePtr <255) - return FSE_count_parallel(count, maxSymbolValuePtr, source, sourceSize, 1); - *maxSymbolValuePtr = 255; - return FSE_countFast(count, maxSymbolValuePtr, source, sourceSize); + unsigned tmpCounters[1024]; + return FSE_count_wksp(count, maxSymbolValuePtr, src, srcSize, tmpCounters); } @@ -428,14 +459,10 @@ `FSE_symbolCompressionTransform symbolTT[maxSymbolValue+1];` // This size is variable Allocation is manual (C standard does not support variable-size structures). */ - size_t FSE_sizeof_CTable (unsigned maxSymbolValue, unsigned tableLog) { - size_t size; - FSE_STATIC_ASSERT((size_t)FSE_CTABLE_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)*4 >= sizeof(CTable_max_t)); /* A compilation error here means FSE_CTABLE_SIZE_U32 is not large enough */ - if (tableLog > FSE_MAX_TABLELOG) return ERROR(GENERIC); - size = FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32); - return size; + if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); + return FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32); } FSE_CTable* FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog) @@ -486,7 +513,7 @@ U32 ToDistribute; /* Init */ - U32 lowThreshold = (U32)(total >> tableLog); + U32 const lowThreshold = (U32)(total >> tableLog); U32 lowOne = (U32)((total * 3) >> (tableLog + 1)); for (s=0; s<=maxSymbolValue; s++) { @@ -534,17 +561,16 @@ return 0; } - { - U64 const vStepLog = 62 - tableLog; + { U64 const vStepLog = 62 - tableLog; U64 const mid = (1ULL << (vStepLog-1)) - 1; U64 const rStep = ((((U64)1<<vStepLog) * ToDistribute) + mid) / total; /* scale on remaining */ U64 tmpTotal = mid; for (s=0; s<=maxSymbolValue; s++) { if (norm[s]==-2) { - U64 end = tmpTotal + (count[s] * rStep); - U32 sStart = (U32)(tmpTotal >> vStepLog); - U32 sEnd = (U32)(end >> vStepLog); - U32 weight = sEnd - sStart; + U64 const end = tmpTotal + (count[s] * rStep); + U32 const sStart = (U32)(tmpTotal >> vStepLog); + U32 const sEnd = (U32)(end >> vStepLog); + U32 const weight = sEnd - sStart; if (weight < 1) return ERROR(GENERIC); norm[s] = (short)weight; @@ -566,7 +592,6 @@ if (tableLog < FSE_minTableLog(total, maxSymbolValue)) return ERROR(GENERIC); /* Too small tableLog, compression potentially impossible */ { U32 const rtbTable[] = { 0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 }; - U64 const scale = 62 - tableLog; U64 const step = ((U64)1<<62) / total; /* <== here, one division ! */ U64 const vStep = 1ULL<<(scale-20); @@ -594,7 +619,7 @@ } } if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) { /* corner case, need another normalization method */ - size_t errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue); + size_t const errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue); if (FSE_isError(errorCode)) return errorCode; } else normalizedCounter[largest] += (short)stillToDistribute; @@ -643,17 +668,15 @@ /* Build Symbol Transformation Table */ { const U32 deltaNbBits = (nbBits << 16) - (1 << nbBits); - for (s=0; s<=maxSymbolValue; s++) { symbolTT[s].deltaNbBits = deltaNbBits; symbolTT[s].deltaFindState = s-1; } } - return 0; } -/* fake FSE_CTable, for rle (100% always same symbol) input */ +/* fake FSE_CTable, for rle input (always same symbol) */ size_t FSE_buildCTable_rle (FSE_CTable* ct, BYTE symbolValue) { void* ptr = ct; @@ -685,14 +708,13 @@ const BYTE* const iend = istart + srcSize; const BYTE* ip=iend; - BIT_CStream_t bitC; FSE_CState_t CState1, CState2; /* init */ if (srcSize <= 2) return 0; - { size_t const errorCode = BIT_initCStream(&bitC, dst, dstSize); - if (FSE_isError(errorCode)) return 0; } + { size_t const initError = BIT_initCStream(&bitC, dst, dstSize); + if (FSE_isError(initError)) return 0; /* not enough space available to write a bitstream */ } #define FSE_FLUSHBITS(s) (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s)) @@ -715,7 +737,7 @@ } /* 2 or 4 encoding per loop */ - for ( ; ip>istart ; ) { + while ( ip>istart ) { FSE_encodeSymbol(&bitC, &CState2, *--ip); @@ -741,7 +763,7 @@ const void* src, size_t srcSize, const FSE_CTable* ct) { - const unsigned fast = (dstSize >= FSE_BLOCKBOUND(srcSize)); + unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize)); if (fast) return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 1); @@ -752,58 +774,76 @@ size_t FSE_compressBound(size_t size) { return FSE_COMPRESSBOUND(size); } -size_t FSE_compress2 (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog) +#define CHECK_V_F(e, f) size_t const e = f; if (ERR_isError(e)) return f +#define CHECK_F(f) { CHECK_V_F(_var_err__, f); } + +/* FSE_compress_wksp() : + * Same as FSE_compress2(), but using an externally allocated scratch buffer (`workSpace`). + * `wkspSize` size must be `(1<<tableLog)`. + */ +size_t FSE_compress_wksp (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize) { - const BYTE* const istart = (const BYTE*) src; - const BYTE* ip = istart; - BYTE* const ostart = (BYTE*) dst; BYTE* op = ostart; BYTE* const oend = ostart + dstSize; U32 count[FSE_MAX_SYMBOL_VALUE+1]; S16 norm[FSE_MAX_SYMBOL_VALUE+1]; - CTable_max_t ct; - size_t errorCode; + FSE_CTable* CTable = (FSE_CTable*)workSpace; + size_t const CTableSize = FSE_CTABLE_SIZE_U32(tableLog, maxSymbolValue); + void* scratchBuffer = (void*)(CTable + CTableSize); + size_t const scratchBufferSize = wkspSize - (CTableSize * sizeof(FSE_CTable)); /* init conditions */ - if (srcSize <= 1) return 0; /* Uncompressible */ + if (wkspSize < FSE_WKSP_SIZE_U32(tableLog, maxSymbolValue)) return ERROR(tableLog_tooLarge); + if (srcSize <= 1) return 0; /* Not compressible */ if (!maxSymbolValue) maxSymbolValue = FSE_MAX_SYMBOL_VALUE; if (!tableLog) tableLog = FSE_DEFAULT_TABLELOG; /* Scan input and build symbol stats */ - errorCode = FSE_count (count, &maxSymbolValue, ip, srcSize); - if (FSE_isError(errorCode)) return errorCode; - if (errorCode == srcSize) return 1; - if (errorCode == 1) return 0; /* each symbol only present once */ - if (errorCode < (srcSize >> 7)) return 0; /* Heuristic : not compressible enough */ + { CHECK_V_F(maxCount, FSE_count(count, &maxSymbolValue, src, srcSize) ); + if (maxCount == srcSize) return 1; /* only a single symbol in src : rle */ + if (maxCount == 1) return 0; /* each symbol present maximum once => not compressible */ + if (maxCount < (srcSize >> 7)) return 0; /* Heuristic : not compressible enough */ + } tableLog = FSE_optimalTableLog(tableLog, srcSize, maxSymbolValue); - errorCode = FSE_normalizeCount (norm, tableLog, count, srcSize, maxSymbolValue); - if (FSE_isError(errorCode)) return errorCode; + CHECK_F( FSE_normalizeCount(norm, tableLog, count, srcSize, maxSymbolValue) ); /* Write table description header */ - errorCode = FSE_writeNCount (op, oend-op, norm, maxSymbolValue, tableLog); - if (FSE_isError(errorCode)) return errorCode; - op += errorCode; + { CHECK_V_F(nc_err, FSE_writeNCount(op, oend-op, norm, maxSymbolValue, tableLog) ); + op += nc_err; + } /* Compress */ - errorCode = FSE_buildCTable (ct, norm, maxSymbolValue, tableLog); - if (FSE_isError(errorCode)) return errorCode; - errorCode = FSE_compress_usingCTable(op, oend - op, ip, srcSize, ct); - if (errorCode == 0) return 0; /* not enough space for compressed data */ - op += errorCode; + CHECK_F( FSE_buildCTable_wksp(CTable, norm, maxSymbolValue, tableLog, scratchBuffer, scratchBufferSize) ); + { CHECK_V_F(cSize, FSE_compress_usingCTable(op, oend - op, src, srcSize, CTable) ); + if (cSize == 0) return 0; /* not enough space for compressed data */ + op += cSize; + } /* check compressibility */ - if ( (size_t)(op-ostart) >= srcSize-1 ) - return 0; + if ( (size_t)(op-ostart) >= srcSize-1 ) return 0; return op-ostart; } -size_t FSE_compress (void* dst, size_t dstSize, const void* src, size_t srcSize) +typedef struct { + FSE_CTable CTable_max[FSE_CTABLE_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)]; + BYTE scratchBuffer[1 << FSE_MAX_TABLELOG]; +} fseWkspMax_t; + +size_t FSE_compress2 (void* dst, size_t dstCapacity, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog) { - return FSE_compress2(dst, dstSize, src, (U32)srcSize, FSE_MAX_SYMBOL_VALUE, FSE_DEFAULT_TABLELOG); + fseWkspMax_t scratchBuffer; + FSE_STATIC_ASSERT(sizeof(scratchBuffer) >= FSE_WKSP_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)); /* compilation failures here means scratchBuffer is not large enough */ + if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); + return FSE_compress_wksp(dst, dstCapacity, src, srcSize, maxSymbolValue, tableLog, &scratchBuffer, sizeof(scratchBuffer)); +} + +size_t FSE_compress (void* dst, size_t dstCapacity, const void* src, size_t srcSize) +{ + return FSE_compress2(dst, dstCapacity, src, srcSize, FSE_MAX_SYMBOL_VALUE, FSE_DEFAULT_TABLELOG); }
--- a/contrib/python-zstandard/zstd/compress/huf_compress.c Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd/compress/huf_compress.c Sat Jan 14 19:41:43 2017 -0800 @@ -56,6 +56,8 @@ * Error Management ****************************************************************/ #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ +#define CHECK_V_F(e, f) size_t const e = f; if (ERR_isError(e)) return f +#define CHECK_F(f) { CHECK_V_F(_var_err__, f); } /* ************************************************************** @@ -70,31 +72,73 @@ /* ******************************************************* * HUF : Huffman block compression *********************************************************/ +/* HUF_compressWeights() : + * Same as FSE_compress(), but dedicated to huff0's weights compression. + * The use case needs much less stack memory. + * Note : all elements within weightTable are supposed to be <= HUF_TABLELOG_MAX. + */ +#define MAX_FSE_TABLELOG_FOR_HUFF_HEADER 6 +size_t HUF_compressWeights (void* dst, size_t dstSize, const void* weightTable, size_t wtSize) +{ + BYTE* const ostart = (BYTE*) dst; + BYTE* op = ostart; + BYTE* const oend = ostart + dstSize; + + U32 maxSymbolValue = HUF_TABLELOG_MAX; + U32 tableLog = MAX_FSE_TABLELOG_FOR_HUFF_HEADER; + + FSE_CTable CTable[FSE_CTABLE_SIZE_U32(MAX_FSE_TABLELOG_FOR_HUFF_HEADER, HUF_TABLELOG_MAX)]; + BYTE scratchBuffer[1<<MAX_FSE_TABLELOG_FOR_HUFF_HEADER]; + + U32 count[HUF_TABLELOG_MAX+1]; + S16 norm[HUF_TABLELOG_MAX+1]; + + /* init conditions */ + if (wtSize <= 1) return 0; /* Not compressible */ + + /* Scan input and build symbol stats */ + { CHECK_V_F(maxCount, FSE_count_simple(count, &maxSymbolValue, weightTable, wtSize) ); + if (maxCount == wtSize) return 1; /* only a single symbol in src : rle */ + if (maxCount == 1) return 0; /* each symbol present maximum once => not compressible */ + } + + tableLog = FSE_optimalTableLog(tableLog, wtSize, maxSymbolValue); + CHECK_F( FSE_normalizeCount(norm, tableLog, count, wtSize, maxSymbolValue) ); + + /* Write table description header */ + { CHECK_V_F(hSize, FSE_writeNCount(op, oend-op, norm, maxSymbolValue, tableLog) ); + op += hSize; + } + + /* Compress */ + CHECK_F( FSE_buildCTable_wksp(CTable, norm, maxSymbolValue, tableLog, scratchBuffer, sizeof(scratchBuffer)) ); + { CHECK_V_F(cSize, FSE_compress_usingCTable(op, oend - op, weightTable, wtSize, CTable) ); + if (cSize == 0) return 0; /* not enough space for compressed data */ + op += cSize; + } + + return op-ostart; +} + + struct HUF_CElt_s { U16 val; BYTE nbBits; }; /* typedef'd to HUF_CElt within "huf.h" */ -typedef struct nodeElt_s { - U32 count; - U16 parent; - BYTE byte; - BYTE nbBits; -} nodeElt; - /*! HUF_writeCTable() : `CTable` : huffman tree to save, using huf representation. @return : size of saved CTable */ size_t HUF_writeCTable (void* dst, size_t maxDstSize, const HUF_CElt* CTable, U32 maxSymbolValue, U32 huffLog) { - BYTE bitsToWeight[HUF_TABLELOG_MAX + 1]; + BYTE bitsToWeight[HUF_TABLELOG_MAX + 1]; /* precomputed conversion table */ BYTE huffWeight[HUF_SYMBOLVALUE_MAX]; BYTE* op = (BYTE*)dst; U32 n; /* check conditions */ - if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(GENERIC); + if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(maxSymbolValue_tooLarge); /* convert to weight */ bitsToWeight[0] = 0; @@ -103,38 +147,33 @@ for (n=0; n<maxSymbolValue; n++) huffWeight[n] = bitsToWeight[CTable[n].nbBits]; - { size_t const size = FSE_compress(op+1, maxDstSize-1, huffWeight, maxSymbolValue); - if (FSE_isError(size)) return size; - if ((size>1) & (size < maxSymbolValue/2)) { /* FSE compressed */ - op[0] = (BYTE)size; - return size+1; - } - } + /* attempt weights compression by FSE */ + { CHECK_V_F(hSize, HUF_compressWeights(op+1, maxDstSize-1, huffWeight, maxSymbolValue) ); + if ((hSize>1) & (hSize < maxSymbolValue/2)) { /* FSE compressed */ + op[0] = (BYTE)hSize; + return hSize+1; + } } - /* raw values */ - if (maxSymbolValue > (256-128)) return ERROR(GENERIC); /* should not happen */ + /* write raw values as 4-bits (max : 15) */ + if (maxSymbolValue > (256-128)) return ERROR(GENERIC); /* should not happen : likely means source cannot be compressed */ if (((maxSymbolValue+1)/2) + 1 > maxDstSize) return ERROR(dstSize_tooSmall); /* not enough space within dst buffer */ op[0] = (BYTE)(128 /*special case*/ + (maxSymbolValue-1)); - huffWeight[maxSymbolValue] = 0; /* to be sure it doesn't cause issue in final combination */ + huffWeight[maxSymbolValue] = 0; /* to be sure it doesn't cause msan issue in final combination */ for (n=0; n<maxSymbolValue; n+=2) op[(n/2)+1] = (BYTE)((huffWeight[n] << 4) + huffWeight[n+1]); return ((maxSymbolValue+1)/2) + 1; - } size_t HUF_readCTable (HUF_CElt* CTable, U32 maxSymbolValue, const void* src, size_t srcSize) { - BYTE huffWeight[HUF_SYMBOLVALUE_MAX + 1]; + BYTE huffWeight[HUF_SYMBOLVALUE_MAX + 1]; /* init not required, even though some static analyzer may complain */ U32 rankVal[HUF_TABLELOG_ABSOLUTEMAX + 1]; /* large enough for values from 0 to 16 */ U32 tableLog = 0; - size_t readSize; U32 nbSymbols = 0; - /*memset(huffWeight, 0, sizeof(huffWeight));*/ /* is not necessary, even though some analyzer complain ... */ /* get symbol weights */ - readSize = HUF_readStats(huffWeight, HUF_SYMBOLVALUE_MAX+1, rankVal, &nbSymbols, &tableLog, src, srcSize); - if (HUF_isError(readSize)) return readSize; + CHECK_V_F(readSize, HUF_readStats(huffWeight, HUF_SYMBOLVALUE_MAX+1, rankVal, &nbSymbols, &tableLog, src, srcSize)); /* check result */ if (tableLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge); @@ -174,6 +213,13 @@ } +typedef struct nodeElt_s { + U32 count; + U16 parent; + BYTE byte; + BYTE nbBits; +} nodeElt; + static U32 HUF_setMaxHeight(nodeElt* huffNode, U32 lastNonNull, U32 maxNbBits) { const U32 largestBits = huffNode[lastNonNull].nbBits; @@ -279,20 +325,26 @@ } +/** HUF_buildCTable_wksp() : + * Same as HUF_buildCTable(), but using externally allocated scratch buffer. + * `workSpace` must be aligned on 4-bytes boundaries, and be at least as large as a table of 1024 unsigned. + */ #define STARTNODE (HUF_SYMBOLVALUE_MAX+1) -size_t HUF_buildCTable (HUF_CElt* tree, const U32* count, U32 maxSymbolValue, U32 maxNbBits) +typedef nodeElt huffNodeTable[2*HUF_SYMBOLVALUE_MAX+1 +1]; +size_t HUF_buildCTable_wksp (HUF_CElt* tree, const U32* count, U32 maxSymbolValue, U32 maxNbBits, void* workSpace, size_t wkspSize) { - nodeElt huffNode0[2*HUF_SYMBOLVALUE_MAX+1 +1]; - nodeElt* huffNode = huffNode0 + 1; + nodeElt* const huffNode0 = (nodeElt*)workSpace; + nodeElt* const huffNode = huffNode0+1; U32 n, nonNullRank; int lowS, lowN; U16 nodeNb = STARTNODE; U32 nodeRoot; /* safety checks */ + if (wkspSize < sizeof(huffNodeTable)) return ERROR(GENERIC); /* workSpace is not large enough */ if (maxNbBits == 0) maxNbBits = HUF_TABLELOG_DEFAULT; if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(GENERIC); - memset(huffNode0, 0, sizeof(huffNode0)); + memset(huffNode0, 0, sizeof(huffNodeTable)); /* sort, decreasing order */ HUF_sort(huffNode, count, maxSymbolValue); @@ -305,7 +357,7 @@ huffNode[lowS].parent = huffNode[lowS-1].parent = nodeNb; nodeNb++; lowS-=2; for (n=nodeNb; n<=nodeRoot; n++) huffNode[n].count = (U32)(1U<<30); - huffNode0[0].count = (U32)(1U<<31); + huffNode0[0].count = (U32)(1U<<31); /* fake entry, strong barrier */ /* create parents */ while (nodeNb <= nodeRoot) { @@ -348,6 +400,15 @@ return maxNbBits; } +/** HUF_buildCTable() : + * Note : count is used before tree is written, so they can safely overlap + */ +size_t HUF_buildCTable (HUF_CElt* tree, const U32* count, U32 maxSymbolValue, U32 maxNbBits) +{ + huffNodeTable nodeTable; + return HUF_buildCTable_wksp(tree, count, maxSymbolValue, maxNbBits, nodeTable, sizeof(nodeTable)); +} + static void HUF_encodeSymbol(BIT_CStream_t* bitCPtr, U32 symbol, const HUF_CElt* CTable) { BIT_addBitsFast(bitCPtr, CTable[symbol].val, CTable[symbol].nbBits); @@ -375,8 +436,8 @@ /* init */ if (dstSize < 8) return 0; /* not enough space to compress */ - { size_t const errorCode = BIT_initCStream(&bitC, op, oend-op); - if (HUF_isError(errorCode)) return 0; } + { size_t const initErr = BIT_initCStream(&bitC, op, oend-op); + if (HUF_isError(initErr)) return 0; } n = srcSize & ~3; /* join to mod 4 */ switch (srcSize & 3) @@ -419,32 +480,28 @@ if (srcSize < 12) return 0; /* no saving possible : too small input */ op += 6; /* jumpTable */ - { size_t const cSize = HUF_compress1X_usingCTable(op, oend-op, ip, segmentSize, CTable); - if (HUF_isError(cSize)) return cSize; + { CHECK_V_F(cSize, HUF_compress1X_usingCTable(op, oend-op, ip, segmentSize, CTable) ); if (cSize==0) return 0; MEM_writeLE16(ostart, (U16)cSize); op += cSize; } ip += segmentSize; - { size_t const cSize = HUF_compress1X_usingCTable(op, oend-op, ip, segmentSize, CTable); - if (HUF_isError(cSize)) return cSize; + { CHECK_V_F(cSize, HUF_compress1X_usingCTable(op, oend-op, ip, segmentSize, CTable) ); if (cSize==0) return 0; MEM_writeLE16(ostart+2, (U16)cSize); op += cSize; } ip += segmentSize; - { size_t const cSize = HUF_compress1X_usingCTable(op, oend-op, ip, segmentSize, CTable); - if (HUF_isError(cSize)) return cSize; + { CHECK_V_F(cSize, HUF_compress1X_usingCTable(op, oend-op, ip, segmentSize, CTable) ); if (cSize==0) return 0; MEM_writeLE16(ostart+4, (U16)cSize); op += cSize; } ip += segmentSize; - { size_t const cSize = HUF_compress1X_usingCTable(op, oend-op, ip, iend-ip, CTable); - if (HUF_isError(cSize)) return cSize; + { CHECK_V_F(cSize, HUF_compress1X_usingCTable(op, oend-op, ip, iend-ip, CTable) ); if (cSize==0) return 0; op += cSize; } @@ -453,20 +510,25 @@ } +/* `workSpace` must a table of at least 1024 unsigned */ static size_t HUF_compress_internal ( void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, - unsigned singleStream) + unsigned singleStream, + void* workSpace, size_t wkspSize) { BYTE* const ostart = (BYTE*)dst; BYTE* const oend = ostart + dstSize; BYTE* op = ostart; - U32 count[HUF_SYMBOLVALUE_MAX+1]; - HUF_CElt CTable[HUF_SYMBOLVALUE_MAX+1]; + union { + U32 count[HUF_SYMBOLVALUE_MAX+1]; + HUF_CElt CTable[HUF_SYMBOLVALUE_MAX+1]; + } table; /* `count` can overlap with `CTable`; saves 1 KB */ /* checks & inits */ + if (wkspSize < sizeof(huffNodeTable)) return ERROR(GENERIC); if (!srcSize) return 0; /* Uncompressed (note : 1 means rle, so first byte must be correct) */ if (!dstSize) return 0; /* cannot fit within dst budget */ if (srcSize > HUF_BLOCKSIZE_MAX) return ERROR(srcSize_wrong); /* current block size limit */ @@ -475,30 +537,27 @@ if (!huffLog) huffLog = HUF_TABLELOG_DEFAULT; /* Scan input and build symbol stats */ - { size_t const largest = FSE_count (count, &maxSymbolValue, (const BYTE*)src, srcSize); - if (HUF_isError(largest)) return largest; + { CHECK_V_F(largest, FSE_count_wksp (table.count, &maxSymbolValue, (const BYTE*)src, srcSize, (U32*)workSpace) ); if (largest == srcSize) { *ostart = ((const BYTE*)src)[0]; return 1; } /* single symbol, rle */ if (largest <= (srcSize >> 7)+1) return 0; /* Fast heuristic : not compressible enough */ } /* Build Huffman Tree */ huffLog = HUF_optimalTableLog(huffLog, srcSize, maxSymbolValue); - { size_t const maxBits = HUF_buildCTable (CTable, count, maxSymbolValue, huffLog); - if (HUF_isError(maxBits)) return maxBits; + { CHECK_V_F(maxBits, HUF_buildCTable_wksp (table.CTable, table.count, maxSymbolValue, huffLog, workSpace, wkspSize) ); huffLog = (U32)maxBits; } /* Write table description header */ - { size_t const hSize = HUF_writeCTable (op, dstSize, CTable, maxSymbolValue, huffLog); - if (HUF_isError(hSize)) return hSize; + { CHECK_V_F(hSize, HUF_writeCTable (op, dstSize, table.CTable, maxSymbolValue, huffLog) ); if (hSize + 12 >= srcSize) return 0; /* not useful to try compression */ op += hSize; } /* Compress */ { size_t const cSize = (singleStream) ? - HUF_compress1X_usingCTable(op, oend - op, src, srcSize, CTable) : /* single segment */ - HUF_compress4X_usingCTable(op, oend - op, src, srcSize, CTable); + HUF_compress1X_usingCTable(op, oend - op, src, srcSize, table.CTable) : /* single segment */ + HUF_compress4X_usingCTable(op, oend - op, src, srcSize, table.CTable); if (HUF_isError(cSize)) return cSize; if (cSize==0) return 0; /* uncompressible */ op += cSize; @@ -512,21 +571,38 @@ } +size_t HUF_compress1X_wksp (void* dst, size_t dstSize, + const void* src, size_t srcSize, + unsigned maxSymbolValue, unsigned huffLog, + void* workSpace, size_t wkspSize) +{ + return HUF_compress_internal(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, 1 /* single stream */, workSpace, wkspSize); +} + size_t HUF_compress1X (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog) { - return HUF_compress_internal(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, 1); + unsigned workSpace[1024]; + return HUF_compress1X_wksp(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, workSpace, sizeof(workSpace)); +} + +size_t HUF_compress4X_wksp (void* dst, size_t dstSize, + const void* src, size_t srcSize, + unsigned maxSymbolValue, unsigned huffLog, + void* workSpace, size_t wkspSize) +{ + return HUF_compress_internal(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, 0 /* 4 streams */, workSpace, wkspSize); } size_t HUF_compress2 (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog) { - return HUF_compress_internal(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, 0); + unsigned workSpace[1024]; + return HUF_compress4X_wksp(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, workSpace, sizeof(workSpace)); } - size_t HUF_compress (void* dst, size_t maxDstSize, const void* src, size_t srcSize) { return HUF_compress2(dst, maxDstSize, src, (U32)srcSize, 255, HUF_TABLELOG_DEFAULT);
--- a/contrib/python-zstandard/zstd/compress/zbuff_compress.c Sat Jan 14 20:05:15 2017 +0530 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,319 +0,0 @@ -/** - * Copyright (c) 2016-present, Yann Collet, Facebook, Inc. - * All rights reserved. - * - * This source code is licensed under the BSD-style license found in the - * LICENSE file in the root directory of this source tree. An additional grant - * of patent rights can be found in the PATENTS file in the same directory. - */ - - - -/* ************************************* -* Dependencies -***************************************/ -#include <stdlib.h> -#include "error_private.h" -#include "zstd_internal.h" /* MIN, ZSTD_BLOCKHEADERSIZE, defaultCustomMem */ -#define ZBUFF_STATIC_LINKING_ONLY -#include "zbuff.h" - - -/* ************************************* -* Constants -***************************************/ -static size_t const ZBUFF_endFrameSize = ZSTD_BLOCKHEADERSIZE; - - -/*-*********************************************************** -* Streaming compression -* -* A ZBUFF_CCtx object is required to track streaming operation. -* Use ZBUFF_createCCtx() and ZBUFF_freeCCtx() to create/release resources. -* Use ZBUFF_compressInit() to start a new compression operation. -* ZBUFF_CCtx objects can be reused multiple times. -* -* Use ZBUFF_compressContinue() repetitively to consume your input. -* *srcSizePtr and *dstCapacityPtr can be any size. -* The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr. -* Note that it may not consume the entire input, in which case it's up to the caller to call again the function with remaining input. -* The content of dst will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters or change dst . -* @return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to improve latency) -* or an error code, which can be tested using ZBUFF_isError(). -* -* ZBUFF_compressFlush() can be used to instruct ZBUFF to compress and output whatever remains within its buffer. -* Note that it will not output more than *dstCapacityPtr. -* Therefore, some content might still be left into its internal buffer if dst buffer is too small. -* @return : nb of bytes still present into internal buffer (0 if it's empty) -* or an error code, which can be tested using ZBUFF_isError(). -* -* ZBUFF_compressEnd() instructs to finish a frame. -* It will perform a flush and write frame epilogue. -* Similar to ZBUFF_compressFlush(), it may not be able to output the entire internal buffer content if *dstCapacityPtr is too small. -* @return : nb of bytes still present into internal buffer (0 if it's empty) -* or an error code, which can be tested using ZBUFF_isError(). -* -* Hint : recommended buffer sizes (not compulsory) -* input : ZSTD_BLOCKSIZE_MAX (128 KB), internal unit size, it improves latency to use this value. -* output : ZSTD_compressBound(ZSTD_BLOCKSIZE_MAX) + ZSTD_blockHeaderSize + ZBUFF_endFrameSize : ensures it's always possible to write/flush/end a full block at best speed. -* ***********************************************************/ - -typedef enum { ZBUFFcs_init, ZBUFFcs_load, ZBUFFcs_flush, ZBUFFcs_final } ZBUFF_cStage; - -/* *** Resources *** */ -struct ZBUFF_CCtx_s { - ZSTD_CCtx* zc; - char* inBuff; - size_t inBuffSize; - size_t inToCompress; - size_t inBuffPos; - size_t inBuffTarget; - size_t blockSize; - char* outBuff; - size_t outBuffSize; - size_t outBuffContentSize; - size_t outBuffFlushedSize; - ZBUFF_cStage stage; - U32 checksum; - U32 frameEnded; - ZSTD_customMem customMem; -}; /* typedef'd tp ZBUFF_CCtx within "zbuff.h" */ - -ZBUFF_CCtx* ZBUFF_createCCtx(void) -{ - return ZBUFF_createCCtx_advanced(defaultCustomMem); -} - -ZBUFF_CCtx* ZBUFF_createCCtx_advanced(ZSTD_customMem customMem) -{ - ZBUFF_CCtx* zbc; - - if (!customMem.customAlloc && !customMem.customFree) - customMem = defaultCustomMem; - - if (!customMem.customAlloc || !customMem.customFree) - return NULL; - - zbc = (ZBUFF_CCtx*)customMem.customAlloc(customMem.opaque, sizeof(ZBUFF_CCtx)); - if (zbc==NULL) return NULL; - memset(zbc, 0, sizeof(ZBUFF_CCtx)); - memcpy(&zbc->customMem, &customMem, sizeof(ZSTD_customMem)); - zbc->zc = ZSTD_createCCtx_advanced(customMem); - if (zbc->zc == NULL) { ZBUFF_freeCCtx(zbc); return NULL; } - return zbc; -} - -size_t ZBUFF_freeCCtx(ZBUFF_CCtx* zbc) -{ - if (zbc==NULL) return 0; /* support free on NULL */ - ZSTD_freeCCtx(zbc->zc); - if (zbc->inBuff) zbc->customMem.customFree(zbc->customMem.opaque, zbc->inBuff); - if (zbc->outBuff) zbc->customMem.customFree(zbc->customMem.opaque, zbc->outBuff); - zbc->customMem.customFree(zbc->customMem.opaque, zbc); - return 0; -} - - -/* ====== Initialization ====== */ - -size_t ZBUFF_compressInit_advanced(ZBUFF_CCtx* zbc, - const void* dict, size_t dictSize, - ZSTD_parameters params, unsigned long long pledgedSrcSize) -{ - /* allocate buffers */ - { size_t const neededInBuffSize = (size_t)1 << params.cParams.windowLog; - if (zbc->inBuffSize < neededInBuffSize) { - zbc->inBuffSize = neededInBuffSize; - zbc->customMem.customFree(zbc->customMem.opaque, zbc->inBuff); /* should not be necessary */ - zbc->inBuff = (char*)zbc->customMem.customAlloc(zbc->customMem.opaque, neededInBuffSize); - if (zbc->inBuff == NULL) return ERROR(memory_allocation); - } - zbc->blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, neededInBuffSize); - } - if (zbc->outBuffSize < ZSTD_compressBound(zbc->blockSize)+1) { - zbc->outBuffSize = ZSTD_compressBound(zbc->blockSize)+1; - zbc->customMem.customFree(zbc->customMem.opaque, zbc->outBuff); /* should not be necessary */ - zbc->outBuff = (char*)zbc->customMem.customAlloc(zbc->customMem.opaque, zbc->outBuffSize); - if (zbc->outBuff == NULL) return ERROR(memory_allocation); - } - - { size_t const errorCode = ZSTD_compressBegin_advanced(zbc->zc, dict, dictSize, params, pledgedSrcSize); - if (ZSTD_isError(errorCode)) return errorCode; } - - zbc->inToCompress = 0; - zbc->inBuffPos = 0; - zbc->inBuffTarget = zbc->blockSize; - zbc->outBuffContentSize = zbc->outBuffFlushedSize = 0; - zbc->stage = ZBUFFcs_load; - zbc->checksum = params.fParams.checksumFlag > 0; - zbc->frameEnded = 0; - return 0; /* ready to go */ -} - - -size_t ZBUFF_compressInitDictionary(ZBUFF_CCtx* zbc, const void* dict, size_t dictSize, int compressionLevel) -{ - ZSTD_parameters const params = ZSTD_getParams(compressionLevel, 0, dictSize); - return ZBUFF_compressInit_advanced(zbc, dict, dictSize, params, 0); -} - -size_t ZBUFF_compressInit(ZBUFF_CCtx* zbc, int compressionLevel) -{ - return ZBUFF_compressInitDictionary(zbc, NULL, 0, compressionLevel); -} - - -/* internal util function */ -MEM_STATIC size_t ZBUFF_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize) -{ - size_t const length = MIN(dstCapacity, srcSize); - memcpy(dst, src, length); - return length; -} - - -/* ====== Compression ====== */ - -typedef enum { zbf_gather, zbf_flush, zbf_end } ZBUFF_flush_e; - -static size_t ZBUFF_compressContinue_generic(ZBUFF_CCtx* zbc, - void* dst, size_t* dstCapacityPtr, - const void* src, size_t* srcSizePtr, - ZBUFF_flush_e const flush) -{ - U32 someMoreWork = 1; - const char* const istart = (const char*)src; - const char* const iend = istart + *srcSizePtr; - const char* ip = istart; - char* const ostart = (char*)dst; - char* const oend = ostart + *dstCapacityPtr; - char* op = ostart; - - while (someMoreWork) { - switch(zbc->stage) - { - case ZBUFFcs_init: return ERROR(init_missing); /* call ZBUFF_compressInit() first ! */ - - case ZBUFFcs_load: - /* complete inBuffer */ - { size_t const toLoad = zbc->inBuffTarget - zbc->inBuffPos; - size_t const loaded = ZBUFF_limitCopy(zbc->inBuff + zbc->inBuffPos, toLoad, ip, iend-ip); - zbc->inBuffPos += loaded; - ip += loaded; - if ( (zbc->inBuffPos==zbc->inToCompress) || (!flush && (toLoad != loaded)) ) { - someMoreWork = 0; break; /* not enough input to get a full block : stop there, wait for more */ - } } - /* compress current block (note : this stage cannot be stopped in the middle) */ - { void* cDst; - size_t cSize; - size_t const iSize = zbc->inBuffPos - zbc->inToCompress; - size_t oSize = oend-op; - if (oSize >= ZSTD_compressBound(iSize)) - cDst = op; /* compress directly into output buffer (avoid flush stage) */ - else - cDst = zbc->outBuff, oSize = zbc->outBuffSize; - cSize = (flush == zbf_end) ? - ZSTD_compressEnd(zbc->zc, cDst, oSize, zbc->inBuff + zbc->inToCompress, iSize) : - ZSTD_compressContinue(zbc->zc, cDst, oSize, zbc->inBuff + zbc->inToCompress, iSize); - if (ZSTD_isError(cSize)) return cSize; - if (flush == zbf_end) zbc->frameEnded = 1; - /* prepare next block */ - zbc->inBuffTarget = zbc->inBuffPos + zbc->blockSize; - if (zbc->inBuffTarget > zbc->inBuffSize) - zbc->inBuffPos = 0, zbc->inBuffTarget = zbc->blockSize; /* note : inBuffSize >= blockSize */ - zbc->inToCompress = zbc->inBuffPos; - if (cDst == op) { op += cSize; break; } /* no need to flush */ - zbc->outBuffContentSize = cSize; - zbc->outBuffFlushedSize = 0; - zbc->stage = ZBUFFcs_flush; /* continue to flush stage */ - } - - case ZBUFFcs_flush: - { size_t const toFlush = zbc->outBuffContentSize - zbc->outBuffFlushedSize; - size_t const flushed = ZBUFF_limitCopy(op, oend-op, zbc->outBuff + zbc->outBuffFlushedSize, toFlush); - op += flushed; - zbc->outBuffFlushedSize += flushed; - if (toFlush!=flushed) { someMoreWork = 0; break; } /* dst too small to store flushed data : stop there */ - zbc->outBuffContentSize = zbc->outBuffFlushedSize = 0; - zbc->stage = ZBUFFcs_load; - break; - } - - case ZBUFFcs_final: - someMoreWork = 0; /* do nothing */ - break; - - default: - return ERROR(GENERIC); /* impossible */ - } - } - - *srcSizePtr = ip - istart; - *dstCapacityPtr = op - ostart; - if (zbc->frameEnded) return 0; - { size_t hintInSize = zbc->inBuffTarget - zbc->inBuffPos; - if (hintInSize==0) hintInSize = zbc->blockSize; - return hintInSize; - } -} - -size_t ZBUFF_compressContinue(ZBUFF_CCtx* zbc, - void* dst, size_t* dstCapacityPtr, - const void* src, size_t* srcSizePtr) -{ - return ZBUFF_compressContinue_generic(zbc, dst, dstCapacityPtr, src, srcSizePtr, zbf_gather); -} - - - -/* ====== Finalize ====== */ - -size_t ZBUFF_compressFlush(ZBUFF_CCtx* zbc, void* dst, size_t* dstCapacityPtr) -{ - size_t srcSize = 0; - ZBUFF_compressContinue_generic(zbc, dst, dstCapacityPtr, &srcSize, &srcSize, zbf_flush); /* use a valid src address instead of NULL */ - return zbc->outBuffContentSize - zbc->outBuffFlushedSize; -} - - -size_t ZBUFF_compressEnd(ZBUFF_CCtx* zbc, void* dst, size_t* dstCapacityPtr) -{ - BYTE* const ostart = (BYTE*)dst; - BYTE* const oend = ostart + *dstCapacityPtr; - BYTE* op = ostart; - - if (zbc->stage != ZBUFFcs_final) { - /* flush whatever remains */ - size_t outSize = *dstCapacityPtr; - size_t srcSize = 0; - size_t const notEnded = ZBUFF_compressContinue_generic(zbc, dst, &outSize, &srcSize, &srcSize, zbf_end); /* use a valid address instead of NULL */ - size_t const remainingToFlush = zbc->outBuffContentSize - zbc->outBuffFlushedSize; - op += outSize; - if (remainingToFlush) { - *dstCapacityPtr = op-ostart; - return remainingToFlush + ZBUFF_endFrameSize + (zbc->checksum * 4); - } - /* create epilogue */ - zbc->stage = ZBUFFcs_final; - zbc->outBuffContentSize = !notEnded ? 0 : - ZSTD_compressEnd(zbc->zc, zbc->outBuff, zbc->outBuffSize, NULL, 0); /* write epilogue into outBuff */ - } - - /* flush epilogue */ - { size_t const toFlush = zbc->outBuffContentSize - zbc->outBuffFlushedSize; - size_t const flushed = ZBUFF_limitCopy(op, oend-op, zbc->outBuff + zbc->outBuffFlushedSize, toFlush); - op += flushed; - zbc->outBuffFlushedSize += flushed; - *dstCapacityPtr = op-ostart; - if (toFlush==flushed) zbc->stage = ZBUFFcs_init; /* end reached */ - return toFlush - flushed; - } -} - - - -/* ************************************* -* Tool functions -***************************************/ -size_t ZBUFF_recommendedCInSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX; } -size_t ZBUFF_recommendedCOutSize(void) { return ZSTD_compressBound(ZSTD_BLOCKSIZE_ABSOLUTEMAX) + ZSTD_blockHeaderSize + ZBUFF_endFrameSize; }
--- a/contrib/python-zstandard/zstd/compress/zstd_compress.c Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd/compress/zstd_compress.c Sat Jan 14 19:41:43 2017 -0800 @@ -33,6 +33,7 @@ /*-************************************* * Helper functions ***************************************/ +#define ZSTD_STATIC_ASSERT(c) { enum { ZSTD_static_assert = 1/(int)(!!(c)) }; } size_t ZSTD_compressBound(size_t srcSize) { return FSE_compressBound(srcSize) + 12; } @@ -82,6 +83,7 @@ FSE_CTable offcodeCTable [FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)]; FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)]; FSE_CTable litlengthCTable [FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)]; + unsigned tmpCounters[1024]; }; ZSTD_CCtx* ZSTD_createCCtx(void) @@ -147,6 +149,14 @@ } +/** ZSTD_cycleLog() : + * condition for correct operation : hashLog > 1 */ +static U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat) +{ + U32 const btScale = ((U32)strat >= (U32)ZSTD_btlazy2); + return hashLog - btScale; +} + /** ZSTD_adjustCParams() : optimize `cPar` for a given input (`srcSize` and `dictSize`). mostly downsizing to reduce memory consumption and initialization. @@ -165,9 +175,9 @@ if (cPar.windowLog > srcLog) cPar.windowLog = srcLog; } } if (cPar.hashLog > cPar.windowLog) cPar.hashLog = cPar.windowLog; - { U32 const btPlus = (cPar.strategy == ZSTD_btlazy2) | (cPar.strategy == ZSTD_btopt) | (cPar.strategy == ZSTD_btopt2); - U32 const maxChainLog = cPar.windowLog+btPlus; - if (cPar.chainLog > maxChainLog) cPar.chainLog = maxChainLog; } /* <= ZSTD_CHAINLOG_MAX */ + { U32 const cycleLog = ZSTD_cycleLog(cPar.chainLog, cPar.strategy); + if (cycleLog > cPar.windowLog) cPar.chainLog -= (cycleLog - cPar.windowLog); + } if (cPar.windowLog < ZSTD_WINDOWLOG_ABSOLUTEMIN) cPar.windowLog = ZSTD_WINDOWLOG_ABSOLUTEMIN; /* required for frame header */ @@ -470,8 +480,8 @@ singleStream = 1; cLitSize = HUF_compress1X_usingCTable(ostart+lhSize, dstCapacity-lhSize, src, srcSize, zc->hufTable); } else { - cLitSize = singleStream ? HUF_compress1X(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11) - : HUF_compress2 (ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11); + cLitSize = singleStream ? HUF_compress1X_wksp(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11, zc->tmpCounters, sizeof(zc->tmpCounters)) + : HUF_compress4X_wksp(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11, zc->tmpCounters, sizeof(zc->tmpCounters)); } if ((cLitSize==0) | (cLitSize >= srcSize - minGain)) @@ -566,6 +576,7 @@ BYTE* op = ostart; size_t const nbSeq = seqStorePtr->sequences - seqStorePtr->sequencesStart; BYTE* seqHead; + BYTE scratchBuffer[1<<MAX(MLFSELog,LLFSELog)]; /* Compress literals */ { const BYTE* const literals = seqStorePtr->litStart; @@ -593,7 +604,7 @@ /* CTable for Literal Lengths */ { U32 max = MaxLL; - size_t const mostFrequent = FSE_countFast(count, &max, llCodeTable, nbSeq); + size_t const mostFrequent = FSE_countFast_wksp(count, &max, llCodeTable, nbSeq, zc->tmpCounters); if ((mostFrequent == nbSeq) && (nbSeq > 2)) { *op++ = llCodeTable[0]; FSE_buildCTable_rle(CTable_LitLength, (BYTE)max); @@ -601,7 +612,7 @@ } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) { LLtype = set_repeat; } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (LL_defaultNormLog-1)))) { - FSE_buildCTable(CTable_LitLength, LL_defaultNorm, MaxLL, LL_defaultNormLog); + FSE_buildCTable_wksp(CTable_LitLength, LL_defaultNorm, MaxLL, LL_defaultNormLog, scratchBuffer, sizeof(scratchBuffer)); LLtype = set_basic; } else { size_t nbSeq_1 = nbSeq; @@ -611,13 +622,13 @@ { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog); /* overflow protected */ if (FSE_isError(NCountSize)) return ERROR(GENERIC); op += NCountSize; } - FSE_buildCTable(CTable_LitLength, norm, max, tableLog); + FSE_buildCTable_wksp(CTable_LitLength, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer)); LLtype = set_compressed; } } /* CTable for Offsets */ { U32 max = MaxOff; - size_t const mostFrequent = FSE_countFast(count, &max, ofCodeTable, nbSeq); + size_t const mostFrequent = FSE_countFast_wksp(count, &max, ofCodeTable, nbSeq, zc->tmpCounters); if ((mostFrequent == nbSeq) && (nbSeq > 2)) { *op++ = ofCodeTable[0]; FSE_buildCTable_rle(CTable_OffsetBits, (BYTE)max); @@ -625,7 +636,7 @@ } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) { Offtype = set_repeat; } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (OF_defaultNormLog-1)))) { - FSE_buildCTable(CTable_OffsetBits, OF_defaultNorm, MaxOff, OF_defaultNormLog); + FSE_buildCTable_wksp(CTable_OffsetBits, OF_defaultNorm, MaxOff, OF_defaultNormLog, scratchBuffer, sizeof(scratchBuffer)); Offtype = set_basic; } else { size_t nbSeq_1 = nbSeq; @@ -635,13 +646,13 @@ { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog); /* overflow protected */ if (FSE_isError(NCountSize)) return ERROR(GENERIC); op += NCountSize; } - FSE_buildCTable(CTable_OffsetBits, norm, max, tableLog); + FSE_buildCTable_wksp(CTable_OffsetBits, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer)); Offtype = set_compressed; } } /* CTable for MatchLengths */ { U32 max = MaxML; - size_t const mostFrequent = FSE_countFast(count, &max, mlCodeTable, nbSeq); + size_t const mostFrequent = FSE_countFast_wksp(count, &max, mlCodeTable, nbSeq, zc->tmpCounters); if ((mostFrequent == nbSeq) && (nbSeq > 2)) { *op++ = *mlCodeTable; FSE_buildCTable_rle(CTable_MatchLength, (BYTE)max); @@ -649,7 +660,7 @@ } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) { MLtype = set_repeat; } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (ML_defaultNormLog-1)))) { - FSE_buildCTable(CTable_MatchLength, ML_defaultNorm, MaxML, ML_defaultNormLog); + FSE_buildCTable_wksp(CTable_MatchLength, ML_defaultNorm, MaxML, ML_defaultNormLog, scratchBuffer, sizeof(scratchBuffer)); MLtype = set_basic; } else { size_t nbSeq_1 = nbSeq; @@ -659,7 +670,7 @@ { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog); /* overflow protected */ if (FSE_isError(NCountSize)) return ERROR(GENERIC); op += NCountSize; } - FSE_buildCTable(CTable_MatchLength, norm, max, tableLog); + FSE_buildCTable_wksp(CTable_MatchLength, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer)); MLtype = set_compressed; } } @@ -739,8 +750,8 @@ { #if 0 /* for debug */ static const BYTE* g_start = NULL; - const U32 pos = (U32)(literals - g_start); - if (g_start==NULL) g_start = literals; + const U32 pos = (U32)((const BYTE*)literals - g_start); + if (g_start==NULL) g_start = (const BYTE*)literals; //if ((pos > 1) && (pos < 50000)) printf("Cpos %6u :%5u literals & match %3u bytes at distance %6u \n", pos, (U32)litLength, (U32)matchCode+MINMATCH, (U32)offsetCode); @@ -1482,8 +1493,9 @@ hashTable[h] = current; /* Update Hash Table */ while (nbCompares-- && (matchIndex > windowLow)) { - U32* nextPtr = bt + 2*(matchIndex & btMask); + U32* const nextPtr = bt + 2*(matchIndex & btMask); size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ + #ifdef ZSTD_C_PREDICT /* note : can create issues when hlog small <= 11 */ const U32* predictPtr = bt + 2*((matchIndex-1) & btMask); /* written this way, as bt is a roll buffer */ if (matchIndex == predictedSmall) { @@ -1579,7 +1591,7 @@ hashTable[h] = current; /* Update Hash Table */ while (nbCompares-- && (matchIndex > windowLow)) { - U32* nextPtr = bt + 2*(matchIndex & btMask); + U32* const nextPtr = bt + 2*(matchIndex & btMask); size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ const BYTE* match; @@ -2271,16 +2283,16 @@ if (remaining < blockSize) blockSize = remaining; /* preemptive overflow correction */ - if (cctx->lowLimit > (1<<30)) { - U32 const btplus = (cctx->params.cParams.strategy == ZSTD_btlazy2) | (cctx->params.cParams.strategy == ZSTD_btopt) | (cctx->params.cParams.strategy == ZSTD_btopt2); - U32 const chainMask = (1 << (cctx->params.cParams.chainLog - btplus)) - 1; - U32 const supLog = MAX(cctx->params.cParams.chainLog, 17 /* blockSize */); - U32 const newLowLimit = (cctx->lowLimit & chainMask) + (1 << supLog); /* preserve position % chainSize, ensure current-repcode doesn't underflow */ - U32 const correction = cctx->lowLimit - newLowLimit; + if (cctx->lowLimit > (2U<<30)) { + U32 const cycleMask = (1 << ZSTD_cycleLog(cctx->params.cParams.hashLog, cctx->params.cParams.strategy)) - 1; + U32 const current = (U32)(ip - cctx->base); + U32 const newCurrent = (current & cycleMask) + (1 << cctx->params.cParams.windowLog); + U32 const correction = current - newCurrent; + ZSTD_STATIC_ASSERT(ZSTD_WINDOWLOG_MAX_64 <= 30); ZSTD_reduceIndex(cctx, correction); cctx->base += correction; cctx->dictBase += correction; - cctx->lowLimit = newLowLimit; + cctx->lowLimit -= correction; cctx->dictLimit -= correction; if (cctx->nextToUpdate < correction) cctx->nextToUpdate = 0; else cctx->nextToUpdate -= correction; @@ -2506,6 +2518,7 @@ const BYTE* const dictEnd = dictPtr + dictSize; short offcodeNCount[MaxOff+1]; unsigned offcodeMaxValue = MaxOff; + BYTE scratchBuffer[1<<MAX(MLFSELog,LLFSELog)]; { size_t const hufHeaderSize = HUF_readCTable(cctx->hufTable, 255, dict, dictSize); if (HUF_isError(hufHeaderSize)) return ERROR(dictionary_corrupted); @@ -2517,7 +2530,7 @@ if (FSE_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted); if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted); /* Defer checking offcodeMaxValue because we need to know the size of the dictionary content */ - CHECK_E (FSE_buildCTable(cctx->offcodeCTable, offcodeNCount, offcodeMaxValue, offcodeLog), dictionary_corrupted); + CHECK_E (FSE_buildCTable_wksp(cctx->offcodeCTable, offcodeNCount, offcodeMaxValue, offcodeLog, scratchBuffer, sizeof(scratchBuffer)), dictionary_corrupted); dictPtr += offcodeHeaderSize; } @@ -2528,7 +2541,7 @@ if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted); /* Every match length code must have non-zero probability */ CHECK_F (ZSTD_checkDictNCount(matchlengthNCount, matchlengthMaxValue, MaxML)); - CHECK_E (FSE_buildCTable(cctx->matchlengthCTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog), dictionary_corrupted); + CHECK_E (FSE_buildCTable_wksp(cctx->matchlengthCTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog, scratchBuffer, sizeof(scratchBuffer)), dictionary_corrupted); dictPtr += matchlengthHeaderSize; } @@ -2539,7 +2552,7 @@ if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted); /* Every literal length code must have non-zero probability */ CHECK_F (ZSTD_checkDictNCount(litlengthNCount, litlengthMaxValue, MaxLL)); - CHECK_E(FSE_buildCTable(cctx->litlengthCTable, litlengthNCount, litlengthMaxValue, litlengthLog), dictionary_corrupted); + CHECK_E(FSE_buildCTable_wksp(cctx->litlengthCTable, litlengthNCount, litlengthMaxValue, litlengthLog, scratchBuffer, sizeof(scratchBuffer)), dictionary_corrupted); dictPtr += litlengthHeaderSize; } @@ -2695,7 +2708,7 @@ size_t ZSTD_compress_usingDict(ZSTD_CCtx* ctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, const void* dict, size_t dictSize, int compressionLevel) { - ZSTD_parameters params = ZSTD_getParams(compressionLevel, srcSize, dictSize); + ZSTD_parameters params = ZSTD_getParams(compressionLevel, srcSize, dict ? dictSize : 0); params.fParams.contentSizeFlag = 1; return ZSTD_compress_internal(ctx, dst, dstCapacity, src, srcSize, dict, dictSize, params); } @@ -2839,6 +2852,8 @@ ZSTD_cStreamStage stage; U32 checksum; U32 frameEnded; + U64 pledgedSrcSize; + U64 inputProcessed; ZSTD_parameters params; ZSTD_customMem customMem; }; /* typedef'd to ZSTD_CStream within "zstd.h" */ @@ -2896,6 +2911,8 @@ zcs->outBuffContentSize = zcs->outBuffFlushedSize = 0; zcs->stage = zcss_load; zcs->frameEnded = 0; + zcs->pledgedSrcSize = pledgedSrcSize; + zcs->inputProcessed = 0; return 0; /* ready to go */ } @@ -2948,6 +2965,12 @@ return ZSTD_initCStream_advanced(zcs, dict, dictSize, params, 0); } +size_t ZSTD_initCStream_srcSize(ZSTD_CStream* zcs, int compressionLevel, unsigned long long pledgedSrcSize) +{ + ZSTD_parameters const params = ZSTD_getParams(compressionLevel, pledgedSrcSize, 0); + return ZSTD_initCStream_advanced(zcs, NULL, 0, params, pledgedSrcSize); +} + size_t ZSTD_initCStream(ZSTD_CStream* zcs, int compressionLevel) { return ZSTD_initCStream_usingDict(zcs, NULL, 0, compressionLevel); @@ -3044,6 +3067,7 @@ *srcSizePtr = ip - istart; *dstCapacityPtr = op - ostart; + zcs->inputProcessed += *srcSizePtr; if (zcs->frameEnded) return 0; { size_t hintInSize = zcs->inBuffTarget - zcs->inBuffPos; if (hintInSize==0) hintInSize = zcs->blockSize; @@ -3088,6 +3112,9 @@ BYTE* const oend = (BYTE*)(output->dst) + output->size; BYTE* op = ostart; + if ((zcs->pledgedSrcSize) && (zcs->inputProcessed != zcs->pledgedSrcSize)) + return ERROR(srcSize_wrong); /* pledgedSrcSize not respected */ + if (zcs->stage != zcss_final) { /* flush whatever remains */ size_t srcSize = 0;
--- a/contrib/python-zstandard/zstd/compress/zstd_opt.h Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd/compress/zstd_opt.h Sat Jan 14 19:41:43 2017 -0800 @@ -15,8 +15,9 @@ #define ZSTD_OPT_H_91842398743 -#define ZSTD_FREQ_DIV 5 -#define ZSTD_MAX_PRICE (1<<30) +#define ZSTD_LITFREQ_ADD 2 +#define ZSTD_FREQ_DIV 4 +#define ZSTD_MAX_PRICE (1<<30) /*-************************************* * Price functions for optimal parser @@ -31,22 +32,32 @@ } -MEM_STATIC void ZSTD_rescaleFreqs(seqStore_t* ssPtr) +MEM_STATIC void ZSTD_rescaleFreqs(seqStore_t* ssPtr, const BYTE* src, size_t srcSize) { unsigned u; ssPtr->cachedLiterals = NULL; ssPtr->cachedPrice = ssPtr->cachedLitLength = 0; + ssPtr->staticPrices = 0; if (ssPtr->litLengthSum == 0) { - ssPtr->litSum = (2<<Litbits); + if (srcSize <= 1024) ssPtr->staticPrices = 1; + + for (u=0; u<=MaxLit; u++) + ssPtr->litFreq[u] = 0; + for (u=0; u<srcSize; u++) + ssPtr->litFreq[src[u]]++; + + ssPtr->litSum = 0; ssPtr->litLengthSum = MaxLL+1; ssPtr->matchLengthSum = MaxML+1; ssPtr->offCodeSum = (MaxOff+1); - ssPtr->matchSum = (2<<Litbits); + ssPtr->matchSum = (ZSTD_LITFREQ_ADD<<Litbits); - for (u=0; u<=MaxLit; u++) - ssPtr->litFreq[u] = 2; + for (u=0; u<=MaxLit; u++) { + ssPtr->litFreq[u] = 1 + (ssPtr->litFreq[u]>>ZSTD_FREQ_DIV); + ssPtr->litSum += ssPtr->litFreq[u]; + } for (u=0; u<=MaxLL; u++) ssPtr->litLengthFreq[u] = 1; for (u=0; u<=MaxML; u++) @@ -61,11 +72,11 @@ ssPtr->litSum = 0; for (u=0; u<=MaxLit; u++) { - ssPtr->litFreq[u] = 1 + (ssPtr->litFreq[u]>>ZSTD_FREQ_DIV); + ssPtr->litFreq[u] = 1 + (ssPtr->litFreq[u]>>(ZSTD_FREQ_DIV+1)); ssPtr->litSum += ssPtr->litFreq[u]; } for (u=0; u<=MaxLL; u++) { - ssPtr->litLengthFreq[u] = 1 + (ssPtr->litLengthFreq[u]>>ZSTD_FREQ_DIV); + ssPtr->litLengthFreq[u] = 1 + (ssPtr->litLengthFreq[u]>>(ZSTD_FREQ_DIV+1)); ssPtr->litLengthSum += ssPtr->litLengthFreq[u]; } for (u=0; u<=MaxML; u++) { @@ -73,6 +84,7 @@ ssPtr->matchLengthSum += ssPtr->matchLengthFreq[u]; ssPtr->matchSum += ssPtr->matchLengthFreq[u] * (u + 3); } + ssPtr->matchSum *= ZSTD_LITFREQ_ADD; for (u=0; u<=MaxOff; u++) { ssPtr->offCodeFreq[u] = 1 + (ssPtr->offCodeFreq[u]>>ZSTD_FREQ_DIV); ssPtr->offCodeSum += ssPtr->offCodeFreq[u]; @@ -87,6 +99,9 @@ { U32 price, u; + if (ssPtr->staticPrices) + return ZSTD_highbit32((U32)litLength+1) + (litLength*6); + if (litLength == 0) return ssPtr->log2litLengthSum - ZSTD_highbit32(ssPtr->litLengthFreq[0]+1); @@ -124,9 +139,13 @@ FORCE_INLINE U32 ZSTD_getPrice(seqStore_t* seqStorePtr, U32 litLength, const BYTE* literals, U32 offset, U32 matchLength, const int ultra) { /* offset */ + U32 price; BYTE const offCode = (BYTE)ZSTD_highbit32(offset+1); - U32 price = offCode + seqStorePtr->log2offCodeSum - ZSTD_highbit32(seqStorePtr->offCodeFreq[offCode]+1); + if (seqStorePtr->staticPrices) + return ZSTD_getLiteralPrice(seqStorePtr, litLength, literals) + ZSTD_highbit32((U32)matchLength+1) + 16 + offCode; + + price = offCode + seqStorePtr->log2offCodeSum - ZSTD_highbit32(seqStorePtr->offCodeFreq[offCode]+1); if (!ultra && offCode >= 20) price += (offCode-19)*2; /* match Length */ @@ -144,9 +163,9 @@ U32 u; /* literals */ - seqStorePtr->litSum += litLength; + seqStorePtr->litSum += litLength*ZSTD_LITFREQ_ADD; for (u=0; u < litLength; u++) - seqStorePtr->litFreq[literals[u]]++; + seqStorePtr->litFreq[literals[u]] += ZSTD_LITFREQ_ADD; /* literal Length */ { const BYTE LL_deltaCode = 19; @@ -401,7 +420,7 @@ /* init */ ctx->nextToUpdate3 = ctx->nextToUpdate; - ZSTD_rescaleFreqs(seqStorePtr); + ZSTD_rescaleFreqs(seqStorePtr, (const BYTE*)src, srcSize); ip += (ip==prefixStart); { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) rep[i]=ctx->rep[i]; } @@ -416,7 +435,7 @@ /* check repCode */ { U32 i, last_i = ZSTD_REP_CHECK + (ip==anchor); for (i=(ip == anchor); i<last_i; i++) { - const S32 repCur = ((i==ZSTD_REP_MOVE_OPT) && (ip==anchor)) ? (rep[0] - 1) : rep[i]; + const S32 repCur = (i==ZSTD_REP_MOVE_OPT) ? (rep[0] - 1) : rep[i]; if ( (repCur > 0) && (repCur < (S32)(ip-prefixStart)) && (MEM_readMINMATCH(ip, minMatch) == MEM_readMINMATCH(ip - repCur, minMatch))) { mlen = (U32)ZSTD_count(ip+minMatch, ip+minMatch-repCur, iend) + minMatch; @@ -501,7 +520,7 @@ best_mlen = minMatch; { U32 i, last_i = ZSTD_REP_CHECK + (mlen != 1); for (i=(opt[cur].mlen != 1); i<last_i; i++) { /* check rep */ - const S32 repCur = ((i==ZSTD_REP_MOVE_OPT) && (opt[cur].mlen != 1)) ? (opt[cur].rep[0] - 1) : opt[cur].rep[i]; + const S32 repCur = (i==ZSTD_REP_MOVE_OPT) ? (opt[cur].rep[0] - 1) : opt[cur].rep[i]; if ( (repCur > 0) && (repCur < (S32)(inr-prefixStart)) && (MEM_readMINMATCH(inr, minMatch) == MEM_readMINMATCH(inr - repCur, minMatch))) { mlen = (U32)ZSTD_count(inr+minMatch, inr+minMatch - repCur, iend) + minMatch; @@ -601,7 +620,7 @@ offset--; } else { if (offset != 0) { - best_off = ((offset==ZSTD_REP_MOVE_OPT) && (litLength==0)) ? (rep[0] - 1) : (rep[offset]); + best_off = (offset==ZSTD_REP_MOVE_OPT) ? (rep[0] - 1) : (rep[offset]); if (offset != 1) rep[2] = rep[1]; rep[1] = rep[0]; rep[0] = best_off; @@ -656,7 +675,7 @@ { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) rep[i]=ctx->rep[i]; } ctx->nextToUpdate3 = ctx->nextToUpdate; - ZSTD_rescaleFreqs(seqStorePtr); + ZSTD_rescaleFreqs(seqStorePtr, (const BYTE*)src, srcSize); ip += (ip==prefixStart); /* Match Loop */ @@ -671,7 +690,7 @@ /* check repCode */ { U32 i, last_i = ZSTD_REP_CHECK + (ip==anchor); for (i = (ip==anchor); i<last_i; i++) { - const S32 repCur = ((i==ZSTD_REP_MOVE_OPT) && (ip==anchor)) ? (rep[0] - 1) : rep[i]; + const S32 repCur = (i==ZSTD_REP_MOVE_OPT) ? (rep[0] - 1) : rep[i]; const U32 repIndex = (U32)(current - repCur); const BYTE* const repBase = repIndex < dictLimit ? dictBase : base; const BYTE* const repMatch = repBase + repIndex; @@ -767,7 +786,7 @@ best_mlen = minMatch; { U32 i, last_i = ZSTD_REP_CHECK + (mlen != 1); for (i = (mlen != 1); i<last_i; i++) { - const S32 repCur = ((i==ZSTD_REP_MOVE_OPT) && (opt[cur].mlen != 1)) ? (opt[cur].rep[0] - 1) : opt[cur].rep[i]; + const S32 repCur = (i==ZSTD_REP_MOVE_OPT) ? (opt[cur].rep[0] - 1) : opt[cur].rep[i]; const U32 repIndex = (U32)(current+cur - repCur); const BYTE* const repBase = repIndex < dictLimit ? dictBase : base; const BYTE* const repMatch = repBase + repIndex; @@ -873,7 +892,7 @@ offset--; } else { if (offset != 0) { - best_off = ((offset==ZSTD_REP_MOVE_OPT) && (litLength==0)) ? (rep[0] - 1) : (rep[offset]); + best_off = (offset==ZSTD_REP_MOVE_OPT) ? (rep[0] - 1) : (rep[offset]); if (offset != 1) rep[2] = rep[1]; rep[1] = rep[0]; rep[0] = best_off;
--- a/contrib/python-zstandard/zstd/decompress/huf_decompress.c Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd/decompress/huf_decompress.c Sat Jan 14 19:41:43 2017 -0800 @@ -358,13 +358,15 @@ typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t; +/* HUF_fillDTableX4Level2() : + * `rankValOrigin` must be a table of at least (HUF_TABLELOG_MAX + 1) U32 */ static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed, const U32* rankValOrigin, const int minWeight, const sortedSymbol_t* sortedSymbols, const U32 sortedListSize, U32 nbBitsBaseline, U16 baseSeq) { HUF_DEltX4 DElt; - U32 rankVal[HUF_TABLELOG_ABSOLUTEMAX + 1]; + U32 rankVal[HUF_TABLELOG_MAX + 1]; /* get pre-calculated rankVal */ memcpy(rankVal, rankValOrigin, sizeof(rankVal)); @@ -398,14 +400,14 @@ } } } -typedef U32 rankVal_t[HUF_TABLELOG_ABSOLUTEMAX][HUF_TABLELOG_ABSOLUTEMAX + 1]; +typedef U32 rankVal_t[HUF_TABLELOG_MAX][HUF_TABLELOG_MAX + 1]; static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog, const sortedSymbol_t* sortedList, const U32 sortedListSize, const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight, const U32 nbBitsBaseline) { - U32 rankVal[HUF_TABLELOG_ABSOLUTEMAX + 1]; + U32 rankVal[HUF_TABLELOG_MAX + 1]; const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */ const U32 minBits = nbBitsBaseline - maxWeight; U32 s; @@ -446,8 +448,8 @@ { BYTE weightList[HUF_SYMBOLVALUE_MAX + 1]; sortedSymbol_t sortedSymbol[HUF_SYMBOLVALUE_MAX + 1]; - U32 rankStats[HUF_TABLELOG_ABSOLUTEMAX + 1] = { 0 }; - U32 rankStart0[HUF_TABLELOG_ABSOLUTEMAX + 2] = { 0 }; + U32 rankStats[HUF_TABLELOG_MAX + 1] = { 0 }; + U32 rankStart0[HUF_TABLELOG_MAX + 2] = { 0 }; U32* const rankStart = rankStart0+1; rankVal_t rankVal; U32 tableLog, maxW, sizeOfSort, nbSymbols; @@ -458,7 +460,7 @@ HUF_DEltX4* const dt = (HUF_DEltX4*)dtPtr; HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(HUF_DTable)); /* if compilation fails here, assertion is false */ - if (maxTableLog > HUF_TABLELOG_ABSOLUTEMAX) return ERROR(tableLog_tooLarge); + if (maxTableLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge); /* memset(weightList, 0, sizeof(weightList)); */ /* is not necessary, even though some analyzer complain ... */ iSize = HUF_readStats(weightList, HUF_SYMBOLVALUE_MAX + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
--- a/contrib/python-zstandard/zstd/decompress/zbuff_decompress.c Sat Jan 14 20:05:15 2017 +0530 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,252 +0,0 @@ -/** - * Copyright (c) 2016-present, Yann Collet, Facebook, Inc. - * All rights reserved. - * - * This source code is licensed under the BSD-style license found in the - * LICENSE file in the root directory of this source tree. An additional grant - * of patent rights can be found in the PATENTS file in the same directory. - */ - - - -/* ************************************* -* Dependencies -***************************************/ -#include <stdlib.h> -#include "error_private.h" -#include "zstd_internal.h" /* MIN, ZSTD_blockHeaderSize, ZSTD_BLOCKSIZE_MAX */ -#define ZBUFF_STATIC_LINKING_ONLY -#include "zbuff.h" - - -typedef enum { ZBUFFds_init, ZBUFFds_loadHeader, - ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFF_dStage; - -/* *** Resource management *** */ -struct ZBUFF_DCtx_s { - ZSTD_DCtx* zd; - ZSTD_frameParams fParams; - ZBUFF_dStage stage; - char* inBuff; - size_t inBuffSize; - size_t inPos; - char* outBuff; - size_t outBuffSize; - size_t outStart; - size_t outEnd; - size_t blockSize; - BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX]; - size_t lhSize; - ZSTD_customMem customMem; -}; /* typedef'd to ZBUFF_DCtx within "zbuff.h" */ - - -ZBUFF_DCtx* ZBUFF_createDCtx(void) -{ - return ZBUFF_createDCtx_advanced(defaultCustomMem); -} - -ZBUFF_DCtx* ZBUFF_createDCtx_advanced(ZSTD_customMem customMem) -{ - ZBUFF_DCtx* zbd; - - if (!customMem.customAlloc && !customMem.customFree) - customMem = defaultCustomMem; - - if (!customMem.customAlloc || !customMem.customFree) - return NULL; - - zbd = (ZBUFF_DCtx*)customMem.customAlloc(customMem.opaque, sizeof(ZBUFF_DCtx)); - if (zbd==NULL) return NULL; - memset(zbd, 0, sizeof(ZBUFF_DCtx)); - memcpy(&zbd->customMem, &customMem, sizeof(ZSTD_customMem)); - zbd->zd = ZSTD_createDCtx_advanced(customMem); - if (zbd->zd == NULL) { ZBUFF_freeDCtx(zbd); return NULL; } - zbd->stage = ZBUFFds_init; - return zbd; -} - -size_t ZBUFF_freeDCtx(ZBUFF_DCtx* zbd) -{ - if (zbd==NULL) return 0; /* support free on null */ - ZSTD_freeDCtx(zbd->zd); - if (zbd->inBuff) zbd->customMem.customFree(zbd->customMem.opaque, zbd->inBuff); - if (zbd->outBuff) zbd->customMem.customFree(zbd->customMem.opaque, zbd->outBuff); - zbd->customMem.customFree(zbd->customMem.opaque, zbd); - return 0; -} - - -/* *** Initialization *** */ - -size_t ZBUFF_decompressInitDictionary(ZBUFF_DCtx* zbd, const void* dict, size_t dictSize) -{ - zbd->stage = ZBUFFds_loadHeader; - zbd->lhSize = zbd->inPos = zbd->outStart = zbd->outEnd = 0; - return ZSTD_decompressBegin_usingDict(zbd->zd, dict, dictSize); -} - -size_t ZBUFF_decompressInit(ZBUFF_DCtx* zbd) -{ - return ZBUFF_decompressInitDictionary(zbd, NULL, 0); -} - - -/* internal util function */ -MEM_STATIC size_t ZBUFF_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize) -{ - size_t const length = MIN(dstCapacity, srcSize); - memcpy(dst, src, length); - return length; -} - - -/* *** Decompression *** */ - -size_t ZBUFF_decompressContinue(ZBUFF_DCtx* zbd, - void* dst, size_t* dstCapacityPtr, - const void* src, size_t* srcSizePtr) -{ - const char* const istart = (const char*)src; - const char* const iend = istart + *srcSizePtr; - const char* ip = istart; - char* const ostart = (char*)dst; - char* const oend = ostart + *dstCapacityPtr; - char* op = ostart; - U32 someMoreWork = 1; - - while (someMoreWork) { - switch(zbd->stage) - { - case ZBUFFds_init : - return ERROR(init_missing); - - case ZBUFFds_loadHeader : - { size_t const hSize = ZSTD_getFrameParams(&(zbd->fParams), zbd->headerBuffer, zbd->lhSize); - if (ZSTD_isError(hSize)) return hSize; - if (hSize != 0) { /* need more input */ - size_t const toLoad = hSize - zbd->lhSize; /* if hSize!=0, hSize > zbd->lhSize */ - if (toLoad > (size_t)(iend-ip)) { /* not enough input to load full header */ - memcpy(zbd->headerBuffer + zbd->lhSize, ip, iend-ip); - zbd->lhSize += iend-ip; - *dstCapacityPtr = 0; - return (hSize - zbd->lhSize) + ZSTD_blockHeaderSize; /* remaining header bytes + next block header */ - } - memcpy(zbd->headerBuffer + zbd->lhSize, ip, toLoad); zbd->lhSize = hSize; ip += toLoad; - break; - } } - - /* Consume header */ - { size_t const h1Size = ZSTD_nextSrcSizeToDecompress(zbd->zd); /* == ZSTD_frameHeaderSize_min */ - size_t const h1Result = ZSTD_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer, h1Size); - if (ZSTD_isError(h1Result)) return h1Result; /* should not happen : already checked */ - if (h1Size < zbd->lhSize) { /* long header */ - size_t const h2Size = ZSTD_nextSrcSizeToDecompress(zbd->zd); - size_t const h2Result = ZSTD_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer+h1Size, h2Size); - if (ZSTD_isError(h2Result)) return h2Result; - } } - - zbd->fParams.windowSize = MAX(zbd->fParams.windowSize, 1U << ZSTD_WINDOWLOG_ABSOLUTEMIN); - - /* Frame header instruct buffer sizes */ - { size_t const blockSize = MIN(zbd->fParams.windowSize, ZSTD_BLOCKSIZE_ABSOLUTEMAX); - size_t const neededOutSize = zbd->fParams.windowSize + blockSize; - zbd->blockSize = blockSize; - if (zbd->inBuffSize < blockSize) { - zbd->customMem.customFree(zbd->customMem.opaque, zbd->inBuff); - zbd->inBuffSize = blockSize; - zbd->inBuff = (char*)zbd->customMem.customAlloc(zbd->customMem.opaque, blockSize); - if (zbd->inBuff == NULL) return ERROR(memory_allocation); - } - if (zbd->outBuffSize < neededOutSize) { - zbd->customMem.customFree(zbd->customMem.opaque, zbd->outBuff); - zbd->outBuffSize = neededOutSize; - zbd->outBuff = (char*)zbd->customMem.customAlloc(zbd->customMem.opaque, neededOutSize); - if (zbd->outBuff == NULL) return ERROR(memory_allocation); - } } - zbd->stage = ZBUFFds_read; - /* pass-through */ - - case ZBUFFds_read: - { size_t const neededInSize = ZSTD_nextSrcSizeToDecompress(zbd->zd); - if (neededInSize==0) { /* end of frame */ - zbd->stage = ZBUFFds_init; - someMoreWork = 0; - break; - } - if ((size_t)(iend-ip) >= neededInSize) { /* decode directly from src */ - const int isSkipFrame = ZSTD_isSkipFrame(zbd->zd); - size_t const decodedSize = ZSTD_decompressContinue(zbd->zd, - zbd->outBuff + zbd->outStart, (isSkipFrame ? 0 : zbd->outBuffSize - zbd->outStart), - ip, neededInSize); - if (ZSTD_isError(decodedSize)) return decodedSize; - ip += neededInSize; - if (!decodedSize && !isSkipFrame) break; /* this was just a header */ - zbd->outEnd = zbd->outStart + decodedSize; - zbd->stage = ZBUFFds_flush; - break; - } - if (ip==iend) { someMoreWork = 0; break; } /* no more input */ - zbd->stage = ZBUFFds_load; - /* pass-through */ - } - - case ZBUFFds_load: - { size_t const neededInSize = ZSTD_nextSrcSizeToDecompress(zbd->zd); - size_t const toLoad = neededInSize - zbd->inPos; /* should always be <= remaining space within inBuff */ - size_t loadedSize; - if (toLoad > zbd->inBuffSize - zbd->inPos) return ERROR(corruption_detected); /* should never happen */ - loadedSize = ZBUFF_limitCopy(zbd->inBuff + zbd->inPos, toLoad, ip, iend-ip); - ip += loadedSize; - zbd->inPos += loadedSize; - if (loadedSize < toLoad) { someMoreWork = 0; break; } /* not enough input, wait for more */ - - /* decode loaded input */ - { const int isSkipFrame = ZSTD_isSkipFrame(zbd->zd); - size_t const decodedSize = ZSTD_decompressContinue(zbd->zd, - zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart, - zbd->inBuff, neededInSize); - if (ZSTD_isError(decodedSize)) return decodedSize; - zbd->inPos = 0; /* input is consumed */ - if (!decodedSize && !isSkipFrame) { zbd->stage = ZBUFFds_read; break; } /* this was just a header */ - zbd->outEnd = zbd->outStart + decodedSize; - zbd->stage = ZBUFFds_flush; - /* pass-through */ - } } - - case ZBUFFds_flush: - { size_t const toFlushSize = zbd->outEnd - zbd->outStart; - size_t const flushedSize = ZBUFF_limitCopy(op, oend-op, zbd->outBuff + zbd->outStart, toFlushSize); - op += flushedSize; - zbd->outStart += flushedSize; - if (flushedSize == toFlushSize) { /* flush completed */ - zbd->stage = ZBUFFds_read; - if (zbd->outStart + zbd->blockSize > zbd->outBuffSize) - zbd->outStart = zbd->outEnd = 0; - break; - } - /* cannot flush everything */ - someMoreWork = 0; - break; - } - default: return ERROR(GENERIC); /* impossible */ - } } - - /* result */ - *srcSizePtr = ip-istart; - *dstCapacityPtr = op-ostart; - { size_t nextSrcSizeHint = ZSTD_nextSrcSizeToDecompress(zbd->zd); - if (!nextSrcSizeHint) return (zbd->outEnd != zbd->outStart); /* return 0 only if fully flushed too */ - nextSrcSizeHint += ZSTD_blockHeaderSize * (ZSTD_nextInputType(zbd->zd) == ZSTDnit_block); - if (zbd->inPos > nextSrcSizeHint) return ERROR(GENERIC); /* should never happen */ - nextSrcSizeHint -= zbd->inPos; /* already loaded*/ - return nextSrcSizeHint; - } -} - - -/* ************************************* -* Tool functions -***************************************/ -size_t ZBUFF_recommendedDInSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX + ZSTD_blockHeaderSize /* block header size*/ ; } -size_t ZBUFF_recommendedDOutSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX; }
--- a/contrib/python-zstandard/zstd/decompress/zstd_decompress.c Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd/decompress/zstd_decompress.c Sat Jan 14 19:41:43 2017 -0800 @@ -56,6 +56,15 @@ #endif +#if defined(_MSC_VER) +# include <mmintrin.h> /* https://msdn.microsoft.com/fr-fr/library/84szxsww(v=vs.90).aspx */ +# define ZSTD_PREFETCH(ptr) _mm_prefetch((const char*)ptr, _MM_HINT_T0) +#elif defined(__GNUC__) +# define ZSTD_PREFETCH(ptr) __builtin_prefetch(ptr, 0, 0) +#else +# define ZSTD_PREFETCH(ptr) /* disabled */ +#endif + /*-************************************* * Macros ***************************************/ @@ -104,7 +113,6 @@ U32 dictID; const BYTE* litPtr; ZSTD_customMem customMem; - size_t litBufSize; size_t litSize; size_t rleSize; BYTE litBuffer[ZSTD_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH]; @@ -193,7 +201,24 @@ * Decompression section ***************************************************************/ -/* See compression format details in : doc/zstd_compression_format.md */ +/*! ZSTD_isFrame() : + * Tells if the content of `buffer` starts with a valid Frame Identifier. + * Note : Frame Identifier is 4 bytes. If `size < 4`, @return will always be 0. + * Note 2 : Legacy Frame Identifiers are considered valid only if Legacy Support is enabled. + * Note 3 : Skippable Frame Identifiers are considered valid. */ +unsigned ZSTD_isFrame(const void* buffer, size_t size) +{ + if (size < 4) return 0; + { U32 const magic = MEM_readLE32(buffer); + if (magic == ZSTD_MAGICNUMBER) return 1; + if ((magic & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) return 1; + } +#if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT >= 1) + if (ZSTD_isLegacy(buffer, size)) return 1; +#endif + return 0; +} + /** ZSTD_frameHeaderSize() : * srcSize must be >= ZSTD_frameHeaderSize_prefix. @@ -412,10 +437,10 @@ return ERROR(corruption_detected); dctx->litPtr = dctx->litBuffer; - dctx->litBufSize = ZSTD_BLOCKSIZE_ABSOLUTEMAX+WILDCOPY_OVERLENGTH; dctx->litSize = litSize; dctx->litEntropy = 1; if (litEncType==set_compressed) dctx->HUFptr = dctx->hufTable; + memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); return litCSize + lhSize; } @@ -442,13 +467,12 @@ if (litSize+lhSize > srcSize) return ERROR(corruption_detected); memcpy(dctx->litBuffer, istart+lhSize, litSize); dctx->litPtr = dctx->litBuffer; - dctx->litBufSize = ZSTD_BLOCKSIZE_ABSOLUTEMAX+8; dctx->litSize = litSize; + memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); return lhSize+litSize; } /* direct reference into compressed stream */ dctx->litPtr = istart+lhSize; - dctx->litBufSize = srcSize-lhSize; dctx->litSize = litSize; return lhSize+litSize; } @@ -473,9 +497,8 @@ break; } if (litSize > ZSTD_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected); - memset(dctx->litBuffer, istart[lhSize], litSize); + memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH); dctx->litPtr = dctx->litBuffer; - dctx->litBufSize = ZSTD_BLOCKSIZE_ABSOLUTEMAX+WILDCOPY_OVERLENGTH; dctx->litSize = litSize; return lhSize+1; } @@ -761,6 +784,7 @@ size_t litLength; size_t matchLength; size_t offset; + const BYTE* match; } seq_t; typedef struct { @@ -769,88 +793,16 @@ FSE_DState_t stateOffb; FSE_DState_t stateML; size_t prevOffset[ZSTD_REP_NUM]; + const BYTE* base; + size_t pos; + iPtrDiff gotoDict; } seqState_t; -static seq_t ZSTD_decodeSequence(seqState_t* seqState) -{ - seq_t seq; - - U32 const llCode = FSE_peekSymbol(&seqState->stateLL); - U32 const mlCode = FSE_peekSymbol(&seqState->stateML); - U32 const ofCode = FSE_peekSymbol(&seqState->stateOffb); /* <= maxOff, by table construction */ - - U32 const llBits = LL_bits[llCode]; - U32 const mlBits = ML_bits[mlCode]; - U32 const ofBits = ofCode; - U32 const totalBits = llBits+mlBits+ofBits; - - static const U32 LL_base[MaxLL+1] = { - 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, - 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, - 0x2000, 0x4000, 0x8000, 0x10000 }; - - static const U32 ML_base[MaxML+1] = { - 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, - 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, - 35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803, - 0x1003, 0x2003, 0x4003, 0x8003, 0x10003 }; - - static const U32 OF_base[MaxOff+1] = { - 0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D, - 0xFD, 0x1FD, 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD, - 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD, - 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD }; - - /* sequence */ - { size_t offset; - if (!ofCode) - offset = 0; - else { - offset = OF_base[ofCode] + BIT_readBits(&seqState->DStream, ofBits); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */ - if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); - } - - if (ofCode <= 1) { - offset += (llCode==0); - if (offset) { - size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset]; - temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */ - if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1]; - seqState->prevOffset[1] = seqState->prevOffset[0]; - seqState->prevOffset[0] = offset = temp; - } else { - offset = seqState->prevOffset[0]; - } - } else { - seqState->prevOffset[2] = seqState->prevOffset[1]; - seqState->prevOffset[1] = seqState->prevOffset[0]; - seqState->prevOffset[0] = offset; - } - seq.offset = offset; - } - - seq.matchLength = ML_base[mlCode] + ((mlCode>31) ? BIT_readBits(&seqState->DStream, mlBits) : 0); /* <= 16 bits */ - if (MEM_32bits() && (mlBits+llBits>24)) BIT_reloadDStream(&seqState->DStream); - - seq.litLength = LL_base[llCode] + ((llCode>15) ? BIT_readBits(&seqState->DStream, llBits) : 0); /* <= 16 bits */ - if (MEM_32bits() || - (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BIT_reloadDStream(&seqState->DStream); - - /* ANS state update */ - FSE_updateState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */ - FSE_updateState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */ - if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */ - FSE_updateState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */ - - return seq; -} - - FORCE_NOINLINE size_t ZSTD_execSequenceLast7(BYTE* op, BYTE* const oend, seq_t sequence, - const BYTE** litPtr, const BYTE* const litLimit_w, + const BYTE** litPtr, const BYTE* const litLimit, const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd) { BYTE* const oLitEnd = op + sequence.litLength; @@ -862,7 +814,7 @@ /* check */ if (oMatchEnd>oend) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */ - if (iLitEnd > litLimit_w) return ERROR(corruption_detected); /* over-read beyond lit buffer */ + if (iLitEnd > litLimit) return ERROR(corruption_detected); /* over-read beyond lit buffer */ if (oLitEnd <= oend_w) return ERROR(GENERIC); /* Precondition */ /* copy literals */ @@ -894,10 +846,87 @@ } + + +static seq_t ZSTD_decodeSequence(seqState_t* seqState) +{ + seq_t seq; + + U32 const llCode = FSE_peekSymbol(&seqState->stateLL); + U32 const mlCode = FSE_peekSymbol(&seqState->stateML); + U32 const ofCode = FSE_peekSymbol(&seqState->stateOffb); /* <= maxOff, by table construction */ + + U32 const llBits = LL_bits[llCode]; + U32 const mlBits = ML_bits[mlCode]; + U32 const ofBits = ofCode; + U32 const totalBits = llBits+mlBits+ofBits; + + static const U32 LL_base[MaxLL+1] = { + 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, + 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, + 0x2000, 0x4000, 0x8000, 0x10000 }; + + static const U32 ML_base[MaxML+1] = { + 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, + 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, + 35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803, + 0x1003, 0x2003, 0x4003, 0x8003, 0x10003 }; + + static const U32 OF_base[MaxOff+1] = { + 0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D, + 0xFD, 0x1FD, 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD, + 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD, + 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD }; + + /* sequence */ + { size_t offset; + if (!ofCode) + offset = 0; + else { + offset = OF_base[ofCode] + BIT_readBitsFast(&seqState->DStream, ofBits); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */ + if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); + } + + if (ofCode <= 1) { + offset += (llCode==0); + if (offset) { + size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset]; + temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */ + if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1]; + seqState->prevOffset[1] = seqState->prevOffset[0]; + seqState->prevOffset[0] = offset = temp; + } else { + offset = seqState->prevOffset[0]; + } + } else { + seqState->prevOffset[2] = seqState->prevOffset[1]; + seqState->prevOffset[1] = seqState->prevOffset[0]; + seqState->prevOffset[0] = offset; + } + seq.offset = offset; + } + + seq.matchLength = ML_base[mlCode] + ((mlCode>31) ? BIT_readBitsFast(&seqState->DStream, mlBits) : 0); /* <= 16 bits */ + if (MEM_32bits() && (mlBits+llBits>24)) BIT_reloadDStream(&seqState->DStream); + + seq.litLength = LL_base[llCode] + ((llCode>15) ? BIT_readBitsFast(&seqState->DStream, llBits) : 0); /* <= 16 bits */ + if (MEM_32bits() || + (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BIT_reloadDStream(&seqState->DStream); + + /* ANS state update */ + FSE_updateState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */ + FSE_updateState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */ + if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */ + FSE_updateState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */ + + return seq; +} + + FORCE_INLINE size_t ZSTD_execSequence(BYTE* op, BYTE* const oend, seq_t sequence, - const BYTE** litPtr, const BYTE* const litLimit_w, + const BYTE** litPtr, const BYTE* const litLimit, const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd) { BYTE* const oLitEnd = op + sequence.litLength; @@ -909,8 +938,8 @@ /* check */ if (oMatchEnd>oend) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */ - if (iLitEnd > litLimit_w) return ERROR(corruption_detected); /* over-read beyond lit buffer */ - if (oLitEnd>oend_w) return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit_w, base, vBase, dictEnd); + if (iLitEnd > litLimit) return ERROR(corruption_detected); /* over-read beyond lit buffer */ + if (oLitEnd>oend_w) return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, base, vBase, dictEnd); /* copy Literals */ ZSTD_copy8(op, *litPtr); @@ -923,7 +952,7 @@ if (sequence.offset > (size_t)(oLitEnd - base)) { /* offset beyond prefix */ if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected); - match = dictEnd - (base-match); + match += (dictEnd-base); if (match + sequence.matchLength <= dictEnd) { memmove(oLitEnd, match, sequence.matchLength); return sequenceLength; @@ -934,13 +963,13 @@ op = oLitEnd + length1; sequence.matchLength -= length1; match = base; - if (op > oend_w) { + if (op > oend_w || sequence.matchLength < MINMATCH) { U32 i; for (i = 0; i < sequence.matchLength; ++i) op[i] = match[i]; return sequenceLength; } } } - /* Requirement: op <= oend_w */ + /* Requirement: op <= oend_w && sequence.matchLength >= MINMATCH */ /* match within prefix */ if (sequence.offset < 8) { @@ -968,7 +997,7 @@ } while (op < oMatchEnd) *op++ = *match++; } else { - ZSTD_wildcopy(op, match, sequence.matchLength-8); /* works even if matchLength < 8 */ + ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */ } return sequenceLength; } @@ -985,7 +1014,6 @@ BYTE* const oend = ostart + maxDstSize; BYTE* op = ostart; const BYTE* litPtr = dctx->litPtr; - const BYTE* const litLimit_w = litPtr + dctx->litBufSize - WILDCOPY_OVERLENGTH; const BYTE* const litEnd = litPtr + dctx->litSize; const BYTE* const base = (const BYTE*) (dctx->base); const BYTE* const vBase = (const BYTE*) (dctx->vBase); @@ -1011,7 +1039,7 @@ for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq ; ) { nbSeq--; { seq_t const sequence = ZSTD_decodeSequence(&seqState); - size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litLimit_w, base, vBase, dictEnd); + size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd); if (ZSTD_isError(oneSeqSize)) return oneSeqSize; op += oneSeqSize; } } @@ -1033,14 +1061,247 @@ } -static void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst) +static seq_t ZSTD_decodeSequenceLong(seqState_t* seqState) +{ + seq_t seq; + + U32 const llCode = FSE_peekSymbol(&seqState->stateLL); + U32 const mlCode = FSE_peekSymbol(&seqState->stateML); + U32 const ofCode = FSE_peekSymbol(&seqState->stateOffb); /* <= maxOff, by table construction */ + + U32 const llBits = LL_bits[llCode]; + U32 const mlBits = ML_bits[mlCode]; + U32 const ofBits = ofCode; + U32 const totalBits = llBits+mlBits+ofBits; + + static const U32 LL_base[MaxLL+1] = { + 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, + 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, + 0x2000, 0x4000, 0x8000, 0x10000 }; + + static const U32 ML_base[MaxML+1] = { + 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, + 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, + 35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803, + 0x1003, 0x2003, 0x4003, 0x8003, 0x10003 }; + + static const U32 OF_base[MaxOff+1] = { + 0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D, + 0xFD, 0x1FD, 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD, + 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD, + 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD }; + + /* sequence */ + { size_t offset; + if (!ofCode) + offset = 0; + else { + offset = OF_base[ofCode] + BIT_readBitsFast(&seqState->DStream, ofBits); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */ + if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); + } + + if (ofCode <= 1) { + offset += (llCode==0); + if (offset) { + size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset]; + temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */ + if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1]; + seqState->prevOffset[1] = seqState->prevOffset[0]; + seqState->prevOffset[0] = offset = temp; + } else { + offset = seqState->prevOffset[0]; + } + } else { + seqState->prevOffset[2] = seqState->prevOffset[1]; + seqState->prevOffset[1] = seqState->prevOffset[0]; + seqState->prevOffset[0] = offset; + } + seq.offset = offset; + } + + seq.matchLength = ML_base[mlCode] + ((mlCode>31) ? BIT_readBitsFast(&seqState->DStream, mlBits) : 0); /* <= 16 bits */ + if (MEM_32bits() && (mlBits+llBits>24)) BIT_reloadDStream(&seqState->DStream); + + seq.litLength = LL_base[llCode] + ((llCode>15) ? BIT_readBitsFast(&seqState->DStream, llBits) : 0); /* <= 16 bits */ + if (MEM_32bits() || + (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BIT_reloadDStream(&seqState->DStream); + + { size_t const pos = seqState->pos + seq.litLength; + seq.match = seqState->base + pos - seq.offset; /* single memory segment */ + if (seq.offset > pos) seq.match += seqState->gotoDict; /* separate memory segment */ + seqState->pos = pos + seq.matchLength; + } + + /* ANS state update */ + FSE_updateState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */ + FSE_updateState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */ + if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */ + FSE_updateState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */ + + return seq; +} + +FORCE_INLINE +size_t ZSTD_execSequenceLong(BYTE* op, + BYTE* const oend, seq_t sequence, + const BYTE** litPtr, const BYTE* const litLimit, + const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd) { - if (dst != dctx->previousDstEnd) { /* not contiguous */ - dctx->dictEnd = dctx->previousDstEnd; - dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base)); - dctx->base = dst; - dctx->previousDstEnd = dst; + BYTE* const oLitEnd = op + sequence.litLength; + size_t const sequenceLength = sequence.litLength + sequence.matchLength; + BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */ + BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH; + const BYTE* const iLitEnd = *litPtr + sequence.litLength; + const BYTE* match = sequence.match; + + /* check */ +#if 1 + if (oMatchEnd>oend) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */ + if (iLitEnd > litLimit) return ERROR(corruption_detected); /* over-read beyond lit buffer */ + if (oLitEnd>oend_w) return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, base, vBase, dictEnd); +#endif + + /* copy Literals */ + ZSTD_copy8(op, *litPtr); + if (sequence.litLength > 8) + ZSTD_wildcopy(op+8, (*litPtr)+8, sequence.litLength - 8); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */ + op = oLitEnd; + *litPtr = iLitEnd; /* update for next sequence */ + + /* copy Match */ +#if 1 + if (sequence.offset > (size_t)(oLitEnd - base)) { + /* offset beyond prefix */ + if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected); + if (match + sequence.matchLength <= dictEnd) { + memmove(oLitEnd, match, sequence.matchLength); + return sequenceLength; + } + /* span extDict & currentPrefixSegment */ + { size_t const length1 = dictEnd - match; + memmove(oLitEnd, match, length1); + op = oLitEnd + length1; + sequence.matchLength -= length1; + match = base; + if (op > oend_w || sequence.matchLength < MINMATCH) { + U32 i; + for (i = 0; i < sequence.matchLength; ++i) op[i] = match[i]; + return sequenceLength; + } + } } + /* Requirement: op <= oend_w && sequence.matchLength >= MINMATCH */ +#endif + + /* match within prefix */ + if (sequence.offset < 8) { + /* close range match, overlap */ + static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */ + static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* substracted */ + int const sub2 = dec64table[sequence.offset]; + op[0] = match[0]; + op[1] = match[1]; + op[2] = match[2]; + op[3] = match[3]; + match += dec32table[sequence.offset]; + ZSTD_copy4(op+4, match); + match -= sub2; + } else { + ZSTD_copy8(op, match); + } + op += 8; match += 8; + + if (oMatchEnd > oend-(16-MINMATCH)) { + if (op < oend_w) { + ZSTD_wildcopy(op, match, oend_w - op); + match += oend_w - op; + op = oend_w; + } + while (op < oMatchEnd) *op++ = *match++; + } else { + ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */ } + return sequenceLength; +} + +static size_t ZSTD_decompressSequencesLong( + ZSTD_DCtx* dctx, + void* dst, size_t maxDstSize, + const void* seqStart, size_t seqSize) +{ + const BYTE* ip = (const BYTE*)seqStart; + const BYTE* const iend = ip + seqSize; + BYTE* const ostart = (BYTE* const)dst; + BYTE* const oend = ostart + maxDstSize; + BYTE* op = ostart; + const BYTE* litPtr = dctx->litPtr; + const BYTE* const litEnd = litPtr + dctx->litSize; + const BYTE* const base = (const BYTE*) (dctx->base); + const BYTE* const vBase = (const BYTE*) (dctx->vBase); + const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd); + int nbSeq; + + /* Build Decoding Tables */ + { size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, seqSize); + if (ZSTD_isError(seqHSize)) return seqHSize; + ip += seqHSize; + } + + /* Regen sequences */ + if (nbSeq) { +#define STORED_SEQS 4 +#define STOSEQ_MASK (STORED_SEQS-1) +#define ADVANCED_SEQS 4 + seq_t sequences[STORED_SEQS]; + int const seqAdvance = MIN(nbSeq, ADVANCED_SEQS); + seqState_t seqState; + int seqNb; + dctx->fseEntropy = 1; + { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->rep[i]; } + seqState.base = base; + seqState.pos = (size_t)(op-base); + seqState.gotoDict = (iPtrDiff)(dictEnd - base); + CHECK_E(BIT_initDStream(&seqState.DStream, ip, iend-ip), corruption_detected); + FSE_initDState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr); + FSE_initDState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr); + FSE_initDState(&seqState.stateML, &seqState.DStream, dctx->MLTptr); + + /* prepare in advance */ + for (seqNb=0; (BIT_reloadDStream(&seqState.DStream) <= BIT_DStream_completed) && seqNb<seqAdvance; seqNb++) { + sequences[seqNb] = ZSTD_decodeSequenceLong(&seqState); + } + if (seqNb<seqAdvance) return ERROR(corruption_detected); + + /* decode and decompress */ + for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && seqNb<nbSeq ; seqNb++) { + seq_t const sequence = ZSTD_decodeSequenceLong(&seqState); + size_t const oneSeqSize = ZSTD_execSequenceLong(op, oend, sequences[(seqNb-ADVANCED_SEQS) & STOSEQ_MASK], &litPtr, litEnd, base, vBase, dictEnd); + if (ZSTD_isError(oneSeqSize)) return oneSeqSize; + ZSTD_PREFETCH(sequence.match); + sequences[seqNb&STOSEQ_MASK] = sequence; + op += oneSeqSize; + } + if (seqNb<nbSeq) return ERROR(corruption_detected); + + /* finish queue */ + seqNb -= seqAdvance; + for ( ; seqNb<nbSeq ; seqNb++) { + size_t const oneSeqSize = ZSTD_execSequenceLong(op, oend, sequences[seqNb&STOSEQ_MASK], &litPtr, litEnd, base, vBase, dictEnd); + if (ZSTD_isError(oneSeqSize)) return oneSeqSize; + op += oneSeqSize; + } + + /* save reps for next block */ + { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->rep[i] = (U32)(seqState.prevOffset[i]); } + } + + /* last literal segment */ + { size_t const lastLLSize = litEnd - litPtr; + if (lastLLSize > (size_t)(oend-op)) return ERROR(dstSize_tooSmall); + memcpy(op, litPtr, lastLLSize); + op += lastLLSize; + } + + return op-ostart; } @@ -1058,10 +1319,21 @@ ip += litCSize; srcSize -= litCSize; } + if (dctx->fParams.windowSize > (1<<23)) return ZSTD_decompressSequencesLong(dctx, dst, dstCapacity, ip, srcSize); return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize); } +static void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst) +{ + if (dst != dctx->previousDstEnd) { /* not contiguous */ + dctx->dictEnd = dctx->previousDstEnd; + dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base)); + dctx->base = dst; + dctx->previousDstEnd = dst; + } +} + size_t ZSTD_decompressBlock(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize) @@ -1506,6 +1778,45 @@ return sizeof(*ddict) + sizeof(ddict->refContext) + ddict->dictSize; } +/*! ZSTD_getDictID_fromDict() : + * Provides the dictID stored within dictionary. + * if @return == 0, the dictionary is not conformant with Zstandard specification. + * It can still be loaded, but as a content-only dictionary. */ +unsigned ZSTD_getDictID_fromDict(const void* dict, size_t dictSize) +{ + if (dictSize < 8) return 0; + if (MEM_readLE32(dict) != ZSTD_DICT_MAGIC) return 0; + return MEM_readLE32((const char*)dict + 4); +} + +/*! ZSTD_getDictID_fromDDict() : + * Provides the dictID of the dictionary loaded into `ddict`. + * If @return == 0, the dictionary is not conformant to Zstandard specification, or empty. + * Non-conformant dictionaries can still be loaded, but as content-only dictionaries. */ +unsigned ZSTD_getDictID_fromDDict(const ZSTD_DDict* ddict) +{ + if (ddict==NULL) return 0; + return ZSTD_getDictID_fromDict(ddict->dict, ddict->dictSize); +} + +/*! ZSTD_getDictID_fromFrame() : + * Provides the dictID required to decompressed the frame stored within `src`. + * If @return == 0, the dictID could not be decoded. + * This could for one of the following reasons : + * - The frame does not require a dictionary to be decoded (most common case). + * - The frame was built with dictID intentionally removed. Whatever dictionary is necessary is a hidden information. + * Note : this use case also happens when using a non-conformant dictionary. + * - `srcSize` is too small, and as a result, the frame header could not be decoded (only possible if `srcSize < ZSTD_FRAMEHEADERSIZE_MAX`). + * - This is not a Zstandard frame. + * When identifying the exact failure cause, it's possible to used ZSTD_getFrameParams(), which will provide a more precise error code. */ +unsigned ZSTD_getDictID_fromFrame(const void* src, size_t srcSize) +{ + ZSTD_frameParams zfp = { 0 , 0 , 0 , 0 }; + size_t const hError = ZSTD_getFrameParams(&zfp, src, srcSize); + if (ZSTD_isError(hError)) return 0; + return zfp.dictID; +} + /*! ZSTD_decompress_usingDDict() : * Decompression using a pre-digested Dictionary @@ -1687,7 +1998,8 @@ switch(zds->stage) { case zdss_init : - return ERROR(init_missing); + ZSTD_resetDStream(zds); /* transparent reset on starting decoding a new frame */ + /* fall-through */ case zdss_loadHeader : { size_t const hSize = ZSTD_getFrameParams(&zds->fParams, zds->headerBuffer, zds->lhSize);
--- a/contrib/python-zstandard/zstd/dictBuilder/zdict.c Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd/dictBuilder/zdict.c Sat Jan 14 19:41:43 2017 -0800 @@ -898,12 +898,14 @@ U32 const nb = MIN(25, dictList[0].pos); U32 const dictContentSize = ZDICT_dictSize(dictList); U32 u; - DISPLAYLEVEL(3, "\n %u segments found, of total size %u \n", dictList[0].pos, dictContentSize); - DISPLAYLEVEL(3, "list %u best segments \n", nb); - for (u=1; u<=nb; u++) { - U32 pos = dictList[u].pos; - U32 length = dictList[u].length; - U32 printedLength = MIN(40, length); + DISPLAYLEVEL(3, "\n %u segments found, of total size %u \n", dictList[0].pos-1, dictContentSize); + DISPLAYLEVEL(3, "list %u best segments \n", nb-1); + for (u=1; u<nb; u++) { + U32 const pos = dictList[u].pos; + U32 const length = dictList[u].length; + U32 const printedLength = MIN(40, length); + if ((pos > samplesBuffSize) || ((pos + length) > samplesBuffSize)) + return ERROR(GENERIC); /* should never happen */ DISPLAYLEVEL(3, "%3u:%3u bytes at pos %8u, savings %7u bytes |", u, length, pos, dictList[u].savings); ZDICT_printHex((const char*)samplesBuffer+pos, printedLength);
--- a/contrib/python-zstandard/zstd/zstd.h Sat Jan 14 20:05:15 2017 +0530 +++ b/contrib/python-zstandard/zstd/zstd.h Sat Jan 14 19:41:43 2017 -0800 @@ -7,24 +7,24 @@ * of patent rights can be found in the PATENTS file in the same directory. */ -#ifndef ZSTD_H_235446 -#define ZSTD_H_235446 - #if defined (__cplusplus) extern "C" { #endif +#ifndef ZSTD_H_235446 +#define ZSTD_H_235446 + /* ====== Dependency ======*/ #include <stddef.h> /* size_t */ -/* ====== Export for Windows ======*/ -/* -* ZSTD_DLL_EXPORT : -* Enable exporting of functions when building a Windows DLL -*/ -#if defined(_WIN32) && defined(ZSTD_DLL_EXPORT) && (ZSTD_DLL_EXPORT==1) +/* ===== ZSTDLIB_API : control library symbols visibility ===== */ +#if defined(__GNUC__) && (__GNUC__ >= 4) +# define ZSTDLIB_API __attribute__ ((visibility ("default"))) +#elif defined(ZSTD_DLL_EXPORT) && (ZSTD_DLL_EXPORT==1) # define ZSTDLIB_API __declspec(dllexport) +#elif defined(ZSTD_DLL_IMPORT) && (ZSTD_DLL_IMPORT==1) +# define ZSTDLIB_API __declspec(dllimport) /* It isn't required but allows to generate better code, saving a function pointer load from the IAT and an indirect jump.*/ #else # define ZSTDLIB_API #endif @@ -51,11 +51,9 @@ *********************************************************************************************************/ /*------ Version ------*/ -ZSTDLIB_API unsigned ZSTD_versionNumber (void); /**< returns version number of ZSTD */ - #define ZSTD_VERSION_MAJOR 1 #define ZSTD_VERSION_MINOR 1 -#define ZSTD_VERSION_RELEASE 1 +#define ZSTD_VERSION_RELEASE 2 #define ZSTD_LIB_VERSION ZSTD_VERSION_MAJOR.ZSTD_VERSION_MINOR.ZSTD_VERSION_RELEASE #define ZSTD_QUOTE(str) #str @@ -63,6 +61,7 @@ #define ZSTD_VERSION_STRING ZSTD_EXPAND_AND_QUOTE(ZSTD_LIB_VERSION) #define ZSTD_VERSION_NUMBER (ZSTD_VERSION_MAJOR *100*100 + ZSTD_VERSION_MINOR *100 + ZSTD_VERSION_RELEASE) +ZSTDLIB_API unsigned ZSTD_versionNumber(void); /**< library version number; to be used when checking dll version */ /*************************************** @@ -72,7 +71,7 @@ Compresses `src` content as a single zstd compressed frame into already allocated `dst`. Hint : compression runs faster if `dstCapacity` >= `ZSTD_compressBound(srcSize)`. @return : compressed size written into `dst` (<= `dstCapacity), - or an error code if it fails (which can be tested using ZSTD_isError()) */ + or an error code if it fails (which can be tested using ZSTD_isError()). */ ZSTDLIB_API size_t ZSTD_compress( void* dst, size_t dstCapacity, const void* src, size_t srcSize, int compressionLevel); @@ -82,7 +81,7 @@ `dstCapacity` is an upper bound of originalSize. If user cannot imply a maximum upper bound, it's better to use streaming mode to decompress data. @return : the number of bytes decompressed into `dst` (<= `dstCapacity`), - or an errorCode if it fails (which can be tested using ZSTD_isError()) */ + or an errorCode if it fails (which can be tested using ZSTD_isError()). */ ZSTDLIB_API size_t ZSTD_decompress( void* dst, size_t dstCapacity, const void* src, size_t compressedSize); @@ -116,16 +115,16 @@ * Explicit memory management ***************************************/ /*= Compression context -* When compressing many messages / blocks, +* When compressing many times, * it is recommended to allocate a context just once, and re-use it for each successive compression operation. -* This will make the situation much easier for the system's memory. +* This will make workload friendlier for system's memory. * Use one context per thread for parallel execution in multi-threaded environments. */ typedef struct ZSTD_CCtx_s ZSTD_CCtx; ZSTDLIB_API ZSTD_CCtx* ZSTD_createCCtx(void); ZSTDLIB_API size_t ZSTD_freeCCtx(ZSTD_CCtx* cctx); /*! ZSTD_compressCCtx() : - Same as ZSTD_compress(), requires an allocated ZSTD_CCtx (see ZSTD_createCCtx()) */ + Same as ZSTD_compress(), requires an allocated ZSTD_CCtx (see ZSTD_createCCtx()). */ ZSTDLIB_API size_t ZSTD_compressCCtx(ZSTD_CCtx* ctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, int compressionLevel); /*= Decompression context */ @@ -134,7 +133,7 @@ ZSTDLIB_API size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx); /*! ZSTD_decompressDCtx() : -* Same as ZSTD_decompress(), requires an allocated ZSTD_DCtx (see ZSTD_createDCtx()) */ +* Same as ZSTD_decompress(), requires an allocated ZSTD_DCtx (see ZSTD_createDCtx()). */ ZSTDLIB_API size_t ZSTD_decompressDCtx(ZSTD_DCtx* ctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize); @@ -143,7 +142,8 @@ ***************************/ /*! ZSTD_compress_usingDict() : * Compression using a predefined Dictionary (see dictBuilder/zdict.h). -* Note : This function load the dictionary, resulting in significant startup delay. */ +* Note : This function loads the dictionary, resulting in significant startup delay. +* Note : When `dict == NULL || dictSize < 8` no dictionary is used. */ ZSTDLIB_API size_t ZSTD_compress_usingDict(ZSTD_CCtx* ctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, @@ -153,7 +153,8 @@ /*! ZSTD_decompress_usingDict() : * Decompression using a predefined Dictionary (see dictBuilder/zdict.h). * Dictionary must be identical to the one used during compression. -* Note : This function load the dictionary, resulting in significant startup delay */ +* Note : This function loads the dictionary, resulting in significant startup delay. +* Note : When `dict == NULL || dictSize < 8` no dictionary is used. */ ZSTDLIB_API size_t ZSTD_decompress_usingDict(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, @@ -169,17 +170,17 @@ * When compressing multiple messages / blocks with the same dictionary, it's recommended to load it just once. * ZSTD_createCDict() will create a digested dictionary, ready to start future compression operations without startup delay. * ZSTD_CDict can be created once and used by multiple threads concurrently, as its usage is read-only. -* `dict` can be released after ZSTD_CDict creation */ +* `dict` can be released after ZSTD_CDict creation. */ ZSTDLIB_API ZSTD_CDict* ZSTD_createCDict(const void* dict, size_t dictSize, int compressionLevel); /*! ZSTD_freeCDict() : -* Function frees memory allocated by ZSTD_createCDict() */ +* Function frees memory allocated by ZSTD_createCDict(). */ ZSTDLIB_API size_t ZSTD_freeCDict(ZSTD_CDict* CDict); /*! ZSTD_compress_usingCDict() : * Compression using a digested Dictionary. * Faster startup than ZSTD_compress_usingDict(), recommended when same dictionary is used multiple times. -* Note that compression level is decided during dictionary creation */ +* Note that compression level is decided during dictionary creation. */ ZSTDLIB_API size_t ZSTD_compress_usingCDict(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, @@ -190,7 +191,7 @@ /*! ZSTD_createDDict() : * Create a digested dictionary, ready to start decompression operation without startup delay. -* `dict` can be released after creation */ +* `dict` can be released after creation. */ ZSTDLIB_API ZSTD_DDict* ZSTD_createDDict(const void* dict, size_t dictSize); /*! ZSTD_freeDDict() : @@ -198,7 +199,7 @@ ZSTDLIB_API size_t ZSTD_freeDDict(ZSTD_DDict* ddict); /*! ZSTD_decompress_usingDDict() : -* Decompression using a digested Dictionary +* Decompression using a digested Dictionary. * Faster startup than ZSTD_decompress_usingDict(), recommended when same dictionary is used multiple times. */ ZSTDLIB_API size_t ZSTD_decompress_usingDDict(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, @@ -236,20 +237,20 @@ * * Start a new compression by initializing ZSTD_CStream. * Use ZSTD_initCStream() to start a new compression operation. -* Use ZSTD_initCStream_usingDict() for a compression which requires a dictionary. +* Use ZSTD_initCStream_usingDict() or ZSTD_initCStream_usingCDict() for a compression which requires a dictionary (experimental section) * * Use ZSTD_compressStream() repetitively to consume input stream. * The function will automatically update both `pos` fields. * Note that it may not consume the entire input, in which case `pos < size`, * and it's up to the caller to present again remaining data. * @return : a size hint, preferred nb of bytes to use as input for next function call -* (it's just a hint, to help latency a little, any other value will work fine) -* (note : the size hint is guaranteed to be <= ZSTD_CStreamInSize() ) * or an error code, which can be tested using ZSTD_isError(). +* Note 1 : it's just a hint, to help latency a little, any other value will work fine. +* Note 2 : size hint is guaranteed to be <= ZSTD_CStreamInSize() * -* At any moment, it's possible to flush whatever data remains within buffer, using ZSTD_flushStream(). +* At any moment, it's possible to flush whatever data remains within internal buffer, using ZSTD_flushStream(). * `output->pos` will be updated. -* Note some content might still be left within internal buffer if `output->size` is too small. +* Note that some content might still be left within internal buffer if `output->size` is too small. * @return : nb of bytes still present within internal buffer (0 if it's empty) * or an error code, which can be tested using ZSTD_isError(). * @@ -258,15 +259,15 @@ * The epilogue is required for decoders to consider a frame completed. * Similar to ZSTD_flushStream(), it may not be able to flush the full content if `output->size` is too small. * In which case, call again ZSTD_endStream() to complete the flush. -* @return : nb of bytes still present within internal buffer (0 if it's empty) +* @return : nb of bytes still present within internal buffer (0 if it's empty, hence compression completed) * or an error code, which can be tested using ZSTD_isError(). * * *******************************************************************/ -/*===== Streaming compression functions ======*/ typedef struct ZSTD_CStream_s ZSTD_CStream; ZSTDLIB_API ZSTD_CStream* ZSTD_createCStream(void); ZSTDLIB_API size_t ZSTD_freeCStream(ZSTD_CStream* zcs); + ZSTDLIB_API size_t ZSTD_initCStream(ZSTD_CStream* zcs, int compressionLevel); ZSTDLIB_API size_t ZSTD_compressStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output, ZSTD_inBuffer* input); ZSTDLIB_API size_t ZSTD_flushStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output); @@ -295,23 +296,25 @@ * If `output.pos < output.size`, decoder has flushed everything it could. * @return : 0 when a frame is completely decoded and fully flushed, * an error code, which can be tested using ZSTD_isError(), -* any other value > 0, which means there is still some work to do to complete the frame. -* The return value is a suggested next input size (just an hint, to help latency). +* any other value > 0, which means there is still some decoding to do to complete current frame. +* The return value is a suggested next input size (a hint to improve latency) that will never load more than the current frame. * *******************************************************************************/ -/*===== Streaming decompression functions =====*/ typedef struct ZSTD_DStream_s ZSTD_DStream; ZSTDLIB_API ZSTD_DStream* ZSTD_createDStream(void); ZSTDLIB_API size_t ZSTD_freeDStream(ZSTD_DStream* zds); + ZSTDLIB_API size_t ZSTD_initDStream(ZSTD_DStream* zds); ZSTDLIB_API size_t ZSTD_decompressStream(ZSTD_DStream* zds, ZSTD_outBuffer* output, ZSTD_inBuffer* input); ZSTDLIB_API size_t ZSTD_DStreamInSize(void); /*!< recommended size for input buffer */ ZSTDLIB_API size_t ZSTD_DStreamOutSize(void); /*!< recommended size for output buffer. Guarantee to successfully flush at least one complete block in all circumstances. */ +#endif /* ZSTD_H_235446 */ -#ifdef ZSTD_STATIC_LINKING_ONLY +#if defined(ZSTD_STATIC_LINKING_ONLY) && !defined(ZSTD_H_ZSTD_STATIC_LINKING_ONLY) +#define ZSTD_H_ZSTD_STATIC_LINKING_ONLY /**************************************************************************************** * START OF ADVANCED AND EXPERIMENTAL FUNCTIONS @@ -403,15 +406,15 @@ * Gives the amount of memory used by a given ZSTD_sizeof_CDict */ ZSTDLIB_API size_t ZSTD_sizeof_CDict(const ZSTD_CDict* cdict); -/*! ZSTD_getParams() : -* same as ZSTD_getCParams(), but @return a full `ZSTD_parameters` object instead of a `ZSTD_compressionParameters`. -* All fields of `ZSTD_frameParameters` are set to default (0) */ -ZSTDLIB_API ZSTD_parameters ZSTD_getParams(int compressionLevel, unsigned long long srcSize, size_t dictSize); +/*! ZSTD_getCParams() : +* @return ZSTD_compressionParameters structure for a selected compression level and estimated srcSize. +* `estimatedSrcSize` value is optional, select 0 if not known */ +ZSTDLIB_API ZSTD_compressionParameters ZSTD_getCParams(int compressionLevel, unsigned long long estimatedSrcSize, size_t dictSize); -/*! ZSTD_getCParams() : -* @return ZSTD_compressionParameters structure for a selected compression level and srcSize. -* `srcSize` value is optional, select 0 if not known */ -ZSTDLIB_API ZSTD_compressionParameters ZSTD_getCParams(int compressionLevel, unsigned long long srcSize, size_t dictSize); +/*! ZSTD_getParams() : +* same as ZSTD_getCParams(), but @return a full `ZSTD_parameters` object instead of sub-component `ZSTD_compressionParameters`. +* All fields of `ZSTD_frameParameters` are set to default (0) */ +ZSTDLIB_API ZSTD_parameters ZSTD_getParams(int compressionLevel, unsigned long long estimatedSrcSize, size_t dictSize); /*! ZSTD_checkCParams() : * Ensure param values remain within authorized range */ @@ -433,6 +436,13 @@ /*--- Advanced decompression functions ---*/ +/*! ZSTD_isFrame() : + * Tells if the content of `buffer` starts with a valid Frame Identifier. + * Note : Frame Identifier is 4 bytes. If `size < 4`, @return will always be 0. + * Note 2 : Legacy Frame Identifiers are considered valid only if Legacy Support is enabled. + * Note 3 : Skippable Frame Identifiers are considered valid. */ +ZSTDLIB_API unsigned ZSTD_isFrame(const void* buffer, size_t size); + /*! ZSTD_estimateDCtxSize() : * Gives the potential amount of memory allocated to create a ZSTD_DCtx */ ZSTDLIB_API size_t ZSTD_estimateDCtxSize(void); @@ -449,6 +459,30 @@ * Gives the amount of memory used by a given ZSTD_DDict */ ZSTDLIB_API size_t ZSTD_sizeof_DDict(const ZSTD_DDict* ddict); +/*! ZSTD_getDictID_fromDict() : + * Provides the dictID stored within dictionary. + * if @return == 0, the dictionary is not conformant with Zstandard specification. + * It can still be loaded, but as a content-only dictionary. */ +unsigned ZSTD_getDictID_fromDict(const void* dict, size_t dictSize); + +/*! ZSTD_getDictID_fromDDict() : + * Provides the dictID of the dictionary loaded into `ddict`. + * If @return == 0, the dictionary is not conformant to Zstandard specification, or empty. + * Non-conformant dictionaries can still be loaded, but as content-only dictionaries. */ +unsigned ZSTD_getDictID_fromDDict(const ZSTD_DDict* ddict); + +/*! ZSTD_getDictID_fromFrame() : + * Provides the dictID required to decompressed the frame stored within `src`. + * If @return == 0, the dictID could not be decoded. + * This could for one of the following reasons : + * - The frame does not require a dictionary to be decoded (most common case). + * - The frame was built with dictID intentionally removed. Whatever dictionary is necessary is a hidden information. + * Note : this use case also happens when using a non-conformant dictionary. + * - `srcSize` is too small, and as a result, the frame header could not be decoded (only possible if `srcSize < ZSTD_FRAMEHEADERSIZE_MAX`). + * - This is not a Zstandard frame. + * When identifying the exact failure cause, it's possible to used ZSTD_getFrameParams(), which will provide a more precise error code. */ +unsigned ZSTD_getDictID_fromFrame(const void* src, size_t srcSize); + /******************************************************************** * Advanced streaming functions @@ -456,6 +490,7 @@ /*===== Advanced Streaming compression functions =====*/ ZSTDLIB_API ZSTD_CStream* ZSTD_createCStream_advanced(ZSTD_customMem customMem); +ZSTDLIB_API size_t ZSTD_initCStream_srcSize(ZSTD_CStream* zcs, int compressionLevel, unsigned long long pledgedSrcSize); /**< pledgedSrcSize must be correct */ ZSTDLIB_API size_t ZSTD_initCStream_usingDict(ZSTD_CStream* zcs, const void* dict, size_t dictSize, int compressionLevel); ZSTDLIB_API size_t ZSTD_initCStream_advanced(ZSTD_CStream* zcs, const void* dict, size_t dictSize, ZSTD_parameters params, unsigned long long pledgedSrcSize); /**< pledgedSrcSize is optional and can be zero == unknown */ @@ -631,10 +666,8 @@ ZSTDLIB_API size_t ZSTD_insertBlock(ZSTD_DCtx* dctx, const void* blockStart, size_t blockSize); /**< insert block into `dctx` history. Useful for uncompressed blocks */ -#endif /* ZSTD_STATIC_LINKING_ONLY */ +#endif /* ZSTD_H_ZSTD_STATIC_LINKING_ONLY */ #if defined (__cplusplus) } #endif - -#endif /* ZSTD_H_235446 */