Показать число с leading zeros. Опции

[Jenya7]

Мне нужно показать число (счетчик) с leading zeros, 8 позиций.
То есть вместо 1234 показать 00001234.
Делаю так

Код

void LCD_DisplayUpperCounter(uint32_t number)
{
    char strbuf[9] = "";
    ItoA(number, strbuf);
    char str[9] = "";

    if(number<10)
        strcat(str,"0000000");
    else if(number<100)
        strcat(str,"000000");
    else if(number<1000)
        strcat(str,"00000");
    else if(number<10000)
        strcat(str,"0000");
    else if(number<100000)
        strcat(str,"000");
    else if(number<1000000)
        strcat(str,"00");
    else if(number<10000000)
        strcat(str,"0");
    else
    {
        //str = "";
    }

    strcat(str,strbuf);
    LCD_DisplayUpperText(str);
}

Все работает. Вопрос можно ли оптимизировать функцию?

Сообщение отредактировал Jenya7 - Jan 21 2015, 07:39

[SM]

Еще, если Ваш CPU умеет быстро вычислять экспоненту числа, то можно сразу вычислить смещение, куда и делать itoa. Но, это уже вне стандартного С, тут придется работать с интринсиками, и забыть о кроссплатформенности.

Еще, думаю, самый быстрый способ, сделать свой itoa:


char str[9];
int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0};
int p=0;
char *str_p = str;
int i;

while (num_table[p]) {
i=0; while ( (number-=num_table[p]) >= 0) i++;
number += num_table[p++];
*str_p++='0' + i;
}


Извиняюсь, если где ошибся, писал прямо сюда, ни откуда не копировал. И никаких itoa с собой не притащит из либы.
И, добавлю, это быстро, если в процессоре нет аппаратного деления.

[ViKo]

Еще, думаю, самый быстрый способ, сделать свой itoa:

Тем более, что в Keil, например, нет itoa для ARM.
Я сотворил когда-то вот такую функцию для Cortex. Но мне нужно, наоборот, чтобы лидирующие нули не писались. Можно переделать.

Код

void itoad_conv(int32_t numb, char *str)
{
  *(uint32_t *)(str)     = 0x20202020;
  *(uint32_t *)(str + 4) = 0x20202020;    
  *(uint32_t *)(str + 8) = 0x00302020;
  str += 10;
  char  sign = '+';
  if (!numb) return;
  if (numb < 0) { numb = -numb; sign = '-'; }
  do { *str-- = numb % 10 + '0'; } while (numb /= 10);
  *str = sign;
}

[SM]

numb % 10

Вот это - всегда делается за 32 итерации условного вычитания (если деление не аппаратное, да и там оно бывает итеративным), или условного сложения-вычитания (для 32-битного int). Поэтому, это не может быстрее, так как в том, что я предложил, для каждой цифры максимум 10 итераций вычитания, что в три раза меньше в самом худшем случае.

Тем более, что в Keil, например, нет itoa для ARM.

Ой. А это, как? Это же ANSI стандартизованная ф-ция. Обязана быть!

[ViKo]

Ой. А это, как? Это же ANSI стандартизованная ф-ция. Обязана быть!

Нема, зуб даю. Года 4 назад писал об этом здесь же. И эту же программу выкладывал.
itoa - не стандартная функция. Предлагается пользоваться sprintf().

[Jenya7]

я пользуюсь этим

Код

  
void Reverse(char s[])
{
  int c, i, j;

  for (i = 0, j = strlen(s)-1; i < j; i++ , j--)
  {
    c = s[i];
    s[i] = s[j];
    s[j] = c;
  }
  //s[i] = '\0';
}

void ItoA(uint32_t n , char s[])
{
  int i = 0;
  do
  {
    s[i++] = n % 10 + '0';
  }
  while ((n /= 10) >= 1);
   //s[i] = '\0';
  Reverse(s);
}

Сообщение отредактировал Jenya7 - Jan 21 2015, 10:01

[CrimsonPig]

я пользуюсь этим

Код

  
void Reverse(char s[])
{
  int c, i, j;

  for (i = 0, j = strlen(s)-1; i < j; i++ , j--)
  {
    c = s[i];
    s[i] = s[j];
    s[j] = c;
  }
  //s[i] = '\0';
}

void ItoA(uint32_t n , char s[])
{
  int i = 0;
  do
  {
    s[i++] = n % 10 + '0';
  }
  while ((n /= 10) >= 1);
   //s[i] = '\0';
  Reverse(s);
}

Любителям прооптимизировать всякую мутоту на заметку:
1. операция взятия остатка от деления: (n%10) и деления (n/=10) насколько они дешевы ? Поддерживаются ли они на уровне железа процессора ? Можно ли без них обойтись ?
2. В цикле for (i = 0, j = strlen(s)-1; i < j; i++ , j--) есть наивное предположение, что компилятор вынесет strlen(s) за цикл как инвариант. В общем случае неверно. s передается как параметр в функцию и компилятор имеет право решить, что данные строки могут изменяться извне в другом треде, например. Поэтому с чистой совестью может оставить вызов strlen в каждой итерации цикла.
В то время как библиотечные функции (если они есть) все-таки пишутся обычно более качественно.

[Jenya7]

Любителям прооптимизировать всякую мутоту на заметку:
1. операция взятия остатка от деления: (n%10) и деления (n/=10) насколько они дешевы ? Поддерживаются ли они на уровне железа процессора ? Можно ли без них обойтись ?
2. В цикле for (i = 0, j = strlen(s)-1; i < j; i++ , j--) есть наивное предположение, что компилятор вынесет strlen(s) за цикл как инвариант. В общем случае неверно. s передается как параметр в функцию и компилятор имеет право решить, что данные строки могут изменяться извне в другом треде, например. Поэтому с чистой совестью может оставить вызов strlen в каждой итерации цикла.
В то время как библиотечные функции (если они есть) все-таки пишутся обычно более качественно.

так нету библиотечных функций в том то и дело. и более лучшей генерик функции я не нашел.

[SM]

так нету библиотечных функций в том то и дело. и более лучшей генерик функции я не нашел.

То, что я дал код, переделывается на работу без нулей введением одного флага, который сначала запрещен, и разрешается при первом ненулевом символе. И управляет занесением символов в выходной буфер. Все равно шустрее, чем использовать % и /, и, даже шустрее, чем c div_t div(int numer, int denom); (сразу % и / в одном флаконе).


char str[9];
int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0};
int p=0;
char *str_p = str;
int i;
int flag=0;

while (num_table[p]) {
i=0; while ( (number-=num_table[p]) >= 0) i++;
number += num_table[p++];
flag |= i;
if (flag) *str_p++='0' + i;
}

Еще можно дооптимизировать, чтобы условное занесение в буфер убрать из цикла, разделив цикл на две части, ну и убрать флаг.

char str[9];
int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0};
int p=0;
char *str_p = str;
int i;
int flag=0;
int tmp;

if (!num) {
*str_p++='0';
return;
}

while ((tmp=num_table[p++]) && (number < tmp)) ;

do {
i='0'; while ( (number-=tmp) >= 0) i++;
number += tmp;
*str_p++=i;
} while (tmp = num_table[p++]);

[CrimsonPig]

То, что я дал код, переделывается на работу без нулей введением одного флага, который сначала запрещен, и разрешается при первом ненулевом символе. И управляет занесением символов в выходной буфер. Все равно шустрее, чем использовать % и /, и, даже шустрее, чем c div_t div(int numer, int denom); (сразу % и / в одном флаконе).

<зевая> int у нас какой разрядности ?

Я практически отошел от использования "просто int". Гораздо спокойнее писать "uint32_t", "uint16_t", "uint8_t" и не беспокоиться о портабельности кода на машину с другой архитектурой ЦПУ.
А еще я ненавижу знаковый int, и использую int32_t только там, где знак нужет в явном виде.

[SM]

<зевая> int у нас какой разрядности ?

Это пусть автор разбирается. Я предпочитаю соблюдать старые добрые стандарты, где еще нет int32_t.

while ( (number-=num_table[p]) >= 0) всегда true.

Это с какого перепуга? Тип не unsigned.
А если нужен полный диапазон unsigned, то тут, к сожалению, С не покатит, так как нужно условие по флагу переноса после математической операции, что реализуемо только на ассемблере. Оптимизация, штука тонкая....

[Jenya7]

Это пусть автор разбирается. Я предпочитаю соблюдать старые добрые стандарты, где еще нет int32_t.


Это с какого перепуга? Тип не unsigned.
А если нужен полный диапазон unsigned, то тут, к сожалению, С не покатит, так как нужно условие по флагу переноса после математической операции, что реализуемо только на ассемблере. Оптимизация, штука тонкая....

неа. надо допиливать функцию. с uint32_t как раз работает просто надо добавить проверку что число "закончилось".

[SM]

надо добавить проверку что число "закончилось".

Это и есть проверка на это - если число стало отрицательным, значит конец цикла.
Для работы с unsigned это бы показал флаг переноса (carry), к сожалению, средствами С не доступный. Если же Вам хватит положительной части диапазона int32_t на все Ваши случаи, то ничего допиливать не надо, а использовать int32_t, на который рассчитан алгоритм. Если нужен полный диапазон unsigned int - то придется либо написать на ассемблере цикл, либо:

while (number>=num_table[p]) {i++; number-=num_table[p]};

и прибавление number += num_table[p убить. Но это не оптимально, так как сравнение и вычитание, по своей сути, одна и та же операция, то есть, тут операций вдвое больше становится.

для этого существуют debug asserts, тесты и метрики code coverage

для чего? Чтобы оптимально написать алгоритм на С, который на нем оптимально написать невозможно по причине недоступности флага переноса ?

[Jenya7]

Если же Вам хватит положительной части диапазона int32_t на все Ваши случаи, то ничего допиливать не надо, а использовать int32_t, на который рассчитан алгоритм.

и с int32_t не работает

[SM]

и с int32_t не работает

Чего там не работает? Сейчас в MSVC 6.0 собрал для теста, все работает. Только не надо ему давать чисел, имеющих больше десятичных разрядов, чем максимальное в таблице.

CODE

#include "stdio.h"

void ItoA(char * str, int number)
{
int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0};
int p=0;
char *str_p = str;
int i;

while (num_table[p]) {
i='0'; while ( (number-=num_table[p]) >= 0) i++;
number += num_table[p++];
*str_p++=i;
}

*str_p++=0;

}


void ItoA1(char * str, int number)
{
int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0};
int p=0;
char *str_p = str;
int i;
int flag=0;
int tmp;

if (!number) {
*str_p++='0';
*str_p++=0;
return;
}

while ((tmp=num_table[p++]) && (number < tmp)) ;

do {
i='0'; while ( (number-=tmp) >= 0) i++;
number += tmp;
*str_p++=i;
} while (tmp = num_table[p++]);

*str_p++=0;
}

int main(int argc, char* argv[])
{


int i=123456;
char str[16];
char str1[16];

ItoA(str, i);
ItoA1(str1, i);



printf("%s %s\n", str, str1);
return 0;
}

[Jenya7]

Чего там не работает? Сейчас в MSVC 6.0 собрал для теста, все работает. Только не надо ему давать чисел, имеющих больше десятичных разрядов, чем максимальное в таблице.

CODE

#include "stdio.h"

void ItoA(char * str, int number)
{
int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0};
int p=0;
char *str_p = str;
int i;

while (num_table[p]) {
i='0'; while ( (number-=num_table[p]) >= 0) i++;
number += num_table[p++];
*str_p++=i;
}

*str_p++=0;

}


void ItoA1(char * str, int number)
{
int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0};
int p=0;
char *str_p = str;
int i;
int flag=0;
int tmp;

if (!number) {
*str_p++='0';
*str_p++=0;
return;
}

while ((tmp=num_table[p++]) && (number < tmp)) ;

do {
i='0'; while ( (number-=tmp) >= 0) i++;
number += tmp;
*str_p++=i;
} while (tmp = num_table[p++]);

*str_p++=0;
}

int main(int argc, char* argv[])
{


int i=123456;
char str[16];
char str1[16];

ItoA(str, i);
ItoA1(str1, i);



printf("%s %s\n", str, str1);
return 0;
}

офигеть! таки работает!

а вот листинг двух функций

Код

void itoa_with_leading_zeroes(int32_t number, char * str)
{
     f64:    b4b0          push    {r4, r5, r7}
     f66:    b08f          sub    sp, #60; 0x3c
     f68:    af00          add    r7, sp, #0
     f6a:    6078          str    r0, [r7, #4]
     f6c:    6039          str    r1, [r7, #0]
    int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0};
     f6e:    f647 530c     movw    r3, #32012; 0x7d0c
     f72:    f2c0 0300     movt    r3, #0
     f76:    f107 0408     add.w    r4, r7, #8
     f7a:    461d          mov    r5, r3
     f7c:    cd0f          ldmia    r5!, {r0, r1, r2, r3}
     f7e:    c40f          stmia    r4!, {r0, r1, r2, r3}
     f80:    cd0f          ldmia    r5!, {r0, r1, r2, r3}
     f82:    c40f          stmia    r4!, {r0, r1, r2, r3}
     f84:    682b          ldr    r3, [r5, #0]
     f86:    6023          str    r3, [r4, #0]
      int p=0;
     f88:    f04f 0300     mov.w    r3, #0
     f8c:    637b          str    r3, [r7, #52]; 0x34
      char *str_p = str;
     f8e:    683b          ldr    r3, [r7, #0]
     f90:    633b          str    r3, [r7, #48]; 0x30
      int i;

      while (num_table[p])
     f92:    e02c          b.n    fee <itoa_with_leading_zeroes+0x8a>
      {
        i='0';
     f94:    f04f 0330     mov.w    r3, #48; 0x30
     f98:    62fb          str    r3, [r7, #44]; 0x2c
        while ( (number-=num_table[p]) >= 0) i++;
     f9a:    e003          b.n    fa4 <itoa_with_leading_zeroes+0x40>
     f9c:    6afb          ldr    r3, [r7, #44]; 0x2c
     f9e:    f103 0301     add.w    r3, r3, #1
     fa2:    62fb          str    r3, [r7, #44]; 0x2c
     fa4:    6b7b          ldr    r3, [r7, #52]; 0x34
     fa6:    ea4f 0383     mov.w    r3, r3, lsl #2
     faa:    f107 0238     add.w    r2, r7, #56; 0x38
     fae:    18d3          adds    r3, r2, r3
     fb0:    f853 3c30     ldr.w    r3, [r3, #-48]
     fb4:    687a          ldr    r2, [r7, #4]
     fb6:    1ad3          subs    r3, r2, r3
     fb8:    607b          str    r3, [r7, #4]
     fba:    687b          ldr    r3, [r7, #4]
     fbc:    2b00          cmp    r3, #0
     fbe:    daed          bge.n    f9c <itoa_with_leading_zeroes+0x38>
        number += num_table[p++];
     fc0:    6b7b          ldr    r3, [r7, #52]; 0x34
     fc2:    ea4f 0383     mov.w    r3, r3, lsl #2
     fc6:    f107 0238     add.w    r2, r7, #56; 0x38
     fca:    18d3          adds    r3, r2, r3
     fcc:    f853 3c30     ldr.w    r3, [r3, #-48]
     fd0:    687a          ldr    r2, [r7, #4]
     fd2:    18d3          adds    r3, r2, r3
     fd4:    607b          str    r3, [r7, #4]
     fd6:    6b7b          ldr    r3, [r7, #52]; 0x34
     fd8:    f103 0301     add.w    r3, r3, #1
     fdc:    637b          str    r3, [r7, #52]; 0x34
        *str_p++=i;
     fde:    6afb          ldr    r3, [r7, #44]; 0x2c
     fe0:    b2da          uxtb    r2, r3
     fe2:    6b3b          ldr    r3, [r7, #48]; 0x30
     fe4:    701a          strb    r2, [r3, #0]
     fe6:    6b3b          ldr    r3, [r7, #48]; 0x30
     fe8:    f103 0301     add.w    r3, r3, #1
     fec:    633b          str    r3, [r7, #48]; 0x30
    int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0};
      int p=0;
      char *str_p = str;
      int i;

      while (num_table[p])
     fee:    6b7b          ldr    r3, [r7, #52]; 0x34
     ff0:    ea4f 0383     mov.w    r3, r3, lsl #2
     ff4:    f107 0238     add.w    r2, r7, #56; 0x38
     ff8:    18d3          adds    r3, r2, r3
     ffa:    f853 3c30     ldr.w    r3, [r3, #-48]
     ffe:    2b00          cmp    r3, #0
    1000:    d1c8          bne.n    f94 <itoa_with_leading_zeroes+0x30>
        while ( (number-=num_table[p]) >= 0) i++;
        number += num_table[p++];
        *str_p++=i;
      }

      *str_p++=0;
    1002:    6b3b          ldr    r3, [r7, #48]; 0x30
    1004:    f04f 0200     mov.w    r2, #0
    1008:    701a          strb    r2, [r3, #0]
    100a:    6b3b          ldr    r3, [r7, #48]; 0x30
    100c:    f103 0301     add.w    r3, r3, #1
    1010:    633b          str    r3, [r7, #48]; 0x30
}

68 инструкций.

и мой старый метод

Код

void ItoA(uint32_t n , char s[])
{
     ef4:    b580          push    {r7, lr}
     ef6:    b084          sub    sp, #16
     ef8:    af00          add    r7, sp, #0
     efa:    6078          str    r0, [r7, #4]
     efc:    6039          str    r1, [r7, #0]
  int i = 0;
     efe:    f04f 0300     mov.w    r3, #0
     f02:    60fb          str    r3, [r7, #12]
  do
  {
    s[i++] = n % 10 + '0';
     f04:    68fb          ldr    r3, [r7, #12]
     f06:    683a          ldr    r2, [r7, #0]
     f08:    18d0          adds    r0, r2, r3
     f0a:    6879          ldr    r1, [r7, #4]
     f0c:    f64c 43cd     movw    r3, #52429; 0xcccd
     f10:    f6cc 43cc     movt    r3, #52428; 0xcccc
     f14:    fba3 2301     umull    r2, r3, r3, r1
     f18:    ea4f 02d3     mov.w    r2, r3, lsr #3
     f1c:    4613          mov    r3, r2
     f1e:    ea4f 0383     mov.w    r3, r3, lsl #2
     f22:    189b          adds    r3, r3, r2
     f24:    ea4f 0343     mov.w    r3, r3, lsl #1
     f28:    1aca          subs    r2, r1, r3
     f2a:    b2d3          uxtb    r3, r2
     f2c:    f103 0330     add.w    r3, r3, #48; 0x30
     f30:    b2db          uxtb    r3, r3
     f32:    7003          strb    r3, [r0, #0]
     f34:    68fb          ldr    r3, [r7, #12]
     f36:    f103 0301     add.w    r3, r3, #1
     f3a:    60fb          str    r3, [r7, #12]
  }
  while ((n /= 10) >= 1);
     f3c:    687a          ldr    r2, [r7, #4]
     f3e:    f64c 43cd     movw    r3, #52429; 0xcccd
     f42:    f6cc 43cc     movt    r3, #52428; 0xcccc
     f46:    fba3 1302     umull    r1, r3, r3, r2
     f4a:    ea4f 03d3     mov.w    r3, r3, lsr #3
     f4e:    607b          str    r3, [r7, #4]
     f50:    687b          ldr    r3, [r7, #4]
     f52:    2b00          cmp    r3, #0
     f54:    d1d6          bne.n    f04 <ItoA+0x10>
   //s[i] = '\0';
  Reverse(s);
     f56:    6838          ldr    r0, [r7, #0]
     f58:    f7ff ff9a     bl    e90 <Reverse>
}

void Reverse(char s[])
{
  int c, i, j;

  for (i = 0, j = strlen(s)-1; i < j; i++ , j--)
     ed4:    697b          ldr    r3, [r7, #20]
     ed6:    f103 0301     add.w    r3, r3, #1
     eda:    617b          str    r3, [r7, #20]
     edc:    693b          ldr    r3, [r7, #16]
     ede:    f103 33ff     add.w    r3, r3, #4294967295
     ee2:    613b          str    r3, [r7, #16]
     ee4:    697a          ldr    r2, [r7, #20]
     ee6:    693b          ldr    r3, [r7, #16]
     ee8:    429a          cmp    r2, r3
     eea:    dbe0          blt.n    eae <Reverse+0x1e>
    c = s[i];
    s[i] = s[j];
    s[j] = c;
  }
  //s[i] = '\0';
}

38+10 = 48 инструкций.

Выбирайте!
---
Упс, уже дали эту ссылку

да. CrimsonPig давал уже эту ссылку. есть интересное решение. надо проверить.

в принципе int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0}; можно вынести из тела функции...

Сообщение отредактировал Jenya7 - Jan 21 2015, 14:23

[CrimsonPig]

в принципе int num_table[9] = {10000000, 1000000,100000,10000,1000,100,10,1,0}; можно вынести из тела функции...

Зачем ? Засорять пространство имен всякими локальными именами - очень плохая идея.
Объявите этот массив внутри функции как
const int num_table[9] = {...}
Хотя нормальный компилятор и так должен был догадаться, что это константы.

[SM]

const int num_table[9] = {...}

не const, а static. Да, это мое упущение. Этому на стеке не место.

Вот что генерирует TI CCS из последнего кода (16 инструкций):

CODE

_ItoA:
;* --------------------------------------------------------------------------*
LDR V9, $C$CON1 ; |11|
.dwpsn file "ccs.c",line 12,column 0,is_stmt
LDR A4, [V9, #0] ; |11|
;* --------------------------------------------------------------------------*
;* BEGIN LOOP ||$C$L1||
;*
;* Loop source line : 12
;* Loop closing brace source line : 16
;* Known Minimum Trip Count : 1
;* Known Maximum Trip Count : 4294967295
;* Known Max Trip Count Factor : 1
;* --------------------------------------------------------------------------*
||$C$L1||:
$C$DW$L$_ItoA$2$B:
SUBS A2, A2, A4 ; |13|
MOV A3, #48 ; |13|
BMI ||$C$L3|| ; |13|
; BRANCHCC OCCURS {||$C$L3||} ; |13|
$C$DW$L$_ItoA$2$E:
;* --------------------------------------------------------------------------*
;* BEGIN LOOP ||$C$L2||
;*
;* Loop source line : 13
;* Loop closing brace source line : 13
;* Known Minimum Trip Count : 1
;* Known Maximum Trip Count : 4294967295
;* Known Max Trip Count Factor : 1
;* --------------------------------------------------------------------------*
||$C$L2||:
$C$DW$L$_ItoA$3$B:
.dwpsn file "ccs.c",line 13,column 0,is_stmt
SUBS A2, A2, A4 ; |13|
ADD A3, A3, #1 ; |13|
BPL ||$C$L2|| ; |13|
; BRANCHCC OCCURS {||$C$L2||} ; |13|
$C$DW$L$_ItoA$3$E:
;* --------------------------------------------------------------------------*
||$C$L3||:
$C$DW$L$_ItoA$4$B:
STRB A3, [A1], #1 ; |15|
ADD A2, A4, A2 ; |14|
LDR A4, [V9, #4]! ; |16|
CMP A4, #0 ; |16|
.dwpsn file "ccs.c",line 16,column 0,is_stmt
BNE ||$C$L1|| ; |16|
; BRANCHCC OCCURS {||$C$L1||} ; |16|
$C$DW$L$_ItoA$4$E:
;* --------------------------------------------------------------------------*
MOV V9, #0 ; |18|
STRB V9, [A1, #0] ; |18|
.dwpsn file "ccs.c",line 20,column 1,is_stmt
$C$DW$4 .dwtag DW_TAG_TI_branch
.dwattr $C$DW$4, DW_AT_low_pc(0x00)
.dwattr $C$DW$4, DW_AT_TI_return
BX LR
; BRANCH OCCURS {LR}