[ceph.git] / ceph / src / isa-l / igzip / proc_heap.asm

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;  Copyright(c) 2011-2018 Intel Corporation All rights reserved.
;
;  Redistribution and use in source and binary forms, with or without
;  modification, are permitted provided that the following conditions
;  are met:
;    * Redistributions of source code must retain the above copyright
;      notice, this list of conditions and the following disclaimer.
;    * Redistributions in binary form must reproduce the above copyright
;      notice, this list of conditions and the following disclaimer in
;      the documentation and/or other materials provided with the
;      distribution.
;    * Neither the name of Intel Corporation nor the names of its
;      contributors may be used to endorse or promote products derived
;      from this software without specific prior written permission.
;
;  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
;  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
;  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
;  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
;  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
;  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
;  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
;  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
;  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
;  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
;  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; returns modified node_ptr
; uint32_t proc_heap(uint64_t *heap, uint32_t  heap_size);

%include "reg_sizes.asm"
%include "heap_macros.asm"

%ifidn __OUTPUT_FORMAT__, win64
%define heap		rcx	; pointer, 64-bit
%define heap_size	rdx
%define	arg3		r8
%define child		rsi
%define tmp32		rdi
%else
%define heap		rdi
%define heap_size	rsi
%define	arg3		rdx
%define child		rcx
%define tmp32		rdx
%endif

%define node_ptr	rax
%define h1		r8
%define h2		r9
%define h3		r10
%define i		r11
%define tmp2		r12

[bits 64]
default rel
section .text

	global build_huff_tree
build_huff_tree:
	endbranch
%ifidn __OUTPUT_FORMAT__, win64
	push	rsi
	push	rdi
%endif
	push	r12

	mov	node_ptr, arg3
.main_loop:
	; REMOVE_MIN64(heap, heap_size, h1);
	mov	h2, [heap + heap_size*8]
	mov	h1, [heap + 1*8]
	mov	qword [heap + heap_size*8], -1
	dec	heap_size
	mov	[heap + 1*8], h2

	mov	i, 1
	heapify	heap, heap_size, i, child, h2, h3, tmp32, tmp2

	mov	h2, [heap + 1*8]
	lea	h3, [h1 + h2]
	mov	[heap + node_ptr*8], h1 %+ w
	mov	[heap + node_ptr*8 - 8], h2 %+ w

	and 	h3, ~0xffff
	or	h3, node_ptr
	sub	node_ptr, 2

	; replace_min64(heap, heap_size, h3)
	mov	[heap + 1*8], h3
	mov	i, 1
	heapify	heap, heap_size, i, child, h2, h3, tmp32, tmp2

	cmp	heap_size, 1
	ja	.main_loop

	mov	h1, [heap + 1*8]
	mov	[heap + node_ptr*8], h1 %+ w

	pop	r12
%ifidn __OUTPUT_FORMAT__, win64
	pop	rdi
	pop	rsi
%endif
	ret

align 32
	global	build_heap
build_heap:
	endbranch
%ifidn __OUTPUT_FORMAT__, win64
	push	rsi
	push	rdi
%endif
	push	r12
	mov	qword [heap + heap_size*8 + 8], -1
	mov	i, heap_size
	shr	i, 1
.loop:
	mov	h1, i
	heapify	heap, heap_size, h1, child, h2, h3, tmp32, tmp2
	dec	i
	jnz	.loop

	pop	r12
%ifidn __OUTPUT_FORMAT__, win64
	pop	rdi
	pop	rsi
%endif
	ret
Commit	Line	Data
f91f0fd5 TL	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
224ce89b WB	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
20effc67 TL	57	[bits 64]
	58	default rel
	59	section .text
	60
224ce89b WB	61	global build_huff_tree
224ce89b WB	62	build_huff_tree:
20effc67	63	endbranch
224ce89b WB	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
	109	align 32
	110	global build_heap
	111	build_heap:
20effc67	112	endbranch
224ce89b WB	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