Вопрос о макросе round_up

Ответ 1

Макрос ROUND_UP полагается на целочисленное деление, чтобы выполнить задание. Он будет работать, только если оба параметра являются целыми числами. Я предполагаю, что N - это число, подлежащее округлению, а S - это интервал, на котором он должен быть округлен. То есть ROUND_UP(12, 5) должен возвращать 15, так как 15 - это первый интервал 5, превышающий 12.

Представьте, что мы округлили, а не вверх. В этом случае макрос будет просто:

#define ROUND_DOWN(N,S) ((N / S) * S)

ROUND_DOWN(12,5) вернет 10, потому что (12/5) в целых делениях равно 2, а 2 * 5 равно 10. Но мы не делаем ROUND_DOWN, мы делаем ROUND_UP. Поэтому, прежде чем делать целочисленное деление, мы хотим добавить столько, сколько можем, не теряя точности. Если бы мы добавили S, это будет работать практически в каждом случае; ROUND_UP(11,5) станет (((11 + 5)/5) * 5), а так как 16/5 в целых делениях равно 3, мы получим 15.

Проблема возникает, когда мы передаем число, которое уже округлено до указанного множителя. ROUND_UP(10, 5) вернет 15, и это неправильно. Поэтому вместо добавления S мы добавляем S-1. Это гарантирует, что мы никогда не будем толкать что-то до следующего "ведра" без необходимости.

Макросы PAGE_ связаны с бинарной математикой. Мы сделаем вид, что имеем дело с 8-битными значениями для простоты. Предположим, что PAGE_SIZE есть 0b00100000. Таким образом, PAGE_SIZE-1 0b00011111. ~(PAGE_SIZE-1) тогда 0b11100000.

Двоичный & будет выровнять два двоичных числа и оставить 1 в любом месте, где оба числа имеют 1. Таким образом, если x был 0b01100111, операция будет выглядеть следующим образом:

  0b01100111  (x)
& 0b11100000  (~(PAGE_SIZE-1))
------------
  0b01100000

Вы заметите, что операция действительно только обнуляла последние 5 бит. Все это. Но это была именно та операция, которая необходима для округления до ближайшего интервала PAGE_SIZE. Обратите внимание, что это работало только потому, что PAGE_SIZE было ровно степенью 2. Это немного напоминает высказывание, что для любого произвольного десятичного числа вы можете округлить до ближайших 100 просто путем обнуления двух последних цифр. Он работает отлично и действительно легко сделать, но не будет работать вообще, если вы пытаетесь округлить до ближайшего кратного 76.

PAGE_ROUND_UP делает то же самое, но добавляет столько, сколько может, на страницу, прежде чем отрезать ее. Мне нравится, как я могу округлить до ближайшего кратного 100, добавив 99 к любому числу, а затем обнулить последние две цифры. (Добавим PAGE_SIZE-1 по той же причине, что и мы добавили S-1 выше.)

Удачи в вашей виртуальной памяти!

Ответ 2

Использование целочисленной арифметики, деление всегда округляется вниз. Чтобы исправить это, вы добавите максимально возможное число, которое не повлияет на результат, если исходный номер был равномерно делимым. Для числа S наибольшее возможное число - S-1.

Округление до степени 2 является особенным, потому что вы можете сделать это с помощью битовых операций. Множество из двух будет иметь ноль в нижнем бите, кратное 4 всегда будет иметь нуль в нижних двух битах и ​​т.д. Двоичное представление мощности 2 - это один бит, за которым следует куча нулей; вычитание 1 очистит этот бит и установит все биты вправо. Инвертирование этого значения создает битную маску с нулями в местах, которые необходимо очистить. Оператор и очистит эти биты в вашем значении, таким образом округляя значение вниз. Тот же трюк добавления (PAGE_SIZE-1) к исходному значению заставляет его округлять, а не вниз.

Ответ 3

Макросы округления страницы предполагают, что `PAGE_SIZE является степенью двух, например:

0x0400    -- 1 KiB
0x0800    -- 2 KiB`
0x1000    -- 4 KiB

Значением PAGE_SIZE - 1, следовательно, является все бит:

0x03FF
0x07FF
0x0FFF

Следовательно, если целые числа составляли 16 бит (вместо 32 или 64 - это меня сбивало с некоторым типом), то значение ~(PAGE_SIZE-1) равно:

0xFC00
0xFE00
0xF000

Когда вы берете значение x (предполагая, неправдоподобно для реальной жизни, но достаточное для целей изложения, что ULONG_PTR - это неподписанное 16-битовое целое число) 0xBFAB, то

PAGE_SIZE         PAGE_ROUND_DN(0xBFAB)   PAGE_ROUND_UP(0xBFAB)

0x0400     -->    0xBC00                  0xC000
0x0800     -->    0xB800                  0xC000
0x1000     -->    0xB000                  0xC000

Макросы округляются вниз и до ближайшего кратного размера страницы. Последние пять бит будут только обнулены, если PAGE_SIZE == 0x20 (или 32).

Ответ 4

В соответствии с текущим проектом стандарта (C99) этот макрос не совсем корректен, но обратите внимание, что для отрицательных значений N результат будет почти наверняка неверным.

Формула:

#define ROUND_UP(N, S) ((((N) + (S) - 1) / (S)) * (S))

Использует тот факт, что целочисленное деление округляет вниз для неотрицательных целых чисел и использует часть S - 1, чтобы заставить его округлить.

Однако целочисленное деление округляется к нулю (C99, раздел 6.5.5. Мультипликативные операторы, п. 6). Для отрицательного N правильный способ "округления": "N / S", не более, не меньше.

Он становится еще более привлекательным, если S также может быть отрицательным значением, но пусть даже не туда... (см. Как я могу обеспечить, чтобы деление из целых чисел всегда округляется? для более подробного обсуждения различных неправильных и одного или двух правильных решений)

Ответ 5

The и делает это так. Хорошо, давайте возьмем несколько двоичных чисел.

(with 1000 being page size)
PAGE_ROUND_UP(01101b)=
01101b+1000b-1b & ~(1000b-1b) =
01101b+111b & ~(111b) =
01101b+111b & ...11000b = (the ... means 1 continuing for size of ULONG)
10100b & 11000b=
10000b

Итак, как вы можете видеть (надеюсь). Это округляет, добавляя PAGE_SIZE к x, а затем ANDing, чтобы он отменил нижние бит PAGE_SIZE, которые не установлены