2 Copyright (C) Andrew Tridgell 1998
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.
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.
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.
19 /* a dumb implementation of a block sorting compressor, primarily
20 written to make sure I understand the algorithm */
25 uchar *p; /* pointer into original buffer */
28 static uchar *block_end;
29 static uchar *block_start;
31 static int ch_cmp(struct ch *d1, struct ch *d2)
35 uchar *p1=d1->p, *p2=d2->p;
37 if (p1[0] != p2[0]) return p1[0] - p2[0];
39 len1 = (int)(block_end - p1);
40 len2 = (int)(block_end - p2);
41 len = MIN(len1, len2);
43 ret = memcmp(d1->p, d2->p, len);
44 if (ret != 0) return ret;
49 if (p1 == block_end) p1 = block_start;
50 if (p2 == block_end) p2 = block_start;
52 len = (block_end-block_start)-len;
55 if (p1[0] != p2[0]) return p1[0] - p2[0];
57 if (p1 == block_end) p1 = block_start;
58 if (p2 == block_end) p2 = block_start;
64 /* sort a block of data */
65 void block_sort(uchar *in, uchar *out, int len)
73 d = (struct ch *)malloc(len*sizeof(d[0]));
75 fprintf(stderr,"not enough memory in block_sort - exiting\n");
79 /* fill the data array */
80 for (i=0;i<len-1;i++) {
86 qsort(d, len, sizeof(d[0]), ch_cmp);
88 /* pull out the sorted data */
94 out[i+4] = d[i].p[-1];
99 out[1] = (Index>>8)&0xFF;
100 out[2] = (Index>>16)&0xFF;
101 out[3] = (Index>>24)&0xFF;
108 static int uch_cmp(int *d1, int *d2)
110 return block_start[*d1] - block_start[*d2];
113 /* unsort a block of data */
114 void block_unsort(uchar *in, uchar *out, int len)
119 Index = in[0] | (in[1]<<8) | (in[2]<<16) | (in[3]<<24);
126 /* build the indexes */
127 links = (int *)malloc(len*sizeof(links[0]));
128 for (i=0;i<len;i++) {
132 /* sort the indexes by transmitted char to reveal the links */
133 qsort(links, len, sizeof(links[0]), uch_cmp);
135 /* follow our tail to decode the data */
137 for (i=0;i<len;i++) {
147 int main(int argc, char *argv[])
155 fd1 = open(f1, O_RDONLY);
156 fd2 = open(f2, O_WRONLY|O_CREAT|O_TRUNC, 0666);
160 buf1 = (uchar *)malloc(st.st_size);
161 buf2 = (uchar *)malloc(st.st_size+4);
163 read(fd1, buf1, st.st_size);
165 if (!strstr(argv[0],"bunsort")) {
166 block_sort(buf1, buf2, st.st_size);
168 write(fd2,buf2,st.st_size+4);
170 block_unsort(buf1, buf2, st.st_size);
172 write(fd2,buf2,st.st_size-4);