[Gall]

 Сообщение от SviMik :

Ты не понял. "Что-то-еще-делание" может затянуться дольше, чем период между прерываниями. Что тогда?

Порезать его на части.

 Сообщение от SviMik :

А если там будет общение с внешними девайсами? Оно тем более может затянуться.

Грубая ошибка проектирования программы - ожидание в общении со внешними девайсами не должно тормозить остальной код.

 Сообщение от SviMik :

Самое логичное - код, проигрывающий семпл, надо писать в прерывание, т.к. он должен выполняться немедленно.
Код, который должен выполняться в фоновом режиме, писать в основном цикле. Он будет выполняться между прерываниями.
Мне такой вариант кажется самым производительным. А как бы сделал ты?

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

Код такого рода элементарно пишется без прерываний (и более того, при желании можно гарантировать точную частоту отсчетом по тактам, что дает джиттер на такт меньше, чем прерывания). Пишется это на конечных автоматах. Код разбивается на несколько коротких (меньше 166 тактов) частей, выполняющих кусочки обработки протокола карты. Поллинг карты делается по аналогии с подходом poll/select в UNIX. В цикле выбираем очередное действие по обработке данных, затем паузу (можно даже просто nop добить, если знать число тактов) и вывод сэмпла.

Никакой проблемы здесь нет, кроме проблемы понимания одной идеи - программу можно "вывернуть наизнанку", оперируя не последовательностью действий, а состояниями и событиями. Почему-то этот простой факт всегда вводит в ступор не только начинающих, но даже многих довольно опытных программистов, хотя по сути это мощный прием УПРОЩЕНИЯ программы.

Если возникает необходимость строго считать такты, то для написания таких программ лучше использовать самодельные вспомогательные утилиты (программы, которые пишут программу). На таком подходе в свое время кем-то был сделан драйвер LCD-экрана, отсылавший в реальном времени байты из видеопамяти на матрицу. Там между выводом байтов оставалось всего по 1 пустому такту, и то не всегда, и программа была написана "через строчку", как стасованная колода карт - чередующиеся команды от разных нитей исполнения.

[Gall]

 Сообщение от INFERION :

По твоим словам выходит, что программа в фоновом режиме не может выполнятся дольше интервалов между прерываниями. Т.е. приходится время от времени сохранять промежуточные данные и разрешать флаг глобального прерывания, чтоб не пропустить событие.

Первая фраза верна, вторая - нет. А именно, при таком подходе к написанию в программе просто нет "промежуточных данных" как таковых, и отдельных действий по сохранению не требуется. Просто каждой нити исполнения назначается собственный набор регистров и переменных, не пересекающийся с другими нитями, и тогда команды от разных нитей можно спокойно тасовать в любом порядке, с любыми sleep внутри - это никак ничему не мешает.

 Сообщение от INFERION :

Так что мешает вставить эти же фрагменты кода между командами Sleep? Так и проще будет.

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

 Сообщение от INFERION :

Не придётся часто разрешать прерывания, т.к. время прогнозируемое.

При таком подходе прерывания НИКОГДА НЕ ЗАПРЕЩАЮТСЯ. Может, в этом ответ на все вопросы?

 Сообщение от INFERION :

Не могу я представить как на "слипах" построить серьёзную программу, нормально реагирующую на все события, в любых их комбинациях. Прерывания с этим сами разберутся, а там думать и огородить приходится.

Как раз беда прерываний в том, что они НЕ разбираются сами во ВСЕХ комбинациях событий. Сложность в том, что "очередь" прерываний представляет всего лишь набор флажков с приоритетами, и обработку прерываний никак нельзя считать "справедливым планированием" задач. Фактически речь идет о том, чтобы аппаратную очередь прерываний заменить на программный "справедливый планировщик", а сами прерывания сделать всего лишь постановщиками задач в очередь этого планировщика. "Справедливость" предполагает, что время выделяется КАЖДОЙ из задач, и самая приоритетная не может сожрать весь процессор, даже если ей непрерывно сыплются прерывания. Самая простая реализация справедливого планировщика не требует очереди как таковой - она просто имеет каждую нить исполнения под if. В более сложных задачах применяются более продвинутые алгоритмы (см. работы Дейкстры, "задачу обедающих философов" и т.п.)

В серьезной программе на подходе конечных автоматов 90% работы программиста - это правильное построение набора состояний и автоматов. В простой программе это можно сделать в уме, в программе чуть сложнее - вручную на листке бумаги. Сложные программы, такие как парсеры сетевых протоколов, могут иметь сотни состояний, и построить их руками нереально. В этом случае используются специальные инструменты - генераторы конечных автоматов (ragel, apertium, sfst, lex/yacc, antlr) и программы машинной алгебры (mace4, prover9), которые по заданным требованиям пишут почти готовую программу. Их можно использовать и для проверки программ на прерываниях - для поиска фатальных сочетаний событий, рушащих программу (это сложно вручную, но легко для машины).

Прелесть подхода конечных автоматов в том, что всего лишь 8 байт памяти дают 2^64 возможных сочетаний флажков. Это позволяет писать сложнейшие алгоритмы, используя всего лишь от 2 до 8 регистров (8-битных) для хранения промежуточных состояний. Вместе с несколькими десятками команд на анализ состояний это позволяет написать очень компактный и быстрый обработчик сложнейших протоколов обмена с периферией. В частности, для раскодирования любого (!) протокола серийно выпускаемых ИК-пультов достаточно 1 регистра. Примерно такую же сложность имеют раскодировщики spdif и подобных вещей, а анализатор XML с порта RS232 уложится в 8 регистров. Теоретически, в mega128 должен влезть оптимизирующий компилятор Си...

[SviMik]

Сложные программы, такие как парсеры сетевых протоколов, могут иметь сотни состояний, и построить их руками нереально. В этом случае используются специальные инструменты - генераторы конечных автоматов (ragel, apertium, sfst, lex/yacc, antlr) и программы машинной алгебры (mace4, prover9), которые по заданным требованиям пишут почти готовую программу.

Я так понимаю, что это уже выходит за рамки того программирования, которое подразумеваю я - именно самостоятельное написание кода

Порезать его на части.

Это может оказаться очень трудоёмкой работой! Впрочем, ты и сам написал, что руками это может оказаться нереально
А я люблю делать всё руками, зачем мне такие сложности?

Можешь на примере написать, как это делается? Если это то, что я думаю - там на одну проверку всех флагов уйдёт много тактов, а их надо проверять между каждыми семплами, чтобы определить, что надо делать, верно? А между семлпами может оказаться всего десяток тактов.

Прелесть подхода конечных автоматов в том, что всего лишь 8 байт памяти дают 2^64 возможных сочетаний флажков.

Кроме флажков, может понадобиться ещё хранить байты, стринги, а то и вовсе массивы Так что про озу ничего не понял, что ты хотел скзать. Не одни же флажки там хранятся. А хранится всё, что надо хранить, плюс ещё твои флажки

[Gall]

"Самостоятельное написание кода" подразумевает даже не Ассемблер, а машинный код. Уже на Си код пишет все-таки компилятор. То, о чем я говорю - это просто использование языков еще более высокого уровня, чем Си - настолько высокого, что они Си на выходе вместо машинного кода дают.

Написать, как выглядит сгенерированный код, я могу, но понять, как именно ЭТО работает - нереально.

А про ОЗУ - вот что. В "обычной" программе при ближайшем рассмотрении в памяти хранится очень много лишнего. Флажки можно хранить не дополнительно к строкам и счетчикам, а ВМЕСТО них.

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

# комментарий

а = 12
b = 456
name = test
longname = "test test"

Конечный результат следует поместить в заранее выделенные переменные.

"Вариант новичка" номер 1. Читаем из файла строку (то есть, читаем файл по байтам, пока не наткнемся на символ перевода строки). Определяем, является ли строка комментарием. Ищем в ней знак равенства. Определяем, есть ли кавычки. Выделяем имя (слева от знака равенства) и ищем его в массиве перебором, в лучшем случае - в дереве. Заполняем переменную.
Накладные расходы: строка в памяти, список всех переменных.

"Вариант новичка" номер 2. Читаем файл много раз, каждый раз ища одну переменную. Без комментариев.

И, наконец, оптимальное решение задачи. Входной файл в нем читается ровно один раз, можно даже по одному байтику. Никаких промежуточных строк не храним. Все, что требуется - это одна целочисленная переменная "номер состояния".

Вот как это работает. Изначально мы находимся в состоянии "начало строки". Когда приходит байт, если это не пробел, мы меняем состояние. После символа "#" мы переходим в состояние "комментарий", в котором остаемся до символа "конец строки". После знака равенства - в состояние "значение", а если мы уже в состоянии "значение" и видим кавычку - то в состояние "значение внутри кавычек". И так далее. Таким образом мы можем получить полное знание о содержимом файла, не видя более 1 байта за раз.

Как мы опознаем имена перед знаком равенства? Очень просто. Каждому имени соответствует состояние, попасть в которое можно только из состояния "одной буквы не хватает до полного имени" - и так далее.

Аналогично обрабатываются и числа. По одной цифре читаем параллеьно с вычислением результата.

На первый взгляд может показаться, что программа получается длиннее и медленнее. Это не так. Наоборот, накапливается очень серьезная экономия, связанная именно с обращениями к памяти - программа не делает копирование строк, не выделяет и не освобождает память, а на микроконтроллерах не вызывает инструкций обращения к ОЗУ. Тем самым можно ускорить программу и сократить расход памяти за счет некоторого увеличения длины кода. Но место под код обычно гораздо "дешевле" ОЗУ, особенно на микроконтроллерах, где каждый байт ОЗУ на счету. На указанном подходе в нашей группе и мною лично были разработаны очень серьезные программы, одна из которых (парсер потоков синдикации Яндекс.Видео), по-видимому, является самой быстрой в мире в своем классе.

Статьи из Википедии по теме:
Автоматное программирование
Событийно-ориентированное программирование

[SviMik]

То, о чем я говорю - это просто использование языков еще более высокого уровня

Тогда тем более оффтоп! Тут про Си говорим Мне не нужны другие языки...
ЗЫ. Думал ты про генератор кода, которые встроенны в некоторые редакторы для мк. Кликаешь в визарде, а он создаёт шаблоны на Си для разной периферии.

На первый взгляд может показаться, что программа получается длиннее и медленнее.

Очевидно, программа получается сложнее! Это самое главное! И да, длиннее...
Может в итоге, эта скорость и не нужна. В этом плане, парсинг конфига - неудачная задача, разовая. И освободившуюся после этого процесса ОЗУ можно использовать для других целей.

Но место под код обычно гораздо "дешевле" ОЗУ, особенно на микроконтроллерах

Если писать на ассемблере, до ОЗУ иногда вообще дело не доходит - регистров хватает (пример - я читаю с карточки wav файл и играю его без озу). А вот программа может легко не влезть в мк! Вот купил я тиньку с 2кб памяти, а программа уже заняла больше половины, мог и не вместиться
Цены у них от памяти гуляют очень сильно! attiny261 - 4.33 евро, attiny861 - 7.03 евро. Ощущение, что память на вес золота, а всё остальное ничего не стоит.

[lasers_AVSel]

ИМНО: Программа(функция) на автоматах действительно получается экономичнее и проще.
Например: если завести один регистр состояния и один switch, можно избежать совершенно жуткого ветвления в программе(функции) с кучей флагов и вложенных друг в друга if...else. Но вот отлаживать такую програмку(функцию) сложнее.
Но тут выручает Cи, отладку и тестирование ПО можно выполнить и на обычном ПК. Если конечно заранее работу с железом вынести в отдельные файлы. В этом случае эмулятор девайса на ПК делается элементарно

[Gall]

 Сообщение от SviMik :

Тогда тем более оффтоп! Тут про Си говорим Мне не нужны другие языки...

Очень, очень глупо. Нельзя привязываться к одному языку. Язык надо выбирать строго по задаче. Точнее, есть очень важный программистский тезис:

Не пишите программу. Пишите программу, которая напишет программу.

Только в простейших случаях программа пишется руками.

 Сообщение от SviMik :

Очевидно, программа получается сложнее! Это самое главное! И да, длиннее...

Программа получается более многословной, но ее логика становится ПРОЩЕ. Простота написанных "в лоб" программ - КАЖУЩАЯСЯ, ведь на самом деле в них не учтены многие важные вещи. Возьмем самый простой пример, опять же с большого компа:

int main() { printf("Hello World!\n"); return 0; }

Верно ли написана эта программа? НЕТ! Дело в том, что функция printf может вернуть код ошибки. Правильно было бы переписать программу подобным образом:

int main() { return (printf("Hello World!\n") == 13) ? 0 : 1; }

Программа стала значительно сложнее. А все лишь потому, что мы исправили в ней неочевидную ошибку. Так вот, в ЛЮБОЙ программе, написанной "как проще", таких неочевидных ошибок ПОЛНО, и если их все исправить - получается сложнейшая нечитаемая каша из if. Все еще хочешь писать "в лоб"?

 Сообщение от SviMik :

А вот программа может легко не влезть в мк! Вот купил я тиньку с 2кб памяти, а программа уже заняла больше половины, мог и не вместиться

Именно поэтому на ассемблере писать и не надо. Потому что это его болезнь - невлезание кода. Попробуй на той же тиньке параллельно с проигрыванием wav еще и светодиодов-хамелеонов программно сделать на все свободные выводы через ШИМ. СлабО? А все потому, что ресурсов на эти светодиоды хватит только в том случае, если переплести нити исполнения. Писать программу в стиле "строчка оттуда, строчка отсюда" человек не может. На Си такое тоже фиг напишешь. Как же быть?

Спасет самодельный компилятор. Написать его можно на чем угодно, самые подходящие языки - perl, php или функциональные (lisp, haskell). Каждая нить исполнения (на каждый светодиод, на проигрывание wav и т.п.) пишется руками на псевдоассемблере отдельно. "Псевдоассемблер" от настоящего ассемблера отличается тем, что там вместо имен регистров ставятся буквы. Затем с помощью самодельной программы все это сшивается воедино - проставляются имена регистров, подсчитываются такты (по таблице из даташита), перетасовываются команды из разных нитей. Вручную это фиг сделаешь, а с помощью самодельной программки - тьфу, ерунда. Это называется "метапрограммирование". Именно оно позволяет писать самые простые и оптимальные программы.

Пример:
на входе - нить 1:

#loop
sbi PORTA, 6
#delay 3 // такта
cbi PORTA, 6
#delay 1
#endloop

на входе - нить 2:

#loop
sbi PORTB, 1
#delay 1
cbi PORTB, 1
#delay 3
#endloop

На выходе самодельного "компилятора":

L0:
    sbi PORTA, 6
    sbi PORTB, 1
    nop
    cbi PORTB, 1
    cbi PORTA, 6
    rjmp L0

А теперь представь, что у тебя не две нити, а сотня. Вручную сможешь их так переплести? А программа, написанная за 15 минут - сможет легко.

Добавлено через 4 минуты

 Сообщение от AVSel :

Но тут выручает Cи, отладку и тестирование ПО можно выполнить и на обычном ПК. Если конечно заранее работу с железом вынести в отдельные файлы. В этом случае эмулятор девайса на ПК делается элементарно

Можно пойти еще дальше - не тестировать и не отлаживать вообще. Существует определенный набор приемов написания (больше относится к C++, но можно применить и к Си), который практически гарантирует правильность программы, если она вообще скомпилируется. Я никогда не пользуюсь эмулятором или отладчиком при программировании мироконтроллеров и почти никогда - при программировании компа. Их функции берет на себя компилятор.

[lasers_AVSel]

 Сообщение от Gall :

Я никогда не пользуюсь эмулятором или отладчиком при программировании мироконтроллеров и почти никогда - при программировании компа.

+1 Я кстати тоже. Но особо "стремные" функции для МК все же прогоняю на ПК
Хотел было одно время поиграться с JTAG-ом но руководство деньгу зажало

[SviMik]

Очень, очень глупо. Нельзя привязываться к одному языку. Язык надо выбирать строго по задаче.

Си, Ассемблер... Мало? Зря. Всех в мире языков не выучить - только потратишь свою жизнь на их изучение, ничего не написав

Вручную сможешь их так переплести? А программа, написанная за 15 минут - сможет легко.

А если нити используют регистры? Как ты их переплетёшь, если регистров не хватит?
И, боюсь спросить, а как сравнения, циклы и условные переходы получатся после переплетения?

Существует определенный набор приемов написания (больше относится к C++, но можно применить и к Си), который практически гарантирует правильность программы, если она вообще скомпилируется.

Помимо правильности программы, есть и логические ошибки. Особенно при общении с внешними девайсами.
Никакой приём не поможет, если не так понял протокол устройства, принцип работы какой-то переферии, и т.п.

[lasers_AVSel]

 Сообщение от SviMik :

Помимо правильности программы, есть и логические ошибки. Особенно при общении с внешними девайсами.
Никакой приём не поможет, если не так понял протокол устройства, принцип работы какой-то переферии, и т.п.

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

Насчет переферии. Исследование непонятно как работающей переферии- это отдельная задача, лучше выполняется на спец. стенде или на худой конец на спец. прошивке. Хотя при наличии нормального даташита проблем обычно не возникает.

[Gall]

 Сообщение от SviMik :

Си, Ассемблер... Мало? Зря. Всех в мире языков не выучить - только потратишь свою жизнь на их изучение, ничего не написав

Ерунда. На изучение нового языка требуется 2-3 дня, не больше. Я около 50 языков знаю. Более того, я считаю, что знание экзотических языков совершенно необходимо, поскольку позволяет использовать приемы одного языка в другом языке (например, я могу писать на Си как на Хаскеле, поскольку знаю Хаскел).

 Сообщение от SviMik :

А если нити используют регистры? Как ты их переплетёшь, если регистров не хватит?
И, боюсь спросить, а как сравнения, циклы и условные переходы получатся после переплетения?

Надо придумать подходящий способ переплетения. С регистрами просто - надо поступить с ними так же, как я заменил nop на #delay. С ветвлениями - объясню ниже.

 Сообщение от SviMik :

Помимо правильности программы, есть и логические ошибки. Особенно при общении с внешними девайсами.
Никакой приём не поможет, если не так понял протокол устройства, принцип работы какой-то переферии, и т.п.

Да, и поэтому программу следует строить так, чтобы логических ошибок "по глупости" не могло быть, а ошибки "по непониманию" легко устранялись. В первую очередь для этого надо рассмотреть ВСЕ возможные ситуации, а в программе с ветвлениями это нереально (каждый if удваивает число ситуаций).

Именно это рождает событийный стиль программирования. Вместо того, чтобы пытаться понять, какие ситуации программа может создать, нужно изначально придумать список всех возможных ситуаций. Затем в программе просто перечисляются все эти ситуации, и для каждой указывается действие. Это избавляет от извечной головной боли при переделке программ. Выяснив, что я неправильно понял документацию, я исправлю в программе всего две-три строчки, и эти две-три строчки полностью перекроят логику программы. В результате я потрачу 5 минут на то, что могло бы занять несколько дней.

Такой подход одновременно избавляет от ветвлений как таковых (вот ответ про ветвления). Большие ветвления if...else заменяются максимум на однострочные - вида if(x) do(); - а справиться с ними гораздо легче, чем с большим переплетением инструкций. То же самое происходит и с циклами. В Хаскеле, например, вообще нет циклов, и это не мешает на нем программировать. В прошивке всегда есть главный цикл, и использовать можно его.

Здесь возможно справедливое замечание - а не будет ли полученная программа неэффективной? В принципе при написании на Ассемблере это вполне возможно. На Си такой проблемы обычно нет, там есть оптимизатор. Но иногда программисту хочется избавить себя от лишней работы настолько, что оптимизатору не справиться. В этом случае надо опять использовать метапрограммирование - написать программку, которая построит ветвления из списка состояний. Использовать для этого можно любой язык, хоть бейсик, но наиболее удобны python, ruby, perl, может быть php и m4.

Вообще программирование микроконтроллеров (аналогичный ему пример с больших компов - написание сетевых демонов, серверов) - достаточно частный пример, в котором именно событийный подход и метапрограммирование оказываются наилучшими. Другие задачи решаются иначе. Банальная, но очень важная рекомендация на этот счет звучит так: ни в коем случае нельзя привязываться к какому-то одному языку и к какому-то одному подходу в написании. Если уж совершенно не хочется учить много разных языков, то есть необходимый минимум - это Haskell (или Lisp) и часть Perl - минимальный набор команд + регулярные выражения. Из литературы - неплохо прочитать "Искусство программирования" Кнута и совершенно необходимо - "Алгоритмы и структуры данных" Вирта.

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

Вот пример задачки. К микроконтроллеру ATmega32 подключен стандартный текстовой дисплейчик, скажем, 2x16 символов, и клавиатурка от телефона (тупо кнопки на порты). Никакой другой периферии (в том числе памяти) нету. Требуется реализовать ввод текста T9 со словарем на 10-20 тысяч слов. Для усложнения задачки положим, что процессор работает на очень низкой частоте - например, 32768 Гц от часового кварца. Разрешима ли задача, и если да, то как? (Я давал эту задачу студентам на лекциях, когда преподавал в УПИ, и в принципе первокурсники после моих лекций справились с нею.)

[SviMik]

Вот пример задачки.

10-20 тысяч слов не проблема, если по ним построен правильный индекс (или, более обощённо - использован правильный формат хранения, не требующий перебора всей таблицы).

Если уж совершенно не хочется учить много разных языков, то есть необходимый минимум - это Haskell (или Lisp) и часть Perl - минимальный набор команд + регулярные выражения.

Хм, а при чём тут перл? Не под мк же на нём писать.
Если уж речь пошла обо всех языках (не только для AVR), то ещё я знаю php, STL (контроллеры сименса S7-200), ST (контроллеры Festo), FBD (контроллеры сименса LOGO).
Но 50 языков - это жесть. Я бы лопнул, изучить столько

На изучение нового языка требуется 2-3 дня, не больше.

Изучение - понятие растяжимое. Можно разобрать Hello world на Си за пять минут, но это не значит "изучил Си". И за 2-3 дня тоже изучишь только основной синтаксис и принцип написания, но всё равно до настоящего "изучил" вряд ли за 2-3 дня можно дойти. Это будет "имею представление".

Ладно, знаешь, с чем я не согласен? С тем, что ты в теме про Си расписываешь, что надо пользоваться любыми языками, кроме самого Си

[lasers_AVSel]

 Сообщение от SviMik :

10-20 тысяч слов не проблема, если по ним построен правильный индекс (или, более обощённо - использован правильный формат хранения, не требующий перебора всей таблицы).

Ответ неверный, в 32к 10-20тыс слов не влезет, и на 32768Гц на поиск уйдут часы

[Gall]

 Сообщение от AVSel :

Ответ неверный, в 32к 10-20тыс слов не влезет, и на 32768Гц на поиск уйдут часы

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

Этот алгоритм называется "DAWG" (Directed Acyclic Word Graph). Помимо T9, он широко используется в программах проверки правописания, разгадывания и составления россвордов. Впервые он был предложен в 1988 году как алгоритм для игры в Scrabble в статье http://www.cs.cmu.edu/afs/c... .

Мои студенты после объяснений алгоритма trie смогли самостоятельно разработать алгоритм dawg.

[Gall]

 Сообщение от SviMik :

10-20 тысяч слов не проблема, если по ним построен правильный индекс (или, более обощённо - использован правильный формат хранения, не требующий перебора всей таблицы).

А можно ли такой правильный формат построить? 10-20 тысяч слов надо уложить в 10-20 тысяч байт, то есть примерно по байту на слово. Ой ли? Даже rar так не жмет.

 Сообщение от SviMik :

Хм, а при чём тут перл? Не под мк же на нём писать.

Перл - замечательный язык для написания генрированного кода на Си. PHP (в режим командной строки, а не веба) - тоже. Если возникает необходимость написать для МК сложную программу, то можно сделать программу на PHP, которая напишет программу на Си.

Что касается большого многообразия языков, то тут важно, чтобы языки были совершенно разными по идеологии. PHP слишком похож на Си - да, в нем есть eval и можно организовать лямбда-выражения легче, чем на Си, но тем не менее написанию лямбда-выражений на нем не научишься. А жаль. Ведь на Си тоже можно сделать лямбду, но лямбда на Си делается так неочевидно, что ее "по наитию" никто никогда не напишет. Надо целенаправленно хотеть эту лямбду сделать. А для этого надо для начала владеть ею.

 Сообщение от SviMik :

Изучение - понятие растяжимое. Можно разобрать Hello world на Си за пять минут, но это не значит "изучил Си". И за 2-3 дня тоже изучишь только основной синтаксис и принцип написания, но всё равно до настоящего "изучил" вряд ли за 2-3 дня можно дойти. Это будет "имею представление".

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

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

 Сообщение от SviMik :

Ладно, знаешь, с чем я не согласен? С тем, что ты в теме про Си расписываешь, что надо пользоваться любыми языками, кроме самого Си

Си - основной язык для написания. Тем не менее, программу на Си необязательно писать руками от и до; можно использовать вспомогательные инструменты (в том числе и самодельные, написанные на любом удобном языке), которые эту программу правильно скомпонуют. Вот вкратце суть всего флейма про другие языки.

Еще хотелось бы подчеркнуть, что изучение разных языков (хотя бы поверхностное, на уровне Hello World) дает представление о том, КАК ЕЩЕ можно написать ту же программу. Языки ведь разные есть. В Haskell нет циклов, например, вместо них рекурсия, и нет исполнения строка за строкой - там программа пишется в алгебраическом виде. В Brainfuck всего 6 команд, тем не менее он тьюринговски полон. Есть язык, в котором программа представляет собой bitmap-картинку, по которой надо ходить, а очередное действие определяется цветом. Некоторые из этих языков практические, некоторые - чисто эзотерические (то есть просто для демонстрации, что так тоже можно). Но в любом случае их изучение полезно для раскрепощения сознания, а то ведь если из инструментов владеть только молотком, то все проблемы будут казаться гвоздями...

[SviMik]

Никаких словарей и индексов не надо делать вообще. Достаточно построить один большой конечный автомат с приблизительно 100 тыс. состояниями.

А варианты с несколькими словами на комбинацию он поддерживает?
А такой автомат можно обучить новым словам? Если уж говорить о полноценном Т9 - это ещё и добавление новых слов.

[lasers_AVSel]

 Сообщение от Gall :

Неверно, задача разрешима.

Так я и не говорил что это не возможно Задача не решается через базу.

 Сообщение от SviMik :

А варианты с несколькими словами на комбинацию он поддерживает?
А такой автомат можно обучить новым словам? Если уж говорить о полноценном Т9 - это ещё и добавление новых слов.

Варианты с несколькими словами запросто, а добавление новых слов- нет. Хотя если попытатся самообучаемый автомат сделать...

[SviMik]

поиск очердной буквы при нажатии клавиши занимает около 10 тактов

Почему "очередной буквы"? По мере ввода, варианты слов могут меняться целиком, с нажатием каждой клавиши.

[Gall]

 Сообщение от SviMik :

Почему "очередной буквы"? По мере ввода, варианты слов могут меняться целиком, с нажатием каждой клавиши.

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

Обучение новым словам как правило делается за счет ОТДЕЛЬНОГО словаря. Дело в том, что в момент ПОСТРОЕНИЯ оптимальных графов DAWG требуется около 200 мегабайт памяти, и сделать это на микроконтроллере нельзя. Поэтому в мобильниках держат два словаря - собственно DAWG в прошивке и отдельный словарь обучения, а поиск просто делается параллельно по обоим. Словарь обучения во многих мобильниках не DAWG, а просто trie, его проще строить, а пользователь вряд ли вобьет много слов.

К чему все это было. К тому, что с бухты-барахты такую штуку не придумать. Она требует целенаправленного изучения. Таких вещей в программировании много. И самое неприятное, что они зачастую встречаются даже в "простейших" программах (см. выше про ошибку в классической "Hello World"). Самое главное - вовремя заглянуть в справочник, если знаний математики не хватает на самостоятельное построение алгоритма. А знаний не хватит почти наверняка - их у выпускников матмеха с красным дипломом и то далеко не всегда хватает.

[SviMik]

Кстати про -O2 (UPD: да нет, даже с -Os прошивка толстая выходит).
Почему в листинге я вижу все функции клонированными?

void spi_send(char cData){
	/* Start transmission */
	SPDR = cData;
  5e:	80 e8       	ldi	r24, 0x80	; 128
  60:	8e bd       	out	0x2e, r24	; 46
	/* Wait for transmission complete */
	while(!(SPSR & (1<<SPIF))){}
  62:	0d b4       	in	r0, 0x2d	; 45
  64:	07 fe       	sbrs	r0, 7
  66:	fd cf       	rjmp	.-6      	; 0x62 <lcd_resetpos+0x6>
	SPCR = (1<<SPE)|(1<<MSTR);
}

void spi_send(char cData){
	/* Start transmission */
	SPDR = cData;
  68:	80 e4       	ldi	r24, 0x40	; 64
  6a:	8e bd       	out	0x2e, r24	; 46
	/* Wait for transmission complete */
	while(!(SPSR & (1<<SPIF))){}
  6c:	0d b4       	in	r0, 0x2d	; 45
  6e:	07 fe       	sbrs	r0, 7
  70:	fd cf       	rjmp	.-6      	; 0x6c <lcd_resetpos+0x10>

и так далее. Тоесть везде, где я вызываю spi_send(), он его вставляет целиком заново. Так и флеша не напасёшся
Я понимаю, что так быстрее, но не до такой же степени, чтоб 13 раз spi_send вставлять!

Что ещё удивительнее - а зачем он в листинг вставил spi_init два раза, если он вообще только 1 раз вызывается?

00000046 <spi_init>:

#include <avr/io.h>

void spi_init(void){
	/* Set MOSI and SCK output */
	PORTB = PORTB | (1<<3)|(1<<5);
  46:	85 b1       	in	r24, 0x05	; 5
  48:	88 62       	ori	r24, 0x28	; 40
  4a:	85 b9       	out	0x05, r24	; 5
	/* Enable SPI, Master, set clock rate fck/4 */
	SPCR = (1<<SPE)|(1<<MSTR);
  4c:	80 e5       	ldi	r24, 0x50	; 80
  4e:	8c bd       	out	0x2c, r24	; 44
}
  50:	08 95       	ret

<.........>

000000e8 <main>:

#include <avr/io.h>

void spi_init(void){
	/* Set MOSI and SCK output */
	PORTB = PORTB | (1<<3)|(1<<5);
  e8:	85 b1       	in	r24, 0x05	; 5
  ea:	88 62       	ori	r24, 0x28	; 40
  ec:	85 b9       	out	0x05, r24	; 5
	/* Enable SPI, Master, set clock rate fck/4 */
	SPCR = (1<<SPE)|(1<<MSTR);
  ee:	80 e5       	ldi	r24, 0x50	; 80
  f0:	8c bd       	out	0x2c, r24	; 44
  f2:	ff cf       	rjmp	.-2      	; 0xf2 <main+0xa>