>> If we use the other algorithm, we can reduce the time more than three >> times. >> >> in attache I placed a test-file that contains 'my_ultoa' function. >> >> my_ultoa(12345L, s, 10) requires 924 MCU cycles. >> against ultoa(12345L, s, 10) - 3174
> Yes, but how many cycles does "my_ultoa(99999L, s, 10)" require and how > does that fare against the standard ltoa(99999L, s, 10)? I've tested the worst case ((ulong)-1) and 3999999999, it takes near 1200 MCU. also if we will use two tables: word upto 2^16 and dword upto 2^32 it will take less time. In attache optimized variant: my_ultoa(12345L, s, 10) takes less than 500 MCU and 3999999999 takes less than 1000 >> >> What do You think about this algorithm? > I'm concerned that it might perform badly for very small numbers > compared to the regular ltoa. Also the fact that the time taken by the > algorithm depends a lot on the number (i.e. 99999 takes longer than 11111). > Attached is a version (that I didn't even compile test, to be honest) > that should alleviate the last problem a little and be faster in the > average case, but it is even larger than the original version. It only > works for bases up to 16, though. I'll look through Your code :) -- . ''`. Dmitry E. Oboukhov : :’ : email: [email protected] jabber://[email protected] `. `~’ GPGKey: 1024D / F8E26537 2006-11-21 `- 1B23 D4F8 8EC0 D902 0555 E438 AB8C 00CF F8E2 6537
#ifdef __LINUX_TEST__
#define PROGMEM
#define pgm_read_dword(x) (*(x))
#define pgm_read_word(x) (*(x))
#define pgm_read_byte(x) (*(x))
#else
#include <avr/pgmspace.h>
#endif
static const char letters[] PROGMEM =
"0123456789"
"abcdefghijklmnopqrstuvwxyz";
struct digits {
unsigned long l[5];
unsigned d[6];
};
static const struct digits digits8 PROGMEM = {
.l = {
1073741824,
134217728,
16777216,
2097152,
262144,
},
.d = {
32768,
4096,
512,
64,
8,
1,
}
};
static const struct digits digits10 PROGMEM = {
.l = {
1000000000,
100000000,
10000000,
1000000,
100000,
},
.d = {
10000,
1000,
100,
10,
1,
}
};
static const struct digits digits16 PROGMEM = {
.l = {
268435456,
16777216,
1048576,
65536,
},
.d = {
4096,
256,
16,
1,
}
};
static const struct digits digits32 PROGMEM = {
.l = {
1073741824,
33554432,
1048576,
},
.d = {
32768,
1024,
32,
1,
}
};
static const struct digits digits36 PROGMEM = {
.l = {
2176782336,
60466176,
1679616,
},
.d = {
46656,
1296,
36,
1,
}
};
char * my_ultoa(unsigned long __val, char *__s, int base) {
/* optimizing stack overhead */
union {
unsigned long l;
struct {
unsigned d;
unsigned dv;
};
} check;
const struct digits *d;
unsigned char i, j = 0, k;
switch(base) {
case 8:
d = &digits8;
break;
case 16:
d = &digits16;
break;
case 32:
d = &digits32;
break;
case 36:
d = &digits36;
break;
default:
d = &digits10;
break;
}
if (__val >= (1L << 16)) {
for (i = 0; i < sizeof(d->l) / sizeof(unsigned long); i++) {
check.l = pgm_read_dword(d->l + i);
if (!check.l)
break;
for (k = 0; check.l <= __val; k++)
__val -= check.l;
if (k || j)
__s[j++] = pgm_read_byte(letters + k);
}
}
check.dv = __val;
for(i = 0; i < sizeof(d->d) / sizeof(unsigned); i++) {
check.d = pgm_read_word(d->d + i);
if (!check.d)
break;
for (k = 0; check.d <= check.dv; k++)
check.dv -= check.d;
if (k || j)
__s[j++] = pgm_read_byte(letters + k);
}
if (!j)
__s[j++] = '0';
__s[j] = 0;
return __s;
}
char * my_utoa(unsigned __val, char *__s, int base) {
return my_ultoa(__val, __s, base);
}
char * my_ltoa (long __val, char *__s, int base) {
if (__val >= 0)
return my_ultoa(__val, __s, base);
__s[0] = '-';
return my_ultoa(-__val, __s + 1, base) - 1;
}
char * my_itoa (int __val, char *__s, int base) {
if (__val >= 0)
return my_utoa(__val, __s, base);
__s[0] = '-';
return my_utoa(-__val, __s + 1, base) - 1;
}
signature.asc
Description: Digital signature
_______________________________________________ AVR-libc-dev mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/avr-libc-dev
