aboutsummaryrefslogtreecommitdiffstats
path: root/include/lzsscomprs.h
blob: 0f352e7a9c7e65cda942973c3aa83548af2caeb2 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/******************************************************************************
 *  lzsscomprs.h   - definition of Class SWCompress used for data compression
 *
 * $Id: lzsscomprs.h,v 1.3 2001/02/09 15:38:51 jansorg Exp $
 *
 * Copyright 1998 CrossWire Bible Society (http://www.crosswire.org)
 *	CrossWire Bible Society
 *	P. O. Box 2528
 *	Tempe, AZ  85280-2528
 *
 * 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 version 2.
 *
 * 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.
 *
 */

#ifndef LZSSCOMPRS_H
#define LZSSCOMPRS_H

#include <swcomprs.h>

#include <defs.h>

// The following are constant sizes used by the compression algorithm.
//
//  N         - This is the size of the ring buffer.  It is set
//              to 4K.  It is important to note that a position
//              within the ring buffer requires 12 bits.  
//
//  F         - This is the maximum length of a character sequence
//              that can be taken from the ring buffer.  It is set
//              to 18.  Note that a length must be 3 before it is
//              worthwhile to store a position/length pair, so the
//              length can be encoded in only 4 bits.  Or, put yet
//              another way, it is not necessary to encode a length
//              of 0-18, it is necessary to encode a length of
//              3-18, which requires 4 bits.
//              
//  THRESHOLD - It takes 2 bytes to store an offset and
//              a length.  If a character sequence only
//              requires 1 or 2 characters to store 
//              uncompressed, then it is better to store
//              it uncompressed than as an offset into
//              the ring buffer.
//
// Note that the 12 bits used to store the position and the 4 bits
// used to store the length equal a total of 16 bits, or 2 bytes.

#define N		4096
#define F		18
#define THRESHOLD	3
#define NOT_USED	N



class SWDLLEXPORT LZSSCompress:public SWCompress
{
  static unsigned char m_ring_buffer[N + F - 1];
  static short int m_match_position;
  static short int m_match_length;
  static short int m_lson[N + 1];
  static short int m_rson[N + 257];
  static short int m_dad[N + 1];
  void InitTree ();
  void InsertNode (short int Pos);
  void DeleteNode (short int Node);
public:
    LZSSCompress ();
    virtual ~ LZSSCompress ();
  virtual void Encode (void);
  virtual void Decode (void);
};

#endif