xnu-4570.71.2.tar.gz

[apple/xnu.git] / osfmk / arm / WKdmDecompress_new.s

/*
 * Copyright (c) 2000-2013 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 * 
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */

/*
 This file contains armv7 hand optimized implementation of WKdm memory page decompressor. 

	void WKdm_decompress (WK_word* src_buf, WK_word* dest_buf, WK_word* scratch, __unused__ unsigned int words);

	input :
		src_buf : address of input compressed data buffer
		dest_buf : address of output decompressed buffer 
		scratch : a 16-byte aligned 4k bytes scratch memory provided by the caller
		words : this argument is not used in the implementation

	output :

		the input buffer is decompressed and the dest_buf is written with decompressed data.

	Am algorithm description of the WKdm compress and bit stream format can be found in the WKdm Compress armv7 assembly code WKdmCompress.s

	The bit stream (*src_buf) consists of 
		a. 12 bytes header
		b. 256 bytes for 1024 packed tags
		c. (varying number of) words for new words not matched to dictionary word. 
		d. (varying number of) 32-bit words for packed 4-bit dict_indices (for class 1 and 3)
		e. (varying number of) 32-bit words for packed 10-bit low bits (for class 1)

	where the header (of 3 words) specifies the ending boundaries (in 32-bit words) from the start of the bit stream of c,d,e, respectively.

	The decompressor 1st unpacking the bit stream component b/d/e into temorary buffers. Then it sequentially decodes the decompressed word as follows

		for (i=0;i<1024;i++) {
			tag = *next_tag++
			switch (tag) {
				case 0 : *dest_buf++ = 0; break;
				case 1 : dict_word = dictionary[*dict_index]; dictionary[*dict_index++] = *dest_buf++ = dict_word&0xfffffc00 | *LowBits++; break;
				case 2 : x = *new_word++; k = (x>>10)&255; k = hashTable[k]; dictionary[k] = *dest_buf++ = x; break;
				case 3 : *dest_buf++ = dictionary[*dict_index++];  break;
			}
 
 	cclee, 11/9/12

    Added zero page, single value page, sparse page, early abort optimizations
    rsrini, 09/14/14

*/

    #define MZV_MAGIC           17185      // magic value used to identify MZV page encoding

	#define	ZERO				0
	#define	PARTIAL_MATCH		1
	#define	MISS_TAG			2
	#define	MATCH				3

	.text
	.syntax unified
	.align	4

	// void WKdm_decompress (WK_word* src_buf, WK_word* dest_buf, WK_word* scratch, unsigned int bytes);

	.globl _WKdm_decompress_new
_WKdm_decompress_new:

	/*
			--------   symbolizing registers --------
			the armv7 code was ported from x86_64 so we name some registers that are used as temp variables with x86_64 register names. 
	*/

	#define	src_buf			r0
	#define	dest_buf		r1
	#define	scratch			r2
	#define	eax				r3
	#define	ebx				r4
	#define	hashTable		r4
	#define	ecx				r5
	#define	edx				r6
    #define n_bytes         r8
	#define	next_tag		r12
	#define	tags_counter	lr
	#define	dictionary		sp
	#define	v0		q0
	#define	v1		q1
	#define	v2		q2
	#define	v3		q3
	#define	v4		q4
	#define	v5		q5

	// and scratch memory for local variables

    // [sp,#0] : dictionary
    // [scratch,#0] : tempTagsArray		was 64
    // [scratch,#1024] : tempQPosArray  was 1088
    // [scratch,#2048] : tempLowBitsArray was 2112

	push	{r7, lr}
	mov		r7, sp
	push	{r4-r6,r8-r11}
#if KERNEL
	sub		ecx, sp, #96
	sub		sp, sp, #96
	vst1.64	{q0,q1},[ecx]!
	vst1.64	{q2,q3},[ecx]!
	vst1.64	{q4,q5},[ecx]!
#endif
	sub		sp, sp, #64			// allocate for dictionary

    mov     n_bytes, r3                         // save the n_bytes passed as function args
    ldr     eax, [src_buf]                      // read the 1st word from the header
    mov     ecx, #MZV_MAGIC
    cmp     eax, ecx                            // is the alternate packer used (i.e. is MZV page)?
    bne     L_default_decompressor              // default decompressor was used

                                                // Mostly Zero Page Handling...
                                                // {
    add     src_buf, src_buf, 4                 // skip the header
    mov     eax, dest_buf
    mov     ecx, #4096                          // number of bytes to zero out
    mov     r9, #0
    mov     r10, #0
    mov     r11, #0
    mov     r12, #0
1:
    subs    ecx, ecx, #64
    stmia   eax!, {r9-r12}
    stmia   eax!, {r9-r12}
    stmia   eax!, {r9-r12}
    stmia   eax!, {r9-r12}
    bne     1b

    mov     r12, #4                             // current byte position in src to read from
2:
    ldr     eax, [src_buf], #4                  // get the word
    ldrh    edx, [src_buf], #2                  // get the index
    str     eax, [dest_buf, edx]                // store non-0 word in the destination buffer
    add     r12, r12, #6                        // 6 more bytes processed
    cmp     r12, n_bytes                        // finished processing all the bytes?
    bne     2b
    b       L_done
                                                // }

L_default_decompressor:
	
    /*
			---------------------- set up registers and PRELOAD_DICTIONARY ---------------------------------
	*/
    // NOTE: ALL THE DICTIONARY VALUES MUST BE INITIALIZED TO ZERO TO MIRROR THE COMPRESSOR
	vmov.i32	q0, #0
	mov		r8, sp
	adr		ebx, _table_2bits
    vst1.64	{q0}, [r8]!
	add		r10, src_buf, #268			// TAGS_AREA_END
    vst1.64	{q0}, [r8]!
	add		eax, src_buf, #12			// TAGS_AREA_START	
    vst1.64	{q0}, [r8]!
	mov		ecx, scratch				// tempTagsArray
    vst1.64	{q0}, [r8]!
	vld1.64	{q0,q1},[ebx,:128]


	// WK_unpack_2bits(TAGS_AREA_START(src_buf), TAGS_AREA_END(src_buf), tempTagsArray);
/*
	unpacking 16 2-bit tags (from a 32-bit word) into 16 bytes
    for arm64, this can be done by
		1. read the input 32-bit word into GPR w
    	2. duplicate GPR into 4 elements in a vector register v0
    	3. ushl.4s vd, v0, vshift   where vshift = {0, -2, -4, -6}
    	4. and.4s  vd, vd, vmask    where vmask = 0x03030303030303030303030303030303
*/

L_WK_unpack_2bits:
	vld1.64	{v5}, [eax]!				// read 4 32-bit words for 64 2-bit tags
	vdup.32	v2, d10[0]					// duplicate to 4 elements
	vdup.32	v3, d10[1]					// duplicate to 4 elements
	vdup.32	v4, d11[0]					// duplicate to 4 elements
	vdup.32	v5, d11[1]					// duplicate to 4 elements
	vshl.u32	v2, v2, v0				// v0 = {0, -2, -4, -6}
	vshl.u32	v3, v3, v0				// v0 = {0, -2, -4, -6}
	vshl.u32	v4, v4, v0				// v0 = {0, -2, -4, -6}
	vshl.u32	v5, v5, v0				// v0 = {0, -2, -4, -6}
	vand	v2, v2, v1					// v1 = {3,3,...,3}
	vand	v3, v3, v1					// v1 = {3,3,...,3}
	vand	v4, v4, v1					// v1 = {3,3,...,3}
	vand	v5, v5, v1					// v1 = {3,3,...,3}
	vst1.64	{v2,v3}, [ecx,:128]!		// write 64 tags into tempTagsArray
	cmp		r10, eax					// TAGS_AREA_END vs TAGS_AREA_START
	vst1.64	{v4,v5}, [ecx,:128]!		// write 64 tags into tempTagsArray
	bhi	L_WK_unpack_2bits				// if not reach TAGS_AREA_END, repeat L_WK_unpack_2bits


	// WK_unpack_4bits(QPOS_AREA_START(src_buf), QPOS_AREA_END(src_buf), tempQPosArray);

	ldm		src_buf, {r8,r9}			// WKdm header qpos start and end
	adr		ebx, _table_4bits
	subs	r12, r9, r8					// r12 = (QPOS_AREA_END - QPOS_AREA_START)/4
	add		r8, src_buf, r8, lsl #2		// QPOS_AREA_START
	add		r9, src_buf, r9, lsl #2		// QPOS_AREA_END
	bls		1f							// if QPOS_AREA_END <= QPOS_AREA_START, skip L_WK_unpack_4bits
	add		ecx, scratch, #1024			// tempQPosArray
	vld1.64	{v0,v1},[ebx,:128]

	subs	r12, r12, #1	
	bls		2f							// do loop of 2 only if w14 >= 5 
L_WK_unpack_4bits:
	vld1.64	{d4}, [r8]!					// read a 32-bit word for 8 4-bit positions 
	subs	r12, r12, #2
	vmov	d5, d4
	vzip.32	d4, d5
	vshl.u32	v2, v2, v0				// v0 = {0, -4, 0, -4}
	vand	v2, v2, v1					// v1 = {15,15,...,15} 
	vst1.64	{q2}, [ecx,:128]!
	bhi		L_WK_unpack_4bits	
2:
	adds	r12, r12, #1	
	ble	1f

	ldr		r12, [r8], #4				// read a 32-bit word for 8 4-bit positions 
	vdup.32	d4, r12						// duplicate to 2 elements
	vshl.u32	v2, v2, v0				// v0 = {0, -4}
	vand	v2, v2, v1					// v1 = {15,15,...,15} 
	vst1.64	{d4}, [ecx,:64]!			// write 16 tags into tempTagsArray

1:

	// WK_unpack_3_tenbits(LOW_BITS_AREA_START(src_buf), LOW_BITS_AREA_END(src_buf), tempLowBitsArray);

	ldr		eax, [src_buf,#8]			// LOW_BITS_AREA_END offset
	add		r8, src_buf, eax, lsl #2	// LOW_BITS_AREA_END
	cmp		r8, r9						// LOW_BITS_AREA_START vs LOW_BITS_AREA_END
	add		ecx, scratch, #2048			// tempLowBitsArray 
	add		edx, scratch, #4096			// last tenbits
	bls		1f							// if START>=END, skip L_WK_unpack_3_tenbits

	adr		ebx, _table_10bits
	vld1.64	{v0,v1},[ebx,:128]

	mov		r11, #0x03ff
L_WK_unpack_3_tenbits:
	ldr		r12, [r9], #4				// read a 32-bit word for 3 low 10-bits
	and		lr, r11, r12
	strh	lr, [ecx], #2
	cmp		ecx, edx
	and		lr, r11, r12, lsr #10
	beq		1f
	strh	lr, [ecx], #2
	and		lr, r11, r12, lsr #20
	strh	lr, [ecx], #2

	cmp		r8, r9						// LOW_BITS_AREA_START vs LOW_BITS_AREA_END
	bhi		L_WK_unpack_3_tenbits		// repeat loop if LOW_BITS_AREA_END > next_word
 
1:
	/*
		set up before going to the main decompress loop
	*/

	mov		next_tag, scratch			// tempTagsArray
	add		r8, scratch, #1024			// next_qpos
	add		r11, scratch, #2048			// tempLowBitsArray 
#if defined(KERNEL) && !SLIDABLE
    adr     hashTable, L_table
    ldr     hashTable, [hashTable]
#else
    ldr     hashTable, L_table
L_table0:
    ldr     hashTable, [pc, hashTable]
#endif
	mov		tags_counter, #1024			// tags_counter

	b		L_next

	.align 4,0x90
L_ZERO_TAG:
	/*
		we can only get here if w9 = 0, meaning this is a zero tag
		*dest_buf++ = 0;	
	*/
	subs	tags_counter,tags_counter,#1	// tags_counter--
	str		r9, [dest_buf], #4				// *dest_buf++ = 0
	ble		L_done							// if next_tag >= tag_area_end, we're done

	/* WKdm decompress main loop */
L_next:
	ldrb	r9, [next_tag], #1				// new tag
	cmp		r9, #0
	beq		L_ZERO_TAG 
	cmp		r9, #2							// partial match tag ?
	beq		L_MISS_TAG
	bgt		L_EXACT_TAG

L_PARTIAL_TAG:
	/*
			this is a partial match:
				dict_word = dictionary[*dict_index]; 
				dictionary[*dict_index++] = *dest_buf++ = dict_word&0xfffffc00 | *LowBits++; 
	*/
	ldrb	edx, [r8], #1					// qpos = *next_qpos++
	ldrh	ecx, [r11], #2					// lower 10-bits from *next_low_bits++
	ldr		eax, [dictionary, edx, lsl #2]	// read dictionary word
	subs	tags_counter,tags_counter,#1	// tags_counter--
	lsr		eax, eax, #10					// clear lower 10 bits
	orr		eax, ecx, eax, lsl #10			// pad the lower 10-bits from *next_low_bits
	str		eax, [dictionary,edx,lsl #2]	// *dict_location = newly formed word 
	str		eax, [dest_buf], #4				// *dest_buf++ = newly formed word
	bgt		L_next							// repeat loop until next_tag==tag_area_end

L_done:

	add		sp, sp, #64			// deallocate for dictionary

	// release stack memory, restore registers, and return
#if KERNEL
	vld1.64	{q0,q1},[sp]!
	vld1.64	{q2,q3},[sp]!
	vld1.64	{q4,q5},[sp]!
#endif
	pop		{r4-r6,r8-r11}
	pop		{r7,pc}

	.align 4,0x90
L_MISS_TAG:
	/*
		this is a dictionary miss.
			x = *new_word++; 
			k = (x>>10)&255; 
			k = hashTable[k]; 
			dictionary[k] = *dest_buf++ = x;
	*/
	subs	tags_counter,tags_counter,#1	// tags_counter--
	ldr		eax, [r10], #4					// w = *next_full_patt++
	lsr		edx, eax, #10					// w>>10
	str		eax, [dest_buf], #4				// *dest_buf++ = word
	and		edx, edx, #0x0ff				// 8-bit hash table index
	ldrb	edx, [ebx, edx]					// qpos
	str		eax, [dictionary,edx]			// dictionary[qpos] = word
	bgt		L_next							// repeat the loop
	b		L_done							// if next_tag >= tag_area_end, we're done

	.align 4,0x90

L_EXACT_TAG:
	/* 
			this is an exact match;
			*dest_buf++ = dictionary[*dict_index++];
	*/

	ldrb	eax, [r8], #1					// qpos = *next_qpos++
	subs	tags_counter,tags_counter,#1	// tags_counter--
	ldr		eax, [dictionary,eax,lsl #2]	// w = dictionary[qpos]
	str		eax, [dest_buf], #4				// *dest_buf++ = w
	bgt		L_next							// repeat the loop
	b		L_done							// if next_tag >= tag_area_end, we're done


	.align 4

_table_2bits:
	.word	0
	.word	-2
	.word	-4
	.word	-6
	.word	0x03030303
	.word	0x03030303
	.word	0x03030303
	.word	0x03030303

_table_4bits:
	.word	0
	.word	-4
	.word	0
	.word	-4
	.word	0x0f0f0f0f
	.word	0x0f0f0f0f
	.word	0x0f0f0f0f
	.word	0x0f0f0f0f

_table_10bits:
	.word	0
	.word	-10
	.word	-20
	.word	0
	.word	1023
	.word	1023
	.word	1023
	.word	0


#if defined(KERNEL) && !SLIDABLE
    .align  2
L_table:
    .long   _hashLookupTable_new
#else
    .align  2
L_table:
    .long   L_Tab$non_lazy_ptr-(L_table0+8)

     .section    __DATA,__nl_symbol_ptr,non_lazy_symbol_pointers
    .align  2
L_Tab$non_lazy_ptr:
    .indirect_symbol    _hashLookupTable_new
    .long   0
#endif