"Fossies" - the Fresh Open Source Software Archive

Member "grzip-0.3.0/libgrzip.c" (4 Jan 2007, 11672 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 "libgrzip.c" see the Fossies "Dox" file reference documentation.

    1 /*-------------------------------------------------*/
    2 /* GRZipII/libGRZip compressor          libGRZip.c */
    3 /* libGRZip Compression(Decompression) 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   Ilya.Grebnov@magicssoft.ru, http://magicssoft.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   George Plechanov, Michael Schindler, Robert Sedgewick,
   30   Julian Seward, David Wheeler, Vadim Yoockin.
   31 
   32   Normal compression mode:
   33     Compression     memory use : [7-9]*BlockLen  + 1Mb
   34     Decompression   memory use : 5*BlockLen      + 1Mb
   35   Fast compression mode:
   36     Compression     memory use : 5*BlockLen      + 1Mb
   37     Decompression   memory use : 5.125*BlockLen  + 1Mb
   38 
   39   For more information on these sources, see the manual.
   40 --*/
   41 
   42 #include <math.h>
   43 #include <stdlib.h>
   44 #include <stdio.h>
   45 #include <string.h>
   46 #include <time.h>
   47 
   48 #include "libGRZip.h"
   49 #include "CRC32.c"
   50 #include "BWT.c"
   51 #include "LZP.c"
   52 #include "ST4.c"
   53 #include "MTF_Ari.c"
   54 #include "WFC_Ari.c"
   55 #include "Rec_Flt.c"
   56 
   57 sint32 GRZip_StoreBlock(uint8 * Input ,sint32 Size,
   58                         uint8 * Output,sint32 Mode)
   59 {
   60   *(sint32 *)(Output+4)=-1;
   61   *(sint32 *)(Output+8)=Mode&0xFF;
   62   *(sint32 *)(Output+12)=0;
   63   *(sint32 *)(Output+16)=Size;
   64   memcpy(Output+28,Input,Size);
   65   *(sint32 *)(Output+20)=GRZip_GetCRC32(Output+28,Size);
   66   *(sint32 *)(Output+24)=GRZip_GetCRC32(Output,24);
   67   return (Size+28);
   68 }
   69 
   70 sint32 GRZip_CompressBlock(uint8 * Input ,sint32 Size,
   71                            uint8 * Output,sint32 Mode)
   72 {
   73   sint32 SSize=Size;
   74 
   75   *(sint32 *)Output=Size;
   76 
   77   if ((Size<32)||(Size>GRZ_MaxBlockSize))
   78     return(GRZip_StoreBlock(Input,Size,Output,0));
   79 
   80   if (Size<1024) Mode|=GRZ_Compression_ST4;
   81 
   82   if ((Size>1024)&&((Mode&GRZ_Disable_DeltaFlt)==0))
   83   {
   84     sint32 RecMode=GRZip_Rec_Test((uint8 *)Input,Size);
   85     if (RecMode)
   86     {
   87       sint32 NewSize=0;
   88       uint8 * Buffer=(uint8 *)malloc(Size+1024);
   89       if (Buffer==NULL) return(GRZip_StoreBlock(Input,Size,Output,0));
   90       GRZip_Rec_Encode(Input,Size,Buffer,RecMode); Mode+=GRZ_Disable_DeltaFlt;
   91       if ((RecMode&1)==1)
   92       {
   93         sint32 PartSize=(Size>>1);
   94         sint32 Result=GRZip_CompressBlock(Buffer,PartSize,Output+28,Mode);
   95         if (Result<0) {free(Buffer);return(GRZip_StoreBlock(Input,Size,Output,0));}
   96         NewSize=Result;
   97         Result=GRZip_CompressBlock(Buffer+PartSize,Size-PartSize,Output+28+NewSize,Mode);
   98         if (Result<0) {free(Buffer);return(GRZip_StoreBlock(Input,Size,Output,0));}
   99         NewSize+=Result;
  100       }
  101       if ((RecMode&1)==0)
  102       {
  103         sint32 PartSize=(Size>>2);
  104         sint32 Result=GRZip_CompressBlock(Buffer,PartSize,Output+28,Mode);
  105         if (Result<0) {free(Buffer);return(GRZip_StoreBlock(Input,Size,Output,0));}
  106         NewSize=Result;
  107         Result=GRZip_CompressBlock(Buffer+PartSize,PartSize,Output+28+NewSize,Mode);
  108         if (Result<0) {free(Buffer);return(GRZip_StoreBlock(Input,Size,Output,0));}
  109         NewSize+=Result;
  110         Result=GRZip_CompressBlock(Buffer+2*PartSize,PartSize,Output+28+NewSize,Mode);
  111         if (Result<0) {free(Buffer);return(GRZip_StoreBlock(Input,Size,Output,0));}
  112         NewSize+=Result;
  113         Result=GRZip_CompressBlock(Buffer+3*PartSize,Size-3*PartSize,Output+28+NewSize,Mode);
  114         if (Result<0) {free(Buffer);return(GRZip_StoreBlock(Input,Size,Output,0));}
  115         NewSize+=Result;
  116       }
  117       free(Buffer);
  118 
  119       if (NewSize>=Size) return(GRZip_StoreBlock(Input,Size,Output,0));
  120 
  121       *(sint32 *)(Output+4)=-2;
  122       *(sint32 *)(Output+8)=RecMode;
  123       *(sint32 *)(Output+16)=NewSize;
  124       *(sint32 *)(Output+20)=GRZip_GetCRC32(Output+28,NewSize);
  125       *(sint32 *)(Output+24)=GRZip_GetCRC32(Output,24);
  126 
  127       return (NewSize+28);
  128     }
  129   }
  130 
  131   uint8 * LZPBuffer=(uint8 *)malloc(Size+1024);
  132   if (LZPBuffer==NULL) return(GRZip_StoreBlock(Input,Size,Output,0));
  133 
  134   if (Mode&0x0F)
  135   {
  136     sint32 Result=GRZip_LZP_Encode(Input,Size,LZPBuffer,Mode&0xFF);
  137     if (Result==GRZ_NOT_ENOUGH_MEMORY)
  138     {
  139       free(LZPBuffer);
  140       return(GRZip_StoreBlock(Input,Size,Output,0));
  141     };
  142     if (Result==GRZ_NOT_COMPRESSIBLE)
  143     {
  144       Mode=Mode&0xFFFFFF00;
  145       memcpy(LZPBuffer,Input,Size);
  146       *(sint32 *)(Output+8)=Size;
  147     }
  148     else
  149      { *(sint32 *)(Output+8)=Result,Size=Result;}
  150   }
  151   else
  152   {
  153     memcpy(LZPBuffer,Input,Size);
  154     *(sint32 *)(Output+8)=Size;
  155   }
  156   sint32 Result;
  157 
  158   for (Result=0;Result<8;Result++) LZPBuffer[Result+Size]=0;
  159   Size=(Size+7)&(~7);
  160 
  161   if (Mode&GRZ_Compression_ST4)
  162     Result=GRZip_ST4_Encode(LZPBuffer,Size,LZPBuffer);
  163   else
  164     Result=GRZip_BWT_Encode(LZPBuffer,Size,LZPBuffer,Mode&GRZ_BWTSorting_Fast);
  165 
  166   if (Result==GRZ_NOT_ENOUGH_MEMORY)
  167   {
  168     if (Mode&0x0F)
  169     {
  170       sint32 Result=GRZip_LZP_Encode(Input,SSize,LZPBuffer,Mode&0xFF);
  171       if (Result==GRZ_NOT_ENOUGH_MEMORY)
  172       {
  173         free(LZPBuffer);
  174         return(GRZip_StoreBlock(Input,SSize,Output,0));
  175       };
  176       Result=GRZip_StoreBlock(LZPBuffer,Result,Output,Mode);
  177       free(LZPBuffer);
  178       return (Result);
  179     }
  180     free(LZPBuffer);
  181     return(GRZip_StoreBlock(Input,SSize,Output,0));
  182   };
  183 
  184   *(sint32 *)(Output+12)=Result;
  185 
  186   if (Mode&GRZ_Compression_MTF)
  187     Result=GRZip_MTF_Ari_Encode(LZPBuffer,Size,Output+28);
  188   else
  189     Result=GRZip_WFC_Ari_Encode(LZPBuffer,Size,Output+28);
  190 
  191   if ((Result==GRZ_NOT_ENOUGH_MEMORY)||(Result==GRZ_NOT_COMPRESSIBLE))
  192   {
  193     if (Mode&0x0F)
  194     {
  195       sint32 Result=GRZip_LZP_Encode(Input,SSize,LZPBuffer,Mode&0xFF);
  196       if (Result==GRZ_NOT_ENOUGH_MEMORY)
  197       {
  198         free(LZPBuffer);
  199         return(GRZip_StoreBlock(Input,SSize,Output,0));
  200       };
  201       Result=GRZip_StoreBlock(LZPBuffer,Result,Output,Mode);
  202       free(LZPBuffer);
  203       return (Result);
  204     }
  205     free(LZPBuffer);
  206     return(GRZip_StoreBlock(Input,SSize,Output,0));
  207   };
  208 
  209   *(sint32 *)(Output+4)=Mode;
  210   *(sint32 *)(Output+16)=Result;
  211   *(sint32 *)(Output+20)=GRZip_GetCRC32(Output+28,Result);
  212   *(sint32 *)(Output+24)=GRZip_GetCRC32(Output,24);
  213 
  214   free(LZPBuffer);
  215   return (Result+28);
  216 }
  217 
  218 sint32 GRZip_CheckBlockSign(uint8 * Input,sint32 Size)
  219 {
  220   if (Size<28) return (GRZ_UNEXPECTED_EOF);
  221   if ((*(sint32 *)(Input+24))!=GRZip_GetCRC32(Input,24))
  222     return (GRZ_CRC_ERROR);
  223   return (GRZ_NO_ERROR);
  224 }
  225 
  226 sint32 GRZip_DecompressBlock(uint8 * Input,sint32 Size,uint8 * Output)
  227 {
  228   if (Size<28) return (GRZ_UNEXPECTED_EOF);
  229   if ((*(sint32 *)(Input+24))!=GRZip_GetCRC32(Input,24))
  230     return (GRZ_CRC_ERROR);
  231   if ((*(sint32 *)(Input+16))+28>Size) return (GRZ_UNEXPECTED_EOF);
  232   if ((*(sint32 *)(Input+20))!=GRZip_GetCRC32(Input+28,*(sint32 *)(Input+16)))
  233     return (GRZ_CRC_ERROR);
  234   sint32 Mode=*(sint32 *)(Input+4);
  235   sint32 Result=*(sint32 *)(Input+16);
  236   if (Mode==-1)
  237   {
  238     Mode=*(sint32 *)(Input+8);
  239     if (Mode==0)
  240     {
  241       memcpy(Output,Input+28,Result);
  242       return (Result);
  243     }
  244     Result=GRZip_LZP_Decode(Input+28,Result,Output,Mode&0xFF);
  245     return (Result);
  246   }
  247 
  248   if (Mode==-2)
  249   {
  250     sint32 RecMode=*(sint32 *)(Input+8);
  251               Size=*(sint32 *)(Input);
  252 
  253     uint8 * Buffer=(uint8 *)malloc(Size+1024);
  254     if (Buffer==NULL) return(GRZ_NOT_ENOUGH_MEMORY);
  255 
  256     uint8 * Tmp=(Input+28);
  257     sint32  OutputPos=0;
  258 
  259     if ((RecMode&1)==1)
  260     {
  261       Result=GRZip_DecompressBlock(Tmp,(*(sint32 *)(Tmp+16))+28,Buffer+OutputPos);
  262       if (Result<0) {free(Buffer);return Result;};
  263       OutputPos+=Result;
  264       Tmp=Tmp+(*(sint32 *)(Tmp+16))+28;
  265       Result=GRZip_DecompressBlock(Tmp,(*(sint32 *)(Tmp+16))+28,Buffer+OutputPos);
  266       if (Result<0) {free(Buffer);return Result;};
  267     }
  268     if ((RecMode&1)==0)
  269     {
  270       Result=GRZip_DecompressBlock(Tmp,(*(sint32 *)(Tmp+16))+28,Buffer+OutputPos);
  271       if (Result<0) {free(Buffer);return Result;};
  272       OutputPos+=Result;
  273       Tmp=Tmp+(*(sint32 *)(Tmp+16))+28;
  274       Result=GRZip_DecompressBlock(Tmp,(*(sint32 *)(Tmp+16))+28,Buffer+OutputPos);
  275       if (Result<0) {free(Buffer);return Result;};
  276       OutputPos+=Result;
  277       Tmp=Tmp+(*(sint32 *)(Tmp+16))+28;
  278       Result=GRZip_DecompressBlock(Tmp,(*(sint32 *)(Tmp+16))+28,Buffer+OutputPos);
  279       if (Result<0) {free(Buffer);return Result;};
  280       OutputPos+=Result;
  281       Tmp=Tmp+(*(sint32 *)(Tmp+16))+28;
  282       Result=GRZip_DecompressBlock(Tmp,(*(sint32 *)(Tmp+16))+28,Buffer+OutputPos);
  283       if (Result<0) {free(Buffer);return Result;};
  284     }
  285     GRZip_Rec_Decode(Buffer,Size,Output,RecMode);
  286     free(Buffer);
  287     return (Size);
  288   }
  289 
  290   uint8 * LZPBuffer=(uint8 *)malloc(*(sint32 *)(Input+8)+1024);
  291   if (LZPBuffer==NULL) return(GRZ_NOT_ENOUGH_MEMORY);
  292 
  293   sint32 TSize;
  294 
  295   if (Mode&GRZ_Compression_MTF)
  296     TSize=GRZip_MTF_Ari_Decode(Input+28,LZPBuffer);
  297   else
  298     TSize=GRZip_WFC_Ari_Decode(Input+28,(*(sint32 *)(Input+8)),LZPBuffer);
  299 
  300   if (Result==GRZ_NOT_ENOUGH_MEMORY)
  301   {
  302     free(LZPBuffer);
  303     return(GRZ_NOT_ENOUGH_MEMORY);
  304   };
  305 
  306   Result=*(sint32 *)(Input+12);
  307 
  308   if (Mode&GRZ_Compression_ST4)
  309     Result=GRZip_ST4_Decode(LZPBuffer,TSize,Result);
  310   else
  311     Result=GRZip_BWT_Decode(LZPBuffer,TSize,Result);
  312 
  313   if (Result==GRZ_NOT_ENOUGH_MEMORY)
  314   {
  315     free(LZPBuffer);
  316     return(GRZ_NOT_ENOUGH_MEMORY);
  317   };
  318 
  319   TSize=*(sint32 *)(Input+8);
  320 
  321   if (Mode&0x0F)
  322   {
  323     sint32 Result=GRZip_LZP_Decode(LZPBuffer,TSize,Output,Mode&0xFF);
  324     if (Result==GRZ_NOT_ENOUGH_MEMORY)
  325     {
  326       free(LZPBuffer);
  327       return(GRZ_NOT_ENOUGH_MEMORY);
  328     };
  329   }
  330   else
  331     memcpy(Output,LZPBuffer,TSize);
  332 
  333   free(LZPBuffer);
  334   return (*(sint32 *)Input);
  335 }
  336 
  337 #define ABS_MaxByte      256
  338 #define ABS_MinBlockSize 24*1024
  339 
  340 sint32 GRZip_GetAdaptativeBlockSize(uint8 * Input,sint32 Size)
  341 {
  342   sint32  TotFreq[ABS_MaxByte];
  343   sint32     Freq[ABS_MaxByte];
  344 
  345   if (Size<=ABS_MinBlockSize) return Size;
  346 
  347   memset(TotFreq,0,ABS_MaxByte*sizeof(sint32));
  348 
  349   uint8 * SInput=Input;
  350   uint8 * InputEnd=Input+ABS_MinBlockSize;
  351   while  (Input<InputEnd) TotFreq[*Input++]++;
  352 
  353   sint32 Pos=ABS_MinBlockSize,BlockSize=ABS_MinBlockSize/2;
  354 
  355   while (Pos+BlockSize<Size)
  356   {
  357     memset(Freq,0,ABS_MaxByte*sizeof(sint32));
  358 
  359     sint32 i=0,Sum=BlockSize+(Pos>>1);
  360 
  361     uint8 * Ptr=SInput+Pos;
  362     uint8 * PtrEnd=Ptr+BlockSize;
  363     while (Ptr<PtrEnd) Freq[*Ptr++]++;
  364 
  365     double AvgSize=0,RealSize=0;
  366     for (i=0;i<ABS_MaxByte;i++)
  367       if (Freq[i])
  368       {
  369         sint32 Fr=Freq[i];
  370         RealSize-=Fr*log10((double)Fr/BlockSize);
  371          AvgSize-=Fr*log10((double)(Fr+(TotFreq[i]>>1))/Sum);
  372       }
  373 
  374     if (AvgSize>1.25*RealSize)
  375     {
  376        if (BlockSize<256)
  377          return Pos;
  378        else
  379          {BlockSize>>=1;continue;}
  380     }
  381 
  382     for (i=0;i<ABS_MaxByte;i++) TotFreq[i]+=Freq[i];
  383     Pos+=BlockSize;
  384   }
  385   return Size;
  386 }
  387 
  388 #undef ABS_MaxByte
  389 #undef ABS_MinBlockSize
  390 
  391 /*-------------------------------------------------*/
  392 /* End                                  libgrzip.c */
  393 /*-------------------------------------------------*/