Я уже плакался по поводу исключения в x86-64 команд двоично-десятичной арифметики DAA/DAS и плакался по поводу отмены команды проверки целочисленного переполнения INTO. Теперь настала очередь плакаться по поводу выброшенной команды BOUND. Как говорится, леди и джентльмены, подставляйте свои жилетки и декольте. Начинаю плач.

Команда BOUND проверки выхода индекса за границы массива по-своему уникальна в архитектуре x86. Потому что она явным образом предназначена для поддержки процессором языков высокого уровня. В этой части, пожалуй, только она одна такая и есть. Команда имеет два операнда, в первом из них указывается регистр с текущим значением индекса, а во втором – адрес в памяти «кортежа» из пары границ. Если число со знаком в первом операнде не входит в диапазон, заданный вторым операндом – генерируется исключение. Обратите внимание, что это поддержка не только одного какого-нибудь Си, так как границы массива могут быть любые, даже отрицательные.

Я столкнулся с нужностью контроля индексов в те далекие времена, когда в ходу были еще перфокарты. Однажды никак не мог понять, почему моя программа делает что-то странное. Коллега предложил включить контроль индексов. В БЭСМ-Алгол для этого была стандартная перфокарта, с пробитым символом «ромбик» и словом КОНТ. Я прямо взвился от такого предложения: «я же все просмотрел, индексы везде в порядке!» Но эту стандартную карту все-таки подложил в колоду. И – опа! – ошибка сразу нашлась! Потому что, будучи молодым и наивным программистом, я смотрел в текст своей программы и видел в нем только то, что хотел видеть, а не то, что там написано в реальности.

Вскоре случилась еще одна история. В те золотые времена разработки носителя «Энергия» был у нас сотрудник, занимавшийся расчетом динамических нагрузок. Ему приходилось обсчитывать много вариантов, а каждый расчет занимал часа полтора. Сейчас такие задачи почему-то с оттенком пренебрежения называют «числодробилками». Но в те времена почти все программы были такими. Так вот, он заказывал на каждую ночь два часа работы на БЭСМ-6, а утром забирал результат. Однажды вечером прямо в машинный зал вошли два других сотрудника в надежде быстрее прогнать свои программы и случайно спихнули ожидавшую ввода колоду того, о ком я рассказываю. Колода упала на пол и рассыпалась. Ну как рассыпалась – только несколько перфокарт отлетело. Они ее подобрали, и оказалось, что одна из отлетевших карт – та самая карта с ромбиком и текстом КОНТ. Сотрудники сообразили, что хозяин колоды, конечно же, не использует ее для своей давно отлаженной программы, а просто хранит, чтобы не искать, если начнет что-то менять. Для этого перфокарты надо было помещать в самый конец колоды за последней значащей перфокартой, которая официально называлась «конец ввода по А3», а на жаргоне даже неприлично – «длинный конец» из-за длинного пробитого столбика дырок. Вот из конца колоды она и отлетела. Карта КОНТ была вставлена на свое место за «длинным концом», инцидент был исчерпан.

Однако на следующее утро хозяин колоды бегал и спрашивал, кто и что делал с его программой? Оказалось, что он понятия не имеет ни о каких картах с ромбиками. Пару лет назад ему один раз составили «паспорт» колоды (с картой КОНТ), и он ничего никогда там не трогал. А вчера КОНТ, получается, выкинули. В результате того, что контроль индексов был выключен, его программа выдала (правильный) результат не за полтора часа, а за несколько минут.

Поэтому с самого начала я воспринял, во-первых, важность контроля индекса, поскольку неверный индекс массива – самый простой способ испортить программу. А во-вторых, то, что к проверкам нужно относиться бережливо, поскольку это дорогие (длительные) операции.

И вот, при переходе от x86 к x86-64 BOUND приказала долго жить. Я встречал в сети разные предположения, почему ее выкинули. Дескать, мешала предсказателю переходов. Но ведь генерация исключения – это вовсе не переход. Дескать, кодов не хватает, а тут занят код 62H. Тоже странно. Ну, заняли бы коды выброшенных команд PUSHAD/POPAD, их не так жалко. Дескать, границы, записанные в памяти, легко испортить вредоносной программой. Ага, а стек нельзя испортить вредоносной программой? И т.д. и т.п. Вплоть до аргумента: «ей никто не пользуется». Но это же замкнутый круг – выкинули, потому, что не пользуются, а пользоваться нельзя, потому, что выкинули.

Команде BOUND вообще как-то не везет. Например, в ее описании в официальной документации INTEL написана чушь собачья. Я не преувеличиваю. Вероятно, в результате технической ошибки пропало несколько слов и получилось, что текущее значение индекса должно быть «меньше или равно верхней границе плюс размер операнда». Прямо так английским по белому и написано «…and less than or equal to the upper bound plus the operand size in bytes».

Причем в переводе на русский в некоторых справочниках проявили творчество и заменили слово «плюс» на «сумму». Так и пишут, что индекс должен быть меньше или равен сумме верхней границы и размера операнда. Но легко убедиться, что никакого размера операнда к верхней границе в BOUND не прибавляется. Например, если граница указана в памяти 10, и индекс в регистре равен 11, BOUND даст исключение.

Но как бы я не плакался, в x86-64 никакой BOUND уже не предусмотрено и приходится жить без нее. И, как и в случае с INTO, встает вопрос: как быстрее и лучше проводить проверку выхода индекса за границы массива?

Еще в стародавние времена предлагался выход в том, чтобы задать допустимый диапазон индекса прямо в типе целой переменной, используемой для индекса. Например, если описать переменную как-нибудь как i int [1..100], указав допустимый диапазон, для использования как индекса массива с границами 1:100, то контроль индексов пойдет «сам собой». Правда, при этом проверки-то в программе все равно не исчезают. Хотя их может стать меньше, чем если проверять индекс при каждом обращении к массиву. Но тут есть и другая сложность. Например, при сортировке надо переставить i-й и i+1-й элементы массива. Даже если i и не выходит за границы массива, i+1 – может выйти, и заданный для i допустимый диапазон в этом случае не спасает. Конечно, можно завести переменную j типа i, присвоить j=i+1; и далее использовать индексы только как переменные, без выражений. Но это некрасиво, не наглядно, громоздко и требует лишних действий.

Поэтому я остановился на реализации проверки индекса при обращении к массиву, а не к переменной-индексу.

Поскольку массив – это набор одинаковых элементов, для доступа к элементу массива по индексу обязательно потребуется умножение индекса на размер элемента массива. В x86 есть удобная форма знакового умножения с тремя операндами: регистр, куда поместить результат, первый сомножитель (может быть переменной в памяти) и второй сомножитель-константа. Для доступа к элементам массива – это как раз то, что надо. Например, доступ к массиву x по индексу i в случае, если размер одного элемента массива 100 байт, осуществляется командами типа:

mov   esi, offset x    ;начало массива x
imul  eax, i,100       ;умножаем размер элемента на индекс
add   esi,eax          ;получаем в esi адрес i-ого элемента

Теперь в x86-64 для контроля выхода индекса за границы вместо использования BOUND требуются явные проверки. Однако добавление напрямую команд сравнения и условных переходов к каждому обращению к элементу массива слишком раздувает код. Поэтому я использовал системный вызов, которому надо передать и текущее значение индекса, и допустимые границы.

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

Поэтому я решил при необходимости контролировать индекс использовать «старую добрую» imul в форме с одним операндом-сомножителем, поскольку у нее второй сомножитель всегда ax/eax/rax, и результат всегда пишется в ax:dx/eax:edx/rax:rdx. В этом случае передавать значение индекса в системный вызов не требуется – он всегда после умножения будет в этой паре регистров. А передавать в этом случае системному вызову нужно только границы-константы. Причем, старшая часть произведения, попадающая в регистр dx/edx/rdx, вообще-то всегда должна быть нулевой или полностью заполненной единичными битами (при отрицательном индексе). И поэтому ее можно как константу не передавать, а только подразумевать.

Рассмотрим простой пример. Пусть имеется массив с границами от 1 до 100 и размером каждого элемента 100 байт. Требуется присвоить некоторое значение i-ому элементу. Под индекс выделяется целочисленная переменная размером 8 байт.

dcl a(1:100) char(100);
dcl i fixed(63);
a(i)='12345678';

При этом получаются вот такие команды без контроля индекса (?SMCCM - это системный вызов заполнения строки):

486B3D0028000064       imul q rdi,I,100
BEE8000000             mov  q rsi,offset @000000E8h
488DBF8C000000         lea    rdi,A+0FFFFFF9Ch[rdi]
B064                   mov    al,100
B108                   mov    cl,8
E800000000             call   ?SMCCM

То же действие, но с контролем индекса:

6A6458                 movsxq rax,100
48F72D00280000         imul q I
6A64                   push   100      ;нижняя граница
6810270000             push   10000    ;верхняя граница
E800000000             call   ?SERV3   ;системный вызов контроля индекса
BEE8000000             mov  q rsi,offset @000000E8h
488DB88C000000         lea    rdi,A+0FFFFFF9Ch[rax]
B064                   mov    al,100
B108                   mov    cl,8
E800000000             call   ?SMCCM

В системный вызов ?SERV3 передаются через стек две границы, умноженные на размер элемента, при этом в RAX:RDX находится произведение индекса i на размер элемента.

Если бы нижняя граница массива начиналась с нуля, использовалась бы другая разновидность системного вызова контроля индекса, поскольку передавать нижнюю всегда нулевую границу не требуется:

6A6458                 movsxq rax,100
48F72D68280000         imul q I
6810270000             push   10000		;верхняя граница
E800000000             call   ?SERV4	;системный вызов контроля
BEE8000000             mov  q rsi,offset @000000E8h
488DB8F0000000         lea    rdi,A[rax]
B064                   mov    al,100
B108                   mov    cl,8
E800000000             call   ?SMCCM

Внутри этих системных вызовов контроля производится сравнение числа, записанного в rax:rdx на попадание в диапазон, переданный константами через стек:

PUBLIC ?SERV3:
      PUSH      0               ;ДОБАВЛЯЕМ НОЛЬ
;---- НЕ НИЖЕ НИЖНЕЙ ГРАНИЦЫ ----
      SUB       [RSP]+18H,RAX
      SBB       [RSP]+000,RDX
      JL        @
      CMP       Q PTR [RSP]+18H,0
      JNZ       ERR
;---- НЕ ВЫШЕ ВЕРХНЕЙ ГРАНИЦЫ ----
@:    MOV       Q PTR [RSP],0
      SUB       [RSP]+10H,RAX
      SBB       [RSP]+000,RDX
      JL        ERR
;---- КОНТРОЛЬ ПРОШЕЛ ----
      ADD       RSP,8           ;ВЫБРОСИЛИ НОЛЬ ИЗ СТЕКА
      RET       16

PUBLIC ?SERV4:
      PUSH      0               ;ДОБАВЛЯЕМ НУЛИ
      PUSH      0
;---- НЕ НИЖЕ НИЖНЕЙ ГРАНИЦЫ ----
      SUB       [RSP]+08H,RAX
      SBB       [RSP]+000,RDX
      JL        @
      CMP       Q PTR [RSP]+08H,0
      JNZ       ERR
;---- НЕ ВЫШЕ ВЕРХНЕЙ ГРАНИЦЫ ----
@:    MOV       Q PTR [RSP],0
      SUB       [RSP]+18H,RAX
      SBB       [RSP]+000,RDX
      JL        ERR
;---- КОНТРОЛЬ ПРОШЕЛ ----
      ADD       RSP,16          ;ВЫБРОСИЛИ ДВА НУЛЯ ИЗ СТЕКА
      RET       8

Может показаться, что проверка старшей половины произведения в регистре RDX избыточна. Вряд ли на практике индекс сможет превысить 2⁶³. Однако в результате ошибок программы в переменной-индексе может оказаться и просто мешанина из нулей и единиц. Поэтому все-таки надежнее проверить и старшую половину произведения. На всякий случай.

Разумеется, есть случаи, когда контроль индексов не требуется. Например, если в программе есть цикл с заголовком

do i=lbound(a) to hbound(a);

и внутри этого цикла в изменение индекса i никто не вмешивается, то использование встроенных функций lbound и hbound гарантирует, что индекс не выйдет за пределы границ массива. Проблема в том, что для доказательства этого требуется кропотливый анализ программы компилятором. Для простых компиляторов такой полный анализ часто недостижим.

Поэтому я использую более простой способ сокращения проверок, заключающийся в том, что ищутся линейные участки кода, т.е. участки, где нет вызовов подпрограмм, переходов или меток, на которые может попасть управление откуда угодно из программы. Если на таком линейном участке встречаются обращения к элементам массивов по индексу, то для первого обращения проверка индекса ставится всегда, а для следующих обращений проверяется, что это такие же границы и такой же индекс (и индекс с предыдущей проверки не изменился). В этом случаях – проверка больше не нужна, так как она уже выполнена ранее.

Например, массивы имеют разные размеры элементов, но одинаковые границы:

dcl a(1:100) char(100);
dcl b(1:100) char(50);
dcl i fixed(63);
a(i)=b(i);

Тогда достаточно только одной проверки индекса, что и сокращает код и ускоряет выполнение:

6A6458                 movsxq rax,100
48F72D803B0000         imul q I
488BF8                 mov  q rdi,rax
6A64                   push   100       ;нижняя граница
6810270000             push   10000     ;верхняя граница
E800000000             call   ?SERV3    ;контроль индекса
486B35803B000032       imul q rsi,I,50	;умножение уже без контроля
488DB6C6270000         lea    rsi,B+0FFFFFFCEh[rsi]
488DBF84000000         lea    rdi,A+0FFFFFF9Ch[rdi]
B064                   mov    al,100
B132                   mov    cl,50
E800000000             call   ?SMCCM

Количество различных команд в x86-64 уже приблизилось к тысяче. В частности, не так давно добавлены команды, связанные с контролем допустимости адресов BNDCL, BNDCU, BNDCN, BNDLDX, BNDMK, BNDMOV, BNDSTX в аббревиатурах которых угадывается слово BOUND (и, кстати, тоже генерирующих исключения при выходе проверяемого адреса из допустимого диапазона), а вот самую простую команду BOUND, единственную команду поддержки языковых конструкций высокого уровня, работавшую еще со времен 80286 на всех типах процессоров, почему-то посчитали ненужной. Хотя, на мой взгляд, рациональнее было бы просто расширить ее префиксом REX до 64-х разрядных значений.

Как и в случае DAA/DAS и INTO, команду BOUND, разумеется, можно функционально заменить совокупностью нескольких других команд. Хотя это раздувает код. Можно также оставить их в коде и обрабатывать исключения от этих команд, как от запрещенных. Хотя это замедляет выполнение. Обидно также, что прекрасная идея поддержки процессором языков высокого уровня не находит понимания.