Chameleon

Chameleon Svn Source Tree

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

Source at commit 1808 created 12 years 4 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