[РЕШЕНО]Простой алгоритм деления целого на 1000.

[kuzulis]

Доброго времени суток.

Имею некую 6-ти байтную переменную (массив), в которой лежит значение времени в миллисекундах, прошедшего от 1970 года.
Значения в массиве хранятся так: байт с индексом 0 - самый старший, байт с индексом 5 - самый младший.

Нужно перевести это значение с секунды, т.е. поделить на 1000.

Но проблема в том, что компилятор (Borland C 3x) поддерживает целый тип максимум 4 байта!

Прочитал гуголь - но там все алгоритмы уж больно общие и сложноваты для первого вхождения (в основном для сверх больших чисел для криптографии).
Может быть, можно как-то поиметь частный случай? (Т.к. делить нужно только на одно конкретное число).
Я "всё" уже перепробовал, мыслей больше нет (чтобы было и просто и быстро).

Может кто внесет новых мыслишек как можно это реализовать?
 

[SimpleSunny]

В целый тип (4 байта), без дополнительных оговорок, все равно не получится.
Сейчас 6 байт (48 разрядов), целочисленно поделить на 1000 (~1024) сдвинуть вправо на 10 разрядов.
Итого значащих будет 38 разряда, а 4 байта (32 разряда).

[kuzulis]

В целый тип (4 байта), без дополнительных оговорок, все равно не получится.
Сейчас 6 байт (48 разрядов), целочисленно поделить на 1000 (~1024) сдвинуть вправо на 10 разрядов.
Итого значащих будет 38 разряда, а 4 байта (32 разряда).

Да, это понятно. До 4х байт (0xFFFFFFFF) секунды с 1970 года будут еще набираться порядка ~100 лет ,
поэтому если поделить 6-ти байтные миллисекунды на 1000 то вполне влезаем в 4 байта.

Вот возникла идея сделать так:

сек = (мсек >> 9) * (512/1000);

При этом,
1. >> 9 эквивалентно целому делению на 512 , т.е. этот результат - целое число
2. результат 512/1000 можно всунуть в float/double.
3. результат СЕК = тоже сделать float/double
4. Но потом как-то нужно преобразовать вещественный CEK в целое число, отбросив всё после запятой.

При таком "раскладе" погрешность составит ~1 сек, что вполне меня устраивает.
Главная проблема в п.4 

[SimpleSunny]

Если не боитесь потери старших битов, можно тогда сделать проще:
int sec = (a[4] + 256 * (a[3] + 256 * (a[2] + 256 * (a[1] + 256 * a[0])))) / 1000;
sec *= 256;

[Fat-Zer]

//оффтоп
а может не думать о 2029-м и остановится на 4-х байтах

//по делу
// подразумеваю, что всё дело происходит на x86
1) старшие 4 байта поставить в правильном порядке и поделить на 1000
2) посчитать остаток от этого
3) остаток сдвинуть на 16 влево и прибавить к младшим двум байтам в правельном порядке
4) поделить (3) на 1000
5) прибавить к результату (1)<<16
всё быстрее плавающей арифметики..

Код

C
unsigned time6le_2sec(char *buff)
{
unsigned h;
unsigned l=0;
unsigned sech;
unsigned secl;
 
(char*)(&h)[3]=buff[0];
(char*)(&h)[2]=buff[1];
(char*)(&h)[1]=buff[2];
(char*)(&h)[0]=buff[3];
sech = h / 1000;
l = (h % 1000) << 16 + buff[4] << 8 + buff[5];
secl = l / 1000;
return secl + sech << 16;
}
 

для систем с ЛЕ алгоритм будет проще, но другой...

ЗЫ: это какой-то драйвер файловой системы?

Если не боитесь потери старших битов, можно тогда сделать проще:
int sec = (a[4] + 256 * (a[3] + 256 * (a[2] + 256 * (a[1] + 256 * a[0])))) / 1000;
sec *= 256;

выходите за разрядную сетку раньше, чем начинаете делить...

[GreatSnake]

Да, это понятно. До 4х байт (0xFFFFFFFF) секунды с 1970 года будут еще набираться порядка ~100 лет ,

С чего это вы взяли? Вообще-то до 19.01.2038.

[Fat-Zer]

Да, это понятно. До 4х байт (0xFFFFFFFF) секунды с 1970 года будут еще набираться порядка ~100 лет ,

С чего это вы взяли? Вообще-то до 19.01.2038.

да... чего-то меня заклинило. В 2029-м будет какой-то другой конец света...

[SimpleSunny]

выходите за разрядную сетку раньше, чем начинаете делить...

Да, ошибся. Можно деление внести в скобки. (:

[Кутенок]

Вот возникла идея сделать так:
сек = (мсек >> 9) * (512/1000);
При этом,
1. >> 9 эквивалентно целому делению на 512 , т.е. этот результат - целое число
2. результат 512/1000 можно всунуть в float/double.
3. результат СЕК = тоже сделать float/double
4. Но потом как-то нужно преобразовать вещественный CEK в целое число, отбросив всё после запятой.

При таком "раскладе" погрешность составит ~1 сек, что вполне меня устраивает.
Главная проблема в п.4  

А что такого в п.4? Чем тебя int(CЕК) не устраивает?

[GreatSnake]

Но потом как-то нужно преобразовать вещественный CEK в целое число, отбросив всё после запятой.

double modf(double x, double *iptr)

[Fat-Zer]

выходите за разрядную сетку раньше, чем начинаете делить...

Да, ошибся. Можно деление внести в скобки. (:

погрешность большая набежит

[brankovic]

почему тогда сразу не посчитать во флоатах? В смысле зачем сдвиги, 512 / 1000 и т.д.?

Код

C++ (Qt)
unsigned char buf [6];
 
double r = 0;
for (int i = 0; i < 6; ++i)
  r = r  * 256 + buf [i];
 
std::cout << (unsigned) (r / 1000) << std::endl;
 

[kuzulis]

почему тогда сразу не посчитать во флоатах? В смысле зачем сдвиги, 512 / 1000 и т.д.?

Да, это всё работает, но медленно!
Я немного переделал под себя:

Код

C
void div_1000_abs_time(u8 *t)
{
    double sec = t[0];
    sec = (sec * 256) + t[1];
    sec = (sec * 256) + t[2];
    sec = (sec * 256) + t[3];
    sec = (sec * 256) + t[4];
    sec = (sec * 256) + t[5];
    sec /= 1000;
    u32 r = u32(sec);
    t[0] = 0x00;
    t[1] = 0x00;
    t[2] = r >> 24;
    t[3] = r >> 16;
    t[4] = r >> 8;
    t[5] = r;
}
 

всё быстрее плавающей арифметики..

Да, я согласен, но это было бы хорошо, если б твой пример адекватно работал, т.е. он правильно дает результат при компиляции MinGW и неправильный при Borland C 3x.
(По крайней мере у меня)
Вот немного измененный твой пример:

Код

C
void div_1000_abs_time2(u8 *t)
{
    u32 h;
    ((u8 *)(&h))[3] = t[0];
    ((u8 *)(&h))[2] = t[1];
    ((u8 *)(&h))[1] = t[2];
    ((u8 *)(&h))[0] = t[3];
 
    u32 sech = h / 1000;
    u32 secl = (h % 1000);
    secl <<= 16;
    secl += (t[4] << 8) + t[5];
    secl /= 1000;
    secl += (sech << 16);
 
    t[0] = 0x00;
    t[1] = 0x00;
    t[2] = secl >> 24;
    t[3] = secl >> 16;
    t[4] = secl >> 8;
    t[5] = secl;
}
 

Например, при делении числа:

0x 01  2d  e7  7d  84  d8

на 1000,
правильный результат должен быть:

0x 00  00  4d  49  98  f7

но оно в борланде даёт:

0x  00  00  4d  49  98  b5

Т.е. почему-то гдето что-то теряет.

ЗЫ: типы данных u8, u16, u32 это:

Код

C
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned long u32;
 

Эх, а так хочется воспользоваться (и проверить на скорость) вариантом Fat-Zer-а

[brankovic]

Да, это всё работает, но медленно!
...
Эх, а так хочется воспользоваться (и проверить на скорость) вариантом Fat-Zer-а

попробуйте ещё столбиком поделить:

Код

C++ (Qt)
unsigned d1000 (unsigned char *buf)
{
   unsigned result = 0, carry = 0, d = 1000, char_bit = 8;
   for (int i = 0; i < 6; ++i, carry <<= char_bit)
   {
      unsigned u = buf [i] + carry;
      result = (result << char_bit) + u / d;
      carry = u % d;
   }
 
   return result;
}
 

[kuzulis]

попробуйте ещё столбиком поделить:

Вот, это уже дело! Спасибо!
Работает в ~два раза быстрее чем с флоатами. А после того как я раскрыл цикл и немного подправил - стало работать еще быстрее:

Код

C
...
#include <limits.h>
...
...
void div_1000_abs_time3(u8 *t)
{
    enum { D = 1000 };
    u32 u = t[0];
    u32 result = (u / D);
    u32 carry = (u % D) << CHAR_BIT;
    u = t[1] + carry;
    result = (result << CHAR_BIT) + (u / D);
    carry = (u % D) << CHAR_BIT;
    u = t[2] + carry;
    result = (result << CHAR_BIT) + (u / D);
    carry = (u % D) << CHAR_BIT;
    u = t[3] + carry;
    result = (result << CHAR_BIT) + (u / D);
    carry = (u % D) << CHAR_BIT;
    u = t[4] + carry;
    result = (result << CHAR_BIT) + (u / D);
    carry = (u % D) << CHAR_BIT;
    u = t[5] + carry;
    result = (result << CHAR_BIT) + (u / D);
    t[0] = 0x00;
    t[1] = 0x00;
    t[2] = result >> 24;
    t[3] = result >> 16;
    t[4] = result >> 8;
    t[5] = result;
}
 

Оставлю скорее всего этот вариант. Благодарю.