C. Глава 2. Целые числа
"В Си существует всего лишь несколько базовых типов: char - единичный байт, который может содержать один символ из допустимого символьного набора; int - целое, обычно отображающее естественное представление целых в машине; float - число с плавающей точкой одинарной точности; double - число с плавающей точкой двойной точности. Имеется также несколько квалификаторов, которые можно использовать вместе с указанными базовыми типами. Например, квалификаторы short (короткий) и long (длинный) применяются к целым."
"Значения типа char - это просто малые целые, и их можно свободно использовать в арифметических выражениях, что значительно облегчает всевозможные манипуляции с символами."
(Б. Керниган, Д. Ритчи "Язык программирования C")
Эта глава довольно важная и без чисел. Поэтому автору хотелось бы, чтобы читатели отнеслись к ней внимательно, даже, если не все сразу будет понятно. Обещаю, что дальше будет проще.
1. Целые числа в компьютере
В математике целые числа (множество Z) могут принимать значения от минус бесконечности до нуля и от единицы до плюс, или просто бесконечности. В компьютере приходится ограничивать это множество разрядностью используемых процессоров. Для дальнейшего, чтобы не делать элементарных ошибок, необходимо вполне определенно представлять, как кодируются числа в компьютере. Какой размер имеют числовые типы. Где находится знак числа, в каждом из этих случаев.
Работать с числами, не имея ясного ответа на все эти вопросы, можно только в качестве пользователя. Но нам придется программировать функции - это тупое продолжение темы ввода/вывода - для преобразования строк в числа, и чисел в строки. Любые неучтенные здесь вещи могут привести к ошибкам, некоторые из которых всплывут позже. Подобного рода функции лежат в основе почти всего последующего и являются самой нижней тарелкой в большой стопке.
Давайте начнем с самого простого типа - char. Разбирая этот тип, мы поймем устройство всех остальных целых типов, которые будут отличаться от char только размером. Сначала решается вопрос о том, сколько различных состояний может принимать char. Благодаря хорошо известной двоичной природе современной электроники используется двоичная система счисления. Поэтому, все "круглые" числа кодируются целыми степенями двоек: 2 - степень равна 1, 4 - степень равна 2 и т.д. Минимальным компьютерным "разрядом" следовало бы ожидать число 2, но оно слишком мелкое для серьезных задач. Размер многострадального байта менялся во времена дорогой памяти несколько раз (а память тогда была чуть не на вес золота), пока не принял свой современный вид: 8 двоичных разрядов.
Двойка в восьмой степени дает значение 256. Таким образом, в одном байте можно закодировать 255 целых чисел без знака. 255 потому, что ноль обязательно принадлежит любому числовому множеству, множеству целых чисел в математике он принадлежит просто по определению.
Любой бит в байте может принимать только 2 значения 0 или 1 (если, конечно, железо исправно). Если все биты равны нулю, то и байт равен нулю. Есть еще одна особенность байта - это обычно полноценный аппаратный регистр. Его можно представить как счетчик (очень распространенный режим работы регистров), который считает по кругу: 0,1, 2, … 254, 255, 0, 1,2, … Но так обстоит дело, когда байт является беззнаковым числом. Что со знаком?
Если отнять от нуля единицу, в множестве целых чисел мы получаем минус единицу. То есть, минус единица хранится в байте, когда все его биты равны единицам, а это в прежней интерпретации число 255. -2 тогда будет 254 по старому и т.д. Считать так очень удобно, но наступает момент, когда нам потребуется отличать положительные числа от отрицательных. Этот тяжкий момент естественно отложить до тех пор, пока не обнулится старший бит байта. Тогда у нас получается конфликт с положительным числом два в седьмой степени минус единица, или, что тоже самое, 0x7F в шестнадцатеричной системе или 127 в десятичной системе.
Таким образом, получается естественный признак знака: старший бит числа. Это правило остается справедливым для любого числа разрядов. Каринка ниже может кое-что пояснить на примере простого случая, для типа char:
Рис. 2-1. Наглядно о знаковом числовом типе char.
Число 127 является последним и наибольшим положительным числом в типе char, потому, что вслед за этим сразу меняется знак числа - старший бит устанавливается в единицу. Значение -128 не всегда входит в диапазон типа char, например в стандарте ANSI C множество значений типа char ограничено интервалом [-127, 127].
Следующий тип - int. Обычно его размер поддерживается на уровне 32-бита, это дает очень приличный диапазон чисел для счета, индексов, адресов памяти. Но в современных машинах может обрабатываться и 64 двоичных разряда. Это как решит компилятор для конкретной платформы. int, как и char, может быть со знаком или без. В случае использования знака любой целый тип занимает вдвое меньший интервал, что понятно, так как степень двойки уменьшается на единицу.
int может использоваться с квалификаторм long: long int, или просто long, но long не является смостоятельным типом. Такой тип на 32-разрядных машинах занимал 64 бита. Квалификатор short "уменьшает" размер типа int обычно до 2 байтов. Все беззнаковые типы объявляются как unsigned. Это самый необходимый минимум, который нам понадобится знать на ближайшее будущее.
2. Функции atoi и itoa
Alpha TO Integer - имя функции говорит о том, что символьная запись целого числа преобразуется в истинно двоичную форму. Это позарез нужная нам функция и сейчас мы как раз будем писать ее код. Вторая функция почти не нуждается в пояснении и нужна для обратной операции - извлечения числа в символьную строку.
Что нужно для написания этих функций? Для начала немного математики. Любая функция задается на множестве и определяется (принимает значения) в другом множестве. Это буквально означает, что функцию нельзя смутить, сбить с толку, никаким некорректным значением. Она должна самостоятельно обрабатывать все ошибки. Просто потому, что некорректное значение не входит в область определения функции. Так в идеале. На практике бывает иначе, но на то и идеалы, чтобы к ним стремиться.
Затем правило, которое ставит в соответствие одному значению из области определения другое значение, из области задания. Причем одно, и только одно. В программировании это называют одним словом - алгоритм. В общем, все, как в математике. Умеешь определять множества и умеешь задавать правила? Тогда у тебя почти не будет ошибок в процессе работы, и совсем не будет ошибок на выходе. Если хотя бы одного условия не выполнено, будешь лузером. Эти простые вещи нужно просто прибить гвоздями к голове и относиться к ним, как к военной присяге.
В общем, начнем с любой из функций. Пусть это будет atoi. Первым делом определим, что является ее множеством задания. Это числовые строки, строки, содержащие цифры и, возможно, знаки - или + в начале. Мы можем потребовать, чтобы число записывалось в каноническом виде - не дай бог никаких пробелов перед, и никаких веущих нулей. Но такой тупой функцией будет нелегко пользоваться. Разбор числовой строки предстает проблемой. В книге авторов языка (первое издание) функция atoi описана ради простоты достаточно незатейливо. Мы просто начинаем преобразовывать символы в число, поразрядно умножая их на 10. Ошибки не проверяются. В последующих изданиях atoi записана еще проще, но вычисления производятся при помощи плавающих (!) чисел, а затем от числа плавающего типа отделяется целая часть.
Рис. 2-2. Что может оказаться в строке с числом.
Рисунок 2-2 наглядно изображает "анатомию" числовой строки. Хотя ведущие нули встречаются не слишком часто, это бывает, и игнорировать их нельзя. В самом начале мы можем отбрасывать все пробелы и табуляции. Слово "пробелы" на картинке означает часть кода, отвечающего за пропуск начальных пробелов. Если попадется знак минус, то его контекст меняется для дальнейшего. Второй минус будет ошибкой, а это значит, что число не найдено. Это вынуждает нас изменять код, проверяющий пробелы.
Все множество символов мы можем разделить на "допускающие" продолжать работу и "недопускающие". В каждом контексте есть свое разбиение множества символов на эти классы, которые не пересекаются. Для подобных проблем этого в C используется специальная таблица и набор функций is… которые выясняют что есть что: цифра или буква (isalnum), буква (isalpha), цифра (isdigit), пробел или табуляция (isblank), и так далее, для каждого переданного им символа. Сейчас мы этим заморачиваться не будем, чтобы не отвлекаться от главной темы, тем более, что отвлечься, все равно, придется. Поехали!
Для тех, кто в прошлой главе нарезал enigma.c на новые файлы getc.c, putc.c, getchar.c и putchar.c, но не смог переработать их правильно, здесь будет подсказка. Заодно мы начнем использовать, по аналогии с m (make), похожую команду c (compile). Вот как она выглядит:
#!/bin/bash
case $1 in
'-r') a=$1
shift;;
esac
cc -S $1.c -fno-builtin -o - | sed '
/\.type/d
/\.LF/d
/\.cfi/d
/\.ident/d
/\.-main/d
/\.section/d' > $1.s
as $1.s -o $1.o
case $a in
'-r') exit;;
esac
rm $1.s
Лст. 2-1. Команда компиляции файла в объектный модуль.
Это просто немного измененная копия m. Мы ограничиваемся только компиляцией и получением объектного модуля. Ну, а если захотим увидеть код ассемблера, то можем использовать ключ -r, который предписывает оставить его на диске.
(Не забудем сделать скрипт исполняемым! : chmod 700 c) Теперь остается просто выполнить команды:
$ ls get* put*
getc.c getchar.c putc.c putchar.c
$ c getc
$ c putc
$ c getchar
$ c putchar
$ ls get* put*
getc.c getchar.o putc.c putchar.o
getchar.c getc.o putchar.c putc.o
$
Лст. 2-2. Компиляция объектных модулей.
Команды ls тут не обязательны, это просто для наглядности и чтобы убедиться, что все получилось. И теперь осталось только добавить полученные модули в список m:
#!/bin/bash
cc -S $1.c -fno-builtin -o - | sed '
/\.type/d
/\.LF/d
/\.cfi/d
/\.ident/d
/\.-main/d
/\.section/d' > $1.s
as $1.s -o $1.o
ld -s $1.o crt0.o write.o read.o getc.o putc.o \
getchar.o putchar.o -o $1
Лст. 2-3. Дополнения в m.
Если командная строка в shell-скрипте получается слишком длинной, ее можно переносить на следующую обратным слешем.
Мы могли бы убрать из m много кода, заменив его вызовом команды c. Но тогда m стал бы зависимым c, и в его отсутствии просто не мог работать. Это не одна зависимость, которую мы можем тут наблюдать. Так, например, getchar зависит от getc, а putchar зависит от putc. Зависящее не будет работать без зависимого. Любые изменения в зависящем коснутся зависимого, но не наоборот. На этом закончим отступление и вернемся в основную тему.
Сейчас нам понадобится в явном виде функция exit. Мы уже используем этот системный вызов в нашей простенькой RTL, но сейчас он будет нужен явно. Вы уже подумываете о новой функции? Этого не потребуется. Просто сделаем глобальную адресную метку в файле crt0.s и переассемблируем его:
.text
.globl _start, exit
_start:
pop %rbp
movq %rsp, %rbp
movq -8(%rbp), %rdi
leaq (%rbp), %rsi
leaq 8(%rsi,%rdi,8), %rdx
and $-16, %rsp
call main
exit:
movq %rax, %rdi
movq $60, %rax
syscall
Лст. 2-4. Новая версия crt0.s (временная)
as crt0.s -o crt0.o
Лст. 2-5. Сборка crt0.o
К сожалению, в таком виде мы не сможем передавать в функцию аргумент - код выхода. Позже мы напишем настоящую exit, а пока хватит и этой. Поскольку у нас еще слишком мало даже самого необходимого, то приходится отвлекаться от чисел и atoi почти на каждом шагу.
Вот код самой первой версии программы intnums, цель которой - написать функции atoi и itoa, проверить их работу и заодно коснуться кое-каких других аспектов, например, отладки.
//intnums.c - целые числа
int atoi( char *s )
{
int r, si = 0; // возвращаемое значение и знак
char *b, *e; // указатели начала и конца
// перечисляемый тип для состояний
enum { start, space1, sign, space2,
lzero, digits, stop };
int state = start; // переменная управляющая
// машиной состояний
char c;
while( 1 ) // машина состояний
{
c = *s++; // выбор очередного байта строки
putchar(c); //debug! мы как-нибудь пометим
exit(); // такой код. он временный.
switch( state )
{
case start:
switch( с )
{
case ' ':
case '\t':
state = space1;
continue;
case '-':
si = -1;
state = space2;
continue;
case '0':
state = lzero;
continue;
}
}
}
}
char test[] = "q - 1203.45r12"; // образец для разбора
main()
{
if( atoi( test ) == -123 ) return 0;
return 1;
}
Лст. 2-6. Первая неполная версия atoi для отладки.
Я говорил, что нам не нужен отладчик, но я не говорил, что мы не будем заниматься отладкой. Поскольку сама программа может служить отличным отладчиком, то пусть и занимается этим.
Первый тест заключается в проверке "отладчика". Ожидается, что программа напечатает первый символ строки, q. Если это произойдет, то конструкция *s++ работает правильно. Сначала должен быть считан байт из строки test, а затем увеличен указатель. Это можно выяснить, просто зная приоритеты операторов языка, но не будем слишком спешить. Я просто показываю простые способы отладки.
Запуская программу, получаем:
$ m intnums
$ intnums
q$
Лст. 2-7. Вывод отладки.
Ожидания оправдались. Мы напечатали символ, содержащийся в переменной c. Поскольку символа новой строки в поток stdout не посылалось, то bash напечатал приглашение ввода непосредственно после q.
Следующий вопрос, куда передаст управление оператор continue? Допустим, мы нашли пробел, но как продолжится цикл while? Как continue относится к родному блоку switch, внешнему блоку switch? К оператору цикла while? Это вопрос, который можно задать отладчику, то есть самой программе. Сделав предположение, поставим ловушку, перекомпилируем и запустим программу. Но не всегда сделать это слишком просто. Тогда может выручить "рентген", то есть, код ассемблера (или дамп объектного кода, но об этом как-нибудь в другой раз).
Кроме всего прочего, компилятор оптимизирует код, иногда до неузнаваемости. Например, переменная r, объявленная, но неиспользованная, вовсе не будет упомянута всуе. То же самое относится к указателям b и e. Без кода после блоков switch пример будет не слишком наглядным, и компилятор также может его оптимизировать. Поэтому будет полезно оставить такую метку, которую компилятор будет вынужден оставить в ассемблерном коде. Это сделано в следующих двух листингах.
. . .
case ' ':
case '\t':
state = space1;
asm volatile( "# >---->" ); //debug!
continue;
case '-':
si = -1;
state = space2;
continue;
case '0':
state = lzero;
continue;
}
r = 5; //debug!
asm volatile( "# } inn. sw. out" ); //
}
r = 6; //debug!
asm volatile( "# } ext. sw. out" ); //
}
. . .
Лст. 2-8. Код C подготовленный для разбора ассемблерного вывода.
.file "intnums.c"
.text
.globl atoi
atoi:
pushq %rbp
movq %rsp, %rbp
movq %rdi, -24(%rbp)
movl $0, -8(%rbp)
movl $0, -12(%rbp)
.L10: | while (1) {
movq -24(%rbp), %rax
leaq 1(%rax), %rdx
. . . . . . . . . . . . . . .
jmp .L4
.L5:
movl $1, -12(%rbp) | state = space1;
#APP
# 31 "intnums.c" 1
# >---->
# 0 "" 2
#NO_APP
jmp .L9 | continue;
.L7:
. . . . . . . . . . . . . . .
.L4: | } граница внутреннего блока switch
movl $5, -4(%rbp) | r = 5;
#APP
# 42 "intnums.c" 1
# } inn. sw. out
# 0 "" 2
#NO_APP
.L2: | } граница внешнего блока switch
movl $6, -4(%rbp) | r = 6;
#APP
# 45 "intnums.c" 1
# } ext. sw. out
# 0 "" 2
#NO_APP
jmp .L10
.L9: | } граница блока while
jmp .L10
.size atoi, .-atoi
.globl test
. . . . . . . . . . . . . . .
Лст. 2-9. Ассемблерный код после компиляции.
Разбирая листинг 2-9 мы видим, что оператор continue компилятор превратил в команду перехода на метку L9. Находим эту метку, и видим, что фактически управление возвращается на метку L10, обойдя весь временно использованный код, то есть, к очередному проходу цикла while. Все, как и было обещано синтаксисом языка.
Если кто-то может возразить, что за меткой L9 скрывается нечто важное, а автор готовит мировой заговор, то тогда посмотрим на реальный код программы. Его можно получить утилитой objdump:
$ objdump -d intnums > intnums-dump.txt
Лст. 2-9. Дизассемблирование программы intnums.
И теперь заглянем в файл дампа:
intnums: file format elf64-x86-64
Disassembly of section .text:
00000000004000b0 <.text>:
4000b0: 55 push %rbp <------------ atoi
4000b1: 48 89 e5 mov %rsp,%rbp
4000b4: 48 83 ec 20 sub $0x20,%rsp
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
уберем колонку машинных кодов
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
4000b8: mov %rdi,-0x18(%rbp) <-- s
4000bc: movl $0x0,-0x4(%rbp) <-- si
4000c3: movl $0x0,-0x8(%rbp) <-- test
4000ca: mov -0x18(%rbp),%rax | while(1){
4000ce: lea 0x1(%rax),%rdx |
4000d2: mov %rdx,-0x18(%rbp) | *s++
4000d6: movzbl (%rax),%eax |
4000d9: mov %al,-0x9(%rbp) <-- c = %al;
4000dc: movsbl -0x9(%rbp),%eax | while( 1 ) {
4000e0: mov %eax,%edi |
4000e2: mov $0x0,%eax | putch(c);
4000e7: callq 0x40022d |
4000ec: mov $0x0,%eax | exit();
4000f1: callq 0x40017e |
4000f6: mov -0x8(%rbp),%eax | case: start;
4000f9: test %eax,%eax |
4000fb: je 0x4000ff | switch( c ){
4000fd: jmp 0x4000ca <------ к началу цикла ---
4000ff: movsbl -0x9(%rbp),%eax |
400103: cmp $0x20,%eax | case ' ':
400106: je 0x400120
400108: cmp $0x20,%eax
40010b: jg 0x400114
40010d: cmp $0x9,%eax | case '\t':
400110: je 0x400120 |
400112: jmp 0x4000ca | continue;
400114: cmp $0x2d,%eax
400117: je 0x400129
400119: cmp $0x30,%eax
40011c: je 0x400139
40011e: jmp 0x4000ca
400120: movl $0x1,-0x8(%rbp) | state = space1;
400127: jmp 0x400141
400129: movl $0xffffffff,-0x4(%rbp)
400130: movl $0x3,-0x8(%rbp)
400137: jmp 0x400141
400139: $0x4,-0x8(%rbp)
400140: nop <------ наша первая вставка ------
400141: jmp 0x4000ca | continue;
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
400143: 55 push %rbp
400144: 48 89 e5 mov %rsp,%rbp
400147: bf 50 02 60 00 mov $0x600250,%edi
40014c: e8 5f ff ff ff callq 0x4000b0
400151: 83 f8 85 cmp $0xffffff85,%eax
400154: 75 07 jne 0x40015d
. . . . . . . . . . . . . . . . . . . . . . . .
Лст.2-10. Фрагмент дампа intnums, функция atoi.
Ради экономии места было убрано немало машинного кода, нас интересуют только адреса. Мы начинаем анализ с того места, где начинается работа со стеком функции. Поскольку вся отладочная информация - так приходится работать хакерам - из файла удалена, то приходится догадываться, где именно находится та или иная переменная. Компилятор действует достаточно просто: располагая стековые переменные в таком порядке: -0x4(%rbp), -0x8(%rbp), -0x9(%rbp). Поскольку у нас есть исходник на языке C, то мы можем предположить, что смещение -4 в стеке указывает на si, раз уж эта переменная инициализируется, -8 указывает на test, а -9 - на переменную с.
Так оно и окажется в действительности. И теперь мы можем прослеживать остальное. В блоке адресов 4000ca... 4000dc компилятор поместил инструкцию c = *s++; а затем идет код переключателей switch. Просто надо следовать за потоком управления, так как компилятор иногда может сварить весьма причудливый бульон, на первый взгляд, кажущийся бессмысленным. На самом деле, это дань многоступенчатому процессорному конвейеру, и наличному числу ядер процессора, так компилятор позаботился о расщеплении потока команд, чтобы процессор мог побыстрее выполнить их без неоправданных перекуров.
Так мы окончательно убедили всех фом неверующих, что метка L9 была чисто формальной. Как видите, отладчик не всегда нужен, а если удалена отладочная информация, то практически бесполезен, и приходится действовать так, как действует хакер. Конечно, отладчик здорово помогает и хакеру, так как трассировка кода в нем происходит автоматически. Но в наших простых случаях мы можем еще долго и спокойно жить без отладчиков.
Теперь можно вернуться к параграфу, откуда мы поехали на экскурсию с отладкой и продолжить работу над кодом. Допишем пусковую часть машины, раздел кода start.
Перечисляемый тип enum облегчает именование различных частей кода, фактически это просто константы 0, 1, 2, ...
Работоспособная версия кода лучше всего достигается удалением из него всех логических ошибок, в противоположность бесконечному тестированию. Конечно, это нелегко. Тем более, что и на этом пути нет полной гарантии от ошибок. Однако, именно такой код оказывается в дальнейшем легко обслуживаемым. Он же обычно оказывается легким (в смысле объема) и быстрым.
//intnums.c - целые числа
int atoi( char *s )
{
int r, si = 0; // возвращаемое значение и знак
char *b, *e; // указатели начала и конца
// перечисляемый тип для состояний
enum { start, space, lzero, digit, digits };
int state = start; // переменная управляющая
// машиной состояний
char c;
while( 1 ) // машина состояний
{
c = *s; // выбор очередного байта строки
switch( state )
{
case start: // в самом начале
switch( c ) // смотрим, что в c
{
case ' ': // если пробел
case '\t': // или символ табуляции, то
s++; // переходим к следующему символу
continue; // ... продолжаем ...
case '-': // если минус, то
si = -1; // запоминаем знак в переменной
s++;
state = space; // и проверяем пробелы
continue; // после знака минус
case '0': // если ведущий ноль, то сразу
s++;
state = lzero; // переходим на его пропуск
continue;
case '1': // если ненулевая цифра, то
case '2': // изменяем состояние автомата,
case '3': // но указатель не перемещается
case '4': // на следующий символ, так как
case '5': // еще неизвестно, что может на
case '6': // него повлиять
case '7':
case '8':
case '9':
state = digit;
continue;
default: // по умолчанию: в этом контексте,
return 0; // любой нецифровой символ является
} // ошибкой и мы возвращаем ноль
case space: // контекст пробелов после знака минус
switch( c )
{
case ' ': // пробелы и табуляции
case '\t': // обрабатываются как прежде
s++;
continue;
case '0': // еще раз проверяем на ведушие
s++; // нули и переходим, если надо
state = lzero;
continue;
case '-':
return 0; // второй минус - ошибка!
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
state = digit;
continue;
default: // любой другой символ показывает,
return 0; // что числа в этой строке нет
}
case lzero: // пропуск ведущих нулей
switch( c )
{
case '0': // если обнаружен еще один ведущий
s++; // ноль, продолжаем игнорировать
continue; // все остальные
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
state = digit;
continue;
default: // как и прежде, любой нецифровой
return 0; // символ будет ошибкой
}
case digit: // случай первой цифры обрабатывается
b = s; // только в этом месте, чтобы не было
s++; // ошибок с указателем на нее
state = digits; // затем можно обрабатывать все
continue; // остальные цифры
case digits: // перебор цифр
switch( c )
{
case '0': // теперь все цифры в оставшейся
case '1': // последовательности являются
case '2': // значащими, включая ноль
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
s++; // поэтому продолжаем выбирать
continue; // их до конца, и любая нецифра
default: // является признаком остановки
e = s; // и сохранения указателя
}
}
break; // прерываем цикл while
}
putchar(*b); //debug! первый символ
putchar(*e); // последний символ + 1
putchar( '0' + e-b ); // длина последовательности
exit(); //
}
char test[] = " - 00014567.45r12"; // образец для разбора
main()
{
atoi( test );
}
Лст. 2-11. Автомат для разбора целого числа в строке.
Всегда ли будет код из листинга 2-11 работать правильно? Если мы докажем, что это так, то тогда тестирование будет играть роль поиска опечатков: если компилятор пропустит код, то тогда ошибкой может быть случайное использование какой-нибудь переменной или константы на на месте.
В новой версии убраны лишние состояния. В разделе start машина пропускает все пробелы (разделители). Это логично, так как никаким числом в таком случае и не пахнет. Число может появиться только в двух случаях: появление цифры или знака минус (легко добавить и плюс, если необходимо). Все остальное должно просто закончить функцию с возвратом нуля. Можно просто взять и проанализировать каждый переход, так как число всех состояний и переходов конечно.
Рис. 2-3. Диаграмма состояний автомата разбора строки с числом.
1. Переход совершается в случае пробелов.
2. Обнаружен знак минус.
3. Обнаружена ненулевая цифра 1...9.
4. Все, кроме цифр, минуса и пробелов.
5. Ноль.
6. Безусловный переход.
7. Ноль.
8. Пробел, минус, любой нецифровой символ.
9. Пробелы.
10. Обнаружена цифра 1...9.
11. Пробел, минус, любой нецифровой символ.
12. Ноль.
13. Безусловный переход.
14. Безусловный переход.
15. Все цифры, включая ноль.
16. Любой символ, отличный от цифры.
Тестовая версия из листинга 2-11 занимает около 2 Kb места. Используя препроцессор, можно написать более короткую версию, которая займет вдвое меньше места. Назовем ее intnums1:
//intnums1.c - целые числа. версия с макрофункциями
#define dig() *s<'1'||*s>'9'?0:1
#define digz() *s<'0'||*s>'9'?0:1
#define spskip() while(*s==' '||*s=='\t')s++
#define lzskip() while(*s=='0')s++
#define dgskip() while(digz())s++
int atoi( char *s )
{
int r, si = 1; // возвращаемое значение и знак
char *b, *e, i; // указатели начала и конца, индекс
spskip(); // пропустим начальные пробелы
if( *s == '-' ) // сохранение знака минус
{ si = -1; s++; };
spskip(); // пропустим пробелы
if( *s == '-' ) return 0; // нечего искать
if( *s == '0' ) lzskip(); // пропускаем ведущие нули
if( dig() ) b = s; // устанавливаем нач. указатель
else return 0; // при нецифре выходим
dgskip(); // пропускаем цифры
e = s; // устанавливаем кон. указатель
putchar(*b); //debug! первый символ
putchar(*e); // последний символ + 1
putchar( '0' + e-b ); // длина последовательности
exit(); //
}
char test[] = " - 00140067.45r12"; // образец для разбора
main()
{
atoi( test );
}
Лст. 2-12. Альтернативная версия atoi.
Препроцессор читает файл, и делает подстановку текста, заменяя макроопределения тем, что стоит после них. Компилятору, все равно, передается не файл, а его образ в памяти, так что есть смысл в таких вещах. В нашей книжке мы не предлагаем читателям вещи для зубрежки, для этого есть другие источники информации. Мы берем только то, что будет полезно в данный момент и тут же используем его, глядя на то, как это работает.
Макроопределения очень полезны для задания констант, разбросанных по коду команды. Изменения производятся только в одном месте, а касаются всего кода. В больших программах это удобно. Впрочем, не только константы, но и функции можно таким образом использовать, и они могут помочь даже в маленьких программах, как мы видим. Есть у макроопределений и недостатки - они могут сильно затруднить отладку кода, поэтому доверять им можно только очень хорошо проверенные алгоритмы.
Проверим обе версии на размер кода:
$ du -b intnums intnums1
2016 intnums
1272 intnums1
$
Лст. 2-13. Сравнение размеров программ.
Интересно было бы сравнить и быстродействие. Это несложно организовать:
. . .
//putchar(*b); //debug! первый символ
//putchar(*e); // последний символ + 1
//putchar( '0' + e-b ); // длина последовательности
//exit(); //
}
char test[] = " - 00140067.45r12"; // образец для разбора
main()
{
int i = 1000000;
while( i-- ) atoi( test );
}
Лст. 2-14. Простой тест быстродействия.
Заставим обе программы вызвать atoi по миллиону раз и сравним результаты тестов:
$ m intnums
$ m intnums1
$ time intnums
real 0m0.092s
user 0m0.092s
sys 0m0.000s
$ time intnums1
real 0m0.043s
user 0m0.040s
sys 0m0.000s
$
Лст. 2-15. Результаты теста на быстродействие.
Итак, вторая версия не только почти вдвое меньше, но и вдвое быстрее, то есть, в три раза эффективней. Если функция вызывается один раз, то такая разница практически ничего не означает, но она может вызываться десятки миллионов раз за небольшое время, и тогда это может стать довольно критичным. Как бы ни было, обе версии имеют свои преимущества: например, в первую из них гораздо легче вносить изменения, а вторая вряд ли была так понятна без первой.
Вот сколько геморроя может потребоваться, чтобы задать область определения для функции, в том смысле, который здесь имеется в виду: функция должна сама уметь выбирать корректные значения, так как на ее вход может поступать что угодно.
Теперь время делать вторую часть: преобразовать полученную строку в целое число, и проследить, чтобы при этом не возникло никаких ошибок. Сложно сказать, как работали при создании библиотек C отцы основатели и первопроходцы, но сейчас нам позарез понадобится функция itoa, и функция, печатающая строку. Поэтому пока прервемся с atoi, и начнем писать функцию itoa. Сделать это будет проще, так как целое число хранится в памяти во вполне определенном формате, исключающем любые сюрпризы.
Проще всего выглядит функция для печати строки:
int puts( char *s )
{
int e;
while( *s )
{
e = putchar( *s++ );
if( e == -1 ) break;
}
putchar( '\n' );
return e;
}
Лст. 2-16. Функция puts для вывода строки в stdout.
Пока в строке есть байты, отличающиеся от нулевого байта, вызывается функция putchar. Если происходит ошибка, возвращается EOF. Строка, хотя до сих пор это не оговаривалась, имеет единственное ограничение: нуль-терминатор, байт, равный нулю. Это снимает нелепые ограничения, которые накладывают другие языки, в которых длина кодируется байтом или двумя. И кто их только придумал? После того, как строка выведена, в поток дописывается символ новой строки.
Функция itoa пишется значительно проще, чем atoi. Как уже говорилось, по причине того, что множество ее аргументов почти не содержит некорректных значений. Но как мы увидим скоро, все-таки содержит. Поскольку эта функция считается нестандартной, то мы напишем ее так, как представляется удобным. Вот ее код:
char *itoa( int v, int b )
{
static char s[33]; // строка для результата
char sgn = 0, *rp = s + 32; // знак и возв. указатель
if( v < 0 ) { v *= -1; sgn = '-'; } // учет знака
*rp = '\0'; // нуль-терминатор выходной строки
// случай, когда аргумент функции равен нулю
if( v == 0 ) { *(--rp) = '0'; return rp; };
// поразрядное получение цифр числа
while( v != 0 )
{
*(--rp) = v % b + '0';
v /= b;
}
// восстановление знака
if( sgn == '-' ) *(--rp) = sgn;
return rp;
}
Лст. 2-17. Функция itoa.
Отличие от "стандартной", лучше сказать, общеизвестной, объявляемой как char *itoa( int value, char *str, int base ); здесь в том, что у нас только два аргумента: числовое значение и основание числовой системы. Внутри функции используется статическая переменная длиной 32 символа. Так много выделено для тех, кто захочет вывести число -31^2 в двоичном виде. В таком виде число -1111111111111111111111111111111 содержит 1 байт для знака, 31 цифру, и еще требуется байт для нуль-терминатора, итого 33 байта.
Перед началом работы функции указатель rp инициализируется адресом последнего байта строки. Если число меньше нуля, оно умножается на минус единицу, то есть, делается положительным, чтобы положительные и отрицательные числа обрабатывались одинаково. Последний байт строки s инициализируется нуль-терминатором. Если число равно нулю, то можно сразу вернуть соответствующий результат. По указателю rp записывается символ нуля, перед этим указатель предварительно уменьшается на одну позицию в строке. После этого, вызывающей функции возвращается его значение.
Если v отличен от нуля, то мы выполняем цикл выделения цифр числа, который работает до получения последней цифры. Его суть в том, мы последовательно выясняем значения остатков от деления этого числа на основание числовой системы, например, десятичной. Каждый остаток складывается с символом нуля и образует символ соответствующей цифры. Затем надо поделить число на основание системы счисления и сохранить результат для очередного прохода цикла.
Если число меньше нуля, то к нему дописывается знак, информация о чем была получена в самом начале и сохранилась в форме значения '-' в переменной sgn. Функция возвращает указатель на строку с результатом, на его первый байт.
Когда мы передаем этой функции некоторое число, она печатает его верно:
main()
{
puts( itoa( -7809, 10 ) );
puts( itoa( -2, 10 ) );
puts( itoa( -1, 10 ) );
puts( itoa( 0, 10 ) );
puts( itoa( 1, 10 ) );
puts( itoa( 12, 10 ) );
puts( itoa( 123, 2 ) );
}
. . .
$ m intnums; intnums
-7809
-2
-1
0
1
12
123
$
Лст. 2-18. Тест функции возле нуля.
Но вот еще небольшой тест:
main()
{
puts( itoa( -2147483646, 10 ) );
puts( itoa( -2147483647, 10 ) );
puts( itoa( -2147483648, 10 ) );
puts( itoa( -2147483649, 10 ) );
puts( itoa( -2147483650, 10 ) );
puts( "----------------------" );
puts( itoa( 2147483646, 10 ) );
puts( itoa( 2147483647, 10 ) );
puts( itoa( 2147483648, 10 ) );
puts( itoa( 2147483649, 10 ) );
puts( itoa( 2147483650, 10 ) );
}
. . .
$ m intnums; intnums
intnums.c: In function ‘main’:
intnums.c:77:5: warning: overflow in implicit constant
conversion [-Woverflow]
puts( itoa( -2147483649, 10 ) );
^
intnums.c:78:5: warning: overflow in implicit constant
conversion [-Woverflow]
puts( itoa( -2147483650, 10 ) );
^
-2147483646
-2147483647
-./,),(-*,(
2147483647
2147483646
----------------------
2147483646
2147483647
-./,),(-*,(
-2147483647
-2147483646
$
Лст. 2-19. Тест вблизи переполнения типа int.
Компилятор предупреждает о переполнении в константе, а затем и программа выдает ошибочные результаты. О значениях -2147483648 и 2147483648 никаких предупреждений нет, но это как раз то значение, где функция спотыкается и начинает выдавать мусор.
Давайте посмотрим, как выглядит этот фрагмент в настоящем дампе, полученном утилитой objdump. Так как нас интересуют сами числа а не код, создадим крохотную программу такого содержания:
//ovf.c - как выглядят очень большие числа
int demo[] = {
-2147483646, -2147483647, -2147483648, -2147483649, -2147483650
2147483646, 2147483647, 2147483648, 2147483649, 2147483650 };
main(){}
Лст. 2-20. Тест для просмотра данных.
Для начала получим ассемблерный код:
$ c -r ovf
ovf.c:4:1: warning: overflow in implicit constant
conversion [-Woverflow]
-2147483646, -2147483647, -2147483648, -2147483649, -2147483650,
^
ovf.c:4:1: warning: overflow in implicit constant
conversion [-Woverflow]
$
Лст. 2-21. Получим объектный модуль в коде ассемблера.
Дальше