src/liblzma/lzma/fastpos.h

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       fastpos.h
   4 /// \brief      Kind of two-bit version of bit scan reverse
   5 //
   6 //  Copyright (C) 1999-2007 Igor Pavlov
   7 //  Copyright (C) 2008 Lasse Collin
   8 //
   9 //  This library is free software; you can redistribute it and/or
  10 //  modify it under the terms of the GNU Lesser General Public
  11 //  License as published by the Free Software Foundation; either
  12 //  version 2.1 of the License, or (at your option) any later version.
  13 //
  14 //  This library is distributed in the hope that it will be useful,
  15 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17 //  Lesser General Public License for more details.
  18 //
  19 ///////////////////////////////////////////////////////////////////////////////
  20
  21 #ifndef LZMA_FASTPOS_H
  22 #define LZMA_FASTPOS_H
  23
  24 // LZMA encodes match distances (positions) by storing the highest two
  25 // bits using a six-bit value [0, 63], and then the missing lower bits.
  26 // Dictionary size is also stored using this encoding in the new .lzma
  27 // file format header.
  28 //
  29 // fastpos.h provides a way to quickly find out the correct six-bit
  30 // values. The following table gives some examples of this encoding:
  31 //
  32 //      pos   return
  33 //       0       0
  34 //       1       1
  35 //       2       2
  36 //       3       3
  37 //       4       4
  38 //       5       4
  39 //       6       5
  40 //       7       5
  41 //       8       6
  42 //      11       6
  43 //      12       7
  44 //     ...      ...
  45 //      15       7
  46 //      16       8
  47 //      17       8
  48 //     ...      ...
  49 //      23       8
  50 //      24       9
  51 //      25       9
  52 //     ...      ...
  53 //
  54 //
  55 // Provided functions or macros
  56 // ----------------------------
  57 //
  58 // get_pos_slot(pos) is the basic version. get_pos_slot_2(pos)
  59 // assumes that pos >= FULL_DISTANCES, thus the result is at least
  60 // FULL_DISTANCES_BITS * 2. Using get_pos_slot(pos) instead of
  61 // get_pos_slot_2(pos) would give the same result, but get_pos_slot_2(pos)
  62 // should be tiny bit faster due to the assumption being made.
  63 //
  64 //
  65 // Size vs. speed
  66 // --------------
  67 //
  68 // With some CPUs that have fast BSR (bit scan reverse) instruction, the
  69 // size optimized version is slightly faster than the bigger table based
  70 // approach. Such CPUs include Intel Pentium Pro, Pentium II, Pentium III
  71 // and Core 2 (possibly others). AMD K7 seems to have slower BSR, but that
  72 // would still have speed roughly comparable to the table version. Older
  73 // x86 CPUs like the original Pentium have very slow BSR; on those systems
  74 // the table version is a lot faster.
  75 //
  76 // On some CPUs, the table version is a lot faster when using position
  77 // dependent code, but with position independent code the size optimized
  78 // version is slightly faster. This occurs at least on 32-bit SPARC (no
  79 // ASM optimizations).
  80 //
  81 // I'm making the table version the default, because that has good speed
  82 // on all systems I have tried. The size optimized version is sometimes
  83 // slightly faster, but sometimes it is a lot slower.
  84 //
  85 // Finally, this code isn't a major bottle neck in LZMA encoding anyway.
  86
  87 #ifdef HAVE_SMALL
  88 #       include "bsr.h"
  89
  90 #       define get_pos_slot(pos) ((pos) <= 4 ? (pos) : get_pos_slot_2(pos))
  91
  92 static inline uint32_t
  93 get_pos_slot_2(uint32_t pos)
  94 {
  95         uint32_t i;
  96         lzma_bsr(i, pos);
  97         return (i + i) + ((pos >> (i - 1)) & 1);
  98 }
  99
 100
 101 #else
 102
 103 #define FASTPOS_BITS 13
 104
 105 extern const uint8_t lzma_fastpos[1 << FASTPOS_BITS];
 106
 107
 108 #define fastpos_shift(extra, n) \
 109         ((extra) + (n) * (FASTPOS_BITS - 1))
 110
 111 #define fastpos_limit(extra, n) \
 112         (UINT32_C(1) << (FASTPOS_BITS + fastpos_shift(extra, n)))
 113
 114 #define fastpos_result(pos, extra, n) \
 115         lzma_fastpos[(pos) >> fastpos_shift(extra, n)] \
 116                         + 2 * fastpos_shift(extra, n)
 117
 118
 119 static inline uint32_t
 120 get_pos_slot(uint32_t pos)
 121 {
 122         // If it is small enough, we can pick the result directly from
 123         // the precalculated table.
 124         if (pos < fastpos_limit(0, 0))
 125                 return lzma_fastpos[pos];
 126
 127         if (pos < fastpos_limit(0, 1))
 128                 return fastpos_result(pos, 0, 1);
 129
 130         return fastpos_result(pos, 0, 2);
 131 }
 132
 133
 134 #ifdef FULL_DISTANCES_BITS
 135 static inline uint32_t
 136 get_pos_slot_2(uint32_t pos)
 137 {
 138         // FIXME: This assert() cannot be enabled at the moment, because
 139         // lzma_getoptimum.c calls this function so that this assertion
 140         // fails; however, it ignores the result of this function when
 141         // this assert() would have failed.
 142         // assert(pos >= FULL_DISTANCES);
 143
 144         if (pos < fastpos_limit(FULL_DISTANCES_BITS - 1, 0))
 145                 return fastpos_result(pos, FULL_DISTANCES_BITS - 1, 0);
 146
 147         if (pos < fastpos_limit(FULL_DISTANCES_BITS - 1, 1))
 148                 return fastpos_result(pos, FULL_DISTANCES_BITS - 1, 1);
 149
 150         return fastpos_result(pos, FULL_DISTANCES_BITS - 1, 2);
 151 }
 152 #endif
 153
 154 #endif
 155
 156 #endif