Итак, сегодня мы рассмотрим две особые команды интерфейса 1-wire, предназначенные для поиска устройств на шине, а также алгоритм поиска устройств с помощью этих команд.
Почему мы алгоритм именно рассмотрим, а не напишем? Да потому что он, вообще-то говоря уже написан. «Максимкины» инженеры накатали для этого специальный документ AN187, который лежит в сети в открытом доступе. Единственный его недостаток в том, что написан он на буржуинском, что, согласитесь, не очень удобно. Вот этот недостаток мы сегодня и исправим, ну и плюс, как всегда, некоторые подробности и объяснения по поводу того, откуда у этого алгоритма растут ноги.
Итак, первая команда называется «Search ROM» и имеет шестнадцатиричный код 0xF0. Она предназначена для поиска вообще всех подключенных к шине 1-Wire устройств.
Вторая команда называется «Alarm Search» и имеет шестнадцатиричный код 0xEC. Она предназначена для поиска всех подключенных к шине 1-Wire устройств, находящихся в состоянии Alarm.
Логика работы у обеих команд одинаковая. После того, как мастер отправляет в сеть одну из этих команд, все Slave-устройства, подпадающие под критерий поиска (то есть для команды «Search ROM» — вообще все устройства сети, а для команды «Alarm Search» — устройства, находящиеся в состоянии Alarm), начинают обмениваться с мастером информацией по следующему алгоритму:
1) Slave передаёт мастеру младший бит ROM
2) Slave передаёт мастеру инверсную копию младшего бита ROM и ждёт ответ от мастера
3) Если мастер присылает в ответ тот же самый бит, который Slave посылал ему в пункте 1, то Slave повторяет шаги 1,2 для следующего бита ROM, в противном случае Slave прекращает обмен данными с мастером
Теперь давайте мы эту логику пока запомним и немного от неё отвлечёмся. Рассмотрим просто произвольные двоичные числа. Ну, скажем, 8-битные. Ну, например такие: 10001010, 00110011, 10001100, 11001001. Всю группу этих двоичных чисел можно изобразить в виде двоичного дерева, ветвями которого являются биты в соответствующих разрядах, а узлами — места, после которых биты отличаются (то есть после которых ветвь раздваивается).
По такому принципу можно составить деревья как от младших битов к старшим, так и наоборот, но мы будем рисовать от младших битов к старшим (смотрим рисунок справа). Очевидно, что аналогичное двоичное дерево мы можем постоить для любой группы двоичных чисел, любой разрядности.
Далее, вспоминаем основы программирования, а конкретно, — алгоритм прямого обхода двоичных деревьев. Что нам нужно для обхода некоего произвольного дерева? Всего две вещи: a) знать, где находятся узлы; б) уметь выбирать то или иное направление обхода.
А вот теперь вернёмся к логике работы команд поиска, описанной нами в самом начале статьи. И подумаем вот о чём:
1) Поскольку шина общая, то посылаемые мастером команды будут видеть сразу все устройства на шине. И, соответственно, отвечать будут тоже сразу все устройства, причём все одновременно, поскольку передача данных синхронизируется мастером.
2) Архитектура шины 1-Wire такова, что доминантным является низкий уровень сигнала на шине. То есть, если какие-то устройства будут выставлять на шине низкий уровень, а какие-то — высокий, то победят те, кто выставлял низкий уровень, и, соответственно, на шине установится низкий уровень.
Эти две особенности шины 1-Wire, в сочетании с логикой работы команд поиска, дают нам механизм определения узлов в двоичном дереве, составленном из ROM-адресов устройств, отвечающих заданным критериям поиска.
Тут всё очень просто. Со стороны мастера, когда он читает биты от slave-устройств, возможны следующие ситуации:
- Мастер считывает с шины 01. Это означает, что все устройства, участвующие в обмене данными, послали ему биты 01 (текущий бит ROM = 0, его инверсная копия = 1);
- Мастер считывает с шины 10. Это означает, что все устройства, участвующие в обмене данными, послали ему биты 10 (аналогично первому пункту, только наоборот);
- Мастер считывает с шины 00. Это означает, что какие-то устройства послали ему 01, а какие-то 10 (в обоих случаях победили те, кто посылал нули). Это означает, что перед мастером находится узел двоичного дерева, то есть на этой ветви существуют такие ROM-адреса, у которых следующий бит равен нулю и такие, у которых следующий бит равен единице;
- Есть ещё вариант, когда мастер считывает с шины 11. Казалось бы, такая ситуация является невероятной, однако она тоже возможна, например, если устройства, с которыми мастер решил продолжить разговор, отключились.
Осталось только найти механизм выбора направления обхода. Ну, тут уж всё очевидно, — такой механизм предоставляется нам третьим пунктом логики работы команд поиска. Ответ от мастера — это и есть выбор направления. Отправляя в шину в качестве ответа ноль или единицу, мастер как раз и решает с какой группой устройств он «продолжит разговор», по какой ветке он дальше пойдёт.
Теперь рассмотрим одну особенность алгоритма обхода двоичного дерева, характерную для шины 1-Wire. Особенность эта заключается в том, что мы можем двигаться по дереву только вперёд и каждый новый маршрут должны проходить с самого начала. То есть для каждого нового маршрута нужно заново посылать в шину Reset, команду поиска и доходить до того узла, на котором нам сейчас нужно повернуть в другую сторону. Соответственно, нам нужно будет как-то запоминать, где и куда мы в последний раз поворачивали.
Ну вот, пожалуй все важные моменты будущего алгоритма обхода двоичного дерева адресов ROM мы уже рассмотрели и теперь можем, наконец, этот алгоритм как-то формализовать. Давайте этим и займёмся, но для начала условимся в дальнейшем, для удобства, называть поворот в ветку, обозначающую нулевой бит, — поворотом налево, а поворот в ветку, обозначающую единичный бит, — поворотом направо. Кроме того, давайте уровень узла договоримся считать равным разряду битов, перед которыми этот узел расположен.
Всё, переходим к самому алгоритму.
I) Определимся с переменными, которые нам понадобятся:
- ROM[64] — массив, в котором по мере заполнения будет формироваться очередной найденный ROM;
- CRC — переменная, в которой мы будем вычислять CRC (подробнее про вычисление CRC можно прочитать здесь)
- SlaveBit, ISlaveBit — очередной бит и его инверсная копия, считанные с шины мастером;
- Step — переменная, показывающая, на каком шаге поиска мы находимся (бит какого разряда мы сейчас ищем);
- LastDev — флаг, показывающий, что мы нашли последний девайс (дальше продолжать поиск не нужно);
- MasterBit — переменная, в которой будет записан ответ от мастера (она определяет дальнейшее направление поиска);
- LastFork — уровень, на котором расположена последняя развилка, из которой мы поворачивали влево при предыдущем проходе по дереву (в этот раз на ней нужно повернуть направо);
- LastFamilyFork — здесь хранится уровень последней развилки, относящейся к семейству устройств (младший байт ROM)
- ZeroFork — сюда пишем уровни всех развилок, в которых мастер при текущем проходе по дереву отвечал нулём (поворачивал налево), в конце прохода отсюда мы узнаем уровень последней такой развилки.
II) Составим блок-схему процедуры прохода по одному из маршрутов:
Ну вот, теперь, используя приведённую выше блок-схему, легко можно реализовать алгоритм обхода двоичного дерева ROM-адресов, то есть найти все устройства, отвечающие критериям поиска, заданным соответствующей командой.
Для этого нужно инициализировать переменную LastDev значением 0, переменную LastFork значением -1 и выполнять составленную по блок-схеме процедуру столько раз, сколько потребуется, до тех пор, пока очередное выполнение не завершится с ошибкой (при этом каждый раз после успешного выполнения процедуры мы будем получать новое значение ROM).
Более того, если инициализировать значение ROM каким-либо номером, LastDev — нулём, а LastFork любым значением >64, то однократное выполнение процедуры позволяет проверить, есть ли на шине девайс с заданным номером. Если такого девайса нет, то выполнение процедуры завершится с ошибкой (на каком-то этапе мастер получит с шины две единицы).
Если записать в первый байт ROM код семейства, в остальные байты ROM — нули, LastFork инициализировать любым значением >64, а LastDev значением 0, то выполнение процедуры столько раз, сколько потребуется, до тех пор, пока очередное выполнение не завершится с ошибкой, позволит найти все устройства заданного семейства, отвечающие заданному командой критерию поиска.
Вот в общем-то и всё. Пример реализации описанного алгоритма можно посмотреть в программе для программирования микросхем памяти DS2430, исходники которой можно скачать в подразделе «полезные программы для ПК«.