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