Mercurial > 510Connectbot

annotate src/com/jcraft/jzlib/Tree.java @ 361:395a16681ae1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add help files to the web documentation
author Carl Byington <carl@five-ten-sg.com>
date Mon, 04 Aug 2014 08:23:36 -0700
parents 46c2115ae1c8
children
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
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
11 2. Redistributions in binary form must reproduce the above copyright
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
12 notice, this list of conditions and the following disclaimer in
0
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
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
37 final class Tree{
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
38 static final private int MAX_BITS=15;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
39 static final private int BL_CODES=19;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
40 static final private int D_CODES=30;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
41 static final private int LITERALS=256;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
42 static final private int LENGTH_CODES=29;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
43 static final private int L_CODES=(LITERALS+1+LENGTH_CODES);
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
44 static final private int HEAP_SIZE=(2*L_CODES+1);
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
45
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
46 // Bit length codes must not exceed MAX_BL_BITS bits
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
47 static final int MAX_BL_BITS=7;
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
48
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
49 // end of block literal code
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
50 static final int END_BLOCK=256;
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
51
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
52 // repeat previous bit length 3-6 times (2 bits of repeat count)
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
53 static final int REP_3_6=16;
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
54
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
55 // repeat a zero length 3-10 times (3 bits of repeat count)
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
56 static final int REPZ_3_10=17;
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
57
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
58 // repeat a zero length 11-138 times (7 bits of repeat count)
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
59 static final int REPZ_11_138=18;
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
60
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
61 // extra bits for each length code
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
62 static final int[] extra_lbits={
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
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
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
64 };
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
65
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
66 // extra bits for each distance code
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
67 static final int[] extra_dbits={
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
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
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
69 };
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
70
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
71 // extra bits for each bit length code
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
72 static final int[] extra_blbits={
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
73 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
74 };
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
75
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
76 static final byte[] bl_order={
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
77 16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
0
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
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
80 // The lengths of the bit length codes are sent in order of decreasing
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
81 // probability, to avoid transmitting the lengths for unused bit
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
82 // length codes.
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
83
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
84 static final int Buf_size=8*2;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
85
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
86 // see definition of array dist_code below
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
87 static final int DIST_CODE_LEN=512;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
88
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
89 static final byte[] _dist_code = {
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
90 0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
91 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
92 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
93 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
94 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
95 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
96 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
97 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
98 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
99 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
100 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
101 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
102 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 0, 0, 16, 17,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
103 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
104 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
105 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
106 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
107 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
108 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
109 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
110 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
111 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
112 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
113 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
114 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
115 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
116 };
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
117
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
118 static final byte[] _length_code={
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
119 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 12, 12,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
120 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
121 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
122 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
123 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
124 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
125 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
126 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
127 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
128 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
129 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
130 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
131 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
132 };
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
133
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
134 static final int[] base_length = {
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
135 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
136 64, 80, 96, 112, 128, 160, 192, 224, 0
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
137 };
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
138
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
139 static final int[] base_dist = {
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
140 0, 1, 2, 3, 4, 6, 8, 12, 16, 24,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
141 32, 48, 64, 96, 128, 192, 256, 384, 512, 768,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
142 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
143 };
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
144
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
145 // Mapping from a distance to a distance code. dist is the distance - 1 and
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
146 // must not have side effects. _dist_code[256] and _dist_code[257] are never
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
147 // used.
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
148 static int d_code(int dist){
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
149 return ((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>>7)]);
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
150 }
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
151
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
152 short[] dyn_tree; // the dynamic tree
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
153 int max_code; // largest code with non zero frequency
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
154 StaticTree stat_desc; // the corresponding static tree
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
155
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
156 // Compute the optimal bit lengths for a tree and update the total bit length
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
157 // for the current block.
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
158 // IN assertion: the fields freq and dad are set, heap[heap_max] and
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
159 // above are the tree nodes sorted by increasing frequency.
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
160 // OUT assertions: the field len is set to the optimal bit length, the
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
161 // array bl_count contains the frequencies for each bit length.
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
162 // The length opt_len is updated; static_len is also updated if stree is
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
163 // not null.
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
164 void gen_bitlen(Deflate s){
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
165 short[] tree = dyn_tree;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
166 short[] stree = stat_desc.static_tree;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
167 int[] extra = stat_desc.extra_bits;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
168 int base = stat_desc.extra_base;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
169 int max_length = stat_desc.max_length;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
170 int h; // heap index
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
171 int n, m; // iterate over the tree elements
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
172 int bits; // bit length
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
173 int xbits; // extra bits
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
174 short f; // frequency
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
175 int overflow = 0; // number of elements with bit length too large
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
176
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
177 for (bits = 0; bits <= MAX_BITS; bits++) s.bl_count[bits] = 0;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
178
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
179 // In a first pass, compute the optimal bit lengths (which may
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
180 // overflow in the case of the bit length tree).
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
181 tree[s.heap[s.heap_max]*2+1] = 0; // root of the heap
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
182
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
183 for(h=s.heap_max+1; h<HEAP_SIZE; h++){
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
184 n = s.heap[h];
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
185 bits = tree[tree[n*2+1]*2+1] + 1;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
186 if (bits > max_length){ bits = max_length; overflow++; }
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
187 tree[n*2+1] = (short)bits;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
188 // We overwrite tree[n*2+1] which is no longer needed
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
189
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
190 if (n > max_code) continue; // not a leaf node
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
191
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
192 s.bl_count[bits]++;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
193 xbits = 0;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
194 if (n >= base) xbits = extra[n-base];
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
195 f = tree[n*2];
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
196 s.opt_len += f * (bits + xbits);
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
197 if (stree!=null) s.static_len += f * (stree[n*2+1] + xbits);
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
198 }
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
199 if (overflow == 0) return;
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
200
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
201 // This happens for example on obj2 and pic of the Calgary corpus
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
202 // Find the first bit length which could increase:
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
203 do {
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
204 bits = max_length-1;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
205 while(s.bl_count[bits]==0) bits--;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
206 s.bl_count[bits]--; // move one leaf down the tree
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
207 s.bl_count[bits+1]+=2; // move one overflow item as its brother
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
208 s.bl_count[max_length]--;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
209 // The brother of the overflow item also moves one step up,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
210 // but this does not affect bl_count[max_length]
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
211 overflow -= 2;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
212 }
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
213 while (overflow > 0);
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
214
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
215 for (bits = max_length; bits != 0; bits--) {
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
216 n = s.bl_count[bits];
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
217 while (n != 0) {
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
218 m = s.heap[--h];
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
219 if (m > max_code) continue;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
220 if (tree[m*2+1] != bits) {
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
221 s.opt_len += ((long)bits - (long)tree[m*2+1])*(long)tree[m*2];
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
222 tree[m*2+1] = (short)bits;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
223 }
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
224 n--;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
225 }
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
226 }
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
227 }
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
228
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
229 // Construct one Huffman tree and assigns the code bit strings and lengths.
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
230 // Update the total bit length for the current block.
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
231 // IN assertion: the field freq is set for all tree elements.
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
232 // OUT assertions: the fields len and code are set to the optimal bit length
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
233 // and corresponding code. The length opt_len is updated; static_len is
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
234 // also updated if stree is not null. The field max_code is set.
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
235 void build_tree(Deflate s){
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
236 short[] tree=dyn_tree;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
237 short[] stree=stat_desc.static_tree;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
238 int elems=stat_desc.elems;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
239 int n, m; // iterate over heap elements
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
240 int max_code=-1; // largest code with non zero frequency
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
241 int node; // new node being created
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
242
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
243 // Construct the initial heap, with least frequent element in
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
244 // heap[1]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
245 // heap[0] is not used.
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
246 s.heap_len = 0;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
247 s.heap_max = HEAP_SIZE;
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
248
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
249 for(n=0; n<elems; n++) {
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
250 if(tree[n*2] != 0) {
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
251 s.heap[++s.heap_len] = max_code = n;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
252 s.depth[n] = 0;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
253 }
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
254 else{
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
255 tree[n*2+1] = 0;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
256 }
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
257 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
258
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
259 // The pkzip format requires that at least one distance code exists,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
260 // and that at least one bit should be sent even if there is only one
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
261 // possible code. So to avoid special checks later on we force at least
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
262 // two codes of non zero frequency.
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
263 while (s.heap_len < 2) {
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
264 node = s.heap[++s.heap_len] = (max_code < 2 ? ++max_code : 0);
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
265 tree[node*2] = 1;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
266 s.depth[node] = 0;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
267 s.opt_len--; if (stree!=null) s.static_len -= stree[node*2+1];
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
268 // node is 0 or 1 so it does not have extra bits
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
269 }
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
270 this.max_code = max_code;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
271
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
272 // The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
273 // establish sub-heaps of increasing lengths:
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
274
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
275 for(n=s.heap_len/2;n>=1; n--)
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
276 s.pqdownheap(tree, n);
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
277
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
278 // Construct the Huffman tree by repeatedly combining the least two
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
279 // frequent nodes.
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
280
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
281 node=elems; // next internal node of the tree
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
282 do{
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
283 // n = node of least frequency
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
284 n=s.heap[1];
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
285 s.heap[1]=s.heap[s.heap_len--];
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
286 s.pqdownheap(tree, 1);
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
287 m=s.heap[1]; // m = node of next least frequency
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
288
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
289 s.heap[--s.heap_max] = n; // keep the nodes sorted by frequency
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
290 s.heap[--s.heap_max] = m;
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
291
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
292 // Create a new node father of n and m
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
293 tree[node*2] = (short)(tree[n*2] + tree[m*2]);
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
294 s.depth[node] = (byte)(Math.max(s.depth[n],s.depth[m])+1);
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
295 tree[n*2+1] = tree[m*2+1] = (short)node;
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
296
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
297 // and insert the new node in the heap
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
298 s.heap[1] = node++;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
299 s.pqdownheap(tree, 1);
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
300 }
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
301 while(s.heap_len>=2);
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
302
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
303 s.heap[--s.heap_max] = s.heap[1];
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
304
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
305 // At this point, the fields freq and dad are set. We can now
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
306 // generate the bit lengths.
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
307
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
308 gen_bitlen(s);
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
309
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
310 // The field len is now set, we can generate the bit codes
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
311 gen_codes(tree, max_code, s.bl_count, s.next_code);
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
312 }
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
313
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
314 // Generate the codes for a given tree and bit counts (which need not be
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
315 // optimal).
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
316 // IN assertion: the array bl_count contains the bit length statistics for
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
317 // the given tree and the field len is set for all tree elements.
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
318 // OUT assertion: the field code is set for all tree elements of non
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
319 // zero code length.
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
320 private final static void gen_codes(
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
321 short[] tree, // the tree to decorate
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
322 int max_code, // largest code with non zero frequency
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
323 short[] bl_count, // number of codes at each bit length
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
324 short[] next_code){
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
325 short code = 0; // running code value
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
326 int bits; // bit index
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
327 int n; // code index
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
328
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
329 // The distribution counts are first used to generate the code values
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
330 // without bit reversal.
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
331 next_code[0]=0;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
332 for (bits = 1; bits <= MAX_BITS; bits++) {
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
333 next_code[bits] = code = (short)((code + bl_count[bits-1]) << 1);
0
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
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
336 // Check that the bit counts in bl_count are consistent. The last code
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
337 // must be all ones.
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
338 //Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
339 // "inconsistent bit counts");
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
340 //Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
341
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
342 for (n = 0; n <= max_code; n++) {
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
343 int len = tree[n*2+1];
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
344 if (len == 0) continue;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
345 // Now reverse the bits
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
346 tree[n*2] = (short)(bi_reverse(next_code[len]++, len));
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
347 }
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
348 }
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
349
357
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
350 // Reverse the first len bits of a code, using straightforward code (a faster
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
351 // method would use a table)
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
352 // IN assertion: 1 <= len <= 15
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
353 private final static int bi_reverse(
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
354 int code, // the value to invert
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
355 int len // its bit length
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
356 ){
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
357 int res = 0;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
358 do{
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
359 res|=code&1;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
360 code>>>=1;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
361 res<<=1;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
362 }
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
363 while(--len>0);
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
364 return res>>>1;
46c2115ae1c8 update jzlib to a21be20213d66eff15904d925e9b721956a01ef7
Carl Byington <carl@five-ten-sg.com>
parents: 0
diff changeset
365 }
0
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
366 }
0ce5cc452d02 initial version
Carl Byington <carl@five-ten-sg.com>
parents:
diff changeset
367