home *** CD-ROM | disk | FTP | other *** search
/ World of Shareware - Software Farm 2 / wosw_2.zip / wosw_2 / PRINTING / DVIPS386.ZIP / REPACK.C < prev    next >
C/C++ Source or Header  |  1991-11-03  |  15KB  |  478 lines
  1. /*
  2.  *   Compressed TeX fonts in PostScript.  Copyright (C) 1989
  3.  *   by Radical Eye Software.  All Rights Reserved.
  4.  *   (Slight mods by Don Knuth in December 89.)
  5.  */
  6. #include "structures.h" /* The copyright notice in that file is included too! */
  7. #ifdef DEBUG
  8. extern integer debug_flag;
  9. #endif /* DEBUG */
  10.  
  11. /*   Given a raster that has been unpacked from PK format,
  12.  *   we compress it by another scheme that is suitable for
  13.  *   a PostScript-oriented unpacking. We write instructions for
  14.  *   a little interpreter whose one-byte instructions have the form
  15.  *   18*opcode+parameter. The interpreter forms each row based
  16.  *   on simple transformations to the previous row. */
  17.  
  18. #define MAXOUT (18)
  19. #define CMD(n) (MAXOUT*(n))
  20. #define ADVXCHG1 CMD(0)
  21. #define ADVXCHG1END CMD(1)
  22. #define CHGX CMD(2)-1
  23. #define CHGXEND CMD(3)-1
  24. #define ADVXLSH CMD(4)
  25. #define ADVXLSHEND CMD(5)
  26. #define ADVXRSH CMD(6)
  27. #define ADVXRSHEND CMD(7)
  28. #define ADVX CMD(8)-1
  29. #define REPX CMD(9)-1
  30. #define SETX CMD(10)-1
  31. #define CLRX CMD(11)-1
  32. #define ADVXCHG2 CMD(12)
  33. #define ADVXCHG2END CMD(13)
  34. #define END CMD(14)
  35.  
  36. /* extern char *malloc() ; */
  37. extern void* malloc(unsigned) ;
  38. /* extern free() ; */
  39. extern void free(void*) ;
  40. extern void error() ;
  41. extern long getlong() ;
  42. extern long unpack() ;
  43.  
  44. static int rowlength = 0 ;
  45. static unsigned char *specdata ;
  46. static long tslen = 0 ;
  47. static unsigned char *tempstore, *tsp, *tsend ;
  48.  
  49. void putlong(a, i)
  50. register char *a ;
  51. long i ;
  52. {
  53.    a[0] = i >> 24 ;
  54.    a[1] = i >> 16 ;
  55.    a[2] = i >> 8 ;
  56.    a[3] = i ;
  57. }
  58.  
  59. long getlong(a)
  60. register unsigned char *a ;
  61. {
  62.    return ((((((a[0] << 8L) + a[1]) << 8L) + a[2]) << 8L) + a[3]) ;
  63. }
  64.  
  65. /* First, a routine that appends one byte to the compressed output. */
  66.  
  67. #define addtse(n) {lcm=tsp-tempstore;addts(n);} /* mark END option position */
  68.  
  69. static void addts(what)
  70. register unsigned char what ;
  71. {
  72.    register unsigned char *p, *q ;
  73.  
  74.    if (tsp >= tsend) {
  75.       if (tempstore == NULL) {
  76.          tslen = 4096 ;
  77.          tempstore = (unsigned char *)malloc((unsigned)tslen) ;
  78.          if (tempstore == NULL)
  79.             error("! out of memory") ;
  80.          tsp = tempstore ;
  81.       } else {
  82.          tslen = 2 * tslen ;
  83.          tsp = (unsigned char *)malloc((unsigned)tslen) ;
  84.          if (tsp == NULL)
  85.             error("! out of memory") ;
  86.          for (p=tempstore, q=tsp; p<tsend; p++, q++)
  87.             *q = *p ;
  88.          free((char *)tempstore) ;
  89.          tempstore = tsp ;
  90.          tsp = q ;
  91.       }
  92.       tsend = tempstore + tslen ;
  93.    }
  94.    *tsp++ = what ;
  95. }
  96.  
  97. /* Next, a routine that discovers how to do the compression. */
  98.  
  99. #define rsh(a,b) ( ((a)==0) ? ((b)==128) : ( ((a)==255) ? ((b)==127) :\
  100.                                     ((b)==(((a)>>1)|((a)&128))) ))
  101. #define lsh(a,b) ( ((a)==0) ? ((b)==1) : ( ((a)==255) ? ((b)==254) :\
  102.                                     ((b)==((((a)<<1)&255)|((a)&1))) ))
  103. #define DIFFERENT (1)
  104. #define LSHPOSSIB (2)
  105. #define RSHPOSSIB (4)
  106. #define BLKPOSSIB (8)
  107. #define WHTPOSSIB (16)
  108. #define ENDROW (32)
  109. #define NOPOSSIB(n) ((n&(LSHPOSSIB|RSHPOSSIB|BLKPOSSIB|WHTPOSSIB))==0)
  110. #define NOSHIFT(n) ((n&(LSHPOSSIB|RSHPOSSIB))==0)
  111. /*
  112.  *   Our input bytes are packed to the 16-bit word.  On output,
  113.  *   they're packed to bytes. Thus, we may have to skip a byte at
  114.  *   the end of each row.
  115.  */
  116. void dochar(from, width, height)
  117. unsigned char *from ;
  118. short width, height ; /* in bytes */
  119. {
  120.    register int i ;
  121.    register unsigned char *f, *t, *d ;
  122.    register unsigned char *e ;
  123.    register int accum ;
  124.    int j, k ;
  125.    int diffrow ;
  126.    int repeatcount ;
  127.    int lit, pos, cmd = 0 ;
  128.    long lcm ;
  129.    int widthc ;
  130.  
  131.    widthc = width + (width & 1) ; /* halfword correction */
  132.    lcm = -1 ;
  133.    if (widthc > rowlength) {
  134.       if (rowlength)
  135.          free((char *)specdata) ;
  136.       rowlength = widthc ;
  137.       specdata = (unsigned char *)malloc((unsigned)(rowlength + 15)) ;
  138.       if (specdata == NULL)
  139.          error("! out of memory") ;
  140.    }
  141.    for (i= -15, t=specdata; i<=widthc; i++, t++)
  142.       *t = 0 ;
  143.    repeatcount = 0 ;
  144.    f = specdata + 2 ;
  145.    for (j=0; j<height; j++, f = from, from += widthc) {
  146.       diffrow = 0 ;
  147.       for (i=0, t=from, d=specdata; i<width; i++, f++, t++, d++) {
  148.          if (*f == *t) {
  149.             if (*t == 0)
  150.                *d = WHTPOSSIB ;
  151.             else if (*t == 255)
  152.                *d = BLKPOSSIB ;
  153.             else
  154.                *d = 0 ;
  155.          } else {
  156.             accum = DIFFERENT ;
  157.             if (rsh(*f, *t))
  158.                accum |= RSHPOSSIB ;
  159.             else if (lsh(*f, *t))
  160.                accum |= LSHPOSSIB ;
  161.             if (*t == 0)
  162.                accum |= WHTPOSSIB ;
  163.             else if (*t == 255)
  164.                accum |= BLKPOSSIB ;
  165.             *d = accum ;
  166.             diffrow++ ;
  167.          }
  168.       } /* end 'for i' */
  169.       *d = ENDROW ;
  170.       if (diffrow == 0) {
  171.          repeatcount++ ;
  172.       } else {
  173.          if (repeatcount) {
  174.             while (repeatcount > MAXOUT) {
  175.                addts((unsigned char)(REPX+MAXOUT)) ;
  176.                repeatcount -= MAXOUT ;
  177.             }
  178.             addts((unsigned char)(REPX+repeatcount)) ;
  179.             repeatcount = 0 ;
  180.          }
  181.          pos = 0 ;
  182.          for (i=0, d=specdata, f=t-width; i<width;) {
  183.             if ((*d & DIFFERENT) == 0) {
  184.                i++ ;
  185.                d++ ;
  186.                f++ ;
  187.             } else {
  188.                accum = 0 ;
  189.                if (pos != i)
  190.                   lit = NOSHIFT(*d) ;
  191.                else /* N.B.: 'lit' does not imply literate programming here */
  192.                   lit = NOPOSSIB(*d) ;
  193.                for (e=d; ;e++) {
  194.                   if (NOPOSSIB(*e))
  195.                      lit = 1 ;
  196.                   if ((*e & DIFFERENT) == 0)
  197.                      break ;
  198.                   if ((*e & WHTPOSSIB) &&
  199.                       (e[1] & WHTPOSSIB)) {
  200.                      while (*e & WHTPOSSIB) {
  201.                         e++ ;
  202.                         accum++ ;
  203.                      }
  204.                      cmd = CLRX ;
  205.                      e -= accum ;
  206.                      break ;
  207.                   } else if ((*e & BLKPOSSIB) &&
  208.                       (e[1] & BLKPOSSIB)) {
  209.                      while (*e & BLKPOSSIB) {
  210.                         e++ ;
  211.                         accum++ ;
  212.                      }
  213.                      cmd = SETX ;
  214.                      e -= accum ;
  215.                      break ;
  216.                   }
  217.                } /* end 'for e'; d pts to first bad byte, e to next good one */
  218.                while (i - pos > MAXOUT) {
  219.                   addts((unsigned char)(ADVX+MAXOUT)) ;
  220.                   pos += MAXOUT ;
  221.                }
  222.                if (k = (e - d)) {
  223.                   if (lit) {
  224.                      if (k > 2) {
  225.                         if (i > pos) {
  226.                            addts((unsigned char)(ADVX + i - pos)) ;
  227.                            pos = i ;
  228.                         }
  229.                         while (k > MAXOUT) {
  230.                            addts((unsigned char)(CHGX + MAXOUT)) ;
  231.                            for (k=0; k<MAXOUT; k++)
  232.                               addts((unsigned char)(*f++)) ;
  233.                            d += MAXOUT ;
  234.                            pos += MAXOUT ;
  235.                            i += MAXOUT ;
  236.                            k -= MAXOUT ;
  237.                         }
  238.                         addtse((unsigned char)(CHGX + k)) ;
  239.                         pos += k ;
  240.                         for (; d<e; d++, i++, f++)
  241.                            addts((unsigned char)(*f)) ;
  242.                      } else {
  243.                         if (k == 1) {
  244.                            if (i == pos+MAXOUT) {
  245.                               addts((unsigned char)(ADVX + MAXOUT)) ;
  246.                               pos = i ;
  247.                            }
  248.                            addtse((unsigned char)(ADVXCHG1 + i - pos)) ;
  249.                            addts((unsigned char)(*f)) ;
  250.                            i++ ;
  251.                            pos = i ;
  252.                            d++ ;
  253.                            f++ ;
  254.                         } else {
  255.                            if (i == pos+MAXOUT) {
  256.                               addts((unsigned char)(ADVX + MAXOUT)) ;
  257.                               pos = i ;
  258.                            }
  259.                            addtse((unsigned char)(ADVXCHG2 + i - pos)) ;
  260.                            addts((unsigned char)(*f)) ;
  261.                            addts((unsigned char)(f[1])) ;
  262.                            i += 2 ;
  263.                            pos = i ;
  264.                            d += 2 ;
  265.                            f += 2 ;
  266.                         }
  267.                      }
  268.                   } else {
  269.                      while (e > d) {
  270.                         if (*d & LSHPOSSIB) {
  271.                            if (i == pos+MAXOUT) {
  272.                               addts((unsigned char)(ADVX + MAXOUT)) ;
  273.                               pos = i ;
  274.                            }
  275.                            addtse((unsigned char)(ADVXLSH + i - pos)) ;
  276.                         } else if (*d & RSHPOSSIB) {
  277.                            if (i == pos+MAXOUT) {
  278.                               addts((unsigned char)(ADVX + MAXOUT)) ;
  279.                               pos = i ;
  280.                            }
  281.                            addtse((unsigned char)(ADVXRSH + i - pos)) ;
  282.                         } else if (*d & WHTPOSSIB) { /* i==pos */
  283.                            addts((unsigned char)(CLRX + 1)) ; lcm = -1 ;
  284.                         } else if (*d & BLKPOSSIB) { /* i==pos */
  285.                            addts((unsigned char)(SETX + 1)) ; lcm = -1 ;
  286.                         } else
  287.                            error("! bug") ; /* why wasn't lit true? */
  288.                         d++ ;
  289.                         f++ ;
  290.                         i++ ;
  291.                         pos = i ;
  292.                      } /* end 'while e>d' */
  293.                   }
  294.                } /* end 'if e>d' */
  295.                if (accum > 0) {
  296.                   if (i > pos) {
  297.                      addts((unsigned char)(ADVX + i - pos)) ;
  298.                      pos = i ;
  299.                   }
  300.                   i += accum ;
  301.                   d += accum ;
  302.                   f += accum ;
  303.                   while (accum > MAXOUT) {
  304.                      addts((unsigned char)(cmd + MAXOUT)) ;
  305.                      accum -= MAXOUT ;
  306.                      pos += MAXOUT ;
  307.                   }
  308.                   lcm = -1 ;
  309.                   addts((unsigned char)(cmd + accum)) ;
  310.                   pos += accum ;
  311.                }
  312.             } /* end 'else DIFFERENT' */
  313.          } /* end 'for i' */
  314.          if (lcm != -1) {
  315.             tempstore[lcm] += MAXOUT ;  /* append END */
  316.             lcm = -1 ;
  317.          } else {
  318.             addts((unsigned char)(END)) ;
  319.          }
  320.       } /* end 'else rows different' */
  321. #ifdef DEBUG
  322.       if (d != specdata + width)
  323.          error("! internal inconsistency in repack") ;
  324. #endif
  325.    } /* end 'for j' */
  326.    if (repeatcount) {
  327.       while (repeatcount > MAXOUT) {
  328.          addts((unsigned char)(REPX+MAXOUT)) ;
  329.          repeatcount -= MAXOUT ;
  330.       }
  331.       addts((unsigned char)(REPX+repeatcount)) ;
  332.       repeatcount = 0 ;
  333.    }
  334. }
  335.  
  336. extern long bytesleft ;
  337. extern quarterword *raster ;
  338. static long mbytesleft ;
  339. static quarterword *mraster ;
  340.  
  341. char *
  342. makecopy(what, len, p)
  343. register unsigned char *what ;
  344. register long len ;
  345. register unsigned char *p ;
  346. {
  347.    register unsigned char *q ;
  348.  
  349.    if (p == NULL) {
  350.       if (len > 32760)
  351.          error("! oops, raster too big") ;
  352.       if (bytesleft < len) {
  353.          if (RASTERCHUNK > len) {
  354.             raster = (quarterword *)malloc((unsigned)RASTERCHUNK) ;
  355.             bytesleft = RASTERCHUNK ;
  356.          } else {
  357.             raster = (quarterword *)malloc((unsigned)len) ;
  358.             bytesleft = len ;
  359.          }
  360.          if (raster == NULL) {
  361.             error("! out of memory during allocation") ;
  362.          }
  363.       }
  364.       p = (unsigned char *)raster ;
  365.       bytesleft -= len ;
  366.       raster += len ;
  367.    }
  368.    q = p ;
  369.    while (len > 0) {
  370.       *p++ = *what++ ;
  371.       len -- ;
  372.    }
  373.    return ((char *)q) ;
  374. }
  375.  
  376. /* Now the main routine, which is called when a character is used
  377.    for the very first time. */
  378.  
  379. void repack(cp)
  380. register chardesctype *cp ;
  381. {
  382.    register long i, j ;
  383.    register unsigned char *p ;
  384.    register int width, height ;
  385.    register int wwidth ;
  386.    char startbytes ;
  387.    int smallchar ;
  388.  
  389.    p = cp->packptr ;
  390.    if (p == NULL)
  391.       error("! no raster?") ;
  392.    tsp = tempstore ;
  393.    tsend = tempstore + tslen ;
  394.    addts(*p) ; /* copy the PK flag byte */
  395.    if (*p & 4) {
  396.       if ((*p & 7) == 7) {
  397.          startbytes = 17 ;
  398.          width = getlong(p + 1) ;
  399.          height = getlong(p + 5) ;
  400.          for (i=0; i<12; i++)
  401.             addts(*++p) ;
  402.       } else {
  403.          startbytes = 9 ;
  404.          width = p[1] * 256 + p[2] ;
  405.          height = p[3] * 256 + p[4] ;
  406.          addts(*++p) ;
  407.          addts(*++p) ;
  408.          addts(*++p) ;
  409.          addts(*++p) ;
  410.       }
  411.    } else {
  412.       startbytes = 5 ;
  413.       width = p[1] ;
  414.       height = p[2] ;
  415.    }
  416.    addts(*++p) ;
  417.    addts(*++p) ;
  418.    addts(*++p) ;
  419.    addts(*++p) ;
  420.    p++ ; /* OK, p now points to beginning of the nibbles */
  421.    addts((unsigned char)0) ;
  422.    addts((unsigned char)0) ;
  423.    addts((unsigned char)0) ;
  424.    addts((unsigned char)0) ; /* leave room to stick in a new length field */
  425.    wwidth = (width + 15) / 16 ;
  426.    i = 2 * height * (long)wwidth ;
  427.    if (i <= 0)
  428.       i = 2 ;
  429.    if ((cp->flags & BIGCHAR) == 0)
  430.       smallchar = 5 ;
  431.    else
  432.       smallchar = 0 ;
  433.    i += smallchar ;
  434.    if (mbytesleft < i) {
  435.       if (mbytesleft >= RASTERCHUNK)
  436.          (void) free((char *) mraster) ;
  437.       if (RASTERCHUNK > i) {
  438.          mraster = (quarterword *)malloc((unsigned)RASTERCHUNK) ;
  439.          mbytesleft = RASTERCHUNK ;
  440.       } else {
  441.          mraster = (quarterword *)malloc((unsigned)(i + 3)) ;
  442.          mbytesleft = i ;
  443.       }
  444.       if (mraster == NULL) {
  445.          error("! out of memory during allocation") ;
  446.       }
  447.    }
  448.    while (i > 0)
  449.       mraster[--i] = 0 ;
  450.    i = startbytes + unpack(p, (halfword *)mraster, (halfword)width,
  451.                 (halfword)height,  *(cp->packptr)) ;
  452.    dochar(mraster, (width + 7) >> 3, height) ;
  453.    if (smallchar) {
  454.       addts((unsigned char)0) ;
  455.       addts((unsigned char)0) ;
  456.       addts((unsigned char)0) ;
  457.       addts((unsigned char)0) ;
  458.       addts((unsigned char)0) ;
  459.    }
  460.    j = tsp - tempstore ;
  461. #ifdef DEBUG
  462.    if (dd(D_COMPRESS))
  463. #ifdef SHORTINT
  464.         (void)fprintf(stderr,"PK %ld bytes, unpacked %ld, compressed %ld\n",
  465. #else /* ~SHORTINT */
  466.         (void)fprintf(stderr,"PK %d bytes, unpacked %d, compressed %d\n",
  467. #endif /* ~SHORTINT */
  468.             i-(long)startbytes, ((width+7L)/8)*height, j-(long)startbytes-4) ;
  469. #endif /* DEBUG */
  470.    if ( i < j )
  471.       cp->packptr =
  472.               (unsigned char *)makecopy(tempstore, j, (unsigned char *)0) ;
  473.    else
  474.       makecopy(tempstore, j, (unsigned char *)cp->packptr) ;
  475.    putlong((char *)(cp->packptr+startbytes), j-startbytes-4-smallchar) ;
  476.    cp->flags |= REPACKED ;
  477. }
  478.