util.c

给出了 zip 压缩算法的完整实现过程。

/*
  Copyright (c) 1990-2006 Info-ZIP.  All rights reserved.

  See the accompanying file LICENSE, version 2005-Feb-10 or later
  (the contents of which are also included in zip.h) for terms of use.
  If, for some reason, all these files are missing, the Info-ZIP license
  also may be found at:  ftp://ftp.info-zip.org/pub/infozip/license.html
*/
/*
 *  util.c by Mark Adler.
 */
#define __UTIL_C

#include "zip.h"
#include "ebcdic.h"
#include <ctype.h>

#ifdef MSDOS16
#  include <dos.h>
#endif

uch upper[256], lower[256];
/* Country-dependent case map table */


#ifndef UTIL /* UTIL picks out namecmp code (all utils) */

/* Local functions */
local int recmatch OF((ZCONST char *, ZCONST char *, int));
local int count_args OF((char *s));

#ifdef MSDOS16
  local unsigned ident OF((unsigned chr));
#endif

#ifdef NO_MKTIME
#  ifndef IZ_MKTIME_ONLY
#    define IZ_MKTIME_ONLY      /* only mktime() related code is pulled in */
#  endif
#  include "timezone.c"
#endif

#ifndef HAVE_FSEEKABLE
int fseekable(fp)
FILE *fp;
{
    long x;

    return (fp == NULL || (fseek(fp, -1L, SEEK_CUR) == 0 &&
            (x = ftell(fp)) >= 0 &&
            fseek(fp,  1L, SEEK_CUR) == 0 &&
            ftell(fp) == x + 1));
}
#endif /* HAVE_FSEEKABLE */

char *isshexp(p)
char *p;                /* candidate sh expression */
/* If p is a sh expression, a pointer to the first special character is
   returned.  Otherwise, NULL is returned. */
{
  for (; *p; INCSTR(p))
    if (*p == '\\' && *(p+1))
      p++;
#ifdef VMS
    else if (*p == '%' || *p == '*')
#else /* !VMS */
# ifdef RISCOS
    /* RISC OS uses # as its single-character wildcard */
    else if (*p == '#' || *p == '*' || *p == '[')
# else /* !RISC OS */
    else if (*p == '?' || *p == '*' || *p == '[')
# endif
#endif /* ?VMS */
      return p;
  return NULL;
}


local int recmatch(p, s, cs)
ZCONST char *p;  /* sh pattern to match */
ZCONST char *s;  /* string to match it to */
int cs;          /* flag: force case-sensitive matching */
/* Recursively compare the sh pattern p with the string s and return 1 if
   they match, and 0 or 2 if they don't or if there is a syntax error in the
   pattern.  This routine recurses on itself no deeper than the number of
   characters in the pattern. */
{
  int c;        /* pattern char or start of range in [-] loop */
  /* Get first character, the pattern for new recmatch calls follows */
  c = *POSTINCSTR(p);

  /* If that was the end of the pattern, match if string empty too */
  if (c == 0)
    return *s == 0;

  /* '?' (or '%' or '#') matches any character (but not an empty string) */
#ifdef VMS
  if (c == '%')
#else /* !VMS */
# ifdef RISCOS
  if (c == '#')
# else /* !RISC OS */
  if (c == '?')
# endif
#endif /* ?VMS */
#ifdef WILD_STOP_AT_DIR
    return (*s && *s != '/') ? recmatch(p, s + CLEN(s), cs) : 0;
#else
    return *s ? recmatch(p, s + CLEN(s), cs) : 0;
#endif

  /* '*' matches any number of characters, including zero */
#ifdef AMIGA
  if (c == '#' && *p == '?')            /* "#?" is Amiga-ese for "*" */
    c = '*', p++;
#endif /* AMIGA */
  if (c == '*')
  {
    if (*p == 0)
      return 1;
#ifdef WILD_STOP_AT_DIR
    for (; *s && *s != '/'; INCSTR(s))
      if ((c = recmatch(p, s, cs)) != 0)
        return c;
    return (*p == '/' || (*p == '\\' && p[1] == '/'))
      ? recmatch(p, s, cs) : 2;
#else /* !WILD_STOP_AT_DIR */
    if (!isshexp((char *)p))
    {
      /* optimization for rest of pattern being a literal string */

      /* optimization to handle patterns like *.txt */
      /* if the first char in the pattern is '*' and there */
      /* are no other shell expression chars, i.e. a literal string */
      /* then just compare the literal string at the end */

      ZCONST char *srest;

      srest = s + (strlen(s) - strlen(p));
      if (srest - s < 0)
        /* remaining literal string from pattern is longer than rest of
           test string, there can't be a match
         */
        return 0;
      else
        /* compare the remaining literal pattern string with the last bytes
           of the test string to check for a match */
#ifdef _MBCS
      {
        ZCONST char *q = s;

        /* MBCS-aware code must not scan backwards into a string from
         * the end.
         * So, we have to move forward by character from our well-known
         * character position s in the test string until we have advanced
         * to the srest position.
         */
        while (q < srest)
          INCSTR(q);
        /* In case the byte *srest is a trailing byte of a multibyte
         * character, we have actually advanced past the position (srest).
         * For this case, the match has failed!
         */
        if (q != srest)
          return 0;
        return ((cs ? strcmp(p, q) : namecmp(p, q)) == 0);
      }
#else /* !_MBCS */
        return ((cs ? strcmp(p, srest) : namecmp(p, srest)) == 0);
#endif /* ?_MBCS */
    }
    else
    {
      /* pattern contains more wildcards, continue with recursion... */
      for (; *s; INCSTR(s))
        if ((c = recmatch(p, s, cs)) != 0)
          return (int)c;
      return 2;           /* 2 means give up--shmatch will return false */
    }
#endif /* ?WILD_STOP_AT_DIR */
  }

#ifndef VMS             /* No bracket matching in VMS */
  /* Parse and process the list of characters and ranges in brackets */
  if (c == '[')
  {
    int e;              /* flag true if next char to be taken literally */
    ZCONST char *q;     /* pointer to end of [-] group */
    int r;              /* flag true to match anything but the range */

    if (*s == 0)                        /* need a character to match */
      return 0;
    p += (r = (*p == '!' || *p == '^')); /* see if reverse */
    for (q = p, e = 0; *q; q++)         /* find closing bracket */
      if (e)
        e = 0;
      else
        if (*q == '\\')
          e = 1;
        else if (*q == ']')
          break;
    if (*q != ']')                      /* nothing matches if bad syntax */
      return 0;
    for (c = 0, e = *p == '-'; p < q; p++)      /* go through the list */
    {
      if (e == 0 && *p == '\\')         /* set escape flag if \ */
        e = 1;
      else if (e == 0 && *p == '-')     /* set start of range if - */
        c = *(p-1);
      else
      {
        uch cc = (cs ? (uch)*s : case_map((uch)*s));
        uch uc = (uch) c;
        if (*(p+1) != '-')
          for (uc = uc ? uc : (uch)*p; uc <= (uch)*p; uc++)
            /* compare range */
            if ((cs ? uc : case_map(uc)) == cc)
              return r ? 0 : recmatch(q + CLEN(q), s + CLEN(s), cs);
        c = e = 0;                      /* clear range, escape flags */
      }
    }
    return r ? recmatch(q + CLEN(q), s + CLEN(s), cs) : 0;
                                        /* bracket match failed */
  }
#endif /* !VMS */

  /* If escape ('\'), just compare next character */
  if (c == '\\')
    if ((c = *p++) == '\0')             /* if \ at end, then syntax error */
      return 0;

#ifdef VMS
  /* 2005-11-06 SMS.
     Handle "..." wildcard in p with "." or "]" in s.
  */
  if ((c == '.') && (*p == '.') && (*(p+ CLEN( p)) == '.') &&
   ((*s == '.') || (*s == ']')))
  {
    /* Match "...]" with "]".  Continue after "]" in both. */
    if ((*(p+ 2* CLEN( p)) == ']') && (*s == ']'))
      return recmatch( (p+ 3* CLEN( p)), (s+ CLEN( s)), cs);

    /* Else, look for a reduced match in s, until "]" in or end of s. */
    for (; *s && (*s != ']'); INCSTR(s))
      if (*s == '.')
        /* If reduced match, then continue after "..." in p, "." in s. */
        if ((c = recmatch( (p+ CLEN( p)), s, cs)) != 0)
          return (int)c;

    /* Match "...]" with "]".  Continue after "]" in both. */
    if ((*(p+ 2* CLEN( p)) == ']') && (*s == ']'))
      return recmatch( (p+ 3* CLEN( p)), (s+ CLEN( s)), cs);

    /* No reduced match.  Quit. */
    return 2;
  }

#endif /* def VMS */

  /* Just a character--compare it */
  return (cs ? c == *s : case_map((uch)c) == case_map((uch)*s)) ?
          recmatch(p, s + CLEN(s), cs) : 0;
}


int shmatch(p, s, cs)
ZCONST char *p;         /* sh pattern to match */
ZCONST char *s;         /* string to match it to */
int cs;                 /* force case-sensitive match if TRUE */
/* Compare the sh pattern p with the string s and return true if they match,
   false if they don't or if there is a syntax error in the pattern. */
{
  return recmatch(p, s, cs) == 1;
}


#if defined(DOS) || defined(WIN32)
/* XXX  also suitable for OS2?  Atari?  Human68K?  TOPS-20?? */

int dosmatch(p, s, cs)
ZCONST char *p;         /* dos pattern to match    */
ZCONST char *s;         /* string to match it to   */
int cs;                 /* force case-sensitive match if TRUE */
/* Treat filenames without periods as having an implicit trailing period */
{
  char *s1;             /* revised string to match */
  int r;                /* result */

  if (strchr(p, '.') && !strchr(s, '.') &&
      ((s1 = malloc(strlen(s) + 2)) != NULL))
  {
    strcpy(s1, s);
    strcat(s1, ".");
  }
  else
  {
    /* will usually be OK */
    s1 = (char *)s;
  }

  r = recmatch(p, s1, cs) == 1;
  if (s != s1)
    free((zvoid *)s1);
  return r == 1;
}

#endif /* DOS || WIN32 */

zvoid far **search(b, a, n, cmp)
ZCONST zvoid *b;        /* pointer to value to search for */
ZCONST zvoid far **a;   /* table of pointers to values, sorted */
extent n;               /* number of pointers in a[] */
int (*cmp) OF((ZCONST zvoid *, ZCONST zvoid far *)); /* comparison function */

/* Search for b in the pointer list a[0..n-1] using the compare function
   cmp(b, c) where c is an element of a[i] and cmp() returns negative if
   *b < *c, zero if *b == *c, or positive if *b > *c.  If *b is found,
   search returns a pointer to the entry in a[], else search() returns
   NULL.  The nature and size of *b and *c (they can be different) are
   left up to the cmp() function.  A binary search is used, and it is
   assumed that the list is sorted in ascending order. */
{
  ZCONST zvoid far **i; /* pointer to midpoint of current range */
  ZCONST zvoid far **l; /* pointer to lower end of current range */
  int r;                /* result of (*cmp)() call */
  ZCONST zvoid far **u; /* pointer to upper end of current range */

  l = (ZCONST zvoid far **)a;  u = l + (n-1);
  while (u >= l) {
    i = l + ((unsigned)(u - l) >> 1);
    if ((r = (*cmp)(b, (ZCONST char far *)*(struct zlist far **)i)) < 0)
      u = i - 1;
    else if (r > 0)
      l = i + 1;
    else
      return (zvoid far **)i;
  }
  return NULL;          /* If b were in list, it would belong at l */
}

#endif /* !UTIL */

#ifdef MSDOS16

local unsigned ident(unsigned chr)
{
   return chr; /* in al */
}

void init_upper()
{
  static struct country {
    uch ignore[18];
    int (far *casemap)(int);
    uch filler[16];
  } country_info;

  struct country far *info = &country_info;
  union REGS regs;
  struct SREGS sregs;
  unsigned int c;

  regs.x.ax = 0x3800; /* get country info */
  regs.x.dx = FP_OFF(info);
  sregs.ds  = FP_SEG(info);
  intdosx(&regs, &regs, &sregs);
  for (c = 0; c < 128; c++) {
    upper[c] = (uch) toupper(c);
    lower[c] = (uch) c;
  }
  for (; c < sizeof(upper); c++) {
    upper[c] = (uch) (*country_info.casemap)(ident(c));
    /* ident() required because casemap takes its parameter in al */
    lower[c] = (uch) c;
  }
  for (c = 0; c < sizeof(upper); c++ ) {
    int u = upper[c];
    if (u != c && lower[u] == (uch) u) {
      lower[u] = (uch)c;
    }
  }
  for (c = 'A'; c <= 'Z'; c++) {
    lower[c] = (uch) (c - 'A' + 'a');
  }
}
#else /* !MSDOS16 */
#  ifndef OS2

void init_upper()
{
  unsigned int c;