1ec6e5de6SGreg Tucker /********************************************************************** 2ec6e5de6SGreg Tucker Copyright(c) 2011-2017 Intel Corporation All rights reserved. 3ec6e5de6SGreg Tucker 4ec6e5de6SGreg Tucker Redistribution and use in source and binary forms, with or without 5ec6e5de6SGreg Tucker modification, are permitted provided that the following conditions 6ec6e5de6SGreg Tucker are met: 7ec6e5de6SGreg Tucker * Redistributions of source code must retain the above copyright 8ec6e5de6SGreg Tucker notice, this list of conditions and the following disclaimer. 9ec6e5de6SGreg Tucker * Redistributions in binary form must reproduce the above copyright 10ec6e5de6SGreg Tucker notice, this list of conditions and the following disclaimer in 11ec6e5de6SGreg Tucker the documentation and/or other materials provided with the 12ec6e5de6SGreg Tucker distribution. 13ec6e5de6SGreg Tucker * Neither the name of Intel Corporation nor the names of its 14ec6e5de6SGreg Tucker contributors may be used to endorse or promote products derived 15ec6e5de6SGreg Tucker from this software without specific prior written permission. 16ec6e5de6SGreg Tucker 17ec6e5de6SGreg Tucker THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 18ec6e5de6SGreg Tucker "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 19ec6e5de6SGreg Tucker LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 20ec6e5de6SGreg Tucker A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 21ec6e5de6SGreg Tucker OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 22ec6e5de6SGreg Tucker SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 23ec6e5de6SGreg Tucker LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24ec6e5de6SGreg Tucker DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25ec6e5de6SGreg Tucker THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26ec6e5de6SGreg Tucker (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 27ec6e5de6SGreg Tucker OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28ec6e5de6SGreg Tucker **********************************************************************/ 29ec6e5de6SGreg Tucker 30ec6e5de6SGreg Tucker #include "igzip_lib.h" 31ec6e5de6SGreg Tucker #include "huff_codes.h" 32ec6e5de6SGreg Tucker 33*a301835eSDaniel Verkamp static inline void heapify(uint64_t * heap, uint64_t heap_size, uint64_t index) 34ec6e5de6SGreg Tucker { 35ec6e5de6SGreg Tucker uint64_t child = 2 * index, tmp; 36ec6e5de6SGreg Tucker while (child <= heap_size) { 37ec6e5de6SGreg Tucker child = (heap[child] <= heap[child + 1]) ? child : child + 1; 38ec6e5de6SGreg Tucker 39ec6e5de6SGreg Tucker if (heap[index] > heap[child]) { 40ec6e5de6SGreg Tucker tmp = heap[index]; 41ec6e5de6SGreg Tucker heap[index] = heap[child]; 42ec6e5de6SGreg Tucker heap[child] = tmp; 43ec6e5de6SGreg Tucker index = child; 44ec6e5de6SGreg Tucker child = 2 * index; 45ec6e5de6SGreg Tucker } else 46ec6e5de6SGreg Tucker break; 47ec6e5de6SGreg Tucker } 48ec6e5de6SGreg Tucker } 49ec6e5de6SGreg Tucker 50ec6e5de6SGreg Tucker void build_heap(uint64_t * heap, uint64_t heap_size) 51ec6e5de6SGreg Tucker { 52ec6e5de6SGreg Tucker uint64_t i; 53ec6e5de6SGreg Tucker heap[heap_size + 1] = -1; 54ec6e5de6SGreg Tucker for (i = heap_size / 2; i > 0; i--) 55ec6e5de6SGreg Tucker heapify(heap, heap_size, i); 56ec6e5de6SGreg Tucker 57ec6e5de6SGreg Tucker } 58ec6e5de6SGreg Tucker 59ec6e5de6SGreg Tucker uint32_t build_huff_tree(struct heap_tree *heap_space, uint64_t heap_size, uint64_t node_ptr) 60ec6e5de6SGreg Tucker { 61ec6e5de6SGreg Tucker uint64_t *heap = (uint64_t *) heap_space; 62ec6e5de6SGreg Tucker uint64_t h1, h2; 63ec6e5de6SGreg Tucker 64ec6e5de6SGreg Tucker while (heap_size > 1) { 65ec6e5de6SGreg Tucker h1 = heap[1]; 66ec6e5de6SGreg Tucker heap[1] = heap[heap_size]; 67ec6e5de6SGreg Tucker heap[heap_size--] = -1; 68ec6e5de6SGreg Tucker 69ec6e5de6SGreg Tucker heapify(heap, heap_size, 1); 70ec6e5de6SGreg Tucker 71ec6e5de6SGreg Tucker h2 = heap[1]; 72ec6e5de6SGreg Tucker heap[1] = ((h1 + h2) & ~0xFFFFull) | node_ptr; 73ec6e5de6SGreg Tucker 74ec6e5de6SGreg Tucker heapify(heap, heap_size, 1); 75ec6e5de6SGreg Tucker 76ec6e5de6SGreg Tucker *(uint16_t *) (&heap[node_ptr]) = h1; 77ec6e5de6SGreg Tucker *(uint16_t *) (&heap[node_ptr - 1]) = h2; 78ec6e5de6SGreg Tucker node_ptr -= 2; 79ec6e5de6SGreg Tucker 80ec6e5de6SGreg Tucker } 81ec6e5de6SGreg Tucker h1 = heap[1]; 82ec6e5de6SGreg Tucker *(uint16_t *) (&heap[node_ptr]) = h1; 83ec6e5de6SGreg Tucker return node_ptr; 84ec6e5de6SGreg Tucker } 85