| 1 | /* |
| 2 | * Adaptive Huffman code input to output |
| 3 | * |
| 4 | * On - line algorithm |
| 5 | * |
| 6 | * Does not prepend decoding tree |
| 7 | * |
| 8 | * Written by Colin L. Mc Master (UCB) February 28, 1979 |
| 9 | */ |
| 10 | |
| 11 | |
| 12 | #include "compact.h" |
| 13 | |
| 14 | union cio d; |
| 15 | int bits; |
| 16 | |
| 17 | |
| 18 | main (argc, argv) |
| 19 | short argc; |
| 20 | char *argv [ ]; |
| 21 | { |
| 22 | register short i, j; |
| 23 | register int m; |
| 24 | union cio c; |
| 25 | short l; |
| 26 | longint ic, n; |
| 27 | char *cp, fname [LNAME]; |
| 28 | |
| 29 | dir [513] . next = NULL; |
| 30 | for (head = dir + (j = 513); j--; ) { |
| 31 | dirp = head--; |
| 32 | head -> next = dirp; |
| 33 | } |
| 34 | bottom = dirp -> pt = dict; |
| 35 | dict [0] . top [0] = dict [0] . top [1] = dirp; |
| 36 | dirq = dirp -> next; |
| 37 | in [EF] . flags = FBIT | SEEN; |
| 38 | |
| 39 | for (i = 1; ; i++) { |
| 40 | ic = oc = 0; |
| 41 | (bottom -> top [1]) -> next = flist; |
| 42 | bottom -> top [1] = dirp; |
| 43 | flist = dirq; |
| 44 | if (i >= argc) { |
| 45 | uncfp = stdin; |
| 46 | cfp = stdout; |
| 47 | } |
| 48 | else { |
| 49 | m = -1; |
| 50 | cp = fname; |
| 51 | for (l = 0; l < (LNAME - 3) && (*cp = argv [i][l]); l++) |
| 52 | if (*cp++ == '/') m = l; |
| 53 | if (l >= (LNAME - 3) || (l - m) > 13) { |
| 54 | fprintf (stderr, "%s: File name too long\n", argv [i]); |
| 55 | if (i == argc - 1) break; |
| 56 | continue; |
| 57 | } |
| 58 | if ((uncfp = fopen (argv [i], "r")) == NULL) { |
| 59 | perror (argv [i]); |
| 60 | if (i == argc - 1) break; |
| 61 | continue; |
| 62 | } |
| 63 | } |
| 64 | |
| 65 | fstat (fileno (uncfp), &status); |
| 66 | if ((status.st_mode & 040000) == 040000) { |
| 67 | fprintf (stderr, "%s: Can't compact a directory\n", argv [i]); |
| 68 | if (i < argc) goto closein; |
| 69 | break; |
| 70 | } |
| 71 | |
| 72 | if ((d . integ = getc (uncfp)) != EOF) { |
| 73 | ic++; |
| 74 | if ((c . integ = getc (uncfp)) != EOF) { |
| 75 | d . chars . hib = c . integ & 0377; |
| 76 | if ((d . integ &= 0177777) == COMPACTED) { |
| 77 | fprintf (stderr, "%s: Already compacted.\n", argv [i]); |
| 78 | if (i < argc) goto closein; |
| 79 | break; |
| 80 | } |
| 81 | if (d . integ == PACKED) { |
| 82 | fprintf (stderr, "%s: Already packed using program pack. Use unpack.\n", argv [i]); |
| 83 | if (i < argc) goto closein; |
| 84 | break; |
| 85 | } |
| 86 | if (i < argc) { |
| 87 | *cp++ = '.'; *cp++ = 'C'; *cp = '\0'; |
| 88 | if ((cfp = fopen (fname, "w")) == NULL) { |
| 89 | perror (fname); |
| 90 | goto closein; |
| 91 | } |
| 92 | chmod (fname, status.st_mode); |
| 93 | } |
| 94 | c . integ = COMPACTED; |
| 95 | putc (c . chars . lob, cfp); |
| 96 | putc (c . chars . hib, cfp); |
| 97 | if (ferror (cfp)) |
| 98 | if (i < argc) { |
| 99 | perror (fname); |
| 100 | unlink (fname); |
| 101 | goto closeboth; |
| 102 | } |
| 103 | else goto fail; |
| 104 | bits = 8; |
| 105 | oc = 2; |
| 106 | c . integ = d . integ & 0377; |
| 107 | |
| 108 | in [NC] . fp = in [EF] . fp = dict [0] . sp [0] . p = bottom = dict + 1; |
| 109 | bottom -> count [0] = bottom -> count [1] = dict [0] . count [1] = 1; |
| 110 | dirp -> next = dict [0] . top [1] = bottom -> top [0] = bottom -> top [1] = dirq = NEW; |
| 111 | dirq -> next = NULL; |
| 112 | dict [0] . fath . fp = NULL; |
| 113 | dirq -> pt = bottom -> fath . fp = in [c . integ] . fp = dict; |
| 114 | in [c . integ] . flags = (FBIT | SEEN); |
| 115 | in [NC] . flags = SEEN; |
| 116 | dict [0] . fath . flags = RLEAF; |
| 117 | bottom -> fath . flags = (LLEAF | RLEAF); |
| 118 | dict [0] . count [0] = 2; |
| 119 | |
| 120 | dict [0] . sp [1] . ch = c . integ; |
| 121 | bottom -> sp [0] . ch = NC; |
| 122 | bottom -> sp [1] . ch = EF; |
| 123 | |
| 124 | for (c . integ = ((d . integ >> 8) & 0377); c . integ != EOF; c . integ = getc (uncfp)) { |
| 125 | ic++; |
| 126 | if (in [c . integ] . flags & SEEN) encode (c . integ); |
| 127 | else { |
| 128 | encode (NC); |
| 129 | uptree (NC); |
| 130 | insert (c . integ); |
| 131 | |
| 132 | m = 0200; |
| 133 | for (j = 8; j--; m >>= 1) { |
| 134 | d . integ <<= 1; |
| 135 | if (m & c . integ) d . integ++; |
| 136 | ++bits; |
| 137 | if ((bits &= 017) == 0) { |
| 138 | putc (d . chars . hib, cfp); |
| 139 | putc (d . chars . lob, cfp); |
| 140 | oc += 2; |
| 141 | } |
| 142 | } |
| 143 | } |
| 144 | if (ferror (cfp)) |
| 145 | if (i < argc) { |
| 146 | perror (fname); |
| 147 | unlink (fname); |
| 148 | goto closeboth; |
| 149 | } |
| 150 | else goto fail; |
| 151 | uptree (c . integ); |
| 152 | |
| 153 | } |
| 154 | |
| 155 | if (ferror (uncfp)) |
| 156 | if (i < argc) { |
| 157 | perror (argv [i]); |
| 158 | unlink (fname); |
| 159 | goto closeboth; |
| 160 | } |
| 161 | else goto fail; |
| 162 | |
| 163 | encode (EF); |
| 164 | |
| 165 | if (bits) { |
| 166 | d . integ <<= (16 - bits); |
| 167 | oc++; |
| 168 | putc (d . chars . hib, cfp); |
| 169 | if (bits > 8) { |
| 170 | oc++; |
| 171 | putc (d . chars . lob, cfp); |
| 172 | } |
| 173 | bits = 0; |
| 174 | } |
| 175 | } |
| 176 | else oc = ic; |
| 177 | } |
| 178 | |
| 179 | if (ferror (uncfp) || ferror (cfp)) |
| 180 | if (i < argc) { |
| 181 | if (ferror (cfp)) |
| 182 | perror (fname); |
| 183 | else |
| 184 | perror (argv [i]); |
| 185 | if (oc > 1) { |
| 186 | unlink (fname); |
| 187 | goto closeboth; |
| 188 | } |
| 189 | goto closein; |
| 190 | } |
| 191 | else goto fail; |
| 192 | else { |
| 193 | if (oc >= ic) { |
| 194 | if (i < argc) fprintf (stderr, "%s: ", argv [i]); |
| 195 | if (i < argc) fprintf (stderr, "Not compacted. "); |
| 196 | fprintf (stderr, "Does not save bytes.\n"); |
| 197 | if (i < argc) { |
| 198 | if (oc > 1) { |
| 199 | unlink (fname); |
| 200 | goto closeboth; |
| 201 | } |
| 202 | goto closein; |
| 203 | } |
| 204 | else break; |
| 205 | } |
| 206 | while ((ic - oc) > 21474) { |
| 207 | ic /= 10; |
| 208 | oc /= 10; |
| 209 | } |
| 210 | n = 100000 * (ic - oc) / ic + 5; |
| 211 | m = (n % 1000) / 10; |
| 212 | bits = m % 10 + '0'; |
| 213 | c . integ = m / 10 + '0'; |
| 214 | if (i < argc) fprintf (stderr, "%s: ", argv [i]); |
| 215 | fprintf (stderr, "Compression : %4ld.%c%c%%\n", n / 1000, c . chars . lob, bits); |
| 216 | } |
| 217 | |
| 218 | if (i >= argc) break; |
| 219 | unlink (argv [i]); |
| 220 | closeboth : fclose (cfp); |
| 221 | closein : fclose (uncfp); |
| 222 | if (i == argc - 1) break; |
| 223 | for (j = 256; j--; ) in [j] . flags = 0; |
| 224 | continue; |
| 225 | fail : fprintf (stderr, "Unsuccessful compact of standard input to standard output.\n"); |
| 226 | break; |
| 227 | } |
| 228 | } |
| 229 | |
| 230 | encode (ch) |
| 231 | int ch; |
| 232 | { |
| 233 | |
| 234 | register struct node *pp; |
| 235 | register char j; |
| 236 | union cio c; |
| 237 | int stack [17], stp, stbits; |
| 238 | |
| 239 | c . integ = ch; |
| 240 | stack [stp = 0] = in [c . integ] . flags & FBIT; |
| 241 | stbits = 1; |
| 242 | pp = in [c . integ] . fp; |
| 243 | |
| 244 | while (pp -> fath . fp) { |
| 245 | stack [stp] <<= 1; |
| 246 | if (pp -> fath . flags & FBIT) stack [stp]++; |
| 247 | stbits++; |
| 248 | if ((stbits &= 017) == 0) stp++; |
| 249 | pp = pp -> fath . fp; |
| 250 | } |
| 251 | |
| 252 | /* pop the output stack */ |
| 253 | |
| 254 | for (stp++; stp--; ) { |
| 255 | for (j = 0; j < stbits; j++) { |
| 256 | d . integ <<= 1; |
| 257 | if (stack [stp] & 01) d . integ++; |
| 258 | ++bits; |
| 259 | if ((bits &= 017) == 0) { |
| 260 | putc (d . chars . hib, cfp); |
| 261 | putc (d . chars . lob, cfp); |
| 262 | if (ferror (cfp)) return; |
| 263 | oc += 2; |
| 264 | } |
| 265 | stack [stp] >>= 1; |
| 266 | } |
| 267 | stbits = 16; |
| 268 | } |
| 269 | } |