zipsplit.c

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

/*
  Copyright (c) 1990-2005 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, both of these files are missing, the Info-ZIP license
  also may be found at:  ftp://ftp.info-zip.org/pub/infozip/license.html
*/
/*
 *  zipsplit.c by Mark Adler.
 */
#define __ZIPSPLIT_C

#ifndef UTIL
#define UTIL
#endif
#include "zip.h"
#define DEFCPYRT        /* main module: enable copyright string defines! */
#include "revision.h"
#include <signal.h>

#define DEFSIZ 36000L   /* Default split size (change in help() too) */
#ifdef MSDOS
#  define NL 2          /* Number of bytes written for a \n */
#else /* !MSDOS */
#  define NL 1          /* Number of bytes written for a \n */
#endif /* ?MSDOS */
#ifdef RISCOS
#  define INDEX "zipspl/idx"      /* Name of index file */
#  define TEMPL_FMT "%%0%dld"
#  define TEMPL_SIZ 13
#  define ZPATH_SEP '.'
#else
#ifdef QDOS
#  define ZPATH_SEP '_'
#  define INDEX "zipsplit_idx"    /* Name of index file */
#  define TEMPL_FMT "%%0%dld_zip"
#  define TEMPL_SIZ 17
#  define exit(p1) QDOSexit()
#else
#ifdef VM_CMS
#  define INDEX "zipsplit.idx"    /* Name of index file */
#  define TEMPL_FMT "%%0%dld.zip"
#  define TEMPL_SIZ 21
#  define ZPATH_SEP '.'
#else
#  define INDEX "zipsplit.idx"    /* Name of index file */
#  define TEMPL_FMT "%%0%dld.zip"
#  define TEMPL_SIZ 17
#  define ZPATH_SEP '.'
#endif /* VM_CMS */
#endif /* QDOS */
#endif /* RISCOS */

#ifdef MACOS
#define ziperr(c, h)    zipspliterr(c, h)
#define zipwarn(a, b)   zipsplitwarn(a, b)
void zipsplitwarn(ZCONST char *a, ZCONST char *b);
void zipspliterr(int c, ZCONST char *h);
#endif /* MACOS */

/* Local functions */
local zvoid *talloc OF((extent));
local void tfree OF((zvoid *));
local void tfreeall OF((void));
local void handler OF((int));
local void license OF((void));
local void help OF((void));
local void version_info OF((void));
local extent simple OF((ulg *, extent, ulg, ulg));
local int descmp OF((ZCONST zvoid *, ZCONST zvoid *));
local extent greedy OF((ulg *, extent, ulg, ulg));
local int retry OF((void));
int main OF((int, char **));


/* Output zip files */
local char template[TEMPL_SIZ]; /* name template for output files */
local int zipsmade = 0;         /* number of zip files made */
local int indexmade = 0;        /* true if index file made */
local char *path = NULL;        /* space for full name */
local char *name;               /* where name goes in path[] */


/* The talloc() and tree() routines extend malloc() and free() to keep
   track of all allocated memory.  Then the tfreeall() routine uses this
   information to free all allocated memory before exiting. */

#define TMAX 6          /* set intelligently by examining the code */
zvoid *talls[TMAX];     /* malloc'ed pointers to track */
int talln = 0;          /* number of entries in talls[] */


local zvoid *talloc(s)
extent s;
/* does a malloc() and saves the pointer to free later (does not check
   for an overflow of the talls[] list) */
{
  zvoid *p;

  if ((p = (zvoid *)malloc(s)) != NULL)
    talls[talln++] = p;
  return p;
}


local void tfree(p)
zvoid *p;
/* does a free() and also removes the pointer from the talloc() list */
{
  int i;

  free(p);
  i = talln;
  while (i--)
    if (talls[i] == p)
      break;
  if (i >= 0)
  {
    while (++i < talln)
      talls[i - 1] = talls[i];
    talln--;
  }
}


local void tfreeall()
/* free everything talloc'ed and not tfree'd */
{
  while (talln)
    free(talls[--talln]);
}


void ziperr(c, h)
int c;                  /* error code from the ZE_ class */
ZCONST char *h;         /* message about how it happened */
/* Issue a message for the error, clean up files and memory, and exit. */
{
  if (PERR(c))
    perror("zipsplit error");
  fprintf(stderr, "zipsplit error: %s (%s)\n", ziperrors[c-1], h);
  if (indexmade)
  {
    strcpy(name, INDEX);
    destroy(path);
  }
  for (; zipsmade; zipsmade--)
  {
    sprintf(name, template, zipsmade);
    destroy(path);
  }
  tfreeall();
  if (zipfile != NULL)
    free((zvoid *)zipfile);
  EXIT(c);
}


local void handler(s)
int s;                  /* signal number (ignored) */
/* Upon getting a user interrupt, abort cleanly using ziperr(). */
{
#ifndef MSDOS
  putc('\n', stderr);
#endif /* !MSDOS */
  ziperr(ZE_ABORT, "aborting");
  s++;                                  /* keep some compilers happy */
}


void zipwarn(a, b)
ZCONST char *a, *b;     /* message strings juxtaposed in output */
/* Print a warning message to stderr and return. */
{
  fprintf(stderr, "zipsplit warning: %s%s\n", a, b);
}


local void license()
/* Print license information to stdout. */
{
  extent i;             /* counter for copyright array */

  for (i = 0; i < sizeof(swlicense)/sizeof(char *); i++)
    puts(swlicense[i]);
}


local void help()
/* Print help (along with license info) to stdout. */
{
  extent i;             /* counter for help array */

  /* help array */
  static ZCONST char *text[] = {
"",
"ZipSplit %s (%s)",
#ifdef VM_CMS
"Usage:  zipsplit [-tipqs] [-n size] [-r room] [-b fm] zipfile",
#else
"Usage:  zipsplit [-tipqs] [-n size] [-r room] [-b path] zipfile",
#endif
"  -t   report how many files it will take, but don't make them",
#ifdef RISCOS
"  -i   make index (" INDEX ") and count its size against first zip file",
#else
"  -i   make index (zipsplit.idx) and count its size against first zip file",
#endif
"  -n   make zip files no larger than \"size\" (default = 36000)",
"  -r   leave room for \"room\" bytes on the first disk (default = 0)",
#ifdef VM_CMS
"  -b   use \"fm\" as the filemode for the output zip files",
#else
"  -b   use \"path\" for the output zip files",
#endif
"  -p   pause between output zip files",
"  -q   quieter operation, suppress some informational messages",
"  -s   do a sequential split even if it takes more zip files",
"  -h   show this help    -v   show version info    -L   show software license"
  };

  for (i = 0; i < sizeof(copyright)/sizeof(char *); i++) {
    printf(copyright[i], "zipsplit");
    putchar('\n');
  }
  for (i = 0; i < sizeof(text)/sizeof(char *); i++)
  {
    printf(text[i], VERSION, REVDATE);
    putchar('\n');
  }
}


local void version_info()
/* Print verbose info about program version and compile time options
   to stdout. */
{
  extent i;             /* counter in text arrays */

  /* Options info array */
  static ZCONST char *comp_opts[] = {
#ifdef DEBUG
    "DEBUG",
#endif
    NULL
  };

  for (i = 0; i < sizeof(copyright)/sizeof(char *); i++)
  {
    printf(copyright[i], "zipsplit");
    putchar('\n');
  }

  for (i = 0; i < sizeof(versinfolines)/sizeof(char *); i++)
  {
    printf(versinfolines[i], "ZipSplit", VERSION, REVDATE);
    putchar('\n');
  }

  version_local();

  puts("ZipSplit special compilation options:");
  for (i = 0; (int)i < (int)(sizeof(comp_opts)/sizeof(char *) - 1); i++)
  {
    printf("\t%s\n",comp_opts[i]);
  }
  if (i == 0)
      puts("\t[none]");
}


local extent simple(a, n, c, d)
ulg *a;         /* items to put in bins, return value: destination bins */
extent n;       /* number of items */
ulg c;          /* capacity of each bin */
ulg d;          /* amount to deduct from first bin */
/* Return the number of bins of capacity c that are needed to contain the
   integers in a[0..n-1] placed sequentially into the bins.  The value d
   is deducted initially from the first bin (space for index).  The entries
   in a[] are replaced by the destination bins. */
{
  extent k;     /* current bin number */
  ulg t;        /* space used in current bin */

  t = k = 0;
  while (n--)
  {
    if (*a + t > c - (k == 0 ? d : 0))
    {
      k++;
      t = 0;
    }
    t += *a;
    *(ulg huge *)a++ = k;
  }
  return k + 1;
}


local int descmp(a, b)
ZCONST zvoid *a, *b;          /* pointers to pointers to ulg's to compare */
/* Used by qsort() in greedy() to do a descending sort. */
{
  return **(ulg **)a < **(ulg **)b ? 1 : (**(ulg **)a > **(ulg **)b ? -1 : 0);
}


local extent greedy(a, n, c, d)
ulg *a;         /* items to put in bins, return value: destination bins */
extent n;       /* number of items */
ulg c;          /* capacity of each bin */
ulg d;          /* amount to deduct from first bin */
/* Return the number of bins of capacity c that are needed to contain the
   items with sizes a[0..n-1] placed non-sequentially into the bins.  The
   value d is deducted initially from the first bin (space for index).
   The entries in a[] are replaced by the destination bins. */
{
  ulg *b;       /* space left in each bin (malloc'ed for each m) */
  ulg *e;       /* copy of argument a[] (malloc'ed) */
  extent i;     /* steps through items */
  extent j;     /* steps through bins */
  extent k;     /* best bin to put current item in */
  extent m;     /* current number of bins */
  ulg **s;      /* pointers to e[], sorted descending (malloc'ed) */
  ulg t;        /* space left in best bin (index k) */

  /* Algorithm:
     1. Copy a[] to e[] and sort pointers to e[0..n-1] (in s[]), in
        descending order.
     2. Compute total of s[] and set m to the smallest number of bins of
        capacity c that can hold the total.
     3. Allocate m bins.
     4. For each item in s[], starting with the largest, put it in the
        bin with the smallest current capacity greater than or equal to the
        item's size.  If no bin has enough room, increment m and go to step 4.
     5. Else, all items ended up in a bin--return m.
  */

  /* Copy a[] to e[], put pointers to e[] in s[], and sort s[].  Also compute
     the initial number of bins (minus 1). */
  if ((e = (ulg *)malloc(n * sizeof(ulg))) == NULL ||
      (s = (ulg **)malloc(n * sizeof(ulg *))) == NULL)
  {
    if (e != NULL)
      free((zvoid *)e);
    ziperr(ZE_MEM, "was trying a smart split");
    return 0;                           /* only to make compiler happy */
  }
  memcpy((char *)e, (char *)a, n * sizeof(ulg));
  for (t = i = 0; i < n; i++)
    t += *(s[i] = e + i);
  m = (extent)((t + c - 1) / c) - 1;    /* pre-decrement for loop */
  qsort((char *)s, n, sizeof(ulg *), descmp);

  /* Stuff bins until successful */
  do {
    /* Increment the number of bins, allocate and initialize bins */
    if ((b = (ulg *)malloc(++m * sizeof(ulg))) == NULL)
    {
      free((zvoid *)s);
      free((zvoid *)e);
      ziperr(ZE_MEM, "was trying a smart split");
    }
    b[0] = c - d;                       /* leave space in first bin */
    for (j = 1; j < m; j++)
      b[j] = c;

    /* Fill the bins greedily */
    for (i = 0; i < n; i++)
    {
      /* Find smallest bin that will hold item i (size s[i]) */
      t = c + 1;
      for (k = j = 0; j < m; j++)
        if (*s[i] <= b[j] && b[j] < t)
          t = b[k = j];

      /* If no bins big enough for *s[i], try next m */
      if (t == c + 1)
        break;

      /* Diminish that bin and save where it goes */
      b[k] -= *s[i];
      a[(int)((ulg huge *)(s[i]) - (ulg huge *)e)] = k;
    }

    /* Clean up */
    free((zvoid *)b);

    /* Do until all items put in a bin */
  } while (i < n);

  /* Done--clean up and return the number of bins needed */
  free((zvoid *)s);
  free((zvoid *)e);
  return m;
}


local int retry()
{
  char m[10];
  fputs("Error writing to disk--redo entire disk? ", stderr);
  fgets(m, 10, stdin);
  return *m == 'y' || *m == 'Y';
}


#ifndef USE_ZIPSPLITMAIN
int main(argc, argv)
#else
int zipsplitmain(argc, argv)
#endif

int argc;               /* number of tokens in command line */