bsort.c

   1 /*
   2    Copyright (C) Andrew Tridgell 1998
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17 */
  18
  19 /* a dumb implementation of a block sorting compressor, primarily
  20    written to make sure I understand the algorithm */
  21
  22 #include "rzip.h"
  23
  24 struct ch {
  25         uchar *p; /* pointer into original buffer */
  26 };
  27
  28 static uchar *block_end;
  29 static uchar *block_start;
  30
  31 static int ch_cmp(struct ch *d1, struct ch *d2)
  32 {
  33         int len1, len2, len;
  34         int ret;
  35         uchar *p1=d1->p, *p2=d2->p;
  36
  37         if (p1[0] != p2[0]) return p1[0] - p2[0];
  38
  39         len1 = (int)(block_end - p1);
  40         len2 = (int)(block_end - p2);
  41         len = MIN(len1, len2);
  42
  43         ret = memcmp(d1->p, d2->p, len);
  44         if (ret != 0) return ret;
  45
  46         p1 += len;
  47         p2 += len;
  48
  49         if (p1 == block_end) p1 = block_start;
  50         if (p2 == block_end) p2 = block_start;
  51
  52         len = (block_end-block_start)-len;
  53
  54         while (len--) {
  55                 if (p1[0] != p2[0]) return p1[0] - p2[0];
  56                 p1++; p2++;
  57                 if (p1 == block_end) p1 = block_start;
  58                 if (p2 == block_end) p2 = block_start;
  59         }
  60
  61         return 0;
  62 }
  63
  64 /* sort a block of data */
  65 void block_sort(uchar *in, uchar *out, int len)
  66 {
  67         struct ch *d;
  68         int i, Index;
  69
  70         block_start = in;
  71         block_end = in+len;
  72
  73         d = (struct ch *)malloc(len*sizeof(d[0]));
  74         if (!d) {
  75                 fprintf(stderr,"not enough memory in block_sort - exiting\n");
  76                 exit(1);
  77         }
  78
  79         /* fill the data array */
  80         for (i=0;i<len-1;i++) {
  81                 d[i].p = &in[i+1];
  82         }
  83         d[i].p = &in[0];
  84
  85         /* sort it */
  86         qsort(d, len, sizeof(d[0]), ch_cmp);
  87
  88         /* pull out the sorted data */
  89         for (i=0;i<len;i++) {
  90                 if (d[i].p == in) {
  91                         Index = i;
  92                         out[i+4] = in[len-1];
  93                 } else {
  94                         out[i+4] = d[i].p[-1];
  95                 }
  96         }
  97
  98         out[0] = Index&0xFF;
  99         out[1] = (Index>>8)&0xFF;
 100         out[2] = (Index>>16)&0xFF;
 101         out[3] = (Index>>24)&0xFF;
 102
 103         /* cleanup */
 104         free(d);
 105 }
 106
 107
 108 static int uch_cmp(int *d1, int *d2)
 109 {
 110         return block_start[*d1] - block_start[*d2];
 111 }
 112
 113 /* unsort a block of data */
 114 void block_unsort(uchar *in, uchar *out, int len)
 115 {
 116         int Index, i, j;
 117         int *links;
 118
 119         Index = in[0] | (in[1]<<8) | (in[2]<<16) | (in[3]<<24);
 120
 121         len -= 4;
 122         in += 4;
 123
 124         block_start = in;
 125
 126         /* build the indexes */
 127         links = (int *)malloc(len*sizeof(links[0]));
 128         for (i=0;i<len;i++) {
 129                 links[i] = i;
 130         }
 131
 132         /* sort the indexes by transmitted char to reveal the links */
 133         qsort(links, len, sizeof(links[0]), uch_cmp);
 134
 135         /* follow our tail to decode the data */
 136         j = links[Index];
 137         for (i=0;i<len;i++) {
 138                 out[i] = in[j];
 139                 j = links[j];
 140         }
 141
 142         /* cleanup */
 143         free(links);
 144 }
 145
 146
 147  int main(int argc, char *argv[])
 148 {
 149         char *f1 = argv[1];
 150         char *f2 = argv[2];
 151         int fd1, fd2;
 152         uchar *buf1, *buf2;
 153         struct stat st;
 154
 155         fd1 = open(f1, O_RDONLY);
 156         fd2 = open(f2, O_WRONLY|O_CREAT|O_TRUNC, 0666);
 157
 158         fstat(fd1, &st);
 159
 160         buf1 = (uchar *)malloc(st.st_size);
 161         buf2 = (uchar *)malloc(st.st_size+4);
 162
 163         read(fd1, buf1, st.st_size);
 164
 165         if (!strstr(argv[0],"bunsort")) {
 166                 block_sort(buf1, buf2, st.st_size);
 167
 168                 write(fd2,buf2,st.st_size+4);
 169         } else {
 170                 block_unsort(buf1, buf2, st.st_size);
 171
 172                 write(fd2,buf2,st.st_size-4);
 173         }
 174
 175         close(fd1);
 176         close(fd2);
 177         return 0;
 178 }