zftape-compress.c

linux-2.6.15.6

/*
 *      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;