// SPDX-License-Identifier: 0BSD

///////////////////////////////////////////////////////////////////////////////

//

/// \file       fastpos.h

/// \brief      Kind of two-bit version of bit scan reverse

///

//  Authors:    Igor Pavlov

//              Lasse Collin

//

///////////////////////////////////////////////////////////////////////////////

#ifndef LZMA_FASTPOS_H

#define LZMA_FASTPOS_H

// LZMA encodes match distances by storing the highest two bits using

// a six-bit value [0, 63], and then the missing lower bits.

// Dictionary size is also stored using this encoding in the .xz

// file format header.

//

// fastpos.h provides a way to quickly find out the correct six-bit

// values. The following table gives some examples of this encoding:

//

//     dist   return

//       0       0

//       1       1

//       2       2

//       3       3

//       4       4

//       5       4

//       6       5

//       7       5

//       8       6

//      11       6

//      12       7

//     ...      ...

//      15       7

//      16       8

//      17       8

//     ...      ...

//      23       8

//      24       9

//      25       9

//     ...      ...

//

//

// Provided functions or macros

// ----------------------------

//

// get_dist_slot(dist) is the basic version. get_dist_slot_2(dist)

// assumes that dist >= FULL_DISTANCES, thus the result is at least

// FULL_DISTANCES_BITS * 2. Using get_dist_slot(dist) instead of

// get_dist_slot_2(dist) would give the same result, but get_dist_slot_2(dist)

// should be tiny bit faster due to the assumption being made.

//

//

// Size vs. speed

// --------------

//

// With some CPUs that have fast BSR (bit scan reverse) instruction, the

// size optimized version is slightly faster than the bigger table based

// approach. Such CPUs include Intel Pentium Pro, Pentium II, Pentium III

// and Core 2 (possibly others). AMD K7 seems to have slower BSR, but that

// would still have speed roughly comparable to the table version. Older

// x86 CPUs like the original Pentium have very slow BSR; on those systems

// the table version is a lot faster.

//

// On some CPUs, the table version is a lot faster when using position

// dependent code, but with position independent code the size optimized

// version is slightly faster. This occurs at least on 32-bit SPARC (no

// ASM optimizations).

//

// I'm making the table version the default, because that has good speed

// on all systems I have tried. The size optimized version is sometimes

// slightly faster, but sometimes it is a lot slower.

#ifdef HAVE_SMALL

# define get_dist_slot(dist) \

    ((dist) <= 4 ? (dist) : get_dist_slot_2(dist))

static inline uint32_t

get_dist_slot_2(uint32_t dist)

{

  const uint32_t i = bsr32(dist);

  return (i + i) + ((dist >> (i - 1)) & 1);

}

#else

#define FASTPOS_BITS 13

lzma_attr_visibility_hidden

extern const uint8_t lzma_fastpos[1 << FASTPOS_BITS];

#define fastpos_shift(extra, n) \

  ((extra) + (n) * (FASTPOS_BITS - 1))

#define fastpos_limit(extra, n) \

  (UINT32_C(1) << (FASTPOS_BITS + fastpos_shift(extra, n)))

#define fastpos_result(dist, extra, n) \

  (uint32_t)(lzma_fastpos[(dist) >> fastpos_shift(extra, n)]) \

      + 2 * fastpos_shift(extra, n)

static inline uint32_t

get_dist_slot(uint32_t dist)

{

  // If it is small enough, we can pick the result directly from

  // the precalculated table.

  if (dist < fastpos_limit(0, 0))

    return lzma_fastpos[dist];

  if (dist < fastpos_limit(0, 1))

    return fastpos_result(dist, 0, 1);

  return fastpos_result(dist, 0, 2);

}

lzma_encoder.c:get_dist_slot

Line

Count

Source

110

54.7k

{

111

  // If it is small enough, we can pick the result directly from

112

  // the precalculated table.

113

54.7k

  if (dist < fastpos_limit(0, 0))

114

54.7k

    return lzma_fastpos[dist];

115

116

0

  if (dist < fastpos_limit(0, 1))

117

0

    return fastpos_result(dist, 0, 1);

118

119

0

  return fastpos_result(dist, 0, 2);

120

0

}

lzma_encoder_optimum_normal.c:get_dist_slot

Line

Count

Source

110

295k

{

111

  // If it is small enough, we can pick the result directly from

112

  // the precalculated table.

113

295k

  if (dist < fastpos_limit(0, 0))

114

295k

    return lzma_fastpos[dist];

115

116

0

  if (dist < fastpos_limit(0, 1))

117

0

    return fastpos_result(dist, 0, 1);

118

119

0

  return fastpos_result(dist, 0, 2);

120

0

}

Unexecuted instantiation: fastpos_table.c:get_dist_slot

lzma2_encoder.c:get_dist_slot

Line

Count

Source

110

3.67k

{

111

  // If it is small enough, we can pick the result directly from

112

  // the precalculated table.

113

3.67k

  if (dist < fastpos_limit(0, 0))

114

0

    return lzma_fastpos[dist];

115

116

3.67k

  if (dist < fastpos_limit(0, 1))

117

3.67k

    return fastpos_result(dist, 0, 1);

118

119

0

  return fastpos_result(dist, 0, 2);

120

3.67k

}

#ifdef FULL_DISTANCES_BITS

static inline uint32_t

get_dist_slot_2(uint32_t dist)

{

  assert(dist >= FULL_DISTANCES);

  if (dist < fastpos_limit(FULL_DISTANCES_BITS - 1, 0))

    return fastpos_result(dist, FULL_DISTANCES_BITS - 1, 0);

  if (dist < fastpos_limit(FULL_DISTANCES_BITS - 1, 1))

    return fastpos_result(dist, FULL_DISTANCES_BITS - 1, 1);

  return fastpos_result(dist, FULL_DISTANCES_BITS - 1, 2);

}

Unexecuted instantiation: lzma_encoder.c:get_dist_slot_2

lzma_encoder_optimum_normal.c:get_dist_slot_2

Line

Count

Source

126

1.37M

{

127

1.37M

  assert(dist >= FULL_DISTANCES);

128

129

1.37M

  if (dist < fastpos_limit(FULL_DISTANCES_BITS - 1, 0))

130

1.37M

    return fastpos_result(dist, FULL_DISTANCES_BITS - 1, 0);

131

132

0

  if (dist < fastpos_limit(FULL_DISTANCES_BITS - 1, 1))

133

0

    return fastpos_result(dist, FULL_DISTANCES_BITS - 1, 1);

134

135

0

  return fastpos_result(dist, FULL_DISTANCES_BITS - 1, 2);

136

0

}

#endif

#endif

#endif