]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /********************************************************************** |
2 | Copyright(c) 2011-2016 Intel Corporation All rights reserved. | |
3 | ||
4 | Redistribution and use in source and binary forms, with or without | |
5 | modification, are permitted provided that the following conditions | |
6 | are met: | |
7 | * Redistributions of source code must retain the above copyright | |
8 | notice, this list of conditions and the following disclaimer. | |
9 | * Redistributions in binary form must reproduce the above copyright | |
10 | notice, this list of conditions and the following disclaimer in | |
11 | the documentation and/or other materials provided with the | |
12 | distribution. | |
13 | * Neither the name of Intel Corporation nor the names of its | |
14 | contributors may be used to endorse or promote products derived | |
15 | from this software without specific prior written permission. | |
16 | ||
17 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
18 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
19 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
20 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
21 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
22 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
23 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
24 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
25 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
26 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
27 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
28 | **********************************************************************/ | |
29 | ||
30 | #include <immintrin.h> | |
31 | #include <stdint.h> | |
32 | #include <string.h> | |
33 | #include <assert.h> | |
34 | #include "igzip_lib.h" | |
35 | #include "huff_codes.h" | |
36 | #include "huffman.h" | |
37 | ||
38 | #define LENGTH_BITS 5 | |
39 | ||
40 | /* The order code length codes are written in the dynamic code header. This is | |
41 | * defined in RFC 1951 page 13 */ | |
42 | static const uint8_t code_length_code_order[] = | |
43 | { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; | |
44 | ||
45 | int heap_push(struct huff_tree element, struct histheap *heap) | |
46 | { | |
47 | uint16_t index; | |
48 | uint16_t parent; | |
49 | assert(heap->size < MAX_HISTHEAP_SIZE); | |
50 | index = heap->size; | |
51 | heap->size += 1; | |
52 | parent = (index - 1) / 2; | |
53 | while ((index != 0) && (heap->tree[parent].frequency > element.frequency)) { | |
54 | heap->tree[index] = heap->tree[parent]; | |
55 | index = parent; | |
56 | parent = (index - 1) / 2; | |
57 | ||
58 | } | |
59 | heap->tree[index] = element; | |
60 | ||
61 | return index; | |
62 | } | |
63 | ||
64 | struct huff_tree heap_pop(struct histheap *heap) | |
65 | { | |
66 | struct huff_tree root, temp; | |
67 | uint16_t index = 0; | |
68 | uint16_t child = 1; | |
69 | assert(heap->size > 0); | |
70 | root = heap->tree[index]; | |
71 | heap->size--; | |
72 | heap->tree[index] = heap->tree[heap->size]; | |
73 | ||
74 | while (child + 1 < heap->size) { | |
75 | if (heap->tree[child].frequency < heap->tree[index].frequency | |
76 | || heap->tree[child + 1].frequency < heap->tree[index].frequency) { | |
77 | if (heap->tree[child].frequency > heap->tree[child + 1].frequency) | |
78 | child += 1; | |
79 | temp = heap->tree[index]; | |
80 | heap->tree[index] = heap->tree[child]; | |
81 | heap->tree[child] = temp; | |
82 | index = child; | |
83 | child = 2 * child + 1; | |
84 | } else { | |
85 | break; | |
86 | } | |
87 | } | |
88 | ||
89 | if (child < heap->size) { | |
90 | if (heap->tree[child].frequency < heap->tree[index].frequency) { | |
91 | temp = heap->tree[index]; | |
92 | heap->tree[index] = heap->tree[child]; | |
93 | heap->tree[child] = temp; | |
94 | } | |
95 | } | |
96 | ||
97 | return root; | |
98 | ||
99 | } | |
100 | ||
101 | struct linked_list_node *pop_from_front(struct linked_list *list) | |
102 | { | |
103 | struct linked_list_node *temp; | |
104 | ||
105 | temp = list->start; | |
106 | if (list->start != NULL) { | |
107 | list->start = list->start->next; | |
108 | if (list->start != NULL) | |
109 | list->start->previous = NULL; | |
110 | else | |
111 | list->end = NULL; | |
112 | list->length -= 1; | |
113 | } | |
114 | return temp; | |
115 | } | |
116 | ||
117 | void append_to_front(struct linked_list *list, struct linked_list_node *new_element) | |
118 | { | |
119 | new_element->next = list->start; | |
120 | new_element->previous = NULL; | |
121 | if (list->start != NULL) | |
122 | list->start->previous = new_element; | |
123 | else | |
124 | list->end = new_element; | |
125 | list->start = new_element; | |
126 | list->length += 1; | |
127 | ||
128 | return; | |
129 | } | |
130 | ||
131 | void append_to_back(struct linked_list *list, struct linked_list_node *new_element) | |
132 | { | |
133 | new_element->previous = list->end; | |
134 | new_element->next = NULL; | |
135 | if (list->end != NULL) | |
136 | list->end->next = new_element; | |
137 | else | |
138 | list->start = new_element; | |
139 | list->end = new_element; | |
140 | list->length += 1; | |
141 | ||
142 | return; | |
143 | } | |
144 | ||
145 | void isal_update_histogram(uint8_t * start_stream, int length, | |
146 | struct isal_huff_histogram *histogram) | |
147 | { | |
148 | uint32_t literal = 0, hash; | |
149 | uint8_t *last_seen[HASH_SIZE]; | |
150 | uint8_t *current, *seen, *end_stream, *next_hash, *end; | |
151 | uint32_t match_length; | |
152 | uint32_t dist; | |
153 | uint64_t *lit_len_histogram = histogram->lit_len_histogram; | |
154 | uint64_t *dist_histogram = histogram->dist_histogram; | |
155 | ||
156 | if (length <= 0) | |
157 | return; | |
158 | ||
159 | end_stream = start_stream + length; | |
160 | memset(last_seen, 0, sizeof(last_seen)); /* Initialize last_seen to be 0. */ | |
161 | for (current = start_stream; current < end_stream - 3; current++) { | |
162 | literal = *(uint32_t *) current; | |
163 | hash = compute_hash(literal) & HASH_MASK; | |
164 | seen = last_seen[hash]; | |
165 | last_seen[hash] = current; | |
166 | dist = current - seen; | |
167 | if (dist < D) { | |
168 | match_length = compare258(seen, current, end_stream - current); | |
169 | if (match_length >= SHORTEST_MATCH) { | |
170 | next_hash = current; | |
171 | #ifdef LIMIT_HASH_UPDATE | |
172 | end = next_hash + 3; | |
173 | #else | |
174 | end = next_hash + match_length; | |
175 | #endif | |
176 | if (end > end_stream - 3) | |
177 | end = end_stream - 3; | |
178 | next_hash++; | |
179 | for (; next_hash < end; next_hash++) { | |
180 | literal = *(uint32_t *) next_hash; | |
181 | hash = compute_hash(literal) & HASH_MASK; | |
182 | last_seen[hash] = next_hash; | |
183 | } | |
184 | ||
185 | dist_histogram[convert_dist_to_dist_sym(dist)] += 1; | |
186 | lit_len_histogram[convert_length_to_len_sym(match_length)] += | |
187 | 1; | |
188 | current += match_length - 1; | |
189 | continue; | |
190 | } | |
191 | } | |
192 | lit_len_histogram[literal & 0xFF] += 1; | |
193 | } | |
194 | literal = literal >> 8; | |
195 | hash = compute_hash(literal) & HASH_MASK; | |
196 | seen = last_seen[hash]; | |
197 | last_seen[hash] = current; | |
198 | dist = current - seen; | |
199 | if (dist < D) { | |
200 | match_length = compare258(seen, current, end_stream - current); | |
201 | if (match_length >= SHORTEST_MATCH) { | |
202 | dist_histogram[convert_dist_to_dist_sym(dist)] += 1; | |
203 | lit_len_histogram[convert_length_to_len_sym(match_length)] += 1; | |
204 | lit_len_histogram[256] += 1; | |
205 | return; | |
206 | } | |
207 | } else | |
208 | lit_len_histogram[literal & 0xFF] += 1; | |
209 | lit_len_histogram[(literal >> 8) & 0xFF] += 1; | |
210 | lit_len_histogram[(literal >> 16) & 0xFF] += 1; | |
211 | lit_len_histogram[256] += 1; | |
212 | return; | |
213 | } | |
214 | ||
215 | uint32_t convert_dist_to_dist_sym(uint32_t dist) | |
216 | { | |
217 | assert(dist <= 32768 && dist > 0); | |
218 | if (dist <= 2) | |
219 | return dist - 1; | |
220 | else if (dist <= 4) | |
221 | return 0 + (dist - 1) / 1; | |
222 | else if (dist <= 8) | |
223 | return 2 + (dist - 1) / 2; | |
224 | else if (dist <= 16) | |
225 | return 4 + (dist - 1) / 4; | |
226 | else if (dist <= 32) | |
227 | return 6 + (dist - 1) / 8; | |
228 | else if (dist <= 64) | |
229 | return 8 + (dist - 1) / 16; | |
230 | else if (dist <= 128) | |
231 | return 10 + (dist - 1) / 32; | |
232 | else if (dist <= 256) | |
233 | return 12 + (dist - 1) / 64; | |
234 | else if (dist <= 512) | |
235 | return 14 + (dist - 1) / 128; | |
236 | else if (dist <= 1024) | |
237 | return 16 + (dist - 1) / 256; | |
238 | else if (dist <= 2048) | |
239 | return 18 + (dist - 1) / 512; | |
240 | else if (dist <= 4096) | |
241 | return 20 + (dist - 1) / 1024; | |
242 | else if (dist <= 8192) | |
243 | return 22 + (dist - 1) / 2048; | |
244 | else if (dist <= 16384) | |
245 | return 24 + (dist - 1) / 4096; | |
246 | else if (dist <= 32768) | |
247 | return 26 + (dist - 1) / 8192; | |
248 | else | |
249 | return ~0; /* ~0 is an invalid distance code */ | |
250 | ||
251 | } | |
252 | ||
253 | uint32_t convert_length_to_len_sym(uint32_t length) | |
254 | { | |
255 | assert(length > 2 && length < 259); | |
256 | ||
257 | /* Based on tables on page 11 in RFC 1951 */ | |
258 | if (length < 11) | |
259 | return 257 + length - 3; | |
260 | else if (length < 19) | |
261 | return 261 + (length - 3) / 2; | |
262 | else if (length < 35) | |
263 | return 265 + (length - 3) / 4; | |
264 | else if (length < 67) | |
265 | return 269 + (length - 3) / 8; | |
266 | else if (length < 131) | |
267 | return 273 + (length - 3) / 16; | |
268 | else if (length < 258) | |
269 | return 277 + (length - 3) / 32; | |
270 | else | |
271 | return 285; | |
272 | } | |
273 | ||
274 | struct huff_tree create_symbol_subset_huff_tree(struct huff_tree *tree_array, | |
275 | uint64_t * histogram, uint32_t size) | |
276 | { | |
277 | /* Assumes there are at least 2 symbols. */ | |
278 | int i; | |
279 | uint32_t node_index; | |
280 | struct huff_tree tree; | |
281 | struct histheap heap; | |
282 | ||
283 | heap.size = 0; | |
284 | ||
285 | tree.right = tree.left = NULL; | |
286 | ||
287 | /* Intitializes heap for construction of the huffman tree */ | |
288 | for (i = 0; i < size; i++) { | |
289 | tree.value = i; | |
290 | tree.frequency = histogram[i]; | |
291 | tree_array[i] = tree; | |
292 | ||
293 | /* If symbol does not appear (has frequency 0), ignore it. */ | |
294 | if (tree_array[i].frequency != 0) | |
295 | heap_push(tree, &heap); | |
296 | } | |
297 | ||
298 | node_index = size; | |
299 | ||
300 | /* Construct the huffman tree */ | |
301 | while (heap.size > 1) { | |
302 | ||
303 | tree = heap_pop(&heap); | |
304 | tree_array[node_index].frequency = tree.frequency; | |
305 | tree_array[node_index].left = &tree_array[tree.value]; | |
306 | ||
307 | tree = heap_pop(&heap); | |
308 | tree_array[node_index].frequency += tree.frequency; | |
309 | tree_array[node_index].right = &tree_array[tree.value]; | |
310 | ||
311 | tree_array[node_index].value = node_index; | |
312 | heap_push(tree_array[node_index], &heap); | |
313 | ||
314 | node_index += 1; | |
315 | } | |
316 | ||
317 | return heap_pop(&heap); | |
318 | } | |
319 | ||
320 | struct huff_tree create_huff_tree(struct huff_tree *tree_array, uint64_t * histogram, | |
321 | uint32_t size) | |
322 | { | |
323 | int i; | |
324 | uint32_t node_index; | |
325 | struct huff_tree tree; | |
326 | struct histheap heap; | |
327 | ||
328 | heap.size = 0; | |
329 | ||
330 | tree.right = tree.left = NULL; | |
331 | ||
332 | /* Intitializes heap for construction of the huffman tree */ | |
333 | for (i = 0; i < size; i++) { | |
334 | tree.value = i; | |
335 | tree.frequency = histogram[i]; | |
336 | tree_array[i] = tree; | |
337 | heap_push(tree, &heap); | |
338 | } | |
339 | ||
340 | node_index = size; | |
341 | ||
342 | /* Construct the huffman tree */ | |
343 | while (heap.size > 1) { | |
344 | ||
345 | tree = heap_pop(&heap); | |
346 | tree_array[node_index].frequency = tree.frequency; | |
347 | tree_array[node_index].left = &tree_array[tree.value]; | |
348 | ||
349 | tree = heap_pop(&heap); | |
350 | tree_array[node_index].frequency += tree.frequency; | |
351 | tree_array[node_index].right = &tree_array[tree.value]; | |
352 | ||
353 | tree_array[node_index].value = node_index; | |
354 | heap_push(tree_array[node_index], &heap); | |
355 | ||
356 | node_index += 1; | |
357 | } | |
358 | ||
359 | return heap_pop(&heap); | |
360 | } | |
361 | ||
362 | int create_huff_lookup(struct huff_code *huff_lookup_table, int table_length, | |
363 | struct huff_tree root, uint8_t max_depth) | |
364 | { | |
365 | /* Used to create a count of number of elements with a given code length */ | |
366 | uint16_t count[MAX_HUFF_TREE_DEPTH + 1]; | |
367 | ||
368 | memset(count, 0, sizeof(count)); | |
369 | ||
370 | if (find_code_lengths(huff_lookup_table, count, root, max_depth) != 0) | |
371 | return 1; | |
372 | ||
373 | set_huff_codes(huff_lookup_table, table_length, count); | |
374 | ||
375 | return 0; | |
376 | } | |
377 | ||
378 | int find_code_lengths(struct huff_code *huff_lookup_table, uint16_t * count, | |
379 | struct huff_tree root, uint8_t max_depth) | |
380 | { | |
381 | struct linked_list depth_array[MAX_HUFF_TREE_DEPTH + 2]; | |
382 | struct linked_list_node linked_lists[MAX_HISTHEAP_SIZE]; | |
383 | struct linked_list_node *temp; | |
384 | uint16_t extra_nodes = 0; | |
385 | int i, j; | |
386 | ||
387 | memset(depth_array, 0, sizeof(depth_array)); | |
388 | memset(linked_lists, 0, sizeof(linked_lists)); | |
389 | for (i = 0; i < MAX_HISTHEAP_SIZE; i++) | |
390 | linked_lists[i].value = i; | |
391 | ||
392 | huffman_tree_traversal(depth_array, linked_lists, &extra_nodes, max_depth, root, 0); | |
393 | ||
394 | /* This for loop fixes up the huffman tree to have a maximum depth not exceeding | |
395 | * max_depth. This algorithm works by removing all elements below max_depth, | |
396 | * filling up the empty leafs which are created with elements form the huffman | |
397 | * tree and then iteratively pushing down the least frequent leaf that is above | |
398 | * max_depth to a depth 1 lower, and moving up a leaf below max_depth to that | |
399 | * same depth.*/ | |
400 | for (i = MAX_HUFF_TREE_DEPTH + 1; i > max_depth; i--) { | |
401 | ||
402 | /* find element to push up the tree */ | |
403 | while (depth_array[i].start != NULL) { | |
404 | if (extra_nodes > 0) { | |
405 | temp = pop_from_front(&depth_array[i]); | |
406 | append_to_back(&depth_array[max_depth], temp); | |
407 | extra_nodes -= 1; | |
408 | ||
409 | } else { | |
410 | assert(depth_array[max_depth].length % 2 == 0); | |
411 | assert(extra_nodes == 0); | |
412 | ||
413 | /* find element to push down in the tree */ | |
414 | for (j = max_depth - 1; j >= 0; j--) | |
415 | if (depth_array[j].start != NULL) | |
416 | break; | |
417 | ||
418 | /* No element available to push down further. */ | |
419 | if (j < 0) | |
420 | return 1; | |
421 | ||
422 | temp = pop_from_front(&depth_array[i]); | |
423 | append_to_front(&depth_array[j + 1], temp); | |
424 | ||
425 | temp = pop_from_front(&depth_array[j]); | |
426 | append_to_back(&depth_array[j + 1], temp); | |
427 | } | |
428 | } | |
429 | } | |
430 | ||
431 | for (i = 0; i < MAX_HUFF_TREE_DEPTH + 2; i++) { | |
432 | temp = depth_array[i].start; | |
433 | ||
434 | while (temp != NULL) { | |
435 | huff_lookup_table[temp->value].length = i; | |
436 | count[i] += 1; | |
437 | temp = temp->next; | |
438 | } | |
439 | } | |
440 | return 0; | |
441 | ||
442 | } | |
443 | ||
444 | void huffman_tree_traversal(struct linked_list *depth_array, | |
445 | struct linked_list_node *linked_lists, uint16_t * extra_nodes, | |
446 | uint8_t max_depth, struct huff_tree current_node, | |
447 | uint16_t current_depth) | |
448 | { | |
449 | /* This algorithm performs a traversal of the huffman tree. It is setup | |
450 | * to visit the leaves in order of frequency and bin elements into a | |
451 | * linked list by depth.*/ | |
452 | if (current_node.left == NULL) { | |
453 | if (current_depth < MAX_HUFF_TREE_DEPTH + 1) | |
454 | append_to_front(&depth_array[current_depth], | |
455 | &linked_lists[current_node.value]); | |
456 | else | |
457 | append_to_front(&depth_array[MAX_HUFF_TREE_DEPTH + 1], | |
458 | &linked_lists[current_node.value]); | |
459 | return; | |
460 | ||
461 | } else if (current_depth == max_depth) | |
462 | *extra_nodes += 1; | |
463 | ||
464 | if (current_node.left->frequency < current_node.right->frequency) { | |
465 | huffman_tree_traversal(depth_array, linked_lists, extra_nodes, max_depth, | |
466 | *current_node.right, current_depth + 1); | |
467 | huffman_tree_traversal(depth_array, linked_lists, extra_nodes, max_depth, | |
468 | *current_node.left, current_depth + 1); | |
469 | ||
470 | } else { | |
471 | huffman_tree_traversal(depth_array, linked_lists, extra_nodes, max_depth, | |
472 | *current_node.left, current_depth + 1); | |
473 | huffman_tree_traversal(depth_array, linked_lists, extra_nodes, max_depth, | |
474 | *current_node.right, current_depth + 1); | |
475 | } | |
476 | ||
477 | } | |
478 | ||
479 | /* | |
480 | * Returns integer with first length bits reversed and all higher bits zeroed | |
481 | */ | |
482 | uint16_t bit_reverse(uint16_t bits, uint8_t length) | |
483 | { | |
484 | bits = ((bits >> 1) & 0x55555555) | ((bits & 0x55555555) << 1); // swap bits | |
485 | bits = ((bits >> 2) & 0x33333333) | ((bits & 0x33333333) << 2); // swap pairs | |
486 | bits = ((bits >> 4) & 0x0F0F0F0F) | ((bits & 0x0F0F0F0F) << 4); // swap nibbles | |
487 | bits = ((bits >> 8) & 0x00FF00FF) | ((bits & 0x00FF00FF) << 8); // swap bytes | |
488 | return bits >> (16 - length); | |
489 | } | |
490 | ||
491 | void set_huff_codes(struct huff_code *huff_code_table, int table_length, uint16_t * count) | |
492 | { | |
493 | /* Uses the algorithm mentioned in the deflate standard, Rfc 1951. */ | |
494 | int i; | |
495 | uint16_t code = 0; | |
496 | uint16_t next_code[MAX_HUFF_TREE_DEPTH + 1]; | |
497 | ||
498 | next_code[0] = code; | |
499 | ||
500 | for (i = 1; i < MAX_HUFF_TREE_DEPTH + 1; i++) | |
501 | next_code[i] = (next_code[i - 1] + count[i - 1]) << 1; | |
502 | ||
503 | for (i = 0; i < table_length; i++) { | |
504 | if (huff_code_table[i].length != 0) { | |
505 | huff_code_table[i].code = | |
506 | bit_reverse(next_code[huff_code_table[i].length], | |
507 | huff_code_table[i].length); | |
508 | next_code[huff_code_table[i].length] += 1; | |
509 | } | |
510 | } | |
511 | ||
512 | return; | |
513 | } | |
514 | ||
515 | int create_header(uint8_t * header, uint32_t header_length, struct huff_code *lit_huff_table, | |
516 | struct huff_code *dist_huff_table, uint32_t end_of_block) | |
517 | { | |
518 | int i; | |
519 | uint64_t histogram[HUFF_LEN]; | |
520 | uint16_t huffman_rep[LIT_LEN + DIST_LEN]; | |
521 | uint16_t extra_bits[LIT_LEN + DIST_LEN]; | |
522 | uint16_t length; | |
523 | struct huff_tree root; | |
524 | struct huff_tree tree_array[2 * HUFF_LEN - 1]; | |
525 | struct huff_code lookup_table[HUFF_LEN]; | |
526 | struct huff_code combined_table[LIT_LEN + DIST_LEN]; | |
527 | ||
528 | /* hlit, hdist, and hclen are defined in RFC 1951 page 13 */ | |
529 | uint32_t hlit, hdist, hclen; | |
530 | uint64_t bit_count; | |
531 | ||
532 | memset(lookup_table, 0, sizeof(lookup_table)); | |
533 | ||
534 | /* Calculate hlit */ | |
535 | for (i = LIT_LEN - 1; i > 256; i--) | |
536 | if (lit_huff_table[i].length != 0) | |
537 | break; | |
538 | ||
539 | hlit = i - 256; | |
540 | ||
541 | /* Calculate hdist */ | |
542 | for (i = DIST_LEN - 1; i > 0; i--) | |
543 | if (dist_huff_table[i].length != 0) | |
544 | break; | |
545 | ||
546 | hdist = i; | |
547 | ||
548 | /* Combine huffman tables for run length encoding */ | |
549 | for (i = 0; i < 257 + hlit; i++) | |
550 | combined_table[i] = lit_huff_table[i]; | |
551 | for (i = 0; i < 1 + hdist; i++) | |
552 | combined_table[i + hlit + 257] = dist_huff_table[i]; | |
553 | ||
554 | memset(extra_bits, 0, LIT_LEN + DIST_LEN); | |
555 | memset(histogram, 0, sizeof(histogram)); | |
556 | ||
557 | /* Create a run length encoded representation of the literal/lenght and | |
558 | * distance huffman trees. */ | |
559 | length = create_huffman_rep(huffman_rep, histogram, extra_bits, | |
560 | combined_table, hlit + 257 + hdist + 1); | |
561 | ||
562 | /* Create a huffman tree to encode run length encoded representation. */ | |
563 | root = create_symbol_subset_huff_tree(tree_array, histogram, HUFF_LEN); | |
564 | create_huff_lookup(lookup_table, HUFF_LEN, root, 7); | |
565 | ||
566 | /* Calculate hclen */ | |
567 | for (i = CODE_LEN_CODES - 1; i > 3; i--) /* i must be at least 4 */ | |
568 | if (lookup_table[code_length_code_order[i]].length != 0) | |
569 | break; | |
570 | ||
571 | hclen = i - 3; | |
572 | ||
573 | /* Generate actual header. */ | |
574 | bit_count = create_huffman_header(header, header_length, lookup_table, huffman_rep, | |
575 | extra_bits, length, end_of_block, hclen, hlit, | |
576 | hdist); | |
577 | ||
578 | return bit_count; | |
579 | } | |
580 | ||
581 | uint16_t create_huffman_rep(uint16_t * huffman_rep, uint64_t * histogram, | |
582 | uint16_t * extra_bits, struct huff_code * huff_table, uint16_t len) | |
583 | { | |
584 | uint16_t current_in_index = 0, current_out_index = 0, run_length, last_code; | |
585 | ||
586 | while (current_in_index < len) { | |
587 | last_code = huff_table[current_in_index].length; | |
588 | run_length = 0; | |
589 | ||
590 | while (current_in_index < len | |
591 | && last_code == huff_table[current_in_index].length) { | |
592 | run_length += 1; | |
593 | current_in_index += 1; | |
594 | } | |
595 | ||
596 | current_out_index = flush_repeats(huffman_rep, histogram, extra_bits, | |
597 | last_code, run_length, current_out_index); | |
598 | } | |
599 | return current_out_index; | |
600 | } | |
601 | ||
602 | uint16_t flush_repeats(uint16_t * huffman_rep, uint64_t * histogram, uint16_t * extra_bits, | |
603 | uint16_t last_code, uint16_t run_length, uint16_t current_index) | |
604 | { | |
605 | int j; | |
606 | ||
607 | if (last_code != 0 && last_code < HUFF_LEN && run_length > 0) { | |
608 | huffman_rep[current_index++] = last_code; | |
609 | histogram[last_code] += 1; | |
610 | run_length -= 1; | |
611 | ||
612 | } | |
613 | ||
614 | if (run_length < SHORTEST_MATCH) { | |
615 | for (j = 0; j < run_length; j++) { | |
616 | huffman_rep[current_index++] = last_code; | |
617 | histogram[last_code] += 1; | |
618 | } | |
619 | } else { | |
620 | if (last_code == 0) { | |
621 | /* The values 138 is the maximum repeat length | |
622 | * represented with code 18. The value 10 is the maximum | |
623 | * repeate length represented with 17. */ | |
624 | for (; run_length > 138; run_length -= 138) { | |
625 | huffman_rep[current_index] = 0x12; | |
626 | extra_bits[current_index++] = 0x7F7; | |
627 | histogram[18]++; | |
628 | } | |
629 | ||
630 | if (run_length > 10) { | |
631 | huffman_rep[current_index] = 18; | |
632 | extra_bits[current_index++] = ((run_length - 11) << 4) | 7; | |
633 | histogram[18] += 1; | |
634 | ||
635 | } else if (run_length >= SHORTEST_MATCH) { | |
636 | huffman_rep[current_index] = 17; | |
637 | extra_bits[current_index++] = ((run_length - 3) << 4) | 3; | |
638 | histogram[17] += 1; | |
639 | ||
640 | } else { | |
641 | for (j = 0; j < run_length; j++) { | |
642 | huffman_rep[current_index++] = last_code; | |
643 | histogram[last_code] += 1; | |
644 | } | |
645 | } | |
646 | ||
647 | } else { | |
648 | for (; run_length > 6; run_length -= 6) { | |
649 | huffman_rep[current_index] = 0x10; | |
650 | extra_bits[current_index++] = 0x32; | |
651 | histogram[16]++; | |
652 | } | |
653 | ||
654 | if (run_length >= SHORTEST_MATCH) { | |
655 | huffman_rep[current_index] = 16; | |
656 | extra_bits[current_index++] = ((run_length - 3) << 4) | 2; | |
657 | histogram[16] += 1; | |
658 | ||
659 | } else { | |
660 | for (j = 0; j < run_length; j++) { | |
661 | huffman_rep[current_index++] = last_code; | |
662 | histogram[last_code] += 1; | |
663 | } | |
664 | } | |
665 | } | |
666 | ||
667 | } | |
668 | ||
669 | return current_index; | |
670 | } | |
671 | ||
672 | int create_huffman_header(uint8_t * header, uint32_t header_length, | |
673 | struct huff_code *lookup_table, uint16_t * huffman_rep, | |
674 | uint16_t * extra_bits, uint16_t huffman_rep_length, | |
675 | uint32_t end_of_block, uint32_t hclen, uint32_t hlit, uint32_t hdist) | |
676 | { | |
677 | /* hlit, hdist, hclen are as defined in the deflate standard, head is the | |
678 | * first three deflate header bits.*/ | |
679 | int i; | |
680 | uint32_t head; | |
681 | uint64_t bit_count; | |
682 | struct huff_code huffman_value; | |
683 | struct BitBuf2 header_bitbuf; | |
684 | ||
685 | if (end_of_block) | |
686 | head = 0x05; | |
687 | else | |
688 | head = 0x04; | |
689 | ||
690 | set_buf(&header_bitbuf, header, header_length); | |
691 | init(&header_bitbuf); | |
692 | ||
693 | write_bits(&header_bitbuf, (head | (hlit << 3) | (hdist << 8) | (hclen << 13)), | |
694 | DYN_HDR_START_LEN); | |
695 | ||
696 | uint64_t tmp = 0; | |
697 | for (i = hclen + 3; i >= 0; i--) { | |
698 | tmp = (tmp << 3) | lookup_table[code_length_code_order[i]].length; | |
699 | } | |
700 | ||
701 | write_bits(&header_bitbuf, tmp, (hclen + 4) * 3); | |
702 | ||
703 | for (i = 0; i < huffman_rep_length; i++) { | |
704 | huffman_value = lookup_table[huffman_rep[i]]; | |
705 | ||
706 | write_bits(&header_bitbuf, (uint64_t) huffman_value.code, | |
707 | (uint32_t) huffman_value.length); | |
708 | ||
709 | if (huffman_rep[i] > 15) { | |
710 | write_bits(&header_bitbuf, (uint64_t) extra_bits[i] >> 4, | |
711 | (uint32_t) extra_bits[i] & 0xF); | |
712 | } | |
713 | } | |
714 | bit_count = 8 * buffer_used(&header_bitbuf) + header_bitbuf.m_bit_count; | |
715 | flush(&header_bitbuf); | |
716 | ||
717 | return bit_count; | |
718 | } | |
719 | ||
720 | void create_code_tables(uint16_t * code_table, uint8_t * code_length_table, uint32_t length, | |
721 | struct huff_code *hufftable) | |
722 | { | |
723 | int i; | |
724 | for (i = 0; i < length; i++) { | |
725 | code_table[i] = hufftable[i].code; | |
726 | code_length_table[i] = hufftable[i].length; | |
727 | } | |
728 | } | |
729 | ||
730 | void create_packed_len_table(uint32_t * packed_table, struct huff_code *lit_len_hufftable) | |
731 | { | |
732 | int i, count = 0; | |
733 | uint16_t extra_bits; | |
734 | uint16_t extra_bits_count = 0; | |
735 | ||
736 | /* Gain extra bits is the next place where the number of extra bits in | |
737 | * lenght codes increases. */ | |
738 | uint16_t gain_extra_bits = LEN_EXTRA_BITS_START; | |
739 | ||
740 | for (i = 257; i < LIT_LEN - 1; i++) { | |
741 | for (extra_bits = 0; extra_bits < (1 << extra_bits_count); extra_bits++) { | |
742 | if (count > 254) | |
743 | break; | |
744 | packed_table[count++] = | |
745 | (extra_bits << (lit_len_hufftable[i].length + LENGTH_BITS)) | | |
746 | (lit_len_hufftable[i].code << LENGTH_BITS) | | |
747 | (lit_len_hufftable[i].length + extra_bits_count); | |
748 | } | |
749 | ||
750 | if (i == gain_extra_bits) { | |
751 | gain_extra_bits += LEN_EXTRA_BITS_INTERVAL; | |
752 | extra_bits_count += 1; | |
753 | } | |
754 | } | |
755 | ||
756 | packed_table[count] = (lit_len_hufftable[LIT_LEN - 1].code << LENGTH_BITS) | | |
757 | (lit_len_hufftable[LIT_LEN - 1].length); | |
758 | } | |
759 | ||
760 | void create_packed_dist_table(uint32_t * packed_table, uint32_t length, | |
761 | struct huff_code *dist_hufftable) | |
762 | { | |
763 | int i, count = 0; | |
764 | uint16_t extra_bits; | |
765 | uint16_t extra_bits_count = 0; | |
766 | ||
767 | /* Gain extra bits is the next place where the number of extra bits in | |
768 | * distance codes increases. */ | |
769 | uint16_t gain_extra_bits = DIST_EXTRA_BITS_START; | |
770 | ||
771 | for (i = 0; i < DIST_LEN; i++) { | |
772 | for (extra_bits = 0; extra_bits < (1 << extra_bits_count); extra_bits++) { | |
773 | if (count >= length) | |
774 | return; | |
775 | ||
776 | packed_table[count++] = | |
777 | (extra_bits << (dist_hufftable[i].length + LENGTH_BITS)) | | |
778 | (dist_hufftable[i].code << LENGTH_BITS) | | |
779 | (dist_hufftable[i].length + extra_bits_count); | |
780 | ||
781 | } | |
782 | ||
783 | if (i == gain_extra_bits) { | |
784 | gain_extra_bits += DIST_EXTRA_BITS_INTERVAL; | |
785 | extra_bits_count += 1; | |
786 | } | |
787 | } | |
788 | } | |
789 | ||
790 | int are_hufftables_useable(struct huff_code *lit_len_hufftable, | |
791 | struct huff_code *dist_hufftable) | |
792 | { | |
793 | int max_lit_code_len = 0, max_len_code_len = 0, max_dist_code_len = 0; | |
794 | int dist_extra_bits = 0, len_extra_bits = 0; | |
795 | int gain_dist_extra_bits = DIST_EXTRA_BITS_START; | |
796 | int gain_len_extra_bits = LEN_EXTRA_BITS_START; | |
797 | int max_code_len; | |
798 | int i; | |
799 | ||
800 | for (i = 0; i < LIT_LEN; i++) | |
801 | if (lit_len_hufftable[i].length > max_lit_code_len) | |
802 | max_lit_code_len = lit_len_hufftable[i].length; | |
803 | ||
804 | for (i = 257; i < LIT_LEN - 1; i++) { | |
805 | if (lit_len_hufftable[i].length + len_extra_bits > max_len_code_len) | |
806 | max_len_code_len = lit_len_hufftable[i].length + len_extra_bits; | |
807 | ||
808 | if (i == gain_len_extra_bits) { | |
809 | gain_len_extra_bits += LEN_EXTRA_BITS_INTERVAL; | |
810 | len_extra_bits += 1; | |
811 | } | |
812 | } | |
813 | ||
814 | for (i = 0; i < DIST_LEN; i++) { | |
815 | if (dist_hufftable[i].length + dist_extra_bits > max_dist_code_len) | |
816 | max_dist_code_len = dist_hufftable[i].length + dist_extra_bits; | |
817 | ||
818 | if (i == gain_dist_extra_bits) { | |
819 | gain_dist_extra_bits += DIST_EXTRA_BITS_INTERVAL; | |
820 | dist_extra_bits += 1; | |
821 | } | |
822 | } | |
823 | ||
824 | max_code_len = max_lit_code_len + max_len_code_len + max_dist_code_len; | |
825 | ||
826 | /* Some versions of igzip can write upto one literal, one length and one | |
827 | * distance code at the same time. This checks to make sure that is | |
828 | * always writeable in bitbuf*/ | |
829 | return (max_code_len > MAX_BITBUF_BIT_WRITE); | |
830 | } | |
831 | ||
832 | int isal_create_hufftables(struct isal_hufftables *hufftables, | |
833 | struct isal_huff_histogram *histogram) | |
834 | { | |
835 | struct huff_tree lit_tree, dist_tree; | |
836 | struct huff_tree lit_tree_array[2 * LIT_LEN - 1], dist_tree_array[2 * DIST_LEN - 1]; | |
837 | struct huff_code lit_huff_table[LIT_LEN], dist_huff_table[DIST_LEN]; | |
838 | uint64_t bit_count; | |
839 | int max_dist = convert_dist_to_dist_sym(IGZIP_D); | |
840 | ||
841 | uint32_t *dist_table = hufftables->dist_table; | |
842 | uint32_t *len_table = hufftables->len_table; | |
843 | uint16_t *lit_table = hufftables->lit_table; | |
844 | uint16_t *dcodes = hufftables->dcodes; | |
845 | uint8_t *lit_table_sizes = hufftables->lit_table_sizes; | |
846 | uint8_t *dcodes_sizes = hufftables->dcodes_sizes; | |
847 | uint8_t *deflate_hdr = hufftables->deflate_hdr; | |
848 | uint64_t *lit_len_histogram = histogram->lit_len_histogram; | |
849 | uint64_t *dist_histogram = histogram->dist_histogram; | |
850 | ||
851 | memset(hufftables, 0, sizeof(struct isal_hufftables)); | |
852 | memset(lit_tree_array, 0, sizeof(lit_tree_array)); | |
853 | memset(dist_tree_array, 0, sizeof(dist_tree_array)); | |
854 | memset(lit_huff_table, 0, sizeof(lit_huff_table)); | |
855 | memset(dist_huff_table, 0, sizeof(dist_huff_table)); | |
856 | ||
857 | lit_tree = create_huff_tree(lit_tree_array, lit_len_histogram, LIT_LEN); | |
858 | dist_tree = create_huff_tree(dist_tree_array, dist_histogram, max_dist + 1); | |
859 | ||
860 | if (create_huff_lookup(lit_huff_table, LIT_LEN, lit_tree, MAX_DEFLATE_CODE_LEN) > 0) | |
861 | return INVALID_LIT_LEN_HUFFCODE; | |
862 | ||
863 | if (create_huff_lookup(dist_huff_table, DIST_LEN, dist_tree, MAX_DEFLATE_CODE_LEN) > 0) | |
864 | return INVALID_DIST_HUFFCODE; | |
865 | ||
866 | if (are_hufftables_useable(lit_huff_table, dist_huff_table)) { | |
867 | if (create_huff_lookup | |
868 | (lit_huff_table, LIT_LEN, lit_tree, MAX_SAFE_LIT_CODE_LEN) > 0) | |
869 | return INVALID_LIT_LEN_HUFFCODE; | |
870 | ||
871 | if (create_huff_lookup | |
872 | (dist_huff_table, DIST_LEN, dist_tree, MAX_SAFE_DIST_CODE_LEN) > 0) | |
873 | return INVALID_DIST_HUFFCODE; | |
874 | ||
875 | if (are_hufftables_useable(lit_huff_table, dist_huff_table)) | |
876 | return INVALID_HUFFCODE; | |
877 | } | |
878 | ||
879 | create_code_tables(dcodes, dcodes_sizes, DIST_LEN - DCODE_OFFSET, | |
880 | dist_huff_table + DCODE_OFFSET); | |
881 | ||
882 | create_code_tables(lit_table, lit_table_sizes, LIT_TABLE_SIZE, lit_huff_table); | |
883 | ||
884 | create_packed_len_table(len_table, lit_huff_table); | |
885 | create_packed_dist_table(dist_table, DIST_TABLE_SIZE, dist_huff_table); | |
886 | ||
887 | bit_count = | |
888 | create_header(deflate_hdr, sizeof(deflate_hdr), lit_huff_table, dist_huff_table, | |
889 | LAST_BLOCK); | |
890 | ||
891 | hufftables->deflate_hdr_count = bit_count / 8; | |
892 | hufftables->deflate_hdr_extra_bits = bit_count % 8; | |
893 | ||
894 | return 0; | |
895 | } | |
896 | ||
897 | int isal_create_hufftables_subset(struct isal_hufftables *hufftables, | |
898 | struct isal_huff_histogram *histogram) | |
899 | { | |
900 | struct huff_tree lit_tree, dist_tree; | |
901 | struct huff_tree lit_tree_array[2 * LIT_LEN - 1], dist_tree_array[2 * DIST_LEN - 1]; | |
902 | struct huff_code lit_huff_table[LIT_LEN], dist_huff_table[DIST_LEN]; | |
903 | uint64_t bit_count; | |
904 | int j, max_dist = convert_dist_to_dist_sym(IGZIP_D); | |
905 | ||
906 | uint32_t *dist_table = hufftables->dist_table; | |
907 | uint32_t *len_table = hufftables->len_table; | |
908 | uint16_t *lit_table = hufftables->lit_table; | |
909 | uint16_t *dcodes = hufftables->dcodes; | |
910 | uint8_t *lit_table_sizes = hufftables->lit_table_sizes; | |
911 | uint8_t *dcodes_sizes = hufftables->dcodes_sizes; | |
912 | uint8_t *deflate_hdr = hufftables->deflate_hdr; | |
913 | uint64_t *lit_len_histogram = histogram->lit_len_histogram; | |
914 | uint64_t *dist_histogram = histogram->dist_histogram; | |
915 | ||
916 | memset(hufftables, 0, sizeof(struct isal_hufftables)); | |
917 | memset(lit_tree_array, 0, sizeof(lit_tree_array)); | |
918 | memset(dist_tree_array, 0, sizeof(dist_tree_array)); | |
919 | memset(lit_huff_table, 0, sizeof(lit_huff_table)); | |
920 | memset(dist_huff_table, 0, sizeof(dist_huff_table)); | |
921 | ||
922 | for (j = LIT_TABLE_SIZE; j < LIT_LEN; j++) | |
923 | if (lit_len_histogram[j] == 0) | |
924 | lit_len_histogram[j]++; | |
925 | ||
926 | lit_tree = create_symbol_subset_huff_tree(lit_tree_array, lit_len_histogram, LIT_LEN); | |
927 | dist_tree = create_huff_tree(dist_tree_array, dist_histogram, max_dist + 1); | |
928 | ||
929 | if (create_huff_lookup(lit_huff_table, LIT_LEN, lit_tree, MAX_DEFLATE_CODE_LEN) > 0) | |
930 | return INVALID_LIT_LEN_HUFFCODE; | |
931 | ||
932 | if (create_huff_lookup(dist_huff_table, DIST_LEN, dist_tree, MAX_DEFLATE_CODE_LEN) > 0) | |
933 | return INVALID_DIST_HUFFCODE; | |
934 | ||
935 | if (are_hufftables_useable(lit_huff_table, dist_huff_table)) { | |
936 | if (create_huff_lookup | |
937 | (lit_huff_table, LIT_LEN, lit_tree, MAX_SAFE_LIT_CODE_LEN) > 0) | |
938 | return INVALID_LIT_LEN_HUFFCODE; | |
939 | ||
940 | if (create_huff_lookup | |
941 | (dist_huff_table, DIST_LEN, dist_tree, MAX_SAFE_DIST_CODE_LEN) > 0) | |
942 | return INVALID_DIST_HUFFCODE; | |
943 | ||
944 | if (are_hufftables_useable(lit_huff_table, dist_huff_table)) | |
945 | return INVALID_HUFFCODE; | |
946 | } | |
947 | ||
948 | create_code_tables(dcodes, dcodes_sizes, DIST_LEN - DCODE_OFFSET, | |
949 | dist_huff_table + DCODE_OFFSET); | |
950 | ||
951 | create_code_tables(lit_table, lit_table_sizes, LIT_TABLE_SIZE, lit_huff_table); | |
952 | ||
953 | create_packed_len_table(len_table, lit_huff_table); | |
954 | create_packed_dist_table(dist_table, DIST_TABLE_SIZE, dist_huff_table); | |
955 | ||
956 | bit_count = | |
957 | create_header(deflate_hdr, sizeof(deflate_hdr), lit_huff_table, dist_huff_table, | |
958 | LAST_BLOCK); | |
959 | ||
960 | hufftables->deflate_hdr_count = bit_count / 8; | |
961 | hufftables->deflate_hdr_extra_bits = bit_count % 8; | |
962 | ||
963 | return 0; | |
964 | } |