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

   1 ; returns modified node_ptr
   2 ; uint32_t proc_heap(uint64_t *heap, uint32_t  heap_size);
   3
   4 %include "reg_sizes.asm"
   5 %include "heap_macros.asm"
   6
   7 %ifidn __OUTPUT_FORMAT__, win64
   8 %define heap            rcx     ; pointer, 64-bit
   9 %define heap_size       rdx
  10 %define arg3            r8
  11 %define child           rsi
  12 %define tmp32           rdi
  13 %else
  14 %define heap            rdi
  15 %define heap_size       rsi
  16 %define arg3            rdx
  17 %define child           rcx
  18 %define tmp32           rdx
  19 %endif
  20
  21 %define node_ptr        rax
  22 %define h1              r8
  23 %define h2              r9
  24 %define h3              r10
  25 %define i               r11
  26 %define tmp2            r12
  27
  28         global build_huff_tree
  29 build_huff_tree:
  30 %ifidn __OUTPUT_FORMAT__, win64
  31         push    rsi
  32         push    rdi
  33 %endif
  34         push    r12
  35
  36         mov     node_ptr, arg3
  37 .main_loop:
  38         ; REMOVE_MIN64(heap, heap_size, h1);
  39         mov     h2, [heap + heap_size*8]
  40         mov     h1, [heap + 1*8]
  41         mov     qword [heap + heap_size*8], -1
  42         dec     heap_size
  43         mov     [heap + 1*8], h2
  44
  45         mov     i, 1
  46         heapify heap, heap_size, i, child, h2, h3, tmp32, tmp2
  47
  48         mov     h2, [heap + 1*8]
  49         lea     h3, [h1 + h2]
  50         mov     [heap + node_ptr*8], h1 %+ w
  51         mov     [heap + node_ptr*8 - 8], h2 %+ w
  52
  53         and     h3, ~0xffff
  54         or      h3, node_ptr
  55         sub     node_ptr, 2
  56
  57         ; replace_min64(heap, heap_size, h3)
  58         mov     [heap + 1*8], h3
  59         mov     i, 1
  60         heapify heap, heap_size, i, child, h2, h3, tmp32, tmp2
  61
  62         cmp     heap_size, 1
  63         ja      .main_loop
  64
  65         mov     h1, [heap + 1*8]
  66         mov     [heap + node_ptr*8], h1 %+ w
  67
  68         pop     r12
  69 %ifidn __OUTPUT_FORMAT__, win64
  70         pop     rdi
  71         pop     rsi
  72 %endif
  73         ret
  74
  75 align 32
  76         global  build_heap
  77 build_heap:
  78 %ifidn __OUTPUT_FORMAT__, win64
  79         push    rsi
  80         push    rdi
  81 %endif
  82         push    r12
  83         mov     qword [heap + heap_size*8 + 8], -1
  84         mov     i, heap_size
  85         shr     i, 1
  86 .loop:
  87         mov     h1, i
  88         heapify heap, heap_size, h1, child, h2, h3, tmp32, tmp2
  89         dec     i
  90         jnz     .loop
  91
  92         pop     r12
  93 %ifidn __OUTPUT_FORMAT__, win64
  94         pop     rdi
  95         pop     rsi
  96 %endif
  97         ret