[apple/xnu.git] / osfmk / x86_64 / 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 x86_64 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 x86_64 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/30/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

	.text

	.globl _WKdm_decompress_new
_WKdm_decompress_new:

	// save registers, and allocate stack memory for local variables

	pushq	%rbp
	movq	%rsp, %rbp
	pushq	%r12
	pushq	%r13
	pushq	%rbx

	subq	$(64+8+16), %rsp

    movl    0(%rdi), %eax               // read the 1st word from the header
    cmpl    MZV_MAGIC, %eax             // is the alternate packer used (i.e. is MZV page)?
    jne     L_default_decompressor      // default decompressor was used

                                        // Mostly Zero Page Handling...
                                        // {
    movq    $0, %rax
1:                                      // Zero out the entire page
    movq    $0, 0(%rsi, %rax)
    movq    $0, 8(%rsi, %rax)
    movq    $0, 16(%rsi, %rax)
    movq    $0, 24(%rsi, %rax)
    movq    $0, 32(%rsi, %rax)
    movq    $0, 40(%rsi, %rax)
    movq    $0, 48(%rsi, %rax)
    movq    $0, 56(%rsi, %rax)
    addq    $64, %rax
    cmpq    $4096, %rax
    jne     1b

    movq    $4, %r12                    // current byte position in src to read from
2:
    movl    0(%rdi, %r12), %eax         // get the word
    movzwq  4(%rdi, %r12), %rdx         // get the index
    movl    %eax, 0(%rsi, %rdx)         // store non-0 word in the destination buffer
    addq    $6, %r12                    // 6 more bytes processed
    cmpl    %ecx, %r12d                 // finished processing all the bytes?
    jne     2b
    jmp     L_done
                                        // }

L_default_decompressor:

	movq	%rsi, %r12					// dest_buf
	movq	%rdx, %r13					// scratch_buf

	// PRELOAD_DICTONARY; dictionary starting address : starting address 0(%rsp)
    // NOTE: ALL THE DICTIONARY VALUES MUST BE INITIALIZED TO ZERO TO MIRROR THE COMPRESSOR
#if 1
	movl	$0, 0(%rsp)
	movl	$0, 4(%rsp)
	movl	$0, 8(%rsp)
	movl	$0, 12(%rsp)
	movl	$0, 16(%rsp)
	movl	$0, 20(%rsp)
	movl	$0, 24(%rsp)
	movl	$0, 28(%rsp)
	movl	$0, 32(%rsp)
	movl	$0, 36(%rsp)
	movl	$0, 40(%rsp)
	movl	$0, 44(%rsp)
	movl	$0, 48(%rsp)
	movl	$0, 52(%rsp)
	movl	$0, 56(%rsp)
	movl	$0, 60(%rsp)
#else
	mov		$0x100000001, %rax
	mov		%rax, (%rsp)
	mov		%rax, 8(%rsp)
	mov		%rax, 16(%rsp)
	mov		%rax, 24(%rsp)
	mov		%rax, 32(%rsp)
	mov		%rax, 40(%rsp)
	mov		%rax, 48(%rsp)
	mov		%rax, 56(%rsp)
#endif

	// WK_unpack_2bits(TAGS_AREA_START(src_buf), TAGS_AREA_END(src_buf), tempTagsArray);

	leaq	268(%rdi), %r10				// TAGS_AREA_END
	leaq	12(%rdi), %rax				// TAGS_AREA_START 
	movq	%r13, %rsi					// tempTagsArray
	cmpq	%rax, %r10					// TAGS_AREA_END vs TAGS_AREA_START
	jbe		1f							// if TAGS_AREA_END <= TAGS_AREA_START, skip L_WK_unpack_2bits
	movq	%r13, %rcx					// next_word
	xorl	%r8d, %r8d					// i = 0
	mov		$(50529027<<32)+50529027, %r9
L_WK_unpack_2bits:
	movl	12(%rdi,%r8, 4), %eax
	movl	12(%rdi,%r8, 4), %edx
	shrl	$2, %eax
	shlq	$32, %rax
	orq		%rdx, %rax
	movq	%rax, %rdx
	shrq	$4, %rax
	andq	%r9, %rdx
	andq	%r9, %rax
	incq	%r8							// i++
	movq	%rdx, (%rcx)
	movq	%rax, 8(%rcx)
	addq	$16, %rcx					// next_tags += 16
	cmpq	$64, %r8					// i vs 64
	jne		L_WK_unpack_2bits			// repeat loop until i==64
1:


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

	mov		4(%rdi), %eax				// WKdm header qpos end
	leaq	(%rdi,%rax,4), %r9			// QPOS_AREA_END
	mov		0(%rdi), %eax				// WKdm header qpos start
	leaq	(%rdi,%rax,4), %r8			// QPOS_AREA_START
	leaq	1024(%r13), %rbx			// tempQPosArray
	cmpq	%r8, %r9					// QPOS_AREA_END vs QPOS_AREA_START
	jbe		1f							// if QPOS_AREA_END <= QPOS_AREA_START, skip L_WK_unpack_4bits
	leaq	8(%rbx), %rcx				// next_qpos

	mov		$(252645135<<32)+252645135, %r11
L_WK_unpack_4bits:
	movl	(%r8), %eax					// w = *next_word
	movl	%eax, %edx					// w
	shlq	$28, %rax
	orq		%rdx, %rax
	addq	$4, %r8						// next_word++
	andq	%r11, %rax
	movq	%rax, -8(%rcx)
	addq	$8, %rcx					// next_qpos+=8
	cmpq	%r8, %r9					// QPOS_AREA_END vs QPOS_AREA_START
	ja		L_WK_unpack_4bits			// repeat loop until QPOS_AREA_END <= QPOS_AREA_START


1:

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

	movl	8(%rdi), %eax				// LOW_BITS_AREA_END offset
	leaq	(%rdi,%rax,4), %rdi			// LOW_BITS_AREA_END
	leaq	2048(%r13), %r11			// tempLowBitsArray
	leaq	4094(%r13), %r13			// final tenbits addr
	sub		%r9, %rdi					// LOW_BITS_AREA_START vs LOW_BITS_AREA_END
	jle		1f							// if START>=END, skip L_WK_unpack_3_tenbits
	movq	%r11, %rcx					// next_low_bits
L_WK_unpack_3_tenbits:
	movl	(%r9), %eax					// w = *next_word, 0:c:b:a
	movl	$(1023<<10), %edx
	movl	$(1023<<20), %r8d
	andl	%eax, %edx					// b << 10
	andl	%eax, %r8d					// c << 20
	andq	$1023, %rax
	shll	$6, %edx
	shlq	$12, %r8
	orl		%edx, %eax
	orq		%r8, %rax
	cmp		%r13, %rcx
	je		2f
	mov		%rax, (%rcx)
	jmp		3f
2:	mov		%ax, (%rcx)
3:
	addq	$4, %r9						// next_word++
	addq	$6, %rcx					// next_low_bits += 3
	sub		$4, %rdi
	jg		L_WK_unpack_3_tenbits		// repeat loop if LOW_BITS_AREA_END > next_word
1:


	#define	next_qpos		%rbx
	#define	hash			%r8
	#define	tags_counter	%edi
	#define	dest_buf		%r12
	#define next_full_patt	%r10	

	leaq	_hashLookupTable_new(%rip), hash	// hash look up table
	movl	$1024, tags_counter				// tags_counter
	jmp		L_next

	.align 4,0x90
L_nonpartital:
	jl		L_ZERO_TAG
	cmpb	$2, -1(%rsi)
	je		L_MISS_TAG

L_EXACT_TAG:
	movzbl	(next_qpos), %eax				// qpos = *next_qpos
	incq	next_qpos						// next_qpos++
	decl	tags_counter					// tags_counter--
	movl	(%rsp,%rax,4), %eax				// w = dictionary[qpos]
	movl	%eax, -4(dest_buf)				// *dest_buf = w
	je		L_done

L_next:
	incq	%rsi							// next_tag++
	addq	$4, dest_buf
	cmpb	$1, -1(%rsi)
	jne		L_nonpartital

L_PARTIAL_TAG:
	movzbl	(next_qpos),%edx				// qpos = *next_qpos
	incq	next_qpos						// next_qpos++
	movl	(%rsp,%rdx,4), %eax				// read dictionary word
	andl	$-1024, %eax					// clear lower 10 bits
	or		(%r11), %ax						// pad the lower 10-bits from *next_low_bits
	addq	$2, %r11						// next_low_bits++
	decl	tags_counter					// tags_counter--
	movl	%eax, (%rsp,%rdx,4)				// *dict_location = newly formed word 
	movl	%eax, -4(dest_buf)				// *dest_buf = newly formed word
	jg		L_next							// repeat loop until next_tag==tag_area_end

L_done:

	// release stack memory, restore registers, and return

	addq	$(64+8+16), %rsp
	popq	%rbx
	popq	%r13
	popq	%r12
	leave
	ret

	.align 4,0x90
L_MISS_TAG:
	movl	(next_full_patt), %edx			// w = *next_full_patt
	movl	(next_full_patt), %eax			// w = *next_full_patt
	shrl	$10, %edx						// w>>10
	addq	$4, next_full_patt				// next_full_patt++
	movzbl	%dl, %edx						// 8-bit hash table index
	movl	%eax, -4(dest_buf)				// *dest_buf = word
	movzbl	(hash,%rdx),%edx				// qpos
	decl	tags_counter					// tags_counter--
	movl	%eax, (%rsp,%rdx)				// dictionary[qpos] = word
	jg		L_next							// repeat the loop
	jmp		L_done

	.align 4,0x90
L_ZERO_TAG:
	decl	tags_counter					// tags_counter--
	movl	$0, -4(dest_buf)					// *dest_buf = 0
	jg		L_next							// repeat the loop
	jmp		L_done
Commit	Line	Data
39236c6e A	1	/*
	2	* Copyright (c) 2000-2013 Apple Inc. All rights reserved.
	3	*
	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
	5	*
	6	* This file contains Original Code and/or Modifications of Original Code
	7	* as defined in and that are subject to the Apple Public Source License
	8	* Version 2.0 (the 'License'). You may not use this file except in
	9	* compliance with the License. The rights granted to you under the License
	10	* may not be used to create, or enable the creation or redistribution of,
	11	* unlawful or unlicensed copies of an Apple operating system, or to
	12	* circumvent, violate, or enable the circumvention or violation of, any
	13	* terms of an Apple operating system software license agreement.
	14	*
	15	* Please obtain a copy of the License at
	16	* http://www.opensource.apple.com/apsl/ and read it before using this file.
	17	*
	18	* The Original Code and all software distributed under the License are
	19	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	20	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	21	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	22	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	23	* Please see the License for the specific language governing rights and
	24	* limitations under the License.
	25	*
	26	* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
	27	*/
	28
	29	/*
	30	This file contains x86_64 hand optimized implementation of WKdm memory page decompressor.
	31
	32	void WKdm_decompress (WK_word* src_buf, WK_word* dest_buf, WK_word* scratch, __unused__ unsigned int words);
	33
	34	input :
	35	src_buf : address of input compressed data buffer
	36	dest_buf : address of output decompressed buffer
	37	scratch : a 16-byte aligned 4k bytes scratch memory provided by the caller
	38	words : this argument is not used in the implementation
	39
	40	output :
	41
	42	the input buffer is decompressed and the dest_buf is written with decompressed data.
	43
	44	Am algorithm description of the WKdm compress and bit stream format can be found in the WKdm Compress x86_64 assembly code WKdmCompress.s
	45
	46	The bit stream (*src_buf) consists of
	47	a. 12 bytes header
	48	b. 256 bytes for 1024 packed tags
	49	c. (varying number of) words for new words not matched to dictionary word.
	50	d. (varying number of) 32-bit words for packed 4-bit dict_indices (for class 1 and 3)
	51	e. (varying number of) 32-bit words for packed 10-bit low bits (for class 1)
	52
	53	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.
	54
	55	The decompressor 1st unpacking the bit stream component b/d/e into temorary buffers. Then it sequentially decodes the decompressed word as follows
	56
	57	for (i=0;i<1024;i++) {
	58	tag = *next_tag++
	59	switch (tag) {
	60	case 0 : *dest_buf++ = 0; break;
	61	case 1 : dict_word = dictionary[dict_index]; dictionary[dict_index++] = dest_buf++ = dict_word&0xfffffc00 \| LowBits++; break;
	62	case 2 : x = new_word++; k = (x>>10)&255; k = hashTable[k]; dictionary[k] = dest_buf++ = x; break;
	63	case 3 : dest_buf++ = dictionary[dict_index++]; break;
	64	}
65
66	cclee, 11/30/12
3e170ce0 A	67
	68	Added zero page, single value page, sparse page, early abort optimizations
	69	rsrini, 09/14/14
39236c6e A	70	*/
39236c6e A	71
3e170ce0 A	72	#define MZV_MAGIC $17185 // magic value used to identify MZV page encoding
3e170ce0 A	73
39236c6e A	74	.text
	75
	76	.globl _WKdm_decompress_new
	77	_WKdm_decompress_new:
	78
	79	// save registers, and allocate stack memory for local variables
	80
	81	pushq %rbp
	82	movq %rsp, %rbp
	83	pushq %r12
	84	pushq %r13
	85	pushq %rbx
	86
	87	subq $(64+8+16), %rsp
	88
3e170ce0 A	89	movl 0(%rdi), %eax // read the 1st word from the header
	90	cmpl MZV_MAGIC, %eax // is the alternate packer used (i.e. is MZV page)?
	91	jne L_default_decompressor // default decompressor was used
	92
	93	// Mostly Zero Page Handling...
	94	// {
	95	movq $0, %rax
	96	1: // Zero out the entire page
	97	movq $0, 0(%rsi, %rax)
	98	movq $0, 8(%rsi, %rax)
	99	movq $0, 16(%rsi, %rax)
	100	movq $0, 24(%rsi, %rax)
	101	movq $0, 32(%rsi, %rax)
	102	movq $0, 40(%rsi, %rax)
	103	movq $0, 48(%rsi, %rax)
	104	movq $0, 56(%rsi, %rax)
	105	addq $64, %rax
	106	cmpq $4096, %rax
	107	jne 1b
	108
	109	movq $4, %r12 // current byte position in src to read from
	110	2:
	111	movl 0(%rdi, %r12), %eax // get the word
	112	movzwq 4(%rdi, %r12), %rdx // get the index
	113	movl %eax, 0(%rsi, %rdx) // store non-0 word in the destination buffer
	114	addq $6, %r12 // 6 more bytes processed
	115	cmpl %ecx, %r12d // finished processing all the bytes?
	116	jne 2b
	117	jmp L_done
	118	// }
	119
	120	L_default_decompressor:
	121
39236c6e	122	movq %rsi, %r12 // dest_buf
3e170ce0	123	movq %rdx, %r13 // scratch_buf
39236c6e A	124
39236c6e A	125	// PRELOAD_DICTONARY; dictionary starting address : starting address 0(%rsp)
3e170ce0	126	// NOTE: ALL THE DICTIONARY VALUES MUST BE INITIALIZED TO ZERO TO MIRROR THE COMPRESSOR
39236c6e	127	#if 1
3e170ce0 A	128	movl $0, 0(%rsp)
	129	movl $0, 4(%rsp)
	130	movl $0, 8(%rsp)
	131	movl $0, 12(%rsp)
	132	movl $0, 16(%rsp)
	133	movl $0, 20(%rsp)
	134	movl $0, 24(%rsp)
	135	movl $0, 28(%rsp)
	136	movl $0, 32(%rsp)
	137	movl $0, 36(%rsp)
	138	movl $0, 40(%rsp)
	139	movl $0, 44(%rsp)
	140	movl $0, 48(%rsp)
	141	movl $0, 52(%rsp)
	142	movl $0, 56(%rsp)
	143	movl $0, 60(%rsp)
39236c6e A	144	#else
	145	mov $0x100000001, %rax
	146	mov %rax, (%rsp)
	147	mov %rax, 8(%rsp)
	148	mov %rax, 16(%rsp)
	149	mov %rax, 24(%rsp)
	150	mov %rax, 32(%rsp)
	151	mov %rax, 40(%rsp)
	152	mov %rax, 48(%rsp)
	153	mov %rax, 56(%rsp)
	154	#endif
	155
	156	// WK_unpack_2bits(TAGS_AREA_START(src_buf), TAGS_AREA_END(src_buf), tempTagsArray);
	157
	158	leaq 268(%rdi), %r10 // TAGS_AREA_END
	159	leaq 12(%rdi), %rax // TAGS_AREA_START
	160	movq %r13, %rsi // tempTagsArray
	161	cmpq %rax, %r10 // TAGS_AREA_END vs TAGS_AREA_START
	162	jbe 1f // if TAGS_AREA_END <= TAGS_AREA_START, skip L_WK_unpack_2bits
	163	movq %r13, %rcx // next_word
	164	xorl %r8d, %r8d // i = 0
	165	mov $(50529027<<32)+50529027, %r9
	166	L_WK_unpack_2bits:
	167	movl 12(%rdi,%r8, 4), %eax
	168	movl 12(%rdi,%r8, 4), %edx
	169	shrl $2, %eax
	170	shlq $32, %rax
	171	orq %rdx, %rax
	172	movq %rax, %rdx
	173	shrq $4, %rax
	174	andq %r9, %rdx
	175	andq %r9, %rax
	176	incq %r8 // i++
	177	movq %rdx, (%rcx)
	178	movq %rax, 8(%rcx)
	179	addq $16, %rcx // next_tags += 16
	180	cmpq $64, %r8 // i vs 64
	181	jne L_WK_unpack_2bits // repeat loop until i==64
	182	1:
	183
	184
	185	// WK_unpack_4bits(QPOS_AREA_START(src_buf), QPOS_AREA_END(src_buf), tempQPosArray);
	186
	187	mov 4(%rdi), %eax // WKdm header qpos end
	188	leaq (%rdi,%rax,4), %r9 // QPOS_AREA_END
	189	mov 0(%rdi), %eax // WKdm header qpos start
	190	leaq (%rdi,%rax,4), %r8 // QPOS_AREA_START
	191	leaq 1024(%r13), %rbx // tempQPosArray
	192	cmpq %r8, %r9 // QPOS_AREA_END vs QPOS_AREA_START
	193	jbe 1f // if QPOS_AREA_END <= QPOS_AREA_START, skip L_WK_unpack_4bits
	194	leaq 8(%rbx), %rcx // next_qpos
	195
	196	mov $(252645135<<32)+252645135, %r11
	197	L_WK_unpack_4bits:
	198	movl (%r8), %eax // w = *next_word
	199	movl %eax, %edx // w
	200	shlq $28, %rax
	201	orq %rdx, %rax
	202	addq $4, %r8 // next_word++
	203	andq %r11, %rax
	204	movq %rax, -8(%rcx)
	205	addq $8, %rcx // next_qpos+=8
	206	cmpq %r8, %r9 // QPOS_AREA_END vs QPOS_AREA_START
	207	ja L_WK_unpack_4bits // repeat loop until QPOS_AREA_END <= QPOS_AREA_START
208
209
210	1:
211
212	// WK_unpack_3_tenbits(LOW_BITS_AREA_START(src_buf), LOW_BITS_AREA_END(src_buf), tempLowBitsArray);
213
214	movl 8(%rdi), %eax // LOW_BITS_AREA_END offset
215	leaq (%rdi,%rax,4), %rdi // LOW_BITS_AREA_END
216	leaq 2048(%r13), %r11 // tempLowBitsArray
217	leaq 4094(%r13), %r13 // final tenbits addr
218	sub %r9, %rdi // LOW_BITS_AREA_START vs LOW_BITS_AREA_END
219	jle 1f // if START>=END, skip L_WK_unpack_3_tenbits
220	movq %r11, %rcx // next_low_bits
221	L_WK_unpack_3_tenbits:
222	movl (%r9), %eax // w = *next_word, 0:c:b:a
223	movl $(1023<<10), %edx
224	movl $(1023<<20), %r8d
225	andl %eax, %edx // b << 10
226	andl %eax, %r8d // c << 20
227	andq $1023, %rax
228	shll $6, %edx
229	shlq $12, %r8
230	orl %edx, %eax
231	orq %r8, %rax
232	cmp %r13, %rcx
233	je 2f
234	mov %rax, (%rcx)
235	jmp 3f
236	2: mov %ax, (%rcx)
237	3:
238	addq $4, %r9 // next_word++
239	addq $6, %rcx // next_low_bits += 3
240	sub $4, %rdi
241	jg L_WK_unpack_3_tenbits // repeat loop if LOW_BITS_AREA_END > next_word
242	1:
243
244
245	#define next_qpos %rbx
246	#define hash %r8
247	#define tags_counter %edi
248	#define dest_buf %r12
249	#define next_full_patt %r10
250
251	leaq _hashLookupTable_new(%rip), hash // hash look up table
252	movl $1024, tags_counter // tags_counter
253	jmp L_next
254
255	.align 4,0x90
256	L_nonpartital:
257	jl L_ZERO_TAG
258	cmpb $2, -1(%rsi)
259	je L_MISS_TAG
260
261	L_EXACT_TAG:
262	movzbl (next_qpos), %eax // qpos = *next_qpos
263	incq next_qpos // next_qpos++
264	decl tags_counter // tags_counter--
265	movl (%rsp,%rax,4), %eax // w = dictionary[qpos]
266	movl %eax, -4(dest_buf) // *dest_buf = w
267	je L_done
268
269	L_next:
270	incq %rsi // next_tag++
271	addq $4, dest_buf
272	cmpb $1, -1(%rsi)
273	jne L_nonpartital
274
275	L_PARTIAL_TAG:
276	movzbl (next_qpos),%edx // qpos = *next_qpos
277	incq next_qpos // next_qpos++
278	movl (%rsp,%rdx,4), %eax // read dictionary word
279	andl $-1024, %eax // clear lower 10 bits
280	or (%r11), %ax // pad the lower 10-bits from *next_low_bits
281	addq $2, %r11 // next_low_bits++
282	decl tags_counter // tags_counter--
283	movl %eax, (%rsp,%rdx,4) // *dict_location = newly formed word
284	movl %eax, -4(dest_buf) // *dest_buf = newly formed word
285	jg L_next // repeat loop until next_tag==tag_area_end
286
287	L_done:
288
289	// release stack memory, restore registers, and return
290
291	addq $(64+8+16), %rsp
292	popq %rbx
293	popq %r13
294	popq %r12
295	leave
296	ret
297
298	.align 4,0x90
299	L_MISS_TAG:
300	movl (next_full_patt), %edx // w = *next_full_patt
301	movl (next_full_patt), %eax // w = *next_full_patt
302	shrl $10, %edx // w>>10
303	addq $4, next_full_patt // next_full_patt++
304	movzbl %dl, %edx // 8-bit hash table index
305	movl %eax, -4(dest_buf) // *dest_buf = word
306	movzbl (hash,%rdx),%edx // qpos
307	decl tags_counter // tags_counter--
308	movl %eax, (%rsp,%rdx) // dictionary[qpos] = word
309	jg L_next // repeat the loop
310	jmp L_done
311
312	.align 4,0x90
313	L_ZERO_TAG:
314	decl tags_counter // tags_counter--
315	movl $0, -4(dest_buf) // *dest_buf = 0
316	jg L_next // repeat the loop
317	jmp L_done
318
319