| 1 | /* direct-mapped partial matching compressor with simple 22/10 split␊ |
| 2 | *␊ |
| 3 | * Compresses buffers using a dictionary based match and partial match␊ |
| 4 | * (high bits only or full match) scheme.␊ |
| 5 | *␊ |
| 6 | * Paul Wilson -- wilson@cs.utexas.edu␊ |
| 7 | * Scott F. Kaplan -- sfkaplan@cs.utexas.edu␊ |
| 8 | * September 1997␊ |
| 9 | *␊ |
| 10 | * compressed output format, in memory order␊ |
| 11 | * 1. a four-word HEADER containing four one-word values:␊ |
| 12 | * i. a one-word code saying what algorithm compressed the data␊ |
| 13 | * ii. an integer WORD offset into the page saying␊ |
| 14 | * where the queue position area starts␊ |
| 15 | * iii. an integer WORD offset into the page saying where␊ |
| 16 | * the low-bits area starts␊ |
| 17 | * iv. an integer WORD offset into the page saying where the␊ |
| 18 | * low-bits area ends␊ |
| 19 | *␊ |
| 20 | * 2. a 64-word TAGS AREA holding one two-bit tag for each word in ␊ |
| 21 | * the original (1024-word) page, packed 16 per word␊ |
| 22 | *␊ |
| 23 | * 3. a variable-sized FULL WORDS AREA (always word aligned and an␊ |
| 24 | * integral number of words) holding full-word patterns that␊ |
| 25 | * were not in the dictionary when encoded (i.e., dictionary misses)␊ |
| 26 | *␊ |
| 27 | * 4. a variable-sized QUEUE POSITIONS AREA (always word aligned and␊ |
| 28 | * an integral number of words) holding four-bit queue positions,␊ |
| 29 | * packed eight per word.␊ |
| 30 | *␊ |
| 31 | * 5. a variable-sized LOW BITS AREA (always word aligned and an␊ |
| 32 | * integral number of words) holding ten-bit low-bit patterns␊ |
| 33 | * (from partial matches), packed three per word. ␊ |
| 34 | */␊ |
| 35 | ␊ |
| 36 | ␊ |
| 37 | #ifdef __cplusplus␊ |
| 38 | extern "C" {␊ |
| 39 | #endif␊ |
| 40 | ␊ |
| 41 | /* ============================================================ */␊ |
| 42 | /* Included files */␊ |
| 43 | ␊ |
| 44 | //#include <stdio.h>␊ |
| 45 | //#include <unistd.h>␊ |
| 46 | //#include <math.h>␊ |
| 47 | //#include <strings.h>␊ |
| 48 | ␊ |
| 49 | typedef unsigned long WK_word;␊ |
| 50 | ␊ |
| 51 | /* at the moment we have dependencies on the page size. That should␊ |
| 52 | * be changed to work for any power-of-two size that's at least 16␊ |
| 53 | * words, or something like that␊ |
| 54 | */␊ |
| 55 | ␊ |
| 56 | #define PAGE_SIZE_IN_WORDS 1024␊ |
| 57 | #define PAGE_SIZE_IN_BYTES 4096␊ |
| 58 | ␊ |
| 59 | #define DICTIONARY_SIZE 16␊ |
| 60 | ␊ |
| 61 | /*␊ |
| 62 | * macros defining the basic layout of stuff in a page␊ |
| 63 | */␊ |
| 64 | #define HEADER_SIZE_IN_WORDS 4␊ |
| 65 | #define TAGS_AREA_OFFSET 4␊ |
| 66 | #define TAGS_AREA_SIZE 64␊ |
| 67 | ␊ |
| 68 | /* the next few are used during compression to write the header */␊ |
| 69 | #define SET_QPOS_AREA_START(compr_dest_buf,qpos_start_addr) \␊ |
| 70 | (compr_dest_buf[1] = qpos_start_addr - compr_dest_buf)␊ |
| 71 | #define SET_LOW_BITS_AREA_START(compr_dest_buf,lb_start_addr) \␊ |
| 72 | (compr_dest_buf[2] = lb_start_addr - compr_dest_buf)␊ |
| 73 | #define SET_LOW_BITS_AREA_END(compr_dest_buf,lb_end_addr) \␊ |
| 74 | (compr_dest_buf[3] = lb_end_addr - compr_dest_buf)␊ |
| 75 | ␊ |
| 76 | /* the next few are only use during decompression to read the header */␊ |
| 77 | #define TAGS_AREA_START(decomp_src_buf) \␊ |
| 78 | (decomp_src_buf + TAGS_AREA_OFFSET)␊ |
| 79 | #define TAGS_AREA_END(decomp_src_buf) \␊ |
| 80 | (TAGS_AREA_START(decomp_src_buf) + TAGS_AREA_SIZE)␊ |
| 81 | #define FULL_WORD_AREA_START(the_buf) TAGS_AREA_END(the_buf)␊ |
| 82 | #define QPOS_AREA_START(decomp_src_buf) \␊ |
| 83 | (decomp_src_buf + decomp_src_buf[1]) ␊ |
| 84 | #define LOW_BITS_AREA_START(decomp_src_buf) \␊ |
| 85 | (decomp_src_buf + (decomp_src_buf[2]))␊ |
| 86 | #define QPOS_AREA_END(the_buf) LOW_BITS_AREA_START(the_buf)␊ |
| 87 | #define LOW_BITS_AREA_END(decomp_src_buf) \␊ |
| 88 | (decomp_src_buf + (decomp_src_buf[3]))␊ |
| 89 | ␊ |
| 90 | /* ============================================================ */␊ |
| 91 | /* Types and structures */␊ |
| 92 | ␊ |
| 93 | /* A structure to store each element of the dictionary. */␊ |
| 94 | typedef WK_word DictionaryElement;␊ |
| 95 | ␊ |
| 96 | /* ============================================================ */␊ |
| 97 | /* Misc constants */␊ |
| 98 | ␊ |
| 99 | #define BITS_PER_WORD 32␊ |
| 100 | #define BYTES_PER_WORD 4␊ |
| 101 | #define NUM_LOW_BITS 10␊ |
| 102 | #define LOW_BITS_MASK 0x3FF␊ |
| 103 | #define ALL_ONES_MASK 0xFFFFFFFF␊ |
| 104 | ␊ |
| 105 | #define TWO_BITS_PACKING_MASK 0x03030303␊ |
| 106 | #define FOUR_BITS_PACKING_MASK 0x0F0F0F0F␊ |
| 107 | #define TEN_LOW_BITS_MASK 0x000003FF␊ |
| 108 | #define TWENTY_TWO_HIGH_BITS_MASK 0xFFFFFC00␊ |
| 109 | ␊ |
| 110 | /* Tag values. NOTE THAT CODE MAY DEPEND ON THE NUMBERS USED.␊ |
| 111 | * Check for conditionals doing arithmetic on these things␊ |
| 112 | * before changing them␊ |
| 113 | */␊ |
| 114 | #define ZERO_TAG 0x0␊ |
| 115 | #define PARTIAL_TAG 0x1␊ |
| 116 | #define MISS_TAG 0x2␊ |
| 117 | #define EXACT_TAG 0x3␊ |
| 118 | ␊ |
| 119 | #define BITS_PER_BYTE 8␊ |
| 120 | ␊ |
| 121 | /* ============================================================ */␊ |
| 122 | /* Global macros */␊ |
| 123 | ␊ |
| 124 | /* Shift out the low bits of a pattern to give the high bits pattern.␊ |
| 125 | The stripped patterns are used for initial tests of partial␊ |
| 126 | matches. */␊ |
| 127 | #define HIGH_BITS(word_pattern) (word_pattern >> NUM_LOW_BITS)␊ |
| 128 | ␊ |
| 129 | /* String the high bits of a pattern so the low order bits can␊ |
| 130 | be included in an encoding of a partial match. */␊ |
| 131 | #define LOW_BITS(word_pattern) (word_pattern & LOW_BITS_MASK)␊ |
| 132 | ␊ |
| 133 | #if defined DEBUG_WK␊ |
| 134 | #define DEBUG_PRINT_1(string) printf (string)␊ |
| 135 | #define DEBUG_PRINT_2(string,value) printf(string, value)␊ |
| 136 | #else␊ |
| 137 | #define DEBUG_PRINT_1(string)␊ |
| 138 | #define DEBUG_PRINT_2(string, value)␊ |
| 139 | #endif␊ |
| 140 | ␊ |
| 141 | /* Set up the dictionary before performing compression or␊ |
| 142 | decompression. Each element is loaded with some value, the␊ |
| 143 | high-bits version of that value, and a next pointer. */␊ |
| 144 | #define PRELOAD_DICTIONARY { \␊ |
| 145 | dictionary[0] = 1; \␊ |
| 146 | dictionary[1] = 1; \␊ |
| 147 | dictionary[2] = 1; \␊ |
| 148 | dictionary[3] = 1; \␊ |
| 149 | dictionary[4] = 1; \␊ |
| 150 | dictionary[5] = 1; \␊ |
| 151 | dictionary[6] = 1; \␊ |
| 152 | dictionary[7] = 1; \␊ |
| 153 | dictionary[8] = 1; \␊ |
| 154 | dictionary[9] = 1; \␊ |
| 155 | dictionary[10] = 1; \␊ |
| 156 | dictionary[11] = 1; \␊ |
| 157 | dictionary[12] = 1; \␊ |
| 158 | dictionary[13] = 1; \␊ |
| 159 | dictionary[14] = 1; \␊ |
| 160 | dictionary[15] = 1; \␊ |
| 161 | }␊ |
| 162 | ␊ |
| 163 | /* these are the constants for the hash function lookup table.␊ |
| 164 | * Only zero maps to zero. The rest of the tabale is the result␊ |
| 165 | * of appending 17 randomizations of the multiples of 4 from␊ |
| 166 | * 4 to 56. Generated by a Scheme script in hash.scm. ␊ |
| 167 | */␊ |
| 168 | #define HASH_LOOKUP_TABLE_CONTENTS { \␊ |
| 169 | 0, 52, 8, 56, 16, 12, 28, 20, 4, 36, 48, 24, 44, 40, 32, 60, \␊ |
| 170 | 8, 12, 28, 20, 4, 60, 16, 36, 24, 48, 44, 32, 52, 56, 40, 12, \␊ |
| 171 | 8, 48, 16, 52, 60, 28, 56, 32, 20, 24, 36, 40, 44, 4, 8, 40, \␊ |
| 172 | 60, 32, 20, 44, 4, 36, 52, 24, 16, 56, 48, 12, 28, 16, 8, 40, \␊ |
| 173 | 36, 28, 32, 12, 4, 44, 52, 20, 24, 48, 60, 56, 40, 48, 8, 32, \␊ |
| 174 | 28, 36, 4, 44, 20, 56, 60, 24, 52, 16, 12, 12, 4, 48, 20, 8, \␊ |
| 175 | 52, 16, 60, 24, 36, 44, 28, 56, 40, 32, 36, 20, 24, 60, 40, 44, \␊ |
| 176 | 52, 16, 32, 4, 48, 8, 28, 56, 12, 28, 32, 40, 52, 36, 16, 20, \␊ |
| 177 | 48, 8, 4, 60, 24, 56, 44, 12, 8, 36, 24, 28, 16, 60, 20, 56, \␊ |
| 178 | 32, 40, 48, 12, 4, 44, 52, 44, 40, 12, 56, 8, 36, 24, 60, 28, \␊ |
| 179 | 48, 4, 32, 20, 16, 52, 60, 12, 24, 36, 8, 4, 16, 56, 48, 44, \␊ |
| 180 | 40, 52, 32, 20, 28, 32, 12, 36, 28, 24, 56, 40, 16, 52, 44, 4, \␊ |
| 181 | 20, 60, 8, 48, 48, 52, 12, 20, 32, 44, 36, 28, 4, 40, 24, 8, \␊ |
| 182 | 56, 60, 16, 36, 32, 8, 40, 4, 52, 24, 44, 20, 12, 28, 48, 56, \␊ |
| 183 | 16, 60, 4, 52, 60, 48, 20, 16, 56, 44, 24, 8, 40, 12, 32, 28, \␊ |
| 184 | 36, 24, 32, 12, 4, 20, 16, 60, 36, 28, 8, 52, 40, 48, 44, 56 \␊ |
| 185 | }␊ |
| 186 | ␊ |
| 187 | #define HASH_TO_DICT_BYTE_OFFSET(pattern) \␊ |
| 188 | (hashLookupTable[((pattern) >> 10) & 0xFF])␊ |
| 189 | ␊ |
| 190 | extern const char hashLookupTable[];␊ |
| 191 | ␊ |
| 192 | /* EMIT... macros emit bytes or words into the intermediate arrays␊ |
| 193 | */␊ |
| 194 | ␊ |
| 195 | #define EMIT_BYTE(fill_ptr, byte_value) {*fill_ptr = byte_value; fill_ptr++;}␊ |
| 196 | #define EMIT_WORD(fill_ptr,word_value) {*fill_ptr = word_value; fill_ptr++;}␊ |
| 197 | ␊ |
| 198 | /* RECORD... macros record the results of modeling in the intermediate␊ |
| 199 | * arrays␊ |
| 200 | */␊ |
| 201 | ␊ |
| 202 | #define RECORD_ZERO { EMIT_BYTE(next_tag,ZERO_TAG); }␊ |
| 203 | ␊ |
| 204 | #define RECORD_EXACT(queue_posn) EMIT_BYTE(next_tag,EXACT_TAG); \␊ |
| 205 | EMIT_BYTE(next_qp,(queue_posn)); ␊ |
| 206 | ␊ |
| 207 | #define RECORD_PARTIAL(queue_posn,low_bits_pattern) { \␊ |
| 208 | EMIT_BYTE(next_tag,PARTIAL_TAG); \␊ |
| 209 | EMIT_BYTE(next_qp,(queue_posn)); \␊ |
| 210 | EMIT_WORD(next_low_bits,(low_bits_pattern)) }␊ |
| 211 | ␊ |
| 212 | #define RECORD_MISS(word_pattern) EMIT_BYTE(next_tag,MISS_TAG); \␊ |
| 213 | EMIT_WORD(next_full_patt,(word_pattern)); ␊ |
| 214 | ␉␉␉␉ ␊ |
| 215 | void␊ |
| 216 | WKdm_decompress (WK_word* src_buf,␊ |
| 217 | ␉␉ WK_word* dest_buf,␊ |
| 218 | ␉␉ unsigned int words);␊ |
| 219 | unsigned int␊ |
| 220 | WKdm_compress (WK_word* src_buf,␊ |
| 221 | WK_word* dest_buf,␊ |
| 222 | ␉ unsigned int num_input_words);␊ |
| 223 | ␊ |
| 224 | #ifdef __cplusplus␊ |
| 225 | } /* extern "C" */␊ |
| 226 | #endif␊ |
| 227 | |
