annotate src/com/jcraft/jzlib/Tree.java @ 301:ca5dd224a87b ganymed

add ecdsa key support everywhere
author Carl Byington <carl@five-ten-sg.com>
date Tue, 29 Jul 2014 18:50:35 -0700
parents 0ce5cc452d02
children 46c2115ae1c8
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
1 /* -*-mode:java; c-basic-offset:2; -*- */
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
2 /*
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
3 Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
4
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
5 Redistribution and use in source and binary forms, with or without
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
6 modification, are permitted provided that the following conditions are met:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
7
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
8 1. Redistributions of source code must retain the above copyright notice,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
9 this list of conditions and the following disclaimer.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
10
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
11 2. Redistributions in binary form must reproduce the above copyright
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
12 notice, this list of conditions and the following disclaimer in
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
13 the documentation and/or other materials provided with the distribution.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
14
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
15 3. The names of the authors may not be used to endorse or promote products
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
16 derived from this software without specific prior written permission.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
17
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
18 THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
19 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
20 FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
21 INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
22 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
23 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
24 OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
25 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
26 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
27 EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
28 */
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
29 /*
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
30 * This program is based on zlib-1.1.3, so all credit should go authors
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
31 * Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
32 * and contributors of zlib.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
33 */
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
34
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
35 package com.jcraft.jzlib;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
36
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
37 final class Tree {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
38 static final private int MAX_BITS = 15;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
39 static final private int BL_CODES = 19;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
40 static final private int D_CODES = 30;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
41 static final private int LITERALS = 256;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
42 static final private int LENGTH_CODES = 29;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
43 static final private int L_CODES = (LITERALS + 1 + LENGTH_CODES);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
44 static final private int HEAP_SIZE = (2 * L_CODES + 1);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
45
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
46 // Bit length codes must not exceed MAX_BL_BITS bits
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
47 static final int MAX_BL_BITS = 7;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
48
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
49 // end of block literal code
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
50 static final int END_BLOCK = 256;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
51
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
52 // repeat previous bit length 3-6 times (2 bits of repeat count)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
53 static final int REP_3_6 = 16;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
54
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
55 // repeat a zero length 3-10 times (3 bits of repeat count)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
56 static final int REPZ_3_10 = 17;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
57
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
58 // repeat a zero length 11-138 times (7 bits of repeat count)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
59 static final int REPZ_11_138 = 18;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
60
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
61 // extra bits for each length code
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
62 static final int[] extra_lbits = {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
63 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
64 };
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
65
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
66 // extra bits for each distance code
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
67 static final int[] extra_dbits = {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
68 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
69 };
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
70
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
71 // extra bits for each bit length code
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
72 static final int[] extra_blbits = {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
73 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
74 };
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
75
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
76 static final byte[] bl_order = {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
77 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
78 };
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
79
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
80
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
81 // The lengths of the bit length codes are sent in order of decreasing
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
82 // probability, to avoid transmitting the lengths for unused bit
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
83 // length codes.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
84
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
85 static final int Buf_size = 8 * 2;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
86
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
87 // see definition of array dist_code below
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
88 static final int DIST_CODE_LEN = 512;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
89
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
90 static final byte[] _dist_code = {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
91 0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
92 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
93 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
94 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
95 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
96 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
97 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
98 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
99 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
100 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
101 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
102 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
103 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 0, 0, 16, 17,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
104 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
105 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
106 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
107 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
108 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
109 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
110 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
111 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
112 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
113 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
114 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
115 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
116 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
117 };
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
118
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
119 static final byte[] _length_code = {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
120 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 12, 12,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
121 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
122 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
123 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
124 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
125 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
126 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
127 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
128 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
129 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
130 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
131 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
132 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
133 };
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
134
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
135 static final int[] base_length = {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
136 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
137 64, 80, 96, 112, 128, 160, 192, 224, 0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
138 };
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
139
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
140 static final int[] base_dist = {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
141 0, 1, 2, 3, 4, 6, 8, 12, 16, 24,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
142 32, 48, 64, 96, 128, 192, 256, 384, 512, 768,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
143 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
144 };
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
145
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
146 // Mapping from a distance to a distance code. dist is the distance - 1 and
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
147 // must not have side effects. _dist_code[256] and _dist_code[257] are never
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
148 // used.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
149 static int d_code(int dist) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
150 return ((dist) < 256 ? _dist_code[dist] : _dist_code[256 + ((dist) >>> 7)]);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
151 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
152
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
153 short[] dyn_tree; // the dynamic tree
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
154 int max_code; // largest code with non zero frequency
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
155 StaticTree stat_desc; // the corresponding static tree
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
156
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
157 // Compute the optimal bit lengths for a tree and update the total bit length
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
158 // for the current block.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
159 // IN assertion: the fields freq and dad are set, heap[heap_max] and
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
160 // above are the tree nodes sorted by increasing frequency.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
161 // OUT assertions: the field len is set to the optimal bit length, the
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
162 // array bl_count contains the frequencies for each bit length.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
163 // The length opt_len is updated; static_len is also updated if stree is
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
164 // not null.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
165 void gen_bitlen(Deflate s) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
166 short[] tree = dyn_tree;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
167 short[] stree = stat_desc.static_tree;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
168 int[] extra = stat_desc.extra_bits;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
169 int base = stat_desc.extra_base;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
170 int max_length = stat_desc.max_length;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
171 int h; // heap index
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
172 int n, m; // iterate over the tree elements
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
173 int bits; // bit length
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
174 int xbits; // extra bits
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
175 short f; // frequency
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
176 int overflow = 0; // number of elements with bit length too large
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
177
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
178 for (bits = 0; bits <= MAX_BITS; bits++) s.bl_count[bits] = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
179
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
180 // In a first pass, compute the optimal bit lengths (which may
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
181 // overflow in the case of the bit length tree).
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
182 tree[s.heap[s.heap_max] * 2 + 1] = 0; // root of the heap
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
183
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
184 for (h = s.heap_max + 1; h < HEAP_SIZE; h++) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
185 n = s.heap[h];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
186 bits = tree[tree[n * 2 + 1] * 2 + 1] + 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
187
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
188 if (bits > max_length) { bits = max_length; overflow++; }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
189
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
190 tree[n * 2 + 1] = (short)bits;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
191
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
192 // We overwrite tree[n*2+1] which is no longer needed
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
193 if (n > max_code) continue; // not a leaf node
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
194
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
195 s.bl_count[bits]++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
196 xbits = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
197
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
198 if (n >= base) xbits = extra[n - base];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
199
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
200 f = tree[n * 2];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
201 s.opt_len += f * (bits + xbits);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
202
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
203 if (stree != null) s.static_len += f * (stree[n * 2 + 1] + xbits);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
204 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
205
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
206 if (overflow == 0) return;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
207
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
208 // This happens for example on obj2 and pic of the Calgary corpus
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
209 // Find the first bit length which could increase:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
210 do {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
211 bits = max_length - 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
212
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
213 while (s.bl_count[bits] == 0) bits--;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
214
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
215 s.bl_count[bits]--; // move one leaf down the tree
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
216 s.bl_count[bits + 1] += 2; // move one overflow item as its brother
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
217 s.bl_count[max_length]--;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
218 // The brother of the overflow item also moves one step up,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
219 // but this does not affect bl_count[max_length]
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
220 overflow -= 2;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
221 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
222 while (overflow > 0);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
223
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
224 for (bits = max_length; bits != 0; bits--) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
225 n = s.bl_count[bits];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
226
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
227 while (n != 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
228 m = s.heap[--h];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
229
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
230 if (m > max_code) continue;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
231
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
232 if (tree[m * 2 + 1] != bits) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
233 s.opt_len += ((long)bits - (long)tree[m * 2 + 1]) * (long)tree[m * 2];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
234 tree[m * 2 + 1] = (short)bits;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
235 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
236
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
237 n--;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
238 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
239 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
240 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
241
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
242 // Construct one Huffman tree and assigns the code bit strings and lengths.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
243 // Update the total bit length for the current block.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
244 // IN assertion: the field freq is set for all tree elements.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
245 // OUT assertions: the fields len and code are set to the optimal bit length
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
246 // and corresponding code. The length opt_len is updated; static_len is
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
247 // also updated if stree is not null. The field max_code is set.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
248 void build_tree(Deflate s) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
249 short[] tree = dyn_tree;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
250 short[] stree = stat_desc.static_tree;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
251 int elems = stat_desc.elems;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
252 int n, m; // iterate over heap elements
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
253 int max_code = -1; // largest code with non zero frequency
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
254 int node; // new node being created
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
255 // Construct the initial heap, with least frequent element in
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
256 // heap[1]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
257 // heap[0] is not used.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
258 s.heap_len = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
259 s.heap_max = HEAP_SIZE;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
260
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
261 for (n = 0; n < elems; n++) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
262 if (tree[n * 2] != 0) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
263 s.heap[++s.heap_len] = max_code = n;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
264 s.depth[n] = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
265 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
266 else {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
267 tree[n * 2 + 1] = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
268 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
269 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
270
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
271 // The pkzip format requires that at least one distance code exists,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
272 // and that at least one bit should be sent even if there is only one
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
273 // possible code. So to avoid special checks later on we force at least
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
274 // two codes of non zero frequency.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
275 while (s.heap_len < 2) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
276 node = s.heap[++s.heap_len] = (max_code < 2 ? ++max_code : 0);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
277 tree[node * 2] = 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
278 s.depth[node] = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
279 s.opt_len--; if (stree != null) s.static_len -= stree[node * 2 + 1];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
280 // node is 0 or 1 so it does not have extra bits
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
281 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
282
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
283 this.max_code = max_code;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
284
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
285 // The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
286 // establish sub-heaps of increasing lengths:
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
287 for (n = s.heap_len / 2; n >= 1; n--)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
288 s.pqdownheap(tree, n);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
289
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
290 // Construct the Huffman tree by repeatedly combining the least two
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
291 // frequent nodes.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
292 node = elems; // next internal node of the tree
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
293
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
294 do {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
295 // n = node of least frequency
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
296 n = s.heap[1];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
297 s.heap[1] = s.heap[s.heap_len--];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
298 s.pqdownheap(tree, 1);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
299 m = s.heap[1]; // m = node of next least frequency
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
300 s.heap[--s.heap_max] = n; // keep the nodes sorted by frequency
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
301 s.heap[--s.heap_max] = m;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
302 // Create a new node father of n and m
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
303 tree[node * 2] = (short)(tree[n * 2] + tree[m * 2]);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
304 s.depth[node] = (byte)(Math.max(s.depth[n], s.depth[m]) + 1);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
305 tree[n * 2 + 1] = tree[m * 2 + 1] = (short)node;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
306 // and insert the new node in the heap
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
307 s.heap[1] = node++;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
308 s.pqdownheap(tree, 1);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
309 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
310 while (s.heap_len >= 2);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
311
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
312 s.heap[--s.heap_max] = s.heap[1];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
313 // At this point, the fields freq and dad are set. We can now
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
314 // generate the bit lengths.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
315 gen_bitlen(s);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
316 // The field len is now set, we can generate the bit codes
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
317 gen_codes(tree, max_code, s.bl_count);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
318 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
319
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
320 // Generate the codes for a given tree and bit counts (which need not be
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
321 // optimal).
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
322 // IN assertion: the array bl_count contains the bit length statistics for
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
323 // the given tree and the field len is set for all tree elements.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
324 // OUT assertion: the field code is set for all tree elements of non
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
325 // zero code length.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
326 static void gen_codes(short[] tree, // the tree to decorate
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
327 int max_code, // largest code with non zero frequency
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
328 short[] bl_count // number of codes at each bit length
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
329 ) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
330 short[] next_code = new short[MAX_BITS + 1]; // next code value for each bit length
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
331 short code = 0; // running code value
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
332 int bits; // bit index
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
333 int n; // code index
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
334
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
335 // The distribution counts are first used to generate the code values
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
336 // without bit reversal.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
337 for (bits = 1; bits <= MAX_BITS; bits++) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
338 next_code[bits] = code = (short)((code + bl_count[bits - 1]) << 1);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
339 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
340
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
341 // Check that the bit counts in bl_count are consistent. The last code
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
342 // must be all ones.
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
343 //Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
344 // "inconsistent bit counts");
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
345 //Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
346 for (n = 0; n <= max_code; n++) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
347 int len = tree[n * 2 + 1];
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
348
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
349 if (len == 0) continue;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
350
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
351 // Now reverse the bits
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
352 tree[n * 2] = (short)(bi_reverse(next_code[len]++, len));
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
353 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
354 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
355
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
356 // Reverse the first len bits of a code, using straightforward code (a faster
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
357 // method would use a table)
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
358 // IN assertion: 1 <= len <= 15
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
359 static int bi_reverse(int code, // the value to invert
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
360 int len // its bit length
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
361 ) {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
362 int res = 0;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
363
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
364 do {
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
365 res |= code & 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
366 code >>>= 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
367 res <<= 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
368 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
369 while (--len > 0);
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
370
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
371 return res >>> 1;
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
372 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
373 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
374