Блог Ермолаева Игоря

Чудесная идея

Mon, 09 Apr 2012 12:23:57 GMT

Я чудесную идею
Ясно вижу без препон:
Как на сайте в интернете
Заработать миллион!

Лишь одна осталось малость,
Если можно так сказать:
Нужно мне мою идею
Поскорей реализовать!

Я инвестор, денег море
У меня уже давно,
Я не жадный, но зарплаты
Не простите все равно!

И про план я свой секретный
Ничего вам не скажу...
Поработайте бесплатно,
Может после награжу!

Если все пойдет нормально
И рак свистнет на горе,
Пол процента своей доли
Так и быть отдам тебе!

Потеплело за окошком

Mon, 06 Feb 2012 08:55:33 GMT

Потеплело за окошком,
Курс рубля рекорд побил -
Вот что значит Лукашенко
К нам из отпуска прибыл!

Былое вдохновение

Thu, 26 Jan 2012 05:56:09 GMT

Утеряно былое вдохновение,
А то бы здесь уже давно
Я безо всякого стеснения
Поэму выдал про говно.

Радиоактивные отходы и Гринпис

Mon, 28 Nov 2011 08:26:08 GMT

Поезд едет, а в вагонах
Под тройной стальной броней,
Тихо плещутся отходы
С излучающей "фигней".

Охраняют это поезд -
Ведь понятно, что вокруг
не покажется всем мало,
Если что случиться вдруг...

Но "зеленые" всех больше
Думу думают о том,
Что бы поезд ненароком
Не испачкал ихний дом.

От того себя на рельсы
Перед поездом кладут,
И отходам ненавистным
Продвигаться не дают.

А ведь может так случиться:
Кто-то ляжет на пути,
Тормозить придется быстро,
Можно с рельсов и сойти...

Разольются тут отходы,
И начнется страшный гам...
А Гринпис всем гордо скажет:
"А ведь я предупреждал!"

Кошка на кактусе

Fri, 25 Nov 2011 13:27:38 GMT

Было дело, как-то кошка
Не нашла себе лукошка.
По пустыне долго шла,
Кактус маленький нашла.
Поместила на верхушку
Свою маленькую тушку.
Кактус вырос в высоту,
Кошку видно за версту.
И такое вот бывает,
А народ теперь гадает...

Не пишется в ЖеЖе...

Wed, 16 Nov 2011 07:59:14 GMT

Хоть время интересное
Настало, но уже
Иссякло вдохновение -
Не пишется в ЖеЖе...

Тонущий курс

Mon, 15 Aug 2011 08:48:03 GMT

Курс валюты плавает
У зарубежных стран
То вниз, то вверх он скачет -
Таков у них изъян...

Мы видя это дело,
Своей дорогой шли:
И к тонущему курсу
В конце концов пришли!

Требуется помощь в переводе программы на белорусский и украинский языки

Mon, 18 Apr 2011 07:39:39 GMT

Здравствуйте, уважаемые носители белорусского и украинского языка!

Я уже достаточно долгое время разрабатываю бесплатную программу по поиску на компьютере похожих изображений:

antidupl.narod.ru/russian/index.html

Программа на настоящий момент поддерживает русский и английский языки. В последней версии мне пользователи из других стран прислали также перевод на испанский и итальянский язык. Мне бы хотелось так же, что бы программа поддерживала белорусский и украинский языки, но к сожалению я не настолько хорошо их знаю, а у автоматических переводчиков пока качество ниже плинтуса.

В связи с чем, мне требуется помощь аудитории по переводу файла со строковыми ресурсами.

Желающие помочь, могут обращаться на мыло antidupl@rambler.ru и я вам предоставлю все необходимые для этого данные.

Заранее благодарен.

Группа маньяков

Wed, 13 Apr 2011 15:25:24 GMT

Нашей бравою спецслужбой,
Не прошло и пару дней,
Был опознан и задержан
Террорист-маньяк-злодей!

Он уже во всем признался:
Вот уже который год
Он один везде коварно
Подрывает наш народ!

Тут спецслужбам подфартило:
Напрягли свой тонкий слух,
И помощника поймали,
А потом и целых двух...

И уже во всем признались
Три бомбиста-маньяка,
Как все бомбы вместе клали,
Чтоб взорвать наверняка.

Психиатры всего мира
Теперь будут точно знать:
Что маньяки-одиночки
Могут группой нападать!

Где сахар?

Mon, 11 Apr 2011 06:39:30 GMT

Где сахар и где масло?
Я все узнать хотел,
Но только Папа Коли
Давно уже все съел...

Перед зеркалом

Fri, 04 Mar 2011 13:10:20 GMT

Руки-веточки, животик,
Сколиоз и толстый зад -
Разве в зеркале все это
Ты увидеть будешь рад?

От чего же телевизор
И диван твои друзья?
От чего без сигареты
Обойтись ни как нельзя?

Почему забыл бассейн
И поход в спортивный зал?
От чего с утра зарядку
выполнять ты перестал?

Так сожми в кулак всю волю,
Воплоти свои мечты:
Быть здоровым или хилым -
Выбираешь только ты!

Валентинка

Mon, 14 Feb 2011 14:47:08 GMT

Хоть порою в этой жизни нам бывает не легко,
Но я верю: у нас будет все с тобою хорошо!
Не печалься, мое солнце, понапрасну не грусти,
Море радости и счастья у нас будет впереди!

Первый день рождения

Mon, 24 Jan 2011 15:42:13 GMT

Вот он только что родился,
Улыбнулся вот для нас,
Первый раз перевернулся,
Взял игрушку в первый раз.

Первый раз вот встал в кроватке,
Появился первый зуб,
Первый раз невнятно: "Мама!" -
Прозвучало с его губ.

Возраст шел по дням, неделям
И по месяцам... и вот,
Наступил момент сынишке
Набежал уж целый год.

В день рождения первый самый
Мы желаем, чтобы он
Рос здоровым и веселым,
Был заботой окружен,

Чтоб уверенной походкой
Шел на жизненном пути,
Чтобы много дней рождений
Еще было впереди!

Снеговик

Mon, 10 Jan 2011 14:30:56 GMT

Снег пушистый, мягкий, белый
Устилает зимний лес,
Что внутри себя скрывает
Столько сказочных чудес.

Я гуляю с своим сыном,
Он в колясочке заснул.
Потому с аллеи шумной
На тропинку я свернул.

Спит сынишка, ну а папа
Бить баклуши не привык,
Он слепил за это время
На поляне снеговик...

32

Mon, 03 Jan 2011 08:18:04 GMT

Лишь рассвет слегка занялся
За окном моим едва,
С ощущением проснулся:
Мне сегодня тридцать два!

Это много или мало?
Промежуточный итог:
И не юный, и не старый...
Пришла зрелость на порог!

Послание депутатов Всебелорусского народного собрания Президенту

Tue, 07 Dec 2010 07:22:28 GMT

Мы внимаем твои речи
С бурною овацией,
Несогласие считаем
С тобою провокацией!

Попу мы тебе лизать
Хоть всю жизнь готовые,
Только ты нам подари
Печи микроволновые!

Лукашенко: Космические технологии в Беларуси войдут в повседневный обиход

Mon, 06 Dec 2010 13:28:29 GMT

На работу на ракете
Будем каждый день летать!
И картошку на комете
Мы научимся сажать!

А с Титана подешевке
Повезем сюда мы газ,
Марсианские кредиты
Будут льготные для нас!

В общем будет без обмана
Ждать осталось так- фигня,
Это будет очень скоро...
Голосуйте за меня!

Первый шаг

Thu, 18 Nov 2010 15:02:59 GMT

Всем скажу я по секрету,
Что вчера случилось так:
Дести месяцев пусть нету,
Сын мой сделал первый шаг!

Осенняя печаль

Tue, 16 Nov 2010 09:17:40 GMT

Несбывшиеся грезы
Нам все немного жаль.
Роняет тихо слезы
Осенняя печаль.

Дорогу закрывает
Нам горизонтом дней.
И ветер обрывает
Последний лист с ветвей.

Но прочь печаль, сомнения
Коль жив ты и здоров.
И видно небо синее
В просвете облаков.

Лукашенко: Экономические катаклизмы Беларуси не грозят

Fri, 08 Oct 2010 08:08:04 GMT

Говорят, народа слуги
Могут только нагло врать.
Но они нам намекают,
Нужно только их понять.

Если вдруг нам заявляют:
Дефициту не бывать -
В магазин бегите сразу
Соль и спички покупать.

Говорят, что безработных
Будет меньше с каждым днем -
Это значит скоро в отпуск
Неоплаченный пойдем.

Из Нацбанка если скажут:
Золотой запас растет -
То понятно рубль завтра
Непременно упадет!

Ну а если Батька вышел
Успокаивать народ -
Это значит сто пудово
Жопа полная придет!

Оптимизация программы по скорости на примере медианного фильтра

Thu, 07 Oct 2010 12:07:00 GMT

Введение

В данной статье я решил привести пример оптимизации по скорости исполнения алгоритма, предназначенного для обработки видео изображения. В качестве примера, мной был выбран алгоритм медианной фильтрации. Медианная фильтрация является эффективным способом подавления шумов, которые неизбежно появляются на цифровых камерах в условиях малого освещения сцены. Алгоритм этот достаточно ресурсоемок – так например, при обработке серого изображения медианным фильтром 3х3 требуется порядка 50 операций на одну точку изображения. И если для обработки одиночных фотографий скорость в принципе не сильно важна, то при обработке видео потока скорость обработки кадра является критическим параметром при выборе алгоритма.

Для справки напоминаю суть алгоритма:

Для каждой точки исходного изображения берется некоторая окрестность (в нашем случае 3x3).
Точки данной окрестности сортируются по возрастанию яркости.
Средняя точка (5-я для фильтра 3х3) отсортированной окрестности записывается в итоговое изображение.

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

0-й вариант реализации

В этой начальной реализации задача была решена в лоб: окрестность для каждой точки исходного изображения копировалась во вспомогательный массив, который затем сортировался при помощи функции std::sort().

    void median_filter(unsigned char* src, int width, int height, int stride, unsigned char* dst)
    {
        int a[9];
        for(int y = 0; y < height; ++y)
        {
            for(int x = 0; x < width; ++x)
            {
                load(src + x, stride, a); //см. приложение
        	    std::sort(a, a + 9);
                dst[x] = (unsigned char)a[4];
            }
            dst += stride; 
            src += stride;
        }
    }

1-я оптимизация

У предыдущего метода, впрочем, сразу видно узкое место – это стандартная функции сортировки. Она предназначена для сортировки массива произвольного размера, в ней осуществляется множество внутренних проверок, потому она, скорее всего, не будет оптимальным решением для данной задачи, где массив мал и имеет фиксированный размер. Кроме того, нам совсем не обязательно полностью сортировать массив, достаточно, что бы в 4-м элементе было требуемое нами значение. Потому мы можем применить метод сортировки «сетью». Кроме того вызов сам функций в теле цикла также вызывает дополнительные накладные расходы, потому функцию сортировки мы сделаем inline:

    inline void sort(int& a, int& b) // сортирует пару чисел
    {
        if(a > b)
        {
            int t = a;
            a = b;
            b = t;
        }
    }

    inline void sort(int a[9]) //частично сортирует весь массив
    {
        sort(a[1], a[2]); sort(a[4], a[5]); sort(a[7], a[8]); 
        sort(a[0], a[1]); sort(a[3], a[4]); sort(a[6], a[7]);
        sort(a[1], a[2]); sort(a[4], a[5]); sort(a[7], a[8]); 
        sort(a[0], a[3]); sort(a[5], a[8]); sort(a[4], a[7]);
        sort(a[3], a[6]); sort(a[1], a[4]); sort(a[2], a[5]); 
        sort(a[4], a[7]); sort(a[4], a[2]); sort(a[6], a[4]);
        sort(a[4], a[2]);
    }

2-я оптимизация

Хотя первый метод и получился значительно быстрее нулевого (см. результат тестирования ниже), но у него осталось одно узкое место – в этом методе очень много условных переходов. Как известно, современные процессоры очень их не любят, так как имеют конвейерную архитектуру и возможность внеочередного исполнения нескольких команд за один такт. И для первого, и для второго условные переходы крайне нежелательны, так как процессор должен останавливаться и ждать результатов вычислений, чтобы узнать по какой ветке программы ему следует идти дальше. К счастью сортировку двух 8 битных значений вполне можно реализовать и без условных переходов:

    inline void sort(int& a, int& b)
    {
        int d = a - b;
        int m = ~(d >> 8);
        b += d&m;
        a -= d&m;
    }

3-я оптимизация

В принципе предыдущей оптимизации уже вполне достаточно, однако можно еще немного оптимизировать функцию void sort(int& a, int& b) с применением вспомогательног массива. Однако останавливаться здесь подробно на нем я не буду, так эта оптимизация не дает существенного ускорения работы алгоритма. Впрочем все желающие могут посмотреть его реализацию в приложении.

4-я оптимизация

До сих пор мы оставались в рамках стандратного С++ и не учитывали все возможности современных процессоров. Однако еще начина с процессора Pentium-MMX в процессорах появилась поддержка MMX (Multimedia Extensions) инструкций для векторной обработки данных. В частности, команды MMX могут исполнять целочисленные векторные операции сразу над 8-ю 8-битными числами за раз. А начиная с процессоров Pentium-IV и Athlon-64 появилась поддержка инструкций из набора SSE2 (Streaming SIMD Extensions), которые позволяют обрабатывать целочисленные векторные операции сразу над 16-ю 8-битными числами за раз. Сразу понятно, что теоретически использование SSE2 инструкций может потенциально ускорить программу 16 раз, потому глупо не попытаться их использовать.

К счастью, для того, чтобы задействовать инструкции из набора SSE2, совсем не обязательно использовать ассемблер. Большинство современных С++ компиляторов имеют поддержку intrinsics (встроенных функций, с помощью которых можно задействовать всевозможные расширения процессоров). Программирование с использованием intrinsics практически не отличается от программирования на чистом С. Intrinsic функции преобразуются компилятором напрямую в инструкции процессора, хотя при этом работа непосредственно с регистрами процессора остается скрытой от программиста. В большистве случаев программа с использованием intrinsics не уступает в быстродействии программе, написанной на ассемблере.

Целочисленные комманды SSE2 определены в заголовочном файле < emmintrin.h > . В качестве базового типа выступает __m128i - 128 битный вектор, который в зависимости от контекста может интерпетироваться как набор 2-х 64 битных, 4-х 32 битных, 8-х 16 битных, 16-х 8 битных знаковых или беззнаковых чисел. Как видно, поддерживают не только векторные арифметические операции, но также векторные логические операции, а также векторные операции загрузки и выгрузки данных. Ниже приведен 4-й вариант оптимизации медианного фильтра при помощи SSE2 инструкций. Код, как мне кажется, довольно нагляден.

    inline void sort(__m128i& a, __m128i& b)
    {
        const __m128i t = a;
        a = _mm_min_epu8(t, b); //нахождение минимума 2-х 8 битных безннаковых чисел для каждого из 16 значений вектора
        b = _mm_max_epu8(t, b); //нахождение максимума 2-х 8 битных безннаковых чисел для каждого из 16 значений вектора
    }

    inline void sort(__m128i a[9])
    {
        sort(a[1], a[2]); sort(a[4], a[5]); sort(a[7], a[8]); 
        sort(a[0], a[1]); sort(a[3], a[4]); sort(a[6], a[7]);
        sort(a[1], a[2]); sort(a[4], a[5]); sort(a[7], a[8]); 
        sort(a[0], a[3]); sort(a[5], a[8]); sort(a[4], a[7]);
        sort(a[3], a[6]); sort(a[1], a[4]); sort(a[2], a[5]); 
        sort(a[4], a[7]); sort(a[4], a[2]); sort(a[6], a[4]);
        sort(a[4], a[2]);
    }

    inline void load(unsigned char* src, int stride, __m128i a[9])
    {
        a[0] = _mm_loadu_si128((__m128i*)(src - 1 - stride)); //загрузка 128 битного вектора по невыровненному по 16 битной границе адресу
        a[1] = _mm_load_si128((__m128i*)(src - stride)); //загрузка 128 битного вектора по выровненному по 16 битной границе адресу
        a[2] = _mm_loadu_si128((__m128i*)(src + 1 - stride));

        a[3] = _mm_loadu_si128((__m128i*)(src - 1));
        a[4] = _mm_load_si128((__m128i*)(src));
        a[5] = _mm_loadu_si128((__m128i*)(src + 1));

        a[6] = _mm_loadu_si128((__m128i*)(src - 1 + stride));
        a[7] = _mm_load_si128((__m128i*)(src + stride));
        a[8] = _mm_loadu_si128((__m128i*)(src + 1 + stride));
    }

    void median_filter(unsigned char* src, int width, int height, int stride, unsigned char* dst)
    {
        __m128i a[9];
        for(int y = 0; y < height; y++)
        {
            for(int x = 0; x < width; x += sizeof(__m128i))
            {
                load(src + x, stride, a);
                sort(a);
                _mm_store_si128((__m128i*)(dst + x), a[4]); //сохранение 128 битного вектора по выровненному по 16 битной границе адресу
            }
            dst += stride; 
            src += stride;
        }
    }

Тестирование

Тестирование производилось на серых изображениях размером 1 MB. Для повышения точности измерения времени, тесты прогонялись несколько раз. Время выполнения получали делением общего времени исполнения тестов на количество прогонов. Количество прогонов выбиралось таким образом, что общее время исполнения было не меньше 1 секунды, что должно обеспечить два знака точности при измерении времени исполнения алгоритмов. Всего было протестировано 5 вариантов решения задачи:

0-й вариант с использованием стандартной сортировки.
1-й вариант с использованием сортировки "сетью".
2-й вариант с использованием сортировки "сетью" + без использования условных переходов.
3-й вариант с использованием сортировки "сетью" + без использования условных переходов (метод с применением вспомогательного массива) .
4-й вариант с оптимизацией под SSE2 расширение процессора.

Исходные коды теста находятся в приложении (см. ниже). Тест был скомпилирован с максимальной оптимизацией под Microsoft Visual Studio 2008 и был запущен на нескольких машинах со следующими результатами:

Производитель	Intel			AMD
Название	Core i5 750	Core 2 Due	T2080	Phenom II X6	Athlon 64 X2	Athlon
Частота, GHz	2.67	2.3	1.7	2.8	2,8	0,8
Название теста	Среднее время исполнения, мс
base::median_filter with std::sort	141	165	239	102	126	516
base::median_filter with sorter_v1	46.7	59.4	76.6	39.9	65.8	170
base::median_filter with sorter_v2	26.7	37.1	58.4	25.3	40.8	142
base::median_filter with sorter_v3	24.1	29.7	41.2	23.7	47.6	131
sse2::median_filter	0.636	1.48	3.69	0.808	1.80	---
Название теста	Относительный/абсолютный выигрыш от оптимизации
base::median_filter with sorter_v1	3.0 / 3.0	2.8 / 2.8	3.1 / 3.1	2.6 / 2.6	1.9 / 1.9	3.0 / 3.0
base::median_filter with sorter_v2	1.7 / 5.3	1.6 / 4.4	1.3 / 4.1	1.6 / 4.0	1.6 / 3.0	1.2 / 3.6
base::median_filter with sorter_v3	1.1 / 5.9	1.2 / 5.6	1.4 / 5.8	1.1 / 4.3	0.9 / 2.6	1.1 / 3.9
sse2::median_filter	37.9 / 222	20.1 / 111	11.2 / 64.8	29.3 / 126	22.6 / 70	-- / --

Примечание: процессоры AMD Athlon не поддерживают инструкции из набора SSE2.

Выводы

На основании результатов тестов можно сделать следующие выводы:

При помощи стандартных средств C++ данный алгоритм может быть оптимизирован по скорости в 4-6 раз.
С применением инструкций SSE2 данный алгоритм можно еще ускорить в 10-40 раз. Это достаточно большая величина, которая перекрывает, как мне кажется, минусы отхода от потери переносимости стандартного C++.
Если соотнести время исполнения SSE2 и частоту процессоров, то можно судить о количестве инструкций SSE2 выполняемых данным процессором за один такт. Особенно это хорошо видно на примере процессоров Intel. Так настольный процессор Core 2 Due выполняет по одной операции SSE2 за такт, с мобильный процессор T2080 может выполнять лишь одну операцию за два такта. В тоже время новые процессоры Core i5 значительно ускорились и явно могут обрабатывать по 2 такие операции за такт.

Приложение

Код тестовой программы (написан на C++ под Microsoft Visual Studio 2008):

#include < iostream>
#include < algorithm>
#include < windows.h>
#include < emmintrin.h>

namespace base
{
    const int saturate[] = 
    {
        0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,
        16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  30,  31,
        32,  33,  34,  35,  36,  37,  38,  39,  40,  41,  42,  43,  44,  45,  46,  47,
        48,  49,  50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  60,  61,  62,  63,
        64,  65,  66,  67,  68,  69,  70,  71,  72,  73,  74,  75,  76,  77,  78,  79,
        80,  81,  82,  83,  84,  85,  86,  87,  88,  89,  90,  91,  92,  93,  94,  95,
        96,  97,  98,  99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
        112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127,
        128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143,
        144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,
        160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175,
        176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,
        192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,
        208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,
        224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
        240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255
    };

    __forceinline int cast(int t) 
    {
        return saturate[t + 256];
    }

    struct sorter_v0
    {
    };

    struct sorter_v1
    {
        __forceinline void operator() (int& a, int& b)
        {
            if(a > b)
            {
                int t = a;
                a = b;
                b = t;
            }
        }
    };

    struct sorter_v2
    {
        __forceinline void operator() (int& a, int& b)
        {
            int d = a - b;
            int m = ~(d >> 8);
            b += d&m;
            a -= d&m;
        }
    };

    struct sorter_v3
    {
        __forceinline void operator() (int& a, int& b)
        {
            int t = cast(a - b);
            b += t;
            a -= t;
        }
    };

    template < class Sorter> __forceinline void sort(int a[9], Sorter sorter)
    {
        sorter(a[1], a[2]); sorter(a[4], a[5]); sorter(a[7], a[8]); 
        sorter(a[0], a[1]); sorter(a[3], a[4]); sorter(a[6], a[7]);
        sorter(a[1], a[2]); sorter(a[4], a[5]); sorter(a[7], a[8]); 
        sorter(a[0], a[3]); sorter(a[5], a[8]); sorter(a[4], a[7]);
        sorter(a[3], a[6]); sorter(a[1], a[4]); sorter(a[2], a[5]); 
        sorter(a[4], a[7]); sorter(a[4], a[2]); sorter(a[6], a[4]);
        sorter(a[4], a[2]);
    }

    template <> __forceinline void sort< sorter_v0>(int a[9], sorter_v0 sorter)
    {
        std::sort(a, a + 9);
    }

    __forceinline void load(unsigned char* src, int stride, int a[9])
    {
        a[0] = src[-1 - stride];  
        a[1] = src[-stride]; 
        a[2] = src[1 - stride];

        a[3] = src[-1];         
        a[4] = src[0];              
        a[5] = src[1];

        a[6] = src[-1 + stride];  
        a[7] = src[stride];  
        a[8] = src[1 + stride];
    }

    template < class Sorter> void median_filter(unsigned char* src, int width, int height, int stride, unsigned char* dst, Sorter sorter)
    {
        int a[9];
        for(int y = 0; y < height; y++)
        {
            for(int x = 0; x < width; ++x)
            {
                load(src + x, stride, a);
                sort(a, sorter);
                dst[x] = (unsigned char)a[4];
            }
            dst += stride; 
            src += stride;
        }
    }
}

namespace sse2
{
    __forceinline void sort(__m128i& a, __m128i& b)
    {
        const __m128i t = a;
        a = _mm_min_epu8(t, b);
        b = _mm_max_epu8(t, b);
    }

    __forceinline void sort(__m128i a[9])
    {
        sort(a[1], a[2]); sort(a[4], a[5]); sort(a[7], a[8]); 
        sort(a[0], a[1]); sort(a[3], a[4]); sort(a[6], a[7]);
        sort(a[1], a[2]); sort(a[4], a[5]); sort(a[7], a[8]); 
        sort(a[0], a[3]); sort(a[5], a[8]); sort(a[4], a[7]);
        sort(a[3], a[6]); sort(a[1], a[4]); sort(a[2], a[5]); 
        sort(a[4], a[7]); sort(a[4], a[2]); sort(a[6], a[4]);
        sort(a[4], a[2]);
    }

    __forceinline void load(unsigned char* src, int stride, __m128i a[9])
    {
        a[0] = _mm_loadu_si128((__m128i*)(src - 1 - stride));
        a[1] = _mm_load_si128((__m128i*)(src - stride));
        a[2] = _mm_loadu_si128((__m128i*)(src + 1 - stride));

        a[3] = _mm_loadu_si128((__m128i*)(src - 1));
        a[4] = _mm_load_si128((__m128i*)(src));
        a[5] = _mm_loadu_si128((__m128i*)(src + 1));

        a[6] = _mm_loadu_si128((__m128i*)(src - 1 + stride));
        a[7] = _mm_load_si128((__m128i*)(src + stride));
        a[8] = _mm_loadu_si128((__m128i*)(src + 1 + stride));
    }

    void median_filter(unsigned char* src, int width, int height, int stride, unsigned char* dst)
    {
        __m128i a[9];
        for(int y = 0; y < height; y++)
        {
            for(int x = 0; x < width; x += sizeof(__m128i))
            {
                load(src + x, stride, a);
                sort(a);
                _mm_store_si128((__m128i*)(dst + x), a[4]);
            }
            dst += stride; 
            src += stride;
        }
    }
}

struct Image
{
    int width;
    int height;
    int stride;
    unsigned char* data;

    Image(int width_, int height_)
    {
        width = width_;
        height = height_;
        stride = (width/sizeof(__m128i) + 2 + (width%sizeof(__m128i) ? 1 : 0))*sizeof(__m128i);
        m_data = (unsigned char*)_mm_malloc(stride*(height + 2), sizeof(__m128i));
        data = m_data + stride + sizeof(__m128i);
        memset(m_data, 0, stride*(height + 2));
    }

    ~Image()
    {
        _mm_free(m_data);
    }

    bool operator==(const Image ℑ)
    {
        return 
            width == image.width && height == image.height && 
            memcmp(m_data, image.m_data, stride*(height + 2)) == 0;
    }

    void Fill(int seed)
    {
        srand(seed);
        for(int row = 0; row < height; row++)
            for(int col = 0; col < width; col++)
                data[stride*row + col] = (rand()*255)/RAND_MAX;
    }

private:
    unsigned char* m_data;
};

double GetTime()
{
    LARGE_INTEGER freq, count;
    QueryPerformanceFrequency(&freq);
    QueryPerformanceCounter(&count);
    return 1.0 / (freq.HighPart * (double)0xffffffff + freq.LowPart) * 
        (count.HighPart * (double)0xffffffff + count.LowPart);
}

int main()
{
    const int w = 1024;
    const int h = 1024;

    Image src(w, h), dst0(w, h), dst1(w, h), dst2(w, h), dst3(w, h), dst4(w, h);

    src.Fill(1);

    {
        const int n = 10;
        double t = GetTime();
        for(int i = 0; i < n; i++)
            base::median_filter(src.data, src.width, src.height, src.stride, dst0.data, base::sorter_v0());
        t = GetTime() - t;
        std::cout << "C++ base::median_filter with std::sort time = " << t/n*1000 << " ms" << std::endl;
    }

    {
        const int n = 30;
        double t = GetTime();
        for(int i = 0; i < n; i++)
            base::median_filter(src.data, src.width, src.height, src.stride, dst1.data, base::sorter_v1());
        t = GetTime() - t;
        std::cout << "C++ base::median_filter with sorter_v1 time = " << t/n*1000 << " ms" << std::endl;
        if(!(dst0 == dst1))
            std::cout << "C++ base::median_filter with sorter_v1 error!" << std::endl;
    }

    {
        const int n = 50;
        double t = GetTime();
        for(int i = 0; i < n; i++)
            base::median_filter(src.data, src.width, src.height, src.stride, dst2.data, base::sorter_v2());
        t = GetTime() - t;
        std::cout << "C++ base::median_filter with sorter_v2 time = " << t/n*1000 << " ms" << std::endl;
        if(!(dst0 == dst2))
            std::cout << "C++ base::median_filter with sorter_v2 error!" << std::endl;
    }

    {
        const int n = 60;
        double t = GetTime();
        for(int i = 0; i < n; i++)
            base::median_filter(src.data, src.width, src.height, src.stride, dst3.data, base::sorter_v3());
        t = GetTime() - t;
        std::cout << "C++ base::median_filter with sorter_v3 time = " << t/n*1000 << " ms" << std::endl;
        if(!(dst0 == dst3))
            std::cout << "C++ base::median_filter with sorter_v3 error!" << std::endl;
    }

    {
        const int n = 2000;
        double t = GetTime();
        for(int i = 0; i < n; i++)
            sse2::median_filter(src.data, src.width, src.height, src.stride, dst4.data);
        t = GetTime() - t;
        std::cout << "C++ sse2::median_filter time = " << t/n*1000 << " ms" << std::endl;
        if(!(dst0 == dst4))
            std::cout << "C++ sse2::median_filter error!" << std::endl;
    }
}

На обед!

Wed, 06 Oct 2010 10:57:08 GMT

Аппетит во мне проснулся,
Потому давай, сосед,
Коли нету возражений,
Выдвигаться на обед!

Юра, приезжай!

Fri, 01 Oct 2010 11:58:34 GMT

Если ты был самым главным,
Но тебе не повезло -
Был уволен или свергнут
В своем царстве, как назло.

В телевизоре ругают
И грозят привлечь к суду,
Заморозить миллионы,
Что хранятся на счету...

Но не надо огорчаться
И напрасно слезы лить,
Нужно только Беларусь вам
Поскорее посетить!

Всем диктаторам тут бывшим
Лукашенко даст приют...
Может быть настанет время -
И ему приют дадут?

P.S. сей опус - немного переделанный ранее вариант про Бакиева.

Пиши обе!

Tue, 28 Sep 2010 14:45:37 GMT

Хоть убейте, президента
Не могу никак понять:
Ну зачем ему так часто
День рождения менять?

Коль ты не определился
С днем рожденья своего:
Иль тридцатого родился,
Или тридцать первого.

Коли обе эти даты
У тебя в мозгу живут,
Запиши их обе в паспорт:
Не стесняйся, все поймут!

Колобок не ушел от медведя...

Tue, 28 Sep 2010 12:02:24 GMT

Колобка судьба от зайца
И от волка сберегла,
Ну а с мишкой даже кепка
Колобку не помогла...