foreign/dskdcmps.h

   1 // See readme-dskdcmps.txt for more information about this file.
   2 // Modifications for Deark are Copyright (C) 2021 Jason Summers, and have the
   3 // same terms of use as the main part of Deark.
   4 // Alternatively, at your option, the modifications for Deark may be treated
   5 // as public domain.
   6
   7 // Intro from the original software:
   8
   9 //*******************************************************************
  10 //
  11 // program - dskdcmps.c
  12 // purpose - test decompression of dsk files
  13 //
  14 //
  15 // LZW decompression - no warranties expressed or implied
  16 // Note that this code was mainly a test to see if it could
  17 // be done, and to understand how dsk files were compressed
  18 // and if in turn they could be decompressed without creating
  19 // diskettes (the entire reason for dskxtrct).
  20 //
  21 // Also note that there is some of confusion over the status of the
  22 // patent for the LZW decompression algorithm. You use this code
  23 // at your own risk.
  24 //
  25 //*******************************************************************
  26
  27 //#define PgmTitle "dskdcmps"
  28 //#define PgmVersion "1.0 (08/01/2000)"
  29
  30 //#define DD_EXTRADBG
  31 #define DD_MAXSTRLEN 4096
  32 #define DD_MAXTABLE 4096
  33
  34 struct dd_codet {
  35         u16 hold;
  36         int j;
  37         u16 oldcode, oldest, newest;
  38         u16 older[DD_MAXTABLE], newer[DD_MAXTABLE];
  39         u16 charlink[DD_MAXTABLE]; // parent?
  40         int usecount[DD_MAXTABLE]; // How many other codes depend on this code?
  41         UI size[DD_MAXTABLE];
  42         u8 valfirst[DD_MAXTABLE];
  43         u8 value[DD_MAXTABLE];
  44 };
  45
  46 struct dd_Ctl {
  47         deark *c;
  48         const char *modname;
  49         struct de_dfilter_in_params *dcmpri;
  50         struct de_dfilter_out_params *dcmpro;
  51         struct de_dfilter_results *dres;
  52         i64 code_counter;
  53         i64 inf_pos;
  54         i64 inf_endpos;
  55         i64 nbytes_written;
  56         int eof_flag;
  57         int err_flag;
  58         u8 valbuf[DD_MAXTABLE];
  59         char msg[DD_MAXSTRLEN];
  60 };
  61
  62 //*******************************************************************
  63 static void dd_tmsg(struct dd_Ctl *Ctl, const char *fmt, ...)
  64         de_gnuc_attribute ((format (printf, 2, 3)));
  65
  66 static void dd_tmsg(struct dd_Ctl *Ctl, const char *fmt, ...)
  67 {
  68         va_list ap;
  69
  70         if (Ctl->c->debug_level<3) return;
  71
  72         va_start(ap, fmt);
  73         de_vsnprintf(Ctl->msg, sizeof(Ctl->msg), fmt, ap);
  74         va_end(ap);
  75
  76         de_dbg(Ctl->c, "%s", Ctl->msg);
  77 }
  78
  79 //*******************************************************************
  80
  81 #ifdef DD_EXTRADBG
  82
  83 static void dd_dumpstate(struct dd_Ctl *Ctl, struct dd_codet * ct)
  84 {
  85         size_t i;
  86         dbuf *dmpf = NULL;
  87         FILE *f; // copy of dmpf->fp; do not close
  88         char filename[100];
  89
  90         de_snprintf(filename, sizeof(filename), "ddump%07"I64_FMT".tmp", Ctl->code_counter);
  91         dmpf = dbuf_create_unmanaged_file(Ctl->c, filename, DE_OVERWRITEMODE_DEFAULT, 0);
  92         f = dmpf->fp;
  93
  94         fprintf(f, "codes processed: %u\n", (UI)Ctl->code_counter);
  95         fprintf(f, "code olde newe clin uc siz\n");
  96         for(i=0; i<4096; i++) {
  97                 fprintf(f, "%4u %4u %4u %4u %2u %4u", (UI)i,
  98                         (UI)ct->older[i], (UI)ct->newer[i],
  99                         (UI)ct->charlink[i],
 100                         (UI)ct->usecount[i],
 101                         (UI)ct->size[i]);
 102
 103                 if(ct->size[i]==1) {
 104                         fprintf(f, " %02x", (UI)ct->value[i]);
 105                 }
 106                 else if(ct->size[i]==2) {
 107                         fprintf(f, " %02x %02x", (UI)ct->valfirst[i], (UI)ct->value[i]);
 108                 }
 109                 else if(ct->size[i]>2) {
 110                         fprintf(f, " %02x...%02x", (UI)ct->valfirst[i], (UI)ct->value[i]);
 111                 }
 112
 113                 if(i==(size_t)ct->oldcode) fprintf(f, " OLDCODE");
 114                 if(i==(size_t)ct->oldest) fprintf(f, " oldest");
 115                 if(i==(size_t)ct->newest) fprintf(f, " newest");
 116
 117                 fprintf(f, "\n");
 118         }
 119
 120         dbuf_close(dmpf);
 121 }
 122
 123 #endif
 124
 125 //*******************************************************************
 126 static void dd_ValidateLinkChains (struct dd_Ctl *Ctl, struct dd_codet * ct, u16 tcode)
 127 {
 128         u16 tnewer, tolder;
 129         UI errcode = 0;
 130
 131         if(Ctl->c->debug_level<3) return;
 132         tnewer = ct->newer[tcode];
 133         tolder = ct->older[tcode];
 134         if (tcode == ct->newest) {
 135                 if (tnewer != 0) {
 136                         errcode += 1;
 137                 }
 138         }
 139         else {
 140                 if (ct->older[tnewer] != tcode) {
 141                         errcode += 2;
 142                 }
 143         }
 144         if (tcode == ct->oldest) {
 145                 if (tolder != 0) {
 146                         errcode += 4;
 147                 }
 148         }
 149         else {
 150                 if (ct->newer[tolder] != tcode) {
 151                         errcode += 8;
 152                 }
 153         }
 154
 155         if(errcode) {
 156                 dd_tmsg(Ctl, "Link validation error (%u). tcode: %4x, older: %4x, newer: %4x",
 157                         errcode, tcode, tolder, ct->newer[tolder]);
 158         }
 159 }
 160
 161 //*******************************************************************
 162 static void dd_OutputString(struct dd_Ctl *Ctl, struct dd_codet * ct, u16 tcode)
 163 {
 164         size_t i;
 165         size_t valbuf_pos = DD_MAXTABLE;
 166         u16 curcode = tcode;
 167
 168         if(ct->size[tcode]<1 || ct->size[tcode]>DD_MAXTABLE-256) {
 169                 Ctl->err_flag = 1;
 170                 goto done;
 171         }
 172
 173         for(i=0; i<(size_t)ct->size[tcode]; i++) {
 174                 if(curcode>=DD_MAXTABLE || curcode<1) {
 175                         Ctl->err_flag = 1;
 176                         goto done;
 177                 }
 178
 179                 if(ct->size[curcode] != ct->size[tcode]-i) {
 180                         Ctl->err_flag = 1;
 181                         goto done;
 182                 }
 183
 184                 valbuf_pos--;
 185                 Ctl->valbuf[valbuf_pos] = ct->value[curcode];
 186
 187                 // Traverse the tree, back toward the root codes.
 188                 curcode = ct->charlink[curcode];
 189         }
 190
 191         dbuf_write(Ctl->dcmpro->f, &Ctl->valbuf[valbuf_pos], ct->size[tcode]);
 192         Ctl->nbytes_written += (i64)ct->size[tcode];
 193
 194 done:
 195         ;
 196 }
 197
 198 //*******************************************************************
 199 static u16 dd_GetNextcode (struct dd_Ctl *Ctl, struct dd_codet * ct)
 200 {
 201         u16 code;
 202
 203         if(Ctl->inf_pos >= Ctl->inf_endpos) {
 204                 Ctl->eof_flag = 1;
 205                 return 0;
 206         }
 207
 208         if (ct->j) {
 209                 code = (u16)dbuf_getbyte_p(Ctl->dcmpri->f, &Ctl->inf_pos) << 4;
 210                 ct->hold = (u16)dbuf_getbyte_p(Ctl->dcmpri->f, &Ctl->inf_pos);
 211                 code |= (ct->hold >> 4);
 212         }
 213         else {
 214                 code = (ct->hold & 0x0f) << 8;
 215                 code |= (u16)dbuf_getbyte_p(Ctl->dcmpri->f, &Ctl->inf_pos);
 216                 ct->hold = 0;
 217         }
 218         ct->j = !ct->j;
 219         return (code);
 220 }
 221
 222 //*******************************************************************
 223 static struct dd_codet * dd_DInit (struct dd_Ctl *Ctl)
 224 {
 225         struct dd_codet * ct;
 226         u16 code;
 227
 228         ct = (struct dd_codet *) de_malloc(Ctl->c, sizeof(struct dd_codet));
 229         for (code = 1; code <= 256; code++) {
 230                 ct->valfirst[code] = (u8)(code-1);
 231                 ct->value[code] = (u8)(code-1);
 232                 ct->size[code] = 1;
 233                 // Maybe this is set to 1 just to prevent it from ever getting down
 234                 // to 0. So it doesn't get re-used.
 235                 ct->usecount[code] = 1;
 236         }
 237         for (code = 257; code <= 4095; code++) {
 238                 if(code<4095) {
 239                         ct->newer[code] = code + 1;
 240                 }
 241                 if(code>257) {
 242                         ct->older[code] = code - 1;
 243                 }
 244         }
 245         ct->oldest = 257;
 246         ct->newest = 4095;
 247         ct->j = 1;
 248         ct->oldcode = 0;
 249         ct->hold = 0;
 250         return (ct);
 251 }
 252
 253 static void dd_DFree(struct dd_Ctl *Ctl, struct dd_codet *ct)
 254 {
 255         if(!ct) return;
 256         de_free(Ctl->c, ct);
 257 }
 258
 259 //*******************************************************************
 260 static void dd_AddMRU (struct dd_Ctl *Ctl, struct dd_codet * ct, u16 tcode)
 261 {
 262         if (ct->usecount[tcode] != 0) {
 263                 dd_tmsg(Ctl, "Usecount not zero in AddMRU, code: %4x", tcode);
 264         }
 265         ct->newer[ct->newest] = tcode;
 266         ct->older[tcode] = ct->newest;
 267         ct->newer[tcode] = 0;
 268         ct->newest = tcode;
 269 }
 270
 271 //*******************************************************************
 272 static void dd_UnlinkCode (struct dd_Ctl *Ctl, struct dd_codet * ct, u16 tcode)
 273 {
 274         u16 tnewer, tolder;
 275
 276         dd_ValidateLinkChains(Ctl, ct, ct->oldest);
 277         tnewer = ct->newer[tcode];
 278         tolder = ct->older[tcode];
 279         if (tcode == ct->newest)
 280                 ct->newest = tolder;
 281         else
 282                 ct->older[tnewer] = tolder;
 283         if (tcode == ct->oldest)
 284                 ct->oldest = tnewer;
 285         else
 286                 ct->newer[tolder] = tnewer;
 287         ct->older[tcode] = ct->newer[tcode] = 0;
 288 }
 289
 290 //*******************************************************************
 291 static u16 dd_GetLRU (struct dd_Ctl *Ctl, struct dd_codet * ct)
 292 {
 293         u16 tcode, xcode;
 294
 295         dd_ValidateLinkChains(Ctl, ct, ct->oldest);
 296         tcode = ct->oldest;
 297         if (ct->usecount[tcode] != 0) {
 298                 dd_tmsg(Ctl, "Usecount not zero in GetLRU, code: %4x", tcode);
 299         }
 300         xcode = ct->charlink[tcode];
 301         dd_UnlinkCode (Ctl, ct, tcode);
 302
 303         if (xcode != 0) {
 304                 ct->usecount[xcode] --;
 305                 if (ct->usecount[xcode] == 0) {
 306                         dd_AddMRU (Ctl, ct, xcode);
 307                 }
 308         }
 309
 310         return (tcode);
 311 }
 312
 313 //*******************************************************************
 314 static void dd_ReserveEntry (struct dd_Ctl *Ctl, struct dd_codet * ct, u16 tcode)
 315 {
 316         if (ct->usecount[tcode] > 0) {
 317                 ct->usecount[tcode] ++;
 318         }
 319         else {
 320                 dd_UnlinkCode(Ctl, ct, tcode);
 321                 ct->usecount[tcode] = 1;
 322         }
 323 }
 324
 325 //*******************************************************************
 326 static void dd_BuildEntry (struct dd_Ctl *Ctl, struct dd_codet * ct, u16 newcode)
 327 {
 328         u16 lruentry, tcode;
 329         int old_codesize;
 330         int new_codesize;
 331         u8 *codestr = NULL;
 332
 333         lruentry = dd_GetLRU(Ctl, ct);
 334         old_codesize = ct->size[ct->oldcode];
 335         if(old_codesize<1) {
 336                 Ctl->err_flag = 1;
 337                 goto done;
 338         }
 339         new_codesize = old_codesize + 1;
 340         if(new_codesize > DD_MAXTABLE) {
 341                 Ctl->err_flag = 1;
 342                 goto done;
 343         }
 344
 345         if (newcode != lruentry) {
 346                 tcode = newcode;
 347         }
 348         else {
 349                 tcode = ct->oldcode;
 350         }
 351
 352         ct->valfirst[lruentry] = ct->valfirst[ct->oldcode];
 353         ct->value[lruentry] = ct->valfirst[tcode];
 354
 355         ct->size[lruentry] = new_codesize;
 356         ct->charlink[lruentry] = ct->oldcode;
 357         dd_ReserveEntry(Ctl, ct, ct->oldcode);
 358         ct->usecount[lruentry] = 0;
 359         dd_AddMRU (Ctl, ct, lruentry);
 360
 361 done:
 362         if(codestr) {
 363                 de_free(Ctl->c, codestr);
 364         }
 365 }
 366
 367 //*******************************************************************
 368 static void dd_Decompress (struct dd_Ctl *Ctl)
 369 {
 370         struct dd_codet * ct;
 371         u16 newcode;
 372
 373         ct = dd_DInit(Ctl);
 374
 375         while(1) {
 376                 newcode = dd_GetNextcode(Ctl, ct);
 377                 if(Ctl->c->debug_level>=3) {
 378                         de_dbg(Ctl->c, "%"I64_FMT" [i%"I64_FMT"/o%"I64_FMT"] code=%u oc=%u",
 379                                 Ctl->code_counter,
 380                                 Ctl->inf_pos, Ctl->nbytes_written,
 381                                 (UI)newcode, (UI)ct->oldcode);
 382                 }
 383                 if(newcode==0 || Ctl->eof_flag || Ctl->err_flag) break;
 384                 if (ct->oldcode > 0)
 385                         dd_BuildEntry(Ctl, ct, newcode);
 386                 if(Ctl->err_flag) break;
 387                 dd_OutputString(Ctl, ct, newcode);
 388                 ct->oldcode = newcode;
 389                 Ctl->code_counter++;
 390         }
 391
 392         if(Ctl->err_flag) {
 393                 de_dfilter_set_errorf(Ctl->c, Ctl->dres, Ctl->modname, "Bad compressed data");
 394         }
 395         dd_DFree(Ctl, ct);
 396 }
 397
 398 static void dskdcmps_run(deark *c, struct de_dfilter_in_params *dcmpri,
 399         struct de_dfilter_out_params *dcmpro, struct de_dfilter_results *dres)
 400 {
 401         struct dd_Ctl *Ctl = NULL;
 402
 403         Ctl = de_malloc(c, sizeof(struct dd_Ctl));
 404         Ctl->c = c;
 405         Ctl->modname = "ibmlzw";
 406         Ctl->dcmpri = dcmpri;
 407         Ctl->dcmpro = dcmpro;
 408         Ctl->dres = dres;
 409         Ctl->inf_pos = dcmpri->pos;
 410         Ctl->inf_endpos = dcmpri->pos + dcmpri->len;
 411
 412         dd_Decompress(Ctl);
 413
 414         de_free(c, Ctl);
 415 }