1;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 2; Copyright(c) 2011-2018 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; returns modified node_ptr 31; uint32_t proc_heap(uint64_t *heap, uint32_t heap_size); 32 33%include "reg_sizes.asm" 34%include "heap_macros.asm" 35 36%ifidn __OUTPUT_FORMAT__, win64 37%define heap rcx ; pointer, 64-bit 38%define heap_size rdx 39%define arg3 r8 40%define child rsi 41%define tmp32 rdi 42%else 43%define heap rdi 44%define heap_size rsi 45%define arg3 rdx 46%define child rcx 47%define tmp32 rdx 48%endif 49 50%define node_ptr rax 51%define h1 r8 52%define h2 r9 53%define h3 r10 54%define i r11 55%define tmp2 r12 56 57[bits 64] 58default rel 59section .text 60 61 global build_huff_tree 62build_huff_tree: 63 endbranch 64%ifidn __OUTPUT_FORMAT__, win64 65 push rsi 66 push rdi 67%endif 68 push r12 69 70 mov node_ptr, arg3 71.main_loop: 72 ; REMOVE_MIN64(heap, heap_size, h1); 73 mov h2, [heap + heap_size*8] 74 mov h1, [heap + 1*8] 75 mov qword [heap + heap_size*8], -1 76 dec heap_size 77 mov [heap + 1*8], h2 78 79 mov i, 1 80 heapify heap, heap_size, i, child, h2, h3, tmp32, tmp2 81 82 mov h2, [heap + 1*8] 83 lea h3, [h1 + h2] 84 mov [heap + node_ptr*8], h1 %+ w 85 mov [heap + node_ptr*8 - 8], h2 %+ w 86 87 and h3, ~0xffff 88 or h3, node_ptr 89 sub node_ptr, 2 90 91 ; replace_min64(heap, heap_size, h3) 92 mov [heap + 1*8], h3 93 mov i, 1 94 heapify heap, heap_size, i, child, h2, h3, tmp32, tmp2 95 96 cmp heap_size, 1 97 ja .main_loop 98 99 mov h1, [heap + 1*8] 100 mov [heap + node_ptr*8], h1 %+ w 101 102 pop r12 103%ifidn __OUTPUT_FORMAT__, win64 104 pop rdi 105 pop rsi 106%endif 107 ret 108 109align 32 110 global build_heap 111build_heap: 112 endbranch 113%ifidn __OUTPUT_FORMAT__, win64 114 push rsi 115 push rdi 116%endif 117 push r12 118 mov qword [heap + heap_size*8 + 8], -1 119 mov i, heap_size 120 shr i, 1 121.loop: 122 mov h1, i 123 heapify heap, heap_size, h1, child, h2, h3, tmp32, tmp2 124 dec i 125 jnz .loop 126 127 pop r12 128%ifidn __OUTPUT_FORMAT__, win64 129 pop rdi 130 pop rsi 131%endif 132 ret 133