1 | /* |
2 | Copyright (c) 2015-2016, Apple Inc. All rights reserved. |
3 | |
4 | Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: |
5 | |
6 | 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. |
7 | |
8 | 2. 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 | |
11 | 3. 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 | |
14 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
15 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE |
16 | COPYRIGHT 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) |
18 | HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
19 | ARISING 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. */ |
49 | typedef 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 */ |
59 | typedef 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. */ |
72 | typedef 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. */ |
114 | void lzvn_encode(lzvn_encoder_state *state); |
115 | |
116 | #endif // LZVN_ENCODE_BASE_H |
117 | |