ceph/src/spdk/isa-l/igzip/igzip_icf_body.c

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