libkern/kxld/WKdmCompress.c

   1 #include "WKdm.h"
   2
   3 /***********************************************************************
   4  *                   THE PACKING ROUTINES
   5  */
   6
   7 /* WK_pack_2bits()
   8  * Pack some multiple of four words holding two-bit tags (in the low
   9  * two bits of each byte) into an integral number of words, i.e.,
  10  * one fourth as many.
  11  * NOTE: Pad the input out with zeroes to a multiple of four words!
  12  */
  13 static WK_word*
  14 WK_pack_2bits(WK_word* source_buf,
  15     WK_word* source_end,
  16     WK_word* dest_buf)
  17 {
  18         WK_word* src_next = source_buf;
  19         WK_word* dest_next = dest_buf;
  20
  21         while (src_next < source_end) {
  22                 WK_word temp = src_next[0];
  23                 temp |= (src_next[1] << 2);
  24                 temp |= (src_next[2] << 4);
  25                 temp |= (src_next[3] << 6);
  26
  27                 dest_next[0] = temp;
  28                 dest_next++;
  29                 src_next += 4;
  30         }
  31
  32         return dest_next;
  33 }
  34
  35 /* WK_pack_4bits()
  36  * Pack an even number of words holding 4-bit patterns in the low bits
  37  * of each byte into half as many words.
  38  * note: pad out the input with zeroes to an even number of words!
  39  */
  40
  41 static WK_word*
  42 WK_pack_4bits(WK_word* source_buf,
  43     WK_word* source_end,
  44     WK_word* dest_buf)
  45 {
  46         WK_word* src_next = source_buf;
  47         WK_word* dest_next = dest_buf;
  48
  49         /* this loop should probably be unrolled */
  50         while (src_next < source_end) {
  51                 WK_word temp = src_next[0];
  52                 temp |= (src_next[1] << 4);
  53
  54                 dest_next[0] = temp;
  55                 dest_next++;
  56                 src_next += 2;
  57         }
  58
  59         return dest_next;
  60 }
  61
  62 /* pack_3_tenbits()
  63  * Pack a sequence of three ten bit items into one word.
  64  * note: pad out the input with zeroes to an even number of words!
  65  */
  66 static WK_word*
  67 WK_pack_3_tenbits(WK_word* source_buf,
  68     WK_word* source_end,
  69     WK_word* dest_buf)
  70 {
  71         WK_word* src_next = source_buf;
  72         WK_word* dest_next = dest_buf;
  73
  74         /* this loop should probably be unrolled */
  75         while (src_next < source_end) {
  76                 WK_word temp = src_next[0];
  77                 temp |= (src_next[1] << 10);
  78                 temp |= (src_next[2] << 20);
  79
  80                 dest_next[0] = temp;
  81                 dest_next++;
  82                 src_next += 3;
  83         }
  84
  85         return dest_next;
  86 }
  87
  88 /***************************************************************************
  89  *  WKdm_compress()---THE COMPRESSOR
  90  */
  91
  92 unsigned int
  93 WKdm_compress(WK_word* src_buf,
  94     WK_word* dest_buf,
  95     unsigned int num_input_words)
  96 {
  97         DictionaryElement dictionary[DICTIONARY_SIZE];
  98
  99         /* arrays that hold output data in intermediate form during modeling */
 100         /* and whose contents are packed into the actual output after modeling */
 101
 102         /* sizes of these arrays should be increased if you want to compress
 103          * pages larger than 4KB
 104          */
 105         WK_word tempTagsArray[300];   /* tags for everything          */
 106         WK_word tempQPosArray[300];   /* queue positions for matches  */
 107         WK_word tempLowBitsArray[1200]; /* low bits for partial matches */
 108
 109         /* boundary_tmp will be used for keeping track of what's where in
 110          * the compressed page during packing
 111          */
 112         WK_word* boundary_tmp;
 113
 114         /* Fill pointers for filling intermediate arrays (of queue positions
 115          * and low bits) during encoding.
 116          * Full words go straight to the destination buffer area reserved
 117          * for them.  (Right after where the tags go.)
 118          */
 119         WK_word* next_full_patt;
 120         char* next_tag = (char *) tempTagsArray;
 121         char* next_qp = (char *) tempQPosArray;
 122         WK_word* next_low_bits = tempLowBitsArray;
 123
 124         WK_word* next_input_word = src_buf;
 125         WK_word* end_of_input = src_buf + num_input_words;
 126
 127         PRELOAD_DICTIONARY;
 128
 129         next_full_patt = dest_buf + TAGS_AREA_OFFSET + (num_input_words / 16);
 130
 131 #ifdef WK_DEBUG
 132         printf("\nIn WKdm_compress\n");
 133         printf("About to actually compress, src_buf is %u\n", src_buf);
 134         printf("dictionary is at %u\n", dictionary);
 135         printf("dest_buf is %u next_full_patt is %u\n", dest_buf, next_full_patt);
 136         fflush(stdout);
 137 #endif
 138
 139         while (next_input_word < end_of_input) {
 140                 WK_word *dict_location;
 141                 WK_word dict_word;
 142                 WK_word input_word = *next_input_word;
 143
 144                 /* compute hash value, which is a byte offset into the dictionary,
 145                  * and add it to the base address of the dictionary. Cast back and
 146                  * forth to/from char * so no shifts are needed
 147                  */
 148                 dict_location =
 149                     (WK_word *)
 150                     ((void*) (((char*) dictionary) + HASH_TO_DICT_BYTE_OFFSET(input_word)));
 151
 152                 dict_word = *dict_location;
 153
 154                 if (input_word == dict_word) {
 155                         RECORD_EXACT(dict_location - dictionary);
 156                 } else if (input_word == 0) {
 157                         RECORD_ZERO;
 158                 } else {
 159                         WK_word input_high_bits = HIGH_BITS(input_word);
 160                         if (input_high_bits == HIGH_BITS(dict_word)) {
 161                                 RECORD_PARTIAL(dict_location - dictionary, LOW_BITS(input_word));
 162                                 *dict_location = input_word;
 163                         } else {
 164                                 RECORD_MISS(input_word);
 165                                 *dict_location = input_word;
 166                         }
 167                 }
 168                 next_input_word++;
 169         }
 170
 171 #ifdef WK_DEBUG
 172         printf("AFTER MODELING in WKdm_compress()\n"); fflush(stdout);
 173         printf("tempTagsArray holds %u bytes\n",
 174             next_tag - (char *) tempTagsArray);
 175         printf("tempQPosArray holds %u bytes\n",
 176             next_qp - (char *) tempQPosArray);
 177         printf("tempLowBitsArray holds %u bytes\n",
 178             (char *) next_low_bits - (char *) tempLowBitsArray);
 179
 180         printf("next_full_patt is %p\n",
 181             next_full_patt);
 182
 183         printf(" i.e., there are %u full patterns\n",
 184             next_full_patt - (dest_buf + TAGS_AREA_OFFSET + (num_input_words / 16)));
 185         fflush(stdout);
 186
 187         { int i;
 188           WK_word *arr = (dest_buf + TAGS_AREA_OFFSET + (num_input_words / 16));
 189
 190           printf("  first 20 full patterns are: \n");
 191           for (i = 0; i < 20; i++) {
 192                   printf(" %d", arr[i]);
 193           }
 194           printf("\n");}
 195 #endif
 196
 197         /* Record (into the header) where we stopped writing full words,
 198          * which is where we will pack the queue positions.  (Recall
 199          * that we wrote the full words directly into the dest buffer
 200          * during modeling.
 201          */
 202
 203         SET_QPOS_AREA_START(dest_buf, next_full_patt);
 204
 205         /* Pack the tags into the tags area, between the page header
 206          * and the full words area.  We don't pad for the packer
 207          * because we assume that the page size is a multiple of 16.
 208          */
 209
 210 #ifdef WK_DEBUG
 211         printf("about to pack %u bytes holding tags\n",
 212             next_tag - (char *) tempTagsArray);
 213
 214         { int i;
 215           char* arr = (char *) tempTagsArray;
 216
 217           printf("  first 200 tags are: \n");
 218           for (i = 0; i < 200; i++) {
 219                   printf(" %d", arr[i]);
 220           }
 221           printf("\n");}
 222 #endif
 223
 224         boundary_tmp = WK_pack_2bits(tempTagsArray,
 225             (WK_word *) ((void *) next_tag),
 226             dest_buf + HEADER_SIZE_IN_WORDS);
 227
 228 #ifdef WK_DEBUG
 229         printf("packing tags stopped at %u\n", boundary_tmp);
 230 #endif
 231
 232         /* Pack the queue positions into the area just after
 233          * the full words.  We have to round up the source
 234          * region to a multiple of two words.
 235          */
 236
 237         {
 238                 unsigned int num_bytes_to_pack = (unsigned int)(next_qp - (char *) tempQPosArray);
 239                 unsigned int num_packed_words = (num_bytes_to_pack + 7) >> 3; // ceil((double) num_bytes_to_pack / 8);
 240                 unsigned int num_source_words = num_packed_words * 2;
 241                 WK_word* endQPosArray = tempQPosArray + num_source_words;
 242
 243                 /* Pad out the array with zeros to avoid corrupting real packed
 244                  *  values. */
 245                 for (; /* next_qp is already set as desired */
 246                     next_qp < (char*)endQPosArray;
 247                     next_qp++) {
 248                         *next_qp = 0;
 249                 }
 250
 251 #ifdef WK_DEBUG
 252                 printf("about to pack %u (bytes holding) queue posns.\n",
 253                     num_bytes_to_pack);
 254                 printf("packing them from %u words into %u words\n",
 255                     num_source_words, num_packed_words);
 256                 printf("dest is range %u to %u\n",
 257                     next_full_patt, next_full_patt + num_packed_words);
 258                 { int i;
 259                   char *arr = (char *) tempQPosArray;
 260                   printf("  first 200 queue positions are: \n");
 261                   for (i = 0; i < 200; i++) {
 262                           printf(" %d", arr[i]);
 263                   }
 264                   printf("\n");}
 265 #endif
 266
 267                 boundary_tmp = WK_pack_4bits(tempQPosArray,
 268                     endQPosArray,
 269                     next_full_patt);
 270 #ifdef WK_DEBUG
 271                 printf("Packing of queue positions stopped at %u\n", boundary_tmp);
 272 #endif // WK_DEBUG
 273
 274                 /* Record (into the header) where we stopped packing queue positions,
 275                  * which is where we will start packing low bits.
 276                  */
 277                 SET_LOW_BITS_AREA_START(dest_buf, boundary_tmp);
 278         }
 279
 280         /* Pack the low bit patterns into the area just after
 281          * the queue positions.  We have to round up the source
 282          * region to a multiple of three words.
 283          */
 284
 285         {
 286                 unsigned int num_tenbits_to_pack =
 287                     (unsigned int)(next_low_bits - tempLowBitsArray);
 288                 unsigned int num_packed_words = (num_tenbits_to_pack + 2) / 3; //ceil((double) num_tenbits_to_pack / 3);
 289                 unsigned int num_source_words = num_packed_words * 3;
 290                 WK_word* endLowBitsArray = tempLowBitsArray + num_source_words;
 291
 292                 /* Pad out the array with zeros to avoid corrupting real packed
 293                  *  values. */
 294
 295                 for (; /* next_low_bits is already set as desired */
 296                     next_low_bits < endLowBitsArray;
 297                     next_low_bits++) {
 298                         *next_low_bits = 0;
 299                 }
 300
 301 #ifdef WK_DEBUG
 302                 printf("about to pack low bits\n");
 303                 printf("num_tenbits_to_pack is %u\n", num_tenbits_to_pack);
 304                 printf("endLowBitsArray is %u\n", endLowBitsArray);
 305 #endif
 306
 307                 boundary_tmp = WK_pack_3_tenbits(tempLowBitsArray,
 308                     endLowBitsArray,
 309                     boundary_tmp);
 310
 311                 SET_LOW_BITS_AREA_END(dest_buf, boundary_tmp);
 312         }
 313
 314         return (unsigned int)((char *) boundary_tmp - (char *) dest_buf);
 315 }