added latency tool
[tridge/junkcode.git] / 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 }