воскресенье, 5 июня 2022 г.

Эмуляция инструкций CLZ и CTZ для Cortex-M23

Вылезла проблема эффективной реализации операции CLZ, потому что на ядре Cortex-M23 она не поддерживатся. В тоже время есть тонны кода для Cortex-M3/M4 с использованием инструкции CLZ.
Я изучил в доступных источниках и не нашел хорошей реалиазации. Мне нужна эффективная реализация этой операции, потому что на ней основана одна из основных функций -- выделение памяти и работа с флагами. Решил, что надо самому подобрать такую реализацию.

static	const uint8_t lut[16]= {4, 3, 2, 2, 1, 1, 1, 1};
int clz_u32(uint32_t a)
{
	int i = 28;
	if((a>>16)!=0) a>>=16,i-=16;
	if((a>> 8)!=0) a>>=8, i-=8;
	if((a>> 4)!=0) a>>=4, i-=4;
	return i + lut[a];
}
Еще одна реализация. Можно таблицу подстановки представить конструкцией switch.

int _clz_u32(uint32_t r0)
{
	int i=28;
	uint32_t b;
	if ((b = r0>>16) != 0) r0=b, i-=16;
	if ((b = r0>>8 ) != 0) r0=b, i-=8;
	if ((b = r0>>4 ) != 0) r0=b, i-=4;
	switch(r0 & 0xF) {
	case 0: b=4; break;
	case 1: b=3; break;
	case 2 ... 3: b=2; break;
	case 4 ... 7: b=1; break;
	default:b=0; break;
	}
	return i + b;//lut[r0];
}
Дальше занялся исследованием кода, который производися компилятором (#gcc -O3 -S).
Руками выполнил оптимизацию за компияторм, чтобы код стал компактнее. Оптимизация - обращене к таблице подстановки с использованием инструкции ADR.
__clzsi2:
        movs    r3, #28 // i=28

        lsrs    r2, r0, #16
        cbz     r2, 1f
        movs    r0, r2
        subs    r3, r3, #16
1:
        lsrs    r2, r0, #8
        cbz     r2, 1f
        movs    r0, r2
        subs    r3, r3, #8
1:
        lsrs    r2, r0, #4
        cbz     r2, 1f
        movs    r0, r2
        subs    r3, r3, #4
1:
        adr     r2, 1f
        ldrb    r0, [r2, r0]
        adds    r0, r0, r3
        bx      lr
	.align 2
1:
	.byte 4, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0
Это пожалуй самая эффективная реализация. Затем подобрал аналогичным образом реализацию для CTZ.

static	const uint8_t lut_ctz[16]= {4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};
int _ctz_u32(uint32_t a)
{
	int i = 28;
	if((a<<16)!=0) a<<=16,i-=16;
	if((a<< 8)!=0) a<<=8, i-=8;
	if((a<< 4)!=0) a<<=4, i-=4;
	return i + lut_ctz[a>>28];
}
__ctzsi2:
        movs    r3, #28

        lsls    r2, r0, #16
        cbz     r2, 1f
        movs    r0, r2
        subs    r3, r3, #16
1:
        lsls    r2, r0, #8
        cbz     r2, 1f
        movs    r0, r2
        subs    r3, r3, #8
1:
        lsls    r2, r0, #4
        cbz     r2, 1f
        movs    r0, r2
        subs    r3, r3, #4
1:
        lsrs    r0, r0, #28
        adr     r2, 1f
        ldrb    r0, [r2, r0]
        adds    r0, r0, r3
        bx      lr
	.align 2
1:
	.byte 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
[ARM DDI0550] ARM Cortex-M23 Processor Technical Reference Manual

Комментариев нет:

Отправить комментарий