1/*
2Copyright (c) 2015-2016, Apple Inc. All rights reserved.
3
4Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
5
61. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
7
82. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer
9 in the documentation and/or other materials provided with the distribution.
10
113. Neither the name of the copyright holder(s) nor the names of any contributors may be used to endorse or promote products derived
12 from this software without specific prior written permission.
13
14THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
15LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
16COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
17(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
18HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
19ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
20*/
21
22// LZVN low-level encoder
23
24#ifndef LZVN_ENCODE_BASE_H
25#define LZVN_ENCODE_BASE_H
26
27#include "lzfse_internal.h"
28
29// ===============================================================
30// Types and Constants
31
32#define LZVN_ENCODE_HASH_BITS \
33 14 // number of bits returned by the hash function [10, 16]
34#define LZVN_ENCODE_OFFSETS_PER_HASH \
35 4 // stored offsets stack for each hash value, MUST be 4
36#define LZVN_ENCODE_HASH_VALUES \
37 (1 << LZVN_ENCODE_HASH_BITS) // number of entries in hash table
38#define LZVN_ENCODE_MAX_DISTANCE \
39 0xffff // max match distance we can represent with LZVN encoding, MUST be
40 // 0xFFFF
41#define LZVN_ENCODE_MIN_MARGIN \
42 8 // min number of bytes required between current and end during encoding,
43 // MUST be >= 8
44#define LZVN_ENCODE_MAX_LITERAL_BACKLOG \
45 400 // if the number of pending literals exceeds this size, emit a long
46 // literal, MUST be >= 271
47
48/*! @abstract Type of table entry. */
49typedef struct {
50 int32_t indices[4]; // signed indices in source buffer
51 uint32_t values[4]; // corresponding 32-bit values
52} lzvn_encode_entry_type;
53
54// Work size
55#define LZVN_ENCODE_WORK_SIZE \
56 (LZVN_ENCODE_HASH_VALUES * sizeof(lzvn_encode_entry_type))
57
58/*! @abstract Match */
59typedef struct {
60 lzvn_offset m_begin; // beginning of match, current position
61 lzvn_offset m_end; // end of match, this is where the next literal would begin
62 // if we emit the entire match
63 lzvn_offset M; // match length M: m_end - m_begin
64 lzvn_offset D; // match distance D
65 lzvn_offset K; // match gain: M - distance storage (L not included)
66} lzvn_match_info;
67
68// ===============================================================
69// Internal encoder state
70
71/*! @abstract Base encoder state and I/O. */
72typedef struct {
73
74 // Encoder I/O
75
76 // Source buffer
77 const unsigned char *src;
78 // Valid range in source buffer: we can access src[i] for src_begin <= i <
79 // src_end. src_begin may be negative.
80 lzvn_offset src_begin;
81 lzvn_offset src_end;
82 // Next byte to process in source buffer
83 lzvn_offset src_current;
84 // Next byte after the last byte to process in source buffer. We MUST have:
85 // src_current_end + 8 <= src_end.
86 lzvn_offset src_current_end;
87 // Next byte to encode in source buffer, may be before or after src_current.
88 lzvn_offset src_literal;
89
90 // Next byte to write in destination buffer
91 unsigned char *dst;
92 // Valid range in destination buffer: [dst_begin, dst_end - 1]
93 unsigned char *dst_begin;
94 unsigned char *dst_end;
95
96 // Encoder state
97
98 // Pending match
99 lzvn_match_info pending;
100
101 // Distance for last emitted match, or 0
102 lzvn_offset d_prev;
103
104 // Hash table used to find matches. Stores LZVN_ENCODE_OFFSETS_PER_HASH 32-bit
105 // signed indices in the source buffer, and the corresponding 4-byte values.
106 // The number of entries in the table is LZVN_ENCODE_HASH_VALUES.
107 lzvn_encode_entry_type *table;
108
109} lzvn_encoder_state;
110
111/*! @abstract Encode source to destination.
112 * Update \p state.
113 * The call ensures \c src_literal is never left too far behind \c src_current. */
114void lzvn_encode(lzvn_encoder_state *state);
115
116#endif // LZVN_ENCODE_BASE_H
117