cosmetix
[iv.d.git] / balz.d
bloba8f7b74f1b8135d6cc9be3bbdc7b83a1c51ed700
1 /**
2 * BALZ: A ROLZ-based file compressor.
4 * balz is written and placed in the public domain by Ilya Muravyov <ilya.muravyov@yahoo.com>
6 * BALZ is a ROLZ-based data compressor with a high compression ratio and fast decompression.
8 * Special thanks to Matt Mahoney, Eugene Shelwien, Uwe Herklotz, Malcolm Taylor and LovePimple.
10 * D port by Ketmar // Invisible Vector
12 * What is ROLZ: http://ezcodesample.com/rolz/rolz_article.html
14 module iv.balz /*is aliced*/;
15 import iv.alice;
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");
26 private:
27 enum MAGIC = 0xab; // baLZ
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; }
38 private:
39 uint code;
40 uint low;
41 uint high;
43 enum CounterSize = 256;
44 Counter* counters; // [512][CounterSize], then [TabSize][CounterSize]
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;
56 enum TabBits = 7;
57 enum TabSize = 1<<TabBits;
58 enum TabMask = TabSize-1;
60 enum MinMatchLen = 3;
61 enum MaxMatchLen = 255+MinMatchLen;
63 //enum SlDictBits = 25;
64 ubyte lastDictBits = 0;
65 ubyte SlDictBits = 25;
66 uint SlDictSize; // = 1<<SlDictBits;
67 uint SlDictMask; // = cast(uint)(SlDictSize-1);
69 enum TabCntSize = 1<<16;
71 ubyte* sldict; //[SlDictSize]
72 uint* tab; // [TabSize][TabCntSize]
73 int* cnt; // [TabCntSize]
75 bool inProgress; // we are currently doing compressing or decompressing (and can't reinit the engine)
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;
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;
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);
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;
115 public:
116 ~this () { freeMem(); }
118 @disable this (this); // no copies
120 enum MinDictBits = 10; /// minimum dictionary size
121 enum MaxDictBits = 25; /// maximum dictionary size
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); }
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;
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);
143 xfree(counters);
144 xfree(cnt);
145 xfree(tab);
146 xfree(sldict);
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);
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();
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;
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");
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;
199 int[MaxMatchLen+1] bestIdx;
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;
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;
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;
258 idx = bestIdx.ptr[len];
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;
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;
279 // flush output buffer again
280 if (obufPos > 0) { auto wr = obufPos; obufPos = 0; putBuf(obuf[0..wr]); }
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);
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");
300 return ibuf[ibufPos++];
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();
313 while ((low^high) < (1<<24)) {
314 code = (code<<8)|getb();
315 low <<= 8;
316 high = (high<<8)|255;
318 return bit;
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");
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); }
337 return ctx-Limit;
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);
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;
362 if (flen > 0) {
363 if (n > flen) n = cast(int)flen; // don't read more than we need
364 flen -= n;
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;
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;
386 tab[c2*TabSize+(++cnt[c2]&TabMask)] = tmp;
388 totalout += p;
389 putBuf(sldict[0..p]);
391 return totalout;
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;
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);
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;
424 cnt[0..TabCntSize] = 0;
425 code = 0;
426 low = 0;
427 high = uint.max;
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;
438 int getPts (int len, int x) {
439 pragma(inline, true);
440 return (len >= MinMatchLen ? (len<<TabBits)-x : ((MinMatchLen-1)<<TabBits)-8);
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;
464 return getPts(len, idx);
470 // ////////////////////////////////////////////////////////////////////////// //
471 // handy aliases
472 alias Balz = BalzCodec!"encoder"; /// alias for Balz encoder
473 alias Unbalz = BalzCodec!"decoder"; /// alias for Balz decoder