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 | |