diff options
author | Denys Vlasenko <vda.linux@googlemail.com> | 2010-11-03 02:38:31 +0100 |
---|---|---|
committer | Denys Vlasenko <vda.linux@googlemail.com> | 2010-11-03 02:38:31 +0100 |
commit | 833d4e7f84f59099ee66eabfa3457ebb7d37eaa8 (patch) | |
tree | 3be84e1049707ce8077291065fe3689497c69b9c /archival/libarchive/unxz/xz_lzma2.h | |
parent | 5e9934028aa030312a1a2e2e32d5ceade8672beb (diff) | |
download | busybox-w32-833d4e7f84f59099ee66eabfa3457ebb7d37eaa8.tar.gz busybox-w32-833d4e7f84f59099ee66eabfa3457ebb7d37eaa8.tar.bz2 busybox-w32-833d4e7f84f59099ee66eabfa3457ebb7d37eaa8.zip |
rename archival/libunarchive -> archival/libarchive; move bz/ into it
Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
Diffstat (limited to 'archival/libarchive/unxz/xz_lzma2.h')
-rw-r--r-- | archival/libarchive/unxz/xz_lzma2.h | 204 |
1 files changed, 204 insertions, 0 deletions
diff --git a/archival/libarchive/unxz/xz_lzma2.h b/archival/libarchive/unxz/xz_lzma2.h new file mode 100644 index 000000000..47f21afbc --- /dev/null +++ b/archival/libarchive/unxz/xz_lzma2.h | |||
@@ -0,0 +1,204 @@ | |||
1 | /* | ||
2 | * LZMA2 definitions | ||
3 | * | ||
4 | * Authors: Lasse Collin <lasse.collin@tukaani.org> | ||
5 | * Igor Pavlov <http://7-zip.org/> | ||
6 | * | ||
7 | * This file has been put into the public domain. | ||
8 | * You can do whatever you want with this file. | ||
9 | */ | ||
10 | |||
11 | #ifndef XZ_LZMA2_H | ||
12 | #define XZ_LZMA2_H | ||
13 | |||
14 | /* Range coder constants */ | ||
15 | #define RC_SHIFT_BITS 8 | ||
16 | #define RC_TOP_BITS 24 | ||
17 | #define RC_TOP_VALUE (1 << RC_TOP_BITS) | ||
18 | #define RC_BIT_MODEL_TOTAL_BITS 11 | ||
19 | #define RC_BIT_MODEL_TOTAL (1 << RC_BIT_MODEL_TOTAL_BITS) | ||
20 | #define RC_MOVE_BITS 5 | ||
21 | |||
22 | /* | ||
23 | * Maximum number of position states. A position state is the lowest pb | ||
24 | * number of bits of the current uncompressed offset. In some places there | ||
25 | * are different sets of probabilities for different position states. | ||
26 | */ | ||
27 | #define POS_STATES_MAX (1 << 4) | ||
28 | |||
29 | /* | ||
30 | * This enum is used to track which LZMA symbols have occurred most recently | ||
31 | * and in which order. This information is used to predict the next symbol. | ||
32 | * | ||
33 | * Symbols: | ||
34 | * - Literal: One 8-bit byte | ||
35 | * - Match: Repeat a chunk of data at some distance | ||
36 | * - Long repeat: Multi-byte match at a recently seen distance | ||
37 | * - Short repeat: One-byte repeat at a recently seen distance | ||
38 | * | ||
39 | * The symbol names are in from STATE_oldest_older_previous. REP means | ||
40 | * either short or long repeated match, and NONLIT means any non-literal. | ||
41 | */ | ||
42 | enum lzma_state { | ||
43 | STATE_LIT_LIT, | ||
44 | STATE_MATCH_LIT_LIT, | ||
45 | STATE_REP_LIT_LIT, | ||
46 | STATE_SHORTREP_LIT_LIT, | ||
47 | STATE_MATCH_LIT, | ||
48 | STATE_REP_LIT, | ||
49 | STATE_SHORTREP_LIT, | ||
50 | STATE_LIT_MATCH, | ||
51 | STATE_LIT_LONGREP, | ||
52 | STATE_LIT_SHORTREP, | ||
53 | STATE_NONLIT_MATCH, | ||
54 | STATE_NONLIT_REP | ||
55 | }; | ||
56 | |||
57 | /* Total number of states */ | ||
58 | #define STATES 12 | ||
59 | |||
60 | /* The lowest 7 states indicate that the previous state was a literal. */ | ||
61 | #define LIT_STATES 7 | ||
62 | |||
63 | /* Indicate that the latest symbol was a literal. */ | ||
64 | static inline void XZ_FUNC lzma_state_literal(enum lzma_state *state) | ||
65 | { | ||
66 | if (*state <= STATE_SHORTREP_LIT_LIT) | ||
67 | *state = STATE_LIT_LIT; | ||
68 | else if (*state <= STATE_LIT_SHORTREP) | ||
69 | *state -= 3; | ||
70 | else | ||
71 | *state -= 6; | ||
72 | } | ||
73 | |||
74 | /* Indicate that the latest symbol was a match. */ | ||
75 | static inline void XZ_FUNC lzma_state_match(enum lzma_state *state) | ||
76 | { | ||
77 | *state = *state < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH; | ||
78 | } | ||
79 | |||
80 | /* Indicate that the latest state was a long repeated match. */ | ||
81 | static inline void XZ_FUNC lzma_state_long_rep(enum lzma_state *state) | ||
82 | { | ||
83 | *state = *state < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP; | ||
84 | } | ||
85 | |||
86 | /* Indicate that the latest symbol was a short match. */ | ||
87 | static inline void XZ_FUNC lzma_state_short_rep(enum lzma_state *state) | ||
88 | { | ||
89 | *state = *state < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP; | ||
90 | } | ||
91 | |||
92 | /* Test if the previous symbol was a literal. */ | ||
93 | static inline bool XZ_FUNC lzma_state_is_literal(enum lzma_state state) | ||
94 | { | ||
95 | return state < LIT_STATES; | ||
96 | } | ||
97 | |||
98 | /* Each literal coder is divided in three sections: | ||
99 | * - 0x001-0x0FF: Without match byte | ||
100 | * - 0x101-0x1FF: With match byte; match bit is 0 | ||
101 | * - 0x201-0x2FF: With match byte; match bit is 1 | ||
102 | * | ||
103 | * Match byte is used when the previous LZMA symbol was something else than | ||
104 | * a literal (that is, it was some kind of match). | ||
105 | */ | ||
106 | #define LITERAL_CODER_SIZE 0x300 | ||
107 | |||
108 | /* Maximum number of literal coders */ | ||
109 | #define LITERAL_CODERS_MAX (1 << 4) | ||
110 | |||
111 | /* Minimum length of a match is two bytes. */ | ||
112 | #define MATCH_LEN_MIN 2 | ||
113 | |||
114 | /* Match length is encoded with 4, 5, or 10 bits. | ||
115 | * | ||
116 | * Length Bits | ||
117 | * 2-9 4 = Choice=0 + 3 bits | ||
118 | * 10-17 5 = Choice=1 + Choice2=0 + 3 bits | ||
119 | * 18-273 10 = Choice=1 + Choice2=1 + 8 bits | ||
120 | */ | ||
121 | #define LEN_LOW_BITS 3 | ||
122 | #define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS) | ||
123 | #define LEN_MID_BITS 3 | ||
124 | #define LEN_MID_SYMBOLS (1 << LEN_MID_BITS) | ||
125 | #define LEN_HIGH_BITS 8 | ||
126 | #define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS) | ||
127 | #define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS) | ||
128 | |||
129 | /* | ||
130 | * Maximum length of a match is 273 which is a result of the encoding | ||
131 | * described above. | ||
132 | */ | ||
133 | #define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1) | ||
134 | |||
135 | /* | ||
136 | * Different sets of probabilities are used for match distances that have | ||
137 | * very short match length: Lengths of 2, 3, and 4 bytes have a separate | ||
138 | * set of probabilities for each length. The matches with longer length | ||
139 | * use a shared set of probabilities. | ||
140 | */ | ||
141 | #define DIST_STATES 4 | ||
142 | |||
143 | /* | ||
144 | * Get the index of the appropriate probability array for decoding | ||
145 | * the distance slot. | ||
146 | */ | ||
147 | static inline uint32_t XZ_FUNC lzma_get_dist_state(uint32_t len) | ||
148 | { | ||
149 | return len < DIST_STATES + MATCH_LEN_MIN | ||
150 | ? len - MATCH_LEN_MIN : DIST_STATES - 1; | ||
151 | } | ||
152 | |||
153 | /* | ||
154 | * The highest two bits of a 32-bit match distance are encoded using six bits. | ||
155 | * This six-bit value is called a distance slot. This way encoding a 32-bit | ||
156 | * value takes 6-36 bits, larger values taking more bits. | ||
157 | */ | ||
158 | #define DIST_SLOT_BITS 6 | ||
159 | #define DIST_SLOTS (1 << DIST_SLOT_BITS) | ||
160 | |||
161 | /* Match distances up to 127 are fully encoded using probabilities. Since | ||
162 | * the highest two bits (distance slot) are always encoded using six bits, | ||
163 | * the distances 0-3 don't need any additional bits to encode, since the | ||
164 | * distance slot itself is the same as the actual distance. DIST_MODEL_START | ||
165 | * indicates the first distance slot where at least one additional bit is | ||
166 | * needed. | ||
167 | */ | ||
168 | #define DIST_MODEL_START 4 | ||
169 | |||
170 | /* | ||
171 | * Match distances greater than 127 are encoded in three pieces: | ||
172 | * - distance slot: the highest two bits | ||
173 | * - direct bits: 2-26 bits below the highest two bits | ||
174 | * - alignment bits: four lowest bits | ||
175 | * | ||
176 | * Direct bits don't use any probabilities. | ||
177 | * | ||
178 | * The distance slot value of 14 is for distances 128-191. | ||
179 | */ | ||
180 | #define DIST_MODEL_END 14 | ||
181 | |||
182 | /* Distance slots that indicate a distance <= 127. */ | ||
183 | #define FULL_DISTANCES_BITS (DIST_MODEL_END / 2) | ||
184 | #define FULL_DISTANCES (1 << FULL_DISTANCES_BITS) | ||
185 | |||
186 | /* | ||
187 | * For match distances greater than 127, only the highest two bits and the | ||
188 | * lowest four bits (alignment) is encoded using probabilities. | ||
189 | */ | ||
190 | #define ALIGN_BITS 4 | ||
191 | #define ALIGN_SIZE (1 << ALIGN_BITS) | ||
192 | #define ALIGN_MASK (ALIGN_SIZE - 1) | ||
193 | |||
194 | /* Total number of all probability variables */ | ||
195 | #define PROBS_TOTAL (1846 + LITERAL_CODERS_MAX * LITERAL_CODER_SIZE) | ||
196 | |||
197 | /* | ||
198 | * LZMA remembers the four most recent match distances. Reusing these | ||
199 | * distances tends to take less space than re-encoding the actual | ||
200 | * distance value. | ||
201 | */ | ||
202 | #define REPS 4 | ||
203 | |||
204 | #endif | ||