Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, AcidTheProgrammer, Вы писали:
К>>>Берём 255+2 = 257 = 1'0000'0010'b.
ATP>>Ну всетаки 257 — это 100000001b
К>Да... маразм не дремлет... конечно же, 100000001.
К>>>Значащая часть: S = (x+y)&(highbit-1) = 1'0000'0010'b & 0'1111'1111'b = 0'0000'0010'b. К>>>Бит переполнения: C = (x+y)&highbit = 1'0000'0000'b.
ATP>>Тут все понятно
К>>>Делаем из него маску: M = C-1 = 1'0000'0000'b — 1 = 0'1111'1111'b.
ATP>>А вот ту можно поподробней... если С == 0, то C — 1 == -1 == 111111111.....11111
К>См выше про маразм.
К>Маску можно сделать хитрым способом: К>Получим значение бита переноса: c = C>>height = 0 или 1 К>далее маску можно вытягивать из простой 2-элементной таблицы { 0, highbit-1 } К>или рожать с помощью хитрой формулы (http://www.rsdn.ru/Forum/?mid=1220781
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>1. Складываю 28 битные целые (четверка бит в запасе есть) ATP>2. Таблица не подходит — лобовой вариант, но слишком она уж большая в моем случае ATP>3. Ассемблер не подходит — ясно что аппратно все просто реализуется, но нельзя по заданию ATP>4. Суммирую не несколько значений в один аккамулятор, а много (НАПРИМЕР также как с случае с увеличением яркости). ATP>5. Граница должна задаваться в виде 2^N но не включительно, тоесть в случае 2^16 последнее число должно быть 65535
Так я уже написал функцию: сложить, взять 29-й бит (то есть перенос из 28), превратить его в маску, сделать OR.
А будешь ты это делать с одним аккумулятором и многими слагаемыми, или с многими аккумуляторами и одним слагаемым — разницы никакой нет.
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Нужна реализация без IFа ATP>MMX — не предлагать
А что предлагать? От языка зависит.
Можно, например, так:
unsigned int data[count];
unsigned int sum=0, over=0;
unsigned int mask = (~0)<<N; // все старшие биты, начиная с Nfor(int i=0; i<count; ++i)
{
sum += data[i];
over |= (sum & mask);
}
// один-единственный if на весь набор:if(over)
sum = (1<<N);
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, 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;
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, 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 использовать не могу)
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Способ понятен, но If всеравно есть. У меня в цикле всего одно сложение, тоесть нет аккамулятора как у вас. ATP>Наприме: представте операцию повышения яркости на ихображении — ко всем точкам прибавляется константа, но результат не должен переходить за 255.
ATP>Нужно что в этом случае бех if работало (сейчас пока используется max (x, y). MMX использовать не могу)
А вообще, если ты делаешь какую-то быструю операцию наподобие обработки изображения — то или пользуйся спецсредствами (ассемблер), или бери в руки профайлер и выясняй, что является узким местом. Будет ли им ветвление или же вычисление громоздкого выражения — загадка.
Для суммы, мне кажется, дешевле всего сделать так:
— взять сумматор с разрядностью, достаточной, чтобы сложить все слагаемые набора
— суммировать (в цикле) без заморочек
— один раз поветвиться, либо родить хитрое выражение над битами.
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";
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х разрядное, поэтому уж очеь большая таблица должна быть.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>>Способ понятен, но If всеравно есть. У меня в цикле всего одно сложение, тоесть нет аккамулятора как у вас. ATP>>Наприме: представте операцию повышения яркости на ихображении — ко всем точкам прибавляется константа, но результат не должен переходить за 255.
ATP>>Нужно что в этом случае бех if работало (сейчас пока используется max (x, y). MMX использовать не могу)
К>Я выше написал ответ без иф. К>
К>А вообще, если ты делаешь какую-то быструю операцию наподобие обработки изображения — то или пользуйся спецсредствами (ассемблер), или бери в руки профайлер и выясняй, что является узким местом. Будет ли им ветвление или же вычисление громоздкого выражения — загадка.
К>Для суммы, мне кажется, дешевле всего сделать так: К>- взять сумматор с разрядностью, достаточной, чтобы сложить все слагаемые набора К>- суммировать (в цикле) без заморочек К>- один раз поветвиться, либо родить хитрое выражение над битами.
Спасибо, но у меня есть ожно но: насколько я понимаю по формуле у вас граница включается в диаппзон, а мне нужно что б не включалас, последнее число было бы 255 в случае 2^8
Здравствуйте, 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;
Затейливая форма для получения маски объясняется так:
Спасибо болшле за посты, но все не то,
хотелось бы уточнить:
1. Складываю 28 битные целые (четверка бит в запасе есть)
2. Таблица не подходит — лобовой вариант, но слишком она уж большая в моем случае
3. Ассемблер не подходит — ясно что аппратно все просто реализуется, но нельзя по заданию
4. Суммирую не несколько значений в один аккамулятор, а много (НАПРИМЕР также как с случае с увеличением яркости).
5. Граница должна задаваться в виде 2^N но не включительно, тоесть в случае 2^16 последнее число должно быть 65535
С учетом этих требование есть ли какие-нибудь метоты?
Фишка этого приёма — в том, что >> над знаковыми целыми — не логический, а арифметический сдвиг (x86 — shr, sar соответственно).
То есть деление на степень двойки.
100...000b значит -2^(R-1), соответственно, после сдвига получим -1, то есть 111...111b.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, 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
ATP>1. Складываю 28 битные целые (четверка бит в запасе есть) ATP>4. Суммирую не несколько значений в один аккамулятор, а много (НАПРИМЕР также как с случае с увеличением яркости). ATP>5. Граница должна задаваться в виде 2^N но не включительно, тоесть в случае 2^16 последнее число должно быть 65535
Здравствуйте, Ranger_XL, Вы писали:
ATP>>1. Складываю 28 битные целые (четверка бит в запасе есть) ATP>>4. Суммирую не несколько значений в один аккамулятор, а много (НАПРИМЕР также как с случае с увеличением яркости). ATP>>5. Граница должна задаваться в виде 2^N но не включительно, тоесть в случае 2^16 последнее число должно быть 65535
R_X>или я чего-то не понимаю, или это тривиально:
R_X>int32 mask = 0x0FFFFFFF; R_X>int32 result = (data + num) & mask;
Limit == 255 (0xFF)
Надо: 255 + 2 == 255
Твой вариант: 255 + 2 == 1 == a + b (mod 256)
new RSDN@Home(1.1.4, 303) << new Message(); std::head::ear << "SCOOTER — No Fate";
Здравствуйте, AcidTheProgrammer, Вы писали:
К>>Берём 255+2 = 257 = 1'0000'0010'b.
ATP>Ну всетаки 257 — это 100000001b
Да... маразм не дремлет... конечно же, 100000001.
К>>Значащая часть: S = (x+y)&(highbit-1) = 1'0000'0010'b & 0'1111'1111'b = 0'0000'0010'b. К>>Бит переполнения: C = (x+y)&highbit = 1'0000'0000'b.
ATP>Тут все понятно
К>>Делаем из него маску: M = C-1 = 1'0000'0000'b — 1 = 0'1111'1111'b.
ATP>А вот ту можно поподробней... если С == 0, то C — 1 == -1 == 111111111.....11111
См выше про маразм.
Маску можно сделать хитрым способом:
Получим значение бита переноса: c = C>>height = 0 или 1
далее маску можно вытягивать из простой 2-элементной таблицы { 0, highbit-1 }
или рожать с помощью хитрой формулы (http://www.rsdn.ru/Forum/?mid=1220781