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