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