1 /*
2 * Decomp-ile^Wress .d scripts
3
4 * Copyright (C) 2007 Sylvain Beucler
5
6 * This file is part of GNU FreeDink
7
8 * GNU FreeDink is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License as
10 * published by the Free Software Foundation; either version 3 of the
11 * License, or (at your option) any later version.
12
13 * GNU FreeDink is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17
18 * You should have received a copy of the GNU General Public License
19 * along with this program. If not, see
20 * <http://www.gnu.org/licenses/>.
21 */
22
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <assert.h>
27 #define NB_PAIRS_MAX 128
28
29 /* Dink's .d files are compressed using the Binary Pair Encoding
30 algorithm, using one single block, check
31 http://www.csse.monash.edu.au/cluster/RJK/Compress/problem.html for
32 details. */
33
34 /* Format:
35 - <nb_pairs + 128> (1 byte)
36 - nb_pairs * <2 bytes> = pairs table, starting at 128
37 <pair #128><pair #129><pair #130>...
38 - <compressed text>, where all chars > 127 are to be replaced by the
39 matching pair
40 */
41
42 /* Simple run with 3 pairs: */
43 /*
44 - Pairs:
45 0 = 65 ('a'), 65 ('a') // coded as 128
46 1 = 128, 128 // coded as 129
47 2 = 129, 129 // coded as 130
48 - Text body:
49 130
50 - Stack (bottom is left):
51 -> (0)
52 -> 130
53 -> 129, 129
54 -> 129, 128, 128
55 -> 129, 128, 65, 65
56 -> 129, 128, 65 [output => 65]
57 -> 129, 128 [output => 65]
58 -> 129, 65, 65
59 -> 129, 65 [output => 65]
60 -> 129, [output => 65]
61 -> 129
62 -> 128, 128
63 -> 128, 65, 65
64 -> 128, 65 [output => 65]
65 -> 128 [output => 65]
66 -> 65, 65
67 -> 65 [output => 65]
68 -> (0) [output => 65]
69 - Output:
70 aaaaaaaa
71 */
72
73 #ifdef DEBUG
74 #define debug(...) fprintf(stderr, __VA_ARGS__)
75 #else
76 #define debug(...)
77 #endif
78
decompress(FILE * in,FILE * out)79 int decompress(FILE *in, FILE *out)
80 {
81 /* Replacement strings contain at most 2^NB_PAIRS_MAX
82 (or 1<<NB_PAIRS_MAX) */
83 /* Maximum length of a substitution = 2^128 =~ 2x10^38 => can't be
84 cached. Instead we'll stack the pairs references in the body of
85 the compressed text and pop them until the stack is
86 empty. There's a maximum of 128 chained pairs, so the stack has a
87 size of 128 + 1 (last substitution references non-pairs). */
88 unsigned char pairs[NB_PAIRS_MAX][2];
89 unsigned char stack[NB_PAIRS_MAX+1];
90 int stack_top = -1; /* empty stack */
91
92 /* First byte is the number of pairs + 128 */
93 int nb_pairs = fgetc(in);
94 nb_pairs -= NB_PAIRS_MAX;
95 debug("nb_pairs = %d\n", nb_pairs);
96 if (nb_pairs < 0)
97 return -1; /* Invalid header: negative number of pairs */
98
99 /* Read pairs table */
100 for (int i = 0; i < nb_pairs; i++)
101 {
102 for (int j = 0; j < 2; j++)
103 {
104 int c = fgetc(in);
105 if (c == EOF)
106 return -1; /* Invalid header: truncated pair table */
107 if (c > i+128)
108 return -1; /* Invalid header: reference to a pair that is not registered yet */
109 pairs[i][j] = c;
110 }
111 }
112
113 /* Debug: dump pair table */
114 for (int i = 0; i < nb_pairs; i++)
115 {
116 debug("pairs[%d]: %d . %d\n", i, pairs[i][0], pairs[i][1]);
117 }
118
119 /* Decompress file */
120 while (1)
121 {
122 assert(stack_top < nb_pairs+1);
123 if (stack_top < 0) /* empty stack */
124 {
125 int c = fgetc(in);
126 if (c == EOF) /* end of file */
127 break;
128 else if (c < 128)
129 fputc(c, out);
130 else
131 stack[++stack_top] = c;
132 }
133 else
134 {
135 if (stack[stack_top] < 128)
136 fputc(stack[stack_top--], out);
137 else
138 {
139 unsigned char cur_pair = stack[stack_top--] - 128;
140 if (cur_pair >= nb_pairs)
141 return -1; /* Invalid body: references non-existent pair */
142 stack[++stack_top] = pairs[cur_pair][1];
143 stack[++stack_top] = pairs[cur_pair][0];
144 }
145 }
146 }
147 return 0;
148 }
149
main(int argc,char * argv[])150 int main(int argc, char *argv[])
151 {
152 if (argc < 2)
153 {
154 printf("Usage: %s script.d ...\n", argv[0]);
155 exit(1);
156 }
157
158 while(*(++argv))
159 {
160 char *infile = *argv;
161 char *outfile;
162 int infile_len = strlen(infile);
163 int success = -1;
164 printf("Uncompressing %s... ", infile);
165 FILE *in;
166 if ((in = fopen(*argv, "rb")) == NULL)
167 {
168 perror("");
169 }
170 else
171 {
172 FILE *out;
173 outfile = malloc(infile_len + 1);
174 strcpy(outfile, infile);
175 outfile[infile_len - 1]--; /* D->C */
176 debug("outfile=%s\n", outfile);
177 if ((out = fopen(outfile, "wb")) == NULL)
178 {
179 perror("");
180 }
181 else
182 {
183 success = decompress(in, out);
184 fclose(out);
185 }
186 free(outfile);
187 fclose(in);
188 }
189 if (success != 0)
190 printf("failed!");
191 else
192 printf("done!");
193 printf("\n");
194 }
195 return 0;
196 }
197
198 /**
199 * Local Variables:
200 * compile-command: "gcc -Wall -std=c99 -pedantic -g d2c.c -o d2c"
201 * End:
202 */
203