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