Chameleon

Chameleon Svn Source Tree

Root/tags/2.0/i386/boot2/WKdmDecompress.c

Source at commit 1808 created 12 years 3 months ago.
By blackosx, Revise layout of package installer 'Welcome' file so it looks cleaner. Change the copyright notice to begin from 2009 as seen in the Chameleon 2.0 r431 installer. Should this date be set earlier?
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: 1808