Может поменять местами трюки с байтовой маской и многобайтовым логическим сдвигом на 4 намного быстрее, чем наивный метод использования цепочек битового сдвига.

Я пишу алгоритм с фиксированной точкой (16Q16), который выполняет деление с использованием метода Ньютона – Рафсона , описанный в Википедии. (Связанный вопрос SE ЗДЕСЬ.)

Первый шаг требует логического сдвига вправо на 1–16 бит. Мой процессор представляет собой 8-битный микроконтроллер, поэтому у меня нет переключателя передач; оборудование может поддерживать сдвиг только на 1 бит. (Связанный вопрос SE ЗДЕСЬ.) Для сдвига на n бит можно использовать команду одинарного сдвига n раз, однако это имеет значительную синхронизацию наихудшего случая. Этот плохой наихудший случай становится ужасным, если усугубляется многобайтовой природой сдвига. Если для сдвига 1 байта 1 раз требуется 1 цикл, мы можем быстро представить себе проблему, когда нужно сдвинуть 16 байтов 16 раз. Помните, что это всего лишь шаг 1.

Очевидная оптимизация - разделять и властвовать; вычислить вручную для всех степеней 2. Первый, тривиальный случай - сдвиг на 16 и 8, поскольку это просто изменение индекса памяти на число с фиксированной точкой. Для этого требуется всего ~ 4 цикла / инструкции для сдвига 16 байтов на 16 бит, что в 64 раза больше по сравнению с цепочкой с одним сдвигом.

Проблема, с которой я столкнулся, - это надоедливые сдвиги на 4.

Моя интуиция, а также несколько фрагментов и сообщений здесь и там подсказывают мне, что существует эффективный способ объединить инструкции быстрой замены с битовыми масками и логическими операциями, чтобы создать своего рода эффект застежки-молнии с быстрой заменой, который может оптимально сдвинуть произвольный длина массива по 4 бита. (Связанный вопрос SE ЗДЕСЬ. Ссылки на ответ 3)

Я ЗНАЮ, что это можно сделать, по крайней мере, фундаментально, потому что я хорошо разбираюсь в концепциях, использующих только инструкции SWAP, XOR и AND. Я также знаю, что это можно сделать БЫСТРЕЕ, потому что то, что у меня есть, на один цикл быстрее (смеется, да, на один), чем простой метод цепочки сдвигов. (см. поле кода ниже) Я не знаю ...

Можно ли это сделать с временной сложностью, намного более близкой к одному циклу на байт, чем к одному циклу на бит, используя какой-либо трюк с маской байта подкачки nybble?

Примечание: это PIC18 ASM, но довольно очевидно, что происходит. Любые предложения о том, как это можно значительно улучшить, будут ответом на этот вопрос. ДА! Я понимаю, что это вполне может быть уже близко к оптимальному, но понимаю, что сдвиг на 4 - это повторяющаяся горячая точка в нескольких частях кода. Я ожидаю вырезать хотя бы одну инструкцию из каждого блока. Вырезать два было бы потрясающе.

; Shift the denominator -> 4 (19 cyc)
;------------------------------------------
        SWAPF   Denom+3, W, BANKED
        MOVWF   Denom+3, BANKED
        ANDLW   0xF0
        XORWF   Denom+3, F, BANKED

        SWAPF   Denom+2, F, BANKED
        XORWF   Denom+2, F, BANKED
        XORWF   Denom+2, W, BANKED
        ANDLW   0xF0
        XORWF   Denom+2, F, BANKED

        SWAPF   Denom+1, F, BANKED
        XORWF   Denom+1, F, BANKED
        XORWF   Denom+1, W, BANKED
        ANDLW   0xF0
        XORWF   Denom+1, F, BANKED

        SWAPF   Denom+0, F, BANKED
        XORWF   Denom+0, F, BANKED
        XORWF   Denom+0, W, BANKED
        ANDLW   0xF0
        XORWF   Denom+0, F, BANKED
;------------------------------------------