32 бит деление

[ivagor]

Если пошел уклон в сторону оптимизации по размеру, то можно немного сократить и ускорить

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

[b2m]

Ну, ivagor как обычно в своём репертуаре...

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

Если пошел уклон в сторону оптимизации по скорости, то можно выиграть ещё 48 тактов

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

[ivagor]

Раз пошло увеличение размера, то за +2 байта можно еще ускорить. Надо определиться, все же оптимизация по размеру или по скорости. И если по скорости, то можно ли разворачивать цикл (и если да, то явно можно нагуглить быстрые процедуры).

Скрытый текст

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
		dec a
		jr nz, DIV321
		ret
DIV322:
		ccf
		sbc hl,bc
DIV323:
		inc de
		dec a
		jr nz, DIV321
		ret

[свернуть]

[b2m]

Надо определиться, все же оптимизация по размеру или по скорости.

Блин, при 27 байтах на процедуру, какой смысл в оптимизации по размеру, если не разворачивать цикл?

И если по скорости, то можно ли разворачивать цикл

Мой вариант удобнее разворачивать

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

А если ограничить делитель и частное 15-ю битами, то ветку DIV322 можно выкинуть, и тогда уже развернуть. Вряд-ли найдутся более быстрые процедуры.

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

А потом ещё сэкономить заменив jr DIV324 на dec de

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

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 байт

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

А если ограничить делитель и частное 15-ю битами, то ветку DIV322 можно выкинуть

Хотя, не очевидно это, хорошо бы доказать...

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

Ооо... как можно было забыть, что inc e на 2 такта быстрее inc de!!!

[Sayman]

если ограничить делитель и частное 15-ю битами

такая процедура не нужна. делитель 16 бит нужен.

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

оригинальная процедура (на z80, до ваших оптимизаций), на моих тестах/примерах отжрала 1055 тактов. так что у вас уже не оптимизация, а что-то обратное.

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

[ivagor]

Без четких критериев оптимальности и ограничений не получится сделать оптимальную процедуру. Если говорить о развернутых вариантах, то для 8080 быстрейшим является реализация алгоритма blackmirrora, которую можно найти в ветке про пи. Насчет ее оптимальности по скорости для z80 (с соответствующей оптимизацией) я уверен не на 100%, но по крайней мере она где-то среди быстрейших.
Если вернуться к сравнительно компактным процедурам, то изменив распределение регистров, можно еще оптимизировать

Скрытый текст

DIV32:
		ld a,b
		ld b,16 ; BC = HLBC/DE, HL = HLBC%DE
DIV321:
		sla c
		rla
		adc hl,hl
		jr c, DIV322
		sbc hl,de
		jr nc, DIV323
		add hl,de
		djnz DIV321
		ld b,a
		ret
DIV322:
		ccf
		sbc hl,de
DIV323:
		inc c
		djnz DIV321
		ld b,a
		ret

[свернуть]

И важно знать предполагаемые диапазоны наиболее вероятных значений делимого и делителя. Самую короткую процедуру можно оптимизировать без увеличения размера для (как мне представляется) наиболее востребованных соотношений делимого и делителя, для четкой проверки нужен конкретный test bench.

[Advertiser]

[Sayman]

ivagor, в моём представлении математическая процедура должна выполнять математику, не взирая на 15 бит или ещё там что то. если процедура называется 32:16, то она во всём диапазоне должна работать. Если же процедура работает только в каких-то конкретных диапазонах, то увы, 32:16 её уже называть нельзя. и хорошо бы в комментариях к процедуре такое указывать. я топик то создал - работая с утилитой, которая должна работать с данными на винте, математика предполагает наличие всего диапазона (во всяком случае до 28 бит для ЛБА). столкнулся как раз с тем, что именованные процедуры, вроде div32_16 и тому подобные на проверку не могут даже 18 бит разделить на 16, выдавая вместо результата мусор. Увы, но в написании таких процедур я не силён. Но, изначальная для z80 процедура от b2m, переписка с 8080, оказалась самой быстрой и при этом весьма короткой (находил в разы больше и при этом медленнее).
сами понимаете, z80 математически обделённый, а потому нужна какая то быстрая процедура, но не превращённая в 16килобайтного монстра ради экономии 50 тактов.

[ivagor]

если процедура называется 32:16, то она во всём диапазоне должна работать

Это не подвергается сомнению. Просто надо учитывать, что от соотношений делимого и делителя зависят вероятности прохождения тех или иных веток процедуры, и это можно учесть.

Но, изначальная для z80 процедура от b2m, переписка с 8080, оказалась самой быстрой и при этом весьма короткой

Это я не понимаю, с тех пор здесь выложены и более короткие и более быстрые варианты.

[Sayman]

хммм. был не прав. опечатался при расчётах чтоли?
эта процедура 2055 тактов.
эта процедура 1756 тактов.
эта процедура 1586 тактов.
эта процедура 1538 тактов.
эта процедура 1406 тактов.

считал полуавтоматом через эмулятор ZxMak2, у него есть счётчик тактов, им и пользовался. но при изначальном подсчёте где то ошибся (опечатался) и на 1000 тактов пролетел по изначальной процедуре. пересчитал сейчас и заодно остальные процедуры тоже пересчитал. последнюю. где про 15бит, считать не стал, зачем мне 15бит?!

как считал:

		ld hl,0x001f		;реальное значение
		ld de,0xf7df		;размера диска в секторах
		ld bc,0xffef		;максимум кластеров FAT16
		push hl
		push de
		push bc
		call DIV32
		pop bc
		pop de
		pop hl
		push hl
		push de
		push bc
		call DIV32_2
		pop bc
		pop de
		pop hl
		push hl
		push de
		push bc
		call DIV32_3
		pop bc
		pop de
		pop hl
		push hl
		push de
		push bc
		call DIV32_4
		pop bc
		pop de
		pop hl
		push hl
		push de
		push bc
		call DIV32_5

на каждом call остановка, замер тактов в счётчике, выполнение call, снова подсчёт и вычитание первого значения. в расчёте сама call тоже участвует (входит в потраченные такты).
от куда брал для замера значения (делимое, делитель): на этих значениях споткнулась процедура деления, которую я втыкал в утилиту изначально. потом начал пихать другие, они тоже ошибались. Потом нашёл рабочий вариант, но на 4000 тактов. печально. Потом уже вот тут b2m подкинул первую процедуру. значения реальные, взятые с моего винта. поскольку на них произошёл спотык (а я знаю верное значение на выходе, т.к. параллельно на калькуляторе считал для контроля), то их и использовал далее для тестов. может не совсем верное решение, но "я так вижу")))

[ivagor]

Вариант с восстановлением остатка довели до кондиции, теперь вариант без восстановления остатка (не надо верить всему, что писали Гуртовцев и Гудыменко). Раскладка регистров измененная, как в последнем restoring варианте.

Скрытый текст

; BC = HLBC/DE, HL = HLBC%DE
; Non-restoring division
DIVNR32:
		ld a,b
		ld b,16
DIVNR321:
		db 0CBh
		db 031h	;sll c
		rla
		adc hl,hl
		jr c,DIVNR323
		sbc hl,de
		jr c,DIVNR322_
DIVNR321_:
		djnz DIVNR321
DIVNR325:
		db 0CBh
		db 031h	;sll c
		rla
		ld b,a
		ret
DIVNR323:
		ccf
		sbc hl,de
		jr nc,DIVNR322_
		djnz DIVNR321
		jr DIVNR325
		
DIVNR322:
		sla c
		rla
		adc hl,hl
		jr nc,DIVNR324
		add hl,de
		jr c,DIVNR321_
DIVNR322_:
		djnz DIVNR322
DIVNR326:
		sla c
		rla
		ld b,a
		add hl,de
		ret
DIVNR324:
		add hl,de
		jr nc,DIVNR321_
		djnz DIVNR322
		jr DIVNR326

[свернуть]

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

Вероятно финальный вариант без восстановления остатка, по крайней мере у меня идеи вроде иссякли. +5 байт, зато:
1. В большинстве случаев немного быстрее
2. Без недокументированных команд
3. Узкоспециальное достоинство - от этого варианта ближе до версии для 8080

Скрытый текст

; BC = HLBC/DE, HL = HLBC%DE
; Non-restoring division
DIVNR32:
		ld a,b
		call DIVNR32_8
		ex af,af'
		ld a,c
		call DIVNR32_8
		ld c,a
		ex af,af'
		ld b,a
		ret
		
DIVNR32_8:		
		ld b,8
DIVNR321:
		scf
		rla
		adc hl,hl
		jr c,DIVNR323
		sbc hl,de
		jr c,DIVNR322_
DIVNR321_:
		djnz DIVNR321
		scf
		rla
		ret
DIVNR323:
		ccf
		sbc hl,de
		jr nc,DIVNR322_
DIVNR321_2:
		djnz DIVNR321+1
		rla
		ret
		
DIVNR322:
		add a,a
		adc hl,hl
		jr nc,DIVNR324
		add hl,de
		jr c,DIVNR321_2
DIVNR322_:
		djnz DIVNR322
		add a,a
		add hl,de
		ret
DIVNR324:
		add hl,de
		jr nc,DIVNR321_
		djnz DIVNR322
		add a,a
		add hl,de
		ret

[свернуть]