archivers/zip.c
changeset 464 21c8e0d1578c
parent 446 e1f7fe003b70
child 467 99664d9842cb
equal deleted inserted replaced
463:98455f2c89c6 464:21c8e0d1578c
    23 #include "physfs.h"
    23 #include "physfs.h"
    24 #include "zlib.h"
    24 #include "zlib.h"
    25 
    25 
    26 #define __PHYSICSFS_INTERNAL__
    26 #define __PHYSICSFS_INTERNAL__
    27 #include "physfs_internal.h"
    27 #include "physfs_internal.h"
    28 
       
    29 /*
       
    30  * When sorting the zip entries in an archive, we use a modified QuickSort.
       
    31  *  When there are less then ZIP_QUICKSORT_THRESHOLD entries left to sort,
       
    32  *  we switch over to an InsertionSort for the remainder. Tweak to taste.
       
    33  */
       
    34 #define ZIP_QUICKSORT_THRESHOLD 4
       
    35 
    28 
    36 /*
    29 /*
    37  * A buffer of ZIP_READBUFSIZE is malloc() for each compressed file opened,
    30  * A buffer of ZIP_READBUFSIZE is malloc() for each compressed file opened,
    38  *  and is free()'d when you close the file; compressed data is read into
    31  *  and is free()'d when you close the file; compressed data is read into
    39  *  this buffer, and then is decompressed into the buffer passed to
    32  *  this buffer, and then is decompressed into the buffer passed to
   935     free(entry->name);
   928     free(entry->name);
   936     return(0);  /* failure. */
   929     return(0);  /* failure. */
   937 } /* zip_load_entry */
   930 } /* zip_load_entry */
   938 
   931 
   939 
   932 
   940 static void zip_entry_swap(ZIPentry *a, PHYSFS_uint32 one, PHYSFS_uint32 two)
   933 static int zip_entry_cmp(void *_a, PHYSFS_uint32 one, PHYSFS_uint32 two)
       
   934 {
       
   935     ZIPentry *a = (ZIPentry *) _a;
       
   936     return(strcmp(a[one].name, a[two].name));
       
   937 } /* zip_entry_cmp */
       
   938 
       
   939 
       
   940 static void zip_entry_swap(void *_a, PHYSFS_uint32 one, PHYSFS_uint32 two)
   941 {
   941 {
   942     ZIPentry tmp;
   942     ZIPentry tmp;
   943     memcpy(&tmp, &a[one], sizeof (ZIPentry));
   943     ZIPentry *first = &(((ZIPentry *) _a)[one]);
   944     memcpy(&a[one], &a[two], sizeof (ZIPentry));
   944     ZIPentry *second = &(((ZIPentry *) _a)[two]);
   945     memcpy(&a[two], &tmp, sizeof (ZIPentry));
   945     memcpy(&tmp, first, sizeof (ZIPentry));
       
   946     memcpy(first, second, sizeof (ZIPentry));
       
   947     memcpy(second, &tmp, sizeof (ZIPentry));
   946 } /* zip_entry_swap */
   948 } /* zip_entry_swap */
   947 
       
   948 
       
   949 static void zip_quick_sort(ZIPentry *a, PHYSFS_uint32 lo, PHYSFS_uint32 hi)
       
   950 {
       
   951     PHYSFS_uint32 i;
       
   952     PHYSFS_uint32 j;
       
   953     ZIPentry *v;
       
   954 
       
   955 	if ((hi - lo) > ZIP_QUICKSORT_THRESHOLD)
       
   956 	{
       
   957 		i = (hi + lo) / 2;
       
   958 
       
   959 		if (strcmp(a[lo].name, a[i].name) > 0) zip_entry_swap(a, lo, i);
       
   960 		if (strcmp(a[lo].name, a[hi].name) > 0) zip_entry_swap(a, lo, hi);
       
   961 		if (strcmp(a[i].name, a[hi].name) > 0) zip_entry_swap(a, i, hi);
       
   962 
       
   963 		j = hi - 1;
       
   964 		zip_entry_swap(a, i, j);
       
   965 		i = lo;
       
   966 		v = &a[j];
       
   967 		while (1)
       
   968 		{
       
   969 			while(strcmp(a[++i].name, v->name) < 0) {}
       
   970 			while(strcmp(a[--j].name, v->name) > 0) {}
       
   971 			if (j < i)
       
   972                 break;
       
   973 			zip_entry_swap(a, i, j);
       
   974 		} /* while */
       
   975 		zip_entry_swap(a, i, hi-1);
       
   976 		zip_quick_sort(a, lo, j);
       
   977 		zip_quick_sort(a, i+1, hi);
       
   978 	} /* if */
       
   979 } /* zip_quick_sort */
       
   980 
       
   981 
       
   982 static void zip_insertion_sort(ZIPentry *a, PHYSFS_uint32 lo, PHYSFS_uint32 hi)
       
   983 {
       
   984     PHYSFS_uint32 i;
       
   985     PHYSFS_uint32 j;
       
   986     ZIPentry tmp;
       
   987 
       
   988     for (i = lo + 1; i <= hi; i++)
       
   989     {
       
   990         memcpy(&tmp, &a[i], sizeof (ZIPentry));
       
   991         j = i;
       
   992         while ((j > lo) && (strcmp(a[j - 1].name, tmp.name) > 0))
       
   993         {
       
   994             memcpy(&a[j], &a[j - 1], sizeof (ZIPentry));
       
   995             j--;
       
   996         } /* while */
       
   997         memcpy(&a[j], &tmp, sizeof (ZIPentry));
       
   998     } /* for */
       
   999 } /* zip_insertion_sort */
       
  1000 
       
  1001 
       
  1002 static void zip_sort_entries(ZIPentry *entries, PHYSFS_uint32 max)
       
  1003 {
       
  1004     /*
       
  1005      * Fast Quicksort algorithm inspired by code from here:
       
  1006      *   http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
       
  1007      */
       
  1008     if (max <= ZIP_QUICKSORT_THRESHOLD)
       
  1009         zip_quick_sort(entries, 0, max - 1);
       
  1010 	zip_insertion_sort(entries, 0, max - 1);
       
  1011 } /* zip_sort_entries */
       
  1012 
   949 
  1013 
   950 
  1014 static int zip_load_entries(void *in, DirHandle *dirh,
   951 static int zip_load_entries(void *in, DirHandle *dirh,
  1015                             PHYSFS_uint32 data_ofs, PHYSFS_uint32 central_ofs)
   952                             PHYSFS_uint32 data_ofs, PHYSFS_uint32 central_ofs)
  1016 {
   953 {
  1030             zip_free_entries(info->entries, i);
   967             zip_free_entries(info->entries, i);
  1031             return(0);
   968             return(0);
  1032         } /* if */
   969         } /* if */
  1033     } /* for */
   970     } /* for */
  1034 
   971 
  1035     zip_sort_entries(info->entries, max);
   972     __PHYSFS_sort(info->entries, max, zip_entry_cmp, zip_entry_swap);
  1036     return(1);
   973     return(1);
  1037 } /* zip_load_entries */
   974 } /* zip_load_entries */
  1038 
   975 
  1039 
   976 
  1040 static int zip_parse_end_of_central_dir(void *in, DirHandle *dirh,
   977 static int zip_parse_end_of_central_dir(void *in, DirHandle *dirh,