...

суббота, 4 июля 2015 г.

OpenCL. Как начать

Тяжелый старт


Всем привет! Какое-то время назад я начал копать тему с OpenCL под C#. Но наткнулся на трудности, связанные с тем, что не то, что под C#, а вообще по этой теме очень мало материала. Какую-то вводную по OpenCL можно почерпнуть здесь. Так же простой, но работающей старт OpenCL описан вот тут. Ни на йоту не хочу обидеть авторов, но все статьи, что я находил на русском (и на хабре в том числе) страдают одной и той же проблемой — очень мало примеров. Документация есть, её много и как принято для хорошей документации читается сложно. В своей статье (а если всё будет нормально, то и в цикле статей), я постараюсь поподробней описать эту область, с точки зрения человека, который начал её копать с нуля. Думаю такой подход будет полезен тем кто хочет быстро стартовать в высоко производительных вычислениях.
Первоначально я хотел написать статью-минисамоучитель OpenCL, которая содержала в себе информацию, о там что это, как устроено, как писать код и какие-то рекомендации, основанные на моем опыте. Но в процессе понял, что если даже быть кратким, то уткнусь в ограничения объема статьи. Потому что, имхо, статья должна быть такого объема, чтобы усвоить её объем было не сложно. По этому в данной статье (которая станет первой) я планирую описать, то как стартовать в OpenCL, проверить что локально все корректно законфигурино, и написать простейшую программу. Вопросы с устройством памяти, архитектурой и прочим будут описаны в следующих статьях.

Друзья, сразу хотел бы сказать, что мой опыт в OpenCL пока, к сожалению, далек от гуру/йода уровня, но на вопросы постараюсь отвечать изо всех сил. А если что-то не знаю, то буду делиться ресурсами и видением того как это на самом деле должно работать.

Что. Где. Как.


OpenCL это технология связанная с параллельными компьютерными вычислениями на различных типах графических и центральных процессоров. Тема с параллельным вычислениями на GPU совсем недавно широко продвигалась вместе с технологией CUDA. Данное продвижение в основном обеспечивалось усилиями компании Nvidia. Отличия OpenGL и CUDA уже широко обсуждались.

OpenGL позволяет работать как с CPU так и с GPU, но думаю нам более интересно будет сосредоточиться на работе с GPU. Для использования данной технологии понадобиться мало мальски современная видеокарта. Главное это проверить, что устройство функционирует нормально. На всякий случай напоминаю что это можно сделать в диспетчере устройств.

Если в данном окне вы видите какие-то фейлы или ворнинги, то вам прямая дорога на сайт производителя вашей видеокарты. Свежие драйвера должны решить проблему с функционированием железа и как следствие дать доступ к мощностям OpenCL.

Первоначально я планировал использовать OpenCL по C#. Но наткнулся на проблему, что все существующие фреймворки типа Cloo или OpenCLNet являются самописными и Khronus не имеет к ним никакого отношения и следовательно не гарантирует их стабильную работу. Ну и все мы помним главную проблему — очень мало примеров. Исходя из этого вначале я бы хотел представить примеры написанные на C++, а уже потом, получив подтверждение того что OpenCL ведет себя так как мы ожидаем, привинтить прокси в виде C# фреймворка.
Итак, чтобы использовать OpenCL через С++ необходимо найти его API. Для этого открывайте переменные среды, и ищете там переменную со страшным названием, намекающую своим названием на производителя вашей видеокарты. У меня данная переменная называется «AMDAPPSDKROOT». После этого можете посмотреть что лежит оп указанному пути. Там ищите папочку include\CL.

Кстати, обычно в папочки include, рядом с папкой CL лежит и папка GL, предоставляющая доступ к знаменитой графической библиотеки.

Теперь создаем проект в Visual Studio, подключаем в свойствах проекта папку include (в моем случае $(AMDAPPSDKROOT)\include\) и в бой!

Инфраструктура


Мы должны помнить, что мы будем работать с OpenCL не через API, а при помощи API. Вроде бы кажется, что эти две фразы практически идентичны, но это не так. К примеру, вспомните OpenGL. Как происходит там работа (урощённый вариант) — вначале мы настраиваем какие-то общие параметры, а потом прямо из кода вызываем методы типа «нарисовать сферу», «изменить параметры источника света» и т.д.
Так вот в OpenCL сценарий другой:
  1. При помощи API получаем доступ к устройствам, которые поддерживают OpenCL. Это часть приложения обычно называется хостом;
  2. Пишем код который будет выполняться на устройстве. Этот код называется kernel. Данный код о хосте вообще ничего не знает. Его может дернуть любой хост
  3. При помощи API прогружаем код kernel и запускаем его выполнение на выбранном устройстве.

Как видите наше приложение будет иметь комплексную инфраструктуру. Давайте займемся ее настройкой!

Так как на предыдущем шаге мы предусмотрительно подсоединили папочку include, то теперь вы можем просто добавить ссылку на заголовочный файл cl.h, который даст доступ к API. При добавление cl.h, стоит добавить проверку выбора платформы:

#ifdef __APPLE__
#include <OpenCL/opencl.h>
#else
#include <CL/cl.h>
#endif 


Теперь необходимо выбрать устройство на котором будет отрабатывать наш код и создать контекст в котором будут жить наши переменные. Как это сделать показано ниже:
/* получить доступные платформы */
ret = clGetPlatformIDs(1, &platform_id, &ret_num_platforms);

/* получить доступные устройства */
ret = clGetDeviceIDs(platform_id, CL_DEVICE_TYPE_DEFAULT, 1, &device_id, &ret_num_devices);

/* создать контекст */
context = clCreateContext(NULL, 1, &device_id, NULL, NULL, &ret);

/* создаем команду */
command_queue = clCreateCommandQueue(context, device_id, 0, &ret);


Обращаю внимание на переменную ret. Это переменная, которая содержит числовое значение которое возвращает та или иная функция. Если ret== 0, то функция выполнилась корректно, если нет, то значит произошла ошибка.
Так же заслуживает внимание константа CL_DEVICE_TYPE_DEFAULT, она запрашивает устройство, которое используется для вычислений на OpenCL по умолчанию. Вместо данной константы могут быть использованы другие. К примеру:
  • CL_DEVICE_TYPE_CPU — запросит существующие CPU.
  • CL_DEVICE_TYPE_GPU — запросит существующие GPU.

Kernel


Отлично. Настроили инфраструктуру. Теперь возьмемся за kernel. Kernel — это просто функция объявление, которой начинается с ключевого слова __kernel. Синтаксис языка программирования OpenCL базируется на стандарте C99, но имеет ряд специфических и очень важных изменений. Об этом будет (я очень надеюсь) отдельная статья. Пока базовая информация:
  1. Код который, будет дергаться с хостовой части, для исполнения, должен начинаться с ключевого слова __kernel;
  2. Функция с ключевым словом __kernel всегда возвращает void;
  3. Существуют квалификаторы типов памяти: __global, __local, __constant, __private, которые будут определять, в какой памяти будут храниться переменные. Если квалификатора перед переменной нет, то она является __private;
  4. «Общение» между хостом и kernel будет через параметры kernel. Чтобы kernel мог что-то передать хосту через параметр, параметр должен быть с квалификатором __global (пока будем использовать только __global);
  5. Код kernel принято хранить в файле с расширением cl. Но по сути подобный код может генерироваться и на лету. Это позволяет обойти некоторые ограничения. Но об этом в другой раз :)

Простейший пример kernel приведен ниже:
__kernel void test(__global int* message)
{
        // получаем текущий id.
        int gid = get_global_id(0);

        message[gid] += gid;
}

Что делает данный код. Первое — получает глобальный id work-item который сейчас выполняется. Work-item — это то что и выполняет наш kernel. Так как мы имеем дела с параллельными вычислениями, то для каждого work-item создается свой kernel который ничего не знает о других. И никто не может гарантировать в каком порядке все work-item отработают. Но об этом подробней будет в отдельной статье (уже утал это повторять). В нашем примере это по сути индекс элемента в массиве, потому что мы будем каждый элемент массива обрабатывать в отдельном work-item. Думаю вторую строчку строчку в kernel комментировать излишни :)

Формируем kernel


Следующий шаг скомпилировать, то что лежит в файле *.cl. Делается это следующим образом:
cl_program program = NULL;
cl_kernel kernel = NULL;

FILE *fp;
const char fileName[] = "../forTest.cl";
size_t source_size;
char *source_str;
int i;

try {
        fp = fopen(fileName, "r");
        if (!fp) {
                fprintf(stderr, "Failed to load kernel.\n");
                exit(1);
        }
        source_str = (char *)malloc(MAX_SOURCE_SIZE);
        source_size = fread(source_str, 1, MAX_SOURCE_SIZE, fp);
        fclose(fp);
} 
catch (int a) {
        printf("%f", a);
}

/* создать бинарник из кода программы */
program = clCreateProgramWithSource(context, 1, (const char **)&source_str, (const size_t *)&source_size, &ret);

/* скомпилировать программу */
ret = clBuildProgram(program, 1, &device_id, NULL, NULL, NULL);

/* создать кернел */
kernel = clCreateKernel(program, "test", &ret);


Типы cl_program и cl_kernel определены в cl.h. Сам сценарий довольно прост — загружаем файл, создаем бинарник (clCreateProgramWithSource) и компилируем. Если переменная ret по прежнему содержит 0, то вы все сделали правильно. И останется только создать сам kernel. Важно, чтобы имя передаваемое в команду clCreateKernel, совпадало с именем kernel в файле cl. В нашем случае это «test».

Параметры


Я уже упоминал, что «общения» kernel с хостом происходит за счет записи/чтения в параметры, которые передаются в kernel. В нашем случае это параметр message. Параметры, которые позволяют вот так общаться хосту с kernel, называются буферами(buffer). Давайте создадим такой буфер на стороне хоста и передадим в kernel через API:
cl_mem memobj = NULL;
int memLenth = 10;
cl_int* mem = (cl_int *)malloc(sizeof(cl_int) * memLenth);

/* создать буфер */
memobj = clCreateBuffer(context, CL_MEM_READ_WRITE, memLenth * sizeof(cl_int), NULL, &ret);

/* записать данные в буфер */
ret = clEnqueueWriteBuffer(command_queue, memobj, CL_TRUE, 0, memLenth * sizeof(cl_int), mem, 0, NULL, NULL);

/* устанавливаем параметр */
ret = clSetKernelArg(kernel, 0, sizeof(cl_mem), (void *)&memobj);

Важно отметить константу CL_MEM_READ_WRITE, она означает, что мы у нас есть права для буфера на чтение и запись, на стороне kernel. Так же могут быть использованы константы типа CL_MEM_WRITE_ONLY, CL_MEM_READ_ONLY и др. Так же в методе clSetKernelArg, важен второй аргумент, он содержит индекс параметра. В данном случае 0, так как параметр message идет первым в сигнатуре kernel. Если бы он шел вторым, то мы бы написали:

/* устанавливаем параметр */
ret = clSetKernelArg(kernel, 1, sizeof(cl_mem), (void *)&memobj);

clEnqueueWriteBuffer записывает данные из массива mem в буфер memobj.
Ну что в целом все готово. Осталось только выполнить kernel.

Исполняем kernel


Погнали, отправляем код на исполнение:
size_t global_work_size[1] = { 10 };

/* выполнить кернел */
ret = clEnqueueNDRangeKernel(command_queue, kernel, 1, NULL, global_work_size, NULL, 0, NULL, NULL);

/* считать данные из буфера */
ret = clEnqueueReadBuffer(command_queue, memobj, CL_TRUE, 0, memLenth * sizeof(float), mem, 0, NULL, NULL);

global_work_size содержит число work-item которые будут созданы. Я уже говорил, что на обработку каждого элемента массива у нас будет свой work-item. Элементов в массиве у нас 10, следовательно work-item содержит 10. clEnqueueNDRangeKernel особых вопросов порождать не должна — просто запускает указанный kernel заданное число раз. clEnqueueReadBuffer считывает данные из буфера с именем memobj и помещает данные в массив mem. Данные в mem и есть наш результат!

Итоги и выводы


Друзья, вот так я представляю старт в OpenCL для новичка. Надеюсь на ваши конструктивные замечания в комментариях, чтобы можно было внести апдейты в будущем. Я пытался быть кратким, но все равно объем вышел не маленький. Так что могу сказать, что материала для 2-3 статей найти еще смогу.

Спасибо, всем кто дочитал до конца!

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Дайджест интересных материалов из мира веб-разработки и IT за последнюю неделю №167 (29 июня — 4 июля 2015)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Метки лучше разделять запятой. Например: общение, социальные сети, myspace.com, подростки, мердок

или закрыть

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Устройство WebP

WebP — сравнительно новый формат от Google. Картинки в этом формате занимают на 30% меньше места на странице благодаря особому сжатию, построенному на кодировании ключевых кадров в видеокодеке VP8.

WebP поддерживает сжатие с потерями и без, разные степени прозрачности, метаданные и может содержать встроенный ICC-профиль. Но пока не все браузеры и приложения поддерживают формат.

image

Как устроено сжатие в WebP


Сжатие с потерями основано на утверждении, что яркость и цвет соседних пикселей мало отличаются друг от друга.

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

После математически обратимого преобразования (с помощью ДКП) результат подвергается квантованию и энтропийному кодированию.

image

Lossy WebP


В lossy WebP используется арифметическое кодирование — один из алгоритмов энтропийного сжатия. В WebP используется блочное квантование и биты распределяются адаптивно между различными фрагментами изображения: меньшее количество бит для фрагментов с низкой энтропией и большее — для фрагментов с высокой. Такое кодирование считается более гибким, чем код Хаффмана (который использует JPEG).

JPEG делит изображение на одинаковые блоки, а технологии кодирования WebP использует умное деление. В тех частях картинки, где есть много мелких и быстро изменяющихся деталей блоки имеют размер 4 х 4 пикселя, а в монотонных областях — 16 х 16.

image

Как происходит прогнозирование


Декодер VP8 имеет 2 класса прогнозирования:
  • Intra — внутри одного макроблока
  • Inter — прогнозирование на основе соседних макроблоков

Intra имеет четыре алгоритма прогнозирования для блоков 16х16 и 8 для детализирующих блоков 4 х 4:
  • H_PRED горизонтальное прогнозирование. Заливает следующую колонку на основе той, что находится слева от нее.
  • V_PRED вертикальное прогнозирование. Заливает следующий ряд на основе предыдущего верхнего.
  • DC_PRED заполняет блок, используя усредненные значения цвета и яркости пикселей строки
  • TM_PRED заполняет блок, используя не только усредненные значения строки A и колонки L, но и пиксель P, который находится сверху и слева от блока. Каждая строка начинается с пикселя в колонке L и заполняется в соответствии с различиями пикселей в колонке, начиная от пикселя P.

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

image

Сжатие без потерь


При сжатии без потерь используется вариант алгоритма LZ77 — кода Хаффмана. А также пространственное прогнозирование и преобразование цветового пространства.

Не только прогнозирование


Сжатие с альфа-каналом

Формат WebP позволяет получить сжатую картинку с альфа-каналом без потерь. Раньше, чтобы получить прозрачность все изображение должно было быть lossless. А в WebP можно уменьшить вес картинки с прозрачными областями.
Цветовое преобразование

Также в WebP используется методы адаптивного квантования цветовой составляющей, чтобы предотвратить влияние цветовых каналов друг на друга. Изображение делится на блоки и для каждого блока применяется свой режим трансформации green_to_red, green_to_blue или red_to_blue. Цветовое преобразование сохраняет неизменным значение зеленого канала G, преобразует красный R в зависимости от зеленого, и синий В в зависимости от зеленого, а затем в зависимости от красного.
Цветовое кеширование

Сжатие lossless WebP использует уже обработанные фрагменты изображения для работы с новыми пикселями. В случае если подходящие совпадения не найдены, используется локально созданная палитра. Эта палитра постоянно обновляется цветами, найденными при сканировании картинки.
Индексирование палитры

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

Для картинок с небольшим количеством мелких деталей используется технология апскейлинга. Прежде чем кодироваться — изображение ресайзится.

Статья написана на основе этого материала. А попробовать webp сжатие можно тут.

Конспект


  1. В WebP картинка делится на макроблоки. Блоки размером 4х4 px для мелких деталей и 16х16 для монотонных областей.
  2. Внутри каждого макроблока декодер предсказывает яркость и цвет каждого следующего пикселя на основе ранее полученных.
  3. В lossy WebP используется арифметическое кодирование, а в lossless — код Хаффмана.
  4. WebP позволяет получить сжатую картинку с альфа-каналом без потерь.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Удаленная инъкция Wi-Fi кадров

image

Стандарт WiFi 802.11n использует механизм агрегации кадров для уменьшения накладных расходов при передаче данных.
Для этого несколько кадров объединяются в один. При этом маркер разделителя кадров передается вместе с данными.
Это позволяет сформировать данные, которые при прохождении через WiFi устройство будут интерпретированы им как отдельные кадры.

То есть имея контроль над потоком данных передаваемых от сервера клиенту (например при загрузке файла с сервера атакующего) или от клиента к серверу, можно генерировать произвольные пакеты на всех уровнях OSI:

  • Пакет с любыми заголовками RadioTap: Beacon, Probe Request/Respone, Deauthentication
  • L2 уровень: указать любой MAC адрес в заголовках пакета, можно производить ARP спуфинг
  • L3/L4 уровень: скрафтить любой TCP/UDP/ICMP пакет с любыми заголовками IP
  • и так далее

Уязвимости подвержены только открытые сети стандарта 802.11n.

Схема PHY кадра с инъекцией
image

Как видно разделитель кадра (A-MPDY delimiter) помещается прямо в payload с пользовательскими данными, поэтому при получении такого кадра принимающей стороной, будет произведена деагрегация и наша последовательность будет воспринята операционной системой как отдельный пакет.

Подробнее об уязвимости можно прочесть в докладе Injection Attacks on 802.11n MAC Frame Aggregation

Код для эксплуатирования уязвимости http://ift.tt/1NDK51b

Скрипт, генерирующий payload — aggr-inject.py.
Для инъекции фреймов от точки доступа к клиенту предлагается сгенерировать jpg файл, который будет скачивать жертва (как на картинке в заголовке поста). В обратную сторону, от клиента к точке предлагается посылать специальный сформированный POST запрос на веб-сервер атакующего.
Тип передаваемых данных не имеет никакого значения, достаточно иметь возможность создать управляемый атакующим поток данных. В данном случае взят HTTP как самый простой пример. При этом важно, чтобы данные были переданы в неизменном виде на сам wifi чип, поэтому данные должны быть переданы по открытому каналу (HTTPS не подходит), не подвергаться обработке, сжатию.

Самый простой пример демонстрации уязвимости: посылка широковещательных beacon фреймов. Маяков, которые посылает точка доступа, сообщая о своем имени сети (SSID).

Файл, инъецирующий маяки с именем сети «injected SSID» aggr_beacon.jpg 250MB

Скорее всего, вы не увидите новую сеть в списке доступных для подключения WiFi сетей, так как большинство операционных систем используют активное сканирование, и показывают только сети, ответившие им на probe request. Поэтому чтобы увидеть инъекцию пакетов нужно использовать пассивное сканирование.

Кстати, на заметку тем, кто используется Mac OS, можно дампать WiFi трафик родной картой airport. Рекомендую для этого мою тулзу airport-sniffer. Дамп можно будет найти в /tmp/airportXXXX.cap

Мой тестовый стенд идентичен картинке в заголовке поста. Вредоносный файл скачивается планшетом, дампер запущен на ноутбуке, подключенном к той же точке доступа TL-MR3020 с прошивкой openwrt 12.09. Также инъекция успешно воспроизводится с использованием USB адаптера tl-wn821n.

Вот как выглядят пойманные ноутбуком пакеты:

tcpdump -e -r /tmp/airport.pcap type mgt subtype beacon
13:33:11.317916 4269971522us tsft -84dB noise antenna 0 2462 MHz 11g ht/20 72.2 Mb/s MCS 7 20 MHz short GI greenfield BCC FEC BSSID:00:00:00:00:00:00 (oui Ethernet) DA:Broadcast SA:00:00:00:00:00:00 (oui Ethernet) Beacon (injected SSID) [6.0 9.0 12.0 18.0 24.0 36.0 48.0 54.0 Mbit] ESS CH: 1
13:33:11.317916 4269971522us tsft bad-fcs -84dB noise antenna 0 2462 MHz 11g ht/20 72.2 Mb/s MCS 7 20 MHz short GI greenfield BCC FEC BSSID:00:00:00:00:00:00 (oui Ethernet) DA:Broadcast SA:00:00:00:00:00:00 (oui Ethernet) Beacon (injected SSID) [1.0* 35.0 23.0 18.0 24.0 36.0 48.0 54.0 Mbit] ESS CH: 1
13:33:11.317917 4269971522us tsft -84dB noise antenna 0 2462 MHz 11g ht/20 72.2 Mb/s MCS 7 20 MHz short GI greenfield BCC FEC BSSID:00:00:00:00:00:00 (oui Ethernet) DA:Broadcast SA:00:00:00:00:00:00 (oui Ethernet) Beacon (injected SSID) [6.0 9.0 12.0 18.0 24.0 36.0 48.0 54.0 Mbit] ESS CH: 1
13:33:11.317918 4269971522us tsft -84dB noise antenna 0 2462 MHz 11g ht/20 72.2 Mb/s MCS 7 20 MHz short GI greenfield BCC FEC BSSID:00:00:00:00:00:00 (oui Ethernet) DA:Broadcast SA:00:00:00:00:00:00 (oui Ethernet) Beacon (injected SSID) [6.0 9.0 12.0 18.0 24.0 36.0 48.0 54.0 Mbit] ESS CH: 1
13:33:11.317919 4269971522us tsft -84dB noise antenna 0 2462 MHz 11g ht/20 72.2 Mb/s MCS 7 20 MHz short GI greenfield BCC FEC BSSID:00:00:00:00:00:00 (oui Ethernet) DA:Broadcast SA:00:00:00:00:00:00 (oui Ethernet) Beacon (injected SSID) [6.0 9.0 12.0 18.0 24.0 36.0 48.0 54.0 Mbit] ESS CH: 1
13:33:11.317921 4269971522us tsft -84dB noise antenna 0 2462 MHz 11g ht/20 72.2 Mb/s MCS 7 20 MHz short GI greenfield BCC FEC BSSID:00:00:00:00:00:00 (oui Ethernet) DA:Broadcast SA:00:00:00:00:00:00 (oui Ethernet) Beacon (injected SSID) [6.0 9.0 12.0 18.0 24.0 36.0 48.0 54.0 Mbit] ESS CH: 1
13:33:11.317922 4269971522us tsft -84dB noise antenna 0 2462 MHz 11g ht/20 72.2 Mb/s MCS 7 20 MHz short GI greenfield BCC FEC BSSID:00:00:00:00:00:00 (oui Ethernet) DA:Broadcast SA:00:00:00:00:00:00 (oui Ethernet) Beacon (injected SSID) [6.0 9.0 12.0 18.0 24.0 36.0 48.0 54.0 Mbit] ESS CH: 1
13:33:11.317923 4269971522us tsft -84dB noise antenna 0 2462 MHz 11g ht/20 72.2 Mb/s MCS 7 20 MHz short GI greenfield BCC FEC BSSID:00:00:00:00:00:00 (oui Ethernet) DA:Broadcast SA:00:00:00:00:00:00 (oui Ethernet) Beacon (injected SSID) [6.0 9.0 12.0 18.0 24.0 36.0 48.0 54.0 Mbit] ESS CH: 1
13:33:12.876472 4271529509us tsft bad-fcs -85dB noise antenna 0 2462 MHz 11g ht/20 72.2 Mb/s MCS 7 20 MHz short GI greenfield BCC FEC BSSID:18:00:00:00:00:00 (oui Unknown) DA:Broadcast SA:1c:e9:87:8a:54:36 (oui Unknown) Beacon (injected SSID) [6.0 9.0 12.0 18.0 24.0 36.0 48.0 54.0 Mbit] ESS CH: 1



По таймингам видно, что инъекции происходят очень бодро.

Для того чтобы провести реальную атакую необходимо подниматься на L2 и L3 уровни, то есть нужно знать MAC адрес точки доступа, в некоторых случаях MAC адрес клиента, IP адреса клиентов за NAT. Поэтому эксплуатировать уязвимость в реальных условиях крайне сложно. Максимум — это посылать deauth пакет и отключать всех клиентов от сети.

Мне удалось успешно провести инъекции TCP пакетов и я попытался пролезть на TCP порт клиента, находящегося за NAT, пытаясь создать в nf_conntrack трансляцию, пропускающую мои пакеты клиенту. Но у меня так и не получилось. Если послать клиенту SYN от имени удаленного хоста, его ответ SYN-ACK не создает трансляцию и ответить ему из мира нельзя. Если же послать от клиента SYN в мир и ответить ему, пусть даже создав трансляцию на роутере в состоянии ESTABLISHED, новый SYN из мира посланный клиенту будет отброшен. Даже фантазии на эту тему разбились о проблему с угадыванием seqence number. Хотя, может быть, я просто лошара и у вас получится.

Подобное можно успешно провернуть с UDP. Также в примерах есть способ сканировать хосты за NAT, посылая icmp.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Vim по полной: Работа с Git


  1. Введение (vim_lib)
  2. Менеджер плагинов без фатальных недостатков (vim_lib, vim_plugmanager)
  3. Уровень проекта и файловая система (vim_prj, nerdtree)
  4. Snippets и шаблоны файлов (UltiSnips, vim_template)
  5. Компиляция и выполнение чего угодно (vim-quickrun)
  6. Работа с Git (vim_git)
  7. Деплой (vim_deploy)
  8. Тестирование с помощью xUnit (vim_unittest)
  9. Библиотека, на которой все держится (vim_lib)
  10. Другие полезные плагины

Часто ли вам приходится использовать Git? В смысле, вы коммитите изменения каждый час или каждые несколько минут? Я делаю это очень часто и не слежу за чистотой репозитория, так как считаю его не более чем журналом изменений, а не произведением искусства. Такой подход требует от редактора хорошей интеграцией с Git, позволяющей в пару нажатий клавиш создать новый коммит, вернуться в прежнее состояние, перейти на другую ветку и так далее. Если вы используете современную среду разработки, в которой реализована интеграция с Git, вам очень повезло, но что делать пользователям редактора Vim? Есть ли плагин, который не просто реализует Vim-команды по тиму GitCommit, GitCheckout и GitBranch, а предоставляет удобный интерфейс в лучших традициях редактора?
Когда я впервые задумался об интеграции Vim с Git, я, конечно же, попробовал готовые плагины и решения, но почему они все лишь реализуют команды редактора, а не предоставляют чего то большего? Я активно пользуюсь Git как с помощью CLI, так и посредством различных программ с GUI. У того и у другого есть свои плюсы и минусы, но в работе часто решаются следующие задачи:
  • Индексация и добавление коммитов
  • Просмотр изменений
  • Переход между ветками и слияние
  • Просмотр истории, ее фильтрация и переход в прежние состояния

У Git есть еще много полезного, но, как показала моя практика, чаще всего используются эти четыре действия. Важно отметить, что все они отнюдь не тривиальны. На пример, для добавления нескольких файлов в коммит нужно выполнить две команды и перечислить адреса этих файлов, что довольно долго (при использовании CLI). С другой стороны, постоянно переключаться между редактором и используемой программой с GUI для работы с Git тоже довольно накладно, так как, лично мне, тяжело переключаться между контекстом (читать — интерфейсом) используемого редактора (Vim) и GUI (мышь). Заметив это, я решил написать собственный плагин для Vim, который будет удобен пользователям этого редактора и при этом достаточно прост, даже для любителей GUI. Кстати, именно с этого плагина началась библиотека vim_lib, о которой вы уже слышали в прошлых моих статьях.

В чем же изюм этого плагина? С помощью горячих клавиш можно легко индексировать файлы, коммитить индекс и т.д. В свою очередь окна редактора используются плагином так, что получается GUI с привычным для пользователя Vim управлением. На пример, чтобы удалить ветку, достаточно открыть окно веток, навести курсор на нужную ветку и использовать dd, «как дома»!


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

Об окнах


Для начала запомните: плагин активно использует окна (window) редактора как элементы графического интерфейса.
Пример


Окна реализованы так, что используются они с помощью стандартных команд редактора Vim. То есть для выбора некоторого элемента, на пример ветки, нужно навести указатель (текстовый) на имя этой ветки, чтобы удалить ее используется команда dd, а для добавления команда a, и так везде. Все окна сопровождаются встроенной документацией, о которой сообщает подсказка вида «Branch list (Press? for help)». Нажав ?, подсказка будет развернута в том же окне.
Пример


Достаточно просто?

Об API плагина


Так же вам стоит знать: все создаваемые мной плагины реализуют API в виде Vim функций. Так, все API данного плагина присутствует в виде функций vim_git#..., на пример vim_git#status, vim_git#tagList, vim_git#branchList и т.д. Большинство плагинов при этом реализуют как пункты меню Vim, которые используют API плагина, так и команды. Лично мне удобнее биндить клавиши, это быстрее любых меню и команд редактора, но я не настаиваю.

Вот пример того, как я забиндил клавиш для плагина vim_git:

Plugin 'vim_git', {
      \  'map': {
      \    'status':      '<Leader>gs', " Окно статуса
      \    'log':         '<Leader>gl', " Окно истории коммитов
      \    'branchList':  '<Leader>gb', " Окно веток
      \    'tagList':     '<Leader>gt', " Окно тегов
      \    'addCurrent':  '<Leader>ga', " Добавить текущий файл в индекс
      \    'addAll':      '<Leader>gA', " Добавить все изменения в индекс
      \    'commit':      '<Leader>gc', " Коммит индекса
      \    'commitAll':   '<Leader>gC', " Добавить все изменения в индекс и их коммит
      \    'pushCurrent': '<Leader>go', " Push
      \    'pullCurrent': '<Leader>gi', " Pull
      \    'remoteList':  '<Leader>gr', " Окно удаленных репозиториев
      \  }
      \}


О стеке окон


Многие окна vim_git (как и всех моих плагинов) реализованы в виде стека. Это означает, что если в окне вы выполняете команду, которая приводит к открытию другого окна (на пример пытаетесь посмотреть различия между двумя коммитами), это новое окно будет открыто в текущем окне. Если вы закроете новое окно (на пример с помощью :q), то откроется первое окно. Таким образом вы используете стек окон.
Если эти моменты вам понятны, то переходим к делу.

Индекс


Для просмотра состояния индекса Git используется vim_git#status (или сочетание gs). Это окно содержит подробную информацию о состоянии репозитория и индекса в виде ответа самого Git. То есть никакой обработки плагин не выполняет, все стандартно.
Окно статуса


В данном окне реализованы следующие команды (сочетания клавишь):
  • a — добавить файл под курсором в индекс. При этом окно будет автоматически перерисовано и вы увидите что файл действительно добавлен в индекс. Чтобы не повторяться, все окна плагина перерисовываются автоматически по мере надобности
  • dd — удалить файл под курсором из индекса
  • da — удалить все файлы из индекса
  • u — восстановить файл под курсором в состояние последнего коммита
  • U — восстановить все файлы в состояние последнего коммита
  • d — показать изменения в файле в режиме
    Git-diff

  • D — показать изменения в файле в режиме
    Vim-diff


Коммит


При коммите плагин откроет новое окно, в котором вам будет необходимо написать комментарий. После сохранения и закрытия этого окна (на пример с помощью ZZ), коммит будет создан. Чтобы отменить создание коммита, достаточно закрыть окно без сохранения (:q!). Естественно в коммит попадут только те изменения, которые были добавлены в индекс на момент выполнения коммита.
Окно коммита


История коммитов


Для просмотра истории коммитов используется vim_git#log (или сочетание gl). Это окно выводит историю коммитов в двух режимах:
  • Классический — коммиты перечислены в виде блоков
    Пример


  • Граф — коммиты представлены в виде дерева
    Пример



В данном окне реализованы следующие команды (сочетания клавиш):
  • Enter — перейти на указанный коммит
  • u — отменить изменения
  • d — показать разницу между текущим состоянием репозитория и указанным коммитом в режиме Git-diff
  • v — переключиться между режимами вывода истории (классический и граф)

Отдельно следует упомянуть о фильтре и состоянии коммита.

Фильтр истории


Команда (сочетание клавиш) f открывает диалог, в котором вы можете добавить различные фильтры для истории, будь то имя интересующего вас автора или дата создания коммита.
Диалог фильтра


Состояние коммита


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


В этом окне реализованы следующие команды (сочетания клавишь):
  • d — изменения (в режиме Git-diff) в файле под курсором, внесенные коммитом
  • D — изменения (в режиме Git-vim) в файле под курсором, внесенные коммитом

Ветки


Для просмотра доступных веток (локальных и удаленных) используется vim_git#branchList (или сочетание gb).
Окно веток


В данном окне реализованы следующие команды (сочетания клавишь):
  • Enter — перейти на ветку под курсором
  • a — добавить новую ветку
  • r — переименовать ветку под курсором
  • dd — удалить ветку
  • m — слить текущую ветку с веткой под курсором
  • o — push ветки (только для локальных веток)
  • d — показать разницу между текущей веткой и веткой под курсором (в режиме Git-diff)
  • s — показать состояне ветки (аналогично состоянию коммита)
  • i — слить изменения из удаленной ветки в текущую

Удаленные репозитории


Для просмотра зарегистрированных удаленных репозиториев используется vim_git#remoteList (или сочетание gr).
Окно удаленных репозиториев


В данном окне реализованы следующие команды (сочетания клавиш):
  • a — добавить новый псевдоним удаленного репозитория
  • dd — удалить псевдоним под курсором
  • r — переименовать псевдоним под курсором
  • f — получить изменения из репозитория под курсором
  • i — получить и слить изменения из удаленного репозитория под курсором в текущую ветку
  • o — отправить все изменения текущей ветки в удаленный репозиторий под курсором

Теги


Для просмотра тегов используется vim_git#tagList (или сочетание gt).
Окно тегов


В данном окне реализованы следующие команды (сочетания клавиш):
  • Enter — перейти на коммит, на который указывает тег под курсором
  • a — добавить новый тег для текущего коммита
  • A — добавить аннотирующий тег для текущего коммита
  • dd — удалить тег под курсором
  • s — показать информацию о теге

Сила плагина в удобном API и GUI, что позволяет мне активно пользоваться Git не выходя из редактора. Конечно я не осветил все функции vim_git, так как статья уже довольно длинна и не хочется утомлять читателя, потому вы найдете еще много интересного в этом плагине (на пример с помощью go легко push'ить, а с помощью gi pull'ить изменения).

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

[unable to retrieve full-text content]

[Перевод] Семь удивительных «возможностей» Javascript

За последние несколько месяцев я сделал несколько доработок для JSHint, в основном с целью изучить ES6 (я особенно горжусь тем, как переделано обнаружение областей видимости для переменных). Во время этого процесса я наткнулся на несколько вещей, которые меня удивили — в основном, в ES6, однако есть и кое-что про ES3, что я до этого никогда не использовал.

Break из любого блока


Наверняка вы знаете, что в любом цикле можно использовать ключевые слова break и continue — это стандартная возможность в современных языках программирования. Однако не все знают, что циклам можно давать метки и с их помощью прерывать любой конкретный цикл:
outer: for(var i = 0; i < 4; i++) {
    while(true) {
        continue outer;
    }
}


То же самое применимо и к break. Вы наверняка видели, как он используется в выражении switch:
switch(i) {
   case 1:
       break;
}


Вообще говоря, именно поэтому Крокфорд не советует добавлять отступы перед case — выражение break выкидывает из блока switch, а не case, но мне вариант с отступами кажется более читабельным. Выражения switch также можно помечать меткой:
myswitch: switch(i) {
   case 1:
       break myswitch;
}


Также можно объявлять блоки просто так. Знаю, что это также доступно в C#, и наверняка в других языках тоже:
{
  {
      console.log("Я внутри произвольного блока");
  }
}


Если сложить все это вместе, можно выйти из любого блока с помощью метки:
outer: {
  inner: {
      if (true) {
        break outer;
      }
  }
  console.log("Эта строчка никогда не выполнится");
}


Разумеется, это относится только к break — оператор continue допустим только внутри цикла. Я ни разу не видел метки в коде на Javascript — скорее всего, потому, что если вдруг понадобится экстренно выйти из более чем одного блока, это повод переписать код на функцию с return.

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

function(a, b, c) {
  if (a) {
     if (b) {
       return true;
     }
     doSomething();
     if (c) {
       return c;
     }
  }
  return b;
}


Добавляем метки, и получается вот что:
function(a, b, c) {
  var returnValue = b;
  myBlock: if (a) {
     if (b) {
       returnValue = true;
       break myBlock;
     }
     doSomething();
     if (c) {
       returnValue = c;
     }
  }
  return returnValue;
}


Или же, можно было бы использовать больше блоков:
function(a, b, c) {
  var returnValue = b;
  if (a) {
     if (b) {
       returnValue = true;
     } else {
       doSomething();
       if (c) {
         returnValue = c;
       }
    }
  }
  return returnValue;
}


Вообще, вариант с метками мне нравится меньше всех, но может только потому, что я к нему не привык?

Деструктуризация существующей переменной


Сперва — фишка, которую я не могу могу объяснить. В ES3, судя по всему, можно добавить скобки вокруг переменной при присваивании и это будет работать:
var a;
(a) = 1;
assertTrue(a === 1);


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

Деструктуризация — это процесс получения значения переменной из объекта или массива. Чаще всего можно видеть подобный пример:

function pullOutInParams({a}, [b]) {
  console.log(a, b);
}
function pullOutInLet(obj, arr) {
  let {a} = obj;
  let [b] = arr;
  console.log(a, b);
}
pullOutInParams({a: "Hello" }, ["World"]);
pullOutInLet({a: "Hello" }, ["World"]);


Но можно сделать то же самое и без let, var и const. Для массива достаточно написать вот так:
var a;
[a] = array;


А вот с объектом не получится — его необходимо обернуть в круглые скобки:
var a;
({a} = array);


Причина в том, что это дает слишком большой простор для двусмысленного толкования и ошибок, связанных с анонимными блоками кода, потому как автоматическая расстановка точек с запятой превращает идентификаторы в вычисляемые выражения, а они могут иметь побочные эффекты:
var a = {
   get b() {
     console.log("Превед!");
   }
};
with(a) {
  {
    b
  }
}


Возвращаясь к изначальному примеру, где мы заключили присваивание в круглые скобки — вопреки предположениям, это не имеет никакого отношения к деструктуризации:
var a, b, c;
(a) = 1;
[b] = [2];
({c} = { c : 3 });


Деструктуризация с числами


Еще один аспект деструктуризации, о которой не все могут подозревать — это то, что названия свойств не обязательно должны быть незакавыченными строками. Это могут быть числа:
var {1 : a} = { 1: true };


Или строки в кавычках:
var {"1" : a} = { "1": true };


А еще можно вычислять имя свойства из выражения:
var myProp = "1";
var {[myProp] : a} = { [myProp]: true };


Это позволяет с легкостью написать очень запутанный код:
var a = "a";
var {[a] : [a]} = { a: [a] };


Объявления класса привязаны к блоку


Объявления функции поднимаются в самый верх блока, что позволяет использовать их до объявления:
func();
function func() {
  console.log("Все в порядке");
}


А вот если функция объявляется в ходе присваивания переменной, то поднимается только объявление переменной, но не присваивание ей значения:
func(); // func объявлена, но не имеет значения, поэтому ошибка "func не является функцией"
var func = function func() {
  console.log("Всё в порядке");
};


Классы — одна из наиболее популярных частей спецификации ES6, и всегда считались своего рода синтаксическим сахаром для функций. Однако если вы думаете, что этот код заработает, то вы ошибаетесь:
new func();

class func {
  constructor() {
    console.log("Все в порядке");
  }
}


Несмотря на сходство с первым примером, оно не работает. На самом деле это эквивалент следующего кода:
new func();

let func = function func() {
  console.log("Fine");
}


Тут мы пытаемся обратиться к func внутри временной мертвой зоны, что является синтаксической ошибкой.

Параметры-тёзки


Я предполагал, что у функции не может быть двух параметров с одним и тем же именем — а на самом деле может!
function func(a, a) {
  console.log(a);
}

func("Привет", "Мир");
// выводит "Мир"


Однако в strict mode всё не так:
function func(a, a) {
  "use strict";
  console.log(a);
}

func("Привет", "Мир");
// в Chrome будет ошибка - SyntaxError: Strict mode function may not have duplicate parameter names


Оператор typeof небезопасен


Ладно, ладно, я украл это наблюдение, но повторить все равно будет не лишним.

До ES6 было широко известно, что с помощью оператора typeof можно безопасно узнать, объявлен ли идентификатор, даже если ему не присвоено значение:

if (typeof Symbol !== "undefined") {
  // Symbol доступен
}
// Этот код выкинет исключение, если Symbol не объявлен
if (Symbol !== "undefined") {
}


Но теперь это работает только в том случае, если вы не объявили переменную с помощью let или const. Всему виной ВМЗ, из-за которой обращение к переменной до ее присваивания является синтаксической ошибкой, даже несмотря на то, что «под капотом» объявление переменной все равно поднимается в самый верх блока.
if (typeof Symbol !== "undefined") {
  // Symbol доступен
}
let Symbol = true; // вызывает синтаксическую ошибку в условии выше!


Создание массива


Я всегда избегал создания массива с помощью ключевого слова new. В основном потому, что аргументы могут быть либо длиной массива, либо его элементами:
new Array(1); // [undefined]
new Array(1, 2); // [1, 2]


Однако коллега недавно наткнулся на кое-что, что мне раньше не встречалось:
var arr = new Array(10);
for(var i = 0; i < arr.length; i++) {
  arr[i] = i;
}
console.dir(arr);


Этот код выдает массив с числами от 0 до 9. А что будет, если отрефакторить его с использованием map?
var arr = new Array(10);
arr = arr.map(function(item, index) { return index; });
console.dir(arr);


Массив остался неизменным. Судя по всему, конструктор, принимающий длину, создает массив и задает свойство length, но не создает никаких элементов. Поэтому обратиться к свойству можно, а перечислить элементы нельзя. А если задать значение какому-нибудь элементу?
var arr = new Array(10);
arr[8] = undefined;
arr = arr.map(function(item, index) { return index; });
console.dir(arr);


Получаем массив, где восьмому элементу присвоено число 8, но все остальные значения не заданы. Если посмотреть на код полифилла для функции map, она проверяет заданность свойства с помощью оператора in. Такого же поведения можно достичь с помощью литералов массива:
var arr = [];
arr[9] = undefined;
// или же
var arr = [];
arr.length = 10;


Другие жемчужины


В блоге разработчиков Mozilla есть отличная статья про функции со стрелками, где говорится о том, что комментарии можно помечать символом <--. Неплохо почитать и остальные посты в блоге.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

пятница, 3 июля 2015 г.

О тонкостях приватности в Telegram Bots API: «это не баг, это фича»

imageНеделю назад в мессенджере Telegram был запущен Bots API — платформа для создания ботов. Платформа пусть немного сыроватая, слегка костыльная, но тем не менее интересная — как для пользователей, так и для разработчиков, которые тут же ринулись писать (и портировать) разнообразных ботов. Но, как оказалось, в API есть как минимум одна особенность, которая может показаться довольно неожиданной (и даже неприятной) для конечных пользователей.

Сразу оговорюсь: данная заметка не является очередным нападком на защищенность Телеграма. Более того, учитывая дружеские отношения с некоторыми из разработчиков мессенджера, писать статью не особенно хотелось. Но предостеречь тех, кто планирует создавать и, главное, пользоваться ботами в Telegram, мне показалось важным. «Платон мне друг, но истина дороже».

Сначала вкратце для рядовых пользователей. Если вы отправляете какому-то боту в Телеграме фотографию (рассчитывая, что бот потом эту фотографию отправит другому человеку), — помните, что конечный получатель фото (при желании) легко сможет узнать ваше имя/фото/юзернейм (и сможет связаться с вами напрямую). Даже если бот предполагает приватность и анонимность. Этот интересный аспект крайне неочевиден даже для самих создателей ботов. И они (пока что!) ничего не могут с этим сделать. Строго говоря, это касается не только фотографий (а почти всех видов прикреплений), но увидеть ваш профиль в других случаях несколько сложнее.

В том числе этому подвержен приведенный в качестве примера в описании новой платформы @HotOrBot. В этом «аналоге Тиндера» можно легко подсматривать аккаунты тех, чьи фото вам предлагают оценить (и, собственно, писать им — даже если они ещё не ответили вам взаимностью).

(как видно на иллюстрациях, достаточно открыть фотографию, например, в веб-версии Телеграма)

В созданном мною @TalkBot (он позволяет анонимно общаться в «комнатах» в духе IRC или тет-а-тет, выступая в роли посредника) та же проблема: не шлите в комнату-чатик фотографии, если не хотите быть деанонимизированы. Но мой бот хотя бы предупреждает всех об этом.

Техническая подоплека и почему эту проблему нельзя решить без участия Телеграма. Сейчас с отправленным боту файлом бот может сделать только одно: взять его айдишник (file_id) и отправить кому-то ещё (это forward не самого сообщения, а только вложенной картинки/видео/аудио/документа, в документации это выглядит просто как трюк для экономии ресурсов). Получить тело файла в данный момент, к сожалению, нельзя (очевидно, это будет реализовано в ближайшее время, поскольку фича архиважная). В противном случае можно было бы не использовать тот же file_id, а залить фото заново (хоть какой-то workaround был бы). Сейчас иного решения, кроме как предупреждать пользователей (или ограничивать функциональность вовсе), нет.

Почему это не баг в платформе? Формально такое поведение более-менее задокументировано (конструкторы InputMediaPhoto vs InputMediaUploadedPhoto, а также возвращаемый объект photo) в обычном API, поэтому багом считаться не может. И вообще, боты создаются третьими сторонами — какая уж тут приватность. Учитывая позиционирование Телеграма как мессенджера, делающего упор на приватность, возможно, клиентским приложениям стоит более явным образом давать понять, что все отправляемые ботам данные полностью открыты авторам ботов (какой бы банальностью это не звучало).

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

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Каламбуры на css

сегодня в 21:48

Хабровчане, всех с пятницей! Сейчас у подавляющего большинства читателей хабра рабочий день уже закончился, поэтому можно расслабиться и немного отвлечься от серьезных тем. Вы знали, что на css можно каламбурить? На кдпв один из примеров, а под катом небольшая простыня специфических css шуток.
#big-bang::before { 
content: "";
}

.lego {
display: block;
}

.autobots {
transform: translate3d();
}

.ninja {
color: black;   
visibility: hidden;
animation-duration:0.00001s;
}

#china { 
border-top-style: solid;
}

#tower-of-pisa { 
font-style: italic;
}

#australia { 
transform: rotateY(180deg);
}

.kkk {
color: white !important; 
}

.ikea {
display: table
}

.moonwalk { 
transition: .2s ease-in-out; transform: translateX(-300px);
}

.rich-people {
top: 1%;
}
.working-class {
bottom: 99%;
}

.slimshady {
vertical-align: top;
}

.sith {
position:absolute;
}

.delorean { 
z-index: -1955;
}

.illuminati { 
position: absolute;
visibility: hidden;
}

.twins {
flex-grow:1;
}

.gangsta-rap { 
word-spacing: 0;
}

* {
position: relative;
}

.beer { float: right; float: left; float: right; float: left; float: right; float: left; float: right; float: none; }


Если тема интересна — стоит гуглить «CSS Puns», если же хорошо работает фантазия — пишите свои каламбуры в комментариях.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

[Из песочницы] Четно-нечетная сортировка слиянием Бэтчера

Введение


Алгоритм четно-нечетной сортировки слиянием (odd-even mergesort) был разработан Бэтчером в 1968 году. Алгоритм не слишком популярный и не слишком известный. Однако он достаточно легко параллелится и его реализация не слишком сложна. Лично я узнал о нем когда разбирался с MPI и увидел тестовое задание на coursera: написать сортировку Бэтчера.

Базовые операции


Приведенный код не идеален в плане производительности, однако он наиболее прост для восприятия и понимания алгоритма.

В алгоритме нам понадобятся три следующих абстрактных операции:

compare-exchange — меняем элементы местами, если они идут не по порядку.

template <class T>
void compexch(T& a, T&b)
{
    if (b < a)
        std::swap(a, b);
}


perfect shuffle — делим массив пополам и далее первый элемент первой половины — первый в результате, первый элемент второй половины — второй в результате, второй первой половины — третий в результате и т.д. Массив обязательно четной длины. Фактически, мы расставляем элементы первой половины по четным позициям, а из второй — по нечетной.
template <class T>
void shuffle(std::vector<T>& a, unsigned int l, unsigned int r)
{
    auto half = (unsigned int) (l + r) / 2;
    std::vector<T> tmp(a.size());
    unsigned int i, j;
    for (i = l, j = 0; i <= r; i += 2, j++)
    {
        tmp[i] = a[l + j];
        tmp[i + 1] = a[half + j + 1];
    }
    for (auto i = 0; i < tmp.size(); i++)
       a[i] = tmp[i];
}


perfect unshuffle — операция, обратная предыдущей. Элементы, занимающие четные позиции, отправляются в первую половину массива-результата, нечетные — во вторую.
template <class T>
void unshuffle(std::vector<T>& a, unsigned int l, unsigned int r)
{
    auto half = (unsigned int) (l + r) / 2;
    std::vector<T> tmp(a.size());
    unsigned int i, j;
    for (i = l, j =0; i<=r; i += 2, j++)
    {
        tmp[l + j] = a[i];
        tmp[half + j + 1] = a[i + 1];
    }
    for (auto i = 0; i < tmp.size(); i++)
        a[i]  = tmp[i];
}


Собственно алгоритм


Как это часто бывает в постах/статьях/книгах про сортировки, мы предполагаем, что приходящий нам на вход массив имеет размер, равный степени двойки. Это упростит описание алгоритма и доказательство его корректности. Это ограничение снимем потом.

С помощью введенных операций алгоритм формулируется довольно просто. С помощью операции unshuffle мы разбиваем массив на две половины. Далее надо уже отсортировать каждую из этих половин и потом слить обратно с помощью операции shuffle. Алгоритм не просто так называется четно-нечетной сортировкой слиянием — подход аналогичен известной merge sort, разве что логика разбиения на части другая — по четности индекса, а не просто пополам.

Простейшая реализация с помощью введенных операций:

template <class T>
void OddEvenMergeSort(std::vector<T>& a, unsigned int l, unsigned int r)
{
    if (r == l + 1) compexch(a[l], a[r]); //мы дошли до подмассива размера 2 - теперь просто сравним элементы
    if (r < l + 2) return; //дошли до подмассива размера 1 - выходим, такой подмассив априори отсортирован
    unshuffle(a, l, r); //делим подмассив на две части
    auto half = (unsigned int) (l + r) / 2;
    OddEvenMergeSort(a, l, half);
    OddEvenMergeSort(a, half + 1, r); //вызываемся рекурсивно для половинок
    shuffle(a, l, r); //сливаем части
    for (auto i = l + 1; i < r; i += 2)
        compexch(a[i], a[i + 1]);
    auto halfSize = (r - l + 1) / 2 - 1;       //*
    for (int i = l + 1; i + halfSize < r; i++) //*
        compexch(a[i], a[i + halfSize]);    //*
}


Замечание
Если вы, как и я, читали про этот алгоритм у Сэджвика в «Фундаментальных алгоритмах на С++», то можете заметить, что у него в функции OddEvenMergeSort нет строк, помеченных "*". Уж опечатка это или что, не знаю. Однако алгоритм, приведенный в его книге, ошибается, например, на строке «ABABABAB».

После первого же вызова unshuffle мы получим «AAAABBBB». Далее мы вызываемся рекурсивно для частей «AAAA» и «BBBB». Будем считать, что алгоритм работает верно. Тогда после вызовов мы так и получим части «AAAA» и «BBBB». Сделаем shuffle, получим «ABABABAB». Попарное сравнение выродится в 4-х кратный вызов compexch(«A», «B»), которые ничего не изменят.

Три добавленные строки решают эту проблему. В будущем, если будет время, опишу, почему.


Описание


Сам принцип работы практически ничем не отличается от merge sort, однако операции слияния выполняются совершенно по-разному. Если в merge sort мы заводим два индекса — в первой и во второй половине массива, где половины уже отсортированы, и на каждом шаге просто ставим в результат наименьший из текущих в каждой половине, то здесь мы просто делаем операцию shuffle, а потом попарное сравнение получившегося массива.

Как запустить?


Достаточно вызвать
 OddEvenMergeSort(a, 0, a.size() - 1); 

Как быть с массивами длины не являющейся степенью двойки?


Самый простой способ — добавить необходимое число элементов до степени двойки, которые априори все больше (или все меньше) любого элемента в исходном массиве.

Второй подход такой.

Т.к. любое число можно представить как сумму степеней двойки, то разбить массив на такие подмассивы, отсортировать их по отдельности сортировкой Бэтчера и объединить с помощью операции, аналогичной слиянию в merge sort
При этом маленькие подмассивы можно сортировать другим алгоритмом, который, например, не требует рекурсивных вызовов.

Пример работы

AGINORSTAEELMPXY
AIOSAEMXGNRTELPY
AOAMISEX
AAOM
AA
  MO
AMAO
AAMO
    IESX
    EI
      SX
    ESIX
    EISX
AEAIMSOX
AAEIMOSX
        GREPNTLY
        GERP
        EG
          PR
        EPGR
        EGPR
            NLTY
            LN
              TY
            LTNY
            LNTY
        ELGNPTRY
        EGLNPRTY
AEAGELINMPORSTXY
AAEEGILMNOPRSTXY

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

[Из песочницы] Формула подсчёта количества дней в месяце

Примечание: данный пост является переводом статьи http://ift.tt/1yTV54k (Часть I), а также авторским к нему дополнением (Часть II). Не следует относиться к материалу серьёзно, а скорее как к разминке для ума, требующей не более чем школьных знаний арифметики и не имеющей практического применения. Всем приятного чтения!

Вступление


Недавно, после очередной бессонной ночи, я размышлял о методах запоминания количества дней в каждом месяце года. Для этого есть считалочка, а также способ считать на костяшках пальцев, но ни то, ни другое меня не устроило. Я задумался, а не существует ли какой-нибудь математической формулы для решения такой задачи, и — не обнаружив при беглом изучении таковую — бросил себе вызов её создать.

ФормализуяДругими словами, необходимо найти функцию f, такую, что значение f(x) для каждого месяца x, представленного числом от 1 до 12, равняется количеству дней в этом месяце. Таблица значений аргумента и функции1:

x 1 2 3 4 5 6 7 8 9 10 11 12
f(x) 31 28 31 30 31 30 31 31 30 31 30 31

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

Ниже следуют мои шаги по нахождению решения.

Математический аппарат


Сначала бегло освежим в памяти два жизненно необходимых в решении этой задачи оператора: целочисленное деление и остаток от деления.

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


Остаток от деления это оператор, находящий остаток от деления. Во многих языках программирования применяется символ %, я же буду использовать конструкции вида , например:

Замечу, что остаток от деления имеет равный с делением приоритет.

Основы


Итак, применим наш математический аппарат для получения базовой формулы.2 В обычном месяце 30 или 31 день, так что мы можем использовать для получения поочерёдно 1 или 0, а затем просто прибавить к этому числу константу:

Получаем таблицу, полужирным выделены корректные значения:
x 1 2 3 4 5 6 7 8 9 10 11 12
f(x) 31 30 31 30 31 30 31 30 31 30 31 30

Неплохое начало! Уже есть правильные значения для января и для месяцев с марта по июль включительно. Февраль — особый случай, и с ним мы разберёмся чуть позже. После июля для оставшихся месяцев порядок получения 0 и 1 должен быть изменён на обратный.
Для этого мы может прибавить к делимому 1:

x 1 2 3 4 5 6 7 8 9 10 11 12
f(x) 30 31 30 31 30 31 30 31 30 31 30 31

Теперь правильные значения с августа по декабрь, но, как и предполагалось, значения для прочих месяцев неверны. Давайте посмотрим как мы можем объединить эти формулы.

Наложение маски


Для этого необходима кусочно-заданная функция, но — так как мне это показалось скучным — я задумался о другом пути решения, использующем одну часть функции на одном интервале, другую — на другом.
Полагаю, что проще всего будет найти выражение, равное 1 в одной области применения и 0 — в остальной. Метод, в котором умножая аргумент на выражение мы исключаем его из формулы вне области его применения, я назвал «наложением маски», потому такое поведение подобно некой битовой маске.
Для применения этого метода в последней части нашей функции необходимо найти выражение, равное 1 при , и — так как значения аргумента всегда меньше 16 — для этого прекрасно подходит целочисленное деление на 8.
x 1 2 3 4 5 6 7 8 9 10 11 12
x8 0 0 0 0 0 0 0 1 1 1 1 1

Теперь с помощью этой маски, используя в делимом выражение вместо 1, мы можем заменить порядок получения 0 и 1 формуле на обратный:

x 1 2 3 4 5 6 7 8 9 10 11 12
f(x) 31 30 31 30 31 30 31 31 30 31 30 31

Эврика! Всё правильно, кроме февраля. Сюрприз-сюрприз.

Февраль


В любом месяце 30 или 31 день, кроме февраля с его 28 (високосный год выходит за рамки этой задачи).3 На текущий момент по нашей формуле в нём 30 дней, поэтому неплохо бы вычесть выражение, равное 2 при .
Лучшее что мне удалось придумать это , что накладывает маску на все месяцы после февраля:
x 1 2 3 4 5 6 7 8 9 10 11 12
2 mod x 0 0 2 2 2 2 2 2 2 2 2 2

Изменив базовую константу на 28 с добавлением 2 к остальным месяцам получим формулу:

x 1 2 3 4 5 6 7 8 9 10 11 12
f(x) 29 28 31 30 31 30 31 31 30 31 30 31

К сожалению, январь теперь короче на 2 дня. Но, к счастью, получить выражение, которое будет применяться только для первого месяца очень легко: это округлённое вниз обратное к число. Умножив его на 2 получаем окончательную формулу:

x 1 2 3 4 5 6 7 8 9 10 11 12
f(x) 31 28 31 30 31 30 31 31 30 31 30 31

Послесловие


Вот она — формула для получения количества дней в любом месяце года, использующая простейшую арифметику. В следующий раз когда вы будете вспоминать сколько же дней в сентябре, просто выполните с помощью этой однострочной функции на JavaScript:
function f(x) { return 28 + (x + Math.floor(x/8)) % 2 + 2 % x + 2 * Math.floor(1/x); }

Вступление


В первой части была получена короткая и даже немного изящная формула, основными достоинствами которой являются простота математического аппарата, отсутствие ветвлений и условных выражений, лаконичность. К недостаткам — кроме того, что вы не будете применять её в вашем проекте — можно отнести отсутствие проверки на вискокосный и не високосный год.
Поэтому я поставил перед собой задачу создать функцию f, такую, что значение f(x, y) для каждого месяца x, представленного числом от 1 до 12 и года y, большего 0, равняется количеству дней в месяце x в году y.
Для нетерпеливых под спойлером находится готовый ответ, остальных же прошу следовать за мной.
Ответ

Остаток от деления: mod и ⌊⌋


Для визуальной наглядности договоримся, что в некоторых формулах оператор деления с остатком заменён нижними скобками, там где это показалось мне необходимым:

Високосный год


В високосный год вводится дополнительный день календаря: 29 февраля. Как известно, високосным является год, кратный 4 и не кратный 100, либо кратный 400. Запишем тождественное этому высказыванию выражение:

Математическим аналогом будет следующая функция g(y), значением которой будет 0, если год високосный, или число, большее 0 в обратном случае:


y 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004
g(y) 960 1446 0 486 976 1470 0 494 992 1494 0 2 8 18 0

Полужирным выделены високосные года.

Неплохо, но недостаточно. Следующим шагом необходимо к функции g(y) применить инъекцию вида:


Что позволит изменить значение функции на 1 для високосных лет и 0 для не високосных, чтобы использовать её в формуле определения количества дней в месяце:

В качестве функции g' можно использовать 1 минус остаток от деления для :
x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
g'(x) Infinity 1 0 0 0 0 0 0 0 0 0 0 0 0 0

Легко заметить, что увеличив делимое и делитель на 1 мы получим правильную формулу при :
x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
g'(x) 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Соответственно, применив функцию g' к значению функции g получаем формулу:

y 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004
g(y) 960 1446 0 486 976 1470 0 494 992 1494 0 2 8 18 0
g'(g(y)) 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1

Напоминаю, что в рамках принятой договорённости оператор получения остатка от деления может быть изображен как mod, так и ⌊⌋.

Наложение маски


В формуле часть является поправкой, прибавляющей 2 дня к январю. Если убрать множитель 2 и в числителе заменить 1 на 2, тогда эта формула будет прибавлять 2 дня к январю и 1 день к февралю, что даёт нам ключ к добавлению дня в високосном году. Для наглядности используем в формуле промежуточное значение g'(y) и в качестве y используем 2000 (високосный) и 2001 (не високосный) годы:

x 1 2 3 4 5 6 7 8 9 10 11 12
f(x, 2000) 31 29 31 30 31 30 31 31 30 31 30 31
f(x, 2001) 30 28 31 30 31 30 31 31 30 31 30 30

Значения для всех месяцев, кроме января не високосного года верны.

Для исправления этого досадного недоразумения добавим к январю 1 день уже известной нам формулой :


x 1 2 3 4 5 6 7 8 9 10 11 12
f(x, 2000) 32 29 31 30 31 30 31 31 30 31 30 31
f(x, 2001) 31 28 31 30 31 30 31 31 30 31 30 30

Теперь необходимо вычесть 1 день из января в случае високосного года, для чего нам поможет знание того, что для любого x , а .

Так как , тогда формула итоговая формула примет вид:



Или:

x 1 2 3 4 5 6 7 8 9 10 11 12
f(x, 2000) 31 29 31 30 31 30 31 31 30 31 30 31
f(x, 2001) 31 28 31 30 31 30 31 31 30 31 30 30

Заключение


В результате получена уже значительно более громоздкая, но более универсальная формула, которую также можно использовать для получения количества дней в месяце определённого года:
function f(x,y) { return 28 + (x + Math.floor(x / 8)) % 2 + 2 % x + Math.floor((2 - ((y % 4) * ((y % 100) + (y % 400)) + 2) % ((y % 4) * ((y % 100) + (y % 400)) + 1)) / x) + Math.floor(1/x) - Math.floor((1 - ((y % 4) * ((y % 100) + (y % 400)) + 2) % ((y % 4) * ((y % 100) + (y % 400)) + 1))/x); }

Пример на C# ideone.com/dnmv7A.


1. Я не умею пользоваться подобной мнемоникой, поэтому подсмотрел табличку в интернете.
2. «Основы», или «Правило С Многими Исключениями», как и большинство правил.
3. Изначально в римском календаре февраль был последним месяцем года, поэтому есть логика в том, что он короче всех остальных. Также есть логика в добавлении или удалении дня именно в конце года, поэтому его длина является переменной.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.