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

Сегодня будем выводить иконку на черно-белый графический LCD — но это слишком простая задача. Потому что перед тем как её вывести, необходимо её нарисовать. Рисовать можно в Paint, потом использовать генератор, который переведет растровое изображение в код и использовать его для вывода на экран.

Но мы не ищем простых путей, поэтому иконку будем рисовать сами на С++ для CortexM4 микроконтроллера и сразу в ПЗУ, чтобы не зависеть от всех этих внешних программ, заодно и посмотрим как можно отловить ошибки в уже существующем коде (студентов), которые никто не заметил (даже PVS-Studio).

А еще некоторые компиляторы запрещают делать UB для кода исполняющегося во времени компиляции, поэтому можно отлавливать и UB. Например, мой IAR прекрасно ловит переполнения int. Но обо всем поподробнее.

Чтобы было просто — рисовать будем круг.

Как нарисовать круг

Итак, рисовать будем круг, и срисовываем его прямиком с Википедии — вот прямо отсюда.

На С++ от сутдентов это будет выглядеть примерно так:

/*************************************************************************
* Function: drawCircle
*************************************************************************/
template<typename TFrameBuffer>
constexpr void DrawLibrary::drawCircle(TFrameBuffer& framebuffer, const tPoint leftUpperPoint,
                                        const tPoint rightLowerPoint, const size_t width)
{
   const  size_t sizeX= rightLowerPoint.coordinateX - leftUpperPoint.coordinateX;
   const  size_t sizeY = rightLowerPoint.coordinateY - leftUpperPoint.coordinateY;
   const size_t maxDiameter = sizeX < sizeY ? (sizeX) : (sizeY);
  
   size_t radius = maxDiameter / 2U;
   const size_t centerX = radius;
   const size_t centerY = radius;
   
   for (size_t i = 0U; i < width; ++i)
   {
      size_t y = radius;
      size_t x = 0;
      int32_t delta = 1 - radius * 2;
      int32_t error = 0;
      
      while (y >= x)
      {
         const size_t centerXPlusX = centerX + x;
         const size_t centerXPlusY = centerX + y;
         const size_t centerXMinusX = centerX - x;
         const size_t centerXMinusY = centerX - y;
         const size_t centerYPlusY = centerY + y;
         const size_t centerYPlusX = centerY + x;
         const size_t centerYMinusY = centerY - y;
         const size_t centerYMinusX = centerY - x;
   
         framebuffer.setDataInGivenPosition(centerXPlusX,centerYPlusY);
         framebuffer.setDataInGivenPosition(centerXPlusX,centerYMinusY);
         
         framebuffer.setDataInGivenPosition(centerXMinusX,centerYPlusY);
         framebuffer.setDataInGivenPosition(centerXMinusX,centerYMinusY);
         
         framebuffer.setDataInGivenPosition(centerXPlusY,centerYPlusX);
         framebuffer.setDataInGivenPosition(centerXPlusY,centerYMinusX);
         
         framebuffer.setDataInGivenPosition(centerXMinusY,centerYPlusX);
         framebuffer.setDataInGivenPosition(centerXMinusY,centerYMinusX);
        
         error = 2 * (delta + y) - 1;
         if ((delta < 0) && (error <= 0))
         {
            ++x;
            delta += 2 * x + 1;
         }
         else if ((delta > 0) && (error > 0))
         {
            --y;
            delta -= 2 * y + 1;
         }
         else
         {
            ++x;
            --y;
            delta += 2 * (x - y);
         }
      }
      --radius;
   };
}

В этом коде сразу минимум 2 ошибки, которые как будто-бы не влияют на работу функции, но на самом деле еще как влияют, но об этом немного позже. Так вот, одна из этих ошибок UB и вторая — выход за предел массива у буфера buffer. Найти такие ошибки трудно, и даже PVS-Studio обнаружил только UB.

Немного о функции, она рисует круг, вписанный в квадрат с координатами leftUpperPoint и rightLowerPoint, если это прямоугольник, то берется наименьшая из сторон. В строчке 10 как раз так задается диаметр. Остальное отлично описано в википедии.

Буфер в "ПЗУ"

Как вы заметили, функция рисования круга — constexpr — это означает, что рисовать она может во время компиляции. Но для того, чтобы она рисовала во время компиляции, необходимо, чтобы передаваемый buffer, тоже был доступен во время компиляции. Давайте быстренько напишем простейший такой буфер.

template <size_t XsizeInPixels, size_t YsizeInPixels>
class FrameBuffer
{
public:
    constexpr size_t getSize() const
    {
        return std::size(buffer);
    }
    static constexpr size_t getSizeX() 
    {
        return XsizeInPixels;
    }
    static constexpr size_t getSizeY() 
    {
        return YsizeInPixels;
    }
    
    constexpr void setDataInGivenPosition(const size_t x, const size_t y)
    {
      const size_t yPosition = y / 8U; 
      const size_t positionBitInByte = (y - (yPosition * 8U ));
      buffer[y * yPosition + x] |= (1U << positionBitInByte);
    }
    
private:
    uint8_t buffer[XsizeInPixels * YsizeInPixels / 8U] = {};    
};

В нем ничего такого интересного, кроме того, что он имеет constexpr конструктор и constexpr функцию setDataInGivenPosition т.е. формально мы можем создать этот буфер на этапе компиляции и нарисовать туда круг.

Без сомнения, если мы создадим constexpr объект буфера, то он попадет в ПЗУ.

constexpr FrameBuffer<10, 10> oBuffer; //всё - буфер в ПЗУ

Но нарисовать туда не получится, поскольку функция setDataInGivenPosition хоть и constexpr, но не константная и меняет состояние объекта и вызывать её у самого constexpr объекта нельзя — это и логично.

Иконка в ПЗУ и не очень в ПЗУ

Чтобы разрешить проблему, мы можем вызывать эту функцию при инициализации constexpr объекта. Поэтому давайте создадим класс иконка, которая будет просто кругом.

template <typename TBuffer, size_t width>
struct IconCircle
{
   constexpr IconCircle()
   {
      const tPoint leftUpperPoint = {0U, 0U};
      const tPoint rightLowerPoint = {getSizeX(), getSizeY()};
      cDrawLibrary::drawCircle(oFrameBuffer, leftUpperPoint, 
                               rightLowerPoint, width);
   }
   
   TBuffer oFrameBuffer;
   constexpr size_t getSizeX() const {return TBuffer::getSizeX();}
   constexpr size_t getSizeY() const {return TBuffer::getSizeY();}
};

Теперь в constexpr конструкторе мы рисуем круг прямо в oFrameBuffer во время компиляции и наш буфер попадает прямиком в ПЗУ, но это не точно, потому что компилятор может рассчитанные значения подставлять прямо в код, все зависит от того будете ли обращаться к буферу по его адресу или там в цикле по индексу или итератору.

А вот если решите вывести из него один байт, то компилятор просто подставит значение этого байта. Те значения, которые вы не используете, компилятор вообще может выкинуть, ну потому что они не нужны программе, например, решите вывести только 10 байт(ну не нужен вам весь круг почему-то) из иконки не обращаясь через итератор к массиву и, вуаля, будет только 10 этих значении прямо в коде, а остальных байт даже в ПЗУ не будет.

В общем, не суть важно, важно, что теперь мы можем создавать круг прямо в ПЗУ, и никакого кода не будет, максимум только массив байт буфера в ПЗУ.

Выглядит это так:

constexpr static size_t circleDiameter = 32U;
using tIconCircleBuffer = FrameBuffer<circleDiameter, circleDiameter>;
//Создаем иконку круг толщиной 3 пикселя прямиком в ПЗУ
constexpr IconCircle<tIconCircleBuffer, 3U> oIconSplashCircle{};

Весь код который мы до этого тут написали не попал в прошивку, остался только буфер с кругом в ПЗУ. Но, если что, такой код у нас не скомпилируется.... и все из-за тех 2 начальных ошибок, которые я показал в начале статьи.

А вот следующий очень даже скомпилится.

constexpr static size_t circleDiameter = 32U;
using tIconCircleBuffer = FrameBuffer<circleDiameter, circleDiameter>;
//Создаем иконку круг толщиной 3 пикселя прямиком в ОЗУ
IconCircle<tIconCircleBuffer, 3U> oIconCircle{};

Такой код уже будет работать, но не долго, пока программа не обратится к области важных данных, которые мы попортили. Кроме того, этот код генерит кучу написанного выше нами, кода функций, в том числе и рисование круга в буфер, который теперь будет находиться в ОЗУ — но возможно мы так и задумали, может быть мы хотим со временем поменять эту иконку.

Происходит это потому, что мы создали не константный объект oIconCircle, который по определению не может быть в ПЗУ, а значит не может и во время компиляции запустить метод рисования круга.

Ловим переполнение буфера

Переходим теперь к интересному, отлавливанию ошибок переполнения буфера компилятором. Итак, наша ошибка заключается в том, что мы неправильно определили координаты центра. В буфере массив по Х и Y начинается от 0 и до diameter — 1, а в функции, будет переполнение когда мы сложим 2 радиуса, см 29 строку и соответственно обратимся к буферу по координатам diameter, diameter, что явно за пределами массива.

template<typename TFrameBuffer>
static constexpr void DrawLibrary::drawCircle(TFrameBuffer& framebuffer, 
                                       const tPoint leftUpperPoint,
                                       const tPoint rightLowerPoint, 
                                       const size_t width)
{
   const  size_t sizeX= rightLowerPoint.coordinateX - leftUpperPoint.coordinateX;
   const  size_t sizeY= rightLowerPoint.coordinateY - leftUpperPoint.coordinateY;
   
   const size_t maxDiameter = sizeX < sizeY ? sizeX : sizeY;   
   
   size_t radius = maxDiameter / 2U; //самое просто отнять 1 от радиуса

   const size_t centerX = radius;
   const size_t centerY = radius;
   
   for (size_t i = 0U; i < width; ++i)
   {
      //размер буфера от 0 до diameter - 1, но мы задаем так, что
      //максимальное значение точки будет равно diameter == 2 * radius, 
      //что явно находится вне размера буфера.
      size_t y = radius;  
      size_t x = 0U;
      int32_t delta = 1 - radius * 2;
      int32_t error = 0;
      
      while (y >= x)
      {
         ...      
         //строка 29 Вот тут мы прибавляем к centerY + y == 2 * radius  
         framebuffer.setDataInGivenPosition(centerXPlusX,centerYPlusY);        
         framebuffer.setDataInGivenPosition(centerXPlusX,centerYMinusY);
         
         framebuffer.setDataInGivenPosition(centerXMinusX,centerYPlusY);
         framebuffer.setDataInGivenPosition(centerXMinusX,centerYMinusY);
         
         framebuffer.setDataInGivenPosition(centerXPlusY,centerYPlusX);
         framebuffer.setDataInGivenPosition(centerXPlusY,centerYMinusX);
         
         framebuffer.setDataInGivenPosition(centerXMinusY,centerYPlusX);
         framebuffer.setDataInGivenPosition(centerXMinusY,centerYMinusX);
        
         ...
   };
}

Но мы в нашем случае с иконкой в ОЗУ еще этого не обнаружили. А очень хотим обнаружить, но при этом, желаем чтобы иконка была в ОЗУ, а то вдруг мы потом решим поменять её и добавить к кругу рюшечек.

Давайте попробуем отловить это. Как мы помним, если бы мы рисовали кружок на этапе компиляции, то компилятор бы не смог такое УГ скомпилировать, потому что во время компиляции у него будет паника и данные не влезут в отведенный массив.

Таким образом, нам надо попробовать создать точно такой же объект во время компиляции, и если он создастся, то значит все с нашей функцией хорошо, а если нет — то беда.

Нужно учесть, что если мы создадим второй такой же объект он чисто теоретически отъест ПЗУ на размер буфера, хотя конечно реальный компилятор не даст этого сделать, так как этот объект не будет нигде использоваться. Но нам нужно, чтобы все было по правилам. Поэтому воспользуемся static_assert , где и попытаемся создать точно такой же объект.

constexpr static size_t circleDiameter = 32U;
using tIconCircleBuffer = FrameBuffer<circleDiameter, circleDiameter>;
using tIconCircle = IconCircle<tIconCircleBuffer, 3U>;
//Создаем иконку круг толщиной 3 пикселя в ОЗУ
tIconCircle oIconSplashCircle{};
//Пытаемся создать точно такой же объект во время компиляции, 
//если он создастся, то все хорошо
static_assert([](){constexpr tIconCircle oCircle{}; return true;}(), "Hi");

Вот теперь все хорошо, объекта, который создается в static_assert не будет в реальной жизни вообще, но попытка создать его во время компиляции будет, если там у нас приключится выход за пределы массива, то компилятор выдаст, что-то примерно такое:

<source>:202:50: error: array subscript value '144' is outside the bounds of array type 'uint8_t [128]' {aka 'unsigned char [128]'}

Можно лицезреть код здесь

Поправить это можно просто отняв 1 от радиуса

Тоже самое, но минус 1

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

Например, чтобы проверить, что функция setDataInGivenPosition не делает ничего запрещенного, можно написать такой тест

template<typename TBufferType, int maxValueI, int maxValueJ>
struct CompileTimeBufferSetDataTest
{
    static void check()
    {
       static_assert([]() 
       { 
         struct cFrameBufferSetDataInGivenPositionCompileTimeTest 
         {        
           constexpr cFrameBufferSetDataInGivenPositionCompileTimeTest(int i, 
                                                                       int j) 
           {  
             oBuffer.setDataInGivenPosition(i,j); 
             result = true; 
           }       
           TBufferType oBuffer; 
           bool result = true;
         };
         bool result = true;
         for (int i = 0; i < maxValueI; ++i)
         {
             for (int j = 0; j < maxValueJ; ++j)
             {
                cFrameBufferSetDataInGivenPositionCompileTimeTest oTest{i,j};
                result &= oTest.result; 
             }
         }         
         return result; 
       }(), "assert");      
    }    
};

Он просто пробегается по всем x и y от 0 до maxValueI, maxValueJ и вызывает функцию setDataInGivenPosition в конструкторе, и если она сделает что-то нехорошее, то объект не сможет создаться во время компиляции и компилятор выдаст ошибку.

Можно запихнуть в этот код какую-то логику, чтобы проверить работу функции более детально. А потом вызвать её где-нибудь в коде. Я вызвал ее так:

int main()
{
  static IconCircle<tIconCircleBuffer, 3U> oIconSplashCircle{};
 
  constexpr int maxValueI = 32; 
  constexpr int maxValueJ = 32; 
  //Check that with maxValueI there are no index out of bounds  
  CompileTimeBufferSetDataTest<tIconCircleBuffer,maxValueI,maxValueJ>::check(); 
}

IAR ловит UB

На самом деле, в godbolt компиляторы не смогли обнаружить UB, зато его обнаружил PVS-Studio — красавчик.

UB найденное PVS-Studio

<source>:140:1: warning: V1026 The 'delta' variable is incremented in the loop. Undefined behavior will occur in case of signed integer overflow.

А вот IAR не смог откомпилировать такой код, сработала наша заготовка со static_assert

template<typename TFrameBuffer>
constexpr void DrawLibrary::drawCircle(TFrameBuffer& framebuffer, const tPoint leftUpperPoint,
                                        const tPoint rightLowerPoint, const size_t width)
{
   const  size_t sizeX= rightLowerPoint.coordinateX - leftUpperPoint.coordinateX;
   const  size_t sizeY = rightLowerPoint.coordinateY - leftUpperPoint.coordinateY;
   
   const size_t maxDiameter = sizeX < sizeY ? sizeX : sizeY;   
   size_t radius = maxDiameter / 2U - 1U; //беззнаковое целое

   const size_t centerX = radius;
   const size_t centerY = radius;
   
   for (size_t i = 0U; i < width; ++i)
   {
      size_t y = radius;   //беззнаковое целое
      size_t x = 0U;       //беззнаковое целое 
      int32_t delta = 1 - (int32_t)radius * 2; // вот тут порядок мы привел к (int32_t)
      int32_t error = 0;
      
      while (y >= x)
      {
         const size_t centerXPlusX = size_t(centerX + x);
         const size_t centerXPlusY = size_t(centerX + y);
         const size_t centerXMinusX = size_t(centerX - x);
         const size_t centerXMinusY = size_t(centerX - y);
         const size_t centerYPlusY = size_t(centerY + y);
         const size_t centerYPlusX = size_t(centerY + x);
         const size_t centerYMinusY = size_t(centerY - y);
         const size_t centerYMinusX = size_t(centerY - x);
   
         framebuffer.setDataInGivenPosition(centerXPlusX,centerYPlusY);
        
         framebuffer.setDataInGivenPosition(centerXPlusX,centerYMinusY);
         
         framebuffer.setDataInGivenPosition(centerXMinusX,centerYPlusY);
         framebuffer.setDataInGivenPosition(centerXMinusX,centerYMinusY);
         
         framebuffer.setDataInGivenPosition(centerXPlusY,centerYPlusX);
         framebuffer.setDataInGivenPosition(centerXPlusY,centerYMinusX);
         
         framebuffer.setDataInGivenPosition(centerXMinusY,centerYPlusX);
         framebuffer.setDataInGivenPosition(centerXMinusY,centerYMinusX);
        
         error = 2 * (delta + y) - 1; //тут вот тоже все странно
         if ((delta < 0) && (error <= 0))
         {
            ++x;
            delta += (int32_t)2 * x + (int32_t)1;
         }
         else if ((delta > 0) && (error >0))
         {
            --y;
            delta -= 2 * y + 1; // и тут
         }
         else
         {
            ++x;
            --y;
            delta += 2 * (x - y);  //А вот тут вообще не порядок, это UB
         }
      }
      --radius;
   };
}

Таким образом, в IAR кроме выхода за пределы массива можно отловить еще и все UB, которые есть в коде.

Резюме

Понаписал я много, но вы спросите, а иконка то в ПЗУ хоть правильно нарисовалась? Да, после всех доработок метода — и вот он пруф:

Код экспериментов

P.S

Кстати, если вы еще помните про UB вот в этой строчке

delta += 2 * (x - y);

Где x и y это беззнаковые целые, то студенты решили поправить это вот так:

delta += 2 * ((int32_t)x - (int32_t)y);

Как вы думаете, что произошло? Да UB ушел, но .... вместо круга получился Ромб. Вот такое оно бездумное преобразование типов.