Pregunta sobre round_up macro

Question

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

Con la macro anterior, alguien podría ayudarme a entender la parte "(s) -1", ¿por qué?

y también las macros como:

#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))) 

Sé que la "(~ (PAGE_SIZE-1)))" parte será cero fuera de los últimos cinco bits, pero aparte de eso no tengo ni idea, especialmente el papel '&' juega el operador.

Gracias,

Answer 1

La macro ROUND_UP se basa en la división de enteros para realizar el trabajo. Solo funcionará si ambos parámetros son enteros. Supongo que N es el número que se redondeará y S es el intervalo en el que debe redondearse. Es decir, ROUND_UP(12, 5) debe devolver 15, ya que 15 es el primer intervalo de 5 más grande que 12.

Imagine que estábamos redondeando hacia abajo en lugar de hacia arriba. En ese caso, la macro sería simplemente:

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

ROUND_DOWN(12,5) regresarían 10, porque (12/5) en la división entera es 2, y 2 * 5 es 10. Pero no estamos haciendo ROUND_DOWN, que estamos haciendo ROUND_UP . Entonces, antes de hacer la división de enteros, queremos agregar todo lo que podamos sin perder precisión. Si agregamos S, funcionaría en casi todos los casos; ROUND_UP(11,5) se convertiría en (((11 + 5)/5) * 5), y como 16/5 en la división de enteros es 3, obtendríamos 15.

El problema surge cuando pasamos un número que ya está redondeado a el múltiple especificado ROUND_UP(10, 5) devolvería 15, y eso está mal. Entonces, en lugar de agregar S, agregamos S-1. Esto garantiza que nunca empujemos algo al siguiente "cubo" innecesariamente.

Las macros PAGE_ tienen que ver con la matemática binaria. Fingiremos que estamos tratando con valores de 8 bits por simplicidad. Supongamos que PAGE_SIZE es 0b00100000. PAGE_SIZE-1 es así 0b00011111. ~(PAGE_SIZE-1) es entonces 0b11100000.

Un & binario alineará dos números binarios y dejará un 1 en cualquier lugar donde ambos números tengan un 1.Por lo tanto, si x fue 0b01100111, la operación sería algo así:

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

Se habrá dado cuenta de que la operación realmente sólo pone a cero de salida los últimos 5 bits. Eso es todo. Pero esa fue exactamente la operación que se necesitó para redondear al intervalo más cercano de PAGE_SIZE. Tenga en cuenta que esto solo funcionó porque PAGE_SIZE era exactamente una potencia de 2. Es como decir que para cualquier número decimal arbitrario, puede redondear al 100 más cercano simplemente poniendo en cero los últimos dos dígitos. Funciona perfectamente, y es realmente fácil de hacer, pero no funcionaría en absoluto si estuviera intentando redondear al múltiplo 76 más cercano.

PAGE_ROUND_UP hace lo mismo, pero agrega todo lo que puede a la página antes de cortarla Es como hacer un redondeo al múltiplo de 100 más cercano agregando 99 a cualquier número y , luego poniendo a cero los últimos dos dígitos. (Añadimos PAGE_SIZE-1 por la misma razón que agregamos S-1 arriba.)

¡Buena suerte con su memoria virtual!

Answer 2

Usando la aritmética de enteros, dividiendo siempre redondea hacia abajo. Para solucionarlo, agrega el número más grande posible que no afectará el resultado si el número original fue divisible de manera uniforme. Para el número S, el mayor número posible es S-1.

Redondear a una potencia de 2 es especial, porque puede hacerlo con operaciones de bits. Un múltiplo de 2 siempre tendrá un cero en el bit inferior, un múltiplo de 4 siempre tendrá cero en los dos bits inferiores, etc. La representación binaria de una potencia de 2 es un bit único seguido de un montón de ceros; restando 1 borrará ese bit y establecerá todos los bits a la derecha. Invertir ese valor crea una máscara de bits con ceros en los lugares que deben borrarse. El operador & borrará esos bits en su valor, redondeando así el valor. El mismo truco de agregar (PAGE_SIZE-1) al valor original hace que redondee en lugar de hacia abajo.

Answer 3

La & lo hace tan bien ... bien, vamos a tomar algunos números binarios.

 
(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 

Por lo tanto, como se puede ver (con suerte) se redondea hacia arriba mediante la adición de PAGE_SIZE a X y luego AND por lo que anula los bits inferiores de PAGE_SIZE que no estén establecidos

Answer 4

Las macros página de redondeo suponen que `PAGE_SIZE es una potencia de dos, tales como:

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

El valor de PAGE_SIZE - 1, por lo tanto, es todos los bits uno:

0x03FF 
0x07FF 
0x0FFF 

Por lo tanto, si los números enteros fueron 16 bits (en lugar de 32 o 64 - me ahorra algo de tecleo), entonces el valor de ~(PAGE_SIZE-1) es:

0xFC00 
0xFE00 
0xF000 

Cuando se toma el valor de x (suponiendo, inverosímil de verdad la vida, pero suficiente para los fines de exposición, que ULONG_PTR es un entero sin signo de 16 bits) es 0xBFAB, entonces

PAGE_SIZE   PAGE_ROUND_DN(0xBFAB) PAGE_ROUND_UP(0xBFAB) 

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

las macros redondean hacia abajo y hacia arriba al múltiplo más cercano de un tamaño de página. Los últimos cinco bits solo se pondrían a cero si PAGE_SIZE == 0x20 (o 32).

Answer 5

Basado en el borrador actual del estándar (C99) esta macro no es del todo correcta, sin embargo, tenga en cuenta que para los valores negativos de N, el resultado casi seguro será incorrecto.

La fórmula:

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

hace uso del hecho de que la división entera redondea hacia abajo para los números enteros no negativos y utiliza la parte S - 1 para forzarlo a redondear en su lugar.

Sin embargo, la división entera redondea hacia cero (C99, sección 6.5.5. Operadores multiplicadores, elemento 6). Para N negativo, la forma correcta de 'redondear' es 'N/S', nada más, nada menos.

Se hace aún más complicado si S también se le permite ser un valor negativo, pero vamos a ir allí ni siquiera ... (ver: How can I ensure that a division of integers is always rounded up? para una discusión más detallada de varias equivocado y uno o dos soluciones adecuadas)