Как стать автором
Обновить
3
Карма
0
Рейтинг
Vadim Sukhomlinov @VSukhomlinov

embedded systems, security

  • Подписчики 7
  • Подписки 8

Программный генератор статистически безупречных случайных чисел

это называется deterministic random bit generator :) весь вопрос в размере внутреннего состояния, обратимости функции и возможности предсказать следующие значения по истории (потому внутреннее состояние должно быть относительно большим). в криптографически стойких обычно использует функцию типа вычисления хеша (SHA256 итп), которая сложно обратима. полностью случайные только аппаратные генераторы, где используются физические процессы.

Программный генератор статистически безупречных случайных чисел

попробуйте проверить статистику с помощью webhome.phy.duke.edu/~rgb/General/dieharder.php — стандартный набор тестов для проверки качества генераторов. Есть стандартные генераторы типа HMAC_DRBG, но они довольно ресурсоемкие, есть типа xoroshiro (http://prng.di.unimi.it/) — весьма неплохие.
Без результатов тестов утверждения о качестве не очень обоснованы. Кроме того для «легких» тестов генераторов можно использовать Adaptive Proportion Test и Repetitive Count Test, хотя последний больше на аппаратные генераторы ориентирован. Они описаны в nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90B.pdf 4.4.1 и 4.4.2.

Перевод числа в строку с помощью FPU

можно и в исходниках разные реализации найти для удобства. различных аппроксимаций для функций много. www.netlib.org/fdlibm например. Есть и библиотеки с поддержкой векторов — скажем синус 4-х аргументов за раз (Intel SVML и др). можно попробовать в таком стиле реализовать перевод чисел в строку — сразу 2-4 за проход.

Перевод числа в строку с помощью FPU

мне интересно не растёт ли погрешность при вычислении степени десятки через логарифм — для чисел меньше 1 надо домножить на положительные степени 10, многие из которых представимы точно и вычисление их через логарифм скорее всего будет неточным. но с другой стороны у FPU 80-бит точность, так что может и не существенно. Но я бы сравнил по этому показателю и разобрался бы откуда отклонения возникают, если они есть. FBSTP — вероятно даёт самое большое сокращение кода — мне эта команда всегда нравилась, и жаль что её нет в SSE наборе :)
вообще при изменении типа округления на FPU его хорошо бы восстановить к предыдущему значению, так как другие вычисления могут бы чувствительны.
И финальный код с делениями на 10 — для ускорения можно делить на 100 и брать 2 символа из таблицы, но я не думаю, что это место критично по производительности. Еще можно задействовать AAM/AAD вместо DIV на константу, но я не уверен, что они остались в 64-битном режиме.

Перевод числа в строку с помощью FPU

интересный подход, понравилось удаление периодических 9-ок в конце, но есть нюанс — в 64-битном режиме на x86 используется SSE+ для арифметики с плавающей точкой. В принципе и в 32-битном режиме тоже можно использовать SSE. Все использованные инструкции в коде имеют аналоги в SSE (FBSTP, увы нет) и позволяют напрямую адресовать регистры, вместо стека. FXTRACT можно в целочисленных регистрах сделать, и вместо пошагового умножения/деления на 10 сделать «пристрелку» по степени 2 — умножить на константу log10 (2), получить степень 10ки, возвести 10 в эту степень по таблице или быстрым способом и скорректировать число. деления вообще заметно медленнее, вместо деления на 10 быстрее умножать на 1/10, но теряется точность.

Программистское везение

у меня 2 гипотезы:
1) эта запись вызывала задержку на шине, которая для чего то была необходима — проверка — записать в какой-то другой порт.
2) это мало документированная фича для работы с адресами выше 16МБ, где адрес 24-бита уже недостаточно.
docs.freebsd.org/doc/3.4-RELEASE/usr/share/doc/handbook/dma.html
A new implementation of the 8237, called the 82374, allows 16 bits of page register to be specified, allows access to the entire 32 bit address space, without the use of bounce buffers.

Предлагаю подумать: как технологии могут помочь бороться с пропагандой в СМИ?

хорошие идеи. для себя — я обычно читаю а не смотрю, и читаю новости из разных стран, чтобы разные точки зрения видеть. Есть стартапы вроде www.thefactual.com которые пытаются автоматизировать этот процесс, удалять эмоциональную оценку, оставляя факты, предлагая разные интерпретации их.

Оптимизация C++: совмещаем скорость и высокий уровень. Доклад Яндекса

Например embedded платформы разных видов с 128-256KB RAM, 256K-1MB Flash, 25-100МГц, но надо криптографию реализовать с приемлемой скоростью — профилирование очень затруднительно, разве что в симуляции или виртуальной машине.
alignas — относительно свежее (по моим меркам %) нововведение, раньше надо было либо вручную выравнивать, либо нестандартные расширения использовать.
Абсолютно согласен, что для большинства обычных приложений нет смысла всем этим заниматься. Кроме тех случаев, когда без этого никак :) Скажем, обработка сетевых пакетов 40Gbit, при 64х байтных пакетах времени на классификацию — порядка 12 нс, да можно разбить на несколько ядер… но доступ к памяти — 100+нс, и без оптимизации под кеш не обойтись. И там либо ты успеваешь все обработать, либо будут потери пакетов. Но там на С++ мало кто пишет — обычно чистый С внизу или что-то типа С+ с очень выборочным набором используемых средств. Даже чередование банков памяти (interleaving) при выделении буферов начинает играть роль, не говоря уже про performance counters для анализа непредсказанных переходов, кеш-промахов, загрузку исполнительных блоков процессора, итп — приходится изучать не только где тормозит, но еще и почему.

Оптимизация C++: совмещаем скорость и высокий уровень. Доклад Яндекса

likely задаёт ожидаемый путь исполнения, что тоже полезно. __builtin_expect() задает ожидаемое значение выражения для количества итераций, что влияет на решения по оптимизации. в принципе это можно получить в процессе профилировки, если есть такая возможность на целевой платформе. мы говорим о разных вещах тем не менее — я про то как выжать максимум из компилятора, а вы про то как в С++ это правильно написать.
#pragma GCC unroll, iv_dep, aligned, optimize, итп — расширения компилятора и в стандарте С++ отсутствуют, но бывают полезны когда надо выжать максимум.
while, do в C++ никто не отменял, да и goto в общем-то тоже. да, некрасиво, зато позволяет обойти узкие места.

Оптимизация C++: совмещаем скорость и высокий уровень. Доклад Яндекса

безусловно компилятор может сделать очень многое и с каждой новой версией качество оптимизаций возрастает. с gcc использование __builtin_expect() и __builtin_expect_with_probability() для указания наиболее вероятного значения по моим экспериментам давало хороший результат в коде, в ряде случаев __builtin_assume_aligned() оказывался полезным (скажем void * указатель, который на самом деле всегда выровнен при использовании функции). Но форма записи цикла, проверки граничных условий тоже сильно влияет на качество кода, причем зависит от версии к версии компилятора. По конкретный компилятор можно научится писать так, чтобы код был качественный, но если нужна поддержка нескольких компиляторов приходится идти на компромиссы или использовать ассемблер или intrinsics.

Оптимизация C++: совмещаем скорость и высокий уровень. Доклад Яндекса

по стандарту vector и array — вроде как zero-cost abstractions, которые не должны ухудшать код, а проверки должны удаляться на этапе компиляции, выносится из цикла по возможности, но как их наличие сказывается на оптимизации — вопрос весьма интересный. В Gnu libstdc++ их вроде как нет — только косвенное обращение, в libstdcxx они как asserts github.com/llvm-mirror/libcxx/blob/master/include/vector#L1546. Но даже само наличие косвенных обращений влияет на возможности оптимизации — компилятор должен вынести их из цикла, количество проходов ограничено, итп.

Оптимизация C++: совмещаем скорость и высокий уровень. Доклад Яндекса

оптимизация доступа в память, блочная обработка — это одно из первых действий. загрузка кеш-линиями, блоки под размер кешей. при использовании нескольких потоков — cache sharing, в том числе false sharing (доступ к разным частям одной кеш-линии). я обычно сразу смотрю в ассемблерный код, чтобы понять что и как и очень подозрительно отношусь к использованию vector и прочих STL в коде, где нужна производительность — проверки диапазона индексов, выделения памяти — всё дает накладные расходы, ограничивает оптимизации, часто до С-стиля спускаюсь. Если целевая машина понятна, то можно сразу писать с расчетом на векторизацию и доступный набор инструкций, использование intrinsic со своеобразными инструкциями, которые компилятор маловероятно что применит (но шанс дать надо). Я еще компилирую вычислительное ядро gcc, clang и что есть под рукой (godbolt в помощь), чтобы быстро проверить потенциал автоматической компиляции, взять от компилятора удачные элементы и помочь где надо ручками. У Intel раньше много материалов было на тему подходов к оптимизации, сейчас с разгона мало что могу найти — software.intel.com/content/www/us/en/develop/articles/intel-parallel-computing-centers-training.html, software.intel.com/content/www/us/en/develop/videos/optimization-for-intel-parallel-architectures.html

Полное руководство по сезонной депрессии (SAD). 7 видов светотерапии

Я экспериментировал с лампами OSRAM BIOLUX — они дают спектр близкий к солнечному с примесью ближнего УФ и позиционируются как лампы, которые дают естественный для животных свет. Ну я подумал, а чем я хуже и попробовал :) Собрал светильник из 8 х 18Вт ламп (в обычный квадратный поставил в 2 раза больше ламп) и поставил в ванную — супруга сказала, что свет шикарный. Сейчас не уверен, можно ли найти эти лампы в продаже. В 2013 я заказывал их с доставкой из Германии, и до сих пор запас еще есть небольшой. Они относительно недорогие были — около 200р за лампу, но по 20шт в упаковке.

Расчет факторов в антифроде. Доклад Яндекса

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

Новый, инновационный дизайн шурупа от Outlaw Fasteners ломает все многовековые устои

похожая конструкция давно используется для спец. саморезов для массивной доски. например, e-u-r-o-tec.ru/shop/paneltwistec/Hobotec_zk/
у этих только головка отличается. идея интересная, но преимущество относительно Torx надо бы в цифрах увидеть — когда срывает предложенную конструкцию и когда Torx и PH / PZ. экономия времени только если приходится часто менять размеры саморезов, а это редко. обычно каким-то одним типом работаешь, потом другим, так что удобство есть, но проявляется нечасто. кроме того, нужны разные варианты саморезов — тот что сделали на дерево ориентируется, а было бы полезно тогда и варианты по металлу, гипсокартону итп и массовые поставки.

Детектирование и локализация произвольного текста на изображениях, полученных с помощью фотокамер мобильных телефонов

В свое время я делал штуку для выделения текста (номера автомобиля) и применил построчно для этого прямое и обратное БПФ — после прямого отбрасывал в результате те гармоники, которые относятся к очень низким и очень высоким частотам и делал обратное преобразование. после этого применял нечто, что называл «инерциальный» фильтр — по сути суммировал вдоль строки яркости бегущим окном и если значение было больше порога, то отмечал точку. В результате получал размеченные зоны, где был некоторый ритм, характерный для текста. Это еще в 97-98гг было, работало почти в реальном времени на i486, правда с камеры было невысокое разрешение. БПФ помню еще Watcom C компилировал, а потом руками дооптимизировал, sin & cos по таблице итп.

Линус Торвальдс предлагает 2560х1600 как новый стандарт для ноутбуков

с самими шрифтами проблем никаких — масштабируются отлично. но кроме растровых картинок есть еще другие элементы интерфейса, где размеры задаются в абсолютных пикселях, и при изменении DPI текст перестает вмещаться. Этим грешат и Дельфи и разные UI библиотеки, и некоторые особо талантливые разработчики независимо от средств разработки) Даже Start-menu, taskbar не очень хорошо себя ведут. Да и темы оформления, когда размеры шрифта для одного элемента управления приложения используют для других, в результате получается, что все работает только при стандартных настройках. ОС может ввести режим совместимости, когда приложению будут указываться «стандартные» 96 DPI, а изображения, размеры элементов — пропорционально увеличиваться. шаг к этому уже сделан в виде опции совместимости «disable high DPI scaling», но она не решает проблему маленьких шрифтов.

Линус Торвальдс предлагает 2560х1600 как новый стандарт для ноутбуков

эта байка, которую поддерживает толпа не очень опытных пользователей и продавцов в магазинов. Мелко. Все что нужно сделать для избавления от этого — сделать чтобы Windows 8 автоматически настраивала размер шрифтов в зависимости от размера экрана и разрешения (DPI) и обеспечило корректную работу собственных приложений с различным DPI, разработчики приложений разрабатывали соответственно в соответствии с правилами.
В WIndows 8 для десктоп-приложений, по-прежнему есть проблема с масштабированием шрифтов — большинство приложений съезжает. Может быть разработчикам в Microsoft как-то помочь, раз сами не справляются? :)

А я, так полностью согласен с Линусом — для профессиональной работы, разработки итп — высокое разрешение является большим плюсом. Бьюсь с дистрибьюторами, чтобы ввозили и «правильные» конфигурации (благо большинство вендоров имеют в ассортименте панели высокого разрешения), но проблема идет от ритейла и извращенного понимания потребностей пользователей. Ну и цена, конечно выше, и под концепцию «дайте мне розовый ноутбук 13» за 20т.р. на полку" не подходит.

Машинный перевод и автоматический словарь в Яндексе

это похоже на недостатки статистического перевода) в моем случае, в «сводках ООН :)» вероятно фигурировала фраза «no action is required', которая корректно переводится как „никаких действий не требуется“. Но при этом частица „не“ ассоциирована в таком словосочетании с „никаких“, а остаток фразы соответственно неправильно. есть гипотеза, что такая проблема будет со многими фразами, которые на русский переводятся с двойным отрицанием.
А вот пример how much is the fish — очень странный. how much is the bread — нормально переводиться как „сколько стоит хлеб“, было бы логично, чтобы и все замены существительного правильно переводились. Я надеюсь Яндекс прояснит в чем тут дело. Пока видно, что структура предложения никак не анализируется.

Машинный перевод и автоматический словарь в Яндексе

иногда странно как то переводит — видимо структура предложения вообще на анализируется. пример: перевод 'action required' ->'необходимые действия', а 'action is required' ->'действий не требуется'. Откуда взялось 'не' остается только гадать. Возможно тексты ООН некорректно переведены были, отсюда и проблемы :) Кстати, Google Translate тоже страдает этой болезнью на этом примере.

Информация

В рейтинге
Не участвует
Откуда
Santa Clara, California, США
Дата рождения
Зарегистрирован
Активность