68. Массивы и строки

Массив — это несколько значений одного типа, лежащих подряд. Строка в C — тот же массив символов, у которого в конце стоит ноль. Никакой другой «строки» в языке нет, и почти все ошибки со строками — следствие того, что это просто массив.

На микроконтроллере у массивов появляется вопрос, которого на компьютере не задают: где они лежат. От одного слова const зависит, займёт таблица место только во Flash или ещё и в ОЗУ, которого в десятки раз меньше. Это посчитано по настоящим объектным файлам.

Как это называется в документации

Оригинал	Перевод
array, element, index	массив, элемент, индекс
initializer list	список начальных значений
designated initializer	инициализация с указанием индекса
out-of-bounds access	выход за границу массива
variable-length array (VLA)	массив переменной длины
row-major order	построчное размещение
null-terminated string	строка с завершающим нулём
string literal	строковая константа
buffer overflow	переполнение буфера
truncation	обрезка
scan set	набор символов в scanf
checksum, CRC	контрольная сумма, циклический код

68.1 Массив: одинаковые элементы подряд

int a[5];                   /* пять int подряд: a[0] … a[4] */
float t[24];                /* температура по часам */

Индексы начинаются с нуля, последний — на единицу меньше размера. Все элементы лежат вплотную, и a[i] — это *(a + i) (раздел 67.4).

Число элементов считают так:

#define COUNT(arr) (sizeof(arr) / sizeof((arr)[0]))

Это работает, пока arr — настоящий массив. Переданный в функцию массив становится указателем, и там формула даст неправду (раздел 67.5).

Размер массива должен быть известен при компиляции: число или #define. Переменная не подходит — кроме случая, о котором в 68.5.

68.2 Начальные значения

int x[5] = {7, 5};          /* 7 5 0 0 0 — недостающие становятся нулями */
int z[100] = {0};           /* все сто — нули */
static const int lut[5] = {[3] = 9};   /* 0 0 0 9 0 — задан только четвёртый */

Правило простое: если задан хоть один элемент, все незаданные — нули. Запись [3] = 9 удобна для таблиц, где индекс — номер команды или состояния: видно, какому номеру что соответствует.

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

Обнулить массив позже — отдельная задача: = {0} работает только при объявлении. Потом используют memset(a, 0, sizeof a) или цикл — и это одно и то же: и цикл обнуления, и memset компилятор превращает в один и тот же вызов библиотечной функции __aeabi_memclr4.

68.3 Где массив живёт на камне

Вот что происходит с одним и тем же массивом на 256 байт в зависимости от объявления — по размерам секций объектного файла:

Вторая строка — самая дорогая. Массив без const с начальными значениями занимает место дважды: образ начальных значений лежит во Flash, а при старте копируется в ОЗУ (раздел 11.2). Таблица шрифта, синуса или команд, объявленная без const, — это килобайты ОЗУ, потраченные ни на что. Отсюда правило из раздела 3.6: всё, что не меняется, — const.

Третья строка дешевле: массив нулей не хранится во Flash вовсе, стартовый код просто обнулит нужную область ОЗУ.

Четвёртая — про стек. Большой локальный массив съедает стек при каждом вызове (раздел 66.7), и буферы на килобайт делают static или глобальными.

68.4 Выход за границу

Индекс никто не проверяет. a[5] у массива из пяти элементов прочитает или запишет то, что лежит в памяти следом, — обычно соседнюю переменную:

int a[5];
int n = 1;
a[n - 2] = 3;       /* a[-1]: запись перед началом массива */
a[5] = 100;         /* запись после конца */

Компилятор замечает выход за границу, только когда индекс — константа: на a[5] он предупредит без всяких ключей — «array index 5 is past the end of the array». Индекс из переменной не проверяется никак.

На компьютере такая ошибка иногда роняет программу; на камне почти никогда — там за массивом просто другие данные, и они молча портятся. Проявляется это «переменная меняется сама по себе» — в месте, никак не связанном с ошибкой.

Защита — дисциплина: размер хранить рядом с массивом, индекс проверять на входе функции, для приёма данных — всегда ограничивать длину.

68.5 Массив переменной длины

Стандарт C99 разрешает локальный массив, размер которого известен только во время работы:

void process(int n)
{
    int buf[n];         /* размер — значение n */
    ...
}

На компьютере это удобно. На микроконтроллере — опасно: массив ложится на стек, и сколько стека понадобится, зависит от данных. Посчитать это заранее нельзя ни вам, ни компоновщику (раздел 66.7).

Компилятор принимает такой массив молча — даже с -Wall -Wextra. Предупреждает только отдельный ключ -Wvla, и в проектах для микроконтроллеров его стоит включать. Правильная замена — массив максимального размера и отдельная переменная с числом занятых элементов.

68.6 Типовые операции

Возьмём int a[6] = {5, 3, 8, 1, 9, 2}.

Позиция минимума и максимума — один проход с запоминанием индекса; здесь минимум на позиции 3, максимум — на 4.

Циклический сдвиг влево — запомнить первый, сдвинуть остальные, первый поставить в конец: 3 8 1 9 2 5.

Разворот — обменивать элементы с двух концов до середины: 2 9 1 8 3 5.

void reverse(int *a, int n)
{
    for (int i = 0; i < n / 2; i++) {
        int t = a[i];
        a[i] = a[n - 1 - i];
        a[n - 1 - i] = t;
    }
}

Сортировка пузырьком — соседние элементы, стоящие не по порядку, меняются местами; за каждый проход самый большой «всплывает» в конец. Если за проход не было ни одного обмена, массив уже упорядочен и можно остановиться:

for (int i = 0; i < n - 1; i++) {
    int swapped = 0;
    for (int j = 0; j < n - 1 - i; j++)
        if (a[j] > a[j + 1]) { swap(&a[j], &a[j + 1]); swapped = 1; }
    if (!swapped) break;
}

На десяти элементах это 9 сравнений, если массив уже упорядочен, и 45, если упорядочен в обратную сторону. Сортировка выбором — найти минимум оставшейся части и поставить его на место — даёт тот же результат. Для небольших массивов на камне обе годятся; для больших есть qsort в стандартной библиотеке (раздел 74), а как сравнивать алгоритмы — раздел 76.

68.7 Двумерные массивы

int m[3][5];            /* 3 строки по 5 элементов */

В памяти это одна строка за другой: сначала пять элементов m[0], потом пять m[1], потом m[2]. Соседние строки отстоят на 5 элементов, строка занимает 20 байт, весь массив — 60. Адрес m[i][j] компилятор считает как начало + (i · 5 + j) · 4.

Отсюда два практических следствия.

Обходить массив нужно по строкам: внутренний цикл — по последнему индексу. Так обращения идут подряд по памяти.

В функцию двумерный массив передают с размером строки — иначе компилятор не сможет посчитать адрес:

void print(int rows, int a[][5]);              /* число столбцов — константа */
void print(int rows, int cols, const int *a);  /* a[i * cols + j]; вызов: print(3, 5, &m[0][0]) */

Запись a[rows][cols] с переменными размерами — тоже массив переменной длины, и -Wvla (раздел 68.5) на неё предупредит.

Пример с камня — кадр монохромного дисплея 128 × 64 точки. Каждый байт хранит восемь точек столбца, поэтому кадр — это uint8_t fb[8][128], 1024 байта. На камне с 20 КБ ОЗУ это 5 % всей памяти — вот почему изображение часто рисуют прямо в дисплей, без кадра в памяти.

68.8 Строка — массив с нулём в конце

char st[] = "hello";    /* 6 байт: h e l l o \0 */
char buf[10] = "hello"; /* 10 байт: hello, \0 и ещё четыре нуля */

Длина строки нигде не хранится. Конец обозначен символом с кодом ноль, и все функции идут по строке, пока его не встретят. Отсюда разница, которую надо помнить:

strlen устроена просто:

size_t my_strlen(const char *s)
{
    size_t n = 0;
    while (*s++) n++;
    return n;
}

Два следствия. Первое: strlen каждый раз проходит строку целиком — вызывать её в условии цикла по той же строке расточительно. Второе, важное для обмена данными: двоичные данные — не строка. Байт 0x00 посреди пакета strlen примет за конец (раздел 37).

И не путайте три нуля: '\0' — символ с кодом 0, конец строки; '0' — цифра, код 48; "0" — строка из цифры и завершающего нуля, два байта.

68.9 Строка во Flash и в ОЗУ

С размещением строк та же история, что с массивами, но с одной тонкостью:

Во второй строке сама строка лежит во Flash, но указатель на неё — обычная переменная, её можно перенаправить, поэтому она в ОЗУ, а её начальное значение при старте копируется из Flash (как в таблице 68.3). Чтобы и указатель ушёл во Flash, нужен второй const. По Flash разницы нет — 10 байт в обоих случаях, — а ОЗУ он экономит: 4 байта на строку, 400 — на таблицу из сотни сообщений.

Писать в строковую константу нельзя: это неопределённое поведение, а на STM32 константа вообще лежит во Flash, которую обычной записью не изменить (раздел 11.5). Если строку нужно менять — объявляйте массив.

68.10 Функции для строк

Стандартные функции из string.h — strlen, strcpy, strcat, strcmp и другие — подробно в разделе 74. Здесь — три ловушки.

Строки нельзя сравнивать через ==. Это сравнение адресов, а не содержимого: два массива с одинаковым текстом "hello" дают == ложь. Сравнивают strcmp: она возвращает ноль при равенстве, отрицательное число, если первая строка меньше, и положительное, если больше.

strcpy не знает размера приёмника и пишет, пока не встретит ноль в источнике. Строка длиннее буфера перепишет всё, что за ним лежит.

strncpy не спасает так, как кажется. Если строка не поместилась, она копирует ровно столько символов, сколько разрешено, — и не ставит завершающий ноль:

char d[8];
strncpy(d, "hello world", 5);   /* d = h e l l o и дальше — что было в памяти */

Безопасный способ — snprintf: он всегда ставит ноль и никогда не пишет больше, чем разрешено:

char e[6];
int n = snprintf(e, sizeof e, "%s", "hello world");   /* e = "hello", n = 11 */
if (n >= (int)sizeof e) { /* не поместилось */ }

Возвращает он длину, которая получилась бы без ограничения, — по ней видно, что строка обрезана. На камне это главный инструмент сборки строк: сообщения в порт, строки для дисплея.

68.11 Разбор строк

Строка из последовательного порта — самый частый ввод на камне. sscanf разбирает её по формату, а набор символов %[…] задаёт, что считать частью поля:

char key[20], val[20];
int r = sscanf(line, "%19[0-9]=%19[a-z]", key, val);

Ширина 19 — размер буфера минус место под завершающий ноль. Без неё длинная строка из порта перепишет память за буфером (раздел 74.5).

sscanf возвращает, сколько полей удалось заполнить, — это и есть проверка разбора:

Проверять результат обязательно: при нуле и единице в val остаётся то, что было раньше.

Для чисел на камне чаще берут strtol — она сообщает, где кончилось число, и не тянет за собой весь форматный разбор (раздел 74).

Массив байтов и контрольная сумма. Типичная обработка массива на камне — посчитать контрольную сумму пакета. Вот CRC-8 с полиномом 0x31 и начальным значением 0xFF:

uint8_t crc8(const uint8_t *p, unsigned len)
{
    uint8_t crc = 0xFF;
    while (len--) {
        crc ^= *p++;
        for (int b = 0; b < 8; b++)
            crc = (crc & 0x80) ? (uint8_t)((crc << 1) ^ 0x31) : (uint8_t)(crc << 1);
    }
    return crc;
}

Для строки "123456789" она даёт 0xF7 — это контрольное значение алгоритма, по которому проверяют любую реализацию. Аппаратный блок CRC считает быстрее, но не всякий CRC: у F1 и F4 он умеет только CRC-32 с полиномом 0x04C11DB7, и этот CRC-8 ему не по силам. Полином 0x31, ширину 8 бит и начальное значение задают только настраиваемому блоку — у G4, L4 и других семейств из раздела 12.5.

68.12 Грабли

Таблица «съела» ОЗУ. Объявлена без const — занимает место и во Flash, и в ОЗУ.

Переменная меняется сама по себе. Запись за границу соседнего массива.

Размер массива в функции неверный. sizeof от указателя; размер передают параметром.

Стек переполнился на одних данных и не на других. Массив переменной длины. Ключ -Wvla находит такие места.

Двумерный массив обходится медленно. Внутренний цикл идёт по первому индексу — поперёк памяти.

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

sizeof строки на единицу больше длины. Завершающий ноль.

if (s == "on") никогда не срабатывает. Сравниваются адреса; нужна strcmp.

После strncpy строка «продолжается» мусором. Не поставлен завершающий ноль.

Строка для дисплея переписала соседние данные. strcpy или sprintf без ограничения длины; нужен snprintf.

Разбор команды иногда берёт старое значение. Не проверен результат sscanf.

Запись в строку не работает. Это константа во Flash; нужен массив.

68.13 Итоги

• Массив — элементы подряд; sizeof(a) / sizeof(a[0]) — число элементов, пока a не стал указателем.
• Незаданные начальные значения — нули, если задан хоть один; {[3] = 9} задаёт элемент по индексу.
• На камне const-таблица лежит только во Flash, таблица без const — во Flash и в ОЗУ, массив нулей — только в ОЗУ.
• Выход за границу никто не проверяет; компилятор замечает только постоянный индекс.
• Массив переменной длины — неизвестный расход стека; предупреждает только -Wvla.
• Пузырёк на 10 элементах — от 9 до 45 сравнений.
• Двумерный массив лежит по строкам; кадр дисплея 128 × 64 — 1024 байта.
• Строка — массив с нулём в конце; sizeof — место, strlen — длина.
• const char * оставляет указатель в ОЗУ; const char *const уносит во Flash и его.
• Строки сравнивают strcmp, собирают snprintf; strncpy при обрезке не ставит ноль.
• sscanf возвращает число разобранных полей — его проверяют всегда; у %[…] и %s задают ширину — размер буфера минус один.
• CRC-8 строки "123456789" с полиномом 0x31 — 0xF7.

Дальше: раздел 69 «Вещественные числа».