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
|
/*
* The deflate_quick deflate strategy, designed to be used when cycles are
* at a premium.
*
* Copyright (C) 2013 Intel Corporation. All rights reserved.
* Authors:
* Wajdi Feghali <wajdi.k.feghali@intel.com>
* Jim Guilford <james.guilford@intel.com>
* Vinodh Gopal <vinodh.gopal@intel.com>
* Erdinc Ozturk <erdinc.ozturk@intel.com>
* Jim Kukunas <james.t.kukunas@linux.intel.com>
*
* Portions are Copyright (C) 2016 12Sided Technology, LLC.
* Author:
* Phil Vachon <pvachon@12sidedtech.com>
*
* For conditions of distribution and use, see copyright notice in zlib.h
*/
#include "zbuild.h"
#include "deflate.h"
#include "deflate_p.h"
#include "functable.h"
#include "trees_emit.h"
extern const ct_data static_ltree[L_CODES+2];
extern const ct_data static_dtree[D_CODES];
#define QUICK_START_BLOCK(s, last) { \
zng_tr_emit_tree(s, STATIC_TREES, last); \
s->block_open = 1 + (int)last; \
s->block_start = (int)s->strstart; \
}
#define QUICK_END_BLOCK(s, last) { \
if (s->block_open) { \
zng_tr_emit_end_block(s, static_ltree, last); \
s->block_open = 0; \
s->block_start = (int)s->strstart; \
PREFIX(flush_pending)(s->strm); \
if (s->strm->avail_out == 0) \
return (last) ? finish_started : need_more; \
} \
}
Z_INTERNAL block_state deflate_quick(deflate_state *s, int flush) {
Pos hash_head;
int64_t dist;
unsigned match_len, last;
last = (flush == Z_FINISH) ? 1 : 0;
if (UNLIKELY(last && s->block_open != 2)) {
/* Emit end of previous block */
QUICK_END_BLOCK(s, 0);
/* Emit start of last block */
QUICK_START_BLOCK(s, last);
} else if (UNLIKELY(s->block_open == 0 && s->lookahead > 0)) {
/* Start new block only when we have lookahead data, so that if no
input data is given an empty block will not be written */
QUICK_START_BLOCK(s, last);
}
for (;;) {
if (UNLIKELY(s->pending + ((BIT_BUF_SIZE + 7) >> 3) >= s->pending_buf_size)) {
PREFIX(flush_pending)(s->strm);
if (s->strm->avail_out == 0) {
return (last && s->strm->avail_in == 0 && s->bi_valid == 0 && s->block_open == 0) ? finish_started : need_more;
}
}
if (UNLIKELY(s->lookahead < MIN_LOOKAHEAD)) {
fill_window(s);
if (UNLIKELY(s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH)) {
return need_more;
}
if (UNLIKELY(s->lookahead == 0))
break;
if (UNLIKELY(s->block_open == 0)) {
/* Start new block when we have lookahead data, so that if no
input data is given an empty block will not be written */
QUICK_START_BLOCK(s, last);
}
}
if (LIKELY(s->lookahead >= WANT_MIN_MATCH)) {
hash_head = functable.quick_insert_string(s, s->strstart);
dist = (int64_t)s->strstart - hash_head;
if (dist <= MAX_DIST(s) && dist > 0) {
const uint8_t *str_start = s->window + s->strstart;
const uint8_t *match_start = s->window + hash_head;
if (zmemcmp_2(str_start, match_start) == 0) {
match_len = functable.compare256(str_start+2, match_start+2) + 2;
if (match_len >= WANT_MIN_MATCH) {
if (UNLIKELY(match_len > s->lookahead))
match_len = s->lookahead;
check_match(s, s->strstart, hash_head, match_len);
zng_tr_emit_dist(s, static_ltree, static_dtree, match_len - STD_MIN_MATCH, (uint32_t)dist);
s->lookahead -= match_len;
s->strstart += match_len;
continue;
}
}
}
}
zng_tr_emit_lit(s, static_ltree, s->window[s->strstart]);
s->strstart++;
s->lookahead--;
}
s->insert = s->strstart < (STD_MIN_MATCH - 1) ? s->strstart : (STD_MIN_MATCH - 1);
if (UNLIKELY(last)) {
QUICK_END_BLOCK(s, 1);
return finish_done;
}
QUICK_END_BLOCK(s, 0);
return block_done;
}
|
