Перейти к содержимому

Fingercomp

Гуру
 Профиль  Активность

  • Публикации

    1 629

  • Зарегистрирован

  • Посещение

  • Победитель дней

    283

Записи блога, опубликованные пользователем Fingercomp

  1. Fingercomp
    Последняя, пятая часть мастеровления полностью посвящена шеллу и его программам. Переменные окружения, алиасы и с ними связанные команды — я не врал.

    Сложность: высокая 75%
    Скучность: высокая 75%
    Дубовость: для продвинутых 80%

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


    ШЕЛЛ OPENOS.
    Сразу предупреждаю, что мы не будем рассматривать в данном гайде именно API шелла, только как программу. Из места — в карьер и...  
    Переменные окружения
    Это такие переменные, доступ к которым есть у всех приложений. По умолчанию создаются:
    "EDITOR" = "/bin/edit". Редактор по умолчанию. "HISTSIZE" = "10". Размер истории. "HOME" = "/home". Домашняя папка. "IFS" = " ". Символ для разделения. "MANPATH" = "/usr/man:.". Пути к папкам с файлами справочной системы. "PAGER" = "/bin/more". Программа типа more, осуществляющая функцию постраничного вывода. "PATH" = "/bin:/usr/bin:/home/bin:.". Основная переменная системы, указывает папки, где искать программы. "PS1" = "$PWD# ". Собственно, выражение, которое указывается в интерактивном режиме шелле перед полем команд. "PWD" = "/". Текущая рабочая директория, меняется, например, при вызове cd. "SHELL" = "/bin/sh". Шелл по умолчанию. "TMPDIR" = "/tmp". Временная директория.

    Таким образом, если изменить эти параметры и запустить использующие эти переменные программы, то можно изменять их поведение по собственным нуждам.
     
    set и unset
    Используются для этого две программы: set и unset. У первой следующий синтаксис: set [<название>[=<значение>]]. Если не указать никаких аргументов, просто перечислятся все переменные окружения. Если указать только название, то под определённым порядковым номером запишется название, если же ему присвоить значение, то возникнет пара <название>=<значение>. Главное — не ошибитесь при изменении важных переменных типа PATH.
    Чтобы снять значение переменной, пропишите unset <название переменной> [название второй переменной] [...].
     
    Алиасы
    Что такое алиасы? Это создание команды, которая будет вызывать другую. В общем, можно считать это ещё одним типом ссылки. Из стандартных алиасов имеются:
    dir = ls list = ls move = mv rename = mv copy = cp del = rm md = mkdir cls = clear less = more rs = redstone view = edit -r help = man ? = man cp = cp -i

    В данном перечне при написании команды слева выполняется команда справа. Это может быть удобно, например, чтобы не писать длинное "redstone", а только "rs".
     
    alias и unalias
    Но не это главное. Вы сами можете устанавливать алиасы!
    Первая команда alias имеет следующий синтаксис: alias [<Ваш вариант> [исполняемая команда]]. Если не указать аргументов в принципе, покажутся все алиасы, если указать только название — значение алиаса. Устанавливается только при указании значения.
    Чтобы снять алиас, достаточно команды unalias. unalias <название>.
     
    user*
    Приватность данных всё больше и больше волнует смертных человекоподобных существ пользователей ПК. OpenOS не остался исключением, и итог тому — предоставляемым самим модом функции управления пользователями. Тут всё просто. Есть в списке — гуляй, нет в списке — сорри, аксесс денайд.
    На основании уже сказанного мной текста, логично предположить, что детальное описание и использование лежит в глубине документации по API OpenComputers, и Вы будете правы. Единственная причина, почему я пишу об этом — для операций управления списком предназначены две простейшие утилиты useradd и userdel.
    Синтаксис useradd: useradd <игрок>. Ограничение состоит в том, что игрок этот должен быть в онлайне. И ограничение это накладывает сам мод, не система. К сожалению.
    Соответственно, логично, что userdel <игрок> удаляет игрока из списка пользователей.
    Если список пуст, то компьютер доступен всем. Если Вы сначала добавили друга, а затем захотели прописать себя — увы и ах. Так что прописывайте себя первым пользователем, если ещё собираетесь пользоваться компьютером. В любом случае, если Вы совершили олошность, то могут спасти ситуацию администратор или этот счастливый игрок.
     
    * и ?
    Обратили внимание на заголовок предыдущей записи? Тогда поговорим о масках. Нет, совсем не карнавальных.
    Представим следующую стркутуру:
    /|+ clones| || + clone001| + clone002| + clone003| + clone004| + clone101| + clone110| + colne001| + colne101| + colne|+ clonesEX|+ docsEX|+ docs | + doc_future-bak + doc*nature+smth + docFcreature_smth + doc2progsmth + doc.no + totallyNOTa.doc
    Задача попроще. Предположим, мы хотим перетащить в папку clonesEX все файлы из папки clones, при этом копировать папку нельзя. Что делать? Здесь нам на помощь придут эти самые маски. Конкретнее — *. Звёздочка в пути заменяет нуль и более символов. Соответственно, команда: mv clones/* clonesEX.
    Отмотаем время назад и допустим, что нужно перетащить только файлы с colne. Подумав, составляем команду: cp clones/colne* cloneEX. К слову, эта команда также захватит с собою colne. А что, если нам нужны именно файлы с номерами?.. Звёздочка тут не поможет, поэтому воспользуемся знаком вопроса (?). Он заменяет ровно один символ. В нашем случае достаточно такого: cp clones/colne??? clonesEX. Или даже такого: cp clones/colne?* clonesEX.
    По этому принципу перетащим все файлы, начинающиееся с doc, заканчивающиеся smth и имеющего название, отделённого двумя символами от doc и smth, из docs в docsEX. Подумайте, какую команду можно использовать.
    Ответ:

     
     
    ТАБ!
    Завершим рассказ о шелле потрясающей кавишей [TAB]. Суть её проста и огромна — если Вы ввели часть пути, то нажатие ТАБа дополнит до первого совпадения. Ещё одно нажатие — следующее совпадение и т. д.
     


    ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ СТАНДАРТНЫХ ПРОГРАММ?
    Удивительно, но мы, наконец-то, рассмотрели все стандартные утилиты и принципы работы (пишите в commentsStart, если это не так). Потому я закрываю цикл "OpenOS. От дуба до Мастера". В будущем будут другие записи, которые, вероятно, рассмотрят вопрос OpenOS в плане предоставляемых АПИ и скрытых открытых возможностей.
    Благодарю за прочтение.


    ←

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


    Сложность: средне 60%
    Скучность: средне 55%
    Дубовость: для продвинутых 50%
     


    ФАЙЛОВЫЕ СИСТЕМЫ, ЗАКЛЮЧЕНИЕ. УСТРОЙСТВА И МОНТИРОВАНИЕ
    Приступаем к самой сложной штуке в OpenOS — это монтирование файловых систем. Итак, начнём.  

    Логика работы
    Итак, начнём с того, что каждый накопитель — это устройство. У устройства есть свой адрес, который показывается при наведении мышкой. Устройство имеет определённую вместимость. Имеет количество свободной и занятой области. И, наконец, характеризуется наличием метки "Read-Only".


    Допустим, это устройство У имеет адрес Address, вместимость 2 МБ и занято 0.5 МБ.
    Другое устройство Д имеет адрес sserddA и такие же характеристики.
    В OpenOS выбирается одно основное устройство, которое становится корнем. У нас / = У. Оно имеет все стандартные файлы и папки. Но как перейти на устройство Д? Оказывается, в папке /mnt/ собраны ссылки на все устройства. Именами ссылок являются первые 3 буквы адреса устройства. Что интересно, даже если У — корень, ссылка на устройство всё равно будет в /mnt. Вот так: / Устройство У|│┅│+ mnt | |+ Add Устройство У |+ sse Устройство Д |┅
    Монтирование
    Но что, если если у нас таких устройств — 5, например? Помнить все 5 адресов, пусть даже трёх первых букв, писать длинные пути — не-у-доб-но. Согласитесь? Поэтому в ОС есть возможность ручного монтирования. То есть, проще говоря, можно создать ссылку на устройство в любом желаемом месте. Вот только ln здесь не поможет — это ведь не файл, а совершенно другой раздел. Для этих целей служит команда mount. У неё два варианта работы:
    mount -a <адрес> <место назначения> — создаёт ссылку на устройство, адрес которого начинается с <адрес>, в заданной директории <место назначения>. При этом указаннной папки не должно быть до этого на диске. После этого в выбранной директории будут все файлы с устройства. Для устройства Д — mount -a sse /devD/. mount <путь /mnt/адрес> <место назначения> — также создаёт ссылку на устройство в месте назначения, только вместо адреса используется путь типа /mnt/адрес. Для устройства Д это — mount /mnt/sse /devD/.

    Директория, которая является ссылкой на устройство, наызвается точкой монтирования.
     

    df
    Эта команда отобразит все подключённые в данный момент хранилища данных, укажет точку монтирования и состояние. Для нашего компьютера было бы показано следующее:
    Filesystem Used Available Use% Mounted onAddress 512k 2M 25% /Address 512k 2M 25% /mnt/addsserddA 512k 2M 25% /mnt/sse
    Как видите, если у файловой системы несколько точек монтирования, то будет показана информация о каждой из них.
     

    label
    Это у нас названия простые и запоминающиеся. В реальности вместо них были бы эти ужасные длинные непонятные адреса. И чтобы сделать их понятными, можно повесить метку. Что проще: "835f48a-5df9-eb6a-36cb-6ab452d8f16a" или "Programs"? Думаю, всё же второе.
    Чтобы поставить такую метку, воспользуемся командой label, у которой опять два варианта работы:
    label -a <метка или часть адреса> <метка> — устанавливает данному диску метку. label <точка монтирования> <метка> — устанавливает диску по данной точке монтирования метку.

    Кстати, если не указывать метку, то выведется информация о текущей.
    И ещё, установочная дискета имеет метку "openos", а жёсткий диск с ОС — "OpenOS" по умолчанию.

    Информация
    При монтировании первым способом можно вместо части адреса ввести метку.
     
     
     

    ПАЙПИНГ
    Файлы
    Простейший пример — перенаправление вывода echo в файл. Для этого используется >. Смотрите: echo "Hello all!" > hi.all. Содержимое hi.all очищается (или создаётся чистый файл, если его не было), и весь вывод идёт туда. Таким образом, в файле будет следующее: Hello all!
    Если же необходимо из файла содержимое вывести в команду, используется команда <. Вот только примеров такому мне найти не удалось.
     

    Между командами
    Другой простейший пример — команда cat. Если Вы помните, она печатала содержимое всё подряд, и если его больше высоты экрана, то просто обрезается. Так вот, чтобы не случалось такого, используется команда more и пайпинг.
    Сразу скажу, как это сделать. more | cat <файл>. Обратите внимание на |. Этот символ обозначает, что весь вывод из правой команды надо перенаправлять в левую.
    Скажу по секрету — тут можно было обойтись даже без пайпинга. more умеет сама открывать и читать файлы. Но есть нам нужен не файл, а, например, какой-нибудь df — вот тут и потребуется пайпинг.
     
    В любом случае, эта штука является невостребованной, так как она недоделана. Вероятно, в будущем этот недостаток будет устранён, а пока просто запомним три оператора.


    Список терминов: монтирование — процесс создания ссылки на устройство точка монтирования — название ссылки на устройство метка — пользовательское имя для накопителя



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


    ← →

  3. Fingercomp
    Продолжаем беседу об операционной системе Bolge OpenOS. В этой записи речь пойдёт про те самые оставшиеся утилиты, которые облегчат жизнь программисту.


    Сложность: средне 60%
    Скучность: высокая 80%
    Дубовость: для продвинутых 65%

    Операционная система OpenOS в первую очередь покрывает вопросы (относительно) удобного программирования для OpenComputers. Конечно, это не исключает сторонние редакторы типа Sublime Text или Notepad++, но иметь такие средства нужно и важно. Давайте же я расскажу о них. 


    УТИЛИТЫ ДЛЯ ПРОГРАММИРОВАНИЯ.
    Простой перечень утилит с пояснениями.  
    address
    Наипростейшая из наипростейших утилит, может соперничать даже с print("Hello, world!"). Просто выводит адрес компьютера. Интереса ради, пропишите view /bin/address.lua.
     
    components
    Ещё раз я расскажу об этой программке. Она выводит список компонентов, подключённых к системе. Можно задать фильтр, тогда выведутся только указанные компоненты. Если же указать ключ -l (о них в следующей части), то для каждого компонента будут указываться методы.
     
    dmesg
    Данная программа случает все события и выводит информацию о них на экран. Можно указать фильтры событий для просулшивания через пробел.
     
    flash
    Та самая программа, которая записывает код на EEPROM. Ключ -l выводит код о текущего EEPROM, -r записывает код в файл, а -q заставляет не задавать вопросов.
     
    hostname
    Данная программа бессмысленна без пакета network. Но, тем не менее, она может устанавливать и выводить текущее имя компьютера.
     
    lua
    Если запустить без аргумента или с ключом -i, то запустится интерактивный сеанс Lua-интерпретатора, где можно запускать программы. При этом все библиотеки автоматически переносятся в _G, так что дополнительно подключать их не требуется. Если же указать файл, то скрипт предпримет попытку запуститься и выдаст сообщение при обнаружении ошибки.
     
    primary
    Синтаксис: primary <компонент> [адрес]. Если аргумент [адрес] опущен, то выводится информация о первичном компоненте, иначе — предпринимается попытка сделать данное устройство первичным.
     
    rc
    Программа управления сервисами (о них — в следующих частях). Синтаксис: rc <сервис> [команда] [аргументы].
     
    redstone
    Предоставляет простой интерфейс управления редстоун-сигналами на первичной ред-карте/ред-блоке. По умолчанию синтаксис следующий: redstone <сторона> [значение]. Если [значение] не задано, выводится информация о текущем. Иначе — устанавливается.
    Для многожильных кабелей синтаксис следующий: redstone -b <сторона> <цвет> [значение]. Работа необязательного аргумента такая же.
    Для блоков, предоставляющих интерфейс беспроводной передачи ред-сигнала, команды следующие:
    redstone -w [сила]. Если [сила] задана, устанавливается значение на беспроводном передатчике. Иначе — выводится текущее значение силы. redstone -f [частота]. Устанавливает частоту, если задан аргумент, иначе — выводит текущую.

    sh
    Запускает сеанс командной строки, если не передано аргументов и io.stdin не перенаправлен. Иначе — читает команды из этого потока и выполняет их.
     
    umount
    Синтаксис: umount <точка монтирования>. Отмонтирует устройство по данной точке монтирования.

    Вот так. Следующая часть целиком и полностью посвящена шеллу, ему родимому. Это: переменные окружения, алиасы, ключи, аргументы, особенности работы шелла и прочее. Пока жду комментариев по этой части, пишите, если что-то непонятно.  



    ← →

  4. Fingercomp

    OpenOS. Потоки

    Автор: Fingercomp,

    Потоки — очень полезные штуки, позволяющие исполнять несколько кусков кода. Раньше для их использования приходилось скачивать отдельную библиотеку, работающую через костыли. Начиная с OpenOS 1.6.4, они есть в стандартной поставке ОС — в модуле thread. Давайте посмотрим, из чего она состоит — и в чём её преимущество перед любыми другим библиотеками.
     
    Начнём с версий. OpenOS 1.6.4 — версия, включённая в OpenComputers 1.7.0. Если не хотите возиться с обновлением системы вручную, требуется иметь версию выше или равную 1.7.0.
     
    Сразу обращаю внимание на самую важную вещь: потоки не могут исполняться одновременно. В один момент времени только один поток может работать.
     
    В чём тогда красота тредов?
     
    Они автономны, то есть:
    Начинают исполнение сразу же после создания. Передают исполнение в другие потоки в местах, указанных использователем, — при том или ином вызове computer.pullSignal (os.sleep, event.pull и т. д.). Автоматически продолжают своё исполнение без необходимости самостоятельно их стартовать. Потоки можно убить и приостановить.
    Они неблокирующие:
    Вызов computer.pullSignal не блокирует исполнение других потоков.
    Они отцепляемые:
    Процесс, в котором был создан поток, называется родительским. При завершении родительского процесса все потоки останавливаются. Поток может отсоединиться от родительского процесса и работать полностью автономно — например, как слушатели событий. Поток может сменить родителя на другого. Поток сам является процессом и потому может создавать дочерние потоки. Работающий поток не даёт завершиться своему родителю.
    Они независимы при обработке событий:
    Потоки не наследуют и не передают дочерним свой набор слушателей событий. Все слушатели событий и таймеры принадлежат только конкретному потоку. Как следствие, поток не может изменять их набор в другом. Слушатели и таймеры автоматически удаляются при завершении потока, даже если завершение вызвано ошибкой. Приостановленные потоки игнорирует события. Если несколько потоков вызвали event.pull на одно и то же событие, они оба его получат.
    Этот набор фич в таком объёме присутствует только в этой библиотеке, и ни одна другая и не даёт столько простоты в работе с ними.
     
    Пожалуй, приступим к использованию. Потоки создаются функцией thread.create: первым аргументом передаётся функция, дальше идут аргументы к ней.
    local thread = require("thread") local t = thread.create(function(a, b) print("В потоке получены аргументы:", a, b) end, 21, 42)
    Функция возвращает объект потока. Его же может получить сам поток вызовом thread.current() — однако если вызвана не в потоке, то возвращает nil. На всякий случай, основной процесс не является потоком.
     
    Объект потока позволяет чудить различные вещи с потоком.
     
    t:suspend() приостанавливает поток. Как уже сказано, такой поток не будет получать события и обрабатывать тики таймера. Забавно, что если приостановить поток, когда он ждёт события, то неизвестно, что он получит после его возобновления.
     
    t:resume() возобновляет работу ранее приостановленного потока. Так как созданные потоки сразу начинают работу, то обычно этот метод вызывать не придётся.
     
    t:kill() убивает поток, то есть завершает его, удаляя всех слушателей и таймеры. Возобновить работу потока после того, как он убит, нельзя.
     
    t:status() возвращает строку со статусом потока:
    "running" — поток работает или блокирован другим. Такой поток не даёт завершиться своему родителю. "suspended" — поток приостановлен. Его дочерние потоки также будут приостановлены. Когда родительский процесс завершается, такой поток автоматически убивается. "dead" — поток мёртв.  
    t:attach() позволяет сменить родителя у потока. Без аргумента поток будет присоединён к текущему процессу. Переданное как аргумент число позволяет указать, к кому присоединить: 0 — текущий процесс, 1 — родитель текущего и т. д.
     
    t:detach() отцепляет поток от родителя. Такой поток будет работать до его остановки или перезагрузки компьютера.
     
    t:join() останавливает процесс, в котором была вызвана это функция, до завершения потока t.
    local thread = require("thread") local t = thread.create(function() os.sleep(10) end) t:join() -- остановится на 10 секунд
    Можно передать первым аргументом этой функции число, которое будет служит таймаутом (в секундах). Тогда, если не успеет завершиться поток за это время, join завершится досрочно.
     
    t:join ждёт только одного потока. Для групп потоков есть функции thread.waitForAny и thread.waitForAll — обратите внимание, что это функции библиотеки, а не методы объекта потока.
     
    Обе функции первым аргументом требуют таблицу с потоками, а вторым опционально можно задать таймаут.
     
    thread.waitForAll ждёт, пока завершатся все потоки из списка.
    local thread = require("thread") local t1 = thread.create(function() os.sleep(10) end) local t2 = thread.create(function() os.sleep(15) end) thread.waitForAll({t1, t2}) print("Это сообщение будет написано через 15 секунд")   thread.waitForAny ждёт, пока завершится хотя бы один поток из списка.
    local thread = require("thread") local t1 = thread.create(function() os.sleep(10) end) local t2 = thread.create(function() os.sleep(15) end) thread.waitForAny({t1, t2}) print("Это сообщение будет написано через 10 секунд")
    Что будет, если поток бросает ошибку? При ошибке в потоке она не будет проброшена в родительский процесс. Как и со слушателями, она будет записана в файл /tmp/event.log, но родитель не сможет узнать причину ошибки — и, вообще, успешно ли завершился поток.
    local thread = require("thread") local t = thread.create(function() os.sleep(3) error("test") end) print(t:status()) --> running t:join() print(t:status()) --> dead
    Кроме того, событие жёстокого прерывания (Ctrl+Alt+C) не передаётся всем процессам — только одному; причём неизвестно, какому именно: родителю или одному из его потоков. Если вы используете потоки, первым делом сделайте один, который будет ждать события interrupted и подчищать ресурсы.
    local thread = require("thread") local cleanupThread = thread.create(function() event.pull("interrupted") print("Принял ^C, чищу всякие ресурсы") end) local mainThread = thread.create(function() while true do local input = io.read() if input == "exit" then break end end end) thread.waitForAny({cleanupThread, mainThread}) os.exit(0) Обратите внимание, что в конце программы стоит os.exit. Я уже упоминал не раз, что родительский процесс, достигнув конца программы, не завершится до тех пор, пока работает хотя бы один из его дочерних потоков. Вызов os.exit() позволяет выйти из программы, закрыв все дочерние потоки. Что, безусловно, достаточно удобно.

    Есть ещё один момент. Допустим, данная программа запускается в роботе:
    local robot = require("robot") local thread = require("thread") local moveThread = thread.create(function() while true do robot.forward() end end) local inputThread = thread.create(function() while true do local input = io.read() if input == "exit" then break end end end) thread.waitForAny({inputThread, moveThread}) os.exit(0) Если вы запустите эту программу, то должны заметить, что вы ничего не сможете написать в роботе, хотя работает io.read. Дело в том, что функция robot.forward вызывает метод компонента, который блокирует исполнение компьютера. Пока робот двигается, на компьютере не может выполняться ни одна команда.
     
    Чтобы хоть что-то можно было вставить в строку, то поставьте после robot.forward какой-нибудь os.sleep(0) — он позволит соседнему потоку принять и обработать события. Тем не менее, строка ввода всё равно будет работать с тормозами.
     
    В подобном случае задумайтесь над тем, чтобы использовать вместо строки ввода иное средство коммуникации: редстоун, сеть, интернет-сокет.
     
    Несмотря на всё, библиотека действительно облегчает работу с потоками в OpenOS. Кроме того, очень удобно поместить все слушатели событий в один поток, чтобы они все автоматически были удалены после убийства потока.
    local event = require("event") thread = require("thread") local mainThread = thread.create(function() event.listen("key_down", function(evt, addr, key, code, user) print("A key has been pressed!") end) while true do print("do something") os.sleep(0.5) end end) -- событие interrupted не ловится обработчиками local intThread = thread.create(function() event.pull("interrupted") end) thread.waitForAny({mainThread, intThread}) os.exit(0) Не нужно функции сохранять в переменные и помнить, что нужно ставить event.ignore в конце программы; не требуется ребутать компьютер, если программа завершилась с ошибкой, а до отключения слушателей дело не дошло.
     
    В общем, красота.
  5. Fingercomp
    Продолжаю рассказывать про Computronics и, в частности, про офигенную звуковую карточку из этого мода. На очереди модуляция: частотная и амплитудная. Помимо этого восполняю долг по основам.
     
    Юзать будем мою прогу synth, которую я недавно зарелизил. Она здесь невероятно поможет.
     
    Звуковая волна
    Вы же знаете, как выглядит звуковая волна?
     




     

    Вот, например, синусоида. Как видно, здесь есть некоторый фрагмент, который повторяется несколько раз. Частота показывает, сколько раз в секунду этот фрагмент повторяется, и измеряется в герцах (Гц или Hz). Чем выше частота, тем больше волна "сжата", скажем так, с боков. Вот как выглядят три синусоиды с разными частотами: 110 Гц, 220 Гц, 440 Гц - на одинаковом масштабе.
     




     

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




     

    При максимальной громкости у простой синусоиды пиковые значения будут в точках +1 и -1. Они плавно сменяются. Прикольно, да.
     
    Синусоиды - это офигенные штуки, но на них клин светом не сошёлся. Из основных типов волн, помимо синусоид, есть меандр, треугольная волна и пилообразная. Они в таком же порядке изображены на рисунках ниже.
     





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


     

    На самом деле, их можно представить в виде набора бесконечного числа синусоид, о чём когда-то поведал Фурье, но мы с этим заморачиваться не будем: раскладывать на синусоиды в звуковой карте не принято. Поведали об этом для красного словца - и то хорошо.
     
    Теперь, когда рассказал про основы, можно переходить к более весёлым и сложным вещам. То бишь к модуляции.
     
    Модуляция
    Модуляция - это изменение одного сигнала (несущего) другим (модулятором). Изменять можно по-разному - мы будем говорить об амплитудной модуляции и частотной модуляции.
    С модуляцией у нас появляется уникальнейший шанс получить офигенные и красивые звуки, поэтому не будем ждать и сразу перепрыгнем к мясу.
     
    Амплитудная модуляция
    Как я сказал, для модуляции нужны два сигнала: несущий и сам модулятор. Поэтому здесь и далее я привожу на рисунках сразу три графика: несущий сигнал, модулирующий сигнал и результат модуляции.
    Например, выставим две синусоиды с частотой 440 Гц.
     




     

    Итак, амплитудная модуляция - это умножение одного сигнала на другой.
     


    A(t) = C(t) × M(t),


     

    где t - время, C - функция, возвращающая значение несущей волны на моменте времени t, M - то же, но для модулятора.
    Однако не всё так просто. Перед умножением к значениям с модулятора прибавляется единица. Получается, что самая верхняя точка будет на +2, а самая нижняя - на 0. Иными словами, волна перенесена вверх.
     
    На низких частотах - до 20-30 Гц, откуда начинается граница слышимого человеком звука, - графики будут выглядеть как-то так, медленно увеличивая амплитуду от 0 до 4 и обратно.
     




     

    И звучать оно будет как увеличение и уменьшение громкости (количество таких увеличений и уменьшений равно частоте модулятора).
     
    Однако когда частота модулятора становится больше, наблюдаем вот такую картину (частота модулятора равна здесь 330 Гц).
     




     

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


    f1 = |c - m|,



    f2 = c + m,


     

    где c - частота несущей волны, а m - частота модулятора. Возникающие звуковые волны около этих частот вдвое тише, чем несущая.
     
    В звуковой карте можно поставить амплитудный модулятор следующим образом: sound.setAM(carrierChan: number, modulatorChan: number).
     
    Амплитудная модуляция - забавная вещь, и в то же время тут очень трудно подобрать что-то интересное и красивое. Поэтому переходим к частотной модуляции - там веселья дофига.
     
    Частотная модуляция
    В частотной модуляции модулятор изменяет частоту несущей волны. Как ни странно.
    Почему частотная модуляция уделывает амплитудную? Здесь может быть гораздо больше боковых частот. И потому звучать оно может гораздо круче.
     
    При когда значение на модуляторе увеличивается, повышается и частота на несущей волне.
     
    Звуковая карта поддерживает индекс модуляции. Он задаёт максимальное изменение частоты несущей волны. При индексе, равном 100, частота несущей волны может меняться на 100 Гц вверх и на 100 Гц вниз. Если индекс равен 1000, то частота меняться может на 1000 Гц вверх и на 1000 Гц вниз. Ну и так далее.
    Иными словами, индекс задаёт силу модуляции.
     
    Если частота модулятора будет очень низкой (например, 4 Гц), то получим что-то вроде сирены.
     





    c = 440 Гц; m = 4 Гц; i = 200


     

    С повышением частоты получим вибрирующий звук. И потом услышим дополнительные частоты.
     





    c = 220 Гц; m = 880 Гц; i = 660


     

    Как видно, получившаяся волна получилась довольно сложной.
     
    Установить модулятор в звуковой карте можно с помощью функции sound.setFM(carrierChan: number, modulatorChan: number, index: number).
     
    И не забывайте про ADSR-огибающую: из однообразного тона можно получить довольно интересный звук. Как работает эта штука, я рассказывал.
     

     
    На этом всё. Из всех фич остался неразобранным лишь шум LFSR, но там штука очень и очень странная и непонятная.
     
    Наверняка всё равно остались некоторые вопросы по поводу модуляции. Поэтому за дополнительной информацией я предлагаю обратиться к другим сайтам. Вот несколько очень полезных ссылочек, где есть примеры звука и детальное описание:
    FM Synthesis - The Synthesizer Academy Frequency modulation synthesis - Wikipedia FM Synthesis - Music and Computers Modulation synthesis - Wikibooks (здесь рассказывается про амплитудную модуляцию в том числе).

    Ну и используйте прогу synth, чтобы удобно было изучать звуковую карту.
  6. Fingercomp
    Перед тем, как я начну, хочу сразу обратиться к забугорным ребятам, читающим эту запись.
     
    Hey! If you are reading this, please tell Vexatos to document the sound card. The in-game manual page is a meaningless piece of text that explains nothing.
    Documentation is written to help others to get an idea of how something works. The sound card is a complex thing that definitely needs a how-to guide to be used in programs.
    So if he wants the sound card to be used in programs, he should write the proper documentation with the detailed description of each concept, feature, and component method.
    The following is the result of efforts put to understand how the sound card works. It took me several months until I realized how to make a simple beep. How am I supposed to create more complex waves? >_>
     
    Ну да ладно.
     

    Хей! Разбирался я недавно, как работает звуковая карта из CX, и поэтому хочу предоставить результаты своих трудов.
    Как и написано сверху, доков нет, автор мода бездействует, везде уныние и отчаяние, поэтому пришлось действовать по-хардкорному. То есть чтением исходников и научнейшим тыком.
     
    Итак, есть компьютер со звуковой картой. Нужен звук. Звучит просто, м?
     
     
    Звуковая карта даёт нам замечательные функции вроде установки ADSR-огибающей, типа волны, шума простого или из LFSR, амплитудной и частотной модуляции. Но мы тут решили заняться простым звуком, поэтому всякие LFSR, AM, FM безжалостно выкидываем. Получаем такой план:
    Открыть канал. Поставить тип волны. Задать частоту волны. Установить громкость. Обработать.  
    1. Открыть канал
    Э, извините, а что за каналы?
    ...
    В звуковой карте звук генерируется с помощью инструкций, которые выполняются друг за другом. Почти все работают с определённым каналом. Если бы канал был один, мы бы смогли играть в один момент времени только одну, условно, ноту. Чтобы параллельно шло сразу несколько звуковых волн, нужно использовать несколько каналов. На каждом можно задать свои тип и частоту волны, громкость, ADSR-огибающую. По умолчанию таких каналов в звуковой карте 8 штук.
     
    С каналами всё довольно просто: открытый канал генерирует звук, закрытый канал не генерирует звук (правда, нужно будет здесь кое-что поправить, когда будет изучать ADSR).
     
    Открыть канал можно с помощью функции sound.open(channel: number). Закрыть: sound.close(channel: number).
     
    2. Поставить тип волны
    Всего типов звуковая карта поддерживает пять: шум (noise), меандр (square), синусоида (sine), треугольная (triangle) и пилообразная (sawtooth).
     
     

    Waveforms ru [CC BY-SA 3.0 (http://creativecommons.org/licenses/by-sa/3.0) или GFDL (http://www.gnu.org/copyleft/fdl.html)], автор Omegatron (original work)
    Kirill Borisenko (Russian translation; see File:Waveforms for Cyrillic Segment.png)
    Incnis Mrsi (ultimate work), с Викисклада
    Очевидно, что разные типы волн звучат по-разному.
     
    Установить тип волны можно с помощью функции sound.setWave(channel: number, type: number). Видно, что тип волны должен быть числом. Соответствующее типу волны число можно получить с помощью таблицы sound.modes. Например, sound.modes.sine или sound.modes.noise.
     
    3. Задать частоту волны
    Чем больше частота, тем выше звук. Частота 440 Hz соответствует ноте ля в первой октаве. Другие частоты можно найти по табличке на Википедии.
     
    Используем функцию sound.setFrequency(channel: number, freq: number).
     
    4. Установить громкость
    Громкость может быть в пределах от 0 до 1 включительно. Половина максимальной громкости - 0.5. И так далее.
     
    Функция: sound.setVolume(channel: number, volume: number).
     
    5. Обработать
    Чтобы обработать все инструкции, нужно вызвать sound.process(). Но если вы просто возьмёте и вызовете функцию, то ничего не услышите. Дело в том, что, достигнув конца инструкций, звуковая карта прекращает генерировать звук.
     
    Поэтому нужно выставить некоторую задержку в конце всех других инструкций, чтобы звуковая карта подождала перед прекращением воспроизведения звука. Для этого служит sound.delay(delay: number). Задержка указывается в миллисекундах. Например, sound.delay(2500). При этом эта функция тоже является инструкцией, поэтому её можно выставить несколько раз. Однако если задержка превышает 5000 (5 секунд), то звуковая карта выдаст ошибку.
     
     
    Проиграв несколько типов волн, мы всё равно останемся неудовлетворёнными. Ну где это видано, что звук мгновенно нарастает и затухает?
    Чтобы как-то это контроллировать, мы воспользуемся ADSR-огибающей. На Википедии довольно хорошо написано, в чём смысл этого.
     
    Скопируем сюда оттуда пикчу:

    И вкратце распишем суть.
    Если вы хоть когда-либо слышали музыкальные инструменты, вы могли заметить, что громкость звука со временем меняется. У гитары громкость мгновенно нарастает и постепенно затухает, а у флейты нарастает не сразу, например.
    Чтобы очень-очень грубо моделировать эти инструменты, мы используем ADSR.
    Attack - это время нарастания громкости звука до максимальной (последняя устанавливается через sound.volume).
    Decay - время затухания сигнала сразу после достижения максимальной отметки до следующего параметра.
    Sustain - отметка громкости, к которой стремится Decay. Значение 1 - это максимальная громкость звука на канале (установленная с помощью sound.setVolume), 0 - отсутствие звука вовсе.
    При достижении отметки Sustain звук остаётся на этом уровне до "отпускания клавиши" (т.е. закрытия канала).
    Release - время затухания сигнала после закрытия канала, от отметки Sustain до нуля.
     
    Время везде в миллисекундах.
     
    Попробуем? Вызываем функцию sound.setADSR(channel: number, attack: number, decay: number, sustain: number, release: number) до пятого шага. Например sound.setADSR(1, 1000, 500, 0.33, 1000).
    И замечаем, что громкость меняется со временем. Yay!
     
     
    На этом счастливом моменте повествование обрывается. Итоговый код, который можно запустить и послушать примитивный бип:
    local sound = require("component").sound sound.close(1) sound.close(2) sound.open(1) sound.setWave(1, sound.modes.sine) sound.setFrequency(1, 440) sound.setVolume(1, 1) sound.setADSR(1, 1000, 500, 0.33, 1000) sound.delay(1000) sound.open(2) sound.setWave(2, sound.modes.noise) sound.setFrequency(2, 440) sound.setVolume(2, 0.6) sound.setADSR(2, 1, 250, 0, 1) sound.delay(1500) sound.process()
    К остальному, надеюсь, я ещё вернусь в другой записи. Сначала нужно самому понять, как оно работает в версии для CX.
    Поэтому наслаждаться пока приходится только бибикалкой.
  7. Fingercomp
    В звуковой карточке есть дохрена функционала - поэтому она и крутая. В этой части попытаюсь объяснить достаточно сложные штуки, которые используют большие дяди.
    Надеюсь, что вы прочитали и поняли две предыдущие части цикла - это будет довольно важно для последующего повествования.
    [Раньше тут был полноценный пост с эмбедом, но после переезда оно всё, соответственно, сломалось. Текст доступен здесь.]
  8. Fingercomp

    Автозапуск программ

    Автор: Fingercomp,

    Если до версии 1.6 все использовали файл /autorun.lua и были довольны, то теперь ситуация несколько изменилась. Поэтому я опишу все варианты автозапуска программ в этой небольшой заметке.
     
    С версии OpenOS 1.6 файл autorun.lua больше не запускается на rootfs (то есть на файловой системе работающей операционной системы). Вот все пять способов, которые можно использовать для автозапуска программ.
    Модифицировать /init.lua.
    Это самый плохой и ужасный вариант из всех. Во-первых, программа будет запускаться до запуска шелла и инициализации библиотек, поэтому возможны краши системы. Во-вторых, если сделать ошибку в файле, то придётся переустанавливать этот файл, что не очень удобно.
    Добавить скрипт в /boot.
    Это не такой плохой вариант, но здесь также возможны ошибки при использовании стандартных библиотек, так как бутскрипты запускаются не в самом конце загрузки.
    Модифицировать /etc/profile.
    Это файл, каждая строка которого последовательно исполнаяется при запуске программ. Проблема в том, что при переустановке системы этот файл будет перезаписываться. Поэтому не вариант.
    Модифицировать /home/.shrc.
    Это самый оптимальный вариант. Но программа будет запускаться при каждом запуске шелла. Если прописать exit в шелле, то программа запустится ещё раз. Если для графических всяких программ это самый лучший вариант, то для одноразовых демонов, которые регистрируют листнеры на ивенты и выходят, вариант не очень хороший, так как тогда листнеры зарегистрируются дважды.
    Использовать систему rc.
    Подробно о ней рассказывал @LeshaInc: http://computercraft.ru/topic/1679-rc-chto-za-zver-takoi/
    Это система, которая позволяет писать своих "демонов" — программ, исполняемых в фоне — и контролировать их из шелла с помощью команд. Графические утилиты так запускать проблематично, потому что возможны всякие артефакты отображения.

    Поэтому используйте варианты 4 или 5 в зависимости от программы, которую требуется запустить.
  9. Fingercomp

    Автокрафт OpenComputers

    Автор: Fingercomp,

    Первая публичная реализация автокрафта на OpenComputers.
    Исполнительным элементом является робот, командующим же — компьютер. Хранилищем предметов здесь выступает МЭ-сеть, с интерфейсом в роли передатчика предметов в обе стороны.
    Для начала использования автокрафта Вам потребуется:

    Компьютер.
    Это главная часть системы, хранящая базу данных рецептов и экспортирующая предметы из дерева крафта в нужном порядке.
    Требования:
    Графическая карта второго уровня. Беспроводная сетевая карта. Процессор второго уровня и выше. Планки памяти уровня 2 и выше (зависит от размеров базы данных). Жёсткий диск уровня 1 и выше (зависит от размера базы данных). Интернет-карта (для скачивания программы). EEPROM. OpenOS Робот.
    Это исполняющая часть системы. По сигналу с модема "craft" она крафтит предметы и складирует полученное в МЭ.
    Требования:
    Апгрейд крафта. Контроллер инвентаря. Инвентарь. Клавиатура. Экран Т1. Дисковод. Интернет-карта (для скачивания программы). Беспроводная сетевая карта. Процессор уровня Т2 и выше. Планки памяти уровня Т2 и выше (возможная комбинация: Т2 и Т1.5). EEPROM. OpenOS. Жёсткий диск первого уровня. МЭ-сеть.

    Это хранящая часть системы, из которой достаются айтемы и в которую кладутся результаты крафтов.
    Требования:
    ME Drive и ячейки. Терминал для доступа к сети (может быть исключён). Интерфейс. После крафта всех необходимых вещей можно приступать к установке. Поставьте робота лицом в интерфейс. Убедитесь, что интерфейс готов к работе. Теперь соберите компьютер. Установите на робота и компьютер OpenOS. Скачайте программы, используя команды ниже, для робота и компьютера соответственно:
    Компьютер:
    pastebin get pXunJUE2 /usr/bin/craft.lua
    pastebin get ixwtEUr6 /usr/bin/recipes.lua
    pastebin get V2Zrnp6F /usr/share/db
    Робот:
    pastebin get tiwidCYt /autorun.lua
    pastebin get S1J5Y7mb /scan.lua
    Теперь запишите адреса сетевых карт на компьютере и роботе (components modem). Откройте файл /usr/bin/craft.lua на компьютере.
    В строке ROBOT замените значение на адрес сетевой карты робота.
    В строке DIR замените значение на сторону экспорта (сторона света, где находится робот относительно интерфейса). "north", "south", "east", "west", "up", "down".
    В строке TECH_SLOTS замените значение на количество слотов внизу робота (инструмент, дискета, контейнеры).

    После этого откройте файл /scan.lua на роботе и замените значение переменной COMP на адрес сетевой карты компьютера.


    Если всё сделано правильно, можно запустить файл /autorun на роботе и recipes на компьютере. Интерфейс у данных программ понятен без моих комментариев. Программа recipes предназначена для управления базой данных: удаление, изменение, добавление, просмотр рецептов. Программа craft на компьютере предназначена для самого процесса крафта. Напоследок, для сканирования рецептов нажмите 7 в recipes, выложите рецепт в роботе и в выделенный слот положите результат крафта. Затем запустите программу scan на роботе и выполните инструкции на компьютере.

    Скриншоты.
     
    Все вопросы, замеченные баги оставляйте в комментариях.
  10. Fingercomp
    Многие игроки здесь видели или хотя бы слышали про огромный дронодом, который построил @Asior в былые времена на сервере RoboCraft. С тем чтобы прояснить происхождение этой хаты и оставить о ней заметку в этом клубе, специально для «Новостей подполья» @Fingercomp обратился к создателю постройки и попросил рассказать про неё. Редакция представляет обработанную версию истории.
     
    История начинается в начале мая 2016 года, когда запустился сервер RoboCraft, на который сразу же хлынули толпы игроков, хотевшие «поскорее стать топовыми игроками, обладателями гор ресурсов и, конечно же, новых идей и программ». Туда попал и герой нашего рассказа. Развитие было довольно сложным. Поначалу он «хотел, как обычно, отстроить бункер и спокойно, потихоньку наращивать силы», но этому воспрепятствовал случай: система автоматического расселения игроков закинула Asior невесть куда — в середину заражённого биома. Очевидно, что герой этому не обрадовался. Ему потому пришлось бегать в поисках нового места.
     
     
    Конечно, Asior таки организовал себе временное убежище и начал стремительное развитие в игре. Но в чате игроки часто оставляли ссылочки на скриншоты своих невероятно красивых палат с невероятно крутых ракурсов.
     
     
    Он перерыл огромное число чертежей домов, замков, статуй — и решил построить дрона. Дрона из OpenComputers. Ведь сервер специально разрабатывался для этого мода. Asior зашёл в сингл и долго, упорно воздвигал новые варианты постройки и безжалостно крушил старые. Наконец, он определился с тем, как именно должно будет выглядеть его будущее жилище. Оставалось лишь воспроизвести это всё на сервере. Но здесь и возникла основная проблема: как добыть такое огромное количество ресурсов для строительства? Разрешена она была путём не самым чистым:
     
     
    Впрочем, и того, что он раздобыл, сполна хватило на постройку основного корпуса дрона. Это потребовало огромного числа строительных лесов и невероятных акробатических способностей и дополнительно осложнялось тем фактом, что полученные вечные блоки не перемещались из хотбара. Но стиснув зубы и получая подкормку от щедрых игроков Asior таки построил дрона.
     

     
     
    Потому пришлось придумать, как расширить жилище. Некоторые предлагали соорудить какое-нибудь здание, к которому был бы «привязан» дрон, но, увы, это не вписывалось в местность.
     
     
    Далее настала очередь внутренней отделки: ставились перегородки, размещалось оборудование. А монументальное сооружение, памятник роботу и дрону, стал пользовался большой популярностью, чему создатель не противился: «я был не против, чтобы все желающие посмотрели, как я живу, уточнили какие-то вопросы или помогли чем-нибудь».
     
    С тех пор сервер RoboCraft давно закрыт, но память о роботе и дроне жива до сих пор. Редакция присоединяется к пожеланию героя остроить то, что поражало бы воображение и отпечаталось в приятных воспоминаниях десятков игроков.
     
    И мы всё так же мы призываем вас оформить подписку на «Новости подполья». Годноты здесь много было, есть — а то ли ещё будет.
  11. Fingercomp
    Среди всех компонентов в OC у интернет-платы самый ужасный API. Неудивительно, что правильно использовать его умеют немногие. Даже за Vexatos мне приходилось чинить tape.lua — программку для записи кассет. Плюс в ирке нередко спрашивают, как отправить HTTP-запрос на сервер. Значит, пришло время написать, как же всё-таки использовать интернет-плату.
     
    Гайд строится на следующих предположениях (сорри за педантизм):
    Вы умеете прогать на Lua, в том числе знаете о двух основных способах возвращать ошибку. Вы писали уже программы для OpenComputers, которые использовали API этого мода или OpenOS, особенно либу event. Вы как-то использовали (или пытались использовать) интернет-карточку в программах. Секции 1, 3: вы понимаете основные принципы HTTP. Секции 2, 4: вы понимаете, как пользоваться TCP-сокетами и зачем (не обязательно в Lua). Секция 4: вас не смущает setmetatable и вы понимаете, как делать ООП на прототипах. Секции 2, 4: у вас OC 1.6.0 или выше. Секции 1, 3, 5: у вас OC 1.7.5 или выше. Текущая версия мода — 1.7.5, а в новой ничего не изменилось.  
    У инет-карты есть две разных фичи — HTTP-запросы и TCP-сокеты. Кратко пробежимся по API и затем разберём детальнее применение. Рассматривать я буду API компонента: часто используют require("internet") — это не компонент, а обёртка.
     
    1. Отправка HTTP-запросов: component.internet.request
    У этого метода 4 параметра:
    URL, на который надо послать запрос. На всякий случай, URL начинается со схемы (http: или https:), после которого идёт адрес хоста (например: //localhost, //127.0.0.1, //[::1], //google.com:443), за которым следует путь (/my-file.html). Пример: https://computercraft.ru/blogs/entry/666-profiliruem-programmy-pod-oc/. Данные запроса. Оно же тело запроса. Если мы отправляем GET/HEAD-запрос, то этот аргумент надо установить в nil. Хедеры, которыми запрос сопровождать. Можно поставить nil, тогда там по минимуму дефолтные подтянутся. Иначе передавать надо таблицу. Её ключи — это названия хедеров. Например, {["Content-Type"] = "application/json"}. Метод запроса. Если же этот аргумент не передавать, то возьмётся по дефолту GET или POST: это зависит от того, пуст ли аргумент 2 или нет.
    Если возникла ошибка, метод вернёт nil и сообщение об ошибке.
    Если же всё нормально, то метод вернёт handle — табличку с функциями. Вот что это за функции:
    handle.finishConnect() — проверяет, подключены ли мы к серверу. Если да, то вернёт true. Если к серверу ещё не подключены, то вернёт false. Если же возникла ошибка (например, 404 вернул сервер или закрыл соединение), то вернёт nil и сообщение об ошибке. Например, nil, "connection lost". В доках написано, что функция ошибку пробрасывает. На самом деле нет: она вообще не бросает исключения. handle.response() — возвращает мета-данные ответа с сервера. Если соединение ещё не установлено, вернёт nil. Если возникла ошибка, вернёт nil и сообщение об ошибке. Например, nil, "connection lost". В противном случае возвращает 3 значения: Код ответа (например, 200). Статус (например, "OK"). Таблицу с хедерами, которые отправил сервер. Выглядит примерно так: {["Content-Type"] = {"application/json", n = 1}, ["X-My-Header"] = {"value 1", "value 2", n = 2}}. Выпишу отдельно, что значения таблицы — это не строки, а ещё одни таблицы. handle.read([n: number]) — читает n байт (если n не задано, то сколько сможет). Если компьютер ещё не успел получить данные, то отдаст "". Если возникла ошибка, то выдаст nil и сообщение об ошибке. Например, nil, "connection lost". Если сервер закрыл соединение, то вернёт nil. В противном случае отдаст строку с частью ответа. handle.close() — закрывает соединение.  
    2. TCP-сокеты: component.internet.connect
    У метода есть 2 параметра:
    Адрес хоста. Например, 127.0.0.1. Здесь также можно указать порт: google.com:80. Порт. Если в первом аргументе порта нет, то второй параметр обязателен.  
    Если возникла ошибка, он также вернёт nil и сообщение. Иначе возвращает handle — табличку с функциями. Вот такими:
    handle.finishConnect() — то же, что и выше. handle.read([n: number]) — то же, что и выше. handle.write(data: string) — отправляет data по сокету на сервер. Возвращает число переданных байт. Если соединение не установлено, это число равно 0. handle.close() — то же, что и выше. handle.id() — возвращает id сокета.  
    3. Как правильно отправить HTTP-запрос на сервер и получить ответ
    Чтобы было интереснее, реальная задача: написать аналог pastebin, только вместо пастбина использовать https://clbin.com/. Особенности:
    Для взаимодействия с сайтом нужно отправлять HTTP-запросы: GET и POST. Это всё OC умеет. Чтобы скачать, достаточно простого GET по ссылке. Это можно сделать даже через wget. А вот чтобы отправить файл, надо использовать MIME-тип multipart/form-data. OC не умеет из коробки такие формы отправлять. Мы напишем минимальную реализацию, которая бы нас устроила. Не забываем, что этот MIME-тип нужно установить в хедер. При этом мы хотим красиво обработать все ошибки и не допустить ошибок сами. Таким образом, использовать будем практически все фичи.
     
    3.1. multipart/form-data
    Порядок особенностей нам не важен, поэтому начинаем с самого скучного. Сделаем функцию, которая принимает данные и обрамляет их согласно формату multipart/form-data.
    local function generateBorder(str) local longestOccurence = nil for match in str:gmatch("%-*cldata") do if not longestOccurence or #match > #longestOccurence then longestOccurence = match end end return longestOccurence and ("-" .. longestOccurence) or "cldata" end local function asFormData(str, fieldName) local border = generateBorder(str) local contentType = "multipart/form-data; boundary=" .. border return ([[ --%s Content-Disposition: form-data; name="%s" %s --%s--]]):format( border, fieldName, str, border ), contentType end Так как это не туториал по интернет-стандартам, вдаваться в детали реализации не буду.
    С помощью asFormData можно содержимое файла превратить в тело HTTP-запроса. Мы будем вызывать asFormData(str, "clbin"), ибо этого требует сайт.
    Кроме того, эта функция нам передаст значение хедера Content-Type. Он нам понадобится.
     
    3.2. Взаимодействие с сайтом
    Напишем теперь функцию — обёртку над component.internet.request.
    local function request(url, body, headers, timeout) local handle, err = inet.request(url, body, headers) -- ① if not handle then return nil, ("request failed: %s"):format(err or "unknown error") end local start = comp.uptime() -- ② while true do local status, err = handle.finishConnect() -- ③ if status then -- ④ break end if status == nil then -- ⑤ return nil, ("request failed: %s"):format(err or "unknown error") end if comp.uptime() >= start + timeout then -- ⑥ handle.close() return nil, "request failed: connection timed out" end os.sleep(0.05) -- ⑦ end return handle -- ⑧ end Эту функцию можно прямо брать и копипастить в свои программы. Что она делает:
    ① — отправляем запрос. Сразу обрабатываем ошибку. ② — запрос доходит до сервера не мгновенно. Нужно подождать. Чтобы не зависнуть слишком долго, мы засекаем время начала. ③ — вызываем finishConnect, чтобы узнать статус подключения. ④ — finishConnect вернул true. Значит, соединение установлено. Уходим из цикла. ⑤ — finishConnect вернул nil. Мы специально проверяем через status == nil, потому что не нужно путать его с false. nil — это ошибка. Поэтому оформляем его как ошибку. ⑥ — проверяем, висим ли в цикле мы слишком долго. Если да, то тоже возвращаем ошибку. Не забываем закрыть за собой соединение. ⑦ — нам не нужен бизи-луп. Спим. ⑧ — мы не читаем сразу всё в память, чтобы экономить память. Вместо этого отдаём наружу handle.  
    Частая ошибка — отсутствие элементов ②–⑦. Они нужны. Если до установки соединения мы вызовем handle.read(), то получим nil. Многие программы в этом случае сразу отчаются получить ответ и вернут ошибку. А надо было просто подождать.
     
    3.3. Отправка файла
    Функция для отправки файла должна сначала прочесть его содержимое, затем сделать запрос и прочесть ответ. В ответе будет находиться URL файла.
    local function sendFile(path) local f, err = io.open(path, "r") -- ① if not f then return nil, ("could not open file for reading: %s"):format(err or "unknown error") end local contents = f:read("*a") -- ② f:close() local data, contentType = asFormData(contents, "clbin") -- ③ local headers = {["Content-Type"] = contentType} local handle, err = request("https://clbin.com", data, headers, 10) -- ④ if not handle then return nil, err end local url = {} -- ⑤ local read = 0 local _, _, responseHeaders = handle.response() -- ⑥ local length for k, v in pairs(responseHeaders) do -- ⑦ if k:lower() == "content-length" then length = tonumber(v) end end while not length or read < length do -- ⑧ local chunk, err = handle.read() if not chunk then if length then -- ⑨ return nil, ("error occured while reading response: %s"):format(err or "unknown error") -- ⑩ end break -- ⑩ end read = read + #chunk -- ⑪ if length and read > length then chunk = chunk:sub(1, length - read - 1) -- ⑫ end table.insert(url, chunk) end handle.close() -- ⑬ return table.concat(url) -- ⑭ end ① — открываем файл для чтения. Обрабатываем ошибки. ② — считываем всё из файла. Не забываем закрыть его за собой. ③ — вызываем заранее написанную функцию asFormData. Мы получаем тело запроса и значение хедера Content-Type. Создаём таблицу хедеров. ④ — отправляем наш запрос. Обрабатываем ошибки. ⑤ — handle.read может не сразу вернуть весь ответ, а кусочками. Чтобы не забивать память кучей строк, кусочки мы будем класть в таблицу (получится что-то вроде {"htt", "p://", "clbi", "n.co", "m/ab", "cdef"}). Также мы храним число прочитанных байт. ⑥ — мы хотим сверять число прочитанных байт с ожидаемым размером ответа. Для этого нам потребуется получить хедеры, отправленными сервером. Вызываем handle.response. ⑦ — размер ответа обычно пишется в заголовок Content-Length. Однако сервер может поиграться с регистром. Например, писать content-length или CONTENT-LENGTH. OpenComputers не трогает эти хедеры. Поэтому придётся пройтись по всем ключам таблицы и найти хедер без учёта регистра. ⑧ — если length не nil, то это число. Тогда проверяем, что ещё столько байт мы не прочли, и заходим в цикл. Если же Content-Length не задан, то будем считать, что серверу не важно, сколько надо прочесть, и крутимся до упора. ⑨ — handle.read может ещё вернуть ошибку. Если нам известна длина, то в силу условия цикла мы прочли меньше, чем ожидали. Сигналим о неудаче. (Закрывать соединение в случае ошибки не требуется.) ⑩ — если же длина неизвестна, то считаем, что сервер отдал всё, что мог, ошибку игнорируем и покидаем цикл. ⑪ — не забываем обновлять read. ⑫ — если сервер случайно отослал нам больше данных, чем надо (а мы знаем, сколько надо: length определён), то излишки обрезаем. Код здесь отрежет с конца строки (read - length) байт. ⑬ — закрываем соединение за собой, когда оно больше не нужно. ⑭ — наконец, склеиваем таблицу в одну строку.  
    3.4. Скачивание файлов
    Код для скачивания похож на предыдущий. Только вот в память мы записывать ответ с сервера уже не будем. Вместо этого напрямую пишем в файл.
    local function getFile(url, path) local f, err = io.open(path, "w") -- ① if not f then return nil, ("could not open file for writing: %s"):format(err or "unknown error") end local handle, err = request(url, nil, nil, 10) -- ② if not handle then return nil, err end local read = 0 local _, _, responseHeaders = handle.response() local length for k, v in pairs(responseHeaders) do if k:lower() == "content-length" then length = tonumber(v) end end while not length or read < length do local chunk, err = handle.read() if not chunk then if length then f:close() -- ③ return nil, ("error occured while reading response: %s"):format(err or "unknown error") end break end read = read + #chunk if length and read > length then chunk = chunk:sub(1, length - read - 1) end f:write(chunk) end f:close() -- ④ handle.close() return true end ① — открываем файл, в этот раз для записи. Обрабатываем ошибки. ② — отправляем запрос без данных и с дефолтными хедерами. Обрабатываем ошибки. ③ — если мы сюда попали, то дальше сделаем ретурн. Поэтому не забываем закрывать за собой файл. (Сокет закрывать не нужно, так как при ошибке он это делает сам.) ④ — добропорядочно освобождаем ресурсы.  
    Чтобы было удобнее копипастить, я оставил повторяющийся код в двух функциях. В своей программке можно sendFIle и getFile отрефакторить, выделить дублирующуюся часть в отдельную функцию.
     
    3.5. UI
    Пришло время красивой каденции. Аккордом финальным в ней будет пользовательский интерфейс. Он к интернет-карте отношения уже не имеет, но для полноты приведу и его.
    local args, opts = shell.parse(...) local function printHelp() io.stderr:write([[ Usage: clbin { get [-f] <code> <path> | put <path> } clbin get [-f] <code> <path> Download a file from clbin to <path>. If the target file exists, -f overwrites it. clbin put <path> Upload a file to clbin. ]]) os.exit(1) end if args[1] == "get" then if #args < 3 then printHelp() end local code = args[2] local path = args[3] local url = ("https://clbin.com/%s"):format(code) path = fs.concat(shell.getWorkingDirectory(), path) if not (opts.f or opts.force) and fs.exists(path) then io.stderr:write("file already exists, pass -f to overwrite\n") os.exit(2) end local status, err = getFile(url, path) if status then print("Success! The file is written to " .. path) os.exit(0) else io.stderr:write(err .. "\n") os.exit(3) end elseif args[1] == "put" then if #args < 2 then printHelp() end local path = args[2] local url, err = sendFile(path) if url then url = url:gsub("[\r\n]", "") print("Success! The file is posted to " .. url) os.exit(0) else io.stderr:write(err .. "\n") os.exit(4) end else printHelp() end  
    3.6. Вуаля
    Осталось добавить реквайры, и мы получим полноценный клиент clbin. Результат — на гисте.
     
    4. Как правильно установить соединение через TCP-сокет
    Прошлая секция была вроде интересной, поэтому здесь тоже запилим какую-нибудь программку. @Totoro вот сделал интернет-мост Stem. Напишем для него клиент. Правильно. Опять же, особенности:
    Работает через TCP-сокет. Протокол бинарный. И асинхронный. А ещё сессионный: у каждого TCP-соединения есть собственный стейт. Доки хранятся на вики. При разрыве соединения клиент должен переподключиться и восстановить стейт.  
    Здесь снова придётся использовать все фичи интернет-карты.
     
    4.1. Архитектура
    Мы разделим программу на 2 части — фронтенд и бэкенд. Фронт будет заниматься рисованием и приёмом данных от пользователя, и им займёмся в конце и без комментариев. Бэк — поддержанием соединения и коммуникации с сервером. Это куда больше имеет отношения к гайду, рассмотрим подробнее.
     
    Бэкенд реализуем через ООП. Создадим конструктор, напихаем методов, которые затем будет дёргать фронт.
     
    4.2. Конструктор
    Привычно вбиваем ООП-шаблон в Lua.
    local newClient do local meta = { __index = {}, } function newClient(address, channels, connectionTimeout, readTimeout, maxReconnects) local obj = { __address = address, __channels = channels, __connectionTimeout = connectionTimeout, __readTimeout = readTimeout, __maxReconnects = maxReconnects; __socket = nil, __buffer = nil, __running = false, __reconnectCount = 0, } return setmetatable(obj, meta) end end Ну, тут всё мирно пока. Начнём боевые действия с протокола.
     
    4.3. Протокол
    Для него наклепаем кучу методов, которые будут крафтить пакеты и писать их через write. Write сделаем позже. Также сразу сделаем персеры.
    local meta = { __index = { __opcodes = { message = 0, subscribe = 1, unsubscribe = 2, ping = 3, pong = 4, }, __craftPacket = function(self, opcode, data) return (">s2"):pack(string.char(opcode) .. data) end, __parsePacket = function(self, packet) local opcode, data = (">I1"):unpack(packet), packet:sub(2) return self.__parsers[opcode](data) end, send = function(self, channel, message) return self:write(self:__craftPacket(self.__opcodes.message, (">s1"):pack(channel) .. message)) end, subscribe = function(self, channel) return self:write(self:__craftPacket(self.__opcodes.subscribe, (">s1"):pack(channel))) end, unsubscribe = function(self, channel) return self:write(self:__craftPacket(self.__opcodes.unsubscribe, (">s1"):pack(channel))) end, ping = function(self, message) return self:write(self:__craftPacket(self.__opcodes.ping, message)) end, pong = function(self, message) return self:write(self:__craftPacket(self.__opcodes.pong, message)) end, }, } meta.__index.__parsers = { [meta.__index.__opcodes.message] = function(data) local channel, idx = (">s1"):unpack(data) return { type = "message", channel = channel, message = data:sub(idx), } end, [meta.__index.__opcodes.subscribe] = function(data) return { type = "subscribe", channel = (">s1"):unpack(data), } end, [meta.__index.__opcodes.unsubscribe] = function(data) return { type = "unsubscribe", channel = (">s1"):unpack(data), } end, [meta.__index.__opcodes.ping] = function(data) return { type = "ping", message = data, } end, [meta.__index.__opcodes.pong] = function(data) return { type = "pong", message = data, } end, } В коде я активно использую string.pack и string.unpack. Эти функции доступны только на Lua 5.3 и выше, но позволяют очень удобно работать с бинарными форматами.
     
    4.4. Подключение к серверу
    Прежде чем реализуем write, нужно разобраться с подключением. Оно нетривиально.
    local meta = { __index = { ..., connect = function(self) local socketStream = assert(inet.socket(self.__address)) -- ① local socket = socketStream.socket -- ② local start = comp.uptime() -- ③ while true do local status, err = socket.finishConnect() if status then break end if status == nil then error(("connection failed: %s"):format(err or "unknown error")) -- ④ end if comp.uptime() >= start + self.__connectionTimeout then socket.close() error("connection failed: timed out") -- ④ end os.sleep(0.05) end self.__socket = socket -- ⑤ self.__buffer = buffer.new("rwb", socketStream) -- ⑥ self.__buffer:setTimeout(self.__readTimeout) -- ⑦ self.__buffer:setvbuf("no", 512) -- ⑧ for _, channel in ipairs(self.__channels) do -- ⑨ self:subscribe(channel) end end, }, } ① — я использую обёртку над component.internet. Она потом будет нужна, чтобы мы могли поместить сокет в буфер. Обращаю внимание, что вызов обёрнут в assert. Работает она так: если первое значение не nil и не false, то возвращает его, а иначе кидает ошибку, используя второе значение в качестве сообщения. Проще говоря, она превращает nil, "error message" в исключение. ② — а пока я вытягиваю из обёртки сокет... ③ — чтобы можно было проверить, установлено ли соединение. Код здесь аналогичен тому, что мы делали в прошлой секции. Не выдумываем. ④ — одно различие: вместо return nil, "error message" я сразу прокидываю исключение. Прежде всего потому, что ошибки мы прокидывать должны единообразно. Раз в ① кидаем исключение, и здесь делаем то же.

    Почему исключение, а не return nil, "error message"? Мы вызывать connect будем из всяких мест. Так как в случае ошибок бэкенд беспомощен, то лучше прокинуть ошибку до фронтенда и не усложнять код бэка проверками на nil. Кроме того, это громкая ошибка: если забыть где-то её обработать, она запринтится на экран, случайно пропустить её или подменить какой-нибудь непонятной "attempt to index a nil value" не получится.

    В конце концов, мне так проще. ⑤ — сокет я сохраняю в поле. socket.finishConnect нам ещё понадобится. ⑥ — пришло время обернуть сокет в буфер. Может показаться излишним, особенно учитывая ⑧. Причины станут ясны, когда будем делать чтение.

    rw — это буфер для чтения и записи. b — бинарный режим: buffer:read(2) вернёт 2 байта, а не 2 символа. Так как символы кодируются в UTF-8 и занимают 1 (латиница), 2 (кириллица, диакритика), 3 (BMP: куча письменностей, всякие графические символы, большая часть китайско-японско-корейских иероглифов) или 4 байта (всё, что не влезло в BMP, например emoji), то отсутствие этого режима может дать ощутимую разницу. В нашем случае протокол бинарный — ставим b. ⑦ — устанавливаем таймаут для чтения. Объясню подробнее, когда будем это чтение делать. ⑧ — отключаем буфер для записи. Он нам не нужен. ⑨ — здесь же подключаемся ко всем каналам.  
    Итого мы получаем свойства __socket и __buffer. Сокет использовать будем, чтобы вызывать .finishConnect() и .id(). Буфер — для записи и чтения.
     
    4.5. Запись
    Теперь, разобравшись с сокетами и буферами, мы можем запросто писать в сокет. Пилим write:
    local meta = { __index = { ..., write = function(self, data) return assert(self.__buffer:write(data)) end, }, } Здесь тоже оборачиваем write в assert, чтобы кидать исключения. Причины уже пояснял.
     
    4.6. Чтение и обработка пакета
    Сначала делаем функцию readOne. Она будет пытаться читать ровно один пакет. Здесь требуется нестандартная обработка ошибок, поэтому код сложноват.
    local meta = { __index = { ..., readOne = function(self, callback) -- ⑥ self.__buffer:setTimeout(0) -- ① local status, head, err = pcall(self.__buffer.read, self.__buffer, 2) self.__buffer:setTimeout(self.__readTimeout) if not status and head:match("timeout$") then return end assert(status, head) -- ② local length = (">I2"):unpack(assert(head, err)) -- ③ local packet = self:__parsePacket(assert(self.__buffer:read(length))) -- ④ if packet.type == "ping" then -- ⑤ self:pong(packet.message) end callback(self, packet) -- ⑥ return true end, } } ① — рассмотрим эту мишуру по порядку: Любой пакет stem начинается с 2 байт, которыми кодируется длина остатка. Отсюда всплывает двойка. Автор buffer, к сожалению, не осилил реализовать адекватную обработку ошибок. Он использует и исключения, и тихие ошибки (nil, "error message"). В случае таймаута будет прокинуто исключение. Однако мы перед чтением поставили таймаут в 0. Если буфер не найдёт сразу 2 байта в сокете, то он сразу кинет ошибку. Мы хотим проверить, есть ли в сокете пакет, который бы можно было прочесть. Используем pcall. Сначала раскроем self.__buffer:read(2) как self.__buffer.read(self.__buffer, 2), а затем поместим функцию и её аргументы в pcall. pcall возвращать будет сразу 3 значения по следующему принципу: Если на сокете есть 2 непрочитанных байта, read вернёт их без ошибок. Тогда status будет равен true, в head сохранятся эти 2 байта, а в err запишется nil. Если на сокете этих байтов нет, то read прокинет исключение "timeout". status установится в false, head приравняется "/lib/buffer.lua:74: timeout", а err также будет nil. Если же при чтении с сокета возникла другая ошибка, то read вернёт её по-тихому: status будет true, head — nil, а сообщение об ошибке уйдёт в err. Не думаю, что этот случай возможен, однако read может кинуть исключение и не из-за таймаута. status установится в false, а ошибка сохранится в head. В if мы проверяем, был ли таймаут (ситуация 1.2). В таком случае мы не кидаем исключения, а тихо выходим. Наконец, не забываем вернуть прежнее значение таймаута. ② — обрабатываем случай 1.4. ③ — обрабатываем случай 1.3 с помощью assert. Последний оставшийся и единственный успешный случай (1.1) также покрывается: распаковываем 2 байта в целое беззнаковое число (uint16_t). ④ — в ③ мы получили длину оставшегося пакета. Очевидно, надо остаток дочитать, что и делаем. Здесь уже не надо отдельно обрабатывать таймаут, достаточно assert. Считанный пакет отдаём в __parsePacket. ⑤ — если сервер докопался до нас своим пингом, отправим ему понгу. ⑥ — функция readOne принимает коллбэк. Это функция, которая будет обрабатывать все пакеты. Коллбэк будет передавать фронтенд, а бэкенд займётся минимальной обработкой, чтобы в принципе работало. Как, например, ③.  
    Отлично. Мы приготовили все примитивы, которые были нужны. Осталось собрать их воедино — в event loop.
     
    4.7. Event loop и события
    Ивент луп — это цикл, который ждёт событий и что-то с ними делает. Пришло время разобраться, что за события есть в OC.
     
    Когда мы вызываем socket.read или socket.finishConnect, устанавливается "ловушка" (селектор). Она срабатывает, когда на сокет пришли новые байты. При этом компьютер получает событие internet_ready. После чего "ловушка" деактивируется до следующего вызова.
     
    internet_ready, таким образом, — это событие, извещающее нас о том, что на сокете валяются непрочитанные данные и пора вызвать socket.read, чтобы их собрать. У события два параметра. Первый — это адрес интернет-карты. Второй — id сокета. Тот id, который возвращает socket.id(). Поэтому мы сохранили сокет в поле __socket: сейчас будем использовать его.
    local meta = { __index = { ..., __run = function(self, callback) while self.__running do local e, _, id = event.pullMultiple(self.__readTimeout, "internet_ready", "stem%-client::stop") -- ① if e == "internet_ready" and id == self.__socket.id() then -- ② while self:readOne(callback) do self.__reconnectCount = 0 -- ③ end elseif e ~= "stem-client::stop" then self:ensureConnected() -- ④ end end end, stop = function(self) self.__running = false event.push("stem-client::stop") -- ⑤ end, } } ① — ждём события internet_ready или stem-client::stop. Так как в event.pullMultiple названия ивентов сверяются через string.match, дефис экранируем. Второй ивент нужен, чтобы принудительно прервать цикл из stop. ② — обрабатываем мы только internet_ready и только для нашего сокета. Проверяем. ③ — если поймался пакет или пакеты, то пытаемся обработать каждый в порядке прибытия. Когда мы закончили обрабатывать все пакеты, self:readOne вернёт nil, и цикл прервётся. Кстати говоря, если мы внутри цикла оказались, то соединение установилось. Не забываем отметить это. ④ — если же улов пуст, перепроверяем, подключены ли мы вообще. ⑤ — не забываем добавить метод, чтобы остановить наш цикл. Отсюда же отсылаем событие stem-client::stop.  
    Отлично. Теперь пришло время ловить все наши прокидываемые исключения.
     
    4.8. Обработка ошибок
    Последними 2 функциями, которые мы добавим, будут ensureConnected и run. С их помощью бэкенд будет автоматически переподключаться к серверу в случае проблем.
    local meta = { __index = { ..., ensureConnected = function(self) local status, err = self.__socket.finishConnect() -- ① if status == false then error("not yet connected") end return assert(status, err or "unknown error") end, run = function(self, callback) if self.__running then -- ② return end self:connect() -- ③ self.__running = true while self.__running do -- ④ local status, err = pcall(self.__run, self, callback) -- ⑤ if not status then if self.__reconnectCount == self.__maxReconnects then -- ⑥ return nil, ("connection lost: %s; reconnect limit is reached"):format(err or "unknown error") end self.__reconnectCount = self.__reconnectCount + 1 self.__buffer:close() -- ⑦ if not pcall(self.connect, self) then -- ⑧ if self.__socket then self.__socket:close() end if self.__buffer then self.__buffer:close() end os.sleep(1) end end end self.__buffer:close() end, }, } ① — ensureConnected просто прокинет ошибку, которую вернёт finishConnect(). ② — принимаем защитную позицию против дураков. Рекурсивно запускать циклы смысла нет. ③ — сначала подключаемся к серверу. Если всё отлично, то можно начинать. ④ — как и в __run, здесь мы оборачиваем код в цикл. Если вызван stop(), то сначала остановится self.__run, а затем и этот цикл. ⑤ — обработка исключений требует pcall. Потому что их надо словить. ⑥ — если мы старались-старались, но так и не смогли уложиться в self.__maxReconnects по реконнектам, кидаемся белым флагом. ⑦ — не забудем закрыть буфер. ⑧ — вспомним, что self.connect кидает исключение. Перехватываем. На всякий случае позакрываем то, что породил connect.  
    4.9. Фронтенд
    На этом наш бэкенд готов. Поздравляю. Остаётся лишь прицепить ввод-вывод. Опять же, даю готовый код без комментариев, ибо не об этом пост.
    local gpu = com.gpu local w, h = gpu.getResolution() local function writeLine(color, line) local oldFg if gpu.getForeground() ~= color then oldFg = gpu.setForeground(color) end local lines = 0 for line in text.wrappedLines(line, w + 1, w + 1) do lines = lines + 1 end gpu.copy(1, 1, w, h - 1, 0, -lines) local i = 0 for line in text.wrappedLines(line, w + 1, w + 1) do gpu.set(1, h - lines + i, (" "):rep(w)) gpu.set(1, h - lines + i, line) i = i + 1 end if oldFg then gpu.setForeground(oldFg) end end local channel = ... if not channel then io.stderr:write("Usage: stem <channel>\n") os.exit(1) end if #channel == 0 or #channel >= 256 then io.stderr:write("Invalid channel name\n") os.exit(2) end local client = newClient( "stem.fomalhaut.me:5733", {channel}, 10, 10, 5 ) require("thread").create(function() while true do term.setCursor(1, h) io.write("← ") local line = io.read() if not line then break end local status, err = pcall(client.send, client, channel, line) if not status then writeLine(0xff0000, ("Got error while sending: %s"):format(err or "unknown error")) break end end client:stop() end) client:run(function(client, evt) if evt.type == "message" then writeLine(0x66ff00, "→ " .. evt.message) elseif evt.type == "ping" or evt.type == "pong" then writeLine(0xa5a5a5, "Ping: " .. evt.message:gsub(".", function(c) return ("%02x"):format(c:byte()) end)) end end) os.exit(0) Здесь я упускаю одну вещь: обработку ошибок в client.send. Если мы попытаемся отправить сообщение, когда у нас потеряно соединение (или до того, как оно установлено), мы или словим ошибку, или потеряем сообщение. Починить это можно, добавив очередь отправляемых пакетов, но это в разы усложнит программу, поэтому оставим так.
     
    4.10. Готово!
    Добавим реквайров... И у нас получился вполне рабочий клиент для Stem!

    Код программы — на гисте.
     
    5. В чём различие между component.internet и require("internet")
    Первое — исходный компонент. Второе — обёртка над ним. У обёртки есть 3 функции:
    internet.request(url, data, headers, method) — обёртка над component.internet.request. Удобна тем, что все ошибки превращает в исключения за программиста. Кроме того, возвращаемое значение — итератор, и его можно поместить в цикл for. Тем не менее, код, который ждёт установки соединения, нужно писать самому. internet.socket(address, port) — промежуточная обёртка над component.internet.connect. Она используется для того, чтобы потом превратить её в буфер, как сделали мы. Сама по себе достаточно бесполезна. internet.open(address, port) — тоже обёртка над component.internet.connect. Она вызывает internet.socket(address, port) и сразу превращает результат в буфер. Проблема в том, что сам объект сокета использовать можно только через приватные свойства, которые могут ломаться между обновлениями OpenOS. Из-за этого функция исключительно ущербна.  
    Для отправки HTTP-запросов я предпочитаю использовать API компонента. TCP-сокеты же проще создавать через обёртку (internet.socket), вручную проверять подключение и так же вручную укладывать обёртку в буфер, как показано выше.
     
    6. Конец
    Самое сложное в использовании интернет-карты — это правильно обработать все ошибки. Они могут возникнуть на каждом шагу, при этом быть полноценными исключениями или тихими ошибками. Необработанные исключения крашат программу, из-за чего возникает желание весь код программы поместить в один большой pcall. Например, IRC-клиент, который на дискете поставляется, делает так. Тихие ошибки гораздо подлее. Необработанные, они тоже крашат программу, только вот сама ошибка теряется, подменяется другой (обычно "attempt to index a nil value").
     
    В Lua обработать все ошибки — задача сложная, потому что механизм ошибок ужасен. В нормальных языках стэктрейс отделён от сообщения об ошибке, плюс каждая ошибка имеет свой тип, по которому можно безопасно определять вид ошибки. Lua этим не заморачивается: сообщение об ошибке включает позицию в коде, откуда ошибка прокинута. Есть или нет стэктрейс, зависит от выбора между pcall и xpcall. Если они находятся где-то в другой библиотеке, программист на выбор повлиять не может. В коде Stem-клиента единственный способ узнать, от таймаута ли ошибка прокинута, — матчить последние 7 символов на слово "timeout". Это эталонный костыль. Даже в JavaScript механизм лучше.
     
    Поэтому этот пост получился не столько про интернет-карту, сколько про обработку ошибок.
  12. Fingercomp

    Как отключить Ctrl-Alt-C

    Автор: Fingercomp,

    TL;DR: require("process").info().data.signal = function() end.
     
    С версии OpenOS 1.7.3 интеррапты работают так:
    local interrupting = uptime() - lastInterrupt > 1 and keyboard.isControlDown() and keyboard.isKeyDown(keyboard.keys.c) if interrupting then lastInterrupt = uptime() if keyboard.isAltDown() then require("process").info().data.signal("interrupted", 0) return end event.push("interrupted", lastInterrupt) end Это отрывок из /lib/event.lua. Он говорит, что если зажать Ctrl, Alt и C, то вызовется некоторая функция: require("process").info().data.signal.
     
    Программы в OpenOS запускаются в процессах. У каждого процесса есть свой главный поток (о них я писал где-то там), своё окружение. Каждый процесс следит за тем, какие файлы открыты, чтобы их закрыть при завершении процесса, жонглирует событиями и занимается сложной логикой. А ещё у каждого процесса есть свои данные. Эти данные для текущего процесса как раз возвращает process.info().data.
     
    У процессов есть иерархия. Корневой процесс — это тот, в котором запускается /init.lua. В нём устанавливается переменная signal:
    -- /boot/01_process.lua local init_thread = _coroutine.running() process.list[init_thread] = { path = "/init.lua", command = "init", env = _ENV, data = { vars={}, handles={}, io={}, --init will populate this coroutine_handler = _coroutine, signal = error -- ① }, instances = setmetatable({}, {__mode="v"}) }  
    Другие программы запускаются в дочерних процессах. Они наследуют данные родительского процесса. Поэтому process.info().data.signal, обработчик жёсткого интеррапта, по умолчанию возвращает функцию error. Но данные можно переопределить. Как видно из кода /lib/event.lua, нам достаточно, чтобы новый обработчик не вызывал error.
    require("process").info().data.signal = function(msg, level) print("You've pressed Ctrl-Alt-C!") end Это будет работать для всех потоков внутри текущего процесса, а также для других, запущенных в нём.
     
    Стоит отметить, что потоки знают, к какому процессу они прицеплены, и этот процесс можно менять на другой. thread:detach() — просто лёгкий способ сменить процесс, в котором работает поток, на корневой. А там process.info().data.signal — это функция error. Поэтому после Ctrl-Alt-C поток всё равно получит ошибку и, если она не поймана, завершится. А программа продолжит работать. Поэтому, чтобы быть совсем спокойным, можно отключить Ctrl-Alt-C глобально:
    local process = require("process") local p = process.findProcess() while p.parent do p = p.parent end p.data.signal = function() end Хотя я бы, конечно, не советовал так делать. Очень неудобно потом останавливать другие программы: приходится перезагружать компьютер.
  13. Fingercomp
    В комнатных условиях этот пост вы должны были получить по HTTPS. HTTPS — это такая матрёшка из HTTP и TLS. Что делает HTTP, в целом, всем более-менее понятно и так. А TLS делает HTTP безопасным, шифруя трафик туда-сюда, чтоб его нельзя было, перехватив, расшифровать или незаметно подменить.
     
    HTTPS-запросы в OpenComputers ещё можно посылать без ухищрений, а вот другие протоколы поверх TLS уже просто так не получится. Это, например, FTP и IRC, но, в принципе, может быть и XMPP (?), NNTP (??), SMTP (????) или даже SIP для совсем безумных. Да и HTTPS-то тоже не без ограничений. Когда история только начиналась лет десять назад, в OC нельзя было указывать свои хедеры. Сейчас можно, но, как я понимаю, всякие хипстерские PATCH-запросики отправить не получится, и попытки это исправить провалились.
     
    В общем, у реализации TLS прямо для OC на Lua польза есть. Так что где-то в прошлом тысячелетии я сделал libtls. Повезло, что в теме не сказать чтобы сильно разбирался и не представлял масштаба начинания. Качество реализации оказалось соответствующим. Поэтому, когда в 2018 году вышла новая версия протокола (1.3), было желание переписать всё с нуля и по-нормальному.
     
    Прошло пять лет. На месте индустрия не стояла и как раз с середины 2010-х годов стала внедрять алгоритмы, обеспечивающие forward secrecy. Этот термин означает, что даже если кто-то набрутфорсит или сольёт ключи от одной TLS-сессии, то в расшифровке последующих сессий ему успех этот никак не поможет, потому что каждый раз ключи генерируются другие. И так уж вышло, что эти алгоритмы работают либо долго, либо на эллиптических кривых.
     
    Как-то в IRC один человек пинганул меня, что очень хотелось бы в libtls эллиптическую криптографию. Разумеется, трогать libtls желания у меня никакого не было, поэтому вместо этого потратил 3 недели и запилил новую библиотеку libtls13. Это реализация TLS 1.3 для OpenComputers, но, кроме того, ещё и библиотека всяких криптографических алгоритмов на чистом Lua. Там и AES-GCM, и ChaCha20-Poly1305, и SHA2, и RSA, и, собственно, эллиптическая криптография: X25519, Ed25519. Когда я зарелизил, этот же человек попросил добавить ещё и ECDSA.
     
    ECDSA — это алгоритм электронной подписи на эллиптических кривых. Отправитель генерит пару ключей: секретный и публичный. Секретный он, хм, держит в секрете, потому что им он подписывает сообщения. Публичный же пускает по ветру, чтобы любой, кто получает сообщение и подпись, мог последнюю проверить. Если кто-то сообщение подменит, то проверка эта провалится. (Либо же этот кто-то накрутил удачи столько, что нашёл коллизию хэшей SHA-256, чему можно только позавидовать: пока таких людей не обнаружилось.)
     
    Тут нужно сказать, что ECDSA в libtls13 уже был, но только на дата-карточке. ECDSA работает с эллиптическими кривыми, и карточка умеет в две: secp256r1 (256-битные ключи) и secp384r1 (384-битные), — из которых в TLS юзабельна была только первая (потому что для 384 бит карточка не тот хэш юзает).
    И, естественно, человеку нужна была именно secp384r1.
     
    Вот про то, как я реализовывал на Lua алгоритм ECDSA для кривой secp384r1, и поговорим. Ниже:
    определение эллиптических кривых конечные поля и группы реализация модульной арифметики для фиксированного модуля а также операций в группе эллиптической кривой махинации с битами реализация собственно ECDSA (что, на самом деле, не так и интересно) пара слов об ASN.1 — как JSON, только от большого комитета из literally 1984 сколько-то про тестирование Всё это приправлено математикой и сложными терминами, чтоб сложней было понять.
     
    1. Эллиптические кривые
    Криптография на эллиптических кривых — это такое очень конкретное приложение абстрактной алгебры. Поэтому, когда гуглится какая-нибудь статья про них, автор либо считает, что читатель уже её основы получил на первом курсе вуза, либо пытается (не сильно успешно) излагать первый курс вуза сам. Мне кажется, что средний игрок в Minecraft, даже с OC, не сильно соотносится с прилежным студентом математической специальности. Поэтому в посте дальше попытаюсь (не сильно успешно) изложить элементы абстрактной алгебры.
     
    Итак. Взглянем-ка на вот этот набор символов.
     
    y2 = x3 + ax + b.
     
    Это уравнение. Тут есть буквы a и b — это какие-то константы. Они берутся от балды и не меняются. Ещё есть буквы x и y — это переменные. Они берутся от балды и вечно меняются.
     
    Уравнений много всяких, но вот конкретно это называется уравнением эллиптической кривой. Кривая там получается, если взять все решения (x, y) уравнения и намалевать ими по плоскости. Вот как это выглядит (пикча с википедии).
     

     
    Странно, конечно, что в первых трёх пикчах пузырь отчленён от усов, но в глазах математика кривая на каждой пикче ровно одна. Эллипсов нигде не видно. Впрочем, с ними эти кривые почти никак не связаны.
     
    Есть нюанс, правда. Если так получилось, что 4a3 + 27b2 = 0, то математики говорят, что мы налажали. На графике это выражается тем, что кривая самопересекается, имеет острые шипы (как на рисунке выше при a = b = 0) или изолированные одноточечные выбросы. К счастью, здесь a и b выбрали за нас в американском институте, и там всё гладенько.
     
    2. Кольца и поля
    Выше все числа были вещественными. В электронных вычислительных машинках работать с ними как-то несподручно. Поэтому сделали два гениальных хода.
    Во-первых, в уравнении ограничили a, b, x и y целыми числами. С этим уже попроще, но их как была бесконечность, так и стала. Так что, во-вторых, после каждой операции берётся остаток от деления на какое-то разумное число q. После каждой — это значит после каждого сложения, умножения и возведения в степень, то есть вот так:
     
    (y % q)(y % q) % q = (((((x % q)(x % q)(x % q) % q) + ((a % q)(x % q) % q)) % q) + (b % q)) % q.
     
    Каждый раз писать так влом, поэтому переопределим сложение, умножение и возведение в степень так, чтобы они сами работали по модулю q. И когда теперь я напишу y2 = x3 + ax + b, об этом вспомним и фактически делать будем то, что в большом уравнении.
     
    Думаю, то, что мы переопределили сложение, программиста на Lua сильно смущать не должно. Во-первых, с целыми числами и так все эти операции совершаются по модулю 264 (потому что числа 64-битные), и поэтому плюс не такой, как в школе, где числа бесконечны, уже не впервые встречается. Во-вторых, норкоманы спокойно переопределяют метаметоды __add и __sub и не сильно парятся об этом. Но программисты на Lua не единственные люди, которые такими вещами занимаются. Как и следовало ожидать, первой такой эзотерикой озаботились математики.
     
    Когда мы адекватно определяем сложение и умножение, вместе эти операции они называют кольцом. Само собою, как и эллиптические кривые на эллипсы не похожи, так и кольца эти с фигурой толком не связаны. Все эти имена — многовековое легаси, так что ничего удивительного. Кольцо — это такой абстрактный интерфейс, если по-человечески выражаться, с операциями + и *. Там надо, чтоб ещё кучка правил выполнялась, которые можно загуглить при желании (ну либо на всю жизнь запомнить, как я...). Польза от колец этих одна: они себя ведут приятным образом.
     
    Вот, например, сложение/умножение целых чисел по модулю — это кольцо. И поэтому работать по модулю можно вполне успешно: можем вычитать, выполняются привычные утверждения вроде (x + y)2 = x2 + 2xy + y2 и т. д.
     
    Кольца — это прекрасно, но возникают вопросы с делением. Деление здорового человека выглядит так: если a / b = c и b ≠ 0, то bc = a. То есть деление — обратная операция к умножению. В Lua что /, что // — деление курильщика. Первое нам бесполезно, потому что выдаёт числа с плавающей точкой, когда мы работали с целыми. Второе не обладает свойством выше.
     
    К вопросу подойти можно с тыльной стороны. Поделить на b — то же самое, что умножить на обратное к b. Оно обозначается b −1. В школе нужно просто взять и поделить единицу о b, но вот прям здесь это выглядит подозрительным. Потому что сначала деление определили через умножение на обратное, а потом обратное считаем через деление.
     
    Поэтому математики подсуетились и придумали поле. Это как кольцо, только ещё нужно для каждого ненулевого элемента определить ему обратный по умножению. То есть каждому b, кроме нуля, сопоставить b −1, чтобы b −1b = 1. И тогда можем спокойно делить, как ни в чём не бывало. Вся задача теперь состоит в определении обратного.
     
    И для модульной арифметики возникают проблемы. Оказывается, что, например, по модулю 264, как в Lua, для чётных чисел обратных в принципе не может существовать. Хотя вот для 3, например, обратный элемент имеется и равен −6148914691236517205 (можете проверить). Это означает, что просто так модульная арифметика — кольцо, но не поле. Поэтому, как бы деление ни попытались определить, нормально на всех (ненулевых) числах оно не заработает.
     
    Но как только модуль становится простым числом p, возникают чудеса. Потому что там вот как раз каждый элемент можно обратить. Например, если p = 13, то вот как это выглядит:
    1−1 = 1 2−1 = 7 3−1 = 9 4−1 = 10 5−1 = 8 6−1 = 11 7−1 = 2 8−1 = 5 9−1 = 3 10−1 = 4 11−1 = 6 12−1 = 12 Никакой ракетной магии: для каждого числа просто перебираем 12 ненулевых остатков от деления на 13 и ищем тот, умножение с которым даёт остаток 1.
     
    Модульная арифметика с простым модулем p является полем. Поэтому в нём верны все алгебраические преобразования, включая использующие деление. Например, a / b + c / d = (ad + bc) / bd, тоже со школы знакомое, справедливо, даже если все операции делать по модулю простого числа (а деление производить через умножение на обратное). Математики несколько веков без компьютера сидели и от скуки кучу таких преобразований напридумывали, и их все можно юзать в любом поле.
     
    Короче говоря, поле — это круто, поэтому дальше везде все операции будем проводить по модулю простого числа.
     
    3. Группа эллиптической кривой
    В первой главе мы взяли уравнение эллиптической кривой и полюбовались на графики. Во второй сказали, что работать будем по модулю, чтоб компуктер не взорвался, и уточнили, что модуль простой, чтоб могли делить и властвовать. Количество текста, которое посвятили делению, несмотря на то что до этого оно нигде не фигурировало, должно наталкивать на мысль, что всё ещё впереди. Поэтому продолжаем углубляться в эллиптическую нору.
     
    Точки эллиптической кривой — это пары чисел (x, y), которые решают уравнение кривой. Вот это уравнение ещё раз, чтоб не скроллили туда-сюда:
     
    y2 = x3 + ax + b.
     
    Теперь давайте придумывать, что с точками можно сделать.
     
    Для начала можно увидеть, что y фигурирует в уравнении единожды и в квадрате. Это значит, что если (x, y) уравнение решает, то и (x, −y) тоже вполне сойдёт, потому что квадрат минус всё равно съест. Ровно поэтому на самой первой пикче все кривые были симметричны горизонтальной оси. Так что первая операция точке P сопоставит ей противоположную, у которой координата y заменена на −y. Эту операцию вполне логично мы обозначим минусом: −P.
     
    Если есть минус, то должен быть и плюс. Это, конечно, не всегда так по жизни, но у нас абстрактные размышления, поэтому можем позволить. Плюс будет брать две точки и выплёвывать третью по какой-то схеме.
     
    Самое простое — это нейтральная точка, или «ноль». Её обозначим буквой O. И скажем, что P + O = O + P = P. Примитивные манёвры: сложение с нулём отдаёт исходную точку. Заодно свяжем и плюс с минусом: P + (−P) = O. Всё, дело за малым — определить плюс для остальных точек и узнать, какую именно точку мы обозначили за O.
     
    Мозг прежде всего тянется складывать точки покоординатно. Типа (a, b) + (c, d) = (a + c, b + d). Удобно, красиво, вот только в корне неверно. Слева от равенства были точки на нашей кривой. Справа от равенства точка очень вряд ли на ней окажется. Так как мы тысячу слов заморачивались с эллиптическими кривыми, такой плюс нас не устраивает.
     
    Обратимся к геометрии. Для этого возьмём рандомно, например, a = −1, b = 1 и построим график.
     

     
    Ой. По модулю 31 кривая — набор раскиданных точек. Как-то не очень информативно получается. Лучше тогда забыть про модуль и сообразить пока без него.
     

     
    Вот у нас две рандомных точки. Ну, например, проведём через них прямую.
     

     
    Вот она, третья точка-то! Можем, она и будет результатом сложения? То есть P + Q = R. Также получим P + R = Q.
     
    Но теперь вспомним про «ноль». Пусть Q = O, так как буквы похожи. Второе равенство говорит, что P + R = O, то есть P = −R. А по первому P = R. Получается, P = −P: любая точка равна противоположной! Это как-то совсем не то, что мы бы хотели.
     
    Решение просто — P + Q = −R. Иначе говоря, сумма трёх точек на прямой равна нулю. Тогда у нас всё будет работать шикарно.
     
    Свяжем геометрию с алгеброй: компьютеру нужно координаты R высчитывать по формуле. Если вспомнить уравнение прямой, подставить координаты P и Q и разрешить относительно R, то получим вот такое:
     
    s = (Q.y − P.y) / (Q.x − P.x),
    xʹ = s2 − P.x − P.y,
    yʹ = −P.y − s(xʹ − P.x).
     
    Вот (xʹ, yʹ) — это и есть наша сумма.
     
    Формулы всем прекрасны, кроме случая, когда у P и Q координата x одинакова. Потому что тогда в формуле для s будем делить на ноль, а это неприятно.
    Формула считает угол наклона прямой между P и Q. Прямая эта называется секущей, а предел секущей, как известно, есть касательная. Поэтому при P.x = Q.x приравняем s углу наклона касательной — то есть производной:
     

    s = (3P.x2 + a) / (2P.y).
     
    Но деление-то тут всё ещё есть, и если y в точке P занулится, то, пока P + P считать будем, делить станем на ноль. Правда, если P.y = 0, то P = −P (мы ведь именно у этой координаты знак меняем). Значит, P + P = O. Тоже всё, в принципе, решается дополнительными проверками.
     
    Кстати, пока мы здесь, в вещественных числах, было бы неплохо понять, а какие координаты у «нулевой» точки O. Ситуация получается очень весёлая, потому что их нет. Их украл товарищ Вейерштрасс. Вот как это вышло. Чтобы посчитать P + P, нам нужно взять касательную к P (см. справа).
     
    Если будем двигать P к левому краю, пересечение с кривой будет всё выше и выше. В конце концов пересечение улетит на бесконечность, а касательная станет вертикальной. Как мы помним, результатом суммы будет O. Получается, нулевая точка O находится на бесконечности, как бы странно это ни звучало. В простых координатах (x, y) бесконечность не уместится. Мы потом придумаем, что с этим делать, когда будем реализовывать всё вышеописанное на Lua.
     
    К слову, о Lua. Пока бы вернуться всё-таки к модульной арифметике. Как вся арканная геометрия нам поможет? А мы просто возьмём те же формулы. Посчитать по ним координаты мы можем, потому что они используют сложение, вычитание, умножение и деление, а все эти операции определены в поле. А результат будет решать уравнение потому, что оно тоже юзает те же операции.
     
    Работа в поле (операции по модулю простого числа) нас спасает просто по всем пунктам. Получается, абстракции, которые математики наплодили, несут какую-то пользу? Удивительно...
     
    Раз уж об абстракциях вспомнили, закинем ещё одну, чтоб объяснить название главы. Точки кривой с операцией их сложения математики назовут группой. Причём, так как порядок сложения точек не влияет на результат (по-умному это называется коммутативностью), группу назовут коммутативной (или абелевой). Поэтому, когда будем реализовывать операции на Lua, применим трюки из теории групп.
     
    Итак, что мы получили.
    Можем искать противоположные точки. Можем точки складывать между собой, оставаясь на кривой. Весь этот зоопарк называется группой. И под конец огребли дурное предзнаменование, что это нам ещё понадобится...  
    4. Арифметика в полях
    Пора б уже выдвигаться на поле и пытаться сооружать на Lua всё, что до этого описывали. Для начала познакомимся с кривой, с которой будем работать. Она называется secp384r1, потому что:
    определена она группой SEC над полем, образованным модульной арифметиков по модулю простого (p) числа длиной в 384 бит и параметры выбирались рандомно  
    Как уже говорил, кривая задаётся значениями a и b. У это кривой они такие:
     
    a = −3,
    b = 0xb3312fa7 e23ee7e4 988e056b e3f82d19 181d9c6e fe814112 0314088f 5013875a c656398d 8a2ed19d 2a85c8ed d3ec2aef.
     
    Размер константы b внушает уважение, конечно. Осталось ещё p обозначить. Оно вот такое необычное:
     
    p = 2384 − 2128 − 296 + 232 − 1.
     
    Длина модуля — 384 бит, и в одно целое число в языке Lua (всего с 64 битиками) оно никак не влезет. Поэтому эти числа мы побьём на кусочки и будем хранить в таблице. Нужно только понять, какого размера брать куски. Это зависит от того, какие операции собираемся проделывать.
     
    Нам нужны сложение и вычитание. В Lua с этим проблем не возникает, потому что + и - определены для 64-битных чисел.
     
    Нужны умножение и деление. Деление, как уже говорил, — просто умножение на обратное. Обращение чисел, как я потом покажу, мы тоже реализуем с помощью умножения. Таким образом, нужно лишь обеспечить добротное умножение, и всё будет в шоколаде.
     
    В Lua оператор * берёт два 64-битных числа и отдаёт 64-битное произведение. Если немного подумать, то 263 × 263 = 2126, что в 64 бита не очень-то и влезает. Всё, что не влезло в один кусочек результата, нам нужно будет перетащить в следующий. Но для этого нужно знать, что, собственно, перетаскивать. А Lua старшие биты не отдаёт, и узнать не получится.
     
    Поэтому если нужно умножение, то куски должны быть размером не больше 32 бит. Тогда даже самое большое произведение — (232 − 1)2 = 264 − 233 + 1 — влезет в 64 бита.
     
    Пораскинув мозгами, я порезал ещё мельче — длиной в 30 бит. Вот как это выглядит.
     

     
    Итого число представляется 13 кусками, которые я дальше называть буду словами. В таблице они лежат в порядке номеров бит. Это означает, что нулевой бит исходного числа находится в нулевом бите первого слова, а, например, 333-й — в третьем бите 12-го слова. Такой расклад называется little-endian. Так как 384 на 30 не делится, последнее, тринадцатое слово содержит всего 24 бита.
     
    Почему выбрал 30, а не 32, я объясню, когда будем пилить умножение. А пока начнём с малого — единицы и нуля.
     
    4.1. Нейтральные элементы
    Это такое умное название для нуля и единицы. Смотрим на схему выше и соображаем код:
    local function fieldZero(a) a = a or {} for i = 1, 13, 1 do a[i] = 0 end return a end local function fieldOne(a) a = a or {} for i = 2, 13, 1 do a[i] = 0 end a[1] = 1 return a end Так как вся криптография — это сплошные числодробилки, забивать память таблицами не очень хочется. Поэтому все наши функции будут результат записывать в таблицу, переданную по ссылке первым аргументом.
     
    Ноль и один — всему голова, но пора бы перейти к чему-то поинтереснее.
     
    4.2. Сложение
    Складывать числа будем по-простому: от младших слов к старшим.
    Правда, нужно ещё помнить о переносах:
    00111111 11111111 11111111 11111111 + 00111111 11111111 11111111 11111111 =================================== 01111111 11111111 11111111 11111110 ^ Тут я сложил два каких-то 30-битных числа. А получил 31-битное. Этот лишний бит надо изъять и прибавить к следующему слову. В результате код выглядит вот так:
    local carry = 0 for i = 1, 12, 1 do local word = a[i] + b[i] + carry c[i] = word & 0x3fffffff -- ① carry = word >> 30 -- ② end local word = a[13] + b[13] + carry c[13] = word & 0xffffff -- ③ carry = word >> 24 ① — это константа с тридцатью единицами. С помощью неё в c[⁠i] записываем только 30 младших бит.
    ② — а всё, что не вместилось, закидываем в carry, который на следующей итерации прибавится.
    ③ — с последним словом делаем всё то же, только там 24 бита, а не 30.
     
    На данном этапе получается вот так:
     
    a + b = c + 2384 * carry.
     
    Это мы сделали сложение по модулю 2384, а у нас он не такой:
     
    p = 2384 − 2128 − 296 + 232 − 1.
     
    Мы работаем по модулю p, так что
     
    2384 − 2128 − 296 + 232 − 1 = 0
     
    (= здесь — это «равно по модулю».)

    Перенесём всё, кроме первого, вправо:
     
    2384 = 2128 + 296 − 232 + 1.
     
    Получается, чтобы избавиться от бита переноса (carry), который у нас мог появиться после сложения, надо его прибавить к 128-му, 96-му и нулевому биту, а из 32-го вычесть. Ориентируемся на схему выше и так и поступаем:
    c[2] = c[2] - (carry << 2) -- bit 32 c[4] = c[4] + (carry << 6) -- bit 96 c[5] = c[5] + (carry << 8) -- bit 128 for i = 1, 13, 1 do local word = c[i] + carry c[i] = word & 0x3fffffff carry = word >> 30 carry = carry | -(carry & 1 << 63 >> 30) -- ① end В первых трёх строках мы обработали 128-й, 96-й и 32-й биты. Однако это может попортить ранее сделанную работу: например, если c[4] оказался равен 0x3fffffff — 30 единиц, — то после прибавления единицы c[4] будет уже 31-битным. Поэтому в циклике ниже я снова обрабатываю переносы. Заодно такое ловкое построение кода обработает и нулевой бит.
     
    Тут есть одна грабля, которая обозначена ①. Дело в том, что из 32-го бита мы carry вычитали. Что будет, если c[2] был нулевым до вычитания?
    00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 - 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000100 ======================================================================== 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111100 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Внизу оказалось закодировано -4. Когда в цикле дойдём до второго слова, мы в него запишем младщие 30 бит, как и положено. А потом в carry присвоим 34 старших бита (подчёркнуто в схеме выше):
    00000000 00000000 00000000 00000011 11111111 11111111 11111111 11111111 Это то, что мы собираемся прибавить к третьему слову. Но нам надо, наоборот, из третьего слова единицу вычесть, потому что во втором было слишком маленькое значение. Для этого вспомним, что x − 1 = x + (−1), то есть если мы хотим именно складывать, то в carry надо записать −1. И если бы carry был не 64-битным числом, а 34-битным, то именно −1 бы там и оказалось:
    11 11111111 11111111 11111111 11111111₂ = -1 Нам нужно лишь расширить carry до 64-битного числа, чтобы получилось так:
    11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111₂ = -1 Для этого самый старший бит здесь (тридцать третий) нужно прокопировать влево, пока не наберём, сколько нужно. Эта операция называется знаковым расширением. Именно этим и занимается строка, отмеченная ①:
    carry = carry | -(carry & 1 << 63 >> 30) Сначала мы достаём 33-й бит (1 << 63 << 30 — то же, что и 1 << 33):
    00000000 00000000 00000000 00000011 11111111 11111111 11111111 11111111 = carry & 00000000 00000000 00000000 00000010 00000000 00000000 00000000 00000000 = 1 << 63 >> 30 ======================================================================== 00000000 00000000 00000000 00000010 00000000 00000000 00000000 00000000 Затем мы берём противоположное число (такое, сумма с которым даёт ноль). Алгоритм его нахождения прост: перевернуть все биты в числе и прибавить единицу.
    00000000 00000000 00000000 00000010 00000000 00000000 00000000 00000000 ~: 11111111 11111111 11111111 11111101 11111111 11111111 11111111 11111111 +1: 11111111 11111111 11111111 11111110 00000000 00000000 00000000 00000000 Наконец, проставляем эти биты в carry:
    00000000 00000000 00000000 00000011 11111111 11111111 11111111 11111111 = carry | 11111111 11111111 11111111 11111110 00000000 00000000 00000000 00000000 = -(carry & 1 << 63 >> 30) ======================================================================== 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 = -1 Вуаля. Если бы 33-й бит в carry не стоял, то справа от | оказался бы 0, и вернулось бы то же число. Так что в результате цикл автомагически расставит переносы на словах.
     
    После всех этих операций мы получим либо число, полностью сокращённое по модулю p (то есть от 0 до p − 1), либо почти сокращённое — в пределах от p до 2p − 1. Иначе говоря, в c у нас останется лежать либо (a + b) % p, либо p + (a + b) % p. Чтобы довести процедуру до конца, надо проверить, меньше ли результат модуля p, и вычесть p, если это не так. Но мы этим заморачиваться будем только по необходимости, чтоб экономить ресурсы, потому что складывать мы будем очень много, и почти сокращённых чисел в большинстве случаев будет достаточно.
     
    Вот так складываются 2 числа по фиксированному модулю. Трюки, которые отсюда нужно извлечь:
    сложение с переносом перенос старших бит каждого слова в последующее сокращение лишних бит результата по модулю p знаковое расширение  
    4.3. Вычитание
    Вычитать число из другого будем кодом, похожим на предыдущий:
    -- "p right-shifted by 9" local prs9 = { -- ① 0x3ffffe00, 0x000007ff, 0x00000000, 0x3fff8000, 0x3ffdffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x1ffffffff, } local function fieldSub(c, a, b) local carry = 0 for i = 1, 12, 1 do local word = a[i] - b[i] + prs9[i] + carry -- ① c[i] = word & 0x3fffffff carry = word >> 30 carry = carry | -(carry & 1 << 63 >> 30) -- ② end local word = a[13] - b[13] + prs9[13] + carry -- ① c[13] = word & 0xffffff carry = word >> 24 c[2] = c[2] - (carry << 2) -- bit 32 c[4] = c[4] + (carry << 6) -- bit 96 c[5] = c[5] + (carry << 8) -- bit 128 for i = 1, 13, 1 do local word = c[i] + carry c[i] = word & 0x3fffffff carry = word >> 30 carry = carry | -(carry & 1 << 63 >> 30) end end Отличия я обозначил. Во-первых, числа, с которыми мы работаем, неотрицательные. Но нужно что-то делать, если вычитаем, например, единицу из нуля.
    Для этого функция выше вычисляет не a − b, а a + 29p − b. Этим ничего не сломаю, потому что 29p делится на p без остатка, и при сокращении по модулю он уйдёт. Но 29p — это 393-битное число (у него проставлен 392-й бит), а другие числа много меньше его (мы их держим в диапазоне от 0 до 2p - 1, напоминаю). Поэтому результат точно будет неотрицательным. Девятка здесь выбрана от балды: можно было и двойку поставить, например.
     
    А во-вторых, так как мы вычитаем числа, то может возникнуть та же проблема, что и раньше: в carry может понадобиться записать отрицательное число, чтоб вычесть его из следующего слова. Поступаем так же: производим знаковое расширение после каждого возможного вычитания.
     
    В остальном это то же сложение.
     
    4.4. Умножение
    Принцип работы умножения в модульной арифметике — сначала сделать само перемножение, а потом мучительно его сократить по модулю. Перемножать будем по словам «в столбик». В десятичной системе счисления мы каждую цифру одного числа множим на каждую цифру другого числа, а потом всё суммируем:
    123 × 321 ====== 3 = 1×3 + 2 = 1×2 + 1 = 1×1 + 6 = 2×3 + 4 = 2×2 + 2 = 2×1 + 9 = 3×3 + 6 = 3×2 + 3 = 3×1 ====== + 3 = 3 + 8 = 2 + 6 + 14 = 1 + 4 + 9 + 8 = 2 + 6 + 3 = 3 ====== 39483 Обычно в записи одну цифру умножают сразу на всё число, потому что в мозгу человека хватает кратосрочной памяти, чтоб запомнить переносы. Таким образом промежуточные результаты группируются по-горизонтали — так, как на схеме посередине (группы разделены пустыми строками).
     
    Но никто не мешает группировать и по-вертикали, как после второй черты. Например, первую строку получим, помножив 1-ю цифру одного числа на 1-ю цифру другого. Вторая строка — сумма произведения 1-й цифры одного числа на 2-ю цифру другого и произведения 2-й цифры на 1-ю. В общем случае будет так: если в числах K цифр, то n-ая строка — сумма всех a[⁠i] * b[n + 1 − i], где i меняется от math.max(1, n − K + 1) до math.min(n, K).
     
    Это были десятичные числа, где a[⁠i] с b[j] в пределах от 0 до 9. Ничто не мешает взять числа покрупнее. В частности, a[i⁠] и b[j] можно сделать 30-битными — по выбранному размеру слова. Формула останется той же самой, а промежуточный результат будет группирован по словам, что очень удобно. В коде это выглядеть будет так:
    local d = {} for n = 1, 25, 1 do local dn = 0 for i = math.max(1, n - 12), math.min(n, 13), 1 do local j = n + 1 - i dn = dn + a[i] * b[j] end d[n] = dn end Операция, которую мы проделываем, в математике называют свёрткой. В результате свёртки в d будут лежать промежуточные результаты умножения. Остаётся только перенести старшие биты каждого слова в последующее и провести сокращение по модулю.
     
    У себя в коде я этот цикл развернул, потому что умножений в ECDSA надо проделывать десятки тысяч, и вот такие вложенные циклы там ни к чему. Получилось так:
    local a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13 = table.unpack(a, 1, 13) local b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12, b13 = table.unpack(b, 1, 13) local d = { a1 * b1, a1 * b2 + a2 * b1, a1 * b3 + a2 * b2 + a3 * b1, a1 * b4 + a2 * b3 + a3 * b2 + a4 * b1, a1 * b5 + a2 * b4 + a3 * b3 + a4 * b2 + a5 * b1, a1 * b6 + a2 * b5 + a3 * b4 + a4 * b3 + a5 * b2 + a6 * b1, a1 * b7 + a2 * b6 + a3 * b5 + a4 * b4 + a5 * b3 + a6 * b2 + a7 * b1, a1 * b8 + a2 * b7 + a3 * b6 + a4 * b5 + a5 * b4 + a6 * b3 + a7 * b2 + a8 * b1, a1 * b9 + a2 * b8 + a3 * b7 + a4 * b6 + a5 * b5 + a6 * b4 + a7 * b3 + a8 * b2 + a9 * b1, a1 * b10 + a2 * b9 + a3 * b8 + a4 * b7 + a5 * b6 + a6 * b5 + a7 * b4 + a8 * b3 + a9 * b2 + a10 * b1, a1 * b11 + a2 * b10 + a3 * b9 + a4 * b8 + a5 * b7 + a6 * b6 + a7 * b5 + a8 * b4 + a9 * b3 + a10 * b2 + a11 * b1, a1 * b12 + a2 * b11 + a3 * b10 + a4 * b9 + a5 * b8 + a6 * b7 + a7 * b6 + a8 * b5 + a9 * b4 + a10 * b3 + a11 * b2 + a12 * b1, a1 * b13 + a2 * b12 + a3 * b11 + a4 * b10 + a5 * b9 + a6 * b8 + a7 * b7 + a8 * b6 + a9 * b5 + a10 * b4 + a11 * b3 + a12 * b2 + a13 * b1, a2 * b13 + a3 * b12 + a4 * b11 + a5 * b10 + a6 * b9 + a7 * b8 + a8 * b7 + a9 * b6 + a10 * b5 + a11 * b4 + a12 * b3 + a13 * b2, a3 * b13 + a4 * b12 + a5 * b11 + a6 * b10 + a7 * b9 + a8 * b8 + a9 * b7 + a10 * b6 + a11 * b5 + a12 * b4 + a13 * b3, a4 * b13 + a5 * b12 + a6 * b11 + a7 * b10 + a8 * b9 + a9 * b8 + a10 * b7 + a11 * b6 + a12 * b5 + a13 * b4, a5 * b13 + a6 * b12 + a7 * b11 + a8 * b10 + a9 * b9 + a10 * b8 + a11 * b7 + a12 * b6 + a13 * b5, a6 * b13 + a7 * b12 + a8 * b11 + a9 * b10 + a10 * b9 + a11 * b8 + a12 * b7 + a13 * b6, a7 * b13 + a8 * b12 + a9 * b11 + a10 * b10 + a11 * b9 + a12 * b8 + a13 * b7, a8 * b13 + a9 * b12 + a10 * b11 + a11 * b10 + a12 * b9 + a13 * b8, a9 * b13 + a10 * b12 + a11 * b11 + a12 * b10 + a13 * b9, a10 * b13 + a11 * b12 + a12 * b11 + a13 * b10, a11 * b13 + a12 * b12 + a13 * b11, a12 * b13 + a13 * b12, a13 * b13, } Вот тут можно поговорить, наконец, о том, почему слова именно 30-битные. Тринадцатый элемент — вот этот:
    a1 * b13 + a2 * b12 + a3 * b11 + a4 * b10 + a5 * b9 + a6 * b8 + a7 * b7 + a8 * b6 + a9 * b5 + a10 * b4 + a11 * b3 + a12 * b2 + a13 * b1, Это сумма 13 произведений 30-битных чисел. Каждое из чисел не превышает 230 − 1, поэтому каждое отдельное произведение не больше 260 − 231 + 1. А значит, сумма меньше либо равна 13 × (260 − 231 + 1) = 0xcffffff98000000d. В этом числе 64 бита, поэтому промежуточный результат вмещается без переполнения. Если же слова делить на 31 бит, то d[13] мог легко переполниться. Поэтому ограничился тридцатью.
     
    Это был первый этап умножения. Дальше предстоит 768-битное число сократить до 384 бит. Начинаем с известных технологий — переноса старших бит:
    local carry = 0 for i = 1, 25, 1 do local word = d[i] + carry d[i] = word & 0x3fffffff carry = word >> 30 end Двадцать шестое слово результата будет храниться в carry. Теперь надо избавиться от 13 старших слов, чтобы у нас остались только младшие 13 слов результата. Потому что их мы уже сокращать по модулю умеем (см. сложение, если не умеем). Пользуемся тем же трюком, что и раньше:
     
    2384 = 2128 + 296 − 232 + 1,
     
    поэтому (домножим на 26 + 30k):
     
    2390 + 30k = 2136 + 30k + 2102 + 30k − 238 + 30k + 26.
     
    После небольших перегруппировок получим, наконец, такое:
     
    230(13 + k) = 230(13 + k − 9) + 14 + 230(13 + k − 10) + 12 − 230(13 + k − 12) + 8 + 230(13 + k − 13) + 6.
     
    Страшно, да? А вот как это будет в коде:
    local i = 26 repeat d[i - 9] = d[i - 9] + (carry << 14) d[i - 10] = d[i - 10] + (carry << 12) d[i - 12] = d[i - 12] - (carry << 8) d[i - 13] = d[i - 13] + (carry << 6) i = i - 1 carry = d[i] until i == 13 По окончании у нас остаются 13 слов (390 бит), которые нужно свести до 384 бит. Для начала снова проделаем переносы, потому что мы активно в эти слова писали (и активно из них вычитали — не забываем знаковое расширение):
    carry = 0 for i = 1, 12, 1 do local word = d[i] + carry c[i] = word & 0x3fffffff carry = word >> 30 carry = carry | -(carry & 1 << 63 >> 30) end local word = d[13] + carry c[13] = word & 0xffffff carry = word >> 24 carry = carry | -(carry & 1 << 63 >> 24) И после этого, наконец, последний раз сократим результат по модулю. Здесь всё абсолютно то же самое, что и в конце сложения:
    c[2] = c[2] - (carry << 2) -- bit 32 c[4] = c[4] + (carry << 6) -- bit 96 c[5] = c[5] + (carry << 8) -- bit 128 for i = 1, 13, 1 do local word = c[i] + carry c[i] = word & 0x3fffffff carry = word >> 30 carry = carry | -(carry & 1 << 63 >> 30) end И на этом всё. Произведение a и b лежит в c и не превышает 2p − 1.
     
    4.5. Возведение в квадрат
    В эллиптической криптографии умножений в поле делается очень много. Но значительная часть умножений на самом деле является возведением в квадрат (a * a). В этом случае a[⁠i] * b[j] = a[j] * b[⁠i] (индексы меняются местами, а результат тот же, потому что a = b), и из 169 64-битных умножений почти половина (78) излишня, потому что вычисляет уже посчитанное значение.
     
    Поэтому имеет смысл сделать отдельную функцию для возведения в квадрат. Её код отличаться от прошлой будет только в двух местах: там нет распаковывания b, а свёртка (d) считается немного иначе:
    local d = { a1 * a1, a1 * a2 << 1, (a1 * a3 << 1) + a2 * a2, a1 * a4 + a2 * a3 << 1, (a1 * a5 + a2 * a4 << 1) + a3 * a3, a1 * a6 + a2 * a5 + a3 * a4 << 1, (a1 * a7 + a2 * a6 + a3 * a5 << 1) + a4 * a4, a1 * a8 + a2 * a7 + a3 * a6 + a4 * a5 << 1, (a1 * a9 + a2 * a8 + a3 * a7 + a4 * a6 << 1) + a5 * a5, a1 * a10 + a2 * a9 + a3 * a8 + a4 * a7 + a5 * a6 << 1, (a1 * a11 + a2 * a10 + a3 * a9 + a4 * a8 + a5 * a7 << 1) + a6 * a6, a1 * a12 + a2 * a11 + a3 * a10 + a4 * a9 + a5 * a8 + a6 * a7 << 1, (a1 * a13 + a2 * a12 + a3 * a11 + a4 * a10 + a5 * a9 + a6 * a8 << 1) + a7 * a7, a2 * a13 + a3 * a12 + a4 * a11 + a5 * a10 + a6 * a9 + a7 * a8 << 1, (a3 * a13 + a4 * a12 + a5 * a11 + a6 * a10 + a7 * a9 << 1) + a8 * a8, a4 * a13 + a5 * a12 + a6 * a11 + a7 * a10 + a8 * a9 << 1, (a5 * a13 + a6 * a12 + a7 * a11 + a8 * a10 << 1) + a9 * a9, a6 * a13 + a7 * a12 + a8 * a11 + a9 * a10 << 1, (a7 * a13 + a8 * a12 + a9 * a11 << 1) + a10 * a10, a8 * a13 + a9 * a12 + a10 * a11 << 1, (a9 * a13 + a10 * a12 << 1) + a11 * a11, a10 * a13 + a11 * a12 << 1, (a11 * a13 << 1) + a12 * a12, a12 * a13 << 1, a13 * a13, } Я тут ещё упоролся и вместо умножения на 2 побитово сдвигаю влево.
     
    4.6. Обращение чисел
    Как уже говорил, деление мы заменяем умножением на обратный элемент в поле. Для поиска обратного элемента по модулю простого числа у нас есть 2 варианта: либо применять расширенный алгоритм Евклида, либо воспользоваться малой теоремой Ферма. Проще всего второе, к тому же время его работы не зависит от входного числа, что важно в криптографии.

    Теорема это выглядит так: если a ≠ 0 и p простое, то a p − 1 = 1. Так как a p − 1 — это a × a p − 2, получается, что a p − 2 — обратный элемент. Значит, нам нужно всего лишь умножить a с собою p − 2 раз.
     
    Тут возникает проблема, потому что p − 2 — это слегка большое число со 116 знаками в десятичной записи. Если влоб работать на процессоре Рутмастера, который делает 10 миллиардов умножений в секунду, то обращение займёт всего 125 унтригинтиллионов лет. Достойная работа для вычислительного устройства.
     
    Ну на самом деле нет, есть варианты сильно лучше. Посмотрим пока на более приземлённые примеры: например, как мы можем возвести число в 45-ую степень? А вот, например:
    b = a -- b = a b = b^2 -- b = a² b = b^2 * a -- b = a⁵ b = b^2 * a -- b = a¹¹ b = b^2 -- b = a²² b = b^2 * a -- b = a⁴⁵ Вместо 45 умножений у нас всего 5 возведений в степень и 3 умножения. Алгоритм для такого называется square-and-multiply, и мы его подробно изучим позднее. Пока стоит отметить, что если мы позволим раскошелиться на временные переменные, то от одного умножения можно избавиться:
    b = a -- b = a b = b^2 -- b = a² b = b^2 * a -- b = a⁵ c = b^2 -- c = a¹⁰ c = c^2 -- c = a²⁰ b = c^2 * b -- b = a⁴⁵ Для экспонент на сто порядков больше тоже есть варианты сэкономить до приличия. Алгоритм square-and-multiply вышеупомянутый позволит возвести в степень 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112317 всего за 383 возведения в квадрат и 318 умножений.

    Но мы вместо этого воспользуемся тулзой addchain. Получится что-то такое:
    local function fieldInvert(b, a) local t1, t2, t3, t4 = {}, {}, {}, {} fieldSq(b, a) fieldMul(b, a, b) fieldSq(b, b) fieldMul(t2, a, b) fieldSq(b, t2) fieldSq(b, b) fieldSq(b, b) fieldMul(b, t2, b) fieldSq(t1, b) for i = 1, 5, 1 do fieldSq(t1, t1) end fieldMul(t1, b, t1) fieldSq(t3, t1) for i = 1, 11, 1 do fieldSq(t3, t3) end fieldMul(t1, t1, t3) for i = 1, 6, 1 do fieldSq(t1, t1) end fieldMul(b, b, t1) fieldSq(t1, b) fieldMul(t3, a, t1) fieldSq(t1, t3) fieldMul(t1, a, t1) fieldSq(t4, t1) for i = 1, 30, 1 do fieldSq(t4, t4) end fieldMul(t3, t3, t4) fieldSq(t4, t3) for i = 1, 62, 1 do fieldSq(t4, t4) end fieldMul(t3, t3, t4) fieldSq(t4, t3) for i = 1, 125, 1 do fieldSq(t4, t4) end fieldMul(t3, t3, t4) for i = 1, 3, 1 do fieldSq(t3, t3) end fieldMul(t2, t2, t3) for i = 1, 33, 1 do fieldSq(t2, t2) end fieldMul(t1, t1, t2) for i = 1, 94, 1 do fieldSq(t1, t1) end fieldMul(b, b, t1) fieldSq(b, b) fieldSq(b, b) fieldMul(b, a, b) end Функция слегка гигантская, но ничего ракетоподобного в ней не обнаруживается. Вместо 318 умножений здесь их всего 15 (возведений в квадрат осталось столько же), так что заморачивались не зря. Хотя всё равно дорогая операция.
     
    Итак, теперь мы можем складывать и вычитать числа по модулю p, а ещё умножать и даже делить. Славно поработали. Теперь, наконец, можно вернуться к тому, с чего начинали, то есть к эллиптическим кривым.
     
    5. Реализация операций на эллиптической кривой
    Непосредственно операций в поле, которые мы муторно реализовывали всю прошлую главу, ECDSA вообще не юзает. Но она выполняет операции над точками на эллиптической кривой, а они уже задействуют наше поле.
     
    Формулы товарища Вейерштрасса, которые мы вывели в третьей главе, хороши, но нам не очень подходят. Причин на то две.
     
    Во-первых, там надо дофига делить. Складывать точки нужно будет сотни раз, и каждый раз высчитывать обратный элемент — очень спорная затея. Это всё же самая дорогая операция, что у нас есть.
     
    Во-вторых, нет нуля. Тут я даже комментировать не буду.
     
    В общем, половину третьей главы вы читали зря, потому что юзать мы будем что-то совсем другое. Вместо того, что хранить координаты точки (x, y), мы будем таскать триплет (X, Y, Z). Каждая из больших букв — это 384-битное число из поля (то есть работаем по модулю p). Соотносятся эти представления так:
     
    x = X / Z 2,
    y = Y / Z 3.
     
    То есть, чтобы получить тройку по (x, y), можно просто засетить X = x, Y = y и Z = 1. Чтоб вернуться, нужно обратить Z, взять квадрат, домножить на X (получаем x) и на Z −1Y (получаем y).
     
    В принципе, можно увидеть, что для одной и той же точки (x, y) координаты (X, Y, Z) мы можем взять совершенно разные в зависимости от Z. Преимущество здесь в том, что для сложения точек по (X, Y, Z)-координатам нам вообще не нужно дорогущее деление. Оно там потвикает как-то X, Y, Z, и Z уже может стать не единичным, но пока нам не нужны конкретные x и y, никаких делений проводить не потребуется. Сделаем мы его лишь единожды — когда закончим работу с кривой.
     
    А ещё эта тройка позволяет кодировать точку на бесконечности...
     
    5.1. Нейтральный элемент
    Вспомним исходное уравнение кривой:
     
    y2 = x3 + ax + b.
     
    Подставим x = X / Z 2 и y = Y / Z 3 в него:
     
    Y 2 / Z 6 = X 3 / Z 6 + aX / Z 2 + b.
     
    Домножим обе части на Z 6:
     
    Y 2 = X 3 + aXZ 4 + bZ 6.
     
    У точки на бесконечности координата Z равна нулю (из-за чего x и y как раз в бесконечность улетают). Тогда от уравнения останется лишь это:
     
    Y 2 = X 3.
     
    В общем, как и у любой другой точки, точку на бесконечности тоже можно представить кучей способов. Например, (1, 1, 0). Я у себя даже вообще все координаты занулял, но здесь давайте всё же возьмём эту тройку как наш канонический нейтральный элемент.
    local function groupJacobianZero(q) q = q or {} q[1] = fieldOne() -- X q[2] = fieldOne() -- Y q[3] = fieldZero() -- Z return q end Хранить координаты эти будем в таблице по порядку: X, Y, Z. В функции написано Jacobian, потому что так называются координаты, которые мы используем.
     
    Вооружившись нулём, пришло время сделать что-нибудь полезное. Например, сложить-таки точки.
     
    5.2. Сложение точек
    В интернетах есть целый сайт с формулами для вычисления точек на эллиптических кривых. На нём можно найти вот эту запись. Формула не то чтобы очевидная, но нас особо тонкости её не волнуют.

    Что волнует, так это её цена: это 11 умножений, 5 возведений в квадрат, 9 сложений/вычитаний и 4 умножения на константу 2 (сдвиг влево на один бит). Они там отсортированы в порядке увеличения числа умножений как самой дорогой операции, и конкретно эта формула торчит сверху.

    Там, конечно, есть и ещё более дешёвые, но у них всех есть какие-то предположения к входным точками, например что Z = 1, и нам не подходят. Поэтому берём эту формулу и переписываем её на Lua.
    local function groupJacobianAddUnchecked(d, p, q) local x1, y1, z1 = p[1], p[2], p[3] local x2, y2, z2 = q[1], q[2], q[3] local x3, y3, z3 = d[1], d[2], d[3] local z1z1, z2z2, u1, u2, s1, s2, h, i, j, r, v = {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {} fieldSq(z1z1, z1) -- Z₁Z₁ = Z₁² fieldSq(z2z2, z2) -- Z₂Z₂ = Z₂² fieldMul(u1, x1, z2z2) -- U₁ = X₁ * Z₂Z₂ fieldMul(u2, x2, z1z1) -- U₂ = X₂ * Z₁Z₁ fieldMul(s1, z2, z2z2) -- Z₂³ fieldMul(s1, y1, s1) -- S₁ = Y₁ * Z₂³ fieldMul(s2, z1, z1z1) -- Z₁³ fieldMul(s2, y2, s2) -- S₂ = Y₂ * Z₁³ fieldAdd(z3, z1, z2) -- Z₁ + Z₂ fieldSub(h, u2, u1) -- H = U₂ - U₁ fieldMul2(i, h) -- 2 * H fieldSq(i, i) -- I = (2 * H)² fieldMul(j, h, i) -- J = H * I fieldSub(r, s2, s1) -- S₂ - S₁ fieldMul2(r, r) -- r = 2 * (S₂ - S₁) fieldMul(v, u1, i) -- V = U₁ * I local t2 = {} fieldMul2(t2, v) -- 2 * V fieldSq(x3, r) -- r² fieldSub(x3, x3, j) -- r² - J fieldSub(x3, x3, t2) -- X₃ = r² - J - 2 * V fieldMul(t2, s1, j) -- S₁ * J fieldMul2(t2, t2) -- 2 * S₁ * J fieldSub(y3, v, x3) -- V - X₃ fieldMul(y3, r, y3) -- r * (V - X₃) fieldSub(y3, y3, t2) -- Y₃ = r * (V - X₃) - 2 * S₁ * J fieldSq(z3, z3) -- (Z₁ + Z₂)² fieldSub(z3, z3, z1z1) -- (Z₁ + Z₂)² - Z₁Z₁ fieldSub(z3, z3, z2z2) -- (Z₁ + Z₂)² - Z₁Z₁ - Z₂Z₂ fieldMul(z3, z3, h) -- Z₃ = ((Z₁ + Z₂)² - Z₁Z₁ - Z₂Z₂) * H return fieldZeroFlag(r) end Здесь ещё юзаются 2 новые функции. fieldMul2 производит умножение на 2. Реализовано это на основе сложения, где a[⁠i] + b[⁠i] просто заменяется на (a << 1).
     
    И другая функция — fieldZeroFlag. Она возвращает 1, если в переменной r записан ноль, либо 0 в противном случае. Так как все числа у нас в промежутке от 0 до 2p − 1, узнать, равно ли число нулю, можно, например, так:
    local function fieldReduceQuick(b, a) -- a minus p local amp = {} local borrow = 0 for i = 1, 13, 1 do local word = a[i] - p[i] - borrow amp[i] = word & 0x3fffffff borrow = word >> 63 end fieldCopy(b, a) fieldCmov(b, amp, borrow ~ 0x1) return borrow end local function fieldZeroFlag(a) local b = {} fieldReduceQuick(b, a) local bits = 0 for i = 1, 13, 1 do bits = bits | b[i] end return -bits >> 63 ~ 0x1 end Сначала приводим число к диапазону от 0 до p − 1, для чего по-простому вычитаем из числа p. Выбираем из результата вычитания и исходного числа неотрицательное, а другое выкидываем. Затем проходимся по всем битам в выбранном числе, склеивая их трубою (|) в переменную bits. Если bits нулевой, то −bits тоже будет нулевым; если же bits ненулевой, то −bits будет отрицательным. Поэтому если извлечь знаковый бит и инвертировать его (при помощи XOR: ~ 0x1), получим как раз то, что и нужно было.
     
    Могли заметить, что код несколько громоздкий. Например, всё, что делает fieldZeroFlag, — проверяет, является ли какое-либо из слов ненулевым. Это можно сделать сильно проще вот так:
    for i = 1, 13, 1 do if b[i] ~= 0 then return 0 end end return 1 Но тогда время исполнения этого цикла будет зависеть от исходного числа. Так, конечно, можно делать, но с точки зрения практической криптографии это нехорошо. Время работы криптографических алгоритмов не должно зависеть от значения секретных данных, потому что никто не мешает замерить это время и получить информацию о содержимом секретов. Если же оно не зависит, то замеры никакой информации раскрыть не могут. Такие алгоритмы называются работающими за константное время.
     
    В посте у меня есть только алгоритм проверки подписи, а не генерации её. Проверка же работает только с публичными значениями. Поэтому конкретно в этом случае, действительно, можно было сделать и по-простому. Но когда я реализовывал, я планировал ещё и генерацию сделать, которой нужен уже секретный ключ. Поэтому все приводимые алгоритмы работают за константное время, хотя на реализацию генерации подписи я к концу подзабил.
     
    Вернёмся к сложению, однако. Давным-давно, в другой главе у нас были две различные формулы для сложения двух точек. Даже в координатах (X, Y, Z) от этого мы никуда не ушли: формула выше, которую реализовали для сложения двух точек, выдаёт правильный результат только в том случае, если P и Q — две различные ненулевые точки.

    Проверить, что точки ненулевые, весьма просто: у них должна быть ненулевая координата Z. Но как можно убедиться в том, что они различны, ведь одну и ту же точку можно записать в координатах (X, Y, Z) огромным числом способов? Для этого придётся снова позаниматься алгеброй.
     
    Сначала поразмышляем в обратном направлении: что будет, если P = Q? Тогда, вполне очевидно, x1 = x2 и y1 = y2. Выразим это через X, Y, Z:
     
    x1 = x2  ⇒  X1 / Z12 = X2 / Z22,
    y1 = y2  ⇒  Y1 / Z13 = Y2 / Z23.
     
    Вследствие этого в формуле выше получим, что
     
    S2 = Y2Z13 = Z13Z23Y1 / Z13 = Y1Z23 = S1.
     
    Тогда r = S2 − S1 = 0. Аналогично можно получить, что U1 = U2, из-за чего H обнуляется, и поэтому Z3 также будет нулевым. То, что Z3 нулевое, значит, что результат суммы — точка на бесконечности.
     
    Теперь попробуем изменить порядок мысли. Пусть мы провели сложение двух ненулевых P и Q и получили точку на бесконечности и r = 0. Можем ли тогда сказать, что P = Q, и формулу на самом деле применять было нельзя?
     
    Из того, что r = 0, мы получаем, что S1 = S2. Z1 и Z2 не равны нулю (входные точки ненулевые), поэтому:
     
    Y1Z23 = Y2Z13  ⇒  Y1 / Z13 = Y2 / Z23,
     
    то есть y1 = y2.
     
    Теперь разберёмся с иксами. Формула для Z3 такая: ((Z1 + Z2)2 − Z12 − Z22) × H. Так как мы работаем в поле, можно спокойно раскрыть скобки внутри:
     
    Z3 = (Z12 + 2Z1Z2 + Z22 − Z12 − Z22) × H = 2Z1Z2H.
     
    Опять вспоминаем, что Z1 и Z2 ненулевые, а результат нулевой. Можем ли тогда сказать, что H = 0? Да, можем, потому что работаем в поле, где это выполняется.
     
    Тут я б хотел отметить, что необходимо именно поле, а не кольцо. Допустим, мы работали бы по модулю составного числа 15. Но тогда могли бы взять два ненулевых числа 3 и 5, перемножить и словить ноль в ответе! В поле такого невозможно. К счастью, у нас все операции по модулю простого числа p, поэтому это именно поле.
     
    Итак, получили, что H = 0. Это означает, что U1 = U2. Подставим формулы для U1 и U2:
     
    X1Z22 = X2Z12  ⇒  X1 / Z12 = X2 / Z22.
     
    Слева x1, справа x2, и они равны. Победа: мы доказали, что r = 0 и Z3 = 0 означает, что x1 = x2 и y1 = y2.
     
    Алгоритм сложения тогда выглядеть будет так:
    Если P = O, то вернуть Q. Если Q = O, то вернуть P. Провести сложение по формуле выше. Если функция вернула 1 (то есть r = 0) и результат — точка на бесконечности, то результат неверный и нужно пересчитать его по формуле удвоения точки. Иначе вернуть результат (он корректен).  
    В целом всё закономерно, но нужна формула удвоения. Давайте реализуем и её.
     
    5.3. Удвоение точек
    Для удвоения (вычисления P + P) формулы тоже приведены на том же сайте. Юзать будем вот такую. В коде она выглядит так:
    local function groupJacobianDouble(q, p) local x1, y1, z1 = p[1], p[2], p[3] local x3, y3, z3 = q[1], q[2], q[3] local delta = {} fieldSq(delta, z1) -- delta = Z₁² local gamma = {} fieldSq(gamma, y1) -- gamma = Y₁² local beta = {} fieldMul(beta, x1, gamma) -- beta = X₁ * gamma local x1mdelta = {} local alpha = {} fieldSub(x1mdelta, x1, delta) -- X₁ - delta fieldAdd(alpha, x1, delta) -- X₁ + delta fieldMul(alpha, x1mdelta, alpha) -- (X₁ - delta) * (X₁ + delta) fieldMul3(alpha, alpha) -- alpha = 3 * (X₁ - delta) * (X₁ + delta) fieldAdd(z3, y1, z1) -- Y₁ + Z₁ fieldSq(z3, z3) -- (Y₁ + Z₁)² fieldSub(z3, z3, gamma) -- (Y₁ + Z₁)² - gamma fieldSub(z3, z3, delta) -- Z₃ = (Y₁ + Z₁)² - gamma - delta fieldMul4(y3, beta) -- 4 * beta fieldMul2(beta, y3) -- 8 * beta fieldSq(x3, alpha) -- alpha² fieldSub(x3, x3, beta) -- X₃ = alpha² - 8 * beta fieldSq(gamma, gamma) -- gamma² fieldMul8(gamma, gamma) -- 8 * gamma² fieldSub(y3, y3, x3) -- 4 * beta - X₃ fieldMul(y3, alpha, y3) -- alpha * (4 * beta - X₃) fieldSub(y3, y3, gamma) -- Y₃ = alpha * (4 * beta - X₃) - 8 * gamma² end Здесь функции нужны ещё fieldMul3, fieldMul4 и fieldMul8. Их всех можно определить на основе fieldMulWord, которая умножает 384-битное число на одно 30-битное слово по модулю p:
    local function fieldMulWord(c, a, b) local carry = 0 for i = 1, 12, 1 do local word = a[i] * b + carry c[i] = word & 0x3fffffff carry = word >> 30 end local word = a[13] * b + carry c[13] = word & 0xffffff carry = word >> 24 c[2] = c[2] - (carry << 2) -- bit 32 c[4] = c[4] + (carry << 6) -- bit 96 c[5] = c[5] + (carry << 8) -- bit 128 for i = 1, 13, 1 do local word = c[i] + carry c[i] = word & 0x3fffffff carry = word >> 30 carry = carry | -(carry & 1 << 63 >> 30) end end По сути это то же сложение, только вместо a[⁠i] + b[⁠i] пишем a[⁠i] * b. Вместо 169 умножений, как в fieldMul, здесь их нужно всего 13, поэтому в этих заморочках имеется смысл.
     
    Формула удвоения никаких особых случаев, как при сложении, не имеет и без проблем удваивает любую входную точку. Она ещё и дешевле, чем сложение. Но в данном случае формулу удвоения нужно было реализовывать для обеспечения корректности, а не простой оптимизации.
     
    Люди кучу раз пытались реализовывать криптографию на эллиптических кривых и постоянно спотыкались о то, что формула сложения выдаёт неверный результат, если P = Q. Ситуация эта не то чтобы очень частая, поэтому найти проблему трудно, и она проскакивает незамеченной, пока какой-нибудь заинтересованный человек не сломает из-за неё всю криптосистему.
     
    На помощь приходят «полные» формулы сложения, которые, хотя и дорогие по сравнению с обычными формулами, выдают корректный результат на всех входных данных. Таким образом, с ними все эти проблемы избегаются. Найти их можно, например, в этой статье: https://eprint.iacr.org/2015/1060.pdf. В качестве упражнения можно попробовать реализовать их самому.
     
    5.4. Вычитание точек
    Последняя базовая операция, которая нам нужна в группе эллиптической кривой, — это вычитание одной точки из другой. Его можно реализовать при помощи сложения с противоположной точкой. У противоположной точки другой знак у координаты y — и, следовательно, Y. В модульной арифметике «поменять знак» значит просто вычесть y из нуля. Поэтому вычитание выглядит следующим образом:
    local function groupJacobianSub(d, r, q) local mq = {q[1], {}, q[3]} fieldSub(mq[2], fieldZero(), q[2]) groupJacobianAdd(d, r, mq) end Теперь, когда все основные операции у нас реализованы, наконец можно поговорить о ECDSA.
     
    6. Умножение на скаляр. Приватные ключи
    С точками прямо сейчас мы можем совершать две вещи: обнулять и суммировать. Инструменты скудные, поэтому попробуем что-нибудь изобразить помощнее.

    Для этого возьмём какую-нибудь точку P на кривой и будем её прибавлять к самой себе несколько раз: P + P, P + P + P и т. д. Чтоб не взрываться с записи, обозначать такое мы будем дальше так: [k]P, где k — какое-то число, — это k точек P, сложенные вместе. Операция эта, как выясняется, не бессмысленна, потому что затрагивает много вопросов о жизни и смерти циклических групп.
     
    Вот что я имею в виду. В нашей группе точек явно не бесконечно. Как минимум, различные точки должны иметь различные координаты, а различных координат существует только p2. Причём большинство из них не будут решать уравнение, так что точек на кривой ещё меньше.
     
    Получается, когда мы будем увеличивать k в [k]P, рано или поздно мы начнём повторяться. Причём, если подумать, то первой повторится точка P, потом [2]P и так далее. Более того, повторению P будет предшествовать получение точки на бесконечности. Значит, есть какое-то такое ненулевое N, что [N]P = O, и потом снова [N + 1]P = P, [N + 2]P = [2]P, ... То есть все эти сложения цикличны.

    Минимальное такое N в математике называется порядком элемента. Равно ли N количеству точек на кривой (это количество называется порядком группы)? То есть будем ли мы повторяться с безысходности, когда пробежим вообще все существующие точки?

    В общем случае — не факт. Но группа эллиптической кривой secp384r1 является циклической. Это значит, что на кривой есть такая точка G, порядок которой таки равен порядку группы. Она называется порождающим элементом либо генератором группы. Прибавляя генератор к самому себе, мы каждый раз будем получать разные точки, пока не обойдём всю кривую.
     
    Обзовём, как и в стандарте ECDSA, порядок группы буквой n. В случае secp384r1 это простое число, слегка меньшее, чем p. Координаты генератора G на кривой тоже даются в стандарте.

    Ключевая вещь, благодаря чему эллиптические кривые вообще несут какую-то пользу в криптографии, такая. Для любой точки P можем набрать достаточно генераторов в сумме, чтобы её получить, то есть существует k такое, что [k]G = P. По k найти P очень просто, и мы этим дальше будем как раз заниматься. А вот обратно, — зная P, найти k — дико сложно. Единственные варианты, которые придумали, лишь слегка умнее перебора втупую.
     
    Поэтому в ECDSA рандомное k от 1 до n − 1 является приватным ключом и никому не раскрывается. А по нему вычисляется Q = [k]G, координаты которой будут уже публичным ключом, известными всему миру.
     
    Как уже писал ранее, на генерацию ключей и подписей я подзабил, когда дошёл до этого, и реализовал только проверку подписи. А там вместо вычисления [k]G нужно считать [⁠u]G + [v]Q. Можно было бы, конечно, реализовать отдельно алгоритм для вычисления [k]P с любых k и P, потом применить его дважды и сложить результаты, но я не стал. Заместо этого я реализовал отдельный специализированный алгоритм, который вычисляет сразу всё выражение [⁠u]G + [v]Q для заданных u, v и Q.
     
    6.1. Алгоритмы умножения на скаляр
    Итак, нужно точку P скалярно множить на скаляр. Скаляр увесистый — 384 бит в ширину. Пока будем одно число так влоб суммировать, перед глазами новемвигинтиллион вселенных успеют до текущего состояния с нуля развиться. Хм, где-то мы уже с такой проблемой боролись...
     
    В общем, я бы мог тут упороться с мультипликативными группами поля и дискретными логарифмами. Но проще будет сказать, что все те методы, с помощью которых возводили числа в гигантские степени по модулю, могут быть применены и для умножения точек кривой на скаляр. Например, я там говорил про алгоритм square-and-multiply («взять квадрат и помножить»). Здесь это будет double-and-add («удводить и сложить»). Давайте всё-таки изучим, что это за алгоритм такой.
     
    Пусть наше k не 384, а 5 бит в ширину и равен двадцати двум — либо 101102 в двоичной записи. Для начала мы обнуляем результат, после чего начинаем обходить биты в числе k от старшего ко младшему. Каждый раз при переходе к следующему биту результат удваиваем, после чего, если бит попался единичный, ещё и прибавляем к нему P.

    Вот что это вытворит для нашего k:
    k = 10110 result = O 1. удваиваем результат: result = [2]result = [2]O = O 2. получаем следующий бит: k = 10110 ↳ 1 3. он единичный, поэтому прибавляем к результату P: result = result + P = O + P = P result = [1₂]P 1. удваиваем результат: result = [2]result = [2]P = [2]P 2. получаем следующий бит: k = 10110 ↳ 0 3. он нулевой, так что ничего не делаем result = [10₂]P 1. удваиваем результат: result = [2]result = [2][2]P = [4]P 2. получаем следующий бит: k = 10110 ↳ 1 3. он единичный, поэтому прибавляем к результату P: result = result + P = [4]P + P = [5]P result = [101₂]P 1. удваиваем результат: result = [2]result = [2][5]P = [10]P 2. получаем следующий бит: k = 10110 ↳ 1 3. он единичный, поэтому прибавляем к результату P: result = result + P = [10]P + P = [11]P result = [1011₂]P 1. удваиваем результат: result = [2]result = [22]P 2. получаем следующий бит: k = 10110 ↳ 0 3. он нулевой, так что ничего не делаем result = [10110₂]P После третьего шага я каждый раз показываю скаляр в результате в двоичной записи. Битики в скаляре всегда совпадают с битиками, которые мы до этого момента прочли. В конце алгоритма, соответственно, битики в скаляре совпадают с k, и мы получаем корректный результат.
     
    Алгоритм в целом уже неплох, но сейчас надо делать столько сложений, сколько в скаляре бит, а их там до 384 может быть. Хотелось бы уменьшить объём работы. Идея состоит в том, чтобы вместо прибавления одного бита каждый раз, докидывать их сразу пачкой в результат. Сделать это можно так:
    Выбираем размер окна — w бит. Множим точку P на нечётные скаляры от 3 до 2w − 1: получим [3]P, [5]P, [7]P, ..., [2w − 1]P. Обнуляем результат. Обходим биты в скаляре k от старшего к младшему и каждый раз: Удваиваем результат. Читаем следующий бит из k, и, если он ненулевой, делаем следующее: Среди последующих w − 1 битов находим последний единичный и прочитываем все биты до него (включительно). Все прочитанные биты, включая самый первый из 4.2, объединяем в число x. Удваиваем результат столько раз, сколько дополнительных бит скушали в 4.2.1. И прибавляем к результату [x]P.
    Возьмём какой-нибудь более амбициозный k = 6717 = 11010001111012, а размер окна выберем w = 3. Алгоритм отработает следующим образом:
    удваиваем P, запоминаем [2]P вычисляем: [3]P = [2]P + P [5]P = [2]P + [3]P [7]P = [2]P + [5]P k = 1101000111101 result = O 1. удваиваем результат: result = [2]result = [2]O = O 2. читаем следующий бит: k = 1101000111101 ↳ 1 он единичный, поэтому: 1. среди последующих 2 битов находим последний единичный и считываем до него: k = 1101000111101 ^· 2. x = 11₂ 3. удваиваем результат 1 раз: result = [2]result = O 4. прибавляем [x]P к результату: result = result + [11₂]P = [11₂]P 1. удваиваем результат: result = [2]result = [2][11₂]P = [110₂]P 2. читаем следующий бит: k = 1101000111101 ↳ 0 1. удваиваем результат: result = [2]result = [2][110₂]P = [1100₂]P 2. читаем следующий бит: k = 1101000111101 ↳ 1 3. он единичный, поэтому: 1. среди последующих 2 битов находим последний единичный и считываем до него: k = 1101000111101 ·· 2. x = 1₂ 3. удваиваем результат 0 раз 4. прибавляем [x]P к результату: result = result + [1₂]P = [1101₂]P 1. удваиваем результат: result = [2]result = [2][1101₂]P = [11010₂]P 2. читаем следующий бит: k = 1101000111101 ↳ 0 1. удваиваем результат: result = [2]result = [2][11010₂]P = [110100₂]P 2. читаем следующий бит: k = 1101000111101 ↳ 0 1. удваиваем результат: result = [2]result = [2][110100₂]P = [1101000₂]P 2. читаем следующий бит: k = 1101000111101 ↳ 0 1. удваиваем результат: result = [2]result = [2][1101000₂]P = [11010000₂]P 2. читаем следующий бит: k = 1101000111101 ↳ 1 3. он единичный, поэтому: 1. среди последующих 2 битов находим последний единичный и считываем до него: k = 1101000111101 ~^ 2. x = 111₂ 3. удваиваем результат 2 раза: result = [2]result = [2][11010000₂]P = [110100000₂]P result = [2]result = [2][110100000₂]P = [1101000000₂]P 4. прибавляем [x]P к результату: result = result + [7]P = [1101000111₂]P 1. удваиваем результат: result = [2]result = [2][1101000111₂]P = [11010001110₂]P 2. читаем следующий бит: k = 1101000111101 ↳ 1 3. он единичный, поэтому: 1. среди последующих 2 битов находим последний единичный и считываем до него: k = 1101000111101 ~^ 2. x = 101₂ 3. удваиваем результат 2 раза: result = [2]result = [2][11010001110₂]P = [110100011100₂]P result = [2]result = [2][110100011100₂]P = [1101000111000₂]P 4. прибавляем [x]P к результату: result = result + [5]P = [1101000111101₂]P В данном случае пришлось сделать 14 удвоений (1 в подготовительной фазе и 13 в цикле) и 7 сложений (3 + 4 соответственно). С прошлым алгоритмом double-and-add бы потребовалось 13 удвоений, но 8 сложений. Так как сложения дороже, то алгоритм даёт чистый выигрыш в стоимости операций.

    В целом он обычно работает не хуже, чем double-and-add, и особенно хорошо, если в скаляре несколько единиц подряд. Но если единичек мало, то подготовительные вычисления могут насчитать точки, которые я потом нигде не заиспользую, и время на вычисления потрачу зря.
     
    Более того, нам необязательно именно складывать постоянно. Можно и вычитать! Несколько странно видеть, конечно, вычитание при вычислении суммы, но смысл в нём имеется, если в скаляре очень много единиц идут подряд.
     
    Например, как в k = 1023 = 11111111112, где их все десять. Вместо 10 удвоений и 10 сложений (double-and-add) или 11 удвоений и 7 сложений (улучшенный алгоритм) можно поступить так. Посчитать [1024]P — на это нужно 11 удвоений. А затем вычесть P. И выйдет это сильно дешевле.
     
    6.2. Генерация цепи сложений-вычитаний
    Вот ровно этим код ниже и занимается:
    local function getChain(k) local r = {} for i = 0, 383, 1 do -- ① r[i + 1] = k[i // 30 + 1] >> i % 30 & 0x1 end r[385] = 0 -- ⑪ for i = 1, 384, 1 do -- ② if r[i] == 1 then for b = 1, 5, 1 do -- ③ if i + b > 384 then -- ④ break elseif r[i + b] == 1 then -- ⑤ local bit = r[i + b] << b local factor = r[i] + bit -- ⑥ if factor <= 31 then -- ⑦ r[i] = factor r[i + b] = 0 else factor = r[i] - bit -- ⑧ if factor < -31 then -- ⑨ break end r[i] = factor for j = i + b, 385, 1 do -- ⑩ if r[j] == 0 then r[j] = 1 break end r[j] = 0 end end end end end end return r end В данном случае я выбрал w = 5 (и при подготовке нужно будет вычислить от [3]P до [31]P). Цикл ① разбивает 384-битный скаляр k — табличку из 13 30-битных слов — на отдельные биты в r. Эта таблица r кодирует действия улучшенного второго умножения на скаляр, который мы рассматривали. Работать будет так. Проходимся справа налево по r (начиная с первого ненулевого числа) и каждый раз:
    удваиваем результат если значение x положительно, то прибавляем [x]P к результату если значение x отрицательно, то вычитаем [−x]P из результата (минус нужен, чтоб отрицательное число стало положительным)  
    После ① там каждый x — либо 0, либо 1. Поэтому следующий гигантский цикл их сгруппирует вместе для оптимизации. Работает он так.
     
    ② — проходимся по всем битам в r. Делаем это в порядке, обратном тому, как потом будем в double-and-add применять: от младшего к старшему.
    ③ — когда встречаем единицу, считываем следующие биты, пока они есть (④). Среди них интересуют только единичные (⑤).
    ⑥ — сначала я пытаюсь подтянуть этот единичный бит в r[⁠i], чтобы мы вместо двух сложений сразу прибавили предпосчитанное значение со скаляром побольше (⑦). Например, если r[⁠i] и r[i + 3] оба были равны единице, r[i + 3] я обнулю, а сложение перенесу в r[⁠i], который теперь будет равен 1 + (1 << 3) = 9: будет один прибавляться [9]P, а не два раза по P.
     
    Для b ≤ 4 условие ⑦ будет всегда выполняться, но когда дойдём до b = 5, минимальный скаляр уже будет 33, который мы не считали. Поэтому попробуем вместо этого вычитание (⑧). Если проблем не возникает (⑨), то дальше надо «скомпенсировать» в r то, что мы вычли.
     
    Например, был у нас скаляр 1011111000012 и всё то же окно w = 5. На первом же этапе мы запишем r[1] = 1 − (1 << 5) = −31. Поэтому вместо сложений будем вычитать [31]P. Но тогда и исходное число должно быть на 31 больше. Поэтому 31 = 111112 надо к скаляру прибавить.

    В результате у нас ещё одна единичка будет перенесена в старшие разряды, из-за чего единичные разряды будут обнуляться, пока не дойдём до нуля. Дальше будем уже выстраивать цепочку операций для 1100000000002.
     
    Вот в цикле ⑩ это и происходит. А так как у нас старших ненулевых бит среди 384 может не оказаться, надо предусмотреть резервный 385-й (⑪).
     
    Как-то так мы получаем цепочку операций для эффективного вычисления умножения точки на скаляр. Отмечу, что последовательность операций в цепочке зависит от скаляра, который подаётся на вход. Если он секретный, то все эти оптимизации использовать нежелательно. Но так как мы собираемся только проверять подписи, а там все данные публичны, проблемы в неконстантности не возникает.
     
    6.3. Алгоритм вычисления [⁠u]G + [v]P
    Собственно, вот сам алгоритм, с помощью которого будем вычислять [⁠u]G + [v]P:
    local g = { -- ① { 0x32760ab7, 0x295178e1, 0x355296c3, 0xbc976f, 0x142a3855, 0x1d078209, 0x39b9859f, 0x0ed8a2e9, 0x2d746e1d, 0x1c7bcc82, 0x1378eb1c, 0x08afa2c1, 0xaa87ca, }, { 0x10ea0e5f, 0x290c75f2, 0x17e819d7, 0x182c7387, 0x30b8c00a, 0x28c44ed7, 0x2147ce9d, 0x076f4a26, 0x1c29f8f4, 0x22fe4a4b, 0x06f5d9e9, 0x12a5898b, 0x3617de, }, fieldOne(), } local gWindow = groupDoScalarMultPrecomputation(g) -- ② for i, p in ipairs(gWindow) do -- ③ groupJacobianToAffine(p, p) end local function groupJacobianDoubleBaseScalarMulAdd(d, p, u, v) local pWindow = groupDoScalarMultPrecomputation(p) -- ④ local gChain = getChain(u) -- ⑤ local pChain = getChain(v) -- ⑤ groupJacobianZero(d) local i = 385 while i > 1 and gChain[i] == 0 and pChain[i] == 0 do -- ⑥ i = i - 1 end for i = i, 1, -1 do -- ⑦ groupJacobianDouble(d, d) if gChain[i] > 0 then groupJacobianMixedAdd(d, d, gWindow[1 + (gChain[i] >> 1)]) -- ⑨ elseif gChain[i] < 0 then -- ⑧ groupJacobianMixedSub(d, d, gWindow[1 + (-gChain[i] >> 1)]) -- ⑨ end if pChain[i] > 0 then groupJacobianAdd(d, d, pWindow[1 + (pChain[i] >> 1)]) elseif pChain[i] < 0 then -- ⑧ groupJacobianSub(d, d, pWindow[1 + (-pChain[i] >> 1)]) end end end ① — вне функции определяю g — координаты генератора.
    ② — здесь же делаю подготовительные вычисления (считаю [3]G, [5]G, ..., [31]G).
    ③ — для ещё большей эффективности все эти точки я перевожу в координаты (x, y, 1), для чего нужно обращать элемент Z. К счастью, проводится это лишь единожды, а результаты запоминаются. В принципе, можно сохранить результаты вычислений в файл и просто загружать оттуда, а не вычислять здесь.
    ④ — внутри функции уже выполняю подготовительные вычисления для точки P, которая заранее мне неизвестна.
    ⑤ — затем составляю цепочки операций для вычисления [⁠u]G и [v]P в отдельности.
    ⑥ — нахожу первую ненулевую операцию в какой-либо из цепочек.
    ⑦ — и от неё начиная, иду по остальным операциям с шагом −1.
    ⑧ — стоит обратить внимание, что тут 2 ветки: на > 0 и < 0. Если в цепочке записан ноль, ничего делать не нужно.
    ⑨ — благодаря упорной работе в ③ формулы для сложения (вычитания) точек можно заметно упростить. Эти формулы я реализовал в функциях groupJacobianMixedAdd и groupJacobianMixedSub по аналогии с предыдущими, поэтому останавливаться на них не буду.
     
    Сам алгоритм умножения я уже показывал. Здесь он адаптирован, чтоб работать сразу с двумя точками. Так как [2]([uʹ]G + [vʹ]P) = [2uʹ]G + [2vʹ]P, биты в результате не перемешиваются, и алгоритм будет работать, как и ожидалось. В результате получим именно [⁠u]G + [v]P, который нам и нужен.
     
    Это был последний алгоритм на эллиптических кривых, который нужен для проверки подписей в ECDSA. Поэтому можем, наконец, перейти к его реализации. А начнём с декодирования публичного ключа из байтового представления.
     
    7. Декодирование точек эллиптической кривой
    Как писал ранее, публичный ключ в ECDSA — это (x, y)-координаты точки [k]G. О том, как именно их нужно кодировать в байты, написан целый стандарт SEC 1. В общем-то, варианта два:
    Несжатое представление: пишем байт \x04, потом координату x и координату y как 48-байтовые big-endian-числа. Либо сжатое представление, в котором координата y упускается в принципе, за исключением самого младшего его бита.

    Дело в том, что, как я говорил, если (x, y) решает уравнение, то и (x, −y) тоже, то есть один x точку определяет неоднозначно. Но один из этих игреков будет чётным, а другой — нет. Собственно, именно это и показывает самый младший бит. Поэтому в сжатом представлении точка записывается так: если y чётный, пишем \x02, а если нет, то \x03; после этого дописываем координату x как 48-байтовое big-endian-число.  
    Если нам дали точку в сжатом представлении, то придётся решать уравнение y2 = x3 − 3x + b (на secp384r1 параметр a = −3). Для этого надо уметь извлекать квадратный корень по модулю — число, квадрат которого даст правую часть. Этот квадратный корень — совсем не та вещь, которая для обычных чисел. Например, у числа 2 по модулю p квадратный корень существует и равен
     
    0x83da5b0a808954ec4da354c3d9a24626426da013408406c410ecf78879b99d711354f9802677568aa327717821c98efb.

    В целом, если модуль простой, то существуют алгоритмы нахождения квадратного корня. В случае, если модуль этот ещё и даёт остаток 3 при делении на 4 (выполнено для secp384r1), то алгоритм упрощается до возведения в степень (p + 1) / 4. Правда, нужно потом результат проверить (возвести в квадрат и сравнить с исходным), потому что не у каждого числа имеется корень.
     
    На практике же часто этим не заморачиваются и используют несжатое представление. Из него мы получаем два числа: x и y. Но, вообще говоря, не факт, что они взяты с кривой, а не просто рандомные какие-то. Поэтому нужно обязательно проверить, что выполняется y2 = x3 − 3x + b. Тут уже можно просто y возвести в квадрат вычесть правую часть, никаких квадратных корней не требуется. Если получили ноль, то всё прекрасно.

    Само собою, отсутствие этой проверки — тоже неплохой такой источник рофловых дыр в безопасности, как и кривые формулы сложения.
     
    8. Арифметика по модулю n
    Самое весёлое в ECDSA — это тот момент, когда, реализовав арифметику в одном поле, ты вчитываешься в стандарт и понимаешь, что нужна ещё и в другом. Напомню кратко содержание одной из прошлых глав.
     
    На кривой secp384r1 есть такой генератор G — точка, умножение которой на разные скаляры даёт все точки кривой. По крайней мере, пока эти скаляры 0 ≤ k < n, потому что [n]G = O, и последующие скаляры начинают цикл снова. И вот по простому модулю n-то как раз арифметику ECDSA и хочет. А до этого у нас везде был p, который тоже простой, но другой.
     
    Вот они для сравнения:
    p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000fffffffd = 2³⁸⁴ - 2¹²⁸ - 2⁹⁶ + 2³² - 1 n = 0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973 = 2³⁸⁴ - 0x389cb27e0bc8d220a7e5f24db74f58851313e695333ad68d Так что да, придётся запилить ещё и операции по модулю n. Вот какие именно операции нужны в ECDSA для проверки подписи:
    вычитание умножение возведение в квадрат обращение по модулю  
    Так как модуль n в длину такой же, как и p, — 384-битный, то резать его будем так же: тринадцатью словами по 30 бит. Благодаря этому алгоритмы в большей части остаются те же, надо только поменять, как именно мы будем сокращать результаты по модулю n. Потому что в данном случае уже будет выполняться другое равенство:
     
    2384 = 0x389cb27e0bc8d220a7e5f24db74f58851313e695333ad68d.
     
    Эту колбасу порежем на 30-битные куски:
     
    2384 = 0x389 × 2180 + 0x32c9f82f × 2150 + 0x8d220a7 × 2120 + 0x397c936d × 290 + 0x34f58851 × 260 + 0xc4f9a54 × 230 + 0x333ad68d.
     
    Тогда, например, scalarSub, который производит вычитание, выглядеть станет уже так:
    -- "order right-shifted by 9" local orderrs9 = { 0x0a52e600, 0x20cb5666, 0x14ef5d9d, 0x06d92458, 0x1bbeb034, 0x2c0fa1b9, 0x3ff8ec69, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x1ffffffff, } local function scalarSub(c, a, b) local carry = 0 for i = 1, 12, 1 do local word = a[i] - b[i] + orderrs9[i] + carry c[i] = word & 0x3fffffff carry = word >> 30 carry = carry | -(carry & 1 << 63 >> 30) end local word = a[13] - b[13] + orderrs9[13] + carry c[13] = word & 0xffffff carry = word >> 24 c[1] = c[1] + carry * 0x333ad68d c[2] = c[2] + carry * 0xc4f9a54 c[3] = c[3] + carry * 0x34f58851 c[4] = c[4] + carry * 0x397c936d c[5] = c[5] + carry * 0x8d220a7 c[6] = c[6] + carry * 0x32c9f82f c[7] = c[7] + carry * 0x389 carry = 0 for i = 1, 13, 1 do local word = c[i] + carry c[i] = word & 0x3fffffff carry = word >> 30 end end Тут ещё можно заметить, что последний цикл не делает знакового расширения, потому что мы не производим вычитания при сокращении по модулю.
     
    Эти огромные куски приносят дварф-фортрессовское веселье при реализации умножения, когда мы избавляемся от старших 13 слов. Дело в том, что если мы сразу все 13 старших слов сократим в одном цикле, то промежуточные результаты вычислений могут легко переполниться, из-за чего алгоритм насчитает какую-то чепуху. Поэтому приходится посередине операции останавливаться на то, чтобы перенести старшие биты в следующие слова, после чего снова возвращаться к сокращению. Получается вот так:
    local i = 26 repeat d[i - 7] = d[i - 7] + carry * 0xe272 -- ① d[i - 8] = d[i - 8] + carry * 0x327e0bc8 d[i - 9] = d[i - 9] + carry * 0x348829f9 d[i - 10] = d[i - 10] + carry * 0x1f24db74 d[i - 11] = d[i - 11] + carry * 0x3d62144c d[i - 12] = d[i - 12] + carry * 0x13e69533 d[i - 13] = d[i - 13] + carry * 0xeb5a340 i = i - 1 carry = d[i] until i == 19 carry = 0 for i = 20 - 13, 19, 1 do local word = d[i] + carry d[i] = word & 0x3fffffff carry = word >> 30 end d[20] = carry i = 20 repeat d[i - 7] = d[i - 7] + carry * 0xe272 -- ① d[i - 8] = d[i - 8] + carry * 0x327e0bc8 d[i - 9] = d[i - 9] + carry * 0x348829f9 d[i - 10] = d[i - 10] + carry * 0x1f24db74 d[i - 11] = d[i - 11] + carry * 0x3d62144c d[i - 12] = d[i - 12] + carry * 0x13e69533 d[i - 13] = d[i - 13] + carry * 0xeb5a340 i = i - 1 carry = d[i] until i == 13 ① — это n, сдвинутый влево на 6 бит. Мы аналогично поступали и с p.
     
    Почему останавливаться надо именно на девятнадцатом слове? Ну, на самом деле, взято это с потолка (как номер посередине между 13 и 26). Спустя год после того, как я этот код написал, я запилил скрипт для Z3, который вычисляет всё то же. Если я не накосячил в нём, то контрпримера, когда бы промежуточные результаты снова переполнились, он найти не смог. Так что должно работать.
     
    И, разумеется, в функции вычисления квадрата числа тоже нужно таким образом переделать сокращение по модулю. Ctrl+C, Ctrl+V.
     
    Содержание функции scalarInvert, как и в прошлый раз, генерируется тулзой addchain. Цепочка операций, правда, получается совсем другой, потому что и степень поменялась с p − 2 на n − 2. Получается вот так.
    local function scalarRepeatedSq(b, a, n) scalarSq(b, a) for i = 2, n, 1 do scalarSq(b, b) end end local function scalarInvert(b, a) local t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11 = {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {} scalarSq(t4, a) scalarMul(t2, a, t4) scalarMul(t1, t4, t2) scalarMul(t3, t4, t1) scalarMul(t5, t4, t3) scalarMul(b, t4, t5) scalarMul(t6, t4, b) scalarMul(t4, t4, t6) scalarSq(t7, t4) scalarMul(t7, a, t7) scalarSq(t9, t7) scalarSq(t9, t9) scalarSq(t10, t9) scalarSq(t8, t10) scalarRepeatedSq(t11, t8, 5) scalarMul(t8, t8, t11) scalarRepeatedSq(t11, t8, 10) scalarMul(t8, t8, t11) scalarRepeatedSq(t11, t8, 4) scalarMul(t10, t10, t11) scalarRepeatedSq(t10, t10, 21) scalarMul(t8, t8, t10) scalarRepeatedSq(t10, t8, 3) scalarMul(t9, t9, t10) scalarRepeatedSq(t9, t9, 47) scalarMul(t8, t8, t9) scalarRepeatedSq(t9, t8, 95) scalarMul(t8, t8, t9) scalarMul(t8, t4, t8) scalarRepeatedSq(t8, t8, 6) scalarMul(t8, t3, t8) scalarRepeatedSq(t8, t8, 3) scalarMul(t8, t2, t8) scalarRepeatedSq(t8, t8, 7) scalarMul(t8, t6, t8) scalarRepeatedSq(t8, t8, 6) scalarMul(t8, t6, t8) scalarSq(t8, t8) scalarMul(t8, a, t8) scalarRepeatedSq(t8, t8, 11) scalarMul(t8, t7, t8) scalarSq(t8, t8) scalarSq(t8, t8) scalarMul(t8, a, t8) scalarRepeatedSq(t8, t8, 8) scalarMul(t8, t6, t8) scalarSq(t8, t8) scalarSq(t8, t8) scalarMul(t8, t2, t8) scalarRepeatedSq(t8, t8, 6) scalarMul(t8, b, t8) scalarRepeatedSq(t8, t8, 4) scalarMul(t8, t3, t8) scalarRepeatedSq(t8, t8, 6) scalarMul(t7, t7, t8) scalarRepeatedSq(t7, t7, 5) scalarMul(t7, b, t7) scalarRepeatedSq(t7, t7, 10) scalarMul(t7, t6, t7) scalarRepeatedSq(t7, t7, 9) scalarMul(t6, t6, t7) scalarRepeatedSq(t6, t6, 4) scalarMul(t6, b, t6) scalarRepeatedSq(t6, t6, 6) scalarMul(t5, t5, t6) scalarRepeatedSq(t5, t5, 3) scalarMul(t5, a, t5) scalarRepeatedSq(t5, t5, 7) scalarMul(t5, b, t5) scalarRepeatedSq(t5, t5, 7) scalarMul(t5, t1, t5) scalarRepeatedSq(t5, t5, 5) scalarMul(t5, t3, t5) scalarRepeatedSq(t5, t5, 5) scalarMul(t4, t4, t5) scalarRepeatedSq(t4, t4, 5) scalarMul(t4, b, t4) scalarRepeatedSq(t4, t4, 4) scalarMul(t4, b, t4) scalarRepeatedSq(t4, t4, 5) scalarMul(t3, t3, t4) scalarRepeatedSq(t3, t3, 3) scalarMul(t3, t2, t3) scalarRepeatedSq(t3, t3, 7) scalarMul(t3, t2, t3) scalarRepeatedSq(t3, t3, 6) scalarMul(t3, b, t3) scalarRepeatedSq(t3, t3, 4) scalarMul(t3, t1, t3) scalarRepeatedSq(t3, t3, 3) scalarMul(t3, t2, t3) scalarRepeatedSq(t3, t3, 4) scalarMul(t3, t2, t3) scalarRepeatedSq(t3, t3, 4) scalarMul(t2, t2, t3) scalarRepeatedSq(t2, t2, 6) scalarMul(t2, t1, t2) scalarRepeatedSq(t2, t2, 5) scalarMul(t1, t1, t2) scalarRepeatedSq(t1, t1, 6) scalarMul(b, b, t1) scalarSq(b, b) scalarMul(b, a, b) scalarRepeatedSq(b, b, 4) scalarMul(b, a, b) end Чтоб проверить, что в лапше этой я не накосячил, написал на питоне скриптик, который её парсит и символически производит те же операции. А потом сравнил степень, в которую функция возводит фактически, с ожидаемой. В общем, она совпадает, так что за счёт 11 временных переменных мы получаем правильный результат.
     
    Вот так быстренько пробежались по операциям в поле скаляров. Теперь-то точно всё, что для сверки подписей в ECDSA требовалось, у нас наконец-то имеется.
     
    9. Проверка подписей ECDSA
    Что, вообще, такое подпись и где там эллиптические кривые? Подпись ECDSA — это просто пара чисел, которые названы прозрачно понятными именами в лучших традициях математики — r и s. Сначала посмотрим, как они получаются:
    Пусть d — приватный ключ (рандомное число от 1 до n − 1), а Q = [d]G — публичный. Генерируем рандомное число k от 1 до n − 1. Вычисляем R = [k]G и разбираем её на координаты R.x и R.y. Затем высчитываем r = R.x % n — это нужно потому, что R.x был по модулю p, а нужен он по модулю n. Наконец, s = k −1(h + rd) % n, где h — это 384-битный хэш сообщения, вычисленный при помощи SHA-384, распаршенный как big-endian-число, взятое по модулю n. Если r или s оказался нулевым, возвращаемся на шаг 2.  
    Проверяются подписи потом по такому алгоритму:
    Проверяем, что 0 < r < n, 0 < s < n, а также валидность публичного ключа. Считаем хэш SHA-384 от сообщения и 48-байтовый результат декодируем как скаляр h (сокращённый по модулю n). Вычисляем u = hs −1 % n, v = rs −1 % n. Находим R = [⁠u]G + [v]Q. Убеждаемся, что R — это не точка на бесконечности, и расщепляем по координатам R.x и R.y. Наконец, чекаем, что R.x % n = r.  
    Если какая-либо из проверок не удалась, подпись признаётся невалидной. Проверки на r, s и R нужны, чтобы мы не пытались проверять нулевую подпись: без проверки такая подпись «действительна» для любого сообщения. И, само собою разумеется, есть люди, которые забывают про все три этих проверки.
     
    Как видно, алгоритмы эти — просто какие-то числодробилки. На самом деле даже вдаваться в суть преобразований необязательно, чтобы реализовать. Так как все функции, которые в алгоритме проверки подписей юзаются, мы, разлившись на восемь тысяч слов, написали, остаётся их только собрать воедино:
    function lib.ecdsaVerifyDecoded(message, hash, r, s, q) if scalarCanonicalFlag(r) == 0 or scalarCanonicalFlag(s) == 0 then -- ① return nil, "invalid signature" end if scalarIsZero(r) or scalarIsZero(s) then return nil, "invalid signature" end local messageHash = hash():update(message):finish():sub(1, 48) local e = scalarFromBytes(messageHash) -- ③ local sInv = {} scalarInvert(sInv, s) local u, v = {}, {} scalarMul(u, e, sInv) scalarReduceQuick(u, u) scalarMul(v, r, sInv) scalarReduceQuick(v, v) local p = groupJacobianZero() groupJacobianDoubleBaseScalarMulAdd(p, q, u, v) if groupJacobianZeroFlag(p) == 1 then return nil, "invalid signature" end groupJacobianToAffine(p, p) -- ② fieldReduceQuick(p[1], p[1]) -- r minus x local rmx = {} scalarSub(rmx, r, p[1]) if not scalarIsZero(rmx) then return nil, "invalid signature" end return true end ① — функции scalarCanonicalFlag просто проверяют, находится ли число в диапазоне от 0 до n − 1. Как это делать, я показывал ранее вместе с реализацией fieldReduceQuick.
    ② — не забываем, что точки все у нас представлены координатами (X, Y, Z), а нужны (x, y). Это единственное место, где нужно инвертировать Z.
     
    Тут ещё есть одна функция, отмеченная ③, которая загружает скаляр из 48-байтной строки в табличку. Выглядит она так:
    local function scalarFromBytes(s) local a13 = (">I3"):unpack(s, 1) local a12 = (">I4"):unpack(s, 4) >> 2 local a11hi = (">I2"):unpack(s, 7) & (1 << 10) - 1 local a11lo = (">I3"):unpack(s, 9) >> 4 local a10 = (">I5"):unpack(s, 11) >> 6 & 0x3fffffff local a9hi = (">I2"):unpack(s, 15) & (1 << 14) - 1 local a9lo = (">I2"):unpack(s, 17) local a8 = (">I4"):unpack(s, 19) >> 2 local a7hi = (">I3"):unpack(s, 22) & (1 << 18) - 1 local a7lo = (">I2"):unpack(s, 25) >> 4 local a6 = (">I5"):unpack(s, 26) >> 6 & 0x3fffffff local a5hi = (">I3"):unpack(s, 30) & (1 << 22) - 1 local a5lo = (">I1"):unpack(s, 33) local a4 = (">I4"):unpack(s, 34) >> 2 local a3hi = (">I4"):unpack(s, 37) & (1 << 26) - 1 local a3lo = (">I1"):unpack(s, 41) >> 4 local a2 = (">I5"):unpack(s, 41) >> 6 & 0x3fffffff local a1 = (">I4"):unpack(s, 45) & 0x3fffffff return { a1, a2, a3hi << 4 | a3lo, a4, a5hi << 8 | a5lo, a6, a7hi << 12 | a7lo, a8, a9hi << 16 | a9lo, a10, a11hi << 20 | a11lo, a12, a13, } end Тут не сказать чтобы дикая магия творится. Просто раскрыл блокнот, нарисовал там 48-байтный прямоугольник, разбил на куски по 30 бит, посчитал смещения и выразил свои чувства в коде.
     
    Кстати, о чувствах.
     
    10. Декодирование подписей
    Подпись — это пара 384-битных чисел r и s. Как представить их в байтах? Если у вас всё в порядке с головой, вы, наверное, просто бы закодировали r (в little-endian или big-endian) как 48-байтовую строку, затем приклеили бы так же кодированный s и получили вполне человеческую запись на 96 байт. Кодировать в одну сторону тривиально, в другую ошибиться при декодировании практически негде — мир да согласие.
     
    Но, конечно же, дыр в реализациях ECDSA разработчикам алгоритма показалось слишком мало, и вместо этого подписи кодируются при помощи такого изысканного деликатеса, как ASN.1. Это... ну, я бы назвал это JSON-ом или XML, какими бы они были, если бы их спроектировал большой неповоротливый комитет в 1984 году.
     
    Правда, ASN.1 расшифровывается как abstract syntax notation (one), то есть нотация в абстрактном синтаксисе, что, скажем так, само себе не самое оригинальное имя. Означает оно то, что как именно кодировать (и декодировать) значения, ASN.1 не определяет. Он только даёт язык описания схемы (как XSD), в которой наша подпись выглядит вот так:
    ECDSA-Sig-Value ::= SEQUENCE { r INTEGER, s INTEGER } Все эти ключевые слова капсом и пучки укропа (::=) вместо человеческих равенств — настоявшиеся пряности, волнующие язык.
     
    Кодировать эту субстанцию можно в куче разных форматов, включая даже XML и JSON. В мобильной связи, слышал, ASN.1, как майонез, заливают во все дыры и протоколы, и JSON-кодирование ASN.1-схем разработчиков софта радует каждый раз, когда им приходится с этим сталкиваться. Меня пока жизнь уберегла от таких психических травм, к великому счастью.
     
    В криптографии применяется формат DER. В двух местах: в сертификатах и вот этих самых подписях. Так как рисовал формат DER тот самый неповоротливый комитет, который предусмотрел футганы на все случаи жизни, читать стандарт и реализовывать его — утончённое удовольствие для истинных гурманов.
     
    Так что знакомьтесь — я гурман. DER-декодер реализовывал на Lua дважды. Для сертификатов в первую очередь, но здесь вот, в ECDSA, тоже пригодилось. В принципе, ничего не мешает сделать функцию, которая декодирует чисто эту структуру в формате DER, но раз уж у меня был декодер готовый, то его и заюзал.
     
    Были и другие гурманы. На багах в декодере DER проверяльщики подписей тоже сыпались...
     
    11. Тестирование
    Как понять, что 2 тысячи строчек кода, которые я написал, делают ровно то, что написано, если код почти весь состоит из неочевидных числопревращений? Тестировать такие низкоуровневые вещи всегда дико весело. К счастью, нам сильно повезло с предметной областью.

    Если бы такие же числодробили считали какую-то математическую (физическую) модель, как это отлаживать, я не сильно представляю. В криптографии же это достаточно просто. Во-первых, если где-то накосячить, то почти наверняка результат не сойдётся с ожидаемым. Во-вторых, все вычисления детерминистичны. В-третьих, алгоритмы стандартизованы, и имеется куча имплементаций, с которыми можно сравниваться.
     
    Прежде всего я запилил реализацию операций на эллиптической кривой на Python. В отличие от Lua, в языке Python числа могут быть произвольной длины, и напрямую работать с 384 битами там не представляет никаких трудностей. С помощью неё нагенерил несколько тестовых примеров, с которыми мог сравнивать код на Lua.
     
    Также у корпорации Google на GitHub завалялся один такой большой репозиторий. Там куча JSON-файлов с тестовыми примерами для самых разных криптографических алгоритмов. Достаточно просто распарсить JSON и заюзать данные в своих тестах.
     
    Кроме того, авторы криптографических алгоритмов часто описание самого алгоритма снабжают тестовыми векторами — примерами получаемых результатов при конкретных входных данных. Это те же тестовые данные, по сути. ECDSA не исключение, и тестовые векторы из стандарта тоже проверяю в своих тестах.
     
    Для ряда операций применял более изощрённые методы. Например, когда показывал scalarInvert, я упоминал, что корректность цепочки проверил, её проинтерпретировав символически скриптом на Python. Слова-то сложные, но по сути я просто спарсил регексами кусок кода, который обращал скаляр, и проследил за изменениями экспонент на каждой производимой операции.
     
    Наконец, термоядерный вариант — формальная верификация программ. Формальные методы грубо можно поделить на две группы, которые я назову так: автоматические и ручные. В автоматических формулируется, что именно доказывается, а система потом определяет, верно ли доказываемое утверждение или нет (ищется контрпример). В ручных системах доказательство нужно писать самому, а система лишь проверяет, что доказательство не нарушает логических правил.
     
    Опыт использования последних у меня уже был. Как-то, например, корректность программы на 12 строчек доказывал — определение условия корректности и его доказательство на языке Coq (сейчас он как-то иначе называется) потребовало почти в 100 раз больше строк кода, и он не то чтобы вышел сильно читабельным. Отчасти потому, что в этих вещах я несколько нуб всё ещё, но и в целом что-то объёмное так доказывать — титанический труд.
     
    А вот с автоматическими системами именно для доказательства корректности своих программ сталкиваться не приходилось. Поэтому для проверки, что в scalarMul никакие промежуточные результаты не переполняют 64-битные числа, попробовал реализовать скрипт на Python для SMT-решателя Z3. Условия корректности я там, правда, в полуручном режиме сгенерировал, но всё равно, когда спустя 2.5 часа Z3 написал, что контрпример не существует, было такое стойкое ощущение магии. Крутая вещь, короче говоря.
     
    Так что могу сказать, что код в статье, или по крайней мере в libtls13, делает примерно то, чего от него и требуется.
     
    12. Завершение сеанса
    Пакет libtls13 можно скачать с oppm. Вот ссылка на пакет. А вот на сам файл с реализацией ECDSA.
     
    Статья изначально была написана в поджатом изложении на английском языке год назад (но не опубликована), и стена текста выше — это её расширенный перевод.
     
    Аддендум 1. Зачем всё это
    Если вы не разделяете моих интересов в математическую сторону вопроса и ориентированы на результат («хочу запилить ECDSA»), большое количество математики может вызвать вопросы, неужели она там действительна нужна в таком объёме. Поэтому решил добавить к статье ещё перечень глав с описанием, зачем я их написал.
    §1: эллиптические кривые. Глава определяет уравнение эллиптической кривой и точки на них. Представление точки как пары координат нужно, чтобы было понятно, как устроен приватный ключ (§6), и для реализации операций на кривой (§5). Уравнение нужно, чтобы проверить (§7), что публичный ключ валидный, а не просто рандомная пара чисел. §2: кольца и поля. Глава знакомит с арифметикой по модулю, операциями сложения, умножения и деления, а также объясняет, почему модуль берётся именно простой. Понятие кольца поясняет, почему я могу без опаски манипулировать уравнениями при сложении точек (§5.2). Понятие поля позволяет переиспользовать формулы для вычисления суммы точек кривой (§3), используется для обращения элементов по модулю (§4.6), а отсутствие делителей нуля в нём — критичный факт, на который опирается доказательство корректности алгоритма сложения точек (§5.2). §3: группа эллиптической кривой. Глава определяет две базовые операции на эллиптической кривой: сложение точек и взятие противоположного элемента. Также показывает, почему сложение устроено так необычно. Наконец, вводит нейтральный элемент (нуль) — точку на бесконечности. То, что нуль — это бесконечность, применяется при реализации кривой (§5.1). Алгоритм проверки подписей требует проверки точек (публичного ключа и результата вычислений) на нуль (§9). Сложение точек в алгоритме ECDSA повторяется многократно (§9) — это основная вещь, из-за которой подпись нельзя подделать. Сложность формулы сложения обосновывает выбор альтернативного представления точек в реализации (§5). Взятие противоположной точки используется для реализации вычитания (§5.4). Элементы теории групп (порядок, цикличность) вводятся при описании, почему приватный ключ и публичный ключ именно такие (§6). §4: арифметика в полях. Глава описывает представление элементов поля в Lua, показывает модуль p и параметры кривой a, b. Вид модуля используется во всех операциях для сокращения результатов по модулю (§4.1–§4.6). Значение параметров нужно для проверки публичного ключа (§7). Представление очевидным образом юзается в подглавах (§4.1–§4.6), а также переиспользуется при реализации другого поля (§8). Вся глава нужна для реализации операций на эллиптической кривой (§5). §4.1: нейтральные элементы. Подглава показывает устройство нуля и единицы. Также приводится принцип возврата результата вычислений. Очевидным образом юзается в последующих подглавах (§4.2–§4.6). Нуль и единица в поле нужны для определения нуля на кривой (§5.1). §4.2: сложение. Подглава показывает, как складывать большие числа по большому модулю p. Описывает технику сложения с переносом, сокращение результата по модулю и реализацию знакового расширения на Lua. Сложение в поле применяется при сложении точек кривой (§5.2) и удвоения (§5.3). С небольшими изменениями тот же алгоритм используется для умножения на 30-битное слово (§5.2, §5.3) и вычитании (§4.3). Сокращение по модулю — финальная часть других операций в поле (§4.3–§4.5). §4.3: вычитание. Подглава описывает алгоритм вычитания по модулю, который даёт неотрицательный результат. Как и сложение, используется в формулах для сложения (§5.2) и удвоения (§5.3) точек. Также нужно для вычитания точек, чтобы инвертировать знак у координаты y (§5.4). Аналогичный алгоритм применяется для вычисления по модулю n (§8). §4.4: умножение. Подглава рассказывает об альтернативном представлении умножения «в столбик», вводит операцию свёртки и показывает, как она совмещается с модульной редукцией для вычисления умножения двух чисел по модулю p. Используется при обращении чисел по модулю (§4.6). Этот же алгоритм специализируется для случая a = b, чтобы получить алгоритм возведения в квадрат по модулю (§4.5). Применяется в формулах сложения (§5.2) и удвоения (§5.3) точек. Сложность умножения обосновывает выбор формул. Усложнение для модуля n описывается в §8. §4.5: возведение в квадрат. Подглава описывает видоизменённый алгоритм умножения, чтобы вычислять квадрат числа по модулю. Нужен, чтобы остальные операции (§4.6, §5.2, §5.3) работали заметно быстрее. Применяется в формулах сложения (§5.2) и удвоения (§5.3) точек. Аналогичный алгоритм применяется для вычисления по модулю n (§8). §4.6: обращение чисел. Подглава показывает, как с помощью малой теоремы Ферма обратить элемент по модулю p. Впервые упоминается инструмент addchain, с помощью которого аналогичная операция проделывается по модулю n (§8). Обращение нужно для деления чисел по модулю (§5). Непомерная сложность алгоритма обращения обосновывает выбор альтернативного представления точек на кривой (§5). В этом представлении обращение — финальная операция при вычислении [⁠u]G + [v]Q, которое встречается в алгоритме проверки подписи (§9). §5: реализация операций на эллиптической кривой. Глава вводит более эффективное представление точек на кривой и описывает, как перейти к нему из обычного представления в виде пары (x, y) и обратно. Представление нужно, чтобы операции сложения (§5.2) и удвоения (§5.3) работали гораздо быстрее. Также это представление позволяет выразить точку на бесконечности (§5.1). Описание перехода в обычные координаты используется для ускорения (§6.3) алгоритма вычисления [⁠u]G + [v]Q, применяющегося в ECDSA (§9). §5.1: нейтральный элемент. Подглава описывает устройство точки на бесконечности, а также показывает, как точка хранится в памяти программы. Сравнение с нейтральным элементом — это одна из проверок, которые необходимо выполнить в ECDSA для результата вычислений (§9), и защищает от подделки подписи. Вид нейтрального элемента (нулевая координата Z) используется для составления полного алгоритма сложения точек и доказательства его корректности (§5.2). Представление очевидным образом используется во всём последующем коде. §5.2: сложение точек. Подглава описывает ключевую операцию в эллиптической криптографии — сложение точек, показывает необходимость отдельной формулы удвоения. Сложение в ECDSA повторяется многократно (§9), чему посвящена вся глава §6. Неправильный результат, выдаваемый формулой для сложения точки с самой собой, требует реализации отдельной формулы удвоения (§5.3). В главе также определяется функция fieldReduceQuick, которая применяется в ECDSA для полного сокращения координаты точки-результата по модулю p (§9). На её основе же сделана функция scalarCanonicalFlag, реализующая первую проверку алгоритма ECDSA (§9). §5.3: удвоение точек. Подглава приводит алгоритм вычисления удвоения точки кривой. Необходимо для корректной работы сложения точек (§5.2). Благодаря дешевизне в сравнении со сложением применяется в алгоритме многократного сложения (§6, в частности §6.3). §5.4: вычитание точек. Подглава показывает, как с помощью сложения реализовать вычитание точек кривой. Применяется для ускорения работы многократного сложения (§6.1–§6.3). §6: умножение на скаляр. Приватные ключи. Глава вводит элементы теории групп: понятие порядка, генератора. Вводится обозначение [k]P для многократного сложения (умножения на скаляр) точки кривой. Определяется число n. Описывается устройство приватных и публичных ключей, а также неявно формулируется задача дискретного логарифмирования. Глава показывает, зачем в принципе в криптографии применяются эллиптические кривые. Устройство публичного ключа используется для его декодирования из байтового представления (§7). В главе описывается, почему вычисления в ECDSA производятся именно по модулю n, а не p. Само значение n определяется при реализации поля вычетов по этому модулю (§8). Умножение на скаляр — единственная операция на эллиптической кривой, явно используемая в ECDSA (§9). §6.1: алгоритмы умножения на скаляр. Подглава описывает алгоритм double-and-add и его модификацию. Без этих алгоритмов время работы ECDSA бы выражалось экзотическими числами с сотней знаков в десятичной записи. На модификации алгоритма основывается фактически реализованный алгоритм для вычисления [⁠u]G + [v]Q (§6.3). Принцип работы алгоритмов необходимо знать, чтобы понимать, что вообще происходит при генерации цепи сложений-вычитаний (§6.2). §6.2: генерация цепи сложений-вычитаний. Подглава приводит алгоритм генерации цепи операций для умножения точки на большой скаляр. Используется в конечном алгоритме для вычисления [⁠u]G + [v]Q (§6.3). Позволяет ещё сильнее ускорить этот алгоритм. §6.3: алгоритм вычисления [⁠u]G + [v]Q. Подглава показывает, каким образом выполняется операция на эллиптической кривой, используемая в ECDSA для проверки подписи. Используется в ECDSA для проверки подписи (§9). §7: декодирование точек эллиптической кривой. Глава описывает два формата представления точки в байтах и рассказывает о взятии квадратного корня по модулю. Точка — это публичный ключ. Собственно, программе обычно он поступает в байтовом массиве, поэтому необходимо сначала декодировать, чтобы что-то можно было с ним делать, например проверять подписи. Также в главе описываются важнейшие проверки, которые следует сделать имплементации для публичного ключа, используемого в ECDSA (§9). Проверка публичных ключей обязательна в алгоритме обмена ключами ECDH. Отсутствие может привести к компрометации секретных данных (invalid curve attack). §8: арифметика по модулю n. Глава описывает модификацию алгоритмов из §4 для вычисления по модулю n. В частности, описывается, как производить сокращение по модулю и обращение элементов. Вычитание, умножение и обращение по модулю используются непосредственно в ECDSA (§9). Обращение по модулю использует функцию возведения в квадрат для ускорения работы. §9: проверка подписей ECDSA. Глава приводит реализацию алгоритма проверки подписи ECDSA на Lua. Также она содержит функцию преобразования 48-байтового массива в представление скаляра в виде 13 30-битных слов. Собственно, ради этого вся статья и писалась. ECDSA используется, чтобы убедиться в подлинности сообщения или документа. В частности, алгоритм цифровой подписи — одна из составляющих TLS. Цифровая подпись на основе ECDSA применяется в правительстве США. Схожий с ECDSA алгоритм используется и в России. §10: декодирование подписей. Глава вводит форматы ASN.1 и DER, с помощью которых кодируется подпись. Чтобы подпись, поступившую как набор байт, вообще можно было проверить, её надо декодировать из этих арканных форматов данных. §11: тестирование. Глава приводит список методов тестирования, с помощью которых обеспечивается корректность реализации криптографических алгоритмов. Безопасность основывается на корректности этих алгоритмов. Если в них бага, то либо сервис будет отвергать корректные данные, либо, что ещё хуже, принимать некорректные. Последнее может привести к компрометации всего сервиса. §12: завершение сеанса. Глава заключительная, приводит ссылки на полную реализацию. Небольшая часть функций, в ней используемых, в статье не описаны или описаны лишь вкратце. По ссылке при желании можно ознакомиться с полным кодом программы, скриптами, тестами.
  14. Fingercomp

    Обновление OpenComputers 1.7.1

    Автор: Fingercomp,

    Багофиксы, в основном только они. Вот из того, что добавилось:
    У планшетов можно получать полноценное направление взгляда игрока. Количество максимальных частей пакета добавлено в информацию об устройстве (та, что computer.getDeviceInfo(). [1.10.2] Интеграция с ExtraCells и Mekanism. [1.12.2] Интеграция с ComputerCraft.

    Остальное:
    Изменили рецепт алмазных кусков по умолчанию. Пофиксили область видимости датчика движения. Планшетам разрешили отрубать экран. Дроны адекватно заставили воспринимать чанклодырное улучшение. Item conduits из EnderIO чего-то из микроконтроллеров доставали ненужного. Несовместимость с IC2 Classic устранена. В IRC-клиенте с дискеты пофиксили CTCP. [1.11.2] Какая-то бага с добавлением предметов в улучшение-БД. [1.11.2] И ещё бага с доступом к компонентам вроде дисковода в планшетах.

    Обновления в OpenOS:
    Нет необходимости теперь, в кои-то веки, писать = в начале строк в интерпретаторе Lua. Оно автоматически возвращает. Можно в error пихать таблицы, и крашиться не должно. Наконец-то разрешили монтировать системы файловые в существующие директории. Ещё можно примонтировать директорию в другое место. Если вы напишете одну команду и 10 раз другую, то в истории последняя будет только один раз. Не придётся 10 раз тыкать "вверх", чтобы первую команду получить. Фиксили проблемы с загрузкой OpenOS на медленных хостах. Я думаю, это ошибка TLWY, которая при старте кидалась. .shrc может принимать ввод. Пофиксили поиск названия клавиши по коду в либе keyboard. Фикс event.cancel и event.ignore какой-то. Интерпретатор теперь здраво воспринимает ошибки переполнения памяти в сериализаторе. Какой-то TLWY в /bin/tree.lua. Улучшения в vt100 всякие. Код стал ещё уродливее ради уменьшения потребления памяти. Вот такие улучшения.

    Вот как-то так. Отсюда качабельно.
  15. Fingercomp
    Он вышел раньше, чем я предполагал — ниже список нового.
    Сила овец и оцелотов в их пушистости. Теперь пушистость можно приложить к делу и питать компы — с помощью ковровых конденсаторов. От обычных конденсаторов они толком не отличаются, но могут генерировать энергию, если по ним ходят минимум 2 пушистых животных: овцы или оцелоты, которые генерируют больше энергии. Все новые процессоры, которые будут скрафчены, будут с Lua 5.3 по умолчанию. Сменить можно так же — шифт-пкм. К беспроводной карточке, которую мы все знали, теперь добавили урезанную версию T1, тоже беспроводную. Она может открывать только 1 порт и стрелять сигналом на 16 блоков, а не 400. Креативная компонентная шина (штука, пихабельная в серверы), которая добавляет 1024 компонента. Логичное дополнение. Роботов можно подключать к компьютерам как компоненты. И менять имя роботов: то, что раньше делалось в наковальне, теперь можно через setName и getName. Робот должен быть выключен, чтобы функции работали. Починены всякие проблемки с рендерингом всяких символов. Блоки-инвентари иногда не сохраняли содержимое при сохранении мира. Дроны с чанклодырями не всегда грузили чанки. Пофикшена интеграция с AE2. computer.addUser неправильно отдавал ошибку как-то. Хитбоксы у кабелей теперь обтягивают их форму. Раньше кабели-пересечения были с хитбоксом на весь блок. Апгрейд крафта не всегда крафтил, когда должен был. Апгрейд крафта крафтил один предмет и ломал рецепт — для всех, в том числе игроков. Весело. Датчик движения как-то коряво работал. Пофикшена работа роботов с предметами-инвентарями вроде жидкостных ячеек IC2. Устранена возможная утечка памяти в сетевом коде. В MC 1.10+: пофикшена getMetadata у дебаг-карты. В MC 1.10+: добавлена getBlockstate для дебаг-карты. В MC 1.12: нельзя было заменить EEPROM дрону. В MC 1.7.10: добавлены getAllStacks и inventoryName для транспозеров с инвентарных апгрейдов. Обновлён французский перевод. В OpenOS: Обновлён install.lua, чтобы работал более предсказуемо. uuid.lua возвращает правильные UUID 4 версии, как в RFC написано. Фиксы всякие поддержки vt100. Утечка памяти при загрузке процессов (есть и такая, даже в Луа). Более конкретные комбинации клавиш: Ctrl+Alt+Delete не будет считаться за Ctrl+Delete, например.



    Вайтлиста измерений для чанклоадера... ну, их пока нет.
     
    Скачать.
  16. Fingercomp
    Предлагаю поглядеть на новое обновление мода. Очень толстого обновления.
    Отрегулировали частоту выполнения хука, который шлёт этот ненавистный "too long without yielding", так что теперь и скорость исполнения кода должна гораздо возрасти, и с ошибкой этой код падать реже. Мы проверяли: некая гуи-либа с 1.6 fps до 2.5 fps только благодаря этому работать стала. Оптимизировали производительность ещё и записи на диск. Пошустрее будет — обещают, что в 5–500 раз. Сетевой разделитель (сплиттер) стал компонентом. Можно программно теперь отключать куски сети. Жёсткие диски стало возможным делать Read-Only. Компьютеры CC могут читать сигналы бандлед-редстоуна OC. И наоборот. Функции [il]debug.getlocal[/il] и [il]debug.getupvalue[/il]: возвращают они лишь только имя переменной, но не значение её. И мне кажется, что это уже давно было завезено. Геолайзеры получили методы [il]isSunVisible[/il], [il]canSeeSky[/il] и [il]detect[/il]. Неплохо. В [il]computer.beep[/il] можно писать морзянку. [il]computer.beep("---.---")[/il]. [il]redstone.setOutput[/il] научился ставить значения больше 15. Клавиатуру можно цеплять к монитору, если ещё поставить к непередней стороне блока. Наконец-то. [1.12] Вернули поддержку Project Red. Через адаптер можно теперь работать с камерой реактора IC2. У серверных дисководов тоже есть теперь гуишка (пкм в мире или внутри интерфейса стойки). Торговый апгрейд обзавёлся методом [il]getMerchantId[/il]. Полезно, если жителей куча. [1.12] Вернули поддержку энергии AE2. В конце-то концов: дебаг-карте добавили [il]scanContentsAt[/il]. Больше инфы возвращается для предметов из Draconic Evolution. Вейпоинты стало можно ставить вверх или вниз. Связанные карты можно крафтить вместе (повяжет на новый канал их). Плюс получать адрес канала при сканировании стэка. Можно теперь менять цветовой код сундуков Ender Storage. Связанные карты также научились будить компьютер по сигналу, как модемы. Белый и чёрный списки измерений для чанклоадера. Метод [il]disk_drive.media[/il], которым можно получить адрес дискеты внутри дисковода. Поддержка Forge Energy для зарядки предметов вроде батареек и планшетов. Анализатор показывать будет по клику на адаптер ещё и содержащийся в нём компонент. Событие [il]redstone_changed[/il] показывает, какой цвет поменялся на бандлед-кабеле. По шифт-клику компоненты закидываются в соответствии с их уровнями. Подрезали немного шум в логе от OC. Методы вроде [il]robot.suck[/il], [il]robot.suchFromSlot[/il] и [il]transpoer.transferItem[/il] теперь возвращают вместо [il]true[/il] число перемещённых предметов. Немного уменьшили назойливость частиц наномашинок. Жёсткий диск 3 уровня в режиме без ФС стал иметь по умолчанию не 6, а 8 пластин. Улучшили рендер кабелей как-то. Такие же "как-то" улучшения произошли с инвентарём роботов, апгрейдом крафта, методами [il]swing[/il] и [il]use[/il], взаимодействием с жидкостными баками. С модами получше работать должны. Чанклодыри можно ставить в микроконтроллер теперь. Расширили покрытие юникода шрифтом. Стандартный биос стал есть меньше памяти. Мониторы глючить должны поменьше. Пофиксили обнуление содержимого инвентарей блоков мода при крашах. Ещё некий краш при установке микроконтроллеров починили. Команду [il]/oc_nm[/il] вправили в место и заставили работать. Дюп роботов убран. Команды перемещения теперь говорят, успешно или безуспешно вызов завершился. Форсирование [il]LuaJ[/il] не форсировало эту архитектуру. [il]transferItem[/il] проверял не ту сторону. Починили Unknown error при попытке залить чего-то в некие машинки. Дюп дронов тоже починили. Выкорчевали возможную ошибку при запуске вместе с IC2. Роботы перестали потреблять ингредиенты при крафте, которые не потребляются. Апгрейд ангельский стал работать. Пофиксили торговый апгрейд. Его прямая задача исполнялась кривовато. Роботы не перемещались, когда нужно было. Дюп предметов дронами и роботами. Дискету network тоже можно ставить через install теперь. Дюп жидкостей, конечно, тоже был и тоже пофикшен. Дроны не реинициализировались после включения по сообщению модема. И вели себя очень странно. Всякие фиксы в интеграции с AE2. Опять некий дюп EEPROM. Удалён. Краши при загрузке с Applied Llamagistics. Краши при нетрадиионной установке компьютеров. Краши (но на клиенте), связанные как-то с кабелями и загрузкой чанков. [il]enableNanomachinePfx[/il] не имела эффекта. Роботы стали вызывать обработчики модов при получении опыта. Вводящие в заблуждение сообщения анализатора о выключенных компьютерах стали вводить в заблуждение в меньшей степени. Микроконтроллеры свою начинку теперь тоже выключают вместе с собою. Всякие ошибки кидал апгрейд поводка вместе с некоторыми модами. Фиксед. [1.10+] Починен рецепт крафта карточки с мировым датчиком. Экран планшетов теперь не зависает. Терминальные серверы ненормально цепляли удалённых терминалов на себя. Ошибки освещения с шейдерами. В OpenOS ещё отметить можно:
    Команда [il]reset[/il], которая ресетит разрешение. Ошибки сервисов пишутся в /tmp/event.log. Можно теперь ловить ошибки по Ctrl-Alt-C (жёсткие прерывания) путём переопределения функции в [il]process.info().data.signal[/il]. Копипаст в [il]edit[/il]: Ctrl-K — вырезать, Ctrl-U — вставить строку. Процессы закрывают файлы при завершении. Ссылочка на гитхаб, откуда можно скачать мод.
  17. Fingercomp

    Палитры OpenComputers

    Автор: Fingercomp,

    Немногие знают, как работают палитры в OpenComputers. Расскажу здесь, как избавиться от необходимости прописывать гектары цветов в палитре, покажу, как упаковываются цвета в OpenComputers и дам пару алгоритмов для работы с индексами.
     
    Сразу условимся, что индексы палитр у нас будут начинаться с нуля.
     
    На каждой из трёх уровней видеокарт и мониторов своя поддерживаемая палитра цветов. Будем двигаться снизу вверх.

    Первый уровень
    Палитра состоит из двух цветов: чёрного и заданного в конфиге (по умолчанию белого). Конвертация цвета в индекс палитры тривиальна:
    цвет нулевой — и индекс нулевой (чёрный цвет); цвет ненулевой — индекс единичный. Цвет в индекс (deflate) и обратно (inflate) превращать — одно удовольствие:
    local palette = { 0x000000, CONFIG.monochromeColor } local function t1deflate(index) if index == 0 then return 0 else return 1 end end local function t1inflate(index) return palette[index + 1] end Как и говорил.

    Второй уровень
    В палитре второго уровня имеется 16 закреплённых цветов:
    local palette = {0xFFFFFF, 0xFFCC33, 0xCC66CC, 0x6699FF, 0xFFFF33, 0x33CC33, 0xFF6699, 0x333333, 0xCCCCCC, 0x336699, 0x9933CC, 0x333399, 0x663300, 0x336600, 0xFF3333, 0x000000}
    При конвертации цвета в индекс палитры вернётся ближайший к данному цвет из палитры. Насколько цвета друг к другу близки, рассчитывается по специальной формуле, которая учитывает, что человеческий глаз лучше воспринимает зелёный, нежели красный и синий. В коде этим занимается функция delta. Вот как она выглядит (вместе с функций extract, выделяющей из числа вида 0xABCDEF числа 0xAB, 0xCD, 0xEF):
    local function extract(color) color = color % 0x1000000 local r = math.floor(color / 0x10000) local g = math.floor((color - r * 0x10000) / 0x100) local b = color - r * 0x10000 - g * 0x100 return r, g, b end local function delta(color1, color2) local r1, g1, b1 = extract(color1) local r2, g2, b2 = extract(color2) local dr = r1 - r2 local dg = g1 - g2 local db = b1 - b2 return (0.2126 * dr^2 + 0.7152 * dg^2 + 0.0722 * db^2) end   Теперь можно конвертировать цвет в индекс палитры. Суть такова: выбираем из двух цветов ближайший и возвращаем его.
    local function t2deflate(color) -- Сначала проверяем, совпадает ли данный цвет -- с каким-либо из палитры for idx, v in pairs(palette) do if v == color then return idx end end -- Составляем таблицу разниц между цветами local deltas = {} for idx, v in pairs(palette) do table.append(deltas, {idx, delta(v, color)}) end -- Сортируем по увеличению разницы table.sort(deltas, function(a, b) return a[2] < b[2] end) -- Первый элемент будет с наименьшей разницей, -- то есть искомый. Возвращаем индекс. return deltas[1][1] - 1 end  
    Обратная же процедура — превращение индекса палитры в цвет — неизменна.
    local t2inflate = t1inflate
    Третий уровень
    Палитра третьего уровня содержит уже 256 цветов: первые 16 цветов изменяются, а остальные соответствуют цветам палитры RGB-6-8-5. Это означает, что можно смешивать 6 оттенков красного, 8 оттенков зелёного и 5 оттенков синего. В общем-то, довольно очевидна причина такого выбора: человеческий глаз лучше всего различает оттенки зелёного и хуже всего — оттенки синего.

    В любом случае, здесь алгоритмец будет посложнее. Сначала нужно сгенерировать палитру.
    Начнём с первых 16 цветов. Они не включаются в палитру RGB-6-8-5, поэтому их заполнять нужно отдельно. В OpenComputers по умолчанию они содержат оттенки серого. Так как чёрный и белый уже включены в основную, зафиксированную палитру, то заново их дублировать смысла нет.
    local palette = {} -- grayscale for i = 1, 16, 1 do palette[i] = 0xFF * i / (16 + 1) * 0x10101 end
    Таким образом в таблице получаются следующие оттенки серого:
    0x0F, 0x1E, 0x2D, 0x3C, 0x4B, 0x5A, 0x69, 0x78, 0x87, 0x96, 0xA5, 0xB4, 0xC3, 0xD2, 0xE1, 0xF0 Эти цвета мы записываем в индексы от 0 до 15. Теперь нужно сгенерировать остальные цвета — они не изменяются. Здесь будет посложнее.
    Посмотрим на картинку с палитрой:

    В OpenComputers левая верхняя ячейка палитры (0x000000) имеет индекс 16, а правая нижняя (0xFFFFFF) имеет индекс 255. Индексы распределяются слева направо, сверху вниз. То есть правая верхняя ячейка (0x00FFFF) имеет индекс 55, а вторая сверху и левая (0x330000) — это номер 56. Отсюда вытекает следующий алгоритм нахождения цвета: сначала найти индексы отдельно по R, G, B, затем для каждого из этих трёх индексов найти соответствующий ему оттенок цвета, а затем всё сложить.
    for idx = 16, 255, 1 do local i = idx - 16 local iB = i % 5 local iG = (i / 5) % 8 local iR = (i / 5 / 8) % 6 local r = math.floor(iR * 0xFF / (6 - 1) + 0.5) local g = math.floor(iG * 0xFF / (8 - 1) + 0.5) local b = math.floor(iB * 0xFF / (5 - 1) + 0.5) palette[idx + 1] = r * 0x10000 + g * 0x100 + b end Идея следующая. Каждый из трёх каналов принимает значение от 0 до 255 (0xFF). Разбиваем их на определённое число ступеней (по-умному — квантуем): 6 для красного, 8 для зелёного и 5 для синего. Например, синий канал мы разобьём так:
    0/4 · 255 = 0 1/4 · 255 = 63.75 2/4 · 255 = 127.5 3/4 · 255 = 191.25 4/4 · 255 = 255 В знаменателе тут 4, а не 5, потому что считаем с нуля. Затем округляем до ближайшего целого конструкцией math.floor(x + 0.5). Перебрав все комбинации, мы получим все 6 × 5 × 8 = 240 цветов неизменяемой части палитры.
     
    Всё. Палитра есть, теперь можно, наконец-то, конвертировать индексы между цветами.
    Из индексов получить цвет довольно просто. Достаточно использовать ту же функцию, что и для предыдущих уровней:
    t3inflate = t2inflate
    С обратной же конвертацией всё несколько сложнее. Функция, используемая в OC, подбирает ближайший цвет хитрым алгоритмом, который я привожу ниже.
    local function t3deflate(color) local paletteIndex = t2deflate(color) -- Если цвет из палитры, то используем значение выше for k, v in pairs(palette) do if v == color then return paletteIndex end end -- Иначе используем хитромудрый код local r, g, b = extract(color) local idxR = math.floor(r * (6 - 1) / 0xFF + 0.5) local idxG = math.floor(g * (8 - 1) / 0xFF + 0.5) local idxB = math.floor(b * (5 - 1) / 0xFF + 0.5) local deflated = 16 + idxR * 8 * 5 + idxG * 5 + idxB if (delta(t3inflate(deflated % 0x100), color) < delta(t3inflate(paletteIndex & 0x100), color)) then return deflated else return paletteIndex end end Хитромудрость здесь не сильно сложная, на самом деле. Мы сначала находим индекс самого близкого цвета из изменяемой части палитры (paletteIndex). Дальше высчитываем индекс цвета из неизменяемой части (deflated), для чего в каждом канале отдельно ищем номер ближайшей ступени, на которые ранее квантовали. Последний if сравнивает 2 варианта и возвращает самый похожий (с точки зрения человека) на исходный.   В общем-то, это всё. Показал портированный со Scala на Lua код, который используется в OpenComputers. С помощью этого можно оптимизировать операции с экраном, выбирая поддерживаемые монитором цвета. И заодно избавиться от таблиц цветов, которые некоторые буквально берут и копипастят в файл, даже не задумываясь об изменяемых цветах палитры.
    Особенно это важно, когда берётся значение цвета через gpu.get, потому что следующий код всегда вернёт false:
    local gpu = require("component").gpu gpu.setForeground(0x20AFFF) gpu.setBackground(0x20AFFF) gpu.set(1, 1, "HI") return select(2, gpu.get(1, 1)) == 0x20AFFF И всё потому, что gpu.get возвращает уже приведённый к индексу из палитры цвет. А 0x20AFFF в палитре, если не менять первые 16 цветов, не имеется.

    Enjoy :P
  18. Fingercomp

    Пара трюков OpenComputers

    Автор: Fingercomp,

    Здесь опишу такие штучки, которые могут потребоваться продвинутым OC-программистам (да и просто Луа-программистам).
     
    Busy Idle
    С помощью этого трюка можно делать довольно точные задержки, причём с длительностью менее тика.
    local lastSleep = os.clock() local function sleep(t) local begin = os.clock() while os.clock() - begin < t do if lastSleep - os.clock() >= 3.5 then -- В конфигурации дефолтное значение = 5 секунд, ставим на 1.5 меньше для безопасности. os.sleep(0.05) -- Вынужденная задержка. lastSleep = os.clock() t = t - 0.05 end end end
    Проверка по значению
    Очень часто в моих программах нужно найти ключ, значение которого соответствует данному. Для этого я написал простую функцию:
    local function isin(tbl, value) for k, v in pairs(tbl) do if v == value then return true, k end end return false end На огромных массивах может и затормозить — скорость работы прямо зависит от длины массива.
     
    Табличная магия
    Рассмотрим этот на первый взгляд обычный пример кода:
    local tbl1 = {"My", "super", "table", 42} local tbl2 = tbl1 tbl2[2] = "cool" for _, tbl in pairs({tbl1, tbl2}) do -- Напечатать значения таблиц for k, v in pairs(tbl) do print(k, v) end end Разумно ожидать такое:
    1 My 2 super 3 table 4 42 1 My 2 cool 3 table 4 42 Но вместо этого получаем: 1 My 2 cool 3 table 4 42 1 My 2 cool 3 table 4 42
    Как видно, изменив значение в одной таблице, изменилась и другая.
    Дело в том, что переменная хранит указатель на таблицу, а не саму таблицу. Соответственно, и tbl1, и tbl2 ссылаются на один и тот же массив.
    На первый взгляд это кажется ненормальным. Как скопировать-то таблицу?
    local function copy(tbl) if type(tbl) ~= "table" then return tbl end local result = {} for k, v in pairs(tbl) do result[k] = copy(v) end return result end
    Но из этого можно извлечь очень полезное применение. Когда мы передаём таблицу в аргументы функции, массив не копируется, а даётся указатель на тот же самый. Поэтому можно сообразить такой код:
    local function removeOddNums(tbl) for k, v in pairs(tbl) do if tonumber(v) and v % 2 == 1 then tbl[k] = nil end end end local table = {5, 26, 249586, 457139, 876, 42, 153} removeOddNums(tbl) И он будет работать. Этим и объясняется, почему table.sort не возвращает таблицу. У меня не самое полезное применение, однако с помощью таблицы можно создавать "поинтеры", например, так: local numPtr = {42}, а в функциях использовать так: local value = numPtr[1]; numPtr[1] = 666. И уже использовать их в своих вычислениях.
     
    Думаю, вы найдёте применение этим фокусам. Не самые очевидные моменты, однако иногда требуется.
    The end.
  19. Fingercomp

    Парсер CSV

    Автор: Fingercomp,

    CSV идёт от Comma-Separated Values, что, в общем, довольно точно описывает этот формат хранения таблиц. Вот типичная таблица:
    aaa,bbb,ccc,dddeee,fff,ggg,hhh
    Как видно, строки отделяются \n, а ячейки ­— запятой. Последняя строка может иметь или не иметь \n.
     
    Формат очень простой. Описывается он в RFC 4180. Там всего 7 пунктов. Ну а раз простой, давайте соорудим парсер.
     
    Вот у нас есть строка aaa,bbb,ccc,ddd\neee,fff,ggg,hhh. Задача: сделать из неё
    [ [ "aaa", "bbb", "ccc", "ddd" ], [ "eee", "fff", "ggg", "hhh" ]]
     
    Так как позже я немного усложню парсер, очевидный вариант со split, которая делит строку, опустим. Сделаем так:
    def parse_csv(s): # Сюда идёт результат result = [] # Текущая строка row = [] # Текущая ячейка cell = "" # Проходимся по строке for i in range(len(s)): # Текущий символ c = s[i] if c == ",": # Если символ — запятая, закрываем ячейку row.append(cell) cell = "" elif c == "\n": # Если это перевод строки, то закрываем ячейку и строку row.append(cell) cell = "" result.append(row) row = [] else: # Любой другой символ добавляем в ячейку cell += c # Возвращаем результат return result
    Запускаем:
    >>> parse_csv("aaa,bbb,ccc,ddd\neee,fff,ggg,hhh\n")[['aaa', 'bbb', 'ccc', 'ddd'], ['eee', 'fff', 'ggg', 'hhh']] >>> parse_csv("aaa,bbb,ccc,ddd\neee,fff,ggg,hhh")[['aaa', 'bbb', 'ccc', 'ddd']]
     
    Действительно, в конце может и не быть \n. Давайте поправим:
    def parse_csv(s): result = [] row = [] cell = "" for i in range(len(s)): c = s[i] if c == ",": row.append(cell) cell = "" elif c == "\n": row.append(cell) cell = "" result.append(row) row = [] else: cell += c # Если ячейка не пуста if cell: # Закрываем ячейку и строку row.append(cell) result.append(row) return result
    Проверяем:
    >>> parse_csv("aaa,bbb,ccc,ddd\neee,fff,ggg,hhh\n")[['aaa', 'bbb', 'ccc', 'ddd'], ['eee', 'fff', 'ggg', 'hhh']] >>> parse_csv("aaa,bbb,ccc,ddd\neee,fff,ggg,hhh")[['aaa', 'bbb', 'ccc', 'ddd'], ['eee', 'fff', 'ggg', 'hhh']]
    Замечательно.
     
    Почему я проверяю только ячейку, а не строку ещё? Просто пустая ячейка и непустая строка может быть только тогда, когда на конце строки висит запятая. aaa,bbb,. А это явно запрещено по RFC.
     

    В текущем виде в ячейке у нас не получится хранить \n и ,. Если первый символ ещё кое-как, то без запятой как-то совсем не весело, верно?
    На наше счастье, в спецификации есть и это. Ячейку можно поместить в двойные кавычки (", кто не понял), тогда до следующей кавычки обрабатываться \n и , не будут.
     
    Давайте улучшим наш парсер, добавив поддержку этих самых кавычек. Так как у нас посимвольный парсинг, сделать это гораздо проще. Вот так:
    def parse_csv(s): result = [] row = [] cell = "" # Начиналась ли текущая ячейка с кавычки quoted = False for i in range(len(s)): c = s[i] if quoted: if c == '"': # Закрывающая кавычка quoted = False else: cell += c else: if c == '"': if not cell: # Открывающая кавычка в начале ячейки quoted = True else: # Кавычка в середине строки: запрещено return False elif c == ",": row.append(cell) cell = "" elif c == "\n": row.append(cell) cell = "" result.append(row) row = [] else: cell += c if cell: if quoted: # Где-то не закрыли кавычки return False row.append(cell) result.append(row) return result
     
    Проверяем:

     
     
    Всё верно, кроме последнего. В середине строки в закавыченных строках эти самые кавычки должны быть экранированы вот так: "". Например: "aaa""bbb,ccc",ddd,eee. Давайте починим и это.

    def parse_csv(s): result = [] row = [] cell = "" quoted = False # Является ли предыдущий символ кавычкой prevQuote = False for i in range(len(s)): c = s[i] if quoted: if c == '"': # Помечаем, что у нас есть кавычка в середине строки. # Она может быть экранированной. prevQuote = True quoted = False else: cell += c else: if c == '"': if not cell: quoted = True else: if prevQuote: # Если у нас прошлый символ был кавычкой, # то получаем экранированную кавычку. cell += '"' quoted = True prevQuote = False else: return False elif c == ",": row.append(cell) cell = "" # Кавычка была закрывающей prevQuote = False elif c == "\n": row.append(cell) cell = "" result.append(row) row = [] # Кавычка была закрывающей prevQuote = False else: if prevQuote: # Мы ждали кавычку или закрытие ячейки. return False cell += c if cell: if quoted: return False row.append(cell) result.append(row) return result
     
    Опять тестируем:

     
     
    Вот и всё. 44 строки кода на Python — и мы можем парсить CSV.
    Я также переписал парсер на Lua, опубликовал его в OPPM под libcsv. Можете качать и радоваться. Вот сырцы.
     
    Ну и надеюсь, это было менее сложно, чем мои записи про пакетные менеджеры до этого, и вы смогли прочитать это .
  20. Fingercomp
    tl;dr: https://gist.github.com/Fingercomp/0773bb0714296c0cb00d70a696d39bb3
     
    Понятия не имею, зачем я сюда об этом пишу, ведь если вы можете этот текст понять, и в оригинале можно прочитать.
     
    В любом случае, получил намёк, что три моих статейки про звуковую карту удовлетворительны в какой-то степени, но они на русском. Видите ли, ситуация с документацией спустя полгода после первого поста не улучшилась никак, так что единственный туториал для неё недоступен для понимания тех, кто не говорит по-русски.
     
    Поэтому я потратил выходные на перевод постов на английский язык. Заняло это отчего-то дольше, чем я ожидал. Результат на гисте.
     
    Все три поста в одном месте. Я там подбросил ещё чутка инфы и терминов и подправил фактические неточности. Мне лень было несколько раз перечитывать один и тот же текст, так что где-то могут остаться очепятки и всякие извороты языковые не к месту.
    Но если понимаете английский, то всё равно должно быть удобнее, чем бегать по трём статьям здесь, в блоге. Ну а мне редактировать проще.
     
    В общем, ссылку я оставил, больше мне сказать нечего.
  21. Fingercomp

    Про скобочки

    Автор: Fingercomp,

    Продолжу рассказывать про знаки препинания. В этом посте — 3 разных истории про пару круглых скобок.
     
    1. Вызовы функций
    Если функция вызывается с одним аргументом — строковым или табличным литералом, то скобочки необязательны.
    local function identity(x) return x end print(identity "test" == "test") print(table.unpack(identity {"test"}) == "test") Это чисто синтаксическая фишка, которая никак не влияет на исполнение кода. Очень удобно, чтобы вызвать функцию и передать ей таблицу с опциями.
    local logger = getLogger { name = "main", level = "info", output = {stdout}, }  
    Если несколько литералов так разместить подряд, получится ряд последовательных вызовов:
    myFunc "hello" "world" {"how do you do"} -- myFunc("hello")("world")({"how do you do"}) Используя эту фичу, можно воплотить всякие норкоманские вещи. Как вам вот такой форматтер с интерполяцией?
    local myVar = 42 print(format "myVar = " {myVar} ", and I'm running " {_VERSION} ()) --> myVar = 42, and I'm running Lua 5.3  
     
    2. Ещё про литералы
    У всех строк есть метатаблица, у которой __index = string. Это значит, что можно вместо string.gsub(str, ...) писать str.gsub(str, ...), или str:gsub(...). Очень удобно, особенно последнее.
     
    Но вот просто так заменить str литералом нельзя. "test":gsub(...) — синтаксически неправильный код. Выручат скобки вокруг литерала: ("test"):gsub(...). Постоянно этим пользуюсь.
     
    Та же ситуация, если мы хотим проиндексировать табличный литерал: {foo = "bar"}.foo выдаст ошибку. Лечится аналогично: ({foo = "bar}).foo.
     
    Кроме индексации, скобочки нужны при вызове: вместо function() return 42 end() нужно писать (function() return 42 end)().
     
    Наконец, есть ещё литералы численные: 42, например. В обычной Lua оборачивать их в скобки смысла, пожалуй, и не имеет, но с небольшим шаманством опять потребуются скобочки:
    debug.setmetatable(0, {__call = function(self) print(self) end}); (42)() --> 42 Правда, в OpenComputers отключён debug.setmetatable.
     
     
    3. Функции с множественным выхлопом
    В Lua функция может вернуть несколько значений:
    local function test() return 1, 2, 3 end print(test()) --> 1 2 3 Однако бывает, что нужно достать только одно значение, а про остальные забыть. Для этого нужно обернуть в скобки вызов функции, вот так:
    print((test())) --> 1 Скобочки возьмут только первое значение и отбросят остальные. С помощью функции select можно выбрать и другое по счёту:
    local function identity(...) return ... end print((select(3, identity(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)))) --> 8
  22. Fingercomp

    Прокачка стектрейса

    Автор: Fingercomp,

    Эта беспрецедентно короткая запись имеет начало своих ног в запросе @Laine_prikol, как-то спросивший в нашей ирке, можно ли стэктрейс сделать не таким тупым. Меня это заинтересовало, и спустя часик выросла очень короткая программка, которая рисует вот такие стэктрейсы:
    # 0: C field function yield(...) (defined in [C]) # 1: Lua local function f(f=function: 0x559402b83590, a=42, b=24, vararg test, nil):109 (defined in trace.lua at L108) # 2: Lua local function outer(f=function: 0x5594040b2230, g=function: 0x559402b83590, a=42, b=24, <... (1 arg)>):105 (defined in trace.lua at L103) # 3: Lua function <anon>():113 (defined in trace.lua at L102) Заметили что-то необычное? Наконец-то пишется, какие аргументы имеются у функции, потому что это куда информативнее беглому взгляду, чем описание расположения и строки.
     
    Код лежит на гисте: https://gist.github.com/Fingercomp/a688d221356cb371d940b947d0ca90a8. Использованы функции debug.getinfo и debug.getlocal. Аргументы должны писаться даже внутри OC, но уже без значений.
  23. Fingercomp
    В прошлый раз я патчил OpenComputers, чтобы пробрасывать нативную либу debug. Пойдём дальше.
    Добавим нативных либ package и os. Прокинем дефолтное окружение внутрь песочницы. Пропатчим мод, чтобы можно было загружать си-модули. Загрузим профилятор и посмотрим, что из этого вышло.  
    На винде ничего не заработает. Гарантирую. Если надо профилировать, ставьте нормальные оси или мучайтесь.
     
    0. Сырцы мода
    Так как мы будем патчить мод, надо сначала подготовить исходники.
    $ git clone https://github.com/MightyPirates/OpenComputers.git $ cd OpenComputers $ git checkout master-MC1.12 $ ./gradlew setupDecompWorkspace На третьей строке версию выбираем по вкусу и выпекаем всё необходимое для компиляции.
     
    1. Нативные либы
    Здесь всё просто. Открываем файл src/main/scala/li/cil/oc/server/machine/luac/LuaStateFactory.scala. Творим следующее:

    Вуаля. Теперь в machine.lua будут глобальные переменные package и _os. Отмечу отдельно, что меняем мы только архитектуру Lua 5.3.
    Уже на этом этапе у нас может сломаться персистентность. Это не страшно: она и должна сломаться.
     
    2. Прокидываем окружение
    Поступаем аналогично тому, что делали в прошлой записи: меняем src/main/resources/assets/opencomputers/lua/machine.lua:

    Внутри песочницы в глобальной переменной env запечатлено будет всё окружение machine.lua.
     
    3. C-модули
    Уже сейчас можно загрузить OpenOS и прописать env.require("libname"). Проблема в том, что C-модули так подключить не получится. Связано это с особенностью Lua. Абстрактно задача заключается в том, чтобы загрузить библиотку Lua с dlopen(..., RTLD_GLOBAL). System.loadLibrary в жаве флаг этот упускает по очевидным причинам, а нам он нужен. Значит, пришло время костылей.
     
    3.1. Подключаем JNA: build.gradle

    Первый ханк нужен, чтобы можно было потом компилировать мод. Почему-то у курсов мавен не работает, а разбираться мне лень.
     
    3.2. Патчим ещё раз src/main/scala/li/cil/oc/server/machine/luac/LuaStateFactory.scala

    Во-первых, подключаем хэшмапу. Потребуется.
    Во-вторых, импортируем JNA. Вернее, его часть.
    В-третьих, патчим код, чтобы он загружал Lua 5.3 через JNA. Магическая константа 0x101 — это значение RTLD_LAZY | RTLD_GLOBAL на моей системе. На фряхе, маке оно может отличаться.
     
    На этом этапе Lua 5.2 не будет работать. Включаться будет только Lua 5.3 из-за конфликта имён.
    Кроме того, JNA — это, вообще, огромная либа. Ради одной функции её подключать — это оверкилл. Но я в тонкостях JVM и JNI не силён. Как уже сказал, разбираться мне лень.
     
    3.3. Компилируем
    $ ./gradlew assemble Выхлоп в build/libs. Берём жарник без суффиксов вроде -javadoc, -api, -sources.
     
    4. Настраиваем профилятор
    Профилятор я написал сам на Rust. Вот ссылка: https://github.com/Fingercomp/lprofile-rs
    Очевидно, нам надо его скомпилировать.
     
    4.1. Компилируем профилятор
    Ставим cargo (мультитул раста такой) любым удобным способом. Собираем:
    $ cd .. $ git clone --recurse-submodules https://github.com/Fingercomp/lprofile-rs.git $ cd lprofile-rs $ cargo build --release В target/release будет лежать liblprofile.so. Тырим его.
     
    4.2. Определяем pwd
    Кидаем пропатченный OC в моды и запускаем игру. Пишем в опенкомпе env._os.getenv("PWD"), чтобы определить текущую директорию. Кидаем либу-профилятор в неё.
     
    4.3. Профилируем
    Наконец, можно заняться мясом.
    local profiler = env.require("lprofile").Profiler() local result = profiler(function() local v = 0 for i = 1, 10e6, 1 do v = v + i end end) table.sort(result, function(lhs, rhs) return lhs.totalTime < rhs.totalTime end) print("Name", "# of calls", "Total time", "Total time, excluding inner calls") for _, v in ipairs(result) do print(("%s\t%d\t%.6f s\t%.6f s"):format(v.name, v.calls, v.totalTime, v.totalSelfTime)) end print("total time:", result.totalTime)
     
    5. Зачем
    Мы получили наполовину сломанную версию OpenComputers: без Lua 5.3, без персистентности. Зато можем профилировать программы.
     
    Этот пост я написал, чтобы не забыть самому. Сомневаюсь, что кому-то интересно заниматься такой норкомагией.
  24. Fingercomp
    Каждый метод компонента в OpenComputers характеризуется его прямотой: есть прямые методы, а есть непрямые. Не раз в ирке разъяснял разницу. Сейчас расскажу и вам.
     
    Предположения:
    Текущая версия мода — 1.7.5. Вы собирали опенкомпьютер. Вы знаете, кто такой компонент, что у него за методы и как их вызвать.  
    С непрямыми вызовами всё просто. Они уводят компьютер в сон на тик. Всегда, при любом условии, даже в случае ошибки, после вызова непрямого метода компьютер до следующего тика работать не будет.
     
    Прямые вызовы такого ограничения не имеют. Один такой вызов может занимать произвольное количество времени. Зависит это от бюджета вызовов.
     
    У компьютеров OC есть бюджет вызовов. Это скрытая безразмерная величина. Каждый тик она сбрасывается до определённого значения. Определено оно так:
    Сначала смотрим на процессор в компьютере. Точнее, на уровень: T1 соответствует 0.5, T2 — 1.0, T3 — 1.5. Затем на каждую из планок памяти. T1 или T1.5 — это 0.5, T2 или T2.5 — 1.0, T3 или T3.5 — 1.5. Получаем несколько чисел. Суммируем, делим на количество — находим тем самым среднее арифметическое, которое и будет максимальным бюджетом вызовов.  
    Практикум:

    T2 процессор → 1.0 Планка T2.5 → 1.0 Планка T3.5 → 1.5 Бюджет вызовов: (1.0 + 1.0 + 1.5) / 3 ≈ 1.167.  
    Пример второй:

    Т3 процессор → 1.5 Планки T3.5 → 1.5, 1.5, 1.5 Планка T2.5 → 1.0 Бюджет вызовов: (1.5 + 1.5 + 1.5 + 1.5 + 1.0) / 5 = 1.4. Достаточно.
     
    Каждый прямой вызов расходует этот бюджет. По умолчанию — ровно одну тысячную его. Самые последние дев-билды мода делают прямые вызовы по умолчанию абсолютно бесплатными. Когда бюджет уходит в минус, компьютер принудительно спит до следующего тика.
     
    Определяет прямоту метода разработчик. Для создания метода в коде мода используется аннотация li.cil.oc.api.machine.Callback. Примерно так (метод hologram.get):
    @Callback(direct = true, doc = """function(x:number, y:number, z:number):number -- Returns the value for the specified voxel.""") def get(context: Context, args: Arguments): Array[AnyRef] = this.synchronized { ... } Если мы видим здесь direct = true, то это абсолютно точно прямой вызов. Если direct = false или отсутствует, то вызов непрямой.
     
    У метода может быть кастомная стоимость вызова. Не 0.001. У дата-карточки такое особенно. Пример (data.inflate):
    @Callback(direct = true, limit = 4, doc = """function(data:string):string -- Applies inflate decompression to the data.""") def inflate(context: Context, args: Arguments): Array[AnyRef] = { ... } limit = 4 читать как "потребляю 1/4 бюджета при вызове". Для сервера выше это 5 вызовов в тик. Недурно.
     
    У видеокарты всё сложно. Вообще, она тоже ограничивает ярость использования через бюджет вызовов. Потому на Т3-комплекте работать будет быстрее. Но количество потребляемого бюджета также зависит и от уровня видеокарточки. Для OC 1.7.5 распределение такое:
     
    Операция Стоимость  T1 GPU   T2 GPU  T3 GPU setBackground 1/32 1/64 1/128 setForeground 1/32 1/64 1/128 setPaletteColor 1/2 1/8 1/16 set 1/64 1/128 1/256 copy 1/16 1/32 1/64 fill 1/32 1/64 1/128  
     
    Поэтому максимально можно вызвать 384 сета в тик.
     
    Чтобы программно определить прямоту методов, есть функция component.methods(addr). Отдаём ей полный адрес компонента, получаем таблицу. В ключах имена методов, в значениях их прямота.
    Или же можно воспользоваться этой таблицей. Она включает все методы всех компонентов, которые есть в OpenComputers.
     
    И наконец, размер бюджета можно сменить в конфиге. Опция budgetCosts занимается именно этим.
  25. Fingercomp
    Раз уж я тут пишу понемногу свой крутой пакетный манагёр, расскажу о пакетных менеджерах немного.
     
    Пакетный менеджер — штука сложная. Потому что, хотя задача у него, в общем-то, одна — менеджировать пакеты — сюда включается и установка, и удаление, и обновление, и, вообще, много всякого. Но а так как пока сам не напишешь, ПМ не поймёшь, здесь расскажу об установке пакетов и зависимостей с кодом.
     
    Ещё немного предисловий, о зависимостях. Это ключевая фича ПМ: вы-то прогу скопировать/разархировать и сами можете, вот только если программа зависит от другой, а та — от двух других, и т. д., вам это надоест. Людям надоело. Создали пакетные менеджеры. Теперь программы пакуются в пакеты — а рядом со скомпилированными бинарниками лежит ещё кусок информации: имя пакета, версии, зависимости, авторы, изменения и много-много всяких других полей. При установке данные считываются и далее уже делается, что сказано. Зависимости ли ставятся, ещё ли что-нибудь.
     
    А затем пакетов становится много, появляются репозитории полноценные, ну и так далее.
     
    Итак, давайте сделаем программу для установки пакетов. Ну, почти. Именно полезной нагрузки как таковой не будет, будем использовать такую структуру информации о пакете (назовём это манифестом пакета):
    { "name": "имя пакета", "files": [ { "url": "http://example.com/bin-1", "path": "/usr/bin/program1" } , { "url": "http://example.com/library-1.so", "path": "/usr/lib/library1.so" } ]}
    Пока без зависимостей, всё просто.
     

    Вот такой код получим:
    def install(name): # получаем манифест пакета с данным именем manifest = getManifest(name) # проходимся по файлам... for file in manifest["files"]: # ...скачиваем и ставим их в нужные места download(url=file["url"], path=file["path"])
    Ничего примечательного, на самом деле. Получаем манифест, скачиваем файлы и пишем "тадаам".
     

    Давайте сделаем вот такие манифесты:
    { "name": "pkg1" # имя пакета, "deps": # зависимости [ { "name": "pkg1-1" } , { "name": "pkg1-2" } ], "files": [ { "url": "http://example.com/pkg1/file", "path": "/opt/pkg1/file" } ]} { "name": "pkg1-1", "deps": [ { "name": "pkg1-1-1" } ], "files": [ { "url": "http://example.com/pkg1-1/file1", "path": "/opt/pkg1-1/file1" } , { "url": "http://example.com/pkg1-1/file2", "path": "/opt/pkg1-1/file2" } ]} { "name": "pkg1-1-1", "deps": [], "files": [ { "url": "http://example.com/pkg1-1-1/file", "path": "/opt/pkg1-1-1/file" } ] { "name": "pkg1-2", "deps": [], "files": [ { "url": "http://example.com/pkg1-2/file1", "path": "/opt/pkg1-2/file1" } , { "url": "http://example.com/pkg1-2/file2", "path": "/opt/pkg1-2/file2" } ]}
    У нас есть 4 пакета: pkg1, pkg1-1, pkg1-1-1, pkg1-2. Вот граф зависимостей:
     
     
     
     
     
     
     
     
     



     

    Очевидно, что просто так теперь тут в рандомном порядке пакеты поставить нельзя. Так как при установке пакета, например, pkg1-1, он совершенно справедливо считает, что его зависимость, pkg1-1-1, уже установлена.
     
    То есть, по-хорошему, нам надо сначала брать пакеты без неразрешённых зависимостей, и подниматься вверх. Однако, есть идея покруче.
     
    Я сейчас наваяю рекурсивную функцию resolveDeps, которая будет, как ни странно, разрешать зависимости:
    def resolveDeps(name): result = [] # результатирующая последовательность установки пакетов manifest = getManifest(name) for dep in manifest["deps"]: # В Python справедливен код типа `[1, 2, 3] + [4, 5, 6] == [1, 2, 3, 4, 5, 6]`, т.е. склеиваение списков. result = resolveDeps(dep["name"]) + result return result
    Если мы дадим ей манифесты, она выдаст вот такой список: ["pkg1-1-1", "pkg1-1", "pkg1-2", "pkg1"] — от менее сложного к более сложному. То, что нужно. Затем мы ставим просто их:
    for pkg in resolveDeps("pkg1"): install(pkg)
    Давайте улучшим алгоритм. Сделаем проверку на установленность: нам ведь не надо повторно скачивать файлы, которые уже есть.
    def resolveDeps(name): result = [] # Проверяем, установлен ли пакет if not isInstalled(name): manifest = getManifest(name) for dep in manifest["deps"]: result = resolveDeps(dep["name"]) + result return result
    Если у нас уже поставлен pkg1-1, то получим всего лишь ["pkg1-2", "pkg1"]. Круто!
     

    Возьмём другой граф:
     
     
     




    Как видно, от pkg1-1-1 зависят сразу 2 пакета: pkg1-1 и pkg1-2. Проблема в том, что на выходе у нас будет ["pkg1-1-1", "pkg1-1-1", "pkg1-1", "pkg1-2", "pkg1"] — ни разу не то, что мы хотели. Давайте это исправим:
    def resolveDeps(name, resolved=None): resolved = resolved or [] # список уже разрешённых пакетов if name in resolved: # Пакет уже был разрешён, ничего больше не требуется return resolved if not isInstalled(name): manifest = getManifest(name) for dep in manifest["deps"]: resolveDeps(dep["name"], resolved) # Теперь список один на всю рекурсию resolved.append(name) # Без рекурсии сюда попасть можно, если пакет не имеет неустановленных зависимостей return resolved
    Теперь выхлоп у нас ["pkg1-1-1", "pkg1-1", "pkg1-2", "pkg1"] — как и предписывали.
     

    А вот вам ещё граф:
     
     
     




     

    Какая тут засада? А у нас дерево циркулярное — не руки циркуляркой отрезает, а в бесконечную рекурсию вводит. Вот как можно этого избежать:
    def resolveDeps(name, resolved=None, unresolved=None): resolved = resolved or [] unresolved = unresolved or [] # список ещё не разрешённых пакетов if name in unresolved: # Мы попали сюда через рекурсию. Когда-то пакет уже был добавлен в список unresolved, # после чего функция ушла в рекурсивное разрешение зависимостей этого пакета. # Какой-то из зависимостей в итоге опять имеет данный пакет как зависимость. # Это ошибка, такого быть не должно, паникуем. raise ValueError("circular dependencies detected") if name in resolved: # Пакет уже был разрешён, ничего больше не требуется return resolved unresolved.append(name) if not isInstalled(name): manifest = getManifest(name) for dep in manifest["deps"]: resolveDeps(dep["name"], resolved, unresolved) # даём unresolved resolved.append(name) # Не забываем убирать из списка del unresolved[unresoved.index(name)] return resolved
    Теперь у нас в данном графе будет сгенерировано исключение, а потому рекурсии бесконечной не произойдёт.
     

    Итак, у нас есть простая функция, которая составляет список пакетов для последовательной установки без ломаний. Это уже круто, но время шло, и появилось такое явление как версии. Впрочем, об этом поговорим в другой раз. Там есть свои заморочки, с которыми нужно разобраться.
     
    Вот похожая статья, но на английском. Рекомендую ознакомиться.
     
    Лицензия: CreativeCommons Attribution-NonCommercial 4.0 International License

×
×
  • Создать...