oldpakerz/wdx.d

   1 /*
   2  * original code: WDOSX-Pack v1.07, (c) 1999-2001 by Joergen Ibsen / Jibz
   3  * for data and executable compression software: http://www.ibsensoftware.com/
   4  */
   5 module iv.oldpakerz.wdx /*is aliced*/;
   6 private:
   7 import iv.alice;
   8
   9
  10 // ////////////////////////////////////////////////////////////////////////// //
  11 enum WDXUNPACK_LEN2_LIMIT = 1920;
  12
  13
  14 public usize wdx_packbuf_size (usize size_in) {
  15   if (size_in < 1) return 0;
  16   return size_in+((size_in+7)/8)+2;
  17 }
  18
  19
  20 struct match_t {
  21   uint pos;
  22   uint len;
  23 }
  24
  25
  26 struct pack_state_t {
  27   uint next_back_entry;
  28   ubyte *tag_byte;
  29   int bit_count;
  30   uint *back_tbl; /* back-table, array */
  31   const(ubyte)* bufin, srcofs, backptr;
  32   ubyte *bufout;
  33   uint *lookup; /* lookup-table [256][256] */
  34   uint last_match_pos;
  35   int last_was_match;
  36   uint bytes_out;
  37   usize size_out;
  38 }
  39
  40
  41 void wdxi_adv_tag_byte (pack_state_t *ps, uint bit) {
  42   /* check bitcount and then decrement */
  43   if (ps.bit_count-- == 0) {
  44     if (ps.size_out-- == 0) throw new Exception("wdx error");
  45     ps.bit_count = 7;
  46     ps.tag_byte = ps.bufout++;
  47     *ps.tag_byte = 0;
  48     ++ps.bytes_out;
  49   }
  50   /* shift in bit */
  51   *ps.tag_byte = cast(ubyte)(((*ps.tag_byte)<<1)|(bit ? 1 : 0));
  52 }
  53
  54
  55 /* output Gamma2-code for val in range [2..?] ... */
  56 void wdxi_out_gamma (pack_state_t *ps, uint val) {
  57   uint invertlen = 0, invert = 0;
  58   /* rotate bits into invert (except last) */
  59   do {
  60     invert = (invert<<1)|(val&0x01);
  61     ++invertlen;
  62     val = (val>>1)&0x7FFFFFFF;
  63   } while (val > 1);
  64   /* output Gamma2-encoded bits */
  65   for (--invertlen; invertlen > 0; --invertlen) {
  66     wdxi_adv_tag_byte(ps, invert&0x01);
  67     wdxi_adv_tag_byte(ps, 1);
  68     invert >>= 1;
  69   }
  70   wdxi_adv_tag_byte(ps, invert&0x01);
  71   wdxi_adv_tag_byte(ps, 0);
  72 }
  73
  74
  75 void wdxi_out_lit (pack_state_t *ps, ubyte lit) {
  76   ps.last_was_match = 0;
  77   wdxi_adv_tag_byte(ps, 0); /* 0 indicates a literal */
  78   if (ps.size_out-- == 0) throw new Exception("wdx error");
  79   *ps.bufout++ = lit; /* output the literal */
  80   ++ps.bytes_out;
  81 }
  82
  83
  84 void wdxi_out_pair (pack_state_t *ps, uint pos, uint len, const ubyte *buffer) {
  85   /* if we just had a match, don't use ps.last_match_pos */
  86   if (ps.last_was_match) {
  87     /* if a short match is too far away, encode it as two literals instead */
  88     if (pos > WDXUNPACK_LEN2_LIMIT && len == 2) {
  89       wdxi_out_lit(ps, buffer[0]);
  90       wdxi_out_lit(ps, buffer[1]);
  91     } else {
  92       wdxi_adv_tag_byte(ps, 1); /* 1 indicates a match */
  93       /* a match more than WDXUNPACK_LEN2_LIMIT bytes back will be longer than 2 */
  94       if (pos > WDXUNPACK_LEN2_LIMIT) --len;
  95       wdxi_out_gamma(ps, len); /* output length */
  96       ps.last_match_pos = pos--;
  97       /*assert(pos >= 0);*/
  98       wdxi_out_gamma(ps, ((pos>>6)&0x3FFFFFFF)+2); /* output high part of position */
  99       /* output low 6 bits of position */
 100       wdxi_adv_tag_byte(ps, pos&0x20);
 101       wdxi_adv_tag_byte(ps, pos&0x10);
 102       wdxi_adv_tag_byte(ps, pos&0x08);
 103       wdxi_adv_tag_byte(ps, pos&0x04);
 104       wdxi_adv_tag_byte(ps, pos&0x02);
 105       wdxi_adv_tag_byte(ps, pos&0x01);
 106     }
 107   } else {
 108     ps.last_was_match = 1;
 109     /* if a short match is too far away, encode it as two literals instead */
 110     if (pos > WDXUNPACK_LEN2_LIMIT && len == 2 && pos != ps.last_match_pos) {
 111       wdxi_out_lit(ps, buffer[0]);
 112       wdxi_out_lit(ps, buffer[1]);
 113     } else {
 114       wdxi_adv_tag_byte(ps, 1); /* 1 indicates a match */
 115       /* a match more than WDXUNPACK_LEN2_LIMIT bytes back will be longer than 2 */
 116       if (pos > WDXUNPACK_LEN2_LIMIT && pos != ps.last_match_pos) --len;
 117       wdxi_out_gamma(ps, len); /* output length */
 118       /* output position */
 119       if (pos == ps.last_match_pos) {
 120         /* a match with position 0 means use last position */
 121         wdxi_adv_tag_byte(ps, 0);
 122         wdxi_adv_tag_byte(ps, 0);
 123       } else {
 124         ps.last_match_pos = pos--;
 125         /*assert(pos >= 0);*/
 126         wdxi_out_gamma(ps, ((pos>>6)&0x3FFFFFFF)+3); /* output high part of position */
 127         /* output low 6 bits of position */
 128         wdxi_adv_tag_byte(ps, pos&0x20);
 129         wdxi_adv_tag_byte(ps, pos&0x10);
 130         wdxi_adv_tag_byte(ps, pos&0x08);
 131         wdxi_adv_tag_byte(ps, pos&0x04);
 132         wdxi_adv_tag_byte(ps, pos&0x02);
 133         wdxi_adv_tag_byte(ps, pos&0x01);
 134       }
 135     }
 136   }
 137 }
 138
 139
 140 void wdxi_find_match (pack_state_t *ps, match_t *thematch, const ubyte *buffer, uint lookback, uint lookforward) {
 141   uint back_pos, match_len, best_match_len, best_match_pos;
 142   const(ubyte)* ptr;
 143   uint idx0, idx1;
 144   /* temporary variables to avoid indirect addressing into the match */
 145   best_match_len = 0;
 146   best_match_pos = 0;
 147   /* update ps.lookup- and backtable up to current position */
 148   while (ps.backptr < buffer) {
 149     idx0 = ps.backptr[0];
 150     idx1 = ps.backptr[1];
 151     ps.back_tbl[ps.next_back_entry] = ps.lookup[idx0*256+idx1];
 152     ps.lookup[idx0*256+idx1] = ps.next_back_entry;
 153     ++ps.next_back_entry;
 154     ++ps.backptr;
 155   }
 156   /* get position by looking up next two bytes */
 157   back_pos = ps.lookup[buffer[0]*256+buffer[1]];
 158   if (back_pos != 0 && lookforward > 1) {
 159     ptr = back_pos+ps.srcofs;
 160     /* go backwards until before buffer */
 161     while (ptr >= buffer && back_pos != 0) {
 162       /*back_pos := PInt(Integer(ps.back_tbl)+back_pos*4)^;*/
 163       back_pos = ps.back_tbl[back_pos];
 164       ptr = back_pos+ps.srcofs;
 165     }
 166     /* search through table entries */
 167     while (back_pos != 0 && buffer-ptr <= lookback) {
 168       match_len = 2;
 169       /* if this position has a chance to be better */
 170       if (*(ptr+best_match_len) == *(buffer+best_match_len)) {
 171         /* scan it */
 172         while (match_len < lookforward && *(ptr+match_len) == *(buffer+match_len)) ++match_len;
 173         /* check it */
 174         if (match_len+(buffer-ptr == ps.last_match_pos) > best_match_len+(best_match_pos == ps.last_match_pos)) {
 175           best_match_len = match_len;
 176           if (best_match_len == lookforward) back_pos = 0;
 177           best_match_pos = buffer-ptr;
 178         }
 179       }
 180       /* move backwards to next position */
 181       back_pos = ps.back_tbl[back_pos];
 182       ptr = back_pos+ps.srcofs;
 183     }
 184   }
 185   /* forget match if too far away */
 186   if (best_match_pos > WDXUNPACK_LEN2_LIMIT && best_match_len == 2 && best_match_pos != ps.last_match_pos) {
 187     best_match_len = 0;
 188     best_match_pos = 0;
 189   }
 190   /* update the match with best match */
 191   thematch.len = best_match_len;
 192   thematch.pos = best_match_pos;
 193 }
 194
 195
 196 // ////////////////////////////////////////////////////////////////////////// //
 197 public ssize wdx_pack (void *buf_out, usize size_out, const(void)* buf_in, usize size_in) {
 198   import core.stdc.stdlib : malloc, free;
 199   import core.stdc.string : memset;
 200   /* global variables */
 201   pack_state_t ps;
 202   match_t match, nextmatch, literalmatch, testmatch;
 203   uint pos, lastpos, literalCount;
 204   uint i0, i1;
 205   /* main code */
 206   if (size_in < 1) return 0;
 207   if (size_out < 2) return -1;
 208   /* init ps */
 209   ps.bufin = cast(const(ubyte)*)buf_in;
 210   ps.bufout = cast(ubyte*)buf_out;
 211   ps.lookup = null; /* lookup-table [256][256] */
 212   ps.last_match_pos = 0;
 213   ps.last_was_match = 0;
 214   ps.bytes_out = 0;
 215   ps.size_out = size_out;
 216   /* alloc memory */
 217   if ((ps.back_tbl = cast(uint*)malloc((size_in+4)*4)) is null) return -2; /* out of memory */
 218   if ((ps.lookup = cast(uint*)malloc(256*256*4)) is null) { free(ps.back_tbl); return -2; } /* out of memory */
 219   scope(exit) {
 220     free(ps.lookup);
 221     free(ps.back_tbl);
 222   }
 223   /* go on */
 224   memset(&match, 0, match.sizeof);
 225   memset(&nextmatch, 0, nextmatch.sizeof);
 226   memset(&literalmatch, 0, literalmatch.sizeof);
 227   memset(&testmatch, 0, testmatch.sizeof);
 228   literalmatch.pos = literalmatch.len = 0;
 229   ps.srcofs = ps.bufin-1;
 230   /* init ps.lookup- and backtable */
 231   memset(ps.lookup, 0, 256*256*4);
 232   memset(ps.back_tbl, 0, (size_in+4)*4);
 233   ps.backptr = ps.bufin;
 234   ps.back_tbl[0] = 0;
 235   ps.next_back_entry = 1;
 236   lastpos = -1;
 237   ps.last_match_pos = -1;
 238   ps.last_was_match = 0;
 239   literalCount = 0;
 240   /* the first byte is sent verbatim */
 241   *ps.bufout++ = *ps.bufin++;
 242   --size_out;
 243   ++ps.bytes_out;
 244   /* init tag-byte */
 245   ps.bit_count = 8;
 246   *(ps.tag_byte = ps.bufout++) = 0;
 247   --size_out;
 248   ++ps.bytes_out;
 249   /* pack data */
 250   pos = 1;
 251   while (pos < size_in) {
 252     /* find best match at current position (if not already found) */
 253     if (pos == lastpos) {
 254       match.len = nextmatch.len;
 255       match.pos = nextmatch.pos;
 256     } else {
 257       wdxi_find_match(&ps, &match, ps.bufin, pos, size_in-pos);
 258     }
 259     /* if we found a match, find the best match at the next position */
 260     if (match.len != 0) {
 261       wdxi_find_match(&ps, &nextmatch, ps.bufin+1, pos+1, size_in-(pos+1));
 262       lastpos = pos+1;
 263     } else {
 264       nextmatch.len = 0;
 265     }
 266     /* decide if we should output a match or a literal */
 267     i0 = (match.pos==ps.last_match_pos ? 1 : 0);
 268     i1 = (nextmatch.pos==ps.last_match_pos ? 1 : 0);
 269     if (match.len != 0 && match.len+i0 >= nextmatch.len+i1) {
 270       /* output any pending literals */
 271       if (literalCount != 0) {
 272         if (literalCount == 1) {
 273           wdxi_out_lit(&ps, ps.bufin[-1]);
 274         } else {
 275           /* check if there is a closer match with the required length */
 276           wdxi_find_match(&ps, &testmatch, ps.bufin-literalCount, literalmatch.pos, literalCount);
 277           if (testmatch.len >= literalCount) {
 278             wdxi_out_pair(&ps, testmatch.pos, literalCount, ps.bufin-literalCount);
 279           } else {
 280             wdxi_out_pair(&ps, literalmatch.pos, literalCount, ps.bufin-literalCount);
 281           }
 282         }
 283         literalCount = 0;
 284       }
 285       /* output match */
 286       wdxi_out_pair(&ps, match.pos, match.len, ps.bufin);
 287       ps.bufin += match.len;
 288       pos += match.len;
 289     } else {
 290       /* check if we are allready collecting literals */
 291       if (literalCount != 0) {
 292         /* if so, continue.. */
 293         ++literalCount;
 294         /* have we collected as many as possible? */
 295         if (literalCount == literalmatch.len) {
 296           wdxi_out_pair(&ps, literalmatch.pos, literalCount, ps.bufin-literalCount+1);
 297           literalCount = 0;
 298         }
 299       } else {
 300         /* if we had a match which was not good enough, then save it.. */
 301         if (match.len != 0) {
 302           literalmatch.len = match.len;
 303           literalmatch.pos = match.pos;
 304           ++literalCount;
 305         } else {
 306           /* if not, we have to output the literal now */
 307           wdxi_out_lit(&ps, ps.bufin[0]);
 308         }
 309       }
 310       ++ps.bufin;
 311       ++pos;
 312     }
 313   }
 314   /* output any remaining literal bytes */
 315   if (literalCount != 0) {
 316     if (literalCount == 1) {
 317       wdxi_out_lit(&ps, ps.bufin[-1]);
 318     } else {
 319       wdxi_out_pair(&ps, literalmatch.pos, literalCount, ps.bufin-literalCount);
 320     }
 321   }
 322   /* switch last ps.tag_byte into position */
 323   if (ps.bit_count != 8) *ps.tag_byte <<= ps.bit_count;
 324   //
 325   return ps.bytes_out;
 326 }
 327
 328
 329 // ////////////////////////////////////////////////////////////////////////// //
 330 public ssize wdx_unpack (void *buf_out, usize size_out, const(void)* buf_in, usize size_in) {
 331   int len, pos, b, itsOk;
 332   ubyte *pp;
 333   const(ubyte)* src = cast(const ubyte *)buf_in;
 334   ubyte *dest = cast(ubyte*)buf_out;
 335   ubyte fbyte = 0;
 336   int last_match_pos = 0, last_was_match = 0, bCount = 0, origOutSz = size_out;
 337   /* main code */
 338   if (size_out < 1) return 0;
 339   if (size_in < 1) return -1; /* out of input data */
 340
 341   auto WDXU_GET_BIT () {
 342     int res;
 343     if (bCount <= 0) {
 344       if (size_in < 1) throw new Exception("wdx error");
 345       fbyte = *src++;
 346       --size_in;
 347       bCount = 8;
 348     }
 349     res = (fbyte&0x80 ? 1 : 0);
 350     fbyte = (fbyte&0x7f)<<1;
 351     --bCount;
 352     return res;
 353   }
 354
 355   auto WDXU_GET_GAMMA () {
 356     int res = 1;
 357     do {
 358       res = (res<<1)|WDXU_GET_BIT();
 359     } while (WDXU_GET_BIT() == 1);
 360     return res;
 361   }
 362
 363   /* get 6 low bits of position */
 364   auto WDXU_GET_LO_POS (int _pos) {
 365     int ps = _pos;
 366     for (int f = 0; f < 6; ++f) ps = (ps<<1)|WDXU_GET_BIT();
 367     return ps;
 368   }
 369
 370   /* the first byte was sent verbatim */
 371   *dest++ = *src++;
 372   --size_in;
 373   --size_out;
 374   while (size_out > 0) {
 375     itsOk = 1;
 376     b = WDXU_GET_BIT();
 377     itsOk = 0;
 378     if (b == 0) {
 379       /* literal */
 380       if (size_in < 1) break;
 381       if (size_out == 0) return -1;
 382       *dest++ = *src++;
 383       --size_in;
 384       --size_out;
 385       last_was_match = 0;
 386     } else {
 387       /* match */
 388       len = WDXU_GET_GAMMA();
 389       if (last_was_match) {
 390         pos = WDXU_GET_GAMMA()-2;
 391         pos = WDXU_GET_LO_POS(pos)+1;
 392         last_match_pos = pos;
 393         if (pos > WDXUNPACK_LEN2_LIMIT) ++len;
 394       } else {
 395         last_was_match = 1;
 396         pos = WDXU_GET_GAMMA()-2;
 397         /* same position as last match? */
 398         if (pos == 0) {
 399           pos = last_match_pos;
 400         } else {
 401           pos = WDXU_GET_LO_POS(pos-1)+1;
 402           last_match_pos = pos;
 403           if (pos > WDXUNPACK_LEN2_LIMIT) ++len;
 404         }
 405       }
 406       /* copy match */
 407       /*FIXME: wrapping*/
 408       pp = dest-pos;
 409       if (cast(void*)pp < cast(void*)buf_out) return -1; /* shit! */
 410       if (size_out < len) return -1;
 411       for (; len > 0 && size_out > 0; --size_out, --len) *dest++ = *pp++;
 412     }
 413   }
 414   return origOutSz-size_out;
 415 //wdxu_error:
 416   /* decompressing error */
 417   if (!itsOk) return -1;
 418   return origOutSz-size_out;
 419 }