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; heapify heap, heap_size, i, child, tmp1, tmp2, tmpd 31%macro heapify2 7 32%define %%heap %1 ; qword ptr 33%define %%heap_size %2 ; dword 34%define %%i %3 ; dword 35%define %%child %4 ; dword 36%define %%tmp1 %5 ; qword 37%define %%tmp2 %6 ; qword 38%define %%tmpd %7 ; dword 39 align 16 40%%heapify1: 41 lea %%child, [%%i + %%i] 42 cmp %%child, %%heap_size 43 ja %%end_heapify1 44 mov %%tmp1, [%%heap + %%child] 45 mov %%tmpd, %%child 46 mov %%tmp2, [%%heap + %%child) + 8] 47 lea %%child, [%%child + 1] 48 cmove %%tmp2, %%tmp1 49 cmp %%tmp1, %%tmp2 50 cmovbe %%child, %%tmpd 51 cmovbe %%tmp2, %%tmp1 52 ; child is correct, %%tmp2 = heap[child] 53 mov %%tmp1, [%%heap + %%i] 54 cmp %%tmp1, %%tmp2 55 jbe %%end_heapify1 56 mov [%%heap + %%i], %%tmp2 57 mov [%%heap + %%child], %%tmp1 58 mov %%i, %%child 59 jmp %%heapify1 60%%end_heapify1 61%endm 62 63; heapify heap, heap_size, i, child, tmp1, tmp2, tmpd, tmp3 64%macro heapify 8 65%define %%heap %1 ; qword ptr 66%define %%heap_size %2 ; qword 67%define %%i %3 ; qword 68%define %%child %4 ; qword 69%define %%tmp1 %5 ; qword 70%define %%tmp2 %6 ; qword 71%define %%tmpd %7 ; qword 72%define %%tmp3 %8 73 align 16 74%%heapify1: 75 lea %%child, [%%i + %%i] 76; mov %%child, %%i 77; add %%child, %%child 78 cmp %%child, %%heap_size 79 ja %%end_heapify1 80 mov %%tmp1, [%%heap + %%child*8] 81 mov %%tmp2, [%%heap + %%child*8 + 8] 82 mov %%tmp3, [%%heap + %%i*8] 83 mov %%tmpd, %%child 84 add %%tmpd, 1 85 86 cmp %%tmp2, %%tmp1 87 cmovb %%child, %%tmpd 88 cmovb %%tmp1, %%tmp2 89 ; child is correct, tmp1 = heap[child] 90 cmp %%tmp3, %%tmp1 91 jbe %%end_heapify1 92 ; swap i and child 93 mov [%%heap + %%i*8], %%tmp1 94 mov [%%heap + %%child*8], %%tmp3 95 mov %%i, %%child 96 jmp %%heapify1 97%%end_heapify1: 98%endm 99