diff options
Diffstat (limited to 'archival/libarchive/bz/compress.c')
-rw-r--r-- | archival/libarchive/bz/compress.c | 685 |
1 files changed, 685 insertions, 0 deletions
diff --git a/archival/libarchive/bz/compress.c b/archival/libarchive/bz/compress.c new file mode 100644 index 000000000..6f1c70a08 --- /dev/null +++ b/archival/libarchive/bz/compress.c | |||
@@ -0,0 +1,685 @@ | |||
1 | /* | ||
2 | * bzip2 is written by Julian Seward <jseward@bzip.org>. | ||
3 | * Adapted for busybox by Denys Vlasenko <vda.linux@googlemail.com>. | ||
4 | * See README and LICENSE files in this directory for more information. | ||
5 | */ | ||
6 | |||
7 | /*-------------------------------------------------------------*/ | ||
8 | /*--- Compression machinery (not incl block sorting) ---*/ | ||
9 | /*--- compress.c ---*/ | ||
10 | /*-------------------------------------------------------------*/ | ||
11 | |||
12 | /* ------------------------------------------------------------------ | ||
13 | This file is part of bzip2/libbzip2, a program and library for | ||
14 | lossless, block-sorting data compression. | ||
15 | |||
16 | bzip2/libbzip2 version 1.0.4 of 20 December 2006 | ||
17 | Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org> | ||
18 | |||
19 | Please read the WARNING, DISCLAIMER and PATENTS sections in the | ||
20 | README file. | ||
21 | |||
22 | This program is released under the terms of the license contained | ||
23 | in the file LICENSE. | ||
24 | ------------------------------------------------------------------ */ | ||
25 | |||
26 | /* CHANGES | ||
27 | * 0.9.0 -- original version. | ||
28 | * 0.9.0a/b -- no changes in this file. | ||
29 | * 0.9.0c -- changed setting of nGroups in sendMTFValues() | ||
30 | * so as to do a bit better on small files | ||
31 | */ | ||
32 | |||
33 | /* #include "bzlib_private.h" */ | ||
34 | |||
35 | /*---------------------------------------------------*/ | ||
36 | /*--- Bit stream I/O ---*/ | ||
37 | /*---------------------------------------------------*/ | ||
38 | |||
39 | /*---------------------------------------------------*/ | ||
40 | static | ||
41 | void BZ2_bsInitWrite(EState* s) | ||
42 | { | ||
43 | s->bsLive = 0; | ||
44 | s->bsBuff = 0; | ||
45 | } | ||
46 | |||
47 | |||
48 | /*---------------------------------------------------*/ | ||
49 | static NOINLINE | ||
50 | void bsFinishWrite(EState* s) | ||
51 | { | ||
52 | while (s->bsLive > 0) { | ||
53 | s->zbits[s->numZ] = (uint8_t)(s->bsBuff >> 24); | ||
54 | s->numZ++; | ||
55 | s->bsBuff <<= 8; | ||
56 | s->bsLive -= 8; | ||
57 | } | ||
58 | } | ||
59 | |||
60 | |||
61 | /*---------------------------------------------------*/ | ||
62 | static | ||
63 | /* Helps only on level 5, on other levels hurts. ? */ | ||
64 | #if CONFIG_BZIP2_FEATURE_SPEED >= 5 | ||
65 | ALWAYS_INLINE | ||
66 | #endif | ||
67 | void bsW(EState* s, int32_t n, uint32_t v) | ||
68 | { | ||
69 | while (s->bsLive >= 8) { | ||
70 | s->zbits[s->numZ] = (uint8_t)(s->bsBuff >> 24); | ||
71 | s->numZ++; | ||
72 | s->bsBuff <<= 8; | ||
73 | s->bsLive -= 8; | ||
74 | } | ||
75 | s->bsBuff |= (v << (32 - s->bsLive - n)); | ||
76 | s->bsLive += n; | ||
77 | } | ||
78 | |||
79 | |||
80 | /*---------------------------------------------------*/ | ||
81 | static | ||
82 | void bsPutU32(EState* s, unsigned u) | ||
83 | { | ||
84 | bsW(s, 8, (u >> 24) & 0xff); | ||
85 | bsW(s, 8, (u >> 16) & 0xff); | ||
86 | bsW(s, 8, (u >> 8) & 0xff); | ||
87 | bsW(s, 8, u & 0xff); | ||
88 | } | ||
89 | |||
90 | |||
91 | /*---------------------------------------------------*/ | ||
92 | static | ||
93 | void bsPutU16(EState* s, unsigned u) | ||
94 | { | ||
95 | bsW(s, 8, (u >> 8) & 0xff); | ||
96 | bsW(s, 8, u & 0xff); | ||
97 | } | ||
98 | |||
99 | |||
100 | /*---------------------------------------------------*/ | ||
101 | /*--- The back end proper ---*/ | ||
102 | /*---------------------------------------------------*/ | ||
103 | |||
104 | /*---------------------------------------------------*/ | ||
105 | static | ||
106 | void makeMaps_e(EState* s) | ||
107 | { | ||
108 | int i; | ||
109 | s->nInUse = 0; | ||
110 | for (i = 0; i < 256; i++) { | ||
111 | if (s->inUse[i]) { | ||
112 | s->unseqToSeq[i] = s->nInUse; | ||
113 | s->nInUse++; | ||
114 | } | ||
115 | } | ||
116 | } | ||
117 | |||
118 | |||
119 | /*---------------------------------------------------*/ | ||
120 | static NOINLINE | ||
121 | void generateMTFValues(EState* s) | ||
122 | { | ||
123 | uint8_t yy[256]; | ||
124 | int32_t i, j; | ||
125 | int32_t zPend; | ||
126 | int32_t wr; | ||
127 | int32_t EOB; | ||
128 | |||
129 | /* | ||
130 | * After sorting (eg, here), | ||
131 | * s->arr1[0 .. s->nblock-1] holds sorted order, | ||
132 | * and | ||
133 | * ((uint8_t*)s->arr2)[0 .. s->nblock-1] | ||
134 | * holds the original block data. | ||
135 | * | ||
136 | * The first thing to do is generate the MTF values, | ||
137 | * and put them in ((uint16_t*)s->arr1)[0 .. s->nblock-1]. | ||
138 | * | ||
139 | * Because there are strictly fewer or equal MTF values | ||
140 | * than block values, ptr values in this area are overwritten | ||
141 | * with MTF values only when they are no longer needed. | ||
142 | * | ||
143 | * The final compressed bitstream is generated into the | ||
144 | * area starting at &((uint8_t*)s->arr2)[s->nblock] | ||
145 | * | ||
146 | * These storage aliases are set up in bzCompressInit(), | ||
147 | * except for the last one, which is arranged in | ||
148 | * compressBlock(). | ||
149 | */ | ||
150 | uint32_t* ptr = s->ptr; | ||
151 | uint8_t* block = s->block; | ||
152 | uint16_t* mtfv = s->mtfv; | ||
153 | |||
154 | makeMaps_e(s); | ||
155 | EOB = s->nInUse+1; | ||
156 | |||
157 | for (i = 0; i <= EOB; i++) | ||
158 | s->mtfFreq[i] = 0; | ||
159 | |||
160 | wr = 0; | ||
161 | zPend = 0; | ||
162 | for (i = 0; i < s->nInUse; i++) | ||
163 | yy[i] = (uint8_t) i; | ||
164 | |||
165 | for (i = 0; i < s->nblock; i++) { | ||
166 | uint8_t ll_i; | ||
167 | AssertD(wr <= i, "generateMTFValues(1)"); | ||
168 | j = ptr[i] - 1; | ||
169 | if (j < 0) | ||
170 | j += s->nblock; | ||
171 | ll_i = s->unseqToSeq[block[j]]; | ||
172 | AssertD(ll_i < s->nInUse, "generateMTFValues(2a)"); | ||
173 | |||
174 | if (yy[0] == ll_i) { | ||
175 | zPend++; | ||
176 | } else { | ||
177 | if (zPend > 0) { | ||
178 | zPend--; | ||
179 | while (1) { | ||
180 | if (zPend & 1) { | ||
181 | mtfv[wr] = BZ_RUNB; wr++; | ||
182 | s->mtfFreq[BZ_RUNB]++; | ||
183 | } else { | ||
184 | mtfv[wr] = BZ_RUNA; wr++; | ||
185 | s->mtfFreq[BZ_RUNA]++; | ||
186 | } | ||
187 | if (zPend < 2) break; | ||
188 | zPend = (uint32_t)(zPend - 2) / 2; | ||
189 | /* bbox: unsigned div is easier */ | ||
190 | }; | ||
191 | zPend = 0; | ||
192 | } | ||
193 | { | ||
194 | register uint8_t rtmp; | ||
195 | register uint8_t* ryy_j; | ||
196 | register uint8_t rll_i; | ||
197 | rtmp = yy[1]; | ||
198 | yy[1] = yy[0]; | ||
199 | ryy_j = &(yy[1]); | ||
200 | rll_i = ll_i; | ||
201 | while (rll_i != rtmp) { | ||
202 | register uint8_t rtmp2; | ||
203 | ryy_j++; | ||
204 | rtmp2 = rtmp; | ||
205 | rtmp = *ryy_j; | ||
206 | *ryy_j = rtmp2; | ||
207 | }; | ||
208 | yy[0] = rtmp; | ||
209 | j = ryy_j - &(yy[0]); | ||
210 | mtfv[wr] = j+1; | ||
211 | wr++; | ||
212 | s->mtfFreq[j+1]++; | ||
213 | } | ||
214 | } | ||
215 | } | ||
216 | |||
217 | if (zPend > 0) { | ||
218 | zPend--; | ||
219 | while (1) { | ||
220 | if (zPend & 1) { | ||
221 | mtfv[wr] = BZ_RUNB; | ||
222 | wr++; | ||
223 | s->mtfFreq[BZ_RUNB]++; | ||
224 | } else { | ||
225 | mtfv[wr] = BZ_RUNA; | ||
226 | wr++; | ||
227 | s->mtfFreq[BZ_RUNA]++; | ||
228 | } | ||
229 | if (zPend < 2) | ||
230 | break; | ||
231 | zPend = (uint32_t)(zPend - 2) / 2; | ||
232 | /* bbox: unsigned div is easier */ | ||
233 | }; | ||
234 | zPend = 0; | ||
235 | } | ||
236 | |||
237 | mtfv[wr] = EOB; | ||
238 | wr++; | ||
239 | s->mtfFreq[EOB]++; | ||
240 | |||
241 | s->nMTF = wr; | ||
242 | } | ||
243 | |||
244 | |||
245 | /*---------------------------------------------------*/ | ||
246 | #define BZ_LESSER_ICOST 0 | ||
247 | #define BZ_GREATER_ICOST 15 | ||
248 | |||
249 | static NOINLINE | ||
250 | void sendMTFValues(EState* s) | ||
251 | { | ||
252 | int32_t v, t, i, j, gs, ge, totc, bt, bc, iter; | ||
253 | int32_t nSelectors, alphaSize, minLen, maxLen, selCtr; | ||
254 | int32_t nGroups, nBytes; | ||
255 | |||
256 | /* | ||
257 | * uint8_t len[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
258 | * is a global since the decoder also needs it. | ||
259 | * | ||
260 | * int32_t code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
261 | * int32_t rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
262 | * are also globals only used in this proc. | ||
263 | * Made global to keep stack frame size small. | ||
264 | */ | ||
265 | #define code sendMTFValues__code | ||
266 | #define rfreq sendMTFValues__rfreq | ||
267 | #define len_pack sendMTFValues__len_pack | ||
268 | |||
269 | uint16_t cost[BZ_N_GROUPS]; | ||
270 | int32_t fave[BZ_N_GROUPS]; | ||
271 | |||
272 | uint16_t* mtfv = s->mtfv; | ||
273 | |||
274 | alphaSize = s->nInUse + 2; | ||
275 | for (t = 0; t < BZ_N_GROUPS; t++) | ||
276 | for (v = 0; v < alphaSize; v++) | ||
277 | s->len[t][v] = BZ_GREATER_ICOST; | ||
278 | |||
279 | /*--- Decide how many coding tables to use ---*/ | ||
280 | AssertH(s->nMTF > 0, 3001); | ||
281 | if (s->nMTF < 200) nGroups = 2; else | ||
282 | if (s->nMTF < 600) nGroups = 3; else | ||
283 | if (s->nMTF < 1200) nGroups = 4; else | ||
284 | if (s->nMTF < 2400) nGroups = 5; else | ||
285 | nGroups = 6; | ||
286 | |||
287 | /*--- Generate an initial set of coding tables ---*/ | ||
288 | { | ||
289 | int32_t nPart, remF, tFreq, aFreq; | ||
290 | |||
291 | nPart = nGroups; | ||
292 | remF = s->nMTF; | ||
293 | gs = 0; | ||
294 | while (nPart > 0) { | ||
295 | tFreq = remF / nPart; | ||
296 | ge = gs - 1; | ||
297 | aFreq = 0; | ||
298 | while (aFreq < tFreq && ge < alphaSize-1) { | ||
299 | ge++; | ||
300 | aFreq += s->mtfFreq[ge]; | ||
301 | } | ||
302 | |||
303 | if (ge > gs | ||
304 | && nPart != nGroups && nPart != 1 | ||
305 | && ((nGroups - nPart) % 2 == 1) /* bbox: can this be replaced by x & 1? */ | ||
306 | ) { | ||
307 | aFreq -= s->mtfFreq[ge]; | ||
308 | ge--; | ||
309 | } | ||
310 | |||
311 | for (v = 0; v < alphaSize; v++) | ||
312 | if (v >= gs && v <= ge) | ||
313 | s->len[nPart-1][v] = BZ_LESSER_ICOST; | ||
314 | else | ||
315 | s->len[nPart-1][v] = BZ_GREATER_ICOST; | ||
316 | |||
317 | nPart--; | ||
318 | gs = ge + 1; | ||
319 | remF -= aFreq; | ||
320 | } | ||
321 | } | ||
322 | |||
323 | /* | ||
324 | * Iterate up to BZ_N_ITERS times to improve the tables. | ||
325 | */ | ||
326 | for (iter = 0; iter < BZ_N_ITERS; iter++) { | ||
327 | for (t = 0; t < nGroups; t++) | ||
328 | fave[t] = 0; | ||
329 | |||
330 | for (t = 0; t < nGroups; t++) | ||
331 | for (v = 0; v < alphaSize; v++) | ||
332 | s->rfreq[t][v] = 0; | ||
333 | |||
334 | #if CONFIG_BZIP2_FEATURE_SPEED >= 5 | ||
335 | /* | ||
336 | * Set up an auxiliary length table which is used to fast-track | ||
337 | * the common case (nGroups == 6). | ||
338 | */ | ||
339 | if (nGroups == 6) { | ||
340 | for (v = 0; v < alphaSize; v++) { | ||
341 | s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v]; | ||
342 | s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v]; | ||
343 | s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v]; | ||
344 | } | ||
345 | } | ||
346 | #endif | ||
347 | nSelectors = 0; | ||
348 | totc = 0; | ||
349 | gs = 0; | ||
350 | while (1) { | ||
351 | /*--- Set group start & end marks. --*/ | ||
352 | if (gs >= s->nMTF) | ||
353 | break; | ||
354 | ge = gs + BZ_G_SIZE - 1; | ||
355 | if (ge >= s->nMTF) | ||
356 | ge = s->nMTF-1; | ||
357 | |||
358 | /* | ||
359 | * Calculate the cost of this group as coded | ||
360 | * by each of the coding tables. | ||
361 | */ | ||
362 | for (t = 0; t < nGroups; t++) | ||
363 | cost[t] = 0; | ||
364 | #if CONFIG_BZIP2_FEATURE_SPEED >= 5 | ||
365 | if (nGroups == 6 && 50 == ge-gs+1) { | ||
366 | /*--- fast track the common case ---*/ | ||
367 | register uint32_t cost01, cost23, cost45; | ||
368 | register uint16_t icv; | ||
369 | cost01 = cost23 = cost45 = 0; | ||
370 | #define BZ_ITER(nn) \ | ||
371 | icv = mtfv[gs+(nn)]; \ | ||
372 | cost01 += s->len_pack[icv][0]; \ | ||
373 | cost23 += s->len_pack[icv][1]; \ | ||
374 | cost45 += s->len_pack[icv][2]; | ||
375 | BZ_ITER(0); BZ_ITER(1); BZ_ITER(2); BZ_ITER(3); BZ_ITER(4); | ||
376 | BZ_ITER(5); BZ_ITER(6); BZ_ITER(7); BZ_ITER(8); BZ_ITER(9); | ||
377 | BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14); | ||
378 | BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19); | ||
379 | BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24); | ||
380 | BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29); | ||
381 | BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34); | ||
382 | BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39); | ||
383 | BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44); | ||
384 | BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49); | ||
385 | #undef BZ_ITER | ||
386 | cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16; | ||
387 | cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16; | ||
388 | cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16; | ||
389 | |||
390 | } else | ||
391 | #endif | ||
392 | { | ||
393 | /*--- slow version which correctly handles all situations ---*/ | ||
394 | for (i = gs; i <= ge; i++) { | ||
395 | uint16_t icv = mtfv[i]; | ||
396 | for (t = 0; t < nGroups; t++) | ||
397 | cost[t] += s->len[t][icv]; | ||
398 | } | ||
399 | } | ||
400 | /* | ||
401 | * Find the coding table which is best for this group, | ||
402 | * and record its identity in the selector table. | ||
403 | */ | ||
404 | /*bc = 999999999;*/ | ||
405 | /*bt = -1;*/ | ||
406 | bc = cost[0]; | ||
407 | bt = 0; | ||
408 | for (t = 1 /*0*/; t < nGroups; t++) { | ||
409 | if (cost[t] < bc) { | ||
410 | bc = cost[t]; | ||
411 | bt = t; | ||
412 | } | ||
413 | } | ||
414 | totc += bc; | ||
415 | fave[bt]++; | ||
416 | s->selector[nSelectors] = bt; | ||
417 | nSelectors++; | ||
418 | |||
419 | /* | ||
420 | * Increment the symbol frequencies for the selected table. | ||
421 | */ | ||
422 | /* 1% faster compress. +800 bytes */ | ||
423 | #if CONFIG_BZIP2_FEATURE_SPEED >= 4 | ||
424 | if (nGroups == 6 && 50 == ge-gs+1) { | ||
425 | /*--- fast track the common case ---*/ | ||
426 | #define BZ_ITUR(nn) s->rfreq[bt][mtfv[gs + (nn)]]++ | ||
427 | BZ_ITUR(0); BZ_ITUR(1); BZ_ITUR(2); BZ_ITUR(3); BZ_ITUR(4); | ||
428 | BZ_ITUR(5); BZ_ITUR(6); BZ_ITUR(7); BZ_ITUR(8); BZ_ITUR(9); | ||
429 | BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14); | ||
430 | BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19); | ||
431 | BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24); | ||
432 | BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29); | ||
433 | BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34); | ||
434 | BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39); | ||
435 | BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44); | ||
436 | BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49); | ||
437 | #undef BZ_ITUR | ||
438 | gs = ge + 1; | ||
439 | } else | ||
440 | #endif | ||
441 | { | ||
442 | /*--- slow version which correctly handles all situations ---*/ | ||
443 | while (gs <= ge) { | ||
444 | s->rfreq[bt][mtfv[gs]]++; | ||
445 | gs++; | ||
446 | } | ||
447 | /* already is: gs = ge + 1; */ | ||
448 | } | ||
449 | } | ||
450 | |||
451 | /* | ||
452 | * Recompute the tables based on the accumulated frequencies. | ||
453 | */ | ||
454 | /* maxLen was changed from 20 to 17 in bzip2-1.0.3. See | ||
455 | * comment in huffman.c for details. */ | ||
456 | for (t = 0; t < nGroups; t++) | ||
457 | BZ2_hbMakeCodeLengths(s, &(s->len[t][0]), &(s->rfreq[t][0]), alphaSize, 17 /*20*/); | ||
458 | } | ||
459 | |||
460 | AssertH(nGroups < 8, 3002); | ||
461 | AssertH(nSelectors < 32768 && nSelectors <= (2 + (900000 / BZ_G_SIZE)), 3003); | ||
462 | |||
463 | /*--- Compute MTF values for the selectors. ---*/ | ||
464 | { | ||
465 | uint8_t pos[BZ_N_GROUPS], ll_i, tmp2, tmp; | ||
466 | |||
467 | for (i = 0; i < nGroups; i++) | ||
468 | pos[i] = i; | ||
469 | for (i = 0; i < nSelectors; i++) { | ||
470 | ll_i = s->selector[i]; | ||
471 | j = 0; | ||
472 | tmp = pos[j]; | ||
473 | while (ll_i != tmp) { | ||
474 | j++; | ||
475 | tmp2 = tmp; | ||
476 | tmp = pos[j]; | ||
477 | pos[j] = tmp2; | ||
478 | }; | ||
479 | pos[0] = tmp; | ||
480 | s->selectorMtf[i] = j; | ||
481 | } | ||
482 | }; | ||
483 | |||
484 | /*--- Assign actual codes for the tables. --*/ | ||
485 | for (t = 0; t < nGroups; t++) { | ||
486 | minLen = 32; | ||
487 | maxLen = 0; | ||
488 | for (i = 0; i < alphaSize; i++) { | ||
489 | if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; | ||
490 | if (s->len[t][i] < minLen) minLen = s->len[t][i]; | ||
491 | } | ||
492 | AssertH(!(maxLen > 17 /*20*/), 3004); | ||
493 | AssertH(!(minLen < 1), 3005); | ||
494 | BZ2_hbAssignCodes(&(s->code[t][0]), &(s->len[t][0]), minLen, maxLen, alphaSize); | ||
495 | } | ||
496 | |||
497 | /*--- Transmit the mapping table. ---*/ | ||
498 | { | ||
499 | /* bbox: optimized a bit more than in bzip2 */ | ||
500 | int inUse16 = 0; | ||
501 | for (i = 0; i < 16; i++) { | ||
502 | if (sizeof(long) <= 4) { | ||
503 | inUse16 = inUse16*2 + | ||
504 | ((*(uint32_t*)&(s->inUse[i * 16 + 0]) | ||
505 | | *(uint32_t*)&(s->inUse[i * 16 + 4]) | ||
506 | | *(uint32_t*)&(s->inUse[i * 16 + 8]) | ||
507 | | *(uint32_t*)&(s->inUse[i * 16 + 12])) != 0); | ||
508 | } else { /* Our CPU can do better */ | ||
509 | inUse16 = inUse16*2 + | ||
510 | ((*(uint64_t*)&(s->inUse[i * 16 + 0]) | ||
511 | | *(uint64_t*)&(s->inUse[i * 16 + 8])) != 0); | ||
512 | } | ||
513 | } | ||
514 | |||
515 | nBytes = s->numZ; | ||
516 | bsW(s, 16, inUse16); | ||
517 | |||
518 | inUse16 <<= (sizeof(int)*8 - 16); /* move 15th bit into sign bit */ | ||
519 | for (i = 0; i < 16; i++) { | ||
520 | if (inUse16 < 0) { | ||
521 | unsigned v16 = 0; | ||
522 | for (j = 0; j < 16; j++) | ||
523 | v16 = v16*2 + s->inUse[i * 16 + j]; | ||
524 | bsW(s, 16, v16); | ||
525 | } | ||
526 | inUse16 <<= 1; | ||
527 | } | ||
528 | } | ||
529 | |||
530 | /*--- Now the selectors. ---*/ | ||
531 | nBytes = s->numZ; | ||
532 | bsW(s, 3, nGroups); | ||
533 | bsW(s, 15, nSelectors); | ||
534 | for (i = 0; i < nSelectors; i++) { | ||
535 | for (j = 0; j < s->selectorMtf[i]; j++) | ||
536 | bsW(s, 1, 1); | ||
537 | bsW(s, 1, 0); | ||
538 | } | ||
539 | |||
540 | /*--- Now the coding tables. ---*/ | ||
541 | nBytes = s->numZ; | ||
542 | |||
543 | for (t = 0; t < nGroups; t++) { | ||
544 | int32_t curr = s->len[t][0]; | ||
545 | bsW(s, 5, curr); | ||
546 | for (i = 0; i < alphaSize; i++) { | ||
547 | while (curr < s->len[t][i]) { bsW(s, 2, 2); curr++; /* 10 */ }; | ||
548 | while (curr > s->len[t][i]) { bsW(s, 2, 3); curr--; /* 11 */ }; | ||
549 | bsW(s, 1, 0); | ||
550 | } | ||
551 | } | ||
552 | |||
553 | /*--- And finally, the block data proper ---*/ | ||
554 | nBytes = s->numZ; | ||
555 | selCtr = 0; | ||
556 | gs = 0; | ||
557 | while (1) { | ||
558 | if (gs >= s->nMTF) | ||
559 | break; | ||
560 | ge = gs + BZ_G_SIZE - 1; | ||
561 | if (ge >= s->nMTF) | ||
562 | ge = s->nMTF-1; | ||
563 | AssertH(s->selector[selCtr] < nGroups, 3006); | ||
564 | |||
565 | /* Costs 1300 bytes and is _slower_ (on Intel Core 2) */ | ||
566 | #if 0 | ||
567 | if (nGroups == 6 && 50 == ge-gs+1) { | ||
568 | /*--- fast track the common case ---*/ | ||
569 | uint16_t mtfv_i; | ||
570 | uint8_t* s_len_sel_selCtr = &(s->len[s->selector[selCtr]][0]); | ||
571 | int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]); | ||
572 | #define BZ_ITAH(nn) \ | ||
573 | mtfv_i = mtfv[gs+(nn)]; \ | ||
574 | bsW(s, s_len_sel_selCtr[mtfv_i], s_code_sel_selCtr[mtfv_i]) | ||
575 | BZ_ITAH(0); BZ_ITAH(1); BZ_ITAH(2); BZ_ITAH(3); BZ_ITAH(4); | ||
576 | BZ_ITAH(5); BZ_ITAH(6); BZ_ITAH(7); BZ_ITAH(8); BZ_ITAH(9); | ||
577 | BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14); | ||
578 | BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19); | ||
579 | BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24); | ||
580 | BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29); | ||
581 | BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34); | ||
582 | BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39); | ||
583 | BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44); | ||
584 | BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49); | ||
585 | #undef BZ_ITAH | ||
586 | gs = ge+1; | ||
587 | } else | ||
588 | #endif | ||
589 | { | ||
590 | /*--- slow version which correctly handles all situations ---*/ | ||
591 | /* code is bit bigger, but moves multiply out of the loop */ | ||
592 | uint8_t* s_len_sel_selCtr = &(s->len [s->selector[selCtr]][0]); | ||
593 | int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]); | ||
594 | while (gs <= ge) { | ||
595 | bsW(s, | ||
596 | s_len_sel_selCtr[mtfv[gs]], | ||
597 | s_code_sel_selCtr[mtfv[gs]] | ||
598 | ); | ||
599 | gs++; | ||
600 | } | ||
601 | /* already is: gs = ge+1; */ | ||
602 | } | ||
603 | selCtr++; | ||
604 | } | ||
605 | AssertH(selCtr == nSelectors, 3007); | ||
606 | #undef code | ||
607 | #undef rfreq | ||
608 | #undef len_pack | ||
609 | } | ||
610 | |||
611 | |||
612 | /*---------------------------------------------------*/ | ||
613 | static | ||
614 | void BZ2_compressBlock(EState* s, int is_last_block) | ||
615 | { | ||
616 | if (s->nblock > 0) { | ||
617 | BZ_FINALISE_CRC(s->blockCRC); | ||
618 | s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31); | ||
619 | s->combinedCRC ^= s->blockCRC; | ||
620 | if (s->blockNo > 1) | ||
621 | s->numZ = 0; | ||
622 | |||
623 | BZ2_blockSort(s); | ||
624 | } | ||
625 | |||
626 | s->zbits = &((uint8_t*)s->arr2)[s->nblock]; | ||
627 | |||
628 | /*-- If this is the first block, create the stream header. --*/ | ||
629 | if (s->blockNo == 1) { | ||
630 | BZ2_bsInitWrite(s); | ||
631 | /*bsPutU8(s, BZ_HDR_B);*/ | ||
632 | /*bsPutU8(s, BZ_HDR_Z);*/ | ||
633 | /*bsPutU8(s, BZ_HDR_h);*/ | ||
634 | /*bsPutU8(s, BZ_HDR_0 + s->blockSize100k);*/ | ||
635 | bsPutU32(s, BZ_HDR_BZh0 + s->blockSize100k); | ||
636 | } | ||
637 | |||
638 | if (s->nblock > 0) { | ||
639 | /*bsPutU8(s, 0x31);*/ | ||
640 | /*bsPutU8(s, 0x41);*/ | ||
641 | /*bsPutU8(s, 0x59);*/ | ||
642 | /*bsPutU8(s, 0x26);*/ | ||
643 | bsPutU32(s, 0x31415926); | ||
644 | /*bsPutU8(s, 0x53);*/ | ||
645 | /*bsPutU8(s, 0x59);*/ | ||
646 | bsPutU16(s, 0x5359); | ||
647 | |||
648 | /*-- Now the block's CRC, so it is in a known place. --*/ | ||
649 | bsPutU32(s, s->blockCRC); | ||
650 | |||
651 | /* | ||
652 | * Now a single bit indicating (non-)randomisation. | ||
653 | * As of version 0.9.5, we use a better sorting algorithm | ||
654 | * which makes randomisation unnecessary. So always set | ||
655 | * the randomised bit to 'no'. Of course, the decoder | ||
656 | * still needs to be able to handle randomised blocks | ||
657 | * so as to maintain backwards compatibility with | ||
658 | * older versions of bzip2. | ||
659 | */ | ||
660 | bsW(s, 1, 0); | ||
661 | |||
662 | bsW(s, 24, s->origPtr); | ||
663 | generateMTFValues(s); | ||
664 | sendMTFValues(s); | ||
665 | } | ||
666 | |||
667 | /*-- If this is the last block, add the stream trailer. --*/ | ||
668 | if (is_last_block) { | ||
669 | /*bsPutU8(s, 0x17);*/ | ||
670 | /*bsPutU8(s, 0x72);*/ | ||
671 | /*bsPutU8(s, 0x45);*/ | ||
672 | /*bsPutU8(s, 0x38);*/ | ||
673 | bsPutU32(s, 0x17724538); | ||
674 | /*bsPutU8(s, 0x50);*/ | ||
675 | /*bsPutU8(s, 0x90);*/ | ||
676 | bsPutU16(s, 0x5090); | ||
677 | bsPutU32(s, s->combinedCRC); | ||
678 | bsFinishWrite(s); | ||
679 | } | ||
680 | } | ||
681 | |||
682 | |||
683 | /*-------------------------------------------------------------*/ | ||
684 | /*--- end compress.c ---*/ | ||
685 | /*-------------------------------------------------------------*/ | ||