balz.d

   1 /**
   2  * BALZ: A ROLZ-based file compressor.
   3  *
   4  * balz is written and placed in the public domain by Ilya Muravyov <ilya.muravyov@yahoo.com>
   5  *
   6  * BALZ is a ROLZ-based data compressor with a high compression ratio and fast decompression.
   7  *
   8  * Special thanks to Matt Mahoney, Eugene Shelwien, Uwe Herklotz, Malcolm Taylor and LovePimple.
   9  *
  10  * D port by Ketmar // Invisible Vector
  11  *
  12  * What is ROLZ: http://ezcodesample.com/rolz/rolz_article.html
  13  */
  14 module iv.balz /*is aliced*/;
  15 import iv.alice;
  16
  17
  18 // ////////////////////////////////////////////////////////////////////////// //
  19 /// LZ compressor and decompressor.
  20 ///
  21 /// memory usage (both for compression and for decompression): (~65MB)
  22 struct BalzCodec(string mode) {
  23 static assert(mode == "encoder" || mode == "decoder", "invalid Balz mode");
  24 //static assert(BufBits >= 8 && BufBits <= 25, "invalid dictionary size");
  25
  26 private:
  27   enum MAGIC = 0xab; // baLZ
  28
  29   static align(1) struct Counter {
  30   pure nothrow @safe @nogc align(1):
  31     ushort p1 = 1<<15;
  32     ushort p2 = 1<<15;
  33     @property uint p () const { pragma(inline, true); return p1+p2; }
  34     void update0 () { pragma(inline, true); p1 -= p1>>3; p2 -= p2>>6; }
  35     void update1 () { pragma(inline, true); p1 += (p1^65535)>>3; p2 += (p2^65535)>>6; }
  36   }
  37
  38 private:
  39   uint code;
  40   uint low;
  41   uint high;
  42
  43   enum CounterSize = 256;
  44   Counter* counters; // [512][CounterSize], then [TabSize][CounterSize]
  45
  46   static if (mode == "encoder") {
  47     enum obufSize = 65536;
  48     ubyte* obuf;
  49     uint obufPos;
  50   } else {
  51     ubyte* ibuf;
  52     enum ibufSize = 65536;
  53     uint ibufPos, ibufUsed;
  54   }
  55
  56   enum TabBits = 7;
  57   enum TabSize = 1<<TabBits;
  58   enum TabMask = TabSize-1;
  59
  60   enum MinMatchLen = 3;
  61   enum MaxMatchLen = 255+MinMatchLen;
  62
  63   //enum SlDictBits = 25;
  64   ubyte lastDictBits = 0;
  65   ubyte SlDictBits = 25;
  66   uint SlDictSize; // = 1<<SlDictBits;
  67   uint SlDictMask; // = cast(uint)(SlDictSize-1);
  68
  69   enum TabCntSize = 1<<16;
  70
  71   ubyte* sldict; //[SlDictSize]
  72   uint* tab; // [TabSize][TabCntSize]
  73   int* cnt; // [TabCntSize]
  74
  75   bool inProgress; // we are currently doing compressing or decompressing (and can't reinit the engine)
  76
  77 private:
  78   static T* xalloc(T) (uint mem) if (T.sizeof > 0) {
  79     import core.exception : onOutOfMemoryError;
  80     assert(mem != 0);
  81     import core.stdc.stdlib : malloc;
  82     auto res = malloc(mem*T.sizeof);
  83     if (res is null) onOutOfMemoryError();
  84     debug(balz_alloc) { import core.stdc.stdio : printf; printf("balz allocated %u bytes\n", cast(uint)(mem*T.sizeof)); }
  85     return cast(T*)res;
  86   }
  87
  88   static void xfree(T) (ref T* ptr) {
  89     if (ptr !is null) {
  90       import core.stdc.stdlib : free;
  91       free(ptr);
  92       ptr = null;
  93     }
  94   }
  95
  96 public:
  97   /// read data to provided buffer. return number of bytes read (can be less then buf size) or 0 on EOF. should throw on error.
  98   alias GetBufFn = uint delegate (void[] buf);
  99   /// write data from buffer. should write everything. should throw on error.
 100   alias PutBufFn = void delegate (const(void)[] buf);
 101
 102 public:
 103   /// get memory requirements for current configuration
 104   uint getMemoryRequirements () {
 105     pragma(inline, true);
 106     static if (mode == "encoder") enum iobufsize = obufSize; else enum iobufsize = ibufSize;
 107     return
 108       (1U<<SlDictBits)+ // sldict
 109       TabSize*TabCntSize*cast(uint)uint.sizeof+ // tab
 110       TabCntSize*cast(uint)int.sizeof+
 111       (512*CounterSize+TabSize*CounterSize)*cast(uint)Counter.sizeof+
 112       iobufsize;
 113   }
 114
 115 public:
 116   ~this () { freeMem(); }
 117
 118   @disable this (this); // no copies
 119
 120   enum MinDictBits = 10; /// minimum dictionary size
 121   enum MaxDictBits = 25; /// maximum dictionary size
 122
 123   @property ubyte dictBits () const pure nothrow @safe @nogc { pragma(inline, true); return SlDictBits; }
 124   @property uint dictSize () const pure nothrow @safe @nogc { pragma(inline, true); return (1U<<SlDictBits); }
 125
 126   /// reinit the engine with new dictionary size
 127   bool reinit (ubyte dictbits) pure nothrow @safe @nogc {
 128     if (dictbits < MinDictBits || dictbits > MaxDictBits) return false;
 129     if (inProgress) return false;
 130     SlDictBits = dictbits;
 131     SlDictSize = 1U<<SlDictBits;
 132     SlDictMask = cast(uint)(SlDictSize-1);
 133     return true;
 134   }
 135
 136   /// free working memory. can be called after compressing/decompressing.
 137   void freeMem () {
 138     static if (mode == "encoder") {
 139       xfree(obuf);
 140     } else {
 141       xfree(ibuf);
 142     }
 143     xfree(counters);
 144     xfree(cnt);
 145     xfree(tab);
 146     xfree(sldict);
 147   }
 148
 149   // ////////////////////////////////////////////////////////////////////// //
 150   /// compress data. will call `getBuf()` to read uncompressed data and
 151   /// `putBuf` to write compressed data. set `max` to `true` to squeeze some
 152   /// more bytes, but sacrifice some speed.
 153   static if (mode == "encoder") void compress (scope GetBufFn getBuf, scope PutBufFn putBuf, bool max=false) {
 154     assert(getBuf !is null);
 155     assert(putBuf !is null);
 156
 157     // i moved the following functions here 'cause they need to do i/o
 158     void encodeWithCounter (int bit, Counter* counter) {
 159       immutable mid = cast(uint)(low+((cast(ulong)(high-low)*(counter.p<<15))>>32));
 160       if (bit) {
 161         high = mid;
 162         counter.update1();
 163       } else {
 164         low = mid+1;
 165         counter.update0();
 166       }
 167       while ((low^high) < (1<<24)) {
 168         if (obufPos >= obufSize) { auto wr = obufPos; obufPos = 0; putBuf(obuf[0..wr]); }
 169         obuf[obufPos++] = cast(ubyte)(low>>24);
 170         low <<= 8;
 171         high = (high<<8)|255;
 172       }
 173     }
 174
 175     // doesn't do 511-escaping
 176     void encode(string mode) (uint t, uint c) {
 177       static if (mode == "char") {
 178         enum Limit = 512;
 179         enum Mask = 256;
 180         auto cptr = counters;
 181         debug(balz_eos) { import core.stdc.stdio : printf; printf("ec: t=%u; c=%u\n", cast(uint)t, cast(uint)c); }
 182       } else static if (mode == "idx") {
 183         enum Limit = TabSize;
 184         enum Mask = (TabSize>>1);
 185         auto cptr = counters+(512*CounterSize);
 186       } else {
 187         static assert(0, "invalid mode");
 188       }
 189       cptr += c*Limit;
 190       int ctx = 1;
 191       while (ctx < Limit) {
 192         immutable bit = cast(int)((t&Mask) != 0);
 193         t += t;
 194         encodeWithCounter(bit, cptr+ctx);
 195         ctx += ctx+bit;
 196       }
 197     }
 198
 199     int[MaxMatchLen+1] bestIdx;
 200
 201     if (inProgress) throw new Exception("already doing something");
 202     inProgress = true;
 203     scope(exit) inProgress = false;
 204     reset();
 205     obuf[obufPos++] = MAGIC;
 206     obuf[obufPos++] = 00; // stream version
 207     for (;;) {
 208       int n = 0;
 209       while (n < SlDictSize) {
 210         auto rd = getBuf(sldict[n..SlDictSize]);
 211         if (rd == 0) break;
 212         n += rd;
 213       }
 214       // write block size
 215       encode!"char"((n>>24)&0xff, 0);
 216       encode!"char"((n>>16)&0xff, 0);
 217       encode!"char"((n>>8)&0xff, 0);
 218       encode!"char"(n&0xff, 0);
 219       if (n == 0) break;
 220       int p = 0;
 221       while (p < 2 && p < n) encode!"char"(sldict[p++], 0);
 222       tab[0..TabSize*TabCntSize] = 0;
 223       while (p < n) {
 224         immutable int c2 = sldict[(p+SlDictSize-2)&SlDictMask]|(sldict[(p+SlDictSize-1)&SlDictMask]<<8);
 225         immutable uint hash = getHash(p);
 226         int len = MinMatchLen-1;
 227         int idx = TabSize;
 228         int maxMatch = n-p;
 229         if (maxMatch > MaxMatchLen) maxMatch = MaxMatchLen;
 230         // hash search
 231         foreach (uint x; 0..TabSize) {
 232           immutable uint d = tab[c2*TabSize+((cnt[c2]-x)&TabMask)];
 233           if (!d) break;
 234           if ((d&~SlDictMask) != hash) continue;
 235           immutable int s = d&SlDictMask;
 236           if (sldict[(s+len)&SlDictMask] != sldict[(p+len)&SlDictMask] || sldict[s] != sldict[p&SlDictMask]) continue;
 237           int l = 0;
 238           while (++l < maxMatch) if (sldict[(s+l)&SlDictMask] != sldict[(p+l)&SlDictMask]) break;
 239           if (l > len) {
 240             for (int i = l; i > len; --i) bestIdx.ptr[i] = x;
 241             idx = x;
 242             len = l;
 243             if (l == maxMatch) break;
 244           }
 245         }
 246         // check match
 247         if (max && len >= MinMatchLen) {
 248           int sum = getPts(len, idx)+getPtsAt(p+len, n);
 249           if (sum < getPts(len+MaxMatchLen, 0)) {
 250             immutable int lookahead = len;
 251             for (int i = 1; i < lookahead; ++i) {
 252               immutable int tmp = getPts(i, bestIdx.ptr[i])+getPtsAt(p+i, n);
 253               if (tmp > sum) {
 254                 sum = tmp;
 255                 len = i;
 256               }
 257             }
 258             idx = bestIdx.ptr[len];
 259           }
 260         }
 261         tab[c2*TabSize+(++cnt[c2]&TabMask)] = hash|p;
 262         if (len >= MinMatchLen) {
 263           encode!"char"((256-MinMatchLen)+len, sldict[(p+SlDictSize-1)&SlDictMask]);
 264           encode!"idx"(idx, sldict[(p+SlDictSize-2)&SlDictMask]);
 265           p += len;
 266         } else {
 267           encode!"char"(sldict[p], sldict[(p+SlDictSize-1)&SlDictMask]);
 268           ++p;
 269         }
 270       }
 271     }
 272     // flush output buffer, so we can skip flush checks in code flush
 273     if (obufPos > 0) { auto wr = obufPos; obufPos = 0; putBuf(obuf[0..wr]); }
 274     // flush codes
 275     foreach (immutable _; 0..4) {
 276       obuf[obufPos++] = cast(ubyte)(low>>24);
 277       low <<= 8;
 278     }
 279     // flush output buffer again
 280     if (obufPos > 0) { auto wr = obufPos; obufPos = 0; putBuf(obuf[0..wr]); }
 281   }
 282
 283   // ////////////////////////////////////////////////////////////////////// //
 284   /// decompress data. will call `getBuf()` to read compressed data and
 285   /// `putBuf` to write uncompressed data. pass *uncompressed* data length in
 286   /// `flen`. sorry, no "end of stream" flag is provided.
 287   /// returns number of decoded bytes.
 288   static if (mode == "decoder") long decompress (scope GetBufFn getBuf, scope PutBufFn putBuf, long flen=-1) {
 289     assert(getBuf !is null);
 290     assert(putBuf !is null);
 291     //assert(flen >= 0);
 292
 293     // i moved the following functions here 'cause they need to do i/o
 294     ubyte getb () {
 295       if (ibufPos >= ibufUsed) {
 296         ibufPos = ibufUsed = 0;
 297         ibufUsed = getBuf(ibuf[0..ibufSize]);
 298         if (ibufUsed == 0) throw new Exception("out of input data");
 299       }
 300       return ibuf[ibufPos++];
 301     }
 302
 303     uint decodeWithCounter (Counter* counter) {
 304       immutable uint mid = cast(uint)(low+((cast(ulong)(high-low)*(counter.p<<15))>>32));
 305       immutable int bit = (code <= mid);
 306       if (bit) {
 307         high = mid;
 308         counter.update1();
 309       } else {
 310         low = mid+1;
 311         counter.update0();
 312       }
 313       while ((low^high) < (1<<24)) {
 314         code = (code<<8)|getb();
 315         low <<= 8;
 316         high = (high<<8)|255;
 317       }
 318       return bit;
 319     }
 320
 321     int decode(string mode) (uint c) {
 322       static if (mode == "char") {
 323         enum Limit = 512;
 324         auto cptr = counters;
 325       } else static if (mode == "idx") {
 326         enum Limit = TabSize;
 327         auto cptr = counters+(512*CounterSize);
 328       } else {
 329         static assert(0, "invalid mode");
 330       }
 331       cptr += c*Limit;
 332       uint ctx = 1;
 333       while (ctx < Limit) ctx += ctx+decodeWithCounter(cptr+ctx);
 334       static if (mode == "char") {
 335         debug(balz_eos) { import core.stdc.stdio : printf; printf("dc: t=%u; c=%u\n", cast(uint)(ctx-Limit), cast(uint)c); }
 336       }
 337       return ctx-Limit;
 338     }
 339
 340     if (inProgress) throw new Exception("already doing something");
 341     inProgress = true;
 342     scope(exit) inProgress = false;
 343     long totalout = 0;
 344     reset();
 345     if (getb() != MAGIC) throw new Exception("invalid compressed stream format");
 346     if (getb() != 00) throw new Exception("invalid compressed stream version");
 347     foreach (immutable _; 0..4) code = (code<<8)|getb();
 348     while (flen != 0) {
 349       // read block size
 350       int n = 0;
 351       foreach (immutable _; 0..4) {
 352         immutable uint t = decode!"char"(0);
 353         if (t >= 256) throw new Exception("compressed stream corrupted");
 354         n = (n<<8)|(t&0xff);
 355       }
 356       if (n < 0 || n > SlDictSize) throw new Exception("compressed stream corrupted");
 357       if (n == 0) {
 358         // done
 359         if (flen > 0) throw new Exception("compressed stream ends unexpectedly");
 360         break;
 361       }
 362       if (flen > 0) {
 363         if (n > flen) n = cast(int)flen; // don't read more than we need
 364         flen -= n;
 365       }
 366       int p = 0;
 367       while (p < 2 && p < n) {
 368         immutable uint t = decode!"char"(0);
 369         if (t >= 256) throw new Exception("compressed stream corrupted");
 370         sldict[p++] = cast(ubyte)t;
 371       }
 372       while (p < n) {
 373         immutable int tmp = p;
 374         immutable int c2 = sldict[(p+SlDictSize-2)&SlDictMask]|(sldict[(p+SlDictSize-1)&SlDictMask]<<8);
 375         int t = decode!"char"(sldict[(p+SlDictSize-1)&SlDictMask]);
 376         if (t >= 256) {
 377           int len = t-256;
 378           int s = tab[c2*TabSize+((cnt[c2]-decode!"idx"(sldict[(p+SlDictSize-2)&SlDictMask]))&TabMask)];
 379           sldict[p&SlDictMask] = sldict[s&SlDictMask]; ++p; ++s;
 380           sldict[p&SlDictMask] = sldict[s&SlDictMask]; ++p; ++s;
 381           sldict[p&SlDictMask] = sldict[s&SlDictMask]; ++p; ++s;
 382           while (len--) { sldict[p&SlDictMask] = sldict[s&SlDictMask]; ++p; ++s; }
 383         } else {
 384           sldict[p&SlDictMask] = cast(ubyte)t; ++p;
 385         }
 386         tab[c2*TabSize+(++cnt[c2]&TabMask)] = tmp;
 387       }
 388       totalout += p;
 389       putBuf(sldict[0..p]);
 390     }
 391     return totalout;
 392   }
 393
 394 private:
 395   void setupMem () {
 396     scope(failure) freeMem();
 397     SlDictSize = 1U<<SlDictBits;
 398     SlDictMask = cast(uint)(SlDictSize-1);
 399     if (sldict is null || SlDictBits != lastDictBits) {
 400       xfree(sldict);
 401       sldict = xalloc!ubyte(SlDictSize);
 402       lastDictBits = SlDictBits;
 403     }
 404     if (tab is null) tab = xalloc!uint(TabSize*TabCntSize);
 405     if (cnt is null) cnt = xalloc!int(TabCntSize);
 406     if (counters is null) counters = xalloc!Counter(512*CounterSize+TabSize*CounterSize);
 407     static if (mode == "encoder") {
 408       if (obuf is null) obuf = xalloc!ubyte(obufSize);
 409     } else {
 410       if (ibuf is null) ibuf = xalloc!ubyte(ibufSize);
 411     }
 412   }
 413
 414   void reset () {
 415     setupMem();
 416     sldict[0..SlDictSize] = 0;
 417     counters[0..512*CounterSize+TabSize*CounterSize] = Counter.init;
 418     static if (mode == "decoder") {
 419       tab[0..TabSize*TabCntSize] = 0; // encoder will immediately reinit this anyway
 420       ibufPos = ibufUsed = 0;
 421     } else {
 422       obufPos = 0;
 423     }
 424     cnt[0..TabCntSize] = 0;
 425     code = 0;
 426     low = 0;
 427     high = uint.max;
 428   }
 429
 430   // ////////////////////////////////////////////////////////////////////// //
 431   // encoder utility functions
 432   static if (mode == "encoder") {
 433     uint getHash (int p) {
 434       pragma(inline, true);
 435       return (((sldict[(p+0)&SlDictMask]|(sldict[(p+1)&SlDictMask]<<8)|(sldict[(p+2)&SlDictMask]<<16)|(sldict[(p+3)&SlDictMask]<<24))&0xffffff)*2654435769UL)&~SlDictMask;
 436     }
 437
 438     int getPts (int len, int x) {
 439       pragma(inline, true);
 440       return (len >= MinMatchLen ? (len<<TabBits)-x : ((MinMatchLen-1)<<TabBits)-8);
 441     }
 442
 443     int getPtsAt (int p, int n) {
 444       immutable int c2 = sldict[(p+SlDictSize-2)&SlDictMask]|(sldict[(p+SlDictSize-1)&SlDictMask]<<8);//*cast(ushort*)(sldict.ptr+p-2);
 445       immutable uint hash = getHash(p);
 446       int len = MinMatchLen-1;
 447       int idx = TabSize;
 448       int maxMatch = n-p;
 449       if (maxMatch > MaxMatchLen) maxMatch = MaxMatchLen;
 450       foreach (int x; 0..TabSize) {
 451         immutable uint d = tab[c2*TabSize+((cnt[c2]-x)&TabMask)];
 452         if (!d) break;
 453         if ((d&~SlDictMask) != hash) continue;
 454         immutable int s = d&SlDictMask;
 455         if (sldict[(s+len)&SlDictMask] != sldict[(p+len)&SlDictMask] || sldict[s] != sldict[p]) continue;
 456         int l = 0;
 457         while (++l < maxMatch) if (sldict[(s+l)&SlDictMask] != sldict[(p+l)&SlDictMask]) break;
 458         if (l > len) {
 459           idx = x;
 460           len = l;
 461           if (l == maxMatch) break;
 462         }
 463       }
 464       return getPts(len, idx);
 465     }
 466   }
 467 }
 468
 469
 470 // ////////////////////////////////////////////////////////////////////////// //
 471 // handy aliases
 472 alias Balz = BalzCodec!"encoder"; /// alias for Balz encoder
 473 alias Unbalz = BalzCodec!"decoder"; /// alias for Balz decoder