diff options
| author | Linus Torvalds | 2005-04-16 15:20:36 -0700 |
|---|---|---|
| committer | Linus Torvalds | 2005-04-16 15:20:36 -0700 |
| commit | 1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 (patch) | |
| tree | 0bba044c4ce775e45a88a51686b5d9f90697ea9d /drivers/char/ftape/compressor | |
Linux-2.6.12-rc2
Initial git repository build. I'm not bothering with the full history,
even though we have it. We can create a separate "historical" git
archive of that later if we want to, and in the meantime it's about
3.2GB when imported into git - space that would just make the early
git days unnecessarily complicated, when we don't have a lot of good
infrastructure for it.
Let it rip!
Diffstat (limited to 'drivers/char/ftape/compressor')
| -rw-r--r-- | drivers/char/ftape/compressor/Makefile | 31 | ||||
| -rw-r--r-- | drivers/char/ftape/compressor/lzrw3.c | 743 | ||||
| -rw-r--r-- | drivers/char/ftape/compressor/lzrw3.h | 253 | ||||
| -rw-r--r-- | drivers/char/ftape/compressor/zftape-compress.c | 1203 | ||||
| -rw-r--r-- | drivers/char/ftape/compressor/zftape-compress.h | 83 |
5 files changed, 2313 insertions, 0 deletions
diff --git a/drivers/char/ftape/compressor/Makefile b/drivers/char/ftape/compressor/Makefile new file mode 100644 index 000000000000..1fbd6c4019db --- /dev/null +++ b/drivers/char/ftape/compressor/Makefile @@ -0,0 +1,31 @@ +# +# Copyright (C) 1997 Claus-Justus Heine. +# +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 2, or (at your option) +# any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program; see the file COPYING. If not, write to +# the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. +# +# $Source: /homes/cvs/ftape-stacked/ftape/compressor/Makefile,v $ +# $Revision: 1.1 $ +# $Date: 1997/10/05 19:12:28 $ +# +# Makefile for the optional compressor for th zftape VFS +# interface to the QIC-40/80/3010/3020 floppy-tape driver for +# Linux. +# + +obj-$(CONFIG_ZFT_COMPRESSOR) += zft-compressor.o + +zft-compressor-objs := zftape-compress.o lzrw3.o + +CFLAGS_lzrw3.o := -O6 -funroll-all-loops diff --git a/drivers/char/ftape/compressor/lzrw3.c b/drivers/char/ftape/compressor/lzrw3.c new file mode 100644 index 000000000000..a032a0ee2a99 --- /dev/null +++ b/drivers/char/ftape/compressor/lzrw3.c @@ -0,0 +1,743 @@ +/* + * $Source: /homes/cvs/ftape-stacked/ftape/compressor/lzrw3.c,v $ + * $Revision: 1.1 $ + * $Date: 1997/10/05 19:12:29 $ + * + * Implementation of Ross Williams lzrw3 algorithm. Adaption for zftape. + * + */ + +#include "../compressor/lzrw3.h" /* Defines single exported function "compress". */ + +/******************************************************************************/ +/* */ +/* LZRW3.C */ +/* */ +/******************************************************************************/ +/* */ +/* Author : Ross Williams. */ +/* Date : 30-Jun-1991. */ +/* Release : 1. */ +/* */ +/******************************************************************************/ +/* */ +/* This file contains an implementation of the LZRW3 data compression */ +/* algorithm in C. */ +/* */ +/* The algorithm is a general purpose compression algorithm that runs fast */ +/* and gives reasonable compression. The algorithm is a member of the Lempel */ +/* Ziv family of algorithms and bases its compression on the presence in the */ +/* data of repeated substrings. */ +/* */ +/* This algorithm is unpatented and the code is public domain. As the */ +/* algorithm is based on the LZ77 class of algorithms, it is unlikely to be */ +/* the subject of a patent challenge. */ +/* */ +/* Unlike the LZRW1 and LZRW1-A algorithms, the LZRW3 algorithm is */ +/* deterministic and is guaranteed to yield the same compressed */ +/* representation for a given file each time it is run. */ +/* */ +/* The LZRW3 algorithm was originally designed and implemented */ +/* by Ross Williams on 31-Dec-1990. */ +/* */ +/* Here are the results of applying this code, compiled under THINK C 4.0 */ +/* and running on a Mac-SE (8MHz 68000), to the standard calgary corpus. */ +/* */ +/* +----------------------------------------------------------------+ */ +/* | DATA COMPRESSION TEST | */ +/* | ===================== | */ +/* | Time of run : Sun 30-Jun-1991 09:31PM | */ +/* | Timing accuracy : One part in 100 | */ +/* | Context length : 262144 bytes (= 256.0000K) | */ +/* | Test suite : Calgary Corpus Suite | */ +/* | Files in suite : 14 | */ +/* | Algorithm : LZRW3 | */ +/* | Note: All averages are calculated from the un-rounded values. | */ +/* +----------------------------------------------------------------+ */ +/* | File Name Length CxB ComLen %Remn Bits Com K/s Dec K/s | */ +/* | ---------- ------ --- ------ ----- ---- ------- ------- | */ +/* | rpus:Bib.D 111261 1 55033 49.5 3.96 19.46 32.27 | */ +/* | us:Book1.D 768771 3 467962 60.9 4.87 17.03 31.07 | */ +/* | us:Book2.D 610856 3 317102 51.9 4.15 19.39 34.15 | */ +/* | rpus:Geo.D 102400 1 82424 80.5 6.44 11.65 18.18 | */ +/* | pus:News.D 377109 2 205670 54.5 4.36 17.14 27.47 | */ +/* | pus:Obj1.D 21504 1 13027 60.6 4.85 13.40 18.95 | */ +/* | pus:Obj2.D 246814 1 116286 47.1 3.77 19.31 30.10 | */ +/* | s:Paper1.D 53161 1 27522 51.8 4.14 18.60 31.15 | */ +/* | s:Paper2.D 82199 1 45160 54.9 4.40 18.45 32.84 | */ +/* | rpus:Pic.D 513216 2 122388 23.8 1.91 35.29 51.05 | */ +/* | us:Progc.D 39611 1 19669 49.7 3.97 18.87 30.64 | */ +/* | us:Progl.D 71646 1 28247 39.4 3.15 24.34 40.66 | */ +/* | us:Progp.D 49379 1 19377 39.2 3.14 23.91 39.23 | */ +/* | us:Trans.D 93695 1 33481 35.7 2.86 25.48 40.37 | */ +/* +----------------------------------------------------------------+ */ +/* | Average 224401 1 110953 50.0 4.00 20.17 32.72 | */ +/* +----------------------------------------------------------------+ */ +/* */ +/******************************************************************************/ + +/******************************************************************************/ + +/* The following structure is returned by the "compress" function below when */ +/* the user asks the function to return identifying information. */ +/* The most important field in the record is the working memory field which */ +/* tells the calling program how much working memory should be passed to */ +/* "compress" when it is called to perform a compression or decompression. */ +/* LZRW3 uses the same amount of memory during compression and decompression. */ +/* For more information on this structure see "compress.h". */ + +#define U(X) ((ULONG) X) +#define SIZE_P_BYTE (U(sizeof(UBYTE *))) +#define SIZE_WORD (U(sizeof(UWORD ))) +#define ALIGNMENT_FUDGE (U(16)) +#define MEM_REQ ( U(4096)*(SIZE_P_BYTE) + ALIGNMENT_FUDGE ) + +static struct compress_identity identity = +{ + U(0x032DDEA8), /* Algorithm identification number. */ + MEM_REQ, /* Working memory (bytes) required. */ + "LZRW3", /* Name of algorithm. */ + "1.0", /* Version number of algorithm. */ + "31-Dec-1990", /* Date of algorithm. */ + "Public Domain", /* Copyright notice. */ + "Ross N. Williams", /* Author of algorithm. */ + "Renaissance Software", /* Affiliation of author. */ + "Public Domain" /* Vendor of algorithm. */ +}; + +LOCAL void compress_compress (UBYTE *,UBYTE *,ULONG,UBYTE *, LONG *); +LOCAL void compress_decompress(UBYTE *,UBYTE *,LONG, UBYTE *, ULONG *); + +/******************************************************************************/ + +/* This function is the only function exported by this module. */ +/* Depending on its first parameter, the function can be requested to */ +/* compress a block of memory, decompress a block of memory, or to identify */ +/* itself. For more information, see the specification file "compress.h". */ + +EXPORT void lzrw3_compress( + UWORD action, /* Action to be performed. */ + UBYTE *wrk_mem, /* Address of working memory we can use.*/ + UBYTE *src_adr, /* Address of input data. */ + LONG src_len, /* Length of input data. */ + UBYTE *dst_adr, /* Address to put output data. */ + void *p_dst_len /* Address of longword for length of output data.*/ +) +{ + switch (action) + { + case COMPRESS_ACTION_IDENTITY: + *((struct compress_identity **)p_dst_len)= &identity; + break; + case COMPRESS_ACTION_COMPRESS: + compress_compress(wrk_mem,src_adr,src_len,dst_adr,(LONG *)p_dst_len); + break; + case COMPRESS_ACTION_DECOMPRESS: + compress_decompress(wrk_mem,src_adr,src_len,dst_adr,(LONG *)p_dst_len); + break; + } +} + +/******************************************************************************/ +/* */ +/* BRIEF DESCRIPTION OF THE LZRW3 ALGORITHM */ +/* ======================================== */ +/* The LZRW3 algorithm is identical to the LZRW1-A algorithm except that */ +/* instead of transmitting history offsets, it transmits hash table indexes. */ +/* In order to decode the indexes, the decompressor must maintain an */ +/* identical hash table. Copy items are straightforward:when the decompressor */ +/* receives a copy item, it simply looks up the hash table to translate the */ +/* index into a pointer into the data already decompressed. To update the */ +/* hash table, it replaces the same table entry with a pointer to the start */ +/* of the newly decoded phrase. The tricky part is with literal items, for at */ +/* the time that the decompressor receives a literal item the decompressor */ +/* does not have the three bytes in the Ziv (that the compressor has) to */ +/* perform the three-byte hash. To solve this problem, in LZRW3, both the */ +/* compressor and decompressor are wired up so that they "buffer" these */ +/* literals and update their hash tables only when three bytes are available. */ +/* This makes the maximum buffering 2 bytes. */ +/* */ +/* Replacement of offsets by hash table indexes yields a few percent extra */ +/* compression at the cost of some speed. LZRW3 is slower than LZRW1, LZRW1-A */ +/* and LZRW2, but yields better compression. */ +/* */ +/* Extra compression could be obtained by using a hash table of depth two. */ +/* However, increasing the depth above one incurs a significant decrease in */ +/* compression speed which was not considered worthwhile. Another reason for */ +/* keeping the depth down to one was to allow easy comparison with the */ +/* LZRW1-A and LZRW2 algorithms so as to demonstrate the exact effect of the */ +/* use of direct hash indexes. */ +/* */ +/* +---+ */ +/* |___|4095 */ +/* |___| */ +/* +---------------------*_|<---+ /----+---\ */ +/* | |___| +---|Hash | */ +/* | |___| |Function| */ +/* | |___| \--------/ */ +/* | |___|0 ^ */ +/* | +---+ | */ +/* | Hash +-----+ */ +/* | Table | */ +/* | --- */ +/* v ^^^ */ +/* +-------------------------------------|----------------+ */ +/* |||||||||||||||||||||||||||||||||||||||||||||||||||||||| */ +/* +-------------------------------------|----------------+ */ +/* | |1......18| | */ +/* |<------- Lempel=History ------------>|<--Ziv-->| | */ +/* | (=bytes already processed) |<-Still to go-->| */ +/* |<-------------------- INPUT BLOCK ------------------->| */ +/* */ +/* The diagram above for LZRW3 looks almost identical to the diagram for */ +/* LZRW1. The difference is that in LZRW3, the compressor transmits hash */ +/* table indices instead of Lempel offsets. For this to work, the */ +/* decompressor must maintain a hash table as well as the compressor and both */ +/* compressor and decompressor must "buffer" literals, as the decompressor */ +/* cannot hash phrases commencing with a literal until another two bytes have */ +/* arrived. */ +/* */ +/* LZRW3 Algorithm Execution Summary */ +/* --------------------------------- */ +/* 1. Hash the first three bytes of the Ziv to yield a hash table index h. */ +/* 2. Look up the hash table yielding history pointer p. */ +/* 3. Match where p points with the Ziv. If there is a match of three or */ +/* more bytes, code those bytes (in the Ziv) as a copy item, otherwise */ +/* code the next byte in the Ziv as a literal item. */ +/* 4. Update the hash table as possible subject to the constraint that only */ +/* phrases commencing three bytes back from the Ziv can be hashed and */ +/* entered into the hash table. (This enables the decompressor to keep */ +/* pace). See the description and code for more details. */ +/* */ +/******************************************************************************/ +/* */ +/* DEFINITION OF COMPRESSED FILE FORMAT */ +/* ==================================== */ +/* * A compressed file consists of a COPY FLAG followed by a REMAINDER. */ +/* * The copy flag CF uses up four bytes with the first byte being the */ +/* least significant. */ +/* * If CF=1, then the compressed file represents the remainder of the file */ +/* exactly. Otherwise CF=0 and the remainder of the file consists of zero */ +/* or more GROUPS, each of which represents one or more bytes. */ +/* * Each group consists of two bytes of CONTROL information followed by */ +/* sixteen ITEMs except for the last group which can contain from one */ +/* to sixteen items. */ +/* * An item can be either a LITERAL item or a COPY item. */ +/* * Each item corresponds to a bit in the control bytes. */ +/* * The first control byte corresponds to the first 8 items in the group */ +/* with bit 0 corresponding to the first item in the group and bit 7 to */ +/* the eighth item in the group. */ +/* * The second control byte corresponds to the second 8 items in the group */ +/* with bit 0 corresponding to the ninth item in the group and bit 7 to */ +/* the sixteenth item in the group. */ +/* * A zero bit in a control word means that the corresponding item is a */ +/* literal item. A one bit corresponds to a copy item. */ +/* * A literal item consists of a single byte which represents itself. */ +/* * A copy item consists of two bytes that represent from 3 to 18 bytes. */ +/* * The first byte in a copy item will be denoted C1. */ +/* * The second byte in a copy item will be denoted C2. */ +/* * Bits will be selected using square brackets. */ +/* For example: C1[0..3] is the low nibble of the first control byte. */ +/* of copy item C1. */ +/* * The LENGTH of a copy item is defined to be C1[0..3]+3 which is a number */ +/* in the range [3,18]. */ +/* * The INDEX of a copy item is defined to be C1[4..7]*256+C2[0..8] which */ +/* is a number in the range [0,4095]. */ +/* * A copy item represents the sequence of bytes */ +/* text[POS-OFFSET..POS-OFFSET+LENGTH-1] where */ +/* text is the entire text of the uncompressed string. */ +/* POS is the index in the text of the character following the */ +/* string represented by all the items preceeding the item */ +/* being defined. */ +/* OFFSET is obtained from INDEX by looking up the hash table. */ +/* */ +/******************************************************************************/ + +/* The following #define defines the length of the copy flag that appears at */ +/* the start of the compressed file. The value of four bytes was chosen */ +/* because the fast_copy routine on my Macintosh runs faster if the source */ +/* and destination blocks are relatively longword aligned. */ +/* The actual flag data appears in the first byte. The rest are zeroed so as */ +/* to normalize the compressed representation (i.e. not non-deterministic). */ +#define FLAG_BYTES 4 + +/* The following #defines define the meaning of the values of the copy */ +/* flag at the start of the compressed file. */ +#define FLAG_COMPRESS 0 /* Signals that output was result of compression. */ +#define FLAG_COPY 1 /* Signals that output was simply copied over. */ + +/* The 68000 microprocessor (on which this algorithm was originally developed */ +/* is fussy about non-aligned arrays of words. To avoid these problems the */ +/* following macro can be used to "waste" from 0 to 3 bytes so as to align */ +/* the argument pointer. */ +#define ULONG_ALIGN_UP(X) ((((ULONG)X)+sizeof(ULONG)-1)&~(sizeof(ULONG)-1)) + + +/* The following constant defines the maximum length of an uncompressed item. */ +/* This definition must not be changed; its value is hardwired into the code. */ +/* The longest number of bytes that can be spanned by a single item is 18 */ +/* for the longest copy item. */ +#define MAX_RAW_ITEM (18) + +/* The following constant defines the maximum length of an uncompressed group.*/ +/* This definition must not be changed; its value is hardwired into the code. */ +/* A group contains at most 16 items which explains this definition. */ +#define MAX_RAW_GROUP (16*MAX_RAW_ITEM) + +/* The following constant defines the maximum length of a compressed group. */ +/* This definition must not be changed; its value is hardwired into the code. */ +/* A compressed group consists of two control bytes followed by up to 16 */ +/* compressed items each of which can have a maximum length of two bytes. */ +#define MAX_CMP_GROUP (2+16*2) + +/* The following constant defines the number of entries in the hash table. */ +/* This definition must not be changed; its value is hardwired into the code. */ +#define HASH_TABLE_LENGTH (4096) + +/* LZRW3, unlike LZRW1(-A), must initialize its hash table so as to enable */ +/* the compressor and decompressor to stay in step maintaining identical hash */ +/* tables. In an early version of the algorithm, the tables were simply */ +/* initialized to zero and a check for zero was included just before the */ +/* matching code. However, this test costs time. A better solution is to */ +/* initialize all the entries in the hash table to point to a constant */ +/* string. The decompressor does the same. This solution requires no extra */ +/* test. The contents of the string do not matter so long as the string is */ +/* the same for the compressor and decompressor and contains at least */ +/* MAX_RAW_ITEM bytes. I chose consecutive decimal digits because they do not */ +/* have white space problems (e.g. there is no chance that the compiler will */ +/* replace more than one space by a TAB) and because they make the length of */ +/* the string obvious by inspection. */ +#define START_STRING_18 ((UBYTE *) "123456789012345678") + +/* In this algorithm, hash values have to be calculated at more than one */ +/* point. The following macro neatens the code up for this. */ +#define HASH(PTR) \ + (((40543*(((*(PTR))<<8)^((*((PTR)+1))<<4)^(*((PTR)+2))))>>4) & 0xFFF) + +/******************************************************************************/ + +/* Input : Hand over the required amount of working memory in p_wrk_mem. */ +/* Input : Specify input block using p_src_first and src_len. */ +/* Input : Point p_dst_first to the start of the output zone (OZ). */ +/* Input : Point p_dst_len to a ULONG to receive the output length. */ +/* Input : Input block and output zone must not overlap. */ +/* Output : Length of output block written to *p_dst_len. */ +/* Output : Output block in Mem[p_dst_first..p_dst_first+*p_dst_len-1]. May */ +/* Output : write in OZ=Mem[p_dst_first..p_dst_first+src_len+MAX_CMP_GROUP-1].*/ +/* Output : Upon completion guaranteed *p_dst_len<=src_len+FLAG_BYTES. */ +LOCAL void compress_compress(UBYTE *p_wrk_mem, + UBYTE *p_src_first, ULONG src_len, + UBYTE *p_dst_first, LONG *p_dst_len) +{ + /* p_src and p_dst step through the source and destination blocks. */ + register UBYTE *p_src = p_src_first; + register UBYTE *p_dst = p_dst_first; + + /* The following variables are never modified and are used in the */ + /* calculations that determine when the main loop terminates. */ + UBYTE *p_src_post = p_src_first+src_len; + UBYTE *p_dst_post = p_dst_first+src_len; + UBYTE *p_src_max1 = p_src_first+src_len-MAX_RAW_ITEM; + UBYTE *p_src_max16 = p_src_first+src_len-MAX_RAW_ITEM*16; + + /* The variables 'p_control' and 'control' are used to buffer control bits. */ + /* Before each group is processed, the next two bytes of the output block */ + /* are set aside for the control word for the group about to be processed. */ + /* 'p_control' is set to point to the first byte of that word. Meanwhile, */ + /* 'control' buffers the control bits being generated during the processing */ + /* of the group. Instead of having a counter to keep track of how many items */ + /* have been processed (=the number of bits in the control word), at the */ + /* start of each group, the top word of 'control' is filled with 1 bits. */ + /* As 'control' is shifted for each item, the 1 bits in the top word are */ + /* absorbed or destroyed. When they all run out (i.e. when the top word is */ + /* all zero bits, we know that we are at the end of a group. */ +# define TOPWORD 0xFFFF0000 + UBYTE *p_control; + register ULONG control=TOPWORD; + + /* THe variable 'hash' always points to the first element of the hash table. */ + UBYTE **hash= (UBYTE **) ULONG_ALIGN_UP(p_wrk_mem); + + /* The following two variables represent the literal buffer. p_h1 points to */ + /* the hash table entry corresponding to the youngest literal. p_h2 points */ + /* to the hash table entry corresponding to the second youngest literal. */ + /* Note: p_h1=0=>p_h2=0 because zero values denote absence of a pending */ + /* literal. The variables are initialized to zero meaning an empty "buffer". */ + UBYTE **p_h1=NULL; + UBYTE **p_h2=NULL; + + /* To start, we write the flag bytes. Being optimistic, we set the flag to */ + /* FLAG_COMPRESS. The remaining flag bytes are zeroed so as to keep the */ + /* algorithm deterministic. */ + *p_dst++=FLAG_COMPRESS; + {UWORD i; for (i=2;i<=FLAG_BYTES;i++) *p_dst++=0;} + + /* Reserve the first word of output as the control word for the first group. */ + /* Note: This is undone at the end if the input block is empty. */ + p_control=p_dst; p_dst+=2; + + /* Initialize all elements of the hash table to point to a constant string. */ + /* Use of an unrolled loop speeds this up considerably. */ + {UWORD i; UBYTE **p_h=hash; +# define ZH *p_h++=START_STRING_18 + for (i=0;i<256;i++) /* 256=HASH_TABLE_LENGTH/16. */ + {ZH;ZH;ZH;ZH; + ZH;ZH;ZH;ZH; + ZH;ZH;ZH;ZH; + ZH;ZH;ZH;ZH;} + } + + /* The main loop processes either 1 or 16 items per iteration. As its */ + /* termination logic is complicated, I have opted for an infinite loop */ + /* structure containing 'break' and 'goto' statements. */ + while (TRUE) + {/* Begin main processing loop. */ + + /* Note: All the variables here except unroll should be defined within */ + /* the inner loop. Unfortunately the loop hasn't got a block. */ + register UBYTE *p; /* Scans through targ phrase during matching. */ + register UBYTE *p_ziv= NULL ; /* Points to first byte of current Ziv. */ + register UWORD unroll; /* Loop counter for unrolled inner loop. */ + register UWORD index; /* Index of current hash table entry. */ + register UBYTE **p_h0 = NULL ; /* Pointer to current hash table entry. */ + + /* Test for overrun and jump to overrun code if necessary. */ + if (p_dst>p_dst_post) + goto overrun; + + /* The following cascade of if statements efficiently catches and deals */ + /* with varying degrees of closeness to the end of the input block. */ + /* When we get very close to the end, we stop updating the table and */ + /* code the remaining bytes as literals. This makes the code simpler. */ + unroll=16; + if (p_src>p_src_max16) + { + unroll=1; + if (p_src>p_src_max1) + { + if (p_src==p_src_post) + break; + else + goto literal; + } + } + + /* This inner unrolled loop processes 'unroll' (whose value is either 1 */ + /* or 16) items. I have chosen to implement this loop with labels and */ + /* gotos to heighten the ease with which the loop may be implemented with */ + /* a single decrement and branch instruction in assembly language and */ + /* also because the labels act as highly readable place markers. */ + /* (Also because we jump into the loop for endgame literals (see above)). */ + + begin_unrolled_loop: + + /* To process the next phrase, we hash the next three bytes and use */ + /* the resultant hash table index to look up the hash table. A pointer */ + /* to the entry is stored in p_h0 so as to avoid an array lookup. The */ + /* hash table entry *p_h0 is looked up yielding a pointer p to a */ + /* potential match of the Ziv in the history. */ + index=HASH(p_src); + p_h0=&hash[index]; + p=*p_h0; + + /* Having looked up the candidate position, we are in a position to */ + /* attempt a match. The match loop has been unrolled using the PS */ + /* macro so that failure within the first three bytes automatically */ + /* results in the literal branch being taken. The coding is simple. */ + /* p_ziv saves p_src so we can let p_src wander. */ +# define PS *p++!=*p_src++ + p_ziv=p_src; + if (PS || PS || PS) + { + /* Literal. */ + + /* Code the literal byte as itself and a zero control bit. */ + p_src=p_ziv; literal: *p_dst++=*p_src++; control&=0xFFFEFFFF; + + /* We have just coded a literal. If we had two pending ones, that */ + /* makes three and we can update the hash table. */ + if (p_h2!=0) + {*p_h2=p_ziv-2;} + + /* In any case, rotate the hash table pointers for next time. */ + p_h2=p_h1; p_h1=p_h0; + + } + else + { + /* Copy */ + + /* Match up to 15 remaining bytes using an unrolled loop and code. */ +#if 0 + PS || PS || PS || PS || PS || PS || PS || PS || + PS || PS || PS || PS || PS || PS || PS || p_src++; +#else + if ( + !( PS || PS || PS || PS || PS || PS || PS || PS || + PS || PS || PS || PS || PS || PS || PS ) + ) p_src++; +#endif + *p_dst++=((index&0xF00)>>4)|(--p_src-p_ziv-3); + *p_dst++=index&0xFF; + + /* As we have just coded three bytes, we are now in a position to */ + /* update the hash table with the literal bytes that were pending */ + /* upon the arrival of extra context bytes. */ + if (p_h1!=0) + { + if (p_h2) + {*p_h2=p_ziv-2; p_h2=NULL;} + *p_h1=p_ziv-1; p_h1=NULL; + } + + /* In any case, we can update the hash table based on the current */ + /* position as we just coded at least three bytes in a copy items. */ + *p_h0=p_ziv; + + } + control>>=1; + + /* This loop is all set up for a decrement and jump instruction! */ +#ifndef linux +` end_unrolled_loop: if (--unroll) goto begin_unrolled_loop; +#else + /* end_unrolled_loop: */ if (--unroll) goto begin_unrolled_loop; +#endif + + /* At this point it will nearly always be the end of a group in which */ + /* case, we have to do some control-word processing. However, near the */ + /* end of the input block, the inner unrolled loop is only executed once. */ + /* This necessitates the 'if' test. */ + if ((control&TOPWORD)==0) + { + /* Write the control word to the place we saved for it in the output. */ + *p_control++= control &0xFF; + *p_control = (control>>8) &0xFF; + + /* Reserve the next word in the output block for the control word */ + /* for the group about to be processed. */ + p_control=p_dst; p_dst+=2; + + /* Reset the control bits buffer. */ + control=TOPWORD; + } + + } /* End main processing loop. */ + + /* After the main processing loop has executed, all the input bytes have */ + /* been processed. However, the control word has still to be written to the */ + /* word reserved for it in the output at the start of the most recent group. */ + /* Before writing, the control word has to be shifted so that all the bits */ + /* are in the right place. The "empty" bit positions are filled with 1s */ + /* which partially fill the top word. */ + while(control&TOPWORD) control>>=1; + *p_control++= control &0xFF; + *p_control++=(control>>8) &0xFF; + + /* If the last group contained no items, delete the control word too. */ + if (p_control==p_dst) p_dst-=2; + + /* Write the length of the output block to the dst_len parameter and return. */ + *p_dst_len=p_dst-p_dst_first; + return; + + /* Jump here as soon as an overrun is detected. An overrun is defined to */ + /* have occurred if p_dst>p_dst_first+src_len. That is, the moment the */ + /* length of the output written so far exceeds the length of the input block.*/ + /* The algorithm checks for overruns at least at the end of each group */ + /* which means that the maximum overrun is MAX_CMP_GROUP bytes. */ + /* Once an overrun occurs, the only thing to do is to set the copy flag and */ + /* copy the input over. */ + overrun: +#if 0 + *p_dst_first=FLAG_COPY; + fast_copy(p_src_first,p_dst_first+FLAG_BYTES,src_len); + *p_dst_len=src_len+FLAG_BYTES; +#else + fast_copy(p_src_first,p_dst_first,src_len); + *p_dst_len= -src_len; /* return a negative number to indicate uncompressed data */ +#endif +} + +/******************************************************************************/ + +/* Input : Hand over the required amount of working memory in p_wrk_mem. */ +/* Input : Specify input block using p_src_first and src_len. */ +/* Input : Point p_dst_first to the start of the output zone. */ +/* Input : Point p_dst_len to a ULONG to receive the output length. */ +/* Input : Input block and output zone must not overlap. User knows */ +/* Input : upperbound on output block length from earlier compression. */ +/* Input : In any case, maximum expansion possible is nine times. */ +/* Output : Length of output block written to *p_dst_len. */ +/* Output : Output block in Mem[p_dst_first..p_dst_first+*p_dst_len-1]. */ +/* Output : Writes only in Mem[p_dst_first..p_dst_first+*p_dst_len-1]. */ +LOCAL void compress_decompress( UBYTE *p_wrk_mem, + UBYTE *p_src_first, LONG src_len, + UBYTE *p_dst_first, ULONG *p_dst_len) +{ + /* Byte pointers p_src and p_dst scan through the input and output blocks. */ + register UBYTE *p_src = p_src_first+FLAG_BYTES; + register UBYTE *p_dst = p_dst_first; + /* we need to avoid a SEGV when trying to uncompress corrupt data */ + register UBYTE *p_dst_post = p_dst_first + *p_dst_len; + + /* The following two variables are never modified and are used to control */ + /* the main loop. */ + UBYTE *p_src_post = p_src_first+src_len; + UBYTE *p_src_max16 = p_src_first+src_len-(MAX_CMP_GROUP-2); + + /* The hash table is the only resident of the working memory. The hash table */ + /* contains HASH_TABLE_LENGTH=4096 pointers to positions in the history. To */ + /* keep Macintoshes happy, it is longword aligned. */ + UBYTE **hash = (UBYTE **) ULONG_ALIGN_UP(p_wrk_mem); + + /* The variable 'control' is used to buffer the control bits which appear in */ + /* groups of 16 bits (control words) at the start of each compressed group. */ + /* When each group is read, bit 16 of the register is set to one. Whenever */ + /* a new bit is needed, the register is shifted right. When the value of the */ + /* register becomes 1, we know that we have reached the end of a group. */ + /* Initializing the register to 1 thus instructs the code to follow that it */ + /* should read a new control word immediately. */ + register ULONG control=1; + + /* The value of 'literals' is always in the range 0..3. It is the number of */ + /* consecutive literal items just seen. We have to record this number so as */ + /* to know when to update the hash table. When literals gets to 3, there */ + /* have been three consecutive literals and we can update at the position of */ + /* the oldest of the three. */ + register UWORD literals=0; + + /* Check the leading copy flag to see if the compressor chose to use a copy */ + /* operation instead of a compression operation. If a copy operation was */ + /* used, then all we need to do is copy the data over, set the output length */ + /* and return. */ +#if 0 + if (*p_src_first==FLAG_COPY) + { + fast_copy(p_src_first+FLAG_BYTES,p_dst_first,src_len-FLAG_BYTES); + *p_dst_len=src_len-FLAG_BYTES; + return; + } +#else + if ( src_len < 0 ) + { + fast_copy(p_src_first,p_dst_first,-src_len ); + *p_dst_len = (ULONG)-src_len; + return; + } +#endif + + /* Initialize all elements of the hash table to point to a constant string. */ + /* Use of an unrolled loop speeds this up considerably. */ + {UWORD i; UBYTE **p_h=hash; +# define ZJ *p_h++=START_STRING_18 + for (i=0;i<256;i++) /* 256=HASH_TABLE_LENGTH/16. */ + {ZJ;ZJ;ZJ;ZJ; + ZJ;ZJ;ZJ;ZJ; + ZJ;ZJ;ZJ;ZJ; + ZJ;ZJ;ZJ;ZJ;} + } + + /* The outer loop processes either 1 or 16 items per iteration depending on */ + /* how close p_src is to the end of the input block. */ + while (p_src!=p_src_post) + {/* Start of outer loop */ + + register UWORD unroll; /* Counts unrolled loop executions. */ + + /* When 'control' has the value 1, it means that the 16 buffered control */ + /* bits that were read in at the start of the current group have all been */ + /* shifted out and that all that is left is the 1 bit that was injected */ + /* into bit 16 at the start of the current group. When we reach the end */ + /* of a group, we have to load a new control word and inject a new 1 bit. */ + if (control==1) + { + control=0x10000|*p_src++; + control|=(*p_src++)<<8; + } + + /* If it is possible that we are within 16 groups from the end of the */ + /* input, execute the unrolled loop only once, else process a whole group */ + /* of 16 items by looping 16 times. */ + unroll= p_src<=p_src_max16 ? 16 : 1; + + /* This inner loop processes one phrase (item) per iteration. */ + while (unroll--) + { /* Begin unrolled inner loop. */ + + /* Process a literal or copy item depending on the next control bit. */ + if (control&1) + { + /* Copy item. */ + + register UBYTE *p; /* Points to place from which to copy. */ + register UWORD lenmt; /* Length of copy item minus three. */ + register UBYTE **p_hte; /* Pointer to current hash table entry.*/ + register UBYTE *p_ziv=p_dst; /* Pointer to start of current Ziv. */ + + /* Read and dismantle the copy word. Work out from where to copy. */ + lenmt=*p_src++; + p_hte=&hash[((lenmt&0xF0)<<4)|*p_src++]; + p=*p_hte; + lenmt&=0xF; + + /* Now perform the copy using a half unrolled loop. */ + *p_dst++=*p++; + *p_dst++=*p++; + *p_dst++=*p++; + while (lenmt--) + *p_dst++=*p++; + + /* Because we have just received 3 or more bytes in a copy item */ + /* (whose bytes we have just installed in the output), we are now */ + /* in a position to flush all the pending literal hashings that had */ + /* been postponed for lack of bytes. */ + if (literals>0) + { + register UBYTE *r=p_ziv-literals; + hash[HASH(r)]=r; + if (literals==2) + {r++; hash[HASH(r)]=r;} + literals=0; + } + + /* In any case, we can immediately update the hash table with the */ + /* current position. We don't need to do a HASH(...) to work out */ + /* where to put the pointer, as the compressor just told us!!! */ + *p_hte=p_ziv; + + } + else + { + /* Literal item. */ + + /* Copy over the literal byte. */ + *p_dst++=*p_src++; + + /* If we now have three literals waiting to be hashed into the hash */ + /* table, we can do one of them now (because there are three). */ + if (++literals == 3) + {register UBYTE *p=p_dst-3; hash[HASH(p)]=p; literals=2;} + } + + /* Shift the control buffer so the next control bit is in bit 0. */ + control>>=1; +#if 1 + if (p_dst > p_dst_post) + { + /* Shit: we tried to decompress corrupt data */ + *p_dst_len = 0; + return; + } +#endif + } /* End unrolled inner loop. */ + + } /* End of outer loop */ + + /* Write the length of the decompressed data before returning. */ + *p_dst_len=p_dst-p_dst_first; +} + +/******************************************************************************/ +/* End of LZRW3.C */ +/******************************************************************************/ diff --git a/drivers/char/ftape/compressor/lzrw3.h b/drivers/char/ftape/compressor/lzrw3.h new file mode 100644 index 000000000000..533feba47526 --- /dev/null +++ b/drivers/char/ftape/compressor/lzrw3.h @@ -0,0 +1,253 @@ +#ifndef _LZRW3_H +#define _LZRW3_H +/* + * $Source: /homes/cvs/ftape-stacked/ftape/compressor/lzrw3.h,v $ + * $Revision: 1.1 $ + * $Date: 1997/10/05 19:12:30 $ + * + * include files for lzrw3. Only slighty modified from the original + * version. Assembles the three include files compress.h, port.h and + * fastcopy.h from the original lzrw3 package. + * + */ + +#include <linux/types.h> +#include <linux/string.h> + +/******************************************************************************/ +/* */ +/* COMPRESS.H */ +/* */ +/******************************************************************************/ +/* */ +/* Author : Ross Williams. */ +/* Date : December 1989. */ +/* */ +/* This header file defines the interface to a set of functions called */ +/* 'compress', each member of which implements a particular data compression */ +/* algorithm. */ +/* */ +/* Normally in C programming, for each .H file, there is a corresponding .C */ +/* file that implements the functions promised in the .H file. */ +/* Here, there are many .C files corresponding to this header file. */ +/* Each comforming implementation file contains a single function */ +/* called 'compress' that implements a single data compression */ +/* algorithm that conforms with the interface specified in this header file. */ +/* Only one algorithm can be linked in at a time in this organization. */ +/* */ +/******************************************************************************/ +/* */ +/* DEFINITION OF FUNCTION COMPRESS */ +/* =============================== */ +/* */ +/* Summary of Function Compress */ +/* ---------------------------- */ +/* The action that 'compress' takes depends on its first argument called */ +/* 'action'. The function provides three actions: */ +/* */ +/* - Return information about the algorithm. */ +/* - Compress a block of memory. */ +/* - Decompress a block of memory. */ +/* */ +/* Parameters */ +/* ---------- */ +/* See the formal C definition later for a description of the parameters. */ +/* */ +/* Constants */ +/* --------- */ +/* COMPRESS_OVERRUN: The constant COMPRESS_OVERRUN defines by how many bytes */ +/* an algorithm is allowed to expand a block during a compression operation. */ +/* */ +/* Although compression algorithms usually compress data, there will always */ +/* be data that a given compressor will expand (this can be proven). */ +/* Fortunately, the degree of expansion can be limited to a single bit, by */ +/* copying over the input data if the data gets bigger during compression. */ +/* To allow for this possibility, the first bit of a compressed */ +/* representation can be used as a flag indicating whether the */ +/* input data was copied over, or truly compressed. In practice, the first */ +/* byte would be used to store this bit so as to maintain byte alignment. */ +/* */ +/* Unfortunately, in general, the only way to tell if an algorithm will */ +/* expand a particular block of data is to run the algorithm on the data. */ +/* If the algorithm does not continuously monitor how many output bytes it */ +/* has written, it might write an output block far larger than the input */ +/* block before realizing that it has done so. */ +/* On the other hand, continuous checks on output length are inefficient. */ +/* */ +/* To cater for all these problems, this interface definition: */ +/* > Allows a compression algorithm to return an output block that is up to */ +/* COMPRESS_OVERRUN bytes longer than the input block. */ +/* > Allows a compression algorithm to write up to COMPRESS_OVERRUN bytes */ +/* more than the length of the input block to the memory of the output */ +/* block regardless of the length of the output block eventually returned. */ +/* This allows an algorithm to overrun the length of the input block in the */ +/* output block by up to COMPRESS_OVERRUN bytes between expansion checks. */ +/* */ +/* The problem does not arise for decompression. */ +/* */ +/* Identity Action */ +/* --------------- */ +/* > action must be COMPRESS_ACTION_IDENTITY. */ +/* > p_dst_len must point to a longword to receive a longword address. */ +/* > The value of the other parameters does not matter. */ +/* > After execution, the longword that p_dst_len points to will be a pointer */ +/* to a structure of type compress_identity. */ +/* Thus, for example, after the call, (*p_dst_len)->memory will return the */ +/* number of bytes of working memory that the algorithm requires to run. */ +/* > The values of the identity structure returned are fixed constant */ +/* attributes of the algorithm and must not vary from call to call. */ +/* */ +/* Common Requirements for Compression and Decompression Actions */ +/* ------------------------------------------------------------- */ +/* > wrk_mem must point to an unused block of memory of a length specified in */ +/* the algorithm's identity block. The identity block can be obtained by */ +/* making a separate call to compress, specifying the identity action. */ +/* > The INPUT BLOCK is defined to be Memory[src_addr,src_addr+src_len-1]. */ +/* > dst_len will be used to denote *p_dst_len. */ +/* > dst_len is not read by compress, only written. */ +/* > The value of dst_len is defined only upon termination. */ +/* > The OUTPUT BLOCK is defined to be Memory[dst_addr,dst_addr+dst_len-1]. */ +/* */ +/* Compression Action */ +/* ------------------ */ +/* > action must be COMPRESS_ACTION_COMPRESS. */ +/* > src_len must be in the range [0,COMPRESS_MAX_ORG]. */ +/* > The OUTPUT ZONE is defined to be */ +/* Memory[dst_addr,dst_addr+src_len-1+COMPRESS_OVERRUN]. */ +/* > The function can modify any part of the output zone regardless of the */ +/* final length of the output block. */ +/* > The input block and the output zone must not overlap. */ +/* > dst_len will be in the range [0,src_len+COMPRESS_OVERRUN]. */ +/* > dst_len will be in the range [0,COMPRESS_MAX_COM] (from prev fact). */ +/* > The output block will consist of a representation of the input block. */ +/* */ +/* Decompression Action */ +/* -------------------- */ +/* > action must be COMPRESS_ACTION_DECOMPRESS. */ +/* > The input block must be the result of an earlier compression operation. */ +/* > If the previous fact is true, the following facts must also be true: */ +/* > src_len will be in the range [0,COMPRESS_MAX_COM]. */ +/* > dst_len will be in the range [0,COMPRESS_MAX_ORG]. */ +/* > The input and output blocks must not overlap. */ +/* > Only the output block is modified. */ +/* > Upon termination, the output block will consist of the bytes contained */ +/* in the input block passed to the earlier compression operation. */ +/* */ +/******************************************************************************/ + +/******************************************************************************/ +/* */ +/* PORT.H */ +/* */ +/******************************************************************************/ +/* */ +/* This module contains macro definitions and types that are likely to */ +/* change between computers. */ +/* */ +/******************************************************************************/ + +#ifndef DONE_PORT /* Only do this if not previously done. */ + + #ifdef THINK_C + #define UBYTE unsigned char /* Unsigned byte */ + #define UWORD unsigned int /* Unsigned word (2 bytes) */ + #define ULONG unsigned long /* Unsigned word (4 bytes) */ + #define BOOL unsigned char /* Boolean */ + #define FOPEN_BINARY_READ "rb" /* Mode string for binary reading. */ + #define FOPEN_BINARY_WRITE "wb" /* Mode string for binary writing. */ + #define FOPEN_TEXT_APPEND "a" /* Mode string for text appending. */ + #define REAL double /* USed for floating point stuff. */ + #endif + #if defined(LINUX) || defined(linux) + #define UBYTE __u8 /* Unsigned byte */ + #define UWORD __u16 /* Unsigned word (2 bytes) */ + #define ULONG __u32 /* Unsigned word (4 bytes) */ + #define LONG __s32 /* Signed word (4 bytes) */ + #define BOOL is not used here /* Boolean */ + #define FOPEN_BINARY_READ not used /* Mode string for binary reading. */ + #define FOPEN_BINARY_WRITE not used /* Mode string for binary writing. */ + #define FOPEN_TEXT_APPEND not used /* Mode string for text appending. */ + #define REAL not used /* USed for floating point stuff. */ + #ifndef TRUE + #define TRUE 1 + #endif + #endif + + #define DONE_PORT /* Don't do all this again. */ + #define MALLOC_FAIL NULL /* Failure status from malloc() */ + #define LOCAL static /* For non-exported routines. */ + #define EXPORT /* Signals exported function. */ + #define then /* Useful for aligning ifs. */ + +#endif + +/******************************************************************************/ +/* End of PORT.H */ +/******************************************************************************/ + +#define COMPRESS_ACTION_IDENTITY 0 +#define COMPRESS_ACTION_COMPRESS 1 +#define COMPRESS_ACTION_DECOMPRESS 2 + +#define COMPRESS_OVERRUN 1024 +#define COMPRESS_MAX_COM 0x70000000 +#define COMPRESS_MAX_ORG (COMPRESS_MAX_COM-COMPRESS_OVERRUN) + +#define COMPRESS_MAX_STRLEN 255 + +/* The following structure provides information about the algorithm. */ +/* > The top bit of id must be zero. The remaining bits must be chosen by */ +/* the author of the algorithm by tossing a coin 31 times. */ +/* > The amount of memory requested by the algorithm is specified in bytes */ +/* and must be in the range [0,0x70000000]. */ +/* > All strings s must be such that strlen(s)<=COMPRESS_MAX_STRLEN. */ +struct compress_identity + { + ULONG id; /* Identifying number of algorithm. */ + ULONG memory; /* Number of bytes of working memory required. */ + + char *name; /* Name of algorithm. */ + char *version; /* Version number. */ + char *date; /* Date of release of this version. */ + char *copyright; /* Copyright message. */ + + char *author; /* Author of algorithm. */ + char *affiliation; /* Affiliation of author. */ + char *vendor; /* Where the algorithm can be obtained. */ + }; + +void lzrw3_compress( /* Single function interface to compression algorithm. */ +UWORD action, /* Action to be performed. */ +UBYTE *wrk_mem, /* Working memory temporarily given to routine to use. */ +UBYTE *src_adr, /* Address of input data. */ +LONG src_len, /* Length of input data. */ +UBYTE *dst_adr, /* Address of output data. */ +void *p_dst_len /* Pointer to a longword where routine will write: */ + /* If action=..IDENTITY => Adr of id structure. */ + /* If action=..COMPRESS => Length of output data. */ + /* If action=..DECOMPRESS => Length of output data. */ +); + +/******************************************************************************/ +/* End of COMPRESS.H */ +/******************************************************************************/ + + +/******************************************************************************/ +/* fast_copy.h */ +/******************************************************************************/ + +/* This function copies a block of memory very quickly. */ +/* The exact speed depends on the relative alignment of the blocks of memory. */ +/* PRE : 0<=src_len<=(2^32)-1 . */ +/* PRE : Source and destination blocks must not overlap. */ +/* POST : MEM[dst_adr,dst_adr+src_len-1]=MEM[src_adr,src_adr+src_len-1]. */ +/* POST : MEM[dst_adr,dst_adr+src_len-1] is the only memory changed. */ + +#define fast_copy(src,dst,len) memcpy(dst,src,len) + +/******************************************************************************/ +/* End of fast_copy.h */ +/******************************************************************************/ + +#endif diff --git a/drivers/char/ftape/compressor/zftape-compress.c b/drivers/char/ftape/compressor/zftape-compress.c new file mode 100644 index 000000000000..220a227e6061 --- /dev/null +++ b/drivers/char/ftape/compressor/zftape-compress.c @@ -0,0 +1,1203 @@ +/* + * Copyright (C) 1994-1997 Claus-Justus Heine + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2, or (at + your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; see the file COPYING. If not, write to + the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, + USA. + + * + * This file implements a "generic" interface between the * + * zftape-driver and a compression-algorithm. The * + * compression-algorithm currently used is a LZ77. I use the * + * implementation lzrw3 by Ross N. Williams (Renaissance * + * Software). The compression program itself is in the file + * lzrw3.c * and lzrw3.h. To adopt another compression algorithm + * the functions * zft_compress() and zft_uncompress() must be + * changed * appropriately. See below. + */ + +#include <linux/errno.h> +#include <linux/mm.h> +#include <linux/module.h> + +#include <linux/zftape.h> + +#include <asm/uaccess.h> + +#include "../zftape/zftape-init.h" +#include "../zftape/zftape-eof.h" +#include "../zftape/zftape-ctl.h" +#include "../zftape/zftape-write.h" +#include "../zftape/zftape-read.h" +#include "../zftape/zftape-rw.h" +#include "../compressor/zftape-compress.h" +#include "../zftape/zftape-vtbl.h" +#include "../compressor/lzrw3.h" + +/* + * global variables + */ + +/* I handle the allocation of this buffer as a special case, because + * it's size varies depending on the tape length inserted. + */ + +/* local variables + */ +static void *zftc_wrk_mem = NULL; +static __u8 *zftc_buf = NULL; +static void *zftc_scratch_buf = NULL; + +/* compression statistics + */ +static unsigned int zftc_wr_uncompressed = 0; +static unsigned int zftc_wr_compressed = 0; +static unsigned int zftc_rd_uncompressed = 0; +static unsigned int zftc_rd_compressed = 0; + +/* forward */ +static int zftc_write(int *write_cnt, + __u8 *dst_buf, const int seg_sz, + const __u8 __user *src_buf, const int req_len, + const zft_position *pos, const zft_volinfo *volume); +static int zftc_read(int *read_cnt, + __u8 __user *dst_buf, const int to_do, + const __u8 *src_buf, const int seg_sz, + const zft_position *pos, const zft_volinfo *volume); +static int zftc_seek(unsigned int new_block_pos, + zft_position *pos, const zft_volinfo *volume, + __u8 *buffer); +static void zftc_lock (void); +static void zftc_reset (void); +static void zftc_cleanup(void); +static void zftc_stats (void); + +/* compressed segment. This conforms to QIC-80-MC, Revision K. + * + * Rev. K applies to tapes with `fixed length format' which is + * indicated by format code 2,3 and 5. See below for format code 4 and 6 + * + * 2 bytes: offset of compression segment structure + * 29k > offset >= 29k-18: data from previous segment ens in this + * segment and no compressed block starts + * in this segment + * offset == 0: data from previous segment occupies entire + * segment and continues in next segment + * n bytes: remainder from previous segment + * + * Rev. K: + * 4 bytes: 4 bytes: files set byte offset + * Post Rev. K and QIC-3020/3020: + * 8 bytes: 8 bytes: files set byte offset + * 2 bytes: byte count N (amount of data following) + * bit 15 is set if data is compressed, bit 15 is not + * set if data is uncompressed + * N bytes: data (as much as specified in the byte count) + * 2 bytes: byte count N_1 of next cluster + * N_1 bytes: data of next cluset + * 2 bytes: byte count N_2 of next cluster + * N_2 bytes: ... + * + * Note that the `N' byte count accounts only for the bytes that in the + * current segment if the cluster spans to the next segment. + */ + +typedef struct +{ + int cmpr_pos; /* actual position in compression buffer */ + int cmpr_sz; /* what is left in the compression buffer + * when copying the compressed data to the + * deblock buffer + */ + unsigned int first_block; /* location of header information in + * this segment + */ + unsigned int count; /* amount of data of current block + * contained in current segment + */ + unsigned int offset; /* offset in current segment */ + unsigned int spans:1; /* might continue in next segment */ + unsigned int uncmpr; /* 0x8000 if this block contains + * uncompressed data + */ + __s64 foffs; /* file set byte offset, same as in + * compression map segment + */ +} cmpr_info; + +static cmpr_info cseg; /* static data. Must be kept uptodate and shared by + * read, write and seek functions + */ + +#define DUMP_CMPR_INFO(level, msg, info) \ + TRACE(level, msg "\n" \ + KERN_INFO "cmpr_pos : %d\n" \ + KERN_INFO "cmpr_sz : %d\n" \ + KERN_INFO "first_block: %d\n" \ + KERN_INFO "count : %d\n" \ + KERN_INFO "offset : %d\n" \ + KERN_INFO "spans : %d\n" \ + KERN_INFO "uncmpr : 0x%04x\n" \ + KERN_INFO "foffs : " LL_X, \ + (info)->cmpr_pos, (info)->cmpr_sz, (info)->first_block, \ + (info)->count, (info)->offset, (info)->spans == 1, \ + (info)->uncmpr, LL((info)->foffs)) + +/* dispatch compression segment info, return error code + * + * afterwards, cseg->offset points to start of data of the NEXT + * compressed block, and cseg->count contains the amount of data + * left in the actual compressed block. cseg->spans is set to 1 if + * the block is continued in the following segment. Otherwise it is + * set to 0. + */ +static int get_cseg (cmpr_info *cinfo, const __u8 *buff, + const unsigned int seg_sz, + const zft_volinfo *volume) +{ + TRACE_FUN(ft_t_flow); + + cinfo->first_block = GET2(buff, 0); + if (cinfo->first_block == 0) { /* data spans to next segment */ + cinfo->count = seg_sz - sizeof(__u16); + cinfo->offset = seg_sz; + cinfo->spans = 1; + } else { /* cluster definetely ends in this segment */ + if (cinfo->first_block > seg_sz) { + /* data corrupted */ + TRACE_ABORT(-EIO, ft_t_err, "corrupted data:\n" + KERN_INFO "segment size: %d\n" + KERN_INFO "first block : %d", + seg_sz, cinfo->first_block); + } + cinfo->count = cinfo->first_block - sizeof(__u16); + cinfo->offset = cinfo->first_block; + cinfo->spans = 0; + } + /* now get the offset the first block should have in the + * uncompressed data stream. + * + * For this magic `18' refer to CRF-3 standard or QIC-80MC, + * Rev. K. + */ + if ((seg_sz - cinfo->offset) > 18) { + if (volume->qic113) { /* > revision K */ + TRACE(ft_t_data_flow, "New QIC-113 compliance"); + cinfo->foffs = GET8(buff, cinfo->offset); + cinfo->offset += sizeof(__s64); + } else { + TRACE(/* ft_t_data_flow */ ft_t_noise, "pre QIC-113 version"); + cinfo->foffs = (__s64)GET4(buff, cinfo->offset); + cinfo->offset += sizeof(__u32); + } + } + if (cinfo->foffs > volume->size) { + TRACE_ABORT(-EIO, ft_t_err, "Inconsistency:\n" + KERN_INFO "offset in current volume: %d\n" + KERN_INFO "size of current volume : %d", + (int)(cinfo->foffs>>10), (int)(volume->size>>10)); + } + if (cinfo->cmpr_pos + cinfo->count > volume->blk_sz) { + TRACE_ABORT(-EIO, ft_t_err, "Inconsistency:\n" + KERN_INFO "block size : %d\n" + KERN_INFO "data record: %d", + volume->blk_sz, cinfo->cmpr_pos + cinfo->count); + } + DUMP_CMPR_INFO(ft_t_noise /* ft_t_any */, "", cinfo); + TRACE_EXIT 0; +} + +/* This one is called, when a new cluster starts in same segment. + * + * Note: if this is the first cluster in the current segment, we must + * not check whether there are more than 18 bytes available because + * this have already been done in get_cseg() and there may be less + * than 18 bytes available due to header information. + * + */ +static void get_next_cluster(cmpr_info *cluster, const __u8 *buff, + const int seg_sz, const int finish) +{ + TRACE_FUN(ft_t_flow); + + if (seg_sz - cluster->offset > 18 || cluster->foffs != 0) { + cluster->count = GET2(buff, cluster->offset); + cluster->uncmpr = cluster->count & 0x8000; + cluster->count -= cluster->uncmpr; + cluster->offset += sizeof(__u16); + cluster->foffs = 0; + if ((cluster->offset + cluster->count) < seg_sz) { + cluster->spans = 0; + } else if (cluster->offset + cluster->count == seg_sz) { + cluster->spans = !finish; + } else { + /* either an error or a volume written by an + * old version. If this is a data error, then we'll + * catch it later. + */ + TRACE(ft_t_data_flow, "Either error or old volume"); + cluster->spans = 1; + cluster->count = seg_sz - cluster->offset; + } + } else { + cluster->count = 0; + cluster->spans = 0; + cluster->foffs = 0; + } + DUMP_CMPR_INFO(ft_t_noise /* ft_t_any */ , "", cluster); + TRACE_EXIT; +} + +static void zftc_lock(void) +{ +} + +/* this function is needed for zftape_reset_position in zftape-io.c + */ +static void zftc_reset(void) +{ + TRACE_FUN(ft_t_flow); + + memset((void *)&cseg, '\0', sizeof(cseg)); + zftc_stats(); + TRACE_EXIT; +} + +static int cmpr_mem_initialized = 0; +static unsigned int alloc_blksz = 0; + +static int zft_allocate_cmpr_mem(unsigned int blksz) +{ + TRACE_FUN(ft_t_flow); + + if (cmpr_mem_initialized && blksz == alloc_blksz) { + TRACE_EXIT 0; + } + TRACE_CATCH(zft_vmalloc_once(&zftc_wrk_mem, CMPR_WRK_MEM_SIZE), + zftc_cleanup()); + TRACE_CATCH(zft_vmalloc_always(&zftc_buf, blksz + CMPR_OVERRUN), + zftc_cleanup()); + alloc_blksz = blksz; + TRACE_CATCH(zft_vmalloc_always(&zftc_scratch_buf, blksz+CMPR_OVERRUN), + zftc_cleanup()); + cmpr_mem_initialized = 1; + TRACE_EXIT 0; +} + +static void zftc_cleanup(void) +{ + TRACE_FUN(ft_t_flow); + + zft_vfree(&zftc_wrk_mem, CMPR_WRK_MEM_SIZE); + zft_vfree(&zftc_buf, alloc_blksz + CMPR_OVERRUN); + zft_vfree(&zftc_scratch_buf, alloc_blksz + CMPR_OVERRUN); + cmpr_mem_initialized = alloc_blksz = 0; + TRACE_EXIT; +} + +/***************************************************************************** + * * + * The following two functions "ftape_compress()" and * + * "ftape_uncompress()" are the interface to the actual compression * + * algorithm (i.e. they are calling the "compress()" function from * + * the lzrw3 package for now). These routines could quite easily be * + * changed to adopt another compression algorithm instead of lzrw3, * + * which currently is used. * + * * + *****************************************************************************/ + +/* called by zft_compress_write() to perform the compression. Must + * return the size of the compressed data. + * + * NOTE: The size of the compressed data should not exceed the size of + * the uncompressed data. Most compression algorithms have means + * to store data unchanged if the "compressed" data amount would + * exceed the original one. Mostly this is done by storing some + * flag-bytes in front of the compressed data to indicate if it + * is compressed or not. Thus the worst compression result + * length is the original length plus those flag-bytes. + * + * We don't want that, as the QIC-80 standard provides a means + * of marking uncompressed blocks by simply setting bit 15 of + * the compressed block's length. Thus a compessed block can + * have at most a length of 2^15-1 bytes. The QIC-80 standard + * restricts the block-length even further, allowing only 29k - + * 6 bytes. + * + * Currently, the maximum blocksize used by zftape is 28k. + * + * In short: don't exceed the length of the input-package, set + * bit 15 of the compressed size to 1 if you have copied data + * instead of compressing it. + */ +static int zft_compress(__u8 *in_buffer, unsigned int in_sz, __u8 *out_buffer) +{ + __s32 compressed_sz; + TRACE_FUN(ft_t_flow); + + + lzrw3_compress(COMPRESS_ACTION_COMPRESS, zftc_wrk_mem, + in_buffer, in_sz, out_buffer, &compressed_sz); + if (TRACE_LEVEL >= ft_t_info) { + /* the compiler will optimize this away when + * compiled with NO_TRACE_AT_ALL option + */ + TRACE(ft_t_data_flow, "\n" + KERN_INFO "before compression: %d bytes\n" + KERN_INFO "after compresison : %d bytes", + in_sz, + (int)(compressed_sz < 0 + ? -compressed_sz : compressed_sz)); + /* for statistical purposes + */ + zftc_wr_compressed += (compressed_sz < 0 + ? -compressed_sz : compressed_sz); + zftc_wr_uncompressed += in_sz; + } + TRACE_EXIT (int)compressed_sz; +} + +/* called by zft_compress_read() to decompress the data. Must + * return the size of the decompressed data for sanity checks + * (compared with zft_blk_sz) + * + * NOTE: Read the note for zft_compress() above! If bit 15 of the + * parameter in_sz is set, then the data in in_buffer isn't + * compressed, which must be handled by the un-compression + * algorithm. (I changed lzrw3 to handle this.) + * + * The parameter max_out_sz is needed to prevent buffer overruns when + * uncompressing corrupt data. + */ +static unsigned int zft_uncompress(__u8 *in_buffer, + int in_sz, + __u8 *out_buffer, + unsigned int max_out_sz) +{ + TRACE_FUN(ft_t_flow); + + lzrw3_compress(COMPRESS_ACTION_DECOMPRESS, zftc_wrk_mem, + in_buffer, (__s32)in_sz, + out_buffer, (__u32 *)&max_out_sz); + + if (TRACE_LEVEL >= ft_t_info) { + TRACE(ft_t_data_flow, "\n" + KERN_INFO "before decompression: %d bytes\n" + KERN_INFO "after decompression : %d bytes", + in_sz < 0 ? -in_sz : in_sz,(int)max_out_sz); + /* for statistical purposes + */ + zftc_rd_compressed += in_sz < 0 ? -in_sz : in_sz; + zftc_rd_uncompressed += max_out_sz; + } + TRACE_EXIT (unsigned int)max_out_sz; +} + +/* print some statistics about the efficiency of the compression to + * the kernel log + */ +static void zftc_stats(void) +{ + TRACE_FUN(ft_t_flow); + + if (TRACE_LEVEL < ft_t_info) { + TRACE_EXIT; + } + if (zftc_wr_uncompressed != 0) { + if (zftc_wr_compressed > (1<<14)) { + TRACE(ft_t_info, "compression statistics (writing):\n" + KERN_INFO " compr./uncmpr. : %3d %%", + (((zftc_wr_compressed>>10) * 100) + / (zftc_wr_uncompressed>>10))); + } else { + TRACE(ft_t_info, "compression statistics (writing):\n" + KERN_INFO " compr./uncmpr. : %3d %%", + ((zftc_wr_compressed * 100) + / zftc_wr_uncompressed)); + } + } + if (zftc_rd_uncompressed != 0) { + if (zftc_rd_compressed > (1<<14)) { + TRACE(ft_t_info, "compression statistics (reading):\n" + KERN_INFO " compr./uncmpr. : %3d %%", + (((zftc_rd_compressed>>10) * 100) + / (zftc_rd_uncompressed>>10))); + } else { + TRACE(ft_t_info, "compression statistics (reading):\n" + KERN_INFO " compr./uncmpr. : %3d %%", + ((zftc_rd_compressed * 100) + / zftc_rd_uncompressed)); + } + } + /* only print it once: */ + zftc_wr_uncompressed = + zftc_wr_compressed = + zftc_rd_uncompressed = + zftc_rd_compressed = 0; + TRACE_EXIT; +} + +/* start new compressed block + */ +static int start_new_cseg(cmpr_info *cluster, + char *dst_buf, + const zft_position *pos, + const unsigned int blk_sz, + const char *src_buf, + const int this_segs_sz, + const int qic113) +{ + int size_left; + int cp_cnt; + int buf_pos; + TRACE_FUN(ft_t_flow); + + size_left = this_segs_sz - sizeof(__u16) - cluster->cmpr_sz; + TRACE(ft_t_data_flow,"\n" + KERN_INFO "segment size : %d\n" + KERN_INFO "compressed_sz: %d\n" + KERN_INFO "size_left : %d", + this_segs_sz, cluster->cmpr_sz, size_left); + if (size_left > 18) { /* start a new cluseter */ + cp_cnt = cluster->cmpr_sz; + cluster->cmpr_sz = 0; + buf_pos = cp_cnt + sizeof(__u16); + PUT2(dst_buf, 0, buf_pos); + + if (qic113) { + __s64 foffs = pos->volume_pos; + if (cp_cnt) foffs += (__s64)blk_sz; + + TRACE(ft_t_data_flow, "new style QIC-113 header"); + PUT8(dst_buf, buf_pos, foffs); + buf_pos += sizeof(__s64); + } else { + __u32 foffs = (__u32)pos->volume_pos; + if (cp_cnt) foffs += (__u32)blk_sz; + + TRACE(ft_t_data_flow, "old style QIC-80MC header"); + PUT4(dst_buf, buf_pos, foffs); + buf_pos += sizeof(__u32); + } + } else if (size_left >= 0) { + cp_cnt = cluster->cmpr_sz; + cluster->cmpr_sz = 0; + buf_pos = cp_cnt + sizeof(__u16); + PUT2(dst_buf, 0, buf_pos); + /* zero unused part of segment. */ + memset(dst_buf + buf_pos, '\0', size_left); + buf_pos = this_segs_sz; + } else { /* need entire segment and more space */ + PUT2(dst_buf, 0, 0); + cp_cnt = this_segs_sz - sizeof(__u16); + cluster->cmpr_sz -= cp_cnt; + buf_pos = this_segs_sz; + } + memcpy(dst_buf + sizeof(__u16), src_buf + cluster->cmpr_pos, cp_cnt); + cluster->cmpr_pos += cp_cnt; + TRACE_EXIT buf_pos; +} + +/* return-value: the number of bytes removed from the user-buffer + * `src_buf' or error code + * + * int *write_cnt : how much actually has been moved to the + * dst_buf. Need not be initialized when + * function returns with an error code + * (negativ return value) + * __u8 *dst_buf : kernel space buffer where the has to be + * copied to. The contents of this buffers + * goes to a specific segment. + * const int seg_sz : the size of the segment dst_buf will be + * copied to. + * const zft_position *pos : struct containing the coordinates in + * the current volume (byte position, + * segment id of current segment etc) + * const zft_volinfo *volume: information about the current volume, + * size etc. + * const __u8 *src_buf : user space buffer that contains the + * data the user wants to be written to + * tape. + * const int req_len : the amount of data the user wants to be + * written to tape. + */ +static int zftc_write(int *write_cnt, + __u8 *dst_buf, const int seg_sz, + const __u8 __user *src_buf, const int req_len, + const zft_position *pos, const zft_volinfo *volume) +{ + int req_len_left = req_len; + int result; + int len_left; + int buf_pos_write = pos->seg_byte_pos; + TRACE_FUN(ft_t_flow); + + /* Note: we do not unlock the module because + * there are some values cached in that `cseg' variable. We + * don't don't want to use this information when being + * unloaded by kerneld even when the tape is full or when we + * cannot allocate enough memory. + */ + if (pos->tape_pos > (volume->size-volume->blk_sz-ZFT_CMPR_OVERHEAD)) { + TRACE_EXIT -ENOSPC; + } + if (zft_allocate_cmpr_mem(volume->blk_sz) < 0) { + /* should we unlock the module? But it shouldn't + * be locked anyway ... + */ + TRACE_EXIT -ENOMEM; + } + if (buf_pos_write == 0) { /* fill a new segment */ + *write_cnt = buf_pos_write = start_new_cseg(&cseg, + dst_buf, + pos, + volume->blk_sz, + zftc_buf, + seg_sz, + volume->qic113); + if (cseg.cmpr_sz == 0 && cseg.cmpr_pos != 0) { + req_len_left -= result = volume->blk_sz; + cseg.cmpr_pos = 0; + } else { + result = 0; + } + } else { + *write_cnt = result = 0; + } + + len_left = seg_sz - buf_pos_write; + while ((req_len_left > 0) && (len_left > 18)) { + /* now we have some size left for a new compressed + * block. We know, that the compression buffer is + * empty (else there wouldn't be any space left). + */ + if (copy_from_user(zftc_scratch_buf, src_buf + result, + volume->blk_sz) != 0) { + TRACE_EXIT -EFAULT; + } + req_len_left -= volume->blk_sz; + cseg.cmpr_sz = zft_compress(zftc_scratch_buf, volume->blk_sz, + zftc_buf); + if (cseg.cmpr_sz < 0) { + cseg.uncmpr = 0x8000; + cseg.cmpr_sz = -cseg.cmpr_sz; + } else { + cseg.uncmpr = 0; + } + /* increment "result" iff we copied the entire + * compressed block to the zft_deblock_buf + */ + len_left -= sizeof(__u16); + if (len_left >= cseg.cmpr_sz) { + len_left -= cseg.count = cseg.cmpr_sz; + cseg.cmpr_pos = cseg.cmpr_sz = 0; + result += volume->blk_sz; + } else { + cseg.cmpr_sz -= + cseg.cmpr_pos = + cseg.count = len_left; + len_left = 0; + } + PUT2(dst_buf, buf_pos_write, cseg.uncmpr | cseg.count); + buf_pos_write += sizeof(__u16); + memcpy(dst_buf + buf_pos_write, zftc_buf, cseg.count); + buf_pos_write += cseg.count; + *write_cnt += cseg.count + sizeof(__u16); + FT_SIGNAL_EXIT(_DONT_BLOCK); + } + /* erase the remainder of the segment if less than 18 bytes + * left (18 bytes is due to the QIC-80 standard) + */ + if (len_left <= 18) { + memset(dst_buf + buf_pos_write, '\0', len_left); + (*write_cnt) += len_left; + } + TRACE(ft_t_data_flow, "returning %d", result); + TRACE_EXIT result; +} + +/* out: + * + * int *read_cnt: the number of bytes we removed from the zft_deblock_buf + * (result) + * int *to_do : the remaining size of the read-request. + * + * in: + * + * char *buff : buff is the address of the upper part of the user + * buffer, that hasn't been filled with data yet. + + * int buf_pos_read : copy of from _ftape_read() + * int buf_len_read : copy of buf_len_rd from _ftape_read() + * char *zft_deblock_buf: zft_deblock_buf + * unsigned short blk_sz: the block size valid for this volume, may differ + * from zft_blk_sz. + * int finish: if != 0 means that this is the last segment belonging + * to this volume + * returns the amount of data actually copied to the user-buffer + * + * to_do MUST NOT SHRINK except to indicate an EOF. In this case *to_do has to + * be set to 0 + */ +static int zftc_read (int *read_cnt, + __u8 __user *dst_buf, const int to_do, + const __u8 *src_buf, const int seg_sz, + const zft_position *pos, const zft_volinfo *volume) +{ + int uncompressed_sz; + int result = 0; + int remaining = to_do; + TRACE_FUN(ft_t_flow); + + TRACE_CATCH(zft_allocate_cmpr_mem(volume->blk_sz),); + if (pos->seg_byte_pos == 0) { + /* new segment just read + */ + TRACE_CATCH(get_cseg(&cseg, src_buf, seg_sz, volume), + *read_cnt = 0); + memcpy(zftc_buf + cseg.cmpr_pos, src_buf + sizeof(__u16), + cseg.count); + cseg.cmpr_pos += cseg.count; + *read_cnt = cseg.offset; + DUMP_CMPR_INFO(ft_t_noise /* ft_t_any */, "", &cseg); + } else { + *read_cnt = 0; + } + /* loop and uncompress until user buffer full or + * deblock-buffer empty + */ + TRACE(ft_t_data_flow, "compressed_sz: %d, compos : %d, *read_cnt: %d", + cseg.cmpr_sz, cseg.cmpr_pos, *read_cnt); + while ((cseg.spans == 0) && (remaining > 0)) { + if (cseg.cmpr_pos != 0) { /* cmpr buf is not empty */ + uncompressed_sz = + zft_uncompress(zftc_buf, + cseg.uncmpr == 0x8000 ? + -cseg.cmpr_pos : cseg.cmpr_pos, + zftc_scratch_buf, + volume->blk_sz); + if (uncompressed_sz != volume->blk_sz) { + *read_cnt = 0; + TRACE_ABORT(-EIO, ft_t_warn, + "Uncompressed blk (%d) != blk size (%d)", + uncompressed_sz, volume->blk_sz); + } + if (copy_to_user(dst_buf + result, + zftc_scratch_buf, + uncompressed_sz) != 0 ) { + TRACE_EXIT -EFAULT; + } + remaining -= uncompressed_sz; + result += uncompressed_sz; + cseg.cmpr_pos = 0; + } + if (remaining > 0) { + get_next_cluster(&cseg, src_buf, seg_sz, + volume->end_seg == pos->seg_pos); + if (cseg.count != 0) { + memcpy(zftc_buf, src_buf + cseg.offset, + cseg.count); + cseg.cmpr_pos = cseg.count; + cseg.offset += cseg.count; + *read_cnt += cseg.count + sizeof(__u16); + } else { + remaining = 0; + } + } + TRACE(ft_t_data_flow, "\n" + KERN_INFO "compressed_sz: %d\n" + KERN_INFO "compos : %d\n" + KERN_INFO "*read_cnt : %d", + cseg.cmpr_sz, cseg.cmpr_pos, *read_cnt); + } + if (seg_sz - cseg.offset <= 18) { + *read_cnt += seg_sz - cseg.offset; + TRACE(ft_t_data_flow, "expanding read cnt to: %d", *read_cnt); + } + TRACE(ft_t_data_flow, "\n" + KERN_INFO "segment size : %d\n" + KERN_INFO "read count : %d\n" + KERN_INFO "buf_pos_read : %d\n" + KERN_INFO "remaining : %d", + seg_sz, *read_cnt, pos->seg_byte_pos, + seg_sz - *read_cnt - pos->seg_byte_pos); + TRACE(ft_t_data_flow, "returning: %d", result); + TRACE_EXIT result; +} + +/* seeks to the new data-position. Reads sometimes a segment. + * + * start_seg and end_seg give the boundaries of the current volume + * blk_sz is the blk_sz of the current volume as stored in the + * volume label + * + * We don't allow blocksizes less than 1024 bytes, therefore we don't need + * a 64 bit argument for new_block_pos. + */ + +static int seek_in_segment(const unsigned int to_do, cmpr_info *c_info, + const char *src_buf, const int seg_sz, + const int seg_pos, const zft_volinfo *volume); +static int slow_seek_forward_until_error(const unsigned int distance, + cmpr_info *c_info, zft_position *pos, + const zft_volinfo *volume, __u8 *buf); +static int search_valid_segment(unsigned int segment, + const unsigned int end_seg, + const unsigned int max_foffs, + zft_position *pos, cmpr_info *c_info, + const zft_volinfo *volume, __u8 *buf); +static int slow_seek_forward(unsigned int dest, cmpr_info *c_info, + zft_position *pos, const zft_volinfo *volume, + __u8 *buf); +static int compute_seg_pos(unsigned int dest, zft_position *pos, + const zft_volinfo *volume); + +#define ZFT_SLOW_SEEK_THRESHOLD 10 /* segments */ +#define ZFT_FAST_SEEK_MAX_TRIALS 10 /* times */ +#define ZFT_FAST_SEEK_BACKUP 10 /* segments */ + +static int zftc_seek(unsigned int new_block_pos, + zft_position *pos, const zft_volinfo *volume, __u8 *buf) +{ + unsigned int dest; + int limit; + int distance; + int result = 0; + int seg_dist; + int new_seg; + int old_seg = 0; + int fast_seek_trials = 0; + TRACE_FUN(ft_t_flow); + + if (new_block_pos == 0) { + pos->seg_pos = volume->start_seg; + pos->seg_byte_pos = 0; + pos->volume_pos = 0; + zftc_reset(); + TRACE_EXIT 0; + } + dest = new_block_pos * (volume->blk_sz >> 10); + distance = dest - (pos->volume_pos >> 10); + while (distance != 0) { + seg_dist = compute_seg_pos(dest, pos, volume); + TRACE(ft_t_noise, "\n" + KERN_INFO "seg_dist: %d\n" + KERN_INFO "distance: %d\n" + KERN_INFO "dest : %d\n" + KERN_INFO "vpos : %d\n" + KERN_INFO "seg_pos : %d\n" + KERN_INFO "trials : %d", + seg_dist, distance, dest, + (unsigned int)(pos->volume_pos>>10), pos->seg_pos, + fast_seek_trials); + if (distance > 0) { + if (seg_dist < 0) { + TRACE(ft_t_bug, "BUG: distance %d > 0, " + "segment difference %d < 0", + distance, seg_dist); + result = -EIO; + break; + } + new_seg = pos->seg_pos + seg_dist; + if (new_seg > volume->end_seg) { + new_seg = volume->end_seg; + } + if (old_seg == new_seg || /* loop */ + seg_dist <= ZFT_SLOW_SEEK_THRESHOLD || + fast_seek_trials >= ZFT_FAST_SEEK_MAX_TRIALS) { + TRACE(ft_t_noise, "starting slow seek:\n" + KERN_INFO "fast seek failed too often: %s\n" + KERN_INFO "near target position : %s\n" + KERN_INFO "looping between two segs : %s", + (fast_seek_trials >= + ZFT_FAST_SEEK_MAX_TRIALS) + ? "yes" : "no", + (seg_dist <= ZFT_SLOW_SEEK_THRESHOLD) + ? "yes" : "no", + (old_seg == new_seg) + ? "yes" : "no"); + result = slow_seek_forward(dest, &cseg, + pos, volume, buf); + break; + } + old_seg = new_seg; + limit = volume->end_seg; + fast_seek_trials ++; + for (;;) { + result = search_valid_segment(new_seg, limit, + volume->size, + pos, &cseg, + volume, buf); + if (result == 0 || result == -EINTR) { + break; + } + if (new_seg == volume->start_seg) { + result = -EIO; /* set errror + * condition + */ + break; + } + limit = new_seg; + new_seg -= ZFT_FAST_SEEK_BACKUP; + if (new_seg < volume->start_seg) { + new_seg = volume->start_seg; + } + } + if (result < 0) { + TRACE(ft_t_warn, + "Couldn't find a readable segment"); + break; + } + } else /* if (distance < 0) */ { + if (seg_dist > 0) { + TRACE(ft_t_bug, "BUG: distance %d < 0, " + "segment difference %d >0", + distance, seg_dist); + result = -EIO; + break; + } + new_seg = pos->seg_pos + seg_dist; + if (fast_seek_trials > 0 && seg_dist == 0) { + /* this avoids sticking to the same + * segment all the time. On the other hand: + * if we got here for the first time, and the + * deblock_buffer still contains a valid + * segment, then there is no need to skip to + * the previous segment if the desired position + * is inside this segment. + */ + new_seg --; + } + if (new_seg < volume->start_seg) { + new_seg = volume->start_seg; + } + limit = pos->seg_pos; + fast_seek_trials ++; + for (;;) { + result = search_valid_segment(new_seg, limit, + pos->volume_pos, + pos, &cseg, + volume, buf); + if (result == 0 || result == -EINTR) { + break; + } + if (new_seg == volume->start_seg) { + result = -EIO; /* set errror + * condition + */ + break; + } + limit = new_seg; + new_seg -= ZFT_FAST_SEEK_BACKUP; + if (new_seg < volume->start_seg) { + new_seg = volume->start_seg; + } + } + if (result < 0) { + TRACE(ft_t_warn, + "Couldn't find a readable segment"); + break; + } + } + distance = dest - (pos->volume_pos >> 10); + } + TRACE_EXIT result; +} + + +/* advance inside the given segment at most to_do bytes. + * of kilobytes moved + */ + +static int seek_in_segment(const unsigned int to_do, + cmpr_info *c_info, + const char *src_buf, + const int seg_sz, + const int seg_pos, + const zft_volinfo *volume) +{ + int result = 0; + int blk_sz = volume->blk_sz >> 10; + int remaining = to_do; + TRACE_FUN(ft_t_flow); + + if (c_info->offset == 0) { + /* new segment just read + */ + TRACE_CATCH(get_cseg(c_info, src_buf, seg_sz, volume),); + c_info->cmpr_pos += c_info->count; + DUMP_CMPR_INFO(ft_t_noise, "", c_info); + } + /* loop and uncompress until user buffer full or + * deblock-buffer empty + */ + TRACE(ft_t_noise, "compressed_sz: %d, compos : %d", + c_info->cmpr_sz, c_info->cmpr_pos); + while (c_info->spans == 0 && remaining > 0) { + if (c_info->cmpr_pos != 0) { /* cmpr buf is not empty */ + result += blk_sz; + remaining -= blk_sz; + c_info->cmpr_pos = 0; + } + if (remaining > 0) { + get_next_cluster(c_info, src_buf, seg_sz, + volume->end_seg == seg_pos); + if (c_info->count != 0) { + c_info->cmpr_pos = c_info->count; + c_info->offset += c_info->count; + } else { + break; + } + } + /* Allow escape from this loop on signal! + */ + FT_SIGNAL_EXIT(_DONT_BLOCK); + DUMP_CMPR_INFO(ft_t_noise, "", c_info); + TRACE(ft_t_noise, "to_do: %d", remaining); + } + if (seg_sz - c_info->offset <= 18) { + c_info->offset = seg_sz; + } + TRACE(ft_t_noise, "\n" + KERN_INFO "segment size : %d\n" + KERN_INFO "buf_pos_read : %d\n" + KERN_INFO "remaining : %d", + seg_sz, c_info->offset, + seg_sz - c_info->offset); + TRACE_EXIT result; +} + +static int slow_seek_forward_until_error(const unsigned int distance, + cmpr_info *c_info, + zft_position *pos, + const zft_volinfo *volume, + __u8 *buf) +{ + unsigned int remaining = distance; + int seg_sz; + int seg_pos; + int result; + TRACE_FUN(ft_t_flow); + + seg_pos = pos->seg_pos; + do { + TRACE_CATCH(seg_sz = zft_fetch_segment(seg_pos, buf, + FT_RD_AHEAD),); + /* now we have the contents of the actual segment in + * the deblock buffer + */ + TRACE_CATCH(result = seek_in_segment(remaining, c_info, buf, + seg_sz, seg_pos,volume),); + remaining -= result; + pos->volume_pos += result<<10; + pos->seg_pos = seg_pos; + pos->seg_byte_pos = c_info->offset; + seg_pos ++; + if (seg_pos <= volume->end_seg && c_info->offset == seg_sz) { + pos->seg_pos ++; + pos->seg_byte_pos = 0; + c_info->offset = 0; + } + /* Allow escape from this loop on signal! + */ + FT_SIGNAL_EXIT(_DONT_BLOCK); + TRACE(ft_t_noise, "\n" + KERN_INFO "remaining: %d\n" + KERN_INFO "seg_pos: %d\n" + KERN_INFO "end_seg: %d\n" + KERN_INFO "result: %d", + remaining, seg_pos, volume->end_seg, result); + } while (remaining > 0 && seg_pos <= volume->end_seg); + TRACE_EXIT 0; +} + +/* return segment id of next segment containing valid data, -EIO otherwise + */ +static int search_valid_segment(unsigned int segment, + const unsigned int end_seg, + const unsigned int max_foffs, + zft_position *pos, + cmpr_info *c_info, + const zft_volinfo *volume, + __u8 *buf) +{ + cmpr_info tmp_info; + int seg_sz; + TRACE_FUN(ft_t_flow); + + memset(&tmp_info, 0, sizeof(cmpr_info)); + while (segment <= end_seg) { + FT_SIGNAL_EXIT(_DONT_BLOCK); + TRACE(ft_t_noise, + "Searching readable segment between %d and %d", + segment, end_seg); + seg_sz = zft_fetch_segment(segment, buf, FT_RD_AHEAD); + if ((seg_sz > 0) && + (get_cseg (&tmp_info, buf, seg_sz, volume) >= 0) && + (tmp_info.foffs != 0 || segment == volume->start_seg)) { + if ((tmp_info.foffs>>10) > max_foffs) { + TRACE_ABORT(-EIO, ft_t_noise, "\n" + KERN_INFO "cseg.foff: %d\n" + KERN_INFO "dest : %d", + (int)(tmp_info.foffs >> 10), + max_foffs); + } + DUMP_CMPR_INFO(ft_t_noise, "", &tmp_info); + *c_info = tmp_info; + pos->seg_pos = segment; + pos->volume_pos = c_info->foffs; + pos->seg_byte_pos = c_info->offset; + TRACE(ft_t_noise, "found segment at %d", segment); + TRACE_EXIT 0; + } + segment++; + } + TRACE_EXIT -EIO; +} + +static int slow_seek_forward(unsigned int dest, + cmpr_info *c_info, + zft_position *pos, + const zft_volinfo *volume, + __u8 *buf) +{ + unsigned int distance; + int result = 0; + TRACE_FUN(ft_t_flow); + + distance = dest - (pos->volume_pos >> 10); + while ((distance > 0) && + (result = slow_seek_forward_until_error(distance, + c_info, + pos, + volume, + buf)) < 0) { + if (result == -EINTR) { + break; + } + TRACE(ft_t_noise, "seg_pos: %d", pos->seg_pos); + /* the failing segment is either pos->seg_pos or + * pos->seg_pos + 1. There is no need to further try + * that segment, because ftape_read_segment() already + * has tried very much to read it. So we start with + * following segment, which is pos->seg_pos + 1 + */ + if(search_valid_segment(pos->seg_pos+1, volume->end_seg, dest, + pos, c_info, + volume, buf) < 0) { + TRACE(ft_t_noise, "search_valid_segment() failed"); + result = -EIO; + break; + } + distance = dest - (pos->volume_pos >> 10); + result = 0; + TRACE(ft_t_noise, "segment: %d", pos->seg_pos); + /* found valid segment, retry the seek */ + } + TRACE_EXIT result; +} + +static int compute_seg_pos(const unsigned int dest, + zft_position *pos, + const zft_volinfo *volume) +{ + int segment; + int distance = dest - (pos->volume_pos >> 10); + unsigned int raw_size; + unsigned int virt_size; + unsigned int factor; + TRACE_FUN(ft_t_flow); + + if (distance >= 0) { + raw_size = volume->end_seg - pos->seg_pos + 1; + virt_size = ((unsigned int)(volume->size>>10) + - (unsigned int)(pos->volume_pos>>10) + + FT_SECTORS_PER_SEGMENT - FT_ECC_SECTORS - 1); + virt_size /= FT_SECTORS_PER_SEGMENT - FT_ECC_SECTORS; + if (virt_size == 0 || raw_size == 0) { + TRACE_EXIT 0; + } + if (raw_size >= (1<<25)) { + factor = raw_size/(virt_size>>7); + } else { + factor = (raw_size<<7)/virt_size; + } + segment = distance/(FT_SECTORS_PER_SEGMENT-FT_ECC_SECTORS); + segment = (segment * factor)>>7; + } else { + raw_size = pos->seg_pos - volume->start_seg + 1; + virt_size = ((unsigned int)(pos->volume_pos>>10) + + FT_SECTORS_PER_SEGMENT - FT_ECC_SECTORS - 1); + virt_size /= FT_SECTORS_PER_SEGMENT - FT_ECC_SECTORS; + if (virt_size == 0 || raw_size == 0) { + TRACE_EXIT 0; + } + if (raw_size >= (1<<25)) { + factor = raw_size/(virt_size>>7); + } else { + factor = (raw_size<<7)/virt_size; + } + segment = distance/(FT_SECTORS_PER_SEGMENT-FT_ECC_SECTORS); + } + TRACE(ft_t_noise, "factor: %d/%d", factor, 1<<7); + TRACE_EXIT segment; +} + +static struct zft_cmpr_ops cmpr_ops = { + zftc_write, + zftc_read, + zftc_seek, + zftc_lock, + zftc_reset, + zftc_cleanup +}; + +int zft_compressor_init(void) +{ + TRACE_FUN(ft_t_flow); + +#ifdef MODULE + printk(KERN_INFO "zftape compressor v1.00a 970514 for " FTAPE_VERSION "\n"); + if (TRACE_LEVEL >= ft_t_info) { + printk( +KERN_INFO "(c) 1997 Claus-Justus Heine (claus@momo.math.rwth-aachen.de)\n" +KERN_INFO "Compressor for zftape (lzrw3 algorithm)\n"); + } +#else /* !MODULE */ + /* print a short no-nonsense boot message */ + printk("zftape compressor v1.00a 970514\n"); + printk("For use with " FTAPE_VERSION "\n"); +#endif /* MODULE */ + TRACE(ft_t_info, "zft_compressor_init @ 0x%p", zft_compressor_init); + TRACE(ft_t_info, "installing compressor for zftape ..."); + TRACE_CATCH(zft_cmpr_register(&cmpr_ops),); + TRACE_EXIT 0; +} + +#ifdef MODULE + +MODULE_AUTHOR( + "(c) 1996, 1997 Claus-Justus Heine (claus@momo.math.rwth-aachen.de"); +MODULE_DESCRIPTION( +"Compression routines for zftape. Uses the lzrw3 algorithm by Ross Williams"); +MODULE_LICENSE("GPL"); + +/* Called by modules package when installing the driver + */ +int init_module(void) +{ + return zft_compressor_init(); +} + +#endif /* MODULE */ diff --git a/drivers/char/ftape/compressor/zftape-compress.h b/drivers/char/ftape/compressor/zftape-compress.h new file mode 100644 index 000000000000..f200741e33bf --- /dev/null +++ b/drivers/char/ftape/compressor/zftape-compress.h @@ -0,0 +1,83 @@ +#ifndef _ZFTAPE_COMPRESS_H +#define _ZFTAPE_COMPRESS_H +/* + * Copyright (c) 1994-1997 Claus-Justus Heine + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2, or (at + your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; see the file COPYING. If not, write to + the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, + USA. + + * + * $Source: /homes/cvs/ftape-stacked/ftape/compressor/zftape-compress.h,v $ + * $Revision: 1.1 $ + * $Date: 1997/10/05 19:12:32 $ + * + * This file contains macros and definitions for zftape's + * builtin compression code. + * + */ + +#include "../zftape/zftape-buffers.h" +#include "../zftape/zftape-vtbl.h" +#include "../compressor/lzrw3.h" + +/* CMPR_WRK_MEM_SIZE gives the size of the compression wrk_mem */ +/* I got these out of lzrw3.c */ +#define U(X) ((__u32) X) +#define SIZE_P_BYTE (U(sizeof(__u8 *))) +#define ALIGNMENT_FUDGE (U(16)) + +#define CMPR_WRK_MEM_SIZE (U(4096)*(SIZE_P_BYTE) + ALIGNMENT_FUDGE) + +/* the maximum number of bytes the size of the "compressed" data can + * exceed the uncompressed data. As it is quite useless to compress + * data twice it is sometimes the case that it is more efficient to + * copy a block of data but to feed it to the "compression" + * algorithm. In this case there are some flag bytes or the like + * proceding the "compressed" data. THAT MUST NOT BE THE CASE for the + * algorithm we use for this driver. Instead, the high bit 15 of + * compressed_size: + * + * compressed_size = ftape_compress() + * + * must be set in such a case. + * + * Nevertheless, it might also be as for lzrw3 that there is an + * "intermediate" overrun that exceeds the amount of the compressed + * data that is actually produced. During the algorithm we need in the + * worst case MAX_CMP_GROUP bytes more than the input-size. + */ +#define MAX_CMP_GROUP (2+16*2) /* from lzrw3.c */ + +#define CMPR_OVERRUN MAX_CMP_GROUP /* during compression */ + +/****************************************************/ + +#define CMPR_BUFFER_SIZE (MAX_BLOCK_SIZE + CMPR_OVERRUN) + +/* the compression map stores the byte offset compressed blocks within + * the current volume for catridges with format code 2,3 and 5 + * (and old versions of zftape) and the offset measured in kilobytes for + * format code 4 and 6. This gives us a possible max. size of a + * compressed volume of 1024*4GIG which should be enough. + */ +typedef __u32 CmprMap; + +/* globals + */ + +/* exported functions + */ + +#endif /* _ZFTAPE_COMPRESS_H */ |