git.saurik.com Git - apple/xnu.git/blob - osfmk/arm64/lz4_encode

1 /*

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 #include <vm/lz4_assembly_select.h>

30 #include <vm/lz4_constants.h>

31 #include <arm64/asm.h>

32

33 #if LZ4_ENABLE_ASSEMBLY_ENCODE_ARM64

34

35 /* void lz4_encode_2gb(uint8_t ** dst_ptr,

36 size_t dst_size,

37 const uint8_t ** src_ptr,

38 const uint8_t * src_begin,

39 size_t src_size,

40 lz4_hash_entry_t hash_table[LZ4_COMPRESS_HASH_ENTRIES],

41 int skip_final_literals) */

42

43 .globl _lz4_encode_2gb

44

45 #define dst_ptr x0

46 #define dst_size x1

47 #define src_ptr x2

48 #define src_begin x3

49 #define src_size x4

50 #define hash_table x5

51 #define skip_final_literals x6

52

53 .text

54 .p2align 4

55 _lz4_encode_2gb:

56

57 // esteblish frame

58 ARM64_STACK_PROLOG

59 stp fp, lr, [sp, #-16]!

60 mov fp, sp

61

62 stp x19, x20, [sp, #-16]!

63 stp x21, x22, [sp, #-16]!

64 stp x23, x24, [sp, #-16]!

65 stp x25, x26, [sp, #-16]!

66 stp x27, x28, [sp, #-16]!

67

68 // constant registers

69 adr x7, L_constant

70 ldr w28, [x7, #4] // x28 = 0x80808081 (magic number to cmopute 1/255)

71 ldr w7, [x7] // x7 = LZ4_COMPRESS_HASH_MULTIPLY

72 mov x27, #-1 // x27 = 0xffffffffffffffff

73 dup.4s v1, w27 // q1 = {0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff}

74

75

76 // x9 - is current dst

77 // x10 - dst_end - safety_margin

78 ldr x9, [x0] // dst

79 add x10, x9, x1 // dst_end

80 sub x10, x10, #LZ4_GOFAST_SAFETY_MARGIN // dst_end - safety_margin

81 cmp x10, x9 // if dst_size < safety_margin abort

82 b.lt L_done

83

84 // x11 - is current src

85 // x12 - is src_end - safety margin

86 ldr x11, [x2] // src

87 add x12, x11, x4 // src_end

88 sub x12, x12, #LZ4_GOFAST_SAFETY_MARGIN // src_end - safety_margin

89 cmp x12, x11 // if src_size < safety_margin skip to trailing_literals

90 b.lt L_trailing_literals

91

92

93 // this block search for the next available match

94 // set match_begin to current src (which is also where last match ended)

95 L_search_next_available_match:

96 mov x13, x11 // match_begin = src

97 sub x14, x13, x3 // match_postion = match_begin - src_begin

98

99 // compute hash value for the next 5 "quads"

100 // hash distance need to be 0 < D < 0x10000

101

102 L_hash_match:

103 ldr x15, [x13] // match_first_4_bytes

104 umull x20, w7, w15 // match_bytes * LZ4_COMPRESS_HASH_MULTIPLY

105 lsr w20, w20, #LZ4_COMPRESS_HASH_SHIFT // use LZ4_COMPRESS_HASH_BITS MSbits as index

106 add x20, x5, x20, lsl #3 // hash_table_entry ptr (hash + 8*index)

107

108 ldp w19, w22, [x20] // read entry values (w19 - pos, w22 - 4 bytes at pos)

109 stp w14, w15, [x20] // write entry values (w14 - current pos, w15 - current 4 bytes)

110

111 add x26, x14, #1 // next_match pos

112 lsr x25, x15, #8 // next_match_first_4_bytes

113 umull x21, w7, w25 // match_bytes * LZ4_COMPRESS_HASH_MULTIPLY

114 lsr w21, w21, #LZ4_COMPRESS_HASH_SHIFT // use LZ4_COMPRESS_HASH_BITS MSbits as index

115 add x21, x5, x21, lsl #3 // hash_table_entry ptr (hash + 8*index)

116

117 ldp w23, w24, [x21] // read entry values (w23 - pos, w24 - 4 bytes at pos)

118 stp w26, w25, [x21] // write entry values (w26 - next pos, w25 - next 4 bytes)

119

120 cmp w15, w22

121 b.ne L_try_next_match_0 // compare the 4 bytes to see if there is a match

122 sub w19, w14, w19 // x19 - match_dist (current_pos - match_pos)

123 cmp w19, #0x10000

124 ccmp w19, #0, #0xf, lo

125 b.eq L_try_next_match_0 // verify the 0 < dist < 0x10000

126 b L_found_valid_match

127

128 L_try_next_match_0:

129 add x13, x13, #1

130 add x14, x14, #1

131

132 add x26, x14, #1 // next_match pos

133 lsr x15, x15, #16 // next_match_first_4_bytes

134 umull x20, w7, w15 // match_bytes * LZ4_COMPRESS_HASH_MULTIPLY

135 lsr w20, w20, #LZ4_COMPRESS_HASH_SHIFT // use LZ4_COMPRESS_HASH_BITS MSbits as index

136 add x20, x5, x20, lsl #3 // hash_table_entry ptr (hash + 8*index)

137

138 ldp w21, w22, [x20] // read entry values (w19 - pos, w22 - 4 bytes at pos)

139 stp w26, w15, [x20] // write entry values (w14 - current pos, w15 - current 4 bytes)

140

141 cmp w25, w24

142 b.ne L_try_next_match_1 // compare the 4 bytes to see if there is a match

143 sub w19, w14, w23 // x19 - match_dist (current_pos - match_pos)

144 cmp w19, #0x10000

145 ccmp w19, #0, #0xf, lo

146 b.eq L_try_next_match_1 // verify the 0 < dist < 0x10000

147 b L_found_valid_match

148

149 L_try_next_match_1:

150 add x13, x13, #1

151 add x14, x14, #1

152

153 add x26, x14, #1 // next_match pos

154 lsr x25, x15, #8 // next_match_first_4_bytes

155 umull x20, w7, w25 // match_bytes * LZ4_COMPRESS_HASH_MULTIPLY

156 lsr w20, w20, #LZ4_COMPRESS_HASH_SHIFT // use LZ4_COMPRESS_HASH_BITS MSbits as index

157 add x20, x5, x20, lsl #3 // hash_table_entry ptr (hash + 8*index)

158

159 ldp w23, w24, [x20] // read entry values (w23 - pos, w24 - 4 bytes at pos)

160 stp w26, w25, [x20] // write entry values (w26 - next pos, w25 - next 4 bytes)

161

162 cmp w15, w22

163 b.ne L_try_next_match_2 // compare the 4 bytes to see if there is a match

164 sub w19, w14, w21 // x19 - match_dist (current_pos - match_pos)

165 cmp w19, #0x10000

166 ccmp w19, #0, #0xf, lo

167 b.eq L_try_next_match_2 // verify the 0 < dist < 0x10000

168 b L_found_valid_match

169

170 L_try_next_match_2:

171 add x13, x13, #1

172 add x14, x14, #1

173

174 add x26, x14, #1 // next_match pos

175 lsr x15, x15, #16 // next_match_first_4_bytes

176 umull x20, w7, w15 // match_bytes * LZ4_COMPRESS_HASH_MULTIPLY

177 lsr w20, w20, #LZ4_COMPRESS_HASH_SHIFT // use LZ4_COMPRESS_HASH_BITS MSbits as index

178 add x20, x5, x20, lsl #3 // hash_table_entry ptr (hash + 8*index)

179

180 ldp w21, w22, [x20] // read entry values (w19 - pos, w22 - 4 bytes at pos)

181 stp w26, w15, [x20] // write entry values (w14 - current pos, w15 - current 4 bytes)

182

183 cmp w25, w24

184 b.ne L_try_next_match_3 // compare the 4 bytes to see if there is a match

185 sub w19, w14, w23 // x19 - match_dist (current_pos - match_pos)

186 cmp w19, #0x10000

187 ccmp w19, #0, #0xf, lo

188 b.eq L_try_next_match_3 // verify the 0 < dist < 0x10000

189 b L_found_valid_match

190

191 L_try_next_match_3:

192 add x13, x13, #1

193 add x14, x14, #1

194

195 cmp w15, w22

196 b.ne L_try_next_matchs // compare the 4 bytes to see if there is a match

197 sub w19, w14, w21 // x19 - match_dist (current_pos - match_pos)

198 cmp w19, #0x10000

199 ccmp w19, #0, #0xf, lo

200 b.eq L_try_next_matchs // verify the 0 < dist < 0x10000

201 b L_found_valid_match

202

203 // this block exapnd the valid match as much as possible

204 // first it try to expand the match forward

205 // next it try to expand the match backword

206 L_found_valid_match:

207 add x20, x13, #4 // match_end = match_begin+4 (already confirmd the first 4 bytes)

208 sub x21, x20, x19 // ref_end = match_end - dist

209 L_found_valid_match_expand_forward_loop:

210 ldr x22, [x20], #8 // load match_current_8_bytes (safe to load becasue of safety margin)

211 ldr x23, [x21], #8 // load ref_current_8_bytes

212 cmp x22, x23

213 b.ne L_found_valid_match_expand_forward_partial

214 cmp x20, x12 // check if match_end reached src_end

215 b.lo L_found_valid_match_expand_forward_loop

216 b L_found_valid_match_expand_backward

217 L_found_valid_match_expand_forward_partial:

218 sub x20, x20, #8 // revert match_end by 8 and compute actual match of current 8 bytes

219 eor x22, x22, x23 // compare the bits using xor

220 rbit x22, x22 // revert the bits to use clz (the none equivalent bytes would have at least 1 set bit)

221 clz x22, x22 // after the revrse for every equal prefix byte clz would count 8

222 add x20, x20, x22, lsr #3 // add the actual number of matching bytes is (clz result)>>3

223 L_found_valid_match_expand_backward:

224 sub x15, x13, x19 // ref_begin = match_begin - dist

225 L_found_valid_match_expand_backward_loop:

226 cmp x13, x11 // check if match_begin reached src (previous match end)

227 ccmp x15, x3, #0xd, gt // check if ref_begin reached src_begin

228 b.le L_found_valid_match_emit_match

229 ldrb w22, [x13, #-1]! // load match_current_8_bytes (safe to load becasue of safety margin)

230 ldrb w23, [x15, #-1]! // load ref_current_8_bytes

231 cmp w22, w23

232 b.eq L_found_valid_match_expand_backward_loop

233 add x13, x13, #1 // revert x13, last compare didn't match

234

235 // this block write the match into dst

236 // it write the ML token [extra L tokens] [literals] <2byte dist> [extar M tokens]

237 // it update src & dst positions and progress to L_search_next_available_match

238 L_found_valid_match_emit_match:

239 sub x21, x20, x13 // match_length - match_end - match_begin

240 sub x21, x21, #4 // match_length - 4 (first 4 bytes are guaranteed)

241 sub x22, x13, x11 // literals_length = match_begin - src // compute

242 sub x26, x10, x9 // dst_remaining_space = dst_end - dst

243 sub x26, x26, x22 // dst_remaining_space -= literals_length

244 subs x26, x26, #3 // dst_remaining_space -= 2_dist_bytes + L/M_token

245 b.lo L_done // exit if dst isn't sufficent

246

247 and x23, x21, #0xf // store M 4 LSbits

248 add x23, x23, x22, lsl #4 // add L 4 LSbits

249 add x15, x9, #1 // tmp_dst = dst + 1

250 cmp x22, #15 // if L >= 15 need to write more L tokens

251 b.lo L_found_valid_match_copy_literals

252 orr x23, x23, #0xf0 // update L/M token to be 0xfM

253 sub x24, x22, #15 // reduce 15 from number_of_literals

254 sub x26, x26, #1 // check if there is space for the extra L token

255 b.lo L_done

256 cmp x24, #255 // check if need to compute number of 255 tokens

257 b.lo L_found_valid_match_skip_L_255_tokens

258 umull x25, w24, w28 // x25 - (literals_to_token * 1_DIV_255_magic_number)

259 lsr x25, x25, #39 // x25 - number_of_255_tokens = (literals_to_token * 1_DIV_255_magic_number)>>39

260 subs x26, x26, x25 // check if there is sufficent space for the 255_tokens

261 b.lo L_done

262 mov x13, #255

263 umsubl x24, w25, w13, x24 // x24 - value_of_remainder_token = literals_to_token - (number_of_255_tokens*255)

264 L_found_valid_match_L_255_tokens_loop:

265 str q1, [x15], #16 // store 16 255 tokens into dst_tmp. safe to store because dst has safety_margin

266 subs x25, x25, #16 // check if there are any 255 token left after current 16

267 b.hi L_found_valid_match_L_255_tokens_loop

268 add x15, x15, x25 // revert tmp_dst if written too many 255 tokens.

269 L_found_valid_match_skip_L_255_tokens:

270 strb w24, [x15], #1 // write last L token

271 L_found_valid_match_copy_literals:

272 ldr q0, [x11], #16 // load current 16 literals. (safe becasue src_end has safety margin)

273 str q0, [x15], #16 // store current 16 literals. (safe becasue dst_end has safety margin)

274 subs x22, x22, #16

275 b.gt L_found_valid_match_copy_literals

276 add x15, x15, x22 // revert tmp_dst if written too many literals

277 strh w19, [x15], #2 // store dist bytes

278 cmp x21, #15 // if M >= 15 need to write more M tokens

279 b.lo L_found_valid_match_finish_writing_match

280 orr x23, x23, #0xf // update L/M token to be 0xLf

281 sub x24, x21, #15 // reduce 15 from match_length

282 sub x26, x26, #1 // check if there is space for the extra M token

283 b.lo L_done

284 cmp x24, #255 // check if need to compute number of 255 tokens

285 b.lo L_found_valid_match_skip_M_255_tokens

286 umull x25, w24, w28 // x25 - (match_length * 1_DIV_255_magic_number)

287 lsr x25, x25, #39 // x25 - number_of_255_tokens = (match_length * 1_DIV_255_magic_number)>>39

288 subs x26, x26, x25 // check if there is sufficent space for the 255_tokens

289 b.lo L_done

290 mov x13, #255

291 umsubl x24, w25, w13, x24 // x24 - value_of_remainder_token = literals_to_token - (match_length*255)

292 L_found_valid_match_M_255_tokens_loop:

293 str q1, [x15], #16 // store 16 255 tokens into dst_tmp. safe to store because dst has safety_margin

294 subs x25, x25, #16 // check if there are any 255 token left after current 16

295 b.hi L_found_valid_match_M_255_tokens_loop

296 add x15, x15, x25 // revert tmp_dst if written too many 255 tokens.

297 L_found_valid_match_skip_M_255_tokens:

298 strb w24, [x15], #1 // write last M token

299 L_found_valid_match_finish_writing_match:

300 strb w23, [x9] // store first token of match in dst

301 mov x9, x15 // update dst to last postion written

302 mov x11, x20 // update src to match_end (last byte that was encoded)

303 cmp x11, x12 // check if src reached src_end

304 ccmp x9, x10, #9, lt // check if dst reached dst_end

305 b.ge L_trailing_literals

306 b L_search_next_available_match

307 // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

308 // attempted to hash three quad values from the end of each emited match

309 // this eneded up being slower and less compression (???)

310 // this block set match_begin and pos for next hash search and

311 // compute the hash values for the last 3 bytes of currently emited match

312 // only need to comute these hash becasue other "quads" were hashed when the original

313 // data was read.

314

315 L_try_next_matchs:

316 add x13, x13, #1 // move to next match

317 add x14, x14, #1 // update next match pos

318 cmp x13, x12 // check match_begin didn't reach src_end

319 b.lo L_hash_match

320

321 L_trailing_literals:

322 // unless skip_final_literals is set

323 // write the trailing bytes as literals

324 // traliing bytes include the whole src (with the safty margin)

325 // need to verify whole dst (withthe safty margin) has sufficent space

326

327 tst x6, x6

328 b.ne L_done // if skip_final_literals is set skip writing them

329

330 add x12, x12, #LZ4_GOFAST_SAFETY_MARGIN // add safety_margin

331 subs x13, x12, x11 // remaining_src

332 b.eq L_done // finish if there are 0 trailing literals

333

334 add x10, x10, #LZ4_GOFAST_SAFETY_MARGIN // add safety_margin

335 sub x14, x10, x9 // remaining dst (dst_end - dst)

336 sub x14, x14, #1 // 1 byte is needed at least to write literals token

337 subs x14, x14, x13 // finish if dst can't contain all remaining literals + 1 literals token

338 b.le L_done // (need to verify that it has room for literals tokens

339

340 cmp x13, #15

341 b.lt L_trailing_literals_store_less_than_15_literals

342 subs x14, x14, #1 // 1-extra byte is needed for literals tokens

343 b.mi L_done

344 mov w15, #0xf0

345 strb w15, [x9], #1 // write literals first token (Important !!! if 255 tokens exist but dst isn't sufficent need to revert dst by 1)

346 sub x15, x13, #15

347 cmp x15, #255

348 b.lo L_trailing_literals_no_255_tokens

349 umull x19, w15, w28 // x19 - (literals_to_token * 1_DIV_255_magic_number)

350 lsr x19, x19, #39 // x19 - number_of_255_tokens = (literals_to_token * 1_DIV_255_magic_number)>>39

351 subs x14, x14, x19

352 b.mi L_revert_x9_and_done

353 mov x26, #255

354 umsubl x15, w26, w19, x15 // x15 - value_of_remainder_token = literals_to_token - (number_of_255_tokens*255)

355 L_tariling_literals_write_16_255_tokens:

356 str q1, [x9], #16 // store 16 255 tokens each iteration (this is safe becasue there is space for 15 or more literals + remainder token)

357 subs x19, x19, #16

358 b.gt L_tariling_literals_write_16_255_tokens

359 add x9, x9, x19 // fixes dst to actual number of tokens (x19 might not be a mulitple of 16)

360 L_trailing_literals_no_255_tokens:

361 strb w15, [x9], #1 // store remainder_token

362 lsr x14, x13, #4 // check if there are more than 16 literals left to be written

363 tst x14, x14

364 b.eq L_trailing_literals_copy_less_than_16_literals

365 L_trailing_literals_copy_16_literals:

366 ldr q0, [x11], #16 // load current_16_literals

367 str q0, [ x9], #16 // *dst16++ = current_16_literals

368 subs x14, x14, #1

369 b.gt L_trailing_literals_copy_16_literals

370 cmp x11, x12

371 b.lo L_trailing_literals_copy_less_than_16_literals

372 b L_done

373

374 L_trailing_literals_store_less_than_15_literals:

375 lsl x14, x13, #4 // literals_only_token is 0xL0 (where L is 4 bits)

376 strb w14, [x9], #1 // *dst++ = literals_only_token

377 L_trailing_literals_copy_less_than_16_literals:

378 ldrb w13, [x11], #1 // load current_literal

379 strb w13, [ x9], #1 // *dst++ = current_literal

380 cmp x11, x12

381 b.lo L_trailing_literals_copy_less_than_16_literals

382

383 // this block upadte dst & src pointers and remove frame

384 L_done:

385 str x9, [x0]

386 str x11, [x2]

387

388 ldp x27, x28, [sp], #16

389 ldp x25, x26, [sp], #16

390 ldp x23, x24, [sp], #16

391 ldp x21, x22, [sp], #16

392 ldp x19, x20, [sp], #16

393

394 // clear frame

395 ldp fp, lr, [sp], #16

396 ARM64_STACK_EPILOG

397

398 L_revert_x9_and_done:

399 sub x9, x9, #1

400 b L_done

401

402 .p2align 2

403 L_constant:

404 .long LZ4_COMPRESS_HASH_MULTIPLY

405 .long 0x80808081

406

407 #endif

408