source: nikanabo/current/xdelta/diy/xdelta3-djw.h@ 185

Last change on this file since 185 was 185, checked in by geyser, 18 years ago
File size: 51.0 KB
Line 
1/* xdelta 3 - delta compression tools and library
2 * Copyright (C) 2002, 2006, 2007. Joshua P. MacDonald
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
18
19#ifndef _XDELTA3_DJW_H_
20#define _XDELTA3_DJW_H_
21
22/* The following people deserve much credit for the algorithms and techniques contained in
23 * this file:
24
25 Julian Seward
26 Bzip2 sources, implementation of the multi-table Huffman technique.
27
28 Jean-loup Gailly and Mark Adler and L. Peter Deutsch
29 Zlib source code, RFC 1951
30
31 Daniel S. Hirschberg and Debra A. LeLewer
32 "Efficient Decoding of Prefix Codes"
33 Communications of the ACM, April 1990 33(4).
34
35 David J. Wheeler
36 Program bred3.c, bexp3 and accompanying documents bred3.ps, huff.ps.
37 This contains the idea behind the multi-table Huffman and 1-2 coding techniques.
38 ftp://ftp.cl.cam.ac.uk/users/djw3/
39
40*/
41
42/* OPT: during the multi-table iteration, pick the worst-overall performing table and
43 * replace it with exactly the frequencies of the worst-overall performing sector or
44 * N-worst performing sectors. */
45
46/* REF: See xdfs-0.222 and xdfs-0.226 for some old experiments with the Bzip prefix coding
47 * strategy. xdfs-0.256 contains the last of the other-format tests, including RFC1950
48 * and the RFC1950+MTF tests. */
49
50#define DJW_MAX_CODELEN 32 /* Maximum length of an alphabet code. */
51
52#define DJW_TOTAL_CODES (DJW_MAX_CODELEN+2) /* [RUN_0, RUN_1, 1-DJW_MAX_CODELEN] */
53
54#define RUN_0 0 /* Symbols used in MTF+1/2 coding. */
55#define RUN_1 1
56
57#define DJW_BASIC_CODES 5 /* Number of code lengths always encoded (djw_encode_basic array) */
58#define DJW_RUN_CODES 2 /* Number of run codes */
59#define DJW_EXTRA_12OFFSET 7 /* Offset of extra codes */
60#define DJW_EXTRA_CODES 15 /* Number of optionally encoded code lengths (djw_encode_extra array) */
61#define DJW_EXTRA_CODE_BITS 4 /* Number of bits to code [0-DJW_EXTRA_CODES] */
62
63#define DJW_MAX_GROUPS 8 /* Max number of group coding tables */
64#define DJW_GROUP_BITS 3 /* Number of bits to code [1-DJW_MAX_GROUPS] */
65
66#define DJW_SECTORSZ_MULT 5 /* Multiplier for encoded sectorsz */
67#define DJW_SECTORSZ_BITS 5 /* Number of bits to code group size */
68#define DJW_SECTORSZ_MAX ((1 << DJW_SECTORSZ_BITS) * DJW_SECTORSZ_MULT)
69
70#define DJW_MAX_ITER 6 /* Maximum number of iterations to find group tables. */
71#define DJW_MIN_IMPROVEMENT 20 /* Minimum number of bits an iteration must reduce coding by. */
72
73#define DJW_MAX_CLCLEN 15 /* Maximum code length of a prefix code length */
74#define DJW_CLCLEN_BITS 4 /* Number of bits to code [0-DJW_MAX_CLCLEN] */
75
76#define DJW_MAX_GBCLEN 7 /* Maximum code length of a group selector */
77#define DJW_GBCLEN_BITS 3 /* Number of bits to code [0-DJW_MAX_GBCLEN]
78 * @!@ Actually, should never have zero code lengths here, or
79 * else a group went unused. Write a test for this: if a group
80 * goes unused, eliminate it? */
81
82#define EFFICIENCY_BITS 16 /* It has to save at least this many bits... */
83
84typedef struct _djw_stream djw_stream;
85typedef struct _djw_heapen djw_heapen;
86typedef struct _djw_prefix djw_prefix;
87typedef uint32_t djw_weight;
88
89/* To enable Huffman tuning code... */
90#ifndef TUNE_HUFFMAN
91#define TUNE_HUFFMAN 0
92#endif
93
94#if TUNE_HUFFMAN == 0
95#define xd3_real_encode_huff xd3_encode_huff
96#define IF_TUNE(x)
97#define IF_NTUNE(x) x
98#else
99static uint xd3_bitsof_output (xd3_output *output, bit_state *bstate);
100#define IF_TUNE(x) x
101#define IF_NTUNE(x)
102static djw_weight tune_freq[DJW_TOTAL_CODES];
103static uint8_t tune_clen[DJW_MAX_GROUPS][ALPHABET_SIZE];
104static usize_t tune_prefix_bits;
105static usize_t tune_select_bits;
106static usize_t tune_encode_bits;
107#endif
108struct _djw_heapen
109{
110 uint32_t depth;
111 uint32_t freq;
112 uint32_t parent;
113};
114
115struct _djw_prefix
116{
117 usize_t scount;
118 uint8_t *symbol;
119 usize_t mcount;
120 uint8_t *mtfsym;
121 uint8_t *repcnt;
122};
123
124struct _djw_stream
125{
126 int unused;
127};
128
129/* Each Huffman table consists of 256 "code length" (CLEN) codes, which are themselves
130 * Huffman coded after eliminating repeats and move-to-front coding. The prefix consists
131 * of all the CLEN codes in djw_encode_basic plus a 4-bit value stating how many of the
132 * djw_encode_extra codes are actually coded (the rest are presumed zero, or unused CLEN
133 * codes).
134 *
135 * These values of these two arrays were arrived at by studying the distribution of min
136 * and max clen over a collection of DATA, INST, and ADDR inputs. The goal is to specify
137 * the order of djw_extra_codes that is most likely to minimize the number of extra codes
138 * that must be encoded.
139 *
140 * Results: 158896 sections were counted by compressing files (window size 512K) listed
141 * with: `find / -type f ( -user jmacd -o -perm +444 )`
142 *
143 * The distribution of CLEN codes for each efficient invocation of the secondary
144 * compressor (taking the best number of groups/sector size) was recorded. Then we look at
145 * the distribution of min and max clen values, counting the number of times the value
146 * C_low is less than the min and C_high is greater than the max. Values >= C_high and <=
147 * C_low will not have their lengths coded. The results are sorted and the least likely
148 * 15 are placed into the djw_encode_extra[] array in order. These values are used as
149 * the initial MTF ordering.
150
151 clow[1] = 155119
152 clow[2] = 140325
153 clow[3] = 84072
154 ---
155 clow[4] = 7225
156 clow[5] = 1093
157 clow[6] = 215
158 ---
159 chigh[4] = 1
160 chigh[5] = 30
161 chigh[6] = 218
162 chigh[7] = 2060
163 chigh[8] = 13271
164 ---
165 chigh[9] = 39463
166 chigh[10] = 77360
167 chigh[11] = 118298
168 chigh[12] = 141360
169 chigh[13] = 154086
170 chigh[14] = 157967
171 chigh[15] = 158603
172 chigh[16] = 158864
173 chigh[17] = 158893
174 chigh[18] = 158895
175 chigh[19] = 158896
176 chigh[20] = 158896
177
178*/
179
180static const uint8_t djw_encode_12extra[DJW_EXTRA_CODES] =
181 {
182 9, 10, 3, 11, 2, 12, 13, 1, 14, 15, 16, 17, 18, 19, 20
183 };
184
185static const uint8_t djw_encode_12basic[DJW_BASIC_CODES] =
186 {
187 4, 5, 6, 7, 8,
188 };
189
190/*********************************************************************/
191/* DECLS */
192/*********************************************************************/
193
194static djw_stream* djw_alloc (xd3_stream *stream /*, int alphabet_size */);
195static void djw_init (djw_stream *h);
196static void djw_destroy (xd3_stream *stream,
197 djw_stream *h);
198
199#if XD3_ENCODER
200static int xd3_encode_huff (xd3_stream *stream,
201 djw_stream *sec_stream,
202 xd3_output *input,
203 xd3_output *output,
204 xd3_sec_cfg *cfg);
205#endif
206
207static int xd3_decode_huff (xd3_stream *stream,
208 djw_stream *sec_stream,
209 const uint8_t **input,
210 const uint8_t *const input_end,
211 uint8_t **output,
212 const uint8_t *const output_end);
213
214/*********************************************************************/
215/* HUFFMAN */
216/*********************************************************************/
217
218static djw_stream*
219djw_alloc (xd3_stream *stream)
220{
221 return xd3_alloc (stream, sizeof (djw_stream), 1);
222}
223
224static void
225djw_init (djw_stream *h)
226{
227 /* Fields are initialized prior to use. */
228}
229
230static void
231djw_destroy (xd3_stream *stream,
232 djw_stream *h)
233{
234 xd3_free (stream, h);
235}
236
237
238/*********************************************************************/
239/* HEAP */
240/*********************************************************************/
241
242static INLINE int
243heap_less (const djw_heapen *a, const djw_heapen *b)
244{
245 return a->freq < b->freq ||
246 (a->freq == b->freq &&
247 a->depth < b->depth);
248}
249
250static INLINE void
251heap_insert (uint *heap, const djw_heapen *ents, uint p, const uint e)
252{
253 /* Insert ents[e] into next slot heap[p] */
254 uint pp = p/2; /* P's parent */
255
256 while (heap_less (& ents[e], & ents[heap[pp]]))
257 {
258 heap[p] = heap[pp];
259 p = pp;
260 pp = p/2;
261 }
262
263 heap[p] = e;
264}
265
266static INLINE djw_heapen*
267heap_extract (uint *heap, const djw_heapen *ents, uint heap_last)
268{
269 uint smallest = heap[1];
270 uint p, pc, t;
271
272 /* Caller decrements heap_last, so heap_last+1 is the replacement elt. */
273 heap[1] = heap[heap_last+1];
274
275 /* Re-heapify */
276 for (p = 1; ; p = pc)
277 {
278 pc = p*2;
279
280 /* Reached bottom of heap */
281 if (pc > heap_last) { break; }
282
283 /* See if second child is smaller. */
284 if (pc < heap_last && heap_less (& ents[heap[pc+1]], & ents[heap[pc]])) { pc += 1; }
285
286 /* If pc is not smaller than p, heap property re-established. */
287 if (! heap_less (& ents[heap[pc]], & ents[heap[p]])) { break; }
288
289 t = heap[pc];
290 heap[pc] = heap[p];
291 heap[p] = t;
292 }
293
294 return (djw_heapen*) & ents[smallest];
295}
296
297#if XD3_DEBUG
298static void
299heap_check (uint *heap, djw_heapen *ents, uint heap_last)
300{
301 uint i;
302 for (i = 1; i <= heap_last; i += 1)
303 {
304 /* Heap property: child not less than parent */
305 XD3_ASSERT (! heap_less (& ents[heap[i]], & ents[heap[i/2]]));
306 }
307}
308#endif
309
310/*********************************************************************/
311/* MTF, 1/2 */
312/*********************************************************************/
313
314static INLINE usize_t
315djw_update_mtf (uint8_t *mtf, usize_t mtf_i)
316{
317 int k;
318 usize_t sym = mtf[mtf_i];
319
320 for (k = mtf_i; k != 0; k -= 1) { mtf[k] = mtf[k-1]; }
321
322 mtf[0] = sym;
323 return sym;
324}
325
326static INLINE void
327djw_update_1_2 (int *mtf_run, usize_t *mtf_i, uint8_t *mtfsym, djw_weight *freq)
328{
329 int code;
330
331 do
332 {
333 /* Offset by 1, since any number of RUN_ symbols implies run>0... */
334 *mtf_run -= 1;
335
336 code = (*mtf_run & 1) ? RUN_1 : RUN_0;
337
338 mtfsym[(*mtf_i)++] = code;
339 freq[code] += 1;
340 *mtf_run >>= 1;
341 }
342 while (*mtf_run >= 1);
343
344 *mtf_run = 0;
345}
346
347static void
348djw_init_clen_mtf_1_2 (uint8_t *clmtf)
349{
350 int i, cl_i = 0;
351
352 clmtf[cl_i++] = 0;
353 for (i = 0; i < DJW_BASIC_CODES; i += 1) { clmtf[cl_i++] = djw_encode_12basic[i]; }
354 for (i = 0; i < DJW_EXTRA_CODES; i += 1) { clmtf[cl_i++] = djw_encode_12extra[i]; }
355}
356
357/*********************************************************************/
358/* PREFIX CODES */
359/*********************************************************************/
360#if XD3_ENCODER
361static usize_t
362djw_build_prefix (const djw_weight *freq, uint8_t *clen, int asize, int maxlen)
363{
364 /* Heap with 0th entry unused, prefix tree with up to ALPHABET_SIZE-1 internal nodes,
365 * never more than ALPHABET_SIZE entries actually in the heap (minimum weight subtrees
366 * during prefix construction). First ALPHABET_SIZE entries are the actual symbols,
367 * next ALPHABET_SIZE-1 are internal nodes. */
368 djw_heapen ents[ALPHABET_SIZE * 2];
369 uint heap[ALPHABET_SIZE + 1];
370
371 uint heap_last; /* Index of the last _valid_ heap entry. */
372 uint ents_size; /* Number of entries, including 0th fake entry */
373 int overflow; /* Number of code lengths that overflow */
374 uint32_t total_bits;
375 int i;
376
377 IF_DEBUG (uint32_t first_bits = 0);
378
379 /* Insert real symbol frequences. */
380 for (i = 0; i < asize; i += 1)
381 {
382 ents[i+1].freq = freq[i];
383 }
384
385 again:
386
387 /* The loop is re-entered each time an overflow occurs. Re-initialize... */
388 heap_last = 0;
389 ents_size = 1;
390 overflow = 0;
391 total_bits = 0;
392
393 /* 0th entry terminates the while loop in heap_insert (its the parent of the smallest
394 * element, always less-than) */
395 heap[0] = 0;
396 ents[0].depth = 0;
397 ents[0].freq = 0;
398
399 /* Initial heap. */
400 for (i = 0; i < asize; i += 1, ents_size += 1)
401 {
402 ents[ents_size].depth = 0;
403 ents[ents_size].parent = 0;
404
405 if (ents[ents_size].freq != 0)
406 {
407 heap_insert (heap, ents, ++heap_last, ents_size);
408 }
409 }
410
411 IF_DEBUG (heap_check (heap, ents, heap_last));
412
413 /* Must be at least one symbol, or else we can't get here. */
414 XD3_ASSERT (heap_last != 0);
415
416 /* If there is only one symbol, fake a second to prevent zero-length codes. */
417 if (unlikely (heap_last == 1))
418 {
419 /* Pick either the first or last symbol. */
420 int s = freq[0] ? asize-1 : 0;
421 ents[s+1].freq = 1;
422 goto again;
423 }
424
425 /* Build prefix tree. */
426 while (heap_last > 1)
427 {
428 djw_heapen *h1 = heap_extract (heap, ents, --heap_last);
429 djw_heapen *h2 = heap_extract (heap, ents, --heap_last);
430
431 ents[ents_size].freq = h1->freq + h2->freq;
432 ents[ents_size].depth = 1 + max (h1->depth, h2->depth);
433 ents[ents_size].parent = 0;
434
435 h1->parent = h2->parent = ents_size;
436
437 heap_insert (heap, ents, ++heap_last, ents_size++);
438
439 IF_DEBUG (heap_check (heap, ents, heap_last));
440 }
441
442 /* Now compute prefix code lengths, counting parents. */
443 for (i = 1; i < asize+1; i += 1)
444 {
445 int b = 0;
446
447 if (ents[i].freq != 0)
448 {
449 int p = i;
450
451 while ((p = ents[p].parent) != 0) { b += 1; }
452
453 if (b > maxlen) { overflow = 1; }
454
455 total_bits += b * freq[i-1];
456 }
457
458 /* clen is 0-origin, unlike ents. */
459 clen[i-1] = b;
460 }
461
462 IF_DEBUG (if (first_bits == 0) first_bits = total_bits);
463
464 if (! overflow)
465 {
466 IF_DEBUG (if (first_bits != total_bits)
467 {
468 DP(RINT "code length overflow changed %u bits\n", (usize_t)(total_bits - first_bits));
469 });
470 return total_bits;
471 }
472
473 /* OPT: There is a non-looping way to fix overflow shown in zlib, but this is easier
474 * (for now), as done in bzip2. */
475 for (i = 1; i < asize+1; i += 1)
476 {
477 ents[i].freq = ents[i].freq / 2 + 1;
478 }
479
480 goto again;
481}
482
483static void
484djw_build_codes (uint *codes, const uint8_t *clen, int asize DEBUG_ARG (int abs_max))
485{
486 int i, l;
487 int min_clen = DJW_MAX_CODELEN;
488 int max_clen = 0;
489 uint code = 0;
490
491 for (i = 0; i < asize; i += 1)
492 {
493 if (clen[i] > 0 && clen[i] < min_clen)
494 {
495 min_clen = clen[i];
496 }
497
498 max_clen = max (max_clen, (int) clen[i]);
499 }
500
501 XD3_ASSERT (max_clen <= abs_max);
502
503 for (l = min_clen; l <= max_clen; l += 1)
504 {
505 for (i = 0; i < asize; i += 1)
506 {
507 if (clen[i] == l) { codes[i] = code++; }
508 }
509
510 code <<= 1;
511 }
512}
513
514/*********************************************************************/
515/* MOVE-TO-FRONT */
516/*********************************************************************/
517static void
518djw_compute_mtf_1_2 (djw_prefix *prefix,
519 uint8_t *mtf,
520 djw_weight *freq_out, /* freak out! */
521 usize_t nsym)
522{
523 int i, j, k;
524 usize_t sym;
525 usize_t size = prefix->scount;
526 usize_t mtf_i = 0;
527 int mtf_run = 0;
528
529 memset (freq_out, 0, sizeof (freq_out[0]) * (nsym+1));
530
531 for (i = 0; i < size; )
532 {
533 /* OPT: Bzip optimizes this algorithm a little by effectively checking j==0 before
534 * the MTF update. */
535 sym = prefix->symbol[i++];
536
537 for (j = 0; mtf[j] != sym; j += 1) { }
538
539 XD3_ASSERT (j < nsym);
540
541 for (k = j; k >= 1; k -= 1) { mtf[k] = mtf[k-1]; }
542
543 mtf[0] = sym;
544
545 if (j == 0)
546 {
547 mtf_run += 1;
548 continue;
549 }
550
551 if (mtf_run > 0)
552 {
553 djw_update_1_2 (& mtf_run, & mtf_i, prefix->mtfsym, freq_out);
554 }
555
556 /* Non-zero symbols are offset by RUN_1 */
557 prefix->mtfsym[mtf_i++] = j+RUN_1;
558 freq_out[j+RUN_1] += 1;
559 }
560
561 if (mtf_run > 0)
562 {
563 djw_update_1_2 (& mtf_run, & mtf_i, prefix->mtfsym, freq_out);
564 }
565
566 prefix->mcount = mtf_i;
567}
568
569static usize_t
570djw_count_freqs (djw_weight *freq, xd3_output *input)
571{
572 xd3_output *in;
573 usize_t size = 0;
574
575 memset (freq, 0, sizeof (freq[0]) * ALPHABET_SIZE);
576
577 /* Freqency counting. OPT: can be accomplished beforehand. */
578 for (in = input; in; in = in->next_page)
579 {
580 const uint8_t *p = in->base;
581 const uint8_t *p_max = p + in->next;
582
583 size += in->next;
584
585 do { freq[*p++] += 1; } while (p < p_max);
586 }
587
588 IF_DEBUG1 ({int i;
589 DP(RINT "freqs: ");
590 for (i = 0; i < ALPHABET_SIZE; i += 1) { DP(RINT "%u ", freq[i]); }
591 DP(RINT "\n");});
592
593 return size;
594}
595
596static void
597djw_compute_multi_prefix (int groups,
598 uint8_t clen[DJW_MAX_GROUPS][ALPHABET_SIZE],
599 djw_prefix *prefix)
600{
601 int gp, i;
602
603 prefix->scount = ALPHABET_SIZE;
604 memcpy (prefix->symbol, clen[0], ALPHABET_SIZE);
605
606 for (gp = 1; gp < groups; gp += 1)
607 {
608 for (i = 0; i < ALPHABET_SIZE; i += 1)
609 {
610 if (clen[gp][i] == 0)
611 {
612 continue;
613 }
614
615 prefix->symbol[prefix->scount++] = clen[gp][i];
616 }
617 }
618}
619
620static void
621djw_compute_prefix_1_2 (djw_prefix *prefix, djw_weight *freq)
622{
623 uint8_t clmtf[DJW_MAX_CODELEN+1];
624
625 djw_init_clen_mtf_1_2 (clmtf);
626
627 djw_compute_mtf_1_2 (prefix, clmtf, freq, DJW_MAX_CODELEN+1);
628}
629
630static int
631djw_encode_prefix (xd3_stream *stream,
632 xd3_output **output,
633 bit_state *bstate,
634 djw_prefix *prefix)
635{
636 int ret, i;
637 uint num_to_encode;
638 djw_weight clfreq[DJW_TOTAL_CODES];
639 uint8_t clclen[DJW_TOTAL_CODES];
640 uint clcode[DJW_TOTAL_CODES];
641
642 IF_TUNE (memset (clfreq, 0, sizeof (clfreq)));
643
644 /* Move-to-front encode prefix symbols, count frequencies */
645 djw_compute_prefix_1_2 (prefix, clfreq);
646
647 /* Compute codes */
648 djw_build_prefix (clfreq, clclen, DJW_TOTAL_CODES, DJW_MAX_CLCLEN);
649 djw_build_codes (clcode, clclen, DJW_TOTAL_CODES DEBUG_ARG (DJW_MAX_CLCLEN));
650
651 /* Compute number of extra codes beyond basic ones for this template. */
652 num_to_encode = DJW_TOTAL_CODES;
653 while (num_to_encode > DJW_EXTRA_12OFFSET && clclen[num_to_encode-1] == 0) { num_to_encode -= 1; }
654 XD3_ASSERT (num_to_encode - DJW_EXTRA_12OFFSET < (1 << DJW_EXTRA_CODE_BITS));
655
656 /* Encode: # of extra codes */
657 if ((ret = xd3_encode_bits (stream, output, bstate, DJW_EXTRA_CODE_BITS,
658 num_to_encode - DJW_EXTRA_12OFFSET))) { return ret; }
659
660 /* Encode: MTF code lengths */
661 for (i = 0; i < num_to_encode; i += 1)
662 {
663 if ((ret = xd3_encode_bits (stream, output, bstate, DJW_CLCLEN_BITS, clclen[i]))) { return ret; }
664 }
665
666 /* Encode: CLEN code lengths */
667 for (i = 0; i < prefix->mcount; i += 1)
668 {
669 usize_t mtf_sym = prefix->mtfsym[i];
670 usize_t bits = clclen[mtf_sym];
671 usize_t code = clcode[mtf_sym];
672
673 if ((ret = xd3_encode_bits (stream, output, bstate, bits, code))) { return ret; }
674 }
675
676 IF_TUNE (memcpy (tune_freq, clfreq, sizeof (clfreq)));
677
678 return 0;
679}
680
681static void
682djw_compute_selector_1_2 (djw_prefix *prefix,
683 usize_t groups,
684 djw_weight *gbest_freq)
685{
686 uint8_t grmtf[DJW_MAX_GROUPS];
687 usize_t i;
688
689 for (i = 0; i < groups; i += 1) { grmtf[i] = i; }
690
691 djw_compute_mtf_1_2 (prefix, grmtf, gbest_freq, groups);
692}
693
694static int
695xd3_encode_howmany_groups (xd3_stream *stream,
696 xd3_sec_cfg *cfg,
697 usize_t input_size,
698 usize_t *ret_groups,
699 usize_t *ret_sector_size)
700{
701 usize_t cfg_groups = 0;
702 usize_t cfg_sector_size = 0;
703 usize_t sugg_groups = 0;
704 usize_t sugg_sector_size = 0;
705
706 if (cfg->ngroups != 0)
707 {
708 if (cfg->ngroups < 0 || cfg->ngroups > DJW_MAX_GROUPS)
709 {
710 stream->msg = "invalid secondary encoder group number";
711 return XD3_INTERNAL;
712 }
713
714 cfg_groups = cfg->ngroups;
715 }
716
717 if (cfg->sector_size != 0)
718 {
719 if (cfg->sector_size < DJW_SECTORSZ_MULT || cfg->sector_size > DJW_SECTORSZ_MAX || (cfg->sector_size % DJW_SECTORSZ_MULT) != 0)
720 {
721 stream->msg = "invalid secondary encoder sector size";
722 return XD3_INTERNAL;
723 }
724
725 cfg_sector_size = cfg->sector_size;
726 }
727
728 if (cfg_groups == 0 || cfg_sector_size == 0)
729 {
730 /* These values were found empirically using xdelta3-tune around version
731 * xdfs-0.256. */
732 switch (cfg->data_type)
733 {
734 case DATA_SECTION:
735 if (input_size < 1000) { sugg_groups = 1; sugg_sector_size = 0; }
736 else if (input_size < 4000) { sugg_groups = 2; sugg_sector_size = 10; }
737 else if (input_size < 7000) { sugg_groups = 3; sugg_sector_size = 10; }
738 else if (input_size < 10000) { sugg_groups = 4; sugg_sector_size = 10; }
739 else if (input_size < 25000) { sugg_groups = 5; sugg_sector_size = 10; }
740 else if (input_size < 50000) { sugg_groups = 7; sugg_sector_size = 20; }
741 else if (input_size < 100000) { sugg_groups = 8; sugg_sector_size = 30; }
742 else { sugg_groups = 8; sugg_sector_size = 70; }
743 break;
744 case INST_SECTION:
745 if (input_size < 7000) { sugg_groups = 1; sugg_sector_size = 0; }
746 else if (input_size < 10000) { sugg_groups = 2; sugg_sector_size = 50; }
747 else if (input_size < 25000) { sugg_groups = 3; sugg_sector_size = 50; }
748 else if (input_size < 50000) { sugg_groups = 6; sugg_sector_size = 40; }
749 else if (input_size < 100000) { sugg_groups = 8; sugg_sector_size = 40; }
750 else { sugg_groups = 8; sugg_sector_size = 40; }
751 break;
752 case ADDR_SECTION:
753 if (input_size < 9000) { sugg_groups = 1; sugg_sector_size = 0; }
754 else if (input_size < 25000) { sugg_groups = 2; sugg_sector_size = 130; }
755 else if (input_size < 50000) { sugg_groups = 3; sugg_sector_size = 130; }
756 else if (input_size < 100000) { sugg_groups = 5; sugg_sector_size = 130; }
757 else { sugg_groups = 7; sugg_sector_size = 130; }
758 break;
759 }
760
761 if (cfg_groups == 0)
762 {
763 cfg_groups = sugg_groups;
764 }
765
766 if (cfg_sector_size == 0)
767 {
768 cfg_sector_size = sugg_sector_size;
769 }
770 }
771
772 if (cfg_groups != 1 && cfg_sector_size == 0)
773 {
774 switch (cfg->data_type)
775 {
776 case DATA_SECTION:
777 cfg_sector_size = 20;
778 break;
779 case INST_SECTION:
780 cfg_sector_size = 50;
781 break;
782 case ADDR_SECTION:
783 cfg_sector_size = 130;
784 break;
785 }
786 }
787
788 (*ret_groups) = cfg_groups;
789 (*ret_sector_size) = cfg_sector_size;
790
791 XD3_ASSERT (cfg_groups > 0 && cfg_groups <= DJW_MAX_GROUPS);
792 XD3_ASSERT (cfg_groups == 1 || (cfg_sector_size >= DJW_SECTORSZ_MULT && cfg_sector_size <= DJW_SECTORSZ_MAX));
793
794 return 0;
795}
796
797static int
798xd3_real_encode_huff (xd3_stream *stream,
799 djw_stream *h,
800 xd3_output *input,
801 xd3_output *output,
802 xd3_sec_cfg *cfg)
803{
804 int ret;
805 usize_t groups, sector_size;
806 bit_state bstate = BIT_STATE_ENCODE_INIT;
807 xd3_output *in;
808 int encode_bits;
809 usize_t input_bits;
810 usize_t input_bytes;
811 usize_t initial_offset = output->next;
812 djw_weight real_freq[ALPHABET_SIZE];
813 uint8_t *gbest = NULL; /* Dynamic allocations: could put these in djw_stream. */
814 uint8_t *gbest_mtf = NULL;
815
816 input_bytes = djw_count_freqs (real_freq, input);
817 input_bits = input_bytes * 8;
818
819 XD3_ASSERT (input_bytes > 0);
820
821 if ((ret = xd3_encode_howmany_groups (stream, cfg, input_bytes, & groups, & sector_size)))
822 {
823 return ret;
824 }
825
826 if (0)
827 {
828 regroup:
829 /* Sometimes we dynamically decide there are too many groups. Arrive here. */
830 output->next = initial_offset;
831 xd3_bit_state_encode_init (& bstate);
832 }
833
834 /* Encode: # of groups (3 bits) */
835 if ((ret = xd3_encode_bits (stream, & output, & bstate, DJW_GROUP_BITS, groups-1))) { goto failure; }
836
837 if (groups == 1)
838 {
839 /* Single Huffman group. */
840 uint code[ALPHABET_SIZE]; /* Codes */
841 IF_TUNE (uint8_t *clen = tune_clen[0];)
842 IF_NTUNE (uint8_t clen[ALPHABET_SIZE];)
843 uint8_t prefix_mtfsym[ALPHABET_SIZE];
844 djw_prefix prefix;
845
846 encode_bits =
847 djw_build_prefix (real_freq, clen, ALPHABET_SIZE, DJW_MAX_CODELEN);
848 djw_build_codes (code, clen, ALPHABET_SIZE DEBUG_ARG (DJW_MAX_CODELEN));
849
850 if (encode_bits + EFFICIENCY_BITS >= input_bits && ! cfg->inefficient) { goto nosecond; }
851
852 /* Encode: prefix */
853 prefix.mtfsym = prefix_mtfsym;
854 prefix.symbol = clen;
855 prefix.scount = ALPHABET_SIZE;
856
857 if ((ret = djw_encode_prefix (stream, & output, & bstate, & prefix))) { goto failure; }
858
859 if (encode_bits + (8 * output->next) + EFFICIENCY_BITS >= input_bits && ! cfg->inefficient) { goto nosecond; }
860
861 IF_TUNE (tune_prefix_bits = xd3_bitsof_output (output, & bstate));
862 IF_TUNE (tune_select_bits = 0);
863 IF_TUNE (tune_encode_bits = encode_bits);
864
865 /* Encode: data */
866 for (in = input; in; in = in->next_page)
867 {
868 const uint8_t *p = in->base;
869 const uint8_t *p_max = p + in->next;
870
871 do
872 {
873 usize_t sym = *p++;
874 usize_t bits = clen[sym];
875
876 IF_DEBUG (encode_bits -= bits);
877
878 if ((ret = xd3_encode_bits (stream, & output, & bstate, bits, code[sym]))) { goto failure; }
879 }
880 while (p < p_max);
881 }
882
883 XD3_ASSERT (encode_bits == 0);
884 }
885 else
886 {
887 /* DJW Huffman */
888 djw_weight evolve_freq[DJW_MAX_GROUPS][ALPHABET_SIZE];
889#if TUNE_HUFFMAN == 0
890 uint8_t evolve_clen[DJW_MAX_GROUPS][ALPHABET_SIZE];
891#else
892#define evolve_clen tune_clen
893#endif
894 djw_weight left = input_bytes;
895 int gp;
896 int niter = 0;
897 usize_t select_bits;
898 usize_t sym1 = 0, sym2 = 0, s;
899 usize_t gcost[DJW_MAX_GROUPS];
900 uint gbest_code[DJW_MAX_GROUPS+2];
901 uint8_t gbest_clen[DJW_MAX_GROUPS+2];
902 usize_t gbest_max = 1 + (input_bytes - 1) / sector_size;
903 int best_bits = 0;
904 usize_t gbest_no;
905 usize_t gpcnt;
906 const uint8_t *p;
907 IF_DEBUG1 (usize_t gcount[DJW_MAX_GROUPS]);
908
909 /* Encode: sector size (5 bits) */
910 if ((ret = xd3_encode_bits (stream, & output, & bstate,
911 DJW_SECTORSZ_BITS, (sector_size/DJW_SECTORSZ_MULT)-1))) { goto failure; }
912
913 /* Dynamic allocation. */
914 if (gbest == NULL)
915 {
916 if ((gbest = xd3_alloc (stream, gbest_max, 1)) == NULL) { ret = ENOMEM; goto failure; }
917 }
918
919 if (gbest_mtf == NULL)
920 {
921 if ((gbest_mtf = xd3_alloc (stream, gbest_max, 1)) == NULL) { ret = ENOMEM; goto failure; }
922 }
923
924 /* OPT: Some of the inner loops can be optimized, as shown in bzip2 */
925
926 /* Generate initial code length tables. */
927 for (gp = 0; gp < groups; gp += 1)
928 {
929 djw_weight sum = 0;
930 djw_weight goal = left / (groups - gp);
931
932 IF_DEBUG1 (usize_t nz = 0);
933
934 /* Due to the single-code granularity of this distribution, it may be that we
935 * can't generate a distribution for each group. In that case subtract one
936 * group and try again. If (inefficient), we're testing group behavior, so
937 * don't mess things up. */
938 if (goal == 0 && !cfg->inefficient)
939 {
940 IF_DEBUG1 (DP(RINT "too many groups (%u), dropping one\n", groups));
941 groups -= 1;
942 goto regroup;
943 }
944
945 /* Sum == goal is possible when (cfg->inefficient)... */
946 while (sum < goal)
947 {
948 XD3_ASSERT (sym2 < ALPHABET_SIZE);
949 IF_DEBUG1 (nz += real_freq[sym2] != 0);
950 sum += real_freq[sym2++];
951 }
952
953 IF_DEBUG1(DP(RINT "group %u has symbols %u..%u (%u non-zero) (%u/%u = %.3f)\n",
954 gp, sym1, sym2, nz, sum, input_bytes, sum / (double)input_bytes););
955
956 for (s = 0; s < ALPHABET_SIZE; s += 1)
957 {
958 evolve_clen[gp][s] = (s >= sym1 && s <= sym2) ? 1 : 16;
959 }
960
961 left -= sum;
962 sym1 = sym2+1;
963 }
964
965 repeat:
966
967 niter += 1;
968 gbest_no = 0;
969 memset (evolve_freq, 0, sizeof (evolve_freq[0]) * groups);
970 IF_DEBUG1 (memset (gcount, 0, sizeof (gcount[0]) * groups));
971
972 /* For each input page (loop is irregular to allow non-pow2-size group size. */
973 in = input;
974 p = in->base;
975
976 /* For each group-size sector. */
977 do
978 {
979 const uint8_t *p0 = p;
980 xd3_output *in0 = in;
981 usize_t best = 0;
982 usize_t winner = 0;
983
984 /* Select best group for each sector, update evolve_freq. */
985 memset (gcost, 0, sizeof (gcost[0]) * groups);
986
987 /* For each byte in sector. */
988 for (gpcnt = 0; gpcnt < sector_size; gpcnt += 1)
989 {
990 /* For each group. */
991 for (gp = 0; gp < groups; gp += 1)
992 {
993 gcost[gp] += evolve_clen[gp][*p];
994 }
995
996 /* Check end-of-input-page. */
997# define GP_PAGE() \
998 if (++p - in->base == in->next) \
999 { \
1000 in = in->next_page; \
1001 if (in == NULL) { break; } \
1002 p = in->base; \
1003 }
1004
1005 GP_PAGE ();
1006 }
1007
1008 /* Find min cost group for this sector */
1009 best = -1U;
1010 for (gp = 0; gp < groups; gp += 1)
1011 {
1012 if (gcost[gp] < best) { best = gcost[gp]; winner = gp; }
1013 }
1014
1015 XD3_ASSERT(gbest_no < gbest_max);
1016 gbest[gbest_no++] = winner;
1017 IF_DEBUG1 (gcount[winner] += 1);
1018
1019 p = p0;
1020 in = in0;
1021
1022 /* Update group frequencies. */
1023 for (gpcnt = 0; gpcnt < sector_size; gpcnt += 1)
1024 {
1025 evolve_freq[winner][*p] += 1;
1026
1027 GP_PAGE ();
1028 }
1029 }
1030 while (in != NULL);
1031
1032 XD3_ASSERT (gbest_no == gbest_max);
1033
1034 /* Recompute code lengths. */
1035 encode_bits = 0;
1036 for (gp = 0; gp < groups; gp += 1)
1037 {
1038 int i;
1039 uint8_t evolve_zero[ALPHABET_SIZE];
1040 int any_zeros = 0;
1041
1042 memset (evolve_zero, 0, sizeof (evolve_zero));
1043
1044 /* Cannot allow a zero clen when the real frequency is non-zero. Note: this
1045 * means we are going to encode a fairly long code for these unused entries. An
1046 * improvement would be to implement a NOTUSED code for when these are actually
1047 * zero, but this requires another data structure (evolve_zero) since we don't
1048 * know when evolve_freq[i] == 0... Briefly tested, looked worse. */
1049 for (i = 0; i < ALPHABET_SIZE; i += 1)
1050 {
1051 if (evolve_freq[gp][i] == 0 && real_freq[i] != 0)
1052 {
1053 evolve_freq[gp][i] = 1;
1054 evolve_zero[i] = 1;
1055 any_zeros = 1;
1056 }
1057 }
1058
1059 encode_bits += djw_build_prefix (evolve_freq[gp], evolve_clen[gp], ALPHABET_SIZE, DJW_MAX_CODELEN);
1060
1061 /* The above faking of frequencies does not matter for the last iteration, but
1062 * we don't know when that is yet. However, it also breaks the encode_bits
1063 * computation. Necessary for accuracy, and for the (encode_bits==0) assert
1064 * after all bits are output. */
1065 if (any_zeros)
1066 {
1067 IF_DEBUG1 (usize_t save_total = encode_bits);
1068
1069 for (i = 0; i < ALPHABET_SIZE; i += 1)
1070 {
1071 if (evolve_zero[i]) { encode_bits -= evolve_clen[gp][i]; }
1072 }
1073
1074 IF_DEBUG1 (DP(RINT "evolve_zero reduced %u bits in group %u\n", save_total - encode_bits, gp));
1075 }
1076 }
1077
1078 IF_DEBUG1(
1079 DP(RINT "pass %u total bits: %u group uses: ", niter, encode_bits);
1080 for (gp = 0; gp < groups; gp += 1) { DP(RINT "%u ", gcount[gp]); }
1081 DP(RINT "\n"););
1082
1083 /* End iteration. (The following assertion proved invalid.) */
1084 /*XD3_ASSERT (niter == 1 || best_bits >= encode_bits);*/
1085
1086 IF_DEBUG1 (if (niter > 1 && best_bits < encode_bits) {
1087 DP(RINT "iteration lost %u bits\n", encode_bits - best_bits); });
1088
1089 if (niter == 1 || (niter < DJW_MAX_ITER && (best_bits - encode_bits) >= DJW_MIN_IMPROVEMENT))
1090 {
1091 best_bits = encode_bits;
1092 goto repeat;
1093 }
1094
1095 /* Efficiency check. */
1096 if (encode_bits + EFFICIENCY_BITS >= input_bits && ! cfg->inefficient) { goto nosecond; }
1097
1098 IF_DEBUG1 (DP(RINT "djw compression: %u -> %0.3f\n", input_bytes, encode_bits / 8.0));
1099
1100 /* Encode: prefix */
1101 {
1102 uint8_t prefix_symbol[DJW_MAX_GROUPS * ALPHABET_SIZE];
1103 uint8_t prefix_mtfsym[DJW_MAX_GROUPS * ALPHABET_SIZE];
1104 uint8_t prefix_repcnt[DJW_MAX_GROUPS * ALPHABET_SIZE];
1105 djw_prefix prefix;
1106
1107 prefix.symbol = prefix_symbol;
1108 prefix.mtfsym = prefix_mtfsym;
1109 prefix.repcnt = prefix_repcnt;
1110
1111 djw_compute_multi_prefix (groups, evolve_clen, & prefix);
1112 if ((ret = djw_encode_prefix (stream, & output, & bstate, & prefix))) { goto failure; }
1113 }
1114
1115 /* Encode: selector frequencies */
1116 {
1117 djw_weight gbest_freq[DJW_MAX_GROUPS+1];
1118 djw_prefix gbest_prefix;
1119 usize_t i;
1120
1121 gbest_prefix.scount = gbest_no;
1122 gbest_prefix.symbol = gbest;
1123 gbest_prefix.mtfsym = gbest_mtf;
1124
1125 djw_compute_selector_1_2 (& gbest_prefix, groups, gbest_freq);
1126
1127 select_bits =
1128 djw_build_prefix (gbest_freq, gbest_clen, groups+1, DJW_MAX_GBCLEN);
1129 djw_build_codes (gbest_code, gbest_clen, groups+1 DEBUG_ARG (DJW_MAX_GBCLEN));
1130
1131 IF_TUNE (tune_prefix_bits = xd3_bitsof_output (output, & bstate));
1132 IF_TUNE (tune_select_bits = select_bits);
1133 IF_TUNE (tune_encode_bits = encode_bits);
1134
1135 for (i = 0; i < groups+1; i += 1)
1136 {
1137 if ((ret = xd3_encode_bits (stream, & output, & bstate, DJW_GBCLEN_BITS, gbest_clen[i]))) { goto failure; }
1138 }
1139
1140 for (i = 0; i < gbest_prefix.mcount; i += 1)
1141 {
1142 usize_t gp_mtf = gbest_mtf[i];
1143 usize_t gp_sel_bits = gbest_clen[gp_mtf];
1144 usize_t gp_sel_code = gbest_code[gp_mtf];
1145
1146 XD3_ASSERT (gp_mtf < groups+1);
1147
1148 if ((ret = xd3_encode_bits (stream, & output, & bstate, gp_sel_bits, gp_sel_code))) { goto failure; }
1149
1150 IF_DEBUG (select_bits -= gp_sel_bits);
1151 }
1152
1153 XD3_ASSERT (select_bits == 0);
1154 }
1155
1156 /* Efficiency check. */
1157 if (encode_bits + select_bits + (8 * output->next) + EFFICIENCY_BITS >= input_bits && ! cfg->inefficient) { goto nosecond; }
1158
1159 /* Encode: data */
1160 {
1161 uint evolve_code[DJW_MAX_GROUPS][ALPHABET_SIZE];
1162 usize_t sector = 0;
1163
1164 /* Build code tables for each group. */
1165 for (gp = 0; gp < groups; gp += 1)
1166 {
1167 djw_build_codes (evolve_code[gp], evolve_clen[gp], ALPHABET_SIZE DEBUG_ARG (DJW_MAX_CODELEN));
1168 }
1169
1170 /* Now loop over the input. */
1171 in = input;
1172 p = in->base;
1173
1174 do
1175 {
1176 /* For each sector. */
1177 usize_t gp_best = gbest[sector];
1178 uint *gp_codes = evolve_code[gp_best];
1179 uint8_t *gp_clens = evolve_clen[gp_best];
1180
1181 XD3_ASSERT (sector < gbest_no);
1182
1183 sector += 1;
1184
1185 /* Encode the sector data. */
1186 for (gpcnt = 0; gpcnt < sector_size; gpcnt += 1)
1187 {
1188 usize_t sym = *p;
1189 usize_t bits = gp_clens[sym];
1190 usize_t code = gp_codes[sym];
1191
1192 IF_DEBUG (encode_bits -= bits);
1193
1194 if ((ret = xd3_encode_bits (stream, & output, & bstate, bits, code))) { goto failure; }
1195
1196 GP_PAGE ();
1197 }
1198 }
1199 while (in != NULL);
1200
1201 XD3_ASSERT (select_bits == 0);
1202 XD3_ASSERT (encode_bits == 0);
1203
1204#undef evolve_clen
1205 }
1206 }
1207
1208 ret = xd3_flush_bits (stream, & output, & bstate);
1209
1210 if (0)
1211 {
1212 nosecond:
1213 stream->msg = "secondary compression was inefficient";
1214 ret = XD3_NOSECOND;
1215 }
1216
1217 failure:
1218
1219 xd3_free (stream, gbest);
1220 xd3_free (stream, gbest_mtf);
1221 return ret;
1222}
1223#endif /* XD3_ENCODER */
1224
1225/*********************************************************************/
1226/* DECODE */
1227/*********************************************************************/
1228
1229static void
1230djw_build_decoder (xd3_stream *stream,
1231 usize_t asize,
1232 usize_t abs_max,
1233 const uint8_t *clen,
1234 uint8_t *inorder,
1235 uint *base,
1236 uint *limit,
1237 uint *min_clenp,
1238 uint *max_clenp)
1239{
1240 int i, l;
1241 const uint8_t *ci;
1242 uint nr_clen [DJW_MAX_CODELEN+2];
1243 uint tmp_base[DJW_MAX_CODELEN+2];
1244 int min_clen;
1245 int max_clen;
1246
1247 /* Assumption: the two temporary arrays are large enough to hold abs_max. */
1248 XD3_ASSERT (abs_max <= DJW_MAX_CODELEN);
1249
1250 /* This looks something like the start of zlib's inftrees.c */
1251 memset (nr_clen, 0, sizeof (nr_clen[0]) * (abs_max+1));
1252
1253 /* Count number of each code length */
1254 i = asize;
1255 ci = clen;
1256 do
1257 {
1258 /* Caller _must_ check that values are in-range. Most of the time
1259 * the caller decodes a specific number of bits, which imply the max value, and the
1260 * other time the caller decodes a huffman value, which must be in-range. Therefore,
1261 * its an assertion and this function cannot otherwise fail. */
1262 XD3_ASSERT (*ci <= abs_max);
1263
1264 nr_clen[*ci++]++;
1265 }
1266 while (--i != 0);
1267
1268 /* Compute min, max. */
1269 for (i = 1; i <= abs_max; i += 1) { if (nr_clen[i]) { break; } }
1270 min_clen = i;
1271 for (i = abs_max; i != 0; i -= 1) { if (nr_clen[i]) { break; } }
1272 max_clen = i;
1273
1274 /* Fill the BASE, LIMIT table. */
1275 tmp_base[min_clen] = 0;
1276 base[min_clen] = 0;
1277 limit[min_clen] = nr_clen[min_clen] - 1;
1278 for (i = min_clen + 1; i <= max_clen; i += 1)
1279 {
1280 uint last_limit = ((limit[i-1] + 1) << 1);
1281 tmp_base[i] = tmp_base[i-1] + nr_clen[i-1];
1282 limit[i] = last_limit + nr_clen[i] - 1;
1283 base[i] = last_limit - tmp_base[i];
1284 }
1285
1286 /* Fill the inorder array, canonically ordered codes. */
1287 ci = clen;
1288 for (i = 0; i < asize; i += 1)
1289 {
1290 if ((l = *ci++) != 0)
1291 {
1292 inorder[tmp_base[l]++] = i;
1293 }
1294 }
1295
1296 *min_clenp = min_clen;
1297 *max_clenp = max_clen;
1298}
1299
1300static INLINE int
1301djw_decode_symbol (xd3_stream *stream,
1302 bit_state *bstate,
1303 const uint8_t **input,
1304 const uint8_t *input_end,
1305 const uint8_t *inorder,
1306 const uint *base,
1307 const uint *limit,
1308 uint min_clen,
1309 uint max_clen,
1310 usize_t *sym,
1311 usize_t max_sym)
1312{
1313 usize_t code = 0;
1314 usize_t bits = 0;
1315
1316 /* OPT: Supposedly a small lookup table improves speed here... */
1317
1318 /* Code outline is similar to xd3_decode_bits... */
1319 if (bstate->cur_mask == 0x100) { goto next_byte; }
1320
1321 for (;;)
1322 {
1323 do
1324 {
1325 if (bits == max_clen) { goto corrupt; }
1326
1327 bits += 1;
1328 code = (code << 1);
1329
1330 if (bstate->cur_byte & bstate->cur_mask) { code |= 1; }
1331
1332 bstate->cur_mask <<= 1;
1333
1334 if (bits >= min_clen && code <= limit[bits]) { goto done; }
1335 }
1336 while (bstate->cur_mask != 0x100);
1337
1338 next_byte:
1339
1340 if (*input == input_end)
1341 {
1342 stream->msg = "secondary decoder end of input";
1343 return XD3_INTERNAL;
1344 }
1345
1346 bstate->cur_byte = *(*input)++;
1347 bstate->cur_mask = 1;
1348 }
1349
1350 done:
1351
1352 if (base[bits] <= code)
1353 {
1354 usize_t offset = code - base[bits];
1355
1356 if (offset <= max_sym)
1357 {
1358 IF_DEBUG2 (DP(RINT "(j) %u ", code));
1359 *sym = inorder[offset];
1360 return 0;
1361 }
1362 }
1363
1364 corrupt:
1365 stream->msg = "secondary decoder invalid code";
1366 return XD3_INTERNAL;
1367}
1368
1369static int
1370djw_decode_clclen (xd3_stream *stream,
1371 bit_state *bstate,
1372 const uint8_t **input,
1373 const uint8_t *input_end,
1374 uint8_t *cl_inorder,
1375 uint *cl_base,
1376 uint *cl_limit,
1377 uint *cl_minlen,
1378 uint *cl_maxlen,
1379 uint8_t *cl_mtf)
1380{
1381 int ret;
1382 uint8_t cl_clen[DJW_TOTAL_CODES];
1383 usize_t num_codes, value;
1384 int i;
1385
1386 /* How many extra code lengths to encode. */
1387 if ((ret = xd3_decode_bits (stream, bstate, input, input_end, DJW_EXTRA_CODE_BITS, & num_codes))) { return ret; }
1388
1389 num_codes += DJW_EXTRA_12OFFSET;
1390
1391 /* Read num_codes. */
1392 for (i = 0; i < num_codes; i += 1)
1393 {
1394 if ((ret = xd3_decode_bits (stream, bstate, input, input_end, DJW_CLCLEN_BITS, & value))) { return ret; }
1395
1396 cl_clen[i] = value;
1397 }
1398
1399 /* Set the rest to zero. */
1400 for (; i < DJW_TOTAL_CODES; i += 1) { cl_clen[i] = 0; }
1401
1402 /* No need to check for in-range clen values, because: */
1403 XD3_ASSERT (1 << DJW_CLCLEN_BITS == DJW_MAX_CLCLEN + 1);
1404
1405 /* Build the code-length decoder. */
1406 djw_build_decoder (stream, DJW_TOTAL_CODES, DJW_MAX_CLCLEN,
1407 cl_clen, cl_inorder, cl_base, cl_limit, cl_minlen, cl_maxlen);
1408
1409 /* Initialize the MTF state. */
1410 djw_init_clen_mtf_1_2 (cl_mtf);
1411
1412 return 0;
1413}
1414
1415static INLINE int
1416djw_decode_1_2 (xd3_stream *stream,
1417 bit_state *bstate,
1418 const uint8_t **input,
1419 const uint8_t *input_end,
1420 const uint8_t *inorder,
1421 const uint *base,
1422 const uint *limit,
1423 const uint *minlen,
1424 const uint *maxlen,
1425 uint8_t *mtfvals,
1426 usize_t elts,
1427 usize_t skip_offset,
1428 uint8_t *values)
1429{
1430 usize_t n = 0, rep = 0, mtf = 0, s = 0;
1431 int ret;
1432
1433 while (n < elts)
1434 {
1435 /* Special case inside generic code: CLEN only: If not the first group, we already
1436 * know the zero frequencies. */
1437 if (skip_offset != 0 && n >= skip_offset && values[n-skip_offset] == 0)
1438 {
1439 values[n++] = 0;
1440 continue;
1441 }
1442
1443 /* Repeat last symbol. */
1444 if (rep != 0)
1445 {
1446 values[n++] = mtfvals[0];
1447 rep -= 1;
1448 continue;
1449 }
1450
1451 /* Symbol following last repeat code. */
1452 if (mtf != 0)
1453 {
1454 usize_t sym = djw_update_mtf (mtfvals, mtf);
1455 values[n++] = sym;
1456 mtf = 0;
1457 continue;
1458 }
1459
1460 /* Decode next symbol/repeat code. */
1461 if ((ret = djw_decode_symbol (stream, bstate, input, input_end,
1462 inorder, base, limit, *minlen, *maxlen,
1463 & mtf, DJW_TOTAL_CODES))) { return ret; }
1464
1465 if (mtf <= RUN_1)
1466 {
1467 /* Repetition. */
1468 rep = ((mtf + 1) << s);
1469 mtf = 0;
1470 s += 1;
1471 }
1472 else
1473 {
1474 /* Remove the RUN_1 MTF offset. */
1475 mtf -= 1;
1476 s = 0;
1477 }
1478 }
1479
1480 /* If (rep != 0) there were too many codes received. */
1481 if (rep != 0)
1482 {
1483 stream->msg = "secondary decoder invalid repeat code";
1484 return XD3_INTERNAL;
1485 }
1486
1487 return 0;
1488}
1489
1490static INLINE int
1491djw_decode_prefix (xd3_stream *stream,
1492 bit_state *bstate,
1493 const uint8_t **input,
1494 const uint8_t *input_end,
1495 const uint8_t *cl_inorder,
1496 const uint *cl_base,
1497 const uint *cl_limit,
1498 const uint *cl_minlen,
1499 const uint *cl_maxlen,
1500 uint8_t *cl_mtf,
1501 usize_t groups,
1502 uint8_t *clen)
1503{
1504 return djw_decode_1_2 (stream, bstate, input, input_end,
1505 cl_inorder, cl_base, cl_limit, cl_minlen, cl_maxlen, cl_mtf,
1506 ALPHABET_SIZE * groups, ALPHABET_SIZE, clen);
1507}
1508
1509static int
1510xd3_decode_huff (xd3_stream *stream,
1511 djw_stream *h,
1512 const uint8_t **input_pos,
1513 const uint8_t *const input_end,
1514 uint8_t **output_pos,
1515 const uint8_t *const output_end)
1516{
1517 const uint8_t *input = *input_pos;
1518 uint8_t *output = *output_pos;
1519 bit_state bstate = BIT_STATE_DECODE_INIT;
1520 uint8_t *sel_group = NULL;
1521 usize_t groups, gp;
1522 usize_t output_bytes = (output_end - output);
1523 usize_t sector_size;
1524 usize_t sectors;
1525 int ret;
1526
1527 /* Invalid input. */
1528 if (output_bytes == 0)
1529 {
1530 stream->msg = "secondary decoder invalid input";
1531 return XD3_INTERNAL;
1532 }
1533
1534 /* Decode: number of groups */
1535 if ((ret = xd3_decode_bits (stream, & bstate, & input, input_end, DJW_GROUP_BITS, & groups))) { goto fail; }
1536
1537 groups += 1;
1538
1539 if (groups > 1)
1540 {
1541 /* Decode: group size */
1542 if ((ret = xd3_decode_bits (stream, & bstate, & input, input_end, DJW_SECTORSZ_BITS, & sector_size))) { goto fail; }
1543
1544 sector_size = (sector_size + 1) * DJW_SECTORSZ_MULT;
1545 }
1546 else
1547 {
1548 /* Default for groups == 1 */
1549 sector_size = output_bytes;
1550 }
1551
1552 sectors = 1 + (output_bytes - 1) / sector_size;
1553
1554 /* @!@ In the case of groups==1, lots of extra stack space gets used here. Could
1555 * dynamically allocate this memory, which would help with excess parameter passing,
1556 * too. Passing too many parameters in this file, simplify it! */
1557
1558 /* Outer scope: per-group symbol decoder tables. */
1559 {
1560 uint8_t inorder[DJW_MAX_GROUPS][ALPHABET_SIZE];
1561 uint base [DJW_MAX_GROUPS][DJW_MAX_CODELEN+2];
1562 uint limit [DJW_MAX_GROUPS][DJW_MAX_CODELEN+2];
1563 uint minlen [DJW_MAX_GROUPS];
1564 uint maxlen [DJW_MAX_GROUPS];
1565
1566 /* Nested scope: code length decoder tables. */
1567 {
1568 uint8_t clen [DJW_MAX_GROUPS][ALPHABET_SIZE];
1569 uint8_t cl_inorder[DJW_TOTAL_CODES];
1570 uint cl_base [DJW_MAX_CLCLEN+2];
1571 uint cl_limit [DJW_MAX_CLCLEN+2];
1572 uint8_t cl_mtf [DJW_TOTAL_CODES];
1573 uint cl_minlen;
1574 uint cl_maxlen;
1575
1576 /* Compute the code length decoder. */
1577 if ((ret = djw_decode_clclen (stream, & bstate, & input, input_end,
1578 cl_inorder, cl_base, cl_limit, & cl_minlen,
1579 & cl_maxlen, cl_mtf))) { goto fail; }
1580
1581 /* Now decode each group decoder. */
1582 if ((ret = djw_decode_prefix (stream, & bstate, & input, input_end,
1583 cl_inorder, cl_base, cl_limit,
1584 & cl_minlen, & cl_maxlen, cl_mtf,
1585 groups, clen[0]))) { goto fail; }
1586
1587 /* Prepare the actual decoding tables. */
1588 for (gp = 0; gp < groups; gp += 1)
1589 {
1590 djw_build_decoder (stream, ALPHABET_SIZE, DJW_MAX_CODELEN,
1591 clen[gp], inorder[gp], base[gp], limit[gp],
1592 & minlen[gp], & maxlen[gp]);
1593 }
1594 }
1595
1596 /* Decode: selector clens. */
1597 {
1598 uint8_t sel_inorder[DJW_MAX_GROUPS+2];
1599 uint sel_base [DJW_MAX_GBCLEN+2];
1600 uint sel_limit [DJW_MAX_GBCLEN+2];
1601 uint8_t sel_mtf [DJW_MAX_GROUPS+2];
1602 uint sel_minlen;
1603 uint sel_maxlen;
1604
1605 /* Setup group selection. */
1606 if (groups > 1)
1607 {
1608 uint8_t sel_clen[DJW_MAX_GROUPS+1];
1609
1610 for (gp = 0; gp < groups+1; gp += 1)
1611 {
1612 usize_t value;
1613
1614 if ((ret = xd3_decode_bits (stream, & bstate, & input, input_end, DJW_GBCLEN_BITS, & value))) { goto fail; }
1615
1616 sel_clen[gp] = value;
1617 sel_mtf[gp] = gp;
1618 }
1619
1620 if ((sel_group = xd3_alloc (stream, sectors, 1)) == NULL) { ret = ENOMEM; goto fail; }
1621
1622 djw_build_decoder (stream, groups+1, DJW_MAX_GBCLEN, sel_clen,
1623 sel_inorder, sel_base, sel_limit, & sel_minlen, & sel_maxlen);
1624
1625 if ((ret = djw_decode_1_2 (stream, & bstate, & input, input_end,
1626 sel_inorder, sel_base, sel_limit, & sel_minlen, & sel_maxlen, sel_mtf,
1627 sectors, 0, sel_group))) { goto fail; }
1628 }
1629
1630 /* Now decode each sector. */
1631 {
1632 uint8_t *gp_inorder = inorder[0]; /* Initialize for (groups==1) case. */
1633 uint *gp_base = base[0];
1634 uint *gp_limit = limit[0];
1635 uint gp_minlen = minlen[0];
1636 uint gp_maxlen = maxlen[0];
1637 usize_t c;
1638
1639 for (c = 0; c < sectors; c += 1)
1640 {
1641 usize_t n;
1642
1643 if (groups >= 2)
1644 {
1645 gp = sel_group[c];
1646
1647 XD3_ASSERT (gp < groups);
1648
1649 gp_inorder = inorder[gp];
1650 gp_base = base[gp];
1651 gp_limit = limit[gp];
1652 gp_minlen = minlen[gp];
1653 gp_maxlen = maxlen[gp];
1654 }
1655
1656 XD3_ASSERT (output_end - output > 0);
1657
1658 /* Decode next sector. */
1659 n = min (sector_size, (usize_t) (output_end - output));
1660
1661 do
1662 {
1663 usize_t sym;
1664
1665 if ((ret = djw_decode_symbol (stream, & bstate, & input, input_end,
1666 gp_inorder, gp_base, gp_limit, gp_minlen, gp_maxlen,
1667 & sym, ALPHABET_SIZE))) { goto fail; }
1668
1669 *output++ = sym;
1670 }
1671 while (--n);
1672 }
1673 }
1674 }
1675 }
1676
1677 IF_REGRESSION (if ((ret = xd3_test_clean_bits (stream, & bstate))) { goto fail; });
1678 XD3_ASSERT (ret == 0);
1679
1680 fail:
1681 xd3_free (stream, sel_group);
1682
1683 (*input_pos) = input;
1684 (*output_pos) = output;
1685 return ret;
1686}
1687
1688/*********************************************************************/
1689/* TUNING */
1690/*********************************************************************/
1691
1692#if TUNE_HUFFMAN && XD3_ENCODER
1693#include <stdio.h>
1694#include "xdelta3-fgk.h"
1695
1696static uint
1697xd3_bitsof_output (xd3_output *output, bit_state *bstate)
1698{
1699 uint x = 0;
1700 uint m = bstate->cur_mask;
1701
1702 while (m != 1)
1703 {
1704 x += 1;
1705 m >>= 1;
1706 }
1707
1708 return x + 8 * xd3_sizeof_output (output);
1709}
1710
1711static const char* xd3_sect_type (xd3_section_type type)
1712{
1713 switch (type)
1714 {
1715 case DATA_SECTION: return "DATA";
1716 case INST_SECTION: return "INST";
1717 case ADDR_SECTION: return "ADDR";
1718 }
1719 abort ();
1720}
1721
1722static int
1723xd3_encode_huff (xd3_stream *stream,
1724 djw_stream *h,
1725 xd3_output *input,
1726 xd3_output *unused_output,
1727 xd3_sec_cfg *cfg)
1728{
1729 int ret = 0;
1730 int input_size = xd3_sizeof_output (input);
1731 static int hdr = 0;
1732 const char *sect_type = xd3_sect_type (cfg->data_type);
1733 xd3_output *output;
1734 usize_t output_size;
1735
1736 if (hdr == 0) { hdr = 1; DP(RINT "____ SECT INSZ SECTORSZ GPNO OUTSZ PREFIX SELECT ENCODE\n"); }
1737
1738 DP(RINT "SECTION %s %u\n", sect_type, input_size);
1739
1740 {
1741 int gp, i;
1742 int best_size = 99999999;
1743 usize_t best_prefix = 0, best_select = 0, best_encode = 0, best_sector_size = 0;
1744 int best_gpno = -1;
1745 const char *t12 = "12";
1746 usize_t clen_count[DJW_MAX_CODELEN+1];
1747 djw_weight best_freq[DJW_TOTAL_CODES];
1748
1749 for (cfg->ngroups = 1; cfg->ngroups <= /*1*/ DJW_MAX_GROUPS; cfg->ngroups += 1)
1750 {
1751 for (cfg->sector_size = 10; cfg->sector_size <= DJW_SECTORSZ_MAX; cfg->sector_size += 10)
1752 {
1753 output = xd3_alloc_output (stream, NULL);
1754
1755 if ((ret = xd3_real_encode_huff (stream, h, input, output, cfg))) { goto fail; }
1756
1757 output_size = xd3_sizeof_output (output);
1758
1759 if (output_size < best_size)
1760 {
1761 best_size = output_size;
1762 best_gpno = cfg->ngroups;
1763 best_prefix = tune_prefix_bits;
1764 best_select = tune_select_bits;
1765 best_encode = tune_encode_bits;
1766 best_sector_size = cfg->sector_size;
1767 memset (clen_count, 0, sizeof (clen_count));
1768
1769 for (gp = 0; gp < cfg->ngroups; gp += 1)
1770 {
1771 for (i = 0; i < ALPHABET_SIZE; i += 1)
1772 {
1773 clen_count[tune_clen[gp][i]] += 1;
1774 }
1775 }
1776
1777 memcpy (best_freq, tune_freq, sizeof (tune_freq));
1778
1779 XD3_ASSERT (sizeof (tune_freq) == sizeof (mtf_freq));
1780 }
1781
1782 if (1)
1783 {
1784 DP(RINT "COMP%s %u %u %u %u %u %u\n",
1785 t12, cfg->ngroups, cfg->sector_size,
1786 output_size, tune_prefix_bits, tune_select_bits, tune_encode_bits);
1787 }
1788 else
1789 {
1790 fail:
1791 DP(RINT "COMP%s %u %u %u %u %u %u\n",
1792 t12, cfg->ngroups, cfg->sector_size,
1793 input_size, 0, 0, 0);
1794 }
1795
1796 xd3_free_output (stream, output);
1797
1798 XD3_ASSERT (ret == 0 || ret == XD3_NOSECOND);
1799
1800 if (cfg->ngroups == 1) { break; }
1801 }
1802 }
1803
1804 if (best_gpno > 0)
1805 {
1806 DP(RINT "BEST%s %u %u %u %u %u %u\n",
1807 t12, best_gpno, best_sector_size,
1808 best_size, best_prefix, best_select, best_encode);
1809
1810#if 0
1811 DP(RINT "CLEN%s ", t12);
1812 for (i = 1; i <= DJW_MAX_CODELEN; i += 1)
1813 {
1814 DP(RINT "%u ", clen_count[i]);
1815 }
1816 DP(RINT "\n");
1817
1818 DP(RINT "FREQ%s ", t12);
1819 for (i = 0; i < DJW_TOTAL_CODES; i += 1)
1820 {
1821 DP(RINT "%u ", tune_freq[i]);
1822 }
1823 DP(RINT "\n");
1824#endif
1825 }
1826 }
1827
1828 /* Compare to split single-table windows. */
1829 {
1830 int parts, i;
1831
1832 cfg->ngroups = 1;
1833
1834 for (parts = 2; parts <= DJW_MAX_GROUPS; parts += 1)
1835 {
1836 usize_t part_size = input_size / parts;
1837 xd3_output *inp = input, *partin, *partin_head;
1838 usize_t off = 0;
1839 usize_t part_total = 0;
1840
1841 if (part_size < 1000) { break; }
1842
1843 for (i = 0; i < parts; i += 1)
1844 {
1845 usize_t inc;
1846
1847 partin = partin_head = xd3_alloc_output (stream, NULL);
1848 output = xd3_alloc_output (stream, NULL);
1849
1850 for (inc = 0; ((i < parts-1) && inc < part_size) ||
1851 ((i == parts-1) && inp != NULL); )
1852 {
1853 usize_t take;
1854
1855 if (i < parts-1)
1856 {
1857 take = min (part_size - inc, inp->next - off);
1858 }
1859 else
1860 {
1861 take = inp->next - off;
1862 }
1863
1864 ret = xd3_emit_bytes (stream, & partin, inp->base + off, take);
1865
1866 off += take;
1867 inc += take;
1868
1869 if (off == inp->next)
1870 {
1871 inp = inp->next_page;
1872 off = 0;
1873 }
1874 }
1875
1876 ret = xd3_real_encode_huff (stream, h, partin_head, output, cfg);
1877
1878 part_total += xd3_sizeof_output (output);
1879
1880 xd3_free_output (stream, partin_head);
1881 xd3_free_output (stream, output);
1882
1883 XD3_ASSERT (ret == 0 || ret == XD3_NOSECOND);
1884
1885 if (ret == XD3_NOSECOND)
1886 {
1887 break;
1888 }
1889 }
1890
1891 if (ret != XD3_NOSECOND)
1892 {
1893 DP(RINT "PART %u %u\n", parts, part_total);
1894 }
1895 }
1896 }
1897
1898 /* Compare to FGK */
1899 {
1900 fgk_stream *fgk = fgk_alloc (stream);
1901
1902 fgk_init (fgk);
1903
1904 output = xd3_alloc_output (stream, NULL);
1905
1906 ret = xd3_encode_fgk (stream, fgk, input, output, NULL);
1907
1908 output_size = xd3_sizeof_output (output);
1909 xd3_free_output (stream, output);
1910 fgk_destroy (stream, fgk);
1911
1912 XD3_ASSERT (ret == 0);
1913
1914 DP(RINT "FGK %u\n", output_size);
1915 }
1916
1917 DP(RINT "END_SECTION %s %u\n", sect_type, input_size);
1918
1919 return 0;
1920}
1921#endif
1922
1923#endif
Note: See TracBrowser for help on using the repository browser.