8.  Экранные библиотеки и работа с видеопамятью.
     Терминал в UNIX с точки зрения программ - это файл.  Он представляет  собой  два
устройства:  при записи write() в этот файл осуществляется вывод на экран; при чтении
read()-ом из этого файла - читается информация с клавиатуры.
     Современные терминалы в определенном смысле являются устройствами  прямого  дос-
тупа:
-    информация может быть выведена в любое место экрана, а не только последовательно
     строка за строкой.
-    некоторые терминалы позволяют прочесть содержимое произвольной области экрана  в
     вашу программу.
Традиционные терминалы являются самостоятельными устройствами, общающимися с  компью-
тером  через линию связи. Протокол[*] общения образует систему команд терминала и может
быть различен для терминалов разных моделей. Поэтому библиотека работы с традиционным
терминалом должна решать следующие проблемы:
-    настройка на систему команд данного устройства, чтобы одна  и  та  же  программа
     работала на разных типах терминалов.
-    эмуляция недостающих в системе команд; максимальное использование  предоставлен-
     ных терминалом возможностей.
-    мимнимизация передачи данных через линию связи (для ускорения работы).
-    было бы полезно, чтобы библиотека предоставляла пользователю некоторые  логичес-
     кие  абстракции,  вроде  ОКОН  -  прямоугольных областей на экране, ведущих себя
     подобно маленьким терминалам.

     В UNIX эти задачи решает стандартная библиотека curses (а только первую задачу -
более  простая библиотека termcap). Для настройки на систему команд конкретного дисп-
лея  эти  библиотеки  считывают  описание  системы   команд,   хранящееся   в   файле
/etc/termcap.  Кроме них бывают и другие экранные библиотеки, а также существуют иные
способы работы с экраном (через видеопамять, см. ниже).
     В задачах данного раздела вам придется пользоваться библиотекой curses. При ком-
пиляции  программ эта библиотека подключается при помощи указания ключа -lcurses, как
в следующем примере:

    cc progr.c -Ox -o progr -lcurses -lm

Здесь  подключаются  две  библиотеки:  /usr/lib/libcurses.a  (работа  с  экраном)   и
/usr/lib/libm.a  (математические  функции,  вроде  sin, fabs).  Ключи для подключения
библиотек должны быть записаны в команде САМЫМИ ПОСЛЕДНИМИ. Заметим, что  стандартная
библиотека  языка  Си (содержащая системные вызовы, библиотеку stdio (функции printf,
scanf, fread, fseek, ...), разные часто употребляемые функции (strlen, strcat, sleep,
malloc,  rand,  ...))  /lib/libc.a  подключается  автоматически и не требует указания
ключа -lc.
     В начале своей программы вы должны написать директиву

    #include <curses.h>

подключающую файл /usr/include/curses.h, в котором описаны форматы данных, используе-
мых  библиотекой curses, некоторые предопределенные константы и.т.п. (это надо, чтобы
ваша программа пользовалась именно этими  стандартными  соглашениями).  Посмотрите  в
этот файл!
     Когда вы пользуетесь curses-ом, вы НЕ должны пользоваться функциями  стандартной
библиотеки stdio для непосредственного вывода на экран; так вы не должны пользоваться
____________________
   [*] Под протоколом в программировании подразумевают ряд соглашений двух сторон (сер-
вера  и  клиентов;  двух машин в сети (кстати, термин для обозначения машины в сети -
"host" или "site")) о формате (правилах оформления) и смысле  данных  в  передаваемых
друг  другу сообщениях.  Аналогия из жизни - человеческие речь и язык.  Речь всех лю-
дей состоит из одних и тех же звуков и может быть записана одними и теми  же  буквами
(а  данные  -  байтами).   Но  если  два человека говорят на разных языках - т.е. по-
разному конструируют фразы и интерпретируют звуки - они не поймут друг друга!





А. Богатырев, 1992-95                  - 349 -                              Си в UNIX

функциями printf, putchar.  Это происходит потому, что curses хранит  в  памяти  про-
цесса копию содержимого экрана, и если вы выводите что-либо на экран терминала обходя
функции библиотеки curses, то реальное содержимое экрана и  позиция  курсора  на  нем
перестают соответствовать хранимым в памяти, и библиотека curses начнет выводить неп-
равильное изображение.

       ПРОГРАММА
        |  |
        | CURSES---копия экрана
        | printw,addch,move
        |  |
        V  V
     библиотека STDIO --printf,putchar----> экран

Таким образом, curses является дополнительным "слоем" между вашей программой и  стан-
дартным выводом и игнорировать этот слой не следует.
     Напомним, что изображение, создаваемое при  помощи  библиотеки  curses,  сначала
формируется  в  памяти программы без выполнения каких-либо операций с экраном дисплея
(т.е. все функции wmove, waddch, waddstr,  wprintw  изменяют  только  ОБРАЗЫ  окон  в
памяти,  а  на экране ничего не происходит!).  И лишь только ПОСЛЕ того, как вы вызо-
вете функцию refresh() ("обновить"), все изменения происшедшие в окнах будут  отобра-
жены  на  экране  дисплея  (такое  одновременное  обновление всех изменившихся частей
экрана позволяет провести ряд оптимизаций).  Если вы забудете сделать refresh - экран
останется  неизменным. Обычно эту функцию вызывают перед тем, как запросить у пользо-
вателя какой-либо ввод с клавиатуры, чтобы пользователь увидел текущую "свежую"  кар-
тинку.   Хранение содержимого окон в памяти программы позволяет ей считывать содержи-
мое окон, тогда как большинство обычных терминалов не  способны  выдать  в  компьютер
содержимое какой-либо области экрана.

     Общение с терминалом через линию связи (или вообще через последовательный прото-
кол) является довольно медленным.  На персональных компьютерах существует другой спо-
соб работы с экраном: через прямой доступ в так называемую "видеопамять" -  специаль-
ную  область  памяти  компьютера, содержимое которой аппаратно отображается на экране
консоли.  Работа с экраном превращается для программиста в  работу  с  этим  массивом
байт (запись/чтение).  Программы, пользующиеся этим способом, просты и работают очень
быстро (ибо доступ к памяти черезвычайно быстр, и сделанные в ней изменения "проявля-
ются"  на  экране почти мгновенно). Недостаток таких программ - привязанность к конк-
ретному типу машины. Эти программы немобильны и не могут работать ни на обычных  тер-
миналах  (подключаемых к линии связи), ни на машинах с другой структурой видеопамяти.
Выбор между "традиционной" работой с экраном и прямым доступом  (фактически  -  между
мобильностью  и  скоростью)  -  вопрос  принципиальный, тем не менее принятие решения
зависит только от вас.  Видеопамять IBM PC в текстовом режиме 80x25 16  цветов  имеет
следующую структуру:

       struct symbol{       /* IBM PC family           */
            char chr;       /* код символа             */
            char attr;      /* атрибуты символа (цвет) */
       } mem[ 25 ] [ 80 ];  /* 25 строк по 80 символов */


               Структура байта атрибутов:
     -------------------------------------------
     | 7   | 6 | 5 | 4 | 3         | 2 | 1 | 0 | # бита
     ------------------|------------------------
     |blink| R | G | B | intensity | r | g | b | цвет
     ------------------|------------------------
     background (фон)  | foreground (цвет букв)

    R - red (красный) G - green (зеленый) B - blue (синий)
    blink     - мерцание букв (не фона!)
    intensity - повышенная яркость



А. Богатырев, 1992-95                  - 350 -                              Си в UNIX

Координатная система на экране: верхний левый угол экрана имеет координаты (0,0), ось
X горизонтальна, ось Y вертикальна и направлена сверху вниз.
     Цвет символа получается смешиванием  3х  цветов:  красного,  зеленого  и  синего
(электронно-лучевая  трубка  дисплея  имеет 3 электронные пушки, отвечающие этим цве-
там).  Кроме того, допустимы более яркие цвета. 4 бита задают комбинацию 3х  основных
цветов и повышенной яркости. Образуется 2**4=16 цветов:

                 I R G B   номер цвета
    BLACK        0 0 0 0    0    черный
    BLUE         0 0 0 1    1    синий
    GREEN        0 0 1 0    2    зеленый
    CYAN         0 0 1 1    3    циановый (серо-голубой)
    RED          0 1 0 0    4    красный
    MAGENTA      0 1 0 1    5    малиновый
    BROWN        0 1 1 0    6    коричневый
    LIGHTGRAY    0 1 1 1    7    светло-серый (темно-белый)

    DARKGRAY     1 0 0 0    8    темно-серый
    LIGHTBLUE    1 0 0 1    9    светло-синий
    LIGHTGREEN   1 0 1 0   10    светло-зеленый
    LIGHTCYAN    1 0 1 1   11    светло-циановый
    LIGHTRED     1 1 0 0   12    ярко-красный
    LIGHTMAGENTA 1 1 0 1   13    ярко-малиновый
    YELLOW       1 1 1 0   14    желтый
    WHITE        1 1 1 1   15    (ярко)-белый

     Физический адрес видеопамяти IBM PC в цветном алфавитно-цифровом режиме  (80x25,
16  цветов)  равен 0xB800:0x0000. В MS DOS указатель на эту память можно получить при
помощи макроса make far pointer: MK_FP (это должен быть far или huge указатель!).   В
XENIX[*] указатель получается при помощи системного вызова ioctl, причем  система  пре-
доставит  вам  виртуальный адрес, ибо привелегия работы с физическими адресами в UNIX
принадлежит только системе.  Работу с экраном в XENIX вы  можете  увидеть  в  примере
"осыпающиеся буквы".

8.1.

    /*#! /bin/cc  fall.c -o fall -lx
     *      "Осыпающиеся буквы".
     *      Использование видеопамяти IBM PC в ОС XENIX.
     *      Данная программа иллюстрирует доступ к экрану
     *      персонального компьютера как к массиву байт;
     *      все изменения в массиве немедленно отображаются на экране.
     *          Функция nap() находится в библиотеке -lx
     *      Показана также работа с портами IBM PC при помощи ioctl().
     */
    #include <stdio.h>
    #include <fcntl.h>         /* O_RDWR */
    #include <signal.h>
    #include <ctype.h>
    #include <sys/types.h>
    #include <sys/at_ansi.h>
    #include <sys/kd.h>        /* for System V/4 and Interactive UNIX only */
    /*#include <sys/machdep.h>    for XENIX and SCO UNIX only */
    #include <sys/sysmacros.h>


____________________
   [*] XENIX - (произносится "зиникс") версия UNIX для IBM PC,  первоначально  разрабо-
танная фирмой Microsoft и поставляемая фирмой Santa Cruz Operation (SCO).





А. Богатырев, 1992-95                  - 351 -                              Си в UNIX

    #ifdef M_I386
    # define far    /* на 32-битной машине far не требуется */
    #endif

    char far *screen;   /* видеопамять как массив байт */
                        /* far - "длинный" (32-битный) адрес(segment,offset) */
    int     segm;       /* сегмент с видеопамятью */

    #define COLS  80        /* число колонок на экране */
    #define LINES 25        /* число строк */

    #define DELAY 20        /* задержка (миллисекунд) */
    int  ega;               /* дескриптор для доступа к драйверу EGA */


    /* структура для обмена с портами */
    static struct port_io_struct    PORT[ 4 /* не более 4 за раз */] = {
           /* операция       номер порта   данные */
           /*   .dir           .port        .data */

     /* Переустановить flip/flop:
      * заставить порт 0x3C0 ожидать пары адрес/значение
      * при последовательной записи байтов в этот порт.
      */
        {   IN_ON_PORT,     0x3DA,       -1               },
           /* IN-чтение */
     /* Теперь 3c0 ожидает пары адрес/значение */
        {   OUT_ON_PORT,    0x3C0,       -1 /* адрес */   },
        {   OUT_ON_PORT,    0x3C0,       -1 /* значение*/ },
           /* OUT-запись */
     /* переинициализировать дисплей, установив бит #5 порта 3c0 */
        {   OUT_ON_PORT,    0x3C0,       0x20             }
    };


    void closescr(nsig){             /* конец работы */
            setbgcolor(0);  /* установить черный фон экрана */
            exit(0);
    }


    /* получение доступа к видеопамяти адаптера VGA/EGA/CGA */
    void openscr () {
        static struct videodev {
            char *dev; int mapmode;
        } vd[] = {
            { "/dev/vga", MAPVGA },
            { "/dev/ega", MAPEGA },
            { "/dev/cga", MAPCGA },
            { NULL,       -1     }
        }, *v; /* устройство для доступа к видеоадаптеру */
        for(v=vd; v->dev;v++ )
            if((ega = open (v->dev, O_RDWR)) >= 0 ) goto ok;
        fprintf( stderr, "Can't open video adapter\n" );
        exit(1);









А. Богатырев, 1992-95                  - 352 -                              Си в UNIX

    ok:
        /* fprintf(stderr, "Adapter:%s\n", v->dev); */
        /* получить адрес видеопамяти и доступ к ней */
    #ifdef M_I386
        screen = (char *) ioctl (ega, v->mapmode, 0);
    #else
        segm = ioctl (ega, v->mapmode, 0);
        screen = sotofar (segm, 0); /* (segment,offset) to far pointer */
    #endif
        signal( SIGINT, closescr );
    }


    /* макросы для доступа к байтам "символ" и "атрибуты"
     * в координатах (x,y) экрана.
     */
    #define GET(x,y)        screen[ ((x) + (y) * COLS ) * 2 ]
    #define PUT(x,y, c)     screen[ ((x) + (y) * COLS ) * 2 ]  = (c)

    #define GETATTR(x,y)        screen[ ((x) + (y) * COLS ) * 2 + 1 ]
    #define PUTATTR(x,y, a)     screen[ ((x) + (y) * COLS ) * 2 + 1 ] = (a)

    /* символ изображается как черный пробел ? */
    #define white(c,a) ((isspace(c) || c==0) && (attr & 0160)==0)


    /* установить цвет фона экрана */
    void setbgcolor( color ){
         PORT[1].data = 0;  /* регистр номер 0 палитры содержит цвет фона */
         /* всего в палитре 16 регистров (0x00...0xFF) */

         PORT[2].data = color ;
         /* новое значение цвета, составленное как битовая маска
          *  RGBrgb  (r- красный, g- зеленый, b- синий, RGB- дополнительные
          *  тусклые цвета)
          */

         /* выполнить обмены с портами */
         if( ioctl( ega, EGAIO, PORT ) < 0 ){
               fprintf( stderr, "Can't out port\n" );
               perror( "out" );
         }
    }





















А. Богатырев, 1992-95                  - 353 -                              Си в UNIX

    void main(ac, av) char **av;{
            void fall();

            openscr();
            if( ac == 1 ){
                setbgcolor(020);    /* темно-зеленый фон экрана */
                fall();             /* осыпание букв */
            } else {
                if(*av[1] == 'g')
    /* Установить режим адаптера graphics 640x350 16-colors */
                     ioctl( ega, SW_CG640x350, NULL);
    /* Если вы хотите получить адрес видеопамяти в графическом режиме,
     * вы должны СНАЧАЛА включить этот режим,
     * ЗАТЕМ сделать screen=ioctl(ega, v->mapmode, NULL);
     * и ЕЩЕ РАЗ сделать включение графического режима.
     */
    /* Установить режим адаптера text 80x25 16-colors       */
                else ioctl( ega, SW_ENHC80x25, NULL);
            }
            closescr(0);
    }


    /* осыпать буквы вниз */
    void fall(){
            register i, j;
            int rest;
            int nextcol;
            int n;
            int changed = 1;        /* не 0, если еще не все буквы опали */
            char mask [ COLS ];

            while( changed ){
               changed = 0;
               for( i = 0 ; i < COLS ; i++ )
                    mask[ i ] = 0;

               for( i = 0 ; i < COLS ; i++ ){
                    rest = COLS - i;   /* осталось осыпать колонок */
                    nextcol = rand() % rest;


                    j = 0;  /* индекс в mask */
                    n = 0;  /* счетчик */

                    for(;;){
                            if( mask[j] == 0 ){
                                    if( n == nextcol ) break;
                                    n++;
                            } j++;
                    }

                    changed += fallColumn( j );
                    mask[j] = 1;
               }
            }
    }







А. Богатырев, 1992-95                  - 354 -                              Си в UNIX

    /* осыпать буквы в одном столбце */
    int fallColumn( x ){
            register int y;
            char ch, attr;
            int firstspace = (-1);
            int firstnospace = (-1);

    Again:
            /* find the falled array */
            for( y=LINES-1; y >= 0 ; y-- ){

                    ch = GET( x, y );
                    attr = GETATTR( x,y );

                    if( white(ch, attr)){
                        firstspace = y;
                        goto FindNoSpace;
                    }
            }


    AllNoSpaces:
            return 0;       /* ничего не изменилось */
    FindNoSpace:            /* найти не пробел */
            for( ; y >= 0 ; y-- ){

                    ch = GET( x, y );
                    attr = GETATTR( x, y );

                    if( !white(ch, attr)){
                            firstnospace = y;
                            goto Fall;
                    }
            }


    AllSpaces:       /* в данном столбце все упало */
            return 0;
    Fall:
            /* "уронить" букву */
            for( y = firstnospace ; y < firstspace ; y++ ){
                    /* переместить символ на экране на одну позицию вниз */
                    ch   = GET( x, y );
                    attr = GETATTR( x, y );

                    PUT( x, y, 0 );
                    PUTATTR( x, y, 0 );

                    PUT( x, y+1 , ch );
                    PUTATTR( x, y+1, attr );

                    nap( DELAY );   /* подождать DELAY миллисекунд */
            }
            return 1;               /* что-то изменилось */
    }


8.2.  Для работы может оказаться более удобным иметь указатель на видеопамять как  на
массив структур. Приведем пример для системы MS DOS:





А. Богатырев, 1992-95                  - 355 -                              Си в UNIX

    #include <dos.h>  /* там определено MK_FP */
    char far *screen =
             MK_FP(0xB800 /*сегмент*/, 0x0000 /*смещение*/);
    struct symb{
            char chr; char attr;
    } far *scr, far *ptr;
    #define COLS  80        /* число колонок */
    #define LINES 25        /* число строк   */
    #define SCR(x,y)   scr[(x) + COLS * (y)]
    /* x из 0..79, y из 0..24 */


    void main(){
      int x, y;
      char c;
      scr = (struct symb far *) screen;
      /* или сразу
       * scr = (struct symb far *) MK_FP(0xB800,0x0000);
       */


      /* переписать строки экрана справа налево */
      for(x=0; x < COLS/2; x++ )
        for( y=0; y < LINES; y++ ){
             c = SCR(x,y).chr;
             SCR(x,y).chr = SCR(COLS-1-x, y).chr;
             SCR(COLS-1-x, y).chr = c;
        }


      /* сделать цвет экрана: желтым по синему */
      for(x=0; x < COLS; x++)
        for(y=0; y < LINES; y++)
             SCR(x,y).attr = (0xE | (0x1 << 4));
                        /* желтый + синий фон */

      /* прочесть любую кнопку с клавиатуры (пауза) */
      (void) getch();
    }

И, наконец, еще удобнее работа с видеопамятью как с двумерным массивом структур:

    #include <dos.h>  /* MS DOS */
    #define COLS 80
    #define LINES 25
    struct symb {
           char chr; char attr;
    } (far *scr)[ COLS ] = MK_FP(0xB800, 0);


    void main(void){
         register x, y;
         for(y=0; y < LINES; y++)
             for(x=0; x < COLS; ++x){
                 scr[y][x].chr = '?';
                 scr[y][x].attr = (y << 4) | (x & 0xF);
             }
         getch();
    }

Учтите, что при работе с экраном через видеопамять, курсор не  перемещается!  Если  в



А. Богатырев, 1992-95                  - 356 -                              Си в UNIX

обычной  работе  с  экраном  текст выводится в позиции курсора и курсор автоматически
продвигается, то здесь курсор будет оставаться на своем прежнем месте. Для  перемеще-
ния  курсора  в  нужное вам место, вы должны его поставить явным образом по окончании
записи в видеопамять (например, обращаясь к портам видеоконтроллера).
     Обратите внимание, что спецификатор модели памяти far должен  указываться  перед
КАЖДЫМ  указателем (именно для иллюстрации этого в первом примере описан неиспользуе-
мый указатель ptr).

8.3.  Составьте программу сохранения содержимого экрана IBM PC (видеопамяти) в  текс-
товом режиме в файл и обратно (в системе XENIX).

8.4.  Пользуясь прямым доступом в видеопамять, напишите функции для спасения  прямоу-
гольной области экрана в массив и обратно. Вот функция для спасения в массив:

    typedef struct {
       short xlen, ylen;
       char  *save;
    } Pict;
    extern void *malloc(unsigned);

    Pict *gettext (int x, int y, int xlen, int ylen){
       Pict *n   = (Pict *) malloc(sizeof *n);
       register char *s; register i, j;

       n->xlen = xlen; n->ylen = ylen;
       s = n->save = (char *) malloc( 2 * xlen * ylen );
       for(i=y; i < y+ylen; i++)
            for(j=x; j < x+xlen; j++){
                *s++ = SCR(j,i).chr ;
                *s++ = SCR(j,i).attr;
            }
       return n;
    }

Добавьте проверки на корректность xlen, ylen (в пределах экрана).   Напишите  функцию
puttext для вывода спасенной области обратно; функцию free(buf) лучше в нее не встав-
лять.

    void puttext (Pict *n, int x, int y){
       register char *s = n->save;
       register i, j;
       for(i=y; i < y + n->ylen; i++)
            for(j=x; j < x + n->xlen; j++){
                SCR(j,i).chr  = *s++;
                SCR(j,i).attr = *s++;
            }
    }
    /* очистка памяти текстового буфера */
    void deltext(Pict *n){ free(n->save); free(n); }

Приведем еще одну полезную функцию, которая может вам пригодиться - это аналог printf
при прямой работе с видеопамятью.

    #include <stdarg.h>
    /* текущий цвет: белый по синему */
    static char currentColor = 0x1F;

    int videoprintf (int x, int y, char *fmt, ...){
        char buf[512], *s;
        va_list var;




А. Богатырев, 1992-95                  - 357 -                              Си в UNIX

        /* clipping (отсечение по границам экрана) */
        if( y < 0 || y >= LINES ) return x;

        va_start(var, fmt);
        vsprintf(buf, fmt, var);
        va_end(var);

        for(s=buf; *s; s++, x++){
            /* отсечение */
            if(x < 0    ) continue;
            if(x >= COLS) break;
            SCR(x,y).chr = *s;
            SCR(x,y).attr = currentColor;
        }
        return x;
    }
    void setcolor (int col){ currentColor = col; }


8.5.  Пользуясь написанными функциями, реализуйте функции  для  "выскакивающих"  окон
(pop-up window):

    Pict *save;
      save = gettext (x,y,xlen,ylen);

      // ... рисуем цветными пробелами прямоугольник с
      // углами (x,y) вверху-слева и (x+xlen-1,y+ylen-1)
      // внизу-справа...

      // ...рисуем некие таблицы, меню, текст в этой зоне...

      // стираем нарисованное окно, восстановив то изображение,
      // поверх которого оно "всплыло".
      puttext (save,x,y);
      deltext (save);

Для начала напишите "выскакивающее" окно с сообщением; окно должно исчезать по  нажа-
тию любой клавиши.

       c = message(x, y,   text);

Размер окна вычисляйте по длине строки text. Код клавиши возвращайте в качестве  зна-
чения функции.
     Теперь сделайте text массивом строк: char *text[]; (последняя строка - NULL).

8.6.  Сделайте так, чтобы "выскакивающие" окна имели тень. Для этого надо сохранить в
некоторый буфер атрибуты символов (сами символы не надо!), находящихся на местах $:

            ##########
            ##########$
            ##########$
             $$$$$$$$$$

а затем прописать этим символам на экране атрибут 0x07 (белый по черному). При стира-
нии  окна (puttext-ом) следует восстановить спасенные атрибуты этих символов (стереть
тень). Если окно имеет размер xlen*ylen, то размер буфера равен xlen+ylen-1 байт.

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





А. Богатырев, 1992-95                  - 358 -                              Си в UNIX

8.8.  Напишите "выскакивающее" окно, которое проявляется на экране как бы  расширяясь
из точки:

                           ##############
                ######     ##############
       ###      ######     ##############
                ######     ##############
                           ##############

Вам следует написать функцию box(x,y,width,height), рисующую цветной прямоугольник  с
верхним  левым  углом  (x,y)  и размером (width,height). Пусть конечное окно задается
углом (x0,y0) и размером (W,H). Тогда "вырастание" окна описывается таким алгоритмом:

    void zoom(int x0, int y0, int W, int H){
        int x, y, w, h, hprev; /* промежуточное окно */
        for(hprev=0, w=1; w < W; w++){
            h = H * w; h /= W;  /* W/H == w/h */
            if(h == hprev) continue;
            hprev = h;
            x = x0 + (W - w)/2; /* чтобы центры окон */
            y = y0 + (H - h)/2; /* совпадали         */
            box(x, y, w, h);
            delay(10);      /* задержка 10 миллисек. */
        }
        box(x0, y0, W, H);
    }


8.9.  Составьте библиотеку функций, аналогичных библиотеке curses, для ЭВМ  IBM PC  в
ОС XENIX.  Используйте прямой доступ в видеопамять.

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

      carry(n, from, to, by) = if( n > 0 ){
                    carry( n-1, from, by, to );
                    перенесиОдинДиск( from, to );
                    carry( n-1, by,   to, from );
                 }
      Вызов:     carry( n, 0, 1, 2 );
      n    - сколько дисков перенести (n > 0).
      from - откуда (номер стержня).
      to   - куда.
      by   - при помощи (промежуточный стержень).

n дисков потребуют (2**n)-1 переносов.

8.11.  Напишите программу, ищущую выход из лабиринта ("червяк в  лабиринте").   Лаби-
ринт  загружается  из  файла  .maze (не забудьте про расширение табуляций!). Алгоритм
имеет рекурсивную природу и выглядит примерно так:

    #include <setjmp.h>
    jmp_buf jmp; int found = 0;

    maze(){ /* Это головная функция */
        if( setjmp(jmp) == 0 ){ /* начало */
            if( неСтенка(x_входа, y_входа))
                GO( x_входа, y_входа);



А. Богатырев, 1992-95                  - 359 -                              Си в UNIX

        }
    }
    GO(x, y){       /* пойти в точку (x, y) */
        if( этоВыход(x, y)){ found = 1;  /* нашел выход */
            пометить(x, y); longjmp(jmp, 1);}
        пометить(x, y);
        if( неСтенка(x-1,y)) GO(x-1, y);  /* влево */
        if( неСтенка(x,y-1)) GO(x, y-1);  /* вверх */
        if( неСтенка(x+1,y)) GO(x+1, y);  /* вправо */
        if( неСтенка(x,y+1)) GO(x, y+1);  /* вниз   */
        снятьПометку(x, y);
    }
    #define пометить(x, y)     лабиринт[y][x] = '*'
    #define снятьПометку(x, y) лабиринт[y][x] = ' '
    #define этоВыход(x, y)   (x == x_выхода && y == y_выхода)
    /* можно искать "золото":  (лабиринт[y][x] == '$') */

    неСтенка(x, y){ /* стенку изображайте символом @ или # */
      if( координатыВнеПоля(x, y)) return 0; /*край лабиринта*/
      return (лабиринт[y][x] == ' ');
    }

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

8.12.  Используя библиотеку termcap напишите функции для:
-    очистки экрана.
-    позиционирования курсора.
-    включения/выключения режима выделения текста инверсией.

8.13.  Используя написанные функции, реализуйте программу выбора в  меню.   Выбранную
строку выделяйте инверсией фона.

    /*#!/bin/cc termio.c -O -o termio -ltermcap
     * Смотри   man termio, termcap и screen.
     *              Работа с  терминалом в стиле System-V.
     *              Работа с  системой команд терминала через /etc/termcap
     *              Работа со временем.
     *              Работа с  будильником.
     */

    #include <stdio.h>              /* standard input/output */
    #include <sys/types.h>          /* system typedefs */
    #include <termio.h>             /* terminal input/output */
    #include <signal.h>             /* signals */
    #include <fcntl.h>              /* file control */
    #include <time.h>               /* time structure */

    void setsigs(), drawItem(), drawTitle(), prSelects(), printTime();















А. Богатырев, 1992-95                  - 360 -                              Си в UNIX

    /* Работа с описанием терминала TERMCAP ---------------------------------*/
    extern char *getenv ();         /* получить переменную окружения         */
    extern char *tgetstr ();        /* получить строчный описатель /termcap/ */
    extern char *tgoto ();          /* подставить %-параметры      /termcap/ */

    static char Tbuf[2048],         /* буфер для описания терминала, обычно 1024 */
      /* Tbuf[] можно сделать локальной автоматической переменной
       * в функции tinit(), чтобы не занимать место */
                Strings[256],       /* буфер для расшифрованных описателей */
               *p;                  /* вспомогательная перем.              */
    char   *tname;                  /* название типа терминала             */
    int     COLS,                   /* число колонок экрана                */
            LINES;                  /* число строк экрана                  */
    char   *CM;                     /* описатель: cursor motion            */
    char   *CL;                     /* описатель: clear screen             */
    char   *CE;                     /* описатель: clear end of line        */
    char   *SO,
           *SE;                     /* описатели: standout Start и End     */
    char   *BOLD,
           *NORM;                   /* описатели: boldface and NoStandout  */
    int    BSflag;                  /* можно использовать back space '\b'  */


    void tinit () {      /* Функция настройки на систему команд дисплея */
        p = Strings;
        /* Прочесть описание терминала в Tbuf */
        switch (tgetent (Tbuf, tname = getenv ("TERM"))) {
             case -1:
                printf ("Нет файла TERMCAP (/etc/termcap).\n");
                exit (1);
            case 0:
                printf ("Терминал %s не описан.\n", tname);
                exit (2);
            case 1:
                break;              /* OK */
        }
        COLS =  tgetnum ("co");     /* Прочесть числовые описатели. */
        LINES = tgetnum ("li");

        CM = tgetstr ("cm", &p);    /* Прочесть строчные описатели.      */
        CL = tgetstr ("cl", &p);    /* Описатель дешифруется и заносится */
        CE = tgetstr ("ce", &p);    /* в массив по адресу p. Затем       */
        SO = tgetstr ("so", &p);    /* указатель p продвигается на       */
        SE = tgetstr ("se", &p);    /* свободное место, а адрес расшиф-  */
        BOLD = tgetstr ("md", &p);  /* рованной строки выдается из ф-ции */
        NORM = tgetstr ("me", &p);

        BSflag = tgetflag( "bs" );  /* Узнать значение флажка:
                 1 - есть, 0 - нет   */
    }














А. Богатырев, 1992-95                  - 361 -                              Си в UNIX

    /* Макрос, внесенный в функцию.
       Дело в том, что tputs в качестве третьего аргумента
       требует имя функции, которую она вызывает в цикле: (*f)(c);
       Если подать на вход макрос, вроде putchar,
       а не адрес входа в функцию, мы
       и не достигнем желанного эффекта,
       и получим ругань от компилятора.
    */
    void put (c) char c;
    {   putchar (c);  }


    /* очистить экран */
    void clearScreen () {
        if (CL == NULL)      /* Функция tputs() дорасшифровывает описатель */
            return;          /* (обрабатывая задержки) и выдает его        */
        tputs (CL, 1, put);  /* посимвольно ф-цией put(c) 1 раз            */
        /* Можно выдать команду не 1 раз, а несколько: например если это   */
        /* команда сдвига курсора на 1 позицию влево '\b'                  */
    }


    /* очистить конец строки, курсор остается на месте */
    void clearEOL () {  /* clear to the end of line */
        if (CE == NULL)
            return;
        tputs (CE, 1, put);
    }


    /* позиционировать курсор */
    void gotoXY (x, y) {  /* y - по вертикали СВЕРХУ-ВНИЗ. */
        if (x < 0 || y < 0 || x >= COLS || y >= LINES) {
            printf ("Точка (%d,%d) вне экрана\n", x, y);
            return;
        }
        /* CM - описатель, содержащий 2 параметра. Подстановку параметров
         * делает функция tgoto() */
        tputs (tgoto (CM, x, y), 1, put);
    }


    /* включить выделение */
    void standout () {
        if (SO) tputs (SO, 1, put);
    }


    /* выключить выделение */
    void standend () {
        if (SE) tputs (SE, 1, put);
        /* else normal(); */
    }


    /* включить жирный шрифт */
    void bold () {
        if (BOLD) tputs (BOLD, 1, put);
    }





А. Богатырев, 1992-95                  - 362 -                              Си в UNIX

    /* выключить любой необычный шрифт */
    void normal () {
        if (NORM) tputs (NORM, 1, put);
        else      standend();
    }


    /* Управление драйвером терминала --------------------------------- */

    #define ESC '\033'
    #define ctrl(c)         ((c) & 037 )

    int     curMode = 0;
    int     inited = 0;

    struct termio   old,
                    new;
    int     fdtty;

    void ttinit () {
     /* открыть терминал в режиме "чтение без ожидания" */
        fdtty = open ("/dev/tty", O_RDWR | O_NDELAY);

     /* узнать текущие режимы драйвера */
        ioctl (fdtty, TCGETA, &old);

        new = old;

     /* input flags */
     /* отменить преобразование кода '\r' в '\n' на вводе              */
        new.c_iflag &= ~ICRNL;
        if ((old.c_cflag & CSIZE) == CS8)  /* 8-битный код             */
             new.c_iflag &= ~ISTRIP;       /* отменить & 0177 на вводе */

     /* output flags */
     /* отменить TAB3 - замену табуляций '\t' на пробелы               */
     /* отменить ONLCR - замену '\n' на пару '\r\n' на выводе          */
        new.c_oflag &= ~(TAB3 | ONLCR);

     /* local flags */
     /* выключить режим ICANON, включить CBREAK                        */
     /* выключить эхоотображение набираемых символов                   */
        new.c_lflag &= ~(ICANON | ECHO);

     /* control chars */      /* при вводе с клавиш ждать не более ... */
        new.c_cc[VMIN]  = 1;  /* 1 символа и */
        new.c_cc[VTIME] = 0;  /* 0 секунд    */
        /* Это соответствует режиму CBREAK */

      /* Символы, нажатие которых заставляет драйвер терминала послать сигнал
       * либо отредактировать набранную строку. Значение 0 означает,
       * что соответствующего символа не будет */
        new.c_cc[VINTR]  = ctrl ('C'); /* символ, генерящий SIGINT         */
        new.c_cc[VQUIT]  = '\0';       /* символ, генерящий SIGQUIT        */
        new.c_cc[VERASE] = '\0';       /* забой (отмена последнего символа)*/
        new.c_cc[VKILL]  = '\0';       /* символ отмены строки             */
      /* По умолчанию эти кнопки равны: DEL, CTRL/\, BACKSPACE, CTRL/U     */

        setsigs ();
        inited = 1;                   /* уже инициализировано */
    }



А. Богатырев, 1992-95                  - 363 -                              Си в UNIX

    void openVisual () {      /* open visual mode (включить "экранный" режим) */
        if (!inited)
            ttinit ();
        if (curMode == 1)
            return;

        /* установить моды драйвера из структуры new */
        ioctl (fdtty, TCSETAW, &new);
        curMode = 1;        /* экранный режим */
    }


    void closeVisual () {        /* canon mode (включить канонический режим) */
        if (!inited)
            ttinit ();
        if (curMode == 0)
            return;

        ioctl (fdtty, TCSETAW, &old);
        curMode = 0;        /* канонический режим */
    }


    /* завершить процесс */
    void die (nsig) {
        normal();
        closeVisual (); /* При завершении программы (в том числе по
           * сигналу) мы должны восстановить прежние режимы драйвера,
           * чтобы терминал оказался в корректном состоянии. */
        gotoXY (0, LINES - 1);
        putchar ('\n');
        if (nsig)
            printf ("Пришел сигнал #%d\n", nsig);
        exit (nsig);
    }


    void setsigs () {
        register    ns;

        /* Перехватывать все сигналы; завершаться по ним. */
        /* UNIX имеет 15 стандартных сигналов. */
        for (ns = 1; ns <= 15; ns++)
            signal (ns, die);
    }



















А. Богатырев, 1992-95                  - 364 -                              Си в UNIX

    /* Работа с меню -------------------------------------------- */

    struct menu {
        char   *m_text;             /* выдаваемая строка */
        int     m_label;            /* помечена ли она ? */
    }           menuText[] = {
            /* названия песен Beatles */
        {       "Across the Universe", 0            } ,
        {       "All I've got to do",  0            } ,
        {       "All my loving",       0            } ,
        {       "All together now",    0            } ,
        {       "All You need is love",0            } ,
        {       "And I love her",      0            } ,
        {       "And your bird can sing", 0         } ,
        {       "Another girl",        0            } ,
        {       "Any time at all",     0            } ,
        {       "Ask me why",          0            } ,
        {       NULL,                  0            }
    };


    #define Y_TOP 6
    int     nitems;                 /* количество строк в меню */
    int     nselected = 0;          /* количество выбранных строк */

    char    title[] =
            "ПРОБЕЛ - вниз, ЗАБОЙ - вверх, ESC - выход, \
    ENTER - выбрать, TAB - отменить";

    # define TIMELINE 1

    void main (ac, av) char **av; {
        char  **line;
        register    i;
        int     c;
        int     n;                  /* текущая строка */
        extern char readkey ();     /* forward */

        extern char *ttyname ();    /* имя терминала */
        char   *mytty;

        extern char *getlogin ();   /* имя пользователя */
        char   *userName = getlogin ();

        srand (getpid () + getuid ());      /* инициализировать
                                             * датчик случайных чисел */
        /* считаем строки меню */
        for (nitems = 0; menuText[nitems].m_text != NULL; nitems++);

        /* инициализируем терминал */
        tinit (); ttinit();
        mytty = ttyname(fdtty);
        openVisual ();











А. Богатырев, 1992-95                  - 365 -                              Си в UNIX

    again:
        clearScreen ();
        if (mytty != NULL && userName != NULL) {
            gotoXY (0, TIMELINE);
            bold ();
            printf ("%s", userName);
            normal ();
            printf (" at %s (%s)", mytty, tname);
        }

        drawTitle ("",    Y_TOP - 4);
        drawTitle (title, Y_TOP - 3);
        drawTitle ("",    Y_TOP - 2);

     /* рисуем меню */
        for (i = 0; i < nitems; i++) {
            drawItem (i, 20, Y_TOP + i, 0);
        }


        /* цикл перемещений по меню */
        for (n=0; ; ) {
            printTime ();   /* выдаем текущее время */
            drawItem (n, 20, Y_TOP + n, 1);

            c = getcharacter ();

            drawItem (n, 20, Y_TOP + n, 0);


            switch (c) {
                case ' ':
            go_down:
                    n++;
                    if (n == nitems)
                        n = 0;
                    break;


                case '\b': case 0177:
                    n--;
                    if (n < 0)
                        n = nitems - 1;
                    break;

                case ESC:
                    goto out;


                case '\t':          /* Unselect item */
                    if (menuText[n].m_label != 0) {
                        menuText[n].m_label = 0;
                        drawItem (n, 20, Y_TOP + n, 0);
                        nselected--;
                        prSelects ();
                    }
                    goto go_down;







А. Богатырев, 1992-95                  - 366 -                              Си в UNIX

                case '\r':          /* Select item */
                case '\n':
                    bold ();
                    drawTitle (menuText[n].m_text, LINES - 2);
                                    /* last but two line */
                    normal ();

                    if (menuText[n].m_label == 0) {
                        menuText[n].m_label = 1;
                        drawItem (n, 20, Y_TOP + n, 0);
                        nselected++;
                        prSelects ();
                    }
                    goto go_down;


                default:
                    goto go_down;
            }
        }


    out:
        clearScreen ();

        gotoXY (COLS / 3, LINES / 2);
        bold ();
        printf ("Нажми любую кнопку.");
        normal ();

        /* замусорить экран */
        while (!(c = readkey ())) {
            /* случайные точки */
            gotoXY (rand () % (COLS - 1), rand () % LINES);
            putchar ("@.*"[rand () % 3]);   /* выдать символ */
            fflush (stdout);
        }


        standout ();
        printf ("Нажата кнопка с кодом 0%o\n", c & 0377);
        standend ();

        if (c == ESC) {
            sleep (2);              /* подождать 2 секунды */
            goto again;
        }

        die (0);                    /* успешно завершиться,
                                     * восстановив режимы драйвера */
    }













А. Богатырев, 1992-95                  - 367 -                              Си в UNIX

    /* Нарисовать строку меню номер i
     * в координатах (x,y) с или без выделения
     */
    void drawItem (i, x, y, out) {
        gotoXY (x, y);
        if (out) {
            standout ();
            bold ();
        }
        printf ("%c %s ",
                menuText[i].m_label ? '-' : ' ',  /* помечено или нет */
                menuText[i].m_text          /* сама строка */
            );

        if (out) {
            standend ();
            normal ();
        }
    }


    /* нарисовать центрированную строку в инверсном изображении */
    void drawTitle (title, y) char  *title; {
        register int    n;
        int     length = strlen (title);    /* длина строки */

        gotoXY (0, y);
     /* clearEOL(); */
        standout ();

        for (n = 0; n < (COLS - length) / 2; n++)
            putchar (' ');

        printf ("%s", title); n += length;

     /* дорисовать инверсией до конца экрана */
        for (; n < COLS - 1; n++)
            putchar (' ');
        standend ();
    }


    /* выдать общее число выбранных строк */
    void prSelects () {
        char    buffer[30];

        if (nselected == 0) {
            gotoXY (0, LINES - 1);
            clearEOL ();
        }
        else {
            sprintf (buffer, "Выбрано: %d/%d", nselected, nitems);
            drawTitle (buffer, LINES - 1);
        }
    }









А. Богатырев, 1992-95                  - 368 -                              Си в UNIX

    /* Работа с будильником -------------------------- */

    #define PAUSE 4
    int     alarmed;                /* флаг будильника */

    /* реакция на сигнал "будильник" */
    void onalarm (nsig) {
        alarmed = 1;
    }

    /* Прочесть символ с клавиатуры, но не позже чем через PAUSE секунд.
     * иначе вернуть код 'пробел'.
     */
    int getcharacter () {
        int     c;

        fflush(stdout);

     /* заказать реакцию на будильник */
        signal (SIGALRM, onalarm);
        alarmed = 0;                /* сбросить флаг */

     /* заказать сигнал "будильник" через PAUSE секунд */
        alarm (PAUSE);

     /* ждать нажатия кнопки.
      * Этот оператор завершится либо при нажатии кнопки,
      * либо при получении сигнала.
      */
        c = getchar ();

     /* проверяем флаг */
        if (!alarmed) {             /* был нажат символ */
            alarm (0);              /* отменить заказ будильника */
            return c;
        }

     /* был получен сигнал "будильник" */
        return ' ';                 /* продвинуть выбранную строку вниз */
    }


    /* ---- NDELAY read ----------------------------- */

    /* Вернуть 0 если на клавиатуре ничего не нажато,
     * иначе вернуть нажатую кнопку
     */
    char    readkey () {
        char    c;
        int     nread;

        nread = read (fdtty, &c, 1);
        /* обычный read() дожидался бы нажатия кнопки.
         * O_NDELAY позволяет не ждать, но вернуть "прочитано 0 символов".
         */
        return (nread == 0) ? 0 : c;
    }







А. Богатырев, 1992-95                  - 369 -                              Си в UNIX

    /* -------- Работа со временем ------------------------ */
    void printTime () {
        time_t  t;                  /* текущее время */
        struct  tm  *tm;
        extern  struct tm   *localtime ();
        char    tmbuf[30];
        static  char *week[7]   = { "Вс",  "Пн",  "Вт",  "Ср",  "Чт",  "Пт", "Сб" };
        static  char *month[12] = { "Янв", "Фев", "Мар", "Апр", "Май", "Июн",
                                    "Июл", "Авг", "Сен", "Окт", "Ноя", "Дек"      };

        time (&t);                  /* узнать текущее время */
        tm = localtime (&t);        /* разложить его на компоненты */

        sprintf (tmbuf, "%2s %02d:%02d:%02d %02d-%3s-%d",
                week[tm -> tm_wday],  /* день недели (0..6)   */
                tm -> tm_hour,        /* часы   (0..23)       */
                tm -> tm_min ,        /* минуты (0..59)       */
                tm -> tm_sec ,        /* секунды (0..59)      */
                tm -> tm_mday,        /* число месяца (1..31) */
                month[tm -> tm_mon],  /* месяц (0..11)        */
                tm -> tm_year + 1900  /* год                  */
            );

        gotoXY (COLS / 2, TIMELINE);
        clearEOL ();

        gotoXY (COLS - strlen (tmbuf) - 1, TIMELINE);
        bold ();
        printf ("%s", tmbuf);
        normal ();
    }


8.14.  Напишите программу, выдающую файл на экран порциями по 20  строк  и  ожидающую
нажатия клавиши. Усложнения:
a)   добавить клавишу для возврата к началу файла.
b)   используя библиотеку termcap,  очищать  экран  перед  выдачей  очередной  порции
     текста.
c)   напишите эту программу, используя библиотеку curses.
d)   используя curses, напишите программу параллельного просмотра 2-х  файлов  в  2-х
     неперекрывающихся окнах.
e)   то же в перекрывающихся окнах.

8.15.  Напишите функции включения и выключения режима эхо-отображения  набираемых  на
клавиатуре символов (ECHO).

8.16.  То же про "режим немедленного ввода" (CBREAK).  В обычном режиме строка,  наб-
ранная на клавиатуре, сначала попадает в некоторый буфер в драйвере терминала[*].





____________________
   [*] Такие буфера носят название "character lists" - clist.  Существуют "сырой" (raw)
clist, в который попадают ВСЕ символы, вводимые с клавиатуры; и "канонический" clist,
в котором хранится отредактированная строка - обработаны забой, отмена  строки.  Сами
специальные  символы  (редактирования и генерации сигналов) в каноническую очередь не
попадают (в режиме ICANON).





А. Богатырев, 1992-95                  - 370 -                              Си в UNIX

                 "Сырая"           "Каноническая"
    клавиатура--->ОчередьВвода--*-->ОчередьВвода-->read
                                |           файл-устройство
      драйвер терминала         V эхо          /dev/tty??
                                |
    экран<---ОчередьВывода---<--*--<-----------<---write

Этот буфер используется для предчтения - вы можете набирать текст на  клавиатуре  еще
до того, как программа запросит его read-ом: этот набранный текст сохранится в буфере
и при поступлении запроса будет выдан из буфера. Также, в каноническом режиме ICANON,
буфер  ввода используется для редактирования введенной строки: забой отменяет послед-
ний набранный символ, CTRL/U отменяет всю набранную строку; а также  он  используется
для выполнения некоторых преобразований символов на вводе и выводе[**].
     Введенная строка попадает в программу (которая запросила данные с клавиатуры при
помощи read, gets, putchar) только после того, как вы нажмете кнопку <ENTER>  с кодом
'\n'.  До этого вводимые символы накапливаются в буфере, но в программу не передаются
-  программа  тем временем "спит" в вызове read.  Как только будет нажат символ '\n',
он сам поступит в буфер, а программа будет разбужена и  сможет  наконец  прочесть  из
буфера ввода набранный текст.
     Для меню, редакторов и других "экранных" программ этот режим неудобен:  пришлось
бы слишком часто нажимать <ENTER>.  В режиме CBREAK нажатая буква немедленно попадает
в вашу программу (без ожидания нажатия '\n').  В данном случае буфер драйвера исполь-
зуется  только для предчтения, но не для редактирования вводимого текста.  Редактиро-
вание возлагается на вас - предусмотрите его в своей программе сами!
     Заметьте, что код кнопки <ENTER> ("конец ввода") - '\n' - не  только  "проталки-
вает"  текст  в  программу,  но и сам попадает в буфер драйвера, а затем в вашу прог-
рамму. Не забывайте его как-то обрабатывать.
     В MS DOS функция чтения кнопки в режиме ~ECHO+CBREAK называется getch(). В  UNIX
аналогично ей будет работать обычный getchar(), если перед его использованием устано-
вить нужные режимы драйвера tty вызовом ioctl.  По окончании программы режим драйвера
надо  восстановить (за вас это никто не сделает). Также следует восстанавливать режим
драйвера при аварийном завершении программы (по любому сигналу[*][*]).
     Очереди ввода и вывода используются  также  для  синхронизации  скорости  работы
программы (скажем, скорости наполнения буфера вывода символами, поступающими из прог-
раммы через вызовы write) и скорости работы устройства (с  которой  драйвер  выбирает
символы  с  другого  конца  очереди и выдает их на экран); а также для преобразований
символов на вводе и выводе. Пример управления всеми режимами есть в приложении.

8.17.  Функциональные клавиши большинства дисплеев посылают в линию не один,  а  нес-
колько  символов. Например на терминалах, работающих в системе команд стандарта ANSI,
кнопки со стрелками посылают такие последовательности:

    стрелка вверх  "\033[A"  кнопка Home  "\033[H"
    стрелка вниз   "\033[B"  кнопка End   "\033[F"
    стрелка вправо "\033[C"  кнопка PgUp  "\033[I"
    стрелка влево  "\033[D"  кнопка PgDn  "\033[G"

(поскольку первым символом управляющих  последовательностей  обычно  является  символ
'\033' (escape), то их называют еще escape-последовательностями).  Нам же в программе
удобно воспринимать такую последовательность как единственный код с  целым  значением
большим  0xFF.   Склейка  последовательностей символов, поступающих от функциональных
клавиш, в такой внутренний код -  также  задача  экранной  библиотеки  (учет  системы
команд дисплея на вводе).

____________________
   [**] Режимы преобразований, символы редактирования, и.т.п. управляются системным  вы-
зовом ioctl. Большой пример на эту тему есть в приложении.
   [*][*] Если ваша программа завершилась аварийно и моды терминала остались в "странном"
состоянии, то привести терминал в чувство можно командой stty sane





А. Богатырев, 1992-95                  - 371 -                              Си в UNIX

     Самым интересным является то, что одиночный символ '\033' тоже  может  прийти  с
клавиатуры  - его посылает клавиша Esc. Поэтому если мы строим распознаватель клавиш,
который при поступлении кода 033 начинает ожидать составную последовательность  -  мы
должны  выставлять таймаут, например alarm(1); и если по его истечении больше никаких
символов не поступило - выдавать код 033 как код клавиши Esc.
     Напишите распознаватель кодов, поступающих с клавиатуры. Коды обычных букв выда-
вать  как  есть  (0..0377),  коды  функциональных  клавиш выдавать как числа >= 0400.
Учтите, что разные типы дисплеев посылают разные последовательности от одних и тех же
функциональных  клавиш: предусмотрите настройку на систему команд ДАННОГО дисплея при
помощи библиотеки termcap. Распознаватель удобно строить при помощи сравнения  посту-
пающих  символов  с  ветвями дерева (спускаясь по нужной ветви дерева при поступлении
очередного символа. Как только достигли листа дерева -  возвращаем  код,  приписанный
этому листу):

    ---> '\033' ---> '[' ---> 'A' --> выдать 0400
                |        \--> 'B' -->        0401
                |        \--> 'C' -->        0402
                |        \--> 'D' -->        0403
                \--> 'X' ----------->        0404
                          ...

Нужное дерево стройте при настройке на систему команд данного дисплея.
     Библиотека curses уже имеет такой встроенный  распознаватель.   Чтобы  составные
последовательности склеивались в специальные коды, вы должны установить режим keypad:

    int c; WINDOW *window;
           ...
    keypad(window, TRUE);
           ...
    c = wgetch(window);

Без этого wgetch() считывает все символы поодиночке.   Символические  названия  кодов
для  функциональных  клавиш  перечислены в <curses.h> и имеют вид KEY_LEFT, KEY_RIGHT
и.т.п.  Если вы работаете с единственным окном размером с весь экран, то  в  качестве
параметра  window вы должны использовать стандартное окно stdscr (это имя предопреде-
лено в include-файле curses.h).

    # ======================================== Makefile для getch
    getch: getch.o
            cc getch.o -o getch -ltermlib

    getch.o: getch.c getch.h
            cc -g -DUSG -c getch.c





















А. Богатырев, 1992-95                  - 372 -                              Си в UNIX

    /* Разбор составных последовательностей клавиш с клавиатуры.  */
    /* ================================================== getch.h */
    #define FALSE   0
    #define TRUE    1
    #define BOOLEAN unsigned char
    #define INPUT_CHANNEL   0
    #define OUTPUT_CHANNEL  1

    #define KEY_DOWN      0400
    #define KEY_UP        0401
    #define KEY_LEFT      0402
    #define KEY_RIGHT     0403

    #define KEY_PGDN      0404
    #define KEY_PGUP      0405

    #define KEY_HOME      0406
    #define KEY_END       0407

    #define KEY_BACKSPACE 0410
    #define KEY_BACKTAB   0411

    #define KEY_DC        0412
    #define KEY_IC        0413

    #define KEY_DL        0414
    #define KEY_IL        0415

    #define KEY_F(n)      (0416+n)

    #define ESC           ' 33'


    extern char *tgetstr();

    void _put(char c);
    void _puts(char *s);
    void keyboard_access_denied(void);
    char *strdup(const char *s);
    void keyinit(void);
    int getc_raw(void);
    void keyreset(void);
    int getch(void);
    int lgetch(BOOLEAN);
    int ggetch(BOOLEAN);
    int kgetch(void);
    void _sigalrm(int n);
    void init_keytry(void);
    void add_to_try(char *str, short code);
    void keypad_on(void);
    void keypad_off(void);
    int dotest(void);
    void tinit(void);
    void main(void);










А. Богатырев, 1992-95                  - 373 -                              Си в UNIX

    /* ===================================================== getch.c
     *      The source version of getch.c file was
     *      written by Pavel Curtis.
     *
     */

    #include <stdio.h>
    #include <signal.h>
    #include <setjmp.h>
    #include <termios.h>
    #include <ctype.h>
    #include <string.h>
    #include <locale.h>
    #include "getch.h"

    #define keypad_local   S[0]
    #define keypad_xmit    S[1]

    #define key_backspace  S[2]
    #define key_backtab    S[3]

    #define key_left       S[4]
    #define key_right      S[5]
    #define key_up         S[6]
    #define key_down       S[7]

    #define key_ic         S[8]
    #define key_dc         S[9]
    #define key_il        S[10]
    #define key_dl        S[11]

    #define key_f1        S[12]
    #define key_f2        S[13]
    #define key_f3        S[14]
    #define key_f4        S[15]
    #define key_f5        S[16]
    #define key_f6        S[17]
    #define key_f7        S[18]
    #define key_f8        S[19]
    #define key_f9        S[20]
    #define key_f10       S[21]     /*  f0 */
    #define key_f11       S[22]     /* f11 */
    #define key_f12       S[23]     /* f12 */
    #define key_home      S[24]
    #define key_end       S[25]
    #define key_npage     S[26]
    #define key_ppage     S[27]

    #define TOTAL 28















А. Богатырев, 1992-95                  - 374 -                              Си в UNIX

    /* descriptors for keys */
    char *KEYS[TOTAL+1] = {
            "ke", "ks",

            "kb", "kB",
            "kl", "kr", "ku", "kd",
            "kI", "kD", "kA", "kL",

            "f1", "f2", "f3", "f4", "f5",
            "f6", "f7", "f8", "f9", "f0",
            "f.", "f-",

            "kh", "kH", "kN", "kP",

            NULL

    }, *S[TOTAL];


    void _put (char c)  { write( INPUT_CHANNEL, &c, 1 ); }
    void _puts(char *s) { tputs ( s, 1, _put ); }

    static int  _backcnt = 0;
    static char _backbuf[30];

    static struct try {
            struct try *child;
            struct try *sibling;
            char ch;
            short value;
    }       *_keytry;

    BOOLEAN keypadok = FALSE;

    struct termios new_modes;

    void keyboard_access_denied(){ printf( "Клавиатура недоступна.\n" ); exit(1); }
    char *strdup(const char *s)  { return strcpy((char *) malloc(strlen(s)+1), s); }


























А. Богатырев, 1992-95                  - 375 -                              Си в UNIX

    /* Инициализация таблицы строк */
    void keyinit(){
            char *key, nkey[80], *p;
            register i;

            keyreset();
            for( i=0; i < TOTAL; i++ ){
                    p = nkey;
                    printf("tgetstr(%s)...", KEYS[i]);
                    key = tgetstr(KEYS[i], &p);

                    if(S[i]) free(S[i]);
                    if(key == NULL){
                            S[i] = NULL;   /* No such key */
                            printf("клавиша не определена.\n");
                    }else{
                            /* Decrypted string */
                            S[i] = strdup(key);
                            printf("считано.\n");
                    }
            }

            init_keytry();
            if( tcgetattr(INPUT_CHANNEL, &new_modes) < 0 ){
                    keyboard_access_denied();
            }

            /* input flags */

            /* отменить преобразование кода '\r' в '\n' на вводе */
            new_modes.c_iflag &= ~ICRNL;
            if ((new_modes.c_cflag & CSIZE) == CS8)  /* 8-битный код */
                 new_modes.c_iflag &= ~ISTRIP;       /* отменить & 0177 на вводе */

            /* output flags */

            /* отменить TAB3 - замену табуляций '\t' на пробелы */
            /* отменить ONLCR - замену '\n' на пару '\r\n' на выводе */
            new_modes.c_oflag &= ~(TAB3 | ONLCR);

            /* local flags */

            /* выключить режим ICANON, включить CBREAK */
            /* выключить эхоотображение набираемых символов */
            new_modes.c_lflag &= ~(ICANON | ECHO);

            /* control chars */      /* при вводе с клавиш ждать не более ... */
            new_modes.c_cc[VMIN]  = 1;  /* 1 символа и */
            new_modes.c_cc[VTIME] = 0;  /* 0 секунд    */
            /* Это соответствует режиму CBREAK */

            /* Символы, нажатие которых заставляет драйвер терминала послать сигнал
             * либо отредактировать набранную строку. Значение 0 означает,
             * что соответствующего символа не будет */
            new_modes.c_cc[VINTR]  = '\0'; /* символ, генерящий SIGINT  */
            new_modes.c_cc[VQUIT]  = '\0'; /* символ, генерящий SIGQUIT */
            new_modes.c_cc[VERASE] = '\0'; /* забой (отмена последнего символа)*/
            new_modes.c_cc[VKILL]  = '\0'; /* символ отмены строки      */
    }





А. Богатырев, 1992-95                  - 376 -                              Си в UNIX

    /* Чтение одного символа непосредственно с клавиатуры */
    int getc_raw(){
            int n; char c;

            n = read(INPUT_CHANNEL, &c, 1);
            if (n <= 0) return EOF;
            return (c & 0xFF);
    }


    static BOOLEAN  _getback  = FALSE;
    static char     _backchar = '\0';

    /* Чтение символа - либо из буфера (если не пуст), либо с клавиатуры */
    #define nextc()       (_backcnt > 0  ?  _backbuf[--_backcnt]         : \
                           _getback      ?  _getback = FALSE, _backchar  : \
                                             getc_raw())

    #define putback(ch)   _backbuf[_backcnt++] = ch

    void keyreset(){
            _backcnt = 0; _backchar = '\0';
            _getback = FALSE;
    }


    /* Функция чтения составного символа */
    int getch(){
            int c = lgetch(TRUE);
            keypad_off();
            return c;
    }


    /*
            ВНИМАНИЕ!
                    Если в процессе будет получен сигнал,
                    в то время как процесс находится внутри вызова getch(),
                    то системный вызов read() вернет 0 и errno == EINTR.
                    В этом случае getch() вернет '\0'.
                    Чтобы избежать этой ситуации используется функция lgetch()
    */
    int lgetch(BOOLEAN kpad) {
            int c;

            while((c = ggetch(kpad)) <= 0);
            return c;
    }


    int ggetch(BOOLEAN kpad) {
            int kgetch();

            if( kpad ) keypad_on();
            else       keypad_off();

            return keypadok ? kgetch() : nextc();
    }






А. Богатырев, 1992-95                  - 377 -                              Си в UNIX

    /*
    **      int kgetch()
    **
    **      Get an input character, but take care of keypad sequences, returning
    **      an appropriate code when one matches the input.  After each character
    **      is received, set a one-second alarm call.  If no more of the sequence
    **      is received by the time the alarm goes off, pass through the sequence
    **      gotten so far.
    **
    */

    #define CRNL(c)    (((c) == '\r') ? '\n' : (c))

    /* борьба с русской клавиатурой */
    #if !defined(XENIX) || defined(VENIX)
    # define unify(c) ( (c)&(( (c)&0100 ) ? ~0240 : 0377 ))
    #else
    # define unify(c) (c)
    #endif













































А. Богатырев, 1992-95                  - 378 -                              Си в UNIX

    /* ==================================================================== */
    #if !defined(XENIX) && !defined(USG) && !defined(M_UNIX) && !defined(unix)

            /* Для семейства BSD */

    static BOOLEAN   alarmed;
    jmp_buf          jbuf;

    int kgetch()
    {
            register struct try  *ptr;
            int         ch;
            char        buffer[10];     /* Assume no sequences longer than 10 */
            register char        *bufp = buffer;
            void        (*oldsig)();
            void         _sigalrm();

            ptr = _keytry;

            oldsig = signal(SIGALRM, _sigalrm);
            alarmed = FALSE;

            if( setjmp( jbuf )) /* чтоб свалиться сюда с read-а */
                    ch = EOF;

            do
            {
                if( alarmed )
                    break;
                ch = nextc();
                if (ch != EOF)              /* getc() returns EOF on error, too */
                    *(bufp++) = ch;
                if (alarmed)
                    break;

                while (ptr != (struct try *)NULL &&
                       (ch == EOF || unify(CRNL(ptr->ch)) != unify(CRNL(ch))  ))
                    ptr = ptr->sibling;

                if (ptr != (struct try *)NULL)
                {
                    if (ptr->value != 0)
                    {
                        alarm(0);
                        signal(SIGALRM, oldsig);
                        return(ptr->value);
                    }
                    else
                    {
                        ptr = ptr->child;
                        alarm(1);
                    }
                }

            } while (ptr != (struct try *)NULL);

            alarm(0);
            signal(SIGALRM, oldsig);

            if (ch == EOF && bufp == buffer)
                return ch;



А. Богатырев, 1992-95                  - 379 -                              Си в UNIX

            while (--bufp > buffer)
                putback(*bufp);
            return(*bufp & 0377);
    }


    void _sigalrm(int n)
    {
            alarmed = TRUE;
            longjmp(jbuf, 1);
    }





















































А. Богатырев, 1992-95                  - 380 -                              Си в UNIX

    /* ==================================================================== */
    #else   /* XENIX or USG */

            /* Для семейства SYSTEM V */

    static  BOOLEAN alarmed;

    int kgetch()
    {
            register struct try  *ptr;
            int         ch;
            char        buffer[10];     /* Assume no sequences longer than 10 */
            register char        *bufp = buffer;
            void         (*oldsig)();
            void         _sigalrm();

            ptr = _keytry;

            oldsig = signal(SIGALRM, _sigalrm);
            alarmed = FALSE;

            do
            {
                ch = nextc();
                if (ch != EOF)              /* getc() returns EOF on error, too */
                    *(bufp++) = ch;
                if (alarmed)
                    break;

                while (ptr != (struct try *)NULL &&
                       (ch == EOF || unify(CRNL(ptr->ch)) != unify(CRNL(ch))  ))
                    ptr = ptr->sibling;

                if (ptr != (struct try *)NULL)
                {
                    if (ptr->value != 0)
                    {
                        alarm(0);
                        signal(SIGALRM, oldsig);
                        return(ptr->value);
                    }
                    else
                    {
                        ptr = ptr->child;
                        alarm(1);
                    }
                }

            } while (ptr != (struct try *)NULL);

            alarm(0);
            signal(SIGALRM, oldsig);

            if (ch == EOF && bufp == buffer)
                return ch;
            while (--bufp > buffer)
                putback(*bufp);
            return(*bufp & 0377);
    }





А. Богатырев, 1992-95                  - 381 -                              Си в UNIX

    void _sigalrm(int n)
    {
            alarmed = TRUE;
            signal(SIGALRM, _sigalrm);
    }

    #endif /*XENIX*/


    /* ==================================================================== */
    /*
    **      init_keytry()
    **      Построение дерева разбора последовательностей символов.
    **
    */

    void init_keytry()
    {
            _keytry = (struct try *) NULL;

            add_to_try(key_backspace, KEY_BACKSPACE);
            add_to_try("\b",          KEY_BACKSPACE);
            add_to_try("\177",        KEY_BACKSPACE);

            add_to_try(key_backtab,   KEY_BACKTAB);
            add_to_try(key_dc,        KEY_DC);
            add_to_try(key_dl,        KEY_DL);
            add_to_try(key_down,      KEY_DOWN);

            add_to_try(key_f1,        KEY_F(1));
            add_to_try(key_f2,        KEY_F(2));
            add_to_try(key_f3,        KEY_F(3));
            add_to_try(key_f4,        KEY_F(4));
            add_to_try(key_f5,        KEY_F(5));
            add_to_try(key_f6,        KEY_F(6));
            add_to_try(key_f7,        KEY_F(7));
            add_to_try(key_f8,        KEY_F(8));
            add_to_try(key_f9,        KEY_F(9));
            add_to_try(key_f10,       KEY_F(10));
            add_to_try(key_f11,       KEY_F(11));
            add_to_try(key_f12,       KEY_F(12));
            add_to_try(key_home,      KEY_HOME);
            add_to_try(key_ic,        KEY_IC);
            add_to_try(key_il,        KEY_IL);
            add_to_try(key_left,      KEY_LEFT);
            add_to_try(key_npage,     KEY_PGDN);
            add_to_try(key_ppage,     KEY_PGUP);
            add_to_try(key_right,     KEY_RIGHT);
            add_to_try(key_up,        KEY_UP);
            add_to_try(key_end,       KEY_END);
    }













А. Богатырев, 1992-95                  - 382 -                              Си в UNIX

    void add_to_try(char *str, short code)
    {
            static BOOLEAN  out_of_memory = FALSE;
            struct try      *ptr, *savedptr;

            if (str == NULL || out_of_memory)
                return;

            if (_keytry != (struct try *) NULL)
            {
                ptr = _keytry;

                for (;;)
                {
                    while (ptr->ch != *str  &&  ptr->sibling != (struct try *)NULL)
                        ptr = ptr->sibling;

                    if (ptr->ch == *str)
                    {
                        if (*(++str))
                        {
                            if (ptr->child != (struct try *)NULL)
                                ptr = ptr->child;
                            else
                                break;
                        }
                        else
                        {
                            ptr->value = code;
                            return;
                        }
                    }
                    else
                    {
                        if ((ptr->sibling =
                           (struct try *) malloc(sizeof *ptr)) == (struct try *)NULL)
                        {
                            out_of_memory = TRUE;
                            return;
                        }

                        savedptr = ptr = ptr->sibling;
                        ptr->child = ptr->sibling = (struct try *)NULL;
                        ptr->ch = *str++;
                        ptr->value = 0;

                        break;
                    }
                } /* end for (;;) */
            }
            else    /* _keytry == NULL :: First sequence to be added */
            {
                savedptr = ptr = _keytry = (struct try *) malloc(sizeof *ptr);

                if (ptr == (struct try *) NULL)
                {
                    out_of_memory = TRUE;
                    return;
                }

                ptr->child = ptr->sibling = (struct try *) NULL;



А. Богатырев, 1992-95                  - 383 -                              Си в UNIX

                ptr->ch = *(str++);
                ptr->value = 0;
            }

                /* at this point, we are adding to the try.  ptr->child == NULL */

            while (*str)
            {
                ptr->child = (struct try *) malloc(sizeof *ptr);

                ptr = ptr->child;

                if (ptr == (struct try *)NULL)
                {
                    out_of_memory = TRUE;

                    ptr = savedptr;
                    while (ptr != (struct try *)NULL)
                    {
                        savedptr = ptr->child;
                        free(ptr);
                        ptr = savedptr;
                    }

                    return;
                }

                ptr->child = ptr->sibling = (struct try *)NULL;
                ptr->ch = *(str++);
                ptr->value = 0;
            }

            ptr->value = code;
            return;
    }


    /* Включение альтернативного режима клавиатуры */
    void keypad_on(){
            if( keypadok ) return;
            keypadok = TRUE;
            if( keypad_xmit ) _puts( keypad_xmit );
    }

    /* Включение стандартного режима клавиатуры */
    void keypad_off(){
            if( !keypadok ) return;
            keypadok = FALSE;
            if( keypad_local ) _puts( keypad_local );
    }














А. Богатырев, 1992-95                  - 384 -                              Си в UNIX

    /* Тестовая функция */
    int dotest()
    {
            struct termios saved_modes;
            int c;
            char *s;
            char keyname[20];

            if( tcgetattr(INPUT_CHANNEL, &saved_modes) < 0 ){
    err:            keyboard_access_denied();
            }
            if( tcsetattr(INPUT_CHANNEL, TCSADRAIN, &new_modes) < 0 )
                    goto err;

            keyreset();

            for(;;){
                    c = getch();

                    switch(c){
                    case KEY_DOWN:      s = "K_DOWN"  ; break;
                    case KEY_UP:        s = "K_UP"    ; break;
                    case KEY_LEFT:      s = "K_LEFT"  ; break;
                    case KEY_RIGHT:     s = "K_RIGHT" ; break;
                    case KEY_PGDN:      s = "K_PGDN"  ; break;
                    case KEY_PGUP:      s = "K_PGUP"  ; break;
                    case KEY_HOME:      s = "K_HOME"  ; break;
                    case KEY_END:       s = "K_END"   ; break;
                    case KEY_BACKSPACE: s = "K_BS"    ; break;
                    case '\t':          s = "K_TAB"   ; break;
                    case KEY_BACKTAB:   s = "K_BTAB"  ; break;
                    case KEY_DC:        s = "K_DEL"   ; break;
                    case KEY_IC:        s = "K_INS"   ; break;
                    case KEY_DL:        s = "K_DL"    ; break;
                    case KEY_IL:        s = "K_IL"    ; break;

                    case KEY_F(1):      s = "K_F1"    ; break;
                    case KEY_F(2):      s = "K_F2"    ; break;
                    case KEY_F(3):      s = "K_F3"    ; break;
                    case KEY_F(4):      s = "K_F4"    ; break;
                    case KEY_F(5):      s = "K_F5"    ; break;
                    case KEY_F(6):      s = "K_F6"    ; break;
                    case KEY_F(7):      s = "K_F7"    ; break;
                    case KEY_F(8):      s = "K_F8"    ; break;
                    case KEY_F(9):      s = "K_F9"    ; break;
                    case KEY_F(10):     s = "K_F10"   ; break;
                    case KEY_F(11):     s = "K_F11"   ; break;
                    case KEY_F(12):     s = "K_F12"   ; break;

                    case ESC:           s = "ESC"     ; break;
                    case EOF:           s = "K_EOF"   ; break;
                    case '\r':          s = "K_RETURN"; break;
                    case '\n':          s = "K_ENTER" ; break;
                    default:
                            s = keyname;
                            if( c >= 0400 ){
                                    sprintf(keyname, "K_F%d", c - KEY_F(0));
                            } else if( iscntrl(c)){
                                    sprintf(keyname, "CTRL(%c)", c + 'A' - 1);
                            } else {
                                    sprintf(keyname, "%c", c );



А. Богатырев, 1992-95                  - 385 -                              Си в UNIX

                            }
                    }
                    printf("Клавиша: %s\n\r", s);

                    if(c == ESC)
                            break;
            }
            tcsetattr(INPUT_CHANNEL, TCSADRAIN, &saved_modes);
    }


    /* Функция настройки на систему команд дисплея */
    void tinit (void) {
        /* static */ char Tbuf[2048];
        /* Tbuf должен сохраняться все время, пока могут вызываться функции tgetstr().
         * Для этого он либо должен быть static, либо вызов функции keyinit()
         * должен находиться внутри tinit(), что и сделано.
         */
        char *tname;
        extern char *getenv();

        if((tname = getenv("TERM")) == NULL){
            printf("TERM не определено: неизвестный тип терминала.\n");
            exit(2);
        }
        printf("Терминал: %s\n", tname);

        /* Прочесть описание терминала в Tbuf */
        switch (tgetent(Tbuf, tname)) {
             case -1:
                printf ("Нет файла TERMCAP (/etc/termcap).\n");
                exit (1);
            case 0:
                printf ("Терминал '%s' не описан.\n", tname);
                exit (2);
            case 1:
                break;              /* OK */
        }
        if(strlen(Tbuf) >= 1024)
    printf("Описание терминала слишком длинное - возможны потери в конце описания\n");

        keyinit();  /* инициализировать строки, пока Tbuf[] доступен */
    }


    void main(void){
            setlocale(LC_ALL, "");
            tinit();
            /* keyinit(); */
            dotest();
            exit(0);
    }

По поводу этого алгоритма надо сказать еще пару слов. Его модификация может с успехом
применяться  для  поиска  слов в таблице (команд, ключей в базе данных, итп.): список
слов превращается в дерево. В таком поисковом алгоритме не требуются таймауты,  необ-
ходимые  при  вводе  с  клавиатуры,  поскольку есть явные терминаторы строк - символы
'\0', которых нет при вводе с клавиатуры.   В  чем  эффективность  такого  алгоритма?
Сравним последовательный перебор при помощи strcmp и поиск в дереве букв:





А. Богатырев, 1992-95                  - 386 -                              Си в UNIX

    "zzzzzzzzzza"
    "zzzzzzzzzzb"
    "zzzzzzzzzzbx"
    "zzzzzzzzzzc"
    "zzzzzzzzzzcx"

Для линейного перебора (даже в отсортированном  массиве)  поиск  строки  zzzzzzzzzzcx
потребует

    zzzzzzzzzza     |       11 сравнений, отказ
    zzzzzzzzzzb     |       11 сравнений, отказ
    zzzzzzzzzzbx    |       12 сравнений, отказ
    zzzzzzzzzzc     |       11 сравнений, отказ
    zzzzzzzzzzcx    V       12 сравнений, успех

Всего: 57 шагов.  Для поиска в дереве:

    __z__z__z__z__z__z__z__z__z__z__a__\0
                                  |_b__\0
                                  |  |_x__\0
                                  |
                                  |_c__\0
                                     |_x__\0

потребуется проход вправо (вниз) на 10 шагов, потом выбор среди 'a','b','c', потом  -
выбор среди '\0' и 'x'.  Всего: 15 шагов. За счет того, что общий "корень" проходится
ровно один раз, а не каждый раз заново. Но это и требует  предварительной  подготовки
данных: превращения строк в дерево!

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

    addstr( "\b \b" );
            или
    addch( '\b' ); delch();

Недостатком этих способов является некорректное поведение в начале строки (при x==0).
Исправьте это!

8.19.  На curses-е напишите функцию редактирования текста  в  окне.   Функция  должна
возвращать  массив  строк с обрезанными концевыми пробелами. Вариант: возвращать одну
строку, в которой строки окна разделяются символами '\n'.

8.20.  Напишите функцию, рисующую прямую линию из точки (x1,y1) в (x2,y2).  Указание:
используйте  алгоритм  Брезенхема  (минимального  отклонения).   Ответ: пусть функция
putpixel(x,y,color) рисует точку в координатах (x,y) цветом color.

    void line(int x1, int y1,   int x2, int y2,
              int color){
        int dx, dy, i1, i2, i, kx, ky;
        register int d; /* "отклонение" */
        register int x, y;
        short /* boolean */ l;




А. Богатырев, 1992-95                  - 387 -                              Си в UNIX

        dy = y2 - y1; dx = x2 - x1;
        if( !dx && !dy ){
                putpixel(x1,y1, color); return;
        }
        kx = 1; /* шаг по x */
        ky = 1; /* шаг по y */
        /* Выбор тактовой оси */
        if( dx < 0 ){ dx = -dx; kx = -1; } /* Y */
        else if( dx == 0 )      kx = 0;    /* X */
        if( dy < 0 ){ dy = -dy; ky = -1; }
        if( dx < dy ){ l = 0; d = dx; dx = dy; dy = d; }
        else           l = 1;

        i1 = dy + dy; d = i1 - dx; i2 = d - dx;
        x = x1; y = y1;

        for( i=0; i < dx; i++ ){
             putpixel( x, y, color );

             if( l ) x += kx; /* шаг по такт. оси   */
             else    y += ky;
             if( d < 0 ) /* горизонтальный шаг      */
                 d += i1;
             else{       /* диагональный шаг        */
                 d += i2;
                 if( l ) y += ky; /* прирост высоты */
                 else    x += kx;
             }
        }
        putpixel(x, y, color);  /* последняя точка  */
    }


8.21.  Составьте программу, которая строит график функции sin(x) на отрезке от  0  до
2*пи.   Учтите  такие вещи: соседние точки графика следует соединять отрезком прямой,
чтобы график выглядел непрерывным; не забывайте приводить double к int, т.к.  коорди-
наты пикселов[*] - целые числа.

8.22.  Напишите функцию, которая заполняет в массиве байт count бит подряд, начиная с
x-ого бита от левого края массива:

        байт 0      |          байт 1
    7 6 5 4 3 2 1 0 | 7 6  5  4  3  2  1  0 : биты в байте
    0 1 2 3 4 5 6 7 | 8 9 10 11 12 13 14 15 : x
        ==========================
            x=2, count=11

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

    void horizLine(char *addr,int x,int count,char pattern){
      static char masks[8] = {
           0xFF, 0x7F, 0x3F, 0x1F, 0x0F, 0x07, 0x03, 0x01 };
      /* индекс в этом массиве равен числу 0-битов слева */
____________________
   [*] Пиксел (pixel, pel) - picture element, в машинной графике - точка растра на  эк-
ране.





А. Богатырев, 1992-95                  - 388 -                              Си в UNIX

      register i;
      char mask;
      short lbits, rbits; /* число битов слева и справа */
      short onebyte;      /* единственный байт ? */

      addr += x/8;        /* в байте 8 бит */
      mask = masks[ lbits = x & 7 ];   /* x % 8 */
      if( count >= (rbits = 8 - lbits)){
          count -= rbits; onebyte = 0;
      }else{
          mask &= ~masks[ lbits = (x+count) & 7 ];
          onebyte = 1;
      }
    /* Первый байт */
      *addr = (*addr & ~mask) | (pattern & mask);
      addr++;
      /* Для pattern==0xFF можно просто
       *     *addr++ |= mask;
       * поскольку (a &~m)|(0xFF & m) = (a &~m) | m =
       *   (a|m) & (~m|m) = (a|m) & 0xFF = a | m
       * Почему здесь нельзя написать *addr++ = (*addr...) ?
       * Потому, что ++ может быть сделан ДО вычисления
       * правой части присваивания!
       */
      if(onebyte) return;
    /* Средние байты */
      for(i = count/8; i > 0; --i)
          *addr++ = pattern;  /* mask==0xFF */
    /* Последний байт */
      if((lbits = count & 7) == 0) return;
      /* последний байт был полным */
      mask = ~masks[lbits];
      *addr = (*addr & ~mask) | (pattern & mask);
    }

Заметим, что для быстродействия подобные алгоритмы обычно пишутся на ассемблере.

8.23.  Напишите при помощи curses-а "электронные часы",  отображающие  текущее  время
большими  цифрами  (например, размером 8x8 обычных символов) каждые 5 секунд. Исполь-
зуйте alarm(), pause().

8.24.  Составьте программу, реализующую простой диалоговый интерфейс,  основанный  на
меню. Меню хранятся в текстовых файлах вида:





















А. Богатырев, 1992-95                  - 389 -                              Си в UNIX

            файл menu2_12
    -----------------------------------------------
    ЗАГОЛОВОК_МЕНЮ
    +команда_выполняемая_при_входе_в_меню
    -команда_выполняемая_при_выходе_из_меню
    альтернатива_1
            команда1_1
            команда1_2
    альтернатива_2
            команда2_1
            команда2_2  #комментарий
            команда2_3
    альтернатива_3
           >menu2_2     #это переход в другое меню
    альтернатива_4
           >>menu3_7    #хранимое в файле menu3_7
    ...
            ...
    -----------------------------------------------

Программа должна обеспечивать: возврат к предыдущему меню по клавише Esc  (для  этого
следует  хранить "историю" вызовов меню друг из друга, например в виде "полного имени
меню":

    .rootmenu.menu1_2.menu2_4.menu3_1

где menuI_J - имена файлов с меню), обеспечить выход из программы по клавишам  'q'  и
ESC,  выдачу подсказки по F1, выдачу полного имени меню по F2.  Вызов меню при помощи
>&gt; означает замещение текущего меню новым, что соответствует замене  последней  компо-
ненты  в  полном  имени  меню.  Вызов  >&gt;>&gt; означает вызов меню как функции, т.е. после
выбора в новом меню и выполнения нужных действий автоматически должно быть выдано  то
меню, из которого произошел вызов (такой вызов соответствует удлинению полного имени,
а возврат из вызова - отсечению последней компоненты).  Этот вызов может быть показан
на  экране  как  появление нового "выскакивающего" окна поверх окна с предыдущим меню
(окно возникает чуть сдвинутым - скажем, на y=1 и x=-2), а возврат - как исчезновение
этого окна.  Заголовок меню должен высвечиваться в верхней строке меню:

               |-------------------
            |--ЗАГОЛОВОК_МЕНЮ---- |
            |  альтернатива_1   | |
            |  альтернатива_2   | |
            | *альтернатива_3   | |
            |  альтернатива_4   |--
            ---------------------

Сначала реализуйте версию, в которой каждой "альтернативе" соответствует единственная
строка   "команда".    Команды  следует  запускать  при  помощи  стандартной  функции
system(команда).
     Усложните функцию выбора в меню так, чтобы альтернативы можно было  выбирать  по
первой букве при помощи нажатия кнопки с этой буквой (в любом регистре):

            Compile
            Edit
            Run program


8.25.  Напишите на curses-е функцию, реализующую выбор в меню  -  прямоугольной  таб-
лице:






А. Богатырев, 1992-95                  - 390 -                              Си в UNIX

            слово1   слово4   слово7
            слово2  *слово5   слово8
            слово3   слово6

Строки - элементы меню - передаются в функцию выбора в  виде  массива  строк.   Число
элементов  меню  заранее  неизвестно и должно подсчитываться внутри функции.  Учтите,
что все строки могут не поместиться в таблице, поэтому надо предусмотреть  "прокручи-
вание"  строк  через  таблицу  при  достижении  края меню (т.е. таблица служит как бы
"окошком" через которое мы обозреваем таблицу большего  размера,  возможно  перемещая
окно  над ней).  Предусмотрите также случай, когда таблица оказывается заполненной не
полностью (как на рисунке).

8.26.  Используя библиотеку curses, напишите программу, реализующую клеточный автомат
Конвея  "Жизнь". Правила: есть прямоугольное поле (вообще говоря бесконечное, но при-
нято в конечной модели замыкать края в кольцо), в котором живут  "клетки"  некоторого
организма.  Каждая имеет 8 соседних полей. Следующее поколение "клеток" образуется по
таким правилам:
-    если "клетка" имеет 2 или 3 соседей - она выживает.
-    если "клетка" имеет меньше 2 или больше 3 соседей - она погибает.
-    в пустом поле, имеющем ровно 3х живых соседей, рождается новая "клетка".

Предусмотрите: редактирование поля, случайное заполнение  поля,  останов  при  смерти
всех "клеток", останов при стабилизации колонии.

8.27.  При помощи curses-а напишите экранный редактор кодов доступа к файлу (в  форме
rwxrwxrwx).   Расширьте  программу, позволяя редактировать коды доступа у группы фай-
лов, изображая имена файлов и коды доступа в виде таблицы:

            НАЗВАНИЕ   КОДЫ ДОСТУПА
              файл1      rwxrw-r--
              файл2      rw-r-xr-x
              файл3      rwxrwxr--

Имена файлов задавайте как аргументы для main().  Указание: используйте для получения
текущих  кодов  доступа  системный вызов stat(), а для их изменения - системный вызов
chmod().