Add an unpatched version of xz, XZ Utils, to /trunk/deps/third_party

xz/src/liblzma/lz/lz_decoder.h

+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lz_decoder.h
+/// \brief      LZ out window
+///
+//  Authors:    Igor Pavlov
+//              Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZ_DECODER_H
+#define LZMA_LZ_DECODER_H
+
+#include "common.h"
+
+
+typedef struct {
+        /// Pointer to the dictionary buffer. It can be an allocated buffer
+        /// internal to liblzma, or it can a be a buffer given by the
+        /// application when in single-call mode (not implemented yet).
+        uint8_t *buf;
+
+        /// Write position in dictionary. The next byte will be written to
+        /// buf[pos].
+        size_t pos;
+
+        /// Indicates how full the dictionary is. This is used by
+        /// dict_is_distance_valid() to detect corrupt files that would
+        /// read beyond the beginning of the dictionary.
+        size_t full;
+
+        /// Write limit
+        size_t limit;
+
+        /// Size of the dictionary
+        size_t size;
+
+        /// True when dictionary should be reset before decoding more data.
+        bool need_reset;
+
+} lzma_dict;
+
+
+typedef struct {
+        size_t dict_size;
+        const uint8_t *preset_dict;
+        size_t preset_dict_size;
+} lzma_lz_options;
+
+
+typedef struct {
+        /// Data specific to the LZ-based decoder
+        lzma_coder *coder;
+
+        /// Function to decode from in[] to *dict
+        lzma_ret (*code)(lzma_coder *restrict coder,
+                        lzma_dict *restrict dict, const uint8_t *restrict in,
+                        size_t *restrict in_pos, size_t in_size);
+
+        void (*reset)(lzma_coder *coder, const void *options);
+
+        /// Set the uncompressed size
+        void (*set_uncompressed)(lzma_coder *coder,
+                        lzma_vli uncompressed_size);
+
+        /// Free allocated resources
+        void (*end)(lzma_coder *coder, lzma_allocator *allocator);
+
+} lzma_lz_decoder;
+
+
+#define LZMA_LZ_DECODER_INIT \
+        (lzma_lz_decoder){ \
+                .coder = NULL, \
+                .code = NULL, \
+                .reset = NULL, \
+                .set_uncompressed = NULL, \
+                .end = NULL, \
+        }
+
+
+extern lzma_ret lzma_lz_decoder_init(lzma_next_coder *next,
+                lzma_allocator *allocator, const lzma_filter_info *filters,
+                lzma_ret (*lz_init)(lzma_lz_decoder *lz,
+                        lzma_allocator *allocator, const void *options,
+                        lzma_lz_options *lz_options));
+
+extern uint64_t lzma_lz_decoder_memusage(size_t dictionary_size);
+
+extern void lzma_lz_decoder_uncompressed(
+                lzma_coder *coder, lzma_vli uncompressed_size);
+
+
+//////////////////////
+// Inline functions //
+//////////////////////
+
+/// Get a byte from the history buffer.
+static inline uint8_t
+dict_get(const lzma_dict *const dict, const uint32_t distance)
+{
+        return dict->buf[dict->pos - distance - 1
+                        + (distance < dict->pos ? 0 : dict->size)];
+}
+
+
+/// Test if dictionary is empty.
+static inline bool
+dict_is_empty(const lzma_dict *const dict)
+{
+        return dict->full == 0;
+}
+
+
+/// Validate the match distance
+static inline bool
+dict_is_distance_valid(const lzma_dict *const dict, const size_t distance)
+{
+        return dict->full > distance;
+}
+
+
+/// Repeat *len bytes at distance.
+static inline bool
+dict_repeat(lzma_dict *dict, uint32_t distance, uint32_t *len)
+{
+        // Don't write past the end of the dictionary.
+        const size_t dict_avail = dict->limit - dict->pos;
+        uint32_t left = my_min(dict_avail, *len);
+        *len -= left;
+
+        // Repeat a block of data from the history. Because memcpy() is faster
+        // than copying byte by byte in a loop, the copying process gets split
+        // into three cases.
+        if (distance < left) {
+                // Source and target areas overlap, thus we can't use
+                // memcpy() nor even memmove() safely.
+                do {
+                        dict->buf[dict->pos] = dict_get(dict, distance);
+                        ++dict->pos;
+                } while (--left > 0);
+
+        } else if (distance < dict->pos) {
+                // The easiest and fastest case
+                memcpy(dict->buf + dict->pos,
+                                dict->buf + dict->pos - distance - 1,
+                                left);
+                dict->pos += left;
+
+        } else {
+                // The bigger the dictionary, the more rare this
+                // case occurs. We need to "wrap" the dict, thus
+                // we might need two memcpy() to copy all the data.
+                assert(dict->full == dict->size);
+                const uint32_t copy_pos
+                                = dict->pos - distance - 1 + dict->size;
+                uint32_t copy_size = dict->size - copy_pos;
+
+                if (copy_size < left) {
+                        memmove(dict->buf + dict->pos, dict->buf + copy_pos,
+                                        copy_size);
+                        dict->pos += copy_size;
+                        copy_size = left - copy_size;
+                        memcpy(dict->buf + dict->pos, dict->buf, copy_size);
+                        dict->pos += copy_size;
+                } else {
+                        memmove(dict->buf + dict->pos, dict->buf + copy_pos,
+                                        left);
+                        dict->pos += left;
+                }
+        }
+
+        // Update how full the dictionary is.
+        if (dict->full < dict->pos)
+                dict->full = dict->pos;
+
+        return unlikely(*len != 0);
+}
+
+
+/// Puts one byte into the dictionary. Returns true if the dictionary was
+/// already full and the byte couldn't be added.
+static inline bool
+dict_put(lzma_dict *dict, uint8_t byte)
+{
+        if (unlikely(dict->pos == dict->limit))
+                return true;
+
+        dict->buf[dict->pos++] = byte;
+
+        if (dict->pos > dict->full)
+                dict->full = dict->pos;
+
+        return false;
+}
+
+
+/// Copies arbitrary amount of data into the dictionary.
+static inline void
+dict_write(lzma_dict *restrict dict, const uint8_t *restrict in,
+                size_t *restrict in_pos, size_t in_size,
+                size_t *restrict left)
+{
+        // NOTE: If we are being given more data than the size of the
+        // dictionary, it could be possible to optimize the LZ decoder
+        // so that not everything needs to go through the dictionary.
+        // This shouldn't be very common thing in practice though, and
+        // the slowdown of one extra memcpy() isn't bad compared to how
+        // much time it would have taken if the data were compressed.
+
+        if (in_size - *in_pos > *left)
+                in_size = *in_pos + *left;
+
+        *left -= lzma_bufcpy(in, in_pos, in_size,
+                        dict->buf, &dict->pos, dict->limit);
+
+        if (dict->pos > dict->full)
+                dict->full = dict->pos;
+
+        return;
+}
+
+
+static inline void
+dict_reset(lzma_dict *dict)
+{
+        dict->need_reset = true;
+        return;
+}
+
+#endif