Не так давно в процессе разработки редактора 2D-графики возникла задача разложить матрицу аффинного преобразования на плоскости, на произведение матриц простых преобразований с тем, чтобы отобразить их пользователю и предложить какую-то более-менее адекватную интерпретацию того, что произошло с объектом на канвасе. Честно говоря, эта задача вызвала у меня определенные трудности. Университет я закончил уже давно, и мне было непонятно, а возможно ли это сделать в принципе, учитывая, что исходная матрица могла быть результатом произвольной последовательности сдвигов, масштабов, поворотов, и переносов, причем каждое преобразование могло иметь свой произвольный центр. И, во-вторых, непонятно было, как найти семь параметров, имея всего шесть коэффициентов матрицы. Ключом к решению этой задачи оказалась статья "Разложение матрицы центроаффинного преобразования для нормализации изображения"¹, в которой рассматривается такая же задача, но без учета преобразования переноса и для преобразований относительно центра координат. Далее я фактически просто адаптирую результаты этой статьи с учетом переноса и для произвольного центра преобразований.Читать полностью »
Рубрика «Программирование» - 736
Разложение матрицы аффинного преобразования
2016-03-04 в 13:57, admin, рубрики: Алгоритмы, математика, матрицы, ПрограммированиеОбзор физики в играх Sonic. Части 3 и 4: прыжки и вращение
2016-03-04 в 8:39, admin, рубрики: game development, Sonic the hedgehog, Алгоритмы, Программирование, старые игры, физика 
От переводчика: части обзора имеют небольшой размер, поэтому решил переводить сразу по две. Часть первая, часть вторая.
Читать полностью »
8 марта, мамы и программирование
2016-03-04 в 7:41, admin, рубрики: 8 марта, mail.ru, Блог компании Mail.Ru Group, Программирование, пятницаПривет! Кажется, иногда могут быть посты-исключения, а не только посты с кусками кода? Сегодня в блоге у нас именно тот случай. Посмотрите наше небольшое видео (кстати, код есть на 3-й секунде). Не забудьте поздравить маму с 8 марта и сказать ей «спасибо»!
Первый хакатон 2ГИС
2016-03-04 в 6:24, admin, рубрики: Блог компании 2ГИС, веб-дизайн, Веб-разработка, Программирование, хакатон, Хакатоны 
На прошлых выходных мы организовали в новосибирском офисе 2ГИС первый открытый хакатон. Не будем рассказывать, как было круто, какие классные проекты выиграли и вот это всё. Мы поделимся некоторыми советами для организаторов подобных мероприятий и зададим пару вопросов.
Читать полностью »
Обзор и сравнительное тестирование ПЭВМ «Эльбрус 401‑PC». Дополнение — вопросы и ответы
2016-03-03 в 17:41, admin, рубрики: 1891ВМ8Я, 1991ВГ1Я, Debian, E2K, ELBRUS, epic, Firefox, LCC, OSL, VLIW, Железо, защищённое исполнение программ, МЦСТ, Программирование, Процессоры, Софт, ЭльбрусПожалуй, главным результатом публикации этого обзора, — помимо собственно ознакомления общественности с первыми независимыми впечатлениями от нового компьютера, — стало желание самой фирмы МЦСТ раскрыть побольше подробностей, устранить возникшие недоразумения и ответить на вопросы, поднимаемые в статье и в комментариях к ней. Некоторые из этих вопросов настолько фундаментальны, что заслуживают по отдельной статье каждый, и потому требуют серьёзной проработки. Сейчас же мы рассмотрим те из них, которые лучше всего укладываются в формат интервью.
Шустрый потокобезопасный менеджер кучи и голый Си
2016-03-03 в 15:39, admin, рубрики: C, c++, Алгоритмы, параллельное программирование, Программирование, программирование; c; c++;, метки: программирование; c; c++;При планировании любой задачи мы стремимся как можно точнее конкретизировать запросы, определить исходные данные и по возможности избавиться от любой неопределенности, мешающей просчитать конечный результат. Однако при разработке высокоуровневой логики не всегда уделяется внимание таким простым казалось бы вещам, как размещение данных в памяти, менеджмент потоков, обрабатывающих наш функционал, особенности реализации динамических массивов или бинарный интерфейс процедур. Когда написанная программа предельно лаконична и оптимизирована, но при этом работает не так быстро, как хотелось бы, закономерно возникает вопрос: «а что еще можно улучшить?» Насколько можно доверять низкоуровневому инструментарию, написанному профессиональными программистами, безусловно разбирающимися в своем деле, но при этом ни черта не понимающими в тех идеях, что вы хотите реализовать? Фрагментация, зацикленность, прерывания, события, объекты, уведомления, каждое новое знакомство с Си-шными или WinAPI-шными библиотеками подталкивает к очевидной мысли: «зачем такая громоздкая реализация?» Почему нельзя просто сделать менеджер кучи выделяющий память за строгое количество шагов? Использовать real-time статистику при работе с разделяемыми данными, вместо сложной системы семафоров и уведомлений? Наращивать динамические массивы без переразмещения и обращаться к случайной ячейке за одинаковое время после любого количества реформаций? Миссия не кажется невыполнимой. Осталось только попробовать.
Предлагаю широкому вниманию процедурную реализацию менеджера кучи, способного выделять диапазоны памяти заказных размеров. Цикл поиска при этом не превышает нормированных пределов. Работа с памятью состоит всего из двух процедур: memAlloc и memRecycle, выполняющих связанные функции. Потокобезопасность поддерживается с помощью дополнительного инструментария, в свою очередь состоящего еще из нескольких процедур. О распараллеливании немного поподробнее: принцип базируется на ассоциированной блокировке разделяемых данных, схожих с блокировкой шины методами Interlocked, однако без блокировки шины. Весь процесс сводится к созданию позиционных стопоров, являющихся по сути диапазонами памяти, содержащими однобайтовые метки состояний каждого из потоков в доступном пуле. Размер выводится из этого соотношения. Поскольку я использую восьмипотоковый пул (а больше мне не нужно), то позиционные стопоры у меня занимают 8 байт (64 бита). Перед перезаписью разделяемой информации стопор блокируется исполняющим потоком, записывая метку в байт под смещением своего номера в пуле. Другие потоки не будут работать с разделяемыми данными пока стопор не обнулится, выполняя Sleep, либо откладывая задачу, либо считая овечек в цикле, на выбор программиста.
Клоны Interlocked процедур — threadExchange, threadCompareExchange и threadIncrement выполняют те же функции, что и оригиналы. Однако при работе внутри потока из пула не блокируют шину. Вместо этого используется ассемблерная процедура, задача которой сводится к двухступенчатой проверке стопора и установке собственной метки (стоит отметить, что при работе вне пула, в потоке не имеющем номера, все же используется блокировка шины). Ее реализация ниже:
Читать полностью »
Обзор примитивов синхронизации
2016-03-03 в 14:03, admin, рубрики: condition variables, Mutex, semaphore, spinlock, Программирование, программирование микроконтроллеров, системное программированиеСинхронизация нужна в любой малтитредной программе. (Если, конечно, она не состоит из локлесс алгоритмов на 100%, что вряд ли). Будь то приложение или компонента ядра современной операционной системы.
Меня всё нижесказанное, конечно, больше волнует с точки зрения разработки ядра ОС. Но почти всё применимо и к пользовательскому коду.
Кстати, ядра старых ОС в примитивах синхронизации не нуждались, поскольку преемптивной мультизадачности внутри ядра в старые добрые времена не было. (Уж за Юникс 7-й версии я отвечаю. Не было.) Точнее, единственным методом синхронизации был запрет прерываний. Но об этом позже.
Сначала перечислим героев. Мне известны следующие примитивы синхронизации:
User/kernel mode: mutex+cond, sema, enter/leave critical section.
Kernel only: spinlock, управление прерываниями.
Зачем всё это нужно, читатель, наверное, знает, но всё же уточним.
Если некоторая структура данных может быть доступна двум параллельно работающим нитям (или нити и прерыванию), и являет собой сущность, к которой нельзя обеспечить атомарный доступ, то работу с такой структурой нужно производить так, чтобы только одна нить одновременно выполняла сложные манипуляции состоянием структуры.
Читать полностью »
Теория и практика парсинга исходников с помощью ANTLR и Roslyn
2016-03-03 в 13:39, admin, рубрики: .net, antlr, AST, C#, java, php, PLSQL, roslyn, tsql, Блог компании Positive Technologies, грамматика, Компиляторы, неоднозначность, ошибка синтаксиса, парсинг, ПрограммированиеВ нашем проекте PT Application Inspector реализовано несколько подходов к анализу исходного кода на различных языках программирования:
- поиск по сигнатурам;
- исследование свойств математических моделей, полученных в результате статической абстрактной интерпретации кода;
- динамический анализ развернутого приложения и верификация на нем результатов статического анализа.
Наш цикл статей посвящен структуре и принципам работы модуля сигнатурного поиска (PM, pattern matching). Преимущества такого анализатора — скорость работы, простота описания шаблонов и масштабируемость на другие языки. Среди недостатков можно выделить то, что модуль не в состоянии анализировать сложные уязвимости, требующие построения высокоуровневых моделей выполнения кода.
К разрабатываемому модулю были, в числе прочих, сформулированы следующие требования:
- поддержка нескольких языков программирования и простое добавление новых;
- поддержка анализа кода, содержащего синтаксические и семантические ошибки;
- возможность описания шаблонов на универсальном языке (DSL, domain specific language).
В нашем случае все шаблоны описывают какие-либо уязвимости или недостатки в исходном коде.
Весь процесс анализа кода может быть разбит на следующие этапы:
- парсинг в зависимое от языка представление (abstract syntax tree, AST);
- преобразование AST в независимый от языка унифицированный формат;
- непосредственное сопоставление с шаблонами, описанными на DSL.
Данная статья посвящена первому этапу, а именно: парсингу, сравнению функциональных возможностей и особенностей различных парсеров, применению теории на практике на примере грамматик Java, PHP, PLSQL, TSQL и даже C#. Остальные этапы будут рассмотрены в следующих публикациях.
Читать полностью »
Грэйс «бабуля COBOL» Хоппер
2016-03-03 в 11:23, admin, рубрики: edison software, Блог компании Edison, Компиляторы, Программирование, стандарты«Она истинный морпех, но если копнуть глубже, мы найдем пирата.»
Грейс Хоппер (Grace Hopper) — американская учёная и контр-адмирал флота США. Программист гарвардского компьютера Марк I.
- В детстве разобрала 7 будильников, чтобы понять, как все устроено.
- Боролась за идею машинонезависимого языка программирования.
- Разработала первый компилятор.
- Приложила руку к распространению мема «дебаггинг» (выловив настоящего жука из Mark 2).
- Могла объяснить сообразительным военным, что такое «наносекунда» и «пикосекунда». На пальцах.
- В её честь назвали эсминец USS Hopper (DDG-70).
- И суперкомпьютер Cray XE6 «Hopper».
- И в ее честь именная премия Ассоциациеи вычислительной техники (ACM) — присуждается молодому (до 35 лет) специалисту, сделавшему значительный вклад в области вычислительной техники.
Построив успешную карьеру математика в Йеле (защитив докторскую и став профессором), Грэйс Хоппер в 1943 (37 лет) пошла добровольцем во Флот.
Но у нее был недобор по весу 6 кг, поэтому пришлось сесть «за клавиатуру» Гарвардского Mark 1.
Читать полностью »
Чем плохо быть full stack разработчиком
2016-03-03 в 10:33, admin, рубрики: Full Stack, Веб-разработка, карьера, Программирование, разработкаВведение
Прежде всего определимся с терминами. Есть много разных представлений о том, кто же такой full stack разработчик, кто-то даже вполне обоснованно считает, что такие разработчики — это миф, но в этой статье будет иметься в виду разработчик, который обладает знаниями и умениями, позволяющими с нуля написать некий софт и вывести его в продакшн. При этом софт может быть рассчитан на web платформу, мобильные приложения или десктопные. Идеальный full stack разработчик — это тот, кто владеет в какой-то мере всеми платформами и может разработать и установить на них свой софт. Но это действительно скорее миф.
Ну или хотя бы кого-то, кто не будет слишком сильно жаловаться, когда его попросят поработать вне его зоны комфорта.
Возможно, по заголовку кому-то покажется, что это жалобный пост, который говорит о том, как плохо живётся неквалифицированному школьнику, который похватал всего из разных статей в интернете. Нет, пост не жалобный, мы говорим про full stack, а не full slack, и в конце будет так же рассмотрен список плюсов. И мы будем рассматривать не школьника, а разработчика с опытом работы в пять и более лет. Просто посмотрим, какие минусы есть в таком развитии.
Читать полностью »