Debian Codegraph @

src/djvu/bs.cpp

raw
1 /*
2 * bs.cpp - BZZ-coder from DjVuLibre, a general purpose compressor
3 * based on the Burrows-Wheeler (or "block sorting") transform.
4 */
5
6 #include "../base/mdjvucfg.h"
7 #include <minidjvu/minidjvu.h>
8
9 #include <stdlib.h>
10 #include <stdio.h>
11 #include <string.h>
12
13 #include "bs.h"
14
15 // ========================================
16 // --- Global Definitions
17
18
19 // Sorting tresholds
20 enum { FREQMAX=4, CTXIDS=3 };
21 // Limits on block sizes
22 enum { MINBLOCK=10, MAXBLOCK=4096 };
23
24
25
26 #ifdef OVERFLOW
27 #undef OVERFLOW
28 #endif
29 // Overflow required when encoding
30 static const int OVERFLOW=32;
31
32 // Sorting tresholds
33 static const int RANKSORT_THRESH=10;
34 static const int QUICKSORT_STACK=512;
35 static const int PRESORT_THRESH=10;
36 static const int PRESORT_DEPTH=8;
37 static const int RADIX_THRESH=32768;
38
39 static const int FREQS0=100000;
40 static const int FREQS1=1000000;
41
42 // ========================================
43 // -- Sorting Routines
44
45
46 class _BSort // DJVU_CLASS
47 {
48 public:
49 ~_BSort();
50 _BSort(unsigned char *data, int size);
51 void run(int &markerpos);
52 private:
53 // Members
54 int size;
55 unsigned char *data;
56 unsigned int *posn;
57 int *rank;
58 // Helpers
59 inline int GT(int p1, int p2, int depth);
60 inline int GTD(int p1, int p2, int depth);
61 // -- final in-depth sort
62 void ranksort(int lo, int hi, int d);
63 // -- doubling sort
64 int pivot3r(int *rr, int lo, int hi);
65 void quicksort3r(int lo, int hi, int d);
66 // -- presort to depth PRESORT_DEPTH
67 unsigned char pivot3d(unsigned char *dd, int lo, int hi);
68 void quicksort3d(int lo, int hi, int d);
69 // -- radixsort
70 void radixsort16(void);
71 void radixsort8(void);
72 };
73
74
75 // blocksort -- the main entry point
76
77 static void blocksort(unsigned char *data, int size, int &markerpos)
78 {
79 _BSort bsort(data, size);
80 bsort.run(markerpos);
81 }
82
83
84 // _BSort construction
85
86 _BSort::_BSort(unsigned char *xdata, int xsize)
87 : size(xsize), data(xdata)
88 {
89 posn = (unsigned int *) calloc (size, sizeof(unsigned int));
90 rank = (int *) calloc (size+1, sizeof(int));
91
92 assert(size>0 && size<0x1000000);
93 rank[size] = -1;
94 }
95
96 _BSort::~_BSort()
97 {
98 free(posn);
99 free(rank);
100 }
101
102
103
104 // GT -- compare suffixes using rank information
105
106 inline int _BSort::GT(int p1, int p2, int depth)
107 {
108 int r1, r2;
109 int twod = depth + depth;
110 while (1)
111 {
112 r1=rank[p1+depth]; r2=rank[p2+depth];
113 p1+=twod; p2+=twod;
114 if (r1!=r2)
115 return (r1>r2);
116 r1=rank[p1]; r2=rank[p2];
117 if (r1!=r2)
118 return (r1>r2);
119 r1=rank[p1+depth]; r2=rank[p2+depth];
120 p1+=twod; p2+=twod;
121 if (r1!=r2)
122 return (r1>r2);
123 r1=rank[p1]; r2=rank[p2];
124 if (r1!=r2)
125 return (r1>r2);
126 r1=rank[p1+depth]; r2=rank[p2+depth];
127 p1+=twod; p2+=twod;
128 if (r1!=r2)
129 return (r1>r2);
130 r1=rank[p1]; r2=rank[p2];
131 if (r1!=r2)
132 return (r1>r2);
133 r1=rank[p1+depth]; r2=rank[p2+depth];
134 p1+=twod; p2+=twod;
135 if (r1!=r2)
136 return (r1>r2);
137 r1=rank[p1]; r2=rank[p2];
138 if (r1!=r2)
139 return (r1>r2);
140 };
141 }
142
143
144 // _BSort::ranksort --
145 // -- a simple insertion sort based on GT
146
147 void _BSort::ranksort(int lo, int hi, int depth)
148 {
149 int i,j;
150 for (i=lo+1; i<=hi; i++)
151 {
152 int tmp = posn[i];
153 for(j=i-1; j>=lo && GT(posn[j], tmp, depth); j--)
154 posn[j+1] = posn[j];
155 posn[j+1] = tmp;
156 }
157 for(i=lo;i<=hi;i++)
158 rank[posn[i]]=i;
159 }
160
161 // pivot -- return suitable pivot
162
163 int _BSort::pivot3r(int *rr, int lo, int hi)
164 {
165 int c1, c2, c3;
166 if (hi-lo > 256)
167 {
168 c1 = pivot3r(rr, lo, (6*lo+2*hi)/8);
169 c2 = pivot3r(rr, (5*lo+3*hi)/8, (3*lo+5*hi)/8);
170 c3 = pivot3r(rr, (2*lo+6*hi)/8, hi);
171 }
172 else
173 {
174 c1 = rr[posn[lo]];
175 c2 = rr[posn[(lo+hi)/2]];
176 c3 = rr[posn[hi]];
177 }
178 // Extract median
179 if (c1>c3)
180 { int tmp=c1; c1=c3; c3=tmp; }
181 if (c2<=c1)
182 return c1;
183 else if (c2>=c3)
184 return c3;
185 else
186 return c2;
187 }
188
189
190 // _BSort::quicksort3r -- Three way quicksort algorithm
191 // Sort suffixes based on rank at pos+depth
192 // The algorithm breaks into ranksort when size is
193 // smaller than RANKSORT_THRESH
194
195 static inline int mini(int a, int b)
196 {
197 return (a<=b) ? a : b;
198 }
199
200 static inline void vswap(int i, int j, int n, unsigned int *x)
201 {
202 while (n-- > 0)
203 {
204 int tmp = x[i]; x[i++]=x[j]; x[j++]=tmp;
205 }
206 }
207
208 void _BSort::quicksort3r(int lo, int hi, int depth)
209 {
210 /* Initialize stack */
211 int slo[QUICKSORT_STACK];
212 int shi[QUICKSORT_STACK];
213 int sp = 1;
214 slo[0] = lo;
215 shi[0] = hi;
216 // Recursion elimination loop
217 while (--sp>=0)
218 {
219 lo = slo[sp];
220 hi = shi[sp];
221 // Test for insertion sort
222 if (hi-lo<RANKSORT_THRESH)
223 {
224 ranksort(lo, hi, depth);
225 }
226 else
227 {
228 int tmp;
229 int *rr=rank+depth;
230 int med = pivot3r(rr,lo,hi);
231 // -- positions are organized as follows:
232 // [lo..l1[ [l1..l[ ]h..h1] ]h1..hi]
233 // = < > =
234 int l1 = lo;
235 int h1 = hi;
236 while (rr[posn[l1]]==med && l1<h1) { l1++; }
237 while (rr[posn[h1]]==med && l1<h1) { h1--; }
238 int l = l1;
239 int h = h1;
240 // -- partition set
241 for (;;)
242 {
243 while (l<=h)
244 {
245 int c = rr[posn[l]] - med;
246 if (c > 0) break;
247 if (c == 0) { tmp=posn[l]; posn[l]=posn[l1]; posn[l1++]=tmp; }
248 l++;
249 }
250 while (l<=h)
251 {
252 int c = rr[posn[h]] - med;
253 if (c < 0) break;
254 if (c == 0) { tmp=posn[h]; posn[h]=posn[h1]; posn[h1--]=tmp; }
255 h--;
256 }
257 if (l>h) break;
258 tmp=posn[l]; posn[l]=posn[h]; posn[h]=tmp;
259 }
260 // -- reorganize as follows
261 // [lo..l1[ [l1..h1] ]h1..hi]
262 // < = >
263 tmp = mini(l1-lo, l-l1);
264 vswap(lo, l-tmp, tmp, posn);
265 l1 = lo + (l-l1);
266 tmp = mini(hi-h1, h1-h);
267 vswap(hi-tmp+1, h+1, tmp, posn);
268 h1 = hi - (h1-h);
269 // -- process segments
270 assert(sp+2<QUICKSORT_STACK);
271 // ----- middle segment (=?) [l1, h1]
272 for(int i=l1;i<=h1;i++)
273 rank[posn[i]] = h1;
274 // ----- lower segment (<) [lo, l1[
275 if (l1 > lo)
276 {
277 for(int i=lo;i<l1;i++)
278 rank[posn[i]]=l1-1;
279 slo[sp]=lo;
280 shi[sp]=l1-1;
281 if (slo[sp] < shi[sp])
282 sp++;
283 }
284 // ----- upper segment (>) ]h1, hi]
285 if (h1 < hi)
286 {
287 slo[sp]=h1+1;
288 shi[sp]=hi;
289 if (slo[sp] < shi[sp])
290 sp++;
291 }
292 }
293 }
294 }
295
296
297
298
299
300
301 // GTD -- compare suffixes using data information
302 // (up to depth PRESORT_DEPTH)
303
304 inline int _BSort::GTD(int p1, int p2, int depth)
305 {
306 unsigned char c1, c2;
307 p1+=depth; p2+=depth;
308 while (depth < PRESORT_DEPTH)
309 {
310 // Perform two
311 c1=data[p1]; c2=data[p2];
312 if (c1!=c2)
313 return (c1>c2);
314 c1=data[p1+1]; c2=data[p2+1];
315 p1+=2; p2+=2; depth+=2;
316 if (c1!=c2)
317 return (c1>c2);
318 }
319 if (p1<size && p2<size)
320 return 0;
321 return (p1<p2);
322 }
323
324 // pivot3d -- return suitable pivot
325
326 unsigned char _BSort::pivot3d(unsigned char *rr, int lo, int hi)
327 {
328 unsigned char c1, c2, c3;
329 if (hi-lo > 256)
330 {
331 c1 = pivot3d(rr, lo, (6*lo+2*hi)/8);
332 c2 = pivot3d(rr, (5*lo+3*hi)/8, (3*lo+5*hi)/8);
333 c3 = pivot3d(rr, (2*lo+6*hi)/8, hi);
334 }
335 else
336 {
337 c1 = rr[posn[lo]];
338 c2 = rr[posn[(lo+hi)/2]];
339 c3 = rr[posn[hi]];
340 }
341 // Extract median
342 if (c1>c3)
343 { int tmp=c1; c1=c3; c3=tmp; }
344 if (c2<=c1)
345 return c1;
346 else if (c2>=c3)
347 return c3;
348 else
349 return c2;
350 }
351
352
353 // _BSort::quicksort3d -- Three way quicksort algorithm
354 // Sort suffixes based on strings until reaching
355 // depth rank at pos+depth
356 // The algorithm breaks into ranksort when size is
357 // smaller than PRESORT_THRESH
358
359 void _BSort::quicksort3d(int lo, int hi, int depth)
360 {
361 /* Initialize stack */
362 int slo[QUICKSORT_STACK];
363 int shi[QUICKSORT_STACK];
364 int sd[QUICKSORT_STACK];
365 int sp = 1;
366 slo[0] = lo;
367 shi[0] = hi;
368 sd[0] = depth;
369 // Recursion elimination loop
370 while (--sp>=0)
371 {
372 lo = slo[sp];
373 hi = shi[sp];
374 depth = sd[sp];
375 // Test for insertion sort
376 if (depth >= PRESORT_DEPTH)
377 {
378 for (int i=lo; i<=hi; i++)
379 rank[posn[i]] = hi;
380 }
381 else if (hi-lo<PRESORT_THRESH)
382 {
383 int i,j;
384 for (i=lo+1; i<=hi; i++)
385 {
386 int tmp = posn[i];
387 for(j=i-1; j>=lo && GTD(posn[j], tmp, depth); j--)
388 posn[j+1] = posn[j];
389 posn[j+1] = tmp;
390 }
391 for(i=hi;i>=lo;i=j)
392 {
393 int tmp = posn[i];
394 rank[tmp] = i;
395 for (j=i-1; j>=lo && !GTD(tmp,posn[j],depth); j--)
396 rank[posn[j]] = i;
397 }
398 }
399 else
400 {
401 int tmp;
402 unsigned char *dd=data+depth;
403 unsigned char med = pivot3d(dd,lo,hi);
404 // -- positions are organized as follows:
405 // [lo..l1[ [l1..l[ ]h..h1] ]h1..hi]
406 // = < > =
407 int l1 = lo;
408 int h1 = hi;
409 while (dd[posn[l1]]==med && l1<h1) { l1++; }
410 while (dd[posn[h1]]==med && l1<h1) { h1--; }
411 int l = l1;
412 int h = h1;
413 // -- partition set
414 for (;;)
415 {
416 while (l<=h)
417 {
418 int c = (int)dd[posn[l]] - (int)med;
419 if (c > 0) break;
420 if (c == 0) { tmp=posn[l]; posn[l]=posn[l1]; posn[l1++]=tmp; }
421 l++;
422 }
423 while (l<=h)
424 {
425 int c = (int)dd[posn[h]] - (int)med;
426 if (c < 0) break;
427 if (c == 0) { tmp=posn[h]; posn[h]=posn[h1]; posn[h1--]=tmp; }
428 h--;
429 }
430 if (l>h) break;
431 tmp=posn[l]; posn[l]=posn[h]; posn[h]=tmp;
432 }
433 // -- reorganize as follows
434 // [lo..l1[ [l1..h1] ]h1..hi]
435 // < = >
436 tmp = mini(l1-lo, l-l1);
437 vswap(lo, l-tmp, tmp, posn);
438 l1 = lo + (l-l1);
439 tmp = mini(hi-h1, h1-h);
440 vswap(hi-tmp+1, h+1, tmp, posn);
441 h1 = hi - (h1-h);
442 // -- process segments
443 assert(sp+3<QUICKSORT_STACK);
444 // ----- middle segment (=?) [l1, h1]
445 l = l1; h = h1;
446 if (med==0) // special case for marker [slow]
447 for (int i=l; i<=h; i++)
448 if ((int)posn[i]+depth == size-1)
449 {
450 tmp=posn[i]; posn[i]=posn[l]; posn[l]=tmp;
451 rank[tmp]=l++; break;
452 }
453 if (l<h)
454 {
455 slo[sp] = l; shi[sp] = h; sd[sp++] = depth+1;
456 }
457 else if (l==h)
458 {
459 rank[posn[h]] = h;
460 }
461 // ----- lower segment (<) [lo, l1[
462 l = lo;
463 h = l1-1;
464 if (l<h)
465 {
466 slo[sp] = l; shi[sp] = h; sd[sp++] = depth;
467 }
468 else if (l==h)
469 {
470 rank[posn[h]] = h;
471 }
472 // ----- upper segment (>) ]h1, hi]
473 l = h1+1;
474 h = hi;
475 if (l<h)
476 {
477 slo[sp] = l; shi[sp] = h; sd[sp++] = depth;
478 }
479 else if (l==h)
480 {
481 rank[posn[h]] = h;
482 }
483 }
484 }
485 }
486
487
488
489
490 // _BSort::radixsort8 -- 8 bit radix sort
491
492 void _BSort::radixsort8(void)
493 {
494 int i;
495 // Initialize frequency array
496 int lo[256], hi[256];
497 for (i=0; i<256; i++)
498 hi[i] = lo[i] = 0;
499 // Count occurences
500 for (i=0; i<size-1; i++)
501 hi[data[i]] ++;
502 // Compute positions (lo)
503 int last = 1;
504 for (i=0; i<256; i++)
505 {
506 lo[i] = last;
507 hi[i] = last + hi[i] - 1;
508 last = hi[i] + 1;
509 }
510 for (i=0; i<size-1; i++)
511 {
512 posn[ lo[data[i]]++ ] = i;
513 rank[ i ] = hi[data[i]];
514 }
515 // Process marker "$"
516 posn[0] = size-1;
517 rank[size-1] = 0;
518 // Extra element
519 rank[size] = -1;
520 }
521
522
523 // _BSort::radixsort16 -- 16 bit radix sort
524
525 void _BSort::radixsort16(void)
526 {
527 int i;
528 // Initialize frequency array
529 int *ftab = (int *) calloc(65536, sizeof(int));
530 for (i=0; i<65536; i++)
531 ftab[i] = 0;
532 // Count occurences
533 unsigned char c1 = data[0];
534 for (i=0; i<size-1; i++)
535 {
536 unsigned char c2 = data[i+1];
537 ftab[(c1<<8)|c2] ++;
538 c1 = c2;
539 }
540 // Generate upper position
541 for (i=1;i<65536;i++)
542 ftab[i] += ftab[i-1];
543 // Fill rank array with upper bound
544 c1 = data[0];
545 for (i=0; i<size-2; i++)
546 {
547 unsigned char c2 = data[i+1];
548 rank[i] = ftab[(c1<<8)|c2];
549 c1 = c2;
550 }
551 // Fill posn array (backwards)
552 c1 = data[size-2];
553 for (i=size-3; i>=0; i--)
554 {
555 unsigned char c2 = data[i];
556 posn[ ftab[(c2<<8)|c1]-- ] = i;
557 c1 = c2;
558 }
559 // Fixup marker stuff
560 assert(data[size-1]==0);
561 c1 = data[size-2];
562 posn[0] = size-1;
563 posn[ ftab[(c1<<8)] ] = size-2;
564 rank[size-1] = 0;
565 rank[size-2] = ftab[(c1<<8)];
566 // Extra element
567 rank[size] = -1;
568 }
569
570
571
572 // _BSort::run -- main sort loop
573
574 void _BSort::run(int &markerpos)
575 {
576 int lo, hi;
577 assert(size>0);
578 assert(data[size-1]==0);
579 // Step 1: Radix sort
580 int depth = 0;
581 if (size > RADIX_THRESH)
582 {
583 radixsort16();
584 depth=2;
585 }
586 else
587 {
588 radixsort8();
589 depth=1;
590 }
591 // Step 2: Perform presort to depth PRESORT_DEPTH
592 for (lo=0; lo<size; lo++)
593 {
594 hi = rank[posn[lo]];
595 if (lo < hi)
596 quicksort3d(lo, hi, depth);
597 lo = hi;
598 }
599 depth = PRESORT_DEPTH;
600 // Step 3: Perform rank doubling
601 int again = 1;
602 while (again)
603 {
604 again = 0;
605 int sorted_lo = 0;
606 for (lo=0; lo<size; lo++)
607 {
608 hi = rank[posn[lo]&0xffffff];
609 if (lo == hi)
610 {
611 lo += (posn[lo]>>24) & 0xff;
612 }
613 else
614 {
615 if (hi-lo < RANKSORT_THRESH)
616 {
617 ranksort(lo, hi, depth);
618 }
619 else
620 {
621 again += 1;
622 while (sorted_lo < lo-1)
623 {
624 int step = mini(255, lo-1-sorted_lo);
625 posn[sorted_lo] = (posn[sorted_lo]&0xffffff) | (step<<24);
626 sorted_lo += step+1;
627 }
628 quicksort3r(lo, hi, depth);
629 sorted_lo = hi + 1;
630 }
631 lo = hi;
632 }
633 }
634 // Finish threading
635 while (sorted_lo < lo-1)
636 {
637 int step = mini(255, lo-1-sorted_lo);
638 posn[sorted_lo] = (posn[sorted_lo]&0xffffff) | (step<<24);
639 sorted_lo += step+1;
640 }
641 // Double depth
642 depth += depth;
643 }
644 // Step 4: Permute data
645 int i;
646 markerpos = -1;
647 for (i=0; i<size; i++)
648 rank[i] = data[i];
649 for (i=0; i<size; i++)
650 {
651 int j = posn[i] & 0xffffff;
652 if (j>0)
653 {
654 data[i] = rank[j-1];
655 }
656 else
657 {
658 data[i] = 0;
659 markerpos = i;
660 }
661 }
662 assert(markerpos>=0 && markerpos<size);
663 }
664
665
666 // ========================================
667 // -- Encoding
668
669 static void encode_raw(ZPEncoder &zp, int bits, int x)
670 {
671 int n = 1;
672 int m = (1<<bits);
673 while (n < m)
674 {
675 x = (x & (m-1)) << 1;
676 int b = (x >> bits);
677 zp.encode_without_context(b);
678 n = (n<<1) | b;
679 }
680 }
681
682 static void encode_binary(ZPEncoder &zp, ZPBitContext *ctx, int bits, int x)
683 {
684 // Require 2^bits-1 contexts
685 int n = 1;
686 int m = (1<<bits);
687 ctx = ctx - 1;
688 while (n < m)
689 {
690 x = (x & (m-1)) << 1;
691 int b = (x >> bits);
692 zp.encode(b, ctx[n]);
693 n = (n<<1) | b;
694 }
695 }
696
697 unsigned int BSEncoder::encode()
698 {
699 /////////////////////////////////
700 //////////// Block Sort Tranform
701
702 int markerpos = size-1;
703 blocksort(data,size,markerpos);
704
705 /////////////////////////////////
706 //////////// Encode Output Stream
707
708 // Header
709 ZPEncoder &zp = gzp;
710 encode_raw(gzp, 24, size);
711 // Determine and Encode Estimation Speed
712 int fshift = 0;
713 if (size < FREQS0)
714 {
715 fshift=0; zp.encode_without_context(0);
716 }
717 else if (size < FREQS1)
718 {
719 fshift = 1;
720 zp.encode_without_context(1);
721 zp.encode_without_context(0);
722 }
723 else
724 {
725 fshift = 2;
726 zp.encode_without_context(1);
727 zp.encode_without_context(1);
728 }
729 // MTF
730 unsigned char mtf[256];
731 unsigned char rmtf[256];
732 unsigned int freq[FREQMAX];
733 int m = 0;
734 for (m=0; m<256; m++)
735 mtf[m] = m;
736 for (m=0; m<256; m++)
737 rmtf[mtf[m]] = m;
738 int fadd = 4;
739 for (m=0; m<FREQMAX; m++)
740 freq[m] = 0;
741 // Encode
742 int i;
743 int mtfno = 3;
744 for (i=0; i<size; i++)
745 {
746 // Get MTF data
747 int c = data[i];
748 int ctxid = CTXIDS-1;
749 if (ctxid>mtfno) ctxid=mtfno;
750 mtfno = rmtf[c];
751 if (i==markerpos)
752 mtfno = 256;
753 // Encode using ZPCodec
754 int b;
755 ZPBitContext *cx = ctx;
756 b = (mtfno==0);
757 zp.encode(b, cx[ctxid]);
758 if (b) goto rotate; cx+=CTXIDS;
759 b = (mtfno==1);
760 zp.encode(b, cx[ctxid]);
761 if (b) goto rotate; cx+=CTXIDS;
762 b = (mtfno<4);
763 zp.encode(b, cx[0]);
764 if (b) { encode_binary(zp,cx+1,1,mtfno-2); goto rotate; }
765 cx+=1+1;
766 b = (mtfno<8);
767 zp.encode(b, cx[0]);
768 if (b) { encode_binary(zp,cx+1,2,mtfno-4); goto rotate; }
769 cx+=1+3;
770 b = (mtfno<16);
771 zp.encode(b, cx[0]);
772 if (b) { encode_binary(zp,cx+1,3,mtfno-8); goto rotate; }
773 cx+=1+7;
774 b = (mtfno<32);
775 zp.encode(b, cx[0]);
776 if (b) { encode_binary(zp,cx+1,4,mtfno-16); goto rotate; }
777 cx+=1+15;
778 b = (mtfno<64);
779 zp.encode(b, cx[0]);
780 if (b) { encode_binary(zp,cx+1,5,mtfno-32); goto rotate; }
781 cx+=1+31;
782 b = (mtfno<128);
783 zp.encode(b, cx[0]);
784 if (b) { encode_binary(zp,cx+1,6,mtfno-64); goto rotate; }
785 cx+=1+63;
786 b = (mtfno<256);
787 zp.encode(b, cx[0]);
788 if (b) { encode_binary(zp,cx+1,7,mtfno-128); goto rotate; }
789 continue;
790 // Rotate MTF according to empirical frequencies (new!)
791 rotate:
792 // Adjust frequencies for overflow
793 fadd = fadd + (fadd>>fshift);
794 if (fadd > 0x10000000)
795 {
796 fadd = fadd>>24;
797 freq[0] >>= 24;
798 freq[1] >>= 24;
799 freq[2] >>= 24;
800 freq[3] >>= 24;
801 for (int k=4; k<FREQMAX; k++)
802 freq[k] = freq[k]>>24;
803 }
804 // Relocate new char according to new freq
805 unsigned int fc = fadd;
806 if (mtfno < FREQMAX)
807 fc += freq[mtfno];
808 int k;
809 for (k=mtfno; k>=FREQMAX; k--)
810 {
811 mtf[k] = mtf[k-1];
812 rmtf[mtf[k]] = k;
813 }
814 for (; k>0 && fc>=freq[k-1]; k--)
815 {
816 mtf[k] = mtf[k-1];
817 freq[k] = freq[k-1];
818 rmtf[mtf[k]] = k;
819 }
820 mtf[k] = c;
821 freq[k] = fc;
822 rmtf[mtf[k]] = k;
823 }
824 // Terminate
825 return 0;
826 }
827
828 // ========================================
829 // --- Construction
830
831 BSEncoder::BSEncoder(FILE *f,const int xencoding)
832 : data(NULL), gzp(f)
833 {
834 const int encoding=(xencoding<MINBLOCK)?MINBLOCK:xencoding;
835 // Record block size
836 blocksize = encoding * 1024;
837 // Initialize context array
838 memset(ctx, 0, sizeof(ctx));
839 }
840
841 void BSEncoder::close()
842 {
843 // Flush
844 flush();
845 // Encode EOF marker
846 encode_raw(gzp, 24, 0);
847 // Free allocated memory
848 free(data);
849 data = NULL;
850 gzp.close();
851 }
852
853 BSEncoder::~BSEncoder()
854 {
855 if (data) close();
856 }
857
858 // ========================================
859 // -- ByteStream interface
860
861 void BSEncoder::flush()
862 {
863 if (bptr>0)
864 {
865 assert(bptr<(int)blocksize);
866 memset(data+bptr, 0, OVERFLOW);
867 size = bptr+1;
868 encode();
869 }
870 size = bptr = 0;
871 }
872
873 size_t BSEncoder::write(void *buffer, size_t sz)
874 {
875 // Trivial checks
876 if (sz == 0)
877 return 0;
878 // Loop
879 int copied = 0;
880 while (sz > 0)
881 {
882 // Initialize
883 if (!data)
884 {
885 bptr = 0;
886 data = (unsigned char *) calloc(blocksize+OVERFLOW, sizeof(unsigned char));
887 }
888 // Compute remaining
889 int bytes = blocksize - 1 - bptr;
890 if (bytes > (int)sz)
891 bytes = sz;
892 // Store date (todo: rle)
893 memcpy(data+bptr, buffer, bytes);
894 buffer = (void*)((char*)buffer + bytes);
895 bptr += bytes;
896 sz -= bytes;
897 copied += bytes;
898 offset += bytes;
899 // Flush when needed
900 if (bptr + 1 >= (int)blocksize)
901 flush();
902 }
903 // return
904 return copied;
905 }
906
907 size_t BSEncoder::writall(void *buffer, size_t wsize)
908 {
909 size_t total = 0;
910 while (wsize > 0)
911 {
912 size_t nitems = write(buffer, wsize);
913 total += nitems;
914 wsize -= nitems;
915 buffer = (void*)((char*)buffer + nitems);
916 }
917 return total;
918 }
919
920 void BSEncoder::write8 (unsigned int card)
921 {
922 unsigned char c[1];
923 c[0] = (card) & 0xff;
924 write((void*)c, sizeof(c));
925 }
926
927 void BSEncoder::write16(unsigned int card)
928 {
929 unsigned char c[2];
930 c[0] = (card>>8) & 0xff;
931 c[1] = (card) & 0xff;
932 writall((void*)c, sizeof(c));
933 }
934
935 void BSEncoder::write24(unsigned int card)
936 {
937 unsigned char c[3];
938 c[0] = (card>>16) & 0xff;
939 c[1] = (card>>8) & 0xff;
940 c[2] = (card) & 0xff;
941 writall((void*)c, sizeof(c));
942 }
943
944 void BSEncoder::write32(unsigned int card)
945 {
946 unsigned char c[4];
947 c[0] = (card>>24) & 0xff;
948 c[1] = (card>>16) & 0xff;
949 c[2] = (card>>8) & 0xff;
950 c[3] = (card) & 0xff;
951 writall((void*)c, sizeof(c));
952 }
953
954
955