WKdmDecompress_16k.s [plain text]
/*
* Copyright (c) 2000-2014 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 arm64 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 : an 8-k bytes scratch mempro provided by the caller
words : this argument is used by the mostly-zero-value decoder
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 arm64 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) 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 switch (tag) {
case 0 : *dest_buf++ = 0 case 2 : x = *new_word++ }
cclee, Nov 9, '12
Added zero page, single value page, sparse page, early abort optimizations
rsrini, 09/14/14
*/
#define PAGES_SIZE_IN_KBYTES 16
#define MZV_MAGIC 17185 // magic value used to identify MZV page encoding
#ifndef PAGES_SIZE_IN_KBYTES
#define PAGES_SIZE_IN_KBYTES 4
#endif
#if !((PAGES_SIZE_IN_KBYTES==4) || (PAGES_SIZE_IN_KBYTES==16))
#error "Only PAGES_SIZE_IN_KBYTES = 4 or 16 is supported"
#endif
#define scale (PAGES_SIZE_IN_KBYTES/4)
.align 4
.text
/*
void WKdm_decompress (WK_word* src_buf, WK_word* dest_buf, WK_word* scratch, unsigned int bytes)
.globl _WKdm_decompress_16k
_WKdm_decompress_16k:
/*
-------- symbolizing registers --------
the arm64 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 x0
#define dest_buf x1
#define scratch x2
#define n_bytes x3
#define dictionary sp
#define rax x13
#define eax w13
#define rbx x4
#define ebx w4
#define rcx x5
#define ecx w5
#define rdx x6
#define edx w6
#define tags_counter x7
#define next_tag x12
#define r8 x8
#define r9 x9
#define r10 x10
#define r11 x11
#define r12 x12
/*
------ scratch memory for local variables ---------
[sp,#0] : dictionary
[scratch,#0] : tempTagsArray
[scratch,#1024] : tempQPosArray
[scratch,#2048] : tempLowBitsArray
*/
#if KERNEL
sub rax, sp, #96
sub sp, sp, #96
st1.4s {v0,v1,v2},[rax],#48
st1.4s {v3,v4,v5},[rax],#48
#endif
sub sp, sp, #64
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)?
b.ne L_default_decompressor // default decompressor was used
// Mostly Zero Page Handling...
// {
add src_buf, src_buf, 4 // skip the header
mov rax, dest_buf
mov rcx, #(PAGES_SIZE_IN_KBYTES*1024) // number of bytes to zero out
1:
dc zva, rax // zero 64 bytes. since dest_buf is a page, it will be 4096 or 16384 byte aligned
add rax, rax, #64
dc zva, rax
add rax, rax, #64
dc zva, rax
add rax, rax, #64
dc zva, rax
add rax, rax, #64
subs rcx, rcx, #256
b.ne 1b
mov r12, #4 // current byte position in src to read from
mov rdx, #0
2:
ldr eax, [src_buf], #4 // get the word
ldrh edx, [src_buf], #2 // get the index
str eax, [dest_buf, rdx] // 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?
b.ne 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
adrp rbx, _table_2bits@GOTPAGE
stp xzr, xzr, [dictionary, #0]
add r10, src_buf, #(12+256*scale) // TAGS_AREA_END
stp xzr, xzr, [dictionary, #16]
add rax, src_buf, #12 // TAGS_AREA_START
ldr rbx, [rbx, _table_2bits@GOTPAGEOFF]
stp xzr, xzr, [dictionary, #32]
mov rcx, scratch // tempTagsArray
stp xzr, xzr, [dictionary, #48]
ld1.4s {v0,v1},[rbx]
/*
------------------------------ unpacking bit stream ----------------------------------
*/
// 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:
ldr q5, [rax], #16 // read 4 32-bit words for 64 2-bit tags
dup.4s v2, v5[0] // duplicate to 4 elements
dup.4s v3, v5[1] // duplicate to 4 elements
dup.4s v4, v5[2] // duplicate to 4 elements
dup.4s v5, v5[3] // duplicate to 4 elements
ushl.4s v2, v2, v0 // v1 = {0, -2, -4, -6}
ushl.4s v3, v3, v0 // v1 = {0, -2, -4, -6}
ushl.4s v4, v4, v0 // v1 = {0, -2, -4, -6}
ushl.4s v5, v5, v0 // v1 = {0, -2, -4, -6}
and.16b v2, v2, v1 // v2 = {3,3,...,3}
and.16b v3, v3, v1 // v2 = {3,3,...,3}
and.16b v4, v4, v1 // v2 = {3,3,...,3}
and.16b v5, v5, v1 // v2 = {3,3,...,3}
cmp r10, rax // TAGS_AREA_END vs TAGS_AREA_START
st1.4s {v2,v3,v4,v5}, [rcx], #64 // write 64 tags into tempTagsArray
b.hi 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) ldp w8, w9, [src_buf] // WKdm header qpos start and end
adrp rbx, _table_4bits@GOTPAGE
subs x14, r9, r8 // x14 = (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
b.ls 1f // if QPOS_AREA_END <= QPOS_AREA_START, skip L_WK_unpack_4bits
ldr rbx, [rbx, _table_4bits@GOTPAGEOFF]
add rcx, scratch, #(1024*scale) // tempQPosArray
ld1.4s {v0,v1},[rbx]
subs w14, w14, #1
b.ls 2f // do loop of 2 only if w14 >= 5
L_WK_unpack_4bits:
ldr d2, [r8], #8 // read a 32-bit word for 8 4-bit positions
subs w14, w14, #2
zip1.4s v2, v2, v2
ushl.4s v2, v2, v0 // v1 = {0, -4, 0, -4}
and.16b v2, v2, v1 // v2 = {15,15,...,15}
str q2, [rcx], #16
b.hi L_WK_unpack_4bits
2:
adds w14, w14, #1
b.le 1f
ldr s3, [r8], #4 // read a 32-bit word for 8 4-bit positions
dup.2s v2, v3[0] // duplicate to 2 elements
ushl.2s v2, v2, v0 // v1 = {0, -4}
and.8b v2, v2, v1 // v2 = {15,15,...,15}
str d2, [rcx], #8 // 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, rax, lsl #2 // LOW_BITS_AREA_END
add rcx, scratch, #(2048*scale) // tempLowBitsArray
#if (scale==1)
add r11, scratch, #(4096*scale-2) // final tenbits for the rare case
#else
add r11, scratch, #(4096*scale) // final tenbits for the rare case
sub r11, r11, #2
#endif
subs r8, r8, r9 // LOW_BITS_AREA_START vs LOW_BITS_AREA_END
b.ls 1f // if START>=END, skip L_WK_unpack_3_tenbits
adrp rbx, _table_10bits@GOTPAGE
ldr rbx, [rbx, _table_10bits@GOTPAGEOFF]
ld1.4s {v0,v1,v2,v3},[rbx]
/*
a very rare case : 1024 tenbits, 1023 + 1 -> 341 + final 1 that is padded with 2 zeros
since the scratch memory is 4k (2k for this section), we need to pay attention to the last case
so we don't overwrite to the scratch memory
we 1st do a single 3_tenbits, followed by 2x_3_tenbits loop, and detect whether the last 3_tenbits
hits the raee case
*/
#if 1
subs r8, r8, #4 // pre-decrement by 8
ldr s4, [r9], #4 // read 32-bit words for 3 low 10-bits
zip1.4s v4, v4, v4 // bits 0-63 contain first triplet twice, bits 64-127 contain second triplet twice.
ushl.4s v5, v4, v0 // v0 = {6, 0, 6, 0}, places second element of triplets into bits 16-25 and 80-89.
ushl.4s v4, v4, v1 // v1 = {0, -20, 0, -20}, places third element of triplets into bits 32-41 and 96-105.
and.16b v5, v5, v2 // v2 = {0, 1023, 0, 0, 0, 1023, 0, 0}, isolate second element of triplets.
and.16b v4, v4, v3 // v3 = {1023, 0, 1023, 0, 1023, 0, 1023, 0}, isolate first and third elements of triplets
orr.16b v4, v4, v5 // combine data
str d4, [rcx], #6 // write 3 low 10-bits
b.eq 1f
#endif
subs r8, r8, #8 // pre-decrement by 8
b.lt L_WK_unpack_3_tenbits
L_WK_unpack_2x_3_tenbits:
ldr d4, [r9], #8 // read 2 32-bit words for a pair of 3 low 10-bits
zip1.4s v4, v4, v4 // bits 0-63 contain first triplet twice, bits 64-127 contain second triplet twice.
ushl.4s v5, v4, v0 // v0 = {6, 0, 6, 0}, places second element of triplets into bits 16-25 and 80-89.
ushl.4s v4, v4, v1 // v1 = {0, -20, 0, -20}, places third element of triplets into bits 32-41 and 96-105.
and.16b v5, v5, v2 // v2 = {0, 1023, 0, 0, 0, 1023, 0, 0}, isolate second element of triplets.
and.16b v4, v4, v3 // v3 = {1023, 0, 1023, 0, 1023, 0, 1023, 0}, isolate first and third elements of triplets
orr.16b v4, v4, v5 // combine data
ins v5.d[0], v4.d[1]
str d4, [rcx], #6 // write 3 low 10-bits
str d5, [rcx], #6 // write 3 low 10-bits
subs r8, r8, #8
b.ge L_WK_unpack_2x_3_tenbits // repeat loop if LOW_BITS_AREA_END > next_word
tst r8, #4
b.eq 1f
L_WK_unpack_3_tenbits:
ldr s4, [r9] // read 32-bit words for 3 low 10-bits
zip1.4s v4, v4, v4 // bits 0-63 contain first triplet twice, bits 64-127 contain second triplet twice.
ushl.4s v5, v4, v0 // v0 = {6, 0, 6, 0}, places second element of triplets into bits 16-25 and 80-89.
ushl.4s v4, v4, v1 // v1 = {0, -20, 0, -20}, places third element of triplets into bits 32-41 and 96-105.
and.16b v5, v5, v2 // v2 = {0, 1023, 0, 0, 0, 1023, 0, 0}, isolate second element of triplets.
and.16b v4, v4, v3 // v3 = {1023, 0, 1023, 0, 1023, 0, 1023, 0}, isolate first and third elements of triplets
orr.16b v4, v4, v5 // combine data
#if 0
str d4, [rcx] // write 3 low 10-bits
#else
cmp rcx, r11
b.eq 2f
str d4, [rcx] // write 3 low 10-bits
b 1f
2:
str h4, [rcx] // write final 1 low 10-bits
#endif
1:
/*
set up before going to the main decompress loop
*/
mov next_tag, scratch // tempTagsArray
add r8, scratch, #(1024*scale) // next_qpos
add r11, scratch, #(2048*scale) // tempLowBitsArray
adrp rbx, _hashLookupTable@GOTPAGE
mov tags_counter, #(1024*scale) // tag_area_end
ldr rbx, [rbx, _hashLookupTable@GOTPAGEOFF]
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 str w9, [dest_buf], #4 // *dest_buf++ = 0
subs tags_counter, tags_counter, #1 // next_tag vs tag_area_end
b.ls L_done // if next_tag >= tag_area_end, we're done
/* WKdm decompress main loop */
L_next:
ldrb w9, [next_tag], #1 // new tag
cbz w9, L_ZERO_TAG
cmp w9, #2 // partial match tag ?
b.eq L_MISS_TAG
b.gt L_EXACT_TAG
L_PARTIAL_TAG:
/*
this is a partial match:
dict_word = dictionary[*dict_index] */
ldrb edx, [r8], #1 // qpos = *next_qpos++
ldrh ecx, [r11], #2 // lower 10-bits from *next_low_bits++
ldr eax, [dictionary, rdx, lsl #2] // read dictionary word
bfm eax, ecx, #0, #9 // pad the lower 10-bits from *next_low_bits
str eax, [dictionary,rdx,lsl #2] // *dict_location = newly formed word
str eax, [dest_buf], #4 // *dest_buf++ = newly formed word
subs tags_counter, tags_counter, #1 // next_tag vs tag_area_end
b.gt L_next // repeat loop until next_tag==tag_area_end
L_done:
// release stack memory, restore registers, and return
add sp, sp, #64 // deallocate for dictionary
#if KERNEL
ld1.4s {v0,v1,v2},[sp],#48
ld1.4s {v3,v4,v5},[sp],#48
#endif
ret lr
.align 4,0x90
L_MISS_TAG:
/*
this is a dictionary miss.
x = *new_word++ k = hashTable[k] */
ldr eax, [r10], #4 // w = *next_full_patt++
ubfm edx, eax, #10, #17 // 8-bit hash table index
str eax, [dest_buf], #4 // *dest_buf++ = word
ldrb edx, [rbx, rdx] // qpos
str eax, [dictionary,rdx] // dictionary[qpos] = word
subs tags_counter, tags_counter, #1 // next_tag vs tag_area_end
b.gt 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 */
ldrb eax, [r8], #1 // qpos = *next_qpos++
ldr eax, [dictionary,rax,lsl #2] // w = dictionary[qpos]
str eax, [dest_buf], #4 // *dest_buf++ = w
subs tags_counter, tags_counter, #1 // next_tag vs tag_area_end
b.gt L_next // repeat the loop
b L_done // if next_tag >= tag_area_end, we're done