Лицензия Creative Commons
Содержимое блога доступно по лицензии Creative Commons Атрибуция — С сохранением условий
(Attribution-ShareAlike) 3.0 Unported
, если не указано иное.

понедельник, 26 ноября 2012 г.

Препроцессор C

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

На прошлой неделе, изучая код ядра Linux, я наткнулся на довольно занятный заголовочный файл. В файле объявлено два макроса и одна inline-функция. Заинтересовало же меня следующее: название одного из макросов совпадает с именем функции, равно как и набор их параметров. Я подумал -- как будет работать этот код? И решил провести эксперимент, как только появится свободное время.

На следующий день я вспомнил про этот файл -- и понял, что результат компиляции очевиден и без проведения эксперимента: достаточно вспомнить, как работает компилятор gcc.

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

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

После этого происходит компиляция, потом -- преобразование ассемблерного кода в машинный код и, наконец, линковка.

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

Если же всё прошло нормально, то в конце-концов мы получаем исполняемый файл.

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

Посмотрим на примере.

Итак, допустим, у нас есть заголовочный файл и файл с исходным кодом -- назовём их test.h и test.c соответственно. Вот содержимое test.h:

 
#ifndef __TEST_H__ 
#define __TEST_H__

inline int function1(int param) 
{
 return param; 
}

#define function1(param) function1(param)

#endif /* ifndef __TEST_H__ */

Кстати говоря, имена макросам в C принято давать в верхнем регистре, чтобы их можно было легко отличить от обычных функций и переменных. В данной же ситуации мы намеренно отступаем от этого соглашения.

А вот содержимое test.c:

 
#include <stdio.h> 
#include "macros.h"

int main(int argc, char *argv[])
{ 
 printf("Result of calling function1: %d\n", 
  function1(100));

 return 0;
}

Результат работы препроцессора можно увидеть, передав gcc ключ -E, вот так:

$ gcc -E test.c -o test.i

Не буду приводить здесь этот файл test.i полностью (он достаточно объёмен) -- посмотрим лишь на последние 15 строк:

 
$ tail -15 test.i 


inline int function1(int param)
{
 return param;
}
# 3 "test.c" 2

int main(int argc, char *argv[])
{
 printf("Result of calling function1: %d\n",
  function1(100));

 return 0;
}

Здесь мы видим, что в main() всё так же вызывается function1(), однако этот вызов был получен в результате работы препроцессора: он нашёл макрос function1, потом встретил имя function1 в main(), и подменил его результатом обработки макроса.

Попробуем сделать следующее: поменяем макрос function1() в test.h таким образом, чтобы он разворачивался в вызов несуществующей функции function2():

 
#define function1(param) function2(param)

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

 
$ tail -15 test.i        


inline int function1(int param)
{
 return param;
}
# 3 "test.c" 2

int main(int argc, char *argv[])
{
 printf("Result of calling function1: %d\n",
  function2(100));

 return 0;
}

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

 
$ gcc test.c 
/tmp/ccUBRByP.o: In function `main':
test.c:(.text+0x19): undefined reference to `function2' collect2:
выполнение ld завершилось с кодом возврата 1

Из этого можно сделать интересный вывод: если у нас существует функция и макрос с одинаковым именем и набором параметров, то нам не удастся вызвать функцию напрямую -- её вызов прежде будет обработан препроцессором, который подставит в место вызова результат обработки макроса. Таким образом, функция может быть "скрыта" от компилятора, или подменена. Например, поменяв макрос следующим образом:

 
#define function1(param) 0

И скомпилировав программу, мы увидим следующее:

$ gcc test.c 
$ ./a.out 
Result of calling function1: 0

Мы получили ноль, несмотря на то, что передавали в функцию число 100, так как вызов функции был принят препроцессором за вызов макроса, и заменён на тело макроса -- то есть, на ноль.

Итак, с помощью препроцессора можно делать занятные вещи -- например, подменить функцию (можно сказать, под носом у компилятора), как в рассмотренном примере. Использование же макросов может сделать код как более читаемым, так и совершенно запутать его -- достаточно вспомнить, что многие работы, участвовавшие в IOCCC, активно используют макросы.

воскресенье, 28 октября 2012 г.

Удаление элемента списка в Scheme

Доброго времени суток, случайные и неслучайные читатели этого блога.

Сейчас довольно много пишу на Scheme, в связи с работой над проектом LazyCat. В проекте используется Scheme для GUI и для высокоуровневой логики. Подробнее о проекте на русском языке можно узнать здесь. В данной же заметке я хочу рассказать о проблеме удаления элемента из списка.

Если вы сталкивались с Lisp'ом в жизни (например, настраивая GNU Emacs), то должны знать, что список является едва ли не основным представлением как данных, так и собственно программы, их обрабатывающей. Даже название языка -- Lisp -- произошло от "List Processing", т.е. "обработка списков". Scheme, как диалект Lisp, не представляет исключение в этом плане. И работая с Scheme, вы постоянно работаете со списками.

Так вот, в LazyCat список управляемых хостов хранится, как Lisp-список. Пример:

 
'((#f host1 host2) ("ssh-hosts" host2 host4))

В данном примере есть две группы:

  • группа #f, в которую помещяются "бездомные" хосты, которые не являются членами какой-либо группы (уж так повелось);
  • и группа "ssh-hosts".

В каждой группе -- по два хоста. Первый элемент группы -- который можно получить через операцию car -- имя группы.

(car '("ssh-hosts" host2 host4)) => "ssh-hosts"

Оставшаяся часть списка -- получаемая через cdr -- это члены группы.

(cdr '("ssh-hosts" host2 host4)) => '(host2 host4)

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

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

  1. Нужно взять часть списка, чей car -- элемент, который необходимо удалить. Эту часть можно найти путём простого перебора элементов.
  2. После этого нужно получить cdr списка.
  3. Склеить с помощью операции append две части списка -- часть списка до текущего car и часть списка, получаемая по cdr относительно текущей части с удаляемым элементом в car.

На практике же это превратилось в довольно громоздкую конструкцию:

 

(let ((new-cdr '())) 
  (let f ((group-members (cdr group)))

    ;; Are there elements in the given list?
    (if (not (null? group-members))

        (if (eq? (car group-members) host)

             ;; We found the host which should be removed from the list.
             ;; Cut out the car of the list and concatenate two lists
             (set-cdr! group (append new-cdr (cdr group-members)))

             ;; Host is not found. Check the next group member.
             (begin 
               ;; Add the current car to the new cdr of the group
               (new-cdr (append new-cdr (car group-members))) 
               ;; Try the next group member 
               (f (cdr group-members)))))))

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

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

Благодаря использованию модуля (ice-9 common-list) вышеприведённый кусок кода был заменён на следующую строчку:

 

(set-cdr! group (remove-if (lambda (element) (eq? element host)) 
                           (cdr group)))

Функция remove-if применяет предикат (фукнцию, возвращающую #t (true) или #f (false)) переданный, как первый параметр, ко всем элементам списка (второй параметр функции). Если предикат возвращает #t -- то элемент удаляется из списка. По завершению remove-if возвращает список, из которого удалены требуемые элементы.

В представленном выше примере remove-if сравнивает два объекта -- элемент списка и хост. Если элемент списка и хост -- один и тот же объект, то он удаляется из списка. После этого происходит замена cdr группы новым списком хостов.

Пример использования remove-if взят из файла host-list.scm, являющегося частью LazyCat.

- Артём

понедельник, 7 мая 2012 г.

Получение информации о MBR и таблице разделов с помощью file(1)

Только что узнал о таком интересном умении Unix-утилиты file(1), как вывод информации из главной загрузочной записи (англ. Master Boot Record, или, по-простому, MBR).

Для примера сохраним MBR с устройства /dev/sda в файл. Для этого нам нужно скопировать первые 512 байт с жёсткого диска, то есть, один блок по 512 байт. Хочу предупредить, что утилита dd(1) славится своей способностью портить жёсткие диски при неумелом обращении. Поэтому всегда проверяйте, правильно ли вы указали источник if и место сохранения of данных. Просто нужно немного внимательности. Итак, сохраняем MBR:

$ dd if=/dev/sda of=/mnt/backup/boot.mbr bs=512 count=1

Затем получим информацию о файле:

$ file /mnt/backup/boot.mbr
/mnt/backup/boot.mbr: x86 boot sector; GRand Unified Bootloader, stage1 version 0x3, stage2 address 0x2000, stage2 segment 0x200; partition 1: ID=0x83, active, starthead 1, startsector 63, 29302497 sectors; partition 2: ID=0x83, starthead 254, startsector 29302560, 8000370 sectors; partition 3: ID=0x82, starthead 254, startsector 37302930, 2554335 sectors, code offset 0x4

В выводе команды можно увидеть тип загрузчика (GRand Unified Bootloader - GRUB) и информацию из таблицы разделов. Каждая запись отделена точкой с запятой. Например, запись

partition 1: ID=0x83, active, starthead 1, startsector 63, 29302497 sectors;

говорит, что на первом разделе (/dev/sda1) находится файловая система ext (в данном случае, ext2), так как её шестнадцатиричный код - 0x83. Так же видно, что первый раздел является активным (active) - то есть, с него осуществляется загрузка. Далее идёт размер раздела в секторах.

Вот более подробная статья на эту тему (на английском):
http://www.miljan.org/main/2007/09/05/easy-way-to-read-mbr/

четверг, 2 февраля 2012 г.

Нестандартное применение функции getopt(3)

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

Как вы наверняка знаете, getopt(3) позволяет легко разбирать (или "парсить", да простит меня русский язык) опции командной строки, переданные программе.

Вместо термина "опция" так же используются термины "флаг" или "ключ".

Вот простой пример, демонстрирующий работу getopt(3):

#include <stdio.h>
#include <unistd.h>

int
main(int argc, char* argv[])
{
  int opt;

  while ((opt = getopt(argc, argv, "ab:")) > 0)
    {
      switch (opt)
      {
      case 'a':
          puts("'a' option was found.");
          break;

      case 'b':
          printf("'b' option was found. number = %d\n", atoi(optarg));
          break;
      }
    }

  return 0;
}

Работа с программой может выглядить следующим образом:

$ ./a.out -a -b 10
'a' option was found.
'b' option was found. number = 10

В данном примере используются только короткие опции - то есть, которые начинаются с "-", например, "-h", "-n 9". Родственная функция getopt_long(3) позволяет парсить так же и длинные опции, начинающиеся с "--" (например, "--verbose" или "--option=value").

Использование getopt(3) позволяет избежать создания собственного "велосипеда" для разбора опций командной строки. А теперь представим, что нам нужно разобрать подобным образом массив строк, передаваемый в качестве параметра нашей собственной функции. Почему бы не использовать для этого столь удобный инструмент, как getopt(3)? Тем более, что функция main() очень похожа на другие функции (точнее, другие функции очень похожи неё). Разве что main() является стандартной точкой входа в программу, с которой начинается её выполнение. Но для нашего эксперимента это не столь важно. Попробуем "подделать" обычную функцию под main(), чтобы getopt(3) не обнаружила подмены. Для этого посмотрим внимательно на main().

Итак, main() принимает в качестве параметров количество аргументов командной строки argc и собственно сам список аргументов argv, который представляет собой массив указателей на строки (массивы символов). Чтобы getopt(3) работала корректно, нужно создать функцию с подобным набором параметров. Внутри функции организуем разбор "командной строки":

void
fun1(int argc, char* argv[])
{
  int opt;
  
  while ((opt = getopt(argc, argv, "ab:c:")) > 0)
    {
      switch (opt)
 {
 case 'a':
   puts("'a' was found.");
   break;

 case 'b':
   printf("'b' was found. optarg = %d\n", atoi(optarg));
   break;

 case 'c':
   printf("'c' was found. optarg = %d\n", atoi(optarg));
   break;
 }
    }
}  

Теперь возьмёмся за main():

#include <stdio.h>
#include <unistd.h>

void fun1(int argc, char* argv[]);

int
main(void)
{
  int   argc = 3;
  char* test_array[] = { "-a", "-b 10", "-c 20" };

  fun1(argc, test_array);

  return 0;
}

Скомпилируем и запустим программу:

$ gcc -o getopt-test getopt-test.c
$ ./getopt-test
'b' was found. optarg = 10
'c' was found. optarg = 20

Как можно заметить, куда-то подевался нулевой элемент массива argv - словно getopt(3) начала просмотр массива с первого элемента. Разберёмся, почему. Вспомним, что при запуске программы нулевой элемент массива argv, передаваемый в main(), содержит имя исполняемого файла программы. Поэтому функция getopt(3) попросту пропускает его, так как он не содержит опций командной строки.

Решение проблемы выглядит следующим образом:

int
main(void)
{
  int   argc = 4; /* 3 аргумента командной строки + имя программы */
  char* test_array[] = { "fun1", "-a", "-b 10", "-c 20" };

  fun1(argc, test_array);

  return 0;
}

Скомпилируем и проверим исправленную версию программы:

$ gcc -o getopt-test getopt-test.c
$ ./getopt-test
'a' was found.
'b' was found. optarg = 10
'c' was found. optarg = 20

По результатам работы программы видно, что теперь getopt(3) находит опцию "-a".

понедельник, 2 января 2012 г.

Конвейерная обработка данных в Unix

Доброго времени суток, случайные и не случайные читатели этого блога.

Сегодня я хотел бы рассмотреть пример программы, которая может работать в режиме "конвейера" (pipeline), что является обыденным делом для утилит Unix-подобных систем.

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

Наша программа будет принимать на вход вывод некой другой программы, обрабатывать эти данные неким образом и передавать на стандартный вывод.

Просто? Просто.

Исходный текст программы тоже очень простой:

#include <stdio.h>
#include <stdlib.h>

int
main(void)
{
  char ch;

  while (fread(&ch, sizeof(char), 1, stdin))
    putchar(toupper(ch));
  
  exit(EXIT_SUCCESS);
}

Теперь немного технических деталей. Когда вы пишете что-то вроде

$ cat my-file.txt | sort

командная оболочка (shell) связывает стандартный поток вывода stdout команды cat(1) со стандартным потоком ввода stdin команды sort(1). Таким образом, эти команды связываются в конвейер, проходя через который данные преобразуются определённым образом. В данном примере, мы выводим (считываем) содержимое файла my-file.txt на stdout, команда sort(1) принимает эти данные на stdin, сортирует их и выводит на stdout. На этом конвейер заканчивается и обработанные данные выводятся на терминал.

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

Важно заметить, что программы, составляющие конвейер, выполняются параллельно. Если рассматривать приведённый ранее пример, то команда cat(1) и sort(1) работают одновременно. Как только cat(1) выводит данные на stdout, они сразу же могут быть считаны командой sort(1) из stdin.

Сравните с последовательностью команд, разделённых точкой с запятой, которые выполняются одна за другой:

$ cat my-file.txt; sort

Сначала будет выполнена команда cat(1), которая выведет содержимое файла my-file.txt на экран, а потом будет выполнена команда sort(1), которая будет ждать ввода данных с stdin.

Скомпилируем наконец нашу программу и посмотрим, что полезного она может сделать.

$ gcc tu.c -o tu

Протестируем работу программы. Свяжем в конвейер команду awk(1) и нашу програму:

$ awk --copyleft | ./tu

Команда awk(1) с параметром --copyleft выводит краткий вариант лицензии GPL на stdout. Далее наша программа считывает в цикле по одному символу с stdin, преобразует считанный символ в прописной и выводит этот символ на stdout.

Вывод нашей программы можно так же отправить дальше по конвейеру.

$ awk --copyleft | ./tu |\
   sed s/'1989, 1991-2010 FREE SOFTWARE FOUNDATION'/'2012 Artyom Poptsov'/

Неплохой обзор конвейерной обработки данных в Unix дан в следующих статьях:

воскресенье, 1 января 2012 г.

Новогодняя ёлка на Emacs Lisp

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

Пользуясь случаем, поздравляю вас с уже наступившим Новым Годом. Дабы немного поднять вам (и себе) новогоднее настроение, публикую исходный код программы на Emacs Lisp, которая рисует замечательную новогоднюю ACSII-ёлку.

;;;
;;; Copyright (C) 2011 Artyom Poptsov
;;;
;;; This program is free software; you can redistribute it and/or modify
;;; it under the terms of the GNU General Public License as published by
;;; the Free Software Foundation; either version 3 of the License, or
;;; (at your option) any later version.
;;;
;;; For more information, see http://www.gnu.org/licenses/
;;;

;; Result of running this program sends to other buffer
(with-output-to-temp-buffer "*tree*"

  ;; Get height of the tree from stdin
  (setf HIGHT (read))

  ;; There are symbols that I will use for drawing the tree
  (setq C_BG    ":")
  (setq C_TREE  "^")
  (setq C_TRUNK "#")

  ;; A few variables
  (setq PADDING 2) ; Padding from edges of the "canvas".
  (setf TRUNK_H (/ HIGHT 4))                              

  ;; I'm using this funtions for printing empty strings filled with BG
  (defun print-bg-for-picture ()
    "This function prints out a few strings filled with background"
    (loop for i from 1 to PADDING do
   (loop for j from 0 to (+ (* HIGHT 2) (* PADDING 3)) do
  (princ C_BG))
   (princ "\n")))

  (print-bg-for-picture)

  ;; Main loop
  (loop for i from 0 to (+ HIGHT TRUNK_H (* PADDING 2)) do
 (loop for j from 0 to PADDING do
       (princ C_BG))
 (if (< i HIGHT)
     ;; Top of the tree
     (loop for j from 0 to (* HIGHT 2) do
    (if (or (< j (- HIGHT i))
     (> j (+ HIGHT i)))
        (princ C_BG)
      (princ C_TREE)))
   ;; Trunk of the tree
   (loop for j from 0 to (* HIGHT 2) do
  (if (or (< j (- HIGHT (/ HIGHT 10)))
   (> j (+ HIGHT (/ HIGHT 10))))
      (princ C_BG)
    (princ C_TRUNK))))
 (loop for j from 0 to PADDING do
       (princ C_BG))
 
 (princ "\n"))
  (print-bg-for-picture))

Вы можете вычислить (выполнить) эту программу следующим образом: запустите текстовый редактор Emacs (предположим, что он у вас уже установлен), скопируйте исходный код в буфер *scratch*, поместите точку (курсор) после последней скобки в конце программы и нажмите C-x C-e (Ctrl+x Ctrl+e). Далее вы можете ввести размер ёлки.

В результате, если вы всё сделали правильно, у вас откроется новое окно, в котором отобразится результат работы программы:

::::::::::::::::::::::::::::::::::::::::::::::: ::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::::::::^::::::::::::::::::::::: ::::::::::::::::::::::^^^:::::::::::::::::::::: :::::::::::::::::::::^^^^^::::::::::::::::::::: ::::::::::::::::::::^^^^^^^:::::::::::::::::::: :::::::::::::::::::^^^^^^^^^::::::::::::::::::: ::::::::::::::::::^^^^^^^^^^^:::::::::::::::::: :::::::::::::::::^^^^^^^^^^^^^::::::::::::::::: ::::::::::::::::^^^^^^^^^^^^^^^:::::::::::::::: :::::::::::::::^^^^^^^^^^^^^^^^^::::::::::::::: ::::::::::::::^^^^^^^^^^^^^^^^^^^:::::::::::::: :::::::::::::^^^^^^^^^^^^^^^^^^^^^::::::::::::: ::::::::::::^^^^^^^^^^^^^^^^^^^^^^^:::::::::::: :::::::::::^^^^^^^^^^^^^^^^^^^^^^^^^::::::::::: ::::::::::^^^^^^^^^^^^^^^^^^^^^^^^^^^:::::::::: :::::::::^^^^^^^^^^^^^^^^^^^^^^^^^^^^^::::::::: ::::::::^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^:::::::: :::::::^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^::::::: ::::::^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^:::::: :::::^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^::::: ::::^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^:::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: :::::::::::::::::::::#####::::::::::::::::::::: ::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::::::::::::::::::::::::::::::::

Happy New Year and happy coding!