Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

RunLenCompress.cpp

Go to the documentation of this file.
00001 /*
00002 This product contains certain software code or other information
00003 ("AT&T Software") proprietary to AT&T Corp. ("AT&T").  The AT&T
00004 Software is provided to you "AS IS".  YOU ASSUME TOTAL RESPONSIBILITY
00005 AND RISK FOR USE OF THE AT&T SOFTWARE.  AT&T DOES NOT MAKE, AND
00006 EXPRESSLY DISCLAIMS, ANY EXPRESS OR IMPLIED WARRANTIES OF ANY KIND
00007 WHATSOEVER, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
00008 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE, WARRANTIES OF
00009 TITLE OR NON-INFRINGEMENT OF ANY INTELLECTUAL PROPERTY RIGHTS, ANY
00010 WARRANTIES ARISING BY USAGE OF TRADE, COURSE OF DEALING OR COURSE OF
00011 PERFORMANCE, OR ANY WARRANTY THAT THE AT&T SOFTWARE IS "ERROR FREE" OR
00012 WILL MEET YOUR REQUIREMENTS.
00013 
00014 Unless you accept a license to use the AT&T Software, you shall not
00015 reverse compile, disassemble or otherwise reverse engineer this
00016 product to ascertain the source code for any AT&T Software.
00017 
00018 (c) AT&T Corp. All rights reserved.  AT&T is a registered trademark of AT&T Corp.
00019 
00020 ***********************************************************************
00021 
00022 History:
00023 
00024       24/11/99  - initial release by Hartmut Liefke, liefke@seas.upenn.edu
00025                                      Dan Suciu,      suciu@research.att.com
00026 */
00027 
00028 //***************************************************************************
00029 //***************************************************************************
00030 
00031 // This module contains the run-length encoder 'rl'
00032 
00033 #include "CompressMan.hpp"
00034 
00035 #ifdef XDEMILL
00036 #include "UnCompCont.hpp"
00037 #endif
00038 
00039 //***************************************************************************
00040 //***************************************************************************
00041 
00042 extern MemStreamer blockmem;
00043 //MemStreamer *compressmem=&blockmem;
00044 
00045 #define RUNLENGTH_ITEM_MINSIZE 16
00046 
00047 // The run length item is used to store the current run-length item.
00048 // The run length item can be quite large - therefore, we store it
00049 // in a single-chained list. The list grows bigger, if longer items
00050 // need to be stored.
00051 
00052 struct CurRunLengthItem
00053    // The string is stored in the current item
00054 {
00055    CurRunLengthItem  *next;
00056    unsigned short    len;     // The current length of data within this item
00057    unsigned short    size;    // The size of the item
00058 
00059    char *GetStrPtr() {  return (char *)(this+1);   }
00060       // Returns the pointer to the data
00061 };
00062 
00063 struct CurRunLengthState
00064    // Represents the state of the run-length encoder
00065 {
00066    CurRunLengthItem  *items;        // The list of items
00067    unsigned short    totallen;      // The overall length of the string
00068    short             runlencount;   // If -1, if we just started
00069 
00070    void KeepNewString(unsigned char *str,unsigned short len)
00071       // Keeps the current string in the memory
00072       // If the previous memory is not enough, we need to allocate more
00073       // CurRunLengthItem
00074    {
00075       CurRunLengthItem  **itemref;
00076       unsigned          allocsize;
00077 
00078 #ifdef XMILL
00079       runlencount=0;
00080 #endif
00081 
00082       totallen=len;
00083 
00084       itemref=&items;
00085 
00086       // First, we copy the new string over the sequence of existing
00087       // CurRunLengthItem's
00088 
00089       while(*itemref!=NULL)
00090       {
00091          (*itemref)->len = ((*itemref)->size < len) ? (*itemref)->size : len;
00092             
00093          mymemcpy((*itemref)->GetStrPtr(),(char *)str,(*itemref)->len);
00094 
00095          str+=(*itemref)->len;
00096          len-=(*itemref)->len;
00097 
00098          itemref=&((*itemref)->next);
00099 
00100          if(len==0)  // Did we reach the end of new data?
00101                      // (I.e. the new run length item is shorter)
00102                      // We set the length of the remaining items to 0
00103          {
00104             while(*itemref!=NULL)
00105             {
00106                (*itemref)->len=0;
00107                itemref=&((*itemref)->next);
00108             }
00109             break;
00110          }
00111       }
00112 
00113       if(len>0)
00114          // If there is still data left in the new run length string,
00115          // we need to allocate new memory for the remaining bytes
00116       {
00117          if(len<RUNLENGTH_ITEM_MINSIZE)
00118             allocsize=RUNLENGTH_ITEM_MINSIZE;
00119          else
00120             allocsize=((len-1)|3)+1;
00121 
00122          *itemref=(CurRunLengthItem *)blockmem.GetByteBlock(sizeof(CurRunLengthItem)+allocsize);
00123 
00124          (*itemref)->size=allocsize;
00125          (*itemref)->len=len;
00126 
00127          mymemcpy((*itemref)->GetStrPtr(),(char *)str,len);
00128 
00129          (*itemref)->next=NULL;
00130       }
00131    }
00132 };
00133 
00134 #ifdef XMILL
00135 
00136 class RunLengthCompressor : public UserCompressor
00137 {
00138 public:
00139    RunLengthCompressor()
00140    {
00141       datasize=sizeof(CurRunLengthState);
00142       contnum=1;  // We need one container for ourselves
00143       isrejecting=0;
00144       canoverlap=0;
00145       isfixedlen=0;
00146    }
00147 
00148 // Compression functions
00149 
00150    void InitCompress(CompressContainer *cont,char *dataptr)
00151    {
00152       ((CurRunLengthState *)dataptr)->items=NULL;
00153       ((CurRunLengthState *)dataptr)->runlencount=-1;
00154    }
00155 
00156    // Note that we don't have function 'ParseString', since it compressor
00157    // is always accepting
00158 
00159    void CompressString(char *str,unsigned len,CompressContainer *cont,char *dataptr)
00160    {
00161       CurRunLengthState *state=(CurRunLengthState *)dataptr;
00162 
00163       if(state->runlencount!=-1) // Do we already have an run-length item
00164                                  // that is currently active ?
00165       {
00166          CurRunLengthItem  *item=state->items;
00167          char              *curptr=str;
00168          unsigned          curlen=len;
00169 
00170          // Let's check whether new item is the same as the old one.
00171          while(item!=NULL)
00172          {
00173             if((item->len>curlen)||
00174                (memcmp(item->GetStrPtr(),curptr,item->len)!=0))
00175                break;
00176 
00177             curptr+=item->len;
00178             curlen-=item->len;
00179 
00180             item=item->next;
00181 
00182             if((curlen==0)&&(item==NULL))
00183                // The current item matches the new string ==> We simply increase the count
00184             {
00185                state->runlencount++;
00186                return;
00187             }
00188          }
00189          // The items don't match
00190          // ==> We must store the count and the current string
00191 
00192          cont->StoreUInt32(state->totallen);
00193 
00194          item=state->items;
00195 
00196          while(item!=NULL)
00197          {
00198             cont->StoreData(item->GetStrPtr(),item->len);
00199             item=item->next;
00200          }
00201          cont->StoreUInt32(state->runlencount);
00202       }
00203       else
00204          dataptr=NULL;
00205 
00206       // We keep the new string in memory
00207 
00208       state->KeepNewString((unsigned char *)str,len);
00209    }
00210 
00211    void FinishCompress(CompressContainer *cont,char *dataptr)
00212       // The compression is finalized by storing the current
00213       // run length and the value.
00214    {
00215       CurRunLengthState *state=(CurRunLengthState *)dataptr;
00216 
00217       if(state->runlencount!=-1)
00218          // Do we have a piece of data in memory ?
00219       {
00220          CurRunLengthItem *item;
00221 
00222          // We store the run-length count and the actual string
00223          cont->StoreUInt32(state->totallen);
00224 
00225          item=state->items;
00226 
00227          while(item!=NULL)
00228          {
00229             cont->StoreData(item->GetStrPtr(),item->len);
00230             item=item->next;
00231          }
00232          cont->StoreUInt32(state->runlencount);
00233       }
00234    }
00235 };
00236 
00237 #endif
00238 
00239 //****************************************************************************************
00240 
00241 // The decompressor for run length encoder
00242 
00243 #ifdef XDEMILL
00244 
00245 class RunLengthUncompressor : public UserUncompressor
00246 {
00247 public:
00248    RunLengthUncompressor()
00249    {
00250       datasize=sizeof(CurRunLengthState);
00251       contnum=1;  // We need one container for ourselves
00252    }
00253 
00254 // Compression functions
00255 
00256    void InitUncompress(UncompressContainer *cont,char *dataptr)
00257       // The initialization for the state
00258    {
00259       ((CurRunLengthState *)dataptr)->items=NULL;
00260       ((CurRunLengthState *)dataptr)->runlencount=-1;
00261    }
00262 
00263    void UncompressItem(UncompressContainer *cont,char *dataptr,XMLOutput *output)
00264    {
00265       CurRunLengthState *state=(CurRunLengthState *)dataptr;
00266 
00267       if(state->runlencount==-1) // Do we already have an run-length item
00268                                  // that is currently active ?
00269       {
00270          // We load the next item from the container
00271          // and the runlength number
00272 
00273          int len=cont->LoadUInt32();
00274          unsigned char *ptr=cont->GetDataPtr(len);
00275 
00276          output->characters((char *)ptr,len);
00277 
00278          state->runlencount=((short)cont->LoadUInt32())-1;
00279 
00280          state->KeepNewString(ptr,len);
00281       }
00282       else
00283       {
00284          // If we have a runlength count >-1, then we simply output
00285          // the current object and decrease the count
00286          CurRunLengthItem  *item=state->items;
00287 
00288          while(item!=NULL)
00289          {
00290             output->characters(item->GetStrPtr(),item->len);
00291             item=item->next;
00292          }
00293          state->runlencount--;
00294       }
00295    }
00296 };
00297 
00298 #endif
00299 
00300 //****************************************************************************************
00301 
00302 // The compressor factory
00303 
00304 class RunLengthCompressorFactory : public UserCompressorFactory
00305 {
00306 #ifdef XDEMILL
00307    RunLengthUncompressor uncompressor;
00308 #endif
00309 
00310 public:
00311    char *GetName()         {  return "rl"; }
00312    char *GetDescription()  {  return "Run-length encoder for arbitrary text strings"; }
00313 
00314 #ifdef XMILL
00315    UserCompressor *InstantiateCompressor(char *paramstr,int len)
00316    {
00317       if(paramstr!=NULL)
00318       {
00319          Error("Run length compressor 'rl' should not have any arguments ('");
00320          ErrorCont(paramstr,len);
00321          Error("')");
00322          Exit();
00323       }
00324       return new RunLengthCompressor();
00325    }
00326 #endif
00327 
00328 #ifdef XDEMILL
00329    UserUncompressor *InstantiateUncompressor(char *paramstr,int len)
00330    {
00331       return &uncompressor;
00332    }
00333 #endif
00334 };
00335 
00336 RunLengthCompressorFactory  runlengthcompressor;

Generated on Sat Oct 13 16:08:40 2001 for XMILL by doxygen1.2.11.1 written by Dimitri van Heesch, © 1997-2001