WebSVN – NedoOS – Blame – /src/nv/heapsort.asm

Rev	Author	Line No.	Line
73	Alone	1	;MAIN "HPTST",#16
		2
		3	;working assumptions:
		4
		5	;0000..7FFF -- code area
		6	;8000..BFFF, C000..FFFF -- page switching area
		7
		8	;uses 2 pages for elements, 4 pages for strings
		9	;strings are zero-terminated, cant cross page boundary
		10
		11	;switches pages on its own
		12	;-------------------------------------------------------------------------------
		13	;-------------------------------------------------------------------------------
		14
		15
		16
		17	HPSRT_init ;inits everything for a new sort
		18
109	demige	19	; LD HL,#4000
		20	; LD (HS_s0free),HL
		21	; LD (HS_s1free),HL
		22	; LD (HS_s2free),HL
		23	; LD (HS_s3free),HL
73	Alone	24
109	demige	25	; LD H,L ;0
		26	ld hl,0
73	Alone	27	LD (HS_enum),HL
		28
		29	RET
		30
		31	;HS_strpg DB #20 ;4 pages for strings
		32	;HS_elpg DB #24 ;2 pages for elements
		33
		34	;free spaces in string pages
109	demige	35	;HS_s0free DW 0
		36	;HS_s1free DW 0
		37	;HS_s2free DW 0
		38	;HS_s3free DW 0
73	Alone	39
		40	;elements array free offset
		41	HS_enum DW 0 ;working number of elements
		42	HS_num DW 0 ;final number of elements
		43
		44
		45	HPSRT_add ;adds new element to heap, keeping heap property
		46	;
109	demige	47	; DE -- heap element (strptr)
73	Alone	48	;
		49	;out: CY=1 - no space for the element
		50	;
109	demige	51	;kills: every reg
73	Alone	52
		53	;check if there is place for new element
		54	;max. 8192 els
		55
109	demige	56	;EXX
73	Alone	57	LD HL,(HS_enum)
		58	INC HL
		59	BIT 5,H
		60	;JR Z,$+4
		61	SCF
		62	RET nz ;too many elements
		63
		64	LD (HS_enum),HL
		65	DEC HL
		66
		67	PUSH HL
		68
		69	;num2addr
109	demige	70	;ADD HL,HL
73	Alone	71	ADD HL,HL
109	demige	72	;LD A,H
		73	;RLCA
		74	;RLCA
		75	;AND 1
73	Alone	76	;LD B,A
		77	;LD A,(HS_elpg)
		78	;ADD A,B
		79	PGW3elpg
		80	LD A,#C0
		81	OR H
		82	LD H,A
		83
109	demige	84	;EXX
		85	;LD A,D
		86	;EXX
		87	;LD (HL),A
		88	;INC L
		89	;EXX
		90	;LD A,E
		91	;EXX
		92	;LD (HL),A
		93	;INC L
		94	;EXX
		95	if HEAPSORT_LH
		96	LD (HL),e
		97	else
		98	LD (HL),d
		99	endif
		100	;EXX
		101	;LD (HL),A
73	Alone	102	INC L
109	demige	103	;EXX
		104	if HEAPSORT_LH
		105	LD (HL),d
		106	else
		107	LD (HL),e
		108	endif
		109	;EXX
		110	;LD (HL),A
73	Alone	111
		112
		113	POP HL
		114
		115	CALL HPSRT_upswap
		116
		117	OR A
		118	RET
		119
		120
		121
		122
		123
		124	HPSRT_sort ;sorts array after all additions finished
		125
		126
		127	LD HL,(HS_enum)
		128	LD (HS_num),HL ;final number of elements
		129
		130	HS_s_loop
		131	LD HL,(HS_enum)
		132
		133	;no sort if no elements
		134	LD A,H
		135	OR L
		136	RET Z
		137
		138	;no sort if 1 element
		139	DEC HL
		140	LD A,H
		141	OR L
		142	RET Z
		143
		144	LD (HS_enum),HL ;1 element less to sort next time
		145
		146	;swap last element (in HL) with top
		147
109	demige	148	;ADD HL,HL
73	Alone	149	ADD HL,HL
109	demige	150	;LD A,H
		151	;RLCA
		152	;RLCA
		153	;AND 1
73	Alone	154	;LD B,A
		155	;LD A,(HS_elpg)
		156	;ADD A,B
		157	PGW3elpg
		158	LD A,H
		159	OR #C0
		160	LD H,A
		161
		162	LD DE,#8000
		163	;LD A,(HS_elpg)
		164	PGW2elpg0
		165
109	demige	166	DUP 1;3
73	Alone	167	LD A,(DE)
		168	LD B,(HL)
		169	EXD
		170	LD (DE),A
		171	LD (HL),B
		172	INC E
		173	INC L
		174	EDUP
		175	LD A,(DE)
		176	LD B,(HL)
		177	EXD
		178	LD (DE),A
		179	LD (HL),B
		180
		181	CALL HPSRT_downswap
		182
		183	JR HS_s_loop
		184
		185
		186
		187	;do downswap from the root to HS_enum
		188	HPSRT_downswap
		189	LD DE,0 ;root
		190
		191	HS_s_dswp_loop
		192	;calc left leaf
		193	LD H,D
		194	LD L,E
		195	ADD HL,HL
		196	INC HL ;HL - left leaf
		197
		198	LD BC,(HS_enum) ; size of array
		199	OR A
		200	SBC HL,BC
		201	RET NC ;no leafs
		202
		203	PUSH DE
		204
		205	LD A,H ;if result is #FFFF -
		206	AND L ;only left leaf
		207	ADD HL,BC
		208	INC A
		209	JR Z,HS_s_dswp_left
		210
		211	;have 2 leafs
		212	LD D,H
		213	LD E,L
		214	INC DE ;DE - right leaf
		215
		216	PUSH HL,DE
		217	CALL HPSRT_cmpel
		218	;CY=1 - DE is smaller
		219	;CY=0 - DE is equal or bigger
		220
		221	POP DE,HL
		222	JR C,$+3
		223	EXD
		224	;now in HL is biggest leaf of two
		225
		226	HS_s_dswp_left
		227	POP DE ;root
		228	;HL is leaf to swap with
		229
		230	PUSH HL ;also next root
		231
		232	CALL HPSRT_cmpswap
		233
		234	POP DE
		235	JR C,HS_s_dswp_loop
		236
		237	RET
		238
		239
		240
		241
		242
		243	HPSRT_upswap ;in: HL - number of leaf element to process
		244	; swaps elements up to the root
		245
		246	LD A,H
		247	OR L
		248	RET Z
		249
		250	;calc root
		251	LD D,H
		252	LD E,L
		253	dec de
		254	SRL D
		255	RR E
		256	;JR C,$+3
		257	;DEC DE
		258
		259	PUSH DE ;remember root el for possible recursion
		260
		261	CALL HPSRT_cmpswap
		262
		263	;restore root in HL
		264	POP HL
		265
		266	RET NC ;exit if no swap
		267
		268	;tail recursion
		269	JR HPSRT_upswap
		270
		271
		272	HPSRT_cmpswap ;CY=1 if swap, CY=0 otherwise
109	demige	273	;di
		274	;jr $
		275	;ei
73	Alone	276	EXD
		277	ADD HL,HL
109	demige	278	;ADD HL,HL
		279	;LD A,H
		280	;RLCA
		281	;RLCA
		282	;AND 1
73	Alone	283	;LD B,A
		284	;LD A,(HS_elpg)
		285	;ADD A,B
109	demige	286	;PUSH AF ;pg num for root
73	Alone	287	PGW2elpg
		288	;LD A,H
		289	;AND #3F
		290	;OR #80
		291	;LD H,A
		292	res 6,h
		293	set 7,h
		294	EXD
		295
		296	ADD HL,HL
109	demige	297	;ADD HL,HL
		298	;LD A,H
		299	;RLCA
		300	;RLCA
		301	;AND 1
73	Alone	302	;LD B,A
		303	;LD A,(HS_elpg)
		304	;ADD A,B
109	demige	305	;PUSH AF ;pg num for leaf
73	Alone	306	PGW3elpg
		307	LD A,H
		308	OR #C0
		309	LD H,A
		310
		311	CALL HPSRT_cmp
		312	;CY=0 - de is not smaller, no swap
		313
		314	JR C,HS_us_swp
		315
		316	;no swap - stop
		317	POP HL
		318	POP HL
		319	RET
		320	HS_us_swp
109	demige	321	;POP AF
73	Alone	322	PGW3elpg
109	demige	323	;POP AF
73	Alone	324	PGW2elpg
		325
109	demige	326	DUP 1;3
73	Alone	327	LD A,(DE)
		328	LD B,(HL)
		329	EXD
		330	LD (DE),A
		331	LD (HL),B
		332	INC E
		333	INC L
		334	EDUP
		335	LD A,(DE)
		336	LD B,(HL)
		337	EXD
		338	LD (DE),A
		339	LD (HL),B
		340
		341	SCF
		342	RET
		343
		344
		345
		346	HPSRT_cmpel
		347	;in: DE,HL - elements
		348	;out: CY=1 if de is smaller, otherwise CY=0
		349
		350	;make offsets instead of el numbers, switch pages
		351	; 8000-BFFF - for root el (DE)
		352	; C000-FFFF - for leaf el (HL)
		353
		354	EXD
		355	ADD HL,HL
109	demige	356	;ADD HL,HL
73	Alone	357	LD A,H
		358	RLCA
		359	RLCA
		360	AND 1
		361	;LD B,A
		362	;LD A,(HS_elpg)
		363	;ADD A,B
		364	PGW2elpg
		365	;LD A,H
		366	;AND #3F
		367	;OR #80
		368	;LD H,A
		369	res 6,h
		370	set 7,h
		371	EXD
		372
		373	ADD HL,HL
109	demige	374	;ADD HL,HL
73	Alone	375	LD A,H
		376	RLCA
		377	RLCA
		378	AND 1
		379	;LD B,A
		380	;LD A,(HS_elpg)
		381	;ADD A,B
		382	PGW3elpg
		383	LD A,H
		384	OR #C0
		385	LD H,A
		386
		387	HPSRT_cmp ;compare element pointed by HL
		388	; with element pointed by DE
		389
		390	;we kill pages in W2 and W3
		391	;but retain HL and DE
		392
		393	;out: CY=0 - DE is not smaller (may be upper in tree)
		394
		395
		396	PUSH DE
		397	PUSH HL
		398
		399	;compare dir/file, dir is always smaller
109	demige	400	; LD A,(DE)
		401	; XOR (HL)
		402	; JP P,HS_cp_str
73	Alone	403
109	demige	404	; ;signs differ: DE must be file to be greater
73	Alone	405
109	demige	406	; LD A,(HL)
		407	; RLCA
73	Alone	408
109	demige	409	; POP HL
		410	; POP DE
		411	; RET
73	Alone	412
109	demige	413
		414	;HS_alonecmp
73	Alone	415	;get strings into DE,HL, also paging
		416	EXD
109	demige	417	;INC L
		418	;INC L
73	Alone	419	LD A,(HL)
		420	INC L
109	demige	421	if HEAPSORT_LH
		422	LD h,(HL)
		423	LD l,A
		424	;ld a,h
		425	else
73	Alone	426	LD L,(HL)
		427	LD H,A
109	demige	428	endif
		429	;RLCA
		430	;RLCA
		431	;AND 3
		432	ld a,l
		433	and 31
		434	add a,(ix+PANEL.pgadd)
73	Alone	435	;LD B,A
		436	;LD A,(HS_strpg)
		437	;ADD A,B
		438	PGW2strpg
109	demige	439	ld a,l
		440	and 0xe0
		441	ld l,a
73	Alone	442	;LD A,H
		443	;AND #3F
		444	;OR #80
		445	;LD H,A
		446	res 6,h
		447	set 7,h
		448	EXD
		449
109	demige	450	;INC L
		451	;INC L
73	Alone	452	LD A,(HL)
		453	INC L
109	demige	454	if HEAPSORT_LH
		455	LD h,(HL)
		456	LD l,A
		457	;ld a,h
		458	else
73	Alone	459	LD L,(HL)
		460	LD H,A
109	demige	461	endif
		462	;RLCA
		463	;RLCA
		464	;AND 3
		465	ld a,l
		466	and 31
		467	add a,(ix+PANEL.pgadd)
73	Alone	468	;LD B,A
		469	;LD A,(HS_strpg)
		470	;ADD A,B
		471	PGW3strpg
109	demige	472	ld a,l
		473	and 0xe0
		474	ld l,a
73	Alone	475	LD A,H
		476	OR #C0
		477	LD H,A
		478
109	demige	479	call comparer
		480	ccf
		481	pop hl
		482	pop de
		483	ret

Subversion Repositories NedoOS

(root)/src/nv/heapsort.asm – Rev 109