« back to all changes in this revision
Viewing changes to xdelta3-djw.h
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): A Mennucc1
- Date: 2007-08-26 16:06:58 UTC
- Revision ID: james.westby@ubuntu.com-20070826160658-o16ja43dsv4d0kgl
Tags: upstream-0q.dfsg
Import upstream version 0q.dfsg
- files added:
- examples
added
removed
xdelta3-djw.h
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
84
typedef struct _djw_stream djw_stream;
85
typedef struct _djw_heapen djw_heapen;
86
typedef struct _djw_prefix djw_prefix;
87
typedef 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
99
static uint xd3_bitsof_output (xd3_output *output, bit_state *bstate);
100
#define IF_TUNE(x) x
101
#define IF_NTUNE(x)
102
static djw_weight tune_freq[DJW_TOTAL_CODES];
103
static uint8_t tune_clen[DJW_MAX_GROUPS][ALPHABET_SIZE];
104
static usize_t tune_prefix_bits;
105
static usize_t tune_select_bits;
106
static usize_t tune_encode_bits;
107
#endif
108
struct _djw_heapen
109
{
110
uint32_t depth;
111
uint32_t freq;
112
uint32_t parent;
113
};
114
115
struct _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
124
struct _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
180
static 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
185
static const uint8_t djw_encode_12basic[DJW_BASIC_CODES] =
186
{
187
4, 5, 6, 7, 8,
188
};
189
190
/*********************************************************************/
191
/* DECLS */
192
/*********************************************************************/
193
194
static djw_stream* djw_alloc (xd3_stream *stream /*, int alphabet_size */);
195
static void djw_init (djw_stream *h);
196
static void djw_destroy (xd3_stream *stream,
197
djw_stream *h);
198
199
#if XD3_ENCODER
200
static 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
207
static 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
218
static djw_stream*
219
djw_alloc (xd3_stream *stream)
220
{
221
return xd3_alloc (stream, sizeof (djw_stream), 1);
222
}
223
224
static void
225
djw_init (djw_stream *h)
226
{
227
/* Fields are initialized prior to use. */
228
}
229
230
static void
231
djw_destroy (xd3_stream *stream,
232
djw_stream *h)
233
{
234
xd3_free (stream, h);
235
}
236
237
238
/*********************************************************************/
239
/* HEAP */
240
/*********************************************************************/
241
242
static INLINE int
243
heap_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
250
static INLINE void
251
heap_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
266
static INLINE djw_heapen*
267
heap_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
298
static void
299
heap_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
314
static INLINE usize_t
315
djw_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
326
static INLINE void
327
djw_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
347
static void
348
djw_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
361
static usize_t
362
djw_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
483
static void
484
djw_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
/*********************************************************************/
517
static void
518
djw_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
569
static usize_t
570
djw_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
596
static void
597
djw_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
620
static void
621
djw_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
630
static int
631
djw_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
681
static void
682
djw_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
694
static int
695
xd3_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
797
static int
798
xd3_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
1229
static void
1230
djw_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
1300
static INLINE int
1301
djw_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
1369
static int
1370
djw_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
1415
static INLINE int
1416
djw_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
1490
static INLINE int
1491
djw_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
1509
static int
1510
xd3_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
1696
static uint
1697
xd3_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
1711
static 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
1722
static int
1723
xd3_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
Loggerhead is a web-based interface for Breezy
Version: 2.0.1