1 ///////////////////////////////////////////////////////////////////////////////
4 /// \brief Kind of two-bit version of bit scan reverse
6 // Copyright (C) 1999-2007 Igor Pavlov
7 // Copyright (C) 2008 Lasse Collin
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.
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.
19 ///////////////////////////////////////////////////////////////////////////////
21 #ifndef LZMA_FASTPOS_H
22 #define LZMA_FASTPOS_H
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.
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:
55 // Provided functions or macros
56 // ----------------------------
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.
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.
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).
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.
85 // Finally, this code isn't a major bottle neck in LZMA encoding anyway.
90 # define get_pos_slot(pos) ((pos) <= 4 ? (pos) : get_pos_slot_2(pos))
92 static inline uint32_t
93 get_pos_slot_2(uint32_t pos)
97 return (i + i) + ((pos >> (i - 1)) & 1);
103 #define FASTPOS_BITS 13
105 extern const uint8_t lzma_fastpos[1 << FASTPOS_BITS];
108 #define fastpos_shift(extra, n) \
109 ((extra) + (n) * (FASTPOS_BITS - 1))
111 #define fastpos_limit(extra, n) \
112 (UINT32_C(1) << (FASTPOS_BITS + fastpos_shift(extra, n)))
114 #define fastpos_result(pos, extra, n) \
115 lzma_fastpos[(pos) >> fastpos_shift(extra, n)] \
116 + 2 * fastpos_shift(extra, n)
119 static inline uint32_t
120 get_pos_slot(uint32_t pos)
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];
127 if (pos < fastpos_limit(0, 1))
128 return fastpos_result(pos, 0, 1);
130 return fastpos_result(pos, 0, 2);
134 #ifdef FULL_DISTANCES_BITS
135 static inline uint32_t
136 get_pos_slot_2(uint32_t pos)
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);
144 if (pos < fastpos_limit(FULL_DISTANCES_BITS - 1, 0))
145 return fastpos_result(pos, FULL_DISTANCES_BITS - 1, 0);
147 if (pos < fastpos_limit(FULL_DISTANCES_BITS - 1, 1))
148 return fastpos_result(pos, FULL_DISTANCES_BITS - 1, 1);
150 return fastpos_result(pos, FULL_DISTANCES_BITS - 1, 2);