В этом тексте вы узнаете зачем программистам микроконтроллеров нужна стабильная сортировка.
В программировании микроконтроллеров периодически приходится решать задачу о выявлении пересечения интервалов. Чаще всего это нужно при разработке загрузчиков и NVRAM, чтобы во время исполнения прошивки определять, что диапазоны памяти конфигов в самом деле пересекаются или не пересекаются.
Например Вы пишете загрузчик. Поступает команда прописать память от и до. Надо убедиться, что диапазон памяти самого загрузчика не пересекается с той памятью, которую надо изменить.
Второй пример. Вы хотите прописать массив в Flash память. Надо прежде всего проверить принадлежит ли вообще массив области Flash памяти. Если да, то начать писать. Если нет, то выдать ошибку.
Третий пример. Стандарт разработки ПО ISO-26262 требует перед применением конфига проверять его на валидность в run-time.
На первый взгляд простая задачка, однако, как оказалось, реализовать такое в коде - это вовсе нетривиальная задачка. Но обо всём по порядку...
Постановка задачи
Даны два непрерывных интервала:
номер интервала | Начало | Конец | Имя интервала |
1 | x1_start | x1_end | A |
2 | x2_start | x2_end | B |
Определить:
1--пересекаются ли эти два интервала?
2--поглощает ли один интервал другой?
4--стыкуются ли эти два интервала
5--прочее
Тут же добавлю модульные тесты для процедуры проверки факта пересечения интервалов
# | A | B | Пересекаются? | комментарий |
1 | [1 7] | [5 9] | 1 | нахлёст |
2 | [1 9] | [6 8] | 1 | В внутри А |
3 | [0 1] | [1 2] | 0 | соприкасаются |
4 | [0 1] | [2 3] | 0 | |
5 | [0 1] | [1 1] | 1 | точечный интервал с краю |
6 | [7 7] | [0 9] | 1 | точечный интервал внутри |
7 | [0 5] | [5 9] | 0 | соприкасаются |
В качестве X может быть всё, что только угодно: адреса физической памяти, время (time-stamp) отправки и прибытия автобусов, напряжение, диапазон радио частот. Словом всё, что обычно распределяется в виде диапазона величин.
Терминология
Непрерывные интервалы пересекаются, если существуют точки, которые присутствует в обоих интервалах.
Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка.
Название алгоритма | Название алгоритма | AVERAGE Performance |
insertion sort | Сортировка вставками | ¼ n 2 |
bubble sort | Сортировка пузырьком | ½ n 2 |
mergesort | Сортировка слиянием | n log2 n |
множество типа continuum - множество, где между двумя числами из множества всегда можно выбрать число, которое по середине.
Решение
Вы конечно можете применить аппарат линейной алгебры, представить интервалы в виде векторов, потом двигать вертикальный вектор Vy=(0; 1) и на каждом числе искать пересечение векторов. Однако это безумно много вычислений. Так не правильно.
Есть решение проще. Надо взять интервалы и представить их в другой форме записи.
Фаза 1: Превратить интервалы в массив точек
Мы представим векторы в виде последовательности точек. Образно выражаясь, расщепим интервалы на атомарные точки. Возьмём два интервала и составим из них массив точек. При этом каждая точка, как структура данных, будет обладать следующими тремя свойствами.
№ | Название переменной | возможные значения |
1 | Координата Х | целое число (-N, -1, 0, 1, +N) |
2 | Тип скобки | начало или конец интервала: [ или ] |
3 | Номер самого интервала | натуральное число (1 2 3 4 5) |
Получится массив структур из 4х точек.
Фаза 2: Сортировка
Выберем массив точек и выполним последовательно три стабильные сортировки. Порядок сортировок имеет тут ключевое значение.
# | критерий сортировки | компаратор |
1 | по скобкам | [ < ] |
2 | по номеру интервала | 1<2 |
3 | по координате X | 1<2 |
Тут нужна именно стабильная сортировка, чтобы очередная сортировка (по X) не испортила порядок с одинаковыми значениями x для предыдущей сортировки по типу скобки.
Фаза 3 Поиск пересечения
Вот у нас кристаллизовался трижды отсортированный массив. Главный порядок - это последняя сортировка по X.
Теперь надо завести переменную cross. Читаем точки массива с лева-направо -->. Если встретили открывающую скобку, то увеличиваем cross на +1 . Если встретили закрывающуюся скобку, то вычитаем -1 из cross. Таким образом, если во время обхода массива переменная cross принимает 2, то это значит, что тут интервалы начали пересекаться.
Просто и не затейлево.
Практическая часть
Итак, танцуем от печки... Точку представим в виде структуры данных IntervalPoints_t.
typedef enum {
INT_POINT_START = 1,
INT_POINT_END = 2,
INT_POINT_UNDEF = 0,
} IntervalPoint_t;
typedef struct {
uint32_t val;
uint32_t num;
IntervalPoint_t type;
} IntervalPoints_t;
typedef struct {
uint32_t start;
uint32_t end;
} IntervalE_t;
typedef struct {
uint32_t start;
uint32_t size;
} IntervalS_t;
Перед вами набор основных функций для обработки интервалов
Скрытый текст
#include "interval.h"
#include <stdlib.h>
#include <string.h>
#include "data_utils.h"
#include "log.h"
bool is_interval_e(const IntervalE_t* const Interval) {
bool res = false;
if(Interval->start < Interval->end) {
res = true;
}
return res;
}
bool IntervalConvert_e_s(const IntervalE_t* const in,
IntervalS_t* const out) {
bool res = false;
res = is_interval_e(in);
if(res) {
out->start = in->start;
out->size = in->end - in->start;
}
return res;
}
bool IntervalConvert_2_1(const IntervalS_t* const in,
IntervalE_t* const out) {
bool res = false;
if(in) {
if(out) {
out->start = in->start;
out->end = in->start + in->size;
}
}
return res;
}
static int comp_points(const void* elem1,
const void* elem2) {
if((((IntervalPoints_t*)elem2)->val) <
(((IntervalPoints_t*)elem1)->val))
return 1;
if((((IntervalPoints_t*)elem1)->val) <
(((IntervalPoints_t*)elem2)->val))
return -1;
return 0;
}
static int comp_num(const void* elem1,
const void* elem2) {
int ret = 0;
if((((IntervalPoints_t*)elem2)->num) <
(((IntervalPoints_t*)elem1)->num) )
ret = 1;
if((((IntervalPoints_t*)elem1)->num) <
(((IntervalPoints_t*)elem2)->num) )
ret = -1;
return ret;
}
static int comp_bracket(const void* elem1,
const void* elem2) {
int ret = 0;
if((((IntervalPoints_t*)elem2)->type) <
(((IntervalPoints_t*)elem1)->type) )
ret = 1;
if((((IntervalPoints_t*)elem1)->type) <
(((IntervalPoints_t*)elem2)->type) )
ret = -1;
return ret;
}
bool interval_intersect(const IntervalE_t* const A,
const IntervalE_t* const B) {
bool res = false;
IntervalPoints_t Point[4] = {0};
Point[0].val = A->start;
Point[0].type = INT_POINT_START;
Point[0].num = 1;
Point[1].val = A->end;
Point[1].type = INT_POINT_END;
Point[1].num = 1;
Point[2].val = B->start;
Point[2].type = INT_POINT_START;
Point[2].num = 2;
Point[3].val = B->end;
Point[3].type = INT_POINT_END;
Point[3].num = 2;
mergeSort(Point, ARRAY_SIZE(Point),
sizeof(IntervalPoints_t), comp_bracket);
mergeSort(Point, ARRAY_SIZE(Point),
sizeof(IntervalPoints_t), comp_num);
mergeSort(Point, ARRAY_SIZE(Point),
sizeof(IntervalPoints_t), comp_points);
uint32_t i = 0;
int32_t cnt = 0;
for(i = 0; i < ARRAY_SIZE(Point); i++) {
switch(Point[i].type) {
case INT_POINT_START:
cnt++;
break;
case INT_POINT_END:
cnt--;
break;
default:
break;
}
if(1 < cnt) {
res = true;
break;
}
}
return res;
}
А функция interval_intersect_continuum ищет ненулевые пересечения. В случае их нахождения возвращает true.
bool interval_intersect_continuum(const IntervalE_t* const A,
const IntervalE_t* const B) {
bool res = false;
bool spot_start = false;
bool spot_end = false;
IntervalE_t commom_e = {
.start = 0,
.end = 0,
};
IntervalPoints_t Point[4] = {0};
Point[0].val = A->start;
Point[0].type = INT_POINT_START;
Point[0].num = 1;
Point[1].val = A->end;
Point[1].type = INT_POINT_END;
Point[1].num = 1;
Point[2].val = B->start;
Point[2].type = INT_POINT_START;
Point[2].num = 2;
Point[3].val = B->end;
Point[3].type = INT_POINT_END;
Point[3].num = 2;
mergeSort(Point, ARRAY_SIZE(Point), sizeof(IntervalPoints_t), comp_bracket);
mergeSort(Point, ARRAY_SIZE(Point), sizeof(IntervalPoints_t), comp_num);
mergeSort(Point, ARRAY_SIZE(Point), sizeof(IntervalPoints_t), comp_points);
int32_t i = 0;
int32_t line_cnt = 0;
for(i = 0; i < ARRAY_SIZE(Point); i++) {
switch(Point[i].type) {
case INT_POINT_START:
line_cnt++;
break;
case INT_POINT_END:
line_cnt--;
break;
default:
break;
}
if(2 == line_cnt) {
if(false == spot_start) {
commom_e.start = Point[i].val;
spot_start = true;
}
}
if(line_cnt < 2) {
if(spot_start) {
if(false == spot_end) {
spot_end = true;
commom_e.end = Point[i].val;
}
}
}
}
IntervalS_t commom_s = {0};
res = IntervalConvert_e_s(&commom_e, &commom_s);
if(commom_s.size) {
res = true;
} else {
res = false;
}
return res;
}Функция interval_is_dock проверяет, что интервалы стыкуются другу к другу без промежутка.
bool interval_is_dock(const IntervalE_t* const pA, const IntervalE_t* const pB) {
bool dock = false;
if(pA->end == pB->start) {
dock = true;
}
if(pB->end == pA->start) {
dock = true;
}
return dock;
}
И проверка, что один интервал поглощает другой интервал
static bool interval_is_a_in_b(const IntervalE_t* const pA,
const IntervalE_t* const pB) {
bool res = false;
if(pB->start <= pA->start) {
if(pA->end <= pB->end) {
res = true;
}
}
return res;
}
bool interval_is_merge(IntervalE_t* const pA,
IntervalE_t* const pB) {
bool res = false;
res = interval_is_a_in_b(pA, pB);
if(false == res) {
res = interval_is_a_in_b(pB, pA);
}
return res;
}Вот и весь джентельменский набор.
Арифметику над интервалами лучше выделить в отдельный программный компонент и отдельную папку в репозитории с именем interval. Это пригодится Вам много где. Например для определения пересечения временных интервалов или при пуске NVRAM.
Что можно улучшить
Формально можно построить целую алгебру над интервалами. Определить сумму интервалов, разность интервалов, умножение интервала на число, логические операции "и", "или", "исключающее или", "нет" между интервалами и прочее. Определить строгое [] и нестрогое () вхождения границ интервалов (как в школе). Корректно обрабатывать интервалы-лучи и прочее. Однако самая употребительная задача - это всё же проверять интервалы на пересечения и на поглощение. Остальное - чисто из академического интереса.
Приложения интервальной арифметики
1--Поиск пересечения временных интервалов в расписании транспорта.
2--проверка диапазонов памяти в прошивках. Проверка конфигов для NVRAM на валидность при старте прошивки.
3--построение диаграмм Ганта в программах планировщиках задач.
4--Реализация функции memmove()
Итог
Удалось научиться просто и легко проверять факт наличия пересечения/поглощения абстрактных интервалов. Это открывает дорогу для разработки с NVRAM внутри микроконтроллерных прошивок и многого другого.
Ссылки
№ | Название | URL |
1 | Задача о Выборе Билетов | |
2 | NVRAM для микроконтроллеров | |
3 | ISO 26262-6 разбор документа (или как писать безопасный софт) |
