1 /* deflate_stored.c -- store data without compression using deflation algorithm
2 *
3 * Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler
4 * For conditions of distribution and use, see copyright notice in zlib.h
5 */
6
7 #include "zbuild.h"
8 #include "deflate.h"
9 #include "deflate_p.h"
10 #include "functable.h"
11
12 /* ===========================================================================
13 * Copy without compression as much as possible from the input stream, return
14 * the current block state.
15 *
16 * In case deflateParams() is used to later switch to a non-zero compression
17 * level, s->matches (otherwise unused when storing) keeps track of the number
18 * of hash table slides to perform. If s->matches is 1, then one hash table
19 * slide will be done when switching. If s->matches is 2, the maximum value
20 * allowed here, then the hash table will be cleared, since two or more slides
21 * is the same as a clear.
22 *
23 * deflate_stored() is written to minimize the number of times an input byte is
24 * copied. It is most efficient with large input and output buffers, which
25 * maximizes the opportunites to have a single copy from next_in to next_out.
26 */
deflate_stored(deflate_state * s,int flush)27 Z_INTERNAL block_state deflate_stored(deflate_state *s, int flush) {
28 /* Smallest worthy block size when not flushing or finishing. By default
29 * this is 32K. This can be as small as 507 bytes for memLevel == 1. For
30 * large input and output buffers, the stored block size will be larger.
31 */
32 unsigned min_block = MIN(s->pending_buf_size - 5, s->w_size);
33
34 /* Copy as many min_block or larger stored blocks directly to next_out as
35 * possible. If flushing, copy the remaining available input to next_out as
36 * stored blocks, if there is enough space.
37 */
38 unsigned len, left, have, last = 0;
39 unsigned used = s->strm->avail_in;
40 do {
41 /* Set len to the maximum size block that we can copy directly with the
42 * available input data and output space. Set left to how much of that
43 * would be copied from what's left in the window.
44 */
45 len = MAX_STORED; /* maximum deflate stored block length */
46 have = (s->bi_valid + 42) >> 3; /* number of header bytes */
47 if (s->strm->avail_out < have) /* need room for header */
48 break;
49 /* maximum stored block length that will fit in avail_out: */
50 have = s->strm->avail_out - have;
51 left = (int)s->strstart - s->block_start; /* bytes left in window */
52 if (len > (unsigned long)left + s->strm->avail_in)
53 len = left + s->strm->avail_in; /* limit len to the input */
54 len = MIN(len, have); /* limit len to the output */
55
56 /* If the stored block would be less than min_block in length, or if
57 * unable to copy all of the available input when flushing, then try
58 * copying to the window and the pending buffer instead. Also don't
59 * write an empty block when flushing -- deflate() does that.
60 */
61 if (len < min_block && ((len == 0 && flush != Z_FINISH) || flush == Z_NO_FLUSH || len != left + s->strm->avail_in))
62 break;
63
64 /* Make a dummy stored block in pending to get the header bytes,
65 * including any pending bits. This also updates the debugging counts.
66 */
67 last = flush == Z_FINISH && len == left + s->strm->avail_in ? 1 : 0;
68 zng_tr_stored_block(s, (char *)0, 0L, last);
69
70 /* Replace the lengths in the dummy stored block with len. */
71 s->pending -= 4;
72 put_short(s, (uint16_t)len);
73 put_short(s, (uint16_t)~len);
74
75 /* Write the stored block header bytes. */
76 PREFIX(flush_pending)(s->strm);
77
78 /* Update debugging counts for the data about to be copied. */
79 cmpr_bits_add(s, len << 3);
80 sent_bits_add(s, len << 3);
81
82 /* Copy uncompressed bytes from the window to next_out. */
83 if (left) {
84 left = MIN(left, len);
85 memcpy(s->strm->next_out, s->window + s->block_start, left);
86 s->strm->next_out += left;
87 s->strm->avail_out -= left;
88 s->strm->total_out += left;
89 s->block_start += (int)left;
90 len -= left;
91 }
92
93 /* Copy uncompressed bytes directly from next_in to next_out, updating
94 * the check value.
95 */
96 if (len) {
97 read_buf(s->strm, s->strm->next_out, len);
98 s->strm->next_out += len;
99 s->strm->avail_out -= len;
100 s->strm->total_out += len;
101 }
102 } while (last == 0);
103
104 /* Update the sliding window with the last s->w_size bytes of the copied
105 * data, or append all of the copied data to the existing window if less
106 * than s->w_size bytes were copied. Also update the number of bytes to
107 * insert in the hash tables, in the event that deflateParams() switches to
108 * a non-zero compression level.
109 */
110 used -= s->strm->avail_in; /* number of input bytes directly copied */
111 if (used) {
112 /* If any input was used, then no unused input remains in the window,
113 * therefore s->block_start == s->strstart.
114 */
115 if (used >= s->w_size) { /* supplant the previous history */
116 s->matches = 2; /* clear hash */
117 memcpy(s->window, s->strm->next_in - s->w_size, s->w_size);
118 s->strstart = s->w_size;
119 s->insert = s->strstart;
120 } else {
121 if (s->window_size - s->strstart <= used) {
122 /* Slide the window down. */
123 s->strstart -= s->w_size;
124 memcpy(s->window, s->window + s->w_size, s->strstart);
125 if (s->matches < 2)
126 s->matches++; /* add a pending slide_hash() */
127 s->insert = MIN(s->insert, s->strstart);
128 }
129 memcpy(s->window + s->strstart, s->strm->next_in - used, used);
130 s->strstart += used;
131 s->insert += MIN(used, s->w_size - s->insert);
132 }
133 s->block_start = (int)s->strstart;
134 }
135 s->high_water = MAX(s->high_water, s->strstart);
136
137 /* If the last block was written to next_out, then done. */
138 if (last)
139 return finish_done;
140
141 /* If flushing and all input has been consumed, then done. */
142 if (flush != Z_NO_FLUSH && flush != Z_FINISH && s->strm->avail_in == 0 && (int)s->strstart == s->block_start)
143 return block_done;
144
145 /* Fill the window with any remaining input. */
146 have = s->window_size - s->strstart;
147 if (s->strm->avail_in > have && s->block_start >= (int)s->w_size) {
148 /* Slide the window down. */
149 s->block_start -= (int)s->w_size;
150 s->strstart -= s->w_size;
151 memcpy(s->window, s->window + s->w_size, s->strstart);
152 if (s->matches < 2)
153 s->matches++; /* add a pending slide_hash() */
154 have += s->w_size; /* more space now */
155 s->insert = MIN(s->insert, s->strstart);
156 }
157
158 have = MIN(have, s->strm->avail_in);
159 if (have) {
160 read_buf(s->strm, s->window + s->strstart, have);
161 s->strstart += have;
162 s->insert += MIN(have, s->w_size - s->insert);
163 }
164 s->high_water = MAX(s->high_water, s->strstart);
165
166 /* There was not enough avail_out to write a complete worthy or flushed
167 * stored block to next_out. Write a stored block to pending instead, if we
168 * have enough input for a worthy block, or if flushing and there is enough
169 * room for the remaining input as a stored block in the pending buffer.
170 */
171 have = (s->bi_valid + 42) >> 3; /* number of header bytes */
172 /* maximum stored block length that will fit in pending: */
173 have = MIN(s->pending_buf_size - have, MAX_STORED);
174 min_block = MIN(have, s->w_size);
175 left = (int)s->strstart - s->block_start;
176 if (left >= min_block || ((left || flush == Z_FINISH) && flush != Z_NO_FLUSH && s->strm->avail_in == 0 && left <= have)) {
177 len = MIN(left, have);
178 last = flush == Z_FINISH && s->strm->avail_in == 0 && len == left ? 1 : 0;
179 zng_tr_stored_block(s, (char *)s->window + s->block_start, len, last);
180 s->block_start += (int)len;
181 PREFIX(flush_pending)(s->strm);
182 }
183
184 /* We've done all we can with the available input and output. */
185 return last ? finish_started : need_more;
186 }
187