Навеяно генераторами Python а (оператор yield)
Просто мысли по поводу оптимальной реализации на С
Обычно (Protothreads, FREERTOS Co-routines)реализуются с помощью макросов которые разворачиваются в примерно такую структуру:
Код
switch(state) {
.....
.....
state = __LINE__; return; case __LINE__:
.....
.....
state = __LINE__; return; case __LINE__:
}
имеют ограничения на локальные переменные и код неоптимальный получается.
Я хочу попробовать сохранять локальные переменные (которые обычно помещаются в регистрах) и восстанавливать их при след. запуске.
Варианты реализации для несложных функций, у которых локальные переменные помещаются в регистрах ( к тому же в примере сохраняются только регистры R24-R27, R4-R5). Оптимизацию надо ставить максимальную по скорости.
(Вариант 1 можно доделать так что бы не было ограничений на количество регистров и локльных переменных в стеке).
uint8_t generator_next(uint8_t) передает параметр очередному шагу генератора и возвращает значение.
Внутри функции генератора – функция uint8_t yield(uint8_t) принимает аргумент для возврата generator_next (результат очередного шага) и возвращает следующий аргумент вызова generator_next (параметр следующего шага).
Эти параметры могут и не использоваться.
Вариант 1:
Для каждого генератора сохраняем указатель на точку входа и локальные переменные ( регистры). При инициализации сохраняем адрес функции ( локальные регистры мусор).
При вызове next сохраняем в стеке указатель на generator_t, обмениваем локальные регистры с сохраненными и переходим по сохраненной точке. При yield вытаскиваем из стека новую точку входа, указатель на generator_t, обмениваем локальные регистры с сохраненными и дальше обычный ret.
реализация generator_next и yield
Код
//обмен регистров R24-R27, R4-R5
swap_locals MACRO
ldd r18, Z+2
ldd r19, Z+3
std Z+2, r24
std Z+3, r25
movw r24, r18
ldd r18, Z+4
ldd r19, Z+5
std Z+4, r26
std Z+5, r27
movw r26, r18
ldd r18, Z+6
ldd r19, Z+7
std Z+6, r4
std Z+7, r5
movw r4, r18
ENDM
RSEG CODE:CODE:NOROOT(1)
PUBLIC generator_next
generator_next:
//сохранение указателя на generator_t
push ZH
push ZL
//обмен регистров
swap_locals
//переход по сохраненному адресу
ldd r18, Z+1
ld ZL, Z
mov ZH, r18
ijmp
PUBLIC yield
yield:
//получение адреса возврата из стека
pop r19
pop r18
//получение сохраненнго указателя на generator_t
pop ZL
pop ZH
//сохранение следующей точки входа
std Z+0, r18
std Z+1, r19
//обмен регистров
swap_locals
ret
Небольшой тест
Код
#include <stdint.h>
#include <stdio.h>
typedef void (__task __version_3 *gfunc_ptr_t)(uint8_t c);
typedef struct {
gfunc_ptr_t entry;
uint8_t saved_regs[6];
}generator_t;
uint8_t yield(uint8_t ret);
__z uint8_t generator_next(generator_t *g, uint8_t val);
static inline void generator_init1(generator_t *g, gfunc_ptr_t entry)
{
g->entry = entry;
}
__task __noreturn
void gen1(uint8_t max)
{
uint8_t i;
uint8_t step;
uint8_t tmp;
step=1;
while(1) {
for(i=0;i<max;i+=step) {
tmp=yield(i);
if (tmp)
step=tmp;
}
}
}
void gen1_test(void)
{
generator_t g;
generator_init1(&g,gen1);
//первый вызов функция с самого начала фактически передается max,
//но возвращает уже 1 значение
printf("%d ",generator_next(&g,10));
printf("%d ",generator_next(&g,0));
printf("%d ",generator_next(&g,6));
printf("%d ",generator_next(&g,0));
printf("%d ",generator_next(&g,0));
printf("%d ",generator_next(&g,3));
printf("%d ",generator_next(&g,0));
printf("%d ",generator_next(&g,0));
}
На выходе получаем 0 1 7 0 6 9 0 3
Неудобство в передаче начальных параметров.
Вариант 2.
generator_t хранит те же данные, функции yield и generator_next такие же.
Но теперь объявляем функцию генератора с первым параметром generator_t в регистре Z (__z) и нужным числом аргументов и в начале функции после нужной инициализации вызывается generator_begin. Для старта генератора просто вызывается функция с начальными аргументами, а уже потом generator_next для получения очередного значения.
При инициализации структуры generator_t просто сохраняется младший байт указателя C_STACK. generator_begin определяет сколько регистров сохранила функция и вытаскивает их из C_STACK ( тут используется особенность IAR обычно использует регистры для локальных переменных в таком порядке R24 R25 R26 R27 R4 R5 …., а сохраняет их в стеке в обратном порядке)
Реализация:
Код
PUBLIC generator_begin
PUBLIC generator_init
generator_init:
//сохраняем текущий C_STACK используется в generator_begin
//для определения кол-ва сохраненных регистров
std Z+2, YL
ret
generator_begin:
//получение адреса возврата из стека
pop r19
pop r18
//сохранение следующей точки входа
st Z+, r18
st Z+, r19
//r0 = кол-во сохраненных регистров
mov r18, YL
ld r0, Z
sub r0, r18
// сохраняем локальные регистры генератора
st Z+, r24
st Z+, r25
st Z+, r26
st Z+, r27
st Z+, r4
st Z+, r5
//восстанавливаем регистры вызвавшей функции (заодно и указатель C_STACK)
breq _ret
ld r24, Y+
dec r0
breq _ret
ld r25, Y+
dec r0
breq _ret
ld r26, Y+
dec r0
breq _ret
ld r27, Y+
dec r0
breq _ret
ld r4, Y+
dec r0
breq _ret
ld r5, Y+
_ret: ret
Небольшой тест
Код
__z uint8_t generator_begin(generator_t *g, uint8_t ret);
__z void generator_init(generator_t *g);
__z uint8_t gen2(generator_t *g, char* buf, uint8_t len)
{
uint8_t i,tmp;
tmp = generator_begin(g,0);
while(1) {
while(tmp!='$')
tmp=yield(0);
i=0;
while( (i<len) && ((tmp=yield(0))!='#'))
buf[i++]=tmp;
tmp = yield(i);
}
}
char buf1[17];
char buf2[5];
__flash const char test[]="$12345$6789#";
void gen2_test(void)
{
generator_t g1;
generator_t g2;
char __flash const *ptr;
char c;
uint8_t len;
generator_init(&g1);
generator_init(&g2);
gen2(&g1,buf1,16);
gen2(&g2,buf2,4);
ptr = test;
while((c=*ptr++)) {
len=generator_next(&g1,c);
if (len) {
buf1[len]=0;
printf("*1* %d:%s\n",(int)len,buf1);
}
len=generator_next(&g2,c);
if (len) {
buf2[len]=0;
printf("*2* %d:%s\n",(int)len,buf2);
}
}
}
На выходе получаем:
*2* 4:1234
*2* 4:6789
*1* 10:12345$6789
Недостаток – очень сильная зависимость от реализации компилятора ( регистры могут использоваться в другом порядке)
реализация легковесных нитей, попытка создать оптимальный аналог Protothreads, FREERTOS Co-routines
May 23 2008, 09:22
