1 /* Lzlib - Compression library for the lzip format
2 Copyright (C) 2009-2021 Antonio Diaz Diaz.
3
4 This library is free software. Redistribution and use in source and
5 binary forms, with or without modification, are permitted provided
6 that the following conditions are met:
7
8 1. Redistributions of source code must retain the above copyright
9 notice, this list of conditions, and the following disclaimer.
10
11 2. Redistributions in binary form must reproduce the above copyright
12 notice, this list of conditions, and the following disclaimer in the
13 documentation and/or other materials provided with the distribution.
14
15 This library is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
18 */
19
20 enum { price_shift_bits = 6,
21 price_step_bits = 2 };
22
23 static const uint8_t dis_slots[1<<10] =
24 {
25 0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
26 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9,
27 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
28 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
29 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
30 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
31 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
32 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
33 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
34 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
35 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
36 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
37 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
38 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
39 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
40 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
41 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
42 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
43 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
44 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
45 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
46 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
47 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
48 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
49 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
50 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
51 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
52 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
53 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
54 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
55 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
56 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
57 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
58 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
59 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
60 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
61 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
62 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
63 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
64 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
65 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
66 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
67 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
68 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
69 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
70 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
71 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
72 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
73 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
74 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
75 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
76 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
77 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
78 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
79 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
80 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
81 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
82 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
83 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
84 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
85 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
86 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
87 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
88 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19 };
89
get_slot(const unsigned dis)90 static inline uint8_t get_slot( const unsigned dis )
91 {
92 if( dis < (1 << 10) ) return dis_slots[dis];
93 if( dis < (1 << 19) ) return dis_slots[dis>> 9] + 18;
94 if( dis < (1 << 28) ) return dis_slots[dis>>18] + 36;
95 return dis_slots[dis>>27] + 54;
96 }
97
98
99 static const short prob_prices[bit_model_total >> price_step_bits] =
100 {
101 640, 539, 492, 461, 438, 419, 404, 390, 379, 369, 359, 351, 343, 336, 330, 323,
102 318, 312, 307, 302, 298, 293, 289, 285, 281, 277, 274, 270, 267, 264, 261, 258,
103 255, 252, 250, 247, 244, 242, 239, 237, 235, 232, 230, 228, 226, 224, 222, 220,
104 218, 216, 214, 213, 211, 209, 207, 206, 204, 202, 201, 199, 198, 196, 195, 193,
105 192, 190, 189, 188, 186, 185, 184, 182, 181, 180, 178, 177, 176, 175, 174, 172,
106 171, 170, 169, 168, 167, 166, 165, 164, 163, 162, 161, 159, 158, 157, 157, 156,
107 155, 154, 153, 152, 151, 150, 149, 148, 147, 146, 145, 145, 144, 143, 142, 141,
108 140, 140, 139, 138, 137, 136, 136, 135, 134, 133, 133, 132, 131, 130, 130, 129,
109 128, 127, 127, 126, 125, 125, 124, 123, 123, 122, 121, 121, 120, 119, 119, 118,
110 117, 117, 116, 115, 115, 114, 114, 113, 112, 112, 111, 111, 110, 109, 109, 108,
111 108, 107, 106, 106, 105, 105, 104, 104, 103, 103, 102, 101, 101, 100, 100, 99,
112 99, 98, 98, 97, 97, 96, 96, 95, 95, 94, 94, 93, 93, 92, 92, 91,
113 91, 90, 90, 89, 89, 88, 88, 88, 87, 87, 86, 86, 85, 85, 84, 84,
114 83, 83, 83, 82, 82, 81, 81, 80, 80, 80, 79, 79, 78, 78, 77, 77,
115 77, 76, 76, 75, 75, 75, 74, 74, 73, 73, 73, 72, 72, 71, 71, 71,
116 70, 70, 70, 69, 69, 68, 68, 68, 67, 67, 67, 66, 66, 65, 65, 65,
117 64, 64, 64, 63, 63, 63, 62, 62, 61, 61, 61, 60, 60, 60, 59, 59,
118 59, 58, 58, 58, 57, 57, 57, 56, 56, 56, 55, 55, 55, 54, 54, 54,
119 53, 53, 53, 53, 52, 52, 52, 51, 51, 51, 50, 50, 50, 49, 49, 49,
120 48, 48, 48, 48, 47, 47, 47, 46, 46, 46, 45, 45, 45, 45, 44, 44,
121 44, 43, 43, 43, 43, 42, 42, 42, 41, 41, 41, 41, 40, 40, 40, 40,
122 39, 39, 39, 38, 38, 38, 38, 37, 37, 37, 37, 36, 36, 36, 35, 35,
123 35, 35, 34, 34, 34, 34, 33, 33, 33, 33, 32, 32, 32, 32, 31, 31,
124 31, 31, 30, 30, 30, 30, 29, 29, 29, 29, 28, 28, 28, 28, 27, 27,
125 27, 27, 26, 26, 26, 26, 26, 25, 25, 25, 25, 24, 24, 24, 24, 23,
126 23, 23, 23, 22, 22, 22, 22, 22, 21, 21, 21, 21, 20, 20, 20, 20,
127 20, 19, 19, 19, 19, 18, 18, 18, 18, 18, 17, 17, 17, 17, 17, 16,
128 16, 16, 16, 15, 15, 15, 15, 15, 14, 14, 14, 14, 14, 13, 13, 13,
129 13, 13, 12, 12, 12, 12, 12, 11, 11, 11, 11, 10, 10, 10, 10, 10,
130 9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7,
131 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4,
132 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1 };
133
get_price(const int probability)134 static inline int get_price( const int probability )
135 { return prob_prices[probability >> price_step_bits]; }
136
137
price0(const Bit_model probability)138 static inline int price0( const Bit_model probability )
139 { return get_price( probability ); }
140
price1(const Bit_model probability)141 static inline int price1( const Bit_model probability )
142 { return get_price( bit_model_total - probability ); }
143
price_bit(const Bit_model bm,const bool bit)144 static inline int price_bit( const Bit_model bm, const bool bit )
145 { return ( bit ? price1( bm ) : price0( bm ) ); }
146
147
price_symbol3(const Bit_model bm[],int symbol)148 static inline int price_symbol3( const Bit_model bm[], int symbol )
149 {
150 int price;
151 bool bit = symbol & 1;
152 symbol |= 8; symbol >>= 1;
153 price = price_bit( bm[symbol], bit );
154 bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit );
155 return price + price_bit( bm[1], symbol & 1 );
156 }
157
158
price_symbol6(const Bit_model bm[],unsigned symbol)159 static inline int price_symbol6( const Bit_model bm[], unsigned symbol )
160 {
161 int price;
162 bool bit = symbol & 1;
163 symbol |= 64; symbol >>= 1;
164 price = price_bit( bm[symbol], bit );
165 bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit );
166 bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit );
167 bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit );
168 bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit );
169 return price + price_bit( bm[1], symbol & 1 );
170 }
171
172
price_symbol8(const Bit_model bm[],int symbol)173 static inline int price_symbol8( const Bit_model bm[], int symbol )
174 {
175 int price;
176 bool bit = symbol & 1;
177 symbol |= 0x100; symbol >>= 1;
178 price = price_bit( bm[symbol], bit );
179 bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit );
180 bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit );
181 bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit );
182 bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit );
183 bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit );
184 bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit );
185 return price + price_bit( bm[1], symbol & 1 );
186 }
187
188
price_symbol_reversed(const Bit_model bm[],int symbol,const int num_bits)189 static inline int price_symbol_reversed( const Bit_model bm[], int symbol,
190 const int num_bits )
191 {
192 int price = 0;
193 int model = 1;
194 int i;
195 for( i = num_bits; i > 0; --i )
196 {
197 const bool bit = symbol & 1;
198 symbol >>= 1;
199 price += price_bit( bm[model], bit );
200 model <<= 1; model |= bit;
201 }
202 return price;
203 }
204
205
price_matched(const Bit_model bm[],unsigned symbol,unsigned match_byte)206 static inline int price_matched( const Bit_model bm[], unsigned symbol,
207 unsigned match_byte )
208 {
209 int price = 0;
210 unsigned mask = 0x100;
211 symbol |= mask;
212 while( true )
213 {
214 const unsigned match_bit = ( match_byte <<= 1 ) & mask;
215 const bool bit = ( symbol <<= 1 ) & 0x100;
216 price += price_bit( bm[(symbol>>9)+match_bit+mask], bit );
217 if( symbol >= 0x10000 ) return price;
218 mask &= ~(match_bit ^ symbol); /* if( match_bit != bit ) mask = 0; */
219 }
220 }
221
222
223 struct Matchfinder_base
224 {
225 unsigned long long partial_data_pos;
226 uint8_t * buffer; /* input buffer */
227 int32_t * prev_positions; /* 1 + last seen position of key. else 0 */
228 int32_t * pos_array; /* may be tree or chain */
229 int before_size; /* bytes to keep in buffer before dictionary */
230 int after_size; /* bytes to keep in buffer after pos */
231 int buffer_size;
232 int dictionary_size; /* bytes to keep in buffer before pos */
233 int pos; /* current pos in buffer */
234 int cyclic_pos; /* cycles through [0, dictionary_size] */
235 int stream_pos; /* first byte not yet read from file */
236 int pos_limit; /* when reached, a new block must be read */
237 int key4_mask;
238 int num_prev_positions23;
239 int num_prev_positions; /* size of prev_positions */
240 int pos_array_size;
241 int saved_dictionary_size; /* dictionary_size restored by Mb_reset */
242 bool at_stream_end; /* stream_pos shows real end of file */
243 bool sync_flush_pending;
244 };
245
246 static bool Mb_normalize_pos( struct Matchfinder_base * const mb );
247
248 static bool Mb_init( struct Matchfinder_base * const mb, const int before_size,
249 const int dict_size, const int after_size,
250 const int dict_factor, const int num_prev_positions23,
251 const int pos_array_factor );
252
Mb_free(struct Matchfinder_base * const mb)253 static inline void Mb_free( struct Matchfinder_base * const mb )
254 { free( mb->prev_positions ); free( mb->buffer ); }
255
Mb_peek(const struct Matchfinder_base * const mb,const int distance)256 static inline uint8_t Mb_peek( const struct Matchfinder_base * const mb,
257 const int distance )
258 { return mb->buffer[mb->pos-distance]; }
259
Mb_available_bytes(const struct Matchfinder_base * const mb)260 static inline int Mb_available_bytes( const struct Matchfinder_base * const mb )
261 { return mb->stream_pos - mb->pos; }
262
263 static inline unsigned long long
Mb_data_position(const struct Matchfinder_base * const mb)264 Mb_data_position( const struct Matchfinder_base * const mb )
265 { return mb->partial_data_pos + mb->pos; }
266
Mb_finish(struct Matchfinder_base * const mb)267 static inline void Mb_finish( struct Matchfinder_base * const mb )
268 { mb->at_stream_end = true; mb->sync_flush_pending = false; }
269
Mb_data_finished(const struct Matchfinder_base * const mb)270 static inline bool Mb_data_finished( const struct Matchfinder_base * const mb )
271 { return mb->at_stream_end && mb->pos >= mb->stream_pos; }
272
Mb_flushing_or_end(const struct Matchfinder_base * const mb)273 static inline bool Mb_flushing_or_end( const struct Matchfinder_base * const mb )
274 { return mb->at_stream_end || mb->sync_flush_pending; }
275
Mb_free_bytes(const struct Matchfinder_base * const mb)276 static inline int Mb_free_bytes( const struct Matchfinder_base * const mb )
277 { if( Mb_flushing_or_end( mb ) ) return 0;
278 return mb->buffer_size - mb->stream_pos; }
279
280 static inline bool
Mb_enough_available_bytes(const struct Matchfinder_base * const mb)281 Mb_enough_available_bytes( const struct Matchfinder_base * const mb )
282 { return ( mb->pos + mb->after_size <= mb->stream_pos ||
283 ( Mb_flushing_or_end( mb ) && mb->pos < mb->stream_pos ) ); }
284
285 static inline const uint8_t *
Mb_ptr_to_current_pos(const struct Matchfinder_base * const mb)286 Mb_ptr_to_current_pos( const struct Matchfinder_base * const mb )
287 { return mb->buffer + mb->pos; }
288
Mb_write_data(struct Matchfinder_base * const mb,const uint8_t * const inbuf,const int size)289 static int Mb_write_data( struct Matchfinder_base * const mb,
290 const uint8_t * const inbuf, const int size )
291 {
292 const int sz = min( mb->buffer_size - mb->stream_pos, size );
293 if( Mb_flushing_or_end( mb ) || sz <= 0 ) return 0;
294 memcpy( mb->buffer + mb->stream_pos, inbuf, sz );
295 mb->stream_pos += sz;
296 return sz;
297 }
298
Mb_true_match_len(const struct Matchfinder_base * const mb,const int index,const int distance)299 static inline int Mb_true_match_len( const struct Matchfinder_base * const mb,
300 const int index, const int distance )
301 {
302 const uint8_t * const data = mb->buffer + mb->pos;
303 int i = index;
304 const int len_limit = min( Mb_available_bytes( mb ), max_match_len );
305 while( i < len_limit && data[i-distance] == data[i] ) ++i;
306 return i;
307 }
308
Mb_move_pos(struct Matchfinder_base * const mb)309 static inline bool Mb_move_pos( struct Matchfinder_base * const mb )
310 {
311 if( ++mb->cyclic_pos > mb->dictionary_size ) mb->cyclic_pos = 0;
312 if( ++mb->pos >= mb->pos_limit ) return Mb_normalize_pos( mb );
313 return true;
314 }
315
316
317 struct Range_encoder
318 {
319 struct Circular_buffer cb;
320 unsigned min_free_bytes;
321 uint64_t low;
322 unsigned long long partial_member_pos;
323 uint32_t range;
324 unsigned ff_count;
325 uint8_t cache;
326 Lzip_header header;
327 };
328
Re_shift_low(struct Range_encoder * const renc)329 static inline void Re_shift_low( struct Range_encoder * const renc )
330 {
331 if( renc->low >> 24 != 0xFF )
332 {
333 const bool carry = ( renc->low > 0xFFFFFFFFU );
334 Cb_put_byte( &renc->cb, renc->cache + carry );
335 for( ; renc->ff_count > 0; --renc->ff_count )
336 Cb_put_byte( &renc->cb, 0xFF + carry );
337 renc->cache = renc->low >> 24;
338 }
339 else ++renc->ff_count;
340 renc->low = ( renc->low & 0x00FFFFFFU ) << 8;
341 }
342
Re_reset(struct Range_encoder * const renc,const unsigned dictionary_size)343 static inline void Re_reset( struct Range_encoder * const renc,
344 const unsigned dictionary_size )
345 {
346 int i;
347 Cb_reset( &renc->cb );
348 renc->low = 0;
349 renc->partial_member_pos = 0;
350 renc->range = 0xFFFFFFFFU;
351 renc->ff_count = 0;
352 renc->cache = 0;
353 Lh_set_dictionary_size( renc->header, dictionary_size );
354 for( i = 0; i < Lh_size; ++i )
355 Cb_put_byte( &renc->cb, renc->header[i] );
356 }
357
Re_init(struct Range_encoder * const renc,const unsigned dictionary_size,const unsigned min_free_bytes)358 static inline bool Re_init( struct Range_encoder * const renc,
359 const unsigned dictionary_size,
360 const unsigned min_free_bytes )
361 {
362 if( !Cb_init( &renc->cb, 65536 + min_free_bytes ) ) return false;
363 renc->min_free_bytes = min_free_bytes;
364 Lh_set_magic( renc->header );
365 Re_reset( renc, dictionary_size );
366 return true;
367 }
368
Re_free(struct Range_encoder * const renc)369 static inline void Re_free( struct Range_encoder * const renc )
370 { Cb_free( &renc->cb ); }
371
372 static inline unsigned long long
Re_member_position(const struct Range_encoder * const renc)373 Re_member_position( const struct Range_encoder * const renc )
374 { return renc->partial_member_pos + Cb_used_bytes( &renc->cb ) + renc->ff_count; }
375
Re_enough_free_bytes(const struct Range_encoder * const renc)376 static inline bool Re_enough_free_bytes( const struct Range_encoder * const renc )
377 { return Cb_free_bytes( &renc->cb ) >= renc->min_free_bytes + renc->ff_count; }
378
Re_read_data(struct Range_encoder * const renc,uint8_t * const out_buffer,const int out_size)379 static inline int Re_read_data( struct Range_encoder * const renc,
380 uint8_t * const out_buffer, const int out_size )
381 {
382 const int size = Cb_read_data( &renc->cb, out_buffer, out_size );
383 if( size > 0 ) renc->partial_member_pos += size;
384 return size;
385 }
386
Re_flush(struct Range_encoder * const renc)387 static inline void Re_flush( struct Range_encoder * const renc )
388 {
389 int i; for( i = 0; i < 5; ++i ) Re_shift_low( renc );
390 renc->low = 0;
391 renc->range = 0xFFFFFFFFU;
392 renc->ff_count = 0;
393 renc->cache = 0;
394 }
395
Re_encode(struct Range_encoder * const renc,const int symbol,const int num_bits)396 static inline void Re_encode( struct Range_encoder * const renc,
397 const int symbol, const int num_bits )
398 {
399 unsigned mask;
400 for( mask = 1 << ( num_bits - 1 ); mask > 0; mask >>= 1 )
401 {
402 renc->range >>= 1;
403 if( symbol & mask ) renc->low += renc->range;
404 if( renc->range <= 0x00FFFFFFU )
405 { renc->range <<= 8; Re_shift_low( renc ); }
406 }
407 }
408
Re_encode_bit(struct Range_encoder * const renc,Bit_model * const probability,const bool bit)409 static inline void Re_encode_bit( struct Range_encoder * const renc,
410 Bit_model * const probability, const bool bit )
411 {
412 const uint32_t bound = ( renc->range >> bit_model_total_bits ) * *probability;
413 if( !bit )
414 {
415 renc->range = bound;
416 *probability += (bit_model_total - *probability) >> bit_model_move_bits;
417 }
418 else
419 {
420 renc->low += bound;
421 renc->range -= bound;
422 *probability -= *probability >> bit_model_move_bits;
423 }
424 if( renc->range <= 0x00FFFFFFU ) { renc->range <<= 8; Re_shift_low( renc ); }
425 }
426
Re_encode_tree3(struct Range_encoder * const renc,Bit_model bm[],const int symbol)427 static inline void Re_encode_tree3( struct Range_encoder * const renc,
428 Bit_model bm[], const int symbol )
429 {
430 int model;
431 bool bit = ( symbol >> 2 ) & 1;
432 Re_encode_bit( renc, &bm[1], bit );
433 model = 2 | bit;
434 bit = ( symbol >> 1 ) & 1;
435 Re_encode_bit( renc, &bm[model], bit ); model <<= 1; model |= bit;
436 Re_encode_bit( renc, &bm[model], symbol & 1 );
437 }
438
Re_encode_tree6(struct Range_encoder * const renc,Bit_model bm[],const unsigned symbol)439 static inline void Re_encode_tree6( struct Range_encoder * const renc,
440 Bit_model bm[], const unsigned symbol )
441 {
442 int model;
443 bool bit = ( symbol >> 5 ) & 1;
444 Re_encode_bit( renc, &bm[1], bit );
445 model = 2 | bit;
446 bit = ( symbol >> 4 ) & 1;
447 Re_encode_bit( renc, &bm[model], bit ); model <<= 1; model |= bit;
448 bit = ( symbol >> 3 ) & 1;
449 Re_encode_bit( renc, &bm[model], bit ); model <<= 1; model |= bit;
450 bit = ( symbol >> 2 ) & 1;
451 Re_encode_bit( renc, &bm[model], bit ); model <<= 1; model |= bit;
452 bit = ( symbol >> 1 ) & 1;
453 Re_encode_bit( renc, &bm[model], bit ); model <<= 1; model |= bit;
454 Re_encode_bit( renc, &bm[model], symbol & 1 );
455 }
456
Re_encode_tree8(struct Range_encoder * const renc,Bit_model bm[],const int symbol)457 static inline void Re_encode_tree8( struct Range_encoder * const renc,
458 Bit_model bm[], const int symbol )
459 {
460 int model = 1;
461 int i;
462 for( i = 7; i >= 0; --i )
463 {
464 const bool bit = ( symbol >> i ) & 1;
465 Re_encode_bit( renc, &bm[model], bit );
466 model <<= 1; model |= bit;
467 }
468 }
469
Re_encode_tree_reversed(struct Range_encoder * const renc,Bit_model bm[],int symbol,const int num_bits)470 static inline void Re_encode_tree_reversed( struct Range_encoder * const renc,
471 Bit_model bm[], int symbol, const int num_bits )
472 {
473 int model = 1;
474 int i;
475 for( i = num_bits; i > 0; --i )
476 {
477 const bool bit = symbol & 1;
478 symbol >>= 1;
479 Re_encode_bit( renc, &bm[model], bit );
480 model <<= 1; model |= bit;
481 }
482 }
483
Re_encode_matched(struct Range_encoder * const renc,Bit_model bm[],unsigned symbol,unsigned match_byte)484 static inline void Re_encode_matched( struct Range_encoder * const renc,
485 Bit_model bm[], unsigned symbol,
486 unsigned match_byte )
487 {
488 unsigned mask = 0x100;
489 symbol |= mask;
490 while( true )
491 {
492 const unsigned match_bit = ( match_byte <<= 1 ) & mask;
493 const bool bit = ( symbol <<= 1 ) & 0x100;
494 Re_encode_bit( renc, &bm[(symbol>>9)+match_bit+mask], bit );
495 if( symbol >= 0x10000 ) break;
496 mask &= ~(match_bit ^ symbol); /* if( match_bit != bit ) mask = 0; */
497 }
498 }
499
Re_encode_len(struct Range_encoder * const renc,struct Len_model * const lm,int symbol,const int pos_state)500 static inline void Re_encode_len( struct Range_encoder * const renc,
501 struct Len_model * const lm,
502 int symbol, const int pos_state )
503 {
504 bool bit = ( ( symbol -= min_match_len ) >= len_low_symbols );
505 Re_encode_bit( renc, &lm->choice1, bit );
506 if( !bit )
507 Re_encode_tree3( renc, lm->bm_low[pos_state], symbol );
508 else
509 {
510 bit = ( ( symbol -= len_low_symbols ) >= len_mid_symbols );
511 Re_encode_bit( renc, &lm->choice2, bit );
512 if( !bit )
513 Re_encode_tree3( renc, lm->bm_mid[pos_state], symbol );
514 else
515 Re_encode_tree8( renc, lm->bm_high, symbol - len_mid_symbols );
516 }
517 }
518
519
520 enum { max_marker_size = 16,
521 num_rep_distances = 4 }; /* must be 4 */
522
523 struct LZ_encoder_base
524 {
525 struct Matchfinder_base mb;
526 unsigned long long member_size_limit;
527 uint32_t crc;
528
529 Bit_model bm_literal[1<<literal_context_bits][0x300];
530 Bit_model bm_match[states][pos_states];
531 Bit_model bm_rep[states];
532 Bit_model bm_rep0[states];
533 Bit_model bm_rep1[states];
534 Bit_model bm_rep2[states];
535 Bit_model bm_len[states][pos_states];
536 Bit_model bm_dis_slot[len_states][1<<dis_slot_bits];
537 Bit_model bm_dis[modeled_distances-end_dis_model+1];
538 Bit_model bm_align[dis_align_size];
539 struct Len_model match_len_model;
540 struct Len_model rep_len_model;
541 struct Range_encoder renc;
542 int reps[num_rep_distances];
543 State state;
544 bool member_finished;
545 };
546
547 static void LZeb_reset( struct LZ_encoder_base * const eb,
548 const unsigned long long member_size );
549
LZeb_init(struct LZ_encoder_base * const eb,const int before_size,const int dict_size,const int after_size,const int dict_factor,const int num_prev_positions23,const int pos_array_factor,const unsigned min_free_bytes,const unsigned long long member_size)550 static inline bool LZeb_init( struct LZ_encoder_base * const eb,
551 const int before_size, const int dict_size,
552 const int after_size, const int dict_factor,
553 const int num_prev_positions23,
554 const int pos_array_factor,
555 const unsigned min_free_bytes,
556 const unsigned long long member_size )
557 {
558 if( !Mb_init( &eb->mb, before_size, dict_size, after_size, dict_factor,
559 num_prev_positions23, pos_array_factor ) ) return false;
560 if( !Re_init( &eb->renc, eb->mb.dictionary_size, min_free_bytes ) )
561 return false;
562 LZeb_reset( eb, member_size );
563 return true;
564 }
565
LZeb_member_finished(const struct LZ_encoder_base * const eb)566 static inline bool LZeb_member_finished( const struct LZ_encoder_base * const eb )
567 { return ( eb->member_finished && Cb_empty( &eb->renc.cb ) ); }
568
LZeb_free(struct LZ_encoder_base * const eb)569 static inline void LZeb_free( struct LZ_encoder_base * const eb )
570 { Re_free( &eb->renc ); Mb_free( &eb->mb ); }
571
LZeb_crc(const struct LZ_encoder_base * const eb)572 static inline unsigned LZeb_crc( const struct LZ_encoder_base * const eb )
573 { return eb->crc ^ 0xFFFFFFFFU; }
574
LZeb_price_literal(const struct LZ_encoder_base * const eb,const uint8_t prev_byte,const uint8_t symbol)575 static inline int LZeb_price_literal( const struct LZ_encoder_base * const eb,
576 const uint8_t prev_byte, const uint8_t symbol )
577 { return price_symbol8( eb->bm_literal[get_lit_state(prev_byte)], symbol ); }
578
LZeb_price_matched(const struct LZ_encoder_base * const eb,const uint8_t prev_byte,const uint8_t symbol,const uint8_t match_byte)579 static inline int LZeb_price_matched( const struct LZ_encoder_base * const eb,
580 const uint8_t prev_byte, const uint8_t symbol, const uint8_t match_byte )
581 { return price_matched( eb->bm_literal[get_lit_state(prev_byte)], symbol,
582 match_byte ); }
583
LZeb_encode_literal(struct LZ_encoder_base * const eb,const uint8_t prev_byte,const uint8_t symbol)584 static inline void LZeb_encode_literal( struct LZ_encoder_base * const eb,
585 const uint8_t prev_byte, const uint8_t symbol )
586 { Re_encode_tree8( &eb->renc, eb->bm_literal[get_lit_state(prev_byte)],
587 symbol ); }
588
LZeb_encode_matched(struct LZ_encoder_base * const eb,const uint8_t prev_byte,const uint8_t symbol,const uint8_t match_byte)589 static inline void LZeb_encode_matched( struct LZ_encoder_base * const eb,
590 const uint8_t prev_byte, const uint8_t symbol, const uint8_t match_byte )
591 { Re_encode_matched( &eb->renc, eb->bm_literal[get_lit_state(prev_byte)],
592 symbol, match_byte ); }
593
LZeb_encode_pair(struct LZ_encoder_base * const eb,const unsigned dis,const int len,const int pos_state)594 static inline void LZeb_encode_pair( struct LZ_encoder_base * const eb,
595 const unsigned dis, const int len,
596 const int pos_state )
597 {
598 const unsigned dis_slot = get_slot( dis );
599 Re_encode_len( &eb->renc, &eb->match_len_model, len, pos_state );
600 Re_encode_tree6( &eb->renc, eb->bm_dis_slot[get_len_state(len)], dis_slot );
601
602 if( dis_slot >= start_dis_model )
603 {
604 const int direct_bits = ( dis_slot >> 1 ) - 1;
605 const unsigned base = ( 2 | ( dis_slot & 1 ) ) << direct_bits;
606 const unsigned direct_dis = dis - base;
607
608 if( dis_slot < end_dis_model )
609 Re_encode_tree_reversed( &eb->renc, eb->bm_dis + ( base - dis_slot ),
610 direct_dis, direct_bits );
611 else
612 {
613 Re_encode( &eb->renc, direct_dis >> dis_align_bits,
614 direct_bits - dis_align_bits );
615 Re_encode_tree_reversed( &eb->renc, eb->bm_align, direct_dis, dis_align_bits );
616 }
617 }
618 }
619