i386/boot2/WKdmDecompress.c

   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 }