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   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  */
  57 static WK_word*
  58 WK_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  */
  88 static WK_word*
  89 WK_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
 124 void
 125 WKdm_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               (((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 }