"Fossies" - the Fresh Open Source Software Archive

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

    1 /*-------------------------------------------------*/
    2 /* GRZipII/libGRZip compressor               ST4.c */
    3 /* ST Order-4 Sorting 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   ST memory use         : 5*BlockLen     + 256Kb
   33   Reverse ST memory use : 5.125*BlockLen + 256Kb
   34 
   35   For more information on these sources, see the manual.
   36 --*/
   37 
   38 #include <stdio.h>
   39 #include "libGRZip.h"
   40 
   41 #define ST_MaxByte           256
   42 #define ST_MaxWord           65536
   43 #define ST_INDIRECT          0x800000
   44 
   45 sint32 GRZip_ST4_Encode(uint8 * Input, sint32 Size, uint8 * Output)
   46 {
   47   sint32    FBP,i;
   48   uint32    W;
   49 
   50   sint32 *  Counter=(sint32 *)malloc(ST_MaxWord*sizeof(sint32));
   51   if (Counter==NULL) return (GRZ_NOT_ENOUGH_MEMORY);
   52 
   53   uint32 *  Context=(uint32 *)malloc(Size*sizeof(uint32));
   54   if (Context==NULL) {free(Counter);return (GRZ_NOT_ENOUGH_MEMORY);}
   55 
   56   memset    (Counter,0,ST_MaxWord*sizeof(sint32));
   57 
   58   W=Input[Size-1]<<8; for (i=0;i<Size;i++) Counter[(W=(W>>8)|(Input[i]<<8))]++;
   59 
   60   for (W=0,i=0;i<ST_MaxWord;i++) W+=Counter[i],Counter[i]=W-Counter[i];
   61 
   62   W=(Input[Size-4]<<8)|Input[Size-5];
   63   if (W==0xFFFF) FBP=Size-1; else FBP=Counter[W+1]-1;
   64 
   65   W=(Input[Size-1]<<24)|(Input[Size-2]<<16)|(Input[Size-3]<<8)|(Input[Size-4]);
   66 
   67   for (i=0;i<Size;i++)
   68   {
   69     uint8 c=Input[i];
   70     Context[Counter[W&0x0000FFFF]++]=(W&0xFFFF0000)|c;
   71     W=(W>>8)|(c<<24);
   72   }
   73 
   74   for (i=Size-1;i>=FBP;i--) Output[--Counter[Context[i]>>16]]=Context[i]&0xFF;
   75   FBP=Counter[Context[FBP]>>16];
   76   for (;i>=0;i--) Output[--Counter[Context[i]>>16]]=Context[i]&0xFF;
   77 
   78   free(Context);
   79   free(Counter);
   80 
   81   return FBP;
   82 }
   83 
   84 #define ST_SetBit(Bit) (Flag[Bit>>3]|=(1<<(Bit & 7)))
   85 #define ST_GetBit(Bit) (Flag[Bit>>3]&(1<<(Bit & 7)))
   86 
   87 sint32 GRZip_ST4_Decode(uint8 * Input, sint32 Size, sint32 FBP)
   88 {
   89   sint32    LastSeen[ST_MaxByte],T[ST_MaxByte],S[ST_MaxByte];
   90   sint32    CStart,Sum,i,j;
   91 
   92   sint32 *  Context2=(sint32 *)malloc(ST_MaxWord*sizeof(sint32));
   93   if (Context2==NULL) return (GRZ_NOT_ENOUGH_MEMORY);
   94 
   95   uint8  *  Flag=(uint8 *)malloc(((Size+8)>>3)*sizeof(uint8));
   96   if (Flag==NULL) {free(Context2);return (GRZ_NOT_ENOUGH_MEMORY);}
   97 
   98   uint32 *  Table=(uint32 *)malloc((Size+1)*sizeof(uint32));
   99   if (Table==NULL) {free(Flag);free(Context2);return (GRZ_NOT_ENOUGH_MEMORY);}
  100 
  101   memset    (Context2,0,ST_MaxWord*sizeof(sint32));
  102   memset    (Flag,0,((Size+8)>>3)*sizeof(uint8));
  103 
  104   memset    (T,0,ST_MaxByte*sizeof(sint32));
  105   memset    (LastSeen,0xFF,ST_MaxByte*sizeof(sint32));
  106 
  107   for (i=0;i<Size;i++) T[Input[i]]++;
  108 
  109   for (i=0,j=0,Sum=0;i<ST_MaxByte;i++)
  110     for (Sum+=T[i],T[i]=Sum-T[i];j<Sum;j++)
  111       Context2[(Input[j]<<8)|i]++;
  112 
  113   memcpy(S,T,ST_MaxByte*sizeof(sint32));
  114 
  115   for (i=0,j=0,Sum=0;i<ST_MaxWord;i++)
  116     for (CStart=Sum,Sum+=Context2[i];j<Sum;j++)
  117     {
  118       uint8 c=Input[j];
  119       if (LastSeen[c]!=CStart)
  120       {
  121         LastSeen[c]=CStart;
  122         ST_SetBit(T[c]);
  123       }
  124       T[c]++;
  125     }
  126 
  127   memset(LastSeen,0,ST_MaxByte*sizeof(sint32));
  128 
  129   for (CStart=0,i=0;i<Size;i++)
  130   {
  131     uint8 c=Input[i];
  132     if (ST_GetBit(i)) CStart=i;
  133     if (LastSeen[c]<=CStart)
  134     {
  135       Table[i]=S[c];
  136       LastSeen[c]=i+1;
  137     }
  138     else
  139       Table[i]=(LastSeen[c]-1)|ST_INDIRECT;
  140     S[c]++;
  141     Table[i]|=(c<<24);
  142   }
  143   Table[Size]=ST_INDIRECT;
  144 
  145   free(Context2);
  146   free(Flag);
  147 
  148   for (j=FBP,Sum=Table[FBP],i=0;i<Size;i++)
  149     if (Sum&ST_INDIRECT)
  150     {
  151       j=((Table[Sum&(ST_INDIRECT-1)]++)&(ST_INDIRECT-1));
  152       Sum=Table[j];
  153       Input[i]=Sum>>24;
  154     }
  155     else
  156     {
  157       Table[j]++; Sum=Table[j=Sum&(ST_INDIRECT-1)];
  158       Input[i]=Sum>>24;
  159     }
  160   free(Table);
  161   return GRZ_NO_ERROR;
  162 }
  163 
  164 #undef ST_MaxByte
  165 #undef ST_MaxWord
  166 #undef ST_INDIRECT
  167 #undef ST_SetBit
  168 #undef ST_GetBit
  169 
  170 /*-------------------------------------------------*/
  171 /* End                                       ST4.c */
  172 /*-------------------------------------------------*/