home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume35 / freeze / part02 / statist.c < prev   
C/C++ Source or Header  |  1993-02-21  |  6KB  |  293 lines
  1. #include "freeze.h"
  2. #include "lz.h"
  3.  
  4. /* This program calculates the distribution of the matched strings'
  5. positions and lengths using nearly the same code as `freeze'.
  6. */
  7.  
  8. #define N_POS 62
  9. #define T (N_POS * 2 - 1)
  10. #define R (T - 1)
  11.  
  12. #define update(c) (/* fprintf(stderr, "%d\n", c), */ freq[c]++)
  13.  
  14. long in_count, refers = 0;
  15.  
  16. long indc_count;
  17. int reduceflag = 0, greedy = 0;
  18.  
  19. int lens[LOOKAHEAD+1];
  20.  
  21. us_t bits[9];
  22.  
  23. short   prnt[T];
  24. ul_t freq[T];
  25. short used[T];
  26.  
  27. void freeze(), StartHuff();
  28.  
  29. RETSIGTYPE giveres();
  30.  
  31. int main(argc, argv) char ** argv; {
  32.     argv++;
  33.     while (argc > 1) {
  34.         if (**argv == '-') {
  35.             while (*++(*argv) == 'g' || **argv == 'x')
  36.                 greedy += ((**argv == 'g') << 1) - 1;
  37.             if (**argv)
  38.                 goto usage;
  39.             argc--; argv++;
  40.         } else
  41.             break;
  42.     }
  43.     usage:
  44.     if(argc != 1) {
  45.         fprintf(stderr, "Usage: statist [-gx...] < sample_file\n");
  46.         fprintf(stderr, "Press INTR to display current values\n");
  47.         exit(0);
  48.     }
  49.     signal(SIGINT, giveres);
  50.  
  51. #ifdef DOS
  52.     setmode(fileno(stdin), O_BINARY);       /* Oh this MS-DOS ... */
  53. #endif  /* DOS */
  54.  
  55.     freeze();
  56.     giveres();
  57.     return 0;
  58. }
  59.  
  60. ul_t isqrt(val)
  61. ul_t val;
  62. {
  63.   ul_t result = 0;
  64.   ul_t side = 0;
  65.   ul_t left = 0;
  66.   int digit = 0;
  67.   int i;
  68.   for (i=0; i<sizeof(ul_t)*4; i++)
  69.   {
  70.     left = (left << 2) + (val >> (sizeof(ul_t) * 8 - 2));
  71.     val <<= 2;
  72.     if (left >= side*2 + 1)
  73.     {
  74.       left -= side*2+1;
  75.       side = (side+1)*2;
  76.       result <<= 1;
  77.       result |= 1;
  78.     }
  79.     else
  80.     {
  81.       side *= 2;
  82.       result <<= 1;
  83.     }
  84.   }
  85.   return result;
  86. }
  87.  
  88.  
  89. /* Prints the (current) values of tunable parameters. Uncertainty is
  90. the number of missequencings (algorithm assumes the probabilities
  91. of references decrease uniformly when distance increases). Ideally
  92. it should be 0, but somewhat about 5 or less denotes the given 8 values
  93. could improve the compression rate when using them.
  94. */
  95.  
  96. RETSIGTYPE giveres() {
  97.     us_t c;
  98.     register int i, j, k, pr, f, average, sum;
  99.     ul_t cumul, sigma2;
  100.     short r, percent;
  101.     signal(SIGINT, giveres);
  102.     newtry:
  103.     StartHuff(N_POS);
  104.     pr = f = 0;
  105.     i = N_POS;
  106.     r = N_POS * 2 - 2;
  107.     while (i <= r) {
  108.         j = findmin(i);
  109.         k = findmin(i);
  110.         freq[i] = freq[j] + freq[k];
  111.         prnt[j] = prnt[k] = i++;
  112.     }
  113.  
  114.     for (c = 1; c <= 6; c++) bits[c] = 0;
  115.  
  116.     printf("Non-monotonities are in: ");
  117.  
  118.     for(c = 0; c < N_POS; c++) {
  119.         j = 0;
  120.         k = c;
  121.         do j++; while ((k = prnt[k]) != r);
  122.         if (j <= 6)
  123.             bits[j]++;
  124.         if (j < pr) {
  125.             f += pr - j;
  126.             printf("%d, ", c);
  127.  
  128.         } else
  129.             pr = j;
  130.     }
  131.     if(f == 0)
  132.         printf("\b\b\b\babsent.\n");
  133.     else
  134.         printf("\b\b.\n");
  135.  
  136.     k = bits[1] + bits[2] + bits[3] + bits[4] +
  137.     bits[5] + bits[6];
  138.  
  139.     k = N_POS - k;  /* free variable length codes for 7 & 8 bits */
  140.  
  141.     j = 128 * bits[1] + 64 * bits[2] + 32 * bits[3] +
  142.     16 * bits[4] + 8 * bits[5] + 4 * bits[6];
  143.  
  144.     j = 256 - j;    /* free byte images for these codes */
  145.  
  146. /*      Equation:
  147.         bits[7] + bits[8] = k
  148.     2 * bits[7] + bits[8] = j
  149. */
  150.     j -= k;
  151.     if (j < 0 || k < j) {
  152.         printf("Huffman tree has more than 8 levels, reducing...\n");
  153.         for (i = 0; i < N_POS; i++)
  154.             if (!freq[i])
  155.                 freq[i] = 1;
  156.             else if (reduceflag)
  157.                 freq[i] = (freq[i] + 1) / 2;
  158.         reduceflag = 1;
  159.         goto newtry;
  160.     } else {
  161.         bits[7] = j;
  162.         bits[8] = k - j;
  163.         printf("%d,%d,%d,%d,%d,%d,%d,%d (uncertainty = %d)\n",
  164.             bits[1], bits[2], bits[3], bits[4],
  165.             bits[5], bits[6], bits[7], bits[8], f);
  166.     }
  167.     sum = 0; cumul = 0;
  168.     for(i = 3; i <= LOOKAHEAD; i++) {
  169.         cumul += (ul_t) i * lens[i];
  170.         sum += lens[i];
  171.     }
  172.     sum || sum++;
  173.     printf("Average match length: %d.%02d\n",
  174.         average = cumul / sum, i = cumul * 100 / sum % 100);
  175.     if (i >= 50) average++;
  176.     j = sum;
  177.     percent = 0;
  178.     for (i = LOOKAHEAD; i >= 3; i--) {
  179.         static pcs[] = { 999, 995, 990, 970, 950, 900, 800, 700, 500 };
  180.         j -= lens[i];
  181.         newpcs:
  182.         if (j <= sum * pcs[percent] / 1000) {
  183.             printf("Percentile %d.%d: %d\n",
  184.                 pcs[percent] / 10, pcs[percent] % 10, i);
  185.             if (percent == sizeof(pcs)/sizeof(int) - 1)
  186.                 break;
  187.             else {
  188.                 percent++;
  189.                 goto newpcs;
  190.             }
  191.         }
  192.     }
  193.     for (sigma2 = 0, i = 3; i <= LOOKAHEAD; i++)
  194.         sigma2 += (ul_t)(i - average)*(i - average)*lens[i];
  195.     sigma2 = sigma2 * 100 / sum;
  196.     j = (int)isqrt(sigma2);
  197.     printf("Sigma: %d.%1d\n", j / 10, j % 10);
  198.     printf("References: %ld\n", refers);
  199.     fflush(stdout);
  200. }
  201.  
  202.  
  203. void freeze ()
  204. {
  205.     register int i, len, s, c;
  206.     register hash_t r;
  207.     int match_length;
  208.  
  209.     StartHuff(0);
  210.     InitTree();
  211.     r = MAXDIST + 1;
  212.     s = (r + LOOKAHEAD) & WINMASK;
  213.     for (len = 0; len < LOOKAHEAD && (c = getchar()) != EOF; len++)
  214.       text_buf[r + len] = c;
  215.  
  216.     in_count = len;
  217.     for (i = r - LOOKAHEAD; i < MAXDIST; i++)
  218.       text_buf[i] = ' ';
  219.     for (i = r - LOOKAHEAD; i <= r; i++) {
  220.         register uc_t  *key = &text_buf[i];
  221.         register unsigned p = hashof(key);
  222.         next[i] = hashtab[p];
  223.         hashtab[p] = i;
  224.     }
  225.     while (len != 0) {
  226.         match_length = LOOKAHEAD + get_next_match(THRESHOLD - LOOKAHEAD, r);
  227.         if (match_length > len)
  228.             match_length = len;
  229.         if (match_length <= THRESHOLD) {
  230.             match_length = 1;
  231.         } else if (match_length >= chain_length) {
  232.             lens[match_length] ++;
  233.             update((((r - match_position) & WINMASK) - 1) >> 7);
  234.             refers ++;
  235.         } else {
  236.             register us_t orig_length, orig_position;
  237.             orig_length = match_length;
  238.             orig_position = match_position;
  239.             Next_Char(WINSIZE, LOOKAHEAD);
  240.             match_length = LOOKAHEAD + get_next_match(match_length - LOOKAHEAD, r);
  241.             if (match_length > len)
  242.                 match_length = len;
  243.             if (orig_length >= match_length) {
  244.                 lens[orig_length] ++;
  245.                 update((((r - 1 - orig_position) & WINMASK) - 1) >> 7);
  246.                 match_length = orig_length - 1;
  247.             } else  {
  248.                 lens[match_length] ++;
  249.                 update((((r - match_position) & WINMASK) - 1) >> 7);
  250.             }
  251.             refers ++;
  252.         }
  253.         for (i = 0; i < match_length &&
  254.                 (c = getchar()) != EOF; i++) {
  255.             text_buf[s] = c;
  256.             if (s < LOOKAHEAD - 1)
  257.                 text_buf[s + WINSIZE] = c;
  258.             s = (s + 1) & WINMASK;
  259.             r++;
  260.             InsertNode();
  261.         }
  262.         in_count += i;
  263.         if ((in_count > indc_count)) {
  264.             fprintf(stderr, "%5dK\b\b\b\b\b\b", in_count / 1024);
  265.             fflush (stderr);
  266.             indc_count += 4096;
  267.         }
  268.         while (i++ < match_length) {
  269.             len--;
  270.             r++;
  271.             InsertNode();
  272.         }
  273.     }
  274. }
  275.  
  276. void StartHuff(beg) {
  277.     int i;
  278.     for (i = beg; i < N_POS * 2 - 1; i++)
  279.         freq[i] = 0;
  280.     for (i = 0; i < N_POS * 2 - 1; i++)
  281.         used[i] = prnt[i] = 0;
  282. }
  283.  
  284. int findmin(range) {
  285.     long min = (1 << 30) - 1, argmin = -1, i;
  286.     for (i = 0; i < range; i++) {
  287.         if(!used[i] && freq[i] < min)
  288.             min = freq[argmin = i];
  289.     }
  290.     used[argmin] = 1;
  291.     return argmin;
  292. }
  293.