Математические функции

Sayman · Post by **Sayman** » 18 Feb 2021 00:22

Приветствую.
На днях сидел ковырялся с утилитой форматирования. Нужна была процедура деления 32:16=16,16 (остаток). Решил позаимствовать процедуру из Flex Navigator, но оказалось, что процедура в командере не рабочая. Провёл несколько тестов, на больших или не ровных (с точки зрения HEX числа) значениях выдаёт всякую фигню. на мелких значениях более или менее работает.
Далее решил проверить сразу несколько процедур. Выбрал из FM, pq-dos и с просторов интернета.
По итогу рабочих процедур нашёл только 2. одна процедура из bdos`а PQ-DOS для Профи, вторая с викии CPC. Процедура из PQ-DOS жрёт около 4000 тактов (чуть больше). Процедура от CPC около 1200 - 1500, но занимает раза в 2 больше места. Провёл на них несколько тестов, обе дают корректные результаты. На CPC процедуре ещё отдельно и остатки протестировал.
размещаю обе процедуры тут, а в командерах требуется замена этих мат.процедур во избежание багов с файлами и ФС в целом!

процедура из PQ-DOS:

Code: Select all

;Input: HL:DE = Dividend, BC = Divisor, HL'= 0
;Output: HL:DE = Quotient, DE' = Remainder
div32_pqdos:
;		exx
;		push	bc		;'
;		push	hl		;'
;		exx

		push	bc
		exx
		pop	bc		;'
		ld	hl,0
		exx
		ld	b,32

.d32_1:		add	hl,hl
		ex	de,hl
		adc	hl,hl
		ex	de,hl

		exx
		adc	hl,hl

		or	a
		sbc	hl,bc
		jr	nc,.d32_2
		add	hl,bc
		exx
		dec	l
		exx
.d32_2:		exx
		inc	l
		djnz	.d32_1
	
		exx
		ex de,hl
;		pop	hl
;		pop	bc
		exx
		ret

процедура из викии CPC (причёсанная под sjasm/sjasmplus):

Code: Select all

		macro div_r
			SLA   E
			RL    D
			ADC   HL, HL

			LD    A, L
			ADD   A, C
			LD    A, H
			ADC   A, B
			JR    NC,.t2

			ADD   HL, BC
			INC   DE
.t2:
		endm

		macro div_e
			SLA   E
			RL    D
			ADC   HL, HL
			JR    C, .t1

			LD    A, L
			ADD   A, C
			LD    A, H
			ADC   A, B
			JR    NC, .t2
.t1:			ADD   HL, BC
			INC   DE
.t2:
		endm

; BCDE = HLDE/BC, HL = HLDE%BC
;1171t
div32x16_cpc:	DEC   BC
		LD    A, B
		CPL
		LD    B, A
		LD    A, C
		CPL
		LD    C, A
		ADD   A, L
		LD    A, B
		ADC   A, H
		JR    NC, .DIV16

		PUSH  DE
		EX    DE, HL
		LD    HL, 0000
		CALL  .DIV32R
		EX    DE, HL
		EX    (SP), HL
		EX    DE, HL
		CALL  .DIV32E
		POP   BC
		RET

.DIV16:		CALL  .DIV32E
		LD    BC, 0000
		RET

; DE = HLDE/(-BC), HL = HLDE%(-BC), -BC < $8000
.DIV32R:	CALL  $+3
		rept 8
			div_r
		endm
		RET

; DE = HLDE/(-BC), HL = HLDE%(-BC)
.DIV32E:	CALL  $+3
		rept 8
			div_e
		endm
		RET

Shaos · Post by **Shaos** » 18 Feb 2021 02:17

b2m предложил ещё более быстрый и короткий вариант:
https://zx-pk.ru/threads/32913-32-bit-delenie.html
(переписка с 8080 из книги Гуртовцева, Гудыменко ):

Code: Select all

DIV32:	ld a,b ; DE = HLDE/BC, HL = HLDE%BC
	cpl
	ld b,a
	ld a,c
	cpl
	ld c,a
	inc bc
	xor a
DIV321:	add hl,hl
	rra
	ex de,hl
	add hl,hl
	ex de,hl
	jr nc, DIV320
	inc hl
DIV320:	push hl
	add hl,bc
	jr nc, DIV322
	rla
DIV323:	inc de
	inc sp
	inc sp
	add a, 10h
	jr nc, DIV321
	ret
DIV322:	rla
	jr c, DIV323
	pop hl
	add a, 10h
	jr nc, DIV321
	ret

b2m wrote:Вообще-то можно с использованием Z80 инструкций подсократить, например при 32-битном сдвиге использовать adc hl,hl, а вместо инверсии делителя использовать sbc hl,bc

Я попробовал - не выходит получить выгоду от таких замен на z80-инструкции - выходит заметно больше кода который исполняется медленнее - так что лучше оставить как есть...

b2m · Post by **b2m** » 18 Feb 2021 05:21

Shaos wrote:не выходит получить выгоду от таких замен на z80-инструкции

А если так:

Code: Select all

DIV32:	xor a ; DE = HLDE/BC, HL = HLDE%BC
DIV321:	ex de,hl
	add hl,hl
	ex de,hl
	adс hl,hl
	rra
	push hl
	ccf
	sbс hl,bc
	jr c, DIV322
	rla
DIV323:	inc de
	inc sp
	inc sp
	add a, 10h
	jr nc, DIV321
	ret
DIV322:	rla
	jr c, DIV323
	pop hl
	add a, 10h
	jr nc, DIV321
	ret

Если хочется ещё компактнее, можно три повторяющиеся команды конца цикла заменить на одну jr

А ещё, можно чуть ускорить, если не делать push hl / inc sp / inc sp когда не надо. Тогда и rla / rra можно будет выкинуть, но за счёт дополнительной sbс hl,bc, конечно.

b2m · Post by **b2m** » 18 Feb 2021 05:39

Вот, даже проверял, вроде правильно:

Code: Select all

DIV32:	ld a,10h ; DE = HLDE/BC, HL = HLDE%BC
DIV321:	ex de,hl
	add hl,hl
	ex de,hl
	adс hl,hl
	jr c DIV322
	push hl
	sbс hl,bc
	jr nc, DIV323
	pop hl
	jr DIV325
DIV322:	ccf
	sbс hl,bc
	jr DIV324
DIV323:	inc sp
	inc sp
DIV324:	inc de
DIV325:	dec a
	jr nz, DIV321
	ret

b2m · Post by **b2m** » 18 Feb 2021 07:12

Кстати, если делитель и частное не превышают 32767 (например если используется арифметика со знаком и перед вызовом эти числа приводятся к положительным), то ветку DIV322 можно смело выкинуть.

Shaos · Post by **Shaos** » 18 Feb 2021 10:46

чото там выше вперемешку русские c в мнемониках ассемблера - вот причесал:

Code: Select all

DIV32MM: ; DE = HLDE/BC, HL = HLDE%BC
   ld a,10h
DIV321MM:
   ex de,hl
   add hl,hl
   ex de,hl
   adc hl,hl
   jr c,DIV322MM
   push hl
   sbc hl,bc
   jr nc,DIV323MM
   pop hl
   jr DIV325MM
DIV322MM:
   ccf
   sbc hl,bc
   jr DIV324MM
DIV323MM:
   inc sp
   inc sp
DIV324MM:
   inc de
DIV325MM:
   dec a
   jr nz,DIV321MM
   ret

Воде работает

b2m · Post by **b2m** » 18 Feb 2021 10:50

ivagor, как обычно, оптимизировал мой код

Code: Select all

DIV32:
		ld a,10h ; DE = HLDE/BC, HL = HLDE%BC
DIV321:
		ex de,hl
		add hl,hl
		ex de,hl
		adc hl,hl
		jr c, DIV322
		sbc hl,bc
		jr nc, DIV323
		add hl,bc
		jr DIV324
DIV322:
		ccf
		sbc hl,bc
DIV323:
		inc de
DIV324:
		dec a
		jr nz, DIV321
		ret

Shaos · Post by **Shaos** » 18 Feb 2021 11:26

Дублирование в двух форумах не всегда синхронно - новая версия от b2m

Code: Select all

DIV32:
		ld a,10h ; DE = HLDE/BC, HL = HLDE%BC
DIV321:
		sla e
		rl d
		adc hl,hl
		jr c, DIV322
		sbc hl,bc
		jr nc, DIV323
		add hl,bc
		jr DIV324
DIV322:
		ccf
		sbc hl,bc
DIV323:
		inc de
DIV324:
		dec a
		jr nz, DIV321
		ret

Shaos · Post by **Shaos** » 18 Feb 2021 12:36

Самая быстрая подпрограмма от b2m если делитель 15-битный

Code: Select all

DIV32: ; DE = HLDE/BC, HL = HLDE%BC, HLDE<2^31, BC<2^15
	rept 16
		sla e
		rl d
		adc hl,hl
		sbc hl,bc
		jr nc, $+4
		add hl,bc
		dec de
		inc de
	endm
	ret

апдейт:

Code: Select all

DIV32: ; DE = HLDE/BC, HL = HLDE%BC, HLDE<2^31, BC<2^15
	rept 16
		sla e
		rl d
		adc hl,hl
		sbc hl,bc
		jr nc, $+4
		add hl,bc
		dec e
		inc e
	endm
	ret

- - - Добавлено - - -

1162 тактов максимум

- - - Добавлено - - -

209 байт

Sayman · Post by **Sayman** » 18 Feb 2021 21:03

сам же и исправляю свой косяк - изначальная процедура на 2055тактов. последняя (через 1 пост вверх) 1456 тактов, но в каких диапазонах работает не известно, надо тоже проверять. на моих значениях работает вроде нормально.
последняя процедура с 15битами обрезанная, не смотрел, т.к. не полный диапазон не интересен.

Shaos · Post by **Shaos** » 18 Feb 2021 23:00

да - последний вариант для твоих целей неинтересен - из него надо деления со знаком сделать (убирать минус если есть, передавать в эту подпрограмму как 31-битное делимое и 15-битный делитель и потом возвращать знак обратно, если надо)

Alekcandr · Post by **Alekcandr** » 20 Feb 2021 02:15

Sayman, а в чем проблема? Взять готовую процедуру из исходников, которых пруд пруди. Тема избитая и 1000 раз проверенная. Ну, пусть на 100 тактов медлееееенней. Операция деления тяжелая, на 3.5Мгц всегда была не спешная, как и FAT16.

Есть ведь много интересных штук, а тут опять изобретаем колесо.

p.s. вот допустим. в MSX вложен один вайт в цикл M1. это минус 20% быстродействия. надо доработать? нет. как говорил один уважаемый программист на MSX - это не проблема, есть, много других интересных и не исследованных штук.

возможно, математику имеет смысл дорабатывать под эксклюзивную штуку с особой заточкой. но вот так под универсал?

если нужно очень. можно разделить задачу на несколько этапов деления (16/16 c остатком). это высший пилотаж. когда все основные штуки в программе работают. мопед не мой.

Code: Select all

;	  Subroutine divide
;	     Inputs  BC = para1, DE = para2
;	     Outputs HL = rest, BC = result

C3E24:	XOR	A
        LD	H,A
        LD	L,A
        LD	A,16
J3E29:	CCF	
J3E2A:	RL	C
        RL	B
        DEC	A
        RET	M
        ADC	HL,HL
        SBC	HL,DE
        JR	NC,J3E29
        ADD	HL,DE
        OR	A
        JR	J3E2A

еще подумавши. в целом не понятна задача. зачем 32 на 16. может возможно это упрастить? а когда не понятна задача, это капец во что может выльется

Shaos · Post by **Shaos** » 20 Feb 2021 12:41

Alekcandr wrote:Sayman, а в чем проблема? Взять готовую процедуру из исходников, которых пруд пруди. Тема избитая и 1000 раз проверенная. Ну, пусть на 100 тактов медлееееенней. Операция деления тяжелая, на 3.5Мгц всегда была не спешная, как и FAT16.

просто оказалось, что процедуры деления, использованные в программах на Спринтере неработают нормально на всём диапазоне входных значений - вот и начался поиск новых решений, способных поделить то, что Сайману надо было поделить...

Sayman · Post by **Sayman** » 20 Feb 2021 22:33

Alekcandr wrote:Sayman, а в чем проблема? Взять готовую процедуру из исходников, которых пруд пруди. Тема избитая и 1000 раз проверенная. Ну, пусть на 100 тактов медлееееенней. Операция деления тяжелая, на 3.5Мгц всегда была не спешная, как и FAT16.

Есть ведь много интересных штук, а тут опять изобретаем колесо.

p.s. вот допустим. в MSX вложен один вайт в цикл M1. это минус 20% быстродействия. надо доработать? нет. как говорил один уважаемый программист на MSX - это не проблема, есть, много других интересных и не исследованных штук.

возможно, математику имеет смысл дорабатывать под эксклюзивную штуку с особой заточкой. но вот так под универсал?

если нужно очень. можно разделить задачу на несколько этапов деления (16/16 c остатком). это высший пилотаж. когда все основные штуки в программе работают. мопед не мой.
Code: Select all
;	  Subroutine divide
;	     Inputs  BC = para1, DE = para2
;	     Outputs HL = rest, BC = result

C3E24:	XOR	A
        LD	H,A
        LD	L,A
        LD	A,16
J3E29:	CCF	
J3E2A:	RL	C
        RL	B
        DEC	A
        RET	M
        ADC	HL,HL
        SBC	HL,DE
        JR	NC,J3E29
        ADD	HL,DE
        OR	A
        JR	J3E2A
еще подумавши. в целом не понятна задача. зачем 32 на 16. может возможно это упрастить? а когда не понятна задача, это капец во что может выльется

Если быть чуть более внимательным и прочитать первый пост. то сразу становится понятно, что процедура деления 16:16 для работы с дисками не подходит от слова совсем, если только ты не хочешь ограничить свою утилиту в 32мб . нумерация секторов - 28бит (поскольку LBA28). это явно не влезает в процедуру 16:16.
Да и экономия не 100 такто, а как оказалось почти 3тыщи тактов. процедуры из исходников не рабочие.
Кстати, файловая система FAT16 самая быстрая. я бьы не зназвал её не спешно. Она быстрее даже, чем FAT12 и намного быстрее, чем FAT32 в реалиях z80.

Alekcandr · Post by **Alekcandr** » 21 Feb 2021 02:43

Странно, что FAT16 быстрее FAT12. По моим данным это не так. Ну да ладно.

Применительно к теме можно посмотреть исходники Nextor и как там реализуется математика применительно к FAT16. Функции деления 32/16 в чистом виде не нашел, может плохо искал.

Математические функции

Математические функции

Re: Математические функции

Re: Математические функции

Re: Математические функции

Re: Математические функции

Re: Математические функции

Re: Математические функции

Re: Математические функции

Re: Математические функции

Re: Математические функции

Re: Математические функции

Re: Математические функции

Re: Математические функции

Re: Математические функции

Re: Математические функции