70 лет назад, 16 декабря 1947 г. в лабораториях Bell Labs Джон Бардин и Уолтер Браттейн под руководством Уильяма Шокли создали первый действующий биполярный транзистор. 23 декабря Браттейн продемонстрировал ставил коллегам первый транзисторный усилитель. Поэтому этот день часто называют Днем транзистора.

Бардин стоит слева, Браттейн стоит справа, Шокли сидит

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

Но какую работу выполняет транзистор для нас? Давайте отправимся в мысленное путешествие: проследим путь от какой-нибудь высокоуровневой финтифли до нашего именинника — транзистора.

Что взять в качестве отправной точки? Ну вот хотя бы отрисовку кнопки хабраката.

HTML и CSS


Кнопка состоит из пикселей фона, текста, и границы. В коде задается тегом <a>, к которому применяются правила оформления CSS. Например, к границе применяется CSS правило для скругления углов:

border-radius: 3px;
кнопа

Таким образом, граница состоит из четырех отрезков и четырех дуг (“четвертинок” окружности).

Браузер


Для исследования я взял свой любимый Firefox. До того, как FF начнет рисовать нашу кнопку, ему нужно проделать большую работу по парсингу и расчету положения элементов:

  • Загрузить по сети HTML, распарсить, составить DOM-дерево
  • Загрузить по сети CSS, провести лексический анализ, распарсить
  • Привязать к элементам страницы правила с учетом приоритета и наследования
  • Для всех видимых нод DOM составить дерево их прямоугольных областей — фреймов.
  • Для фреймов рассчитать размеры и местонахождение (см. видео)
  • Из фреймов составить слои с учетом с учетом z-index и типа содержимого (<canvas>, SVG, <video>).
  • Создать список отрисовки в порядке: фоновый цвет, фоновое изображение, граница, потомки, outline.


Мы на этих шагах останавливаться подробно не будем. После них наступает собственно отрисовка нужных элементов.

Качаем исходники, чтобы узнать, что там происходит,
Нужно скачать исходный код Mozilla Firefox. По инструкции получаем исходный код Firefox из Mercurial и Visual Studio с инструментами C++. В VS необходимо в настройках отладки подключить символы из symbols.mozilla.org. Интересующий нас код лежит явно где-то в /layout/.

Для того, чтобы найти нужную функцию, я расставлял брейкпоинты в коде, потом запускал Firefox. В браузере я открывал c упрощенную копию страницы, где есть только наша кнопка со стилями, и в полноэкранном режиме — чтобы брейкпоинты не срабатывали на элементы интерфейса самого FF.

За отрисовку границ отвечает файл nsCSSRenderingBorders.cpp. А общая функция отрисовки границ называется (кто бы мог подумать): DrawBorders(). Функция выбирает оптимальный способ отрисовки для различных ситуаций. У нас относительно простой случай: есть border-radius, но границы со всех сторон сплошные (solid) и одного цвета.

Наш if
if (allBordersSame &&
      mCompositeColors[0] == nullptr &&
      mBorderStyles[0] == NS_STYLE_BORDER_STYLE_SOLID &&
      !mAvoidStroke &&
      !mNoBorderRadius)
  {
    // Relatively simple case.
    gfxRect outerRect = ThebesRect(mOuterRect);
    RoundedRect borderInnerRect(outerRect, mBorderRadii);
    borderInnerRect.Deflate(mBorderWidths[eSideTop],
                            mBorderWidths[eSideBottom],
                            mBorderWidths[eSideLeft],
                            mBorderWidths[eSideRight]);

    // Instead of stroking we just use two paths: an inner and an outer.
    // This allows us to draw borders that we couldn't when stroking. For example,
    // borders with a border width >= the border radius. (i.e. when there are
    // square corners on the inside)
    //
    // Further, this approach can be more efficient because the backend
    // doesn't need to compute an offset curve to stroke the path. We know that
    // the rounded parts are elipses we can offset exactly and can just compute
    // a new cubic approximation.
    RefPtr<PathBuilder> builder = mDrawTarget->CreatePathBuilder();
    AppendRoundedRectToPath(builder, mOuterRect, mBorderRadii, true);
    AppendRoundedRectToPath(builder, ToRect(borderInnerRect.rect), borderInnerRect.corners, false);
    RefPtr<Path> path = builder->Finish();
    mDrawTarget->Fill(path, color);
    return;
  }


Есть гораздо более сложные варианты, например стыковка в углах с border-radius разных типов границ dotted и dashed, см. DrawDashedOrDottedCorner(). Там в коде совершенно
шикарные комментарии
    //      radius.width
    // |<----------------->|
    // |                   |
    // |             ___---+-------------
    // |         __--     #|#       ###
    // |       _-        ##|##     #####
    // |     /           ##+##     ##+##
    // |   /             # P #     #####
    // |  |               #|#       ###
    // | |             __--+-------------
    // ||            _-    ^
    // ||          /       |
    // |         /        first dot is filled
    // |        |
    // |       |
    // |      |
    // |      |
    // |      |
    // +------+
    // |##  ##|
    // |##  ##|
    // |##  ##|


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

AppendRoundedRectToPath(builder, mOuterRect, mBorderRadii, true);
AppendRoundedRectToPath(builder, ToRect(borderInnerRect.rect), borderInnerRect.corners, false);
RefPtr<Path> path = builder->Finish();
mDrawTarget->Fill(path, color);

Идем в AppendRoundedRectToPath() в gfx/2d/PathHelpers.cpp.

Опять расставляем брейкпоинты
a9430-clip-21kb

Из комментария к функции узнаем, что уголки отрисовываются по четырем контрольным точкам кривыми Безье. Кривые Безье часто применяются в компьютерной графике, в том числе и для отрисовки дуг кругов и эллипсов. Как мы дальше узнаем из комментария, существует множество вариантов выбора контрольных точек для построения кривой. При этом нам необходимо, чтобы точки 0 и 3 принадлежали сторонам прямоугольника, точки 0, 1 и C лежали на одной прямой, точки 3, 2 и C — на другой. См. рисунок:

mozilla rounded border bezier curve

Нам остается рассчитать соотношения длин отрезков 01/0C и 32/3С. Тут авторы используют приближенные вычисления и получают магическую константу альфа:

const Float alpha = Float(0.55191497064665766025);

К сожалению, статьи с алгоритмом выбора контрольных точек, на которую ссылается комментарий, нет в открытом доступе. Но вообще нужно отметить, что в компьютерной графике алгоритмы часто используют апроксимацию для повышения производительности. Например, Алгоритм Брезенхема позволяет рисовать отрезки и окружности не «в лоб» — решением уравнений y = f(x), а более хитрыми целочисленными операциями. Тоже самое с заливкой и т.д.

Далее в цикле мы идем от угла к углу, с помощью alpha вычисляем координаты контрольных точек и, наконец, вызываем функции отрисовки линии границы и дуги угла:

aPathBuilder->LineTo(p0);
aPathBuilder->BezierTo(p1, p2, p3); 


Полный код AppendRoundedRectToPath()
void
AppendRoundedRectToPath(PathBuilder* aPathBuilder,
                        const Rect& aRect,
                        const RectCornerRadii& aRadii,
                        bool aDrawClockwise)
{
  // For CW drawing, this looks like:
  //
  //  ...******0**      1    C
  //              ****
  //                  ***    2
  //                     **
  //                       *
  //                        *
  //                         3
  //                         *
  //                         *
  //
  // Where 0, 1, 2, 3 are the control points of the Bezier curve for
  // the corner, and C is the actual corner point.
  //
  // At the start of the loop, the current point is assumed to be
  // the point adjacent to the top left corner on the top
  // horizontal.  Note that corner indices start at the top left and
  // continue clockwise, whereas in our loop i = 0 refers to the top
  // right corner.
  //
  // When going CCW, the control points are swapped, and the first
  // corner that's drawn is the top left (along with the top segment).
  //
  // There is considerable latitude in how one chooses the four
  // control points for a Bezier curve approximation to an ellipse.
  // For the overall path to be continuous and show no corner at the
  // endpoints of the arc, points 0 and 3 must be at the ends of the
  // straight segments of the rectangle; points 0, 1, and C must be
  // collinear; and points 3, 2, and C must also be collinear.  This
  // leaves only two free parameters: the ratio of the line segments
  // 01 and 0C, and the ratio of the line segments 32 and 3C.  See
  // the following papers for extensive discussion of how to choose
  // these ratios:
  //
  //   Dokken, Tor, et al. "Good approximation of circles by
  //      curvature-continuous Bezier curves."  Computer-Aided
  //      Geometric Design 7(1990) 33--41.
  //   Goldapp, Michael. "Approximation of circular arcs by cubic
  //      polynomials." Computer-Aided Geometric Design 8(1991) 227--238.
  //   Maisonobe, Luc. "Drawing an elliptical arc using polylines,
  //      quadratic, or cubic Bezier curves."
  //      http://www.spaceroots.org/documents/ellipse/elliptical-arc.pdf
  //
  // We follow the approach in section 2 of Goldapp (least-error,
  // Hermite-type approximation) and make both ratios equal to
  //
  //          2   2 + n - sqrt(2n + 28)
  //  alpha = - * ---------------------
  //          3           n - 4
  //
  // where n = 3( cbrt(sqrt(2)+1) - cbrt(sqrt(2)-1) ).
  //
  // This is the result of Goldapp's equation (10b) when the angle
  // swept out by the arc is pi/2, and the parameter "a-bar" is the
  // expression given immediately below equation (21).
  //
  // Using this value, the maximum radial error for a circle, as a
  // fraction of the radius, is on the order of 0.2 x 10^-3.
  // Neither Dokken nor Goldapp discusses error for a general
  // ellipse; Maisonobe does, but his choice of control points
  // follows different constraints, and Goldapp's expression for
  // 'alpha' gives much smaller radial error, even for very flat
  // ellipses, than Maisonobe's equivalent.
  //
  // For the various corners and for each axis, the sign of this
  // constant changes, or it might be 0 -- it's multiplied by the
  // appropriate multiplier from the list before using.

  const Float alpha = Float(0.55191497064665766025);

  typedef struct { Float a, b; } twoFloats;

  twoFloats cwCornerMults[4] = { { -1,  0 },    // cc == clockwise
                                 {  0, -1 },
                                 { +1,  0 },
                                 {  0, +1 } };
  twoFloats ccwCornerMults[4] = { { +1,  0 },   // ccw == counter-clockwise
                                  {  0, -1 },
                                  { -1,  0 },
                                  {  0, +1 } };

  twoFloats *cornerMults = aDrawClockwise ? cwCornerMults : ccwCornerMults;

  Point cornerCoords[] = { aRect.TopLeft(), aRect.TopRight(),
                           aRect.BottomRight(), aRect.BottomLeft() };

  Point pc, p0, p1, p2, p3;

  if (aDrawClockwise) {
    aPathBuilder->MoveTo(Point(aRect.X() + aRadii[RectCorner::TopLeft].width,
                               aRect.Y()));
  } else {
    aPathBuilder->MoveTo(Point(aRect.X() + aRect.Width() - aRadii[RectCorner::TopRight].width,
                               aRect.Y()));
  }

  for (int i = 0; i < 4; ++i) {
    // the corner index -- either 1 2 3 0 (cw) or 0 3 2 1 (ccw)
    int c = aDrawClockwise ? ((i+1) % 4) : ((4-i) % 4);

    // i+2 and i+3 respectively.  These are used to index into the corner
    // multiplier table, and were deduced by calculating out the long form
    // of each corner and finding a pattern in the signs and values.
    int i2 = (i+2) % 4;
    int i3 = (i+3) % 4;

    pc = cornerCoords[c];

    if (aRadii[c].width > 0.0 && aRadii[c].height > 0.0) {
      p0.x = pc.x + cornerMults[i].a * aRadii[c].width;
      p0.y = pc.y + cornerMults[i].b * aRadii[c].height;

      p3.x = pc.x + cornerMults[i3].a * aRadii[c].width;
      p3.y = pc.y + cornerMults[i3].b * aRadii[c].height;

      p1.x = p0.x + alpha * cornerMults[i2].a * aRadii[c].width;
      p1.y = p0.y + alpha * cornerMults[i2].b * aRadii[c].height;

      p2.x = p3.x - alpha * cornerMults[i3].a * aRadii[c].width;
      p2.y = p3.y - alpha * cornerMults[i3].b * aRadii[c].height;

      aPathBuilder->LineTo(p0);
      aPathBuilder->BezierTo(p1, p2, p3);
    } else {
      aPathBuilder->LineTo(pc);
    }
  }

  aPathBuilder->Close();
}


А вот дальше все зависит от бекенда 2D графики, который использует Mozilla.

Графический движок


Gecko использует платформонезависимую библиотеку Moz2D, которая в свою очередь может использовать один из бекендов: Cairo, Skia, Direct2D, Quartz и NV Path. Например, для Windows доступны Direct2D, Cairo, Skia. Skia является также бекендом Chromium. Поменять бекенд можно в about:config. Бекенды, в свою очередь, могут считать все на CPU, а могут использовать в какой-то мере аппаратное ускорение GPU. Например, у Skia есть свой OpenGL бекенд — Ganesh.

Код Direct2D закрыт, поэтому лучше включим Skia и посмотрим, что она делает. Вызывается функция отрисовки кубической кривой SkPath::cubicTo. Чтобы построить кривую она разбивается алгоритмом де Кастельжо на некоторое число прямых отрезков, которые собственно и отрисовываются (см. core/SkGeometry.cpp).


Машинный код


У меня, если честно, не получилось до конца разобраться во внутренностях Skia, поэтому я сделал шаг назад — к AppendRoundedRectToPath(), где все операции происходят над целыми числами — что может быть проще?

Открыв дизассемблированный код, мы должны найти в нем операцию сложения.

...
142B1863 00 00                add         byte ptr [eax],al  
142B1865 00 8D 43 FF 0F 84    add         byte ptr [ebp-7BF000BDh],cl  
142B186B 67 01 00             add         dword ptr [bx+si],eax  
142B186E 00 99 0F 57 C9 F7    add         byte ptr [ecx-836A8F1h],bl  
142B1874 F9                   stc  
142B1875 8B C3                mov         eax,ebx  
142B1877 8B CA                mov         ecx,edx  
142B1879 99                   cdq  
142B187A F7 7C 24 28          idiv        eax,dword ptr [esp+28h]  
...

Ага! Даже такой далекий от ASM человек, как я, легко догадается, что за сложение отвечает операция ADD. Возьмем первую операцию:

142B1863 00 00 add byte ptr [eax],al
0x142B1863 — адрес в оперативной памяти
0x00 — opcode — код инструкции процессора. Эта Mozilla скомпилирована под х86, и, открыв таблицу инструкций х86, мы увидим, что код 00 означает 8-битную операцию сложения с мнемоникой ADD. Первым операндом может быть регистр или ячейка оперативной памяти, вторым — регистр. Первый операнд складывается со вторым, результат записывается в первый. Поясню, на всякий случай, что регистр — это сверхбыстрая оперативная память внутри процессора, например для хранения промежуточных результатов вычислений.

Второй байт тоже равен 0x00 и называется MOD-REG-R/M. Его биты задают операнды и способ адресации.



MOD = 00b в комбинации с R/M = 000b означает, что используется косвенная адресация
REG = 000b означает, что используется регистр AL (младшие 8-бит регистра EAX)
[eax] — указывает на то, что сложение производится с ячейкой оперативной памяти, адрес которой лежит в регистре EAX

Как же процессор обрабатывает команду ADD?

Процессор


По описанию микроархитектуры Skylake я составил (крайне упрощенный) перечень этапов:

  1. Инструкции x86 выбираются из кэша инструкций L1 32Кб в буффер предекодирования блоками по 16 байт
  2. Предекодированные команды организуются в очередь Instruction Queue (размером 2х25) и попадают в декодеры
  3. Декодер преобразует x86 операцию в 1-4 машинные микрооперации (µOPs). Наша ADD станет 1 µOP для ALU (арифметическо-логическое устройство) и 2 µOP для AGU (устройство вычисления адреса) (см., но это не точно). В целях оптимизации процессор на этом этапе может сливать две х86 инструкции или две микрооперации в одну.
  4. Микрооперации попадают в Allocation Queue (IDQ). Здесь тоже применяются оптимизации, такие как Loop Stream Detector — отключение выборки при обнаружении цикла.
  5. Начинается исполнение: микрооперация попадает в буфер переупорядочения, где оптимизируется порядок будущего исполнения операций. Для ускорения выполнения свободные физические регистры процессора временно переименовываются в нужные для исполнения операции. Производятся другие оптимизации.
  6. Микрооперация попадает в диспетчер Unified Scheduler, который решает в какой момент и в какой порт отправить операции для исполнения вне очередности их поступления. За каждым портом располагается исполнительное устройство. Наши микрооперации попадут в ALU и AGU.


Ядро SkyLake. Изображение с сайта en.wikichip.org.

Повторюсь, это моё очень упрощенное описание и не претендует на точность и полноту. Для дальнейшего ознакомления рекомендую к прочтению пост Путешествие через вычислительный конвейер процессора и статья Процессоры семейства Intel Core i7

АЛУ


Теперь интересно было бы узнать, что происходит в ALU: каким образом складываются числа? К сожалению, информация по конкретной реализации микроархитектуры и АЛУ является коммерческой тайной Intel, поэтому далее обратимся к теории.

Устройство для сложения двух двоичных разрядов (т.е. бит) называется сумматором. На выходе получается сумма и бит переноса.


Источник: Википедия

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


Источник: Википедия

Как видно из рисунка, сумматор составляется из логических элементов: XOR, AND, OR. А каждый логический элемент может быть реализован с помощью нескольких транзисторов. Или даже реле.

Mattausch, CMOS Design, H20/6/6
Пример реализации полного сумматора на КМОП-транзисторах. Источник

Вот мы и добрались до транзистора! Хотя, конечно, на транзисторах работает не только ALU, но и другие блоки процессора, а больше всего транзисторов используется в кэш-памяти в качестве её ячеек.

В реальности схема сумматора в нашем процессоре может быть построена по-другому и быть гораздо сложнее. Например, уже Intel 8008 45 лет назад умел вычислять все биты переноса заранее, чтобы выполнять сложение параллельно (т.н. сумматор с параллельным переносом). Кому интересно, почитайте интересный пост о реверс-инжиниринге ALU Intel 8008 в блоге Ken Shirriff. Т.е. используются различные оптимизации: например, умножение тоже выгодно делать не «в лоб».

Выводы: что мы узнали?


  • Всё сложно
  • Наглядно показано: чтобы решить проблему излишней сложности, инженеры используют разбиение сложных систем на уровни (слои).
  • Многоуровневые архитектуры позволяют обеспечить переносимость: например, Firefox может запускаться в различных ОС и на различном оборудовании.
  • Взаимодействие между уровнями осуществляется за счет открытости спецификаций на интерфейсы, сервисы и форматы данных, например HTML и CSS, С++, набор команд x86 и т.п.
  • В самом низу трудится наш юбиляр — транзистор.

P.S. Т.к. я — дилетант (веб-разработчик), и C++, ASM, архитектуру ВТ знаю совсем чуть-чуть — из институтского курса, я мог что-то и напутать. Пожалуйста, не стесняйтесь присылать замечания.

Комментарии (9)


  1. agens
    24.12.2017 10:24

    Отличная работа.


  1. svistkovr
    24.12.2017 10:28

    Отличная статья. Интересная техно экскурсия получилась.
    Сразу вспомнилась заставка из фильма матрица 2. Сначала мелькают какие-то вспышки сигналов, потом иероглифы разных масштабов которые превращаются в часы.


  1. Barma2012
    24.12.2017 12:46

    Анимашки просто супер — всё доступно и понятно! ))
    Спасибо большое!


  1. dom1n1k
    24.12.2017 14:57

    Тут авторы используют приближенные вычисления и получают магическую константу альфа:
    const Float alpha = Float(0.55191497064665766025);

    Тут дело в том, что воспроизвести кривыми Безье математически строгую окружность невозможно, не умеют они этого. Но можно нарисовать приближенно, с достаточной для практики точностью. То есть единственно-верного значения alpha не существует.

    Я как-то решал для себя эту задачу и получил почти то же самое значение (отличие в 3 знаке после запятой). Авторы статьи, на которую ссылается FF, похоже, подбирали коэффициент для минимизации погрешности по всей длине дуги. А я пошёл по самому простому пути «в лоб» — подобрал альфу так, чтобы на окружность точно попала средняя точка дуги (45 градусов). В этом случае вычисления получаются очень простые, потому что параметр t для всех отрезков будет 0.5, то есть координаты точек можно тупо усреднять.

    Вычисления на бумажке


  1. avorobyov
    24.12.2017 16:52

    Отличная статья. Вначале я решил что будет экскурсия в историю, но автор зашел совершенно с другой стороны.


  1. pronvit
    24.12.2017 17:02

    Статья хороша, но с арифметикой (ее реализацией в железе) и так все понятно. Мне вот всегда было интересно, как в железе устроен конвейер, как процессор «выбирает», «перекодирует», «исполняет». То есть, как получается переход от статической логики к некоторым действиям.


    1. vin2809
      25.12.2017 00:45

      Чего Вы автора мучаете, он же написал, что

      я — дилетант (веб-разработчик), и C++, ASM, архитектуру ВТ знаю совсем чуть-чуть — из институтского курса

      А публикация действительно превосходная с очень неожиданной логикой связи между CSS и транзистором.


    1. dimaviolinist
      25.12.2017 00:45

      Есть отличная книжка. Учебник на русском языке «Цифровая схемотехника и архитектура компьютера» Дэвида Харриса и Сары Харрис.
      Её можно бесплатно скачать. Вёрстка, правда, под планшет, но можно книгу и купить в бумажном варианте. Кстати, FPGA стоят совсем не безумных денег, чуть больше двадцатки долларов (EP4CE10). Её хватит, например, для простеньких и не очень проектов типа Марсоход 2. Если интересно именно поковырять процессор, то Вам сюда.


  1. KirillFormado
    25.12.2017 00:45

    здесь можно сделать ссылку на книгу "код — тайный язык информатики"