1 #include "igzip_lib.h" 2 #include "huffman.h" 3 #include "encode_df.h" 4 #include "igzip_level_buf_structs.h" 5 6 extern uint64_t 7 gen_icf_map_lh1(struct isal_zstream *, struct deflate_icf *, uint64_t); 8 extern void 9 set_long_icf_fg(uint8_t *, uint64_t, uint64_t, struct deflate_icf *); 10 extern void 11 isal_deflate_icf_body_lvl1(struct isal_zstream *); 12 extern void 13 isal_deflate_icf_body_lvl2(struct isal_zstream *); 14 extern void 15 isal_deflate_icf_body_lvl3(struct isal_zstream *); 16 /* 17 ************************************************************* 18 * Helper functions 19 ************************************************************ 20 */ 21 static inline void 22 write_deflate_icf(struct deflate_icf *icf, uint32_t lit_len, uint32_t lit_dist, uint32_t extra_bits) 23 { 24 /* icf->lit_len = lit_len; */ 25 /* icf->lit_dist = lit_dist; */ 26 /* icf->dist_extra = extra_bits; */ 27 28 store_native_u32((uint8_t *) icf, 29 lit_len | (lit_dist << LIT_LEN_BIT_COUNT) | 30 (extra_bits << (LIT_LEN_BIT_COUNT + DIST_LIT_BIT_COUNT))); 31 } 32 33 void 34 set_long_icf_fg_base(uint8_t *next_in, uint64_t processed, uint64_t input_size, 35 struct deflate_icf *match_lookup) 36 { 37 uint8_t *end_processed = next_in + processed; 38 uint8_t *end_in = next_in + input_size; 39 uint32_t dist_code, dist_extra, dist, len; 40 uint32_t match_len; 41 uint32_t dist_start[] = { 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0007, 0x0009, 0x000d, 42 0x0011, 0x0019, 0x0021, 0x0031, 0x0041, 0x0061, 0x0081, 0x00c1, 43 0x0101, 0x0181, 0x0201, 0x0301, 0x0401, 0x0601, 0x0801, 0x0c01, 44 0x1001, 0x1801, 0x2001, 0x3001, 0x4001, 0x6001, 0x0000, 0x0000 }; 45 46 if (end_in > end_processed + ISAL_LOOK_AHEAD) 47 end_in = end_processed + ISAL_LOOK_AHEAD; 48 49 while (next_in < end_processed) { 50 dist_code = match_lookup->lit_dist; 51 dist_extra = match_lookup->dist_extra; 52 dist = dist_start[dist_code] + dist_extra; 53 len = match_lookup->lit_len; 54 if (len >= 8 + LEN_OFFSET) { 55 match_len = 56 compare((next_in + 8) - dist, next_in + 8, end_in - (next_in + 8)) + 57 LEN_OFFSET + 8; 58 59 while (match_len > match_lookup->lit_len && 60 match_len >= LEN_OFFSET + SHORTEST_MATCH) { 61 write_deflate_icf(match_lookup, 62 match_len > LEN_MAX ? LEN_MAX : match_len, 63 dist_code, dist_extra); 64 match_lookup++; 65 next_in++; 66 match_len--; 67 } 68 } 69 70 match_lookup++; 71 next_in++; 72 } 73 } 74 75 /* 76 ************************************************************* 77 * Methods for generating one pass match lookup table 78 ************************************************************ 79 */ 80 uint64_t 81 gen_icf_map_h1_base(struct isal_zstream *stream, struct deflate_icf *matches_icf_lookup, 82 uint64_t input_size) 83 { 84 85 uint32_t dist, len, extra_bits; 86 uint8_t *next_in = stream->next_in, *end_in = stream->next_in + input_size; 87 uint8_t *file_start = (uint8_t *) ((uintptr_t) stream->next_in - stream->total_in); 88 uint32_t hash; 89 uint64_t next_bytes, match_bytes; 90 uint64_t match; 91 struct level_buf *level_buf = (struct level_buf *) stream->level_buf; 92 uint16_t *hash_table = level_buf->hash_map.hash_table; 93 uint32_t hist_size = stream->internal_state.dist_mask; 94 uint32_t hash_mask = stream->internal_state.hash_mask; 95 96 if (input_size < ISAL_LOOK_AHEAD) 97 return 0; 98 99 if (stream->internal_state.has_hist == IGZIP_NO_HIST) { 100 matches_icf_lookup->lit_len = *next_in; 101 matches_icf_lookup->lit_dist = 0x1e; 102 matches_icf_lookup->dist_extra = 0; 103 104 hash = compute_hash(load_le_u32(next_in)) & hash_mask; 105 hash_table[hash] = (uint64_t) (next_in - file_start); 106 107 next_in++; 108 matches_icf_lookup++; 109 stream->internal_state.has_hist = IGZIP_HIST; 110 } 111 112 while (next_in < end_in - ISAL_LOOK_AHEAD) { 113 hash = compute_hash(load_le_u32(next_in)) & hash_mask; 114 dist = (next_in - file_start - hash_table[hash]); 115 dist = ((dist - 1) & hist_size) + 1; 116 hash_table[hash] = (uint64_t) (next_in - file_start); 117 118 match_bytes = load_le_u64(next_in - dist); 119 next_bytes = load_le_u64(next_in); 120 match = next_bytes ^ match_bytes; 121 122 len = tzbytecnt(match); 123 124 if (len >= SHORTEST_MATCH) { 125 len += LEN_OFFSET; 126 get_dist_icf_code(dist, &dist, &extra_bits); 127 write_deflate_icf(matches_icf_lookup, len, dist, extra_bits); 128 } else { 129 write_deflate_icf(matches_icf_lookup, *next_in, 0x1e, 0); 130 } 131 132 next_in++; 133 matches_icf_lookup++; 134 } 135 return next_in - stream->next_in; 136 } 137 138 /* 139 ************************************************************* 140 * One pass methods for parsing provided match lookup table 141 ************************************************************ 142 */ 143 static struct deflate_icf * 144 compress_icf_map_g(struct isal_zstream *stream, struct deflate_icf *matches_next, 145 struct deflate_icf *matches_end) 146 { 147 uint32_t lit_len, lit_len2, dist; 148 uint64_t code; 149 struct isal_zstate *state = &stream->internal_state; 150 struct level_buf *level_buf = (struct level_buf *) stream->level_buf; 151 struct deflate_icf *matches_start = matches_next; 152 struct deflate_icf *icf_buf_end = 153 level_buf->icf_buf_next + level_buf->icf_buf_avail_out / sizeof(struct deflate_icf); 154 155 while (matches_next + 1 < matches_end && level_buf->icf_buf_next + 1 < icf_buf_end) { 156 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ 157 code = load_native_u64((uint8_t *) matches_next); 158 #else 159 code = load_native_u32((uint8_t *) matches_next) | 160 ((uint64_t) load_native_u32((uint8_t *) (matches_next + 1)) << 32); 161 #endif 162 lit_len = code & LIT_LEN_MASK; 163 lit_len2 = (code >> ICF_CODE_LEN) & LIT_LEN_MASK; 164 level_buf->hist.ll_hist[lit_len]++; 165 166 if (lit_len >= LEN_START) { 167 store_native_u32((uint8_t *) level_buf->icf_buf_next, code); 168 level_buf->icf_buf_next++; 169 170 dist = (code >> ICF_DIST_OFFSET) & DIST_LIT_MASK; 171 level_buf->hist.d_hist[dist]++; 172 lit_len -= LEN_OFFSET; 173 matches_next += lit_len; 174 175 } else if (lit_len2 >= LEN_START) { 176 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ 177 store_native_u64((uint8_t *) level_buf->icf_buf_next, code); 178 #else 179 store_native_u32((uint8_t *) level_buf->icf_buf_next, (uint32_t) code); 180 store_native_u32((uint8_t *) (level_buf->icf_buf_next + 1), 181 (uint32_t) (code >> 32)); 182 #endif 183 level_buf->icf_buf_next += 2; 184 185 level_buf->hist.ll_hist[lit_len2]++; 186 187 dist = (code >> (ICF_CODE_LEN + ICF_DIST_OFFSET)) & DIST_LIT_MASK; 188 level_buf->hist.d_hist[dist]++; 189 lit_len2 -= LEN_OFFSET - 1; 190 matches_next += lit_len2; 191 192 } else { 193 code = ((lit_len2 + LIT_START) << ICF_DIST_OFFSET) | lit_len; 194 store_native_u32((uint8_t *) level_buf->icf_buf_next, code); 195 level_buf->icf_buf_next++; 196 197 level_buf->hist.ll_hist[lit_len2]++; 198 199 matches_next += 2; 200 } 201 } 202 203 while (matches_next < matches_end && level_buf->icf_buf_next < icf_buf_end) { 204 code = load_native_u32((uint8_t *) matches_next); 205 lit_len = code & LIT_LEN_MASK; 206 store_native_u32((uint8_t *) level_buf->icf_buf_next, code); 207 level_buf->icf_buf_next++; 208 209 level_buf->hist.ll_hist[lit_len]++; 210 if (lit_len >= LEN_START) { 211 dist = (code >> 10) & 0x1ff; 212 level_buf->hist.d_hist[dist]++; 213 lit_len -= LEN_OFFSET; 214 matches_next += lit_len; 215 } else { 216 matches_next++; 217 } 218 } 219 220 level_buf->icf_buf_avail_out = 221 (icf_buf_end - level_buf->icf_buf_next) * sizeof(struct deflate_icf); 222 223 state->block_end += matches_next - matches_start; 224 if (matches_next > matches_end && matches_start < matches_end) { 225 stream->next_in += matches_next - matches_end; 226 stream->avail_in -= matches_next - matches_end; 227 stream->total_in += matches_next - matches_end; 228 } 229 230 return matches_next; 231 } 232 233 /* 234 ************************************************************* 235 * Compression functions combining different methods 236 ************************************************************ 237 */ 238 static inline void 239 icf_body_next_state(struct isal_zstream *stream) 240 { 241 struct level_buf *level_buf = (struct level_buf *) stream->level_buf; 242 struct isal_zstate *state = &stream->internal_state; 243 244 if (level_buf->icf_buf_avail_out <= 0) 245 state->state = ZSTATE_CREATE_HDR; 246 247 else if (stream->avail_in <= ISAL_LOOK_AHEAD && 248 (stream->end_of_stream || stream->flush != NO_FLUSH)) 249 state->state = ZSTATE_FLUSH_READ_BUFFER; 250 } 251 252 void 253 icf_body_hash1_fillgreedy_lazy(struct isal_zstream *stream) 254 { 255 struct deflate_icf *matches_icf, *matches_next_icf, *matches_end_icf; 256 struct deflate_icf *matches_icf_lookup; 257 struct level_buf *level_buf = (struct level_buf *) stream->level_buf; 258 uint32_t input_size, processed; 259 260 matches_icf = level_buf->hash_map.matches; 261 matches_icf_lookup = matches_icf; 262 matches_next_icf = level_buf->hash_map.matches_next; 263 matches_end_icf = level_buf->hash_map.matches_end; 264 265 matches_next_icf = compress_icf_map_g(stream, matches_next_icf, matches_end_icf); 266 267 while (matches_next_icf >= matches_end_icf) { 268 input_size = MATCH_BUF_SIZE; 269 input_size = (input_size > stream->avail_in) ? stream->avail_in : input_size; 270 271 if (input_size <= ISAL_LOOK_AHEAD) 272 break; 273 274 processed = gen_icf_map_h1_base(stream, matches_icf_lookup, input_size); 275 276 set_long_icf_fg(stream->next_in, processed, input_size, matches_icf_lookup); 277 278 stream->next_in += processed; 279 stream->avail_in -= processed; 280 stream->total_in += processed; 281 282 matches_end_icf = matches_icf + processed; 283 matches_next_icf = compress_icf_map_g(stream, matches_icf, matches_end_icf); 284 } 285 286 level_buf->hash_map.matches_next = matches_next_icf; 287 level_buf->hash_map.matches_end = matches_end_icf; 288 289 icf_body_next_state(stream); 290 } 291 292 void 293 icf_body_lazyhash1_fillgreedy_greedy(struct isal_zstream *stream) 294 { 295 struct deflate_icf *matches_icf, *matches_next_icf, *matches_end_icf; 296 struct deflate_icf *matches_icf_lookup; 297 struct level_buf *level_buf = (struct level_buf *) stream->level_buf; 298 uint32_t input_size, processed; 299 300 matches_icf = level_buf->hash_map.matches; 301 matches_icf_lookup = matches_icf; 302 matches_next_icf = level_buf->hash_map.matches_next; 303 matches_end_icf = level_buf->hash_map.matches_end; 304 305 matches_next_icf = compress_icf_map_g(stream, matches_next_icf, matches_end_icf); 306 307 while (matches_next_icf >= matches_end_icf) { 308 input_size = MATCH_BUF_SIZE; 309 input_size = (input_size > stream->avail_in) ? stream->avail_in : input_size; 310 311 if (input_size <= ISAL_LOOK_AHEAD) 312 break; 313 314 processed = gen_icf_map_lh1(stream, matches_icf_lookup, input_size); 315 316 set_long_icf_fg(stream->next_in, processed, input_size, matches_icf_lookup); 317 318 stream->next_in += processed; 319 stream->avail_in -= processed; 320 stream->total_in += processed; 321 322 matches_end_icf = matches_icf + processed; 323 matches_next_icf = compress_icf_map_g(stream, matches_icf, matches_end_icf); 324 } 325 326 level_buf->hash_map.matches_next = matches_next_icf; 327 level_buf->hash_map.matches_end = matches_end_icf; 328 329 icf_body_next_state(stream); 330 } 331 332 void 333 isal_deflate_icf_body(struct isal_zstream *stream) 334 { 335 switch (stream->level) { 336 case 3: 337 isal_deflate_icf_body_lvl3(stream); 338 break; 339 case 2: 340 isal_deflate_icf_body_lvl2(stream); 341 break; 342 case 1: 343 default: 344 isal_deflate_icf_body_lvl1(stream); 345 } 346 } 347