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

Question

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

С помощью приведенного выше макроса может кто-нибудь помочь мне разобраться в части "(s) -1", почему это так?

, а также такие макросы, как:

#define PAGE_ROUND_DOWN(x) (((ULONG_PTR)(x)) & (~(PAGE_SIZE-1)))
#define PAGE_ROUND_UP(x) ( (((ULONG_PTR)(x)) + PAGE_SIZE-1)  & (~(PAGE_SIZE-1)) ) 

Я знаю, что часть "(~ (PAGE_SIZE-1)))" обнулит последние пять битов, но, кроме того, я ничего не понимаю, особенно роль оператора & & играет.

Спасибо

Answer 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 выше.)

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

Answer 2

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

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

Answer 3

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

Формула:

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

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

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

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

Answer 4

Макросы округления страницы предполагают, что `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).

Answer 5

И делает это так ... ну ладно, давайте возьмем несколько двоичных чисел.

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

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