nexmon – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /***************************************************************************
2 * *
3 * ########### ########### ########## ########## *
4 * ############ ############ ############ ############ *
5 * ## ## ## ## ## ## ## *
6 * ## ## ## ## ## ## ## *
7 * ########### #### ###### ## ## ## ## ###### *
8 * ########### #### # ## ## ## ## # # *
9 * ## ## ###### ## ## ## ## # # *
10 * ## ## # ## ## ## ## # # *
11 * ############ ##### ###### ## ## ## ##### ###### *
12 * ########### ########### ## ## ## ########## *
13 * *
14 * S E C U R E M O B I L E N E T W O R K I N G *
15 * *
16 * This file is part of NexMon. *
17 * *
18 * Based on: *
19 * *
20 * tinflate -- tiny inflate library *
21 * *
22 * Copyright (c) 2016 NexMon Team *
23 * *
24 * NexMon is free software: you can redistribute it and/or modify *
25 * it under the terms of the GNU General Public License as published by *
26 * the Free Software Foundation, either version 3 of the License, or *
27 * (at your option) any later version. *
28 * *
29 * NexMon is distributed in the hope that it will be useful, *
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
32 * GNU General Public License for more details. *
33 * *
34 * You should have received a copy of the GNU General Public License *
35 * along with NexMon. If not, see <http://www.gnu.org/licenses/>. *
36 * *
37 **************************************************************************/
38  
39 #pragma NEXMON targetregion "ucode"
40  
41 #include <firmware_version.h> // definition of firmware version macros
42 #include <debug.h> // contains macros to access the debug hardware
43 #include <wrapper.h> // wrapper definitions for functions that already exist in the firmware
44 #include <structs.h> // structures that are used by the code in the firmware
45 #include <helper.h> // useful helper functions
46 #include <patcher.h> // macros used to craete patches such as BLPatch, BPatch, ...
47 #include <objmem.h> // Functions to access object memory
48  
49 #define OBJADDR_UCM_SEL 0x00000000
50 #define OBJADDR_UCMX_SEL 0x00080000
51  
52  
53 extern unsigned char ucode_compressed_bin[];
54 extern unsigned int ucode_compressed_bin_len;
55  
56 /**
57 * Function used by tinflate_partial to write a byte to an address in the output buffer
58 * here it is implemented to directly write to the object memory of the d11 core
59 */
60 void
61 tinflate_write_objmem(void *out_base, unsigned long idx, unsigned char value)
62 {
63 wlc_bmac_write_objmem_byte((struct wlc_hw_info *) out_base, idx, value, OBJADDR_UCM_SEL);
64 }
65  
66 /**
67 * Function used by tinflate_partial to read a byte from an address in the output buffer
68 * here it is implemented to directly read from the object memory of the d11 core
69 */
70 unsigned char
71 tinflate_read_objmem(void *out_base, unsigned long idx)
72 {
73 return wlc_bmac_read_objmem_byte((struct wlc_hw_info *) out_base, idx, OBJADDR_UCM_SEL);
74 }
75  
76 /**
77 * Function used by tinflate_partial to write a byte to an address in the output buffer
78 * here it is implemented to directly write to the object memory of the d11 core
79 */
80 void
81 tinflate_write_objmemx(void *out_base, unsigned long idx, unsigned char value)
82 {
83 wlc_bmac_write_objmem_byte((struct wlc_hw_info *) out_base, idx, value, OBJADDR_UCMX_SEL);
84 }
85  
86 /**
87 * Function used by tinflate_partial to read a byte from an address in the output buffer
88 * here it is implemented to directly read from the object memory of the d11 core
89 */
90 unsigned char
91 tinflate_read_objmemx(void *out_base, unsigned long idx)
92 {
93 return wlc_bmac_read_objmem_byte((struct wlc_hw_info *) out_base, idx, OBJADDR_UCMX_SEL);
94 }
95  
96 /*
97 * tinflate.c -- tiny inflate library
98 *
99 * Written by Andrew Church <achurch@achurch.org>
100 * This source code is public domain.
101 */
102  
103 /* Structure of the decompression state buffer. */
104 typedef struct DecompressionState_ {
105 /* state: Parsing state. Used to resume processing at the appropriate
106 * point after running out of data while decompressing a block. */
107 enum {
108 INITIAL = 0, /* Initial state of a new state block (must be zero). */
109 PARTIAL_ZLIB_HEADER, /* Waiting for a second data byte. */
110 HEADER,
111 UNCOMPRESSED_LEN,
112 UNCOMPRESSED_ILEN,
113 UNCOMPRESSED_DATA,
114 LITERAL_COUNT,
115 DISTANCE_COUNT,
116 CODELEN_COUNT,
117 READ_CODE_LENGTHS,
118 READ_LENGTHS,
119 READ_LENGTHS_16,
120 READ_LENGTHS_17,
121 READ_LENGTHS_18,
122 READ_SYMBOL,
123 READ_LENGTH,
124 READ_DISTANCE,
125 READ_DISTANCE_EXTRA
126 } state;
127  
128 /* in_ptr: Pointer to the next byte to be read from the input buffer. */
129 const unsigned char *in_ptr;
130 /* in_top: Pointer to one byte past the last byte of the input buffer. */
131 const unsigned char *in_top;
132 /* out_base: Pointer to the beginning of the output buffer. */
133 unsigned char *out_base;
134 /* out_ofs: Offset of the next byte to be stored in the output buffer. */
135 unsigned long out_ofs;
136 /* out_size: Total number of bytes in the output buffer. */
137 unsigned long out_size;
138  
139 /* bit_accum: Bit accumulator. */
140 unsigned long bit_accum;
141 /* num_bits: Number of valid bits in accumulator. */
142 unsigned char num_bits;
143 /* final: Nonzero to indicate that the current block is the last one. */
144 unsigned char final;
145  
146 /* first_byte: First byte read from the input stream. Used to detect
147 * an RFC 1950 (zlib) header when the input data is passed in one byte
148 * at a time. Only valid when state == PARTIAL_ZLIB_HEADER. */
149 unsigned char first_byte;
150  
151 /* block_type: Compressed block type. */
152 unsigned char block_type;
153 /* counter: Generic counter. */
154 unsigned int counter;
155 /* symbol: Symbol corresponding to the code currently being processed. */
156 unsigned int symbol;
157 /* last_value: Last value read for length/distance table construction. */
158 unsigned int last_value;
159 /* repeat_length: Length of a repeated string. */
160 unsigned int repeat_length;
161  
162 /* len: Length of an uncompressed block. */
163 unsigned int len;
164 /* ilen: Inverted length of an uncompressed block. */
165 unsigned int ilen;
166 /* nread: Number of bytes copied from an uncompressed block. */
167 unsigned int nread;
168  
169 /* literal_table: Code-to-symbol conversion table for the alphabet used
170 * for literals and length values. Elements 0 and 1 correspond to a
171 * one-bit code of 0 or 1, respectively; other elements are linked
172 * (directly or indirectly) from these to represent the Huffman tree.
173 * The value of each element is:
174 * - for terminal codes, the symbol corresponding to the code (a
175 * nonnegative value);
176 * - for nonterminal codes, the one's complement of the array index
177 * corresponding to the code with a zero appended (the following
178 * array element corresponds to the code with a one appended).
179 * For an alphabet of N symbols, a Huffman tree will have N-1 non-leaf
180 * nodes (including the root node, which is not represented in the
181 * array). In the case of the literal/length alphabet, there are
182 * normally 286 symbols; however, the default (static) Huffman table
183 * uses a 288-symbol alphabet with two unused symbols, so we reserve
184 * enough space for that alphabet. */
185 short literal_table[288*2-2];
186 /* distance_table: Code-to-symbol conversion table for the alphabet
187 * used for distances. This alphabet consists of 32 symbols, 2 of
188 * which are unused. */
189 short distance_table[32*2-2];
190 /* literal_count: Number of literal codes in the Huffman table (HLIT in
191 * RFC 1951). */
192 unsigned int literal_count;
193 /* distance_count: Number of distance codes in the Huffman table (HDIST
194 * in RFC 1951). */
195 unsigned int distance_count;
196 /* codelen_count: Number of code length codes in the Huffman table used
197 * for decompressing the main Huffman tables (HCLEN in RFC 1951). */
198 unsigned int codelen_count;
199 /* codelen_table: Code-to-symbol conversion table for the alphabet used
200 * for code lengths. */
201 short codelen_table[19*2-2];
202 /* literal_len, distance_len, codelen_len: Code length of the code for
203 * each symbol in each alphabet. */
204 unsigned char literal_len[288], distance_len[32], codelen_len[19];
205  
206 /* function called to set a byte in the output buffer */
207 void (*set_out_base)(void *, unsigned long, unsigned char);
208 /* function called to get a byte from the output buffer */
209 unsigned char (*get_out_base)(void *, unsigned long);
210 } DecompressionState;
211  
212 /* Local function declarations. */
213 static int tinflate_block(DecompressionState *state);
214 static int gen_huffman_table(unsigned int symbols,
215 const unsigned char *lengths,
216 int allow_no_symbols,
217 short *table);
218  
219 /**
220 * tinflate_block: Decompress a single block of data compressed with the
221 * "deflate" algorithm.
222 *
223 * Parameters:
224 * state: Decompression state buffer.
225 * Return value:
226 * Zero on success, an unspecified positive value if the end of the
227 * input data is reached before decompression of the block is complete,
228 * or an unspecified negative value if an error other than reaching
229 * the end of the input data occurs. (A full output buffer is not
230 * considered an error.)
231 * Preconditions:
232 * state != NULL
233 */
234 inline static int
235 tinflate_block(DecompressionState *state)
236 {
237 /* in_ptr, in_top, out_base, out_ofs, out_top, bit_accum, num_bits:
238 * Local copies of state variables, to aid compiler optimization. */
239 const unsigned char *in_ptr = state->in_ptr;
240 const unsigned char *in_top = state->in_top;
241 unsigned char *out_base = state->out_base;
242 unsigned long out_ofs = state->out_ofs;
243 unsigned long out_size = state->out_size;
244 unsigned long bit_accum = state->bit_accum;
245 unsigned int num_bits = state->num_bits;
246  
247 /*-------------------------------------------------------------------*/
248  
249 /* The GETBITS macro retrieves the specified number of bits (n) from
250 * the block, returning from the function if no more data is available,
251 * and stores the value in the given variable (var). The number of
252 * bits to retrieve (n) must be no greater than 25. */
253  
254 #define GETBITS(n,var) \
255 do { \
256 const unsigned int __n = (n); /* Avoid multiple evaluations. */ \
257 while (num_bits < __n) { \
258 if (in_ptr >= in_top) { \
259 goto out_of_data; \
260 } \
261 bit_accum |= ((unsigned long) *in_ptr) << num_bits; \
262 num_bits += 8; \
263 in_ptr++; \
264 } \
265 var = bit_accum & ((1UL << __n) - 1); \
266 bit_accum >>= __n; \
267 num_bits -= __n; \
268 } while (0)
269  
270 /* The GETHUFF macro retrieves enough bits from the block to form a
271 * Huffman code according to the given Huffman table (table), storing
272 * the corresponding symbol into the given variable (var). */
273 #define GETHUFF(var,table) \
274 do { \
275 unsigned int bits_used = 0; \
276 unsigned int index = 0; \
277 for (;;) { \
278 if (num_bits <= bits_used) { \
279 if (in_ptr >= in_top) { \
280 goto out_of_data; \
281 } \
282 bit_accum |= (unsigned long) *in_ptr << num_bits; \
283 num_bits += 8; \
284 in_ptr++; \
285 } \
286 index += (bit_accum >> bits_used) & 1; \
287 bits_used++; \
288 if ((table)[index] >= 0) { \
289 break; \
290 } \
291 index = ~(table)[index]; \
292 } \
293 bit_accum >>= bits_used; \
294 num_bits -= bits_used; \
295 var = (table)[index]; \
296 } while (0)
297  
298 /*-------------------------------------------------------------------*/
299  
300 /**** If continuing processing from an interrupted block, jump to ****
301 **** the appropriate location. ****/
302  
303 #define CHECK_STATE(s) case s: goto state_##s
304 switch (state->state) {
305 CHECK_STATE(HEADER);
306 CHECK_STATE(UNCOMPRESSED_LEN);
307 CHECK_STATE(UNCOMPRESSED_ILEN);
308 CHECK_STATE(UNCOMPRESSED_DATA);
309 CHECK_STATE(LITERAL_COUNT);
310 CHECK_STATE(DISTANCE_COUNT);
311 CHECK_STATE(CODELEN_COUNT);
312 CHECK_STATE(READ_CODE_LENGTHS);
313 CHECK_STATE(READ_LENGTHS);
314 CHECK_STATE(READ_LENGTHS_16);
315 CHECK_STATE(READ_LENGTHS_17);
316 CHECK_STATE(READ_LENGTHS_18);
317 CHECK_STATE(READ_SYMBOL);
318 CHECK_STATE(READ_LENGTH);
319 CHECK_STATE(READ_DISTANCE);
320 CHECK_STATE(READ_DISTANCE_EXTRA);
321 case INITIAL:
322 case PARTIAL_ZLIB_HEADER:
323 /* Both of these are impossible, since tinflate_partial() handles
324 * them on its own. We include them here to avoid triggering a
325 * compiler warning due to missing enumeration cases. */
326 /* Empty statement to avoid syntax errors. */ ;
327 }
328 /* The state value is invalid, so return an error. */
329 return -1;
330 #undef CHECK_STATE
331  
332 /**** Process the block header. If the block is not a compressed ****
333 **** block, process it and return from the function. ****/
334  
335 /* Retrieve the block header. */
336 state_HEADER:
337 GETBITS(3, state->block_type);
338 state->final = state->block_type & 1;
339 state->block_type >>= 1;
340  
341 /* Check for blocks with an invalid block code. */
342 if (state->block_type == 3) {
343 goto error_return;
344 }
345  
346 /* Check for uncompressed blocks, and just copy them to the output
347 * buffer. */
348 if (state->block_type == 0) {
349 num_bits = 0; /* Skip remaining bits in the previous byte. */
350 state->state = UNCOMPRESSED_LEN;
351 state_UNCOMPRESSED_LEN:
352 GETBITS(16, state->len);
353 state->state = UNCOMPRESSED_ILEN;
354 state_UNCOMPRESSED_ILEN:
355 GETBITS(16, state->ilen);
356 if (state->ilen != (~state->len & 0xFFFF)) {
357 /* Length values don't match, so the stream must be corrupted. */
358 goto error_return;
359 }
360 /* Copy bytes to the output buffer. */
361 state->nread = 0;
362 state->state = UNCOMPRESSED_DATA;
363 state_UNCOMPRESSED_DATA:
364 while (state->nread < state->len) {
365 if (in_ptr >= in_top) {
366 goto out_of_data;
367 }
368 //PUTBYTE(*in_ptr++);
369 if (out_ofs < out_size) {
370 state->set_out_base(out_base, out_ofs, *in_ptr++);
371 }
372 out_ofs++;
373 state->nread++;
374 }
375 /* Update the state buffer and return success. */
376 state->in_ptr = in_ptr;
377 state->out_ofs = out_ofs;
378 /* This "& 0xFFFFFFFFUL" is a no-op on systems where the "long"
379 * type is 32 bits wide; but where it is wider, the ~ operation
380 * will set the high bits of the variable, so we need to clear
381 * them out. */
382 state->bit_accum = bit_accum;
383 state->num_bits = num_bits;
384 state->state = HEADER;
385 return 0;
386 } /* if (state->block_type == 0) */
387  
388 /**** Initialize the decoding tables. ****/
389  
390 if (state->block_type == 2) { /* Dynamic tables. */
391  
392 /* codelen_order: Order of code lengths in the block header for the
393 * code length alphabet. */
394 static const unsigned char codelen_order[19] = {
395 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
396 };
397  
398 /* Retrieve the three code counts from the block header. */
399 state->state = LITERAL_COUNT;
400 state_LITERAL_COUNT:
401 GETBITS(5, state->literal_count);
402 state->literal_count += 257;
403 state->state = DISTANCE_COUNT;
404 state_DISTANCE_COUNT:
405 GETBITS(5, state->distance_count);
406 state->distance_count += 1;
407 state->state = CODELEN_COUNT;
408 state_CODELEN_COUNT:
409 GETBITS(4, state->codelen_count);
410 state->codelen_count += 4;
411  
412 /* Retrieve the specified number of code lengths for the code
413 * length alphabet, clearing the rest to zero. */
414 state->counter = 0;
415 state->state = READ_CODE_LENGTHS;
416 state_READ_CODE_LENGTHS:
417 while (state->counter < state->codelen_count) {
418 GETBITS(3, state->codelen_len[codelen_order[state->counter]]);
419 state->counter++;
420 }
421 for (; state->counter < 19; state->counter++) {
422 state->codelen_len[codelen_order[state->counter]] = 0;
423 }
424  
425 /* Generate the code length Huffman table. */
426 if (!gen_huffman_table(19, state->codelen_len, 0,
427 state->codelen_table)) {
428 goto error_return;
429 }
430  
431 /* Read code lengths for the literal/length and distance alphabets. */
432 {
433 /* repeat_count: Number of times remaining to repeat value.
434 * (We cannot run out of data while repeating values, so there
435 * is no need to store this counter in the state buffer.) */
436 unsigned int repeat_count;
437  
438 state->last_value = 0;
439 state->counter = 0;
440 state->state = READ_LENGTHS;
441 state_READ_LENGTHS:
442 repeat_count = 0;
443 while (state->counter < state->literal_count + state->distance_count) {
444 if (repeat_count == 0) {
445 /* Get the next value and/or repeat count from the
446 * bitstream. */
447 GETHUFF(state->symbol, state->codelen_table);
448 if (state->symbol < 16) {
449 /* Literal bit length. */
450 state->last_value = state->symbol;
451 repeat_count = 1;
452 } else if (state->symbol == 16) {
453 /* Repeat last bit length 3-6 times. */
454 state->state = READ_LENGTHS_16;
455 state_READ_LENGTHS_16:
456 GETBITS(2, repeat_count);
457 repeat_count += 3;
458 } else if (state->symbol == 17) {
459 /* Repeat "0" 3-10 times. */
460 state->last_value = 0;
461 state->state = READ_LENGTHS_17;
462 state_READ_LENGTHS_17:
463 GETBITS(3, repeat_count);
464 repeat_count += 3;
465 } else { /* symbol == 18 */
466 /* Repeat "0" 11-138 times. */
467 state->last_value = 0;
468 state->state = READ_LENGTHS_18;
469 state_READ_LENGTHS_18:
470 GETBITS(7, repeat_count);
471 repeat_count += 11;
472 }
473 } /* if (repeat_count == 0) */
474 if (state->counter < state->literal_count) {
475 state->literal_len[state->counter] = state->last_value;
476 } else {
477 state->distance_len[state->counter - state->literal_count]
478 = state->last_value;
479 }
480 state->counter++;
481 repeat_count--;
482 state->state = READ_LENGTHS;
483 } /* while (counter < literal_count + distance_count) */
484 }
485  
486 /* Generate the literal/length and distance Huffman tables. The
487 * distance table is allowed to have no symbols (as may happen if
488 * the data is all literals). */
489 if (!gen_huffman_table(state->literal_count, state->literal_len, 0,
490 state->literal_table)
491 || !gen_huffman_table(state->distance_count, state->distance_len, 1,
492 state->distance_table)) {
493 goto error_return;
494 }
495  
496 } else { /* Static tables. */
497  
498 int next_free = 2; /* Next free index. */
499 int i;
500  
501 /* All 1-6 bit codes are nonterminal. */
502 for (i = 0; i < 0x7E; i++) {
503 state->literal_table[i] = ~next_free;
504 next_free += 2;
505 }
506 /* 7-bit codes 000 0000 through 001 0111 correspond to symbols 256
507 * through 279. */
508 for (; i < 0x96; i++) {
509 state->literal_table[i] = (short)i + (256 - 0x7E);
510 }
511 /* All other 7-bit codes are nonterminal. */
512 for (; i < 0xFE; i++) {
513 state->literal_table[i] = ~next_free;
514 next_free += 2;
515 }
516 /* 8-bit codes 0011 0000 through 1011 1111 correspond to symbols 0
517 * through 143. */
518 for (; i < 0x18E; i++) {
519 state->literal_table[i] = (short)i + (0 - 0xFE);
520 }
521 /* 8-bit codes 1100 0000 through 1100 0111 correspond to symbols
522 * 280 through 287. (Symbols 286 and 287 are not used in the
523 * compressed data itself, but they take part in the construction
524 * of the code table.) */
525 for (; i < 0x196; i++) {
526 state->literal_table[i] = (short)i + (280 - 0x18E);
527 }
528 /* 8-bit codes 1100 1000 through 1111 1111 are nonterminal. */
529 for (; i < 0x1CE; i++) {
530 state->literal_table[i] = ~next_free;
531 next_free += 2;
532 }
533 /* 9-bit codes 1 1001 0000 through 1 1111 1111 correspond to
534 * symbols 144 through 255. */
535 for (; i < 0x23E; i++) {
536 state->literal_table[i] = (short)i + (144 - 0x1CE);
537 }
538  
539 /* Distance codes are represented as 5-bit integers for static
540 * tables; we treat them as Huffman codes, and set up a table here
541 * so that they can be processed in the same manner as for dynamic
542 * Huffman coding. */
543 for (i = 0; i < 0x1E; i++) {
544 state->distance_table[i] = ~(i*2+2);
545 }
546 for (i = 0x1E; i < 0x3E; i++) {
547 state->distance_table[i] = i - 0x1E;
548 }
549  
550 } /* if (dynamic vs. static codes) */
551  
552 /**** Read and process codes from the compressed stream until we ****
553 **** find an end-of-stream symbol (256). If we run out of data, ****
554 **** the GETHUFF or GETBITS macro will exit the function, so we ****
555 **** do not need a separate check for an out-of-data condition. ****/
556  
557 for (;;) {
558  
559 /* distance: The distance backward to the beginning of a repeated
560 * string. */
561 unsigned int distance;
562  
563  
564 /* Ensure that the output offset has not rolled over to a negative
565 * value; if it has, return an error. (The "out_ofs" state field
566 * is unsigned, so a rollover will not cause any improper memory
567 * accesses, but this check ensures that (1) a caller who treats
568 * the value as signed will not suffer negative rollover, and (2)
569 * processing the next symbol will not cause the unsigned offset
570 * value to roll over to zero. The interface routines also treat
571 * a potential negative rollover as an error, so this check will
572 * not generate any spurious errors.) */
573 if ((long)out_ofs < 0) {
574 goto error_return;
575 }
576  
577 state->state = READ_SYMBOL;
578 state_READ_SYMBOL:
579 /* Read a compressed symbol from the block. */
580 GETHUFF(state->symbol, state->literal_table);
581  
582 /* If the symbol is a literal, add it to the buffer and continue
583 * with the next code. */
584 if (state->symbol < 256) {
585 //PUTBYTE(state->symbol);
586 if (out_ofs < out_size) {
587 state->set_out_base(out_base, out_ofs, state->symbol);
588 }
589 out_ofs++;
590 continue;
591 }
592  
593 /* If the symbol indicates end-of-block, exit the decompression
594 * loop. */
595 if (state->symbol == 256) {
596 break;
597 }
598  
599 /* The symbol must indicate a repeated string length, so determine
600 * the length, reading extra bits from the stream as necessary. */
601 if (state->symbol <= 264) {
602 state->repeat_length = (state->symbol-257) + 3;
603 } else if (state->symbol <= 284) {
604 state->state = READ_LENGTH;
605 state_READ_LENGTH:
606 /* Empty statement to avoid syntax errors. */ ;
607 {
608 const unsigned int length_bits = (state->symbol-261) / 4;
609 GETBITS(length_bits, state->repeat_length);
610 state->repeat_length +=
611 3 + ((4 + ((state->symbol-265) & 3)) << length_bits);
612 }
613 } else if (state->symbol == 285) {
614 state->repeat_length = 258;
615 } else {
616 /* Invalid symbol. */
617 goto error_return;
618 }
619  
620 /* Read the distance symbol from the bitstream and determine the
621 * backward distance to the string. */
622 state->state = READ_DISTANCE;
623 state_READ_DISTANCE:
624 GETHUFF(state->symbol, state->distance_table);
625 if (state->symbol <= 3) {
626 distance = state->symbol + 1;
627 } else if (state->symbol <= 29) {
628 state->state = READ_DISTANCE_EXTRA;
629 state_READ_DISTANCE_EXTRA:
630 /* Empty statement to avoid syntax errors. */ ;
631 {
632 const unsigned int distance_bits = (state->symbol-2) / 2;
633 GETBITS(distance_bits, distance);
634 distance += 1 + ((2 + (state->symbol & 1)) << distance_bits);
635 }
636 } else {
637 /* Invalid symbol. */
638 goto error_return;
639 }
640  
641 /* Ensure that the distance does not exceed the amount of data in
642 * the output buffer. If it does, return an error. */
643 if (out_ofs < distance) {
644 goto error_return;
645 }
646  
647 /* Copy bytes from the input buffer to the output buffer. Since
648 * the output pointer advances with each byte written, we can
649 * simply use a constant offset (the value of "distance") from the
650 * output pointer to retrieve the byte to copy. If the output
651 * buffer becomes full during the copy, the CRC value will not be
652 * updated with the remaining bytes (as the source offset could
653 * subsequently run past the end of the output buffer as well), but
654 * since the CRC is explicitly undefined in this case, this is not
655 * a problem. */
656 {
657 unsigned int repeat_length = state->repeat_length;
658 unsigned int overflow = 0;
659 if (out_ofs + repeat_length > out_size) {
660 if (out_ofs > out_size) {
661 overflow = repeat_length;
662 } else {
663 overflow = (out_ofs - out_size) + repeat_length;
664 }
665 repeat_length -= overflow;
666 }
667 for (; repeat_length > 0; repeat_length--) {
668 //PUTBYTE_SAFE(out_base[out_ofs - distance]);
669 state->set_out_base(out_base, out_ofs,
670 state->get_out_base(out_base, out_ofs - distance));
671 out_ofs++;
672 }
673 out_ofs += overflow;
674 }
675  
676 } /* End of decompression loop. */
677  
678 /**** Update the state buffer with our local state variables, ****
679 **** and return success. ****/
680  
681 state->in_ptr = in_ptr;
682 state->out_ofs = out_ofs;
683 state->bit_accum = bit_accum;
684 state->num_bits = num_bits;
685 state->state = HEADER;
686 return 0;
687  
688 /*-------------------------------------------------------------------*/
689  
690 /**** Update the state buffer with our local state variables, ****
691 **** and return an out-of-data result. ****/
692  
693 out_of_data:
694 state->in_ptr = in_ptr;
695 state->out_ofs = out_ofs;
696 state->bit_accum = bit_accum;
697 state->num_bits = num_bits;
698 return 1;
699  
700 /**** Update the state buffer with our local state variables, ****
701 **** and return an error result. ****/
702  
703 error_return:
704 state->in_ptr = in_ptr;
705 state->out_ofs = out_ofs;
706 state->bit_accum = bit_accum;
707 state->num_bits = num_bits;
708 return -1;
709 }
710  
711 /*************************************************************************/
712  
713 /**
714 * gen_huffman_table: Generate a Huffman table from a set of code lengths,
715 * using the algorithm described in RFC 1951. The table format is as
716 * described for the literal_table[] array in tinflate_block().
717 *
718 * Parameters:
719 * symbols: Number of symbols in the alphabet.
720 * lengths: Bit lengths of the codes for each symbol
721 * (0 = symbol not used).
722 * allow_no_symbols: True (nonzero) if a table with no symbols (i.e.,
723 * no nonzero code lengths) should be allowed.
724 * table: Array into which the Huffman table will be stored.
725 * Return value:
726 * Nonzero on success, zero on failure (erroneous data).
727 * Preconditions:
728 * symbols > 0 && symbols <= 288
729 * lengths != NULL
730 * table != NULL
731 * Notes:
732 * lengths[] must contain the number of elements specified by
733 * "symbols"; table[] must have enough room for symbols*2-2 elements,
734 * or for 2 elements if "symbols" is 1; and all code lengths must be
735 * no greater than 15.
736 */
737 static int
738 gen_huffman_table(unsigned int symbols,
739 const unsigned char *lengths,
740 int allow_no_symbols,
741 short *table)
742 {
743 /* length_count: Count of symbols with each code length. */
744 unsigned short length_count[16];
745 /* total_count: Count of all symbols with non-zero lengths. */
746 unsigned short total_count;
747 /* first_code: First code value to be used for each code length. */
748 unsigned short first_code[16];
749 /* index: Current table index. This is guaranteed (modulo hardware
750 * errors or memory corruption while this routine is running) to never
751 * exceed symbols*2-2 entries, so its value is not bound-checked below.
752 * This can be seen by simple induction: Given a code alphabet of N
753 * symbols (N >= 2), adding a new symbol N+1 involves taking a
754 * previously terminal code and splitting it into two codes, one with
755 * a 0 appended and the other with a 1 appended. This is equivalent
756 * to converting the corresponding leaf node of the Huffman tree to
757 * an internal node and adding two new leaf nodes as children, thus
758 * increasing the total node count by 2. Since the table[] array
759 * corresponds exactly to the Huffman tree, and index is incremented
760 * exactly once for each node, index can never exceed the total number
761 * of nodes in the tree (2N-2 for N symbols), which is also the
762 * required length of the array. */
763 unsigned int index;
764  
765 unsigned int i;
766  
767 /* Count the number of symbols that have each code length. If an
768 * invalid code length is found, abort. */
769 for (i = 0; i < 16; i++) {
770 length_count[i] = 0;
771 }
772 for (i = 0; i < symbols; i++) {
773 /* We don't count codes of length 0 since they don't participate
774 * in forming the tree. (It's also convenient to have
775 * length_count[0] == 0 for the code range calculation below.) */
776 if (lengths[i] > 0) {
777 length_count[lengths[i]]++;
778 }
779 }
780  
781 /* Check for a degenerate table of zero or one symbol. */
782 total_count = 0;
783 for (i = 1; i < 16; i++) {
784 total_count += length_count[i];
785 }
786 if (total_count == 0) {
787 return allow_no_symbols;
788 } else if (total_count == 1) {
789 for (i = 0; i < symbols; i++) {
790 if (lengths[i] != 0) {
791 table[0] = table[1] = i;
792 }
793 }
794 return 1;
795 }
796  
797 /* Determine the first code value for each code length, and make sure
798 * the code space is completely filled as required. Note that we rely
799 * on length_count[0] being left at 0 above. */
800 first_code[0] = 0;
801 for (i = 1; i < 16; i++) {
802 first_code[i] = (first_code[i-1] + length_count[i-1]) << 1;
803 if (first_code[i] + length_count[i] > 1U<<i) {
804 /* Too many symbols of this code length -- we can't form a
805 * valid Huffman tree. */
806 return 0;
807 }
808 }
809 if (first_code[15] + length_count[15] != 1U<<15) {
810 /* The Huffman tree is incomplete and thus invalid. */
811 return 0;
812 }
813  
814 /* Create the Huffman table, assigning codes to symbols sequentially
815 * within each code length. If the code value or table overflows
816 * (presumably due to invalid data), abort. */
817 index = 0;
818 for (i = 1; i < 16; i++) {
819 /* code_limit: Maximum code value for this code length, plus one. */
820 unsigned int code_limit = 1U << i;
821 /* next_code: First free code after all symbols with this code
822 * length have been assigned. */
823 unsigned int next_code = first_code[i] + length_count[i];
824 /* next_index: First array index for the next higher code length. */
825 unsigned int next_index = index + (code_limit - first_code[i]);
826 unsigned int j;
827  
828 /* Fill in any symbols of this code length. */
829 for (j = 0; j < symbols; j++) {
830 if (lengths[j] == i) {
831 table[index++] = j;
832 }
833 }
834  
835 /* Fill in remaining (internal) nodes for this length. */
836 for (j = next_code; j < code_limit; j++) {
837 table[index++] = ~next_index;
838 next_index += 2;
839 }
840 } /* for each code length */
841  
842 /* Return success. */
843 return 1;
844 }
845  
846 /**
847 * tinflate_partial: Decompress a portion of a stream of data compressed
848 * with the "deflate" algorithm.
849 *
850 * Parameters:
851 * compressed_data: Pointer to the portion of the compressed data to
852 * process.
853 * compressed_size: Number of bytes of compressed data.
854 * output_buffer: Pointer to the buffer to receive uncompressed data.
855 * output_size: Size of the output buffer, in bytes.
856 * size_ret: Pointer to variable to receive the size of the
857 * uncompressed data, or NULL if the size is not
858 * needed.
859 * state_buffer: Pointer to a buffer to hold state information,
860 * which must be zeroed before the first call for
861 * the stream.
862 * state_buffer_size: Size of the state buffer, in bytes. Must be no
863 * less than the value returned by
864 * tinflate_state_size().
865 * Return value:
866 * Zero when the data has been completely decompressed; an unspecified
867 * positive value if the end of the input data is reached before
868 * decompression is complete; or an unspecified negative value if an
869 * error occurs. (A full output buffer is not considered an error.)
870 */
871 int
872 tinflate_partial(const void *compressed_data, long compressed_size,
873 void *output_buffer, long output_size,
874 unsigned long *size_ret,
875 void *state_buffer, long state_buffer_size,
876 void (*set_out_base)(void *, unsigned long, unsigned char),
877 unsigned char (*get_out_base)(void *, unsigned long))
878 {
879 /* state: Decompression state buffer, cast to the structured type. */
880 DecompressionState *state = (DecompressionState *)state_buffer;
881  
882 /*-------------------------------------------------------------------*/
883  
884 /**** Insert data pointers into decompression state block. ****/
885  
886 state->in_ptr = (const unsigned char *)compressed_data;
887 state->in_top = state->in_ptr + compressed_size;
888 state->out_base = output_buffer;
889 state->out_size = output_size;
890 state->set_out_base = set_out_base;
891 state->get_out_base = get_out_base;
892  
893 /**** If this is the first call, check for a zlib header, then ****
894 **** initialize the processing state. ****/
895  
896 if (state->state == INITIAL || state->state == PARTIAL_ZLIB_HEADER) {
897 /*
898 * A zlib header is a big-endian 16-bit integer, composed of the
899 * following fields:
900 * 0xF000: Window size (log2(maximum_distance), 8..15) minus 8
901 * 0x0F00: Compression method (always 8)
902 * 0x00C0: Compression level
903 * 0x0020: Custom dictionary flag
904 * 0x001F: Check bits (set so the header is a multiple of 31)
905 */
906 unsigned int zlib_header;
907 if (compressed_size == 0) {
908 /* We didn't get any data at all, so there's no change in state. */
909 return 1;
910 }
911 if (state->state == INITIAL && compressed_size == 1) {
912 /* Save the single byte in the state block for next time. */
913 state->first_byte = state->in_ptr[0];
914 state->state = PARTIAL_ZLIB_HEADER;
915 return 1;
916 }
917 if (state->state == PARTIAL_ZLIB_HEADER) {
918 zlib_header = state->first_byte<<8 | state->in_ptr[0];
919 } else {
920 zlib_header = state->in_ptr[0]<<8 | state->in_ptr[1];
921 }
922 if ((zlib_header & 0x8F00) == 0x0800 && zlib_header % 31 == 0) {
923 if (zlib_header & 0x0020) {
924 /* This library does not support custom dictionaries. */
925 return -1;
926 }
927 state->in_ptr += (state->state == PARTIAL_ZLIB_HEADER ? 1 : 2);
928 } else if (state->state == PARTIAL_ZLIB_HEADER) {
929 /* Return the first byte to the bitstream so we can process it
930 * as part of the compressed data. */
931 state->bit_accum = state->first_byte;
932 state->num_bits = 8;
933 }
934 state->state = HEADER;
935 }
936  
937 /**** Decompress blocks until either the end of the compressed ****
938 **** data is reached, an error occurs, or a block with the ****
939 **** "final" bit is set. ****/
940  
941 do {
942 int res = tinflate_block(state);
943 if (res != 0) {
944 /* This will catch the out-of-data case, so we don't need to
945 * check for out-of-data separately. */
946 return res;
947 }
948 /* Ensure that the total output size has not rolled over to a
949 * negative value; if it has, return an error. */
950 if ((long)state->out_ofs < 0) {
951 return -1;
952 }
953 /* Check for end-of-stream. (Note that this flag will be set at
954 * the beginning of processing the final block, but since we
955 * already checked for end-of-block, we do not need to do so again
956 * here.) */
957 } while (!state->final);
958  
959 /**** Return the total decompressed size and CRC (if requested). ****/
960  
961 if (size_ret) {
962 *size_ret = state->out_ofs;
963 }
964 return 0;
965 }
966  
967 /* End of tinflate.c */
968  
969  
970 void
971 wlc_ucode_write_compressed(struct wlc_hw_info *wlc_hw, const int ucode[], const unsigned int nbytes)
972 {
973 /* state: Decompression state buffer to pass to tinflate_block(). */
974 DecompressionState state;
975  
976 /**** Clear decompression state buffer. ****/
977 state.state = INITIAL;
978 state.out_ofs = 0;
979 state.bit_accum = 0;
980 state.num_bits = 0;
981 state.final = 0;
982 /* No other fields need to be cleared. */
983  
984 /**** Call tinflate_partial() to do the actual decompression. ****/
985 tinflate_partial(ucode_compressed_bin, ucode_compressed_bin_len,
986 wlc_hw, 100000, 0, &state, sizeof(state), tinflate_write_objmem, tinflate_read_objmem);
987 }
988  
989 void
990 wlc_ucode_write_compressed_args(struct wlc_hw_info *wlc_hw, const int ucode[], const unsigned int nbytes)
991 {
992 /* state: Decompression state buffer to pass to tinflate_block(). */
993 DecompressionState state;
994  
995 /**** Clear decompression state buffer. ****/
996 state.state = INITIAL;
997 state.out_ofs = 0;
998 state.bit_accum = 0;
999 state.num_bits = 0;
1000 state.final = 0;
1001 /* No other fields need to be cleared. */
1002  
1003 /**** Call tinflate_partial() to do the actual decompression. ****/
1004 tinflate_partial(ucode, nbytes,
1005 wlc_hw, 100000, 0, &state, sizeof(state), tinflate_write_objmem, tinflate_read_objmem);
1006 }
1007  
1008 void
1009 wlc_ucodex_write_compressed_args(struct wlc_hw_info *wlc_hw, const int ucodex[], const unsigned int nbytes)
1010 {
1011 /* state: Decompression state buffer to pass to tinflate_block(). */
1012 DecompressionState state;
1013  
1014 /**** Clear decompression state buffer. ****/
1015 state.state = INITIAL;
1016 state.out_ofs = 0;
1017 state.bit_accum = 0;
1018 state.num_bits = 0;
1019 state.final = 0;
1020 /* No other fields need to be cleared. */
1021  
1022 /**** Call tinflate_partial() to do the actual decompression. ****/
1023 tinflate_partial(ucodex, nbytes,
1024 wlc_hw, 100000, 0, &state, sizeof(state), tinflate_write_objmemx, tinflate_read_objmemx);
1025 }