Mercurial > 510Connectbot

annotate app/src/main/java/com/jcraft/jzlib/Tree.java @ 512:e1dd1fd46e18

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
change connections file name and look for it in the accuspeech voice projects directory, then the downloads directory
author Carl Byington <carl@five-ten-sg.com>
date Fri, 10 Feb 2023 14:32:41 -0700
parents d29cce60f393
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