16a2d7a95SEric Dumazet #ifndef _LINUX_RECIPROCAL_DIV_H 26a2d7a95SEric Dumazet #define _LINUX_RECIPROCAL_DIV_H 36a2d7a95SEric Dumazet 46a2d7a95SEric Dumazet #include <linux/types.h> 56a2d7a95SEric Dumazet 66a2d7a95SEric Dumazet /* 7*809fa972SHannes Frederic Sowa * This algorithm is based on the paper "Division by Invariant 8*809fa972SHannes Frederic Sowa * Integers Using Multiplication" by Torbjörn Granlund and Peter 9*809fa972SHannes Frederic Sowa * L. Montgomery. 106a2d7a95SEric Dumazet * 11*809fa972SHannes Frederic Sowa * The assembler implementation from Agner Fog, which this code is 12*809fa972SHannes Frederic Sowa * based on, can be found here: 13*809fa972SHannes Frederic Sowa * http://www.agner.org/optimize/asmlib.zip 146a2d7a95SEric Dumazet * 15*809fa972SHannes Frederic Sowa * This optimization for A/B is helpful if the divisor B is mostly 16*809fa972SHannes Frederic Sowa * runtime invariant. The reciprocal of B is calculated in the 17*809fa972SHannes Frederic Sowa * slow-path with reciprocal_value(). The fast-path can then just use 18*809fa972SHannes Frederic Sowa * a much faster multiplication operation with a variable dividend A 19*809fa972SHannes Frederic Sowa * to calculate the division A/B. 206a2d7a95SEric Dumazet */ 216a2d7a95SEric Dumazet 22*809fa972SHannes Frederic Sowa struct reciprocal_value { 23*809fa972SHannes Frederic Sowa u32 m; 24*809fa972SHannes Frederic Sowa u8 sh1, sh2; 25*809fa972SHannes Frederic Sowa }; 266a2d7a95SEric Dumazet 27*809fa972SHannes Frederic Sowa struct reciprocal_value reciprocal_value(u32 d); 286a2d7a95SEric Dumazet 29*809fa972SHannes Frederic Sowa static inline u32 reciprocal_divide(u32 a, struct reciprocal_value R) 306a2d7a95SEric Dumazet { 31*809fa972SHannes Frederic Sowa u32 t = (u32)(((u64)a * R.m) >> 32); 32*809fa972SHannes Frederic Sowa return (t + ((a - t) >> R.sh1)) >> R.sh2; 336a2d7a95SEric Dumazet } 34*809fa972SHannes Frederic Sowa 35*809fa972SHannes Frederic Sowa #endif /* _LINUX_RECIPROCAL_DIV_H */ 36