Back to index

tetex-bin  3.0
repack.c
Go to the documentation of this file.
00001 /*
00002  *   Compressed TeX fonts in PostScript.
00003  *   By Radical Eye Software.
00004  *   (Slight mods by Don Knuth in December 89.)
00005  */
00006 #include "dvips.h" /* The copyright notice in that file is included too! */
00007 #ifdef DEBUG
00008 extern integer debug_flag;
00009 #endif /* DEBUG */
00010 
00011 /*   Given a raster that has been unpacked from PK format,
00012  *   we compress it by another scheme that is suitable for
00013  *   a PostScript-oriented unpacking. We write instructions for
00014  *   a little interpreter whose one-byte instructions have the form
00015  *   18*opcode+parameter. The interpreter forms each row based
00016  *   on simple transformations to the previous row. */
00017 
00018 #define MAXOUT (18)
00019 #define CMD(n) (MAXOUT*(n))
00020 #define ADVXCHG1 CMD(0)
00021 #define ADVXCHG1END CMD(1)
00022 #define CHGX CMD(2)-1
00023 #define CHGXEND CMD(3)-1
00024 #define ADVXLSH CMD(4)
00025 #define ADVXLSHEND CMD(5)
00026 #define ADVXRSH CMD(6)
00027 #define ADVXRSHEND CMD(7)
00028 #define ADVX CMD(8)-1
00029 #define REPX CMD(9)-1
00030 #define SETX CMD(10)-1
00031 #define CLRX CMD(11)-1
00032 #define ADVXCHG2 CMD(12)
00033 #define ADVXCHG2END CMD(13)
00034 #define END CMD(14)
00035 
00036 #include "protos.h"
00037 
00038 static int rowlength = -1 ;
00039 static unsigned char *specdata ;
00040 static long tslen = 0 ;
00041 static unsigned char *tempstore, *tsp, *tsend ;
00042 
00043 void putlong P2C(register char *, a, long, i)
00044 {
00045    a[0] = i >> 24 ;
00046    a[1] = i >> 16 ;
00047    a[2] = i >> 8 ;
00048    a[3] = i ;
00049 }
00050 
00051 long getlong P1C(register unsigned char *, a)
00052 {
00053    return ((((((a[0] << 8L) + a[1]) << 8L) + a[2]) << 8L) + a[3]) ;
00054 }
00055 
00056 /* First, a routine that appends one byte to the compressed output. */
00057 
00058 #define addtse(n) {lcm=tsp-tempstore;addts(n);} /* mark END option position */
00059 
00060 static void addts P1C(register unsigned char, what)
00061 {
00062    register unsigned char *p, *q ;
00063 
00064    if (tsp >= tsend) {
00065       if (tempstore == NULL) {
00066          tslen = 2020 ;
00067          tempstore = (unsigned char *)mymalloc((integer)tslen) ;
00068          tsp = tempstore ;
00069       } else {
00070          tslen = 2 * tslen ;
00071          tsp = (unsigned char *)mymalloc((integer)tslen) ;
00072          for (p=tempstore, q=tsp; p<tsend; p++, q++)
00073             *q = *p ;
00074          free((char *)tempstore) ;
00075          tempstore = tsp ;
00076          tsp = q ;
00077       }
00078       tsend = tempstore + tslen ;
00079    }
00080    *tsp++ = what ;
00081 }
00082 
00083 /* Next, a routine that discovers how to do the compression. */
00084 
00085 #define rsh(a,b) ( ((a)==0) ? ((b)==128) : ( ((a)==255) ? ((b)==127) :\
00086                                     ((b)==(((a)>>1)|((a)&128))) ))
00087 #define lsh(a,b) ( ((a)==0) ? ((b)==1) : ( ((a)==255) ? ((b)==254) :\
00088                                     ((b)==((((a)<<1)&255)|((a)&1))) ))
00089 #define DIFFERENT (1)
00090 #define LSHPOSSIB (2)
00091 #define RSHPOSSIB (4)
00092 #define BLKPOSSIB (8)
00093 #define WHTPOSSIB (16)
00094 #define ENDROW (32)
00095 #define NOPOSSIB(n) ((n&(LSHPOSSIB|RSHPOSSIB|BLKPOSSIB|WHTPOSSIB))==0)
00096 #define NOSHIFT(n) ((n&(LSHPOSSIB|RSHPOSSIB))==0)
00097 /*
00098  *   Our input bytes are packed to the 16-bit word.  On output,
00099  *   they're packed to bytes. Thus, we may have to skip a byte at
00100  *   the end of each row.
00101  */
00102 void dochar P3C(unsigned char *, from, short, width, short, height)
00103 {
00104    register int i ;
00105    register unsigned char *f, *t, *d ;
00106    register unsigned char *e ;
00107    register int accum ;
00108    int j, k, kk ;
00109    int diffrow ;
00110    int repeatcount ;
00111    int lit, pos, cmd = 0 ;
00112    long lcm ;
00113    int widthc ;
00114 
00115    widthc = width + (width & 1) ; /* halfword correction */
00116    lcm = -1 ;
00117    if (widthc > rowlength) {
00118       if (rowlength > 0)
00119          free((char *)specdata) ;
00120       rowlength = widthc + 30 ;
00121       specdata = (unsigned char *)mymalloc((integer)(rowlength + 15)) ;
00122    }
00123    for (i= -15, t=specdata; i<=widthc; i++, t++)
00124       *t = 0 ;
00125    repeatcount = 0 ;
00126    f = specdata + 2 ;
00127    for (j=0; j<height; j++, f = from, from += widthc) {
00128       diffrow = 0 ;
00129       for (i=0, t=from, d=specdata; i<width; i++, f++, t++, d++) {
00130          if (*f == *t) {
00131             if (*t == 0)
00132                *d = WHTPOSSIB ;
00133             else if (*t == 255)
00134                *d = BLKPOSSIB ;
00135             else
00136                *d = 0 ;
00137          } else {
00138             accum = DIFFERENT ;
00139             if (rsh(*f, *t))
00140                accum |= RSHPOSSIB ;
00141             else if (lsh(*f, *t))
00142                accum |= LSHPOSSIB ;
00143             if (*t == 0)
00144                accum |= WHTPOSSIB ;
00145             else if (*t == 255)
00146                accum |= BLKPOSSIB ;
00147             *d = accum ;
00148             diffrow++ ;
00149          }
00150       } /* end 'for i' */
00151       *d = ENDROW ;
00152       if (diffrow == 0) {
00153          repeatcount++ ;
00154       } else {
00155          if (repeatcount) {
00156             while (repeatcount > MAXOUT) {
00157                addts((unsigned char)(REPX+MAXOUT)) ;
00158                repeatcount -= MAXOUT ;
00159             }
00160             addts((unsigned char)(REPX+repeatcount)) ;
00161             repeatcount = 0 ;
00162          }
00163          pos = 0 ;
00164          for (i=0, d=specdata, f=t-width; i<width;) {
00165             if ((*d & DIFFERENT) == 0) {
00166                i++ ;
00167                d++ ;
00168                f++ ;
00169             } else {
00170                accum = 0 ;
00171                if (pos != i)
00172                   lit = NOSHIFT(*d) ;
00173                else /* N.B.: 'lit' does not imply literate programming here */
00174                   lit = NOPOSSIB(*d) ;
00175                for (e=d; ;e++) {
00176                   if (NOPOSSIB(*e))
00177                      lit = 1 ;
00178                   if ((*e & DIFFERENT) == 0)
00179                      break ;
00180                   if ((*e & WHTPOSSIB) &&
00181                       (e[1] & WHTPOSSIB)) {
00182                      while (*e & WHTPOSSIB) {
00183                         e++ ;
00184                         accum++ ;
00185                      }
00186                      cmd = CLRX ;
00187                      e -= accum ;
00188                      break ;
00189                   } else if ((*e & BLKPOSSIB) &&
00190                       (e[1] & BLKPOSSIB)) {
00191                      while (*e & BLKPOSSIB) {
00192                         e++ ;
00193                         accum++ ;
00194                      }
00195                      cmd = SETX ;
00196                      e -= accum ;
00197                      break ;
00198                   }
00199                } /* end 'for e'; d pts to first bad byte, e to next good one */
00200                while (i - pos > MAXOUT) {
00201                   addts((unsigned char)(ADVX+MAXOUT)) ;
00202                   pos += MAXOUT ;
00203                }
00204                if (0 != (k = (e - d))) {
00205                   if (lit) {
00206                      if (k > 2) {
00207                         if (i > pos) {
00208                            addts((unsigned char)(ADVX + i - pos)) ;
00209                            pos = i ;
00210                         }
00211                         while (k > MAXOUT) {
00212                            addts((unsigned char)(CHGX + MAXOUT)) ;
00213                            for (kk=0; kk<MAXOUT; kk++)
00214                               addts((unsigned char)(*f++)) ;
00215                            d += MAXOUT ;
00216                            pos += MAXOUT ;
00217                            i += MAXOUT ;
00218                            k -= MAXOUT ;
00219                         }
00220                         addtse((unsigned char)(CHGX + k)) ;
00221                         pos += k ;
00222                         for (; d<e; d++, i++, f++)
00223                            addts((unsigned char)(*f)) ;
00224                      } else {
00225                         if (k == 1) {
00226                            if (i == pos+MAXOUT) {
00227                               addts((unsigned char)(ADVX + MAXOUT)) ;
00228                               pos = i ;
00229                            }
00230                            addtse((unsigned char)(ADVXCHG1 + i - pos)) ;
00231                            addts((unsigned char)(*f)) ;
00232                            i++ ;
00233                            pos = i ;
00234                            d++ ;
00235                            f++ ;
00236                         } else {
00237                            if (i == pos+MAXOUT) {
00238                               addts((unsigned char)(ADVX + MAXOUT)) ;
00239                               pos = i ;
00240                            }
00241                            addtse((unsigned char)(ADVXCHG2 + i - pos)) ;
00242                            addts((unsigned char)(*f)) ;
00243                            addts((unsigned char)(f[1])) ;
00244                            i += 2 ;
00245                            pos = i ;
00246                            d += 2 ;
00247                            f += 2 ;
00248                         }
00249                      }
00250                   } else {
00251                      while (e > d) {
00252                         if (*d & LSHPOSSIB) {
00253                            if (i == pos+MAXOUT) {
00254                               addts((unsigned char)(ADVX + MAXOUT)) ;
00255                               pos = i ;
00256                            }
00257                            addtse((unsigned char)(ADVXLSH + i - pos)) ;
00258                         } else if (*d & RSHPOSSIB) {
00259                            if (i == pos+MAXOUT) {
00260                               addts((unsigned char)(ADVX + MAXOUT)) ;
00261                               pos = i ;
00262                            }
00263                            addtse((unsigned char)(ADVXRSH + i - pos)) ;
00264                         } else if (*d & WHTPOSSIB) { /* i==pos */
00265                            addts((unsigned char)(CLRX + 1)) ; lcm = -1 ;
00266                         } else if (*d & BLKPOSSIB) { /* i==pos */
00267                            addts((unsigned char)(SETX + 1)) ; lcm = -1 ;
00268                         } else
00269                            error("! bug") ; /* why wasn't lit true? */
00270                         d++ ;
00271                         f++ ;
00272                         i++ ;
00273                         pos = i ;
00274                      } /* end 'while e>d' */
00275                   }
00276                } /* end 'if e>d' */
00277                if (accum > 0) {
00278                   if (i > pos) {
00279                      addts((unsigned char)(ADVX + i - pos)) ;
00280                      pos = i ;
00281                   }
00282                   i += accum ;
00283                   d += accum ;
00284                   f += accum ;
00285                   while (accum > MAXOUT) {
00286                      addts((unsigned char)(cmd + MAXOUT)) ;
00287                      accum -= MAXOUT ;
00288                      pos += MAXOUT ;
00289                   }
00290                   lcm = -1 ;
00291                   addts((unsigned char)(cmd + accum)) ;
00292                   pos += accum ;
00293                }
00294             } /* end 'else DIFFERENT' */
00295          } /* end 'for i' */
00296          if (lcm != -1) {
00297             tempstore[lcm] += MAXOUT ;  /* append END */
00298             lcm = -1 ;
00299          } else {
00300             addts((unsigned char)(END)) ;
00301          }
00302       } /* end 'else rows different' */
00303 #ifdef DEBUG
00304       if (d != specdata + width)
00305          error("! internal inconsistency in repack") ;
00306 #endif
00307    } /* end 'for j' */
00308    if (repeatcount) {
00309       while (repeatcount > MAXOUT) {
00310          addts((unsigned char)(REPX+MAXOUT)) ;
00311          repeatcount -= MAXOUT ;
00312       }
00313       addts((unsigned char)(REPX+repeatcount)) ;
00314       repeatcount = 0 ;
00315    }
00316 }
00317 
00318 extern long bytesleft ;
00319 extern quarterword *raster ;
00320 long mbytesleft ;
00321 quarterword *mraster ;
00322 
00323 char *
00324 makecopy P3C(register unsigned char *, what, 
00325             register long, len, 
00326             register unsigned char *, p)
00327 {
00328    register unsigned char *q ;
00329 
00330    if (p == NULL) {
00331       if (len > MINCHUNK)
00332          p = (unsigned char *)mymalloc((integer)len) ;
00333       else {
00334          if (bytesleft < len) {
00335             raster = (quarterword *)mymalloc((integer)RASTERCHUNK) ;
00336             bytesleft = RASTERCHUNK ;
00337          }
00338          p = (unsigned char *)raster ;
00339          bytesleft -= len ;
00340          raster += len ;
00341       }
00342    }
00343    q = p ;
00344    while (len > 0) {
00345       *p++ = *what++ ;
00346       len -- ;
00347    }
00348    return ((char *)q) ;
00349 }
00350 
00351 /* Now the main routine, which is called when a character is used
00352    for the very first time. */
00353 void repack P1C(register chardesctype *, cp)
00354 {
00355    register long i, j ;
00356    register unsigned char *p ;
00357    register int width, height ;
00358    register int wwidth ;
00359    char startbytes ;
00360    int smallchar ;
00361 
00362    p = cp->packptr ;
00363    if (p == NULL)
00364       error("! no raster?") ;
00365    tsp = tempstore ;
00366    tsend = tempstore + tslen ;
00367    addts(*p) ; /* copy the PK flag byte */
00368    if (*p & 4) {
00369       if ((*p & 7) == 7) {
00370          startbytes = 17 ;
00371          width = getlong(p + 1) ;
00372          height = getlong(p + 5) ;
00373          for (i=0; i<12; i++)
00374             addts(*++p) ;
00375       } else {
00376          startbytes = 9 ;
00377          width = p[1] * 256 + p[2] ;
00378          height = p[3] * 256 + p[4] ;
00379          addts(*++p) ;
00380          addts(*++p) ;
00381          addts(*++p) ;
00382          addts(*++p) ;
00383       }
00384    } else {
00385       startbytes = 5 ;
00386       width = p[1] ;
00387       height = p[2] ;
00388    }
00389    addts(*++p) ;
00390    addts(*++p) ;
00391    addts(*++p) ;
00392    addts(*++p) ;
00393    p++ ; /* OK, p now points to beginning of the nibbles */
00394    addts((unsigned char)0) ;
00395    addts((unsigned char)0) ;
00396    addts((unsigned char)0) ;
00397    addts((unsigned char)0) ; /* leave room to stick in a new length field */
00398    wwidth = (width + 15) / 16 ;
00399    i = 2 * height * (long)wwidth ;
00400    if (i <= 0)
00401       i = 2 ;
00402    if ((cp->flags & BIGCHAR) == 0)
00403       smallchar = 5 ;
00404    else
00405       smallchar = 0 ;
00406    i += smallchar ;
00407    if (mbytesleft < i) {
00408       if (mbytesleft >= RASTERCHUNK)
00409          (void) free((char *) mraster) ;
00410       if (RASTERCHUNK > i) {
00411          mraster = (quarterword *)mymalloc((integer)RASTERCHUNK) ;
00412          mbytesleft = RASTERCHUNK ;
00413       } else {
00414          i += i / 4 ;
00415          mraster = (quarterword *)mymalloc((integer)(i + 3)) ;
00416          mbytesleft = i ;
00417       }
00418    }
00419    while (i > 0)
00420       mraster[--i] = 0 ;
00421    i = startbytes + unpack(p, (halfword *)mraster, (halfword)width,
00422                 (halfword)height,  *(cp->packptr)) ;
00423    dochar(mraster, (width + 7) >> 3, height) ;
00424    if (smallchar) {
00425       addts((unsigned char)0) ;
00426       addts((unsigned char)0) ;
00427       addts((unsigned char)0) ;
00428       addts((unsigned char)0) ;
00429       addts((unsigned char)0) ;
00430    }
00431    j = tsp - tempstore ;
00432 #ifdef DEBUG
00433    if (dd(D_COMPRESS))
00434         (void)fprintf(stderr,"PK %ld bytes, unpacked %ld, compressed %ld\n",
00435        i-(long)startbytes, (long)((width+7L)/8)*height, j-(long)startbytes-4) ;
00436 #endif /* DEBUG */
00437    if ( i < j ) {
00438       if (i > MINCHUNK)
00439          free(cp->packptr) ;
00440       cp->packptr =
00441               (unsigned char *)makecopy(tempstore, j, (unsigned char *)0) ;
00442    } else
00443       makecopy(tempstore, j, (unsigned char *)cp->packptr) ;
00444    putlong((char *)(cp->packptr+startbytes), j-startbytes-4-smallchar) ;
00445    cp->flags |= REPACKED ;
00446 }