dlzma/refdec.d

   1 /* converted by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
   2  * Understanding is not required. Only obedience.
   3  *
   4  * This program is free software. It comes without any warranty, to
   5  * the extent permitted by applicable law. You can redistribute it
   6  * and/or modify it under the terms of the Do What The Fuck You Want
   7  * To Public License, Version 2, as published by Sam Hocevar. See
   8  * http://www.wtfpl.net/txt/copying/ for more details.
   9  */
  10 // LZMA Reference Decoder
  11 // 2015-06-14 : Igor Pavlov : Public domain
  12 // This code implements LZMA file decoding according to LZMA specification.
  13 // This code is not optimized for speed.
  14 module iv.dlzma.refdec;
  15
  16 /*
  17 usage:
  18
  19   CLzmaDecoder lzmaDecoder;
  20
  21   ubyte[5] header = void; // lzma properties
  22   fi.rawReadExact(header[]);
  23   lzmaDecoder.decodeProperties(header.ptr);
  24   lzmaDecoder.markerIsMandatory = false;
  25   lzmaDecoder.create(totalUnpackedSize);
  26
  27   main_loop: for (;;) {
  28     auto res = lzmaDecoder.decodeStep(
  29       delegate () { ubyte b; fi.rawReadExact((&b)[0..1]); return b; },
  30       (ubyte b) { fo.rawWriteExact((&b)[0..1]); }
  31     );
  32     switch (res) {
  33       case CLzmaDecoder.Result.Continue: break;
  34       case CLzmaDecoder.Result.Error: throw new VFSException("LZMA stream corrupted");
  35       case CLzmaDecoder.Result.FinishedWithMarker:
  36       case CLzmaDecoder.Result.FinishedWithoutMarker:
  37         break main_loop;
  38       default: assert(0, "LZMA internal error");
  39     }
  40   }
  41 */
  42
  43
  44 // ////////////////////////////////////////////////////////////////////////// //
  45 struct CLzmaDecoder {
  46 public:
  47   enum Result {
  48     Error = -1,
  49     Continue = 0,
  50     FinishedWithMarker = 1,
  51     FinishedWithoutMarker = 2,
  52   }
  53
  54 private:
  55   CProb[kNumStates<<kNumPosBitsMax] isMatch;
  56   CProb[kNumStates] isRep;
  57   CProb[kNumStates] isRepG0;
  58   CProb[kNumStates] isRepG1;
  59   CProb[kNumStates] isRepG2;
  60   CProb[kNumStates<<kNumPosBitsMax] isRep0Long;
  61
  62   CLenDecoder lenDecoder;
  63   CLenDecoder repLenDecoder;
  64
  65   CProb* litProbs;
  66   usize litProbsAllotedBytes;
  67   CBitTreeDecoder!6[kNumLenToPosStates] posSlotDecoder;
  68   CBitTreeDecoder!kNumAlignBits alignDecoder;
  69   CProb[1+kNumFullDistances-kEndPosModelIndex] posDecoders;
  70
  71   uint rep0, rep1, rep2, rep3;
  72   uint state;
  73   bool unpackSizeDefined;
  74   ulong unpackSize;
  75
  76 public:
  77   CRangeDecoder rangeDec;
  78   COutWindow outWindow;
  79
  80   bool markerIsMandatory;
  81   uint lc, pb, lp;
  82   uint dictSize;
  83   uint dictSizeInProperties;
  84   bool inited;
  85
  86   //@disable this (this);
  87
  88   void close () {
  89     import core.stdc.stdlib : free;
  90     if (litProbs !is null) free(litProbs);
  91     litProbs = null;
  92     inited = false;
  93     outWindow.close();
  94   }
  95
  96   void decodeProperties (const(ubyte)* properties) {
  97     enum LZMAMinDictSize = 1U<<12;
  98     uint d = properties[0];
  99     if (d >= 9*5*5) throw new Exception("Incorrect LZMA properties");
 100     lc = d%9;
 101     d /= 9;
 102     pb = d/5;
 103     lp = d%5;
 104     dictSizeInProperties = 0;
 105     for (int i = 0; i < 4; ++i) dictSizeInProperties |= cast(uint)properties[i+1]<<(8*i);
 106     dictSize = dictSizeInProperties;
 107     if (dictSize < LZMAMinDictSize) dictSize = LZMAMinDictSize;
 108   }
 109
 110   void create (ulong aunpackSize) {
 111     inited = false;
 112     unpackSizeDefined = true;
 113     unpackSize = aunpackSize;
 114   }
 115
 116   void create () {
 117     inited = false;
 118     unpackSizeDefined = false;
 119     unpackSize = 0;
 120   }
 121
 122
 123   Result decodeStep (scope ubyte delegate () readByte, scope void delegate (ubyte b) writeByte) {
 124     void decodeLiteral (uint state, uint rep0) {
 125       uint prevByte = 0;
 126       if (!outWindow.isEmpty()) prevByte = outWindow.getByte(1);
 127
 128       uint symbol = 1;
 129       uint litState = ((outWindow.totalPos&((1<<lp)-1))<<lc)+(prevByte>>(8-lc));
 130       CProb* probs = litProbs+(0x300U*litState);
 131
 132       if (state >= 7) {
 133         uint matchByte = outWindow.getByte(rep0+1);
 134         do {
 135           uint matchBit = (matchByte>>7)&1;
 136           matchByte <<= 1;
 137           uint bit = rangeDec.decodeBit(&probs[((1+matchBit)<<8)+symbol], readByte);
 138           symbol = (symbol<<1)|bit;
 139           if (matchBit != bit) break;
 140         } while (symbol < 0x100);
 141       } while (symbol < 0x100)
 142       symbol = (symbol<<1)|rangeDec.decodeBit(&probs[symbol], readByte);
 143       outWindow.putByte(cast(ubyte)(symbol-0x100), writeByte);
 144     }
 145
 146     uint decodeDistance (uint len) {
 147       uint lenState = len;
 148       if (lenState > kNumLenToPosStates-1) lenState = kNumLenToPosStates-1;
 149
 150       uint posSlot = posSlotDecoder[lenState].decode(rangeDec, readByte);
 151       if (posSlot < 4) return posSlot;
 152
 153       uint numDirectBits = cast(uint)((posSlot>>1)-1);
 154       uint dist = ((2|(posSlot&1))<<numDirectBits);
 155       if (posSlot < kEndPosModelIndex) {
 156         dist += bitTreeReverseDecode(posDecoders.ptr+dist-posSlot, numDirectBits, rangeDec, readByte);
 157       } else {
 158         dist += rangeDec.decodeDirectBits(numDirectBits-kNumAlignBits, readByte)<<kNumAlignBits;
 159         dist += alignDecoder.reverseDecode(rangeDec, readByte);
 160       }
 161       return dist;
 162     }
 163
 164     if (!inited) {
 165       inited = true;
 166       outWindow.create(dictSize);
 167       createLiterals();
 168       if (!rangeDec.initialize(readByte)) throw new Exception("can't initialize lzma range decoder");
 169       initialize();
 170       rep0 = rep1 = rep2 = rep3 = 0;
 171       state = 0;
 172     }
 173
 174     if (unpackSizeDefined && unpackSize == 0 && !markerIsMandatory) {
 175       if (rangeDec.isFinishedOK()) return Result.FinishedWithoutMarker;
 176     }
 177
 178     uint posState = outWindow.totalPos&((1<<pb)-1);
 179
 180     if (rangeDec.decodeBit(&isMatch[(state<<kNumPosBitsMax)+posState], readByte) == 0) {
 181       if (unpackSizeDefined && unpackSize == 0) return Result.Error;
 182       decodeLiteral(state, rep0);
 183       state = updateStateLiteral(state);
 184       --unpackSize;
 185       return Result.Continue;
 186     }
 187
 188     uint len;
 189
 190     if (rangeDec.decodeBit(&isRep[state], readByte) != 0) {
 191       if (unpackSizeDefined && unpackSize == 0) return Result.Error;
 192       if (outWindow.isEmpty()) return Result.Error;
 193       if (rangeDec.decodeBit(&isRepG0[state], readByte) == 0) {
 194         if (rangeDec.decodeBit(&isRep0Long[(state<<kNumPosBitsMax)+posState], readByte) == 0) {
 195           state = updateStateShortRep(state);
 196           outWindow.putByte(outWindow.getByte(rep0+1), writeByte);
 197           --unpackSize;
 198           return Result.Continue;
 199         }
 200       } else {
 201         uint dist;
 202         if (rangeDec.decodeBit(&isRepG1[state], readByte) == 0) {
 203           dist = rep1;
 204         } else {
 205           if (rangeDec.decodeBit(&isRepG2[state], readByte) == 0) {
 206             dist = rep2;
 207           } else {
 208             dist = rep3;
 209             rep3 = rep2;
 210           }
 211           rep2 = rep1;
 212         }
 213         rep1 = rep0;
 214         rep0 = dist;
 215       }
 216       len = repLenDecoder.decode(rangeDec, posState, readByte);
 217       state = updateStateRep(state);
 218     } else {
 219       rep3 = rep2;
 220       rep2 = rep1;
 221       rep1 = rep0;
 222       len = lenDecoder.decode(rangeDec, posState, readByte);
 223       state = updateStateMatch(state);
 224       rep0 = decodeDistance(len);
 225       if (rep0 == 0xFFFFFFFF) return (rangeDec.isFinishedOK() ? Result.FinishedWithMarker : Result.Error);
 226       if (unpackSizeDefined && unpackSize == 0) return Result.Error;
 227       if (rep0 >= dictSize || !outWindow.checkDistance(rep0)) return Result.Error;
 228     }
 229     len += kMatchMinLen;
 230     bool isError = false;
 231     if (unpackSizeDefined && unpackSize < len) {
 232       len = cast(uint)unpackSize;
 233       isError = true;
 234     }
 235     outWindow.copyMatch(rep0+1, len, writeByte);
 236     unpackSize -= len;
 237     if (isError) return Result.Error;
 238     return Result.Continue;
 239   }
 240
 241 private:
 242   void createLiterals () {
 243     //litProbs = new CProb[](0x300U<<(lc+lp));
 244     import core.stdc.stdlib : realloc;
 245     //import core.stdc.string : memset;
 246     usize toalloc = (0x300U<<(lc+lp))*CProb.sizeof;
 247     if (litProbs is null || toalloc > litProbsAllotedBytes) {
 248       auto nb = cast(CProb*)realloc(litProbs, toalloc);
 249       if (nb is null) throw new Exception("LZMA: out of memory");
 250       litProbsAllotedBytes = toalloc;
 251       litProbs = nb;
 252     }
 253     //memset(litProbs, 0, (0x300U<<(lc+lp))*CProb.sizeof);
 254   }
 255
 256   void initLiterals () {
 257     uint num = 0x300U<<(lc+lp);
 258     //for (uint i = 0; i < num; ++i) litProbs[i] = ProbInitValue;
 259     litProbs[0..num] = ProbInitValue;
 260   }
 261
 262   void initDist () {
 263     for (uint i = 0; i < kNumLenToPosStates; i++) posSlotDecoder[i].initialize();
 264     alignDecoder.initialize();
 265     posDecoders[] = ProbInitValue;
 266   }
 267
 268   void initialize () {
 269     initLiterals();
 270     initDist();
 271
 272     isMatch[] = ProbInitValue;
 273     isRep[] = ProbInitValue;
 274     isRepG0[] = ProbInitValue;
 275     isRepG1[] = ProbInitValue;
 276     isRepG2[] = ProbInitValue;
 277     isRep0Long[] = ProbInitValue;
 278
 279     lenDecoder.initialize();
 280     repLenDecoder.initialize();
 281   }
 282
 283 static:
 284   struct COutWindow {
 285   private:
 286     ubyte* buf;
 287     uint pos;
 288     uint size;
 289     uint bufsize;
 290     bool isFull;
 291
 292   public:
 293     uint totalPos;
 294
 295     //@disable this (this);
 296
 297     void close () {
 298       import core.stdc.stdlib : free;
 299       if (buf !is null) {
 300         //{ import core.stdc.stdio : printf; printf("LZMA: freeing: buf=%p; bufsize=%u\n", buf, bufsize); }
 301         free(buf);
 302         buf = null;
 303       }
 304     }
 305
 306     void create (uint dictSize) @trusted {
 307       import core.stdc.stdlib : realloc;
 308       if (buf is null || bufsize < dictSize) {
 309         auto nb = cast(ubyte*)realloc(buf, dictSize);
 310         if (nb is null) {
 311           //{ import core.stdc.stdio : printf; printf("*** buf=%p; nb=%p; bufsize=%u; dictSize=%u\n", buf, nb, bufsize, dictSize); }
 312           throw new Exception("LZMA: cannot allocate sliding window");
 313         }
 314         buf = nb;
 315         bufsize = dictSize;
 316       }
 317       size = dictSize;
 318       reset();
 319     }
 320
 321     void reset () {
 322       pos = 0;
 323       isFull = false;
 324       totalPos = 0;
 325       buf[0..size] = 0; // just in case
 326     }
 327
 328     ubyte getByte (uint dist) const pure nothrow @trusted @nogc { pragma(inline, true); return (buf[dist <= pos ? pos-dist : size-dist+pos]); }
 329
 330     void putByte (ubyte b, scope void delegate (ubyte b) writeByte) {
 331       ++totalPos;
 332       buf[pos++] = b;
 333       if (pos == size) { pos = 0; isFull = true; }
 334       writeByte(b);
 335     }
 336
 337     void copyMatch (uint dist, uint len, scope void delegate (ubyte b) writeByte) {
 338       pragma(inline, true);
 339       while (len--) {
 340         //putByte(getByte(dist));
 341         ubyte b = getByte(dist);
 342         ++totalPos;
 343         buf[pos++] = b;
 344         if (pos == size) { pos = 0; isFull = true; }
 345         writeByte(b);
 346       }
 347     }
 348
 349     bool checkDistance (uint dist) const pure nothrow @trusted @nogc { pragma(inline, true); return (dist <= pos || isFull); }
 350
 351     bool isEmpty () const pure nothrow @trusted @nogc { pragma(inline, true); return (pos == 0 && !isFull); }
 352   }
 353
 354
 355   enum kNumBitModelTotalBits = 11;
 356   enum kNumMoveBits = 5;
 357
 358   alias CProb = ushort;
 359
 360   enum ProbInitValue = (1U<<kNumBitModelTotalBits)/2;
 361
 362
 363   struct CRangeDecoder {
 364   private:
 365     enum kTopValue = 1U<<24;
 366
 367     uint range;
 368     uint code;
 369
 370   private:
 371     void normalize (scope ubyte delegate () readByte) {
 372       if (range < kTopValue) {
 373         range <<= 8;
 374         code = (code<<8)|readByte();
 375       }
 376     }
 377
 378   public:
 379     bool corrupted;
 380
 381     //@disable this (this);
 382
 383     bool initialize (scope ubyte delegate () readByte) {
 384       corrupted = false;
 385       range = 0xFFFFFFFFU;
 386       code = 0;
 387       ubyte b = readByte();
 388       for (int i = 0; i < 4; i++) code = (code<<8)|readByte();
 389       if (b != 0 || code == range) corrupted = true;
 390       return (b == 0);
 391     }
 392
 393     bool isFinishedOK () const pure nothrow @safe @nogc { pragma(inline, true); return (code == 0); }
 394
 395     uint decodeDirectBits (uint numBits, scope ubyte delegate () readByte) {
 396       uint res = 0;
 397       do {
 398         range >>= 1;
 399         code -= range;
 400         uint t = 0U-(cast(uint)code>>31);
 401         code += range&t;
 402         if (code == range) corrupted = true;
 403         normalize(readByte);
 404         res <<= 1;
 405         res += t+1;
 406       } while (--numBits);
 407       return res;
 408     }
 409
 410     uint decodeBit (CProb* prob, scope ubyte delegate () readByte) {
 411       uint v = *prob;
 412       uint bound = (range>>kNumBitModelTotalBits)*v;
 413       uint symbol;
 414       if (code < bound) {
 415         v += ((1<<kNumBitModelTotalBits)-v)>>kNumMoveBits;
 416         range = bound;
 417         symbol = 0;
 418       } else {
 419         v -= v>>kNumMoveBits;
 420         code -= bound;
 421         range -= bound;
 422         symbol = 1;
 423       }
 424       *prob = cast(CProb)v;
 425       normalize(readByte);
 426       return symbol;
 427     }
 428   }
 429
 430
 431   uint bitTreeReverseDecode (CProb* probs, uint numBits, ref CRangeDecoder rc, scope ubyte delegate () readByte) {
 432     uint m = 1;
 433     uint symbol = 0;
 434     for (uint i = 0; i < numBits; ++i) {
 435       uint bit = rc.decodeBit(probs+m, readByte);
 436       m <<= 1;
 437       m += bit;
 438       symbol |= bit<<i;
 439     }
 440     return symbol;
 441   }
 442
 443
 444   struct CBitTreeDecoder(uint NumBits) {
 445     CProb[1U<<NumBits] probs = ProbInitValue;
 446
 447   public:
 448     //@disable this (this);
 449
 450     void initialize () { probs[] = ProbInitValue; }
 451
 452     uint decode (ref CRangeDecoder rc, scope ubyte delegate () readByte) {
 453       uint m = 1;
 454       for (uint i = 0; i < NumBits; ++i) m = (m<<1)+rc.decodeBit(&probs[m], readByte);
 455       return m-(1U<<NumBits);
 456     }
 457
 458     uint reverseDecode (ref CRangeDecoder rc, scope ubyte delegate () readByte) { pragma(inline, true); return bitTreeReverseDecode(probs.ptr, NumBits, rc, readByte); }
 459   }
 460
 461
 462   enum kNumPosBitsMax = 4;
 463
 464   enum kNumStates = 12;
 465   enum kNumLenToPosStates = 4;
 466   enum kNumAlignBits = 4;
 467   enum kStartPosModelIndex = 4;
 468   enum kEndPosModelIndex = 14;
 469   enum kNumFullDistances = 1U<<(kEndPosModelIndex>>1);
 470   enum kMatchMinLen = 2;
 471
 472
 473   struct CLenDecoder {
 474     CProb choice;
 475     CProb choice2;
 476     CBitTreeDecoder!3[1U<<kNumPosBitsMax] lowCoder;
 477     CBitTreeDecoder!3[1U<<kNumPosBitsMax] midCoder;
 478     CBitTreeDecoder!8 highCoder;
 479
 480   public:
 481     //@disable this (this);
 482
 483     void initialize () {
 484       choice = ProbInitValue;
 485       choice2 = ProbInitValue;
 486       highCoder.initialize();
 487       for (uint i = 0; i < (1<<kNumPosBitsMax); ++i) {
 488         lowCoder[i].initialize();
 489         midCoder[i].initialize();
 490       }
 491     }
 492
 493     uint decode (ref CRangeDecoder rc, uint posState, scope ubyte delegate () readByte) {
 494       if (rc.decodeBit(&choice, readByte) == 0) return lowCoder[posState].decode(rc, readByte);
 495       if (rc.decodeBit(&choice2, readByte) == 0) return 8+midCoder[posState].decode(rc, readByte);
 496       return 16+highCoder.decode(rc, readByte);
 497     }
 498   }
 499
 500
 501   uint updateStateLiteral (uint state) pure nothrow @safe @nogc {
 502     pragma(inline, true);
 503     /*
 504     if (state < 4) return 0;
 505     if (state < 10) return state-3;
 506     return state-6;
 507     */
 508     return (state < 4 ? 0 : state < 10 ? state-3 : state-6);
 509   }
 510   uint updateStateMatch (uint state) pure nothrow @safe @nogc { pragma(inline, true); return (state < 7 ? 7 : 10); }
 511   uint updateStateRep (uint state) pure nothrow @safe @nogc { pragma(inline, true); return (state < 7 ? 8 : 11); }
 512   uint updateStateShortRep (uint state) pure nothrow @safe @nogc { pragma(inline, true); return (state < 7 ? 9 : 11); }
 513 }