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_max(a,b) (((a) > (b)) ? (a) : (b))
  32 #define dd_strlen(a) ((int)de_strlen(a))
  33 #define DD_MAXSTRLEN 4096
  34 #define DD_MAXTABLE 4096
  35
  36 struct dd_codet {
  37         u16 hold;
  38         int j;
  39         u16 oldcode, oldest, newest;
  40         u16 older[DD_MAXTABLE], newer[DD_MAXTABLE];
  41         u16 charlink[DD_MAXTABLE], charlast[DD_MAXTABLE], charfirst[DD_MAXTABLE];
  42         int used[DD_MAXTABLE], usecount[DD_MAXTABLE];
  43         int size[DD_MAXTABLE];
  44         u8 *code[DD_MAXTABLE]; // Points to .size[] malloc'd bytes
  45 };
  46
  47 struct dd_Ctl {
  48         deark *c;
  49         struct de_dfilter_in_params *dcmpri;
  50         struct de_dfilter_out_params *dcmpro;
  51         struct de_dfilter_results *dres;
  52         i64 inf_pos;
  53         i64 inf_endpos;
  54         int eof_flag;
  55         int err_flag;
  56         int TraceLevel;
  57         char msg[DD_MAXSTRLEN];
  58 #ifdef DD_EXTRADBG
  59         char work [DD_MAXSTRLEN], work2[DD_MAXSTRLEN], work3[DD_MAXSTRLEN];
  60 #endif
  61 };
  62
  63 //*******************************************************************
  64 static void dd_tmsg(struct dd_Ctl *Ctl, int tracelevel, const char *fmt, ...)
  65         de_gnuc_attribute ((format (printf, 3, 4)));
  66
  67 static void dd_tmsg(struct dd_Ctl *Ctl, int level, const char *fmt, ...)
  68 {
  69         va_list ap;
  70
  71         if (level > Ctl->TraceLevel)
  72                 return;
  73
  74         va_start(ap, fmt);
  75         de_vsnprintf(Ctl->msg, sizeof(Ctl->msg), fmt, ap);
  76         va_end(ap);
  77
  78         de_dbg(Ctl->c, "%s", Ctl->msg);
  79 }
  80
  81 //*******************************************************************
  82 #ifdef DD_EXTRADBG
  83 static char *dd_right (char *target, char *source, int len)
  84 {
  85         int i, tpos, slen;
  86
  87         if (target == NULL)
  88                 return NULL;
  89         if (source == NULL)
  90                 target[0] = '\0';
  91         else {
  92                 slen = dd_strlen(source);
  93                 for (i = dd_max(0, slen - len), tpos = 0; i < slen; i++)
  94                         target [tpos++] = source [i];
  95                 target[tpos] = '\0';
  96         }
  97         return target;
  98 }
  99 #endif
 100
 101 //*******************************************************************
 102 static void dd_PrintEntry (struct dd_Ctl *Ctl, struct dd_codet * ct, u16 tcode)
 103 {
 104         dd_tmsg(Ctl, 1, "Entry code: %4x, usecount: %4x, clink: %4x, clast: %4x, cfirst: %4x",
 105                         tcode, ct->usecount[tcode], ct->charlink[tcode], ct->charlast[tcode],
 106                         ct->charfirst[tcode]);
 107         dd_tmsg(Ctl, 1, "older: %4x, newer: %4x, used: %4d, size: %4d",
 108                         ct->older[tcode], ct->newer[tcode], ct->used[tcode], ct->size[tcode]);
 109 }
 110
 111 //*******************************************************************
 112 static void dd_ValidateLinkChains (struct dd_Ctl *Ctl, struct dd_codet * ct, u16 tcode)
 113 {
 114         u16 tnewer, tolder;
 115
 116         if(Ctl->TraceLevel<1) return;
 117         tnewer = ct->newer[tcode];
 118         tolder = ct->older[tcode];
 119         if (tcode == ct->newest) {
 120                 if (tnewer != 0) {
 121                         dd_tmsg(Ctl, 1, "Newer code not zero. tcode: %4x, newer: %4x, older: %4x",
 122                                 tcode, tnewer, ct->older[tnewer]);
 123                 }
 124         }
 125         else {
 126                 if (ct->older[tnewer] != tcode) {
 127                         dd_tmsg(Ctl, 1, "Older code not linked. tcode: %4x, newer: %4x, older: %4x",
 128                                 tcode, tnewer, ct->older[tnewer]);
 129                 }
 130         }
 131         if (tcode == ct->oldest) {
 132                 if (tolder != 0) {
 133                         dd_tmsg(Ctl, 1, "Older code not zero. tcode: %4x, older: %4x, newer: %4x",
 134                                 tcode, tolder, ct->newer[tolder]);
 135                 }
 136         }
 137         else {
 138                 if (ct->newer[tolder] != tcode) {
 139                         dd_tmsg(Ctl, 1, "Newer code not linked. tcode: %4x, older: %4x, newer: %4x",
 140                                 tcode, tolder, ct->newer[tolder]);
 141                 }
 142         }
 143 }
 144
 145 //*******************************************************************
 146 static void dd_OutputString(struct dd_Ctl *Ctl, struct dd_codet * ct, u16 tcode)
 147 {
 148         dbuf_write(Ctl->dcmpro->f, (const u8*)ct->code[tcode], ct->size[tcode]);
 149 }
 150
 151 //*******************************************************************
 152 static u16 dd_GetNextcode (struct dd_Ctl *Ctl, struct dd_codet * ct)
 153 {
 154         u16 code;
 155
 156         if(Ctl->inf_pos >= Ctl->inf_endpos) {
 157                 Ctl->eof_flag = 1;
 158                 return 0;
 159         }
 160
 161         if (ct->j) {
 162                 code = (u16)dbuf_getbyte_p(Ctl->dcmpri->f, &Ctl->inf_pos) << 4;
 163                 ct->hold = (u16)dbuf_getbyte_p(Ctl->dcmpri->f, &Ctl->inf_pos);
 164                 code |= (ct->hold >> 4);
 165         }
 166         else {
 167                 code = (ct->hold & 0x0f) << 8;
 168                 code |= (u16)dbuf_getbyte_p(Ctl->dcmpri->f, &Ctl->inf_pos);
 169                 ct->hold = 0;
 170         }
 171         ct->j = !ct->j;
 172         return (code);
 173 }
 174
 175 //*******************************************************************
 176 static struct dd_codet * dd_DInit (struct dd_Ctl *Ctl)
 177 {
 178         struct dd_codet * ct;
 179         u16 code;
 180
 181         ct = (struct dd_codet *) de_malloc(Ctl->c, sizeof(struct dd_codet));
 182         for (code = 1; code <= 256; code++) {
 183                 ct->charlast[code] = code;
 184                 ct->charfirst[code] = code;
 185                 ct->code[code] = (u8 *) de_malloc(Ctl->c, 1);
 186                 ct->code[code][0] = (u8)(code-1);
 187                 ct->size[code] = 1;
 188                 ct->usecount[code] = 1;
 189         }
 190         for (code = 257; code <= 4095; code++) {
 191                 if(code<4095) {
 192                         ct->newer[code] = code + 1;
 193                 }
 194                 if(code>257) {
 195                         ct->older[code] = code - 1;
 196                 }
 197         }
 198         ct->oldest = 257;
 199         ct->newest = 4095;
 200         ct->j = 1;
 201         ct->oldcode = 0;
 202         ct->hold = 0;
 203         return (ct);
 204 }
 205
 206 static void dd_DFree(struct dd_Ctl *Ctl, struct dd_codet *ct)
 207 {
 208         UI i;
 209
 210         if(!ct) return;
 211         for(i=0; i<DD_MAXTABLE; i++) {
 212                 if (ct->code[i] != NULL) {
 213                         de_free(Ctl->c, ct->code[i]);
 214                         ct->code[i] = NULL;
 215                         ct->size[i] = 0;
 216                 }
 217         }
 218         de_free(Ctl->c, ct);
 219 }
 220
 221 //*******************************************************************
 222 static void dd_AddMRU (struct dd_Ctl *Ctl, struct dd_codet * ct, u16 tcode)
 223 {
 224         if (ct->usecount[tcode] != 0) {
 225                 dd_tmsg(Ctl, 1, "Usecount not zero in AddMRU, code: %4x", tcode);
 226                 dd_PrintEntry(Ctl, ct, tcode);
 227         }
 228         ct->newer[ct->newest] = tcode;
 229         ct->older[tcode] = ct->newest;
 230         ct->newer[tcode] = 0;
 231         ct->newest = tcode;
 232 }
 233
 234 //*******************************************************************
 235 static void dd_UnlinkCode (struct dd_Ctl *Ctl, struct dd_codet * ct, u16 tcode)
 236 {
 237         u16 tnewer, tolder;
 238
 239         dd_ValidateLinkChains(Ctl, ct, ct->oldest);
 240         tnewer = ct->newer[tcode];
 241         tolder = ct->older[tcode];
 242         if (tcode == ct->newest)
 243                 ct->newest = tolder;
 244         else
 245                 ct->older[tnewer] = tolder;
 246         if (tcode == ct->oldest)
 247                 ct->oldest = tnewer;
 248         else
 249                 ct->newer[tolder] = tnewer;
 250         ct->older[tcode] = ct->newer[tcode] = 0;
 251 }
 252
 253 //*******************************************************************
 254 static u16 dd_GetLRU (struct dd_Ctl *Ctl, struct dd_codet * ct)
 255 {
 256         u16 tcode, xcode;
 257
 258         dd_ValidateLinkChains(Ctl, ct, ct->oldest);
 259         tcode = ct->oldest;
 260         if (ct->usecount[tcode] != 0) {
 261                 dd_tmsg(Ctl, 1, "Usecount not zero in GetLRU, code: %4x", tcode);
 262                 dd_PrintEntry(Ctl, ct, tcode);
 263         }
 264         xcode = ct->charlink[tcode];
 265         dd_UnlinkCode (Ctl, ct, tcode);
 266
 267         if (xcode != 0) {
 268                 ct->usecount[xcode] --;
 269                 if (ct->usecount[xcode] == 0) {
 270                         dd_AddMRU (Ctl, ct, xcode);
 271                 }
 272         }
 273
 274         if (ct->code[tcode] != NULL) {
 275                 de_free(Ctl->c, ct->code[tcode]);
 276                 ct->code[tcode] = NULL;
 277                 ct->size[tcode] = 0;
 278         }
 279
 280         ct->used[tcode] ++;
 281         return (tcode);
 282 }
 283
 284 //*******************************************************************
 285 static void dd_ReserveEntry (struct dd_Ctl *Ctl, struct dd_codet * ct, u16 tcode)
 286 {
 287         if (ct->usecount[tcode] > 0) {
 288                 ct->usecount[tcode] ++;
 289         }
 290         else {
 291                 dd_UnlinkCode(Ctl, ct, tcode);
 292                 ct->usecount[tcode] = 1;
 293         }
 294 }
 295
 296 //*******************************************************************
 297 static void dd_BuildEntry (struct dd_Ctl *Ctl, struct dd_codet * ct, u16 newcode)
 298 {
 299         u16 lruentry, tcode;
 300         int old_codesize;
 301         int new_codesize;
 302         u8 *codestr = NULL;
 303
 304         lruentry = dd_GetLRU(Ctl, ct);
 305         old_codesize = ct->size[ct->oldcode];
 306         if(old_codesize<1 || !ct->code[ct->oldcode]) {
 307                 Ctl->err_flag = 1;
 308                 goto done;
 309         }
 310         new_codesize = old_codesize + 1;
 311         if(new_codesize > DD_MAXTABLE) {
 312                 Ctl->err_flag = 1;
 313                 goto done;
 314         }
 315         // TODO?: This makes a huge total number of memory allocations (though only
 316         // about 4096 will be active at any given time). Mabye it should be rewritten
 317         // to not do that.
 318         codestr = (u8 *) de_malloc(Ctl->c, new_codesize);
 319         de_memcpy(codestr, ct->code[ct->oldcode], (size_t)old_codesize);
 320         if (newcode != lruentry) {
 321                 tcode = newcode;
 322         }
 323         else {
 324                 tcode = ct->oldcode;
 325         }
 326         if(!ct->code[tcode]) {
 327                 Ctl->err_flag = 1;
 328                 goto done;
 329         }
 330         codestr[new_codesize - 1] = ct->code[tcode][0];
 331         ct->code[lruentry] = codestr;
 332         codestr = NULL;
 333         ct->size[lruentry] = new_codesize;
 334         ct->charlink[lruentry] = ct->oldcode;
 335         ct->charfirst[lruentry] = ct->charfirst[ct->charlink[lruentry]];
 336         ct->charlast[lruentry] = tcode;
 337         dd_ReserveEntry(Ctl, ct, ct->oldcode);
 338         dd_AddMRU (Ctl, ct, lruentry);
 339
 340 #ifdef DD_EXTRADBG
 341         if(Ctl->TraceLevel<1) return;
 342         int test;
 343         de_strlcpy(Ctl->work, "", sizeof(Ctl->work));
 344         for (test = 0; test < new_codesize; test++) {
 345                 de_snprintf(Ctl->work2, sizeof(Ctl->work2), "%2x", codestr[test]);
 346                 dd_right(Ctl->work3, Ctl->work2, 2);
 347                 strcat(Ctl->work, Ctl->work3);
 348         }
 349         dd_tmsg(Ctl, 1, "offset: %4x, newcode: %4x. nused: %4x, lru: %4x, lused: %4x, size: %4d, str: %s",
 350                 (UI)Ctl->inf_pos, newcode, ct->used[newcode], lruentry, ct->used[lruentry], new_codesize, Ctl->work);
 351 #endif
 352
 353 done:
 354         if(codestr) {
 355                 de_free(Ctl->c, codestr);
 356         }
 357 }
 358
 359 //*******************************************************************
 360 static void dd_Decompress (struct dd_Ctl *Ctl)
 361 {
 362         struct dd_codet * ct;
 363         u16 newcode;
 364
 365         ct = dd_DInit(Ctl);
 366
 367         while(1) {
 368                 newcode = dd_GetNextcode(Ctl, ct);
 369                 if(newcode==0 || Ctl->eof_flag || Ctl->err_flag) break;
 370                 if (ct->oldcode > 0)
 371                         dd_BuildEntry(Ctl, ct, newcode);
 372                 if(Ctl->err_flag) break;
 373                 dd_OutputString(Ctl, ct, newcode);
 374                 ct->oldcode = newcode;
 375         }
 376
 377         if(Ctl->err_flag) {
 378                 de_dfilter_set_errorf(Ctl->c, Ctl->dres, "dskdcmprs", "Bad compressed data");
 379         }
 380         dd_DFree(Ctl, ct);
 381 }
 382
 383 static void dskdcmps_run(deark *c, struct de_dfilter_in_params *dcmpri,
 384         struct de_dfilter_out_params *dcmpro, struct de_dfilter_results *dres)
 385 {
 386         struct dd_Ctl *Ctl = NULL;
 387
 388         Ctl = de_malloc(c, sizeof(struct dd_Ctl));
 389         Ctl->c = c;
 390         Ctl->dcmpri = dcmpri;
 391         Ctl->dcmpro = dcmpro;
 392         Ctl->dres = dres;
 393         Ctl->inf_pos = dcmpri->pos;
 394         Ctl->inf_endpos = dcmpri->pos + dcmpri->len;
 395         Ctl->TraceLevel = 0;
 396         if(c->debug_level>=3) {
 397                 Ctl->TraceLevel = 1;
 398         }
 399
 400         dd_Decompress(Ctl);
 401
 402         de_free(c, Ctl);
 403 }