diff options
author | Mark Adler <madler@alumni.caltech.edu> | 2024-03-09 23:40:12 -0800 |
---|---|---|
committer | Mark Adler <madler@alumni.caltech.edu> | 2024-03-10 00:37:23 -0800 |
commit | 4a5e3e7d255f3f8eba9ecdb8bd8080db43bf0aeb (patch) | |
tree | febbe59398ce4dec2ad0c26e236bf0d77d0fd952 /contrib | |
parent | 54e205f8780b91f8c28865ff4d2bb1c9fda79e48 (diff) | |
download | zlib-4a5e3e7d255f3f8eba9ecdb8bd8080db43bf0aeb.tar.gz zlib-4a5e3e7d255f3f8eba9ecdb8bd8080db43bf0aeb.tar.bz2 zlib-4a5e3e7d255f3f8eba9ecdb8bd8080db43bf0aeb.zip |
Add zipAlreadyThere() to minizip zip.c to help avoid duplicates.
Diffstat (limited to 'contrib')
-rw-r--r-- | contrib/minizip/skipset.h | 359 | ||||
-rw-r--r-- | contrib/minizip/zip.c | 239 | ||||
-rw-r--r-- | contrib/minizip/zip.h | 24 |
3 files changed, 612 insertions, 10 deletions
diff --git a/contrib/minizip/skipset.h b/contrib/minizip/skipset.h new file mode 100644 index 0000000..f829b18 --- /dev/null +++ b/contrib/minizip/skipset.h | |||
@@ -0,0 +1,359 @@ | |||
1 | // skipset.h -- set operations using a skiplist | ||
2 | // Copyright (C) 2024 Mark Adler | ||
3 | // See MiniZip_info.txt for the license. | ||
4 | |||
5 | // This implements a skiplist set, i.e. just keys, no data, with ~O(log n) time | ||
6 | // insert and search operations. The application defines the type of a key, and | ||
7 | // provides a function to compare two keys. | ||
8 | |||
9 | // This header is not definitions of functions found in another source file -- | ||
10 | // it creates the set functions, with the application's key type, right where | ||
11 | // the #include is. Before this header is #included, these must be defined: | ||
12 | // | ||
13 | // 1. A macro or typedef for set_key_t, the type of a key. | ||
14 | // 2. A macro or function set_cmp(a, b) to compare two keys. The return values | ||
15 | // are < 0 for a < b, 0 for a == b, and > 0 for a > b. | ||
16 | // 3. A macro or function set_drop(s, k) to release the key k's resources, if | ||
17 | // any, when doing a set_end() or set_clear(). s is a pointer to the set | ||
18 | // that key is in, for use with set_free() if desired. | ||
19 | // | ||
20 | // Example usage: | ||
21 | // | ||
22 | // typedef int set_key_t; | ||
23 | // #define set_cmp(a, b) ((a) < (b) ? -1 : (a) == (b) ? 0 : 1) | ||
24 | // #define set_drop(s, k) | ||
25 | // #include "skipset.h" | ||
26 | // | ||
27 | // int test(void) { // return 0: good, 1: bad, -1: out of memory | ||
28 | // set_t set; | ||
29 | // if (setjmp(set.env)) | ||
30 | // return -1; | ||
31 | // set_start(&set); | ||
32 | // set_insert(&set, 2); | ||
33 | // set_insert(&set, 1); | ||
34 | // set_insert(&set, 7); | ||
35 | // int bad = !set_found(&set, 2); | ||
36 | // bad = bad || set_found(&set, 5); | ||
37 | // set_end(&set); | ||
38 | // return bad; | ||
39 | // } | ||
40 | // | ||
41 | // Interface summary (see more details below): | ||
42 | // - set_t is the type of the set being operated on (a set_t pointer is passed) | ||
43 | // - set_start() initializes a new, empty set (initialize set.env first) | ||
44 | // - set_insert() inserts a new key into the set, or not if it's already there | ||
45 | // - set_found() determines whether or not a key is in the set | ||
46 | // - set_end() ends the use of the set, freeing all memory | ||
47 | // - set_clear() empties the set, equivalent to set_end() and then set_start() | ||
48 | // - set_ok() checks if set appears to be usable, i.e. started and not ended | ||
49 | // | ||
50 | // Auxiliary functions available to the application: | ||
51 | // - set_alloc() allocates memory with optional tracking (#define SET_TRACK) | ||
52 | // - set_free() deallocates memory allocated by set_alloc() | ||
53 | // - set_rand() returns 32 random bits (seeded by set_start()) | ||
54 | |||
55 | #ifndef SKIPSET_H | ||
56 | #define SKIPSET_H | ||
57 | |||
58 | #include <stdlib.h> // realloc(), free(), NULL, size_t | ||
59 | #include <setjmp.h> // jmp_buf, longjmp() | ||
60 | #include <errno.h> // ENOMEM | ||
61 | #include <stdint.h> // int16_t, uint32_t, uint64_t | ||
62 | #include <time.h> // time(), clock() | ||
63 | #include <assert.h> // assert.h | ||
64 | |||
65 | // Structures and functions below noted as "--private--" should not be used by | ||
66 | // the application. set_t is partially private and partially public -- see the | ||
67 | // comments there. | ||
68 | |||
69 | // There is no POSIX random() in MSVC, and rand() is awful. For portability, we | ||
70 | // cannot rely on a library function for random numbers. Instead we use the | ||
71 | // fast and effective algorithm below, invented by Melissa O'Neill. | ||
72 | |||
73 | // *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / www.pcg-random.org | ||
74 | // Licensed under Apache License 2.0 (NO WARRANTY, etc. see website) | ||
75 | // --private-- Random number generator state. | ||
76 | typedef struct { | ||
77 | uint64_t state; // 64-bit generator state | ||
78 | uint64_t inc; // 63-bit sequence id | ||
79 | } set_rand_t; | ||
80 | // --private-- Initialize the state *gen using seed and seq. seed seeds the | ||
81 | // advancing 64-bit state. seq is a sequence selection constant. | ||
82 | void set_seed(set_rand_t *gen, uint64_t seed, uint64_t seq) { | ||
83 | gen->inc = (seq << 1) | 1; | ||
84 | gen->state = (seed + gen->inc) * 6364136223846793005ULL + gen->inc; | ||
85 | } | ||
86 | // Return 32 random bits, advancing the state *gen. | ||
87 | uint32_t set_rand(set_rand_t *gen) { | ||
88 | uint64_t state = gen->state; | ||
89 | gen->state = state * 6364136223846793005ULL + gen->inc; | ||
90 | uint32_t mix = (uint32_t)(((state >> 18) ^ state) >> 27); | ||
91 | int rot = state >> 59; | ||
92 | return (mix >> rot) | (mix << ((-rot) & 31)); | ||
93 | } | ||
94 | // End of PCG32 code. | ||
95 | |||
96 | // --private-- Linked-list node. | ||
97 | typedef struct set_node_s set_node_t; | ||
98 | struct set_node_s { | ||
99 | set_key_t key; // the key (not used for head or path) | ||
100 | int16_t size; // number of allocated pointers in right[] | ||
101 | int16_t fill; // number of pointers in right[] filled in | ||
102 | set_node_t **right; // pointer for each level, each to the right | ||
103 | }; | ||
104 | |||
105 | // A set. The application sets env, may use gen with set_rand(), and may read | ||
106 | // allocs and memory. The remaining variables are --private-- . | ||
107 | typedef struct set_s { | ||
108 | set_node_t *head; // skiplist head -- no key, just links | ||
109 | set_node_t *path; // right[] is path to key from set_found() | ||
110 | set_node_t *node; // node under construction, in case of longjmp() | ||
111 | int16_t depth; // maximum depth of the skiplist | ||
112 | uint64_t ran; // a precious trove of random bits | ||
113 | set_rand_t gen; // random number generator state | ||
114 | jmp_buf env; // setjmp() environment for allocation errors | ||
115 | #ifdef SET_TRACK | ||
116 | size_t allocs; // number of allocations | ||
117 | size_t memory; // total amount of allocated memory (>= requests) | ||
118 | #endif | ||
119 | } set_t; | ||
120 | |||
121 | // Memory allocation and deallocation. set_alloc(set, ptr, size) returns a | ||
122 | // pointer to an allocation of size bytes if ptr is NULL, or the previous | ||
123 | // allocation ptr resized to size bytes. set_alloc() will never return NULL. | ||
124 | // set_free(set, ptr) frees an allocation created by set_alloc(). These may be | ||
125 | // used by the application. e.g. if allocation tracking is desired. | ||
126 | #ifdef SET_TRACK | ||
127 | // Track the number of allocations and the total backing memory size. | ||
128 | # if defined(_WIN32) | ||
129 | # include <malloc.h> | ||
130 | # define SET_ALLOC_SIZE(ptr) _msize(ptr) | ||
131 | # elif defined(__MACH__) | ||
132 | # include <malloc/malloc.h> | ||
133 | # define SET_ALLOC_SIZE(ptr) malloc_size(ptr) | ||
134 | # elif defined(__linux__) | ||
135 | # include <malloc.h> | ||
136 | # define SET_ALLOC_SIZE(ptr) malloc_usable_size(ptr) | ||
137 | # elif defined(__FreeBSD__) | ||
138 | # include <malloc_np.h> | ||
139 | # define SET_ALLOC_SIZE(ptr) malloc_usable_size(ptr) | ||
140 | # elif defined(__NetBSD__) | ||
141 | # include <jemalloc/jemalloc.h> | ||
142 | # define SET_ALLOC_SIZE(ptr) malloc_usable_size(ptr) | ||
143 | # else // e.g. OpenBSD | ||
144 | # define SET_ALLOC_SIZE(ptr) 0 | ||
145 | # endif | ||
146 | // With tracking. | ||
147 | void *set_alloc(set_t *set, void *ptr, size_t size) { | ||
148 | size_t had = ptr == NULL ? 0 : SET_ALLOC_SIZE(ptr); | ||
149 | void *mem = realloc(ptr, size); | ||
150 | if (mem == NULL) | ||
151 | longjmp(set->env, ENOMEM); | ||
152 | set->allocs += ptr == NULL; | ||
153 | set->memory += SET_ALLOC_SIZE(mem) - had; | ||
154 | return mem; | ||
155 | } | ||
156 | void set_free(set_t *set, void *ptr) { | ||
157 | if (ptr != NULL) { | ||
158 | set->allocs--; | ||
159 | set->memory -= SET_ALLOC_SIZE(ptr); | ||
160 | free(ptr); | ||
161 | } | ||
162 | } | ||
163 | #else | ||
164 | // Without tracking. | ||
165 | void *set_alloc(set_t *set, void *ptr, size_t size) { | ||
166 | void *mem = realloc(ptr, size); | ||
167 | if (mem == NULL) | ||
168 | longjmp(set->env, ENOMEM); | ||
169 | return mem; | ||
170 | } | ||
171 | void set_free(set_t *set, void *ptr) { | ||
172 | (void)set; | ||
173 | free(ptr); | ||
174 | } | ||
175 | #endif | ||
176 | |||
177 | // --private-- Grow node's array right[] as needed to be able to hold at least | ||
178 | // want links. If fill is true, assure that the first want links are filled in, | ||
179 | // setting them to set->head if not previously filled in. Otherwise it is | ||
180 | // assumed that the first want links are about to be filled in. | ||
181 | void set_grow(set_t *set, set_node_t *node, int want, int fill) { | ||
182 | if (node->size < want) { | ||
183 | int more = node->size ? node->size : 1; | ||
184 | while (more < want) | ||
185 | more <<= 1; | ||
186 | node->right = set_alloc(set, node->right, more * sizeof(set_node_t *)); | ||
187 | node->size = (int16_t)more; | ||
188 | } | ||
189 | int i; | ||
190 | if (fill) | ||
191 | for (i = node->fill; i < want; i++) | ||
192 | node->right[i] = set->head; | ||
193 | node->fill = (int16_t)want; | ||
194 | } | ||
195 | |||
196 | // --private-- Return a new node. key is left uninitialized. | ||
197 | set_node_t *set_node(set_t *set) { | ||
198 | set_node_t *node = set_alloc(set, NULL, sizeof(set_node_t)); | ||
199 | node->size = 0; | ||
200 | node->fill = 0; | ||
201 | node->right = NULL; | ||
202 | return node; | ||
203 | } | ||
204 | |||
205 | // --private-- Free the list linked from head, along with the keys. | ||
206 | void set_sweep(set_t *set) { | ||
207 | set_node_t *step = set->head->right[0]; | ||
208 | while (step != set->head) { | ||
209 | set_node_t *next = step->right[0]; // save link to next node | ||
210 | set_drop(set, step->key); | ||
211 | set_free(set, step->right); | ||
212 | set_free(set, step); | ||
213 | step = next; | ||
214 | } | ||
215 | } | ||
216 | |||
217 | // Initialize a new set. set->env must be initialized using setjmp() before | ||
218 | // set_start() is called. A longjmp(set->env, ENOMEM) will be used to handle a | ||
219 | // memory allocation failure during any of the operations. (See setjmp.h and | ||
220 | // errno.h.) The set can still be used if this happens, assuming that it didn't | ||
221 | // happen during set_start(). Whether set_start() completed or not, set_end() | ||
222 | // can be used to free the set's memory after a longjmp(). | ||
223 | void set_start(set_t *set) { | ||
224 | #ifdef SET_TRACK | ||
225 | set->allocs = 0; | ||
226 | set->memory = 0; | ||
227 | #endif | ||
228 | set->head = set->path = set->node = NULL; // in case set_node() fails | ||
229 | set->path = set_node(set); | ||
230 | set->head = set_node(set); | ||
231 | set_grow(set, set->head, 1, 1); // one link back to head for an empty set | ||
232 | *(unsigned char *)&set->head->key = 137; // set id | ||
233 | set->depth = 0; | ||
234 | set_seed(&set->gen, (uint64_t)time(NULL) * (uint64_t)clock(), 0); | ||
235 | set->ran = 1; | ||
236 | } | ||
237 | |||
238 | // Return true if *set appears to be in a usable state. If *set has been zeroed | ||
239 | // out, then set_ok(set) will be false and set_end(set) will be safe. | ||
240 | int set_ok(set_t *set) { | ||
241 | return set->head != NULL && | ||
242 | set->head->right != NULL && | ||
243 | *(unsigned char *)&set->head->key == 137; | ||
244 | } | ||
245 | |||
246 | // Empty the set. This frees the memory used for the previous set contents. | ||
247 | // After set_clear(), *set is ready for use, as if after a set_start(). | ||
248 | void set_clear(set_t *set) { | ||
249 | assert(set_ok(set) && "improper use"); | ||
250 | |||
251 | // Free all the keys and their nodes. | ||
252 | set_sweep(set); | ||
253 | |||
254 | // Leave the head and path allocations as is. Clear their contents, with | ||
255 | // head pointing to itself and setting depth to zero, for an empty set. | ||
256 | set->head->right[0] = set->head; | ||
257 | set->head->fill = 1; | ||
258 | set->path->fill = 0; | ||
259 | set->depth = 0; | ||
260 | } | ||
261 | |||
262 | // Done using the set -- free all allocations. The only operation on *set | ||
263 | // permitted after this is set_start(). Though another set_end() would do no | ||
264 | // harm. This can be done at any time after a set_start(), or after a longjmp() | ||
265 | // on any allocation failure, including during a set_start(). | ||
266 | void set_end(set_t *set) { | ||
267 | if (set->head != NULL) { | ||
268 | // Empty the set and free the head node. | ||
269 | if (set->head->right != NULL) { | ||
270 | set_sweep(set); | ||
271 | set_free(set, set->head->right); | ||
272 | } | ||
273 | set_free(set, set->head); | ||
274 | set->head = NULL; | ||
275 | } | ||
276 | if (set->path != NULL) { | ||
277 | // Free the path work area. | ||
278 | set_free(set, set->path->right); | ||
279 | set_free(set, set->path); | ||
280 | set->path = NULL; | ||
281 | } | ||
282 | if (set->node != NULL) { | ||
283 | // Free the node that was under construction when longjmp() hit. | ||
284 | set_drop(set, set->node->key); | ||
285 | set_free(set, set->node->right); | ||
286 | set_free(set, set->node); | ||
287 | set->node = NULL; | ||
288 | } | ||
289 | } | ||
290 | |||
291 | // Look for key. Return 1 if found or 0 if not. This also puts the path to get | ||
292 | // there in set->path, for use by set_insert(). | ||
293 | int set_found(set_t *set, set_key_t key) { | ||
294 | assert(set_ok(set) && "improper use"); | ||
295 | |||
296 | // Start at depth and work down and right as determined by key comparisons. | ||
297 | set_node_t *head = set->head, *here = head; | ||
298 | int i = set->depth; | ||
299 | set_grow(set, set->path, i + 1, 0); | ||
300 | do { | ||
301 | while (here->right[i] != head && | ||
302 | set_cmp(here->right[i]->key, key) < 0) | ||
303 | here = here->right[i]; | ||
304 | set->path->right[i] = here; | ||
305 | } while (i--); | ||
306 | |||
307 | // See if the key matches. | ||
308 | here = here->right[0]; | ||
309 | return here != head && set_cmp(here->key, key) == 0; | ||
310 | } | ||
311 | |||
312 | // Insert the key key. Return 0 on success, or 1 if key is already in the set. | ||
313 | int set_insert(set_t *set, set_key_t key) { | ||
314 | assert(set_ok(set) && "improper use"); | ||
315 | |||
316 | if (set_found(set, key)) | ||
317 | // That key is already in the set. | ||
318 | return 1; | ||
319 | |||
320 | // Randomly generate a new level-- level 0 with probability 1/2, 1 with | ||
321 | // probability 1/4, 2 with probability 1/8, etc. | ||
322 | int level = 0; | ||
323 | for (;;) { | ||
324 | if (set->ran == 1) | ||
325 | // Ran out. Get another 32 random bits. | ||
326 | set->ran = set_rand(&set->gen) | (1ULL << 32); | ||
327 | int bit = set->ran & 1; | ||
328 | set->ran >>= 1; | ||
329 | if (bit) | ||
330 | break; | ||
331 | assert(level < 32767 && | ||
332 | "Overhead, without any fuss, the stars were going out."); | ||
333 | level++; | ||
334 | } | ||
335 | if (level > set->depth) { | ||
336 | // The maximum depth is now deeper. Update the structures. | ||
337 | set_grow(set, set->path, level + 1, 1); | ||
338 | set_grow(set, set->head, level + 1, 1); | ||
339 | set->depth = (int16_t)level; | ||
340 | } | ||
341 | |||
342 | // Make a new node for the provided key, and insert it in the lists up to | ||
343 | // and including level. | ||
344 | set->node = set_node(set); | ||
345 | set->node->key = key; | ||
346 | set_grow(set, set->node, level + 1, 0); | ||
347 | int i; | ||
348 | for (i = 0; i <= level; i++) { | ||
349 | set->node->right[i] = set->path->right[i]->right[i]; | ||
350 | set->path->right[i]->right[i] = set->node; | ||
351 | } | ||
352 | set->node = NULL; | ||
353 | return 0; | ||
354 | } | ||
355 | |||
356 | #else | ||
357 | #error ** another skiplist set already created here | ||
358 | // Would need to implement a prefix in order to support multiple sets. | ||
359 | #endif | ||
diff --git a/contrib/minizip/zip.c b/contrib/minizip/zip.c index a6329ae..d16e9ae 100644 --- a/contrib/minizip/zip.c +++ b/contrib/minizip/zip.c | |||
@@ -123,6 +123,19 @@ typedef struct linkedlist_data_s | |||
123 | } linkedlist_data; | 123 | } linkedlist_data; |
124 | 124 | ||
125 | 125 | ||
126 | // zipAlreadyThere() set functions for a set of zero-terminated strings, and | ||
127 | // a block_t type for reading the central directory datablocks. | ||
128 | typedef char const *set_key_t; | ||
129 | #define set_cmp(a, b) strcmp(a, b) | ||
130 | #define set_drop(s, k) set_free(s, (void *)(intptr_t)(k)) | ||
131 | #include "skipset.h" | ||
132 | typedef struct { | ||
133 | unsigned char *next; // next byte in datablock data | ||
134 | size_t left; // number of bytes left in data (at least) | ||
135 | linkedlist_datablock_internal *node; // current datablock | ||
136 | } block_t; | ||
137 | |||
138 | |||
126 | typedef struct | 139 | typedef struct |
127 | { | 140 | { |
128 | z_stream stream; /* zLib stream structure for inflate */ | 141 | z_stream stream; /* zLib stream structure for inflate */ |
@@ -174,6 +187,10 @@ typedef struct | |||
174 | char *globalcomment; | 187 | char *globalcomment; |
175 | #endif | 188 | #endif |
176 | 189 | ||
190 | // Support for zipAlreadyThere(). | ||
191 | set_t set; // set for detecting name collisions | ||
192 | block_t block; // block for reading the central directory | ||
193 | |||
177 | } zip64_internal; | 194 | } zip64_internal; |
178 | 195 | ||
179 | 196 | ||
@@ -264,6 +281,223 @@ local int add_data_in_datablock(linkedlist_data* ll, const void* buf, uLong len) | |||
264 | return ZIP_OK; | 281 | return ZIP_OK; |
265 | } | 282 | } |
266 | 283 | ||
284 | // zipAlreadyThere() operations. "set" in the zip internal structure keeps the | ||
285 | // set of names that are in the under-construction central directory so far. A | ||
286 | // skipset provides ~O(log n) time insertion and searching. Central directory | ||
287 | // records, stored in a linked list of allocated memory datablocks, is read | ||
288 | // through "block" in the zip internal structure. | ||
289 | |||
290 | // The block_*() functions support extracting the central directory file names | ||
291 | // from the datablocks. They are designed to support a growing directory by | ||
292 | // automatically continuing once more data has been appended to the linked | ||
293 | // datablocks. | ||
294 | |||
295 | // Initialize *block to the head of list. This should only be called once the | ||
296 | // list has at least some data in it, i.e. list->first_block is not NULL. | ||
297 | local void block_init(block_t *block, linkedlist_data *list) { | ||
298 | block->node = list->first_block; | ||
299 | block->next = block->node->data; | ||
300 | block->left = block->node->filled_in_this_block; | ||
301 | } | ||
302 | |||
303 | // Mark *block as bad, with all subsequent reads returning end, even if more | ||
304 | // data is added to the datablocks. This is invoked if the central directory is | ||
305 | // invalid, so there is no longer any point in attempting to interpret it. | ||
306 | local void block_stop(block_t *block) { | ||
307 | block->left = 0; | ||
308 | block->next = NULL; | ||
309 | } | ||
310 | |||
311 | // Return true if *block has reached the end of the data in the datablocks. | ||
312 | local int block_end(block_t *block) { | ||
313 | linkedlist_datablock_internal *node = block->node; | ||
314 | if (node == NULL) | ||
315 | // This block was previously terminated with extreme prejudice. | ||
316 | return 1; | ||
317 | if (block->next < node->data + node->filled_in_this_block) | ||
318 | // There are more bytes to read in the current datablock. | ||
319 | return 0; | ||
320 | while (node->next_datablock != NULL) { | ||
321 | if (node->filled_in_this_block != 0) | ||
322 | // There are some bytes in a later datablock. | ||
323 | return 0; | ||
324 | node = node->next_datablock; | ||
325 | } | ||
326 | // Reached the end of the list of datablocks. There's nothing. | ||
327 | return 1; | ||
328 | } | ||
329 | |||
330 | // Return one byte from *block, or -1 if the end is reached. | ||
331 | local int block_get(block_t *block) { | ||
332 | while (block->left == 0) { | ||
333 | if (block->node == NULL) | ||
334 | // We've been marked bad. Return end. | ||
335 | return -1; | ||
336 | // Update left in case more was filled in since we were last here. | ||
337 | block->left = block->node->filled_in_this_block - | ||
338 | (block->next - block->node->data); | ||
339 | if (block->left != 0) | ||
340 | // There was indeed more data appended in the current datablock. | ||
341 | break; | ||
342 | if (block->node->next_datablock == NULL) | ||
343 | // No more data here, and there is no next datablock. At the end. | ||
344 | return -1; | ||
345 | // Try the next datablock for more data. | ||
346 | block->node = block->node->next_datablock; | ||
347 | block->next = block->node->data; | ||
348 | block->left = block->node->filled_in_this_block; | ||
349 | } | ||
350 | // We have a byte to return. | ||
351 | block->left--; | ||
352 | return *block->next++; | ||
353 | } | ||
354 | |||
355 | // Return a 16-bit unsigned little-endian value from block, or a negative value | ||
356 | // if the end is reached. | ||
357 | local long block_get2(block_t *block) { | ||
358 | long got = block_get(block); | ||
359 | return got | ((long)block_get(block) << 8); | ||
360 | } | ||
361 | |||
362 | // Read up to len bytes from block into buf. Return the number of bytes read. | ||
363 | local size_t block_read(block_t *block, unsigned char *buf, size_t len) { | ||
364 | size_t need = len; | ||
365 | while (need) { | ||
366 | if (block->left == 0) { | ||
367 | // Get a byte to update and step through the linked list as needed. | ||
368 | int got = block_get(block); | ||
369 | if (got == -1) | ||
370 | // Reached the end. | ||
371 | break; | ||
372 | *buf++ = (unsigned char)got; | ||
373 | need--; | ||
374 | continue; | ||
375 | } | ||
376 | size_t take = need > block->left ? block->left : need; | ||
377 | memcpy(buf, block->next, take); | ||
378 | block->next += take; | ||
379 | block->left -= take; | ||
380 | buf += take; | ||
381 | need -= take; | ||
382 | } | ||
383 | return len - need; // return the number of bytes copied | ||
384 | } | ||
385 | |||
386 | // Skip n bytes in block. Return 0 on success or -1 if there are less than n | ||
387 | // bytes to the end. | ||
388 | local int block_skip(block_t *block, size_t n) { | ||
389 | while (n > block->left) { | ||
390 | n -= block->left; | ||
391 | block->next += block->left; | ||
392 | block->left = 0; | ||
393 | if (block_get(block) == -1) | ||
394 | return -1; | ||
395 | n--; | ||
396 | } | ||
397 | block->next += n; | ||
398 | block->left -= n; | ||
399 | return 0; | ||
400 | } | ||
401 | |||
402 | // Process the next central directory record at *block. Return the allocated, | ||
403 | // zero-terminated file name, or NULL for end of input or invalid data. If | ||
404 | // invalid, *block is marked bad. This uses *set for the allocation of memory. | ||
405 | local char *block_central_name(block_t *block, set_t *set) { | ||
406 | char *name = NULL; | ||
407 | for (;;) { | ||
408 | if (block_end(block)) | ||
409 | // At the end of the central directory (so far). | ||
410 | return NULL; | ||
411 | |||
412 | // Check for a central directory record signature. | ||
413 | if (block_get2(block) != (CENTRALHEADERMAGIC & 0xffff) || | ||
414 | block_get2(block) != (CENTRALHEADERMAGIC >> 16)) | ||
415 | // Incorrect signature. | ||
416 | break; | ||
417 | |||
418 | // Go through the remaining fixed-length portion of the record, | ||
419 | // extracting the lengths of the three variable-length fields. | ||
420 | block_skip(block, 24); | ||
421 | unsigned flen = block_get2(block); // file name length | ||
422 | unsigned xlen = block_get2(block); // extra field length | ||
423 | unsigned clen = block_get2(block); // comment field length | ||
424 | if (block_skip(block, 12) == -1) | ||
425 | // Premature end of the record. | ||
426 | break; | ||
427 | |||
428 | // Extract the name and skip over the extra and comment fields. | ||
429 | name = set_alloc(set, NULL, flen + 1); | ||
430 | if (block_read(block, (unsigned char *)name, flen) < flen || | ||
431 | block_skip(block, xlen + clen) == -1) | ||
432 | // Premature end of the record. | ||
433 | break; | ||
434 | |||
435 | // Check for embedded nuls in the name. | ||
436 | if (memchr(name, 0, flen) != NULL) { | ||
437 | // This name can never match the zero-terminated name provided to | ||
438 | // zipAlreadyThere(), so we discard it and go back to get another | ||
439 | // name. (Who the heck is putting nuls inside their zip file entry | ||
440 | // names anyway?) | ||
441 | set_free(set, name); | ||
442 | continue; | ||
443 | } | ||
444 | |||
445 | // All good. Return the zero-terminated file name. | ||
446 | name[flen] = 0; | ||
447 | return name; | ||
448 | } | ||
449 | |||
450 | // Invalid signature or premature end of the central directory record. | ||
451 | // Abandon trying to process the central directory. | ||
452 | set_free(set, name); | ||
453 | block_stop(block); | ||
454 | return NULL; | ||
455 | } | ||
456 | |||
457 | // Return 0 if name is not in the central directory so far, 1 if it is, -1 if | ||
458 | // the central directory is invalid, -2 if out of memory, or ZIP_PARAMERROR if | ||
459 | // file is NULL. | ||
460 | extern int ZEXPORT zipAlreadyThere(zipFile file, char const *name) { | ||
461 | zip64_internal *zip = file; | ||
462 | if (zip == NULL) | ||
463 | return ZIP_PARAMERROR; | ||
464 | if (zip->central_dir.first_block == NULL) | ||
465 | // No central directory yet, so no, name isn't there. | ||
466 | return 0; | ||
467 | if (setjmp(zip->set.env)) { | ||
468 | // Memory allocation failure. | ||
469 | set_end(&zip->set); | ||
470 | return -2; | ||
471 | } | ||
472 | if (!set_ok(&zip->set)) { | ||
473 | // This is the first time here with some central directory content. We | ||
474 | // construct this set of names only on demand. Prepare set and block. | ||
475 | set_start(&zip->set); | ||
476 | block_init(&zip->block, &zip->central_dir); | ||
477 | } | ||
478 | |||
479 | // Update the set of names from the current central directory contents. | ||
480 | // This reads any new central directory records since the last time we were | ||
481 | // here. | ||
482 | for (;;) { | ||
483 | char *there = block_central_name(&zip->block, &zip->set); | ||
484 | if (there == NULL) { | ||
485 | if (zip->block.next == NULL) | ||
486 | // The central directory is invalid. | ||
487 | return -1; | ||
488 | break; | ||
489 | } | ||
490 | |||
491 | // Add there to the set. | ||
492 | if (set_insert(&zip->set, there)) | ||
493 | // There's already a duplicate in the central directory! We'll just | ||
494 | // let this be and carry on. | ||
495 | set_free(&zip->set, there); | ||
496 | } | ||
497 | |||
498 | // Return true if name is in the central directory. | ||
499 | return set_found(&zip->set, name); | ||
500 | } | ||
267 | 501 | ||
268 | 502 | ||
269 | /****************************************************************************/ | 503 | /****************************************************************************/ |
@@ -551,7 +785,7 @@ local ZPOS64_T zip64local_SearchCentralDir64(const zlib_filefunc64_32_def* pzlib | |||
551 | 785 | ||
552 | for (i=(int)uReadSize-3; (i--)>0;) | 786 | for (i=(int)uReadSize-3; (i--)>0;) |
553 | { | 787 | { |
554 | // Signature "0x07064b50" Zip64 end of central directory locater | 788 | // Signature "0x07064b50" Zip64 end of central directory locator |
555 | if (((*(buf+i))==0x50) && ((*(buf+i+1))==0x4b) && ((*(buf+i+2))==0x06) && ((*(buf+i+3))==0x07)) | 789 | if (((*(buf+i))==0x50) && ((*(buf+i+1))==0x4b) && ((*(buf+i+2))==0x06) && ((*(buf+i+3))==0x07)) |
556 | { | 790 | { |
557 | uPosFound = uReadPos+(unsigned)i; | 791 | uPosFound = uReadPos+(unsigned)i; |
@@ -843,6 +1077,7 @@ extern zipFile ZEXPORT zipOpen3(const void *pathname, int append, zipcharpc* glo | |||
843 | ziinit.number_entry = 0; | 1077 | ziinit.number_entry = 0; |
844 | ziinit.add_position_when_writing_offset = 0; | 1078 | ziinit.add_position_when_writing_offset = 0; |
845 | init_linkedlist(&(ziinit.central_dir)); | 1079 | init_linkedlist(&(ziinit.central_dir)); |
1080 | memset(&ziinit.set, 0, sizeof(set_t)); // make sure set appears dormant | ||
846 | 1081 | ||
847 | 1082 | ||
848 | 1083 | ||
@@ -1870,6 +2105,8 @@ extern int ZEXPORT zipClose(zipFile file, const char* global_comment) { | |||
1870 | } | 2105 | } |
1871 | free_linkedlist(&(zi->central_dir)); | 2106 | free_linkedlist(&(zi->central_dir)); |
1872 | 2107 | ||
2108 | set_end(&zi->set); // set was zeroed, so this is safe | ||
2109 | |||
1873 | pos = centraldir_pos_inzip - zi->add_position_when_writing_offset; | 2110 | pos = centraldir_pos_inzip - zi->add_position_when_writing_offset; |
1874 | if(pos >= 0xffffffff || zi->number_entry >= 0xFFFF) | 2111 | if(pos >= 0xffffffff || zi->number_entry >= 0xFFFF) |
1875 | { | 2112 | { |
diff --git a/contrib/minizip/zip.h b/contrib/minizip/zip.h index 3e230d3..1f7f0b2 100644 --- a/contrib/minizip/zip.h +++ b/contrib/minizip/zip.h | |||
@@ -35,7 +35,7 @@ | |||
35 | 35 | ||
36 | See header of zip.h | 36 | See header of zip.h |
37 | 37 | ||
38 | */ | 38 | */ |
39 | 39 | ||
40 | #ifndef _zip12_H | 40 | #ifndef _zip12_H |
41 | #define _zip12_H | 41 | #define _zip12_H |
@@ -127,12 +127,12 @@ extern zipFile ZEXPORT zipOpen64(const void *pathname, int append); | |||
127 | If the zipfile cannot be opened, the return value is NULL. | 127 | If the zipfile cannot be opened, the return value is NULL. |
128 | Else, the return value is a zipFile Handle, usable with other function | 128 | Else, the return value is a zipFile Handle, usable with other function |
129 | of this zip package. | 129 | of this zip package. |
130 | */ | 130 | */ |
131 | 131 | ||
132 | /* Note : there is no delete function into a zipfile. | 132 | /* Note : there is no delete function into a zipfile. |
133 | If you want delete file into a zipfile, you must open a zipfile, and create another | 133 | If you want delete file into a zipfile, you must open a zipfile, and create another |
134 | Of course, you can use RAW reading and writing to copy the file you did not want delete | 134 | Of course, you can use RAW reading and writing to copy the file you did not want delete |
135 | */ | 135 | */ |
136 | 136 | ||
137 | extern zipFile ZEXPORT zipOpen2(const char *pathname, | 137 | extern zipFile ZEXPORT zipOpen2(const char *pathname, |
138 | int append, | 138 | int append, |
@@ -186,7 +186,7 @@ extern int ZEXPORT zipOpenNewFileInZip64(zipFile file, | |||
186 | zip64 is set to 1 if a zip64 extended information block should be added to the local file header. | 186 | zip64 is set to 1 if a zip64 extended information block should be added to the local file header. |
187 | this MUST be '1' if the uncompressed size is >= 0xffffffff. | 187 | this MUST be '1' if the uncompressed size is >= 0xffffffff. |
188 | 188 | ||
189 | */ | 189 | */ |
190 | 190 | ||
191 | 191 | ||
192 | extern int ZEXPORT zipOpenNewFileInZip2(zipFile file, | 192 | extern int ZEXPORT zipOpenNewFileInZip2(zipFile file, |
@@ -311,12 +311,12 @@ extern int ZEXPORT zipWriteInFileInZip(zipFile file, | |||
311 | unsigned len); | 311 | unsigned len); |
312 | /* | 312 | /* |
313 | Write data in the zipfile | 313 | Write data in the zipfile |
314 | */ | 314 | */ |
315 | 315 | ||
316 | extern int ZEXPORT zipCloseFileInZip(zipFile file); | 316 | extern int ZEXPORT zipCloseFileInZip(zipFile file); |
317 | /* | 317 | /* |
318 | Close the current file in the zipfile | 318 | Close the current file in the zipfile |
319 | */ | 319 | */ |
320 | 320 | ||
321 | extern int ZEXPORT zipCloseFileInZipRaw(zipFile file, | 321 | extern int ZEXPORT zipCloseFileInZipRaw(zipFile file, |
322 | uLong uncompressed_size, | 322 | uLong uncompressed_size, |
@@ -326,17 +326,23 @@ extern int ZEXPORT zipCloseFileInZipRaw64(zipFile file, | |||
326 | ZPOS64_T uncompressed_size, | 326 | ZPOS64_T uncompressed_size, |
327 | uLong crc32); | 327 | uLong crc32); |
328 | 328 | ||
329 | extern int ZEXPORT zipAlreadyThere(zipFile file, | ||
330 | char const* name); | ||
331 | /* | ||
332 | See if name is already in file's central directory. | ||
333 | */ | ||
334 | |||
329 | /* | 335 | /* |
330 | Close the current file in the zipfile, for file opened with | 336 | Close the current file in the zipfile, for file opened with |
331 | parameter raw=1 in zipOpenNewFileInZip2 | 337 | parameter raw=1 in zipOpenNewFileInZip2 |
332 | uncompressed_size and crc32 are value for the uncompressed size | 338 | uncompressed_size and crc32 are value for the uncompressed size |
333 | */ | 339 | */ |
334 | 340 | ||
335 | extern int ZEXPORT zipClose(zipFile file, | 341 | extern int ZEXPORT zipClose(zipFile file, |
336 | const char* global_comment); | 342 | const char* global_comment); |
337 | /* | 343 | /* |
338 | Close the zipfile | 344 | Close the zipfile |
339 | */ | 345 | */ |
340 | 346 | ||
341 | 347 | ||
342 | extern int ZEXPORT zipRemoveExtraInfoBlock(char* pData, int* dataLen, short sHeader); | 348 | extern int ZEXPORT zipRemoveExtraInfoBlock(char* pData, int* dataLen, short sHeader); |
@@ -355,7 +361,7 @@ extern int ZEXPORT zipRemoveExtraInfoBlock(char* pData, int* dataLen, short sHea | |||
355 | 361 | ||
356 | Remove ZIP64 Extra information from a Local File Header extra field data | 362 | Remove ZIP64 Extra information from a Local File Header extra field data |
357 | zipRemoveExtraInfoBlock(pLocalHeaderExtraFieldData, &nLocalHeaderExtraFieldDataLen, 0x0001); | 363 | zipRemoveExtraInfoBlock(pLocalHeaderExtraFieldData, &nLocalHeaderExtraFieldDataLen, 0x0001); |
358 | */ | 364 | */ |
359 | 365 | ||
360 | #ifdef __cplusplus | 366 | #ifdef __cplusplus |
361 | } | 367 | } |