1 #include "stdinc.h"
2 #include "whack.h"
3 
4 enum
5 {
6 	DMaxFastLen	= 7,
7 	DBigLenCode	= 0x3c,		/* minimum code for large lenth encoding */
8 	DBigLenBits	= 6,
9 	DBigLenBase	= 1		/* starting items to encode for big lens */
10 };
11 
12 static uchar lenval[1 << (DBigLenBits - 1)] =
13 {
14 	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
15 	3, 3, 3, 3, 3, 3, 3, 3,
16 	4, 4, 4, 4,
17 	5,
18 	6,
19 	255,
20 	255
21 };
22 
23 static uchar lenbits[] =
24 {
25 	0, 0, 0,
26 	2, 3, 5, 5,
27 };
28 
29 static uchar offbits[16] =
30 {
31 	5, 5, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 12, 13
32 };
33 
34 static ushort offbase[16] =
35 {
36 	0, 0x20,
37 	0x40, 0x60,
38 	0x80, 0xc0,
39 	0x100, 0x180,
40 	0x200, 0x300,
41 	0x400, 0x600,
42 	0x800, 0xc00,
43 	0x1000,
44 	0x2000
45 };
46 
47 void
48 unwhackinit(Unwhack *uw)
49 {
50 	uw->err[0] = '\0';
51 }
52 
53 int
54 unwhack(Unwhack *uw, uchar *dst, int ndst, uchar *src, int nsrc)
55 {
56 	uchar *s, *d, *dmax, *smax, lit;
57 	ulong uwbits, lithist;
58 	int i, off, len, bits, use, code, uwnbits, overbits;
59 
60 	d = dst;
61 	dmax = d + ndst;
62 
63 	smax = src + nsrc;
64 	uwnbits = 0;
65 	uwbits = 0;
66 	overbits = 0;
67 	lithist = ~0;
68 	while(src < smax || uwnbits - overbits >= MinDecode){
69 		while(uwnbits <= 24){
70 			uwbits <<= 8;
71 			if(src < smax)
72 				uwbits |= *src++;
73 			else
74 				overbits += 8;
75 			uwnbits += 8;
76 		}
77 
78 		/*
79 		 * literal
80 		 */
81 		len = lenval[(uwbits >> (uwnbits - 5)) & 0x1f];
82 		if(len == 0){
83 			if(lithist & 0xf){
84 				uwnbits -= 9;
85 				lit = (uwbits >> uwnbits) & 0xff;
86 				lit &= 255;
87 			}else{
88 				uwnbits -= 8;
89 				lit = (uwbits >> uwnbits) & 0x7f;
90 				if(lit < 32){
91 					if(lit < 24){
92 						uwnbits -= 2;
93 						lit = (lit << 2) | ((uwbits >> uwnbits) & 3);
94 					}else{
95 						uwnbits -= 3;
96 						lit = (lit << 3) | ((uwbits >> uwnbits) & 7);
97 					}
98 					lit = (lit - 64) & 0xff;
99 				}
100 			}
101 			if(d >= dmax){
102 				snprint(uw->err, WhackErrLen, "too much output");
103 				return -1;
104 			}
105 			*d++ = lit;
106 			lithist = (lithist << 1) | (lit < 32) | (lit > 127);
107 			continue;
108 		}
109 
110 		/*
111 		 * length
112 		 */
113 		if(len < 255)
114 			uwnbits -= lenbits[len];
115 		else{
116 			uwnbits -= DBigLenBits;
117 			code = ((uwbits >> uwnbits) & ((1 << DBigLenBits) - 1)) - DBigLenCode;
118 			len = DMaxFastLen;
119 			use = DBigLenBase;
120 			bits = (DBigLenBits & 1) ^ 1;
121 			while(code >= use){
122 				len += use;
123 				code -= use;
124 				code <<= 1;
125 				uwnbits--;
126 				if(uwnbits < 0){
127 					snprint(uw->err, WhackErrLen, "len out of range");
128 					return -1;
129 				}
130 				code |= (uwbits >> uwnbits) & 1;
131 				use <<= bits;
132 				bits ^= 1;
133 			}
134 			len += code;
135 
136 			while(uwnbits <= 24){
137 				uwbits <<= 8;
138 				if(src < smax)
139 					uwbits |= *src++;
140 				else
141 					overbits += 8;
142 				uwnbits += 8;
143 			}
144 		}
145 
146 		/*
147 		 * offset
148 		 */
149 		uwnbits -= 4;
150 		bits = (uwbits >> uwnbits) & 0xf;
151 		off = offbase[bits];
152 		bits = offbits[bits];
153 
154 		uwnbits -= bits;
155 		off |= (uwbits >> uwnbits) & ((1 << bits) - 1);
156 		off++;
157 
158 		if(off > d - dst){
159 			snprint(uw->err, WhackErrLen, "offset out of range: off=%d d=%ld len=%d nbits=%d", off, d - dst, len, uwnbits);
160 			return -1;
161 		}
162 		if(d + len > dmax){
163 			snprint(uw->err, WhackErrLen, "len out of range");
164 			return -1;
165 		}
166 		s = d - off;
167 		for(i = 0; i < len; i++)
168 			d[i] = s[i];
169 		d += len;
170 	}
171 	if(uwnbits < overbits){
172 		snprint(uw->err, WhackErrLen, "compressed data overrun");
173 		return -1;
174 	}
175 
176 	len = d - dst;
177 
178 	return len;
179 }