osfmk/vm/WKdm_new.h

   1 /*
   2  * Copyright (c) 2000-2013 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 /* direct-mapped partial matching compressor with simple 22/10 split
  30  *
  31  *  Compresses buffers using a dictionary based match and partial match
  32  *  (high bits only or full match) scheme.
  33  *
  34  *  Paul Wilson -- wilson@cs.utexas.edu
  35  *  Scott F. Kaplan -- sfkaplan@cs.utexas.edu
  36  *  September 1997
  37  */
  38
  39 /* compressed output format, in memory order
  40  *  1. a four-word HEADER containing four one-word values:
  41  *     i.   a one-word code saying what algorithm compressed the data
  42  *     ii.  an integer WORD offset into the page saying
  43  *          where the queue position area starts
  44  *     iii. an integer WORD offset into the page saying where
  45  *          the low-bits area starts
  46  *     iv.  an integer WORD offset into the page saying where the
  47  *          low-bits area ends
  48  *
  49  *  2. a 64-word TAGS AREA holding one two-bit tag for each word in
  50  *     the original (1024-word) page, packed 16 per word
  51  *
  52  *  3. a variable-sized FULL WORDS AREA (always word aligned and an
  53  *     integral number of words) holding full-word patterns that
  54  *     were not in the dictionary when encoded (i.e., dictionary misses)
  55  *
  56  *  4. a variable-sized QUEUE POSITIONS AREA (always word aligned and
  57  *     an integral number of words) holding four-bit queue positions,
  58  *     packed eight per word.
  59  *
  60  *  5. a variable-sized LOW BITS AREA (always word aligned and an
  61  *     integral number of words) holding ten-bit low-bit patterns
  62  *     (from partial matches), packed three per word.
  63  */
  64
  65
  66 #ifdef __cplusplus
  67 extern "C" {
  68 #endif
  69
  70 /* ============================================================ */
  71 /* Included files */
  72
  73 #ifdef WK_DEBUG
  74 #include <stdio.h>
  75 #include <unistd.h>
  76 #include <math.h>
  77 #include <strings.h>
  78 #endif
  79
  80 typedef unsigned int WK_word;
  81
  82 /* at the moment we have dependencies on the page size.  That should
  83  * be changed to work for any power-of-two size that's at least 16
  84  * words, or something like that
  85  */
  86
  87 #define PAGE_SIZE_IN_WORDS 1024
  88 #define PAGE_SIZE_IN_BYTES 4096
  89
  90 #define DICTIONARY_SIZE 16
  91
  92 /*
  93  * macros defining the basic layout of stuff in a page
  94  */
  95 #define HEADER_SIZE_IN_WORDS 3
  96 #define TAGS_AREA_OFFSET 3
  97 #define TAGS_AREA_SIZE 64
  98
  99 /* the next few are used during compression to write the header */
 100 #define SET_QPOS_AREA_START(compr_dest_buf,qpos_start_addr)  \
 101         (compr_dest_buf[0] = qpos_start_addr - compr_dest_buf)
 102 #define SET_LOW_BITS_AREA_START(compr_dest_buf,lb_start_addr) \
 103         (compr_dest_buf[1] = lb_start_addr - compr_dest_buf)
 104 #define SET_LOW_BITS_AREA_END(compr_dest_buf,lb_end_addr) \
 105         (compr_dest_buf[2] = lb_end_addr - compr_dest_buf)
 106
 107 /* the next few are only use during decompression to read the header */
 108 #define TAGS_AREA_START(decomp_src_buf)       \
 109         (decomp_src_buf + TAGS_AREA_OFFSET)
 110 #define TAGS_AREA_END(decomp_src_buf)         \
 111         (TAGS_AREA_START(decomp_src_buf) + TAGS_AREA_SIZE)
 112 #define FULL_WORD_AREA_START(the_buf) TAGS_AREA_END(the_buf)
 113 #define QPOS_AREA_START(decomp_src_buf)       \
 114         (decomp_src_buf + decomp_src_buf[0])
 115 #define LOW_BITS_AREA_START(decomp_src_buf)   \
 116         (decomp_src_buf + (decomp_src_buf[1]))
 117 #define QPOS_AREA_END(the_buf) LOW_BITS_AREA_START(the_buf)
 118 #define LOW_BITS_AREA_END(decomp_src_buf)     \
 119         (decomp_src_buf + (decomp_src_buf[2]))
 120
 121 /* ============================================================ */
 122 /* Types and structures */
 123
 124 /* A structure to store each element of the dictionary. */
 125 typedef WK_word DictionaryElement;
 126
 127 /* ============================================================ */
 128 /* Misc constants */
 129
 130 #define BITS_PER_WORD 32
 131 #define BYTES_PER_WORD 4
 132 #define NUM_LOW_BITS 10
 133 #define LOW_BITS_MASK 0x3FF
 134 #define ALL_ONES_MASK 0xFFFFFFFF
 135
 136 #define TWO_BITS_PACKING_MASK 0x03030303
 137 #define FOUR_BITS_PACKING_MASK 0x0F0F0F0F
 138 #define TEN_LOW_BITS_MASK 0x000003FF
 139 #define TWENTY_TWO_HIGH_BITS_MASK 0xFFFFFC00
 140
 141 /* Tag values.  NOTE THAT CODE MAY DEPEND ON THE NUMBERS USED.
 142  * Check for conditionals doing arithmetic on these things
 143  * before changing them
 144  */
 145 #define ZERO_TAG 0x0
 146 #define PARTIAL_TAG 0x1
 147 #define MISS_TAG 0x2
 148 #define EXACT_TAG 0x3
 149
 150 #define BITS_PER_BYTE 8
 151
 152 /* ============================================================ */
 153 /* Global macros */
 154
 155 /* Shift out the low bits of a pattern to give the high bits pattern.
 156    The stripped patterns are used for initial tests of partial
 157    matches. */
 158 #define HIGH_BITS(word_pattern) (word_pattern >> NUM_LOW_BITS)
 159
 160 /* String the high bits of a pattern so the low order bits can
 161    be included in an encoding of a partial match. */
 162 #define LOW_BITS(word_pattern) (word_pattern & LOW_BITS_MASK)
 163
 164 #if defined DEBUG_WK
 165 #define DEBUG_PRINT_1(string) printf (string)
 166 #define DEBUG_PRINT_2(string,value) printf(string, value)
 167 #else
 168 #define DEBUG_PRINT_1(string)
 169 #define DEBUG_PRINT_2(string, value)
 170 #endif
 171
 172 /* Set up the dictionary before performing compression or
 173    decompression.  Each element is loaded with some value, the
 174    high-bits version of that value, and a next pointer. */
 175 #define PRELOAD_DICTIONARY { \
 176   dictionary[0] = 1; \
 177   dictionary[1] = 1; \
 178   dictionary[2] = 1; \
 179   dictionary[3] = 1; \
 180   dictionary[4] = 1; \
 181   dictionary[5] = 1; \
 182   dictionary[6] = 1; \
 183   dictionary[7] = 1; \
 184   dictionary[8] = 1; \
 185   dictionary[9] = 1; \
 186   dictionary[10] = 1; \
 187   dictionary[11] = 1; \
 188   dictionary[12] = 1; \
 189   dictionary[13] = 1; \
 190   dictionary[14] = 1; \
 191   dictionary[15] = 1; \
 192 }
 193
 194 /* these are the constants for the hash function lookup table.
 195  * Only zero maps to zero.  The rest of the tabale is the result
 196  * of appending 17 randomizations of the multiples of 4 from
 197  * 4 to 56.  Generated by a Scheme script in hash.scm.
 198  */
 199 #define HASH_LOOKUP_TABLE_CONTENTS { \
 200    0, 52,  8, 56, 16, 12, 28, 20,  4, 36, 48, 24, 44, 40, 32, 60, \
 201    8, 12, 28, 20,  4, 60, 16, 36, 24, 48, 44, 32, 52, 56, 40, 12, \
 202    8, 48, 16, 52, 60, 28, 56, 32, 20, 24, 36, 40, 44,  4,  8, 40, \
 203   60, 32, 20, 44,  4, 36, 52, 24, 16, 56, 48, 12, 28, 16,  8, 40, \
 204   36, 28, 32, 12,  4, 44, 52, 20, 24, 48, 60, 56, 40, 48,  8, 32, \
 205   28, 36,  4, 44, 20, 56, 60, 24, 52, 16, 12, 12,  4, 48, 20,  8, \
 206   52, 16, 60, 24, 36, 44, 28, 56, 40, 32, 36, 20, 24, 60, 40, 44, \
 207   52, 16, 32,  4, 48,  8, 28, 56, 12, 28, 32, 40, 52, 36, 16, 20, \
 208   48,  8,  4, 60, 24, 56, 44, 12,  8, 36, 24, 28, 16, 60, 20, 56, \
 209   32, 40, 48, 12,  4, 44, 52, 44, 40, 12, 56,  8, 36, 24, 60, 28, \
 210   48,  4, 32, 20, 16, 52, 60, 12, 24, 36,  8,  4, 16, 56, 48, 44, \
 211   40, 52, 32, 20, 28, 32, 12, 36, 28, 24, 56, 40, 16, 52, 44,  4, \
 212   20, 60,  8, 48, 48, 52, 12, 20, 32, 44, 36, 28,  4, 40, 24,  8, \
 213   56, 60, 16, 36, 32,  8, 40,  4, 52, 24, 44, 20, 12, 28, 48, 56, \
 214   16, 60,  4, 52, 60, 48, 20, 16, 56, 44, 24,  8, 40, 12, 32, 28, \
 215   36, 24, 32, 12,  4, 20, 16, 60, 36, 28,  8, 52, 40, 48, 44, 56  \
 216 }
 217
 218 #define HASH_TO_DICT_BYTE_OFFSET(pattern) \
 219         (hashLookupTable[((pattern) >> 10) & 0xFF])
 220
 221 extern const char hashLookupTable[];
 222
 223 /* EMIT... macros emit bytes or words into the intermediate arrays
 224  */
 225
 226 #define EMIT_BYTE(fill_ptr, byte_value) {*fill_ptr++ = byte_value; }
 227 #define EMIT_WORD(fill_ptr,word_value) {*fill_ptr++ = word_value; }
 228
 229 /* RECORD... macros record the results of modeling in the intermediate
 230  * arrays
 231  */
 232
 233 #define RECORD_ZERO { EMIT_BYTE(next_tag,ZERO_TAG); }
 234
 235 #define RECORD_EXACT(queue_posn)  EMIT_BYTE(next_tag,EXACT_TAG);  \
 236                                   EMIT_BYTE(next_qp,(queue_posn));
 237
 238 #define RECORD_PARTIAL(queue_posn,low_bits_pattern) { \
 239    EMIT_BYTE(next_tag,PARTIAL_TAG);                   \
 240    EMIT_BYTE(next_qp,(queue_posn));                   \
 241    EMIT_WORD(next_low_bits,(low_bits_pattern))  }
 242
 243 #define RECORD_MISS(word_pattern) EMIT_BYTE(next_tag,MISS_TAG); \
 244                                   EMIT_WORD(next_full_patt,(word_pattern));
 245
 246
 247 #define WKdm_SCRATCH_BUF_SIZE   4096
 248
 249 void
 250 WKdm_decompress_new (WK_word* src_buf,
 251                  WK_word* dest_buf,
 252                  WK_word* scratch,
 253                  unsigned int bytes);
 254 int
 255 WKdm_compress_new (WK_word* src_buf,
 256                WK_word* dest_buf,
 257                WK_word* scratch,
 258                unsigned int limit);
 259
 260 #ifdef __cplusplus
 261 } /* extern "C" */
 262 #endif