ceph/src/spdk/isa-l/igzip/proc_heap.asm

   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         global build_huff_tree
  58 build_huff_tree:
  59 %ifidn __OUTPUT_FORMAT__, win64
  60         push    rsi
  61         push    rdi
  62 %endif
  63         push    r12
  64
  65         mov     node_ptr, arg3
  66 .main_loop:
  67         ; REMOVE_MIN64(heap, heap_size, h1);
  68         mov     h2, [heap + heap_size*8]
  69         mov     h1, [heap + 1*8]
  70         mov     qword [heap + heap_size*8], -1
  71         dec     heap_size
  72         mov     [heap + 1*8], h2
  73
  74         mov     i, 1
  75         heapify heap, heap_size, i, child, h2, h3, tmp32, tmp2
  76
  77         mov     h2, [heap + 1*8]
  78         lea     h3, [h1 + h2]
  79         mov     [heap + node_ptr*8], h1 %+ w
  80         mov     [heap + node_ptr*8 - 8], h2 %+ w
  81
  82         and     h3, ~0xffff
  83         or      h3, node_ptr
  84         sub     node_ptr, 2
  85
  86         ; replace_min64(heap, heap_size, h3)
  87         mov     [heap + 1*8], h3
  88         mov     i, 1
  89         heapify heap, heap_size, i, child, h2, h3, tmp32, tmp2
  90
  91         cmp     heap_size, 1
  92         ja      .main_loop
  93
  94         mov     h1, [heap + 1*8]
  95         mov     [heap + node_ptr*8], h1 %+ w
  96
  97         pop     r12
  98 %ifidn __OUTPUT_FORMAT__, win64
  99         pop     rdi
 100         pop     rsi
 101 %endif
 102         ret
 103
 104 align 32
 105         global  build_heap
 106 build_heap:
 107 %ifidn __OUTPUT_FORMAT__, win64
 108         push    rsi
 109         push    rdi
 110 %endif
 111         push    r12
 112         mov     qword [heap + heap_size*8 + 8], -1
 113         mov     i, heap_size
 114         shr     i, 1
 115 .loop:
 116         mov     h1, i
 117         heapify heap, heap_size, h1, child, h2, h3, tmp32, tmp2
 118         dec     i
 119         jnz     .loop
 120
 121         pop     r12
 122 %ifidn __OUTPUT_FORMAT__, win64
 123         pop     rdi
 124         pop     rsi
 125 %endif
 126         ret