/* * 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;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, 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]; 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, 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 = (x>>10)&255; k = hashTable[k]; dictionary[k] = *dest_buf++ = x; */ 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; *dest_buf++ = dictionary[*dict_index++]; */ 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