lzv1/lzv1.c

filter: Statementstmt 96.3% 80 / 83 Branchbran 91.6% 55 / 60 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 94.4% 135 / 143 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« LZV1.xs ↑ Summary blib/lib/Compress/LZV1.pm »
1 /***********************************************************************
2 **
3 ** lzv.c -- an extremly fast compression/decompression-method
4 **
5 ** Written by Hermann Vogt
6 **
7 ** v 0.5 -- 00/04/10 fix unaligned access (Marc)
8 ** v 0.4 -- 00/03/25 adapted for PApp by Marc Lehmann <pcg@goof.com>
9 ** v 0.3 -- 94/03/08 aCembler version of rLZV built in.
10 ** v 0.2 -- 94/03/04 Changes for usage with DouBle 0.2 built in.
11 ** v 0.1 -- 94/03/01 Intensivly tested, removed all known bugs.
12 ** v 0.0 -- 94/02/21 First Version.
13 **
14 ** Copyright (c) 1994 Hermann Vogt. Redistribution of this file is
15 ** permitted under the GNU Public Licence.
16 **
17 ** The method presented here is faster and compresses better
18 ** than lzrw1 and lzrw1-a. I named it lzv for "Lev-Zimpel-Vogt".
19 ** It uses ideas introduced by Ross Williams in his algorithm lzrw1
20 ** [R. N. Williams (1991): "An Extremly Fast ZIV-Lempel Data
21 ** Compression Algorithm", Proceedings IEEE Data Compression
22 ** Conference, Snowbird, Utah, 362-371] and by Fiala and Green in their
23 ** algorithm a1 [E. R. Fiala, D. H. Greene (1989): "Data Compression
24 ** with Finite Windows", Communications of the ACM, 4, 490-505].
25 ** Because lzv differs strongly from both, I hope there will be no
26 ** patent problems. The hashing-method has been stolen from Jean-loup
27 ** Gailly's (patent free) gzip.
28 **
29 ** KNOWN PROBLEMS:
30 ** - My english is very bad.
31 ** - Badly commented. (I hope this will be better in the next
32 ** version.)
33 ** - I'm not sure if lzv is free from patent problems.
34 **
35 ***********************************************************************/
36  
37 #define HSIZE 0x4000
38 #define HMASK 0x3fff
39 #define HSHIFT 5
40  
41 #define MLL 32 /* Maximum len of chain of literals */
42 #define MML (8+256) /* Maximum len of match */
43 #define MOFF 8191 /* Maximum offset */
44 #define HSIZ 16384 /* Size of Hashtable */
45  
46 /* ugly type names */
47  
48 typedef unsigned char uch;
49 typedef unsigned short ush;
50 typedef unsigned int uit;
51  
52 #undef ONLY_64K /* 64k-max encoder is faster */
53 /* but only veeeery slightly */
54  
55 /* unconditionally aligning does not cost much much, so do it if unsure */
56 #define align_ushort !defined(__i386)
57  
58 static int
59 9 wLZV1 (uch * in, uch * out, ush * heap, int len, int out_len)
60 {
61 uit hval, op, ip, l_len, m_pos, m_off, m_len, maxlen;
62 9 ush *lzv1_htab = heap;
63  
64 9 maxlen = out_len;
65 9 hval = ((in[0] << 5) ^ in[1]) & (HSIZ - 1);
66 9 ip = op = l_len = 0;
67  
68 do
69 {
70 211177 hval = ((hval << 5) ^ in[ip + 2]) & (HSIZ - 1);
71 211177 m_pos = lzv1_htab[hval];
72 211177 lzv1_htab[hval] = ip;
73  
74 #ifndef ONLY_64K
75 /*
76 * If you want to compress more than 64K, uncomment
77 * the following lines.
78 */
79  
80 211177 m_pos = (ip & ~0xffff) + m_pos;
81 211177 ▶ if (m_pos >= ip && m_pos >= 0x10000)
Branch: 2 branches
BranchTrueFalseTotal
if (m_pos >= ip && m_pos >= 0x10000) 15963 195214 211177
if (m_pos >= ip && m_pos >= 0x10000) 11170 4793 15963
82 11170 m_pos -= 0x10000;
83 #endif
84  
85 211177 ▶ if (m_pos < ip
Branch: 1 branch
BranchTrueFalseTotal
if (m_pos < ip 206384 4793 211177
86 206384 ▶ && in[m_pos ] == in[ip ]
Branch: 1 branch
BranchTrueFalseTotal
&& in[m_pos ] == in[ip ] 118768 87616 206384
87 118768 ▶ && (m_off = ip - m_pos - 1) <= MOFF
Branch: 1 branch
BranchTrueFalseTotal
&& (m_off = ip - m_pos - 1) <= MOFF 116985 1783 118768
88 116985 ▶ && ip + 4 < len
Branch: 1 branch
BranchTrueFalseTotal
&& ip + 4 < len 116983 2 116985
89 #if align_ushort
90 116983 ▶ && in[m_pos + 1] == in[ip + 1]
Branch: 1 branch
BranchTrueFalseTotal
&& in[m_pos + 1] == in[ip + 1] 113152 3831 116983
91 113152 ▶ && in[m_pos + 2] == in[ip + 2]
Branch: 1 branch
BranchTrueFalseTotal
&& in[m_pos + 2] == in[ip + 2] 113144 8 113152
92 #else
93 && *(ush *) (in + m_pos + 1) == *(ush *) (in + ip + 1)
94 #endif
95 )
96 113143 {
97 /* We have found a match */
98 113144 uit look = len - ip - 2;
99 113144 ▶ if (look > MML)
Branch: 1 branch
BranchTrueFalseTotal
if (look > MML) 112970 174 113144
100 112970 look = MML;
101 113144 m_len = 2;
102  
103 do
104 {
105 665818 m_len++;
106 }
107 665818 ▶ while (m_len != look && in[ip + m_len] == in[m_pos + m_len]);
Branch: 2 branches
BranchTrueFalseTotal
while (m_len != look && in[ip + m_len] == in[m_pos + m_len]); 663761 2057 665818
while (m_len != look && in[ip + m_len] == in[m_pos + m_len]); 552674 111087 663761
108  
109 113144 ▶ if (op + 2 + l_len + 3 >= maxlen)
Branch: 1 branch
BranchTrueFalseTotal
if (op + 2 + l_len + 3 >= maxlen) 1 113143 113144
110 1 return 0;
111  
112 113143 ▶ if (l_len != 0)
Branch: 1 branch
BranchTrueFalseTotal
if (l_len != 0) 4169 108974 113143
113 {
114 4169 out[op++] = (l_len - 1) << 3;
115 do
116 {
117 46910 out[op++] = in[ip - l_len--];
118 }
119 46910 ▶ while (l_len != 0);
Branch: 1 branch
BranchTrueFalseTotal
while (l_len != 0); 42741 4169 46910
120 }
121  
122 113143 m_len -= 2;
123  
124 113143 ▶ if (m_len <= 6)
Branch: 1 branch
BranchTrueFalseTotal
if (m_len <= 6) 111084 2059 113143
125 {
126 111084 out[op++] = m_len | ((m_off >> 5) & 0xf8);
127 }
128 else
129 {
130 2059 out[op++] = 0x07 | ((m_off >> 5) & 0xf8);
131 2059 out[op++] = m_len - 7;
132 }
133  
134 113143 out[op++] = m_off & 0xff;
135 113143 ip++;
136 113143 hval = ((hval << 5) ^ in[ip + 2]) & (HSIZ - 1);
137 113143 lzv1_htab[hval] = ip;
138 113143 ip++;
139  
140 do
141 {
142 665817 hval = ((hval << 5) ^ in[ip + 2]) & (HSIZ - 1);
143 665817 lzv1_htab[hval] = ip;
144 665817 ip++;
145 665817 m_len--;
146 }
147 665817 ▶ while (0 != m_len);
Branch: 1 branch
BranchTrueFalseTotal
while (0 != m_len); 552674 113143 665817
148 }
149 else
150 {
151 /* No match found */
152 98033 ip++;
153 98033 l_len++;
154  
155 98033 ▶ if (MLL == l_len)
Branch: 1 branch
BranchTrueFalseTotal
if (MLL == l_len) 1596 96437 98033
156 {
157 1596 ▶ if (op + 2 + MLL >= maxlen)
Branch: 1 branch
BranchTrueFalseTotal
if (op + 2 + MLL >= maxlen) 0 1596 1596
158 0 return 0;
159  
160 1596 out[op++] = 0xf8;
161  
162 do
163 {
164 51072 out[op++] = in[ip - l_len--];
165 }
166 51072 ▶ while (l_len != 0);
Branch: 1 branch
BranchTrueFalseTotal
while (l_len != 0); 49476 1596 51072
167 }
168 }
169 }
170 211176 ▶ while (ip < len);
Branch: 1 branch
BranchTrueFalseTotal
while (ip < len); 211168 8 211176
171  
172 8 ▶ if (l_len != 0)
Branch: 1 branch
BranchTrueFalseTotal
if (l_len != 0) 8 0 8
173 {
174 8 ▶ if (op + l_len + 3 >= maxlen)
Branch: 1 branch
BranchTrueFalseTotal
if (op + l_len + 3 >= maxlen) 0 8 8
175 0 return 0;
176  
177 8 out[op++] = (l_len - 1) << 3;
178  
179 do
180 {
181 24 out[op++] = in[ip - l_len--];
182 }
183 24 ▶ while (l_len != 0);
Branch: 1 branch
BranchTrueFalseTotal
while (l_len != 0); 16 8 24
184 }
185 8 return op;
186 }
187  
188 static int
189 8 rLZV1 (uch const *const in, uch * const out, int ilen, int len)
190 {
191 register uit tbuf, c_len;
192 8 uch *const out_end = out + len;
193 8 register uch *op = out;
194 8 uch const *const in_end = in + ilen;
195 8 register uch const *ip = in;
196  
197 do
198 {
199 110320 tbuf = *ip++;
200 110320 c_len = tbuf & 0x07;
201  
202 110320 ▶ if (0 == c_len)
Branch: 1 branch
BranchTrueFalseTotal
if (0 == c_len) 701 109619 110320
203 {
204 701 c_len = (tbuf >> 3) + 1;
205  
206 /*if (op + c_len > out_end) /* too many checks... */
207 /* return 0;*/
208  
209 do
210 1548 *op++ = *ip++;
211 1548 ▶ while (--c_len); /* effic: memcpy()? */
Branch: 1 branch
BranchTrueFalseTotal
while (--c_len); /* effic: memcpy()? */ 847 701 1548
212 }
213 else
214 {
215 register uch *m_pos;
216  
217 109619 ▶ if (0x07 == c_len)
Branch: 1 branch
BranchTrueFalseTotal
if (0x07 == c_len) 2059 107560 109619
218 2059 c_len = *ip++ + 7;
219 109619 m_pos = op - 1 - (((uit) (tbuf & 0xf8) << 5) | *ip++);
220  
221 /* If we don't check this then we segfault (if in user
222 space) or leave process in uninteruptible state (if
223 in kernel) if the data is corrupt. */
224 109619 ▶ if (m_pos < out)
Branch: 1 branch
BranchTrueFalseTotal
if (m_pos < out) 0 109619 109619
225 0 return 0; /* Compression error. */
226  
227 /*if (op + c_len + 2 > out_end) /* too many checks */
228 /* return 0;*/
229  
230 109619 *op++ = *m_pos++;
231 109619 *op++ = *m_pos++;
232  
233 do
234 662245 *op++ = *m_pos++;
235 662245 ▶ while (--c_len);
Branch: 1 branch
BranchTrueFalseTotal
while (--c_len); 552626 109619 662245
236 }
237 }
238 110320 ▶ while (op < out_end && ip < in_end);
Branch: 2 branches
BranchTrueFalseTotal
while (op < out_end && ip < in_end); 110312 8 110320
while (op < out_end && ip < in_end); 110312 0 110312
239  
240 8 return op - out;
241 }
« LZV1.xs ↑ Summary blib/lib/Compress/LZV1.pm »