source: trunk/libdjvu/BSByteStream.cpp @ 15

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

needed libs update

File size: 13.0 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: BSByteStream.cpp,v 1.8 2003/11/07 22:08:20 leonb Exp $
55// $Name: release_3_5_16 $
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#include <stdlib.h>
67#include <stdio.h>
68#include <string.h>
69#include "BSByteStream.h"
70#undef BSORT_TIMER
71#ifdef BSORT_TIMER
72#include "GOS.h"
73#endif
74
75
76#ifdef HAVE_NAMESPACES
77namespace DJVU {
78# ifdef NOT_DEFINED // Just to fool emacs c++ mode
79}
80#endif
81#endif
82
83class BSByteStream::Decode : public BSByteStream
84{
85public:
86  /** Creates a Static object for allocating the memory area of
87      length #sz# starting at address #buffer#. */
88  Decode(GP<ByteStream> bs);
89  ~Decode();
90  void init(void);
91  // Virtual functions
92  virtual size_t read(void *buffer, size_t sz);
93  virtual void flush(void);
94protected:
95  unsigned int decode(void);
96private:
97  bool eof;
98};
99
100// ========================================
101// --- Assertion
102
103#define ASSERT(expr) do{if(!(expr))G_THROW("assertion ("#expr") failed");}while(0)
104
105// ========================================
106// --- Construction
107
108BSByteStream::BSByteStream(GP<ByteStream> xbs)
109: offset(0), bptr(0), blocksize(0), size(0), bs(xbs),
110  gbs(xbs), gdata(data,0)
111{
112  // Initialize context array
113  memset(ctx, 0, sizeof(ctx));
114}
115
116BSByteStream::~BSByteStream() {}
117
118BSByteStream::Decode::Decode(GP<ByteStream> xbs)
119: BSByteStream(xbs), eof(false) {}
120
121void
122BSByteStream::Decode::init(void)
123{
124  gzp=ZPCodec::create(gbs,false,true);
125}
126
127BSByteStream::Decode::~Decode() {}
128
129GP<ByteStream>
130BSByteStream::create(GP<ByteStream> xbs)
131{
132  BSByteStream::Decode *rbs=new BSByteStream::Decode(xbs);
133  GP<ByteStream> retval=rbs;
134  rbs->init();
135  return retval;
136}
137
138void 
139BSByteStream::Decode::flush()
140{
141  size = bptr = 0;
142}
143
144// ========================================
145// -- Decoding
146
147
148static int 
149decode_raw(ZPCodec &zp, int bits)
150{
151  int n = 1;
152  const int m = (1<<bits);
153  while (n < m)
154    {
155      const int b = zp.decoder();
156      n = (n<<1) | b;
157    }
158  return n - m;
159}
160
161static inline int 
162decode_binary(ZPCodec &zp, BitContext *ctx, int bits)
163{
164  int n = 1;
165  int m = (1<<bits);
166  ctx = ctx - 1;
167  while (n < m)
168    {
169      int b = zp.decoder(ctx[n]);
170      n = (n<<1) | b;
171    }
172  return n - m;
173}
174
175
176static inline void
177assignmtf(unsigned char xmtf[256])
178{
179  static const unsigned char mtf[256]={
180    0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,
181    0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F,
182    0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,
183    0x18,0x19,0x1A,0x1B,0x1C,0x1D,0x1E,0x1F,
184    0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,
185    0x28,0x29,0x2A,0x2B,0x2C,0x2D,0x2E,0x2F,
186    0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,
187    0x38,0x39,0x3A,0x3B,0x3C,0x3D,0x3E,0x3F,
188    0x40,0x41,0x42,0x43,0x44,0x45,0x46,0x47,
189    0x48,0x49,0x4A,0x4B,0x4C,0x4D,0x4E,0x4F,
190    0x50,0x51,0x52,0x53,0x54,0x55,0x56,0x57,
191    0x58,0x59,0x5A,0x5B,0x5C,0x5D,0x5E,0x5F,
192    0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,
193    0x68,0x69,0x6A,0x6B,0x6C,0x6D,0x6E,0x6F,
194    0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,
195    0x78,0x79,0x7A,0x7B,0x7C,0x7D,0x7E,0x7F,
196    0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,
197    0x88,0x89,0x8A,0x8B,0x8C,0x8D,0x8E,0x8F,
198    0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,
199    0x98,0x99,0x9A,0x9B,0x9C,0x9D,0x9E,0x9F,
200    0xA0,0xA1,0xA2,0xA3,0xA4,0xA5,0xA6,0xA7,
201    0xA8,0xA9,0xAA,0xAB,0xAC,0xAD,0xAE,0xAF,
202    0xB0,0xB1,0xB2,0xB3,0xB4,0xB5,0xB6,0xB7,
203    0xB8,0xB9,0xBA,0xBB,0xBC,0xBD,0xBE,0xBF,
204    0xC0,0xC1,0xC2,0xC3,0xC4,0xC5,0xC6,0xC7,
205    0xC8,0xC9,0xCA,0xCB,0xCC,0xCD,0xCE,0xCF,
206    0xD0,0xD1,0xD2,0xD3,0xD4,0xD5,0xD6,0xD7,
207    0xD8,0xD9,0xDA,0xDB,0xDC,0xDD,0xDE,0xDF,
208    0xE0,0xE1,0xE2,0xE3,0xE4,0xE5,0xE6,0xE7,
209    0xE8,0xE9,0xEA,0xEB,0xEC,0xED,0xEE,0xEF,
210    0xF0,0xF1,0xF2,0xF3,0xF4,0xF5,0xF6,0xF7,
211    0xF8,0xF9,0xFA,0xFB,0xFC,0xFD,0xFE,0xFF};
212  memcpy(xmtf,mtf,sizeof(mtf));
213}
214 
215unsigned int
216BSByteStream::Decode::decode(void)
217{
218  /////////////////////////////////
219  ////////////  Decode input stream
220 
221  int i;
222  // Decode block size
223  ZPCodec &zp=*gzp;
224  size = decode_raw(zp, 24);
225  if (!size)
226    return 0;
227  if (size>MAXBLOCK*1024)
228    G_THROW( ERR_MSG("ByteStream.corrupt") );
229  // Allocate
230  if ((int)blocksize < size)
231    {
232      blocksize = size;
233      if (data)
234      {
235        gdata.resize(0);
236      }
237    }
238  if (! data) 
239    gdata.resize(blocksize);
240  // Decode Estimation Speed
241  int fshift = 0;
242  if (zp.decoder())
243    {
244      fshift += 1;
245      if (zp.decoder())
246        fshift += 1;
247    }
248  // Prepare Quasi MTF
249  static const unsigned char xmtf[256]={
250    0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,
251    0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F,
252    0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,
253    0x18,0x19,0x1A,0x1B,0x1C,0x1D,0x1E,0x1F,
254    0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,
255    0x28,0x29,0x2A,0x2B,0x2C,0x2D,0x2E,0x2F,
256    0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,
257    0x38,0x39,0x3A,0x3B,0x3C,0x3D,0x3E,0x3F,
258    0x40,0x41,0x42,0x43,0x44,0x45,0x46,0x47,
259    0x48,0x49,0x4A,0x4B,0x4C,0x4D,0x4E,0x4F,
260    0x50,0x51,0x52,0x53,0x54,0x55,0x56,0x57,
261    0x58,0x59,0x5A,0x5B,0x5C,0x5D,0x5E,0x5F,
262    0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,
263    0x68,0x69,0x6A,0x6B,0x6C,0x6D,0x6E,0x6F,
264    0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,
265    0x78,0x79,0x7A,0x7B,0x7C,0x7D,0x7E,0x7F,
266    0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,
267    0x88,0x89,0x8A,0x8B,0x8C,0x8D,0x8E,0x8F,
268    0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,
269    0x98,0x99,0x9A,0x9B,0x9C,0x9D,0x9E,0x9F,
270    0xA0,0xA1,0xA2,0xA3,0xA4,0xA5,0xA6,0xA7,
271    0xA8,0xA9,0xAA,0xAB,0xAC,0xAD,0xAE,0xAF,
272    0xB0,0xB1,0xB2,0xB3,0xB4,0xB5,0xB6,0xB7,
273    0xB8,0xB9,0xBA,0xBB,0xBC,0xBD,0xBE,0xBF,
274    0xC0,0xC1,0xC2,0xC3,0xC4,0xC5,0xC6,0xC7,
275    0xC8,0xC9,0xCA,0xCB,0xCC,0xCD,0xCE,0xCF,
276    0xD0,0xD1,0xD2,0xD3,0xD4,0xD5,0xD6,0xD7,
277    0xD8,0xD9,0xDA,0xDB,0xDC,0xDD,0xDE,0xDF,
278    0xE0,0xE1,0xE2,0xE3,0xE4,0xE5,0xE6,0xE7,
279    0xE8,0xE9,0xEA,0xEB,0xEC,0xED,0xEE,0xEF,
280    0xF0,0xF1,0xF2,0xF3,0xF4,0xF5,0xF6,0xF7,
281    0xF8,0xF9,0xFA,0xFB,0xFC,0xFD,0xFE,0xFF};
282  unsigned char mtf[256];
283  memcpy(mtf,xmtf,sizeof(xmtf));
284  unsigned int freq[FREQMAX];
285  memset(freq,0,sizeof(freq));
286  int fadd = 4;
287  // Decode
288  int mtfno = 3;
289  int markerpos = -1;
290  for (i=0; i<size; i++)
291    {
292      int ctxid = CTXIDS-1;
293      if (ctxid>mtfno) ctxid=mtfno;
294      BitContext *cx = ctx;
295      if (zp.decoder(cx[ctxid]))
296        { mtfno=0; data[i]=mtf[mtfno]; goto rotate; }
297      cx+=CTXIDS;
298      if (zp.decoder(cx[ctxid]))
299        { mtfno=1; data[i]=mtf[mtfno]; goto rotate; } 
300      cx+=CTXIDS;
301      if (zp.decoder(cx[0]))
302        { mtfno=2+decode_binary(zp,cx+1,1); data[i]=mtf[mtfno]; goto rotate; } 
303      cx+=1+1;
304      if (zp.decoder(cx[0]))
305        { mtfno=4+decode_binary(zp,cx+1,2); data[i]=mtf[mtfno]; goto rotate; } 
306      cx+=1+3;
307      if (zp.decoder(cx[0]))
308        { mtfno=8+decode_binary(zp,cx+1,3); data[i]=mtf[mtfno]; goto rotate; } 
309      cx+=1+7;
310      if (zp.decoder(cx[0]))
311        { mtfno=16+decode_binary(zp,cx+1,4); data[i]=mtf[mtfno]; goto rotate; } 
312      cx+=1+15;
313      if (zp.decoder(cx[0]))
314        { mtfno=32+decode_binary(zp,cx+1,5); data[i]=mtf[mtfno]; goto rotate; } 
315      cx+=1+31;
316      if (zp.decoder(cx[0]))
317        { mtfno=64+decode_binary(zp,cx+1,6); data[i]=mtf[mtfno]; goto rotate; } 
318      cx+=1+63;
319      if (zp.decoder(cx[0]))
320        { mtfno=128+decode_binary(zp,cx+1,7); data[i]=mtf[mtfno]; goto rotate; } 
321      mtfno=256;
322      data[i]=0;
323      markerpos=i;
324      continue;
325      // Rotate mtf according to empirical frequencies (new!)
326    rotate:
327      // Adjust frequencies for overflow
328      int k;
329      fadd = fadd + (fadd>>fshift);
330      if (fadd > 0x10000000) 
331        {
332          fadd    >>= 24;
333          freq[0] >>= 24;
334          freq[1] >>= 24;
335          freq[2] >>= 24;
336          freq[3] >>= 24;
337          for (k=4; k<FREQMAX; k++)
338            freq[k] = freq[k]>>24;
339        }
340      // Relocate new char according to new freq
341      unsigned int fc = fadd;
342      if (mtfno < FREQMAX)
343        fc += freq[mtfno];
344      for (k=mtfno; k>=FREQMAX; k--) 
345        mtf[k] = mtf[k-1];
346      for (; k>0 && fc>=freq[k-1]; k--)
347        {
348          mtf[k] = mtf[k-1];
349          freq[k] = freq[k-1];
350        }
351      mtf[k] = data[i];
352      freq[k] = fc;
353    }
354 
355
356  /////////////////////////////////
357  ////////// Reconstruct the string
358 
359  if (markerpos<1 || markerpos>=size)
360    G_THROW( ERR_MSG("ByteStream.corrupt") );
361  // Allocate pointers
362  unsigned int *posn;
363  GPBuffer<unsigned int> gposn(posn,blocksize);
364  memset(posn, 0, sizeof(unsigned int)*size);
365  // Prepare count buffer
366  int count[256];
367  for (i=0; i<256; i++)
368    count[i] = 0;
369  // Fill count buffer
370  for (i=0; i<markerpos; i++) 
371    {
372      unsigned char c = data[i];
373      posn[i] = (c<<24) | (count[c] & 0xffffff);
374      count[c] += 1;
375    }
376  for (i=markerpos+1; i<size; i++)
377    {
378      unsigned char c = data[i];
379      posn[i] = (c<<24) | (count[c] & 0xffffff);
380      count[c] += 1;
381    }
382  // Compute sorted char positions
383  int last = 1;
384  for (i=0; i<256; i++)
385    {
386      int tmp = count[i];
387      count[i] = last;
388      last += tmp;
389    }
390  // Undo the sort transform
391  i = 0;
392  last = size-1;
393  while (last>0)
394    {
395      unsigned int n = posn[i];
396      unsigned char c = (posn[i]>>24);
397      data[--last] = c;
398      i = count[c] + (n & 0xffffff);
399    }
400  // Free and check
401  if (i != markerpos)
402    G_THROW( ERR_MSG("ByteStream.corrupt") );
403  return size;
404}
405
406
407
408// ========================================
409// -- ByteStream interface
410
411
412
413long 
414BSByteStream::tell() const
415{
416  return offset;
417}
418
419size_t 
420BSByteStream::Decode::read(void *buffer, size_t sz)
421{
422  if (eof)
423    return 0;
424  // Loop
425  int copied = 0;
426  while (sz>0 && !eof)
427    {
428      // Decode if needed
429      if (!size)
430        {
431          bptr = 0;
432          if (! decode()) 
433          {
434            size = 1 ;
435            eof = true;
436          }
437          size -= 1;
438        }
439      // Compute remaining
440      int bytes = size;
441      if (bytes > (int)sz)
442        bytes = sz;
443      // Transfer
444      if (buffer && bytes)
445        {
446          memcpy(buffer, data+bptr, bytes);
447          buffer = (void*)((char*)buffer + bytes);
448        }
449      size -= bytes;
450      bptr += bytes;
451      sz -= bytes;
452      copied += bytes;
453      offset += bytes;
454    }
455  // Return copied bytes
456  return copied;
457}
458
459
460#ifdef HAVE_NAMESPACES
461}
462# ifndef NOT_USING_DJVU_NAMESPACE
463using namespace DJVU;
464# endif
465#endif
Note: See TracBrowser for help on using the repository browser.