регистру длину, в результате чего устанавливается двухбнговый флаг условия. Первый флаг устанавливается в 1, если при сложении произошел перенос, а второй оказывается установленным, если 32-битовый результат сложения ненулевой. Переход в последней команде выполняется только тогда, когда оба флага условия равны 1. После выполнения перехода ra будет содержать длину диапазона адресов, выходящую за пределы первой страницы (дополнительная возможность, которая не запрашивалась).

Если, например, а=0 н /=4096, перенос будет иметь место, однако результат в регистре ra окажется нулевым, так что перехода к метке crosses не будет.

Теперь посмотрим, нельзя ли адаптировать этот метод для RISC-компьютеров, на которых нет команды перехода при наличии переноса и ненулевого результата команды. Примем для простоты размер блока равным 8. Согласно [7] переход по метке CROSSES произойдет только в том случае, если был перенос (т.е. (я -8)+Z > 2) н если результат не равен нулю (т.е. (я -8) + / 2"), что эквивалентно условию (я -8) + / > 2. Это условие, в свою очередь, эквивалентно появлению переноса в последнем сложении при вычислении ((я -8)-l) + Z. Если в компьютере имеется команда переход при наличии переноса, то данный алгоритм можно использовать непосредственно; при этом потребуется пять команд с учетом загрузки константы -8.

Если же такой команды нет, можно воспользоваться тем, что перенос при суммировании х + у происходит тогда н только тогда, когда -л<у, н будет получено выражение

((я-8)-1)<;.

Использование различных тождеств типа -,(лг-1) =-лг дает ряд эквивалентных выражения для предиката "выход за границы блока".

-(я-8)<; -,(я-8)+1<;

(-na&7) + l<Z

На большинстве RISC-компыотеров эти выражения вычисляются за пять или шесть команд.

С другой стороны, очевидно, что выход за границы 8-байтового блока произойдет тогда н только тогда, когда (я&7)+/-1>8. Непосредственному вычислению это выражение не поддается в силу возможного переполнения (которое возникает при очень больших /). Однако если переписать выражение в виде 8-(я&7)</, то его можно вычислить, не вызывая переполнения.

Это дает нам выражение

8-(я&7)<;,

которое на большинстве RISC-компьютеров вычисляется при помощи пяти команд (или четырех, если компьютер имеет команду вычитания из непосредственно заданного значения). При наличии выхода за границы блока одна дополнительная команда вычитания позволяет вычислить значение /-(8-(я &7)), которое дает нам длину поддиапазона адресов, выходящего за пределы первого блока.

3.3. ПРОВЕРКА ПЕРЕСЕЧЕНИЯ ГРАНИЦЫ СТЕПЕНИ 2 61

ГЛАВА 4

АРИФМЕТИЧЕСКИЕ ГРАНИЦЫ

4.1. Проверка границ целых чисел

Под "проверкой границ" {bounds checking) подразумевается проверка того, находится ли целое значение х в пределах диапазона от а до Ь, т.е. выполняется ли соотношение

а<х<Ь.

Считаем, что все упомянутые здесь величины представляют собой целые знаковые числа.

Важным применением данного действия является проверка индексов элементов массива. Например, пусть объявлен одномерный массив Л, нижняя и верхняя граница которого соответственно равны 1 и 10. При обращении к элементу массива A(i) компилятор может сгенерировать код для проверки корректности индекса 1S i S10. Если г выходит за пределы объявленного диапазона индексов, выполняется команда перехода или прерывания для обработки ошибки. В этом разделе показано, что такая проверка может быть выполнена посредством одного сравнения [52]:

i-l<9.

Очевидно, что этот метод лучше предыдущего, поскольку содержит только одну команду условного ветвления; кроме того, значение i-l в дальнейшем можно использовать при адресации элемента массива.

Возникает вопрос: всегда ли справедлива реализация

a<xb=i> х-аЬ-а

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

Лемма. Если а и Ь - знаковые целые числа, причем а<Ь, и если рассматривать вычисленное значение Ь-а как беззнаковое целое число, то это значение корректно представляет арифметическое значение Ь-а.

Доказательство. (Предполагается, что используется 32-разрядный компьютер.) Так как aSb, то значения арифметической разности Ь-а находятся в диапазоне от О до (2" -l)-(-2") = 2 -1. Если истинное значение разности находится в диапазоне от О до 2-1, то вычисленная компьютером разность будет корректна (так как бит знака равен О при рассмотрении результата как целого знакового числа). Таким образом, вычисленный результат будет корректен независимо от того, как он интерпретируется - как знаковое или беззнаковое целое число.

Если значение истанной разности находится между 2 и 2-1, вычисленный компьютером результат будет отличаться от истинного на 2 (поскольку это число не может быть представлено 32 бигами при знаковой интерпретации). Таким образом, при знаковой интерпретации будет получен результат, лежащий в диапазоне от -iP до -1. Результат машинного вычисления также уменьшается на 2 при этом бит знака становится равным 1. Однако если рассматривать вычисленный результат как беззнаковое целое число, то его значение за счет использования бита знака (который при этом имеет вес 2) увеличивается на iP. Следовательно, при рассмотрении результата как беззнакового целого числа он корректно представляет истинное значение.

Теперь мы можем перейти к "теореме границ".

Теорема. Если аиЪ - целые знаковые числа и aib.mo

a<x<b = x-akb-a. (1)

Доказательство. В зависимости от значения х, возможны три случая. Согласно рассмотренной ранее лемме, поскольку в любом из случаев а<Ь, значение 6-я , рассматриваемое как беззнаковое целое число (что и происходит в уравнении (1)), равно арифметическому значению разности Ьиа.

Случай 1: х<а. При этом разность х-а , рассматриваемая как беззнаковое число, равна + Какими бы ни были значения лг и (в диапазоне 32-битовых чисел), выполняется неравенство х + 2>Ь и соответственно х-а + 2 >Ь-а. Следовательно, х-а>Ь-а и обе части уравнения (1) ложны.

Случай 2: а < х < . В этом случае ифмехически x-a<fc-a.TaKKaK а < Jt, то согласно лемме истинное значение разности х-а равно вычисленному значению лг - я , если рассматривать его как беззнаковое. Следовательно, х-а<Ь-а и обе части уравнения (1) истинны.

Случай 3: х > fc. В таком случае х-а>Ь-а. Так как fc й а, в этом случае х>а , и согласно лемме истинное значение разности х-а равно вычисленному значению лг - я , рассматриваемому как беззнаковое число. Следовательно, х-а>Ь-а и обе части уравнения (1) ложны.

Рассмотренная теорема справедлива и для беззнаковых целых а и fc. Для беззнаковых чисел рассмотренцая лемма становится тривиальной, а значит, приведенное выше доказательство теоремы справедливо и для беззнаковых чисел.

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

EcnHa<fc, то a<x<b = x-a<,b-a = b-x<b-a.

EcnHflSfc, то a<x<fc = лf-я<6-й. „

EcnHa<fc, то a<xib = b-x<b-a.

Ест а <b, то а < jc<fc = лг-я-1<6-я-1 =6-лг-1<6-я-1. В последнем преобразовании 6 -я -1 можно заменить на b .

При проверке граничных условий вида -2""SxS2""-l лучше использовать другие преобразования. Проверка таких условий определяет, может ли знаковое число х быть корректно представлено как и-разрядное целое число в дополнительном коде. Ниже приводится несколько равноценных методов проверки для п=8.