source: trunk/libdjvu/BSEncodeByteStream.cpp @ 17

Last change on this file since 17 was 17, checked in by Eugene Romanenko, 15 years ago

update makefiles, remove absolute paths, update djvulibre to version 3.5.17

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