git.oblomov.eu Git - linux-2.6/blob - drivers/char/ftape/compressor/lzrw3.h

   1 #ifndef _LZRW3_H
   2 #define _LZRW3_H
   3 /*
   4  * $Source: /homes/cvs/ftape-stacked/ftape/compressor/lzrw3.h,v $
   5  * $Revision: 1.1 $
   6  * $Date: 1997/10/05 19:12:30 $
   7  *
   8  *  include files for lzrw3. Only slighty modified from the original
   9  *  version. Assembles the three include files compress.h, port.h and
  10  *  fastcopy.h from the original lzrw3 package.
  11  *
  12  */
  13
  14 #include <linux/types.h>
  15 #include <linux/string.h>
  16
  17 /******************************************************************************/
  18 /*                                                                            */
  19 /*                                 COMPRESS.H                                 */
  20 /*                                                                            */
  21 /******************************************************************************/
  22 /*                                                                            */
  23 /* Author : Ross Williams.                                                    */
  24 /* Date   : December 1989.                                                    */
  25 /*                                                                            */
  26 /* This header file defines the interface to a set of functions called        */
  27 /* 'compress', each member of which implements a particular data compression  */
  28 /* algorithm.                                                                 */
  29 /*                                                                            */
  30 /* Normally in C programming, for each .H file, there is a corresponding .C   */
  31 /* file that implements the functions promised in the .H file.                */
  32 /* Here, there are many .C files corresponding to this header file.           */
  33 /* Each comforming implementation file contains a single function             */
  34 /* called 'compress' that implements a single data compression                */
  35 /* algorithm that conforms with the interface specified in this header file.  */
  36 /* Only one algorithm can be linked in at a time in this organization.        */
  37 /*                                                                            */
  38 /******************************************************************************/
  39 /*                                                                            */
  40 /*                    DEFINITION OF FUNCTION COMPRESS                         */
  41 /*                    ===============================                         */
  42 /*                                                                            */
  43 /* Summary of Function Compress                                               */
  44 /* ----------------------------                                               */
  45 /* The action that 'compress' takes depends on its first argument called      */
  46 /* 'action'.  The function provides three actions:                            */
  47 /*                                                                            */
  48 /*    - Return information about the algorithm.                               */
  49 /*    - Compress   a block of memory.                                         */
  50 /*    - Decompress a block of memory.                                         */
  51 /*                                                                            */
  52 /* Parameters                                                                 */
  53 /* ----------                                                                 */
  54 /* See the formal C definition later for a description of the parameters.     */
  55 /*                                                                            */
  56 /* Constants                                                                  */
  57 /* ---------                                                                  */
  58 /* COMPRESS_OVERRUN: The constant COMPRESS_OVERRUN defines by how many bytes  */
  59 /* an algorithm is allowed to expand a block during a compression operation.  */
  60 /*                                                                            */
  61 /* Although compression algorithms usually compress data, there will always   */
  62 /* be data that a given compressor will expand (this can be proven).          */
  63 /* Fortunately, the degree of expansion can be limited to a single bit, by    */
  64 /* copying over the input data if the data gets bigger during compression.    */
  65 /* To allow for this possibility, the first bit of a compressed               */
  66 /* representation can be used as a flag indicating whether the                */
  67 /* input data was copied over, or truly compressed. In practice, the first    */
  68 /* byte would be used to store this bit so as to maintain byte alignment.     */
  69 /*                                                                            */
  70 /* Unfortunately, in general, the only way to tell if an algorithm will       */
  71 /* expand a particular block of data is to run the algorithm on the data.     */
  72 /* If the algorithm does not continuously monitor how many output bytes it    */
  73 /* has written, it might write an output block far larger than the input      */
  74 /* block before realizing that it has done so.                                */
  75 /* On the other hand, continuous checks on output length are inefficient.     */
  76 /*                                                                            */
  77 /* To cater for all these problems, this interface definition:                */
  78 /* > Allows a compression algorithm to return an output block that is up to   */
  79 /*   COMPRESS_OVERRUN bytes longer than the input block.                      */
  80 /* > Allows a compression algorithm to write up to COMPRESS_OVERRUN bytes     */
  81 /*   more than the length of the input block to the memory of the output      */
  82 /*   block regardless of the length of the output block eventually returned.  */
  83 /*   This allows an algorithm to overrun the length of the input block in the */
  84 /*   output block by up to COMPRESS_OVERRUN bytes between expansion checks.   */
  85 /*                                                                            */
  86 /* The problem does not arise for decompression.                              */
  87 /*                                                                            */
  88 /* Identity Action                                                            */
  89 /* ---------------                                                            */
  90 /* > action must be COMPRESS_ACTION_IDENTITY.                                 */
  91 /* > p_dst_len must point to a longword to receive a longword address.        */
  92 /* > The value of the other parameters does not matter.                       */
  93 /* > After execution, the longword that p_dst_len points to will be a pointer */
  94 /*   to a structure of type compress_identity.                                */
  95 /*   Thus, for example, after the call, (*p_dst_len)->memory will return the  */
  96 /*   number of bytes of working memory that the algorithm requires to run.    */
  97 /* > The values of the identity structure returned are fixed constant         */
  98 /*   attributes of the algorithm and must not vary from call to call.         */
  99 /*                                                                            */
 100 /* Common Requirements for Compression and Decompression Actions              */
 101 /* -------------------------------------------------------------              */
 102 /* > wrk_mem must point to an unused block of memory of a length specified in */
 103 /*   the algorithm's identity block. The identity block can be obtained by    */
 104 /*   making a separate call to compress, specifying the identity action.      */
 105 /* > The INPUT BLOCK is defined to be Memory[src_addr,src_addr+src_len-1].    */
 106 /* > dst_len will be used to denote *p_dst_len.                               */
 107 /* > dst_len is not read by compress, only written.                           */
 108 /* > The value of dst_len is defined only upon termination.                   */
 109 /* > The OUTPUT BLOCK is defined to be Memory[dst_addr,dst_addr+dst_len-1].   */
 110 /*                                                                            */
 111 /* Compression Action                                                         */
 112 /* ------------------                                                         */
 113 /* > action must be COMPRESS_ACTION_COMPRESS.                                 */
 114 /* > src_len must be in the range [0,COMPRESS_MAX_ORG].                       */
 115 /* > The OUTPUT ZONE is defined to be                                         */
 116 /*      Memory[dst_addr,dst_addr+src_len-1+COMPRESS_OVERRUN].                 */
 117 /* > The function can modify any part of the output zone regardless of the    */
 118 /*   final length of the output block.                                        */
 119 /* > The input block and the output zone must not overlap.                    */
 120 /* > dst_len will be in the range [0,src_len+COMPRESS_OVERRUN].               */
 121 /* > dst_len will be in the range [0,COMPRESS_MAX_COM] (from prev fact).      */
 122 /* > The output block will consist of a representation of the input block.    */
 123 /*                                                                            */
 124 /* Decompression Action                                                       */
 125 /* --------------------                                                       */
 126 /* > action must be COMPRESS_ACTION_DECOMPRESS.                               */
 127 /* > The input block must be the result of an earlier compression operation.  */
 128 /* > If the previous fact is true, the following facts must also be true:     */
 129 /*   > src_len will be in the range [0,COMPRESS_MAX_COM].                     */
 130 /*   > dst_len will be in the range [0,COMPRESS_MAX_ORG].                     */
 131 /* > The input and output blocks must not overlap.                            */
 132 /* > Only the output block is modified.                                       */
 133 /* > Upon termination, the output block will consist of the bytes contained   */
 134 /*   in the input block passed to the earlier compression operation.          */
 135 /*                                                                            */
 136 /******************************************************************************/
 137
 138 /******************************************************************************/
 139 /*                                                                            */
 140 /*                                    PORT.H                                  */
 141 /*                                                                            */
 142 /******************************************************************************/
 143 /*                                                                            */
 144 /* This module contains macro definitions and types that are likely to        */
 145 /* change between computers.                                                  */
 146 /*                                                                            */
 147 /******************************************************************************/
 148
 149 #ifndef DONE_PORT       /* Only do this if not previously done.               */
 150
 151    #ifdef THINK_C
 152       #define UBYTE unsigned char      /* Unsigned byte                       */
 153       #define UWORD unsigned int       /* Unsigned word (2 bytes)             */
 154       #define ULONG unsigned long      /* Unsigned word (4 bytes)             */
 155       #define BOOL  unsigned char      /* Boolean                             */
 156       #define FOPEN_BINARY_READ  "rb"  /* Mode string for binary reading.     */
 157       #define FOPEN_BINARY_WRITE "wb"  /* Mode string for binary writing.     */
 158       #define FOPEN_TEXT_APPEND  "a"   /* Mode string for text appending.     */
 159       #define REAL double              /* USed for floating point stuff.      */
 160    #endif
 161    #if defined(LINUX) || defined(linux)
 162       #define UBYTE __u8               /* Unsigned byte                       */
 163       #define UWORD __u16              /* Unsigned word (2 bytes)             */
 164       #define ULONG __u32              /* Unsigned word (4 bytes)             */
 165       #define LONG  __s32              /* Signed   word (4 bytes)             */
 166       #define BOOL  is not used here   /* Boolean                             */
 167       #define FOPEN_BINARY_READ  not used  /* Mode string for binary reading. */
 168       #define FOPEN_BINARY_WRITE not used  /* Mode string for binary writing. */
 169       #define FOPEN_TEXT_APPEND  not used  /* Mode string for text appending. */
 170       #define REAL not used                /* USed for floating point stuff.  */
 171       #ifndef TRUE
 172       #define TRUE 1
 173       #endif
 174    #endif
 175
 176    #define DONE_PORT                   /* Don't do all this again.            */
 177    #define MALLOC_FAIL NULL            /* Failure status from malloc()        */
 178    #define LOCAL static                /* For non-exported routines.          */
 179    #define EXPORT                      /* Signals exported function.          */
 180    #define then                        /* Useful for aligning ifs.            */
 181
 182 #endif
 183
 184 /******************************************************************************/
 185 /*                              End of PORT.H                                 */
 186 /******************************************************************************/
 187
 188 #define COMPRESS_ACTION_IDENTITY   0
 189 #define COMPRESS_ACTION_COMPRESS   1
 190 #define COMPRESS_ACTION_DECOMPRESS 2
 191
 192 #define COMPRESS_OVERRUN 1024
 193 #define COMPRESS_MAX_COM 0x70000000
 194 #define COMPRESS_MAX_ORG (COMPRESS_MAX_COM-COMPRESS_OVERRUN)
 195
 196 #define COMPRESS_MAX_STRLEN 255
 197
 198 /* The following structure provides information about the algorithm.         */
 199 /* > The top bit of id must be zero. The remaining bits must be chosen by    */
 200 /*   the author of the algorithm by tossing a coin 31 times.                 */
 201 /* > The amount of memory requested by the algorithm is specified in bytes   */
 202 /*   and must be in the range [0,0x70000000].                                */
 203 /* > All strings s must be such that strlen(s)<=COMPRESS_MAX_STRLEN.         */
 204 struct compress_identity
 205   {
 206    ULONG id;           /* Identifying number of algorithm.            */
 207    ULONG memory;       /* Number of bytes of working memory required. */
 208
 209    char  *name;        /* Name of algorithm.                          */
 210    char  *version;     /* Version number.                             */
 211    char  *date;        /* Date of release of this version.            */
 212    char  *copyright;   /* Copyright message.                          */
 213
 214    char  *author;      /* Author of algorithm.                        */
 215    char  *affiliation; /* Affiliation of author.                      */
 216    char  *vendor;      /* Where the algorithm can be obtained.        */
 217   };
 218
 219 void  lzrw3_compress(        /* Single function interface to compression algorithm. */
 220 UWORD     action,      /* Action to be performed.                             */
 221 UBYTE   *wrk_mem,      /* Working memory temporarily given to routine to use. */
 222 UBYTE   *src_adr,      /* Address of input  data.                             */
 223 LONG     src_len,      /* Length  of input  data.                             */
 224 UBYTE   *dst_adr,      /* Address of output data.                             */
 225 void  *p_dst_len       /* Pointer to a longword where routine will write:     */
 226                        /*    If action=..IDENTITY   => Adr of id structure.   */
 227                        /*    If action=..COMPRESS   => Length of output data. */
 228                        /*    If action=..DECOMPRESS => Length of output data. */
 229 );
 230
 231 /******************************************************************************/
 232 /*                             End of COMPRESS.H                              */
 233 /******************************************************************************/
 234
 235
 236 /******************************************************************************/
 237 /*                                  fast_copy.h                               */
 238 /******************************************************************************/
 239
 240 /* This function copies a block of memory very quickly.                       */
 241 /* The exact speed depends on the relative alignment of the blocks of memory. */
 242 /* PRE  : 0<=src_len<=(2^32)-1 .                                              */
 243 /* PRE  : Source and destination blocks must not overlap.                     */
 244 /* POST : MEM[dst_adr,dst_adr+src_len-1]=MEM[src_adr,src_adr+src_len-1].      */
 245 /* POST : MEM[dst_adr,dst_adr+src_len-1] is the only memory changed.          */
 246
 247 #define fast_copy(src,dst,len) memcpy(dst,src,len)
 248
 249 /******************************************************************************/
 250 /*                               End of fast_copy.h                           */
 251 /******************************************************************************/
 252
 253 #endif