source: trunk/libdjvu/BSEncodeByteStream.cpp @ 280

Last change on this file since 280 was 280, checked in by rbri, 11 years ago

DJVU plugin: djvulibre updated to version 3.5.22

File size: 24.5 KB
Line 
1//C-  -*- C++ -*-
2//C- -------------------------------------------------------------------
3//C- DjVuLibre-3.5
4//C- Copyright (c) 2002  Leon Bottou and Yann Le Cun.
5//C- Copyright (c) 2001  AT&T
6//C-
7//C- This software is subject to, and may be distributed under, the
8//C- GNU General Public License, either Version 2 of the license,
9//C- or (at your option) any later version. The license should have
10//C- accompanied the software or you may obtain a copy of the license
11//C- from the Free Software Foundation at http://www.fsf.org .
12//C-
13//C- This program is distributed in the hope that it will be useful,
14//C- but WITHOUT ANY WARRANTY; without even the implied warranty of
15//C- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16//C- GNU General Public License for more details.
17//C-
18//C- DjVuLibre-3.5 is derived from the DjVu(r) Reference Library from
19//C- Lizardtech Software.  Lizardtech Software has authorized us to
20//C- replace the original DjVu(r) Reference Library notice by the following
21//C- text (see doc/lizard2002.djvu and doc/lizardtech2007.djvu):
22//C-
23//C-  ------------------------------------------------------------------
24//C- | DjVu (r) Reference Library (v. 3.5)
25//C- | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.
26//C- | The DjVu Reference Library is protected by U.S. Pat. No.
27//C- | 6,058,214 and patents pending.
28//C- |
29//C- | This software is subject to, and may be distributed under, the
30//C- | GNU General Public License, either Version 2 of the license,
31//C- | or (at your option) any later version. The license should have
32//C- | accompanied the software or you may obtain a copy of the license
33//C- | from the Free Software Foundation at http://www.fsf.org .
34//C- |
35//C- | The computer code originally released by LizardTech under this
36//C- | license and unmodified by other parties is deemed "the LIZARDTECH
37//C- | ORIGINAL CODE."  Subject to any third party intellectual property
38//C- | claims, LizardTech grants recipient a worldwide, royalty-free,
39//C- | non-exclusive license to make, use, sell, or otherwise dispose of
40//C- | the LIZARDTECH ORIGINAL CODE or of programs derived from the
41//C- | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU
42//C- | General Public License.   This grant only confers the right to
43//C- | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to
44//C- | the extent such infringement is reasonably necessary to enable
45//C- | recipient to make, have made, practice, sell, or otherwise dispose
46//C- | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to
47//C- | any greater extent that may be necessary to utilize further
48//C- | modifications or combinations.
49//C- |
50//C- | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY
51//C- | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
52//C- | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF
53//C- | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
54//C- +------------------------------------------------------------------
55//
56// $Id: BSEncodeByteStream.cpp,v 1.9 2007/03/25 20:48:29 leonb Exp $
57// $Name: release_3_5_22 $
58
59#ifdef HAVE_CONFIG_H
60# include "config.h"
61#endif
62#if NEED_GNUG_PRAGMAS
63# pragma implementation
64#endif
65
66// - Author: Leon Bottou, 07/1998
67
68
69
70#include "BSByteStream.h"
71#include "GString.h"
72#undef BSORT_TIMER
73#ifdef BSORT_TIMER
74#include "GOS.h"
75#endif
76
77#include <stdlib.h>
78#include <stdio.h>
79#include <string.h>
80
81
82#ifdef HAVE_NAMESPACES
83namespace DJVU {
84# ifdef NOT_DEFINED // Just to fool emacs c++ mode
85}
86#endif
87#endif
88
89
90// ========================================
91// --- Assertion
92
93#define ASSERT(expr) do{if(!(expr))G_THROW("assertion ("#expr") failed");}while(0)
94
95
96
97// ========================================
98// --- Global Definitions
99           
100
101#ifdef OVERFLOW
102#undef OVERFLOW
103#endif
104// Overflow required when encoding
105static const int OVERFLOW=32;
106
107// Sorting tresholds
108static const int RANKSORT_THRESH=10;
109static const int QUICKSORT_STACK=512;
110static const int PRESORT_THRESH=10;
111static const int PRESORT_DEPTH=8;
112static const int RADIX_THRESH=32768;
113
114static const int FREQS0=100000;
115static const int FREQS1=1000000;
116
117// ========================================
118// -- Sorting Routines
119
120 
121class _BSort  // DJVU_CLASS
122{
123public:
124  ~_BSort();
125  _BSort(unsigned char *data, int size);
126  void run(int &markerpos);
127private:
128  // Members
129  int            size;
130  unsigned char *data;
131  unsigned int  *posn;
132  GPBuffer<unsigned int> gposn;
133  int           *rank;
134  GPBuffer<int> grank;
135  // Helpers
136  inline int GT(int p1, int p2, int depth);
137  inline int GTD(int p1, int p2, int depth);
138  // -- final in-depth sort
139  void ranksort(int lo, int hi, int d);
140  // -- doubling sort
141  int  pivot3r(int *rr, int lo, int hi);
142  void quicksort3r(int lo, int hi, int d);
143  // -- presort to depth PRESORT_DEPTH
144  unsigned char pivot3d(unsigned char *dd, int lo, int hi);
145  void quicksort3d(int lo, int hi, int d);
146  // -- radixsort
147  void radixsort16(void);
148  void radixsort8(void);
149};
150
151
152// blocksort -- the main entry point
153
154static void 
155blocksort(unsigned char *data, int size, int &markerpos)
156{
157  _BSort bsort(data, size);
158  bsort.run(markerpos);
159}
160
161
162// _BSort construction
163
164_BSort::_BSort(unsigned char *xdata, int xsize)
165  : size(xsize), data(xdata), gposn(posn,xsize), grank(rank,xsize+1)
166{
167  ASSERT(size>0 && size<0x1000000);
168  rank[size] = -1;
169}
170
171_BSort::~_BSort()
172{
173}
174
175
176
177// GT -- compare suffixes using rank information
178
179inline int 
180_BSort::GT(int p1, int p2, int depth)
181{
182  int r1, r2;
183  int twod = depth + depth;
184  while (1)
185    {
186      r1=rank[p1+depth]; r2=rank[p2+depth];
187      p1+=twod;  p2+=twod;
188      if (r1!=r2) 
189        return (r1>r2);
190      r1=rank[p1]; r2=rank[p2];
191      if (r1!=r2) 
192        return (r1>r2);
193      r1=rank[p1+depth]; r2=rank[p2+depth];
194      p1+=twod;  p2+=twod;
195      if (r1!=r2) 
196        return (r1>r2);
197      r1=rank[p1]; r2=rank[p2];
198      if (r1!=r2) 
199        return (r1>r2);
200      r1=rank[p1+depth]; r2=rank[p2+depth];
201      p1+=twod;  p2+=twod;
202      if (r1!=r2) 
203        return (r1>r2);
204      r1=rank[p1]; r2=rank[p2];
205      if (r1!=r2) 
206        return (r1>r2);
207      r1=rank[p1+depth]; r2=rank[p2+depth];
208      p1+=twod;  p2+=twod;
209      if (r1!=r2) 
210        return (r1>r2);
211      r1=rank[p1]; r2=rank[p2];
212      if (r1!=r2) 
213        return (r1>r2);
214    };
215}
216
217
218// _BSort::ranksort --
219// -- a simple insertion sort based on GT
220
221void 
222_BSort::ranksort(int lo, int hi, int depth)
223{
224  int i,j;
225  for (i=lo+1; i<=hi; i++)
226    {
227      int tmp = posn[i];
228      for(j=i-1; j>=lo && GT(posn[j], tmp, depth); j--)
229        posn[j+1] = posn[j];
230      posn[j+1] = tmp;
231    }
232  for(i=lo;i<=hi;i++) 
233    rank[posn[i]]=i;
234}
235
236// pivot -- return suitable pivot
237
238inline int
239_BSort::pivot3r(int *rr, int lo, int hi)
240{
241  int c1, c2, c3;
242  if (hi-lo > 256)
243    {
244      c1 = pivot3r(rr, lo, (6*lo+2*hi)/8);
245      c2 = pivot3r(rr, (5*lo+3*hi)/8, (3*lo+5*hi)/8);
246      c3 = pivot3r(rr, (2*lo+6*hi)/8, hi);
247    }
248  else
249    {
250      c1 = rr[posn[lo]];
251      c2 = rr[posn[(lo+hi)/2]];
252      c3 = rr[posn[hi]];
253    }
254  // Extract median
255  if (c1>c3)
256    { int tmp=c1; c1=c3; c3=tmp; }
257  if (c2<=c1)
258    return c1;
259  else if (c2>=c3)
260    return c3;
261  else
262    return c2;
263}
264
265
266// _BSort::quicksort3r -- Three way quicksort algorithm
267//    Sort suffixes based on rank at pos+depth
268//    The algorithm breaks into ranksort when size is
269//    smaller than RANKSORT_THRESH
270
271static inline int
272mini(int a, int b) 
273{
274  return (a<=b) ? a : b;
275}
276
277static inline void
278vswap(int i, int j, int n, unsigned int *x)
279{
280  while (n-- > 0) 
281    { int tmp = x[i]; x[i++]=x[j]; x[j++]=tmp; }
282}
283
284void 
285_BSort::quicksort3r(int lo, int hi, int depth)
286{
287  /* Initialize stack */
288  int slo[QUICKSORT_STACK];
289  int shi[QUICKSORT_STACK];
290  int sp = 1;
291  slo[0] = lo;
292  shi[0] = hi;
293  // Recursion elimination loop
294  while (--sp>=0)
295    {
296      lo = slo[sp];
297      hi = shi[sp];
298      // Test for insertion sort
299      if (hi-lo<RANKSORT_THRESH)
300        {
301          ranksort(lo, hi, depth);
302        }
303      else
304        {
305          int tmp;
306          int *rr=rank+depth;
307          int med = pivot3r(rr,lo,hi);
308          // -- positions are organized as follows:
309          //   [lo..l1[ [l1..l[ ]h..h1] ]h1..hi]
310          //      =        <       >        =
311          int l1 = lo;
312          int h1 = hi;
313          while (rr[posn[l1]]==med && l1<h1) { l1++; }
314          while (rr[posn[h1]]==med && l1<h1) { h1--; }
315          int l = l1;
316          int h = h1;
317          // -- partition set
318          for (;;)
319            {
320              while (l<=h)
321                {
322                  int c = rr[posn[l]] - med;
323                  if (c > 0) break;
324                  if (c == 0) { tmp=posn[l]; posn[l]=posn[l1]; posn[l1++]=tmp; }
325                  l++;
326                }
327              while (l<=h)
328                {
329                  int c = rr[posn[h]] - med;
330                  if (c < 0) break;
331                  if (c == 0) { tmp=posn[h]; posn[h]=posn[h1]; posn[h1--]=tmp; }
332                  h--;
333                }
334              if (l>h) break;
335              tmp=posn[l]; posn[l]=posn[h]; posn[h]=tmp;
336            }
337          // -- reorganize as follows
338          //   [lo..l1[ [l1..h1] ]h1..hi]
339          //      <        =        >
340          tmp = mini(l1-lo, l-l1);
341          vswap(lo, l-tmp, tmp, posn);
342          l1 = lo + (l-l1);
343          tmp = mini(hi-h1, h1-h);
344          vswap(hi-tmp+1, h+1, tmp, posn);
345          h1 = hi - (h1-h);
346          // -- process segments
347          ASSERT(sp+2<QUICKSORT_STACK);
348          // ----- middle segment (=?) [l1, h1]
349          for(int i=l1;i<=h1;i++) 
350            rank[posn[i]] = h1;
351          // ----- lower segment (<) [lo, l1[
352          if (l1 > lo)
353            {
354              for(int i=lo;i<l1;i++) 
355                rank[posn[i]]=l1-1;
356              slo[sp]=lo;
357              shi[sp]=l1-1;
358              if (slo[sp] < shi[sp]) 
359                sp++;
360            }
361          // ----- upper segment (>) ]h1, hi]
362          if (h1 < hi)
363            {
364              slo[sp]=h1+1;
365              shi[sp]=hi;
366              if (slo[sp] < shi[sp]) 
367                sp++;
368            }
369        }
370    }
371}
372
373
374
375
376
377
378// GTD -- compare suffixes using data information
379//  (up to depth PRESORT_DEPTH)
380
381inline int 
382_BSort::GTD(int p1, int p2, int depth)
383{
384  unsigned char c1, c2;
385  p1+=depth; p2+=depth;
386  while (depth < PRESORT_DEPTH)
387    {
388      // Perform two
389      c1=data[p1]; c2=data[p2];
390      if (c1!=c2) 
391        return (c1>c2);
392      c1=data[p1+1]; c2=data[p2+1];
393      p1+=2;  p2+=2; depth+=2;
394      if (c1!=c2) 
395        return (c1>c2);
396    }
397  if (p1<size && p2<size)
398    return 0;
399  return (p1<p2);
400}
401
402// pivot3d -- return suitable pivot
403
404inline unsigned char
405_BSort::pivot3d(unsigned char *rr, int lo, int hi)
406{
407  unsigned char c1, c2, c3;
408  if (hi-lo > 256)
409    {
410      c1 = pivot3d(rr, lo, (6*lo+2*hi)/8);
411      c2 = pivot3d(rr, (5*lo+3*hi)/8, (3*lo+5*hi)/8);
412      c3 = pivot3d(rr, (2*lo+6*hi)/8, hi);
413    }
414  else
415    {
416      c1 = rr[posn[lo]];
417      c2 = rr[posn[(lo+hi)/2]];
418      c3 = rr[posn[hi]];
419    }
420  // Extract median
421  if (c1>c3)
422    { int tmp=c1; c1=c3; c3=tmp; }
423  if (c2<=c1)
424    return c1;
425  else if (c2>=c3)
426    return c3;
427  else
428    return c2;
429}
430
431
432// _BSort::quicksort3d -- Three way quicksort algorithm
433//    Sort suffixes based on strings until reaching
434//    depth rank at pos+depth
435//    The algorithm breaks into ranksort when size is
436//    smaller than PRESORT_THRESH
437
438void 
439_BSort::quicksort3d(int lo, int hi, int depth)
440{
441  /* Initialize stack */
442  int slo[QUICKSORT_STACK];
443  int shi[QUICKSORT_STACK];
444  int sd[QUICKSORT_STACK];
445  int sp = 1;
446  slo[0] = lo;
447  shi[0] = hi;
448  sd[0] = depth;
449  // Recursion elimination loop
450  while (--sp>=0)
451    {
452      lo = slo[sp];
453      hi = shi[sp];
454      depth = sd[sp];
455      // Test for insertion sort
456      if (depth >= PRESORT_DEPTH)
457        {
458          for (int i=lo; i<=hi; i++)
459            rank[posn[i]] = hi;
460        }
461      else if (hi-lo<PRESORT_THRESH)
462        {
463          int i,j;
464          for (i=lo+1; i<=hi; i++)
465            {
466              int tmp = posn[i];
467              for(j=i-1; j>=lo && GTD(posn[j], tmp, depth); j--)
468                posn[j+1] = posn[j];
469              posn[j+1] = tmp;
470            }
471          for(i=hi;i>=lo;i=j)
472            {
473              int tmp = posn[i];
474              rank[tmp] = i;
475              for (j=i-1; j>=lo && !GTD(tmp,posn[j],depth); j--)
476                rank[posn[j]] = i;
477            }
478        }
479        else
480        {
481          int tmp;
482          unsigned char *dd=data+depth;
483          unsigned char med = pivot3d(dd,lo,hi);
484          // -- positions are organized as follows:
485          //   [lo..l1[ [l1..l[ ]h..h1] ]h1..hi]
486          //      =        <       >        =
487          int l1 = lo;
488          int h1 = hi;
489          while (dd[posn[l1]]==med && l1<h1) { l1++; }
490          while (dd[posn[h1]]==med && l1<h1) { h1--; }
491          int l = l1;
492          int h = h1;
493          // -- partition set
494          for (;;)
495            {
496              while (l<=h)
497                {
498                  int c = (int)dd[posn[l]] - (int)med;
499                  if (c > 0) break;
500                  if (c == 0) { tmp=posn[l]; posn[l]=posn[l1]; posn[l1++]=tmp; }
501                  l++;
502                }
503              while (l<=h)
504                {
505                  int c = (int)dd[posn[h]] - (int)med;
506                  if (c < 0) break;
507                  if (c == 0) { tmp=posn[h]; posn[h]=posn[h1]; posn[h1--]=tmp; }
508                  h--;
509                }
510              if (l>h) break;
511              tmp=posn[l]; posn[l]=posn[h]; posn[h]=tmp;
512            }
513          // -- reorganize as follows
514          //   [lo..l1[ [l1..h1] ]h1..hi]
515          //      <        =        >
516          tmp = mini(l1-lo, l-l1);
517          vswap(lo, l-tmp, tmp, posn);
518          l1 = lo + (l-l1);
519          tmp = mini(hi-h1, h1-h);
520          vswap(hi-tmp+1, h+1, tmp, posn);
521          h1 = hi - (h1-h);
522          // -- process segments
523          ASSERT(sp+3<QUICKSORT_STACK);
524          // ----- middle segment (=?) [l1, h1]
525          l = l1; h = h1;
526          if (med==0) // special case for marker [slow]
527            for (int i=l; i<=h; i++)
528              if ((int)posn[i]+depth == size-1)
529                { 
530                  tmp=posn[i]; posn[i]=posn[l]; posn[l]=tmp; 
531                  rank[tmp]=l++; break; 
532                }
533          if (l<h)
534            { slo[sp] = l; shi[sp] = h; sd[sp++] = depth+1; }
535          else if (l==h)
536            { rank[posn[h]] = h; }
537          // ----- lower segment (<) [lo, l1[
538          l = lo;
539          h = l1-1;
540          if (l<h)
541            { slo[sp] = l; shi[sp] = h; sd[sp++] = depth; }
542          else if (l==h)
543            { rank[posn[h]] = h; }
544          // ----- upper segment (>) ]h1, hi]
545          l = h1+1;
546          h = hi;
547          if (l<h)
548            { slo[sp] = l; shi[sp] = h; sd[sp++] = depth; }
549          else if (l==h)
550            { rank[posn[h]] = h; }
551        }
552    }
553}
554
555
556
557
558// _BSort::radixsort8 -- 8 bit radix sort
559
560void 
561_BSort::radixsort8(void)
562{
563  int i;
564  // Initialize frequency array
565  int lo[256], hi[256];
566  for (i=0; i<256; i++)
567    hi[i] = lo[i] = 0;
568  // Count occurences
569  for (i=0; i<size-1; i++)
570    hi[data[i]] ++;
571  // Compute positions (lo)
572  int last = 1;
573  for (i=0; i<256; i++)
574    {
575      lo[i] = last;
576      hi[i] = last + hi[i] - 1;
577      last = hi[i] + 1;
578    }
579  for (i=0; i<size-1; i++)
580    {
581      posn[ lo[data[i]]++ ] = i;
582      rank[ i ] = hi[data[i]];
583    }
584  // Process marker "$"
585  posn[0] = size-1;
586  rank[size-1] = 0;
587  // Extra element
588  rank[size] = -1;
589}
590
591
592// _BSort::radixsort16 -- 16 bit radix sort
593
594void 
595_BSort::radixsort16(void)
596{
597  int i;
598  // Initialize frequency array
599  int *ftab;
600  GPBuffer<int> gftab(ftab,65536);
601  for (i=0; i<65536; i++)
602    ftab[i] = 0;
603  // Count occurences
604  unsigned char c1 = data[0];
605  for (i=0; i<size-1; i++)
606    {
607      unsigned char c2 = data[i+1];
608      ftab[(c1<<8)|c2] ++;
609      c1 = c2;
610    }
611  // Generate upper position
612  for (i=1;i<65536;i++)
613    ftab[i] += ftab[i-1];
614  // Fill rank array with upper bound
615  c1 = data[0];
616  for (i=0; i<size-2; i++)
617    {
618      unsigned char c2 = data[i+1];
619      rank[i] = ftab[(c1<<8)|c2];
620      c1 = c2;
621    }
622  // Fill posn array (backwards)
623  c1 = data[size-2];
624  for (i=size-3; i>=0; i--)
625    {
626      unsigned char c2 = data[i];
627      posn[ ftab[(c2<<8)|c1]-- ] = i;
628      c1 = c2;
629    }
630  // Fixup marker stuff
631  ASSERT(data[size-1]==0);
632  c1 = data[size-2];
633  posn[0] = size-1;
634  posn[ ftab[(c1<<8)] ] = size-2;
635  rank[size-1] = 0;
636  rank[size-2] = ftab[(c1<<8)];
637  // Extra element
638  rank[size] = -1;
639}
640
641
642
643// _BSort::run -- main sort loop
644
645void
646_BSort::run(int &markerpos)
647{
648  int lo, hi;
649  ASSERT(size>0);
650  ASSERT(data[size-1]==0);
651#ifdef BSORT_TIMER
652  long start = GOS::ticks();
653#endif 
654  // Step 1: Radix sort
655  int depth = 0;
656  if (size > RADIX_THRESH)
657    { 
658      radixsort16();
659      depth=2;
660    }
661  else
662    { 
663      radixsort8(); 
664      depth=1;
665    }
666  // Step 2: Perform presort to depth PRESORT_DEPTH
667  for (lo=0; lo<size; lo++)
668    {
669      hi = rank[posn[lo]];
670      if (lo < hi)
671        quicksort3d(lo, hi, depth);
672      lo = hi;
673    }
674  depth = PRESORT_DEPTH;
675#ifdef BSORT_TIMER
676  long middle = GOS::ticks();
677#endif 
678  // Step 3: Perform rank doubling
679  int again = 1;
680  while (again)
681    {
682      again = 0;
683      int sorted_lo = 0;
684      for (lo=0; lo<size; lo++)
685        {
686          hi = rank[posn[lo]&0xffffff];
687          if (lo == hi)
688            {
689              lo += (posn[lo]>>24) & 0xff;
690            }
691          else
692            {
693              if (hi-lo < RANKSORT_THRESH)
694                {
695                  ranksort(lo, hi, depth);
696                }
697              else
698                {
699                  again += 1;
700                  while (sorted_lo < lo-1)
701                    {
702                      int step = mini(255, lo-1-sorted_lo);
703                      posn[sorted_lo] = (posn[sorted_lo]&0xffffff) | (step<<24);
704                      sorted_lo += step+1;
705                    }
706                  quicksort3r(lo, hi, depth);
707                  sorted_lo = hi + 1;
708                }
709              lo = hi;
710            }
711        }
712      // Finish threading
713      while (sorted_lo < lo-1)
714        {
715          int step = mini(255, lo-1-sorted_lo);
716          posn[sorted_lo] = (posn[sorted_lo]&0xffffff) | (step<<24);
717          sorted_lo += step+1;
718        }
719      // Double depth
720      depth += depth;
721    }
722  // Step 4: Permute data
723  int i;
724  markerpos = -1;
725  for (i=0; i<size; i++)
726    rank[i] = data[i];
727  for (i=0; i<size; i++)
728    {
729      int j = posn[i] & 0xffffff;
730      if (j>0) 
731        { 
732          data[i] = rank[j-1];
733        } 
734      else 
735        {
736          data[i] = 0;
737          markerpos = i;
738        }
739    }
740  ASSERT(markerpos>=0 && markerpos<size);
741#ifdef BSORT_TIMER
742  long end = GOS::ticks();
743  DjVuPrintErrorUTF8("Sorting time: %d bytes in %ld + %ld = %ld ms\n", 
744          size-1, middle-start, end-middle, end-start);
745#endif 
746}
747
748
749// ========================================
750// -- Encoding
751
752static void
753encode_raw(ZPCodec &zp, int bits, int x)
754{
755  int n = 1;
756  int m = (1<<bits);
757  while (n < m)
758    {
759      x = (x & (m-1)) << 1;
760      int b = (x >> bits);
761      zp.encoder(b);
762      n = (n<<1) | b;
763    }
764}
765
766static inline void
767encode_binary(ZPCodec &zp, BitContext *ctx, int bits, int x)
768{
769  // Require 2^bits-1  contexts
770  int n = 1;
771  int m = (1<<bits);
772  ctx = ctx - 1;
773  while (n < m)
774    {
775      x = (x & (m-1)) << 1;
776      int b = (x >> bits);
777      zp.encoder(b, ctx[n]);
778      n = (n<<1) | b;
779    }
780}
781
782class BSByteStream::Encode : public BSByteStream
783{
784public:
785  /** Creates a Static object for allocating the memory area of
786      length #sz# starting at address #buffer#. */
787  Encode(GP<ByteStream> bs);
788  ~Encode();
789  void init(const int encoding);
790  // Virtual functions
791  virtual size_t write(const void *buffer, size_t sz);
792  virtual void flush(void);
793protected:
794  unsigned int encode(void);
795};
796
797unsigned int
798BSByteStream::Encode::encode()
799{ 
800  /////////////////////////////////
801  ////////////  Block Sort Tranform
802
803  int markerpos = size-1;
804  blocksort(data,size,markerpos);
805
806  /////////////////////////////////
807  //////////// Encode Output Stream
808
809  // Header
810  ZPCodec &zp=*gzp;
811  encode_raw(zp, 24, size);
812  // Determine and Encode Estimation Speed
813  int fshift = 0;
814  if (size < FREQS0)
815    { fshift=0; zp.encoder(0); }
816  else if (size < FREQS1)
817    { fshift = 1; zp.encoder(1); zp.encoder(0); }
818  else
819    { fshift = 2; zp.encoder(1); zp.encoder(1); }
820  // MTF
821  unsigned char mtf[256];
822  unsigned char rmtf[256];
823  unsigned int  freq[FREQMAX];
824  int m = 0;
825  for (m=0; m<256; m++)
826    mtf[m] = m;
827  for (m=0; m<256; m++)
828    rmtf[mtf[m]] = m;
829  int fadd = 4;
830  for (m=0; m<FREQMAX; m++)
831    freq[m] = 0;
832  // Encode
833  int i;
834  int mtfno = 3;
835  for (i=0; i<size; i++)
836    {
837      // Get MTF data
838      int c = data[i];
839      int ctxid = CTXIDS-1;
840      if (ctxid>mtfno) ctxid=mtfno;
841      mtfno = rmtf[c];
842      if (i==markerpos)
843        mtfno = 256;
844      // Encode using ZPCoder
845      int b;
846      BitContext *cx = ctx;
847      b = (mtfno==0);
848      zp.encoder(b, cx[ctxid]);
849      if (b) goto rotate; cx+=CTXIDS;
850      b = (mtfno==1);
851      zp.encoder(b, cx[ctxid]);
852      if (b) goto rotate; cx+=CTXIDS;
853      b = (mtfno<4);
854      zp.encoder(b, cx[0]);
855      if (b) { encode_binary(zp,cx+1,1,mtfno-2); goto rotate; } 
856      cx+=1+1;
857      b = (mtfno<8);
858      zp.encoder(b, cx[0]);
859      if (b) { encode_binary(zp,cx+1,2,mtfno-4); goto rotate; } 
860      cx+=1+3;
861      b = (mtfno<16);
862      zp.encoder(b, cx[0]);
863      if (b) { encode_binary(zp,cx+1,3,mtfno-8); goto rotate; } 
864      cx+=1+7;
865      b = (mtfno<32);
866      zp.encoder(b, cx[0]);
867      if (b) { encode_binary(zp,cx+1,4,mtfno-16); goto rotate; } 
868      cx+=1+15;
869      b = (mtfno<64);
870      zp.encoder(b, cx[0]);
871      if (b) { encode_binary(zp,cx+1,5,mtfno-32); goto rotate; } 
872      cx+=1+31;
873      b = (mtfno<128);
874      zp.encoder(b, cx[0]);
875      if (b) { encode_binary(zp,cx+1,6,mtfno-64); goto rotate; } 
876      cx+=1+63;
877      b = (mtfno<256);
878      zp.encoder(b, cx[0]);
879      if (b) { encode_binary(zp,cx+1,7,mtfno-128); goto rotate; } 
880      continue;
881      // Rotate MTF according to empirical frequencies (new!)
882    rotate:
883      // Adjust frequencies for overflow
884      fadd = fadd + (fadd>>fshift);
885      if (fadd > 0x10000000) 
886        {
887          fadd = fadd>>24;
888          freq[0] >>= 24;
889          freq[1] >>= 24;
890          freq[2] >>= 24;
891          freq[3] >>= 24;
892          for (int k=4; k<FREQMAX; k++)
893            freq[k] = freq[k]>>24;
894        }
895      // Relocate new char according to new freq
896      unsigned int fc = fadd;
897      if (mtfno < FREQMAX)
898        fc += freq[mtfno];
899      int k;
900      for (k=mtfno; k>=FREQMAX; k--)
901        {
902          mtf[k] = mtf[k-1];
903          rmtf[mtf[k]] = k;
904        }
905      for (; k>0 && fc>=freq[k-1]; k--)
906        {
907          mtf[k] = mtf[k-1];
908          freq[k] = freq[k-1];
909          rmtf[mtf[k]] = k;
910        }
911      mtf[k] = c;
912      freq[k] = fc;
913      rmtf[mtf[k]] = k;
914    }
915  // Terminate
916  return 0;
917}
918
919// ========================================
920// --- Construction
921
922BSByteStream::Encode::Encode(GP<ByteStream> xbs)
923: BSByteStream(xbs) {}
924
925void
926BSByteStream::Encode::init(const int xencoding)
927{
928  gzp=ZPCodec::create(gbs,true,true);
929  const int encoding=(xencoding<MINBLOCK)?MINBLOCK:xencoding;
930  if (encoding > MAXBLOCK)
931    G_THROW( ERR_MSG("ByteStream.blocksize") "\t" + GUTF8String(MAXBLOCK) );
932  // Record block size
933  blocksize = encoding * 1024;
934  // Initialize context array
935}
936
937BSByteStream::Encode::~Encode()
938{
939  // Flush
940  flush();
941  // Encode EOF marker
942  encode_raw(*gzp, 24, 0);
943  // Free allocated memory
944}
945
946GP<ByteStream>
947BSByteStream::create(GP<ByteStream> xbs,const int blocksize)
948{
949  BSByteStream::Encode *rbs=new BSByteStream::Encode(xbs);
950  GP<ByteStream> retval=rbs;
951  rbs->init(blocksize);
952  return retval;
953}
954
955// ========================================
956// -- ByteStream interface
957
958void 
959BSByteStream::Encode::flush()
960{
961  if (bptr>0)
962  {
963    ASSERT(bptr<(int)blocksize);
964    memset(data+bptr, 0, OVERFLOW);
965    size = bptr+1;
966    encode();
967  }
968  size = bptr = 0;
969}
970
971size_t 
972BSByteStream::Encode::write(const void *buffer, size_t sz)
973{
974  // Trivial checks
975  if (sz == 0)
976    return 0;
977  // Loop
978  int copied = 0;
979  while (sz > 0)
980    {
981      // Initialize
982      if (!data) 
983        {
984          bptr = 0;
985          gdata.resize(blocksize+OVERFLOW);
986        }
987      // Compute remaining
988      int bytes = blocksize - 1 - bptr;
989      if (bytes > (int)sz)
990        bytes = sz;
991      // Store date (todo: rle)
992      memcpy(data+bptr, buffer, bytes);
993      buffer = (void*)((char*)buffer + bytes);
994      bptr += bytes;
995      sz -= bytes;
996      copied += bytes;
997      offset += bytes;
998      // Flush when needed
999      if (bptr + 1 >= (int)blocksize)
1000        flush();
1001    }
1002  // return
1003  return copied;
1004}
1005
1006
1007#ifdef HAVE_NAMESPACES
1008}
1009# ifndef NOT_USING_DJVU_NAMESPACE
1010using namespace DJVU;
1011# endif
1012#endif
Note: See TracBrowser for help on using the repository browser.