summaryrefslogtreecommitdiffstats
path: root/src/isa-l/igzip/igzip_update_histogram.asm
blob: 4d91f7fbe22f8129059915b5fe4cb585d4669622 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
%include "options.asm"

%include "lz0a_const.asm"
%include "data_struct2.asm"
%include "bitbuf2.asm"
%include "huffman.asm"
%include "igzip_compare_types.asm"
%include "reg_sizes.asm"

%include "stdmac.asm"

extern rfc1951_lookup_table
_len_to_code_offset	equ	0

%define LAST_BYTES_COUNT	3 ; Bytes to prevent reading out of array bounds
%define LA_STATELESS	280	  ; Max number of bytes read in loop2 rounded up to 8 byte boundary
%define LIT_LEN 286
%define DIST_LEN 30
%define HIST_ELEM_SIZE	8

%ifdef DEBUG
%macro MARK 1
global %1
%1:
%endm
%else
%macro MARK 1
%endm
%endif

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
%define	file_start	rdi
%define file_length	rsi
%define	histogram	rdx
%define rfc_lookup	r9
%define	f_i		r10

%define	curr_data	rax

%define	tmp2		rcx

%define	dist		rbx
%define	dist_code2	rbx

%define	dist2		r12
%define	dist_code	r12

%define	len		rbp
%define	len_code	rbp
%define	hash3		rbp

%define	curr_data2	r8
%define	len2		r8
%define	tmp4		r8

%define	tmp1		r11

%define	tmp3		r13

%define	hash		r14

%define	hash2		r15

%define	xtmp0		xmm0
%define	xtmp1		xmm1
%define	xdata		xmm2

%define	ytmp0		ymm0
%define	ytmp1		ymm1

%if(ARCH == 01)
%define	vtmp0	xtmp0
%define	vtmp1	xtmp1
%define	V_LENGTH	16
%else
%define	vtmp0	ytmp0
%define	vtmp1	ytmp1
%define	V_LENGTH	32
%endif
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
_eob_count_offset   equ  0	 ; local variable (8 bytes)
f_end_i_mem_offset  equ  8
gpr_save_mem_offset equ 16       ; gpr save area (8*8 bytes)
xmm_save_mem_offset equ 16 + 8*8 ; xmm save area (4*16 bytes) (16 byte aligned)
stack_size          equ 2*8 + 8*8 + 4*16 + 8
;;; 8 because stack address is odd multiple of 8 after a function call and
;;; we want it aligned to 16 bytes

%ifidn __OUTPUT_FORMAT__, elf64
%define arg0	rdi
%define	arg1	rsi
%define arg2	rdx

%macro FUNC_SAVE 0
%ifdef ALIGN_STACK
	push	rbp
	mov	rbp, rsp
	sub	rsp, stack_size
	and	rsp, ~15
%else
	sub	rsp, stack_size
%endif

	mov [rsp + gpr_save_mem_offset + 0*8], rbx
	mov [rsp + gpr_save_mem_offset + 1*8], rbp
	mov [rsp + gpr_save_mem_offset + 2*8], r12
	mov [rsp + gpr_save_mem_offset + 3*8], r13
	mov [rsp + gpr_save_mem_offset + 4*8], r14
	mov [rsp + gpr_save_mem_offset + 5*8], r15
%endm

%macro FUNC_RESTORE 0
	mov	rbx, [rsp + gpr_save_mem_offset + 0*8]
	mov	rbp, [rsp + gpr_save_mem_offset + 1*8]
	mov	r12, [rsp + gpr_save_mem_offset + 2*8]
	mov	r13, [rsp + gpr_save_mem_offset + 3*8]
	mov	r14, [rsp + gpr_save_mem_offset + 4*8]
	mov	r15, [rsp + gpr_save_mem_offset + 5*8]

%ifndef ALIGN_STACK
	add	rsp, stack_size
%else
	mov	rsp, rbp
	pop	rbp
%endif
%endm
%endif

%ifidn __OUTPUT_FORMAT__, win64
%define arg0	rcx
%define	arg1	rdx
%define	arg2	r8

%macro FUNC_SAVE 0
%ifdef ALIGN_STACK
	push	rbp
	mov	rbp, rsp
	sub	rsp, stack_size
	and	rsp, ~15
%else
	sub	rsp, stack_size
%endif

	mov [rsp + gpr_save_mem_offset + 0*8], rbx
	mov [rsp + gpr_save_mem_offset + 1*8], rsi
	mov [rsp + gpr_save_mem_offset + 2*8], rdi
	mov [rsp + gpr_save_mem_offset + 3*8], rbp
	mov [rsp + gpr_save_mem_offset + 4*8], r12
	mov [rsp + gpr_save_mem_offset + 5*8], r13
	mov [rsp + gpr_save_mem_offset + 6*8], r14
	mov [rsp + gpr_save_mem_offset + 7*8], r15
%endm

%macro FUNC_RESTORE 0
	mov	rbx, [rsp + gpr_save_mem_offset + 0*8]
	mov	rsi, [rsp + gpr_save_mem_offset + 1*8]
	mov	rdi, [rsp + gpr_save_mem_offset + 2*8]
	mov	rbp, [rsp + gpr_save_mem_offset + 3*8]
	mov	r12, [rsp + gpr_save_mem_offset + 4*8]
	mov	r13, [rsp + gpr_save_mem_offset + 5*8]
	mov	r14, [rsp + gpr_save_mem_offset + 6*8]
	mov	r15, [rsp + gpr_save_mem_offset + 7*8]

%ifndef ALIGN_STACK
	add	rsp, stack_size
%else
	mov	rsp, rbp
	pop	rbp
%endif
%endm
%endif


_lit_len_offset	equ	0
_dist_offset	equ	(8 * LIT_LEN)
_hash_offset	equ	(_dist_offset + 8 * DIST_LEN)


%macro len_to_len_code 3
%define %%len_code	%1 	; Output
%define	%%len		%2	; Input
%define	%%rfc_lookup	%3
	movzx	%%len_code, byte [%%rfc_lookup + _len_to_code_offset + %%len]
	or	%%len_code, 0x100
%endm

;;; Clobbers rcx and dist
%macro	dist_to_dist_code 2
%define %%dist_code	%1	; Output code associated with dist
%define	%%dist_coded	%1d
%define	%%dist		%2d	; Input dist
	dec	%%dist
	mov	%%dist_coded, %%dist
	bsr	ecx, %%dist_coded
	dec	ecx
	SHRX	%%dist_code, %%dist_code, rcx
	lea	%%dist_coded, [%%dist_coded + 2*ecx]

	cmp	%%dist, 1
	cmovle	%%dist_coded, %%dist
%endm

;;; Clobbers rcx and dist
%macro	dist_to_dist_code2 2
%define	%%dist_code	%1	; Output code associated with dist
%define %%dist_coded	%1d
%define	%%dist		%2d	; Input -(dist - 1)
	neg	%%dist
	mov	%%dist_coded, %%dist
	bsr	ecx, %%dist_coded
	dec	ecx
	SHRX	%%dist_code, %%dist_code, rcx
	lea	%%dist_coded, [%%dist_coded + 2*ecx]

	cmp	%%dist, 1
	cmovle	%%dist_coded, %%dist
%endm

; void isal_update_histogram
global isal_update_histogram_ %+ ARCH
isal_update_histogram_ %+ ARCH %+ :
	FUNC_SAVE

%ifnidn	file_start, arg0
	mov	file_start, arg0
%endif
%ifnidn	file_length, arg1
	mov	file_length, arg1
%endif
%ifnidn	histogram, arg2
	mov	histogram, arg2
%endif
	mov	f_i, 0
	cmp	file_length, 0
	je	exit_ret	; If nothing to do then exit

	mov	tmp1, qword [histogram + _lit_len_offset + 8*256]
	inc	tmp1
	mov	[rsp + _eob_count_offset], tmp1

	lea	rfc_lookup, [rfc1951_lookup_table]

	;; Init hash_table
	PXOR	vtmp0, vtmp0, vtmp0
	mov	rcx, (IGZIP_HASH_SIZE - V_LENGTH)
init_hash_table:
	MOVDQU	[histogram + _hash_offset + 2 * rcx], vtmp0
	MOVDQU	[histogram + _hash_offset + 2 * (rcx + V_LENGTH / 2)], vtmp0
	sub	rcx, V_LENGTH
	jge	init_hash_table

	sub	file_length, LA_STATELESS
	cmp	file_length, 0
	jle	end_loop_2


	;; Load first literal into histogram
	mov	curr_data, [file_start + f_i]
	compute_hash	hash, curr_data
	and	hash %+ d, HASH_MASK
	mov	[histogram + _hash_offset + 2 * hash], f_i %+ w
	and	curr_data, 0xff
	inc	qword [histogram + _lit_len_offset + HIST_ELEM_SIZE * curr_data]
	inc	f_i

	;; Setup to begin loop 2
	MOVDQU	xdata, [file_start + f_i]
	mov	curr_data, [file_start + f_i]
	mov	curr_data2, curr_data
	compute_hash	hash, curr_data
	shr	curr_data2, 8
	compute_hash	hash2, curr_data2

	and	hash2 %+ d, HASH_MASK
	and	hash, HASH_MASK
loop2:
	xor	dist, dist
	xor	dist2, dist2
	xor	tmp3, tmp3

	lea	tmp1, [file_start + f_i]

	MOVQ	curr_data, xdata
	PSRLDQ	xdata, 1

	;; Load possible look back distances and update hash data
	mov	dist %+ w, f_i %+ w
	sub	dist, 1
	sub	dist %+ w, word [histogram + _hash_offset + 2 * hash]
	mov	[histogram + _hash_offset + 2 * hash], f_i %+ w

	add	f_i, 1

	mov	dist2 %+ w, f_i %+ w
	sub	dist2, 1
	sub	dist2 %+ w, word [histogram + _hash_offset + 2 * hash2]
	mov	[histogram + _hash_offset + 2 * hash2], f_i %+ w

	;; Start computing hashes to be used in either the next loop or
	;; for updating the hash if a match is found
	MOVQ	curr_data2, xdata
	MOVQ	tmp2, xdata
	shr	curr_data2, 8
	compute_hash	hash, curr_data2

	;; Check if look back distances are valid. Load a junk distance of 1
	;; if the look back distance is too long for speculative lookups.
	and	dist %+ d, (D-1)
	neg	dist

	and	dist2 %+ d, (D-1)
	neg	dist2

	shr	tmp2, 16
	compute_hash	hash2, tmp2

	;; Check for long len/dist matches (>7)
	mov	len, curr_data
	xor	len, [tmp1 + dist - 1]
	jz	compare_loop

	and	hash %+ d, HASH_MASK
	and	hash2 %+ d, HASH_MASK

	MOVQ	len2, xdata
	xor	len2, [tmp1 + dist2]
	jz	compare_loop2

	;; Specutively load the code for the first literal
	movzx   tmp1, curr_data %+ b
	shr	curr_data, 8

	lea	tmp3, [f_i + 1]

	;; Check for len/dist match for first literal
	test    len %+ d, 0xFFFFFFFF
	jz      len_dist_huffman_pre

	;; Store first literal
	inc	qword [histogram + _lit_len_offset + HIST_ELEM_SIZE * tmp1]

	;; Check for len/dist match for second literal
	test    len2 %+ d, 0xFFFFFFFF
	jnz     lit_lit_huffman
len_dist_lit_huffman_pre:
	;; Calculate repeat length
	tzcnt	len2, len2
	shr	len2, 3

len_dist_lit_huffman:
	MOVQ	curr_data, xdata
	shr	curr_data, 24
	compute_hash hash3, curr_data

	;; Store updated hashes
	mov	[histogram + _hash_offset + 2 * hash], tmp3 %+ w
	add	tmp3,1
	mov	[histogram + _hash_offset + 2 * hash2], tmp3 %+ w
	add	tmp3, 1

	add	f_i, len2

	MOVDQU	xdata, [file_start + f_i]
	mov	curr_data, [file_start + f_i]
	mov	tmp1, curr_data
	compute_hash	hash, curr_data

	and	hash3, HASH_MASK
	mov	[histogram + _hash_offset + 2 * hash3], tmp3 %+ w

	dist_to_dist_code2 dist_code2, dist2

	len_to_len_code len_code, len2, rfc_lookup

	shr	tmp1, 8
	compute_hash	hash2, tmp1

	inc	qword [histogram + _lit_len_offset + HIST_ELEM_SIZE * len_code]
	inc	qword [histogram + _dist_offset + HIST_ELEM_SIZE * dist_code2]

	and	hash2 %+ d, HASH_MASK
	and	hash, HASH_MASK

	cmp	f_i, file_length
	jl	loop2
	jmp	end_loop_2
	;; encode as dist/len

len_dist_huffman_pre:
	tzcnt	len, len
	shr	len, 3

len_dist_huffman:
	mov	[histogram + _hash_offset + 2 * hash], tmp3 %+ w
	add	tmp3,1
	mov	[histogram + _hash_offset + 2 * hash2], tmp3 %+ w

	dec	f_i
	add	f_i, len

	MOVDQU	xdata, [file_start + f_i]
	mov	curr_data, [file_start + f_i]
	mov	tmp1, curr_data
	compute_hash	hash, curr_data

	dist_to_dist_code2 dist_code, dist

	len_to_len_code len_code, len, rfc_lookup

	shr	tmp1, 8
	compute_hash	hash2, tmp1

	inc	qword [histogram + _lit_len_offset + HIST_ELEM_SIZE * len_code]
	inc	qword [histogram + _dist_offset + HIST_ELEM_SIZE * dist_code]

	and	hash2 %+ d, HASH_MASK
	and	hash, HASH_MASK

	cmp	f_i, file_length
	jl	loop2
	jmp	end_loop_2

lit_lit_huffman:
	MOVDQU	xdata, [file_start + f_i + 1]
	and     curr_data, 0xff
	add	f_i, 1
	inc	qword [histogram + _lit_len_offset + HIST_ELEM_SIZE * curr_data]

	cmp	f_i, file_length
	jl	loop2

end_loop_2:
	add	file_length, LA_STATELESS - LAST_BYTES_COUNT
	cmp	f_i, file_length
	jge	final_bytes

loop2_finish:
	mov	curr_data %+ d, dword [file_start + f_i]
	compute_hash	hash, curr_data
	and	hash %+ d, HASH_MASK

	;; Calculate possible distance for length/dist pair.
	xor	dist, dist
	mov	dist %+ w, f_i %+ w
	sub	dist %+ w, word [histogram + _hash_offset + 2 * hash]
	mov	[histogram + _hash_offset + 2 * hash], f_i %+ w

	;; Check if look back distance is valid (the dec is to handle when dist = 0)
	dec	dist
	cmp	dist %+ d, (D-1)
	jae	encode_literal_finish
	inc	dist

	;; Check if look back distance is a match
	lea	tmp4, [file_length + LAST_BYTES_COUNT]
	sub	tmp4, f_i
	lea	tmp1, [file_start + f_i]
	mov	tmp2, tmp1
	sub	tmp2, dist
	compare	tmp4, tmp1, tmp2, len, tmp3

	;; Limit len to maximum value of 258
	mov	tmp2, 258
	cmp	len, 258
	cmova	len, tmp2
	cmp	len, SHORTEST_MATCH
	jb	encode_literal_finish

	add	f_i, len

	len_to_len_code	len_code, len, rfc_lookup
	dist_to_dist_code dist_code, dist

	inc	qword [histogram + _lit_len_offset + HIST_ELEM_SIZE * len_code]
	inc	qword [histogram + _dist_offset + HIST_ELEM_SIZE * dist_code]

	cmp	f_i, file_length
	jl	loop2_finish
	jmp	final_bytes

encode_literal_finish:
	;; Encode literal
	and	curr_data %+ d, 0xFF
	inc	qword [histogram + _lit_len_offset + HIST_ELEM_SIZE * curr_data]

	;; Setup for next loop
	add	f_i, 1
	cmp	f_i, file_length
	jl	loop2_finish

final_bytes:
	add	file_length, LAST_BYTES_COUNT
final_bytes_loop:
	cmp	f_i, file_length
	jge	end
	movzx	curr_data, byte [file_start + f_i]
	inc	qword [histogram + _lit_len_offset + HIST_ELEM_SIZE * curr_data]
	inc	f_i
	jmp	final_bytes_loop

end:
	;; Handle eob at end of stream
	mov	tmp1, [rsp + _eob_count_offset]
	mov	qword [histogram + _lit_len_offset + HIST_ELEM_SIZE * 256], tmp1

exit_ret:
	FUNC_RESTORE
	ret

compare_loop:
	and	hash %+ d, HASH_MASK
	and	hash2 %+ d, HASH_MASK
	lea	tmp2, [tmp1 + dist - 1]
%if (COMPARE_TYPE == 1)
	compare250	tmp1, tmp2, len, tmp3
%elif (COMPARE_TYPE == 2)
	compare250_x	tmp1, tmp2, len, tmp3, xtmp0, xtmp1
%elif (COMPARE_TYPE == 3)
	compare250_y	tmp1, tmp2, len, tmp3, ytmp0, ytmp1
%else
	%error Unknown Compare type COMPARE_TYPE
	 % error
%endif
	lea	tmp3, [f_i + 1]
	jmp	len_dist_huffman

compare_loop2:
	add	tmp1, 1
	lea	tmp2, [tmp1 + dist2 - 1]

%if (COMPARE_TYPE == 1)
	compare250	tmp1, tmp2, len2, tmp3
%elif (COMPARE_TYPE == 2)
	compare250_x	tmp1, tmp2, len2, tmp3, xtmp0, xtmp1
%elif (COMPARE_TYPE == 3)
	compare250_y	tmp1, tmp2, len2, tmp3, ytmp0, ytmp1
%else
%error Unknown Compare type COMPARE_TYPE
 % error
%endif
	and	curr_data, 0xff
	inc	qword [histogram + _lit_len_offset + 8 * curr_data]
	lea	tmp3, [f_i + 1]
	jmp	len_dist_lit_huffman

section .data
	align 32
D_vector:
	dw	-(D + 1) & 0xFFFF, -(D + 1) & 0xFFFF, -(D + 1) & 0xFFFF, -(D + 1) & 0xFFFF
	dw	-(D + 1) & 0xFFFF, -(D + 1) & 0xFFFF, -(D + 1) & 0xFFFF, -(D + 1) & 0xFFFF
	dw	-(D + 1) & 0xFFFF, -(D + 1) & 0xFFFF, -(D + 1) & 0xFFFF, -(D + 1) & 0xFFFF
	dw	-(D + 1) & 0xFFFF, -(D + 1) & 0xFFFF, -(D + 1) & 0xFFFF, -(D + 1) & 0xFFFF