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" 32*aae6e29dSRoy Oursler #include "unaligned.h" 33ec6e5de6SGreg Tucker 34a301835eSDaniel Verkamp static inline void heapify(uint64_t * heap, uint64_t heap_size, uint64_t index) 35ec6e5de6SGreg Tucker { 36ec6e5de6SGreg Tucker uint64_t child = 2 * index, tmp; 37ec6e5de6SGreg Tucker while (child <= heap_size) { 38ec6e5de6SGreg Tucker child = (heap[child] <= heap[child + 1]) ? child : child + 1; 39ec6e5de6SGreg Tucker 40ec6e5de6SGreg Tucker if (heap[index] > heap[child]) { 41ec6e5de6SGreg Tucker tmp = heap[index]; 42ec6e5de6SGreg Tucker heap[index] = heap[child]; 43ec6e5de6SGreg Tucker heap[child] = tmp; 44ec6e5de6SGreg Tucker index = child; 45ec6e5de6SGreg Tucker child = 2 * index; 46ec6e5de6SGreg Tucker } else 47ec6e5de6SGreg Tucker break; 48ec6e5de6SGreg Tucker } 49ec6e5de6SGreg Tucker } 50ec6e5de6SGreg Tucker 51ec6e5de6SGreg Tucker void build_heap(uint64_t * heap, uint64_t heap_size) 52ec6e5de6SGreg Tucker { 53ec6e5de6SGreg Tucker uint64_t i; 54ec6e5de6SGreg Tucker heap[heap_size + 1] = -1; 55ec6e5de6SGreg Tucker for (i = heap_size / 2; i > 0; i--) 56ec6e5de6SGreg Tucker heapify(heap, heap_size, i); 57ec6e5de6SGreg Tucker 58ec6e5de6SGreg Tucker } 59ec6e5de6SGreg Tucker 60ec6e5de6SGreg Tucker uint32_t build_huff_tree(struct heap_tree *heap_space, uint64_t heap_size, uint64_t node_ptr) 61ec6e5de6SGreg Tucker { 62ec6e5de6SGreg Tucker uint64_t *heap = (uint64_t *) heap_space; 63ec6e5de6SGreg Tucker uint64_t h1, h2; 64ec6e5de6SGreg Tucker 65ec6e5de6SGreg Tucker while (heap_size > 1) { 66ec6e5de6SGreg Tucker h1 = heap[1]; 67ec6e5de6SGreg Tucker heap[1] = heap[heap_size]; 68ec6e5de6SGreg Tucker heap[heap_size--] = -1; 69ec6e5de6SGreg Tucker 70ec6e5de6SGreg Tucker heapify(heap, heap_size, 1); 71ec6e5de6SGreg Tucker 72ec6e5de6SGreg Tucker h2 = heap[1]; 73ec6e5de6SGreg Tucker heap[1] = ((h1 + h2) & ~0xFFFFull) | node_ptr; 74ec6e5de6SGreg Tucker 75ec6e5de6SGreg Tucker heapify(heap, heap_size, 1); 76ec6e5de6SGreg Tucker 77*aae6e29dSRoy Oursler store_u16((uint8_t *) & heap[node_ptr], h1); 78*aae6e29dSRoy Oursler store_u16((uint8_t *) & heap[node_ptr - 1], h2); 79ec6e5de6SGreg Tucker node_ptr -= 2; 80ec6e5de6SGreg Tucker 81ec6e5de6SGreg Tucker } 82ec6e5de6SGreg Tucker h1 = heap[1]; 83*aae6e29dSRoy Oursler store_u16((uint8_t *) & heap[node_ptr], h1); 84ec6e5de6SGreg Tucker return node_ptr; 85ec6e5de6SGreg Tucker } 86