"Fossies" - the Fresh Open Source Software Archive

Member "grzip-0.3.0/LZP.c" (4 Jan 2007, 5139 Bytes) of package /linux/privat/old/grzip-0.3.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "LZP.c" see the Fossies "Dox" file reference documentation.

    1 /*-------------------------------------------------*/
    2 /* GRZipII/libGRZip compressor               LZP.c */
    3 /* LZP Preprocessing Functions                     */
    4 /*-------------------------------------------------*/
    5 
    6 /*--
    7   This file is a part of GRZipII and/or libGRZip, a program
    8   and library for lossless, block-sorting data compression.
    9 
   10   Copyright (C) 2002-2004 Grebnov Ilya. All rights reserved.
   11 
   12   This library is free software; you can redistribute it and/or
   13   modify it under the terms of the GNU Lesser General Public
   14   License as published by the Free Software Foundation; either
   15   version 2.1 of the License, or (at your option) any later version.
   16 
   17   This library is distributed in the hope that it will be useful,
   18   but WITHOUT ANY WARRANTY; without even the implied warranty of
   19   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
   20   Lesser General Public License for more details.
   21 
   22   Grebnov Ilya, Ivanovo, Russian Federation.
   23   grib@crazy.ru
   24 
   25   This program is based on (at least) the work of:
   26   Juergen Abel, Jon L. Bentley, Edgar Binder,
   27   Charles Bloom, Mike Burrows, Andrey Cadach,
   28   Damien Debin, Sebastian Deorowicz, Peter Fenwick,
   29   Michael Schindler, Robert Sedgewick, Julian Seward,
   30   David Wheeler, Vadim Yoockin.
   31 
   32   LZP memory use         : 2*BlockLen + [16-1024] Kb
   33   Reverse LZP memory use : 2*BlockLen + [16-1024] Kb
   34 
   35   For more information on these sources, see the manual.
   36 --*/
   37 
   38 #include <stdio.h>
   39 #include "libGRZip.h"
   40 
   41 #define LZP_MatchFlag    0xF2
   42 #define LZP_RunFlag      0xF3
   43 #define LZP_XorFlag      (uint8)(0xFF^LZP_RunFlag)
   44 
   45 #define LZP_AllocHashTable()                                          \
   46   uint8 ** Contexts=(uint8 **)malloc((LZP_HT_Size+1)*sizeof(uint8 *));\
   47   if (Contexts==NULL) return (GRZ_NOT_ENOUGH_MEMORY);                 \
   48   memset(Contexts,0,(LZP_HT_Size+1)*sizeof(uint8 *));
   49 
   50 #define LZP_FreeHashTable() free(Contexts);
   51 
   52 sint32 GRZip_LZP_Encode(uint8 * Input,uint32 Size,uint8 * Output,uint8 Mode)
   53 {
   54   uint32 LZP_HT_Size=(1<<(3+(Mode&0xF)))-1;
   55   uint32 LZP_MinMatchLen=2+3*(Mode>>4);
   56 
   57   LZP_AllocHashTable();
   58 
   59   uint8  * InputEnd=Input+Size;
   60   uint8  * OutputEnd=Output+Size-1;
   61 
   62   *((uint32 *)Output)=*((uint32 *)Input);
   63 
   64   uint32 Ctx=(Input[3]+(Input[2]<<8)+(Input[1]<<16)+(Input[0]<<24));
   65 
   66   Input+=4;
   67   Output+=4;
   68 
   69   while ((Input<InputEnd)&&(Output<OutputEnd))
   70   {
   71     uint32  HashIndex=((Ctx>>15)^Ctx^(Ctx>>3))&LZP_HT_Size;
   72     uint8 * Pointer=Contexts[HashIndex];
   73     Contexts[HashIndex]=Input;
   74 
   75     if (Pointer)
   76      {
   77        uint32  CommonLength=0;
   78        uint8 * Ptr=Input;
   79        while (Ptr<InputEnd)
   80        {
   81          if (*Ptr++!=*Pointer++) break;
   82          CommonLength++;
   83        }
   84        if (CommonLength<LZP_MinMatchLen) CommonLength=0;
   85        if (CommonLength)
   86         {
   87           Input+=CommonLength;
   88           Ctx=(Input[-1]+(Input[-2]<<8)+(Input[-3]<<16)+(Input[-4]<<24));
   89           CommonLength=CommonLength-LZP_MinMatchLen+1;
   90           (*Output++)=LZP_MatchFlag;
   91           while (CommonLength>254)
   92           {
   93             (*Output++)=LZP_RunFlag;
   94             if (Output>=OutputEnd)
   95              {
   96                LZP_FreeHashTable();
   97                return (GRZ_NOT_COMPRESSIBLE);
   98              }
   99             CommonLength-=255;
  100           }
  101           (*Output++)=((uint8)(CommonLength^LZP_XorFlag));
  102         }
  103        else
  104         {
  105           uint8 Ch=((*Output++)=(*Input++));
  106           Ctx=(Ctx<<8)|Ch;
  107           if (Ch==LZP_MatchFlag) *Output++=LZP_XorFlag;
  108         }
  109      }
  110     else
  111       Ctx=(Ctx<<8)|((*Output++)=(*Input++));
  112   }
  113   LZP_FreeHashTable();
  114   if (Output>=OutputEnd) return (GRZ_NOT_COMPRESSIBLE);
  115   return (Output+Size-OutputEnd-1);
  116 }
  117 
  118 sint32 GRZip_LZP_Decode(uint8 * Input,uint32 Size,uint8 * Output,uint8 Mode)
  119 {
  120   uint32 LZP_HT_Size=(1<<(3+(Mode&0xF)))-1;
  121   uint32 LZP_MinMatchLen=2+3*(Mode>>4);
  122 
  123   LZP_AllocHashTable();
  124   uint8  * InputEnd=Input+Size;
  125   uint8  * OutputBeg=Output;
  126 
  127   *((uint32 *)Output)=*((uint32 *)Input);
  128   uint32 Ctx=(Input[3]+(Input[2]<<8)+(Input[1]<<16)+(Input[0]<<24));
  129 
  130   Input+=4;
  131   Output+=4;
  132 
  133   while (Input<InputEnd)
  134   {
  135     uint32  HashIndex=((Ctx>>15)^Ctx^(Ctx>>3))&LZP_HT_Size;
  136     uint8 * Pointer=Contexts[HashIndex];
  137 
  138     Contexts[HashIndex]=Output;
  139 
  140     if (Pointer)
  141      {
  142        if ((*Input++)!=LZP_MatchFlag) Ctx=(Ctx<<8)|(*Output++=*(Input-1));
  143        else
  144        {
  145          uint32 CommonLength=0;
  146          while (CommonLength+=((*Input)^LZP_XorFlag),(*Input++)==LZP_RunFlag);
  147          if (CommonLength)
  148           {
  149             CommonLength=CommonLength+LZP_MinMatchLen-1;
  150             while (CommonLength--) *Output++=*Pointer++;
  151             Ctx=(Output[-1]+(Output[-2]<<8)+(Output[-3]<<16)+(Output[-4]<<24));
  152           }
  153          else
  154           Ctx=(Ctx<<8)|(*Output++=LZP_MatchFlag);
  155        }
  156      }
  157     else
  158       Ctx=(Ctx<<8)|((*Output++)=(*Input++));
  159   }
  160   LZP_FreeHashTable();
  161   return (Output-OutputBeg);
  162 }
  163 
  164 #undef LZP_MatchFlag
  165 #undef LZP_RunFlag
  166 #undef LZP_XorFlag
  167 #undef LZP_InitHashTables
  168 #undef LZP_FreeHashTables
  169 
  170 /*-------------------------------------------------*/
  171 /* End                                       LZP.c */
  172 /*-------------------------------------------------*/