]> git.proxmox.com Git - ceph.git/blob - ceph/src/isa-l/igzip/huff_codes.c
projects / ceph.git / blob
? search:


d69c99d9ed60cce04bf0352b1d7e77d50ad9417b
[ceph.git] / ceph / src / isa-l / igzip / huff_codes.c
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 }
Ceph