Changeset 95239 in vbox for trunk/src/libs/zlib-1.2.12/examples
- Timestamp:
- Jun 9, 2022 9:09:44 AM (3 years ago)
- svn:sync-xref-src-repo-rev:
- 151769
- Location:
- trunk/src/libs/zlib-1.2.12
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/src/libs/zlib-1.2.12
- Property svn:mergeinfo
-
old new 20 20 /branches/dsen/gui3/src/libs/zlib-1.2.11:79645-79692 21 21 /trunk/src/src/libs/zlib-1.2.11:92342 22 /vendor/zlib/1.2.12:151751 23 /vendor/zlib/current:150724-151750
-
- Property svn:mergeinfo
-
trunk/src/libs/zlib-1.2.12/examples/README.examples
r76163 r95239 35 35 - illustrates use of a gzip header extra field 36 36 37 gznorm.c 38 normalize a gzip file by combining members into a single member 39 - demonstrates how to concatenate deflate streams using Z_BLOCK 40 37 41 zlib_how.html 38 42 painfully comprehensive description of zpipe.c (see below) … … 45 49 46 50 zran.c 51 zran.h 47 52 index a zlib or gzip stream and randomly access it 48 53 - illustrates the use of Z_BLOCK, inflatePrime(), and -
trunk/src/libs/zlib-1.2.12/examples/enough.c
r76163 r95239 1 1 /* enough.c -- determine the maximum size of inflate's Huffman code tables over 2 * all possible valid and complete Huffmancodes, subject to a length limit.3 * Copyright (C) 2007, 2008, 2012 Mark Adler4 * Version 1. 4 18 August 2012Mark Adler2 * all possible valid and complete prefix codes, subject to a length limit. 3 * Copyright (C) 2007, 2008, 2012, 2018 Mark Adler 4 * Version 1.5 5 August 2018 Mark Adler 5 5 */ 6 6 … … 18 18 Clean up comparisons of different types 19 19 Clean up code indentation 20 1.5 5 Aug 2018 Clean up code style, formatting, and comments 21 Show all the codes for the maximum, and only the maximum 20 22 */ 21 23 22 24 /* 23 Examine all possible Huffmancodes for a given number of symbols and a24 maximum code length in bits to determine the maximum table size for z ilb's25 inflate. Only complete Huffmancodes are counted.25 Examine all possible prefix codes for a given number of symbols and a 26 maximum code length in bits to determine the maximum table size for zlib's 27 inflate. Only complete prefix codes are counted. 26 28 27 29 Two codes are considered distinct if the vectors of the number of codes per 28 length are not identical. 30 length are not identical. So permutations of the symbol assignments result 29 31 in the same code for the counting, as do permutations of the assignments of 30 32 the bit values to the codes (i.e. only canonical codes are counted). 31 33 32 34 We build a code from shorter to longer lengths, determining how many symbols 33 are coded at each length. 35 are coded at each length. At each step, we have how many symbols remain to 34 36 be coded, what the last code length used was, and how many bit patterns of 35 37 that length remain unused. Then we add one to the code length and double the 36 number of unused patterns to graduate to the next code length. 38 number of unused patterns to graduate to the next code length. We then 37 39 assign all portions of the remaining symbols to that code length that 38 preserve the properties of a correct and eventually complete code. 40 preserve the properties of a correct and eventually complete code. Those 39 41 properties are: we cannot use more bit patterns than are available; and when 40 all the symbols are used, there are exactly zero possible bit patterns 41 remaining.42 all the symbols are used, there are exactly zero possible bit patterns left 43 unused. 42 44 43 45 The inflate Huffman decoding algorithm uses two-level lookup tables for 44 speed. There is a single first-level table to decode codes up to root bits 45 in length (root == 9 in the current inflate implementation). The table 46 has 1 << root entries and is indexed by the next root bits of input. Codes 47 shorter than root bits have replicated table entries, so that the correct 48 entry is pointed to regardless of the bits that follow the short code. If 49 the code is longer than root bits, then the table entry points to a second- 50 level table. The size of that table is determined by the longest code with 51 that root-bit prefix. If that longest code has length len, then the table 52 has size 1 << (len - root), to index the remaining bits in that set of 53 codes. Each subsequent root-bit prefix then has its own sub-table. The 54 total number of table entries required by the code is calculated 55 incrementally as the number of codes at each bit length is populated. When 56 all of the codes are shorter than root bits, then root is reduced to the 57 longest code length, resulting in a single, smaller, one-level table. 46 speed. There is a single first-level table to decode codes up to root bits 47 in length (root == 9 for literal/length codes and root == 6 for distance 48 codes, in the current inflate implementation). The base table has 1 << root 49 entries and is indexed by the next root bits of input. Codes shorter than 50 root bits have replicated table entries, so that the correct entry is 51 pointed to regardless of the bits that follow the short code. If the code is 52 longer than root bits, then the table entry points to a second-level table. 53 The size of that table is determined by the longest code with that root-bit 54 prefix. If that longest code has length len, then the table has size 1 << 55 (len - root), to index the remaining bits in that set of codes. Each 56 subsequent root-bit prefix then has its own sub-table. The total number of 57 table entries required by the code is calculated incrementally as the number 58 of codes at each bit length is populated. When all of the codes are shorter 59 than root bits, then root is reduced to the longest code length, resulting 60 in a single, smaller, one-level table. 58 61 59 62 The inflate algorithm also provides for small values of root (relative to 60 63 the log2 of the number of symbols), where the shortest code has more bits 61 than root. 62 code. 63 that the number of symbols is less than 2^(root + 1).64 than root. In that case, root is increased to the length of the shortest 65 code. This program, by design, does not handle that case, so it is verified 66 that the number of symbols is less than 1 << (root + 1). 64 67 65 68 In order to speed up the examination (by about ten orders of magnitude for 66 69 the default arguments), the intermediate states in the build-up of a code 67 are remembered and previously visited branches are pruned. 70 are remembered and previously visited branches are pruned. The memory 68 71 required for this will increase rapidly with the total number of symbols and 69 the maximum code length in bits. 72 the maximum code length in bits. However this is a very small price to pay 70 73 for the vast speedup. 71 74 72 First, all of the possible Huffmancodes are counted, and reachable75 First, all of the possible prefix codes are counted, and reachable 73 76 intermediate states are noted by a non-zero count in a saved-results array. 74 77 Second, the intermediate states that lead to (root + 1) bit or longer codes 75 78 are used to look at all sub-codes from those junctures for their inflate 76 memory usage. 79 memory usage. (The amount of memory used is not affected by the number of 77 80 codes of root bits or less in length.) Third, the visited states in the 78 81 construction of those sub-codes and the associated calculation of the table … … 80 83 Beginning the code examination at (root + 1) bit codes, which is enabled by 81 84 identifying the reachable nodes, accounts for about six of the orders of 82 magnitude of improvement for the default arguments. 83 orders of magnitude come from not revisiting previous states. 84 approximately 2x10^16 possible Huffmancodes, only about 2x10^6 sub-codes85 magnitude of improvement for the default arguments. About another four 86 orders of magnitude come from not revisiting previous states. Out of 87 approximately 2x10^16 possible prefix codes, only about 2x10^6 sub-codes 85 88 need to be examined to cover all of the possible table memory usage cases 86 89 for the default arguments of 286 symbols limited to 15-bit codes. 87 90 88 Note that an unsigned long long type is used for counting. It is quite easy89 to exceed the capacity of an eight-byte integer with a large number of90 symbols and a large maximum code length, so multiple-precision arithmetic91 would need to replace the unsigned long long arithmetic in that case. This92 program will abort if an overflow occurs. The big_t type identifies where93 the counting takesplace.94 95 An unsigned long long type is also used for calculating the number of96 possible codes remaining at the maximum length. This limits the maximum97 code length to the number of bits in a long long minus the number of bits98 needed to represent the symbols in a flat code. The code_t type identifies99 where the bit patterncounting takes place.91 Note that the uintmax_t type is used for counting. It is quite easy to 92 exceed the capacity of an eight-byte integer with a large number of symbols 93 and a large maximum code length, so multiple-precision arithmetic would need 94 to replace the integer arithmetic in that case. This program will abort if 95 an overflow occurs. The big_t type identifies where the counting takes 96 place. 97 98 The uintmax_t type is also used for calculating the number of possible codes 99 remaining at the maximum length. This limits the maximum code length to the 100 number of bits in a long long minus the number of bits needed to represent 101 the symbols in a flat code. The code_t type identifies where the bit-pattern 102 counting takes place. 100 103 */ 101 104 … … 103 106 #include <stdlib.h> 104 107 #include <string.h> 108 #include <stdarg.h> 109 #include <stdint.h> 105 110 #include <assert.h> 106 111 107 112 #define local static 108 113 109 /* special data types */ 110 typedef unsigned long long big_t; /* type for code counting */ 111 typedef unsigned long long code_t; /* type for bit pattern counting */ 112 struct tab { /* type for been here check */ 113 size_t len; /* length of bit vector in char's */ 114 char *vec; /* allocated bit vector */ 114 // Special data types. 115 typedef uintmax_t big_t; // type for code counting 116 #define PRIbig "ju" // printf format for big_t 117 typedef uintmax_t code_t; // type for bit pattern counting 118 struct tab { // type for been-here check 119 size_t len; // allocated length of bit vector in octets 120 char *vec; // allocated bit vector 115 121 }; 116 122 … … 127 133 len: 1..max - 1 (max == maximum code length in bits) 128 134 129 syms == 2 is not saved since that immediately leads to a single code. 135 syms == 2 is not saved since that immediately leads to a single code. left 130 136 must be even, since it represents the number of available bit patterns at 131 the current length, which is double the number at the previous length. 132 leftends at syms-1 since left == syms immediately results in a single code.137 the current length, which is double the number at the previous length. left 138 ends at syms-1 since left == syms immediately results in a single code. 133 139 (left > sym is not allowed since that would result in an incomplete code.) 134 140 len is less than max, since the code completes immediately when len == max. 135 141 136 The offset into the array is calculated for the three indices with the 137 first one (syms) being outermost, and the last one (len) being innermost. 138 We build the array with length max-1 lists for the len index, with syms-3 139 of those for each symbol. There are totsym-2 of those, with each one 140 varying in length as a function of sym. See the calculation of index in 141 count() for the index, and the calculation of size in main() for the size 142 of the array. 142 The offset into the array is calculated for the three indices with the first 143 one (syms) being outermost, and the last one (len) being innermost. We build 144 the array with length max-1 lists for the len index, with syms-3 of those 145 for each symbol. There are totsym-2 of those, with each one varying in 146 length as a function of sym. See the calculation of index in map() for the 147 index, and the calculation of size in main() for the size of the array. 143 148 144 149 For the deflate example of 286 symbols limited to 15-bit codes, the array 145 has 284,284 entries, taking up 2.17 MB for an 8-byte big_t. More than146 halfof the space allocated for saved results is actually used -- not all147 possible triplets are reached in the generation of valid Huffmancodes.150 has 284,284 entries, taking up 2.17 MB for an 8-byte big_t. More than half 151 of the space allocated for saved results is actually used -- not all 152 possible triplets are reached in the generation of valid prefix codes. 148 153 */ 149 154 … … 152 157 Each element in the array is further indexed by the (mem, rem) doublet, 153 158 where mem is the amount of inflate table space used so far, and rem is the 154 remaining unused entries in the current inflate sub-table. 159 remaining unused entries in the current inflate sub-table. Each indexed 155 160 element is simply one bit indicating whether the state has been visited or 156 not. 161 not. Since the ranges for mem and rem are not known a priori, each bit 157 162 vector is of a variable size, and grows as needed to accommodate the visited 158 states. 159 array. 163 states. mem and rem are used to calculate a single index in a triangular 164 array. Since the range of mem is expected in the default case to be about 160 165 ten times larger than the range of rem, the array is skewed to reduce the 161 memory usage, with eight times the range for mem than for rem. 162 calculations for offset and bit in been here() for the details.166 memory usage, with eight times the range for mem than for rem. See the 167 calculations for offset and bit in been_here() for the details. 163 168 164 169 For the deflate example of 286 symbols limited to 15-bit codes, the bit 165 vectors grow to total approximately 21 MB, in addition to the 4.3 MB done[] 166 array itself. 170 vectors grow to total 5.5 MB, in addition to the 4.3 MB done array itself. 167 171 */ 168 172 169 /* Globals to avoid propagating constants or constant pointers recursively */ 170 local int max; /* maximum allowed bit length for the codes */ 171 local int root; /* size of base code table in bits */ 172 local int large; /* largest code table so far */ 173 local size_t size; /* number of elements in num and done */ 174 local int *code; /* number of symbols assigned to each bit length */ 175 local big_t *num; /* saved results array for code counting */ 176 local struct tab *done; /* states already evaluated array */ 177 178 /* Index function for num[] and done[] */ 179 #define INDEX(i,j,k) (((size_t)((i-1)>>1)*((i-2)>>1)+(j>>1)-1)*(max-1)+k-1) 180 181 /* Free allocated space. Uses globals code, num, and done. */ 182 local void cleanup(void) 183 { 184 size_t n; 185 186 if (done != NULL) { 187 for (n = 0; n < size; n++) 188 if (done[n].len) 189 free(done[n].vec); 190 free(done); 191 } 192 if (num != NULL) 193 free(num); 194 if (code != NULL) 195 free(code); 196 } 197 198 /* Return the number of possible Huffman codes using bit patterns of lengths 199 len through max inclusive, coding syms symbols, with left bit patterns of 200 length len unused -- return -1 if there is an overflow in the counting. 201 Keep a record of previous results in num to prevent repeating the same 202 calculation. Uses the globals max and num. */ 203 local big_t count(int syms, int len, int left) 204 { 205 big_t sum; /* number of possible codes from this juncture */ 206 big_t got; /* value returned from count() */ 207 int least; /* least number of syms to use at this juncture */ 208 int most; /* most number of syms to use at this juncture */ 209 int use; /* number of bit patterns to use in next call */ 210 size_t index; /* index of this case in *num */ 211 212 /* see if only one possible code */ 173 // Type for a variable-length, allocated string. 174 typedef struct { 175 char *str; // pointer to allocated string 176 size_t size; // size of allocation 177 size_t len; // length of string, not including terminating zero 178 } string_t; 179 180 // Clear a string_t. 181 local void string_clear(string_t *s) { 182 s->str[0] = 0; 183 s->len = 0; 184 } 185 186 // Initialize a string_t. 187 local void string_init(string_t *s) { 188 s->size = 16; 189 s->str = malloc(s->size); 190 assert(s->str != NULL && "out of memory"); 191 string_clear(s); 192 } 193 194 // Release the allocation of a string_t. 195 local void string_free(string_t *s) { 196 free(s->str); 197 s->str = NULL; 198 s->size = 0; 199 s->len = 0; 200 } 201 202 // Save the results of printf with fmt and the subsequent argument list to s. 203 // Each call appends to s. The allocated space for s is increased as needed. 204 local void string_printf(string_t *s, char *fmt, ...) { 205 va_list ap; 206 va_start(ap, fmt); 207 size_t len = s->len; 208 int ret = vsnprintf(s->str + len, s->size - len, fmt, ap); 209 assert(ret >= 0 && "out of memory"); 210 s->len += ret; 211 if (s->size < s->len + 1) { 212 do { 213 s->size <<= 1; 214 assert(s->size != 0 && "overflow"); 215 } while (s->size < s->len + 1); 216 s->str = realloc(s->str, s->size); 217 assert(s->str != NULL && "out of memory"); 218 vsnprintf(s->str + len, s->size - len, fmt, ap); 219 } 220 va_end(ap); 221 } 222 223 // Globals to avoid propagating constants or constant pointers recursively. 224 struct { 225 int max; // maximum allowed bit length for the codes 226 int root; // size of base code table in bits 227 int large; // largest code table so far 228 size_t size; // number of elements in num and done 229 big_t tot; // total number of codes with maximum tables size 230 string_t out; // display of subcodes for maximum tables size 231 int *code; // number of symbols assigned to each bit length 232 big_t *num; // saved results array for code counting 233 struct tab *done; // states already evaluated array 234 } g; 235 236 // Index function for num[] and done[]. 237 local inline size_t map(int syms, int left, int len) { 238 return ((size_t)((syms - 1) >> 1) * ((syms - 2) >> 1) + 239 (left >> 1) - 1) * (g.max - 1) + 240 len - 1; 241 } 242 243 // Free allocated space in globals. 244 local void cleanup(void) { 245 if (g.done != NULL) { 246 for (size_t n = 0; n < g.size; n++) 247 if (g.done[n].len) 248 free(g.done[n].vec); 249 g.size = 0; 250 free(g.done); g.done = NULL; 251 } 252 free(g.num); g.num = NULL; 253 free(g.code); g.code = NULL; 254 string_free(&g.out); 255 } 256 257 // Return the number of possible prefix codes using bit patterns of lengths len 258 // through max inclusive, coding syms symbols, with left bit patterns of length 259 // len unused -- return -1 if there is an overflow in the counting. Keep a 260 // record of previous results in num to prevent repeating the same calculation. 261 local big_t count(int syms, int left, int len) { 262 // see if only one possible code 213 263 if (syms == left) 214 264 return 1; 215 265 216 / * note and verify the expected state */217 assert(syms > left && left > 0 && len < max);218 219 / * see if we've done this one already */220 index = INDEX(syms, left, len);221 got =num[index];266 // note and verify the expected state 267 assert(syms > left && left > 0 && len < g.max); 268 269 // see if we've done this one already 270 size_t index = map(syms, left, len); 271 big_t got = g.num[index]; 222 272 if (got) 223 return got; / * we have -- return the saved result */224 225 / *we need to use at least this many bit patterns so that the code won't be226 incomplete at the next length (more bit patterns than symbols) */227 least = (left << 1) - syms;273 return got; // we have -- return the saved result 274 275 // we need to use at least this many bit patterns so that the code won't be 276 // incomplete at the next length (more bit patterns than symbols) 277 int least = (left << 1) - syms; 228 278 if (least < 0) 229 279 least = 0; 230 280 231 / *we can use at most this many bit patterns, lest there not be enough232 233 no limit to the code length, this would become: most = left - 1) */234 most = (((code_t)left << (max - len)) - syms) /235 (((code_t)1 << (max - len)) - 1);236 237 / * count all possible codes from this juncture and add them up */238 sum = 0;239 for ( use = least; use <= most; use++) {240 got = count(syms - use, len + 1, (left - use) <<1);281 // we can use at most this many bit patterns, lest there not be enough 282 // available for the remaining symbols at the maximum length (if there were 283 // no limit to the code length, this would become: most = left - 1) 284 int most = (((code_t)left << (g.max - len)) - syms) / 285 (((code_t)1 << (g.max - len)) - 1); 286 287 // count all possible codes from this juncture and add them up 288 big_t sum = 0; 289 for (int use = least; use <= most; use++) { 290 got = count(syms - use, (left - use) << 1, len + 1); 241 291 sum += got; 242 if (got == (big_t) 0 - 1 || sum < got) /* overflow */243 return (big_t) 0 -1;244 } 245 246 / * verify that all recursive calls are productive */292 if (got == (big_t)-1 || sum < got) // overflow 293 return (big_t)-1; 294 } 295 296 // verify that all recursive calls are productive 247 297 assert(sum != 0); 248 298 249 / * save the result and return it */250 num[index] = sum;299 // save the result and return it 300 g.num[index] = sum; 251 301 return sum; 252 302 } 253 303 254 /* Return true if we've been here before, set to true if not. Set a bit in a 255 bit vector to indicate visiting this state. Each (syms,len,left) state 256 has a variable size bit vector indexed by (mem,rem). The bit vector is 257 lengthened if needed to allow setting the (mem,rem) bit. */ 258 local int beenhere(int syms, int len, int left, int mem, int rem) 259 { 260 size_t index; /* index for this state's bit vector */ 261 size_t offset; /* offset in this state's bit vector */ 262 int bit; /* mask for this state's bit */ 263 size_t length; /* length of the bit vector in bytes */ 264 char *vector; /* new or enlarged bit vector */ 265 266 /* point to vector for (syms,left,len), bit in vector for (mem,rem) */ 267 index = INDEX(syms, left, len); 268 mem -= 1 << root; 269 offset = (mem >> 3) + rem; 304 // Return true if we've been here before, set to true if not. Set a bit in a 305 // bit vector to indicate visiting this state. Each (syms,len,left) state has a 306 // variable size bit vector indexed by (mem,rem). The bit vector is lengthened 307 // as needed to allow setting the (mem,rem) bit. 308 local int been_here(int syms, int left, int len, int mem, int rem) { 309 // point to vector for (syms,left,len), bit in vector for (mem,rem) 310 size_t index = map(syms, left, len); 311 mem -= 1 << g.root; // mem always includes the root table 312 mem >>= 1; // mem and rem are always even 313 rem >>= 1; 314 size_t offset = (mem >> 3) + rem; 270 315 offset = ((offset * (offset + 1)) >> 1) + rem; 271 bit = 1 << (mem & 7);272 273 / * see if we've been here */274 length =done[index].len;275 if (offset < length && ( done[index].vec[offset] & bit) != 0)276 return 1; / * done this! */277 278 / * we haven't been here before -- set the bit to show we have now */279 280 / * see if we need to lengthen the vector in order to set the bit */316 int bit = 1 << (mem & 7); 317 318 // see if we've been here 319 size_t length = g.done[index].len; 320 if (offset < length && (g.done[index].vec[offset] & bit) != 0) 321 return 1; // done this! 322 323 // we haven't been here before -- set the bit to show we have now 324 325 // see if we need to lengthen the vector in order to set the bit 281 326 if (length <= offset) { 282 /* if we have one already, enlarge it, zero out the appended space */ 327 // if we have one already, enlarge it, zero out the appended space 328 char *vector; 283 329 if (length) { 284 330 do { 285 331 length <<= 1; 286 332 } while (length <= offset); 287 vector = realloc( done[index].vec, length);288 if (vector != NULL)289 memset(vector + done[index].len, 0, length -done[index].len);333 vector = realloc(g.done[index].vec, length); 334 assert(vector != NULL && "out of memory"); 335 memset(vector + g.done[index].len, 0, length - g.done[index].len); 290 336 } 291 337 292 / * otherwise we need to make a new vector and zero it out */338 // otherwise we need to make a new vector and zero it out 293 339 else { 294 length = 1 << (len - root);340 length = 16; 295 341 while (length <= offset) 296 342 length <<= 1; 297 vector = calloc(length, sizeof(char)); 343 vector = calloc(length, 1); 344 assert(vector != NULL && "out of memory"); 298 345 } 299 346 300 /* in either case, bail if we can't get the memory */ 301 if (vector == NULL) { 302 fputs("abort: unable to allocate enough memory\n", stderr); 303 cleanup(); 304 exit(1); 305 } 306 307 /* install the new vector */ 308 done[index].len = length; 309 done[index].vec = vector; 310 } 311 312 /* set the bit */ 313 done[index].vec[offset] |= bit; 347 // install the new vector 348 g.done[index].len = length; 349 g.done[index].vec = vector; 350 } 351 352 // set the bit 353 g.done[index].vec[offset] |= bit; 314 354 return 0; 315 355 } 316 356 317 /* Examine all possible codes from the given node (syms, len, left). Compute 318 the amount of memory required to build inflate's decoding tables, where the 319 number of code structures used so far is mem, and the number remaining in 320 the current sub-table is rem. Uses the globals max, code, root, large, and 321 done. */ 322 local void examine(int syms, int len, int left, int mem, int rem) 323 { 324 int least; /* least number of syms to use at this juncture */ 325 int most; /* most number of syms to use at this juncture */ 326 int use; /* number of bit patterns to use in next call */ 327 328 /* see if we have a complete code */ 357 // Examine all possible codes from the given node (syms, len, left). Compute 358 // the amount of memory required to build inflate's decoding tables, where the 359 // number of code structures used so far is mem, and the number remaining in 360 // the current sub-table is rem. 361 local void examine(int syms, int left, int len, int mem, int rem) { 362 // see if we have a complete code 329 363 if (syms == left) { 330 / * set the last code entry */331 code[len] = left;332 333 / * complete computation of memory used by this code */364 // set the last code entry 365 g.code[len] = left; 366 367 // complete computation of memory used by this code 334 368 while (rem < left) { 335 369 left -= rem; 336 rem = 1 << (len - root);370 rem = 1 << (len - g.root); 337 371 mem += rem; 338 372 } 339 373 assert(rem == left); 340 374 341 /* if this is a new maximum, show the entries used and the sub-code */ 342 if (mem > large) { 343 large = mem; 344 printf("max %d: ", mem); 345 for (use = root + 1; use <= max; use++) 346 if (code[use]) 347 printf("%d[%d] ", code[use], use); 348 putchar('\n'); 349 fflush(stdout); 375 // if this is at the maximum, show the sub-code 376 if (mem >= g.large) { 377 // if this is a new maximum, update the maximum and clear out the 378 // printed sub-codes from the previous maximum 379 if (mem > g.large) { 380 g.large = mem; 381 string_clear(&g.out); 382 } 383 384 // compute the starting state for this sub-code 385 syms = 0; 386 left = 1 << g.max; 387 for (int bits = g.max; bits > g.root; bits--) { 388 syms += g.code[bits]; 389 left -= g.code[bits]; 390 assert((left & 1) == 0); 391 left >>= 1; 392 } 393 394 // print the starting state and the resulting sub-code to g.out 395 string_printf(&g.out, "<%u, %u, %u>:", 396 syms, g.root + 1, ((1 << g.root) - left) << 1); 397 for (int bits = g.root + 1; bits <= g.max; bits++) 398 if (g.code[bits]) 399 string_printf(&g.out, " %d[%d]", g.code[bits], bits); 400 string_printf(&g.out, "\n"); 350 401 } 351 402 352 / * remove entries as we drop back down in the recursion */353 code[len] = 0;403 // remove entries as we drop back down in the recursion 404 g.code[len] = 0; 354 405 return; 355 406 } 356 407 357 / * prune the tree if we can */358 if (been here(syms, len, left, mem, rem))408 // prune the tree if we can 409 if (been_here(syms, left, len, mem, rem)) 359 410 return; 360 411 361 / *we need to use at least this many bit patterns so that the code won't be362 incomplete at the next length (more bit patterns than symbols) */363 least = (left << 1) - syms;412 // we need to use at least this many bit patterns so that the code won't be 413 // incomplete at the next length (more bit patterns than symbols) 414 int least = (left << 1) - syms; 364 415 if (least < 0) 365 416 least = 0; 366 417 367 / *we can use at most this many bit patterns, lest there not be enough368 369 no limit to the code length, this would become: most = left - 1) */370 most = (((code_t)left << (max - len)) - syms) /371 (((code_t)1 << (max - len)) - 1);372 373 / * occupy least table spaces, creating new sub-tables as needed */374 use = least;418 // we can use at most this many bit patterns, lest there not be enough 419 // available for the remaining symbols at the maximum length (if there were 420 // no limit to the code length, this would become: most = left - 1) 421 int most = (((code_t)left << (g.max - len)) - syms) / 422 (((code_t)1 << (g.max - len)) - 1); 423 424 // occupy least table spaces, creating new sub-tables as needed 425 int use = least; 375 426 while (rem < use) { 376 427 use -= rem; 377 rem = 1 << (len - root);428 rem = 1 << (len - g.root); 378 429 mem += rem; 379 430 } 380 431 rem -= use; 381 432 382 / * examine codes from here, updating table space as we go */433 // examine codes from here, updating table space as we go 383 434 for (use = least; use <= most; use++) { 384 code[len] = use;385 examine(syms - use, len + 1, (left - use) <<1,386 mem + (rem ? 1 << (len - root) : 0), rem << 1);435 g.code[len] = use; 436 examine(syms - use, (left - use) << 1, len + 1, 437 mem + (rem ? 1 << (len - g.root) : 0), rem << 1); 387 438 if (rem == 0) { 388 rem = 1 << (len - root);439 rem = 1 << (len - g.root); 389 440 mem += rem; 390 441 } … … 392 443 } 393 444 394 /* remove entries as we drop back down in the recursion */ 395 code[len] = 0; 396 } 397 398 /* Look at all sub-codes starting with root + 1 bits. Look at only the valid 399 intermediate code states (syms, left, len). For each completed code, 400 calculate the amount of memory required by inflate to build the decoding 401 tables. Find the maximum amount of memory required and show the code that 402 requires that maximum. Uses the globals max, root, and num. */ 403 local void enough(int syms) 404 { 405 int n; /* number of remaing symbols for this node */ 406 int left; /* number of unused bit patterns at this length */ 407 size_t index; /* index of this case in *num */ 408 409 /* clear code */ 410 for (n = 0; n <= max; n++) 411 code[n] = 0; 412 413 /* look at all (root + 1) bit and longer codes */ 414 large = 1 << root; /* base table */ 415 if (root < max) /* otherwise, there's only a base table */ 416 for (n = 3; n <= syms; n++) 417 for (left = 2; left < n; left += 2) 418 { 419 /* look at all reachable (root + 1) bit nodes, and the 420 resulting codes (complete at root + 2 or more) */ 421 index = INDEX(n, left, root + 1); 422 if (root + 1 < max && num[index]) /* reachable node */ 423 examine(n, root + 1, left, 1 << root, 0); 424 425 /* also look at root bit codes with completions at root + 1 426 bits (not saved in num, since complete), just in case */ 427 if (num[index - 1] && n <= left << 1) 428 examine((n - left) << 1, root + 1, (n - left) << 1, 429 1 << root, 0); 445 // remove entries as we drop back down in the recursion 446 g.code[len] = 0; 447 } 448 449 // Look at all sub-codes starting with root + 1 bits. Look at only the valid 450 // intermediate code states (syms, left, len). For each completed code, 451 // calculate the amount of memory required by inflate to build the decoding 452 // tables. Find the maximum amount of memory required and show the codes that 453 // require that maximum. 454 local void enough(int syms) { 455 // clear code 456 for (int n = 0; n <= g.max; n++) 457 g.code[n] = 0; 458 459 // look at all (root + 1) bit and longer codes 460 string_clear(&g.out); // empty saved results 461 g.large = 1 << g.root; // base table 462 if (g.root < g.max) // otherwise, there's only a base table 463 for (int n = 3; n <= syms; n++) 464 for (int left = 2; left < n; left += 2) { 465 // look at all reachable (root + 1) bit nodes, and the 466 // resulting codes (complete at root + 2 or more) 467 size_t index = map(n, left, g.root + 1); 468 if (g.root + 1 < g.max && g.num[index]) // reachable node 469 examine(n, left, g.root + 1, 1 << g.root, 0); 470 471 // also look at root bit codes with completions at root + 1 472 // bits (not saved in num, since complete), just in case 473 if (g.num[index - 1] && n <= left << 1) 474 examine((n - left) << 1, (n - left) << 1, g.root + 1, 475 1 << g.root, 0); 430 476 } 431 477 432 /* done */ 433 printf("done: maximum of %d table entries\n", large); 434 } 435 436 /* 437 Examine and show the total number of possible Huffman codes for a given 438 maximum number of symbols, initial root table size, and maximum code length 439 in bits -- those are the command arguments in that order. The default 440 values are 286, 9, and 15 respectively, for the deflate literal/length code. 441 The possible codes are counted for each number of coded symbols from two to 442 the maximum. The counts for each of those and the total number of codes are 443 shown. The maximum number of inflate table entires is then calculated 444 across all possible codes. Each new maximum number of table entries and the 445 associated sub-code (starting at root + 1 == 10 bits) is shown. 446 447 To count and examine Huffman codes that are not length-limited, provide a 448 maximum length equal to the number of symbols minus one. 449 450 For the deflate literal/length code, use "enough". For the deflate distance 451 code, use "enough 30 6". 452 453 This uses the %llu printf format to print big_t numbers, which assumes that 454 big_t is an unsigned long long. If the big_t type is changed (for example 455 to a multiple precision type), the method of printing will also need to be 456 updated. 457 */ 458 int main(int argc, char **argv) 459 { 460 int syms; /* total number of symbols to code */ 461 int n; /* number of symbols to code for this run */ 462 big_t got; /* return value of count() */ 463 big_t sum; /* accumulated number of codes over n */ 464 code_t word; /* for counting bits in code_t */ 465 466 /* set up globals for cleanup() */ 467 code = NULL; 468 num = NULL; 469 done = NULL; 470 471 /* get arguments -- default to the deflate literal/length code */ 472 syms = 286; 473 root = 9; 474 max = 15; 478 // done 479 printf("maximum of %d table entries for root = %d\n", g.large, g.root); 480 fputs(g.out.str, stdout); 481 } 482 483 // Examine and show the total number of possible prefix codes for a given 484 // maximum number of symbols, initial root table size, and maximum code length 485 // in bits -- those are the command arguments in that order. The default values 486 // are 286, 9, and 15 respectively, for the deflate literal/length code. The 487 // possible codes are counted for each number of coded symbols from two to the 488 // maximum. The counts for each of those and the total number of codes are 489 // shown. The maximum number of inflate table entires is then calculated across 490 // all possible codes. Each new maximum number of table entries and the 491 // associated sub-code (starting at root + 1 == 10 bits) is shown. 492 // 493 // To count and examine prefix codes that are not length-limited, provide a 494 // maximum length equal to the number of symbols minus one. 495 // 496 // For the deflate literal/length code, use "enough". For the deflate distance 497 // code, use "enough 30 6". 498 int main(int argc, char **argv) { 499 // set up globals for cleanup() 500 g.code = NULL; 501 g.num = NULL; 502 g.done = NULL; 503 string_init(&g.out); 504 505 // get arguments -- default to the deflate literal/length code 506 int syms = 286; 507 g.root = 9; 508 g.max = 15; 475 509 if (argc > 1) { 476 510 syms = atoi(argv[1]); 477 511 if (argc > 2) { 478 root = atoi(argv[2]);512 g.root = atoi(argv[2]); 479 513 if (argc > 3) 480 max = atoi(argv[3]);514 g.max = atoi(argv[3]); 481 515 } 482 516 } 483 if (argc > 4 || syms < 2 || root < 1 ||max < 1) {517 if (argc > 4 || syms < 2 || g.root < 1 || g.max < 1) { 484 518 fputs("invalid arguments, need: [sym >= 2 [root >= 1 [max >= 1]]]\n", 485 519 stderr); … … 487 521 } 488 522 489 /* if not restricting the code length, the longest is syms - 1 */ 490 if (max > syms - 1) 491 max = syms - 1; 492 493 /* determine the number of bits in a code_t */ 494 for (n = 0, word = 1; word; n++, word <<= 1) 495 ; 496 497 /* make sure that the calculation of most will not overflow */ 498 if (max > n || (code_t)(syms - 2) >= (((code_t)0 - 1) >> (max - 1))) { 523 // if not restricting the code length, the longest is syms - 1 524 if (g.max > syms - 1) 525 g.max = syms - 1; 526 527 // determine the number of bits in a code_t 528 int bits = 0; 529 for (code_t word = 1; word; word <<= 1) 530 bits++; 531 532 // make sure that the calculation of most will not overflow 533 if (g.max > bits || (code_t)(syms - 2) >= ((code_t)-1 >> (g.max - 1))) { 499 534 fputs("abort: code length too long for internal types\n", stderr); 500 535 return 1; 501 536 } 502 537 503 / * reject impossible code requests */504 if ((code_t)(syms - 1) > ((code_t)1 << max) - 1) {538 // reject impossible code requests 539 if ((code_t)(syms - 1) > ((code_t)1 << g.max) - 1) { 505 540 fprintf(stderr, "%d symbols cannot be coded in %d bits\n", 506 syms, max);541 syms, g.max); 507 542 return 1; 508 543 } 509 544 510 /* allocate code vector */ 511 code = calloc(max + 1, sizeof(int)); 512 if (code == NULL) { 513 fputs("abort: unable to allocate enough memory\n", stderr); 514 return 1; 515 } 516 517 /* determine size of saved results array, checking for overflows, 518 allocate and clear the array (set all to zero with calloc()) */ 519 if (syms == 2) /* iff max == 1 */ 520 num = NULL; /* won't be saving any results */ 545 // allocate code vector 546 g.code = calloc(g.max + 1, sizeof(int)); 547 assert(g.code != NULL && "out of memory"); 548 549 // determine size of saved results array, checking for overflows, 550 // allocate and clear the array (set all to zero with calloc()) 551 if (syms == 2) // iff max == 1 552 g.num = NULL; // won't be saving any results 521 553 else { 522 size = syms >> 1;523 i f (size > ((size_t)0 - 1) / (n = (syms - 1) >> 1) ||524 (size *= n, size > ((size_t)0 - 1) / (n = max - 1)) ||525 (size *= n, size > ((size_t)0 - 1) / sizeof(big_t)) ||526 (num = calloc(size, sizeof(big_t))) == NULL) {527 fputs("abort: unable to allocate enough memory\n", stderr);528 cleanup();529 return 1;530 }531 } 532 533 / * count possible codes for all numbers of symbols, add up counts */534 sum = 0;535 for ( n = 2; n <= syms; n++) {536 got = count(n, 1, 2);554 g.size = syms >> 1; 555 int n = (syms - 1) >> 1; 556 assert(g.size <= (size_t)-1 / n && "overflow"); 557 g.size *= n; 558 n = g.max - 1; 559 assert(g.size <= (size_t)-1 / n && "overflow"); 560 g.size *= n; 561 g.num = calloc(g.size, sizeof(big_t)); 562 assert(g.num != NULL && "out of memory"); 563 } 564 565 // count possible codes for all numbers of symbols, add up counts 566 big_t sum = 0; 567 for (int n = 2; n <= syms; n++) { 568 big_t got = count(n, 2, 1); 537 569 sum += got; 538 if (got == (big_t)0 - 1 || sum < got) { /* overflow */ 539 fputs("abort: can't count that high!\n", stderr); 540 cleanup(); 541 return 1; 542 } 543 printf("%llu %d-codes\n", got, n); 544 } 545 printf("%llu total codes for 2 to %d symbols", sum, syms); 546 if (max < syms - 1) 547 printf(" (%d-bit length limit)\n", max); 570 assert(got != (big_t)-1 && sum >= got && "overflow"); 571 } 572 printf("%"PRIbig" total codes for 2 to %d symbols", sum, syms); 573 if (g.max < syms - 1) 574 printf(" (%d-bit length limit)\n", g.max); 548 575 else 549 576 puts(" (no length limit)"); 550 577 551 / * allocate and clear done array for beenhere() */578 // allocate and clear done array for been_here() 552 579 if (syms == 2) 553 done = NULL; 554 else if (size > ((size_t)0 - 1) / sizeof(struct tab) || 555 (done = calloc(size, sizeof(struct tab))) == NULL) { 556 fputs("abort: unable to allocate enough memory\n", stderr); 557 cleanup(); 558 return 1; 559 } 560 561 /* find and show maximum inflate table usage */ 562 if (root > max) /* reduce root to max length */ 563 root = max; 564 if ((code_t)syms < ((code_t)1 << (root + 1))) 580 g.done = NULL; 581 else { 582 g.done = calloc(g.size, sizeof(struct tab)); 583 assert(g.done != NULL && "out of memory"); 584 } 585 586 // find and show maximum inflate table usage 587 if (g.root > g.max) // reduce root to max length 588 g.root = g.max; 589 if ((code_t)syms < ((code_t)1 << (g.root + 1))) 565 590 enough(syms); 566 591 else 567 puts("cannot handle minimum code lengths > root");568 569 / * done */592 fputs("cannot handle minimum code lengths > root", stderr); 593 594 // done 570 595 cleanup(); 571 596 return 0; -
trunk/src/libs/zlib-1.2.12/examples/gzappend.c
r76163 r95239 138 138 if (rot == 1) { 139 139 tmp = *list; 140 mem cpy(list, list + 1, len - 1);140 memmove(list, list + 1, len - 1); 141 141 *last = tmp; 142 142 return; -
trunk/src/libs/zlib-1.2.12/examples/gzlog.c
r76163 r95239 1 1 /* 2 2 * gzlog.c 3 * Copyright (C) 2004, 2008, 2012, 2016 Mark Adler, all rights reserved3 * Copyright (C) 2004, 2008, 2012, 2016, 2019 Mark Adler, all rights reserved 4 4 * For conditions of distribution and use, see copyright notice in gzlog.h 5 * version 2. 2, 14 Aug 20125 * version 2.3, 25 May 2019 6 6 */ 7 7 … … 757 757 } 758 758 if ((fd = open(log->path, O_RDONLY, 0)) < 0) { 759 free(data); 759 760 log_log(log, op, ".add file read failure"); 760 761 return -1; … … 763 764 close(fd); 764 765 if (ret) { 766 free(data); 765 767 log_log(log, op, ".add file read failure"); 766 768 return -1; -
trunk/src/libs/zlib-1.2.12/examples/zran.c
r76163 r95239 1 1 /* zran.c -- example of zlib/gzip stream indexing and random access 2 * Copyright (C) 2005, 2012 Mark Adler2 * Copyright (C) 2005, 2012, 2018 Mark Adler 3 3 * For conditions of distribution and use, see copyright notice in zlib.h 4 Version 1.1 29 Sep 2012Mark Adler */4 * Version 1.2 14 Oct 2018 Mark Adler */ 5 5 6 6 /* Version History: 7 7 1.0 29 May 2005 First version 8 8 1.1 29 Sep 2012 Fix memory reallocation error 9 1.2 14 Oct 2018 Handle gzip streams with multiple members 10 Add a header file to facilitate usage in applications 9 11 */ 10 12 … … 21 23 uncompressed data that precede that block. Also the uncompressed offset of 22 24 that block is saved to provide a referece for locating a desired starting 23 point in the uncompressed stream. build_index() works by decompressing the24 input zlib or gzip stream a block at a time, and at the end of each block25 deciding if enough uncompressed data has gone by to justify the creation of26 a new access point. If so, that point is saved in a data structure that27 grows as needed to accommodate the points.25 point in the uncompressed stream. deflate_index_build() works by 26 decompressing the input zlib or gzip stream a block at a time, and at the 27 end of each block deciding if enough uncompressed data has gone by to 28 justify the creation of a new access point. If so, that point is saved in a 29 data structure that grows as needed to accommodate the points. 28 30 29 31 To use the index, an offset in the uncompressed data is provided, for which … … 44 46 access, mainly copying the 32K byte dictionary. So if small pieces of the 45 47 file are being accessed, it would make sense to implement a cache to hold 46 some lookahead and avoid many calls to extract() for small lengths. 48 some lookahead and avoid many calls to deflate_index_extract() for small 49 lengths. 47 50 48 51 Another way to build an index would be to use inflateCopy(). That would … … 57 60 #include <string.h> 58 61 #include "zlib.h" 59 60 #define local static 61 62 #define SPAN 1048576L /* desired distance between access points */ 62 #include "zran.h" 63 63 64 #define WINSIZE 32768U /* sliding window size */ 64 65 #define CHUNK 16384 /* file input buffer size */ 65 66 66 /* access point entry*/67 /* Access point entry. */ 67 68 struct point { 68 69 off_t out; /* corresponding offset in uncompressed data */ 69 70 off_t in; /* offset in input file of first full byte */ 70 int bits; /* number of bits (1-7) from byte at in -1, or 0 */71 int bits; /* number of bits (1-7) from byte at in-1, or 0 */ 71 72 unsigned char window[WINSIZE]; /* preceding 32K of uncompressed data */ 72 73 }; 73 74 74 /* access point list */ 75 struct access { 76 int have; /* number of list entries filled in */ 77 int size; /* number of list entries allocated */ 78 struct point *list; /* allocated list */ 79 }; 80 81 /* Deallocate an index built by build_index() */ 82 local void free_index(struct access *index) 75 /* See comments in zran.h. */ 76 void deflate_index_free(struct deflate_index *index) 83 77 { 84 78 if (index != NULL) { … … 88 82 } 89 83 90 /* Add an entry to the access point list. If out of memory, deallocate the 91 existing list and return NULL. */ 92 local struct access *addpoint(struct access *index, int bits, 93 off_t in, off_t out, unsigned left, unsigned char *window) 84 /* Add an entry to the access point list. If out of memory, deallocate the 85 existing list and return NULL. index->gzip is the allocated size of the 86 index in point entries, until it is time for deflate_index_build() to 87 return, at which point gzip is set to indicate a gzip file or not. 88 */ 89 static struct deflate_index *addpoint(struct deflate_index *index, int bits, 90 off_t in, off_t out, unsigned left, 91 unsigned char *window) 94 92 { 95 93 struct point *next; … … 97 95 /* if list is empty, create it (start with eight points) */ 98 96 if (index == NULL) { 99 index = malloc(sizeof(struct access));97 index = malloc(sizeof(struct deflate_index)); 100 98 if (index == NULL) return NULL; 101 99 index->list = malloc(sizeof(struct point) << 3); … … 104 102 return NULL; 105 103 } 106 index-> size= 8;104 index->gzip = 8; 107 105 index->have = 0; 108 106 } 109 107 110 108 /* if list is full, make it bigger */ 111 else if (index->have == index-> size) {112 index-> size<<= 1;113 next = realloc(index->list, sizeof(struct point) * index-> size);109 else if (index->have == index->gzip) { 110 index->gzip <<= 1; 111 next = realloc(index->list, sizeof(struct point) * index->gzip); 114 112 if (next == NULL) { 115 free_index(index);113 deflate_index_free(index); 116 114 return NULL; 117 115 } … … 120 118 121 119 /* fill in entry and increment how many we have */ 122 next = index->list+ index->have;120 next = (struct point *)(index->list) + index->have; 123 121 next->bits = bits; 124 122 next->in = in; … … 134 132 } 135 133 136 /* Make one entire pass through the compressed stream and build an index, with 137 access points about every span bytes of uncompressed output -- span is 138 chosen to balance the speed of random access against the memory requirements 139 of the list, about 32K bytes per access point. Note that data after the end 140 of the first zlib or gzip stream in the file is ignored. build_index() 141 returns the number of access points on success (>= 1), Z_MEM_ERROR for out 142 of memory, Z_DATA_ERROR for an error in the input file, or Z_ERRNO for a 143 file read error. On success, *built points to the resulting index. */ 144 local int build_index(FILE *in, off_t span, struct access **built) 134 /* See comments in zran.h. */ 135 int deflate_index_build(FILE *in, off_t span, struct deflate_index **built) 145 136 { 146 137 int ret; 138 int gzip = 0; /* true if reading a gzip file */ 147 139 off_t totin, totout; /* our own total counters to avoid 4GB limit */ 148 140 off_t last; /* totout value of last access point */ 149 struct access *index;/* access points being generated */141 struct deflate_index *index; /* access points being generated */ 150 142 z_stream strm; 151 143 unsigned char input[CHUNK]; … … 164 156 /* inflate the input, maintain a sliding window, and build an index -- this 165 157 also validates the integrity of the compressed data using the check 166 information at the end ofthe gzip or zlib stream */158 information in the gzip or zlib stream */ 167 159 totin = totout = last = 0; 168 160 index = NULL; /* will be allocated by first addpoint() */ … … 173 165 if (ferror(in)) { 174 166 ret = Z_ERRNO; 175 goto build_index_error;167 goto deflate_index_build_error; 176 168 } 177 169 if (strm.avail_in == 0) { 178 170 ret = Z_DATA_ERROR; 179 goto build_index_error;171 goto deflate_index_build_error; 180 172 } 181 173 strm.next_in = input; 174 175 /* check for a gzip stream */ 176 if (totin == 0 && strm.avail_in >= 3 && 177 input[0] == 31 && input[1] == 139 && input[2] == 8) 178 gzip = 1; 182 179 183 180 /* process all of that, or until end of stream */ … … 199 196 ret = Z_DATA_ERROR; 200 197 if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR) 201 goto build_index_error; 202 if (ret == Z_STREAM_END) 198 goto deflate_index_build_error; 199 if (ret == Z_STREAM_END) { 200 if (gzip && 201 (strm.avail_in || ungetc(getc(in), in) != EOF)) { 202 ret = inflateReset(&strm); 203 if (ret != Z_OK) 204 goto deflate_index_build_error; 205 continue; 206 } 203 207 break; 208 } 204 209 205 210 /* if at end of block, consider adding an index entry (note that if … … 218 223 if (index == NULL) { 219 224 ret = Z_MEM_ERROR; 220 goto build_index_error;225 goto deflate_index_build_error; 221 226 } 222 227 last = totout; … … 228 233 (void)inflateEnd(&strm); 229 234 index->list = realloc(index->list, sizeof(struct point) * index->have); 230 index->size = index->have; 235 index->gzip = gzip; 236 index->length = totout; 231 237 *built = index; 232 return index-> size;238 return index->have; 233 239 234 240 /* return error */ 235 build_index_error:241 deflate_index_build_error: 236 242 (void)inflateEnd(&strm); 237 if (index != NULL) 238 free_index(index); 243 deflate_index_free(index); 239 244 return ret; 240 245 } 241 246 242 /* Use the index to read len bytes from offset into buf, return bytes read or 243 negative for error (Z_DATA_ERROR or Z_MEM_ERROR). If data is requested past 244 the end of the uncompressed data, then extract() will return a value less 245 than len, indicating how much as actually read into buf. This function 246 should not return a data error unless the file was modified since the index 247 was generated. extract() may also return Z_ERRNO if there is an error on 248 reading or seeking the input file. */ 249 local int extract(FILE *in, struct access *index, off_t offset, 250 unsigned char *buf, int len) 247 /* See comments in zran.h. */ 248 int deflate_index_extract(FILE *in, struct deflate_index *index, off_t offset, 249 unsigned char *buf, int len) 251 250 { 252 251 int ret, skip; … … 277 276 ret = fseeko(in, here->in - (here->bits ? 1 : 0), SEEK_SET); 278 277 if (ret == -1) 279 goto extract_ret;278 goto deflate_index_extract_ret; 280 279 if (here->bits) { 281 280 ret = getc(in); 282 281 if (ret == -1) { 283 282 ret = ferror(in) ? Z_ERRNO : Z_DATA_ERROR; 284 goto extract_ret;283 goto deflate_index_extract_ret; 285 284 } 286 285 (void)inflatePrime(&strm, here->bits, ret >> (8 - here->bits)); … … 294 293 do { 295 294 /* define where to put uncompressed data, and how much */ 296 if (offset == 0 && skip) { /* at offset now */297 strm.avail_out = len;298 strm.next_out = buf;299 skip = 0; /* only do this once */300 }301 295 if (offset > WINSIZE) { /* skip WINSIZE bytes */ 302 296 strm.avail_out = WINSIZE; … … 304 298 offset -= WINSIZE; 305 299 } 306 else if (offset != 0) {/* last skip */300 else if (offset > 0) { /* last skip */ 307 301 strm.avail_out = (unsigned)offset; 308 302 strm.next_out = discard; 309 303 offset = 0; 304 } 305 else if (skip) { /* at offset now */ 306 strm.avail_out = len; 307 strm.next_out = buf; 308 skip = 0; /* only do this once */ 310 309 } 311 310 … … 316 315 if (ferror(in)) { 317 316 ret = Z_ERRNO; 318 goto extract_ret;317 goto deflate_index_extract_ret; 319 318 } 320 319 if (strm.avail_in == 0) { 321 320 ret = Z_DATA_ERROR; 322 goto extract_ret;321 goto deflate_index_extract_ret; 323 322 } 324 323 strm.next_in = input; … … 328 327 ret = Z_DATA_ERROR; 329 328 if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR) 330 goto extract_ret; 331 if (ret == Z_STREAM_END) 332 break; 329 goto deflate_index_extract_ret; 330 if (ret == Z_STREAM_END) { 331 /* the raw deflate stream has ended */ 332 if (index->gzip == 0) 333 /* this is a zlib stream that has ended -- done */ 334 break; 335 336 /* near the end of a gzip member, which might be followed by 337 another gzip member -- skip the gzip trailer and see if 338 there is more input after it */ 339 if (strm.avail_in < 8) { 340 fseeko(in, 8 - strm.avail_in, SEEK_CUR); 341 strm.avail_in = 0; 342 } 343 else { 344 strm.avail_in -= 8; 345 strm.next_in += 8; 346 } 347 if (strm.avail_in == 0 && ungetc(getc(in), in) == EOF) 348 /* the input ended after the gzip trailer -- done */ 349 break; 350 351 /* there is more input, so another gzip member should follow -- 352 validate and skip the gzip header */ 353 ret = inflateReset2(&strm, 31); 354 if (ret != Z_OK) 355 goto deflate_index_extract_ret; 356 do { 357 if (strm.avail_in == 0) { 358 strm.avail_in = fread(input, 1, CHUNK, in); 359 if (ferror(in)) { 360 ret = Z_ERRNO; 361 goto deflate_index_extract_ret; 362 } 363 if (strm.avail_in == 0) { 364 ret = Z_DATA_ERROR; 365 goto deflate_index_extract_ret; 366 } 367 strm.next_in = input; 368 } 369 ret = inflate(&strm, Z_BLOCK); 370 if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR) 371 goto deflate_index_extract_ret; 372 } while ((strm.data_type & 128) == 0); 373 374 /* set up to continue decompression of the raw deflate stream 375 that follows the gzip header */ 376 ret = inflateReset2(&strm, -15); 377 if (ret != Z_OK) 378 goto deflate_index_extract_ret; 379 } 380 381 /* continue to process the available input before reading more */ 333 382 } while (strm.avail_out != 0); 334 383 335 /* if reach end of stream, then don't keep trying to get more */336 384 if (ret == Z_STREAM_END) 385 /* reached the end of the compressed data -- return the data that 386 was available, possibly less than requested */ 337 387 break; 338 388 339 /* do until offset reached and requested data read , or stream ends*/389 /* do until offset reached and requested data read */ 340 390 } while (skip); 341 391 342 /* compute number of uncompressed bytes read afteroffset */392 /* compute the number of uncompressed bytes read after the offset */ 343 393 ret = skip ? 0 : len - strm.avail_out; 344 394 345 /* clean up and return bytes read orerror */346 extract_ret:395 /* clean up and return the bytes read, or the negative error */ 396 deflate_index_extract_ret: 347 397 (void)inflateEnd(&strm); 348 398 return ret; 349 399 } 350 400 351 /* Demonstrate the use of build_index() and extract() by processing the file 352 provided on the command line, and the extracting 16K from about 2/3rds of 353 the way through the uncompressed output, and writing that to stdout. */ 401 #ifdef TEST 402 403 #define SPAN 1048576L /* desired distance between access points */ 404 #define LEN 16384 /* number of bytes to extract */ 405 406 /* Demonstrate the use of deflate_index_build() and deflate_index_extract() by 407 processing the file provided on the command line, and extracting LEN bytes 408 from 2/3rds of the way through the uncompressed output, writing that to 409 stdout. An offset can be provided as the second argument, in which case the 410 data is extracted from there instead. */ 354 411 int main(int argc, char **argv) 355 412 { 356 413 int len; 357 off_t offset ;414 off_t offset = -1; 358 415 FILE *in; 359 struct access*index = NULL;360 unsigned char buf[ CHUNK];416 struct deflate_index *index = NULL; 417 unsigned char buf[LEN]; 361 418 362 419 /* open input file */ 363 if (argc != 2) {364 fprintf(stderr, "usage: zran file.gz \n");420 if (argc < 2 || argc > 3) { 421 fprintf(stderr, "usage: zran file.gz [offset]\n"); 365 422 return 1; 366 423 } … … 371 428 } 372 429 430 /* get optional offset */ 431 if (argc == 3) { 432 char *end; 433 offset = strtoll(argv[2], &end, 10); 434 if (*end || offset < 0) { 435 fprintf(stderr, "zran: %s is not a valid offset\n", argv[2]); 436 return 1; 437 } 438 } 439 373 440 /* build index */ 374 len = build_index(in, SPAN, &index);441 len = deflate_index_build(in, SPAN, &index); 375 442 if (len < 0) { 376 443 fclose(in); … … 393 460 394 461 /* use index by reading some bytes from an arbitrary offset */ 395 offset = (index->list[index->have - 1].out << 1) / 3; 396 len = extract(in, index, offset, buf, CHUNK); 462 if (offset == -1) 463 offset = (index->length << 1) / 3; 464 len = deflate_index_extract(in, index, offset, buf, LEN); 397 465 if (len < 0) 398 466 fprintf(stderr, "zran: extraction failed: %s error\n", … … 404 472 405 473 /* clean up and exit */ 406 free_index(index);474 deflate_index_free(index); 407 475 fclose(in); 408 476 return 0; 409 477 } 478 479 #endif
Note:
See TracChangeset
for help on using the changeset viewer.