Chameleon

Chameleon Svn Source Tree

Root/trunk/i386/boot2/WKdmDecompress.c

1#include <sys/cdefs.h>
2#include "WKdm.h"
3
4/* Part of __HIB section */
5
6/***************************************************************************
7 * THE UNPACKING ROUTINES should GO HERE
8 */
9
10const char hashLookupTable [] = HASH_LOOKUP_TABLE_CONTENTS;
11
12#if 0
13#define GET_NEXT_TAG tags[tagsIndex++]
14#define GET_NEXT_FULL_PATTERN fullPatterns[fullPatternsIndex++]
15#define GET_NEXT_LOW_BITS lowBits[lowBitsIndex++]
16#define GET_NEXT_DICTIONARY_INDEX dictionaryIndices[dictionaryIndicesIndex++]
17#endif
18
19/* WK_unpack_2bits takes any number of words containing 16 two-bit values
20 * and unpacks them into four times as many words containg those
21 * two bit values as bytes (with the low two bits of each byte holding
22 * the actual value.
23 */
24static WK_word*
25WK_unpack_2bits(WK_word *input_buf,
26 WK_word *input_end,
27 WK_word *output_buf) {
28
29 register WK_word *input_next = input_buf;
30 register WK_word *output_next = output_buf;
31 register WK_word packing_mask = TWO_BITS_PACKING_MASK;
32
33 /* loop to repeatedly grab one input word and unpack it into
34 * 4 output words. This loop could be unrolled a little---it's
35 * designed to be easy to do that.
36 */
37 while (input_next < input_end) {
38 register WK_word temp = input_next[0];
39 DEBUG_PRINT_2("Unpacked tags word: %.8x\n", temp);
40 output_next[0] = temp & packing_mask;
41 output_next[1] = (temp >> 2) & packing_mask;
42 output_next[2] = (temp >> 4) & packing_mask;
43 output_next[3] = (temp >> 6) & packing_mask;
44
45 output_next += 4;
46 input_next++;
47 }
48
49 return output_next;
50
51}
52
53/* unpack four bits consumes any number of words (between input_buf
54 * and input_end) holding 8 4-bit values per word, and unpacks them
55 * into twice as many words, with each value in a separate byte.
56 * (The four-bit values occupy the low halves of the bytes in the
57 * result).
58 */
59static WK_word*
60WK_unpack_4bits(WK_word *input_buf,
61 WK_word *input_end,
62 WK_word *output_buf) {
63
64 register WK_word *input_next = input_buf;
65 register WK_word *output_next = output_buf;
66 register WK_word packing_mask = FOUR_BITS_PACKING_MASK;
67
68
69 /* loop to repeatedly grab one input word and unpack it into
70 * 4 output words. This loop should probably be unrolled
71 * a little---it's designed to be easy to do that.
72 */
73 while (input_next < input_end) {
74 register WK_word temp = input_next[0];
75 DEBUG_PRINT_2("Unpacked dictionary indices word: %.8x\n", temp);
76 output_next[0] = temp & packing_mask;
77 output_next[1] = (temp >> 4) & packing_mask;
78
79 output_next += 2;
80 input_next++;
81 }
82
83 return output_next;
84
85}
86
87/* unpack_3_tenbits unpacks three 10-bit items from (the low 30 bits of)
88 * a 32-bit word
89 */
90static WK_word*
91WK_unpack_3_tenbits(WK_word *input_buf,
92 WK_word *input_end,
93 WK_word *output_buf) {
94
95 register WK_word *input_next = input_buf;
96 register WK_word *output_next = output_buf;
97 register WK_word packing_mask = LOW_BITS_MASK;
98
99 /* loop to fetch words of input, splitting each into three
100 * words of output with 10 meaningful low bits. This loop
101 * probably ought to be unrolled and maybe coiled
102 */
103 while (input_next < input_end) {
104 register WK_word temp = input_next[0];
105
106 output_next[0] = temp & packing_mask;
107 output_next[1] = (temp >> 10) & packing_mask;
108 output_next[2] = temp >> 20;
109
110 input_next++;
111 output_next += 3;
112 }
113
114 return output_next;
115
116}
117
118/*********************************************************************
119 * WKdm_decompress --- THE DECOMPRESSOR
120 * Expects WORD pointers to the source and destination buffers
121 * and a page size in words. The page size had better be 1024 unless
122 * somebody finds the places that are dependent on the page size and
123 * fixes them
124 */
125
126void
127WKdm_decompress (WK_word* src_buf,
128 WK_word* dest_buf,
129 __unused unsigned int words)
130{
131
132 DictionaryElement dictionary[DICTIONARY_SIZE];
133
134 /* arrays that hold output data in intermediate form during modeling */
135 /* and whose contents are packed into the actual output after modeling */
136
137 /* sizes of these arrays should be increased if you want to compress
138 * pages larger than 4KB
139 */
140 WK_word tempTagsArray[300]; /* tags for everything */
141 WK_word tempQPosArray[300]; /* queue positions for matches */
142 WK_word tempLowBitsArray[1200]; /* low bits for partial matches */
143
144 PRELOAD_DICTIONARY;
145
146#ifdef WK_DEBUG
147 printf("\nIn DECOMPRESSOR\n");
148 printf("tempTagsArray is at %u\n", (unsigned long int) tempTagsArray);
149 printf("tempQPosArray is at %u\n", (unsigned long int) tempQPosArray);
150 printf("tempLowBitsArray is at %u\n", (unsigned long int) tempLowBitsArray);
151
152 printf(" first four words of source buffer are:\n");
153 printf(" %u\n %u\n %u\n %u\n",
154 src_buf[0], src_buf[1], src_buf[2], src_buf[3]);
155
156 { int i;
157 WK_word *arr =(src_buf + TAGS_AREA_OFFSET + (PAGE_SIZE_IN_WORDS / 16));
158
159 printf(" first 20 full patterns are: \n");
160 for (i = 0; i < 20; i++) {
161 printf(" %d", arr[i]);
162 }
163 printf("\n");
164 }
165#endif
166
167 WK_unpack_2bits(TAGS_AREA_START(src_buf),
168 TAGS_AREA_END(src_buf),
169 tempTagsArray);
170
171#ifdef WK_DEBUG
172 { int i;
173 char* arr = (char *) tempTagsArray;
174
175 printf(" first 200 tags are: \n");
176 for (i = 0; i < 200; i++) {
177 printf(" %d", arr[i]);
178 }
179 printf("\n");
180 }
181#endif
182
183 WK_unpack_4bits(QPOS_AREA_START(src_buf),
184 QPOS_AREA_END(src_buf),
185 tempQPosArray);
186
187#ifdef WK_DEBUG
188 { int i;
189 char* arr = (char *) tempQPosArray;
190
191 printf(" first 200 queue positions are: \n");
192 for (i = 0; i < 200; i++) {
193 printf(" %d", arr[i]);
194 }
195 printf("\n");
196 }
197#endif
198
199 WK_unpack_3_tenbits(LOW_BITS_AREA_START(src_buf),
200 LOW_BITS_AREA_END(src_buf),
201 tempLowBitsArray);
202
203#ifdef WK_DEBUG
204 printf("AFTER UNPACKING, about to enter main block \n");
205#endif
206
207 {
208 register char *next_tag = (char *) tempTagsArray;
209 char *tags_area_end =
210 ((char *) tempTagsArray) + PAGE_SIZE_IN_WORDS;
211 char *next_q_pos = (char *) tempQPosArray;
212 WK_word *next_low_bits = tempLowBitsArray;
213 WK_word *next_full_word = FULL_WORD_AREA_START(src_buf);
214
215 WK_word *next_output = dest_buf;
216
217#ifdef WK_DEBUG
218 printf("next_output is %u\n", next_output);
219
220 printf("next_tag is %u \n", next_tag);
221 printf("tags_area_end is %u\n", tags_area_end);
222 printf("next_q_pos is %u\n", next_q_pos);
223 printf("next_low_bits is %u\n", next_low_bits);
224 printf("next_full_word is %u\n", next_full_word);
225#endif
226
227 /* this loop should probably be unrolled. Maybe we should unpack
228 * as 4 bit values, giving two consecutive tags, and switch on
229 * that 16 ways to decompress 2 words at a whack
230 */
231 while (next_tag < tags_area_end) {
232
233 char tag = next_tag[0];
234
235 switch(tag) {
236
237 case ZERO_TAG: {
238 *next_output = 0;
239 break;
240 }
241 case EXACT_TAG: {
242 WK_word *dict_location = dictionary + *(next_q_pos++);
243 /* no need to replace dict. entry if matched exactly */
244 *next_output = *dict_location;
245 break;
246 }
247 case PARTIAL_TAG: {
248 WK_word *dict_location = dictionary + *(next_q_pos++);
249 {
250 WK_word temp = *dict_location;
251
252 /* strip out low bits */
253 temp = ((temp >> NUM_LOW_BITS) << NUM_LOW_BITS);
254
255 /* add in stored low bits from temp array */
256 temp = temp | *(next_low_bits++);
257
258 *dict_location = temp; /* replace old value in dict. */
259 *next_output = temp; /* and echo it to output */
260 }
261 break;
262 }
263 case MISS_TAG: {
264 WK_word missed_word = *(next_full_word++);
265 WK_word *dict_location =
266 (WK_word *)
267 (((char *) dictionary) + HASH_TO_DICT_BYTE_OFFSET(missed_word));
268 *dict_location = missed_word;
269 *next_output = missed_word;
270 break;
271 }
272 }
273 next_tag++;
274 next_output++;
275 }
276
277#ifdef WK_DEBUG
278 printf("AFTER DECOMPRESSING\n");
279 printf("next_output is %u\n", (unsigned long int) next_output);
280 printf("next_tag is %u\n", (unsigned long int) next_tag);
281 printf("next_full_word is %u\n", (unsigned long int) next_full_word);
282 printf("next_q_pos is %u\n", (unsigned long int) next_q_pos);
283#endif
284 }
285}
286

Archive Download this file

Revision: 151