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 | |
| 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.
| -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 | } |
