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