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