blob: 2d994685cefa64f371ba6610ba0ad8a174a1c82e
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_FAST >= 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, bt, bc, iter; |
253 | int32_t nSelectors, alphaSize, minLen, maxLen, selCtr; |
254 | int32_t nGroups; |
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_FAST >= 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 | gs = 0; |
349 | while (1) { |
350 | /*--- Set group start & end marks. --*/ |
351 | if (gs >= s->nMTF) |
352 | break; |
353 | ge = gs + BZ_G_SIZE - 1; |
354 | if (ge >= s->nMTF) |
355 | ge = s->nMTF-1; |
356 | |
357 | /* |
358 | * Calculate the cost of this group as coded |
359 | * by each of the coding tables. |
360 | */ |
361 | for (t = 0; t < nGroups; t++) |
362 | cost[t] = 0; |
363 | #if CONFIG_BZIP2_FAST >= 5 |
364 | if (nGroups == 6 && 50 == ge-gs+1) { |
365 | /*--- fast track the common case ---*/ |
366 | register uint32_t cost01, cost23, cost45; |
367 | register uint16_t icv; |
368 | cost01 = cost23 = cost45 = 0; |
369 | #define BZ_ITER(nn) \ |
370 | icv = mtfv[gs+(nn)]; \ |
371 | cost01 += s->len_pack[icv][0]; \ |
372 | cost23 += s->len_pack[icv][1]; \ |
373 | cost45 += s->len_pack[icv][2]; |
374 | BZ_ITER(0); BZ_ITER(1); BZ_ITER(2); BZ_ITER(3); BZ_ITER(4); |
375 | BZ_ITER(5); BZ_ITER(6); BZ_ITER(7); BZ_ITER(8); BZ_ITER(9); |
376 | BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14); |
377 | BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19); |
378 | BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24); |
379 | BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29); |
380 | BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34); |
381 | BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39); |
382 | BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44); |
383 | BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49); |
384 | #undef BZ_ITER |
385 | cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16; |
386 | cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16; |
387 | cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16; |
388 | } else |
389 | #endif |
390 | { |
391 | /*--- slow version which correctly handles all situations ---*/ |
392 | for (i = gs; i <= ge; i++) { |
393 | uint16_t icv = mtfv[i]; |
394 | for (t = 0; t < nGroups; t++) |
395 | cost[t] += s->len[t][icv]; |
396 | } |
397 | } |
398 | /* |
399 | * Find the coding table which is best for this group, |
400 | * and record its identity in the selector table. |
401 | */ |
402 | /*bc = 999999999;*/ |
403 | /*bt = -1;*/ |
404 | bc = cost[0]; |
405 | bt = 0; |
406 | for (t = 1 /*0*/; t < nGroups; t++) { |
407 | if (cost[t] < bc) { |
408 | bc = cost[t]; |
409 | bt = t; |
410 | } |
411 | } |
412 | fave[bt]++; |
413 | s->selector[nSelectors] = bt; |
414 | nSelectors++; |
415 | |
416 | /* |
417 | * Increment the symbol frequencies for the selected table. |
418 | */ |
419 | /* 1% faster compress. +800 bytes */ |
420 | #if CONFIG_BZIP2_FAST >= 4 |
421 | if (nGroups == 6 && 50 == ge-gs+1) { |
422 | /*--- fast track the common case ---*/ |
423 | #define BZ_ITUR(nn) s->rfreq[bt][mtfv[gs + (nn)]]++ |
424 | BZ_ITUR(0); BZ_ITUR(1); BZ_ITUR(2); BZ_ITUR(3); BZ_ITUR(4); |
425 | BZ_ITUR(5); BZ_ITUR(6); BZ_ITUR(7); BZ_ITUR(8); BZ_ITUR(9); |
426 | BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14); |
427 | BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19); |
428 | BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24); |
429 | BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29); |
430 | BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34); |
431 | BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39); |
432 | BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44); |
433 | BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49); |
434 | #undef BZ_ITUR |
435 | gs = ge + 1; |
436 | } else |
437 | #endif |
438 | { |
439 | /*--- slow version which correctly handles all situations ---*/ |
440 | while (gs <= ge) { |
441 | s->rfreq[bt][mtfv[gs]]++; |
442 | gs++; |
443 | } |
444 | /* already is: gs = ge + 1; */ |
445 | } |
446 | } |
447 | |
448 | /* |
449 | * Recompute the tables based on the accumulated frequencies. |
450 | */ |
451 | /* maxLen was changed from 20 to 17 in bzip2-1.0.3. See |
452 | * comment in huffman.c for details. */ |
453 | for (t = 0; t < nGroups; t++) |
454 | BZ2_hbMakeCodeLengths(s, &(s->len[t][0]), &(s->rfreq[t][0]), alphaSize, 17 /*20*/); |
455 | } |
456 | |
457 | AssertH(nGroups < 8, 3002); |
458 | AssertH(nSelectors < 32768 && nSelectors <= (2 + (900000 / BZ_G_SIZE)), 3003); |
459 | |
460 | /*--- Compute MTF values for the selectors. ---*/ |
461 | { |
462 | uint8_t pos[BZ_N_GROUPS], ll_i, tmp2, tmp; |
463 | |
464 | for (i = 0; i < nGroups; i++) |
465 | pos[i] = i; |
466 | for (i = 0; i < nSelectors; i++) { |
467 | ll_i = s->selector[i]; |
468 | j = 0; |
469 | tmp = pos[j]; |
470 | while (ll_i != tmp) { |
471 | j++; |
472 | tmp2 = tmp; |
473 | tmp = pos[j]; |
474 | pos[j] = tmp2; |
475 | }; |
476 | pos[0] = tmp; |
477 | s->selectorMtf[i] = j; |
478 | } |
479 | }; |
480 | |
481 | /*--- Assign actual codes for the tables. --*/ |
482 | for (t = 0; t < nGroups; t++) { |
483 | minLen = 32; |
484 | maxLen = 0; |
485 | for (i = 0; i < alphaSize; i++) { |
486 | if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; |
487 | if (s->len[t][i] < minLen) minLen = s->len[t][i]; |
488 | } |
489 | AssertH(!(maxLen > 17 /*20*/), 3004); |
490 | AssertH(!(minLen < 1), 3005); |
491 | BZ2_hbAssignCodes(&(s->code[t][0]), &(s->len[t][0]), minLen, maxLen, alphaSize); |
492 | } |
493 | |
494 | /*--- Transmit the mapping table. ---*/ |
495 | { |
496 | /* bbox: optimized a bit more than in bzip2 */ |
497 | int inUse16 = 0; |
498 | for (i = 0; i < 16; i++) { |
499 | if (sizeof(long) <= 4) { |
500 | inUse16 = inUse16*2 + |
501 | ((*(bb__aliased_uint32_t*)&(s->inUse[i * 16 + 0]) |
502 | | *(bb__aliased_uint32_t*)&(s->inUse[i * 16 + 4]) |
503 | | *(bb__aliased_uint32_t*)&(s->inUse[i * 16 + 8]) |
504 | | *(bb__aliased_uint32_t*)&(s->inUse[i * 16 + 12])) != 0); |
505 | } else { /* Our CPU can do better */ |
506 | inUse16 = inUse16*2 + |
507 | ((*(bb__aliased_uint64_t*)&(s->inUse[i * 16 + 0]) |
508 | | *(bb__aliased_uint64_t*)&(s->inUse[i * 16 + 8])) != 0); |
509 | } |
510 | } |
511 | |
512 | bsW(s, 16, inUse16); |
513 | |
514 | inUse16 <<= (sizeof(int)*8 - 16); /* move 15th bit into sign bit */ |
515 | for (i = 0; i < 16; i++) { |
516 | if (inUse16 < 0) { |
517 | unsigned v16 = 0; |
518 | for (j = 0; j < 16; j++) |
519 | v16 = v16*2 + s->inUse[i * 16 + j]; |
520 | bsW(s, 16, v16); |
521 | } |
522 | inUse16 <<= 1; |
523 | } |
524 | } |
525 | |
526 | /*--- Now the selectors. ---*/ |
527 | bsW(s, 3, nGroups); |
528 | bsW(s, 15, nSelectors); |
529 | for (i = 0; i < nSelectors; i++) { |
530 | for (j = 0; j < s->selectorMtf[i]; j++) |
531 | bsW(s, 1, 1); |
532 | bsW(s, 1, 0); |
533 | } |
534 | |
535 | /*--- Now the coding tables. ---*/ |
536 | for (t = 0; t < nGroups; t++) { |
537 | int32_t curr = s->len[t][0]; |
538 | bsW(s, 5, curr); |
539 | for (i = 0; i < alphaSize; i++) { |
540 | while (curr < s->len[t][i]) { bsW(s, 2, 2); curr++; /* 10 */ }; |
541 | while (curr > s->len[t][i]) { bsW(s, 2, 3); curr--; /* 11 */ }; |
542 | bsW(s, 1, 0); |
543 | } |
544 | } |
545 | |
546 | /*--- And finally, the block data proper ---*/ |
547 | selCtr = 0; |
548 | gs = 0; |
549 | while (1) { |
550 | if (gs >= s->nMTF) |
551 | break; |
552 | ge = gs + BZ_G_SIZE - 1; |
553 | if (ge >= s->nMTF) |
554 | ge = s->nMTF-1; |
555 | AssertH(s->selector[selCtr] < nGroups, 3006); |
556 | |
557 | /* Costs 1300 bytes and is _slower_ (on Intel Core 2) */ |
558 | #if 0 |
559 | if (nGroups == 6 && 50 == ge-gs+1) { |
560 | /*--- fast track the common case ---*/ |
561 | uint16_t mtfv_i; |
562 | uint8_t* s_len_sel_selCtr = &(s->len[s->selector[selCtr]][0]); |
563 | int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]); |
564 | #define BZ_ITAH(nn) \ |
565 | mtfv_i = mtfv[gs+(nn)]; \ |
566 | bsW(s, s_len_sel_selCtr[mtfv_i], s_code_sel_selCtr[mtfv_i]) |
567 | BZ_ITAH(0); BZ_ITAH(1); BZ_ITAH(2); BZ_ITAH(3); BZ_ITAH(4); |
568 | BZ_ITAH(5); BZ_ITAH(6); BZ_ITAH(7); BZ_ITAH(8); BZ_ITAH(9); |
569 | BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14); |
570 | BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19); |
571 | BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24); |
572 | BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29); |
573 | BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34); |
574 | BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39); |
575 | BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44); |
576 | BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49); |
577 | #undef BZ_ITAH |
578 | gs = ge+1; |
579 | } else |
580 | #endif |
581 | { |
582 | /*--- slow version which correctly handles all situations ---*/ |
583 | /* code is bit bigger, but moves multiply out of the loop */ |
584 | uint8_t* s_len_sel_selCtr = &(s->len [s->selector[selCtr]][0]); |
585 | int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]); |
586 | while (gs <= ge) { |
587 | bsW(s, |
588 | s_len_sel_selCtr[mtfv[gs]], |
589 | s_code_sel_selCtr[mtfv[gs]] |
590 | ); |
591 | gs++; |
592 | } |
593 | /* already is: gs = ge+1; */ |
594 | } |
595 | selCtr++; |
596 | } |
597 | AssertH(selCtr == nSelectors, 3007); |
598 | #undef code |
599 | #undef rfreq |
600 | #undef len_pack |
601 | } |
602 | |
603 | |
604 | /*---------------------------------------------------*/ |
605 | static |
606 | void BZ2_compressBlock(EState* s, int is_last_block) |
607 | { |
608 | if (s->nblock > 0) { |
609 | BZ_FINALISE_CRC(s->blockCRC); |
610 | s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31); |
611 | s->combinedCRC ^= s->blockCRC; |
612 | if (s->blockNo > 1) |
613 | s->numZ = 0; |
614 | |
615 | BZ2_blockSort(s); |
616 | } |
617 | |
618 | s->zbits = &((uint8_t*)s->arr2)[s->nblock]; |
619 | |
620 | /*-- If this is the first block, create the stream header. --*/ |
621 | if (s->blockNo == 1) { |
622 | BZ2_bsInitWrite(s); |
623 | /*bsPutU8(s, BZ_HDR_B);*/ |
624 | /*bsPutU8(s, BZ_HDR_Z);*/ |
625 | /*bsPutU8(s, BZ_HDR_h);*/ |
626 | /*bsPutU8(s, BZ_HDR_0 + s->blockSize100k);*/ |
627 | bsPutU32(s, BZ_HDR_BZh0 + s->blockSize100k); |
628 | } |
629 | |
630 | if (s->nblock > 0) { |
631 | /*bsPutU8(s, 0x31);*/ |
632 | /*bsPutU8(s, 0x41);*/ |
633 | /*bsPutU8(s, 0x59);*/ |
634 | /*bsPutU8(s, 0x26);*/ |
635 | bsPutU32(s, 0x31415926); |
636 | /*bsPutU8(s, 0x53);*/ |
637 | /*bsPutU8(s, 0x59);*/ |
638 | bsPutU16(s, 0x5359); |
639 | |
640 | /*-- Now the block's CRC, so it is in a known place. --*/ |
641 | bsPutU32(s, s->blockCRC); |
642 | |
643 | /* |
644 | * Now a single bit indicating (non-)randomisation. |
645 | * As of version 0.9.5, we use a better sorting algorithm |
646 | * which makes randomisation unnecessary. So always set |
647 | * the randomised bit to 'no'. Of course, the decoder |
648 | * still needs to be able to handle randomised blocks |
649 | * so as to maintain backwards compatibility with |
650 | * older versions of bzip2. |
651 | */ |
652 | bsW(s, 1, 0); |
653 | |
654 | bsW(s, 24, s->origPtr); |
655 | generateMTFValues(s); |
656 | sendMTFValues(s); |
657 | } |
658 | |
659 | /*-- If this is the last block, add the stream trailer. --*/ |
660 | if (is_last_block) { |
661 | /*bsPutU8(s, 0x17);*/ |
662 | /*bsPutU8(s, 0x72);*/ |
663 | /*bsPutU8(s, 0x45);*/ |
664 | /*bsPutU8(s, 0x38);*/ |
665 | bsPutU32(s, 0x17724538); |
666 | /*bsPutU8(s, 0x50);*/ |
667 | /*bsPutU8(s, 0x90);*/ |
668 | bsPutU16(s, 0x5090); |
669 | bsPutU32(s, s->combinedCRC); |
670 | bsFinishWrite(s); |
671 | } |
672 | } |
673 | |
674 | |
675 | /*-------------------------------------------------------------*/ |
676 | /*--- end compress.c ---*/ |
677 | /*-------------------------------------------------------------*/ |
678 |