| 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 | ␊ |
| 10 | const 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 | */␊ |
| 24 | static WK_word*␊ |
| 25 | WK_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 | */␊ |
| 59 | static WK_word*␊ |
| 60 | WK_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 | */␊ |
| 90 | static WK_word*␊ |
| 91 | WK_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 | ␊ |
| 126 | void␊ |
| 127 | WKdm_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 | |
