1207753Smm/////////////////////////////////////////////////////////////////////////////// 2207753Smm// 3207753Smm/// \file lz_encoder_mf.c 4207753Smm/// \brief Match finders 5207753Smm/// 6207753Smm// Authors: Igor Pavlov 7207753Smm// Lasse Collin 8207753Smm// 9207753Smm// This file has been put into the public domain. 10207753Smm// You can do whatever you want with this file. 11207753Smm// 12207753Smm/////////////////////////////////////////////////////////////////////////////// 13207753Smm 14207753Smm#include "lz_encoder.h" 15207753Smm#include "lz_encoder_hash.h" 16278433Srpaulo#include "memcmplen.h" 17207753Smm 18207753Smm 19207753Smm/// \brief Find matches starting from the current byte 20207753Smm/// 21207753Smm/// \return The length of the longest match found 22207753Smmextern uint32_t 23207753Smmlzma_mf_find(lzma_mf *mf, uint32_t *count_ptr, lzma_match *matches) 24207753Smm{ 25207753Smm // Call the match finder. It returns the number of length-distance 26207753Smm // pairs found. 27207753Smm // FIXME: Minimum count is zero, what _exactly_ is the maximum? 28207753Smm const uint32_t count = mf->find(mf, matches); 29207753Smm 30207753Smm // Length of the longest match; assume that no matches were found 31207753Smm // and thus the maximum length is zero. 32207753Smm uint32_t len_best = 0; 33207753Smm 34207753Smm if (count > 0) { 35207753Smm#ifndef NDEBUG 36207753Smm // Validate the matches. 37207753Smm for (uint32_t i = 0; i < count; ++i) { 38207753Smm assert(matches[i].len <= mf->nice_len); 39207753Smm assert(matches[i].dist < mf->read_pos); 40207753Smm assert(memcmp(mf_ptr(mf) - 1, 41207753Smm mf_ptr(mf) - matches[i].dist - 2, 42207753Smm matches[i].len) == 0); 43207753Smm } 44207753Smm#endif 45207753Smm 46207753Smm // The last used element in the array contains 47207753Smm // the longest match. 48207753Smm len_best = matches[count - 1].len; 49207753Smm 50207753Smm // If a match of maximum search length was found, try to 51207753Smm // extend the match to maximum possible length. 52207753Smm if (len_best == mf->nice_len) { 53207753Smm // The limit for the match length is either the 54207753Smm // maximum match length supported by the LZ-based 55207753Smm // encoder or the number of bytes left in the 56207753Smm // dictionary, whichever is smaller. 57207753Smm uint32_t limit = mf_avail(mf) + 1; 58207753Smm if (limit > mf->match_len_max) 59207753Smm limit = mf->match_len_max; 60207753Smm 61207753Smm // Pointer to the byte we just ran through 62207753Smm // the match finder. 63207753Smm const uint8_t *p1 = mf_ptr(mf) - 1; 64207753Smm 65207753Smm // Pointer to the beginning of the match. We need -1 66207753Smm // here because the match distances are zero based. 67207753Smm const uint8_t *p2 = p1 - matches[count - 1].dist - 1; 68207753Smm 69278433Srpaulo len_best = lzma_memcmplen(p1, p2, len_best, limit); 70207753Smm } 71207753Smm } 72207753Smm 73207753Smm *count_ptr = count; 74207753Smm 75207753Smm // Finally update the read position to indicate that match finder was 76207753Smm // run for this dictionary offset. 77207753Smm ++mf->read_ahead; 78207753Smm 79207753Smm return len_best; 80207753Smm} 81207753Smm 82207753Smm 83207753Smm/// Hash value to indicate unused element in the hash. Since we start the 84207753Smm/// positions from dict_size + 1, zero is always too far to qualify 85207753Smm/// as usable match position. 86207753Smm#define EMPTY_HASH_VALUE 0 87207753Smm 88207753Smm 89207753Smm/// Normalization must be done when lzma_mf.offset + lzma_mf.read_pos 90207753Smm/// reaches MUST_NORMALIZE_POS. 91207753Smm#define MUST_NORMALIZE_POS UINT32_MAX 92207753Smm 93207753Smm 94207753Smm/// \brief Normalizes hash values 95207753Smm/// 96207753Smm/// The hash arrays store positions of match candidates. The positions are 97207753Smm/// relative to an arbitrary offset that is not the same as the absolute 98207753Smm/// offset in the input stream. The relative position of the current byte 99207753Smm/// is lzma_mf.offset + lzma_mf.read_pos. The distances of the matches are 100207753Smm/// the differences of the current read position and the position found from 101207753Smm/// the hash. 102207753Smm/// 103207753Smm/// To prevent integer overflows of the offsets stored in the hash arrays, 104207753Smm/// we need to "normalize" the stored values now and then. During the 105207753Smm/// normalization, we drop values that indicate distance greater than the 106207753Smm/// dictionary size, thus making space for new values. 107207753Smmstatic void 108207753Smmnormalize(lzma_mf *mf) 109207753Smm{ 110207753Smm assert(mf->read_pos + mf->offset == MUST_NORMALIZE_POS); 111207753Smm 112207753Smm // In future we may not want to touch the lowest bits, because there 113207753Smm // may be match finders that use larger resolution than one byte. 114207753Smm const uint32_t subvalue 115207753Smm = (MUST_NORMALIZE_POS - mf->cyclic_size); 116207753Smm // & (~(UINT32_C(1) << 10) - 1); 117207753Smm 118278433Srpaulo for (uint32_t i = 0; i < mf->hash_count; ++i) { 119207753Smm // If the distance is greater than the dictionary size, 120207753Smm // we can simply mark the hash element as empty. 121278433Srpaulo if (mf->hash[i] <= subvalue) 122278433Srpaulo mf->hash[i] = EMPTY_HASH_VALUE; 123278433Srpaulo else 124278433Srpaulo mf->hash[i] -= subvalue; 125278433Srpaulo } 126278433Srpaulo 127278433Srpaulo for (uint32_t i = 0; i < mf->sons_count; ++i) { 128278433Srpaulo // Do the same for mf->son. 129207753Smm // 130278433Srpaulo // NOTE: There may be uninitialized elements in mf->son. 131278433Srpaulo // Valgrind may complain that the "if" below depends on 132278433Srpaulo // an uninitialized value. In this case it is safe to ignore 133278433Srpaulo // the warning. See also the comments in lz_encoder_init() 134278433Srpaulo // in lz_encoder.c. 135278433Srpaulo if (mf->son[i] <= subvalue) 136278433Srpaulo mf->son[i] = EMPTY_HASH_VALUE; 137207753Smm else 138278433Srpaulo mf->son[i] -= subvalue; 139207753Smm } 140207753Smm 141207753Smm // Update offset to match the new locations. 142207753Smm mf->offset -= subvalue; 143207753Smm 144207753Smm return; 145207753Smm} 146207753Smm 147207753Smm 148207753Smm/// Mark the current byte as processed from point of view of the match finder. 149207753Smmstatic void 150207753Smmmove_pos(lzma_mf *mf) 151207753Smm{ 152207753Smm if (++mf->cyclic_pos == mf->cyclic_size) 153207753Smm mf->cyclic_pos = 0; 154207753Smm 155207753Smm ++mf->read_pos; 156207753Smm assert(mf->read_pos <= mf->write_pos); 157207753Smm 158207753Smm if (unlikely(mf->read_pos + mf->offset == UINT32_MAX)) 159207753Smm normalize(mf); 160207753Smm} 161207753Smm 162207753Smm 163207753Smm/// When flushing, we cannot run the match finder unless there is nice_len 164207753Smm/// bytes available in the dictionary. Instead, we skip running the match 165207753Smm/// finder (indicating that no match was found), and count how many bytes we 166207753Smm/// have ignored this way. 167207753Smm/// 168207753Smm/// When new data is given after the flushing was completed, the match finder 169207753Smm/// is restarted by rewinding mf->read_pos backwards by mf->pending. Then 170207753Smm/// the missed bytes are added to the hash using the match finder's skip 171207753Smm/// function (with small amount of input, it may start using mf->pending 172207753Smm/// again if flushing). 173207753Smm/// 174207753Smm/// Due to this rewinding, we don't touch cyclic_pos or test for 175207753Smm/// normalization. It will be done when the match finder's skip function 176207753Smm/// catches up after a flush. 177207753Smmstatic void 178207753Smmmove_pending(lzma_mf *mf) 179207753Smm{ 180207753Smm ++mf->read_pos; 181207753Smm assert(mf->read_pos <= mf->write_pos); 182207753Smm ++mf->pending; 183207753Smm} 184207753Smm 185207753Smm 186207753Smm/// Calculate len_limit and determine if there is enough input to run 187207753Smm/// the actual match finder code. Sets up "cur" and "pos". This macro 188207753Smm/// is used by all find functions and binary tree skip functions. Hash 189207753Smm/// chain skip function doesn't need len_limit so a simpler code is used 190207753Smm/// in them. 191207753Smm#define header(is_bt, len_min, ret_op) \ 192207753Smm uint32_t len_limit = mf_avail(mf); \ 193207753Smm if (mf->nice_len <= len_limit) { \ 194207753Smm len_limit = mf->nice_len; \ 195207753Smm } else if (len_limit < (len_min) \ 196207753Smm || (is_bt && mf->action == LZMA_SYNC_FLUSH)) { \ 197207753Smm assert(mf->action != LZMA_RUN); \ 198207753Smm move_pending(mf); \ 199207753Smm ret_op; \ 200207753Smm } \ 201207753Smm const uint8_t *cur = mf_ptr(mf); \ 202207753Smm const uint32_t pos = mf->read_pos + mf->offset 203207753Smm 204207753Smm 205207753Smm/// Header for find functions. "return 0" indicates that zero matches 206207753Smm/// were found. 207207753Smm#define header_find(is_bt, len_min) \ 208207753Smm header(is_bt, len_min, return 0); \ 209207753Smm uint32_t matches_count = 0 210207753Smm 211207753Smm 212207753Smm/// Header for a loop in a skip function. "continue" tells to skip the rest 213207753Smm/// of the code in the loop. 214207753Smm#define header_skip(is_bt, len_min) \ 215207753Smm header(is_bt, len_min, continue) 216207753Smm 217207753Smm 218207753Smm/// Calls hc_find_func() or bt_find_func() and calculates the total number 219207753Smm/// of matches found. Updates the dictionary position and returns the number 220207753Smm/// of matches found. 221207753Smm#define call_find(func, len_best) \ 222207753Smmdo { \ 223207753Smm matches_count = func(len_limit, pos, cur, cur_match, mf->depth, \ 224207753Smm mf->son, mf->cyclic_pos, mf->cyclic_size, \ 225207753Smm matches + matches_count, len_best) \ 226207753Smm - matches; \ 227207753Smm move_pos(mf); \ 228207753Smm return matches_count; \ 229207753Smm} while (0) 230207753Smm 231207753Smm 232207753Smm//////////////// 233207753Smm// Hash Chain // 234207753Smm//////////////// 235207753Smm 236207753Smm#if defined(HAVE_MF_HC3) || defined(HAVE_MF_HC4) 237207753Smm/// 238207753Smm/// 239207753Smm/// \param len_limit Don't look for matches longer than len_limit. 240207753Smm/// \param pos lzma_mf.read_pos + lzma_mf.offset 241207753Smm/// \param cur Pointer to current byte (mf_ptr(mf)) 242207753Smm/// \param cur_match Start position of the current match candidate 243207753Smm/// \param depth Maximum length of the hash chain 244207753Smm/// \param son lzma_mf.son (contains the hash chain) 245207753Smm/// \param cyclic_pos 246207753Smm/// \param cyclic_size 247207753Smm/// \param matches Array to hold the matches. 248207753Smm/// \param len_best The length of the longest match found so far. 249207753Smmstatic lzma_match * 250207753Smmhc_find_func( 251207753Smm const uint32_t len_limit, 252207753Smm const uint32_t pos, 253207753Smm const uint8_t *const cur, 254207753Smm uint32_t cur_match, 255207753Smm uint32_t depth, 256207753Smm uint32_t *const son, 257207753Smm const uint32_t cyclic_pos, 258207753Smm const uint32_t cyclic_size, 259207753Smm lzma_match *matches, 260207753Smm uint32_t len_best) 261207753Smm{ 262207753Smm son[cyclic_pos] = cur_match; 263207753Smm 264207753Smm while (true) { 265207753Smm const uint32_t delta = pos - cur_match; 266207753Smm if (depth-- == 0 || delta >= cyclic_size) 267207753Smm return matches; 268207753Smm 269207753Smm const uint8_t *const pb = cur - delta; 270207753Smm cur_match = son[cyclic_pos - delta 271207753Smm + (delta > cyclic_pos ? cyclic_size : 0)]; 272207753Smm 273207753Smm if (pb[len_best] == cur[len_best] && pb[0] == cur[0]) { 274278433Srpaulo uint32_t len = lzma_memcmplen(pb, cur, 1, len_limit); 275207753Smm 276207753Smm if (len_best < len) { 277207753Smm len_best = len; 278207753Smm matches->len = len; 279207753Smm matches->dist = delta - 1; 280207753Smm ++matches; 281207753Smm 282207753Smm if (len == len_limit) 283207753Smm return matches; 284207753Smm } 285207753Smm } 286207753Smm } 287207753Smm} 288207753Smm 289207753Smm 290207753Smm#define hc_find(len_best) \ 291207753Smm call_find(hc_find_func, len_best) 292207753Smm 293207753Smm 294207753Smm#define hc_skip() \ 295207753Smmdo { \ 296207753Smm mf->son[mf->cyclic_pos] = cur_match; \ 297207753Smm move_pos(mf); \ 298207753Smm} while (0) 299207753Smm 300207753Smm#endif 301207753Smm 302207753Smm 303207753Smm#ifdef HAVE_MF_HC3 304207753Smmextern uint32_t 305207753Smmlzma_mf_hc3_find(lzma_mf *mf, lzma_match *matches) 306207753Smm{ 307207753Smm header_find(false, 3); 308207753Smm 309207753Smm hash_3_calc(); 310207753Smm 311207753Smm const uint32_t delta2 = pos - mf->hash[hash_2_value]; 312207753Smm const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value]; 313207753Smm 314207753Smm mf->hash[hash_2_value] = pos; 315207753Smm mf->hash[FIX_3_HASH_SIZE + hash_value] = pos; 316207753Smm 317207753Smm uint32_t len_best = 2; 318207753Smm 319207753Smm if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) { 320278433Srpaulo len_best = lzma_memcmplen(cur - delta2, cur, 321278433Srpaulo len_best, len_limit); 322207753Smm 323207753Smm matches[0].len = len_best; 324207753Smm matches[0].dist = delta2 - 1; 325207753Smm matches_count = 1; 326207753Smm 327207753Smm if (len_best == len_limit) { 328207753Smm hc_skip(); 329207753Smm return 1; // matches_count 330207753Smm } 331207753Smm } 332207753Smm 333207753Smm hc_find(len_best); 334207753Smm} 335207753Smm 336207753Smm 337207753Smmextern void 338207753Smmlzma_mf_hc3_skip(lzma_mf *mf, uint32_t amount) 339207753Smm{ 340207753Smm do { 341207753Smm if (mf_avail(mf) < 3) { 342207753Smm move_pending(mf); 343207753Smm continue; 344207753Smm } 345207753Smm 346207753Smm const uint8_t *cur = mf_ptr(mf); 347207753Smm const uint32_t pos = mf->read_pos + mf->offset; 348207753Smm 349207753Smm hash_3_calc(); 350207753Smm 351207753Smm const uint32_t cur_match 352207753Smm = mf->hash[FIX_3_HASH_SIZE + hash_value]; 353207753Smm 354207753Smm mf->hash[hash_2_value] = pos; 355207753Smm mf->hash[FIX_3_HASH_SIZE + hash_value] = pos; 356207753Smm 357207753Smm hc_skip(); 358207753Smm 359207753Smm } while (--amount != 0); 360207753Smm} 361207753Smm#endif 362207753Smm 363207753Smm 364207753Smm#ifdef HAVE_MF_HC4 365207753Smmextern uint32_t 366207753Smmlzma_mf_hc4_find(lzma_mf *mf, lzma_match *matches) 367207753Smm{ 368207753Smm header_find(false, 4); 369207753Smm 370207753Smm hash_4_calc(); 371207753Smm 372207753Smm uint32_t delta2 = pos - mf->hash[hash_2_value]; 373207753Smm const uint32_t delta3 374207753Smm = pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value]; 375207753Smm const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value]; 376207753Smm 377207753Smm mf->hash[hash_2_value ] = pos; 378207753Smm mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos; 379207753Smm mf->hash[FIX_4_HASH_SIZE + hash_value] = pos; 380207753Smm 381207753Smm uint32_t len_best = 1; 382207753Smm 383207753Smm if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) { 384207753Smm len_best = 2; 385207753Smm matches[0].len = 2; 386207753Smm matches[0].dist = delta2 - 1; 387207753Smm matches_count = 1; 388207753Smm } 389207753Smm 390207753Smm if (delta2 != delta3 && delta3 < mf->cyclic_size 391207753Smm && *(cur - delta3) == *cur) { 392207753Smm len_best = 3; 393207753Smm matches[matches_count++].dist = delta3 - 1; 394207753Smm delta2 = delta3; 395207753Smm } 396207753Smm 397207753Smm if (matches_count != 0) { 398278433Srpaulo len_best = lzma_memcmplen(cur - delta2, cur, 399278433Srpaulo len_best, len_limit); 400207753Smm 401207753Smm matches[matches_count - 1].len = len_best; 402207753Smm 403207753Smm if (len_best == len_limit) { 404207753Smm hc_skip(); 405207753Smm return matches_count; 406207753Smm } 407207753Smm } 408207753Smm 409207753Smm if (len_best < 3) 410207753Smm len_best = 3; 411207753Smm 412207753Smm hc_find(len_best); 413207753Smm} 414207753Smm 415207753Smm 416207753Smmextern void 417207753Smmlzma_mf_hc4_skip(lzma_mf *mf, uint32_t amount) 418207753Smm{ 419207753Smm do { 420207753Smm if (mf_avail(mf) < 4) { 421207753Smm move_pending(mf); 422207753Smm continue; 423207753Smm } 424207753Smm 425207753Smm const uint8_t *cur = mf_ptr(mf); 426207753Smm const uint32_t pos = mf->read_pos + mf->offset; 427207753Smm 428207753Smm hash_4_calc(); 429207753Smm 430207753Smm const uint32_t cur_match 431207753Smm = mf->hash[FIX_4_HASH_SIZE + hash_value]; 432207753Smm 433207753Smm mf->hash[hash_2_value] = pos; 434207753Smm mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos; 435207753Smm mf->hash[FIX_4_HASH_SIZE + hash_value] = pos; 436207753Smm 437207753Smm hc_skip(); 438207753Smm 439207753Smm } while (--amount != 0); 440207753Smm} 441207753Smm#endif 442207753Smm 443207753Smm 444207753Smm///////////////// 445207753Smm// Binary Tree // 446207753Smm///////////////// 447207753Smm 448207753Smm#if defined(HAVE_MF_BT2) || defined(HAVE_MF_BT3) || defined(HAVE_MF_BT4) 449207753Smmstatic lzma_match * 450207753Smmbt_find_func( 451207753Smm const uint32_t len_limit, 452207753Smm const uint32_t pos, 453207753Smm const uint8_t *const cur, 454207753Smm uint32_t cur_match, 455207753Smm uint32_t depth, 456207753Smm uint32_t *const son, 457207753Smm const uint32_t cyclic_pos, 458207753Smm const uint32_t cyclic_size, 459207753Smm lzma_match *matches, 460207753Smm uint32_t len_best) 461207753Smm{ 462207753Smm uint32_t *ptr0 = son + (cyclic_pos << 1) + 1; 463207753Smm uint32_t *ptr1 = son + (cyclic_pos << 1); 464207753Smm 465207753Smm uint32_t len0 = 0; 466207753Smm uint32_t len1 = 0; 467207753Smm 468207753Smm while (true) { 469207753Smm const uint32_t delta = pos - cur_match; 470207753Smm if (depth-- == 0 || delta >= cyclic_size) { 471207753Smm *ptr0 = EMPTY_HASH_VALUE; 472207753Smm *ptr1 = EMPTY_HASH_VALUE; 473207753Smm return matches; 474207753Smm } 475207753Smm 476207753Smm uint32_t *const pair = son + ((cyclic_pos - delta 477207753Smm + (delta > cyclic_pos ? cyclic_size : 0)) 478207753Smm << 1); 479207753Smm 480207753Smm const uint8_t *const pb = cur - delta; 481213700Smm uint32_t len = my_min(len0, len1); 482207753Smm 483207753Smm if (pb[len] == cur[len]) { 484278433Srpaulo len = lzma_memcmplen(pb, cur, len + 1, len_limit); 485207753Smm 486207753Smm if (len_best < len) { 487207753Smm len_best = len; 488207753Smm matches->len = len; 489207753Smm matches->dist = delta - 1; 490207753Smm ++matches; 491207753Smm 492207753Smm if (len == len_limit) { 493207753Smm *ptr1 = pair[0]; 494207753Smm *ptr0 = pair[1]; 495207753Smm return matches; 496207753Smm } 497207753Smm } 498207753Smm } 499207753Smm 500207753Smm if (pb[len] < cur[len]) { 501207753Smm *ptr1 = cur_match; 502207753Smm ptr1 = pair + 1; 503207753Smm cur_match = *ptr1; 504207753Smm len1 = len; 505207753Smm } else { 506207753Smm *ptr0 = cur_match; 507207753Smm ptr0 = pair; 508207753Smm cur_match = *ptr0; 509207753Smm len0 = len; 510207753Smm } 511207753Smm } 512207753Smm} 513207753Smm 514207753Smm 515207753Smmstatic void 516207753Smmbt_skip_func( 517207753Smm const uint32_t len_limit, 518207753Smm const uint32_t pos, 519207753Smm const uint8_t *const cur, 520207753Smm uint32_t cur_match, 521207753Smm uint32_t depth, 522207753Smm uint32_t *const son, 523207753Smm const uint32_t cyclic_pos, 524207753Smm const uint32_t cyclic_size) 525207753Smm{ 526207753Smm uint32_t *ptr0 = son + (cyclic_pos << 1) + 1; 527207753Smm uint32_t *ptr1 = son + (cyclic_pos << 1); 528207753Smm 529207753Smm uint32_t len0 = 0; 530207753Smm uint32_t len1 = 0; 531207753Smm 532207753Smm while (true) { 533207753Smm const uint32_t delta = pos - cur_match; 534207753Smm if (depth-- == 0 || delta >= cyclic_size) { 535207753Smm *ptr0 = EMPTY_HASH_VALUE; 536207753Smm *ptr1 = EMPTY_HASH_VALUE; 537207753Smm return; 538207753Smm } 539207753Smm 540207753Smm uint32_t *pair = son + ((cyclic_pos - delta 541207753Smm + (delta > cyclic_pos ? cyclic_size : 0)) 542207753Smm << 1); 543207753Smm const uint8_t *pb = cur - delta; 544213700Smm uint32_t len = my_min(len0, len1); 545207753Smm 546207753Smm if (pb[len] == cur[len]) { 547278433Srpaulo len = lzma_memcmplen(pb, cur, len + 1, len_limit); 548207753Smm 549207753Smm if (len == len_limit) { 550207753Smm *ptr1 = pair[0]; 551207753Smm *ptr0 = pair[1]; 552207753Smm return; 553207753Smm } 554207753Smm } 555207753Smm 556207753Smm if (pb[len] < cur[len]) { 557207753Smm *ptr1 = cur_match; 558207753Smm ptr1 = pair + 1; 559207753Smm cur_match = *ptr1; 560207753Smm len1 = len; 561207753Smm } else { 562207753Smm *ptr0 = cur_match; 563207753Smm ptr0 = pair; 564207753Smm cur_match = *ptr0; 565207753Smm len0 = len; 566207753Smm } 567207753Smm } 568207753Smm} 569207753Smm 570207753Smm 571207753Smm#define bt_find(len_best) \ 572207753Smm call_find(bt_find_func, len_best) 573207753Smm 574207753Smm#define bt_skip() \ 575207753Smmdo { \ 576207753Smm bt_skip_func(len_limit, pos, cur, cur_match, mf->depth, \ 577207753Smm mf->son, mf->cyclic_pos, \ 578207753Smm mf->cyclic_size); \ 579207753Smm move_pos(mf); \ 580207753Smm} while (0) 581207753Smm 582207753Smm#endif 583207753Smm 584207753Smm 585207753Smm#ifdef HAVE_MF_BT2 586207753Smmextern uint32_t 587207753Smmlzma_mf_bt2_find(lzma_mf *mf, lzma_match *matches) 588207753Smm{ 589207753Smm header_find(true, 2); 590207753Smm 591207753Smm hash_2_calc(); 592207753Smm 593207753Smm const uint32_t cur_match = mf->hash[hash_value]; 594207753Smm mf->hash[hash_value] = pos; 595207753Smm 596207753Smm bt_find(1); 597207753Smm} 598207753Smm 599207753Smm 600207753Smmextern void 601207753Smmlzma_mf_bt2_skip(lzma_mf *mf, uint32_t amount) 602207753Smm{ 603207753Smm do { 604207753Smm header_skip(true, 2); 605207753Smm 606207753Smm hash_2_calc(); 607207753Smm 608207753Smm const uint32_t cur_match = mf->hash[hash_value]; 609207753Smm mf->hash[hash_value] = pos; 610207753Smm 611207753Smm bt_skip(); 612207753Smm 613207753Smm } while (--amount != 0); 614207753Smm} 615207753Smm#endif 616207753Smm 617207753Smm 618207753Smm#ifdef HAVE_MF_BT3 619207753Smmextern uint32_t 620207753Smmlzma_mf_bt3_find(lzma_mf *mf, lzma_match *matches) 621207753Smm{ 622207753Smm header_find(true, 3); 623207753Smm 624207753Smm hash_3_calc(); 625207753Smm 626207753Smm const uint32_t delta2 = pos - mf->hash[hash_2_value]; 627207753Smm const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value]; 628207753Smm 629207753Smm mf->hash[hash_2_value] = pos; 630207753Smm mf->hash[FIX_3_HASH_SIZE + hash_value] = pos; 631207753Smm 632207753Smm uint32_t len_best = 2; 633207753Smm 634207753Smm if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) { 635278433Srpaulo len_best = lzma_memcmplen( 636278433Srpaulo cur, cur - delta2, len_best, len_limit); 637207753Smm 638207753Smm matches[0].len = len_best; 639207753Smm matches[0].dist = delta2 - 1; 640207753Smm matches_count = 1; 641207753Smm 642207753Smm if (len_best == len_limit) { 643207753Smm bt_skip(); 644207753Smm return 1; // matches_count 645207753Smm } 646207753Smm } 647207753Smm 648207753Smm bt_find(len_best); 649207753Smm} 650207753Smm 651207753Smm 652207753Smmextern void 653207753Smmlzma_mf_bt3_skip(lzma_mf *mf, uint32_t amount) 654207753Smm{ 655207753Smm do { 656207753Smm header_skip(true, 3); 657207753Smm 658207753Smm hash_3_calc(); 659207753Smm 660207753Smm const uint32_t cur_match 661207753Smm = mf->hash[FIX_3_HASH_SIZE + hash_value]; 662207753Smm 663207753Smm mf->hash[hash_2_value] = pos; 664207753Smm mf->hash[FIX_3_HASH_SIZE + hash_value] = pos; 665207753Smm 666207753Smm bt_skip(); 667207753Smm 668207753Smm } while (--amount != 0); 669207753Smm} 670207753Smm#endif 671207753Smm 672207753Smm 673207753Smm#ifdef HAVE_MF_BT4 674207753Smmextern uint32_t 675207753Smmlzma_mf_bt4_find(lzma_mf *mf, lzma_match *matches) 676207753Smm{ 677207753Smm header_find(true, 4); 678207753Smm 679207753Smm hash_4_calc(); 680207753Smm 681207753Smm uint32_t delta2 = pos - mf->hash[hash_2_value]; 682207753Smm const uint32_t delta3 683207753Smm = pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value]; 684207753Smm const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value]; 685207753Smm 686207753Smm mf->hash[hash_2_value] = pos; 687207753Smm mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos; 688207753Smm mf->hash[FIX_4_HASH_SIZE + hash_value] = pos; 689207753Smm 690207753Smm uint32_t len_best = 1; 691207753Smm 692207753Smm if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) { 693207753Smm len_best = 2; 694207753Smm matches[0].len = 2; 695207753Smm matches[0].dist = delta2 - 1; 696207753Smm matches_count = 1; 697207753Smm } 698207753Smm 699207753Smm if (delta2 != delta3 && delta3 < mf->cyclic_size 700207753Smm && *(cur - delta3) == *cur) { 701207753Smm len_best = 3; 702207753Smm matches[matches_count++].dist = delta3 - 1; 703207753Smm delta2 = delta3; 704207753Smm } 705207753Smm 706207753Smm if (matches_count != 0) { 707278433Srpaulo len_best = lzma_memcmplen( 708278433Srpaulo cur, cur - delta2, len_best, len_limit); 709207753Smm 710207753Smm matches[matches_count - 1].len = len_best; 711207753Smm 712207753Smm if (len_best == len_limit) { 713207753Smm bt_skip(); 714207753Smm return matches_count; 715207753Smm } 716207753Smm } 717207753Smm 718207753Smm if (len_best < 3) 719207753Smm len_best = 3; 720207753Smm 721207753Smm bt_find(len_best); 722207753Smm} 723207753Smm 724207753Smm 725207753Smmextern void 726207753Smmlzma_mf_bt4_skip(lzma_mf *mf, uint32_t amount) 727207753Smm{ 728207753Smm do { 729207753Smm header_skip(true, 4); 730207753Smm 731207753Smm hash_4_calc(); 732207753Smm 733207753Smm const uint32_t cur_match 734207753Smm = mf->hash[FIX_4_HASH_SIZE + hash_value]; 735207753Smm 736207753Smm mf->hash[hash_2_value] = pos; 737207753Smm mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos; 738207753Smm mf->hash[FIX_4_HASH_SIZE + hash_value] = pos; 739207753Smm 740207753Smm bt_skip(); 741207753Smm 742207753Smm } while (--amount != 0); 743207753Smm} 744207753Smm#endif 745