• Skip to content
  • Skip to link menu
KDE 3.5 API Reference
  • KDE API Reference
  • API Reference
  • Sitemap
  • Contact Us
 

kviewshell

BSByteStream.cpp

Go to the documentation of this file.
00001 //C-  -*- C++ -*-
00002 //C- -------------------------------------------------------------------
00003 //C- DjVuLibre-3.5
00004 //C- Copyright (c) 2002  Leon Bottou and Yann Le Cun.
00005 //C- Copyright (c) 2001  AT&T
00006 //C-
00007 //C- This software is subject to, and may be distributed under, the
00008 //C- GNU General Public License, Version 2. The license should have
00009 //C- accompanied the software or you may obtain a copy of the license
00010 //C- from the Free Software Foundation at http://www.fsf.org .
00011 //C-
00012 //C- This program is distributed in the hope that it will be useful,
00013 //C- but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 //C- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 //C- GNU General Public License for more details.
00016 //C- 
00017 //C- DjVuLibre-3.5 is derived from the DjVu(r) Reference Library
00018 //C- distributed by Lizardtech Software.  On July 19th 2002, Lizardtech 
00019 //C- Software authorized us to replace the original DjVu(r) Reference 
00020 //C- Library notice by the following text (see doc/lizard2002.djvu):
00021 //C-
00022 //C-  ------------------------------------------------------------------
00023 //C- | DjVu (r) Reference Library (v. 3.5)
00024 //C- | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.
00025 //C- | The DjVu Reference Library is protected by U.S. Pat. No.
00026 //C- | 6,058,214 and patents pending.
00027 //C- |
00028 //C- | This software is subject to, and may be distributed under, the
00029 //C- | GNU General Public License, Version 2. The license should have
00030 //C- | accompanied the software or you may obtain a copy of the license
00031 //C- | from the Free Software Foundation at http://www.fsf.org .
00032 //C- |
00033 //C- | The computer code originally released by LizardTech under this
00034 //C- | license and unmodified by other parties is deemed "the LIZARDTECH
00035 //C- | ORIGINAL CODE."  Subject to any third party intellectual property
00036 //C- | claims, LizardTech grants recipient a worldwide, royalty-free, 
00037 //C- | non-exclusive license to make, use, sell, or otherwise dispose of 
00038 //C- | the LIZARDTECH ORIGINAL CODE or of programs derived from the 
00039 //C- | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU 
00040 //C- | General Public License.   This grant only confers the right to 
00041 //C- | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to 
00042 //C- | the extent such infringement is reasonably necessary to enable 
00043 //C- | recipient to make, have made, practice, sell, or otherwise dispose 
00044 //C- | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to 
00045 //C- | any greater extent that may be necessary to utilize further 
00046 //C- | modifications or combinations.
00047 //C- |
00048 //C- | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY
00049 //C- | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
00050 //C- | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF
00051 //C- | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
00052 //C- +------------------------------------------------------------------
00053 // 
00054 // $Id: BSByteStream.cpp,v 1.8 2003/11/07 22:08:20 leonb Exp $
00055 // $Name: release_3_5_15 $
00056 
00057 #ifdef HAVE_CONFIG_H
00058 # include "config.h"
00059 #endif
00060 #if NEED_GNUG_PRAGMAS
00061 # pragma implementation
00062 #endif
00063 
00064 // - Author: Leon Bottou, 07/1998
00065 
00066 #include <stdlib.h>
00067 #include <stdio.h>
00068 #include <string.h>
00069 #include "BSByteStream.h"
00070 #undef BSORT_TIMER
00071 #ifdef BSORT_TIMER
00072 #include "GOS.h"
00073 #endif
00074 
00075 
00076 #ifdef HAVE_NAMESPACES
00077 namespace DJVU {
00078 # ifdef NOT_DEFINED // Just to fool emacs c++ mode
00079 }
00080 #endif
00081 #endif
00082 
00083 class BSByteStream::Decode : public BSByteStream
00084 {
00085 public:
00088   Decode(GP<ByteStream> bs);
00089   ~Decode();
00090   void init(void);
00091   // Virtual functions
00092   virtual size_t read(void *buffer, size_t sz);
00093   virtual void flush(void);
00094 protected:
00095   unsigned int decode(void);
00096 private:
00097   bool eof;
00098 };
00099 
00100 // ========================================
00101 // --- Assertion
00102 
00103 #define ASSERT(expr) do{if(!(expr))G_THROW("assertion ("#expr") failed");}while(0)
00104 
00105 // ========================================
00106 // --- Construction
00107 
00108 BSByteStream::BSByteStream(GP<ByteStream> xbs)
00109 : offset(0), bptr(0), blocksize(0), size(0), bs(xbs),
00110   gbs(xbs), gdata(data,0)
00111 {
00112   // Initialize context array
00113   memset(ctx, 0, sizeof(ctx));
00114 }
00115 
00116 BSByteStream::~BSByteStream() {}
00117 
00118 BSByteStream::Decode::Decode(GP<ByteStream> xbs)
00119 : BSByteStream(xbs), eof(false) {}
00120 
00121 void
00122 BSByteStream::Decode::init(void)
00123 {
00124   gzp=ZPCodec::create(gbs,false,true);
00125 }
00126 
00127 BSByteStream::Decode::~Decode() {}
00128 
00129 GP<ByteStream>
00130 BSByteStream::create(GP<ByteStream> xbs)
00131 {
00132   BSByteStream::Decode *rbs=new BSByteStream::Decode(xbs);
00133   GP<ByteStream> retval=rbs;
00134   rbs->init();
00135   return retval;
00136 }
00137 
00138 void 
00139 BSByteStream::Decode::flush()
00140 {
00141   size = bptr = 0;
00142 }
00143 
00144 // ========================================
00145 // -- Decoding
00146 
00147 
00148 static int 
00149 decode_raw(ZPCodec &zp, int bits)
00150 {
00151   int n = 1;
00152   const int m = (1<<bits);
00153   while (n < m)
00154     {
00155       const int b = zp.decoder();
00156       n = (n<<1) | b;
00157     }
00158   return n - m;
00159 }
00160 
00161 static inline int 
00162 decode_binary(ZPCodec &zp, BitContext *ctx, int bits)
00163 {
00164   int n = 1;
00165   int m = (1<<bits);
00166   ctx = ctx - 1;
00167   while (n < m)
00168     {
00169       int b = zp.decoder(ctx[n]);
00170       n = (n<<1) | b;
00171     }
00172   return n - m;
00173 }
00174 
00175 
00176 static inline void
00177 assignmtf(unsigned char xmtf[256])
00178 {
00179   static const unsigned char mtf[256]={
00180     0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,
00181     0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F,
00182     0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,
00183     0x18,0x19,0x1A,0x1B,0x1C,0x1D,0x1E,0x1F,
00184     0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,
00185     0x28,0x29,0x2A,0x2B,0x2C,0x2D,0x2E,0x2F,
00186     0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,
00187     0x38,0x39,0x3A,0x3B,0x3C,0x3D,0x3E,0x3F,
00188     0x40,0x41,0x42,0x43,0x44,0x45,0x46,0x47,
00189     0x48,0x49,0x4A,0x4B,0x4C,0x4D,0x4E,0x4F,
00190     0x50,0x51,0x52,0x53,0x54,0x55,0x56,0x57,
00191     0x58,0x59,0x5A,0x5B,0x5C,0x5D,0x5E,0x5F,
00192     0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,
00193     0x68,0x69,0x6A,0x6B,0x6C,0x6D,0x6E,0x6F,
00194     0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,
00195     0x78,0x79,0x7A,0x7B,0x7C,0x7D,0x7E,0x7F,
00196     0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,
00197     0x88,0x89,0x8A,0x8B,0x8C,0x8D,0x8E,0x8F,
00198     0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,
00199     0x98,0x99,0x9A,0x9B,0x9C,0x9D,0x9E,0x9F,
00200     0xA0,0xA1,0xA2,0xA3,0xA4,0xA5,0xA6,0xA7,
00201     0xA8,0xA9,0xAA,0xAB,0xAC,0xAD,0xAE,0xAF,
00202     0xB0,0xB1,0xB2,0xB3,0xB4,0xB5,0xB6,0xB7,
00203     0xB8,0xB9,0xBA,0xBB,0xBC,0xBD,0xBE,0xBF,
00204     0xC0,0xC1,0xC2,0xC3,0xC4,0xC5,0xC6,0xC7,
00205     0xC8,0xC9,0xCA,0xCB,0xCC,0xCD,0xCE,0xCF,
00206     0xD0,0xD1,0xD2,0xD3,0xD4,0xD5,0xD6,0xD7,
00207     0xD8,0xD9,0xDA,0xDB,0xDC,0xDD,0xDE,0xDF,
00208     0xE0,0xE1,0xE2,0xE3,0xE4,0xE5,0xE6,0xE7,
00209     0xE8,0xE9,0xEA,0xEB,0xEC,0xED,0xEE,0xEF,
00210     0xF0,0xF1,0xF2,0xF3,0xF4,0xF5,0xF6,0xF7,
00211     0xF8,0xF9,0xFA,0xFB,0xFC,0xFD,0xFE,0xFF};
00212   memcpy(xmtf,mtf,sizeof(mtf));
00213 }
00214   
00215 unsigned int
00216 BSByteStream::Decode::decode(void)
00217 {
00220   
00221   int i;
00222   // Decode block size
00223   ZPCodec &zp=*gzp;
00224   size = decode_raw(zp, 24);
00225   if (!size)
00226     return 0;
00227   if (size>MAXBLOCK*1024)
00228     G_THROW( ERR_MSG("ByteStream.corrupt") );
00229   // Allocate
00230   if ((int)blocksize < size)
00231     {
00232       blocksize = size;
00233       if (data)
00234       {
00235         gdata.resize(0);
00236       }
00237     }
00238   if (! data) 
00239     gdata.resize(blocksize);
00240   // Decode Estimation Speed
00241   int fshift = 0;
00242   if (zp.decoder())
00243     {
00244       fshift += 1;
00245       if (zp.decoder())
00246         fshift += 1;
00247     }
00248   // Prepare Quasi MTF
00249   static const unsigned char xmtf[256]={
00250     0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,
00251     0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F,
00252     0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,
00253     0x18,0x19,0x1A,0x1B,0x1C,0x1D,0x1E,0x1F,
00254     0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,
00255     0x28,0x29,0x2A,0x2B,0x2C,0x2D,0x2E,0x2F,
00256     0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,
00257     0x38,0x39,0x3A,0x3B,0x3C,0x3D,0x3E,0x3F,
00258     0x40,0x41,0x42,0x43,0x44,0x45,0x46,0x47,
00259     0x48,0x49,0x4A,0x4B,0x4C,0x4D,0x4E,0x4F,
00260     0x50,0x51,0x52,0x53,0x54,0x55,0x56,0x57,
00261     0x58,0x59,0x5A,0x5B,0x5C,0x5D,0x5E,0x5F,
00262     0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,
00263     0x68,0x69,0x6A,0x6B,0x6C,0x6D,0x6E,0x6F,
00264     0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,
00265     0x78,0x79,0x7A,0x7B,0x7C,0x7D,0x7E,0x7F,
00266     0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,
00267     0x88,0x89,0x8A,0x8B,0x8C,0x8D,0x8E,0x8F,
00268     0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,
00269     0x98,0x99,0x9A,0x9B,0x9C,0x9D,0x9E,0x9F,
00270     0xA0,0xA1,0xA2,0xA3,0xA4,0xA5,0xA6,0xA7,
00271     0xA8,0xA9,0xAA,0xAB,0xAC,0xAD,0xAE,0xAF,
00272     0xB0,0xB1,0xB2,0xB3,0xB4,0xB5,0xB6,0xB7,
00273     0xB8,0xB9,0xBA,0xBB,0xBC,0xBD,0xBE,0xBF,
00274     0xC0,0xC1,0xC2,0xC3,0xC4,0xC5,0xC6,0xC7,
00275     0xC8,0xC9,0xCA,0xCB,0xCC,0xCD,0xCE,0xCF,
00276     0xD0,0xD1,0xD2,0xD3,0xD4,0xD5,0xD6,0xD7,
00277     0xD8,0xD9,0xDA,0xDB,0xDC,0xDD,0xDE,0xDF,
00278     0xE0,0xE1,0xE2,0xE3,0xE4,0xE5,0xE6,0xE7,
00279     0xE8,0xE9,0xEA,0xEB,0xEC,0xED,0xEE,0xEF,
00280     0xF0,0xF1,0xF2,0xF3,0xF4,0xF5,0xF6,0xF7,
00281     0xF8,0xF9,0xFA,0xFB,0xFC,0xFD,0xFE,0xFF};
00282   unsigned char mtf[256];
00283   memcpy(mtf,xmtf,sizeof(xmtf));
00284   unsigned int freq[FREQMAX];
00285   memset(freq,0,sizeof(freq));
00286   int fadd = 4;
00287   // Decode
00288   int mtfno = 3;
00289   int markerpos = -1;
00290   for (i=0; i<size; i++)
00291     {
00292       int ctxid = CTXIDS-1;
00293       if (ctxid>mtfno) ctxid=mtfno;
00294       BitContext *cx = ctx;
00295       if (zp.decoder(cx[ctxid]))
00296         { mtfno=0; data[i]=mtf[mtfno]; goto rotate; }
00297       cx+=CTXIDS;
00298       if (zp.decoder(cx[ctxid]))
00299         { mtfno=1; data[i]=mtf[mtfno]; goto rotate; } 
00300       cx+=CTXIDS;
00301       if (zp.decoder(cx[0]))
00302         { mtfno=2+decode_binary(zp,cx+1,1); data[i]=mtf[mtfno]; goto rotate; } 
00303       cx+=1+1;
00304       if (zp.decoder(cx[0]))
00305         { mtfno=4+decode_binary(zp,cx+1,2); data[i]=mtf[mtfno]; goto rotate; } 
00306       cx+=1+3;
00307       if (zp.decoder(cx[0]))
00308         { mtfno=8+decode_binary(zp,cx+1,3); data[i]=mtf[mtfno]; goto rotate; } 
00309       cx+=1+7;
00310       if (zp.decoder(cx[0]))
00311         { mtfno=16+decode_binary(zp,cx+1,4); data[i]=mtf[mtfno]; goto rotate; } 
00312       cx+=1+15;
00313       if (zp.decoder(cx[0]))
00314         { mtfno=32+decode_binary(zp,cx+1,5); data[i]=mtf[mtfno]; goto rotate; } 
00315       cx+=1+31;
00316       if (zp.decoder(cx[0]))
00317         { mtfno=64+decode_binary(zp,cx+1,6); data[i]=mtf[mtfno]; goto rotate; } 
00318       cx+=1+63;
00319       if (zp.decoder(cx[0]))
00320         { mtfno=128+decode_binary(zp,cx+1,7); data[i]=mtf[mtfno]; goto rotate; } 
00321       mtfno=256;
00322       data[i]=0;
00323       markerpos=i;
00324       continue;
00325       // Rotate mtf according to empirical frequencies (new!)
00326     rotate:
00327       // Adjust frequencies for overflow
00328       int k;
00329       fadd = fadd + (fadd>>fshift);
00330       if (fadd > 0x10000000) 
00331         {
00332           fadd    >>= 24;
00333           freq[0] >>= 24;
00334           freq[1] >>= 24;
00335           freq[2] >>= 24;
00336           freq[3] >>= 24;
00337           for (k=4; k<FREQMAX; k++)
00338             freq[k] = freq[k]>>24;
00339         }
00340       // Relocate new char according to new freq
00341       unsigned int fc = fadd;
00342       if (mtfno < FREQMAX)
00343         fc += freq[mtfno];
00344       for (k=mtfno; k>=FREQMAX; k--) 
00345         mtf[k] = mtf[k-1];
00346       for (; k>0 && fc>=freq[k-1]; k--)
00347         {
00348           mtf[k] = mtf[k-1];
00349           freq[k] = freq[k-1];
00350         }
00351       mtf[k] = data[i];
00352       freq[k] = fc;
00353     }
00354   
00355 
00358   
00359   if (markerpos<1 || markerpos>=size)
00360     G_THROW( ERR_MSG("ByteStream.corrupt") );
00361   // Allocate pointers
00362   unsigned int *posn;
00363   GPBuffer<unsigned int> gposn(posn,blocksize);
00364   memset(posn, 0, sizeof(unsigned int)*size);
00365   // Prepare count buffer
00366   int count[256];
00367   for (i=0; i<256; i++)
00368     count[i] = 0;
00369   // Fill count buffer
00370   for (i=0; i<markerpos; i++) 
00371     {
00372       unsigned char c = data[i];
00373       posn[i] = (c<<24) | (count[c] & 0xffffff);
00374       count[c] += 1;
00375     }
00376   for (i=markerpos+1; i<size; i++)
00377     {
00378       unsigned char c = data[i];
00379       posn[i] = (c<<24) | (count[c] & 0xffffff);
00380       count[c] += 1;
00381     }
00382   // Compute sorted char positions
00383   int last = 1;
00384   for (i=0; i<256; i++)
00385     {
00386       int tmp = count[i];
00387       count[i] = last;
00388       last += tmp;
00389     }
00390   // Undo the sort transform
00391   i = 0;
00392   last = size-1;
00393   while (last>0)
00394     {
00395       unsigned int n = posn[i];
00396       unsigned char c = (posn[i]>>24);
00397       data[--last] = c;
00398       i = count[c] + (n & 0xffffff);
00399     }
00400   // Free and check
00401   if (i != markerpos)
00402     G_THROW( ERR_MSG("ByteStream.corrupt") );
00403   return size;
00404 }
00405 
00406 
00407 
00408 // ========================================
00409 // -- ByteStream interface
00410 
00411 
00412 
00413 long 
00414 BSByteStream::tell() const
00415 {
00416   return offset;
00417 }
00418 
00419 size_t 
00420 BSByteStream::Decode::read(void *buffer, size_t sz)
00421 {
00422   if (eof)
00423     return 0;
00424   // Loop
00425   int copied = 0;
00426   while (sz>0 && !eof)
00427     {
00428       // Decode if needed
00429       if (!size)
00430         {
00431           bptr = 0;
00432           if (! decode()) 
00433           {
00434             size = 1 ;
00435             eof = true;
00436           }
00437           size -= 1;
00438         }
00439       // Compute remaining
00440       int bytes = size;
00441       if (bytes > (int)sz)
00442         bytes = sz;
00443       // Transfer
00444       if (buffer && bytes)
00445         {
00446           memcpy(buffer, data+bptr, bytes);
00447           buffer = (void*)((char*)buffer + bytes);
00448         }
00449       size -= bytes;
00450       bptr += bytes;
00451       sz -= bytes;
00452       copied += bytes;
00453       offset += bytes;
00454     }
00455   // Return copied bytes
00456   return copied;
00457 }
00458 
00459 
00460 #ifdef HAVE_NAMESPACES
00461 }
00462 # ifndef NOT_USING_DJVU_NAMESPACE
00463 using namespace DJVU;
00464 # endif
00465 #endif

kviewshell

Skip menu "kviewshell"
  • Main Page
  • Namespace List
  • Class Hierarchy
  • Alphabetical List
  • Class List
  • File List
  • Namespace Members
  • Class Members

API Reference

Skip menu "API Reference"
  • kviewshell
Generated for API Reference by doxygen 1.5.9
This website is maintained by Adriaan de Groot and Allen Winter.
KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal