Domanda sulla macro round_up

Question

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

Con la macro sopra, qualcuno potrebbe aiutarmi a capire la parte "(s) -1", perché?

e anche le macro come:

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

So che la "(~ (PAGE_SIZE-1)))" parte sarà azzerare gli ultimi cinque bit, ma a parte questo io sono all'oscuro, in particolare il l'operatore del ruolo '&' suona.

Grazie,

Answer 1

La macro ROUND_UP si basa sulla divisione integer per eseguire il lavoro. Funzionerà solo se entrambi i parametri sono interi. Suppongo che N sia il numero da arrotondare e S è l'intervallo su cui deve essere arrotondato. Cioè, ROUND_UP(12, 5) dovrebbe restituire 15, poiché 15 è il primo intervallo di 5 maggiore di 12.

Immagina di arrotondare il volume anziché salire. In tal caso, la macro sarebbe semplicemente:

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

ROUND_DOWN(12,5) sarebbe ritorno 10, a causa (12/5) nella divisione intera è 2, e 2 * 5 è 10. Ma non stiamo facendo ROUND_DOWN, stiamo facendo ROUND_UP . Quindi, prima di fare la divisione intera, vogliamo aggiungere il più possibile senza perdere la precisione. Se aggiungessimo S, funzionerebbe in quasi tutti i casi; ROUND_UP(11,5) diventerebbe (((11 + 5)/5) * 5), e dal 16/5 nella divisione intera è 3, otterremmo 15.

Il problema si presenta quando passiamo un numero che è già arrotondato a il multiplo specificato. ROUND_UP(10, 5) restituire 15, e questo è sbagliato. Quindi, invece di aggiungere S, aggiungiamo S-1. Questo garantisce che non spingeremo mai qualcosa fino al prossimo "secchio" inutilmente.

I macro PAGE_ hanno a che fare con la matematica binaria. Faremo finta di avere a che fare con valori a 8 bit per motivi di semplicità. Supponiamo che PAGE_SIZE sia 0b00100000. PAGE_SIZE-1 è quindi 0b00011111. ~(PAGE_SIZE-1) è quindi 0b11100000.

Un binario & allineerà due numeri binari e lascerà un 1 ovunque che entrambi i numeri abbiano un 1.Così, se x era 0b01100111, l'operazione sarebbe andata in questo modo:

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

Noterete che l'operazione in realtà solo azzerato-out gli ultimi 5 bit. È tutto. Ma quella era esattamente l'operazione necessaria per arrotondare al più vicino intervallo di PAGE_SIZE. Si noti che questo ha funzionato solo perché PAGE_SIZE era esattamente una potenza di 2. È un po 'come dire che per qualsiasi numero decimale arbitrario, è possibile arrotondare al 100 più vicino semplicemente azzerando le ultime due cifre. Funziona perfettamente, ed è veramente facile da fare, ma non funzionerebbe affatto se si cercasse di arrotondare al multiplo più vicino di 76.

PAGE_ROUND_UP fa la stessa cosa, ma aggiunge il più possibile la pagina prima di tagliarla. È un po 'come posso arrotondare al multiplo più vicino a 100 aggiungendo 99 a qualsiasi numero e quindi a azzerando le ultime due cifre. (Aggiungiamo PAGE_SIZE-1 per la stessa ragione per cui abbiamo aggiunto S-1 sopra.)

Buona fortuna con la tua memoria virtuale!

Answer 2

Utilizzando aritmetica intera, dividendo sempre arrotonda giù. Per risolvere il problema, aggiungi il numero più grande possibile che non influirà sul risultato se il numero originale è equamente divisibile. Per il numero S, il numero più grande possibile è S-1.

Arrotondare a una potenza di 2 è speciale, perché è possibile farlo con operazioni di bit. Un multiplo di 2 avrà zero nel bit inferiore, un multiplo di 4 avrà sempre zero nei due bit inferiori, ecc. La rappresentazione binaria di una potenza di 2 è un singolo bit seguito da un gruppo di zeri; sottraendo 1 si cancella quel bit e si impostano tutti i bit a destra. L'inversione di quel valore crea un bit mask con zero nelle posizioni che devono essere cancellate. L'operatore & cancellerà quei bit nel proprio valore, arrotondando così il valore. Lo stesso trucco di aggiungere (PAGE_SIZE-1) al valore originale lo fa arrotondare per eccesso anziché per difetto.

Answer 3

Il & lo rende così .. beh ok, consente di prendere alcuni numeri binari.

 
(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 

Quindi, come si può vedere (si spera) Questo completa il quadro con l'aggiunta di PAGE_SIZE a x e poi AND quindi cancella i bit di fondo di PAGE_SIZE che non sono impostati

Answer 4

Le macro pagina di arrotondamento per scontato che `PAGE_SIZE è una potenza di due, ad esempio:

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

Il valore di PAGE_SIZE - 1, pertanto, è tutt'uno bit:

0x03FF 
0x07FF 
0x0FFF 

Pertanto, se gli interi sono stati 16 bit (invece di 32 o 64 - mi fa risparmiare un po 'di battitura), allora il valore di ~(PAGE_SIZE-1) è:

0xFC00 
0xFE00 
0xF000 

Quando si prende il valore di x (assumendo, implausibilmente per davvero vita, ma sufficiente, ai fini di esposizione, che ULONG_PTR è un intero a 16 bit senza segno) è 0xBFAB, quindi

PAGE_SIZE   PAGE_ROUND_DN(0xBFAB) PAGE_ROUND_UP(0xBFAB) 

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

le macro arrotondare e fino al multiplo più vicino di un formato pagina. Gli ultimi cinque bit verrebbero azzerati solo se PAGE_SIZE == 0x20 (o 32).

Answer 5

In base alla bozza standard corrente (C99) questa macro non è del tutto corretta tuttavia, si noti che per i valori negativi di N il risultato sarà quasi certamente errato.

La formula:

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

fa uso del fatto che la divisione intera arrotonda per numeri interi non negativi e utilizza la parte S - 1 forzarlo per arrotondare invece.

Tuttavia, la divisione intera arrotonda a zero (C99, Sezione 6.5.5 Operatori moltiplicativi, elemento 6). Per il valore negativo N, il modo corretto di "arrotondare" è: "N/S", niente di più, niente di meno.

Diventa ancora più coinvolti se S è anche permesso di essere un valore negativo, ma cerchiamo di non addirittura andare lì ... (vedi: How can I ensure that a division of integers is always rounded up? per una discussione più dettagliata dei vari sbagliato e uno o due soluzioni giuste)