Насыщение
От: AcidTheProgrammer Россия https://hts.tv/
Дата: 10.06.05 13:27
Оценка:
Подскажите пожалуйста быстрый метод реализации сложение с насыщением

тоесть есть граница например 2^N, так что бы в случае выхода за пределы максимального значения результат был максимумом.

Например

240 + 60 = 255. если граница равна 255

Нужна реализация без IFа

MMX — не предлагать
Re: Насыщение
От: Кодт Россия  
Дата: 10.06.05 13:55
Оценка:
Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>Нужна реализация без IFа

ATP>MMX — не предлагать

А что предлагать? От языка зависит.

Можно, например, так:
unsigned int data[count];
unsigned int sum=0, over=0;
unsigned int mask = (~0)<<N; // все старшие биты, начиная с N

for(int i=0; i<count; ++i)
{
  sum += data[i];
  over |= (sum & mask);
}

// один-единственный if на весь набор:
if(over)
  sum = (1<<N);
Перекуём баги на фичи!
Re[2]: Насыщение
От: _DAle_ Беларусь  
Дата: 10.06.05 14:25
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, AcidTheProgrammer, Вы писали:


ATP>>Нужна реализация без IFа

ATP>>MMX — не предлагать

К>А что предлагать? От языка зависит.


К>Можно, например, так:

К>
К>unsigned int data[count];
К>unsigned int sum=0, over=0;
К>unsigned int mask = (~0)<<N; // все старшие биты, начиная с N

К>for(int i=0; i<count; ++i)
К>{
К>  sum += data[i];
К>  over |= (sum & mask);
К>}

К>// один-единственный if на весь набор:
К>if(over)
К>  sum = (1<<N);
К>


Можно подправить, чтобы избавиться от if
    unsigned int data[count];
    unsigned int sum[2], over=0;
    sum[0] = 0;
    sum[1] = 1<<N;
    unsigned int mask = (~0)<<N; 

    for(int i=0; i<count; ++i)
    {
      sum[0] += data[i];
      over |= (sum[0] & mask);
    }

    unsigned int result = sum[(bool) over];
    std::cout << result;


Но мне кажется, что просили немножко другое.
... << RSDN@Home 1.1.4 beta 7 rev. 447>>
Re[3]: Насыщение
От: Кодт Россия  
Дата: 10.06.05 15:04
Оценка: 7 (2)
Здравствуйте, _DAle_, Вы писали:

_DA>Можно подправить, чтобы избавиться от if

_DA>    unsigned int result = sum[(bool) over];

Это тот же if, только хорошо спрятанный.

_DA>Но мне кажется, что просили немножко другое.


Почему? Может быть, потребовалось написать векторное выражение. Что-то вроде
суммироватьСОграничением(Набор) = суммировать(НаборЧисел,хитраяОперацияСуммирования)


А вот, кстати, я придумал эту хитрую функцию...
template<unsigned N>
inline unsigned saturated_plus(unsigned x, unsigned y)
{
  STATIC_ASSERT(N < CHAR_BITS*sizeof(unsigned)); // т.е. не вылезаем из разрядной сетки и ещё оставляем старший бит незадействованным
  unsigned const highbit = 1<<N; // 1000...0b
  ASSERT(x < highbit);
  ASSERT(y < highbit);
  unsigned sum = x+y; // sum < highbit*2
  unsigned carry = sum & highbit;
  unsigned flood = carry-1; // либо все нули, либо все единицы
  unsigned result = (sum & ~highbit) | flood; // бит переноса обнуляем, биты данных заливаем
  return result;
}

или, в одну строку,
template<unsigned N>
inline unsigned saturated_plus(unsigned x, unsigned y)
{
  return ((x+y)&~(1<<N)) | (((x+y)&(1<<N))-1);
}
Перекуём баги на фичи!
Re[2]: Насыщение
От: AcidTheProgrammer Россия https://hts.tv/
Дата: 10.06.05 17:26
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, AcidTheProgrammer, Вы писали:


ATP>>Нужна реализация без IFа

ATP>>MMX — не предлагать

К>А что предлагать? От языка зависит.


К>Можно, например, так:

К>
К>unsigned int data[count];
К>unsigned int sum=0, over=0;
К>unsigned int mask = (~0)<<N; // все старшие биты, начиная с N

К>for(int i=0; i<count; ++i)
К>{
К>  sum += data[i];
К>  over |= (sum & mask);
К>}

К>// один-единственный if на весь набор:
К>if(over)
К>  sum = (1<<N);
К>


Способ понятен, но If всеравно есть. У меня в цикле всего одно сложение, тоесть нет аккамулятора как у вас.
Наприме: представте операцию повышения яркости на ихображении — ко всем точкам прибавляется константа, но результат не должен переходить за 255.

Нужно что в этом случае бех if работало (сейчас пока используется max (x, y). MMX использовать не могу)
Re[3]: Насыщение
От: Кодт Россия  
Дата: 11.06.05 09:19
Оценка:
Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>Способ понятен, но If всеравно есть. У меня в цикле всего одно сложение, тоесть нет аккамулятора как у вас.

ATP>Наприме: представте операцию повышения яркости на ихображении — ко всем точкам прибавляется константа, но результат не должен переходить за 255.

ATP>Нужно что в этом случае бех if работало (сейчас пока используется max (x, y). MMX использовать не могу)


Я выше написал ответ без иф.
unsigned const highbit = 1<<N;
inline unsigned adds(unsigned x, unsigned y) { return (x+y)&~highbit | ((x+y)&highbit-1); }

// нахождение суммы с ограничением
unsigned sum = 0;
for(i=0; i<count; ++i)
  sum = adds(sum,x[i]);

// инкремент с ограничением
unsigned delta;
for(i=0; i<count; ++i)
  x[i] = adds(x[i],delta);

А вообще, если ты делаешь какую-то быструю операцию наподобие обработки изображения — то или пользуйся спецсредствами (ассемблер), или бери в руки профайлер и выясняй, что является узким местом. Будет ли им ветвление или же вычисление громоздкого выражения — загадка.

Для суммы, мне кажется, дешевле всего сделать так:
— взять сумматор с разрядностью, достаточной, чтобы сложить все слагаемые набора
— суммировать (в цикле) без заморочек
— один раз поветвиться, либо родить хитрое выражение над битами.
Перекуём баги на фичи!
Re: Насыщение
От: ansi  
Дата: 11.06.05 10:46
Оценка:
Здравствуйте, AcidTheProgrammer, Вы писали:

Если тебе нужна вся разрядность, то только асм:

int main(int argc, char* argv[])
{
   unsigned a = 1, b = 0xFFFFFFFF, c;

   // unsigned +
   __asm {
      xor ebx, ebx
      not ebx

      mov eax, a
      add eax, b
      cmovc eax, ebx
      mov c, eax
   };

   std::cout << c << "\r\n";

    // unsigned -
   __asm {
      xor ebx, ebx
      mov eax, a
      sub eax, b
      cmovc eax, ebx
      mov c, eax
   };

   std::cout << c << "\r\n";

   return 0;
}


Если неполная разрядность, то Кодт уже любезно предоставил. А если еще и знаковое насыщение, то ... это посложнее будет.
Команды условной загрузки (CMOVcc) вроде как не на всех процах есть, однако такое "чудо" еще надо постараться найти... Вот с Итаниумом проще — там любая команда может быть условной. Эх, когда же наконец вымрет этот x86...
new RSDN@Home(1.1.4, 303) << new Message(); std::head::ear << "Apocalyptica — Nothing Else Matters";
Re[3]: Насыщение
От: WinterMute Россия http://yarrr.ru
Дата: 11.06.05 12:37
Оценка:
ATP>Способ понятен, но If всеравно есть. У меня в цикле всего одно сложение, тоесть нет аккамулятора как у вас.
ATP>Наприме: представте операцию повышения яркости на ихображении — ко всем точкам прибавляется константа, но результат не должен переходить за 255.

ATP>Нужно что в этом случае бех if работало (сейчас пока используется max (x, y). MMX использовать не могу)


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

void Brightness( Img& img, int level )
{
    unsigned char cache[256];
    
    // кэширование
    for( int i = 0; i< 256; i++ )
    {
        int res = i + level;
        if( res < 0 ) cache[i] = 0;
        if( res > 255 ) cache[i] = 255
        else cache[i] = (unsigned char)res;
    }

    // повышение яркости
    for( int y = 0; y < img.H(); y++ )
    for( int x = 0; y < img.W(); x++ )
    {
        img.pixel( x, y ).R() = cache[ img.pixel( x, y ).R() ];
        img.pixel( x, y ).G() = cache[ img.pixel( x, y ).G() ];
        img.pixel( x, y ).B() = cache[ img.pixel( x, y ).B() ];
    }
}


Разумеется, это оправдано для изображений содержащих более 256/3 точек.
Re[4]: Насыщение
От: Аноним  
Дата: 12.06.05 07:04
Оценка:
Здравствуйте, WinterMute, Вы писали:

ATP>>Способ понятен, но If всеравно есть. У меня в цикле всего одно сложение, тоесть нет аккамулятора как у вас.

ATP>>Наприме: представте операцию повышения яркости на ихображении — ко всем точкам прибавляется константа, но результат не должен переходить за 255.

ATP>>Нужно что в этом случае бех if работало (сейчас пока используется max (x, y). MMX использовать не могу)


WM>Если тебе нужно оптимизировать повышение яркости, то проще всего сделать кэширование.


WM>
WM>void Brightness( Img& img, int level )
WM>{
WM>    unsigned char cache[256];
    
WM>    // кэширование
WM>    for( int i = 0; i< 256; i++ )
WM>    {
WM>        int res = i + level;
WM>        if( res < 0 ) cache[i] = 0;
WM>        if( res > 255 ) cache[i] = 255
WM>        else cache[i] = (unsigned char)res;
WM>    }

WM>    // повышение яркости
WM>    for( int y = 0; y < img.H(); y++ )
WM>    for( int x = 0; y < img.W(); x++ )
WM>    {
WM>        img.pixel( x, y ).R() = cache[ img.pixel( x, y ).R() ];
WM>        img.pixel( x, y ).G() = cache[ img.pixel( x, y ).G() ];
WM>        img.pixel( x, y ).B() = cache[ img.pixel( x, y ).B() ];
WM>    }
WM>}
WM>


WM>Разумеется, это оправдано для изображений содержащих более 256/3 точек.


Спасибо, но это первое что мне в голову пришло сделать — LookupTable. Просто сечас рассматриваю тругие варианты. Пример с яркостью это я так привел, на самом деле в моем млучае сложение практически 32х разрядное, поэтому уж очеь большая таблица должна быть.
Re[4]: Насыщение
От: AcidTheProgrammer Россия https://hts.tv/
Дата: 12.06.05 07:16
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, AcidTheProgrammer, Вы писали:


ATP>>Способ понятен, но If всеравно есть. У меня в цикле всего одно сложение, тоесть нет аккамулятора как у вас.

ATP>>Наприме: представте операцию повышения яркости на ихображении — ко всем точкам прибавляется константа, но результат не должен переходить за 255.

ATP>>Нужно что в этом случае бех if работало (сейчас пока используется max (x, y). MMX использовать не могу)


К>Я выше написал ответ без иф.

К>
К>unsigned const highbit = 1<<N;
К>inline unsigned adds(unsigned x, unsigned y) { return (x+y)&~highbit | ((x+y)&highbit-1); }

К>// нахождение суммы с ограничением
К>unsigned sum = 0;
К>for(i=0; i<count; ++i)
К>  sum = adds(sum,x[i]);

К>// инкремент с ограничением
К>unsigned delta;
К>for(i=0; i<count; ++i)
К>  x[i] = adds(x[i],delta);
К>

К>А вообще, если ты делаешь какую-то быструю операцию наподобие обработки изображения — то или пользуйся спецсредствами (ассемблер), или бери в руки профайлер и выясняй, что является узким местом. Будет ли им ветвление или же вычисление громоздкого выражения — загадка.

К>Для суммы, мне кажется, дешевле всего сделать так:

К>- взять сумматор с разрядностью, достаточной, чтобы сложить все слагаемые набора
К>- суммировать (в цикле) без заморочек
К>- один раз поветвиться, либо родить хитрое выражение над битами.

Спасибо, но у меня есть ожно но: насколько я понимаю по формуле у вас граница включается в диаппзон, а мне нужно что б не включалас, последнее число было бы 255 в случае 2^8
Re[5]: Насыщение
От: Кодт Россия  
Дата: 13.06.05 10:02
Оценка:
Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>Спасибо, но у меня есть ожно но: насколько я понимаю по формуле у вас граница включается в диаппзон, а мне нужно что б не включалас, последнее число было бы 255 в случае 2^8


Обычно системы команд процессоров позволяют эффективно работать с флагом переноса. Т.е. если сумма вылезла из разрядной сетки, то взводится CarryFlag, который можно быстро превратить в маску (например, через вычитание с заёмом, subtract with borrow). Выше уже привели код.

В чистом же Си такой фокус нахаляву невозможен — придётся или пользоваться арифметикой бОльшей разрядности, или прибегать к разным трюкам.
Конечно, изобрести что-нибудь этакое можно, но компилятор вряд ли сможет оптимизировать до xor,add,cmovc.

На каких целевых платформах будет работать твоя программа, ты знаешь? Вряд ли более чем на двух-трёх разных.
Сделай к ним ассемблерные вставки, а для остальных напиши обходное решение (хоть с ветвлением, хоть с масками).

Один из способов вписаться в разрядную сетку — это разбить сетку на две части и выполнить операции над частями чисел.
x = xh*K + xl
y = yh*K + yl
где K — степень 2
x+y = (xh+yh)*K + (xl+yl)
в этом случае можно отследить переносы из каждой суммы вверх. И если в итоге будет перенос, то превращаем его в маску.
typedef unsigned int inttype; // выбранный нами тип
int const R = sizeof(inttype)*CHAR_BIT; // разрядная сетка

inttype const L = R/2; // разрядность младшей части
   // в общем-то, без разницы, чему оно равно. Главное, чтобы было строго 0<L<R
inttype const H = R-L; // разрядность старшей части

inttype const ML = (1<<L)-1; // маска младшей части
inttype const MH = (1<<H)-1; // маска старшей части

inttype x, y;

inttype xl = x&ML, xh = x>>L;
inttype yl = y&ML, yh = y>>L;

inttype tl = (xl+yl);
inttype sl = tl&ML, cl = tl>>L; // сумма и перенос младших частей

inttype th = (xh+yh+cl);
inttype sh = th&MH, ch = th>>H; // сумма и перенос старших частей (с переносом из нижних)

inttype s = (sh<<L) | sl; // сумма
inttype m = // ch==0 ? 0 : ~0 // маска
            (((ch<<(R-1))-1)<<1)|ch;
inttype t = s|m;

Затейливая форма для получения маски объясняется так:
                          <---R--->
   ch                   = 000...001
   ch<<(R-1)            = 100...000
  (ch<<(R-1))-1         = 011...111
 ((ch<<(R-1))-1)<<1     = 111...110
(((ch<<(R-1))-1)<<1)|ch = 111...111

(для ch==0, очевидно, результат будет равен 0).

Как из этого всего сделать одно здоровенное выражение — оставляю любителям обфускации.
Перекуём баги на фичи!
Re: IMHO, ...
От: Аноним  
Дата: 14.06.05 04:22
Оценка:
... для длинных чисел с if'ом всё равно будет быстрее.
Re: Насыщение
От: minorlogic Украина  
Дата: 14.06.05 06:08
Оценка:
Здравствуйте, AcidTheProgrammer, Вы писали:

Если задача действительно так важна , со советую посмотреть как это реализованов IPP
Intel Performance Primitives
Ищу работу, 3D, SLAM, computer graphics/vision.
Re: Насыщение
От: Ranger_XL  
Дата: 14.06.05 08:15
Оценка:
ATP>Подскажите пожалуйста быстрый метод реализации сложение с насыщением

Завести матрицу 255х255 всевозможных комбинаций исходных данных и просчитать сумму заранее
Re: Насыщение
От: AcidTheProgrammer Россия https://hts.tv/
Дата: 14.06.05 08:35
Оценка:
Спасибо болшле за посты, но все не то,
хотелось бы уточнить:

1. Складываю 28 битные целые (четверка бит в запасе есть)
2. Таблица не подходит — лобовой вариант, но слишком она уж большая в моем случае
3. Ассемблер не подходит — ясно что аппратно все просто реализуется, но нельзя по заданию
4. Суммирую не несколько значений в один аккамулятор, а много (НАПРИМЕР также как с случае с увеличением яркости).
5. Граница должна задаваться в виде 2^N но не включительно, тоесть в случае 2^16 последнее число должно быть 65535

С учетом этих требование есть ли какие-нибудь метоты?
Re[6]: Насыщение
От: conraddk Россия  
Дата: 14.06.05 08:48
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Затейливая форма для получения маски объясняется так:

К>
К>                          <---R--->
К>   ch                   = 000...001
К>   ch<<(R-1)            = 100...000
К>  (ch<<(R-1))-1         = 011...111
К> ((ch<<(R-1))-1)<<1     = 111...110
К>(((ch<<(R-1))-1)<<1)|ch = 111...111
К>

К>(для ch==0, очевидно, результат будет равен 0).
Интересная штука была бы, а не получается Смотрим для ch=0:
   ch                   = 000...000
   ch<<(R-1)            = 000...000
  (ch<<(R-1))-1         = 111...111 (!)
 ((ch<<(R-1))-1)<<1     = 111...110
(((ch<<(R-1))-1)<<1)|ch = 111...110

Только ширина здесь не R бит, а сколько там помещается в представление ch.
... << RSDN@Home 1.1.4 beta 5 rev. 395>>
Все на свете должно происходить медленно и неправильно...
Re[2]: Насыщение
От: Кодт Россия  
Дата: 14.06.05 09:23
Оценка: +1
Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>1. Складываю 28 битные целые (четверка бит в запасе есть)

ATP>2. Таблица не подходит — лобовой вариант, но слишком она уж большая в моем случае
ATP>3. Ассемблер не подходит — ясно что аппратно все просто реализуется, но нельзя по заданию
ATP>4. Суммирую не несколько значений в один аккамулятор, а много (НАПРИМЕР также как с случае с увеличением яркости).
ATP>5. Граница должна задаваться в виде 2^N но не включительно, тоесть в случае 2^16 последнее число должно быть 65535

Так я уже написал функцию: сложить, взять 29-й бит (то есть перенос из 28), превратить его в маску, сделать OR.
А будешь ты это делать с одним аккумулятором и многими слагаемыми, или с многими аккумуляторами и одним слагаемым — разницы никакой нет.
Перекуём баги на фичи!
Re[7]: Насыщение
От: Кодт Россия  
Дата: 14.06.05 09:34
Оценка: 7 (1) :)
Здравствуйте, conraddk, Вы писали:

C>Интересная штука была бы, а не получается Смотрим для ch=0:


Ой, блиииин! Действительно.
Ладно, корректируем:
<---R--->  <---R--->
000...001  000...000     ch
000...000  000...001                 ch^1
100...000  000...000     ch<<(R-1)
100...000  000...001    (ch<<(R-1))|(ch^1)
011...111  000...000   ((ch<<(R-1))|(ch^1))-1
111...110  000...000  (((ch<<(R-1))|(ch^1))-1)<<1
111...111  000...000 ((((ch<<(R-1))|(ch^1))-1)<<1)|ch

Перекуём баги на фичи!
Re[8]: Насыщение
От: Кодт Россия  
Дата: 14.06.05 10:27
Оценка:
Можно ещё проще:
unsigned ch; // 0 / 1
unsigned mask = unsigned(signed(ch<<(R-1))>>(R-1));

Фишка этого приёма — в том, что >> над знаковыми целыми — не логический, а арифметический сдвиг (x86 — shr, sar соответственно).
То есть деление на степень двойки.
100...000b значит -2^(R-1), соответственно, после сдвига получим -1, то есть 111...111b.
Перекуём баги на фичи!
Re[3]: Насыщение
От: AcidTheProgrammer Россия https://hts.tv/
Дата: 14.06.05 10:32
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, AcidTheProgrammer, Вы писали:


ATP>>1. Складываю 28 битные целые (четверка бит в запасе есть)

ATP>>2. Таблица не подходит — лобовой вариант, но слишком она уж большая в моем случае
ATP>>3. Ассемблер не подходит — ясно что аппратно все просто реализуется, но нельзя по заданию
ATP>>4. Суммирую не несколько значений в один аккамулятор, а много (НАПРИМЕР также как с случае с увеличением яркости).
ATP>>5. Граница должна задаваться в виде 2^N но не включительно, тоесть в случае 2^16 последнее число должно быть 65535

К>Так я уже написал функцию: сложить, взять 29-й бит (то есть перенос из 28), превратить его в маску, сделать OR.

К>А будешь ты это делать с одним аккумулятором и многими слагаемыми, или с многими аккумуляторами и одним слагаемым — разницы никакой нет.

Что-то туплю — не пойму как ваш метод работает
Например:
Есть предел 2^8 — 100000000b

Берем число например 255 и прибавляет 2 получает 257 — 100000001b

1. (x+y) & ~highbit — получаем 100000000b бит переполнения
2. (x+y) & (highbit — 1) — получаем маску после наложения маски 000000001b
3. ORим — получаем 100000001b

Где я ошибаюсь?
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.