home *** CD-ROM | disk | FTP | other *** search
/ PDA Software Library / pdasoftwarelib.iso / PSION / MISC / READER / ZVR.ZIP / ZVR.C < prev    next >
Encoding:
C/C++ Source or Header  |  1995-04-11  |  17.7 KB  |  770 lines

  1. /*
  2. ** Really mindless text compression program.
  3. **
  4. ** The intended use of the compression is to be able to fit
  5. ** E-text books (Gutenberg, OBI, Wiretap) into a smaller space
  6. ** so that they can be read on a machine with very limited store,
  7. ** such as a handheld computer.  One implication of this is that
  8. ** the form of compression does not need to be completely lossless
  9. ** as long as the result is still readable.
  10. **
  11. ** This program assumes a linear address space at least large enough
  12. ** to load the whole text.  One implication of this is that it won't
  13. ** be usable as a simple DOS program, but the alternative was to spend
  14. ** more time on this than I felt I could afford.
  15. */
  16. #include <stdlib.h>
  17. #include <string.h>
  18. #include <stdio.h>
  19. #include <assert.h>
  20.  
  21. #define FILTER                 /* don't preprocess text if this is      */
  22.                                /* not defined                           */
  23.                                /* this should give LOSSLESS compression */
  24.                                /* useful mainly for testing purposes    */
  25.  
  26. #define NEARLY 10              /* less than this is "nearly" unused */
  27.  
  28. #define GRAM 2                 /* size of strings to scan for */
  29. #define GRAMS 4000             /* max size of dictionary of scanned strings */
  30.  
  31. #define LLIM 250               /* max size of uncompressed line in file */
  32.  
  33. #define FALSE 0
  34. #define TRUE 1
  35.  
  36. #define NL '\n'
  37. #define CR '\r'
  38.  
  39. static unsigned long character_count[256];
  40.  
  41. /*
  42. ** definition
  43. **
  44. ** This is a table of definitions for the 256 possible character values.
  45. ** Note that character 0 is never used for anything, in order to avoid
  46. ** C string termination problems.
  47. **
  48. ** For other characters, the table entry is a pointer to a heap string
  49. ** which is what that character would expand to if it appeared in the
  50. ** compressed string.
  51. **
  52. ** Note that this is NOT a recursive concept; the definition is a flattened
  53. ** string of characters.  This, if the character "q" only appears before
  54. ** "u" and is chosen as symbol "x", then the definition of "x" will be
  55. ** "qu" and "q" itself may then be redefined as something else later on.
  56. */
  57. static unsigned char *definition[256];
  58.  
  59. /*
  60. ** Text storage
  61. **
  62. ** "original_size" is the size, in characters, of the original file.
  63. ** "text" is a pointer to a heap area of a little bigger than this size,
  64. ** so that it can be terminated by a couple of special characters and
  65. ** a zero if required.
  66. ** "current_size" is the number of characters in "text" which are
  67. ** currently valid.
  68. */
  69. static size_t original_size;
  70. static size_t current_size;
  71. static unsigned char *text;
  72.  
  73. /*
  74. ** abandon
  75. **
  76. ** Single point of exit from the program in the event of problems.
  77. */
  78. static void abandon ( const char *s )
  79. {
  80.    fprintf(stderr, "Abandon: %s\n", s);
  81.    exit(EXIT_FAILURE);
  82. }
  83.  
  84. /*
  85. ** process_char
  86. **
  87. ** Called once for each character in the input file.  This is a state
  88. ** machine which weeds out things like redundant white space and
  89. ** unwanted hyphenation.
  90. */
  91. static unsigned char *pp;   /* pointer through which process_char writes */
  92.  
  93. #if defined(FILTER)
  94. static void process_char ( unsigned char c )
  95. {
  96.    static enum state {
  97.       END_PARA,          /* have just seen end of a paragraph         */
  98.       END_LINE,          /* have just seen end of a line              */
  99.       IN_WORD,           /* we are inside a word                      */
  100.       IN_LINE,           /* inside a line, but not inside a word      */
  101.       PEND_SPACE,        /* in white space                            */
  102.       PEND_HYPHEN,       /* just seen a hyphen, may be at end of word */
  103.       PEND_HYPHEN_NL     /* floop-<NL> seen                           */
  104.    } state = END_PARA;
  105.  
  106.    switch (state) {
  107.  
  108.    line_ended:
  109.    case END_LINE:
  110.       if (c == NL) {
  111.      /*
  112.      ** If we see a second newline after the end of an
  113.      ** ordinary line, we have come to the end of the
  114.      ** paragraph.  Issue the second newline and move
  115.      ** into the END_PARA state.
  116.      */
  117.      *pp++ = c;
  118.      state = END_PARA;
  119.       } else if (c == ' ') {
  120.      /*
  121.      ** If we see a leading space after a newline, we have
  122.      ** see the _other_ kind of paragraph-starting convention,
  123.      ** and we must change it to the first kind.
  124.      */
  125.      *pp++ = NL;
  126.      state = END_PARA;
  127.       } else if (isalpha(c)) {
  128.      *pp++ = c;
  129.      state = IN_WORD;
  130.       } else {
  131.      *pp++ = c;
  132.      state = IN_LINE;
  133.       }
  134.       break;
  135.  
  136.    case END_PARA:
  137.       if (c == ' ') {
  138.      /*
  139.      ** Ignore spaces at this point; we know we are at the end of
  140.      ** a paragraph already.
  141.      */
  142.       } else if (c == NL) {
  143.      /*
  144.      ** Ignore extra blank lines
  145.      */
  146.       } else {
  147.      /*
  148.      ** Something interesting: consider in line context
  149.      */
  150.      goto in_line;
  151.       }
  152.       break;
  153.  
  154.    in_line:
  155.    case IN_LINE:
  156.       state = IN_LINE;
  157.       if (c == ' ') {
  158.      state = PEND_SPACE;
  159.       } else if (c == NL) {
  160.      *pp++ = NL;
  161.      state = END_LINE;
  162.       } else if (isalpha(c)) {
  163.      *pp++ = c;
  164.      state = IN_WORD;
  165.       } else {
  166.      *pp++ = c;
  167.       }
  168.       break;
  169.  
  170.    case IN_WORD:
  171.       if (isalpha(c)) {
  172.      *pp++ = c;
  173.       } else if (c == '-') {
  174.      state = PEND_HYPHEN;
  175.       } else {
  176.      goto in_line;
  177.       }
  178.       break;
  179.  
  180.    case PEND_HYPHEN:
  181.       if (isalpha(c)) { /* hyphen within a word */
  182.      *pp++ = '-';
  183.      *pp++ = c;
  184.      state = IN_WORD;
  185.       } else if (c == ' ') {
  186.      /* absorb spaces after in-word hyphens */
  187.       } else if (c == NL) {
  188.      state = PEND_HYPHEN_NL;
  189.       } else {
  190.      *pp++ = '-'; /* flush hyphen */
  191.          goto in_line;
  192.       }
  193.       break;
  194.  
  195.    case PEND_HYPHEN_NL:
  196.       if (isalpha(c)) {
  197.      /*
  198.      ** We have seen a <alpha><-><wsp><NL><wsp><alpha>
  199.      ** sequence in a word.  Drop the middle of it and
  200.      ** join the two lines together, which will also
  201.      ** join the two parts of the word together.
  202.      */
  203.      *pp++ = c;
  204.      state = IN_WORD;
  205.       } else if (c == ' ') {
  206.      /*
  207.      ** Absorb spaces at beginning of lines like these
  208.      */
  209.       } else {
  210.      *pp++ = '-';
  211.      *pp++ = NL;
  212.      state = END_LINE;
  213.      goto line_ended;
  214.       }
  215.       break;
  216.  
  217.    case PEND_SPACE:
  218.       if (c == ' ') {
  219.      /* ignore multiple white space */
  220.       } else if (c == NL) {
  221.      /*
  222.      ** White space before line end: take as line end.
  223.      */
  224.      *pp++ = NL;
  225.      state = END_LINE;
  226.       } else {
  227.      *pp++ = ' ';
  228.      goto in_line;
  229.       }
  230.       break;
  231.  
  232.    default:
  233.       fprintf(stderr, "state: %d character: %d\n", state, c);
  234.       abandon("process state machine failure");
  235.    }
  236. }
  237. #endif /* FILTER */
  238.  
  239. static load_file(FILE *fin)
  240. {
  241.    int c;
  242.  
  243.    /*
  244.    ** Work out the size of the file by reading it all in, character
  245.    ** at a time.  Slow but sure.
  246.    */
  247.    original_size = 0;
  248.    for (;;) {
  249.       int c = fgetc(fin);
  250.       if (c == EOF) break;
  251.       original_size++;
  252.    }
  253.    printf("original size: %ld characters\n", (long)original_size);
  254.  
  255.    /*
  256.    ** Allocate some space for the file...
  257.    */
  258.    text = malloc(original_size)+10;
  259.    if (!text) abandon("could not allocate buffer for text");
  260.  
  261.    /*
  262.    ** Reset the file pointer to the start and load the file in.
  263.    */
  264.    fseek(fin, 0, SEEK_SET);
  265.    pp = text;
  266.    for (;;) {
  267.       int c = fgetc(fin);
  268.       if (c == EOF) break;
  269.       #if defined(FILTER)
  270.          process_char(c);
  271.       #else
  272.          *pp++ = c;
  273.       #endif
  274.    }
  275.  
  276.    /*
  277.    ** Purge state machine if we have one.
  278.    */
  279.    #if defined(FILTER)
  280.       process_char(NL);
  281.       process_char(NL);
  282.       process_char(NL);
  283.    #endif
  284.    current_size = pp - text;
  285. }
  286.  
  287. /*
  288. ** pchar
  289. **
  290. ** Prints a character in such a way that it is always readable,
  291. ** if necessary hexifying it.
  292. */
  293. static void pchar (int n)
  294. {
  295.    if (isprint(n)) {
  296.       putchar(n);
  297.    } else {
  298.       printf("<%02X>", n);
  299.    }
  300. }
  301.  
  302. /*
  303. ** pstring
  304. **
  305. ** Prints a given string "safely" through pchar.
  306. */
  307. static void pstring ( const unsigned char *s )
  308. {
  309.    while (*s) pchar(*s++);
  310. }
  311.  
  312. static void show_nearlies(void)
  313. {
  314.    int nearlies;
  315.    int c;
  316.    for (c=1, nearlies=0; c<256; c++) {
  317.       int count = character_count[c];
  318.       if (count && (count<NEARLY)) nearlies++;
  319.    }
  320.    printf("nearly empty character slots: %d\n", nearlies);
  321.    if (nearlies) {
  322.       printf("   ");
  323.       for (c=1; c<256; c++) {
  324.          if (character_count[c] == 0) continue;
  325.          if (character_count[c] < NEARLY) pchar(c);
  326.       }
  327.       putchar(NL);
  328.    }
  329. }
  330.  
  331. static int count_characters(void)
  332. {
  333.    int c, empties;
  334.    unsigned char *p = text;
  335.  
  336.    /*
  337.    ** First, zero the count array.
  338.    */
  339.    for (c=1; c<256; c++)
  340.       character_count[c] = 0;
  341.  
  342.    /*
  343.    ** Make sure we don't by accident use anything as a symbol
  344.    ** that the Psion IOREAD function will regard as significant.
  345.    **
  346.    ** (1000 is large enough to prevent these turning up as "nearlies").
  347.    */
  348.    character_count[26] = 1000;
  349.    character_count[NL] = 1000;
  350.    character_count[CR] = 1000;
  351.  
  352.    while (p != (text+current_size)) {
  353.       character_count[*p]++;
  354.       p++;
  355.    }
  356.  
  357.    for (c=1, empties=0; c<256; c++) {
  358.       int count = character_count[c];
  359.       if (count == 0) empties++;
  360.    }
  361.  
  362.    printf("empty character slots: %d\n", empties);
  363.  
  364.    return empties;
  365. }
  366.  
  367. struct gram {
  368.    char ch[GRAM];
  369.    unsigned long nrefs;
  370. };
  371.  
  372. static struct gram grams[GRAMS];
  373. static int cur_grams;
  374. static unsigned long dropped_grams;
  375.  
  376. static void pgram ( const struct gram *g )
  377. {
  378.    int i;
  379.    for (i=0; i<GRAM; i++) pchar(g->ch[i]);
  380. }
  381.  
  382. static int sort_nrefs ( const void *L, const void *R )
  383. {
  384.    const struct gram *LL = L;
  385.    const struct gram *RR = R;
  386.    if (LL->nrefs < RR->nrefs) return -1;
  387.    if (LL->nrefs > RR->nrefs) return 1;
  388.    return 0;
  389. }
  390.  
  391. static int sort_grams ( const void *L, const void *R )
  392. {
  393.    const struct gram *LL = L;
  394.    const struct gram *RR = R;
  395.    return strncmp(LL->ch, RR->ch, GRAM);
  396. }
  397.  
  398. static void count_gram ( const char *g )
  399. {
  400.    struct gram gram;
  401.    struct gram *q;
  402.    memcpy(gram.ch, g, GRAM);
  403.    q = bsearch(&gram, grams, cur_grams, sizeof(struct gram), sort_grams);
  404.    if (q) {
  405.       q->nrefs++;
  406.    } else if (cur_grams < GRAMS) {
  407.       /*
  408.       ** A gram we haven't seen before, but which we do have room
  409.       ** for in the table.
  410.       */
  411.       gram.nrefs = 1;
  412.       #if 0
  413.          /*
  414.      ** add this gram in at the end of the table
  415.      */
  416.      grams[cur_grams] = gram;
  417.       #else
  418.          /*
  419.      ** Add this gram in at the start of the table.
  420.      ** This is likely to be statistically close to where it
  421.      ** will be going, particularly if it is a late arrival.
  422.      */
  423.          if (cur_grams) memmove(grams+1, grams, cur_grams*sizeof(struct gram));
  424.          grams[0] = gram;
  425.       #endif
  426.       cur_grams++;
  427.       qsort(grams, cur_grams, sizeof(struct gram), sort_grams);
  428.    } else {
  429.       dropped_grams++;
  430.    }
  431. }
  432.  
  433. /*
  434. ** valid_gram
  435. **
  436. ** True if the string is an allowed n-gram.  False if it
  437. ** contains NL and is therefore prohibited.
  438. */
  439. static int valid_gram ( const unsigned char *p )
  440. {
  441.    int i;
  442.    for (i=0; i<GRAM; i++)
  443.       if (*p++ == NL) return FALSE;
  444.    return TRUE;
  445. }
  446.  
  447. /*
  448. ** count_grams
  449. **
  450. ** Run through the current text counting each n-gram
  451. ** as we go.
  452. */
  453. static void count_grams(void)
  454. {
  455.    char *p = text;
  456.    char *plim = text+current_size-GRAM+1;
  457.    dropped_grams = 0;
  458.    while (p != plim) {
  459.       if (valid_gram(p))
  460.      count_gram(p);
  461.       p++;
  462.    }
  463. }
  464.  
  465. static void reset_grams(void)
  466. {
  467.    int cut = cur_grams/100;
  468.    int i;
  469.    if (cut) {
  470.       memmove(grams, grams+cut, (cur_grams-cut)*sizeof(struct gram));
  471.       cur_grams -= cut;
  472.    }
  473.    for (i=0; i<cur_grams; i++)
  474.       grams[i].nrefs = 0;
  475. }
  476.  
  477. static void replace_gram(int gramno, struct gram *g)
  478. {
  479.    char *from = text;
  480.    char *to = text;
  481.    char *org_limit = text + current_size;
  482.    char *limit = text+current_size-GRAM+1;
  483.    current_size = 0;
  484.    while (from < limit) {
  485.       if (!strncmp(from, g->ch, GRAM)) {
  486.      *to++ = gramno;
  487.      from += GRAM;
  488.       } else {
  489.      *to++ = *from++;
  490.       }
  491.       current_size++;
  492.    }
  493.    while (from != org_limit) {
  494.       *to++ = *from++;
  495.       current_size++;
  496.    }
  497. }
  498.  
  499. /*
  500. ** replace_string
  501. **
  502. ** Replace an arbitrary string with a shorter string replacement
  503. ** throughout the current version of the text.
  504. */
  505. static int replace_string ( const unsigned char *s,
  506.                const unsigned char *r )
  507. {
  508.    int n = 0;
  509.    unsigned char *beg = text;
  510.    int rlen = strlen(r);
  511.    int cut = strlen(s)-strlen(r);  /* number of characters to lose */
  512.    text[current_size] = 0; /* terminate current text */
  513.    while (beg = strstr(beg, s)) {
  514.       memcpy(beg, r, rlen); /* perform replacement */
  515.       n++;
  516.       if (cut) memmove(beg+rlen, beg+rlen+cut, strlen(beg+rlen+cut)+1);
  517.       current_size -= cut;
  518.    }
  519.    return n;
  520. }
  521.  
  522. static void expand_gram ( unsigned char *buf, struct gram *g )
  523. {
  524.    int i;
  525.    *buf = 0;
  526.    for (i=0; i<GRAM; i++)
  527.       strcat(buf, definition[g->ch[i]]);
  528. }
  529.  
  530. static void compute_grams(void)
  531. {
  532.    unsigned char ch;
  533.    for (ch=255; ch>=1; ch--) {
  534.       struct gram *g;
  535.       if (!character_count[ch]) {
  536.      /*
  537.      ** We can use this character value as a gram definition.
  538.      */
  539.      unsigned char x[100];
  540.  
  541.      printf("size now %ld (down %2.1f%%) ",
  542.         (long)current_size,
  543.         100.0*(original_size-current_size)/(double)original_size);
  544.      fflush(stdout);
  545.  
  546.      count_grams();
  547.  
  548.      qsort(grams, cur_grams, sizeof(struct gram), sort_nrefs);
  549.      g = &grams[cur_grams-1];
  550.  
  551.      printf("top %d-gram is \"", GRAM);
  552.      pgram(g);
  553.      printf("\" (ref %ld, drop %lu)\n", g->nrefs, dropped_grams);
  554.  
  555.      replace_gram(ch, g);
  556.  
  557.      expand_gram(x, g);
  558.  
  559.      reset_grams();
  560.      cur_grams--;   /* we no longer have this one */
  561.  
  562.      free(definition[ch]);
  563.      definition[ch] = strdup(x);
  564.      printf("   character value %d now expands to \"", ch);
  565.      pstring(definition[ch]);
  566.      putchar('"');
  567.      putchar(NL);
  568.       }
  569.    }
  570. }
  571.  
  572. static void dump_table ( FILE *fout )
  573. {
  574.    int ch;
  575.    for (ch=0; ch<=255; ch++) {
  576.       const unsigned char *def = definition[ch];
  577.       if (strlen(def)==1 && *def == ch) {
  578.      /*
  579.      ** If the character is defined as itself, just put out
  580.      ** a blank line.
  581.      */
  582.      fputc(NL, fout);
  583.       } else {
  584.      /*
  585.      ** Otherwise, put out the definition of the character
  586.      ** on a line.
  587.      */
  588.      fprintf(fout, "%s\n", definition[ch]);
  589.       }
  590.    }
  591. }
  592.  
  593. /*
  594. ** initialise_definitions
  595. **
  596. ** Set up the definition array with pointers to heap strings
  597. ** defining the symbol as equivalent to itself.
  598. */
  599. static void initialise_definitions(void)
  600. {
  601.    int c;
  602.    for (c=1; c<256; c++) {
  603.       unsigned char x[2];
  604.       x[0] = c; x[1] = 0;
  605.       definition[c] = strdup(x);
  606.       if (!definition[c]) abandon("can't initialise definition");
  607.    }
  608. }
  609.  
  610. /*
  611. ** optimise_lines
  612. **
  613. ** This function scans the text and re-formats all the paragraphs
  614. ** to give maximal line sizes.  The effect of this is to allow the
  615. ** compression algorithms to work slightly more effectively because
  616. ** word endings are more often seen as with a space (which can be
  617. ** involved in compression) than before (NL can not be part of
  618. ** a compression symbol).
  619. **
  620. ** Note that any such change leaves the text exactly the same
  621. ** size as it was before.
  622. */
  623. #if defined(FILTER)
  624. static void optimise_lines(void)
  625. {
  626.    unsigned char *p;
  627.  
  628.    /*
  629.    ** Terminate the current text.
  630.    */
  631.    text[current_size] = 0;
  632.  
  633.    /*
  634.    ** Phase 1
  635.    **
  636.    ** Make each paragraph (where paragraphs are defined as being
  637.    ** separated by blank lines) be a single line with spaces
  638.    ** separating words.
  639.    */
  640.    p = text;
  641.    while (p = strchr(p, NL)) {
  642.       if (p[1] == NL) {
  643.      /*
  644.      ** THIS newline is the end of the paragraph, the NEXT
  645.      ** one is the required blank line.  We don't want to
  646.      ** touch this, and THEN we want to start at the start
  647.      ** of the next paragraph.
  648.      */
  649.      p += 2;
  650.       } else if (p[1] == 0) {
  651.      /*
  652.      ** Last newline in the file.
  653.      */
  654.      break;
  655.       } else {
  656.      /*
  657.      ** Simple end of line, but not end of paragraph.
  658.      */
  659.      *p++ = ' ';
  660.       }
  661.    }
  662.  
  663.    /*
  664.    ** Phase 2
  665.    **
  666.    ** For each paragraph/line in the file, reduce it to lines shorter
  667.    ** than or equal to LLIM characters by converting spaces to NLs.
  668.    */
  669.    p = text;
  670.    while (*p) {
  671.       unsigned char *end; /* points to end of this line (NL character) */
  672.  
  673.       /*
  674.       ** "p" points to the start of the current line.
  675.       ** If this is a blank line, just skip over it.
  676.       */
  677.       if (*p == NL) {
  678.      p++;
  679.      continue;
  680.       }
  681.  
  682.       /*
  683.       ** We are at the start of a non-empty line.
  684.       ** Locate it's NL character and thus figure out
  685.       ** how long the line is.
  686.       */
  687.       end = strchr(p, NL);
  688.  
  689.       /*
  690.       ** Reduce this line, while it is still too large.
  691.       */
  692.       while ( (end-p) > LLIM ) {
  693.      unsigned char *brk = p+LLIM;   /* candidate breakpoint */
  694.      while (*brk != ' ') brk--;     /* run back to previous space */
  695.      *brk = NL;                     /* overwrite with newline */
  696.      p = brk+1;                     /* new beginning of line */
  697.       }
  698.  
  699.       p = end+1;                        /* move to start of next line */
  700.    }
  701. }
  702. #endif
  703.  
  704. /*
  705. ** main
  706. */
  707. int main(int argc, char *argv[])
  708. {
  709.    FILE *fin, *fout;
  710.    int n;
  711.  
  712.    if (argc != 3) abandon("two arguments (in, out) required");
  713.  
  714.    fin = fopen(argv[1], "r");
  715.    if (!fin) abandon("could not open input file");
  716.    
  717.    load_file(fin);
  718.    fclose(fin);
  719.  
  720.    /*
  721.    ** Perform some text replacements.
  722.    **
  723.    ** For "Terminal Compromise":
  724.    **   ^[ ^H ^\   ->  e-grave
  725.    **   ^[ ^B ^\   ->  e-acute
  726.    **   <130>      ->  e-acute
  727.    **
  728.    ** General textual:
  729.    **   Spaced out ellipsis ". . ." to "..."
  730.    **   Compact lines of stars
  731.    */
  732.    #if defined(FILTER)
  733.       n = replace_string("\x1B\x08\x1C", "\x8A");
  734.       if (n) printf("e-grave replacements: %d\n", n);
  735.       n = replace_string("\x1B\x02\x1C", "\x82");
  736.       n += replace_string("<130>", "\x82");
  737.       if (n) printf("e-acute replacements: %d\n", n);
  738.       n = replace_string(". .", "..");
  739.       if (n) printf("ellipsis compressions: %d\n", n);
  740.       n = replace_string("* *", "**");
  741.       if (n) printf("star compressions: %d\n", n);
  742.    #endif
  743.  
  744.    /*
  745.    ** Reformat paragraphs
  746.    */
  747.    #if defined(FILTER)
  748.       optimise_lines();
  749.    #endif
  750.  
  751.    initialise_definitions();
  752.  
  753.    while (count_characters())
  754.       compute_grams();
  755.  
  756.    show_nearlies();
  757.  
  758.    /*
  759.    ** Create the output file
  760.    */
  761.    fout = fopen(argv[2], "w");
  762.    if (!fout) abandon("could not open output file");
  763.    definition[0] = "!!Compressed!!";
  764.    dump_table(fout);
  765.    fwrite(text, 1, current_size, fout);
  766.    fclose(fout);
  767.  
  768.    return EXIT_SUCCESS;
  769. }
  770.