libkern/kxld/WKdmDecompress.c

   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*
  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*
  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*
  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
 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 }