aboutsummaryrefslogtreecommitdiff
path: root/examples
diff options
context:
space:
mode:
authorMark Adler <madler@alumni.caltech.edu>2018-08-01 01:37:03 -0700
committerMark Adler <madler@alumni.caltech.edu>2018-08-01 01:37:03 -0700
commit194e558efefe58866c88519708a7ff836b2c66be (patch)
tree4374dc3410b82ca2388d3cc463a60d8d60ae49f1 /examples
parent4346a16853e19b45787ce933666026903fb8f3f8 (diff)
downloadzlib-194e558efefe58866c88519708a7ff836b2c66be.tar.gz
zlib-194e558efefe58866c88519708a7ff836b2c66be.tar.bz2
zlib-194e558efefe58866c88519708a7ff836b2c66be.zip
Use a structure to make globals in enough.c evident.
Diffstat (limited to 'examples')
-rw-r--r--examples/enough.c175
1 files changed, 89 insertions, 86 deletions
diff --git a/examples/enough.c b/examples/enough.c
index b991144..b1be6f0 100644
--- a/examples/enough.c
+++ b/examples/enough.c
@@ -167,32 +167,34 @@ struct tab { /* type for been here check */
167 */ 167 */
168 168
169/* Globals to avoid propagating constants or constant pointers recursively */ 169/* Globals to avoid propagating constants or constant pointers recursively */
170local int max; /* maximum allowed bit length for the codes */ 170struct {
171local int root; /* size of base code table in bits */ 171 int max; /* maximum allowed bit length for the codes */
172local int large; /* largest code table so far */ 172 int root; /* size of base code table in bits */
173local size_t size; /* number of elements in num and done */ 173 int large; /* largest code table so far */
174local int *code; /* number of symbols assigned to each bit length */ 174 size_t size; /* number of elements in num and done */
175local big_t *num; /* saved results array for code counting */ 175 int *code; /* number of symbols assigned to each bit length */
176local struct tab *done; /* states already evaluated array */ 176 big_t *num; /* saved results array for code counting */
177 struct tab *done; /* states already evaluated array */
178} g;
177 179
178/* Index function for num[] and done[] */ 180/* 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) 181#define INDEX(i,j,k) (((size_t)((i-1)>>1)*((i-2)>>1)+(j>>1)-1)*(g.max-1)+k-1)
180 182
181/* Free allocated space. Uses globals code, num, and done. */ 183/* Free allocated space. Uses globals code, num, and done. */
182local void cleanup(void) 184local void cleanup(void)
183{ 185{
184 size_t n; 186 size_t n;
185 187
186 if (done != NULL) { 188 if (g.done != NULL) {
187 for (n = 0; n < size; n++) 189 for (n = 0; n < g.size; n++)
188 if (done[n].len) 190 if (g.done[n].len)
189 free(done[n].vec); 191 free(g.done[n].vec);
190 free(done); 192 free(g.done);
191 } 193 }
192 if (num != NULL) 194 if (g.num != NULL)
193 free(num); 195 free(g.num);
194 if (code != NULL) 196 if (g.code != NULL)
195 free(code); 197 free(g.code);
196} 198}
197 199
198/* Return the number of possible Huffman codes using bit patterns of lengths 200/* Return the number of possible Huffman codes using bit patterns of lengths
@@ -214,11 +216,11 @@ local big_t count(int syms, int len, int left)
214 return 1; 216 return 1;
215 217
216 /* note and verify the expected state */ 218 /* note and verify the expected state */
217 assert(syms > left && left > 0 && len < max); 219 assert(syms > left && left > 0 && len < g.max);
218 220
219 /* see if we've done this one already */ 221 /* see if we've done this one already */
220 index = INDEX(syms, left, len); 222 index = INDEX(syms, left, len);
221 got = num[index]; 223 got = g.num[index];
222 if (got) 224 if (got)
223 return got; /* we have -- return the saved result */ 225 return got; /* we have -- return the saved result */
224 226
@@ -231,8 +233,8 @@ local big_t count(int syms, int len, int left)
231 /* we can use at most this many bit patterns, lest there not be enough 233 /* we can use at most this many bit patterns, lest there not be enough
232 available for the remaining symbols at the maximum length (if there were 234 available for the remaining symbols at the maximum length (if there were
233 no limit to the code length, this would become: most = left - 1) */ 235 no limit to the code length, this would become: most = left - 1) */
234 most = (((code_t)left << (max - len)) - syms) / 236 most = (((code_t)left << (g.max - len)) - syms) /
235 (((code_t)1 << (max - len)) - 1); 237 (((code_t)1 << (g.max - len)) - 1);
236 238
237 /* count all possible codes from this juncture and add them up */ 239 /* count all possible codes from this juncture and add them up */
238 sum = 0; 240 sum = 0;
@@ -247,7 +249,7 @@ local big_t count(int syms, int len, int left)
247 assert(sum != 0); 249 assert(sum != 0);
248 250
249 /* save the result and return it */ 251 /* save the result and return it */
250 num[index] = sum; 252 g.num[index] = sum;
251 return sum; 253 return sum;
252} 254}
253 255
@@ -265,14 +267,14 @@ local int beenhere(int syms, int len, int left, int mem, int rem)
265 267
266 /* point to vector for (syms,left,len), bit in vector for (mem,rem) */ 268 /* point to vector for (syms,left,len), bit in vector for (mem,rem) */
267 index = INDEX(syms, left, len); 269 index = INDEX(syms, left, len);
268 mem -= 1 << root; 270 mem -= 1 << g.root;
269 offset = (mem >> 3) + rem; 271 offset = (mem >> 3) + rem;
270 offset = ((offset * (offset + 1)) >> 1) + rem; 272 offset = ((offset * (offset + 1)) >> 1) + rem;
271 bit = 1 << (mem & 7); 273 bit = 1 << (mem & 7);
272 274
273 /* see if we've been here */ 275 /* see if we've been here */
274 length = done[index].len; 276 length = g.done[index].len;
275 if (offset < length && (done[index].vec[offset] & bit) != 0) 277 if (offset < length && (g.done[index].vec[offset] & bit) != 0)
276 return 1; /* done this! */ 278 return 1; /* done this! */
277 279
278 /* we haven't been here before -- set the bit to show we have now */ 280 /* we haven't been here before -- set the bit to show we have now */
@@ -284,14 +286,15 @@ local int beenhere(int syms, int len, int left, int mem, int rem)
284 do { 286 do {
285 length <<= 1; 287 length <<= 1;
286 } while (length <= offset); 288 } while (length <= offset);
287 vector = realloc(done[index].vec, length); 289 vector = realloc(g.done[index].vec, length);
288 if (vector != NULL) 290 if (vector != NULL)
289 memset(vector + done[index].len, 0, length - done[index].len); 291 memset(vector + g.done[index].len, 0,
292 length - g.done[index].len);
290 } 293 }
291 294
292 /* otherwise we need to make a new vector and zero it out */ 295 /* otherwise we need to make a new vector and zero it out */
293 else { 296 else {
294 length = 1 << (len - root); 297 length = 1 << (len - g.root);
295 while (length <= offset) 298 while (length <= offset)
296 length <<= 1; 299 length <<= 1;
297 vector = calloc(length, sizeof(char)); 300 vector = calloc(length, sizeof(char));
@@ -305,12 +308,12 @@ local int beenhere(int syms, int len, int left, int mem, int rem)
305 } 308 }
306 309
307 /* install the new vector */ 310 /* install the new vector */
308 done[index].len = length; 311 g.done[index].len = length;
309 done[index].vec = vector; 312 g.done[index].vec = vector;
310 } 313 }
311 314
312 /* set the bit */ 315 /* set the bit */
313 done[index].vec[offset] |= bit; 316 g.done[index].vec[offset] |= bit;
314 return 0; 317 return 0;
315} 318}
316 319
@@ -328,29 +331,29 @@ local void examine(int syms, int len, int left, int mem, int rem)
328 /* see if we have a complete code */ 331 /* see if we have a complete code */
329 if (syms == left) { 332 if (syms == left) {
330 /* set the last code entry */ 333 /* set the last code entry */
331 code[len] = left; 334 g.code[len] = left;
332 335
333 /* complete computation of memory used by this code */ 336 /* complete computation of memory used by this code */
334 while (rem < left) { 337 while (rem < left) {
335 left -= rem; 338 left -= rem;
336 rem = 1 << (len - root); 339 rem = 1 << (len - g.root);
337 mem += rem; 340 mem += rem;
338 } 341 }
339 assert(rem == left); 342 assert(rem == left);
340 343
341 /* if this is a new maximum, show the entries used and the sub-code */ 344 /* if this is a new maximum, show the entries used and the sub-code */
342 if (mem > large) { 345 if (mem > g.large) {
343 large = mem; 346 g.large = mem;
344 printf("max %d: ", mem); 347 printf("max %d: ", mem);
345 for (use = root + 1; use <= max; use++) 348 for (use = g.root + 1; use <= g.max; use++)
346 if (code[use]) 349 if (g.code[use])
347 printf("%d[%d] ", code[use], use); 350 printf("%d[%d] ", g.code[use], use);
348 putchar('\n'); 351 putchar('\n');
349 fflush(stdout); 352 fflush(stdout);
350 } 353 }
351 354
352 /* remove entries as we drop back down in the recursion */ 355 /* remove entries as we drop back down in the recursion */
353 code[len] = 0; 356 g.code[len] = 0;
354 return; 357 return;
355 } 358 }
356 359
@@ -367,32 +370,32 @@ local void examine(int syms, int len, int left, int mem, int rem)
367 /* we can use at most this many bit patterns, lest there not be enough 370 /* we can use at most this many bit patterns, lest there not be enough
368 available for the remaining symbols at the maximum length (if there were 371 available for the remaining symbols at the maximum length (if there were
369 no limit to the code length, this would become: most = left - 1) */ 372 no limit to the code length, this would become: most = left - 1) */
370 most = (((code_t)left << (max - len)) - syms) / 373 most = (((code_t)left << (g.max - len)) - syms) /
371 (((code_t)1 << (max - len)) - 1); 374 (((code_t)1 << (g.max - len)) - 1);
372 375
373 /* occupy least table spaces, creating new sub-tables as needed */ 376 /* occupy least table spaces, creating new sub-tables as needed */
374 use = least; 377 use = least;
375 while (rem < use) { 378 while (rem < use) {
376 use -= rem; 379 use -= rem;
377 rem = 1 << (len - root); 380 rem = 1 << (len - g.root);
378 mem += rem; 381 mem += rem;
379 } 382 }
380 rem -= use; 383 rem -= use;
381 384
382 /* examine codes from here, updating table space as we go */ 385 /* examine codes from here, updating table space as we go */
383 for (use = least; use <= most; use++) { 386 for (use = least; use <= most; use++) {
384 code[len] = use; 387 g.code[len] = use;
385 examine(syms - use, len + 1, (left - use) << 1, 388 examine(syms - use, len + 1, (left - use) << 1,
386 mem + (rem ? 1 << (len - root) : 0), rem << 1); 389 mem + (rem ? 1 << (len - g.root) : 0), rem << 1);
387 if (rem == 0) { 390 if (rem == 0) {
388 rem = 1 << (len - root); 391 rem = 1 << (len - g.root);
389 mem += rem; 392 mem += rem;
390 } 393 }
391 rem--; 394 rem--;
392 } 395 }
393 396
394 /* remove entries as we drop back down in the recursion */ 397 /* remove entries as we drop back down in the recursion */
395 code[len] = 0; 398 g.code[len] = 0;
396} 399}
397 400
398/* Look at all sub-codes starting with root + 1 bits. Look at only the valid 401/* Look at all sub-codes starting with root + 1 bits. Look at only the valid
@@ -407,30 +410,30 @@ local void enough(int syms)
407 size_t index; /* index of this case in *num */ 410 size_t index; /* index of this case in *num */
408 411
409 /* clear code */ 412 /* clear code */
410 for (n = 0; n <= max; n++) 413 for (n = 0; n <= g.max; n++)
411 code[n] = 0; 414 g.code[n] = 0;
412 415
413 /* look at all (root + 1) bit and longer codes */ 416 /* look at all (root + 1) bit and longer codes */
414 large = 1 << root; /* base table */ 417 g.large = 1 << g.root; /* base table */
415 if (root < max) /* otherwise, there's only a base table */ 418 if (g.root < g.max) /* otherwise, there's only a base table */
416 for (n = 3; n <= syms; n++) 419 for (n = 3; n <= syms; n++)
417 for (left = 2; left < n; left += 2) 420 for (left = 2; left < n; left += 2)
418 { 421 {
419 /* look at all reachable (root + 1) bit nodes, and the 422 /* look at all reachable (root + 1) bit nodes, and the
420 resulting codes (complete at root + 2 or more) */ 423 resulting codes (complete at root + 2 or more) */
421 index = INDEX(n, left, root + 1); 424 index = INDEX(n, left, g.root + 1);
422 if (root + 1 < max && num[index]) /* reachable node */ 425 if (g.root + 1 < g.max && g.num[index]) /* reachable node */
423 examine(n, root + 1, left, 1 << root, 0); 426 examine(n, g.root + 1, left, 1 << g.root, 0);
424 427
425 /* also look at root bit codes with completions at root + 1 428 /* also look at root bit codes with completions at root + 1
426 bits (not saved in num, since complete), just in case */ 429 bits (not saved in num, since complete), just in case */
427 if (num[index - 1] && n <= left << 1) 430 if (g.num[index - 1] && n <= left << 1)
428 examine((n - left) << 1, root + 1, (n - left) << 1, 431 examine((n - left) << 1, g.root + 1, (n - left) << 1,
429 1 << root, 0); 432 1 << g.root, 0);
430 } 433 }
431 434
432 /* done */ 435 /* done */
433 printf("done: maximum of %d table entries\n", large); 436 printf("done: maximum of %d table entries\n", g.large);
434} 437}
435 438
436/* 439/*
@@ -464,52 +467,52 @@ int main(int argc, char **argv)
464 code_t word; /* for counting bits in code_t */ 467 code_t word; /* for counting bits in code_t */
465 468
466 /* set up globals for cleanup() */ 469 /* set up globals for cleanup() */
467 code = NULL; 470 g.code = NULL;
468 num = NULL; 471 g.num = NULL;
469 done = NULL; 472 g.done = NULL;
470 473
471 /* get arguments -- default to the deflate literal/length code */ 474 /* get arguments -- default to the deflate literal/length code */
472 syms = 286; 475 syms = 286;
473 root = 9; 476 g.root = 9;
474 max = 15; 477 g.max = 15;
475 if (argc > 1) { 478 if (argc > 1) {
476 syms = atoi(argv[1]); 479 syms = atoi(argv[1]);
477 if (argc > 2) { 480 if (argc > 2) {
478 root = atoi(argv[2]); 481 g.root = atoi(argv[2]);
479 if (argc > 3) 482 if (argc > 3)
480 max = atoi(argv[3]); 483 g.max = atoi(argv[3]);
481 } 484 }
482 } 485 }
483 if (argc > 4 || syms < 2 || root < 1 || max < 1) { 486 if (argc > 4 || syms < 2 || g.root < 1 || g.max < 1) {
484 fputs("invalid arguments, need: [sym >= 2 [root >= 1 [max >= 1]]]\n", 487 fputs("invalid arguments, need: [sym >= 2 [root >= 1 [max >= 1]]]\n",
485 stderr); 488 stderr);
486 return 1; 489 return 1;
487 } 490 }
488 491
489 /* if not restricting the code length, the longest is syms - 1 */ 492 /* if not restricting the code length, the longest is syms - 1 */
490 if (max > syms - 1) 493 if (g.max > syms - 1)
491 max = syms - 1; 494 g.max = syms - 1;
492 495
493 /* determine the number of bits in a code_t */ 496 /* determine the number of bits in a code_t */
494 for (n = 0, word = 1; word; n++, word <<= 1) 497 for (n = 0, word = 1; word; n++, word <<= 1)
495 ; 498 ;
496 499
497 /* make sure that the calculation of most will not overflow */ 500 /* make sure that the calculation of most will not overflow */
498 if (max > n || (code_t)(syms - 2) >= (((code_t)0 - 1) >> (max - 1))) { 501 if (g.max > n || (code_t)(syms - 2) >= (((code_t)0 - 1) >> (g.max - 1))) {
499 fputs("abort: code length too long for internal types\n", stderr); 502 fputs("abort: code length too long for internal types\n", stderr);
500 return 1; 503 return 1;
501 } 504 }
502 505
503 /* reject impossible code requests */ 506 /* reject impossible code requests */
504 if ((code_t)(syms - 1) > ((code_t)1 << max) - 1) { 507 if ((code_t)(syms - 1) > ((code_t)1 << g.max) - 1) {
505 fprintf(stderr, "%d symbols cannot be coded in %d bits\n", 508 fprintf(stderr, "%d symbols cannot be coded in %d bits\n",
506 syms, max); 509 syms, g.max);
507 return 1; 510 return 1;
508 } 511 }
509 512
510 /* allocate code vector */ 513 /* allocate code vector */
511 code = calloc(max + 1, sizeof(int)); 514 g.code = calloc(g.max + 1, sizeof(int));
512 if (code == NULL) { 515 if (g.code == NULL) {
513 fputs("abort: unable to allocate enough memory\n", stderr); 516 fputs("abort: unable to allocate enough memory\n", stderr);
514 return 1; 517 return 1;
515 } 518 }
@@ -517,13 +520,13 @@ int main(int argc, char **argv)
517 /* determine size of saved results array, checking for overflows, 520 /* determine size of saved results array, checking for overflows,
518 allocate and clear the array (set all to zero with calloc()) */ 521 allocate and clear the array (set all to zero with calloc()) */
519 if (syms == 2) /* iff max == 1 */ 522 if (syms == 2) /* iff max == 1 */
520 num = NULL; /* won't be saving any results */ 523 g.num = NULL; /* won't be saving any results */
521 else { 524 else {
522 size = syms >> 1; 525 g.size = syms >> 1;
523 if (size > ((size_t)0 - 1) / (n = (syms - 1) >> 1) || 526 if (g.size > ((size_t)0 - 1) / (n = (syms - 1) >> 1) ||
524 (size *= n, size > ((size_t)0 - 1) / (n = max - 1)) || 527 (g.size *= n, g.size > ((size_t)0 - 1) / (n = g.max - 1)) ||
525 (size *= n, size > ((size_t)0 - 1) / sizeof(big_t)) || 528 (g.size *= n, g.size > ((size_t)0 - 1) / sizeof(big_t)) ||
526 (num = calloc(size, sizeof(big_t))) == NULL) { 529 (g.num = calloc(g.size, sizeof(big_t))) == NULL) {
527 fputs("abort: unable to allocate enough memory\n", stderr); 530 fputs("abort: unable to allocate enough memory\n", stderr);
528 cleanup(); 531 cleanup();
529 return 1; 532 return 1;
@@ -543,25 +546,25 @@ int main(int argc, char **argv)
543 printf("%llu %d-codes\n", got, n); 546 printf("%llu %d-codes\n", got, n);
544 } 547 }
545 printf("%llu total codes for 2 to %d symbols", sum, syms); 548 printf("%llu total codes for 2 to %d symbols", sum, syms);
546 if (max < syms - 1) 549 if (g.max < syms - 1)
547 printf(" (%d-bit length limit)\n", max); 550 printf(" (%d-bit length limit)\n", g.max);
548 else 551 else
549 puts(" (no length limit)"); 552 puts(" (no length limit)");
550 553
551 /* allocate and clear done array for beenhere() */ 554 /* allocate and clear done array for beenhere() */
552 if (syms == 2) 555 if (syms == 2)
553 done = NULL; 556 g.done = NULL;
554 else if (size > ((size_t)0 - 1) / sizeof(struct tab) || 557 else if (g.size > ((size_t)0 - 1) / sizeof(struct tab) ||
555 (done = calloc(size, sizeof(struct tab))) == NULL) { 558 (g.done = calloc(g.size, sizeof(struct tab))) == NULL) {
556 fputs("abort: unable to allocate enough memory\n", stderr); 559 fputs("abort: unable to allocate enough memory\n", stderr);
557 cleanup(); 560 cleanup();
558 return 1; 561 return 1;
559 } 562 }
560 563
561 /* find and show maximum inflate table usage */ 564 /* find and show maximum inflate table usage */
562 if (root > max) /* reduce root to max length */ 565 if (g.root > g.max) /* reduce root to max length */
563 root = max; 566 g.root = g.max;
564 if ((code_t)syms < ((code_t)1 << (root + 1))) 567 if ((code_t)syms < ((code_t)1 << (g.root + 1)))
565 enough(syms); 568 enough(syms);
566 else 569 else
567 puts("cannot handle minimum code lengths > root"); 570 puts("cannot handle minimum code lengths > root");