• Стандартная библиотека Visual Studio 2015 и телеметрия

      Преамбула


      Программы на C и C++, как правило, проводят бо́льшую часть своей жизни внутри функции main() и функций, прямо или косвенно вызываемых из main(). Тем не менее, на самом деле выполнение программы начинается вовсе не с main(), а с некоторого кода из стандартной библиотеки, поставляемой вместе с компилятором. Таковой код, по идее, должен подготавливать окружение для других функций стандартной библиотеки, которые, возможно, позовёт main(), а также параметры самой main() (под Windows; Unix-системы имеют тенденцию передавать argc/argv/envp в подготовленном виде прямо при запуске процесса, но речь не о них). Симметрично, завершающий return в функции main() — вовсе не последняя инструкция программы, после него следует ещё немного кода из стандартной библиотеки.
      В Visual Studio «настоящая» точка входа в программу называется mainCRTStartup. В комплекте с VS идут исходники стандартной библиотеки, в VS2015 определение mainCRTStartup находится в %PROGRAMFILES(X86)%\VC\crt\src\vcruntime\exe_main.cpp, но, впрочем, всю работу выполняет exe_common.inl рядом. Давайте туда посмотрим.
      ...
              // If this module has any thread-local destructors, register the
              // callback function with the Unified CRT to run on exit.
              _tls_callback_type const * const tls_dtor_callback = __scrt_get_dyn_tls_dtor_callback();
              if (*tls_dtor_callback != nullptr && __scrt_is_nonwritable_in_current_image(tls_dtor_callback))
              {
                  _register_thread_local_exe_atexit_callback(*tls_dtor_callback);
              }
      
              __telemetry_main_invoke_trigger(nullptr);
      
              //
              // Initialization is complete; invoke main...
              //
      
              int const main_result = invoke_main();
      
              //
              // main has returned; exit somehow...
              //
      
              __telemetry_main_return_trigger(nullptr);
      
              if (!__scrt_is_managed_app())
                  exit(main_result);
      
              if (!has_cctor)
                  _cexit();
      
              // Finally, we terminate the CRT:
              __scrt_uninitialize_crt(true, false);
              return main_result;
      ...
      

      Ой, а что это за вызовы __telemetry, обрамляющие вызов main?
    • Особенность оригинальной реализации Color Lines


        Игра Color Lines aka «Шарики» в особом представлении, вероятно, не нуждается: компьютер заваливает доску 9*9 шариками разных цветов, человек может перемещать их по свободным клеткам, выстраивая в ряды. Ряды от 5 и более шариков одного цвета самоуничтожаются; если это произошло после хода человека, ему начисляются очки и даётся ещё один ход; если в процессе наброса от компьютера, то очки самоуничтожаются вместе с шариками.

        Игра имеет большое число клонов, от входящих в поставку Gnome и KDE до реализаций на JavaScript в 30 строк. Тем не менее, большинство реализаций не учитывает одну интересную особенность, присутствующую в оригинальной DOS-игре, и заметно влияющую на геймплей.

        Опытные игроки (в компетентности которых не позволяли сомневаться их рекорды, намного большие, чем у меня) уверяли, что компьютер выбирает места для новых шариков вовсе не случайно, а так, чтобы «ломать» горизонтальные и вертикальные ряды и, как следствие, рекомендовали концентрироваться на выстраивании диагональных рядов. Понятно, что естественная реализация выбора места «взять случайное поле из свободных» безразлична к направлению рядов. Что же под капотом у DOS-реализации?
        Читать дальше →
      • Гипотеза Бёрча — Свиннертон-Дайера

          Эта примечательная гипотеза связывает поведение функции L там, где в настоящее время неизвестно, определена ли она, и порядок группы Ш, про которую неизвестно, конечна ли она!
          J.T.Tate, The arithmetic of elliptic curves, Inventiones mathematicae 23 (1974)
          Оригинал
          This remarkable conjecture relates the behaviour of a function L at a point where it is not at present known to be defined to the order of a group Ш which is not known to be finite!
          (Краткая справка насчёт актуальности цитаты 40-летней давности: после Уайлса и Ко таки стало известно, что функцию L можно определить на всей комплексной плоскости. Конечность группы Ш в общем случае остаётся неизвестной.)
          Остаётся обсудить возможность ошибки. В качестве предосторожности против внутренних ошибок компьютера можно прогнать все вычисления дважды или делать проверки внутри программы. Более того, компьютеры — в отличие от людей — устроены так, что их ошибки обычно чересчур велики, чтобы их не заметить. Мы уверены, что в наших результатах нет подобных ошибок. С другой стороны, при кодировании замысловатой схемы вычислений в компьютерную программу неизбежны программистские ошибки. Большинство из них обнаруживаются ещё до основных запусков, из-за того, что программа виснет или выдаёт нелепые результаты. Но программа, которую считается работающей, всё ещё может содержать логические ошибки, проявляющиеся при редких стечениях обстоятельств: и действительно, большинство компьютеров подвержено аномалиям, из-за которых те иногда ведут себя не так, как должны по спецификациям. В сущности, наша программа для этапа (ii) оказалась неточной и пропустила очень небольшое количество эквивалентностей, которые должна была найти.

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

          B.J.Birch and H.P.F.Swinnerton-Dyer, Notes on elliptic curves. I, Journal für die reine und angewandte Mathematik 212 (1963)
          Оригинал
          It remains to discuss the question of error. One can take precautions against machine errors either by running all the calculations twice or by checks included in the program. Moreover, machines — unlike human beings — are so designed that the errors they make are usually too gross to be overlooked. We are satisfied that there are in our results no undetected errors of this sort. On the other hand, in translating an elaborate scheme of calculation into a machine program one is bound to make mistakes. Most of these are found before the program is used for production runs; they show up because the program grinds to a halt or produces ridiculous results. But a program which is believed to work may still contain logical errors which only have an effect in rare circumstances: and indeed most computers have anomalies which cause them occasionally not to behave in the way that their specifications suggest. In fact, our program for stage (ii) was imperfect in that a very few equivalences were missed by the machine.

          For these reasons we believe that results obtained from a computer should not be automatically trusted. In some cases they can be checked because they have properties which were not essentially used in the course of the calculation and which would be unlikely to survive if an error had been made. (For example, if a table of a smooth function has been calculated without the use of interpolation, it can be checked by differencing.) But if checks of this sort are not available, results should not be fully trusted until they have been independently reproduced by a different programmer using a different machine. We do not think this sets an unreasonable standard, now that computers are becoming so widely available; and we are satisfied that lower standards have already led to a number of untrue results being published and believed.


          Под катом не будет формулировки гипотезы; знающие выражения вроде «Euler product» и «holomorphic continuation» (и в смысле языка, и в смысле обозначаемых понятий) могут прочитать пятистраничный pdf с сайта института Клэя. Под катом — некоторая попытка пояснить, на каком направлении развития математической мысли вообще находится гипотеза Бёрча — Свиннертон-Дайера. А также — как можно досчитать до больших чисел вроде тех, что показаны на КДПВ, менее чем за секунду.
          Читать дальше →
          • +21
          • 14,6k
          • 8
        • Почему Windows 95 подвисала при форматировании дискеты?

          • Перевод
          Рэймонд Чен отвечает на известную шутку:
          — Папа, покажи, какая винда многозадачная!
          — Сейчас, сынок, только дискету доформатирую...

          Кто же целыми днями форматирует дискеты? Оказывается, многие гики только этим и заняты. (Вообще-то, можно покупать дискеты уже отформатированными, только тссс!) Но почему Windows 95 подвисала при форматировании дискеты?

          Всё дело в совместимости с MS-DOS.

          Как мы видели немного раньше, MS-DOS в Windows 95 выступала как слой для старых 16-битных драйверов. Несмотря на то, что в итоге операции ввода-вывода обрабатывались 32-битной файловой подсистемой, все они проходили через 16-битный код, чтобы 16-битные драйверы, TSR и подобные обработчики видели «нормальные 16-битные операции» и работали в привычном им окружении.

          В 16-битном мире форматированием занималось программное прерывание 13h, и многие программы использовали этот факт, перехватывая прерывание так, чтобы получать управление при форматировании дискеты. Так делали некоторые TSR, программы для бэкапов (программы для бэкапов, разработанные для Windows 3.0, включали в себя 32-битные драйверы под Windows 3.x, называемые VxD, для отслеживания операций с дискетами). Но это объясняет не всё. В конце концов, Windows 95 прогоняла весь дисковый ввод-вывод, а не только форматирование дискет, через 16-битный код. Почему же форматирование дискет так существенно влияло на систему?

          Читать дальше →
        • Какую роль играла MS-DOS в составе Windows 95?

          • Перевод
          MS-DOS в составе Windows 95 использовалась для двух целей:
          • Она служила загрузчиком.
          • Она выступала в качестве слоя совместимости с 16-битными драйверами.
          Когда Windows 95 стартовала, сначала загружалась специальная версия MS-DOS, именно она обрабатывала ваш файл CONFIG.SYS, запускала COMMAND.COM, который выполнял ваш AUTOEXEC.BAT и в конце концов выполнял WIN.COM, который в свою очередь начинал процесс загрузки 32-битного менеджера виртуальных машин VMM.

          Эта специальная версия MS-DOS была полностью функциональна в той мере, в которой слова «полностью функциональна» вообще применимы к MS-DOS. По-другому и быть не могло, при выходе в режим эмуляции MS-DOS только эта версия и оставалась работать.

          Программа WIN.COM начинала загрузку того, что большинство людей называют собственно «Windows». Посредством копии MS-DOS она загружала менеджер виртуальных машин, считывала файл SYSTEM.INI, загружала драйверы виртуальных устройств, затем выключала EMM386 (если таковой был) и переключалась в защищённый режим. «Настоящая Windows» с точки зрения большинства людей — именно защищённый режим.

          В защищённом режиме драйверы виртуальных устройств творили свою магию. В числе их действий было вытаскивание всего состояния MS-DOS, перевод его в состояние 32-битной файловой подсистемы и отключение MS-DOS. Все дальнейшие файловые операции направлялись в 32-битную файловую подсистему. Когда программа обращалась к int 21h, ответственной за обработку оказывалась 32-битная файловая подсистема.

          Здесь вступает в игру вторая роль MS-DOS. Видите ли, программы и драйверы MS-DOS любили встраиваться в глубины операционной системы. Они могли заменять обработчик прерывания 21h, они могли патчить код системы, они могли заменять низкоуровневые дисковые обработчики int 25h и int 26h. Они могли также творить умопомрачительные вещи с прерываниями BIOS типа int 13h, ответственного за работу с дисками.

          Читать дальше →
        • Представление чисел суммой двух квадратов и эллиптические кривые

            Пусть p — нечётное простое число. Довольно широко известно, что p представимо в виде суммы двух квадратов целых чисел p=a2+b2 тогда и только тогда, когда p при делении на 4 даёт остаток 1: 5=12+22, 13=32+22, 17=12+42, ...; 3, 7, 11,… непредставимы. Куда менее известно, что a и b можно записать красивой формулой, имеющей непосредственное отношение к одной эллиптической кривой. Об этом результате 1907 года за авторством немца по фамилии Jacobsthal и о связанных вещах мы сегодня и поговорим.

            Совсем легко понять, почему 3, 7, 11 и прочие числа, дающие при делении на 4 остаток 3, непредставимы в виде a2+b2: квадрат чётного числа всегда делится на 4, квадрат нечётного числа всегда даёт остаток 1 при делении на 4, сумма двух квадратов при делении на 4 может давать остатки 0, 1 или 2, но никак не 3. Представимость простых чисел вида 4k+1 неочевидна (особенно если заметить, что простота существенна: число 21 хотя и имеет нужный остаток, но суммой двух квадратов не представляется).

            Читать дальше →
          • Ищем коды уровней в Prehistorik-2


              В игре Prehistorik 2 не предусмотрены сейвы, но на каждом уровне есть (болтается в воздухе в некотором месте уровня) код уровня. Есть два режима прохождения, Beginner и Expert, код также определяет режим. При старте игры можно начать с первого уровня, а можно ввести код и попасть сразу на соответствующий уровень. На одном и том же компьютере с неизменным окружением коды не меняются, но на разных компьютерах коды, вообще говоря, разные, так что коды, найденные при прохождении и тщательно выписанные на бумажку, станут совершенно бесполезны в другом окружении. Поэтому вместо бумажки лучше иметь программу, которая пишет коды для конкретного окружения. Готовый результат: genpass.com, представляет из себя DOS-программу, которая должна запускаться в том же окружении, что и игра. Альтернативный вариант попасть на нужный уровень из экрана ввода кода: ввести три кода ADDE C0DE F00D либо DEAD C0DE F00D, каждый из трёх кодов сам по себе неверен, но при вводе их в таком порядке четвёртый код — номер уровня от 1 до 10, плюс 10 для режима Expert, приводит сразу на запрошенный уровень.

              Под катом — процесс исследования. Требуется знание ассемблера x86 хотя бы на уровне «читаю со словарём».

              Читать дальше →
            • Архив Рекурсивный.7z: какой-то файл и архив Рекурсивный.7z

              Формат архивов 7-Zip довольно гибкий и позволяет, например, включать весь архив как один из файлов внутри самого архива, лишь немного считерив. Разберём формат на примере: создадим почти вручную архив с именем «Рекурсивный.7z», содержащий два файла: «Какой-то файл.txt» с содержимым «Hello, Habrahabr!» и «Рекурсивный.7z», копию самого себя.

              Краткая документация по формату входит в LZMA SDK. Архив начинается со следующей структуры размером 32 байта. Все позиции внутри архива кодируются как смещения относительно конца этой структуры.
              сигнатура, 6 байт: { '7', 'z', 0xBC, 0xAF, 0x27, 0x1C };
              версия формата, два байта { Major, Minor }, 7-Zip 9.20 пишет сюда { 0, 3 };
              CRC следующих трёх полей, 4 байта;
              смещение основного заголовка относительно конца этой структуры, 8 байт;
              размер основного заголовка, 8 байт;
              CRC основного заголовка, 4 байта.

              Далее следуют данные файлов без какой бы то ни было информации о самих файлах и о границах данных. Основной заголовок, который описывает всё содержимое архива, размещается в конце архива.

              Основной заголовок может быть сам по себе упакован (а также зашифрован). Поскольку он содержит структурированные данные (типа имён файлов), коэффициент сжатия достаточно неплохой. Именно для возможности подобного сжатия вся информация о файлах в 7z собрана в одном заголовке и полностью отделена от сжатых данных файлов. Признак упакованности — первый байт основного заголовка: он должен быть равен 1 у неупакованного заголовка и 0x17 у упакованного. Для создания архива вручную мы не будем ничего сжимать.

              Читать дальше →